[VPlan] Add first VPlan version of sinkScalarOperands.

[fhahn]

Summary

This patch adds a first VPlan-based implementation of sinking of scalar
operands.

The current version traverse a VPlan once and processes all operands of
a predicated REPLICATE recipe. If one of those operands can be sunk,
it is moved to the block containing the predicated REPLICATE recipe.
Continue with processing the operands of the sunk recipe.

The initial version does not re-process candidates after other recipes
have been sunk. It also cannot partially sink induction increments at
the moment. The VPlan only contains WIDEN-INDUCTION recipes and if the
induction is used for example in a GEP, only the first lane is used and
in the lowered IR the adds for the other lanes can be sunk into the
predicated blocks.

[gilr]

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

129

use VPBB instead?

[fhahn]

Updated to use VPBB in the lambda, thanks!

I think the original code also had a bug that meant we would sink instructions that may read from memory, which would be incorrect if we move it across a instruction that may modify the read memory. I added a new test case and I think the original sinkScalarOperands gets this wrong as well.

I also put up D100857, which adjusts the logic in the legacy version of sinkScalarOperands to only handle the scalar parts of recipes that cannot be sunk by the Vplan-to-Vplan sinkScalarOperands. This requires a bit more code, so I put it up as a separate patch, but it could also be folded into this one.

[gilr]

Very nice step forward!!

llvm/lib/Transforms/Vectorize/VPlan.h

1279 ↗

