[Mesa-dev] [PATCH 2/2] mesa: Use the new hash table for the variable refcount visitor.

[Ian Romanick]

On 12/03/2012 02:52 PM, Jordan Justen wrote:
> From: Eric Anholt <eric at anholt.net>
>

Were you able to measure a performance improvement on any of the 
problematic cases?

> Reviewed-by: Jordan Justen <jordan.l.justen at intel.com>
> [jordan.l.justen at intel.com: open_hash_table => hash_table]
> Signed-off-by: Jordan Justen <jordan.l.justen at intel.com>
> ---
>   src/glsl/Makefile.am                  |    1 +
>   src/glsl/builtin_compiler/Makefile.am |    1 +
>   src/glsl/ir_variable_refcount.cpp     |   47 ++++++++++++++++++++++++++++-----
>   src/glsl/ir_variable_refcount.h       |   17 +++---------
>   src/glsl/opt_dead_code.cpp            |    8 ++++--
>   5 files changed, 52 insertions(+), 22 deletions(-)
>
> diff --git a/src/glsl/Makefile.am b/src/glsl/Makefile.am
> index 2ba439c..320d947 100644
> --- a/src/glsl/Makefile.am
> +++ b/src/glsl/Makefile.am
> @@ -42,6 +42,7 @@ noinst_PROGRAMS = glsl_compiler glsl_test
>   libglsl_la_SOURCES = \
>   	glsl_lexer.ll \
>   	glsl_parser.cc \
> +	$(top_srcdir)/src/mesa/main/hash_table.c \

Does this need to be here?  If so, what about scons, Android.mk, etc.

