Fix maximum legal VF calculation

[alonkom]

Summary

This patch fixes pr34283, which exposed that the computation of maximum legal width for vectorization was wrong, because it relied on MaxInterleaveFactor to obtain the maximum stride used in the loop, however not all strided accesses in the loop have an interleave-group associated with them. In pr34283 the interleave group gets invalidated because it is a store with gaps; as a result MaxInterleaveFactor is 1, and the computed maximum legal width for vectorization comes out larger than it should be.
Instead of recording the maximum stride in the loop, which can be over conservative (e.g. if the access with the maximum stride is not involved in the dependence limitation), this patch tracks the actual maximum legal width imposed by accesses that are involved in dependencies.

[dorit]

Looks fine to me (with a couple very minor dbg reports improvements).
@Ayal/@hfinkel - what do you say?

lib/Transforms/Vectorize/LoopVectorize.cpp

6281

Not strictly related to your patch, but since you are already adding a missing "Invalidate candidate interleave group" message above for the case that shows up in PR34283 (thanks!) , might as well also add a similar message that's missing here (where we invalidate a candidate interleave group due to a reverse access with gaps).

6378

Another small nit not related to your patch, but while we're here: would be nice to make this message a bit clearer, e.g. "... Widest register safe to use is..."

[Ayal]

include/llvm/Analysis/LoopAccessAnalysis.h

205

Should MaxSafeRegisterWidth replace MaxSafeDepDistBytes, or are both needed?

265

that causes the worse[worst] restriction

>> that is most restrictive.

lib/Transforms/Vectorize/LoopVectorize.cpp

6226

Can simplify: "LV: Invalidate candidate interleaved store group due to gaps.\n"

6363

This comment about being fairly conservative (i.e., could be room for improvement) still holds, right?

6366

So another way of fixing this could be to have Legal record the MaxStride, instead of asking it for the MaxInterleaveFactor here?

6367

that incurs the largest restriction

that is most restrictive

test/Transforms/LoopVectorize/X86/pr34283-1.ll

1

No need to require asserts here, right?

Better place the test say in memdep.ll, rather than opening a new file? Following TestingGuide.html#writing-new-regression-tests. In any case, place both tests in same file, using the PR number in the function names instead of foo.

25

Can we also/instead check the runtime guard that is generated, perhaps where M is not a compile-time constant?

26

min[i]mum

test/Transforms/LoopVectorize/X86/pr34283-2.ll

1

The "2>&1" is not needed here.

25

This is a bit fragile, as it's relying on the cost-model to choose exactly VF=4. Perhaps better to simply CHECK for a vector whose VF is in the range 2-7, and no vectors of VF 8 or larger?

[alonkom]

include/llvm/Analysis/LoopAccessAnalysis.h

205

I think we need both. MaxSafeDepDistBytes is used in a few other LAA functions, and is correct.

lib/Transforms/Vectorize/LoopVectorize.cpp

6363

We are actually now dropping this over-conservativeness, which was also not conservative enough.

6366

yes, this was one of the possible solutions we thought of, but it is less accurate.

Furthermore we can also drop getMaxInterleaveFactor() as it becomes dead.

test/Transforms/LoopVectorize/X86/pr34283-1.ll

1

The asserts are needed for checking the debug output, but we can check the IR instead, as in the second test.

25

This fix involves compile time distances that affect max VF; no runtime guards involved.

test/Transforms/LoopVectorize/X86/pr34283-2.ll

25

Can force-vectorization-width=4 and CHECK that it vectorized, and force-vectorization-width=8 and CHECK that it did not.

[Ayal]

Only additional comment is whether the test needs to be X86/skx specific, or whether it can be placed in, say, memdep.ll

[alonkom]

The test is now placed in memdep.ll

[Ayal]

lib/Transforms/Vectorize/LoopVectorize.cpp

1677

Best assert that LAI is not null before dereferencing it.

6374

While you're touching this, best use std::min.

test/Transforms/LoopVectorize/memdep.ll

230 ↗

