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
42 static bool lower_returns_in_cf_list(struct exec_list *cf_list,
43 struct lower_returns_state *state);
44
45 static void
predicate_following(nir_cf_node * node,struct lower_returns_state * state)46 predicate_following(nir_cf_node *node, struct lower_returns_state *state)
47 {
48 nir_builder *b = &state->builder;
49 b->cursor = nir_after_cf_node_and_phis(node);
50
51 if (nir_cursors_equal(b->cursor, nir_after_cf_list(state->cf_list)))
52 return; /* Nothing to predicate */
53
54 assert(state->return_flag);
55
56 nir_if *if_stmt = nir_if_create(b->shader);
57 if_stmt->condition = nir_src_for_ssa(nir_load_var(b, state->return_flag));
58 nir_cf_node_insert(b->cursor, &if_stmt->cf_node);
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_instr *brk =
65 nir_jump_instr_create(state->builder.shader, nir_jump_break);
66 nir_instr_insert(nir_before_cf_list(&if_stmt->then_list), &brk->instr);
67 } else {
68 /* Otherwise, we need to actually move everything into the else case
69 * of the if statement.
70 */
71 nir_cf_list list;
72 nir_cf_extract(&list, nir_after_cf_node(&if_stmt->cf_node),
73 nir_after_cf_list(state->cf_list));
74 assert(!exec_list_is_empty(&list.list));
75 nir_cf_reinsert(&list, nir_before_cf_list(&if_stmt->else_list));
76 }
77 }
78
79 static bool
lower_returns_in_loop(nir_loop * loop,struct lower_returns_state * state)80 lower_returns_in_loop(nir_loop *loop, struct lower_returns_state *state)
81 {
82 nir_loop *parent = state->loop;
83 state->loop = loop;
84 bool progress = lower_returns_in_cf_list(&loop->body, state);
85 state->loop = parent;
86
87 /* If the recursive call made progress, then there were returns inside
88 * of the loop. These would have been lowered to breaks with the return
89 * flag set to true. We need to predicate everything following the loop
90 * on the return flag.
91 */
92 if (progress) {
93 predicate_following(&loop->cf_node, state);
94 state->has_predicated_return = true;
95 }
96
97 return progress;
98 }
99
100 static bool
lower_returns_in_if(nir_if * if_stmt,struct lower_returns_state * state)101 lower_returns_in_if(nir_if *if_stmt, struct lower_returns_state *state)
102 {
103 bool progress, then_progress, else_progress;
104
105 bool has_predicated_return = state->has_predicated_return;
106 state->has_predicated_return = false;
107
108 then_progress = lower_returns_in_cf_list(&if_stmt->then_list, state);
109 else_progress = lower_returns_in_cf_list(&if_stmt->else_list, state);
110 progress = then_progress || else_progress;
111
112 /* If either of the recursive calls made progress, then there were
113 * returns inside of the body of the if. If we're in a loop, then these
114 * were lowered to breaks which automatically skip to the end of the
115 * loop so we don't have to do anything. If we're not in a loop, then
116 * all we know is that the return flag is set appropriately and that the
117 * recursive calls ensured that nothing gets executed *inside* the if
118 * after a return. In order to ensure nothing outside gets executed
119 * after a return, we need to predicate everything following on the
120 * return flag.
121 */
122 if (progress && !state->loop) {
123 if (state->has_predicated_return) {
124 predicate_following(&if_stmt->cf_node, state);
125 } else {
126 /* If there are no nested returns we can just add the instructions to
127 * the end of the branch that doesn't have the return.
128 */
129 nir_cf_list list;
130 nir_cf_extract(&list, nir_after_cf_node(&if_stmt->cf_node),
131 nir_after_cf_list(state->cf_list));
132
133 if (then_progress && else_progress) {
134 /* Both branches return so delete instructions following the if */
135 nir_cf_delete(&list);
136 } else if (then_progress) {
137 nir_cf_reinsert(&list, nir_after_cf_list(&if_stmt->else_list));
138 } else {
139 nir_cf_reinsert(&list, nir_after_cf_list(&if_stmt->then_list));
140 }
141 }
142 }
143
144 state->has_predicated_return = progress || has_predicated_return;
145
146 return progress;
147 }
148
149 static bool
lower_returns_in_block(nir_block * block,struct lower_returns_state * state)150 lower_returns_in_block(nir_block *block, struct lower_returns_state *state)
151 {
152 if (block->predecessors->entries == 0 &&
153 block != nir_start_block(state->builder.impl)) {
154 /* This block is unreachable. Delete it and everything after it. */
155 nir_cf_list list;
156 nir_cf_extract(&list, nir_before_cf_node(&block->cf_node),
157 nir_after_cf_list(state->cf_list));
158
159 if (exec_list_is_empty(&list.list)) {
160 /* There's nothing here, which also means there's nothing in this
161 * block so we have nothing to do.
162 */
163 return false;
164 } else {
165 nir_cf_delete(&list);
166 return true;
167 }
168 }
169
170 nir_instr *last_instr = nir_block_last_instr(block);
171 if (last_instr == NULL)
172 return false;
173
174 if (last_instr->type != nir_instr_type_jump)
175 return false;
176
177 nir_jump_instr *jump = nir_instr_as_jump(last_instr);
178 if (jump->type != nir_jump_return)
179 return false;
180
181 nir_instr_remove(&jump->instr);
182
183 nir_builder *b = &state->builder;
184
185 /* Set the return flag */
186 if (state->return_flag == NULL) {
187 state->return_flag =
188 nir_local_variable_create(b->impl, glsl_bool_type(), "return");
189
190 /* Initialize the variable to 0 */
191 b->cursor = nir_before_cf_list(&b->impl->body);
192 nir_store_var(b, state->return_flag, nir_imm_int(b, NIR_FALSE), 1);
193 }
194
195 b->cursor = nir_after_block(block);
196 nir_store_var(b, state->return_flag, nir_imm_int(b, NIR_TRUE), 1);
197
198 if (state->loop) {
199 /* We're in a loop; we need to break out of it. */
200 nir_jump(b, nir_jump_break);
201 } else {
202 /* Not in a loop; we'll deal with predicating later*/
203 assert(nir_cf_node_next(&block->cf_node) == NULL);
204 }
205
206 return true;
207 }
208
209 static bool
lower_returns_in_cf_list(struct exec_list * cf_list,struct lower_returns_state * state)210 lower_returns_in_cf_list(struct exec_list *cf_list,
211 struct lower_returns_state *state)
212 {
213 bool progress = false;
214
215 struct exec_list *parent_list = state->cf_list;
216 state->cf_list = cf_list;
217
218 /* We iterate over the list backwards because any given lower call may
219 * take everything following the given CF node and predicate it. In
220 * order to avoid recursion/iteration problems, we want everything after
221 * a given node to already be lowered before this happens.
222 */
223 foreach_list_typed_reverse_safe(nir_cf_node, node, node, cf_list) {
224 switch (node->type) {
225 case nir_cf_node_block:
226 if (lower_returns_in_block(nir_cf_node_as_block(node), state))
227 progress = true;
228 break;
229
230 case nir_cf_node_if:
231 if (lower_returns_in_if(nir_cf_node_as_if(node), state))
232 progress = true;
233 break;
234
235 case nir_cf_node_loop:
236 if (lower_returns_in_loop(nir_cf_node_as_loop(node), state))
237 progress = true;
238 break;
239
240 default:
241 unreachable("Invalid inner CF node type");
242 }
243 }
244
245 state->cf_list = parent_list;
246
247 return progress;
248 }
249
250 bool
nir_lower_returns_impl(nir_function_impl * impl)251 nir_lower_returns_impl(nir_function_impl *impl)
252 {
253 struct lower_returns_state state;
254
255 state.cf_list = &impl->body;
256 state.loop = NULL;
257 state.return_flag = NULL;
258 state.has_predicated_return = false;
259 nir_builder_init(&state.builder, impl);
260
261 bool progress = lower_returns_in_cf_list(&impl->body, &state);
262
263 if (progress) {
264 nir_metadata_preserve(impl, nir_metadata_none);
265 nir_repair_ssa_impl(impl);
266 }
267
268 return progress;
269 }
270
271 bool
nir_lower_returns(nir_shader * shader)272 nir_lower_returns(nir_shader *shader)
273 {
274 bool progress = false;
275
276 nir_foreach_function(function, shader) {
277 if (function->impl)
278 progress = nir_lower_returns_impl(function->impl) || progress;
279 }
280
281 return progress;
282 }
283