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