diff options
Diffstat (limited to 'mesalib/src/glsl/loop_analysis.cpp')
| -rw-r--r-- | mesalib/src/glsl/loop_analysis.cpp | 196 |
1 files changed, 157 insertions, 39 deletions
diff --git a/mesalib/src/glsl/loop_analysis.cpp b/mesalib/src/glsl/loop_analysis.cpp index b08241af5..fd2b6c923 100644 --- a/mesalib/src/glsl/loop_analysis.cpp +++ b/mesalib/src/glsl/loop_analysis.cpp @@ -33,6 +33,46 @@ static bool all_expression_operands_are_loop_constant(ir_rvalue *, static ir_rvalue *get_basic_induction_increment(ir_assignment *, hash_table *); +/** + * Record the fact that the given loop variable was referenced inside the loop. + * + * \arg in_assignee is true if the reference was on the LHS of an assignment. + * + * \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_or_nested_loop, + ir_assignment *current_assignment) +{ + if (in_assignee) { + assert(current_assignment != 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); + + this->first_assignment = current_assignment; + } + + this->num_assignments++; + } else if (this->first_assignment == current_assignment) { + /* This catches the case where the variable is used in the RHS of an + * assignment where it is also in the LHS. + */ + this->read_before_write = true; + } +} + + loop_state::loop_state() { this->ht = hash_table_ctor(0, hash_table_pointer_hash, @@ -94,7 +134,7 @@ loop_terminator * 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); @@ -102,6 +142,33 @@ loop_variable_state::insert(ir_if *if_stmt) return t; } + +/** + * If the given variable already is recorded in the state for this loop, + * return the corresponding loop_variable object that records information + * about it. + * + * Otherwise, create a new loop_variable object to record information about + * the variable, and set its \c read_before_write field appropriately based on + * \c in_assignee. + * + * \arg in_assignee is true if this variable was encountered on the LHS of an + * assignment. + */ +loop_variable * +loop_variable_state::get_or_insert(ir_variable *var, bool in_assignee) +{ + loop_variable *lv = this->get(var); + + if (lv == NULL) { + lv = this->insert(var); + lv->read_before_write = !in_assignee; + } + + return lv; +} + + namespace { class loop_analysis : public ir_hierarchical_visitor { @@ -157,14 +224,14 @@ loop_analysis::visit(ir_loop_jump *ir) ir_visitor_status loop_analysis::visit_enter(ir_call *ir) { - /* 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; } @@ -177,35 +244,18 @@ loop_analysis::visit(ir_dereference_variable *ir) if (this->state.is_empty()) return visit_continue; - loop_variable_state *const ls = - (loop_variable_state *) this->state.get_head(); - - ir_variable *var = ir->variable_referenced(); - loop_variable *lv = ls->get(var); - - if (lv == NULL) { - lv = ls->insert(var); - lv->read_before_write = !this->in_assignee; - } - - if (this->in_assignee) { - assert(this->current_assignment != NULL); + bool nested = false; - lv->conditional_assignment = (this->if_statement_depth > 0) - || (this->current_assignment->condition != NULL); + foreach_list(node, &this->state) { + loop_variable_state *const ls = (loop_variable_state *) node; - if (lv->first_assignment == NULL) { - assert(lv->num_assignments == 0); - - lv->first_assignment = this->current_assignment; - } + ir_variable *var = ir->variable_referenced(); + loop_variable *lv = ls->get_or_insert(var, this->in_assignee); - lv->num_assignments++; - } else if (lv->first_assignment == this->current_assignment) { - /* This catches the case where the variable is used in the RHS of an - * assignment where it is also in the LHS. - */ - lv->read_before_write = true; + lv->record_reference(this->in_assignee, + nested || this->if_statement_depth > 0, + this->current_assignment); + nested = true; } return visit_continue; @@ -286,7 +336,7 @@ loop_analysis::visit_leave(ir_loop *ir) 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 @@ -326,9 +376,10 @@ loop_analysis::visit_leave(ir_loop *ir) 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 @@ -338,8 +389,6 @@ loop_analysis::visit_leave(ir_loop *ir) 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(); @@ -347,6 +396,75 @@ loop_analysis::visit_leave(ir_loop *ir) } } + /* 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; } |