Fix incorrect expand of non-linear addrecs

[apilipenko]

Summary

We have a problem in SCEVExpander around expansion of non-linear addrecs. Expanding an addrec SCEVExpander emits an expression to compute the addrec at a given iteration number (using SCEVAddRecExpr::evaluateAtIteration). As an iteration number it uses the canonical induction variable of the loop. Canonical IV here is an IV starting at 0 and incremented by 1 on every iteration, {0,+,1}. When the loop doesn't have a canonical IV SCEVExpander inserts one. It uses the type of the addrec to be expanded as the type for the canonical IV. This is not always correct.

If the addrec to expand is a linear addrec {start,+,step}, the expression to compute the value at the given iteration i is:

(start + i * step) mod MaxType,

where MaxType is the maximum value in the type of the addrec.

A canonical IV of the same type as addrec corresponds to (i mod MaxType). Using this IV as the iteration number i works fine for linear addrecs:

(start + i * step) mod MaxType = (start mod MaxType) + (i mod MaxType) * (step mod MaxType)

This is because mod commutates with + and *, so we can sink mod (truncation) down to the operands.

But it's not correct for non-linear addrecs because the expression to compute the value on the given iteration involves division (see BinomialCoefficient function in ScalarEvolution.cpp).

For example, look at scev-expand-canonical-iv-type.ll test in this patch. In this example, loop-vectorize expands i8 {0,+,2,+,1} addrec in the loop without a canonical IV. It inserts a canonical IV of type i8 and uses in the expression to compute the value of the addrec at the given iteration.

The expression is:

((i * (i - 1)) /u 2 + 2 * i) mod 256

Using a i8 canonical IV effectively turns it into:

((i mod 256) * ((i mod 256) - 1)) /u 2 + 2 * (i mod 256)

This is not equal to the original expression, because mod and division (truncation and lshr) don't commutate. In this case we need to used a canonical IV of a wider type. For the exact SCEVs of this example see below [1].

SCEVExpander needs to be aware that expansion of an addrec might need an canonical IV of a type wider than the addrec. This patch fixes the issue by introducing SCEVAddRecExpr::minIterationWidthForEvaluateAtIteration method and using it in SCEVExpander.

This patch can be split into three distinct changes. I plan to split them when integrating, but post the initial review with all three in one for better context.

1. Prepare SCEVExpander::visitAddRecExpr to use CanonicalIV wider than the addrec.
2. Introduce SCEVAddRecExpr::minIterationWidthForEvaluateAtIteration, MinIterationWidthForBinomialCoefficient with an assertion in BinomialCoefficient.
3. Use SCEVAddRecExpr::minIterationWidthForEvaluateAtIteration in SCEVExpander::visitAddRecExpr to compute the type of the canonical IV.

This patch is currently going through our internal fuzzing and performance testing.

[1] Debug output from evaluateAtIteration before the fix:

evaluateAtIteration this = {0,+,2,+,1}<%outer_loop>
evaluateAtIteration it = i8 %indvar
evaluateAtIteration result = ((trunc i9 (((zext i8 (-1 + %indvar) to i9) * (zext i8 %indvar to i9)) /u 2) to i8) + (2 * %indvar))

After the fix:

evaluateAtIteration this = {0,+,2,+,1}<%outer_loop>
evaluateAtIteration it = i9 %indvar
evaluateAtIteration result = ((trunc i9 (((-1 + %indvar) * %indvar) /u 2) to i8) + (2 * (trunc i9 %indvar to i8)))

[reames]

Artur, nice find. In terms of staging complexity, have you considered how impactful it would be to simply refuse to generate the value at the given iteration in this case? evaluateAtIteration is allowed to return SCEVCouldNotCompute. I'm tempted to first introduce a bailout for a quick correctness fix - maybe along side your assert to see if we're missing any other cases - and then spend more time considering your full fix.

One observation: I really don't think we want to be emitting an i9. We probably want to be rounding up to the nearest legal type. For i65, I doubt we want to be generating it at all. It's probably best to simply bail out in that case.

p.s. Please go ahead and land your preparatory changes (1). The context was helpful, but we should get those out of the way to simplify the rest of the review. (This is mostly just factoring out CanonicalIVType right?)

lib/Analysis/ScalarEvolutionExpander.cpp

1486

Removing this entirely seems like overkill. Maybe either add a restriction to a) affine addrecs or b) the bitwidth of the existing canonical IV is sufficient?

