[VPlan] Record whether scalar IVs are need in induction recipe. (NFC)

[fhahn]

Summary

This explicitly records whether a scalar IV is needed in the
VPWidenIntOrFpInductionRecipe, to remove a dependence on the cost-model
during its ::execute.

It will also be used in D116123 to determine if a vector phi will be
generated.

[fhahn]

Rename to needsVectorIV

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

2588–2589

While we're here, comment above is out of sync with code below.

8605

!NeedsScalarIV || !NeedsScalarIVOnly - suffice to have only !NeedsScalarIVOnly to feed NeedsVectorIV ?

Refactor the code that constructs a VPWidenIntOrFpInductionRecipe to be used by both tryToOptimizeInduction[PHI,Truncate]?

[fhahn]

Address latest comments, thanks! I unified the VPWidenIntOrFpInductionRecipe* creating in a single helper. Comment also updated.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

2588–2589

Updated, thanks!

8605

Good point, thanks! Looks like !NeedsScalarIVOnly is indeed sufficient. Updated and also moved to common createInductionRecipe helper!

[Ayal]

This is fine, couple of final nits; thanks for accommodating!

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

2590

Suffice to ask if !Def->needsScalarIV() as that implies Def->needsVectorIV() - they cannot both be false if Def is not dead - but being explicit is clearer?

2597

Suffice to ask if Def->needsVectorIV() as we already know that Def->needsScalarIV() here - but being explicit is clearer?

8527

"create[Widen]InductionRecipe" ?

8549

Nice to see the above encapsulated here!

[fhahn]

Address latest comments, thanks! I am planning to land this soon.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

protected:
   /// node, and \p Step is the loop-invariant step. If \p EntryVal is a
   /// truncate instruction, instead of widening the original IV, we widen a
   /// version of the IV truncated to \p EntryVal's type.
   void createVectorIntOrFpInductionPHI(const InductionDescriptor &II,
                                        Value *Step, Value *Start,
                                        Instruction *EntryVal, VPValue *Def,
                                        VPTransformState &State);
 
-  /// Returns true if an instruction \p I should be scalarized instead of
-  /// vectorized for the chosen vectorization factor.
-  bool shouldScalarizeInstruction(Instruction *I) const;
-
-  /// Returns true if we should generate a scalar version of \p IV.
-  bool needsScalarInduction(Instruction *IV) const;
-
   /// Returns (and creates if needed) the original loop trip count.
   Value *getOrCreateTripCount(Loop *NewLoop);
 
   /// Returns (and creates if needed) the trip count of the widened loop.
   Value *getOrCreateVectorTripCount(Loop *NewLoop);
 
   /// Returns a bitcasted value to the requested vector type.
   /// Also handles bitcasts of vector<float> <-> vector<pointer> types.
void InnerLoopVectorizer::createVectorIntOrFpInductionPHI(
   auto *Br = cast<BranchInst>(LoopVectorLatch->getTerminator());
   LastInduction->moveBefore(Br);
   LastInduction->setName("vec.ind.next");
 
   VecInd->addIncoming(SteppedStart, LoopVectorPreHeader);
   VecInd->addIncoming(LastInduction, LoopVectorLatch);
 }
 
-bool InnerLoopVectorizer::shouldScalarizeInstruction(Instruction *I) const {
-  return Cost->isScalarAfterVectorization(I, VF) ||
-         Cost->isProfitableToScalarize(I, VF);
-}
-
-bool InnerLoopVectorizer::needsScalarInduction(Instruction *IV) const {
-  if (shouldScalarizeInstruction(IV))
-    return true;
-  auto isScalarInst = [&](User *U) -> bool {
-    auto *I = cast<Instruction>(U);
-    return (OrigLoop->contains(I) && shouldScalarizeInstruction(I));
-  };
-  return llvm::any_of(IV->users(), isScalarInst);
-}
-
 void InnerLoopVectorizer::widenIntOrFpInduction(
     PHINode *IV, VPWidenIntOrFpInductionRecipe *Def, VPTransformState &State,
     Value *CanonicalIV) {
   Value *Start = Def->getStartValue()->getLiveInIRValue();
   const InductionDescriptor &ID = Def->getInductionDescriptor();
   TruncInst *Trunc = Def->getTruncInst();
   IRBuilder<> &Builder = State.Builder;
   assert(IV->getType() == ID.getStartValue()->getType() && "Types must match");
for (unsigned Part = 0; Part < UF; ++Part) {
         addMetadata(EntryPart, Trunc);
       }
     }
     return;
   }
 
   // Determine if we want a scalar version of the induction variable. This is
   // true if the induction variable itself is not widened, or if it has at
   // least one user in the loop that is not widened.
