[Mesa-dev] [RFC] nir: Improve induction variables detection

[Elie Tournier]

The actual code detect only basic induction variables (i = i +/- c).
I'm working on improve the detection in order to reconize derived induction varibles (j = c1 * i +/- c2).
I obtain the code below.

I'm not sure about the nir_derived_induction_var.
Should I replace "nir_loop_variable *def_outside_loop" by "nir_basic_indiction_var"?

Comments are welcome.

The goal is to implement a strength reduction algo.

Signed-off-by: Elie Tournier <tournier.elie at gmail.com>
---
 src/compiler/nir/nir_loop_analyze.c | 46 ++++++++++++++++++++++++++++++++++++-
 1 file changed, 45 insertions(+), 1 deletion(-)

diff --git a/src/compiler/nir/nir_loop_analyze.c b/src/compiler/nir/nir_loop_analyze.c
index 6afad9e603..587726914a 100644
--- a/src/compiler/nir/nir_loop_analyze.c
+++ b/src/compiler/nir/nir_loop_analyze.c
@@ -29,10 +29,12 @@ typedef enum {
    undefined,
    invariant,
    not_invariant,
-   basic_induction
+   basic_induction,
+   derived_induction
 } nir_loop_variable_type;
 
 struct nir_basic_induction_var;
+struct nir_derived_induction_var;
 
 typedef struct {
    /* A link for the work list */
@@ -49,6 +51,9 @@ typedef struct {
    /* If this is of type basic_induction */
    struct nir_basic_induction_var *ind;
 
+   /* If this is of type derived_induction */
+   struct nir_derived_induction_var *derived_ind;
+
    /* True if variable is in an if branch or a nested loop */
    bool in_control_flow;
 
@@ -61,6 +66,14 @@ typedef struct nir_basic_induction_var {
    nir_loop_variable *def_outside_loop;     /* The phi-src outside the loop */
 } nir_basic_induction_var;
 
+typedef struct nir_derived_induction_var {
+   nir_op alu_op;                           /* The type of alu-operation    */
+   nir_loop_variable *alu_def;              /* The def of the alu-operation */
+   nir_loop_variable *invariant_0;          /* The invariant alu-operand    */
+   nir_loop_variable *invariant_1;          /* The invariant alu-operand    */
+   nir_loop_variable *def_outside_loop;     /* The phi-src outside the loop */
+} nir_derived_induction_var;
+
 typedef struct {
    /* The loop we store information for */
    nir_loop *loop;
@@ -227,6 +240,7 @@ compute_induction_information(loop_info_state *state)
 
       nir_phi_instr *phi = nir_instr_as_phi(var->def->parent_instr);
       nir_basic_induction_var *biv = rzalloc(state, nir_basic_induction_var);
+      nir_derived_induction_var *div = rzalloc(state, nir_derived_induction_var);
 
       nir_foreach_phi_src(src, phi) {
          nir_loop_variable *src_var = get_loop_var(src->src.ssa, state);
@@ -239,9 +253,11 @@ compute_induction_information(loop_info_state *state)
 
          if (!src_var->in_loop) {
             biv->def_outside_loop = src_var;
+            div->def_outside_loop = src_var;
          } else if (is_var_alu(src_var)) {
             nir_alu_instr *alu = nir_instr_as_alu(src_var->def->parent_instr);
 
+            /* basic induction variable (i = i +/- c) */
             if (nir_op_infos[alu->op].num_inputs == 2) {
                biv->alu_def = src_var;
                biv->alu_op = alu->op;
@@ -253,6 +269,23 @@ compute_induction_information(loop_info_state *state)
                      biv->invariant = get_loop_var(alu->src[i].src.ssa, state);
                }
             }
+            /* derived induction variable (j = c1 * i +/- c2 ) */
+            if (nir_op_infos[alu->op].num_inputs == 3) {
+               div->alu_def = src_var;
+               div->alu_op = alu->op;
+
+               for (unsigned i = 0; i < 3; i++) {
+                  /* Is one of the operands const, an other the induction var,
+                   * and the last an other const
+                   */
+                  if (alu->src[i].src.ssa->parent_instr->type == nir_instr_type_load_const &&
+                      alu->src[1-i].src.ssa == &phi->dest.ssa &&
+                      alu->src[2-i].src.ssa->parent_instr->type == nir_instr_type_load_const) {
+                     div->invariant_0 = get_loop_var(alu->src[i].src.ssa, state);
+                     div->invariant_1 = get_loop_var(alu->src[2-i].src.ssa, state);
+                  }
+               }
+            }
          }
       }
 
@@ -265,8 +298,19 @@ compute_induction_information(loop_info_state *state)
          var->ind = biv;
 
          found_induction_var = true;
+      } else if (div->alu_def && div->def_outside_loop && div->invariant_0 &&
+          div->invariant_1 && is_var_constant(div->def_outside_loop)) {
+         assert(is_var_constant(div->invariant_0));
+         assert(is_var_constant(div->invariant_1));
+         div->alu_def->type = derived_induction;
+         div->alu_def->derived_ind = div;
+         var->type = derived_induction;
+         var->derived_ind = div;
+
+         found_induction_var = true;
       } else {
          ralloc_free(biv);
+         ralloc_free(div);
       }
    }
    return found_induction_var;
-- 
2.11.0