1/* 2 * Copyright © 2016 Intel Corporation 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/nir_builder.h" 26#include "nir_constant_expressions.h" 27#include "nir_control_flow.h" 28#include "nir_loop_analyze.h" 29 30static nir_ssa_def *clone_alu_and_replace_src_defs(nir_builder *b, 31 const nir_alu_instr *alu, 32 nir_ssa_def **src_defs); 33 34/** 35 * Gets the single block that jumps back to the loop header. Already assumes 36 * there is exactly one such block. 37 */ 38static nir_block* 39find_continue_block(nir_loop *loop) 40{ 41 nir_block *header_block = nir_loop_first_block(loop); 42 nir_block *prev_block = 43 nir_cf_node_as_block(nir_cf_node_prev(&loop->cf_node)); 44 45 assert(header_block->predecessors->entries == 2); 46 47 set_foreach(header_block->predecessors, pred_entry) { 48 if (pred_entry->key != prev_block) 49 return (nir_block*)pred_entry->key; 50 } 51 52 unreachable("Continue block not found!"); 53} 54 55/** 56 * Does a phi have one constant value from outside a loop and one from inside? 57 */ 58static bool 59phi_has_constant_from_outside_and_one_from_inside_loop(nir_phi_instr *phi, 60 const nir_block *entry_block, 61 uint32_t *entry_val, 62 uint32_t *continue_val) 63{ 64 /* We already know we have exactly one continue */ 65 assert(exec_list_length(&phi->srcs) == 2); 66 67 *entry_val = 0; 68 *continue_val = 0; 69 70 nir_foreach_phi_src(src, phi) { 71 assert(src->src.is_ssa); 72 nir_const_value *const_src = nir_src_as_const_value(src->src); 73 if (!const_src) 74 return false; 75 76 if (src->pred != entry_block) { 77 *continue_val = const_src[0].u32; 78 } else { 79 *entry_val = const_src[0].u32; 80 } 81 } 82 83 return true; 84} 85 86/** 87 * This optimization detects if statements at the tops of loops where the 88 * condition is a phi node of two constants and moves half of the if to above 89 * the loop and the other half of the if to the end of the loop. A simple for 90 * loop "for (int i = 0; i < 4; i++)", when run through the SPIR-V front-end, 91 * ends up looking something like this: 92 * 93 * vec1 32 ssa_0 = load_const (0x00000000) 94 * vec1 32 ssa_1 = load_const (0xffffffff) 95 * loop { 96 * block block_1: 97 * vec1 32 ssa_2 = phi block_0: ssa_0, block_7: ssa_5 98 * vec1 32 ssa_3 = phi block_0: ssa_0, block_7: ssa_1 99 * if ssa_3 { 100 * block block_2: 101 * vec1 32 ssa_4 = load_const (0x00000001) 102 * vec1 32 ssa_5 = iadd ssa_2, ssa_4 103 * } else { 104 * block block_3: 105 * } 106 * block block_4: 107 * vec1 32 ssa_6 = load_const (0x00000004) 108 * vec1 32 ssa_7 = ilt ssa_5, ssa_6 109 * if ssa_7 { 110 * block block_5: 111 * } else { 112 * block block_6: 113 * break 114 * } 115 * block block_7: 116 * } 117 * 118 * This turns it into something like this: 119 * 120 * // Stuff from block 1 121 * // Stuff from block 3 122 * loop { 123 * block block_1: 124 * vec1 32 ssa_2 = phi block_0: ssa_0, block_7: ssa_5 125 * vec1 32 ssa_6 = load_const (0x00000004) 126 * vec1 32 ssa_7 = ilt ssa_2, ssa_6 127 * if ssa_7 { 128 * block block_5: 129 * } else { 130 * block block_6: 131 * break 132 * } 133 * block block_7: 134 * // Stuff from block 1 135 * // Stuff from block 2 136 * vec1 32 ssa_4 = load_const (0x00000001) 137 * vec1 32 ssa_5 = iadd ssa_2, ssa_4 138 * } 139 */ 140static bool 141opt_peel_loop_initial_if(nir_loop *loop) 142{ 143 nir_block *header_block = nir_loop_first_block(loop); 144 nir_block *const prev_block = 145 nir_cf_node_as_block(nir_cf_node_prev(&loop->cf_node)); 146 147 /* It would be insane if this were not true */ 148 assert(_mesa_set_search(header_block->predecessors, prev_block)); 149 150 /* The loop must have exactly one continue block which could be a block 151 * ending in a continue instruction or the "natural" continue from the 152 * last block in the loop back to the top. 153 */ 154 if (header_block->predecessors->entries != 2) 155 return false; 156 157 nir_cf_node *if_node = nir_cf_node_next(&header_block->cf_node); 158 if (!if_node || if_node->type != nir_cf_node_if) 159 return false; 160 161 nir_if *nif = nir_cf_node_as_if(if_node); 162 assert(nif->condition.is_ssa); 163 164 nir_ssa_def *cond = nif->condition.ssa; 165 if (cond->parent_instr->type != nir_instr_type_phi) 166 return false; 167 168 nir_phi_instr *cond_phi = nir_instr_as_phi(cond->parent_instr); 169 if (cond->parent_instr->block != header_block) 170 return false; 171 172 uint32_t entry_val = 0, continue_val = 0; 173 if (!phi_has_constant_from_outside_and_one_from_inside_loop(cond_phi, 174 prev_block, 175 &entry_val, 176 &continue_val)) 177 return false; 178 179 /* If they both execute or both don't execute, this is a job for 180 * nir_dead_cf, not this pass. 181 */ 182 if ((entry_val && continue_val) || (!entry_val && !continue_val)) 183 return false; 184 185 struct exec_list *continue_list, *entry_list; 186 if (continue_val) { 187 continue_list = &nif->then_list; 188 entry_list = &nif->else_list; 189 } else { 190 continue_list = &nif->else_list; 191 entry_list = &nif->then_list; 192 } 193 194 /* We want to be moving the contents of entry_list to above the loop so it 195 * can't contain any break or continue instructions. 196 */ 197 foreach_list_typed(nir_cf_node, cf_node, node, entry_list) { 198 nir_foreach_block_in_cf_node(block, cf_node) { 199 nir_instr *last_instr = nir_block_last_instr(block); 200 if (last_instr && last_instr->type == nir_instr_type_jump) 201 return false; 202 } 203 } 204 205 /* We're about to re-arrange a bunch of blocks so make sure that we don't 206 * have deref uses which cross block boundaries. We don't want a deref 207 * accidentally ending up in a phi. 208 */ 209 nir_rematerialize_derefs_in_use_blocks_impl( 210 nir_cf_node_get_function(&loop->cf_node)); 211 212 /* Before we do anything, convert the loop to LCSSA. We're about to 213 * replace a bunch of SSA defs with registers and this will prevent any of 214 * it from leaking outside the loop. 215 */ 216 nir_convert_loop_to_lcssa(loop); 217 218 nir_block *after_if_block = 219 nir_cf_node_as_block(nir_cf_node_next(&nif->cf_node)); 220 221 /* Get rid of phis in the header block since we will be duplicating it */ 222 nir_lower_phis_to_regs_block(header_block); 223 /* Get rid of phis after the if since dominance will change */ 224 nir_lower_phis_to_regs_block(after_if_block); 225 226 /* Get rid of SSA defs in the pieces we're about to move around */ 227 nir_lower_ssa_defs_to_regs_block(header_block); 228 nir_foreach_block_in_cf_node(block, &nif->cf_node) 229 nir_lower_ssa_defs_to_regs_block(block); 230 231 nir_cf_list header, tmp; 232 nir_cf_extract(&header, nir_before_block(header_block), 233 nir_after_block(header_block)); 234 235 nir_cf_list_clone(&tmp, &header, &loop->cf_node, NULL); 236 nir_cf_reinsert(&tmp, nir_before_cf_node(&loop->cf_node)); 237 nir_cf_extract(&tmp, nir_before_cf_list(entry_list), 238 nir_after_cf_list(entry_list)); 239 nir_cf_reinsert(&tmp, nir_before_cf_node(&loop->cf_node)); 240 241 nir_cf_reinsert(&header, 242 nir_after_block_before_jump(find_continue_block(loop))); 243 244 bool continue_list_jumps = 245 nir_block_ends_in_jump(exec_node_data(nir_block, 246 exec_list_get_tail(continue_list), 247 cf_node.node)); 248 249 nir_cf_extract(&tmp, nir_before_cf_list(continue_list), 250 nir_after_cf_list(continue_list)); 251 252 /* Get continue block again as the previous reinsert might have removed the 253 * block. Also, if both the continue list and the continue block ends in 254 * jump instructions, removes the jump from the latter, as it will not be 255 * executed if we insert the continue list before it. */ 256 257 nir_block *continue_block = find_continue_block(loop); 258 259 if (continue_list_jumps) { 260 nir_instr *last_instr = nir_block_last_instr(continue_block); 261 if (last_instr && last_instr->type == nir_instr_type_jump) 262 nir_instr_remove(last_instr); 263 } 264 265 nir_cf_reinsert(&tmp, 266 nir_after_block_before_jump(continue_block)); 267 268 nir_cf_node_remove(&nif->cf_node); 269 270 return true; 271} 272 273static bool 274alu_instr_is_comparison(const nir_alu_instr *alu) 275{ 276 switch (alu->op) { 277 case nir_op_flt32: 278 case nir_op_fge32: 279 case nir_op_feq32: 280 case nir_op_fne32: 281 case nir_op_ilt32: 282 case nir_op_ult32: 283 case nir_op_ige32: 284 case nir_op_uge32: 285 case nir_op_ieq32: 286 case nir_op_ine32: 287 return true; 288 default: 289 return nir_alu_instr_is_comparison(alu); 290 } 291} 292 293static bool 294alu_instr_is_type_conversion(const nir_alu_instr *alu) 295{ 296 return nir_op_infos[alu->op].num_inputs == 1 && 297 nir_alu_type_get_base_type(nir_op_infos[alu->op].output_type) != 298 nir_alu_type_get_base_type(nir_op_infos[alu->op].input_types[0]); 299} 300 301/** 302 * Splits ALU instructions that have a source that is a phi node 303 * 304 * ALU instructions in the header block of a loop that meet the following 305 * criteria can be split. 306 * 307 * - The loop has no continue instructions other than the "natural" continue 308 * at the bottom of the loop. 309 * 310 * - At least one source of the instruction is a phi node from the header block. 311 * 312 * and either this rule 313 * 314 * - The phi node selects undef from the block before the loop and a value 315 * from the continue block of the loop. 316 * 317 * or these two rules 318 * 319 * - The phi node selects a constant from the block before the loop. 320 * 321 * - The non-phi source of the ALU instruction comes from a block that 322 * dominates the block before the loop. The most common failure mode for 323 * this check is sources that are generated in the loop header block. 324 * 325 * The split process moves the original ALU instruction to the bottom of the 326 * loop. The phi node source is replaced with the value from the phi node 327 * selected from the continue block (i.e., the non-undef value). A new phi 328 * node is added to the header block that selects either undef from the block 329 * before the loop or the result of the (moved) ALU instruction. 330 * 331 * The splitting transforms a loop like: 332 * 333 * vec1 32 ssa_7 = undefined 334 * vec1 32 ssa_8 = load_const (0x00000001) 335 * vec1 32 ssa_10 = load_const (0x00000000) 336 * // succs: block_1 337 * loop { 338 * block block_1: 339 * // preds: block_0 block_4 340 * vec1 32 ssa_11 = phi block_0: ssa_7, block_4: ssa_15 341 * vec1 32 ssa_12 = phi block_0: ssa_1, block_4: ssa_15 342 * vec1 32 ssa_13 = phi block_0: ssa_10, block_4: ssa_16 343 * vec1 32 ssa_14 = iadd ssa_11, ssa_8 344 * vec1 32 ssa_15 = b32csel ssa_13, ssa_14, ssa_12 345 * ... 346 * // succs: block_1 347 * } 348 * 349 * into: 350 * 351 * vec1 32 ssa_7 = undefined 352 * vec1 32 ssa_8 = load_const (0x00000001) 353 * vec1 32 ssa_10 = load_const (0x00000000) 354 * // succs: block_1 355 * loop { 356 * block block_1: 357 * // preds: block_0 block_4 358 * vec1 32 ssa_11 = phi block_0: ssa_7, block_4: ssa_15 359 * vec1 32 ssa_12 = phi block_0: ssa_1, block_4: ssa_15 360 * vec1 32 ssa_13 = phi block_0: ssa_10, block_4: ssa_16 361 * vec1 32 ssa_21 = phi block_0: sss_7, block_4: ssa_20 362 * vec1 32 ssa_15 = b32csel ssa_13, ssa_21, ssa_12 363 * ... 364 * vec1 32 ssa_20 = iadd ssa_15, ssa_8 365 * // succs: block_1 366 * } 367 * 368 * If the phi does not select an undef, the instruction is duplicated in the 369 * loop continue block (as in the undef case) and in the previous block. When 370 * the ALU instruction is duplicated in the previous block, the correct source 371 * must be selected from the phi node. 372 */ 373static bool 374opt_split_alu_of_phi(nir_builder *b, nir_loop *loop) 375{ 376 bool progress = false; 377 nir_block *header_block = nir_loop_first_block(loop); 378 nir_block *const prev_block = 379 nir_cf_node_as_block(nir_cf_node_prev(&loop->cf_node)); 380 381 /* It would be insane if this were not true */ 382 assert(_mesa_set_search(header_block->predecessors, prev_block)); 383 384 /* The loop must have exactly one continue block which could be a block 385 * ending in a continue instruction or the "natural" continue from the 386 * last block in the loop back to the top. 387 */ 388 if (header_block->predecessors->entries != 2) 389 return false; 390 391 nir_foreach_instr_safe(instr, header_block) { 392 if (instr->type != nir_instr_type_alu) 393 continue; 394 395 nir_alu_instr *const alu = nir_instr_as_alu(instr); 396 397 /* Most ALU ops produce an undefined result if any source is undef. 398 * However, operations like bcsel only produce undefined results of the 399 * first operand is undef. Even in the undefined case, the result 400 * should be one of the other two operands, so the result of the bcsel 401 * should never be replaced with undef. 402 * 403 * nir_op_vec{2,3,4}, nir_op_imov, and nir_op_fmov are excluded because 404 * they can easily lead to infinite optimization loops. 405 */ 406 if (alu->op == nir_op_bcsel || 407 alu->op == nir_op_b32csel || 408 alu->op == nir_op_fcsel || 409 alu->op == nir_op_vec2 || 410 alu->op == nir_op_vec3 || 411 alu->op == nir_op_vec4 || 412 alu->op == nir_op_imov || 413 alu->op == nir_op_fmov || 414 alu_instr_is_comparison(alu) || 415 alu_instr_is_type_conversion(alu)) 416 continue; 417 418 bool has_phi_src_from_prev_block = false; 419 bool all_non_phi_exist_in_prev_block = true; 420 bool is_prev_result_undef = true; 421 bool is_prev_result_const = true; 422 nir_ssa_def *prev_srcs[8]; // FINISHME: Array size? 423 nir_ssa_def *continue_srcs[8]; // FINISHME: Array size? 424 425 for (unsigned i = 0; i < nir_op_infos[alu->op].num_inputs; i++) { 426 nir_instr *const src_instr = alu->src[i].src.ssa->parent_instr; 427 428 /* If the source is a phi in the loop header block, then the 429 * prev_srcs and continue_srcs will come from the different sources 430 * of the phi. 431 */ 432 if (src_instr->type == nir_instr_type_phi && 433 src_instr->block == header_block) { 434 nir_phi_instr *const phi = nir_instr_as_phi(src_instr); 435 436 /* Only strictly need to NULL out the pointers when the assertions 437 * (below) are compiled in. Debugging a NULL pointer deref in the 438 * wild is easier than debugging a random pointer deref, so set 439 * NULL unconditionally just to be safe. 440 */ 441 prev_srcs[i] = NULL; 442 continue_srcs[i] = NULL; 443 444 nir_foreach_phi_src(src_of_phi, phi) { 445 if (src_of_phi->pred == prev_block) { 446 if (src_of_phi->src.ssa->parent_instr->type != 447 nir_instr_type_ssa_undef) { 448 is_prev_result_undef = false; 449 } 450 451 if (src_of_phi->src.ssa->parent_instr->type != 452 nir_instr_type_load_const) { 453 is_prev_result_const = false; 454 } 455 456 prev_srcs[i] = src_of_phi->src.ssa; 457 has_phi_src_from_prev_block = true; 458 } else 459 continue_srcs[i] = src_of_phi->src.ssa; 460 } 461 462 assert(prev_srcs[i] != NULL); 463 assert(continue_srcs[i] != NULL); 464 } else { 465 /* If the source is not a phi (or a phi in a block other than the 466 * loop header), then the value must exist in prev_block. 467 */ 468 if (!nir_block_dominates(src_instr->block, prev_block)) { 469 all_non_phi_exist_in_prev_block = false; 470 break; 471 } 472 473 prev_srcs[i] = alu->src[i].src.ssa; 474 continue_srcs[i] = alu->src[i].src.ssa; 475 } 476 } 477 478 if (has_phi_src_from_prev_block && all_non_phi_exist_in_prev_block && 479 (is_prev_result_undef || is_prev_result_const)) { 480 nir_block *const continue_block = find_continue_block(loop); 481 nir_ssa_def *prev_value; 482 483 if (!is_prev_result_undef) { 484 b->cursor = nir_after_block(prev_block); 485 prev_value = clone_alu_and_replace_src_defs(b, alu, prev_srcs); 486 } else { 487 /* Since the undef used as the source of the original ALU 488 * instruction may have different number of components or 489 * bit size than the result of that instruction, a new 490 * undef must be created. 491 */ 492 nir_ssa_undef_instr *undef = 493 nir_ssa_undef_instr_create(b->shader, 494 alu->dest.dest.ssa.num_components, 495 alu->dest.dest.ssa.bit_size); 496 497 nir_instr_insert_after_block(prev_block, &undef->instr); 498 499 prev_value = &undef->def; 500 } 501 502 /* Make a copy of the original ALU instruction. Replace the sources 503 * of the new instruction that read a phi with an undef source from 504 * prev_block with the non-undef source of that phi. 505 * 506 * Insert the new instruction at the end of the continue block. 507 */ 508 b->cursor = nir_after_block_before_jump(continue_block); 509 510 nir_ssa_def *const alu_copy = 511 clone_alu_and_replace_src_defs(b, alu, continue_srcs); 512 513 /* Make a new phi node that selects a value from prev_block and the 514 * result of the new instruction from continue_block. 515 */ 516 nir_phi_instr *const phi = nir_phi_instr_create(b->shader); 517 nir_phi_src *phi_src; 518 519 phi_src = ralloc(phi, nir_phi_src); 520 phi_src->pred = prev_block; 521 phi_src->src = nir_src_for_ssa(prev_value); 522 exec_list_push_tail(&phi->srcs, &phi_src->node); 523 524 phi_src = ralloc(phi, nir_phi_src); 525 phi_src->pred = continue_block; 526 phi_src->src = nir_src_for_ssa(alu_copy); 527 exec_list_push_tail(&phi->srcs, &phi_src->node); 528 529 nir_ssa_dest_init(&phi->instr, &phi->dest, 530 alu_copy->num_components, alu_copy->bit_size, NULL); 531 532 b->cursor = nir_after_phis(header_block); 533 nir_builder_instr_insert(b, &phi->instr); 534 535 /* Modify all readers of the original ALU instruction to read the 536 * result of the phi. 537 */ 538 nir_foreach_use_safe(use_src, &alu->dest.dest.ssa) { 539 nir_instr_rewrite_src(use_src->parent_instr, 540 use_src, 541 nir_src_for_ssa(&phi->dest.ssa)); 542 } 543 544 nir_foreach_if_use_safe(use_src, &alu->dest.dest.ssa) { 545 nir_if_rewrite_condition(use_src->parent_if, 546 nir_src_for_ssa(&phi->dest.ssa)); 547 } 548 549 /* Since the original ALU instruction no longer has any readers, just 550 * remove it. 551 */ 552 nir_instr_remove_v(&alu->instr); 553 ralloc_free(alu); 554 555 progress = true; 556 } 557 } 558 559 return progress; 560} 561 562/** 563 * Get the SSA value from a phi node that corresponds to a specific block 564 */ 565static nir_ssa_def * 566ssa_for_phi_from_block(nir_phi_instr *phi, nir_block *block) 567{ 568 nir_foreach_phi_src(src, phi) { 569 if (src->pred == block) 570 return src->src.ssa; 571 } 572 573 assert(!"Block is not a predecessor of phi."); 574 return NULL; 575} 576 577/** 578 * Simplify a bcsel whose sources are all phi nodes from the loop header block 579 * 580 * bcsel instructions in a loop that meet the following criteria can be 581 * converted to phi nodes: 582 * 583 * - The loop has no continue instructions other than the "natural" continue 584 * at the bottom of the loop. 585 * 586 * - All of the sources of the bcsel are phi nodes in the header block of the 587 * loop. 588 * 589 * - The phi node representing the condition of the bcsel instruction chooses 590 * only constant values. 591 * 592 * The contant value from the condition will select one of the other sources 593 * when entered from outside the loop and the remaining source when entered 594 * from the continue block. Since each of these sources is also a phi node in 595 * the header block, the value of the phi node can be "evaluated." These 596 * evaluated phi nodes provide the sources for a new phi node. All users of 597 * the bcsel result are updated to use the phi node result. 598 * 599 * The replacement transforms loops like: 600 * 601 * vec1 32 ssa_7 = undefined 602 * vec1 32 ssa_8 = load_const (0x00000001) 603 * vec1 32 ssa_9 = load_const (0x000000c8) 604 * vec1 32 ssa_10 = load_const (0x00000000) 605 * // succs: block_1 606 * loop { 607 * block block_1: 608 * // preds: block_0 block_4 609 * vec1 32 ssa_11 = phi block_0: ssa_1, block_4: ssa_14 610 * vec1 32 ssa_12 = phi block_0: ssa_10, block_4: ssa_15 611 * vec1 32 ssa_13 = phi block_0: ssa_7, block_4: ssa_25 612 * vec1 32 ssa_14 = b32csel ssa_12, ssa_13, ssa_11 613 * vec1 32 ssa_16 = ige32 ssa_14, ssa_9 614 * ... 615 * vec1 32 ssa_15 = load_const (0xffffffff) 616 * ... 617 * vec1 32 ssa_25 = iadd ssa_14, ssa_8 618 * // succs: block_1 619 * } 620 * 621 * into: 622 * 623 * vec1 32 ssa_7 = undefined 624 * vec1 32 ssa_8 = load_const (0x00000001) 625 * vec1 32 ssa_9 = load_const (0x000000c8) 626 * vec1 32 ssa_10 = load_const (0x00000000) 627 * // succs: block_1 628 * loop { 629 * block block_1: 630 * // preds: block_0 block_4 631 * vec1 32 ssa_11 = phi block_0: ssa_1, block_4: ssa_14 632 * vec1 32 ssa_12 = phi block_0: ssa_10, block_4: ssa_15 633 * vec1 32 ssa_13 = phi block_0: ssa_7, block_4: ssa_25 634 * vec1 32 sss_26 = phi block_0: ssa_1, block_4: ssa_25 635 * vec1 32 ssa_16 = ige32 ssa_26, ssa_9 636 * ... 637 * vec1 32 ssa_15 = load_const (0xffffffff) 638 * ... 639 * vec1 32 ssa_25 = iadd ssa_26, ssa_8 640 * // succs: block_1 641 * } 642 * 643 * \note 644 * It may be possible modify this function to not require a phi node as the 645 * source of the bcsel that is selected when entering from outside the loop. 646 * The only restriction is that the source must be geneated outside the loop 647 * (since it will become the source of a phi node in the header block of the 648 * loop). 649 */ 650static bool 651opt_simplify_bcsel_of_phi(nir_builder *b, nir_loop *loop) 652{ 653 bool progress = false; 654 nir_block *header_block = nir_loop_first_block(loop); 655 nir_block *const prev_block = 656 nir_cf_node_as_block(nir_cf_node_prev(&loop->cf_node)); 657 658 /* It would be insane if this were not true */ 659 assert(_mesa_set_search(header_block->predecessors, prev_block)); 660 661 /* The loop must have exactly one continue block which could be a block 662 * ending in a continue instruction or the "natural" continue from the 663 * last block in the loop back to the top. 664 */ 665 if (header_block->predecessors->entries != 2) 666 return false; 667 668 /* We can move any bcsel that can guaranteed to execut on every iteration 669 * of a loop. For now this is accomplished by only taking bcsels from the 670 * header_block. In the future, this could be expanced to include any 671 * bcsel that must come before any break. 672 * 673 * For more details, see 674 * https://gitlab.freedesktop.org/mesa/mesa/merge_requests/170#note_110305 675 */ 676 nir_foreach_instr_safe(instr, header_block) { 677 if (instr->type != nir_instr_type_alu) 678 continue; 679 680 nir_alu_instr *const bcsel = nir_instr_as_alu(instr); 681 if (bcsel->op != nir_op_bcsel && 682 bcsel->op != nir_op_b32csel && 683 bcsel->op != nir_op_fcsel) 684 continue; 685 686 bool match = true; 687 for (unsigned i = 0; i < 3; i++) { 688 /* FINISHME: The abs and negate cases could be handled by adding 689 * move instructions at the bottom of the continue block and more 690 * phi nodes in the header_block. 691 */ 692 if (!bcsel->src[i].src.is_ssa || 693 bcsel->src[i].src.ssa->parent_instr->type != nir_instr_type_phi || 694 bcsel->src[i].src.ssa->parent_instr->block != header_block || 695 bcsel->src[i].negate || bcsel->src[i].abs) { 696 match = false; 697 break; 698 } 699 } 700 701 if (!match) 702 continue; 703 704 nir_phi_instr *const cond_phi = 705 nir_instr_as_phi(bcsel->src[0].src.ssa->parent_instr); 706 707 uint32_t entry_val = 0, continue_val = 0; 708 if (!phi_has_constant_from_outside_and_one_from_inside_loop(cond_phi, 709 prev_block, 710 &entry_val, 711 &continue_val)) 712 continue; 713 714 /* If they both execute or both don't execute, this is a job for 715 * nir_dead_cf, not this pass. 716 */ 717 if ((entry_val && continue_val) || (!entry_val && !continue_val)) 718 continue; 719 720 const unsigned entry_src = entry_val ? 1 : 2; 721 const unsigned continue_src = entry_val ? 2 : 1; 722 723 /* Create a new phi node that selects the value for prev_block from 724 * the bcsel source that is selected by entry_val and the value for 725 * continue_block from the other bcsel source. Both sources have 726 * already been verified to be phi nodes. 727 */ 728 nir_block *const continue_block = find_continue_block(loop); 729 nir_phi_instr *const phi = nir_phi_instr_create(b->shader); 730 nir_phi_src *phi_src; 731 732 phi_src = ralloc(phi, nir_phi_src); 733 phi_src->pred = prev_block; 734 phi_src->src = 735 nir_src_for_ssa(ssa_for_phi_from_block(nir_instr_as_phi(bcsel->src[entry_src].src.ssa->parent_instr), 736 prev_block)); 737 exec_list_push_tail(&phi->srcs, &phi_src->node); 738 739 phi_src = ralloc(phi, nir_phi_src); 740 phi_src->pred = continue_block; 741 phi_src->src = 742 nir_src_for_ssa(ssa_for_phi_from_block(nir_instr_as_phi(bcsel->src[continue_src].src.ssa->parent_instr), 743 continue_block)); 744 exec_list_push_tail(&phi->srcs, &phi_src->node); 745 746 nir_ssa_dest_init(&phi->instr, 747 &phi->dest, 748 nir_dest_num_components(bcsel->dest.dest), 749 nir_dest_bit_size(bcsel->dest.dest), 750 NULL); 751 752 b->cursor = nir_after_phis(header_block); 753 nir_builder_instr_insert(b, &phi->instr); 754 755 /* Modify all readers of the bcsel instruction to read the result of 756 * the phi. 757 */ 758 nir_foreach_use_safe(use_src, &bcsel->dest.dest.ssa) { 759 nir_instr_rewrite_src(use_src->parent_instr, 760 use_src, 761 nir_src_for_ssa(&phi->dest.ssa)); 762 } 763 764 nir_foreach_if_use_safe(use_src, &bcsel->dest.dest.ssa) { 765 nir_if_rewrite_condition(use_src->parent_if, 766 nir_src_for_ssa(&phi->dest.ssa)); 767 } 768 769 /* Since the original bcsel instruction no longer has any readers, 770 * just remove it. 771 */ 772 nir_instr_remove_v(&bcsel->instr); 773 ralloc_free(bcsel); 774 775 progress = true; 776 } 777 778 return progress; 779} 780 781static bool 782is_block_empty(nir_block *block) 783{ 784 return nir_cf_node_is_last(&block->cf_node) && 785 exec_list_is_empty(&block->instr_list); 786} 787 788static bool 789nir_block_ends_in_continue(nir_block *block) 790{ 791 if (exec_list_is_empty(&block->instr_list)) 792 return false; 793 794 nir_instr *instr = nir_block_last_instr(block); 795 return instr->type == nir_instr_type_jump && 796 nir_instr_as_jump(instr)->type == nir_jump_continue; 797} 798 799/** 800 * This optimization turns: 801 * 802 * loop { 803 * ... 804 * if (cond) { 805 * do_work_1(); 806 * continue; 807 * } else { 808 * } 809 * do_work_2(); 810 * } 811 * 812 * into: 813 * 814 * loop { 815 * ... 816 * if (cond) { 817 * do_work_1(); 818 * continue; 819 * } else { 820 * do_work_2(); 821 * } 822 * } 823 * 824 * The continue should then be removed by nir_opt_trivial_continues() and the 825 * loop can potentially be unrolled. 826 * 827 * Note: Unless the function param aggressive_last_continue==true do_work_2() 828 * is only ever blocks and nested loops. We avoid nesting other if-statments 829 * in the branch as this can result in increased register pressure, and in 830 * the i965 driver it causes a large amount of spilling in shader-db. 831 * For RADV however nesting these if-statements allows further continues to be 832 * remove and provides a significant FPS boost in Doom, which is why we have 833 * opted for this special bool to enable more aggresive optimisations. 834 * TODO: The GCM pass solves most of the spilling regressions in i965, if it 835 * is ever enabled we should consider removing the aggressive_last_continue 836 * param. 837 */ 838static bool 839opt_if_loop_last_continue(nir_loop *loop, bool aggressive_last_continue) 840{ 841 nir_if *nif; 842 bool then_ends_in_continue = false; 843 bool else_ends_in_continue = false; 844 845 /* Scan the control flow of the loop from the last to the first node 846 * looking for an if-statement we can optimise. 847 */ 848 nir_block *last_block = nir_loop_last_block(loop); 849 nir_cf_node *if_node = nir_cf_node_prev(&last_block->cf_node); 850 while (if_node) { 851 if (if_node->type == nir_cf_node_if) { 852 nif = nir_cf_node_as_if(if_node); 853 nir_block *then_block = nir_if_last_then_block(nif); 854 nir_block *else_block = nir_if_last_else_block(nif); 855 856 then_ends_in_continue = nir_block_ends_in_continue(then_block); 857 else_ends_in_continue = nir_block_ends_in_continue(else_block); 858 859 /* If both branches end in a jump do nothing, this should be handled 860 * by nir_opt_dead_cf(). 861 */ 862 if ((then_ends_in_continue || nir_block_ends_in_break(then_block)) && 863 (else_ends_in_continue || nir_block_ends_in_break(else_block))) 864 return false; 865 866 /* If continue found stop scanning and attempt optimisation, or 867 */ 868 if (then_ends_in_continue || else_ends_in_continue || 869 !aggressive_last_continue) 870 break; 871 } 872 873 if_node = nir_cf_node_prev(if_node); 874 } 875 876 /* If we didn't find an if to optimise return */ 877 if (!then_ends_in_continue && !else_ends_in_continue) 878 return false; 879 880 /* If there is nothing after the if-statement we bail */ 881 if (&nif->cf_node == nir_cf_node_prev(&last_block->cf_node) && 882 exec_list_is_empty(&last_block->instr_list)) 883 return false; 884 885 /* Move the last block of the loop inside the last if-statement */ 886 nir_cf_list tmp; 887 nir_cf_extract(&tmp, nir_after_cf_node(if_node), 888 nir_after_block(last_block)); 889 if (then_ends_in_continue) 890 nir_cf_reinsert(&tmp, nir_after_cf_list(&nif->else_list)); 891 else 892 nir_cf_reinsert(&tmp, nir_after_cf_list(&nif->then_list)); 893 894 /* In order to avoid running nir_lower_regs_to_ssa_impl() every time an if 895 * opt makes progress we leave nir_opt_trivial_continues() to remove the 896 * continue now that the end of the loop has been simplified. 897 */ 898 899 return true; 900} 901 902/* Walk all the phis in the block immediately following the if statement and 903 * swap the blocks. 904 */ 905static void 906rewrite_phi_predecessor_blocks(nir_if *nif, 907 nir_block *old_then_block, 908 nir_block *old_else_block, 909 nir_block *new_then_block, 910 nir_block *new_else_block) 911{ 912 nir_block *after_if_block = 913 nir_cf_node_as_block(nir_cf_node_next(&nif->cf_node)); 914 915 nir_foreach_instr(instr, after_if_block) { 916 if (instr->type != nir_instr_type_phi) 917 continue; 918 919 nir_phi_instr *phi = nir_instr_as_phi(instr); 920 921 foreach_list_typed(nir_phi_src, src, node, &phi->srcs) { 922 if (src->pred == old_then_block) { 923 src->pred = new_then_block; 924 } else if (src->pred == old_else_block) { 925 src->pred = new_else_block; 926 } 927 } 928 } 929} 930 931/** 932 * This optimization turns: 933 * 934 * if (cond) { 935 * } else { 936 * do_work(); 937 * } 938 * 939 * into: 940 * 941 * if (!cond) { 942 * do_work(); 943 * } else { 944 * } 945 */ 946static bool 947opt_if_simplification(nir_builder *b, nir_if *nif) 948{ 949 /* Only simplify if the then block is empty and the else block is not. */ 950 if (!is_block_empty(nir_if_first_then_block(nif)) || 951 is_block_empty(nir_if_first_else_block(nif))) 952 return false; 953 954 /* Make sure the condition is a comparison operation. */ 955 nir_instr *src_instr = nif->condition.ssa->parent_instr; 956 if (src_instr->type != nir_instr_type_alu) 957 return false; 958 959 nir_alu_instr *alu_instr = nir_instr_as_alu(src_instr); 960 if (!nir_alu_instr_is_comparison(alu_instr)) 961 return false; 962 963 /* Insert the inverted instruction and rewrite the condition. */ 964 b->cursor = nir_after_instr(&alu_instr->instr); 965 966 nir_ssa_def *new_condition = 967 nir_inot(b, &alu_instr->dest.dest.ssa); 968 969 nir_if_rewrite_condition(nif, nir_src_for_ssa(new_condition)); 970 971 /* Grab pointers to the last then/else blocks for fixing up the phis. */ 972 nir_block *then_block = nir_if_last_then_block(nif); 973 nir_block *else_block = nir_if_last_else_block(nif); 974 975 rewrite_phi_predecessor_blocks(nif, then_block, else_block, else_block, 976 then_block); 977 978 /* Finally, move the else block to the then block. */ 979 nir_cf_list tmp; 980 nir_cf_extract(&tmp, nir_before_cf_list(&nif->else_list), 981 nir_after_cf_list(&nif->else_list)); 982 nir_cf_reinsert(&tmp, nir_before_cf_list(&nif->then_list)); 983 984 return true; 985} 986 987/** 988 * This optimization simplifies potential loop terminators which then allows 989 * other passes such as opt_if_simplification() and loop unrolling to progress 990 * further: 991 * 992 * if (cond) { 993 * ... then block instructions ... 994 * } else { 995 * ... 996 * break; 997 * } 998 * 999 * into: 1000 * 1001 * if (cond) { 1002 * } else { 1003 * ... 1004 * break; 1005 * } 1006 * ... then block instructions ... 1007 */ 1008static bool 1009opt_if_loop_terminator(nir_if *nif) 1010{ 1011 nir_block *break_blk = NULL; 1012 nir_block *continue_from_blk = NULL; 1013 bool continue_from_then = true; 1014 1015 nir_block *last_then = nir_if_last_then_block(nif); 1016 nir_block *last_else = nir_if_last_else_block(nif); 1017 1018 if (nir_block_ends_in_break(last_then)) { 1019 break_blk = last_then; 1020 continue_from_blk = last_else; 1021 continue_from_then = false; 1022 } else if (nir_block_ends_in_break(last_else)) { 1023 break_blk = last_else; 1024 continue_from_blk = last_then; 1025 } 1026 1027 /* Continue if the if-statement contained no jumps at all */ 1028 if (!break_blk) 1029 return false; 1030 1031 /* If the continue from block is empty then return as there is nothing to 1032 * move. 1033 */ 1034 nir_block *first_continue_from_blk = continue_from_then ? 1035 nir_if_first_then_block(nif) : 1036 nir_if_first_else_block(nif); 1037 if (is_block_empty(first_continue_from_blk)) 1038 return false; 1039 1040 if (!nir_is_trivial_loop_if(nif, break_blk)) 1041 return false; 1042 1043 /* Even though this if statement has a jump on one side, we may still have 1044 * phis afterwards. Single-source phis can be produced by loop unrolling 1045 * or dead control-flow passes and are perfectly legal. Run a quick phi 1046 * removal on the block after the if to clean up any such phis. 1047 */ 1048 nir_opt_remove_phis_block(nir_cf_node_as_block(nir_cf_node_next(&nif->cf_node))); 1049 1050 /* Finally, move the continue from branch after the if-statement. */ 1051 nir_cf_list tmp; 1052 nir_cf_extract(&tmp, nir_before_block(first_continue_from_blk), 1053 nir_after_block(continue_from_blk)); 1054 nir_cf_reinsert(&tmp, nir_after_cf_node(&nif->cf_node)); 1055 1056 return true; 1057} 1058 1059static bool 1060evaluate_if_condition(nir_if *nif, nir_cursor cursor, bool *value) 1061{ 1062 nir_block *use_block = nir_cursor_current_block(cursor); 1063 if (nir_block_dominates(nir_if_first_then_block(nif), use_block)) { 1064 *value = true; 1065 return true; 1066 } else if (nir_block_dominates(nir_if_first_else_block(nif), use_block)) { 1067 *value = false; 1068 return true; 1069 } else { 1070 return false; 1071 } 1072} 1073 1074static nir_ssa_def * 1075clone_alu_and_replace_src_defs(nir_builder *b, const nir_alu_instr *alu, 1076 nir_ssa_def **src_defs) 1077{ 1078 nir_alu_instr *nalu = nir_alu_instr_create(b->shader, alu->op); 1079 nalu->exact = alu->exact; 1080 1081 nir_ssa_dest_init(&nalu->instr, &nalu->dest.dest, 1082 alu->dest.dest.ssa.num_components, 1083 alu->dest.dest.ssa.bit_size, alu->dest.dest.ssa.name); 1084 1085 nalu->dest.saturate = alu->dest.saturate; 1086 nalu->dest.write_mask = alu->dest.write_mask; 1087 1088 for (unsigned i = 0; i < nir_op_infos[alu->op].num_inputs; i++) { 1089 assert(alu->src[i].src.is_ssa); 1090 nalu->src[i].src = nir_src_for_ssa(src_defs[i]); 1091 nalu->src[i].negate = alu->src[i].negate; 1092 nalu->src[i].abs = alu->src[i].abs; 1093 memcpy(nalu->src[i].swizzle, alu->src[i].swizzle, 1094 sizeof(nalu->src[i].swizzle)); 1095 } 1096 1097 nir_builder_instr_insert(b, &nalu->instr); 1098 1099 return &nalu->dest.dest.ssa;; 1100} 1101 1102/* 1103 * This propagates if condition evaluation down the chain of some alu 1104 * instructions. For example by checking the use of some of the following alu 1105 * instruction we can eventually replace ssa_107 with NIR_TRUE. 1106 * 1107 * loop { 1108 * block block_1: 1109 * vec1 32 ssa_85 = load_const (0x00000002) 1110 * vec1 32 ssa_86 = ieq ssa_48, ssa_85 1111 * vec1 32 ssa_87 = load_const (0x00000001) 1112 * vec1 32 ssa_88 = ieq ssa_48, ssa_87 1113 * vec1 32 ssa_89 = ior ssa_86, ssa_88 1114 * vec1 32 ssa_90 = ieq ssa_48, ssa_0 1115 * vec1 32 ssa_91 = ior ssa_89, ssa_90 1116 * if ssa_86 { 1117 * block block_2: 1118 * ... 1119 * break 1120 * } else { 1121 * block block_3: 1122 * } 1123 * block block_4: 1124 * if ssa_88 { 1125 * block block_5: 1126 * ... 1127 * break 1128 * } else { 1129 * block block_6: 1130 * } 1131 * block block_7: 1132 * if ssa_90 { 1133 * block block_8: 1134 * ... 1135 * break 1136 * } else { 1137 * block block_9: 1138 * } 1139 * block block_10: 1140 * vec1 32 ssa_107 = inot ssa_91 1141 * if ssa_107 { 1142 * block block_11: 1143 * break 1144 * } else { 1145 * block block_12: 1146 * } 1147 * } 1148 */ 1149static bool 1150propagate_condition_eval(nir_builder *b, nir_if *nif, nir_src *use_src, 1151 nir_src *alu_use, nir_alu_instr *alu, 1152 bool is_if_condition) 1153{ 1154 bool bool_value; 1155 b->cursor = nir_before_src(alu_use, is_if_condition); 1156 if (!evaluate_if_condition(nif, b->cursor, &bool_value)) 1157 return false; 1158 1159 nir_ssa_def *def[4] = {0}; 1160 for (unsigned i = 0; i < nir_op_infos[alu->op].num_inputs; i++) { 1161 if (alu->src[i].src.ssa == use_src->ssa) { 1162 def[i] = nir_imm_bool(b, bool_value); 1163 } else { 1164 def[i] = alu->src[i].src.ssa; 1165 } 1166 } 1167 1168 nir_ssa_def *nalu = clone_alu_and_replace_src_defs(b, alu, def); 1169 1170 /* Rewrite use to use new alu instruction */ 1171 nir_src new_src = nir_src_for_ssa(nalu); 1172 1173 if (is_if_condition) 1174 nir_if_rewrite_condition(alu_use->parent_if, new_src); 1175 else 1176 nir_instr_rewrite_src(alu_use->parent_instr, alu_use, new_src); 1177 1178 return true; 1179} 1180 1181static bool 1182can_propagate_through_alu(nir_src *src) 1183{ 1184 if (src->parent_instr->type != nir_instr_type_alu) 1185 return false; 1186 1187 nir_alu_instr *alu = nir_instr_as_alu(src->parent_instr); 1188 switch (alu->op) { 1189 case nir_op_ior: 1190 case nir_op_iand: 1191 case nir_op_inot: 1192 case nir_op_b2i32: 1193 return true; 1194 case nir_op_bcsel: 1195 return src == &alu->src[0].src; 1196 default: 1197 return false; 1198 } 1199} 1200 1201static bool 1202evaluate_condition_use(nir_builder *b, nir_if *nif, nir_src *use_src, 1203 bool is_if_condition) 1204{ 1205 bool progress = false; 1206 1207 b->cursor = nir_before_src(use_src, is_if_condition); 1208 1209 bool bool_value; 1210 if (evaluate_if_condition(nif, b->cursor, &bool_value)) { 1211 /* Rewrite use to use const */ 1212 nir_src imm_src = nir_src_for_ssa(nir_imm_bool(b, bool_value)); 1213 if (is_if_condition) 1214 nir_if_rewrite_condition(use_src->parent_if, imm_src); 1215 else 1216 nir_instr_rewrite_src(use_src->parent_instr, use_src, imm_src); 1217 1218 progress = true; 1219 } 1220 1221 if (!is_if_condition && can_propagate_through_alu(use_src)) { 1222 nir_alu_instr *alu = nir_instr_as_alu(use_src->parent_instr); 1223 1224 nir_foreach_use_safe(alu_use, &alu->dest.dest.ssa) { 1225 progress |= propagate_condition_eval(b, nif, use_src, alu_use, alu, 1226 false); 1227 } 1228 1229 nir_foreach_if_use_safe(alu_use, &alu->dest.dest.ssa) { 1230 progress |= propagate_condition_eval(b, nif, use_src, alu_use, alu, 1231 true); 1232 } 1233 } 1234 1235 return progress; 1236} 1237 1238static bool 1239opt_if_evaluate_condition_use(nir_builder *b, nir_if *nif) 1240{ 1241 bool progress = false; 1242 1243 /* Evaluate any uses of the if condition inside the if branches */ 1244 assert(nif->condition.is_ssa); 1245 nir_foreach_use_safe(use_src, nif->condition.ssa) { 1246 progress |= evaluate_condition_use(b, nif, use_src, false); 1247 } 1248 1249 nir_foreach_if_use_safe(use_src, nif->condition.ssa) { 1250 if (use_src->parent_if != nif) 1251 progress |= evaluate_condition_use(b, nif, use_src, true); 1252 } 1253 1254 return progress; 1255} 1256 1257static void 1258simple_merge_if(nir_if *dest_if, nir_if *src_if, bool dest_if_then, 1259 bool src_if_then) 1260{ 1261 /* Now merge the if branch */ 1262 nir_block *dest_blk = dest_if_then ? nir_if_last_then_block(dest_if) 1263 : nir_if_last_else_block(dest_if); 1264 1265 struct exec_list *list = src_if_then ? &src_if->then_list 1266 : &src_if->else_list; 1267 1268 nir_cf_list if_cf_list; 1269 nir_cf_extract(&if_cf_list, nir_before_cf_list(list), 1270 nir_after_cf_list(list)); 1271 nir_cf_reinsert(&if_cf_list, nir_after_block(dest_blk)); 1272} 1273 1274static bool 1275opt_if_merge(nir_if *nif) 1276{ 1277 bool progress = false; 1278 1279 nir_block *next_blk = nir_cf_node_cf_tree_next(&nif->cf_node); 1280 if (next_blk && nif->condition.is_ssa) { 1281 nir_if *next_if = nir_block_get_following_if(next_blk); 1282 if (next_if && next_if->condition.is_ssa) { 1283 1284 /* Here we merge two consecutive ifs that have the same 1285 * condition e.g: 1286 * 1287 * if ssa_12 { 1288 * ... 1289 * } else { 1290 * ... 1291 * } 1292 * if ssa_12 { 1293 * ... 1294 * } else { 1295 * ... 1296 * } 1297 * 1298 * Note: This only merges if-statements when the block between them 1299 * is empty. The reason we don't try to merge ifs that just have phis 1300 * between them is because this can results in increased register 1301 * pressure. For example when merging if ladders created by indirect 1302 * indexing. 1303 */ 1304 if (nif->condition.ssa == next_if->condition.ssa && 1305 exec_list_is_empty(&next_blk->instr_list)) { 1306 1307 simple_merge_if(nif, next_if, true, true); 1308 simple_merge_if(nif, next_if, false, false); 1309 1310 nir_block *new_then_block = nir_if_last_then_block(nif); 1311 nir_block *new_else_block = nir_if_last_else_block(nif); 1312 1313 nir_block *old_then_block = nir_if_last_then_block(next_if); 1314 nir_block *old_else_block = nir_if_last_else_block(next_if); 1315 1316 /* Rewrite the predecessor block for any phis following the second 1317 * if-statement. 1318 */ 1319 rewrite_phi_predecessor_blocks(next_if, old_then_block, 1320 old_else_block, 1321 new_then_block, 1322 new_else_block); 1323 1324 /* Move phis after merged if to avoid them being deleted when we 1325 * remove the merged if-statement. 1326 */ 1327 nir_block *after_next_if_block = 1328 nir_cf_node_as_block(nir_cf_node_next(&next_if->cf_node)); 1329 1330 nir_foreach_instr_safe(instr, after_next_if_block) { 1331 if (instr->type != nir_instr_type_phi) 1332 break; 1333 1334 exec_node_remove(&instr->node); 1335 exec_list_push_tail(&next_blk->instr_list, &instr->node); 1336 instr->block = next_blk; 1337 } 1338 1339 nir_cf_node_remove(&next_if->cf_node); 1340 1341 progress = true; 1342 } 1343 } 1344 } 1345 1346 return progress; 1347} 1348 1349static bool 1350opt_if_cf_list(nir_builder *b, struct exec_list *cf_list, 1351 bool aggressive_last_continue) 1352{ 1353 bool progress = false; 1354 foreach_list_typed(nir_cf_node, cf_node, node, cf_list) { 1355 switch (cf_node->type) { 1356 case nir_cf_node_block: 1357 break; 1358 1359 case nir_cf_node_if: { 1360 nir_if *nif = nir_cf_node_as_if(cf_node); 1361 progress |= opt_if_cf_list(b, &nif->then_list, 1362 aggressive_last_continue); 1363 progress |= opt_if_cf_list(b, &nif->else_list, 1364 aggressive_last_continue); 1365 progress |= opt_if_loop_terminator(nif); 1366 progress |= opt_if_merge(nif); 1367 progress |= opt_if_simplification(b, nif); 1368 break; 1369 } 1370 1371 case nir_cf_node_loop: { 1372 nir_loop *loop = nir_cf_node_as_loop(cf_node); 1373 progress |= opt_if_cf_list(b, &loop->body, 1374 aggressive_last_continue); 1375 progress |= opt_simplify_bcsel_of_phi(b, loop); 1376 progress |= opt_peel_loop_initial_if(loop); 1377 progress |= opt_if_loop_last_continue(loop, 1378 aggressive_last_continue); 1379 break; 1380 } 1381 1382 case nir_cf_node_function: 1383 unreachable("Invalid cf type"); 1384 } 1385 } 1386 1387 return progress; 1388} 1389 1390/** 1391 * These optimisations depend on nir_metadata_block_index and therefore must 1392 * not do anything to cause the metadata to become invalid. 1393 */ 1394static bool 1395opt_if_safe_cf_list(nir_builder *b, struct exec_list *cf_list) 1396{ 1397 bool progress = false; 1398 foreach_list_typed(nir_cf_node, cf_node, node, cf_list) { 1399 switch (cf_node->type) { 1400 case nir_cf_node_block: 1401 break; 1402 1403 case nir_cf_node_if: { 1404 nir_if *nif = nir_cf_node_as_if(cf_node); 1405 progress |= opt_if_safe_cf_list(b, &nif->then_list); 1406 progress |= opt_if_safe_cf_list(b, &nif->else_list); 1407 progress |= opt_if_evaluate_condition_use(b, nif); 1408 break; 1409 } 1410 1411 case nir_cf_node_loop: { 1412 nir_loop *loop = nir_cf_node_as_loop(cf_node); 1413 progress |= opt_if_safe_cf_list(b, &loop->body); 1414 progress |= opt_split_alu_of_phi(b, loop); 1415 break; 1416 } 1417 1418 case nir_cf_node_function: 1419 unreachable("Invalid cf type"); 1420 } 1421 } 1422 1423 return progress; 1424} 1425 1426bool 1427nir_opt_if(nir_shader *shader, bool aggressive_last_continue) 1428{ 1429 bool progress = false; 1430 1431 nir_foreach_function(function, shader) { 1432 if (function->impl == NULL) 1433 continue; 1434 1435 nir_builder b; 1436 nir_builder_init(&b, function->impl); 1437 1438 nir_metadata_require(function->impl, nir_metadata_block_index | 1439 nir_metadata_dominance); 1440 progress = opt_if_safe_cf_list(&b, &function->impl->body); 1441 nir_metadata_preserve(function->impl, nir_metadata_block_index | 1442 nir_metadata_dominance); 1443 1444 if (opt_if_cf_list(&b, &function->impl->body, 1445 aggressive_last_continue)) { 1446 nir_metadata_preserve(function->impl, nir_metadata_none); 1447 1448 /* If that made progress, we're no longer really in SSA form. We 1449 * need to convert registers back into SSA defs and clean up SSA defs 1450 * that don't dominate their uses. 1451 */ 1452 nir_lower_regs_to_ssa_impl(function->impl); 1453 1454 progress = true; 1455 } else { 1456 #ifndef NDEBUG 1457 function->impl->valid_metadata &= ~nir_metadata_not_properly_reset; 1458 #endif 1459 } 1460 } 1461 1462 return progress; 1463} 1464