// 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 const SCEV *
-// class. We only create one SCEV of a particular shape, so pointer-comparisons
-// for equality are legal.
+// can handle. We only create one SCEV of a particular shape, so
+// pointer-comparisons for equality are legal.
//
// One important aspect of the SCEV objects is that they are never cyclic, even
// if there is a cycle in the dataflow for an expression (ie, a PHI node). If
return false;
}
-const SCEV *
-SCEVCouldNotCompute::replaceSymbolicValuesWithConcrete(
- const SCEV *Sym,
- const SCEV *Conc,
- ScalarEvolution &SE) const {
- return this;
+bool SCEVCouldNotCompute::hasOperand(const SCEV *) const {
+ llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
+ return false;
}
void SCEVCouldNotCompute::print(raw_ostream &OS) const {
}
const SCEV *ScalarEvolution::getConstant(const APInt& Val) {
- return getConstant(getContext().getConstantInt(Val));
+ return getConstant(ConstantInt::get(getContext(), Val));
}
const SCEV *
ScalarEvolution::getConstant(const Type *Ty, uint64_t V, bool isSigned) {
return getConstant(
- getContext().getConstantInt(cast<IntegerType>(Ty), V, isSigned));
+ ConstantInt::get(cast<IntegerType>(Ty), V, isSigned));
}
const Type *SCEVConstant::getType() const { return V->getType(); }
OS << ")";
}
-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);
- if (H != getOperand(i)) {
- SmallVector<const SCEV *, 8> NewOps;
- NewOps.reserve(getNumOperands());
- for (unsigned j = 0; j != i; ++j)
- NewOps.push_back(getOperand(j));
- NewOps.push_back(H);
- for (++i; i != e; ++i)
- NewOps.push_back(getOperand(i)->
- replaceSymbolicValuesWithConcrete(Sym, Conc, SE));
-
- if (isa<SCEVAddExpr>(this))
- return SE.getAddExpr(NewOps);
- else if (isa<SCEVMulExpr>(this))
- return SE.getMulExpr(NewOps);
- else if (isa<SCEVSMaxExpr>(this))
- return SE.getSMaxExpr(NewOps);
- else if (isa<SCEVUMaxExpr>(this))
- return SE.getUMaxExpr(NewOps);
- else
- llvm_unreachable("Unknown commutative expr!");
- }
- }
- return this;
-}
-
bool SCEVNAryExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
if (!getOperand(i)->dominates(BB, DT))
return RHS->getType();
}
-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);
- if (H != getOperand(i)) {
- SmallVector<const SCEV *, 8> NewOps;
- NewOps.reserve(getNumOperands());
- for (unsigned j = 0; j != i; ++j)
- NewOps.push_back(getOperand(j));
- NewOps.push_back(H);
- for (++i; i != e; ++i)
- NewOps.push_back(getOperand(i)->
- replaceSymbolicValuesWithConcrete(Sym, Conc, SE));
-
- return SE.getAddRecExpr(NewOps, L);
- }
- }
- return this;
-}
-
-
bool SCEVAddRecExpr::isLoopInvariant(const Loop *QueryLoop) const {
// Add recurrences are never invariant in the function-body (null loop).
if (!QueryLoop)
unsigned BitWidth = getTypeSizeInBits(AR->getType());
const Loop *L = AR->getLoop();
+ // If we have special knowledge that this addrec won't overflow,
+ // we don't need to do any further analysis.
+ if (AR->hasNoUnsignedOverflow())
+ return getAddRecExpr(getZeroExtendExpr(Start, Ty),
+ getZeroExtendExpr(Step, Ty),
+ L);
+
// Check whether the backedge-taken count is SCEVCouldNotCompute.
// Note that this serves two purposes: It filters out loops that are
// simply not analyzable, and it covers the case where this code is
unsigned BitWidth = getTypeSizeInBits(AR->getType());
const Loop *L = AR->getLoop();
+ // If we have special knowledge that this addrec won't overflow,
+ // we don't need to do any further analysis.
+ if (AR->hasNoSignedOverflow())
+ return getAddRecExpr(getSignExtendExpr(Start, Ty),
+ getSignExtendExpr(Step, Ty),
+ L);
+
// Check whether the backedge-taken count is SCEVCouldNotCompute.
// Note that this serves two purposes: It filters out loops that are
// simply not analyzable, and it covers the case where this code is
getTruncateOrZeroExtend(Step, Start->getType()));
Add = getAddExpr(Start, UMul);
OperandExtendedAdd =
- getAddExpr(getZeroExtendExpr(Start, WideTy),
+ getAddExpr(getSignExtendExpr(Start, WideTy),
getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy),
getZeroExtendExpr(Step, WideTy)));
- if (getZeroExtendExpr(Add, WideTy) == OperandExtendedAdd)
+ if (getSignExtendExpr(Add, WideTy) == OperandExtendedAdd)
// Return the expression with the addrec on the outside.
return getAddRecExpr(getSignExtendExpr(Start, Ty),
getZeroExtendExpr(Step, Ty),
++Idx;
while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
// We found two constants, fold them together!
- ConstantInt *Fold = getContext().getConstantInt(LHSC->getValue()->getValue() *
+ ConstantInt *Fold = ConstantInt::get(getContext(),
+ LHSC->getValue()->getValue() *
RHSC->getValue()->getValue());
Ops[0] = getConstant(Fold);
Ops.erase(Ops.begin()+1); // Erase the folded element
return S;
}
-/// getUDivExpr - Get a canonical multiply expression, or something simpler if
-/// possible.
+/// getUDivExpr - Get a canonical unsigned division expression, or something
+/// simpler if possible.
const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS,
const SCEV *RHS) {
assert(getEffectiveSCEVType(LHS->getType()) ==
if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
Constant *LHSCV = LHSC->getValue();
Constant *RHSCV = RHSC->getValue();
- return getConstant(cast<ConstantInt>(getContext().getConstantExprUDiv(LHSCV,
+ return getConstant(cast<ConstantInt>(ConstantExpr::getUDiv(LHSCV,
RHSCV)));
}
}
/// getAddRecExpr - Get an add recurrence expression for the specified loop.
/// Simplify the expression as much as possible.
const SCEV *ScalarEvolution::getAddRecExpr(const SCEV *Start,
- const SCEV *Step, const Loop *L) {
+ const SCEV *Step, const Loop *L) {
SmallVector<const SCEV *, 4> Operands;
Operands.push_back(Start);
if (const SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step))
assert(Idx < Ops.size());
while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
// We found two constants, fold them together!
- ConstantInt *Fold = getContext().getConstantInt(
+ ConstantInt *Fold = ConstantInt::get(getContext(),
APIntOps::smax(LHSC->getValue()->getValue(),
RHSC->getValue()->getValue()));
Ops[0] = getConstant(Fold);
assert(Idx < Ops.size());
while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
// We found two constants, fold them together!
- ConstantInt *Fold = getContext().getConstantInt(
+ ConstantInt *Fold = ConstantInt::get(getContext(),
APIntOps::umax(LHSC->getValue()->getValue(),
RHSC->getValue()->getValue()));
Ops[0] = getConstant(Fold);
/// specified signed integer value and return a SCEV for the constant.
const SCEV *ScalarEvolution::getIntegerSCEV(int Val, const Type *Ty) {
const IntegerType *ITy = cast<IntegerType>(getEffectiveSCEVType(Ty));
- return getConstant(getContext().getConstantInt(ITy, Val));
+ 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 getConstant(
- cast<ConstantInt>(getContext().getConstantExprNeg(VC->getValue())));
+ cast<ConstantInt>(ConstantExpr::getNeg(VC->getValue())));
const Type *Ty = V->getType();
Ty = getEffectiveSCEVType(Ty);
return getMulExpr(V,
- getConstant(cast<ConstantInt>(getContext().getAllOnesValue(Ty))));
+ getConstant(cast<ConstantInt>(Constant::getAllOnesValue(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 getConstant(
- cast<ConstantInt>(getContext().getConstantExprNot(VC->getValue())));
+ cast<ConstantInt>(ConstantExpr::getNot(VC->getValue())));
const Type *Ty = V->getType();
Ty = getEffectiveSCEVType(Ty);
const SCEV *AllOnes =
- getConstant(cast<ConstantInt>(getContext().getAllOnesValue(Ty)));
+ getConstant(cast<ConstantInt>(Constant::getAllOnesValue(Ty)));
return getMinusSCEV(AllOnes, V);
}
return getUMinExpr(PromotedLHS, PromotedRHS);
}
-/// 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.
+/// PushDefUseChildren - Push users of the given Instruction
+/// onto the given Worklist.
+static void
+PushDefUseChildren(Instruction *I,
+ SmallVectorImpl<Instruction *> &Worklist) {
+ // Push the def-use children onto the Worklist stack.
+ for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
+ UI != UE; ++UI)
+ Worklist.push_back(cast<Instruction>(UI));
+}
+
+/// ForgetSymbolicValue - This looks up computed SCEV values for all
+/// instructions that depend on the given instruction and removes them from
+/// the Scalars map if they reference SymName. This is used during PHI
+/// resolution.
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;
+ScalarEvolution::ForgetSymbolicName(Instruction *I, const SCEV *SymName) {
+ SmallVector<Instruction *, 16> Worklist;
+ PushDefUseChildren(I, Worklist);
- const SCEV *NV =
- SI->second->replaceSymbolicValuesWithConcrete(SymName, NewVal, *this);
- if (NV == SI->second) return; // No change.
+ SmallPtrSet<Instruction *, 8> Visited;
+ Visited.insert(I);
+ while (!Worklist.empty()) {
+ Instruction *I = Worklist.pop_back_val();
+ if (!Visited.insert(I)) continue;
- SI->second = NV; // Update the scalars map!
+ std::map<SCEVCallbackVH, const SCEV*>::iterator It =
+ Scalars.find(static_cast<Value *>(I));
+ if (It != Scalars.end()) {
+ // Short-circuit the def-use traversal if the symbolic name
+ // ceases to appear in expressions.
+ if (!It->second->hasOperand(SymName))
+ continue;
+
+ // SCEVUnknown for a PHI either means that it has an unrecognized
+ // structure, or it's a PHI that's in the progress of being computed
+ // by createNodeForPHI. In the former case, additional loop trip
+ // count information isn't going to change anything. In the later
+ // case, createNodeForPHI will perform the necessary updates on its
+ // own when it gets to that point.
+ if (!isa<PHINode>(I) || !isa<SCEVUnknown>(It->second))
+ Scalars.erase(It);
+ ValuesAtScopes.erase(I);
+ }
- // Any instruction values that use this instruction might also need to be
- // updated!
- for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
- UI != E; ++UI)
- ReplaceSymbolicValueWithConcrete(cast<Instruction>(*UI), SymName, NewVal);
+ PushDefUseChildren(I, Worklist);
+ }
}
/// createNodeForPHI - PHI nodes have two cases. Either the PHI node exists in
// Using this symbolic name for the PHI, analyze the value coming around
// the back-edge.
- const SCEV *BEValue = getSCEV(PN->getIncomingValue(BackEdge));
+ Value *BEValueV = PN->getIncomingValue(BackEdge);
+ const SCEV *BEValue = getSCEV(BEValueV);
// NOTE: If BEValue is loop invariant, we know that the PHI node just
// has a special value for the first iteration of the loop.
cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) {
const SCEV *StartVal =
getSCEV(PN->getIncomingValue(IncomingEdge));
- const SCEV *PHISCEV =
- getAddRecExpr(StartVal, Accum, L);
+ const SCEVAddRecExpr *PHISCEV =
+ cast<SCEVAddRecExpr>(getAddRecExpr(StartVal, Accum, L));
+
+ // If the increment doesn't overflow, then neither the addrec nor the
+ // post-increment will overflow.
+ if (const AddOperator *OBO = dyn_cast<AddOperator>(BEValueV))
+ if (OBO->getOperand(0) == PN &&
+ getSCEV(OBO->getOperand(1)) ==
+ PHISCEV->getStepRecurrence(*this)) {
+ const SCEVAddRecExpr *PostInc = PHISCEV->getPostIncExpr(*this);
+ if (OBO->hasNoUnsignedOverflow()) {
+ const_cast<SCEVAddRecExpr *>(PHISCEV)
+ ->setHasNoUnsignedOverflow(true);
+ const_cast<SCEVAddRecExpr *>(PostInc)
+ ->setHasNoUnsignedOverflow(true);
+ }
+ if (OBO->hasNoSignedOverflow()) {
+ const_cast<SCEVAddRecExpr *>(PHISCEV)
+ ->setHasNoSignedOverflow(true);
+ const_cast<SCEVAddRecExpr *>(PostInc)
+ ->setHasNoSignedOverflow(true);
+ }
+ }
// 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
- // entries for the scalars that use the PHI (except for the PHI
- // itself) to use the new analyzed value instead of the "symbolic"
- // value.
- ReplaceSymbolicValueWithConcrete(PN, SymbolicName, PHISCEV);
+ // to be symbolic. We now need to go back and purge all of the
+ // entries for the scalars that use the symbolic expression.
+ ForgetSymbolicName(PN, SymbolicName);
+ Scalars[SCEVCallbackVH(PN, this)] = PHISCEV;
return PHISCEV;
}
}
getAddRecExpr(StartVal, AddRec->getOperand(1), 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
- // entries for the scalars that use the PHI (except for the PHI
- // itself) to use the new analyzed value instead of the "symbolic"
- // value.
- ReplaceSymbolicValueWithConcrete(PN, SymbolicName, PHISCEV);
+ // to be symbolic. We now need to go back and purge all of the
+ // entries for the scalars that use the symbolic expression.
+ ForgetSymbolicName(PN, SymbolicName);
+ Scalars[SCEVCallbackVH(PN, this)] = PHISCEV;
return PHISCEV;
}
}
// Turn shift left of a constant amount into a multiply.
if (ConstantInt *SA = dyn_cast<ConstantInt>(U->getOperand(1))) {
uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
- Constant *X = getContext().getConstantInt(
+ Constant *X = ConstantInt::get(getContext(),
APInt(BitWidth, 1).shl(SA->getLimitedValue(BitWidth)));
return getMulExpr(getSCEV(U->getOperand(0)), getSCEV(X));
}
// Turn logical shift right of a constant into a unsigned divide.
if (ConstantInt *SA = dyn_cast<ConstantInt>(U->getOperand(1))) {
uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
- Constant *X = getContext().getConstantInt(
+ Constant *X = ConstantInt::get(getContext(),
APInt(BitWidth, 1).shl(SA->getLimitedValue(BitWidth)));
return getUDivExpr(getSCEV(U->getOperand(0)), getSCEV(X));
}
Worklist.push_back(PN);
}
-/// PushDefUseChildren - Push users of the given Instruction
-/// onto the given Worklist.
-static void
-PushDefUseChildren(Instruction *I,
- SmallVectorImpl<Instruction *> &Worklist) {
- // Push the def-use children onto the Worklist stack.
- for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
- UI != UE; ++UI)
- Worklist.push_back(cast<Instruction>(UI));
-}
-
const ScalarEvolution::BackedgeTakenInfo &
ScalarEvolution::getBackedgeTakenInfo(const Loop *L) {
// Initially insert a CouldNotCompute for this loop. If the insertion
} else if (isa<ConstantAggregateZero>(Init)) {
if (const StructType *STy = dyn_cast<StructType>(Init->getType())) {
assert(Idx < STy->getNumElements() && "Bad struct index!");
- Init = Context.getNullValue(STy->getElementType(Idx));
+ Init = Constant::getNullValue(STy->getElementType(Idx));
} else if (const ArrayType *ATy = dyn_cast<ArrayType>(Init->getType())) {
if (Idx >= ATy->getNumElements()) return 0; // Bogus program
- Init = Context.getNullValue(ATy->getElementType());
+ Init = Constant::getNullValue(ATy->getElementType());
} else {
llvm_unreachable("Unknown constant aggregate type!");
}
unsigned MaxSteps = MaxBruteForceIterations;
for (unsigned IterationNum = 0; IterationNum != MaxSteps; ++IterationNum) {
- ConstantInt *ItCst = getContext().getConstantInt(
+ ConstantInt *ItCst = ConstantInt::get(
cast<IntegerType>(IdxExpr->getType()), IterationNum);
ConstantInt *Val = EvaluateConstantChrecAtConstant(IdxExpr, ItCst, *this);
}
}
-/// ComputeBackedgeTakenCountExhaustively - If the trip is known to execute a
+/// ComputeBackedgeTakenCountExhaustively - If the loop is known to execute a
/// constant number of times (the condition evolves only from constants),
/// try to evaluate a few iterations of the loop until we get the exit
/// condition gets a value of ExitWhen (true or false). If we cannot
LLVMContext &Context = SE.getContext();
ConstantInt *Solution1 =
- Context.getConstantInt((NegB + SqrtVal).sdiv(TwoA));
+ ConstantInt::get(Context, (NegB + SqrtVal).sdiv(TwoA));
ConstantInt *Solution2 =
- Context.getConstantInt((NegB - SqrtVal).sdiv(TwoA));
+ ConstantInt::get(Context, (NegB - SqrtVal).sdiv(TwoA));
return std::make_pair(SE.getConstant(Solution1),
SE.getConstant(Solution2));
#endif
// Pick the smallest positive root value.
if (ConstantInt *CB =
- dyn_cast<ConstantInt>(getContext().getConstantExprICmp(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.
// Check Add for unsigned overflow.
// TODO: More sophisticated things could be done here.
- const Type *WideTy = getContext().getIntegerType(getTypeSizeInBits(Ty) + 1);
+ const Type *WideTy = IntegerType::get(getTypeSizeInBits(Ty) + 1);
const SCEV *EDiff = getZeroExtendExpr(Diff, WideTy);
const SCEV *ERoundUp = getZeroExtendExpr(RoundUp, WideTy);
const SCEV *OperandExtendedAdd = getAddExpr(EDiff, ERoundUp);
// The exit value should be (End+A)/A.
APInt ExitVal = (End + A).udiv(A);
- ConstantInt *ExitValue = SE.getContext().getConstantInt(ExitVal);
+ ConstantInt *ExitValue = ConstantInt::get(SE.getContext(), ExitVal);
// Evaluate at the exit value. If we really did fall out of the valid
// range, then we computed our trip count, otherwise wrap around or other
// Ensure that the previous value is in the range. This is a sanity check.
assert(Range.contains(
EvaluateConstantChrecAtConstant(this,
- SE.getContext().getConstantInt(ExitVal - One), SE)->getValue()) &&
+ ConstantInt::get(SE.getContext(), ExitVal - One), SE)->getValue()) &&
"Linear scev computation is off in a bad way!");
return SE.getConstant(ExitValue);
} else if (isQuadratic()) {
if (R1) {
// Pick the smallest positive root value.
if (ConstantInt *CB =
- dyn_cast<ConstantInt>(
- SE.getContext().getConstantExprICmp(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.
if (Range.contains(R1Val->getValue())) {
// The next iteration must be out of the range...
ConstantInt *NextVal =
- SE.getContext().getConstantInt(R1->getValue()->getValue()+1);
+ ConstantInt::get(SE.getContext(), R1->getValue()->getValue()+1);
R1Val = EvaluateConstantChrecAtConstant(this, NextVal, SE);
if (!Range.contains(R1Val->getValue()))
// If R1 was not in the range, then it is a good return value. Make
// sure that R1-1 WAS in the range though, just in case.
ConstantInt *NextVal =
- SE.getContext().getConstantInt(R1->getValue()->getValue()-1);
+ ConstantInt::get(SE.getContext(), R1->getValue()->getValue()-1);
R1Val = EvaluateConstantChrecAtConstant(this, NextVal, SE);
if (Range.contains(R1Val->getValue()))
return R1;
projects / oota-llvm.git / blobdiff