(On Diff #114571)

Better clarify:
; where the dependence distance here is 6 iterations, given by |N-(N-12)|/2.

include/llvm/Analysis/LoopAccessAnalysis.h

struct Dependence {
 
     /// \brief Print the dependence.  \p Instr is used to map the instruction
     /// indices to instructions.
     void print(raw_ostream &OS, unsigned Depth,
                const SmallVectorImpl<Instruction *> &Instrs) const;
   };
 
   MemoryDepChecker(PredicatedScalarEvolution &PSE, const Loop *L)
-      : PSE(PSE), InnermostLoop(L), AccessIdx(0),
+      : PSE(PSE), InnermostLoop(L), AccessIdx(0), MaxSafeRegisterWidth(0),
         ShouldRetryWithRuntimeCheck(false), SafeForVectorization(true),
         RecordDependences(true) {}
 
   /// \brief Register the location (instructions are given increasing numbers)
   /// of a write access.
   void addAccess(StoreInst *SI) {
     Value *Ptr = SI->getPointerOperand();
     Accesses[MemAccessInfo(Ptr, true)].push_back(AccessIdx);
public:
   /// \brief No memory dependence was encountered that would inhibit
   /// vectorization.
   bool isSafeForVectorization() const { return SafeForVectorization; }
 
   /// \brief The maximum number of bytes of a vector register we can vectorize
   /// the accesses safely with.
   uint64_t getMaxSafeDepDistBytes() { return MaxSafeDepDistBytes; }
 
+  /// \brief Return the number of elements that are safe to operate on
+  /// simultaneously, multiplied by the size of the element in bits.
+  uint64_t getMaxSafeRegisterWidth() const { return MaxSafeRegisterWidth; }
+
   /// \brief In same cases when the dependency check fails we can still
   /// vectorize the loop with a dynamic array access check.
   bool shouldRetryWithRuntimeCheck() { return ShouldRetryWithRuntimeCheck; }
 
   /// \brief Returns the memory dependences.  If null is returned we exceeded
   /// the MaxDependences threshold and this information is not
   /// available.
   const SmallVectorImpl<Dependence> *getDependences() const {
private:
   SmallVector<Instruction *, 16> InstMap;
 
   /// \brief The program order index to be used for the next instruction.
   unsigned AccessIdx;
 
   // We can access this many bytes in parallel safely.
   uint64_t MaxSafeDepDistBytes;
 
+  /// \brief Number of elements (from consecutive iterations) that are safe to
+  /// operate on simultaneously, multiplied by the size of the element in bits.
+  /// The size of the element is taken from the memory access that causes the
+  /// worse restriction.
+  uint64_t MaxSafeRegisterWidth;
+
   /// \brief If we see a non-constant dependence distance we can still try to
   /// vectorize this loop with runtime checks.
   bool ShouldRetryWithRuntimeCheck;
 
   /// \brief No memory dependence was encountered that would inhibit
   /// vectorization.
   bool SafeForVectorization;
 

lib/Analysis/LoopAccessAnalysis.cpp

MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
   MaxSafeDepDistBytes =
       std::min(static_cast<uint64_t>(Distance), MaxSafeDepDistBytes);
 
   bool IsTrueDataDependence = (!AIsWrite && BIsWrite);
   if (IsTrueDataDependence && EnableForwardingConflictDetection &&
       couldPreventStoreLoadForward(Distance, TypeByteSize))
     return Dependence::BackwardVectorizableButPreventsForwarding;
 
+  uint64_t MaxVF = MaxSafeDepDistBytes / (TypeByteSize * Stride);
   DEBUG(dbgs() << "LAA: Positive distance " << Val.getSExtValue()
-               << " with max VF = "
-               << MaxSafeDepDistBytes / (TypeByteSize * Stride) << '\n');
-
+               << " with max VF = " << MaxVF << '\n');
+  uint64_t MaxVFInBits = MaxVF * TypeByteSize * 8 ;
+  MaxSafeRegisterWidth = (MaxSafeRegisterWidth == 0) ?
+      MaxVFInBits : std::min(MaxSafeRegisterWidth, MaxVFInBits);
   return Dependence::BackwardVectorizable;
 }
 
 bool MemoryDepChecker::areDepsSafe(DepCandidates &AccessSets,
                                    MemAccessInfoList &CheckDeps,
                                    const ValueToValueMap &Strides) {
 
   MaxSafeDepDistBytes = -1;

lib/Transforms/Vectorize/LoopVectorize.cpp

public:
   /// \brief Returns true if an interleaved group requires a scalar iteration
   /// to handle accesses with gaps.
   bool requiresScalarEpilogue() const {
     return InterleaveInfo.requiresScalarEpilogue();
   }
 
   unsigned getMaxSafeDepDistBytes() { return LAI->getMaxSafeDepDistBytes(); }
 
+  uint64_t getMaxSafeRegisterWidth() const {
+    return LAI->getDepChecker().getMaxSafeRegisterWidth();
+  }
+
   bool hasStride(Value *V) { return LAI->hasStride(V); }
 
   /// Returns true if the target machine supports masked store operation
   /// for the given \p DataType and kind of access to \p Ptr.
   bool isLegalMaskedStore(Type *DataType, Value *Ptr) {
     return isConsecutivePtr(Ptr) && TTI->isLegalMaskedStore(DataType);
   }
   /// Returns true if the target machine supports masked load operation
for (auto AI = std::next(BI); AI != E; ++AI) {
         if (A->mayReadFromMemory())
           Group->setInsertPos(A);
       }
     } // Iteration over A accesses.
   } // Iteration over B accesses.
 
   // Remove interleaved store groups with gaps.
   for (InterleaveGroup *Group : StoreGroups)
-    if (Group->getNumMembers() != Group->getFactor())
+    if (Group->getNumMembers() != Group->getFactor()) {
+      DEBUG(dbgs() << "LV: Invalidate candidate interleaved group due to "
+                      "interleaved store group with gaps.\n");
       releaseGroup(Group);
+    }
 
   // Remove interleaved groups with gaps (currently only loads) whose memory
   // accesses may wrap around. We have to revisit the getPtrStride analysis,
   // this time with ShouldCheckWrap=true, since collectConstStrideAccesses does
   // not check wrapping (see documentation there).
   // FORNOW we use Assume=false;
   // TODO: Change to Assume=true but making sure we don't exceed the threshold
   // of runtime SCEV assumptions checks (thereby potentially failing to
