[Mesa-dev] [PATCH 1/2] glsl: Change copy propagation to use variable -> acp_entry mapping

[Thomas Helland]

Map from ir_variable to acp_entry instead of from lhs to rhs.
Add a field in the acp_entry for the acp_entry of the ir_variable
that is meant to be a replacement for this ir_variable.
Insert both acp_entries in the table mapped to their own ir_variable.
This way we can use only one hash table, and it should make the simpler.
Complexity should drop from O(n^2) to O(1) assuming hash_table lookups
are O(1). Suggestion courtesy of Connor Abbott.
This cuts compilation time on an adaption of the shader in bug 94477
from 95 seconds to 75 on my ivy bridge laptop using i965 with debug.

Bugzilla: https://bugs.freedesktop.org/show_bug.cgi?id=94477
---
 src/compiler/glsl/opt_copy_propagation.cpp | 47 +++++++++++++++++++++++-------
 1 file changed, 37 insertions(+), 10 deletions(-)

diff --git a/src/compiler/glsl/opt_copy_propagation.cpp b/src/compiler/glsl/opt_copy_propagation.cpp
index 247c4988ed..b164a9dcc8 100644
--- a/src/compiler/glsl/opt_copy_propagation.cpp
+++ b/src/compiler/glsl/opt_copy_propagation.cpp
@@ -56,6 +56,29 @@ public:
    ir_variable *var;
 };
 
+class acp_entry : public exec_node
+{
+public:
+   /* override operator new from exec_node */
+   DECLARE_LINEAR_ZALLOC_CXX_OPERATORS(kill_entry)
+
+   acp_entry(ir_variable *var, acp_entry *replacement)
+   {
+      assert(var);
+      this->var = var;
+      dead = false;
+      this->replacement = replacement;
+   }
+
+   ir_variable *var;
+
+   /* The acp_entry for the variable we want to replace this with */
+   acp_entry *replacement;
+
+   bool dead;
+};
+
+
 class ir_copy_propagation_visitor : public ir_hierarchical_visitor {
 public:
    ir_copy_propagation_visitor()
@@ -88,6 +111,7 @@ public:
 
    /** Hash of lhs->rhs: The available copies to propagate */
    hash_table *acp;
+
    /**
     * List of kill_entry: The variables whose values were killed in this
     * block.
@@ -164,8 +188,11 @@ ir_copy_propagation_visitor::visit(ir_dereference_variable *ir)
 
    struct hash_entry *entry = _mesa_hash_table_search(acp, ir->var);
    if (entry) {
-      ir->var = (ir_variable *) entry->data;
-      progress = true;
+      acp_entry *this_acp_entry = (acp_entry *) entry->data;
+      if (this_acp_entry->replacement && !this_acp_entry->replacement->dead) {
+         ir->var = (ir_variable *) this_acp_entry->replacement->var;
+         progress = true;
+      }
    }
 
    return visit_continue;
@@ -307,16 +334,12 @@ ir_copy_propagation_visitor::kill(ir_variable *var)
    /* Remove any entries currently in the ACP for this kill. */
    struct hash_entry *entry = _mesa_hash_table_search(acp, var);
    if (entry) {
+      acp_entry *this_acp_entry = (acp_entry *) entry->data;
+      this_acp_entry->dead = true;
       _mesa_hash_table_remove(acp, entry);
    }
 
-   hash_table_foreach(acp, entry) {
-      if (var == (ir_variable *) entry->data) {
-         _mesa_hash_table_remove(acp, entry);
-      }
-   }
-
-   /* Add the LHS variable to the list of killed variables in this block.
+   /* Add the variable to the list of killed variables in this block.
     */
    this->kills->push_tail(new(this->lin_ctx) kill_entry(var));
 }
@@ -348,7 +371,11 @@ ir_copy_propagation_visitor::add_copy(ir_assignment *ir)
                  lhs_var->data.precise == rhs_var->data.precise) {
          assert(lhs_var);
          assert(rhs_var);
-         _mesa_hash_table_insert(acp, lhs_var, rhs_var);
+         acp_entry *rhs_entry = new(this->lin_ctx) acp_entry(rhs_var, NULL);
+         acp_entry *lhs_entry = new(this->lin_ctx) acp_entry(lhs_var, rhs_entry);
+         _mesa_hash_table_insert(acp, lhs_var, lhs_entry);
+         _mesa_hash_table_insert(acp, rhs_var, rhs_entry);
+         
       }
    }
 }
-- 
2.11.0