2 * Copyright © 2014 Intel Corporation
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:
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
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
24 * Connor Abbott (cwabbott0@gmail.com)
28 #include "nir_control_flow_private.h"
31 * \name Control flow modification
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
37 * 2. Each if-statement and loop must have one basic block before it and one
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 * 5. The CFG must always be connected - this means that we must insert a fake
43 * CFG edge for loops with no break statement.
45 * The purpose of the second one is so that we have places to insert code during
46 * GCM, as well as eliminating the possibility of critical edges.
51 block_ends_in_jump(nir_block
*block
)
53 return !exec_list_is_empty(&block
->instr_list
) &&
54 nir_block_last_instr(block
)->type
== nir_instr_type_jump
;
58 block_add_pred(nir_block
*block
, nir_block
*pred
)
60 _mesa_set_add(block
->predecessors
, pred
);
64 block_remove_pred(nir_block
*block
, nir_block
*pred
)
66 struct set_entry
*entry
= _mesa_set_search(block
->predecessors
, pred
);
70 _mesa_set_remove(block
->predecessors
, entry
);
74 link_blocks(nir_block
*pred
, nir_block
*succ1
, nir_block
*succ2
)
76 pred
->successors
[0] = succ1
;
78 block_add_pred(succ1
, pred
);
80 pred
->successors
[1] = succ2
;
82 block_add_pred(succ2
, pred
);
86 unlink_blocks(nir_block
*pred
, nir_block
*succ
)
88 if (pred
->successors
[0] == succ
) {
89 pred
->successors
[0] = pred
->successors
[1];
90 pred
->successors
[1] = NULL
;
92 assert(pred
->successors
[1] == succ
);
93 pred
->successors
[1] = NULL
;
96 block_remove_pred(succ
, pred
);
100 unlink_block_successors(nir_block
*block
)
102 if (block
->successors
[1] != NULL
)
103 unlink_blocks(block
, block
->successors
[1]);
104 if (block
->successors
[0] != NULL
)
105 unlink_blocks(block
, block
->successors
[0]);
109 link_non_block_to_block(nir_cf_node
*node
, nir_block
*block
)
111 if (node
->type
== nir_cf_node_if
) {
113 * We're trying to link an if to a block after it; this just means linking
114 * the last block of the then and else branches.
117 nir_if
*if_stmt
= nir_cf_node_as_if(node
);
119 nir_cf_node
*last_then
= nir_if_last_then_node(if_stmt
);
120 assert(last_then
->type
== nir_cf_node_block
);
121 nir_block
*last_then_block
= nir_cf_node_as_block(last_then
);
123 nir_cf_node
*last_else
= nir_if_last_else_node(if_stmt
);
124 assert(last_else
->type
== nir_cf_node_block
);
125 nir_block
*last_else_block
= nir_cf_node_as_block(last_else
);
127 if (!block_ends_in_jump(last_then_block
)) {
128 unlink_block_successors(last_then_block
);
129 link_blocks(last_then_block
, block
, NULL
);
132 if (!block_ends_in_jump(last_else_block
)) {
133 unlink_block_successors(last_else_block
);
134 link_blocks(last_else_block
, block
, NULL
);
137 assert(node
->type
== nir_cf_node_loop
);
140 * We can only get to this codepath if we're inserting a new loop, or
141 * at least a loop with no break statements; we can't insert break
142 * statements into a loop when we haven't inserted it into the CFG
143 * because we wouldn't know which block comes after the loop
144 * and therefore, which block should be the successor of the block with
145 * the break). Therefore, we need to insert a fake edge (see invariant
149 nir_loop
*loop
= nir_cf_node_as_loop(node
);
151 nir_cf_node
*last
= nir_loop_last_cf_node(loop
);
152 assert(last
->type
== nir_cf_node_block
);
153 nir_block
*last_block
= nir_cf_node_as_block(last
);
155 last_block
->successors
[1] = block
;
156 block_add_pred(block
, last_block
);
161 link_block_to_non_block(nir_block
*block
, nir_cf_node
*node
)
163 if (node
->type
== nir_cf_node_if
) {
165 * We're trying to link a block to an if after it; this just means linking
166 * the block to the first block of the then and else branches.
169 nir_if
*if_stmt
= nir_cf_node_as_if(node
);
171 nir_cf_node
*first_then
= nir_if_first_then_node(if_stmt
);
172 assert(first_then
->type
== nir_cf_node_block
);
173 nir_block
*first_then_block
= nir_cf_node_as_block(first_then
);
175 nir_cf_node
*first_else
= nir_if_first_else_node(if_stmt
);
176 assert(first_else
->type
== nir_cf_node_block
);
177 nir_block
*first_else_block
= nir_cf_node_as_block(first_else
);
179 unlink_block_successors(block
);
180 link_blocks(block
, first_then_block
, first_else_block
);
183 * For similar reasons as the corresponding case in
184 * link_non_block_to_block(), don't worry about if the loop header has
185 * any predecessors that need to be unlinked.
188 assert(node
->type
== nir_cf_node_loop
);
190 nir_loop
*loop
= nir_cf_node_as_loop(node
);
192 nir_cf_node
*loop_header
= nir_loop_first_cf_node(loop
);
193 assert(loop_header
->type
== nir_cf_node_block
);
194 nir_block
*loop_header_block
= nir_cf_node_as_block(loop_header
);
196 unlink_block_successors(block
);
197 link_blocks(block
, loop_header_block
, NULL
);
203 * Replace a block's successor with a different one.
206 replace_successor(nir_block
*block
, nir_block
*old_succ
, nir_block
*new_succ
)
208 if (block
->successors
[0] == old_succ
) {
209 block
->successors
[0] = new_succ
;
211 assert(block
->successors
[1] == old_succ
);
212 block
->successors
[1] = new_succ
;
215 block_remove_pred(old_succ
, block
);
216 block_add_pred(new_succ
, block
);
220 * Takes a basic block and inserts a new empty basic block before it, making its
221 * predecessors point to the new block. This essentially splits the block into
222 * an empty header and a body so that another non-block CF node can be inserted
223 * between the two. Note that this does *not* link the two basic blocks, so
224 * some kind of cleanup *must* be performed after this call.
228 split_block_beginning(nir_block
*block
)
230 nir_block
*new_block
= nir_block_create(ralloc_parent(block
));
231 new_block
->cf_node
.parent
= block
->cf_node
.parent
;
232 exec_node_insert_node_before(&block
->cf_node
.node
, &new_block
->cf_node
.node
);
234 struct set_entry
*entry
;
235 set_foreach(block
->predecessors
, entry
) {
236 nir_block
*pred
= (nir_block
*) entry
->key
;
237 replace_successor(pred
, block
, new_block
);
240 /* Any phi nodes must stay part of the new block, or else their
241 * sourcse will be messed up. This will reverse the order of the phi's, but
242 * order shouldn't matter.
244 nir_foreach_instr_safe(block
, instr
) {
245 if (instr
->type
!= nir_instr_type_phi
)
248 exec_node_remove(&instr
->node
);
249 instr
->block
= new_block
;
250 exec_list_push_head(&new_block
->instr_list
, &instr
->node
);
257 rewrite_phi_preds(nir_block
*block
, nir_block
*old_pred
, nir_block
*new_pred
)
259 nir_foreach_instr_safe(block
, instr
) {
260 if (instr
->type
!= nir_instr_type_phi
)
263 nir_phi_instr
*phi
= nir_instr_as_phi(instr
);
264 nir_foreach_phi_src(phi
, src
) {
265 if (src
->pred
== old_pred
) {
266 src
->pred
= new_pred
;
274 insert_phi_undef(nir_block
*block
, nir_block
*pred
)
276 nir_function_impl
*impl
= nir_cf_node_get_function(&block
->cf_node
);
277 nir_foreach_instr(block
, instr
) {
278 if (instr
->type
!= nir_instr_type_phi
)
281 nir_phi_instr
*phi
= nir_instr_as_phi(instr
);
282 nir_ssa_undef_instr
*undef
=
283 nir_ssa_undef_instr_create(ralloc_parent(phi
),
284 phi
->dest
.ssa
.num_components
,
285 phi
->dest
.ssa
.bit_size
);
286 nir_instr_insert_before_cf_list(&impl
->body
, &undef
->instr
);
287 nir_phi_src
*src
= ralloc(phi
, nir_phi_src
);
289 src
->src
.parent_instr
= &phi
->instr
;
290 src
->src
.is_ssa
= true;
291 src
->src
.ssa
= &undef
->def
;
293 list_addtail(&src
->src
.use_link
, &undef
->def
.uses
);
295 exec_list_push_tail(&phi
->srcs
, &src
->node
);
300 * Moves the successors of source to the successors of dest, leaving both
301 * successors of source NULL.
305 move_successors(nir_block
*source
, nir_block
*dest
)
307 nir_block
*succ1
= source
->successors
[0];
308 nir_block
*succ2
= source
->successors
[1];
311 unlink_blocks(source
, succ1
);
312 rewrite_phi_preds(succ1
, source
, dest
);
316 unlink_blocks(source
, succ2
);
317 rewrite_phi_preds(succ2
, source
, dest
);
320 unlink_block_successors(dest
);
321 link_blocks(dest
, succ1
, succ2
);
324 /* Given a basic block with no successors that has been inserted into the
325 * control flow tree, gives it the successors it would normally have assuming
326 * it doesn't end in a jump instruction. Also inserts phi sources with undefs
330 block_add_normal_succs(nir_block
*block
)
332 if (exec_node_is_tail_sentinel(block
->cf_node
.node
.next
)) {
333 nir_cf_node
*parent
= block
->cf_node
.parent
;
334 if (parent
->type
== nir_cf_node_if
) {
335 nir_cf_node
*next
= nir_cf_node_next(parent
);
336 assert(next
->type
== nir_cf_node_block
);
337 nir_block
*next_block
= nir_cf_node_as_block(next
);
339 link_blocks(block
, next_block
, NULL
);
340 } else if (parent
->type
== nir_cf_node_loop
) {
341 nir_loop
*loop
= nir_cf_node_as_loop(parent
);
343 nir_cf_node
*head
= nir_loop_first_cf_node(loop
);
344 assert(head
->type
== nir_cf_node_block
);
345 nir_block
*head_block
= nir_cf_node_as_block(head
);
347 link_blocks(block
, head_block
, NULL
);
348 insert_phi_undef(head_block
, block
);
350 assert(parent
->type
== nir_cf_node_function
);
351 nir_function_impl
*impl
= nir_cf_node_as_function(parent
);
352 link_blocks(block
, impl
->end_block
, NULL
);
355 nir_cf_node
*next
= nir_cf_node_next(&block
->cf_node
);
356 if (next
->type
== nir_cf_node_if
) {
357 nir_if
*next_if
= nir_cf_node_as_if(next
);
359 nir_cf_node
*first_then
= nir_if_first_then_node(next_if
);
360 assert(first_then
->type
== nir_cf_node_block
);
361 nir_block
*first_then_block
= nir_cf_node_as_block(first_then
);
363 nir_cf_node
*first_else
= nir_if_first_else_node(next_if
);
364 assert(first_else
->type
== nir_cf_node_block
);
365 nir_block
*first_else_block
= nir_cf_node_as_block(first_else
);
367 link_blocks(block
, first_then_block
, first_else_block
);
369 assert(next
->type
== nir_cf_node_loop
);
370 nir_loop
*next_loop
= nir_cf_node_as_loop(next
);
372 nir_cf_node
*first
= nir_loop_first_cf_node(next_loop
);
373 assert(first
->type
== nir_cf_node_block
);
374 nir_block
*first_block
= nir_cf_node_as_block(first
);
376 link_blocks(block
, first_block
, NULL
);
377 insert_phi_undef(first_block
, block
);
383 split_block_end(nir_block
*block
)
385 nir_block
*new_block
= nir_block_create(ralloc_parent(block
));
386 new_block
->cf_node
.parent
= block
->cf_node
.parent
;
387 exec_node_insert_after(&block
->cf_node
.node
, &new_block
->cf_node
.node
);
389 if (block_ends_in_jump(block
)) {
390 /* Figure out what successor block would've had if it didn't have a jump
391 * instruction, and make new_block have that successor.
393 block_add_normal_succs(new_block
);
395 move_successors(block
, new_block
);
402 split_block_before_instr(nir_instr
*instr
)
404 assert(instr
->type
!= nir_instr_type_phi
);
405 nir_block
*new_block
= split_block_beginning(instr
->block
);
407 nir_foreach_instr_safe(instr
->block
, cur_instr
) {
408 if (cur_instr
== instr
)
411 exec_node_remove(&cur_instr
->node
);
412 cur_instr
->block
= new_block
;
413 exec_list_push_tail(&new_block
->instr_list
, &cur_instr
->node
);
419 /* Splits a basic block at the point specified by the cursor. The "before" and
420 * "after" arguments are filled out with the blocks resulting from the split
421 * if non-NULL. Note that the "beginning" of the block is actually interpreted
422 * as before the first non-phi instruction, and it's illegal to split a block
423 * before a phi instruction.
427 split_block_cursor(nir_cursor cursor
,
428 nir_block
**_before
, nir_block
**_after
)
430 nir_block
*before
, *after
;
431 switch (cursor
.option
) {
432 case nir_cursor_before_block
:
433 after
= cursor
.block
;
434 before
= split_block_beginning(cursor
.block
);
437 case nir_cursor_after_block
:
438 before
= cursor
.block
;
439 after
= split_block_end(cursor
.block
);
442 case nir_cursor_before_instr
:
443 after
= cursor
.instr
->block
;
444 before
= split_block_before_instr(cursor
.instr
);
447 case nir_cursor_after_instr
:
448 /* We lower this to split_block_before_instr() so that we can keep the
449 * after-a-jump-instr case contained to split_block_end().
451 if (nir_instr_is_last(cursor
.instr
)) {
452 before
= cursor
.instr
->block
;
453 after
= split_block_end(cursor
.instr
->block
);
455 after
= cursor
.instr
->block
;
456 before
= split_block_before_instr(nir_instr_next(cursor
.instr
));
461 unreachable("not reached");
471 * Inserts a non-basic block between two basic blocks and links them together.
475 insert_non_block(nir_block
*before
, nir_cf_node
*node
, nir_block
*after
)
477 node
->parent
= before
->cf_node
.parent
;
478 exec_node_insert_after(&before
->cf_node
.node
, &node
->node
);
479 link_block_to_non_block(before
, node
);
480 link_non_block_to_block(node
, after
);
483 /* walk up the control flow tree to find the innermost enclosed loop */
485 nearest_loop(nir_cf_node
*node
)
487 while (node
->type
!= nir_cf_node_loop
) {
491 return nir_cf_node_as_loop(node
);
495 * update the CFG after a jump instruction has been added to the end of a block
499 nir_handle_add_jump(nir_block
*block
)
501 nir_instr
*instr
= nir_block_last_instr(block
);
502 nir_jump_instr
*jump_instr
= nir_instr_as_jump(instr
);
504 unlink_block_successors(block
);
506 nir_function_impl
*impl
= nir_cf_node_get_function(&block
->cf_node
);
507 nir_metadata_preserve(impl
, nir_metadata_none
);
509 if (jump_instr
->type
== nir_jump_break
||
510 jump_instr
->type
== nir_jump_continue
) {
511 nir_loop
*loop
= nearest_loop(&block
->cf_node
);
513 if (jump_instr
->type
== nir_jump_continue
) {
514 nir_cf_node
*first_node
= nir_loop_first_cf_node(loop
);
515 assert(first_node
->type
== nir_cf_node_block
);
516 nir_block
*first_block
= nir_cf_node_as_block(first_node
);
517 link_blocks(block
, first_block
, NULL
);
519 nir_cf_node
*after
= nir_cf_node_next(&loop
->cf_node
);
520 assert(after
->type
== nir_cf_node_block
);
521 nir_block
*after_block
= nir_cf_node_as_block(after
);
522 link_blocks(block
, after_block
, NULL
);
524 /* If we inserted a fake link, remove it */
525 nir_cf_node
*last
= nir_loop_last_cf_node(loop
);
526 assert(last
->type
== nir_cf_node_block
);
527 nir_block
*last_block
= nir_cf_node_as_block(last
);
528 if (last_block
->successors
[1] != NULL
)
529 unlink_blocks(last_block
, after_block
);
532 assert(jump_instr
->type
== nir_jump_return
);
533 link_blocks(block
, impl
->end_block
, NULL
);
538 remove_phi_src(nir_block
*block
, nir_block
*pred
)
540 nir_foreach_instr(block
, instr
) {
541 if (instr
->type
!= nir_instr_type_phi
)
544 nir_phi_instr
*phi
= nir_instr_as_phi(instr
);
545 nir_foreach_phi_src_safe(phi
, src
) {
546 if (src
->pred
== pred
) {
547 list_del(&src
->src
.use_link
);
548 exec_node_remove(&src
->node
);
554 /* Removes the successor of a block with a jump, and inserts a fake edge for
555 * infinite loops. Note that the jump to be eliminated may be free-floating.
559 unlink_jump(nir_block
*block
, nir_jump_type type
, bool add_normal_successors
)
561 nir_block
*next
= block
->successors
[0];
563 if (block
->successors
[0])
564 remove_phi_src(block
->successors
[0], block
);
565 if (block
->successors
[1])
566 remove_phi_src(block
->successors
[1], block
);
568 unlink_block_successors(block
);
569 if (add_normal_successors
)
570 block_add_normal_succs(block
);
572 /* If we've just removed a break, and the block we were jumping to (after
573 * the loop) now has zero predecessors, we've created a new infinite loop.
575 * NIR doesn't allow blocks (other than the start block) to have zero
576 * predecessors. In particular, dominance assumes all blocks are reachable.
577 * So, we insert a "fake link" by making successors[1] point after the loop.
579 * Note that we have to do this after unlinking/recreating the block's
580 * successors. If we removed a "break" at the end of the loop, then
581 * block == last_block, so block->successors[0] would already be "next",
582 * and adding a fake link would create two identical successors. Doing
583 * this afterward works, as we'll have changed block->successors[0] to
584 * be the top of the loop.
586 if (type
== nir_jump_break
&& next
->predecessors
->entries
== 0) {
588 nir_cf_node_as_loop(nir_cf_node_prev(&next
->cf_node
));
590 /* insert fake link */
591 nir_cf_node
*last
= nir_loop_last_cf_node(loop
);
592 assert(last
->type
== nir_cf_node_block
);
593 nir_block
*last_block
= nir_cf_node_as_block(last
);
595 last_block
->successors
[1] = next
;
596 block_add_pred(next
, last_block
);
601 nir_handle_remove_jump(nir_block
*block
, nir_jump_type type
)
603 unlink_jump(block
, type
, true);
605 nir_function_impl
*impl
= nir_cf_node_get_function(&block
->cf_node
);
606 nir_metadata_preserve(impl
, nir_metadata_none
);
610 update_if_uses(nir_cf_node
*node
)
612 if (node
->type
!= nir_cf_node_if
)
615 nir_if
*if_stmt
= nir_cf_node_as_if(node
);
617 if_stmt
->condition
.parent_if
= if_stmt
;
618 if (if_stmt
->condition
.is_ssa
) {
619 list_addtail(&if_stmt
->condition
.use_link
,
620 &if_stmt
->condition
.ssa
->if_uses
);
622 list_addtail(&if_stmt
->condition
.use_link
,
623 &if_stmt
->condition
.reg
.reg
->if_uses
);
628 * Stitch two basic blocks together into one. The aggregate must have the same
629 * predecessors as the first and the same successors as the second.
633 stitch_blocks(nir_block
*before
, nir_block
*after
)
636 * We move after into before, so we have to deal with up to 2 successors vs.
637 * possibly a large number of predecessors.
639 * TODO: special case when before is empty and after isn't?
642 if (block_ends_in_jump(before
)) {
643 assert(exec_list_is_empty(&after
->instr_list
));
644 if (after
->successors
[0])
645 remove_phi_src(after
->successors
[0], after
);
646 if (after
->successors
[1])
647 remove_phi_src(after
->successors
[1], after
);
648 unlink_block_successors(after
);
649 exec_node_remove(&after
->cf_node
.node
);
651 move_successors(after
, before
);
653 foreach_list_typed(nir_instr
, instr
, node
, &after
->instr_list
) {
654 instr
->block
= before
;
657 exec_list_append(&before
->instr_list
, &after
->instr_list
);
658 exec_node_remove(&after
->cf_node
.node
);
663 nir_cf_node_insert(nir_cursor cursor
, nir_cf_node
*node
)
665 nir_block
*before
, *after
;
667 split_block_cursor(cursor
, &before
, &after
);
669 if (node
->type
== nir_cf_node_block
) {
670 nir_block
*block
= nir_cf_node_as_block(node
);
671 exec_node_insert_after(&before
->cf_node
.node
, &block
->cf_node
.node
);
672 block
->cf_node
.parent
= before
->cf_node
.parent
;
673 /* stitch_blocks() assumes that any block that ends with a jump has
674 * already been setup with the correct successors, so we need to set
675 * up jumps here as the block is being inserted.
677 if (block_ends_in_jump(block
))
678 nir_handle_add_jump(block
);
680 stitch_blocks(block
, after
);
681 stitch_blocks(before
, block
);
683 update_if_uses(node
);
684 insert_non_block(before
, node
, after
);
689 replace_ssa_def_uses(nir_ssa_def
*def
, void *void_impl
)
691 nir_function_impl
*impl
= void_impl
;
692 void *mem_ctx
= ralloc_parent(impl
);
694 nir_ssa_undef_instr
*undef
=
695 nir_ssa_undef_instr_create(mem_ctx
, def
->num_components
,
697 nir_instr_insert_before_cf_list(&impl
->body
, &undef
->instr
);
698 nir_ssa_def_rewrite_uses(def
, nir_src_for_ssa(&undef
->def
));
703 cleanup_cf_node(nir_cf_node
*node
, nir_function_impl
*impl
)
705 switch (node
->type
) {
706 case nir_cf_node_block
: {
707 nir_block
*block
= nir_cf_node_as_block(node
);
708 /* We need to walk the instructions and clean up defs/uses */
709 nir_foreach_instr_safe(block
, instr
) {
710 if (instr
->type
== nir_instr_type_jump
) {
711 nir_jump_type jump_type
= nir_instr_as_jump(instr
)->type
;
712 unlink_jump(block
, jump_type
, false);
714 nir_foreach_ssa_def(instr
, replace_ssa_def_uses
, impl
);
715 nir_instr_remove(instr
);
721 case nir_cf_node_if
: {
722 nir_if
*if_stmt
= nir_cf_node_as_if(node
);
723 foreach_list_typed(nir_cf_node
, child
, node
, &if_stmt
->then_list
)
724 cleanup_cf_node(child
, impl
);
725 foreach_list_typed(nir_cf_node
, child
, node
, &if_stmt
->else_list
)
726 cleanup_cf_node(child
, impl
);
728 list_del(&if_stmt
->condition
.use_link
);
732 case nir_cf_node_loop
: {
733 nir_loop
*loop
= nir_cf_node_as_loop(node
);
734 foreach_list_typed(nir_cf_node
, child
, node
, &loop
->body
)
735 cleanup_cf_node(child
, impl
);
738 case nir_cf_node_function
: {
739 nir_function_impl
*impl
= nir_cf_node_as_function(node
);
740 foreach_list_typed(nir_cf_node
, child
, node
, &impl
->body
)
741 cleanup_cf_node(child
, impl
);
745 unreachable("Invalid CF node type");
750 nir_cf_extract(nir_cf_list
*extracted
, nir_cursor begin
, nir_cursor end
)
752 nir_block
*block_begin
, *block_end
, *block_before
, *block_after
;
754 if (nir_cursors_equal(begin
, end
)) {
755 exec_list_make_empty(&extracted
->list
);
756 extracted
->impl
= NULL
; /* we shouldn't need this */
760 /* In the case where begin points to an instruction in some basic block and
761 * end points to the end of the same basic block, we rely on the fact that
762 * splitting on an instruction moves earlier instructions into a new basic
763 * block. If the later instructions were moved instead, then the end cursor
764 * would be pointing to the same place that begin used to point to, which
765 * is obviously not what we want.
767 split_block_cursor(begin
, &block_before
, &block_begin
);
768 split_block_cursor(end
, &block_end
, &block_after
);
770 extracted
->impl
= nir_cf_node_get_function(&block_begin
->cf_node
);
771 exec_list_make_empty(&extracted
->list
);
773 /* Dominance and other block-related information is toast. */
774 nir_metadata_preserve(extracted
->impl
, nir_metadata_none
);
776 nir_cf_node
*cf_node
= &block_begin
->cf_node
;
777 nir_cf_node
*cf_node_end
= &block_end
->cf_node
;
779 nir_cf_node
*next
= nir_cf_node_next(cf_node
);
781 exec_node_remove(&cf_node
->node
);
782 cf_node
->parent
= NULL
;
783 exec_list_push_tail(&extracted
->list
, &cf_node
->node
);
785 if (cf_node
== cf_node_end
)
791 stitch_blocks(block_before
, block_after
);
795 nir_cf_reinsert(nir_cf_list
*cf_list
, nir_cursor cursor
)
797 nir_block
*before
, *after
;
799 if (exec_list_is_empty(&cf_list
->list
))
802 split_block_cursor(cursor
, &before
, &after
);
804 foreach_list_typed_safe(nir_cf_node
, node
, node
, &cf_list
->list
) {
805 exec_node_remove(&node
->node
);
806 node
->parent
= before
->cf_node
.parent
;
807 exec_node_insert_node_before(&after
->cf_node
.node
, &node
->node
);
810 stitch_blocks(before
,
811 nir_cf_node_as_block(nir_cf_node_next(&before
->cf_node
)));
812 stitch_blocks(nir_cf_node_as_block(nir_cf_node_prev(&after
->cf_node
)),
817 nir_cf_delete(nir_cf_list
*cf_list
)
819 foreach_list_typed(nir_cf_node
, node
, node
, &cf_list
->list
) {
820 cleanup_cf_node(node
, cf_list
->impl
);