// Implementation of the SCEV class.
//
-SCEV::~SCEV() {}
-
void SCEV::dump() const {
print(dbgs());
dbgs() << '\n';
}
+void SCEV::print(raw_ostream &OS) const {
+ switch (getSCEVType()) {
+ case scConstant:
+ WriteAsOperand(OS, cast<SCEVConstant>(this)->getValue(), false);
+ return;
+ case scTruncate: {
+ const SCEVTruncateExpr *Trunc = cast<SCEVTruncateExpr>(this);
+ const SCEV *Op = Trunc->getOperand();
+ OS << "(trunc " << *Op->getType() << " " << *Op << " to "
+ << *Trunc->getType() << ")";
+ return;
+ }
+ case scZeroExtend: {
+ const SCEVZeroExtendExpr *ZExt = cast<SCEVZeroExtendExpr>(this);
+ const SCEV *Op = ZExt->getOperand();
+ OS << "(zext " << *Op->getType() << " " << *Op << " to "
+ << *ZExt->getType() << ")";
+ return;
+ }
+ case scSignExtend: {
+ const SCEVSignExtendExpr *SExt = cast<SCEVSignExtendExpr>(this);
+ const SCEV *Op = SExt->getOperand();
+ OS << "(sext " << *Op->getType() << " " << *Op << " to "
+ << *SExt->getType() << ")";
+ return;
+ }
+ case scAddRecExpr: {
+ const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(this);
+ OS << "{" << *AR->getOperand(0);
+ for (unsigned i = 1, e = AR->getNumOperands(); i != e; ++i)
+ OS << ",+," << *AR->getOperand(i);
+ OS << "}<";
+ WriteAsOperand(OS, AR->getLoop()->getHeader(), /*PrintType=*/false);
+ OS << ">";
+ return;
+ }
+ case scAddExpr:
+ case scMulExpr:
+ case scUMaxExpr:
+ case scSMaxExpr: {
+ const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(this);
+ const char *OpStr = 0;
+ switch (NAry->getSCEVType()) {
+ case scAddExpr: OpStr = " + "; break;
+ case scMulExpr: OpStr = " * "; break;
+ case scUMaxExpr: OpStr = " umax "; break;
+ case scSMaxExpr: OpStr = " smax "; break;
+ }
+ OS << "(";
+ for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end();
+ I != E; ++I) {
+ OS << **I;
+ if (llvm::next(I) != E)
+ OS << OpStr;
+ }
+ OS << ")";
+ return;
+ }
+ case scUDivExpr: {
+ const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(this);
+ OS << "(" << *UDiv->getLHS() << " /u " << *UDiv->getRHS() << ")";
+ return;
+ }
+ case scUnknown: {
+ const SCEVUnknown *U = cast<SCEVUnknown>(this);
+ const Type *AllocTy;
+ if (U->isSizeOf(AllocTy)) {
+ OS << "sizeof(" << *AllocTy << ")";
+ return;
+ }
+ if (U->isAlignOf(AllocTy)) {
+ OS << "alignof(" << *AllocTy << ")";
+ return;
+ }
+
+ const Type *CTy;
+ Constant *FieldNo;
+ if (U->isOffsetOf(CTy, FieldNo)) {
+ OS << "offsetof(" << *CTy << ", ";
+ WriteAsOperand(OS, FieldNo, false);
+ OS << ")";
+ return;
+ }
+
+ // Otherwise just print it normally.
+ WriteAsOperand(OS, U->getValue(), false);
+ return;
+ }
+ case scCouldNotCompute:
+ OS << "***COULDNOTCOMPUTE***";
+ return;
+ default: break;
+ }
+ llvm_unreachable("Unknown SCEV kind!");
+}
+
+const Type *SCEV::getType() const {
+ switch (getSCEVType()) {
+ case scConstant:
+ return cast<SCEVConstant>(this)->getType();
+ case scTruncate:
+ case scZeroExtend:
+ case scSignExtend:
+ return cast<SCEVCastExpr>(this)->getType();
+ case scAddRecExpr:
+ case scMulExpr:
+ case scUMaxExpr:
+ case scSMaxExpr:
+ return cast<SCEVNAryExpr>(this)->getType();
+ case scAddExpr:
+ return cast<SCEVAddExpr>(this)->getType();
+ case scUDivExpr:
+ return cast<SCEVUDivExpr>(this)->getType();
+ case scUnknown:
+ return cast<SCEVUnknown>(this)->getType();
+ case scCouldNotCompute:
+ llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
+ return 0;
+ default: break;
+ }
+ llvm_unreachable("Unknown SCEV kind!");
+ return 0;
+}
+
bool SCEV::isZero() const {
if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(this))
return SC->getValue()->isZero();
SCEVCouldNotCompute::SCEVCouldNotCompute() :
SCEV(FoldingSetNodeIDRef(), scCouldNotCompute) {}
-const Type *SCEVCouldNotCompute::getType() const {
- llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
- return 0;
-}
-
-bool SCEVCouldNotCompute::hasOperand(const SCEV *) const {
- llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
- return false;
-}
-
-void SCEVCouldNotCompute::print(raw_ostream &OS) const {
- OS << "***COULDNOTCOMPUTE***";
-}
-
bool SCEVCouldNotCompute::classof(const SCEV *S) {
return S->getSCEVType() == scCouldNotCompute;
}
return getConstant(ConstantInt::get(ITy, V, isSigned));
}
-const Type *SCEVConstant::getType() const { return V->getType(); }
-
-void SCEVConstant::print(raw_ostream &OS) const {
- WriteAsOperand(OS, V, false);
-}
-
SCEVCastExpr::SCEVCastExpr(const FoldingSetNodeIDRef ID,
unsigned SCEVTy, const SCEV *op, const Type *ty)
: SCEV(ID, SCEVTy), Op(op), Ty(ty) {}
"Cannot truncate non-integer value!");
}
-void SCEVTruncateExpr::print(raw_ostream &OS) const {
- OS << "(trunc " << *Op->getType() << " " << *Op << " to " << *Ty << ")";
-}
-
SCEVZeroExtendExpr::SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID,
const SCEV *op, const Type *ty)
: SCEVCastExpr(ID, scZeroExtend, op, ty) {
"Cannot zero extend non-integer value!");
}
-void SCEVZeroExtendExpr::print(raw_ostream &OS) const {
- OS << "(zext " << *Op->getType() << " " << *Op << " to " << *Ty << ")";
-}
-
SCEVSignExtendExpr::SCEVSignExtendExpr(const FoldingSetNodeIDRef ID,
const SCEV *op, const Type *ty)
: SCEVCastExpr(ID, scSignExtend, op, ty) {
"Cannot sign extend non-integer value!");
}
-void SCEVSignExtendExpr::print(raw_ostream &OS) const {
- OS << "(sext " << *Op->getType() << " " << *Op << " to " << *Ty << ")";
-}
-
-void SCEVCommutativeExpr::print(raw_ostream &OS) const {
- const char *OpStr = getOperationStr();
- OS << "(";
- for (op_iterator I = op_begin(), E = op_end(); I != E; ++I) {
- OS << **I;
- if (llvm::next(I) != E)
- OS << OpStr;
- }
- OS << ")";
-}
-
-bool SCEVNAryExpr::hasOperand(const SCEV *O) const {
- for (op_iterator I = op_begin(), E = op_end(); I != E; ++I) {
- const SCEV *S = *I;
- if (O == S || S->hasOperand(O))
- return true;
- }
- return false;
-}
-
-void SCEVUDivExpr::print(raw_ostream &OS) const {
- OS << "(" << *LHS << " /u " << *RHS << ")";
-}
-
-const Type *SCEVUDivExpr::getType() const {
- // In most cases the types of LHS and RHS will be the same, but in some
- // crazy cases one or the other may be a pointer. ScalarEvolution doesn't
- // depend on the type for correctness, but handling types carefully can
- // avoid extra casts in the SCEVExpander. The LHS is more likely to be
- // a pointer type than the RHS, so use the RHS' type here.
- return RHS->getType();
-}
-
-void SCEVAddRecExpr::print(raw_ostream &OS) const {
- OS << "{" << *Operands[0];
- for (unsigned i = 1, e = NumOperands; i != e; ++i)
- OS << ",+," << *Operands[i];
- OS << "}<";
- WriteAsOperand(OS, L->getHeader(), /*PrintType=*/false);
- OS << ">";
-}
-
void SCEVUnknown::deleted() {
// Clear this SCEVUnknown from various maps.
- SE->ValuesAtScopes.erase(this);
- SE->UnsignedRanges.erase(this);
- SE->SignedRanges.erase(this);
+ SE->forgetMemoizedResults(this);
// Remove this SCEVUnknown from the uniquing map.
SE->UniqueSCEVs.RemoveNode(this);
void SCEVUnknown::allUsesReplacedWith(Value *New) {
// Clear this SCEVUnknown from various maps.
- SE->ValuesAtScopes.erase(this);
- SE->UnsignedRanges.erase(this);
- SE->SignedRanges.erase(this);
+ SE->forgetMemoizedResults(this);
// Remove this SCEVUnknown from the uniquing map.
SE->UniqueSCEVs.RemoveNode(this);
setValPtr(New);
}
-const Type *SCEVUnknown::getType() const {
- return getValue()->getType();
-}
-
bool SCEVUnknown::isSizeOf(const Type *&AllocTy) const {
if (ConstantExpr *VCE = dyn_cast<ConstantExpr>(getValue()))
if (VCE->getOpcode() == Instruction::PtrToInt)
return false;
}
-void SCEVUnknown::print(raw_ostream &OS) const {
- const Type *AllocTy;
- if (isSizeOf(AllocTy)) {
- OS << "sizeof(" << *AllocTy << ")";
- return;
- }
- if (isAlignOf(AllocTy)) {
- OS << "alignof(" << *AllocTy << ")";
- return;
- }
-
- const Type *CTy;
- Constant *FieldNo;
- if (isOffsetOf(CTy, FieldNo)) {
- OS << "offsetof(" << *CTy << ", ";
- WriteAsOperand(OS, FieldNo, false);
- OS << ")";
- return;
- }
-
- // Otherwise just print it normally.
- WriteAsOperand(OS, getValue(), false);
-}
-
//===----------------------------------------------------------------------===//
// SCEV Utilities
//===----------------------------------------------------------------------===//
// Short-circuit the def-use traversal if the symbolic name
// ceases to appear in expressions.
- if (Old != SymName && !Old->hasOperand(SymName))
+ if (Old != SymName && !hasOperand(Old, SymName))
continue;
// SCEVUnknown for a PHI either means that it has an unrecognized
if (!isa<PHINode>(I) ||
!isa<SCEVUnknown>(Old) ||
(I != PN && Old == SymName)) {
- ValuesAtScopes.erase(Old);
- UnsignedRanges.erase(Old);
- SignedRanges.erase(Old);
+ forgetMemoizedResults(Old);
ValueExprMap.erase(It);
}
}
// PHI's incoming blocks are in a different loop, in which case doing so
// risks breaking LCSSA form. Instcombine would normally zap these, but
// it doesn't have DominatorTree information, so it may miss cases.
- if (Value *V = SimplifyInstruction(PN, TD, DT)) {
- Instruction *I = dyn_cast<Instruction>(V);
- // Only instructions are problematic for preserving LCSSA form.
- if (!I)
+ if (Value *V = SimplifyInstruction(PN, TD, DT))
+ if (LI->replacementPreservesLCSSAForm(PN, V))
return getSCEV(V);
- // If the instruction is not defined in a loop, then it can be used freely.
- Loop *ILoop = LI->getLoopFor(I->getParent());
- if (!ILoop)
- return getSCEV(I);
-
- // If the instruction is defined in the same loop as the phi node, or in a
- // loop that contains the phi node loop as an inner loop, then using it as
- // a replacement for the phi node will not break LCSSA form.
- Loop *PNLoop = LI->getLoopFor(PN->getParent());
- if (ILoop->contains(PNLoop))
- return getSCEV(I);
- }
-
// If it's not a loop phi, we can't handle it yet.
return getUnknown(PN);
}
// If C is a single bit, it may be in the sign-bit position
// before the zero-extend. In this case, represent the xor
// using an add, which is equivalent, and re-apply the zext.
- APInt Trunc = APInt(CI->getValue()).trunc(Z0TySize);
- if (APInt(Trunc).zext(getTypeSizeInBits(UTy)) == CI->getValue() &&
+ APInt Trunc = CI->getValue().trunc(Z0TySize);
+ if (Trunc.zext(getTypeSizeInBits(UTy)) == CI->getValue() &&
Trunc.isSignBit())
return getZeroExtendExpr(getAddExpr(Z0, getConstant(Trunc)),
UTy);
// case, createNodeForPHI will perform the necessary updates on its
// own when it gets to that point.
if (!isa<PHINode>(I) || !isa<SCEVUnknown>(Old)) {
- ValuesAtScopes.erase(Old);
- UnsignedRanges.erase(Old);
- SignedRanges.erase(Old);
+ forgetMemoizedResults(Old);
ValueExprMap.erase(It);
}
if (PHINode *PN = dyn_cast<PHINode>(I))
ValueExprMapType::iterator It = ValueExprMap.find(static_cast<Value *>(I));
if (It != ValueExprMap.end()) {
- const SCEV *Old = It->second;
- ValuesAtScopes.erase(Old);
- UnsignedRanges.erase(Old);
- SignedRanges.erase(Old);
+ forgetMemoizedResults(It->second);
ValueExprMap.erase(It);
if (PHINode *PN = dyn_cast<PHINode>(I))
ConstantEvolutionLoopExitValue.erase(PN);
ValueExprMapType::iterator It = ValueExprMap.find(static_cast<Value *>(I));
if (It != ValueExprMap.end()) {
- const SCEV *Old = It->second;
- ValuesAtScopes.erase(Old);
- UnsignedRanges.erase(Old);
- SignedRanges.erase(Old);
+ forgetMemoizedResults(It->second);
ValueExprMap.erase(It);
if (PHINode *PN = dyn_cast<PHINode>(I))
ConstantEvolutionLoopExitValue.erase(PN);
// bit width during computations.
APInt AD = A.lshr(Mult2).zext(BW + 1); // AD = A / D
APInt Mod(BW + 1, 0);
- Mod.set(BW - Mult2); // Mod = N / D
+ Mod.setBit(BW - Mult2); // Mod = N / D
APInt I = AD.multiplicativeInverse(Mod);
// 4. Compute the minimum unsigned root of the equation:
trivially_true:
// Return 0 == 0.
- LHS = RHS = getConstant(Type::getInt1Ty(getContext()), 0);
+ LHS = RHS = getConstant(ConstantInt::getFalse(getContext()));
Pred = ICmpInst::ICMP_EQ;
return true;
trivially_false:
// Return 0 != 0.
- LHS = RHS = getConstant(Type::getInt1Ty(getContext()), 0);
+ LHS = RHS = getConstant(ConstantInt::getFalse(getContext()));
Pred = ICmpInst::ICMP_NE;
return true;
}
BackedgeTakenCounts.clear();
ConstantEvolutionLoopExitValue.clear();
ValuesAtScopes.clear();
+ LoopDispositions.clear();
+ BlockDispositions.clear();
UnsignedRanges.clear();
SignedRanges.clear();
UniqueSCEVs.clear();
PrintLoopInfo(OS, &SE, *I);
}
-bool ScalarEvolution::isLoopInvariant(const SCEV *S, const Loop *L) {
+ScalarEvolution::LoopDisposition
+ScalarEvolution::getLoopDisposition(const SCEV *S, const Loop *L) {
+ std::map<const Loop *, LoopDisposition> &Values = LoopDispositions[S];
+ std::pair<std::map<const Loop *, LoopDisposition>::iterator, bool> Pair =
+ Values.insert(std::make_pair(L, LoopVariant));
+ if (!Pair.second)
+ return Pair.first->second;
+
+ LoopDisposition D = computeLoopDisposition(S, L);
+ return LoopDispositions[S][L] = D;
+}
+
+ScalarEvolution::LoopDisposition
+ScalarEvolution::computeLoopDisposition(const SCEV *S, const Loop *L) {
switch (S->getSCEVType()) {
case scConstant:
- return true;
+ return LoopInvariant;
case scTruncate:
case scZeroExtend:
case scSignExtend:
- return isLoopInvariant(cast<SCEVCastExpr>(S)->getOperand(), L);
+ return getLoopDisposition(cast<SCEVCastExpr>(S)->getOperand(), L);
case scAddRecExpr: {
const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(S);
+ // If L is the addrec's loop, it's computable.
+ if (AR->getLoop() == L)
+ return LoopComputable;
+
// Add recurrences are never invariant in the function-body (null loop).
if (!L)
- return false;
+ return LoopVariant;
// This recurrence is variant w.r.t. L if L contains AR's loop.
if (L->contains(AR->getLoop()))
- return false;
+ return LoopVariant;
// This recurrence is invariant w.r.t. L if AR's loop contains L.
if (AR->getLoop()->contains(L))
- return true;
+ return LoopInvariant;
// This recurrence is variant w.r.t. L if any of its operands
// are variant.
for (SCEVAddRecExpr::op_iterator I = AR->op_begin(), E = AR->op_end();
I != E; ++I)
if (!isLoopInvariant(*I, L))
- return false;
+ return LoopVariant;
// Otherwise it's loop-invariant.
- return true;
+ return LoopInvariant;
}
case scAddExpr:
case scMulExpr:
case scUMaxExpr:
case scSMaxExpr: {
const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(S);
+ bool HasVarying = false;
for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end();
- I != E; ++I)
- if (!isLoopInvariant(*I, L))
- return false;
- return true;
+ I != E; ++I) {
+ LoopDisposition D = getLoopDisposition(*I, L);
+ if (D == LoopVariant)
+ return LoopVariant;
+ if (D == LoopComputable)
+ HasVarying = true;
+ }
+ return HasVarying ? LoopComputable : LoopInvariant;
}
case scUDivExpr: {
const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S);
- return isLoopInvariant(UDiv->getLHS(), L) &&
- isLoopInvariant(UDiv->getRHS(), L);
+ LoopDisposition LD = getLoopDisposition(UDiv->getLHS(), L);
+ if (LD == LoopVariant)
+ return LoopVariant;
+ LoopDisposition RD = getLoopDisposition(UDiv->getRHS(), L);
+ if (RD == LoopVariant)
+ return LoopVariant;
+ return (LD == LoopInvariant && RD == LoopInvariant) ?
+ LoopInvariant : LoopComputable;
}
case scUnknown:
// All non-instruction values are loop invariant. All instructions are loop
// Instructions are never considered invariant in the function body
// (null loop) because they are defined within the "loop".
if (Instruction *I = dyn_cast<Instruction>(cast<SCEVUnknown>(S)->getValue()))
- return L && !L->contains(I);
- return true;
+ return (L && !L->contains(I)) ? LoopInvariant : LoopVariant;
+ return LoopInvariant;
case scCouldNotCompute:
llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
- return false;
+ return LoopVariant;
default: break;
}
llvm_unreachable("Unknown SCEV kind!");
- return false;
+ return LoopVariant;
+}
+
+bool ScalarEvolution::isLoopInvariant(const SCEV *S, const Loop *L) {
+ return getLoopDisposition(S, L) == LoopInvariant;
}
bool ScalarEvolution::hasComputableLoopEvolution(const SCEV *S, const Loop *L) {
- switch (S->getSCEVType()) {
- case scConstant:
- return false;
- case scTruncate:
- case scZeroExtend:
- case scSignExtend:
- return hasComputableLoopEvolution(cast<SCEVCastExpr>(S)->getOperand(), L);
- case scAddRecExpr:
- return cast<SCEVAddRecExpr>(S)->getLoop() == L;
- case scAddExpr:
- case scMulExpr:
- case scUMaxExpr:
- case scSMaxExpr: {
- const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(S);
- bool HasVarying = false;
- for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end();
- I != E; ++I) {
- const SCEV *Op = *I;
- if (!isLoopInvariant(Op, L)) {
- if (hasComputableLoopEvolution(Op, L))
- HasVarying = true;
- else
- return false;
- }
- }
- return HasVarying;
- }
- case scUDivExpr: {
- const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S);
- bool HasVarying = false;
- if (!isLoopInvariant(UDiv->getLHS(), L)) {
- if (hasComputableLoopEvolution(UDiv->getLHS(), L))
- HasVarying = true;
- else
- return false;
- }
- if (!isLoopInvariant(UDiv->getRHS(), L)) {
- if (hasComputableLoopEvolution(UDiv->getRHS(), L))
- HasVarying = true;
- else
- return false;
- }
- return HasVarying;
- }
- case scUnknown:
- return false;
- case scCouldNotCompute:
- llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
- return false;
- default: break;
- }
- llvm_unreachable("Unknown SCEV kind!");
- return false;
+ return getLoopDisposition(S, L) == LoopComputable;
+}
+
+ScalarEvolution::BlockDisposition
+ScalarEvolution::getBlockDisposition(const SCEV *S, const BasicBlock *BB) {
+ std::map<const BasicBlock *, BlockDisposition> &Values = BlockDispositions[S];
+ std::pair<std::map<const BasicBlock *, BlockDisposition>::iterator, bool>
+ Pair = Values.insert(std::make_pair(BB, DoesNotDominateBlock));
+ if (!Pair.second)
+ return Pair.first->second;
+
+ BlockDisposition D = computeBlockDisposition(S, BB);
+ return BlockDispositions[S][BB] = D;
}
-bool ScalarEvolution::dominates(const SCEV *S, BasicBlock *BB) const {
+ScalarEvolution::BlockDisposition
+ScalarEvolution::computeBlockDisposition(const SCEV *S, const BasicBlock *BB) {
switch (S->getSCEVType()) {
case scConstant:
- return true;
+ return ProperlyDominatesBlock;
case scTruncate:
case scZeroExtend:
case scSignExtend:
- return dominates(cast<SCEVCastExpr>(S)->getOperand(), BB);
+ return getBlockDisposition(cast<SCEVCastExpr>(S)->getOperand(), BB);
case scAddRecExpr: {
+ // This uses a "dominates" query instead of "properly dominates" query
+ // to test for proper dominance too, because the instruction which
+ // produces the addrec's value is a PHI, and a PHI effectively properly
+ // dominates its entire containing block.
const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(S);
if (!DT->dominates(AR->getLoop()->getHeader(), BB))
- return false;
+ return DoesNotDominateBlock;
}
// FALL THROUGH into SCEVNAryExpr handling.
case scAddExpr:
case scUMaxExpr:
case scSMaxExpr: {
const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(S);
+ bool Proper = true;
for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end();
- I != E; ++I)
- if (!dominates(*I, BB))
- return false;
- return true;
+ I != E; ++I) {
+ BlockDisposition D = getBlockDisposition(*I, BB);
+ if (D == DoesNotDominateBlock)
+ return DoesNotDominateBlock;
+ if (D == DominatesBlock)
+ Proper = false;
+ }
+ return Proper ? ProperlyDominatesBlock : DominatesBlock;
}
case scUDivExpr: {
const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S);
- return dominates(UDiv->getLHS(), BB) && dominates(UDiv->getRHS(), BB);
+ const SCEV *LHS = UDiv->getLHS(), *RHS = UDiv->getRHS();
+ BlockDisposition LD = getBlockDisposition(LHS, BB);
+ if (LD == DoesNotDominateBlock)
+ return DoesNotDominateBlock;
+ BlockDisposition RD = getBlockDisposition(RHS, BB);
+ if (RD == DoesNotDominateBlock)
+ return DoesNotDominateBlock;
+ return (LD == ProperlyDominatesBlock && RD == ProperlyDominatesBlock) ?
+ ProperlyDominatesBlock : DominatesBlock;
}
case scUnknown:
if (Instruction *I =
- dyn_cast<Instruction>(cast<SCEVUnknown>(S)->getValue()))
- return DT->dominates(I->getParent(), BB);
- return true;
+ dyn_cast<Instruction>(cast<SCEVUnknown>(S)->getValue())) {
+ if (I->getParent() == BB)
+ return DominatesBlock;
+ if (DT->properlyDominates(I->getParent(), BB))
+ return ProperlyDominatesBlock;
+ return DoesNotDominateBlock;
+ }
+ return ProperlyDominatesBlock;
case scCouldNotCompute:
llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
- return false;
+ return DoesNotDominateBlock;
default: break;
}
llvm_unreachable("Unknown SCEV kind!");
- return false;
+ return DoesNotDominateBlock;
}
-bool ScalarEvolution::properlyDominates(const SCEV *S, BasicBlock *BB) const {
+bool ScalarEvolution::dominates(const SCEV *S, const BasicBlock *BB) {
+ return getBlockDisposition(S, BB) >= DominatesBlock;
+}
+
+bool ScalarEvolution::properlyDominates(const SCEV *S, const BasicBlock *BB) {
+ return getBlockDisposition(S, BB) == ProperlyDominatesBlock;
+}
+
+bool ScalarEvolution::hasOperand(const SCEV *S, const SCEV *Op) const {
switch (S->getSCEVType()) {
case scConstant:
- return true;
+ return false;
case scTruncate:
case scZeroExtend:
- case scSignExtend:
- return properlyDominates(cast<SCEVCastExpr>(S)->getOperand(), BB);
- case scAddRecExpr: {
- // This uses a "dominates" query instead of "properly dominates" query
- // because the instruction which produces the addrec's value is a PHI, and
- // a PHI effectively properly dominates its entire containing block.
- const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(S);
- if (!DT->dominates(AR->getLoop()->getHeader(), BB))
- return false;
+ case scSignExtend: {
+ const SCEVCastExpr *Cast = cast<SCEVCastExpr>(S);
+ const SCEV *CastOp = Cast->getOperand();
+ return Op == CastOp || hasOperand(CastOp, Op);
}
- // FALL THROUGH into SCEVNAryExpr handling.
+ case scAddRecExpr:
case scAddExpr:
case scMulExpr:
case scUMaxExpr:
case scSMaxExpr: {
const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(S);
for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end();
- I != E; ++I)
- if (!properlyDominates(*I, BB))
- return false;
- return true;
+ I != E; ++I) {
+ const SCEV *NAryOp = *I;
+ if (NAryOp == Op || hasOperand(NAryOp, Op))
+ return true;
+ }
+ return false;
}
case scUDivExpr: {
const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S);
- return properlyDominates(UDiv->getLHS(), BB) &&
- properlyDominates(UDiv->getRHS(), BB);
+ const SCEV *LHS = UDiv->getLHS(), *RHS = UDiv->getRHS();
+ return LHS == Op || hasOperand(LHS, Op) ||
+ RHS == Op || hasOperand(RHS, Op);
}
case scUnknown:
- if (Instruction *I =
- dyn_cast<Instruction>(cast<SCEVUnknown>(S)->getValue()))
- return DT->properlyDominates(I->getParent(), BB);
- return true;
+ return false;
case scCouldNotCompute:
llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
return false;
llvm_unreachable("Unknown SCEV kind!");
return false;
}
+
+void ScalarEvolution::forgetMemoizedResults(const SCEV *S) {
+ ValuesAtScopes.erase(S);
+ LoopDispositions.erase(S);
+ BlockDispositions.erase(S);
+ UnsignedRanges.erase(S);
+ SignedRanges.erase(S);
+}
projects / oota-llvm.git / blobdiff