if (LastMember) {
         releaseGroup(Group);
       }
     } else {
       // Case 3: A non-reversed interleaved load group with gaps: We need
       // to execute at least one scalar epilogue iteration. This will ensure
       // we don't speculatively access memory out-of-bounds. We only need
       // to look for a member at index factor - 1, since every group must have
       // a member at index zero.
       if (Group->isReverse()) {
         releaseGroup(Group);
         continue;
       }
       DEBUG(dbgs() << "LV: Interleaved group requires epilogue iteration.\n");
       RequiresScalarEpilogue = true;
     }
   }
 }

 
 unsigned LoopVectorizationCostModel::computeFeasibleMaxVF(bool OptForSize) {
   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.
+  // 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 incurs the largest restriction (involved in the
+  // smallest dependence distance).
   if (Legal->getMaxSafeDepDistBytes() != -1U)
-    MaxSafeDepDist =
-        Legal->getMaxSafeDepDistBytes() * 8 / Legal->getMaxInterleaveFactor();
+    MaxSafeDepDist = Legal->getMaxSafeRegisterWidth();
 
   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");
 
   if (MaxVectorSize == 0) {
     DEBUG(dbgs() << "LV: The target has no vector registers.\n");
     MaxVectorSize = 1;
   }
 
   assert(MaxVectorSize <= 64 && "Did not expect to pack so many elements"

test/Transforms/LoopVectorize/X86/pr34283-1.ll

+; REQUIRES: asserts
+; RUN: opt -S -loop-vectorize -mcpu=skx -debug-only=loop-vectorize < %s  2>&1 | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+;Check the new calculation of the maximum safe distance in bits which can be vectorized.
+;The previous behavior did not take account that the stride was 2.
+;Therefore the MaxSafeDist was computed as 384 bits instead of 192.  
+
+;#define M 32
+;#define N 2 * M
+;unsigned int a [N];
+;void foo(){
+; unsigned int j=0;
+;   for (j = 0; j < M - 6; ++j)
+;    {
+;        a[N - 2 * j] = 69;
+;        a[N - 12 - 2 * j] = 7;
+;    }
+;
+;}
+
+; CHECK-LABEL: foo
+; CHECK: LV: The Widest register is: 192 bits.
+; MaxVF in loop is 6, therefore minmum required register is 6 * sizeof(int) * 8 = 192 bits
+
+@a = common local_unnamed_addr global [64 x i32] zeroinitializer, align 16
+
+; Function Attrs: norecurse nounwind uwtable
+define void @foo() local_unnamed_addr {
+entry:
+  br label %for.body
+
+for.body:                                         
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %0 = shl i64 %indvars.iv, 1
+  %1 = sub nuw nsw i64 64, %0
+  %arrayidx = getelementptr inbounds [64 x i32], [64 x i32]* @a, i64 0, i64 %1
+  store i32 69, i32* %arrayidx, align 8
+  %2 = sub nuw nsw i64 52, %0
+  %arrayidx4 = getelementptr inbounds [64 x i32], [64 x i32]* @a, i64 0, i64 %2
+  store i32 7, i32* %arrayidx4, align 8
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 26
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          
+  ret void
+}

test/Transforms/LoopVectorize/X86/pr34283-2.ll

+; RUN: opt -S -loop-vectorize -mcpu=skx < %s  2>&1 | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+;Check the new calculation of the maximum safe distance in bits which can be vectorized.
+;The previous behavior did not take account that the stride was 2.
+;Therefore the maxVF was computed as 8 instead of 4.  
+
+;#define M 32
+;#define N 2 * M
+;unsigned int a [N];
+;void foo(){
+; unsigned int j=0;
+;   for (j = 0; j < M - 6; ++j)
+;    {
+;        a[N - 2 * j] = 69;
+;        a[N - 12 - 2 * j] = 7;
+;    }
+;
+;}
+
+; CHECK-LABEL: foo
+; CHECK: <4 x i32>
+; CHECK-NOT: <8 x i32>
+
+@a = common local_unnamed_addr global [64 x i32] zeroinitializer, align 16
+
+; Function Attrs: norecurse nounwind uwtable
+define void @foo() local_unnamed_addr {
+entry:
+  br label %for.body
+
+for.body:                                         
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %0 = shl i64 %indvars.iv, 1
+  %1 = sub nuw nsw i64 64, %0
+  %arrayidx = getelementptr inbounds [64 x i32], [64 x i32]* @a, i64 0, i64 %1
+  store i32 69, i32* %arrayidx, align 8
+  %2 = sub nuw nsw i64 52, %0
+  %arrayidx4 = getelementptr inbounds [64 x i32], [64 x i32]* @a, i64 0, i64 %2
+  store i32 7, i32* %arrayidx4, align 8
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 26
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          
+  ret void
+}