1 /*
2 * Copyright © 2015 Intel Corporation
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 #include "nir.h"
25 #include "nir_builder.h"
26 #include "nir_control_flow.h"
27
28 struct lower_returns_state {
29 nir_builder builder;
30 struct exec_list *cf_list;
31 nir_loop *loop;
32 nir_variable *return_flag;
33
34 /* This indicates that we have a return which is predicated on some form of
35 * control-flow. Since whether or not the return happens can only be
36 * determined dynamically at run-time, everything that occurs afterwards
37 * needs to be predicated on the return flag variable.
38 */
39 bool has_predicated_return;
40
41 bool removed_unreachable_code;
42 };
43
44 static bool lower_returns_in_cf_list(struct exec_list *cf_list,
45 struct lower_returns_state *state);
46
47 static void
predicate_following(nir_cf_node * node,struct lower_returns_state * state)48 predicate_following(nir_cf_node *node, struct lower_returns_state *state)
49 {
50 nir_builder *b = &state->builder;
51 b->cursor = nir_after_cf_node_and_phis(node);
52
53 if (!state->loop && nir_cursors_equal(b->cursor, nir_after_cf_list(state->cf_list)))
54 return; /* Nothing to predicate */
55
56 assert(state->return_flag);
57
58 nir_if *if_stmt = nir_push_if(b, nir_load_var(b, state->return_flag));
59
60 if (state->loop) {
61 /* If we're inside of a loop, then all we need to do is insert a
62 * conditional break.
63 */
64 nir_jump(b, nir_jump_break);
65
66 nir_block *block = nir_cursor_current_block(b->cursor);
67 nir_insert_phi_undef(block->successors[0], block);
68 } else {
69 /* Otherwise, we need to actually move everything into the else case
70 * of the if statement.
71 */
72 nir_cf_list list;
73 nir_cf_extract(&list, nir_after_cf_node(&if_stmt->cf_node),
74 nir_after_cf_list(state->cf_list));
75 assert(!exec_list_is_empty(&list.list));
76 nir_cf_reinsert(&list, nir_before_cf_list(&if_stmt->else_list));
77 }
78
79 nir_pop_if(b, NULL);
80 }
81
82 static bool
lower_returns_in_loop(nir_loop * loop,struct lower_returns_state * state)83 lower_returns_in_loop(nir_loop *loop, struct lower_returns_state *state)
84 {
85 nir_loop *parent = state->loop;
86 state->loop = loop;
87 bool progress = lower_returns_in_cf_list(&loop->body, state);
88 state->loop = parent;
89
90 /* If the recursive call made progress, then there were returns inside
91 * of the loop. These would have been lowered to breaks with the return
92 * flag set to true. We need to predicate everything following the loop
93 * on the return flag.
94 */
95 if (progress) {
96 predicate_following(&loop->cf_node, state);
97 state->has_predicated_return = true;
98 }
99
100 return progress;
101 }
102
103 static bool
lower_returns_in_if(nir_if * if_stmt,struct lower_returns_state * state)104 lower_returns_in_if(nir_if *if_stmt, struct lower_returns_state *state)
105 {
106 bool progress, then_progress, else_progress;
107
108 bool has_predicated_return = state->has_predicated_return;
109 state->has_predicated_return = false;
110
111 then_progress = lower_returns_in_cf_list(&if_stmt->then_list, state);
112 else_progress = lower_returns_in_cf_list(&if_stmt->else_list, state);
113 progress = then_progress || else_progress;
114
115 /* If either of the recursive calls made progress, then there were
116 * returns inside of the body of the if. If we're in a loop, then these
117 * were lowered to breaks which automatically skip to the end of the
118 * loop so we don't have to do anything. If we're not in a loop, then
119 * all we know is that the return flag is set appropriately and that the
120 * recursive calls ensured that nothing gets executed *inside* the if
121 * after a return. In order to ensure nothing outside gets executed
122 * after a return, we need to predicate everything following on the
123 * return flag.
124 */
125 if (progress && !state->loop) {
126 if (state->has_predicated_return) {
127 predicate_following(&if_stmt->cf_node, state);
128 } else {
129 /* If there are no nested returns we can just add the instructions to
130 * the end of the branch that doesn't have the return.
131 */
132
133 /* nir_cf_extract will not extract phis at the start of the block. In
134 * this case we know that any phis will have to have a single
135 * predecessor, so we can just replace the phi with its single source.
136 */
137 nir_block *succ_block = nir_after_cf_node(&if_stmt->cf_node).block;
138 nir_opt_remove_phis_block(succ_block);
139 assert(nir_block_first_instr(succ_block) == NULL ||
140 nir_block_first_instr(succ_block)->type != nir_instr_type_phi);
141
142 nir_cf_list list;
143 nir_cf_extract(&list, nir_after_cf_node(&if_stmt->cf_node),
144 nir_after_cf_list(state->cf_list));
145
146 if (then_progress && else_progress) {
147 /* Both branches return so delete instructions following the if */
148 nir_cf_delete(&list);
149 } else if (then_progress) {
150 nir_cf_reinsert(&list, nir_after_cf_list(&if_stmt->else_list));
151 } else {
152 nir_cf_reinsert(&list, nir_after_cf_list(&if_stmt->then_list));
153 }
154 }
155 }
156
157 state->has_predicated_return = progress || has_predicated_return;
158
159 return progress;
160 }
161
162 static bool
lower_returns_in_block(nir_block * block,struct lower_returns_state * state)163 lower_returns_in_block(nir_block *block, struct lower_returns_state *state)
164 {
165 if (block->predecessors->entries == 0 &&
166 block != nir_start_block(state->builder.impl)) {
167 /* This block is unreachable. Delete it and everything after it. */
168 nir_cf_list list;
169 nir_cf_extract(&list, nir_before_cf_node(&block->cf_node),
170 nir_after_cf_list(state->cf_list));
171
172 if (exec_list_is_empty(&list.list)) {
173 /* There's nothing here, which also means there's nothing in this
174 * block so we have nothing to do.
175 */
176 return false;
177 } else {
178 state->removed_unreachable_code = true;
179 nir_cf_delete(&list);
180 return false;
181 }
182 }
183
184 nir_instr *last_instr = nir_block_last_instr(block);
185 if (last_instr == NULL)
186 return false;
187
188 if (last_instr->type != nir_instr_type_jump)
189 return false;
190
191 nir_jump_instr *jump = nir_instr_as_jump(last_instr);
192 if (jump->type != nir_jump_return)
193 return false;
194
195 nir_instr_remove(&jump->instr);
196
197 /* If this is a return in the last block of the function there is nothing
198 * more to do once its removed.
199 */
200 if (block == nir_impl_last_block(state->builder.impl))
201 return true;
202
203 nir_builder *b = &state->builder;
204
205 /* Set the return flag */
206 if (state->return_flag == NULL) {
207 state->return_flag =
208 nir_local_variable_create(b->impl, glsl_bool_type(), "return");
209
210 /* Initialize the variable to 0 */
211 b->cursor = nir_before_cf_list(&b->impl->body);
212 nir_store_var(b, state->return_flag, nir_imm_false(b), 1);
213 }
214
215 b->cursor = nir_after_block(block);
216 nir_store_var(b, state->return_flag, nir_imm_true(b), 1);
217
218 if (state->loop) {
219 /* We're in a loop; we need to break out of it. */
220 nir_jump(b, nir_jump_break);
221
222 nir_insert_phi_undef(block->successors[0], block);
223 } else {
224 /* Not in a loop; we'll deal with predicating later*/
225 assert(nir_cf_node_next(&block->cf_node) == NULL);
226 }
227
228 return true;
229 }
230
231 static bool
lower_returns_in_cf_list(struct exec_list * cf_list,struct lower_returns_state * state)232 lower_returns_in_cf_list(struct exec_list *cf_list,
233 struct lower_returns_state *state)
234 {
235 bool progress = false;
236
237 struct exec_list *parent_list = state->cf_list;
238 state->cf_list = cf_list;
239
240 /* We iterate over the list backwards because any given lower call may
241 * take everything following the given CF node and predicate it. In
242 * order to avoid recursion/iteration problems, we want everything after
243 * a given node to already be lowered before this happens.
244 */
245 foreach_list_typed_reverse_safe(nir_cf_node, node, node, cf_list) {
246 switch (node->type) {
247 case nir_cf_node_block:
248 if (lower_returns_in_block(nir_cf_node_as_block(node), state))
249 progress = true;
250 break;
251
252 case nir_cf_node_if:
253 if (lower_returns_in_if(nir_cf_node_as_if(node), state))
254 progress = true;
255 break;
256
257 case nir_cf_node_loop:
258 if (lower_returns_in_loop(nir_cf_node_as_loop(node), state))
259 progress = true;
260 break;
261
262 default:
263 unreachable("Invalid inner CF node type");
264 }
265 }
266
267 state->cf_list = parent_list;
268
269 return progress;
270 }
271
272 bool
nir_lower_returns_impl(nir_function_impl * impl)273 nir_lower_returns_impl(nir_function_impl *impl)
274 {
275 struct lower_returns_state state;
276
277 state.cf_list = &impl->body;
278 state.loop = NULL;
279 state.return_flag = NULL;
280 state.has_predicated_return = false;
281 state.removed_unreachable_code = false;
282 nir_builder_init(&state.builder, impl);
283
284 bool progress = lower_returns_in_cf_list(&impl->body, &state);
285 progress = progress || state.removed_unreachable_code;
286
287 if (progress) {
288 nir_metadata_preserve(impl, nir_metadata_none);
289 nir_repair_ssa_impl(impl);
290 } else {
291 nir_metadata_preserve(impl, nir_metadata_all);
292 }
293
294 return progress;
295 }
296
297 bool
nir_lower_returns(nir_shader * shader)298 nir_lower_returns(nir_shader *shader)
299 {
300 bool progress = false;
301
302 nir_foreach_function(function, shader) {
303 if (function->impl)
304 progress = nir_lower_returns_impl(function->impl) || progress;
305 }
306
307 return progress;
308 }
309