+/// getUnsignedRange - Determine the unsigned range for a particular SCEV.
+///
+ConstantRange
+ScalarEvolution::getUnsignedRange(const SCEV *S) {
+
+ if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S))
+ return ConstantRange(C->getValue()->getValue());
+
+ unsigned BitWidth = getTypeSizeInBits(S->getType());
+ ConstantRange ConservativeResult(BitWidth, /*isFullSet=*/true);
+
+ // If the value has known zeros, the maximum unsigned value will have those
+ // known zeros as well.
+ uint32_t TZ = GetMinTrailingZeros(S);
+ if (TZ != 0)
+ ConservativeResult =
+ ConstantRange(APInt::getMinValue(BitWidth),
+ APInt::getMaxValue(BitWidth).lshr(TZ).shl(TZ) + 1);
+
+ if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
+ ConstantRange X = getUnsignedRange(Add->getOperand(0));
+ for (unsigned i = 1, e = Add->getNumOperands(); i != e; ++i)
+ X = X.add(getUnsignedRange(Add->getOperand(i)));
+ return ConservativeResult.intersectWith(X);
+ }
+
+ if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) {
+ ConstantRange X = getUnsignedRange(Mul->getOperand(0));
+ for (unsigned i = 1, e = Mul->getNumOperands(); i != e; ++i)
+ X = X.multiply(getUnsignedRange(Mul->getOperand(i)));
+ return ConservativeResult.intersectWith(X);
+ }
+
+ if (const SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(S)) {
+ ConstantRange X = getUnsignedRange(SMax->getOperand(0));
+ for (unsigned i = 1, e = SMax->getNumOperands(); i != e; ++i)
+ X = X.smax(getUnsignedRange(SMax->getOperand(i)));
+ return ConservativeResult.intersectWith(X);
+ }
+
+ if (const SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(S)) {
+ ConstantRange X = getUnsignedRange(UMax->getOperand(0));
+ for (unsigned i = 1, e = UMax->getNumOperands(); i != e; ++i)
+ X = X.umax(getUnsignedRange(UMax->getOperand(i)));
+ return ConservativeResult.intersectWith(X);
+ }
+
+ if (const SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(S)) {
+ ConstantRange X = getUnsignedRange(UDiv->getLHS());
+ ConstantRange Y = getUnsignedRange(UDiv->getRHS());
+ return ConservativeResult.intersectWith(X.udiv(Y));
+ }
+
+ if (const SCEVZeroExtendExpr *ZExt = dyn_cast<SCEVZeroExtendExpr>(S)) {
+ ConstantRange X = getUnsignedRange(ZExt->getOperand());
+ return ConservativeResult.intersectWith(X.zeroExtend(BitWidth));
+ }
+
+ if (const SCEVSignExtendExpr *SExt = dyn_cast<SCEVSignExtendExpr>(S)) {
+ ConstantRange X = getUnsignedRange(SExt->getOperand());
+ return ConservativeResult.intersectWith(X.signExtend(BitWidth));
+ }
+
+ if (const SCEVTruncateExpr *Trunc = dyn_cast<SCEVTruncateExpr>(S)) {
+ ConstantRange X = getUnsignedRange(Trunc->getOperand());
+ return ConservativeResult.intersectWith(X.truncate(BitWidth));
+ }
+
+ if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
+ // If there's no unsigned wrap, the value will never be less than its
+ // initial value.
+ if (AddRec->hasNoUnsignedWrap())
+ if (const SCEVConstant *C = dyn_cast<SCEVConstant>(AddRec->getStart()))
+ ConservativeResult =
+ ConstantRange(C->getValue()->getValue(),
+ APInt(getTypeSizeInBits(C->getType()), 0));
+
+ // TODO: non-affine addrec
+ if (AddRec->isAffine()) {
+ const Type *Ty = AddRec->getType();
+ const SCEV *MaxBECount = getMaxBackedgeTakenCount(AddRec->getLoop());
+ if (!isa<SCEVCouldNotCompute>(MaxBECount) &&
+ getTypeSizeInBits(MaxBECount->getType()) <= BitWidth) {
+ MaxBECount = getNoopOrZeroExtend(MaxBECount, Ty);
+
+ const SCEV *Start = AddRec->getStart();
+ const SCEV *End = AddRec->evaluateAtIteration(MaxBECount, *this);
+
+ // Check for overflow.
+ if (!AddRec->hasNoUnsignedWrap())
+ return ConservativeResult;
+
+ ConstantRange StartRange = getUnsignedRange(Start);
+ ConstantRange EndRange = getUnsignedRange(End);
+ APInt Min = APIntOps::umin(StartRange.getUnsignedMin(),
+ EndRange.getUnsignedMin());
+ APInt Max = APIntOps::umax(StartRange.getUnsignedMax(),
+ EndRange.getUnsignedMax());
+ if (Min.isMinValue() && Max.isMaxValue())
+ return ConservativeResult;
+ return ConservativeResult.intersectWith(ConstantRange(Min, Max+1));
+ }
+ }
+
+ return ConservativeResult;
+ }
+
+ if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
+ // For a SCEVUnknown, ask ValueTracking.
+ unsigned BitWidth = getTypeSizeInBits(U->getType());
+ APInt Mask = APInt::getAllOnesValue(BitWidth);
+ APInt Zeros(BitWidth, 0), Ones(BitWidth, 0);
+ ComputeMaskedBits(U->getValue(), Mask, Zeros, Ones, TD);
+ if (Ones == ~Zeros + 1)
+ return ConservativeResult;
+ return ConservativeResult.intersectWith(ConstantRange(Ones, ~Zeros + 1));
+ }
+
+ return ConservativeResult;
+}
+
+/// getSignedRange - Determine the signed range for a particular SCEV.
+///
+ConstantRange
+ScalarEvolution::getSignedRange(const SCEV *S) {
+
+ if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S))
+ return ConstantRange(C->getValue()->getValue());
+
+ unsigned BitWidth = getTypeSizeInBits(S->getType());
+ ConstantRange ConservativeResult(BitWidth, /*isFullSet=*/true);
+
+ // If the value has known zeros, the maximum signed value will have those
+ // known zeros as well.
+ uint32_t TZ = GetMinTrailingZeros(S);
+ if (TZ != 0)
+ ConservativeResult =
+ ConstantRange(APInt::getSignedMinValue(BitWidth),
+ APInt::getSignedMaxValue(BitWidth).ashr(TZ).shl(TZ) + 1);
+
+ if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
+ ConstantRange X = getSignedRange(Add->getOperand(0));
+ for (unsigned i = 1, e = Add->getNumOperands(); i != e; ++i)
+ X = X.add(getSignedRange(Add->getOperand(i)));
+ return ConservativeResult.intersectWith(X);
+ }
+
+ if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) {
+ ConstantRange X = getSignedRange(Mul->getOperand(0));
+ for (unsigned i = 1, e = Mul->getNumOperands(); i != e; ++i)
+ X = X.multiply(getSignedRange(Mul->getOperand(i)));
+ return ConservativeResult.intersectWith(X);
+ }
+
+ if (const SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(S)) {
+ ConstantRange X = getSignedRange(SMax->getOperand(0));
+ for (unsigned i = 1, e = SMax->getNumOperands(); i != e; ++i)
+ X = X.smax(getSignedRange(SMax->getOperand(i)));
+ return ConservativeResult.intersectWith(X);
+ }
+
+ if (const SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(S)) {
+ ConstantRange X = getSignedRange(UMax->getOperand(0));
+ for (unsigned i = 1, e = UMax->getNumOperands(); i != e; ++i)
+ X = X.umax(getSignedRange(UMax->getOperand(i)));
+ return ConservativeResult.intersectWith(X);
+ }
+
+ if (const SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(S)) {
+ ConstantRange X = getSignedRange(UDiv->getLHS());
+ ConstantRange Y = getSignedRange(UDiv->getRHS());
+ return ConservativeResult.intersectWith(X.udiv(Y));
+ }
+
+ if (const SCEVZeroExtendExpr *ZExt = dyn_cast<SCEVZeroExtendExpr>(S)) {
+ ConstantRange X = getSignedRange(ZExt->getOperand());
+ return ConservativeResult.intersectWith(X.zeroExtend(BitWidth));
+ }
+
+ if (const SCEVSignExtendExpr *SExt = dyn_cast<SCEVSignExtendExpr>(S)) {
+ ConstantRange X = getSignedRange(SExt->getOperand());
+ return ConservativeResult.intersectWith(X.signExtend(BitWidth));
+ }
+
+ if (const SCEVTruncateExpr *Trunc = dyn_cast<SCEVTruncateExpr>(S)) {
+ ConstantRange X = getSignedRange(Trunc->getOperand());
+ return ConservativeResult.intersectWith(X.truncate(BitWidth));
+ }
+
+ if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
+ // If there's no signed wrap, and all the operands have the same sign or
+ // zero, the value won't ever change sign.
+ if (AddRec->hasNoSignedWrap()) {
+ bool AllNonNeg = true;
+ bool AllNonPos = true;
+ for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) {
+ if (!isKnownNonNegative(AddRec->getOperand(i))) AllNonNeg = false;
+ if (!isKnownNonPositive(AddRec->getOperand(i))) AllNonPos = false;
+ }
+ if (AllNonNeg)
+ ConservativeResult = ConservativeResult.intersectWith(
+ ConstantRange(APInt(BitWidth, 0),
+ APInt::getSignedMinValue(BitWidth)));
+ else if (AllNonPos)
+ ConservativeResult = ConservativeResult.intersectWith(
+ ConstantRange(APInt::getSignedMinValue(BitWidth),
+ APInt(BitWidth, 1)));
+ }
+
+ // TODO: non-affine addrec
+ if (AddRec->isAffine()) {
+ const Type *Ty = AddRec->getType();
+ const SCEV *MaxBECount = getMaxBackedgeTakenCount(AddRec->getLoop());
+ if (!isa<SCEVCouldNotCompute>(MaxBECount) &&
+ getTypeSizeInBits(MaxBECount->getType()) <= BitWidth) {
+ MaxBECount = getNoopOrZeroExtend(MaxBECount, Ty);
+
+ const SCEV *Start = AddRec->getStart();
+ const SCEV *End = AddRec->evaluateAtIteration(MaxBECount, *this);
+
+ // Check for overflow.
+ if (!AddRec->hasNoSignedWrap())
+ return ConservativeResult;
+
+ ConstantRange StartRange = getSignedRange(Start);
+ ConstantRange EndRange = getSignedRange(End);
+ APInt Min = APIntOps::smin(StartRange.getSignedMin(),
+ EndRange.getSignedMin());
+ APInt Max = APIntOps::smax(StartRange.getSignedMax(),
+ EndRange.getSignedMax());
+ if (Min.isMinSignedValue() && Max.isMaxSignedValue())
+ return ConservativeResult;
+ return ConservativeResult.intersectWith(ConstantRange(Min, Max+1));
+ }
+ }
+
+ return ConservativeResult;
+ }
+
+ if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
+ // For a SCEVUnknown, ask ValueTracking.
+ if (!U->getValue()->getType()->isInteger() && !TD)
+ return ConservativeResult;
+ unsigned NS = ComputeNumSignBits(U->getValue(), TD);
+ if (NS == 1)
+ return ConservativeResult;
+ return ConservativeResult.intersectWith(
+ ConstantRange(APInt::getSignedMinValue(BitWidth).ashr(NS - 1),
+ APInt::getSignedMaxValue(BitWidth).ashr(NS - 1)+1));
+ }
+
+ return ConservativeResult;
+}
+