summaryrefslogtreecommitdiffstatshomepage
path: root/3rdparty/bgfx/3rdparty/glsl-optimizer/src/glsl/loop_analysis.cpp
diff options
context:
space:
mode:
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.cpp175
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;
}