ir_visitor_status
-loop_analysis::visit_enter(ir_call *ir)
+loop_analysis::visit_enter(ir_call *)
{
/* Mark every loop that we're currently analyzing as containing an ir_call
* (even those at outer nesting levels).
*/
- foreach_list(node, &this->state) {
- loop_variable_state *const ls = (loop_variable_state *) node;
+ foreach_in_list(loop_variable_state, ls, &this->state) {
ls->contains_calls = true;
}
bool nested = false;
- foreach_list(node, &this->state) {
- loop_variable_state *const ls = (loop_variable_state *) node;
-
+ foreach_in_list(loop_variable_state, ls, &this->state) {
ir_variable *var = ir->variable_referenced();
loop_variable *lv = ls->get_or_insert(var, this->in_assignee);
if (ls->contains_calls)
return visit_continue;
- foreach_list(node, &ir->body_instructions) {
+ foreach_in_list(ir_instruction, node, &ir->body_instructions) {
/* Skip over declarations at the start of a loop.
*/
- if (((ir_instruction *) node)->as_variable())
+ if (node->as_variable())
continue;
ir_if *if_stmt = ((ir_instruction *) node)->as_if();
}
- foreach_list_safe(node, &ls->variables) {
- loop_variable *lv = (loop_variable *) node;
-
+ foreach_in_list_safe(loop_variable, lv, &ls->variables) {
/* Move variables that are already marked as being loop constant to
* a separate list. These trivially don't need to be tested.
*/
do {
progress = false;
- foreach_list_safe(node, &ls->variables) {
- loop_variable *lv = (loop_variable *) node;
-
+ foreach_in_list_safe(loop_variable, lv, &ls->variables) {
if (lv->conditional_or_nested_assignment || (lv->num_assignments > 1))
continue;
/* The remaining variables that are not loop invariant might be loop
* induction variables.
*/
- foreach_list_safe(node, &ls->variables) {
- loop_variable *lv = (loop_variable *) node;
-
+ foreach_in_list_safe(loop_variable, lv, &ls->variables) {
/* If there is more than one assignment to a variable, it cannot be a
* loop induction variable. This isn't strictly true, but this is a
* very simple induction variable detector, and it can't handle more
}
}
+ /* Search the loop terminating conditions for those of the form 'i < c'
+ * where i is a loop induction variable, c is a constant, and < is any
+ * relative operator. From each of these we can infer an iteration count.
+ * Also figure out which terminator (if any) produces the smallest
+ * iteration count--this is the limiting terminator.
+ */
+ foreach_in_list(loop_terminator, t, &ls->terminators) {
+ ir_if *if_stmt = t->ir;
+
+ /* If-statements can be either 'if (expr)' or 'if (deref)'. We only care
+ * about the former here.
+ */
+ ir_expression *cond = if_stmt->condition->as_expression();
+ if (cond == NULL)
+ continue;
+
+ 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
+ * which.
+ */
+ ir_rvalue *counter = cond->operands[0]->as_dereference_variable();
+ ir_constant *limit = cond->operands[1]->as_constant();
+ enum ir_expression_operation cmp = cond->operation;
+
+ 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.");
+ }
+ }
+
+ if ((counter == NULL) || (limit == NULL))
+ break;
+
+ ir_variable *var = counter->variable_referenced();
+
+ ir_rvalue *init = find_initial_value(ir, var);
+
+ loop_variable *lv = ls->get(var);
+ if (lv != NULL && lv->is_induction_var()) {
+ t->iterations = calculate_iterations(init, limit, lv->increment,
+ cmp);
+
+ if (t->iterations >= 0 &&
+ (ls->limiting_terminator == NULL ||
+ t->iterations < ls->limiting_terminator->iterations)) {
+ ls->limiting_terminator = t;
+ }
+ }
+ break;
+ }
+
+ default:
+ break;
+ }
+ }
+
return visit_continue;
}
loop_variable *lv =
(loop_variable *) hash_table_find(var_hash, inc_var);
- if (!lv->is_loop_constant())
- inc = NULL;
+ if (lv == NULL || !lv->is_loop_constant()) {
+ assert(lv != NULL);
+ inc = NULL;
+ }
} else
inc = NULL;
}