1 /*
2 * Copyright © 2010 Luca Barbieri
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_variable_index_to_cond_assign.cpp
26 *
27 * Turns non-constant indexing into array types to a series of
28 * conditional moves of each element into a temporary.
29 *
30 * Pre-DX10 GPUs often don't have a native way to do this operation,
31 * and this works around that.
32 */
33
34 #include "ir.h"
35 #include "ir_rvalue_visitor.h"
36 #include "ir_optimization.h"
37 #include "glsl_types.h"
38 #include "main/macros.h"
39
40 struct assignment_generator
41 {
42 ir_instruction* base_ir;
43 ir_rvalue* array;
44 bool is_write;
45 ir_variable* var;
46
assignment_generatorassignment_generator47 assignment_generator()
48 {
49 }
50
generateassignment_generator51 void generate(unsigned i, ir_rvalue* condition, exec_list *list) const
52 {
53 /* Just clone the rest of the deref chain when trying to get at the
54 * underlying variable.
55 */
56 void *mem_ctx = hieralloc_parent(base_ir);
57 ir_rvalue *element =
58 new(mem_ctx) ir_dereference_array(this->array->clone(mem_ctx, NULL),
59 new(mem_ctx) ir_constant(i));
60 ir_rvalue *variable = new(mem_ctx) ir_dereference_variable(this->var);
61
62 ir_assignment *assignment = (is_write)
63 ? new(mem_ctx) ir_assignment(element, variable, condition)
64 : new(mem_ctx) ir_assignment(variable, element, condition);
65
66 list->push_tail(assignment);
67 }
68 };
69
70 struct switch_generator
71 {
72 /* make TFunction a template parameter if you need to use other generators */
73 typedef assignment_generator TFunction;
74 const TFunction& generator;
75
76 ir_variable* index;
77 unsigned linear_sequence_max_length;
78 unsigned condition_components;
79
80 void *mem_ctx;
81
switch_generatorswitch_generator82 switch_generator(const TFunction& generator, ir_variable *index,
83 unsigned linear_sequence_max_length,
84 unsigned condition_components)
85 : generator(generator), index(index),
86 linear_sequence_max_length(linear_sequence_max_length),
87 condition_components(condition_components)
88 {
89 this->mem_ctx = hieralloc_parent(index);
90 }
91
linear_sequenceswitch_generator92 void linear_sequence(unsigned begin, unsigned end, exec_list *list)
93 {
94 if (begin == end)
95 return;
96
97 /* If the array access is a read, read the first element of this subregion
98 * unconditionally. The remaining tests will possibly overwrite this
99 * value with one of the other array elements.
100 *
101 * This optimization cannot be done for writes because it will cause the
102 * first element of the subregion to be written possibly *in addition* to
103 * one of the other elements.
104 */
105 unsigned first;
106 if (!this->generator.is_write) {
107 this->generator.generate(begin, 0, list);
108 first = begin + 1;
109 } else {
110 first = begin;
111 }
112
113 for (unsigned i = first; i < end; i += 4) {
114 const unsigned comps = MIN2(condition_components, end - i);
115
116 ir_rvalue *broadcast_index =
117 new(this->mem_ctx) ir_dereference_variable(index);
118
119 if (comps) {
120 const ir_swizzle_mask m = { 0, 0, 0, 0, comps, false };
121 broadcast_index = new(this->mem_ctx) ir_swizzle(broadcast_index, m);
122 }
123
124 /* Compare the desired index value with the next block of four indices.
125 */
126 ir_constant_data test_indices_data;
127 memset(&test_indices_data, 0, sizeof(test_indices_data));
128 test_indices_data.i[0] = i;
129 test_indices_data.i[1] = i + 1;
130 test_indices_data.i[2] = i + 2;
131 test_indices_data.i[3] = i + 3;
132 ir_constant *const test_indices =
133 new(this->mem_ctx) ir_constant(broadcast_index->type,
134 &test_indices_data);
135
136 ir_rvalue *const condition_val =
137 new(this->mem_ctx) ir_expression(ir_binop_equal,
138 &glsl_type::bool_type[comps - 1],
139 broadcast_index,
140 test_indices);
141
142 ir_variable *const condition =
143 new(this->mem_ctx) ir_variable(condition_val->type,
144 "dereference_array_condition",
145 ir_var_temporary);
146 list->push_tail(condition);
147
148 ir_rvalue *const cond_deref =
149 new(this->mem_ctx) ir_dereference_variable(condition);
150 list->push_tail(new(this->mem_ctx) ir_assignment(cond_deref,
151 condition_val, 0));
152
153 if (comps == 1) {
154 ir_rvalue *const cond_deref =
155 new(this->mem_ctx) ir_dereference_variable(condition);
156
157 this->generator.generate(i, cond_deref, list);
158 } else {
159 for (unsigned j = 0; j < comps; j++) {
160 ir_rvalue *const cond_deref =
161 new(this->mem_ctx) ir_dereference_variable(condition);
162 ir_rvalue *const cond_swiz =
163 new(this->mem_ctx) ir_swizzle(cond_deref, j, 0, 0, 0, 1);
164
165 this->generator.generate(i + j, cond_swiz, list);
166 }
167 }
168 }
169 }
170
bisectswitch_generator171 void bisect(unsigned begin, unsigned end, exec_list *list)
172 {
173 unsigned middle = (begin + end) >> 1;
174
175 assert(index->type->is_integer());
176
177 ir_constant *const middle_c = (index->type->base_type == GLSL_TYPE_UINT)
178 ? new(this->mem_ctx) ir_constant((unsigned)middle)
179 : new(this->mem_ctx) ir_constant((int)middle);
180
181
182 ir_dereference_variable *deref =
183 new(this->mem_ctx) ir_dereference_variable(this->index);
184
185 ir_expression *less =
186 new(this->mem_ctx) ir_expression(ir_binop_less, glsl_type::bool_type,
187 deref, middle_c);
188
189 ir_if *if_less = new(this->mem_ctx) ir_if(less);
190
191 generate(begin, middle, &if_less->then_instructions);
192 generate(middle, end, &if_less->else_instructions);
193
194 list->push_tail(if_less);
195 }
196
generateswitch_generator197 void generate(unsigned begin, unsigned end, exec_list *list)
198 {
199 unsigned length = end - begin;
200 if (length <= this->linear_sequence_max_length)
201 return linear_sequence(begin, end, list);
202 else
203 return bisect(begin, end, list);
204 }
205 };
206
207 /**
208 * Visitor class for replacing expressions with ir_constant values.
209 */
210
211 class variable_index_to_cond_assign_visitor : public ir_rvalue_visitor {
212 public:
variable_index_to_cond_assign_visitor(bool lower_input,bool lower_output,bool lower_temp,bool lower_uniform)213 variable_index_to_cond_assign_visitor(bool lower_input,
214 bool lower_output,
215 bool lower_temp,
216 bool lower_uniform)
217 {
218 this->progress = false;
219 this->lower_inputs = lower_input;
220 this->lower_outputs = lower_output;
221 this->lower_temps = lower_temp;
222 this->lower_uniforms = lower_uniform;
223 }
224
225 bool progress;
226 bool lower_inputs;
227 bool lower_outputs;
228 bool lower_temps;
229 bool lower_uniforms;
230
is_array_or_matrix(const ir_instruction * ir) const231 bool is_array_or_matrix(const ir_instruction *ir) const
232 {
233 return (ir->type->is_array() || ir->type->is_matrix());
234 }
235
needs_lowering(ir_dereference_array * deref) const236 bool needs_lowering(ir_dereference_array *deref) const
237 {
238 if (deref == NULL || deref->array_index->as_constant()
239 || !is_array_or_matrix(deref->array))
240 return false;
241
242 if (deref->array->ir_type == ir_type_constant)
243 return this->lower_temps;
244
245 const ir_variable *const var = deref->array->variable_referenced();
246 switch (var->mode) {
247 case ir_var_auto:
248 case ir_var_temporary:
249 return this->lower_temps;
250 case ir_var_uniform:
251 return this->lower_uniforms;
252 case ir_var_in:
253 return (var->location == -1) ? this->lower_temps : this->lower_inputs;
254 case ir_var_out:
255 return (var->location == -1) ? this->lower_temps : this->lower_outputs;
256 case ir_var_inout:
257 return this->lower_temps;
258 }
259
260 assert(!"Should not get here.");
261 return false;
262 }
263
convert_dereference_array(ir_dereference_array * orig_deref,ir_rvalue * value)264 ir_variable *convert_dereference_array(ir_dereference_array *orig_deref,
265 ir_rvalue* value)
266 {
267 assert(is_array_or_matrix(orig_deref->array));
268
269 const unsigned length = (orig_deref->array->type->is_array())
270 ? orig_deref->array->type->length
271 : orig_deref->array->type->matrix_columns;
272
273 void *const mem_ctx = hieralloc_parent(base_ir);
274 ir_variable *var =
275 new(mem_ctx) ir_variable(orig_deref->type, "dereference_array_value",
276 ir_var_temporary);
277 base_ir->insert_before(var);
278
279 if (value) {
280 ir_dereference *lhs = new(mem_ctx) ir_dereference_variable(var);
281 ir_assignment *assign = new(mem_ctx) ir_assignment(lhs, value, NULL);
282
283 base_ir->insert_before(assign);
284 }
285
286 /* Store the index to a temporary to avoid reusing its tree. */
287 ir_variable *index =
288 new(mem_ctx) ir_variable(orig_deref->array_index->type,
289 "dereference_array_index", ir_var_temporary);
290 base_ir->insert_before(index);
291
292 ir_dereference *lhs = new(mem_ctx) ir_dereference_variable(index);
293 ir_assignment *assign =
294 new(mem_ctx) ir_assignment(lhs, orig_deref->array_index, NULL);
295 base_ir->insert_before(assign);
296
297 assignment_generator ag;
298 ag.array = orig_deref->array;
299 ag.base_ir = base_ir;
300 ag.var = var;
301 ag.is_write = !!value;
302
303 switch_generator sg(ag, index, 4, 4);
304
305 exec_list list;
306 sg.generate(0, length, &list);
307 base_ir->insert_before(&list);
308
309 return var;
310 }
311
handle_rvalue(ir_rvalue ** pir)312 virtual void handle_rvalue(ir_rvalue **pir)
313 {
314 if (!*pir)
315 return;
316
317 ir_dereference_array* orig_deref = (*pir)->as_dereference_array();
318 if (needs_lowering(orig_deref)) {
319 ir_variable* var = convert_dereference_array(orig_deref, 0);
320 assert(var);
321 *pir = new(hieralloc_parent(base_ir)) ir_dereference_variable(var);
322 this->progress = true;
323 }
324 }
325
326 ir_visitor_status
visit_leave(ir_assignment * ir)327 visit_leave(ir_assignment *ir)
328 {
329 ir_rvalue_visitor::visit_leave(ir);
330
331 ir_dereference_array *orig_deref = ir->lhs->as_dereference_array();
332
333 if (needs_lowering(orig_deref)) {
334 convert_dereference_array(orig_deref, ir->rhs);
335 ir->remove();
336 this->progress = true;
337 }
338
339 return visit_continue;
340 }
341 };
342
343 bool
lower_variable_index_to_cond_assign(exec_list * instructions,bool lower_input,bool lower_output,bool lower_temp,bool lower_uniform)344 lower_variable_index_to_cond_assign(exec_list *instructions,
345 bool lower_input,
346 bool lower_output,
347 bool lower_temp,
348 bool lower_uniform)
349 {
350 variable_index_to_cond_assign_visitor v(lower_input,
351 lower_output,
352 lower_temp,
353 lower_uniform);
354
355 visit_list_elements(&v, instructions);
356
357 return v.progress;
358 }
359