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 (at) 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 bool 49 block_ends_in_jump(nir_block *block) 50 { 51 return !exec_list_is_empty(&block->instr_list) && 52 nir_block_last_instr(block)->type == nir_instr_type_jump; 53 } 54 55 static inline void 56 block_add_pred(nir_block *block, nir_block *pred) 57 { 58 _mesa_set_add(block->predecessors, pred); 59 } 60 61 static inline void 62 block_remove_pred(nir_block *block, nir_block *pred) 63 { 64 struct set_entry *entry = _mesa_set_search(block->predecessors, pred); 65 66 assert(entry); 67 68 _mesa_set_remove(block->predecessors, entry); 69 } 70 71 static void 72 link_blocks(nir_block *pred, nir_block *succ1, nir_block *succ2) 73 { 74 pred->successors[0] = succ1; 75 if (succ1 != NULL) 76 block_add_pred(succ1, pred); 77 78 pred->successors[1] = succ2; 79 if (succ2 != NULL) 80 block_add_pred(succ2, pred); 81 } 82 83 static void 84 unlink_blocks(nir_block *pred, nir_block *succ) 85 { 86 if (pred->successors[0] == succ) { 87 pred->successors[0] = pred->successors[1]; 88 pred->successors[1] = NULL; 89 } else { 90 assert(pred->successors[1] == succ); 91 pred->successors[1] = NULL; 92 } 93 94 block_remove_pred(succ, pred); 95 } 96 97 static void 98 unlink_block_successors(nir_block *block) 99 { 100 if (block->successors[1] != NULL) 101 unlink_blocks(block, block->successors[1]); 102 if (block->successors[0] != NULL) 103 unlink_blocks(block, block->successors[0]); 104 } 105 106 static void 107 link_non_block_to_block(nir_cf_node *node, nir_block *block) 108 { 109 if (node->type == nir_cf_node_if) { 110 /* 111 * We're trying to link an if to a block after it; this just means linking 112 * the last block of the then and else branches. 113 */ 114 115 nir_if *if_stmt = nir_cf_node_as_if(node); 116 117 nir_block *last_then_block = nir_if_last_then_block(if_stmt); 118 nir_block *last_else_block = nir_if_last_else_block(if_stmt); 119 120 if (!block_ends_in_jump(last_then_block)) { 121 unlink_block_successors(last_then_block); 122 link_blocks(last_then_block, block, NULL); 123 } 124 125 if (!block_ends_in_jump(last_else_block)) { 126 unlink_block_successors(last_else_block); 127 link_blocks(last_else_block, block, NULL); 128 } 129 } else { 130 assert(node->type == nir_cf_node_loop); 131 } 132 } 133 134 static void 135 link_block_to_non_block(nir_block *block, nir_cf_node *node) 136 { 137 if (node->type == nir_cf_node_if) { 138 /* 139 * We're trying to link a block to an if after it; this just means linking 140 * the block to the first block of the then and else branches. 141 */ 142 143 nir_if *if_stmt = nir_cf_node_as_if(node); 144 145 nir_block *first_then_block = nir_if_first_then_block(if_stmt); 146 nir_block *first_else_block = nir_if_first_else_block(if_stmt); 147 148 unlink_block_successors(block); 149 link_blocks(block, first_then_block, first_else_block); 150 } else { 151 /* 152 * For similar reasons as the corresponding case in 153 * link_non_block_to_block(), don't worry about if the loop header has 154 * any predecessors that need to be unlinked. 155 */ 156 157 nir_loop *loop = nir_cf_node_as_loop(node); 158 159 nir_block *loop_header_block = nir_loop_first_block(loop); 160 161 unlink_block_successors(block); 162 link_blocks(block, loop_header_block, NULL); 163 } 164 165 } 166 167 /** 168 * Replace a block's successor with a different one. 169 */ 170 static void 171 replace_successor(nir_block *block, nir_block *old_succ, nir_block *new_succ) 172 { 173 if (block->successors[0] == old_succ) { 174 block->successors[0] = new_succ; 175 } else { 176 assert(block->successors[1] == old_succ); 177 block->successors[1] = new_succ; 178 } 179 180 block_remove_pred(old_succ, block); 181 block_add_pred(new_succ, block); 182 } 183 184 /** 185 * Takes a basic block and inserts a new empty basic block before it, making its 186 * predecessors point to the new block. This essentially splits the block into 187 * an empty header and a body so that another non-block CF node can be inserted 188 * between the two. Note that this does *not* link the two basic blocks, so 189 * some kind of cleanup *must* be performed after this call. 190 */ 191 192 static nir_block * 193 split_block_beginning(nir_block *block) 194 { 195 nir_block *new_block = nir_block_create(ralloc_parent(block)); 196 new_block->cf_node.parent = block->cf_node.parent; 197 exec_node_insert_node_before(&block->cf_node.node, &new_block->cf_node.node); 198 199 struct set_entry *entry; 200 set_foreach(block->predecessors, entry) { 201 nir_block *pred = (nir_block *) entry->key; 202 replace_successor(pred, block, new_block); 203 } 204 205 /* Any phi nodes must stay part of the new block, or else their 206 * sourcse will be messed up. This will reverse the order of the phi's, but 207 * order shouldn't matter. 208 */ 209 nir_foreach_instr_safe(instr, block) { 210 if (instr->type != nir_instr_type_phi) 211 break; 212 213 exec_node_remove(&instr->node); 214 instr->block = new_block; 215 exec_list_push_head(&new_block->instr_list, &instr->node); 216 } 217 218 return new_block; 219 } 220 221 static void 222 rewrite_phi_preds(nir_block *block, nir_block *old_pred, nir_block *new_pred) 223 { 224 nir_foreach_instr_safe(instr, block) { 225 if (instr->type != nir_instr_type_phi) 226 break; 227 228 nir_phi_instr *phi = nir_instr_as_phi(instr); 229 nir_foreach_phi_src(src, phi) { 230 if (src->pred == old_pred) { 231 src->pred = new_pred; 232 break; 233 } 234 } 235 } 236 } 237 238 static void 239 insert_phi_undef(nir_block *block, nir_block *pred) 240 { 241 nir_function_impl *impl = nir_cf_node_get_function(&block->cf_node); 242 nir_foreach_instr(instr, block) { 243 if (instr->type != nir_instr_type_phi) 244 break; 245 246 nir_phi_instr *phi = nir_instr_as_phi(instr); 247 nir_ssa_undef_instr *undef = 248 nir_ssa_undef_instr_create(ralloc_parent(phi), 249 phi->dest.ssa.num_components, 250 phi->dest.ssa.bit_size); 251 nir_instr_insert_before_cf_list(&impl->body, &undef->instr); 252 nir_phi_src *src = ralloc(phi, nir_phi_src); 253 src->pred = pred; 254 src->src.parent_instr = &phi->instr; 255 src->src.is_ssa = true; 256 src->src.ssa = &undef->def; 257 258 list_addtail(&src->src.use_link, &undef->def.uses); 259 260 exec_list_push_tail(&phi->srcs, &src->node); 261 } 262 } 263 264 /** 265 * Moves the successors of source to the successors of dest, leaving both 266 * successors of source NULL. 267 */ 268 269 static void 270 move_successors(nir_block *source, nir_block *dest) 271 { 272 nir_block *succ1 = source->successors[0]; 273 nir_block *succ2 = source->successors[1]; 274 275 if (succ1) { 276 unlink_blocks(source, succ1); 277 rewrite_phi_preds(succ1, source, dest); 278 } 279 280 if (succ2) { 281 unlink_blocks(source, succ2); 282 rewrite_phi_preds(succ2, source, dest); 283 } 284 285 unlink_block_successors(dest); 286 link_blocks(dest, succ1, succ2); 287 } 288 289 /* Given a basic block with no successors that has been inserted into the 290 * control flow tree, gives it the successors it would normally have assuming 291 * it doesn't end in a jump instruction. Also inserts phi sources with undefs 292 * if necessary. 293 */ 294 static void 295 block_add_normal_succs(nir_block *block) 296 { 297 if (exec_node_is_tail_sentinel(block->cf_node.node.next)) { 298 nir_cf_node *parent = block->cf_node.parent; 299 if (parent->type == nir_cf_node_if) { 300 nir_cf_node *next = nir_cf_node_next(parent); 301 nir_block *next_block = nir_cf_node_as_block(next); 302 303 link_blocks(block, next_block, NULL); 304 } else if (parent->type == nir_cf_node_loop) { 305 nir_loop *loop = nir_cf_node_as_loop(parent); 306 307 nir_block *head_block = nir_loop_first_block(loop); 308 309 link_blocks(block, head_block, NULL); 310 insert_phi_undef(head_block, block); 311 } else { 312 nir_function_impl *impl = nir_cf_node_as_function(parent); 313 link_blocks(block, impl->end_block, NULL); 314 } 315 } else { 316 nir_cf_node *next = nir_cf_node_next(&block->cf_node); 317 if (next->type == nir_cf_node_if) { 318 nir_if *next_if = nir_cf_node_as_if(next); 319 320 nir_block *first_then_block = nir_if_first_then_block(next_if); 321 nir_block *first_else_block = nir_if_first_else_block(next_if); 322 323 link_blocks(block, first_then_block, first_else_block); 324 } else { 325 nir_loop *next_loop = nir_cf_node_as_loop(next); 326 327 nir_block *first_block = nir_loop_first_block(next_loop); 328 329 link_blocks(block, first_block, NULL); 330 insert_phi_undef(first_block, block); 331 } 332 } 333 } 334 335 static nir_block * 336 split_block_end(nir_block *block) 337 { 338 nir_block *new_block = nir_block_create(ralloc_parent(block)); 339 new_block->cf_node.parent = block->cf_node.parent; 340 exec_node_insert_after(&block->cf_node.node, &new_block->cf_node.node); 341 342 if (block_ends_in_jump(block)) { 343 /* Figure out what successor block would've had if it didn't have a jump 344 * instruction, and make new_block have that successor. 345 */ 346 block_add_normal_succs(new_block); 347 } else { 348 move_successors(block, new_block); 349 } 350 351 return new_block; 352 } 353 354 static nir_block * 355 split_block_before_instr(nir_instr *instr) 356 { 357 assert(instr->type != nir_instr_type_phi); 358 nir_block *new_block = split_block_beginning(instr->block); 359 360 nir_foreach_instr_safe(cur_instr, instr->block) { 361 if (cur_instr == instr) 362 break; 363 364 exec_node_remove(&cur_instr->node); 365 cur_instr->block = new_block; 366 exec_list_push_tail(&new_block->instr_list, &cur_instr->node); 367 } 368 369 return new_block; 370 } 371 372 /* Splits a basic block at the point specified by the cursor. The "before" and 373 * "after" arguments are filled out with the blocks resulting from the split 374 * if non-NULL. Note that the "beginning" of the block is actually interpreted 375 * as before the first non-phi instruction, and it's illegal to split a block 376 * before a phi instruction. 377 */ 378 379 static void 380 split_block_cursor(nir_cursor cursor, 381 nir_block **_before, nir_block **_after) 382 { 383 nir_block *before, *after; 384 switch (cursor.option) { 385 case nir_cursor_before_block: 386 after = cursor.block; 387 before = split_block_beginning(cursor.block); 388 break; 389 390 case nir_cursor_after_block: 391 before = cursor.block; 392 after = split_block_end(cursor.block); 393 break; 394 395 case nir_cursor_before_instr: 396 after = cursor.instr->block; 397 before = split_block_before_instr(cursor.instr); 398 break; 399 400 case nir_cursor_after_instr: 401 /* We lower this to split_block_before_instr() so that we can keep the 402 * after-a-jump-instr case contained to split_block_end(). 403 */ 404 if (nir_instr_is_last(cursor.instr)) { 405 before = cursor.instr->block; 406 after = split_block_end(cursor.instr->block); 407 } else { 408 after = cursor.instr->block; 409 before = split_block_before_instr(nir_instr_next(cursor.instr)); 410 } 411 break; 412 413 default: 414 unreachable("not reached"); 415 } 416 417 if (_before) 418 *_before = before; 419 if (_after) 420 *_after = after; 421 } 422 423 /** 424 * Inserts a non-basic block between two basic blocks and links them together. 425 */ 426 427 static void 428 insert_non_block(nir_block *before, nir_cf_node *node, nir_block *after) 429 { 430 node->parent = before->cf_node.parent; 431 exec_node_insert_after(&before->cf_node.node, &node->node); 432 link_block_to_non_block(before, node); 433 link_non_block_to_block(node, after); 434 } 435 436 /* walk up the control flow tree to find the innermost enclosed loop */ 437 static nir_loop * 438 nearest_loop(nir_cf_node *node) 439 { 440 while (node->type != nir_cf_node_loop) { 441 node = node->parent; 442 } 443 444 return nir_cf_node_as_loop(node); 445 } 446 447 /* 448 * update the CFG after a jump instruction has been added to the end of a block 449 */ 450 451 void 452 nir_handle_add_jump(nir_block *block) 453 { 454 nir_instr *instr = nir_block_last_instr(block); 455 nir_jump_instr *jump_instr = nir_instr_as_jump(instr); 456 457 unlink_block_successors(block); 458 459 nir_function_impl *impl = nir_cf_node_get_function(&block->cf_node); 460 nir_metadata_preserve(impl, nir_metadata_none); 461 462 if (jump_instr->type == nir_jump_break || 463 jump_instr->type == nir_jump_continue) { 464 nir_loop *loop = nearest_loop(&block->cf_node); 465 466 if (jump_instr->type == nir_jump_continue) { 467 nir_block *first_block = nir_loop_first_block(loop); 468 link_blocks(block, first_block, NULL); 469 } else { 470 nir_cf_node *after = nir_cf_node_next(&loop->cf_node); 471 nir_block *after_block = nir_cf_node_as_block(after); 472 link_blocks(block, after_block, NULL); 473 } 474 } else { 475 assert(jump_instr->type == nir_jump_return); 476 link_blocks(block, impl->end_block, NULL); 477 } 478 } 479 480 static void 481 remove_phi_src(nir_block *block, nir_block *pred) 482 { 483 nir_foreach_instr(instr, block) { 484 if (instr->type != nir_instr_type_phi) 485 break; 486 487 nir_phi_instr *phi = nir_instr_as_phi(instr); 488 nir_foreach_phi_src_safe(src, phi) { 489 if (src->pred == pred) { 490 list_del(&src->src.use_link); 491 exec_node_remove(&src->node); 492 } 493 } 494 } 495 } 496 497 /* Removes the successor of a block with a jump. Note that the jump to be 498 * eliminated may be free-floating. 499 */ 500 501 static void 502 unlink_jump(nir_block *block, nir_jump_type type, bool add_normal_successors) 503 { 504 if (block->successors[0]) 505 remove_phi_src(block->successors[0], block); 506 if (block->successors[1]) 507 remove_phi_src(block->successors[1], block); 508 509 unlink_block_successors(block); 510 if (add_normal_successors) 511 block_add_normal_succs(block); 512 } 513 514 void 515 nir_handle_remove_jump(nir_block *block, nir_jump_type type) 516 { 517 unlink_jump(block, type, true); 518 519 nir_function_impl *impl = nir_cf_node_get_function(&block->cf_node); 520 nir_metadata_preserve(impl, nir_metadata_none); 521 } 522 523 static void 524 update_if_uses(nir_cf_node *node) 525 { 526 if (node->type != nir_cf_node_if) 527 return; 528 529 nir_if *if_stmt = nir_cf_node_as_if(node); 530 531 if_stmt->condition.parent_if = if_stmt; 532 if (if_stmt->condition.is_ssa) { 533 list_addtail(&if_stmt->condition.use_link, 534 &if_stmt->condition.ssa->if_uses); 535 } else { 536 list_addtail(&if_stmt->condition.use_link, 537 &if_stmt->condition.reg.reg->if_uses); 538 } 539 } 540 541 /** 542 * Stitch two basic blocks together into one. The aggregate must have the same 543 * predecessors as the first and the same successors as the second. 544 */ 545 546 static void 547 stitch_blocks(nir_block *before, nir_block *after) 548 { 549 /* 550 * We move after into before, so we have to deal with up to 2 successors vs. 551 * possibly a large number of predecessors. 552 * 553 * TODO: special case when before is empty and after isn't? 554 */ 555 556 if (block_ends_in_jump(before)) { 557 assert(exec_list_is_empty(&after->instr_list)); 558 if (after->successors[0]) 559 remove_phi_src(after->successors[0], after); 560 if (after->successors[1]) 561 remove_phi_src(after->successors[1], after); 562 unlink_block_successors(after); 563 exec_node_remove(&after->cf_node.node); 564 } else { 565 move_successors(after, before); 566 567 foreach_list_typed(nir_instr, instr, node, &after->instr_list) { 568 instr->block = before; 569 } 570 571 exec_list_append(&before->instr_list, &after->instr_list); 572 exec_node_remove(&after->cf_node.node); 573 } 574 } 575 576 void 577 nir_cf_node_insert(nir_cursor cursor, nir_cf_node *node) 578 { 579 nir_block *before, *after; 580 581 split_block_cursor(cursor, &before, &after); 582 583 if (node->type == nir_cf_node_block) { 584 nir_block *block = nir_cf_node_as_block(node); 585 exec_node_insert_after(&before->cf_node.node, &block->cf_node.node); 586 block->cf_node.parent = before->cf_node.parent; 587 /* stitch_blocks() assumes that any block that ends with a jump has 588 * already been setup with the correct successors, so we need to set 589 * up jumps here as the block is being inserted. 590 */ 591 if (block_ends_in_jump(block)) 592 nir_handle_add_jump(block); 593 594 stitch_blocks(block, after); 595 stitch_blocks(before, block); 596 } else { 597 update_if_uses(node); 598 insert_non_block(before, node, after); 599 } 600 } 601 602 static bool 603 replace_ssa_def_uses(nir_ssa_def *def, void *void_impl) 604 { 605 nir_function_impl *impl = void_impl; 606 void *mem_ctx = ralloc_parent(impl); 607 608 nir_ssa_undef_instr *undef = 609 nir_ssa_undef_instr_create(mem_ctx, def->num_components, 610 def->bit_size); 611 nir_instr_insert_before_cf_list(&impl->body, &undef->instr); 612 nir_ssa_def_rewrite_uses(def, nir_src_for_ssa(&undef->def)); 613 return true; 614 } 615 616 static void 617 cleanup_cf_node(nir_cf_node *node, nir_function_impl *impl) 618 { 619 switch (node->type) { 620 case nir_cf_node_block: { 621 nir_block *block = nir_cf_node_as_block(node); 622 /* We need to walk the instructions and clean up defs/uses */ 623 nir_foreach_instr_safe(instr, block) { 624 if (instr->type == nir_instr_type_jump) { 625 nir_jump_type jump_type = nir_instr_as_jump(instr)->type; 626 unlink_jump(block, jump_type, false); 627 } else { 628 nir_foreach_ssa_def(instr, replace_ssa_def_uses, impl); 629 nir_instr_remove(instr); 630 } 631 } 632 break; 633 } 634 635 case nir_cf_node_if: { 636 nir_if *if_stmt = nir_cf_node_as_if(node); 637 foreach_list_typed(nir_cf_node, child, node, &if_stmt->then_list) 638 cleanup_cf_node(child, impl); 639 foreach_list_typed(nir_cf_node, child, node, &if_stmt->else_list) 640 cleanup_cf_node(child, impl); 641 642 list_del(&if_stmt->condition.use_link); 643 break; 644 } 645 646 case nir_cf_node_loop: { 647 nir_loop *loop = nir_cf_node_as_loop(node); 648 foreach_list_typed(nir_cf_node, child, node, &loop->body) 649 cleanup_cf_node(child, impl); 650 break; 651 } 652 case nir_cf_node_function: { 653 nir_function_impl *impl = nir_cf_node_as_function(node); 654 foreach_list_typed(nir_cf_node, child, node, &impl->body) 655 cleanup_cf_node(child, impl); 656 break; 657 } 658 default: 659 unreachable("Invalid CF node type"); 660 } 661 } 662 663 void 664 nir_cf_extract(nir_cf_list *extracted, nir_cursor begin, nir_cursor end) 665 { 666 nir_block *block_begin, *block_end, *block_before, *block_after; 667 668 if (nir_cursors_equal(begin, end)) { 669 exec_list_make_empty(&extracted->list); 670 extracted->impl = NULL; /* we shouldn't need this */ 671 return; 672 } 673 674 /* In the case where begin points to an instruction in some basic block and 675 * end points to the end of the same basic block, we rely on the fact that 676 * splitting on an instruction moves earlier instructions into a new basic 677 * block. If the later instructions were moved instead, then the end cursor 678 * would be pointing to the same place that begin used to point to, which 679 * is obviously not what we want. 680 */ 681 split_block_cursor(begin, &block_before, &block_begin); 682 split_block_cursor(end, &block_end, &block_after); 683 684 extracted->impl = nir_cf_node_get_function(&block_begin->cf_node); 685 exec_list_make_empty(&extracted->list); 686 687 /* Dominance and other block-related information is toast. */ 688 nir_metadata_preserve(extracted->impl, nir_metadata_none); 689 690 nir_cf_node *cf_node = &block_begin->cf_node; 691 nir_cf_node *cf_node_end = &block_end->cf_node; 692 while (true) { 693 nir_cf_node *next = nir_cf_node_next(cf_node); 694 695 exec_node_remove(&cf_node->node); 696 cf_node->parent = NULL; 697 exec_list_push_tail(&extracted->list, &cf_node->node); 698 699 if (cf_node == cf_node_end) 700 break; 701 702 cf_node = next; 703 } 704 705 stitch_blocks(block_before, block_after); 706 } 707 708 void 709 nir_cf_reinsert(nir_cf_list *cf_list, nir_cursor cursor) 710 { 711 nir_block *before, *after; 712 713 if (exec_list_is_empty(&cf_list->list)) 714 return; 715 716 split_block_cursor(cursor, &before, &after); 717 718 foreach_list_typed_safe(nir_cf_node, node, node, &cf_list->list) { 719 exec_node_remove(&node->node); 720 node->parent = before->cf_node.parent; 721 exec_node_insert_node_before(&after->cf_node.node, &node->node); 722 } 723 724 stitch_blocks(before, 725 nir_cf_node_as_block(nir_cf_node_next(&before->cf_node))); 726 stitch_blocks(nir_cf_node_as_block(nir_cf_node_prev(&after->cf_node)), 727 after); 728 } 729 730 void 731 nir_cf_delete(nir_cf_list *cf_list) 732 { 733 foreach_list_typed(nir_cf_node, node, node, &cf_list->list) { 734 cleanup_cf_node(node, cf_list->impl); 735 } 736 } 737