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 #include "util/bitset.h"
28
29 typedef enum {
30 undefined,
31 invariant,
32 not_invariant,
33 basic_induction
34 } nir_loop_variable_type;
35
36 typedef struct nir_basic_induction_var {
37 nir_alu_instr *alu; /* The def of the alu-operation */
38 nir_ssa_def *def_outside_loop; /* The phi-src outside the loop */
39 } nir_basic_induction_var;
40
41 typedef struct {
42 /* A link for the work list */
43 struct list_head process_link;
44
45 bool in_loop;
46
47 /* The ssa_def associated with this info */
48 nir_ssa_def *def;
49
50 /* The type of this ssa_def */
51 nir_loop_variable_type type;
52
53 /* If this is of type basic_induction */
54 struct nir_basic_induction_var *ind;
55
56 /* True if variable is in an if branch */
57 bool in_if_branch;
58
59 /* True if variable is in a nested loop */
60 bool in_nested_loop;
61
62 /* Could be a basic_induction if following uniforms are inlined */
63 nir_src *init_src;
64 nir_alu_src *update_src;
65 } nir_loop_variable;
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 BITSET_WORD *loop_vars_init;
74
75 /* A list of the loop_vars to analyze */
76 struct list_head process_list;
77
78 nir_variable_mode indirect_mask;
79
80 } loop_info_state;
81
82 static nir_loop_variable *
get_loop_var(nir_ssa_def * value,loop_info_state * state)83 get_loop_var(nir_ssa_def *value, loop_info_state *state)
84 {
85 nir_loop_variable *var = &(state->loop_vars[value->index]);
86
87 if (!BITSET_TEST(state->loop_vars_init, value->index)) {
88 var->in_loop = false;
89 var->def = value;
90 var->in_if_branch = false;
91 var->in_nested_loop = false;
92 var->init_src = NULL;
93 var->update_src = NULL;
94 if (value->parent_instr->type == nir_instr_type_load_const)
95 var->type = invariant;
96 else
97 var->type = undefined;
98
99 BITSET_SET(state->loop_vars_init, value->index);
100 }
101
102 return var;
103 }
104
105 typedef struct {
106 loop_info_state *state;
107 bool in_if_branch;
108 bool in_nested_loop;
109 } init_loop_state;
110
111 static bool
init_loop_def(nir_ssa_def * def,void * void_init_loop_state)112 init_loop_def(nir_ssa_def *def, void *void_init_loop_state)
113 {
114 init_loop_state *loop_init_state = void_init_loop_state;
115 nir_loop_variable *var = get_loop_var(def, loop_init_state->state);
116
117 if (loop_init_state->in_nested_loop) {
118 var->in_nested_loop = true;
119 } else if (loop_init_state->in_if_branch) {
120 var->in_if_branch = true;
121 } else {
122 /* Add to the tail of the list. That way we start at the beginning of
123 * the defs in the loop instead of the end when walking the list. This
124 * means less recursive calls. Only add defs that are not in nested
125 * loops or conditional blocks.
126 */
127 list_addtail(&var->process_link, &loop_init_state->state->process_list);
128 }
129
130 var->in_loop = true;
131
132 return true;
133 }
134
135 /** Calculate an estimated cost in number of instructions
136 *
137 * We do this so that we don't unroll loops which will later get massively
138 * inflated due to int64 or fp64 lowering. The estimates provided here don't
139 * have to be massively accurate; they just have to be good enough that loop
140 * unrolling doesn't cause things to blow up too much.
141 */
142 static unsigned
instr_cost(nir_instr * instr,const nir_shader_compiler_options * options)143 instr_cost(nir_instr *instr, const nir_shader_compiler_options *options)
144 {
145 if (instr->type == nir_instr_type_intrinsic ||
146 instr->type == nir_instr_type_tex)
147 return 1;
148
149 if (instr->type != nir_instr_type_alu)
150 return 0;
151
152 nir_alu_instr *alu = nir_instr_as_alu(instr);
153 const nir_op_info *info = &nir_op_infos[alu->op];
154 unsigned cost = 1;
155
156 if (alu->op == nir_op_flrp) {
157 if ((options->lower_flrp16 && nir_dest_bit_size(alu->dest.dest) == 16) ||
158 (options->lower_flrp32 && nir_dest_bit_size(alu->dest.dest) == 32) ||
159 (options->lower_flrp64 && nir_dest_bit_size(alu->dest.dest) == 64))
160 cost *= 3;
161 }
162
163 /* Assume everything 16 or 32-bit is cheap.
164 *
165 * There are no 64-bit ops that don't have a 64-bit thing as their
166 * destination or first source.
167 */
168 if (nir_dest_bit_size(alu->dest.dest) < 64 &&
169 nir_src_bit_size(alu->src[0].src) < 64)
170 return cost;
171
172 bool is_fp64 = nir_dest_bit_size(alu->dest.dest) == 64 &&
173 nir_alu_type_get_base_type(info->output_type) == nir_type_float;
174 for (unsigned i = 0; i < info->num_inputs; i++) {
175 if (nir_src_bit_size(alu->src[i].src) == 64 &&
176 nir_alu_type_get_base_type(info->input_types[i]) == nir_type_float)
177 is_fp64 = true;
178 }
179
180 if (is_fp64) {
181 /* If it's something lowered normally, it's expensive. */
182 if (options->lower_doubles_options &
183 nir_lower_doubles_op_to_options_mask(alu->op))
184 cost *= 20;
185
186 /* If it's full software, it's even more expensive */
187 if (options->lower_doubles_options & nir_lower_fp64_full_software)
188 cost *= 100;
189
190 return cost;
191 } else {
192 if (options->lower_int64_options &
193 nir_lower_int64_op_to_options_mask(alu->op)) {
194 /* These require a doing the division algorithm. */
195 if (alu->op == nir_op_idiv || alu->op == nir_op_udiv ||
196 alu->op == nir_op_imod || alu->op == nir_op_umod ||
197 alu->op == nir_op_irem)
198 return cost * 100;
199
200 /* Other int64 lowering isn't usually all that expensive */
201 return cost * 5;
202 }
203
204 return cost;
205 }
206 }
207
208 static bool
init_loop_block(nir_block * block,loop_info_state * state,bool in_if_branch,bool in_nested_loop,const nir_shader_compiler_options * options)209 init_loop_block(nir_block *block, loop_info_state *state,
210 bool in_if_branch, bool in_nested_loop,
211 const nir_shader_compiler_options *options)
212 {
213 init_loop_state init_state = {.in_if_branch = in_if_branch,
214 .in_nested_loop = in_nested_loop,
215 .state = state };
216
217 nir_foreach_instr(instr, block) {
218 state->loop->info->instr_cost += instr_cost(instr, options);
219 nir_foreach_ssa_def(instr, init_loop_def, &init_state);
220 }
221
222 return true;
223 }
224
225 static inline bool
is_var_alu(nir_loop_variable * var)226 is_var_alu(nir_loop_variable *var)
227 {
228 return var->def->parent_instr->type == nir_instr_type_alu;
229 }
230
231 static inline bool
is_var_phi(nir_loop_variable * var)232 is_var_phi(nir_loop_variable *var)
233 {
234 return var->def->parent_instr->type == nir_instr_type_phi;
235 }
236
237 static inline bool
mark_invariant(nir_ssa_def * def,loop_info_state * state)238 mark_invariant(nir_ssa_def *def, loop_info_state *state)
239 {
240 nir_loop_variable *var = get_loop_var(def, state);
241
242 if (var->type == invariant)
243 return true;
244
245 if (!var->in_loop) {
246 var->type = invariant;
247 return true;
248 }
249
250 if (var->type == not_invariant)
251 return false;
252
253 if (is_var_alu(var)) {
254 nir_alu_instr *alu = nir_instr_as_alu(def->parent_instr);
255
256 for (unsigned i = 0; i < nir_op_infos[alu->op].num_inputs; i++) {
257 if (!mark_invariant(alu->src[i].src.ssa, state)) {
258 var->type = not_invariant;
259 return false;
260 }
261 }
262 var->type = invariant;
263 return true;
264 }
265
266 /* Phis shouldn't be invariant except if one operand is invariant, and the
267 * other is the phi itself. These should be removed by opt_remove_phis.
268 * load_consts are already set to invariant and constant during init,
269 * and so should return earlier. Remaining op_codes are set undefined.
270 */
271 var->type = not_invariant;
272 return false;
273 }
274
275 static void
compute_invariance_information(loop_info_state * state)276 compute_invariance_information(loop_info_state *state)
277 {
278 /* An expression is invariant in a loop L if:
279 * (base cases)
280 * – it’s a constant
281 * – it’s a variable use, all of whose single defs are outside of L
282 * (inductive cases)
283 * – it’s a pure computation all of whose args are loop invariant
284 * – it’s a variable use whose single reaching def, and the
285 * rhs of that def is loop-invariant
286 */
287 list_for_each_entry_safe(nir_loop_variable, var, &state->process_list,
288 process_link) {
289 assert(!var->in_if_branch && !var->in_nested_loop);
290
291 if (mark_invariant(var->def, state))
292 list_del(&var->process_link);
293 }
294 }
295
296 /* If all of the instruction sources point to identical ALU instructions (as
297 * per nir_instrs_equal), return one of the ALU instructions. Otherwise,
298 * return NULL.
299 */
300 static nir_alu_instr *
phi_instr_as_alu(nir_phi_instr * phi)301 phi_instr_as_alu(nir_phi_instr *phi)
302 {
303 nir_alu_instr *first = NULL;
304 nir_foreach_phi_src(src, phi) {
305 assert(src->src.is_ssa);
306 if (src->src.ssa->parent_instr->type != nir_instr_type_alu)
307 return NULL;
308
309 nir_alu_instr *alu = nir_instr_as_alu(src->src.ssa->parent_instr);
310 if (first == NULL) {
311 first = alu;
312 } else {
313 if (!nir_instrs_equal(&first->instr, &alu->instr))
314 return NULL;
315 }
316 }
317
318 return first;
319 }
320
321 static bool
alu_src_has_identity_swizzle(nir_alu_instr * alu,unsigned src_idx)322 alu_src_has_identity_swizzle(nir_alu_instr *alu, unsigned src_idx)
323 {
324 assert(nir_op_infos[alu->op].input_sizes[src_idx] == 0);
325 assert(alu->dest.dest.is_ssa);
326 for (unsigned i = 0; i < alu->dest.dest.ssa.num_components; i++) {
327 if (alu->src[src_idx].swizzle[i] != i)
328 return false;
329 }
330
331 return true;
332 }
333
334 static bool
is_only_uniform_src(nir_src * src)335 is_only_uniform_src(nir_src *src)
336 {
337 if (!src->is_ssa)
338 return false;
339
340 nir_instr *instr = src->ssa->parent_instr;
341
342 switch (instr->type) {
343 case nir_instr_type_alu: {
344 /* Return true if all sources return true. */
345 nir_alu_instr *alu = nir_instr_as_alu(instr);
346 for (unsigned i = 0; i < nir_op_infos[alu->op].num_inputs; i++) {
347 if (!is_only_uniform_src(&alu->src[i].src))
348 return false;
349 }
350 return true;
351 }
352
353 case nir_instr_type_intrinsic: {
354 nir_intrinsic_instr *inst = nir_instr_as_intrinsic(instr);
355 /* current uniform inline only support load ubo */
356 return inst->intrinsic == nir_intrinsic_load_ubo;
357 }
358
359 case nir_instr_type_load_const:
360 /* Always return true for constants. */
361 return true;
362
363 default:
364 return false;
365 }
366 }
367
368 static bool
compute_induction_information(loop_info_state * state)369 compute_induction_information(loop_info_state *state)
370 {
371 bool found_induction_var = false;
372 unsigned num_induction_vars = 0;
373
374 list_for_each_entry_safe(nir_loop_variable, var, &state->process_list,
375 process_link) {
376
377 /* It can't be an induction variable if it is invariant. Invariants and
378 * things in nested loops or conditionals should have been removed from
379 * the list by compute_invariance_information().
380 */
381 assert(!var->in_if_branch && !var->in_nested_loop &&
382 var->type != invariant);
383
384 /* We are only interested in checking phis for the basic induction
385 * variable case as its simple to detect. All basic induction variables
386 * have a phi node
387 */
388 if (!is_var_phi(var))
389 continue;
390
391 nir_phi_instr *phi = nir_instr_as_phi(var->def->parent_instr);
392 nir_basic_induction_var *biv = rzalloc(state, nir_basic_induction_var);
393
394 nir_src *init_src = NULL;
395 nir_loop_variable *alu_src_var = NULL;
396 nir_foreach_phi_src(src, phi) {
397 nir_loop_variable *src_var = get_loop_var(src->src.ssa, state);
398
399 /* If one of the sources is in an if branch or nested loop then don't
400 * attempt to go any further.
401 */
402 if (src_var->in_if_branch || src_var->in_nested_loop)
403 break;
404
405 /* Detect inductions variables that are incremented in both branches
406 * of an unnested if rather than in a loop block.
407 */
408 if (is_var_phi(src_var)) {
409 nir_phi_instr *src_phi =
410 nir_instr_as_phi(src_var->def->parent_instr);
411 nir_alu_instr *src_phi_alu = phi_instr_as_alu(src_phi);
412 if (src_phi_alu) {
413 src_var = get_loop_var(&src_phi_alu->dest.dest.ssa, state);
414 if (!src_var->in_if_branch)
415 break;
416 }
417 }
418
419 if (!src_var->in_loop && !biv->def_outside_loop) {
420 biv->def_outside_loop = src_var->def;
421 init_src = &src->src;
422 } else if (is_var_alu(src_var) && !biv->alu) {
423 alu_src_var = src_var;
424 nir_alu_instr *alu = nir_instr_as_alu(src_var->def->parent_instr);
425
426 /* Check for unsupported alu operations */
427 if (alu->op != nir_op_iadd && alu->op != nir_op_fadd)
428 break;
429
430 if (nir_op_infos[alu->op].num_inputs == 2) {
431 for (unsigned i = 0; i < 2; i++) {
432 /* Is one of the operands const or uniform, and the other the phi.
433 * The phi source can't be swizzled in any way.
434 */
435 if (alu->src[1-i].src.ssa == &phi->dest.ssa &&
436 alu_src_has_identity_swizzle(alu, 1 - i)) {
437 nir_src *src = &alu->src[i].src;
438 if (nir_src_is_const(*src))
439 biv->alu = alu;
440 else if (is_only_uniform_src(src)) {
441 /* Update value of induction variable is a statement
442 * contains only uniform and constant
443 */
444 var->update_src = alu->src + i;
445 biv->alu = alu;
446 }
447 }
448 }
449 }
450
451 if (!biv->alu)
452 break;
453 } else {
454 biv->alu = NULL;
455 break;
456 }
457 }
458
459 if (biv->alu && biv->def_outside_loop) {
460 nir_instr *inst = biv->def_outside_loop->parent_instr;
461 if (inst->type == nir_instr_type_load_const) {
462 /* Initial value of induction variable is a constant */
463 if (var->update_src) {
464 alu_src_var->update_src = var->update_src;
465 ralloc_free(biv);
466 } else {
467 alu_src_var->type = basic_induction;
468 alu_src_var->ind = biv;
469 var->type = basic_induction;
470 var->ind = biv;
471
472 found_induction_var = true;
473 }
474 num_induction_vars += 2;
475 } else if (is_only_uniform_src(init_src)) {
476 /* Initial value of induction variable is a uniform */
477 var->init_src = init_src;
478
479 alu_src_var->init_src = var->init_src;
480 alu_src_var->update_src = var->update_src;
481
482 num_induction_vars += 2;
483 ralloc_free(biv);
484 } else {
485 var->update_src = NULL;
486 ralloc_free(biv);
487 }
488 } else {
489 var->update_src = NULL;
490 ralloc_free(biv);
491 }
492 }
493
494 nir_loop_info *info = state->loop->info;
495 ralloc_free(info->induction_vars);
496 info->num_induction_vars = 0;
497
498 /* record induction variables into nir_loop_info */
499 if (num_induction_vars) {
500 info->induction_vars = ralloc_array(info, nir_loop_induction_variable,
501 num_induction_vars);
502
503 list_for_each_entry(nir_loop_variable, var, &state->process_list,
504 process_link) {
505 if (var->type == basic_induction || var->init_src || var->update_src) {
506 nir_loop_induction_variable *ivar =
507 &info->induction_vars[info->num_induction_vars++];
508 ivar->def = var->def;
509 ivar->init_src = var->init_src;
510 ivar->update_src = var->update_src;
511 }
512 }
513 /* don't overflow */
514 assert(info->num_induction_vars <= num_induction_vars);
515 }
516
517 return found_induction_var;
518 }
519
520 static bool
find_loop_terminators(loop_info_state * state)521 find_loop_terminators(loop_info_state *state)
522 {
523 bool success = false;
524 foreach_list_typed_safe(nir_cf_node, node, node, &state->loop->body) {
525 if (node->type == nir_cf_node_if) {
526 nir_if *nif = nir_cf_node_as_if(node);
527
528 nir_block *break_blk = NULL;
529 nir_block *continue_from_blk = NULL;
530 bool continue_from_then = true;
531
532 nir_block *last_then = nir_if_last_then_block(nif);
533 nir_block *last_else = nir_if_last_else_block(nif);
534 if (nir_block_ends_in_break(last_then)) {
535 break_blk = last_then;
536 continue_from_blk = last_else;
537 continue_from_then = false;
538 } else if (nir_block_ends_in_break(last_else)) {
539 break_blk = last_else;
540 continue_from_blk = last_then;
541 }
542
543 /* If there is a break then we should find a terminator. If we can
544 * not find a loop terminator, but there is a break-statement then
545 * we should return false so that we do not try to find trip-count
546 */
547 if (!nir_is_trivial_loop_if(nif, break_blk)) {
548 state->loop->info->complex_loop = true;
549 return false;
550 }
551
552 /* Continue if the if contained no jumps at all */
553 if (!break_blk)
554 continue;
555
556 if (nif->condition.ssa->parent_instr->type == nir_instr_type_phi) {
557 state->loop->info->complex_loop = true;
558 return false;
559 }
560
561 nir_loop_terminator *terminator =
562 rzalloc(state->loop->info, nir_loop_terminator);
563
564 list_addtail(&terminator->loop_terminator_link,
565 &state->loop->info->loop_terminator_list);
566
567 terminator->nif = nif;
568 terminator->break_block = break_blk;
569 terminator->continue_from_block = continue_from_blk;
570 terminator->continue_from_then = continue_from_then;
571 terminator->conditional_instr = nif->condition.ssa->parent_instr;
572
573 success = true;
574 }
575 }
576
577 return success;
578 }
579
580 /* This function looks for an array access within a loop that uses an
581 * induction variable for the array index. If found it returns the size of the
582 * array, otherwise 0 is returned. If we find an induction var we pass it back
583 * to the caller via array_index_out.
584 */
585 static unsigned
find_array_access_via_induction(loop_info_state * state,nir_deref_instr * deref,nir_loop_variable ** array_index_out)586 find_array_access_via_induction(loop_info_state *state,
587 nir_deref_instr *deref,
588 nir_loop_variable **array_index_out)
589 {
590 for (nir_deref_instr *d = deref; d; d = nir_deref_instr_parent(d)) {
591 if (d->deref_type != nir_deref_type_array)
592 continue;
593
594 assert(d->arr.index.is_ssa);
595 nir_loop_variable *array_index = get_loop_var(d->arr.index.ssa, state);
596
597 if (array_index->type != basic_induction)
598 continue;
599
600 if (array_index_out)
601 *array_index_out = array_index;
602
603 nir_deref_instr *parent = nir_deref_instr_parent(d);
604 if (glsl_type_is_array_or_matrix(parent->type)) {
605 return glsl_get_length(parent->type);
606 } else {
607 assert(glsl_type_is_vector(parent->type));
608 return glsl_get_vector_elements(parent->type);
609 }
610 }
611
612 return 0;
613 }
614
615 static bool
guess_loop_limit(loop_info_state * state,nir_const_value * limit_val,nir_ssa_scalar basic_ind)616 guess_loop_limit(loop_info_state *state, nir_const_value *limit_val,
617 nir_ssa_scalar basic_ind)
618 {
619 unsigned min_array_size = 0;
620
621 nir_foreach_block_in_cf_node(block, &state->loop->cf_node) {
622 nir_foreach_instr(instr, block) {
623 if (instr->type != nir_instr_type_intrinsic)
624 continue;
625
626 nir_intrinsic_instr *intrin = nir_instr_as_intrinsic(instr);
627
628 /* Check for arrays variably-indexed by a loop induction variable. */
629 if (intrin->intrinsic == nir_intrinsic_load_deref ||
630 intrin->intrinsic == nir_intrinsic_store_deref ||
631 intrin->intrinsic == nir_intrinsic_copy_deref) {
632
633 nir_loop_variable *array_idx = NULL;
634 unsigned array_size =
635 find_array_access_via_induction(state,
636 nir_src_as_deref(intrin->src[0]),
637 &array_idx);
638 if (array_idx && basic_ind.def == array_idx->def &&
639 (min_array_size == 0 || min_array_size > array_size)) {
640 /* Array indices are scalars */
641 assert(basic_ind.def->num_components == 1);
642 min_array_size = array_size;
643 }
644
645 if (intrin->intrinsic != nir_intrinsic_copy_deref)
646 continue;
647
648 array_size =
649 find_array_access_via_induction(state,
650 nir_src_as_deref(intrin->src[1]),
651 &array_idx);
652 if (array_idx && basic_ind.def == array_idx->def &&
653 (min_array_size == 0 || min_array_size > array_size)) {
654 /* Array indices are scalars */
655 assert(basic_ind.def->num_components == 1);
656 min_array_size = array_size;
657 }
658 }
659 }
660 }
661
662 if (min_array_size) {
663 *limit_val = nir_const_value_for_uint(min_array_size,
664 basic_ind.def->bit_size);
665 return true;
666 }
667
668 return false;
669 }
670
671 static bool
try_find_limit_of_alu(nir_ssa_scalar limit,nir_const_value * limit_val,nir_loop_terminator * terminator,loop_info_state * state)672 try_find_limit_of_alu(nir_ssa_scalar limit, nir_const_value *limit_val,
673 nir_loop_terminator *terminator, loop_info_state *state)
674 {
675 if (!nir_ssa_scalar_is_alu(limit))
676 return false;
677
678 nir_op limit_op = nir_ssa_scalar_alu_op(limit);
679 if (limit_op == nir_op_imin || limit_op == nir_op_fmin) {
680 for (unsigned i = 0; i < 2; i++) {
681 nir_ssa_scalar src = nir_ssa_scalar_chase_alu_src(limit, i);
682 if (nir_ssa_scalar_is_const(src)) {
683 *limit_val = nir_ssa_scalar_as_const_value(src);
684 terminator->exact_trip_count_unknown = true;
685 return true;
686 }
687 }
688 }
689
690 return false;
691 }
692
693 static nir_const_value
eval_const_unop(nir_op op,unsigned bit_size,nir_const_value src0,unsigned execution_mode)694 eval_const_unop(nir_op op, unsigned bit_size, nir_const_value src0,
695 unsigned execution_mode)
696 {
697 assert(nir_op_infos[op].num_inputs == 1);
698 nir_const_value dest;
699 nir_const_value *src[1] = { &src0 };
700 nir_eval_const_opcode(op, &dest, 1, bit_size, src, execution_mode);
701 return dest;
702 }
703
704 static nir_const_value
eval_const_binop(nir_op op,unsigned bit_size,nir_const_value src0,nir_const_value src1,unsigned execution_mode)705 eval_const_binop(nir_op op, unsigned bit_size,
706 nir_const_value src0, nir_const_value src1,
707 unsigned execution_mode)
708 {
709 assert(nir_op_infos[op].num_inputs == 2);
710 nir_const_value dest;
711 nir_const_value *src[2] = { &src0, &src1 };
712 nir_eval_const_opcode(op, &dest, 1, bit_size, src, execution_mode);
713 return dest;
714 }
715
716 static int32_t
get_iteration(nir_op cond_op,nir_const_value initial,nir_const_value step,nir_const_value limit,unsigned bit_size,unsigned execution_mode)717 get_iteration(nir_op cond_op, nir_const_value initial, nir_const_value step,
718 nir_const_value limit, unsigned bit_size,
719 unsigned execution_mode)
720 {
721 nir_const_value span, iter;
722
723 switch (cond_op) {
724 case nir_op_ige:
725 case nir_op_ilt:
726 case nir_op_ieq:
727 case nir_op_ine:
728 span = eval_const_binop(nir_op_isub, bit_size, limit, initial,
729 execution_mode);
730 iter = eval_const_binop(nir_op_idiv, bit_size, span, step,
731 execution_mode);
732 break;
733
734 case nir_op_uge:
735 case nir_op_ult:
736 span = eval_const_binop(nir_op_isub, bit_size, limit, initial,
737 execution_mode);
738 iter = eval_const_binop(nir_op_udiv, bit_size, span, step,
739 execution_mode);
740 break;
741
742 case nir_op_fge:
743 case nir_op_flt:
744 case nir_op_feq:
745 case nir_op_fneu:
746 span = eval_const_binop(nir_op_fsub, bit_size, limit, initial,
747 execution_mode);
748 iter = eval_const_binop(nir_op_fdiv, bit_size, span,
749 step, execution_mode);
750 iter = eval_const_unop(nir_op_f2i64, bit_size, iter, execution_mode);
751 break;
752
753 default:
754 return -1;
755 }
756
757 uint64_t iter_u64 = nir_const_value_as_uint(iter, bit_size);
758 return iter_u64 > INT_MAX ? -1 : (int)iter_u64;
759 }
760
761 static bool
will_break_on_first_iteration(nir_const_value step,nir_alu_type induction_base_type,unsigned trip_offset,nir_op cond_op,unsigned bit_size,nir_const_value initial,nir_const_value limit,bool limit_rhs,bool invert_cond,unsigned execution_mode)762 will_break_on_first_iteration(nir_const_value step,
763 nir_alu_type induction_base_type,
764 unsigned trip_offset,
765 nir_op cond_op, unsigned bit_size,
766 nir_const_value initial,
767 nir_const_value limit,
768 bool limit_rhs, bool invert_cond,
769 unsigned execution_mode)
770 {
771 if (trip_offset == 1) {
772 nir_op add_op;
773 switch (induction_base_type) {
774 case nir_type_float:
775 add_op = nir_op_fadd;
776 break;
777 case nir_type_int:
778 case nir_type_uint:
779 add_op = nir_op_iadd;
780 break;
781 default:
782 unreachable("Unhandled induction variable base type!");
783 }
784
785 initial = eval_const_binop(add_op, bit_size, initial, step,
786 execution_mode);
787 }
788
789 nir_const_value *src[2];
790 src[limit_rhs ? 0 : 1] = &initial;
791 src[limit_rhs ? 1 : 0] = &limit;
792
793 /* Evaluate the loop exit condition */
794 nir_const_value result;
795 nir_eval_const_opcode(cond_op, &result, 1, bit_size, src, execution_mode);
796
797 return invert_cond ? !result.b : result.b;
798 }
799
800 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,unsigned execution_mode)801 test_iterations(int32_t iter_int, nir_const_value step,
802 nir_const_value limit, nir_op cond_op, unsigned bit_size,
803 nir_alu_type induction_base_type,
804 nir_const_value initial, bool limit_rhs, bool invert_cond,
805 unsigned execution_mode)
806 {
807 assert(nir_op_infos[cond_op].num_inputs == 2);
808
809 nir_const_value iter_src;
810 nir_op mul_op;
811 nir_op add_op;
812 switch (induction_base_type) {
813 case nir_type_float:
814 iter_src = nir_const_value_for_float(iter_int, bit_size);
815 mul_op = nir_op_fmul;
816 add_op = nir_op_fadd;
817 break;
818 case nir_type_int:
819 case nir_type_uint:
820 iter_src = nir_const_value_for_int(iter_int, bit_size);
821 mul_op = nir_op_imul;
822 add_op = nir_op_iadd;
823 break;
824 default:
825 unreachable("Unhandled induction variable base type!");
826 }
827
828 /* Multiple the iteration count we are testing by the number of times we
829 * step the induction variable each iteration.
830 */
831 nir_const_value mul_result =
832 eval_const_binop(mul_op, bit_size, iter_src, step, execution_mode);
833
834 /* Add the initial value to the accumulated induction variable total */
835 nir_const_value add_result =
836 eval_const_binop(add_op, bit_size, mul_result, initial, execution_mode);
837
838 nir_const_value *src[2];
839 src[limit_rhs ? 0 : 1] = &add_result;
840 src[limit_rhs ? 1 : 0] = &limit;
841
842 /* Evaluate the loop exit condition */
843 nir_const_value result;
844 nir_eval_const_opcode(cond_op, &result, 1, bit_size, src, execution_mode);
845
846 return invert_cond ? !result.b : result.b;
847 }
848
849 static int
calculate_iterations(nir_const_value initial,nir_const_value step,nir_const_value limit,nir_alu_instr * alu,nir_ssa_scalar cond,nir_op alu_op,bool limit_rhs,bool invert_cond,unsigned execution_mode)850 calculate_iterations(nir_const_value initial, nir_const_value step,
851 nir_const_value limit, nir_alu_instr *alu,
852 nir_ssa_scalar cond, nir_op alu_op, bool limit_rhs,
853 bool invert_cond, unsigned execution_mode)
854 {
855 /* nir_op_isub should have been lowered away by this point */
856 assert(alu->op != nir_op_isub);
857
858 /* Make sure the alu type for our induction variable is compatible with the
859 * conditional alus input type. If its not something has gone really wrong.
860 */
861 nir_alu_type induction_base_type =
862 nir_alu_type_get_base_type(nir_op_infos[alu->op].output_type);
863 if (induction_base_type == nir_type_int || induction_base_type == nir_type_uint) {
864 assert(nir_alu_type_get_base_type(nir_op_infos[alu_op].input_types[1]) == nir_type_int ||
865 nir_alu_type_get_base_type(nir_op_infos[alu_op].input_types[1]) == nir_type_uint);
866 } else {
867 assert(nir_alu_type_get_base_type(nir_op_infos[alu_op].input_types[0]) ==
868 induction_base_type);
869 }
870
871 /* Only variable with these update ops were marked as induction. */
872 assert(alu->op == nir_op_iadd || alu->op == nir_op_fadd);
873
874 /* do-while loops can increment the starting value before the condition is
875 * checked. e.g.
876 *
877 * do {
878 * ndx++;
879 * } while (ndx < 3);
880 *
881 * Here we check if the induction variable is used directly by the loop
882 * condition and if so we assume we need to step the initial value.
883 */
884 unsigned trip_offset = 0;
885 nir_alu_instr *cond_alu = nir_instr_as_alu(cond.def->parent_instr);
886 if (cond_alu->src[0].src.ssa == &alu->dest.dest.ssa ||
887 cond_alu->src[1].src.ssa == &alu->dest.dest.ssa) {
888 trip_offset = 1;
889 }
890
891 assert(nir_src_bit_size(alu->src[0].src) ==
892 nir_src_bit_size(alu->src[1].src));
893 unsigned bit_size = nir_src_bit_size(alu->src[0].src);
894
895 /* get_iteration works under assumption that iterator will be
896 * incremented or decremented until it hits the limit,
897 * however if the loop condition is false on the first iteration
898 * get_iteration's assumption is broken. Handle such loops first.
899 */
900 if (will_break_on_first_iteration(step, induction_base_type, trip_offset,
901 alu_op, bit_size, initial,
902 limit, limit_rhs, invert_cond,
903 execution_mode)) {
904 return 0;
905 }
906
907 int iter_int = get_iteration(alu_op, initial, step, limit, bit_size,
908 execution_mode);
909
910 /* If iter_int is negative the loop is ill-formed or is the conditional is
911 * unsigned with a huge iteration count so don't bother going any further.
912 */
913 if (iter_int < 0)
914 return -1;
915
916 /* An explanation from the GLSL unrolling pass:
917 *
918 * Make sure that the calculated number of iterations satisfies the exit
919 * condition. This is needed to catch off-by-one errors and some types of
920 * ill-formed loops. For example, we need to detect that the following
921 * loop does not have a maximum iteration count.
922 *
923 * for (float x = 0.0; x != 0.9; x += 0.2);
924 */
925 for (int bias = -1; bias <= 1; bias++) {
926 const int iter_bias = iter_int + bias;
927
928 if (test_iterations(iter_bias, step, limit, alu_op, bit_size,
929 induction_base_type, initial,
930 limit_rhs, invert_cond, execution_mode)) {
931 return iter_bias > 0 ? iter_bias - trip_offset : iter_bias;
932 }
933 }
934
935 return -1;
936 }
937
938 static nir_op
inverse_comparison(nir_op alu_op)939 inverse_comparison(nir_op alu_op)
940 {
941 switch (alu_op) {
942 case nir_op_fge:
943 return nir_op_flt;
944 case nir_op_ige:
945 return nir_op_ilt;
946 case nir_op_uge:
947 return nir_op_ult;
948 case nir_op_flt:
949 return nir_op_fge;
950 case nir_op_ilt:
951 return nir_op_ige;
952 case nir_op_ult:
953 return nir_op_uge;
954 case nir_op_feq:
955 return nir_op_fneu;
956 case nir_op_ieq:
957 return nir_op_ine;
958 case nir_op_fneu:
959 return nir_op_feq;
960 case nir_op_ine:
961 return nir_op_ieq;
962 default:
963 unreachable("Unsuported comparison!");
964 }
965 }
966
967 static bool
get_induction_and_limit_vars(nir_ssa_scalar cond,nir_ssa_scalar * ind,nir_ssa_scalar * limit,bool * limit_rhs,loop_info_state * state)968 get_induction_and_limit_vars(nir_ssa_scalar cond,
969 nir_ssa_scalar *ind,
970 nir_ssa_scalar *limit,
971 bool *limit_rhs,
972 loop_info_state *state)
973 {
974 nir_ssa_scalar rhs, lhs;
975 lhs = nir_ssa_scalar_chase_alu_src(cond, 0);
976 rhs = nir_ssa_scalar_chase_alu_src(cond, 1);
977
978 if (get_loop_var(lhs.def, state)->type == basic_induction) {
979 *ind = lhs;
980 *limit = rhs;
981 *limit_rhs = true;
982 return true;
983 } else if (get_loop_var(rhs.def, state)->type == basic_induction) {
984 *ind = rhs;
985 *limit = lhs;
986 *limit_rhs = false;
987 return true;
988 } else {
989 return false;
990 }
991 }
992
993 static bool
try_find_trip_count_vars_in_iand(nir_ssa_scalar * cond,nir_ssa_scalar * ind,nir_ssa_scalar * limit,bool * limit_rhs,loop_info_state * state)994 try_find_trip_count_vars_in_iand(nir_ssa_scalar *cond,
995 nir_ssa_scalar *ind,
996 nir_ssa_scalar *limit,
997 bool *limit_rhs,
998 loop_info_state *state)
999 {
1000 const nir_op alu_op = nir_ssa_scalar_alu_op(*cond);
1001 assert(alu_op == nir_op_ieq || alu_op == nir_op_inot);
1002
1003 nir_ssa_scalar iand = nir_ssa_scalar_chase_alu_src(*cond, 0);
1004
1005 if (alu_op == nir_op_ieq) {
1006 nir_ssa_scalar zero = nir_ssa_scalar_chase_alu_src(*cond, 1);
1007
1008 if (!nir_ssa_scalar_is_alu(iand) || !nir_ssa_scalar_is_const(zero)) {
1009 /* Maybe we had it the wrong way, flip things around */
1010 nir_ssa_scalar tmp = zero;
1011 zero = iand;
1012 iand = tmp;
1013
1014 /* If we still didn't find what we need then return */
1015 if (!nir_ssa_scalar_is_const(zero))
1016 return false;
1017 }
1018
1019 /* If the loop is not breaking on (x && y) == 0 then return */
1020 if (nir_ssa_scalar_as_uint(zero) != 0)
1021 return false;
1022 }
1023
1024 if (!nir_ssa_scalar_is_alu(iand))
1025 return false;
1026
1027 if (nir_ssa_scalar_alu_op(iand) != nir_op_iand)
1028 return false;
1029
1030 /* Check if iand src is a terminator condition and try get induction var
1031 * and trip limit var.
1032 */
1033 bool found_induction_var = false;
1034 for (unsigned i = 0; i < 2; i++) {
1035 nir_ssa_scalar src = nir_ssa_scalar_chase_alu_src(iand, i);
1036 if (nir_is_supported_terminator_condition(src) &&
1037 get_induction_and_limit_vars(src, ind, limit, limit_rhs, state)) {
1038 *cond = src;
1039 found_induction_var = true;
1040
1041 /* If we've found one with a constant limit, stop. */
1042 if (nir_ssa_scalar_is_const(*limit))
1043 return true;
1044 }
1045 }
1046
1047 return found_induction_var;
1048 }
1049
1050 /* Run through each of the terminators of the loop and try to infer a possible
1051 * trip-count. We need to check them all, and set the lowest trip-count as the
1052 * trip-count of our loop. If one of the terminators has an undecidable
1053 * trip-count we can not safely assume anything about the duration of the
1054 * loop.
1055 */
1056 static void
find_trip_count(loop_info_state * state,unsigned execution_mode)1057 find_trip_count(loop_info_state *state, unsigned execution_mode)
1058 {
1059 bool trip_count_known = true;
1060 bool guessed_trip_count = false;
1061 nir_loop_terminator *limiting_terminator = NULL;
1062 int max_trip_count = -1;
1063
1064 list_for_each_entry(nir_loop_terminator, terminator,
1065 &state->loop->info->loop_terminator_list,
1066 loop_terminator_link) {
1067 assert(terminator->nif->condition.is_ssa);
1068 nir_ssa_scalar cond = { terminator->nif->condition.ssa, 0 };
1069
1070 if (!nir_ssa_scalar_is_alu(cond)) {
1071 /* If we get here the loop is dead and will get cleaned up by the
1072 * nir_opt_dead_cf pass.
1073 */
1074 trip_count_known = false;
1075 continue;
1076 }
1077
1078 nir_op alu_op = nir_ssa_scalar_alu_op(cond);
1079
1080 bool limit_rhs;
1081 nir_ssa_scalar basic_ind = { NULL, 0 };
1082 nir_ssa_scalar limit;
1083 if ((alu_op == nir_op_inot || alu_op == nir_op_ieq) &&
1084 try_find_trip_count_vars_in_iand(&cond, &basic_ind, &limit,
1085 &limit_rhs, state)) {
1086
1087 /* The loop is exiting on (x && y) == 0 so we need to get the
1088 * inverse of x or y (i.e. which ever contained the induction var) in
1089 * order to compute the trip count.
1090 */
1091 alu_op = inverse_comparison(nir_ssa_scalar_alu_op(cond));
1092 trip_count_known = false;
1093 terminator->exact_trip_count_unknown = true;
1094 }
1095
1096 if (!basic_ind.def) {
1097 if (nir_is_supported_terminator_condition(cond)) {
1098 get_induction_and_limit_vars(cond, &basic_ind,
1099 &limit, &limit_rhs, state);
1100 }
1101 }
1102
1103 /* The comparison has to have a basic induction variable for us to be
1104 * able to find trip counts.
1105 */
1106 if (!basic_ind.def) {
1107 trip_count_known = false;
1108 continue;
1109 }
1110
1111 terminator->induction_rhs = !limit_rhs;
1112
1113 /* Attempt to find a constant limit for the loop */
1114 nir_const_value limit_val;
1115 if (nir_ssa_scalar_is_const(limit)) {
1116 limit_val = nir_ssa_scalar_as_const_value(limit);
1117 } else {
1118 trip_count_known = false;
1119
1120 if (!try_find_limit_of_alu(limit, &limit_val, terminator, state)) {
1121 /* Guess loop limit based on array access */
1122 if (!guess_loop_limit(state, &limit_val, basic_ind)) {
1123 continue;
1124 }
1125
1126 guessed_trip_count = true;
1127 }
1128 }
1129
1130 /* We have determined that we have the following constants:
1131 * (With the typical int i = 0; i < x; i++; as an example)
1132 * - Upper limit.
1133 * - Starting value
1134 * - Step / iteration size
1135 * Thats all thats needed to calculate the trip-count
1136 */
1137
1138 nir_basic_induction_var *ind_var =
1139 get_loop_var(basic_ind.def, state)->ind;
1140
1141 /* The basic induction var might be a vector but, because we guarantee
1142 * earlier that the phi source has a scalar swizzle, we can take the
1143 * component from basic_ind.
1144 */
1145 nir_ssa_scalar initial_s = { ind_var->def_outside_loop, basic_ind.comp };
1146 nir_ssa_scalar alu_s = { &ind_var->alu->dest.dest.ssa, basic_ind.comp };
1147
1148 nir_const_value initial_val = nir_ssa_scalar_as_const_value(initial_s);
1149
1150 /* We are guaranteed by earlier code that at least one of these sources
1151 * is a constant but we don't know which.
1152 */
1153 nir_const_value step_val;
1154 memset(&step_val, 0, sizeof(step_val));
1155 UNUSED bool found_step_value = false;
1156 assert(nir_op_infos[ind_var->alu->op].num_inputs == 2);
1157 for (unsigned i = 0; i < 2; i++) {
1158 nir_ssa_scalar alu_src = nir_ssa_scalar_chase_alu_src(alu_s, i);
1159 if (nir_ssa_scalar_is_const(alu_src)) {
1160 found_step_value = true;
1161 step_val = nir_ssa_scalar_as_const_value(alu_src);
1162 break;
1163 }
1164 }
1165 assert(found_step_value);
1166
1167 int iterations = calculate_iterations(initial_val, step_val, limit_val,
1168 ind_var->alu, cond,
1169 alu_op, limit_rhs,
1170 terminator->continue_from_then,
1171 execution_mode);
1172
1173 /* Where we not able to calculate the iteration count */
1174 if (iterations == -1) {
1175 trip_count_known = false;
1176 guessed_trip_count = false;
1177 continue;
1178 }
1179
1180 if (guessed_trip_count) {
1181 guessed_trip_count = false;
1182 if (state->loop->info->guessed_trip_count == 0 ||
1183 state->loop->info->guessed_trip_count > iterations)
1184 state->loop->info->guessed_trip_count = iterations;
1185
1186 continue;
1187 }
1188
1189 /* If this is the first run or we have found a smaller amount of
1190 * iterations than previously (we have identified a more limiting
1191 * terminator) set the trip count and limiting terminator.
1192 */
1193 if (max_trip_count == -1 || iterations < max_trip_count) {
1194 max_trip_count = iterations;
1195 limiting_terminator = terminator;
1196 }
1197 }
1198
1199 state->loop->info->exact_trip_count_known = trip_count_known;
1200 if (max_trip_count > -1)
1201 state->loop->info->max_trip_count = max_trip_count;
1202 state->loop->info->limiting_terminator = limiting_terminator;
1203 }
1204
1205 static bool
force_unroll_array_access(loop_info_state * state,nir_deref_instr * deref)1206 force_unroll_array_access(loop_info_state *state, nir_deref_instr *deref)
1207 {
1208 unsigned array_size = find_array_access_via_induction(state, deref, NULL);
1209 if (array_size) {
1210 if ((array_size == state->loop->info->max_trip_count) &&
1211 nir_deref_mode_must_be(deref, nir_var_shader_in |
1212 nir_var_shader_out |
1213 nir_var_shader_temp |
1214 nir_var_function_temp))
1215 return true;
1216
1217 if (nir_deref_mode_must_be(deref, state->indirect_mask))
1218 return true;
1219 }
1220
1221 return false;
1222 }
1223
1224 static bool
force_unroll_heuristics(loop_info_state * state,nir_block * block)1225 force_unroll_heuristics(loop_info_state *state, nir_block *block)
1226 {
1227 nir_foreach_instr(instr, block) {
1228 if (instr->type != nir_instr_type_intrinsic)
1229 continue;
1230
1231 nir_intrinsic_instr *intrin = nir_instr_as_intrinsic(instr);
1232
1233 /* Check for arrays variably-indexed by a loop induction variable.
1234 * Unrolling the loop may convert that access into constant-indexing.
1235 */
1236 if (intrin->intrinsic == nir_intrinsic_load_deref ||
1237 intrin->intrinsic == nir_intrinsic_store_deref ||
1238 intrin->intrinsic == nir_intrinsic_copy_deref) {
1239 if (force_unroll_array_access(state,
1240 nir_src_as_deref(intrin->src[0])))
1241 return true;
1242
1243 if (intrin->intrinsic == nir_intrinsic_copy_deref &&
1244 force_unroll_array_access(state,
1245 nir_src_as_deref(intrin->src[1])))
1246 return true;
1247 }
1248 }
1249
1250 return false;
1251 }
1252
1253 static void
get_loop_info(loop_info_state * state,nir_function_impl * impl)1254 get_loop_info(loop_info_state *state, nir_function_impl *impl)
1255 {
1256 nir_shader *shader = impl->function->shader;
1257 const nir_shader_compiler_options *options = shader->options;
1258
1259 /* Add all entries in the outermost part of the loop to the processing list
1260 * Mark the entries in conditionals or in nested loops accordingly
1261 */
1262 foreach_list_typed_safe(nir_cf_node, node, node, &state->loop->body) {
1263 switch (node->type) {
1264
1265 case nir_cf_node_block:
1266 init_loop_block(nir_cf_node_as_block(node), state,
1267 false, false, options);
1268 break;
1269
1270 case nir_cf_node_if:
1271 nir_foreach_block_in_cf_node(block, node)
1272 init_loop_block(block, state, true, false, options);
1273 break;
1274
1275 case nir_cf_node_loop:
1276 nir_foreach_block_in_cf_node(block, node) {
1277 init_loop_block(block, state, false, true, options);
1278 }
1279 break;
1280
1281 case nir_cf_node_function:
1282 break;
1283 }
1284 }
1285
1286 /* Try to find all simple terminators of the loop. If we can't find any,
1287 * or we find possible terminators that have side effects then bail.
1288 */
1289 if (!find_loop_terminators(state)) {
1290 list_for_each_entry_safe(nir_loop_terminator, terminator,
1291 &state->loop->info->loop_terminator_list,
1292 loop_terminator_link) {
1293 list_del(&terminator->loop_terminator_link);
1294 ralloc_free(terminator);
1295 }
1296 return;
1297 }
1298
1299 /* Induction analysis needs invariance information so get that first */
1300 compute_invariance_information(state);
1301
1302 /* We have invariance information so try to find induction variables */
1303 if (!compute_induction_information(state))
1304 return;
1305
1306 /* Run through each of the terminators and try to compute a trip-count */
1307 find_trip_count(state, impl->function->shader->info.float_controls_execution_mode);
1308
1309 nir_foreach_block_in_cf_node(block, &state->loop->cf_node) {
1310 if (force_unroll_heuristics(state, block)) {
1311 state->loop->info->force_unroll = true;
1312 break;
1313 }
1314 }
1315 }
1316
1317 static loop_info_state *
initialize_loop_info_state(nir_loop * loop,void * mem_ctx,nir_function_impl * impl)1318 initialize_loop_info_state(nir_loop *loop, void *mem_ctx,
1319 nir_function_impl *impl)
1320 {
1321 loop_info_state *state = rzalloc(mem_ctx, loop_info_state);
1322 state->loop_vars = ralloc_array(mem_ctx, nir_loop_variable,
1323 impl->ssa_alloc);
1324 state->loop_vars_init = rzalloc_array(mem_ctx, BITSET_WORD,
1325 BITSET_WORDS(impl->ssa_alloc));
1326 state->loop = loop;
1327
1328 list_inithead(&state->process_list);
1329
1330 if (loop->info)
1331 ralloc_free(loop->info);
1332
1333 loop->info = rzalloc(loop, nir_loop_info);
1334
1335 list_inithead(&loop->info->loop_terminator_list);
1336
1337 return state;
1338 }
1339
1340 static void
process_loops(nir_cf_node * cf_node,nir_variable_mode indirect_mask)1341 process_loops(nir_cf_node *cf_node, nir_variable_mode indirect_mask)
1342 {
1343 switch (cf_node->type) {
1344 case nir_cf_node_block:
1345 return;
1346 case nir_cf_node_if: {
1347 nir_if *if_stmt = nir_cf_node_as_if(cf_node);
1348 foreach_list_typed(nir_cf_node, nested_node, node, &if_stmt->then_list)
1349 process_loops(nested_node, indirect_mask);
1350 foreach_list_typed(nir_cf_node, nested_node, node, &if_stmt->else_list)
1351 process_loops(nested_node, indirect_mask);
1352 return;
1353 }
1354 case nir_cf_node_loop: {
1355 nir_loop *loop = nir_cf_node_as_loop(cf_node);
1356 foreach_list_typed(nir_cf_node, nested_node, node, &loop->body)
1357 process_loops(nested_node, indirect_mask);
1358 break;
1359 }
1360 default:
1361 unreachable("unknown cf node type");
1362 }
1363
1364 nir_loop *loop = nir_cf_node_as_loop(cf_node);
1365 nir_function_impl *impl = nir_cf_node_get_function(cf_node);
1366 void *mem_ctx = ralloc_context(NULL);
1367
1368 loop_info_state *state = initialize_loop_info_state(loop, mem_ctx, impl);
1369 state->indirect_mask = indirect_mask;
1370
1371 get_loop_info(state, impl);
1372
1373 ralloc_free(mem_ctx);
1374 }
1375
1376 void
nir_loop_analyze_impl(nir_function_impl * impl,nir_variable_mode indirect_mask)1377 nir_loop_analyze_impl(nir_function_impl *impl,
1378 nir_variable_mode indirect_mask)
1379 {
1380 nir_index_ssa_defs(impl);
1381 foreach_list_typed(nir_cf_node, node, node, &impl->body)
1382 process_loops(node, indirect_mask);
1383 }
1384