[LV] Perform recurrence sinking directly on VPlan.

[fhahn]

Summary

This patch updates LV to sink recipes directly using the VPlan use
chains. The initial patch only moves sinking to be purely VPlan-based.
Follow-up patches will move legality checks to VPlan as well.

At the moment, there's a single test failure remaining.

[fhahn]

Fix remaining erros, refactor. Should be ready for review now.

[Ayal]

A very nice step forward! Raises a few thoughts regarding recipes of predicated instructions, arguably independent of the patch.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8929

Comment above deserves update.

8975

nit: FOR now stands for FixedOrderRecurrence which leads to fixFixedOrderRecurrences() ... how about addSplicesToFixedOrderRecurrences()?

llvm/lib/Transforms/Vectorize/VPlan.h

1262

redundant - aka VPHeaderPHIRecipe::getBackedgeValue()?

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

15

nit: lex order?

552

aka dominates?

Note for completeness: a recipe is considered to dominate itself, i.e., returns true if the same recipe is passed as both A and B.

579

This checking of regions is needed rather than recipeComesBefore()'s checking of parenting basic blocks, because neither basic block dominates the other when they reside in replicate regions? What if only A resides inside a replicate region?
When two recipes belong to the same block, their dominance is clear. Otherwise, if any recipe resides inside a replicate region, should the exit block of the replicate region be considered instead of its parenting basic block? Thereby collapsing the region into a node, or considering a pred-inst-phi instead of its pred-inst.

609

nit: assert with an error message that Current has at most a single value?

622

Clearly SinkCandidate should not be sunk past any of its operands, but this is a bit confusing: Curr dominates SinkCandidate by definition of being its operand, so if Previous=Target dominates Curr it follows that Previous dominates SinkCandidate - however such SinkCandidates are filtered from entering InstrsToSink?

700

(Independent of this patch) Another way of thinking about this: if Previous resides inside a replicate region, treat its pred-inst-phi as if it were Previous? Indeed, such a predicated instruction does not dominate the latch...

703

(Independent of this patch) Should this be under the if (Region)? I.e., Previous surely has a VPBasicBlock parent, and Region has a single successor, but the latter could potentially be a region rather than a VPBasicBlock?

707

