[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 ↗

(On Diff #57209)

I think that conflict detection is a better name.

1215–1218 ↗

(On Diff #57209)

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

lib/Transforms/Vectorize/LoopVectorize.cpp

859 ↗

(On Diff #57209)

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

5199–5202 ↗

(On Diff #57209)

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 ↗

(On Diff #57209)

Yes, thanks for catching that!

[mssimpso]

Thanks very much for the review, Adam!

llvm/trunk/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 of all interleaved groups.
+  unsigned getMaxInterleaveFactor() const {
+    unsigned MaxFactor = 1;
+    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 of 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;
+
+  // Get the maximum safe dependence distance in bits computed by LAA. If the
+  // loop contains any interleaved accesses, we divide the dependence distance
+  // by the maximum interleave factor of all interleaved groups. Note that
+  // although the division ensures correctness, this is a fairly conservative
+  // computation because the maximum distance computed by LAA may not involve
+  // any of the interleaved accesses.
   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");

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

+; RUN: opt < %s -force-vector-interleave=1 -enable-conflict-detection=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 conflict detection 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
+}