[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

292

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

8823

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.

8831

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

8865

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

8967

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

687

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

#endif
 
   /// 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.
   auto SelectedVF = CM.selectVectorizationFactor(MaxVF);
 
VPWidenRecipe *VPRecipeBuilder::tryToWiden(Instruction *I,
 
   if (!IsVectorizableOpcode(I->getOpcode()))
     return nullptr;
 
   // Success: widen this instruction.
   return new VPWidenRecipe(*I, make_range(Operands.begin(), Operands.end()));
 }
 
-VPBasicBlock *VPRecipeBuilder::handleReplication(
-    Instruction *I, VFRange &Range, VPBasicBlock *VPBB,
-    VPlanPtr &Plan) {
+std::pair<VPBasicBlock *, VPRecipeBase *>
+VPRecipeBuilder::handleReplication(Instruction *I, VFRange &Range,
+                                   VPBasicBlock *VPBB, 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);
+  VPRecipeBase *Recipe = new VPReplicateRecipe(
+      I, Plan->mapToVPValues(I->operands()), IsUniform, IsPredicated);
   setRecipe(I, Recipe);
-  Plan->addVPValue(I, Recipe);
+  Plan->getVPValue(I)->replaceAllUsesWith(Recipe->getVPValue(0));
+  Plan->removeVPValueFor(I);
+  Plan->addVPValue(I, Recipe->getVPValue(0));
 
   // 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 (VPValue *Op : Recipe->operands()) {
     auto *PredR = dyn_cast_or_null<VPPredInstPHIRecipe>(Op->getDef());
     if (!PredR)
       continue;
     auto *RepR =
         cast_or_null<VPReplicateRecipe>(PredR->getOperand(0)->getDef());
     assert(RepR->isPredicated() &&
            "expected Replicate recipe to be predicated");
     RepR->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.");
-  // Record predicated instructions for above packing optimizations.
-  VPBlockBase *Region = createReplicateRegion(I, Recipe, Plan);
+  SmallVector<VPBlockBase *, 4> Succs(VPBB->getSuccessors().begin(),
+                                      VPBB->getSuccessors().end());
+  for (auto *Succ : VPBB->getSuccessors())
+    VPBlockUtils::disconnectBlocks(VPBB, Succ);
+  VPBlockBase *Region;
+  std::tie(Region, Recipe) = 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) {
+std::pair<VPRegionBlock *, VPRecipeBase *>
+VPRecipeBuilder::createReplicateRegion(Instruction *Instr,
   // Instructions marked for predication are replicated and placed under an
   // if-then construct to prevent side-effects.
 
   // Generate recipes to compute the block mask for this region.
   VPValue *BlockInMask = createBlockInMask(Instr->getParent(), Plan);
 
   // Build the triangular if-then region.
   std::string RegionName = (Twine("pred.") + Instr->getOpcodeName()).str();
VPRecipeBuilder::createReplicateRegion(Instruction *Instr,
   auto *Pred = new VPBasicBlock(Twine(RegionName) + ".if", PredRecipe);
   VPRegionBlock *Region = new VPRegionBlock(Entry, Exit, RegionName, true);
 
   // Note: first set Entry as region entry and then connect successors starting
   // from it in order, to propagate the "parent" of each VPBasicBlock.
   VPBlockUtils::insertTwoBlocksAfter(Pred, Exit, BlockInMask, Entry);
   VPBlockUtils::connectBlocks(Pred, Exit);
 
-  return Region;
+  return {Region, PHIRecipe ? PHIRecipe : PredRecipe};
 }
 
 VPRecipeOrVPValueTy
 VPRecipeBuilder::tryToCreateWidenRecipe(Instruction *Instr,
                                         ArrayRef<VPValue *> Operands,
                                         VFRange &Range, VPlanPtr &Plan) {
   // First, check for specific widening recipes that deal with calls, memory
   // operations, inductions and Phi nodes.
bool InvariantCond =
         PSE.getSE()->isLoopInvariant(PSE.getSCEV(SI->getOperand(0)), OrigLoop);
     return toVPRecipeResult(new VPWidenSelectRecipe(
         *SI, make_range(Operands.begin(), Operands.end()), InvariantCond));
   }
 
   return toVPRecipeResult(tryToWiden(Instr, Operands));
 }
 
+VPlanPtr LoopVectorizationPlanner::clone(VPlan &OriginalPlan) {
+  VPBlockBase *EntryBlock = OriginalPlan.getEntry()->getEntryBasicBlock();
+
+  auto Plan = std::make_unique<VPlan>();
+  DenseMap<VPBlockBase *, VPBlockBase *> Old2NewBlocks;
+  auto *TopRegion = new VPRegionBlock("TopRegion");
+  Old2NewBlocks[OriginalPlan.getEntry()] = TopRegion;
+
+  // Clone blocks of the original plan, add them to cloned plan.
+  for (VPBlockBase *Base : depth_first(EntryBlock)) {
+    assert(isa<VPBasicBlock>(Base) &&
+           "VPlans without nested regions can be cloned at the moment");
+    Old2NewBlocks[Base] = new VPBasicBlock(Base->getName());
+    Old2NewBlocks[Base]->setParent(
+        cast<VPRegionBlock>(Old2NewBlocks[Base->getParent()]));
+  }
+
+  Plan->setEntry(TopRegion);
+  TopRegion->setEntry(
+      Old2NewBlocks[OriginalPlan.getEntry()->getEntryBasicBlock()]);
+
+  // Connect blocks in cloned plan.
+  for (VPBlockBase *Base : depth_first(EntryBlock)) {
+    for (auto *Succ : Base->getSuccessors()) {
+      VPBlockUtils::connectBlocks(Old2NewBlocks[Base], Old2NewBlocks[Succ]);
+    }
+  }
+
+  DenseMap<VPValue *, VPValue *> Old2New;
+  // Update operands of U to use the version in the cloned plan.
+  auto RemapOperands = [&Old2New, &Plan](VPRecipeBase *U) {
+    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);
+    }
+  };
+
+  // Clone each recipe in the original plan and add it to the cloned plan.
+  SmallVector<VPRecipeBase *, 4> PhisToFix;
+  for (VPBlockBase *Base : depth_first(EntryBlock)) {
+    VPBasicBlock *OrigVPBB = cast<VPBasicBlock>(Base);
+    VPBasicBlock *VPBB = cast<VPBasicBlock>(Old2NewBlocks[OrigVPBB]);
+    for (VPRecipeBase &OrigR : *OrigVPBB) {
+      VPRecipeBase *NewI = OrigR.clone();
+      if (isa<VPWidenPHIRecipe>(NewI))
+        PhisToFix.push_back(NewI);
+      else
+        RemapOperands(NewI);
+
+      for (unsigned I = 0, E = NewI->getNumDefinedValues(); I != E; ++I) {
+        VPValue *NewDef = NewI->getVPValue(I);
+        Old2New[OrigR.getVPValue(I)] = NewDef;
+        Plan->addVPValue(NewDef->getUnderlyingValue(), NewDef);
+      }
+
+      VPBB->appendRecipe(NewI);
+    }
+  }
+
+  for (VPRecipeBase *R : PhisToFix)
+    RemapOperands(R);
+
+  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,
   }
 
   // Remove dead instructions from original VPlan.
   auto *DummyVal = new VPValue();
   OriginalPlan.addExternalDef(DummyVal);
   for (VPBlockBase *Base :
        depth_first<VPBlockBase *>(TopRegion->getEntryBasicBlock())) {
     VPBasicBlock *OriginalVPBB = Base->getEntryBasicBlock();
+
+    // Condition bits set by predicator is not used for now. Drop it.
+    OriginalVPBB->setCondBit(nullptr);
+
     for (VPRecipeBase &Ingredient :
          make_early_inc_range(reverse(*OriginalVPBB))) {
       VPInstruction *VPInst = dyn_cast<VPInstruction>(&Ingredient);
-      if (!VPInst)
+      if (!VPInst || !VPInst->getUnderlyingValue())
         continue;
       Instruction *Instr = VPInst->getUnderlyingInstr();
 
       if (DeadInstructions.contains(Instr) || isa<DbgInfoIntrinsic>(Instr)) {
         Ingredient.getVPValue()->replaceAllUsesWith(DummyVal);
         Ingredient.eraseFromParent();
       }
 
       auto Iter = Inst2VPInst.find(Instr);
       if (Iter != Inst2VPInst.end())
         Iter->second = VPInst;
     }
   }
 
