[AArch64][LoopVectorize] Disable tail-folding for SVE when loop has interleaved accesses

[david-arm]

Summary

If we have interleave groups in the loop we want to vectorise then
we should fall back on normal vectorisation with a scalar epilogue. In
such cases when tail-folding is enabled we'll almost certainly go on to
create vplans with very high costs for all vector VFs and fall back on
VF=1 anyway. This is likely to be worse than if we'd just used an
unpredicated vector loop in the first place.

Once the vectoriser has proper support for analysing all the costs
for each combination of VF and vectorisation style, then we should
be able to remove this.

Added an extra test here:

Transforms/LoopVectorize/AArch64/sve-tail-folding-option.ll

[sdesmalen]

llvm/include/llvm/Analysis/VectorUtils.h

814

nit: s/haveGroups/hasGroups/ ?

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5074

I'm not sure I understand where the UserVF comes into play with this choice, given that this a choice between "tail folding" vs "scalar epilogue". Can you elaborate?

llvm/test/Transforms/LoopVectorize/AArch64/sve-tail-folding-interleave.ll

2

Why is this loop still vectorized with a VF of 8?

[fhahn]

llvm/test/Transforms/LoopVectorize/AArch64/sve-tail-folding-interleave.ll

2

This needs REQUIRES: asserts I think, as it uses -debug, same for the other test. Could. you precommit the tests, so only the impact of the patch is shown in this diff?

10

nit: everything expcept the no alias attribute appears to be unnecessary

[david-arm]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5074

So there is a MVE test that tries to force the use of tail-folding for a loop with masked interleaved accesses, and the test forces a particular VF. So I had two choices here:

1. Either fix the test to reflect the new behaviour, or
2. In cases where the user has explicitly requested tail-folding and forced a VF, then probably the user really wants tail-folding enabled for that VF.

Alternatively I could add a brand new flag controlling this behaviour, something like -use-tail-folding-when-interleaving, etc.

[david-arm]

llvm/test/Transforms/LoopVectorize/AArch64/sve-tail-folding-interleave.ll

2

Hi @sdesmalen, this is actually what we want to happen because this is a loop with interleaved memory accesses where NEON can do this very efficiently. It's actually a VF of 4, but we have the <8 x float> and <12 x float> types in the loop due to deinterleaving loads and interleaving stores, respectively. What this patch is doing is instructing the vectoriser to disable tail folding because performance is likely to be terrible, and instead fall back on normal unpredicated vector loops that don't require masked interleaved accesses.

[david-arm]

• Cleaned up tests.
• Renamed haveGroups -> hasGroups.

[dmgreen]

In terms of MVE - A VLD2/VLD4 cannot be predicated so in that regards we do not support "MaskedInterleavedAccesses". There is code in canTailPredicateLoop that attempts to get that right. Any other interleaving group width will be emulated with a gather/scatter though, which can happily be masked.
https://godbolt.org/z/KzvEqz439

For SVE my understanding is that LD2/LD3/LD4 can be predicated, and other widths (and current codegen as interleaving is not yet supported) will use gather/scatter which can be masked. In the long run they may have MaskedInterleavedAccesses returning true.

Is the problem that we are trying to use one variable for both Neon and SVE vectorization, where SVE prefers folding the tail, and NEON will need not to?

[david-arm]

In D128342#3615721, @dmgreen wrote:

In terms of MVE - A VLD2/VLD4 cannot be predicated so in that regards we do not support "MaskedInterleavedAccesses". There is code in canTailPredicateLoop that attempts to get that right. Any other interleaving group width will be emulated with a gather/scatter though, which can happily be masked.
https://godbolt.org/z/KzvEqz439

For SVE my understanding is that LD2/LD3/LD4 can be predicated, and other widths (and current codegen as interleaving is not yet supported) will use gather/scatter which can be masked. In the long run they may have MaskedInterleavedAccesses returning true.

Is the problem that we are trying to use one variable for both Neon and SVE vectorization, where SVE prefers folding the tail, and NEON will need not to?

Hi @dmgreen, when I first discovered this issue it gave me a headache! The fundamental problem here is that we don't create a matrix of vplan costs with vectorisation style (tail-folding, vector loop + scalar epilogue, etc.) as one axis and VF as the other. This means we cannot look at all possible permutations and choose the lowest cost combination, so our only option is to decide up-front whether or not to use tail-folding before we've calculated any costs.

