[Mesa-dev] [PATCH v3 02/12] nir/dominance: Add a constant-time mechanism for comparing blocks

[Jason Ekstrand]

This is mostly thanks to Connor.  The idea is to do a depth-first search
that computes pre and post indices for all the blocks.  We can then figure
out if one block dominates another in constant time by two simple
comparison operations.

Reviewed-by: Connor Abbott <cwabbott0 at gmail.com>
---
 src/glsl/nir/nir.h           |  9 +++++++++
 src/glsl/nir/nir_dominance.c | 30 ++++++++++++++++++++++++++++++
 2 files changed, 39 insertions(+)

diff --git a/src/glsl/nir/nir.h b/src/glsl/nir/nir.h
index 886dcd2..5d84343 100644
--- a/src/glsl/nir/nir.h
+++ b/src/glsl/nir/nir.h
@@ -1135,6 +1135,14 @@ typedef struct nir_block {
    /* Set of nir_block's on the dominance frontier of this block */
    struct set *dom_frontier;
 
+   /*
+    * These two indices have the property that dom_{pre,post}_index for each
+    * child of this block in the dominance tree will always be between
+    * 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;
+
    /* live in and out for this block; used for liveness analysis */
    BITSET_WORD *live_in;
    BITSET_WORD *live_out;
@@ -1501,6 +1509,7 @@ void nir_calc_dominance_impl(nir_function_impl *impl);
 void nir_calc_dominance(nir_shader *shader);
 
 nir_block *nir_dominance_lca(nir_block *b1, nir_block *b2);
+bool nir_block_dominates(nir_block *parent, nir_block *child);
 
 void nir_dump_dom_tree_impl(nir_function_impl *impl, FILE *fp);
 void nir_dump_dom_tree(nir_shader *shader, FILE *fp);
diff --git a/src/glsl/nir/nir_dominance.c b/src/glsl/nir/nir_dominance.c
index 831b9a3..d69e4f4 100644
--- a/src/glsl/nir/nir_dominance.c
+++ b/src/glsl/nir/nir_dominance.c
@@ -177,6 +177,17 @@ calc_dom_children(nir_function_impl* impl)
    nir_foreach_block(impl, block_add_child, NULL);
 }
 
+static void
+calc_dfs_indicies(nir_block *block, unsigned *index)
+{
+   block->dom_pre_index = (*index)++;
+
+   for (unsigned i = 0; i < block->num_dom_children; i++)
+      calc_dfs_indicies(block->dom_children[i], index);
+
+   block->dom_post_index = (*index)++;
+}
+
 void
 nir_calc_dominance_impl(nir_function_impl *impl)
 {
@@ -201,6 +212,9 @@ nir_calc_dominance_impl(nir_function_impl *impl)
    impl->start_block->imm_dom = NULL;
 
    calc_dom_children(impl);
+
+   unsigned dfs_index = 0;
+   calc_dfs_indicies(impl->start_block, &dfs_index);
 }
 
 void
@@ -234,6 +248,22 @@ nir_dominance_lca(nir_block *b1, nir_block *b2)
    return intersect(b1, b2);
 }
 
+/**
+ * Returns true if parent dominates child
+ */
+bool
+nir_block_dominates(nir_block *parent, nir_block *child)
+{
+   assert(nir_cf_node_get_function(&parent->cf_node) ==
+          nir_cf_node_get_function(&child->cf_node));
+
+   assert(nir_cf_node_get_function(&parent->cf_node)->valid_metadata &
+          nir_metadata_dominance);
+
+   return child->dom_pre_index >= parent->dom_pre_index &&
+          child->dom_post_index <= parent->dom_post_index;
+}
+
 static bool
 dump_block_dom(nir_block *block, void *state)
 {
-- 
2.2.2