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.
25 #include "main/compiler.h"
26 #include "glsl_types.h"
27 #include "loop_analysis.h"
28 #include "ir_hierarchical_visitor.h"
31 * Find an initializer of a variable outside a loop
33 * Works backwards from the loop to find the pre-loop value of the variable.
34 * This is used, for example, to find the initial value of loop induction
37 * \param loop Loop where \c var is an induction variable
38 * \param var Variable whose initializer is to be found
41 * The \c ir_rvalue assigned to the variable outside the loop. May return
42 * \c NULL if no initializer can be found.
45 find_initial_value(ir_loop
*loop
, ir_variable
*var
)
47 for (exec_node
*node
= loop
->prev
;
48 !node
->is_head_sentinel();
50 ir_instruction
*ir
= (ir_instruction
*) node
;
52 switch (ir
->ir_type
) {
55 case ir_type_loop_jump
:
60 case ir_type_function
:
61 case ir_type_function_signature
:
62 assert(!"Should not get here.");
65 case ir_type_assignment
: {
66 ir_assignment
*assign
= ir
->as_assignment();
67 ir_variable
*assignee
= assign
->lhs
->whole_variable_referenced();
70 return (assign
->condition
!= NULL
) ? NULL
: assign
->rhs
;
85 calculate_iterations(ir_rvalue
*from
, ir_rvalue
*to
, ir_rvalue
*increment
,
86 enum ir_expression_operation op
)
88 if (from
== NULL
|| to
== NULL
|| increment
== NULL
)
91 void *mem_ctx
= ralloc_context(NULL
);
93 ir_expression
*const sub
=
94 new(mem_ctx
) ir_expression(ir_binop_sub
, from
->type
, to
, from
);
96 ir_expression
*const div
=
97 new(mem_ctx
) ir_expression(ir_binop_div
, sub
->type
, sub
, increment
);
99 ir_constant
*iter
= div
->constant_expression_value();
104 if (!iter
->type
->is_integer()) {
105 const ir_expression_operation op
= iter
->type
->is_double()
106 ? ir_unop_d2i
: ir_unop_f2i
;
108 new(mem_ctx
) ir_expression(op
, glsl_type::int_type
, iter
, NULL
);
110 iter
= cast
->constant_expression_value();
113 int iter_value
= iter
->get_int_component(0);
115 /* Make sure that the calculated number of iterations satisfies the exit
116 * condition. This is needed to catch off-by-one errors and some types of
117 * ill-formed loops. For example, we need to detect that the following
118 * loop does not have a maximum iteration count.
120 * for (float x = 0.0; x != 0.9; x += 0.2)
123 const int bias
[] = { -1, 0, 1 };
124 bool valid_loop
= false;
126 for (unsigned i
= 0; i
< Elements(bias
); i
++) {
127 /* Increment may be of type int, uint or float. */
128 switch (increment
->type
->base_type
) {
130 iter
= new(mem_ctx
) ir_constant(iter_value
+ bias
[i
]);
133 iter
= new(mem_ctx
) ir_constant(unsigned(iter_value
+ bias
[i
]));
135 case GLSL_TYPE_FLOAT
:
136 iter
= new(mem_ctx
) ir_constant(float(iter_value
+ bias
[i
]));
138 case GLSL_TYPE_DOUBLE
:
139 iter
= new(mem_ctx
) ir_constant(double(iter_value
+ bias
[i
]));
142 unreachable(!"Unsupported type for loop iterator.");
145 ir_expression
*const mul
=
146 new(mem_ctx
) ir_expression(ir_binop_mul
, increment
->type
, iter
,
149 ir_expression
*const add
=
150 new(mem_ctx
) ir_expression(ir_binop_add
, mul
->type
, mul
, from
);
152 ir_expression
*const cmp
=
153 new(mem_ctx
) ir_expression(op
, glsl_type::bool_type
, add
, to
);
155 ir_constant
*const cmp_result
= cmp
->constant_expression_value();
157 assert(cmp_result
!= NULL
);
158 if (cmp_result
->get_bool_component(0)) {
159 iter_value
+= bias
[i
];
165 ralloc_free(mem_ctx
);
166 return (valid_loop
) ? iter_value
: -1;
171 class loop_control_visitor
: public ir_hierarchical_visitor
{
173 loop_control_visitor(loop_state
*state
)
176 this->progress
= false;
179 virtual ir_visitor_status
visit_leave(ir_loop
*ir
);
186 } /* anonymous namespace */
189 loop_control_visitor::visit_leave(ir_loop
*ir
)
191 loop_variable_state
*const ls
= this->state
->get(ir
);
193 /* If we've entered a loop that hasn't been analyzed, something really,
194 * really bad has happened.
198 return visit_continue
;
201 if (ls
->limiting_terminator
!= NULL
) {
202 /* If the limiting terminator has an iteration count of zero, then we've
203 * proven that the loop cannot run, so delete it.
205 int iterations
= ls
->limiting_terminator
->iterations
;
206 if (iterations
== 0) {
208 this->progress
= true;
209 return visit_continue
;
213 /* Remove the conditional break statements associated with all terminators
214 * that are associated with a fixed iteration count, except for the one
215 * associated with the limiting terminator--that one needs to stay, since
216 * it terminates the loop. Exception: if the loop still has a normative
217 * bound, then that terminates the loop, so we don't even need the limiting
220 foreach_in_list(loop_terminator
, t
, &ls
->terminators
) {
221 if (t
->iterations
< 0)
224 if (t
!= ls
->limiting_terminator
) {
227 assert(ls
->num_loop_jumps
> 0);
228 ls
->num_loop_jumps
--;
230 this->progress
= true;
234 return visit_continue
;
239 set_loop_controls(exec_list
*instructions
, loop_state
*ls
)
241 loop_control_visitor
v(ls
);