Mesa (main): nir: Better document the Boissinot algorithm in nir_from_ssa()

[GitLab Mirror]

Module: Mesa
Branch: main
Commit: 0ee322acdb633a0935f542494f7113d86df3f78a
URL:    http://cgit.freedesktop.org/mesa/mesa/commit/?id=0ee322acdb633a0935f542494f7113d86df3f78a

Author: Jason Ekstrand <jason.ekstrand at intel.com>
Date:   Mon Feb  1 16:10:19 2021 -0600

nir: Better document the Boissinot algorithm in nir_from_ssa()

Reviewed-by: Yevhenii Kolesnikov <yevhenii.kolesnikov at globallogic.com>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/8815>

---

 src/compiler/nir/nir_from_ssa.c | 43 +++++++++++++++++++++++++++++++++++++----
 1 file changed, 39 insertions(+), 4 deletions(-)

diff --git a/src/compiler/nir/nir_from_ssa.c b/src/compiler/nir/nir_from_ssa.c
index b624e457e4b..6bfeed23b39 100644
--- a/src/compiler/nir/nir_from_ssa.c
+++ b/src/compiler/nir/nir_from_ssa.c
@@ -105,9 +105,9 @@ ssa_def_dominates(nir_ssa_def *a, nir_ssa_def *b)
  * Each SSA definition is associated with a merge_node and the association
  * is represented by a combination of a hash table and the "def" parameter
  * in the merge_node structure.  The merge_set stores a linked list of
- * merge_nodes in dominance order of the ssa definitions.  (Since the
- * liveness analysis pass indexes the SSA values in dominance order for us,
- * this is an easy thing to keep up.)  It is assumed that no pair of the
+ * merge_nodes, ordered by a pre-order DFS walk of the dominance tree.  (Since
+ * the liveness analysis pass indexes the SSA values in dominance order for
+ * us, this is an easy thing to keep up.)  It is assumed that no pair of the
  * nodes in a given set interfere.  Merging two sets or checking for
  * interference can be done in a single linear-time merge-sort walk of the
  * two lists of nodes.
@@ -185,7 +185,11 @@ merge_nodes_interfere(merge_node *a, merge_node *b)
    return nir_ssa_defs_interfere(a->def, b->def);
 }
 
-/* Merges b into a */
+/* Merges b into a
+ *
+ * This algorithm uses def_after to ensure that the sets always stay in the
+ * same order as the pre-order DFS done by the liveness algorithm.
+ */
 static merge_set *
 merge_merge_sets(merge_set *a, merge_set *b)
 {
@@ -223,6 +227,9 @@ merge_merge_sets(merge_set *a, merge_set *b)
 static bool
 merge_sets_interfere(merge_set *a, merge_set *b)
 {
+   /* List of all the nodes which dominate the current node, in dominance
+    * order.
+    */
    NIR_VLA(merge_node *, dom, a->size + b->size);
    int dom_idx = -1;
 
@@ -231,6 +238,9 @@ merge_sets_interfere(merge_set *a, merge_set *b)
    while (!exec_node_is_tail_sentinel(an) ||
           !exec_node_is_tail_sentinel(bn)) {
 
+      /* We walk the union of the two sets in the same order as the pre-order
+       * DFS done by liveness analysis.
+       */
       merge_node *current;
       if (exec_node_is_tail_sentinel(an)) {
          current = exec_node_data(merge_node, bn, node);
@@ -251,10 +261,35 @@ merge_sets_interfere(merge_set *a, merge_set *b)
          }
       }
 
+      /* Because our walk is a pre-order DFS, we can maintain the list of
+       * dominating nodes as a simple stack, pushing every node onto the list
+       * after we visit it and popping any non-dominating nodes off before we
+       * visit the current node.
+       */
       while (dom_idx >= 0 &&
              !ssa_def_dominates(dom[dom_idx]->def, current->def))
          dom_idx--;
 
+      /* There are three invariants of this algorithm that are important here:
+       *
+       *  1. There is no interference within either set a or set b.
+       *  2. None of the nodes processed up until this point interfere.
+       *  3. All the dominators of `current` have been processed
+       *
+       * Because of these invariants, we only need to check the current node
+       * against its minimal dominator.  If any other node N in the union
+       * interferes with current, then N must dominate current because we are
+       * in SSA form.  If N dominates current then it must also dominate our
+       * minimal dominator dom[dom_idx].  Since N is live at current it must
+       * also be live at the minimal dominator which means N interferes with
+       * the minimal dominator dom[dom_idx] and, by invariants 2 and 3 above,
+       * the algorithm would have already terminated.  Therefore, if we got
+       * here, the only node that can possibly interfere with current is the
+       * minimal dominator dom[dom_idx].
+       *
+       * This is what allows us to do a interference check of the union of the
+       * two sets with a single linear-time walk.
+       */
       if (dom_idx >= 0 && merge_nodes_interfere(current, dom[dom_idx]))
          return true;