/* * Copyright © 2010 Intel Corporation * * Permission is hereby granted, free of charge, to any person obtaining a * copy of this software and associated documentation files (the "Software"), * to deal in the Software without restriction, including without limitation * the rights to use, copy, modify, merge, publish, distribute, sublicense, * and/or sell copies of the Software, and to permit persons to whom the * Software is furnished to do so, subject to the following conditions: * * The above copyright notice and this permission notice (including the next * paragraph) shall be included in all copies or substantial portions of the * Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER * DEALINGS IN THE SOFTWARE. */ #include "compiler/glsl_types.h" #include "loop_analysis.h" #include "ir_hierarchical_visitor.h" 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 ir_rvalue *get_basic_induction_increment(ir_assignment *, hash_table *); /** * Find an initializer of a variable outside a loop * * Works backwards from the loop to find the pre-loop value of the variable. * This is used, for example, to find the initial value of loop induction * variables. * * \param loop Loop where \c var is an induction variable * \param var Variable whose initializer is to be found * * \return * The \c ir_rvalue assigned to the variable outside the loop. May return * \c NULL if no initializer can be found. */ static ir_rvalue * find_initial_value(ir_loop *loop, ir_variable *var) { for (exec_node *node = loop->prev; !node->is_head_sentinel(); node = node->prev) { ir_instruction *ir = (ir_instruction *) node; switch (ir->ir_type) { case ir_type_call: case ir_type_loop: case ir_type_loop_jump: case ir_type_return: case ir_type_if: return NULL; case ir_type_function: case ir_type_function_signature: assert(!"Should not get here."); return NULL; case ir_type_assignment: { ir_assignment *assign = ir->as_assignment(); ir_variable *assignee = assign->lhs->whole_variable_referenced(); if (assignee == var) return (assign->condition != NULL) ? NULL : assign->rhs; break; } default: break; } } return NULL; } static int calculate_iterations(ir_rvalue *from, ir_rvalue *to, ir_rvalue *increment, enum ir_expression_operation op, bool continue_from_then) { if (from == NULL || to == NULL || increment == NULL) return -1; void *mem_ctx = ralloc_context(NULL); ir_expression *const sub = new(mem_ctx) ir_expression(ir_binop_sub, from->type, to, from); ir_expression *const div = new(mem_ctx) ir_expression(ir_binop_div, sub->type, sub, increment); ir_constant *iter = div->constant_expression_value(mem_ctx); if (iter == NULL) { ralloc_free(mem_ctx); return -1; } if (!iter->type->is_integer()) { const ir_expression_operation op = iter->type->is_double() ? ir_unop_d2i : ir_unop_f2i; ir_rvalue *cast = new(mem_ctx) ir_expression(op, glsl_type::int_type, iter, NULL); iter = cast->constant_expression_value(mem_ctx); } int iter_value = iter->get_int_component(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 * loop does not have a maximum iteration count. * * for (float x = 0.0; x != 0.9; x += 0.2) * ; */ const int bias[] = { -1, 0, 1 }; bool valid_loop = false; for (unsigned i = 0; i < ARRAY_SIZE(bias); i++) { /* Increment may be of type int, uint or float. */ switch (increment->type->base_type) { case GLSL_TYPE_INT: iter = new(mem_ctx) ir_constant(iter_value + bias[i]); break; case GLSL_TYPE_UINT: iter = new(mem_ctx) ir_constant(unsigned(iter_value + bias[i])); break; case GLSL_TYPE_FLOAT: iter = new(mem_ctx) ir_constant(float(iter_value + bias[i])); break; case GLSL_TYPE_DOUBLE: iter = new(mem_ctx) ir_constant(double(iter_value + bias[i])); break; default: unreachable("Unsupported type for loop iterator."); } ir_expression *const mul = new(mem_ctx) ir_expression(ir_binop_mul, increment->type, iter, increment); ir_expression *const add = new(mem_ctx) ir_expression(ir_binop_add, mul->type, mul, from); ir_expression *cmp = 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); assert(cmp_result != NULL); if (cmp_result->get_bool_component(0)) { iter_value += bias[i]; valid_loop = true; break; } } ralloc_free(mem_ctx); 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. * * \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 = _mesa_hash_table_create(NULL, _mesa_hash_pointer, _mesa_key_pointer_equal); this->mem_ctx = ralloc_context(NULL); this->loop_found = false; } loop_state::~loop_state() { _mesa_hash_table_destroy(this->ht, NULL); ralloc_free(this->mem_ctx); } loop_variable_state * loop_state::insert(ir_loop *ir) { loop_variable_state *ls = new(this->mem_ctx) loop_variable_state; _mesa_hash_table_insert(this->ht, ir, ls); this->loop_found = true; return ls; } loop_variable_state * loop_state::get(const ir_loop *ir) { hash_entry *entry = _mesa_hash_table_search(this->ht, ir); return entry ? (loop_variable_state *) entry->data : NULL; } loop_variable * loop_variable_state::get(const ir_variable *ir) { hash_entry *entry = _mesa_hash_table_search(this->var_hash, ir); return entry ? (loop_variable *) entry->data : NULL; } loop_variable * loop_variable_state::insert(ir_variable *var) { void *mem_ctx = ralloc_parent(this); loop_variable *lv = rzalloc(mem_ctx, loop_variable); lv->var = var; _mesa_hash_table_insert(this->var_hash, lv->var, lv); this->variables.push_tail(lv); return lv; } loop_terminator * 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; } /** * 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); virtual ir_visitor_status visit(ir_loop_jump *); virtual ir_visitor_status visit(ir_dereference_variable *); virtual ir_visitor_status visit_enter(ir_call *); virtual ir_visitor_status visit_enter(ir_loop *); virtual ir_visitor_status visit_leave(ir_loop *); virtual ir_visitor_status visit_enter(ir_assignment *); virtual ir_visitor_status visit_leave(ir_assignment *); virtual ir_visitor_status visit_enter(ir_if *); virtual ir_visitor_status visit_leave(ir_if *); loop_state *loops; int if_statement_depth; ir_assignment *current_assignment; exec_list state; }; } /* anonymous namespace */ loop_analysis::loop_analysis(loop_state *loops) : loops(loops), if_statement_depth(0), current_assignment(NULL) { /* empty */ } ir_visitor_status loop_analysis::visit(ir_loop_jump *ir) { (void) ir; assert(!this->state.is_empty()); loop_variable_state *const ls = (loop_variable_state *) this->state.get_head(); ls->num_loop_jumps++; return visit_continue; } ir_visitor_status 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_in_list(loop_variable_state, ls, &this->state) { ls->contains_calls = true; } return visit_continue_with_parent; } ir_visitor_status loop_analysis::visit(ir_dereference_variable *ir) { /* If we're not somewhere inside a loop, there's nothing to do. */ if (this->state.is_empty()) return visit_continue; bool nested = false; 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); lv->record_reference(this->in_assignee, nested || this->if_statement_depth > 0, this->current_assignment); nested = true; } return visit_continue; } ir_visitor_status loop_analysis::visit_enter(ir_loop *ir) { loop_variable_state *ls = this->loops->insert(ir); this->state.push_head(ls); return visit_continue; } ir_visitor_status loop_analysis::visit_leave(ir_loop *ir) { loop_variable_state *const ls = (loop_variable_state *) this->state.pop_head(); /* Function calls may contain side effects. These could alter any of our * variables in ways that cannot be known, and may even terminate shader * execution (say, calling discard in the fragment shader). So we can't * rely on any of our analysis about assignments to variables. * * We could perform some conservative analysis (prove there's no statically * possible assignment, etc.) but it isn't worth it for now; function * inlining will allow us to unroll loops anyway. */ if (ls->contains_calls) return visit_continue; foreach_in_list(ir_instruction, node, &ir->body_instructions) { /* Skip over declarations at the start of a loop. */ if (node->as_variable()) continue; ir_if *if_stmt = ((ir_instruction *) node)->as_if(); if (if_stmt != NULL) try_add_loop_terminator(ls, if_stmt); } 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. */ if (lv->is_loop_constant()) { lv->remove(); ls->constants.push_tail(lv); } } /* Each variable assigned in the loop that isn't already marked as being loop * constant might still be loop constant. The requirements at this point * are: * * - Variable is written before it is read. * * - Only one assignment to the variable. * * - All operands on the RHS of the assignment are also loop constants. * * The last requirement is the reason for the progress loop. A variable * marked as a loop constant on one pass may allow other variables to be * marked as loop constant on following passes. */ bool progress; do { progress = false; 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 * accessed there are loop constants, then add this */ ir_rvalue *const rhs = lv->first_assignment->rhs; if (all_expression_operands_are_loop_constant(rhs, ls->var_hash)) { lv->rhs_clean = true; if (lv->is_loop_constant()) { progress = true; lv->remove(); ls->constants.push_tail(lv); } } } } while (progress); /* The remaining variables that are not loop invariant might be loop * induction variables. */ 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 * complex cases. */ if (lv->num_assignments > 1) continue; /* All of the variables with zero assignments in the loop are loop * invariant, and they should have already been filtered out. */ assert(lv->num_assignments == 1); assert(lv->first_assignment != NULL); /* The assignment to the variable in the loop must be unconditional and * not inside a nested loop. */ if (lv->conditional_or_nested_assignment) continue; /* Basic loop induction variables have a single assignment in the loop * that has the form 'VAR = VAR + i' or 'VAR = VAR - i' where i is a * loop invariant. */ ir_rvalue *const inc = get_basic_induction_increment(lv->first_assignment, ls->var_hash); if (inc != NULL) { lv->increment = inc; lv->remove(); ls->induction_variables.push_tail(lv); } } /* 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, t->continue_from_then); if (incremented_before_terminator(ir, var, t->ir)) { t->iterations--; } if (t->iterations >= 0 && (ls->limiting_terminator == NULL || t->iterations < ls->limiting_terminator->iterations)) { ls->limiting_terminator = t; } } break; } default: break; } } return visit_continue; } ir_visitor_status loop_analysis::visit_enter(ir_if *ir) { (void) ir; if (!this->state.is_empty()) this->if_statement_depth++; return visit_continue; } ir_visitor_status loop_analysis::visit_leave(ir_if *ir) { (void) ir; if (!this->state.is_empty()) this->if_statement_depth--; return visit_continue; } ir_visitor_status loop_analysis::visit_enter(ir_assignment *ir) { /* If we're not somewhere inside a loop, there's nothing to do. */ if (this->state.is_empty()) return visit_continue_with_parent; this->current_assignment = ir; return visit_continue; } ir_visitor_status loop_analysis::visit_leave(ir_assignment *ir) { /* Since the visit_enter exits with visit_continue_with_parent for this * case, the loop state stack should never be empty here. */ assert(!this->state.is_empty()); assert(this->current_assignment == ir); this->current_assignment = NULL; return visit_continue; } class examine_rhs : public ir_hierarchical_visitor { public: examine_rhs(hash_table *loop_variables) { this->only_uses_loop_constants = true; this->loop_variables = loop_variables; } virtual ir_visitor_status visit(ir_dereference_variable *ir) { hash_entry *entry = _mesa_hash_table_search(this->loop_variables, ir->var); loop_variable *lv = entry ? (loop_variable *) entry->data : NULL; assert(lv != NULL); if (lv->is_loop_constant()) { return visit_continue; } else { this->only_uses_loop_constants = false; return visit_stop; } } hash_table *loop_variables; bool only_uses_loop_constants; }; bool all_expression_operands_are_loop_constant(ir_rvalue *ir, hash_table *variables) { examine_rhs v(variables); ir->accept(&v); return v.only_uses_loop_constants; } ir_rvalue * get_basic_induction_increment(ir_assignment *ir, hash_table *var_hash) { /* The RHS must be a binary expression. */ ir_expression *const rhs = ir->rhs->as_expression(); if ((rhs == NULL) || ((rhs->operation != ir_binop_add) && (rhs->operation != ir_binop_sub))) return NULL; /* One of the of operands of the expression must be the variable assigned. * If the operation is subtraction, the variable in question must be the * "left" operand. */ ir_variable *const var = ir->lhs->variable_referenced(); ir_variable *const op0 = rhs->operands[0]->variable_referenced(); ir_variable *const op1 = rhs->operands[1]->variable_referenced(); if (((op0 != var) && (op1 != var)) || ((op1 == var) && (rhs->operation == ir_binop_sub))) return NULL; ir_rvalue *inc = (op0 == var) ? rhs->operands[1] : rhs->operands[0]; if (inc->as_constant() == NULL) { ir_variable *const inc_var = inc->variable_referenced(); if (inc_var != NULL) { hash_entry *entry = _mesa_hash_table_search(var_hash, inc_var); loop_variable *lv = entry ? (loop_variable *) entry->data : NULL; if (lv == NULL || !lv->is_loop_constant()) { assert(lv != NULL); inc = NULL; } } else inc = NULL; } if ((inc != NULL) && (rhs->operation == ir_binop_sub)) { void *mem_ctx = ralloc_parent(ir); inc = new(mem_ctx) ir_expression(ir_unop_neg, inc->type, inc->clone(mem_ctx, NULL), NULL); } return inc; } /** * 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 ...) (...then_instrs...break)) * * or * * (if (expression bool ...) ... (...else_instrs...break)) */ void try_add_loop_terminator(loop_variable_state *ls, ir_if *ir) { ir_instruction *inst = (ir_instruction *) ir->then_instructions.get_tail(); ir_instruction *else_inst = (ir_instruction *) ir->else_instructions.get_tail(); if (is_break(inst) || is_break(else_inst)) ls->insert(ir, is_break(else_inst)); } loop_state * analyze_loop_variables(exec_list *instructions) { loop_state *loops = new loop_state; loop_analysis v(loops); v.run(instructions); return v.loops; }