Mesa (master): nir/phi_builder: Don't recurse in value_get_block_def

[Jason Ekstrand]

Module: Mesa
Branch: master
Commit: 78715c7211aa81a1b189c3a29df4b2b98d2e0fc3
URL:    http://cgit.freedesktop.org/mesa/mesa/commit/?id=78715c7211aa81a1b189c3a29df4b2b98d2e0fc3

Author: Jason Ekstrand <jason.ekstrand at intel.com>
Date:   Wed Aug 24 21:49:10 2016 -0700

nir/phi_builder: Don't recurse in value_get_block_def

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
Reviewed-by: Connor Abbott <cwabbott0 at gmail.com>
Reviewed-by: Matt Turner <mattst88 at gmail.com>

---

 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..f96dad7 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 closest 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 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);
+      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