Push it! On Mar 9, 2015 7:03 PM, "Connor Abbott" <cwabbo...@gmail.com> wrote:
> Reviewed-by: Connor Abbott <cwabbo...@gmail.com> > > 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 <kenn...@whitecape.org> > 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 <jason.ekstr...@intel.com> > > Signed-off-by: Kenneth Graunke <kenn...@whitecape.org> > > --- > > 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 > > mesa-dev@lists.freedesktop.org > > http://lists.freedesktop.org/mailman/listinfo/mesa-dev > _______________________________________________ > mesa-dev mailing list > mesa-dev@lists.freedesktop.org > http://lists.freedesktop.org/mailman/listinfo/mesa-dev >
_______________________________________________ mesa-dev mailing list mesa-dev@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/mesa-dev