3 * Copyright © 2010 Intel Corporation
5 * Permission is hereby granted, free of charge, to any person obtaining a
6 * copy of this software and associated documentation files (the "Software"),
7 * to deal in the Software without restriction, including without limitation
8 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9 * and/or sell copies of the Software, and to permit persons to whom the
10 * Software is furnished to do so, subject to the following conditions:
12 * The above copyright notice and this permission notice (including the next
13 * paragraph) shall be included in all copies or substantial portions of the
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
22 * DEALINGS IN THE SOFTWARE.
26 #ifndef LOOP_ANALYSIS_H
27 #define LOOP_ANALYSIS_H
30 #include "program/hash_table.h"
33 * Analyze and classify all variables used in all loops in the instruction list
35 extern class loop_state
*
36 analyze_loop_variables(exec_list
*instructions
);
40 * Fill in loop control fields
42 * Based on analysis of loop variables, this function tries to remove sequences
43 * in the loop of the form
45 * (if (expression bool ...) (break))
47 * and fill in the \c ir_loop::from, \c ir_loop::to, and \c ir_loop::counter
48 * fields of the \c ir_loop.
50 * In this process, some conditional break-statements may be eliminated
51 * altogether. For example, if it is provable that one loop exit condition will
52 * always be satisfied before another, the unnecessary exit condition will be
56 set_loop_controls(exec_list
*instructions
, loop_state
*ls
);
60 unroll_loops(exec_list
*instructions
, loop_state
*ls
, unsigned max_iterations
);
64 * Tracking for all variables used in a loop
66 class loop_variable_state
: public exec_node
{
68 class loop_variable
*get(const ir_variable
*);
69 class loop_variable
*insert(ir_variable
*);
70 class loop_variable
*get_or_insert(ir_variable
*, bool in_assignee
);
71 class loop_terminator
*insert(ir_if
*);
75 * Variables that have not yet been classified
80 * Variables whose values are constant within the body of the loop
82 * This list contains \c loop_variable objects.
87 * Induction variables for this loop
89 * This list contains \c loop_variable objects.
91 exec_list induction_variables
;
94 * Simple if-statements that lead to the termination of the loop
96 * This list contains \c loop_terminator objects.
98 * \sa is_loop_terminator
100 exec_list terminators
;
103 * Hash table containing all variables accessed in this loop
105 hash_table
*var_hash
;
108 * Maximum number of loop iterations.
110 * If this value is negative, then the loop may be infinite. This actually
111 * means that analysis was unable to determine an upper bound on the number
112 * of loop iterations.
117 * Number of ir_loop_jump instructions that operate on this loop
119 unsigned num_loop_jumps
;
122 * Whether this loop contains any function calls.
126 loop_variable_state()
128 this->max_iterations
= -1;
129 this->num_loop_jumps
= 0;
130 this->contains_calls
= false;
131 this->var_hash
= hash_table_ctor(0, hash_table_pointer_hash
,
132 hash_table_pointer_compare
);
135 ~loop_variable_state()
137 hash_table_dtor(this->var_hash
);
140 static void* operator new(size_t size
, void *ctx
)
142 void *lvs
= ralloc_size(ctx
, size
);
145 ralloc_set_destructor(lvs
, (void (*)(void*)) destructor
);
152 destructor(loop_variable_state
*lvs
)
154 lvs
->~loop_variable_state();
159 class loop_variable
: public exec_node
{
161 /** The variable in question. */
164 /** Is the variable read in the loop before it is written? */
165 bool read_before_write
;
167 /** Are all variables in the RHS of the assignment loop constants? */
171 * Is there an assignment to the variable that is conditional, or inside a
174 bool conditional_or_nested_assignment
;
176 /** Reference to the first assignment to the variable in the loop body. */
177 ir_assignment
*first_assignment
;
179 /** Number of assignments to the variable in the loop body. */
180 unsigned num_assignments
;
183 * Increment values for loop induction variables
185 * Loop induction variables have a single increment of the form
186 * \c b * \c biv + \c c, where \c b and \c c are loop constants and \c i
187 * is a basic loop induction variable.
189 * If \c iv_scale is \c NULL, 1 is used. If \c biv is the same as \c var,
190 * then \c var is a basic loop induction variable.
195 ir_rvalue
*increment
;
199 inline bool is_loop_constant() const
201 const bool is_const
= (this->num_assignments
== 0)
202 || ((this->num_assignments
== 1)
203 && !this->conditional_or_nested_assignment
204 && !this->read_before_write
207 /* If the RHS of *the* assignment is clean, then there must be exactly
208 * one assignment of the variable.
210 assert((this->rhs_clean
&& (this->num_assignments
== 1))
211 || !this->rhs_clean
);
213 /* Variables that are marked read-only *MUST* be loop constant.
215 assert(!this->var
->read_only
|| (this->var
->read_only
&& is_const
));
220 void record_reference(bool in_assignee
,
221 bool in_conditional_code_or_nested_loop
,
222 ir_assignment
*current_assignment
);
226 class loop_terminator
: public exec_node
{
237 * Get the loop variable state data for a particular loop
239 loop_variable_state
*get(const ir_loop
*);
241 loop_variable_state
*insert(ir_loop
*ir
);
249 * Hash table containing all loops that have been analyzed.
255 friend loop_state
*analyze_loop_variables(exec_list
*instructions
);
258 #endif /* LOOP_ANALYSIS_H */