X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=src%2Fglsl%2Floop_analysis.cpp;h=21d46ebce536129198256f4520b8392f154c3fe2;hb=e4c540f6d09390013a9cb66060a29f236ad7dcfc;hp=191e92de7c48f7689837f5c769a2784702bf16f2;hpb=82691f12931a022560f8054c8c8e240cd6b2fff4;p=mesa.git diff --git a/src/glsl/loop_analysis.cpp b/src/glsl/loop_analysis.cpp index 191e92de7c4..21d46ebce53 100644 --- a/src/glsl/loop_analysis.cpp +++ b/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); @@ -103,6 +143,34 @@ loop_variable_state::insert(ir_if *if_stmt) } +/** + * 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 { public: loop_analysis(loop_state *loops); @@ -128,6 +196,7 @@ public: exec_list state; }; +} /* anonymous namespace */ loop_analysis::loop_analysis(loop_state *loops) : loops(loops), if_statement_depth(0), current_assignment(NULL) @@ -153,16 +222,15 @@ loop_analysis::visit(ir_loop_jump *ir) 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_in_list(loop_variable_state, ls, &this->state) { + ls->contains_calls = true; + } - ls->contains_calls = true; return visit_continue_with_parent; } @@ -175,35 +243,16 @@ 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(); + bool nested = false; - ir_variable *var = ir->variable_referenced(); - loop_variable *lv = ls->get(var); + 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 (lv == NULL) { - lv = ls->insert(var); - lv->read_before_write = !this->in_assignee; - } - - if (this->in_assignee) { - assert(this->current_assignment != NULL); - - lv->conditional_assignment = (this->if_statement_depth > 0) - || (this->current_assignment->condition != NULL); - - if (lv->first_assignment == NULL) { - assert(lv->num_assignments == 0); - - lv->first_assignment = this->current_assignment; - } - - 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; @@ -236,10 +285,10 @@ loop_analysis::visit_leave(ir_loop *ir) 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(); @@ -251,9 +300,7 @@ loop_analysis::visit_leave(ir_loop *ir) } - 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. */ @@ -281,10 +328,8 @@ loop_analysis::visit_leave(ir_loop *ir) do { progress = false; - foreach_list_safe(node, &ls->variables) { - loop_variable *lv = (loop_variable *) node; - - if (lv->conditional_assignment || (lv->num_assignments > 1)) + foreach_in_list_safe(loop_variable, lv, &ls->variables) { + if (lv->conditional_or_nested_assignment || (lv->num_assignments > 1)) continue; /* Process the RHS of the assignment. If all of the variables @@ -307,9 +352,7 @@ loop_analysis::visit_leave(ir_loop *ir) /* 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 @@ -324,9 +367,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 @@ -336,8 +380,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(); @@ -345,6 +387,74 @@ 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_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; } @@ -469,8 +579,10 @@ get_basic_induction_increment(ir_assignment *ir, hash_table *var_hash) 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; } @@ -503,7 +615,8 @@ is_loop_terminator(ir_if *ir) ir_instruction *const inst = (ir_instruction *) ir->then_instructions.get_head(); - assert(inst != NULL); + if (inst == NULL) + return false; if (inst->ir_type != ir_type_loop_jump) return false;