We currently don't have support for interleaving with SVE using ld2/st2/etc because we cannot rely upon shufflevector in the same way that fixed-width vectorisation does. This means that if we choose to tail-fold a loop with masked interleaved accesses the costs for both NEON and SVE will be so high that we will not vectorise at all. Whereas if we didn't choose to tail-fold we'd actually end up vectorising the interleaved memory accesses using NEON's ld2/st3, which is still faster than a scalar loop. So what I'm trying to do here is avoid causing regressions when enabling tail-folding for any target that does not support masked interleaved memory accesses. If at some point in the future we can support them for SVE then useMaskedInterleavedAccesses will return true.

[dmgreen]

Hi @dmgreen, when I first discovered this issue it gave me a headache! The fundamental problem here is that we don't create a matrix of vplan costs with vectorisation style (tail-folding, vector loop + scalar epilogue, etc.) as one axis and VF as the other. This means we cannot look at all possible permutations and choose the lowest cost combination, so our only option is to decide up-front whether or not to use tail-folding before we've calculated any costs.

We currently don't have support for interleaving with SVE using ld2/st2/etc because we cannot rely upon shufflevector in the same way that fixed-width vectorisation does. This means that if we choose to tail-fold a loop with masked interleaved accesses the costs for both NEON and SVE will be so high that we will not vectorise at all. Whereas if we didn't choose to tail-fold we'd actually end up vectorising the interleaved memory accesses using NEON's ld2/st3, which is still faster than a scalar loop. So what I'm trying to do here is avoid causing regressions when enabling tail-folding for any target that does not support masked interleaved memory accesses. If at some point in the future we can support them for SVE then useMaskedInterleavedAccesses will return true.

Yeah I remember that causing problems for Sjoerd on MVE in the past, with it deciding too much up-front.

Would it be possible to treat this the same way as MVE does - return false for preferPredicateOverEpilogue if the stride of a memory access is 2 or 3 or 4. That would prevent the MVE side getting worse. (It's not a lot worse, but predicating the loop is better than not doing it in the second example up above). And in the long run we can try to keep pushing the vectorizer towards being able to cost different vplans against one another.

[david-arm]

Hi @dmgreen, I can certainly look into this! I'd just assumed that trying to have predicated loops for targets that don't have masked interleaved accesses would be bad in general that's all. It means falling back on gather/scatters or scalarising, either of which is usually very expensive.

It looks like in LoopVectorizePass::processLoop we set up the InterleavedAccessInfo object after we've called getScalarEpilogueLowering, which is a shame but perhaps I can shuffle things around.

[david-arm]

• Changed to using the TTI hook 'preferPredicateOverEpilogue' in order to make the decision about whether to use tail-folding or not. This requires refactoring the LoopVectorizer.cpp code a little in order to pass in the InterleaveAccessInfo object.

[kmclaughlin]

Hi @david-arm, this change looks reasonable to me. Can you please wait a day or so before landing, just to make sure the other reviewers have a chance to look at it again?

llvm/include/llvm/Analysis/VectorUtils.h

public:
   /// out-of-bounds requires a scalar epilogue iteration for correctness.
   bool requiresScalarEpilogue() const { return RequiresScalarEpilogue; }
 
   /// Invalidate groups that require a scalar epilogue (due to gaps). This can
   /// happen when optimizing for size forbids a scalar epilogue, and the gap
   /// cannot be filtered by masking the load/store.
   void invalidateGroupsRequiringScalarEpilogue();
 
+  bool hasGroups() const { return !InterleaveGroups.empty(); }
+
 private:
   /// A wrapper around ScalarEvolution, used to add runtime SCEV checks.
   /// Simplifies SCEV expressions in the context of existing SCEV assumptions.
   /// The interleaved access analysis can also add new predicates (for example
   /// by versioning strides of pointers).
   PredicatedScalarEvolution &PSE;
 
   Loop *TheLoop;

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

if (TheLoop->getExitingBlock() != TheLoop->getLoopLatch()) {
     }
     return FixedScalableVFPair::getNone();
   }
 
   // Now try the tail folding
 
   // Invalidate interleave groups that require an epilogue if we can't mask
   // the interleave-group.
