[LoopVectorize] Don't interleave when the number of runtime checks exceeds the threshold

[TiehuZhang]

Summary

The runtime check threshold should also restrict interleave count. Otherwise, too many runtime checks will be generated for some cases.

[TiehuZhang]

ping

[dmgreen]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7474

isTooManyRuntimeChecks -> hasTooManyRuntimeChecks ?

7548–7549

Why does this check SelectedVF.Width > 1? Can we just remove it or does that not help?

llvm/test/Transforms/LoopVectorize/interleaved-pointer-runtime-check-unprofitable.ll

1 ↗

(On Diff #416894)

If you use -debug, it needs to REQUIRES: asserts
It may be a simpler test to just show that the codegen is not vectorized/interleaved though, with a comment explaining that it would be too much overhead.

3 ↗

(On Diff #416894)

CHECK-LABEL

10 ↗

(On Diff #416894)

There are quite a lot of extra blocks in this test. Can a lot of them be removed?

[fhahn]

llvm/test/Transforms/LoopVectorize/interleaved-pointer-runtime-check-unprofitable.ll

76 ↗

(On Diff #416894)

Please avoid using undef in the test unless necessary.

[dmgreen]

Why does this check SelectedVF.Width > 1? Can we just remove it or does that not help?

Does this mean this didn't help? It seems that code would not alter the IC in any case, as it is already returning VectorizationFactor::Disabled.

Just as a point of cleanup, is it possible to move the logic into selectInterleaveCount, so that it returns a value of 1 if there are too many runtime checks? I'm not sure all the info needed would be easily available inside the costmodel though.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7476

Should this be checking Hints.allowReordering like the other uses of PragmaVectorizeMemoryCheckThreshold?

[TiehuZhang]

In D122126#3413513, @dmgreen wrote:

Why does this check SelectedVF.Width > 1? Can we just remove it or does that not help?

Does this mean this didn't help? It seems that code would not alter the IC in any case, as it is already returning VectorizationFactor::Disabled.

Just as a point of cleanup, is it possible to move the logic into selectInterleaveCount, so that it returns a value of 1 if there are too many runtime checks? I'm not sure all the info needed would be easily available inside the costmodel though.

1. Requirements can not be accessed in selectInterleaveCount, so additional parameters need to be added to selectInterleaveCount. Do you think it is necessary?<br>
2. I'm not sure if I need to keep SelectedVF.Width.getKnownMinValue() > 1, but if it is not necessary, we could remove it in a separate patch.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7548–7549

Probably to reduce compilation time (although the impact is small) ？

llvm/test/Transforms/LoopVectorize/interleaved-pointer-runtime-check-unprofitable.ll

1 ↗

(On Diff #416894)

Done, thanks very much!

76 ↗

(On Diff #416894)

Done, thanks very much!

[dmgreen]

1. Requirements can not be accessed in selectInterleaveCount, so additional parameters need to be added to selectInterleaveCount. Do you think it is necessary?<br>

Yeah - it might need to pass Requirements.getNumRuntimePointerChecks() through to selectInterleaveCount. I think it's OK as you have it right now, but Florian (or anyone else) can complain if they disagree.

2. I'm not sure if I need to keep SelectedVF.Width.getKnownMinValue() > 1, but if it is not necessary, we could remove it in a separate patch.

I was just hoping that if it got to that block then it would prevent the interleaving. It looks like it doesn't work like that though.

LGTM. Perhaps wait a day or two in case anyone else has comments.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7548–7549

Maybe just use a single if now: if (SelectedVF.Width.getKnownMinValue() > 1 && hasTooManyRuntimeChecks()) {

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

323

It would be good to document the helper. Also, requiresTooManyRuntimeChecks may be slightly better, because has seems to imply that the checks are already there to me.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

10458

This check here should be sufficient, there should be no need to also check in selectInterleaveCount.

Could you just move the remark generation & early exit from ::plan here?

You might want to skip those checks if there's a UserVF or UserIC used, with those I think we should always vectorize if possible. It also might be good to add a check line to your test which forces an interleave count > 1.

llvm/test/Transforms/LoopVectorize/interleaved-pointer-runtime-check-unprofitable.ll

1 ↗

(On Diff #419415)

As this relies on the PPC cost-model, this needs to go into the PowerPC subdirectory.

12 ↗

(On Diff #419415)

nit: can change %z_e_8676_1962 to i64 and remove the first load. Also, names could be tidied up a bit.

13 ↗

(On Diff #419415)

nit: it would be good to clean up the names of the blocks a bit more.

[TKaipeng]

In D122126#3418927, @dmgreen wrote:

1. Requirements can not be accessed in selectInterleaveCount, so additional parameters need to be added to selectInterleaveCount. Do you think it is necessary?<br>

Yeah - it might need to pass Requirements.getNumRuntimePointerChecks() through to selectInterleaveCount. I think it's OK as you have it right now, but Florian (or anyone else) can complain if they disagree.

2. I'm not sure if I need to keep SelectedVF.Width.getKnownMinValue() > 1, but if it is not necessary, we could remove it in a separate patch.

I was just hoping that if it got to that block then it would prevent the interleaving. It looks like it doesn't work like that though.

LGTM. Perhaps wait a day or two in case anyone else has comments.

I think SelectedVF.Width.getKnownMinValue() > 1 is used to avoid the check when VF is scalar, but ElementCount::isScalar() seems better.

I don't think the position for the runtimeCheck is good.
Now, the code looks like:
1.If UserVF is OK, do vectorization using UserVF
2.Populate VFCandidates
3.Collect information for vplans
4.Build vplans for all vf candidates and select best VF
5.Check the number of runtime checks for selected VF if it's scalar. If it's too many, stop vectorization.

15234 would be a better order?
1.If UserVF is OK, do vectorization using UserVF
5.Check the number of runtime checks(No need to consider about the VF because the number of runtime checks are same for all VF). If it's too many, stop vectorization.
2.Populate VFCandidates
3.Collect information for vplans
4.Build vplans for all vf candidates

I'm not sure of my opinion. If it's wrong, happy to get a response :)

[fhahn]

Thanks for the update!

In D122126#3421022, @TKaipeng wrote:

I don't think the position for the runtimeCheck is good.
Now, the code looks like:
1.If UserVF is OK, do vectorization using UserVF
2.Populate VFCandidates
3.Collect information for vplans
4.Build vplans for all vf candidates and select best VF
5.Check the number of runtime checks for selected VF if it's scalar. If it's too many, stop vectorization.

15234 would be a better order?
1.If UserVF is OK, do vectorization using UserVF
5.Check the number of runtime checks(No need to consider about the VF because the number of runtime checks are same for all VF). If it's too many, stop vectorization.
2.Populate VFCandidates
3.Collect information for vplans
4.Build vplans for all vf candidates

I'm not sure of my opinion. If it's wrong, happy to get a response :)

It's indeed not at the most optimal position focused solely at compile-time. But I think for this patch, I think it would be good to roughly keep roughly the original order, especially if we manage to check & error at a single place.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

10458

Can the handling be merged into a single check & diagnostic?

[TiehuZhang]

Fix the failed case (optimization-remark-options.c), because the remark info should be updated

[TiehuZhang]

(Updated)
Difference with accepted version: Move memory runtime checks to processLoop to control both VF and IC

[TiehuZhang]

The code has been updated since accept. Please review it again. Thank you very much! @fhahn @dmgreen

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7548–7549

Done. Thanks for your review!

10458

Hi, @fhahn, thanks for your review! It sounds similar to doesNotMeet (https://reviews.llvm.org/D98634), but the difference is that I need to use UserIC and UserVF to control whether this check needs to be performed, right? E.g.

if (!UserVF && LVP.requiresTooManyRuntimeChecks()) {
  /*generate remarks*/
  VF = VectorizationFactor::Disabled();
}

if (!UserIC && LVP.requiresTooManyRuntimeChecks()) {
  /*generate remarks*/
  IC = 1;
}

Could you just move the remark generation & early exit from ::plan here?

You might want to skip those checks if there's a UserVF or UserIC used, with those I think we should always vectorize if possible. It also might be good to add a check line to your test which forces an interleave count > 1.

10458

Hi，@fhahn, thanks for your reply! Does the current version meet the requirements？

10458

Hi, @fhahn, is there any other problem with this patch?

ping

[fhahn]

LGTM with additional suggestions inline, thanks!

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

10462

I think we usually try to use early exits to reduce the indentation, so it might be worth doing something like

if (LVP.requiresTooManyRuntimeChecks()) {
 ORE->emit([&]() {
        return OptimizationRemarkAnalysisAliasing(
                   DEBUG_TYPE, "CantReorderMemOps", L->getStartLoc(),
                   L->getHeader())
               << "loop not vectorized: cannot prove it is safe to reorder "
                  "memory operations";
      });
      LLVM_DEBUG(dbgs() << "LV: Too many memory checks needed.\n");
      Hints.emitRemarkWithHints();
      return false;
}

// Select the interleave count.
 IC = CM.selectInterleaveCount(VF.Width, *VF.Cost.getValue());

(this has the added benefit of not checking for !LVP.requiresTooManyRuntimeChecks() but the unnegated version, which is slightly more straight forward)

llvm/test/Transforms/LoopVectorize/PowerPC/interleaved-pointer-runtime-check-unprofitable.ll

3

Might be good to precommit the test case and then just show the difference in this diff (without the fix ; CHECK: vector.memcheck)

[fhahn]

Still LGTM, thanks! The remaining suggestion can be addressed directly before committing the patch.

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

324

nit: could be turned into const if possible.

[TiehuZhang]

In D122126#3515070, @fhahn wrote:

Still LGTM, thanks! The remaining suggestion can be addressed directly before committing the patch.

Thanks, @fhahn! I'll turn the function into const and add the precommit test when committing the patch

[fhahn]

Thanks!

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

#endif
 
   /// Test a \p Predicate on a \p Range of VF's. Return the value of applying
   /// \p Predicate on Range.Start, possibly decreasing Range.End such that the
   /// returned value holds for the entire \p Range.
   static bool
   getDecisionAndClampRange(const std::function<bool(ElementCount)> &Predicate,
                            VFRange &Range);
 
+  /// Check if the number of runtime checks exceeds the threshold.
+  bool requiresTooManyRuntimeChecks();
+
 protected:
   /// Collect the instructions from the original loop that would be trivially
   /// dead in the vectorized loop if generated.
   void collectTriviallyDeadInstructions(
       SmallPtrSetImpl<Instruction *> &DeadInstructions);
 
   /// Build VPlans for power-of-2 VF's between \p MinVF and \p MaxVF inclusive,
   /// according to the information gathered by Legal when it checked if it is

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

LoopVectorizationPlanner::planInVPlanNativePath(ElementCount UserVF) {
   }
 
   LLVM_DEBUG(
       dbgs() << "LV: Not vectorizing. Inner loops aren't supported in the "
                 "VPlan-native path.\n");
   return VectorizationFactor::Disabled();
 }
 
+bool LoopVectorizationPlanner::requiresTooManyRuntimeChecks() {
+  unsigned NumRuntimePointerChecks = Requirements.getNumRuntimePointerChecks();
+  return (NumRuntimePointerChecks >
+              VectorizerParams::RuntimeMemoryCheckThreshold &&
+          !Hints.allowReordering()) ||
+         NumRuntimePointerChecks > PragmaVectorizeMemoryCheckThreshold;
+}
+
 Optional<VectorizationFactor>
 LoopVectorizationPlanner::plan(ElementCount UserVF, unsigned UserIC) {
   assert(OrigLoop->isInnermost() && "Inner loop expected.");
   FixedScalableVFPair MaxFactors = CM.computeMaxVF(UserVF, UserIC);
   if (!MaxFactors) // Cases that should not to be vectorized nor interleaved.
     return None;
 
   // Invalidate interleave groups if all blocks of loop will be predicated.
LoopVectorizationPlanner::plan(ElementCount UserVF, unsigned UserIC) {
 
   CM.collectInLoopReductions();
   buildVPlansWithVPRecipes(ElementCount::getFixed(1), MaxFactors.FixedVF);
   buildVPlansWithVPRecipes(ElementCount::getScalable(1), MaxFactors.ScalableVF);
 
   LLVM_DEBUG(printPlans(dbgs()));
   if (!MaxFactors.hasVector())
     return VectorizationFactor::Disabled();
 
-  // Select the optimal vectorization factor.
-  auto SelectedVF = CM.selectVectorizationFactor(VFCandidates);
-
-  // Check if it is profitable to vectorize with runtime checks.
-  unsigned NumRuntimePointerChecks = Requirements.getNumRuntimePointerChecks();
-  if (SelectedVF.Width.getKnownMinValue() > 1 && NumRuntimePointerChecks) {
-    bool PragmaThresholdReached =
-        NumRuntimePointerChecks > PragmaVectorizeMemoryCheckThreshold;
-    bool ThresholdReached =
-        NumRuntimePointerChecks > VectorizerParams::RuntimeMemoryCheckThreshold;
-    if ((ThresholdReached && !Hints.allowReordering()) ||
-        PragmaThresholdReached) {
-      ORE->emit([&]() {
-        return OptimizationRemarkAnalysisAliasing(
-                   DEBUG_TYPE, "CantReorderMemOps", OrigLoop->getStartLoc(),
-                   OrigLoop->getHeader())
-               << "loop not vectorized: cannot prove it is safe to reorder "
-                  "memory operations";
-      });
-      LLVM_DEBUG(dbgs() << "LV: Too many memory checks needed.\n");
-      Hints.emitRemarkWithHints();
-      return VectorizationFactor::Disabled();
-    }
-  }
-  return SelectedVF;
+  return CM.selectVectorizationFactor(VFCandidates);
 }
 
 VPlan &LoopVectorizationPlanner::getBestPlanFor(ElementCount VF) const {
   assert(count_if(VPlans,
                   [VF](const VPlanPtr &Plan) { return Plan->hasVF(VF); }) ==
              1 &&
          "Best VF has not a single VPlan.");
 
#endif /* NDEBUG */
 
   // Plan how to best vectorize, return the best VF and its cost.
   Optional<VectorizationFactor> MaybeVF = LVP.plan(UserVF, UserIC);
 
   VectorizationFactor VF = VectorizationFactor::Disabled();
   unsigned IC = 1;
 
   if (MaybeVF) {
+    if (!LVP.requiresTooManyRuntimeChecks()) {
       VF = *MaybeVF;
       // Select the interleave count.
       IC = CM.selectInterleaveCount(VF.Width, *VF.Cost.getValue());
+    } else {
+      ORE->emit([&]() {
+        return OptimizationRemarkAnalysisAliasing(
+                   DEBUG_TYPE, "CantReorderMemOps", L->getStartLoc(),
+                   L->getHeader())
+               << "loop not vectorized: cannot prove it is safe to reorder "
+                  "memory operations";
+      });
+      LLVM_DEBUG(dbgs() << "LV: Too many memory checks needed.\n");
+      Hints.emitRemarkWithHints();
+      return false;
+    }
   }
 
   // Identify the diagnostic messages that should be produced.
   std::pair<StringRef, std::string> VecDiagMsg, IntDiagMsg;
   bool VectorizeLoop = true, InterleaveLoop = true;
   if (VF.Width.isScalar()) {
     LLVM_DEBUG(dbgs() << "LV: Vectorization is possible but not beneficial.\n");
     VecDiagMsg = std::make_pair(

llvm/test/Transforms/LoopVectorize/PowerPC/interleaved-pointer-runtime-check-unprofitable.ll

+; RUN: opt -mtriple=powerpc64-unknown-linux-gnu -mcpu=a2 -S -loop-vectorize  < %s -o - | FileCheck %s
+ 
+; The case will do aggressive interleave on PowerPC, resulting in a lot of memory checks.
+; (On the A2, always unroll aggressively. In fact, if aggressive interleaving is enabled,
+; similar issues may occur on other targets).
+; Interleaving should also be restricted by the threshold of memory checks similar to VF.
+; (e.g., runtime-memory-check-threshold, default 8).
+ 
+; CHECK-LABEL: @eddy_diff_caleddy_
+; CHECK-NOT: vector.memcheck
+ 
+define fastcc void @eddy_diff_caleddy_(i64* %wet_cl, i64 %0, i32 %ncol.cast.val) {
+entry:
+  %trip.count = add nuw i32 %ncol.cast.val, 1
+  %wide.trip.count = zext i32 %ncol.cast.val to i64
+  %1 = shl i64 %0, 1
+  %2 = mul i64 %0, 3
+  %3 = shl i64 %0, 2
+  %4 = mul i64 %0, 5
+  %5 = mul i64 %0, 6
+  %6 = mul i64 %0, 7
+  %7 = shl i64 %0, 3
+  %8 = mul i64 %0, 9
+  %9 = mul i64 %0, 10
+  %10 = mul i64 %0, 11
+  %11 = mul i64 %0, 12
+  br label %loop.body
+ 
+loop.body:
+  %indvars.iv774 = phi i64 [ 0, %entry ], [ %indvars.iv.next775, %loop.body ]
+  %12 = add nsw i64 %indvars.iv774, -5
+  %13 = add i64 %12, %0
+  %14 = getelementptr i64, i64* %wet_cl, i64 %13
+  %15 = bitcast i64* %14 to double*
+  store double 0.000000e+00, double* %15, align 8
+  %16 = add i64 %12, %1
+  %17 = getelementptr i64, i64* %wet_cl, i64 %16
+  %18 = bitcast i64* %17 to double*
+  store double 0.000000e+00, double* %18, align 8
+  %19 = add i64 %12, %2
+  %20 = getelementptr i64, i64* %wet_cl, i64 %19
+  %21 = bitcast i64* %20 to double*
+  store double 0.000000e+00, double* %21, align 8
+  %22 = add i64 %12, %3
+  %23 = getelementptr i64, i64* %wet_cl, i64 %22
+  %24 = bitcast i64* %23 to double*
+  store double 0.000000e+00, double* %24, align 8
+  %25 = add i64 %12, %4
+  %26 = getelementptr i64, i64* %wet_cl, i64 %25
+  %27 = bitcast i64* %26 to double*
+  store double 0.000000e+00, double* %27, align 8
+  %28 = add i64 %12, %5
+  %29 = getelementptr i64, i64* %wet_cl, i64 %28
+  %30 = bitcast i64* %29 to double*
+  store double 0.000000e+00, double* %30, align 8
+  %31 = add i64 %12, %6
+  %32 = getelementptr i64, i64* %wet_cl, i64 %31
+  %33 = bitcast i64* %32 to double*
+  store double 0.000000e+00, double* %33, align 8
+  %34 = add i64 %12, %7
+  %35 = getelementptr i64, i64* %wet_cl, i64 %34
+  %36 = bitcast i64* %35 to double*
+  store double 0.000000e+00, double* %36, align 8
+  %37 = add i64 %12, %8
+  %38 = getelementptr i64, i64* %wet_cl, i64 %37
+  %39 = bitcast i64* %38 to double*
+  store double 0.000000e+00, double* %39, align 8
+  %40 = add i64 %12, %9
+  %41 = getelementptr i64, i64* %wet_cl, i64 %40
+  %42 = bitcast i64* %41 to double*
+  store double 0.000000e+00, double* %42, align 8
+  %43 = add i64 %12, %10
+  %44 = getelementptr i64, i64* %wet_cl, i64 %43
+  %45 = bitcast i64* %44 to double*
+  store double 0.000000e+00, double* %45, align 8
+  %46 = add i64 %12, %11
+  %47 = getelementptr i64, i64* %wet_cl, i64 %46
+  %48 = bitcast i64* %47 to double*
+  store double 0.000000e+00, double* %48, align 8
+  %indvars.iv.next775 = add nuw nsw i64 %indvars.iv774, 1
+  %exitcond778.not = icmp eq i64 %indvars.iv.next775, %wide.trip.count
+  br i1 %exitcond778.not, label %loop.end, label %loop.body
+ 
+loop.end:
+  ret void
+}