[VPlan] Check VPValue step in isCanonical (NFCI).

[fhahn]

Summary

Update the isCanonical() implementations to check the VPValue step
operand instead of the step in the induction descriptor.

At the moment this is NFC, but it enables further optimizations if the
step is replaced by a constant in D147783.

[Ayal]

llvm/lib/Transforms/Vectorize/VPlan.h

1851–1855

Worth also passing in Start?
Documentation should be updated.

llvm/lib/Transforms/Vectorize/VPlanRecipes.cpp

744–745

Deserves a comment? (Step of an induction should be loop invariant, but could be defined by a recipe in loop preheader, or an invariant that was not LICM'd out? In any case, this method checks only if step is 1, i.e., live-in.)

[fhahn]

Address latest comments, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/VPlan.h

1851–1855

Updated to pass both InductionKind & Start instead of whole induction desciptor. Comment updated accordingly, thanks!

llvm/lib/Transforms/Vectorize/VPlanRecipes.cpp

744–745

Added a comment, thanks!

[fhahn]

clang-format

[Ayal]

Looks good to me, thanks! With some minor nits.

llvm/lib/Transforms/Vectorize/VPlanRecipes.cpp

746

typo:

746

749

nit: setting StartC right after StepC here, instead of above, will (a) early-exit earlier, and (b) highlight how the two are set similarly. Except that Start must be a live-in.

May be worth having an API that gets the LiveInIRValue if one exists and returns null otherwise, which could then be used by dyn_cast_or_null.

1107–1108

The start value is no longer "of ID". Comment worth dropping?

1108–1110

nit: to be consistent with first check of Ty above:

1108–1110

1112–1113

ID is no longer present, update comment?

1113–1114

nit: check of Kind can (be the first to) early-exit.

[fhahn]

llvm/lib/Transforms/Vectorize/VPlanRecipes.cpp

746

Thanks, adjusted

749

May be worth having an API that gets the LiveInIRValue if one exists and returns null otherwise, which could then be used by dyn_cast_or_null.

Sounds good, I can see about adding one.

1107–1108

Update comment, thanks!

1108–1110

Adjusted, thanks!

1112–1113

Updated, thanks!

1113–1114

Moved, thanks!

llvm/lib/Transforms/Vectorize/VPlan.h

 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SmallBitVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/ADT/ilist.h"
 #include "llvm/ADT/ilist_node.h"
+#include "llvm/Analysis/IVDescriptors.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/VectorUtils.h"
 #include "llvm/IR/DebugLoc.h"
 #include "llvm/IR/FMF.h"
 #include "llvm/Transforms/Utils/LoopVersioning.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <string>
 
 namespace llvm {
 
 class BasicBlock;
 class DominatorTree;
-class InductionDescriptor;
 class InnerLoopVectorizer;
 class IRBuilderBase;
 class LoopInfo;
 class PredicateScalarEvolution;
 class raw_ostream;
 class RecurrenceDescriptor;
 class SCEV;
 class Type;
#endif
 
   /// Returns true if the recipe only uses the first lane of operand \p Op.
   bool onlyFirstLaneUsed(const VPValue *Op) const override {
     assert(is_contained(operands(), Op) &&
            "Op must be an operand of the recipe");
     return true;
   }
 
-  /// Check if the induction described by \p ID is canonical, i.e.  has the same
-  /// start, step (of 1), and type as the canonical IV.
-  bool isCanonical(const InductionDescriptor &ID, Type *Ty) const;
+  /// Check if the induction described by \p Kind, /p Start and \p Step is
+  /// canonical, i.e.  has the same start, step (of 1), and type as the
+  /// canonical IV.
+  bool isCanonical(InductionDescriptor::InductionKind Kind, VPValue *Start,
+                   VPValue *Step, Type *Ty) const;
 };
 
 /// A recipe for generating the active lane mask for the vector loop that is
 /// used to predicate the vector operations.
 /// TODO: It would be good to use the existing VPWidenPHIRecipe instead and
 /// remove VPActiveLaneMaskPHIRecipe.
 class VPActiveLaneMaskPHIRecipe : public VPHeaderPHIRecipe {
   DebugLoc DL;

llvm/lib/Transforms/Vectorize/VPlanRecipes.cpp

if (getTruncInst()) {
     O << " " << VPlanIngredient(IV);
 
   O << ", ";
   getStepValue()->printAsOperand(O, SlotTracker);
 }
 #endif
 
 bool VPWidenIntOrFpInductionRecipe::isCanonical() const {
+  // The step may be defined by a recipe in the preheader (e.g. if it requires
+  // SCEV expansion), but for the canonical induction the step is required to be
+  // 1, which is represented as live-in.
+  if (getStepValue()->getDefiningRecipe())
+    return false;
+  auto *StepC = dyn_cast<ConstantInt>(getStepValue()->getLiveInIRValue());
   auto *StartC = dyn_cast<ConstantInt>(getStartValue()->getLiveInIRValue());
-  auto *StepC = dyn_cast<SCEVConstant>(getInductionDescriptor().getStep());
   return StartC && StartC->isZero() && StepC && StepC->isOne();
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 void VPDerivedIVRecipe::print(raw_ostream &O, const Twine &Indent,
                               VPSlotTracker &SlotTracker) const {
   O << Indent;
   printAsOperand(O, SlotTracker);
   O << Indent << "= DERIVED-IV ";
   getStartValue()->printAsOperand(O, SlotTracker);
   O << " + ";
   getCanonicalIV()->printAsOperand(O, SlotTracker);
   O << " * ";

 void VPCanonicalIVPHIRecipe::print(raw_ostream &O, const Twine &Indent,
                                    VPSlotTracker &SlotTracker) const {
   O << Indent << "EMIT ";
   printAsOperand(O, SlotTracker);
   O << " = CANONICAL-INDUCTION";
 }
 #endif
 
-bool VPCanonicalIVPHIRecipe::isCanonical(const InductionDescriptor &ID,
-                                         Type *Ty) const {
-  if (Ty != getScalarType())
+bool VPCanonicalIVPHIRecipe::isCanonical(
+    InductionDescriptor::InductionKind Kind, VPValue *Start, VPValue *Step,
+  // The types must match and it must be an integer induction.
+  if (Ty != getScalarType() || Kind != InductionDescriptor::IK_IntInduction)
+    return false;
+  // Start must match the start value of this canonical induction.
+  if (Start != getStartValue())
     return false;
-  // The start value of ID must match the start value of this canonical
-  // induction.
-  if (getStartValue()->getLiveInIRValue() != ID.getStartValue())
+
+  // If the step is defined by a recipe, it is not a ConstantInt.
+  if (Step->getDefiningRecipe())
     return false;
 
-  ConstantInt *Step = ID.getConstIntStepValue();
-  // ID must also be incremented by one. IK_IntInduction always increment the
-  // induction by Step, but the binary op may not be set.
-  return ID.getKind() == InductionDescriptor::IK_IntInduction && Step &&
-         Step->isOne();
+  ConstantInt *StepC = dyn_cast<ConstantInt>(Step->getLiveInIRValue());
+  return StepC && StepC->isOne();
 }
 
 bool VPWidenPointerInductionRecipe::onlyScalarsGenerated(ElementCount VF) {
   return IsScalarAfterVectorization &&
          (!VF.isScalable() || vputils::onlyFirstLaneUsed(this));
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

for (VPRecipeBase &Phi : HeaderVPBB->phis()) {
     VPCanonicalIVPHIRecipe *CanonicalIV = Plan.getCanonicalIV();
     Type *ResultTy = WideIV->getPHINode()->getType();
     if (Instruction *TruncI = WideIV->getTruncInst())
       ResultTy = TruncI->getType();
     const InductionDescriptor &ID = WideIV->getInductionDescriptor();
     VPValue *Step =
         vputils::getOrCreateVPValueForSCEVExpr(Plan, ID.getStep(), SE);
     VPValue *BaseIV = CanonicalIV;
-    if (!CanonicalIV->isCanonical(ID, ResultTy)) {
+    if (!CanonicalIV->isCanonical(ID.getKind(), WideIV->getStartValue(), Step,
+                                  ResultTy)) {
       BaseIV = new VPDerivedIVRecipe(ID, WideIV->getStartValue(), CanonicalIV,
                                      Step, ResultTy);
       HeaderVPBB->insert(BaseIV->getDefiningRecipe(), IP);
     }
 
     VPScalarIVStepsRecipe *Steps = new VPScalarIVStepsRecipe(ID, BaseIV, Step);
     HeaderVPBB->insert(Steps, IP);