1 /*
2 * Copyright © 2015 Thomas Helland
3 * Copyright © 2019 Valve Corporation
4 *
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:
11 *
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
14 * Software.
15 *
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
22 * IN THE SOFTWARE.
23 */
24
25 /*
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:
29 *
30 * loop { -> loop {
31 * ssa2 = .... -> ssa2 = ...
32 * if (cond) -> if (cond)
33 * break; -> break;
34 * ssa3 = ssa2 * ssa4 -> ssa3 = ssa2 * ssa4
35 * } -> }
36 * ssa6 = ssa2 + 4 -> ssa5 = phi(ssa2)
37 * ssa6 = ssa5 + 4
38 */
39
40 #include "nir.h"
41
42 typedef struct {
43 /* The nir_shader we are transforming */
44 nir_shader *shader;
45
46 /* The loop we store information for */
47 nir_loop *loop;
48 nir_block *block_after_loop;
49 nir_block **exit_blocks;
50
51 /* Whether to skip loop invariant variables */
52 bool skip_invariants;
53 bool skip_bool_invariants;
54
55 bool progress;
56 } lcssa_state;
57
58 static bool
is_if_use_inside_loop(nir_src * use,nir_loop * loop)59 is_if_use_inside_loop(nir_src *use, nir_loop *loop)
60 {
61 nir_block *block_before_loop =
62 nir_cf_node_as_block(nir_cf_node_prev(&loop->cf_node));
63 nir_block *block_after_loop =
64 nir_cf_node_as_block(nir_cf_node_next(&loop->cf_node));
65
66 nir_block *prev_block =
67 nir_cf_node_as_block(nir_cf_node_prev(&nir_src_parent_if(use)->cf_node));
68 if (prev_block->index <= block_before_loop->index ||
69 prev_block->index >= block_after_loop->index) {
70 return false;
71 }
72
73 return true;
74 }
75
76 static bool
is_use_inside_loop(nir_src * use,nir_loop * loop)77 is_use_inside_loop(nir_src *use, nir_loop *loop)
78 {
79 nir_block *block_before_loop =
80 nir_cf_node_as_block(nir_cf_node_prev(&loop->cf_node));
81 nir_block *block_after_loop =
82 nir_cf_node_as_block(nir_cf_node_next(&loop->cf_node));
83
84 if (nir_src_parent_instr(use)->block->index <= block_before_loop->index ||
85 nir_src_parent_instr(use)->block->index >= block_after_loop->index) {
86 return false;
87 }
88
89 return true;
90 }
91
92 static bool
is_defined_before_loop(nir_def * def,nir_loop * loop)93 is_defined_before_loop(nir_def *def, nir_loop *loop)
94 {
95 nir_instr *instr = def->parent_instr;
96 nir_block *block_before_loop =
97 nir_cf_node_as_block(nir_cf_node_prev(&loop->cf_node));
98
99 return instr->block->index <= block_before_loop->index;
100 }
101
102 typedef enum instr_invariance {
103 undefined = 0,
104 invariant,
105 not_invariant,
106 } instr_invariance;
107
108 static instr_invariance
109 instr_is_invariant(nir_instr *instr, nir_loop *loop);
110
111 static bool
def_is_invariant(nir_def * def,nir_loop * loop)112 def_is_invariant(nir_def *def, nir_loop *loop)
113 {
114 if (is_defined_before_loop(def, loop))
115 return invariant;
116
117 if (def->parent_instr->pass_flags == undefined)
118 def->parent_instr->pass_flags = instr_is_invariant(def->parent_instr, loop);
119
120 return def->parent_instr->pass_flags == invariant;
121 }
122
123 static bool
src_is_invariant(nir_src * src,void * state)124 src_is_invariant(nir_src *src, void *state)
125 {
126 return def_is_invariant(src->ssa, (nir_loop *)state);
127 }
128
129 static instr_invariance
phi_is_invariant(nir_phi_instr * instr,nir_loop * loop)130 phi_is_invariant(nir_phi_instr *instr, nir_loop *loop)
131 {
132 /* Base case: it's a phi at the loop header
133 * Loop-header phis are updated in each loop iteration with
134 * the loop-carried value, and thus control-flow dependent
135 * on the loop itself.
136 */
137 if (instr->instr.block == nir_loop_first_block(loop))
138 return not_invariant;
139
140 nir_foreach_phi_src(src, instr) {
141 if (!src_is_invariant(&src->src, loop))
142 return not_invariant;
143 }
144
145 /* All loop header- and LCSSA-phis should be handled by this point. */
146 nir_cf_node *prev = nir_cf_node_prev(&instr->instr.block->cf_node);
147 assert(prev && prev->type == nir_cf_node_if);
148
149 /* Invariance of phis after if-nodes also depends on the invariance
150 * of the branch condition.
151 */
152 nir_if *if_node = nir_cf_node_as_if(prev);
153 if (!def_is_invariant(if_node->condition.ssa, loop))
154 return not_invariant;
155
156 return invariant;
157 }
158
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
163 */
164 static instr_invariance
instr_is_invariant(nir_instr * instr,nir_loop * loop)165 instr_is_invariant(nir_instr *instr, nir_loop *loop)
166 {
167 assert(instr->pass_flags == undefined);
168
169 switch (instr->type) {
170 case nir_instr_type_load_const:
171 case nir_instr_type_undef:
172 return invariant;
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;
181 }
182 FALLTHROUGH;
183 default:
184 return nir_foreach_src(instr, src_is_invariant, loop) ? invariant : not_invariant;
185 }
186
187 return invariant;
188 }
189
190 static bool
convert_loop_exit_for_ssa(nir_def * def,void * void_state)191 convert_loop_exit_for_ssa(nir_def *def, void *void_state)
192 {
193 lcssa_state *state = void_state;
194 bool all_uses_inside_loop = true;
195
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)
201 return true;
202 }
203
204 nir_foreach_use_including_if(use, def) {
205 if (nir_src_is_if(use)) {
206 if (!is_if_use_inside_loop(use, state->loop))
207 all_uses_inside_loop = false;
208
209 continue;
210 }
211
212 if (nir_src_parent_instr(use)->type == nir_instr_type_phi &&
213 nir_src_parent_instr(use)->block == state->block_after_loop) {
214 continue;
215 }
216
217 if (!is_use_inside_loop(use, state->loop)) {
218 all_uses_inside_loop = false;
219 }
220 }
221
222 /* There where no sources that had defs outside the loop */
223 if (all_uses_inside_loop)
224 return true;
225
226 if (def->parent_instr->type == nir_instr_type_deref) {
227 nir_rematerialize_deref_in_use_blocks(nir_instr_as_deref(def->parent_instr));
228 return true;
229 }
230
231 /* Initialize a phi-instruction */
232 nir_phi_instr *phi = nir_phi_instr_create(state->shader);
233 nir_def_init(&phi->instr, &phi->def, def->num_components,
234 def->bit_size);
235
236 /* Create a phi node with as many sources pointing to the same ssa_def as
237 * the block has predecessors.
238 */
239 uint32_t num_exits = state->block_after_loop->predecessors->entries;
240 for (uint32_t i = 0; i < num_exits; i++) {
241 nir_phi_instr_add_src(phi, state->exit_blocks[i], def);
242 }
243
244 nir_instr_insert_before_block(state->block_after_loop, &phi->instr);
245 nir_def *dest = &phi->def;
246
247 /* Run through all uses and rewrite those outside the loop to point to
248 * the phi instead of pointing to the ssa-def.
249 */
250 nir_foreach_use_including_if_safe(use, def) {
251 if (nir_src_is_if(use)) {
252 if (!is_if_use_inside_loop(use, state->loop))
253 nir_src_rewrite(&nir_src_parent_if(use)->condition, dest);
254
255 continue;
256 }
257
258 if (nir_src_parent_instr(use)->type == nir_instr_type_phi &&
259 state->block_after_loop == nir_src_parent_instr(use)->block) {
260 continue;
261 }
262
263 if (!is_use_inside_loop(use, state->loop)) {
264 nir_src_rewrite(use, dest);
265 }
266 }
267
268 state->progress = true;
269 return true;
270 }
271
272 static void
setup_loop_state(lcssa_state * state,nir_loop * loop)273 setup_loop_state(lcssa_state *state, nir_loop *loop)
274 {
275 state->loop = loop;
276 state->block_after_loop =
277 nir_cf_node_as_block(nir_cf_node_next(&loop->cf_node));
278
279 ralloc_free(state->exit_blocks);
280 state->exit_blocks = nir_block_get_predecessors_sorted(state->block_after_loop, state);
281 }
282
283 static void
convert_to_lcssa(nir_cf_node * cf_node,lcssa_state * state)284 convert_to_lcssa(nir_cf_node *cf_node, lcssa_state *state)
285 {
286 switch (cf_node->type) {
287 case nir_cf_node_block:
288 return;
289 case nir_cf_node_if: {
290 nir_if *if_stmt = nir_cf_node_as_if(cf_node);
291 foreach_list_typed(nir_cf_node, nested_node, node, &if_stmt->then_list)
292 convert_to_lcssa(nested_node, state);
293 foreach_list_typed(nir_cf_node, nested_node, node, &if_stmt->else_list)
294 convert_to_lcssa(nested_node, state);
295 return;
296 }
297 case nir_cf_node_loop: {
298 if (state->skip_invariants) {
299 nir_foreach_block_in_cf_node(block, cf_node) {
300 nir_foreach_instr(instr, block)
301 instr->pass_flags = undefined;
302 }
303 }
304
305 /* first, convert inner loops */
306 nir_loop *loop = nir_cf_node_as_loop(cf_node);
307 assert(!nir_loop_has_continue_construct(loop));
308 foreach_list_typed(nir_cf_node, nested_node, node, &loop->body)
309 convert_to_lcssa(nested_node, state);
310
311 setup_loop_state(state, loop);
312
313 /* mark loop-invariant instructions */
314 if (state->skip_invariants) {
315 /* Without a loop all instructions are invariant.
316 * For outer loops, multiple breaks can still create phis.
317 * The variance then depends on all (nested) break conditions.
318 * We don't consider this, but assume all not_invariant.
319 */
320 if (nir_loop_first_block(loop)->predecessors->entries == 1)
321 goto end;
322
323 nir_foreach_block_in_cf_node(block, cf_node) {
324 nir_foreach_instr(instr, block) {
325 if (instr->pass_flags == undefined)
326 instr->pass_flags = instr_is_invariant(instr, nir_cf_node_as_loop(cf_node));
327 }
328 }
329 }
330
331 nir_foreach_block_in_cf_node_reverse(block, cf_node) {
332 nir_foreach_instr_reverse_safe(instr, block) {
333 nir_foreach_def(instr, convert_loop_exit_for_ssa, state);
334
335 /* for outer loops, invariant instructions can be variant */
336 if (state->skip_invariants && instr->pass_flags == invariant)
337 instr->pass_flags = undefined;
338 }
339 }
340
341 end:
342 /* For outer loops, the LCSSA-phi should be considered not invariant */
343 if (state->skip_invariants) {
344 nir_foreach_instr(instr, state->block_after_loop) {
345 if (instr->type == nir_instr_type_phi)
346 instr->pass_flags = not_invariant;
347 else
348 break;
349 }
350 }
351 return;
352 }
353 default:
354 unreachable("unknown cf node type");
355 }
356 }
357
358 void
nir_convert_loop_to_lcssa(nir_loop * loop)359 nir_convert_loop_to_lcssa(nir_loop *loop)
360 {
361 assert(!nir_loop_has_continue_construct(loop));
362 nir_function_impl *impl = nir_cf_node_get_function(&loop->cf_node);
363
364 nir_metadata_require(impl, nir_metadata_block_index);
365
366 lcssa_state *state = rzalloc(NULL, lcssa_state);
367 setup_loop_state(state, loop);
368 state->shader = impl->function->shader;
369 state->skip_invariants = false;
370 state->skip_bool_invariants = false;
371
372 nir_foreach_block_in_cf_node_reverse(block, &loop->cf_node) {
373 nir_foreach_instr_reverse_safe(instr, block)
374 nir_foreach_def(instr, convert_loop_exit_for_ssa, state);
375 }
376
377 ralloc_free(state);
378 }
379
380 bool
nir_convert_to_lcssa(nir_shader * shader,bool skip_invariants,bool skip_bool_invariants)381 nir_convert_to_lcssa(nir_shader *shader, bool skip_invariants, bool skip_bool_invariants)
382 {
383 bool progress = false;
384 lcssa_state *state = rzalloc(NULL, lcssa_state);
385 state->shader = shader;
386 state->skip_invariants = skip_invariants;
387 state->skip_bool_invariants = skip_bool_invariants;
388
389 nir_foreach_function_impl(impl, shader) {
390 state->progress = false;
391 nir_metadata_require(impl, nir_metadata_block_index);
392
393 foreach_list_typed(nir_cf_node, node, node, &impl->body)
394 convert_to_lcssa(node, state);
395
396 if (state->progress) {
397 progress = true;
398 nir_metadata_preserve(impl, nir_metadata_control_flow);
399 } else {
400 nir_metadata_preserve(impl, nir_metadata_all);
401 }
402 }
403
404 ralloc_free(state);
405 return progress;
406 }
407