[LV] Always create VPWidenCanonicalIVRecipe, optimize away later.

[fhahn]

Summary

This patch updates createBlockInMask to always generate
VPWidenCanonicalIVRecipe and adds a transform to optimize it away later,
if it is not needed.

This is a step towards breaking up VPWidenIntOrFpInductionRecipe and
explicitly distinguishing between vector phis and scalarizing.

Split off from D116123.

[Ayal]

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

332

Would be better to find VPWidenCanonicalIVRecipe by searching the users of getCanonicalIV(), after connecting the former to the latter, instead of looking for it in HeaderVPBB?

Would be better to search for an IV recipe (among HeaderVPBB->phis()) with an isCanonicalID and same type as widen canonical IV, thereby clearly proving their equivalence, instead of relying on OriginalCanonicalIV?

351

if (WidenOriginalIV && WidenNewIV) {

[fhahn]

Restructure code as suggested, added VPWidenIntOrFpInductionRecipe::isCanonical & use it instead of IR reference, check users of VPCanonicalIVPHIRecipe to find VPWidenCanonicalIVRecipe. This required making the def-use relation between those 2 explicit. Done in 3f2fb767e33a.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9197

Suffice to call it removeRedundantCanonicalIVs ?

llvm/lib/Transforms/Vectorize/VPlan.cpp

1256 ↗

(On Diff #399616)

Original thought was to leverage
static bool isCanonicalID(const InductionDescriptor &ID)

Can potentially specialize upon construction and have a recipe which needs no Start nor Step operands, as these are inherently known constants for such IV's?

llvm/lib/Transforms/Vectorize/VPlan.h

1081

It's also the scalar/element type of the new IV; how about getScalarType?

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

342

Suffice to traverse HeaderVPBB->phis()?

347

Comment should be updated.

349

Would slightly be better to compare with WidenNewIV->getOriginalType()/getScalarType()?

llvm/lib/Transforms/Vectorize/VPlanTransforms.h

50

Comment should be updated.

[fhahn]

Address latest comments, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9197

Updated, thanks!

llvm/lib/Transforms/Vectorize/VPlan.cpp

1256 ↗

(On Diff #399616)

Original thought was to leverage
static bool isCanonicalID(const InductionDescriptor &ID)

I think it would make sense to have VPWidenIntOrFpInductionRecipe::isCanonical() replace the existing use of isCanonicalID. I put up D117551.

Can potentially specialize upon construction and have a recipe which needs no Start nor Step operands, as these are inherently known constants for such IV's?

That would be an option, but I am not sure if the benefits are worth introducing another IV recipe, as we already have a number of them and checking whether it is a canonical induction is cheap & not needed in many places.

llvm/lib/Transforms/Vectorize/VPlan.h

1081

Adjusted the name, thanks!

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

342

Yep, updated!

347

Updated, thanks!

349

Updated, thanks!

llvm/lib/Transforms/Vectorize/VPlanTransforms.h

50

Updated to reference canonical IV.

[Ayal]

This is fine, thanks for accommodating, one last thought: does Canonical mean starting at zero, or possibly at EPResumeVal?

[fhahn]

In D117140#3250984, @Ayal wrote:

This is fine, thanks for accommodating, one last thought: does Canonical mean starting at zero, or possibly at EPResumeVal?

I think checking for zero a the moment should suffice, as EPResumeVal will only be set as start value just before epilogue VPlan execution. This should also match the current behavior before the change (and D117551 which now contains the addition if isCanonical). Once a single plan contains both vector loops we might need some changes in that direction though.

[Ayal]

In D117140#3251026, @fhahn wrote:

In D117140#3250984, @Ayal wrote:

This is fine, thanks for accommodating, one last thought: does Canonical mean starting at zero, or possibly at EPResumeVal?

I think checking for zero a the moment should suffice, as EPResumeVal will only be set as start value just before epilogue VPlan execution. This should also match the current behavior before the change (and D117551 which now contains the addition if isCanonical). Once a single plan contains both vector loops we might need some changes in that direction though.

Resetting start of canonicalIV to EPResumeVal just before epiloque VPlan execution might invalidate passes that relied on this value being zero, including removeRedundantCanonicalIVs()? A test would be good, either confirming or reassuring :-)

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

351

Perhaps suffice to

if (WidenOriginalIV && WidenOriginalIV->isCanonical() &&
    WidenOriginalIV->getScalarType() == WidenNewIV->getScalarType()) {
  WidenNewIV->replaceAllUsesWith(WidenOriginalIV);
  WidenNewIV->eraseFromParent();
  return;
}

llvm/lib/Transforms/Vectorize/VPlanTransforms.h

50

typo: "it exists."

[fhahn]

Address latest comments, thanks!

Resetting start of canonicalIV to EPResumeVal just before epiloque VPlan execution might invalidate passes that relied on this value being zero, including removeRedundantCanonicalIVs()? A test would be good, either confirming or reassuring :-)

I am not sure if it is possible to add a test that has epilogue vectorization and a VPWidenCanonicalIVRecipe. We only add VPWidenCanonicalIVRecipe when folding the tail. In that case, epilogue vectorization is disabled as there's no epilogue. But we should be able to add a relevant test for the stepvector/build-scalar-steps patches I think.

[fhahn]

Fix formatting.

[Ayal]

In D117140#3252232, @fhahn wrote:

Address latest comments, thanks!

Resetting start of canonicalIV to EPResumeVal just before epiloque VPlan execution might invalidate passes that relied on this value being zero, including removeRedundantCanonicalIVs()? A test would be good, either confirming or reassuring :-)

