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_add_pred(nir_block
*block
, nir_block
*pred
)
53 _mesa_set_add(block
->predecessors
, pred
);
57 link_blocks(nir_block
*pred
, nir_block
*succ1
, nir_block
*succ2
)
59 pred
->successors
[0] = succ1
;
61 block_add_pred(succ1
, pred
);
63 pred
->successors
[1] = succ2
;
65 block_add_pred(succ2
, pred
);
69 unlink_blocks(nir_block
*pred
, nir_block
*succ
)
71 if (pred
->successors
[0] == succ
) {
72 pred
->successors
[0] = pred
->successors
[1];
73 pred
->successors
[1] = NULL
;
75 assert(pred
->successors
[1] == succ
);
76 pred
->successors
[1] = NULL
;
79 struct set_entry
*entry
= _mesa_set_search(succ
->predecessors
, pred
);
83 _mesa_set_remove(succ
->predecessors
, entry
);
87 unlink_block_successors(nir_block
*block
)
89 if (block
->successors
[0] != NULL
)
90 unlink_blocks(block
, block
->successors
[0]);
91 if (block
->successors
[1] != NULL
)
92 unlink_blocks(block
, block
->successors
[1]);
96 link_non_block_to_block(nir_cf_node
*node
, nir_block
*block
)
98 if (node
->type
== nir_cf_node_if
) {
100 * We're trying to link an if to a block after it; this just means linking
101 * the last block of the then and else branches.
104 nir_if
*if_stmt
= nir_cf_node_as_if(node
);
106 nir_cf_node
*last_then
= nir_if_last_then_node(if_stmt
);
107 assert(last_then
->type
== nir_cf_node_block
);
108 nir_block
*last_then_block
= nir_cf_node_as_block(last_then
);
110 nir_cf_node
*last_else
= nir_if_last_else_node(if_stmt
);
111 assert(last_else
->type
== nir_cf_node_block
);
112 nir_block
*last_else_block
= nir_cf_node_as_block(last_else
);
114 if (exec_list_is_empty(&last_then_block
->instr_list
) ||
115 nir_block_last_instr(last_then_block
)->type
!= nir_instr_type_jump
) {
116 unlink_block_successors(last_then_block
);
117 link_blocks(last_then_block
, block
, NULL
);
120 if (exec_list_is_empty(&last_else_block
->instr_list
) ||
121 nir_block_last_instr(last_else_block
)->type
!= nir_instr_type_jump
) {
122 unlink_block_successors(last_else_block
);
123 link_blocks(last_else_block
, block
, NULL
);
126 assert(node
->type
== nir_cf_node_loop
);
129 * We can only get to this codepath if we're inserting a new loop, or
130 * at least a loop with no break statements; we can't insert break
131 * statements into a loop when we haven't inserted it into the CFG
132 * because we wouldn't know which block comes after the loop
133 * and therefore, which block should be the successor of the block with
134 * the break). Therefore, we need to insert a fake edge (see invariant
138 nir_loop
*loop
= nir_cf_node_as_loop(node
);
140 nir_cf_node
*last
= nir_loop_last_cf_node(loop
);
141 assert(last
->type
== nir_cf_node_block
);
142 nir_block
*last_block
= nir_cf_node_as_block(last
);
144 last_block
->successors
[1] = block
;
145 block_add_pred(block
, last_block
);
150 link_block_to_non_block(nir_block
*block
, nir_cf_node
*node
)
152 if (node
->type
== nir_cf_node_if
) {
154 * We're trying to link a block to an if after it; this just means linking
155 * the block to the first block of the then and else branches.
158 nir_if
*if_stmt
= nir_cf_node_as_if(node
);
160 nir_cf_node
*first_then
= nir_if_first_then_node(if_stmt
);
161 assert(first_then
->type
== nir_cf_node_block
);
162 nir_block
*first_then_block
= nir_cf_node_as_block(first_then
);
164 nir_cf_node
*first_else
= nir_if_first_else_node(if_stmt
);
165 assert(first_else
->type
== nir_cf_node_block
);
166 nir_block
*first_else_block
= nir_cf_node_as_block(first_else
);
168 unlink_block_successors(block
);
169 link_blocks(block
, first_then_block
, first_else_block
);
172 * For similar reasons as the corresponding case in
173 * link_non_block_to_block(), don't worry about if the loop header has
174 * any predecessors that need to be unlinked.
177 assert(node
->type
== nir_cf_node_loop
);
179 nir_loop
*loop
= nir_cf_node_as_loop(node
);
181 nir_cf_node
*loop_header
= nir_loop_first_cf_node(loop
);
182 assert(loop_header
->type
== nir_cf_node_block
);
183 nir_block
*loop_header_block
= nir_cf_node_as_block(loop_header
);
185 unlink_block_successors(block
);
186 link_blocks(block
, loop_header_block
, NULL
);
192 * Takes a basic block and inserts a new empty basic block before it, making its
193 * predecessors point to the new block. This essentially splits the block into
194 * an empty header and a body so that another non-block CF node can be inserted
195 * between the two. Note that this does *not* link the two basic blocks, so
196 * some kind of cleanup *must* be performed after this call.
200 split_block_beginning(nir_block
*block
)
202 nir_block
*new_block
= nir_block_create(ralloc_parent(block
));
203 new_block
->cf_node
.parent
= block
->cf_node
.parent
;
204 exec_node_insert_node_before(&block
->cf_node
.node
, &new_block
->cf_node
.node
);
206 struct set_entry
*entry
;
207 set_foreach(block
->predecessors
, entry
) {
208 nir_block
*pred
= (nir_block
*) entry
->key
;
210 unlink_blocks(pred
, block
);
211 link_blocks(pred
, new_block
, NULL
);
214 /* Any phi nodes must stay part of the new block, or else their
215 * sourcse will be messed up. This will reverse the order of the phi's, but
216 * order shouldn't matter.
218 nir_foreach_instr_safe(block
, instr
) {
219 if (instr
->type
!= nir_instr_type_phi
)
222 exec_node_remove(&instr
->node
);
223 instr
->block
= new_block
;
224 exec_list_push_head(&new_block
->instr_list
, &instr
->node
);
231 rewrite_phi_preds(nir_block
*block
, nir_block
*old_pred
, nir_block
*new_pred
)
233 nir_foreach_instr_safe(block
, instr
) {
234 if (instr
->type
!= nir_instr_type_phi
)
237 nir_phi_instr
*phi
= nir_instr_as_phi(instr
);
238 nir_foreach_phi_src(phi
, src
) {
239 if (src
->pred
== old_pred
) {
240 src
->pred
= new_pred
;
248 insert_phi_undef(nir_block
*block
, nir_block
*pred
)
250 nir_function_impl
*impl
= nir_cf_node_get_function(&block
->cf_node
);
251 nir_foreach_instr(block
, instr
) {
252 if (instr
->type
!= nir_instr_type_phi
)
255 nir_phi_instr
*phi
= nir_instr_as_phi(instr
);
256 nir_ssa_undef_instr
*undef
=
257 nir_ssa_undef_instr_create(ralloc_parent(phi
),
258 phi
->dest
.ssa
.num_components
);
259 nir_instr_insert_before_cf_list(&impl
->body
, &undef
->instr
);
260 nir_phi_src
*src
= ralloc(phi
, nir_phi_src
);
262 src
->src
.parent_instr
= &phi
->instr
;
263 src
->src
.is_ssa
= true;
264 src
->src
.ssa
= &undef
->def
;
266 list_addtail(&src
->src
.use_link
, &undef
->def
.uses
);
268 exec_list_push_tail(&phi
->srcs
, &src
->node
);
273 * Moves the successors of source to the successors of dest, leaving both
274 * successors of source NULL.
278 move_successors(nir_block
*source
, nir_block
*dest
)
280 nir_block
*succ1
= source
->successors
[0];
281 nir_block
*succ2
= source
->successors
[1];
284 unlink_blocks(source
, succ1
);
285 rewrite_phi_preds(succ1
, source
, dest
);
289 unlink_blocks(source
, succ2
);
290 rewrite_phi_preds(succ2
, source
, dest
);
293 unlink_block_successors(dest
);
294 link_blocks(dest
, succ1
, succ2
);
298 block_ends_in_jump(nir_block
*block
)
300 return !exec_list_is_empty(&block
->instr_list
) &&
301 nir_block_last_instr(block
)->type
== nir_instr_type_jump
;
305 /* Given a basic block with no successors that has been inserted into the
306 * control flow tree, gives it the successors it would normally have assuming
307 * it doesn't end in a jump instruction. Also inserts phi sources with undefs
311 block_add_normal_succs(nir_block
*block
)
313 if (exec_node_is_tail_sentinel(block
->cf_node
.node
.next
)) {
314 nir_cf_node
*parent
= block
->cf_node
.parent
;
315 if (parent
->type
== nir_cf_node_if
) {
316 nir_cf_node
*next
= nir_cf_node_next(parent
);
317 assert(next
->type
== nir_cf_node_block
);
318 nir_block
*next_block
= nir_cf_node_as_block(next
);
320 link_blocks(block
, next_block
, NULL
);
322 assert(parent
->type
== nir_cf_node_loop
);
323 nir_loop
*loop
= nir_cf_node_as_loop(parent
);
325 nir_cf_node
*head
= nir_loop_first_cf_node(loop
);
326 assert(head
->type
== nir_cf_node_block
);
327 nir_block
*head_block
= nir_cf_node_as_block(head
);
329 link_blocks(block
, head_block
, NULL
);
330 insert_phi_undef(head_block
, block
);
333 nir_cf_node
*next
= nir_cf_node_next(&block
->cf_node
);
334 if (next
->type
== nir_cf_node_if
) {
335 nir_if
*next_if
= nir_cf_node_as_if(next
);
337 nir_cf_node
*first_then
= nir_if_first_then_node(next_if
);
338 assert(first_then
->type
== nir_cf_node_block
);
339 nir_block
*first_then_block
= nir_cf_node_as_block(first_then
);
341 nir_cf_node
*first_else
= nir_if_first_else_node(next_if
);
342 assert(first_else
->type
== nir_cf_node_block
);
343 nir_block
*first_else_block
= nir_cf_node_as_block(first_else
);
345 link_blocks(block
, first_then_block
, first_else_block
);
347 assert(next
->type
== nir_cf_node_loop
);
348 nir_loop
*next_loop
= nir_cf_node_as_loop(next
);
350 nir_cf_node
*first
= nir_loop_first_cf_node(next_loop
);
351 assert(first
->type
== nir_cf_node_block
);
352 nir_block
*first_block
= nir_cf_node_as_block(first
);
354 link_blocks(block
, first_block
, NULL
);
355 insert_phi_undef(first_block
, block
);
361 split_block_end(nir_block
*block
)
363 nir_block
*new_block
= nir_block_create(ralloc_parent(block
));
364 new_block
->cf_node
.parent
= block
->cf_node
.parent
;
365 exec_node_insert_after(&block
->cf_node
.node
, &new_block
->cf_node
.node
);
367 if (block_ends_in_jump(block
)) {
368 /* Figure out what successor block would've had if it didn't have a jump
369 * instruction, and make new_block have that successor.
371 block_add_normal_succs(new_block
);
373 move_successors(block
, new_block
);
380 split_block_before_instr(nir_instr
*instr
)
382 assert(instr
->type
!= nir_instr_type_phi
);
383 nir_block
*new_block
= split_block_beginning(instr
->block
);
385 nir_foreach_instr_safe(instr
->block
, cur_instr
) {
386 if (cur_instr
== instr
)
389 exec_node_remove(&cur_instr
->node
);
390 cur_instr
->block
= new_block
;
391 exec_list_push_tail(&new_block
->instr_list
, &cur_instr
->node
);
397 /* Splits a basic block at the point specified by the cursor. The "before" and
398 * "after" arguments are filled out with the blocks resulting from the split
399 * if non-NULL. Note that the "beginning" of the block is actually interpreted
400 * as before the first non-phi instruction, and it's illegal to split a block
401 * before a phi instruction.
405 split_block_cursor(nir_cursor cursor
,
406 nir_block
**_before
, nir_block
**_after
)
408 nir_block
*before
, *after
;
409 switch (cursor
.option
) {
410 case nir_cursor_before_block
:
411 after
= cursor
.block
;
412 before
= split_block_beginning(cursor
.block
);
415 case nir_cursor_after_block
:
416 before
= cursor
.block
;
417 after
= split_block_end(cursor
.block
);
420 case nir_cursor_before_instr
:
421 after
= cursor
.instr
->block
;
422 before
= split_block_before_instr(cursor
.instr
);
425 case nir_cursor_after_instr
:
426 /* We lower this to split_block_before_instr() so that we can keep the
427 * after-a-jump-instr case contained to split_block_end().
429 if (nir_instr_is_last(cursor
.instr
)) {
430 before
= cursor
.instr
->block
;
431 after
= split_block_end(cursor
.instr
->block
);
433 after
= cursor
.instr
->block
;
434 before
= split_block_before_instr(nir_instr_next(cursor
.instr
));
446 * Inserts a non-basic block between two basic blocks and links them together.
450 insert_non_block(nir_block
*before
, nir_cf_node
*node
, nir_block
*after
)
452 node
->parent
= before
->cf_node
.parent
;
453 exec_node_insert_after(&before
->cf_node
.node
, &node
->node
);
454 link_block_to_non_block(before
, node
);
455 link_non_block_to_block(node
, after
);
459 * Inserts a non-basic block before a basic block.
463 insert_non_block_before_block(nir_cf_node
*node
, nir_block
*block
)
465 /* split off the beginning of block into new_block */
466 nir_block
*new_block
= split_block_beginning(block
);
468 /* insert our node in between new_block and block */
469 insert_non_block(new_block
, node
, block
);
472 /* walk up the control flow tree to find the innermost enclosed loop */
474 nearest_loop(nir_cf_node
*node
)
476 while (node
->type
!= nir_cf_node_loop
) {
480 return nir_cf_node_as_loop(node
);
484 * update the CFG after a jump instruction has been added to the end of a block
488 nir_handle_add_jump(nir_block
*block
)
490 nir_instr
*instr
= nir_block_last_instr(block
);
491 nir_jump_instr
*jump_instr
= nir_instr_as_jump(instr
);
493 unlink_block_successors(block
);
495 nir_function_impl
*impl
= nir_cf_node_get_function(&block
->cf_node
);
496 nir_metadata_preserve(impl
, nir_metadata_none
);
498 if (jump_instr
->type
== nir_jump_break
||
499 jump_instr
->type
== nir_jump_continue
) {
500 nir_loop
*loop
= nearest_loop(&block
->cf_node
);
502 if (jump_instr
->type
== nir_jump_continue
) {
503 nir_cf_node
*first_node
= nir_loop_first_cf_node(loop
);
504 assert(first_node
->type
== nir_cf_node_block
);
505 nir_block
*first_block
= nir_cf_node_as_block(first_node
);
506 link_blocks(block
, first_block
, NULL
);
508 nir_cf_node
*after
= nir_cf_node_next(&loop
->cf_node
);
509 assert(after
->type
== nir_cf_node_block
);
510 nir_block
*after_block
= nir_cf_node_as_block(after
);
511 link_blocks(block
, after_block
, NULL
);
513 /* If we inserted a fake link, remove it */
514 nir_cf_node
*last
= nir_loop_last_cf_node(loop
);
515 assert(last
->type
== nir_cf_node_block
);
516 nir_block
*last_block
= nir_cf_node_as_block(last
);
517 if (last_block
->successors
[1] != NULL
)
518 unlink_blocks(last_block
, after_block
);
521 assert(jump_instr
->type
== nir_jump_return
);
522 link_blocks(block
, impl
->end_block
, NULL
);
527 remove_phi_src(nir_block
*block
, nir_block
*pred
)
529 nir_foreach_instr(block
, instr
) {
530 if (instr
->type
!= nir_instr_type_phi
)
533 nir_phi_instr
*phi
= nir_instr_as_phi(instr
);
534 nir_foreach_phi_src_safe(phi
, src
) {
535 if (src
->pred
== pred
) {
536 list_del(&src
->src
.use_link
);
537 exec_node_remove(&src
->node
);
543 /* Removes the successor of a block with a jump, and inserts a fake edge for
544 * infinite loops. Note that the jump to be eliminated may be free-floating.
548 void unlink_jump(nir_block
*block
, nir_jump_type type
)
550 if (block
->successors
[0])
551 remove_phi_src(block
->successors
[0], block
);
552 if (block
->successors
[1])
553 remove_phi_src(block
->successors
[1], block
);
555 if (type
== nir_jump_break
) {
556 nir_block
*next
= block
->successors
[0];
558 if (next
->predecessors
->entries
== 1) {
560 nir_cf_node_as_loop(nir_cf_node_prev(&next
->cf_node
));
562 /* insert fake link */
563 nir_cf_node
*last
= nir_loop_last_cf_node(loop
);
564 assert(last
->type
== nir_cf_node_block
);
565 nir_block
*last_block
= nir_cf_node_as_block(last
);
567 last_block
->successors
[1] = next
;
568 block_add_pred(next
, last_block
);
572 unlink_block_successors(block
);
576 nir_handle_remove_jump(nir_block
*block
, nir_jump_type type
)
578 unlink_jump(block
, type
);
580 block_add_normal_succs(block
);
582 nir_function_impl
*impl
= nir_cf_node_get_function(&block
->cf_node
);
583 nir_metadata_preserve(impl
, nir_metadata_none
);
587 insert_non_block_after_block(nir_block
*block
, nir_cf_node
*node
)
589 /* split off the end of block into new_block */
590 nir_block
*new_block
= split_block_end(block
);
592 /* insert our node in between block and new_block */
593 insert_non_block(block
, node
, new_block
);
597 * Inserts a basic block before another by merging the instructions.
599 * @param block the target of the insertion
600 * @param before the block to be inserted - must not have been inserted before
601 * @param has_jump whether \before has a jump instruction at the end
605 insert_block_before_block(nir_block
*block
, nir_block
*before
, bool has_jump
)
607 assert(!has_jump
|| exec_list_is_empty(&block
->instr_list
));
609 foreach_list_typed(nir_instr
, instr
, node
, &before
->instr_list
) {
610 instr
->block
= block
;
613 exec_list_prepend(&block
->instr_list
, &before
->instr_list
);
616 nir_handle_add_jump(block
);
620 * Inserts a basic block after another by merging the instructions.
622 * @param block the target of the insertion
623 * @param after the block to be inserted - must not have been inserted before
624 * @param has_jump whether \after has a jump instruction at the end
628 insert_block_after_block(nir_block
*block
, nir_block
*after
, bool has_jump
)
630 foreach_list_typed(nir_instr
, instr
, node
, &after
->instr_list
) {
631 instr
->block
= block
;
634 exec_list_append(&block
->instr_list
, &after
->instr_list
);
637 nir_handle_add_jump(block
);
641 update_if_uses(nir_cf_node
*node
)
643 if (node
->type
!= nir_cf_node_if
)
646 nir_if
*if_stmt
= nir_cf_node_as_if(node
);
648 if_stmt
->condition
.parent_if
= if_stmt
;
649 if (if_stmt
->condition
.is_ssa
) {
650 list_addtail(&if_stmt
->condition
.use_link
,
651 &if_stmt
->condition
.ssa
->if_uses
);
653 list_addtail(&if_stmt
->condition
.use_link
,
654 &if_stmt
->condition
.reg
.reg
->if_uses
);
659 nir_cf_node_insert_after(nir_cf_node
*node
, nir_cf_node
*after
)
661 update_if_uses(after
);
663 if (after
->type
== nir_cf_node_block
) {
665 * either node or the one after it must be a basic block, by invariant #2;
666 * in either case, just merge the blocks together.
668 nir_block
*after_block
= nir_cf_node_as_block(after
);
670 bool has_jump
= !exec_list_is_empty(&after_block
->instr_list
) &&
671 nir_block_last_instr(after_block
)->type
== nir_instr_type_jump
;
673 if (node
->type
== nir_cf_node_block
) {
674 insert_block_after_block(nir_cf_node_as_block(node
), after_block
,
677 nir_cf_node
*next
= nir_cf_node_next(node
);
678 assert(next
->type
== nir_cf_node_block
);
679 nir_block
*next_block
= nir_cf_node_as_block(next
);
681 insert_block_before_block(next_block
, after_block
, has_jump
);
684 if (node
->type
== nir_cf_node_block
) {
685 insert_non_block_after_block(nir_cf_node_as_block(node
), after
);
688 * We have to insert a non-basic block after a non-basic block. Since
689 * every non-basic block has a basic block after it, this is equivalent
690 * to inserting a non-basic block before a basic block.
693 nir_cf_node
*next
= nir_cf_node_next(node
);
694 assert(next
->type
== nir_cf_node_block
);
695 nir_block
*next_block
= nir_cf_node_as_block(next
);
697 insert_non_block_before_block(after
, next_block
);
701 nir_function_impl
*impl
= nir_cf_node_get_function(node
);
702 nir_metadata_preserve(impl
, nir_metadata_none
);
706 nir_cf_node_insert_before(nir_cf_node
*node
, nir_cf_node
*before
)
708 update_if_uses(before
);
710 if (before
->type
== nir_cf_node_block
) {
711 nir_block
*before_block
= nir_cf_node_as_block(before
);
713 bool has_jump
= !exec_list_is_empty(&before_block
->instr_list
) &&
714 nir_block_last_instr(before_block
)->type
== nir_instr_type_jump
;
716 if (node
->type
== nir_cf_node_block
) {
717 insert_block_before_block(nir_cf_node_as_block(node
), before_block
,
720 nir_cf_node
*prev
= nir_cf_node_prev(node
);
721 assert(prev
->type
== nir_cf_node_block
);
722 nir_block
*prev_block
= nir_cf_node_as_block(prev
);
724 insert_block_after_block(prev_block
, before_block
, has_jump
);
727 if (node
->type
== nir_cf_node_block
) {
728 insert_non_block_before_block(before
, nir_cf_node_as_block(node
));
731 * We have to insert a non-basic block before a non-basic block. This
732 * is equivalent to inserting a non-basic block after a basic block.
735 nir_cf_node
*prev_node
= nir_cf_node_prev(node
);
736 assert(prev_node
->type
== nir_cf_node_block
);
737 nir_block
*prev_block
= nir_cf_node_as_block(prev_node
);
739 insert_non_block_after_block(prev_block
, before
);
743 nir_function_impl
*impl
= nir_cf_node_get_function(node
);
744 nir_metadata_preserve(impl
, nir_metadata_none
);
748 nir_cf_node_insert_begin(struct exec_list
*list
, nir_cf_node
*node
)
750 nir_cf_node
*begin
= exec_node_data(nir_cf_node
, list
->head
, node
);
751 nir_cf_node_insert_before(begin
, node
);
755 nir_cf_node_insert_end(struct exec_list
*list
, nir_cf_node
*node
)
757 nir_cf_node
*end
= exec_node_data(nir_cf_node
, list
->tail_pred
, node
);
758 nir_cf_node_insert_after(end
, node
);
762 * Stitch two basic blocks together into one. The aggregate must have the same
763 * predecessors as the first and the same successors as the second.
767 stitch_blocks(nir_block
*before
, nir_block
*after
)
770 * We move after into before, so we have to deal with up to 2 successors vs.
771 * possibly a large number of predecessors.
773 * TODO: special case when before is empty and after isn't?
776 if (block_ends_in_jump(before
)) {
777 assert(exec_list_is_empty(&after
->instr_list
));
778 if (after
->successors
[0])
779 remove_phi_src(after
->successors
[0], after
);
780 if (after
->successors
[1])
781 remove_phi_src(after
->successors
[1], after
);
782 unlink_block_successors(after
);
783 exec_node_remove(&after
->cf_node
.node
);
785 move_successors(after
, before
);
787 foreach_list_typed(nir_instr
, instr
, node
, &after
->instr_list
) {
788 instr
->block
= before
;
791 exec_list_append(&before
->instr_list
, &after
->instr_list
);
792 exec_node_remove(&after
->cf_node
.node
);
797 replace_ssa_def_uses(nir_ssa_def
*def
, void *void_impl
)
799 nir_function_impl
*impl
= void_impl
;
800 void *mem_ctx
= ralloc_parent(impl
);
802 nir_ssa_undef_instr
*undef
=
803 nir_ssa_undef_instr_create(mem_ctx
, def
->num_components
);
804 nir_instr_insert_before_cf_list(&impl
->body
, &undef
->instr
);
805 nir_ssa_def_rewrite_uses(def
, nir_src_for_ssa(&undef
->def
), mem_ctx
);
810 cleanup_cf_node(nir_cf_node
*node
, nir_function_impl
*impl
)
812 switch (node
->type
) {
813 case nir_cf_node_block
: {
814 nir_block
*block
= nir_cf_node_as_block(node
);
815 /* We need to walk the instructions and clean up defs/uses */
816 nir_foreach_instr_safe(block
, instr
) {
817 if (instr
->type
== nir_instr_type_jump
) {
818 nir_jump_type jump_type
= nir_instr_as_jump(instr
)->type
;
819 unlink_jump(block
, jump_type
);
821 nir_foreach_ssa_def(instr
, replace_ssa_def_uses
, impl
);
822 nir_instr_remove(instr
);
828 case nir_cf_node_if
: {
829 nir_if
*if_stmt
= nir_cf_node_as_if(node
);
830 foreach_list_typed(nir_cf_node
, child
, node
, &if_stmt
->then_list
)
831 cleanup_cf_node(child
, impl
);
832 foreach_list_typed(nir_cf_node
, child
, node
, &if_stmt
->else_list
)
833 cleanup_cf_node(child
, impl
);
835 list_del(&if_stmt
->condition
.use_link
);
839 case nir_cf_node_loop
: {
840 nir_loop
*loop
= nir_cf_node_as_loop(node
);
841 foreach_list_typed(nir_cf_node
, child
, node
, &loop
->body
)
842 cleanup_cf_node(child
, impl
);
845 case nir_cf_node_function
: {
846 nir_function_impl
*impl
= nir_cf_node_as_function(node
);
847 foreach_list_typed(nir_cf_node
, child
, node
, &impl
->body
)
848 cleanup_cf_node(child
, impl
);
852 unreachable("Invalid CF node type");
857 nir_cf_node_remove(nir_cf_node
*node
)
859 nir_function_impl
*impl
= nir_cf_node_get_function(node
);
860 nir_metadata_preserve(impl
, nir_metadata_none
);
862 if (node
->type
== nir_cf_node_block
) {
864 * Basic blocks can't really be removed by themselves, since they act as
865 * padding between the non-basic blocks. So all we do here is empty the
866 * block of instructions.
868 * TODO: could we assert here?
870 exec_list_make_empty(&nir_cf_node_as_block(node
)->instr_list
);
872 nir_cf_node
*before
= nir_cf_node_prev(node
);
873 assert(before
->type
== nir_cf_node_block
);
874 nir_block
*before_block
= nir_cf_node_as_block(before
);
876 nir_cf_node
*after
= nir_cf_node_next(node
);
877 assert(after
->type
== nir_cf_node_block
);
878 nir_block
*after_block
= nir_cf_node_as_block(after
);
880 exec_node_remove(&node
->node
);
881 stitch_blocks(before_block
, after_block
);
884 cleanup_cf_node(node
, impl
);