diff options
Diffstat (limited to '3rdparty/bgfx/3rdparty/glsl-optimizer/src/glsl/loop_analysis.cpp')
-rw-r--r-- | 3rdparty/bgfx/3rdparty/glsl-optimizer/src/glsl/loop_analysis.cpp | 175 |
1 files changed, 92 insertions, 83 deletions
diff --git a/3rdparty/bgfx/3rdparty/glsl-optimizer/src/glsl/loop_analysis.cpp b/3rdparty/bgfx/3rdparty/glsl-optimizer/src/glsl/loop_analysis.cpp index 240ffc7399d..b0d3e306375 100644 --- a/3rdparty/bgfx/3rdparty/glsl-optimizer/src/glsl/loop_analysis.cpp +++ b/3rdparty/bgfx/3rdparty/glsl-optimizer/src/glsl/loop_analysis.cpp @@ -25,11 +25,10 @@ #include "loop_analysis.h" #include "ir_hierarchical_visitor.h" #include "ir_variable_refcount.h" +#include "util/hash_table.h" static bool is_loop_terminator(ir_if *ir); -static bool used_outside_loops(exec_node *head, ir_variable *var, bool first_assignment); - static bool all_expression_operands_are_loop_constant(ir_rvalue *, hash_table *); @@ -84,6 +83,8 @@ loop_state::loop_state() hash_table_pointer_compare); this->ht_non_inductors = hash_table_ctor(0, hash_table_pointer_hash, hash_table_pointer_compare); + this->ht_variables = hash_table_ctor(0, hash_table_pointer_hash, + hash_table_pointer_compare); this->mem_ctx = ralloc_context(NULL); this->loop_found = false; } @@ -94,6 +95,7 @@ loop_state::~loop_state() hash_table_dtor(this->ht); hash_table_dtor(this->ht_inductors); hash_table_dtor(this->ht_non_inductors); + hash_table_dtor(this->ht_variables); ralloc_free(this->mem_ctx); } @@ -122,10 +124,36 @@ loop_state::get_for_inductor(const ir_variable *ir) return (loop_variable_state *) hash_table_find(this->ht_inductors, ir); } +static void *unreferenced_variable = (void *)1; +static void *assigned_variable = (void *)2; + void -loop_state::insert_non_inductor(ir_variable *var) +loop_state::insert_variable(ir_variable *var) { - // key doesn't matter, just needs to be non-NULL + // data starts as 1. If an assignment is seen, it's replaced with 2. + // this way we can mark a variable as a non-inductor if it's referenced + // other than the first assignment + hash_table_insert(this->ht_variables, unreferenced_variable, var); +} + +void +loop_state::reference_variable(ir_variable *var, bool assignment) +{ + void *ref = hash_table_find(this->ht_variables, var); + + // variable declaration was not seen or already discarded, just ignore + if (ref == NULL) + return; + + if (ref == unreferenced_variable && assignment) + { + hash_table_replace(this->ht_variables, assigned_variable, var); + return; + } + + // variable is referenced and not just in an initial assignment, + // so it cannot be an inductor + hash_table_remove(this->ht_variables, var); hash_table_insert(this->ht_non_inductors, this, var); } @@ -266,10 +294,14 @@ public: virtual ir_visitor_status visit_enter(ir_if *); virtual ir_visitor_status visit_leave(ir_if *); + void visit_general(ir_instruction *); + loop_state *loops; int if_statement_depth; + bool first_pass; + ir_assignment *current_assignment; exec_list state; @@ -277,10 +309,17 @@ public: } /* anonymous namespace */ +void loop_enter_callback(class ir_instruction *ir, void *data) +{ + ((loop_analysis *)data)->visit_general(ir); +} + loop_analysis::loop_analysis(loop_state *loops) - : loops(loops), if_statement_depth(0), current_assignment(NULL) + : loops(loops), if_statement_depth(0), current_assignment(NULL), first_pass(false) { /* empty */ + data_enter = this; + callback_enter = &loop_enter_callback; } @@ -308,16 +347,11 @@ loop_analysis::visit(ir_variable *var) if (!this->state.is_empty()) return visit_continue; - // Check if this variable is used outside a loop anywhere. If it is, it can't be a - // variable that's private to the loop, so can't be an inductor. - // This doesn't reject all possible non-inductors, notably anything declared in an - // outer loop that isn't an inductor in an inner loop, but it can eliminate some - // problem cases - if (used_outside_loops(var->next, var, false)) - { - // add to list of "non inductors" - loops->insert_non_inductor(var); - } + // In the first pass over the instructions we look at variables declared and + // examine their references to determine if they can be an inductor or not + // for the second pass + if (this->first_pass) + loops->insert_variable(var); return visit_continue; } @@ -339,10 +373,15 @@ loop_analysis::visit_enter(ir_call *) ir_visitor_status loop_analysis::visit(ir_dereference_variable *ir) { - /* If we're not somewhere inside a loop, there's nothing to do. + /* If we're not somewhere inside a loop, just check for + * non-inductors */ - if (this->state.is_empty()) + if (this->state.is_empty() || this->first_pass) + { + if (this->state.is_empty() && this->first_pass) + loops->reference_variable(ir->variable_referenced(), this->in_assignee); return visit_continue; + } bool nested = false; @@ -382,8 +421,11 @@ loop_analysis::visit_leave(ir_loop *ir) * 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. + * + * We also skip doing any work in the first pass, where we are just identifying + * variables that cannot be inductors. */ - if (ls->contains_calls) + if (ls->contains_calls || this->first_pass) return visit_continue; foreach_in_list(ir_instruction, node, &ir->body_instructions) { @@ -591,7 +633,7 @@ 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; + return visit_continue; this->current_assignment = ir; @@ -601,10 +643,8 @@ loop_analysis::visit_enter(ir_assignment *ir) 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()); + if (this->state.is_empty()) + return visit_continue; assert(this->current_assignment == ir); this->current_assignment = NULL; @@ -612,6 +652,24 @@ loop_analysis::visit_leave(ir_assignment *ir) return visit_continue; } +void +loop_analysis::visit_general(ir_instruction *ir) +{ + /* If we're inside a loop, we can't start marking things as non-inductors + * Likewise in the second pass we've done all this work, so return early + */ + if (!this->state.is_empty() || !this->first_pass) + return; + + ir_variable_refcount_visitor refs; + ir->accept (&refs); + + struct hash_entry *referenced_var; + hash_table_foreach (refs.ht, referenced_var) { + ir_variable *var = (ir_variable *)referenced_var->key; + loops->reference_variable(var, false); + } +} class examine_rhs : public ir_hierarchical_visitor { public: @@ -733,72 +791,23 @@ is_loop_terminator(ir_if *ir) return true; } - -bool -used_outside_loops(exec_node *head, ir_variable *var, bool first_assignment) -{ - ir_variable_refcount_visitor refs; - for (exec_node* node = head; - !node->is_tail_sentinel(); - node = node->next) - { - ir_instruction *ir = (ir_instruction *) node; - if (ir->ir_type == ir_type_variable) - continue; - - // ignore the first assignment - if (!first_assignment && ir->ir_type == ir_type_assignment) - { - ir_assignment *assign = ir->as_assignment(); - ir_variable *assignee = assign->lhs->whole_variable_referenced(); - - if(assignee == var) - { - first_assignment = true; - continue; - } - } - - // we don't want to recurse into loops - if (ir->ir_type == ir_type_loop) - continue; - - // recurse only for if statements, the other case we would need to recurse is - // loops, but we are looking for uses outside of loops. - if (ir->ir_type == ir_type_if) - { - ir_if *irif = ir->as_if(); - if (used_outside_loops(irif->then_instructions.head, var, first_assignment)) - return true; - if (used_outside_loops(irif->else_instructions.head, var, first_assignment)) - return true; - - // if we didn't find in each branch with our recursion, skip - // otherwise the accept (&refs) below will recurse into loops - // and may give a false positive. - continue; - } - - // we know that we're not inside a loop as we haven't recursed inside, - // and we started outside of a loop, so any references to this variable - // mean it is used outside of any loops - ir->accept (&refs); - if (refs.find_variable_entry(var)) - { - return true; - } - } - - return false; -} - - loop_state * analyze_loop_variables(exec_list *instructions) { loop_state *loops = new loop_state; loop_analysis v(loops); + /* Do two passes over the instructions. The first pass builds a view + * of the variables declared and whether or not they're used outside + * of loops (if so, they cannot be inductors). + * + * In the second pass we apply this information to do the loop analysis + * itself. + */ + v.first_pass = true; v.run(instructions); + v.first_pass = false; + v.run(instructions); + return v.loops; } |