I am not sure if it is possible to add a test that has epilogue vectorization and a VPWidenCanonicalIVRecipe. We only add VPWidenCanonicalIVRecipe when folding the tail. In that case, epilogue vectorization is disabled as there's no epilogue. But we should be able to add a relevant test for the stepvector/build-scalar-steps patches I think.

OK, that's reassuring. Perhaps worth leaving behind a comment somewhere, or better - asserting when resetting start from zero to EPResumeVal that canonicalIV is used only by its Increment but not (potentially misused) by VPWidenCanonicalIVRecipe?

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

344

Above early-exit is now redundant.

[fhahn]

Remove unnecessary early exit.

In D117140#3251403, @Ayal wrote:

In D117140#3251026, @fhahn wrote:

In D117140#3250984, @Ayal wrote:

This is fine, thanks for accommodating, one last thought: does Canonical mean starting at zero, or possibly at EPResumeVal?

I think checking for zero a the moment should suffice, as EPResumeVal will only be set as start value just before epilogue VPlan execution. This should also match the current behavior before the change (and D117551 which now contains the addition if isCanonical). Once a single plan contains both vector loops we might need some changes in that direction though.

Resetting start of canonicalIV to EPResumeVal just before epiloque VPlan execution might invalidate passes that relied on this value being zero, including removeRedundantCanonicalIVs()? A test would be good, either confirming or reassuring :-)

Added an assert in 165e36bf180e.

[Ayal]

llvm/lib/Transforms/Vectorize/VPlan.h

1081

Ahh, if this VPWidenIntOrFpInductionRecipe also folds a Trunc, should getScalarType() return Trunc's type instead of IV's type?

[fhahn]

Update getScalarType to consider truncated IVs.

[fhahn]

llvm/lib/Transforms/Vectorize/VPlan.h

1081

Good spot! I updated the code. I don't think it is an issue at the moment, as widened canonical IV should always use the widest type, so there's no way to add a test IIUC.

[Ayal]

In D117140#3253999, @fhahn wrote:

Remove unnecessary early exit.

In D117140#3251403, @Ayal wrote:

In D117140#3251026, @fhahn wrote:

In D117140#3250984, @Ayal wrote:

This is fine, thanks for accommodating, one last thought: does Canonical mean starting at zero, or possibly at EPResumeVal?

I think checking for zero a the moment should suffice, as EPResumeVal will only be set as start value just before epilogue VPlan execution. This should also match the current behavior before the change (and D117551 which now contains the addition if isCanonical). Once a single plan contains both vector loops we might need some changes in that direction though.

