[Mesa-dev] [PATCH 1/3] glsl: Use hash tables in opt_constant_variable().

[Tapani Pälli]

I did not get as impressive results with these 3 patches (how did you 
measure?) but on my machine (HSW GT2) complete shader_runner time goes 
from ~83 secs to ~70secs so it is definitely improving.

I simply do 'time bin/shader_runner' for the measurement.

Tested-by: Tapani Pälli <tapani.palli at intel.com>

On 09/05/2015 12:21 PM, Kenneth Graunke wrote:
> Cuts compile/link time of the fragment shader in bug #91857 by 31%
> (31.79 -> 21.64).  It has over 8,000 variables so linked lists are
> terrible.
>
> Bugzilla: https://bugs.freedesktop.org/show_bug.cgi?id=91857
> Signed-off-by: Kenneth Graunke <kenneth at whitecape.org>
> ---
>   src/glsl/opt_constant_variable.cpp | 39 ++++++++++++++++++++------------------
>   1 file changed, 21 insertions(+), 18 deletions(-)
>
> diff --git a/src/glsl/opt_constant_variable.cpp b/src/glsl/opt_constant_variable.cpp
> index 7aaaeed..cdfbc34 100644
> --- a/src/glsl/opt_constant_variable.cpp
> +++ b/src/glsl/opt_constant_variable.cpp
> @@ -36,11 +36,11 @@
>   #include "ir_visitor.h"
>   #include "ir_optimization.h"
>   #include "glsl_types.h"
> +#include "util/hash_table.h"
>
>   namespace {
>
>   struct assignment_entry {
> -   exec_node link;
>      int assignment_count;
>      ir_variable *var;
>      ir_constant *constval;
> @@ -54,31 +54,32 @@ public:
>      virtual ir_visitor_status visit_enter(ir_assignment *);
>      virtual ir_visitor_status visit_enter(ir_call *);
>
> -   exec_list list;
> +   struct hash_table *ht;
>   };
>
>   } /* unnamed namespace */
>
>   static struct assignment_entry *
> -get_assignment_entry(ir_variable *var, exec_list *list)
> +get_assignment_entry(ir_variable *var, struct hash_table *ht)
>   {
> +   struct hash_entry *hte = _mesa_hash_table_search(ht, var);
>      struct assignment_entry *entry;
>
> -   foreach_list_typed(struct assignment_entry, entry, link, list) {
> -      if (entry->var == var)
> -	 return entry;
> +   if (hte) {
> +      entry = (struct assignment_entry *) hte->data;
> +   } else {
> +      entry = (struct assignment_entry *) calloc(1, sizeof(*entry));
> +      entry->var = var;
> +      _mesa_hash_table_insert(ht, var, entry);
>      }
>
> -   entry = (struct assignment_entry *)calloc(1, sizeof(*entry));
> -   entry->var = var;
> -   list->push_head(&entry->link);
>      return entry;
>   }
>
>   ir_visitor_status
>   ir_constant_variable_visitor::visit(ir_variable *ir)
>   {
> -   struct assignment_entry *entry = get_assignment_entry(ir, &this->list);
> +   struct assignment_entry *entry = get_assignment_entry(ir, this->ht);
>      entry->our_scope = true;
>      return visit_continue;
>   }
> @@ -97,7 +98,7 @@ ir_constant_variable_visitor::visit_enter(ir_assignment *ir)
>      ir_constant *constval;
>      struct assignment_entry *entry;
>
> -   entry = get_assignment_entry(ir->lhs->variable_referenced(), &this->list);
> +   entry = get_assignment_entry(ir->lhs->variable_referenced(), this->ht);
>      assert(entry);
>      entry->assignment_count++;
>
> @@ -150,7 +151,7 @@ ir_constant_variable_visitor::visit_enter(ir_call *ir)
>   	 struct assignment_entry *entry;
>
>   	 assert(var);
> -	 entry = get_assignment_entry(var, &this->list);
> +	 entry = get_assignment_entry(var, this->ht);
>   	 entry->assignment_count++;
>         }
>      }
> @@ -161,7 +162,7 @@ ir_constant_variable_visitor::visit_enter(ir_call *ir)
>         struct assignment_entry *entry;
>
>         assert(var);
> -      entry = get_assignment_entry(var, &this->list);
> +      entry = get_assignment_entry(var, this->ht);
>         entry->assignment_count++;
>      }
>
> @@ -177,20 +178,22 @@ do_constant_variable(exec_list *instructions)
>      bool progress = false;
>      ir_constant_variable_visitor v;
>
> +   v.ht = _mesa_hash_table_create(NULL, _mesa_hash_pointer,
> +                                  _mesa_key_pointer_equal);
>      v.run(instructions);
>
> -   while (!v.list.is_empty()) {
> -
> -      struct assignment_entry *entry;
> -      entry = exec_node_data(struct assignment_entry, v.list.head, link);
> +   struct hash_entry *hte;
> +   hash_table_foreach(v.ht, hte) {
> +      struct assignment_entry *entry = (struct assignment_entry *) hte->data;
>
>         if (entry->assignment_count == 1 && entry->constval && entry->our_scope) {
>   	 entry->var->constant_value = entry->constval;
>   	 progress = true;
>         }
> -      entry->link.remove();
> +      hte->data = NULL;
>         free(entry);
>      }
> +   _mesa_hash_table_destroy(v.ht, NULL);
>
>      return progress;
>   }
>