[LV] Build generic VPlan up-front.

[fhahn]

Summary

This is a first step towards generating an initial VPlan up-front using
VPInstructions. No decisions are taken at this point. Starting from this
VPlan, we transform VPInstructions into various recipes if possible,
e.g. by widening them. For now, this still exclusively uses the
underlying instructions and the existing cost model.

Breaking things up further, i.e. lower to specialized recipes without
the legacy cost model, is part of the next steps.

This patch also moves the code to weed out dead instruction into a
transform on the initial VPlan. Similarly, sinking instructions can also
be done up-front, before we widen the VPInstructions. This is also a
follow-up, together with moving more of the existing small patch-ups we
do after generating the VPlans.

[fhahn]

rebased and simplified a bit

[fhahn]

Ping :) Also removed some unrelated changes.

I linked a patch series up to D97712, which starts with a generic initial VPlan (that's created in this patch). For each VF, the plan is cloned and VF specific transformations can now happen on the plans directly. At the moment, that is just VF-specific recipe creation, but it should allow us to finally add some more targeted transforms.

[fhahn]

Rebase and some simplifications.

[fhahn]

Update comment.

[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

protected:
   /// according to the information gathered by Legal when it checked if it is
   /// legal to vectorize the loop.
   void buildVPlans(ElementCount MinVF, ElementCount MaxVF);
 
 private:
   /// Build a VPlan according to the information gathered by Legal. \return a
   /// VPlan for vectorization factors \p Range.Start and up to \p Range.End
   /// exclusive, possibly decreasing \p Range.End.
-  VPlanPtr buildVPlan(VFRange &Range);
+  VPlanPtr buildVPlan(const VFRange &Range);
 
   /// Build a VPlan using VPRecipes according to the information gather by
   /// Legal. This method is only used for the legacy inner loop vectorizer.
   VPlanPtr buildVPlanWithVPRecipes(
       VFRange &Range, SmallPtrSetImpl<Instruction *> &DeadInstructions,
       const DenseMap<Instruction *, Instruction *> &SinkAfter);
 
+  VPlanPtr
+  convertToVPRecipes(VPlan &OriginalPlan, VFRange &Range,
+                     const DenseMap<Instruction *, Instruction *> &SinkAfter);
+
   /// Build VPlans for power-of-2 VF's between \p MinVF and \p MaxVF inclusive,
   /// according to the information gathered by Legal when it checked if it is
   /// legal to vectorize the loop. This method creates VPlans using VPRecipes.
   void buildVPlansWithVPRecipes(ElementCount MinVF, ElementCount MaxVF);
+  void buildVPlansWithVPRecipes(ElementCount MinVF, ElementCount MaxVF,
+                                VPlan &OriginalPlan);
 
   /// Adjust the recipes for any inloop reductions. The chain of instructions
   /// leading from the loop exit instr to the phi need to be converted to
   /// reductions, with one operand being vector and the other being the scalar
   /// reduction chain.
   void adjustRecipesForInLoopReductions(VPlanPtr &Plan,
                                         VPRecipeBuilder &RecipeBuilder);
 };
 
 } // namespace llvm
 
 #endif // LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONPLANNER_H

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

