aboutsummaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/Analysis/IVUsers.cpp28
-rw-r--r--lib/Analysis/LoopVR.cpp14
-rw-r--r--lib/Analysis/ScalarEvolution.cpp511
-rw-r--r--lib/Analysis/ScalarEvolutionExpander.cpp68
-rw-r--r--lib/Transforms/Scalar/IndVarSimplify.cpp26
-rw-r--r--lib/Transforms/Scalar/LoopDeletion.cpp2
-rw-r--r--lib/Transforms/Scalar/LoopStrengthReduce.cpp206
7 files changed, 427 insertions, 428 deletions
diff --git a/lib/Analysis/IVUsers.cpp b/lib/Analysis/IVUsers.cpp
index 6a53a83665..caeb14bef3 100644
--- a/lib/Analysis/IVUsers.cpp
+++ b/lib/Analysis/IVUsers.cpp
@@ -39,7 +39,7 @@ Pass *llvm::createIVUsersPass() {
/// containsAddRecFromDifferentLoop - Determine whether expression S involves a
/// subexpression that is an AddRec from a loop other than L. An outer loop
/// of L is OK, but not an inner loop nor a disjoint loop.
-static bool containsAddRecFromDifferentLoop(SCEVHandle S, Loop *L) {
+static bool containsAddRecFromDifferentLoop(const SCEV* S, Loop *L) {
// This is very common, put it first.
if (isa<SCEVConstant>(S))
return false;
@@ -80,10 +80,10 @@ static bool containsAddRecFromDifferentLoop(SCEVHandle S, Loop *L) {
/// a mix of loop invariant and loop variant expressions. The start cannot,
/// however, contain an AddRec from a different loop, unless that loop is an
/// outer loop of the current loop.
-static bool getSCEVStartAndStride(const SCEVHandle &SH, Loop *L, Loop *UseLoop,
- SCEVHandle &Start, SCEVHandle &Stride,
+static bool getSCEVStartAndStride(const SCEV* &SH, Loop *L, Loop *UseLoop,
+ const SCEV* &Start, const SCEV* &Stride,
ScalarEvolution *SE, DominatorTree *DT) {
- SCEVHandle TheAddRec = Start; // Initialize to zero.
+ const SCEV* TheAddRec = Start; // Initialize to zero.
// If the outer level is an AddExpr, the operands are all start values except
// for a nested AddRecExpr.
@@ -109,9 +109,9 @@ static bool getSCEVStartAndStride(const SCEVHandle &SH, Loop *L, Loop *UseLoop,
// Use getSCEVAtScope to attempt to simplify other loops out of
// the picture.
- SCEVHandle AddRecStart = AddRec->getStart();
+ const SCEV* AddRecStart = AddRec->getStart();
AddRecStart = SE->getSCEVAtScope(AddRecStart, UseLoop);
- SCEVHandle AddRecStride = AddRec->getStepRecurrence(*SE);
+ const SCEV* AddRecStride = AddRec->getStepRecurrence(*SE);
// FIXME: If Start contains an SCEVAddRecExpr from a different loop, other
// than an outer loop of the current loop, reject it. LSR has no concept of
@@ -196,13 +196,13 @@ bool IVUsers::AddUsersIfInteresting(Instruction *I) {
return true; // Instruction already handled.
// Get the symbolic expression for this instruction.
- SCEVHandle ISE = SE->getSCEV(I);
+ const SCEV* ISE = SE->getSCEV(I);
if (isa<SCEVCouldNotCompute>(ISE)) return false;
// Get the start and stride for this expression.
Loop *UseLoop = LI->getLoopFor(I->getParent());
- SCEVHandle Start = SE->getIntegerSCEV(0, ISE->getType());
- SCEVHandle Stride = Start;
+ const SCEV* Start = SE->getIntegerSCEV(0, ISE->getType());
+ const SCEV* Stride = Start;
if (!getSCEVStartAndStride(ISE, L, UseLoop, Start, Stride, SE, DT))
return false; // Non-reducible symbolic expression, bail out.
@@ -254,7 +254,7 @@ bool IVUsers::AddUsersIfInteresting(Instruction *I) {
if (IVUseShouldUsePostIncValue(User, I, L, LI, DT, this)) {
// The value used will be incremented by the stride more than we are
// expecting, so subtract this off.
- SCEVHandle NewStart = SE->getMinusSCEV(Start, Stride);
+ const SCEV* NewStart = SE->getMinusSCEV(Start, Stride);
StrideUses->addUser(NewStart, User, I);
StrideUses->Users.back().setIsUseOfPostIncrementedValue(true);
DOUT << " USING POSTINC SCEV, START=" << *NewStart<< "\n";
@@ -295,9 +295,9 @@ bool IVUsers::runOnLoop(Loop *l, LPPassManager &LPM) {
/// getReplacementExpr - Return a SCEV expression which computes the
/// value of the OperandValToReplace of the given IVStrideUse.
-SCEVHandle IVUsers::getReplacementExpr(const IVStrideUse &U) const {
+const SCEV* IVUsers::getReplacementExpr(const IVStrideUse &U) const {
// Start with zero.
- SCEVHandle RetVal = SE->getIntegerSCEV(0, U.getParent()->Stride->getType());
+ const SCEV* RetVal = SE->getIntegerSCEV(0, U.getParent()->Stride->getType());
// Create the basic add recurrence.
RetVal = SE->getAddRecExpr(RetVal, U.getParent()->Stride, L);
// Add the offset in a separate step, because it may be loop-variant.
@@ -308,7 +308,7 @@ SCEVHandle IVUsers::getReplacementExpr(const IVStrideUse &U) const {
RetVal = SE->getAddExpr(RetVal, U.getParent()->Stride);
// Evaluate the expression out of the loop, if possible.
if (!L->contains(U.getUser()->getParent())) {
- SCEVHandle ExitVal = SE->getSCEVAtScope(RetVal, L->getParentLoop());
+ const SCEV* ExitVal = SE->getSCEVAtScope(RetVal, L->getParentLoop());
if (ExitVal->isLoopInvariant(L))
RetVal = ExitVal;
}
@@ -325,7 +325,7 @@ void IVUsers::print(raw_ostream &OS, const Module *M) const {
OS << ":\n";
for (unsigned Stride = 0, e = StrideOrder.size(); Stride != e; ++Stride) {
- std::map<SCEVHandle, IVUsersOfOneStride*>::const_iterator SI =
+ std::map<const SCEV*, IVUsersOfOneStride*>::const_iterator SI =
IVUsesByStride.find(StrideOrder[Stride]);
assert(SI != IVUsesByStride.end() && "Stride doesn't exist!");
OS << " Stride " << *SI->first->getType() << " " << *SI->first << ":\n";
diff --git a/lib/Analysis/LoopVR.cpp b/lib/Analysis/LoopVR.cpp
index 0a3d06bed7..ae715ac586 100644
--- a/lib/Analysis/LoopVR.cpp
+++ b/lib/Analysis/LoopVR.cpp
@@ -26,8 +26,8 @@ char LoopVR::ID = 0;
static RegisterPass<LoopVR> X("loopvr", "Loop Value Ranges", false, true);
/// getRange - determine the range for a particular SCEV within a given Loop
-ConstantRange LoopVR::getRange(SCEVHandle S, Loop *L, ScalarEvolution &SE) {
- SCEVHandle T = SE.getBackedgeTakenCount(L);
+ConstantRange LoopVR::getRange(const SCEV* S, Loop *L, ScalarEvolution &SE) {
+ const SCEV* T = SE.getBackedgeTakenCount(L);
if (isa<SCEVCouldNotCompute>(T))
return ConstantRange(cast<IntegerType>(S->getType())->getBitWidth(), true);
@@ -36,7 +36,7 @@ ConstantRange LoopVR::getRange(SCEVHandle S, Loop *L, ScalarEvolution &SE) {
}
/// getRange - determine the range for a particular SCEV with a given trip count
-ConstantRange LoopVR::getRange(SCEVHandle S, SCEVHandle T, ScalarEvolution &SE){
+ConstantRange LoopVR::getRange(const SCEV* S, const SCEV* T, ScalarEvolution &SE){
if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S))
return ConstantRange(C->getValue()->getValue());
@@ -182,8 +182,8 @@ ConstantRange LoopVR::getRange(SCEVHandle S, SCEVHandle T, ScalarEvolution &SE){
if (!Trip) return FullSet;
if (AddRec->isAffine()) {
- SCEVHandle StartHandle = AddRec->getStart();
- SCEVHandle StepHandle = AddRec->getOperand(1);
+ const SCEV* StartHandle = AddRec->getStart();
+ const SCEV* StepHandle = AddRec->getOperand(1);
const SCEVConstant *Step = dyn_cast<SCEVConstant>(StepHandle);
if (!Step) return FullSet;
@@ -194,7 +194,7 @@ ConstantRange LoopVR::getRange(SCEVHandle S, SCEVHandle T, ScalarEvolution &SE){
if ((TripExt * StepExt).ugt(APInt::getLowBitsSet(ExWidth, ExWidth >> 1)))
return FullSet;
- SCEVHandle EndHandle = SE.getAddExpr(StartHandle,
+ const SCEV* EndHandle = SE.getAddExpr(StartHandle,
SE.getMulExpr(T, StepHandle));
const SCEVConstant *Start = dyn_cast<SCEVConstant>(StartHandle);
const SCEVConstant *End = dyn_cast<SCEVConstant>(EndHandle);
@@ -254,7 +254,7 @@ ConstantRange LoopVR::compute(Value *V) {
ScalarEvolution &SE = getAnalysis<ScalarEvolution>();
- SCEVHandle S = SE.getSCEV(I);
+ const SCEV* S = SE.getSCEV(I);
if (isa<SCEVUnknown>(S) || isa<SCEVCouldNotCompute>(S))
return ConstantRange(cast<IntegerType>(V->getType())->getBitWidth(), false);
diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index d9394805c8..f45562363a 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -14,7 +14,7 @@
// There are several aspects to this library. First is the representation of
// scalar expressions, which are represented as subclasses of the SCEV class.
// These classes are used to represent certain types of subexpressions that we
-// can handle. These classes are reference counted, managed by the SCEVHandle
+// can handle. These classes are reference counted, managed by the const SCEV*
// class. We only create one SCEV of a particular shape, so pointer-comparisons
// for equality are legal.
//
@@ -152,9 +152,9 @@ bool SCEVCouldNotCompute::hasComputableLoopEvolution(const Loop *L) const {
return false;
}
-SCEVHandle SCEVCouldNotCompute::
-replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
- const SCEVHandle &Conc,
+const SCEV* SCEVCouldNotCompute::
+replaceSymbolicValuesWithConcrete(const SCEV* Sym,
+ const SCEV* Conc,
ScalarEvolution &SE) const {
return this;
}
@@ -169,20 +169,20 @@ bool SCEVCouldNotCompute::classof(const SCEV *S) {
// SCEVConstants - Only allow the creation of one SCEVConstant for any
-// particular value. Don't use a SCEVHandle here, or else the object will
+// particular value. Don't use a const SCEV* here, or else the object will
// never be deleted!
-SCEVHandle ScalarEvolution::getConstant(ConstantInt *V) {
+const SCEV* ScalarEvolution::getConstant(ConstantInt *V) {
SCEVConstant *&R = SCEVConstants[V];
if (R == 0) R = new SCEVConstant(V, this);
return R;
}
-SCEVHandle ScalarEvolution::getConstant(const APInt& Val) {
+const SCEV* ScalarEvolution::getConstant(const APInt& Val) {
return getConstant(ConstantInt::get(Val));
}
-SCEVHandle
+const SCEV*
ScalarEvolution::getConstant(const Type *Ty, uint64_t V, bool isSigned) {
return getConstant(ConstantInt::get(cast<IntegerType>(Ty), V, isSigned));
}
@@ -194,7 +194,7 @@ void SCEVConstant::print(raw_ostream &OS) const {
}
SCEVCastExpr::SCEVCastExpr(unsigned SCEVTy,
- const SCEVHandle &op, const Type *ty,
+ const SCEV* op, const Type *ty,
const ScalarEvolution* p)
: SCEV(SCEVTy, p), Op(op), Ty(ty) {}
@@ -205,10 +205,10 @@ bool SCEVCastExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
}
// SCEVTruncates - Only allow the creation of one SCEVTruncateExpr for any
-// particular input. Don't use a SCEVHandle here, or else the object will
+// particular input. Don't use a const SCEV* here, or else the object will
// never be deleted!
-SCEVTruncateExpr::SCEVTruncateExpr(const SCEVHandle &op, const Type *ty,
+SCEVTruncateExpr::SCEVTruncateExpr(const SCEV* op, const Type *ty,
const ScalarEvolution* p)
: SCEVCastExpr(scTruncate, op, ty, p) {
assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) &&
@@ -222,10 +222,10 @@ void SCEVTruncateExpr::print(raw_ostream &OS) const {
}
// SCEVZeroExtends - Only allow the creation of one SCEVZeroExtendExpr for any
-// particular input. Don't use a SCEVHandle here, or else the object will never
+// particular input. Don't use a const SCEV* here, or else the object will never
// be deleted!
-SCEVZeroExtendExpr::SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty,
+SCEVZeroExtendExpr::SCEVZeroExtendExpr(const SCEV* op, const Type *ty,
const ScalarEvolution* p)
: SCEVCastExpr(scZeroExtend, op, ty, p) {
assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) &&
@@ -238,10 +238,10 @@ void SCEVZeroExtendExpr::print(raw_ostream &OS) const {
}
// SCEVSignExtends - Only allow the creation of one SCEVSignExtendExpr for any
-// particular input. Don't use a SCEVHandle here, or else the object will never
+// particular input. Don't use a const SCEV* here, or else the object will never
// be deleted!
-SCEVSignExtendExpr::SCEVSignExtendExpr(const SCEVHandle &op, const Type *ty,
+SCEVSignExtendExpr::SCEVSignExtendExpr(const SCEV* op, const Type *ty,
const ScalarEvolution* p)
: SCEVCastExpr(scSignExtend, op, ty, p) {
assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) &&
@@ -254,7 +254,7 @@ void SCEVSignExtendExpr::print(raw_ostream &OS) const {
}
// SCEVCommExprs - Only allow the creation of one SCEVCommutativeExpr for any
-// particular input. Don't use a SCEVHandle here, or else the object will never
+// particular input. Don't use a const SCEV* here, or else the object will never
// be deleted!
void SCEVCommutativeExpr::print(raw_ostream &OS) const {
@@ -266,15 +266,15 @@ void SCEVCommutativeExpr::print(raw_ostream &OS) const {
OS << ")";
}
-SCEVHandle SCEVCommutativeExpr::
-replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
- const SCEVHandle &Conc,
+const SCEV* SCEVCommutativeExpr::
+replaceSymbolicValuesWithConcrete(const SCEV* Sym,
+ const SCEV* Conc,
ScalarEvolution &SE) const {
for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
- SCEVHandle H =
+ const SCEV* H =
getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
if (H != getOperand(i)) {
- SmallVector<SCEVHandle, 8> NewOps;
+ SmallVector<const SCEV*, 8> NewOps;
NewOps.reserve(getNumOperands());
for (unsigned j = 0; j != i; ++j)
NewOps.push_back(getOperand(j));
@@ -308,7 +308,7 @@ bool SCEVNAryExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
// 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
+// input. Don't use a const SCEV* here, or else the object will never be
// deleted!
bool SCEVUDivExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
@@ -329,18 +329,18 @@ const Type *SCEVUDivExpr::getType() const {
}
// SCEVAddRecExprs - Only allow the creation of one SCEVAddRecExpr for any
-// particular input. Don't use a SCEVHandle here, or else the object will never
+// particular input. Don't use a const SCEV* here, or else the object will never
// be deleted!
-SCEVHandle SCEVAddRecExpr::
-replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
- const SCEVHandle &Conc,
+const SCEV* SCEVAddRecExpr::
+replaceSymbolicValuesWithConcrete(const SCEV* Sym,
+ const SCEV* Conc,
ScalarEvolution &SE) const {
for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
- SCEVHandle H =
+ const SCEV* H =
getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
if (H != getOperand(i)) {
- SmallVector<SCEVHandle, 8> NewOps;
+ SmallVector<const SCEV*, 8> NewOps;
NewOps.reserve(getNumOperands());
for (unsigned j = 0; j != i; ++j)
NewOps.push_back(getOperand(j));
@@ -374,7 +374,7 @@ void SCEVAddRecExpr::print(raw_ostream &OS) const {
}
// SCEVUnknowns - Only allow the creation of one SCEVUnknown for any particular
-// value. Don't use a SCEVHandle here, or else the object will never be
+// value. Don't use a const SCEV* here, or else the object will never be
// deleted!
bool SCEVUnknown::isLoopInvariant(const Loop *L) const {
@@ -531,7 +531,7 @@ namespace {
/// this to depend on where the addresses of various SCEV objects happened to
/// land in memory.
///
-static void GroupByComplexity(SmallVectorImpl<SCEVHandle> &Ops,
+static void GroupByComplexity(SmallVectorImpl<const SCEV*> &Ops,
LoopInfo *LI) {
if (Ops.size() < 2) return; // Noop
if (Ops.size() == 2) {
@@ -574,7 +574,7 @@ static void GroupByComplexity(SmallVectorImpl<SCEVHandle> &Ops,
/// BinomialCoefficient - Compute BC(It, K). The result has width W.
/// Assume, K > 0.
-static SCEVHandle BinomialCoefficient(SCEVHandle It, unsigned K,
+static const SCEV* BinomialCoefficient(const SCEV* It, unsigned K,
ScalarEvolution &SE,
const Type* ResultTy) {
// Handle the simplest case efficiently.
@@ -667,15 +667,15 @@ static SCEVHandle BinomialCoefficient(SCEVHandle It, unsigned K,
// Calculate the product, at width T+W
const IntegerType *CalculationTy = IntegerType::get(CalculationBits);
- SCEVHandle Dividend = SE.getTruncateOrZeroExtend(It, CalculationTy);
+ const SCEV* Dividend = SE.getTruncateOrZeroExtend(It, CalculationTy);
for (unsigned i = 1; i != K; ++i) {
- SCEVHandle S = SE.getMinusSCEV(It, SE.getIntegerSCEV(i, It->getType()));
+ const SCEV* S = SE.getMinusSCEV(It, SE.getIntegerSCEV(i, It->getType()));
Dividend = SE.getMulExpr(Dividend,
SE.getTruncateOrZeroExtend(S, CalculationTy));
}
// Divide by 2^T
- SCEVHandle DivResult = SE.getUDivExpr(Dividend, SE.getConstant(DivFactor));
+ const SCEV* DivResult = SE.getUDivExpr(Dividend, SE.getConstant(DivFactor));
// Truncate the result, and divide by K! / 2^T.
@@ -692,14 +692,14 @@ static SCEVHandle BinomialCoefficient(SCEVHandle It, unsigned K,
///
/// where BC(It, k) stands for binomial coefficient.
///
-SCEVHandle SCEVAddRecExpr::evaluateAtIteration(SCEVHandle It,
+const SCEV* SCEVAddRecExpr::evaluateAtIteration(const SCEV* It,
ScalarEvolution &SE) const {
- SCEVHandle Result = getStart();
+ const SCEV* Result = getStart();
for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
// The computation is correct in the face of overflow provided that the
// multiplication is performed _after_ the evaluation of the binomial
// coefficient.
- SCEVHandle Coeff = BinomialCoefficient(It, i, SE, getType());
+ const SCEV* Coeff = BinomialCoefficient(It, i, SE, getType());
if (isa<SCEVCouldNotCompute>(Coeff))
return Coeff;
@@ -712,7 +712,7 @@ SCEVHandle SCEVAddRecExpr::evaluateAtIteration(SCEVHandle It,
// SCEV Expression folder implementations
//===----------------------------------------------------------------------===//
-SCEVHandle ScalarEvolution::getTruncateExpr(const SCEVHandle &Op,
+const SCEV* ScalarEvolution::getTruncateExpr(const SCEV* Op,
const Type *Ty) {
assert(getTypeSizeInBits(Op->getType()) > getTypeSizeInBits(Ty) &&
"This is not a truncating conversion!");
@@ -738,7 +738,7 @@ SCEVHandle ScalarEvolution::getTruncateExpr(const SCEVHandle &Op,
// If the input value is a chrec scev, truncate the chrec's operands.
if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) {
- SmallVector<SCEVHandle, 4> Operands;
+ SmallVector<const SCEV*, 4> Operands;
for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
Operands.push_back(getTruncateExpr(AddRec->getOperand(i), Ty));
return getAddRecExpr(Operands, AddRec->getLoop());
@@ -749,7 +749,7 @@ SCEVHandle ScalarEvolution::getTruncateExpr(const SCEVHandle &Op,
return Result;
}
-SCEVHandle ScalarEvolution::getZeroExtendExpr(const SCEVHandle &Op,
+const SCEV* ScalarEvolution::getZeroExtendExpr(const SCEV* Op,
const Type *Ty) {
assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
"This is not an extending conversion!");
@@ -782,28 +782,28 @@ SCEVHandle ScalarEvolution::getZeroExtendExpr(const SCEVHandle &Op,
// in infinite recursion. In the later case, the analysis code will
// cope with a conservative value, and it will take care to purge
// that value once it has finished.
- SCEVHandle MaxBECount = getMaxBackedgeTakenCount(AR->getLoop());
+ const SCEV* MaxBECount = getMaxBackedgeTakenCount(AR->getLoop());
if (!isa<SCEVCouldNotCompute>(MaxBECount)) {
// Manually compute the final value for AR, checking for
// overflow.
- SCEVHandle Start = AR->getStart();
- SCEVHandle Step = AR->getStepRecurrence(*this);
+ const SCEV* Start = AR->getStart();
+ const SCEV* Step = AR->getStepRecurrence(*this);
// Check whether the backedge-taken count can be losslessly casted to
// the addrec's type. The count is always unsigned.
- SCEVHandle CastedMaxBECount =
+ const SCEV* CastedMaxBECount =
getTruncateOrZeroExtend(MaxBECount, Start->getType());
- SCEVHandle RecastedMaxBECount =
+ const SCEV* RecastedMaxBECount =
getTruncateOrZeroExtend(CastedMaxBECount, MaxBECount->getType());
if (MaxBECount == RecastedMaxBECount) {
const Type *WideTy =
IntegerType::get(getTypeSizeInBits(Start->getType()) * 2);
// Check whether Start+Step*MaxBECount has no unsigned overflow.
- SCEVHandle ZMul =
+ const SCEV* ZMul =
getMulExpr(CastedMaxBECount,
getTruncateOrZeroExtend(Step, Start->getType()));
- SCEVHandle Add = getAddExpr(Start, ZMul);
- SCEVHandle OperandExtendedAdd =
+ const SCEV* Add = getAddExpr(Start, ZMul);
+ const SCEV* OperandExtendedAdd =
getAddExpr(getZeroExtendExpr(Start, WideTy),
getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy),
getZeroExtendExpr(Step, WideTy)));
@@ -815,7 +815,7 @@ SCEVHandle ScalarEvolution::getZeroExtendExpr(const SCEVHandle &Op,
// Similar to above, only this time treat the step value as signed.
// This covers loops that count down.
- SCEVHandle SMul =
+ const SCEV* SMul =
getMulExpr(CastedMaxBECount,
getTruncateOrSignExtend(Step, Start->getType()));
Add = getAddExpr(Start, SMul);
@@ -837,7 +837,7 @@ SCEVHandle ScalarEvolution::getZeroExtendExpr(const SCEVHandle &Op,
return Result;
}
-SCEVHandle ScalarEvolution::getSignExtendExpr(const SCEVHandle &Op,
+const SCEV* ScalarEvolution::getSignExtendExpr(const SCEV* Op,
const Type *Ty) {
assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
"This is not an extending conversion!");
@@ -870,28 +870,28 @@ SCEVHandle ScalarEvolution::getSignExtendExpr(const SCEVHandle &Op,
// in infinite recursion. In the later case, the analysis code will
// cope with a conservative value, and it will take care to purge
// that value once it has finished.
- SCEVHandle MaxBECount = getMaxBackedgeTakenCount(AR->getLoop());
+ const SCEV* MaxBECount = getMaxBackedgeTakenCount(AR->getLoop());
if (!isa<SCEVCouldNotCompute>(MaxBECount)) {
// Manually compute the final value for AR, checking for
// overflow.
- SCEVHandle Start = AR->getStart();
- SCEVHandle Step = AR->getStepRecurrence(*this);
+ const SCEV* Start = AR->getStart();
+ const SCEV* Step = AR->getStepRecurrence(*this);
// Check whether the backedge-taken count can be losslessly casted to
// the addrec's type. The count is always unsigned.
- SCEVHandle CastedMaxBECount =
+ const SCEV* CastedMaxBECount =
getTruncateOrZeroExtend(MaxBECount, Start->getType());
- SCEVHandle RecastedMaxBECount =
+ const SCEV* RecastedMaxBECount =
getTruncateOrZeroExtend(CastedMaxBECount, MaxBECount->getType());
if (MaxBECount == RecastedMaxBECount) {
const Type *WideTy =
IntegerType::get(getTypeSizeInBits(Start->getType()) * 2);
// Check whether Start+Step*MaxBECount has no signed overflow.
- SCEVHandle SMul =
+ const SCEV* SMul =
getMulExpr(CastedMaxBECount,
getTruncateOrSignExtend(Step, Start->getType()));
- SCEVHandle Add = getAddExpr(Start, SMul);
- SCEVHandle OperandExtendedAdd =
+ const SCEV* Add = getAddExpr(Start, SMul);
+ const SCEV* OperandExtendedAdd =
getAddExpr(getSignExtendExpr(Start, WideTy),
getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy),
getSignExtendExpr(Step, WideTy)));
@@ -912,7 +912,7 @@ SCEVHandle ScalarEvolution::getSignExtendExpr(const SCEVHandle &Op,
/// getAnyExtendExpr - Return a SCEV for the given operand extended with
/// unspecified bits out to the given type.
///
-SCEVHandle ScalarEvolution::getAnyExtendExpr(const SCEVHandle &Op,
+const SCEV* ScalarEvolution::getAnyExtendExpr(const SCEV* Op,
const Type *Ty) {
assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
"This is not an extending conversion!");
@@ -927,19 +927,19 @@ SCEVHandle ScalarEvolution::getAnyExtendExpr(const SCEVHandle &Op,
// Peel off a truncate cast.
if (const SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(Op)) {
- SCEVHandle NewOp = T->getOperand();
+ const SCEV* NewOp = T->getOperand();
if (getTypeSizeInBits(NewOp->getType()) < getTypeSizeInBits(Ty))
return getAnyExtendExpr(NewOp, Ty);
return getTruncateOrNoop(NewOp, Ty);
}
// Next try a zext cast. If the cast is folded, use it.
- SCEVHandle ZExt = getZeroExtendExpr(Op, Ty);
+ const SCEV* ZExt = getZeroExtendExpr(Op, Ty);
if (!isa<SCEVZeroExtendExpr>(ZExt))
return ZExt;
// Next try a sext cast. If the cast is folded, use it.
- SCEVHandle SExt = getSignExtendExpr(Op, Ty);
+ const SCEV* SExt = getSignExtendExpr(Op, Ty);
if (!isa<SCEVSignExtendExpr>(SExt))
return SExt;
@@ -977,10 +977,10 @@ SCEVHandle ScalarEvolution::getAnyExtendExpr(const SCEVHandle &Op,
/// is also used as a check to avoid infinite recursion.
///
static bool
-CollectAddOperandsWithScales(DenseMap<SCEVHandle, APInt> &M,
- SmallVector<SCEVHandle, 8> &NewOps,
+CollectAddOperandsWithScales(DenseMap<const SCEV*, APInt> &M,
+ SmallVector<const SCEV*, 8> &NewOps,
APInt &AccumulatedConstant,
- const SmallVectorImpl<SCEVHandle> &Ops,
+ const SmallVectorImpl<const SCEV*> &Ops,
const APInt &Scale,
ScalarEvolution &SE) {
bool Interesting = false;
@@ -1001,9 +1001,9 @@ CollectAddOperandsWithScales(DenseMap<SCEVHandle, APInt> &M,
} else {
// A multiplication of a constant with some other value. Update
// the map.
- SmallVector<SCEVHandle, 4> MulOps(Mul->op_begin()+1, Mul->op_end());
- SCEVHandle Key = SE.getMulExpr(MulOps);
- std::pair<DenseMap<SCEVHandle, APInt>::iterator, bool> Pair =
+ SmallVector<const SCEV*, 4> MulOps(Mul->op_begin()+1, Mul->op_end());
+ const SCEV* Key = SE.getMulExpr(MulOps);
+ std::pair<DenseMap<const SCEV*, APInt>::iterator, bool> Pair =
M.insert(std::make_pair(Key, APInt()));
if (Pair.second) {
Pair.first->second = NewScale;
@@ -1022,7 +1022,7 @@ CollectAddOperandsWithScales(DenseMap<SCEVHandle, APInt> &M,
AccumulatedConstant += Scale * C->getValue()->getValue();
} else {
// An ordinary operand. Update the map.
- std::pair<DenseMap<SCEVHandle, APInt>::iterator, bool> Pair =
+ std::pair<DenseMap<const SCEV*, APInt>::iterator, bool> Pair =
M.insert(std::make_pair(Ops[i], APInt()));
if (Pair.second) {
Pair.first->second = Scale;
@@ -1049,7 +1049,7 @@ namespace {
/// getAddExpr - Get a canonical add expression, or something simpler if
/// possible.
-SCEVHandle ScalarEvolution::getAddExpr(SmallVectorImpl<SCEVHandle> &Ops) {
+const SCEV* ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV*> &Ops) {
assert(!Ops.empty() && "Cannot get empty add!");
if (Ops.size() == 1) return Ops[0];
#ifndef NDEBUG
@@ -1093,8 +1093,8 @@ SCEVHandle ScalarEvolution::getAddExpr(SmallVectorImpl<SCEVHandle> &Ops) {
if (Ops[i] == Ops[i+1]) { // X + Y + Y --> X + Y*2
// Found a match, merge the two values into a multiply, and add any
// remaining values to the result.
- SCEVHandle Two = getIntegerSCEV(2, Ty);
- SCEVHandle Mul = getMulExpr(Ops[i], Two);
+ const SCEV* Two = getIntegerSCEV(2, Ty);
+ const SCEV* Mul = getMulExpr(Ops[i], Two);
if (Ops.size() == 2)
return Mul;
Ops.erase(Ops.begin()+i, Ops.begin()+i+2);
@@ -1110,7 +1110,7 @@ SCEVHandle ScalarEvolution::getAddExpr(SmallVectorImpl<SCEVHandle> &Ops) {
const SCEVTruncateExpr *Trunc = cast<SCEVTruncateExpr>(Ops[Idx]);
const Type *DstType = Trunc->getType();
const Type *SrcType = Trunc->getOperand()->getType();
- SmallVector<SCEVHandle, 8> LargeOps;
+ SmallVector<const SCEV*, 8> LargeOps;
bool Ok = true;
// Check all the operands to see if they can be represented in the
// source type of the truncate.
@@ -1126,7 +1126,7 @@ SCEVHandle ScalarEvolution::getAddExpr(SmallVectorImpl<SCEVHandle> &Ops) {
// is much more likely to be foldable here.
LargeOps.push_back(getSignExtendExpr(C, SrcType));
} else if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(Ops[i])) {
- SmallVector<SCEVHandle, 8> LargeMulOps;
+ SmallVector<const SCEV*, 8> LargeMulOps;
for (unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
if (const SCEVTruncateExpr *T =
dyn_cast<SCEVTruncateExpr>(M->getOperand(j))) {
@@ -1154,7 +1154,7 @@ SCEVHandle ScalarEvolution::getAddExpr(SmallVectorImpl<SCEVHandle> &Ops) {
}
if (Ok) {
// Evaluate the expression in the larger type.
- SCEVHandle Fold = getAddExpr(LargeOps);
+ const SCEV* Fold = getAddExpr(LargeOps);
// If it folds to something simple, use it. Otherwise, don't.
if (isa<SCEVConstant>(Fold) || isa<SCEVUnknown>(Fold))
return getTruncateExpr(Fold, DstType);
@@ -1191,23 +1191,23 @@ SCEVHandle ScalarEvolution::getAddExpr(SmallVectorImpl<SCEVHandle> &Ops) {
// operands multiplied by constant values.
if (Idx < Ops.size() && isa<SCEVMulExpr>(Ops[Idx])) {
uint64_t BitWidth = getTypeSizeInBits(Ty);
- DenseMap<SCEVHandle, APInt> M;
- SmallVector<SCEVHandle, 8> NewOps;
+ DenseMap<const SCEV*, APInt> M;
+ SmallVector<const SCEV*, 8> NewOps;
APInt AccumulatedConstant(BitWidth, 0);
if (CollectAddOperandsWithScales(M, NewOps, AccumulatedConstant,
Ops, APInt(BitWidth, 1), *this)) {
// Some interesting folding opportunity is present, so its worthwhile to
// re-generate the operands list. Group the operands by constant scale,
// to avoid multiplying by the same constant scale multiple times.
- std::map<APInt, SmallVector<SCEVHandle, 4>, APIntCompare> MulOpLists;
- for (SmallVector<SCEVHandle, 8>::iterator I = NewOps.begin(),
+ std::map<APInt, SmallVector<const SCEV*, 4>, APIntCompare> MulOpLists;
+ for (SmallVector<const SCEV*, 8>::iterator I = NewOps.begin(),
E = NewOps.end(); I != E; ++I)
MulOpLists[M.find(*I)->second].push_back(*I);
// Re-generate the operands list.
Ops.clear();
if (AccumulatedConstant != 0)
Ops.push_back(getConstant(AccumulatedConstant));
- for (std::map<APInt, SmallVector<SCEVHandle, 4>, APIntCompare>::iterator I =
+ for (std::map<APInt, SmallVector<const SCEV*, 4>, APIntCompare>::iterator I =
MulOpLists.begin(), E = MulOpLists.end(); I != E; ++I)
if (I->first != 0)
Ops.push_back(getMulExpr(getConstant(I->first), getAddExpr(I->second)));
@@ -1229,17 +1229,17 @@ SCEVHandle ScalarEvolution::getAddExpr(SmallVectorImpl<SCEVHandle> &Ops) {
for (unsigned AddOp = 0, e = Ops.size(); AddOp != e; ++AddOp)
if (MulOpSCEV == Ops[AddOp] && !isa<SCEVConstant>(Ops[AddOp])) {
// Fold W + X + (X * Y * Z) --> W + (X * ((Y*Z)+1))
- SCEVHandle InnerMul = Mul->getOperand(MulOp == 0);
+ const SCEV* InnerMul = Mul->getOperand(MulOp == 0);
if (Mul->getNumOperands() != 2) {
// If the multiply has more than two operands, we must get the
// Y*Z term.
- SmallVector<SCEVHandle, 4> MulOps(Mul->op_begin(), Mul->op_end());
+ SmallVector<const SCEV*, 4> MulOps(Mul->op_begin(), Mul->op_end());
MulOps.erase(MulOps.begin()+MulOp);
InnerMul = getMulExpr(MulOps);
}
- SCEVHandle One = getIntegerSCEV(1, Ty);
- SCEVHandle AddOne = getAddExpr(InnerMul, One);
- SCEVHandle OuterMul = getMulExpr(AddOne, Ops[AddOp]);
+ const SCEV* One = getIntegerSCEV(1, Ty);
+ const SCEV* AddOne = getAddExpr(InnerMul, One);
+ const SCEV* OuterMul = getMulExpr(AddOne, Ops[AddOp]);
if (Ops.size() == 2) return OuterMul;
if (AddOp < Idx) {
Ops.erase(Ops.begin()+AddOp);
@@ -1263,21 +1263,21 @@ SCEVHandle ScalarEvolution::getAddExpr(SmallVectorImpl<SCEVHandle> &Ops) {
OMulOp != e; ++OMulOp)
if (OtherMul->getOperand(OMulOp) == MulOpSCEV) {
// Fold X + (A*B*C) + (A*D*E) --> X + (A*(B*C+D*E))
- SCEVHandle InnerMul1 = Mul->getOperand(MulOp == 0);
+ const SCEV* InnerMul1 = Mul->getOperand(MulOp == 0);
if (Mul->getNumOperands() != 2) {
- SmallVector<SCEVHandle, 4> MulOps(Mul->op_begin(), Mul->op_end());
+ SmallVector<const SCEV*, 4> MulOps(Mul->op_begin(), Mul->op_end());
MulOps.erase(MulOps.begin()+MulOp);
InnerMul1 = getMulExpr(MulOps);
}
- SCEVHandle InnerMul2 = OtherMul->getOperand(OMulOp == 0);
+ const SCEV* InnerMul2 = OtherMul->getOperand(OMulOp == 0);
if (OtherMul->getNumOperands() != 2) {
- SmallVector<SCEVHandle, 4> MulOps(OtherMul->op_begin(),
+ SmallVector<const SCEV*, 4> MulOps(OtherMul->op_begin(),
OtherMul->op_end());
MulOps.erase(MulOps.begin()+OMulOp);
InnerMul2 = getMulExpr(MulOps);
}
- SCEVHandle InnerMulSum = getAddExpr(InnerMul1,InnerMul2);
- SCEVHandle OuterMul = getMulExpr(MulOpSCEV, InnerMulSum);
+ const SCEV* InnerMulSum = getAddExpr(InnerMul1,InnerMul2);
+ const SCEV* OuterMul = getMulExpr(MulOpSCEV, InnerMulSum);
if (Ops.size() == 2) return OuterMul;
Ops.erase(Ops.begin()+Idx);
Ops.erase(Ops.begin()+OtherMulIdx-1);
@@ -1298,7 +1298,7 @@ SCEVHandle ScalarEvolution::getAddExpr(SmallVectorImpl<SCEVHandle> &Ops) {
for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
// Scan all of the other operands to this add and add them to the vector if
// they are loop invariant w.r.t. the recurrence.
- SmallVector<SCEVHandle, 8> LIOps;
+ SmallVector<const SCEV*, 8> LIOps;
const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
for (unsigned i = 0, e = Ops.size(); i != e; ++i)
if (Ops[i]->isLoopInvariant(AddRec->getLoop())) {
@@ -1312,11 +1312,11 @@ SCEVHandle ScalarEvolution::getAddExpr(SmallVectorImpl<SCEVHandle> &Ops) {
// NLI + LI + {Start,+,Step} --> NLI + {LI+Start,+,Step}
LIOps.push_back(AddRec->getStart());
- SmallVector<SCEVHandle, 4> AddRecOps(AddRec->op_begin(),
+ SmallVector<const SCEV*, 4> AddRecOps(AddRec->op_begin(),
AddRec->op_end());
AddRecOps[0] = getAddExpr(LIOps);
- SCEVHandle NewRec = getAddRecExpr(AddRecOps, AddRec->getLoop());
+ 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;
@@ -1338,7 +1338,7 @@ SCEVHandle ScalarEvolution::getAddExpr(SmallVectorImpl<SCEVHandle> &Ops) {
const SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
if (AddRec->getLoop() == OtherAddRec->getLoop()) {
// Other + {A,+,B} + {C,+,D} --> Other + {A+C,+,B+D}
- SmallVector<SCEVHandle, 4> NewOps(AddRec->op_begin(), AddRec->op_end());
+ SmallVector<const SCEV*, 4> NewOps(AddRec->op_begin(), AddRec->op_end());
for (unsigned i = 0, e = OtherAddRec->getNumOperands(); i != e; ++i) {
if (i >= NewOps.size()) {
NewOps.insert(NewOps.end(), OtherAddRec->op_begin()+i,
@@ -1347,7 +1347,7 @@ SCEVHandle ScalarEvolution::getAddExpr(SmallVectorImpl<SCEVHandle> &Ops) {
}
NewOps[i] = getAddExpr(NewOps[i], OtherAddRec->getOperand(i));
}
- SCEVHandle NewAddRec = getAddRecExpr(NewOps, AddRec->getLoop());
+ const SCEV* NewAddRec = getAddRecExpr(NewOps, AddRec->getLoop());
if (Ops.size() == 2) return NewAddRec;
@@ -1374,7 +1374,7 @@ SCEVHandle ScalarEvolution::getAddExpr(SmallVectorImpl<SCEVHandle> &Ops) {
/// getMulExpr - Get a canonical multiply expression, or something simpler if
/// possible.
-SCEVHandle ScalarEvolution::getMulExpr(SmallVectorImpl<SCEVHandle> &Ops) {
+const SCEV* ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV*> &Ops) {
assert(!Ops.empty() && "Cannot get empty mul!");
#ifndef NDEBUG
for (unsigned i = 1, e = Ops.size(); i != e; ++i)
@@ -1455,7 +1455,7 @@ SCEVHandle ScalarEvolution::getMulExpr(SmallVectorImpl<SCEVHandle> &Ops) {
for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
// Scan all of the other operands to this mul and add them to the vector if
// they are loop invariant w.r.t. the recurrence.
- SmallVector<SCEVHandle, 8> LIOps;
+ SmallVector<const SCEV*, 8> LIOps;
const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
fo