#include "loop_analysis.h"
#include "ir_hierarchical_visitor.h"
-static bool is_loop_terminator(ir_if *ir);
+static void try_add_loop_terminator(loop_variable_state *ls, ir_if *ir);
static bool all_expression_operands_are_loop_constant(ir_rvalue *,
hash_table *);
static int
calculate_iterations(ir_rvalue *from, ir_rvalue *to, ir_rvalue *increment,
- enum ir_expression_operation op)
+ enum ir_expression_operation op, bool continue_from_then,
+ bool swap_compare_operands, bool inc_before_terminator)
{
if (from == NULL || to == NULL || increment == NULL)
return -1;
return -1;
}
- if (!iter->type->is_integer()) {
+ if (!iter->type->is_integer_32()) {
const ir_expression_operation op = iter->type->is_double()
? ir_unop_d2i : ir_unop_f2i;
ir_rvalue *cast =
int iter_value = iter->get_int_component(0);
+ /* Code after this block works under assumption that iterator will be
+ * incremented or decremented until it hits the limit,
+ * however the loop condition can be false on the first iteration.
+ * Handle such loops first.
+ */
+ {
+ ir_rvalue *first_value = from;
+ if (inc_before_terminator) {
+ first_value =
+ new(mem_ctx) ir_expression(ir_binop_add, from->type, from, increment);
+ }
+
+ ir_expression *cmp = swap_compare_operands
+ ? new(mem_ctx) ir_expression(op, glsl_type::bool_type, to, first_value)
+ : new(mem_ctx) ir_expression(op, glsl_type::bool_type, first_value, to);
+ if (continue_from_then)
+ cmp = new(mem_ctx) ir_expression(ir_unop_logic_not, cmp);
+
+ ir_constant *const cmp_result = cmp->constant_expression_value(mem_ctx);
+ assert(cmp_result != NULL);
+ if (cmp_result->get_bool_component(0)) {
+ ralloc_free(mem_ctx);
+ return 0;
+ }
+ }
+
/* Make sure that the calculated number of iterations satisfies the exit
* condition. This is needed to catch off-by-one errors and some types of
* ill-formed loops. For example, we need to detect that the following
ir_expression *const add =
new(mem_ctx) ir_expression(ir_binop_add, mul->type, mul, from);
- ir_expression *const cmp =
- new(mem_ctx) ir_expression(op, glsl_type::bool_type, add, to);
+ ir_expression *cmp = swap_compare_operands
+ ? new(mem_ctx) ir_expression(op, glsl_type::bool_type, to, add)
+ : new(mem_ctx) ir_expression(op, glsl_type::bool_type, add, to);
+ if (continue_from_then)
+ cmp = new(mem_ctx) ir_expression(ir_unop_logic_not, cmp);
ir_constant *const cmp_result = cmp->constant_expression_value(mem_ctx);
}
ralloc_free(mem_ctx);
+
+ if (inc_before_terminator) {
+ iter_value--;
+ }
+
return (valid_loop) ? iter_value : -1;
}
+static bool
+incremented_before_terminator(ir_loop *loop, ir_variable *var,
+ ir_if *terminator)
+{
+ for (exec_node *node = loop->body_instructions.get_head();
+ !node->is_tail_sentinel();
+ node = node->get_next()) {
+ ir_instruction *ir = (ir_instruction *) node;
+
+ switch (ir->ir_type) {
+ case ir_type_if:
+ if (ir->as_if() == terminator)
+ return false;
+ break;
+
+ case ir_type_assignment: {
+ ir_assignment *assign = ir->as_assignment();
+ ir_variable *assignee = assign->lhs->whole_variable_referenced();
+
+ if (assignee == var) {
+ assert(assign->condition == NULL);
+ return true;
+ }
+
+ break;
+ }
+
+ default:
+ break;
+ }
+ }
+
+ unreachable("Unable to find induction variable");
+}
/**
* Record the fact that the given loop variable was referenced inside the loop.
loop_state::loop_state()
{
- this->ht = _mesa_hash_table_create(NULL, _mesa_hash_pointer,
- _mesa_key_pointer_equal);
+ this->ht = _mesa_pointer_hash_table_create(NULL);
this->mem_ctx = ralloc_context(NULL);
this->loop_found = false;
}
loop_variable *
loop_variable_state::get(const ir_variable *ir)
{
+ if (ir == NULL)
+ return NULL;
+
hash_entry *entry = _mesa_hash_table_search(this->var_hash, ir);
return entry ? (loop_variable *) entry->data : NULL;
}
loop_terminator *
-loop_variable_state::insert(ir_if *if_stmt)
+loop_variable_state::insert(ir_if *if_stmt, bool continue_from_then)
{
void *mem_ctx = ralloc_parent(this);
loop_terminator *t = new(mem_ctx) loop_terminator();
t->ir = if_stmt;
+ t->continue_from_then = continue_from_then;
+
this->terminators.push_tail(t);
return t;
ir_if *if_stmt = ((ir_instruction *) node)->as_if();
- if ((if_stmt != NULL) && is_loop_terminator(if_stmt))
- ls->insert(if_stmt);
- else
- break;
+ if (if_stmt != NULL)
+ try_add_loop_terminator(ls, if_stmt);
}
switch (cond->operation) {
case ir_binop_less:
- case ir_binop_greater:
- case ir_binop_lequal:
case ir_binop_gequal: {
/* The expressions that we care about will either be of the form
* 'counter < limit' or 'limit < counter'. Figure out which is
ir_rvalue *counter = cond->operands[0]->as_dereference_variable();
ir_constant *limit = cond->operands[1]->as_constant();
enum ir_expression_operation cmp = cond->operation;
+ bool swap_compare_operands = false;
if (limit == NULL) {
counter = cond->operands[1]->as_dereference_variable();
limit = cond->operands[0]->as_constant();
-
- switch (cmp) {
- case ir_binop_less: cmp = ir_binop_greater; break;
- case ir_binop_greater: cmp = ir_binop_less; break;
- case ir_binop_lequal: cmp = ir_binop_gequal; break;
- case ir_binop_gequal: cmp = ir_binop_lequal; break;
- default: assert(!"Should not get here.");
- }
+ swap_compare_operands = true;
}
if ((counter == NULL) || (limit == NULL))
loop_variable *lv = ls->get(var);
if (lv != NULL && lv->is_induction_var()) {
+ bool inc_before_terminator =
+ incremented_before_terminator(ir, var, t->ir);
+
t->iterations = calculate_iterations(init, limit, lv->increment,
- cmp);
+ cmp, t->continue_from_then,
+ swap_compare_operands,
+ inc_before_terminator);
if (t->iterations >= 0 &&
(ls->limiting_terminator == NULL ||
/**
- * Detect whether an if-statement is a loop terminating condition
+ * Detect whether an if-statement is a loop terminating condition, if so
+ * add it to the list of loop terminators.
*
* Detects if-statements of the form
*
- * (if (expression bool ...) (break))
+ * (if (expression bool ...) (...then_instrs...break))
+ *
+ * or
+ *
+ * (if (expression bool ...) ... (...else_instrs...break))
*/
-bool
-is_loop_terminator(ir_if *ir)
+void
+try_add_loop_terminator(loop_variable_state *ls, ir_if *ir)
{
- if (!ir->else_instructions.is_empty())
- return false;
-
- ir_instruction *const inst =
- (ir_instruction *) ir->then_instructions.get_head();
- if (inst == NULL)
- return false;
-
- if (inst->ir_type != ir_type_loop_jump)
- return false;
-
- ir_loop_jump *const jump = (ir_loop_jump *) inst;
- if (jump->mode != ir_loop_jump::jump_break)
- return false;
+ ir_instruction *inst = (ir_instruction *) ir->then_instructions.get_tail();
+ ir_instruction *else_inst =
+ (ir_instruction *) ir->else_instructions.get_tail();
- return true;
+ if (is_break(inst) || is_break(else_inst))
+ ls->insert(ir, is_break(else_inst));
}
projects / mesa.git / blobdiff