[VPlan] VPWidenIntOrFpInductionRecipe inherits from VPHeaderPHIRecipe

[michaelmaitland]

Summary

VPWidenIntOrFpInductionRecipe inherits from VPHeaderPHIRecipe since this recipe is phi like and only gets placed in vector header vp basic block.

[michaelmaitland]

Since VPWidenIntOrFpInductionRecipe exists is phi like and in the
header, but isnt a VPCSAHeaderPHIRecipe, I fix the verification check.
I think a isHeaderPhi function where recipes can report if they are
header phi like might be nice in the future.

[michaelmaitland]

Fixing syntax error from last update

[michaelmaitland]

Remove the ! that I incorrectly placed in one of the checks

[michaelmaitland]

Add assert before casting.

[michaelmaitland]

@fhahn is there a reason why VPWidenIntOrFpInductionRecipe does not extend VPHeaderPHIRecipe? That might be a better solution than this one.

[michaelmaitland]

In D144125#4133014, @michaelmaitland wrote:

@fhahn is there a reason why VPWidenIntOrFpInductionRecipe does not extend VPHeaderPHIRecipe? That might be a better solution than this one.

To respond to my own question:

I imagine VPWidenIntOrFpInductionRecipe does not extend VPHeaderPHIRecipe because if its changed to derive VPHeaderPHIRecipe, the PHI is the only one that can define this VPValue, even though there are two constructors which would like to set different underlying values for this VPValue:

1. IV defines this VPValue
2. Trunc defines this VPValue

An additional reason why it does not extend is:
> VPWidenIntOrFPInductionRecipe are not in the phi section of the header block for truncates of induction variables. Those recipes are moved to the phi section of the header block after applying SinkAfter, which relies on the original position of the trunc.

Therefore, I prefer the proposed solution.

[michaelmaitland]

Instead of using multiple isa checks in the same guard (and those same checks being duplicated across multiple ifs), move into utils method. Also move isPhi out of VPRecipeBase to reduce class bloat.

[michaelmaitland]

Update missed isHeaderPhi check

[fhahn]

Thanks for the patch.

VPWidenIntOrFPInductionRecipe are not in the phi section of the header block for truncates of induction variables. Those recipes are moved to the phi section of the header block after applying SinkAfter, which relies on the original position of the trunc.

I am not sure if this is still true, we should move them to the header at construction time. If so, It would be better to VPWidenIntOrFpInductionRecipe inherit from VPHeaderPHIRecipe, unless that causes any other issues. They have the same base classes, so that should be fine.

[michaelmaitland]

In D144125#4142196, @fhahn wrote:

Thanks for the patch.

VPWidenIntOrFPInductionRecipe are not in the phi section of the header block for truncates of induction variables. Those recipes are moved to the phi section of the header block after applying SinkAfter, which relies on the original position of the trunc.

I am not sure if this is still true, we should move them to the header at construction time. If so, It would be better to VPWidenIntOrFpInductionRecipe inherit from VPHeaderPHIRecipe, unless that causes any other issues. They have the same base classes, so that should be fine.

I just saw that D142589 landed which removes the fact that VPWidenIntOrFpInductionRecipe are not in the header block for truncates of induction variables. So I think you are right that this is no longer a concern.

However, it is still the case the VPHeaderPHIRecipe only accepts PHINodes as its underlying value, but VPWidenIntOrFpInductionRecipe uses either PHINode or TruncInst as an underlying value. I see two approaches forward:

1. Modify VPHeaderPHIRecipe to accept any Instruction as its underlying value.
2. Only use PHINode as underlying value for VPWidenIntOrFpInductionRecipe.

I prefer option 1, as the only real change required is for the underlying instruction of a VPHeaderPHIRecipe to change from PHINode -> Instruction. Option 2 is more involved since we're currently creating two VPWidenIntOrFpInductionRecipe (one for the phi and one for the trunc), but we would need to only create one (since one recipe per underlying IR is permitted) and update the single recipe with the trunc information when we process the trunc as well as replace uses of the trunc with this recipe.

But I think also boils down to what does it mean to be a "phi-like" recipe. Does it mean that the input IR is phi like? Does it mean that the output IR is phi like? Do both need to be phi like? I think if we are okay with it meaning the output IR is phi like, then option 1 is acceptable. If we are okay with this definition of phi-like, then we are able to have phi-like VPInstructions (which do not have any input IR) in the future.

I have updated this patch with approach 1.

[michaelmaitland]

Remove stacked commit from revision https://reviews.llvm.org/D144125

[fhahn]

Thanks for the update! For the phi-like terminology, what matter is whether the recipe merges incoming values from different blocks.

After changing VPWidenIntOrFpInductionRecipe, are the other changes still needed?

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

10470 ↗

(On Diff #499266)

that should not be needed I think, cast asserts that the argument isa VPHeaderPHIRecipe.

[fhahn]

llvm/lib/Transforms/Vectorize/VPlan.h

1186

Could you make sure that the code movement preserves the original code? I didn't check all lines, but it looks like the original code had a newline before here.

[michaelmaitland]

Remove unncessary assert and fix removal of blank line.

[michaelmaitland]

In D144125#4150975, @fhahn wrote:

After changing VPWidenIntOrFpInductionRecipe, are the other changes still needed?

I think this change reduces class bloat (since not all recipes are phi like, header phi like, or generate backedge). It also makes it so we only use RecipeTy in classof and uses isa to determine whether something isPhi.

I have some changes I plan to upstream in the near future that I think will give these util functions an even stronger justification for existing. If you don't think that the justifications i give are strong enough now, I am happy to remove them from this patch and include them in the future patch I mentioned.

[michaelmaitland]

Remove another unnecessary assert

[fhahn]

In D144125#4151066, @michaelmaitland wrote:

In D144125#4150975, @fhahn wrote:

After changing VPWidenIntOrFpInductionRecipe, are the other changes still needed?

I think this change reduces class bloat (since not all recipes are phi like, header phi like, or generate backedge). It also makes it so we only use RecipeTy in classof and uses isa to determine whether something isPhi.

I have some changes I plan to upstream in the near future that I think will give these util functions an even stronger justification for existing. If you don't think that the justifications i give are strong enough now, I am happy to remove them from this patch and include them in the future patch I mentioned.

Usually we try to keep unrelated changes as separate patches, if possible. It seems like fixing the inheritance can be done on its own and the isPhi changes can be done & discussed separately from that issue.

[michaelmaitland]

Remove Util functions

[fhahn]

LGTM, thanks!

[Ayal]

This change makes a lot of sense, except for getBackedgeValue() - see comment.

llvm/lib/Transforms/Vectorize/VPlan.h

1219–1220

Now that VPWidenIntOrFpInductionRecipe inherits from VPHeaderPHIRecipe, it also inherits getBackedgeValue(), which should return a VPValue defined by some recipe - getBackedgeRecipe() - inside the loop. The default returns getOperand(1). However, VPWidenIntOrFpInductionRecipe has no such VPValue nor recipe to return because it takes care of generating the corresponding IR code only during execution. Better override getBackedgeValue() and getBackedgeRecipe(), asserting they are unreachable/never called?
(Step which here serves as operand 1 instead is a value defined by a recipe in the loop preheader or constant - not a recipe.)

1224–1229

nit: these should now be one liners.

[michaelmaitland]

llvm/lib/Transforms/Vectorize/VPlan.h

1219–1220

I'm happy to add the overridden methods with unreachables in them for now. However, I think in the future it would be nice if a recipe extends another recipe, all operands of the base recipe must exist and be at the same index in the parent recipe. If not all derived versions of HeaderPHIRecipes have backedge values and recipes, then it should not belong in the base class.

[michaelmaitland]

Fix getBackedgeRecipe and getBackedgeValue

[Ayal]

llvm/lib/Transforms/Vectorize/VPlan.h

1219–1220

Agreed. This calls for a refactoring of VPWidenIntOrFpInductionRecipe, which will hopefully simplify its execute() to avoid inserting IR code in multiple points. Also calls for checking other derivatives of HeaderPHIRecipe, including VPWidenPointerInductionRecipe. Worth leaving behind a TODO to clean-up them unreachables?

[michaelmaitland]

Leave TODO to clean up unreachables.

llvm/lib/Transforms/Vectorize/VPlan.h

public:
   static inline bool classof(const VPUser *U) {
     return U->getVPUserID() == VPUser::VPUserID::Recipe;
   }
 
   /// Returns true if the recipe may have side-effects.
   bool mayHaveSideEffects() const;
 
   /// Returns true for PHI-like recipes.
-  bool isPhi() const {
-    return getVPDefID() >= VPFirstPHISC && getVPDefID() <= VPLastPHISC;
-  }
+  virtual bool isPhi() const { return false; }
 
   /// Returns true if the recipe may read from memory.
   bool mayReadFromMemory() const;
 
   /// Returns true if the recipe may write to memory.
   bool mayWriteToMemory() const;
 
   /// Returns true if the recipe may read from or write to memory.
#endif
   /// Returns the scalar type of the induction.
   const Type *getScalarType() const {
     const TruncInst *TruncI = getTruncInst();
     return TruncI ? TruncI->getType() : IV->getType();
   }
 
   /// Returns true if a vector phi needs to be created for the induction.
   bool needsVectorIV() const { return NeedsVectorIV; }
+
+  bool isPhi() const override { return true; }
 };
 
 /// A pure virtual base class for all recipes modeling header phis, including
 /// phis for first order recurrences, pointer inductions and reductions. The
 /// start value is the first operand of the recipe and the incoming value from
 /// the backedge is the second operand.
 ///
 /// Inductions are modeled using the following sub-classes:
