• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 *
get_loop_var(nir_ssa_def * value,loop_info_state * state)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
init_loop_def(nir_ssa_def * def,void * void_init_loop_state)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
init_loop_block(nir_block * block,loop_info_state * state,bool in_control_flow)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
is_var_alu(nir_loop_variable * var)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
is_var_constant(nir_loop_variable * var)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
is_var_phi(nir_loop_variable * var)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
mark_invariant(nir_ssa_def * def,loop_info_state * state)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
compute_invariance_information(loop_info_state * state)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
compute_induction_information(loop_info_state * state)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 phi's 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
initialize_ssa_def(nir_ssa_def * def,void * void_state)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
ends_in_break(nir_block * block)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
find_loop_terminators(loop_info_state * state)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
get_iteration(nir_op cond_op,nir_const_value * initial,nir_const_value * step,nir_const_value * limit,nir_alu_instr * alu)361 get_iteration(nir_op cond_op, nir_const_value *initial, nir_const_value *step,
362               nir_const_value *limit, nir_alu_instr *alu)
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
test_iterations(int32_t iter_int,nir_const_value * step,nir_const_value * limit,nir_op cond_op,unsigned bit_size,nir_alu_type induction_base_type,nir_const_value * initial,bool limit_rhs,bool invert_cond)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
calculate_iterations(nir_const_value * initial,nir_const_value * step,nir_const_value * limit,nir_loop_variable * alu_def,nir_alu_instr * cond_alu,bool limit_rhs,bool invert_cond)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, alu);
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
find_trip_count(loop_info_state * state)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
force_unroll_array_access(loop_info_state * state,nir_shader * ns,nir_deref_var * variable)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
force_unroll_heuristics(loop_info_state * state,nir_shader * ns,nir_block * block)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
get_loop_info(loop_info_state * state,nir_function_impl * impl)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_const's
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 *
initialize_loop_info_state(nir_loop * loop,void * mem_ctx,nir_function_impl * impl)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
process_loops(nir_cf_node * cf_node,nir_variable_mode indirect_mask)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
nir_loop_analyze_impl(nir_function_impl * impl,nir_variable_mode indirect_mask)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 }
845