nir/nir: Use a linked list instead of a hash set for use/def sets

This commit switches us from the current setup of using hash sets for
use/def sets to using linked lists.  Doing so should save us quite a bit of
memory because we aren't carrying around 3 hash sets per register and 2 per
SSA value.  It should also save us CPU time because adding/removing things
from use/def sets is 4 pointer manipulations instead of a hash lookup.

Running shader-db 50 times with USE_NIR=0, NIR, and NIR + use/def lists:

   GLSL IR Only:        586.4 +/- 1.653833
   NIR with hash sets:  675.4 +/- 2.502108
   NIR + use/def lists: 641.2 +/- 1.557043

I also ran a memory usage experiment with Ken's patch to delete GLSL IR and
keep NIR.  This patch cuts an aditional 42.9 MiB of ralloc'd memory over
and above what we gained by deleting the GLSL IR on the same dota trace.

On the code complexity side of things, some things are now much easier and
others are a bit harder.  One of the operations we perform constantly in
optimization passes is to replace one source with another.  Due to the fact
that an instruction can use the same SSA value multiple times, we had to
iterate through the sources of the instruction and determine if the use we
were replacing was the only one before removing it from the set of uses.
With this patch, uses are per-source not per-instruction so we can just
remove it safely.  On the other hand, trying to iterate over all of the
instructions that use a given value is more difficult.  Fortunately, the
two places we do that are the ffma peephole where it doesn't matter and GCM
where we already gracefully handle duplicates visits to an instruction.

Another aspect here is that using linked lists in this way can be tricky to
get right.  With sets, things were quite forgiving and the worst that
happened if you didn't properly remove a use was that it would get caught
in the validator.  With linked lists, it can lead to linked list corruption
which can be harder to track.  However, we do just as much validation of
the linked lists as we did of the sets so the validator should still catch
these problems.  While working on this series, the vast majority of the
bugs I had to fix were caught by assertions.  I don't think the lists are
going to be that much worse than the sets.

Reviewed-by: Connor Abbott <[email protected]>

1 files changed, 85 insertions, 151 deletions

diff --git a/src/glsl/nir/nir.c b/src/glsl/nir/nir.c
index b8f5dd491a4..f03e80a4e0e 100644
--- a/src/glsl/nir/nir.c
+++ b/src/glsl/nir/nir.c
@@ -58,12 +58,9 @@ reg_create(void *mem_ctx, struct exec_list *list)
    nir_register *reg = ralloc(mem_ctx, nir_register);
 
    reg->parent_instr = NULL;
-   reg->uses = _mesa_set_create(reg, _mesa_hash_pointer,
-                                _mesa_key_pointer_equal);
-   reg->defs = _mesa_set_create(reg, _mesa_hash_pointer,
-                                _mesa_key_pointer_equal);
-   reg->if_uses = _mesa_set_create(reg, _mesa_hash_pointer,
-                                   _mesa_key_pointer_equal);
+   list_inithead(&reg->uses);
+   list_inithead(&reg->defs);
+   list_inithead(&reg->if_uses);
 
    reg->num_components = 0;
    reg->num_array_elems = 0;
@@ -1070,11 +1067,14 @@ update_if_uses(nir_cf_node *node)
 
    nir_if *if_stmt = nir_cf_node_as_if(node);
 
-   struct set *if_uses_set = if_stmt->condition.is_ssa ?
-                             if_stmt->condition.ssa->if_uses :
-                             if_stmt->condition.reg.reg->uses;
-
-   _mesa_set_add(if_uses_set, if_stmt);
+   if_stmt->condition.parent_if = if_stmt;
+   if (if_stmt->condition.is_ssa) {
+      list_addtail(&if_stmt->condition.use_link,
+                   &if_stmt->condition.ssa->if_uses);
+   } else {
+      list_addtail(&if_stmt->condition.use_link,
+                   &if_stmt->condition.reg.reg->if_uses);
+   }
 }
 
 void
@@ -1227,16 +1227,7 @@ cleanup_cf_node(nir_cf_node *node)
       foreach_list_typed(nir_cf_node, child, node, &if_stmt->else_list)
          cleanup_cf_node(child);
 
-      struct set *if_uses;
-      if (if_stmt->condition.is_ssa) {
-         if_uses = if_stmt->condition.ssa->if_uses;
-      } else {
-         if_uses = if_stmt->condition.reg.reg->if_uses;
-      }
-
-      struct set_entry *entry = _mesa_set_search(if_uses, if_stmt);
-      assert(entry);
-      _mesa_set_remove(if_uses, entry);
+      list_del(&if_stmt->condition.use_link);
       break;
    }
 
@@ -1293,9 +1284,9 @@ add_use_cb(nir_src *src, void *state)
 {
    nir_instr *instr = state;
 
-   struct set *uses_set = src->is_ssa ? src->ssa->uses : src->reg.reg->uses;
-
-   _mesa_set_add(uses_set, instr);
+   src->parent_instr = instr;
+   list_addtail(&src->use_link,
+                src->is_ssa ? &src->ssa->uses : &src->reg.reg->uses);
 
    return true;
 }