1596

Not sure you actually want getUnknown? Did you mean getSCEV?

[apilipenko]

In D62563#1521477, @reames wrote:

Artur, nice find. In terms of staging complexity, have you considered how impactful it would be to simply refuse to generate the value at the given iteration in this case? evaluateAtIteration is allowed to return SCEVCouldNotCompute. I'm tempted to first introduce a bailout for a quick correctness fix - maybe along side your assert to see if we're missing any other cases - and then spend more time considering your full fix.

Yes, evaluateAtIteration can return SCEVCouldNotCompute, but it doesn't seem like SCEVExpander is ready for that. What we can do instead is to use expandAddRecExprLiterally for non-affine addrecs.

One observation: I really don't think we want to be emitting an i9. We probably want to be rounding up to the nearest legal type. For i65, I doubt we want to be generating it at all. It's probably best to simply bail out in that case.

evaluateAtIteration is already emitting i9 types for high order binomial coefficients. See the debug output in the review description. But I guess you are right, that we don't want to introduce canonical IVs of non-legal types. If we need to bail out for some types the the bail out would be expandAddRecExprLiterally.

In general I like the idea of using expandAddRecExprLiterally for non-affine addrecs, I'm going to run some performance experiments with this approach to see the impact.

[reames]

In D62563#1522063, @apilipenko wrote:

...
In general I like the idea of using expandAddRecExprLiterally for non-affine addrecs, I'm going to run some performance experiments with this approach to see the impact.

Artur and I spoke offline. The workaround suggestion I made doesn't appear to really work well, but Artur is going to move forward with the expandAddRecExprLiterally idea when we'd overflow the IV type. This seems to be a practical fix for non-affine IVs.

[apilipenko]

Fall back to non-canonical mode for non-affine addrecs.

[reames]

include/llvm/Analysis/ScalarEvolutionExpressions.h

347

Does this mean that evaluateAtIteration may return an incorrect result? If so, I'd very much like to see an assert which trips on that usage.

lib/Analysis/ScalarEvolutionExpander.cpp

1486

How about only falling back to literal expansion for non-affine addrecs which actually need the wider expansion?

[ebrevnov]

There is a https://bugs.llvm.org/show_bug.cgi?id=42384 failing due same problem.

[apilipenko]

Finished by @ebrevnov as D65276.

include/llvm/Analysis/ScalarEvolutionExpander.h

class SCEVExpander : public SCEVVisitor<SCEVExpander, Value*> {
 
     /// When expanding addrecs in the IVIncInsertLoop loop, insert the IV
     /// increment at this position.
     Instruction *IVIncInsertPos;
 
     /// Phis that complete an IV chain. Reuse
     DenseSet<AssertingVH<PHINode>> ChainedPhis;
 
-    /// When true, expressions are expanded in "canonical" form. In particular,
-    /// addrecs are expanded as arithmetic based on a canonical induction
-    /// variable. When false, expression are expanded in a more literal form.
+    /// When true, SCEVExpander tries to expand expressions in "canonical" form.
+    /// When false, expressions are expanded in a more literal form.
+    ///
+    /// In "canonical" form addrecs are expanded as arithmetic based on a
+    /// canonical induction variable. Note that CanonicalMode doesn't guarantee
+    /// that all expressions are expanded in "canonical" form. For some
+    /// expressions literal mode can be preferred.
     bool CanonicalMode;
 
     /// When invoked from LSR, the expander is in "strength reduction" mode. The
     /// only difference is that phi's are only reused if they are already in
     /// "expanded" form.
     bool LSRMode;
 
     typedef IRBuilder<TargetFolder> BuilderType;

include/llvm/Analysis/ScalarEvolutionExpressions.h

public:
     void setNoWrapFlags(NoWrapFlags Flags) {
       if (Flags & (FlagNUW | FlagNSW))
         Flags = ScalarEvolution::setFlags(Flags, FlagNW);
       SubclassData |= Flags;
     }
 
