- // TODO: non-affine addrec
- if (AddRec->isAffine()) {
- 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 *Step = AddRec->getStepRecurrence(*this);
-
- ConstantRange StartRange = getUnsignedRange(Start);
- ConstantRange StepRange = getSignedRange(Step);
- ConstantRange MaxBECountRange = getUnsignedRange(MaxBECount);
- ConstantRange EndRange =
- StartRange.add(MaxBECountRange.multiply(StepRange));
-
- // Check for overflow. This must be done with ConstantRange arithmetic
- // because we could be called from within the ScalarEvolution overflow
- // checking code.
- ConstantRange ExtStartRange = StartRange.zextOrTrunc(BitWidth*2+1);
- ConstantRange ExtStepRange = StepRange.sextOrTrunc(BitWidth*2+1);
- ConstantRange ExtMaxBECountRange =
- MaxBECountRange.zextOrTrunc(BitWidth*2+1);
- ConstantRange ExtEndRange = EndRange.zextOrTrunc(BitWidth*2+1);
- if (ExtStartRange.add(ExtMaxBECountRange.multiply(ExtStepRange)) !=
- ExtEndRange)
- return setUnsignedRange(AddRec, ConservativeResult);
-
- APInt Min = APIntOps::umin(StartRange.getUnsignedMin(),
- EndRange.getUnsignedMin());
- APInt Max = APIntOps::umax(StartRange.getUnsignedMax(),
- EndRange.getUnsignedMax());
- if (Min.isMinValue() && Max.isMaxValue())
- return setUnsignedRange(AddRec, ConservativeResult);
- return setUnsignedRange(AddRec,
- ConservativeResult.intersectWith(ConstantRange(Min, Max+1)));
- }
- }
-
- return setUnsignedRange(AddRec, ConservativeResult);
- }
-
- if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
- // Check if the IR explicitly contains !range metadata.
- Optional<ConstantRange> MDRange = GetRangeFromMetadata(U->getValue());
- if (MDRange.hasValue())
- ConservativeResult = ConservativeResult.intersectWith(MDRange.getValue());
-
- // For a SCEVUnknown, ask ValueTracking.
- APInt Zeros(BitWidth, 0), Ones(BitWidth, 0);
- computeKnownBits(U->getValue(), Zeros, Ones, DL, 0, AC, nullptr, DT);
- if (Ones == ~Zeros + 1)
- return setUnsignedRange(U, ConservativeResult);
- return setUnsignedRange(U,
- ConservativeResult.intersectWith(ConstantRange(Ones, ~Zeros + 1)));
- }
-
- return setUnsignedRange(S, ConservativeResult);
-}
-
-/// getSignedRange - Determine the signed range for a particular SCEV.
-///
-ConstantRange
-ScalarEvolution::getSignedRange(const SCEV *S) {
- // See if we've computed this range already.
- DenseMap<const SCEV *, ConstantRange>::iterator I = SignedRanges.find(S);
- if (I != SignedRanges.end())
- return I->second;
-
- if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S))
- return setSignedRange(C, 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 setSignedRange(Add, 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 setSignedRange(Mul, 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 setSignedRange(SMax, 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 setSignedRange(UMax, ConservativeResult.intersectWith(X));
- }
-
- if (const SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(S)) {
- ConstantRange X = getSignedRange(UDiv->getLHS());
- ConstantRange Y = getSignedRange(UDiv->getRHS());
- return setSignedRange(UDiv, ConservativeResult.intersectWith(X.udiv(Y)));
- }
-
- if (const SCEVZeroExtendExpr *ZExt = dyn_cast<SCEVZeroExtendExpr>(S)) {
- ConstantRange X = getSignedRange(ZExt->getOperand());
- return setSignedRange(ZExt,
- ConservativeResult.intersectWith(X.zeroExtend(BitWidth)));
- }
-
- if (const SCEVSignExtendExpr *SExt = dyn_cast<SCEVSignExtendExpr>(S)) {
- ConstantRange X = getSignedRange(SExt->getOperand());
- return setSignedRange(SExt,
- ConservativeResult.intersectWith(X.signExtend(BitWidth)));
- }
-
- if (const SCEVTruncateExpr *Trunc = dyn_cast<SCEVTruncateExpr>(S)) {
- ConstantRange X = getSignedRange(Trunc->getOperand());
- return setSignedRange(Trunc,
- ConservativeResult.intersectWith(X.truncate(BitWidth)));
- }
-
- if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {