[LV] Patch up induction phis after VPlan execution.

[fhahn]

Summary

This patch moves fixing up the incoming value of phis for
VPWidenIntOrFpInductionRecipes to after the VPlan is executed.

At the moment, the code in widenIntOrFpInduction relies on the vector
loop latch being created *before* the VPlan is executed. This prevents
us from modeling the vector latch, preheader and exit blocks in VPlan.

By patching up the incoming values for induction PHIs after VPlan
execution, we remove the need to create the latch up front. This enables
generating the vector latch directly from VPlan, which in turn is
required to enable modeling prehader and exit blocks.

The patch uses a workaround to access both the induction increment and
the vector phi for the recipe. It adds 2 new VPValues which are set to
them. While this is a temporary workaround, this will be removed once
the induction code generation is moved to work on VPlan more directly.
See D111303 for the next step, making the induction increment explicit
as VPValue operand.

[Ayal]

Would it be easier to first keep LastInduction in its original place in the header and then sink it to the latch as a VPlan-to-VPlan transformation after all blocks have been formed? Such a patch should refer to the original D22416.

[fhahn]

Rebased, all tests should be passing now!

In D113183#3146716, @Ayal wrote:

Would it be easier to first keep LastInduction in its original place in the header and then sink it to the latch as a VPlan-to-VPlan transformation after all blocks have been formed? Such a patch should refer to the original D22416.

In this patch, there is still no recipe to represent LastInduction, so unfortuantely I don't think it could be sunk just yet. But D113223 (next patch in stack after the current one) introduces new VPInstruction opcodes InductionIncrementNUW/InductionIncrement and uses them to explicitly model LastInduction.

he patch then can simplify add it to the last block of the plan. The exit condition & branch get a similar treatment in D113224.

[Ayal]

In D113183#3151729, @fhahn wrote:

Rebased, all tests should be passing now!

In D113183#3146716, @Ayal wrote:

Would it be easier to first keep LastInduction in its original place in the header and then sink it to the latch as a VPlan-to-VPlan transformation after all blocks have been formed? Such a patch should refer to the original D22416.

In this patch, there is still no recipe to represent LastInduction, so unfortuantely I don't think it could be sunk just yet. But D113223 (next patch in stack after the current one) introduces new VPInstruction opcodes InductionIncrementNUW/InductionIncrement and uses them to explicitly model LastInduction.

he patch then can simplify add it to the last block of the plan. The exit condition & branch get a similar treatment in D113224.

Yes, in order to sink LastInduction it should be wrapped in a recipe by itself, separating it from VPWidenIntOrFpInductionRecipe. Would introducing such a LastInduction recipe here, potentially created in FixHeaderPhis out of its feeding/consuming VPWidenIntOrFpInductionRecipe, be simpler for this patch? It needs only to take of

LastInduction = cast<Instruction>(
    Builder.CreateBinOp(AddOp, LastInduction, SplatVF, "step.add"));
LastInduction->setDebugLoc(EntryVal->getDebugLoc());

keeping VPWidenIntOrFpInductionRecipe with a single value Def.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

1167

Is this addition of excluding VPWidenIntOrFpInductionRecipe independent of this patch?

2413

PhiDef is redundant? VecInd is already being State.set above as part 0 of Def.

8715

This is when an induction feeds a reduction/FOR; the induction became a multi-valued def so we want to select its first, original value?

Perhaps Inductions should be treated as Reductions, included in PhisToFix, and their increment recipe introduced and rewired here?

IV isn't used, suffice to ask isa<>.

9075

(Related to introducing additional values to a Def; having no underlying values?)

llvm/lib/Transforms/Vectorize/VPlan.h

1058

who needs the II?

[fhahn]

Addressed comments and added a few additional code comments.

In D113183#3153076, @Ayal wrote:

Yes, in order to sink LastInduction it should be wrapped in a recipe by itself, separating it from VPWidenIntOrFpInductionRecipe. Would introducing such a LastInduction recipe here, potentially created in FixHeaderPhis out of its feeding/consuming VPWidenIntOrFpInductionRecipe, be simpler for this patch? It needs only to take of

