[LV] Forced vectorization with runtime checks and OptForSize

[SjoerdMeijer]

Summary

When vectorization is forced with a pragma, we optimise for min size, and we need to emit runtime memory checks, then allow this code growth and don't run in an assert like we currently do.

[uabelho]

It fixes the problem I reported. Thanks!

[Ayal]

When we optimise for size, and need to emit runtime checks to disambiguate memory, we should nicely bail, don't vectorise, and not run in an assert like we currently do.

The logic currently in place to do so is to call LVP.plan() which calls computeMaxVF(), which does

// Bail if runtime checks are required, which are not good when optimising
// for size.
if (runtimeChecksRequired())
  return None;

Does this need to change, presumably move earlier?

[SjoerdMeijer]

Thanks. The runtime check is now done earlier.

[Ayal]

Which commit does this trace back to, D65197? Why is the current logic placed too late, and should it be removed if moved earlier as suggested? Add a reference to the problem @uabelho reported.

[SjoerdMeijer]

Which commit does this trace back to, D65197?

This is the result of D65197 and D66803. The former was the functional change, the latter changed the assert that is now triggered.

Add a reference to the problem @uabelho reported.

There is no corresponding PR for this. The problem reported by @uabelho is added here as a test-case/regression test.

Why is the current logic placed too late, and should it be removed if moved earlier as suggested?

Initially I didn't understand this remark, because I thought I had moved the new logic to happen earlier. But having thought about it, I think your question actually is why the existing logic doesn't work, why it doesn't capture this case as it looks like it should. Thus, this extra bit of logic added in this patch shouldn't be necessary, at least not in this form.

And I agree with that. I think in the existing logic there's a F->hasOptSize() check missing. I am going to look again...

[SjoerdMeijer]

Ah, I had completely missed that this is about the interaction of OptForSize and the loop.vectorize loop hint!
Vectorization is forced, which means that we vectorize even though OptForSize is set and we need to emit runtime checks.

The symptom is that we run in this assert in emitMemRuntimeChecks():

assert(!BB->getParent()->hasOptSize() &&
     "Cannot emit memory checks when optimizing for size");

In getScalarEpilogueLowering(), we do not set CM_ScalarEpilogueNotAllowedOptSize because of the loop hint:

if (Hints.getForce() != LoopVectorizeHints::FK_Enabled &&
    (F->hasOptSize() ||
     llvm::shouldOptimizeForSize(L->getHeader(), PSI, BFI))) {
  SEL = CM_ScalarEpilogueNotAllowedOptSize;

And because CM_ScalarEpilogueNotAllowedOptSize is not set, we do not check runtimeChecksRequired, so that we end up with code growth under OptForSize because of the loop hint.

If we agree that this is desired behaviour, which looks reasonable to me because of this condition, I am going to remove the assert as that is not valid.

[Ayal]

In D67764#1678098, @SjoerdMeijer wrote:

Ah, I had completely missed that this is about the interaction of OptForSize and the loop.vectorize loop hint!
Vectorization is forced, which means that we vectorize even though OptForSize is set and we need to emit runtime checks.

The symptom is that we run in this assert in emitMemRuntimeChecks():

assert(!BB->getParent()->hasOptSize() &&
     "Cannot emit memory checks when optimizing for size");

In getScalarEpilogueLowering(), we do not set CM_ScalarEpilogueNotAllowedOptSize because of the loop hint:

if (Hints.getForce() != LoopVectorizeHints::FK_Enabled &&
    (F->hasOptSize() ||
     llvm::shouldOptimizeForSize(L->getHeader(), PSI, BFI))) {
  SEL = CM_ScalarEpilogueNotAllowedOptSize;

And because CM_ScalarEpilogueNotAllowedOptSize is not set, we do not check runtimeChecksRequired, so that we end up with code growth under OptForSize because of the loop hint.

If we agree that this is desired behaviour, which looks reasonable to me because of this condition, I am going to remove the assert as that is not valid.

Better to make the assert valid by checking !forcedToVectorize in addition to !OptForSize.

[Ayal]

In D67764#1678112, @Ayal wrote:

Better to make the assert valid by checking !forcedToVectorize in addition to !OptForSize.

and also dump some warning.

[SjoerdMeijer]

Restored the assert and expanded it with the !forcedToVectorize check

[Ayal]

So starting from D65197 or so, a loop that is forced to vectorize in a function that is OptForSize, is expected to get vectorized even if it involves replicating the loop.
Another assert which presumably requires similar update is the "Cannot SCEV check stride or overflow when optimizing for size" one.

llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h

315 ↗

(On Diff #221211)

Method itself should be const.
Could alternatively get Hints from CostModel.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

2733–2746

Assert message should say it all, i.e., "... when optimizing for size unless forced to vectorize"; above documentation seems redundant.

In case we are forced to vectorize, optimize for size, and end up replicating the loop due to runtime checks, we should issue an LLVM_DEBUG/ORE message, informing the programmer code bloat may be reduced by removing the forced vectorization, or perhaps by modifying the code s.t. runtime checks are not needed (e.g., adding "restrict").

llvm/test/Transforms/LoopVectorize/runtime-check-optsize.ll

1 ↗

(On Diff #221211)

Suffice to run loop-vectorize only, instead of -O1?

Would be good to add this test to a relevant file, instead of dedicating a new file for each test.

[SjoerdMeijer]

All comments addressed.

[SjoerdMeijer]

Another assert which presumably requires similar update is the "Cannot SCEV check stride or overflow when optimizing for size" one.

Yep, you're exactly right. Fallout from the same work.
We have a PR for that one, https://bugs.llvm.org/show_bug.cgi?id=43371, which I will give exactly the same treatment as soon as this change is accepted.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

2737

Check is redundant, Forced is asserted.

Probably need to have a dummy use of Forced, or avoid defining it, to avoid warning of unused variable in release mode.

llvm/test/Transforms/LoopVectorize/runtime-check.ll

185

This check line belongs to previous test

[SjoerdMeijer]

sorry, forgot to clean that up, keep the original order

[Ayal]

llvm/test/Transforms/LoopVectorize/runtime-check.ll

187

missing optsize attribute?

[SjoerdMeijer]

Added minsize func attr, and also added the check for the new vectorization remark, which I had also missed porting to the new test file... :-( Thanks for spotting. The fix for the other assert will be better than this...

[Ayal]

This LGTM, thanks for fixing!

[SjoerdMeijer]

Many thanks for reviewing!
Will now look at PR43371

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

void InnerLoopVectorizer::emitMemRuntimeChecks(Loop *L, BasicBlock *Bypass) {
   // faster.
   Instruction *FirstCheckInst;
   Instruction *MemRuntimeCheck;
   std::tie(FirstCheckInst, MemRuntimeCheck) =
       Legal->getLAI()->addRuntimeChecks(BB->getTerminator());
   if (!MemRuntimeCheck)
     return;
 
-  assert(!BB->getParent()->hasOptSize() &&
-         "Cannot emit memory checks when optimizing for size");
+  if (BB->getParent()->hasOptSize()) {
+    bool Forced = Cost->Hints->getForce() == LoopVectorizeHints::FK_Enabled;
+    assert(Forced && "Cannot emit memory checks when optimizing for size, "
+                     "unless forced to vectorize.");
+    if (Forced)
+      ORE->emit([&]() {
+        return OptimizationRemarkAnalysis(DEBUG_TYPE, "VectorizationCodeSize",
+                                          L->getStartLoc(), L->getHeader())
+               << "Code-size may be reduced by removing forced "
+                  "vectorization, or by source-code modifications "
+                  "eliminating the need for runtime checks "
+                  "(e.g., adding 'restrict').";
+      });
+  }
 
   // Create a new block containing the memory check.
   BB->setName("vector.memcheck");
   auto *NewBB = BB->splitBasicBlock(BB->getTerminator(), "vector.ph");
   // Update dominator tree immediately if the generated block is a
   // LoopBypassBlock because SCEV expansions to generate loop bypass
   // checks may query it before the current function is finished.
   DT->addNewBlock(NewBB, BB);

llvm/test/Transforms/LoopVectorize/runtime-check.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s  -loop-vectorize -force-vector-interleave=1 -force-vector-width=4 -dce -instcombine -S | FileCheck %s
+; RUN: opt < %s -loop-vectorize -force-vector-interleave=1 -force-vector-width=4 -dce -instcombine -S | FileCheck %s
+; RUN: opt < %s -loop-vectorize -disable-basicaa -S -pass-remarks-analysis='loop-vectorize' 2>&1 | FileCheck %s -check-prefix=FORCED_OPTSIZE
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 
 ; Make sure we vectorize this loop:
 ; int foo(float *a, float *b, int n) {
 ;   for (int i=0; i<n; ++i)
 ;     a[i] = b[i] * 3;
 ; }
for.body:
   %iv.next = add nuw nsw i64 %iv, 1
   %exitcond = icmp eq i64 %iv.next, %n
   br i1 %exitcond, label %loopexit, label %for.body
 
 loopexit:
   ret void
 }
 
+define dso_local void @forced_optsize(i64* noalias nocapture readonly %x_p, i64* noalias nocapture readonly %y_p, i64* noalias nocapture %z_p) local_unnamed_addr #0 {
+; FORCED_OPTSIZE-LABEL: @forced_optsize(
+; FORCED_OPTSIZE:       vector.body:
+entry:
+  br label %for.body
+
+for.cond.cleanup:
+  ret void
+
+for.body:
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %arrayidx = getelementptr inbounds i64, i64* %x_p, i64 %indvars.iv
+  %0 = load i64, i64* %arrayidx, align 8
+  %arrayidx2 = getelementptr inbounds i64, i64* %y_p, i64 %indvars.iv
+  %1 = load i64, i64* %arrayidx2, align 8
+  %add = add nsw i64 %1, %0
+  %arrayidx4 = getelementptr inbounds i64, i64* %z_p, i64 %indvars.iv
+  store i64 %add, i64* %arrayidx4, align 8
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 128
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body, !llvm.loop !12
+}
+
+
 ; CHECK: !9 = !DILocation(line: 101, column: 1, scope: !{{.*}})
 
 !llvm.module.flags = !{!0, !1}
 !llvm.dbg.cu = !{!9}
 !0 = !{i32 2, !"Dwarf Version", i32 4}
 !1 = !{i32 2, !"Debug Info Version", i32 3}
 
 !2 = !{}
 !3 = !DISubroutineType(types: !2)
 !4 = !DIFile(filename: "test.cpp", directory: "/tmp")
 !5 = distinct !DISubprogram(name: "foo", scope: !4, file: !4, line: 99, type: !3, isLocal: false, isDefinition: true, scopeLine: 100, flags: DIFlagPrototyped, isOptimized: false, unit: !9, retainedNodes: !2)
 !6 = !DILocation(line: 100, column: 1, scope: !5)
 !7 = !DILocation(line: 101, column: 1, scope: !5)
 !8 = !DILocation(line: 102, column: 1, scope: !5)
 !9 = distinct !DICompileUnit(language: DW_LANG_C99, producer: "clang",
                              file: !10,
                              isOptimized: true, flags: "-O2",
                              splitDebugFilename: "abc.debug", emissionKind: 2)
 !10 = !DIFile(filename: "path/to/file", directory: "/path/to/dir")
 !11 = !{i32 2, !"Debug Info Version", i32 3}
+!12 = distinct !{!12, !13, !14}
+!13 = !{!"llvm.loop.vectorize.width", i32 2}
+!14 = !{!"llvm.loop.vectorize.enable", i1 true}