diff options
| -rw-r--r-- | src/glsl/nir/nir.h | 9 | ||||
| -rw-r--r-- | src/glsl/nir/nir_dominance.c | 30 |
2 files changed, 39 insertions, 0 deletions
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) { |