     /// Return the value of this chain of recurrences at the specified
     /// iteration number.
+    ///
+    /// Note that for the resulting expression to be correct the iteration
+    /// number can't be narrower than what
+    /// minIterationWidthForEvaluateAtIteration returns.
     const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const;
 
+    /// Return the minimum bitwidth of the iteration expr to compute this
+    /// AddRec at the given iteration without overflow. For affine AddRecs its
+    /// the same as the AddRec type width, for non-affine it might be wider
+    /// that the AddRec type width.
+    unsigned minIterationWidthForEvaluateAtIteration(ScalarEvolution &SE) const;
+
     /// Return the number of iterations of this loop that produce
     /// values in the specified constant range.  Another way of
     /// looking at this is that it returns the first iteration number
     /// where the value is not in the condition, thus computing the
     /// exit count.  If the iteration count can't be computed, an
     /// instance of SCEVCouldNotCompute is returned.
     const SCEV *getNumIterationsInRange(const ConstantRange &Range,
                                         ScalarEvolution &SE) const;

lib/Analysis/ScalarEvolution.cpp

 };
 
 } // end anonymous namespace
 
 //===----------------------------------------------------------------------===//
 //                      Simple SCEV method implementations
 //===----------------------------------------------------------------------===//
 
+static unsigned MinIterationWidthForBinomialCoefficient(unsigned K,
+                                                        Type *ResultTy,
+                                                        ScalarEvolution &SE) {
+  unsigned W = SE.getTypeSizeInBits(ResultTy);
+  unsigned T = 1;
+  for (unsigned i = 3; i <= K; ++i)
+    T += APInt(W, i).countTrailingZeros();
+  return W + T;
+}
+
 /// Compute BC(It, K).  The result has width W.  Assume, K > 0.
 static const SCEV *BinomialCoefficient(const SCEV *It, unsigned K,
                                        ScalarEvolution &SE,
                                        Type *ResultTy) {
   // Handle the simplest case efficiently.
   if (K == 1)
     return SE.getTruncateOrZeroExtend(It, ResultTy);
 
for (unsigned i = 3; i <= K; ++i) {
     unsigned TwoFactors = Mult.countTrailingZeros();
     T += TwoFactors;
     Mult.lshrInPlace(TwoFactors);
     OddFactorial *= Mult;
   }
 
   // We need at least W + T bits for the multiplication step
   unsigned CalculationBits = W + T;
+  assert(MinIterationWidthForBinomialCoefficient(K, ResultTy, SE) ==
+             CalculationBits &&
+         "must be the same!");
 
   // Calculate 2^T, at width T+W.
   APInt DivFactor = APInt::getOneBitSet(CalculationBits, T);
 
   // Calculate the multiplicative inverse of K! / 2^T;
   // this multiplication factor will perform the exact division by
   // K! / 2^T.
   APInt Mod = APInt::getSignedMinValue(W+1);
for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
     if (isa<SCEVCouldNotCompute>(Coeff))
       return Coeff;
 
     Result = SE.getAddExpr(Result, SE.getMulExpr(getOperand(i), Coeff));
   }
   return Result;
 }
 
