static cl::opt<unsigned>
MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden,
cl::desc("Maximum number of iterations SCEV will "
- "symbolically execute a constant derived loop"),
+ "symbolically execute a constant "
+ "derived loop"),
cl::init(100));
static RegisterPass<ScalarEvolution>
SCEVCouldNotCompute::SCEVCouldNotCompute() :
SCEV(scCouldNotCompute) {}
+void SCEVCouldNotCompute::Profile(FoldingSetNodeID &ID) const {
+ assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
+}
+
bool SCEVCouldNotCompute::isLoopInvariant(const Loop *L) const {
assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
return false;
return false;
}
-const SCEV* SCEVCouldNotCompute::
-replaceSymbolicValuesWithConcrete(const SCEV* Sym,
- const SCEV* Conc,
- ScalarEvolution &SE) const {
+const SCEV *
+SCEVCouldNotCompute::replaceSymbolicValuesWithConcrete(
+ const SCEV *Sym,
+ const SCEV *Conc,
+ ScalarEvolution &SE) const {
return this;
}
return S->getSCEVType() == scCouldNotCompute;
}
-
-// SCEVConstants - Only allow the creation of one SCEVConstant for any
-// particular value. Don't use a const SCEV* here, or else the object will
-// never be deleted!
-
const SCEV* ScalarEvolution::getConstant(ConstantInt *V) {
- SCEVConstant *&R = SCEVConstants[V];
- if (R == 0) R = new SCEVConstant(V);
- return R;
+ FoldingSetNodeID ID;
+ ID.AddInteger(scConstant);
+ ID.AddPointer(V);
+ void *IP = 0;
+ if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+ SCEV *S = SCEVAllocator.Allocate<SCEVConstant>();
+ new (S) SCEVConstant(V);
+ UniqueSCEVs.InsertNode(S, IP);
+ return S;
}
const SCEV* ScalarEvolution::getConstant(const APInt& Val) {
return getConstant(ConstantInt::get(cast<IntegerType>(Ty), V, isSigned));
}
+void SCEVConstant::Profile(FoldingSetNodeID &ID) const {
+ ID.AddInteger(scConstant);
+ ID.AddPointer(V);
+}
+
const Type *SCEVConstant::getType() const { return V->getType(); }
void SCEVConstant::print(raw_ostream &OS) const {
const SCEV* op, const Type *ty)
: SCEV(SCEVTy), Op(op), Ty(ty) {}
+void SCEVCastExpr::Profile(FoldingSetNodeID &ID) const {
+ ID.AddInteger(getSCEVType());
+ ID.AddPointer(Op);
+ ID.AddPointer(Ty);
+}
+
bool SCEVCastExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
return Op->dominates(BB, DT);
}
-// SCEVTruncates - Only allow the creation of one SCEVTruncateExpr for any
-// particular input. Don't use a const SCEV* here, or else the object will
-// never be deleted!
-
SCEVTruncateExpr::SCEVTruncateExpr(const SCEV* op, const Type *ty)
: SCEVCastExpr(scTruncate, op, ty) {
assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) &&
"Cannot truncate non-integer value!");
}
-
void SCEVTruncateExpr::print(raw_ostream &OS) const {
OS << "(trunc " << *Op->getType() << " " << *Op << " to " << *Ty << ")";
}
-// SCEVZeroExtends - Only allow the creation of one SCEVZeroExtendExpr for any
-// particular input. Don't use a const SCEV* here, or else the object will never
-// be deleted!
-
SCEVZeroExtendExpr::SCEVZeroExtendExpr(const SCEV* op, const Type *ty)
: SCEVCastExpr(scZeroExtend, op, ty) {
assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) &&
OS << "(zext " << *Op->getType() << " " << *Op << " to " << *Ty << ")";
}
-// SCEVSignExtends - Only allow the creation of one SCEVSignExtendExpr for any
-// particular input. Don't use a const SCEV* here, or else the object will never
-// be deleted!
-
SCEVSignExtendExpr::SCEVSignExtendExpr(const SCEV* op, const Type *ty)
: SCEVCastExpr(scSignExtend, op, ty) {
assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) &&
OS << "(sext " << *Op->getType() << " " << *Op << " to " << *Ty << ")";
}
-// SCEVCommExprs - Only allow the creation of one SCEVCommutativeExpr for any
-// particular input. Don't use a const SCEV* here, or else the object will never
-// be deleted!
-
void SCEVCommutativeExpr::print(raw_ostream &OS) const {
assert(Operands.size() > 1 && "This plus expr shouldn't exist!");
const char *OpStr = getOperationStr();
OS << ")";
}
-const SCEV* SCEVCommutativeExpr::
-replaceSymbolicValuesWithConcrete(const SCEV* Sym,
- const SCEV* Conc,
- ScalarEvolution &SE) const {
+const SCEV *
+SCEVCommutativeExpr::replaceSymbolicValuesWithConcrete(
+ const SCEV *Sym,
+ const SCEV *Conc,
+ ScalarEvolution &SE) const {
for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
const SCEV* H =
getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
return this;
}
+void SCEVNAryExpr::Profile(FoldingSetNodeID &ID) const {
+ ID.AddInteger(getSCEVType());
+ ID.AddInteger(Operands.size());
+ for (unsigned i = 0, e = Operands.size(); i != e; ++i)
+ ID.AddPointer(Operands[i]);
+}
+
bool SCEVNAryExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
if (!getOperand(i)->dominates(BB, DT))
return true;
}
-
-// SCEVUDivs - Only allow the creation of one SCEVUDivExpr for any particular
-// input. Don't use a const SCEV* here, or else the object will never be
-// deleted!
+void SCEVUDivExpr::Profile(FoldingSetNodeID &ID) const {
+ ID.AddInteger(scUDivExpr);
+ ID.AddPointer(LHS);
+ ID.AddPointer(RHS);
+}
bool SCEVUDivExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
return LHS->dominates(BB, DT) && RHS->dominates(BB, DT);
return RHS->getType();
}
-// SCEVAddRecExprs - Only allow the creation of one SCEVAddRecExpr for any
-// particular input. Don't use a const SCEV* here, or else the object will never
-// be deleted!
+void SCEVAddRecExpr::Profile(FoldingSetNodeID &ID) const {
+ ID.AddInteger(scAddRecExpr);
+ ID.AddInteger(Operands.size());
+ for (unsigned i = 0, e = Operands.size(); i != e; ++i)
+ ID.AddPointer(Operands[i]);
+ ID.AddPointer(L);
+}
-const SCEV* SCEVAddRecExpr::
-replaceSymbolicValuesWithConcrete(const SCEV* Sym,
- const SCEV* Conc,
- ScalarEvolution &SE) const {
+const SCEV *
+SCEVAddRecExpr::replaceSymbolicValuesWithConcrete(const SCEV *Sym,
+ const SCEV *Conc,
+ ScalarEvolution &SE) const {
for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
const SCEV* H =
getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
bool SCEVAddRecExpr::isLoopInvariant(const Loop *QueryLoop) const {
- // This recurrence is invariant w.r.t to QueryLoop iff QueryLoop doesn't
- // contain L and if the start is invariant.
// Add recurrences are never invariant in the function-body (null loop).
- return QueryLoop &&
- !QueryLoop->contains(L->getHeader()) &&
- getOperand(0)->isLoopInvariant(QueryLoop);
+ if (!QueryLoop)
+ return false;
+
+ // This recurrence is variant w.r.t. QueryLoop if QueryLoop contains L.
+ if (QueryLoop->contains(L->getHeader()))
+ return false;
+
+ // This recurrence is variant w.r.t. QueryLoop if any of its operands
+ // are variant.
+ for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
+ if (!getOperand(i)->isLoopInvariant(QueryLoop))
+ return false;
+
+ // Otherwise it's loop-invariant.
+ return true;
}
OS << "}<" << L->getHeader()->getName() + ">";
}
-// SCEVUnknowns - Only allow the creation of one SCEVUnknown for any particular
-// value. Don't use a const SCEV* here, or else the object will never be
-// deleted!
+void SCEVUnknown::Profile(FoldingSetNodeID &ID) const {
+ ID.AddInteger(scUnknown);
+ ID.AddPointer(V);
+}
bool SCEVUnknown::isLoopInvariant(const Loop *L) const {
// All non-instruction values are loop invariant. All instructions are loop
// safe in modular arithmetic.
//
// However, this code doesn't use exactly that formula; the formula it uses
- // is something like the following, where T is the number of factors of 2 in
+ // is something like the following, where T is the number of factors of 2 in
// K! (i.e. trailing zeros in the binary representation of K!), and ^ is
// exponentiation:
//
// arithmetic. To do exact division in modular arithmetic, all we have
// to do is multiply by the inverse. Therefore, this step can be done at
// width W.
- //
+ //
// The next issue is how to safely do the division by 2^T. The way this
// is done is by doing the multiplication step at a width of at least W + T
// bits. This way, the bottom W+T bits of the product are accurate. Then,
Ty = getEffectiveSCEVType(Ty);
if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
- return getUnknown(
- ConstantExpr::getTrunc(SC->getValue(), Ty));
+ return getConstant(
+ cast<ConstantInt>(ConstantExpr::getTrunc(SC->getValue(), Ty)));
// trunc(trunc(x)) --> trunc(x)
if (const SCEVTruncateExpr *ST = dyn_cast<SCEVTruncateExpr>(Op))
return getAddRecExpr(Operands, AddRec->getLoop());
}
- SCEVTruncateExpr *&Result = SCEVTruncates[std::make_pair(Op, Ty)];
- if (Result == 0) Result = new SCEVTruncateExpr(Op, Ty);
- return Result;
+ FoldingSetNodeID ID;
+ ID.AddInteger(scTruncate);
+ ID.AddPointer(Op);
+ ID.AddPointer(Ty);
+ void *IP = 0;
+ if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+ SCEV *S = SCEVAllocator.Allocate<SCEVTruncateExpr>();
+ new (S) SCEVTruncateExpr(Op, Ty);
+ UniqueSCEVs.InsertNode(S, IP);
+ return S;
}
const SCEV* ScalarEvolution::getZeroExtendExpr(const SCEV* Op,
const Type *IntTy = getEffectiveSCEVType(Ty);
Constant *C = ConstantExpr::getZExt(SC->getValue(), IntTy);
if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty);
- return getUnknown(C);
+ return getConstant(cast<ConstantInt>(C));
}
// zext(zext(x)) --> zext(x)
}
}
- SCEVZeroExtendExpr *&Result = SCEVZeroExtends[std::make_pair(Op, Ty)];
- if (Result == 0) Result = new SCEVZeroExtendExpr(Op, Ty);
- return Result;
+ FoldingSetNodeID ID;
+ ID.AddInteger(scZeroExtend);
+ ID.AddPointer(Op);
+ ID.AddPointer(Ty);
+ void *IP = 0;
+ if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+ SCEV *S = SCEVAllocator.Allocate<SCEVZeroExtendExpr>();
+ new (S) SCEVZeroExtendExpr(Op, Ty);
+ UniqueSCEVs.InsertNode(S, IP);
+ return S;
}
const SCEV* ScalarEvolution::getSignExtendExpr(const SCEV* Op,
const Type *IntTy = getEffectiveSCEVType(Ty);
Constant *C = ConstantExpr::getSExt(SC->getValue(), IntTy);
if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty);
- return getUnknown(C);
+ return getConstant(cast<ConstantInt>(C));
}
// sext(sext(x)) --> sext(x)
}
}
- SCEVSignExtendExpr *&Result = SCEVSignExtends[std::make_pair(Op, Ty)];
- if (Result == 0) Result = new SCEVSignExtendExpr(Op, Ty);
- return Result;
+ FoldingSetNodeID ID;
+ ID.AddInteger(scSignExtend);
+ ID.AddPointer(Op);
+ ID.AddPointer(Ty);
+ void *IP = 0;
+ if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+ SCEV *S = SCEVAllocator.Allocate<SCEVSignExtendExpr>();
+ new (S) SCEVSignExtendExpr(Op, Ty);
+ UniqueSCEVs.InsertNode(S, IP);
+ return S;
}
/// getAnyExtendExpr - Return a SCEV for the given operand extended with
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()));
+ M.insert(std::make_pair(Key, NewScale));
if (Pair.second) {
- Pair.first->second = NewScale;
NewOps.push_back(Pair.first->first);
} else {
Pair.first->second += NewScale;
} else {
// An ordinary operand. Update the map.
std::pair<DenseMap<const SCEV*, APInt>::iterator, bool> Pair =
- M.insert(std::make_pair(Ops[i], APInt()));
+ M.insert(std::make_pair(Ops[i], Scale));
if (Pair.second) {
- Pair.first->second = Scale;
NewOps.push_back(Pair.first->first);
} else {
Pair.first->second += Scale;
Ops.clear();
if (AccumulatedConstant != 0)
Ops.push_back(getConstant(AccumulatedConstant));
- for (std::map<APInt, SmallVector<const SCEV*, 4>, APIntCompare>::iterator I =
- MulOpLists.begin(), E = MulOpLists.end(); I != E; ++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)));
+ Ops.push_back(getMulExpr(getConstant(I->first),
+ getAddExpr(I->second)));
if (Ops.empty())
return getIntegerSCEV(0, Ty);
if (Ops.size() == 1)
// Fold X + (A*B*C) + (A*D*E) --> X + (A*(B*C+D*E))
const SCEV* InnerMul1 = Mul->getOperand(MulOp == 0);
if (Mul->getNumOperands() != 2) {
- SmallVector<const SCEV*, 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);
}
const SCEV* InnerMul2 = OtherMul->getOperand(OMulOp == 0);
if (OtherMul->getNumOperands() != 2) {
- SmallVector<const SCEV*, 4> MulOps(OtherMul->op_begin(),
- OtherMul->op_end());
+ SmallVector<const SCEV *, 4> MulOps(OtherMul->op_begin(),
+ OtherMul->op_end());
MulOps.erase(MulOps.begin()+OMulOp);
InnerMul2 = getMulExpr(MulOps);
}
const SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
if (AddRec->getLoop() == OtherAddRec->getLoop()) {
// Other + {A,+,B} + {C,+,D} --> Other + {A+C,+,B+D}
- SmallVector<const SCEV*, 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,
// Okay, it looks like we really DO need an add expr. Check to see if we
// already have one, otherwise create a new one.
- std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
- SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scAddExpr,
- SCEVOps)];
- if (Result == 0) Result = new SCEVAddExpr(Ops);
- return Result;
+ FoldingSetNodeID ID;
+ ID.AddInteger(scAddExpr);
+ ID.AddInteger(Ops.size());
+ for (unsigned i = 0, e = Ops.size(); i != e; ++i)
+ ID.AddPointer(Ops[i]);
+ void *IP = 0;
+ if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+ SCEV *S = SCEVAllocator.Allocate<SCEVAddExpr>();
+ new (S) SCEVAddExpr(Ops);
+ UniqueSCEVs.InsertNode(S, IP);
+ return S;
}
++Idx;
while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
// We found two constants, fold them together!
- ConstantInt *Fold = ConstantInt::get(LHSC->getValue()->getValue() *
+ ConstantInt *Fold = ConstantInt::get(LHSC->getValue()->getValue() *
RHSC->getValue()->getValue());
Ops[0] = getConstant(Fold);
Ops.erase(Ops.begin()+1); // Erase the folded element
// Okay, it looks like we really DO need an mul expr. Check to see if we
// already have one, otherwise create a new one.
- std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
- SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scMulExpr,
- SCEVOps)];
- if (Result == 0)
- Result = new SCEVMulExpr(Ops);
- return Result;
+ FoldingSetNodeID ID;
+ ID.AddInteger(scMulExpr);
+ ID.AddInteger(Ops.size());
+ for (unsigned i = 0, e = Ops.size(); i != e; ++i)
+ ID.AddPointer(Ops[i]);
+ void *IP = 0;
+ if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+ SCEV *S = SCEVAllocator.Allocate<SCEVMulExpr>();
+ new (S) SCEVMulExpr(Ops);
+ UniqueSCEVs.InsertNode(S, IP);
+ return S;
}
/// getUDivExpr - Get a canonical multiply expression, or something simpler if
/// possible.
-const SCEV* ScalarEvolution::getUDivExpr(const SCEV* LHS,
- const SCEV* RHS) {
+const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS,
+ const SCEV *RHS) {
assert(getEffectiveSCEVType(LHS->getType()) ==
getEffectiveSCEVType(RHS->getType()) &&
"SCEVUDivExpr operand types don't match!");
if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
Constant *LHSCV = LHSC->getValue();
Constant *RHSCV = RHSC->getValue();
- return getUnknown(ConstantExpr::getUDiv(LHSCV, RHSCV));
+ return getConstant(cast<ConstantInt>(ConstantExpr::getUDiv(LHSCV,
+ RHSCV)));
}
}
- SCEVUDivExpr *&Result = SCEVUDivs[std::make_pair(LHS, RHS)];
- if (Result == 0) Result = new SCEVUDivExpr(LHS, RHS);
- return Result;
+ FoldingSetNodeID ID;
+ ID.AddInteger(scUDivExpr);
+ ID.AddPointer(LHS);
+ ID.AddPointer(RHS);
+ void *IP = 0;
+ if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+ SCEV *S = SCEVAllocator.Allocate<SCEVUDivExpr>();
+ new (S) SCEVUDivExpr(LHS, RHS);
+ UniqueSCEVs.InsertNode(S, IP);
+ return S;
}
/// getAddRecExpr - Get an add recurrence expression for the specified loop.
/// Simplify the expression as much as possible.
-const SCEV* ScalarEvolution::getAddRecExpr(SmallVectorImpl<const SCEV*> &Operands,
- const Loop *L) {
+const SCEV *
+ScalarEvolution::getAddRecExpr(SmallVectorImpl<const SCEV*> &Operands,
+ const Loop *L) {
if (Operands.size() == 1) return Operands[0];
#ifndef NDEBUG
for (unsigned i = 1, e = Operands.size(); i != e; ++i)
SmallVector<const SCEV*, 4> NestedOperands(NestedAR->op_begin(),
NestedAR->op_end());
Operands[0] = NestedAR->getStart();
- NestedOperands[0] = getAddRecExpr(Operands, L);
- return getAddRecExpr(NestedOperands, NestedLoop);
+ // AddRecs require their operands be loop-invariant with respect to their
+ // loops. Don't perform this transformation if it would break this
+ // requirement.
+ bool AllInvariant = true;
+ for (unsigned i = 0, e = Operands.size(); i != e; ++i)
+ if (!Operands[i]->isLoopInvariant(L)) {
+ AllInvariant = false;
+ break;
+ }
+ if (AllInvariant) {
+ NestedOperands[0] = getAddRecExpr(Operands, L);
+ AllInvariant = true;
+ for (unsigned i = 0, e = NestedOperands.size(); i != e; ++i)
+ if (!NestedOperands[i]->isLoopInvariant(NestedLoop)) {
+ AllInvariant = false;
+ break;
+ }
+ if (AllInvariant)
+ // Ok, both add recurrences are valid after the transformation.
+ return getAddRecExpr(NestedOperands, NestedLoop);
+ }
+ // Reset Operands to its original state.
+ Operands[0] = NestedAR;
}
}
- std::vector<const SCEV*> SCEVOps(Operands.begin(), Operands.end());
- SCEVAddRecExpr *&Result = SCEVAddRecExprs[std::make_pair(L, SCEVOps)];
- if (Result == 0) Result = new SCEVAddRecExpr(Operands, L);
- return Result;
+ FoldingSetNodeID ID;
+ ID.AddInteger(scAddRecExpr);
+ ID.AddInteger(Operands.size());
+ for (unsigned i = 0, e = Operands.size(); i != e; ++i)
+ ID.AddPointer(Operands[i]);
+ ID.AddPointer(L);
+ void *IP = 0;
+ if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+ SCEV *S = SCEVAllocator.Allocate<SCEVAddRecExpr>();
+ new (S) SCEVAddRecExpr(Operands, L);
+ UniqueSCEVs.InsertNode(S, IP);
+ return S;
}
-const SCEV* ScalarEvolution::getSMaxExpr(const SCEV* LHS,
- const SCEV* RHS) {
+const SCEV *ScalarEvolution::getSMaxExpr(const SCEV *LHS,
+ const SCEV *RHS) {
SmallVector<const SCEV*, 2> Ops;
Ops.push_back(LHS);
Ops.push_back(RHS);
LHSC = cast<SCEVConstant>(Ops[0]);
}
- // If we are left with a constant -inf, strip it off.
+ // If we are left with a constant minimum-int, strip it off.
if (cast<SCEVConstant>(Ops[0])->getValue()->isMinValue(true)) {
Ops.erase(Ops.begin());
--Idx;
+ } else if (cast<SCEVConstant>(Ops[0])->getValue()->isMaxValue(true)) {
+ // If we have an smax with a constant maximum-int, it will always be
+ // maximum-int.
+ return Ops[0];
}
}
// Okay, it looks like we really DO need an smax expr. Check to see if we
// already have one, otherwise create a new one.
- std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
- SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scSMaxExpr,
- SCEVOps)];
- if (Result == 0) Result = new SCEVSMaxExpr(Ops);
- return Result;
+ FoldingSetNodeID ID;
+ ID.AddInteger(scSMaxExpr);
+ ID.AddInteger(Ops.size());
+ for (unsigned i = 0, e = Ops.size(); i != e; ++i)
+ ID.AddPointer(Ops[i]);
+ void *IP = 0;
+ if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+ SCEV *S = SCEVAllocator.Allocate<SCEVSMaxExpr>();
+ new (S) SCEVSMaxExpr(Ops);
+ UniqueSCEVs.InsertNode(S, IP);
+ return S;
}
-const SCEV* ScalarEvolution::getUMaxExpr(const SCEV* LHS,
- const SCEV* RHS) {
+const SCEV *ScalarEvolution::getUMaxExpr(const SCEV *LHS,
+ const SCEV *RHS) {
SmallVector<const SCEV*, 2> Ops;
Ops.push_back(LHS);
Ops.push_back(RHS);
LHSC = cast<SCEVConstant>(Ops[0]);
}
- // If we are left with a constant zero, strip it off.
+ // If we are left with a constant minimum-int, strip it off.
if (cast<SCEVConstant>(Ops[0])->getValue()->isMinValue(false)) {
Ops.erase(Ops.begin());
--Idx;
+ } else if (cast<SCEVConstant>(Ops[0])->getValue()->isMaxValue(false)) {
+ // If we have an umax with a constant maximum-int, it will always be
+ // maximum-int.
+ return Ops[0];
}
}
// Okay, it looks like we really DO need a umax expr. Check to see if we
// already have one, otherwise create a new one.
- std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
- SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scUMaxExpr,
- SCEVOps)];
- if (Result == 0) Result = new SCEVUMaxExpr(Ops);
- return Result;
+ FoldingSetNodeID ID;
+ ID.AddInteger(scUMaxExpr);
+ ID.AddInteger(Ops.size());
+ for (unsigned i = 0, e = Ops.size(); i != e; ++i)
+ ID.AddPointer(Ops[i]);
+ void *IP = 0;
+ if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+ SCEV *S = SCEVAllocator.Allocate<SCEVUMaxExpr>();
+ new (S) SCEVUMaxExpr(Ops);
+ UniqueSCEVs.InsertNode(S, IP);
+ return S;
}
-const SCEV* ScalarEvolution::getSMinExpr(const SCEV* LHS,
- const SCEV* RHS) {
+const SCEV *ScalarEvolution::getSMinExpr(const SCEV *LHS,
+ const SCEV *RHS) {
// ~smax(~x, ~y) == smin(x, y).
return getNotSCEV(getSMaxExpr(getNotSCEV(LHS), getNotSCEV(RHS)));
}
-const SCEV* ScalarEvolution::getUMinExpr(const SCEV* LHS,
- const SCEV* RHS) {
+const SCEV *ScalarEvolution::getUMinExpr(const SCEV *LHS,
+ const SCEV *RHS) {
// ~umax(~x, ~y) == umin(x, y)
return getNotSCEV(getUMaxExpr(getNotSCEV(LHS), getNotSCEV(RHS)));
}
const SCEV* ScalarEvolution::getUnknown(Value *V) {
- if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
- return getConstant(CI);
- if (isa<ConstantPointerNull>(V))
- return getIntegerSCEV(0, V->getType());
- SCEVUnknown *&Result = SCEVUnknowns[V];
- if (Result == 0) Result = new SCEVUnknown(V);
- return Result;
+ // Don't attempt to do anything other than create a SCEVUnknown object
+ // here. createSCEV only calls getUnknown after checking for all other
+ // interesting possibilities, and any other code that calls getUnknown
+ // is doing so in order to hide a value from SCEV canonicalization.
+
+ FoldingSetNodeID ID;
+ ID.AddInteger(scUnknown);
+ ID.AddPointer(V);
+ void *IP = 0;
+ if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+ SCEV *S = SCEVAllocator.Allocate<SCEVUnknown>();
+ new (S) SCEVUnknown(V);
+ UniqueSCEVs.InsertNode(S, IP);
+ return S;
}
//===----------------------------------------------------------------------===//
}
const SCEV* ScalarEvolution::getCouldNotCompute() {
- return CouldNotCompute;
+ return &CouldNotCompute;
}
/// hasSCEV - Return true if the SCEV for this value has already been
return S;
}
-/// getIntegerSCEV - Given an integer or FP type, create a constant for the
+/// getIntegerSCEV - Given a SCEVable type, create a constant for the
/// specified signed integer value and return a SCEV for the constant.
const SCEV* ScalarEvolution::getIntegerSCEV(int Val, const Type *Ty) {
- Ty = getEffectiveSCEVType(Ty);
- Constant *C;
- if (Val == 0)
- C = Constant::getNullValue(Ty);
- else if (Ty->isFloatingPoint())
- C = ConstantFP::get(APFloat(Ty==Type::FloatTy ? APFloat::IEEEsingle :
- APFloat::IEEEdouble, Val));
- else
- C = ConstantInt::get(Ty, Val);
- return getUnknown(C);
+ const IntegerType *ITy = cast<IntegerType>(getEffectiveSCEVType(Ty));
+ return getConstant(ConstantInt::get(ITy, Val));
}
/// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V
///
const SCEV* ScalarEvolution::getNegativeSCEV(const SCEV* V) {
if (const SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
- return getUnknown(ConstantExpr::getNeg(VC->getValue()));
+ return getConstant(cast<ConstantInt>(ConstantExpr::getNeg(VC->getValue())));
const Type *Ty = V->getType();
Ty = getEffectiveSCEVType(Ty);
/// getNotSCEV - Return a SCEV corresponding to ~V = -1-V
const SCEV* ScalarEvolution::getNotSCEV(const SCEV* V) {
if (const SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
- return getUnknown(ConstantExpr::getNot(VC->getValue()));
+ return getConstant(cast<ConstantInt>(ConstantExpr::getNot(VC->getValue())));
const Type *Ty = V->getType();
Ty = getEffectiveSCEVType(Ty);
/// getMinusSCEV - Return a SCEV corresponding to LHS - RHS.
///
-const SCEV* ScalarEvolution::getMinusSCEV(const SCEV* LHS,
- const SCEV* RHS) {
+const SCEV *ScalarEvolution::getMinusSCEV(const SCEV *LHS,
+ const SCEV *RHS) {
// X - Y --> X + -Y
return getAddExpr(LHS, getNegativeSCEV(RHS));
}
/// getUMaxFromMismatchedTypes - Promote the operands to the wider of
/// the types using zero-extension, and then perform a umax operation
/// with them.
-const SCEV* ScalarEvolution::getUMaxFromMismatchedTypes(const SCEV* LHS,
- const SCEV* RHS) {
+const SCEV *ScalarEvolution::getUMaxFromMismatchedTypes(const SCEV *LHS,
+ const SCEV *RHS) {
const SCEV* PromotedLHS = LHS;
const SCEV* PromotedRHS = RHS;
/// getUMinFromMismatchedTypes - Promote the operands to the wider of
/// the types using zero-extension, and then perform a umin operation
/// with them.
-const SCEV* ScalarEvolution::getUMinFromMismatchedTypes(const SCEV* LHS,
- const SCEV* RHS) {
+const SCEV *ScalarEvolution::getUMinFromMismatchedTypes(const SCEV *LHS,
+ const SCEV *RHS) {
const SCEV* PromotedLHS = LHS;
const SCEV* PromotedRHS = RHS;
/// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value for
/// the specified instruction and replaces any references to the symbolic value
/// SymName with the specified value. This is used during PHI resolution.
-void ScalarEvolution::
-ReplaceSymbolicValueWithConcrete(Instruction *I, const SCEV* SymName,
- const SCEV* NewVal) {
+void
+ScalarEvolution::ReplaceSymbolicValueWithConcrete(Instruction *I,
+ const SCEV *SymName,
+ const SCEV *NewVal) {
std::map<SCEVCallbackVH, const SCEV*>::iterator SI =
Scalars.find(SCEVCallbackVH(I, this));
if (SI == Scalars.end()) return;
if (Accum->isLoopInvariant(L) ||
(isa<SCEVAddRecExpr>(Accum) &&
cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) {
- const SCEV* StartVal = getSCEV(PN->getIncomingValue(IncomingEdge));
- const SCEV* PHISCEV = getAddRecExpr(StartVal, Accum, L);
+ const SCEV *StartVal =
+ getSCEV(PN->getIncomingValue(IncomingEdge));
+ const SCEV *PHISCEV =
+ getAddRecExpr(StartVal, Accum, L);
// Okay, for the entire analysis of this edge we assumed the PHI
// to be symbolic. We now need to go back and update all of the
// initial step of the addrec evolution.
if (StartVal == getMinusSCEV(AddRec->getOperand(0),
AddRec->getOperand(1))) {
- const SCEV* PHISCEV =
+ const SCEV* PHISCEV =
getAddRecExpr(StartVal, AddRec->getOperand(1), L);
// Okay, for the entire analysis of this edge we assumed the PHI
getTypeSizeInBits(C->getOperand()->getType()));
}
+ if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
+ unsigned BitWidth = getTypeSizeInBits(A->getType());
+
+ // Special case decrementing a value (ADD X, -1):
+ if (const SCEVConstant *CRHS = dyn_cast<SCEVConstant>(A->getOperand(0)))
+ if (CRHS->isAllOnesValue()) {
+ SmallVector<const SCEV *, 4> OtherOps(A->op_begin() + 1, A->op_end());
+ const SCEV *OtherOpsAdd = getAddExpr(OtherOps);
+ unsigned LZ = GetMinLeadingZeros(OtherOpsAdd);
+
+ // If the input is known to be 0 or 1, the output is 0/-1, which is all
+ // sign bits set.
+ if (LZ == BitWidth - 1)
+ return BitWidth;
+
+ // If we are subtracting one from a positive number, there is no carry
+ // out of the result.
+ if (LZ > 0)
+ return GetMinSignBits(OtherOpsAdd);
+ }
+
+ // Add can have at most one carry bit. Thus we know that the output
+ // is, at worst, one more bit than the inputs.
+ unsigned Min = BitWidth;
+ for (unsigned i = 0, e = A->getNumOperands(); i != e; ++i) {
+ unsigned N = GetMinSignBits(A->getOperand(i));
+ Min = std::min(Min, N) - 1;
+ if (Min == 0) return 1;
+ }
+ return 1;
+ }
+
if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
// For a SCEVUnknown, ask ValueTracking.
return ComputeNumSignBits(U->getValue(), TD);
Opcode = I->getOpcode();
else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
Opcode = CE->getOpcode();
+ else if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
+ return getConstant(CI);
+ else if (isa<ConstantPointerNull>(V))
+ return getIntegerSCEV(0, V->getType());
+ else if (isa<UndefValue>(V))
+ return getIntegerSCEV(0, V->getType());
else
return getUnknown(V);
BackedgeTakenCounts.insert(std::make_pair(L, getCouldNotCompute()));
if (Pair.second) {
BackedgeTakenInfo ItCount = ComputeBackedgeTakenCount(L);
- if (ItCount.Exact != CouldNotCompute) {
+ if (ItCount.Exact != getCouldNotCompute()) {
assert(ItCount.Exact->isLoopInvariant(L) &&
ItCount.Max->isLoopInvariant(L) &&
"Computed trip count isn't loop invariant for loop!");
// Update the value in the map.
Pair.first->second = ItCount;
} else {
- if (ItCount.Max != CouldNotCompute)
+ if (ItCount.Max != getCouldNotCompute())
// Update the value in the map.
Pair.first->second = ItCount;
if (isa<PHINode>(L->getHeader()->begin()))
SmallVector<Instruction *, 16> Worklist;
for (BasicBlock::iterator I = Header->begin();
PHINode *PN = dyn_cast<PHINode>(I); ++I) {
- std::map<SCEVCallbackVH, const SCEV*>::iterator It = Scalars.find((Value*)I);
+ std::map<SCEVCallbackVH, const SCEV*>::iterator It =
+ Scalars.find((Value*)I);
if (It != Scalars.end() && !isa<SCEVUnknown>(It->second))
Worklist.push_back(PN);
}
L->getExitingBlocks(ExitingBlocks);
// Examine all exits and pick the most conservative values.
- const SCEV* BECount = CouldNotCompute;
- const SCEV* MaxBECount = CouldNotCompute;
+ const SCEV* BECount = getCouldNotCompute();
+ const SCEV* MaxBECount = getCouldNotCompute();
bool CouldNotComputeBECount = false;
- bool CouldNotComputeMaxBECount = false;
for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
BackedgeTakenInfo NewBTI =
ComputeBackedgeTakenCountFromExit(L, ExitingBlocks[i]);
- if (NewBTI.Exact == CouldNotCompute) {
+ if (NewBTI.Exact == getCouldNotCompute()) {
// We couldn't compute an exact value for this exit, so
// we won't be able to compute an exact value for the loop.
CouldNotComputeBECount = true;
- BECount = CouldNotCompute;
+ BECount = getCouldNotCompute();
} else if (!CouldNotComputeBECount) {
- if (BECount == CouldNotCompute)
+ if (BECount == getCouldNotCompute())
BECount = NewBTI.Exact;
- else {
- // TODO: More analysis could be done here. For example, a
- // loop with a short-circuiting && operator has an exact count
- // of the min of both sides.
- CouldNotComputeBECount = true;
- BECount = CouldNotCompute;
- }
- }
- if (NewBTI.Max == CouldNotCompute) {
- // We couldn't compute an maximum value for this exit, so
- // we won't be able to compute an maximum value for the loop.
- CouldNotComputeMaxBECount = true;
- MaxBECount = CouldNotCompute;
- } else if (!CouldNotComputeMaxBECount) {
- if (MaxBECount == CouldNotCompute)
- MaxBECount = NewBTI.Max;
else
- MaxBECount = getUMaxFromMismatchedTypes(MaxBECount, NewBTI.Max);
+ BECount = getUMinFromMismatchedTypes(BECount, NewBTI.Exact);
}
+ if (MaxBECount == getCouldNotCompute())
+ MaxBECount = NewBTI.Max;
+ else if (NewBTI.Max != getCouldNotCompute())
+ MaxBECount = getUMinFromMismatchedTypes(MaxBECount, NewBTI.Max);
}
return BackedgeTakenInfo(BECount, MaxBECount);
//
// FIXME: we should be able to handle switch instructions (with a single exit)
BranchInst *ExitBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
- if (ExitBr == 0) return CouldNotCompute;
+ if (ExitBr == 0) return getCouldNotCompute();
assert(ExitBr->isConditional() && "If unconditional, it can't be in loop!");
-
+
// At this point, we know we have a conditional branch that determines whether
// the loop is exited. However, we don't know if the branch is executed each
// time through the loop. If not, then the execution count of the branch will
for (BasicBlock *BB = ExitBr->getParent(); BB; ) {
BasicBlock *Pred = BB->getUniquePredecessor();
if (!Pred)
- return CouldNotCompute;
+ return getCouldNotCompute();
TerminatorInst *PredTerm = Pred->getTerminator();
for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i) {
BasicBlock *PredSucc = PredTerm->getSuccessor(i);
// If the predecessor has a successor that isn't BB and isn't
// outside the loop, assume the worst.
if (L->contains(PredSucc))
- return CouldNotCompute;
+ return getCouldNotCompute();
}
if (Pred == L->getHeader()) {
Ok = true;
BB = Pred;
}
if (!Ok)
- return CouldNotCompute;
+ return getCouldNotCompute();
}
// Procede to the next level to examine the exit condition expression.
Value *ExitCond,
BasicBlock *TBB,
BasicBlock *FBB) {
- // Check if the controlling expression for this loop is an and or or. In
- // such cases, an exact backedge-taken count may be infeasible, but a
- // maximum count may still be feasible.
+ // Check if the controlling expression for this loop is an And or Or.
if (BinaryOperator *BO = dyn_cast<BinaryOperator>(ExitCond)) {
if (BO->getOpcode() == Instruction::And) {
// Recurse on the operands of the and.
ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(0), TBB, FBB);
BackedgeTakenInfo BTI1 =
ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(1), TBB, FBB);
- const SCEV* BECount = CouldNotCompute;
- const SCEV* MaxBECount = CouldNotCompute;
+ const SCEV* BECount = getCouldNotCompute();
+ const SCEV* MaxBECount = getCouldNotCompute();
if (L->contains(TBB)) {
// Both conditions must be true for the loop to continue executing.
// Choose the less conservative count.
- if (BTI0.Exact == CouldNotCompute || BTI1.Exact == CouldNotCompute)
- BECount = CouldNotCompute;
+ if (BTI0.Exact == getCouldNotCompute() ||
+ BTI1.Exact == getCouldNotCompute())
+ BECount = getCouldNotCompute();
else
BECount = getUMinFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
- if (BTI0.Max == CouldNotCompute)
+ if (BTI0.Max == getCouldNotCompute())
MaxBECount = BTI1.Max;
- else if (BTI1.Max == CouldNotCompute)
+ else if (BTI1.Max == getCouldNotCompute())
MaxBECount = BTI0.Max;
else
MaxBECount = getUMinFromMismatchedTypes(BTI0.Max, BTI1.Max);
} else {
// Both conditions must be true for the loop to exit.
assert(L->contains(FBB) && "Loop block has no successor in loop!");
- if (BTI0.Exact != CouldNotCompute && BTI1.Exact != CouldNotCompute)
+ if (BTI0.Exact != getCouldNotCompute() &&
+ BTI1.Exact != getCouldNotCompute())
BECount = getUMaxFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
- if (BTI0.Max != CouldNotCompute && BTI1.Max != CouldNotCompute)
+ if (BTI0.Max != getCouldNotCompute() &&
+ BTI1.Max != getCouldNotCompute())
MaxBECount = getUMaxFromMismatchedTypes(BTI0.Max, BTI1.Max);
}
ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(0), TBB, FBB);
BackedgeTakenInfo BTI1 =
ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(1), TBB, FBB);
- const SCEV* BECount = CouldNotCompute;
- const SCEV* MaxBECount = CouldNotCompute;
+ const SCEV* BECount = getCouldNotCompute();
+ const SCEV* MaxBECount = getCouldNotCompute();
if (L->contains(FBB)) {
// Both conditions must be false for the loop to continue executing.
// Choose the less conservative count.
- if (BTI0.Exact == CouldNotCompute || BTI1.Exact == CouldNotCompute)
- BECount = CouldNotCompute;
+ if (BTI0.Exact == getCouldNotCompute() ||
+ BTI1.Exact == getCouldNotCompute())
+ BECount = getCouldNotCompute();
else
BECount = getUMinFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
- if (BTI0.Max == CouldNotCompute)
+ if (BTI0.Max == getCouldNotCompute())
MaxBECount = BTI1.Max;
- else if (BTI1.Max == CouldNotCompute)
+ else if (BTI1.Max == getCouldNotCompute())
MaxBECount = BTI0.Max;
else
MaxBECount = getUMinFromMismatchedTypes(BTI0.Max, BTI1.Max);
} else {
// Both conditions must be false for the loop to exit.
assert(L->contains(TBB) && "Loop block has no successor in loop!");
- if (BTI0.Exact != CouldNotCompute && BTI1.Exact != CouldNotCompute)
+ if (BTI0.Exact != getCouldNotCompute() &&
+ BTI1.Exact != getCouldNotCompute())
BECount = getUMaxFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
- if (BTI0.Max != CouldNotCompute && BTI1.Max != CouldNotCompute)
+ if (BTI0.Max != getCouldNotCompute() &&
+ BTI1.Max != getCouldNotCompute())
MaxBECount = getUMaxFromMismatchedTypes(BTI0.Max, BTI1.Max);
}
LHS = getSCEVAtScope(LHS, L);
RHS = getSCEVAtScope(RHS, L);
- // At this point, we would like to compute how many iterations of the
+ // At this point, we would like to compute how many iterations of the
// loop the predicate will return true for these inputs.
if (LHS->isLoopInvariant(L) && !RHS->isLoopInvariant(L)) {
// If there is a loop-invariant, force it into the RHS.
if (ExitCond->getOperand(0)->getType()->isUnsigned())
errs() << "[unsigned] ";
errs() << *LHS << " "
- << Instruction::getOpcodeName(Instruction::ICmp)
+ << Instruction::getOpcodeName(Instruction::ICmp)
<< " " << *RHS << "\n";
#endif
break;
/// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition of
/// 'icmp op load X, cst', try to see if we can compute the backedge
/// execution count.
-const SCEV* ScalarEvolution::
-ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI, Constant *RHS,
- const Loop *L,
- ICmpInst::Predicate predicate) {
- if (LI->isVolatile()) return CouldNotCompute;
+const SCEV *
+ScalarEvolution::ComputeLoadConstantCompareBackedgeTakenCount(
+ LoadInst *LI,
+ Constant *RHS,
+ const Loop *L,
+ ICmpInst::Predicate predicate) {
+ if (LI->isVolatile()) return getCouldNotCompute();
// Check to see if the loaded pointer is a getelementptr of a global.
GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(LI->getOperand(0));
- if (!GEP) return CouldNotCompute;
+ if (!GEP) return getCouldNotCompute();
// Make sure that it is really a constant global we are gepping, with an
// initializer, and make sure the first IDX is really 0.
if (!GV || !GV->isConstant() || !GV->hasInitializer() ||
GEP->getNumOperands() < 3 || !isa<Constant>(GEP->getOperand(1)) ||
!cast<Constant>(GEP->getOperand(1))->isNullValue())
- return CouldNotCompute;
+ return getCouldNotCompute();
// Okay, we allow one non-constant index into the GEP instruction.
Value *VarIdx = 0;
if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i))) {
Indexes.push_back(CI);
} else if (!isa<ConstantInt>(GEP->getOperand(i))) {
- if (VarIdx) return CouldNotCompute; // Multiple non-constant idx's.
+ if (VarIdx) return getCouldNotCompute(); // Multiple non-constant idx's.
VarIdx = GEP->getOperand(i);
VarIdxNum = i-2;
Indexes.push_back(0);
if (!IdxExpr || !IdxExpr->isAffine() || IdxExpr->isLoopInvariant(L) ||
!isa<SCEVConstant>(IdxExpr->getOperand(0)) ||
!isa<SCEVConstant>(IdxExpr->getOperand(1)))
- return CouldNotCompute;
+ return getCouldNotCompute();
unsigned MaxSteps = MaxBruteForceIterations;
for (unsigned IterationNum = 0; IterationNum != MaxSteps; ++IterationNum) {
return getConstant(ItCst); // Found terminating iteration!
}
}
- return CouldNotCompute;
+ return getCouldNotCompute();
}
/// 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 *ScalarEvolution::
-getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs, const Loop *L){
+Constant *
+ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
+ const APInt& BEs,
+ const Loop *L) {
std::map<PHINode*, Constant*>::iterator I =
ConstantEvolutionLoopExitValue.find(PN);
if (I != ConstantEvolutionLoopExitValue.end())
/// 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 CouldNotCompute.
-const SCEV* ScalarEvolution::
-ComputeBackedgeTakenCountExhaustively(const Loop *L, Value *Cond, bool ExitWhen) {
+/// evaluate the trip count of the loop, return getCouldNotCompute().
+const SCEV *
+ScalarEvolution::ComputeBackedgeTakenCountExhaustively(const Loop *L,
+ Value *Cond,
+ bool ExitWhen) {
PHINode *PN = getConstantEvolvingPHI(Cond, L);
- if (PN == 0) return CouldNotCompute;
+ if (PN == 0) return getCouldNotCompute();
// Since the loop is canonicalized, the PHI node must have two entries. One
// entry must be a constant (coming in from outside of the loop), and the
bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
Constant *StartCST =
dyn_cast<Constant>(PN->getIncomingValue(!SecondIsBackedge));
- if (StartCST == 0) return CouldNotCompute; // Must be a constant.
+ if (StartCST == 0) return getCouldNotCompute(); // Must be a constant.
Value *BEValue = PN->getIncomingValue(SecondIsBackedge);
PHINode *PN2 = getConstantEvolvingPHI(BEValue, L);
- if (PN2 != PN) return CouldNotCompute; // Not derived from same PHI.
+ if (PN2 != PN) return getCouldNotCompute(); // Not derived from same PHI.
// Okay, we find a PHI node that defines the trip count of this loop. Execute
// the loop symbolically to determine when the condition gets a value of
dyn_cast_or_null<ConstantInt>(EvaluateExpression(Cond, PHIVal));
// Couldn't symbolically evaluate.
- if (!CondVal) return CouldNotCompute;
+ if (!CondVal) return getCouldNotCompute();
if (CondVal->getValue() == uint64_t(ExitWhen)) {
- ConstantEvolutionLoopExitValue[PN] = PHIVal;
++NumBruteForceTripCountsComputed;
return getConstant(Type::Int32Ty, IterationNum);
}
// Compute the value of the PHI node for the next iteration.
Constant *NextPHI = EvaluateExpression(BEValue, PHIVal);
if (NextPHI == 0 || NextPHI == PHIVal)
- return CouldNotCompute; // Couldn't evaluate or not making progress...
+ return getCouldNotCompute();// Couldn't evaluate or not making progress...
PHIVal = NextPHI;
}
// Too many iterations were needed to evaluate.
- return CouldNotCompute;
+ return getCouldNotCompute();
}
/// getSCEVAtScope - Return a SCEV expression handle for the specified value
Constant *RV = getConstantEvolutionLoopExitValue(PN,
BTCC->getValue()->getValue(),
LI);
- if (RV) return getUnknown(RV);
+ if (RV) return getSCEV(RV);
}
}
std::pair<std::map<const Loop *, Constant *>::iterator, bool> Pair =
Values.insert(std::make_pair(L, static_cast<Constant *>(0)));
if (!Pair.second)
- return Pair.first->second ? &*getUnknown(Pair.first->second) : V;
+ return Pair.first->second ? &*getSCEV(Pair.first->second) : V;
std::vector<Constant*> Operands;
Operands.reserve(I->getNumOperands());
}
}
}
-
+
Constant *C;
if (const CmpInst *CI = dyn_cast<CmpInst>(I))
C = ConstantFoldCompareInstOperands(CI->getPredicate(),
C = ConstantFoldInstOperands(I->getOpcode(), I->getType(),
&Operands[0], Operands.size());
Pair.first->second = C;
- return getUnknown(C);
+ return getSCEV(C);
}
}
if (OpAtScope != Comm->getOperand(i)) {
// Okay, at least one of these operands is loop variant but might be
// foldable. Build a new instance of the folded commutative expression.
- SmallVector<const SCEV*, 8> NewOps(Comm->op_begin(), Comm->op_begin()+i);
+ SmallVector<const SCEV *, 8> NewOps(Comm->op_begin(),
+ Comm->op_begin()+i);
NewOps.push_back(OpAtScope);
for (++i; i != e; ++i) {
// To evaluate this recurrence, we need to know how many times the AddRec
// loop iterates. Compute this now.
const SCEV* BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop());
- if (BackedgeTakenCount == CouldNotCompute) return AddRec;
+ if (BackedgeTakenCount == getCouldNotCompute()) return AddRec;
// Then, evaluate the AddRec.
return AddRec->evaluateAtIteration(BackedgeTakenCount, *this);
APInt Two(BitWidth, 2);
APInt Four(BitWidth, 4);
- {
+ {
using namespace APIntOps;
const APInt& C = L;
// Convert from chrec coefficients to polynomial coefficients AX^2+BX+C
// integer value or else APInt::sqrt() will assert.
APInt SqrtVal(SqrtTerm.sqrt());
- // Compute the two solutions for the quadratic formula.
+ // Compute the two solutions for the quadratic formula.
// The divisions must be performed as signed divisions.
APInt NegB(-B);
APInt TwoA( A << 1 );
ConstantInt *Solution1 = ConstantInt::get((NegB + SqrtVal).sdiv(TwoA));
ConstantInt *Solution2 = ConstantInt::get((NegB - SqrtVal).sdiv(TwoA));
- return std::make_pair(SE.getConstant(Solution1),
+ return std::make_pair(SE.getConstant(Solution1),
SE.getConstant(Solution2));
} // end APIntOps namespace
}
if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
// If the value is already zero, the branch will execute zero times.
if (C->getValue()->isZero()) return C;
- return CouldNotCompute; // Otherwise it will loop infinitely.
+ return getCouldNotCompute(); // Otherwise it will loop infinitely.
}
const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V);
if (!AddRec || AddRec->getLoop() != L)
- return CouldNotCompute;
+ return getCouldNotCompute();
if (AddRec->isAffine()) {
// If this is an affine expression, the execution count of this branch is
// where BW is the common bit width of Start and Step.
// Get the initial value for the loop.
- const SCEV* Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop());
- const SCEV* Step = getSCEVAtScope(AddRec->getOperand(1), L->getParentLoop());
+ const SCEV *Start = getSCEVAtScope(AddRec->getStart(),
+ L->getParentLoop());
+ const SCEV *Step = getSCEVAtScope(AddRec->getOperand(1),
+ L->getParentLoop());
if (const SCEVConstant *StepC = dyn_cast<SCEVConstant>(Step)) {
// For now we handle only constant steps.
#endif
// Pick the smallest positive root value.
if (ConstantInt *CB =
- dyn_cast<ConstantInt>(ConstantExpr::getICmp(ICmpInst::ICMP_ULT,
+ dyn_cast<ConstantInt>(ConstantExpr::getICmp(ICmpInst::ICMP_ULT,
R1->getValue(), R2->getValue()))) {
if (CB->getZExtValue() == false)
std::swap(R1, R2); // R1 is the minimum root now.
}
}
- return CouldNotCompute;
+ return getCouldNotCompute();
}
/// HowFarToNonZero - Return the number of times a backedge checking the
if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
if (!C->getValue()->isNullValue())
return getIntegerSCEV(0, C->getType());
- return CouldNotCompute; // Otherwise it will loop infinitely.
+ return getCouldNotCompute(); // Otherwise it will loop infinitely.
}
// We could implement others, but I really doubt anyone writes loops like
// this, and if they did, they would already be constant folded.
- return CouldNotCompute;
+ return getCouldNotCompute();
}
/// getLoopPredecessor - If the given loop's header has exactly one unique
LoopEntryPredicate->isUnconditional())
continue;
- ICmpInst *ICI = dyn_cast<ICmpInst>(LoopEntryPredicate->getCondition());
- if (!ICI) continue;
+ if (isNecessaryCond(LoopEntryPredicate->getCondition(), Pred, LHS, RHS,
+ LoopEntryPredicate->getSuccessor(0) != PredecessorDest))
+ return true;
+ }
- // Now that we found a conditional branch that dominates the loop, check to
- // see if it is the comparison we are looking for.
- Value *PreCondLHS = ICI->getOperand(0);
- Value *PreCondRHS = ICI->getOperand(1);
- ICmpInst::Predicate Cond;
- if (LoopEntryPredicate->getSuccessor(0) == PredecessorDest)
- Cond = ICI->getPredicate();
- else
- Cond = ICI->getInversePredicate();
+ return false;
+}
- 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;
+/// isNecessaryCond - Test whether the given CondValue value is a condition
+/// which is at least as strict as the one described by Pred, LHS, and RHS.
+bool ScalarEvolution::isNecessaryCond(Value *CondValue,
+ ICmpInst::Predicate Pred,
+ const SCEV *LHS, const SCEV *RHS,
+ bool Inverse) {
+ // Recursivly handle And and Or conditions.
+ if (BinaryOperator *BO = dyn_cast<BinaryOperator>(CondValue)) {
+ if (BO->getOpcode() == Instruction::And) {
+ if (!Inverse)
+ return isNecessaryCond(BO->getOperand(0), Pred, LHS, RHS, Inverse) ||
+ isNecessaryCond(BO->getOperand(1), Pred, LHS, RHS, Inverse);
+ } else if (BO->getOpcode() == Instruction::Or) {
+ if (Inverse)
+ return isNecessaryCond(BO->getOperand(0), Pred, LHS, RHS, Inverse) ||
+ isNecessaryCond(BO->getOperand(1), Pred, LHS, RHS, Inverse);
+ }
+ }
+
+ ICmpInst *ICI = dyn_cast<ICmpInst>(CondValue);
+ if (!ICI) return false;
+
+ // Now that we found a conditional branch that dominates the loop, check to
+ // see if it is the comparison we are looking for.
+ Value *PreCondLHS = ICI->getOperand(0);
+ Value *PreCondRHS = ICI->getOperand(1);
+ ICmpInst::Predicate Cond;
+ if (Inverse)
+ Cond = ICI->getInversePredicate();
+ else
+ Cond = ICI->getPredicate();
+
+ 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;
+ }
+ return false;
+ case ICmpInst::ICMP_SGT:
+ if (Pred == ICmpInst::ICMP_SLT) {
+ std::swap(PreCondLHS, PreCondRHS);
+ Cond = ICmpInst::ICMP_SLT;
+ break;
+ }
+ return false;
+ 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;
+ return false;
+ case ICmpInst::ICMP_SGT:
+ if (A.isMinSignedValue()) break;
+ return false;
+ case ICmpInst::ICMP_ULT:
+ if (A.isMaxValue()) break;
+ return false;
+ case ICmpInst::ICMP_UGT:
+ if (A.isMinValue()) break;
+ return false;
+ default:
+ return false;
+ }
+ 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;
- 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;
+ default:
+ // We weren't able to reconcile the condition.
+ return false;
+ }
- const SCEV* PreCondLHSSCEV = getSCEV(PreCondLHS);
- const SCEV* PreCondRHSSCEV = getSCEV(PreCondRHS);
- if ((HasSameValue(LHS, PreCondLHSSCEV) &&
- HasSameValue(RHS, PreCondRHSSCEV)) ||
- (HasSameValue(LHS, getNotSCEV(PreCondRHSSCEV)) &&
- HasSameValue(RHS, getNotSCEV(PreCondLHSSCEV))))
- return true;
- }
+ if (!PreCondLHS->getType()->isInteger()) return false;
- return false;
+ const SCEV *PreCondLHSSCEV = getSCEV(PreCondLHS);
+ const SCEV *PreCondRHSSCEV = getSCEV(PreCondRHS);
+ return (HasSameValue(LHS, PreCondLHSSCEV) &&
+ HasSameValue(RHS, PreCondRHSSCEV)) ||
+ (HasSameValue(LHS, getNotSCEV(PreCondRHSSCEV)) &&
+ HasSameValue(RHS, getNotSCEV(PreCondLHSSCEV)));
}
/// getBECount - Subtract the end and start values and divide by the step,
getAddExpr(getZeroExtendExpr(Diff, WideTy),
getZeroExtendExpr(RoundUp, WideTy));
if (getZeroExtendExpr(Add, WideTy) != OperandExtendedAdd)
- return CouldNotCompute;
+ return getCouldNotCompute();
return getUDivExpr(Add, Step);
}
/// HowManyLessThans - Return the number of times a backedge containing the
/// specified less-than comparison will execute. If not computable, return
/// CouldNotCompute.
-ScalarEvolution::BackedgeTakenInfo ScalarEvolution::
-HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
- const Loop *L, bool isSigned) {
+ScalarEvolution::BackedgeTakenInfo
+ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
+ const Loop *L, bool isSigned) {
// Only handle: "ADDREC < LoopInvariant".
- if (!RHS->isLoopInvariant(L)) return CouldNotCompute;
+ if (!RHS->isLoopInvariant(L)) return getCouldNotCompute();
const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS);
if (!AddRec || AddRec->getLoop() != L)
- return CouldNotCompute;
+ return getCouldNotCompute();
if (AddRec->isAffine()) {
// FORNOW: We only support unit strides.
// TODO: handle non-constant strides.
const SCEVConstant *CStep = dyn_cast<SCEVConstant>(Step);
if (!CStep || CStep->isZero())
- return CouldNotCompute;
+ return getCouldNotCompute();
if (CStep->isOne()) {
// With unit stride, the iteration never steps past the limit value.
} else if (CStep->getValue()->getValue().isStrictlyPositive()) {
APInt Max = APInt::getSignedMaxValue(BitWidth);
if ((Max - CStep->getValue()->getValue())
.slt(CLimit->getValue()->getValue()))
- return CouldNotCompute;
+ return getCouldNotCompute();
} else {
APInt Max = APInt::getMaxValue(BitWidth);
if ((Max - CStep->getValue()->getValue())
.ult(CLimit->getValue()->getValue()))
- return CouldNotCompute;
+ return getCouldNotCompute();
}
} else
// TODO: handle non-constant limit values below.
- return CouldNotCompute;
+ return getCouldNotCompute();
} else
// TODO: handle negative strides below.
- return CouldNotCompute;
+ return getCouldNotCompute();
// 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.
const SCEV* Start = AddRec->getOperand(0);
// Determine the minimum constant start value.
- const SCEV* MinStart = isa<SCEVConstant>(Start) ? Start :
+ const SCEV *MinStart = isa<SCEVConstant>(Start) ? Start :
getConstant(isSigned ? APInt::getSignedMinValue(BitWidth) :
APInt::getMinValue(BitWidth));
return BackedgeTakenInfo(BECount, MaxBECount);
}
- return CouldNotCompute;
+ return getCouldNotCompute();
}
/// getNumIterationsInRange - Return the number of iterations of this loop that
/// the condition, thus computing the exit count. If the iteration count can't
/// be computed, an instance of SCEVCouldNotCompute is returned.
const SCEV* SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range,
- ScalarEvolution &SE) const {
+ ScalarEvolution &SE) const {
if (Range.isFullSet()) // Infinite loop.
return SE.getCouldNotCompute();
// Ensure that the previous value is in the range. This is a sanity check.
assert(Range.contains(
- EvaluateConstantChrecAtConstant(this,
+ EvaluateConstantChrecAtConstant(this,
ConstantInt::get(ExitVal - One), SE)->getValue()) &&
"Linear scev computation is off in a bad way!");
return SE.getConstant(ExitValue);
if (R1) {
// Pick the smallest positive root value.
if (ConstantInt *CB =
- dyn_cast<ConstantInt>(ConstantExpr::getICmp(ICmpInst::ICMP_ULT,
+ dyn_cast<ConstantInt>(ConstantExpr::getICmp(ICmpInst::ICMP_ULT,
R1->getValue(), R2->getValue()))) {
if (CB->getZExtValue() == false)
std::swap(R1, R2); // R1 is the minimum root now.
//===----------------------------------------------------------------------===//
ScalarEvolution::ScalarEvolution()
- : FunctionPass(&ID), CouldNotCompute(new SCEVCouldNotCompute()) {
+ : FunctionPass(&ID) {
}
bool ScalarEvolution::runOnFunction(Function &F) {
BackedgeTakenCounts.clear();
ConstantEvolutionLoopExitValue.clear();
ValuesAtScopes.clear();
-
- for (std::map<ConstantInt*, SCEVConstant*>::iterator
- I = SCEVConstants.begin(), E = SCEVConstants.end(); I != E; ++I)
- delete I->second;
- for (std::map<std::pair<const SCEV*, const Type*>,
- SCEVTruncateExpr*>::iterator I = SCEVTruncates.begin(),
- E = SCEVTruncates.end(); I != E; ++I)
- delete I->second;
- for (std::map<std::pair<const SCEV*, const Type*>,
- SCEVZeroExtendExpr*>::iterator I = SCEVZeroExtends.begin(),
- E = SCEVZeroExtends.end(); I != E; ++I)
- delete I->second;
- for (std::map<std::pair<unsigned, std::vector<const SCEV*> >,
- SCEVCommutativeExpr*>::iterator I = SCEVCommExprs.begin(),
- E = SCEVCommExprs.end(); I != E; ++I)
- delete I->second;
- for (std::map<std::pair<const SCEV*, const SCEV*>, SCEVUDivExpr*>::iterator
- I = SCEVUDivs.begin(), E = SCEVUDivs.end(); I != E; ++I)
- delete I->second;
- for (std::map<std::pair<const SCEV*, const Type*>,
- SCEVSignExtendExpr*>::iterator I = SCEVSignExtends.begin(),
- E = SCEVSignExtends.end(); I != E; ++I)
- delete I->second;
- for (std::map<std::pair<const Loop *, std::vector<const SCEV*> >,
- SCEVAddRecExpr*>::iterator I = SCEVAddRecExprs.begin(),
- E = SCEVAddRecExprs.end(); I != E; ++I)
- delete I->second;
- for (std::map<Value*, SCEVUnknown*>::iterator I = SCEVUnknowns.begin(),
- E = SCEVUnknowns.end(); I != E; ++I)
- delete I->second;
-
- SCEVConstants.clear();
- SCEVTruncates.clear();
- SCEVZeroExtends.clear();
- SCEVCommExprs.clear();
- SCEVUDivs.clear();
- SCEVSignExtends.clear();
- SCEVAddRecExprs.clear();
- SCEVUnknowns.clear();
+ UniqueSCEVs.clear();
+ SCEVAllocator.Reset();
}
void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const {
OS << "Unpredictable backedge-taken count. ";
}
+ OS << "\n";
+ OS << "Loop " << L->getHeader()->getName() << ": ";
+
+ if (!isa<SCEVCouldNotCompute>(SE->getMaxBackedgeTakenCount(L))) {
+ OS << "max backedge-taken count is " << *SE->getMaxBackedgeTakenCount(L);
+ } else {
+ OS << "Unpredictable max backedge-taken count. ";
+ }
+
OS << "\n";
}
projects / oota-llvm.git / blobdiff