Mesa (master): nir/dominance: Add a constant-time mechanism for comparing blocks

[Jason Ekstrand]

Module: Mesa
Branch: master
Commit: f481a9425cb8d70bc61c6303268a465f5a05896b
URL:    http://cgit.freedesktop.org/mesa/mesa/commit/?id=f481a9425cb8d70bc61c6303268a465f5a05896b

Author: Jason Ekstrand <jason.ekstrand at intel.com>
Date:   Fri Feb  6 12:45:43 2015 -0800

nir/dominance: Add a constant-time mechanism for comparing blocks

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 0784218..7f6e241 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;
@@ -1518,6 +1526,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 29589cb..2f50db1 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)
 {