2 * Copyright © 2015 Thomas Helland
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 * This pass converts the ssa-graph into "Loop Closed SSA form". This is
26 * done by placing phi nodes at the exits of the loop for all values
27 * that are used outside the loop. The result is it transforms:
30 * ssa2 = .... -> ssa2 = ...
31 * if (cond) -> if (cond)
33 * ssa3 = ssa2 * ssa4 -> ssa3 = ssa2 * ssa4
35 * ssa6 = ssa2 + 4 -> ssa5 = phi(ssa2)
42 /* The nir_shader we are transforming */
45 /* The loop we store information for */
51 is_if_use_inside_loop(nir_src
*use
, nir_loop
* loop
)
53 nir_block
*block_before_loop
=
54 nir_cf_node_as_block(nir_cf_node_prev(&loop
->cf_node
));
55 nir_block
*block_after_loop
=
56 nir_cf_node_as_block(nir_cf_node_next(&loop
->cf_node
));
58 nir_block
*prev_block
=
59 nir_cf_node_as_block(nir_cf_node_prev(&use
->parent_if
->cf_node
));
60 if (prev_block
->index
<= block_before_loop
->index
||
61 prev_block
->index
>= block_after_loop
->index
) {
69 is_use_inside_loop(nir_src
*use
, nir_loop
* loop
)
71 nir_block
*block_before_loop
=
72 nir_cf_node_as_block(nir_cf_node_prev(&loop
->cf_node
));
73 nir_block
*block_after_loop
=
74 nir_cf_node_as_block(nir_cf_node_next(&loop
->cf_node
));
76 if (use
->parent_instr
->block
->index
<= block_before_loop
->index
||
77 use
->parent_instr
->block
->index
>= block_after_loop
->index
) {
85 convert_loop_exit_for_ssa(nir_ssa_def
*def
, void *void_state
)
87 lcssa_state
*state
= void_state
;
88 bool all_uses_inside_loop
= true;
90 nir_block
*block_after_loop
=
91 nir_cf_node_as_block(nir_cf_node_next(&state
->loop
->cf_node
));
93 nir_foreach_use(use
, def
) {
94 if (use
->parent_instr
->type
== nir_instr_type_phi
&&
95 use
->parent_instr
->block
== block_after_loop
) {
99 if (!is_use_inside_loop(use
, state
->loop
)) {
100 all_uses_inside_loop
= false;
104 nir_foreach_if_use(use
, def
) {
105 if (!is_if_use_inside_loop(use
, state
->loop
)) {
106 all_uses_inside_loop
= false;
110 /* There where no sources that had defs outside the loop */
111 if (all_uses_inside_loop
)
114 /* Initialize a phi-instruction */
115 nir_phi_instr
*phi
= nir_phi_instr_create(state
->shader
);
116 nir_ssa_dest_init(&phi
->instr
, &phi
->dest
,
117 def
->num_components
, def
->bit_size
, "LCSSA-phi");
119 /* Create a phi node with as many sources pointing to the same ssa_def as
120 * the block has predecessors.
122 struct set_entry
*entry
;
123 set_foreach(block_after_loop
->predecessors
, entry
) {
124 nir_phi_src
*phi_src
= ralloc(phi
, nir_phi_src
);
125 phi_src
->src
= nir_src_for_ssa(def
);
126 phi_src
->pred
= (nir_block
*) entry
->key
;
128 exec_list_push_tail(&phi
->srcs
, &phi_src
->node
);
131 nir_instr_insert_before_block(block_after_loop
, &phi
->instr
);
133 /* Run through all uses and rewrite those outside the loop to point to
134 * the phi instead of pointing to the ssa-def.
136 nir_foreach_use_safe(use
, def
) {
137 if (use
->parent_instr
->type
== nir_instr_type_phi
&&
138 block_after_loop
== use
->parent_instr
->block
) {
142 if (!is_use_inside_loop(use
, state
->loop
)) {
143 nir_instr_rewrite_src(use
->parent_instr
, use
,
144 nir_src_for_ssa(&phi
->dest
.ssa
));
148 nir_foreach_if_use_safe(use
, def
) {
149 if (!is_if_use_inside_loop(use
, state
->loop
)) {
150 nir_if_rewrite_condition(use
->parent_if
,
151 nir_src_for_ssa(&phi
->dest
.ssa
));
159 convert_to_lcssa(nir_cf_node
*cf_node
, lcssa_state
*state
)
161 switch (cf_node
->type
) {
162 case nir_cf_node_block
:
163 nir_foreach_instr(instr
, nir_cf_node_as_block(cf_node
))
164 nir_foreach_ssa_def(instr
, convert_loop_exit_for_ssa
, state
);
166 case nir_cf_node_if
: {
167 nir_if
*if_stmt
= nir_cf_node_as_if(cf_node
);
168 foreach_list_typed(nir_cf_node
, nested_node
, node
, &if_stmt
->then_list
)
169 convert_to_lcssa(nested_node
, state
);
170 foreach_list_typed(nir_cf_node
, nested_node
, node
, &if_stmt
->else_list
)
171 convert_to_lcssa(nested_node
, state
);
174 case nir_cf_node_loop
: {
175 nir_loop
*parent_loop
= state
->loop
;
176 state
->loop
= nir_cf_node_as_loop(cf_node
);
178 foreach_list_typed(nir_cf_node
, nested_node
, node
, &state
->loop
->body
)
179 convert_to_lcssa(nested_node
, state
);
181 state
->loop
= parent_loop
;
185 unreachable("unknown cf node type");
190 nir_convert_loop_to_lcssa(nir_loop
*loop
) {
191 nir_function_impl
*impl
= nir_cf_node_get_function(&loop
->cf_node
);
193 nir_metadata_require(impl
, nir_metadata_block_index
);
195 lcssa_state
*state
= rzalloc(NULL
, lcssa_state
);
197 state
->shader
= impl
->function
->shader
;
199 foreach_list_typed(nir_cf_node
, node
, node
, &state
->loop
->body
)
200 convert_to_lcssa(node
, state
);