+  SmallVector<VPRecipeBase *, 4> ToRemove;
+  // Currently the update instruction of induction PHIs is part of the
+  // instructions to remove. So the use in the VPWidenPHIRecipe will be replaced
+  // by DummyVal, but the recipe won't be removed. Replace it with a new phi
+  // node that only has the start value as operand.
+  for (VPUser *U : DummyVal->users()) {
+    VPRecipeBase *R = cast<VPRecipeBase>(U);
+    auto *VPhi = cast<VPWidenPHIRecipe>(R);
+    auto *NewP =
+        new VPWidenPHIRecipe(cast<PHINode>(VPhi->getUnderlyingValue()));
+    // Not all PHIs set the start value so far.
+    if (VPhi->getStartValue())
+      NewP->addOperand(VPhi->getStartValue());
+    NewP->insertBefore(VPhi);
+    VPhi->getVPValue()->replaceAllUsesWith(NewP);
+    ToRemove.push_back(R);
+  }
+  for (VPRecipeBase *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>();
-
-  VPBasicBlock *Header = OriginalPlan.getEntry()->getEntryBasicBlock();
+  auto Plan = clone(OriginalPlan);
+  VPBasicBlock *Header = Plan->getEntry()->getEntryBasicBlock();
   ReversePostOrderTraversal<VPBlockBase *> RPOT(Header);
 
   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;) {
+    auto ReplaceAllUsesWith = [&Plan](VPDef *Old, VPDef *New) {
+      for (auto &NewV : enumerate(New->definedValues())) {
+        VPValue *OldV = Old->getVPValue(NewV.index());
+        if (auto *UV = OldV->getUnderlyingValue()) {
+          Plan->removeVPValueFor(UV);
+          Plan->addVPValue(UV, NewV.value());
+        }
+        OldV->replaceAllUsesWith(NewV.value());
+      }
+    };
+    auto FirstNonPhi = VPBB->getFirstNonPhi();
+    auto I = VPBB->begin(), E = VPBB->end();
+    while (I != E && (isa<VPWidenIntOrFpInductionRecipe>(*I) ||
+                      isa<VPWidenPHIRecipe>(*I))) {
       VPRecipeBase *Ingredient = &*I++;
-      // First, clone & add the recipes introduced earlier.
-      if (isa<VPWidenIntOrFpInductionRecipe>(Ingredient)) {
-        auto *C = Ingredient->clone();
-        for (unsigned I = 0, E = C->getNumDefinedValues(); I != E; ++I) {
-          auto *NewDef = C->getVPValue(I);
-          auto *UV = NewDef->getUnderlyingValue();
-          Plan->addVPValue(UV, NewDef);
-          Ingredient->getVPValue(I)->replaceAllUsesWith(NewDef);
-        }
-        for (unsigned I = 0, E = Ingredient->getNumOperands(); I != E; ++I)
-          C->setOperand(I, Plan->getOrAddVPValue(
-                               Ingredient->getOperand(I)->getLiveInIRValue()));
-        VPBB->appendRecipe(C);
+      if (isa<VPWidenIntOrFpInductionRecipe>(Ingredient))
         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))
-        continue;
-
-      SmallVector<VPValue *, 4> Operands;
-      auto *Phi = dyn_cast<PHINode>(Instr);
-      if (Phi && Phi->getParent() == OrigLoop->getHeader()) {
-        Operands.push_back(Plan->getOrAddVPValue(
-            Phi->getIncomingValueForBlock(OrigLoop->getLoopPreheader())));
-      } else {
-        auto OpRange = Plan->mapToVPValues(Instr->operands());
-        Operands = {OpRange.begin(), OpRange.end()};
-      }
-      if (auto RecipeOrValue = RecipeBuilder.tryToCreateWidenRecipe(
-              Instr, Operands, 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>(
+      Builder.setInsertPoint(Ingredient->getParent(), FirstNonPhi);
+      auto RecipeOrValue = RecipeBuilder.tryToCreateWidenRecipe(
+          Phi, {Ingredient->op_begin(), Ingredient->getNumOperands()}, 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(Ingredient, 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) && !isa<PHINode>(Instr) &&
+             "Branch and PHI instruction must be removed earlier");
+      auto InsertPt = Ingredient->getIterator();
+      if (Base != VPBB)
+        InsertPt = VPBB->end();
+      Builder.setInsertPoint(VPBB, InsertPt);
+      VPRecipeBase *Recipe = nullptr;
+      if (auto RecipeOrValue = RecipeBuilder.tryToCreateWidenRecipe(
+              Instr, {Ingredient->op_begin(), Ingredient->getNumOperands()},
+              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, Plan);
+        auto Res = RecipeBuilder.handleReplication(Instr, Range, VPBB, Plan);
+        VPBasicBlock *NextVPBB = Res.first;
+        Recipe = Res.second;
         if (NextVPBB != VPBB) {
           VPBB = NextVPBB;
-        VPBB->setName(OriginalVPBB->getName() + "." + Twine(VPBBsForBB++));
+          VPBB->setName(Base->getName() + "." + Twine(VPBBsForBB++));
+        } else {
+          VPBB->insert(Recipe, InsertPt);
+        }
       }
+
+      ReplaceAllUsesWith(Ingredient, 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

assert(Ingredient2Recipe.count(I) &&
            "Recording this ingredients recipe was not requested");
     assert(Ingredient2Recipe[I] != nullptr &&
            "Ingredient doesn't have a recipe");
     return Ingredient2Recipe[I];
   }
 
   /// Create a replicating region for instruction \p I that requires
   /// predication. \p PredRecipe is a VPReplicateRecipe holding \p I.
-  VPRegionBlock *createReplicateRegion(Instruction *I, VPRecipeBase *PredRecipe,
-                                       VPlanPtr &Plan);
+  std::pair<VPRegionBlock *, VPRecipeBase *>
+  createReplicateRegion(Instruction *I, VPRecipeBase *PredRecipe,
 
   /// 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(
-      Instruction *I, VFRange &Range, VPBasicBlock *VPBB,
+  std::pair<VPBasicBlock *, VPRecipeBase *>
+  handleReplication(Instruction *I, VFRange &Range, VPBasicBlock *VPBB,
                     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; }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   /// Print this VPlan to \p O.

llvm/lib/Transforms/Vectorize/VPlan.cpp

void VPWidenGEPRecipe::print(raw_ostream &O, const Twine &Indent,
   O << " ";
   printAsOperand(O, SlotTracker);
   O << " = getelementptr ";
   printOperands(O, SlotTracker);
 }
 
 void VPWidenPHIRecipe::print(raw_ostream &O, const Twine &Indent,
                              VPSlotTracker &SlotTracker) const {
-  O << Indent << "WIDEN-PHI " << VPlanIngredient(getUnderlyingValue());
+  O << Indent << "WIDEN-PHI ";
+  printAsOperand(O, SlotTracker);
+  O << " = phi ";
+  printOperands(O, SlotTracker);
+  O << " (original " << VPlanIngredient(getUnderlyingValue()) << ")";
 }
 
 void VPBlendRecipe::print(raw_ostream &O, const Twine &Indent,
                           VPSlotTracker &SlotTracker) const {
   O << Indent << "BLEND ";
   Phi->printAsOperand(O, false);
   O << " =";
   if (getNumIncomingValues() == 1) {

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/icmp-uniforms.ll

 
 for.end:
   %tmp4 = phi i32 [ %tmp3, %for.body ]
   ret i32 %tmp4
 }
 
 ; Check for crash exposed by D76992.
 ; CHECK:      VPlan 'Initial VPlan for VF={4},UF>=1' {
-; CHECK-NEXT: loop:
-; CHECK-NEXT:   WIDEN-INDUCTION %iv = phi 0, %iv.next
-; CHECK-NEXT:   WIDEN ir<%cond0> = icmp ir<%iv>, ir<13>
-; CHECK-NEXT:   WIDEN-SELECT ir<%s> = select ir<%cond0>, ir<10>, ir<20>
-; CHECK-NEXT: No successor
-; CHECK-NEXT: }
+; CHECK-NEXT: <x1> TopRegion: {
+; CHECK-NEXT:   loop:
+; CHECK-NEXT:     WIDEN-INDUCTION %iv = phi 0, %iv.next
+; CHECK-NEXT:     WIDEN ir<%cond0> = icmp ir<%iv>, ir<13>
+; CHECK-NEXT:     WIDEN-SELECT ir<%s> = select ir<%cond0>, ir<10>, ir<20>
+; CHECK-NEXT:   No successor
+; CHECK-NEXT:   }
+; CHECK-NEXT: }
 define void @test() {
 entry:
   br label %loop
 
 loop:                       ; preds = %loop, %entry
   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
   %cond0 = icmp ult i64 %iv, 13
   %s = select i1 %cond0, i32 10, i32 20
   %iv.next = add nuw nsw i64 %iv, 1
   %exitcond = icmp eq i64 %iv.next, 14
   br i1 %exitcond, label %exit, label %loop
 
 exit:           ; preds = %loop
   ret void
 }

llvm/test/Transforms/LoopVectorize/vplan-dot-printing.ll

 ; REQUIRES: asserts
 
 ; RUN: opt -loop-vectorize -debug-only=loop-vectorize -force-vector-interleave=1 -force-vector-width=4 -vplan-print-in-dot-format -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"
 
 ; Verify that -vplan-print-in-dot-format option works.
 
 define void @print_call_and_memory(i64 %n, float* noalias %y, float* noalias %x) nounwind uwtable {
-; CHECK:       N0 [label =
+; CHECK:       N1 [label =
 ; CHECK-NEXT:    "for.body:\l" +
 ; CHECK-NEXT:    "  WIDEN-INDUCTION %iv = phi %iv.next, 0\l" +
 ; CHECK-NEXT:    "  CLONE ir\<%arrayidx\> = getelementptr ir\<%y\>, ir\<%iv\>\l" +
 ; CHECK-NEXT:    "  WIDEN ir\<%lv\> = load ir\<%arrayidx\>\l" +
 ; CHECK-NEXT:    "  WIDEN-CALL ir\<%call\> = call @llvm.sqrt.f32(ir\<%lv\>)\l" +
 ; CHECK-NEXT:    "  CLONE ir\<%arrayidx2\> = getelementptr ir\<%x\>, ir\<%iv\>\l" +
 ; CHECK-NEXT:    "  WIDEN store ir\<%arrayidx2\>, ir\<%call\>\l" +
 ; CHECK-NEXT:    "No successors\l"

llvm/test/Transforms/LoopVectorize/vplan-printing.ll

 ; REQUIRES: asserts
 
 ; RUN: opt -loop-vectorize -debug-only=loop-vectorize -force-vector-interleave=1 -force-vector-width=4 -prefer-inloop-reductions -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"
 
 ; Tests for printing VPlans.
 
 define void @print_call_and_memory(i64 %n, float* noalias %y, float* noalias %x) nounwind uwtable {
 ; CHECK-LABEL: Checking a loop in "print_call_and_memory"
 ; CHECK:      VPlan 'Initial VPlan for VF={4},UF>=1' {
+; CHECK-NEXT: <x1> TopRegion: {
 ; CHECK-NEXT: for.body:
 ; CHECK-NEXT:   WIDEN-INDUCTION %iv = phi %iv.next, 0
 ; CHECK-NEXT:   CLONE ir<%arrayidx> = getelementptr ir<%y>, ir<%iv>
 ; CHECK-NEXT:   WIDEN ir<%lv> = load ir<%arrayidx>
 ; CHECK-NEXT:   WIDEN-CALL ir<%call> = call @llvm.sqrt.f32(ir<%lv>)
 ; CHECK-NEXT:   CLONE ir<%arrayidx2> = getelementptr ir<%x>, ir<%iv>
 ; CHECK-NEXT:   WIDEN store ir<%arrayidx2>, ir<%call>
 ; CHECK-NEXT: No successors

 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
 define void @print_widen_gep_and_select(i64 %n, float* noalias %y, float* noalias %x, float* %z) nounwind uwtable {
 ; CHECK-LABEL: Checking a loop in "print_widen_gep_and_select"
 ; CHECK:      VPlan 'Initial VPlan for VF={4},UF>=1' {
+; CHECK-NEXT: <x1> TopRegion: {
 ; CHECK-NEXT: for.body:
 ; CHECK-NEXT:   WIDEN-INDUCTION %iv = phi %iv.next, 0
 ; CHECK-NEXT:   WIDEN-GEP Inv[Var] ir<%arrayidx> = getelementptr ir<%y>, ir<%iv>
 ; CHECK-NEXT:   WIDEN ir<%lv> = load ir<%arrayidx>
 ; CHECK-NEXT:   WIDEN ir<%cmp> = icmp ir<%arrayidx>, ir<%z>
 ; CHECK-NEXT:   WIDEN-SELECT ir<%sel> = select ir<%cmp>, ir<1.000000e+01>, ir<2.000000e+01>
 ; CHECK-NEXT:   WIDEN ir<%add> = fadd ir<%lv>, ir<%sel>
 ; CHECK-NEXT:   CLONE ir<%arrayidx2> = getelementptr ir<%x>, ir<%iv>

 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
 define float @print_reduction(i64 %n, float* noalias %y) {
 ; CHECK-LABEL: Checking a loop in "print_reduction"
 ; CHECK:      VPlan 'Initial VPlan for VF={4},UF>=1' {
+; CHECK-NEXT: <x1> TopRegion: {
 ; CHECK-NEXT: for.body:
 ; CHECK-NEXT:   WIDEN-INDUCTION %iv = phi %iv.next, 0
 ; CHECK-NEXT:   WIDEN-PHI %red = phi %red.next, 0.000000e+00
 ; CHECK-NEXT:   CLONE ir<%arrayidx> = getelementptr ir<%y>, ir<%iv>
 ; CHECK-NEXT:   WIDEN ir<%lv> = load ir<%arrayidx>
 ; CHECK-NEXT:   REDUCE ir<%red.next> = ir<%red> + reduce.fadd (ir<%lv>)
 ; CHECK-NEXT: No successors
 ; CHECK-NEXT: }

 
 for.end:                                          ; preds = %for.body, %entry
   ret float %red.next
 }
 
 define void @print_replicate_predicated_phi(i64 %n, i64* %x) {
 ; CHECK-LABEL: Checking a loop in "print_replicate_predicated_phi"
 ; CHECK:      VPlan 'Initial VPlan for VF={4},UF>=1' {
+; CHECK-NEXT: <x1> TopRegion: {
 ; CHECK-NEXT: for.body:
 ; CHECK-NEXT:   WIDEN-INDUCTION %i = phi 0, %i.next
 ; CHECK-NEXT:   WIDEN ir<%cmp> = icmp ir<%i>, ir<5>
 ; CHECK-NEXT: Successor(s): if.then
 ; CHECK-EMPTY:
 ; CHECK-NEXT: if.then:
 ; CHECK-NEXT: Successor(s): pred.udiv
 ; CHECK-EMPTY: