[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

9210

Suffice to call it removeRedundantCanonicalIVs ?

llvm/lib/Transforms/Vectorize/VPlan.cpp

1256

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

1071

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

9210

Updated, thanks!

llvm/lib/Transforms/Vectorize/VPlan.cpp

1256

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

1071

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

1067

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

1067

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::removeRedundantVPWidenCanonicalIVRecipe(*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

 #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 start value of the induction.
   VPValue *getStartValue() { return getOperand(0); }
+  const VPValue *getStartValue() const { return getOperand(0); }
 
   /// Returns the first defined value as TruncInst, if it is one or nullptr
   /// otherwise.
   TruncInst *getTruncInst() {
     return dyn_cast_or_null<TruncInst>(getVPValue(0)->getUnderlyingValue());
   }
   const TruncInst *getTruncInst() const {
     return dyn_cast_or_null<TruncInst>(getVPValue(0)->getUnderlyingValue());
   }
 
   /// 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 type of the original IV.
+  const Type *getOriginalType() const { return 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 type of the original IV.
+  const Type *getOriginalType() 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,

llvm/lib/Transforms/Vectorize/VPlan.cpp

if (getTruncInst()) {
     O << "\\l\"";
     O << " +\n" << Indent << "\"  " << VPlanIngredient(IV) << "\\l\"";
     O << " +\n" << Indent << "\"  ";
     getVPValue(0)->printAsOperand(O, SlotTracker);
   } else
     O << " " << VPlanIngredient(IV);
 }
 
+bool VPWidenIntOrFpInductionRecipe::isCanonical() const {
+  auto *StartC = dyn_cast<ConstantInt>(getStartValue()->getLiveInIRValue());
+  auto *StepC = dyn_cast<SCEVConstant>(getInductionDescriptor().getStep());
+  return StartC && StartC->isZero() && StepC && StepC->isOne();
+}
+
 void VPWidenGEPRecipe::print(raw_ostream &O, const Twine &Indent,
                              VPSlotTracker &SlotTracker) const {
   O << Indent << "WIDEN-GEP ";
   O << (IsPtrLoopInvariant ? "Inv" : "Var");
   size_t IndicesNumber = IsIndexLoopInvariant.size();
   for (size_t I = 0; I < IndicesNumber; ++I)
     O << "[" << (IsIndexLoopInvariant[I] ? "Inv" : "Var") << "]";
 

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 the primary IV recipe, if it
+  /// exists.
+  static void removeRedundantVPWidenCanonicalIVRecipe(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::removeRedundantVPWidenCanonicalIVRecipe(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();
+  VPWidenIntOrFpInductionRecipe *WidenOriginalIV = nullptr;
+  for (VPRecipeBase &Phi : *HeaderVPBB) {
+    WidenOriginalIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
+    if (!WidenOriginalIV)
+      continue;
+
+    // If the induction recipe is for the primary induction use it directly.
+    if (WidenOriginalIV->isCanonical() &&
+        WidenOriginalIV->getOriginalType() == CanonicalIV->getOriginalType())
+      break;
+    WidenOriginalIV = nullptr;
+  }
+
+  if (WidenOriginalIV) {
+    WidenNewIV->replaceAllUsesWith(WidenOriginalIV);
+    WidenNewIV->eraseFromParent();
+  }
+}

llvm/lib/Transforms/Vectorize/VPlanValue.h

bool hasMoreThanOneUniqueUser() {
     while (Current != user_end() && *user_begin() == *Current)
       Current++;
     return Current != user_end();
   }
 
   void replaceAllUsesWith(VPValue *New);
 
   VPDef *getDef() { return Def; }
+  const VPDef *getDef() const { return Def; }
 
   /// Returns the underlying IR value, if this VPValue is defined outside the
   /// scope of VPlan. Returns nullptr if the VPValue is defined by a VPDef
   /// inside a VPlan.
   Value *getLiveInIRValue() {
     assert(!getDef() &&
            "VPValue is not a live-in; it is defined by a VPDef inside a VPlan");
     return getUnderlyingValue();
   }
+  const Value *getLiveInIRValue() const {
+    assert(!getDef() &&
+           "VPValue is not a live-in; it is defined by a VPDef inside a VPlan");
+    return getUnderlyingValue();
+  }
 };
 
 typedef DenseMap<Value *, VPValue *> Value2VPValueTy;
 typedef DenseMap<VPValue *, Value *> VPValue2ValueTy;
 
 raw_ostream &operator<<(raw_ostream &OS, const VPValue &V);
 
 /// This class augments VPValue with operands which provide the inverse def-use