-  if (!useMaskedInterleavedAccesses(TTI)) {
+  if (InterleaveInfo.hasGroups() && !useMaskedInterleavedAccesses(TTI)) {
     assert(WideningDecisions.empty() && Uniforms.empty() && Scalars.empty() &&
            "No decisions should have been taken at this point");
+
+    // If the target doesn't have masked interleaved accesses, then it's very
+    // likely the costs will be far too high to consider vectorising, e.g. see
+    // where useEmulatedMaskMemRefHack is used. If we're permitted to fall back
+    // on an unpredicated vector loop + scalar epilogue then let's do it now.
+    if (UserVF.isZero() &&
+        ScalarEpilogueStatus == CM_ScalarEpilogueNotNeededUsePredicate) {
+      LLVM_DEBUG(dbgs() << "LV: Not folding tail by masking due to "
+                           "interleaving: vectorize with a scalar epilogue "
+                           "instead.\n");
+      ScalarEpilogueStatus = CM_ScalarEpilogueAllowed;
+      return computeFeasibleMaxVF(TC, UserVF, false);
+    }
+
     // Note: There is no need to invalidate any cost modeling decisions here, as
     // non where taken so far.
     InterleaveInfo.invalidateGroupsRequiringScalarEpilogue();
   }
 
   FixedScalableVFPair MaxFactors = computeFeasibleMaxVF(TC, UserVF, true);
   // Avoid tail folding if the trip count is known to be a multiple of any VF
   // we chose.

llvm/test/Transforms/LoopVectorize/AArch64/sve-tail-folding-interleave.ll

+; REQUIRES: asserts
+; RUN: opt -loop-vectorize -S -prefer-predicate-over-epilogue=predicate-else-scalar-epilogue \
+; RUN:   -debug < %s 2>%t | FileCheck %s
+; RUN: cat %t | FileCheck --check-prefix=DEBUG %s
+
+target triple = "aarch64-unknown-linux-gnu"
+
+; DEBUG: Not folding tail by masking due to interleaving: vectorize with a scalar epilogue instead.
+
+define void @foo(ptr noalias %dst, ptr noalias %src, i64 %n) #0 {
+; CHECK-LABEL: @foo(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[N:%.*]], 4
+; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]
+; CHECK:       vector.ph:
+; CHECK-NEXT:    [[N_MOD_VF:%.*]] = urem i64 [[N]], 4
+; CHECK-NEXT:    [[N_VEC:%.*]] = sub i64 [[N]], [[N_MOD_VF]]
+; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
+; CHECK:       vector.body:
+; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
+; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[INDEX]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw nsw i64 [[TMP0]], 1
+; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds float, ptr [[SRC:%.*]], i64 [[TMP1]]
+; CHECK-NEXT:    [[TMP3:%.*]] = getelementptr inbounds float, ptr [[TMP2]], i32 0
+; CHECK-NEXT:    [[WIDE_VEC:%.*]] = load <8 x float>, ptr [[TMP3]], align 4
+; CHECK-NEXT:    [[STRIDED_VEC:%.*]] = shufflevector <8 x float> [[WIDE_VEC]], <8 x float> poison, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
+; CHECK-NEXT:    [[STRIDED_VEC1:%.*]] = shufflevector <8 x float> [[WIDE_VEC]], <8 x float> poison, <4 x i32> <i32 1, i32 3, i32 5, i32 7>
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw nsw i64 [[TMP0]], 3
+; CHECK-NEXT:    [[TMP5:%.*]] = add nuw nsw i64 [[TMP4]], 2
+; CHECK-NEXT:    [[TMP6:%.*]] = getelementptr inbounds float, ptr [[DST:%.*]], i64 [[TMP5]]
+; CHECK-NEXT:    [[TMP7:%.*]] = getelementptr inbounds float, ptr [[TMP6]], i32 -2
+; CHECK-NEXT:    [[TMP8:%.*]] = shufflevector <4 x float> [[STRIDED_VEC]], <4 x float> [[STRIDED_VEC1]], <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
+; CHECK-NEXT:    [[TMP9:%.*]] = shufflevector <8 x float> [[TMP8]], <8 x float> <float 3.000000e+00, float 3.000000e+00, float 3.000000e+00, float 3.000000e+00, float undef, float undef, float undef, float undef>, <12 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7, i32 8, i32 9, i32 10, i32 11>
+; CHECK-NEXT:    [[INTERLEAVED_VEC:%.*]] = shufflevector <12 x float> [[TMP9]], <12 x float> poison, <12 x i32> <i32 0, i32 4, i32 8, i32 1, i32 5, i32 9, i32 2, i32 6, i32 10, i32 3, i32 7, i32 11>
+; CHECK-NEXT:    store <12 x float> [[INTERLEAVED_VEC]], ptr [[TMP7]], align 4
+; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
+; CHECK-NEXT:    [[TMP10:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
+; CHECK-NEXT:    br i1 [[TMP10]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP0:![0-9]+]]
+;
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %i.021 = phi i64 [ %inc, %for.body ], [ 0, %entry ]
+  %mul = shl nuw nsw i64 %i.021, 1
+  %arrayidx = getelementptr inbounds float, ptr %src, i64 %mul
+  %0 = load float, ptr %arrayidx, align 4
+  %mul1 = mul nuw nsw i64 %i.021, 3
+  %arrayidx2 = getelementptr inbounds float, ptr %dst, i64 %mul1
+  store float %0, ptr %arrayidx2, align 4
+  %add = or i64 %mul, 1
+  %arrayidx4 = getelementptr inbounds float, ptr %src, i64 %add
+  %1 = load float, ptr %arrayidx4, align 4
+  %add6 = add nuw nsw i64 %mul1, 1
+  %arrayidx7 = getelementptr inbounds float, ptr %dst, i64 %add6
+  store float %1, ptr %arrayidx7, align 4
+  %add9 = add nuw nsw i64 %mul1, 2
+  %arrayidx10 = getelementptr inbounds float, ptr %dst, i64 %add9
+  store float 3.000000e+00, ptr %arrayidx10, align 4
+  %inc = add nuw nsw i64 %i.021, 1
+  %exitcond.not = icmp eq i64 %inc, %n
+  br i1 %exitcond.not, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body, %entry
+  ret void
+}
+
+attributes #0 = { vscale_range(1,16) "target-features"="+sve" }

