ScalarEvolution.h revision c9759e80f45e5690c3ed3b69c2e9ffd5a1bffd9c 
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 "llvm/Support/ValueHandle.h"
28#include "llvm/ADT/DenseMap.h"
29#include <iosfwd>
30
31namespace llvm {
32  class APInt;
33  class ConstantInt;
34  class Type;
35  class SCEVHandle;
36  class ScalarEvolution;
37  class TargetData;
38  template<> struct DenseMapInfo<SCEVHandle>;
39
40  /// SCEV - This class represents an analyzed expression in the program.  These
41  /// are reference-counted opaque objects that the client is not allowed to
42  /// do much with directly.
43  ///
44  class SCEV {
45    const unsigned SCEVType;      // The SCEV baseclass this node corresponds to
46    mutable unsigned RefCount;
47
48    friend class SCEVHandle;
49    friend class DenseMapInfo<SCEVHandle>;
50    void addRef() const { ++RefCount; }
51    void dropRef() const {
52      if (--RefCount == 0)
53        delete this;
54    }
55
56    const ScalarEvolution* parent;
57
58    SCEV(const SCEV &);            // DO NOT IMPLEMENT
59    void operator=(const SCEV &);  // DO NOT IMPLEMENT
60  protected:
61    virtual ~SCEV();
62  public:
63    explicit SCEV(unsigned SCEVTy, const ScalarEvolution* p) :
64      SCEVType(SCEVTy), RefCount(0), parent(p) {}
65
66    unsigned getSCEVType() const { return SCEVType; }
67
68    /// isLoopInvariant - Return true if the value of this SCEV is unchanging in
69    /// the specified loop.
70    virtual bool isLoopInvariant(const Loop *L) const = 0;
71
72    /// hasComputableLoopEvolution - Return true if this SCEV changes value in a
73    /// known way in the specified loop.  This property being true implies that
74    /// the value is variant in the loop AND that we can emit an expression to
75    /// compute the value of the expression at any particular loop iteration.
76    virtual bool hasComputableLoopEvolution(const Loop *L) const = 0;
77
78    /// getType - Return the LLVM type of this SCEV expression.
79    ///
80    virtual const Type *getType() const = 0;
81
82    /// isZero - Return true if the expression is a constant zero.
83    ///
84    bool isZero() const;
85
86    /// isOne - Return true if the expression is a constant one.
87    ///
88    bool isOne() const;
89
90    /// replaceSymbolicValuesWithConcrete - If this SCEV internally references
91    /// the symbolic value "Sym", construct and return a new SCEV that produces
92    /// the same value, but which uses the concrete value Conc instead of the
93    /// symbolic value.  If this SCEV does not use the symbolic value, it
94    /// returns itself.
95    virtual SCEVHandle
96    replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
97                                      const SCEVHandle &Conc,
98                                      ScalarEvolution &SE) const = 0;
99
100    /// dominates - Return true if elements that makes up this SCEV dominates
101    /// the specified basic block.
102    virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const = 0;
103
104    /// print - Print out the internal representation of this scalar to the
105    /// specified stream.  This should really only be used for debugging
106    /// purposes.
107    virtual void print(raw_ostream &OS) const = 0;
108    void print(std::ostream &OS) const;
109    void print(std::ostream *OS) const { if (OS) print(*OS); }
110
111    /// dump - This method is used for debugging.
112    ///
113    void dump() const;
114  };
115
116  inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) {
117    S.print(OS);
118    return OS;
119  }
120
121  inline std::ostream &operator<<(std::ostream &OS, const SCEV &S) {
122    S.print(OS);
123    return OS;
124  }
125
126  /// SCEVCouldNotCompute - An object of this class is returned by queries that
127  /// could not be answered.  For example, if you ask for the number of
128  /// iterations of a linked-list traversal loop, you will get one of these.
129  /// None of the standard SCEV operations are valid on this class, it is just a
130  /// marker.
131  struct SCEVCouldNotCompute : public SCEV {
132    SCEVCouldNotCompute(const ScalarEvolution* p);
133    ~SCEVCouldNotCompute();
134
135    // None of these methods are valid for this object.
136    virtual bool isLoopInvariant(const Loop *L) const;
137    virtual const Type *getType() const;
138    virtual bool hasComputableLoopEvolution(const Loop *L) const;
139    virtual void print(raw_ostream &OS) const;
140    virtual SCEVHandle
141    replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
142                                      const SCEVHandle &Conc,
143                                      ScalarEvolution &SE) const;
144
145    virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const {
146      return true;
147    }
148
149    /// Methods for support type inquiry through isa, cast, and dyn_cast:
150    static inline bool classof(const SCEVCouldNotCompute *S) { return true; }
151    static bool classof(const SCEV *S);
152  };
153
154  /// SCEVHandle - This class is used to maintain the SCEV object's refcounts,
155  /// freeing the objects when the last reference is dropped.
156  class SCEVHandle {
157    const SCEV *S;
158    SCEVHandle();  // DO NOT IMPLEMENT
159  public:
160    SCEVHandle(const SCEV *s) : S(s) {
161      assert(S && "Cannot create a handle to a null SCEV!");
162      S->addRef();
163    }
164    SCEVHandle(const SCEVHandle &RHS) : S(RHS.S) {
165      S->addRef();
166    }
167    ~SCEVHandle() { S->dropRef(); }
168
169    operator const SCEV*() const { return S; }
170
171    const SCEV &operator*() const { return *S; }
172    const SCEV *operator->() const { return S; }
173
174    bool operator==(const SCEV *RHS) const { return S == RHS; }
175    bool operator!=(const SCEV *RHS) const { return S != RHS; }
176
177    const SCEVHandle &operator=(SCEV *RHS) {
178      if (S != RHS) {
179        S->dropRef();
180        S = RHS;
181        S->addRef();
182      }
183      return *this;
184    }
185
186    const SCEVHandle &operator=(const SCEVHandle &RHS) {
187      if (S != RHS.S) {
188        S->dropRef();
189        S = RHS.S;
190        S->addRef();
191      }
192      return *this;
193    }
194  };
195
196  template<typename From> struct simplify_type;
197  template<> struct simplify_type<const SCEVHandle> {
198    typedef const SCEV* SimpleType;
199    static SimpleType getSimplifiedValue(const SCEVHandle &Node) {
200      return Node;
201    }
202  };
203  template<> struct simplify_type<SCEVHandle>
204    : public simplify_type<const SCEVHandle> {};
205
206  // Specialize DenseMapInfo for SCEVHandle so that SCEVHandle may be used
207  // as a key in DenseMaps.
208  template<>
209  struct DenseMapInfo<SCEVHandle> {
210    static inline SCEVHandle getEmptyKey() {
211      static SCEVCouldNotCompute Empty(0);
212      if (Empty.RefCount == 0)
213        Empty.addRef();
214      return &Empty;
215    }
216    static inline SCEVHandle getTombstoneKey() {
217      static SCEVCouldNotCompute Tombstone(0);
218      if (Tombstone.RefCount == 0)
219        Tombstone.addRef();
220      return &Tombstone;
221    }
222    static unsigned getHashValue(const SCEVHandle &Val) {
223      return DenseMapInfo<const SCEV *>::getHashValue(Val);
224    }
225    static bool isEqual(const SCEVHandle &LHS, const SCEVHandle &RHS) {
226      return LHS == RHS;
227    }
228    static bool isPod() { return false; }
229  };
230
231  /// ScalarEvolution - This class is the main scalar evolution driver.  Because
232  /// client code (intentionally) can't do much with the SCEV objects directly,
233  /// they must ask this class for services.
234  ///
235  class ScalarEvolution : public FunctionPass {
236    /// SCEVCallbackVH - A CallbackVH to arrange for ScalarEvolution to be
237    /// notified whenever a Value is deleted.
238    class SCEVCallbackVH : public CallbackVH {
239      ScalarEvolution *SE;
240      virtual void deleted();
241      virtual void allUsesReplacedWith(Value *New);
242    public:
243      SCEVCallbackVH(Value *V, ScalarEvolution *SE = 0);
244    };
245
246    friend class SCEVCallbackVH;
247    friend class SCEVExpander;
248
249    /// F - The function we are analyzing.
250    ///
251    Function *F;
252
253    /// LI - The loop information for the function we are currently analyzing.
254    ///
255    LoopInfo *LI;
256
257    /// TD - The target data information for the target we are targetting.
258    ///
259    TargetData *TD;
260
261    /// CouldNotCompute - This SCEV is used to represent unknown trip
262    /// counts and things.
263    SCEVHandle CouldNotCompute;
264
265    /// Scalars - This is a cache of the scalars we have analyzed so far.
266    ///
267    std::map<SCEVCallbackVH, SCEVHandle> Scalars;
268
269    /// BackedgeTakenInfo - Information about the backedge-taken count
270    /// of a loop. This currently inclues an exact count and a maximum count.
271    ///
272    struct BackedgeTakenInfo {
273      /// Exact - An expression indicating the exact backedge-taken count of
274      /// the loop if it is known, or a SCEVCouldNotCompute otherwise.
275      SCEVHandle Exact;
276
277      /// Exact - An expression indicating the least maximum backedge-taken
278      /// count of the loop that is known, or a SCEVCouldNotCompute.
279      SCEVHandle Max;
280
281      /*implicit*/ BackedgeTakenInfo(SCEVHandle exact) :
282        Exact(exact), Max(exact) {}
283
284      /*implicit*/ BackedgeTakenInfo(const SCEV *exact) :
285        Exact(exact), Max(exact) {}
286
287      BackedgeTakenInfo(SCEVHandle exact, SCEVHandle max) :
288        Exact(exact), Max(max) {}
289
290      /// hasAnyInfo - Test whether this BackedgeTakenInfo contains any
291      /// computed information, or whether it's all SCEVCouldNotCompute
292      /// values.
293      bool hasAnyInfo() const {
294        return !isa<SCEVCouldNotCompute>(Exact) ||
295               !isa<SCEVCouldNotCompute>(Max);
296      }
297    };
298
299    /// BackedgeTakenCounts - Cache the backedge-taken count of the loops for
300    /// this function as they are computed.
301    std::map<const Loop*, BackedgeTakenInfo> BackedgeTakenCounts;
302
303    /// ConstantEvolutionLoopExitValue - This map contains entries for all of
304    /// the PHI instructions that we attempt to compute constant evolutions for.
305    /// This allows us to avoid potentially expensive recomputation of these
306    /// properties.  An instruction maps to null if we are unable to compute its
307    /// exit value.
308    std::map<PHINode*, Constant*> ConstantEvolutionLoopExitValue;
309
310    /// ValuesAtScopes - This map contains entries for all the instructions
311    /// that we attempt to compute getSCEVAtScope information for without
312    /// using SCEV techniques, which can be expensive.
313    std::map<Instruction *, std::map<const Loop *, Constant *> > ValuesAtScopes;
314
315    /// createSCEV - We know that there is no SCEV for the specified value.
316    /// Analyze the expression.
317    SCEVHandle createSCEV(Value *V);
318
319    /// createNodeForPHI - Provide the special handling we need to analyze PHI
320    /// SCEVs.
321    SCEVHandle createNodeForPHI(PHINode *PN);
322
323    /// createNodeForGEP - Provide the special handling we need to analyze GEP
324    /// SCEVs.
325    SCEVHandle createNodeForGEP(User *GEP);
326
327    /// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value
328    /// for the specified instruction and replaces any references to the
329    /// symbolic value SymName with the specified value.  This is used during
330    /// PHI resolution.
331    void ReplaceSymbolicValueWithConcrete(Instruction *I,
332                                          const SCEVHandle &SymName,
333                                          const SCEVHandle &NewVal);
334
335    /// getBECount - Subtract the end and start values and divide by the step,
336    /// rounding up, to get the number of times the backedge is executed. Return
337    /// CouldNotCompute if an intermediate computation overflows.
338    SCEVHandle getBECount(const SCEVHandle &Start,
339                          const SCEVHandle &End,
340                          const SCEVHandle &Step);
341
342    /// getBackedgeTakenInfo - Return the BackedgeTakenInfo for the given
343    /// loop, lazily computing new values if the loop hasn't been analyzed
344    /// yet.
345    const BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L);
346
347    /// ComputeBackedgeTakenCount - Compute the number of times the specified
348    /// loop will iterate.
349    BackedgeTakenInfo ComputeBackedgeTakenCount(const Loop *L);
350
351    /// ComputeBackedgeTakenCountFromExit - Compute the number of times the
352    /// backedge of the specified loop will execute if it exits via the
353    /// specified block.
354    BackedgeTakenInfo ComputeBackedgeTakenCountFromExit(const Loop *L,
355                                                      BasicBlock *ExitingBlock);
356
357    /// ComputeBackedgeTakenCountFromExitCond - Compute the number of times the
358    /// backedge of the specified loop will execute if its exit condition
359    /// were a conditional branch of ExitCond, TBB, and FBB.
360    BackedgeTakenInfo
361      ComputeBackedgeTakenCountFromExitCond(const Loop *L,
362                                            Value *ExitCond,
363                                            BasicBlock *TBB,
364                                            BasicBlock *FBB);
365
366    /// ComputeBackedgeTakenCountFromExitCondICmp - Compute the number of
367    /// times the backedge of the specified loop will execute if its exit
368    /// condition were a conditional branch of the ICmpInst ExitCond, TBB,
369    /// and FBB.
370    BackedgeTakenInfo
371      ComputeBackedgeTakenCountFromExitCondICmp(const Loop *L,
372                                                ICmpInst *ExitCond,
373                                                BasicBlock *TBB,
374                                                BasicBlock *FBB);
375
376    /// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition
377    /// of 'icmp op load X, cst', try to see if we can compute the trip count.
378    SCEVHandle
379      ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI,
380                                                   Constant *RHS,
381                                                   const Loop *L,
382                                                   ICmpInst::Predicate p);
383
384    /// ComputeBackedgeTakenCountExhaustively - If the trip is known to execute
385    /// a constant number of times (the condition evolves only from constants),
386    /// try to evaluate a few iterations of the loop until we get the exit
387    /// condition gets a value of ExitWhen (true or false).  If we cannot
388    /// evaluate the trip count of the loop, return CouldNotCompute.
389    SCEVHandle ComputeBackedgeTakenCountExhaustively(const Loop *L, Value *Cond,
390                                                     bool ExitWhen);
391
392    /// HowFarToZero - Return the number of times a backedge comparing the
393    /// specified value to zero will execute.  If not computable, return
394    /// CouldNotCompute.
395    SCEVHandle HowFarToZero(const SCEV *V, const Loop *L);
396
397    /// HowFarToNonZero - Return the number of times a backedge checking the
398    /// specified value for nonzero will execute.  If not computable, return
399    /// CouldNotCompute.
400    SCEVHandle HowFarToNonZero(const SCEV *V, const Loop *L);
401
402    /// HowManyLessThans - Return the number of times a backedge containing the
403    /// specified less-than comparison will execute.  If not computable, return
404    /// CouldNotCompute. isSigned specifies whether the less-than is signed.
405    BackedgeTakenInfo HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
406                                       const Loop *L, bool isSigned);
407
408    /// getLoopPredecessor - If the given loop's header has exactly one unique
409    /// predecessor outside the loop, return it. Otherwise return null.
410    BasicBlock *getLoopPredecessor(const Loop *L);
411
412    /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB
413    /// (which may not be an immediate predecessor) which has exactly one
414    /// successor from which BB is reachable, or null if no such block is
415    /// found.
416    BasicBlock* getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB);
417
418    /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is
419    /// in the header of its containing loop, we know the loop executes a
420    /// constant number of times, and the PHI node is just a recurrence
421    /// involving constants, fold it.
422    Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs,
423                                                const Loop *L);
424
425    /// forgetLoopPHIs - Delete the memoized SCEVs associated with the
426    /// PHI nodes in the given loop. This is used when the trip count of
427    /// the loop may have changed.
428    void forgetLoopPHIs(const Loop *L);
429
430  public:
431    static char ID; // Pass identification, replacement for typeid
432    ScalarEvolution();
433
434    /// isSCEVable - Test if values of the given type are analyzable within
435    /// the SCEV framework. This primarily includes integer types, and it
436    /// can optionally include pointer types if the ScalarEvolution class
437    /// has access to target-specific information.
438    bool isSCEVable(const Type *Ty) const;
439
440    /// getTypeSizeInBits - Return the size in bits of the specified type,
441    /// for which isSCEVable must return true.
442    uint64_t getTypeSizeInBits(const Type *Ty) const;
443
444    /// getEffectiveSCEVType - Return a type with the same bitwidth as
445    /// the given type and which represents how SCEV will treat the given
446    /// type, for which isSCEVable must return true. For pointer types,
447    /// this is the pointer-sized integer type.
448    const Type *getEffectiveSCEVType(const Type *Ty) const;
449
450    /// getSCEV - Return a SCEV expression handle for the full generality of the
451    /// specified expression.
452    SCEVHandle getSCEV(Value *V);
453
454    SCEVHandle getConstant(ConstantInt *V);
455    SCEVHandle getConstant(const APInt& Val);
456    SCEVHandle getConstant(const Type *Ty, uint64_t V, bool isSigned = false);
457    SCEVHandle getTruncateExpr(const SCEVHandle &Op, const Type *Ty);
458    SCEVHandle getZeroExtendExpr(const SCEVHandle &Op, const Type *Ty);
459    SCEVHandle getSignExtendExpr(const SCEVHandle &Op, const Type *Ty);
460    SCEVHandle getAnyExtendExpr(const SCEVHandle &Op, const Type *Ty);
461    SCEVHandle getAddExpr(SmallVectorImpl<SCEVHandle> &Ops);
462    SCEVHandle getAddExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) {
463      SmallVector<SCEVHandle, 2> Ops;
464      Ops.push_back(LHS);
465      Ops.push_back(RHS);
466      return getAddExpr(Ops);
467    }
468    SCEVHandle getAddExpr(const SCEVHandle &Op0, const SCEVHandle &Op1,
469                          const SCEVHandle &Op2) {
470      SmallVector<SCEVHandle, 3> Ops;
471      Ops.push_back(Op0);
472      Ops.push_back(Op1);
473      Ops.push_back(Op2);
474      return getAddExpr(Ops);
475    }
476    SCEVHandle getMulExpr(SmallVectorImpl<SCEVHandle> &Ops);
477    SCEVHandle getMulExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) {
478      SmallVector<SCEVHandle, 2> Ops;
479      Ops.push_back(LHS);
480      Ops.push_back(RHS);
481      return getMulExpr(Ops);
482    }
483    SCEVHandle getUDivExpr(const SCEVHandle &LHS, const SCEVHandle &RHS);
484    SCEVHandle getAddRecExpr(const SCEVHandle &Start, const SCEVHandle &Step,
485                             const Loop *L);
486    SCEVHandle getAddRecExpr(SmallVectorImpl<SCEVHandle> &Operands,
487                             const Loop *L);
488    SCEVHandle getAddRecExpr(const SmallVectorImpl<SCEVHandle> &Operands,
489                             const Loop *L) {
490      SmallVector<SCEVHandle, 4> NewOp(Operands.begin(), Operands.end());
491      return getAddRecExpr(NewOp, L);
492    }
493    SCEVHandle getSMaxExpr(const SCEVHandle &LHS, const SCEVHandle &RHS);
494    SCEVHandle getSMaxExpr(SmallVectorImpl<SCEVHandle> &Operands);
495    SCEVHandle getUMaxExpr(const SCEVHandle &LHS, const SCEVHandle &RHS);
496    SCEVHandle getUMaxExpr(SmallVectorImpl<SCEVHandle> &Operands);
497    SCEVHandle getSMinExpr(const SCEVHandle &LHS, const SCEVHandle &RHS);
498    SCEVHandle getUMinExpr(const SCEVHandle &LHS, const SCEVHandle &RHS);
499    SCEVHandle getUnknown(Value *V);
500    SCEVHandle getCouldNotCompute();
501
502    /// getNegativeSCEV - Return the SCEV object corresponding to -V.
503    ///
504    SCEVHandle getNegativeSCEV(const SCEVHandle &V);
505
506    /// getNotSCEV - Return the SCEV object corresponding to ~V.
507    ///
508    SCEVHandle getNotSCEV(const SCEVHandle &V);
509
510    /// getMinusSCEV - Return LHS-RHS.
511    ///
512    SCEVHandle getMinusSCEV(const SCEVHandle &LHS,
513                            const SCEVHandle &RHS);
514
515    /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion
516    /// of the input value to the specified type.  If the type must be
517    /// extended, it is zero extended.
518    SCEVHandle getTruncateOrZeroExtend(const SCEVHandle &V, const Type *Ty);
519
520    /// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion
521    /// of the input value to the specified type.  If the type must be
522    /// extended, it is sign extended.
523    SCEVHandle getTruncateOrSignExtend(const SCEVHandle &V, const Type *Ty);
524
525    /// getNoopOrZeroExtend - Return a SCEV corresponding to a conversion of
526    /// the input value to the specified type.  If the type must be extended,
527    /// it is zero extended.  The conversion must not be narrowing.
528    SCEVHandle getNoopOrZeroExtend(const SCEVHandle &V, const Type *Ty);
529
530    /// getNoopOrSignExtend - Return a SCEV corresponding to a conversion of
531    /// the input value to the specified type.  If the type must be extended,
532    /// it is sign extended.  The conversion must not be narrowing.
533    SCEVHandle getNoopOrSignExtend(const SCEVHandle &V, const Type *Ty);
534
535    /// getNoopOrAnyExtend - Return a SCEV corresponding to a conversion of
536    /// the input value to the specified type. If the type must be extended,
537    /// it is extended with unspecified bits. The conversion must not be
538    /// narrowing.
539    SCEVHandle getNoopOrAnyExtend(const SCEVHandle &V, const Type *Ty);
540
541    /// getTruncateOrNoop - Return a SCEV corresponding to a conversion of the
542    /// input value to the specified type.  The conversion must not be
543    /// widening.
544    SCEVHandle getTruncateOrNoop(const SCEVHandle &V, const Type *Ty);
545
546    /// getIntegerSCEV - Given an integer or FP type, create a constant for the
547    /// specified signed integer value and return a SCEV for the constant.
548    SCEVHandle getIntegerSCEV(int Val, const Type *Ty);
549
550    /// getUMaxFromMismatchedTypes - Promote the operands to the wider of
551    /// the types using zero-extension, and then perform a umax operation
552    /// with them.
553    SCEVHandle getUMaxFromMismatchedTypes(const SCEVHandle &LHS,
554                                          const SCEVHandle &RHS);
555
556    /// getUMinFromMismatchedTypes - Promote the operands to the wider of
557    /// the types using zero-extension, and then perform a umin operation
558    /// with them.
559    SCEVHandle getUMinFromMismatchedTypes(const SCEVHandle &LHS,
560                                          const SCEVHandle &RHS);
561
562    /// hasSCEV - Return true if the SCEV for this value has already been
563    /// computed.
564    bool hasSCEV(Value *V) const;
565
566    /// setSCEV - Insert the specified SCEV into the map of current SCEVs for
567    /// the specified value.
568    void setSCEV(Value *V, const SCEVHandle &H);
569
570    /// getSCEVAtScope - Return a SCEV expression handle for the specified value
571    /// at the specified scope in the program.  The L value specifies a loop
572    /// nest to evaluate the expression at, where null is the top-level or a
573    /// specified loop is immediately inside of the loop.
574    ///
575    /// This method can be used to compute the exit value for a variable defined
576    /// in a loop by querying what the value will hold in the parent loop.
577    ///
578    /// In the case that a relevant loop exit value cannot be computed, the
579    /// original value V is returned.
580    SCEVHandle getSCEVAtScope(const SCEV *S, const Loop *L);
581
582    /// getSCEVAtScope - This is a convenience function which does
583    /// getSCEVAtScope(getSCEV(V), L).
584    SCEVHandle getSCEVAtScope(Value *V, const Loop *L);
585
586    /// isLoopGuardedByCond - Test whether entry to the loop is protected by
587    /// a conditional between LHS and RHS.  This is used to help avoid max
588    /// expressions in loop trip counts.
589    bool isLoopGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,
590                             const SCEV *LHS, const SCEV *RHS);
591
592    /// getBackedgeTakenCount - If the specified loop has a predictable
593    /// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute
594    /// object. The backedge-taken count is the number of times the loop header
595    /// will be branched to from within the loop. This is one less than the
596    /// trip count of the loop, since it doesn't count the first iteration,
597    /// when the header is branched to from outside the loop.
598    ///
599    /// Note that it is not valid to call this method on a loop without a
600    /// loop-invariant backedge-taken count (see
601    /// hasLoopInvariantBackedgeTakenCount).
602    ///
603    SCEVHandle getBackedgeTakenCount(const Loop *L);
604
605    /// getMaxBackedgeTakenCount - Similar to getBackedgeTakenCount, except
606    /// return the least SCEV value that is known never to be less than the
607    /// actual backedge taken count.
608    SCEVHandle getMaxBackedgeTakenCount(const Loop *L);
609
610    /// hasLoopInvariantBackedgeTakenCount - Return true if the specified loop
611    /// has an analyzable loop-invariant backedge-taken count.
612    bool hasLoopInvariantBackedgeTakenCount(const Loop *L);
613
614    /// forgetLoopBackedgeTakenCount - This method should be called by the
615    /// client when it has changed a loop in a way that may effect
616    /// ScalarEvolution's ability to compute a trip count, or if the loop
617    /// is deleted.
618    void forgetLoopBackedgeTakenCount(const Loop *L);
619
620    /// GetMinTrailingZeros - Determine the minimum number of zero bits that S is
621    /// guaranteed to end in (at every loop iteration).  It is, at the same time,
622    /// the minimum number of times S is divisible by 2.  For example, given {4,+,8}
623    /// it returns 2.  If S is guaranteed to be 0, it returns the bitwidth of S.
624    uint32_t GetMinTrailingZeros(const SCEVHandle &S);
625
626    /// GetMinLeadingZeros - Determine the minimum number of zero bits that S is
627    /// guaranteed to begin with (at every loop iteration).
628    uint32_t GetMinLeadingZeros(const SCEVHandle &S);
629
630    /// GetMinSignBits - Determine the minimum number of sign bits that S is
631    /// guaranteed to begin with.
632    uint32_t GetMinSignBits(const SCEVHandle &S);
633
634    virtual bool runOnFunction(Function &F);
635    virtual void releaseMemory();
636    virtual void getAnalysisUsage(AnalysisUsage &AU) const;
637    void print(raw_ostream &OS, const Module* = 0) const;
638    virtual void print(std::ostream &OS, const Module* = 0) const;
639    void print(std::ostream *OS, const Module* M = 0) const {
640      if (OS) print(*OS, M);
641    }
642  };
643}
644
645#endif
646