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>
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 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 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!
-
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!
-
-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);
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!
-
bool SCEVUnknown::isLoopInvariant(const Loop *L) const {
// All non-instruction values are loop invariant. All instructions are loop
// invariant if they are not contained in the specified 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,
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,
++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
/// 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)
/// 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
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);
}
BranchInst *ExitBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
if (ExitBr == 0) return CouldNotCompute;
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
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) {
+const SCEV *
+ScalarEvolution::ComputeLoadConstantCompareBackedgeTakenCount(
+ LoadInst *LI,
+ Constant *RHS,
+ const Loop *L,
+ ICmpInst::Predicate predicate) {
if (LI->isVolatile()) return CouldNotCompute;
// Check to see if the loaded pointer is a getelementptr of a global.
/// 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())
/// 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) {
+const SCEV *
+ScalarEvolution::ComputeBackedgeTakenCountExhaustively(const Loop *L,
+ Value *Cond,
+ bool ExitWhen) {
PHINode *PN = getConstantEvolvingPHI(Cond, L);
if (PN == 0) return CouldNotCompute;
}
}
}
-
+
Constant *C;
if (const CmpInst *CI = dyn_cast<CmpInst>(I))
C = ConstantFoldCompareInstOperands(CI->getPredicate(),
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) {
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
}
// 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.
/// 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;
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));
/// 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.
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<Value*, SCEVUnknown*>::iterator I = SCEVUnknowns.begin(),
E = SCEVUnknowns.end(); I != E; ++I)
delete I->second;
-
+
SCEVConstants.clear();
SCEVTruncates.clear();
SCEVZeroExtends.clear();
projects / oota-llvm.git / commitdiff