I had a look, but unfortunately I don't think this is feasible additional work. The step increment value depends on the induction descriptor and may need to be expanded from a SCEV expression in the pre-header. Once we can model the preheader in VPlan, we can add a recipe in the preheader to create the step value.

Alternatively we could land D111303 first, which expands the step up front and maps it to a VPValue that can be used by the induction recipes. Please let me know if you prefer that direction.

A further complication is that LastInduction is also set for CastDef.

LastInduction = cast<Instruction>(
    Builder.CreateBinOp(AddOp, LastInduction, SplatVF, "step.add"));
LastInduction->setDebugLoc(EntryVal->getDebugLoc());

keeping VPWidenIntOrFpInductionRecipe with a single value Def.

Unfortunately VPWidenIntOrFpInductionRecipe is already a multi-def in some cases (due to handling casts as well).

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

1167

I think it makes sense to exclude it in any case, but it is becoming problematic with the patch (due to adding additional defs, causing a crash in `getUndderlyingValue). I *think* it could also cause issues if the induction recipe has a CastDef.

2413

Unfortunately Def may be reset to something other than the phi, e.g. in CreateSplatIV .

8715

I changed it to isa<>.

Perhaps Inductions should be treated as Reductions, included in PhisToFix, and their increment recipe introduced and rewired here?

Agreed, but could/should be a separate change?

9075

Yes.

llvm/lib/Transforms/Vectorize/VPlan.h

1058

No, it is a leftover from an earlier version. Removed all II-related changes.

[Ayal]

In D113183#3153441, @fhahn wrote:

Addressed comments and added a few additional code comments.

In D113183#3153076, @Ayal wrote:

Yes, in order to sink LastInduction it should be wrapped in a recipe by itself, separating it from VPWidenIntOrFpInductionRecipe. Would introducing such a LastInduction recipe here, potentially created in FixHeaderPhis out of its feeding/consuming VPWidenIntOrFpInductionRecipe, be simpler for this patch? It needs only to take of

I had a look, but unfortunately I don't think this is feasible additional work. The step increment value depends on the induction descriptor and may need to be expanded from a SCEV expression in the pre-header. Once we can model the preheader in VPlan, we can add a recipe in the preheader to create the step value.

OK.
There are actually two issues here: (1) sinking LastInduction to the latch, and (2) feeding LastInduction to the header phi as its operand associated with the latch.
Another temporary workaround may be have ILV::widenIntOrFpInduction() return the LastInduction it generates (in the header, w/o feeding it to the phi), and have VPWidenIntOrFpInductionRecipe record this LastInduction directly. Note that ILV::widenIntOrFpInduction() might not generate a LastInduction - when (unrolling w/o vectorizing) it does not call createVectorIntOrFpInductionPHI(). In such case VPWidenIntOrFpInductionRecipe should not be formed, right?

Alternatively we could land D111303 first, which expands the step up front and maps it to a VPValue that can be used by the induction recipes. Please let me know if you prefer that direction.

A further complication is that LastInduction is also set for CastDef.

LastInduction = cast<Instruction>(
    Builder.CreateBinOp(AddOp, LastInduction, SplatVF, "step.add"));
LastInduction->setDebugLoc(EntryVal->getDebugLoc());

keeping VPWidenIntOrFpInductionRecipe with a single value Def.

Unfortunately VPWidenIntOrFpInductionRecipe is already a multi-def in some cases (due to handling casts as well).

wonder how R->addOperand(IncR->getVPSingleValue()); currently works in fixHeaderPhis - is a testcase of a casted induction feeding a reduction is needed?

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

1167

Any other (header phi?) recipes worth excluding? (Independent of this patch)

2413

Unfortunately Def may be reset to something other than the phi, e.g. in CreateSplatIV .

This truly deserves simplification. Or at-least some explanation what Def refers to in contrast to PhiDef.

[fhahn]

In D113183#3157060, @Ayal wrote:

In D113183#3153441, @fhahn wrote:

Unfortunately VPWidenIntOrFpInductionRecipe is already a multi-def in some cases (due to handling casts as well).

wonder how R->addOperand(IncR->getVPSingleValue()); currently works in fixHeaderPhis - is a testcase of a casted induction feeding a reduction is needed?

It doesn't. I put up D114720 and D114739 to fix 2 crashes in this area.

[fhahn]

Simplify patch by only recording the 'LastInduction' instruction explicitly in the recipe, instead of adding additional defined values. Depends on D115112 which turns VPWidenIntOrFpInductionRecipe into a single-def recipe.

[fhahn]

rebased on top of 505ad03c7d29 ; ping :)

[fhahn]

ping :)

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

510–511

Document return value?

1167

Is there still a problem (due to additional def/cast)?
Prune/stop this backward slice at any header phi recipe?

2521–2523

{} can be dropped

8715

Can IncR->getVPSingleValue() be retained?

llvm/lib/Transforms/Vectorize/VPlan.cpp

849

Can VecInd be found instead by looking up State.get(IV..), as done for reductions and FOR rewired below?

llvm/lib/Transforms/Vectorize/VPlan.h

1015

Better rename LastInduction to "LastIncrementOfVectorIV", throughout?

Scalar IV's are generated w/o a cross-iteration increment, based off of Induction, which is pre-generated as part of the skeleton, along with its last increment in the latch.

An alternative of forming a Region with an Exit to represent the latch, is mentioned in D114586.

[fhahn]

Address latest comments, thanks!

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

510–511

Updated.

1167

Is there still a problem (due to additional def/cast)?

No, with the recent improvements to cast handling there are no changes needed here!

8715

yes!

llvm/lib/Transforms/Vectorize/VPlan.cpp

849

Unfortunately that isn't possible, because State.get(IV,...) may not refer to the phi directly but may be reset to something other than the phi, e.g. in CreateSplatIV

llvm/lib/Transforms/Vectorize/VPlan.h

1015

Better rename LastInduction to "LastIncrementOfVectorIV", throughout?

Done, thanks!

An alternative of forming a Region with an Exit to represent the latch, is mentioned in D114586.

I'll follow up on the suggestion, but I don't see how this is related directly to this patch. Future patches will remove the need to keeping the last induction increment here by modeling the increment explicitly in VPlan. But to support the general induction case, we need to support expand the step for the induction from a SCEV expression in the pre-header. I'll put patches up to do this once we can model the pre-header.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

2413

Add a comment that the other incoming will be added later?

2652

This State.set() seems to be the culprit.

llvm/lib/Transforms/Vectorize/VPlan.cpp

833

Augment above comment to also include induction phis?

849

State.get(IV->getVPSingleValue(), 0) does seem to provide the desired header phi, for non-scalable vectors. However, this State may indeed be reset for scalable vectors. Better to try and fix problems caused by resetting State, than to bypass them.

(CreateSplatIV() sets the State for IV rather than resets it, and only for scalar IV's. Here we're dealing with vector IV's).
This resetting stems from buildScalarSteps() in D98715, which resets the State for both scalar and vector IV's. The latter case resets per-part vectors only if they are scalable (and phi is not UAV). But if only a vector IV is needed, it is built w/o calling buildScalarSteps(), i.e., w/o resetting the State for IV. Why does build*Scalar*Steps() need to reset per-part vectors, only when scalar users are present?

If still needed, the actual PhiOfVectorIV could also be recorded alongside LastIncrementOfVectorIV, instead of tracking it down (or up). This could be done using a separate (derived) induction recipe for scalable vectors. In general, if multiple IR values associated with the same recipe need to be retrieved later to hook-up users and/or definitions, they could be modelled using a multi-VPValued VPDef.

854

LoopVectorLatch aka VectorLatchBB?
Rewiring of all header phi's should ideally look similar, as done below for reductions and FORs. Inductions should use their LastIncrement as Val, and are also SinglePartNeeded.

864

Keep this early-exit if !PhiR || !(FOR || Reduction || [Induction]) as the first thing in the loop?

llvm/lib/Transforms/Vectorize/VPlan.h

1015

An alternative of forming a Region with an Exit to represent the latch, is mentioned in D114586.

... how this is related directly to this patch

This alternative may have two (alternative?) parts:
Having the Exit VPBasicBlock available when creating header phi recipes will enable placing last increments there to begin with, instead of moving them (or their generated IR Instruction). This requires introducing recipes/VPInstructions to model these increments, as proposed in follow-up D113223, so indeed more directly related to that patch.
Having the IR Latch BasicBlock available when header phi recipes execute will enable them to generate their last increments and rewire them there and then, w/o needing to record and rewire later. This requires generating the IR basic block of the latch along with that of the header, presumably by VPRegionBase::execute(). But instead of having induction header-phi recipes be responsible for generating their entire chain of increments, it may be better if they behave like reduction and FOR header-phi recipes, whose 'previous' or last reduction operations have independent recipes; this supports a simple linear code-generation of VPlan, instead of moving a builder's insert position around.

[fhahn]

llvm/lib/Transforms/Vectorize/VPlan.h

1015

Patch to introduce header & latch up front is available now: D115793

I'll see how this may shake out in terms of simplifications here.

[fhahn]

AFAICT this was superseded by an alternative patch.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

public:
   /// inclusive. Uses the VPValue operands from \p RepRecipe instead of \p
   /// Instr's operands.
   void scalarizeInstruction(Instruction *Instr, VPReplicateRecipe *RepRecipe,
                             const VPIteration &Instance, bool IfPredicateInstr,
                             VPTransformState &State);
 
   /// Widen an integer or floating-point induction variable \p IV. If \p Trunc
   /// is provided, the integer induction variable will first be truncated to
   /// the corresponding type.
-  void widenIntOrFpInduction(PHINode *IV, const InductionDescriptor &ID,
-                             Value *Start, TruncInst *Trunc, VPValue *Def,
-                             VPTransformState &State);
+  /// Returns the last increment instruction of the vector induction, if one has
+  /// been created or nullptr otherwise.
+  Instruction *widenIntOrFpInduction(PHINode *IV, const InductionDescriptor &ID,
+                                     Value *Start, TruncInst *Trunc,
+                                     VPValue *Def, VPTransformState &State);
 
   /// Construct the vector value of a scalarized value \p V one lane at a time.
   void packScalarIntoVectorValue(VPValue *Def, const VPIteration &Instance,
                                  VPTransformState &State);
 
   /// Try to vectorize interleaved access group \p Group with the base address
   /// given in \p Addr, optionally masking the vector operations if \p
   /// BlockInMask is non-null. Use \p State to translate given VPValues to IR
void buildScalarSteps(Value *ScalarIV, Value *Step, Instruction *EntryVal,
                         const InductionDescriptor &ID, VPValue *Def,
                         VPTransformState &State);
 
   /// Create a vector induction phi node based on an existing scalar one. \p
   /// EntryVal is the value from the original loop that maps to the vector phi
   /// node, and \p Step is the loop-invariant step. If \p EntryVal is a
   /// truncate instruction, instead of widening the original IV, we widen a
   /// version of the IV truncated to \p EntryVal's type.
-  void createVectorIntOrFpInductionPHI(const InductionDescriptor &II,
+  Instruction *createVectorIntOrFpInductionPHI(const InductionDescriptor &II,
                                                Value *Step, Value *Start,
-                                       Instruction *EntryVal, VPValue *Def,
+                                               Instruction *EntryVal,
+                                               VPValue *Def,
                                                VPTransformState &State);
 
   /// Returns true if an instruction \p I should be scalarized instead of
   /// vectorized for the chosen vectorization factor.
   bool shouldScalarizeInstruction(Instruction *I) const;
 
   /// Returns true if we should generate a scalar version of \p IV.
   bool needsScalarInduction(Instruction *IV) const;
 
while (!Worklist.empty()) {
 
       if (!Visited.insert(CurRec).second)
         continue;
 
       // Prune search if we find another recipe generating a widen memory
       // instruction. Widen memory instructions involved in address computation
       // will lead to gather/scatter instructions, which don't need to be
       // handled.
       if (isa<VPWidenMemoryInstructionRecipe>(CurRec) ||
           isa<VPInterleaveRecipe>(CurRec))
         continue;
 
       // This recipe contributes to the address computation of a widen
       // load/store. Collect recipe if its underlying instruction has
       // poison-generating flags.
       Instruction *Instr = CurRec->getUnderlyingInstr();
       if (Instr && Instr->hasPoisonGeneratingFlags())
if (SafeToHoist)
     Builder.SetInsertPoint(LoopVectorPreHeader->getTerminator());
 
   // Broadcast the scalar into all locations in the vector.
   Value *Shuf = Builder.CreateVectorSplat(VF, V, "broadcast");
 
   return Shuf;
 }
 
-void InnerLoopVectorizer::createVectorIntOrFpInductionPHI(
+Instruction *InnerLoopVectorizer::createVectorIntOrFpInductionPHI(
     const InductionDescriptor &II, Value *Step, Value *Start,
     Instruction *EntryVal, VPValue *Def, VPTransformState &State) {
   IRBuilder<> &Builder = State.Builder;
   assert((isa<PHINode>(EntryVal) || isa<TruncInst>(EntryVal)) &&
          "Expected either an induction phi-node or a truncate of it!");
 
   // Construct the initial value of the vector IV in the vector loop preheader
   auto CurrIP = Builder.saveIP();
Value *SplatVF = isa<Constant>(Mul)
                        : Builder.CreateVectorSplat(State.VF, Mul);
   Builder.restoreIP(CurrIP);
 
   // We may need to add the step a number of times, depending on the unroll
   // factor. The last of those goes into the PHI.
   PHINode *VecInd = PHINode::Create(SteppedStart->getType(), 2, "vec.ind",
                                     &*LoopVectorBody->getFirstInsertionPt());
   VecInd->setDebugLoc(EntryVal->getDebugLoc());
-  Instruction *LastInduction = VecInd;
+  Instruction *LastIncrementOfVectorIV = VecInd;
   for (unsigned Part = 0; Part < UF; ++Part) {
-    State.set(Def, LastInduction, Part);
+    State.set(Def, LastIncrementOfVectorIV, Part);
 
     if (isa<TruncInst>(EntryVal))
-      addMetadata(LastInduction, EntryVal);
+      addMetadata(LastIncrementOfVectorIV, EntryVal);
 
-    LastInduction = cast<Instruction>(
-        Builder.CreateBinOp(AddOp, LastInduction, SplatVF, "step.add"));
-    LastInduction->setDebugLoc(EntryVal->getDebugLoc());
+    LastIncrementOfVectorIV = cast<Instruction>(Builder.CreateBinOp(
+        AddOp, LastIncrementOfVectorIV, SplatVF, "step.add"));
+    LastIncrementOfVectorIV->setDebugLoc(EntryVal->getDebugLoc());
   }
 
-  // Move the last step to the end of the latch block. This ensures consistent
-  // placement of all induction updates.
-  auto *LoopVectorLatch = LI->getLoopFor(LoopVectorBody)->getLoopLatch();
-  auto *Br = cast<BranchInst>(LoopVectorLatch->getTerminator());
-  auto *ICmp = cast<Instruction>(Br->getCondition());
-  LastInduction->moveBefore(ICmp);
-  LastInduction->setName("vec.ind.next");
-
+  LastIncrementOfVectorIV->setName("vec.ind.next");
   VecInd->addIncoming(SteppedStart, LoopVectorPreHeader);
-  VecInd->addIncoming(LastInduction, LoopVectorLatch);
+  return LastIncrementOfVectorIV;
 }
 
 bool InnerLoopVectorizer::shouldScalarizeInstruction(Instruction *I) const {
   return Cost->isScalarAfterVectorization(I, VF) ||
          Cost->isProfitableToScalarize(I, VF);
 }
 
 bool InnerLoopVectorizer::needsScalarInduction(Instruction *IV) const {
   if (shouldScalarizeInstruction(IV))
     return true;
   auto isScalarInst = [&](User *U) -> bool {
     auto *I = cast<Instruction>(U);
     return (OrigLoop->contains(I) && shouldScalarizeInstruction(I));
   };
   return llvm::any_of(IV->users(), isScalarInst);
 }
 
-void InnerLoopVectorizer::widenIntOrFpInduction(PHINode *IV,
-                                                const InductionDescriptor &ID,
-                                                Value *Start, TruncInst *Trunc,
-                                                VPValue *Def,
-                                                VPTransformState &State) {
+Instruction *InnerLoopVectorizer::widenIntOrFpInduction(
+    PHINode *IV, const InductionDescriptor &ID, Value *Start, TruncInst *Trunc,
+    VPValue *Def, VPTransformState &State) {
   IRBuilder<> &Builder = State.Builder;
   assert((IV->getType()->isIntegerTy() || IV != OldInduction) &&
          "Primary induction variable must have an integer type");
   assert(IV->getType() == ID.getStartValue()->getType() && "Types must match");
 
   // The value from the original loop to which we are mapping the new induction
   // variable.
   Instruction *EntryVal = Trunc ? cast<Instruction>(Trunc) : IV;
Instruction *InnerLoopVectorizer::widenIntOrFpInduction(
   if (ID.getInductionBinOp() && isa<FPMathOperator>(ID.getInductionBinOp()))
     Builder.setFastMathFlags(ID.getInductionBinOp()->getFastMathFlags());
 
   // Now do the actual transformations, and start with creating the step value.
   Value *Step = CreateStepValue(ID.getStep());
   if (State.VF.isZero() || State.VF.isScalar()) {
     Value *ScalarIV = CreateScalarIV(Step);
     CreateSplatIV(ScalarIV, Step);
-    return;
+    return nullptr;
   }
 
   // Determine if we want a scalar version of the induction variable. This is
   // true if the induction variable itself is not widened, or if it has at
   // least one user in the loop that is not widened.
   auto NeedsScalarIV = needsScalarInduction(EntryVal);
-  if (!NeedsScalarIV) {
-    createVectorIntOrFpInductionPHI(ID, Step, Start, EntryVal, Def, State);
-    return;
-  }
+  if (!NeedsScalarIV)
+    return createVectorIntOrFpInductionPHI(ID, Step, Start, EntryVal, Def,
+                                           State);
 
   // Try to create a new independent vector induction variable. If we can't
   // create the phi node, we will splat the scalar induction variable in each
   // loop iteration.
   if (!shouldScalarizeInstruction(EntryVal)) {
+    Instruction *LastIncrementOfVectorIV =
         createVectorIntOrFpInductionPHI(ID, Step, Start, EntryVal, Def, State);
     Value *ScalarIV = CreateScalarIV(Step);
     // Create scalar steps that can be used by instructions we will later
     // scalarize. Note that the addition of the scalar steps will not increase
     // the number of instructions in the loop in the common case prior to
     // InstCombine. We will be trading one vector extract for each scalar step.
     buildScalarSteps(ScalarIV, Step, EntryVal, ID, Def, State);
-    return;
+    return LastIncrementOfVectorIV;
   }
 
   // All IV users are scalar instructions, so only emit a scalar IV, not a
   // vectorised IV. Except when we tail-fold, then the splat IV feeds the
   // predicate used by the masked loads/stores.
   Value *ScalarIV = CreateScalarIV(Step);
   if (!Cost->isScalarEpilogueAllowed())
     CreateSplatIV(ScalarIV, Step);
   buildScalarSteps(ScalarIV, Step, EntryVal, ID, Def, State);
+  return nullptr;
 }
 
 Value *InnerLoopVectorizer::getStepVector(Value *Val, Value *StartIdx,
                                           Value *Step,
                                           Instruction::BinaryOps BinOp) {
   // Create and check the types.
   auto *ValVTy = cast<VectorType>(Val->getType());
   ElementCount VLen = ValVTy->getElementCount();
for (unsigned Part = 0; Part < State.UF; ++Part) {
 
     if (!IsUniform && State.VF.isScalable()) {
       auto *SplatStartIdx = Builder.CreateVectorSplat(State.VF, StartIdx0);
       auto *InitVec = Builder.CreateAdd(SplatStartIdx, UnitStepVec);
       if (ScalarIVTy->isFloatingPointTy())
         InitVec = Builder.CreateSIToFP(InitVec, VecIVTy);
       auto *Mul = Builder.CreateBinOp(MulOp, InitVec, SplatStep);
       auto *Add = Builder.CreateBinOp(AddOp, SplatIV, Mul);
       State.set(Def, Add, Part);
       // It's useful to record the lane values too for the known minimum number
       // of elements so we do those below. This improves the code quality when
       // trying to extract the first element, for example.
     }
 
     if (ScalarIVTy->isFloatingPointTy())
       StartIdx0 = Builder.CreateSIToFP(StartIdx0, ScalarIVTy);
 

 }
 
 void VPRecipeBuilder::fixHeaderPhis() {
   BasicBlock *OrigLatch = OrigLoop->getLoopLatch();
   for (VPWidenPHIRecipe *R : PhisToFix) {
     auto *PN = cast<PHINode>(R->getUnderlyingValue());
     VPRecipeBase *IncR =
         getRecipe(cast<Instruction>(PN->getIncomingValueForBlock(OrigLatch)));
     R->addOperand(IncR->getVPSingleValue());
   }
 }
 
 VPBasicBlock *VPRecipeBuilder::handleReplication(
     Instruction *I, VFRange &Range, VPBasicBlock *VPBB,
     VPlanPtr &Plan) {
   bool IsUniform = LoopVectorizationPlanner::getDecisionAndClampRange(
       [&](ElementCount VF) { return CM.isUniformAfterVectorization(I, VF); },
for (Instruction &I : BB->instructionsWithoutDebug()) {
           if (auto *R = dyn_cast_or_null<VPRecipeBase>(VPV->getDef()))
             RecipeBuilder.setRecipe(Instr, R);
           continue;
         }
         // Otherwise, add the new recipe.
         VPRecipeBase *Recipe = RecipeOrValue.get<VPRecipeBase *>();
         for (auto *Def : Recipe->definedValues()) {
           auto *UV = Def->getUnderlyingValue();
           Plan->addVPValue(UV, Def);
         }
 
         if (isa<VPWidenIntOrFpInductionRecipe>(Recipe) &&
             HeaderVPBB->getFirstNonPhi() != VPBB->end()) {
           // Keep track of VPWidenIntOrFpInductionRecipes not in the phi section
           // of the header block. That can happen for truncates of induction
           // variables. Those recipes are moved to the phi section of the header
           // block after applying SinkAfter, which relies on the original
for (unsigned Part = 0; Part < State.UF; ++Part) {
       State.set(this, NewGEP, Part);
       State.ILV->addMetadata(NewGEP, GEP);
     }
   }
 }
 
 void VPWidenIntOrFpInductionRecipe::execute(VPTransformState &State) {
   assert(!State.Instance && "Int or FP induction being replicated.");
-  State.ILV->widenIntOrFpInduction(IV, getInductionDescriptor(),
-                                   getStartValue()->getLiveInIRValue(),
-                                   getTruncInst(), getVPValue(0), State);
+  LastIncrementOfVectorIV = State.ILV->widenIntOrFpInduction(
+      IV, getInductionDescriptor(), getStartValue()->getLiveInIRValue(),
 }
 
 void VPWidenPHIRecipe::execute(VPTransformState &State) {
   State.ILV->widenPHIInstruction(cast<PHINode>(getUnderlyingValue()), this,
                                  State);
 }
 
 void VPBlendRecipe::execute(VPTransformState &State) {

llvm/lib/Transforms/Vectorize/VPlan.h

 };
 
 /// A recipe for handling phi nodes of integer and floating-point inductions,
 /// producing their vector and scalar values.
 class VPWidenIntOrFpInductionRecipe : public VPRecipeBase, public VPValue {
   PHINode *IV;
   const InductionDescriptor &IndDesc;
 
+  /// Pointer to the last vector induction increment generated for the recipe.
+  /// Null if no vector values have been generated. Note that this is a
+  /// temporary measure and only introduced  to facilitate the transition to
+  /// modeling the increment  explicitly in VPlan.
+  Instruction *LastIncrementOfVectorIV = nullptr;
+
 public:
   VPWidenIntOrFpInductionRecipe(PHINode *IV, VPValue *Start,
                                 const InductionDescriptor &IndDesc)
       : VPRecipeBase(VPWidenIntOrFpInductionSC, {Start}), VPValue(IV, this),
         IV(IV), IndDesc(IndDesc) {}
 
   VPWidenIntOrFpInductionRecipe(PHINode *IV, VPValue *Start,
                                 const InductionDescriptor &IndDesc,
#endif
   /// otherwise.
   TruncInst *getTruncInst() {
     return dyn_cast_or_null<TruncInst>(getVPValue(0)->getUnderlyingValue());
   }
   const TruncInst *getTruncInst() const {
     return dyn_cast_or_null<TruncInst>(getVPValue(0)->getUnderlyingValue());
   }
 
   /// Returns the induction descriptor for the recipe.
   const InductionDescriptor &getInductionDescriptor() const { return IndDesc; }
+
+  /// Return the last vector induction increment generated for the recipe.
+  Instruction *getLastIncrementOfVectorIV() { return LastIncrementOfVectorIV; }
 };
 
 /// A recipe for handling first order recurrences and pointer inductions. For
 /// first-order recurrences, the start value is the first operand of the recipe
 /// and the incoming value from the backedge is the second operand. It also
 /// serves as base class for VPReductionPHIRecipe. In the VPlan native path, all
 /// incoming VPValues & VPBasicBlock pairs are managed in the recipe directly.
 class VPWidenPHIRecipe : public VPRecipeBase, public VPValue {

llvm/lib/Transforms/Vectorize/VPlan.cpp

void VPlan::execute(VPTransformState *State) {
   State->CFG.PrevVPBB = nullptr;
   State->CFG.PrevBB = VectorHeaderBB;
   State->CFG.LastBB = VectorLatchBB;
 
   for (VPBlockBase *Block : depth_first(Entry))
     Block->execute(State);
 
   // Fix the latch value of reduction and first-order recurrences phis in the
   // vector loop.
   VPBasicBlock *Header = Entry->getEntryBasicBlock();
+  if (Header->empty()) {
+    assert(EnableVPlanNativePath);
+    Header = cast<VPBasicBlock>(Header->getSingleSuccessor());
+  }
   for (VPRecipeBase &R : Header->phis()) {
+    if (auto *IV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&R)) {
+      if (!IV->getLastIncrementOfVectorIV())
+        continue;
+      Instruction *LastIncrementOfVectorIV = IV->getLastIncrementOfVectorIV();
+      Instruction *Cur = LastIncrementOfVectorIV;
+      // Starting from LastIncrementOfVectorIV, Look through the operands until
+      // we found the starting phi.
+      while (!isa<PHINode>(Cur))
+        Cur = cast<Instruction>(Cur->getOperand(0));
+      PHINode *VecInd = cast<PHINode>(Cur);
+      // Move the last step to the end of the latch block. This ensures
+      // consistent
+      // placement of all induction updates.
+      auto *LoopVectorLatch =
+          State->LI->getLoopFor(State->CFG.PrevBB)->getLoopLatch();
+      auto *Br = cast<BranchInst>(LoopVectorLatch->getTerminator());
+      auto *ICmp = cast<Instruction>(Br->getCondition());
+      LastIncrementOfVectorIV->moveBefore(ICmp);
+
+      VecInd->addIncoming(LastIncrementOfVectorIV, LoopVectorLatch);
+      continue;
+    }
     auto *PhiR = dyn_cast<VPWidenPHIRecipe>(&R);
     if (!PhiR || !(isa<VPFirstOrderRecurrencePHIRecipe>(&R) ||
                    isa<VPReductionPHIRecipe>(&R)))
       continue;
     // For first-order recurrences and in-order reduction phis, only a single
     // part is generated, which provides the last part from the previous
     // iteration. Otherwise all UF parts are generated.
     bool SinglePartNeeded = isa<VPFirstOrderRecurrencePHIRecipe>(&R) ||
                             cast<VPReductionPHIRecipe>(&R)->isOrdered();
     unsigned LastPartForNewPhi = SinglePartNeeded ? 1 : State->UF;
     for (unsigned Part = 0; Part < LastPartForNewPhi; ++Part) {