2 * Copyright © 2010 Luca Barbieri
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
21 * DEALINGS IN THE SOFTWARE.
25 * \file lower_variable_index_to_cond_assign.cpp
27 * Turns non-constant indexing into array types to a series of
28 * conditional moves of each element into a temporary.
30 * Pre-DX10 GPUs often don't have a native way to do this operation,
31 * and this works around that.
35 #include "ir_rvalue_visitor.h"
36 #include "ir_optimization.h"
37 #include "glsl_types.h"
38 #include "main/macros.h"
40 struct assignment_generator
42 ir_instruction
* base_ir
;
47 assignment_generator()
51 void generate(unsigned i
, ir_rvalue
* condition
, exec_list
*list
) const
53 /* Just clone the rest of the deref chain when trying to get at the
54 * underlying variable.
56 void *mem_ctx
= talloc_parent(base_ir
);
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
);
62 ir_assignment
*assignment
= (is_write
)
63 ? new(mem_ctx
) ir_assignment(element
, variable
, condition
)
64 : new(mem_ctx
) ir_assignment(variable
, element
, condition
);
66 list
->push_tail(assignment
);
70 struct switch_generator
72 /* make TFunction a template parameter if you need to use other generators */
73 typedef assignment_generator TFunction
;
74 const TFunction
& generator
;
77 unsigned linear_sequence_max_length
;
78 unsigned condition_components
;
82 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
)
89 this->mem_ctx
= talloc_parent(index
);
92 void linear_sequence(unsigned begin
, unsigned end
, exec_list
*list
)
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.
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.
106 if (!this->generator
.is_write
) {
107 this->generator
.generate(begin
, 0, list
);
113 for (unsigned i
= first
; i
< end
; i
+= 4) {
114 const unsigned comps
= MIN2(condition_components
, end
- i
);
116 ir_rvalue
*broadcast_index
=
117 new(this->mem_ctx
) ir_dereference_variable(index
);
120 const ir_swizzle_mask m
= { 0, 1, 2, 3, comps
, false };
121 broadcast_index
= new(this->mem_ctx
) ir_swizzle(broadcast_index
, m
);
124 /* Compare the desired index value with the next block of four indices.
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
,
136 ir_rvalue
*const condition_val
=
137 new(this->mem_ctx
) ir_expression(ir_binop_equal
,
138 &glsl_type::bool_type
[comps
- 1],
142 ir_variable
*const condition
=
143 new(this->mem_ctx
) ir_variable(condition_val
->type
,
144 "dereference_array_condition",
146 list
->push_tail(condition
);
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
,
154 ir_rvalue
*const cond_deref
=
155 new(this->mem_ctx
) ir_dereference_variable(condition
);
157 this->generator
.generate(i
, cond_deref
, list
);
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);
165 this->generator
.generate(i
+ j
, cond_swiz
, list
);
171 void bisect(unsigned begin
, unsigned end
, exec_list
*list
)
173 unsigned middle
= (begin
+ end
) >> 1;
175 assert(index
->type
->is_integer());
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
);
182 ir_dereference_variable
*deref
=
183 new(this->mem_ctx
) ir_dereference_variable(this->index
);
185 ir_expression
*less
=
186 new(this->mem_ctx
) ir_expression(ir_binop_less
, glsl_type::bool_type
,
189 ir_if
*if_less
= new(this->mem_ctx
) ir_if(less
);
191 generate(begin
, middle
, &if_less
->then_instructions
);
192 generate(middle
, end
, &if_less
->else_instructions
);
194 list
->push_tail(if_less
);
197 void generate(unsigned begin
, unsigned end
, exec_list
*list
)
199 unsigned length
= end
- begin
;
200 if (length
<= this->linear_sequence_max_length
)
201 return linear_sequence(begin
, end
, list
);
203 return bisect(begin
, end
, list
);
208 * Visitor class for replacing expressions with ir_constant values.
211 class variable_index_to_cond_assign_visitor
: public ir_rvalue_visitor
{
213 variable_index_to_cond_assign_visitor()
215 this->progress
= false;
220 ir_variable
*convert_dereference_array(ir_dereference_array
*orig_deref
,
224 if (orig_deref
->array
->type
->is_array())
225 length
= orig_deref
->array
->type
->length
;
226 else if (orig_deref
->array
->type
->is_matrix())
227 length
= orig_deref
->array
->type
->matrix_columns
;
231 void *const mem_ctx
= talloc_parent(base_ir
);
233 new(mem_ctx
) ir_variable(orig_deref
->type
, "dereference_array_value",
235 base_ir
->insert_before(var
);
238 ir_dereference
*lhs
= new(mem_ctx
) ir_dereference_variable(var
);
239 ir_assignment
*assign
= new(mem_ctx
) ir_assignment(lhs
, value
, NULL
);
241 base_ir
->insert_before(assign
);
244 /* Store the index to a temporary to avoid reusing its tree. */
246 new(mem_ctx
) ir_variable(orig_deref
->array_index
->type
,
247 "dereference_array_index", ir_var_temporary
);
248 base_ir
->insert_before(index
);
250 ir_dereference
*lhs
= new(mem_ctx
) ir_dereference_variable(index
);
251 ir_assignment
*assign
=
252 new(mem_ctx
) ir_assignment(lhs
, orig_deref
->array_index
, NULL
);
253 base_ir
->insert_before(assign
);
255 assignment_generator ag
;
256 ag
.array
= orig_deref
->array
;
257 ag
.base_ir
= base_ir
;
259 ag
.is_write
= !!value
;
261 switch_generator
sg(ag
, index
, 4, 4);
264 sg
.generate(0, length
, &list
);
265 base_ir
->insert_before(&list
);
270 virtual void handle_rvalue(ir_rvalue
**pir
)
275 ir_dereference_array
* orig_deref
= (*pir
)->as_dereference_array();
276 if (orig_deref
&& !orig_deref
->array_index
->as_constant()
277 && (orig_deref
->array
->type
->is_array()
278 || orig_deref
->array
->type
->is_matrix())) {
279 ir_variable
* var
= convert_dereference_array(orig_deref
, 0);
281 *pir
= new(talloc_parent(base_ir
)) ir_dereference_variable(var
);
282 this->progress
= true;
287 visit_leave(ir_assignment
*ir
)
289 ir_rvalue_visitor::visit_leave(ir
);
291 ir_dereference_array
*orig_deref
= ir
->lhs
->as_dereference_array();
293 if (orig_deref
&& !orig_deref
->array_index
->as_constant()
294 && (orig_deref
->array
->type
->is_array()
295 || orig_deref
->array
->type
->is_matrix())) {
296 convert_dereference_array(orig_deref
, ir
->rhs
);
298 this->progress
= true;
301 return visit_continue
;
306 lower_variable_index_to_cond_assign(exec_list
*instructions
)
308 variable_index_to_cond_assign_visitor v
;
310 visit_list_elements(&v
, instructions
);