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 lower_if_to_cond_assign.cpp
26 *
27 * This attempts to flatten if-statements to conditional assignments for
28 * GPUs with limited or no flow control support.
29 *
30 * It can't handle other control flow being inside of its block, such
31 * as calls or loops. Hopefully loop unrolling and inlining will take
32 * care of those.
33 *
34 * Drivers for GPUs with no control flow support should simply call
35 *
36 * lower_if_to_cond_assign(instructions)
37 *
38 * to attempt to flatten all if-statements.
39 *
40 * Some GPUs (such as i965 prior to gen6) do support control flow, but have a
41 * maximum nesting depth N. Drivers for such hardware can call
42 *
43 * lower_if_to_cond_assign(instructions, N)
44 *
45 * to attempt to flatten any if-statements appearing at depth > N.
46 */
47
48 #include "glsl_types.h"
49 #include "ir.h"
50 #include "program/hash_table.h"
51
52 class ir_if_to_cond_assign_visitor : public ir_hierarchical_visitor {
53 public:
ir_if_to_cond_assign_visitor(unsigned max_depth)54 ir_if_to_cond_assign_visitor(unsigned max_depth)
55 {
56 this->progress = false;
57 this->max_depth = max_depth;
58 this->depth = 0;
59
60 this->condition_variables = hash_table_ctor(0, hash_table_pointer_hash,
61 hash_table_pointer_compare);
62 }
63
~ir_if_to_cond_assign_visitor()64 ~ir_if_to_cond_assign_visitor()
65 {
66 hash_table_dtor(this->condition_variables);
67 }
68
69 ir_visitor_status visit_enter(ir_if *);
70 ir_visitor_status visit_leave(ir_if *);
71
72 bool progress;
73 unsigned max_depth;
74 unsigned depth;
75
76 struct hash_table *condition_variables;
77 };
78
79 bool
lower_if_to_cond_assign(exec_list * instructions,unsigned max_depth)80 lower_if_to_cond_assign(exec_list *instructions, unsigned max_depth)
81 {
82 if (max_depth == UINT_MAX)
83 return false;
84
85 ir_if_to_cond_assign_visitor v(max_depth);
86
87 visit_list_elements(&v, instructions);
88
89 return v.progress;
90 }
91
92 void
check_control_flow(ir_instruction * ir,void * data)93 check_control_flow(ir_instruction *ir, void *data)
94 {
95 bool *found_control_flow = (bool *)data;
96 switch (ir->ir_type) {
97 case ir_type_call:
98 case ir_type_discard:
99 case ir_type_loop:
100 case ir_type_loop_jump:
101 case ir_type_return:
102 *found_control_flow = true;
103 break;
104 default:
105 break;
106 }
107 }
108
109 void
move_block_to_cond_assign(void * mem_ctx,ir_if * if_ir,ir_rvalue * cond_expr,exec_list * instructions,struct hash_table * ht)110 move_block_to_cond_assign(void *mem_ctx,
111 ir_if *if_ir, ir_rvalue *cond_expr,
112 exec_list *instructions,
113 struct hash_table *ht)
114 {
115 foreach_list_safe(node, instructions) {
116 ir_instruction *ir = (ir_instruction *) node;
117
118 if (ir->ir_type == ir_type_assignment) {
119 ir_assignment *assign = (ir_assignment *)ir;
120
121 if (hash_table_find(ht, assign) == NULL) {
122 hash_table_insert(ht, assign, assign);
123
124 /* If the LHS of the assignment is a condition variable that was
125 * previously added, insert an additional assignment of false to
126 * the variable.
127 */
128 const bool assign_to_cv =
129 hash_table_find(ht, assign->lhs->variable_referenced()) != NULL;
130
131 if (!assign->condition) {
132 if (assign_to_cv) {
133 assign->rhs =
134 new(mem_ctx) ir_expression(ir_binop_logic_and,
135 glsl_type::bool_type,
136 cond_expr->clone(mem_ctx, NULL),
137 assign->rhs);
138 } else {
139 assign->condition = cond_expr->clone(mem_ctx, NULL);
140 }
141 } else {
142 assign->condition =
143 new(mem_ctx) ir_expression(ir_binop_logic_and,
144 glsl_type::bool_type,
145 cond_expr->clone(mem_ctx, NULL),
146 assign->condition);
147 }
148 }
149 }
150
151 /* Now, move from the if block to the block surrounding it. */
152 ir->remove();
153 if_ir->insert_before(ir);
154 }
155 }
156
157 ir_visitor_status
visit_enter(ir_if * ir)158 ir_if_to_cond_assign_visitor::visit_enter(ir_if *ir)
159 {
160 (void) ir;
161 this->depth++;
162
163 return visit_continue;
164 }
165
166 ir_visitor_status
visit_leave(ir_if * ir)167 ir_if_to_cond_assign_visitor::visit_leave(ir_if *ir)
168 {
169 /* Only flatten when beyond the GPU's maximum supported nesting depth. */
170 if (this->depth-- <= this->max_depth)
171 return visit_continue;
172
173 bool found_control_flow = false;
174 ir_assignment *assign;
175
176 /* Check that both blocks don't contain anything we can't support. */
177 foreach_iter(exec_list_iterator, then_iter, ir->then_instructions) {
178 ir_instruction *then_ir = (ir_instruction *)then_iter.get();
179 visit_tree(then_ir, check_control_flow, &found_control_flow);
180 }
181 foreach_iter(exec_list_iterator, else_iter, ir->else_instructions) {
182 ir_instruction *else_ir = (ir_instruction *)else_iter.get();
183 visit_tree(else_ir, check_control_flow, &found_control_flow);
184 }
185 if (found_control_flow)
186 return visit_continue;
187
188 void *mem_ctx = ralloc_parent(ir);
189
190 /* Store the condition to a variable. Move all of the instructions from
191 * the then-clause of the if-statement. Use the condition variable as a
192 * condition for all assignments.
193 */
194 ir_variable *const then_var =
195 new(mem_ctx) ir_variable(glsl_type::bool_type,
196 "if_to_cond_assign_then",
197 ir_var_temporary);
198 ir->insert_before(then_var);
199
200 ir_dereference_variable *then_cond =
201 new(mem_ctx) ir_dereference_variable(then_var);
202
203 assign = new(mem_ctx) ir_assignment(then_cond, ir->condition);
204 ir->insert_before(assign);
205
206 move_block_to_cond_assign(mem_ctx, ir, then_cond,
207 &ir->then_instructions,
208 this->condition_variables);
209
210 /* Add the new condition variable to the hash table. This allows us to
211 * find this variable when lowering other (enclosing) if-statements.
212 */
213 hash_table_insert(this->condition_variables, then_var, then_var);
214
215 /* If there are instructions in the else-clause, store the inverse of the
216 * condition to a variable. Move all of the instructions from the
217 * else-clause if the if-statement. Use the (inverse) condition variable
218 * as a condition for all assignments.
219 */
220 if (!ir->else_instructions.is_empty()) {
221 ir_variable *const else_var =
222 new(mem_ctx) ir_variable(glsl_type::bool_type,
223 "if_to_cond_assign_else",
224 ir_var_temporary);
225 ir->insert_before(else_var);
226
227 ir_dereference_variable *else_cond =
228 new(mem_ctx) ir_dereference_variable(else_var);
229
230 ir_rvalue *inverse =
231 new(mem_ctx) ir_expression(ir_unop_logic_not,
232 then_cond->clone(mem_ctx, NULL));
233
234 assign = new(mem_ctx) ir_assignment(else_cond, inverse);
235 ir->insert_before(assign);
236
237 move_block_to_cond_assign(mem_ctx, ir, else_cond,
238 &ir->else_instructions,
239 this->condition_variables);
240
241 /* Add the new condition variable to the hash table. This allows us to
242 * find this variable when lowering other (enclosing) if-statements.
243 */
244 hash_table_insert(this->condition_variables, else_var, else_var);
245 }
246
247 ir->remove();
248
249 this->progress = true;
250
251 return visit_continue;
252 }
253