X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FScalarEvolution.h;h=349447fbbb624ef66923d40a1ee59112593b87e4;hb=75b51621540c23ddfc1e9ef6b4dc803453d9d122;hp=10d933e68f5b89c194b34c823b9d4bf973e3a6d6;hpb=e97728ecf8a0ee69562cc0e7880cfaa65200c624;p=oota-llvm.git diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index 10d933e68f5..349447fbbb6 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -21,16 +21,16 @@ #ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H #define LLVM_ANALYSIS_SCALAREVOLUTION_H +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/FoldingSet.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Operator.h" #include "llvm/Pass.h" -#include "llvm/Instructions.h" -#include "llvm/Function.h" -#include "llvm/Operator.h" -#include "llvm/Support/DataTypes.h" -#include "llvm/Support/ValueHandle.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/ConstantRange.h" -#include "llvm/ADT/FoldingSet.h" -#include "llvm/ADT/DenseMap.h" +#include "llvm/Support/DataTypes.h" +#include "llvm/Support/ValueHandle.h" #include namespace llvm { @@ -40,7 +40,8 @@ namespace llvm { class DominatorTree; class Type; class ScalarEvolution; - class TargetData; + class DataLayout; + class TargetLibraryInfo; class LLVMContext; class Loop; class LoopInfo; @@ -69,8 +70,8 @@ namespace llvm { unsigned short SubclassData; private: - SCEV(const SCEV &); // DO NOT IMPLEMENT - void operator=(const SCEV &); // DO NOT IMPLEMENT + SCEV(const SCEV &) LLVM_DELETED_FUNCTION; + void operator=(const SCEV &) LLVM_DELETED_FUNCTION; public: /// NoWrapFlags are bitfield indices into SubclassData. @@ -118,6 +119,10 @@ namespace llvm { /// bool isAllOnesValue() const; + /// isNonConstantNegative - Return true if the specified scev is negated, + /// but not a constant. + bool isNonConstantNegative() const; + /// print - Print out the internal representation of this scalar to the /// specified stream. This should really only be used for debugging /// purposes. @@ -135,7 +140,7 @@ namespace llvm { ID = X.FastID; } static bool Equals(const SCEV &X, const FoldingSetNodeID &ID, - FoldingSetNodeID &TempID) { + unsigned IDHash, FoldingSetNodeID &TempID) { return ID == X.FastID; } static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID) { @@ -157,7 +162,6 @@ namespace llvm { SCEVCouldNotCompute(); /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVCouldNotCompute *S) { return true; } static bool classof(const SCEV *S); }; @@ -222,7 +226,11 @@ namespace llvm { /// TD - The target data information for the target we are targeting. /// - TargetData *TD; + DataLayout *TD; + + /// TLI - The target library information for the target we are targeting. + /// + TargetLibraryInfo *TLI; /// DT - The dominator tree. /// @@ -241,6 +249,9 @@ namespace llvm { /// ValueExprMapType ValueExprMap; + /// Mark predicate values currently being processed by isImpliedCond. + DenseSet PendingLoopPredicates; + /// ExitLimit - Information about the number of loop iterations for /// which a loop exit's branch condition evaluates to the not-taken path. /// This is a temporary pair of exact and max expressions that are @@ -327,6 +338,10 @@ namespace llvm { /// getMax - Get the max backedge taken count for the loop. const SCEV *getMax(ScalarEvolution *SE) const; + /// Return true if any backedge taken count expressions refer to the given + /// subexpression. + bool hasOperand(const SCEV *S, ScalarEvolution *SE) const; + /// clear - Invalidate this result and free associated memory. void clear(); }; @@ -438,7 +453,8 @@ namespace llvm { ExitLimit ComputeExitLimitFromCond(const Loop *L, Value *ExitCond, BasicBlock *TBB, - BasicBlock *FBB); + BasicBlock *FBB, + bool IsSubExpr); /// ComputeExitLimitFromICmp - Compute the number of times the backedge of /// the specified loop will execute if its exit condition were a conditional @@ -446,7 +462,8 @@ namespace llvm { ExitLimit ComputeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond, BasicBlock *TBB, - BasicBlock *FBB); + BasicBlock *FBB, + bool IsSubExpr); /// ComputeLoadConstantCompareExitLimit - Given an exit condition /// of 'icmp op load X, cst', try to see if we can compute the @@ -468,7 +485,7 @@ namespace llvm { /// HowFarToZero - Return the number of times an exit condition comparing /// the specified value to zero will execute. If not computable, return /// CouldNotCompute. - ExitLimit HowFarToZero(const SCEV *V, const Loop *L); + ExitLimit HowFarToZero(const SCEV *V, const Loop *L, bool IsSubExpr); /// HowFarToNonZero - Return the number of times an exit condition checking /// the specified value for nonzero will execute. If not computable, return @@ -480,7 +497,7 @@ namespace llvm { /// computable, return CouldNotCompute. isSigned specifies whether the /// less-than is signed. ExitLimit HowManyLessThans(const SCEV *LHS, const SCEV *RHS, - const Loop *L, bool isSigned); + const Loop *L, bool isSigned, bool IsSubExpr); /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB /// (which may not be an immediate predecessor) which has exactly one @@ -721,16 +738,21 @@ namespace llvm { const SCEV *LHS, const SCEV *RHS); /// getSmallConstantTripCount - Returns the maximum trip count of this loop - /// as a normal unsigned value, if possible. Returns 0 if the trip count is - /// unknown or not constant. - unsigned getSmallConstantTripCount(Loop *L, BasicBlock *ExitBlock); + /// as a normal unsigned value. Returns 0 if the trip count is unknown or + /// not constant. This "trip count" assumes that control exits via + /// ExitingBlock. More precisely, it is the number of times that control may + /// reach ExitingBlock before taking the branch. For loops with multiple + /// exits, it may not be the number times that the loop header executes if + /// the loop exits prematurely via another branch. + unsigned getSmallConstantTripCount(Loop *L, BasicBlock *ExitingBlock); /// getSmallConstantTripMultiple - Returns the largest constant divisor of /// the trip count of this loop as a normal unsigned value, if /// possible. This means that the actual trip count is always a multiple of /// the returned value (don't forget the trip count could very well be zero - /// as well!). - unsigned getSmallConstantTripMultiple(Loop *L, BasicBlock *ExitBlock); + /// as well!). As explained in the comments for getSmallConstantTripCount, + /// this assumes that control exits the loop via ExitingBlock. + unsigned getSmallConstantTripMultiple(Loop *L, BasicBlock *ExitingBlock); // getExitCount - Get the expression for the number of loop iterations for // which this loop is guaranteed not to exit via ExitingBlock. Otherwise @@ -815,12 +837,13 @@ namespace llvm { /// SimplifyICmpOperands - Simplify LHS and RHS in a comparison with /// predicate Pred. Return true iff any changes were made. If the - /// operands are provably equal or inequal, LHS and RHS are set to + /// operands are provably equal or unequal, LHS and RHS are set to /// the same value and Pred is set to either ICMP_EQ or ICMP_NE. /// bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, const SCEV *&LHS, - const SCEV *&RHS); + const SCEV *&RHS, + unsigned Depth = 0); /// getLoopDisposition - Return the "disposition" of the given SCEV with /// respect to the given loop. @@ -856,6 +879,7 @@ namespace llvm { virtual void releaseMemory(); virtual void getAnalysisUsage(AnalysisUsage &AU) const; virtual void print(raw_ostream &OS, const Module* = 0) const; + virtual void verifyAnalysis() const; private: FoldingSet UniqueSCEVs;