diff options
| -rw-r--r-- | include/llvm/Analysis/IVUsers.h | 16 | ||||
| -rw-r--r-- | include/llvm/Analysis/LoopVR.h | 4 | ||||
| -rw-r--r-- | include/llvm/Analysis/ScalarEvolution.h | 154 | ||||
| -rw-r--r-- | include/llvm/Analysis/ScalarEvolutionExpander.h | 8 | ||||
| -rw-r--r-- | include/llvm/Analysis/ScalarEvolutionExpressions.h | 99 | ||||
| -rw-r--r-- | lib/Analysis/IVUsers.cpp | 28 | ||||
| -rw-r--r-- | lib/Analysis/LoopVR.cpp | 14 | ||||
| -rw-r--r-- | lib/Analysis/ScalarEvolution.cpp | 412 | ||||
| -rw-r--r-- | lib/Analysis/ScalarEvolutionExpander.cpp | 58 | ||||
| -rw-r--r-- | lib/Transforms/Scalar/IndVarSimplify.cpp | 24 | ||||
| -rw-r--r-- | lib/Transforms/Scalar/LoopDeletion.cpp | 2 | ||||
| -rw-r--r-- | lib/Transforms/Scalar/LoopStrengthReduce.cpp | 206 |
12 files changed, 514 insertions, 511 deletions
diff --git a/include/llvm/Analysis/IVUsers.h b/include/llvm/Analysis/IVUsers.h index 40396e2fca..e4820f0053 100644 --- a/include/llvm/Analysis/IVUsers.h +++ b/include/llvm/Analysis/IVUsers.h @@ -34,7 +34,7 @@ class IVUsersOfOneStride; class IVStrideUse : public CallbackVH, public ilist_node<IVStrideUse> { public: IVStrideUse(IVUsersOfOneStride *parent, - const SCEV* offset, + const SCEV *offset, Instruction* U, Value *O) : CallbackVH(U), Parent(parent), Offset(offset), OperandValToReplace(O), @@ -58,10 +58,10 @@ public: /// getOffset - Return the offset to add to a theoeretical induction /// variable that starts at zero and counts up by the stride to compute /// the value for the use. This always has the same type as the stride. - const SCEV* getOffset() const { return Offset; } + const SCEV *getOffset() const { return Offset; } /// setOffset - Assign a new offset to this use. - void setOffset(const SCEV* Val) { + void setOffset(const SCEV *Val) { Offset = Val; } @@ -96,7 +96,7 @@ private: IVUsersOfOneStride *Parent; /// Offset - The offset to add to the base induction expression. - const SCEV* Offset; + const SCEV *Offset; /// OperandValToReplace - The Value of the operand in the user instruction /// that this IVStrideUse is representing. @@ -158,7 +158,7 @@ public: /// initial value and the operand that uses the IV. ilist<IVStrideUse> Users; - void addUser(const SCEV* Offset, Instruction *User, Value *Operand) { + void addUser(const SCEV *Offset, Instruction *User, Value *Operand) { Users.push_back(new IVStrideUse(this, Offset, User, Operand)); } }; @@ -178,12 +178,12 @@ public: /// IVUsesByStride - A mapping from the strides in StrideOrder to the /// uses in IVUses. - std::map<const SCEV*, IVUsersOfOneStride*> IVUsesByStride; + std::map<const SCEV *, IVUsersOfOneStride*> IVUsesByStride; /// StrideOrder - An ordering of the keys in IVUsesByStride that is stable: /// We use this to iterate over the IVUsesByStride collection without being /// dependent on random ordering of pointers in the process. - SmallVector<const SCEV*, 16> StrideOrder; + SmallVector<const SCEV *, 16> StrideOrder; private: virtual void getAnalysisUsage(AnalysisUsage &AU) const; @@ -203,7 +203,7 @@ public: /// getReplacementExpr - Return a SCEV expression which computes the /// value of the OperandValToReplace of the given IVStrideUse. - const SCEV* getReplacementExpr(const IVStrideUse &U) const; + const SCEV *getReplacementExpr(const IVStrideUse &U) const; void print(raw_ostream &OS, const Module* = 0) const; virtual void print(std::ostream &OS, const Module* = 0) const; diff --git a/include/llvm/Analysis/LoopVR.h b/include/llvm/Analysis/LoopVR.h index 36b62152f8..be13a80d02 100644 --- a/include/llvm/Analysis/LoopVR.h +++ b/include/llvm/Analysis/LoopVR.h @@ -78,9 +78,9 @@ public: private: ConstantRange compute(Value *V); - ConstantRange getRange(const SCEV* S, Loop *L, ScalarEvolution &SE); + ConstantRange getRange(const SCEV *S, Loop *L, ScalarEvolution &SE); - ConstantRange getRange(const SCEV* S, const SCEV* T, ScalarEvolution &SE); + ConstantRange getRange(const SCEV *S, const SCEV *T, ScalarEvolution &SE); std::map<Value *, ConstantRange *> Map; }; diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index 36f881140d..b60a0854c8 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -89,9 +89,9 @@ namespace llvm { /// the same value, but which uses the concrete value Conc instead of the /// symbolic value. If this SCEV does not use the symbolic value, it /// returns itself. - virtual const SCEV* - replaceSymbolicValuesWithConcrete(const SCEV* Sym, - const SCEV* Conc, + virtual const SCEV * + replaceSymbolicValuesWithConcrete(const SCEV *Sym, + const SCEV *Conc, ScalarEvolution &SE) const = 0; /// dominates - Return true if elements that makes up this SCEV dominates @@ -134,9 +134,9 @@ namespace llvm { virtual const Type *getType() const; virtual bool hasComputableLoopEvolution(const Loop *L) const; virtual void print(raw_ostream &OS) const; - virtual const SCEV* - replaceSymbolicValuesWithConcrete(const SCEV* Sym, - const SCEV* Conc, + virtual const SCEV * + replaceSymbolicValuesWithConcrete(const SCEV *Sym, + const SCEV *Conc, ScalarEvolution &SE) const; virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const { @@ -184,7 +184,7 @@ namespace llvm { /// Scalars - This is a cache of the scalars we have analyzed so far. /// - std::map<SCEVCallbackVH, const SCEV*> Scalars; + std::map<SCEVCallbackVH, const SCEV *> Scalars; /// BackedgeTakenInfo - Information about the backedge-taken count /// of a loop. This currently inclues an exact count and a maximum count. @@ -192,16 +192,16 @@ namespace llvm { struct BackedgeTakenInfo { /// Exact - An expression indicating the exact backedge-taken count of /// the loop if it is known, or a SCEVCouldNotCompute otherwise. - const SCEV* Exact; + const SCEV *Exact; /// Exact - An expression indicating the least maximum backedge-taken /// count of the loop that is known, or a SCEVCouldNotCompute. - const SCEV* Max; + const SCEV *Max; - /*implicit*/ BackedgeTakenInfo(const SCEV* exact) : + /*implicit*/ BackedgeTakenInfo(const SCEV *exact) : Exact(exact), Max(exact) {} - BackedgeTakenInfo(const SCEV* exact, const SCEV* max) : + BackedgeTakenInfo(const SCEV *exact, const SCEV *max) : Exact(exact), Max(max) {} /// hasAnyInfo - Test whether this BackedgeTakenInfo contains any @@ -231,30 +231,30 @@ namespace llvm { /// createSCEV - We know that there is no SCEV for the specified value. /// Analyze the expression. - const SCEV* createSCEV(Value *V); + const SCEV *createSCEV(Value *V); /// createNodeForPHI - Provide the special handling we need to analyze PHI /// SCEVs. - const SCEV* createNodeForPHI(PHINode *PN); + const SCEV *createNodeForPHI(PHINode *PN); /// createNodeForGEP - Provide the special handling we need to analyze GEP /// SCEVs. - const SCEV* createNodeForGEP(User *GEP); + const SCEV *createNodeForGEP(User *GEP); /// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value /// for the specified instruction and replaces any references to the /// symbolic value SymName with the specified value. This is used during /// PHI resolution. void ReplaceSymbolicValueWithConcrete(Instruction *I, - const SCEV* SymName, - const SCEV* NewVal); + const SCEV *SymName, + const SCEV *NewVal); /// getBECount - Subtract the end and start values and divide by the step, /// rounding up, to get the number of times the backedge is executed. Return /// CouldNotCompute if an intermediate computation overflows. - const SCEV* getBECount(const SCEV* Start, - const SCEV* End, - const SCEV* Step); + const SCEV *getBECount(const SCEV *Start, + const SCEV *End, + const SCEV *Step); /// getBackedgeTakenInfo - Return the BackedgeTakenInfo for the given /// loop, lazily computing new values if the loop hasn't been analyzed @@ -292,7 +292,7 @@ namespace llvm { /// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition /// of 'icmp op load X, cst', try to see if we can compute the trip count. - const SCEV* + const SCEV * ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI, Constant *RHS, const Loop *L, @@ -303,19 +303,19 @@ namespace llvm { /// try to evaluate a few iterations of the loop until we get the exit /// condition gets a value of ExitWhen (true or false). If we cannot /// evaluate the trip count of the loop, return CouldNotCompute. - const SCEV* ComputeBackedgeTakenCountExhaustively(const Loop *L, + const SCEV *ComputeBackedgeTakenCountExhaustively(const Loop *L, Value *Cond, bool ExitWhen); /// HowFarToZero - Return the number of times a backedge comparing the /// specified value to zero will execute. If not computable, return /// CouldNotCompute. - const SCEV* HowFarToZero(const SCEV *V, const Loop *L); + const SCEV *HowFarToZero(const SCEV *V, const Loop *L); /// HowFarToNonZero - Return the number of times a backedge checking the /// specified value for nonzero will execute. If not computable, return /// CouldNotCompute. - const SCEV* HowFarToNonZero(const SCEV *V, const Loop *L); + const SCEV *HowFarToNonZero(const SCEV *V, const Loop *L); /// HowManyLessThans - Return the number of times a backedge containing the /// specified less-than comparison will execute. If not computable, return @@ -375,115 +375,115 @@ namespace llvm { /// getSCEV - Return a SCEV expression handle for the full generality of the /// specified expression. - const SCEV* getSCEV(Value *V); - - const SCEV* getConstant(ConstantInt *V); - const SCEV* getConstant(const APInt& Val); - const SCEV* getConstant(const Type *Ty, uint64_t V, bool isSigned = false); - const SCEV* getTruncateExpr(const SCEV* Op, const Type *Ty); - const SCEV* getZeroExtendExpr(const SCEV* Op, const Type *Ty); - const SCEV* getSignExtendExpr(const SCEV* Op, const Type *Ty); - const SCEV* getAnyExtendExpr(const SCEV* Op, const Type *Ty); - const SCEV* getAddExpr(SmallVectorImpl<const SCEV*> &Ops); - const SCEV* getAddExpr(const SCEV* LHS, const SCEV* RHS) { - SmallVector<const SCEV*, 2> Ops; + const SCEV *getSCEV(Value *V); + + const SCEV *getConstant(ConstantInt *V); + const SCEV *getConstant(const APInt& Val); + const SCEV *getConstant(const Type *Ty, uint64_t V, bool isSigned = false); + const SCEV *getTruncateExpr(const SCEV *Op, const Type *Ty); + const SCEV *getZeroExtendExpr(const SCEV *Op, const Type *Ty); + const SCEV *getSignExtendExpr(const SCEV *Op, const Type *Ty); + const SCEV *getAnyExtendExpr(const SCEV *Op, const Type *Ty); + const SCEV *getAddExpr(SmallVectorImpl<const SCEV *> &Ops); + const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS) { + SmallVector<const SCEV *, 2> Ops; Ops.push_back(LHS); Ops.push_back(RHS); return getAddExpr(Ops); } - const SCEV* getAddExpr(const SCEV* Op0, const SCEV* Op1, - const SCEV* Op2) { - SmallVector<const SCEV*, 3> Ops; + const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, + const SCEV *Op2) { + SmallVector<const SCEV *, 3> Ops; Ops.push_back(Op0); Ops.push_back(Op1); Ops.push_back(Op2); return getAddExpr(Ops); } - const SCEV* getMulExpr(SmallVectorImpl<const SCEV*> &Ops); - const SCEV* getMulExpr(const SCEV* LHS, const SCEV* RHS) { - SmallVector<const SCEV*, 2> Ops; + const SCEV *getMulExpr(SmallVectorImpl<const SCEV *> &Ops); + const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS) { + SmallVector<const SCEV *, 2> Ops; Ops.push_back(LHS); Ops.push_back(RHS); return getMulExpr(Ops); } - const SCEV* getUDivExpr(const SCEV* LHS, const SCEV* RHS); - const SCEV* getAddRecExpr(const SCEV* Start, const SCEV* Step, + const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L); - const SCEV* getAddRecExpr(SmallVectorImpl<const SCEV*> &Operands, + const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands, const Loop *L); - const SCEV* getAddRecExpr(const SmallVectorImpl<const SCEV*> &Operands, + const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands, const Loop *L) { - SmallVector<const SCEV*, 4> NewOp(Operands.begin(), Operands.end()); + SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end()); return getAddRecExpr(NewOp, L); } - const SCEV* getSMaxExpr(const SCEV* LHS, const SCEV* RHS); - const SCEV* getSMaxExpr(SmallVectorImpl<const SCEV*> &Operands); - const SCEV* getUMaxExpr(const SCEV* LHS, const SCEV* RHS); - const SCEV* getUMaxExpr(SmallVectorImpl<const SCEV*> &Operands); - const SCEV* getSMinExpr(const SCEV* LHS, const SCEV* RHS); - const SCEV* getUMinExpr(const SCEV* LHS, const SCEV* RHS); - const SCEV* getUnknown(Value *V); - const SCEV* getCouldNotCompute(); + const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getSMaxExpr(SmallVectorImpl<const SCEV *> &Operands); + const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getUMaxExpr(SmallVectorImpl<const SCEV *> &Operands); + const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getUnknown(Value *V); + const SCEV *getCouldNotCompute(); /// getNegativeSCEV - Return the SCEV object corresponding to -V. /// - const SCEV* getNegativeSCEV(const SCEV* V); + const SCEV *getNegativeSCEV(const SCEV *V); /// getNotSCEV - Return the SCEV object corresponding to ~V. /// - const SCEV* getNotSCEV(const SCEV* V); + const SCEV *getNotSCEV(const SCEV *V); /// getMinusSCEV - Return LHS-RHS. /// - const SCEV* getMinusSCEV(const SCEV* LHS, - const SCEV* RHS); + const SCEV *getMinusSCEV(const SCEV *LHS, + const SCEV *RHS); /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion /// of the input value to the specified type. If the type must be /// extended, it is zero extended. - const SCEV* getTruncateOrZeroExtend(const SCEV* V, const Type *Ty); + const SCEV *getTruncateOrZeroExtend(const SCEV *V, const Type *Ty); /// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion /// of the input value to the specified type. If the type must be /// extended, it is sign extended. - const SCEV* getTruncateOrSignExtend(const SCEV* V, const Type *Ty); + const SCEV *getTruncateOrSignExtend(const SCEV *V, const Type *Ty); /// getNoopOrZeroExtend - Return a SCEV corresponding to a conversion of /// the input value to the specified type. If the type must be extended, /// it is zero extended. The conversion must not be narrowing. - const SCEV* getNoopOrZeroExtend(const SCEV* V, const Type *Ty); + const SCEV *getNoopOrZeroExtend(const SCEV *V, const Type *Ty); /// getNoopOrSignExtend - Return a SCEV corresponding to a conversion of /// the input value to the specified type. If the type must be extended, /// it is sign extended. The conversion must not be narrowing. - const SCEV* getNoopOrSignExtend(const SCEV* V, const Type *Ty); + const SCEV *getNoopOrSignExtend(const SCEV *V, const Type *Ty); /// getNoopOrAnyExtend - Return a SCEV corresponding to a conversion of /// the input value to the specified type. If the type must be extended, /// it is extended with unspecified bits. The conversion must not be /// narrowing. - const SCEV* getNoopOrAnyExtend(const SCEV* V, const Type *Ty); + const SCEV *getNoopOrAnyExtend(const SCEV *V, const Type *Ty); /// getTruncateOrNoop - Return a SCEV corresponding to a conversion of the /// input value to the specified type. The conversion must not be /// widening. - const SCEV* getTruncateOrNoop(const SCEV* V, const Type *Ty); + const SCEV *getTruncateOrNoop(const SCEV *V, const Type *Ty); /// getIntegerSCEV - Given a SCEVable type, create a constant for the /// specified signed integer value and return a SCEV for the constant. - const SCEV* getIntegerSCEV(int Val, const Type *Ty); + const SCEV *getIntegerSCEV(int Val, const Type *Ty); /// getUMaxFromMismatchedTypes - Promote the operands to the wider of /// the types using zero-extension, and then perform a umax operation /// with them. - const SCEV* getUMaxFromMismatchedTypes(const SCEV* LHS, - const SCEV* RHS); + const SCEV *getUMaxFromMismatchedTypes(const SCEV *LHS, + const SCEV *RHS); /// getUMinFromMismatchedTypes - Promote the operands to the wider of /// the types using zero-extension, and then perform a umin operation /// with them. - const SCEV* getUMinFromMismatchedTypes(const SCEV* LHS, - const SCEV* RHS); + const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, + const SCEV *RHS); /// hasSCEV - Return true if the SCEV for this value has already been /// computed. @@ -491,7 +491,7 @@ namespace llvm { /// setSCEV - Insert the specified SCEV into the map of current SCEVs for /// the specified value. - void setSCEV(Value *V, const SCEV* H); + void setSCEV(Value *V, const SCEV *H); /// getSCEVAtScope - Return a SCEV expression handle for the specified value /// at the specified scope in the program. The L value specifies a loop @@ -503,11 +503,11 @@ namespace llvm { /// /// In the case that a relevant loop exit value cannot be computed, the /// original value V is returned. - const SCEV* getSCEVAtScope(const SCEV *S, const Loop *L); + const SCEV *getSCEVAtScope(const SCEV *S, const Loop *L); /// getSCEVAtScope - This is a convenience function which does /// getSCEVAtScope(getSCEV(V), L). - const SCEV* getSCEVAtScope(Value *V, const Loop *L); + const SCEV *getSCEVAtScope(Value *V, const Loop *L); /// isLoopGuardedByCond - Test whether entry to the loop is protected by /// a conditional between LHS and RHS. This is used to help avoid max @@ -526,12 +526,12 @@ namespace llvm { /// loop-invariant backedge-taken count (see /// hasLoopInvariantBackedgeTakenCount). /// - const SCEV* getBackedgeTakenCount(const Loop *L); + const SCEV *getBackedgeTakenCount(const Loop *L); /// getMaxBackedgeTakenCount - Similar to getBackedgeTakenCount, except /// return the least SCEV value that is known never to be less than the /// actual backedge taken count. - const SCEV* getMaxBackedgeTakenCount(const Loop *L); + const SCEV *getMaxBackedgeTakenCount(const Loop *L); /// hasLoopInvariantBackedgeTakenCount - Return true if the specified loop /// has an analyzable loop-invariant backedge-taken count. @@ -548,15 +548,15 @@ namespace llvm { /// time, the minimum number of times S is divisible by 2. For example, /// given {4,+,8} it returns 2. If S is guaranteed to be 0, it returns the /// bitwidth of S. - uint32_t GetMinTrailingZeros(const SCEV* S); + uint32_t GetMinTrailingZeros(const SCEV *S); /// GetMinLeadingZeros - Determine the minimum number of zero bits that S is /// guaranteed to begin with (at every loop iteration). - uint32_t GetMinLeadingZeros(const SCEV* S); + uint32_t GetMinLeadingZeros(const SCEV *S); /// GetMinSignBits - Determine the minimum number of sign bits that S is /// guaranteed to begin with. - uint32_t GetMinSignBits(const SCEV* S); + uint32_t GetMinSignBits(const SCEV *S); virtual bool runOnFunction(Function &F); virtual void releaseMemory(); diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h index 816d49764d..2c8bcd742b 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpander.h +++ b/include/llvm/Analysis/ScalarEvolutionExpander.h @@ -53,7 +53,7 @@ namespace llvm { /// expandCodeFor - Insert code to directly compute the specified SCEV /// expression into the program. The inserted code is inserted into the /// specified block. - Value *expandCodeFor(const SCEV* SH, const Type *Ty, Instruction *IP) { + Value *expandCodeFor(const SCEV *SH, const Type *Ty, Instruction *IP) { Builder.SetInsertPoint(IP->getParent(), IP); return expandCodeFor(SH, Ty); } @@ -72,8 +72,8 @@ namespace llvm { /// expandAddToGEP - Expand a SCEVAddExpr with a pointer type into a GEP /// instead of using ptrtoint+arithmetic+inttoptr. - Value *expandAddToGEP(const SCEV* const *op_begin, - const SCEV* const *op_end, + Value *expandAddToGEP(const SCEV *const *op_begin, + const SCEV *const *op_end, const PointerType *PTy, const Type *Ty, Value *V); Value *expand(const SCEV *S); @@ -82,7 +82,7 @@ namespace llvm { /// expression into the program. The inserted code is inserted into the /// SCEVExpander's current insertion point. If a type is specified, the /// result will be expanded to have that type, with a cast if necessary. - Value *expandCodeFor(const SCEV* SH, const Type *Ty = 0); + Value *expandCodeFor(const SCEV *SH, const Type *Ty = 0); /// isInsertedInstruction - Return true if the specified instruction was /// inserted by the code rewriter. If so, the client should not modify the diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h index c54c86556c..d56404066b 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpressions.h +++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h @@ -53,8 +53,8 @@ namespace llvm { virtual const Type *getType() const; - const SCEV* replaceSymbolicValuesWithConcrete(const SCEV* Sym, - const SCEV* Conc, + const SCEV *replaceSymbolicValuesWithConcrete(const SCEV *Sym, + const SCEV *Conc, ScalarEvolution &SE) const { return this; } @@ -77,15 +77,15 @@ namespace llvm { /// class SCEVCastExpr : public SCEV { protected: - const SCEV* Op; + const SCEV *Op; const Type *Ty; - SCEVCastExpr(unsigned SCEVTy, const SCEV* op, const Type *ty); + SCEVCastExpr(unsigned SCEVTy, const SCEV *op, const Type *ty); public: virtual void Profile(FoldingSetNodeID &ID) const; - const SCEV* getOperand() const { return Op; } + const SCEV *getOperand() const { return Op; } virtual const Type *getType() const { return Ty; } virtual bool isLoopInvariant(const Loop *L) const { @@ -114,13 +114,13 @@ namespace llvm { class SCEVTruncateExpr : public SCEVCastExpr { friend class ScalarEvolution; - SCEVTruncateExpr(const SCEV* op, const Type *ty); + SCEVTruncateExpr(const SCEV *op, const Type *ty); public: - const SCEV* replaceSymbolicValuesWithConcrete(const SCEV* Sym, - const SCEV* Conc, + const SCEV *replaceSymbolicValuesWithConcrete(const SCEV *Sym, + const SCEV *Conc, ScalarEvolution &SE) const { - const SCEV* H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); + const SCEV *H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); if (H == Op) return this; return SE.getTruncateExpr(H, Ty); @@ -142,13 +142,13 @@ namespace llvm { class SCEVZeroExtendExpr : public SCEVCastExpr { friend class ScalarEvolution; - SCEVZeroExtendExpr(const SCEV* op, const Type *ty); + SCEVZeroExtendExpr(const SCEV *op, const Type *ty); public: - const SCEV* replaceSymbolicValuesWithConcrete(const SCEV* Sym, - const SCEV* Conc, + const SCEV *replaceSymbolicValuesWithConcrete(const SCEV *Sym, + const SCEV *Conc, ScalarEvolution &SE) const { - const SCEV* H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); + const SCEV *H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); if (H == Op) return this; return SE.getZeroExtendExpr(H, Ty); @@ -170,13 +170,13 @@ namespace llvm { class SCEVSignExtendExpr : public SCEVCastExpr { friend class ScalarEvolution; - SCEVSignExtendExpr(const SCEV* op, const Type *ty); + SCEVSignExtendExpr(const SCEV *op, const Type *ty); public: - const SCEV* replaceSymbolicValuesWithConcrete(const SCEV* Sym, - const SCEV* Conc, + const SCEV *replaceSymbolicValuesWithConcrete(const SCEV *Sym, + const SCEV *Conc, ScalarEvolution &SE) const { - const SCEV* H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); + const SCEV *H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); if (H == Op) return this; return SE.getSignExtendExpr(H, Ty); @@ -198,22 +198,24 @@ namespace llvm { /// class SCEVNAryExpr : public SCEV { protected: - SmallVector<const SCEV*, 8> Operands; + SmallVector<const SCEV *, 8> Operands; - SCEVNAryExpr(enum SCEVTypes T, const SmallVectorImpl<const SCEV*> &ops) + SCEVNAryExpr(enum SCEVTypes T, const SmallVectorImpl<const SCEV *> &ops) : SCEV(T), Operands(ops.begin(), ops.end()) {} public: virtual void Profile(FoldingSetNodeID &ID) const; unsigned getNumOperands() const { return (unsigned)Operands.size(); } - const SCEV* getOperand(unsigned i) const { + const SCEV *getOperand(unsigned i) const { assert(i < Operands.size() && "Operand index out of range!"); return Operands[i]; } - const SmallVectorImpl<const SCEV*> &getOperands() const { return Operands; } - typedef SmallVectorImpl<const SCEV*>::const_iterator op_iterator; + const SmallVectorImpl<const SCEV *> &getOperands() const { + return Operands; + } + typedef SmallVectorImpl<const SCEV *>::const_iterator op_iterator; op_iterator op_begin() const { return Operands.begin(); } op_iterator op_end() const { return Operands.end(); } @@ -260,12 +262,12 @@ namespace llvm { class SCEVCommutativeExpr : public SCEVNAryExpr { protected: SCEVCommutativeExpr(enum SCEVTypes T, - const SmallVectorImpl<const SCEV*> &ops) + const SmallVectorImpl<const SCEV *> &ops) : SCEVNAryExpr(T, ops) {} public: - const SCEV* replaceSymbolicValuesWithConcrete(const SCEV* Sym, - const SCEV* Conc, + const SCEV *replaceSymbolicValuesWithConcrete(const SCEV *Sym, + const SCEV *Conc, ScalarEvolution &SE) const; virtual const char *getOperationStr() const = 0; @@ -289,7 +291,7 @@ namespace llvm { class SCEVAddExpr : public SCEVCommutativeExpr { friend class ScalarEvolution; - explicit SCEVAddExpr(const SmallVectorImpl<const SCEV*> &ops) + explicit SCEVAddExpr(const SmallVectorImpl<const SCEV *> &ops) : SCEVCommutativeExpr(scAddExpr, ops) { } @@ -309,7 +311,7 @@ namespace llvm { class SCEVMulExpr : public SCEVCommutativeExpr { friend class ScalarEvolution; - explicit SCEVMulExpr(const SmallVectorImpl<const SCEV*> &ops) + explicit SCEVMulExpr(const SmallVectorImpl<const SCEV *> &ops) : SCEVCommutativeExpr(scMulExpr, ops) { } @@ -330,16 +332,16 @@ namespace llvm { class SCEVUDivExpr : public SCEV { friend class ScalarEvolution; - const SCEV* LHS; - const SCEV* RHS; - SCEVUDivExpr(const SCEV* lhs, const SCEV* rhs) + const SCEV *LHS; + const SCEV *RHS; + SCEVUDivExpr(const SCEV *lhs, const SCEV *rhs) : SCEV(scUDivExpr), LHS(lhs), RHS(rhs) {} public: virtual void Profile(FoldingSetNodeID &ID) const; - const SCEV* getLHS() const { return LHS; } - const SCEV* getRHS() const { return RHS; } + const SCEV *getLHS() const { return LHS; } + const SCEV *getRHS() const { return RHS; } virtual bool isLoopInvariant(const Loop *L) const { return LHS->isLoopInvariant(L) && RHS->isLoopInvariant(L); @@ -350,11 +352,11 @@ namespace llvm { RHS->hasComputableLoopEvolution(L); } - const SCEV* replaceSymbolicValuesWithConcrete(const SCEV* Sym, - const SCEV* Conc, + const SCEV *replaceSymbolicValuesWithConcrete(const SCEV *Sym, + const SCEV *Conc, ScalarEvolution &SE) const { - const SCEV* L = LHS->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); - const SCEV* R = RHS->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); + const SCEV *L = LHS->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); + const SCEV *R = RHS->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); if (L == LHS && R == RHS) return this; else @@ -389,7 +391,7 @@ namespace llvm { const Loop *L; - SCEVAddRecExpr(const SmallVectorImpl<const SCEV*> &ops, const Loop *l) + SCEVAddRecExpr(const SmallVectorImpl<const SCEV *> &ops, const Loop *l) : SCEVNAryExpr(scAddRecExpr, ops), L(l) { for (size_t i = 0, e = Operands.size(); i != e; ++i) assert(Operands[i]->isLoopInvariant(l) && @@ -399,15 +401,16 @@ namespace llvm { public: virtual void Profile(FoldingSetNodeID &ID) const; - const SCEV* getStart() const { return Operands[0]; } + const SCEV *getStart() const { return Operands[0]; } const Loop *getLoop() const { return L; } /// getStepRecurrence - This method constructs and returns the recurrence /// indicating how much this expression steps by. If this is a polynomial /// of degree N, it returns a chrec of degree N-1. - const SCEV* getStepRecurrence(ScalarEvolution &SE) const { + const SCEV *getStepRecurrence(ScalarEvolution &SE) const { if (isAffine()) return getOperand(1); - return SE.getAddRecExpr(SmallVector<const SCEV*, 3>(op_begin()+1,op_end()), + return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1, + op_end()), getLoop()); } @@ -435,7 +438,7 @@ namespace llvm { /// evaluateAtIteration - Return the value of this chain of recurrences at /// the specified iteration number. - const SCEV* evaluateAtIteration(const SCEV* It, ScalarEvolution &SE) const; + const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const; /// getNumIterationsInRange - Return the number of iterations of this loop /// that produce values in the specified constant range. Another way of @@ -443,11 +446,11 @@ namespace llvm { /// value is not in the condition, thus computing the exit count. If the /// iteration count can't be computed, an instance of SCEVCouldNotCompute is /// returned. - const SCEV* getNumIterationsInRange(ConstantRange Range, + const SCEV *getNumIterationsInRange(ConstantRange Range, ScalarEvolution &SE) const; - const SCEV* replaceSymbolicValuesWithConcrete(const SCEV* Sym, - const SCEV* Conc, + const SCEV *replaceSymbolicValuesWithConcrete(const SCEV *Sym, + const SCEV *Conc, ScalarEvolution &SE) const; virtual void print(raw_ostream &OS) const; @@ -466,7 +469,7 @@ namespace llvm { class SCEVSMaxExpr : public SCEVCommutativeExpr { friend class ScalarEvolution; - explicit SCEVSMaxExpr(const SmallVectorImpl<const SCEV*> &ops) + explicit SCEVSMaxExpr(const SmallVectorImpl<const SCEV *> &ops) : SCEVCommutativeExpr(scSMaxExpr, ops) { } @@ -487,7 +490,7 @@ namespace llvm { class SCEVUMaxExpr : public SCEVCommutativeExpr { friend class ScalarEvolution; - explicit SCEVUMaxExpr(const SmallVectorImpl<const SCEV*> &ops) + explicit SCEVUMaxExpr(const SmallVectorImpl<const SCEV *> &ops) : SCEVCommutativeExpr(scUMaxExpr, ops) { } @@ -524,8 +527,8 @@ namespace llvm { return false; // not computable } - const SCEV* replaceSymbolicValuesWithConcrete(const SCEV* Sym, - const SCEV* Conc, + const SCEV *replaceSymbolicValuesWithConcrete(const SCEV *Sym, + const SCEV *Conc, ScalarEvolution &SE) const { if (&*Sym == this) return Conc; return this; diff --git a/lib/Analysis/IVUsers.cpp b/lib/Analysis/IVUsers.cpp index caeb14bef3..317c869164 100644 --- a/lib/Analysis/IVUsers.cpp +++ b/lib/Analysis/IVUsers.cpp @@ -39,7 +39,7 @@ Pass *llvm::createIVUsersPass() { /// containsAddRecFromDifferentLoop - Determine whether expression S involves a /// subexpression that is an AddRec from a loop other than L. An outer loop /// of L is OK, but not an inner loop nor a disjoint loop. -static bool containsAddRecFromDifferentLoop(const SCEV* S, Loop *L) { +static bool containsAddRecFromDifferentLoop(const SCEV *S, Loop *L) { // This is very common, put it first. if (isa<SCEVConstant>(S)) return false; @@ -80,10 +80,10 @@ static bool containsAddRecFromDifferentLoop(const SCEV* S, Loop *L) { /// a mix of loop invariant and loop variant expressions. The start cannot, /// however, contain an AddRec from a different loop, unless that loop is an /// outer loop of the current loop. -static bool getSCEVStartAndStride(const SCEV* &SH, Loop *L, Loop *UseLoop, - const SCEV* &Start, const SCEV* &Stride, +static bool getSCEVStartAndStride(const SCEV *&SH, Loop *L, Loop *UseLoop, + const SCEV *&Start, const SCEV *&Stride, ScalarEvolution *SE, DominatorTree *DT) { - const SCEV* TheAddRec = Start; // Initialize to zero. + const SCEV *TheAddRec = Start; // Initialize to zero. // If the outer level is an AddExpr, the operands are all start values except // for a nested AddRecExpr. @@ -109,9 +109,9 @@ static bool getSCEVStartAndStride(const SCEV* &SH, Loop *L, Loop *UseLoop, / |