2 * Copyright © 2010 Intel Corporation
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.
24 #include "compiler/glsl_types.h"
25 #include "loop_analysis.h"
26 #include "ir_hierarchical_visitor.h"
28 static void try_add_loop_terminator(loop_variable_state
*ls
, ir_if
*ir
);
30 static bool all_expression_operands_are_loop_constant(ir_rvalue
*,
33 static ir_rvalue
*get_basic_induction_increment(ir_assignment
*, hash_table
*);
36 * Find an initializer of a variable outside a loop
38 * Works backwards from the loop to find the pre-loop value of the variable.
39 * This is used, for example, to find the initial value of loop induction
42 * \param loop Loop where \c var is an induction variable
43 * \param var Variable whose initializer is to be found
46 * The \c ir_rvalue assigned to the variable outside the loop. May return
47 * \c NULL if no initializer can be found.
50 find_initial_value(ir_loop
*loop
, ir_variable
*var
)
52 for (exec_node
*node
= loop
->prev
; !node
->is_head_sentinel();
54 ir_instruction
*ir
= (ir_instruction
*) node
;
56 switch (ir
->ir_type
) {
59 case ir_type_loop_jump
:
64 case ir_type_function
:
65 case ir_type_function_signature
:
66 assert(!"Should not get here.");
69 case ir_type_assignment
: {
70 ir_assignment
*assign
= ir
->as_assignment();
71 ir_variable
*assignee
= assign
->lhs
->whole_variable_referenced();
74 return (assign
->condition
!= NULL
) ? NULL
: assign
->rhs
;
89 calculate_iterations(ir_rvalue
*from
, ir_rvalue
*to
, ir_rvalue
*increment
,
90 enum ir_expression_operation op
, bool continue_from_then
)
92 if (from
== NULL
|| to
== NULL
|| increment
== NULL
)
95 void *mem_ctx
= ralloc_context(NULL
);
97 ir_expression
*const sub
=
98 new(mem_ctx
) ir_expression(ir_binop_sub
, from
->type
, to
, from
);
100 ir_expression
*const div
=
101 new(mem_ctx
) ir_expression(ir_binop_div
, sub
->type
, sub
, increment
);
103 ir_constant
*iter
= div
->constant_expression_value(mem_ctx
);
105 ralloc_free(mem_ctx
);
109 if (!iter
->type
->is_integer()) {
110 const ir_expression_operation op
= iter
->type
->is_double()
111 ? ir_unop_d2i
: ir_unop_f2i
;
113 new(mem_ctx
) ir_expression(op
, glsl_type::int_type
, iter
, NULL
);
115 iter
= cast
->constant_expression_value(mem_ctx
);
118 int iter_value
= iter
->get_int_component(0);
120 /* Make sure that the calculated number of iterations satisfies the exit
121 * condition. This is needed to catch off-by-one errors and some types of
122 * ill-formed loops. For example, we need to detect that the following
123 * loop does not have a maximum iteration count.
125 * for (float x = 0.0; x != 0.9; x += 0.2)
128 const int bias
[] = { -1, 0, 1 };
129 bool valid_loop
= false;
131 for (unsigned i
= 0; i
< ARRAY_SIZE(bias
); i
++) {
132 /* Increment may be of type int, uint or float. */
133 switch (increment
->type
->base_type
) {
135 iter
= new(mem_ctx
) ir_constant(iter_value
+ bias
[i
]);
138 iter
= new(mem_ctx
) ir_constant(unsigned(iter_value
+ bias
[i
]));
140 case GLSL_TYPE_FLOAT
:
141 iter
= new(mem_ctx
) ir_constant(float(iter_value
+ bias
[i
]));
143 case GLSL_TYPE_DOUBLE
:
144 iter
= new(mem_ctx
) ir_constant(double(iter_value
+ bias
[i
]));
147 unreachable("Unsupported type for loop iterator.");
150 ir_expression
*const mul
=
151 new(mem_ctx
) ir_expression(ir_binop_mul
, increment
->type
, iter
,
154 ir_expression
*const add
=
155 new(mem_ctx
) ir_expression(ir_binop_add
, mul
->type
, mul
, from
);
158 new(mem_ctx
) ir_expression(op
, glsl_type::bool_type
, add
, to
);
159 if (continue_from_then
)
160 cmp
= new(mem_ctx
) ir_expression(ir_unop_logic_not
, cmp
);
162 ir_constant
*const cmp_result
= cmp
->constant_expression_value(mem_ctx
);
164 assert(cmp_result
!= NULL
);
165 if (cmp_result
->get_bool_component(0)) {
166 iter_value
+= bias
[i
];
172 ralloc_free(mem_ctx
);
173 return (valid_loop
) ? iter_value
: -1;
177 incremented_before_terminator(ir_loop
*loop
, ir_variable
*var
,
180 for (exec_node
*node
= loop
->body_instructions
.get_head();
181 !node
->is_tail_sentinel();
182 node
= node
->get_next()) {
183 ir_instruction
*ir
= (ir_instruction
*) node
;
185 switch (ir
->ir_type
) {
187 if (ir
->as_if() == terminator
)
191 case ir_type_assignment
: {
192 ir_assignment
*assign
= ir
->as_assignment();
193 ir_variable
*assignee
= assign
->lhs
->whole_variable_referenced();
195 if (assignee
== var
) {
196 assert(assign
->condition
== NULL
);
208 unreachable("Unable to find induction variable");
212 * Record the fact that the given loop variable was referenced inside the loop.
214 * \arg in_assignee is true if the reference was on the LHS of an assignment.
216 * \arg in_conditional_code_or_nested_loop is true if the reference occurred
217 * inside an if statement or a nested loop.
219 * \arg current_assignment is the ir_assignment node that the loop variable is
220 * on the LHS of, if any (ignored if \c in_assignee is false).
223 loop_variable::record_reference(bool in_assignee
,
224 bool in_conditional_code_or_nested_loop
,
225 ir_assignment
*current_assignment
)
228 assert(current_assignment
!= NULL
);
230 if (in_conditional_code_or_nested_loop
||
231 current_assignment
->condition
!= NULL
) {
232 this->conditional_or_nested_assignment
= true;
235 if (this->first_assignment
== NULL
) {
236 assert(this->num_assignments
== 0);
238 this->first_assignment
= current_assignment
;
241 this->num_assignments
++;
242 } else if (this->first_assignment
== current_assignment
) {
243 /* This catches the case where the variable is used in the RHS of an
244 * assignment where it is also in the LHS.
246 this->read_before_write
= true;
251 loop_state::loop_state()
253 this->ht
= _mesa_hash_table_create(NULL
, _mesa_hash_pointer
,
254 _mesa_key_pointer_equal
);
255 this->mem_ctx
= ralloc_context(NULL
);
256 this->loop_found
= false;
260 loop_state::~loop_state()
262 _mesa_hash_table_destroy(this->ht
, NULL
);
263 ralloc_free(this->mem_ctx
);
267 loop_variable_state
*
268 loop_state::insert(ir_loop
*ir
)
270 loop_variable_state
*ls
= new(this->mem_ctx
) loop_variable_state
;
272 _mesa_hash_table_insert(this->ht
, ir
, ls
);
273 this->loop_found
= true;
279 loop_variable_state
*
280 loop_state::get(const ir_loop
*ir
)
282 hash_entry
*entry
= _mesa_hash_table_search(this->ht
, ir
);
283 return entry
? (loop_variable_state
*) entry
->data
: NULL
;
288 loop_variable_state::get(const ir_variable
*ir
)
290 hash_entry
*entry
= _mesa_hash_table_search(this->var_hash
, ir
);
291 return entry
? (loop_variable
*) entry
->data
: NULL
;
296 loop_variable_state::insert(ir_variable
*var
)
298 void *mem_ctx
= ralloc_parent(this);
299 loop_variable
*lv
= rzalloc(mem_ctx
, loop_variable
);
303 _mesa_hash_table_insert(this->var_hash
, lv
->var
, lv
);
304 this->variables
.push_tail(lv
);
311 loop_variable_state::insert(ir_if
*if_stmt
, bool continue_from_then
)
313 void *mem_ctx
= ralloc_parent(this);
314 loop_terminator
*t
= new(mem_ctx
) loop_terminator();
317 t
->continue_from_then
= continue_from_then
;
319 this->terminators
.push_tail(t
);
326 * If the given variable already is recorded in the state for this loop,
327 * return the corresponding loop_variable object that records information
330 * Otherwise, create a new loop_variable object to record information about
331 * the variable, and set its \c read_before_write field appropriately based on
334 * \arg in_assignee is true if this variable was encountered on the LHS of an
338 loop_variable_state::get_or_insert(ir_variable
*var
, bool in_assignee
)
340 loop_variable
*lv
= this->get(var
);
343 lv
= this->insert(var
);
344 lv
->read_before_write
= !in_assignee
;
353 class loop_analysis
: public ir_hierarchical_visitor
{
355 loop_analysis(loop_state
*loops
);
357 virtual ir_visitor_status
visit(ir_loop_jump
*);
358 virtual ir_visitor_status
visit(ir_dereference_variable
*);
360 virtual ir_visitor_status
visit_enter(ir_call
*);
362 virtual ir_visitor_status
visit_enter(ir_loop
*);
363 virtual ir_visitor_status
visit_leave(ir_loop
*);
364 virtual ir_visitor_status
visit_enter(ir_assignment
*);
365 virtual ir_visitor_status
visit_leave(ir_assignment
*);
366 virtual ir_visitor_status
visit_enter(ir_if
*);
367 virtual ir_visitor_status
visit_leave(ir_if
*);
371 int if_statement_depth
;
373 ir_assignment
*current_assignment
;
378 } /* anonymous namespace */
380 loop_analysis::loop_analysis(loop_state
*loops
)
381 : loops(loops
), if_statement_depth(0), current_assignment(NULL
)
388 loop_analysis::visit(ir_loop_jump
*ir
)
392 assert(!this->state
.is_empty());
394 loop_variable_state
*const ls
=
395 (loop_variable_state
*) this->state
.get_head();
397 ls
->num_loop_jumps
++;
399 return visit_continue
;
404 loop_analysis::visit_enter(ir_call
*)
406 /* Mark every loop that we're currently analyzing as containing an ir_call
407 * (even those at outer nesting levels).
409 foreach_in_list(loop_variable_state
, ls
, &this->state
) {
410 ls
->contains_calls
= true;
413 return visit_continue_with_parent
;
418 loop_analysis::visit(ir_dereference_variable
*ir
)
420 /* If we're not somewhere inside a loop, there's nothing to do.
422 if (this->state
.is_empty())
423 return visit_continue
;
427 foreach_in_list(loop_variable_state
, ls
, &this->state
) {
428 ir_variable
*var
= ir
->variable_referenced();
429 loop_variable
*lv
= ls
->get_or_insert(var
, this->in_assignee
);
431 lv
->record_reference(this->in_assignee
,
432 nested
|| this->if_statement_depth
> 0,
433 this->current_assignment
);
437 return visit_continue
;
441 loop_analysis::visit_enter(ir_loop
*ir
)
443 loop_variable_state
*ls
= this->loops
->insert(ir
);
444 this->state
.push_head(ls
);
446 return visit_continue
;
450 loop_analysis::visit_leave(ir_loop
*ir
)
452 loop_variable_state
*const ls
=
453 (loop_variable_state
*) this->state
.pop_head();
455 /* Function calls may contain side effects. These could alter any of our
456 * variables in ways that cannot be known, and may even terminate shader
457 * execution (say, calling discard in the fragment shader). So we can't
458 * rely on any of our analysis about assignments to variables.
460 * We could perform some conservative analysis (prove there's no statically
461 * possible assignment, etc.) but it isn't worth it for now; function
462 * inlining will allow us to unroll loops anyway.
464 if (ls
->contains_calls
)
465 return visit_continue
;
467 foreach_in_list(ir_instruction
, node
, &ir
->body_instructions
) {
468 /* Skip over declarations at the start of a loop.
470 if (node
->as_variable())
473 ir_if
*if_stmt
= ((ir_instruction
*) node
)->as_if();
476 try_add_loop_terminator(ls
, if_stmt
);
480 foreach_in_list_safe(loop_variable
, lv
, &ls
->variables
) {
481 /* Move variables that are already marked as being loop constant to
482 * a separate list. These trivially don't need to be tested.
484 if (lv
->is_loop_constant()) {
486 ls
->constants
.push_tail(lv
);
490 /* Each variable assigned in the loop that isn't already marked as being loop
491 * constant might still be loop constant. The requirements at this point
494 * - Variable is written before it is read.
496 * - Only one assignment to the variable.
498 * - All operands on the RHS of the assignment are also loop constants.
500 * The last requirement is the reason for the progress loop. A variable
501 * marked as a loop constant on one pass may allow other variables to be
502 * marked as loop constant on following passes.
508 foreach_in_list_safe(loop_variable
, lv
, &ls
->variables
) {
509 if (lv
->conditional_or_nested_assignment
|| (lv
->num_assignments
> 1))
512 /* Process the RHS of the assignment. If all of the variables
513 * accessed there are loop constants, then add this
515 ir_rvalue
*const rhs
= lv
->first_assignment
->rhs
;
516 if (all_expression_operands_are_loop_constant(rhs
, ls
->var_hash
)) {
517 lv
->rhs_clean
= true;
519 if (lv
->is_loop_constant()) {
523 ls
->constants
.push_tail(lv
);
529 /* The remaining variables that are not loop invariant might be loop
530 * induction variables.
532 foreach_in_list_safe(loop_variable
, lv
, &ls
->variables
) {
533 /* If there is more than one assignment to a variable, it cannot be a
534 * loop induction variable. This isn't strictly true, but this is a
535 * very simple induction variable detector, and it can't handle more
538 if (lv
->num_assignments
> 1)
541 /* All of the variables with zero assignments in the loop are loop
542 * invariant, and they should have already been filtered out.
544 assert(lv
->num_assignments
== 1);
545 assert(lv
->first_assignment
!= NULL
);
547 /* The assignment to the variable in the loop must be unconditional and
548 * not inside a nested loop.
550 if (lv
->conditional_or_nested_assignment
)
553 /* Basic loop induction variables have a single assignment in the loop
554 * that has the form 'VAR = VAR + i' or 'VAR = VAR - i' where i is a
557 ir_rvalue
*const inc
=
558 get_basic_induction_increment(lv
->first_assignment
, ls
->var_hash
);
563 ls
->induction_variables
.push_tail(lv
);
567 /* Search the loop terminating conditions for those of the form 'i < c'
568 * where i is a loop induction variable, c is a constant, and < is any
569 * relative operator. From each of these we can infer an iteration count.
570 * Also figure out which terminator (if any) produces the smallest
571 * iteration count--this is the limiting terminator.
573 foreach_in_list(loop_terminator
, t
, &ls
->terminators
) {
574 ir_if
*if_stmt
= t
->ir
;
576 /* If-statements can be either 'if (expr)' or 'if (deref)'. We only care
577 * about the former here.
579 ir_expression
*cond
= if_stmt
->condition
->as_expression();
583 switch (cond
->operation
) {
585 case ir_binop_greater
:
586 case ir_binop_lequal
:
587 case ir_binop_gequal
: {
588 /* The expressions that we care about will either be of the form
589 * 'counter < limit' or 'limit < counter'. Figure out which is
592 ir_rvalue
*counter
= cond
->operands
[0]->as_dereference_variable();
593 ir_constant
*limit
= cond
->operands
[1]->as_constant();
594 enum ir_expression_operation cmp
= cond
->operation
;
597 counter
= cond
->operands
[1]->as_dereference_variable();
598 limit
= cond
->operands
[0]->as_constant();
601 case ir_binop_less
: cmp
= ir_binop_greater
; break;
602 case ir_binop_greater
: cmp
= ir_binop_less
; break;
603 case ir_binop_lequal
: cmp
= ir_binop_gequal
; break;
604 case ir_binop_gequal
: cmp
= ir_binop_lequal
; break;
605 default: assert(!"Should not get here.");
609 if ((counter
== NULL
) || (limit
== NULL
))
612 ir_variable
*var
= counter
->variable_referenced();
614 ir_rvalue
*init
= find_initial_value(ir
, var
);
616 loop_variable
*lv
= ls
->get(var
);
617 if (lv
!= NULL
&& lv
->is_induction_var()) {
618 t
->iterations
= calculate_iterations(init
, limit
, lv
->increment
,
619 cmp
, t
->continue_from_then
);
621 if (incremented_before_terminator(ir
, var
, t
->ir
)) {
625 if (t
->iterations
>= 0 &&
626 (ls
->limiting_terminator
== NULL
||
627 t
->iterations
< ls
->limiting_terminator
->iterations
)) {
628 ls
->limiting_terminator
= t
;
639 return visit_continue
;
643 loop_analysis::visit_enter(ir_if
*ir
)
647 if (!this->state
.is_empty())
648 this->if_statement_depth
++;
650 return visit_continue
;
654 loop_analysis::visit_leave(ir_if
*ir
)
658 if (!this->state
.is_empty())
659 this->if_statement_depth
--;
661 return visit_continue
;
665 loop_analysis::visit_enter(ir_assignment
*ir
)
667 /* If we're not somewhere inside a loop, there's nothing to do.
669 if (this->state
.is_empty())
670 return visit_continue_with_parent
;
672 this->current_assignment
= ir
;
674 return visit_continue
;
678 loop_analysis::visit_leave(ir_assignment
*ir
)
680 /* Since the visit_enter exits with visit_continue_with_parent for this
681 * case, the loop state stack should never be empty here.
683 assert(!this->state
.is_empty());
685 assert(this->current_assignment
== ir
);
686 this->current_assignment
= NULL
;
688 return visit_continue
;
692 class examine_rhs
: public ir_hierarchical_visitor
{
694 examine_rhs(hash_table
*loop_variables
)
696 this->only_uses_loop_constants
= true;
697 this->loop_variables
= loop_variables
;
700 virtual ir_visitor_status
visit(ir_dereference_variable
*ir
)
702 hash_entry
*entry
= _mesa_hash_table_search(this->loop_variables
,
704 loop_variable
*lv
= entry
? (loop_variable
*) entry
->data
: NULL
;
708 if (lv
->is_loop_constant()) {
709 return visit_continue
;
711 this->only_uses_loop_constants
= false;
716 hash_table
*loop_variables
;
717 bool only_uses_loop_constants
;
722 all_expression_operands_are_loop_constant(ir_rvalue
*ir
, hash_table
*variables
)
724 examine_rhs
v(variables
);
728 return v
.only_uses_loop_constants
;
733 get_basic_induction_increment(ir_assignment
*ir
, hash_table
*var_hash
)
735 /* The RHS must be a binary expression.
737 ir_expression
*const rhs
= ir
->rhs
->as_expression();
739 || ((rhs
->operation
!= ir_binop_add
)
740 && (rhs
->operation
!= ir_binop_sub
)))
743 /* One of the of operands of the expression must be the variable assigned.
744 * If the operation is subtraction, the variable in question must be the
747 ir_variable
*const var
= ir
->lhs
->variable_referenced();
749 ir_variable
*const op0
= rhs
->operands
[0]->variable_referenced();
750 ir_variable
*const op1
= rhs
->operands
[1]->variable_referenced();
752 if (((op0
!= var
) && (op1
!= var
))
753 || ((op1
== var
) && (rhs
->operation
== ir_binop_sub
)))
756 ir_rvalue
*inc
= (op0
== var
) ? rhs
->operands
[1] : rhs
->operands
[0];
758 if (inc
->as_constant() == NULL
) {
759 ir_variable
*const inc_var
= inc
->variable_referenced();
760 if (inc_var
!= NULL
) {
761 hash_entry
*entry
= _mesa_hash_table_search(var_hash
, inc_var
);
762 loop_variable
*lv
= entry
? (loop_variable
*) entry
->data
: NULL
;
764 if (lv
== NULL
|| !lv
->is_loop_constant()) {
772 if ((inc
!= NULL
) && (rhs
->operation
== ir_binop_sub
)) {
773 void *mem_ctx
= ralloc_parent(ir
);
775 inc
= new(mem_ctx
) ir_expression(ir_unop_neg
,
777 inc
->clone(mem_ctx
, NULL
),
786 * Detect whether an if-statement is a loop terminating condition, if so
787 * add it to the list of loop terminators.
789 * Detects if-statements of the form
791 * (if (expression bool ...) (...then_instrs...break))
795 * (if (expression bool ...) ... (...else_instrs...break))
798 try_add_loop_terminator(loop_variable_state
*ls
, ir_if
*ir
)
800 ir_instruction
*inst
= (ir_instruction
*) ir
->then_instructions
.get_tail();
801 ir_instruction
*else_inst
=
802 (ir_instruction
*) ir
->else_instructions
.get_tail();
804 if (is_break(inst
) || is_break(else_inst
))
805 ls
->insert(ir
, is_break(else_inst
));
810 analyze_loop_variables(exec_list
*instructions
)
812 loop_state
*loops
= new loop_state
;
813 loop_analysis
v(loops
);