[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(unsigned MinVF, unsigned 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<Value *> &NeedDef,
       SmallPtrSetImpl<Instruction *> &DeadInstructions,
       const DenseMap<Instruction *, Instruction *> &SinkAfter);
 
+  VPlanPtr
+  convertToVPRecipes(VPlan &OriginalPlan, VFRange &Range,
+                     SmallPtrSetImpl<Value *> &NeedDef,
+                     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(unsigned MinVF, unsigned MaxVF);
+  void buildVPlansWithVPRecipes(unsigned MinVF, unsigned 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

Optional<unsigned> LoopVectorizationCostModel::computeMaxVF(unsigned UserVF,
 
   // 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();
   }
 
   unsigned MaxVF = UserVF ? UserVF : computeFeasibleMaxVF(TC);
   assert((UserVF || isPowerOf2_32(MaxVF)) && "MaxVF must be a power of 2");
   unsigned MaxVFtimesIC = UserIC ? MaxVF * UserIC : MaxVF;
   if (TC > 0 && TC % MaxVFtimesIC == 0) {
     // Accept MaxVF if we do not have a tail.
LoopVectorizationPlanner::plan(ElementCount UserVF, unsigned UserIC) {
   if (!UserVF.isZero()) {
     LLVM_DEBUG(dbgs() << "LV: Using user VF " << UserVF << ".\n");
     assert(isPowerOf2_32(UserVF.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(UserVF);
     CM.collectInLoopReductions();
+    auto InitialPlan =
+        buildVPlan({UserVF.getKnownMinValue(), UserVF.getKnownMinValue()});
     buildVPlansWithVPRecipes(UserVF.getKnownMinValue(),
-                             UserVF.getKnownMinValue());
+                             UserVF.getKnownMinValue(), *InitialPlan);
     LLVM_DEBUG(printPlans(dbgs()));
     return {{UserVF, 0}};
   }
 
   unsigned MaxVF = MaybeMaxVF.getValue();
   assert(MaxVF != 0 && "MaxVF is zero.");
 
   for (unsigned VF = 1; VF <= MaxVF; VF *= 2) {
     // Collect Uniform and Scalar instructions after vectorization with VF.
     CM.collectUniformsAndScalars(ElementCount::getFixed(VF));
 
     // Collect the instructions (and their associated costs) that will be more
     // profitable to scalarize.
     if (VF > 1)
       CM.collectInstsToScalarize(ElementCount::getFixed(VF));
   }
 
   CM.collectInLoopReductions();
 
-  buildVPlansWithVPRecipes(1, MaxVF);
+  auto InitialPlan = buildVPlan({1, MaxVF});
+  buildVPlansWithVPRecipes(1, MaxVF, *InitialPlan);
   LLVM_DEBUG(printPlans(dbgs()));
   if (MaxVF == 1)
     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(unsigned MinVF, unsigned 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.");
+
   for (unsigned VF = MinVF; VF < MaxVF + 1;) {
     VFRange SubRange = {VF, MaxVF + 1};
-    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");
 
if (auto *SI = dyn_cast<SelectInst>(Instr)) {
     return new VPWidenSelectRecipe(*SI, Plan->mapToVPValues(SI->operands()),
                                    InvariantCond);
   }
 
   return tryToWiden(Instr, *Plan);
 }
 
 void LoopVectorizationPlanner::buildVPlansWithVPRecipes(unsigned MinVF,
-                                                        unsigned MaxVF) {
+                                                        unsigned MaxVF,
+                                                        VPlan &OriginalPlan) {
   assert(OrigLoop->isInnermost() && "Inner loop expected.");
 
   // Collect conditions feeding internal conditional branches; they need to be
   // represented in VPlan for it to model masking.
   SmallPtrSet<Value *, 1> NeedDef;
 
   auto *Latch = OrigLoop->getLoopLatch();
   for (BasicBlock *BB : OrigLoop->blocks()) {
void LoopVectorizationPlanner::buildVPlansWithVPRecipes(unsigned MinVF,
   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);
 
+  auto *TopRegion = cast<VPRegionBlock>(OriginalPlan.getEntry());
+  ReversePostOrderTraversal<VPBlockBase *> RPOT(TopRegion->getEntry());
+
+  auto *DummyVal = new VPValue();
+  OriginalPlan.addExternalDef(DummyVal);
+  for (VPBlockBase *Base : RPOT) {
+    // Do not widen instructions in pre-header and exit blocks.
+    if (Base->getNumPredecessors() == 0 || Base->getNumSuccessors() == 0)
+      continue;
+
+    VPBasicBlock *OriginalVPBB = Base->getEntryBasicBlock();
+    OriginalVPBB->setCondBit(nullptr);
+    // Introduce each ingredient into VPlan.
+    for (auto I = OriginalVPBB->rbegin(), E = OriginalVPBB->rend(); I != E;) {
+      VPRecipeBase *Ingredient = &*I++;
+      VPInstruction *VPInst = cast<VPInstruction>(Ingredient);
+      Instruction *Instr = VPInst->getUnderlyingInstr();
+
+      if (DeadInstructions.contains(Instr) || isa<DbgInfoIntrinsic>(Instr)) {
+        Ingredient->getVPValue()->replaceAllUsesWith(DummyVal);
+        Ingredient->eraseFromParent();
+      }
+    }
+  }
+
   for (unsigned VF = MinVF; VF < MaxVF + 1;) {
     VFRange SubRange = {VF, MaxVF + 1};
-    VPlans.push_back(buildVPlanWithVPRecipes(SubRange, NeedDef,
-                                             DeadInstructions, SinkAfter));
+    VPlans.push_back(
+        convertToVPRecipes(OriginalPlan, SubRange, NeedDef, SinkAfter));
     VF = SubRange.End;
   }
 }
 
-VPlanPtr LoopVectorizationPlanner::buildVPlanWithVPRecipes(
-    VFRange &Range, SmallPtrSetImpl<Value *> &NeedDef,
-    SmallPtrSetImpl<Instruction *> &DeadInstructions,
+VPlanPtr LoopVectorizationPlanner::convertToVPRecipes(
+    VPlan &OriginalPlan, VFRange &Range, SmallPtrSetImpl<Value *> &NeedDef,
     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(
   for (Value *V : NeedDef)
     Plan->addVPValue(V);
 
   // 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())) {
+  auto *TopRegion = cast<VPRegionBlock>(OriginalPlan.getEntry());
+  ReversePostOrderTraversal<VPBlockBase *> RPOT(TopRegion->getEntry());
+
+  for (VPBlockBase *Base : RPOT) {
+    // Do not widen instructions in pre-header and exit blocks.
+    if (Base->getNumPredecessors() == 0 || Base->getNumSuccessors() == 0)
+      continue;
+
+    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());
     VPBlockUtils::insertBlockAfter(FirstVPBBForBB, VPBB);
     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 = cast<VPInstruction>(Ingredient);
+      Instruction *Instr = VPInst->getUnderlyingInstr();
 
       // First filter out irrelevant instructions, to ensure no recipes are
       // built for them.
-      if (isa<BranchInst>(Instr) || DeadInstructions.count(Instr) ||
-          DeadInterleaveGroupMembers.contains(Instr))
+      if (isa<BranchInst>(Instr) || DeadInterleaveGroupMembers.contains(Instr))
         continue;
 
       if (auto Recipe =
               RecipeBuilder.tryToCreateWidenRecipe(Instr, Range, Plan)) {
         auto RegisterVPValue = [&Plan, &NeedDef](Value *V, VPValue *Def) {
           if (NeedDef.contains(V))
             Plan->addOrReplaceVPValue(V, Def);
           else
             Plan->addVPValue(V, Def);
         };
 
         if (Recipe->getNumDefinedValues() > 1) {
           for (auto *Def : Recipe->defined_values()) {
             auto *UV = Def->getUnderlyingValue();
             RegisterVPValue(UV, Def);
           }
         } else if (Recipe->getNumDefinedValues() != 0) {
           assert(Recipe->getNumDefinedValues() == 1 &&
                  "all multi-defs should be handled earlier");
-          RegisterVPValue(&I, Recipe->getVPValue());
+          RegisterVPValue(Instr, Recipe->getVPValue());
         }
 
         RecipeBuilder.setRecipe(Instr, Recipe);
         VPBB->appendRecipe(Recipe);
         continue;
       }
 
       // Otherwise, if all widening options failed, Instruction is to be
       // replicated. This may create a successor for VPBB.
       VPBasicBlock *NextVPBB = RecipeBuilder.handleReplication(
           Instr, Range, VPBB, 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());
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 (unsigned VF = Range.Start; VF < Range.End; VF *= 2)
     Plan->addVF(ElementCount::getFixed(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;
   }