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