From 4d083b52c04745d18d8f5446be5805077fa2c51a Mon Sep 17 00:00:00 2001
From: Jason Ekstrand <jason@jlekstrand.net>
Date: Tue, 17 Jan 2017 18:38:35 -0800
Subject: [PATCH] nir/dominance: Better handle unreachable blocks

v2: Fix minor comments (Ken)

Reviewed-by: Kenneth Graunke <kenneth@whitecape.org>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/4636>
---
 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 b9a5637..105e093 100644
--- a/src/compiler/nir/nir.h
+++ b/src/compiler/nir/nir.h
@@ -2406,13 +2406,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 8369c28..192d330 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;
+
    set_foreach(block->dom_frontier, entry) {
       _mesa_set_remove(block->dom_frontier, entry);
    }
@@ -201,18 +205,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));
@@ -224,7 +235,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 an unreachable block does not dominate anything except
+ * another unreachable block.
  */
 bool
 nir_block_dominates(nir_block *parent, nir_block *child)
@@ -235,6 +254,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 == INT16_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.7.4