[Mesa-dev] [RFC 1/2] glsl: Use hash tables for opt_constant_propagation() acp sets.

[Rhys Kidd]

---
 src/glsl/opt_constant_propagation.cpp | 63 +++++++++++++++++++++--------------
 1 file changed, 38 insertions(+), 25 deletions(-)

diff --git a/src/glsl/opt_constant_propagation.cpp b/src/glsl/opt_constant_propagation.cpp
index 184aaa1..b6cbf61 100644
--- a/src/glsl/opt_constant_propagation.cpp
+++ b/src/glsl/opt_constant_propagation.cpp
@@ -95,7 +95,8 @@ public:
       progress = false;
       killed_all = false;
       mem_ctx = ralloc_context(0);
-      this->acp = new(mem_ctx) exec_list;
+      this->acp = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
+                                          _mesa_key_pointer_equal);
       this->kills = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
                                             _mesa_key_pointer_equal);
    }
@@ -118,8 +119,8 @@ public:
    void handle_if_block(exec_list *instructions);
    void handle_rvalue(ir_rvalue **rvalue);
 
-   /** List of acp_entry: The available constants to propagate */
-   exec_list *acp;
+   /** Hash table of acp_entry: The available constants to propagate */
+   hash_table *acp;
 
    /**
     * List of kill_entry: The masks of variables whose values were
@@ -206,11 +207,13 @@ ir_constant_propagation_visitor::constant_propagation(ir_rvalue **rvalue) {
 	 channel = i;
       }
 
-      foreach_in_list(acp_entry, entry, this->acp) {
-	 if (entry->var == deref->var && entry->write_mask & (1 << channel)) {
+      hash_entry *acp_hash_entry;
+      hash_table_foreach(this->acp, acp_hash_entry) {
+         acp_entry *entry = (acp_entry *) acp_hash_entry->data;
+         if (entry->var == deref->var && entry->write_mask & (1 << channel)) {
 	    found = entry;
 	    break;
-	 }
+         }
       }
 
       if (!found)
@@ -264,11 +267,12 @@ ir_constant_propagation_visitor::visit_enter(ir_function_signature *ir)
     * block.  Any instructions at global scope will be shuffled into
     * main() at link time, so they're irrelevant to us.
     */
-   exec_list *orig_acp = this->acp;
+   hash_table *orig_acp = this->acp;
    hash_table *orig_kills = this->kills;
    bool orig_killed_all = this->killed_all;
 
-   this->acp = new(mem_ctx) exec_list;
+   this->acp = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
+                                       _mesa_key_pointer_equal);
    this->kills = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
                                          _mesa_key_pointer_equal);
    this->killed_all = false;
@@ -345,7 +349,8 @@ ir_constant_propagation_visitor::visit_enter(ir_call *ir)
    /* Since we're unlinked, we don't (necssarily) know the side effects of
     * this call.  So kill all copies.
     */
-   acp->make_empty();
+   acp = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
+                                 _mesa_key_pointer_equal);
    this->killed_all = true;
 
    return visit_continue_with_parent;
@@ -354,24 +359,29 @@ ir_constant_propagation_visitor::visit_enter(ir_call *ir)
 void
 ir_constant_propagation_visitor::handle_if_block(exec_list *instructions)
 {
-   exec_list *orig_acp = this->acp;
+   hash_table *orig_acp = this->acp;
    hash_table *orig_kills = this->kills;
    bool orig_killed_all = this->killed_all;
 
-   this->acp = new(mem_ctx) exec_list;
+   this->acp = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
+                                       _mesa_key_pointer_equal);
    this->kills = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
                                          _mesa_key_pointer_equal);
    this->killed_all = false;
 
    /* Populate the initial acp with a constant of the original */
-   foreach_in_list(acp_entry, a, orig_acp) {
-      this->acp->push_tail(new(this->mem_ctx) acp_entry(a));
+   hash_entry *htk;
+   hash_table_foreach(orig_acp, htk) {
+      acp_entry *a = (acp_entry *) htk->data;
+      _mesa_hash_table_insert(this->acp, a,
+                              new(this->mem_ctx) acp_entry(a));
    }
 
    visit_list_elements(this, instructions);
 
    if (this->killed_all) {
-      orig_acp->make_empty();
+      orig_acp = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
+                                         _mesa_key_pointer_equal);
    }
 
    hash_table *new_kills = this->kills;
@@ -379,7 +389,6 @@ ir_constant_propagation_visitor::handle_if_block(exec_list *instructions)
    this->acp = orig_acp;
    this->killed_all = this->killed_all || orig_killed_all;
 
-   hash_entry *htk;
    hash_table_foreach(new_kills, htk) {
       kill_entry *k = (kill_entry *) htk->data;
       kill(k->var, k->write_mask);
@@ -402,7 +411,7 @@ ir_constant_propagation_visitor::visit_enter(ir_if *ir)
 ir_visitor_status
 ir_constant_propagation_visitor::visit_enter(ir_loop *ir)
 {
-   exec_list *orig_acp = this->acp;
+   hash_table *orig_acp = this->acp;
    hash_table *orig_kills = this->kills;
    bool orig_killed_all = this->killed_all;
 
@@ -410,7 +419,8 @@ ir_constant_propagation_visitor::visit_enter(ir_loop *ir)
     * We could go through once, then go through again with the acp
     * cloned minus the killed entries after the first run through.
     */
-   this->acp = new(mem_ctx) exec_list;
+   this->acp = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
+                                       _mesa_key_pointer_equal);
    this->kills = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
                                          _mesa_key_pointer_equal);
    this->killed_all = false;
@@ -418,7 +428,8 @@ ir_constant_propagation_visitor::visit_enter(ir_loop *ir)
    visit_list_elements(this, &ir->body_instructions);
 
    if (this->killed_all) {
-      orig_acp->make_empty();
+      orig_acp = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
+                                         _mesa_key_pointer_equal);
    }
 
    hash_table *new_kills = this->kills;
@@ -446,11 +457,13 @@ ir_constant_propagation_visitor::kill(ir_variable *var, unsigned write_mask)
       return;
 
    /* Remove any entries currently in the ACP for this kill. */
-   foreach_in_list_safe(acp_entry, entry, this->acp) {
+   hash_entry *acp_hash_entry;
+   hash_table_foreach(this->acp, acp_hash_entry) {
+      acp_entry *entry = (acp_entry *) acp_hash_entry->data;
       if (entry->var == var) {
-	 entry->write_mask &= ~write_mask;
-	 if (entry->write_mask == 0)
-	    entry->remove();
+         entry->write_mask &= ~write_mask;
+         if (entry->write_mask == 0)
+            _mesa_hash_table_remove(this->acp, acp_hash_entry);
       }
    }
 
@@ -469,8 +482,8 @@ ir_constant_propagation_visitor::kill(ir_variable *var, unsigned write_mask)
 }
 
 /**
- * Adds an entry to the available constant list if it's a plain assignment
- * of a variable to a variable.
+ * Adds an entry to the available constant hash table if it's a plain
+ * assignment of a variable to a variable.
  */
 void
 ir_constant_propagation_visitor::add_constant(ir_assignment *ir)
@@ -504,7 +517,7 @@ ir_constant_propagation_visitor::add_constant(ir_assignment *ir)
       return;
 
    entry = new(this->mem_ctx) acp_entry(deref->var, ir->write_mask, constant);
-   this->acp->push_tail(entry);
+   _mesa_hash_table_insert(this->acp, deref->var, entry);
 }
 
 } /* unnamed namespace */
-- 
2.1.4