hmm, could Previous be a header phi (i.e., induction, given that reductions feed only themselves inside the loop, and we exhausted all FOR's), or is this checking for blend/pred-inst-phi's?

714

(Independent of this patch) Note that if FOR->getBackedgeValue() differs from Previous then it is a FOR header phi, so in any case it will dominate RecurSplice.

llvm/lib/Transforms/Vectorize/VPlanTransforms.h

27

nit: place last to try and keep lex order?

[fhahn]

Address latest comments, thanks! I think it would be good to address the independent comments once the new sinking code has settled in.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8929

Done, thanks!

8975

Updated to adjustFixedOrderRecurrences, as it also requires sinking. WDYT?

llvm/lib/Transforms/Vectorize/VPlan.h

1262

Ah yes, removed!

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

15

moved, I am not sure why clang-format didn't fix it

552

Renamed! Might make sense to move it to VPDominatorTree eventually, but probably best to avoid the linear scan

579

Adjusted! I also updated the code to not use a set but just sort the vector once after building the list.

609

Added, thanks! It might simplify things if we would provide VPRecipeBase::users() as follow-up

622

This is not needed as long as we keep the recipes to sink in dominance order. This should ensure that we can just update Previous = SinkCandidate. When looking at the operands, an operand may temporarily not dominate SInkCandidate, as it has already been moved past previous.

707

It is checking for header phis, can adjust once the new sinking code has settled in?

llvm/lib/Transforms/Vectorize/VPlanTransforms.h

27

Reordered, thanks!

[Ayal]

In D142589#4094683, @fhahn wrote:

Address latest comments, thanks! I think it would be good to address the independent comments once the new sinking code has settled in.

Sure, also raises the thought of initially representing predicated regions as recipes when dealing with dominance and sinking/motion, then expand them to replicated regions before sinking scalars and code generation.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8975

Very good. A comment may help explain what adjust stands for.

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

15

still one out of place?

562

How about something like:

auto *ParentA = A->getParent();
auto *ParentB = B->getParent();
if (ParentA == ParentB)
  return LocalComesBefore(A, B);

auto *RegionA = GetReplicateRegion(const_cast<VPRecipeBase *>(A));
auto *RegionB = GetReplicateRegion(const_cast<VPRecipeBase *>(B));
if (RegionA)
  ParentA = RegionA->getExiting();
if (RegionB)
  ParentB = RegionB->getExiting();
return VPDT.dominates(ParentA, ParentB);

578

RecipesToSink should be defined next to WorkList, or folded to reuse WorkList or Seen instead: RecipesToSink is a copy of WorkList excluding initial FOR and all VPPredInstPHIRecipes - these can alternatively be ignored when traversing RecipesToSink. See below regarding using Seen instead of RecipesToSink.

607

Recipes to sink are already held in a set: can Seen be set to use this order and serve as RecipesToSink?

611

What if RegionA but not RegionB or vise versa? Should fold the replicate region logic into dominates() above?

[fhahn]

Address latest comments, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

15

argh yes, fixed!

562

Adjusted, thanks!

578

Yeah, updated to ignore the reciepes instead and used WorkList.

607

SmallPtrSet and SetVector cannot be sorted unfortunately. Updated to use WorkList.

611

Adjusted as above, thanks!

[Ayal]

This looks good to me, thanks! Adding couple of final nits.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8973

(Independent of this patch) Can/Should adjustRecipesForReductions() be moved to VPlanTransforms?

8975

Worth documenting what adjustFixedOrderRecurrences() does.

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

15

ah, includes still seem out of lex order (they're not quite in order w/o the patch).

589

Worth asserting SinkCandidate != Previous? FORs shouldn't close a dependence cycle.

607

Thought was to use some other set with "compare" set to dominance order (std::set? Admittedly not SmallPtrSet) to indicate which candidates were already seen and to later traverse them in the desired order.

llvm/lib/Transforms/Vectorize/VPlanTransforms.h

81

Better keep optimizeForVFAndUF() last, as it operates after BestVP and BestUF have been chosen?

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8973

Unfortunately the function still uses the cost model in multiple places; some should be relatively straight-forward to replace as a first step though.

8975

Done, also added a comment to VPlanTransforms.h

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

15

Yes, I think that was why clang-format moved it out-of-place. Will fix separately.

589

Added, thanks!

llvm/lib/Transforms/Vectorize/VPlanTransforms.h

81

Will do.

[dmgreen]

Hello. We started hitting an infinite recursion in a PGO build after this. There is code to reproduce it in https://godbolt.org/z/EcvM8cGoK, hopefully.

[fhahn]

In D142589#4122597, @dmgreen wrote:

Hello. We started hitting an infinite recursion in a PGO build after this. There is code to reproduce it in https://godbolt.org/z/EcvM8cGoK, hopefully.

Thanks! Should be fixed in af3c25dc3d87

[ashay-github]

@fhahn, This patch is causing a Windows Debug build (with VS 2022 MSVC 19.34.31937) of opt to crash for the llvm\test\Transforms\LoopVectorize\first-order-recurrence-sink-replicate-region.ll test (see stack trace below). Sadly, the fix in commit af3c25dc does not resolve the problem. I (locally) reverted this patch and validated that the crash is resolved.

Here is a partial stack trace. Could you revert / fix this crash soon?

0.      Program arguments: build\bin\opt.exe -passes=loop-vectorize -force-vector-width=2 -force-vector-interleave=1 -force-widen-divrem-via-safe-divisor=0 -disable-output -debug-only=loop-vectorize llvm\test\Transforms\LoopVectorize\first-order-recurrence-sink-replicate-region.ll

Exception Code: 0x80000003

 #0 0x00007ff60564a39a std::_Debug_lt_pred<`sinkRecurrenceUsersAfterPrevious'::`2'::<lambda_2> &,llvm::VPRecipeBase * &,llvm::VPRecipeBase * &,0> C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.34.31933\include\xutility:1096:0

 #1 0x00007ff60564b8da std::_Insertion_sort_unchecked<llvm::VPRecipeBase * *,`sinkRecurrenceUsersAfterPrevious'::`2'::<lambda_2> > C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.34.31933\include\algorithm:7519:0

 #2 0x00007ff60564c82d std::_Sort_unchecked<llvm::VPRecipeBase * *,`sinkRecurrenceUsersAfterPrevious'::`2'::<lambda_2> > C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.34.31933\include\algorithm:7640:0

 #3 0x00007ff605650b39 std::sort<llvm::VPRecipeBase * *,`sinkRecurrenceUsersAfterPrevious'::`2'::<lambda_2> > C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.34.31933\include\algorithm:7670:0

 #4 0x00007ff605650aa8 llvm::sort<llvm::VPRecipeBase * *,`sinkRecurrenceUsersAfterPrevious'::`2'::<lambda_2> > llvm-project\llvm\include\llvm\ADT\STLExtras.h:1706:0

 #5 0x00007ff605650a61 llvm::sort<llvm::SmallVector<llvm::VPRecipeBase *,6> &,`sinkRecurrenceUsersAfterPrevious'::`2'::<lambda_2> > llvm-project\llvm\include\llvm\ADT\STLExtras.h:1711:0

 #6 0x00007ff6056448c3 sinkRecurrenceUsersAfterPrevious llvm-project\llvm\lib\Transforms\Vectorize\VPlanTransforms.cpp:619:0

 ...

EDIT: For some context, here is the function in the xutility file where the crash occurs (the failure is in the call to _STL_VERIFY):

template <class _Pr, class _Ty1, class _Ty2,
    enable_if_t<is_same_v<_Remove_cvref_t<_Ty1>, _Remove_cvref_t<_Ty2>>, int> = 0>
constexpr bool _Debug_lt_pred(_Pr&& _Pred, _Ty1&& _Left, _Ty2&& _Right) noexcept(
    noexcept(_Pred(_Left, _Right)) && noexcept(_Pred(_Right, _Left))) {
    // test if _Pred(_Left, _Right) and _Pred is strict weak ordering, when the arguments are the cv-same-type
    const auto _Result = static_cast<bool>(_Pred(_Left, _Right));
    if (_Result) {
        _STL_VERIFY(!_Pred(_Right, _Left), "invalid comparator");
    }

    return _Result;
}

[fhahn]

In D142589#4123383, @ashay-github wrote:

@fhahn, This patch is causing a Windows Debug build (with VS 2022 MSVC 19.34.31937) of opt to crash for the llvm\test\Transforms\LoopVectorize\first-order-recurrence-sink-replicate-region.ll test (see stack trace below). Sadly, the fix in commit af3c25dc does not resolve the problem. I (locally) reverted this patch and validated that the crash is resolved.

Here is a partial stack trace. Could you revert / fix this crash soon?

0.      Program arguments: build\bin\opt.exe -passes=loop-vectorize -force-vector-width=2 -force-vector-interleave=1 -force-widen-divrem-via-safe-divisor=0 -disable-output -debug-only=loop-vectorize llvm\test\Transforms\LoopVectorize\first-order-recurrence-sink-replicate-region.ll

Exception Code: 0x80000003

 #0 0x00007ff60564a39a std::_Debug_lt_pred<`sinkRecurrenceUsersAfterPrevious'::`2'::<lambda_2> &,llvm::VPRecipeBase * &,llvm::VPRecipeBase * &,0> C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.34.31933\include\xutility:1096:0

 #1 0x00007ff60564b8da std::_Insertion_sort_unchecked<llvm::VPRecipeBase * *,`sinkRecurrenceUsersAfterPrevious'::`2'::<lambda_2> > C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.34.31933\include\algorithm:7519:0

 #2 0x00007ff60564c82d std::_Sort_unchecked<llvm::VPRecipeBase * *,`sinkRecurrenceUsersAfterPrevious'::`2'::<lambda_2> > C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.34.31933\include\algorithm:7640:0

 #3 0x00007ff605650b39 std::sort<llvm::VPRecipeBase * *,`sinkRecurrenceUsersAfterPrevious'::`2'::<lambda_2> > C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.34.31933\include\algorithm:7670:0

 #4 0x00007ff605650aa8 llvm::sort<llvm::VPRecipeBase * *,`sinkRecurrenceUsersAfterPrevious'::`2'::<lambda_2> > llvm-project\llvm\include\llvm\ADT\STLExtras.h:1706:0

 #5 0x00007ff605650a61 llvm::sort<llvm::SmallVector<llvm::VPRecipeBase *,6> &,`sinkRecurrenceUsersAfterPrevious'::`2'::<lambda_2> > llvm-project\llvm\include\llvm\ADT\STLExtras.h:1711:0

 #6 0x00007ff6056448c3 sinkRecurrenceUsersAfterPrevious llvm-project\llvm\lib\Transforms\Vectorize\VPlanTransforms.cpp:619:0

 ...

Thanks for the report. This seems to only show up on Windows, so I cannot reproduce this locally.

I *think* I've seen similar issues in the past, could you try to see if the following patch fixes the issue:

diff --git a/llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp b/llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp
index 10a67081a0d0..ddbd27223044 100644
--- a/llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp
+++ b/llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp
@@ -612,7 +612,7 @@ sinkRecurrenceUsersAfterPrevious(VPFirstOrderRecurrencePHIRecipe *FOR,

   // Keep recipes to sink ordered by dominance so earlier instructions are
   // processed first.
-  sort(WorkList, [&VPDT](const VPRecipeBase *A, const VPRecipeBase *B) {
+  stable_sort(WorkList, [&VPDT](const VPRecipeBase *A, const VPRecipeBase *B) {
     return dominates(A, B, VPDT);
   });
```?

[ashay-github]

could you try to see if the following patch fixes the issue:

Unfortunately, that didn't fix it. I see the call to stable_sort in the stack trace, but other than that, it's the same as before:

#0 0x00007ff662b7ce6a std::_Debug_lt_pred<`sinkRecurrenceUsersAfterPrevious'::`2'::<lambda_2> &,llvm::VPRecipeBase * &,llvm::VPRecipeBase * &,0> C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.34.31933\include\xutility:1096:0

#1 0x00007ff662bb23ba std::_Insertion_sort_unchecked<llvm::VPRecipeBase * *,`sinkRecurrenceUsersAfterPrevious'::`2'::<lambda_2> > C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.34.31933\include\algorithm:7519:0
                                                                               
#2 0x00007ff662c1da94 std::stable_sort<llvm::VPRecipeBase * *,`sinkRecurrenceUsersAfterPrevious'::`2'::<lambda_2> > C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.34.31933\include\algorithm:8075:0

#3 0x00007ff662ba07f1 llvm::stable_sort<llvm::SmallVector<llvm::VPRecipeBase *,6> &,`sinkRecurrenceUsersAfterPrevious'::`2'::<lambda_2> > llvm-project\llvm\include\llvm\ADT\STLExtras.h:1955:0

#4 0x00007ff6664948c3 sinkRecurrenceUsersAfterPrevious llvm-project\llvm\lib\Transforms\Vectorize\VPlanTransforms.cpp:619:0

I pasted the code from xutility where the crash occurs and it seems to think that the comparator is invalid. Does that provide any hints / clues?

[fhahn]

In D142589#4123450, @ashay-github wrote:

could you try to see if the following patch fixes the issue:

Unfortunately, that didn't fix it. I see the call to stable_sort in the stack trace, but other than that, it's the same as before:

#0 0x00007ff662b7ce6a std::_Debug_lt_pred<`sinkRecurrenceUsersAfterPrevious'::`2'::<lambda_2> &,llvm::VPRecipeBase * &,llvm::VPRecipeBase * &,0> C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.34.31933\include\xutility:1096:0

#1 0x00007ff662bb23ba std::_Insertion_sort_unchecked<llvm::VPRecipeBase * *,`sinkRecurrenceUsersAfterPrevious'::`2'::<lambda_2> > C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.34.31933\include\algorithm:7519:0
                                                                               
#2 0x00007ff662c1da94 std::stable_sort<llvm::VPRecipeBase * *,`sinkRecurrenceUsersAfterPrevious'::`2'::<lambda_2> > C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.34.31933\include\algorithm:8075:0

#3 0x00007ff662ba07f1 llvm::stable_sort<llvm::SmallVector<llvm::VPRecipeBase *,6> &,`sinkRecurrenceUsersAfterPrevious'::`2'::<lambda_2> > llvm-project\llvm\include\llvm\ADT\STLExtras.h:1955:0

#4 0x00007ff6664948c3 sinkRecurrenceUsersAfterPrevious llvm-project\llvm\lib\Transforms\Vectorize\VPlanTransforms.cpp:619:0

I pasted the code from xutility where the crash occurs and it seems to think that the comparator is invalid. Does that provide any hints / clues?

Thanks for sharing the additional info. I think this may be checking that the comparator doesn't return true for B < A if A < B. This can happen with the current comparator. I pushed a fix that uses properlyDominates to avoid this. Could you check if you still see the issue? If so, I'll revert the set of patches and will try to check this out on a Windows system,.Fix is 807d43239a5f

[ashay-github]

Fix is 807d43239a5f

Yup, that resolved the issue! opt no longer crashes, thanks!

[Ayal]

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

607

As in SLPVectorizer.cpp's std::set<ScheduleData *, ScheduleDataCompare> ReadyInsts;, thereby saving the need to explicitly sort WorkList below. Best confirm that it works on Windows too...

llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h

public:
   const ReductionList &getReductionVars() const { return Reductions; }
 
   /// Returns the induction variables found in the loop.
   const InductionList &getInductionVars() const { return Inductions; }
 
   /// Return the fixed-order recurrences found in the loop.
   RecurrenceSet &getFixedOrderRecurrences() { return FixedOrderRecurrences; }
 
-  /// Return the set of instructions to sink to handle fixed-order recurrences.
-  MapVector<Instruction *, Instruction *> &getSinkAfter() { return SinkAfter; }
-
   /// Returns the widest induction type.
   Type *getWidestInductionType() { return WidestIndTy; }
 
   /// Returns True if given store is a final invariant store of one of the
   /// reductions found in the loop.
   bool isInvariantStoreOfReduction(StoreInst *SI);
 
   /// Returns True if given address is invariant and is used to store recurrent

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

 private:
   /// Build a VPlan according to the information gathered by Legal. \return a
   /// VPlan for vectorization factors \p Range.Start and up to \p Range.End
   /// exclusive, possibly decreasing \p Range.End.
   VPlanPtr buildVPlan(VFRange &Range);
 
   /// Build a VPlan using VPRecipes according to the information gather by
   /// Legal. This method is only used for the legacy inner loop vectorizer.
-  VPlanPtr buildVPlanWithVPRecipes(
-      VFRange &Range, SmallPtrSetImpl<Instruction *> &DeadInstructions,
-      const MapVector<Instruction *, Instruction *> &SinkAfter);
+  VPlanPtr
+  buildVPlanWithVPRecipes(VFRange &Range,
+                          SmallPtrSetImpl<Instruction *> &DeadInstructions);
 
   /// Build VPlans for power-of-2 VF's between \p MinVF and \p MaxVF inclusive,
   /// according to the information gathered by Legal when it checked if it is
   /// legal to vectorize the loop. This method creates VPlans using VPRecipes.
   void buildVPlansWithVPRecipes(ElementCount MinVF, ElementCount MaxVF);
 
   // Adjust the recipes for reductions. For in-loop reductions the chain of
   // instructions leading from the loop exit instr to the phi need to be

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

void LoopVectorizationPlanner::buildVPlansWithVPRecipes(ElementCount MinVF,
   // Add assume instructions we need to drop to DeadInstructions, to prevent
   // them from being added to the VPlan.
   // TODO: We only need to drop assumes in blocks that get flattend. If the
   // control flow is preserved, we should keep them.
   SmallPtrSet<Instruction *, 4> DeadInstructions;
   auto &ConditionalAssumes = Legal->getConditionalAssumes();
   DeadInstructions.insert(ConditionalAssumes.begin(), ConditionalAssumes.end());
 
-  MapVector<Instruction *, Instruction *> &SinkAfter = Legal->getSinkAfter();
-  // Dead instructions do not need sinking. Remove them from SinkAfter.
-  for (Instruction *I : DeadInstructions)
-    SinkAfter.erase(I);
-
-  // Cannot sink instructions after dead instructions (there won't be any
-  // recipes for them). Instead, find the first non-dead previous instruction.
-  for (auto &P : Legal->getSinkAfter()) {
-    Instruction *SinkTarget = P.second;
-    Instruction *FirstInst = &*SinkTarget->getParent()->begin();
-    (void)FirstInst;
-    while (DeadInstructions.contains(SinkTarget)) {
-      assert(
-          SinkTarget != FirstInst &&
-          "Must find a live instruction (at least the one feeding the "
-          "fixed-order recurrence PHI) before reaching beginning of the block");
-      SinkTarget = SinkTarget->getPrevNode();
-      assert(SinkTarget != P.first &&
-             "sink source equals target, no sinking required");
-    }
-    P.second = SinkTarget;
-  }
-
   auto MaxVFPlusOne = MaxVF.getWithIncrement(1);
   for (ElementCount VF = MinVF; ElementCount::isKnownLT(VF, MaxVFPlusOne);) {
     VFRange SubRange = {VF, MaxVFPlusOne};
-    VPlans.push_back(
-        buildVPlanWithVPRecipes(SubRange, DeadInstructions, SinkAfter));
+    VPlans.push_back(buildVPlanWithVPRecipes(SubRange, DeadInstructions));
     VF = SubRange.End;
   }
 }
 
 // Add the necessary canonical IV and branch recipes required to control the
 // loop.
 static void addCanonicalIVRecipes(VPlan &Plan, Type *IdxTy, DebugLoc DL,
                                   bool HasNUW,
for (PHINode &ExitPhi : ExitBB->phis()) {
     Value *IncomingValue =
         ExitPhi.getIncomingValueForBlock(ExitingBB);
     VPValue *V = Plan.getOrAddVPValue(IncomingValue, true);
     Plan.addLiveOut(&ExitPhi, V);
   }
 }
 
 VPlanPtr LoopVectorizationPlanner::buildVPlanWithVPRecipes(
-    VFRange &Range, SmallPtrSetImpl<Instruction *> &DeadInstructions,
-    const MapVector<Instruction *, Instruction *> &SinkAfter) {
+    VFRange &Range, SmallPtrSetImpl<Instruction *> &DeadInstructions) {
 
   SmallPtrSet<const InterleaveGroup<Instruction> *, 1> InterleaveGroups;
 
   VPRecipeBuilder RecipeBuilder(OrigLoop, TLI, Legal, CM, PSE, Builder);
 
   // ---------------------------------------------------------------------------
   // Pre-construction: record ingredients whose recipes we'll need to further
   // process after constructing the initial VPlan.
   // ---------------------------------------------------------------------------
 
-  // Mark instructions we'll need to sink later and their targets as
-  // ingredients whose recipe we'll need to record.
-  for (const auto &Entry : SinkAfter) {
-    RecipeBuilder.recordRecipeOf(Entry.first);
-    RecipeBuilder.recordRecipeOf(Entry.second);
-  }
   for (const auto &Reduction : CM.getInLoopReductionChains()) {
     PHINode *Phi = Reduction.first;
     RecurKind Kind =
         Legal->getReductionVars().find(Phi)->second.getRecurrenceKind();
     const SmallVector<Instruction *, 4> &ReductionOperations = Reduction.second;
 
     RecipeBuilder.recordRecipeOf(Phi);
     for (const auto &R : ReductionOperations) {
addCanonicalIVRecipes(*Plan, Legal->getWidestInductionType(),
                         CM.useActiveLaneMaskForControlFlow());
 
   // Scan the body of the loop in a topological order to visit each basic block
   // after having visited its predecessor basic blocks.
   LoopBlocksDFS DFS(OrigLoop);
   DFS.perform(LI);
 
   VPBasicBlock *VPBB = HeaderVPBB;
-  SmallVector<VPWidenIntOrFpInductionRecipe *> InductionsToMove;
   for (BasicBlock *BB : make_range(DFS.beginRPO(), DFS.endRPO())) {
     // Relevant instructions from basic block BB will be grouped into VPRecipe
     // ingredients and fill a new VPBasicBlock.
     unsigned VPBBsForBB = 0;
     if (VPBB != HeaderVPBB)
       VPBB->setName(BB->getName());
     Builder.setInsertPoint(VPBB);
 
for (Instruction &I : BB->instructionsWithoutDebug()) {
         }
         // Otherwise, add the new recipe.
         VPRecipeBase *Recipe = RecipeOrValue.get<VPRecipeBase *>();
         for (auto *Def : Recipe->definedValues()) {
           auto *UV = Def->getUnderlyingValue();
           Plan->addVPValue(UV, Def);
         }
 
+        RecipeBuilder.setRecipe(Instr, Recipe);
         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
           // position of the trunc.
           assert(isa<TruncInst>(Instr));
-          InductionsToMove.push_back(
-              cast<VPWidenIntOrFpInductionRecipe>(Recipe));
-        }
-        RecipeBuilder.setRecipe(Instr, Recipe);
+          Recipe->insertBefore(*HeaderVPBB, HeaderVPBB->getFirstNonPhi());
+        } else
           VPBB->appendRecipe(Recipe);
         continue;
       }
 
       // Otherwise, if all widening options failed, Instruction is to be
       // replicated. This may create a successor for VPBB.
       VPBasicBlock *NextVPBB =
           RecipeBuilder.handleReplication(Instr, Range, VPBB, Plan);
       if (NextVPBB != VPBB) {
assert(isa<VPRegionBlock>(Plan->getVectorLoopRegion()) &&
          "VPBasicBlock");
   RecipeBuilder.fixHeaderPhis();
 
   // ---------------------------------------------------------------------------
   // Transform initial VPlan: Apply previously taken decisions, in order, to
   // bring the VPlan to its final state.
   // ---------------------------------------------------------------------------
 
-  // Apply Sink-After legal constraints.
-  auto GetReplicateRegion = [](VPRecipeBase *R) -> VPRegionBlock * {
-    auto *Region = dyn_cast_or_null<VPRegionBlock>(R->getParent()->getParent());
-    if (Region && Region->isReplicator()) {
-      assert(Region->getNumSuccessors() == 1 &&
-             Region->getNumPredecessors() == 1 && "Expected SESE region!");
-      assert(R->getParent()->size() == 1 &&
-             "A recipe in an original replicator region must be the only "
-             "recipe in its block");
-      return Region;
-    }
-    return nullptr;
-  };
-  for (const auto &Entry : SinkAfter) {
-    VPRecipeBase *Sink = RecipeBuilder.getRecipe(Entry.first);
-    VPRecipeBase *Target = RecipeBuilder.getRecipe(Entry.second);
-
-    auto *TargetRegion = GetReplicateRegion(Target);
-    auto *SinkRegion = GetReplicateRegion(Sink);
-    if (!SinkRegion) {
-      // If the sink source is not a replicate region, sink the recipe directly.
-      if (TargetRegion) {
-        // The target is in a replication region, make sure to move Sink to
-        // the block after it, not into the replication region itself.
-        VPBasicBlock *NextBlock =
-            cast<VPBasicBlock>(TargetRegion->getSuccessors().front());
-        Sink->moveBefore(*NextBlock, NextBlock->getFirstNonPhi());
-      } else
-        Sink->moveAfter(Target);
-      continue;
-    }
-
-    // The sink source is in a replicate region. Unhook the region from the CFG.
-    auto *SinkPred = SinkRegion->getSinglePredecessor();
-    auto *SinkSucc = SinkRegion->getSingleSuccessor();
-    VPBlockUtils::disconnectBlocks(SinkPred, SinkRegion);
-    VPBlockUtils::disconnectBlocks(SinkRegion, SinkSucc);
-    VPBlockUtils::connectBlocks(SinkPred, SinkSucc);
-
-    if (TargetRegion) {
-      // The target recipe is also in a replicate region, move the sink region
-      // after the target region.
-      auto *TargetSucc = TargetRegion->getSingleSuccessor();
-      VPBlockUtils::disconnectBlocks(TargetRegion, TargetSucc);
-      VPBlockUtils::connectBlocks(TargetRegion, SinkRegion);
-      VPBlockUtils::connectBlocks(SinkRegion, TargetSucc);
-    } else {
-      // The sink source is in a replicate region, we need to move the whole
-      // replicate region, which should only contain a single recipe in the
-      // main block.
-      auto *SplitBlock =
-          Target->getParent()->splitAt(std::next(Target->getIterator()));
-
-      auto *SplitPred = SplitBlock->getSinglePredecessor();
-
-      VPBlockUtils::disconnectBlocks(SplitPred, SplitBlock);
-      VPBlockUtils::connectBlocks(SplitPred, SinkRegion);
-      VPBlockUtils::connectBlocks(SinkRegion, SplitBlock);
-    }
-  }
-
   VPlanTransforms::removeRedundantCanonicalIVs(*Plan);
   VPlanTransforms::removeRedundantInductionCasts(*Plan);
 
-  // Now that sink-after is done, move induction recipes for optimized truncates
-  // to the phi section of the header block.
-  for (VPWidenIntOrFpInductionRecipe *Ind : InductionsToMove)
-    Ind->moveBefore(*HeaderVPBB, HeaderVPBB->getFirstNonPhi());
-
   // Adjust the recipes for any inloop reductions.
   adjustRecipesForReductions(cast<VPBasicBlock>(TopRegion->getExiting()), Plan,
                              RecipeBuilder, Range.Start);
 
-  // Introduce a recipe to combine the incoming and previous values of a
-  // fixed-order recurrence.
-  for (VPRecipeBase &R :
-       Plan->getVectorLoopRegion()->getEntryBasicBlock()->phis()) {
-    auto *RecurPhi = dyn_cast<VPFirstOrderRecurrencePHIRecipe>(&R);
-    if (!RecurPhi)
-      continue;
-
-    VPRecipeBase *PrevRecipe = &RecurPhi->getBackedgeRecipe();
-    // Fixed-order recurrences do not contain cycles, so this loop is guaranteed
-    // to terminate.
-    while (auto *PrevPhi =
-               dyn_cast<VPFirstOrderRecurrencePHIRecipe>(PrevRecipe))
-      PrevRecipe = &PrevPhi->getBackedgeRecipe();
-    VPBasicBlock *InsertBlock = PrevRecipe->getParent();
-    auto *Region = GetReplicateRegion(PrevRecipe);
-    if (Region)
-      InsertBlock = dyn_cast<VPBasicBlock>(Region->getSingleSuccessor());
-    if (!InsertBlock) {
-      InsertBlock = new VPBasicBlock(Region->getName() + ".succ");
-      VPBlockUtils::insertBlockAfter(InsertBlock, Region);
-    }
-    if (Region || PrevRecipe->isPhi())
-      Builder.setInsertPoint(InsertBlock, InsertBlock->getFirstNonPhi());
-    else
-      Builder.setInsertPoint(InsertBlock, std::next(PrevRecipe->getIterator()));
-
-    auto *RecurSplice = cast<VPInstruction>(
-        Builder.createNaryOp(VPInstruction::FirstOrderRecurrenceSplice,
-                             {RecurPhi, RecurPhi->getBackedgeValue()}));
-
-    RecurPhi->replaceAllUsesWith(RecurSplice);
-    // Set the first operand of RecurSplice to RecurPhi again, after replacing
-    // all users.
-    RecurSplice->setOperand(0, RecurPhi);
-  }
+  VPlanTransforms::fixFirstOrderRecurrences(*Plan, Builder);
 
   // Interleave memory: for each Interleave Group we marked earlier as relevant
   // for this VPlan, replace the Recipes widening its memory instructions with a
   // single VPInterleaveRecipe at its insertion point.
   for (const auto *IG : InterleaveGroups) {
     auto *Recipe = cast<VPWidenMemoryInstructionRecipe>(
         RecipeBuilder.getRecipe(IG->getInsertPos()));
     SmallVector<VPValue *, 4> StoredValues;

llvm/lib/Transforms/Vectorize/VPlan.h

struct VPFirstOrderRecurrencePHIRecipe : public VPHeaderPHIRecipe {
   VP_CLASSOF_IMPL(VPDef::VPFirstOrderRecurrencePHISC)
 
   static inline bool classof(const VPHeaderPHIRecipe *R) {
     return R->getVPDefID() == VPDef::VPFirstOrderRecurrencePHISC;
   }
 
   void execute(VPTransformState &State) override;
 
+  VPValue *getPreviousValue() { return getOperand(1); }
+
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
 #endif
 };
 
 /// A recipe for handling reduction phis. The start value is the first operand

llvm/lib/Transforms/Vectorize/VPlanTransforms.h

 namespace llvm {
 
 class InductionDescriptor;
 class Instruction;
 class PHINode;
 class ScalarEvolution;
 class Loop;
 class PredicatedScalarEvolution;
+class VPBuilder;
 class TargetLibraryInfo;
 
 struct VPlanTransforms {
   /// Replaces the VPInstructions in \p Plan with corresponding
   /// widen recipes.
   static void
   VPInstructionsToVPRecipes(Loop *OrigLoop, VPlanPtr &Plan,
                             function_ref<const InductionDescriptor *(PHINode *)>
struct VPlanTransforms {
   /// them with already existing recipes expanding the same SCEV expression.
   static void removeRedundantExpandSCEVRecipes(VPlan &Plan);
 
   /// Optimize \p Plan based on \p BestVF and \p BestUF. This may restrict the
   /// resulting plan to \p BestVF and \p BestUF.
   static void optimizeForVFAndUF(VPlan &Plan, ElementCount BestVF,
                                  unsigned BestUF,
                                  PredicatedScalarEvolution &PSE);
+
+  static void fixFirstOrderRecurrences(VPlan &Plan, VPBuilder &Builder);
 };
 
 } // namespace llvm
 
 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLANTRANSFORMS_H

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

 //===-- VPlanTransforms.cpp - Utility VPlan to VPlan transforms -----------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 /// This file implements a set of utility VPlan to VPlan transformations.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "VPlanTransforms.h"
+#include "VPRecipeBuilder.h"
 #include "VPlanCFG.h"
+#include "VPlanDominatorTree.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/Analysis/IVDescriptors.h"
 #include "llvm/Analysis/VectorUtils.h"
 #include "llvm/IR/Intrinsics.h"
 
 using namespace llvm;
 
void VPlanTransforms::optimizeForVFAndUF(VPlan &Plan, ElementCount BestVF,
   Term->eraseFromParent();
   ExitingVPBB->appendRecipe(BOC);
   Plan.setVF(BestVF);
   Plan.setUF(BestUF);
   // TODO: Further simplifications are possible
   //      1. Replace inductions with constants.
   //      2. Replace vector loop region with VPBasicBlock.
 }
+
+static VPRegionBlock *GetReplicateRegion(VPRecipeBase *R) {
+  auto *Region = dyn_cast_or_null<VPRegionBlock>(R->getParent()->getParent());
+  if (Region && Region->isReplicator()) {
+    assert(Region->getNumSuccessors() == 1 &&
+           Region->getNumPredecessors() == 1 && "Expected SESE region!");
+    assert(R->getParent()->size() == 1 &&
+           "A recipe in an original replicator region must be the only "
+           "recipe in its block");
+    return Region;
+  }
+  return nullptr;
+}
+
+static bool recipeComesBefore(const VPRecipeBase *A, const VPRecipeBase *B,
+                              VPDominatorTree &VPDT) {
+  auto LocalComesBefore = [](const VPRecipeBase *A, const VPRecipeBase *B) {
+    for (auto &R : *A->getParent()) {
+      if (&R == A)
+        return true;
+      if (&R == B)
+        return false;
+    }
+    llvm_unreachable("recipe not found");
+  };
+  if (A->getParent() == B->getParent())
+    return LocalComesBefore(A, B);
+  return VPDT.dominates(A->getParent(), B->getParent());
+}
+
+// Sink users of \p FOR after the recipe defining the previous value \p Previous
+// of the recurrence.
+static void
+sinkRecurrenceUsersAfterPrevious(VPFirstOrderRecurrencePHIRecipe *FOR,
+                                 VPRecipeBase *Previous,
+                                 VPDominatorTree &VPDT) {
+  auto CompareByComesBefore = [&](const VPRecipeBase *A,
+                                  const VPRecipeBase *B) {
+    auto *RegionA = GetReplicateRegion(const_cast<VPRecipeBase *>(A));
+    auto *RegionB = GetReplicateRegion(const_cast<VPRecipeBase *>(B));
+    if (RegionA && RegionB)
+      return VPDT.dominates(RegionA, RegionB);
+
+    return recipeComesBefore(A, B, VPDT);
+  };
+
+  // Collect recipes that need sinking.
+  SmallVector<VPRecipeBase *> WorkList;
+  SmallPtrSet<VPRecipeBase *, 8> Seen;
+  Seen.insert(Previous);
+  // Keep recipes to sink ordered by dominance so earlier instructions are
+  // processed first.
+  std::set<VPRecipeBase *, decltype(CompareByComesBefore)> InstrsToSink(
+      CompareByComesBefore);
+  auto TryToPushSinkCandidate = [&](VPRecipeBase *SinkCandidate) {
+    if (isa<VPHeaderPHIRecipe>(SinkCandidate) ||
+        !Seen.insert(SinkCandidate).second ||
+        recipeComesBefore(Previous, SinkCandidate, VPDT))
+      return;
+
+    WorkList.push_back(SinkCandidate);
+
+    // VPPredInstPHIRecipes don't need sinking, because they will be sunk when
+    // sinking the containing replicate region.
+    if (!isa<VPPredInstPHIRecipe>(SinkCandidate))
+      InstrsToSink.insert(SinkCandidate);
+  };
+
+  // Recursively sink users of FOR after Previous.
+  WorkList.push_back(FOR);
+  for (unsigned I = 0; I != WorkList.size(); ++I) {
+    VPRecipeBase *Current = WorkList[I];
+    for (VPUser *User : Current->getVPSingleValue()->users()) {
+      if (auto *R = dyn_cast<VPRecipeBase>(User))
+        TryToPushSinkCandidate(R);
+    }
+  }
+  for (VPRecipeBase *SinkCandidate : InstrsToSink) {
+    VPRecipeBase *Target = Previous;
+    for (VPValue *Op : SinkCandidate->operands()) {
+      VPRecipeBase *Curr = Op->getDefiningRecipe();
+      if (!Curr)
+        continue;
+      if (recipeComesBefore(Target, Curr, VPDT))
+        Target = Curr;
+    }
+
+    auto *TargetRegion = GetReplicateRegion(Target);
+    auto *SinkRegion = GetReplicateRegion(SinkCandidate);
+    if (!SinkRegion) {
+      // If the sink source is not a replicate region, sink the recipe
+      // directly.
+      if (TargetRegion) {
+        // The target is in a replication region, make sure to move Sink to
+        // the block after it, not into the replication region itself.
+        VPBasicBlock *NextBlock =
+            cast<VPBasicBlock>(TargetRegion->getSuccessors().front());
+        SinkCandidate->moveBefore(*NextBlock, NextBlock->getFirstNonPhi());
+      } else
+        SinkCandidate->moveAfter(Target);
+      continue;
+    }
+    // The sink source is in a replicate region. Unhook the region from the
+    // CFG.
+    auto *SinkPred = SinkRegion->getSinglePredecessor();
+    auto *SinkSucc = SinkRegion->getSingleSuccessor();
+    VPBlockUtils::disconnectBlocks(SinkPred, SinkRegion);
+    VPBlockUtils::disconnectBlocks(SinkRegion, SinkSucc);
+    VPBlockUtils::connectBlocks(SinkPred, SinkSucc);
+
+    if (TargetRegion) {
+      // The target recipe is also in a replicate region, move the sink
+      // region after the target region.
+      auto *TargetSucc = TargetRegion->getSingleSuccessor();
+      VPBlockUtils::disconnectBlocks(TargetRegion, TargetSucc);
+      VPBlockUtils::connectBlocks(TargetRegion, SinkRegion);
+      VPBlockUtils::connectBlocks(SinkRegion, TargetSucc);
+    } else {
+      // The sink source is in a replicate region, we need to move the whole
+      // replicate region, which should only contain a single recipe in the
+      // main block.
+      auto *SplitBlock =
+          Target->getParent()->splitAt(std::next(Target->getIterator()));
+
+      auto *SplitPred = SplitBlock->getSinglePredecessor();
+
+      VPBlockUtils::disconnectBlocks(SplitPred, SplitBlock);
+      VPBlockUtils::connectBlocks(SplitPred, SinkRegion);
+      VPBlockUtils::connectBlocks(SinkRegion, SplitBlock);
+    }
+    // We modified the CFG, update dominator tree.
+    VPDT.recalculate(*SinkRegion->getPlan());
+  }
+}
+
+void VPlanTransforms::fixFirstOrderRecurrences(VPlan &Plan,
+                                               VPBuilder &Builder) {
+  VPDominatorTree VPDT;
+  VPDT.recalculate(Plan);
+
+  for (VPRecipeBase &R :
+       Plan.getVectorLoopRegion()->getEntry()->getEntryBasicBlock()->phis()) {
+    auto *FOR = dyn_cast<VPFirstOrderRecurrencePHIRecipe>(&R);
+    if (!FOR)
+      continue;
+
+    SmallPtrSet<VPFirstOrderRecurrencePHIRecipe *, 4> SeenPhis;
+    VPRecipeBase *Previous = FOR->getPreviousValue()->getDefiningRecipe();
+    // Fixed-order recurrences do not contain cycles, so this loop is guaranteed
+    // to terminate.
+    while (auto *PrevPhi =
+               dyn_cast_or_null<VPFirstOrderRecurrencePHIRecipe>(Previous)) {
+      assert(PrevPhi->getParent() == FOR->getParent());
+      assert(SeenPhis.insert(PrevPhi).second);
+      Previous = PrevPhi->getPreviousValue()->getDefiningRecipe();
+    }
+
+    sinkRecurrenceUsersAfterPrevious(FOR, Previous, VPDT);
+
+    // Introduce a recipe to combine the incoming and previous values of a
+    // fixed-order recurrence.
+    VPBasicBlock *InsertBlock = Previous->getParent();
+    auto *Region = GetReplicateRegion(Previous);
+    if (Region)
+      InsertBlock = dyn_cast<VPBasicBlock>(Region->getSingleSuccessor());
+    if (!InsertBlock) {
+      InsertBlock = new VPBasicBlock(Region->getName() + ".succ");
+      VPBlockUtils::insertBlockAfter(InsertBlock, Region);
+    }
+    if (Region || Previous->isPhi())
+      Builder.setInsertPoint(InsertBlock, InsertBlock->getFirstNonPhi());
+    else
+      Builder.setInsertPoint(InsertBlock, std::next(Previous->getIterator()));
+
+    auto *RecurSplice = cast<VPInstruction>(
+        Builder.createNaryOp(VPInstruction::FirstOrderRecurrenceSplice,
+                             {FOR, FOR->getBackedgeValue()}));
+
+    FOR->replaceAllUsesWith(RecurSplice);
+    // Set the first operand of RecurSplice to FOR again, after replacing
+    // all users.
+    RecurSplice->setOperand(0, FOR);
+  }
+}

llvm/test/Transforms/LoopVectorize/first-order-recurrence-complex.ll

 ; CHECK-NEXT:    [[ADD_1:%.*]] = add i32 [[SCALAR_RECUR]], [[X]]
 ; CHECK-NEXT:    [[IDX_1:%.*]] = getelementptr inbounds [257 x i32], ptr @p, i64 0, i64 [[IV]]
 ; CHECK-NEXT:    [[PRE_NEXT]] = load i32, ptr [[IDX_1]], align 4
 ; CHECK-NEXT:    [[ADD_2:%.*]] = add i32 [[ADD_1]], [[PRE_NEXT]]
 ; CHECK-NEXT:    [[IDX_2:%.*]] = getelementptr inbounds [257 x i32], ptr @q, i64 0, i64 [[IV]]
 ; CHECK-NEXT:    store i32 [[ADD_2]], ptr [[IDX_2]], align 4
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[IV_NEXT]], 2000
-; CHECK-NEXT:    br i1 [[EXITCOND]], label [[EXIT]], label [[FOR]], !llvm.loop [[LOOP2:![0-9]+]]
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[EXIT]], label [[FOR]], !llvm.loop [[LOOP3:![0-9]+]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 
 entry:
   br label %preheader
 
 preheader:

 ; CHECK-NEXT:    [[TMP1:%.*]] = load float, ptr [[FOR_PTR_2:%.*]], align 4
 ; CHECK-NEXT:    [[BROADCAST_SPLATINSERT:%.*]] = insertelement <4 x float> poison, float [[TMP1]], i64 0
 ; CHECK-NEXT:    [[BROADCAST_SPLAT]] = shufflevector <4 x float> [[BROADCAST_SPLATINSERT]], <4 x float> poison, <4 x i32> zeroinitializer
 ; CHECK-NEXT:    [[TMP2:%.*]] = shufflevector <4 x float> [[VECTOR_RECUR1]], <4 x float> [[BROADCAST_SPLAT]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
 ; CHECK-NEXT:    [[TMP3:%.*]] = load float, ptr [[FOR_PTR_1:%.*]], align 4
 ; CHECK-NEXT:    [[BROADCAST_SPLATINSERT2:%.*]] = insertelement <4 x float> poison, float [[TMP3]], i64 0
 ; CHECK-NEXT:    [[BROADCAST_SPLAT3]] = shufflevector <4 x float> [[BROADCAST_SPLATINSERT2]], <4 x float> poison, <4 x i32> zeroinitializer
 ; CHECK-NEXT:    [[TMP4:%.*]] = shufflevector <4 x float> [[VECTOR_RECUR]], <4 x float> [[BROADCAST_SPLAT3]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
-; CHECK-NEXT:    [[TMP5:%.*]] = fmul fast <4 x float> [[TMP4]], <float 2.000000e+00, float 2.000000e+00, float 2.000000e+00, float 2.000000e+00>
+; CHECK-NEXT:    [[TMP5:%.*]] = fadd fast <4 x float> [[TMP4]], <float 1.000000e+00, float 1.000000e+00, float 1.000000e+00, float 1.000000e+00>
 ; CHECK-NEXT:    [[TMP6:%.*]] = fmul fast <4 x float> [[TMP4]], [[TMP2]]
-; CHECK-NEXT:    [[TMP7:%.*]] = fadd fast <4 x float> [[TMP4]], <float 1.000000e+00, float 1.000000e+00, float 1.000000e+00, float 1.000000e+00>
+; CHECK-NEXT:    [[TMP7:%.*]] = fmul fast <4 x float> [[TMP4]], <float 2.000000e+00, float 2.000000e+00, float 2.000000e+00, float 2.000000e+00>
 ; CHECK-NEXT:    [[TMP8:%.*]] = getelementptr inbounds float, ptr [[DST_1:%.*]], i64 [[TMP0]]
 ; CHECK-NEXT:    [[TMP9:%.*]] = getelementptr inbounds float, ptr [[TMP8]], i32 0
 ; CHECK-NEXT:    store <4 x float> [[TMP6]], ptr [[TMP9]], align 4
 ; CHECK-NEXT:    [[TMP10:%.*]] = getelementptr inbounds float, ptr [[DST_2:%.*]], i64 [[TMP0]]
 ; CHECK-NEXT:    [[TMP11:%.*]] = getelementptr inbounds float, ptr [[TMP10]], i32 0
-; CHECK-NEXT:    store <4 x float> [[TMP5]], ptr [[TMP11]], align 4
+; CHECK-NEXT:    store <4 x float> [[TMP7]], ptr [[TMP11]], align 4
 ; CHECK-NEXT:    [[TMP12:%.*]] = getelementptr inbounds float, ptr [[DST_3:%.*]], i64 [[TMP0]]
 ; CHECK-NEXT:    [[TMP13:%.*]] = getelementptr inbounds float, ptr [[TMP12]], i32 0
-; CHECK-NEXT:    store <4 x float> [[TMP7]], ptr [[TMP13]], align 4
+; CHECK-NEXT:    store <4 x float> [[TMP5]], ptr [[TMP13]], align 4
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 ; CHECK-NEXT:    [[TMP14:%.*]] = icmp eq i64 [[INDEX_NEXT]], 1000
 ; CHECK-NEXT:    br i1 [[TMP14]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP10:![0-9]+]]
 ; CHECK:       middle.block:
 ; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 1001, 1000
 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT:%.*]] = extractelement <4 x float> [[BROADCAST_SPLAT3]], i32 3
 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI:%.*]] = extractelement <4 x float> [[BROADCAST_SPLAT3]], i32 2
 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT4:%.*]] = extractelement <4 x float> [[BROADCAST_SPLAT]], i32 3

 ; CHECK-NEXT:    [[TMP1:%.*]] = load float, ptr [[FOR_PTR_2:%.*]], align 4
 ; CHECK-NEXT:    [[BROADCAST_SPLATINSERT:%.*]] = insertelement <4 x float> poison, float [[TMP1]], i64 0
 ; CHECK-NEXT:    [[BROADCAST_SPLAT]] = shufflevector <4 x float> [[BROADCAST_SPLATINSERT]], <4 x float> poison, <4 x i32> zeroinitializer
 ; CHECK-NEXT:    [[TMP2:%.*]] = shufflevector <4 x float> [[VECTOR_RECUR1]], <4 x float> [[BROADCAST_SPLAT]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
 ; CHECK-NEXT:    [[TMP3:%.*]] = load float, ptr [[FOR_PTR_1:%.*]], align 4
 ; CHECK-NEXT:    [[BROADCAST_SPLATINSERT2:%.*]] = insertelement <4 x float> poison, float [[TMP3]], i64 0
 ; CHECK-NEXT:    [[BROADCAST_SPLAT3]] = shufflevector <4 x float> [[BROADCAST_SPLATINSERT2]], <4 x float> poison, <4 x i32> zeroinitializer
 ; CHECK-NEXT:    [[TMP4:%.*]] = shufflevector <4 x float> [[VECTOR_RECUR]], <4 x float> [[BROADCAST_SPLAT3]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
-; CHECK-NEXT:    [[TMP5:%.*]] = fmul fast <4 x float> [[TMP4]], <float 2.000000e+00, float 2.000000e+00, float 2.000000e+00, float 2.000000e+00>
-; CHECK-NEXT:    [[TMP6:%.*]] = fmul fast <4 x float> [[TMP5]], <float 2.000000e+00, float 2.000000e+00, float 2.000000e+00, float 2.000000e+00>
-; CHECK-NEXT:    [[TMP7:%.*]] = fmul fast <4 x float> [[TMP6]], [[TMP2]]
-; CHECK-NEXT:    [[TMP8:%.*]] = fadd fast <4 x float> [[TMP4]], <float 1.000000e+00, float 1.000000e+00, float 1.000000e+00, float 1.000000e+00>
+; CHECK-NEXT:    [[TMP5:%.*]] = fadd fast <4 x float> [[TMP4]], <float 1.000000e+00, float 1.000000e+00, float 1.000000e+00, float 1.000000e+00>
+; CHECK-NEXT:    [[TMP6:%.*]] = fmul fast <4 x float> [[TMP4]], <float 2.000000e+00, float 2.000000e+00, float 2.000000e+00, float 2.000000e+00>
+; CHECK-NEXT:    [[TMP7:%.*]] = fmul fast <4 x float> [[TMP6]], <float 2.000000e+00, float 2.000000e+00, float 2.000000e+00, float 2.000000e+00>
+; CHECK-NEXT:    [[TMP8:%.*]] = fmul fast <4 x float> [[TMP7]], [[TMP2]]
 ; CHECK-NEXT:    [[TMP9:%.*]] = getelementptr inbounds float, ptr [[DST_1:%.*]], i64 [[TMP0]]
 ; CHECK-NEXT:    [[TMP10:%.*]] = getelementptr inbounds float, ptr [[TMP9]], i32 0
-; CHECK-NEXT:    store <4 x float> [[TMP7]], ptr [[TMP10]], align 4
+; CHECK-NEXT:    store <4 x float> [[TMP8]], ptr [[TMP10]], align 4
 ; CHECK-NEXT:    [[TMP11:%.*]] = getelementptr inbounds float, ptr [[DST_2:%.*]], i64 [[TMP0]]
 ; CHECK-NEXT:    [[TMP12:%.*]] = getelementptr inbounds float, ptr [[TMP11]], i32 0
-; CHECK-NEXT:    store <4 x float> [[TMP5]], ptr [[TMP12]], align 4
+; CHECK-NEXT:    store <4 x float> [[TMP6]], ptr [[TMP12]], align 4
 ; CHECK-NEXT:    [[TMP13:%.*]] = getelementptr inbounds float, ptr [[DST_3:%.*]], i64 [[TMP0]]
 ; CHECK-NEXT:    [[TMP14:%.*]] = getelementptr inbounds float, ptr [[TMP13]], i32 0
-; CHECK-NEXT:    store <4 x float> [[TMP8]], ptr [[TMP14]], align 4
+; CHECK-NEXT:    store <4 x float> [[TMP5]], ptr [[TMP14]], align 4
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 ; CHECK-NEXT:    [[TMP15:%.*]] = icmp eq i64 [[INDEX_NEXT]], 1000
 ; CHECK-NEXT:    br i1 [[TMP15]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP12:![0-9]+]]
 ; CHECK:       middle.block:
 ; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 1001, 1000
 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT:%.*]] = extractelement <4 x float> [[BROADCAST_SPLAT3]], i32 3
 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI:%.*]] = extractelement <4 x float> [[BROADCAST_SPLAT3]], i32 2
 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT4:%.*]] = extractelement <4 x float> [[BROADCAST_SPLAT]], i32 3

 ; CHECK-NEXT:    [[VECTOR_RECUR:%.*]] = phi <4 x i64> [ <i64 poison, i64 poison, i64 poison, i64 0>, [[VECTOR_PH]] ], [ [[TMP5:%.*]], [[VECTOR_BODY]] ]
 ; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[INDEX]], 0
 ; CHECK-NEXT:    [[TMP3:%.*]] = getelementptr inbounds i32, ptr [[PTR:%.*]], i32 [[TMP2]]
 ; CHECK-NEXT:    [[TMP4:%.*]] = getelementptr inbounds i32, ptr [[TMP3]], i32 0
 ; CHECK-NEXT:    [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP4]], align 4
 ; CHECK-NEXT:    [[TMP5]] = zext <4 x i32> [[WIDE_LOAD]] to <4 x i64>
 ; CHECK-NEXT:    [[TMP6:%.*]] = shufflevector <4 x i64> [[VECTOR_RECUR]], <4 x i64> [[TMP5]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
 ; CHECK-NEXT:    [[TMP7:%.*]] = trunc <4 x i64> [[TMP6]] to <4 x i32>
-; CHECK-NEXT:    [[TMP8:%.*]] = add <4 x i32> [[TMP7]], <i32 2, i32 2, i32 2, i32 2>
-; CHECK-NEXT:    [[TMP9:%.*]] = mul <4 x i32> [[TMP8]], <i32 99, i32 99, i32 99, i32 99>
-; CHECK-NEXT:    [[TMP10:%.*]] = icmp slt <4 x i32> [[TMP7]], <i32 213, i32 213, i32 213, i32 213>
-; CHECK-NEXT:    [[TMP11:%.*]] = select <4 x i1> [[TMP10]], <4 x i32> [[TMP7]], <4 x i32> [[TMP9]]
+; CHECK-NEXT:    [[TMP8:%.*]] = icmp slt <4 x i32> [[TMP7]], <i32 213, i32 213, i32 213, i32 213>
+; CHECK-NEXT:    [[TMP9:%.*]] = add <4 x i32> [[TMP7]], <i32 2, i32 2, i32 2, i32 2>
+; CHECK-NEXT:    [[TMP10:%.*]] = mul <4 x i32> [[TMP9]], <i32 99, i32 99, i32 99, i32 99>
+; CHECK-NEXT:    [[TMP11:%.*]] = select <4 x i1> [[TMP8]], <4 x i32> [[TMP7]], <4 x i32> [[TMP10]]
 ; CHECK-NEXT:    store <4 x i32> [[TMP11]], ptr [[TMP4]], align 4
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i32 [[INDEX]], 4
 ; CHECK-NEXT:    [[TMP12:%.*]] = icmp eq i32 [[INDEX_NEXT]], [[N_VEC]]
 ; CHECK-NEXT:    br i1 [[TMP12]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP20:![0-9]+]]
 ; CHECK:       middle.block:
 ; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i32 [[UMAX1]], [[N_VEC]]
 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT:%.*]] = extractelement <4 x i64> [[TMP5]], i32 3
 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI:%.*]] = extractelement <4 x i64> [[TMP5]], i32 2

 ; CHECK-NEXT:    [[VECTOR_RECUR:%.*]] = phi <4 x double> [ <double poison, double poison, double poison, double 1.000000e+01>, [[VECTOR_PH]] ], [ [[WIDE_LOAD:%.*]], [[VECTOR_BODY]] ]
 ; CHECK-NEXT:    [[VECTOR_RECUR1:%.*]] = phi <4 x double> [ <double poison, double poison, double poison, double 2.000000e+01>, [[VECTOR_PH]] ], [ [[WIDE_LOAD]], [[VECTOR_BODY]] ]
 ; CHECK-NEXT:    [[OFFSET_IDX:%.*]] = add i64 1, [[INDEX]]
 ; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[OFFSET_IDX]], 0
 ; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds double, ptr [[PTR:%.*]], i64 [[TMP0]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds double, ptr [[TMP1]], i32 0
 ; CHECK-NEXT:    [[WIDE_LOAD]] = load <4 x double>, ptr [[TMP2]], align 8
 ; CHECK-NEXT:    [[TMP3:%.*]] = shufflevector <4 x double> [[VECTOR_RECUR1]], <4 x double> [[WIDE_LOAD]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
-; CHECK-NEXT:    [[TMP4:%.*]] = shufflevector <4 x double> [[VECTOR_RECUR]], <4 x double> [[WIDE_LOAD]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
-; CHECK-NEXT:    [[TMP5:%.*]] = fadd <4 x double> <double 1.000000e+01, double 1.000000e+01, double 1.000000e+01, double 1.000000e+01>, [[TMP3]]
-; CHECK-NEXT:    [[TMP6:%.*]] = fadd <4 x double> [[TMP5]], [[TMP4]]
+; CHECK-NEXT:    [[TMP4:%.*]] = fadd <4 x double> <double 1.000000e+01, double 1.000000e+01, double 1.000000e+01, double 1.000000e+01>, [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = shufflevector <4 x double> [[VECTOR_RECUR]], <4 x double> [[WIDE_LOAD]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
+; CHECK-NEXT:    [[TMP6:%.*]] = fadd <4 x double> [[TMP4]], [[TMP5]]
 ; CHECK-NEXT:    store <4 x double> [[TMP6]], ptr [[TMP2]], align 8
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 ; CHECK-NEXT:    [[TMP7:%.*]] = icmp eq i64 [[INDEX_NEXT]], 996
 ; CHECK-NEXT:    br i1 [[TMP7]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP22:![0-9]+]]
 ; CHECK:       middle.block:
 ; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 999, 996
 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT:%.*]] = extractelement <4 x double> [[WIDE_LOAD]], i32 3
 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI:%.*]] = extractelement <4 x double> [[WIDE_LOAD]], i32 2