[LV] Respect max VF for interleaved accesses

[mssimpso]

Summary

The selection of the vectorization factor currently doesn't consider interleaved accesses. The vectorization factor is based on the maximum safe dependence distance computed by LAA. However, for loops with interleaved groups, we should instead base the vectorization factor on the maximum safe dependence distance divided by the maximum interleave factor among all the interleaved groups. Interleaved accesses not in a group will be scalarized.

I have also added a flag to disable the store-load forwarding optimization in LAA. This is a performance optimization that should not affect correctness. The optimization must be disabled to expose the bug in the included test case. The addition of the flag would be committed in a separate patch.

[mssimpso]

Fixed a typo in the test case comments.

[anemet]

LGTM, thanks for starting to untangle this.

Some minor comments below.

lib/Analysis/LoopAccessAnalysis.cpp

70

I think that conflict detection is a better name.

1215–1218

Don't we want to also disable for the ATy != BTy case?

lib/Transforms/Vectorize/LoopVectorize.cpp

859

wow, what made you write this instead of unsigned ... = 1? ;)

5199–5202

I think that this needs a comment something along the line of the description in this review.

We may also want to mention that this is fairly conservative because the dependence distance may be between non-interleaved accesses, etc. (Hopefully this won't lead to any performance degradation.)

[mssimpso]

lib/Analysis/LoopAccessAnalysis.cpp

1215–1218

Yes, thanks for catching that!

[mssimpso]

Thanks very much for the review, Adam!

lib/Analysis/LoopAccessAnalysis.cpp

 
 /// \brief We collect dependences up to this threshold.
 static cl::opt<unsigned>
     MaxDependences("max-dependences", cl::Hidden,
                    cl::desc("Maximum number of dependences collected by "
                             "loop-access analysis (default = 100)"),
                    cl::init(100));
 
+/// \brief Enable the store-load forwarding performance optimization. This
+/// option can be disabled for correctness testing.
+static cl::opt<bool> EnableStoreLoadForwardOpt(
+    "enable-store-load-forwarding-opt", cl::Hidden,
+    cl::desc(
+        "Enable store-load forwarding optimization in loop-access analysis"),
+    cl::init(true));
+
 bool VectorizerParams::isInterleaveForced() {
   return ::VectorizationInterleave.getNumOccurrences() > 0;
 }
 
 void LoopAccessReport::emitAnalysis(const LoopAccessReport &Message,
                                     const Function *TheFunction,
                                     const Loop *TheLoop,
                                     const char *PassName) {
MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
   auto &DL = InnermostLoop->getHeader()->getModule()->getDataLayout();
   unsigned TypeByteSize = DL.getTypeAllocSize(ATy);
 
   // Negative distances are not plausible dependencies.
   const APInt &Val = C->getAPInt();
   if (Val.isNegative()) {
     bool IsTrueDataDependence = (AIsWrite && !BIsWrite);
     if (IsTrueDataDependence &&
-        (couldPreventStoreLoadForward(Val.abs().getZExtValue(), TypeByteSize) ||
+        ((EnableStoreLoadForwardOpt &&
+          couldPreventStoreLoadForward(Val.abs().getZExtValue(),
+                                       TypeByteSize)) ||
          ATy != BTy)) {
       DEBUG(dbgs() << "LAA: Forward but may prevent st->ld forwarding\n");
       return Dependence::ForwardButPreventsForwarding;
     }
 
     DEBUG(dbgs() << "LAA: Dependence is negative\n");
     return Dependence::Forward;
   }
 
MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
   // analyze the two accesses on array B, the max safe dependence distance
   // is 2. Then we analyze the accesses on array A, the minimum distance needed
   // is 8, which is less than 2 and forbidden vectorization, But actually
   // both A and B could be vectorized by 2 iterations.
   MaxSafeDepDistBytes =
       Distance < MaxSafeDepDistBytes ? Distance : MaxSafeDepDistBytes;
 
   bool IsTrueDataDependence = (!AIsWrite && BIsWrite);
-  if (IsTrueDataDependence &&
+  if (IsTrueDataDependence && EnableStoreLoadForwardOpt &&
       couldPreventStoreLoadForward(Distance, TypeByteSize))
     return Dependence::BackwardVectorizableButPreventsForwarding;
 
   DEBUG(dbgs() << "LAA: Positive distance " << Val.getSExtValue()
                << " with max VF = "
                << MaxSafeDepDistBytes / (TypeByteSize * Stride) << '\n');
 
   return Dependence::BackwardVectorizable;

lib/Transforms/Vectorize/LoopVectorize.cpp

public:
   /// groups. Substitute symbolic strides using \p Strides.
   void analyzeInterleaving(const ValueToValueMap &Strides);
 
   /// \brief Check if \p Instr belongs to any interleave group.
   bool isInterleaved(Instruction *Instr) const {
     return InterleaveGroupMap.count(Instr);
   }
 
+  /// \brief Return the maximum interleave factor among all interleaved groups.
+  unsigned getMaxInterleaveFactor() const {
+    auto MaxFactor = 1u;
+    for (auto &Entry : InterleaveGroupMap)
+      MaxFactor = std::max(MaxFactor, Entry.second->getFactor());
+    return MaxFactor;
+  }
+
   /// \brief Get the interleave group that \p Instr belongs to.
   ///
   /// \returns nullptr if doesn't have such group.
   InterleaveGroup *getInterleaveGroup(Instruction *Instr) const {
     if (InterleaveGroupMap.count(Instr))
       return InterleaveGroupMap.find(Instr)->second;
     return nullptr;
   }
public:
 
   const LoopAccessInfo *getLAI() const { return LAI; }
 
   /// \brief Check if \p Instr belongs to any interleaved access group.
   bool isAccessInterleaved(Instruction *Instr) {
     return InterleaveInfo.isInterleaved(Instr);
   }
 
+  /// \brief Return the maximum interleave factor among all interleaved groups.
+  unsigned getMaxInterleaveFactor() const {
+    return InterleaveInfo.getMaxInterleaveFactor();
+  }
+
   /// \brief Get the interleaved access group that \p Instr belongs to.
   const InterleaveGroup *getInterleavedAccessGroup(Instruction *Instr) {
     return InterleaveInfo.getInterleaveGroup(Instr);
   }
 
   /// \brief Returns true if an interleaved group requires a scalar iteration
   /// to handle accesses with gaps.
   bool requiresScalarEpilogue() const {
LoopVectorizationCostModel::selectVectorizationFactor(bool OptForSize) {
   unsigned TC = SE->getSmallConstantTripCount(TheLoop);
   DEBUG(dbgs() << "LV: Found trip count: " << TC << '\n');
 
   MinBWs = computeMinimumValueSizes(TheLoop->getBlocks(), *DB, &TTI);
   unsigned SmallestType, WidestType;
   std::tie(SmallestType, WidestType) = getSmallestAndWidestTypes();
   unsigned WidestRegister = TTI.getRegisterBitWidth(true);
   unsigned MaxSafeDepDist = -1U;
   if (Legal->getMaxSafeDepDistBytes() != -1U)
-    MaxSafeDepDist = Legal->getMaxSafeDepDistBytes() * 8;
+    MaxSafeDepDist =
+        Legal->getMaxSafeDepDistBytes() * 8 / Legal->getMaxInterleaveFactor();
   WidestRegister =
       ((WidestRegister < MaxSafeDepDist) ? WidestRegister : MaxSafeDepDist);
   unsigned MaxVectorSize = WidestRegister / WidestType;
 
   DEBUG(dbgs() << "LV: The Smallest and Widest types: " << SmallestType << " / "
                << WidestType << " bits.\n");
   DEBUG(dbgs() << "LV: The Widest register is: " << WidestRegister
                << " bits.\n");
 

test/Transforms/LoopVectorize/AArch64/max-vf-for-interleaved.ll

+; RUN: opt < %s -force-vector-interleave=1 -enable-store-load-forwarding-opt=false -loop-vectorize -dce -instcombine -S | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64--linux-gnu"
+
+%struct.pair = type { i32, i32 }
+
+; Check vectorization of interleaved access groups with positive dependence
+; distances. In this test, the maximum safe dependence distance for
+; vectorization is 16 bytes. Normally, this would lead to a maximum VF of 4.
+; However, for interleaved groups, the effective VF is VF * IF, where IF is the
+; interleave factor. Here, the maximum safe dependence distance is recomputed
+; as 16 / IF bytes, resulting in VF=2. Since IF=2, we should generate <4 x i32>
+; loads and stores instead of <8 x i32> accesses.
+;
+; Note: LAA's store-load forwarding optimization has to be disabled for this
+;       test to be vectorized.
+
+; struct pair {
+;   int x;
+;   int y;
+; };
+;
+; void max_vf(struct pair *restrict p) {
+;   for (int i = 0; i < 1000; i++) {
+;     p[i + 2].x = p[i].x
+;     p[i + 2].y = p[i].y
+;   }
+; }
+
+; CHECK-LABEL: @max_vf
+; CHECK: load <4 x i32>
+; CHECK: store <4 x i32>
+
+define void @max_vf(%struct.pair* noalias nocapture %p) {
+entry:
+  br label %for.body
+
+for.body:
+  %i = phi i64 [ 0, %entry ], [ %i.next, %for.body ]
+  %0 = add nuw nsw i64 %i, 2
+  %p_i.x = getelementptr inbounds %struct.pair, %struct.pair* %p, i64 %i, i32 0
+  %p_i_plus_2.x = getelementptr inbounds %struct.pair, %struct.pair* %p, i64 %0, i32 0
+  %1 = load i32, i32* %p_i.x, align 4
+  store i32 %1, i32* %p_i_plus_2.x, align 4
+  %p_i.y = getelementptr inbounds %struct.pair, %struct.pair* %p, i64 %i, i32 1
+  %p_i_plus_2.y = getelementptr inbounds %struct.pair, %struct.pair* %p, i64 %0, i32 1
+  %2 = load i32, i32* %p_i.y, align 4
+  store i32 %2, i32* %p_i_plus_2.y, align 4
+  %i.next = add nuw nsw i64 %i, 1
+  %cond = icmp eq i64 %i.next, 1000
+  br i1 %cond, label %for.exit, label %for.body
+
+for.exit:
+  ret void
+}