[Mesa-dev] [PATCH 2/2] nir: Fix non-determinism in nir_lower_vars_to_ssa().
Jason Ekstrand
jason at jlekstrand.net
Mon Mar 9 19:04:12 PDT 2015
Push it!
On Mar 9, 2015 7:03 PM, "Connor Abbott" <cwabbott0 at gmail.com> wrote:
> Reviewed-by: Connor Abbott <cwabbott0 at 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 <kenneth at 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.ekstrand at intel.com>
> > Signed-off-by: Kenneth Graunke <kenneth at 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 at lists.freedesktop.org
> > http://lists.freedesktop.org/mailman/listinfo/mesa-dev
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/mesa-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freedesktop.org/archives/mesa-dev/attachments/20150309/f517f150/attachment.html>
More information about the mesa-dev
mailing list