diff options
| -rw-r--r-- | lib/Analysis/ScalarEvolution.cpp | 123 | ||||
| -rw-r--r-- | test/Analysis/ScalarEvolution/nsw-offset.ll | 5 | ||||
| -rw-r--r-- | test/Analysis/ScalarEvolution/trip-count9.ll | 408 |
3 files changed, 483 insertions, 53 deletions
diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 2f44913abd..b875543691 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -2912,61 +2912,69 @@ 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 X; + 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 X; + 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 X; + 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 X; + return ConservativeResult.intersectWith(X); } if (const SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(S)) { ConstantRange X = getSignedRange(UDiv->getLHS()); ConstantRange Y = getSignedRange(UDiv->getRHS()); - return X.udiv(Y); + return ConservativeResult.intersectWith(X.udiv(Y)); } if (const SCEVZeroExtendExpr *ZExt = dyn_cast<SCEVZeroExtendExpr>(S)) { ConstantRange X = getSignedRange(ZExt->getOperand()); - return X.zeroExtend(cast<IntegerType>(ZExt->getType())->getBitWidth()); + return ConservativeResult.intersectWith(X.zeroExtend(BitWidth)); } if (const SCEVSignExtendExpr *SExt = dyn_cast<SCEVSignExtendExpr>(S)) { ConstantRange X = getSignedRange(SExt->getOperand()); - return X.signExtend(cast<IntegerType>(SExt->getType())->getBitWidth()); + return ConservativeResult.intersectWith(X.signExtend(BitWidth)); } if (const SCEVTruncateExpr *Trunc = dyn_cast<SCEVTruncateExpr>(S)) { ConstantRange X = getSignedRange(Trunc->getOperand()); - return X.truncate(cast<IntegerType>(Trunc->getType())->getBitWidth()); + return ConservativeResult.intersectWith(X.truncate(BitWidth)); } - ConstantRange FullSet(getTypeSizeInBits(S->getType()), true); - if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) { const SCEV *T = getBackedgeTakenCount(AddRec->getLoop()); const SCEVConstant *Trip = dyn_cast<SCEVConstant>(T); - ConstantRange ConservativeResult = FullSet; // If there's no signed wrap, and all the operands have the same sign or // zero, the value won't ever change sign. @@ -2977,20 +2985,21 @@ ScalarEvolution::getSignedRange(const SCEV *S) { if (!isKnownNonNegative(AddRec->getOperand(i))) AllNonNeg = false; if (!isKnownNonPositive(AddRec->getOperand(i))) AllNonPos = false; } - unsigned BitWidth = getTypeSizeInBits(AddRec->getType()); if (AllNonNeg) - ConservativeResult = ConstantRange(APInt(BitWidth, 0), - APInt::getSignedMinValue(BitWidth)); + ConservativeResult = ConservativeResult.intersectWith( + ConstantRange(APInt(BitWidth, 0), + APInt::getSignedMinValue(BitWidth))); else if (AllNonPos) - ConservativeResult = ConstantRange(APInt::getSignedMinValue(BitWidth), - APInt(BitWidth, 1)); + ConservativeResult = ConservativeResult.intersectWith( + ConstantRange(APInt::getSignedMinValue(BitWidth), + APInt(BitWidth, 1))); } // TODO: non-affine addrec if (Trip && AddRec->isAffine()) { const Type *Ty = AddRec->getType(); const SCEV *MaxBECount = getMaxBackedgeTakenCount(AddRec->getLoop()); - if (getTypeSizeInBits(MaxBECount->getType()) <= getTypeSizeInBits(Ty)) { + if (getTypeSizeInBits(MaxBECount->getType()) <= BitWidth) { MaxBECount = getNoopOrZeroExtend(MaxBECount, Ty); const SCEV *Start = AddRec->getStart(); @@ -3008,7 +3017,7 @@ ScalarEvolution::getSignedRange(const SCEV *S) { EndRange.getSignedMax()); if (Min.isMinSignedValue() && Max.isMaxSignedValue()) return ConservativeResult; - return ConstantRange(Min, Max+1); + return ConservativeResult.intersectWith(ConstantRange(Min, Max+1)); } } @@ -3017,18 +3026,17 @@ ScalarEvolution::getSignedRange(const SCEV *S) { if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) { // For a SCEVUnknown, ask ValueTracking. - unsigned BitWidth = getTypeSizeInBits(U->getType()); if (!U->getValue()->getType()->isInteger() && !TD) - return FullSet; + return ConservativeResult; unsigned NS = ComputeNumSignBits(U->getValue(), TD); if (NS == 1) - return FullSet; - return + return ConservativeResult; + return ConservativeResult.intersectWith( ConstantRange(APInt::getSignedMinValue(BitWidth).ashr(NS - 1), - APInt::getSignedMaxValue(BitWidth).ashr(NS - 1)+1); + APInt::getSignedMaxValue(BitWidth).ashr(NS - 1)+1)); } - return FullSet; + return ConservativeResult; } /// createSCEV - We know that there is no SCEV for the specified value. @@ -4947,6 +4955,9 @@ const SCEV *ScalarEvolution::getBECount(const SCEV *Start, const SCEV *End, const SCEV *Step, bool NoWrap) { + assert(!isKnownNegative(Step) && + "This code doesn't handle negative strides yet!"); + const Type *Ty = Start->getType(); const SCEV *NegOne = getIntegerSCEV(-1, Ty); const SCEV *Diff = getMinusSCEV(End, Start); @@ -4989,39 +5000,35 @@ ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS, AddRec->hasNoUnsignedWrap(); if (AddRec->isAffine()) { - // FORNOW: We only support unit strides. unsigned BitWidth = getTypeSizeInBits(AddRec->getType()); const SCEV *Step = AddRec->getStepRecurrence(*this); - // TODO: handle non-constant strides. - const SCEVConstant *CStep = dyn_cast<SCEVConstant>(Step); - if (!CStep || CStep->isZero()) + if (Step->isZero()) return getCouldNotCompute(); - if (CStep->isOne()) { + if (Step->isOne()) { // With unit stride, the iteration never steps past the limit value. - } else if (CStep->getValue()->getValue().isStrictlyPositive()) { - if (NoWrap) { - // We know the iteration won't step past the maximum value for its type. - ; - } else if (const SCEVConstant *CLimit = dyn_cast<SCEVConstant>(RHS)) { - // Test whether a positive iteration iteration can step past the limit - // value and past the maximum value for its type in a single step. - if (isSigned) { - APInt Max = APInt::getSignedMaxValue(BitWidth); - if ((Max - CStep->getValue()->getValue()) - .slt(CLimit->getValue()->getValue())) - return getCouldNotCompute(); - } else { - APInt Max = APInt::getMaxValue(BitWidth); - if ((Max - CStep->getValue()->getValue()) - .ult(CLimit->getValue()->getValue())) - return getCouldNotCompute(); - } - } else - // TODO: handle non-constant limit values below. - return getCouldNotCompute(); + } else if (isKnownPositive(Step)) { + // Test whether a positive iteration iteration can step past the limit + // value and past the maximum value for its type in a single step. + // Note that it's not sufficient to check NoWrap here, because even + // though the value after a wrap is undefined, it's not undefined + // behavior, so if wrap does occur, the loop could either terminate or + // loop infinately, but in either case, the loop is guaranteed to + // iterate at least until the iteration where the wrapping occurs. + const SCEV *One = getIntegerSCEV(1, Step->getType()); + if (isSigned) { + APInt Max = APInt::getSignedMaxValue(BitWidth); + if ((Max - getSignedRange(getMinusSCEV(Step, One)).getSignedMax()) + .slt(getSignedRange(RHS).getSignedMax())) + return getCouldNotCompute(); + } else { + APInt Max = APInt::getMaxValue(BitWidth); + if ((Max - getUnsignedRange(getMinusSCEV(Step, One)).getUnsignedMax()) + .ult(getUnsignedRange(RHS).getUnsignedMax())) + return getCouldNotCompute(); + } } else - // TODO: handle negative strides below. + // TODO: Handle negative strides here and below. return getCouldNotCompute(); // We know the LHS is of the form {n,+,s} and the RHS is some loop-invariant @@ -5054,6 +5061,20 @@ ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS, getSignedRange(End).getSignedMax() : getUnsignedRange(End).getUnsignedMax()); + // If MaxEnd is within a step of the maximum integer value in its type, + // adjust it down to the minimum value which would produce the same effect. + // This allows the subsequent ceiling divison of (N+(step-1))/step to + // compute the correct value. + const SCEV *StepMinusOne = getMinusSCEV(Step, + getIntegerSCEV(1, Step->getType())); + MaxEnd = isSigned ? + getSMinExpr(MaxEnd, + getMinusSCEV(getConstant(APInt::getSignedMaxValue(BitWidth)), + StepMinusOne)) : + getUMinExpr(MaxEnd, + getMinusSCEV(getConstant(APInt::getMaxValue(BitWidth)), + StepMinusOne)); + // Finally, we subtract these two values and divide, rounding up, to get // the number of times the backedge is executed. const SCEV *BECount = getBECount(Start, End, Step, NoWrap); diff --git a/test/Analysis/ScalarEvolution/nsw-offset.ll b/test/Analysis/ScalarEvolution/nsw-offset.ll index fd0dfe66ae..ed97de6a50 100644 --- a/test/Analysis/ScalarEvolution/nsw-offset.ll +++ b/test/Analysis/ScalarEvolution/nsw-offset.ll @@ -6,8 +6,9 @@ target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128" -define void @foo(i32 %n, double* nocapture %d, double* nocapture %q) nounwind { +define void @foo(i32 %no, double* nocapture %d, double* nocapture %q) nounwind { entry: + %n = and i32 %no, 4294967294 %0 = icmp sgt i32 %n, 0 ; <i1> [#uses=1] br i1 %0, label %bb.nph, label %return @@ -73,4 +74,4 @@ return: ; preds = %bb1.return_crit_edg } ; CHECK: Loop %bb: backedge-taken count is ((-1 + %n) /u 2) -; CHECK: Loop %bb: max backedge-taken count is 1073741823 +; CHECK: Loop %bb: max backedge-taken count is 1073741822 diff --git a/test/Analysis/ScalarEvolution/trip-count9.ll b/test/Analysis/ScalarEvolution/trip-count9.ll new file mode 100644 index 0000000000..9180f2b8dd --- /dev/null +++ b/test/Analysis/ScalarEvolution/trip-count9.ll @@ -0,0 +1,408 @@ +; RUN: opt -analyze -scalar-evolution -S < %s | FileCheck %s + +; Every combination of +; - starting at 0, 1, or %x +; - steping by 1 or 2 +; - stopping at %n or %n*2 +; - using nsw, or not + +; Some of these represent missed opportunities. + +; CHECK: Determining loop execution counts for: @foo +; CHECK: Loop %loop: backedge-taken count is (-1 + %n) +; CHECK: Loop %loop: max backedge-taken count is 6 +define void @foo(i4 %n) { +entry: + %s = icmp sgt i4 %n, 0 + br i1 %s, label %loop, label %exit +loop: + %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] + %i.next = add i4 %i, 1 + %t = icmp slt i4 %i.next, %n + br i1 %t, label %loop, label %exit +exit: + ret void +} + +; CHECK: Determining loop execution counts for: @step2 +; CHECK: Loop %loop: Unpredictable backedge-taken count. +; CHECK: Loop %loop: Unpredictable max backedge-taken count. +define void @step2(i4 %n) { +entry: + %s = icmp sgt i4 %n, 0 + br i1 %s, label %loop, label %exit +loop: + %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] + %i.next = add i4 %i, 2 + %t = icmp slt i4 %i.next, %n + br i1 %t, label %loop, label %exit +exit: + ret void +} + +; CHECK: Determining loop execution counts for: @start1 +; CHECK: Loop %loop: backedge-taken count is (-2 + (2 smax %n)) +; CHECK: Loop %loop: max backedge-taken count is 5 +define void @start1(i4 %n) { +entry: + %s = icmp sgt i4 %n, 0 + br i1 %s, label %loop, label %exit +loop: + %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] + %i.next = add i4 %i, 1 + %t = icmp slt i4 %i.next, %n + br i1 %t, label %loop, label %exit +exit: + ret void +} + +; CHECK: Determining loop execution counts for: @start1_step2 +; CHECK: Loop %loop: Unpredictable backedge-taken count. +; CHECK: Loop %loop: Unpredictable max backedge-taken count. +define void @start1_step2(i4 %n) { +entry: + %s = icmp sgt i4 %n, 0 + br i1 %s, label %loop, label %exit +loop: + %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] + %i.next = add i4 %i, 2 + %t = icmp slt i4 %i.next, %n + br i1 %t, label %loop, label %exit +exit: + ret void +} + +; CHECK: Determining loop execution counts for: @startx +; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax %n)) +; CHECK: Loop %loop: max backedge-taken count is -1 +define void @startx(i4 %n, i4 %x) { +entry: + %s = icmp sgt i4 %n, 0 + br i1 %s, label %loop, label %exit +loop: + %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] + %i.next = add i4 %i, 1 + %t = icmp slt i4 %i.next, %n + br i1 %t, label %loop, label %exit +exit: + ret void +} + +; CHECK: Determining loop execution counts for: @startx_step2 +; CHECK: Loop %loop: Unpredictable backedge-taken count. +; CHECK: Loop %loop: Unpredictable max backedge-taken count. +define void @startx_step2(i4 %n, i4 %x) { +entry: + %s = icmp sgt i4 %n, 0 + br i1 %s, label %loop, label %exit +loop: + %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] + %i.next = add i4 %i, 2 + %t = icmp slt i4 %i.next, %n + br i1 %t, label %loop, label %exit +exit: + ret void +} + +; CHECK: Determining loop execution counts for: @nsw +; CHECK: Loop %loop: backedge-taken count is (-1 + %n) +; CHECK: Loop %loop: max backedge-taken count is 6 +define void @nsw(i4 %n) { +entry: + %s = icmp sgt i4 %n, 0 + br i1 %s, label %loop, label %exit +loop: + %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] + %i.next = add nsw i4 %i, 1 + %t = icmp slt i4 %i.next, %n + br i1 %t, label %loop, label %exit +exit: + ret void +} + +; Be careful with this one. If %n is INT4_MAX, %i.next will wrap. The nsw bit +; says that the result is undefined, but ScalarEvolution must respect that +; subsequent passes may result the undefined behavior in predictable ways. +; CHECK: Determining loop execution counts for: @nsw_step2 +; CHECK: Loop %loop: Unpredictable backedge-taken count. +; CHECK: Loop %loop: Unpredictable max backedge-taken count. +define void @nsw_step2(i4 %n) { +entry: + %s = icmp sgt i4 %n, 0 + br i1 %s, label %loop, label %exit +loop: + %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] + %i.next = add nsw i4 %i, 2 + %t = icmp slt i4 %i.next, %n + br i1 %t, label %loop, label %exit +exit: + ret void +} + +; CHECK: Determining loop execution counts for: @nsw_start1 +; CHECK: Loop %loop: backedge-taken count is (-2 + (2 smax %n)) +; CHECK: Loop %loop: max backedge-taken count is 5 +define void @nsw_start1(i4 %n) { +entry: + %s = icmp sgt i4 %n, 0 + br i1 %s, label %loop, label %exit +loop: + %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] + %i.next = add nsw i4 %i, 1 + %t = icmp slt i4 %i.next, %n + br i1 %t, label %loop, label %exit +exit: + ret void +} + +; CHECK: Determining loop execution counts for: @nsw_start1_step2 +; CHECK: Loop %loop: Unpredictable backedge-taken count. +; CHECK: Loop %loop: Unpredictable max backedge-taken count. +define void @nsw_start1_step2(i4 %n) { +entry: + %s = icmp sgt i4 %n, 0 + br i1 %s, label %loop, label %exit +loop: + %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] + %i.next = add nsw i4 %i, 2 + %t = icmp slt i4 %i.next, %n + br i1 %t, label %loop, label %exit +exit: + ret void +} + +; CHECK: Determining loop execution counts for: @nsw_startx +; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax %n)) +; CHECK: Loop %loop: max backedge-taken count is -1 +define void @nsw_startx(i4 %n, i4 %x) { +entry: + %s = icmp sgt i4 %n, 0 + br i1 %s, label %loop, label %exit +loop: + %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] + %i.next = add nsw i4 %i, 1 + %t = icmp slt i4 %i.next, %n + br i1 %t, label %loop, label %exit +exit: + ret void +} + +; CHECK: Determining loop execution counts for: @nsw_startx_step2 +; CHECK: Loop %loop: Unpredictable backedge-taken count. +; CHECK: Loop %loop: Unpredictable max backedge-taken count. +define void @nsw_startx_step2(i4 %n, i4 %x) { +entry: + %s = icmp sgt i4 %n, 0 + br i1 %s, label %loop, label %exit +loop: + %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] + %i.next = add nsw i4 %i, 2 + %t = icmp slt i4 %i.next, %n + br i1 %t, label %loop, label %exit +exit: + ret void +} + +; CHECK: Determining loop execution counts for: @even +; CHECK: Loop %loop: backedge-taken count is (-1 + (2 * %n)) +; CHECK: Loop %loop: max backedge-taken count is 5 +define void @even(i4 %n) { +entry: + %m = shl i4 %n, 1 + %s = icmp sgt i4 %m, 0 + br i1 %s, label %loop, label %exit +loop: + %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] + %i.next = add i4 %i, 1 + %t = icmp slt i4 %i.next, %m + br i1 %t, label %loop, label %exit +exit: + ret void +} + +; CHECK: Determining loop execution counts for: @even_step2 +; CHECK: Loop %loop: Unpredictable backedge-taken count. +; CHECK: Loop %loop: max backedge-taken count is 2 +define void @even_step2(i4 %n) { +entry: + %m = shl i4 %n, 1 + %s = icmp sgt i4 %m, 0 + br i1 %s, label %loop, label %exit +loop: + %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] + %i.next = add i4 %i, 2 + %t = icmp slt i4 %i.next, %m + br i1 %t, label %loop, label %exit +exit: + ret void +} + +; CHECK: Determining loop execution counts for: @even_start1 +; CHECK: Loop %loop: backedge-taken count is (-2 + (2 smax (2 * %n))) +; CHECK: Loop %loop: max backedge-taken count is 4 +define void @even_start1(i4 %n) { +entry: + %m = shl i4 %n, 1 + %s = icmp sgt i4 %m, 0 + br i1 %s, label %loop, label %exit +loop: + %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] + %i.next = add i4 %i, 1 + %t = icmp slt i4 %i.next, %m + br i1 %t, label %loop, label %exit +exit: + ret void +} + +; CHECK: Determining loop execution counts for: @even_start1_step2 +; CHECK: Loop %loop: Unpredictable backedge-taken count. +; CHECK: Loop %loop: max backedge-taken count is 2 +define void @even_start1_step2(i4 %n) { +entry: + %m = shl i4 %n, 1 + %s = icmp sgt i4 %m, 0 + br i1 %s, label %loop, label %exit +loop: + %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] + %i.next = add i4 %i, 2 + %t = icmp slt i4 %i.next, %m + br i1 %t, label %loop, label %exit +exit: + ret void +} + +; CHECK: Determining loop execution counts for: @even_startx +; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax (2 * %n))) +; CHECK: Loop %loop: max backedge-taken count is -1 +define void @even_startx(i4 %n, i4 %x) { +entry: + %m = shl i4 %n, 1 + %s = icmp sgt i4 %m, 0 + br i1 %s, label %loop, label %exit +loop: + %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] + %i.next = add i4 %i, 1 + %t = icmp slt i4 %i.next, %m + br i1 %t, label %loop, label %exit +exit: + ret void +} + +; CHECK: Determining loop execution counts for: @even_startx_step2 +; CHECK: Loop %loop: Unpredictable backedge-taken count. +; CHECK: Loop %loop: max backedge-taken count is 7 +define void @even_startx_step2(i4 %n, i4 %x) { +entry: + %m = shl i4 %n, 1 + %s = icmp sgt i4 %m, 0 + br i1 %s, label %loop, label %exit +loop: + %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] + %i.next = add i4 %i, 2 + %t = icmp slt i4 %i.next, %m + br i1 %t, label %loop, label %exit +exit: + ret void +} + +; CHECK: Determining loop execution counts for: @even_nsw +; CHECK: Loop %loop: backedge-taken count is (-1 + (2 * %n)) +; CHECK: Loop %loop: max backedge-taken count is 5 +define void @even_nsw(i4 %n) { +entry: + %m = shl i4 %n, 1 + %s = icmp sgt i4 %m, 0 + br i1 %s, label %loop, label %exit +loop: + %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] + %i.next = add nsw i4 %i, 1 + %t = icmp slt i4 %i.next, %m + br i1 %t, label %loop, label %exit +exit: + ret void +} + +; CHECK: Determining loop execution counts for: @even_nsw_step2 +; CHECK: Loop %loop: backedge-taken count is ((-1 + (2 * %n)) /u 2) +; CHECK: Loop %loop: max backedge-taken count is 2 +define void @even_nsw_step2(i4 %n) { +entry: + %m = shl i4 %n, 1 + %s = icmp sgt i4 %m, 0 + br i1 %s, label %loop, label %exit +loop: + %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] + %i.next = add nsw i4 %i, 2 + %t = icmp slt i4 %i.next, %m + br i1 %t, label %loop, label %exit +exit: + ret void +} + +; CHECK: Determining loop execution counts for: @even_nsw_start1 +; CHECK: Loop %loop: backedge-taken count is (-2 + (2 smax (2 * %n))) +; CHECK: Loop %loop: max backedge-taken count is 4 +define void @even_nsw_start1(i4 %n) { +entry: + %m = shl i4 %n, 1 + %s = icmp sgt i4 %m, 0 + br i1 %s, label %loop, label %exit +loop: + %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] + %i.next = add nsw i4 %i, 1 + %t = icmp slt i4 %i.next, %m + br i1 %t, label %loop, label %exit +exit: + ret void +} + +; CHECK: Determining loop execution counts for: @even_nsw_start1_step2 +; CHECK: Loop %loop: backedge-taken count is ((-2 + (3 smax (2 * %n))) /u 2) +; CHECK: Loop %loop: max backedge-taken count is 2 +define void @even_nsw_start1_step2(i4 %n) { +entry: + %m = shl i4 %n, 1 + %s = icmp sgt i4 %m, 0 + br i1 %s, label %loop, label %exit +loop: + %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] + %i.next = add nsw i4 %i, 2 + %t = icmp slt i4 %i.next, %m + br i1 %t, label %loop, label %exit +exit: + ret void +} + +; CHECK: Determining loop execution counts for: @even_nsw_startx +; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax (2 * %n))) +; CHECK: Loop %loop: max backedge-taken count is -1 +define void @even_nsw_startx(i4 %n, i4 %x) { +entry: + %m = shl i4 %n, 1 + %s = icmp sgt i4 %m, 0 + br i1 %s, label %loop, label %exit +loop: + %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] + %i.next = add nsw i4 %i, 1 + %t = icmp slt i4 %i.next, %m + br i1 %t, label %loop, label %exit +exit: + ret void +} + +; CHECK: Determining loop execution counts for: @even_nsw_startx_step2 +; CHECK: Loop %loop: backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x) smax (2 * %n))) /u 2) +; CHECK: Loop %loop: max backedge-taken count is 7 +define void @even_nsw_startx_step2(i4 %n, i4 %x) { +entry: + %m = shl i4 %n, 1 + %s = icmp sgt i4 %m, 0 + br i1 %s, label %loop, label %exit +loop: + %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] + %i.next = add nsw i4 %i, 2 + %t = icmp slt i4 %i.next, %m + br i1 %t, label %loop, label %exit +exit: + ret void +} |