nir/validate: Use a single set for SSA def validation

The current SSA def validation we do in nir_validate validates three
things:

 1. That each SSA def is only ever used in the function in which it is
    defined.

 2. That an nir_src exists in an SSA def's use list if and only if it
    points to that SSA def.

 3. That each nir_src is in the correct use list (uses or if_uses) based
    on whether it's an if condition or not.

The way we were doing this before was that we had a hash table which
provided a map from SSA def to a small ssa_def_validate_state data
structure which contained a pointer to the nir_function_impl and two
hash sets, one for each use list.  This meant piles of allocation and
creating of little hash sets.  It also meant one hash lookup for each
SSA def plus one per use as well as two per src (because we have to look
up the ssa_def_validate_state and then look up the use.)  It also
involved a second walk over the instructions as a post-validate step.

This commit changes us to use a single low-collision hash set of SSA
sources for all of this by being a bit more clever.  We accomplish the
objectives above as follows:

 1. The list is clear when we start validating a function.  If the
    nir_src references an SSA def which is defined in a different
    function, it simply won't be in the set.

 2. When validating the SSA defs, we walk the uses and verify that they
    have is_ssa set and that the SSA def points to the SSA def we're
    validating.  This catches the case of a nir_src being in the wrong
    list.  We then put the nir_src in the set and, when we validate the
    nir_src, we assert that it's in the set.  This takes care of any
    cases where a nir_src isn't in the use list.  After checking that
    the nir_src is in the set, we remove it from the set and, at the end
    of nir_function_impl validation, we assert that the set is empty.
    This takes care of any cases where a nir_src is in a use list but
    the instruction is no longer in the shader.

 3. When we put a nir_src in the set, we set the bottom bit of the
    pointer to 1 if it's the condition of an if.  This lets us detect
    whether or not a nir_src is in the right list.

When running shader-db with an optimized debug build of mesa on my
laptop, I get the following shader-db CPU times:

   With NIR_VALIDATE=0       3033.34 seconds
   Before this commit       20224.83 seconds
   After this commit         6255.50 seconds

Assuming shader-db is a representative sampling of GLSL shaders, this
means that making this change yields an 81% reduction in the time spent
in nir_validate.  It still isn't cheap but enabling validation now only
increases compile times by 2x instead of 6.6x.

Reviewed-by: Eric Anholt <[email protected]>
Reviewed-by: Thomas Helland <[email protected]>

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);