[VPlan] Clone original VPlan and specialize for each VF (WIP).

[a.elovikov]

I didn't recognize that it's still WIP until some point, so some nitpicking comments aren't very useful probably...

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

281

Are we somehow limited that the argument must be an OriginalPlan or can it be some Plan? Specifically, what if I want to try some optimization on already cloned VPlan such that I'm not sure if it's profitable or not, so I want to create a clone of the Plan instead of transforming in place. Would I be able to use that clone method?

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8738

Why don't we use cast similar to line 8721? It's also not clear why we have early continue above, but it might actually have the same answer.

8746

nit: I'd move it out of the loop.

8780

That's mostly copy of the lambda above. Can we unify them somehow?

8888

I think it deserves a dedicated comment, especially because it's surprising to see new recipes created inside the block of code starting with the comment "Remove dead instrutions."

I think that it would be beneficial to address this even in the WIP stage of the patch and not during the final polishing.

llvm/lib/Transforms/Vectorize/VPlan.h

585

Missed in the copy-paste?

[fhahn]

Rebased and simplified.

[fhahn]

Putting this on hold for now, to first focus on sinking scalar operands as VPlan-to-VPlan transform: D100258

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

public:
 
   /// Test a \p Predicate on a \p Range of VF's. Return the value of applying
   /// \p Predicate on Range.Start, possibly decreasing Range.End such that the
   /// returned value holds for the entire \p Range.
   static bool
   getDecisionAndClampRange(const std::function<bool(ElementCount)> &Predicate,
                            VFRange &Range);
 
+  VPlanPtr clone(VPlan &OriginalPlan);
+
 protected:
   /// Collect the instructions from the original loop that would be trivially
   /// dead in the vectorized loop if generated.
   void collectTriviallyDeadInstructions(
       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

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

LLVM_DEBUG(dbgs() << "LV: Using " << (UserVFIsLegal ? "user" : "max")
                       << " VF " << VF << ".\n");
     assert(isPowerOf2_32(VF.getKnownMinValue()) &&
            "VF needs to be a power of two");
     // Collect the instructions (and their associated costs) that will be more
     // profitable to scalarize.
     CM.selectUserVectorizationFactor(VF);
     CM.collectInLoopReductions();
     auto InitialPlan = buildVPlan({VF, VF});
-    buildVPlansWithVPRecipes(VF, VF, *InitialPlan);
+    VPlanPredicator Pred(*InitialPlan);
+    Pred.predicate();
+    buildVPlansWithVPRecipes(UserVF, UserVF, *InitialPlan);
     LLVM_DEBUG(printPlans(dbgs()));
     return {{VF, 0}};
   }
 
   assert(!MaxVF.isScalable() &&
          "Scalable vectors not yet supported beyond this point");
 
   for (ElementCount VF = ElementCount::getFixed(1);
        ElementCount::isKnownLE(VF, MaxVF); VF *= 2) {
     // Collect Uniform and Scalar instructions after vectorization with VF.
     CM.collectUniformsAndScalars(VF);
 
     // Collect the instructions (and their associated costs) that will be more
     // profitable to scalarize.
     if (VF.isVector())
       CM.collectInstsToScalarize(VF);
   }
 
   CM.collectInLoopReductions();
 
   auto InitialPlan = buildVPlan({ElementCount::getFixed(1), MaxVF});
+  VPlanPredicator Pred(*InitialPlan);
+  Pred.predicate();
   buildVPlansWithVPRecipes(ElementCount::getFixed(1), MaxVF, *InitialPlan);
   LLVM_DEBUG(printPlans(dbgs()));
   if (MaxVF.isScalar())
     return VectorizationFactor::Disabled();
 
   // Select the optimal vectorization factor.
   return CM.selectVectorizationFactor(MaxVF);
 }
