#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"
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 << ")";
}
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 << ")";
}
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 << ")";
}
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
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 << ")";
}
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<std::map<std::pair<SCEV*, SCEV*>,
- 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!
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,
return true;
}
+bool SCEVUnknown::dominates(BasicBlock *BB, DominatorTree *DT) const {
+ if (Instruction *I = dyn_cast<Instruction>(getValue()))
+ return DT->dominates(I->getParent(), BB);
+ return true;
+}
+
const Type *SCEVUnknown::getType() const {
return V->getType();
}
}
// 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);
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<SCEVHandle> &Ops) {
assert(!Ops.empty() && "Cannot get empty add!");
}
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<SCEVConstant>(RHS)) {
if (RHSC->getValue()->equalsInt(1))
- return LHS; // X udiv 1 --> X
+ return LHS; // X udiv 1 --> x
if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
Constant *LHSCV = LHSC->getValue();
}
}
+ // 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<SCEVConstant>(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<SCEVConstant>(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.
///
std::map<Value*, SCEVHandle> Scalars;
- /// IterationCounts - Cache the iteration count of the loops for this
- /// function as they are computed.
- std::map<const Loop*, SCEVHandle> IterationCounts;
+ /// BackedgeTakenCounts - Cache the backedge-taken count of the loops for
+ /// this function as they are computed.
+ std::map<const Loop*, SCEVHandle> BackedgeTakenCounts;
/// ConstantEvolutionLoopExitValue - This map contains entries for all of
/// the PHI instructions that we attempt to compute constant evolutions for.
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
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
/// 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
/// 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);
};
}
return MinOpRes;
}
- // SCEVUDivExpr, SCEVSDivExpr, SCEVUnknown
+ // SCEVUDivExpr, SCEVUnknown
return 0;
}
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)));
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<ConstantInt>(U->getOperand(1))) {
uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
Constant *X = ConstantInt::get(
// 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<const Loop*, SCEVHandle>::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<const Loop*, SCEVHandle>::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!");
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<BasicBlock*, 8> ExitBlocks;
L->getExitBlocks(ExitBlocks);
// Note that ICmpInst deals with pointer comparisons too so we must check
// the type of the operand.
if (ExitCond == 0 || isa<PointerType>(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
if (LoadInst *LI = dyn_cast<LoadInst>(ExitCond->getOperand(0)))
if (Constant *RHS = dyn_cast<Constant>(ExitCond->getOperand(1))) {
SCEVHandle ItCnt =
- ComputeLoadConstantCompareIterationCount(LI, RHS, L, Cond);
+ ComputeLoadConstantCompareBackedgeTakenCount(LI, RHS, L, Cond);
if (!isa<SCEVCouldNotCompute>(ItCnt)) return ItCnt;
}
break;
}
case ICmpInst::ICMP_SLT: {
- SCEVHandle TC = HowManyLessThans(LHS, RHS, L, true, false);
+ SCEVHandle TC = HowManyLessThans(LHS, RHS, L, true);
if (!isa<SCEVCouldNotCompute>(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<SCEVCouldNotCompute>(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<SCEVCouldNotCompute>(TC)) return TC;
break;
}
case ICmpInst::ICMP_UGT: {
SCEVHandle TC = HowManyLessThans(SE.getNotSCEV(LHS),
- SE.getNotSCEV(RHS), L, false, false);
- if (!isa<SCEVCouldNotCompute>(TC)) return TC;
- break;
- }
- case ICmpInst::ICMP_SLE: {
- SCEVHandle TC = HowManyLessThans(LHS, RHS, L, true, true);
- if (!isa<SCEVCouldNotCompute>(TC)) return TC;
- break;
- }
- case ICmpInst::ICMP_SGE: {
- SCEVHandle TC = HowManyLessThans(SE.getNotSCEV(LHS),
- SE.getNotSCEV(RHS), L, true, true);
- if (!isa<SCEVCouldNotCompute>(TC)) return TC;
- break;
- }
- case ICmpInst::ICMP_ULE: {
- SCEVHandle TC = HowManyLessThans(LHS, RHS, L, false, true);
- if (!isa<SCEVCouldNotCompute>(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<SCEVCouldNotCompute>(TC)) return TC;
break;
}
default:
#if 0
- cerr << "ComputeIterationCount ";
+ cerr << "ComputeBackedgeTakenCount ";
if (ExitCond->getOperand(0)->getType()->isUnsigned())
cerr << "[unsigned] ";
cerr << *LHS << " "
#endif
break;
}
- return ComputeIterationCountExhaustively(L, ExitCond,
- ExitBr->getSuccessor(0) == ExitBlock);
+ return
+ ComputeBackedgeTakenCountExhaustively(L, ExitCond,
+ ExitBr->getSuccessor(0) == ExitBlock);
}
static ConstantInt *
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.
/// 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<PHINode*, Constant*>::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];
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)
}
}
-/// 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;
if (PHINode *PN = dyn_cast<PHINode>(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<SCEVConstant>(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<SCEVConstant>(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);
}
return Comm;
}
- if (SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(V)) {
- SCEVHandle LHS = getSCEVAtScope(UDiv->getLHS(), L);
+ if (SCEVUDivExpr *Div = dyn_cast<SCEVUDivExpr>(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<SCEVSDivExpr>(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<SCEVAddRecExpr>(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;
}
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();
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<ConstantInt>(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<SCEVConstant>(LHS))
+ std::swap(PreCondLHS, PreCondRHS);
+ break;
+ }
+ continue;
+ default:
+ // We weren't able to reconcile the condition.
+ continue;
+ }
if (!PreCondLHS->getType()->isInteger()) continue;
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.
-
- SCEVConstant *SC = dyn_cast<SCEVConstant>(Stride);
- if (!SC)
- return true;
-
- if (SC->getValue()->isZero())
- return true;
- if (!trueWhenEqual && SC->getValue()->isOne())
- return false;
-
- SCEVConstant *R = dyn_cast<SCEVConstant>(RHS);
- if (!R)
- return true;
-
- if (isSigned) {
- if (SC->getValue()->isOne())
- return R->getValue()->isMaxValue(true);
-
- 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;
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 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
- // might not divide cleanly. 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)
- End = SE.getAddExpr(End, One);
-
- 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(End, Start)
- : SE.getUMaxExpr(End, 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);
}
-
- // 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;
}
-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<SCEVCouldNotCompute>(getBackedgeTakenCount(L));
}
-bool ScalarEvolution::hasLoopInvariantIterationCount(const Loop *L) const {
- return !isa<SCEVCouldNotCompute>(getIterationCount(L));
+void ScalarEvolution::forgetLoopBackedgeTakenCount(const Loop *L) {
+ return ((ScalarEvolutionsImpl*)Impl)->forgetLoopBackedgeTakenCount(L);
}
SCEVHandle ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) const {
if (ExitBlocks.size() != 1)
OS << "<multiple exits> ";
- 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";
projects / oota-llvm.git / blobdiff