lib/Analysis/ScalarEvolution.cpp

946       const SCEV *Start = AR->getStart();
954         return getAddRecExpr(getZeroExtendExpr(Start, Ty),
974           getTruncateOrZeroExtend(MaxBECount, Start->getType());
979           // Check whether Start+Step*MaxBECount has no unsigned overflow.
981           const SCEV *ZAdd = getZeroExtendExpr(getAddExpr(Start, ZMul), WideTy);
982           const SCEV *WideStart = getZeroExtendExpr(Start, WideTy);
993             return getAddRecExpr(getZeroExtendExpr(Start, Ty),
1008             return getAddRecExpr(getZeroExtendExpr(Start, Ty),
1022               (isLoopEntryGuardedByCond(L, ICmpInst::ICMP_ULT, Start, N) &&
1028             return getAddRecExpr(getZeroExtendExpr(Start, Ty),
1036               (isLoopEntryGuardedByCond(L, ICmpInst::ICMP_UGT, Start, N) &&
1043             return getAddRecExpr(getZeroExtendExpr(Start, Ty),
1083 // such: {sext(Step + Start),+,Step} => {(Step + sext(Start),+,Step} As a
1090   const SCEV *Start = AR->getStart();
1094   const SCEVAddExpr *SA = dyn_cast<SCEVAddExpr>(Start);
1127   if (SE->getSignExtendExpr(Start, WideTy) == OperandExtendedStart) {
1147 // Get the normalized sign-extended expression for this AddRec's Start.
1212       const SCEV *Start = AR->getStart();
1240           getTruncateOrZeroExtend(MaxBECount, Start->getType());
1245           // Check whether Start+Step*MaxBECount has no signed overflow.
1247           const SCEV *SAdd = getSignExtendExpr(getAddExpr(Start, SMul), WideTy);
1248           const SCEV *WideStart = getSignExtendExpr(Start, WideTy);
1287              (isLoopEntryGuardedByCond(L, Pred, Start, OverflowLimit) &&
1749       //  NLI + LI + {Start,+,Step}  -->  NLI + {LI+Start,+,Step}
2004       //  NLI * LI * {Start,+,Step}  -->  NLI * {LI*Start,+,LI*Step}
2246 const SCEV *ScalarEvolution::getAddRecExpr(const SCEV *Start, const SCEV *Step,
2250   Operands.push_back(Start);
3399         const SCEV *Start = AddRec->getStart();
3402         ConstantRange StartRange = getUnsignedRange(Start);
3550         const SCEV *Start = AddRec->getStart();
3553         ConstantRange StartRange = getSignedRange(Start);
5554   //     Start + Step*N = 0 (mod 2^BW)
5558   //             Step*N = -Start (mod 2^BW)
5560   // where BW is the common bit width of Start and Step.
5563   const SCEV *Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop());
5570   // to 0, it must be counting down to equal 0. Consequently, N = Start / -Step.
5577   //   N = -Start/Step (as unsigned)
5579   //   N = Start/-Step
5582   const SCEV *Distance = CountDown ? Start : getNegativeSCEV(Start);
5585   // 1*N = -Start; -1*N = Start (mod 2^BW), so:
5588     ConstantRange CR = getUnsignedRange(Start);
5616   // Then, try to solve the above equation provided that Start is constant.
5617   if (const SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start))
6444   const SCEV *Start = IV->getStart();
6446   if (!isLoopEntryGuardedByCond(L, Cond, getMinusSCEV(Start, Stride), RHS))
6447     End = IsSigned ? getSMaxExpr(RHS, Start)
6448                    : getUMaxExpr(RHS, Start);
6450   const SCEV *BECount = computeBECount(getMinusSCEV(End, Start), Stride, false);
6452   APInt MinStart = IsSigned ? getSignedRange(Start).getSignedMin()
6453                             : getUnsignedRange(Start).getUnsignedMin();
6463   // the case End = RHS. This is safe because in the other case (End - Start)
6515   const SCEV *Start = IV->getStart();
6517   if (!isLoopEntryGuardedByCond(L, Cond, getAddExpr(Start, Stride), RHS))
6518     End = IsSigned ? getSMinExpr(RHS, Start)
6519                    : getUMinExpr(RHS, Start);
6521   const SCEV *BECount = computeBECount(getMinusSCEV(Start, End), Stride, false);
6523   APInt MaxStart = IsSigned ? getSignedRange(Start).getSignedMax()
6524                             : getUnsignedRange(Start).getUnsignedMax();
6534   // the case End = RHS. This is safe because in the other case (Start - End)
6725   // Pattern match Step into Start. When Step is a multiply expression, find
6726   // the largest subexpression of Step that appears in Start. When Start is an
6727   // add expression, try to match Step in the subexpressions of Start, non
6729   static const SCEV *findGCD(ScalarEvolution &SE, const SCEV *Start,
6733     const SCEV *Res = R.visit(Start);
6848     // this occurs when Step does not divide the Start expression
6921   // Remove from Start all multiples of Step.
6922   static const SCEV *divide(ScalarEvolution &SE, const SCEV *Start,
6927     // The division is guaranteed to succeed: Step should divide Start with no
6929     assert(Step == SCEVGCD::findGCD(SE, Start, Step, &Rem) && Rem == D.Zero &&
6930            "Step should divide Start with no remainder.");
6931     return D.visit(Start);
7036     const SCEV *Start = divide(SE, Expr->getStart(), GCD);
7039     return SE.getAddRecExpr(Start, Step, Expr->getLoop(),
7128   const SCEV *Start = this->getStart();
7148   // Find the GCD and Remainder of the Start and Step coefficients of this SCEV.
7150   const SCEV *GCD = SCEVGCD::findGCD(SE, Start, Step, &Remainder);
7162   // As findGCD computed Remainder, GCD divides "Start - Remainder." The
7166       SCEVDivision::divide(SE, SE.getMinusSCEV(Start, Remainder), GCD);