ScalarEvolution.h revision b7ef72963b2215ca23c27fa8ea777bada06994d0 
1//===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// The ScalarEvolution class is an LLVM pass which can be used to analyze and
11// catagorize scalar expressions in loops.  It specializes in recognizing
12// general induction variables, representing them with the abstract and opaque
13// SCEV class.  Given this analysis, trip counts of loops and other important
14// properties can be obtained.
15//
16// This analysis is primarily useful for induction variable substitution and
17// strength reduction.
18//
19//===----------------------------------------------------------------------===//
20
21#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H
22#define LLVM_ANALYSIS_SCALAREVOLUTION_H
23
24#include "llvm/Pass.h"
25#include "llvm/Analysis/LoopInfo.h"
26#include "llvm/Support/DataTypes.h"
27#include <iosfwd>
28
29namespace llvm {
30  class APInt;
31  class ConstantInt;
32  class Type;
33  class SCEVHandle;
34  class ScalarEvolution;
35  class TargetData;
36
37  /// SCEV - This class represent an analyzed expression in the program.  These
38  /// are reference counted opaque objects that the client is not allowed to
39  /// do much with directly.
40  ///
41  class SCEV {
42    const unsigned SCEVType;      // The SCEV baseclass this node corresponds to
43    mutable unsigned RefCount;
44
45    friend class SCEVHandle;
46    void addRef() const { ++RefCount; }
47    void dropRef() const {
48      if (--RefCount == 0)
49        delete this;
50    }
51
52    SCEV(const SCEV &);            // DO NOT IMPLEMENT
53    void operator=(const SCEV &);  // DO NOT IMPLEMENT
54  protected:
55    virtual ~SCEV();
56  public:
57    explicit SCEV(unsigned SCEVTy) : SCEVType(SCEVTy), RefCount(0) {}
58
59    unsigned getSCEVType() const { return SCEVType; }
60
61    /// isLoopInvariant - Return true if the value of this SCEV is unchanging in
62    /// the specified loop.
63    virtual bool isLoopInvariant(const Loop *L) const = 0;
64
65    /// hasComputableLoopEvolution - Return true if this SCEV changes value in a
66    /// known way in the specified loop.  This property being true implies that
67    /// the value is variant in the loop AND that we can emit an expression to
68    /// compute the value of the expression at any particular loop iteration.
69    virtual bool hasComputableLoopEvolution(const Loop *L) const = 0;
70
71    /// getType - Return the LLVM type of this SCEV expression.
72    ///
73    virtual const Type *getType() const = 0;
74
75    /// isZero - Return true if the expression is a constant zero.
76    ///
77    bool isZero() const;
78
79    /// replaceSymbolicValuesWithConcrete - If this SCEV internally references
80    /// the symbolic value "Sym", construct and return a new SCEV that produces
81    /// the same value, but which uses the concrete value Conc instead of the
82    /// symbolic value.  If this SCEV does not use the symbolic value, it
83    /// returns itself.
84    virtual SCEVHandle
85    replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
86                                      const SCEVHandle &Conc,
87                                      ScalarEvolution &SE) const = 0;
88
89    /// dominates - Return true if elements that makes up this SCEV dominates
90    /// the specified basic block.
91    virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const = 0;
92
93    /// print - Print out the internal representation of this scalar to the
94    /// specified stream.  This should really only be used for debugging
95    /// purposes.
96    virtual void print(raw_ostream &OS) const = 0;
97    void print(std::ostream &OS) const;
98    void print(std::ostream *OS) const { if (OS) print(*OS); }
99
100    /// dump - This method is used for debugging.
101    ///
102    void dump() const;
103  };
104
105  inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) {
106    S.print(OS);
107    return OS;
108  }
109
110  inline std::ostream &operator<<(std::ostream &OS, const SCEV &S) {
111    S.print(OS);
112    return OS;
113  }
114
115  /// SCEVCouldNotCompute - An object of this class is returned by queries that
116  /// could not be answered.  For example, if you ask for the number of
117  /// iterations of a linked-list traversal loop, you will get one of these.
118  /// None of the standard SCEV operations are valid on this class, it is just a
119  /// marker.
120  struct SCEVCouldNotCompute : public SCEV {
121    SCEVCouldNotCompute();
122
123    // None of these methods are valid for this object.
124    virtual bool isLoopInvariant(const Loop *L) const;
125    virtual const Type *getType() const;
126    virtual bool hasComputableLoopEvolution(const Loop *L) const;
127    virtual void print(raw_ostream &OS) const;
128    virtual SCEVHandle
129    replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
130                                      const SCEVHandle &Conc,
131                                      ScalarEvolution &SE) const;
132
133    virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const {
134      return true;
135    }
136
137    /// Methods for support type inquiry through isa, cast, and dyn_cast:
138    static inline bool classof(const SCEVCouldNotCompute *S) { return true; }
139    static bool classof(const SCEV *S);
140  };
141
142  /// SCEVHandle - This class is used to maintain the SCEV object's refcounts,
143  /// freeing the objects when the last reference is dropped.
144  class SCEVHandle {
145    SCEV *S;
146    SCEVHandle();  // DO NOT IMPLEMENT
147  public:
148    SCEVHandle(const SCEV *s) : S(const_cast<SCEV*>(s)) {
149      assert(S && "Cannot create a handle to a null SCEV!");
150      S->addRef();
151    }
152    SCEVHandle(const SCEVHandle &RHS) : S(RHS.S) {
153      S->addRef();
154    }
155    ~SCEVHandle() { S->dropRef(); }
156
157    operator SCEV*() const { return S; }
158
159    SCEV &operator*() const { return *S; }
160    SCEV *operator->() const { return S; }
161
162    bool operator==(SCEV *RHS) const { return S == RHS; }
163    bool operator!=(SCEV *RHS) const { return S != RHS; }
164
165    const SCEVHandle &operator=(SCEV *RHS) {
166      if (S != RHS) {
167        S->dropRef();
168        S = RHS;
169        S->addRef();
170      }
171      return *this;
172    }
173
174    const SCEVHandle &operator=(const SCEVHandle &RHS) {
175      if (S != RHS.S) {
176        S->dropRef();
177        S = RHS.S;
178        S->addRef();
179      }
180      return *this;
181    }
182  };
183
184  template<typename From> struct simplify_type;
185  template<> struct simplify_type<const SCEVHandle> {
186    typedef SCEV* SimpleType;
187    static SimpleType getSimplifiedValue(const SCEVHandle &Node) {
188      return Node;
189    }
190  };
191  template<> struct simplify_type<SCEVHandle>
192    : public simplify_type<const SCEVHandle> {};
193
194  /// ScalarEvolution - This class is the main scalar evolution driver.  Because
195  /// client code (intentionally) can't do much with the SCEV objects directly,
196  /// they must ask this class for services.
197  ///
198  class ScalarEvolution : public FunctionPass {
199    void *Impl;    // ScalarEvolution uses the pimpl pattern
200  public:
201    static char ID; // Pass identification, replacement for typeid
202    ScalarEvolution() : FunctionPass(&ID), Impl(0) {}
203
204    // getTargetData - Return the TargetData object contained in this
205    // ScalarEvolution.
206    const TargetData &getTargetData() const;
207
208    /// getSCEV - Return a SCEV expression handle for the full generality of the
209    /// specified expression.
210    SCEVHandle getSCEV(Value *V) const;
211
212    SCEVHandle getConstant(ConstantInt *V);
213    SCEVHandle getConstant(const APInt& Val);
214    SCEVHandle getTruncateExpr(const SCEVHandle &Op, const Type *Ty);
215    SCEVHandle getZeroExtendExpr(const SCEVHandle &Op, const Type *Ty);
216    SCEVHandle getSignExtendExpr(const SCEVHandle &Op, const Type *Ty);
217    SCEVHandle getAddExpr(std::vector<SCEVHandle> &Ops);
218    SCEVHandle getAddExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) {
219      std::vector<SCEVHandle> Ops;
220      Ops.push_back(LHS);
221      Ops.push_back(RHS);
222      return getAddExpr(Ops);
223    }
224    SCEVHandle getAddExpr(const SCEVHandle &Op0, const SCEVHandle &Op1,
225                          const SCEVHandle &Op2) {
226      std::vector<SCEVHandle> Ops;
227      Ops.push_back(Op0);
228      Ops.push_back(Op1);
229      Ops.push_back(Op2);
230      return getAddExpr(Ops);
231    }
232    SCEVHandle getMulExpr(std::vector<SCEVHandle> &Ops);
233    SCEVHandle getMulExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) {
234      std::vector<SCEVHandle> Ops;
235      Ops.push_back(LHS);
236      Ops.push_back(RHS);
237      return getMulExpr(Ops);
238    }
239    SCEVHandle getUDivExpr(const SCEVHandle &LHS, const SCEVHandle &RHS);
240    SCEVHandle getAddRecExpr(const SCEVHandle &Start, const SCEVHandle &Step,
241                             const Loop *L);
242    SCEVHandle getAddRecExpr(std::vector<SCEVHandle> &Operands,
243                             const Loop *L);
244    SCEVHandle getAddRecExpr(const std::vector<SCEVHandle> &Operands,
245                             const Loop *L) {
246      std::vector<SCEVHandle> NewOp(Operands);
247      return getAddRecExpr(NewOp, L);
248    }
249    SCEVHandle getSMaxExpr(const SCEVHandle &LHS, const SCEVHandle &RHS);
250    SCEVHandle getSMaxExpr(std::vector<SCEVHandle> Operands);
251    SCEVHandle getUMaxExpr(const SCEVHandle &LHS, const SCEVHandle &RHS);
252    SCEVHandle getUMaxExpr(std::vector<SCEVHandle> Operands);
253    SCEVHandle getUnknown(Value *V);
254    SCEVHandle getCouldNotCompute();
255
256    /// getNegativeSCEV - Return the SCEV object corresponding to -V.
257    ///
258    SCEVHandle getNegativeSCEV(const SCEVHandle &V);
259
260    /// getNotSCEV - Return the SCEV object corresponding to ~V.
261    ///
262    SCEVHandle getNotSCEV(const SCEVHandle &V);
263
264    /// getMinusSCEV - Return LHS-RHS.
265    ///
266    SCEVHandle getMinusSCEV(const SCEVHandle &LHS,
267                            const SCEVHandle &RHS);
268
269    /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion
270    /// of the input value to the specified type.  If the type must be
271    /// extended, it is zero extended.
272    SCEVHandle getTruncateOrZeroExtend(const SCEVHandle &V, const Type *Ty);
273
274    /// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion
275    /// of the input value to the specified type.  If the type must be
276    /// extended, it is sign extended.
277    SCEVHandle getTruncateOrSignExtend(const SCEVHandle &V, const Type *Ty);
278
279    /// getIntegerSCEV - Given an integer or FP type, create a constant for the
280    /// specified signed integer value and return a SCEV for the constant.
281    SCEVHandle getIntegerSCEV(int Val, const Type *Ty);
282
283    /// hasSCEV - Return true if the SCEV for this value has already been
284    /// computed.
285    bool hasSCEV(Value *V) const;
286
287    /// setSCEV - Insert the specified SCEV into the map of current SCEVs for
288    /// the specified value.
289    void setSCEV(Value *V, const SCEVHandle &H);
290
291    /// getSCEVAtScope - Return a SCEV expression handle for the specified value
292    /// at the specified scope in the program.  The L value specifies a loop
293    /// nest to evaluate the expression at, where null is the top-level or a
294    /// specified loop is immediately inside of the loop.
295    ///
296    /// This method can be used to compute the exit value for a variable defined
297    /// in a loop by querying what the value will hold in the parent loop.
298    ///
299    /// If this value is not computable at this scope, a SCEVCouldNotCompute
300    /// object is returned.
301    SCEVHandle getSCEVAtScope(Value *V, const Loop *L) const;
302
303    /// isLoopGuardedByCond - Test whether entry to the loop is protected by
304    /// a conditional between LHS and RHS.
305    bool isLoopGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,
306                             SCEV *LHS, SCEV *RHS);
307
308    /// getBackedgeTakenCount - If the specified loop has a predictable
309    /// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute
310    /// object. The backedge-taken count is the number of times the loop header
311    /// will be branched to from within the loop. This is one less than the
312    /// trip count of the loop, since it doesn't count the first iteration,
313    /// when the header is branched to from outside the loop.
314    ///
315    /// Note that it is not valid to call this method on a loop without a
316    /// loop-invariant backedge-taken count (see
317    /// hasLoopInvariantBackedgeTakenCount).
318    ///
319    SCEVHandle getBackedgeTakenCount(const Loop *L) const;
320
321    /// hasLoopInvariantBackedgeTakenCount - Return true if the specified loop
322    /// has an analyzable loop-invariant backedge-taken count.
323    bool hasLoopInvariantBackedgeTakenCount(const Loop *L) const;
324
325    /// forgetLoopBackedgeTakenCount - This method should be called by the
326    /// client when it has changed a loop in a way that may effect
327    /// ScalarEvolution's ability to compute a trip count, or if the loop
328    /// is deleted.
329    void forgetLoopBackedgeTakenCount(const Loop *L);
330
331    /// deleteValueFromRecords - This method should be called by the
332    /// client before it removes a Value from the program, to make sure
333    /// that no dangling references are left around.
334    void deleteValueFromRecords(Value *V) const;
335
336    virtual bool runOnFunction(Function &F);
337    virtual void releaseMemory();
338    virtual void getAnalysisUsage(AnalysisUsage &AU) const;
339    void print(raw_ostream &OS, const Module* = 0) const;
340    virtual void print(std::ostream &OS, const Module* = 0) const;
341    void print(std::ostream *OS, const Module* M = 0) const {
342      if (OS) print(*OS, M);
343    }
344  };
345}
346
347#endif
348