summaryrefslogtreecommitdiffstats
path: root/src/compiler/nir
diff options
context:
space:
mode:
authorJason Ekstrand <[email protected]>2019-05-04 18:02:50 -0500
committerJason Ekstrand <[email protected]>2019-05-13 14:43:47 +0000
commit712f99934cda7e4bf3f25b8b1f72218ed8113eda (patch)
tree8960a2fcc47a3c4ef711a67cdf3314011e419c45 /src/compiler/nir
parentbab08c791de323f021bcedbd93aee04343637482 (diff)
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]>
Diffstat (limited to 'src/compiler/nir')
-rw-r--r--src/compiler/nir/nir_validate.c128
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);