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

[tournier.elie]

Any comments, tips before I go to deep in the code?

On 24 February 2017 at 12:17, Elie Tournier <tournier.elie at gmail.com> wrote:
> 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
>