[Mesa-dev] [PATCH 2/3] nir/dominance: Add a constant-time mechanism for comparing blocks

[Connor Abbott]

On Fri, Feb 6, 2015 at 7:22 PM, Jason Ekstrand <jason at jlekstrand.net> wrote:
>
>
> On Fri, Feb 6, 2015 at 5:38 PM, Connor Abbott <cwabbott0 at gmail.com> wrote:
>>
>> On Fri, Feb 6, 2015 at 5:12 PM, Jason Ekstrand <jason at 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.

Lol, whoops...

>
>>
>> Reviewed-by: Connor Abbott <cwabbott0 at gmail.com>
>>
>> > +}
>> > +
>> >  static bool
>> >  dump_block_dom(nir_block *block, void *state)
>> >  {
>> > --
>> > 2.2.2
>> >
>> > _______________________________________________
>> > mesa-dev mailing list
>> > mesa-dev at lists.freedesktop.org
>> > http://lists.freedesktop.org/mailman/listinfo/mesa-dev
>
>