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()) {
106 new(mem_ctx
) ir_expression(ir_unop_f2i
, glsl_type::int_type
, iter
,
109 iter
= cast
->constant_expression_value();
112 int iter_value
= iter
->get_int_component(0);
114 /* Make sure that the calculated number of iterations satisfies the exit
115 * condition. This is needed to catch off-by-one errors and some types of
116 * ill-formed loops. For example, we need to detect that the following
117 * loop does not have a maximum iteration count.
119 * for (float x = 0.0; x != 0.9; x += 0.2)
122 const int bias
[] = { -1, 0, 1 };
123 bool valid_loop
= false;
125 for (unsigned i
= 0; i
< Elements(bias
); i
++) {
126 iter
= (increment
->type
->is_integer())
127 ? new(mem_ctx
) ir_constant(iter_value
+ bias
[i
])
128 : new(mem_ctx
) ir_constant(float(iter_value
+ bias
[i
]));
130 ir_expression
*const mul
=
131 new(mem_ctx
) ir_expression(ir_binop_mul
, increment
->type
, iter
,
134 ir_expression
*const add
=
135 new(mem_ctx
) ir_expression(ir_binop_add
, mul
->type
, mul
, from
);
137 ir_expression
*const cmp
=
138 new(mem_ctx
) ir_expression(op
, glsl_type::bool_type
, add
, to
);
140 ir_constant
*const cmp_result
= cmp
->constant_expression_value();
142 assert(cmp_result
!= NULL
);
143 if (cmp_result
->get_bool_component(0)) {
144 iter_value
+= bias
[i
];
150 ralloc_free(mem_ctx
);
151 return (valid_loop
) ? iter_value
: -1;
156 class loop_control_visitor
: public ir_hierarchical_visitor
{
158 loop_control_visitor(loop_state
*state
)
161 this->progress
= false;
164 virtual ir_visitor_status
visit_leave(ir_loop
*ir
);
171 } /* anonymous namespace */
174 loop_control_visitor::visit_leave(ir_loop
*ir
)
176 loop_variable_state
*const ls
= this->state
->get(ir
);
178 /* If we've entered a loop that hasn't been analyzed, something really,
179 * really bad has happened.
183 return visit_continue
;
186 if (ls
->limiting_terminator
!= NULL
) {
187 /* If the limiting terminator has an iteration count of zero, then we've
188 * proven that the loop cannot run, so delete it.
190 int iterations
= ls
->limiting_terminator
->iterations
;
191 if (iterations
== 0) {
193 this->progress
= true;
194 return visit_continue
;
197 /* If the limiting terminator has a lower iteration count than the
198 * normative loop bound (if any), then make this a normatively bounded
199 * loop with the new iteration count.
201 if (ir
->normative_bound
< 0 || iterations
< ir
->normative_bound
)
202 ir
->normative_bound
= iterations
;
205 /* Remove the conditional break statements associated with all terminators
206 * that are associated with a fixed iteration count; the normative bound
207 * will take care of terminating the loop.
209 foreach_list(node
, &ls
->terminators
) {
210 loop_terminator
*t
= (loop_terminator
*) node
;
212 if (t
->iterations
< 0)
217 assert(ls
->num_loop_jumps
> 0);
218 ls
->num_loop_jumps
--;
220 this->progress
= true;
223 return visit_continue
;
228 set_loop_controls(exec_list
*instructions
, loop_state
*ls
)
230 loop_control_visitor
v(ls
);