[LV] Print remark when loop cannot be vectorized due to invalid costs.

[sdesmalen]

Summary

This patch emits remarks for instructions that have invalid costs for
a given set of vectorization factors. Some example output:

t.c:4:19: remark: Instruction with invalid costs prevented vectorization at VF=(vscale x 1): load
    dst[i] = sinf(src[i]);
                  ^
t.c:4:14: remark: Instruction with invalid costs prevented vectorization at VF=(vscale x 1, vscale x 2, vscale x 4): call to llvm.sin.f32
    dst[i] = sinf(src[i]);
             ^
t.c:4:12: remark: Instruction with invalid costs prevented vectorization at VF=(vscale x 1): store
    dst[i] = sinf(src[i]);
           ^

[sdesmalen]

Rebased onto D103882 (and updated test)

[kmclaughlin]

This looks good to me, I just have one question on the changes to selectVectorizationFactor

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

6143

nit: should InvalidCosts[0].first be used as the location of the remark from reportVectorizationInfo, since there could be multiple instructions found in the loop with invalid costs?

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

1680

Could you extend the doc-comment here to include the new argument?

6134

Ideally remarks should be easy to understand for end-users, who do not know about LLVM IR (they specifically are not only targeted at LLVM developers). Instead of printing IR directly, it might be more user-friendly to just say something like call to function sin instead of the plain LLVM IR call. Not sure if we have such pretty-printing anywhere else already though.

Including the file/line info where the instruction appears might be a good first step.

llvm/test/Transforms/LoopVectorize/AArch64/scalable-call.ll

100

could you add debug locations to the test and also check that the correct locations are used for the remark?

[sdesmalen]

• Added debug-info to test, and updated comment for expectedCost
• Changed the patch to emit individual remarks, with their corresponding debug-info, instead of a single remark where this info is all compiled together.

e.g.

t.c:4:19: remark: Instruction with invalid costs prevented vectorization at VF=(vscale x 1): load

dst[i] = sinf(src[i]);
              ^

t.c:4:14: remark: Instruction with invalid costs prevented vectorization at VF=(vscale x 1, vscale x 2, vscale x 4): call to llvm.sin.f32

dst[i] = sinf(src[i]);
         ^

t.c:4:12: remark: Instruction with invalid costs prevented vectorization at VF=(vscale x 1): store

dst[i] = sinf(src[i]);
       ^

[sdesmalen]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

6134

@dmgreen also asked a question about that on https://reviews.llvm.org/D105473#2861460
There is precedent for printing IR directly, although I'm not sure if that's necessarily desirable.

What I've done now is:

1. Prints the opcode and in case of a call, also the name of the function.
2. Emit one remark for each function that has invalid cost and pass the individual Instruction so that the remark mechanism can take the file/line/column info from it.

6143

Fair point! The updated patch should address this now. It now emits a remark with corresponding line/column info for each instruction with invalid cost.

[fhahn]

Great! LGTM

llvm/test/Transforms/LoopVectorize/AArch64/scalable-call.ll

3

you should be able to pass the input file directly to FileCheck, no need for cat.

[iii]

