1 /*
2 * Copyright © 2010 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
21 * DEALINGS IN THE SOFTWARE.
22 */
23
24 /**
25 * \file ir_if_return.cpp
26 *
27 * This pass tries to normalize functions to always return from one
28 * place by moving around blocks of code in if statements.
29 *
30 * This helps on hardware with no branching support, and may even be a
31 * useful transform on hardware supporting control flow by turning
32 * masked returns into normal returns.
33 */
34
35 #include <string.h>
36 #include "glsl_types.h"
37 #include "ir.h"
38
39 class ir_if_return_visitor : public ir_hierarchical_visitor {
40 public:
ir_if_return_visitor()41 ir_if_return_visitor()
42 {
43 this->progress = false;
44 }
45
46 ir_visitor_status visit_enter(ir_function_signature *);
47 ir_visitor_status visit_leave(ir_if *);
48
49 ir_visitor_status move_outer_block_inside(ir_instruction *ir,
50 exec_list *inner_block);
51 void move_returns_after_block(ir_instruction *ir,
52 ir_return *then_return,
53 ir_return *else_return);
54 bool progress;
55 };
56
57 bool
do_if_return(exec_list * instructions)58 do_if_return(exec_list *instructions)
59 {
60 ir_if_return_visitor v;
61
62 do {
63 v.progress = false;
64 visit_list_elements(&v, instructions);
65 } while (v.progress);
66
67 return v.progress;
68 }
69
70 /**
71 * Removes any instructions after a (unconditional) return, since they will
72 * never be executed.
73 */
74 static void
truncate_after_instruction(ir_instruction * ir)75 truncate_after_instruction(ir_instruction *ir)
76 {
77 if (!ir)
78 return;
79
80 while (!ir->get_next()->is_tail_sentinel())
81 ((ir_instruction *)ir->get_next())->remove();
82 }
83
84 /**
85 * Returns an ir_instruction of the first ir_return in the exec_list, or NULL.
86 */
87 static ir_return *
find_return_in_block(exec_list * instructions)88 find_return_in_block(exec_list *instructions)
89 {
90 foreach_iter(exec_list_iterator, iter, *instructions) {
91 ir_instruction *ir = (ir_instruction *)iter.get();
92 if (ir->ir_type == ir_type_return)
93 return (ir_return *)ir;
94 }
95
96 return NULL;
97 }
98
99 void
move_returns_after_block(ir_instruction * ir,ir_return * then_return,ir_return * else_return)100 ir_if_return_visitor::move_returns_after_block(ir_instruction *ir,
101 ir_return *then_return,
102 ir_return *else_return)
103 {
104
105 if (!then_return->value) {
106 then_return->remove();
107 else_return->remove();
108 ir->insert_after(new(ir) ir_return(NULL));
109 } else {
110 ir_assignment *assign;
111 ir_variable *new_var = new(ir) ir_variable(then_return->value->type,
112 "if_return_tmp",
113 ir_var_temporary);
114 ir->insert_before(new_var);
115
116 assign = new(ir) ir_assignment(new(ir) ir_dereference_variable(new_var),
117 then_return->value, NULL);
118 then_return->replace_with(assign);
119
120 assign = new(ir) ir_assignment(new(ir) ir_dereference_variable(new_var),
121 else_return->value, NULL);
122 else_return->replace_with(assign);
123
124 ir_dereference_variable *deref = new(ir) ir_dereference_variable(new_var);
125 ir->insert_after(new(ir) ir_return(deref));
126 }
127 this->progress = true;
128 }
129
130 ir_visitor_status
move_outer_block_inside(ir_instruction * ir,exec_list * inner_block)131 ir_if_return_visitor::move_outer_block_inside(ir_instruction *ir,
132 exec_list *inner_block)
133 {
134 if (!ir->get_next()->is_tail_sentinel()) {
135 while (!ir->get_next()->is_tail_sentinel()) {
136 ir_instruction *move_ir = (ir_instruction *)ir->get_next();
137
138 move_ir->remove();
139 inner_block->push_tail(move_ir);
140 }
141
142 /* If we move the instructions following ir inside the block, it
143 * will confuse the exec_list iteration in the parent that visited
144 * us. So stop the visit at this point.
145 */
146 return visit_stop;
147 } else {
148 return visit_continue;
149 }
150 }
151
152 /* Normalize a function to always have a return statement at the end.
153 *
154 * This avoids the ir_if handler needing to know whether it is at the
155 * top level of the function to know if there's an implicit return at
156 * the end of the outer block.
157 */
158 ir_visitor_status
visit_enter(ir_function_signature * ir)159 ir_if_return_visitor::visit_enter(ir_function_signature *ir)
160 {
161 ir_return *ret;
162
163 if (!ir->is_defined)
164 return visit_continue_with_parent;
165 if (strcmp(ir->function_name(), "main") == 0)
166 return visit_continue_with_parent;
167
168 ret = find_return_in_block(&ir->body);
169
170 if (ret) {
171 truncate_after_instruction(ret);
172 } else {
173 if (ir->return_type->is_void()) {
174 ir->body.push_tail(new(ir) ir_return(NULL));
175 } else {
176 /* Probably, if we've got a function with a return value
177 * hitting this point, it's something like:
178 *
179 * float reduce_below_half(float val)
180 * {
181 * while () {
182 * if (val >= 0.5)
183 * val /= 2.0;
184 * else
185 * return val;
186 * }
187 * }
188 *
189 * So we gain a junk return statement of an undefined value
190 * at the end that never gets executed. However, a backend
191 * using this pass is probably desperate to get rid of
192 * function calls, so go ahead and do it for their sake in
193 * case it fixes apps.
194 */
195 ir_variable *undef = new(ir) ir_variable(ir->return_type,
196 "if_return_undef",
197 ir_var_temporary);
198 ir->body.push_tail(undef);
199
200 ir_dereference_variable *deref = new(ir) ir_dereference_variable(undef);
201 ir->body.push_tail(new(ir) ir_return(deref));
202 }
203 }
204
205 return visit_continue;
206 }
207
208 ir_visitor_status
visit_leave(ir_if * ir)209 ir_if_return_visitor::visit_leave(ir_if *ir)
210 {
211 ir_return *then_return;
212 ir_return *else_return;
213
214 then_return = find_return_in_block(&ir->then_instructions);
215 else_return = find_return_in_block(&ir->else_instructions);
216 if (!then_return && !else_return)
217 return visit_continue;
218
219 /* Trim off any trailing instructions after the return statements
220 * on both sides.
221 */
222 truncate_after_instruction(then_return);
223 truncate_after_instruction(else_return);
224
225 /* If both sides return, then we can move the returns to a single
226 * one outside the if statement.
227 */
228 if (then_return && else_return) {
229 move_returns_after_block(ir, then_return, else_return);
230 return visit_continue;
231 }
232
233 /* If only one side returns, then the block of code after the "if"
234 * is only executed by the other side, so those instructions don't
235 * need to be anywhere but that other side.
236 *
237 * This will usually pull a return statement up into the other
238 * side, so we'll trigger the above case on the next pass.
239 */
240 if (then_return) {
241 return move_outer_block_inside(ir, &ir->else_instructions);
242 } else {
243 assert(else_return);
244 return move_outer_block_inside(ir, &ir->then_instructions);
245 }
246 }
247