VPValue *VPRecipeBuilder::createBlockInMask(BasicBlock *BB, VPlanPtr &Plan) {
   // All-one mask is modelled as no-mask following the convention for masked
   // load/store/gather/scatter. Initialize BlockMask to no-mask.
   VPValue *BlockMask = nullptr;
 
   if (OrigLoop->getHeader() == BB) {
     if (!CM.blockNeedsPredication(BB))
       return BlockMaskCache[BB] = BlockMask; // Loop incoming mask is all-one.
 
-    // Create the block in mask as the first non-phi instruction in the block.
     VPBuilder::InsertPointGuard Guard(Builder);
     auto NewInsertionPoint = Builder.getInsertBlock()->getFirstNonPhi();
     Builder.setInsertPoint(Builder.getInsertBlock(), NewInsertionPoint);
 
     // Introduce the early-exit compare IV <= BTC to form header block mask.
     // This is used instead of IV < TC because TC may wrap, unlike BTC.
     // Start by constructing the desired canonical IV.
     VPValue *IV = nullptr;
     if (Legal->getPrimaryInduction())
       IV = Plan->getOrAddVPValue(Legal->getPrimaryInduction());
     else {
       auto IVRecipe = new VPWidenCanonicalIVRecipe();
-      Builder.getInsertBlock()->insert(IVRecipe, NewInsertionPoint);
+      IVRecipe->insertBefore(&*Builder.getInsertBlock()->begin());
       IV = IVRecipe->getVPValue();
     }
     VPValue *BTC = Plan->getOrCreateBackedgeTakenCount();
     bool TailFolded = !CM.isScalarEpilogueAllowed();
 
     if (TailFolded && CM.TTI.emitGetActiveLaneMask()) {
       // While ActiveLaneMask is a binary op that consumes the loop tripcount
       // as a second argument, we only pass the IV here and extract the
VPWidenRecipe *VPRecipeBuilder::tryToWiden(Instruction *I, VPlan &Plan) const {
 
   if (!IsVectorizableOpcode(I->getOpcode()))
     return nullptr;
 
   // Success: widen this instruction.
   return new VPWidenRecipe(*I, Plan.mapToVPValues(I->operands()));
 }
 
-VPBasicBlock *VPRecipeBuilder::handleReplication(
+std::pair<VPBasicBlock *, VPReplicateRecipe *>
+VPRecipeBuilder::handleReplication(
     Instruction *I, VFRange &Range, VPBasicBlock *VPBB,
     DenseMap<Instruction *, VPReplicateRecipe *> &PredInst2Recipe,
     VPlanPtr &Plan) {
   bool IsUniform = LoopVectorizationPlanner::getDecisionAndClampRange(
       [&](ElementCount VF) { return CM.isUniformAfterVectorization(I, VF); },
       Range);
 
   bool IsPredicated = LoopVectorizationPlanner::getDecisionAndClampRange(
       [&](ElementCount VF) { return CM.isScalarWithPredication(I, VF); },
       Range);
 
   auto *Recipe = new VPReplicateRecipe(I, Plan->mapToVPValues(I->operands()),
                                        IsUniform, IsPredicated);
   setRecipe(I, Recipe);
+  Plan->getVPValue(I)->replaceAllUsesWith(Recipe);
+  Plan->removeVPValueFor(I);
   Plan->addVPValue(I, Recipe);
 
   // Find if I uses a predicated instruction. If so, it will use its scalar
   // value. Avoid hoisting the insert-element which packs the scalar value into
   // a vector value, as that happens iff all users use the vector value.
   for (auto &Op : I->operands())
     if (auto *PredInst = dyn_cast<Instruction>(Op))
       if (PredInst2Recipe.find(PredInst) != PredInst2Recipe.end())
         PredInst2Recipe[PredInst]->setAlsoPack(false);
 
   // Finalize the recipe for Instr, first if it is not predicated.
   if (!IsPredicated) {
     LLVM_DEBUG(dbgs() << "LV: Scalarizing:" << *I << "\n");
-    VPBB->appendRecipe(Recipe);
-    return VPBB;
+    return {VPBB, Recipe};
   }
   LLVM_DEBUG(dbgs() << "LV: Scalarizing and predicating:" << *I << "\n");
-  assert(VPBB->getSuccessors().empty() &&
-         "VPBB has successors when handling predicated replication.");
+  // FIXME
+  SmallVector<VPBlockBase *, 4> Succs(VPBB->getSuccessors().begin(),
+                                      VPBB->getSuccessors().end());
+  for (auto *Succ : VPBB->getSuccessors())
+    VPBlockUtils::disconnectBlocks(VPBB, Succ);
+  // assert(VPBB->getSuccessors().empty() &&
+  //"VPBB has successors when handling predicated replication.");
   // Record predicated instructions for above packing optimizations.
   PredInst2Recipe[I] = Recipe;
   VPBlockBase *Region = createReplicateRegion(I, Recipe, Plan);
   VPBlockUtils::insertBlockAfter(Region, VPBB);
   auto *RegSucc = new VPBasicBlock();
   VPBlockUtils::insertBlockAfter(RegSucc, Region);
-  return RegSucc;
+  for (auto *Succ : Succs)
+    VPBlockUtils::connectBlocks(RegSucc, Succ);
+
+  return {RegSucc, Recipe};
 }
 
 VPRegionBlock *VPRecipeBuilder::createReplicateRegion(Instruction *Instr,
                                                       VPRecipeBase *PredRecipe,
                                                       VPlanPtr &Plan) {
   // Instructions marked for predication are replicated and placed under an
   // if-then construct to prevent side-effects.
 
bool InvariantCond =
         PSE.getSE()->isLoopInvariant(PSE.getSCEV(SI->getOperand(0)), OrigLoop);
     return toVPRecipeResult(new VPWidenSelectRecipe(
         *SI, Plan->mapToVPValues(SI->operands()), InvariantCond));
   }
 
   return toVPRecipeResult(tryToWiden(Instr, *Plan));
 }
 
+VPlanPtr LoopVectorizationPlanner::clone(VPlan &OriginalPlan) {
+  ReversePostOrderTraversal<VPBlockBase *> RPOT(
+      OriginalPlan.getEntry()->getEntryBasicBlock());
+
+  auto Plan = std::make_unique<VPlan>();
+  DenseMap<VPValue *, VPValue *> Old2New;
+  DenseMap<VPBlockBase *, VPBlockBase *> Old2NewBlocks;
+  for (VPBlockBase *Base : RPOT) {
+    assert(isa<VPBasicBlock>(Base));
+    Old2NewBlocks[Base] = new VPBasicBlock(Base->getName());
+  }
+
+  Plan->setEntry(Old2NewBlocks[OriginalPlan.getEntry()]);
+  for (VPBlockBase *Base : RPOT) {
+    for (auto *Succ : Base->getSuccessors()) {
+      VPBlockUtils::connectBlocks(Old2NewBlocks[Base], Old2NewBlocks[Succ]);
+    }
+  }
+
+  SmallVector<VPInstruction *, 4> OldPhisToFix;
+  SmallVector<VPUser *, 4> RemapAfter;
+  for (VPBlockBase *Base : RPOT) {
+    if (Base->getNumPredecessors() == 0 || Base->getNumSuccessors() == 0)
+      continue;
+
+    VPBasicBlock *OriginalVPBB = Base->getEntryBasicBlock();
+    VPBasicBlock *VPBB = cast<VPBasicBlock>(Old2NewBlocks[OriginalVPBB]);
+
+    // Relevant instructions from basic block BB will be grouped into VPRecipe
+    // ingredients and fill a new VPBasicBlock.
+    // Introduce each ingredient into VPlan.
+    for (auto I = OriginalVPBB->begin(), E = OriginalVPBB->end(); I != E;) {
+      VPRecipeBase *Ingredient = &*I++;
+      auto RemapOperands = [&Old2New, &RemapAfter, &Plan](VPRecipeBase *U) {
+        if (isa<VPWidenPHIRecipe>(U)) {
+          RemapAfter.push_back(U);
+          return;
+        }
+
+        for (unsigned I = 0, E = U->getNumOperands(); I != E; ++I) {
+          VPValue *OldOp = U->getOperand(I);
+          VPValue *NewOp = nullptr;
+          if (OldOp->getDef()) {
+            NewOp = Old2New[OldOp];
+            assert(NewOp && "trying to map operand that was not defined");
+          } else {
+            NewOp = Plan->getOrAddVPValue(OldOp->getLiveInIRValue());
+          }
+          U->setOperand(I, NewOp);
+        }
+      };
+
+      VPRecipeBase *NewI = Ingredient->clone();
+      RemapOperands(NewI);
+      for (unsigned I = 0, E = NewI->getNumDefinedValues(); I != E; ++I) {
+        VPValue *NewDef = NewI->getVPValue(I);
+        Old2New[Ingredient->getVPValue(I)] = NewDef;
+        if (NewDef)
+          Plan->addVPValue(NewDef->getUnderlyingValue(), NewDef);
+      }
+
+      VPBB->appendRecipe(NewI);
+    }
+  }
+
+  for (VPUser *U : RemapAfter) {
+    for (unsigned I = 0, E = U->getNumOperands(); I != E; ++I) {
+      VPValue *OldOp = U->getOperand(I);
+      VPValue *NewOp = nullptr;
+      if (OldOp->getDef()) {
+        NewOp = Old2New[OldOp];
+        assert(NewOp && "trying to map operand that was not defined");
+      } else {
+        NewOp = Plan->getOrAddVPValue(OldOp->getLiveInIRValue());
+      }
+      U->setOperand(I, NewOp);
+    }
+  }
+
+  return Plan;
+}
+
 void LoopVectorizationPlanner::buildVPlansWithVPRecipes(ElementCount MinVF,
                                                         ElementCount MaxVF,
                                                         VPlan &OriginalPlan) {
   assert(OrigLoop->isInnermost() && "Inner loop expected.");
 
 
 
   // Remove the loop exit block and pre-header/entry block, to simplify the code dealing with VPlans for inner loops, as those blocks are not needed at the moment.
void LoopVectorizationPlanner::buildVPlansWithVPRecipes(ElementCount MinVF,
 
   DenseMap<Instruction *, VPInstruction *> Inst2VPInst;
   for (auto &Entry : SinkAfter) {
     Inst2VPInst[Entry.first] = nullptr;
     Inst2VPInst[Entry.second] = nullptr;
   }
 
   VPRecipeBuilder RecipeBuilder(OrigLoop, TLI, Legal, CM, PSE, Builder);
-
+  SmallVector<VPRecipeBase *, 4> ToRemove;
   auto *DummyVal = new VPValue();
   OriginalPlan.addExternalDef(DummyVal);
   for (VPBlockBase *Base : RPOT) {
     VPBasicBlock *OriginalVPBB = Base->getEntryBasicBlock();
 
     // First, convert some VPInstructions to recipes, if the conversion does not
     // depend on the VF. At the moment, only VPIntOrFpInductionRecipes are
     // created here.
for (auto I = OriginalVPBB->begin(), E = OriginalVPBB->end(); I != E;) {
         VPhi->eraseFromParent();
       }
     }
 
     // Remove dead instructions.
     for (auto I = OriginalVPBB->rbegin(), E = OriginalVPBB->rend(); I != E;) {
       VPRecipeBase *Ingredient = &*I++;
       VPInstruction *VPInst = dyn_cast<VPInstruction>(Ingredient);
-      if (!VPInst)
+      if (!VPInst || !VPInst->getUnderlyingValue())
         continue;
       Instruction *Instr = VPInst->getUnderlyingInstr();
 
       if (DeadInstructions.contains(Instr) || isa<DbgInfoIntrinsic>(Instr)) {
+        for (VPUser *U :
+             make_early_inc_range(Ingredient->getVPValue()->users())) {
+          VPRecipeBase *R = cast<VPRecipeBase>(U);
+          if (auto *VPhi = dyn_cast<VPWidenPHIRecipe>(R)) {
+            auto *NewP =
+                new VPWidenPHIRecipe(cast<PHINode>(VPhi->getUnderlyingValue()));
+            if (VPhi->getStartValue())
+              NewP->addOperand(VPhi->getStartValue());
+            NewP->insertBefore(VPhi);
+            VPhi->getVPValue()->replaceAllUsesWith(NewP);
+            ToRemove.push_back(VPhi);
+          }
+        }
         Ingredient->getVPValue()->replaceAllUsesWith(DummyVal);
         Ingredient->eraseFromParent();
         continue;
       }
 
       auto Iter = Inst2VPInst.find(Instr);
       if (Iter != Inst2VPInst.end())
         Iter->second = VPInst;
     }
   }
 
+  for (auto *R : ToRemove)
+    R->eraseFromParent();
+
   for (auto &Entry : SinkAfter) {
     VPRecipeBase *Sink = Inst2VPInst.find(Entry.first)->second;
     VPRecipeBase *Target = Inst2VPInst.find(Entry.second)->second;
     Sink->moveAfter(Target);
   }
 
   auto MaxVFPlusOne = MaxVF.getWithIncrement(1);
   for (ElementCount VF = MinVF; ElementCount::isKnownLT(VF, MaxVFPlusOne);) {
for (unsigned i = 0; i < IG->getFactor(); i++)
         RecipeBuilder.recordRecipeOf(Member);
   };
 
   // ---------------------------------------------------------------------------
   // Build initial VPlan: Scan the body of the loop in a topological order to
   // visit each basic block after having visited its predecessor basic blocks.
   // ---------------------------------------------------------------------------
 
-  // Create a dummy pre-entry VPBasicBlock to start building the VPlan.
-  auto Plan = std::make_unique<VPlan>();
-
-  // 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);
-
+  auto Plan = clone(OriginalPlan);
   ReversePostOrderTraversal<VPBlockBase *> RPOT(
-      OriginalPlan.getEntry()->getEntryBasicBlock());
+      Plan->getEntry()->getEntryBasicBlock());
 
+  bool NeedAppend = false;
   VPBasicBlock *VPBB = nullptr;
   for (VPBlockBase *Base : RPOT) {
-    VPBasicBlock *OriginalVPBB = Base->getEntryBasicBlock();
 
     // Relevant instructions from basic block BB will be grouped into VPRecipe
     // ingredients and fill a new VPBasicBlock.
     unsigned VPBBsForBB = 0;
-    auto *FirstVPBBForBB = new VPBasicBlock(OriginalVPBB->getName());
-    if (VPBB)
-      VPBlockUtils::insertBlockAfter(FirstVPBBForBB, VPBB);
-    else
-      Plan->setEntry(FirstVPBBForBB);
-    VPBB = FirstVPBBForBB;
+    VPBB = cast<VPBasicBlock>(Base);
     Builder.setInsertPoint(VPBB);
 
-    // Introduce each ingredient into VPlan.
-    for (auto I = OriginalVPBB->begin(), E = OriginalVPBB->end(); I != E;) {
-      VPRecipeBase *Ingredient = &*I++;
-      if (isa<VPWidenIntOrFpInductionRecipe>(Ingredient)) {
-        auto *C = Ingredient->clone();
-        for (auto *Def : C->definedValues()) {
-          auto *UV = Def->getUnderlyingValue();
-          Plan->addVPValue(UV, Def);
-        }
-        for (unsigned I = 0, E = Ingredient->getNumOperands(); I != E; ++I)
-          C->setOperand(I, Plan->getOrAddVPValue(
-                               Ingredient->getOperand(I)->getLiveInIRValue()));
-        VPBB->appendRecipe(C);
+    auto ReplaceAllUsesWith = [&Plan](VPDef *Def) {
+      for (auto *V : Def->definedValues()) {
+        auto *UV = V->getUnderlyingValue();
+        if (!Plan->hasVPValue(UV)) {
+          Plan->addVPValue(UV, V);
           continue;
         }
-      VPInstruction *VPInst = dyn_cast<VPInstruction>(Ingredient);
-      Instruction *Instr =
-          VPInst
-              ? VPInst->getUnderlyingInstr()
-              : cast<PHINode>(
-                    cast<VPWidenPHIRecipe>(Ingredient)->getUnderlyingInstr());
 
-      // First filter out irrelevant instructions, to ensure no recipes are
-      // built for them.
-      if (isa<BranchInst>(Instr))
+        Plan->getVPValue(UV)->replaceAllUsesWith(V);
+        Plan->removeVPValueFor(UV);
+        Plan->addVPValue(UV, V);
+      }
+    };
+    auto FirstNonPhi = VPBB->getFirstNonPhi();
+    auto I = VPBB->begin(), E = VPBB->end();
+    while (I != E && (isa<VPWidenIntOrFpInductionRecipe>(*I) ||
+                      isa<VPWidenPHIRecipe>(*I))) {
+      VPRecipeBase *Ingredient = &*I++;
+      if (isa<VPWidenIntOrFpInductionRecipe>(Ingredient))
         continue;
-
-      if (auto RecipeOrValue =
-              RecipeBuilder.tryToCreateWidenRecipe(Instr, Range, Plan)) {
-        // If Instr can be simplified to an existing VPValue, use it.
-        if (RecipeOrValue.is<VPValue *>()) {
-          Plan->addVPValue(Instr, RecipeOrValue.get<VPValue *>());
-          continue;
-        }
-        // Otherwise, add the new recipe.
-        VPRecipeBase *Recipe = RecipeOrValue.get<VPRecipeBase *>();
-        for (auto *Def : Recipe->definedValues()) {
-          auto *UV = Def->getUnderlyingValue();
-          Plan->addVPValue(UV, Def);
-        }
+      PHINode *Phi = cast<PHINode>(
+          cast<VPWidenPHIRecipe>(Ingredient)->getUnderlyingInstr());
+      Builder.setInsertPoint(Ingredient->getParent(), FirstNonPhi);
+      auto RecipeOrValue =
+          RecipeBuilder.tryToCreateWidenRecipe(Phi, Range, Plan);
+        Ingredient->getVPValue()->replaceAllUsesWith(
+            RecipeOrValue.get<VPValue *>());
+        Plan->removeVPValueFor(Phi);
+        Plan->addVPValue(Phi, RecipeOrValue.get<VPValue *>());
+        Ingredient->eraseFromParent();
+      RecipeBuilder.setRecipe(Phi, Recipe);
+      if (isa<VPBlendRecipe>(Recipe))
+        VPBB->insert(Recipe, FirstNonPhi);
+      else
+        Recipe->insertBefore(Ingredient);
+
+      ReplaceAllUsesWith(Recipe);
+      Ingredient->eraseFromParent();
 
-        RecipeBuilder.setRecipe(Instr, Recipe);
-        VPBB->appendRecipe(Recipe);
+    // Introduce each ingredient into VPlan.
+    while (I != E) {
+      VPRecipeBase *Ingredient = &*I++;
+      VPInstruction *VPInst = dyn_cast<VPInstruction>(Ingredient);
+      if (!VPInst || !VPInst->getUnderlyingValue())
         continue;
-      }
+      Instruction *Instr = nullptr;
+      Instr = VPInst->getUnderlyingInstr();
+
+      assert(!isa<BranchInst>(Instr) &&
+             "Branch instruction must be removed earlier");
+
+      auto InsertPt = Ingredient->getIterator();
+      if (NeedAppend)
+        InsertPt = VPBB->end();
+      Builder.setInsertPoint(VPBB, InsertPt);
+      VPRecipeBase *Recipe = nullptr;
+      if (auto RecipeOrValue =
+              RecipeBuilder.tryToCreateWidenRecipe(Instr, Range, Plan)) {
+        // Add the new recipe.
+        Recipe = RecipeOrValue.get<VPRecipeBase *>();
+        RecipeBuilder.setRecipe(Instr, Recipe);
+        VPBB->insert(Recipe, InsertPt);
+      } else {
 
         // 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, PredInst2Recipe, Plan);
+        auto Res = RecipeBuilder.handleReplication(Instr, Range, VPBB,
+                                                   PredInst2Recipe, Plan);
+        Recipe = Res.second;
+        VPBasicBlock *NextVPBB = Res.first;
         if (NextVPBB != VPBB) {
           VPBB = NextVPBB;
-        VPBB->setName(OriginalVPBB->getName() + "." + Twine(VPBBsForBB++));
+          VPBB->setName(Base->getName() + "." + Twine(VPBBsForBB++));
+          NeedAppend = true;
+        } else {
+          VPBB->insert(Recipe, InsertPt);
+        }
       }
+
+      ReplaceAllUsesWith(Recipe);
+      Ingredient->eraseFromParent();
     }
   }
 
   // ---------------------------------------------------------------------------
   // Transform initial VPlan: Apply previously taken decisions, in order, to
   // bring the VPlan to its final state.
   // ---------------------------------------------------------------------------
 

llvm/lib/Transforms/Vectorize/VPRecipeBuilder.h

VPRegionBlock *createReplicateRegion(Instruction *I, VPRecipeBase *PredRecipe,
                                        VPlanPtr &Plan);
 
   /// Build a VPReplicationRecipe for \p I and enclose it within a Region if it
   /// is predicated. \return \p VPBB augmented with this new recipe if \p I is
   /// not predicated, otherwise \return a new VPBasicBlock that succeeds the new
   /// Region. Update the packing decision of predicated instructions if they
   /// feed \p I. Range.End may be decreased to ensure same recipe behavior from
   /// \p Range.Start to \p Range.End.
-  VPBasicBlock *handleReplication(
+  std::pair<VPBasicBlock *, VPReplicateRecipe *> handleReplication(
       Instruction *I, VFRange &Range, VPBasicBlock *VPBB,
       DenseMap<Instruction *, VPReplicateRecipe *> &PredInst2Recipe,
       VPlanPtr &Plan);
 };
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_VECTORIZE_VPRECIPEBUILDER_H

llvm/lib/Transforms/Vectorize/VPlan.h

public:
   }
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const VPDef *D) {
     // All VPDefs are also VPRecipeBases.
     return true;
   }
 
+  /// Method to support type inquiry through isa, cast, and dyn_cast.
+  static inline bool classof(const VPUser *D) {
+    // All VPDefs are also VPRecipeBases.
+    return true;
+  }
+
   /// Clone this recipe.
   virtual VPRecipeBase *clone() = 0;
 };
 
 inline bool VPUser::classof(const VPDef *Def) {
   return Def->getVPDefID() == VPRecipeBase::VPInstructionSC ||
          Def->getVPDefID() == VPRecipeBase::VPWidenSC ||
          Def->getVPDefID() == VPRecipeBase::VPWidenCallSC ||
private:
   OpcodeTy Opcode;
 
   /// Utility method serving execute(): generates a single instance of the
   /// modeled instruction.
   void generateInstruction(VPTransformState &State, unsigned Part);
 
 protected:
   void setUnderlyingInstr(Instruction *I) { setUnderlyingValue(I); }
-
 public:
   VPInstruction(unsigned Opcode, ArrayRef<VPValue *> Operands)
       : VPRecipeBase(VPRecipeBase::VPInstructionSC, Operands),
         VPValue(VPValue::VPVInstructionSC, nullptr, this), Opcode(Opcode) {}
 
   VPInstruction(unsigned Opcode, ArrayRef<VPInstruction *> Operands)
       : VPRecipeBase(VPRecipeBase::VPInstructionSC, {}),
         VPValue(VPValue::VPVInstructionSC, nullptr, this), Opcode(Opcode) {
public:
 
   VPValue *getOrAddVPValue(Value *V) {
     assert(V && "Trying to get or add the VPValue of a null Value");
     if (!Value2VPValue.count(V))
       addVPValue(V);
     return getVPValue(V);
   }
 
+  bool hasVPValue(Value *V) { return Value2VPValue.count(V); }
+
   void removeVPValueFor(Value *V) { Value2VPValue.erase(V); }
 
   /// Return the VPLoopInfo analysis for this VPlan.
   VPLoopInfo &getVPLoopInfo() { return VPLInfo; }
   const VPLoopInfo &getVPLoopInfo() const { return VPLInfo; }
 
   /// Dump the plan to stderr (for debugging).
   void dump() const;

llvm/lib/Transforms/Vectorize/VPlanPredicator.cpp

 
 // Generate all predicates needed for CurrBlock by going through its immediate
 // predecessor blocks.
 void VPlanPredicator::createOrPropagatePredicates(VPBlockBase *CurrBlock,
                                                   VPRegionBlock *Region) {
   // Blocks that dominate region exit inherit the predicate from the region.
   // Return after setting the predicate.
   if (VPDomTree.dominates(CurrBlock, Region->getExit())) {
-    VPValue *RegionBP = Region->getPredicate();
-    CurrBlock->setPredicate(RegionBP);
+    //    VPValue *RegionBP = Region->getPredicate();
+    // CurrBlock->setPredicate(RegionBP);
     return;
   }
 
   // Collect all incoming predicates in a worklist.
   std::list<VPValue *> IncomingPredicates;
 
   // Set the builder's insertion point to the top of the current BB
   VPBasicBlock *CurrBB = cast<VPBasicBlock>(CurrBlock->getEntryBasicBlock());
   Builder.setInsertPoint(CurrBB, CurrBB->begin());
 
   // For each predecessor, generate the VPInstructions required for
   // computing 'BP AND (not) CBV" at the top of CurrBB.
   // Collect the outcome of this calculation for all predecessors
   // into IncomingPredicates.
   for (VPBlockBase *PredBlock : CurrBlock->getPredecessors()) {
     // Skip back-edges
     if (VPBlockUtils::isBackEdge(PredBlock, CurrBlock, VPLI))
       continue;
+    continue;
 
     VPValue *IncomingPredicate = nullptr;
     unsigned NumPredSuccsNoBE =
         VPBlockUtils::countSuccessorsNoBE(PredBlock, VPLI);
 
     // If there is an unconditional branch to the currBB, then we don't create
     // edge predicates. We use the predecessor's block predicate instead.
     if (NumPredSuccsNoBE == 1)
       IncomingPredicate = PredBlock->getPredicate();
     else if (NumPredSuccsNoBE == 2) {
       // Emit recipes into CurrBlock if required
       assert(isa<VPBasicBlock>(PredBlock) && "Only BBs have multiple exits");
       IncomingPredicate =
           getOrCreateNotPredicate(cast<VPBasicBlock>(PredBlock), CurrBB);
     } else
       llvm_unreachable("FIXME: switch statement ?");
 
     if (IncomingPredicate)
       IncomingPredicates.push_back(IncomingPredicate);
   }
 
   // Logically OR all incoming predicates by building the Predicate Tree.
-  VPValue *Predicate = genPredicateTree(IncomingPredicates);
+  //  VPValue *Predicate = genPredicateTree(IncomingPredicates);
 
-  // Now update the block's predicate with the new one.
-  CurrBlock->setPredicate(Predicate);
+  //// Now update the block's predicate with the new one.
+  // CurrBlock->setPredicate(Predicate);
 }
 
 // Generate all predicates needed for Region.
 void VPlanPredicator::predicateRegionRec(VPRegionBlock *Region) {
   VPBasicBlock *EntryBlock = cast<VPBasicBlock>(Region->getEntry());
   ReversePostOrderTraversal<VPBlockBase *> RPOT(EntryBlock);
 
   // Generate edge predicates and append them to the block predicate. RPO is

 // This traversal is expensive. Since predication is not adding new
 // blocks, we should be able to compute RPOT once in predication and
 // reuse it here. This becomes even more important once we have nested
 // regions.
 void VPlanPredicator::linearizeRegionRec(VPRegionBlock *Region) {
   ReversePostOrderTraversal<VPBlockBase *> RPOT(Region->getEntry());
   VPBlockBase *PrevBlock = nullptr;
 
+  auto *Exit = Region->getExit();
   for (VPBlockBase *CurrBlock : RPOT) {
     // TODO: Handle nested regions once we start generating the same.
     assert(!isa<VPRegionBlock>(CurrBlock) && "Nested region not expected");
 
     // Linearize control flow by adding an unconditional edge between PrevBlock
     // and CurrBlock skipping loop headers and latches to keep intact loop
     // header predecessors and loop latch successors.
     if (PrevBlock && !VPLI->isLoopHeader(CurrBlock) &&
-        !VPBlockUtils::blockIsLoopLatch(PrevBlock, VPLI)) {
+        !VPBlockUtils::blockIsLoopLatch(PrevBlock, VPLI) && CurrBlock != Exit &&
+        PrevBlock != Exit) {
 
       LLVM_DEBUG(dbgs() << "Linearizing: " << PrevBlock->getName() << "->"
                         << CurrBlock->getName() << "\n");
 
+      SmallVector<VPBlockBase *, 2> Succs(PrevBlock->getSuccessors().begin(),
+                                          PrevBlock->getSuccessors().end());
+      for (auto *Succ : Succs) {
+        VPBlockUtils::disconnectBlocks(PrevBlock, Succ);
+      }
       PrevBlock->clearSuccessors();
       CurrBlock->clearPredecessors();
       VPBlockUtils::connectBlocks(PrevBlock, CurrBlock);
     }
 
     PrevBlock = CurrBlock;
   }
 }

llvm/lib/Transforms/Vectorize/VPlanValue.h

protected:
 
   // DESIGN PRINCIPLE: Access to the underlying IR must be strictly limited to
   // the front-end and back-end of VPlan so that the middle-end is as
   // independent as possible of the underlying IR. We grant access to the
   // underlying IR using friendship. In that way, we should be able to use VPlan
   // for multiple underlying IRs (Polly?) by providing a new VPlan front-end,
   // back-end and analysis information for the new IR.
 
+public:
   // Set \p Val as the underlying Value of this VPValue.
   void setUnderlyingValue(Value *Val) {
     assert(!UnderlyingVal && "Underlying Value is already set.");
     UnderlyingVal = Val;
   }
 
-public:
   /// Return the underlying Value attached to this VPValue.
   Value *getUnderlyingValue() { return UnderlyingVal; }
   const Value *getUnderlyingValue() const { return UnderlyingVal; }
 
   /// An enumeration for keeping track of the concrete subclass of VPValue that
   /// are actually instantiated. Values of this enumeration are kept in the
   /// SubclassID field of the VPValue objects. They are used for concrete
   /// type identification.

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

 ; CHECK:       vector.ph10:
 ; CHECK-NEXT:    [[N_RND_UP11:%.*]] = add nuw nsw i64 [[TMP19]], 4
 ; CHECK-NEXT:    [[N_VEC13:%.*]] = and i64 [[N_RND_UP11]], 8589934588
 ; CHECK-NEXT:    [[BROADCAST_SPLATINSERT20:%.*]] = insertelement <4 x i64> poison, i64 [[TMP19]], i32 0
 ; CHECK-NEXT:    [[BROADCAST_SPLAT21:%.*]] = shufflevector <4 x i64> [[BROADCAST_SPLATINSERT20]], <4 x i64> poison, <4 x i32> zeroinitializer
 ; CHECK-NEXT:    br label [[VECTOR_BODY9:%.*]]
 ; CHECK:       vector.body9:
 ; CHECK-NEXT:    [[INDEX14:%.*]] = phi i64 [ 0, [[VECTOR_PH10]] ], [ [[INDEX_NEXT15:%.*]], [[PRED_STORE_CONTINUE51:%.*]] ]
+; CHECK-NEXT:    [[BROADCAST_SPLATINSERT22:%.*]] = insertelement <4 x i64> poison, i64 [[INDEX14]], i32 0
+; CHECK-NEXT:    [[BROADCAST_SPLAT23:%.*]] = shufflevector <4 x i64> [[BROADCAST_SPLATINSERT22]], <4 x i64> poison, <4 x i32> zeroinitializer
+; CHECK-NEXT:    [[VEC_IV:%.*]] = or <4 x i64> [[BROADCAST_SPLAT23]], <i64 0, i64 1, i64 2, i64 3>
 ; CHECK-NEXT:    [[OFFSET_IDX:%.*]] = add i64 [[I_0_LCSSA]], [[INDEX14]]
 ; CHECK-NEXT:    [[TMP20:%.*]] = add i64 [[OFFSET_IDX]], 1
 ; CHECK-NEXT:    [[TMP21:%.*]] = add i64 [[OFFSET_IDX]], 2
 ; CHECK-NEXT:    [[TMP22:%.*]] = add i64 [[OFFSET_IDX]], 3
-; CHECK-NEXT:    [[BROADCAST_SPLATINSERT28:%.*]] = insertelement <4 x i64> poison, i64 [[INDEX14]], i32 0
-; CHECK-NEXT:    [[BROADCAST_SPLAT29:%.*]] = shufflevector <4 x i64> [[BROADCAST_SPLATINSERT28]], <4 x i64> poison, <4 x i32> zeroinitializer
-; CHECK-NEXT:    [[VEC_IV:%.*]] = or <4 x i64> [[BROADCAST_SPLAT29]], <i64 0, i64 1, i64 2, i64 3>
 ; CHECK-NEXT:    [[TMP23:%.*]] = icmp ule <4 x i64> [[VEC_IV]], [[BROADCAST_SPLAT21]]
 ; CHECK-NEXT:    [[TMP24:%.*]] = extractelement <4 x i1> [[TMP23]], i32 0
 ; CHECK-NEXT:    br i1 [[TMP24]], label [[PRED_LOAD_IF:%.*]], label [[PRED_LOAD_CONTINUE:%.*]]
 ; CHECK:       pred.load.if:
 ; CHECK-NEXT:    [[TMP25:%.*]] = getelementptr inbounds [2048 x i32], [2048 x i32]* @b, i64 0, i64 [[OFFSET_IDX]]
 ; CHECK-NEXT:    [[TMP26:%.*]] = load i32, i32* [[TMP25]], align 4
 ; CHECK-NEXT:    [[TMP27:%.*]] = insertelement <4 x i32> poison, i32 [[TMP26]], i32 0
 ; CHECK-NEXT:    br label [[PRED_LOAD_CONTINUE]]

 ; CHECK:       vector.ph:
 ; CHECK-NEXT:    [[N_RND_UP:%.*]] = add nuw nsw i64 [[TMP3]], 4
 ; CHECK-NEXT:    [[N_VEC:%.*]] = and i64 [[N_RND_UP]], 8589934588
 ; CHECK-NEXT:    [[BROADCAST_SPLATINSERT:%.*]] = insertelement <4 x i64> poison, i64 [[TMP3]], i32 0
 ; CHECK-NEXT:    [[BROADCAST_SPLAT:%.*]] = shufflevector <4 x i64> [[BROADCAST_SPLATINSERT]], <4 x i64> poison, <4 x i32> zeroinitializer
 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
 ; CHECK:       vector.body:
 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[PRED_STORE_CONTINUE27:%.*]] ]
-; CHECK-NEXT:    [[BROADCAST_SPLATINSERT14:%.*]] = insertelement <4 x i64> poison, i64 [[INDEX]], i32 0
-; CHECK-NEXT:    [[BROADCAST_SPLAT15:%.*]] = shufflevector <4 x i64> [[BROADCAST_SPLATINSERT14]], <4 x i64> poison, <4 x i32> zeroinitializer
-; CHECK-NEXT:    [[VEC_IV:%.*]] = or <4 x i64> [[BROADCAST_SPLAT15]], <i64 0, i64 1, i64 2, i64 3>
+; CHECK-NEXT:    [[BROADCAST_SPLATINSERT5:%.*]] = insertelement <4 x i64> poison, i64 [[INDEX]], i32 0
+; CHECK-NEXT:    [[BROADCAST_SPLAT6:%.*]] = shufflevector <4 x i64> [[BROADCAST_SPLATINSERT5]], <4 x i64> poison, <4 x i32> zeroinitializer
+; CHECK-NEXT:    [[VEC_IV:%.*]] = or <4 x i64> [[BROADCAST_SPLAT6]], <i64 0, i64 1, i64 2, i64 3>
 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp ule <4 x i64> [[VEC_IV]], [[BROADCAST_SPLAT]]
 ; CHECK-NEXT:    [[TMP5:%.*]] = extractelement <4 x i1> [[TMP4]], i32 0
 ; CHECK-NEXT:    br i1 [[TMP5]], label [[PRED_LOAD_IF:%.*]], label [[PRED_LOAD_CONTINUE:%.*]]
 ; CHECK:       pred.load.if:
-; CHECK-NEXT:    [[NEXT_GEP10:%.*]] = getelementptr i32, i32* [[Q:%.*]], i64 [[INDEX]]
-; CHECK-NEXT:    [[TMP6:%.*]] = load i32, i32* [[NEXT_GEP10]], align 16
+; CHECK-NEXT:    [[NEXT_GEP12:%.*]] = getelementptr i32, i32* [[Q:%.*]], i64 [[INDEX]]
+; CHECK-NEXT:    [[TMP6:%.*]] = load i32, i32* [[NEXT_GEP12]], align 16
 ; CHECK-NEXT:    br label [[PRED_LOAD_CONTINUE]]
 ; CHECK:       pred.load.continue:
 ; CHECK-NEXT:    [[TMP7:%.*]] = phi i32 [ poison, [[VECTOR_BODY]] ], [ [[TMP6]], [[PRED_LOAD_IF]] ]
 ; CHECK-NEXT:    [[TMP8:%.*]] = extractelement <4 x i1> [[TMP4]], i32 1
 ; CHECK-NEXT:    br i1 [[TMP8]], label [[PRED_LOAD_IF16:%.*]], label [[PRED_LOAD_CONTINUE17:%.*]]
 ; CHECK:       pred.load.if16:
 ; CHECK-NEXT:    [[TMP9:%.*]] = or i64 [[INDEX]], 1
-; CHECK-NEXT:    [[NEXT_GEP11:%.*]] = getelementptr i32, i32* [[Q]], i64 [[TMP9]]
-; CHECK-NEXT:    [[TMP10:%.*]] = load i32, i32* [[NEXT_GEP11]], align 16
+; CHECK-NEXT:    [[NEXT_GEP13:%.*]] = getelementptr i32, i32* [[Q]], i64 [[TMP9]]
+; CHECK-NEXT:    [[TMP10:%.*]] = load i32, i32* [[NEXT_GEP13]], align 16
 ; CHECK-NEXT:    br label [[PRED_LOAD_CONTINUE17]]
 ; CHECK:       pred.load.continue17:
 ; CHECK-NEXT:    [[TMP11:%.*]] = phi i32 [ poison, [[PRED_LOAD_CONTINUE]] ], [ [[TMP10]], [[PRED_LOAD_IF16]] ]
 ; CHECK-NEXT:    [[TMP12:%.*]] = extractelement <4 x i1> [[TMP4]], i32 2
 ; CHECK-NEXT:    br i1 [[TMP12]], label [[PRED_LOAD_IF18:%.*]], label [[PRED_LOAD_CONTINUE19:%.*]]
 ; CHECK:       pred.load.if18:
 ; CHECK-NEXT:    [[TMP13:%.*]] = or i64 [[INDEX]], 2
-; CHECK-NEXT:    [[NEXT_GEP12:%.*]] = getelementptr i32, i32* [[Q]], i64 [[TMP13]]
-; CHECK-NEXT:    [[TMP14:%.*]] = load i32, i32* [[NEXT_GEP12]], align 16
+; CHECK-NEXT:    [[NEXT_GEP14:%.*]] = getelementptr i32, i32* [[Q]], i64 [[TMP13]]
+; CHECK-NEXT:    [[TMP14:%.*]] = load i32, i32* [[NEXT_GEP14]], align 16
 ; CHECK-NEXT:    br label [[PRED_LOAD_CONTINUE19]]
 ; CHECK:       pred.load.continue19:
 ; CHECK-NEXT:    [[TMP15:%.*]] = phi i32 [ poison, [[PRED_LOAD_CONTINUE17]] ], [ [[TMP14]], [[PRED_LOAD_IF18]] ]
 ; CHECK-NEXT:    [[TMP16:%.*]] = extractelement <4 x i1> [[TMP4]], i32 3
 ; CHECK-NEXT:    br i1 [[TMP16]], label [[PRED_LOAD_IF20:%.*]], label [[PRED_LOAD_CONTINUE21:%.*]]
 ; CHECK:       pred.load.if20:
 ; CHECK-NEXT:    [[TMP17:%.*]] = or i64 [[INDEX]], 3
-; CHECK-NEXT:    [[NEXT_GEP13:%.*]] = getelementptr i32, i32* [[Q]], i64 [[TMP17]]
-; CHECK-NEXT:    [[TMP18:%.*]] = load i32, i32* [[NEXT_GEP13]], align 16
+; CHECK-NEXT:    [[NEXT_GEP15:%.*]] = getelementptr i32, i32* [[Q]], i64 [[TMP17]]
+; CHECK-NEXT:    [[TMP18:%.*]] = load i32, i32* [[NEXT_GEP15]], align 16
 ; CHECK-NEXT:    br label [[PRED_LOAD_CONTINUE21]]
 ; CHECK:       pred.load.continue21:
 ; CHECK-NEXT:    [[TMP19:%.*]] = phi i32 [ poison, [[PRED_LOAD_CONTINUE19]] ], [ [[TMP18]], [[PRED_LOAD_IF20]] ]
 ; CHECK-NEXT:    [[TMP20:%.*]] = extractelement <4 x i1> [[TMP4]], i32 0
 ; CHECK-NEXT:    br i1 [[TMP20]], label [[PRED_STORE_IF:%.*]], label [[PRED_STORE_CONTINUE:%.*]]
 ; CHECK:       pred.store.if:
 ; CHECK-NEXT:    [[NEXT_GEP:%.*]] = getelementptr i32, i32* [[P:%.*]], i64 [[INDEX]]
 ; CHECK-NEXT:    store i32 [[TMP7]], i32* [[NEXT_GEP]], align 16
 ; CHECK-NEXT:    br label [[PRED_STORE_CONTINUE]]
 ; CHECK:       pred.store.continue:
 ; CHECK-NEXT:    [[TMP21:%.*]] = extractelement <4 x i1> [[TMP4]], i32 1
 ; CHECK-NEXT:    br i1 [[TMP21]], label [[PRED_STORE_IF22:%.*]], label [[PRED_STORE_CONTINUE23:%.*]]
 ; CHECK:       pred.store.if22:
 ; CHECK-NEXT:    [[TMP22:%.*]] = or i64 [[INDEX]], 1
-; CHECK-NEXT:    [[NEXT_GEP7:%.*]] = getelementptr i32, i32* [[P]], i64 [[TMP22]]
-; CHECK-NEXT:    store i32 [[TMP11]], i32* [[NEXT_GEP7]], align 16
+; CHECK-NEXT:    [[NEXT_GEP9:%.*]] = getelementptr i32, i32* [[P]], i64 [[TMP22]]
+; CHECK-NEXT:    store i32 [[TMP11]], i32* [[NEXT_GEP9]], align 16
 ; CHECK-NEXT:    br label [[PRED_STORE_CONTINUE23]]
 ; CHECK:       pred.store.continue23:
 ; CHECK-NEXT:    [[TMP23:%.*]] = extractelement <4 x i1> [[TMP4]], i32 2
 ; CHECK-NEXT:    br i1 [[TMP23]], label [[PRED_STORE_IF24:%.*]], label [[PRED_STORE_CONTINUE25:%.*]]
 ; CHECK:       pred.store.if24:
 ; CHECK-NEXT:    [[TMP24:%.*]] = or i64 [[INDEX]], 2
-; CHECK-NEXT:    [[NEXT_GEP8:%.*]] = getelementptr i32, i32* [[P]], i64 [[TMP24]]
-; CHECK-NEXT:    store i32 [[TMP15]], i32* [[NEXT_GEP8]], align 16
+; CHECK-NEXT:    [[NEXT_GEP10:%.*]] = getelementptr i32, i32* [[P]], i64 [[TMP24]]
+; CHECK-NEXT:    store i32 [[TMP15]], i32* [[NEXT_GEP10]], align 16
 ; CHECK-NEXT:    br label [[PRED_STORE_CONTINUE25]]
 ; CHECK:       pred.store.continue25:
 ; CHECK-NEXT:    [[TMP25:%.*]] = extractelement <4 x i1> [[TMP4]], i32 3
 ; CHECK-NEXT:    br i1 [[TMP25]], label [[PRED_STORE_IF26:%.*]], label [[PRED_STORE_CONTINUE27]]
 ; CHECK:       pred.store.if26:
 ; CHECK-NEXT:    [[TMP26:%.*]] = or i64 [[INDEX]], 3
-; CHECK-NEXT:    [[NEXT_GEP9:%.*]] = getelementptr i32, i32* [[P]], i64 [[TMP26]]
-; CHECK-NEXT:    store i32 [[TMP19]], i32* [[NEXT_GEP9]], align 16
+; CHECK-NEXT:    [[NEXT_GEP11:%.*]] = getelementptr i32, i32* [[P]], i64 [[TMP26]]
+; CHECK-NEXT:    store i32 [[TMP19]], i32* [[NEXT_GEP11]], align 16
 ; CHECK-NEXT:    br label [[PRED_STORE_CONTINUE27]]
 ; CHECK:       pred.store.continue27:
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add i64 [[INDEX]], 4
 ; CHECK-NEXT:    [[TMP27:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
 ; CHECK-NEXT:    br i1 [[TMP27]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], [[LOOP8:!llvm.loop !.*]]
 ; CHECK:       middle.block:
 ; CHECK-NEXT:    br i1 true, label [[DOT_CRIT_EDGE_LOOPEXIT:%.*]], label [[SCALAR_PH]]
 ; CHECK:       scalar.ph:

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

 ; CHECK-NEXT:    [[TRIP_COUNT_MINUS_1:%.*]] = add nsw i32 [[TMP1]], -1
 ; CHECK-NEXT:    [[BROADCAST_SPLATINSERT:%.*]] = insertelement <4 x i32> poison, i32 [[TRIP_COUNT_MINUS_1]], i32 0
 ; CHECK-NEXT:    [[BROADCAST_SPLAT:%.*]] = shufflevector <4 x i32> [[BROADCAST_SPLATINSERT]], <4 x i32> poison, <4 x i32> zeroinitializer
 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
 ; CHECK:       vector.body:
 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i32 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[PRED_UDIV_CONTINUE9:%.*]] ]
 ; CHECK-NEXT:    [[VECTOR_RECUR:%.*]] = phi <4 x i32> [ <i32 poison, i32 poison, i32 poison, i32 0>, [[VECTOR_PH]] ], [ [[TMP21:%.*]], [[PRED_UDIV_CONTINUE9]] ]
 ; CHECK-NEXT:    [[VEC_PHI1:%.*]] = phi <4 x i32> [ zeroinitializer, [[VECTOR_PH]] ], [ [[TMP23:%.*]], [[PRED_UDIV_CONTINUE9]] ]
-; CHECK-NEXT:    [[OFFSET_IDX:%.*]] = sub i32 [[Y]], [[INDEX]]
 ; CHECK-NEXT:    [[BROADCAST_SPLATINSERT2:%.*]] = insertelement <4 x i32> poison, i32 [[INDEX]], i32 0
 ; CHECK-NEXT:    [[BROADCAST_SPLAT3:%.*]] = shufflevector <4 x i32> [[BROADCAST_SPLATINSERT2]], <4 x i32> poison, <4 x i32> zeroinitializer
 ; CHECK-NEXT:    [[VEC_IV:%.*]] = or <4 x i32> [[BROADCAST_SPLAT3]], <i32 0, i32 1, i32 2, i32 3>
+; CHECK-NEXT:    [[OFFSET_IDX:%.*]] = sub i32 [[Y]], [[INDEX]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp ule <4 x i32> [[VEC_IV]], [[BROADCAST_SPLAT]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = extractelement <4 x i1> [[TMP2]], i32 0
 ; CHECK-NEXT:    br i1 [[TMP3]], label [[PRED_UDIV_IF:%.*]], label [[PRED_UDIV_CONTINUE:%.*]]
 ; CHECK:       pred.udiv.if:
 ; CHECK-NEXT:    [[TMP4:%.*]] = udiv i32 219220132, [[OFFSET_IDX]]
 ; CHECK-NEXT:    [[TMP5:%.*]] = insertelement <4 x i32> poison, i32 [[TMP4]], i32 0
 ; CHECK-NEXT:    br label [[PRED_UDIV_CONTINUE]]
 ; CHECK:       pred.udiv.continue:

llvm/test/Transforms/LoopVectorize/icmp-uniforms.ll

for.body:
   br i1 %cond, label %for.body, label %for.end
 
 for.end:
   %tmp4 = phi i32 [ %tmp3, %for.body ]
   ret i32 %tmp4
 }
 
 ; Check for crash exposed by D76992.
+; CHECK:       After buildPlainCFG
 ; CHECK:       N0 [label =
 ; CHECK-NEXT:    "loop:\n" +
 ; CHECK-NEXT:      "WIDEN-INDUCTION %iv = phi 0, %iv.next\l" +
 ; CHECK-NEXT:      "WIDEN ir<%cond0> = icmp ir<%iv>, ir<13>\l" +
 ; CHECK-NEXT:      "WIDEN-SELECT ir<%s> = select ir<%cond0>, ir<10>, ir<20>\l"
 ; CHECK-NEXT:  ]
 define void @test() {
 entry:

llvm/test/Transforms/LoopVectorize/pr46525-expander-insertpoint.ll

 ; CHECK-NEXT:    [[N_VEC:%.*]] = sub i64 [[N_RND_UP]], [[N_MOD_VF]]
 ; CHECK-NEXT:    [[IND_END:%.*]] = mul i64 [[N_VEC]], [[INC]]
 ; CHECK-NEXT:    [[TRIP_COUNT_MINUS_1:%.*]] = sub i64 [[TMP2]], 1
 ; CHECK-NEXT:    [[BROADCAST_SPLATINSERT:%.*]] = insertelement <2 x i64> poison, i64 [[TRIP_COUNT_MINUS_1]], i32 0
 ; CHECK-NEXT:    [[BROADCAST_SPLAT:%.*]] = shufflevector <2 x i64> [[BROADCAST_SPLATINSERT]], <2 x i64> poison, <2 x i32> zeroinitializer
 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
 ; CHECK:       vector.body:
 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[PRED_STORE_CONTINUE6:%.*]] ]
-; CHECK-NEXT:    [[OFFSET_IDX:%.*]] = mul i64 [[INDEX]], [[INC]]
-; CHECK-NEXT:    [[BROADCAST_SPLATINSERT1:%.*]] = insertelement <2 x i64> poison, i64 [[OFFSET_IDX]], i32 0
+; CHECK-NEXT:    [[BROADCAST_SPLATINSERT1:%.*]] = insertelement <2 x i64> poison, i64 [[INDEX]], i32 0
 ; CHECK-NEXT:    [[BROADCAST_SPLAT2:%.*]] = shufflevector <2 x i64> [[BROADCAST_SPLATINSERT1]], <2 x i64> poison, <2 x i32> zeroinitializer
+; CHECK-NEXT:    [[VEC_IV:%.*]] = add <2 x i64> [[BROADCAST_SPLAT2]], <i64 0, i64 1>
+; CHECK-NEXT:    [[OFFSET_IDX:%.*]] = mul i64 [[INDEX]], [[INC]]
+; CHECK-NEXT:    [[BROADCAST_SPLATINSERT3:%.*]] = insertelement <2 x i64> poison, i64 [[OFFSET_IDX]], i32 0
+; CHECK-NEXT:    [[BROADCAST_SPLAT4:%.*]] = shufflevector <2 x i64> [[BROADCAST_SPLATINSERT3]], <2 x i64> poison, <2 x i32> zeroinitializer
 ; CHECK-NEXT:    [[DOTSPLATINSERT:%.*]] = insertelement <2 x i64> poison, i64 [[INC]], i32 0
 ; CHECK-NEXT:    [[DOTSPLAT:%.*]] = shufflevector <2 x i64> [[DOTSPLATINSERT]], <2 x i64> poison, <2 x i32> zeroinitializer
 ; CHECK-NEXT:    [[TMP3:%.*]] = mul <2 x i64> <i64 0, i64 1>, [[DOTSPLAT]]
-; CHECK-NEXT:    [[INDUCTION:%.*]] = add <2 x i64> [[BROADCAST_SPLAT2]], [[TMP3]]
+; CHECK-NEXT:    [[INDUCTION:%.*]] = add <2 x i64> [[BROADCAST_SPLAT4]], [[TMP3]]
 ; CHECK-NEXT:    [[TMP4:%.*]] = mul i64 0, [[INC]]
 ; CHECK-NEXT:    [[TMP5:%.*]] = add i64 [[OFFSET_IDX]], [[TMP4]]
-; CHECK-NEXT:    [[BROADCAST_SPLATINSERT3:%.*]] = insertelement <2 x i64> poison, i64 [[INDEX]], i32 0
-; CHECK-NEXT:    [[BROADCAST_SPLAT4:%.*]] = shufflevector <2 x i64> [[BROADCAST_SPLATINSERT3]], <2 x i64> poison, <2 x i32> zeroinitializer
-; CHECK-NEXT:    [[VEC_IV:%.*]] = add <2 x i64> [[BROADCAST_SPLAT4]], <i64 0, i64 1>
 ; CHECK-NEXT:    [[TMP6:%.*]] = icmp ule <2 x i64> [[VEC_IV]], [[BROADCAST_SPLAT]]
 ; CHECK-NEXT:    [[TMP7:%.*]] = extractelement <2 x i1> [[TMP6]], i32 0
 ; CHECK-NEXT:    br i1 [[TMP7]], label [[PRED_STORE_IF:%.*]], label [[PRED_STORE_CONTINUE:%.*]]
 ; CHECK:       pred.store.if:
 ; CHECK-NEXT:    store i32 0, i32* [[PTR:%.*]], align 4
 ; CHECK-NEXT:    br label [[PRED_STORE_CONTINUE]]
 ; CHECK:       pred.store.continue:
 ; CHECK-NEXT:    [[TMP8:%.*]] = extractelement <2 x i1> [[TMP6]], i32 1

llvm/test/Transforms/LoopVectorize/select-reduction.ll

 ; CHECK-NEXT:    [[IND_END:%.*]] = sub i64 [[EXTRA_ITER]], [[N_VEC]]
 ; CHECK-NEXT:    [[TRIP_COUNT_MINUS_1:%.*]] = sub i64 [[EXTRA_ITER]], 1
 ; CHECK-NEXT:    [[BROADCAST_SPLATINSERT:%.*]] = insertelement <4 x i64> poison, i64 [[TRIP_COUNT_MINUS_1]], i32 0
 ; CHECK-NEXT:    [[BROADCAST_SPLAT:%.*]] = shufflevector <4 x i64> [[BROADCAST_SPLATINSERT]], <4 x i64> poison, <4 x i32> zeroinitializer
 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
 ; CHECK:       vector.body:
 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
 ; CHECK-NEXT:    [[VEC_PHI:%.*]] = phi <4 x i32> [ zeroinitializer, [[VECTOR_PH]] ], [ [[TMP3:%.*]], [[VECTOR_BODY]] ]
-; CHECK-NEXT:    [[OFFSET_IDX:%.*]] = sub i64 [[EXTRA_ITER]], [[INDEX]]
-; CHECK-NEXT:    [[BROADCAST_SPLATINSERT1:%.*]] = insertelement <4 x i64> poison, i64 [[OFFSET_IDX]], i32 0
+; CHECK-NEXT:    [[BROADCAST_SPLATINSERT1:%.*]] = insertelement <4 x i64> poison, i64 [[INDEX]], i32 0
 ; CHECK-NEXT:    [[BROADCAST_SPLAT2:%.*]] = shufflevector <4 x i64> [[BROADCAST_SPLATINSERT1]], <4 x i64> poison, <4 x i32> zeroinitializer
-; CHECK-NEXT:    [[INDUCTION:%.*]] = add <4 x i64> [[BROADCAST_SPLAT2]], <i64 0, i64 -1, i64 -2, i64 -3>
-; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[OFFSET_IDX]], 0
-; CHECK-NEXT:    [[BROADCAST_SPLATINSERT3:%.*]] = insertelement <4 x i64> poison, i64 [[INDEX]], i32 0
+; CHECK-NEXT:    [[VEC_IV:%.*]] = add <4 x i64> [[BROADCAST_SPLAT2]], <i64 0, i64 1, i64 2, i64 3>
+; CHECK-NEXT:    [[OFFSET_IDX:%.*]] = sub i64 [[EXTRA_ITER]], [[INDEX]]
+; CHECK-NEXT:    [[BROADCAST_SPLATINSERT3:%.*]] = insertelement <4 x i64> poison, i64 [[OFFSET_IDX]], i32 0
 ; CHECK-NEXT:    [[BROADCAST_SPLAT4:%.*]] = shufflevector <4 x i64> [[BROADCAST_SPLATINSERT3]], <4 x i64> poison, <4 x i32> zeroinitializer
-; CHECK-NEXT:    [[VEC_IV:%.*]] = add <4 x i64> [[BROADCAST_SPLAT4]], <i64 0, i64 1, i64 2, i64 3>
+; CHECK-NEXT:    [[INDUCTION:%.*]] = add <4 x i64> [[BROADCAST_SPLAT4]], <i64 0, i64 -1, i64 -2, i64 -3>
+; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[OFFSET_IDX]], 0
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp ule <4 x i64> [[VEC_IV]], [[BROADCAST_SPLAT]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt <4 x i32> [[VEC_PHI]], <i32 10, i32 10, i32 10, i32 10>
 ; CHECK-NEXT:    [[TMP3]] = select <4 x i1> [[TMP2]], <4 x i32> [[VEC_PHI]], <4 x i32> <i32 10, i32 10, i32 10, i32 10>
 ; CHECK-NEXT:    [[TMP4:%.*]] = select <4 x i1> [[TMP1]], <4 x i32> [[TMP3]], <4 x i32> [[VEC_PHI]]
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add i64 [[INDEX]], 4
 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
 ; CHECK-NEXT:    br i1 [[TMP5]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], [[LOOP0:!llvm.loop !.*]]
 ; CHECK:       middle.block: