From f481a9425cb8d70bc61c6303268a465f5a05896b Mon Sep 17 00:00:00 2001 From: Jason Ekstrand Date: Fri, 6 Feb 2015 12:45:43 -0800 Subject: [PATCH] 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 --- 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 0784218c0db..7f6e241f915 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 29589cbce23..2f50db1c1f6 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.30.2