protected:
   }
 
 public:
   ~VPHeaderPHIRecipe() override = default;
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const VPRecipeBase *B) {
     return B->getVPDefID() >= VPDef::VPFirstHeaderPHISC &&
-           B->getVPDefID() <= VPDef::VPLastPHISC;
+           B->getVPDefID() <= VPDef::VPLastHeaderPHISC;
   }
   static inline bool classof(const VPValue *V) {
     auto *B = V->getDefiningRecipe();
     return B && B->getVPDefID() >= VPRecipeBase::VPFirstHeaderPHISC &&
-           B->getVPDefID() <= VPRecipeBase::VPLastPHISC;
+           B->getVPDefID() <= VPRecipeBase::VPLastHeaderPHISC;
   }
 
   /// Generate the phi nodes.
   void execute(VPTransformState &State) override = 0;
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
VPValue *getBackedgeValue() {
     return getOperand(1);
   }
 
   /// Returns the backedge value as a recipe. The backedge value is guaranteed
   /// to be a recipe.
   VPRecipeBase &getBackedgeRecipe() {
     return *getBackedgeValue()->getDefiningRecipe();
   }
+
+  bool isPhi() const override { return true; }
 };
 
 class VPWidenPointerInductionRecipe : public VPHeaderPHIRecipe {
   const InductionDescriptor &IndDesc;
 
   bool IsScalarAfterVectorization;
 
 public:
   /// Create a new VPWidenPointerInductionRecipe for \p Phi with start value \p
   /// Start.
   VPWidenPointerInductionRecipe(PHINode *Phi, VPValue *Start, VPValue *Step,
                                 const InductionDescriptor &IndDesc,
                                 bool IsScalarAfterVectorization)
       : VPHeaderPHIRecipe(VPDef::VPWidenPointerInductionSC, Phi),
         IndDesc(IndDesc),
         IsScalarAfterVectorization(IsScalarAfterVectorization) {
     addOperand(Start);
     addOperand(Step);
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
 #endif
 };
 
 /// A recipe for handling header phis that are widened in the vector loop.
 /// In the VPlan native path, all incoming VPValues & VPBasicBlock pairs are
 /// managed in the recipe directly.
 class VPWidenPHIRecipe : public VPHeaderPHIRecipe {
   /// List of incoming blocks. Only used in the VPlan native path.
   SmallVector<VPBasicBlock *, 2> IncomingBlocks;
 
 public:
   /// Create a new VPWidenPHIRecipe for \p Phi with start value \p Start.
   VPWidenPHIRecipe(PHINode *Phi, VPValue *Start = nullptr)
       : VPHeaderPHIRecipe(VPDef::VPWidenPHISC, Phi) {
     if (Start)
       addOperand(Start);
   }
 
   ~VPWidenPHIRecipe() override = default;
 
   VP_CLASSOF_IMPL(VPDef::VPWidenPHISC)
 
   /// Generate the phi/select nodes.
   void execute(VPTransformState &State) override;
#endif
   bool onlyFirstLaneUsed(const VPValue *Op) const override {
     assert(is_contained(operands(), Op) &&
            "Op must be an operand of the recipe");
     // Recursing through Blend recipes only, must terminate at header phi's the
     // latest.
     return all_of(users(),
                   [this](VPUser *U) { return U->onlyFirstLaneUsed(this); });
   }
+
+  bool isPhi() const override { return true; }
 };
 
 /// VPInterleaveRecipe is a recipe for transforming an interleave group of load
 /// or stores into one wide load/store and shuffles. The first operand of a
 /// VPInterleave recipe is the address, followed by the stored values, followed
 /// by an optional mask.
 class VPInterleaveRecipe : public VPRecipeBase {
   const InterleaveGroup<Instruction> *IG;

 #endif
 
   /// Returns true if the recipe uses scalars of operand \p Op.
   bool usesScalars(const VPValue *Op) const override {
     assert(is_contained(operands(), Op) &&
            "Op must be an operand of the recipe");
     return true;
   }
+
+  bool isPhi() const override { return true; }
 };
 
 /// A Recipe for widening load/store operations.
 /// The recipe uses the following VPValues:
 /// - For load: Address, optional mask
 /// - For store: Address, stored value, optional mask
 /// TODO: We currently execute only per-part unless a specific instance is
 /// provided.

llvm/lib/Transforms/Vectorize/VPlanValue.h

using VPRecipeTy = enum {
     VPReplicateSC,
     VPScalarIVStepsSC,
     VPWidenCallSC,
     VPWidenCanonicalIVSC,
     VPWidenGEPSC,
     VPWidenMemoryInstructionSC,
     VPWidenSC,
     VPWidenSelectSC,
-
-    // Phi-like recipes. Need to be kept together.
     VPBlendSC,
     VPPredInstPHISC,
-    // Header-phi recipes. Need to be kept together.
+    VPWidenIntOrFpInductionSC,
+    // START: SubclassID for recipes that inherit VPHeaderPHIRecipe.
+    // VPHeaderPHIRecipe need to be kept together.
     VPCanonicalIVPHISC,
     VPActiveLaneMaskPHISC,
     VPFirstOrderRecurrencePHISC,
     VPWidenPHISC,
-    VPWidenIntOrFpInductionSC,
     VPWidenPointerInductionSC,
     VPReductionPHISC,
-    VPFirstPHISC = VPBlendSC,
+    // END: SubclassID for recipes that inherit VPHeaderPHIRecipe
     VPFirstHeaderPHISC = VPCanonicalIVPHISC,
-    VPLastPHISC = VPReductionPHISC,
+    VPLastHeaderPHISC = VPReductionPHISC,
   };
 
   VPDef(const unsigned char SC) : SubclassID(SC) {}
 
   virtual ~VPDef() {
     for (VPValue *D : make_early_inc_range(DefinedValues)) {
       assert(D->Def == this &&
              "all defined VPValues should point to the containing VPDef");

llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp

static bool verifyPhiRecipes(const VPBasicBlock *VPBB) {
   unsigned NumActiveLaneMaskPhiRecipes = 0;
   const VPRegionBlock *ParentR = VPBB->getParent();
   bool IsHeaderVPBB = ParentR && !ParentR->isReplicator() &&
                       ParentR->getEntryBasicBlock() == VPBB;
   while (RecipeI != End && RecipeI->isPhi()) {
     if (isa<VPActiveLaneMaskPHIRecipe>(RecipeI))
       NumActiveLaneMaskPhiRecipes++;
 
-    if (IsHeaderVPBB && !isa<VPHeaderPHIRecipe>(*RecipeI)) {
+    if (IsHeaderVPBB && !(isa<VPHeaderPHIRecipe>(*RecipeI) ||
+                          isa<VPWidenIntOrFpInductionRecipe>(*RecipeI))) {
       errs() << "Found non-header PHI recipe in header VPBB";
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
       errs() << ": ";
       RecipeI->dump();
 #endif
       return false;
     }
 
-    if (!IsHeaderVPBB && isa<VPHeaderPHIRecipe>(*RecipeI)) {
+    if (!IsHeaderVPBB && !(isa<VPHeaderPHIRecipe>(*RecipeI) ||
+                           isa<VPWidenIntOrFpInductionRecipe>(*RecipeI))) {
       errs() << "Found header PHI recipe in non-header VPBB";
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
       errs() << ": ";
       RecipeI->dump();
 #endif
       return false;
     }