Push it! <div class="gmail_quote">On Mar 9, 2015 7:03 PM, "Connor Abbott" <<a href="mailto:cwabbott0@gmail.com">cwabbott0@gmail.com</a>> wrote: <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Reviewed-by: Connor Abbott <<a href="mailto:cwabbott0@gmail.com">cwabbott0@gmail.com</a>> I was in the middle of rewriting this pass for making derefs instructions, which hasn't been going nearly as nicely as I would like (ugh...), so if it pans out then I'll have to think about it a little more to make sure the new version is deterministic too. On Mon, Mar 9, 2015 at 9:36 PM, Kenneth Graunke <<a href="mailto:kenneth@whitecape.org">kenneth@whitecape.org</a>> wrote: > Previously, we stored derefs in a hash table, using the malloc'd pointer > as the key. Then, we walked through the hash table and generated code, > based on the order of the hash table's elements. > > Memory addresses returned by malloc are pretty much random, which meant > that the hash was random, and the hash table's elements would be walked > in some random order. This led to successive compiles of the same > shader using different variable names and slightly different orderings > of phi-nodes. Code could not be diff'd, and the final assembly would > sometimes change slightly too. > > It turns out the only point of the hash table was to avoid inserting > the same node multiple times for different dereferences. We never > actually searched the hash table! This patch uses an intrusive > linked list instead. Since exec_list uses head and tail sentinels, > checking prev or next against NULL will tell us whether the node is > already in the list. > > Pair programming with Jason Ekstrand. > > Signed-off-by: Jason Ekstrand <<a href="mailto:jason.ekstrand@intel.com">jason.ekstrand@intel.com</a>> > Signed-off-by: Kenneth Graunke <<a href="mailto:kenneth@whitecape.org">kenneth@whitecape.org</a>> > --- > src/glsl/nir/nir_lower_vars_to_ssa.c | 123 ++++++++--------------------------- > 1 file changed, 26 insertions(+), 97 deletions(-) > > diff --git a/src/glsl/nir/nir_lower_vars_to_ssa.c b/src/glsl/nir/nir_lower_vars_to_ssa.c > index 9e9a418..86e6ab4 100644 > --- a/src/glsl/nir/nir_lower_vars_to_ssa.c > +++ b/src/glsl/nir/nir_lower_vars_to_ssa.c > @@ -35,6 +35,13 @@ struct deref_node { > > bool lower_to_ssa; > > + /* Only valid for things that end up in the direct list. > + * Note that multiple nir_deref_vars may correspond to this node, but they > + * will all be equivalent, so any is as good as the other. > + */ > + nir_deref_var *deref; > + struct exec_node direct_derefs_link; > + > struct set *loads; > struct set *stores; > struct set *copies; > @@ -69,7 +76,7 @@ struct lower_variables_state { > * wildcards and no indirects, these are precisely the derefs that we > * can actually consider lowering. > */ > - struct hash_table *direct_deref_nodes; > + struct exec_list direct_deref_nodes; > > /* Controls whether get_deref_node will add variables to the > * direct_deref_nodes table. This is turned on when we are initially > @@ -83,88 +90,6 @@ struct lower_variables_state { > struct hash_table *phi_table; > }; > > -/* The following two functions implement a hash and equality check for > - * variable dreferences. When the hash or equality function encounters an > - * array, all indirects are treated as equal and are never equal to a > - * direct dereference or a wildcard. > - */ > -static uint32_t > -hash_deref(const void *void_deref) > -{ > - uint32_t hash = _mesa_fnv32_1a_offset_bias; > - > - const nir_deref_var *deref_var = void_deref; > - hash = _mesa_fnv32_1a_accumulate(hash, deref_var->var); > - > - for (const nir_deref *deref = deref_var->deref.child; > - deref; deref = deref->child) { > - switch (deref->deref_type) { > - case nir_deref_type_array: { > - nir_deref_array *deref_array = nir_deref_as_array(deref); > - > - hash = _mesa_fnv32_1a_accumulate(hash, deref_array->deref_array_type); > - > - if (deref_array->deref_array_type == nir_deref_array_type_direct) > - hash = _mesa_fnv32_1a_accumulate(hash, deref_array->base_offset); > - break; > - } > - case nir_deref_type_struct: { > - nir_deref_struct *deref_struct = nir_deref_as_struct(deref); > - hash = _mesa_fnv32_1a_accumulate(hash, deref_struct->index); > - break; > - } > - default: > - assert("Invalid deref chain"); > - } > - } > - > - return hash; > -} > - > -static bool > -derefs_equal(const void *void_a, const void *void_b) > -{ > - const nir_deref_var *a_var = void_a; > - const nir_deref_var *b_var = void_b; > - > - if (a_var->var != b_var->var) > - return false; > - > - for (const nir_deref *a = a_var->deref.child, *b = b_var->deref.child; > - a != NULL; a = a->child, b = b->child) { > - if (a->deref_type != b->deref_type) > - return false; > - > - switch (a->deref_type) { > - case nir_deref_type_array: { > - nir_deref_array *a_arr = nir_deref_as_array(a); > - nir_deref_array *b_arr = nir_deref_as_array(b); > - > - if (a_arr->deref_array_type != b_arr->deref_array_type) > - return false; > - > - if (a_arr->deref_array_type == nir_deref_array_type_direct && > - a_arr->base_offset != b_arr->base_offset) > - return false; > - break; > - } > - case nir_deref_type_struct: > - if (nir_deref_as_struct(a)->index != nir_deref_as_struct(b)->index) > - return false; > - break; > - default: > - assert("Invalid deref chain"); > - return false; > - } > - > - assert((a->child == NULL) == (b->child == NULL)); > - if((a->child == NULL) != (b->child == NULL)) > - return false; > - } > - > - return true; > -} > - > static int > type_get_length(const struct glsl_type *type) > { > @@ -195,6 +120,8 @@ deref_node_create(struct deref_node *parent, > struct deref_node *node = rzalloc_size(mem_ctx, size); > node->type = type; > node->parent = parent; > + node->deref = NULL; > + exec_node_init(&node->direct_derefs_link); > > return node; > } > @@ -297,8 +224,14 @@ get_deref_node(nir_deref_var *deref, struct lower_variables_state *state) > > assert(node); > > - if (is_direct && state->add_to_direct_deref_nodes) > - _mesa_hash_table_insert(state->direct_deref_nodes, deref, node); > + /* Only insert if it isn't already in the list. */ > + if (is_direct && state->add_to_direct_deref_nodes && > + node->direct_derefs_link.next == NULL) { > + node->deref = deref; > + assert(deref->var != NULL); > + exec_list_push_tail(&state->direct_deref_nodes, > + &node->direct_derefs_link); > + } > > return node; > } > @@ -917,10 +850,8 @@ insert_phi_nodes(struct lower_variables_state *state) > unsigned w_start, w_end; > unsigned iter_count = 0; > > - struct hash_entry *deref_entry; > - hash_table_foreach(state->direct_deref_nodes, deref_entry) { > - struct deref_node *node = deref_entry->data; > - > + foreach_list_typed(struct deref_node, node, direct_derefs_link, > + &state->direct_deref_nodes) { > if (node->stores == NULL) > continue; > > @@ -1014,8 +945,7 @@ nir_lower_vars_to_ssa_impl(nir_function_impl *impl) > state.deref_var_nodes = _mesa_hash_table_create(state.dead_ctx, > _mesa_hash_pointer, > _mesa_key_pointer_equal); > - state.direct_deref_nodes = _mesa_hash_table_create(state.dead_ctx, > - hash_deref, derefs_equal); > + exec_list_make_empty(&state.direct_deref_nodes); > state.phi_table = _mesa_hash_table_create(state.dead_ctx, > _mesa_hash_pointer, > _mesa_key_pointer_equal); > @@ -1035,18 +965,17 @@ nir_lower_vars_to_ssa_impl(nir_function_impl *impl) > /* We're about to iterate through direct_deref_nodes. Don't modify it. */ > state.add_to_direct_deref_nodes = false; > > - struct hash_entry *entry; > - hash_table_foreach(state.direct_deref_nodes, entry) { > - nir_deref_var *deref = (void *)entry->key; > - struct deref_node *node = entry->data; > + foreach_list_typed_safe(struct deref_node, node, direct_derefs_link, > + &state.direct_deref_nodes) { > + nir_deref_var *deref = node->deref; > > if (deref->var->data.mode != nir_var_local) { > - _mesa_hash_table_remove(state.direct_deref_nodes, entry); > + exec_node_remove(&node->direct_derefs_link); > continue; > } > > if (deref_may_be_aliased(deref, &state)) { > - _mesa_hash_table_remove(state.direct_deref_nodes, entry); > + exec_node_remove(&node->direct_derefs_link); > continue; > } > > -- > 2.2.2 > > _______________________________________________ > mesa-dev mailing list > <a href="mailto:mesa-dev@lists.freedesktop.org">mesa-dev@lists.freedesktop.org</a> > <a href="http://lists.freedesktop.org/mailman/listinfo/mesa-dev" target="_blank">http://lists.freedesktop.org/mailman/listinfo/mesa-dev</a> _______________________________________________ mesa-dev mailing list <a href="mailto:mesa-dev@lists.freedesktop.org">mesa-dev@lists.freedesktop.org</a> <a href="http://lists.freedesktop.org/mailman/listinfo/mesa-dev" target="_blank">http://lists.freedesktop.org/mailman/listinfo/mesa-dev</a> </blockquote></div>