2 * Copyright © 2016 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
25 #include "nir/nir_builder.h"
26 #include "nir_constant_expressions.h"
27 #include "nir_control_flow.h"
28 #include "nir_loop_analyze.h"
30 static nir_ssa_def
*clone_alu_and_replace_src_defs(nir_builder
*b
,
31 const nir_alu_instr
*alu
,
32 nir_ssa_def
**src_defs
);
35 * Gets the single block that jumps back to the loop header. Already assumes
36 * there is exactly one such block.
39 find_continue_block(nir_loop
*loop
)
41 nir_block
*header_block
= nir_loop_first_block(loop
);
42 nir_block
*prev_block
=
43 nir_cf_node_as_block(nir_cf_node_prev(&loop
->cf_node
));
45 assert(header_block
->predecessors
->entries
== 2);
47 set_foreach(header_block
->predecessors
, pred_entry
) {
48 if (pred_entry
->key
!= prev_block
)
49 return (nir_block
*)pred_entry
->key
;
52 unreachable("Continue block not found!");
56 * Does a phi have one constant value from outside a loop and one from inside?
59 phi_has_constant_from_outside_and_one_from_inside_loop(nir_phi_instr
*phi
,
60 const nir_block
*entry_block
,
62 uint32_t *continue_val
)
64 /* We already know we have exactly one continue */
65 assert(exec_list_length(&phi
->srcs
) == 2);
70 nir_foreach_phi_src(src
, phi
) {
71 assert(src
->src
.is_ssa
);
72 nir_const_value
*const_src
= nir_src_as_const_value(src
->src
);
76 if (src
->pred
!= entry_block
) {
77 *continue_val
= const_src
->u32
[0];
79 *entry_val
= const_src
->u32
[0];
87 * This optimization detects if statements at the tops of loops where the
88 * condition is a phi node of two constants and moves half of the if to above
89 * the loop and the other half of the if to the end of the loop. A simple for
90 * loop "for (int i = 0; i < 4; i++)", when run through the SPIR-V front-end,
91 * ends up looking something like this:
93 * vec1 32 ssa_0 = load_const (0x00000000)
94 * vec1 32 ssa_1 = load_const (0xffffffff)
97 * vec1 32 ssa_2 = phi block_0: ssa_0, block_7: ssa_5
98 * vec1 32 ssa_3 = phi block_0: ssa_0, block_7: ssa_1
101 * vec1 32 ssa_4 = load_const (0x00000001)
102 * vec1 32 ssa_5 = iadd ssa_2, ssa_4
107 * vec1 32 ssa_6 = load_const (0x00000004)
108 * vec1 32 ssa_7 = ilt ssa_5, ssa_6
118 * This turns it into something like this:
120 * // Stuff from block 1
121 * // Stuff from block 3
124 * vec1 32 ssa_2 = phi block_0: ssa_0, block_7: ssa_5
125 * vec1 32 ssa_6 = load_const (0x00000004)
126 * vec1 32 ssa_7 = ilt ssa_2, ssa_6
134 * // Stuff from block 1
135 * // Stuff from block 2
136 * vec1 32 ssa_4 = load_const (0x00000001)
137 * vec1 32 ssa_5 = iadd ssa_2, ssa_4
141 opt_peel_loop_initial_if(nir_loop
*loop
)
143 nir_block
*header_block
= nir_loop_first_block(loop
);
144 nir_block
*const prev_block
=
145 nir_cf_node_as_block(nir_cf_node_prev(&loop
->cf_node
));
147 /* It would be insane if this were not true */
148 assert(_mesa_set_search(header_block
->predecessors
, prev_block
));
150 /* The loop must have exactly one continue block which could be a block
151 * ending in a continue instruction or the "natural" continue from the
152 * last block in the loop back to the top.
154 if (header_block
->predecessors
->entries
!= 2)
157 nir_cf_node
*if_node
= nir_cf_node_next(&header_block
->cf_node
);
158 if (!if_node
|| if_node
->type
!= nir_cf_node_if
)
161 nir_if
*nif
= nir_cf_node_as_if(if_node
);
162 assert(nif
->condition
.is_ssa
);
164 nir_ssa_def
*cond
= nif
->condition
.ssa
;
165 if (cond
->parent_instr
->type
!= nir_instr_type_phi
)
168 nir_phi_instr
*cond_phi
= nir_instr_as_phi(cond
->parent_instr
);
169 if (cond
->parent_instr
->block
!= header_block
)
172 uint32_t entry_val
= 0, continue_val
= 0;
173 if (!phi_has_constant_from_outside_and_one_from_inside_loop(cond_phi
,
179 /* If they both execute or both don't execute, this is a job for
180 * nir_dead_cf, not this pass.
182 if ((entry_val
&& continue_val
) || (!entry_val
&& !continue_val
))
185 struct exec_list
*continue_list
, *entry_list
;
187 continue_list
= &nif
->then_list
;
188 entry_list
= &nif
->else_list
;
190 continue_list
= &nif
->else_list
;
191 entry_list
= &nif
->then_list
;
194 /* We want to be moving the contents of entry_list to above the loop so it
195 * can't contain any break or continue instructions.
197 foreach_list_typed(nir_cf_node
, cf_node
, node
, entry_list
) {
198 nir_foreach_block_in_cf_node(block
, cf_node
) {
199 nir_instr
*last_instr
= nir_block_last_instr(block
);
200 if (last_instr
&& last_instr
->type
== nir_instr_type_jump
)
205 /* We're about to re-arrange a bunch of blocks so make sure that we don't
206 * have deref uses which cross block boundaries. We don't want a deref
207 * accidentally ending up in a phi.
209 nir_rematerialize_derefs_in_use_blocks_impl(
210 nir_cf_node_get_function(&loop
->cf_node
));
212 /* Before we do anything, convert the loop to LCSSA. We're about to
213 * replace a bunch of SSA defs with registers and this will prevent any of
214 * it from leaking outside the loop.
216 nir_convert_loop_to_lcssa(loop
);
218 nir_block
*after_if_block
=
219 nir_cf_node_as_block(nir_cf_node_next(&nif
->cf_node
));
221 /* Get rid of phis in the header block since we will be duplicating it */
222 nir_lower_phis_to_regs_block(header_block
);
223 /* Get rid of phis after the if since dominance will change */
224 nir_lower_phis_to_regs_block(after_if_block
);
226 /* Get rid of SSA defs in the pieces we're about to move around */
227 nir_lower_ssa_defs_to_regs_block(header_block
);
228 nir_foreach_block_in_cf_node(block
, &nif
->cf_node
)
229 nir_lower_ssa_defs_to_regs_block(block
);
231 nir_cf_list header
, tmp
;
232 nir_cf_extract(&header
, nir_before_block(header_block
),
233 nir_after_block(header_block
));
235 nir_cf_list_clone(&tmp
, &header
, &loop
->cf_node
, NULL
);
236 nir_cf_reinsert(&tmp
, nir_before_cf_node(&loop
->cf_node
));
237 nir_cf_extract(&tmp
, nir_before_cf_list(entry_list
),
238 nir_after_cf_list(entry_list
));
239 nir_cf_reinsert(&tmp
, nir_before_cf_node(&loop
->cf_node
));
241 nir_cf_reinsert(&header
,
242 nir_after_block_before_jump(find_continue_block(loop
)));
244 bool continue_list_jumps
=
245 nir_block_ends_in_jump(exec_node_data(nir_block
,
246 exec_list_get_tail(continue_list
),
249 nir_cf_extract(&tmp
, nir_before_cf_list(continue_list
),
250 nir_after_cf_list(continue_list
));
252 /* Get continue block again as the previous reinsert might have removed the
253 * block. Also, if both the continue list and the continue block ends in
254 * jump instructions, removes the jump from the latter, as it will not be
255 * executed if we insert the continue list before it. */
257 nir_block
*continue_block
= find_continue_block(loop
);
259 if (continue_list_jumps
) {
260 nir_instr
*last_instr
= nir_block_last_instr(continue_block
);
261 if (last_instr
&& last_instr
->type
== nir_instr_type_jump
)
262 nir_instr_remove(last_instr
);
265 nir_cf_reinsert(&tmp
,
266 nir_after_block_before_jump(continue_block
));
268 nir_cf_node_remove(&nif
->cf_node
);
274 alu_instr_is_comparison(const nir_alu_instr
*alu
)
289 return nir_alu_instr_is_comparison(alu
);
294 alu_instr_is_type_conversion(const nir_alu_instr
*alu
)
296 return nir_op_infos
[alu
->op
].num_inputs
== 1 &&
297 nir_alu_type_get_base_type(nir_op_infos
[alu
->op
].output_type
) !=
298 nir_alu_type_get_base_type(nir_op_infos
[alu
->op
].input_types
[0]);
302 * Splits ALU instructions that have a source that is a phi node
304 * ALU instructions in the header block of a loop that meet the following
305 * criteria can be split.
307 * - The loop has no continue instructions other than the "natural" continue
308 * at the bottom of the loop.
310 * - At least one source of the instruction is a phi node from the header block.
312 * and either this rule
314 * - The phi node selects undef from the block before the loop and a value
315 * from the continue block of the loop.
319 * - The phi node selects a constant from the block before the loop.
321 * - The non-phi source of the ALU instruction comes from a block that
322 * dominates the block before the loop. The most common failure mode for
323 * this check is sources that are generated in the loop header block.
325 * The split process moves the original ALU instruction to the bottom of the
326 * loop. The phi node source is replaced with the value from the phi node
327 * selected from the continue block (i.e., the non-undef value). A new phi
328 * node is added to the header block that selects either undef from the block
329 * before the loop or the result of the (moved) ALU instruction.
331 * The splitting transforms a loop like:
333 * vec1 32 ssa_7 = undefined
334 * vec1 32 ssa_8 = load_const (0x00000001)
335 * vec1 32 ssa_10 = load_const (0x00000000)
339 * // preds: block_0 block_4
340 * vec1 32 ssa_11 = phi block_0: ssa_7, block_4: ssa_15
341 * vec1 32 ssa_12 = phi block_0: ssa_1, block_4: ssa_15
342 * vec1 32 ssa_13 = phi block_0: ssa_10, block_4: ssa_16
343 * vec1 32 ssa_14 = iadd ssa_11, ssa_8
344 * vec1 32 ssa_15 = b32csel ssa_13, ssa_14, ssa_12
351 * vec1 32 ssa_7 = undefined
352 * vec1 32 ssa_8 = load_const (0x00000001)
353 * vec1 32 ssa_10 = load_const (0x00000000)
357 * // preds: block_0 block_4
358 * vec1 32 ssa_11 = phi block_0: ssa_7, block_4: ssa_15
359 * vec1 32 ssa_12 = phi block_0: ssa_1, block_4: ssa_15
360 * vec1 32 ssa_13 = phi block_0: ssa_10, block_4: ssa_16
361 * vec1 32 ssa_21 = phi block_0: sss_7, block_4: ssa_20
362 * vec1 32 ssa_15 = b32csel ssa_13, ssa_21, ssa_12
364 * vec1 32 ssa_20 = iadd ssa_15, ssa_8
368 * If the phi does not select an undef, the instruction is duplicated in the
369 * loop continue block (as in the undef case) and in the previous block. When
370 * the ALU instruction is duplicated in the previous block, the correct source
371 * must be selected from the phi node.
374 opt_split_alu_of_phi(nir_builder
*b
, nir_loop
*loop
)
376 bool progress
= false;
377 nir_block
*header_block
= nir_loop_first_block(loop
);
378 nir_block
*const prev_block
=
379 nir_cf_node_as_block(nir_cf_node_prev(&loop
->cf_node
));
381 /* It would be insane if this were not true */
382 assert(_mesa_set_search(header_block
->predecessors
, prev_block
));
384 /* The loop must have exactly one continue block which could be a block
385 * ending in a continue instruction or the "natural" continue from the
386 * last block in the loop back to the top.
388 if (header_block
->predecessors
->entries
!= 2)
391 nir_foreach_instr_safe(instr
, header_block
) {
392 if (instr
->type
!= nir_instr_type_alu
)
395 nir_alu_instr
*const alu
= nir_instr_as_alu(instr
);
397 /* Most ALU ops produce an undefined result if any source is undef.
398 * However, operations like bcsel only produce undefined results of the
399 * first operand is undef. Even in the undefined case, the result
400 * should be one of the other two operands, so the result of the bcsel
401 * should never be replaced with undef.
403 * nir_op_vec{2,3,4}, nir_op_imov, and nir_op_fmov are excluded because
404 * they can easily lead to infinite optimization loops.
406 if (alu
->op
== nir_op_bcsel
||
407 alu
->op
== nir_op_b32csel
||
408 alu
->op
== nir_op_fcsel
||
409 alu
->op
== nir_op_vec2
||
410 alu
->op
== nir_op_vec3
||
411 alu
->op
== nir_op_vec4
||
412 alu
->op
== nir_op_imov
||
413 alu
->op
== nir_op_fmov
||
414 alu_instr_is_comparison(alu
) ||
415 alu_instr_is_type_conversion(alu
))
418 bool has_phi_src_from_prev_block
= false;
419 bool all_non_phi_exist_in_prev_block
= true;
420 bool is_prev_result_undef
= true;
421 bool is_prev_result_const
= true;
422 nir_ssa_def
*prev_srcs
[8]; // FINISHME: Array size?
423 nir_ssa_def
*continue_srcs
[8]; // FINISHME: Array size?
425 for (unsigned i
= 0; i
< nir_op_infos
[alu
->op
].num_inputs
; i
++) {
426 nir_instr
*const src_instr
= alu
->src
[i
].src
.ssa
->parent_instr
;
428 /* If the source is a phi in the loop header block, then the
429 * prev_srcs and continue_srcs will come from the different sources
432 if (src_instr
->type
== nir_instr_type_phi
&&
433 src_instr
->block
== header_block
) {
434 nir_phi_instr
*const phi
= nir_instr_as_phi(src_instr
);
436 /* Only strictly need to NULL out the pointers when the assertions
437 * (below) are compiled in. Debugging a NULL pointer deref in the
438 * wild is easier than debugging a random pointer deref, so set
439 * NULL unconditionally just to be safe.
442 continue_srcs
[i
] = NULL
;
444 nir_foreach_phi_src(src_of_phi
, phi
) {
445 if (src_of_phi
->pred
== prev_block
) {
446 if (src_of_phi
->src
.ssa
->parent_instr
->type
!=
447 nir_instr_type_ssa_undef
) {
448 is_prev_result_undef
= false;
451 if (src_of_phi
->src
.ssa
->parent_instr
->type
!=
452 nir_instr_type_load_const
) {
453 is_prev_result_const
= false;
456 prev_srcs
[i
] = src_of_phi
->src
.ssa
;
457 has_phi_src_from_prev_block
= true;
459 continue_srcs
[i
] = src_of_phi
->src
.ssa
;
462 assert(prev_srcs
[i
] != NULL
);
463 assert(continue_srcs
[i
] != NULL
);
465 /* If the source is not a phi (or a phi in a block other than the
466 * loop header), then the value must exist in prev_block.
468 if (!nir_block_dominates(src_instr
->block
, prev_block
)) {
469 all_non_phi_exist_in_prev_block
= false;
473 prev_srcs
[i
] = alu
->src
[i
].src
.ssa
;
474 continue_srcs
[i
] = alu
->src
[i
].src
.ssa
;
478 if (has_phi_src_from_prev_block
&& all_non_phi_exist_in_prev_block
&&
479 (is_prev_result_undef
|| is_prev_result_const
)) {
480 nir_block
*const continue_block
= find_continue_block(loop
);
481 nir_ssa_def
*prev_value
;
483 if (!is_prev_result_undef
) {
484 b
->cursor
= nir_after_block(prev_block
);
485 prev_value
= clone_alu_and_replace_src_defs(b
, alu
, prev_srcs
);
487 /* Since the undef used as the source of the original ALU
488 * instruction may have different number of components or
489 * bit size than the result of that instruction, a new
490 * undef must be created.
492 nir_ssa_undef_instr
*undef
=
493 nir_ssa_undef_instr_create(b
->shader
,
494 alu
->dest
.dest
.ssa
.num_components
,
495 alu
->dest
.dest
.ssa
.bit_size
);
497 nir_instr_insert_after_block(prev_block
, &undef
->instr
);
499 prev_value
= &undef
->def
;
502 /* Make a copy of the original ALU instruction. Replace the sources
503 * of the new instruction that read a phi with an undef source from
504 * prev_block with the non-undef source of that phi.
506 * Insert the new instruction at the end of the continue block.
508 b
->cursor
= nir_after_block_before_jump(continue_block
);
510 nir_ssa_def
*const alu_copy
=
511 clone_alu_and_replace_src_defs(b
, alu
, continue_srcs
);
513 /* Make a new phi node that selects a value from prev_block and the
514 * result of the new instruction from continue_block.
516 nir_phi_instr
*const phi
= nir_phi_instr_create(b
->shader
);
517 nir_phi_src
*phi_src
;
519 phi_src
= ralloc(phi
, nir_phi_src
);
520 phi_src
->pred
= prev_block
;
521 phi_src
->src
= nir_src_for_ssa(prev_value
);
522 exec_list_push_tail(&phi
->srcs
, &phi_src
->node
);
524 phi_src
= ralloc(phi
, nir_phi_src
);
525 phi_src
->pred
= continue_block
;
526 phi_src
->src
= nir_src_for_ssa(alu_copy
);
527 exec_list_push_tail(&phi
->srcs
, &phi_src
->node
);
529 nir_ssa_dest_init(&phi
->instr
, &phi
->dest
,
530 alu_copy
->num_components
, alu_copy
->bit_size
, NULL
);
532 b
->cursor
= nir_after_phis(header_block
);
533 nir_builder_instr_insert(b
, &phi
->instr
);
535 /* Modify all readers of the original ALU instruction to read the
538 nir_foreach_use_safe(use_src
, &alu
->dest
.dest
.ssa
) {
539 nir_instr_rewrite_src(use_src
->parent_instr
,
541 nir_src_for_ssa(&phi
->dest
.ssa
));
544 nir_foreach_if_use_safe(use_src
, &alu
->dest
.dest
.ssa
) {
545 nir_if_rewrite_condition(use_src
->parent_if
,
546 nir_src_for_ssa(&phi
->dest
.ssa
));
549 /* Since the original ALU instruction no longer has any readers, just
552 nir_instr_remove_v(&alu
->instr
);
563 * Get the SSA value from a phi node that corresponds to a specific block
566 ssa_for_phi_from_block(nir_phi_instr
*phi
, nir_block
*block
)
568 nir_foreach_phi_src(src
, phi
) {
569 if (src
->pred
== block
)
573 assert(!"Block is not a predecessor of phi.");
578 * Simplify a bcsel whose sources are all phi nodes from the loop header block
580 * bcsel instructions in a loop that meet the following criteria can be
581 * converted to phi nodes:
583 * - The loop has no continue instructions other than the "natural" continue
584 * at the bottom of the loop.
586 * - All of the sources of the bcsel are phi nodes in the header block of the
589 * - The phi node representing the condition of the bcsel instruction chooses
590 * only constant values.
592 * The contant value from the condition will select one of the other sources
593 * when entered from outside the loop and the remaining source when entered
594 * from the continue block. Since each of these sources is also a phi node in
595 * the header block, the value of the phi node can be "evaluated." These
596 * evaluated phi nodes provide the sources for a new phi node. All users of
597 * the bcsel result are updated to use the phi node result.
599 * The replacement transforms loops like:
601 * vec1 32 ssa_7 = undefined
602 * vec1 32 ssa_8 = load_const (0x00000001)
603 * vec1 32 ssa_9 = load_const (0x000000c8)
604 * vec1 32 ssa_10 = load_const (0x00000000)
608 * // preds: block_0 block_4
609 * vec1 32 ssa_11 = phi block_0: ssa_1, block_4: ssa_14
610 * vec1 32 ssa_12 = phi block_0: ssa_10, block_4: ssa_15
611 * vec1 32 ssa_13 = phi block_0: ssa_7, block_4: ssa_25
612 * vec1 32 ssa_14 = b32csel ssa_12, ssa_13, ssa_11
613 * vec1 32 ssa_16 = ige32 ssa_14, ssa_9
615 * vec1 32 ssa_15 = load_const (0xffffffff)
617 * vec1 32 ssa_25 = iadd ssa_14, ssa_8
623 * vec1 32 ssa_7 = undefined
624 * vec1 32 ssa_8 = load_const (0x00000001)
625 * vec1 32 ssa_9 = load_const (0x000000c8)
626 * vec1 32 ssa_10 = load_const (0x00000000)
630 * // preds: block_0 block_4
631 * vec1 32 ssa_11 = phi block_0: ssa_1, block_4: ssa_14
632 * vec1 32 ssa_12 = phi block_0: ssa_10, block_4: ssa_15
633 * vec1 32 ssa_13 = phi block_0: ssa_7, block_4: ssa_25
634 * vec1 32 sss_26 = phi block_0: ssa_1, block_4: ssa_25
635 * vec1 32 ssa_16 = ige32 ssa_26, ssa_9
637 * vec1 32 ssa_15 = load_const (0xffffffff)
639 * vec1 32 ssa_25 = iadd ssa_26, ssa_8
644 * It may be possible modify this function to not require a phi node as the
645 * source of the bcsel that is selected when entering from outside the loop.
646 * The only restriction is that the source must be geneated outside the loop
647 * (since it will become the source of a phi node in the header block of the
651 opt_simplify_bcsel_of_phi(nir_builder
*b
, nir_loop
*loop
)
653 bool progress
= false;
654 nir_block
*header_block
= nir_loop_first_block(loop
);
655 nir_block
*const prev_block
=
656 nir_cf_node_as_block(nir_cf_node_prev(&loop
->cf_node
));
658 /* It would be insane if this were not true */
659 assert(_mesa_set_search(header_block
->predecessors
, prev_block
));
661 /* The loop must have exactly one continue block which could be a block
662 * ending in a continue instruction or the "natural" continue from the
663 * last block in the loop back to the top.
665 if (header_block
->predecessors
->entries
!= 2)
668 /* We can move any bcsel that can guaranteed to execut on every iteration
669 * of a loop. For now this is accomplished by only taking bcsels from the
670 * header_block. In the future, this could be expanced to include any
671 * bcsel that must come before any break.
673 * For more details, see
674 * https://gitlab.freedesktop.org/mesa/mesa/merge_requests/170#note_110305
676 nir_foreach_instr_safe(instr
, header_block
) {
677 if (instr
->type
!= nir_instr_type_alu
)
680 nir_alu_instr
*const bcsel
= nir_instr_as_alu(instr
);
681 if (bcsel
->op
!= nir_op_bcsel
&&
682 bcsel
->op
!= nir_op_b32csel
&&
683 bcsel
->op
!= nir_op_fcsel
)
687 for (unsigned i
= 0; i
< 3; i
++) {
688 /* FINISHME: The abs and negate cases could be handled by adding
689 * move instructions at the bottom of the continue block and more
690 * phi nodes in the header_block.
692 if (!bcsel
->src
[i
].src
.is_ssa
||
693 bcsel
->src
[i
].src
.ssa
->parent_instr
->type
!= nir_instr_type_phi
||
694 bcsel
->src
[i
].src
.ssa
->parent_instr
->block
!= header_block
||
695 bcsel
->src
[i
].negate
|| bcsel
->src
[i
].abs
) {
704 nir_phi_instr
*const cond_phi
=
705 nir_instr_as_phi(bcsel
->src
[0].src
.ssa
->parent_instr
);
707 uint32_t entry_val
= 0, continue_val
= 0;
708 if (!phi_has_constant_from_outside_and_one_from_inside_loop(cond_phi
,
714 /* If they both execute or both don't execute, this is a job for
715 * nir_dead_cf, not this pass.
717 if ((entry_val
&& continue_val
) || (!entry_val
&& !continue_val
))
720 const unsigned entry_src
= entry_val
? 1 : 2;
721 const unsigned continue_src
= entry_val
? 2 : 1;
723 /* Create a new phi node that selects the value for prev_block from
724 * the bcsel source that is selected by entry_val and the value for
725 * continue_block from the other bcsel source. Both sources have
726 * already been verified to be phi nodes.
728 nir_block
*const continue_block
= find_continue_block(loop
);
729 nir_phi_instr
*const phi
= nir_phi_instr_create(b
->shader
);
730 nir_phi_src
*phi_src
;
732 phi_src
= ralloc(phi
, nir_phi_src
);
733 phi_src
->pred
= prev_block
;
735 nir_src_for_ssa(ssa_for_phi_from_block(nir_instr_as_phi(bcsel
->src
[entry_src
].src
.ssa
->parent_instr
),
737 exec_list_push_tail(&phi
->srcs
, &phi_src
->node
);
739 phi_src
= ralloc(phi
, nir_phi_src
);
740 phi_src
->pred
= continue_block
;
742 nir_src_for_ssa(ssa_for_phi_from_block(nir_instr_as_phi(bcsel
->src
[continue_src
].src
.ssa
->parent_instr
),
744 exec_list_push_tail(&phi
->srcs
, &phi_src
->node
);
746 nir_ssa_dest_init(&phi
->instr
,
748 nir_dest_num_components(bcsel
->dest
.dest
),
749 nir_dest_bit_size(bcsel
->dest
.dest
),
752 b
->cursor
= nir_after_phis(header_block
);
753 nir_builder_instr_insert(b
, &phi
->instr
);
755 /* Modify all readers of the bcsel instruction to read the result of
758 nir_foreach_use_safe(use_src
, &bcsel
->dest
.dest
.ssa
) {
759 nir_instr_rewrite_src(use_src
->parent_instr
,
761 nir_src_for_ssa(&phi
->dest
.ssa
));
764 nir_foreach_if_use_safe(use_src
, &bcsel
->dest
.dest
.ssa
) {
765 nir_if_rewrite_condition(use_src
->parent_if
,
766 nir_src_for_ssa(&phi
->dest
.ssa
));
769 /* Since the original bcsel instruction no longer has any readers,
772 nir_instr_remove_v(&bcsel
->instr
);
782 is_block_empty(nir_block
*block
)
784 return nir_cf_node_is_last(&block
->cf_node
) &&
785 exec_list_is_empty(&block
->instr_list
);
789 nir_block_ends_in_continue(nir_block
*block
)
791 if (exec_list_is_empty(&block
->instr_list
))
794 nir_instr
*instr
= nir_block_last_instr(block
);
795 return instr
->type
== nir_instr_type_jump
&&
796 nir_instr_as_jump(instr
)->type
== nir_jump_continue
;
800 * This optimization turns:
824 * The continue should then be removed by nir_opt_trivial_continues() and the
825 * loop can potentially be unrolled.
827 * Note: do_work_2() is only ever blocks and nested loops. We could also nest
828 * other if-statments in the branch which would allow further continues to
829 * be removed. However in practice this can result in increased register
833 opt_if_loop_last_continue(nir_loop
*loop
)
835 /* Get the last if-stament in the loop */
836 nir_block
*last_block
= nir_loop_last_block(loop
);
837 nir_cf_node
*if_node
= nir_cf_node_prev(&last_block
->cf_node
);
839 if (if_node
->type
== nir_cf_node_if
)
842 if_node
= nir_cf_node_prev(if_node
);
845 if (!if_node
|| if_node
->type
!= nir_cf_node_if
)
848 nir_if
*nif
= nir_cf_node_as_if(if_node
);
849 nir_block
*then_block
= nir_if_last_then_block(nif
);
850 nir_block
*else_block
= nir_if_last_else_block(nif
);
852 bool then_ends_in_continue
= nir_block_ends_in_continue(then_block
);
853 bool else_ends_in_continue
= nir_block_ends_in_continue(else_block
);
855 /* If both branches end in a continue do nothing, this should be handled
856 * by nir_opt_dead_cf().
858 if ((then_ends_in_continue
|| nir_block_ends_in_break(then_block
)) &&
859 (else_ends_in_continue
|| nir_block_ends_in_break(else_block
)))
862 if (!then_ends_in_continue
&& !else_ends_in_continue
)
865 /* if the block after the if/else is empty we bail, otherwise we might end
868 if (&nif
->cf_node
== nir_cf_node_prev(&last_block
->cf_node
) &&
869 exec_list_is_empty(&last_block
->instr_list
))
872 /* Move the last block of the loop inside the last if-statement */
874 nir_cf_extract(&tmp
, nir_after_cf_node(if_node
),
875 nir_after_block(last_block
));
876 if (then_ends_in_continue
)
877 nir_cf_reinsert(&tmp
, nir_after_cf_list(&nif
->else_list
));
879 nir_cf_reinsert(&tmp
, nir_after_cf_list(&nif
->then_list
));
881 /* In order to avoid running nir_lower_regs_to_ssa_impl() every time an if
882 * opt makes progress we leave nir_opt_trivial_continues() to remove the
883 * continue now that the end of the loop has been simplified.
889 /* Walk all the phis in the block immediately following the if statement and
893 rewrite_phi_predecessor_blocks(nir_if
*nif
,
894 nir_block
*old_then_block
,
895 nir_block
*old_else_block
,
896 nir_block
*new_then_block
,
897 nir_block
*new_else_block
)
899 nir_block
*after_if_block
=
900 nir_cf_node_as_block(nir_cf_node_next(&nif
->cf_node
));
902 nir_foreach_instr(instr
, after_if_block
) {
903 if (instr
->type
!= nir_instr_type_phi
)
906 nir_phi_instr
*phi
= nir_instr_as_phi(instr
);
908 foreach_list_typed(nir_phi_src
, src
, node
, &phi
->srcs
) {
909 if (src
->pred
== old_then_block
) {
910 src
->pred
= new_then_block
;
911 } else if (src
->pred
== old_else_block
) {
912 src
->pred
= new_else_block
;
919 * This optimization turns:
934 opt_if_simplification(nir_builder
*b
, nir_if
*nif
)
936 /* Only simplify if the then block is empty and the else block is not. */
937 if (!is_block_empty(nir_if_first_then_block(nif
)) ||
938 is_block_empty(nir_if_first_else_block(nif
)))
941 /* Make sure the condition is a comparison operation. */
942 nir_instr
*src_instr
= nif
->condition
.ssa
->parent_instr
;
943 if (src_instr
->type
!= nir_instr_type_alu
)
946 nir_alu_instr
*alu_instr
= nir_instr_as_alu(src_instr
);
947 if (!nir_alu_instr_is_comparison(alu_instr
))
950 /* Insert the inverted instruction and rewrite the condition. */
951 b
->cursor
= nir_after_instr(&alu_instr
->instr
);
953 nir_ssa_def
*new_condition
=
954 nir_inot(b
, &alu_instr
->dest
.dest
.ssa
);
956 nir_if_rewrite_condition(nif
, nir_src_for_ssa(new_condition
));
958 /* Grab pointers to the last then/else blocks for fixing up the phis. */
959 nir_block
*then_block
= nir_if_last_then_block(nif
);
960 nir_block
*else_block
= nir_if_last_else_block(nif
);
962 rewrite_phi_predecessor_blocks(nif
, then_block
, else_block
, else_block
,
965 /* Finally, move the else block to the then block. */
967 nir_cf_extract(&tmp
, nir_before_cf_list(&nif
->else_list
),
968 nir_after_cf_list(&nif
->else_list
));
969 nir_cf_reinsert(&tmp
, nir_before_cf_list(&nif
->then_list
));
975 * This optimization simplifies potential loop terminators which then allows
976 * other passes such as opt_if_simplification() and loop unrolling to progress
980 * ... then block instructions ...
993 * ... then block instructions ...
996 opt_if_loop_terminator(nir_if
*nif
)
998 nir_block
*break_blk
= NULL
;
999 nir_block
*continue_from_blk
= NULL
;
1000 bool continue_from_then
= true;
1002 nir_block
*last_then
= nir_if_last_then_block(nif
);
1003 nir_block
*last_else
= nir_if_last_else_block(nif
);
1005 if (nir_block_ends_in_break(last_then
)) {
1006 break_blk
= last_then
;
1007 continue_from_blk
= last_else
;
1008 continue_from_then
= false;
1009 } else if (nir_block_ends_in_break(last_else
)) {
1010 break_blk
= last_else
;
1011 continue_from_blk
= last_then
;
1014 /* Continue if the if-statement contained no jumps at all */
1018 /* If the continue from block is empty then return as there is nothing to
1021 nir_block
*first_continue_from_blk
= continue_from_then
?
1022 nir_if_first_then_block(nif
) :
1023 nir_if_first_else_block(nif
);
1024 if (is_block_empty(first_continue_from_blk
))
1027 if (!nir_is_trivial_loop_if(nif
, break_blk
))
1030 /* Finally, move the continue from branch after the if-statement. */
1032 nir_cf_extract(&tmp
, nir_before_block(first_continue_from_blk
),
1033 nir_after_block(continue_from_blk
));
1034 nir_cf_reinsert(&tmp
, nir_after_cf_node(&nif
->cf_node
));
1040 evaluate_if_condition(nir_if
*nif
, nir_cursor cursor
, bool *value
)
1042 nir_block
*use_block
= nir_cursor_current_block(cursor
);
1043 if (nir_block_dominates(nir_if_first_then_block(nif
), use_block
)) {
1046 } else if (nir_block_dominates(nir_if_first_else_block(nif
), use_block
)) {
1054 static nir_ssa_def
*
1055 clone_alu_and_replace_src_defs(nir_builder
*b
, const nir_alu_instr
*alu
,
1056 nir_ssa_def
**src_defs
)
1058 nir_alu_instr
*nalu
= nir_alu_instr_create(b
->shader
, alu
->op
);
1059 nalu
->exact
= alu
->exact
;
1061 nir_ssa_dest_init(&nalu
->instr
, &nalu
->dest
.dest
,
1062 alu
->dest
.dest
.ssa
.num_components
,
1063 alu
->dest
.dest
.ssa
.bit_size
, alu
->dest
.dest
.ssa
.name
);
1065 nalu
->dest
.saturate
= alu
->dest
.saturate
;
1066 nalu
->dest
.write_mask
= alu
->dest
.write_mask
;
1068 for (unsigned i
= 0; i
< nir_op_infos
[alu
->op
].num_inputs
; i
++) {
1069 assert(alu
->src
[i
].src
.is_ssa
);
1070 nalu
->src
[i
].src
= nir_src_for_ssa(src_defs
[i
]);
1071 nalu
->src
[i
].negate
= alu
->src
[i
].negate
;
1072 nalu
->src
[i
].abs
= alu
->src
[i
].abs
;
1073 memcpy(nalu
->src
[i
].swizzle
, alu
->src
[i
].swizzle
,
1074 sizeof(nalu
->src
[i
].swizzle
));
1077 nir_builder_instr_insert(b
, &nalu
->instr
);
1079 return &nalu
->dest
.dest
.ssa
;;
1083 * This propagates if condition evaluation down the chain of some alu
1084 * instructions. For example by checking the use of some of the following alu
1085 * instruction we can eventually replace ssa_107 with NIR_TRUE.
1089 * vec1 32 ssa_85 = load_const (0x00000002)
1090 * vec1 32 ssa_86 = ieq ssa_48, ssa_85
1091 * vec1 32 ssa_87 = load_const (0x00000001)
1092 * vec1 32 ssa_88 = ieq ssa_48, ssa_87
1093 * vec1 32 ssa_89 = ior ssa_86, ssa_88
1094 * vec1 32 ssa_90 = ieq ssa_48, ssa_0
1095 * vec1 32 ssa_91 = ior ssa_89, ssa_90
1120 * vec1 32 ssa_107 = inot ssa_91
1130 propagate_condition_eval(nir_builder
*b
, nir_if
*nif
, nir_src
*use_src
,
1131 nir_src
*alu_use
, nir_alu_instr
*alu
,
1132 bool is_if_condition
)
1135 b
->cursor
= nir_before_src(alu_use
, is_if_condition
);
1136 if (!evaluate_if_condition(nif
, b
->cursor
, &bool_value
))
1139 nir_ssa_def
*def
[4] = {0};
1140 for (unsigned i
= 0; i
< nir_op_infos
[alu
->op
].num_inputs
; i
++) {
1141 if (alu
->src
[i
].src
.ssa
== use_src
->ssa
) {
1142 def
[i
] = nir_imm_bool(b
, bool_value
);
1144 def
[i
] = alu
->src
[i
].src
.ssa
;
1148 nir_ssa_def
*nalu
= clone_alu_and_replace_src_defs(b
, alu
, def
);
1150 /* Rewrite use to use new alu instruction */
1151 nir_src new_src
= nir_src_for_ssa(nalu
);
1153 if (is_if_condition
)
1154 nir_if_rewrite_condition(alu_use
->parent_if
, new_src
);
1156 nir_instr_rewrite_src(alu_use
->parent_instr
, alu_use
, new_src
);
1162 can_propagate_through_alu(nir_src
*src
)
1164 if (src
->parent_instr
->type
!= nir_instr_type_alu
)
1167 nir_alu_instr
*alu
= nir_instr_as_alu(src
->parent_instr
);
1175 return src
== &alu
->src
[0].src
;
1182 evaluate_condition_use(nir_builder
*b
, nir_if
*nif
, nir_src
*use_src
,
1183 bool is_if_condition
)
1185 bool progress
= false;
1187 b
->cursor
= nir_before_src(use_src
, is_if_condition
);
1190 if (evaluate_if_condition(nif
, b
->cursor
, &bool_value
)) {
1191 /* Rewrite use to use const */
1192 nir_src imm_src
= nir_src_for_ssa(nir_imm_bool(b
, bool_value
));
1193 if (is_if_condition
)
1194 nir_if_rewrite_condition(use_src
->parent_if
, imm_src
);
1196 nir_instr_rewrite_src(use_src
->parent_instr
, use_src
, imm_src
);
1201 if (!is_if_condition
&& can_propagate_through_alu(use_src
)) {
1202 nir_alu_instr
*alu
= nir_instr_as_alu(use_src
->parent_instr
);
1204 nir_foreach_use_safe(alu_use
, &alu
->dest
.dest
.ssa
) {
1205 progress
|= propagate_condition_eval(b
, nif
, use_src
, alu_use
, alu
,
1209 nir_foreach_if_use_safe(alu_use
, &alu
->dest
.dest
.ssa
) {
1210 progress
|= propagate_condition_eval(b
, nif
, use_src
, alu_use
, alu
,
1219 opt_if_evaluate_condition_use(nir_builder
*b
, nir_if
*nif
)
1221 bool progress
= false;
1223 /* Evaluate any uses of the if condition inside the if branches */
1224 assert(nif
->condition
.is_ssa
);
1225 nir_foreach_use_safe(use_src
, nif
->condition
.ssa
) {
1226 progress
|= evaluate_condition_use(b
, nif
, use_src
, false);
1229 nir_foreach_if_use_safe(use_src
, nif
->condition
.ssa
) {
1230 if (use_src
->parent_if
!= nif
)
1231 progress
|= evaluate_condition_use(b
, nif
, use_src
, true);
1238 simple_merge_if(nir_if
*dest_if
, nir_if
*src_if
, bool dest_if_then
,
1241 /* Now merge the if branch */
1242 nir_block
*dest_blk
= dest_if_then
? nir_if_last_then_block(dest_if
)
1243 : nir_if_last_else_block(dest_if
);
1245 struct exec_list
*list
= src_if_then
? &src_if
->then_list
1246 : &src_if
->else_list
;
1248 nir_cf_list if_cf_list
;
1249 nir_cf_extract(&if_cf_list
, nir_before_cf_list(list
),
1250 nir_after_cf_list(list
));
1251 nir_cf_reinsert(&if_cf_list
, nir_after_block(dest_blk
));
1255 opt_if_merge(nir_if
*nif
)
1257 bool progress
= false;
1259 nir_block
*next_blk
= nir_cf_node_cf_tree_next(&nif
->cf_node
);
1260 if (next_blk
&& nif
->condition
.is_ssa
) {
1261 nir_if
*next_if
= nir_block_get_following_if(next_blk
);
1262 if (next_if
&& next_if
->condition
.is_ssa
) {
1264 /* Here we merge two consecutive ifs that have the same
1278 * Note: This only merges if-statements when the block between them
1279 * is empty. The reason we don't try to merge ifs that just have phis
1280 * between them is because this can results in increased register
1281 * pressure. For example when merging if ladders created by indirect
1284 if (nif
->condition
.ssa
== next_if
->condition
.ssa
&&
1285 exec_list_is_empty(&next_blk
->instr_list
)) {
1287 simple_merge_if(nif
, next_if
, true, true);
1288 simple_merge_if(nif
, next_if
, false, false);
1290 nir_block
*new_then_block
= nir_if_last_then_block(nif
);
1291 nir_block
*new_else_block
= nir_if_last_else_block(nif
);
1293 nir_block
*old_then_block
= nir_if_last_then_block(next_if
);
1294 nir_block
*old_else_block
= nir_if_last_else_block(next_if
);
1296 /* Rewrite the predecessor block for any phis following the second
1299 rewrite_phi_predecessor_blocks(next_if
, old_then_block
,
1304 /* Move phis after merged if to avoid them being deleted when we
1305 * remove the merged if-statement.
1307 nir_block
*after_next_if_block
=
1308 nir_cf_node_as_block(nir_cf_node_next(&next_if
->cf_node
));
1310 nir_foreach_instr_safe(instr
, after_next_if_block
) {
1311 if (instr
->type
!= nir_instr_type_phi
)
1314 exec_node_remove(&instr
->node
);
1315 exec_list_push_tail(&next_blk
->instr_list
, &instr
->node
);
1316 instr
->block
= next_blk
;
1319 nir_cf_node_remove(&next_if
->cf_node
);
1329 /* Perform optimisations based on the values we can derive from the evaluation
1330 * of if-statement conditions.
1333 opt_for_known_values(nir_builder
*b
, nir_if
*nif
)
1335 bool progress
= false;
1337 assert(nif
->condition
.is_ssa
);
1338 nir_ssa_def
*if_cond
= nif
->condition
.ssa
;
1340 if (if_cond
->parent_instr
->type
!= nir_instr_type_alu
)
1343 nir_alu_instr
*alu
= nir_instr_as_alu(if_cond
->parent_instr
);
1347 nir_load_const_instr
*load_const
= NULL
;
1348 nir_ssa_def
*unknown_val
= NULL
;
1350 nir_ssa_def
*src0
= alu
->src
[0].src
.ssa
;
1351 nir_ssa_def
*src1
= alu
->src
[1].src
.ssa
;
1352 if (src0
->parent_instr
->type
== nir_instr_type_load_const
) {
1353 load_const
= nir_instr_as_load_const(src0
->parent_instr
);
1355 } else if (src1
->parent_instr
->type
== nir_instr_type_load_const
) {
1356 load_const
= nir_instr_as_load_const(src1
->parent_instr
);
1363 /* TODO: remove this and support swizzles? */
1364 if (unknown_val
->num_components
!= 1)
1367 /* Replace unknown ssa uses with the known constant */
1368 nir_foreach_use_safe(use_src
, unknown_val
) {
1369 nir_cursor cursor
= nir_before_src(use_src
, false);
1370 nir_block
*use_block
= nir_cursor_current_block(cursor
);
1371 if (nir_block_dominates(nir_if_first_then_block(nif
), use_block
)) {
1372 nir_instr_rewrite_src(use_src
->parent_instr
, use_src
,
1373 nir_src_for_ssa(&load_const
->def
));
1389 opt_if_cf_list(nir_builder
*b
, struct exec_list
*cf_list
)
1391 bool progress
= false;
1392 foreach_list_typed(nir_cf_node
, cf_node
, node
, cf_list
) {
1393 switch (cf_node
->type
) {
1394 case nir_cf_node_block
:
1397 case nir_cf_node_if
: {
1398 nir_if
*nif
= nir_cf_node_as_if(cf_node
);
1399 progress
|= opt_if_cf_list(b
, &nif
->then_list
);
1400 progress
|= opt_if_cf_list(b
, &nif
->else_list
);
1401 progress
|= opt_if_loop_terminator(nif
);
1402 progress
|= opt_if_merge(nif
);
1403 progress
|= opt_if_simplification(b
, nif
);
1407 case nir_cf_node_loop
: {
1408 nir_loop
*loop
= nir_cf_node_as_loop(cf_node
);
1409 progress
|= opt_if_cf_list(b
, &loop
->body
);
1410 progress
|= opt_simplify_bcsel_of_phi(b
, loop
);
1411 progress
|= opt_peel_loop_initial_if(loop
);
1412 progress
|= opt_if_loop_last_continue(loop
);
1416 case nir_cf_node_function
:
1417 unreachable("Invalid cf type");
1425 * These optimisations depend on nir_metadata_block_index and therefore must
1426 * not do anything to cause the metadata to become invalid.
1429 opt_if_safe_cf_list(nir_builder
*b
, struct exec_list
*cf_list
)
1431 bool progress
= false;
1432 foreach_list_typed(nir_cf_node
, cf_node
, node
, cf_list
) {
1433 switch (cf_node
->type
) {
1434 case nir_cf_node_block
:
1437 case nir_cf_node_if
: {
1438 nir_if
*nif
= nir_cf_node_as_if(cf_node
);
1439 progress
|= opt_if_safe_cf_list(b
, &nif
->then_list
);
1440 progress
|= opt_if_safe_cf_list(b
, &nif
->else_list
);
1441 progress
|= opt_if_evaluate_condition_use(b
, nif
);
1442 progress
|= opt_for_known_values(b
, nif
);
1446 case nir_cf_node_loop
: {
1447 nir_loop
*loop
= nir_cf_node_as_loop(cf_node
);
1448 progress
|= opt_if_safe_cf_list(b
, &loop
->body
);
1449 progress
|= opt_split_alu_of_phi(b
, loop
);
1453 case nir_cf_node_function
:
1454 unreachable("Invalid cf type");
1462 nir_opt_if(nir_shader
*shader
)
1464 bool progress
= false;
1466 nir_foreach_function(function
, shader
) {
1467 if (function
->impl
== NULL
)
1471 nir_builder_init(&b
, function
->impl
);
1473 nir_metadata_require(function
->impl
, nir_metadata_block_index
|
1474 nir_metadata_dominance
);
1475 progress
= opt_if_safe_cf_list(&b
, &function
->impl
->body
);
1476 nir_metadata_preserve(function
->impl
, nir_metadata_block_index
|
1477 nir_metadata_dominance
);
1479 if (opt_if_cf_list(&b
, &function
->impl
->body
)) {
1480 nir_metadata_preserve(function
->impl
, nir_metadata_none
);
1482 /* If that made progress, we're no longer really in SSA form. We
1483 * need to convert registers back into SSA defs and clean up SSA defs
1484 * that don't dominate their uses.
1486 nir_lower_regs_to_ssa_impl(function
->impl
);
1491 function
->impl
->valid_metadata
&= ~nir_metadata_not_properly_reset
;