[LV] Vectorize with FoldTail when Primary Induction is absent

[Ayal]

Summary

Introduce a new VPWidenPrimaryInductionRecipe to generate a vector primary
induction for use in fold-tail-with-masking when a scalar primary induction is
missing.

Follows approach (1) discussed in D76838.

[Ayal]

@SjoerdMeijer , test tail-folding-counting-down.ll introduced in D72324 now fails, as it can be vectorized with fold-tail, but is not vectorized due to cost. What's the intention of this test and how should it be changed?

[fhahn]

Thanks for the patch, Ayal!

I've put up D77577 yesterday to allow mapping the primary IV used to a different IR value during codegen as alternative, but I think adding the recipe is more straight forward in the end, as there is a single place we need to use the primary IV.

llvm/lib/Transforms/Vectorize/VPlan.h

333

Maybe include Vector in the name, e.g. VectorInduction, to avoid confusion with Legal's PrimaryInduction

1166

Comment needs updating.

[SjoerdMeijer]

I was also drafting a patch to implement this yesterday, and it was pretty much this! So I guess that's a good sign. :-)

@SjoerdMeijer , test tail-folding-counting-down.ll introduced in D72324 now fails, as it can be vectorized with fold-tail, but is not vectorized due to cost. What's the intention of this test and how should it be changed?

The purpose of this test was to catch a regression that we were seeing when tail-predication was rejected, but then incorrectly vectorisation also wasn't happening.
In this case, I think it is good to force vectorisation with a vectorisation vector of 4 or something along those lines. I was also modifying this test, but that will do for now, and then I will pick it up later.

[SjoerdMeijer]

I've applied the patch locally, and I'm a bit confused that test/Transforms/LoopVectorize/ARM/tail-folding-counting-down.ll doesn't fail for me, I will double check to see what's going on.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

6772

nit: perhaps this comments now needs to be moved to line 6782, and we need to say something new/extra about the primary IV?

llvm/lib/Transforms/Vectorize/VPlan.h

1153

nit: just curious, do we actually need this?

[Ayal]

In D77635#1966625, @SjoerdMeijer wrote:

I was also drafting a patch to implement this yesterday, and it was pretty much this! So I guess that's a good sign. :-)

@SjoerdMeijer , test tail-folding-counting-down.ll introduced in D72324 now fails, as it can be vectorized with fold-tail, but is not vectorized due to cost. What's the intention of this test and how should it be changed?

The purpose of this test was to catch a regression that we were seeing when tail-predication was rejected, but then incorrectly vectorisation also wasn't happening.
In this case, I think it is good to force vectorisation with a vectorisation vector of 4 or something along those lines. I was also modifying this test, but that will do for now, and then I will pick it up later.

Sorry for the confusion, was referring to the test under test/Transforms/LoopVectorize/ rather than the one under test/Transforms/LoopVectorize/ARM

OK, modified test to force vectorization with VF=4.

(Relevant for picking up later:) Note that llvm/test/Transforms/LoopVectorize/X86/small-size.ll also checks that a loop with reverse iv gets vectorized with fold-tail.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

6772

Added a line saying "Start by constructing the desired canonical IV."

llvm/lib/Transforms/Vectorize/VPlan.h

333

Agreed. Updated comment and changed name to VectorLoopScalarIV. Sounds better/ok?

Maybe better to avoid overloading the "PrimaryInduction" name throughout, keeping it with its original meaning only, and use "Canonical" instead.

1153

we need a VPValue; it could alternatively be owned by Plan, but seems better to hold it locally here.

[Ayal]

Addressed comments.

[SjoerdMeijer]

llvm/lib/Transforms/Vectorize/VPlan.h

333

We are well into bikeshedding territory now, but just one quick question. VectorLoopScalarIV describes well what this is I think, but was just wondering that if we refer to this as the canonical IV in comments, should this not be named something with CanonicalIV in it?

[fhahn]

LGTM, thanks.

llvm/lib/Transforms/Vectorize/VPlan.h

1148

nit: private not needed here, right? Classes should default to private

1149

Could be a unique_ptr?

[fhahn]

llvm/lib/Transforms/Vectorize/VPlan.h

1149

actually, the lifetime is directly tied to the recipe, right? So maybe no pointer is needed at all and we can just add a VPValue Val member?

[Ayal]

llvm/lib/Transforms/Vectorize/VPlan.h

