include/llvm/Analysis/ScalarEvolution.h

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