<div dir="ltr"> <div class="gmail_extra"> <div class="gmail_quote">On Fri, Feb 6, 2015 at 5:38 PM, Connor Abbott <<a href="mailto:cwabbott0@gmail.com" target="_blank">cwabbott0@gmail.com</a>> wrote: <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="HOEnZb"><div class="h5">On Fri, Feb 6, 2015 at 5:12 PM, Jason Ekstrand <<a href="mailto:jason@jlekstrand.net">jason@jlekstrand.net</a>> wrote: > 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. > --- > src/glsl/nir/nir.h | 9 +++++++++ > src/glsl/nir/nir_dominance.c | 27 +++++++++++++++++++++++++++ > 2 files changed, 36 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 1022692..76508f5 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 > @@ -224,6 +238,19 @@ nir_dominance_lca(nir_block *b1, nir_block *b2) > return intersect(b1, b2); > } > > +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_pre_index <= parent->dom_post_index; </div></div>It doesn't matter too much, but I think doing child->dom_post_index <= parent->dom_post_index will make it less likely for people to think it's a bug (I did at first). Other than that, </blockquote><div> </div><div>I copied and pasted it from you. :-P Sure, I'll fix it up. </div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> Reviewed-by: Connor Abbott <<a href="mailto:cwabbott0@gmail.com">cwabbott0@gmail.com</a>> > +} > + > static bool > dump_block_dom(nir_block *block, void *state) > { > -- > 2.2.2 > > _______________________________________________ > mesa-dev mailing list > <a href="mailto:mesa-dev@lists.freedesktop.org">mesa-dev@lists.freedesktop.org</a> > <a href="http://lists.freedesktop.org/mailman/listinfo/mesa-dev" target="_blank">http://lists.freedesktop.org/mailman/listinfo/mesa-dev</a> </blockquote></div> </div></div>