>   	$(LIBGLSL_FILES) \
>   	builtin_function.cpp
>
> diff --git a/src/glsl/builtin_compiler/Makefile.am b/src/glsl/builtin_compiler/Makefile.am
> index 5fad35d..d27aca5 100644
> --- a/src/glsl/builtin_compiler/Makefile.am
> +++ b/src/glsl/builtin_compiler/Makefile.am
> @@ -55,6 +55,7 @@ builtin_compiler_SOURCES = \
>   	$(GLSL_BUILDDIR)/glsl_parser.cc \
>   	$(LIBGLSL_FILES) \
>   	$(LIBGLSL_CXX_FILES) \
> +	$(top_srcdir)/src/mesa/main/hash_table.c \
>   	$(top_srcdir)/src/mesa/program/prog_hash_table.c \
>   	$(top_srcdir)/src/mesa/program/symbol_table.c \
>   	$(GLSL_COMPILER_CXX_FILES) \
> diff --git a/src/glsl/ir_variable_refcount.cpp b/src/glsl/ir_variable_refcount.cpp
> index 1633a73..c747833 100644
> --- a/src/glsl/ir_variable_refcount.cpp
> +++ b/src/glsl/ir_variable_refcount.cpp
> @@ -33,7 +33,38 @@
>   #include "ir_visitor.h"
>   #include "ir_variable_refcount.h"
>   #include "glsl_types.h"
> +#include "main/hash_table.h"
>
> +static bool
> +pointer_key_compare(const void *a, const void *b)
> +{
> +   return a == b;
> +}
> +
> +/* We could do better. */
> +static uint32_t
> +pointer_hash(void *a)
> +{
> +   return (uintptr_t)a;

Perhaps...

	return (uintptr_t) a / sizeof(ir_variable);

Or at least shift of the low couple bits.  Otherwise we know a lot of 
bins will be empty, right?  (Or is this not that kind of hash table?)

> +}
> +
> +ir_variable_refcount_visitor::ir_variable_refcount_visitor()
> +{
> +   this->mem_ctx = ralloc_context(NULL);
> +   this->ht = _mesa_hash_table_create(NULL, pointer_key_compare);
> +}
> +
> +static void
> +free_entry(struct hash_entry *entry)
> +{
> +   free(entry->data);

It looks like this is allocated with new (in 
ir_variable_refcount_visitor::get_variable_entry), so this definitely 
should be delete.

> +}
> +
> +ir_variable_refcount_visitor::~ir_variable_refcount_visitor()
> +{
> +   ralloc_free(this->mem_ctx);
> +   _mesa_hash_table_destroy(this->ht, free_entry);
> +}
>
>   // constructor
>   ir_variable_refcount_entry::ir_variable_refcount_entry(ir_variable *var)
> @@ -50,15 +81,17 @@ ir_variable_refcount_entry *
>   ir_variable_refcount_visitor::get_variable_entry(ir_variable *var)
>   {
>      assert(var);
> -   foreach_iter(exec_list_iterator, iter, this->variable_list) {
> -      ir_variable_refcount_entry *entry = (ir_variable_refcount_entry *)iter.get();
> -      if (entry->var == var)
> -	 return entry;
> -   }
>
> -   ir_variable_refcount_entry *entry = new(mem_ctx) ir_variable_refcount_entry(var);
> +   struct hash_entry *e = _mesa_hash_table_search(this->ht,
> +						    pointer_hash(var),
> +						    var);
> +   if (e)
> +      return (ir_variable_refcount_entry *)e->data;
> +
> +   ir_variable_refcount_entry *entry = new ir_variable_refcount_entry(var);
>      assert(entry->referenced_count == 0);
> -   this->variable_list.push_tail(entry);
> +   _mesa_hash_table_insert(this->ht, pointer_hash(var), var, entry);
> +
>      return entry;
>   }
>
> diff --git a/src/glsl/ir_variable_refcount.h b/src/glsl/ir_variable_refcount.h
> index 51a4945..c15e811 100644
> --- a/src/glsl/ir_variable_refcount.h
> +++ b/src/glsl/ir_variable_refcount.h
> @@ -33,7 +33,7 @@
>   #include "ir_visitor.h"
>   #include "glsl_types.h"
>
> -class ir_variable_refcount_entry : public exec_node
> +class ir_variable_refcount_entry
>   {
>   public:
>      ir_variable_refcount_entry(ir_variable *var);
> @@ -52,16 +52,8 @@ public:
>
>   class ir_variable_refcount_visitor : public ir_hierarchical_visitor {
>   public:
> -   ir_variable_refcount_visitor(void)
> -   {
> -      this->mem_ctx = ralloc_context(NULL);
> -      this->variable_list.make_empty();
> -   }
> -
> -   ~ir_variable_refcount_visitor(void)
> -   {
> -      ralloc_free(this->mem_ctx);
> -   }
> +   ir_variable_refcount_visitor(void);
> +   ~ir_variable_refcount_visitor(void);
>
>      virtual ir_visitor_status visit(ir_variable *);
>      virtual ir_visitor_status visit(ir_dereference_variable *);
> @@ -71,8 +63,7 @@ public:
>
>      ir_variable_refcount_entry *get_variable_entry(ir_variable *var);
>
> -   /* List of ir_variable_refcount_entry */
> -   exec_list variable_list;
> +   struct hash_table *ht;
>
>      void *mem_ctx;
>   };
> diff --git a/src/glsl/opt_dead_code.cpp b/src/glsl/opt_dead_code.cpp
> index de8475f..5351368 100644
> --- a/src/glsl/opt_dead_code.cpp
> +++ b/src/glsl/opt_dead_code.cpp
> @@ -31,6 +31,7 @@
>   #include "ir_visitor.h"
>   #include "ir_variable_refcount.h"
>   #include "glsl_types.h"
> +#include "main/hash_table.h"
>
>   static bool debug = false;
>
> @@ -49,8 +50,11 @@ do_dead_code(exec_list *instructions, bool uniform_locations_assigned)
>
>      v.run(instructions);
>
> -   foreach_iter(exec_list_iterator, iter, v.variable_list) {
> -      ir_variable_refcount_entry *entry = (ir_variable_refcount_entry *)iter.get();
> +   struct hash_entry *e;
> +   for (e = _mesa_hash_table_next_entry(v.ht, NULL);
> +	e != NULL;
> +	e = _mesa_hash_table_next_entry(v.ht, e)) {
> +      ir_variable_refcount_entry *entry = (ir_variable_refcount_entry *)e->data;
>
>         /* Since each assignment is a reference, the refereneced count must be
>          * greater than or equal to the assignment count.  If they are equal,
>