@@ -1320,8 +1311,10 @@ add_reg_def_cb(nir_dest *dest, void *state)
 {
    nir_instr *instr = state;
 
-   if (!dest->is_ssa)
-      _mesa_set_add(dest->reg.reg->defs, instr);
+   if (!dest->is_ssa) {
+      dest->reg.parent_instr = instr;
+      list_addtail(&dest->reg.def_link, &dest->reg.reg->defs);
+   }
 
    return true;
 }
@@ -1436,13 +1429,7 @@ nir_instr_insert_after_cf_list(struct exec_list *list, nir_instr *after)
 static bool
 remove_use_cb(nir_src *src, void *state)
 {
-   nir_instr *instr = state;
-
-   struct set *uses_set = src->is_ssa ? src->ssa->uses : src->reg.reg->uses;
-
-   struct set_entry *entry = _mesa_set_search(uses_set, instr);
-   if (entry)
-      _mesa_set_remove(uses_set, entry);
+   list_del(&src->use_link);
 
    return true;
 }
@@ -1450,16 +1437,8 @@ remove_use_cb(nir_src *src, void *state)
 static bool
 remove_def_cb(nir_dest *dest, void *state)
 {
-   nir_instr *instr = state;
-
-   if (dest->is_ssa)
-      return true;
-
-   nir_register *reg = dest->reg.reg;
-
-   struct set_entry *entry = _mesa_set_search(reg->defs, instr);
-   if (entry)
-      _mesa_set_remove(reg->defs, entry);
+   if (!dest->is_ssa)
+      list_del(&dest->reg.def_link);
 
    return true;
 }
@@ -1834,86 +1813,77 @@ nir_srcs_equal(nir_src src1, nir_src src2)
 }
 
 static bool
-src_does_not_use_def(nir_src *src, void *void_def)
+src_is_valid(const nir_src *src)
 {
-   nir_ssa_def *def = void_def;
-
-   if (src->is_ssa) {
-      return src->ssa != def;
-   } else {
-      return true;
-   }
+   return src->is_ssa ? (src->ssa != NULL) : (src->reg.reg != NULL);
 }
 
