2 * Copyright © 2015 Thomas Helland
3 * Copyright © 2019 Valve Corporation
5 * Permission is hereby granted, free of charge, to any person obtaining a
6 * copy of this software and associated documentation files (the "Software"),
7 * to deal in the Software without restriction, including without limitation
8 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9 * and/or sell copies of the Software, and to permit persons to whom the
10 * Software is furnished to do so, subject to the following conditions:
12 * The above copyright notice and this permission notice (including the next
13 * paragraph) shall be included in all copies or substantial portions of the
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
26 * This pass converts the ssa-graph into "Loop Closed SSA form". This is
27 * done by placing phi nodes at the exits of the loop for all values
28 * that are used outside the loop. The result is it transforms:
31 * ssa2 = .... -> ssa2 = ...
32 * if (cond) -> if (cond)
34 * ssa3 = ssa2 * ssa4 -> ssa3 = ssa2 * ssa4
36 * ssa6 = ssa2 + 4 -> ssa5 = phi(ssa2)
43 /* The nir_shader we are transforming */
46 /* The loop we store information for */
49 /* Whether to skip loop invariant variables */
51 bool skip_bool_invariants
;
57 is_if_use_inside_loop(nir_src
*use
, nir_loop
*loop
)
59 nir_block
*block_before_loop
=
60 nir_cf_node_as_block(nir_cf_node_prev(&loop
->cf_node
));
61 nir_block
*block_after_loop
=
62 nir_cf_node_as_block(nir_cf_node_next(&loop
->cf_node
));
64 nir_block
*prev_block
=
65 nir_cf_node_as_block(nir_cf_node_prev(&use
->parent_if
->cf_node
));
66 if (prev_block
->index
<= block_before_loop
->index
||
67 prev_block
->index
>= block_after_loop
->index
) {
75 is_use_inside_loop(nir_src
*use
, nir_loop
*loop
)
77 nir_block
*block_before_loop
=
78 nir_cf_node_as_block(nir_cf_node_prev(&loop
->cf_node
));
79 nir_block
*block_after_loop
=
80 nir_cf_node_as_block(nir_cf_node_next(&loop
->cf_node
));
82 if (use
->parent_instr
->block
->index
<= block_before_loop
->index
||
83 use
->parent_instr
->block
->index
>= block_after_loop
->index
) {
91 is_defined_before_loop(nir_ssa_def
*def
, nir_loop
*loop
)
93 nir_instr
*instr
= def
->parent_instr
;
94 nir_block
*block_before_loop
=
95 nir_cf_node_as_block(nir_cf_node_prev(&loop
->cf_node
));
97 return instr
->block
->index
<= block_before_loop
->index
;
100 typedef enum instr_invariance
{
106 static instr_invariance
107 instr_is_invariant(nir_instr
*instr
, nir_loop
*loop
);
110 def_is_invariant(nir_ssa_def
*def
, nir_loop
*loop
)
112 if (is_defined_before_loop(def
, loop
))
115 if (def
->parent_instr
->pass_flags
== undefined
)
116 def
->parent_instr
->pass_flags
= instr_is_invariant(def
->parent_instr
, loop
);
118 return def
->parent_instr
->pass_flags
== invariant
;
122 src_is_invariant(nir_src
*src
, void *state
)
125 return def_is_invariant(src
->ssa
, (nir_loop
*)state
);
128 static instr_invariance
129 phi_is_invariant(nir_phi_instr
*instr
, nir_loop
*loop
)
131 /* Base case: it's a phi at the loop header
132 * Loop-header phis are updated in each loop iteration with
133 * the loop-carried value, and thus control-flow dependent
134 * on the loop itself.
136 if (instr
->instr
.block
== nir_loop_first_block(loop
))
137 return not_invariant
;
139 nir_foreach_phi_src(src
, instr
) {
140 if (!src_is_invariant(&src
->src
, loop
))
141 return not_invariant
;
144 /* All loop header- and LCSSA-phis should be handled by this point. */
145 nir_cf_node
*prev
= nir_cf_node_prev(&instr
->instr
.block
->cf_node
);
146 assert(prev
&& prev
->type
== nir_cf_node_if
);
148 /* Invariance of phis after if-nodes also depends on the invariance
149 * of the branch condition.
151 nir_if
*if_node
= nir_cf_node_as_if(prev
);
152 if (!def_is_invariant(if_node
->condition
.ssa
, loop
))
153 return not_invariant
;
159 /* An instruction is said to be loop-invariant if it
160 * - has no sideeffects and
161 * - solely depends on variables defined outside of the loop or
162 * by other invariant instructions
164 static instr_invariance
165 instr_is_invariant(nir_instr
*instr
, nir_loop
*loop
)
167 assert(instr
->pass_flags
== undefined
);
169 switch (instr
->type
) {
170 case nir_instr_type_load_const
:
171 case nir_instr_type_ssa_undef
:
173 case nir_instr_type_call
:
174 return not_invariant
;
175 case nir_instr_type_phi
:
176 return phi_is_invariant(nir_instr_as_phi(instr
), loop
);
177 case nir_instr_type_intrinsic
: {
178 nir_intrinsic_instr
*intrinsic
= nir_instr_as_intrinsic(instr
);
179 if (!(nir_intrinsic_infos
[intrinsic
->intrinsic
].flags
& NIR_INTRINSIC_CAN_REORDER
))
180 return not_invariant
;
184 return nir_foreach_src(instr
, src_is_invariant
, loop
) ? invariant
: not_invariant
;
191 convert_loop_exit_for_ssa(nir_ssa_def
*def
, void *void_state
)
193 lcssa_state
*state
= void_state
;
194 bool all_uses_inside_loop
= true;
196 /* Don't create LCSSA-Phis for loop-invariant variables */
197 if (state
->skip_invariants
&&
198 (def
->bit_size
!= 1 || state
->skip_bool_invariants
)) {
199 assert(def
->parent_instr
->pass_flags
!= undefined
);
200 if (def
->parent_instr
->pass_flags
== invariant
)
204 nir_block
*block_after_loop
=
205 nir_cf_node_as_block(nir_cf_node_next(&state
->loop
->cf_node
));
207 nir_foreach_use(use
, def
) {
208 if (use
->parent_instr
->type
== nir_instr_type_phi
&&
209 use
->parent_instr
->block
== block_after_loop
) {
213 if (!is_use_inside_loop(use
, state
->loop
)) {
214 all_uses_inside_loop
= false;
218 nir_foreach_if_use(use
, def
) {
219 if (!is_if_use_inside_loop(use
, state
->loop
)) {
220 all_uses_inside_loop
= false;
224 /* There where no sources that had defs outside the loop */
225 if (all_uses_inside_loop
)
228 /* Initialize a phi-instruction */
229 nir_phi_instr
*phi
= nir_phi_instr_create(state
->shader
);
230 nir_ssa_dest_init(&phi
->instr
, &phi
->dest
,
231 def
->num_components
, def
->bit_size
, "LCSSA-phi");
233 /* Create a phi node with as many sources pointing to the same ssa_def as
234 * the block has predecessors.
236 set_foreach(block_after_loop
->predecessors
, entry
) {
237 nir_phi_src
*phi_src
= ralloc(phi
, nir_phi_src
);
238 phi_src
->src
= nir_src_for_ssa(def
);
239 phi_src
->pred
= (nir_block
*) entry
->key
;
241 exec_list_push_tail(&phi
->srcs
, &phi_src
->node
);
244 nir_instr_insert_before_block(block_after_loop
, &phi
->instr
);
245 nir_ssa_def
*dest
= &phi
->dest
.ssa
;
247 /* deref instructions need a cast after the phi */
248 if (def
->parent_instr
->type
== nir_instr_type_deref
) {
249 nir_deref_instr
*cast
=
250 nir_deref_instr_create(state
->shader
, nir_deref_type_cast
);
252 nir_deref_instr
*instr
= nir_instr_as_deref(def
->parent_instr
);
253 cast
->mode
= instr
->mode
;
254 cast
->type
= instr
->type
;
255 cast
->parent
= nir_src_for_ssa(&phi
->dest
.ssa
);
256 cast
->cast
.ptr_stride
= nir_deref_instr_ptr_as_array_stride(instr
);
258 nir_ssa_dest_init(&cast
->instr
, &cast
->dest
,
259 phi
->dest
.ssa
.num_components
,
260 phi
->dest
.ssa
.bit_size
, NULL
);
261 nir_instr_insert(nir_after_phis(block_after_loop
), &cast
->instr
);
262 dest
= &cast
->dest
.ssa
;
265 /* Run through all uses and rewrite those outside the loop to point to
266 * the phi instead of pointing to the ssa-def.
268 nir_foreach_use_safe(use
, def
) {
269 if (use
->parent_instr
->type
== nir_instr_type_phi
&&
270 block_after_loop
== use
->parent_instr
->block
) {
274 if (!is_use_inside_loop(use
, state
->loop
)) {
275 nir_instr_rewrite_src(use
->parent_instr
, use
, nir_src_for_ssa(dest
));
279 nir_foreach_if_use_safe(use
, def
) {
280 if (!is_if_use_inside_loop(use
, state
->loop
)) {
281 nir_if_rewrite_condition(use
->parent_if
, nir_src_for_ssa(dest
));
285 state
->progress
= true;
290 convert_to_lcssa(nir_cf_node
*cf_node
, lcssa_state
*state
)
292 switch (cf_node
->type
) {
293 case nir_cf_node_block
:
295 case nir_cf_node_if
: {
296 nir_if
*if_stmt
= nir_cf_node_as_if(cf_node
);
297 foreach_list_typed(nir_cf_node
, nested_node
, node
, &if_stmt
->then_list
)
298 convert_to_lcssa(nested_node
, state
);
299 foreach_list_typed(nir_cf_node
, nested_node
, node
, &if_stmt
->else_list
)
300 convert_to_lcssa(nested_node
, state
);
303 case nir_cf_node_loop
: {
304 if (state
->skip_invariants
) {
305 nir_foreach_block_in_cf_node(block
, cf_node
) {
306 nir_foreach_instr(instr
, block
)
307 instr
->pass_flags
= undefined
;
311 /* first, convert inner loops */
312 nir_loop
*loop
= nir_cf_node_as_loop(cf_node
);
313 foreach_list_typed(nir_cf_node
, nested_node
, node
, &loop
->body
)
314 convert_to_lcssa(nested_node
, state
);
316 /* mark loop-invariant instructions */
317 if (state
->skip_invariants
) {
318 nir_foreach_block_in_cf_node(block
, cf_node
) {
319 nir_foreach_instr(instr
, block
) {
320 if (instr
->pass_flags
== undefined
)
321 instr
->pass_flags
= instr_is_invariant(instr
, nir_cf_node_as_loop(cf_node
));
327 nir_foreach_block_in_cf_node(block
, cf_node
) {
328 nir_foreach_instr(instr
, block
) {
329 nir_foreach_ssa_def(instr
, convert_loop_exit_for_ssa
, state
);
331 /* for outer loops, invariant instructions can be variant */
332 if (state
->skip_invariants
&& instr
->pass_flags
== invariant
)
333 instr
->pass_flags
= undefined
;
337 /* For outer loops, the LCSSA-phi should be considered not invariant */
338 if (state
->skip_invariants
) {
339 nir_block
*block_after_loop
=
340 nir_cf_node_as_block(nir_cf_node_next(&state
->loop
->cf_node
));
341 nir_foreach_instr(instr
, block_after_loop
) {
342 if (instr
->type
== nir_instr_type_phi
)
343 instr
->pass_flags
= not_invariant
;
351 unreachable("unknown cf node type");
356 nir_convert_loop_to_lcssa(nir_loop
*loop
)
358 nir_function_impl
*impl
= nir_cf_node_get_function(&loop
->cf_node
);
360 nir_metadata_require(impl
, nir_metadata_block_index
);
362 lcssa_state
*state
= rzalloc(NULL
, lcssa_state
);
364 state
->shader
= impl
->function
->shader
;
365 state
->skip_invariants
= false;
366 state
->skip_bool_invariants
= false;
368 nir_foreach_block_in_cf_node (block
, &loop
->cf_node
) {
369 nir_foreach_instr(instr
, block
)
370 nir_foreach_ssa_def(instr
, convert_loop_exit_for_ssa
, state
);
377 nir_convert_to_lcssa(nir_shader
*shader
, bool skip_invariants
, bool skip_bool_invariants
)
379 bool progress
= false;
380 lcssa_state
*state
= rzalloc(NULL
, lcssa_state
);
381 state
->shader
= shader
;
382 state
->skip_invariants
= skip_invariants
;
383 state
->skip_bool_invariants
= skip_bool_invariants
;
385 nir_foreach_function(function
, shader
) {
386 if (function
->impl
== NULL
)
389 state
->progress
= false;
390 nir_metadata_require(function
->impl
, nir_metadata_block_index
);
392 foreach_list_typed(nir_cf_node
, node
, node
, &function
->impl
->body
)
393 convert_to_lcssa(node
, state
);
395 if (state
->progress
) {
397 nir_metadata_preserve(function
->impl
, nir_metadata_block_index
|
398 nir_metadata_dominance
);
400 nir_metadata_preserve(function
->impl
, nir_metadata_all
);