1 /* -*- c++ -*- */
2 /*
3  * Copyright © 2010 Intel Corporation
4  *
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:
11  *
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
14  * Software.
15  *
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.
23  */
24 
25 #pragma once
26 #ifndef LOOP_ANALYSIS_H
27 #define LOOP_ANALYSIS_H
28 
29 #include "ir.h"
30 #include "glsl_types.h"
31 #include "program/hash_table.h"
32 
33 /**
34  * Analyze and classify all variables used in all loops in the instruction list
35  */
36 extern class loop_state *
37 analyze_loop_variables(exec_list *instructions);
38 
39 
40 /**
41  * Fill in loop control fields
42  *
43  * Based on analysis of loop variables, this function tries to remove
44  * redundant sequences in the loop of the form
45  *
46  *  (if (expression bool ...) (break))
47  *
48  * For example, if it is provable that one loop exit condition will
49  * always be satisfied before another, the unnecessary exit condition will be
50  * removed.
51  */
52 extern bool
53 set_loop_controls(exec_list *instructions, loop_state *ls);
54 
55 
56 extern bool
57 unroll_loops(exec_list *instructions, loop_state *ls,
58              const struct gl_shader_compiler_options *options);
59 
60 ir_rvalue *
61 find_initial_value(ir_loop *loop, ir_variable *var, ir_instruction **out_containing_ir);
62 
63 int
64 calculate_iterations(ir_rvalue *from, ir_rvalue *to, ir_rvalue *increment,
65 		     enum ir_expression_operation op);
66 
67 
68 /**
69  * Tracking for all variables used in a loop
70  */
71 class loop_variable_state : public exec_node {
72 public:
73    class loop_variable *get(const ir_variable *);
74    class loop_variable *insert(ir_variable *);
75    class loop_variable *get_or_insert(ir_variable *, bool in_assignee);
76    class loop_terminator *insert(ir_if *);
77 
78 
79    /**
80     * Variables that have not yet been classified
81     */
82    exec_list variables;
83 
84    /**
85     * Variables whose values are constant within the body of the loop
86     *
87     * This list contains \c loop_variable objects.
88     */
89    exec_list constants;
90 
91    /**
92     * Induction variables for this loop
93     *
94     * This list contains \c loop_variable objects.
95     */
96    exec_list induction_variables;
97    int private_induction_variable_count;
98 
99    /**
100     * Simple if-statements that lead to the termination of the loop
101     *
102     * This list contains \c loop_terminator objects.
103     *
104     * \sa is_loop_terminator
105     */
106    exec_list terminators;
107 
108    /**
109     * If any of the terminators in \c terminators leads to termination of the
110     * loop after a constant number of iterations, this is the terminator that
111     * leads to termination after the smallest number of iterations.  Otherwise
112     * NULL.
113     */
114    loop_terminator *limiting_terminator;
115 
116    /**
117     * Hash table containing all variables accessed in this loop
118     */
119    hash_table *var_hash;
120 
121    /**
122     * Number of ir_loop_jump instructions that operate on this loop
123     */
124    unsigned num_loop_jumps;
125 
126    /**
127     * Whether this loop contains any function calls.
128     */
129    bool contains_calls;
130 
loop_variable_state()131    loop_variable_state()
132    {
133       this->num_loop_jumps = 0;
134       this->contains_calls = false;
135       this->var_hash = hash_table_ctor(0, hash_table_pointer_hash,
136 				       hash_table_pointer_compare);
137       this->limiting_terminator = NULL;
138    }
139 
~loop_variable_state()140    ~loop_variable_state()
141    {
142       hash_table_dtor(this->var_hash);
143    }
144 
145    DECLARE_RALLOC_CXX_OPERATORS(loop_variable_state)
146 };
147 
148 
149 class loop_variable : public exec_node {
150 public:
151    /** The variable in question. */
152    ir_variable *var;
153 
154    /** Is the variable read in the loop before it is written? */
155    bool read_before_write;
156 
157    /** Are all variables in the RHS of the assignment loop constants? */
158    bool rhs_clean;
159 
160    /**
161     * Is there an assignment to the variable that is conditional, or inside a
162     * nested loop?
163     */
164    bool conditional_or_nested_assignment;
165 
166    /** Reference to the first assignment to the variable in the loop body. */
167    ir_assignment *first_assignment;
168 
169    /** Reference to initial value outside of the loop. */
170    ir_rvalue *initial_value;
171    /** IR that assigned the initial value. */
172    ir_instruction *initial_value_ir;
173 
174    /** Number of assignments to the variable in the loop body. */
175    unsigned num_assignments;
176 
177    /**
178     * Increment value for a loop induction variable
179     *
180     * If this is a loop induction variable, the amount by which the variable
181     * is incremented on each iteration through the loop.
182     *
183     * If this is not a loop induction variable, NULL.
184     */
185    ir_rvalue *increment;
186 
187 
is_induction_var()188    inline bool is_induction_var() const
189    {
190       /* Induction variables always have a non-null increment, and vice
191        * versa.
192        */
193       return this->increment != NULL;
194    }
195 
196 
is_loop_constant()197    inline bool is_loop_constant() const
198    {
199       const bool is_const = (this->num_assignments == 0)
200          || (((this->num_assignments == 1)
201 	     && !this->conditional_or_nested_assignment
202 	     && !this->read_before_write
203              && this->rhs_clean) || this->var->data.read_only);
204 
205       /* If the RHS of *the* assignment is clean, then there must be exactly
206        * one assignment of the variable.
207        */
208       assert((this->rhs_clean && (this->num_assignments == 1))
209 	     || !this->rhs_clean);
210 
211       return is_const;
212    }
213 
214    void record_reference(bool in_assignee,
215                          bool in_conditional_code_or_nested_loop,
216                          ir_assignment *current_assignment);
217 };
218 
219 
220 class loop_terminator : public exec_node {
221 public:
loop_terminator()222    loop_terminator()
223       : ir(NULL), iterations(-1)
224    {
225    }
226 
227    /**
228     * Statement which terminates the loop.
229     */
230    ir_if *ir;
231 
232    /**
233     * The number of iterations after which the terminator is known to
234     * terminate the loop (if that is a fixed value).  Otherwise -1.
235     */
236    int iterations;
237 };
238 
239 
240 class loop_state {
241 public:
242    ~loop_state();
243 
244    /**
245     * Get the loop variable state data for a particular loop
246     */
247    loop_variable_state *get(const ir_loop *);
248 
249    loop_variable_state *insert(ir_loop *ir);
250 
251    loop_variable_state* get_for_inductor (const ir_variable*);
252    bool insert_inductor(loop_variable* loopvar, loop_variable_state* state, ir_loop* loop);
253    void insert_non_inductor(ir_variable *var);
254    void insert_variable(ir_variable *var);
255    void reference_variable(ir_variable *var, bool assignment);
256 
257    bool loop_found;
258 
259 private:
260    loop_state();
261 
262    /**
263     * Hash table containing all loops that have been analyzed.
264     */
265    hash_table *ht;
266 
267    /**
268     * Hash table from ir_variables to loop state, for induction variables.
269     */
270    hash_table *ht_inductors;
271    hash_table *ht_non_inductors;
272    hash_table *ht_variables;
273 
274 
275    void *mem_ctx;
276 
277    friend loop_state *analyze_loop_variables(exec_list *instructions);
278 };
279 
280 #endif /* LOOP_ANALYSIS_H */
281