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 nir_cf_list list;
133 nir_cf_extract(&list, nir_after_cf_node(&if_stmt->cf_node),
134 nir_after_cf_list(state->cf_list));
135
136 if (then_progress && else_progress) {
137 /* Both branches return so delete instructions following the if */
138 nir_cf_delete(&list);
139 } else if (then_progress) {
140 nir_cf_reinsert(&list, nir_after_cf_list(&if_stmt->else_list));
141 } else {
142 nir_cf_reinsert(&list, nir_after_cf_list(&if_stmt->then_list));
143 }
144 }
145 }
146
147 state->has_predicated_return = progress || has_predicated_return;
148
149 return progress;
150 }
151
152 static bool
lower_returns_in_block(nir_block * block,struct lower_returns_state * state)153 lower_returns_in_block(nir_block *block, struct lower_returns_state *state)
154 {
155 if (block->predecessors->entries == 0 &&
156 block != nir_start_block(state->builder.impl)) {
157 /* This block is unreachable. Delete it and everything after it. */
158 nir_cf_list list;
159 nir_cf_extract(&list, nir_before_cf_node(&block->cf_node),
160 nir_after_cf_list(state->cf_list));
161
162 if (exec_list_is_empty(&list.list)) {
163 /* There's nothing here, which also means there's nothing in this
164 * block so we have nothing to do.
165 */
166 return false;
167 } else {
168 state->removed_unreachable_code = true;
169 nir_cf_delete(&list);
170 return false;
171 }
172 }
173
174 nir_instr *last_instr = nir_block_last_instr(block);
175 if (last_instr == NULL)
176 return false;
177
178 if (last_instr->type != nir_instr_type_jump)
179 return false;
180
181 nir_jump_instr *jump = nir_instr_as_jump(last_instr);
182 if (jump->type != nir_jump_return)
183 return false;
184
185 nir_instr_remove(&jump->instr);
186
187 /* If this is a return in the last block of the function there is nothing
188 * more to do once its removed.
189 */
190 if (block == nir_impl_last_block(state->builder.impl))
191 return true;
192
193 nir_builder *b = &state->builder;
194
195 /* Set the return flag */
196 if (state->return_flag == NULL) {
197 state->return_flag =
198 nir_local_variable_create(b->impl, glsl_bool_type(), "return");
199
200 /* Initialize the variable to 0 */
201 b->cursor = nir_before_cf_list(&b->impl->body);
202 nir_store_var(b, state->return_flag, nir_imm_false(b), 1);
203 }
204
205 b->cursor = nir_after_block(block);
206 nir_store_var(b, state->return_flag, nir_imm_true(b), 1);
207
208 if (state->loop) {
209 /* We're in a loop; we need to break out of it. */
210 nir_jump(b, nir_jump_break);
211
212 nir_insert_phi_undef(block->successors[0], block);
213 } else {
214 /* Not in a loop; we'll deal with predicating later*/
215 assert(nir_cf_node_next(&block->cf_node) == NULL);
216 }
217
218 return true;
219 }
220
221 static bool
lower_returns_in_cf_list(struct exec_list * cf_list,struct lower_returns_state * state)222 lower_returns_in_cf_list(struct exec_list *cf_list,
223 struct lower_returns_state *state)
224 {
225 bool progress = false;
226
227 struct exec_list *parent_list = state->cf_list;
228 state->cf_list = cf_list;
229
230 /* We iterate over the list backwards because any given lower call may
231 * take everything following the given CF node and predicate it. In
232 * order to avoid recursion/iteration problems, we want everything after
233 * a given node to already be lowered before this happens.
234 */
235 foreach_list_typed_reverse_safe(nir_cf_node, node, node, cf_list) {
236 switch (node->type) {
237 case nir_cf_node_block:
238 if (lower_returns_in_block(nir_cf_node_as_block(node), state))
239 progress = true;
240 break;
241
242 case nir_cf_node_if:
243 if (lower_returns_in_if(nir_cf_node_as_if(node), state))
244 progress = true;
245 break;
246
247 case nir_cf_node_loop:
248 if (lower_returns_in_loop(nir_cf_node_as_loop(node), state))
249 progress = true;
250 break;
251
252 default:
253 unreachable("Invalid inner CF node type");
254 }
255 }
256
257 state->cf_list = parent_list;
258
259 return progress;
260 }
261
262 bool
nir_lower_returns_impl(nir_function_impl * impl)263 nir_lower_returns_impl(nir_function_impl *impl)
264 {
265 struct lower_returns_state state;
266
267 state.cf_list = &impl->body;
268 state.loop = NULL;
269 state.return_flag = NULL;
270 state.has_predicated_return = false;
271 state.removed_unreachable_code = false;
272 nir_builder_init(&state.builder, impl);
273
274 bool progress = lower_returns_in_cf_list(&impl->body, &state);
275 progress = progress || state.removed_unreachable_code;
276
277 if (progress) {
278 nir_metadata_preserve(impl, nir_metadata_none);
279 nir_repair_ssa_impl(impl);
280 } else {
281 nir_metadata_preserve(impl, nir_metadata_all);
282 }
283
284 return progress;
285 }
286
287 bool
nir_lower_returns(nir_shader * shader)288 nir_lower_returns(nir_shader *shader)
289 {
290 bool progress = false;
291
292 nir_foreach_function(function, shader) {
293 if (function->impl)
294 progress = nir_lower_returns_impl(function->impl) || progress;
295 }
296
297 return progress;
298 }
299