Resetting start of canonicalIV to EPResumeVal just before epiloque VPlan execution might invalidate passes that relied on this value being zero, including removeRedundantCanonicalIVs()? A test would be good, either confirming or reassuring :-)

Added an assert in 165e36bf180e.

Thanks!
For epilog VPlan execution, the start of all IV's should be bumped according to EPResumeVal; perhaps better to model CanonicalIVStartValue as an abstract VPValue of VPlan similar to TripCount and BackedgeTakenCount, w/o claiming it is zero prematurely.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

if (OrigLoop->getHeader() == BB) {
 
     // Introduce the early-exit compare IV <= BTC to form header block mask.
     // This is used instead of IV < TC because TC may wrap, unlike BTC. Start by
     // constructing the desired canonical IV in the header block as its first
     // non-phi instructions.
     assert(CM.foldTailByMasking() && "must fold the tail");
     VPBasicBlock *HeaderVPBB = Plan->getEntry()->getEntryBasicBlock();
     auto NewInsertionPoint = HeaderVPBB->getFirstNonPhi();
-
-    VPValue *IV = nullptr;
-    if (Legal->getPrimaryInduction())
-      IV = Plan->getOrAddVPValue(Legal->getPrimaryInduction());
-    else {
-      auto *IVRecipe = new VPWidenCanonicalIVRecipe(Plan->getCanonicalIV());
-      HeaderVPBB->insert(IVRecipe, NewInsertionPoint);
-      IV = IVRecipe;
-    }
+    auto *IV = new VPWidenCanonicalIVRecipe(Plan->getCanonicalIV());
+    HeaderVPBB->insert(IV, HeaderVPBB->getFirstNonPhi());
 
     VPBuilder::InsertPointGuard Guard(Builder);
     Builder.setInsertPoint(HeaderVPBB, NewInsertionPoint);
     if (CM.TTI.emitGetActiveLaneMask()) {
       VPValue *TC = Plan->getOrCreateTripCount();
       BlockMask = Builder.createNaryOp(VPInstruction::ActiveLaneMask, {IV, TC});
     } else {
       VPValue *BTC = Plan->getOrCreateBackedgeTakenCount();
if (TargetRegion) {
       auto *SplitPred = SplitBlock->getSinglePredecessor();
 
       VPBlockUtils::disconnectBlocks(SplitPred, SplitBlock);
       VPBlockUtils::connectBlocks(SplitPred, SinkRegion);
       VPBlockUtils::connectBlocks(SinkRegion, SplitBlock);
     }
   }
 
+  VPlanTransforms::removeRedundantCanonicalIVs(*Plan);
   VPlanTransforms::removeRedundantInductionCasts(*Plan);
 
   // Now that sink-after is done, move induction recipes for optimized truncates
   // to the phi section of the header block.
   for (VPWidenIntOrFpInductionRecipe *Ind : InductionsToMove)
     Ind->moveBefore(*HeaderVPBB, HeaderVPBB->getFirstNonPhi());
 
   // Adjust the recipes for any inloop reductions.

llvm/lib/Transforms/Vectorize/VPlan.h

#endif
   }
 
   /// Returns the induction descriptor for the recipe.
   const InductionDescriptor &getInductionDescriptor() const { return IndDesc; }
 
   /// Returns true if the induction is canonical, i.e. starting at 0 and
   /// incremented by UF * VF (= the original IV is incremented by 1).
   bool isCanonical() const;
+
+  /// Returns the scalar type of the induction.
+  const Type *getScalarType() const {
+    const TruncInst *TruncI = getTruncInst();
+    return TruncI ? TruncI->getType() : IV->getType();
+  }
 };
 
 /// 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.
 class VPHeaderPHIRecipe : public VPRecipeBase, public VPValue {
 protected:
public:
   /// Generate the canonical scalar induction phi of the vector loop.
   void execute(VPTransformState &State) override;
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
 #endif
+
+  /// Returns the scalar type of the induction.
+  const Type *getScalarType() const {
+    return getOperand(0)->getLiveInIRValue()->getType();
+  }
 };
 
 /// A Recipe for widening the canonical induction variable of the vector loop.
 class VPWidenCanonicalIVRecipe : public VPRecipeBase, public VPValue {
 public:
   VPWidenCanonicalIVRecipe(VPCanonicalIVPHIRecipe *CanonicalIV)
       : VPRecipeBase(VPWidenCanonicalIVSC, {CanonicalIV}),
         VPValue(VPValue::VPVWidenCanonicalIVSC, nullptr, this) {}
 
   ~VPWidenCanonicalIVRecipe() override = default;
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const VPDef *D) {
     return D->getVPDefID() == VPRecipeBase::VPWidenCanonicalIVSC;
   }
 
