X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FScalarEvolution.cpp;h=3a09f2f9d7b170892301fc124c7f8a03f80f2e32;hb=2a0f3ccc9c10186309d5d6a0c4cebe8b477f352a;hp=d2c3f58e9cfd40e6b5f6f6f0d66e6e426852fdd0;hpb=5078f84c82814e4d33846f9ef54281619d362f8a;p=oota-llvm.git diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index d2c3f58e9cf..3a09f2f9d7b 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -63,6 +63,7 @@ #include "llvm/Constants.h" #include "llvm/DerivedTypes.h" #include "llvm/GlobalVariable.h" +#include "llvm/GlobalAlias.h" #include "llvm/Instructions.h" #include "llvm/LLVMContext.h" #include "llvm/Operator.h" @@ -73,7 +74,6 @@ #include "llvm/Assembly/Writer.h" #include "llvm/Target/TargetData.h" #include "llvm/Support/CommandLine.h" -#include "llvm/Support/Compiler.h" #include "llvm/Support/ConstantRange.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/GetElementPtrTypeIterator.h" @@ -121,11 +121,6 @@ void SCEV::dump() const { errs() << '\n'; } -void SCEV::print(std::ostream &o) const { - raw_os_ostream OS(o); - print(OS); -} - bool SCEV::isZero() const { if (const SCEVConstant *SC = dyn_cast(this)) return SC->getValue()->isZero(); @@ -211,6 +206,10 @@ bool SCEVCastExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { return Op->dominates(BB, DT); } +bool SCEVCastExpr::properlyDominates(BasicBlock *BB, DominatorTree *DT) const { + return Op->properlyDominates(BB, DT); +} + SCEVTruncateExpr::SCEVTruncateExpr(const FoldingSetNodeID &ID, const SCEV *op, const Type *ty) : SCEVCastExpr(ID, scTruncate, op, ty) { @@ -264,10 +263,22 @@ bool SCEVNAryExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { return true; } +bool SCEVNAryExpr::properlyDominates(BasicBlock *BB, DominatorTree *DT) const { + for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { + if (!getOperand(i)->properlyDominates(BB, DT)) + return false; + } + return true; +} + bool SCEVUDivExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { return LHS->dominates(BB, DT) && RHS->dominates(BB, DT); } +bool SCEVUDivExpr::properlyDominates(BasicBlock *BB, DominatorTree *DT) const { + return LHS->properlyDominates(BB, DT) && RHS->properlyDominates(BB, DT); +} + void SCEVUDivExpr::print(raw_ostream &OS) const { OS << "(" << *LHS << " /u " << *RHS << ")"; } @@ -287,7 +298,7 @@ bool SCEVAddRecExpr::isLoopInvariant(const Loop *QueryLoop) const { return false; // This recurrence is variant w.r.t. QueryLoop if QueryLoop contains L. - if (QueryLoop->contains(L->getHeader())) + if (QueryLoop->contains(L)) return false; // This recurrence is variant w.r.t. QueryLoop if any of its operands @@ -322,7 +333,7 @@ bool SCEVUnknown::isLoopInvariant(const Loop *L) const { // Instructions are never considered invariant in the function body // (null loop) because they are defined within the "loop". if (Instruction *I = dyn_cast(V)) - return L && !L->contains(I->getParent()); + return L && !L->contains(I); return true; } @@ -332,6 +343,12 @@ bool SCEVUnknown::dominates(BasicBlock *BB, DominatorTree *DT) const { return true; } +bool SCEVUnknown::properlyDominates(BasicBlock *BB, DominatorTree *DT) const { + if (Instruction *I = dyn_cast(getValue())) + return DT->properlyDominates(I->getParent(), BB); + return true; +} + const Type *SCEVUnknown::getType() const { return V->getType(); } @@ -383,12 +400,16 @@ namespace { /// SCEVComplexityCompare - Return true if the complexity of the LHS is less /// than the complexity of the RHS. This comparator is used to canonicalize /// expressions. - class VISIBILITY_HIDDEN SCEVComplexityCompare { + class SCEVComplexityCompare { LoopInfo *LI; public: explicit SCEVComplexityCompare(LoopInfo *li) : LI(li) {} bool operator()(const SCEV *LHS, const SCEV *RHS) const { + // Fast-path: SCEVs are uniqued so we can do a quick equality check. + if (LHS == RHS) + return false; + // Primarily, sort the SCEVs by their getSCEVType(). if (LHS->getSCEVType() != RHS->getSCEVType()) return LHS->getSCEVType() < RHS->getSCEVType(); @@ -1169,7 +1190,8 @@ namespace { /// getAddExpr - Get a canonical add expression, or something simpler if /// possible. -const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl &Ops) { +const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl &Ops, + bool HasNUW, bool HasNSW) { assert(!Ops.empty() && "Cannot get empty add!"); if (Ops.size() == 1) return Ops[0]; #ifndef NDEBUG @@ -1219,7 +1241,7 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl &Ops) { return Mul; Ops.erase(Ops.begin()+i, Ops.begin()+i+2); Ops.push_back(Mul); - return getAddExpr(Ops); + return getAddExpr(Ops, HasNUW, HasNSW); } // Check for truncates. If all the operands are truncated from the same @@ -1274,7 +1296,7 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl &Ops) { } if (Ok) { // Evaluate the expression in the larger type. - const SCEV *Fold = getAddExpr(LargeOps); + const SCEV *Fold = getAddExpr(LargeOps, HasNUW, HasNSW); // If it folds to something simple, use it. Otherwise, don't. if (isa(Fold) || isa(Fold)) return getTruncateExpr(Fold, DstType); @@ -1435,10 +1457,13 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl &Ops) { LIOps.push_back(AddRec->getStart()); SmallVector AddRecOps(AddRec->op_begin(), - AddRec->op_end()); + AddRec->op_end()); AddRecOps[0] = getAddExpr(LIOps); + // It's tempting to propagate NUW/NSW flags here, but nuw/nsw addition + // is not associative so this isn't necessarily safe. const SCEV *NewRec = getAddRecExpr(AddRecOps, AddRec->getLoop()); + // If all of the other operands were loop invariant, we are done. if (Ops.size() == 1) return NewRec; @@ -1494,16 +1519,19 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl &Ops) { ID.AddPointer(Ops[i]); void *IP = 0; if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; - SCEV *S = SCEVAllocator.Allocate(); + SCEVAddExpr *S = SCEVAllocator.Allocate(); new (S) SCEVAddExpr(ID, Ops); UniqueSCEVs.InsertNode(S, IP); + if (HasNUW) S->setHasNoUnsignedWrap(true); + if (HasNSW) S->setHasNoSignedWrap(true); return S; } /// getMulExpr - Get a canonical multiply expression, or something simpler if /// possible. -const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl &Ops) { +const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl &Ops, + bool HasNUW, bool HasNSW) { assert(!Ops.empty() && "Cannot get empty mul!"); #ifndef NDEBUG for (unsigned i = 1, e = Ops.size(); i != e; ++i) @@ -1611,6 +1639,8 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl &Ops) { } } + // It's tempting to propagate the NSW flag here, but nsw multiplication + // is not associative so this isn't necessarily safe. const SCEV *NewRec = getAddRecExpr(NewOps, AddRec->getLoop()); // If all of the other operands were loop invariant, we are done. @@ -1666,9 +1696,11 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl &Ops) { ID.AddPointer(Ops[i]); void *IP = 0; if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; - SCEV *S = SCEVAllocator.Allocate(); + SCEVMulExpr *S = SCEVAllocator.Allocate(); new (S) SCEVMulExpr(ID, Ops); UniqueSCEVs.InsertNode(S, IP); + if (HasNUW) S->setHasNoUnsignedWrap(true); + if (HasNSW) S->setHasNoSignedWrap(true); return S; } @@ -1775,7 +1807,8 @@ const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS, /// getAddRecExpr - Get an add recurrence expression for the specified loop. /// Simplify the expression as much as possible. const SCEV *ScalarEvolution::getAddRecExpr(const SCEV *Start, - const SCEV *Step, const Loop *L) { + const SCEV *Step, const Loop *L, + bool HasNUW, bool HasNSW) { SmallVector Operands; Operands.push_back(Start); if (const SCEVAddRecExpr *StepChrec = dyn_cast(Step)) @@ -1786,14 +1819,15 @@ const SCEV *ScalarEvolution::getAddRecExpr(const SCEV *Start, } Operands.push_back(Step); - return getAddRecExpr(Operands, L); + return getAddRecExpr(Operands, L, HasNUW, HasNSW); } /// getAddRecExpr - Get an add recurrence expression for the specified loop. /// Simplify the expression as much as possible. const SCEV * ScalarEvolution::getAddRecExpr(SmallVectorImpl &Operands, - const Loop *L) { + const Loop *L, + bool HasNUW, bool HasNSW) { if (Operands.size() == 1) return Operands[0]; #ifndef NDEBUG for (unsigned i = 1, e = Operands.size(); i != e; ++i) @@ -1804,15 +1838,15 @@ ScalarEvolution::getAddRecExpr(SmallVectorImpl &Operands, if (Operands.back()->isZero()) { Operands.pop_back(); - return getAddRecExpr(Operands, L); // {X,+,0} --> X + return getAddRecExpr(Operands, L, HasNUW, HasNSW); // {X,+,0} --> X } // Canonicalize nested AddRecs in by nesting them in order of loop depth. if (const SCEVAddRecExpr *NestedAR = dyn_cast(Operands[0])) { - const Loop* NestedLoop = NestedAR->getLoop(); + const Loop *NestedLoop = NestedAR->getLoop(); if (L->getLoopDepth() < NestedLoop->getLoopDepth()) { SmallVector NestedOperands(NestedAR->op_begin(), - NestedAR->op_end()); + NestedAR->op_end()); Operands[0] = NestedAR->getStart(); // AddRecs require their operands be loop-invariant with respect to their // loops. Don't perform this transformation if it would break this @@ -1833,7 +1867,7 @@ ScalarEvolution::getAddRecExpr(SmallVectorImpl &Operands, } if (AllInvariant) // Ok, both add recurrences are valid after the transformation. - return getAddRecExpr(NestedOperands, NestedLoop); + return getAddRecExpr(NestedOperands, NestedLoop, HasNUW, HasNSW); } // Reset Operands to its original state. Operands[0] = NestedAR; @@ -1848,9 +1882,11 @@ ScalarEvolution::getAddRecExpr(SmallVectorImpl &Operands, ID.AddPointer(L); void *IP = 0; if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; - SCEV *S = SCEVAllocator.Allocate(); + SCEVAddRecExpr *S = SCEVAllocator.Allocate(); new (S) SCEVAddRecExpr(ID, Operands, L); UniqueSCEVs.InsertNode(S, IP); + if (HasNUW) S->setHasNoUnsignedWrap(true); + if (HasNSW) S->setHasNoSignedWrap(true); return S; } @@ -2410,7 +2446,7 @@ ScalarEvolution::ForgetSymbolicName(Instruction *I, const SCEV *SymName) { Instruction *I = Worklist.pop_back_val(); if (!Visited.insert(I)) continue; - std::map::iterator It = + std::map::iterator It = Scalars.find(static_cast(I)); if (It != Scalars.end()) { // Short-circuit the def-use traversal if the symbolic name @@ -2424,9 +2460,10 @@ ScalarEvolution::ForgetSymbolicName(Instruction *I, const SCEV *SymName) { // count information isn't going to change anything. In the later // case, createNodeForPHI will perform the necessary updates on its // own when it gets to that point. - if (!isa(I) || !isa(It->second)) + if (!isa(I) || !isa(It->second)) { + ValuesAtScopes.erase(It->second); Scalars.erase(It); - ValuesAtScopes.erase(I); + } } PushDefUseChildren(I, Worklist); @@ -2560,8 +2597,9 @@ const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) { /// createNodeForGEP - Expand GEP instructions into add and multiply /// operations. This allows them to be analyzed by regular SCEV code. /// -const SCEV *ScalarEvolution::createNodeForGEP(Operator *GEP) { +const SCEV *ScalarEvolution::createNodeForGEP(GEPOperator *GEP) { + bool InBounds = GEP->isInBounds(); const Type *IntPtrTy = getEffectiveSCEVType(GEP->getType()); Value *Base = GEP->getOperand(0); // Don't attempt to analyze GEPs over unsized objects. @@ -2578,18 +2616,23 @@ const SCEV *ScalarEvolution::createNodeForGEP(Operator *GEP) { // For a struct, add the member offset. unsigned FieldNo = cast(Index)->getZExtValue(); TotalOffset = getAddExpr(TotalOffset, - getFieldOffsetExpr(STy, FieldNo)); + getFieldOffsetExpr(STy, FieldNo), + /*HasNUW=*/false, /*HasNSW=*/InBounds); } else { // For an array, add the element offset, explicitly scaled. const SCEV *LocalOffset = getSCEV(Index); if (!isa(LocalOffset->getType())) // Getelementptr indicies are signed. LocalOffset = getTruncateOrSignExtend(LocalOffset, IntPtrTy); - LocalOffset = getMulExpr(LocalOffset, getAllocSizeExpr(*GTI)); - TotalOffset = getAddExpr(TotalOffset, LocalOffset); + // Lower "inbounds" GEPs to NSW arithmetic. + LocalOffset = getMulExpr(LocalOffset, getAllocSizeExpr(*GTI), + /*HasNUW=*/false, /*HasNSW=*/InBounds); + TotalOffset = getAddExpr(TotalOffset, LocalOffset, + /*HasNUW=*/false, /*HasNSW=*/InBounds); } } - return getAddExpr(getSCEV(Base), TotalOffset); + return getAddExpr(getSCEV(Base), TotalOffset, + /*HasNUW=*/false, /*HasNSW=*/InBounds); } /// GetMinTrailingZeros - Determine the minimum number of zero bits that S is @@ -2911,15 +2954,23 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) { return getIntegerSCEV(0, V->getType()); else if (isa(V)) return getIntegerSCEV(0, V->getType()); + else if (GlobalAlias *GA = dyn_cast(V)) + return GA->mayBeOverridden() ? getUnknown(V) : getSCEV(GA->getAliasee()); else return getUnknown(V); Operator *U = cast(V); switch (Opcode) { case Instruction::Add: + // Don't transfer the NSW and NUW bits from the Add instruction to the + // Add expression, because the Instruction may be guarded by control + // flow and the no-overflow bits may not be valid for the expression in + // any context. return getAddExpr(getSCEV(U->getOperand(0)), getSCEV(U->getOperand(1))); case Instruction::Mul: + // Don't transfer the NSW and NUW bits from the Mul instruction to the + // Mul expression, as with Add. return getMulExpr(getSCEV(U->getOperand(0)), getSCEV(U->getOperand(1))); case Instruction::UDiv: @@ -2969,8 +3020,20 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) { const SCEV *LHS = getSCEV(U->getOperand(0)); const APInt &CIVal = CI->getValue(); if (GetMinTrailingZeros(LHS) >= - (CIVal.getBitWidth() - CIVal.countLeadingZeros())) - return getAddExpr(LHS, getSCEV(U->getOperand(1))); + (CIVal.getBitWidth() - CIVal.countLeadingZeros())) { + // Build a plain add SCEV. + const SCEV *S = getAddExpr(LHS, getSCEV(CI)); + // If the LHS of the add was an addrec and it has no-wrap flags, + // transfer the no-wrap flags, since an or won't introduce a wrap. + if (const SCEVAddRecExpr *NewAR = dyn_cast(S)) { + const SCEVAddRecExpr *OldAR = cast(LHS); + if (OldAR->hasNoUnsignedWrap()) + const_cast(NewAR)->setHasNoUnsignedWrap(true); + if (OldAR->hasNoSignedWrap()) + const_cast(NewAR)->setHasNoSignedWrap(true); + } + return S; + } } break; case Instruction::Xor: @@ -3078,7 +3141,7 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) { // expressions we handle are GEPs and address literals. case Instruction::GetElementPtr: - return createNodeForGEP(U); + return createNodeForGEP(cast(U)); case Instruction::PHI: return createNodeForPHI(cast(U)); @@ -3189,7 +3252,7 @@ ScalarEvolution::getBackedgeTakenInfo(const Loop *L) { // update the value. The temporary CouldNotCompute value tells SCEV // code elsewhere that it shouldn't attempt to request a new // backedge-taken count, which could result in infinite recursion. - std::pair::iterator, bool> Pair = + std::pair::iterator, bool> Pair = BackedgeTakenCounts.insert(std::make_pair(L, getCouldNotCompute())); if (Pair.second) { BackedgeTakenInfo ItCount = ComputeBackedgeTakenCount(L); @@ -3213,9 +3276,8 @@ ScalarEvolution::getBackedgeTakenInfo(const Loop *L) { // Now that we know more about the trip count for this loop, forget any // existing SCEV values for PHI nodes in this loop since they are only // conservative estimates made without the benefit of trip count - // information. This is similar to the code in - // forgetLoopBackedgeTakenCount, except that it handles SCEVUnknown PHI - // nodes specially. + // information. This is similar to the code in forgetLoop, except that + // it handles SCEVUnknown PHI nodes specially. if (ItCount.hasAnyInfo()) { SmallVector Worklist; PushLoopPHIs(L, Worklist); @@ -3225,7 +3287,7 @@ ScalarEvolution::getBackedgeTakenInfo(const Loop *L) { Instruction *I = Worklist.pop_back_val(); if (!Visited.insert(I)) continue; - std::map::iterator It = + std::map::iterator It = Scalars.find(static_cast(I)); if (It != Scalars.end()) { // SCEVUnknown for a PHI either means that it has an unrecognized @@ -3234,9 +3296,10 @@ ScalarEvolution::getBackedgeTakenInfo(const Loop *L) { // count information isn't going to change anything. In the later // case, createNodeForPHI will perform the necessary updates on its // own when it gets to that point. - if (!isa(I) || !isa(It->second)) + if (!isa(I) || !isa(It->second)) { + ValuesAtScopes.erase(It->second); Scalars.erase(It); - ValuesAtScopes.erase(I); + } if (PHINode *PN = dyn_cast(I)) ConstantEvolutionLoopExitValue.erase(PN); } @@ -3248,13 +3311,14 @@ ScalarEvolution::getBackedgeTakenInfo(const Loop *L) { return Pair.first->second; } -/// forgetLoopBackedgeTakenCount - This method should be called by the -/// client when it has changed a loop in a way that may effect -/// ScalarEvolution's ability to compute a trip count, or if the loop -/// is deleted. -void ScalarEvolution::forgetLoopBackedgeTakenCount(const Loop *L) { +/// forgetLoop - This method should be called by the client when it has +/// changed a loop in a way that may effect ScalarEvolution's ability to +/// compute a trip count, or if the loop is deleted. +void ScalarEvolution::forgetLoop(const Loop *L) { + // Drop any stored trip count value. BackedgeTakenCounts.erase(L); + // Drop information about expressions based on loop-header PHIs. SmallVector Worklist; PushLoopPHIs(L, Worklist); @@ -3263,11 +3327,11 @@ void ScalarEvolution::forgetLoopBackedgeTakenCount(const Loop *L) { Instruction *I = Worklist.pop_back_val(); if (!Visited.insert(I)) continue; - std::map::iterator It = + std::map::iterator It = Scalars.find(static_cast(I)); if (It != Scalars.end()) { + ValuesAtScopes.erase(It->second); Scalars.erase(It); - ValuesAtScopes.erase(I); if (PHINode *PN = dyn_cast(I)) ConstantEvolutionLoopExitValue.erase(PN); } @@ -3280,7 +3344,7 @@ void ScalarEvolution::forgetLoopBackedgeTakenCount(const Loop *L) { /// of the specified loop will execute. ScalarEvolution::BackedgeTakenInfo ScalarEvolution::ComputeBackedgeTakenCount(const Loop *L) { - SmallVector ExitingBlocks; + SmallVector ExitingBlocks; L->getExitingBlocks(ExitingBlocks); // Examine all exits and pick the most conservative values. @@ -3591,7 +3655,7 @@ EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, ConstantInt *C, /// the addressed element of the initializer or null if the index expression is /// invalid. static Constant * -GetAddressedElementFromGlobal(LLVMContext &Context, GlobalVariable *GV, +GetAddressedElementFromGlobal(GlobalVariable *GV, const std::vector &Indices) { Constant *Init = GV->getInitializer(); for (unsigned i = 0, e = Indices.size(); i != e; ++i) { @@ -3679,7 +3743,7 @@ ScalarEvolution::ComputeLoadConstantCompareBackedgeTakenCount( // Form the GEP offset. Indexes[VarIdxNum] = Val; - Constant *Result = GetAddressedElementFromGlobal(getContext(), GV, Indexes); + Constant *Result = GetAddressedElementFromGlobal(GV, Indexes); if (Result == 0) break; // Cannot compute! // Evaluate the condition for this iteration. @@ -3721,7 +3785,7 @@ static PHINode *getConstantEvolvingPHI(Value *V, const Loop *L) { // If this is not an instruction, or if this is an instruction outside of the // loop, it can't be derived from a loop PHI. Instruction *I = dyn_cast(V); - if (I == 0 || !L->contains(I->getParent())) return 0; + if (I == 0 || !L->contains(I)) return 0; if (PHINode *PN = dyn_cast(I)) { if (L->getHeader() == I->getParent()) @@ -3758,29 +3822,26 @@ static PHINode *getConstantEvolvingPHI(Value *V, const Loop *L) { /// getConstantEvolvingPHI predicate, evaluate its value assuming the PHI node /// in the loop has the value PHIVal. If we can't fold this expression for some /// reason, return null. -static Constant *EvaluateExpression(Value *V, Constant *PHIVal) { +static Constant *EvaluateExpression(Value *V, Constant *PHIVal, + const TargetData *TD) { if (isa(V)) return PHIVal; if (Constant *C = dyn_cast(V)) return C; if (GlobalValue *GV = dyn_cast(V)) return GV; Instruction *I = cast(V); - LLVMContext &Context = I->getParent()->getContext(); std::vector Operands; Operands.resize(I->getNumOperands()); for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { - Operands[i] = EvaluateExpression(I->getOperand(i), PHIVal); + Operands[i] = EvaluateExpression(I->getOperand(i), PHIVal, TD); if (Operands[i] == 0) return 0; } if (const CmpInst *CI = dyn_cast(I)) - return ConstantFoldCompareInstOperands(CI->getPredicate(), - &Operands[0], Operands.size(), - Context); - else - return ConstantFoldInstOperands(I->getOpcode(), I->getType(), - &Operands[0], Operands.size(), - Context); + return ConstantFoldCompareInstOperands(CI->getPredicate(), Operands[0], + Operands[1], TD); + return ConstantFoldInstOperands(I->getOpcode(), I->getType(), + &Operands[0], Operands.size(), TD); } /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is @@ -3789,7 +3850,7 @@ static Constant *EvaluateExpression(Value *V, Constant *PHIVal) { /// involving constants, fold it. Constant * ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN, - const APInt& BEs, + const APInt &BEs, const Loop *L) { std::map::iterator I = ConstantEvolutionLoopExitValue.find(PN); @@ -3826,7 +3887,7 @@ ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN, return RetVal = PHIVal; // Got exit value! // Compute the value of the PHI node for the next iteration. - Constant *NextPHI = EvaluateExpression(BEValue, PHIVal); + Constant *NextPHI = EvaluateExpression(BEValue, PHIVal, TD); if (NextPHI == PHIVal) return RetVal = NextPHI; // Stopped evolving! if (NextPHI == 0) @@ -3867,7 +3928,7 @@ ScalarEvolution::ComputeBackedgeTakenCountExhaustively(const Loop *L, for (Constant *PHIVal = StartCST; IterationNum != MaxIterations; ++IterationNum) { ConstantInt *CondVal = - dyn_cast_or_null(EvaluateExpression(Cond, PHIVal)); + dyn_cast_or_null(EvaluateExpression(Cond, PHIVal, TD)); // Couldn't symbolically evaluate. if (!CondVal) return getCouldNotCompute(); @@ -3878,7 +3939,7 @@ ScalarEvolution::ComputeBackedgeTakenCountExhaustively(const Loop *L, } // Compute the value of the PHI node for the next iteration. - Constant *NextPHI = EvaluateExpression(BEValue, PHIVal); + Constant *NextPHI = EvaluateExpression(BEValue, PHIVal, TD); if (NextPHI == 0 || NextPHI == PHIVal) return getCouldNotCompute();// Couldn't evaluate or not making progress... PHIVal = NextPHI; @@ -3888,7 +3949,7 @@ ScalarEvolution::ComputeBackedgeTakenCountExhaustively(const Loop *L, return getCouldNotCompute(); } -/// getSCEVAtScope - Return a SCEV expression handle for the specified value +/// getSCEVAtScope - Return a SCEV expression for the specified value /// at the specified scope in the program. The L value specifies a loop /// nest to evaluate the expression at, where null is the top-level or a /// specified loop is immediately inside of the loop. @@ -3899,8 +3960,20 @@ ScalarEvolution::ComputeBackedgeTakenCountExhaustively(const Loop *L, /// In the case that a relevant loop exit value cannot be computed, the /// original value V is returned. const SCEV *ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) { - // FIXME: this should be turned into a virtual method on SCEV! + // Check to see if we've folded this expression at this loop before. + std::map &Values = ValuesAtScopes[V]; + std::pair::iterator, bool> Pair = + Values.insert(std::make_pair(L, static_cast(0))); + if (!Pair.second) + return Pair.first->second ? Pair.first->second : V; + // Otherwise compute it. + const SCEV *C = computeSCEVAtScope(V, L); + ValuesAtScopes[V][L] = C; + return C; +} + +const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) { if (isa(V)) return V; // If this instruction is evolved from a constant-evolving PHI, compute the @@ -3933,13 +4006,6 @@ const SCEV *ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) { // the arguments into constants, and if so, try to constant propagate the // result. This is particularly useful for computing loop exit values. if (CanConstantFold(I)) { - // Check to see if we've folded this instruction at this loop before. - std::map &Values = ValuesAtScopes[I]; - std::pair::iterator, bool> Pair = - Values.insert(std::make_pair(L, static_cast(0))); - if (!Pair.second) - return Pair.first->second ? &*getSCEV(Pair.first->second) : V; - std::vector Operands; Operands.reserve(I->getNumOperands()); for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { @@ -3953,7 +4019,7 @@ const SCEV *ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) { if (!isSCEVable(Op->getType())) return V; - const SCEV* OpV = getSCEVAtScope(Op, L); + const SCEV *OpV = getSCEVAtScope(Op, L); if (const SCEVConstant *SC = dyn_cast(OpV)) { Constant *C = SC->getValue(); if (C->getType() != Op->getType()) @@ -3982,13 +4048,10 @@ const SCEV *ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) { Constant *C; if (const CmpInst *CI = dyn_cast(I)) C = ConstantFoldCompareInstOperands(CI->getPredicate(), - &Operands[0], Operands.size(), - getContext()); + Operands[0], Operands[1], TD); else C = ConstantFoldInstOperands(I->getOpcode(), I->getType(), - &Operands[0], Operands.size(), - getContext()); - Pair.first->second = C; + &Operands[0], Operands.size(), TD); return getSCEV(C); } } @@ -4039,7 +4102,7 @@ const SCEV *ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) { // If this is a loop recurrence for a loop that does not contain L, then we // are dealing with the final value computed by the loop. if (const SCEVAddRecExpr *AddRec = dyn_cast(V)) { - if (!L || !AddRec->getLoop()->contains(L->getHeader())) { + if (!L || !AddRec->getLoop()->contains(L)) { // To evaluate this recurrence, we need to know how many times the AddRec // loop iterates. Compute this now. const SCEV *BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop()); @@ -4351,7 +4414,7 @@ static bool HasSameValue(const SCEV *A, const SCEV *B) { if (const SCEVUnknown *BU = dyn_cast(B)) if (const Instruction *AI = dyn_cast(AU->getValue())) if (const Instruction *BI = dyn_cast(BU->getValue())) - if (AI->isIdenticalTo(BI)) + if (AI->isIdenticalTo(BI) && !AI->mayReadFromMemory()) return true; // Otherwise assume they may have a different value. @@ -4787,7 +4850,8 @@ ScalarEvolution::isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, /// CouldNotCompute if an intermediate computation overflows. const SCEV *ScalarEvolution::getBECount(const SCEV *Start, const SCEV *End, - const SCEV *Step) { + const SCEV *Step, + bool NoWrap) { const Type *Ty = Start->getType(); const SCEV *NegOne = getIntegerSCEV(-1, Ty); const SCEV *Diff = getMinusSCEV(End, Start); @@ -4797,15 +4861,17 @@ const SCEV *ScalarEvolution::getBECount(const SCEV *Start, // the division will effectively round up. const SCEV *Add = getAddExpr(Diff, RoundUp); - // Check Add for unsigned overflow. - // TODO: More sophisticated things could be done here. - const Type *WideTy = IntegerType::get(getContext(), - getTypeSizeInBits(Ty) + 1); - const SCEV *EDiff = getZeroExtendExpr(Diff, WideTy); - const SCEV *ERoundUp = getZeroExtendExpr(RoundUp, WideTy); - const SCEV *OperandExtendedAdd = getAddExpr(EDiff, ERoundUp); - if (getZeroExtendExpr(Add, WideTy) != OperandExtendedAdd) - return getCouldNotCompute(); + if (!NoWrap) { + // Check Add for unsigned overflow. + // TODO: More sophisticated things could be done here. + const Type *WideTy = IntegerType::get(getContext(), + getTypeSizeInBits(Ty) + 1); + const SCEV *EDiff = getZeroExtendExpr(Diff, WideTy); + const SCEV *ERoundUp = getZeroExtendExpr(RoundUp, WideTy); + const SCEV *OperandExtendedAdd = getAddExpr(EDiff, ERoundUp); + if (getZeroExtendExpr(Add, WideTy) != OperandExtendedAdd) + return getCouldNotCompute(); + } return getUDivExpr(Add, Step); } @@ -4823,6 +4889,10 @@ ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS, if (!AddRec || AddRec->getLoop() != L) return getCouldNotCompute(); + // Check to see if we have a flag which makes analysis easy. + bool NoWrap = isSigned ? AddRec->hasNoSignedWrap() : + AddRec->hasNoUnsignedWrap(); + if (AddRec->isAffine()) { // FORNOW: We only support unit strides. unsigned BitWidth = getTypeSizeInBits(AddRec->getType()); @@ -4835,7 +4905,10 @@ ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS, if (CStep->isOne()) { // With unit stride, the iteration never steps past the limit value. } else if (CStep->getValue()->getValue().isStrictlyPositive()) { - if (const SCEVConstant *CLimit = dyn_cast(RHS)) { + if (NoWrap) { + // We know the iteration won't step past the maximum value for its type. + ; + } else if (const SCEVConstant *CLimit = dyn_cast(RHS)) { // Test whether a positive iteration iteration can step past the limit // value and past the maximum value for its type in a single step. if (isSigned) { @@ -4888,11 +4961,11 @@ ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS, // Finally, we subtract these two values and divide, rounding up, to get // the number of times the backedge is executed. - const SCEV *BECount = getBECount(Start, End, Step); + const SCEV *BECount = getBECount(Start, End, Step, NoWrap); // The maximum backedge count is similar, except using the minimum start // value and the maximum end value. - const SCEV *MaxBECount = getBECount(MinStart, MaxEnd, Step); + const SCEV *MaxBECount = getBECount(MinStart, MaxEnd, Step, NoWrap); return BackedgeTakenInfo(BECount, MaxBECount); } @@ -5033,8 +5106,6 @@ void ScalarEvolution::SCEVCallbackVH::deleted() { assert(SE && "SCEVCallbackVH called with a null ScalarEvolution!"); if (PHINode *PN = dyn_cast(getValPtr())) SE->ConstantEvolutionLoopExitValue.erase(PN); - if (Instruction *I = dyn_cast(getValPtr())) - SE->ValuesAtScopes.erase(I); SE->Scalars.erase(getValPtr()); // this now dangles! } @@ -5064,8 +5135,6 @@ void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(Value *) { continue; if (PHINode *PN = dyn_cast(U)) SE->ConstantEvolutionLoopExitValue.erase(PN); - if (Instruction *I = dyn_cast(U)) - SE->ValuesAtScopes.erase(I); SE->Scalars.erase(U); for (Value::use_iterator UI = U->use_begin(), UE = U->use_end(); UI != UE; ++UI) @@ -5075,8 +5144,6 @@ void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(Value *) { if (DeleteOld) { if (PHINode *PN = dyn_cast(Old)) SE->ConstantEvolutionLoopExitValue.erase(PN); - if (Instruction *I = dyn_cast(Old)) - SE->ValuesAtScopes.erase(I); SE->Scalars.erase(Old); // this now dangles! } @@ -5127,7 +5194,7 @@ static void PrintLoopInfo(raw_ostream &OS, ScalarEvolution *SE, OS << "Loop " << L->getHeader()->getName() << ": "; - SmallVector ExitBlocks; + SmallVector ExitBlocks; L->getExitBlocks(ExitBlocks); if (ExitBlocks.size() != 1) OS << " "; @@ -5150,14 +5217,14 @@ static void PrintLoopInfo(raw_ostream &OS, ScalarEvolution *SE, OS << "\n"; } -void ScalarEvolution::print(raw_ostream &OS, const Module* ) const { +void ScalarEvolution::print(raw_ostream &OS, const Module *) const { // ScalarEvolution's implementaiton of the print method is to print // out SCEV values of all instructions that are interesting. Doing // this potentially causes it to create new SCEV objects though, // which technically conflicts with the const qualifier. This isn't // observable from outside the class though, so casting away the // const isn't dangerous. - ScalarEvolution &SE = *const_cast(this); + ScalarEvolution &SE = *const_cast(this); OS << "Classifying expressions for: " << F->getName() << "\n"; for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) @@ -5193,7 +5260,3 @@ void ScalarEvolution::print(raw_ostream &OS, const Module* ) const { PrintLoopInfo(OS, &SE, *I); } -void ScalarEvolution::print(std::ostream &o, const Module *M) const { - raw_os_ostream OS(o); - print(OS, M); -}