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.
33 * The lowering process proceeds as follows. Each non-constant index
34 * found in an r-value is converted to a canonical form \c array[i]. Each
35 * element of the array is conditionally assigned to a temporary by comparing
36 * \c i to a constant index. This is done by cloning the canonical form and
37 * replacing all occurances of \c i with a constant. Each remaining occurance
38 * of the canonical form in the IR is replaced with a dereference of the
41 * L-values with non-constant indices are handled similarly. In this case,
42 * the RHS of the assignment is assigned to a temporary. The non-constant
43 * index is replace with the canonical form (just like for r-values). The
44 * temporary is conditionally assigned to each element of the canonical form
45 * by comparing \c i with each index. The same clone-and-replace scheme is
50 #include "ir_rvalue_visitor.h"
51 #include "ir_optimization.h"
52 #include "glsl_types.h"
53 #include "main/macros.h"
56 is_array_or_matrix(const ir_instruction
*ir
)
58 return (ir
->type
->is_array() || ir
->type
->is_matrix());
62 * Replace a dereference of a variable with a specified r-value
64 * Each time a dereference of the specified value is replaced, the r-value
67 class deref_replacer
: public ir_rvalue_visitor
{
69 deref_replacer(const ir_variable
*variable_to_replace
, ir_rvalue
*value
)
70 : variable_to_replace(variable_to_replace
), value(value
),
73 assert(this->variable_to_replace
!= NULL
);
74 assert(this->value
!= NULL
);
77 virtual void handle_rvalue(ir_rvalue
**rvalue
)
79 ir_dereference_variable
*const dv
= (*rvalue
)->as_dereference_variable();
81 if ((dv
!= NULL
) && (dv
->var
== this->variable_to_replace
)) {
82 this->progress
= true;
83 *rvalue
= this->value
->clone(ralloc_parent(*rvalue
), NULL
);
87 const ir_variable
*variable_to_replace
;
93 * Find a variable index dereference of an array in an rvalue tree
95 class find_variable_index
: public ir_hierarchical_visitor
{
103 virtual ir_visitor_status
visit_enter(ir_dereference_array
*ir
)
105 if (is_array_or_matrix(ir
->array
)
106 && (ir
->array_index
->as_constant() == NULL
)) {
111 return visit_continue
;
115 * First array dereference found in the tree that has a non-constant index.
117 ir_dereference_array
*deref
;
120 struct assignment_generator
122 ir_instruction
* base_ir
;
123 ir_dereference
*rvalue
;
124 ir_variable
*old_index
;
126 unsigned int write_mask
;
129 assignment_generator()
133 void generate(unsigned i
, ir_rvalue
* condition
, exec_list
*list
) const
135 /* Just clone the rest of the deref chain when trying to get at the
136 * underlying variable.
138 void *mem_ctx
= ralloc_parent(base_ir
);
140 /* Clone the old r-value in its entirety. Then replace any occurances of
141 * the old variable index with the new constant index.
143 ir_dereference
*element
= this->rvalue
->clone(mem_ctx
, NULL
);
144 ir_constant
*const index
= new(mem_ctx
) ir_constant(i
);
145 deref_replacer
r(this->old_index
, index
);
149 /* Generate a conditional assignment to (or from) the constant indexed
152 ir_rvalue
*variable
= new(mem_ctx
) ir_dereference_variable(this->var
);
153 ir_assignment
*const assignment
= (is_write
)
154 ? new(mem_ctx
) ir_assignment(element
, variable
, condition
, write_mask
)
155 : new(mem_ctx
) ir_assignment(variable
, element
, condition
);
157 list
->push_tail(assignment
);
161 struct switch_generator
163 /* make TFunction a template parameter if you need to use other generators */
164 typedef assignment_generator TFunction
;
165 const TFunction
& generator
;
168 unsigned linear_sequence_max_length
;
169 unsigned condition_components
;
173 switch_generator(const TFunction
& generator
, ir_variable
*index
,
174 unsigned linear_sequence_max_length
,
175 unsigned condition_components
)
176 : generator(generator
), index(index
),
177 linear_sequence_max_length(linear_sequence_max_length
),
178 condition_components(condition_components
)
180 this->mem_ctx
= ralloc_parent(index
);
183 void linear_sequence(unsigned begin
, unsigned end
, exec_list
*list
)
188 /* If the array access is a read, read the first element of this subregion
189 * unconditionally. The remaining tests will possibly overwrite this
190 * value with one of the other array elements.
192 * This optimization cannot be done for writes because it will cause the
193 * first element of the subregion to be written possibly *in addition* to
194 * one of the other elements.
197 if (!this->generator
.is_write
) {
198 this->generator
.generate(begin
, 0, list
);
204 for (unsigned i
= first
; i
< end
; i
+= 4) {
205 const unsigned comps
= MIN2(condition_components
, end
- i
);
207 ir_rvalue
*broadcast_index
=
208 new(this->mem_ctx
) ir_dereference_variable(index
);
211 const ir_swizzle_mask m
= { 0, 0, 0, 0, comps
, false };
212 broadcast_index
= new(this->mem_ctx
) ir_swizzle(broadcast_index
, m
);
215 /* Compare the desired index value with the next block of four indices.
217 ir_constant_data test_indices_data
;
218 memset(&test_indices_data
, 0, sizeof(test_indices_data
));
219 test_indices_data
.i
[0] = i
;
220 test_indices_data
.i
[1] = i
+ 1;
221 test_indices_data
.i
[2] = i
+ 2;
222 test_indices_data
.i
[3] = i
+ 3;
223 ir_constant
*const test_indices
=
224 new(this->mem_ctx
) ir_constant(broadcast_index
->type
,
227 ir_rvalue
*const condition_val
=
228 new(this->mem_ctx
) ir_expression(ir_binop_equal
,
229 &glsl_type::bool_type
[comps
- 1],
233 ir_variable
*const condition
=
234 new(this->mem_ctx
) ir_variable(condition_val
->type
,
235 "dereference_array_condition",
237 list
->push_tail(condition
);
239 ir_rvalue
*const cond_deref
=
240 new(this->mem_ctx
) ir_dereference_variable(condition
);
241 list
->push_tail(new(this->mem_ctx
) ir_assignment(cond_deref
,
245 ir_rvalue
*const cond_deref
=
246 new(this->mem_ctx
) ir_dereference_variable(condition
);
248 this->generator
.generate(i
, cond_deref
, list
);
250 for (unsigned j
= 0; j
< comps
; j
++) {
251 ir_rvalue
*const cond_deref
=
252 new(this->mem_ctx
) ir_dereference_variable(condition
);
253 ir_rvalue
*const cond_swiz
=
254 new(this->mem_ctx
) ir_swizzle(cond_deref
, j
, 0, 0, 0, 1);
256 this->generator
.generate(i
+ j
, cond_swiz
, list
);
262 void bisect(unsigned begin
, unsigned end
, exec_list
*list
)
264 unsigned middle
= (begin
+ end
) >> 1;
266 assert(index
->type
->is_integer());
268 ir_constant
*const middle_c
= (index
->type
->base_type
== GLSL_TYPE_UINT
)
269 ? new(this->mem_ctx
) ir_constant((unsigned)middle
)
270 : new(this->mem_ctx
) ir_constant((int)middle
);
273 ir_dereference_variable
*deref
=
274 new(this->mem_ctx
) ir_dereference_variable(this->index
);
276 ir_expression
*less
=
277 new(this->mem_ctx
) ir_expression(ir_binop_less
, glsl_type::bool_type
,
280 ir_if
*if_less
= new(this->mem_ctx
) ir_if(less
);
282 generate(begin
, middle
, &if_less
->then_instructions
);
283 generate(middle
, end
, &if_less
->else_instructions
);
285 list
->push_tail(if_less
);
288 void generate(unsigned begin
, unsigned end
, exec_list
*list
)
290 unsigned length
= end
- begin
;
291 if (length
<= this->linear_sequence_max_length
)
292 return linear_sequence(begin
, end
, list
);
294 return bisect(begin
, end
, list
);
299 * Visitor class for replacing expressions with ir_constant values.
302 class variable_index_to_cond_assign_visitor
: public ir_rvalue_visitor
{
304 variable_index_to_cond_assign_visitor(bool lower_input
,
309 this->progress
= false;
310 this->lower_inputs
= lower_input
;
311 this->lower_outputs
= lower_output
;
312 this->lower_temps
= lower_temp
;
313 this->lower_uniforms
= lower_uniform
;
322 bool storage_type_needs_lowering(ir_dereference_array
*deref
) const
324 /* If a variable isn't eventually the target of this dereference, then
325 * it must be a constant or some sort of anonymous temporary storage.
327 * FINISHME: Is this correct? Most drivers treat arrays of constants as
328 * FINISHME: uniforms. It seems like this should do the same.
330 const ir_variable
*const var
= deref
->array
->variable_referenced();
332 return this->lower_temps
;
336 case ir_var_temporary
:
337 return this->lower_temps
;
339 return this->lower_uniforms
;
341 case ir_var_const_in
:
342 return (var
->location
== -1) ? this->lower_temps
: this->lower_inputs
;
344 return (var
->location
== -1) ? this->lower_temps
: this->lower_outputs
;
346 return this->lower_temps
;
349 assert(!"Should not get here.");
353 bool needs_lowering(ir_dereference_array
*deref
) const
355 if (deref
== NULL
|| deref
->array_index
->as_constant()
356 || !is_array_or_matrix(deref
->array
))
359 return this->storage_type_needs_lowering(deref
);
362 ir_variable
*convert_dereference_array(ir_dereference_array
*orig_deref
,
363 ir_assignment
* orig_assign
,
364 ir_dereference
*orig_base
)
366 assert(is_array_or_matrix(orig_deref
->array
));
368 const unsigned length
= (orig_deref
->array
->type
->is_array())
369 ? orig_deref
->array
->type
->length
370 : orig_deref
->array
->type
->matrix_columns
;
372 void *const mem_ctx
= ralloc_parent(base_ir
);
374 /* Temporary storage for either the result of the dereference of
375 * the array, or the RHS that's being assigned into the
376 * dereference of the array.
381 var
= new(mem_ctx
) ir_variable(orig_assign
->rhs
->type
,
382 "dereference_array_value",
384 base_ir
->insert_before(var
);
386 ir_dereference
*lhs
= new(mem_ctx
) ir_dereference_variable(var
);
387 ir_assignment
*assign
= new(mem_ctx
) ir_assignment(lhs
,
391 base_ir
->insert_before(assign
);
393 var
= new(mem_ctx
) ir_variable(orig_deref
->type
,
394 "dereference_array_value",
396 base_ir
->insert_before(var
);
399 /* Store the index to a temporary to avoid reusing its tree. */
401 new(mem_ctx
) ir_variable(orig_deref
->array_index
->type
,
402 "dereference_array_index", ir_var_temporary
);
403 base_ir
->insert_before(index
);
405 ir_dereference
*lhs
= new(mem_ctx
) ir_dereference_variable(index
);
406 ir_assignment
*assign
=
407 new(mem_ctx
) ir_assignment(lhs
, orig_deref
->array_index
, NULL
);
408 base_ir
->insert_before(assign
);
410 orig_deref
->array_index
= lhs
->clone(mem_ctx
, NULL
);
412 assignment_generator ag
;
413 ag
.rvalue
= orig_base
;
414 ag
.base_ir
= base_ir
;
415 ag
.old_index
= index
;
419 ag
.write_mask
= orig_assign
->write_mask
;
424 switch_generator
sg(ag
, index
, 4, 4);
426 /* If the original assignment has a condition, respect that original
427 * condition! This is acomplished by wrapping the new conditional
428 * assignments in an if-statement that uses the original condition.
430 if ((orig_assign
!= NULL
) && (orig_assign
->condition
!= NULL
)) {
431 /* No need to clone the condition because the IR that it hangs on is
432 * going to be removed from the instruction sequence.
434 ir_if
*if_stmt
= new(mem_ctx
) ir_if(orig_assign
->condition
);
436 sg
.generate(0, length
, &if_stmt
->then_instructions
);
437 base_ir
->insert_before(if_stmt
);
441 sg
.generate(0, length
, &list
);
442 base_ir
->insert_before(&list
);
448 virtual void handle_rvalue(ir_rvalue
**pir
)
450 if (this->in_assignee
)
456 ir_dereference_array
* orig_deref
= (*pir
)->as_dereference_array();
457 if (needs_lowering(orig_deref
)) {
459 convert_dereference_array(orig_deref
, NULL
, orig_deref
);
461 *pir
= new(ralloc_parent(base_ir
)) ir_dereference_variable(var
);
462 this->progress
= true;
467 visit_leave(ir_assignment
*ir
)
469 ir_rvalue_visitor::visit_leave(ir
);
471 find_variable_index f
;
474 if ((f
.deref
!= NULL
) && storage_type_needs_lowering(f
.deref
)) {
475 convert_dereference_array(f
.deref
, ir
, ir
->lhs
);
477 this->progress
= true;
480 return visit_continue
;
485 lower_variable_index_to_cond_assign(exec_list
*instructions
,
491 variable_index_to_cond_assign_visitor
v(lower_input
,
496 /* Continue lowering until no progress is made. If there are multiple
497 * levels of indirection (e.g., non-constant indexing of array elements and
498 * matrix columns of an array of matrix), each pass will only lower one
499 * level of indirection.
503 visit_list_elements(&v
, instructions
);
504 } while (v
.progress
);