+unsigned SCEVAddRecExpr::minIterationWidthForEvaluateAtIteration(
+    ScalarEvolution &SE) const {
+  if (isAffine())
+    return SE.getTypeSizeInBits(getType());
+  return MinIterationWidthForBinomialCoefficient(getNumOperands() - 1,
+                                                 getType(), SE);
+}
+
 //===----------------------------------------------------------------------===//
 //                    SCEV Expression folder implementations
 //===----------------------------------------------------------------------===//
 
 const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op, Type *Ty,
                                              unsigned Depth) {
   assert(getTypeSizeInBits(Op->getType()) > getTypeSizeInBits(Ty) &&
          "This is not a truncating conversion!");

lib/Analysis/ScalarEvolutionExpander.cpp

if (PointerType *PTy = dyn_cast<PointerType>(ExpandTy)) {
       rememberInstruction(Result);
     }
   }
 
   return Result;
 }
 
 Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) {
-  if (!CanonicalMode) return expandAddRecExprLiterally(S);
+  // In canonical mode we compute the addrec as an expression of a canonical IV
+  // using evaluateAtIteration and expand the resulting SCEV expression. This
+  // way we avoid introducing new IVs to carry on the comutation of the addrec
+  // throughout the loop.
+  //
+  // For non-affine addrecs evaluateAtIteration might need a canonical IV of a
+  // type wider than the addrec itself (see SCEVAddRecExpr::
+  // minIterationWidthForEvaluateAtIteration). Emitting a canonical IV of the
+  // proper type might produce non-legal types, for example expanding an i64
+  // {0,+,2,+,1} addrec would need an i65 canonical IV. To avoid this just fall
+  // back to non-canonical mode for non-affine addrecs.
+  if (!CanonicalMode || !S->isAffine())
+    return expandAddRecExprLiterally(S);
 
   Type *Ty = SE.getEffectiveSCEVType(S->getType());
   const Loop *L = S->getLoop();
 
   // First check for an existing canonical IV in a suitable type.
   PHINode *CanonicalIV = nullptr;
   if (PHINode *PN = L->getCanonicalInductionVariable())
     if (SE.getTypeSizeInBits(PN->getType()) >= SE.getTypeSizeInBits(Ty))
       CanonicalIV = PN;
 
   // Rewrite an AddRec in terms of the canonical induction variable, if
   // its type is more narrow.
   if (CanonicalIV &&
       SE.getTypeSizeInBits(CanonicalIV->getType()) >
       SE.getTypeSizeInBits(Ty)) {
     SmallVector<const SCEV *, 4> NewOps(S->getNumOperands());
     for (unsigned i = 0, e = S->getNumOperands(); i != e; ++i)
       NewOps[i] = SE.getAnyExtendExpr(S->op_begin()[i], CanonicalIV->getType());
     Value *V = expand(SE.getAddRecExpr(NewOps, S->getLoop(),
assert(Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) &&
            "IVs with types different from the canonical IV should "
            "already have been handled!");
     return CanonicalIV;
   }
 
   // {0,+,F} --> {0,+,1} * F
 
   // If this is a simple linear addrec, emit it now as a special case.
   if (S->isAffine())    // {0,+,F} --> i*F
     return
       expand(SE.getTruncateOrNoop(
         SE.getMulExpr(SE.getUnknown(CanonicalIV),
                       SE.getNoopOrAnyExtend(S->getOperand(1),
                                             CanonicalIV->getType())),
         Ty));
 
   // If this is a chain of recurrences, turn it into a closed form, using the
   // folders, then expandCodeFor the closed form.  This allows the folders to
   // simplify the expression without having to build a bunch of special code
   // into this folder.
   const SCEV *IH = SE.getUnknown(CanonicalIV);   // Get I as a "symbolic" SCEV.
+  // evaluateAtIteration for non-affine addrecs needs canonical IV of a wider
+  // type. For such addrecs we fall back to non-canonical (literal) expansion
+  // mode.
+  assert(SE.getTypeSizeInBits(IH->getType()) >=
+             S->minIterationWidthForEvaluateAtIteration(SE) &&
+         "Can't use this canonical IV for evaluateAtIteration");
 
   // Promote S up to the canonical IV type, if the cast is foldable.
   const SCEV *NewS = S;
   const SCEV *Ext = SE.getNoopOrAnyExtend(S, CanonicalIV->getType());
   if (isa<SCEVAddRecExpr>(Ext))
     NewS = Ext;
 
   const SCEV *V = cast<SCEVAddRecExpr>(NewS)->evaluateAtIteration(IH, SE);

unittests/Analysis/ScalarEvolutionTest.cpp

auto GetAR2 = [&](ScalarEvolution &SE, Loop *L) -> const SCEV * {
     return SE.getAddRecExpr(SE.getConstant(APInt(ARBitWidth, 5)),
                             SE.getOne(ARType), L, SCEV::FlagAnyWrap);
   };
   TestNoCanonicalIV(GetAR2);
   TestNarrowCanonicalIV(GetAR2);
   TestMatchingCanonicalIV(GetAR2, ARBitWidth);
 }
 
+// Test expansion of non-affine addrecs in CanonicalMode.
+// Expanding non-affine addrecs in canonical mode takes a canonical IV of a
+// type wider than the type of the addrec itself. See SCEVAddRecExpr::
+// minIterationWidthForEvaluateAtIteration comment. Currently, SCEVExpander
+// just falls back to literal mode for non-affine addrecs.
+TEST_F(ScalarEvolutionsTest, SCEVExpandNonAffineAddRec) {
+  LLVMContext C;
+  SMDiagnostic Err;
+
+  // Expand the addrec produced by GetAddRec into a loop without a canonical IV.
+  auto TestNoCanonicalIV = [&](std::function<const SCEVAddRecExpr *(
+                                   ScalarEvolution & SE, Loop * L)> GetAddRec) {
+    std::unique_ptr<Module> M =
+        parseAssemblyString("define i32 @test(i32 %limit) { "
+                            "entry: "
+                            "  br label %loop "
+                            "loop: "
+                            "  %i = phi i32 [ 1, %entry ], [ %i.inc, %loop ] "
+                            "  %i.inc = add nsw i32 %i, 1 "
+                            "  %cont = icmp slt i32 %i.inc, %limit "
+                            "  br i1 %cont, label %loop, label %exit "
+                            "exit: "
+                            "  ret i32 %i.inc "
+                            "}",
+                            Err, C);
+
+    assert(M && "Could not parse module?");
+    assert(!verifyModule(*M) && "Must have been well formed!");
+
+    runWithSE(*M, "test", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
+      auto &I = GetInstByName(F, "i");
+      auto *Loop = LI.getLoopFor(I.getParent());
+      EXPECT_FALSE(Loop->getCanonicalInductionVariable());
+
+      auto *AR = GetAddRec(SE, Loop);
+      EXPECT_FALSE(AR->isAffine());
+
+      SCEVExpander Exp(SE, M->getDataLayout(), "expander");
+      auto *InsertAt = I.getNextNode();
+      Value *V = Exp.expandCodeFor(AR, nullptr, InsertAt);
+      auto *ExpandedAR = SE.getSCEV(V);
+      // Check that the expansion happened literally.
+      EXPECT_EQ(AR, ExpandedAR);
+    });
+  };
+
+  // Expand the addrec produced by GetAddRec into a loop with a canonical IV
+  // which is narrower than addrec type.
+  auto TestNarrowCanonicalIV = [&](
+      std::function<const SCEVAddRecExpr *(ScalarEvolution & SE, Loop * L)>
+          GetAddRec) {
+    std::unique_ptr<Module> M = parseAssemblyString(
+        "define i32 @test(i32 %limit) { "
+        "entry: "
+        "  br label %loop "
+        "loop: "
+        "  %i = phi i32 [ 1, %entry ], [ %i.inc, %loop ] "
+        "  %canonical.iv = phi i8 [ 0, %entry ], [ %canonical.iv.inc, %loop ] "
+        "  %i.inc = add nsw i32 %i, 1 "
+        "  %canonical.iv.inc = add i8 %canonical.iv, 1 "
+        "  %cont = icmp slt i32 %i.inc, %limit "
+        "  br i1 %cont, label %loop, label %exit "
+        "exit: "
+        "  ret i32 %i.inc "
+        "}",
+        Err, C);
+
+    assert(M && "Could not parse module?");
+    assert(!verifyModule(*M) && "Must have been well formed!");
+
+    runWithSE(*M, "test", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
+      auto &I = GetInstByName(F, "i");
+
+      auto *LoopHeaderBB = I.getParent();
+      auto *Loop = LI.getLoopFor(LoopHeaderBB);
+      PHINode *CanonicalIV = Loop->getCanonicalInductionVariable();
+      EXPECT_EQ(CanonicalIV, &GetInstByName(F, "canonical.iv"));
+
+      auto *AR = GetAddRec(SE, Loop);
+      EXPECT_FALSE(AR->isAffine());
+
+      unsigned ExpectedCanonicalIVWidth = SE.getTypeSizeInBits(AR->getType());
+      unsigned CanonicalIVBitWidth =
+          cast<IntegerType>(CanonicalIV->getType())->getBitWidth();
+      EXPECT_LT(CanonicalIVBitWidth, ExpectedCanonicalIVWidth);
+
+      SCEVExpander Exp(SE, M->getDataLayout(), "expander");
+      auto *InsertAt = I.getNextNode();
+      Value *V = Exp.expandCodeFor(AR, nullptr, InsertAt);
+      auto *ExpandedAR = SE.getSCEV(V);
+      // Check that the expansion happened literally.
+      EXPECT_EQ(AR, ExpandedAR);
+    });
+  };
+
+  // Expand the addrec produced by GetAddRec into a loop with a canonical IV
+  // of addrec width.
+  auto TestMatchingCanonicalIV = [&](
+      std::function<const SCEVAddRecExpr *(ScalarEvolution & SE, Loop * L)>
+          GetAddRec,
+      unsigned ARBitWidth) {
+    auto ARBitWidthTypeStr = "i" + std::to_string(ARBitWidth);
+    std::unique_ptr<Module> M = parseAssemblyString(
+        "define i32 @test(i32 %limit) { "
+        "entry: "
+        "  br label %loop "
+        "loop: "
+        "  %i = phi i32 [ 1, %entry ], [ %i.inc, %loop ] "
+        "  %canonical.iv = phi " + ARBitWidthTypeStr +
+            " [ 0, %entry ], [ %canonical.iv.inc, %loop ] "
+        "  %i.inc = add nsw i32 %i, 1 "
+        "  %canonical.iv.inc = add " + ARBitWidthTypeStr +
+            " %canonical.iv, 1 "
+        "  %cont = icmp slt i32 %i.inc, %limit "
+        "  br i1 %cont, label %loop, label %exit "
+        "exit: "
+        "  ret i32 %i.inc "
+        "}",
+        Err, C);
+
+    assert(M && "Could not parse module?");
+    assert(!verifyModule(*M) && "Must have been well formed!");
+
+    runWithSE(*M, "test", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
+      auto &I = GetInstByName(F, "i");
+      auto &CanonicalIV = GetInstByName(F, "canonical.iv");
+
+      auto *LoopHeaderBB = I.getParent();
+      auto *Loop = LI.getLoopFor(LoopHeaderBB);
+      EXPECT_EQ(&CanonicalIV, Loop->getCanonicalInductionVariable());
+      unsigned CanonicalIVBitWidth =
+          cast<IntegerType>(CanonicalIV.getType())->getBitWidth();
+
+      auto *AR = GetAddRec(SE, Loop);
+      EXPECT_FALSE(AR->isAffine());
+      EXPECT_EQ(ARBitWidth, SE.getTypeSizeInBits(AR->getType()));
+      EXPECT_EQ(CanonicalIVBitWidth, ARBitWidth);
+
+      SCEVExpander Exp(SE, M->getDataLayout(), "expander");
+      auto *InsertAt = I.getNextNode();
+      Value *V = Exp.expandCodeFor(AR, nullptr, InsertAt);
+      auto *ExpandedAR = SE.getSCEV(V);
+      // Check that the expansion happened literally.
+      EXPECT_EQ(AR, ExpandedAR);
+    });
+  };
+
+  unsigned ARBitWidth = 16;
+  Type *ARType = IntegerType::get(C, ARBitWidth);
+
+  // Expand {5,+,1,+,1}
+  auto GetAR3 = [&](ScalarEvolution &SE, Loop *L) -> const SCEVAddRecExpr * {
+    SmallVector<const SCEV *, 3> Ops = {SE.getConstant(APInt(ARBitWidth, 5)),
+                                        SE.getOne(ARType), SE.getOne(ARType)};
+    return cast<SCEVAddRecExpr>(SE.getAddRecExpr(Ops, L, SCEV::FlagAnyWrap));
+  };
+  TestNoCanonicalIV(GetAR3);
+  TestNarrowCanonicalIV(GetAR3);
+  TestMatchingCanonicalIV(GetAR3, ARBitWidth);
+
+  // Expand {5,+,1,+,1,+,1}
+  auto GetAR4 = [&](ScalarEvolution &SE, Loop *L) -> const SCEVAddRecExpr * {
+    SmallVector<const SCEV *, 4> Ops = {SE.getConstant(APInt(ARBitWidth, 5)),
+                                        SE.getOne(ARType), SE.getOne(ARType),
+                                        SE.getOne(ARType)};
+    return cast<SCEVAddRecExpr>(SE.getAddRecExpr(Ops, L, SCEV::FlagAnyWrap));
+  };
+  TestNoCanonicalIV(GetAR4);
+  TestNarrowCanonicalIV(GetAR4);
+  TestMatchingCanonicalIV(GetAR4, ARBitWidth);
+
+  // Expand {5,+,1,+,1,+,1,+,1}
+  auto GetAR5 = [&](ScalarEvolution &SE, Loop *L) -> const SCEVAddRecExpr * {
+    SmallVector<const SCEV *, 5> Ops = {SE.getConstant(APInt(ARBitWidth, 5)),
+                                        SE.getOne(ARType), SE.getOne(ARType),
+                                        SE.getOne(ARType), SE.getOne(ARType)};
+    return cast<SCEVAddRecExpr>(SE.getAddRecExpr(Ops, L, SCEV::FlagAnyWrap));
+  };
+  TestNoCanonicalIV(GetAR5);
+  TestNarrowCanonicalIV(GetAR5);
+  TestMatchingCanonicalIV(GetAR5, ARBitWidth);
+}
+
+
 }  // end anonymous namespace
 }  // end namespace llvm