-  auto NeedsScalarIV = needsScalarInduction(EntryVal);
-  if (!NeedsScalarIV) {
+  if (!Def->needsScalarIV()) {
     createVectorIntOrFpInductionPHI(ID, Step, Start, EntryVal, Def, State);
     return;
   }
 
   // Try to create a new independent vector induction variable. If we can't
   // create the phi node, we will splat the scalar induction variable in each
   // loop iteration.
-  if (!shouldScalarizeInstruction(EntryVal)) {
+  if (!Def->needsScalarIVOnly()) {
     createVectorIntOrFpInductionPHI(ID, Step, Start, EntryVal, Def, State);
     Value *ScalarIV = CreateScalarIV(Step);
     // Create scalar steps that can be used by instructions we will later
     // scalarize. Note that the addition of the scalar steps will not increase
     // the number of instructions in the loop in the common case prior to
     // InstCombine. We will be trading one vector extract for each scalar step.
     buildScalarSteps(ScalarIV, Step, EntryVal, ID, Def, State);
     return;
if (LoadInst *Load = dyn_cast<LoadInst>(I))
     return new VPWidenMemoryInstructionRecipe(*Load, Operands[0], Mask,
                                               Consecutive, Reverse);
 
   StoreInst *Store = cast<StoreInst>(I);
   return new VPWidenMemoryInstructionRecipe(*Store, Operands[1], Operands[0],
                                             Mask, Consecutive, Reverse);
 }
 
-VPWidenIntOrFpInductionRecipe *
-VPRecipeBuilder::tryToOptimizeInductionPHI(PHINode *Phi,
-                                           ArrayRef<VPValue *> Operands) const {
+/// Returns true if an instruction \p I should be scalarized instead of
+/// vectorized for the chosen vectorization factor.
+static bool shouldScalarizeInstruction(LoopVectorizationCostModel &Cost,
+                                       Instruction *I, ElementCount VF) {
+  return Cost.isScalarAfterVectorization(I, VF) ||
+         Cost.isProfitableToScalarize(I, VF);
+}
+
+/// Returns true if we should generate a scalar version of \p IV.
+static bool needsScalarInduction(LoopVectorizationCostModel &Cost,
+                                 Loop &OrigLoop, Instruction *IV,
+                                 ElementCount VF) {
+  if (shouldScalarizeInstruction(Cost, IV, VF))
+    return true;
+  auto isScalarInst = [&Cost, &OrigLoop, VF](User *U) -> bool {
+    auto *I = cast<Instruction>(U);
+    return OrigLoop.contains(I) && shouldScalarizeInstruction(Cost, I, VF);
+  };
+  return any_of(IV->users(), isScalarInst);
+}
+
+VPWidenIntOrFpInductionRecipe *VPRecipeBuilder::tryToOptimizeInductionPHI(
+    PHINode *Phi, ArrayRef<VPValue *> Operands, VFRange &Range) const {
+
   // Check if this is an integer or fp induction. If so, build the recipe that
   // produces its scalar and vector values.
   if (auto *II = Legal->getIntOrFpInductionDescriptor(Phi)) {
+    bool NeedsScalarIV = LoopVectorizationPlanner::getDecisionAndClampRange(
+        [&](ElementCount VF) {
+          return needsScalarInduction(CM, *OrigLoop, Phi, VF);
+        },
+        Range);
+    bool NeedsScalarIVOnly = LoopVectorizationPlanner::getDecisionAndClampRange(
+        [&](ElementCount VF) {
+          return shouldScalarizeInstruction(CM, Phi, VF);
+        },
+        Range);
     assert(II->getStartValue() ==
            Phi->getIncomingValueForBlock(OrigLoop->getLoopPreheader()));
-    return new VPWidenIntOrFpInductionRecipe(Phi, Operands[0], *II);
+    return new VPWidenIntOrFpInductionRecipe(Phi, Operands[0], *II,
+                                             NeedsScalarIV, NeedsScalarIVOnly);
   }
 
   return nullptr;
 }
 
 VPWidenIntOrFpInductionRecipe *VPRecipeBuilder::tryToOptimizeInductionTruncate(
     TruncInst *I, ArrayRef<VPValue *> Operands, VFRange &Range,
     VPlan &Plan) const {
return [=](ElementCount VF) -> bool {
       return CM.isOptimizableIVTruncate(K, VF);
     };
   };
 
   if (LoopVectorizationPlanner::getDecisionAndClampRange(
           isOptimizableIVTruncate(I), Range)) {
 
     auto *Phi = cast<PHINode>(I->getOperand(0));
+    bool NeedsScalarIV = LoopVectorizationPlanner::getDecisionAndClampRange(
+        [&](ElementCount VF) {
+          return needsScalarInduction(CM, *OrigLoop, I, VF);
+        },
+        Range);
+    bool NeedsScalarIVOnly = LoopVectorizationPlanner::getDecisionAndClampRange(
+        [&](ElementCount VF) { return shouldScalarizeInstruction(CM, I, VF); },
+        Range);
+
     const InductionDescriptor &II = *Legal->getIntOrFpInductionDescriptor(Phi);
     VPValue *Start = Plan.getOrAddVPValue(II.getStartValue());
-    return new VPWidenIntOrFpInductionRecipe(Phi, Start, II, I);
+    return new VPWidenIntOrFpInductionRecipe(Phi, Start, II, I, NeedsScalarIV,
+                                             NeedsScalarIVOnly);
   }
   return nullptr;
 }
 
 VPRecipeOrVPValueTy VPRecipeBuilder::tryToBlend(PHINode *Phi,
                                                 ArrayRef<VPValue *> Operands,
                                                 VPlanPtr &Plan) {
   // If all incoming values are equal, the incoming VPValue can be used directly
VPRecipeBuilder::tryToCreateWidenRecipe(Instruction *Instr,
 
   if (isa<LoadInst>(Instr) || isa<StoreInst>(Instr))
     return toVPRecipeResult(tryToWidenMemory(Instr, Operands, Range, Plan));
 
   VPRecipeBase *Recipe;
   if (auto Phi = dyn_cast<PHINode>(Instr)) {
     if (Phi->getParent() != OrigLoop->getHeader())
       return tryToBlend(Phi, Operands, Plan);
-    if ((Recipe = tryToOptimizeInductionPHI(Phi, Operands)))
+    if ((Recipe = tryToOptimizeInductionPHI(Phi, Operands, Range)))
       return toVPRecipeResult(Recipe);
 
     VPHeaderPHIRecipe *PhiRecipe = nullptr;
     if (Legal->isReductionVariable(Phi) || Legal->isFirstOrderRecurrence(Phi)) {
       VPValue *StartV = Operands[0];
       if (Legal->isReductionVariable(Phi)) {
         const RecurrenceDescriptor &RdxDesc =
             Legal->getReductionVars().find(Phi)->second;

llvm/lib/Transforms/Vectorize/VPRecipeBuilder.h

class VPRecipeBuilder {
   /// Range.Start and potentially masked. Such instructions are handled by a
   /// recipe that takes an additional VPInstruction for the mask.
   VPRecipeBase *tryToWidenMemory(Instruction *I, ArrayRef<VPValue *> Operands,
                                  VFRange &Range, VPlanPtr &Plan);
 
   /// Check if an induction recipe should be constructed for \I. If so build and
   /// return it. If not, return null.
   VPWidenIntOrFpInductionRecipe *
-  tryToOptimizeInductionPHI(PHINode *Phi, ArrayRef<VPValue *> Operands) const;
+  tryToOptimizeInductionPHI(PHINode *Phi, ArrayRef<VPValue *> Operands,
+                            VFRange &Range) const;
 
   /// Optimize the special case where the operand of \p I is a constant integer
   /// induction variable.
   VPWidenIntOrFpInductionRecipe *
   tryToOptimizeInductionTruncate(TruncInst *I, ArrayRef<VPValue *> Operands,
                                  VFRange &Range, VPlan &Plan) const;
 
   /// Handle non-loop phi nodes. Return a VPValue, if all incoming values match

llvm/lib/Transforms/Vectorize/VPlan.h

 #endif
 };
 
 /// A recipe for handling phi nodes of integer and floating-point inductions,
 /// producing their vector and scalar values.
 class VPWidenIntOrFpInductionRecipe : public VPRecipeBase, public VPValue {
   PHINode *IV;
   const InductionDescriptor &IndDesc;
+  bool NeedsScalarIV;
+  bool NeedsScalarIVOnly;
 
 public:
   VPWidenIntOrFpInductionRecipe(PHINode *IV, VPValue *Start,
-                                const InductionDescriptor &IndDesc)
+                                const InductionDescriptor &IndDesc,
+                                bool NeedsScalarIV, bool NeedsScalarIVOnly)
       : VPRecipeBase(VPWidenIntOrFpInductionSC, {Start}), VPValue(IV, this),
-        IV(IV), IndDesc(IndDesc) {}
+        IV(IV), IndDesc(IndDesc), NeedsScalarIV(NeedsScalarIV),
+        NeedsScalarIVOnly(NeedsScalarIVOnly) {}
 
   VPWidenIntOrFpInductionRecipe(PHINode *IV, VPValue *Start,
                                 const InductionDescriptor &IndDesc,
-                                TruncInst *Trunc)
+                                TruncInst *Trunc, bool NeedsScalarIV,
+                                bool NeedsScalarIVOnly)
       : VPRecipeBase(VPWidenIntOrFpInductionSC, {Start}), VPValue(Trunc, this),
-        IV(IV), IndDesc(IndDesc) {}
+        IV(IV), IndDesc(IndDesc), NeedsScalarIV(NeedsScalarIV),
+        NeedsScalarIVOnly(NeedsScalarIVOnly) {}
 
   ~VPWidenIntOrFpInductionRecipe() override = default;
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const VPDef *D) {
     return D->getVPDefID() == VPRecipeBase::VPWidenIntOrFpInductionSC;
   }
 
#endif
   /// 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();
   }
+
+  bool needsScalarIV() const { return NeedsScalarIV; }
+  bool needsScalarIVOnly() const { return NeedsScalarIVOnly; }
 };
 
 /// 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:

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

for (VPRecipeBase &Ingredient : llvm::make_early_inc_range(*VPBB)) {
         continue;
       }
 
       VPRecipeBase *NewRecipe = nullptr;
       if (auto *VPPhi = dyn_cast<VPWidenPHIRecipe>(&Ingredient)) {
         auto *Phi = cast<PHINode>(VPPhi->getUnderlyingValue());
         if (const auto *II = GetIntOrFpInductionDescriptor(Phi)) {
           VPValue *Start = Plan->getOrAddVPValue(II->getStartValue());
-          NewRecipe = new VPWidenIntOrFpInductionRecipe(Phi, Start, *II);
+          NewRecipe =
+              new VPWidenIntOrFpInductionRecipe(Phi, Start, *II, false, false);
         } else {
           Plan->addVPValue(Phi, VPPhi);
           continue;
         }
       } else {
         assert(isa<VPInstruction>(&Ingredient) &&
                "only VPInstructions expected here");
         assert(!isa<PHINode>(Inst) && "phis should be handled above");