(On Diff #338869)

Allowing to reset IsPredicated seems a bit fragile, as alsoPack is computed on contruction based on it. Since this patch only requires setting IsPredicated, perhaps better to have setIsPredicated() { IsPredicated = true; }. Might be worth adding a comment here that setting IsPredicated late is consistent with alsoPack being initialized to false as all users of the sunk recipes reside within the replicated region so no packing is required.

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

108

Traversing the VPlan in this case doesn't require RPOT, right? can be done with a more efficient recursive scan?
Simpler to first collect all seeds into a worklist, saving the need to make early increments? If so, can alternatively be done by RecipeBuilder during VPlan construction.

128

Should be return !UI || UI->getParent() != VPBB?

133

Would be good to leave a comment here explaining that setting IsPredicated is done in favor of the legacy sinkScalarOperands() which still follows.

[fhahn]

use depth-first instead of RPO, add comment for setting IsPredicated and assertion.

[fhahn]

llvm/lib/Transforms/Vectorize/VPlan.h

1279 ↗

(On Diff #338869)

Agreed! I added a comment and an assertion.

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

108

That's a good point, the traversal order should not matter. I updated it to use depth-first.

Simpler to first collect all seeds into a worklist, saving the need to make early increments? If so, can alternatively be done by RecipeBuilder during VPlan construction.

It may be simpler, but would introduce coupling with the recipe builder and I am not sure that's desired at this point? It seems like it may limit composability of VPlan transforms (e.g. if another transform introduces new predicated recipes, it may have to update the list of seed instructions in the builder or somewhere else)

128

Yes I think so, great catch!

[fhahn]

Remove need for setIsPredicate() by instead considering the operands of sink candidates in PredBB in the worklist as well.

[fhahn]

ping :)

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4609

Perhaps worth noting that VPlan's sinkScalarOperands() was responsible for sinking the instruction into PredBB in this case, but may have failed to sink its (direct or indirect) operands, which we try again here.

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

108

Simpler to first collect all seeds into a worklist, saving the need to make early increments?

I.e., instead of operating in-place using make_early_inc_range(), and somewhat similar to the original sinkScalarOperand()'s use of PredicatedInstructions, would it be better to first enlist all candidates into WorkList, and then loop over it? VPBB can be set to the parent of the first user, which all other users must agree with via the any_of(). In any case, better reuse VPBB instead of RepR->getParent(); and choose more meaningful names than Current, RepR and VPBB to deal with sinking a source Def into the destination basic block where all its Users reside.

Interesting to see that InstsToReanalyze is not needed, presumably because the last user to sink would always trigger the potential sinking of its def? Probably worth a note.

127

Note that in general, insertion point should be after all phi's, but none are expected in VPBB; right?

[fhahn]

Address comments, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4609

I updated the comment to reference VPlanTransforms::sinkScalarOperands and the interaction here.

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

108

I updated the code to first collect all instructions in the initial worklist and then process them separately.

I also adjusted the variable names.

It looks like InstsToReanalyze is not required for any existing test cases, even for the implementation in LV. I tried to construct cases, but if a recipe is used by multiple recipes that are to be sunk, the one that is used multiple times does not get scalarized. I think it's not needed, because if we sink a recipe, its operands get added to the worklist again and the only way it enables further sinking is that there must be a def-use relation between to newly sunk recipe and the one we need to re-try.

127

Yes, there cannot be any PHI recipes in the block, but nevertheless it won't hurt to get the first non-phi recipe, in case that changes in the future. Updated the code.

[Ayal]

Thanks for the changes!
Few remaining nits.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4611

To avoid confusion may help to state more accurately. VPlan's sinkScalarOperands() succeeded in sinking the scalar instruction I, hence it appears in PredBB; but it may have failed to sink I's operands (recursively), which we try (again) here.

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

128

Therefor[e].

Note that SinkCandidate must have at-least one user.
Should cast<recipe>(first user) be dyn_cast (as below), or else drop checking if it's null?
(Note that sinkScalarOperands should not encounter 'native's block users, so it should be ok to cast the first user into a recipe.)

132

Is the cast<VPBasicBlock> needed for SinkTo? (due to const(?))

[fhahn]

Address latest comments, thanks!

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4611

updated the comment, thanks!

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

128

Updated to use a dyn_cast, so the code does not need to rely on what kinds of plans are passed in.

132

Removed, it's not needed.

[Ayal]

Looks good to me, thanks!

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

108

Interesting; might be worth removing the presumably redundant InstsToReanalyze, in a separate patch.
In any case, VPlan's sinkScalarOperands() should be enhanced to retire the original sinkScalarOperands() altogether.

127

"Therefor the" >> "Therefore the"

[fhahn]

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

127

Ah yes! Fixed in the committed version, thanks!

[uabelho]

Hello!

The following starts failing with htis patch:

opt -loop-vectorize -force-vector-width=2 -S -o - bbi-56568.ll

Result:

Instruction does not dominate all uses!
  %2 = getelementptr inbounds [9 x i16], [9 x i16]* @v_102, i16 0, i16 undef
  %7 = load i16, i16* %2, align 1
opt: ../lib/Transforms/Vectorize/LoopVectorize.cpp:10200: bool llvm::LoopVectorizePass::processLoop(llvm::Loop *): Assertion `!verifyFunction(*L->getHeader()->getParent(), &dbgs())' failed.

bbi-56568.ll758 BDownload

[fhahn]

In D100258#2784242, @uabelho wrote:

Hello!

The following starts failing with htis patch:

opt -loop-vectorize -force-vector-width=2 -S -o - bbi-56568.ll

Result:

Instruction does not dominate all uses!
  %2 = getelementptr inbounds [9 x i16], [9 x i16]* @v_102, i16 0, i16 undef
  %7 = load i16, i16* %2, align 1
opt: ../lib/Transforms/Vectorize/LoopVectorize.cpp:10200: bool llvm::LoopVectorizePass::processLoop(llvm::Loop *): Assertion `!verifyFunction(*L->getHeader()->getParent(), &dbgs())' failed.

bbi-56568.ll758 BDownload

Thanks for the report. The issue appears to be that we sink a uniform replicate recipe. We only generate lane 0 for such recipes, so sinking should not be beneficial and it causes the crash because all users use lane 0, which will be generated in a conditional block after sinking. Should be fixed in 38641ddf3e56

[uabelho]

In D100258#2784575, @fhahn wrote:

In D100258#2784242, @uabelho wrote:

Hello!

The following starts failing with htis patch:

opt -loop-vectorize -force-vector-width=2 -S -o - bbi-56568.ll

Result:

Instruction does not dominate all uses!
  %2 = getelementptr inbounds [9 x i16], [9 x i16]* @v_102, i16 0, i16 undef
  %7 = load i16, i16* %2, align 1
opt: ../lib/Transforms/Vectorize/LoopVectorize.cpp:10200: bool llvm::LoopVectorizePass::processLoop(llvm::Loop *): Assertion `!verifyFunction(*L->getHeader()->getParent(), &dbgs())' failed.

bbi-56568.ll758 BDownload

Thanks for the report. The issue appears to be that we sink a uniform replicate recipe. We only generate lane 0 for such recipes, so sinking should not be beneficial and it causes the crash because all users use lane 0, which will be generated in a conditional block after sinking. Should be fixed in 38641ddf3e56

Thanks!

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

do {
     // reset the changed indicator.
     Worklist.insert(InstsToReanalyze.begin(), InstsToReanalyze.end());
     InstsToReanalyze.clear();
     Changed = false;
 
     while (!Worklist.empty()) {
       auto *I = dyn_cast<Instruction>(Worklist.pop_back_val());
 
-      // We can't sink an instruction if it is a phi node, is already in the
-      // predicated block, is not in the loop, or may have side effects.
-      if (!I || isa<PHINode>(I) || I->getParent() == PredBB ||
-          !VectorLoop->contains(I) || I->mayHaveSideEffects())
+      // We can't sink an instruction if it is a phi node, is not in the loop,
+      // or may have side effects.
+      if (!I || isa<PHINode>(I) || !VectorLoop->contains(I) ||
+          I->mayHaveSideEffects())
         continue;
 
+      // If the instruction is already in PredBB, check if we can sink its
+      // operands. In that case, VPlan's sinkScalarOperands() succeeded in
+      // sinking the scalar instruction I, hence it appears in PredBB; but it
+      // may have failed to sink I's operands (recursively), which we try
+      // (again) here.
+      if (I->getParent() == PredBB) {
+        Worklist.insert(I->op_begin(), I->op_end());
+        continue;
+      }
+
       // It's legal to sink the instruction if all its uses occur in the
       // predicated block. Otherwise, there's nothing to do yet, and we may
       // need to reanalyze the instruction.
       if (!llvm::all_of(I->uses(), isBlockOfUsePredicated)) {
         InstsToReanalyze.push_back(I);
         continue;
       }
 
for (auto &Reduction : Legal->getReductionVars()) {
       if (CM.isInLoopReduction(Reduction.first))
         continue;
       VPValue *Phi = Plan->getOrAddVPValue(Reduction.first);
       VPValue *Red = Plan->getOrAddVPValue(Reduction.second.getLoopExitInstr());
       Builder.createNaryOp(Instruction::Select, {Cond, Red, Phi});
     }
   }
 
+  VPlanTransforms::sinkScalarOperands(*Plan);
+
   std::string PlanName;
   raw_string_ostream RSO(PlanName);
   ElementCount VF = Range.Start;
   Plan->addVF(VF);
   RSO << "Initial VPlan for VF={" << VF;
   for (VF *= 2; ElementCount::isKnownLT(VF, Range.End); VF *= 2) {
     Plan->addVF(VF);
     RSO << "," << VF;

llvm/lib/Transforms/Vectorize/VPlanTransforms.h

 
 struct VPlanTransforms {
   /// Replaces the VPInstructions in \p Plan with corresponding
   /// widen recipes.
   static void VPInstructionsToVPRecipes(
       Loop *OrigLoop, VPlanPtr &Plan,
       LoopVectorizationLegality::InductionList &Inductions,
       SmallPtrSetImpl<Instruction *> &DeadInstructions, ScalarEvolution &SE);
+
+  static bool sinkScalarOperands(VPlan &Plan);
 };
 
 } // namespace llvm
 
 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLANTRANSFORMS_H

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

for (auto I = VPBB->begin(), E = VPBB->end(); I != E;) {
       Ingredient->eraseFromParent();
       Plan->removeVPValueFor(Inst);
       for (auto *Def : NewRecipe->definedValues()) {
         Plan->addVPValue(Inst, Def);
       }
     }
   }
 }
+
+bool VPlanTransforms::sinkScalarOperands(VPlan &Plan) {
+  auto Iter = depth_first(
+      VPBlockRecursiveTraversalWrapper<VPBlockBase *>(Plan.getEntry()));
+  bool Changed = false;
+  // First, collect the operands of all predicated replicate recipes as seeds
+  // for sinking.
+  SetVector<VPValue *> WorkList;
+  for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(Iter)) {
+    for (auto &Recipe : *VPBB) {
+      auto *RepR = dyn_cast<VPReplicateRecipe>(&Recipe);
+      if (!RepR || !RepR->isPredicated())
+        continue;
+      WorkList.insert(RepR->op_begin(), RepR->op_end());
+    }
+  }
+
+  // Try to sink each replicate recipe in the worklist.
+  while (!WorkList.empty()) {
+    auto *C = WorkList.pop_back_val();
+    auto *SinkCandidate = dyn_cast_or_null<VPReplicateRecipe>(C->Def);
+    if (!SinkCandidate)
+      continue;
+
+    // All users of SinkCandidate must be in the same block in order to perform
+    // sinking. Therefore the destination block for sinking must match the block
+    // containing the first user.
+    auto *FirstUser = dyn_cast<VPRecipeBase>(*SinkCandidate->user_begin());
+    if (!FirstUser)
+      continue;
+    VPBasicBlock *SinkTo = FirstUser->getParent();
+    if (SinkCandidate->getParent() == SinkTo ||
+        SinkCandidate->mayHaveSideEffects() ||
+        SinkCandidate->mayReadOrWriteMemory())
+      continue;
+
+    // All recipe users of the sink candidate must be in the same block SinkTo.
+    if (any_of(SinkCandidate->users(), [SinkTo](VPUser *U) {
+          auto *UI = dyn_cast<VPRecipeBase>(U);
+          return !UI || UI->getParent() != SinkTo;
+        }))
+      continue;
+
+    SinkCandidate->moveBefore(*SinkTo, SinkTo->getFirstNonPhi());
+    WorkList.insert(SinkCandidate->op_begin(), SinkCandidate->op_end());
+    Changed = true;
+  }
+  return Changed;
+}

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

 ; CHECK-NEXT:    [[NEXT_GEP6:%.*]] = getelementptr i16, i16* [[SRC]], i64 [[TMP14]]
 ; CHECK-NEXT:    [[TMP15:%.*]] = load i16, i16* [[NEXT_GEP6]], align 2
 ; CHECK-NEXT:    br label [[PRED_LOAD_CONTINUE16]]
 ; CHECK:       pred.load.continue16:
 ; CHECK-NEXT:    [[TMP16:%.*]] = phi i16 [ poison, [[PRED_LOAD_CONTINUE14]] ], [ [[TMP15]], [[PRED_LOAD_IF15]] ]
 ; CHECK-NEXT:    [[TMP17:%.*]] = extractelement <4 x i1> [[TMP1]], i32 0
 ; CHECK-NEXT:    br i1 [[TMP17]], label [[PRED_STORE_IF:%.*]], label [[PRED_STORE_CONTINUE:%.*]]
 ; CHECK:       pred.store.if:
+; CHECK-NEXT:    [[NEXT_GEP7:%.*]] = getelementptr i32, i32* [[DST:%.*]], i64 [[INDEX]]
 ; CHECK-NEXT:    [[TMP18:%.*]] = zext i16 [[TMP4]] to i32
 ; CHECK-NEXT:    [[TMP19:%.*]] = shl nuw nsw i32 [[TMP18]], 7
-; CHECK-NEXT:    [[NEXT_GEP7:%.*]] = getelementptr i32, i32* [[DST:%.*]], i64 [[INDEX]]
 ; CHECK-NEXT:    store i32 [[TMP19]], i32* [[NEXT_GEP7]], align 4
 ; CHECK-NEXT:    br label [[PRED_STORE_CONTINUE]]
 ; CHECK:       pred.store.continue:
 ; CHECK-NEXT:    [[TMP20:%.*]] = extractelement <4 x i1> [[TMP1]], i32 1
 ; CHECK-NEXT:    br i1 [[TMP20]], label [[PRED_STORE_IF17:%.*]], label [[PRED_STORE_CONTINUE18:%.*]]
 ; CHECK:       pred.store.if17:
-; CHECK-NEXT:    [[TMP21:%.*]] = zext i16 [[TMP8]] to i32
-; CHECK-NEXT:    [[TMP22:%.*]] = shl nuw nsw i32 [[TMP21]], 7
-; CHECK-NEXT:    [[TMP23:%.*]] = or i64 [[INDEX]], 1
-; CHECK-NEXT:    [[NEXT_GEP8:%.*]] = getelementptr i32, i32* [[DST]], i64 [[TMP23]]
-; CHECK-NEXT:    store i32 [[TMP22]], i32* [[NEXT_GEP8]], align 4
+; CHECK-NEXT:    [[TMP21:%.*]] = or i64 [[INDEX]], 1
+; CHECK-NEXT:    [[NEXT_GEP8:%.*]] = getelementptr i32, i32* [[DST]], i64 [[TMP21]]
+; CHECK-NEXT:    [[TMP22:%.*]] = zext i16 [[TMP8]] to i32
+; CHECK-NEXT:    [[TMP23:%.*]] = shl nuw nsw i32 [[TMP22]], 7
+; CHECK-NEXT:    store i32 [[TMP23]], i32* [[NEXT_GEP8]], align 4
 ; CHECK-NEXT:    br label [[PRED_STORE_CONTINUE18]]
 ; CHECK:       pred.store.continue18:
 ; CHECK-NEXT:    [[TMP24:%.*]] = extractelement <4 x i1> [[TMP1]], i32 2
 ; CHECK-NEXT:    br i1 [[TMP24]], label [[PRED_STORE_IF19:%.*]], label [[PRED_STORE_CONTINUE20:%.*]]
 ; CHECK:       pred.store.if19:
-; CHECK-NEXT:    [[TMP25:%.*]] = zext i16 [[TMP12]] to i32
-; CHECK-NEXT:    [[TMP26:%.*]] = shl nuw nsw i32 [[TMP25]], 7
-; CHECK-NEXT:    [[TMP27:%.*]] = or i64 [[INDEX]], 2
-; CHECK-NEXT:    [[NEXT_GEP9:%.*]] = getelementptr i32, i32* [[DST]], i64 [[TMP27]]
-; CHECK-NEXT:    store i32 [[TMP26]], i32* [[NEXT_GEP9]], align 4
+; CHECK-NEXT:    [[TMP25:%.*]] = or i64 [[INDEX]], 2
+; CHECK-NEXT:    [[NEXT_GEP9:%.*]] = getelementptr i32, i32* [[DST]], i64 [[TMP25]]
+; CHECK-NEXT:    [[TMP26:%.*]] = zext i16 [[TMP12]] to i32
+; CHECK-NEXT:    [[TMP27:%.*]] = shl nuw nsw i32 [[TMP26]], 7
+; CHECK-NEXT:    store i32 [[TMP27]], i32* [[NEXT_GEP9]], align 4
 ; CHECK-NEXT:    br label [[PRED_STORE_CONTINUE20]]
 ; CHECK:       pred.store.continue20:
 ; CHECK-NEXT:    [[TMP28:%.*]] = extractelement <4 x i1> [[TMP1]], i32 3
 ; CHECK-NEXT:    br i1 [[TMP28]], label [[PRED_STORE_IF21:%.*]], label [[PRED_STORE_CONTINUE22]]
 ; CHECK:       pred.store.if21:
-; CHECK-NEXT:    [[TMP29:%.*]] = zext i16 [[TMP16]] to i32
-; 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:    [[TMP29:%.*]] = or i64 [[INDEX]], 3
+; CHECK-NEXT:    [[NEXT_GEP10:%.*]] = getelementptr i32, i32* [[DST]], i64 [[TMP29]]
+; CHECK-NEXT:    [[TMP30:%.*]] = zext i16 [[TMP16]] to i32
+; CHECK-NEXT:    [[TMP31:%.*]] = shl nuw nsw i32 [[TMP30]], 7
+; CHECK-NEXT:    store i32 [[TMP31]], 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]], [[LOOP12:!llvm.loop !.*]]
 ; CHECK:       middle.block:
 ; CHECK-NEXT:    br i1 true, label [[TMP34:%.*]], label [[SCALAR_PH]]
 ; CHECK:       scalar.ph:

llvm/test/Transforms/LoopVectorize/first-order-recurrence-sink-replicate-region.ll

 ; CHECK:      VPlan 'Initial VPlan for VF={2},UF>=1' {
 ; CHECK-NEXT: loop:
 ; CHECK-NEXT:   WIDEN-PHI %0 = phi 0, %conv
 ; CHECK-NEXT:   WIDEN-INDUCTION %iv = phi 0, %iv.next
 ; CHECK-NEXT:   EMIT vp<%3> = icmp ule ir<%iv> vp<%0>
 ; CHECK-NEXT: Successor(s): loop.0
 
 ; CHECK:      loop.0:
-; CHECK-NEXT:   REPLICATE ir<%gep> = getelementptr ir<%ptr>, ir<%iv>
 ; CHECK-NEXT: Successor(s): pred.load
 
 ; CHECK:     <xVFxUF> pred.load: {
 ; CHECK-NEXT:   pred.load.entry:
 ; CHECK-NEXT:     BRANCH-ON-MASK vp<%3>
 ; CHECK-NEXT:   Successor(s): pred.load.if, pred.load.continue
 ; CHECK-NEXT:   CondBit: vp<%3> (loop)
 
 ; CHECK:      pred.load.if:
+; CHECK-NEXT:     REPLICATE ir<%gep> = getelementptr ir<%ptr>, ir<%iv>
 ; CHECK-NEXT:     REPLICATE ir<%lv> = load ir<%gep> (S->V)
 ; CHECK-NEXT:   Successor(s): pred.load.continue
 
 ; CHECK:      pred.load.continue:
 ; CHECK-NEXT:     PHI-PREDICATED-INSTRUCTION vp<%6> = ir<%lv>
 ; CHECK-NEXT:   No successors
 ; CHECK-NEXT: }
 

 ; CHECK-NEXT:   Successor(s): pred.srem.continue
 
 ; CHECK:      pred.srem.continue:
 ; CHECK-NEXT:     PHI-PREDICATED-INSTRUCTION vp<%6> = ir<%rem>
 ; CHECK-NEXT:   No successors
 ; CHECK-NEXT: }
 
 ; CHECK:     loop.0.split:
-; CHECK-NEXT:   REPLICATE ir<%add> = add vp<%6>, ir<%recur.next>
-; CHECK-NEXT:   REPLICATE ir<%gep> = getelementptr ir<%ptr>, ir<%iv>
 ; CHECK-NEXT: Successor(s): pred.store
 
 ; CHECK:      <xVFxUF> pred.store: {
 ; CHECK-NEXT:   pred.store.entry:
 ; CHECK-NEXT:     BRANCH-ON-MASK vp<%3>
 ; CHECK-NEXT:   Successor(s): pred.store.if, pred.store.continue
 ; CHECK-NEXT:   CondBit: vp<%3> (loop)
 
 ; CHECK:      pred.store.if:
+; CHECK-NEXT:     REPLICATE ir<%add> = add vp<%6>, ir<%recur.next>
+; CHECK-NEXT:     REPLICATE ir<%gep> = getelementptr ir<%ptr>, ir<%iv>
 ; CHECK-NEXT:     REPLICATE store ir<%add>, ir<%gep>
 ; CHECK-NEXT:   Successor(s): pred.store.continue
 
 ; CHECK:     pred.store.continue:
 ; CHECK-NEXT:   No successors
 ; CHECK-NEXT: }
 
 ; CHECK:      loop.1:

llvm/test/Transforms/LoopVectorize/if-pred-stores.ll

 ; VEC-NEXT:    [[TMP6:%.*]] = extractelement <2 x i32> [[WIDE_LOAD]], i32 0
 ; VEC-NEXT:    [[TMP7:%.*]] = add nsw i32 [[TMP6]], 20
 ; VEC-NEXT:    store i32 [[TMP7]], i32* [[TMP1]], align 4
 ; VEC-NEXT:    br label [[PRED_STORE_CONTINUE]]
 ; VEC:       pred.store.continue:
 ; VEC-NEXT:    [[TMP8:%.*]] = extractelement <2 x i1> [[TMP4]], i32 1
 ; VEC-NEXT:    br i1 [[TMP8]], label [[PRED_STORE_IF1:%.*]], label [[PRED_STORE_CONTINUE2]]
 ; VEC:       pred.store.if1:
-; VEC-NEXT:    [[TMP9:%.*]] = extractelement <2 x i32> [[WIDE_LOAD]], i32 1
-; VEC-NEXT:    [[TMP10:%.*]] = add nsw i32 [[TMP9]], 20
-; VEC-NEXT:    [[TMP11:%.*]] = add i64 [[INDEX]], 1
-; VEC-NEXT:    [[TMP12:%.*]] = getelementptr inbounds i32, i32* [[F]], i64 [[TMP11]]
-; VEC-NEXT:    store i32 [[TMP10]], i32* [[TMP12]], align 4
+; VEC-NEXT:    [[TMP9:%.*]] = add i64 [[INDEX]], 1
+; VEC-NEXT:    [[TMP10:%.*]] = getelementptr inbounds i32, i32* [[F]], i64 [[TMP9]]
+; VEC-NEXT:    [[TMP11:%.*]] = extractelement <2 x i32> [[WIDE_LOAD]], i32 1
+; VEC-NEXT:    [[TMP12:%.*]] = add nsw i32 [[TMP11]], 20
+; VEC-NEXT:    store i32 [[TMP12]], i32* [[TMP10]], align 4
 ; VEC-NEXT:    br label [[PRED_STORE_CONTINUE2]]
 ; VEC:       pred.store.continue2:
 ; VEC-NEXT:    [[INDEX_NEXT]] = add i64 [[INDEX]], 2
 ; VEC-NEXT:    [[TMP13:%.*]] = icmp eq i64 [[INDEX_NEXT]], 128
 ; VEC-NEXT:    br i1 [[TMP13]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], [[LOOP0:!llvm.loop !.*]]
 ; VEC:       middle.block:
 ; VEC-NEXT:    [[CMP_N:%.*]] = icmp eq i64 128, 128
 ; VEC-NEXT:    br i1 [[CMP_N]], label [[FOR_END:%.*]], label [[FOR_BODY:%.*]]

 ; VEC-NEXT:    [[TMP7:%.*]] = zext i8 [[TMP6]] to i32
 ; VEC-NEXT:    [[TMP8:%.*]] = trunc i32 [[TMP7]] to i8
 ; VEC-NEXT:    store i8 [[TMP8]], i8* [[TMP2]], align 1
 ; VEC-NEXT:    br label [[PRED_STORE_CONTINUE]]
 ; VEC:       pred.store.continue:
 ; VEC-NEXT:    [[TMP9:%.*]] = extractelement <2 x i1> [[BROADCAST_SPLAT]], i32 1
 ; VEC-NEXT:    br i1 [[TMP9]], label [[PRED_STORE_IF2:%.*]], label [[PRED_STORE_CONTINUE3]]
 ; VEC:       pred.store.if2:
-; VEC-NEXT:    [[TMP10:%.*]] = extractelement <2 x i8> [[WIDE_LOAD]], i32 1
-; VEC-NEXT:    [[TMP11:%.*]] = zext i8 [[TMP10]] to i32
-; VEC-NEXT:    [[TMP12:%.*]] = trunc i32 [[TMP11]] to i8
-; VEC-NEXT:    [[TMP13:%.*]] = add i64 [[INDEX]], 1
-; VEC-NEXT:    [[TMP14:%.*]] = getelementptr i8, i8* undef, i64 [[TMP13]]
-; VEC-NEXT:    store i8 [[TMP12]], i8* [[TMP14]], align 1
+; VEC-NEXT:    [[TMP10:%.*]] = add i64 [[INDEX]], 1
+; VEC-NEXT:    [[TMP11:%.*]] = getelementptr i8, i8* undef, i64 [[TMP10]]
+; VEC-NEXT:    [[TMP12:%.*]] = extractelement <2 x i8> [[WIDE_LOAD]], i32 1
+; VEC-NEXT:    [[TMP13:%.*]] = zext i8 [[TMP12]] to i32
+; VEC-NEXT:    [[TMP14:%.*]] = trunc i32 [[TMP13]] to i8
+; VEC-NEXT:    store i8 [[TMP14]], i8* [[TMP11]], align 1
 ; VEC-NEXT:    br label [[PRED_STORE_CONTINUE3]]
 ; VEC:       pred.store.continue3:
 ; VEC-NEXT:    [[INDEX_NEXT]] = add i64 [[INDEX]], 2
 ; VEC-NEXT:    [[TMP15:%.*]] = icmp eq i64 [[INDEX_NEXT]], undef
 ; VEC-NEXT:    br i1 [[TMP15]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], [[LOOP5:!llvm.loop !.*]]
 ; VEC:       middle.block:
 ; VEC-NEXT:    [[CMP_N:%.*]] = icmp eq i64 undef, undef
 ; VEC-NEXT:    br i1 [[CMP_N]], label [[FOR_END:%.*]], label [[FOR_BODY:%.*]]

llvm/test/Transforms/LoopVectorize/vplan-sink-scalars-and-merge-vf1.ll

 ; REQUIRES: asserts
 
 ; RUN: opt -loop-vectorize -force-vector-interleave=2 -force-vector-width=1 -debug -disable-output %s 2>&1 | FileCheck %s
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 
 ; Make sure recipes with side-effects are not sunk.
 define void @sink_with_sideeffects(i1 %c, i8* %ptr) {
 ; CHECK-LABEL: sink_with_sideeffects
 ; CHECK:      VPlan 'Initial VPlan for VF={1},UF>=1' {
 ; CHECK-NEXT: for.body:
 ; CHECK-NEXT:   WIDEN-INDUCTION %tmp0 = phi %tmp6, 0
 ; CHECK-NEXT:   WIDEN-INDUCTION %tmp1 = phi %tmp7, 0
 ; CHECK-NEXT:   CLONE ir<%tmp2> = getelementptr ir<%ptr>, ir<%tmp0>
 ; CHECK-NEXT:   CLONE ir<%tmp3> = load ir<%tmp2>
 ; CHECK-NEXT:   CLONE store ir<0>, ir<%tmp2>
-; CHECK-NEXT:   CLONE ir<%tmp4> = zext ir<%tmp3>
-; CHECK-NEXT:   CLONE ir<%tmp5> = trunc ir<%tmp4>
 ; CHECK-NEXT: Successor(s): if.then
 
 ; CHECK:      if.then:
 ; CHECK-NEXT: Successor(s): pred.store
 
 ; CHECK:      <xVFxUF> pred.store: {
 ; CHECK-NEXT:   pred.store.entry:
 ; CHECK-NEXT:     BRANCH-ON-MASK ir<%c>
 ; CHECK-NEXT:   Successor(s): pred.store.if, pred.store.continue
 ; CHECK-NEXT:   CondBit: ir<%c>
 
 ; CHECK:      pred.store.if:
+; CHECK-NEXT:   CLONE ir<%tmp4> = zext ir<%tmp3>
+; CHECK-NEXT:   CLONE ir<%tmp5> = trunc ir<%tmp4>
 ; CHECK-NEXT:   CLONE store ir<%tmp5>, ir<%tmp2>
 ; CHECK-NEXT:   Successor(s): pred.store.continue
 
 ; CHECK:      pred.store.continue:
 ; CHECK-NEXT:   No successors
 ; CHECK-NEXT: }
 
 ; CHECK:      if.then.0:

llvm/test/Transforms/LoopVectorize/vplan-sink-scalars-and-merge.ll

 ; REQUIRES: asserts
 
 ; RUN: opt -loop-vectorize -force-vector-interleave=1 -force-vector-width=2 -debug -disable-output %s 2>&1 | FileCheck %s
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 
 @a = common global [2048 x i32] zeroinitializer, align 16
 @b = common global [2048 x i32] zeroinitializer, align 16
 @c = common global [2048 x i32] zeroinitializer, align 16
 
 
 ; CHECK-LABEL: LV: Checking a loop in "sink1"
 ; CHECK:      VPlan 'Initial VPlan for VF={2},UF>=1' {
 ; CHECK-NEXT: loop:
 ; CHECK-NEXT:   WIDEN-INDUCTION %indvars.iv = phi 0, %indvars.iv.next
 ; CHECK-NEXT:   EMIT vp<%2> = icmp ule ir<%indvars.iv> vp<%0>
-; CHECK-NEXT:   REPLICATE ir<%gep.b> = getelementptr ir<@b>, ir<0>, ir<%indvars.iv>
 ; CHECK-NEXT: Successor(s): pred.load
 
 ; CHECK:       <xVFxUF> pred.load: {
 ; CHECK-NEXT:   pred.load.entry:
 ; CHECK-NEXT:     BRANCH-ON-MASK vp<%2>
 ; CHECK-NEXT:   Successor(s): pred.load.if, pred.load.continue
 ; CHECK-NEXT:   CondBit: vp<%2> (loop)
 
 ; CHECK:       pred.load.if:
+; CHECK-NEXT:     REPLICATE ir<%gep.b> = getelementptr ir<@b>, ir<0>, ir<%indvars.iv>
 ; CHECK-NEXT:     REPLICATE ir<%lv.b> = load ir<%gep.b>
 ; CHECK-NEXT:   Successor(s): pred.load.continue
 
 ; CHECK:      pred.load.continue:
 ; CHECK-NEXT:     PHI-PREDICATED-INSTRUCTION vp<%5> = ir<%lv.b>
 ; CHECK-NEXT:   No successors
 ; CHECK-NEXT: }
 
 ; CHECK:      loop.0:
-; CHECK-NEXT:   REPLICATE ir<%add> = add vp<%5>, ir<10>
-; CHECK-NEXT:   REPLICATE ir<%mul> = mul ir<2>, ir<%add>
-; CHECK-NEXT:   REPLICATE ir<%gep.a> = getelementptr ir<@a>, ir<0>, ir<%indvars.iv>
 ; CHECK-NEXT: Successor(s): pred.store
 
 ; CHECK:      <xVFxUF> pred.store: {
 ; CHECK-NEXT:   pred.store.entry:
 ; CHECK-NEXT:     BRANCH-ON-MASK vp<%2>
 ; CHECK-NEXT:   Successor(s): pred.store.if, pred.store.continue
 ; CHECK-NEXT:   CondBit: vp<%2> (loop)
 
 ; CHECK:      pred.store.if:
+; CHECK-NEXT:     REPLICATE ir<%add> = add vp<%5>, ir<10>
+; CHECK-NEXT:     REPLICATE ir<%mul> = mul ir<2>, ir<%add>
+; CHECK-NEXT:     REPLICATE ir<%gep.a> = getelementptr ir<@a>, ir<0>, ir<%indvars.iv>
 ; CHECK-NEXT:     REPLICATE store ir<%mul>, ir<%gep.a>
 ; CHECK-NEXT:   Successor(s): pred.store.continue
 
 ; CHECK:      pred.store.continue:
 ; CHECK-NEXT:   No successors
 ; CHECK-NEXT: }
 
 ; CHECK:      loop.1:
exit:
   ret void
 }
 
 ; CHECK-LABEL: LV: Checking a loop in "sink2"
 ; CHECK:      VPlan 'Initial VPlan for VF={2},UF>=1' {
 ; CHECK-NEXT: loop:
 ; CHECK-NEXT:   WIDEN-INDUCTION %indvars.iv = phi 0, %indvars.iv.next
 ; CHECK-NEXT:   EMIT vp<%2> = icmp ule ir<%indvars.iv> vp<%0>
-; CHECK-NEXT:   REPLICATE ir<%gep.b> = getelementptr ir<@b>, ir<0>, ir<%indvars.iv>
 ; CHECK-NEXT: Successor(s): pred.load
 
 ; CHECK:      <xVFxUF> pred.load: {
 ; CHECK-NEXT:   pred.load.entry:
 ; CHECK-NEXT:     BRANCH-ON-MASK vp<%2>
 ; CHECK-NEXT:   Successor(s): pred.load.if, pred.load.continue
 ; CHECK-NEXT:   CondBit: vp<%2> (loop)
 
 ; CHECK:      pred.load.if:
+; CHECK-NEXT:     REPLICATE ir<%gep.b> = getelementptr ir<@b>, ir<0>, ir<%indvars.iv>
 ; CHECK-NEXT:     REPLICATE ir<%lv.b> = load ir<%gep.b>
 ; CHECK-NEXT:   Successor(s): pred.load.continue
 
 ; CHECK:      pred.load.continue:
 ; CHECK-NEXT:     PHI-PREDICATED-INSTRUCTION vp<%5> = ir<%lv.b>
 ; CHECK-NEXT:   No successors
 ; CHECK-NEXT: }
 
 ; CHECK:      loop.0:
-; CHECK-NEXT:   REPLICATE ir<%add> = add vp<%5>, ir<10>
 ; CHECK-NEXT:   WIDEN ir<%mul> = mul ir<%indvars.iv>, ir<2>
-; CHECK-NEXT:   REPLICATE ir<%gep.a> = getelementptr ir<@a>, ir<0>, ir<%mul>
 ; CHECK-NEXT: Successor(s): pred.store
 
 ; CHECK:      <xVFxUF> pred.store: {
 ; CHECK-NEXT:   pred.store.entry:
 ; CHECK-NEXT:     BRANCH-ON-MASK vp<%2>
 ; CHECK-NEXT:   Successor(s): pred.store.if, pred.store.continue
 ; CHECK-NEXT:   CondBit: vp<%2> (loop)
 
 ; CHECK:       pred.store.if:
+; CHECK-NEXT:     REPLICATE ir<%add> = add vp<%5>, ir<10>
+; CHECK-NEXT:     REPLICATE ir<%gep.a> = getelementptr ir<@a>, ir<0>, ir<%mul>
 ; CHECK-NEXT:     REPLICATE store ir<%add>, ir<%gep.a>
 ; CHECK-NEXT:   Successor(s): pred.store.continue
 
 ; CHECK:      pred.store.continue:
 ; CHECK-NEXT:   No successors
 ; CHECK-NEXT: }
 
 ; CHECK:       loop.1:
exit:
   ret void
 }
 
 ; CHECK-LABEL: LV: Checking a loop in "sink3"
 ; CHECK:      VPlan 'Initial VPlan for VF={2},UF>=1' {
 ; CHECK-NEXT: loop:
 ; CHECK-NEXT:   WIDEN-INDUCTION %indvars.iv = phi 0, %indvars.iv.next
 ; CHECK-NEXT:   EMIT vp<%2> = icmp ule ir<%indvars.iv> vp<%0>
-; CHECK-NEXT:   REPLICATE ir<%gep.b> = getelementptr ir<@b>, ir<0>, ir<%indvars.iv>
 ; CHECK-NEXT: Successor(s): pred.load
 
 ; CHECK:      <xVFxUF> pred.load: {
 ; CHECK-NEXT:   pred.load.entry:
 ; CHECK-NEXT:     BRANCH-ON-MASK vp<%2>
 ; CHECK-NEXT:   Successor(s): pred.load.if, pred.load.continue
 ; CHECK-NEXT:   CondBit: vp<%2> (loop)
 
 ; CHECK:       pred.load.if:
+; CHECK-NEXT:     REPLICATE ir<%gep.b> = getelementptr ir<@b>, ir<0>, ir<%indvars.iv>
 ; CHECK-NEXT:     REPLICATE ir<%lv.b> = load ir<%gep.b> (S->V)
 ; CHECK-NEXT:   Successor(s): pred.load.continue
 
 ; CHECK:       pred.load.continue:
 ; CHECK-NEXT:     PHI-PREDICATED-INSTRUCTION vp<%5> = ir<%lv.b>
 ; CHECK-NEXT:   No successors
 ; CHECK-NEXT: }
 
 ; CHECK:      loop.0:
 ; CHECK-NEXT:   WIDEN ir<%add> = add vp<%5>, ir<10>
 ; CHECK-NEXT:   WIDEN ir<%mul> = mul ir<%indvars.iv>, ir<%add>
-; CHECK-NEXT:   REPLICATE ir<%gep.a> = getelementptr ir<@a>, ir<0>, ir<%mul>
 ; CHECK-NEXT: Successor(s): pred.store
 
 ; CHECK:      <xVFxUF> pred.store: {
 ; CHECK-NEXT:   pred.store.entry:
 ; CHECK-NEXT:     BRANCH-ON-MASK vp<%2>
 ; CHECK-NEXT:   Successor(s): pred.store.if, pred.store.continue
 ; CHECK-NEXT:   CondBit: vp<%2> (loop)
 
 ; CHECK:      pred.store.if:
+; CHECK-NEXT:     REPLICATE ir<%gep.a> = getelementptr ir<@a>, ir<0>, ir<%mul>
 ; CHECK-NEXT:     REPLICATE store ir<%add>, ir<%gep.a>
 ; CHECK-NEXT:   Successor(s): pred.store.continue
 
 ; CHECK:      pred.store.continue:
 ; CHECK-NEXT:   No successors
 ; CHECK-NEXT: }
 
 ; CHECK:      loop.1: