*
* \arg in_assignee is true if the reference was on the LHS of an assignment.
*
- * \arg in_conditional_code is true if the reference occurred inside an if
- * statement.
+ * \arg in_conditional_code_or_nested_loop is true if the reference occurred
+ * inside an if statement or a nested loop.
*
* \arg current_assignment is the ir_assignment node that the loop variable is
* on the LHS of, if any (ignored if \c in_assignee is false).
*/
void
-loop_variable::record_reference(bool in_assignee, bool in_conditional_code,
+loop_variable::record_reference(bool in_assignee,
+ bool in_conditional_code_or_nested_loop,
ir_assignment *current_assignment)
{
if (in_assignee) {
assert(current_assignment != NULL);
- this->conditional_assignment = in_conditional_code
- || current_assignment->condition != NULL;
+ if (in_conditional_code_or_nested_loop ||
+ current_assignment->condition != NULL) {
+ this->conditional_or_nested_assignment = true;
+ }
if (this->first_assignment == NULL) {
assert(this->num_assignments == 0);
loop_variable_state::insert(ir_if *if_stmt)
{
void *mem_ctx = ralloc_parent(this);
- loop_terminator *t = rzalloc(mem_ctx, loop_terminator);
+ loop_terminator *t = new(mem_ctx) loop_terminator();
t->ir = if_stmt;
this->terminators.push_tail(t);
ir_visitor_status
-loop_analysis::visit_enter(ir_call *ir)
+loop_analysis::visit_enter(ir_call *)
{
- /* If we're not somewhere inside a loop, there's nothing to do. */
- if (this->state.is_empty())
- return visit_continue;
-
- loop_variable_state *const ls =
- (loop_variable_state *) this->state.get_head();
+ /* 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;
+ ls->contains_calls = true;
+ }
- ls->contains_calls = true;
return visit_continue_with_parent;
}
if (this->state.is_empty())
return visit_continue;
- loop_variable_state *const ls =
- (loop_variable_state *) this->state.get_head();
+ bool nested = false;
- ir_variable *var = ir->variable_referenced();
- loop_variable *lv = ls->get_or_insert(var, this->in_assignee);
+ foreach_list(node, &this->state) {
+ loop_variable_state *const ls = (loop_variable_state *) node;
- lv->record_reference(this->in_assignee, this->if_statement_depth > 0,
- this->current_assignment);
+ ir_variable *var = ir->variable_referenced();
+ loop_variable *lv = ls->get_or_insert(var, this->in_assignee);
+
+ lv->record_reference(this->in_assignee,
+ nested || this->if_statement_depth > 0,
+ this->current_assignment);
+ nested = true;
+ }
return visit_continue;
}
foreach_list_safe(node, &ls->variables) {
loop_variable *lv = (loop_variable *) node;
- if (lv->conditional_assignment || (lv->num_assignments > 1))
+ if (lv->conditional_or_nested_assignment || (lv->num_assignments > 1))
continue;
/* Process the RHS of the assignment. If all of the variables
assert(lv->num_assignments == 1);
assert(lv->first_assignment != NULL);
- /* The assignmnet to the variable in the loop must be unconditional.
+ /* The assignment to the variable in the loop must be unconditional and
+ * not inside a nested loop.
*/
- if (lv->conditional_assignment)
+ if (lv->conditional_or_nested_assignment)
continue;
/* Basic loop induction variables have a single assignment in the loop
ir_rvalue *const inc =
get_basic_induction_increment(lv->first_assignment, ls->var_hash);
if (inc != NULL) {
- lv->iv_scale = NULL;
- lv->biv = lv->var;
lv->increment = inc;
lv->remove();
}
}
+ /* 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_list(node, &ls->terminators) {
+ loop_terminator *t = (loop_terminator *) node;
+ 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;
}
projects / mesa.git / blobdiff