llvm-clang-x86_64-expensive-checks-debian (https://lab.llvm.org/buildbot/#/builders/16/builds/13741) fails with:

<<<<<<
            1: remark: <unknown>:0:0: UserVF ignored because of invalid costs. 
            2: remark: t.c:3:10: Instruction with invalid costs prevented vectorization at VF=(vscale x 1): load 
next:102'0                                                                                                      X error: no match found
            3: remark: t.c:3:20: Instruction with invalid costs prevented vectorization at VF=(vscale x 1): call to llvm.sin.f32 
next:102'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
next:102'1             ?                                                                                                          possible intended match

The bot attributed this to my changes (https://reviews.llvm.org/D105629), but they have nothing to do with aarch64 or vectorization, and this test passes locally for me.

@sdesmalen could you take a look please?

[sdesmalen]

In D105806#2879566, @iii wrote:

llvm-clang-x86_64-expensive-checks-debian (https://lab.llvm.org/buildbot/#/builders/16/builds/13741) fails with:

<<<<<<
            1: remark: <unknown>:0:0: UserVF ignored because of invalid costs. 
            2: remark: t.c:3:10: Instruction with invalid costs prevented vectorization at VF=(vscale x 1): load 
next:102'0                                                                                                      X error: no match found
            3: remark: t.c:3:20: Instruction with invalid costs prevented vectorization at VF=(vscale x 1): call to llvm.sin.f32 
next:102'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
next:102'1             ?                                                                                                          possible intended match

The bot attributed this to my changes (https://reviews.llvm.org/D105629), but they have nothing to do with aarch64 or vectorization, and this test passes locally for me.

@sdesmalen could you take a look please?

Hi @iii thanks for pointing it out, I already started looking into this.

[thakis]

Hi, it looks like you landed a determinism fix in dc7bdc1e7121693df112f2fdb11cc6b88580ba4b. Thanks!

However, http://45.33.8.238/win/41940/summary.html is one commit after dc7bdc1e7121693df112f2fdb11cc6b88580ba4b and still has the test failing. Looks like the fix isn't complete.

[thakis]

(Failure output is here: http://45.33.8.238/win/41940/step_11.txt)

[thakis]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

6115

…maybe this needs to be a stable_sort() instead?

[sdesmalen]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

6115

Doh! The latest issue seems caused by the change in rGdc7bdc1e7121693df112f2fdb11cc6b88580ba4b :

const Instruction *AI = A.first, *BI = B.first;
if (AI->getParent() != BI->getParent())
  return AI->getParent() < BI->getParent();   // pointer comparison

I considered writing:

if (AI->getParent() != BI->getParent())
  return false;

So that AI < BI == false && BI < AI == false and that stable_sort would keep it in place, but this doesn't work in practice.
I didn't think of a more suitable way to order the blocks (the dominator tree is not part of CostModel, so I also can't use that).

Any tips?

[thakis]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

6115

Just the usual "if it takes a while to figure out, revert for now to keep the tree working", sorry.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

private:
   /// operate on vector values after type legalization in the backend. If this
   /// latter value is false, then all operations will be scalarized (i.e. no
   /// vectorization has actually taken place).
   using VectorizationCostTy = std::pair<InstructionCost, bool>;
 
   /// Returns the expected execution cost. The unit of the cost does
   /// not matter because we use the 'cost' units to compare different
   /// vector widths. The cost that is returned is *not* normalized by
-  /// the factor width.
-  VectorizationCostTy expectedCost(ElementCount VF);
+  /// the factor width. If \p Invalid is not nullptr, this function
+  /// will add a pair(Instruction*, ElementCount) to \p Invalid for
+  /// each instruction that has an Invalid cost for the given VF.
+  using InstructionVFPair = std::pair<Instruction *, ElementCount>;
+  VectorizationCostTy
+  expectedCost(ElementCount VF,
+               SmallVectorImpl<InstructionVFPair> *Invalid = nullptr);
 
   /// Returns the execution time cost of an instruction for a given vector
   /// width. Vector width of one means scalar.
   VectorizationCostTy getInstructionCost(Instruction *I, ElementCount VF);
 
   /// The cost-computation logic from getInstructionCost which provides
   /// the vector type as an output parameter.
   InstructionCost getInstructionCost(Instruction *I, ElementCount VF,
VectorizationFactor LoopVectorizationCostModel::selectVectorizationFactor(
   bool ForceVectorization = Hints->getForce() == LoopVectorizeHints::FK_Enabled;
   if (ForceVectorization && VFCandidates.size() > 1) {
     // Ignore scalar width, because the user explicitly wants vectorization.
     // Initialize cost to max so that VF = 2 is, at least, chosen during cost
     // evaluation.
     ChosenFactor.Cost = InstructionCost::getMax();
   }
 
+  SmallVector<InstructionVFPair> InvalidCosts;
   for (const auto &i : VFCandidates) {
     // The cost for scalar VF=1 is already calculated, so ignore it.
     if (i.isScalar())
       continue;
 
-    VectorizationCostTy C = expectedCost(i);
+    VectorizationCostTy C = expectedCost(i, &InvalidCosts);
     VectorizationFactor Candidate(i, C.first);
     LLVM_DEBUG(
         dbgs() << "LV: Vector loop of width " << i << " costs: "
                << (Candidate.Cost / Candidate.Width.getKnownMinValue())
                << (i.isScalable() ? " (assuming a minimum vscale of 1)" : "")
                << ".\n");
 
     if (!C.second && !ForceVectorization) {
       LLVM_DEBUG(
           dbgs() << "LV: Not considering vector loop of width " << i
                  << " because it will not generate any vector instructions.\n");
       continue;
     }
 
     // If profitable add it to ProfitableVF list.
     if (isMoreProfitable(Candidate, ScalarCost))
       ProfitableVFs.push_back(Candidate);
 
     if (isMoreProfitable(Candidate, ChosenFactor))
       ChosenFactor = Candidate;
   }
 
+  // Emit a report of VFs with invalid costs in the loop.
+  if (!InvalidCosts.empty()) {
+    // Sort/group per instruction
+    llvm::sort(InvalidCosts, [](InstructionVFPair &A, InstructionVFPair &B) {
+      ElementCountComparator ECC;
+      return A.first->comesBefore(B.first) || ECC(A.second, B.second);
+    });
+
+    // For a list of ordered instruction-vf pairs:
+    //   [(load, vf1), (load, vf2), (store, vf1)]
+    // Group the instructions together to emit separate remarks for:
+    //   load  (vf1, vf2)
+    //   store (vf1)
+    auto Tail = ArrayRef<InstructionVFPair>(InvalidCosts);
+    auto Subset = ArrayRef<InstructionVFPair>();
+    do {
+      if (Subset.empty())
+        Subset = Tail.take_front(1);
+
+      Instruction *I = Subset.front().first;
+
+      // If the next instruction is different, or if there are no other pairs,
+      // emit a remark for the collated subset. e.g.
+      //   [(load, vf1), (load, vf2))]
+      // to emit:
+      //  remark: invalid costs for 'load' at VF=(vf, vf2)
+      if (Subset == Tail || Tail[Subset.size()].first != I) {
+        std::string OutString;
+        raw_string_ostream OS(OutString);
+        assert(!Subset.empty() && "Unexpected empty range");
+        OS << "Instruction with invalid costs prevented vectorization at VF=(";
+        for (auto &Pair : Subset)
+          OS << (Pair.second == Subset.front().second ? "" : ", ")
+             << Pair.second;
+        OS << "):";
+        if (auto *CI = dyn_cast<CallInst>(I))
+          OS << " call to " << CI->getCalledFunction()->getName();
+        else
+          OS << " " << I->getOpcodeName();
+        OS.flush();
+        reportVectorizationInfo(OutString, "InvalidCost", ORE, TheLoop, I);
+        Tail = Tail.drop_front(Subset.size());
+        Subset = {};
+      } else
+        // Grow the subset by one element
+        Subset = Tail.take_front(Subset.size() + 1);
+    } while (!Tail.empty());
+  }
+
   if (!EnableCondStoresVectorization && NumPredStores) {
     reportVectorizationFailure("There are conditional stores.",
         "store that is conditionally executed prevents vectorization",
         "ConditionalStore", ORE, TheLoop);
     ChosenFactor = ScalarCost;
   }
 
   LLVM_DEBUG(if (ForceVectorization && !ChosenFactor.Width.isScalar() &&
while (!Worklist.empty()) {
     Discount += VectorCost - ScalarCost;
     ScalarCosts[I] = ScalarCost;
   }
 
   return *Discount.getValue();
 }
 
 LoopVectorizationCostModel::VectorizationCostTy
-LoopVectorizationCostModel::expectedCost(ElementCount VF) {
+LoopVectorizationCostModel::expectedCost(
+    ElementCount VF, SmallVectorImpl<InstructionVFPair> *Invalid) {
   VectorizationCostTy Cost;
 
   // For each block.
   for (BasicBlock *BB : TheLoop->blocks()) {
     VectorizationCostTy BlockCost;
 
     // For each instruction in the old loop.
     for (Instruction &I : BB->instructionsWithoutDebug()) {
       // Skip ignored values.
       if (ValuesToIgnore.count(&I) ||
           (VF.isVector() && VecValuesToIgnore.count(&I)))
         continue;
 
       VectorizationCostTy C = getInstructionCost(&I, VF);
 
       // Check if we should override the cost.
       if (ForceTargetInstructionCost.getNumOccurrences() > 0)
         C.first = InstructionCost(ForceTargetInstructionCost);
 
+      // Keep a list of instructions with invalid costs.
+      if (Invalid && !C.first.isValid())
+        Invalid->emplace_back(&I, VF);
+
       BlockCost.first += C.first;
       BlockCost.second |= C.second;
       LLVM_DEBUG(dbgs() << "LV: Found an estimated cost of " << C.first
                         << " for VF " << VF << " For instruction: " << I
                         << '\n');
     }
 
     // If we are vectorizing a predicated block, it will have been

llvm/test/Transforms/LoopVectorize/AArch64/scalable-call.ll

-; RUN: opt -S -loop-vectorize -force-vector-interleave=1 -instcombine -mattr=+sve -mtriple aarch64-unknown-linux-gnu -scalable-vectorization=on < %s | FileCheck %s
+; RUN: opt -S -loop-vectorize -force-vector-interleave=1 -instcombine -mattr=+sve -mtriple aarch64-unknown-linux-gnu -scalable-vectorization=on \
+; RUN:     -pass-remarks-missed=loop-vectorize < %s 2>%t | FileCheck %s
+; RUN: cat %t | FileCheck %s --check-prefix=CHECK-REMARKS
 
 define void @vec_load(i64 %N, double* nocapture %a, double* nocapture readonly %b) {
 ; CHECK-LABEL: @vec_load
 ; CHECK: vector.body:
 ; CHECK: %[[LOAD:.*]] = load <vscale x 2 x double>, <vscale x 2 x double>*
 ; CHECK: call <vscale x 2 x double> @foo_vec(<vscale x 2 x double> %[[LOAD]])
 entry:
   %cmp7 = icmp sgt i64 %N, 0
for.body:
   %iv.next = add nuw nsw i64 %iv, 1
   %exitcond = icmp eq i64 %iv.next, %N
   br i1 %exitcond, label %for.end, label %for.body, !llvm.loop !1
 
 for.end:
   ret void
 }
 
+; CHECK-REMARKS: UserVF ignored because of invalid costs.
+; CHECK-REMARKS-NEXT: t.c:3:10: Instruction with invalid costs prevented vectorization at VF=(vscale x 1): load
+; CHECK-REMARKS-NEXT: t.c:3:20: Instruction with invalid costs prevented vectorization at VF=(vscale x 1, vscale x 2): call to llvm.sin.f32
+; CHECK-REMARKS-NEXT: t.c:3:30: Instruction with invalid costs prevented vectorization at VF=(vscale x 1): store
 define void @vec_sin_no_mapping(float* noalias nocapture %dst, float* noalias nocapture readonly %src, i64 %n) {
 ; CHECK: @vec_sin_no_mapping
 ; CHECK: call fast <2 x float> @llvm.sin.v2f32
 ; CHECK-NOT: <vscale x
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %entry, %for.body
   %i.07 = phi i64 [ %inc, %for.body ], [ 0, %entry ]
   %arrayidx = getelementptr inbounds float, float* %src, i64 %i.07
-  %0 = load float, float* %arrayidx, align 4
-  %1 = tail call fast float @llvm.sin.f32(float %0)
+  %0 = load float, float* %arrayidx, align 4, !dbg !11
+  %1 = tail call fast float @llvm.sin.f32(float %0), !dbg !12
   %arrayidx1 = getelementptr inbounds float, float* %dst, i64 %i.07
-  store float %1, float* %arrayidx1, align 4
+  store float %1, float* %arrayidx1, align 4, !dbg !13
   %inc = add nuw nsw i64 %i.07, 1
   %exitcond.not = icmp eq i64 %inc, %n
   br i1 %exitcond.not, label %for.cond.cleanup, label %for.body, !llvm.loop !1
 
 for.cond.cleanup:                                 ; preds = %for.body
   ret void
 }
 
+; CHECK-REMARKS: UserVF ignored because of invalid costs.
+; CHECK-REMARKS-NEXT: t.c:3:10: Instruction with invalid costs prevented vectorization at VF=(vscale x 1): load
+; CHECK-REMARKS-NEXT: t.c:3:20: Instruction with invalid costs prevented vectorization at VF=(vscale x 1, vscale x 2): call to llvm.sin.f32
+; CHECK-REMARKS-NEXT: t.c:3:30: Instruction with invalid costs prevented vectorization at VF=(vscale x 1): store
 define void @vec_sin_fixed_mapping(float* noalias nocapture %dst, float* noalias nocapture readonly %src, i64 %n) {
 ; CHECK: @vec_sin_fixed_mapping
 ; CHECK: call fast <2 x float> @llvm.sin.v2f32
 ; CHECK-NOT: <vscale x
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %entry, %for.body
   %i.07 = phi i64 [ %inc, %for.body ], [ 0, %entry ]
   %arrayidx = getelementptr inbounds float, float* %src, i64 %i.07
-  %0 = load float, float* %arrayidx, align 4
-  %1 = tail call fast float @llvm.sin.f32(float %0) #3
+  %0 = load float, float* %arrayidx, align 4, !dbg !11
+  %1 = tail call fast float @llvm.sin.f32(float %0) #3, !dbg !12
   %arrayidx1 = getelementptr inbounds float, float* %dst, i64 %i.07
-  store float %1, float* %arrayidx1, align 4
+  store float %1, float* %arrayidx1, align 4, !dbg !13
   %inc = add nuw nsw i64 %i.07, 1
   %exitcond.not = icmp eq i64 %inc, %n
   br i1 %exitcond.not, label %for.cond.cleanup, label %for.body, !llvm.loop !1
 
 for.cond.cleanup:                                 ; preds = %for.body
   ret void
 }
 

 attributes #0 = { "vector-function-abi-variant"="_ZGV_LLVM_Nxv_foo(foo_vec)" }
 attributes #1 = { "vector-function-abi-variant"="_ZGV_LLVM_Nxv_bar(bar_vec)" }
 attributes #2 = { "vector-function-abi-variant"="_ZGV_LLVM_Nxv_llvm.sin.f64(sin_vec_nxv2f64)" }
 attributes #3 = { "vector-function-abi-variant"="_ZGV_LLVM_N2v_llvm.sin.f64(sin_vec_v2f64)" }
 
 !1 = distinct !{!1, !2, !3}
 !2 = !{!"llvm.loop.vectorize.width", i32 2}
 !3 = !{!"llvm.loop.vectorize.scalable.enable", i1 true}
+
+!llvm.dbg.cu = !{!4}
+!llvm.module.flags = !{!7}
+!llvm.ident = !{!8}
+
+!4 = distinct !DICompileUnit(language: DW_LANG_C99, file: !5, producer: "clang", isOptimized: true, runtimeVersion: 0, emissionKind: NoDebug, enums: !6, splitDebugInlining: false, nameTableKind: None)
+!5 = !DIFile(filename: "t.c", directory: "somedir")
+!6 = !{}
+!7 = !{i32 2, !"Debug Info Version", i32 3}
+!8 = !{!"clang"}
+!9 = distinct !DISubprogram(name: "foo", scope: !5, file: !5, line: 2, type: !10, scopeLine: 2, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !4, retainedNodes: !6)
+!10 = !DISubroutineType(types: !6)
+!11 = !DILocation(line: 3, column: 10, scope: !9)
+!12 = !DILocation(line: 3, column: 20, scope: !9)
+!13 = !DILocation(line: 3, column: 30, scope: !9)