1 files changed, 50 insertions, 78 deletions

diff --git a/src/compiler/nir/nir_validate.c b/src/compiler/nir/nir_validate.c
index 3b3244b317e..8278176564f 100644
--- a/src/compiler/nir/nir_validate.c
+++ b/src/compiler/nir/nir_validate.c
@@ -52,15 +52,6 @@ typedef struct {
 } reg_validate_state;
 
 typedef struct {
-   /*
-    * equivalent to the uses in nir_ssa_def, but built up by the validator.
-    * At the end, we verify that the sets have the same entries.
-    */
-   struct set *uses, *if_uses;
-   nir_function_impl *where_defined;
-} ssa_def_validate_state;
-
-typedef struct {
    void *mem_ctx;
 
    /* map of register -> validation state (struct above) */
@@ -90,8 +81,8 @@ typedef struct {
    /* the current function implementation being validated */
    nir_function_impl *impl;
 
-   /* map of SSA value -> function implementation where it is defined */
-   struct hash_table *ssa_defs;
+   /* Set of seen SSA sources */
+   struct set *ssa_srcs;
 
    /* bitset of ssa definitions we have found; used to check uniqueness */
    BITSET_WORD *ssa_defs_found;
@@ -174,30 +165,29 @@ validate_reg_src(nir_src *src, validate_state *state,
    }
 }
 
+#define SET_PTR_BIT(ptr, bit) \
+   (void *)(((uintptr_t)(ptr)) | (((uintptr_t)1) << bit))
+
 static void
 validate_ssa_src(nir_src *src, validate_state *state,
                  unsigned bit_sizes, unsigned num_components)
 {
    validate_assert(state, src->ssa != NULL);
 
-   struct hash_entry *entry = _mesa_hash_table_search(state->ssa_defs, src->ssa);
-
-   validate_assert(state, entry);
-
-   if (!entry)
-      return;
-
-   ssa_def_validate_state *def_state = (ssa_def_validate_state *)entry->data;
-
-   validate_assert(state, def_state->where_defined == state->impl &&
-          "using an SSA value defined in a different function");
-
+   /* As we walk SSA defs, we add every use to this set.  We need to make sure
+    * our use is seen in a use list.
+    */
+   struct set_entry *entry;
    if (state->instr) {
-      _mesa_set_add(def_state->uses, src);
+      entry = _mesa_set_search(state->ssa_srcs, src);
    } else {
-      validate_assert(state, state->if_stmt);
-      _mesa_set_add(def_state->if_uses, src);
+      entry = _mesa_set_search(state->ssa_srcs, SET_PTR_BIT(src, 0));
    }
+   validate_assert(state, entry);
+
+   /* This will let us prove that we've seen all the sources */
+   if (entry)
+      _mesa_set_remove(state->ssa_srcs, entry);
 
    if (bit_sizes)
       validate_assert(state, src->ssa->bit_size & bit_sizes);
@@ -288,14 +278,25 @@ validate_ssa_def(nir_ssa_def *def, validate_state *state)
                           (def->num_components == 16));
 
    list_validate(&def->uses);
-   list_validate(&def->if_uses);
+   nir_foreach_use(src, def) {
+      validate_assert(state, src->is_ssa);
+      validate_assert(state, src->ssa == def);
+      bool already_seen = false;
+      _mesa_set_search_and_add(state->ssa_srcs, src, &already_seen);
+      /* A nir_src should only appear once and only in one SSA def use list */
+      validate_assert(state, !already_seen);
+   }
 
-   ssa_def_validate_state *def_state = ralloc(state->ssa_defs,
-                                              ssa_def_validate_state);
-   def_state->where_defined = state->impl;
-   def_state->uses = _mesa_pointer_set_create(def_state);
-   def_state->if_uses = _mesa_pointer_set_create(def_state);
-   _mesa_hash_table_insert(state->ssa_defs, def, def_state);
+   list_validate(&def->if_uses);
+   nir_foreach_if_use(src, def) {
+      validate_assert(state, src->is_ssa);
+      validate_assert(state, src->ssa == def);
+      bool already_seen = false;
+      _mesa_set_search_and_add(state->ssa_srcs, SET_PTR_BIT(src, 0),
+                               &already_seen);
+      /* A nir_src should only appear once and only in one SSA def use list */
+      validate_assert(state, !already_seen);
+   }
 }
 
 static void
@@ -1078,50 +1079,18 @@ validate_var_decl(nir_variable *var, bool is_global, validate_state *state)
    state->var = NULL;
 }
 
-static bool
-postvalidate_ssa_def(nir_ssa_def *def, void *void_state)
-{
-   validate_state *state = void_state;
-
-   struct hash_entry *entry = _mesa_hash_table_search(state->ssa_defs, def);
-
-   assume(entry);
-   ssa_def_validate_state *def_state = (ssa_def_validate_state *)entry->data;
-
-   nir_foreach_use(src, def) {
-      struct set_entry *entry = _mesa_set_search(def_state->uses, src);
-      validate_assert(state, entry);
-      _mesa_set_remove(def_state->uses, entry);
-   }
-
-   if (def_state->uses->entries != 0) {
-      printf("extra entries in SSA def uses:\n");
-      set_foreach(def_state->uses, entry)
-         printf("%p\n", entry->key);
-
-      abort();
-   }
-
-   nir_foreach_if_use(src, def) {
-      struct set_entry *entry = _mesa_set_search(def_state->if_uses, src);
-      validate_assert(state, entry);
-      _mesa_set_remove(def_state->if_uses, entry);
-   }
-
-   if (def_state->if_uses->entries != 0) {
-      printf("extra entries in SSA def uses:\n");
-      set_foreach(def_state->if_uses, entry)
-         printf("%p\n", entry->key);
-
-      abort();
-   }
-
-   return true;
-}
-
 static void
 validate_function_impl(nir_function_impl *impl, validate_state *state)
 {
+   /* Resize the ssa_srcs set.  It's likely that the size of this set will
+    * never actually hit the number of SSA defs because we remove sources from
+    * the set as we visit them.  (It could actually be much larger because
+    * each SSA def can be used more than once.)  However, growing it now costs
+    * us very little (the extra memory is already dwarfed by the SSA defs
+    * themselves) and makes collisions much less likely.
+    */
+   _mesa_set_resize(state->ssa_srcs, impl->ssa_alloc);
+
    validate_assert(state, impl->function->impl == impl);
    validate_assert(state, impl->cf_node.parent == NULL);
 
@@ -1159,9 +1128,12 @@ validate_function_impl(nir_function_impl *impl, validate_state *state)
       postvalidate_reg_decl(reg, state);
    }
 
-   nir_foreach_block(block, impl) {
-      nir_foreach_instr(instr, block)
-         nir_foreach_ssa_def(instr, postvalidate_ssa_def, state);
+   if (state->ssa_srcs->entries != 0) {
+      printf("extra dangling SSA sources:\n");
+      set_foreach(state->ssa_srcs, entry)
+         printf("%p\n", entry->key);
+
+      abort();
    }
 }
 
@@ -1179,7 +1151,7 @@ init_validate_state(validate_state *state)
 {
    state->mem_ctx = ralloc_context(NULL);
    state->regs = _mesa_pointer_hash_table_create(state->mem_ctx);
-   state->ssa_defs = _mesa_pointer_hash_table_create(state->mem_ctx);
+   state->ssa_srcs = _mesa_pointer_set_create(state->mem_ctx);
    state->ssa_defs_found = NULL;
    state->regs_found = NULL;
    state->var_defs = _mesa_pointer_hash_table_create(state->mem_ctx);