On Fri, Feb 6, 2015 at 5:38 PM, Connor Abbott <cwabbo...@gmail.com> wrote:
> On Fri, Feb 6, 2015 at 5:12 PM, Jason Ekstrand <ja...@jlekstrand.net>
> 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;
>
> 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,
>
I copied and pasted it from you. :-P Sure, I'll fix it up.
> Reviewed-by: Connor Abbott <cwabbo...@gmail.com>
>
> > +}
> > +
> > static bool
> > dump_block_dom(nir_block *block, void *state)
> > {
> > --
> > 2.2.2
> >
> > _______________________________________________
> > mesa-dev mailing list
> > mesa-dev@lists.freedesktop.org
> > http://lists.freedesktop.org/mailman/listinfo/mesa-dev
>
_______________________________________________
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/mesa-dev
