Mesa (staging/21.0): nir/from_ssa: consider defs in sibling blocks

[GitLab Mirror]

Module: Mesa
Branch: staging/21.0
Commit: 06faacb8b1adf4e3e41cdb387fe8390e44345d95
URL:    http://cgit.freedesktop.org/mesa/mesa/commit/?id=06faacb8b1adf4e3e41cdb387fe8390e44345d95

Author: Yevhenii Kolesnikov <yevhenii.kolesnikov at globallogic.com>
Date:   Thu Dec 24 01:16:38 2020 +0200

nir/from_ssa: consider defs in sibling blocks

If def a and def b are in sibling blocks, the one with higher
parent_instr's index does not necessarily come after the other.

Closes: https://gitlab.freedesktop.org/mesa/mesa/-/issues/3712
Fixes: 943ddb945877fc8 "nir: Add a better out-of-SSA pass"
Signed-off-by: Yevhenii Kolesnikov <yevhenii.kolesnikov at globallogic.com>
Reviewed-by: Jason Ekstrand <jason at jlekstrand.net>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/8246>
(cherry picked from commit fd05620e437e4957c9408cae249517f00236cee6)

---

 .pick_status.json               |  2 +-
 src/compiler/nir/nir_from_ssa.c | 19 ++++++++++++++++++-
 2 files changed, 19 insertions(+), 2 deletions(-)

diff --git a/.pick_status.json b/.pick_status.json
index af3522c7631..77859c3700f 100644
--- a/.pick_status.json
+++ b/.pick_status.json
@@ -1084,7 +1084,7 @@
         "description": "nir/from_ssa: consider defs in sibling blocks",
         "nominated": true,
         "nomination_type": 1,
-        "resolution": 0,
+        "resolution": 1,
         "master_sha": null,
         "because_sha": "943ddb945877fc8a48dd7a435d40e1a9e7b9eead"
     },
diff --git a/src/compiler/nir/nir_from_ssa.c b/src/compiler/nir/nir_from_ssa.c
index fcaf156d218..82b18c0b0aa 100644
--- a/src/compiler/nir/nir_from_ssa.c
+++ b/src/compiler/nir/nir_from_ssa.c
@@ -45,6 +45,15 @@ struct from_ssa_state {
 };
 
 /* Returns if def @a comes after def @b.
+ *
+ * The core observation that makes the Boissinot algorithm efficient
+ * is that, given two properly sorted sets, we can check for
+ * interference in these sets via a linear walk. This is accomplished
+ * by doing single combined walk over union of the two sets in DFS
+ * order. It doesn't matter what DFS we do so long as we're
+ * consistent. Fortunately, the dominance algorithm we ran prior to
+ * this pass did such a walk and recorded the pre- and post-indices in
+ * the blocks.
  *
  * We treat SSA undefs as always coming before other instruction types.
  */
@@ -57,7 +66,15 @@ def_after(nir_ssa_def *a, nir_ssa_def *b)
    if (b->parent_instr->type == nir_instr_type_ssa_undef)
       return true;
 
-   return a->parent_instr->index > b->parent_instr->index;
+   /* If they're in the same block, we can rely on whichever instruction
+    * comes first in the block.
+    */
+   if (a->parent_instr->block == b->parent_instr->block)
+      return a->parent_instr->index > b->parent_instr->index;
+
+   /* Otherwise, if blocks are distinct, we sort them in DFS pre-order */
+   return a->parent_instr->block->dom_pre_index >
+          b->parent_instr->block->dom_pre_index;
 }
 
 /* Returns true if a dominates b */