[Mesa-dev] [PATCH 2/2] nir: Fix non-determinism in nir_lower_vars_to_ssa().
Connor Abbott
cwabbott0 at gmail.com
Mon Mar 9 19:03:19 PDT 2015
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
More information about the mesa-dev
mailing list