[Mesa-dev] [RFC 3/5] nir/gcm: Use an array for storring the early block

[Jason Ekstrand]

We are about to adjust our instruction block assignment algorithm and we
will want to know the current block that the instruction lives in.  In
order to allow for this, we can't overwrite nir_instr::block in the
early scheduling pass.
---
 src/compiler/nir/nir_opt_gcm.c | 43 +++++++++++++++++++++++++++++++++---------
 1 file changed, 34 insertions(+), 9 deletions(-)

diff --git a/src/compiler/nir/nir_opt_gcm.c b/src/compiler/nir/nir_opt_gcm.c
index a07f2f1..c4736d9 100644
--- a/src/compiler/nir/nir_opt_gcm.c
+++ b/src/compiler/nir/nir_opt_gcm.c
@@ -51,6 +51,10 @@ struct gcm_block_info {
    nir_instr *last_instr;
 };
 
+struct gcm_instr_info {
+   nir_block *early_block;
+};
+
 /* Flags used in the instr->pass_flags field for various instruction states */
 enum {
    GCM_INSTR_PINNED =            (1 << 0),
@@ -71,6 +75,9 @@ struct gcm_state {
    struct exec_list instrs;
 
    struct gcm_block_info *blocks;
+
+   unsigned num_instrs;
+   struct gcm_instr_info *instr_infos;
 };
 
 /* Recursively walks the CFG and builds the block_info structure */
@@ -115,8 +122,13 @@ gcm_build_block_info(struct exec_list *cf_list, struct gcm_state *state,
 static void
 gcm_pin_instructions(nir_function_impl *impl, struct gcm_state *state)
 {
+   state->num_instrs = 0;
+
    nir_foreach_block(block, impl) {
       nir_foreach_instr_safe(instr, block) {
+         /* Index the instructions for use in gcm_state::instrs */
+         instr->index = state->num_instrs++;
+
          switch (instr->type) {
          case nir_instr_type_alu:
             switch (nir_instr_as_alu(instr)->op) {
@@ -224,8 +236,11 @@ gcm_schedule_early_src(nir_src *src, void *void_state)
     * all of the sources must lie on the same branch of the dominance tree.
     * Therefore, we can just go ahead and just compare indices.
     */
-   if (instr->block->index < src->ssa->parent_instr->block->index)
-      instr->block = src->ssa->parent_instr->block;
+   struct gcm_instr_info *src_info =
+      &state->instr_infos[src->ssa->parent_instr->index];
+   struct gcm_instr_info *info = &state->instr_infos[instr->index];
+   if (info->early_block->index < src_info->early_block->index)
+      info->early_block = src_info->early_block;
 
    /* We need to restore the state instruction because it may have been
     * changed through the gcm_schedule_early_instr call above.  Since we
@@ -242,7 +257,8 @@ gcm_schedule_early_src(nir_src *src, void *void_state)
  * This function performs a recursive depth-first search starting at the
  * given instruction and proceeding through the sources to schedule
  * instructions as early as they can possibly go in the dominance tree.
- * The instructions are "scheduled" by updating their instr->block field.
+ * The instructions are "scheduled" by updating the early_block field of
+ * the corresponding gcm_instr_state entry.
  */
 static void
 gcm_schedule_early_instr(nir_instr *instr, struct gcm_state *state)
@@ -252,17 +268,19 @@ gcm_schedule_early_instr(nir_instr *instr, struct gcm_state *state)
 
    instr->pass_flags |= GCM_INSTR_SCHEDULED_EARLY;
 
-   /* Pinned instructions are already scheduled so we don't need to do
-    * anything.  Also, bailing here keeps us from ever following the
-    * sources of phi nodes which can be back-edges.
+   /* Pinned instructions always get scheduled in their original block so we
+    * don't need to do anything.  Also, bailing here keeps us from ever
+    * following the sources of phi nodes which can be back-edges.
     */
-   if (instr->pass_flags & GCM_INSTR_PINNED)
+   if (instr->pass_flags & GCM_INSTR_PINNED) {
+      state->instr_infos[instr->index].early_block = instr->block;
       return;
+   }
 
    /* Start with the instruction at the top.  As we iterate over the
     * sources, it will get moved down as needed.
     */
-   instr->block = nir_start_block(state->impl);
+   state->instr_infos[instr->index].early_block = nir_start_block(state->impl);
    state->instr = instr;
 
    nir_foreach_src(instr, gcm_schedule_early_src, state);
@@ -327,6 +345,10 @@ gcm_schedule_late_def(nir_ssa_def *def, void *void_state)
    if (lca == NULL)
       return true;
 
+   nir_block *early_block =
+      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
@@ -338,7 +360,7 @@ gcm_schedule_late_def(nir_ssa_def *def, void *void_state)
           state->blocks[best->index].loop_depth)
          best = block;
 
-      if (block == def->parent_instr->block)
+      if (block == early_block)
          break;
    }
    def->parent_instr->block = best;
@@ -477,6 +499,9 @@ opt_gcm_impl(nir_function_impl *impl, bool value_number)
 
    gcm_pin_instructions(impl, &state);
 
+   state.instr_infos =
+      rzalloc_array(NULL, struct gcm_instr_info, state.num_instrs);
+
    bool progress = false;
    if (value_number) {
       struct set *gvn_set = nir_instr_set_create(NULL);
-- 
2.5.0.400.gff86faf