LoopVectorizationCostModel::computeMaxVF(ElementCount UserVF, unsigned UserIC) {
 
   // Now try the tail folding
 
   // Invalidate interleave groups that require an epilogue if we can't mask
   // the interleave-group.
   if (!useMaskedInterleavedAccesses(TTI)) {
     assert(WideningDecisions.empty() && Uniforms.empty() && Scalars.empty() &&
            "No decisions should have been taken at this point");
-    // Note: There is no need to invalidate any cost modeling decisions here, as
-    // non where taken so far.
     InterleaveInfo.invalidateGroupsRequiringScalarEpilogue();
   }
 
   ElementCount MaxVF = computeFeasibleMaxVF(TC, UserVF);
   assert(!MaxVF.isScalable() &&
          "Scalable vectors do not yet support tail folding");
   assert((UserVF.isNonZero() || isPowerOf2_32(MaxVF.getFixedValue())) &&
          "MaxVF must be a power of 2");
if (!UserVF.isZero() &&
     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();
-    buildVPlansWithVPRecipes(VF, VF);
+    auto InitialPlan = buildVPlan({VF, VF});
+    buildVPlansWithVPRecipes(VF, VF, *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();
 
-  buildVPlansWithVPRecipes(ElementCount::getFixed(1), MaxVF);
+  auto InitialPlan = buildVPlan({ElementCount::getFixed(1), MaxVF});
+  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);
 }
 

 
 /// Build VPlans for the full range of feasible VF's = {\p MinVF, 2 * \p MinVF,
 /// 4 * \p MinVF, ..., \p MaxVF} by repeatedly building a VPlan for a sub-range
 /// of VF's starting at a given VF and extending it as much as possible. Each
 /// vectorization decision can potentially shorten this sub-range during
 /// buildVPlan().
 void LoopVectorizationPlanner::buildVPlans(ElementCount MinVF,
                                            ElementCount MaxVF) {
+  // Outer loop handling: They may require CFG and instruction level
+  // transformations before even evaluating whether vectorization is profitable.
+  // Since we cannot modify the incoming IR, we need to build VPlan upfront in
+  // the vectorization pipeline.
+  assert(!OrigLoop->isInnermost());
+  assert(EnableVPlanNativePath && "VPlan-native path is not enabled.");
+
   auto MaxVFPlusOne = MaxVF.getWithIncrement(1);
   for (ElementCount VF = MinVF; ElementCount::isKnownLT(VF, MaxVFPlusOne);) {
     VFRange SubRange = {VF, MaxVFPlusOne};
-    VPlans.push_back(buildVPlan(SubRange));
+    auto Plan = buildVPlan(SubRange);
+
+    if (EnableVPlanPredication) {
+      VPlanPredicator VPP(*Plan);
+      VPP.predicate();
+      // Avoid running transformation to recipes until masked code generation in
+      // VPlan-native path is in place.
+    } else {
+      SmallPtrSet<Instruction *, 1> DeadInstructions;
+      VPlanTransforms::VPInstructionsToVPRecipes(
+          OrigLoop, Plan, Legal->getInductionVars(), DeadInstructions);
+    }
+
+    VPlans.emplace_back(std::move(Plan));
     VF = SubRange.End;
   }
 }
 
 VPValue *VPRecipeBuilder::createEdgeMask(BasicBlock *Src, BasicBlock *Dst,
                                          VPlanPtr &Plan) {
   assert(is_contained(predecessors(Dst), Src) && "Invalid edge");
 
VPRecipeOrVPValueTy VPRecipeBuilder::tryToCreateWidenRecipe(Instruction *Instr,
 
   if (auto *SI = dyn_cast<SelectInst>(Instr)) {
     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));
 }
 
 void LoopVectorizationPlanner::buildVPlansWithVPRecipes(ElementCount MinVF,
-                                                        ElementCount MaxVF) {
+                                                        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.
+  VPBasicBlock *Exit =
+      cast<VPBasicBlock>(OriginalPlan.getEntry()->getExitBasicBlock());
+  SmallVector<VPBlockBase *, 2> Preds(Exit->getPredecessors().begin(),
+                                      Exit->getPredecessors().end());
+  for (VPBlockBase *Pred : Preds)
+    VPBlockUtils::disconnectBlocks(Pred, Exit);
+  delete Exit;
+
+  VPBasicBlock *PreEntry =
+      cast<VPBasicBlock>(OriginalPlan.getEntry()->getEntryBasicBlock());
+  assert(PreEntry->empty() && "Expecting empty pre-entry block.");
+  VPBlockBase *Entry = OriginalPlan.setEntry(PreEntry->getSingleSuccessor());
+  VPBlockUtils::disconnectBlocks(PreEntry, Entry);
+  delete PreEntry;
+
   // Collect instructions from the original loop that will become trivially dead
   // in the vectorized loop. We don't need to vectorize these instructions. For
   // example, original induction update instructions can become dead because we
   // separately emit induction "steps" when generating code for the new loop.
   // Similarly, we create a new latch condition when setting up the structure
   // of the new loop, so the old one can become dead.
   SmallPtrSet<Instruction *, 4> DeadInstructions;
   collectTriviallyDeadInstructions(DeadInstructions);
 
   // Add assume instructions we need to drop to DeadInstructions, to prevent
   // them from being added to the VPlan.
   // TODO: We only need to drop assumes in blocks that get flattend. If the
   // control flow is preserved, we should keep them.
   auto &ConditionalAssumes = Legal->getConditionalAssumes();
   DeadInstructions.insert(ConditionalAssumes.begin(), ConditionalAssumes.end());
 
   DenseMap<Instruction *, Instruction *> &SinkAfter = Legal->getSinkAfter();
   // Dead instructions do not need sinking. Remove them from SinkAfter.
   for (Instruction *I : DeadInstructions)
     SinkAfter.erase(I);
 
+  ReversePostOrderTraversal<VPBlockBase *> RPOT(
+      OriginalPlan.getEntry()->getEntryBasicBlock());
+
+  auto *DummyVal = new VPValue();
+  OriginalPlan.addExternalDef(DummyVal);
+  for (VPBlockBase *Base : RPOT) {
+    VPBasicBlock *OriginalVPBB = Base->getEntryBasicBlock();
+    // Introduce each ingredient into VPlan.
+    for (auto I = OriginalVPBB->rbegin(), E = OriginalVPBB->rend(); I != E;) {
+      VPRecipeBase *Ingredient = &*I++;
+      VPInstruction *VPInst = dyn_cast<VPInstruction>(Ingredient);
+      if (!VPInst)
+        continue;
+      Instruction *Instr = VPInst->getUnderlyingInstr();
+
+      if (DeadInstructions.contains(Instr) || isa<DbgInfoIntrinsic>(Instr)) {
+        Ingredient->getVPValue()->replaceAllUsesWith(DummyVal);
+        Ingredient->eraseFromParent();
+      }
+    }
+  }
+
   auto MaxVFPlusOne = MaxVF.getWithIncrement(1);
   for (ElementCount VF = MinVF; ElementCount::isKnownLT(VF, MaxVFPlusOne);) {
     VFRange SubRange = {VF, MaxVFPlusOne};
-    VPlans.push_back(
-        buildVPlanWithVPRecipes(SubRange, DeadInstructions, SinkAfter));
+    VPlans.push_back(convertToVPRecipes(OriginalPlan, SubRange, SinkAfter));
     VF = SubRange.End;
   }
 }
 
-VPlanPtr LoopVectorizationPlanner::buildVPlanWithVPRecipes(
-    VFRange &Range, SmallPtrSetImpl<Instruction *> &DeadInstructions,
+VPlanPtr LoopVectorizationPlanner::convertToVPRecipes(
+    VPlan &OriginalPlan, VFRange &Range,
     const DenseMap<Instruction *, Instruction *> &SinkAfter) {
 
   // Hold a mapping from predicated instructions to their recipes, in order to
   // fix their AlsoPack behavior if a user is determined to replicate and use a
   // scalar instead of vector value.
   DenseMap<Instruction *, VPReplicateRecipe *> PredInst2Recipe;
 
   SmallPtrSet<const InterleaveGroup<Instruction> *, 1> InterleaveGroups;
VPlanPtr LoopVectorizationPlanner::convertToVPRecipes(
 
   // ---------------------------------------------------------------------------
   // 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 *VPBB = new VPBasicBlock("Pre-Entry");
-  Plan->setEntry(VPBB);
 
   // 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);
 
-  for (BasicBlock *BB : make_range(DFS.beginRPO(), DFS.endRPO())) {
+  ReversePostOrderTraversal<VPBlockBase *> RPOT(
+      OriginalPlan.getEntry()->getEntryBasicBlock());
+
+  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(BB->getName());
+    auto *FirstVPBBForBB = new VPBasicBlock(OriginalVPBB->getName());
+    if (VPBB)
       VPBlockUtils::insertBlockAfter(FirstVPBBForBB, VPBB);
+    else
+      Plan->setEntry(FirstVPBBForBB);
     VPBB = FirstVPBBForBB;
     Builder.setInsertPoint(VPBB);
 
     // Introduce each ingredient into VPlan.
-    // TODO: Model and preserve debug instrinsics in VPlan.
-    for (Instruction &I : BB->instructionsWithoutDebug()) {
-      Instruction *Instr = &I;
+    for (auto I = OriginalVPBB->begin(), E = OriginalVPBB->end(); I != E;) {
+      VPRecipeBase *Ingredient = &*I++;
+      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) || DeadInstructions.count(Instr))
+      if (isa<BranchInst>(Instr))
         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;
for (auto I = OriginalVPBB->begin(), E = OriginalVPBB->end(); I != E;) {
       }
 
       // 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);
       if (NextVPBB != VPBB) {
         VPBB = NextVPBB;
-        VPBB->setName(BB->hasName() ? BB->getName() + "." + Twine(VPBBsForBB++)
-                                    : "");
+        VPBB->setName(OriginalVPBB->getName() + "." + Twine(VPBBsForBB++));
       }
     }
   }
 
-  // Discard empty dummy pre-entry VPBasicBlock. Note that other VPBasicBlocks
-  // may also be empty, such as the last one VPBB, reflecting original
-  // basic-blocks with no recipes.
-  VPBasicBlock *PreEntry = cast<VPBasicBlock>(Plan->getEntry());
-  assert(PreEntry->empty() && "Expecting empty pre-entry block.");
-  VPBlockBase *Entry = Plan->setEntry(PreEntry->getSingleSuccessor());
-  VPBlockUtils::disconnectBlocks(PreEntry, Entry);
-  delete PreEntry;
-
   // ---------------------------------------------------------------------------
   // Transform initial VPlan: Apply previously taken decisions, in order, to
   // bring the VPlan to its final state.
   // ---------------------------------------------------------------------------
 
   // Apply Sink-After legal constraints.
   for (auto &Entry : SinkAfter) {
     VPRecipeBase *Sink = RecipeBuilder.getRecipe(Entry.first);
VPlanPtr LoopVectorizationPlanner::convertToVPRecipes(
   }
   RSO << "},UF>=1";
   RSO.flush();
   Plan->setName(PlanName);
 
   return Plan;
 }
 
-VPlanPtr LoopVectorizationPlanner::buildVPlan(VFRange &Range) {
-  // Outer loop handling: They may require CFG and instruction level
-  // transformations before even evaluating whether vectorization is profitable.
-  // Since we cannot modify the incoming IR, we need to build VPlan upfront in
-  // the vectorization pipeline.
-  assert(!OrigLoop->isInnermost());
-  assert(EnableVPlanNativePath && "VPlan-native path is not enabled.");
-
+VPlanPtr LoopVectorizationPlanner::buildVPlan(const VFRange &Range) {
   // Create new empty VPlan
   auto Plan = std::make_unique<VPlan>();
 
   // Build hierarchical CFG
   VPlanHCFGBuilder HCFGBuilder(OrigLoop, LI, *Plan);
   HCFGBuilder.buildHierarchicalCFG();
 
   for (ElementCount VF = Range.Start; ElementCount::isKnownLT(VF, Range.End);
        VF *= 2)
     Plan->addVF(VF);
 
-  if (EnableVPlanPredication) {
-    VPlanPredicator VPP(*Plan);
-    VPP.predicate();
-
-    // Avoid running transformation to recipes until masked code generation in
-    // VPlan-native path is in place.
-    return Plan;
-  }
-
-  SmallPtrSet<Instruction *, 1> DeadInstructions;
-  VPlanTransforms::VPInstructionsToVPRecipes(
-      OrigLoop, Plan, Legal->getInductionVars(), DeadInstructions);
   return Plan;
 }
 
 // Adjust the recipes for any inloop reductions. The chain of instructions
 // leading from the loop exit instr to the phi need to be converted to
 // reductions, with one operand being vector and the other being the scalar
 // reduction chain.
 void LoopVectorizationPlanner::adjustRecipesForInLoopReductions(

llvm/lib/Transforms/Vectorize/VPlan.h

public:
 
   inline size_t size() const { return Recipes.size(); }
   inline bool empty() const { return Recipes.empty(); }
   inline const VPRecipeBase &front() const { return Recipes.front(); }
   inline VPRecipeBase &front() { return Recipes.front(); }
   inline const VPRecipeBase &back() const { return Recipes.back(); }
   inline VPRecipeBase &back() { return Recipes.back(); }
 
+  iterator_range<iterator> recipes() { return make_range(begin(), end()); }
+
   /// Returns a reference to the list of recipes.
   RecipeListTy &getRecipeList() { return Recipes; }
 
   /// Returns a pointer to a member of the recipe list.
   static RecipeListTy VPBasicBlock::*getSublistAccess(VPRecipeBase *) {
     return &VPBasicBlock::Recipes;
   }