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 * Generate a comparison value for a block of indices
58 * Lowering passes for non-constant indexing of arrays, matrices, or vectors
59 * can use this to generate blocks of index comparison values.
61 * \param instructions List where new instructions will be appended
62 * \param index \c ir_variable containing the desired index
63 * \param base Base value for this block of comparisons
64 * \param components Number of unique index values to compare. This must
65 * be on the range [1, 4].
66 * \param mem_ctx ralloc memory context to be used for all allocations.
69 * An \c ir_rvalue that \b must be cloned for each use in conditional
73 compare_index_block(exec_list
*instructions
, ir_variable
*index
,
74 unsigned base
, unsigned components
, void *mem_ctx
)
76 ir_rvalue
*broadcast_index
= new(mem_ctx
) ir_dereference_variable(index
);
78 assert(index
->type
->is_scalar());
79 assert(index
->type
->base_type
== GLSL_TYPE_INT
|| index
->type
->base_type
== GLSL_TYPE_UINT
);
80 assert(components
>= 1 && components
<= 4);
83 const ir_swizzle_mask m
= { 0, 0, 0, 0, components
, false };
84 broadcast_index
= new(mem_ctx
) ir_swizzle(broadcast_index
, m
);
87 /* Compare the desired index value with the next block of four indices.
89 ir_constant_data test_indices_data
;
90 memset(&test_indices_data
, 0, sizeof(test_indices_data
));
91 test_indices_data
.i
[0] = base
;
92 test_indices_data
.i
[1] = base
+ 1;
93 test_indices_data
.i
[2] = base
+ 2;
94 test_indices_data
.i
[3] = base
+ 3;
96 ir_constant
*const test_indices
=
97 new(mem_ctx
) ir_constant(broadcast_index
->type
,
100 ir_rvalue
*const condition_val
=
101 new(mem_ctx
) ir_expression(ir_binop_equal
,
102 glsl_type::bvec(components
),
106 ir_variable
*const condition
=
107 new(mem_ctx
) ir_variable(condition_val
->type
,
108 "dereference_condition",
110 instructions
->push_tail(condition
);
112 ir_rvalue
*const cond_deref
=
113 new(mem_ctx
) ir_dereference_variable(condition
);
114 instructions
->push_tail(new(mem_ctx
) ir_assignment(cond_deref
, condition_val
, 0));
120 is_array_or_matrix(const ir_rvalue
*ir
)
122 return (ir
->type
->is_array() || ir
->type
->is_matrix());
127 * Replace a dereference of a variable with a specified r-value
129 * Each time a dereference of the specified value is replaced, the r-value
132 class deref_replacer
: public ir_rvalue_visitor
{
134 deref_replacer(const ir_variable
*variable_to_replace
, ir_rvalue
*value
)
135 : variable_to_replace(variable_to_replace
), value(value
),
138 assert(this->variable_to_replace
!= NULL
);
139 assert(this->value
!= NULL
);
142 virtual void handle_rvalue(ir_rvalue
**rvalue
)
144 ir_dereference_variable
*const dv
= (*rvalue
)->as_dereference_variable();
146 if ((dv
!= NULL
) && (dv
->var
== this->variable_to_replace
)) {
147 this->progress
= true;
148 *rvalue
= this->value
->clone(ralloc_parent(*rvalue
), NULL
);
152 const ir_variable
*variable_to_replace
;
158 * Find a variable index dereference of an array in an rvalue tree
160 class find_variable_index
: public ir_hierarchical_visitor
{
162 find_variable_index()
168 virtual ir_visitor_status
visit_enter(ir_dereference_array
*ir
)
170 if (is_array_or_matrix(ir
->array
)
171 && (ir
->array_index
->as_constant() == NULL
)) {
176 return visit_continue
;
180 * First array dereference found in the tree that has a non-constant index.
182 ir_dereference_array
*deref
;
185 struct assignment_generator
187 ir_instruction
* base_ir
;
188 ir_dereference
*rvalue
;
189 ir_variable
*old_index
;
191 unsigned int write_mask
;
194 assignment_generator()
204 void generate(unsigned i
, ir_rvalue
* condition
, exec_list
*list
) const
206 /* Just clone the rest of the deref chain when trying to get at the
207 * underlying variable.
209 void *mem_ctx
= ralloc_parent(base_ir
);
211 /* Clone the old r-value in its entirety. Then replace any occurances of
212 * the old variable index with the new constant index.
214 ir_dereference
*element
= this->rvalue
->clone(mem_ctx
, NULL
);
215 ir_constant
*const index
= new(mem_ctx
) ir_constant(i
);
216 deref_replacer
r(this->old_index
, index
);
220 /* Generate a conditional assignment to (or from) the constant indexed
223 ir_rvalue
*variable
= new(mem_ctx
) ir_dereference_variable(this->var
);
224 ir_assignment
*const assignment
= (is_write
)
225 ? new(mem_ctx
) ir_assignment(element
, variable
, condition
, write_mask
)
226 : new(mem_ctx
) ir_assignment(variable
, element
, condition
);
228 list
->push_tail(assignment
);
232 struct switch_generator
234 /* make TFunction a template parameter if you need to use other generators */
235 typedef assignment_generator TFunction
;
236 const TFunction
& generator
;
239 unsigned linear_sequence_max_length
;
240 unsigned condition_components
;
244 switch_generator(const TFunction
& generator
, ir_variable
*index
,
245 unsigned linear_sequence_max_length
,
246 unsigned condition_components
)
247 : generator(generator
), index(index
),
248 linear_sequence_max_length(linear_sequence_max_length
),
249 condition_components(condition_components
)
251 this->mem_ctx
= ralloc_parent(index
);
254 void linear_sequence(unsigned begin
, unsigned end
, exec_list
*list
)
259 /* If the array access is a read, read the first element of this subregion
260 * unconditionally. The remaining tests will possibly overwrite this
261 * value with one of the other array elements.
263 * This optimization cannot be done for writes because it will cause the
264 * first element of the subregion to be written possibly *in addition* to
265 * one of the other elements.
268 if (!this->generator
.is_write
) {
269 this->generator
.generate(begin
, 0, list
);
275 for (unsigned i
= first
; i
< end
; i
+= 4) {
276 const unsigned comps
= MIN2(condition_components
, end
- i
);
278 ir_rvalue
*const cond_deref
=
279 compare_index_block(list
, index
, i
, comps
, this->mem_ctx
);
282 this->generator
.generate(i
, cond_deref
->clone(this->mem_ctx
, NULL
),
285 for (unsigned j
= 0; j
< comps
; j
++) {
286 ir_rvalue
*const cond_swiz
=
287 new(this->mem_ctx
) ir_swizzle(cond_deref
->clone(this->mem_ctx
, NULL
),
290 this->generator
.generate(i
+ j
, cond_swiz
, list
);
296 void bisect(unsigned begin
, unsigned end
, exec_list
*list
)
298 unsigned middle
= (begin
+ end
) >> 1;
300 assert(index
->type
->is_integer());
302 ir_constant
*const middle_c
= (index
->type
->base_type
== GLSL_TYPE_UINT
)
303 ? new(this->mem_ctx
) ir_constant((unsigned)middle
)
304 : new(this->mem_ctx
) ir_constant((int)middle
);
307 ir_dereference_variable
*deref
=
308 new(this->mem_ctx
) ir_dereference_variable(this->index
);
310 ir_expression
*less
=
311 new(this->mem_ctx
) ir_expression(ir_binop_less
, glsl_type::bool_type
,
314 ir_if
*if_less
= new(this->mem_ctx
) ir_if(less
);
316 generate(begin
, middle
, &if_less
->then_instructions
);
317 generate(middle
, end
, &if_less
->else_instructions
);
319 list
->push_tail(if_less
);
322 void generate(unsigned begin
, unsigned end
, exec_list
*list
)
324 unsigned length
= end
- begin
;
325 if (length
<= this->linear_sequence_max_length
)
326 return linear_sequence(begin
, end
, list
);
328 return bisect(begin
, end
, list
);
333 * Visitor class for replacing expressions with ir_constant values.
336 class variable_index_to_cond_assign_visitor
: public ir_rvalue_visitor
{
338 variable_index_to_cond_assign_visitor(gl_shader_stage stage
,
344 this->progress
= false;
346 this->lower_inputs
= lower_input
;
347 this->lower_outputs
= lower_output
;
348 this->lower_temps
= lower_temp
;
349 this->lower_uniforms
= lower_uniform
;
354 gl_shader_stage stage
;
360 bool storage_type_needs_lowering(ir_dereference_array
*deref
) const
362 /* If a variable isn't eventually the target of this dereference, then
363 * it must be a constant or some sort of anonymous temporary storage.
365 * FINISHME: Is this correct? Most drivers treat arrays of constants as
366 * FINISHME: uniforms. It seems like this should do the same.
368 const ir_variable
*const var
= deref
->array
->variable_referenced();
370 return this->lower_temps
;
372 switch (var
->data
.mode
) {
374 case ir_var_temporary
:
375 return this->lower_temps
;
378 case ir_var_shader_storage
:
379 return this->lower_uniforms
;
381 case ir_var_shader_shared
:
384 case ir_var_function_in
:
385 case ir_var_const_in
:
386 return this->lower_temps
;
388 case ir_var_shader_in
:
389 /* The input array size is unknown at compiler time for non-patch
390 * inputs in TCS and TES. The arrays are sized to
391 * the implementation-dependent limit "gl_MaxPatchVertices", but
392 * the real size is stored in the "gl_PatchVerticesIn" built-in
395 * The TCS input array size is specified by
396 * glPatchParameteri(GL_PATCH_VERTICES).
398 * The TES input array size is specified by the "vertices" output
399 * layout qualifier in TCS.
401 if ((stage
== MESA_SHADER_TESS_CTRL
||
402 stage
== MESA_SHADER_TESS_EVAL
) && !var
->data
.patch
)
404 return this->lower_inputs
;
406 case ir_var_function_out
:
407 /* TCS non-patch outputs can only be indexed with "gl_InvocationID".
408 * Other expressions are not allowed.
410 if (stage
== MESA_SHADER_TESS_CTRL
&& !var
->data
.patch
)
412 return this->lower_temps
;
414 case ir_var_shader_out
:
415 return this->lower_outputs
;
417 case ir_var_function_inout
:
418 return this->lower_temps
;
421 assert(!"Should not get here.");
425 bool needs_lowering(ir_dereference_array
*deref
) const
427 if (deref
== NULL
|| deref
->array_index
->as_constant()
428 || !is_array_or_matrix(deref
->array
))
431 return this->storage_type_needs_lowering(deref
);
434 ir_variable
*convert_dereference_array(ir_dereference_array
*orig_deref
,
435 ir_assignment
* orig_assign
,
436 ir_dereference
*orig_base
)
438 assert(is_array_or_matrix(orig_deref
->array
));
440 const unsigned length
= (orig_deref
->array
->type
->is_array())
441 ? orig_deref
->array
->type
->length
442 : orig_deref
->array
->type
->matrix_columns
;
444 void *const mem_ctx
= ralloc_parent(base_ir
);
446 /* Temporary storage for either the result of the dereference of
447 * the array, or the RHS that's being assigned into the
448 * dereference of the array.
453 var
= new(mem_ctx
) ir_variable(orig_assign
->rhs
->type
,
454 "dereference_array_value",
456 base_ir
->insert_before(var
);
458 ir_dereference
*lhs
= new(mem_ctx
) ir_dereference_variable(var
);
459 ir_assignment
*assign
= new(mem_ctx
) ir_assignment(lhs
,
463 base_ir
->insert_before(assign
);
465 var
= new(mem_ctx
) ir_variable(orig_deref
->type
,
466 "dereference_array_value",
468 base_ir
->insert_before(var
);
471 /* Store the index to a temporary to avoid reusing its tree. */
473 new(mem_ctx
) ir_variable(orig_deref
->array_index
->type
,
474 "dereference_array_index", ir_var_temporary
);
475 base_ir
->insert_before(index
);
477 ir_dereference
*lhs
= new(mem_ctx
) ir_dereference_variable(index
);
478 ir_assignment
*assign
=
479 new(mem_ctx
) ir_assignment(lhs
, orig_deref
->array_index
, NULL
);
480 base_ir
->insert_before(assign
);
482 orig_deref
->array_index
= lhs
->clone(mem_ctx
, NULL
);
484 assignment_generator ag
;
485 ag
.rvalue
= orig_base
;
486 ag
.base_ir
= base_ir
;
487 ag
.old_index
= index
;
491 ag
.write_mask
= orig_assign
->write_mask
;
496 switch_generator
sg(ag
, index
, 4, 4);
498 /* If the original assignment has a condition, respect that original
499 * condition! This is acomplished by wrapping the new conditional
500 * assignments in an if-statement that uses the original condition.
502 if ((orig_assign
!= NULL
) && (orig_assign
->condition
!= NULL
)) {
503 /* No need to clone the condition because the IR that it hangs on is
504 * going to be removed from the instruction sequence.
506 ir_if
*if_stmt
= new(mem_ctx
) ir_if(orig_assign
->condition
);
508 sg
.generate(0, length
, &if_stmt
->then_instructions
);
509 base_ir
->insert_before(if_stmt
);
513 sg
.generate(0, length
, &list
);
514 base_ir
->insert_before(&list
);
520 virtual void handle_rvalue(ir_rvalue
**pir
)
522 if (this->in_assignee
)
528 ir_dereference_array
* orig_deref
= (*pir
)->as_dereference_array();
529 if (needs_lowering(orig_deref
)) {
531 convert_dereference_array(orig_deref
, NULL
, orig_deref
);
533 *pir
= new(ralloc_parent(base_ir
)) ir_dereference_variable(var
);
534 this->progress
= true;
539 visit_leave(ir_assignment
*ir
)
541 ir_rvalue_visitor::visit_leave(ir
);
543 find_variable_index f
;
546 if ((f
.deref
!= NULL
) && storage_type_needs_lowering(f
.deref
)) {
547 convert_dereference_array(f
.deref
, ir
, ir
->lhs
);
549 this->progress
= true;
552 return visit_continue
;
556 } /* anonymous namespace */
559 lower_variable_index_to_cond_assign(gl_shader_stage stage
,
560 exec_list
*instructions
,
566 variable_index_to_cond_assign_visitor
v(stage
,
572 /* Continue lowering until no progress is made. If there are multiple
573 * levels of indirection (e.g., non-constant indexing of array elements and
574 * matrix columns of an array of matrix), each pass will only lower one
575 * level of indirection.
577 bool progress_ever
= false;
580 visit_list_elements(&v
, instructions
);
581 progress_ever
= v
.progress
|| progress_ever
;
582 } while (v
.progress
);
584 return progress_ever
;