src/compiler/nir/nir_loop_analyze.c

   1 /*
   2  * Copyright © 2015 Thomas Helland
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a
   5  * copy of this software and associated documentation files (the "Software"),
   6  * to deal in the Software without restriction, including without limitation
   7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   8  * and/or sell copies of the Software, and to permit persons to whom the
   9  * Software is furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice (including the next
  12  * paragraph) shall be included in all copies or substantial portions of the
  13  * Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  18  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  21  * IN THE SOFTWARE.
  22  */
  23
  24 #include "nir.h"
  25 #include "nir_constant_expressions.h"
  26 #include "nir_loop_analyze.h"
  27
  28 typedef enum {
  29    undefined,
  30    invariant,
  31    not_invariant,
  32    basic_induction
  33 } nir_loop_variable_type;
  34
  35 struct nir_basic_induction_var;
  36
  37 typedef struct {
  38    /* A link for the work list */
  39    struct list_head process_link;
  40
  41    bool in_loop;
  42
  43    /* The ssa_def associated with this info */
  44    nir_ssa_def *def;
  45
  46    /* The type of this ssa_def */
  47    nir_loop_variable_type type;
  48
  49    /* If this is of type basic_induction */
  50    struct nir_basic_induction_var *ind;
  51
  52    /* True if variable is in an if branch or a nested loop */
  53    bool in_control_flow;
  54
  55 } nir_loop_variable;
  56
  57 typedef struct nir_basic_induction_var {
  58    nir_op alu_op;                           /* The type of alu-operation    */
  59    nir_loop_variable *alu_def;              /* The def of the alu-operation */
  60    nir_loop_variable *invariant;            /* The invariant alu-operand    */
  61    nir_loop_variable *def_outside_loop;     /* The phi-src outside the loop */
  62 } nir_basic_induction_var;
  63
  64 typedef struct {
  65    /* The loop we store information for */
  66    nir_loop *loop;
  67
  68    /* Loop_variable for all ssa_defs in function */
  69    nir_loop_variable *loop_vars;
  70
  71    /* A list of the loop_vars to analyze */
  72    struct list_head process_list;
  73
  74    nir_variable_mode indirect_mask;
  75
  76 } loop_info_state;
  77
  78 static nir_loop_variable *
  79 get_loop_var(nir_ssa_def *value, loop_info_state *state)
  80 {
  81    return &(state->loop_vars[value->index]);
  82 }
  83
  84 typedef struct {
  85    loop_info_state *state;
  86    bool in_control_flow;
  87 } init_loop_state;
  88
  89 static bool
  90 init_loop_def(nir_ssa_def *def, void *void_init_loop_state)
  91 {
  92    init_loop_state *loop_init_state = void_init_loop_state;
  93    nir_loop_variable *var = get_loop_var(def, loop_init_state->state);
  94
  95    if (loop_init_state->in_control_flow) {
  96       var->in_control_flow = true;
  97    } else {
  98       /* Add to the tail of the list. That way we start at the beginning of
  99        * the defs in the loop instead of the end when walking the list. This
 100        * means less recursive calls. Only add defs that are not in nested
 101        * loops or conditional blocks.
 102        */
 103       list_addtail(&var->process_link, &loop_init_state->state->process_list);
 104    }
 105
 106    var->in_loop = true;
 107
 108    return true;
 109 }
 110
 111 static bool
 112 init_loop_block(nir_block *block, loop_info_state *state,
 113                 bool in_control_flow)
 114 {
 115    init_loop_state init_state = {.in_control_flow = in_control_flow,
 116                                  .state = state };
 117
 118    nir_foreach_instr(instr, block) {
 119       if (instr->type == nir_instr_type_intrinsic ||
 120           instr->type == nir_instr_type_alu ||
 121           instr->type == nir_instr_type_tex) {
 122          state->loop->info->num_instructions++;
 123       }
 124
 125       nir_foreach_ssa_def(instr, init_loop_def, &init_state);
 126    }
 127
 128    return true;
 129 }
 130
 131 static inline bool
 132 is_var_alu(nir_loop_variable *var)
 133 {
 134    return var->def->parent_instr->type == nir_instr_type_alu;
 135 }
 136
 137 static inline bool
 138 is_var_constant(nir_loop_variable *var)
 139 {
 140    return var->def->parent_instr->type == nir_instr_type_load_const;
 141 }
 142
 143 static inline bool
 144 is_var_phi(nir_loop_variable *var)
 145 {
 146    return var->def->parent_instr->type == nir_instr_type_phi;
 147 }
 148
 149 static inline bool
 150 mark_invariant(nir_ssa_def *def, loop_info_state *state)
 151 {
 152    nir_loop_variable *var = get_loop_var(def, state);
 153
 154    if (var->type == invariant)
 155       return true;
 156
 157    if (!var->in_loop) {
 158       var->type = invariant;
 159       return true;
 160    }
 161
 162    if (var->type == not_invariant)
 163       return false;
 164
 165    if (is_var_alu(var)) {
 166       nir_alu_instr *alu = nir_instr_as_alu(def->parent_instr);
 167
 168       for (unsigned i = 0; i < nir_op_infos[alu->op].num_inputs; i++) {
 169          if (!mark_invariant(alu->src[i].src.ssa, state)) {
 170             var->type = not_invariant;
 171             return false;
 172          }
 173       }
 174       var->type = invariant;
 175       return true;
 176    }
 177
 178    /* Phis shouldn't be invariant except if one operand is invariant, and the
 179     * other is the phi itself. These should be removed by opt_remove_phis.
 180     * load_consts are already set to invariant and constant during init,
 181     * and so should return earlier. Remaining op_codes are set undefined.
 182     */
 183    var->type = not_invariant;
 184    return false;
 185 }
 186
 187 static void
 188 compute_invariance_information(loop_info_state *state)
 189 {
 190    /* An expression is invariant in a loop L if:
 191     *  (base cases)
 192     *    – it’s a constant
 193     *    – it’s a variable use, all of whose single defs are outside of L
 194     *  (inductive cases)
 195     *    – it’s a pure computation all of whose args are loop invariant
 196     *    – it’s a variable use whose single reaching def, and the
 197     *      rhs of that def is loop-invariant
 198     */
 199    list_for_each_entry_safe(nir_loop_variable, var, &state->process_list,
 200                             process_link) {
 201       assert(!var->in_control_flow);
 202
 203       if (mark_invariant(var->def, state))
 204          list_del(&var->process_link);
 205    }
 206 }
 207
 208 static bool
 209 compute_induction_information(loop_info_state *state)
 210 {
 211    bool found_induction_var = false;
 212    list_for_each_entry_safe(nir_loop_variable, var, &state->process_list,
 213                             process_link) {
 214
 215       /* It can't be an induction variable if it is invariant. Invariants and
 216        * things in nested loops or conditionals should have been removed from
 217        * the list by compute_invariance_information().
 218        */
 219       assert(!var->in_control_flow && var->type != invariant);
 220
 221       /* We are only interested in checking phis for the basic induction
 222        * variable case as its simple to detect. All basic induction variables
 223        * have a phi node
 224        */
 225       if (!is_var_phi(var))
 226          continue;
 227
 228       nir_phi_instr *phi = nir_instr_as_phi(var->def->parent_instr);
 229       nir_basic_induction_var *biv = rzalloc(state, nir_basic_induction_var);
 230
 231       nir_foreach_phi_src(src, phi) {
 232          nir_loop_variable *src_var = get_loop_var(src->src.ssa, state);
 233
 234          /* If one of the sources is in a conditional or nested block then
 235           * panic.
 236           */
 237          if (src_var->in_control_flow)
 238             break;
 239
 240          if (!src_var->in_loop) {
 241             biv->def_outside_loop = src_var;
 242          } else if (is_var_alu(src_var)) {
 243             nir_alu_instr *alu = nir_instr_as_alu(src_var->def->parent_instr);
 244
 245             if (nir_op_infos[alu->op].num_inputs == 2) {
 246                biv->alu_def = src_var;
 247                biv->alu_op = alu->op;
 248
 249                for (unsigned i = 0; i < 2; i++) {
 250                   /* Is one of the operands const, and the other the phi */
 251                   if (alu->src[i].src.ssa->parent_instr->type == nir_instr_type_load_const &&
 252                       alu->src[1-i].src.ssa == &phi->dest.ssa)
 253                      biv->invariant = get_loop_var(alu->src[i].src.ssa, state);
 254                }
 255             }
 256          }
 257       }
 258
 259       if (biv->alu_def && biv->def_outside_loop && biv->invariant &&
 260           is_var_constant(biv->def_outside_loop)) {
 261          assert(is_var_constant(biv->invariant));
 262          biv->alu_def->type = basic_induction;
 263          biv->alu_def->ind = biv;
 264          var->type = basic_induction;
 265          var->ind = biv;
 266
 267          found_induction_var = true;
 268       } else {
 269          ralloc_free(biv);
 270       }
 271    }
 272    return found_induction_var;
 273 }
 274
 275 static bool
 276 initialize_ssa_def(nir_ssa_def *def, void *void_state)
 277 {
 278    loop_info_state *state = void_state;
 279    nir_loop_variable *var = get_loop_var(def, state);
 280
 281    var->in_loop = false;
 282    var->def = def;
 283
 284    if (def->parent_instr->type == nir_instr_type_load_const) {
 285       var->type = invariant;
 286    } else {
 287       var->type = undefined;
 288    }
 289
 290    return true;
 291 }
 292
 293 static inline bool
 294 ends_in_break(nir_block *block)
 295 {
 296    if (exec_list_is_empty(&block->instr_list))
 297       return false;
 298
 299    nir_instr *instr = nir_block_last_instr(block);
 300    return instr->type == nir_instr_type_jump &&
 301       nir_instr_as_jump(instr)->type == nir_jump_break;
 302 }
 303
 304 static bool
 305 find_loop_terminators(loop_info_state *state)
 306 {
 307    bool success = false;
 308    foreach_list_typed_safe(nir_cf_node, node, node, &state->loop->body) {
 309       if (node->type == nir_cf_node_if) {
 310          nir_if *nif = nir_cf_node_as_if(node);
 311
 312          nir_block *break_blk = NULL;
 313          nir_block *continue_from_blk = NULL;
 314          bool continue_from_then = true;
 315
 316          nir_block *last_then = nir_if_last_then_block(nif);
 317          nir_block *last_else = nir_if_last_else_block(nif);
 318          if (ends_in_break(last_then)) {
 319             break_blk = last_then;
 320             continue_from_blk = last_else;
 321             continue_from_then = false;
 322          } else if (ends_in_break(last_else)) {
 323             break_blk = last_else;
 324             continue_from_blk = last_then;
 325          }
 326
 327          /* If there is a break then we should find a terminator. If we can
 328           * not find a loop terminator, but there is a break-statement then
 329           * we should return false so that we do not try to find trip-count
 330           */
 331          if (!nir_is_trivial_loop_if(nif, break_blk))
 332             return false;
 333
 334          /* Continue if the if contained no jumps at all */
 335          if (!break_blk)
 336             continue;
 337
 338          if (nif->condition.ssa->parent_instr->type == nir_instr_type_phi)
 339             return false;
 340
 341          nir_loop_terminator *terminator =
 342             rzalloc(state->loop->info, nir_loop_terminator);
 343
 344          list_add(&terminator->loop_terminator_link,
 345                   &state->loop->info->loop_terminator_list);
 346
 347          terminator->nif = nif;
 348          terminator->break_block = break_blk;
 349          terminator->continue_from_block = continue_from_blk;
 350          terminator->continue_from_then = continue_from_then;
 351          terminator->conditional_instr = nif->condition.ssa->parent_instr;
 352
 353          success = true;
 354       }
 355    }
 356
 357    return success;
 358 }
 359
 360 static int32_t
 361 get_iteration(nir_op cond_op, nir_const_value *initial, nir_const_value *step,
 362               nir_const_value *limit)
 363 {
 364    int32_t iter;
 365
 366    switch (cond_op) {
 367    case nir_op_ige:
 368    case nir_op_ilt:
 369    case nir_op_ieq:
 370    case nir_op_ine: {
 371       int32_t initial_val = initial->i32[0];
 372       int32_t span = limit->i32[0] - initial_val;
 373       iter = span / step->i32[0];
 374       break;
 375    }
 376    case nir_op_uge:
 377    case nir_op_ult: {
 378       uint32_t initial_val = initial->u32[0];
 379       uint32_t span = limit->u32[0] - initial_val;
 380       iter = span / step->u32[0];
 381       break;
 382    }
 383    case nir_op_fge:
 384    case nir_op_flt:
 385    case nir_op_feq:
 386    case nir_op_fne: {
 387       float initial_val = initial->f32[0];
 388       float span = limit->f32[0] - initial_val;
 389       iter = span / step->f32[0];
 390       break;
 391    }
 392    default:
 393       return -1;
 394    }
 395
 396    return iter;
 397 }
 398
 399 static bool
 400 test_iterations(int32_t iter_int, nir_const_value *step,
 401                 nir_const_value *limit, nir_op cond_op, unsigned bit_size,
 402                 nir_alu_type induction_base_type,
 403                 nir_const_value *initial, bool limit_rhs, bool invert_cond)
 404 {
 405    assert(nir_op_infos[cond_op].num_inputs == 2);
 406
 407    nir_const_value iter_src = { {0, } };
 408    nir_op mul_op;
 409    nir_op add_op;
 410    switch (induction_base_type) {
 411    case nir_type_float:
 412       iter_src.f32[0] = (float) iter_int;
 413       mul_op = nir_op_fmul;
 414       add_op = nir_op_fadd;
 415       break;
 416    case nir_type_int:
 417    case nir_type_uint:
 418       iter_src.i32[0] = iter_int;
 419       mul_op = nir_op_imul;
 420       add_op = nir_op_iadd;
 421       break;
 422    default:
 423       unreachable("Unhandled induction variable base type!");
 424    }
 425
 426    /* Multiple the iteration count we are testing by the number of times we
 427     * step the induction variable each iteration.
 428     */
 429    nir_const_value mul_src[2] = { iter_src, *step };
 430    nir_const_value mul_result =
 431       nir_eval_const_opcode(mul_op, 1, bit_size, mul_src);
 432
 433    /* Add the initial value to the accumulated induction variable total */
 434    nir_const_value add_src[2] = { mul_result, *initial };
 435    nir_const_value add_result =
 436       nir_eval_const_opcode(add_op, 1, bit_size, add_src);
 437
 438    nir_const_value src[2] = { { {0, } }, { {0, } } };
 439    src[limit_rhs ? 0 : 1] = add_result;
 440    src[limit_rhs ? 1 : 0] = *limit;
 441
 442    /* Evaluate the loop exit condition */
 443    nir_const_value result = nir_eval_const_opcode(cond_op, 1, bit_size, src);
 444
 445    return invert_cond ? (result.u32[0] == 0) : (result.u32[0] != 0);
 446 }
 447
 448 static int
 449 calculate_iterations(nir_const_value *initial, nir_const_value *step,
 450                      nir_const_value *limit, nir_loop_variable *alu_def,
 451                      nir_alu_instr *cond_alu, bool limit_rhs, bool invert_cond)
 452 {
 453    assert(initial != NULL && step != NULL && limit != NULL);
 454
 455    nir_alu_instr *alu = nir_instr_as_alu(alu_def->def->parent_instr);
 456
 457    /* nir_op_isub should have been lowered away by this point */
 458    assert(alu->op != nir_op_isub);
 459
 460    /* Make sure the alu type for our induction variable is compatible with the
 461     * conditional alus input type. If its not something has gone really wrong.
 462     */
 463    nir_alu_type induction_base_type =
 464       nir_alu_type_get_base_type(nir_op_infos[alu->op].output_type);
 465    if (induction_base_type == nir_type_int || induction_base_type == nir_type_uint) {
 466       assert(nir_alu_type_get_base_type(nir_op_infos[cond_alu->op].input_types[1]) == nir_type_int ||
 467              nir_alu_type_get_base_type(nir_op_infos[cond_alu->op].input_types[1]) == nir_type_uint);
 468    } else {
 469       assert(nir_alu_type_get_base_type(nir_op_infos[cond_alu->op].input_types[0]) ==
 470              induction_base_type);
 471    }
 472
 473    /* Check for nsupported alu operations */
 474    if (alu->op != nir_op_iadd && alu->op != nir_op_fadd)
 475       return -1;
 476
 477    /* do-while loops can increment the starting value before the condition is
 478     * checked. e.g.
 479     *
 480     *    do {
 481     *        ndx++;
 482     *     } while (ndx < 3);
 483     *
 484     * Here we check if the induction variable is used directly by the loop
 485     * condition and if so we assume we need to step the initial value.
 486     */
 487    unsigned trip_offset = 0;
 488    if (cond_alu->src[0].src.ssa == alu_def->def ||
 489        cond_alu->src[1].src.ssa == alu_def->def) {
 490       trip_offset = 1;
 491    }
 492
 493    int iter_int = get_iteration(cond_alu->op, initial, step, limit);
 494
 495    /* If iter_int is negative the loop is ill-formed or is the conditional is
 496     * unsigned with a huge iteration count so don't bother going any further.
 497     */
 498    if (iter_int < 0)
 499       return -1;
 500
 501    /* An explanation from the GLSL unrolling pass:
 502     *
 503     * Make sure that the calculated number of iterations satisfies the exit
 504     * condition.  This is needed to catch off-by-one errors and some types of
 505     * ill-formed loops.  For example, we need to detect that the following
 506     * loop does not have a maximum iteration count.
 507     *
 508     *    for (float x = 0.0; x != 0.9; x += 0.2);
 509     */
 510    assert(nir_src_bit_size(alu->src[0].src) ==
 511           nir_src_bit_size(alu->src[1].src));
 512    unsigned bit_size = nir_src_bit_size(alu->src[0].src);
 513    for (int bias = -1; bias <= 1; bias++) {
 514       const int iter_bias = iter_int + bias;
 515
 516       if (test_iterations(iter_bias, step, limit, cond_alu->op, bit_size,
 517                           induction_base_type, initial,
 518                           limit_rhs, invert_cond)) {
 519          return iter_bias > 0 ? iter_bias - trip_offset : iter_bias;
 520       }
 521    }
 522
 523    return -1;
 524 }
 525
 526 /* Run through each of the terminators of the loop and try to infer a possible
 527  * trip-count. We need to check them all, and set the lowest trip-count as the
 528  * trip-count of our loop. If one of the terminators has an undecidable
 529  * trip-count we can not safely assume anything about the duration of the
 530  * loop.
 531  */
 532 static void
 533 find_trip_count(loop_info_state *state)
 534 {
 535    bool trip_count_known = true;
 536    nir_loop_terminator *limiting_terminator = NULL;
 537    int min_trip_count = -1;
 538
 539    list_for_each_entry(nir_loop_terminator, terminator,
 540                        &state->loop->info->loop_terminator_list,
 541                        loop_terminator_link) {
 542
 543       if (terminator->conditional_instr->type != nir_instr_type_alu) {
 544          /* If we get here the loop is dead and will get cleaned up by the
 545           * nir_opt_dead_cf pass.
 546           */
 547          trip_count_known = false;
 548          continue;
 549       }
 550
 551       nir_alu_instr *alu = nir_instr_as_alu(terminator->conditional_instr);
 552       nir_loop_variable *basic_ind = NULL;
 553       nir_loop_variable *limit = NULL;
 554       bool limit_rhs = true;
 555
 556       switch (alu->op) {
 557       case nir_op_fge:      case nir_op_ige:      case nir_op_uge:
 558       case nir_op_flt:      case nir_op_ilt:      case nir_op_ult:
 559       case nir_op_feq:      case nir_op_ieq:
 560       case nir_op_fne:      case nir_op_ine:
 561
 562          /* We assume that the limit is the "right" operand */
 563          basic_ind = get_loop_var(alu->src[0].src.ssa, state);
 564          limit = get_loop_var(alu->src[1].src.ssa, state);
 565
 566          if (basic_ind->type != basic_induction) {
 567             /* We had it the wrong way, flip things around */
 568             basic_ind = get_loop_var(alu->src[1].src.ssa, state);
 569             limit = get_loop_var(alu->src[0].src.ssa, state);
 570             limit_rhs = false;
 571          }
 572
 573          /* The comparison has to have a basic induction variable
 574           * and a constant for us to be able to find trip counts
 575           */
 576          if (basic_ind->type != basic_induction || !is_var_constant(limit)) {
 577             trip_count_known = false;
 578             continue;
 579          }
 580
 581          /* We have determined that we have the following constants:
 582           * (With the typical int i = 0; i < x; i++; as an example)
 583           *    - Upper limit.
 584           *    - Starting value
 585           *    - Step / iteration size
 586           * Thats all thats needed to calculate the trip-count
 587           */
 588
 589          nir_const_value initial_val =
 590             nir_instr_as_load_const(basic_ind->ind->def_outside_loop->
 591                                        def->parent_instr)->value;
 592
 593          nir_const_value step_val =
 594             nir_instr_as_load_const(basic_ind->ind->invariant->def->
 595                                        parent_instr)->value;
 596
 597          nir_const_value limit_val =
 598             nir_instr_as_load_const(limit->def->parent_instr)->value;
 599
 600          int iterations = calculate_iterations(&initial_val, &step_val,
 601                                                &limit_val,
 602                                                basic_ind->ind->alu_def, alu,
 603                                                limit_rhs,
 604                                                terminator->continue_from_then);
 605
 606          /* Where we not able to calculate the iteration count */
 607          if (iterations == -1) {
 608             trip_count_known = false;
 609             continue;
 610          }
 611
 612          /* If this is the first run or we have found a smaller amount of
 613           * iterations than previously (we have identified a more limiting
 614           * terminator) set the trip count and limiting terminator.
 615           */
 616          if (min_trip_count == -1 || iterations < min_trip_count) {
 617             min_trip_count = iterations;
 618             limiting_terminator = terminator;
 619          }
 620          break;
 621
 622       default:
 623          trip_count_known = false;
 624       }
 625    }
 626
 627    state->loop->info->is_trip_count_known = trip_count_known;
 628    if (min_trip_count > -1)
 629       state->loop->info->trip_count = min_trip_count;
 630    state->loop->info->limiting_terminator = limiting_terminator;
 631 }
 632
 633 /* Checks if we should force the loop to be unrolled regardless of size
 634  * due to array access heuristics.
 635  */
 636 static bool
 637 force_unroll_array_access(loop_info_state *state, nir_shader *ns,
 638                           nir_deref_var *variable)
 639 {
 640    nir_deref *tail = &variable->deref;
 641
 642    while (tail->child != NULL) {
 643       tail = tail->child;
 644
 645       if (tail->deref_type == nir_deref_type_array) {
 646
 647          nir_deref_array *deref_array = nir_deref_as_array(tail);
 648          if (deref_array->deref_array_type != nir_deref_array_type_indirect)
 649             continue;
 650
 651          nir_loop_variable *array_index =
 652             get_loop_var(deref_array->indirect.ssa, state);
 653
 654          if (array_index->type != basic_induction)
 655             continue;
 656
 657          /* If an array is indexed by a loop induction variable, and the
 658           * array size is exactly the number of loop iterations, this is
 659           * probably a simple for-loop trying to access each element in
 660           * turn; the application may expect it to be unrolled.
 661           */
 662          if (glsl_get_length(variable->deref.type) ==
 663              state->loop->info->trip_count) {
 664             state->loop->info->force_unroll = true;
 665             return state->loop->info->force_unroll;
 666          }
 667
 668          if (variable->var->data.mode & state->indirect_mask) {
 669             state->loop->info->force_unroll = true;
 670             return state->loop->info->force_unroll;
 671          }
 672       }
 673    }
 674
 675    return false;
 676 }
 677
 678 static bool
 679 force_unroll_heuristics(loop_info_state *state, nir_shader *ns,
 680                         nir_block *block)
 681 {
 682    nir_foreach_instr(instr, block) {
 683       if (instr->type != nir_instr_type_intrinsic)
 684          continue;
 685
 686       nir_intrinsic_instr *intrin = nir_instr_as_intrinsic(instr);
 687
 688       /* Check for arrays variably-indexed by a loop induction variable.
 689        * Unrolling the loop may convert that access into constant-indexing.
 690        */
 691       if (intrin->intrinsic == nir_intrinsic_load_var ||
 692           intrin->intrinsic == nir_intrinsic_store_var ||
 693           intrin->intrinsic == nir_intrinsic_copy_var) {
 694          unsigned num_vars =
 695             nir_intrinsic_infos[intrin->intrinsic].num_variables;
 696          for (unsigned i = 0; i < num_vars; i++) {
 697             if (force_unroll_array_access(state, ns, intrin->variables[i]))
 698                return true;
 699          }
 700       }
 701    }
 702
 703    return false;
 704 }
 705
 706 static void
 707 get_loop_info(loop_info_state *state, nir_function_impl *impl)
 708 {
 709    /* Initialize all variables to "outside_loop". This also marks defs
 710     * invariant and constant if they are nir_instr_type_load_consts
 711     */
 712    nir_foreach_block(block, impl) {
 713       nir_foreach_instr(instr, block)
 714          nir_foreach_ssa_def(instr, initialize_ssa_def, state);
 715    }
 716
 717    /* Add all entries in the outermost part of the loop to the processing list
 718     * Mark the entries in conditionals or in nested loops accordingly
 719     */
 720    foreach_list_typed_safe(nir_cf_node, node, node, &state->loop->body) {
 721       switch (node->type) {
 722
 723       case nir_cf_node_block:
 724          init_loop_block(nir_cf_node_as_block(node), state, false);
 725          break;
 726
 727       case nir_cf_node_if:
 728          nir_foreach_block_in_cf_node(block, node)
 729             init_loop_block(block, state, true);
 730          break;
 731
 732       case nir_cf_node_loop:
 733          nir_foreach_block_in_cf_node(block, node) {
 734             init_loop_block(block, state, true);
 735          }
 736          break;
 737
 738       case nir_cf_node_function:
 739          break;
 740       }
 741    }
 742
 743    /* Induction analysis needs invariance information so get that first */
 744    compute_invariance_information(state);
 745
 746    /* We have invariance information so try to find induction variables */
 747    if (!compute_induction_information(state))
 748       return;
 749
 750    /* Try to find all simple terminators of the loop. If we can't find any,
 751     * or we find possible terminators that have side effects then bail.
 752     */
 753    if (!find_loop_terminators(state)) {
 754       list_for_each_entry_safe(nir_loop_terminator, terminator,
 755                                &state->loop->info->loop_terminator_list,
 756                                loop_terminator_link) {
 757          list_del(&terminator->loop_terminator_link);
 758          ralloc_free(terminator);
 759       }
 760       return;
 761    }
 762
 763    /* Run through each of the terminators and try to compute a trip-count */
 764    find_trip_count(state);
 765
 766    nir_shader *ns = impl->function->shader;
 767    foreach_list_typed_safe(nir_cf_node, node, node, &state->loop->body) {
 768       if (node->type == nir_cf_node_block) {
 769          if (force_unroll_heuristics(state, ns, nir_cf_node_as_block(node)))
 770             break;
 771       } else {
 772          nir_foreach_block_in_cf_node(block, node) {
 773             if (force_unroll_heuristics(state, ns, block))
 774                break;
 775          }
 776       }
 777    }
 778 }
 779
 780 static loop_info_state *
 781 initialize_loop_info_state(nir_loop *loop, void *mem_ctx,
 782                            nir_function_impl *impl)
 783 {
 784    loop_info_state *state = rzalloc(mem_ctx, loop_info_state);
 785    state->loop_vars = rzalloc_array(mem_ctx, nir_loop_variable,
 786                                     impl->ssa_alloc);
 787    state->loop = loop;
 788
 789    list_inithead(&state->process_list);
 790
 791    if (loop->info)
 792      ralloc_free(loop->info);
 793
 794    loop->info = rzalloc(loop, nir_loop_info);
 795
 796    list_inithead(&loop->info->loop_terminator_list);
 797
 798    return state;
 799 }
 800
 801 static void
 802 process_loops(nir_cf_node *cf_node, nir_variable_mode indirect_mask)
 803 {
 804    switch (cf_node->type) {
 805    case nir_cf_node_block:
 806       return;
 807    case nir_cf_node_if: {
 808       nir_if *if_stmt = nir_cf_node_as_if(cf_node);
 809       foreach_list_typed(nir_cf_node, nested_node, node, &if_stmt->then_list)
 810          process_loops(nested_node, indirect_mask);
 811       foreach_list_typed(nir_cf_node, nested_node, node, &if_stmt->else_list)
 812          process_loops(nested_node, indirect_mask);
 813       return;
 814    }
 815    case nir_cf_node_loop: {
 816       nir_loop *loop = nir_cf_node_as_loop(cf_node);
 817       foreach_list_typed(nir_cf_node, nested_node, node, &loop->body)
 818          process_loops(nested_node, indirect_mask);
 819       break;
 820    }
 821    default:
 822       unreachable("unknown cf node type");
 823    }
 824
 825    nir_loop *loop = nir_cf_node_as_loop(cf_node);
 826    nir_function_impl *impl = nir_cf_node_get_function(cf_node);
 827    void *mem_ctx = ralloc_context(NULL);
 828
 829    loop_info_state *state = initialize_loop_info_state(loop, mem_ctx, impl);
 830    state->indirect_mask = indirect_mask;
 831
 832    get_loop_info(state, impl);
 833
 834    ralloc_free(mem_ctx);
 835 }
 836
 837 void
 838 nir_loop_analyze_impl(nir_function_impl *impl,
 839                       nir_variable_mode indirect_mask)
 840 {
 841    nir_index_ssa_defs(impl);
 842    foreach_list_typed(nir_cf_node, node, node, &impl->body)
 843       process_loops(node, indirect_mask);
 844 }