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   loop_variable_state()
126   {
127      this->max_iterations = -1;
128      this->num_loop_jumps = 0;
129      this->var_hash = hash_table_ctor(0, hash_table_pointer_hash,
130				       hash_table_pointer_compare);
131   }
132
133   ~loop_variable_state()
134   {
135      hash_table_dtor(this->var_hash);
136   }
137};
138
139
140class loop_variable : public exec_node {
141public:
142   /** The variable in question. */
143   ir_variable *var;
144
145   /** Is the variable read in the loop before it is written? */
146   bool read_before_write;
147
148   /** Are all variables in the RHS of the assignment loop constants? */
149   bool rhs_clean;
150
151   /** Is there an assignment to the variable that is conditional? */
152   bool conditional_assignment;
153
154   /** Reference to the first assignment to the variable in the loop body. */
155   ir_assignment *first_assignment;
156
157   /** Number of assignments to the variable in the loop body. */
158   unsigned num_assignments;
159
160   /**
161    * Increment values for loop induction variables
162    *
163    * Loop induction variables have a single increment of the form
164    * \c b * \c biv + \c c, where \c b and \c c are loop constants and \c i
165    * is a basic loop induction variable.
166    *
167    * If \c iv_scale is \c NULL, 1 is used.  If \c biv is the same as \c var,
168    * then \c var is a basic loop induction variable.
169    */
170   /*@{*/
171   ir_rvalue *iv_scale;
172   ir_variable *biv;
173   ir_rvalue *increment;
174   /*@}*/
175
176
177   inline bool is_loop_constant() const
178   {
179      const bool is_const = (this->num_assignments == 0)
180	 || ((this->num_assignments == 1)
181	     && !this->conditional_assignment
182	     && !this->read_before_write
183	     && this->rhs_clean);
184
185      /* If the RHS of *the* assignment is clean, then there must be exactly
186       * one assignment of the variable.
187       */
188      assert((this->rhs_clean && (this->num_assignments == 1))
189	     || !this->rhs_clean);
190
191      /* Variables that are marked read-only *MUST* be loop constant.
192       */
193      assert(!this->var->read_only || (this->var->read_only && is_const));
194
195      return is_const;
196   }
197};
198
199
200class loop_terminator : public exec_node {
201public:
202   ir_if *ir;
203};
204
205
206class loop_state {
207public:
208   ~loop_state();
209
210   /**
211    * Get the loop variable state data for a particular loop
212    */
213   loop_variable_state *get(const ir_loop *);
214
215   loop_variable_state *insert(ir_loop *ir);
216
217private:
218   loop_state();
219
220   /**
221    * Hash table containing all loops that have been analyzed.
222    */
223   hash_table *ht;
224
225   void *mem_ctx;
226
227   friend class loop_analysis;
228};
229
230#endif /* LOOP_ANALYSIS_H */
231