333

Yes, I was wondering above if we should use (Scalar/Vector) CanonicalIV throughout, instead of overloading the original PrimaryInduction, which is absent... uploading another version to see how it looks.

1148

right, trying to be consistent...
They should all be dropped in a separate NFC patch.

1149

Right! Lifetimes are indeed tied; when the recipe turns into a VPInstruction, the VPValue will coincide with 'this'. Good catch.

[Ayal]

Address comments, use CanonicalIV instead of overloading the original PrimaryInduction term, update some comments.

[SjoerdMeijer]

Thanks for the patch, and I think CanonicalIV is an improvement.

This LGTM too.

llvm/test/Transforms/LoopVectorize/X86/small-size.ll

171

typo: it's -> its

[skatkov]

Hello @Ayal, unfortunately this patch causes the functional regression.
For the test below, vectorizer decided to vectorize inner loop by 32 while it has only a couple of iteration and it causes a miscompile.
Please fix it quickly or revert the patch.

The reproducer:

; ModuleID = './repro.ll'
source_filename = "./repro.ll"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128-ni:1-p2:32:8:8:32-ni:2"
target triple = "x86_64-unknown-linux-gnu"

@global = external global i8*

define void @hoge(i8* nonnull align 8 dereferenceable_or_null(8) %arg, i8* align 8 dereferenceable_or_null(16) %arg1) {
bb:
  %tmp = load atomic i8*, i8** @global unordered, align 8
  %tmp2 = getelementptr inbounds i8, i8* %tmp, i64 852
  br label %bb3

bb3:                                              ; preds = %bb12, %bb
  %tmp4 = phi i32 [ 1, %bb ], [ %tmp15, %bb12 ]
  %tmp5 = phi i32 [ 0, %bb ], [ %tmp8, %bb12 ]
  br label %bb7

bb6:                                              ; preds = %bb12
  ret void

bb7:                                              ; preds = %bb7, %bb3
  %tmp8 = phi i32 [ %tmp5, %bb3 ], [ %tmp10, %bb7 ]
  %tmp9 = phi i32 [ 1, %bb3 ], [ %tmp10, %bb7 ]
  %tmp10 = add nuw nsw i32 %tmp9, 1
  %tmp11 = icmp ugt i32 %tmp9, 5
  br i1 %tmp11, label %bb12, label %bb7

bb12:                                             ; preds = %bb7
  %tmp13 = mul i32 %tmp8, %tmp4
  %tmp14 = trunc i32 %tmp13 to i8
  fence release
  store atomic i8 %tmp14, i8* %tmp2 unordered, align 1
  fence seq_cst
  %tmp15 = add nuw nsw i32 %tmp4, 1
  %tmp16 = icmp ult i32 %tmp4, 240
  br i1 %tmp16, label %bb3, label %bb6
}

ran as

> opt -passes=loop-vectorize -S -o res.ll ./repro.ll

[Ayal]

In D77635#1979648, @skatkov wrote:

Hello @Ayal, unfortunately this patch causes the functional regression.
For the test below, vectorizer decided to vectorize inner loop by 32 while it has only a couple of iteration and it causes a miscompile.
Please fix it quickly or revert the patch.

The reproducer:

; ModuleID = './repro.ll'
source_filename = "./repro.ll"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128-ni:1-p2:32:8:8:32-ni:2"
target triple = "x86_64-unknown-linux-gnu"

@global = external global i8*

define void @hoge(i8* nonnull align 8 dereferenceable_or_null(8) %arg, i8* align 8 dereferenceable_or_null(16) %arg1) {
bb:
  %tmp = load atomic i8*, i8** @global unordered, align 8
  %tmp2 = getelementptr inbounds i8, i8* %tmp, i64 852
  br label %bb3

bb3:                                              ; preds = %bb12, %bb
  %tmp4 = phi i32 [ 1, %bb ], [ %tmp15, %bb12 ]
  %tmp5 = phi i32 [ 0, %bb ], [ %tmp8, %bb12 ]
  br label %bb7

bb6:                                              ; preds = %bb12
  ret void

bb7:                                              ; preds = %bb7, %bb3
  %tmp8 = phi i32 [ %tmp5, %bb3 ], [ %tmp10, %bb7 ]
  %tmp9 = phi i32 [ 1, %bb3 ], [ %tmp10, %bb7 ]
  %tmp10 = add nuw nsw i32 %tmp9, 1
  %tmp11 = icmp ugt i32 %tmp9, 5
  br i1 %tmp11, label %bb12, label %bb7

bb12:                                             ; preds = %bb7
  %tmp13 = mul i32 %tmp8, %tmp4
  %tmp14 = trunc i32 %tmp13 to i8
  fence release
  store atomic i8 %tmp14, i8* %tmp2 unordered, align 1
  fence seq_cst
  %tmp15 = add nuw nsw i32 %tmp4, 1
  %tmp16 = icmp ult i32 %tmp4, 240
  br i1 %tmp16, label %bb3, label %bb6
}

ran as

> opt -passes=loop-vectorize -S -o res.ll ./repro.ll

Thanks @skatkov. The test compiles for me, and the part that this patch introduces looks correct, but there seems to be a problem with how %tmp8 is handled - as a live-out first-order-recurrence which fold-tail does not handle (the compare it introduces is not used by anyone). To reproduce the bug w/o this patch, transform the loop iv %tmp9 to start at 0 and exit the loop when equal to 4 (instead of starting at 1 and exiting at 5), and add 1 to %tmp8. Would be good to open a PR.
Continuing to investigate.

[skatkov]

Thanks @skatkov. The test compiles for me, and the part that this patch introduces looks correct, but there seems to be a problem with how %tmp8 is handled - as a live-out first-order-recurrence which fold-tail does not handle (the compare it introduces is not used by anyone). To reproduce the bug w/o this patch, transform the loop iv %tmp9 to start at 0 and exit the loop when equal to 4 (instead of starting at 1 and exiting at 5), and add 1 to %tmp8. Would be good to open a PR.
Continuing to investigate.

Hi Ayal, thank you for information.
Indeed, I've reduced an original reproducer and found this patch as a first commit exposing the bug.
Would very appreciate if you could fix the real problem!

[skatkov]

PR filed: https://bugs.llvm.org/show_bug.cgi?id=45526

[SjoerdMeijer]

FYI: I have extracted the ARM test changes from D76838 and have committed that in 9633fc14aef7. Just saying also just in case you do end up reverting this, then that would need some changes. Probably the easiest is to change the check-prefixes to --check-prefixes=COMMON, because then it won't be checking much which is fine in that case; I will pick this up later, also because they will need some work later. I have a suspicion sgt_no_loopguard is miscompiled, but I need to look closer. Anyway, these were the tests that I thought were good to have, and with them in tree it is easier to talk about them.

Some of these tests also show that this change does not support some of the cases that was supported by D76838, and I will be looking at that, hence I will be touching test/Transforms/LoopVectorize/ARM/tail-folding-counting-down.ll again sooner or later.

[uabelho]

I wrote a PR about a crash that started happening with this patch:
https://bugs.llvm.org/show_bug.cgi?id=51614

llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp

bool LoopVectorizationLegality::canVectorize(bool UseVPlanNativePath) {
   // no restrictions.
   return Result;
 }
 
 bool LoopVectorizationLegality::prepareToFoldTailByMasking() {
 
   LLVM_DEBUG(dbgs() << "LV: checking if tail can be folded by masking.\n");
 
-  if (!PrimaryInduction) {
-    reportVectorizationFailure(
-        "No primary induction, cannot fold tail by masking",
-        "Missing a primary induction variable in the loop, which is "
-        "needed in order to fold tail by masking as required.",
-        "NoPrimaryInduction", ORE, TheLoop);
-    return false;
-  }
-
   SmallPtrSet<const Value *, 8> ReductionLiveOuts;
 
   for (auto &Reduction : getReductionVars())
     ReductionLiveOuts.insert(Reduction.second.getLoopExitInstr());
 
   // TODO: handle non-reduction outside users when tail is folded by masking.
   for (auto *AE : AllowedExit) {
     // Check that all users of allowed exit values are inside the loop or

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

void LoopVectorizationPlanner::executePlan(InnerLoopVectorizer &ILV,
   // 1. Create a new empty loop. Unlink the old loop and connect the new one.
   VPCallbackILV CallbackILV(ILV);
 
   VPTransformState State{BestVF, BestUF,      LI,
                          DT,     ILV.Builder, ILV.VectorLoopValueMap,
                          &ILV,   CallbackILV};
   State.CFG.PrevBB = ILV.createVectorizedLoopSkeleton();
   State.TripCount = ILV.getOrCreateTripCount(nullptr);
+  State.CanonicalIV = ILV.Induction;
 
   //===------------------------------------------------===//
   //
   // Notice: any optimization or new instruction that go
   // into the code below should also be implemented in
   // the cost-model.
   //
   //===------------------------------------------------===//
VPValue *VPRecipeBuilder::createBlockInMask(BasicBlock *BB, VPlanPtr &Plan) {
   // All-one mask is modelled as no-mask following the convention for masked
   // load/store/gather/scatter. Initialize BlockMask to no-mask.
   VPValue *BlockMask = nullptr;
 
   if (OrigLoop->getHeader() == BB) {
     if (!CM.blockNeedsPredication(BB))
       return BlockMaskCache[BB] = BlockMask; // Loop incoming mask is all-one.
 
     // Introduce the early-exit compare IV <= BTC to form header block mask.
     // This is used instead of IV < TC because TC may wrap, unlike BTC.
-    VPValue *IV = Plan->getVPValue(Legal->getPrimaryInduction());
+    // Start by constructing the desired canonical IV.
+    VPValue *IV = nullptr;
+    if (Legal->getPrimaryInduction())
+      IV = Plan->getVPValue(Legal->getPrimaryInduction());
+    else {
+      auto IVRecipe = new VPWidenCanonicalIVRecipe();
+      Builder.getInsertBlock()->appendRecipe(IVRecipe);
+      IV = IVRecipe->getVPValue();
+    }
     VPValue *BTC = Plan->getOrCreateBackedgeTakenCount();
     BlockMask = Builder.createNaryOp(VPInstruction::ICmpULE, {IV, BTC});
     return BlockMaskCache[BB] = BlockMask;
   }
 
   // This is the block mask. We OR all incoming edges.
   for (auto *Predecessor : predecessors(BB)) {
     VPValue *EdgeMask = createEdgeMask(Predecessor, BB, Plan);
void LoopVectorizationPlanner::buildVPlansWithVPRecipes(unsigned MinVF,
   for (BasicBlock *BB : OrigLoop->blocks()) {
     if (BB == Latch)
       continue;
     BranchInst *Branch = dyn_cast<BranchInst>(BB->getTerminator());
     if (Branch && Branch->isConditional())
       NeedDef.insert(Branch->getCondition());
   }
 
-  // If the tail is to be folded by masking, the primary induction variable
-  // needs to be represented in VPlan for it to model early-exit masking.
+  // If the tail is to be folded by masking, the primary induction variable, if
+  // exists needs to be represented in VPlan for it to model early-exit masking.
   // Also, both the Phi and the live-out instruction of each reduction are
   // required in order to introduce a select between them in VPlan.
   if (CM.foldTailByMasking()) {
+    if (Legal->getPrimaryInduction())
       NeedDef.insert(Legal->getPrimaryInduction());
     for (auto &Reduction : Legal->getReductionVars()) {
       NeedDef.insert(Reduction.first);
       NeedDef.insert(Reduction.second.getLoopExitInstr());
     }
   }
 
   // Collect instructions from the original loop that will become trivially dead
   // in the vectorized loop. We don't need to vectorize these instructions. For
static ScalarEpilogueLowering getScalarEpilogueLowering(
   // don't look at hints or options, and don't request a scalar epilogue.
   if (OptSize && Hints.getForce() != LoopVectorizeHints::FK_Enabled)
     return CM_ScalarEpilogueNotAllowedOptSize;
 
   bool PredicateOptDisabled = PreferPredicateOverEpilog.getNumOccurrences() &&
                               !PreferPredicateOverEpilog;
 
   // 2) Next, if disabling predication is requested on the command line, honour
-  // this and request a scalar epilogue. Also do this if we don't have a
-  // primary induction variable, which is required for predication.
-  if (PredicateOptDisabled || !LVL.getPrimaryInduction())
+  // this and request a scalar epilogue.
+  if (PredicateOptDisabled)
     return CM_ScalarEpilogueAllowed;
 
   // 3) and 4) look if enabling predication is requested on the command line,
   // with a loop hint, or if the TTI hook indicates this is profitable, request
   // predication .
   if (PreferPredicateOverEpilog ||
       Hints.getPredicate() == LoopVectorizeHints::FK_Enabled ||
       (TTI->preferPredicateOverEpilogue(L, LI, *SE, *AC, TLI, DT,

llvm/lib/Transforms/Vectorize/VPlan.h

struct VPTransformState {
   /// Hold a reference to the Value state information used when generating the
   /// Values of the output IR.
   VectorizerValueMap &ValueMap;
 
   /// Hold a reference to a mapping between VPValues in VPlan and original
   /// Values they correspond to.
   VPValue2ValueTy VPValue2Value;
 
+  /// Hold the canonical scalar IV of the vector loop (start=0, step=VF*UF).
+  Value *CanonicalIV = nullptr;
+
   /// Hold the trip count of the scalar loop.
   Value *TripCount = nullptr;
 
   /// Hold a pointer to InnerLoopVectorizer to reuse its IR generation methods.
   InnerLoopVectorizer *ILV;
 
   VPCallback &Callback;
 };
public:
   using VPRecipeTy = enum {
     VPBlendSC,
     VPBranchOnMaskSC,
     VPInstructionSC,
     VPInterleaveSC,
     VPPredInstPHISC,
     VPReplicateSC,
     VPWidenCallSC,
+    VPWidenCanonicalIVSC,
     VPWidenGEPSC,
     VPWidenIntOrFpInductionSC,
     VPWidenMemoryInstructionSC,
     VPWidenPHISC,
     VPWidenSC,
   };
 
   VPRecipeBase(const unsigned char SC) : SubclassID(SC) {}
public:
   /// Generate the wide load/store.
   void execute(VPTransformState &State) override;
 
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
 };
 
+/// A Recipe for widening the canonical induction variable of the vector loop.
+class VPWidenCanonicalIVRecipe : public VPRecipeBase {
+private:
+  /// A VPValue representing the canonical vector IV.
+  VPValue Val;
+
+public:
+  VPWidenCanonicalIVRecipe() : VPRecipeBase(VPWidenCanonicalIVSC) {}
+  ~VPWidenCanonicalIVRecipe() override = default;
+
+  /// Return the VPValue representing the canonical vector induction variable of
+  /// the vector loop.
+  const VPValue *getVPValue() const { return &Val; }
+  VPValue *getVPValue() { return &Val; }
+
+  /// Method to support type inquiry through isa, cast, and dyn_cast.
+  static inline bool classof(const VPRecipeBase *V) {
+    return V->getVPRecipeID() == VPRecipeBase::VPWidenCanonicalIVSC;
+  }
+
+  /// Generate a canonical vector induction variable of the vector loop, with
+  /// start = {<Part*VF, Part*VF+1, ..., Part*VF+VF-1> for 0 <= Part < UF}, and
+  /// step = <VF*UF, VF*UF, ..., VF*UF>.
+  void execute(VPTransformState &State) override;
+
+  /// Print the recipe.
+  void print(raw_ostream &O, const Twine &Indent,
+             VPSlotTracker &SlotTracker) const override;
+};
+
 /// VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph. It
 /// holds a sequence of zero or more VPRecipe's each representing a sequence of
 /// output IR instructions.
 class VPBasicBlock : public VPBlockBase {
 public:
   using RecipeListTy = iplist<VPRecipeBase>;
 
 private:

llvm/lib/Transforms/Vectorize/VPlan.cpp

void VPWidenMemoryInstructionRecipe::print(raw_ostream &O, const Twine &Indent,
   VPValue *Mask = getMask();
   if (Mask) {
     O << ", ";
     Mask->printAsOperand(O, SlotTracker);
   }
   O << "\\l\"";
 }
 
+void VPWidenCanonicalIVRecipe::execute(VPTransformState &State) {
+  Value *CanonicalIV = State.CanonicalIV;
+  Type *STy = CanonicalIV->getType();
+  IRBuilder<> Builder(State.CFG.PrevBB->getTerminator());
+  Value *VStart = Builder.CreateVectorSplat(State.VF, CanonicalIV, "broadcast");
+  for (unsigned Part = 0, UF = State.UF; Part < UF; ++Part) {
+    SmallVector<Constant *, 8> Indices;
+    for (unsigned Lane = 0, VF = State.VF; Lane < VF; ++Lane)
+      Indices.push_back(ConstantInt::get(STy, Part * VF + Lane));
+    Constant *VStep = ConstantVector::get(Indices);
+    // Add the consecutive indices to the vector value.
+    Value *CanonicalVectorIV = Builder.CreateAdd(VStart, VStep, "vec.iv");
+    State.set(getVPValue(), CanonicalVectorIV, Part);
+  }
+}
+
+void VPWidenCanonicalIVRecipe::print(raw_ostream &O, const Twine &Indent,
+                                     VPSlotTracker &SlotTracker) const {
+  O << " +\n" << Indent << "\"EMIT ";
+  getVPValue()->printAsOperand(O, SlotTracker);
+  O << " = WIDEN-CANONICAL-INDUCTION \\l\"";
+}
+
 template void DomTreeBuilder::Calculate<VPDominatorTree>(VPDominatorTree &DT);
 
 void VPValue::replaceAllUsesWith(VPValue *New) {
   for (VPUser *User : users())
     for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I)
       if (User->getOperand(I) == this)
         User->setOperand(I, New);
 }
void VPSlotTracker::assignSlots(const VPRegionBlock *Region) {
   for (const VPBlockBase *Block : RPOT)
     assignSlots(Block);
 }
 
 void VPSlotTracker::assignSlots(const VPBasicBlock *VPBB) {
   for (const VPRecipeBase &Recipe : *VPBB) {
     if (const auto *VPI = dyn_cast<VPInstruction>(&Recipe))
       assignSlot(VPI);
+    else if (const auto *VPIV = dyn_cast<VPWidenCanonicalIVRecipe>(&Recipe))
+      assignSlot(VPIV->getVPValue());
   }
 }
 
 void VPSlotTracker::assignSlots(const VPlan &Plan) {
 
   for (const VPValue *V : Plan.VPExternalDefs)
     assignSlot(V);
 

llvm/test/Transforms/LoopVectorize/X86/small-size.ll

.lr.ph:                                           ; preds = %.preheader, %.lr.ph
   %indvars.iv.next = add i64 %indvars.iv, 1
   %11 = icmp eq i32 %4, 0
   br i1 %11, label %._crit_edge, label %.lr.ph
 
 ._crit_edge:                                      ; preds = %.lr.ph, %.preheader
   ret void
 }
 
-; N is unknown, we need a tail. Can't vectorize because loop has no primary
-; induction.
+; Loop has no primary induction as it's integer IV has step -1 starting at
+; unknown N, but can still be vectorized.
 ;CHECK-LABEL: @example3(
+; CHECK:       vector.ph:
+; CHECK:    [[BROADCAST_SPLAT2:%.*]] = shufflevector <4 x i64> {{.*}}, <4 x i64> undef, <4 x i32> zeroinitializer
+; CHECK:       vector.body:
+; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0,
+; CHECK-NEXT:    [[BROADCAST_SPLATINSERT:%.*]] = insertelement <4 x i64> undef, i64 [[INDEX]], i32 0
+; CHECK-NEXT:    [[BROADCAST_SPLAT:%.*]] = shufflevector <4 x i64> [[BROADCAST_SPLATINSERT]], <4 x i64> undef, <4 x i32> zeroinitializer
+; CHECK-NEXT:    [[VPIV:%.*]] = or <4 x i64> [[BROADCAST_SPLAT]], <i64 0, i64 1, i64 2, i64 3>
+; CHECK:    {{.*}} = icmp ule <4 x i64> [[VPIV]], [[BROADCAST_SPLAT2]]
 ;CHECK-NOT: <4 x i32>
 ;CHECK: ret void
 define void @example3(i32 %n, i32* noalias nocapture %p, i32* noalias nocapture %q) optsize {
   %1 = icmp eq i32 %n, 0
   br i1 %1, label %._crit_edge, label %.lr.ph
 
 .lr.ph:                                           ; preds = %0, %.lr.ph
   %.05 = phi i32 [ %2, %.lr.ph ], [ %n, %0 ]

 ; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i16* [[NEXT_GEP]] to <4 x i16>*
 ; CHECK-NEXT:    [[WIDE_LOAD:%.*]] = load <4 x i16>, <4 x i16>* [[TMP1]], align 2
 ; CHECK-NEXT:    [[TMP2:%.*]] = zext <4 x i16> [[WIDE_LOAD]] to <4 x i32>
 ; CHECK-NEXT:    [[TMP3:%.*]] = shl nuw nsw <4 x i32> [[TMP2]], <i32 7, i32 7, i32 7, i32 7>
 ; CHECK-NEXT:    [[TMP4:%.*]] = bitcast i32* [[NEXT_GEP4]] to <4 x i32>*
 ; CHECK-NEXT:    store <4 x i32> [[TMP3]], <4 x i32>* [[TMP4]], align 4
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add i64 [[INDEX]], 4
 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i64 [[INDEX_NEXT]], 256
-; CHECK-NEXT:    br i1 [[TMP5]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop !6
+; CHECK-NEXT:    br i1 [[TMP5]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop !10
 ; CHECK:       middle.block:
 ; CHECK-NEXT:    br i1 true, label [[TMP7:%.*]], label [[SCALAR_PH]]
 ; CHECK:       scalar.ph:
 ; CHECK-NEXT:    br label [[TMP6:%.*]]
-; CHECK:         br i1 undef, label [[TMP7]], label [[TMP6]], !llvm.loop !7
+; CHECK:         br i1 undef, label [[TMP7]], label [[TMP6]], !llvm.loop !11
 ; CHECK:         ret void
 ;
   br label %1
 
 ; <label>:1                                       ; preds = %1, %0
   %.04 = phi i16* [ %src, %0 ], [ %2, %1 ]
   %.013 = phi i32* [ %dst, %0 ], [ %6, %1 ]
   %i.02 = phi i32 [ 0, %0 ], [ %7, %1 ]

 ; CHECK-NEXT:    [[TMP30:%.*]] = shl nuw nsw i32 [[TMP29]], 7
 ; CHECK-NEXT:    [[TMP31:%.*]] = or i64 [[INDEX]], 3
 ; CHECK-NEXT:    [[NEXT_GEP10:%.*]] = getelementptr i32, i32* [[DST]], i64 [[TMP31]]
 ; CHECK-NEXT:    store i32 [[TMP30]], i32* [[NEXT_GEP10]], align 4
 ; CHECK-NEXT:    br label [[PRED_STORE_CONTINUE22]]
 ; CHECK:       pred.store.continue22:
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add i64 [[INDEX]], 4
 ; CHECK-NEXT:    [[TMP32:%.*]] = icmp eq i64 [[INDEX_NEXT]], 260
-; CHECK-NEXT:    br i1 [[TMP32]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop !8
+; CHECK-NEXT:    br i1 [[TMP32]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop !12
 ; CHECK:       middle.block:
 ; CHECK-NEXT:    br i1 true, label [[TMP34:%.*]], label [[SCALAR_PH]]
 ; CHECK:       scalar.ph:
 ; CHECK-NEXT:    br label [[TMP33:%.*]]
-; CHECK:         br i1 undef, label [[TMP34]], label [[TMP33]], !llvm.loop !9
+; CHECK:         br i1 undef, label [[TMP34]], label [[TMP33]], !llvm.loop !13
 ; CHECK:         ret void
 ;
   br label %1
 
 ; <label>:1                                       ; preds = %1, %0
   %.04 = phi i16* [ %src, %0 ], [ %2, %1 ]
   %.013 = phi i32* [ %dst, %0 ], [ %6, %1 ]
   %i.02 = phi i64 [ 0, %0 ], [ %7, %1 ]

llvm/test/Transforms/LoopVectorize/tail-folding-counting-down.ll

-; RUN: opt < %s -loop-vectorize -prefer-predicate-over-epilog -S | FileCheck %s
+; RUN: opt < %s -loop-vectorize -prefer-predicate-over-epilog -force-vector-width=4 -S | FileCheck %s
 
-; Check that when we can't predicate this loop that it is still vectorised (with
-; an epilogue).
-; TODO: the reason this can't be predicated is because a primary induction
-; variable can't be found (not yet) for this counting down loop. But with that
-; fixed, this should be able to be predicated.
+; Check that a counting-down loop which has no primary induction variable
+; is vectorized with preferred predication.
 
 ; CHECK-LABEL: vector.body:
+; CHECK-LABEL: middle.block:
+; CHECK-NEXT:    br i1 true,
 
 target datalayout = "e-m:e-p:32:32-Fi8-i64:64-v128:64:128-a:0:32-n32-S64"
 
 define dso_local void @foo(i8* noalias nocapture readonly %A, i8* noalias nocapture readonly %B, i8* noalias nocapture %C, i32 %N) {
 entry:
   %cmp6 = icmp eq i32 %N, 0
   br i1 %cmp6, label %while.end, label %while.body.preheader