[Mesa-dev] [PATCH 1/8] nir/dominance: Better handle unreachable blocks

[Jason Ekstrand]

---
 src/compiler/nir/nir.h           |  9 ++++++++-
 src/compiler/nir/nir_dominance.c | 37 ++++++++++++++++++++++++++++++-------
 2 files changed, 38 insertions(+), 8 deletions(-)

diff --git a/src/compiler/nir/nir.h b/src/compiler/nir/nir.h
index 8d6f7d1..fc18b58 100644
--- a/src/compiler/nir/nir.h
+++ b/src/compiler/nir/nir.h
@@ -1498,13 +1498,20 @@ typedef struct nir_block {
     * dom_pre_index and dom_post_index for this block, which makes testing if
     * a given block is dominated by another block an O(1) operation.
     */
-   unsigned dom_pre_index, dom_post_index;
+   int16_t dom_pre_index, dom_post_index;
 
    /* live in and out for this block; used for liveness analysis */
    BITSET_WORD *live_in;
    BITSET_WORD *live_out;
 } nir_block;
 
+static inline bool
+nir_block_is_reachable(nir_block *b)
+{
+   /* See also nir_block_dominates */
+   return b->dom_post_index != -1;
+}
+
 static inline nir_instr *
 nir_block_first_instr(nir_block *block)
 {
diff --git a/src/compiler/nir/nir_dominance.c b/src/compiler/nir/nir_dominance.c
index 1781cdc..634519c 100644
--- a/src/compiler/nir/nir_dominance.c
+++ b/src/compiler/nir/nir_dominance.c
@@ -42,6 +42,10 @@ init_block(nir_block *block, nir_function_impl *impl)
       block->imm_dom = NULL;
    block->num_dom_children = 0;
 
+   /* See nir_block_dominates */
+   block->dom_pre_index = INT16_MAX;
+   block->dom_post_index = -1;
+
    struct set_entry *entry;
    set_foreach(block->dom_frontier, entry) {
       _mesa_set_remove(block->dom_frontier, entry);
@@ -204,18 +208,25 @@ nir_calc_dominance(nir_shader *shader)
    }
 }
 
+static nir_block *
+block_return_if_reachable(nir_block *b)
+{
+   return (b && nir_block_is_reachable(b)) ? b : NULL;
+}
+
 /**
- * Computes the least common anscestor of two blocks.  If one of the blocks
- * is null, the other block is returned.
+ * Computes the least common ancestor of two blocks.  If one of the blocks
+ * is null or unreachable, the other block is returned or NULL if it's
+ * unreachable.
  */
 nir_block *
 nir_dominance_lca(nir_block *b1, nir_block *b2)
 {
-   if (b1 == NULL)
-      return b2;
+   if (b1 == NULL || !nir_block_is_reachable(b1))
+      return block_return_if_reachable(b2);
 
-   if (b2 == NULL)
-      return b1;
+   if (b2 == NULL || !nir_block_is_reachable(b2))
+      return block_return_if_reachable(b1);
 
    assert(nir_cf_node_get_function(&b1->cf_node) ==
           nir_cf_node_get_function(&b2->cf_node));
@@ -227,7 +238,15 @@ nir_dominance_lca(nir_block *b1, nir_block *b2)
 }
 
 /**
- * Returns true if parent dominates child
+ * Returns true if parent dominates child according to the following
+ * definition:
+ *
+ *    "The block A dominates the block B if every path from the start block
+ *    to block B passes through A."
+ *
+ * This means, in particular, that any unreachable block is dominated by every
+ * other block and unreachable block does not dominate anything except another
+ * unreachable block.
  */
 bool
 nir_block_dominates(nir_block *parent, nir_block *child)
@@ -238,6 +257,10 @@ nir_block_dominates(nir_block *parent, nir_block *child)
    assert(nir_cf_node_get_function(&parent->cf_node)->valid_metadata &
           nir_metadata_dominance);
 
+   /* If a block is unreachable, then nir_block::dom_pre_index == INT32_MAX
+    * and nir_block::dom_post_index == -1.  This allows us to trivially handle
+    * unreachable blocks here with zero extra work.
+    */
    return child->dom_pre_index >= parent->dom_pre_index &&
           child->dom_post_index <= parent->dom_post_index;
 }
-- 
2.5.0.400.gff86faf