X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FScalarEvolution.cpp;h=067b83e466dd77dd0665a3c86d92ffa4062f1db1;hb=b169426272b85ce28a9a56d13154e61b158fc47a;hp=187af66cdb5e0a95b2cd663107fcab1afded3e98;hpb=1bdd93a3dcd16de259011c5b4326512a77e5337d;p=oota-llvm.git diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 187af66cdb5..067b83e466d 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -66,6 +66,7 @@ #include "llvm/GlobalVariable.h" #include "llvm/Instructions.h" #include "llvm/Analysis/ConstantFolding.h" +#include "llvm/Analysis/Dominators.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Assembly/Writer.h" #include "llvm/Transforms/Scalar.h" @@ -205,6 +206,10 @@ SCEVTruncateExpr::~SCEVTruncateExpr() { SCEVTruncates->erase(std::make_pair(Op, Ty)); } +bool SCEVTruncateExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { + return Op->dominates(BB, DT); +} + void SCEVTruncateExpr::print(std::ostream &OS) const { OS << "(truncate " << *Op << " to " << *Ty << ")"; } @@ -227,6 +232,10 @@ SCEVZeroExtendExpr::~SCEVZeroExtendExpr() { SCEVZeroExtends->erase(std::make_pair(Op, Ty)); } +bool SCEVZeroExtendExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { + return Op->dominates(BB, DT); +} + void SCEVZeroExtendExpr::print(std::ostream &OS) const { OS << "(zeroextend " << *Op << " to " << *Ty << ")"; } @@ -249,6 +258,10 @@ SCEVSignExtendExpr::~SCEVSignExtendExpr() { SCEVSignExtends->erase(std::make_pair(Op, Ty)); } +bool SCEVSignExtendExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { + return Op->dominates(BB, DT); +} + void SCEVSignExtendExpr::print(std::ostream &OS) const { OS << "(signextend " << *Op << " to " << *Ty << ")"; } @@ -306,6 +319,14 @@ replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, return this; } +bool SCEVCommutativeExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { + for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { + if (!getOperand(i)->dominates(BB, DT)) + return false; + } + return true; +} + // SCEVUDivs - Only allow the creation of one SCEVUDivExpr for any particular // input. Don't use a SCEVHandle here, or else the object will never be @@ -317,6 +338,10 @@ SCEVUDivExpr::~SCEVUDivExpr() { SCEVUDivs->erase(std::make_pair(LHS, RHS)); } +bool SCEVUDivExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { + return LHS->dominates(BB, DT) && RHS->dominates(BB, DT); +} + void SCEVUDivExpr::print(std::ostream &OS) const { OS << "(" << *LHS << " /u " << *RHS << ")"; } @@ -325,26 +350,6 @@ const Type *SCEVUDivExpr::getType() const { return LHS->getType(); } - -// SCEVSDivs - Only allow the creation of one SCEVSDivExpr for any particular -// input. Don't use a SCEVHandle here, or else the object will never be -// deleted! -static ManagedStatic, - SCEVSDivExpr*> > SCEVSDivs; - -SCEVSDivExpr::~SCEVSDivExpr() { - SCEVSDivs->erase(std::make_pair(LHS, RHS)); -} - -void SCEVSDivExpr::print(std::ostream &OS) const { - OS << "(" << *LHS << " /s " << *RHS << ")"; -} - -const Type *SCEVSDivExpr::getType() const { - return LHS->getType(); -} - - // SCEVAddRecExprs - Only allow the creation of one SCEVAddRecExpr for any // particular input. Don't use a SCEVHandle here, or else the object will never // be deleted! @@ -357,6 +362,15 @@ SCEVAddRecExpr::~SCEVAddRecExpr() { Operands.end()))); } +bool SCEVAddRecExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { + for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { + if (!getOperand(i)->dominates(BB, DT)) + return false; + } + return true; +} + + SCEVHandle SCEVAddRecExpr:: replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, const SCEVHandle &Conc, @@ -411,6 +425,12 @@ bool SCEVUnknown::isLoopInvariant(const Loop *L) const { return true; } +bool SCEVUnknown::dominates(BasicBlock *BB, DominatorTree *DT) const { + if (Instruction *I = dyn_cast(getValue())) + return DT->dominates(I->getParent(), BB); + return true; +} + const Type *SCEVUnknown::getType() const { return V->getType(); } @@ -605,17 +625,7 @@ static SCEVHandle BinomialCoefficient(SCEVHandle It, unsigned K, } // We need at least W + T bits for the multiplication step - // FIXME: A temporary hack; we round up the bitwidths - // to the nearest power of 2 to be nice to the code generator. - unsigned CalculationBits = 1U << Log2_32_Ceil(W + T); - // FIXME: Temporary hack to avoid generating integers that are too wide. - // Although, it's not completely clear how to determine how much - // widening is safe; for example, on X86, we can't really widen - // beyond 64 because we need to be able to do multiplication - // that's CalculationBits wide, but on X86-64, we can safely widen up to - // 128 bits. - if (CalculationBits > 64) - return new SCEVCouldNotCompute(); + unsigned CalculationBits = W + T; // Calcuate 2^T, at width T+W. APInt DivFactor = APInt(CalculationBits, 1).shl(T); @@ -745,6 +755,21 @@ SCEVHandle ScalarEvolution::getTruncateOrZeroExtend(const SCEVHandle &V, return getZeroExtendExpr(V, 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. +SCEVHandle ScalarEvolution::getTruncateOrSignExtend(const SCEVHandle &V, + const Type *Ty) { + const Type *SrcTy = V->getType(); + assert(SrcTy->isInteger() && Ty->isInteger() && + "Cannot truncate or sign extend with non-integer arguments!"); + if (SrcTy->getPrimitiveSizeInBits() == Ty->getPrimitiveSizeInBits()) + return V; // No conversion + if (SrcTy->getPrimitiveSizeInBits() > Ty->getPrimitiveSizeInBits()) + return getTruncateExpr(V, Ty); + return getSignExtendExpr(V, Ty); +} + // get - Get a canonical add expression, or something simpler if possible. SCEVHandle ScalarEvolution::getAddExpr(std::vector &Ops) { assert(!Ops.empty() && "Cannot get empty add!"); @@ -1130,12 +1155,9 @@ SCEVHandle ScalarEvolution::getMulExpr(std::vector &Ops) { } SCEVHandle ScalarEvolution::getUDivExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) { - if (LHS == RHS) - return getIntegerSCEV(1, LHS->getType()); // X udiv X --> 1 - if (SCEVConstant *RHSC = dyn_cast(RHS)) { if (RHSC->getValue()->equalsInt(1)) - return LHS; // X udiv 1 --> X + return LHS; // X udiv 1 --> x if (SCEVConstant *LHSC = dyn_cast(LHS)) { Constant *LHSCV = LHSC->getValue(); @@ -1144,34 +1166,13 @@ SCEVHandle ScalarEvolution::getUDivExpr(const SCEVHandle &LHS, const SCEVHandle } } + // FIXME: implement folding of (X*4)/4 when we know X*4 doesn't overflow. + SCEVUDivExpr *&Result = (*SCEVUDivs)[std::make_pair(LHS, RHS)]; if (Result == 0) Result = new SCEVUDivExpr(LHS, RHS); return Result; } -SCEVHandle ScalarEvolution::getSDivExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) { - if (LHS == RHS) - return getIntegerSCEV(1, LHS->getType()); // X sdiv X --> 1 - - if (SCEVConstant *RHSC = dyn_cast(RHS)) { - if (RHSC->getValue()->equalsInt(1)) - return LHS; // X sdiv 1 --> X - - if (RHSC->getValue()->isAllOnesValue()) - return getNegativeSCEV(LHS); // X sdiv -1 --> -X - - if (SCEVConstant *LHSC = dyn_cast(LHS)) { - Constant *LHSCV = LHSC->getValue(); - Constant *RHSCV = RHSC->getValue(); - return getUnknown(ConstantExpr::getSDiv(LHSCV, RHSCV)); - } - } - - SCEVSDivExpr *&Result = (*SCEVSDivs)[std::make_pair(LHS, RHS)]; - if (Result == 0) Result = new SCEVSDivExpr(LHS, RHS); - return Result; -} - /// SCEVAddRecExpr::get - Get a add recurrence expression for the /// specified loop. Simplify the expression as much as possible. @@ -1418,9 +1419,9 @@ namespace { /// std::map Scalars; - /// IterationCounts - Cache the iteration count of the loops for this - /// function as they are computed. - std::map IterationCounts; + /// BackedgeTakenCounts - Cache the backedge-taken count of the loops for + /// this function as they are computed. + std::map BackedgeTakenCounts; /// ConstantEvolutionLoopExitValue - This map contains entries for all of /// the PHI instructions that we attempt to compute constant evolutions for. @@ -1458,14 +1459,33 @@ namespace { SCEVHandle getSCEVAtScope(SCEV *V, const Loop *L); - /// hasLoopInvariantIterationCount - Return true if the specified loop has - /// an analyzable loop-invariant iteration count. - bool hasLoopInvariantIterationCount(const Loop *L); + /// isLoopGuardedByCond - Test whether entry to the loop is protected by + /// a conditional between LHS and RHS. + bool isLoopGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, + SCEV *LHS, SCEV *RHS); - /// getIterationCount - If the specified loop has a predictable iteration - /// count, return it. Note that it is not valid to call this method on a - /// loop without a loop-invariant iteration count. - SCEVHandle getIterationCount(const Loop *L); + /// hasLoopInvariantBackedgeTakenCount - Return true if the specified loop + /// has an analyzable loop-invariant backedge-taken count. + bool hasLoopInvariantBackedgeTakenCount(const Loop *L); + + /// 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 forgetLoopBackedgeTakenCount(const Loop *L); + + /// getBackedgeTakenCount - If the specified loop has a predictable + /// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute + /// object. The backedge-taken count is the number of times the loop header + /// will be branched to from within the loop. This is one less than the + /// trip count of the loop, since it doesn't count the first iteration, + /// when the header is branched to from outside the loop. + /// + /// Note that it is not valid to call this method on a loop without a + /// loop-invariant backedge-taken count (see + /// hasLoopInvariantBackedgeTakenCount). + /// + SCEVHandle getBackedgeTakenCount(const Loop *L); /// deleteValueFromRecords - This method should be called by the /// client before it removes a value from the program, to make sure @@ -1489,24 +1509,25 @@ namespace { const SCEVHandle &SymName, const SCEVHandle &NewVal); - /// ComputeIterationCount - Compute the number of times the specified loop - /// will iterate. - SCEVHandle ComputeIterationCount(const Loop *L); + /// ComputeBackedgeTakenCount - Compute the number of times the specified + /// loop will iterate. + SCEVHandle ComputeBackedgeTakenCount(const Loop *L); - /// ComputeLoadConstantCompareIterationCount - Given an exit condition of - /// 'icmp op load X, cst', try to see if we can compute the trip count. - SCEVHandle ComputeLoadConstantCompareIterationCount(LoadInst *LI, - Constant *RHS, - const Loop *L, - ICmpInst::Predicate p); + /// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition + /// of 'icmp op load X, cst', try to see if we can compute the trip count. + SCEVHandle + ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI, + Constant *RHS, + const Loop *L, + ICmpInst::Predicate p); - /// ComputeIterationCountExhaustively - If the trip is known to execute a - /// constant number of times (the condition evolves only from constants), + /// ComputeBackedgeTakenCountExhaustively - If the trip is known to execute + /// a constant number of times (the condition evolves only from constants), /// 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 UnknownValue. - SCEVHandle ComputeIterationCountExhaustively(const Loop *L, Value *Cond, - bool ExitWhen); + SCEVHandle 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 @@ -1522,7 +1543,7 @@ namespace { /// specified less-than comparison will execute. If not computable, return /// UnknownValue. isSigned specifies whether the less-than is signed. SCEVHandle HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L, - bool isSigned, bool trueWhenEqual); + bool isSigned); /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB /// (which may not be an immediate predecessor) which has exactly one @@ -1530,21 +1551,11 @@ namespace { /// found. BasicBlock* getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB); - /// executesAtLeastOnce - Test whether entry to the loop is protected by - /// a conditional between LHS and RHS. - bool executesAtLeastOnce(const Loop *L, bool isSigned, bool trueWhenEqual, - SCEV *LHS, SCEV *RHS); - - /// potentialInfiniteLoop - Test whether the loop might jump over the exit value - /// due to wrapping. - bool potentialInfiniteLoop(SCEV *Stride, SCEV *RHS, bool isSigned, - bool trueWhenEqual); - /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is /// in the header of its containing loop, we know the loop executes a /// constant number of times, and the PHI node is just a recurrence /// involving constants, fold it. - Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& Its, + Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs, const Loop *L); }; } @@ -1777,7 +1788,7 @@ static uint32_t GetMinTrailingZeros(SCEVHandle S) { return MinOpRes; } - // SCEVUDivExpr, SCEVSDivExpr, SCEVUnknown + // SCEVUDivExpr, SCEVUnknown return 0; } @@ -1807,9 +1818,6 @@ SCEVHandle ScalarEvolutionsImpl::createSCEV(Value *V) { case Instruction::UDiv: return SE.getUDivExpr(getSCEV(U->getOperand(0)), getSCEV(U->getOperand(1))); - case Instruction::SDiv: - return SE.getSDivExpr(getSCEV(U->getOperand(0)), - getSCEV(U->getOperand(1))); case Instruction::Sub: return SE.getMinusSCEV(getSCEV(U->getOperand(0)), getSCEV(U->getOperand(1))); @@ -1853,7 +1861,7 @@ SCEVHandle ScalarEvolutionsImpl::createSCEV(Value *V) { break; case Instruction::LShr: - // Turn logical shift right of a constant into an unsigned divide. + // Turn logical shift right of a constant into a unsigned divide. if (ConstantInt *SA = dyn_cast(U->getOperand(1))) { uint32_t BitWidth = cast(V->getType())->getBitWidth(); Constant *X = ConstantInt::get( @@ -1933,14 +1941,22 @@ SCEVHandle ScalarEvolutionsImpl::createSCEV(Value *V) { // Iteration Count Computation Code // -/// getIterationCount - If the specified loop has a predictable iteration -/// count, return it. Note that it is not valid to call this method on a -/// loop without a loop-invariant iteration count. -SCEVHandle ScalarEvolutionsImpl::getIterationCount(const Loop *L) { - std::map::iterator I = IterationCounts.find(L); - if (I == IterationCounts.end()) { - SCEVHandle ItCount = ComputeIterationCount(L); - I = IterationCounts.insert(std::make_pair(L, ItCount)).first; +/// getBackedgeTakenCount - If the specified loop has a predictable +/// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute +/// object. The backedge-taken count is the number of times the loop header +/// will be branched to from within the loop. This is one less than the +/// trip count of the loop, since it doesn't count the first iteration, +/// when the header is branched to from outside the loop. +/// +/// Note that it is not valid to call this method on a loop without a +/// loop-invariant backedge-taken count (see +/// hasLoopInvariantBackedgeTakenCount). +/// +SCEVHandle ScalarEvolutionsImpl::getBackedgeTakenCount(const Loop *L) { + std::map::iterator I = BackedgeTakenCounts.find(L); + if (I == BackedgeTakenCounts.end()) { + SCEVHandle ItCount = ComputeBackedgeTakenCount(L); + I = BackedgeTakenCounts.insert(std::make_pair(L, ItCount)).first; if (ItCount != UnknownValue) { assert(ItCount->isLoopInvariant(L) && "Computed trip count isn't loop invariant for loop!"); @@ -1953,9 +1969,17 @@ SCEVHandle ScalarEvolutionsImpl::getIterationCount(const Loop *L) { return I->second; } -/// ComputeIterationCount - Compute the number of times the specified loop -/// will iterate. -SCEVHandle ScalarEvolutionsImpl::ComputeIterationCount(const Loop *L) { +/// 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 ScalarEvolutionsImpl::forgetLoopBackedgeTakenCount(const Loop *L) { + BackedgeTakenCounts.erase(L); +} + +/// ComputeBackedgeTakenCount - Compute the number of times the backedge +/// of the specified loop will execute. +SCEVHandle ScalarEvolutionsImpl::ComputeBackedgeTakenCount(const Loop *L) { // If the loop has a non-one exit block count, we can't analyze it. SmallVector ExitBlocks; L->getExitBlocks(ExitBlocks); @@ -2005,7 +2029,7 @@ SCEVHandle ScalarEvolutionsImpl::ComputeIterationCount(const Loop *L) { // Note that ICmpInst deals with pointer comparisons too so we must check // the type of the operand. if (ExitCond == 0 || isa(ExitCond->getOperand(0)->getType())) - return ComputeIterationCountExhaustively(L, ExitBr->getCondition(), + return ComputeBackedgeTakenCountExhaustively(L, ExitBr->getCondition(), ExitBr->getSuccessor(0) == ExitBlock); // If the condition was exit on true, convert the condition to exit on false @@ -2019,7 +2043,7 @@ SCEVHandle ScalarEvolutionsImpl::ComputeIterationCount(const Loop *L) { if (LoadInst *LI = dyn_cast(ExitCond->getOperand(0))) if (Constant *RHS = dyn_cast(ExitCond->getOperand(1))) { SCEVHandle ItCnt = - ComputeLoadConstantCompareIterationCount(LI, RHS, L, Cond); + ComputeLoadConstantCompareBackedgeTakenCount(LI, RHS, L, Cond); if (!isa(ItCnt)) return ItCnt; } @@ -2079,52 +2103,30 @@ SCEVHandle ScalarEvolutionsImpl::ComputeIterationCount(const Loop *L) { break; } case ICmpInst::ICMP_SLT: { - SCEVHandle TC = HowManyLessThans(LHS, RHS, L, true, false); + SCEVHandle TC = HowManyLessThans(LHS, RHS, L, true); if (!isa(TC)) return TC; break; } case ICmpInst::ICMP_SGT: { SCEVHandle TC = HowManyLessThans(SE.getNotSCEV(LHS), - SE.getNotSCEV(RHS), L, true, false); + SE.getNotSCEV(RHS), L, true); if (!isa(TC)) return TC; break; } case ICmpInst::ICMP_ULT: { - SCEVHandle TC = HowManyLessThans(LHS, RHS, L, false, false); + SCEVHandle TC = HowManyLessThans(LHS, RHS, L, false); if (!isa(TC)) return TC; break; } case ICmpInst::ICMP_UGT: { SCEVHandle TC = HowManyLessThans(SE.getNotSCEV(LHS), - SE.getNotSCEV(RHS), L, false, false); - if (!isa(TC)) return TC; - break; - } - case ICmpInst::ICMP_SLE: { - SCEVHandle TC = HowManyLessThans(LHS, RHS, L, true, true); - if (!isa(TC)) return TC; - break; - } - case ICmpInst::ICMP_SGE: { - SCEVHandle TC = HowManyLessThans(SE.getNotSCEV(LHS), - SE.getNotSCEV(RHS), L, true, true); - if (!isa(TC)) return TC; - break; - } - case ICmpInst::ICMP_ULE: { - SCEVHandle TC = HowManyLessThans(LHS, RHS, L, false, true); - if (!isa(TC)) return TC; - break; - } - case ICmpInst::ICMP_UGE: { - SCEVHandle TC = HowManyLessThans(SE.getNotSCEV(LHS), - SE.getNotSCEV(RHS), L, false, true); + SE.getNotSCEV(RHS), L, false); if (!isa(TC)) return TC; break; } default: #if 0 - cerr << "ComputeIterationCount "; + cerr << "ComputeBackedgeTakenCount "; if (ExitCond->getOperand(0)->getType()->isUnsigned()) cerr << "[unsigned] "; cerr << *LHS << " " @@ -2133,8 +2135,9 @@ SCEVHandle ScalarEvolutionsImpl::ComputeIterationCount(const Loop *L) { #endif break; } - return ComputeIterationCountExhaustively(L, ExitCond, - ExitBr->getSuccessor(0) == ExitBlock); + return + ComputeBackedgeTakenCountExhaustively(L, ExitCond, + ExitBr->getSuccessor(0) == ExitBlock); } static ConstantInt * @@ -2181,12 +2184,13 @@ GetAddressedElementFromGlobal(GlobalVariable *GV, return Init; } -/// ComputeLoadConstantCompareIterationCount - Given an exit condition of -/// 'icmp op load X, cst', try to see if we can compute the trip count. +/// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition of +/// 'icmp op load X, cst', try to see if we can compute the backedge +/// execution count. SCEVHandle ScalarEvolutionsImpl:: -ComputeLoadConstantCompareIterationCount(LoadInst *LI, Constant *RHS, - const Loop *L, - ICmpInst::Predicate predicate) { +ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI, Constant *RHS, + const Loop *L, + ICmpInst::Predicate predicate) { if (LI->isVolatile()) return UnknownValue; // Check to see if the loaded pointer is a getelementptr of a global. @@ -2343,13 +2347,13 @@ static Constant *EvaluateExpression(Value *V, Constant *PHIVal) { /// constant number of times, and the PHI node is just a recurrence /// involving constants, fold it. Constant *ScalarEvolutionsImpl:: -getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& Its, const Loop *L){ +getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs, const Loop *L){ std::map::iterator I = ConstantEvolutionLoopExitValue.find(PN); if (I != ConstantEvolutionLoopExitValue.end()) return I->second; - if (Its.ugt(APInt(Its.getBitWidth(),MaxBruteForceIterations))) + if (BEs.ugt(APInt(BEs.getBitWidth(),MaxBruteForceIterations))) return ConstantEvolutionLoopExitValue[PN] = 0; // Not going to evaluate it. Constant *&RetVal = ConstantEvolutionLoopExitValue[PN]; @@ -2369,10 +2373,10 @@ getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& Its, const Loop *L){ return RetVal = 0; // Not derived from same PHI. // Execute the loop symbolically to determine the exit value. - if (Its.getActiveBits() >= 32) + if (BEs.getActiveBits() >= 32) return RetVal = 0; // More than 2^32-1 iterations?? Not doing it! - unsigned NumIterations = Its.getZExtValue(); // must be in range + unsigned NumIterations = BEs.getZExtValue(); // must be in range unsigned IterationNum = 0; for (Constant *PHIVal = StartCST; ; ++IterationNum) { if (IterationNum == NumIterations) @@ -2388,13 +2392,13 @@ getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& Its, const Loop *L){ } } -/// ComputeIterationCountExhaustively - If the trip is known to execute a +/// ComputeBackedgeTakenCountExhaustively - If the trip is known to execute a /// constant number of times (the condition evolves only from constants), /// 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 UnknownValue. SCEVHandle ScalarEvolutionsImpl:: -ComputeIterationCountExhaustively(const Loop *L, Value *Cond, bool ExitWhen) { +ComputeBackedgeTakenCountExhaustively(const Loop *L, Value *Cond, bool ExitWhen) { PHINode *PN = getConstantEvolvingPHI(Cond, L); if (PN == 0) return UnknownValue; @@ -2457,15 +2461,17 @@ SCEVHandle ScalarEvolutionsImpl::getSCEVAtScope(SCEV *V, const Loop *L) { if (PHINode *PN = dyn_cast(I)) if (PN->getParent() == LI->getHeader()) { // Okay, there is no closed form solution for the PHI node. Check - // to see if the loop that contains it has a known iteration count. - // If so, we may be able to force computation of the exit value. - SCEVHandle IterationCount = getIterationCount(LI); - if (SCEVConstant *ICC = dyn_cast(IterationCount)) { + // to see if the loop that contains it has a known backedge-taken + // count. If so, we may be able to force computation of the exit + // value. + SCEVHandle BackedgeTakenCount = getBackedgeTakenCount(LI); + if (SCEVConstant *BTCC = + dyn_cast(BackedgeTakenCount)) { // Okay, we know how many times the containing loop executes. If // this is a constant evolving PHI node, get the final value at // the specified iteration number. Constant *RV = getConstantEvolutionLoopExitValue(PN, - ICC->getValue()->getValue(), + BTCC->getValue()->getValue(), LI); if (RV) return SE.getUnknown(RV); } @@ -2553,37 +2559,27 @@ SCEVHandle ScalarEvolutionsImpl::getSCEVAtScope(SCEV *V, const Loop *L) { return Comm; } - if (SCEVUDivExpr *UDiv = dyn_cast(V)) { - SCEVHandle LHS = getSCEVAtScope(UDiv->getLHS(), L); + if (SCEVUDivExpr *Div = dyn_cast(V)) { + SCEVHandle LHS = getSCEVAtScope(Div->getLHS(), L); if (LHS == UnknownValue) return LHS; - SCEVHandle RHS = getSCEVAtScope(UDiv->getRHS(), L); + SCEVHandle RHS = getSCEVAtScope(Div->getRHS(), L); if (RHS == UnknownValue) return RHS; - if (LHS == UDiv->getLHS() && RHS == UDiv->getRHS()) - return UDiv; // must be loop invariant + if (LHS == Div->getLHS() && RHS == Div->getRHS()) + return Div; // must be loop invariant return SE.getUDivExpr(LHS, RHS); } - if (SCEVSDivExpr *SDiv = dyn_cast(V)) { - SCEVHandle LHS = getSCEVAtScope(SDiv->getLHS(), L); - if (LHS == UnknownValue) return LHS; - SCEVHandle RHS = getSCEVAtScope(SDiv->getRHS(), L); - if (RHS == UnknownValue) return RHS; - if (LHS == SDiv->getLHS() && RHS == SDiv->getRHS()) - return SDiv; // must be loop invariant - return SE.getSDivExpr(LHS, RHS); - } - // 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 (SCEVAddRecExpr *AddRec = dyn_cast(V)) { if (!L || !AddRec->getLoop()->contains(L->getHeader())) { // To evaluate this recurrence, we need to know how many times the AddRec // loop iterates. Compute this now. - SCEVHandle IterationCount = getIterationCount(AddRec->getLoop()); - if (IterationCount == UnknownValue) return UnknownValue; + SCEVHandle BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop()); + if (BackedgeTakenCount == UnknownValue) return UnknownValue; // Then, evaluate the AddRec. - return AddRec->evaluateAtIteration(IterationCount, SE); + return AddRec->evaluateAtIteration(BackedgeTakenCount, SE); } return UnknownValue; } @@ -2821,10 +2817,10 @@ ScalarEvolutionsImpl::getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB) { return 0; } -/// executesAtLeastOnce - Test whether entry to the loop is protected by +/// isLoopGuardedByCond - Test whether entry to the loop is protected by /// a conditional between LHS and RHS. -bool ScalarEvolutionsImpl::executesAtLeastOnce(const Loop *L, bool isSigned, - bool trueWhenEqual, +bool ScalarEvolutionsImpl::isLoopGuardedByCond(const Loop *L, + ICmpInst::Predicate Pred, SCEV *LHS, SCEV *RHS) { BasicBlock *Preheader = L->getLoopPreheader(); BasicBlock *PreheaderDest = L->getHeader(); @@ -2855,42 +2851,62 @@ bool ScalarEvolutionsImpl::executesAtLeastOnce(const Loop *L, bool isSigned, else Cond = ICI->getInversePredicate(); - switch (Cond) { - case ICmpInst::ICMP_UGT: - if (isSigned || trueWhenEqual) continue; - std::swap(PreCondLHS, PreCondRHS); - Cond = ICmpInst::ICMP_ULT; - break; - case ICmpInst::ICMP_SGT: - if (!isSigned || trueWhenEqual) continue; - std::swap(PreCondLHS, PreCondRHS); - Cond = ICmpInst::ICMP_SLT; - break; - case ICmpInst::ICMP_ULT: - if (isSigned || trueWhenEqual) continue; - break; - case ICmpInst::ICMP_SLT: - if (!isSigned || trueWhenEqual) continue; - break; - case ICmpInst::ICMP_UGE: - if (isSigned || !trueWhenEqual) continue; - std::swap(PreCondLHS, PreCondRHS); - Cond = ICmpInst::ICMP_ULE; - break; - case ICmpInst::ICMP_SGE: - if (!isSigned || !trueWhenEqual) continue; - std::swap(PreCondLHS, PreCondRHS); - Cond = ICmpInst::ICMP_SLE; - break; - case ICmpInst::ICMP_ULE: - if (isSigned || !trueWhenEqual) continue; - break; - case ICmpInst::ICMP_SLE: - if (!isSigned || !trueWhenEqual) continue; - break; - default: - continue; - } + if (Cond == Pred) + ; // An exact match. + else if (!ICmpInst::isTrueWhenEqual(Cond) && Pred == ICmpInst::ICMP_NE) + ; // The actual condition is beyond sufficient. + else + // Check a few special cases. + switch (Cond) { + case ICmpInst::ICMP_UGT: + if (Pred == ICmpInst::ICMP_ULT) { + std::swap(PreCondLHS, PreCondRHS); + Cond = ICmpInst::ICMP_ULT; + break; + } + continue; + case ICmpInst::ICMP_SGT: + if (Pred == ICmpInst::ICMP_SLT) { + std::swap(PreCondLHS, PreCondRHS); + Cond = ICmpInst::ICMP_SLT; + break; + } + continue; + case ICmpInst::ICMP_NE: + // Expressions like (x >u 0) are often canonicalized to (x != 0), + // so check for this case by checking if the NE is comparing against + // a minimum or maximum constant. + if (!ICmpInst::isTrueWhenEqual(Pred)) + if (ConstantInt *CI = dyn_cast(PreCondRHS)) { + const APInt &A = CI->getValue(); + switch (Pred) { + case ICmpInst::ICMP_SLT: + if (A.isMaxSignedValue()) break; + continue; + case ICmpInst::ICMP_SGT: + if (A.isMinSignedValue()) break; + continue; + case ICmpInst::ICMP_ULT: + if (A.isMaxValue()) break; + continue; + case ICmpInst::ICMP_UGT: + if (A.isMinValue()) break; + continue; + default: + continue; + } + Cond = ICmpInst::ICMP_NE; + // NE is symmetric but the original comparison may not be. Swap + // the operands if necessary so that they match below. + if (isa(LHS)) + std::swap(PreCondLHS, PreCondRHS); + break; + } + continue; + default: + // We weren't able to reconcile the condition. + continue; + } if (!PreCondLHS->getType()->isInteger()) continue; @@ -2905,46 +2921,11 @@ bool ScalarEvolutionsImpl::executesAtLeastOnce(const Loop *L, bool isSigned, return false; } -/// potentialInfiniteLoop - Test whether the loop might jump over the exit value -/// due to wrapping around 2^n. -bool ScalarEvolutionsImpl::potentialInfiniteLoop(SCEV *Stride, SCEV *RHS, - bool isSigned, bool trueWhenEqual) { - // Return true when the distance from RHS to maxint > Stride. - - if (!isa(Stride)) - return true; - SCEVConstant *SC = cast(Stride); - - if (SC->getValue()->isZero()) - return true; - if (!trueWhenEqual && SC->getValue()->isOne()) - return false; - - if (!isa(RHS)) - return true; - SCEVConstant *R = cast(RHS); - - if (isSigned) - return true; // XXX: because we don't have an sdiv scev. - - // If negative, it wraps around every iteration, but we don't care about that. - APInt S = SC->getValue()->getValue().abs(); - - APInt Dist = APInt::getMaxValue(R->getValue()->getBitWidth()) - - R->getValue()->getValue(); - - if (trueWhenEqual) - return !S.ult(Dist); - else - return !S.ule(Dist); -} - /// HowManyLessThans - Return the number of times a backedge containing the /// specified less-than comparison will execute. If not computable, return /// UnknownValue. SCEVHandle ScalarEvolutionsImpl:: -HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L, - bool isSigned, bool trueWhenEqual) { +HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L, bool isSigned) { // Only handle: "ADDREC < LoopInvariant". if (!RHS->isLoopInvariant(L)) return UnknownValue; @@ -2953,50 +2934,35 @@ HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L, return UnknownValue; if (AddRec->isAffine()) { - SCEVHandle Stride = AddRec->getOperand(1); - if (potentialInfiniteLoop(Stride, RHS, isSigned, trueWhenEqual)) + // FORNOW: We only support unit strides. + SCEVHandle One = SE.getIntegerSCEV(1, RHS->getType()); + if (AddRec->getOperand(1) != One) return UnknownValue; - // We know the LHS is of the form {n,+,s} and the RHS is some loop-invariant - // m. So, we count the number of iterations in which {n,+,s} < m is true. - // Note that we cannot simply return max(m-n,0)/s because it's not safe to + // We know the LHS is of the form {n,+,1} and the RHS is some loop-invariant + // m. So, we count the number of iterations in which {n,+,1} < m is true. + // Note that we cannot simply return max(m-n,0) because it's not safe to // treat m-n as signed nor unsigned due to overflow possibility. // First, we get the value of the LHS in the first iteration: n SCEVHandle Start = AddRec->getOperand(0); - SCEVHandle One = SE.getIntegerSCEV(1, RHS->getType()); - - // Assuming that the loop will run at least once, we know that it will - // run (m-n)/s times. - SCEVHandle End = RHS; - - if (!executesAtLeastOnce(L, isSigned, trueWhenEqual, - SE.getMinusSCEV(Start, One), RHS)) { - // If not, we get the value of the LHS in the first iteration in which - // the above condition doesn't hold. This equals to max(m,n). - End = isSigned ? SE.getSMaxExpr(RHS, Start) - : SE.getUMaxExpr(RHS, Start); + if (isLoopGuardedByCond(L, + isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, + SE.getMinusSCEV(AddRec->getOperand(0), One), RHS)) { + // Since we know that the condition is true in order to enter the loop, + // we know that it will run exactly m-n times. + return SE.getMinusSCEV(RHS, Start); + } else { + // Then, we get the value of the LHS in the first iteration in which the + // above condition doesn't hold. This equals to max(m,n). + SCEVHandle End = isSigned ? SE.getSMaxExpr(RHS, Start) + : SE.getUMaxExpr(RHS, Start); + + // Finally, we subtract these two values to get the number of times the + // backedge is executed: max(m,n)-n. + return SE.getMinusSCEV(End, Start); } - - // If the expression is less-than-or-equal to, we need to extend the - // loop by one iteration. - // - // The loop won't actually run (m-n)/s times because the loop iterations - // won't divide evenly. For example, if you have {2,+,5} u< 10 the - // division would equal one, but the loop runs twice putting the - // induction variable at 12. - - if (!trueWhenEqual) - // (Stride - 1) is correct only because we know it's unsigned. - // What we really want is to decrease the magnitude of Stride by one. - Start = SE.getMinusSCEV(Start, SE.getMinusSCEV(Stride, One)); - else - Start = SE.getMinusSCEV(Start, Stride); - - // Finally, we subtract these two values to get the number of times the - // backedge is executed: max(m,n)-n. - return SE.getUDivExpr(SE.getMinusSCEV(End, Start), Stride); } return UnknownValue; @@ -3160,12 +3126,23 @@ void ScalarEvolution::setSCEV(Value *V, const SCEVHandle &H) { } -SCEVHandle ScalarEvolution::getIterationCount(const Loop *L) const { - return ((ScalarEvolutionsImpl*)Impl)->getIterationCount(L); +bool ScalarEvolution::isLoopGuardedByCond(const Loop *L, + ICmpInst::Predicate Pred, + SCEV *LHS, SCEV *RHS) { + return ((ScalarEvolutionsImpl*)Impl)->isLoopGuardedByCond(L, Pred, + LHS, RHS); +} + +SCEVHandle ScalarEvolution::getBackedgeTakenCount(const Loop *L) const { + return ((ScalarEvolutionsImpl*)Impl)->getBackedgeTakenCount(L); +} + +bool ScalarEvolution::hasLoopInvariantBackedgeTakenCount(const Loop *L) const { + return !isa(getBackedgeTakenCount(L)); } -bool ScalarEvolution::hasLoopInvariantIterationCount(const Loop *L) const { - return !isa(getIterationCount(L)); +void ScalarEvolution::forgetLoopBackedgeTakenCount(const Loop *L) { + return ((ScalarEvolutionsImpl*)Impl)->forgetLoopBackedgeTakenCount(L); } SCEVHandle ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) const { @@ -3189,10 +3166,10 @@ static void PrintLoopInfo(std::ostream &OS, const ScalarEvolution *SE, if (ExitBlocks.size() != 1) OS << " "; - if (SE->hasLoopInvariantIterationCount(L)) { - OS << *SE->getIterationCount(L) << " iterations! "; + if (SE->hasLoopInvariantBackedgeTakenCount(L)) { + OS << "backedge-taken count is " << *SE->getBackedgeTakenCount(L); } else { - OS << "Unpredictable iteration count. "; + OS << "Unpredictable backedge-taken count. "; } OS << "\n";