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 "program/hash_table.h"
31
32/**
33 * Analyze and classify all variables used in all loops in the instruction list
34 */
35extern class loop_state *
36analyze_loop_variables(exec_list *instructions);
37
38
39/**
40 * Fill in loop control fields
41 *
42 * Based on analysis of loop variables, this function tries to remove sequences
43 * in the loop of the form
44 *
45 *  (if (expression bool ...) (break))
46 *
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.
49 *
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
53 * removed.
54 */
55extern bool
56set_loop_controls(exec_list *instructions, loop_state *ls);
57
58
59extern bool
60unroll_loops(exec_list *instructions, loop_state *ls, unsigned max_iterations);
61
62
63/**
64 * Tracking for all variables used in a loop
65 */
66class loop_variable_state : public exec_node {
67public:
68   class loop_variable *get(const ir_variable *);
69   class loop_variable *insert(ir_variable *);
70   class loop_terminator *insert(ir_if *);
71
72
73   /**
74    * Loop whose variable state is being tracked by this structure
75    */
76   ir_loop *loop;
77
78   /**
79    * Variables that have not yet been classified
80    */
81   exec_list variables;
82
83   /**
84    * Variables whose values are constant within the body of the loop
85    *
86    * This list contains \c loop_variable objects.
87    */
88   exec_list constants;
89
90   /**
91    * Induction variables for this loop
92    *
93    * This list contains \c loop_variable objects.
94    */
95   exec_list induction_variables;
96
97   /**
98    * Simple if-statements that lead to the termination of the loop
99    *
100    * This list contains \c loop_terminator objects.
101    *
102    * \sa is_loop_terminator
103    */
104   exec_list terminators;
105
106   /**
107    * Hash table containing all variables accessed in this loop
108    */
109   hash_table *var_hash;
110
111   /**
112    * Maximum number of loop iterations.
113    *
114    * If this value is negative, then the loop may be infinite.  This actually
115    * means that analysis was unable to determine an upper bound on the number
116    * of loop iterations.
117    */
118   int max_iterations;
119
120   /**
121    * Number of ir_loop_jump instructions that operate on this loop
122    */
123   unsigned num_loop_jumps;
124
125   /**
126    * Whether this loop contains any function calls.
127    */
128   bool contains_calls;
129
130   loop_variable_state()
131   {
132      this->max_iterations = -1;
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   }
138
139   ~loop_variable_state()
140   {
141      hash_table_dtor(this->var_hash);
142   }
143
144   static void* operator new(size_t size, void *ctx)
145   {
146      void *lvs = ralloc_size(ctx, size);
147      assert(lvs != NULL);
148
149      ralloc_set_destructor(lvs, (void (*)(void*)) destructor);
150
151      return lvs;
152   }
153
154private:
155   static void
156   destructor(loop_variable_state *lvs)
157   {
158      lvs->~loop_variable_state();
159   }
160};
161
162
163class loop_variable : public exec_node {
164public:
165   /** The variable in question. */
166   ir_variable *var;
167
168   /** Is the variable read in the loop before it is written? */
169   bool read_before_write;
170
171   /** Are all variables in the RHS of the assignment loop constants? */
172   bool rhs_clean;
173
174   /** Is there an assignment to the variable that is conditional? */
175   bool conditional_assignment;
176
177   /** Reference to the first assignment to the variable in the loop body. */
178   ir_assignment *first_assignment;
179
180   /** Number of assignments to the variable in the loop body. */
181   unsigned num_assignments;
182
183   /**
184    * Increment values for loop induction variables
185    *
186    * Loop induction variables have a single increment of the form
187    * \c b * \c biv + \c c, where \c b and \c c are loop constants and \c i
188    * is a basic loop induction variable.
189    *
190    * If \c iv_scale is \c NULL, 1 is used.  If \c biv is the same as \c var,
191    * then \c var is a basic loop induction variable.
192    */
193   /*@{*/
194   ir_rvalue *iv_scale;
195   ir_variable *biv;
196   ir_rvalue *increment;
197   /*@}*/
198
199
200   inline bool is_loop_constant() const
201   {
202      const bool is_const = (this->num_assignments == 0)
203	 || ((this->num_assignments == 1)
204	     && !this->conditional_assignment
205	     && !this->read_before_write
206	     && this->rhs_clean);
207
208      /* If the RHS of *the* assignment is clean, then there must be exactly
209       * one assignment of the variable.
210       */
211      assert((this->rhs_clean && (this->num_assignments == 1))
212	     || !this->rhs_clean);
213
214      /* Variables that are marked read-only *MUST* be loop constant.
215       */
216      assert(!this->var->read_only || (this->var->read_only && is_const));
217
218      return is_const;
219   }
220};
221
222
223class loop_terminator : public exec_node {
224public:
225   ir_if *ir;
226};
227
228
229class loop_state {
230public:
231   ~loop_state();
232
233   /**
234    * Get the loop variable state data for a particular loop
235    */
236   loop_variable_state *get(const ir_loop *);
237
238   loop_variable_state *insert(ir_loop *ir);
239
240   bool loop_found;
241
242private:
243   loop_state();
244
245   /**
246    * Hash table containing all loops that have been analyzed.
247    */
248   hash_table *ht;
249
250   void *mem_ctx;
251
252   friend class loop_analysis;
253};
254
255#endif /* LOOP_ANALYSIS_H */
256