[Mesa-dev] [RFC 4/5] nir/gcm: Rework the block assignment algorithm

[Jason Ekstrand]

The new algorithm differs from the classic GCM algorithm in that it will
prefer the instruction's original block if there are no better choices.
This new algorithm aims to be a bit more conservative and hopefully not
have quite as much of an impact on register pressure.
---
 src/compiler/nir/nir_opt_gcm.c | 30 ++++++++++++++++++++++++------
 1 file changed, 24 insertions(+), 6 deletions(-)

diff --git a/src/compiler/nir/nir_opt_gcm.c b/src/compiler/nir/nir_opt_gcm.c
index c4736d9..eb1f200 100644
--- a/src/compiler/nir/nir_opt_gcm.c
+++ b/src/compiler/nir/nir_opt_gcm.c
@@ -349,16 +349,34 @@ gcm_schedule_late_def(nir_ssa_def *def, void *void_state)
       state->instr_infos[def->parent_instr->index].early_block;
    assert(nir_block_dominates(early_block, lca));
 
-   /* We now have the LCA of all of the uses.  If our invariants hold,
-    * this is dominated by the block that we chose when scheduling early.
-    * We now walk up the dominance tree and pick the lowest block that is
-    * as far outside loops as we can get.
+   /* We now have the LCA of all of the uses.  This is the lower bound for a
+    * valid scheduling.  We also have a block from the schedule_early pass
+    * which serves as an upper bound.  If our invariants hold, the LCA is
+    * dominated by the early block and our task is to pick an "optimal" new
+    * block into which to place the instruction.
+    *
+    * The heuristic we use is to choose the block closest to the instruction's
+    * original block that is as far into if statements as possible while
+    * staying outside of loops.  It is possible, thanks to value numbering,
+    * for the LCA of the uses to actually dominate the block in which the
+    * instruction was originally placed.  In this case, we place it as far
+    * down the dominance tree as possible.
     */
    nir_block *best = lca;
    for (nir_block *block = lca; block != NULL; block = block->imm_dom) {
-      if (state->blocks[block->index].loop_depth <
-          state->blocks[best->index].loop_depth)
+      struct gcm_block_info *block_info = &state->blocks[block->index];
+      struct gcm_block_info *best_info = &state->blocks[best->index];
+      if (block_info->loop_depth < best_info->loop_depth) {
          best = block;
+      } else if (block_info->loop_depth == best_info->loop_depth) {
+         if (block_info->if_depth > best_info->if_depth) {
+            best = block;
+         } else if (block_info->if_depth == best_info->if_depth) {
+            /* Use the oringinal block if it's no worse than any other */
+            if (block == def->parent_instr->block)
+               best = block;
+         }
+      }
 
       if (block == early_block)
          break;
-- 
2.5.0.400.gff86faf