[LoopVectorize] Calculate Max Feasible Scalable VF.

[sdesmalen]

Summary

This patch adds a 'enable-scalable-vectorizaton' flag to the
loopvectorizer, which for now doesn't change the vectorization, but it
let's computeMaxVF call computeFeasibleMaxVF with 'ComputeScalableMaxVF =
true', which prints the output to a DEBUG ostream. This is then verified
by the corresponding test.

This patch is a preparatory patch with the ultimate goal of making
computeMaxVF() return both a max fixed VF and a max scalable VF,
so that selectVectorizationFactor() can pick the most cost-effective
vectorization factor.

[sdesmalen]

Rebase

[david-arm]

llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp

81 ↗

(On Diff #324642)

Not a problem really, but just wondering why you moved it here? I thought since Val is unsigned the two different checks are identical?

[sdesmalen]

llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp

81 ↗

(On Diff #324642)

That's because Val can now also be -1 (<=> FK_Undefined), used for -scalable-vectorization=on.

[sdesmalen]

llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp

81 ↗

(On Diff #324642)

Sorry, when I replied I didn't realise Val was indeed unsigned, you're right that the result is the same. I thought I'd move it here to make it more clear that both Force and Scalable work the same way (as in, they take FK_Disabled, FK_Undefined or FK_Enabled). But yes, the change is a non-functional one.

I guess this means you can set it to 'disabled' or 'enabled', but not explicitly to 'auto' using the hints.

[david-arm]

LGTM!

[sdesmalen]

Rebased patch.

[sdesmalen]

Abandoned in favour of D98509

llvm/include/llvm/Analysis/TargetTransformInfo.h

public:
 
   /// \return The width of the smallest vector register type.
   unsigned getMinVectorRegisterBitWidth() const;
 
   /// \return The maximum value of vscale if the target specifies an
   ///  architectural maximum vector length, and None otherwise.
   Optional<unsigned> getMaxVScale() const;
 
+  /// \return The maximum number of bits for a block in a scalable vector
+  /// register for a scalable vector with a vscale number of blocks.
+  /// i.e. the maximum number of N x elt bits in <vscale x N x elt>.
+  unsigned getMaxScalableBitsPerBlock() const;
+
   /// \return True if the vectorization factor should be chosen to
   /// make the vector of the smallest element type match the size of a
   /// vector register. For wider element types, this could result in
   /// creating vectors that span multiple vector registers.
   /// If false, the vectorization factor will be chosen based on the
   /// size of the widest element type.
   bool shouldMaximizeVectorBandwidth(bool OptSize) const;
 
virtual int getIntImmCostIntrin(Intrinsic::ID IID, unsigned Idx,
                                   TargetCostKind CostKind) = 0;
   virtual unsigned getNumberOfRegisters(unsigned ClassID) const = 0;
   virtual unsigned getRegisterClassForType(bool Vector,
                                            Type *Ty = nullptr) const = 0;
   virtual const char *getRegisterClassName(unsigned ClassID) const = 0;
   virtual unsigned getRegisterBitWidth(bool Vector) const = 0;
   virtual unsigned getMinVectorRegisterBitWidth() = 0;
   virtual Optional<unsigned> getMaxVScale() const = 0;
+  virtual unsigned getMaxScalableBitsPerBlock() const = 0;
   virtual bool shouldMaximizeVectorBandwidth(bool OptSize) const = 0;
   virtual ElementCount getMinimumVF(unsigned ElemWidth,
                                     bool IsScalableVF) const = 0;
   virtual unsigned getMaximumVF(unsigned ElemWidth, unsigned Opcode) const = 0;
   virtual bool shouldConsiderAddressTypePromotion(
       const Instruction &I, bool &AllowPromotionWithoutCommonHeader) = 0;
   virtual unsigned getCacheLineSize() const = 0;
   virtual Optional<unsigned> getCacheSize(CacheLevel Level) const = 0;
unsigned getRegisterBitWidth(bool Vector) const override {
     return Impl.getRegisterBitWidth(Vector);
   }
   unsigned getMinVectorRegisterBitWidth() override {
     return Impl.getMinVectorRegisterBitWidth();
   }
   Optional<unsigned> getMaxVScale() const override {
     return Impl.getMaxVScale();
   }
+  unsigned getMaxScalableBitsPerBlock() const override {
+    return Impl.getMaxScalableBitsPerBlock();
+  }
   bool shouldMaximizeVectorBandwidth(bool OptSize) const override {
     return Impl.shouldMaximizeVectorBandwidth(OptSize);
   }
   ElementCount getMinimumVF(unsigned ElemWidth,
                             bool IsScalableVF) const override {
     return Impl.getMinimumVF(ElemWidth, IsScalableVF);
   }
   unsigned getMaximumVF(unsigned ElemWidth, unsigned Opcode) const override {

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

public:
   }
 
   unsigned getRegisterBitWidth(bool Vector) const { return 32; }
 
   unsigned getMinVectorRegisterBitWidth() const { return 128; }
 
   Optional<unsigned> getMaxVScale() const { return None; }
 
+  unsigned getMaxScalableBitsPerBlock() const { return 0; }
+
   bool shouldMaximizeVectorBandwidth(bool OptSize) const { return false; }
 
   ElementCount getMinimumVF(unsigned ElemWidth, bool IsScalableVF) const {
     return ElementCount::get(0, IsScalableVF);
   }
 
   unsigned getMaximumVF(unsigned ElemWidth, unsigned Opcode) const { return 0; }
 

llvm/lib/Analysis/TargetTransformInfo.cpp

 unsigned TargetTransformInfo::getMinVectorRegisterBitWidth() const {
   return TTIImpl->getMinVectorRegisterBitWidth();
 }
 
 Optional<unsigned> TargetTransformInfo::getMaxVScale() const {
   return TTIImpl->getMaxVScale();
 }
 
+unsigned TargetTransformInfo::getMaxScalableBitsPerBlock() const {
+  return TTIImpl->getMaxScalableBitsPerBlock();
+}
+
 bool TargetTransformInfo::shouldMaximizeVectorBandwidth(bool OptSize) const {
   return TTIImpl->shouldMaximizeVectorBandwidth(OptSize);
 }
 
 ElementCount TargetTransformInfo::getMinimumVF(unsigned ElemWidth,
                                                bool IsScalableVF) const {
   return TTIImpl->getMinimumVF(ElemWidth, IsScalableVF);
 }

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.h

public:
   ElementCount getMinimumVF(unsigned ElemWidth, bool IsScalableVF) const;
 
   Optional<unsigned> getMaxVScale() const {
     if (ST->hasSVE())
       return AArch64::SVEMaxBitsPerVector / AArch64::SVEBitsPerBlock;
     return BaseT::getMaxVScale();
   }
 
+  unsigned getMaxScalableBitsPerBlock() const {
+    if (ST->hasSVE())
+      return AArch64::SVEBitsPerBlock;
+    return BaseT::getMaxScalableBitsPerBlock();
+  }
+
   unsigned getMaxInterleaveFactor(unsigned VF);
 
   unsigned getGatherScatterOpCost(unsigned Opcode, Type *DataTy,
                                   const Value *Ptr, bool VariableMask,
                                   Align Alignment, TTI::TargetCostKind CostKind,
                                   const Instruction *I = nullptr);
 
   int getCastInstrCost(unsigned Opcode, Type *Dst, Type *Src,

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

 /// Loops with a known constant trip count below this number are vectorized only
 /// if no scalar iteration overheads are incurred.
 static cl::opt<unsigned> TinyTripCountVectorThreshold(
     "vectorizer-min-trip-count", cl::init(16), cl::Hidden,
     cl::desc("Loops with a constant trip count that is smaller than this "
              "value are vectorized only if no scalar iteration overheads "
              "are incurred."));
 
+static cl::opt<bool> EnableScalableVectorization(
+    "enable-scalable-vectorization", cl::init(false), cl::Hidden,
+    cl::desc("Allow the compiler to use scalable vectors to vectorize a loop"));
+
 // Option prefer-predicate-over-epilogue indicates that an epilogue is undesired,
 // that predication is preferred, and this lists all options. I.e., the
 // vectorizer will try to fold the tail-loop (epilogue) into the vector body
 // and predicate the instructions accordingly. If tail-folding fails, there are
 // different fallback strategies depending on these values:
 namespace PreferPredicateTy {
   enum Option {
     ScalarEpilogue = 0,
private:
   /// fixed-width VF.
   Optional<ElementCount> computeFeasibleUserVF(ElementCount UserVF,
                                                unsigned WidestType);
 
   /// \return An upper bound for the vectorization factor, a power-of-2 larger
   /// than zero. One is returned if vectorization should best be avoided due
   /// to cost.
   ElementCount computeFeasibleMaxVF(unsigned ConstTripCount,
-                                    unsigned SmallestType, unsigned WidestType);
+                                    unsigned SmallestType, unsigned WidestType,
+                                    bool ComputeMaxScalableVF);
 
   /// \return A pair with the clamped VF and the maximum safe VF.
   /// If MaxSafeElements allows it, ClampedVF is the SuggestedVF, otherwise
   /// it is clamped to MaxSafeElements. If SuggestedVF is scalable, the returned
   /// VF may be clamped to a non-scalable VF.
   std::pair<ElementCount, ElementCount>
   clampFeasibleMaxVF(ElementCount SuggestedVF, unsigned MaxSafeElements);
 
LoopVectorizationCostModel::computeMaxVF(ElementCount UserVF, unsigned UserIC) {
   MinBWs = computeMinimumValueSizes(TheLoop->getBlocks(), *DB, &TTI);
   unsigned SmallestType, WidestType;
   std::tie(SmallestType, WidestType) = getSmallestAndWidestTypes();
 
   auto GetFeasibleMaxVF = [&]() -> ElementCount {
     // First analyze the UserVF, fall back if the UserVF should be ignored.
     Optional<ElementCount> MaybeMaxVF =
         computeFeasibleUserVF(UserVF, WidestType);
+
+    // First try to find a max scalable VF, because the resulting MaxVF may not
+    // be scalable, depending on dependence distances in the loop, or the
+    // tripcount.
+    if (EnableScalableVectorization && TTI.supportsScalableVectors()) {
+      ElementCount MaxScalableVF =
+          computeFeasibleMaxVF(TC, SmallestType, WidestType,
+                               /*ComputeMaxScalableVF=*/true);
+      if(MaxScalableVF.isScalable())
+        LLVM_DEBUG(dbgs() << "LV: Found feasible scalable VF = " << MaxScalableVF << "\n");
+      else
+        LLVM_DEBUG(dbgs() << "LV: No feasible scalable VF found.\n");
+    }
+
     if (!MaybeMaxVF)
-      MaybeMaxVF = computeFeasibleMaxVF(TC, SmallestType, WidestType);
+      MaybeMaxVF = computeFeasibleMaxVF(TC, SmallestType, WidestType,
+                                        /*ComputeMaxScalableVF=*/false);
 
     return MaybeMaxVF.getValue();
   };
 
   switch (ScalarEpilogueStatus) {
   case CM_ScalarEpilogueAllowed:
     return GetFeasibleMaxVF();
   case CM_ScalarEpilogueNotAllowedUsePredicate:
ORE->emit([&]() {
              << " is unsafe, clamping to maximum safe vectorization factor "
              << ore::NV("VectorizationFactor", NewVF);
     });
   }
   return NewVF;
 }
 
 ElementCount LoopVectorizationCostModel::computeFeasibleMaxVF(
-    unsigned ConstTripCount, unsigned SmallestType, unsigned WidestType) {
+    unsigned ConstTripCount, unsigned SmallestType, unsigned WidestType,
+    bool ComputeMaxScalableVF) {
   // Get the maximum safe dependence distance in bits computed by LAA.
   // It is computed by MaxVF * sizeOf(type) * 8, where type is taken from
   // the memory accesses that is most restrictive (involved in the smallest
   // dependence distance).
   unsigned MaxSafeVectorWidthInBits = Legal->getMaxSafeVectorWidthInBits();
   unsigned MaxSafeElements =
       PowerOf2Floor(MaxSafeVectorWidthInBits / WidestType);
 
-  unsigned WidestRegister = TTI.getRegisterBitWidth(true);
+  unsigned WidestRegister = ComputeMaxScalableVF
+                                ? TTI.getMaxScalableBitsPerBlock()
+                                : TTI.getRegisterBitWidth(true);
 
   LLVM_DEBUG(dbgs() << "LV: The Smallest and Widest types: " << SmallestType
                     << " / " << WidestType << " bits.\n");
   LLVM_DEBUG(dbgs() << "LV: The Widest register safe to use is: "
                     << WidestRegister << " bits.\n");
 
   // Ensure MaxVF is a power of 2; the dependence distance bound may not be.
   // Note that both WidestRegister and WidestType may not be a powers of 2.
-  auto MaxVectorSize =
-      ElementCount::getFixed(PowerOf2Floor(WidestRegister / WidestType));
+  auto MaxVectorSize = ElementCount::get(
+      PowerOf2Floor(WidestRegister / WidestType), ComputeMaxScalableVF);
   std::tie(MaxVectorSize, std::ignore) =
       clampFeasibleMaxVF(MaxVectorSize, MaxSafeElements);
 
   if (MaxVectorSize.getKnownMinValue() == 0) {
     LLVM_DEBUG(dbgs() << "LV: The target has no vector registers.\n");
     return ElementCount::getFixed(1);
   } else if (ConstTripCount && isPowerOf2_32(ConstTripCount)) {
     // We need to clamp the VF to be the ConstTripCount. There is no point in
     // choosing a higher viable VF as done in the loop below.
     ElementCount ClampedVF = MaxVectorSize;
     std::tie(ClampedVF, std::ignore) =
         clampFeasibleMaxVF(MaxVectorSize, ConstTripCount);
     if (ClampedVF != MaxVectorSize) {
       LLVM_DEBUG(dbgs() << "LV: Clamping the MaxVF to the constant trip count: "
                         << ConstTripCount << "\n");
       return ClampedVF;
     }
   }
 
   ElementCount MaxVF = MaxVectorSize;
   if (TTI.shouldMaximizeVectorBandwidth(!isScalarEpilogueAllowed()) ||
       (MaximizeBandwidth && isScalarEpilogueAllowed())) {
-    auto MaxVectorSizeMaxBW =
-        ElementCount::getFixed(PowerOf2Floor(WidestRegister / SmallestType));
+    auto MaxVectorSizeMaxBW = ElementCount::get(
+        PowerOf2Floor(WidestRegister / SmallestType), ComputeMaxScalableVF);
     std::tie(MaxVectorSizeMaxBW, std::ignore) =
         clampFeasibleMaxVF(MaxVectorSizeMaxBW, MaxSafeElements);
 
     // Collect all viable vectorization factors larger than the default MaxVF
     // (i.e. MaxVectorSize).
     SmallVector<ElementCount, 8> VFs;
     for (ElementCount VS = MaxVectorSize * 2;
          ElementCount::isKnownLE(VS, MaxVectorSizeMaxBW); VS *= 2)
for (int i = RUs.size() - 1; i >= 0; --i) {
         if (pair.second > TargetNumRegisters)
           Selected = false;
       }
       if (Selected) {
         MaxVF = VFs[i];
         break;
       }
     }
-    if (ElementCount MinVF = TTI.getMinimumVF(SmallestType, false)) {
+    if (ElementCount MinVF =
+            TTI.getMinimumVF(SmallestType, ComputeMaxScalableVF)) {
       if (ElementCount::isKnownLT(MaxVF, MinVF)) {
         LLVM_DEBUG(dbgs() << "LV: Overriding calculated MaxVF(" << MaxVF
                           << ") with target's minimum: " << MinVF << '\n');
         MaxVF = MinVF;
       }
     }
   }
   return MaxVF;

llvm/test/Transforms/LoopVectorize/AArch64/scalable-vf-analysis.ll

+; REQUIRES: asserts
+; RUN: opt -mtriple=aarch64-none-linux-gnu -mattr=+sve -enable-scalable-vectorization -loop-vectorize -S -debug-only=loop-vectorize < %s 2>&1 | FileCheck %s
+; RUN: opt -mtriple=aarch64-none-linux-gnu -mattr=+sve -enable-scalable-vectorization -loop-vectorize -S -debug-only=loop-vectorize -vectorizer-maximize-bandwidth < %s 2>&1 | FileCheck %s --check-prefix=CHECKMAXBW
+
+; Test that the MaxVF for the following loop, that has no dependence distances,
+; is calculated as vscale x 4 (max legal SVE vector size) or vscale x 16
+; (maximized bandwidth for i8 in the loop).
+define void @test0(i32* %a, i8* %b, i32* %c) {
+; CHECK: LV: Checking a loop in "test0"
+; CHECK: LV: Found feasible scalable VF = vscale x 4
+; CHECKMAXBW: LV: Checking a loop in "test0"
+; CHECKMAXBW: LV: Found feasible scalable VF = vscale x 16
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
+  %arrayidx = getelementptr inbounds i32, i32* %c, i64 %iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %arrayidx2 = getelementptr inbounds i8, i8* %b, i64 %iv
+  %1 = load i8, i8* %arrayidx2, align 4
+  %zext = zext i8 %1 to i32
+  %add = add nsw i32 %zext, %0
+  %arrayidx5 = getelementptr inbounds i32, i32* %a, i64 %iv
+  store i32 %add, i32* %arrayidx5, align 4
+  %iv.next = add nuw nsw i64 %iv, 1
+  %exitcond.not = icmp eq i64 %iv.next, 1024
+  br i1 %exitcond.not, label %exit, label %loop
+
+exit:
+  ret void
+}
+; Test that the MaxVF for the following loop, with a dependence distance
+; of 64 elements, is calculated as (maxvscale = 16) * 4.
+define void @test1(i32* %a, i8* %b) {
+; CHECK: LV: Checking a loop in "test1"
+; CHECK: LV: Found feasible scalable VF = vscale x 4
+; CHECKMAXBW: LV: Checking a loop in "test1"
+; CHECKMAXBW: LV: Found feasible scalable VF = vscale x 4
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
+  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %arrayidx2 = getelementptr inbounds i8, i8* %b, i64 %iv
+  %1 = load i8, i8* %arrayidx2, align 4
+  %zext = zext i8 %1 to i32
+  %add = add nsw i32 %zext, %0
+  %2 = add nuw nsw i64 %iv, 64
+  %arrayidx5 = getelementptr inbounds i32, i32* %a, i64 %2
+  store i32 %add, i32* %arrayidx5, align 4
+  %iv.next = add nuw nsw i64 %iv, 1
+  %exitcond.not = icmp eq i64 %iv.next, 1024
+  br i1 %exitcond.not, label %exit, label %loop
+
+exit:
+  ret void
+}
+
+; Test that the MaxVF for the following loop, with a dependence distance
+; of 32 elements, is calculated as (maxvscale = 16) * 2.
+define void @test2(i32* %a, i8* %b) {
+; CHECK: LV: Checking a loop in "test2"
+; CHECK: LV: Found feasible scalable VF = vscale x 2
+; CHECKMAXBW: LV: Checking a loop in "test2"
+; CHECKMAXBW: LV: Found feasible scalable VF = vscale x 2
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
+  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %arrayidx2 = getelementptr inbounds i8, i8* %b, i64 %iv
+  %1 = load i8, i8* %arrayidx2, align 4
+  %zext = zext i8 %1 to i32
+  %add = add nsw i32 %zext, %0
+  %2 = add nuw nsw i64 %iv, 32
+  %arrayidx5 = getelementptr inbounds i32, i32* %a, i64 %2
+  store i32 %add, i32* %arrayidx5, align 4
+  %iv.next = add nuw nsw i64 %iv, 1
+  %exitcond.not = icmp eq i64 %iv.next, 1024
+  br i1 %exitcond.not, label %exit, label %loop
+
+exit:
+  ret void
+}
+
+; Test that the MaxVF for the following loop, with a dependence distance
+; of 16 elements, is calculated as (maxvscale = 16) * 1.
+define void @test3(i32* %a, i8* %b) {
+; CHECK: LV: Checking a loop in "test3"
+; CHECK: LV: Found feasible scalable VF = vscale x 1
+; CHECKMAXBW: LV: Checking a loop in "test3"
+; CHECKMAXBW: LV: Found feasible scalable VF = vscale x 2
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
+  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %arrayidx2 = getelementptr inbounds i8, i8* %b, i64 %iv
+  %1 = load i8, i8* %arrayidx2, align 4
+  %zext = zext i8 %1 to i32
+  %add = add nsw i32 %zext, %0
+  %2 = add nuw nsw i64 %iv, 16
+  %arrayidx5 = getelementptr inbounds i32, i32* %a, i64 %2
+  store i32 %add, i32* %arrayidx5, align 4
+  %iv.next = add nuw nsw i64 %iv, 1
+  %exitcond.not = icmp eq i64 %iv.next, 1024
+  br i1 %exitcond.not, label %exit, label %loop
+
+exit:
+  ret void
+}