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
;
42 static bool lower_returns_in_cf_list(struct exec_list
*cf_list
,
43 struct lower_returns_state
*state
);
46 predicate_following(nir_cf_node
*node
, struct lower_returns_state
*state
)
48 nir_builder
*b
= &state
->builder
;
49 b
->cursor
= nir_after_cf_node_and_phis(node
);
51 if (nir_cursors_equal(b
->cursor
, nir_after_cf_list(state
->cf_list
)))
52 return; /* Nothing to predicate */
54 assert(state
->return_flag
);
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
);
61 /* If we're inside of a loop, then all we need to do is insert a
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
);
68 /* Otherwise, we need to actually move everything into the else case
69 * of the if statement.
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
));
80 lower_returns_in_loop(nir_loop
*loop
, struct lower_returns_state
*state
)
82 nir_loop
*parent
= state
->loop
;
84 bool progress
= lower_returns_in_cf_list(&loop
->body
, state
);
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
93 predicate_following(&loop
->cf_node
, state
);
94 state
->has_predicated_return
= true;
101 lower_returns_in_if(nir_if
*if_stmt
, struct lower_returns_state
*state
)
103 bool progress
, then_progress
, else_progress
;
105 bool has_predicated_return
= state
->has_predicated_return
;
106 state
->has_predicated_return
= false;
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
;
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
122 if (progress
&& !state
->loop
) {
123 if (state
->has_predicated_return
) {
124 predicate_following(&if_stmt
->cf_node
, state
);
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.
130 nir_cf_extract(&list
, nir_after_cf_node(&if_stmt
->cf_node
),
131 nir_after_cf_list(state
->cf_list
));
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
));
139 nir_cf_reinsert(&list
, nir_after_cf_list(&if_stmt
->then_list
));
144 state
->has_predicated_return
= progress
|| has_predicated_return
;
150 lower_returns_in_block(nir_block
*block
, struct lower_returns_state
*state
)
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. */
156 nir_cf_extract(&list
, nir_before_cf_node(&block
->cf_node
),
157 nir_after_cf_list(state
->cf_list
));
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.
165 nir_cf_delete(&list
);
170 nir_instr
*last_instr
= nir_block_last_instr(block
);
171 if (last_instr
== NULL
)
174 if (last_instr
->type
!= nir_instr_type_jump
)
177 nir_jump_instr
*jump
= nir_instr_as_jump(last_instr
);
178 if (jump
->type
!= nir_jump_return
)
181 nir_instr_remove(&jump
->instr
);
183 nir_builder
*b
= &state
->builder
;
185 /* Set the return flag */
186 if (state
->return_flag
== NULL
) {
188 nir_local_variable_create(b
->impl
, glsl_bool_type(), "return");
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);
195 b
->cursor
= nir_after_block(block
);
196 nir_store_var(b
, state
->return_flag
, nir_imm_int(b
, NIR_TRUE
), 1);
199 /* We're in a loop; we need to break out of it. */
200 nir_jump(b
, nir_jump_break
);
202 /* Not in a loop; we'll deal with predicating later*/
203 assert(nir_cf_node_next(&block
->cf_node
) == NULL
);
210 lower_returns_in_cf_list(struct exec_list
*cf_list
,
211 struct lower_returns_state
*state
)
213 bool progress
= false;
215 struct exec_list
*parent_list
= state
->cf_list
;
216 state
->cf_list
= cf_list
;
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.
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
))
231 if (lower_returns_in_if(nir_cf_node_as_if(node
), state
))
235 case nir_cf_node_loop
:
236 if (lower_returns_in_loop(nir_cf_node_as_loop(node
), state
))
241 unreachable("Invalid inner CF node type");
245 state
->cf_list
= parent_list
;
251 nir_lower_returns_impl(nir_function_impl
*impl
)
253 struct lower_returns_state state
;
255 state
.cf_list
= &impl
->body
;
257 state
.return_flag
= NULL
;
258 state
.has_predicated_return
= false;
259 nir_builder_init(&state
.builder
, impl
);
261 bool progress
= lower_returns_in_cf_list(&impl
->body
, &state
);
264 nir_metadata_preserve(impl
, nir_metadata_none
);
265 nir_repair_ssa_impl(impl
);
272 nir_lower_returns(nir_shader
*shader
)
274 bool progress
= false;
276 nir_foreach_function(function
, shader
) {
278 progress
= nir_lower_returns_impl(function
->impl
) || progress
;