// 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
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/GlobalVariable.h"
+#include "llvm/GlobalAlias.h"
#include "llvm/Instructions.h"
#include "llvm/LLVMContext.h"
#include "llvm/Operator.h"
errs() << '\n';
}
-void SCEV::print(std::ostream &o) const {
- raw_os_ostream OS(o);
- print(OS);
-}
-
bool SCEV::isZero() const {
if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(this))
return SC->getValue()->isZero();
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(Context->getConstantInt(Val));
+ return getConstant(ConstantInt::get(getContext(), Val));
}
const SCEV *
ScalarEvolution::getConstant(const Type *Ty, uint64_t V, bool isSigned) {
return getConstant(
- Context->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)
OS << "}<" << L->getHeader()->getName() + ">";
}
+void SCEVFieldOffsetExpr::print(raw_ostream &OS) const {
+ // LLVM struct fields don't have names, so just print the field number.
+ OS << "offsetof(" << *STy << ", " << FieldNo << ")";
+}
+
+void SCEVAllocSizeExpr::print(raw_ostream &OS) const {
+ OS << "sizeof(" << *AllocTy << ")";
+}
+
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.
// SCEV Utilities
//===----------------------------------------------------------------------===//
+static bool CompareTypes(const Type *A, const Type *B) {
+ if (A->getTypeID() != B->getTypeID())
+ return A->getTypeID() < B->getTypeID();
+ if (const IntegerType *AI = dyn_cast<IntegerType>(A)) {
+ const IntegerType *BI = cast<IntegerType>(B);
+ return AI->getBitWidth() < BI->getBitWidth();
+ }
+ if (const PointerType *AI = dyn_cast<PointerType>(A)) {
+ const PointerType *BI = cast<PointerType>(B);
+ return CompareTypes(AI->getElementType(), BI->getElementType());
+ }
+ if (const ArrayType *AI = dyn_cast<ArrayType>(A)) {
+ const ArrayType *BI = cast<ArrayType>(B);
+ if (AI->getNumElements() != BI->getNumElements())
+ return AI->getNumElements() < BI->getNumElements();
+ return CompareTypes(AI->getElementType(), BI->getElementType());
+ }
+ if (const VectorType *AI = dyn_cast<VectorType>(A)) {
+ const VectorType *BI = cast<VectorType>(B);
+ if (AI->getNumElements() != BI->getNumElements())
+ return AI->getNumElements() < BI->getNumElements();
+ return CompareTypes(AI->getElementType(), BI->getElementType());
+ }
+ if (const StructType *AI = dyn_cast<StructType>(A)) {
+ const StructType *BI = cast<StructType>(B);
+ if (AI->getNumElements() != BI->getNumElements())
+ return AI->getNumElements() < BI->getNumElements();
+ for (unsigned i = 0, e = AI->getNumElements(); i != e; ++i)
+ if (CompareTypes(AI->getElementType(i), BI->getElementType(i)) ||
+ CompareTypes(BI->getElementType(i), AI->getElementType(i)))
+ return CompareTypes(AI->getElementType(i), BI->getElementType(i));
+ }
+ return false;
+}
+
namespace {
/// SCEVComplexityCompare - Return true if the complexity of the LHS is less
/// than the complexity of the RHS. This comparator is used to canonicalize
explicit SCEVComplexityCompare(LoopInfo *li) : LI(li) {}
bool operator()(const SCEV *LHS, const SCEV *RHS) const {
+ // Fast-path: SCEVs are uniqued so we can do a quick equality check.
+ if (LHS == RHS)
+ return false;
+
// Primarily, sort the SCEVs by their getSCEVType().
if (LHS->getSCEVType() != RHS->getSCEVType())
return LHS->getSCEVType() < RHS->getSCEVType();
return operator()(LC->getOperand(), RC->getOperand());
}
+ // Compare offsetof expressions.
+ if (const SCEVFieldOffsetExpr *LA = dyn_cast<SCEVFieldOffsetExpr>(LHS)) {
+ const SCEVFieldOffsetExpr *RA = cast<SCEVFieldOffsetExpr>(RHS);
+ if (CompareTypes(LA->getStructType(), RA->getStructType()) ||
+ CompareTypes(RA->getStructType(), LA->getStructType()))
+ return CompareTypes(LA->getStructType(), RA->getStructType());
+ return LA->getFieldNo() < RA->getFieldNo();
+ }
+
+ // Compare sizeof expressions by the allocation type.
+ if (const SCEVAllocSizeExpr *LA = dyn_cast<SCEVAllocSizeExpr>(LHS)) {
+ const SCEVAllocSizeExpr *RA = cast<SCEVAllocSizeExpr>(RHS);
+ return CompareTypes(LA->getAllocType(), RA->getAllocType());
+ }
+
llvm_unreachable("Unknown SCEV kind!");
return false;
}
MultiplyFactor = MultiplyFactor.trunc(W);
// Calculate the product, at width T+W
- const IntegerType *CalculationTy = IntegerType::get(CalculationBits);
+ const IntegerType *CalculationTy = IntegerType::get(SE.getContext(),
+ CalculationBits);
const SCEV *Dividend = SE.getTruncateOrZeroExtend(It, CalculationTy);
for (unsigned i = 1; i != K; ++i) {
const SCEV *S = SE.getMinusSCEV(It, SE.getIntegerSCEV(i, It->getType()));
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->hasNoUnsignedWrap())
+ 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
const SCEV *RecastedMaxBECount =
getTruncateOrZeroExtend(CastedMaxBECount, MaxBECount->getType());
if (MaxBECount == RecastedMaxBECount) {
- const Type *WideTy = IntegerType::get(BitWidth * 2);
+ const Type *WideTy = IntegerType::get(getContext(), BitWidth * 2);
// Check whether Start+Step*MaxBECount has no unsigned overflow.
const SCEV *ZMul =
getMulExpr(CastedMaxBECount,
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->hasNoSignedWrap())
+ 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
const SCEV *RecastedMaxBECount =
getTruncateOrZeroExtend(CastedMaxBECount, MaxBECount->getType());
if (MaxBECount == RecastedMaxBECount) {
- const Type *WideTy = IntegerType::get(BitWidth * 2);
+ const Type *WideTy = IntegerType::get(getContext(), BitWidth * 2);
// Check whether Start+Step*MaxBECount has no signed overflow.
const SCEV *SMul =
getMulExpr(CastedMaxBECount,
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),
/// unspecified bits out to the given type.
///
const SCEV *ScalarEvolution::getAnyExtendExpr(const SCEV *Op,
- const Type *Ty) {
+ const Type *Ty) {
assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
"This is not an extending conversion!");
assert(isSCEVable(Ty) &&
++Idx;
while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
// We found two constants, fold them together!
- ConstantInt *Fold = Context->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 *RHSC = dyn_cast<SCEVConstant>(RHS)) {
if (RHSC->getValue()->equalsInt(1))
- return LHS; // X udiv 1 --> x
+ return LHS; // X udiv 1 --> x
if (RHSC->isZero())
return getIntegerSCEV(0, LHS->getType()); // value is undefined
if (!RHSC->getValue()->getValue().isPowerOf2())
++MaxShiftAmt;
const IntegerType *ExtTy =
- IntegerType::get(getTypeSizeInBits(Ty) + MaxShiftAmt);
+ IntegerType::get(getContext(), getTypeSizeInBits(Ty) + MaxShiftAmt);
// {X,+,N}/C --> {X/C,+,N/C} if safe and N/C can be folded.
if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHS))
if (const SCEVConstant *Step =
if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
Constant *LHSCV = LHSC->getValue();
Constant *RHSCV = RHSC->getValue();
- return getConstant(cast<ConstantInt>(Context->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 = Context->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 = Context->getConstantInt(
+ ConstantInt *Fold = ConstantInt::get(getContext(),
APIntOps::umax(LHSC->getValue()->getValue(),
RHSC->getValue()->getValue()));
Ops[0] = getConstant(Fold);
return getNotSCEV(getUMaxExpr(getNotSCEV(LHS), getNotSCEV(RHS)));
}
+const SCEV *ScalarEvolution::getFieldOffsetExpr(const StructType *STy,
+ unsigned FieldNo) {
+ // If we have TargetData we can determine the constant offset.
+ if (TD) {
+ const Type *IntPtrTy = TD->getIntPtrType(getContext());
+ const StructLayout &SL = *TD->getStructLayout(STy);
+ uint64_t Offset = SL.getElementOffset(FieldNo);
+ return getIntegerSCEV(Offset, IntPtrTy);
+ }
+
+ // Field 0 is always at offset 0.
+ if (FieldNo == 0) {
+ const Type *Ty = getEffectiveSCEVType(PointerType::getUnqual(STy));
+ return getIntegerSCEV(0, Ty);
+ }
+
+ // Okay, it looks like we really DO need an offsetof expr. Check to see if we
+ // already have one, otherwise create a new one.
+ FoldingSetNodeID ID;
+ ID.AddInteger(scFieldOffset);
+ ID.AddPointer(STy);
+ ID.AddInteger(FieldNo);
+ void *IP = 0;
+ if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+ SCEV *S = SCEVAllocator.Allocate<SCEVFieldOffsetExpr>();
+ const Type *Ty = getEffectiveSCEVType(PointerType::getUnqual(STy));
+ new (S) SCEVFieldOffsetExpr(ID, Ty, STy, FieldNo);
+ UniqueSCEVs.InsertNode(S, IP);
+ return S;
+}
+
+const SCEV *ScalarEvolution::getAllocSizeExpr(const Type *AllocTy) {
+ // If we have TargetData we can determine the constant size.
+ if (TD && AllocTy->isSized()) {
+ const Type *IntPtrTy = TD->getIntPtrType(getContext());
+ return getIntegerSCEV(TD->getTypeAllocSize(AllocTy), IntPtrTy);
+ }
+
+ // Expand an array size into the element size times the number
+ // of elements.
+ if (const ArrayType *ATy = dyn_cast<ArrayType>(AllocTy)) {
+ const SCEV *E = getAllocSizeExpr(ATy->getElementType());
+ return getMulExpr(
+ E, getConstant(ConstantInt::get(cast<IntegerType>(E->getType()),
+ ATy->getNumElements())));
+ }
+
+ // Expand a vector size into the element size times the number
+ // of elements.
+ if (const VectorType *VTy = dyn_cast<VectorType>(AllocTy)) {
+ const SCEV *E = getAllocSizeExpr(VTy->getElementType());
+ return getMulExpr(
+ E, getConstant(ConstantInt::get(cast<IntegerType>(E->getType()),
+ VTy->getNumElements())));
+ }
+
+ // Okay, it looks like we really DO need a sizeof expr. Check to see if we
+ // already have one, otherwise create a new one.
+ FoldingSetNodeID ID;
+ ID.AddInteger(scAllocSize);
+ ID.AddPointer(AllocTy);
+ void *IP = 0;
+ if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+ SCEV *S = SCEVAllocator.Allocate<SCEVAllocSizeExpr>();
+ const Type *Ty = getEffectiveSCEVType(PointerType::getUnqual(AllocTy));
+ new (S) SCEVAllocSizeExpr(ID, Ty, AllocTy);
+ UniqueSCEVs.InsertNode(S, IP);
+ return S;
+}
+
const SCEV *ScalarEvolution::getUnknown(Value *V) {
// Don't attempt to do anything other than create a SCEVUnknown object
// here. createSCEV only calls getUnknown after checking for all other
/// can optionally include pointer types if the ScalarEvolution class
/// has access to target-specific information.
bool ScalarEvolution::isSCEVable(const Type *Ty) const {
- // Integers are always SCEVable.
- if (Ty->isInteger())
- return true;
-
- // Pointers are SCEVable if TargetData information is available
- // to provide pointer size information.
- if (isa<PointerType>(Ty))
- return TD != NULL;
-
- // Otherwise it's not SCEVable.
- return false;
+ // Integers and pointers are always SCEVable.
+ return Ty->isInteger() || isa<PointerType>(Ty);
}
/// getTypeSizeInBits - Return the size in bits of the specified type,
if (TD)
return TD->getTypeSizeInBits(Ty);
- // Otherwise, we support only integer types.
- assert(Ty->isInteger() && "isSCEVable permitted a non-SCEVable type!");
- return Ty->getPrimitiveSizeInBits();
+ // Integer types have fixed sizes.
+ if (Ty->isInteger())
+ return Ty->getPrimitiveSizeInBits();
+
+ // The only other support type is pointer. Without TargetData, conservatively
+ // assume pointers are 64-bit.
+ assert(isa<PointerType>(Ty) && "isSCEVable permitted a non-SCEVable type!");
+ return 64;
}
/// getEffectiveSCEVType - Return a type with the same bitwidth as
if (Ty->isInteger())
return Ty;
+ // The only other support type is pointer.
assert(isa<PointerType>(Ty) && "Unexpected non-pointer non-integer type!");
- return TD->getIntPtrType();
+ if (TD) return TD->getIntPtrType(getContext());
+
+ // Without TargetData, conservatively assume pointers are 64-bit.
+ return Type::getInt64Ty(getContext());
}
const SCEV *ScalarEvolution::getCouldNotCompute() {
/// 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(Context->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>(Context->getConstantExprNeg(VC->getValue())));
+ cast<ConstantInt>(ConstantExpr::getNeg(VC->getValue())));
const Type *Ty = V->getType();
Ty = getEffectiveSCEVType(Ty);
return getMulExpr(V,
- getConstant(cast<ConstantInt>(Context->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>(Context->getConstantExprNot(VC->getValue())));
+ cast<ConstantInt>(ConstantExpr::getNot(VC->getValue())));
const Type *Ty = V->getType();
Ty = getEffectiveSCEVType(Ty);
const SCEV *AllOnes =
- getConstant(cast<ConstantInt>(Context->getAllOnesValue(Ty)));
+ getConstant(cast<ConstantInt>(Constant::getAllOnesValue(Ty)));
return getMinusSCEV(AllOnes, V);
}
ScalarEvolution::getTruncateOrZeroExtend(const SCEV *V,
const Type *Ty) {
const Type *SrcTy = V->getType();
- assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) &&
- (Ty->isInteger() || (TD && isa<PointerType>(Ty))) &&
+ assert((SrcTy->isInteger() || isa<PointerType>(SrcTy)) &&
+ (Ty->isInteger() || isa<PointerType>(Ty)) &&
"Cannot truncate or zero extend with non-integer arguments!");
if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
return V; // No conversion
ScalarEvolution::getTruncateOrSignExtend(const SCEV *V,
const Type *Ty) {
const Type *SrcTy = V->getType();
- assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) &&
- (Ty->isInteger() || (TD && isa<PointerType>(Ty))) &&
+ assert((SrcTy->isInteger() || isa<PointerType>(SrcTy)) &&
+ (Ty->isInteger() || isa<PointerType>(Ty)) &&
"Cannot truncate or zero extend with non-integer arguments!");
if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
return V; // No conversion
const SCEV *
ScalarEvolution::getNoopOrZeroExtend(const SCEV *V, const Type *Ty) {
const Type *SrcTy = V->getType();
- assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) &&
- (Ty->isInteger() || (TD && isa<PointerType>(Ty))) &&
+ assert((SrcTy->isInteger() || isa<PointerType>(SrcTy)) &&
+ (Ty->isInteger() || isa<PointerType>(Ty)) &&
"Cannot noop or zero extend with non-integer arguments!");
assert(getTypeSizeInBits(SrcTy) <= getTypeSizeInBits(Ty) &&
"getNoopOrZeroExtend cannot truncate!");
const SCEV *
ScalarEvolution::getNoopOrSignExtend(const SCEV *V, const Type *Ty) {
const Type *SrcTy = V->getType();
- assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) &&
- (Ty->isInteger() || (TD && isa<PointerType>(Ty))) &&
+ assert((SrcTy->isInteger() || isa<PointerType>(SrcTy)) &&
+ (Ty->isInteger() || isa<PointerType>(Ty)) &&
"Cannot noop or sign extend with non-integer arguments!");
assert(getTypeSizeInBits(SrcTy) <= getTypeSizeInBits(Ty) &&
"getNoopOrSignExtend cannot truncate!");
const SCEV *
ScalarEvolution::getNoopOrAnyExtend(const SCEV *V, const Type *Ty) {
const Type *SrcTy = V->getType();
- assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) &&
- (Ty->isInteger() || (TD && isa<PointerType>(Ty))) &&
+ assert((SrcTy->isInteger() || isa<PointerType>(SrcTy)) &&
+ (Ty->isInteger() || isa<PointerType>(Ty)) &&
"Cannot noop or any extend with non-integer arguments!");
assert(getTypeSizeInBits(SrcTy) <= getTypeSizeInBits(Ty) &&
"getNoopOrAnyExtend cannot truncate!");
const SCEV *
ScalarEvolution::getTruncateOrNoop(const SCEV *V, const Type *Ty) {
const Type *SrcTy = V->getType();
- assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) &&
- (Ty->isInteger() || (TD && isa<PointerType>(Ty))) &&
+ assert((SrcTy->isInteger() || isa<PointerType>(SrcTy)) &&
+ (Ty->isInteger() || isa<PointerType>(Ty)) &&
"Cannot truncate or noop with non-integer arguments!");
assert(getTypeSizeInBits(SrcTy) >= getTypeSizeInBits(Ty) &&
"getTruncateOrNoop cannot extend!");
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)) {
+ ValuesAtScopes.erase(It->second);
+ Scalars.erase(It);
+ }
+ }
- // 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->hasNoUnsignedWrap()) {
+ const_cast<SCEVAddRecExpr *>(PHISCEV)
+ ->setHasNoUnsignedWrap(true);
+ const_cast<SCEVAddRecExpr *>(PostInc)
+ ->setHasNoUnsignedWrap(true);
+ }
+ if (OBO->hasNoSignedWrap()) {
+ const_cast<SCEVAddRecExpr *>(PHISCEV)
+ ->setHasNoSignedWrap(true);
+ const_cast<SCEVAddRecExpr *>(PostInc)
+ ->setHasNoSignedWrap(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;
}
}
///
const SCEV *ScalarEvolution::createNodeForGEP(Operator *GEP) {
- const Type *IntPtrTy = TD->getIntPtrType();
+ const Type *IntPtrTy = getEffectiveSCEVType(GEP->getType());
Value *Base = GEP->getOperand(0);
// Don't attempt to analyze GEPs over unsized objects.
if (!cast<PointerType>(Base->getType())->getElementType()->isSized())
// Compute the (potentially symbolic) offset in bytes for this index.
if (const StructType *STy = dyn_cast<StructType>(*GTI++)) {
// For a struct, add the member offset.
- const StructLayout &SL = *TD->getStructLayout(STy);
unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue();
- uint64_t Offset = SL.getElementOffset(FieldNo);
- TotalOffset = getAddExpr(TotalOffset, getIntegerSCEV(Offset, IntPtrTy));
+ TotalOffset = getAddExpr(TotalOffset,
+ getFieldOffsetExpr(STy, FieldNo));
} else {
// For an array, add the element offset, explicitly scaled.
const SCEV *LocalOffset = getSCEV(Index);
if (!isa<PointerType>(LocalOffset->getType()))
// Getelementptr indicies are signed.
LocalOffset = getTruncateOrSignExtend(LocalOffset, IntPtrTy);
- LocalOffset =
- getMulExpr(LocalOffset,
- getIntegerSCEV(TD->getTypeAllocSize(*GTI), IntPtrTy));
+ LocalOffset = getMulExpr(LocalOffset, getAllocSizeExpr(*GTI));
TotalOffset = getAddExpr(TotalOffset, LocalOffset);
}
}
return getIntegerSCEV(0, V->getType());
else if (isa<UndefValue>(V))
return getIntegerSCEV(0, V->getType());
+ else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V))
+ return GA->mayBeOverridden() ? getUnknown(V) : getSCEV(GA->getAliasee());
else
return getUnknown(V);
if (LZ != 0 && !((~A & ~KnownZero) & EffectiveMask))
return
getZeroExtendExpr(getTruncateExpr(getSCEV(U->getOperand(0)),
- IntegerType::get(BitWidth - LZ)),
+ IntegerType::get(getContext(), BitWidth - LZ)),
U->getType());
}
break;
// 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 = Context->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 = Context->getConstantInt(
+ Constant *X = ConstantInt::get(getContext(),
APInt(BitWidth, 1).shl(SA->getLimitedValue(BitWidth)));
return getUDivExpr(getSCEV(U->getOperand(0)), getSCEV(X));
}
return getIntegerSCEV(0, U->getType()); // value is undefined
return
getSignExtendExpr(getTruncateExpr(getSCEV(L->getOperand(0)),
- IntegerType::get(Amt)),
+ IntegerType::get(getContext(), Amt)),
U->getType());
}
break;
// expressions we handle are GEPs and address literals.
case Instruction::GetElementPtr:
- if (!TD) break; // Without TD we can't analyze pointers.
return createNodeForGEP(U);
case Instruction::PHI:
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
// 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))
+ if (!isa<PHINode>(I) || !isa<SCEVUnknown>(It->second)) {
+ ValuesAtScopes.erase(It->second);
Scalars.erase(It);
- ValuesAtScopes.erase(I);
+ }
if (PHINode *PN = dyn_cast<PHINode>(I))
ConstantEvolutionLoopExitValue.erase(PN);
}
std::map<SCEVCallbackVH, const SCEV*>::iterator It =
Scalars.find(static_cast<Value *>(I));
if (It != Scalars.end()) {
+ ValuesAtScopes.erase(It->second);
Scalars.erase(It);
- ValuesAtScopes.erase(I);
if (PHINode *PN = dyn_cast<PHINode>(I))
ConstantEvolutionLoopExitValue.erase(PN);
}
if (!isa<SCEVCouldNotCompute>(TC)) return TC;
break;
}
- case ICmpInst::ICMP_EQ: {
- // Convert to: while (X-Y == 0) // while (X == Y)
+ case ICmpInst::ICMP_EQ: { // while (X == Y)
+ // Convert to: while (X-Y == 0)
const SCEV *TC = HowFarToNonZero(getMinusSCEV(LHS, RHS), L);
if (!isa<SCEVCouldNotCompute>(TC)) return TC;
break;
/// the addressed element of the initializer or null if the index expression is
/// invalid.
static Constant *
-GetAddressedElementFromGlobal(LLVMContext *Context, GlobalVariable *GV,
+GetAddressedElementFromGlobal(LLVMContext &Context, GlobalVariable *GV,
const std::vector<ConstantInt*> &Indices) {
Constant *Init = GV->getInitializer();
for (unsigned i = 0, e = Indices.size(); i != e; ++i) {
} 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!");
}
// Make sure that it is really a constant global we are gepping, with an
// initializer, and make sure the first IDX is really 0.
GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0));
- if (!GV || !GV->isConstant() || !GV->hasInitializer() ||
+ if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer() ||
GEP->getNumOperands() < 3 || !isa<Constant>(GEP->getOperand(1)) ||
!cast<Constant>(GEP->getOperand(1))->isNullValue())
return getCouldNotCompute();
unsigned MaxSteps = MaxBruteForceIterations;
for (unsigned IterationNum = 0; IterationNum != MaxSteps; ++IterationNum) {
- ConstantInt *ItCst = Context->getConstantInt(
+ ConstantInt *ItCst = ConstantInt::get(
cast<IntegerType>(IdxExpr->getType()), IterationNum);
ConstantInt *Val = EvaluateConstantChrecAtConstant(IdxExpr, ItCst, *this);
// Form the GEP offset.
Indexes[VarIdxNum] = Val;
- Constant *Result = GetAddressedElementFromGlobal(Context, GV, Indexes);
+ Constant *Result = GetAddressedElementFromGlobal(getContext(), GV, Indexes);
if (Result == 0) break; // Cannot compute!
// Evaluate the condition for this iteration.
if (Constant *C = dyn_cast<Constant>(V)) return C;
if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) return GV;
Instruction *I = cast<Instruction>(V);
- LLVMContext *Context = I->getParent()->getContext();
+ LLVMContext &Context = I->getParent()->getContext();
std::vector<Constant*> Operands;
Operands.resize(I->getNumOperands());
}
}
-/// 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
if (CondVal->getValue() == uint64_t(ExitWhen)) {
++NumBruteForceTripCountsComputed;
- return getConstant(Type::Int32Ty, IterationNum);
+ return getConstant(Type::getInt32Ty(getContext()), IterationNum);
}
// Compute the value of the PHI node for the next iteration.
/// In the case that a relevant loop exit value cannot be computed, the
/// original value V is returned.
const SCEV *ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) {
- // FIXME: this should be turned into a virtual method on SCEV!
+ // Check to see if we've folded this expression at this loop before.
+ std::map<const Loop *, const SCEV *> &Values = ValuesAtScopes[V];
+ std::pair<std::map<const Loop *, const SCEV *>::iterator, bool> Pair =
+ Values.insert(std::make_pair(L, static_cast<const SCEV *>(0)));
+ if (!Pair.second)
+ return Pair.first->second ? Pair.first->second : V;
+
+ // Otherwise compute it.
+ const SCEV *C = computeSCEVAtScope(V, L);
+ Pair.first->second = C;
+ return C;
+}
+const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) {
if (isa<SCEVConstant>(V)) return V;
// If this instruction is evolved from a constant-evolving PHI, compute the
// the arguments into constants, and if so, try to constant propagate the
// result. This is particularly useful for computing loop exit values.
if (CanConstantFold(I)) {
- // Check to see if we've folded this instruction at this loop before.
- std::map<const Loop *, Constant *> &Values = ValuesAtScopes[I];
- 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 ? &*getSCEV(Pair.first->second) : V;
-
std::vector<Constant*> Operands;
Operands.reserve(I->getNumOperands());
for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
if (const CmpInst *CI = dyn_cast<CmpInst>(I))
C = ConstantFoldCompareInstOperands(CI->getPredicate(),
&Operands[0], Operands.size(),
- Context);
+ getContext());
else
C = ConstantFoldInstOperands(I->getOpcode(), I->getType(),
- &Operands[0], Operands.size(), Context);
- Pair.first->second = C;
+ &Operands[0], Operands.size(),
+ getContext());
return getSCEV(C);
}
}
return getTruncateExpr(Op, Cast->getType());
}
+ if (isa<SCEVTargetDataConstant>(V))
+ return V;
+
llvm_unreachable("Unknown SCEV type!");
return 0;
}
return std::make_pair(CNC, CNC);
}
- LLVMContext *Context = SE.getContext();
+ 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));
// First, handle unitary steps.
if (StepC->getValue()->equalsInt(1)) // 1*N = -Start (mod 2^BW), so:
- return getNegativeSCEV(Start); // N = -Start (as unsigned)
+ return getNegativeSCEV(Start); // N = -Start (as unsigned)
if (StepC->getValue()->isAllOnesValue()) // -1*N = -Start (mod 2^BW), so:
return Start; // N = Start (as unsigned)
#endif
// Pick the smallest positive root value.
if (ConstantInt *CB =
- dyn_cast<ConstantInt>(Context->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 (const SCEVUnknown *BU = dyn_cast<SCEVUnknown>(B))
if (const Instruction *AI = dyn_cast<Instruction>(AU->getValue()))
if (const Instruction *BI = dyn_cast<Instruction>(BU->getValue()))
- if (AI->isIdenticalTo(BI))
+ if (AI->isIdenticalTo(BI) && !AI->mayReadFromMemory())
return true;
// Otherwise assume they may have a different value.
LoopContinuePredicate->isUnconditional())
return false;
- return
- isNecessaryCond(LoopContinuePredicate->getCondition(), Pred, LHS, RHS,
- LoopContinuePredicate->getSuccessor(0) != L->getHeader());
+ return isImpliedCond(LoopContinuePredicate->getCondition(), Pred, LHS, RHS,
+ LoopContinuePredicate->getSuccessor(0) != L->getHeader());
}
/// isLoopGuardedByCond - Test whether entry to the loop is protected
LoopEntryPredicate->isUnconditional())
continue;
- if (isNecessaryCond(LoopEntryPredicate->getCondition(), Pred, LHS, RHS,
- LoopEntryPredicate->getSuccessor(0) != PredecessorDest))
+ if (isImpliedCond(LoopEntryPredicate->getCondition(), Pred, LHS, RHS,
+ LoopEntryPredicate->getSuccessor(0) != PredecessorDest))
return true;
}
return false;
}
-/// isNecessaryCond - Test whether the condition described by Pred, LHS,
-/// and RHS is a necessary condition for the given Cond value to evaluate
-/// to true.
-bool ScalarEvolution::isNecessaryCond(Value *CondValue,
- ICmpInst::Predicate Pred,
- const SCEV *LHS, const SCEV *RHS,
- bool Inverse) {
+/// isImpliedCond - Test whether the condition described by Pred, LHS,
+/// and RHS is true whenever the given Cond value evaluates to true.
+bool ScalarEvolution::isImpliedCond(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);
+ return isImpliedCond(BO->getOperand(0), Pred, LHS, RHS, Inverse) ||
+ isImpliedCond(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);
+ return isImpliedCond(BO->getOperand(0), Pred, LHS, RHS, Inverse) ||
+ isImpliedCond(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 FoundPred;
- if (Inverse)
- FoundPred = ICI->getInversePredicate();
- else
- FoundPred = ICI->getPredicate();
-
- if (FoundPred == Pred)
- ; // An exact match.
- else if (!ICmpInst::isTrueWhenEqual(FoundPred) && Pred == ICmpInst::ICMP_NE) {
- // The actual condition is beyond sufficient.
- FoundPred = 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);
- } else
- // Check a few special cases.
- switch (FoundPred) {
- case ICmpInst::ICMP_UGT:
- if (Pred == ICmpInst::ICMP_ULT) {
- std::swap(PreCondLHS, PreCondRHS);
- FoundPred = ICmpInst::ICMP_ULT;
- break;
- }
- return false;
- case ICmpInst::ICMP_SGT:
- if (Pred == ICmpInst::ICMP_SLT) {
- std::swap(PreCondLHS, PreCondRHS);
- FoundPred = 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 (const SCEVConstant *C = dyn_cast<SCEVConstant>(RHS)) {
- const APInt &A = C->getValue()->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;
- }
- FoundPred = Pred;
- // 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;
- }
- return false;
- default:
- // We weren't able to reconcile the condition.
- return false;
- }
-
- assert(Pred == FoundPred && "Conditions were not reconciled!");
-
// Bail if the ICmp's operands' types are wider than the needed type
// before attempting to call getSCEV on them. This avoids infinite
// recursion, since the analysis of widening casts can require loop
// exit condition information for overflow checking, which would
// lead back here.
if (getTypeSizeInBits(LHS->getType()) <
- getTypeSizeInBits(PreCondLHS->getType()))
+ getTypeSizeInBits(ICI->getOperand(0)->getType()))
return false;
- const SCEV *FoundLHS = getSCEV(PreCondLHS);
- const SCEV *FoundRHS = getSCEV(PreCondRHS);
+ // Now that we found a conditional branch that dominates the loop, check to
+ // see if it is the comparison we are looking for.
+ ICmpInst::Predicate FoundPred;
+ if (Inverse)
+ FoundPred = ICI->getInversePredicate();
+ else
+ FoundPred = ICI->getPredicate();
+
+ const SCEV *FoundLHS = getSCEV(ICI->getOperand(0));
+ const SCEV *FoundRHS = getSCEV(ICI->getOperand(1));
// Balance the types. The case where FoundLHS' type is wider than
// LHS' type is checked for above.
}
}
- return isNecessaryCondOperands(Pred, LHS, RHS,
- FoundLHS, FoundRHS) ||
+ // Canonicalize the query to match the way instcombine will have
+ // canonicalized the comparison.
+ // First, put a constant operand on the right.
+ if (isa<SCEVConstant>(LHS)) {
+ std::swap(LHS, RHS);
+ Pred = ICmpInst::getSwappedPredicate(Pred);
+ }
+ // Then, canonicalize comparisons with boundary cases.
+ if (const SCEVConstant *RC = dyn_cast<SCEVConstant>(RHS)) {
+ const APInt &RA = RC->getValue()->getValue();
+ switch (Pred) {
+ default: llvm_unreachable("Unexpected ICmpInst::Predicate value!");
+ case ICmpInst::ICMP_EQ:
+ case ICmpInst::ICMP_NE:
+ break;
+ case ICmpInst::ICMP_UGE:
+ if ((RA - 1).isMinValue()) {
+ Pred = ICmpInst::ICMP_NE;
+ RHS = getConstant(RA - 1);
+ break;
+ }
+ if (RA.isMaxValue()) {
+ Pred = ICmpInst::ICMP_EQ;
+ break;
+ }
+ if (RA.isMinValue()) return true;
+ break;
+ case ICmpInst::ICMP_ULE:
+ if ((RA + 1).isMaxValue()) {
+ Pred = ICmpInst::ICMP_NE;
+ RHS = getConstant(RA + 1);
+ break;
+ }
+ if (RA.isMinValue()) {
+ Pred = ICmpInst::ICMP_EQ;
+ break;
+ }
+ if (RA.isMaxValue()) return true;
+ break;
+ case ICmpInst::ICMP_SGE:
+ if ((RA - 1).isMinSignedValue()) {
+ Pred = ICmpInst::ICMP_NE;
+ RHS = getConstant(RA - 1);
+ break;
+ }
+ if (RA.isMaxSignedValue()) {
+ Pred = ICmpInst::ICMP_EQ;
+ break;
+ }
+ if (RA.isMinSignedValue()) return true;
+ break;
+ case ICmpInst::ICMP_SLE:
+ if ((RA + 1).isMaxSignedValue()) {
+ Pred = ICmpInst::ICMP_NE;
+ RHS = getConstant(RA + 1);
+ break;
+ }
+ if (RA.isMinSignedValue()) {
+ Pred = ICmpInst::ICMP_EQ;
+ break;
+ }
+ if (RA.isMaxSignedValue()) return true;
+ break;
+ case ICmpInst::ICMP_UGT:
+ if (RA.isMinValue()) {
+ Pred = ICmpInst::ICMP_NE;
+ break;
+ }
+ if ((RA + 1).isMaxValue()) {
+ Pred = ICmpInst::ICMP_EQ;
+ RHS = getConstant(RA + 1);
+ break;
+ }
+ if (RA.isMaxValue()) return false;
+ break;
+ case ICmpInst::ICMP_ULT:
+ if (RA.isMaxValue()) {
+ Pred = ICmpInst::ICMP_NE;
+ break;
+ }
+ if ((RA - 1).isMinValue()) {
+ Pred = ICmpInst::ICMP_EQ;
+ RHS = getConstant(RA - 1);
+ break;
+ }
+ if (RA.isMinValue()) return false;
+ break;
+ case ICmpInst::ICMP_SGT:
+ if (RA.isMinSignedValue()) {
+ Pred = ICmpInst::ICMP_NE;
+ break;
+ }
+ if ((RA + 1).isMaxSignedValue()) {
+ Pred = ICmpInst::ICMP_EQ;
+ RHS = getConstant(RA + 1);
+ break;
+ }
+ if (RA.isMaxSignedValue()) return false;
+ break;
+ case ICmpInst::ICMP_SLT:
+ if (RA.isMaxSignedValue()) {
+ Pred = ICmpInst::ICMP_NE;
+ break;
+ }
+ if ((RA - 1).isMinSignedValue()) {
+ Pred = ICmpInst::ICMP_EQ;
+ RHS = getConstant(RA - 1);
+ break;
+ }
+ if (RA.isMinSignedValue()) return false;
+ break;
+ }
+ }
+
+ // Check to see if we can make the LHS or RHS match.
+ if (LHS == FoundRHS || RHS == FoundLHS) {
+ if (isa<SCEVConstant>(RHS)) {
+ std::swap(FoundLHS, FoundRHS);
+ FoundPred = ICmpInst::getSwappedPredicate(FoundPred);
+ } else {
+ std::swap(LHS, RHS);
+ Pred = ICmpInst::getSwappedPredicate(Pred);
+ }
+ }
+
+ // Check whether the found predicate is the same as the desired predicate.
+ if (FoundPred == Pred)
+ return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS);
+
+ // Check whether swapping the found predicate makes it the same as the
+ // desired predicate.
+ if (ICmpInst::getSwappedPredicate(FoundPred) == Pred) {
+ if (isa<SCEVConstant>(RHS))
+ return isImpliedCondOperands(Pred, LHS, RHS, FoundRHS, FoundLHS);
+ else
+ return isImpliedCondOperands(ICmpInst::getSwappedPredicate(Pred),
+ RHS, LHS, FoundLHS, FoundRHS);
+ }
+
+ // Check whether the actual condition is beyond sufficient.
+ if (FoundPred == ICmpInst::ICMP_EQ)
+ if (ICmpInst::isTrueWhenEqual(Pred))
+ if (isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS))
+ return true;
+ if (Pred == ICmpInst::ICMP_NE)
+ if (!ICmpInst::isTrueWhenEqual(FoundPred))
+ if (isImpliedCondOperands(FoundPred, LHS, RHS, FoundLHS, FoundRHS))
+ return true;
+
+ // Otherwise assume the worst.
+ return false;
+}
+
+/// isImpliedCondOperands - Test whether the condition described by Pred,
+/// LHS, and RHS is true whenever the condition desribed by Pred, FoundLHS,
+/// and FoundRHS is true.
+bool ScalarEvolution::isImpliedCondOperands(ICmpInst::Predicate Pred,
+ const SCEV *LHS, const SCEV *RHS,
+ const SCEV *FoundLHS,
+ const SCEV *FoundRHS) {
+ return isImpliedCondOperandsHelper(Pred, LHS, RHS,
+ FoundLHS, FoundRHS) ||
// ~x < ~y --> x > y
- isNecessaryCondOperands(Pred, LHS, RHS,
- getNotSCEV(FoundRHS), getNotSCEV(FoundLHS));
+ isImpliedCondOperandsHelper(Pred, LHS, RHS,
+ getNotSCEV(FoundRHS),
+ getNotSCEV(FoundLHS));
}
-/// isNecessaryCondOperands - Test whether the condition described by Pred,
-/// LHS, and RHS is a necessary condition for the condition described by
-/// Pred, FoundLHS, and FoundRHS to evaluate to true.
+/// isImpliedCondOperandsHelper - Test whether the condition described by
+/// Pred, LHS, and RHS is true whenever the condition desribed by Pred,
+/// FoundLHS, and FoundRHS is true.
bool
-ScalarEvolution::isNecessaryCondOperands(ICmpInst::Predicate Pred,
- const SCEV *LHS, const SCEV *RHS,
- const SCEV *FoundLHS,
- const SCEV *FoundRHS) {
+ScalarEvolution::isImpliedCondOperandsHelper(ICmpInst::Predicate Pred,
+ const SCEV *LHS, const SCEV *RHS,
+ const SCEV *FoundLHS,
+ const SCEV *FoundRHS) {
switch (Pred) {
default: llvm_unreachable("Unexpected ICmpInst::Predicate value!");
case ICmpInst::ICMP_EQ:
// Check Add for unsigned overflow.
// TODO: More sophisticated things could be done here.
- const Type *WideTy = Context->getIntegerType(getTypeSizeInBits(Ty) + 1);
+ const Type *WideTy = IntegerType::get(getContext(),
+ 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;
assert(SE && "SCEVCallbackVH called with a null ScalarEvolution!");
if (PHINode *PN = dyn_cast<PHINode>(getValPtr()))
SE->ConstantEvolutionLoopExitValue.erase(PN);
- if (Instruction *I = dyn_cast<Instruction>(getValPtr()))
- SE->ValuesAtScopes.erase(I);
SE->Scalars.erase(getValPtr());
// this now dangles!
}
continue;
if (PHINode *PN = dyn_cast<PHINode>(U))
SE->ConstantEvolutionLoopExitValue.erase(PN);
- if (Instruction *I = dyn_cast<Instruction>(U))
- SE->ValuesAtScopes.erase(I);
SE->Scalars.erase(U);
for (Value::use_iterator UI = U->use_begin(), UE = U->use_end();
UI != UE; ++UI)
if (DeleteOld) {
if (PHINode *PN = dyn_cast<PHINode>(Old))
SE->ConstantEvolutionLoopExitValue.erase(PN);
- if (Instruction *I = dyn_cast<Instruction>(Old))
- SE->ValuesAtScopes.erase(I);
SE->Scalars.erase(Old);
// this now dangles!
}
PrintLoopInfo(OS, &SE, *I);
}
-void ScalarEvolution::print(std::ostream &o, const Module *M) const {
- raw_os_ostream OS(o);
- print(OS, M);
-}