1 /*
2 * Copyright 2023 Valve Corporation
3 * SPDX-License-Identifier: MIT
4 */
5
6 #include "nir.h"
7 #include "nir_control_flow.h"
8
9 static bool
is_block_empty(nir_block * block)10 is_block_empty(nir_block *block)
11 {
12 return nir_cf_node_is_last(&block->cf_node) &&
13 exec_list_is_empty(&block->instr_list);
14 }
15
16 static bool
is_block_singular(nir_block * block)17 is_block_singular(nir_block *block)
18 {
19 return nir_cf_node_is_last(&block->cf_node) &&
20 (exec_list_is_empty(&block->instr_list) ||
21 (exec_list_is_singular(&block->instr_list) && nir_block_ends_in_jump(block)));
22 }
23
24 static bool
nir_block_ends_in_continue(nir_block * block)25 nir_block_ends_in_continue(nir_block *block)
26 {
27 if (exec_list_is_empty(&block->instr_list))
28 return false;
29
30 nir_instr *instr = nir_block_last_instr(block);
31 return instr->type == nir_instr_type_jump &&
32 nir_instr_as_jump(instr)->type == nir_jump_continue;
33 }
34
35 /**
36 * This optimization tries to merge two equal jump instructions (break or
37 * continue) into a single one.
38 *
39 * This optimization turns
40 *
41 * loop {
42 * ...
43 * if (cond) {
44 * do_work_1();
45 * break;
46 * } else {
47 * do_work_2();
48 * break;
49 * }
50 * }
51 *
52 * into:
53 *
54 * loop {
55 * ...
56 * if (cond) {
57 * do_work_1();
58 * } else {
59 * do_work_2();
60 * }
61 * break;
62 * }
63 *
64 * It does the same with continue statements, respectively.
65 *
66 */
67 static bool
opt_loop_merge_break_continue(nir_if * nif)68 opt_loop_merge_break_continue(nir_if *nif)
69 {
70 nir_block *after_if = nir_cf_node_cf_tree_next(&nif->cf_node);
71
72 /* The block after the IF must have no predecessors and be empty. */
73 if (after_if->predecessors->entries > 0 || !is_block_empty(after_if))
74 return false;
75
76 nir_block *last_then = nir_if_last_then_block(nif);
77 nir_block *last_else = nir_if_last_else_block(nif);
78 const bool then_break = nir_block_ends_in_break(last_then);
79 const bool else_break = nir_block_ends_in_break(last_else);
80 const bool then_cont = nir_block_ends_in_continue(last_then);
81 const bool else_cont = nir_block_ends_in_continue(last_else);
82
83 /* If both branch legs end with the same jump instruction,
84 * merge the statement after the branch
85 */
86 if ((then_break && else_break) || (then_cont && else_cont)) {
87 nir_lower_phis_to_regs_block(last_then->successors[0]);
88 nir_instr_remove_v(nir_block_last_instr(last_then));
89 nir_instr *jump = nir_block_last_instr(last_else);
90 nir_instr_remove_v(jump);
91 nir_instr_insert(nir_after_block(after_if), jump);
92 return true;
93 }
94
95 return false;
96 }
97
98 /**
99 * This optimization simplifies potential loop terminators which then allows
100 * other passes such as opt_if_simplification() and loop unrolling to progress
101 * further:
102 *
103 * if (cond) {
104 * ... then block instructions ...
105 * } else {
106 * ...
107 * break;
108 * }
109 *
110 * into:
111 *
112 * if (cond) {
113 * } else {
114 * ...
115 * break;
116 * }
117 * ... then block instructions ...
118 */
119 static bool
opt_loop_terminator(nir_if * nif)120 opt_loop_terminator(nir_if *nif)
121 {
122 nir_block *break_blk = NULL;
123 nir_block *continue_from_blk = NULL;
124 nir_block *first_continue_from_blk = NULL;
125
126 nir_block *last_then = nir_if_last_then_block(nif);
127 nir_block *last_else = nir_if_last_else_block(nif);
128
129 if (nir_block_ends_in_break(last_then)) {
130 break_blk = last_then;
131 continue_from_blk = last_else;
132 first_continue_from_blk = nir_if_first_else_block(nif);
133 } else if (nir_block_ends_in_break(last_else)) {
134 break_blk = last_else;
135 continue_from_blk = last_then;
136 first_continue_from_blk = nir_if_first_then_block(nif);
137 }
138
139 /* Continue if the if-statement contained no jumps at all */
140 if (!break_blk)
141 return false;
142
143 /* If the continue from block is empty then return as there is nothing to
144 * move.
145 */
146 if (is_block_empty(first_continue_from_blk))
147 return false;
148
149 if (nir_block_ends_in_jump(continue_from_blk)) {
150 /* Let nir_opt_dead_cf() clean up any dead code. */
151 if (!is_block_empty(nir_cf_node_cf_tree_next(&nif->cf_node)))
152 return false;
153
154 /* We are about to move the predecessor. */
155 nir_lower_phis_to_regs_block(continue_from_blk->successors[0]);
156 }
157
158 /* Even though this if statement has a jump on one side, we may still have
159 * phis afterwards. Single-source phis can be produced by loop unrolling
160 * or dead control-flow passes and are perfectly legal. Run a quick phi
161 * removal on the block after the if to clean up any such phis.
162 */
163 nir_opt_remove_phis_block(nir_cf_node_as_block(nir_cf_node_next(&nif->cf_node)));
164
165 /* Finally, move the continue from branch after the if-statement. */
166 nir_cf_list tmp;
167 nir_cf_extract(&tmp, nir_before_block(first_continue_from_blk),
168 nir_after_block(continue_from_blk));
169 nir_cf_reinsert(&tmp, nir_after_cf_node(&nif->cf_node));
170
171 return true;
172 }
173
174 /**
175 * This optimization tries to merge the jump instruction (break or continue)
176 * of a block with an equal one from a previous IF.
177 *
178 * This optimization turns:
179 *
180 * loop {
181 * ...
182 * if (cond) {
183 * do_work_1();
184 * break;
185 * } else {
186 * }
187 * do_work_2();
188 * break;
189 * }
190 *
191 * into:
192 *
193 * loop {
194 * ...
195 * if (cond) {
196 * do_work_1();
197 * } else {
198 * do_work_2();
199 * }
200 * break;
201 * }
202 *
203 * It does the same with continue statements, respectively.
204 *
205 */
206 static bool
opt_loop_last_block(nir_block * block,bool is_trivial_continue,bool is_trivial_break)207 opt_loop_last_block(nir_block *block, bool is_trivial_continue, bool is_trivial_break)
208 {
209 /* If this block has no predecessors, let nir_opt_dead_cf() do the cleanup */
210 if (block->predecessors->entries == 0)
211 return false;
212
213 bool progress = false;
214 bool has_break = nir_block_ends_in_break(block);
215 bool has_continue = nir_block_ends_in_continue(block);
216
217 /* Remove any "trivial" break and continue, i.e. those that are at the tail
218 * of a CF-list where we can just delete the instruction and
219 * control-flow will naturally take us to the same target block.
220 */
221 if ((has_break && is_trivial_break) || (has_continue && is_trivial_continue)) {
222 nir_lower_phis_to_regs_block(block->successors[0]);
223 nir_instr_remove_v(nir_block_last_instr(block));
224 return true;
225 }
226
227 if (!nir_block_ends_in_jump(block)) {
228 has_break = is_trivial_break;
229 has_continue = is_trivial_continue;
230 } else if (is_trivial_continue || is_trivial_break) {
231 /* This block ends in a jump that cannot be removed because the implicit
232 * fallthrough leads to a different target block.
233 *
234 * We already optimized this block's jump with the predecessors' when visiting
235 * this block with opt_loop_last_block(block, is_trivial_* = false, false).
236 */
237 return false;
238 }
239
240 /* Nothing to do. */
241 if (!has_continue && !has_break)
242 return false;
243
244 /* Walk backwards and check for previous IF statements whether one of the
245 * branch legs ends with an equal jump instruction as this block.
246 */
247 for (nir_cf_node *prev = nir_cf_node_prev(&block->cf_node); prev != NULL; prev = nir_cf_node_prev(prev)) {
248 /* Skip blocks and nested loops */
249 if (prev->type != nir_cf_node_if)
250 continue;
251
252 nir_if *nif = nir_cf_node_as_if(prev);
253 nir_block *then_block = nir_if_last_then_block(nif);
254 nir_block *else_block = nir_if_last_else_block(nif);
255 if (!nir_block_ends_in_jump(then_block) && !nir_block_ends_in_jump(else_block))
256 continue;
257
258 bool merge_into_then = (has_continue && nir_block_ends_in_continue(else_block)) ||
259 (has_break && nir_block_ends_in_break(else_block));
260 bool merge_into_else = (has_continue && nir_block_ends_in_continue(then_block)) ||
261 (has_break && nir_block_ends_in_break(then_block));
262
263 if (!merge_into_then && !merge_into_else)
264 continue;
265
266 /* If there are single-source phis after the IF, get rid of them first */
267 nir_opt_remove_phis_block(nir_cf_node_cf_tree_next(prev));
268
269 /* We are about to remove one predecessor. */
270 nir_lower_phis_to_regs_block(block->successors[0]);
271
272 nir_cf_list tmp;
273 nir_cf_extract(&tmp, nir_after_cf_node(prev), nir_after_block_before_jump(block));
274
275 if (merge_into_then) {
276 nir_cf_reinsert(&tmp, nir_after_block(then_block));
277 } else {
278 nir_cf_reinsert(&tmp, nir_after_block(else_block));
279 }
280
281 /* Because we split the current block, the pointer is not valid anymore. */
282 block = nir_cf_node_cf_tree_next(prev);
283 progress = true;
284 }
285
286 /* Revisit the predecessor blocks in order to remove implicit jump instructions. */
287 if (is_block_singular(block)) {
288 nir_cf_node *prev = nir_cf_node_prev(&block->cf_node);
289 if (prev && prev->type == nir_cf_node_if) {
290 nir_if *nif = nir_cf_node_as_if(prev);
291 progress |= opt_loop_last_block(nir_if_last_then_block(nif), has_continue, has_break);
292 progress |= opt_loop_last_block(nir_if_last_else_block(nif), has_continue, has_break);
293 }
294 }
295
296 return progress;
297 }
298
299 static bool
opt_loop_cf_list(struct exec_list * cf_list)300 opt_loop_cf_list(struct exec_list *cf_list)
301 {
302 bool progress = false;
303 foreach_list_typed_safe(nir_cf_node, cf_node, node, cf_list) {
304 switch (cf_node->type) {
305 case nir_cf_node_block: {
306 nir_block *block = nir_cf_node_as_block(cf_node);
307 progress |= opt_loop_last_block(block, false, false);
308 break;
309 }
310
311 case nir_cf_node_if: {
312 nir_if *nif = nir_cf_node_as_if(cf_node);
313 progress |= opt_loop_cf_list(&nif->then_list);
314 progress |= opt_loop_cf_list(&nif->else_list);
315 progress |= opt_loop_merge_break_continue(nif);
316 progress |= opt_loop_terminator(nif);
317 break;
318 }
319
320 case nir_cf_node_loop: {
321 nir_loop *loop = nir_cf_node_as_loop(cf_node);
322 assert(!nir_loop_has_continue_construct(loop));
323 progress |= opt_loop_cf_list(&loop->body);
324 progress |= opt_loop_last_block(nir_loop_last_block(loop), true, false);
325 break;
326 }
327
328 case nir_cf_node_function:
329 unreachable("Invalid cf type");
330 }
331 }
332
333 return progress;
334 }
335
336 /**
337 * This pass aims to simplify loop control-flow by reducing the number
338 * of break and continue statements.
339 */
340 bool
nir_opt_loop(nir_shader * shader)341 nir_opt_loop(nir_shader *shader)
342 {
343 bool progress = false;
344
345 nir_foreach_function_impl(impl, shader) {
346 /* First we run the simple pass to get rid of pesky continues */
347 if (opt_loop_cf_list(&impl->body)) {
348 nir_metadata_preserve(impl, nir_metadata_none);
349
350 /* If that made progress, we're no longer really in SSA form. */
351 nir_lower_reg_intrinsics_to_ssa_impl(impl);
352 progress = true;
353 } else {
354 nir_metadata_preserve(impl, nir_metadata_all);
355 }
356 }
357
358 return progress;
359 }
360