llvm/test/Transforms/LoopVectorize/tail-folding-interleave.ll

+; RUN: opt -loop-vectorize -S -prefer-predicate-over-epilogue=predicate-else-scalar-epilogue \
+; RUN:   -enable-interleaved-mem-accesses -debug -disable-output < %s 2>&1 | FileCheck %s
+
+; CHECK: Not folding tail by masking due to interleaving: vectorize with a scalar epilogue instead.
+
+define void @foo(ptr noalias %dst, ptr noalias %src, i64 noundef %n) {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %i.021 = phi i64 [ %inc, %for.body ], [ 0, %entry ]
+  %mul = shl nuw nsw i64 %i.021, 1
+  %arrayidx = getelementptr inbounds float, ptr %src, i64 %mul
+  %0 = load float, ptr %arrayidx, align 4
+  %mul1 = mul nuw nsw i64 %i.021, 3
+  %arrayidx2 = getelementptr inbounds float, ptr %dst, i64 %mul1
+  store float %0, ptr %arrayidx2, align 4
+  %add = or i64 %mul, 1
+  %arrayidx4 = getelementptr inbounds float, ptr %src, i64 %add
+  %1 = load float, ptr %arrayidx4, align 4
+  %add6 = add nuw nsw i64 %mul1, 1
+  %arrayidx7 = getelementptr inbounds float, ptr %dst, i64 %add6
+  store float %1, ptr %arrayidx7, align 4
+  %add9 = add nuw nsw i64 %mul1, 2
+  %arrayidx10 = getelementptr inbounds float, ptr %dst, i64 %add9
+  store float 3.000000e+00, ptr %arrayidx10, align 4
+  %inc = add nuw nsw i64 %i.021, 1
+  %exitcond.not = icmp eq i64 %inc, %n
+  br i1 %exitcond.not, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body, %entry
+  ret void
+}