1 /* 2 * Copyright © 2014 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 * Authors: 24 * Connor Abbott (cwabbott0@gmail.com) 25 * 26 */ 27 28 #include "nir_control_flow_private.h" 29 30 /** 31 * \name Control flow modification 32 * 33 * These functions modify the control flow tree while keeping the control flow 34 * graph up-to-date. The invariants respected are: 35 * 1. Each then statement, else statement, or loop body must have at least one 36 * control flow node. 37 * 2. Each if-statement and loop must have one basic block before it and one 38 * after. 39 * 3. Two basic blocks cannot be directly next to each other. 40 * 4. If a basic block has a jump instruction, there must be only one and it 41 * must be at the end of the block. 42 * 43 * The purpose of the second one is so that we have places to insert code during 44 * GCM, as well as eliminating the possibility of critical edges. 45 */ 46 /*@{*/ 47 48 static inline void block_add_pred(nir_block * block,nir_block * pred)49 block_add_pred(nir_block *block, nir_block *pred) 50 { 51 _mesa_set_add(block->predecessors, pred); 52 } 53 54 static inline void block_remove_pred(nir_block * block,nir_block * pred)55 block_remove_pred(nir_block *block, nir_block *pred) 56 { 57 struct set_entry *entry = _mesa_set_search(block->predecessors, pred); 58 59 assert(entry); 60 61 _mesa_set_remove(block->predecessors, entry); 62 } 63 64 static void link_blocks(nir_block * pred,nir_block * succ1,nir_block * succ2)65 link_blocks(nir_block *pred, nir_block *succ1, nir_block *succ2) 66 { 67 pred->successors[0] = succ1; 68 if (succ1 != NULL) 69 block_add_pred(succ1, pred); 70 71 pred->successors[1] = succ2; 72 if (succ2 != NULL) 73 block_add_pred(succ2, pred); 74 } 75 76 static void unlink_blocks(nir_block * pred,nir_block * succ)77 unlink_blocks(nir_block *pred, nir_block *succ) 78 { 79 if (pred->successors[0] == succ) { 80 pred->successors[0] = pred->successors[1]; 81 pred->successors[1] = NULL; 82 } else { 83 assert(pred->successors[1] == succ); 84 pred->successors[1] = NULL; 85 } 86 87 block_remove_pred(succ, pred); 88 } 89 90 static void unlink_block_successors(nir_block * block)91 unlink_block_successors(nir_block *block) 92 { 93 if (block->successors[1] != NULL) 94 unlink_blocks(block, block->successors[1]); 95 if (block->successors[0] != NULL) 96 unlink_blocks(block, block->successors[0]); 97 } 98 99 static void link_non_block_to_block(nir_cf_node * node,nir_block * block)100 link_non_block_to_block(nir_cf_node *node, nir_block *block) 101 { 102 if (node->type == nir_cf_node_if) { 103 /* 104 * We're trying to link an if to a block after it; this just means linking 105 * the last block of the then and else branches. 106 */ 107 108 nir_if *if_stmt = nir_cf_node_as_if(node); 109 110 nir_block *last_then_block = nir_if_last_then_block(if_stmt); 111 nir_block *last_else_block = nir_if_last_else_block(if_stmt); 112 113 if (!nir_block_ends_in_jump(last_then_block)) { 114 unlink_block_successors(last_then_block); 115 link_blocks(last_then_block, block, NULL); 116 } 117 118 if (!nir_block_ends_in_jump(last_else_block)) { 119 unlink_block_successors(last_else_block); 120 link_blocks(last_else_block, block, NULL); 121 } 122 } else { 123 assert(node->type == nir_cf_node_loop); 124 } 125 } 126 127 static void link_block_to_non_block(nir_block * block,nir_cf_node * node)128 link_block_to_non_block(nir_block *block, nir_cf_node *node) 129 { 130 if (node->type == nir_cf_node_if) { 131 /* 132 * We're trying to link a block to an if after it; this just means linking 133 * the block to the first block of the then and else branches. 134 */ 135 136 nir_if *if_stmt = nir_cf_node_as_if(node); 137 138 nir_block *first_then_block = nir_if_first_then_block(if_stmt); 139 nir_block *first_else_block = nir_if_first_else_block(if_stmt); 140 141 unlink_block_successors(block); 142 link_blocks(block, first_then_block, first_else_block); 143 } else if (node->type == nir_cf_node_loop) { 144 /* 145 * For similar reasons as the corresponding case in 146 * link_non_block_to_block(), don't worry about if the loop header has 147 * any predecessors that need to be unlinked. 148 */ 149 150 nir_loop *loop = nir_cf_node_as_loop(node); 151 152 nir_block *loop_header_block = nir_loop_first_block(loop); 153 154 unlink_block_successors(block); 155 link_blocks(block, loop_header_block, NULL); 156 } 157 } 158 159 /** 160 * Replace a block's successor with a different one. 161 */ 162 static void replace_successor(nir_block * block,nir_block * old_succ,nir_block * new_succ)163 replace_successor(nir_block *block, nir_block *old_succ, nir_block *new_succ) 164 { 165 if (block->successors[0] == old_succ) { 166 block->successors[0] = new_succ; 167 } else { 168 assert(block->successors[1] == old_succ); 169 block->successors[1] = new_succ; 170 } 171 172 block_remove_pred(old_succ, block); 173 block_add_pred(new_succ, block); 174 } 175 176 /** 177 * Takes a basic block and inserts a new empty basic block before it, making its 178 * predecessors point to the new block. This essentially splits the block into 179 * an empty header and a body so that another non-block CF node can be inserted 180 * between the two. Note that this does *not* link the two basic blocks, so 181 * some kind of cleanup *must* be performed after this call. 182 */ 183 184 static nir_block * split_block_beginning(nir_block * block)185 split_block_beginning(nir_block *block) 186 { 187 nir_block *new_block = nir_block_create(ralloc_parent(block)); 188 new_block->cf_node.parent = block->cf_node.parent; 189 exec_node_insert_node_before(&block->cf_node.node, &new_block->cf_node.node); 190 191 set_foreach(block->predecessors, entry) { 192 nir_block *pred = (nir_block *)entry->key; 193 replace_successor(pred, block, new_block); 194 } 195 196 /* Any phi nodes must stay part of the new block, or else their 197 * sources will be messed up. 198 */ 199 nir_foreach_phi_safe(phi, block) { 200 exec_node_remove(&phi->instr.node); 201 phi->instr.block = new_block; 202 exec_list_push_tail(&new_block->instr_list, &phi->instr.node); 203 } 204 205 return new_block; 206 } 207 208 static void rewrite_phi_preds(nir_block * block,nir_block * old_pred,nir_block * new_pred)209 rewrite_phi_preds(nir_block *block, nir_block *old_pred, nir_block *new_pred) 210 { 211 nir_foreach_phi_safe(phi, block) { 212 nir_foreach_phi_src(src, phi) { 213 if (src->pred == old_pred) { 214 src->pred = new_pred; 215 break; 216 } 217 } 218 } 219 } 220 221 void nir_insert_phi_undef(nir_block * block,nir_block * pred)222 nir_insert_phi_undef(nir_block *block, nir_block *pred) 223 { 224 nir_function_impl *impl = nir_cf_node_get_function(&block->cf_node); 225 nir_foreach_phi(phi, block) { 226 nir_undef_instr *undef = 227 nir_undef_instr_create(impl->function->shader, 228 phi->def.num_components, 229 phi->def.bit_size); 230 nir_instr_insert_before_cf_list(&impl->body, &undef->instr); 231 nir_phi_src *src = nir_phi_instr_add_src(phi, pred, &undef->def); 232 list_addtail(&src->src.use_link, &undef->def.uses); 233 } 234 } 235 236 /** 237 * Moves the successors of source to the successors of dest, leaving both 238 * successors of source NULL. 239 */ 240 241 static void move_successors(nir_block * source,nir_block * dest)242 move_successors(nir_block *source, nir_block *dest) 243 { 244 nir_block *succ1 = source->successors[0]; 245 nir_block *succ2 = source->successors[1]; 246 247 if (succ1) { 248 unlink_blocks(source, succ1); 249 rewrite_phi_preds(succ1, source, dest); 250 } 251 252 if (succ2) { 253 unlink_blocks(source, succ2); 254 rewrite_phi_preds(succ2, source, dest); 255 } 256 257 unlink_block_successors(dest); 258 link_blocks(dest, succ1, succ2); 259 } 260 261 /* Given a basic block with no successors that has been inserted into the 262 * control flow tree, gives it the successors it would normally have assuming 263 * it doesn't end in a jump instruction. Also inserts phi sources with undefs 264 * if necessary. 265 */ 266 static void block_add_normal_succs(nir_block * block)267 block_add_normal_succs(nir_block *block) 268 { 269 if (exec_node_is_tail_sentinel(block->cf_node.node.next)) { 270 nir_cf_node *parent = block->cf_node.parent; 271 if (parent->type == nir_cf_node_if) { 272 nir_cf_node *next = nir_cf_node_next(parent); 273 nir_block *next_block = nir_cf_node_as_block(next); 274 275 link_blocks(block, next_block, NULL); 276 nir_insert_phi_undef(next_block, block); 277 } else if (parent->type == nir_cf_node_loop) { 278 nir_loop *loop = nir_cf_node_as_loop(parent); 279 280 nir_block *cont_block; 281 if (block == nir_loop_last_block(loop)) { 282 cont_block = nir_loop_continue_target(loop); 283 } else { 284 assert(block == nir_loop_last_continue_block(loop)); 285 cont_block = nir_loop_first_block(loop); 286 } 287 288 link_blocks(block, cont_block, NULL); 289 nir_insert_phi_undef(cont_block, block); 290 } else { 291 nir_function_impl *impl = nir_cf_node_as_function(parent); 292 link_blocks(block, impl->end_block, NULL); 293 } 294 } else { 295 nir_cf_node *next = nir_cf_node_next(&block->cf_node); 296 if (next->type == nir_cf_node_if) { 297 nir_if *next_if = nir_cf_node_as_if(next); 298 299 nir_block *first_then_block = nir_if_first_then_block(next_if); 300 nir_block *first_else_block = nir_if_first_else_block(next_if); 301 302 link_blocks(block, first_then_block, first_else_block); 303 nir_insert_phi_undef(first_then_block, block); 304 nir_insert_phi_undef(first_else_block, block); 305 } else if (next->type == nir_cf_node_loop) { 306 nir_loop *next_loop = nir_cf_node_as_loop(next); 307 308 nir_block *first_block = nir_loop_first_block(next_loop); 309 310 link_blocks(block, first_block, NULL); 311 nir_insert_phi_undef(first_block, block); 312 } 313 } 314 } 315 316 static nir_block * split_block_end(nir_block * block)317 split_block_end(nir_block *block) 318 { 319 nir_block *new_block = nir_block_create(ralloc_parent(block)); 320 new_block->cf_node.parent = block->cf_node.parent; 321 exec_node_insert_after(&block->cf_node.node, &new_block->cf_node.node); 322 323 if (nir_block_ends_in_jump(block)) { 324 /* Figure out what successor block would've had if it didn't have a jump 325 * instruction, and make new_block have that successor. 326 */ 327 block_add_normal_succs(new_block); 328 } else { 329 move_successors(block, new_block); 330 } 331 332 return new_block; 333 } 334 335 static nir_block * split_block_before_instr(nir_instr * instr)336 split_block_before_instr(nir_instr *instr) 337 { 338 assert(instr->type != nir_instr_type_phi); 339 nir_block *new_block = split_block_beginning(instr->block); 340 341 nir_foreach_instr_safe(cur_instr, instr->block) { 342 if (cur_instr == instr) 343 break; 344 345 exec_node_remove(&cur_instr->node); 346 cur_instr->block = new_block; 347 exec_list_push_tail(&new_block->instr_list, &cur_instr->node); 348 } 349 350 return new_block; 351 } 352 353 /* Splits a basic block at the point specified by the cursor. The "before" and 354 * "after" arguments are filled out with the blocks resulting from the split 355 * if non-NULL. Note that the "beginning" of the block is actually interpreted 356 * as before the first non-phi instruction, and it's illegal to split a block 357 * before a phi instruction. 358 */ 359 360 static void split_block_cursor(nir_cursor cursor,nir_block ** _before,nir_block ** _after)361 split_block_cursor(nir_cursor cursor, 362 nir_block **_before, nir_block **_after) 363 { 364 nir_block *before, *after; 365 switch (cursor.option) { 366 case nir_cursor_before_block: 367 after = cursor.block; 368 before = split_block_beginning(cursor.block); 369 break; 370 371 case nir_cursor_after_block: 372 before = cursor.block; 373 after = split_block_end(cursor.block); 374 break; 375 376 case nir_cursor_before_instr: 377 after = cursor.instr->block; 378 before = split_block_before_instr(cursor.instr); 379 break; 380 381 case nir_cursor_after_instr: 382 /* We lower this to split_block_before_instr() so that we can keep the 383 * after-a-jump-instr case contained to split_block_end(). 384 */ 385 if (nir_instr_is_last(cursor.instr)) { 386 before = cursor.instr->block; 387 after = split_block_end(cursor.instr->block); 388 } else { 389 after = cursor.instr->block; 390 before = split_block_before_instr(nir_instr_next(cursor.instr)); 391 } 392 break; 393 394 default: 395 unreachable("not reached"); 396 } 397 398 if (_before) 399 *_before = before; 400 if (_after) 401 *_after = after; 402 } 403 404 /** 405 * Inserts a non-basic block between two basic blocks and links them together. 406 */ 407 408 static void insert_non_block(nir_block * before,nir_cf_node * node,nir_block * after)409 insert_non_block(nir_block *before, nir_cf_node *node, nir_block *after) 410 { 411 node->parent = before->cf_node.parent; 412 exec_node_insert_after(&before->cf_node.node, &node->node); 413 if (!nir_block_ends_in_jump(before)) 414 link_block_to_non_block(before, node); 415 link_non_block_to_block(node, after); 416 } 417 418 /* walk up the control flow tree to find the innermost enclosed loop */ 419 static nir_loop * nearest_loop(nir_cf_node * node)420 nearest_loop(nir_cf_node *node) 421 { 422 while (node->type != nir_cf_node_loop) { 423 node = node->parent; 424 } 425 426 return nir_cf_node_as_loop(node); 427 } 428 429 void nir_loop_add_continue_construct(nir_loop * loop)430 nir_loop_add_continue_construct(nir_loop *loop) 431 { 432 assert(!nir_loop_has_continue_construct(loop)); 433 434 nir_block *cont = nir_block_create(ralloc_parent(loop)); 435 exec_list_push_tail(&loop->continue_list, &cont->cf_node.node); 436 cont->cf_node.parent = &loop->cf_node; 437 438 /* change predecessors and successors */ 439 nir_block *header = nir_loop_first_block(loop); 440 nir_block *preheader = nir_block_cf_tree_prev(header); 441 set_foreach(header->predecessors, entry) { 442 nir_block *pred = (nir_block *)entry->key; 443 if (pred != preheader) 444 replace_successor(pred, header, cont); 445 } 446 447 link_blocks(cont, header, NULL); 448 } 449 450 void nir_loop_remove_continue_construct(nir_loop * loop)451 nir_loop_remove_continue_construct(nir_loop *loop) 452 { 453 assert(nir_cf_list_is_empty_block(&loop->continue_list)); 454 455 /* change predecessors and successors */ 456 nir_block *header = nir_loop_first_block(loop); 457 nir_block *cont = nir_loop_first_continue_block(loop); 458 set_foreach(cont->predecessors, entry) { 459 nir_block *pred = (nir_block *)entry->key; 460 replace_successor(pred, cont, header); 461 } 462 block_remove_pred(header, cont); 463 464 exec_node_remove(&cont->cf_node.node); 465 } 466 467 static void remove_phi_src(nir_block * block,nir_block * pred)468 remove_phi_src(nir_block *block, nir_block *pred) 469 { 470 nir_foreach_phi(phi, block) { 471 nir_foreach_phi_src_safe(src, phi) { 472 if (src->pred == pred) { 473 list_del(&src->src.use_link); 474 exec_node_remove(&src->node); 475 gc_free(src); 476 } 477 } 478 } 479 } 480 481 /* 482 * update the CFG after a jump instruction has been added to the end of a block 483 */ 484 485 void nir_handle_add_jump(nir_block * block)486 nir_handle_add_jump(nir_block *block) 487 { 488 nir_instr *instr = nir_block_last_instr(block); 489 nir_jump_instr *jump_instr = nir_instr_as_jump(instr); 490 491 if (block->successors[0]) 492 remove_phi_src(block->successors[0], block); 493 if (block->successors[1]) 494 remove_phi_src(block->successors[1], block); 495 unlink_block_successors(block); 496 497 nir_function_impl *impl = nir_cf_node_get_function(&block->cf_node); 498 nir_metadata_preserve(impl, nir_metadata_none); 499 500 switch (jump_instr->type) { 501 case nir_jump_return: 502 case nir_jump_halt: 503 link_blocks(block, impl->end_block, NULL); 504 break; 505 506 case nir_jump_break: { 507 nir_loop *loop = nearest_loop(&block->cf_node); 508 nir_cf_node *after = nir_cf_node_next(&loop->cf_node); 509 nir_block *after_block = nir_cf_node_as_block(after); 510 link_blocks(block, after_block, NULL); 511 break; 512 } 513 514 case nir_jump_continue: { 515 nir_loop *loop = nearest_loop(&block->cf_node); 516 nir_block *cont_block = nir_loop_continue_target(loop); 517 link_blocks(block, cont_block, NULL); 518 break; 519 } 520 521 case nir_jump_goto: 522 link_blocks(block, jump_instr->target, NULL); 523 break; 524 525 case nir_jump_goto_if: 526 link_blocks(block, jump_instr->else_target, jump_instr->target); 527 break; 528 529 default: 530 unreachable("Invalid jump type"); 531 } 532 } 533 534 /* Removes the successor of a block with a jump. Note that the jump to be 535 * eliminated may be free-floating. 536 */ 537 538 static void unlink_jump(nir_block * block,nir_jump_type type,bool add_normal_successors)539 unlink_jump(nir_block *block, nir_jump_type type, bool add_normal_successors) 540 { 541 if (block->successors[0]) 542 remove_phi_src(block->successors[0], block); 543 if (block->successors[1]) 544 remove_phi_src(block->successors[1], block); 545 546 unlink_block_successors(block); 547 if (add_normal_successors) 548 block_add_normal_succs(block); 549 } 550 551 void nir_handle_remove_jump(nir_block * block,nir_jump_type type)552 nir_handle_remove_jump(nir_block *block, nir_jump_type type) 553 { 554 unlink_jump(block, type, true); 555 556 nir_function_impl *impl = nir_cf_node_get_function(&block->cf_node); 557 nir_metadata_preserve(impl, nir_metadata_none); 558 } 559 560 static void update_if_uses(nir_cf_node * node)561 update_if_uses(nir_cf_node *node) 562 { 563 if (node->type != nir_cf_node_if) 564 return; 565 566 nir_if *if_stmt = nir_cf_node_as_if(node); 567 nir_src_set_parent_if(&if_stmt->condition, if_stmt); 568 569 list_addtail(&if_stmt->condition.use_link, 570 &if_stmt->condition.ssa->uses); 571 } 572 573 /** 574 * Stitch two basic blocks together into one. The aggregate must have the same 575 * predecessors as the first and the same successors as the second. 576 * 577 * Returns a cursor pointing at the end of the before block (i.e.m between the 578 * two blocks) once stiched together. 579 */ 580 581 static nir_cursor stitch_blocks(nir_block * before,nir_block * after)582 stitch_blocks(nir_block *before, nir_block *after) 583 { 584 /* 585 * We move after into before, so we have to deal with up to 2 successors vs. 586 * possibly a large number of predecessors. 587 * 588 * TODO: special case when before is empty and after isn't? 589 */ 590 591 if (nir_block_ends_in_jump(before)) { 592 assert(exec_list_is_empty(&after->instr_list)); 593 if (after->successors[0]) 594 remove_phi_src(after->successors[0], after); 595 if (after->successors[1]) 596 remove_phi_src(after->successors[1], after); 597 unlink_block_successors(after); 598 exec_node_remove(&after->cf_node.node); 599 600 return nir_after_block(before); 601 } else { 602 nir_instr *last_before_instr = nir_block_last_instr(before); 603 604 move_successors(after, before); 605 606 foreach_list_typed(nir_instr, instr, node, &after->instr_list) { 607 instr->block = before; 608 } 609 610 exec_list_append(&before->instr_list, &after->instr_list); 611 exec_node_remove(&after->cf_node.node); 612 613 return last_before_instr ? nir_after_instr(last_before_instr) : nir_before_block(before); 614 } 615 } 616 617 void nir_cf_node_insert(nir_cursor cursor,nir_cf_node * node)618 nir_cf_node_insert(nir_cursor cursor, nir_cf_node *node) 619 { 620 nir_block *before, *after; 621 622 split_block_cursor(cursor, &before, &after); 623 624 if (node->type == nir_cf_node_block) { 625 nir_block *block = nir_cf_node_as_block(node); 626 exec_node_insert_after(&before->cf_node.node, &block->cf_node.node); 627 block->cf_node.parent = before->cf_node.parent; 628 /* stitch_blocks() assumes that any block that ends with a jump has 629 * already been setup with the correct successors, so we need to set 630 * up jumps here as the block is being inserted. 631 */ 632 if (nir_block_ends_in_jump(block)) 633 nir_handle_add_jump(block); 634 635 stitch_blocks(block, after); 636 stitch_blocks(before, block); 637 } else { 638 update_if_uses(node); 639 insert_non_block(before, node, after); 640 } 641 } 642 643 static bool replace_ssa_def_uses(nir_def * def,void * void_impl)644 replace_ssa_def_uses(nir_def *def, void *void_impl) 645 { 646 nir_function_impl *impl = void_impl; 647 648 nir_undef_instr *undef = 649 nir_undef_instr_create(impl->function->shader, 650 def->num_components, 651 def->bit_size); 652 nir_instr_insert_before_cf_list(&impl->body, &undef->instr); 653 nir_def_rewrite_uses(def, &undef->def); 654 return true; 655 } 656 657 static void cleanup_cf_node(nir_cf_node * node,nir_function_impl * impl)658 cleanup_cf_node(nir_cf_node *node, nir_function_impl *impl) 659 { 660 switch (node->type) { 661 case nir_cf_node_block: { 662 nir_block *block = nir_cf_node_as_block(node); 663 /* We need to walk the instructions and clean up defs/uses */ 664 nir_foreach_instr_safe(instr, block) { 665 if (instr->type == nir_instr_type_jump) { 666 nir_jump_instr *jump = nir_instr_as_jump(instr); 667 unlink_jump(block, jump->type, false); 668 if (jump->type == nir_jump_goto_if) 669 nir_instr_clear_src(instr, &jump->condition); 670 } else { 671 nir_foreach_def(instr, replace_ssa_def_uses, impl); 672 nir_instr_remove(instr); 673 } 674 } 675 break; 676 } 677 678 case nir_cf_node_if: { 679 nir_if *if_stmt = nir_cf_node_as_if(node); 680 foreach_list_typed(nir_cf_node, child, node, &if_stmt->then_list) 681 cleanup_cf_node(child, impl); 682 foreach_list_typed(nir_cf_node, child, node, &if_stmt->else_list) 683 cleanup_cf_node(child, impl); 684 685 list_del(&if_stmt->condition.use_link); 686 break; 687 } 688 689 case nir_cf_node_loop: { 690 nir_loop *loop = nir_cf_node_as_loop(node); 691 foreach_list_typed(nir_cf_node, child, node, &loop->body) 692 cleanup_cf_node(child, impl); 693 foreach_list_typed(nir_cf_node, child, node, &loop->continue_list) 694 cleanup_cf_node(child, impl); 695 break; 696 } 697 case nir_cf_node_function: { 698 nir_function_impl *impl = nir_cf_node_as_function(node); 699 foreach_list_typed(nir_cf_node, child, node, &impl->body) 700 cleanup_cf_node(child, impl); 701 break; 702 } 703 default: 704 unreachable("Invalid CF node type"); 705 } 706 } 707 708 /** 709 * Extracts everything between two cursors. Returns the cursor which is 710 * equivalent to the old begin/end curosors. 711 */ 712 nir_cursor nir_cf_extract(nir_cf_list * extracted,nir_cursor begin,nir_cursor end)713 nir_cf_extract(nir_cf_list *extracted, nir_cursor begin, nir_cursor end) 714 { 715 nir_block *block_begin, *block_end, *block_before, *block_after; 716 717 if (nir_cursors_equal(begin, end)) { 718 exec_list_make_empty(&extracted->list); 719 extracted->impl = NULL; /* we shouldn't need this */ 720 return begin; 721 } 722 723 split_block_cursor(begin, &block_before, &block_begin); 724 725 /* Splitting a block twice with two cursors created before either split is 726 * tricky and there are a couple of places it can go wrong if both cursors 727 * point to the same block. One is if the second cursor is an block-based 728 * cursor and, thanks to the split above, it ends up pointing to the wrong 729 * block. If it's a before_block cursor and it's in the same block as 730 * begin, then begin must also be a before_block cursor and it should be 731 * caught by the nir_cursors_equal check above and we won't get here. If 732 * it's an after_block cursor, we need to re-adjust to ensure that it 733 * points to the second one of the split blocks, regardless of which it is. 734 */ 735 if (end.option == nir_cursor_after_block && end.block == block_before) 736 end.block = block_begin; 737 738 split_block_cursor(end, &block_end, &block_after); 739 740 /* The second place this can all go wrong is that it could be that the 741 * second split places the original block after the new block in which case 742 * the block_begin pointer that we saved off above is pointing to the block 743 * at the end rather than the block in the middle like it's supposed to be. 744 * In this case, we have to re-adjust begin_block to point to the middle 745 * one. 746 */ 747 if (block_begin == block_after) 748 block_begin = block_end; 749 750 extracted->impl = nir_cf_node_get_function(&block_begin->cf_node); 751 exec_list_make_empty(&extracted->list); 752 753 /* Dominance and other block-related information is toast. */ 754 nir_metadata_preserve(extracted->impl, nir_metadata_none); 755 756 nir_cf_node *cf_node = &block_begin->cf_node; 757 nir_cf_node *cf_node_end = &block_end->cf_node; 758 while (true) { 759 nir_cf_node *next = nir_cf_node_next(cf_node); 760 761 exec_node_remove(&cf_node->node); 762 cf_node->parent = NULL; 763 exec_list_push_tail(&extracted->list, &cf_node->node); 764 765 if (cf_node == cf_node_end) 766 break; 767 768 cf_node = next; 769 } 770 771 return stitch_blocks(block_before, block_after); 772 } 773 774 static void relink_jump_halt_cf_node(nir_cf_node * node,nir_block * end_block)775 relink_jump_halt_cf_node(nir_cf_node *node, nir_block *end_block) 776 { 777 switch (node->type) { 778 case nir_cf_node_block: { 779 nir_block *block = nir_cf_node_as_block(node); 780 nir_instr *last_instr = nir_block_last_instr(block); 781 if (last_instr == NULL || last_instr->type != nir_instr_type_jump) 782 break; 783 784 nir_jump_instr *jump = nir_instr_as_jump(last_instr); 785 /* We can't move a CF list from one function to another while we still 786 * have returns. 787 */ 788 assert(jump->type != nir_jump_return); 789 790 if (jump->type == nir_jump_halt) { 791 unlink_block_successors(block); 792 link_blocks(block, end_block, NULL); 793 } 794 break; 795 } 796 797 case nir_cf_node_if: { 798 nir_if *if_stmt = nir_cf_node_as_if(node); 799 foreach_list_typed(nir_cf_node, child, node, &if_stmt->then_list) 800 relink_jump_halt_cf_node(child, end_block); 801 foreach_list_typed(nir_cf_node, child, node, &if_stmt->else_list) 802 relink_jump_halt_cf_node(child, end_block); 803 break; 804 } 805 806 case nir_cf_node_loop: { 807 nir_loop *loop = nir_cf_node_as_loop(node); 808 foreach_list_typed(nir_cf_node, child, node, &loop->body) 809 relink_jump_halt_cf_node(child, end_block); 810 foreach_list_typed(nir_cf_node, child, node, &loop->continue_list) 811 relink_jump_halt_cf_node(child, end_block); 812 break; 813 } 814 815 case nir_cf_node_function: 816 unreachable("Cannot insert a function in a function"); 817 818 default: 819 unreachable("Invalid CF node type"); 820 } 821 } 822 823 /** 824 * Inserts a list at a given cursor. Returns the cursor at the end of the 825 * insertion (i.e., at the end of the instructions contained in cf_list). 826 */ 827 nir_cursor nir_cf_reinsert(nir_cf_list * cf_list,nir_cursor cursor)828 nir_cf_reinsert(nir_cf_list *cf_list, nir_cursor cursor) 829 { 830 nir_block *before, *after; 831 832 if (exec_list_is_empty(&cf_list->list)) 833 return cursor; 834 835 nir_function_impl *cursor_impl = 836 nir_cf_node_get_function(&nir_cursor_current_block(cursor)->cf_node); 837 if (cf_list->impl != cursor_impl) { 838 foreach_list_typed(nir_cf_node, node, node, &cf_list->list) 839 relink_jump_halt_cf_node(node, cursor_impl->end_block); 840 } 841 842 split_block_cursor(cursor, &before, &after); 843 844 foreach_list_typed_safe(nir_cf_node, node, node, &cf_list->list) { 845 exec_node_remove(&node->node); 846 node->parent = before->cf_node.parent; 847 exec_node_insert_node_before(&after->cf_node.node, &node->node); 848 } 849 850 stitch_blocks(before, 851 nir_cf_node_as_block(nir_cf_node_next(&before->cf_node))); 852 return stitch_blocks(nir_cf_node_as_block(nir_cf_node_prev(&after->cf_node)), 853 after); 854 } 855 856 void nir_cf_delete(nir_cf_list * cf_list)857 nir_cf_delete(nir_cf_list *cf_list) 858 { 859 foreach_list_typed(nir_cf_node, node, node, &cf_list->list) { 860 cleanup_cf_node(node, cf_list->impl); 861 } 862 } 863 864 struct block_index { 865 nir_block *block; 866 uint32_t index; 867 }; 868 869 static void calc_cfg_post_dfs_indices(nir_function_impl * impl,nir_block * block,struct block_index * blocks,uint32_t * count)870 calc_cfg_post_dfs_indices(nir_function_impl *impl, 871 nir_block *block, 872 struct block_index *blocks, 873 uint32_t *count) 874 { 875 if (block == impl->end_block) 876 return; 877 878 assert(block->index < impl->num_blocks); 879 880 if (blocks[block->index].block != NULL) { 881 assert(blocks[block->index].block == block); 882 return; 883 } 884 885 blocks[block->index].block = block; 886 887 for (uint32_t i = 0; i < ARRAY_SIZE(block->successors); i++) { 888 if (block->successors[i] != NULL) 889 calc_cfg_post_dfs_indices(impl, block->successors[i], blocks, count); 890 } 891 892 /* Pre-increment so that unreachable blocks have an index of 0 */ 893 blocks[block->index].index = ++(*count); 894 } 895 896 static int rev_cmp_block_index(const void * _a,const void * _b)897 rev_cmp_block_index(const void *_a, const void *_b) 898 { 899 const struct block_index *a = _a, *b = _b; 900 901 return b->index - a->index; 902 } 903 904 void nir_sort_unstructured_blocks(nir_function_impl * impl)905 nir_sort_unstructured_blocks(nir_function_impl *impl) 906 { 907 /* Re-index the blocks. 908 * 909 * We hand-roll it here instead of calling the helper because we also want 910 * to assert that there are no structured control-flow constructs. 911 */ 912 impl->num_blocks = 0; 913 foreach_list_typed(nir_cf_node, node, node, &impl->body) { 914 nir_block *block = nir_cf_node_as_block(node); 915 block->index = impl->num_blocks++; 916 } 917 918 struct block_index *blocks = 919 rzalloc_array(NULL, struct block_index, impl->num_blocks); 920 921 uint32_t count = 0; 922 calc_cfg_post_dfs_indices(impl, nir_start_block(impl), blocks, &count); 923 assert(count <= impl->num_blocks); 924 925 qsort(blocks, impl->num_blocks, sizeof(*blocks), rev_cmp_block_index); 926 927 struct exec_list dead_blocks; 928 exec_list_move_nodes_to(&impl->body, &dead_blocks); 929 930 for (uint32_t i = 0; i < count; i++) { 931 nir_block *block = blocks[i].block; 932 exec_node_remove(&block->cf_node.node); 933 block->index = i; 934 exec_list_push_tail(&impl->body, &block->cf_node.node); 935 } 936 impl->end_block->index = count; 937 938 for (uint32_t i = count; i < impl->num_blocks; i++) { 939 assert(blocks[i].index == 0); 940 assert(blocks[i].block == NULL); 941 } 942 943 foreach_list_typed_safe(nir_cf_node, node, node, &dead_blocks) 944 cleanup_cf_node(node, impl); 945 946 ralloc_free(blocks); 947 948 /* Dominance is toast but we indexed blocks as part of this pass. */ 949 impl->valid_metadata &= nir_metadata_dominance; 950 impl->valid_metadata |= nir_metadata_block_index; 951 } 952