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

[Thomas Helland]

2016-08-25 7:49 GMT+02:00 Jason Ekstrand <jason at jlekstrand.net>:
> 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
> +    * 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

This doesn't parse at all.

> +       * 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);
> +      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