1 /*
2 * Copyright © 2014 Connor Abbott
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 * Authors:
24 * Connor Abbott (cwabbott0@gmail.com)
25 *
26 */
27
28 #include "nir.h"
29 #include "nir_control_flow.h"
30
31 /*
32 * This file implements an optimization that deletes statically
33 * unreachable/dead code. In NIR, one way this can happen is when an if
34 * statement has a constant condition:
35 *
36 * if (true) {
37 * ...
38 * }
39 *
40 * We delete the if statement and paste the contents of the always-executed
41 * branch into the surrounding control flow, possibly removing more code if
42 * the branch had a jump at the end.
43 *
44 * Another way is that control flow can end in a jump so that code after it
45 * never gets executed. In particular, this can happen after optimizing
46 * something like:
47 *
48 * if (true) {
49 * ...
50 * break;
51 * }
52 * ...
53 *
54 * We also consider the case where both branches of an if end in a jump, e.g.:
55 *
56 * if (...) {
57 * break;
58 * } else {
59 * continue;
60 * }
61 * ...
62 *
63 * Finally, we also handle removing useless loops, i.e. loops with no side
64 * effects and without any definitions that are used elsewhere. This case is a
65 * little different from the first two in that the code is actually run (it
66 * just never does anything), but there are similar issues with needing to
67 * be careful with restarting after deleting the cf_node (see dead_cf_list())
68 * so this is a convenient place to remove them.
69 */
70
71 static void
remove_after_cf_node(nir_cf_node * node)72 remove_after_cf_node(nir_cf_node *node)
73 {
74 nir_cf_node *end = node;
75 while (!nir_cf_node_is_last(end))
76 end = nir_cf_node_next(end);
77
78 nir_cf_list list;
79 nir_cf_extract(&list, nir_after_cf_node(node), nir_after_cf_node(end));
80 nir_cf_delete(&list);
81 }
82
83 static void
opt_constant_if(nir_if * if_stmt,bool condition)84 opt_constant_if(nir_if *if_stmt, bool condition)
85 {
86 /* First, we need to remove any phi nodes after the if by rewriting uses to
87 * point to the correct source.
88 */
89 nir_block *after = nir_cf_node_as_block(nir_cf_node_next(&if_stmt->cf_node));
90 nir_block *last_block = condition ? nir_if_last_then_block(if_stmt)
91 : nir_if_last_else_block(if_stmt);
92
93 nir_foreach_instr_safe(instr, after) {
94 if (instr->type != nir_instr_type_phi)
95 break;
96
97 nir_phi_instr *phi = nir_instr_as_phi(instr);
98 nir_ssa_def *def = NULL;
99 nir_foreach_phi_src(phi_src, phi) {
100 if (phi_src->pred != last_block)
101 continue;
102
103 assert(phi_src->src.is_ssa);
104 def = phi_src->src.ssa;
105 }
106
107 assert(def);
108 assert(phi->dest.is_ssa);
109 nir_ssa_def_rewrite_uses(&phi->dest.ssa, nir_src_for_ssa(def));
110 nir_instr_remove(instr);
111 }
112
113 /* The control flow list we're about to paste in may include a jump at the
114 * end, and in that case we have to delete the rest of the control flow
115 * list after the if since it's unreachable and the validator will balk if
116 * we don't.
117 */
118
119 if (!exec_list_is_empty(&last_block->instr_list)) {
120 nir_instr *last_instr = nir_block_last_instr(last_block);
121 if (last_instr->type == nir_instr_type_jump)
122 remove_after_cf_node(&if_stmt->cf_node);
123 }
124
125 /* Finally, actually paste in the then or else branch and delete the if. */
126 struct exec_list *cf_list = condition ? &if_stmt->then_list
127 : &if_stmt->else_list;
128
129 nir_cf_list list;
130 nir_cf_list_extract(&list, cf_list);
131 nir_cf_reinsert(&list, nir_after_cf_node(&if_stmt->cf_node));
132 nir_cf_node_remove(&if_stmt->cf_node);
133 }
134
135 static bool
cf_node_has_side_effects(nir_cf_node * node)136 cf_node_has_side_effects(nir_cf_node *node)
137 {
138 nir_foreach_block_in_cf_node(block, node) {
139 nir_foreach_instr(instr, block) {
140 if (instr->type == nir_instr_type_call)
141 return true;
142
143 /* Return instructions can cause us to skip over other side-effecting
144 * instructions after the loop, so consider them to have side effects
145 * here.
146 */
147
148 if (instr->type == nir_instr_type_jump &&
149 nir_instr_as_jump(instr)->type == nir_jump_return)
150 return true;
151
152 if (instr->type != nir_instr_type_intrinsic)
153 continue;
154
155 nir_intrinsic_instr *intrin = nir_instr_as_intrinsic(instr);
156 if (!(nir_intrinsic_infos[intrin->intrinsic].flags &
157 NIR_INTRINSIC_CAN_ELIMINATE))
158 return true;
159 }
160 }
161
162 return false;
163 }
164
165 static bool
def_not_live_out(nir_ssa_def * def,void * state)166 def_not_live_out(nir_ssa_def *def, void *state)
167 {
168 nir_block *after = state;
169
170 return !BITSET_TEST(after->live_in, def->live_index);
171 }
172
173 /*
174 * Test if a loop is dead. A loop is dead if:
175 *
176 * 1) It has no side effects (i.e. intrinsics which could possibly affect the
177 * state of the program aside from producing an SSA value, indicated by a lack
178 * of NIR_INTRINSIC_CAN_ELIMINATE).
179 *
180 * 2) It has no phi nodes after it, since those indicate values inside the
181 * loop being used after the loop.
182 *
183 * 3) If there are no phi nodes after the loop, then the only way a value
184 * defined inside the loop can be used outside the loop is if its definition
185 * dominates the block after the loop. If none of the definitions that
186 * dominate the loop exit are used outside the loop, then the loop is dead
187 * and it can be deleted.
188 */
189
190 static bool
loop_is_dead(nir_loop * loop)191 loop_is_dead(nir_loop *loop)
192 {
193 nir_block *before = nir_cf_node_as_block(nir_cf_node_prev(&loop->cf_node));
194 nir_block *after = nir_cf_node_as_block(nir_cf_node_next(&loop->cf_node));
195
196 if (!exec_list_is_empty(&after->instr_list) &&
197 nir_block_first_instr(after)->type == nir_instr_type_phi)
198 return false;
199
200 if (cf_node_has_side_effects(&loop->cf_node))
201 return false;
202
203 nir_function_impl *impl = nir_cf_node_get_function(&loop->cf_node);
204 nir_metadata_require(impl, nir_metadata_live_ssa_defs |
205 nir_metadata_dominance);
206
207 for (nir_block *cur = after->imm_dom; cur && cur != before;
208 cur = cur->imm_dom) {
209 nir_foreach_instr(instr, cur) {
210 if (!nir_foreach_ssa_def(instr, def_not_live_out, after))
211 return false;
212 }
213 }
214
215 return true;
216 }
217
218 static bool
dead_cf_block(nir_block * block)219 dead_cf_block(nir_block *block)
220 {
221 nir_if *following_if = nir_block_get_following_if(block);
222 if (following_if) {
223 nir_const_value *const_value =
224 nir_src_as_const_value(following_if->condition);
225
226 if (!const_value)
227 return false;
228
229 opt_constant_if(following_if, const_value->u32[0] != 0);
230 return true;
231 }
232
233 nir_loop *following_loop = nir_block_get_following_loop(block);
234 if (!following_loop)
235 return false;
236
237 if (!loop_is_dead(following_loop))
238 return false;
239
240 nir_cf_node_remove(&following_loop->cf_node);
241 return true;
242 }
243
244 static bool
ends_in_jump(nir_block * block)245 ends_in_jump(nir_block *block)
246 {
247 if (exec_list_is_empty(&block->instr_list))
248 return false;
249
250 nir_instr *instr = nir_block_last_instr(block);
251 return instr->type == nir_instr_type_jump;
252 }
253
254 static bool
dead_cf_list(struct exec_list * list,bool * list_ends_in_jump)255 dead_cf_list(struct exec_list *list, bool *list_ends_in_jump)
256 {
257 bool progress = false;
258 *list_ends_in_jump = false;
259
260 nir_cf_node *prev = NULL;
261
262 foreach_list_typed(nir_cf_node, cur, node, list) {
263 switch (cur->type) {
264 case nir_cf_node_block: {
265 nir_block *block = nir_cf_node_as_block(cur);
266 if (dead_cf_block(block)) {
267 /* We just deleted the if or loop after this block, so we may have
268 * deleted the block before or after it -- which one is an
269 * implementation detail. Therefore, to recover the place we were
270 * at, we have to use the previous cf_node.
271 */
272
273 if (prev) {
274 cur = nir_cf_node_next(prev);
275 } else {
276 cur = exec_node_data(nir_cf_node, exec_list_get_head(list),
277 node);
278 }
279
280 block = nir_cf_node_as_block(cur);
281
282 progress = true;
283 }
284
285 if (ends_in_jump(block)) {
286 *list_ends_in_jump = true;
287
288 if (!exec_node_is_tail_sentinel(cur->node.next)) {
289 remove_after_cf_node(cur);
290 return true;
291 }
292 }
293
294 break;
295 }
296
297 case nir_cf_node_if: {
298 nir_if *if_stmt = nir_cf_node_as_if(cur);
299 bool then_ends_in_jump, else_ends_in_jump;
300 progress |= dead_cf_list(&if_stmt->then_list, &then_ends_in_jump);
301 progress |= dead_cf_list(&if_stmt->else_list, &else_ends_in_jump);
302
303 if (then_ends_in_jump && else_ends_in_jump) {
304 *list_ends_in_jump = true;
305 nir_block *next = nir_cf_node_as_block(nir_cf_node_next(cur));
306 if (!exec_list_is_empty(&next->instr_list) ||
307 !exec_node_is_tail_sentinel(next->cf_node.node.next)) {
308 remove_after_cf_node(cur);
309 return true;
310 }
311 }
312
313 break;
314 }
315
316 case nir_cf_node_loop: {
317 nir_loop *loop = nir_cf_node_as_loop(cur);
318 bool dummy;
319 progress |= dead_cf_list(&loop->body, &dummy);
320
321 break;
322 }
323
324 default:
325 unreachable("unknown cf node type");
326 }
327
328 prev = cur;
329 }
330
331 return progress;
332 }
333
334 static bool
opt_dead_cf_impl(nir_function_impl * impl)335 opt_dead_cf_impl(nir_function_impl *impl)
336 {
337 bool dummy;
338 bool progress = dead_cf_list(&impl->body, &dummy);
339
340 if (progress)
341 nir_metadata_preserve(impl, nir_metadata_none);
342
343 return progress;
344 }
345
346 bool
nir_opt_dead_cf(nir_shader * shader)347 nir_opt_dead_cf(nir_shader *shader)
348 {
349 bool progress = false;
350
351 nir_foreach_function(function, shader)
352 if (function->impl)
353 progress |= opt_dead_cf_impl(function->impl);
354
355 return progress;
356 }
357