[Mesa-dev] [PATCH] nir/phi_builder: Don't recurse in value_get_block_def

[Connor Abbott]

On Thu, Aug 25, 2016 at 1:49 AM, Jason Ekstrand <jason at jlekstrand.net> wrote:
> In some programs, we can have very deep dominance trees and the recursion
> can cause us to risk stack overflows.  Instead, we replace the recursion
> with a pair of loops, one at the start and one at the end.  This is
> functionally equivalent to what we had before and it's actually a bit
> easier to read in the new form without the recursion.
>
> Signed-off-by: Jason Ekstrand <jason at jlekstrand.net>
> Bugzilla: https://bugs.freedesktop.org/show_bug.cgi?id=97225
> Cc: mesa-stable at lists.freedesktop.org
> ---
>  src/compiler/nir/nir_phi_builder.c | 65 +++++++++++++++++++++-----------------
>  1 file changed, 36 insertions(+), 29 deletions(-)
>
> diff --git a/src/compiler/nir/nir_phi_builder.c b/src/compiler/nir/nir_phi_builder.c
> index dd48975..24a3a7f 100644
> --- a/src/compiler/nir/nir_phi_builder.c
> +++ b/src/compiler/nir/nir_phi_builder.c
> @@ -172,31 +172,27 @@ nir_ssa_def *
>  nir_phi_builder_value_get_block_def(struct nir_phi_builder_value *val,
>                                      nir_block *block)
>  {
> -   /* For each block, we have one of three types of values */
> -   if (val->defs[block->index] == NULL) {
> -      /* NULL indicates that we have no SSA def for this block. */
> -      if (block->imm_dom) {
> -         /* Grab it from our immediate dominator.  We'll stash it here for
> -          * easy access later.
> -          */
> -         val->defs[block->index] =
> -            nir_phi_builder_value_get_block_def(val, block->imm_dom);
> -         return val->defs[block->index];
> -      } else {
> -         /* No immediate dominator means that this block is either the
> -          * start block or unreachable.  In either case, the value is
> -          * undefined so we need an SSA undef.
> -          */
> -         nir_ssa_undef_instr *undef =
> -            nir_ssa_undef_instr_create(val->builder->shader,
> -                                       val->num_components,
> -                                       val->bit_size);
> -         nir_instr_insert(nir_before_cf_list(&val->builder->impl->body),
> -                          &undef->instr);
> -         val->defs[block->index] = &undef->def;
> -         return &undef->def;
> -      }
> -   } else if (val->defs[block->index] == NEEDS_PHI) {
> +   /* Crawl up the dominance tree and find the highest dominator for which we

lowest dominator? Or maybe "closest dominator"?

> +    * have a valid ssa_def, if any.
> +    */
> +   nir_block *dom = block;
> +   while (dom && val->defs[dom->index] == NULL)
> +      dom = dom->imm_dom;
> +
> +   nir_ssa_def *def;
> +   if (dom == NULL) {
> +      /* No dominator means that this we either that we crawled to the top
> +       * without ever finding a definition or that this block is unreachable.
> +       * In either case, the value is undefined so we need an SSA undef.
> +       */
> +      nir_ssa_undef_instr *undef =
> +         nir_ssa_undef_instr_create(val->builder->shader,
> +                                    val->num_components,
> +                                    val->bit_size);
> +      nir_instr_insert(nir_before_cf_list(&val->builder->impl->body),
> +                       &undef->instr);

I mentioned on IRC that in the second case described in the comment
above, we should probably be inserting this into the block we found
whose imm_dom is NULL instead of the start block. But the old code
didn't handle it correctly anways so... meh. Other than the problems
with the comments pointed out by Thomas and me,

Reviewed-by: Connor Abbott <cwabbott0 at gmail.com>

> +      def = &undef->def;
> +   } else if (val->defs[dom->index] == NEEDS_PHI) {
>        /* The magic value NEEDS_PHI indicates that the block needs a phi node
>         * but none has been created.  We need to create one now so we can
>         * return it to the caller.
> @@ -218,17 +214,28 @@ nir_phi_builder_value_get_block_def(struct nir_phi_builder_value *val,
>        nir_phi_instr *phi = nir_phi_instr_create(val->builder->shader);
>        nir_ssa_dest_init(&phi->instr, &phi->dest, val->num_components,
>                          val->bit_size, NULL);
> -      phi->instr.block = block;
> +      phi->instr.block = dom;
>        exec_list_push_tail(&val->phis, &phi->instr.node);
> -      val->defs[block->index] = &phi->dest.ssa;
> -      return &phi->dest.ssa;
> +      def = &phi->dest.ssa;
>     } else {
>        /* In this case, we have an actual SSA def.  It's either the result of a
>         * phi node created by the case above or one passed to us through
>         * nir_phi_builder_value_set_block_def().
>         */
> -      return val->defs[block->index];
> +      def = val->defs[dom->index];
>     }
> +
> +   /* Walk the chain and stash the def in all of the applicable blocks.  We do
> +    * this for two reasons:
> +    *
> +    *  1) To speed up lookup next time even if the next time is called from a
> +    *     block that is not dominated by this one.
> +    *  2) To avoid unneeded recreation of phi nodes and undefs.
> +    */
> +   for (dom = block; dom && val->defs[dom->index] == NULL; dom = dom->imm_dom)
> +      val->defs[dom->index] = def;
> +
> +   return def;
>  }
>
>  static int
> --
> 2.5.0.400.gff86faf
>
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/mesa-dev