-static bool
-src_does_not_use_reg(nir_src *src, void *void_reg)
+static void
+src_remove_all_uses(nir_src *src)
 {
-   nir_register *reg = void_reg;
+   for (; src; src = src->is_ssa ? NULL : src->reg.indirect) {
+      if (!src_is_valid(src))
+         continue;
 
-   if (src->is_ssa) {
-      return true;
-   } else {
-      return src->reg.reg != reg;
+      list_del(&src->use_link);
+   }
+}
+
+static void
+src_add_all_uses(nir_src *src, nir_instr *parent_instr, nir_if *parent_if)
+{
+   for (; src; src = src->is_ssa ? NULL : src->reg.indirect) {
+      if (!src_is_valid(src))
+         continue;
+
+      if (parent_instr) {
+         src->parent_instr = parent_instr;
+         if (src->is_ssa)
+            list_addtail(&src->use_link, &src->ssa->uses);
+         else
+            list_addtail(&src->use_link, &src->reg.reg->uses);
+      } else {
+         assert(parent_if);
+         src->parent_if = parent_if;
+         if (src->is_ssa)
+            list_addtail(&src->use_link, &src->ssa->if_uses);
+         else
+            list_addtail(&src->use_link, &src->reg.reg->if_uses);
+      }
    }
 }
 
 void
 nir_instr_rewrite_src(nir_instr *instr, nir_src *src, nir_src new_src)
 {
-   nir_src old_src = *src;
+   assert(!src_is_valid(src) || src->parent_instr == instr);
+
+   src_remove_all_uses(src);
    *src = new_src;
+   src_add_all_uses(src, instr, NULL);
+}
 
-   for (nir_src *iter_src = &old_src; iter_src;
-        iter_src = iter_src->is_ssa ? NULL : iter_src->reg.indirect) {
-      if (iter_src->is_ssa) {
-         nir_ssa_def *ssa = iter_src->ssa;
-         if (ssa && nir_foreach_src(instr, src_does_not_use_def, ssa)) {
-            struct set_entry *entry = _mesa_set_search(ssa->uses, instr);
-            assert(entry);
-            _mesa_set_remove(ssa->uses, entry);
-         }
-      } else {
-         nir_register *reg = iter_src->reg.reg;
-         if (reg && nir_foreach_src(instr, src_does_not_use_reg, reg)) {
-            struct set_entry *entry = _mesa_set_search(reg->uses, instr);
-            assert(entry);
-            _mesa_set_remove(reg->uses, entry);
-         }
-      }
-   }
+void
+nir_instr_move_src(nir_instr *dest_instr, nir_src *dest, nir_src *src)
+{
+   assert(!src_is_valid(dest) || dest->parent_instr == dest_instr);
 
-   for (nir_src *iter_src = &new_src; iter_src;
-        iter_src = iter_src->is_ssa ? NULL : iter_src->reg.indirect) {
-      if (iter_src->is_ssa) {
-         if (iter_src->ssa)
-            _mesa_set_add(iter_src->ssa->uses, instr);
-      } else {
-         if (iter_src->reg.reg)
-            _mesa_set_add(iter_src->reg.reg->uses, instr);
-      }
-   }
+   src_remove_all_uses(dest);
+   src_remove_all_uses(src);
+   *dest = *src;
+   *src = NIR_SRC_INIT;
+   src_add_all_uses(dest, dest_instr, NULL);
 }
 
 void
 nir_if_rewrite_condition(nir_if *if_stmt, nir_src new_src)
 {
-   for (nir_src *src = &if_stmt->condition; src;
-        src = src->is_ssa ? NULL : src->reg.indirect) {
-      struct set *uses = src->is_ssa ? src->ssa->if_uses
-                                     : src->reg.reg->if_uses;
-      struct set_entry *entry = _mesa_set_search(uses, if_stmt);
-      assert(entry);
-      _mesa_set_remove(uses, entry);
-   }
-
-   if_stmt->condition = new_src;
+   nir_src *src = &if_stmt->condition;
+   assert(!src_is_valid(src) || src->parent_if == if_stmt);
 
-   for (nir_src *src = &if_stmt->condition; src;
-        src = src->is_ssa ? NULL : src->reg.indirect) {
-      struct set *uses = src->is_ssa ? src->ssa->if_uses
-                                     : src->reg.reg->if_uses;
-      _mesa_set_add(uses, if_stmt);
-   }
+   src_remove_all_uses(src);
+   *src = new_src;
+   src_add_all_uses(src, NULL, if_stmt);
 }
 
 void
@@ -1922,10 +1892,8 @@ nir_ssa_def_init(nir_instr *instr, nir_ssa_def *def,
 {
    def->name = name;
    def->parent_instr = instr;
-   def->uses = _mesa_set_create(instr, _mesa_hash_pointer,
-                                _mesa_key_pointer_equal);
-   def->if_uses = _mesa_set_create(instr, _mesa_hash_pointer,
-                                   _mesa_key_pointer_equal);
+   list_inithead(&def->uses);
+   list_inithead(&def->if_uses);
    def->num_components = num_components;
 
    if (instr->block) {
@@ -1946,57 +1914,23 @@ nir_ssa_dest_init(nir_instr *instr, nir_dest *dest,
    nir_ssa_def_init(instr, &dest->ssa, num_components, name);
 }
 
-struct ssa_def_rewrite_state {
-   void *mem_ctx;
-   nir_ssa_def *old;
-   nir_src new_src;
-};
-
-static bool
-ssa_def_rewrite_uses_src(nir_src *src, void *void_state)
-{
-   struct ssa_def_rewrite_state *state = void_state;
-
-   if (src->is_ssa && src->ssa == state->old)
-      nir_src_copy(src, &state->new_src, state->mem_ctx);
-
-   return true;
-}
-
 void
 nir_ssa_def_rewrite_uses(nir_ssa_def *def, nir_src new_src, void *mem_ctx)
 {
-   struct ssa_def_rewrite_state state;
-   state.mem_ctx = mem_ctx;
-   state.old = def;
-   state.new_src = new_src;
-
    assert(!new_src.is_ssa || def != new_src.ssa);
 
-   struct set *new_uses, *new_if_uses;
-   if (new_src.is_ssa) {
-      new_uses = new_src.ssa->uses;
-      new_if_uses = new_src.ssa->if_uses;
-   } else {
-      new_uses = new_src.reg.reg->uses;
-      new_if_uses = new_src.reg.reg->if_uses;
-   }
-
-   struct set_entry *entry;
-   set_foreach(def->uses, entry) {
-      nir_instr *instr = (nir_instr *)entry->key;
-
-      _mesa_set_remove(def->uses, entry);
-      nir_foreach_src(instr, ssa_def_rewrite_uses_src, &state);
-      _mesa_set_add(new_uses, instr);
+   nir_foreach_use_safe(def, use_src) {
+      nir_instr *src_parent_instr = use_src->parent_instr;
+      list_del(&use_src->use_link);
+      nir_src_copy(use_src, &new_src, mem_ctx);
+      src_add_all_uses(use_src, src_parent_instr, NULL);
    }
 
-   set_foreach(def->if_uses, entry) {
-      nir_if *if_use = (nir_if *)entry->key;
-
-      _mesa_set_remove(def->if_uses, entry);
-      nir_src_copy(&if_use->condition, &new_src, mem_ctx);
-      _mesa_set_add(new_if_uses, if_use);
+   nir_foreach_if_use_safe(def, use_src) {
+      nir_if *src_parent_if = use_src->parent_if;
+      list_del(&use_src->use_link);
+      nir_src_copy(use_src, &new_src, mem_ctx);
+      src_add_all_uses(use_src, NULL, src_parent_if);
    }
 }