src/compiler/nir/nir_control_flow.c

   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 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 }