+  /// Extra classof implementations to allow directly casting from VPUser ->
+  /// VPWidenCanonicalIVRecipe.
+  static inline bool classof(const VPUser *U) {
+    auto *R = dyn_cast<VPRecipeBase>(U);
+    return R && R->getVPDefID() == VPRecipeBase::VPWidenCanonicalIVSC;
+  }
+  static inline bool classof(const VPRecipeBase *R) {
+    return R->getVPDefID() == VPRecipeBase::VPWidenCanonicalIVSC;
+  }
+
   /// Generate a canonical vector induction variable of the vector loop, with
   /// start = {<Part*VF, Part*VF+1, ..., Part*VF+VF-1> for 0 <= Part < UF}, and
   /// step = <VF*UF, VF*UF, ..., VF*UF>.
   void execute(VPTransformState &State) override;
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
 #endif
+
+  /// Returns the scalar type of the induction.
+  const Type *getScalarType() const {
+    return cast<VPCanonicalIVPHIRecipe>(getOperand(0)->getDef())
+        ->getScalarType();
+  }
 };
 
 /// 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. All PHI-like recipes must come before any non-PHI recipes.
 class VPBasicBlock : public VPBlockBase {
 public:
   using RecipeListTy = iplist<VPRecipeBase>;

llvm/lib/Transforms/Vectorize/VPlanTransforms.h

struct VPlanTransforms {
 
   /// Remove redundant casts of inductions.
   ///
   /// Such redundant casts are casts of induction variables that can be ignored,
   /// because we already proved that the casted phi is equal to the uncasted phi
   /// in the vectorized loop. There is no need to vectorize the cast - the same
   /// value can be used for both the phi and casts in the vector loop.
   static void removeRedundantInductionCasts(VPlan &Plan);
+
+  /// Try to replace VPWidenCanonicalIVRecipes with a widened canonical IV
+  /// recipe, if it exists.
+  static void removeRedundantCanonicalIVs(VPlan &Plan);
 };
 
 } // namespace llvm
 
 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLANTRANSFORMS_H

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

for (Instruction *IRCast : reverse(Casts)) {
       FindMyCast = FoundUserCast->getVPSingleValue();
     }
   }
   for (auto &E : CastsToRemove) {
     E.first->getVPSingleValue()->replaceAllUsesWith(E.second);
     E.first->eraseFromParent();
   }
 }
+
+void VPlanTransforms::removeRedundantCanonicalIVs(VPlan &Plan) {
+  VPCanonicalIVPHIRecipe *CanonicalIV = Plan.getCanonicalIV();
+  VPWidenCanonicalIVRecipe *WidenNewIV = nullptr;
+  for (VPUser *U : CanonicalIV->users()) {
+    WidenNewIV = dyn_cast<VPWidenCanonicalIVRecipe>(U);
+    if (WidenNewIV)
+      break;
+  }
+
+  if (!WidenNewIV)
+    return;
+
+  VPBasicBlock *HeaderVPBB = Plan.getVectorLoopRegion()->getEntryBasicBlock();
+  for (VPRecipeBase &Phi : HeaderVPBB->phis()) {
+    auto *WidenOriginalIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
+
+    // If the induction recipe is canonical and the types match, use it
+    // directly.
+    if (WidenOriginalIV && WidenOriginalIV->isCanonical() &&
+        WidenOriginalIV->getScalarType() == WidenNewIV->getScalarType()) {
+      WidenNewIV->replaceAllUsesWith(WidenOriginalIV);
+      WidenNewIV->eraseFromParent();
+      return;
+    }
+  }
+}