1 /*
2 * Copyright © 2015 Thomas Helland
3 *
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:
10 *
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
13 * Software.
14 *
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
21 * IN THE SOFTWARE.
22 */
23
24 /*
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:
28 *
29 * loop { -> loop {
30 * ssa2 = .... -> ssa2 = ...
31 * if (cond) -> if (cond)
32 * break; -> break;
33 * ssa3 = ssa2 * ssa4 -> ssa3 = ssa2 * ssa4
34 * } -> }
35 * ssa6 = ssa2 + 4 -> ssa5 = phi(ssa2)
36 * ssa6 = ssa5 + 4
37 */
38
39 #include "nir.h"
40
41 typedef struct {
42 /* The nir_shader we are transforming */
43 nir_shader *shader;
44
45 /* The loop we store information for */
46 nir_loop *loop;
47
48 } lcssa_state;
49
50 static bool
is_if_use_inside_loop(nir_src * use,nir_loop * loop)51 is_if_use_inside_loop(nir_src *use, nir_loop* loop)
52 {
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));
57
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) {
62 return false;
63 }
64
65 return true;
66 }
67
68 static bool
is_use_inside_loop(nir_src * use,nir_loop * loop)69 is_use_inside_loop(nir_src *use, nir_loop* loop)
70 {
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));
75
76 if (use->parent_instr->block->index <= block_before_loop->index ||
77 use->parent_instr->block->index >= block_after_loop->index) {
78 return false;
79 }
80
81 return true;
82 }
83
84 static bool
convert_loop_exit_for_ssa(nir_ssa_def * def,void * void_state)85 convert_loop_exit_for_ssa(nir_ssa_def *def, void *void_state)
86 {
87 lcssa_state *state = void_state;
88 bool all_uses_inside_loop = true;
89
90 nir_block *block_after_loop =
91 nir_cf_node_as_block(nir_cf_node_next(&state->loop->cf_node));
92
93 nir_foreach_use(use, def) {
94 if (use->parent_instr->type == nir_instr_type_phi &&
95 use->parent_instr->block == block_after_loop) {
96 continue;
97 }
98
99 if (!is_use_inside_loop(use, state->loop)) {
100 all_uses_inside_loop = false;
101 }
102 }
103
104 nir_foreach_if_use(use, def) {
105 if (!is_if_use_inside_loop(use, state->loop)) {
106 all_uses_inside_loop = false;
107 }
108 }
109
110 /* There where no sources that had defs outside the loop */
111 if (all_uses_inside_loop)
112 return true;
113
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");
118
119 /* Create a phi node with as many sources pointing to the same ssa_def as
120 * the block has predecessors.
121 */
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;
127
128 exec_list_push_tail(&phi->srcs, &phi_src->node);
129 }
130
131 nir_instr_insert_before_block(block_after_loop, &phi->instr);
132
133 /* Run through all uses and rewrite those outside the loop to point to
134 * the phi instead of pointing to the ssa-def.
135 */
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) {
139 continue;
140 }
141
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));
145 }
146 }
147
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));
152 }
153 }
154
155 return true;
156 }
157
158 static void
convert_to_lcssa(nir_cf_node * cf_node,lcssa_state * state)159 convert_to_lcssa(nir_cf_node *cf_node, lcssa_state *state)
160 {
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);
165 return;
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);
172 return;
173 }
174 case nir_cf_node_loop: {
175 nir_loop *parent_loop = state->loop;
176 state->loop = nir_cf_node_as_loop(cf_node);
177
178 foreach_list_typed(nir_cf_node, nested_node, node, &state->loop->body)
179 convert_to_lcssa(nested_node, state);
180
181 state->loop = parent_loop;
182 return;
183 }
184 default:
185 unreachable("unknown cf node type");
186 }
187 }
188
189 void
nir_convert_loop_to_lcssa(nir_loop * loop)190 nir_convert_loop_to_lcssa(nir_loop *loop) {
191 nir_function_impl *impl = nir_cf_node_get_function(&loop->cf_node);
192
193 nir_metadata_require(impl, nir_metadata_block_index);
194
195 lcssa_state *state = rzalloc(NULL, lcssa_state);
196 state->loop = loop;
197 state->shader = impl->function->shader;
198
199 foreach_list_typed(nir_cf_node, node, node, &state->loop->body)
200 convert_to_lcssa(node, state);
201
202 ralloc_free(state);
203 }
204