2 * Copyright © 2015 Intel Corporation
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:
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
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
25 #include "nir_builder.h"
26 #include "nir_control_flow.h"
28 struct lower_returns_state
{
30 struct exec_list
*cf_list
;
32 nir_variable
*return_flag
;
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.
39 bool has_predicated_return
;
41 bool removed_unreachable_code
;
44 static bool lower_returns_in_cf_list(struct exec_list
*cf_list
,
45 struct lower_returns_state
*state
);
48 predicate_following(nir_cf_node
*node
, struct lower_returns_state
*state
)
50 nir_builder
*b
= &state
->builder
;
51 b
->cursor
= nir_after_cf_node_and_phis(node
);
53 if (!state
->loop
&& nir_cursors_equal(b
->cursor
, nir_after_cf_list(state
->cf_list
)))
54 return; /* Nothing to predicate */
56 assert(state
->return_flag
);
58 nir_if
*if_stmt
= nir_if_create(b
->shader
);
59 if_stmt
->condition
= nir_src_for_ssa(nir_load_var(b
, state
->return_flag
));
60 nir_cf_node_insert(b
->cursor
, &if_stmt
->cf_node
);
63 /* If we're inside of a loop, then all we need to do is insert a
67 nir_jump_instr_create(state
->builder
.shader
, nir_jump_break
);
68 nir_instr_insert(nir_before_cf_list(&if_stmt
->then_list
), &brk
->instr
);
70 /* Otherwise, we need to actually move everything into the else case
71 * of the if statement.
74 nir_cf_extract(&list
, nir_after_cf_node(&if_stmt
->cf_node
),
75 nir_after_cf_list(state
->cf_list
));
76 assert(!exec_list_is_empty(&list
.list
));
77 nir_cf_reinsert(&list
, nir_before_cf_list(&if_stmt
->else_list
));
82 lower_returns_in_loop(nir_loop
*loop
, struct lower_returns_state
*state
)
84 nir_loop
*parent
= state
->loop
;
86 bool progress
= lower_returns_in_cf_list(&loop
->body
, state
);
89 /* If the recursive call made progress, then there were returns inside
90 * of the loop. These would have been lowered to breaks with the return
91 * flag set to true. We need to predicate everything following the loop
95 predicate_following(&loop
->cf_node
, state
);
96 state
->has_predicated_return
= true;
103 lower_returns_in_if(nir_if
*if_stmt
, struct lower_returns_state
*state
)
105 bool progress
, then_progress
, else_progress
;
107 bool has_predicated_return
= state
->has_predicated_return
;
108 state
->has_predicated_return
= false;
110 then_progress
= lower_returns_in_cf_list(&if_stmt
->then_list
, state
);
111 else_progress
= lower_returns_in_cf_list(&if_stmt
->else_list
, state
);
112 progress
= then_progress
|| else_progress
;
114 /* If either of the recursive calls made progress, then there were
115 * returns inside of the body of the if. If we're in a loop, then these
116 * were lowered to breaks which automatically skip to the end of the
117 * loop so we don't have to do anything. If we're not in a loop, then
118 * all we know is that the return flag is set appropriately and that the
119 * recursive calls ensured that nothing gets executed *inside* the if
120 * after a return. In order to ensure nothing outside gets executed
121 * after a return, we need to predicate everything following on the
124 if (progress
&& !state
->loop
) {
125 if (state
->has_predicated_return
) {
126 predicate_following(&if_stmt
->cf_node
, state
);
128 /* If there are no nested returns we can just add the instructions to
129 * the end of the branch that doesn't have the return.
132 nir_cf_extract(&list
, nir_after_cf_node(&if_stmt
->cf_node
),
133 nir_after_cf_list(state
->cf_list
));
135 if (then_progress
&& else_progress
) {
136 /* Both branches return so delete instructions following the if */
137 nir_cf_delete(&list
);
138 } else if (then_progress
) {
139 nir_cf_reinsert(&list
, nir_after_cf_list(&if_stmt
->else_list
));
141 nir_cf_reinsert(&list
, nir_after_cf_list(&if_stmt
->then_list
));
146 state
->has_predicated_return
= progress
|| has_predicated_return
;
152 lower_returns_in_block(nir_block
*block
, struct lower_returns_state
*state
)
154 if (block
->predecessors
->entries
== 0 &&
155 block
!= nir_start_block(state
->builder
.impl
)) {
156 /* This block is unreachable. Delete it and everything after it. */
158 nir_cf_extract(&list
, nir_before_cf_node(&block
->cf_node
),
159 nir_after_cf_list(state
->cf_list
));
161 if (exec_list_is_empty(&list
.list
)) {
162 /* There's nothing here, which also means there's nothing in this
163 * block so we have nothing to do.
167 state
->removed_unreachable_code
= true;
168 nir_cf_delete(&list
);
173 nir_instr
*last_instr
= nir_block_last_instr(block
);
174 if (last_instr
== NULL
)
177 if (last_instr
->type
!= nir_instr_type_jump
)
180 nir_jump_instr
*jump
= nir_instr_as_jump(last_instr
);
181 if (jump
->type
!= nir_jump_return
)
184 nir_instr_remove(&jump
->instr
);
186 /* If this is a return in the last block of the function there is nothing
187 * more to do once its removed.
189 if (block
== nir_impl_last_block(state
->builder
.impl
))
192 nir_builder
*b
= &state
->builder
;
194 /* Set the return flag */
195 if (state
->return_flag
== NULL
) {
197 nir_local_variable_create(b
->impl
, glsl_bool_type(), "return");
199 /* Initialize the variable to 0 */
200 b
->cursor
= nir_before_cf_list(&b
->impl
->body
);
201 nir_store_var(b
, state
->return_flag
, nir_imm_false(b
), 1);
204 b
->cursor
= nir_after_block(block
);
205 nir_store_var(b
, state
->return_flag
, nir_imm_true(b
), 1);
208 /* We're in a loop; we need to break out of it. */
209 nir_jump(b
, nir_jump_break
);
211 /* Not in a loop; we'll deal with predicating later*/
212 assert(nir_cf_node_next(&block
->cf_node
) == NULL
);
219 lower_returns_in_cf_list(struct exec_list
*cf_list
,
220 struct lower_returns_state
*state
)
222 bool progress
= false;
224 struct exec_list
*parent_list
= state
->cf_list
;
225 state
->cf_list
= cf_list
;
227 /* We iterate over the list backwards because any given lower call may
228 * take everything following the given CF node and predicate it. In
229 * order to avoid recursion/iteration problems, we want everything after
230 * a given node to already be lowered before this happens.
232 foreach_list_typed_reverse_safe(nir_cf_node
, node
, node
, cf_list
) {
233 switch (node
->type
) {
234 case nir_cf_node_block
:
235 if (lower_returns_in_block(nir_cf_node_as_block(node
), state
))
240 if (lower_returns_in_if(nir_cf_node_as_if(node
), state
))
244 case nir_cf_node_loop
:
245 if (lower_returns_in_loop(nir_cf_node_as_loop(node
), state
))
250 unreachable("Invalid inner CF node type");
254 state
->cf_list
= parent_list
;
260 nir_lower_returns_impl(nir_function_impl
*impl
)
262 struct lower_returns_state state
;
264 state
.cf_list
= &impl
->body
;
266 state
.return_flag
= NULL
;
267 state
.has_predicated_return
= false;
268 state
.removed_unreachable_code
= false;
269 nir_builder_init(&state
.builder
, impl
);
271 bool progress
= lower_returns_in_cf_list(&impl
->body
, &state
);
272 progress
= progress
|| state
.removed_unreachable_code
;
275 nir_metadata_preserve(impl
, nir_metadata_none
);
276 nir_repair_ssa_impl(impl
);
278 nir_metadata_preserve(impl
, nir_metadata_all
);
285 nir_lower_returns(nir_shader
*shader
)
287 bool progress
= false;
289 nir_foreach_function(function
, shader
) {
291 progress
= nir_lower_returns_impl(function
->impl
) || progress
;