#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 << ")";
}
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();
}
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!");
///
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.
bool isLoopGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,
SCEV *LHS, SCEV *RHS);
- /// hasLoopInvariantIterationCount - Return true if the specified loop has
- /// an analyzable loop-invariant iteration count.
- bool hasLoopInvariantIterationCount(const Loop *L);
-
- /// 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
/// 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);
};
}
// 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;
}
}
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);
}
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;
}
LHS, RHS);
}
-SCEVHandle ScalarEvolution::getIterationCount(const Loop *L) const {
- return ((ScalarEvolutionsImpl*)Impl)->getIterationCount(L);
+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