[VPlan] Add VPBasicBlock::phis() helper (NFC).

[fhahn]

Summary

This patch introduces a helper to obtain an iterator range for the
PHI-like recipes in a block.

[fhahn]

ping :)

[Ayal]

Looks good to me!

This is aligned with BasicBlock::phis(), with a simpler implementation based on finding FirstNonPHI. Number of phi's is expected to be limited, so running twice until FirstNonPHI instead of once should be tolerable.

Would be good to document some place that all phi recipes appear before any non-phi recipe in VPBasicBlock, as in BasicBlock. (This assumption predates this patch.)

llvm/lib/Transforms/Vectorize/VPlan.h

1488

worth adding getFirstNonPHI() and have phis() use it?

1494

worth having both these recipes inherit from a common base class, which represents all phi recipes, resulting in a single isa<> here?

once some of these header phi recipes are converted into VPInstructions, this may be more complicated.

[fhahn]

Updates:

1. add comment about PHI node order to VPBasicBlock
2. use existing getFirstNonPhi() in phis()
3. add VPrecipeBase::isPhi(), use it in getFirstNonPhi

In D100101#2718833, @Ayal wrote:

Looks good to me!

This is aligned with BasicBlock::phis(), with a simpler implementation based on finding FirstNonPHI. Number of phi's is expected to be limited, so running twice until FirstNonPHI instead of once should be tolerable.

Would be good to document some place that all phi recipes appear before any non-phi recipe in VPBasicBlock, as in BasicBlock. (This assumption predates this patch.)

Thanks for taking a look! I added a sentence to the top-level comment for VPBasicBlock saying that all PHI-like recipes must come before non-phi recipes. I hope that's sufficient or were you thinking about a different place?

[fhahn]

llvm/lib/Transforms/Vectorize/VPlan.h

1488

There's already a getFirstNonPhi, which I originally missed. I updated the code to use it directly (and moved phis() to getFirstNonPhi.

1494

worth having both these recipes inherit from a common base class, which represents all phi recipes, resulting in a single isa<> here?

I'm not sure if there is much benefit at the moment, as I don't think the PHI-like recipes could really share much in the common base class?

I added a VPRecipeBase::isPhi() helper to directly check if a recipe is PHI-like, so we have a single place for such a check. I think that should give us the same convenience with respect to having a simple check for PHI-like recipes, but without having to add an extra level in the class hierarchy for now. WDYT?

[fhahn]

Rebased so this now applies directly on top of main.

[fhahn]

Ping :)

[Ayal]

This is fine, thanks!

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

 void InnerLoopVectorizer::fixCrossIterationPHIs(VPTransformState &State) {
   // In order to support recurrences we need to be able to vectorize Phi nodes.
   // Phi nodes have cycles, so we need to vectorize them in two stages. This is
   // stage #2: We now need to fix the recurrences by adding incoming edges to
   // the currently empty PHI nodes. At this point every instruction in the
   // original loop is widened to a vector form so we can use them to construct
   // the incoming edges.
   VPBasicBlock *Header = State.Plan->getEntry()->getEntryBasicBlock();
-  for (VPRecipeBase &R : *Header) {
-    if (isa<VPWidenIntOrFpInductionRecipe>(&R))
-      continue;
+  for (VPRecipeBase &R : Header->phis()) {
     VPWidenPHIRecipe *PhiR = dyn_cast<VPWidenPHIRecipe>(&R);
     if (!PhiR)
-      break;
-
+      continue;
     auto *OrigPhi = cast<PHINode>(PhiR->getUnderlyingValue());
     if (PhiR->getRecurrenceDescriptor()) {
       fixReduction(PhiR, State);
     } else if (Legal->isFirstOrderRecurrence(OrigPhi))
       fixFirstOrderRecurrence(OrigPhi, State);
   }
 }
 

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;
   }
 
   /// Returns true if the recipe may have side-effects.
   bool mayHaveSideEffects() const;
+
+  /// Returns true for PHI-like recipes.
+  bool isPhi() const {
+    return getVPDefID() == VPWidenIntOrFpInductionSC || getVPDefID() == VPWidenPHISC ||
+      getVPDefID() == VPPredInstPHISC || getVPDefID() == VPWidenCanonicalIVSC;
+  }
 };
 
 inline bool VPUser::classof(const VPDef *Def) {
   return Def->getVPDefID() == VPRecipeBase::VPInstructionSC ||
          Def->getVPDefID() == VPRecipeBase::VPWidenSC ||
          Def->getVPDefID() == VPRecipeBase::VPWidenCallSC ||
          Def->getVPDefID() == VPRecipeBase::VPWidenSelectSC ||
          Def->getVPDefID() == VPRecipeBase::VPWidenGEPSC ||
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
 #endif
 };
 
 /// VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph. It
 /// holds a sequence of zero or more VPRecipe's each representing a sequence of
-/// output IR instructions.
+/// output IR instructions. All PHI-like recipes must come before any non-PHI recipes.
 class VPBasicBlock : public VPBlockBase {
 public:
   using RecipeListTy = iplist<VPRecipeBase>;
 
 private:
   /// The VPRecipes held in the order of output instructions to generate.
   RecipeListTy Recipes;
 
public:
   inline const_reverse_iterator rend() const { return Recipes.rend(); }
 
   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(); }
 
   /// 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;
   }
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const VPBlockBase *V) {
     return V->getVPBlockID() == VPBlockBase::VPBasicBlockSC;
   }
 
   void insert(VPRecipeBase *Recipe, iterator InsertPt) {
public:
 
   /// The method which generates the output IR instructions that correspond to
   /// this VPBasicBlock, thereby "executing" the VPlan.
   void execute(struct VPTransformState *State) override;
 
   /// Return the position of the first non-phi node recipe in the block.
   iterator getFirstNonPhi();
 
+  /// Returns an iterator range over the PHI-like recipes in the block.
+  iterator_range<iterator> phis() {
+    return make_range(begin(), getFirstNonPhi());
+  }
+
   void dropAllReferences(VPValue *NewValue) override;
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   /// Print this VPBsicBlock to \p O, prefixing all lines with \p Indent. \p
   /// SlotTracker is used to print unnamed VPValue's using consequtive numbers.
   ///
   /// Note that the numbering is applied to the whole VPlan, so printing
   /// individual blocks is consistent with the whole VPlan printing.

llvm/lib/Transforms/Vectorize/VPlan.cpp

void VPBlockBase::deleteCFG(VPBlockBase *Entry) {
   SmallVector<VPBlockBase *, 8> Blocks(depth_first(Entry));
 
   for (VPBlockBase *Block : Blocks)
     delete Block;
 }
 
 VPBasicBlock::iterator VPBasicBlock::getFirstNonPhi() {
   iterator It = begin();
-  while (It != end() && (isa<VPWidenPHIRecipe>(&*It) ||
-                         isa<VPWidenIntOrFpInductionRecipe>(&*It) ||
-                         isa<VPPredInstPHIRecipe>(&*It) ||
-                         isa<VPWidenCanonicalIVRecipe>(&*It)))
+  while (It != end() && It->isPhi())
     It++;
   return It;
 }
 
 Value *VPTransformState::get(VPValue *Def, const VPIteration &Instance) {
   if (!Def->getDef())
     return Def->getLiveInIRValue();