[LV] Tail-folding with runtime memory checks

[SjoerdMeijer]

Summary

The loop vectorizer is running in an assert when it tries to fold the tail and
has to emit runtime memory disambiguation checks. This happens as soon as
you try to do something like:

#pragma clang loop predicate(enable)
for (int i=0; i < N; i++)
  A[i] = B[i] + C[i];

where A, B, and C are integer pointers, not annotated with e.g. the restrict
type qualifier.

However, it looks like the logic to deal with this is all in place, so this
simply removes the assert.

[SjoerdMeijer]

I wrote some manual tests, and looked at some IR, and the produced code looked okay to me.
I will continue testing a bit more until you point out to me that I missed something here and did something stupid :-)

[Ayal]

The original intent was to make sure that under OptForSize only a single (vector) loop will be produced. I.e., w/o a scalar loop serving either as scalar leftover iterations or as runtime guard bailout. There's another such assert in emitSCEVChecks(). Now that FoldTailByMasking no longer implies OptForSize this should indeed be updated (to use CM_ScalarEpilogueNotAllowedOptSize instead perhaps?).

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

2699

also here

[SjoerdMeijer]

Hi,

Thanks for taking a look at this, and for clarifying this:

The original intent was to make sure that under OptForSize only a single (vector) loop will be produced. I.e., w/o a scalar loop serving either as scalar leftover iterations or as runtime guard bailout.

and for pointing this out:

There's another such assert in emitSCEVChecks(). Now that FoldTailByMasking no longer implies OptForSize this should indeed be updated (to use CM_ScalarEpilogueNotAllowedOptSize instead perhaps?).

Shall we address this separately in a different patch? I am looking at this now, and feel that I have embarked on a little SCEV adventure, and that this is a separate issue.

[Ayal]

In D66803#1648523, @SjoerdMeijer wrote:

Shall we address this separately in a different patch? I am looking at this now, and feel that I have embarked on a little SCEV adventure, and that this is a separate issue.

Sure. Can also add a TODO/FIXME for now.

[SjoerdMeijer]

Thanks, have added a FIXME, which I will address asap.

[SjoerdMeijer]

I have addressed the other assert in D66932.

[Ayal]

In D66803#1650509, @SjoerdMeijer wrote:

I have addressed the other assert in D66932.

OK, great, then the FIXME is probably redundant.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

2732

Replace the assert so that it checks hasOptSize, instead of removing it?

llvm/test/Transforms/LoopVectorize/X86/tail-folding-memcheck.ll

14

Better avoid hard coded values such as %12.
E.g., see what utils/update_test_checks.py makes of it.

[SjoerdMeijer]

Comments addressed.

[SjoerdMeijer]

llvm/test/Transforms/LoopVectorize/X86/tail-folding-memcheck.ll

14

Thanks for spotting, copy-paste mistake.
I think checking the masked loads/stores and the labels is good enough (and conciser), but if you think it is better I can run the script.

[SjoerdMeijer]

friendly ping

[SjoerdMeijer]

Many thanks for reviewing!

[uabelho]

Hi,

I've hit the new assertion when compiling for my out of tree target when using -Osize in combination with

#pragma clang loop vectorize(enable)

on a loop.

What is supposed to prevent us from triggering the assertion in a case like that?

[uabelho]

In D66803#1656923, @uabelho wrote:

Hi,

I've hit the new assertion when compiling for my out of tree target when using -Osize in combination with

#pragma clang loop vectorize(enable)

on a loop.

What is supposed to prevent us from triggering the assertion in a case like that?

Can be reproduced on trunk with

clang -mllvm -disable-llvm-optzns -S -Xclang -emit-llvm-bc -Os lala.c -o ./lala.bc
opt -disable-basicaa -O1 -S -o - lala.bc

lala.c264 BDownload

[SjoerdMeijer]

Hi, sorry about this.

Just looking at the .C file, I was surprised that it tries to emit runtime checks because restrict is. But running opt with disable-basicaa I can imagine it will try to do that yes; that doesn't really surprise me. And so when I ran clang -Os -fvectorize I am not running in to this assert.

Triggering this assert with opt shows its usefulness of this assert I think. But if we can trigger this from a user-facing tool clang then I think we do have a problem. Do you have a clang command to trigger this?

[uabelho]

Why would it be ok to give the assert when we run

clang
opt

?
You mean that clang's output in that case is broken? In that case I'd expect a verifier in opt to catch the fault, not that opt would crash with an assertion.

Anyway, I get the crash also with

clang -mllvm -disable-basicaa -S -Os lala.c -o -

[SjoerdMeijer]

I was just trying to say that triggering an assert by some option combination in a non-user facing tool is probably not that difficult. And I was also trying to say that the assert was kind of serving it purpose, because I was expecting basicaa to run. But probably that assumption is wrong?

But let's forget this, because I agree that asserting is not really a graceful way of dealing with this, and there's probably room for improvement. Just checking what you are expecting for this case: do you expect this loop to be vectorised? I would guess that because of disabling basicaa, runtime checks are required and there's code growth, which is undesired when optimising for size, so no vectorization.

[uabelho]

Normally we do use basicaa, the crash was found in "fuzz" tests where we compile the code with random flags.

So I'm not really sure what the vectorizer should really do in that case, apart from not crashing :)

[SjoerdMeijer]

Okay, thanks for reporting, I will look into this.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

void InnerLoopVectorizer::emitSCEVChecks(Loop *L, BasicBlock *Bypass) {
   Value *SCEVCheck =
       Exp.expandCodeForPredicate(&PSE.getUnionPredicate(), BB->getTerminator());
 
   if (auto *C = dyn_cast<ConstantInt>(SCEVCheck))
     if (C->isZero())
       return;
 
   assert(!Cost->foldTailByMasking() &&
          "Cannot SCEV check stride or overflow when folding tail");
+
   // Create a new block containing the stride check.
   BB->setName("vector.scevcheck");
   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);
   if (L->getParentLoop())
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(!Cost->foldTailByMasking() && "Cannot check memory when folding tail");
+  assert(!BB->getParent()->hasOptSize() &&
+         "Cannot emit memory checks when optimizing for size");
+
   // 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);
   if (L->getParentLoop())

llvm/test/Transforms/LoopVectorize/X86/tail-folding-memcheck.ll

+; RUN: opt < %s  -loop-vectorize -mcpu=core-avx2 -S | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define dso_local void @_Z1GPiS_S_(i32* nocapture %A, i32* nocapture readonly %B, i32* nocapture readonly %C) local_unnamed_addr #0 {
+; CHECK-LABEL: @_Z1GPiS_S_
+; CHECK: vector.memcheck:
+; CHECK: vector.body:
+; CHECK: @llvm.masked.load.v8i32.p0v8i32
+; CHECK: @llvm.masked.load.v8i32.p0v8i32
+; CHECK: @llvm.masked.store.v8i32.p0v8i32
+; CHECK: br i1 %{{.*}}, label %{{.*}}, label %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 i32, i32* %B, i64 %indvars.iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %arrayidx2 = getelementptr inbounds i32, i32* %C, i64 %indvars.iv
+  %1 = load i32, i32* %arrayidx2, align 4
+  %add = add nsw i32 %1, %0
+  %arrayidx4 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  store i32 %add, i32* %arrayidx4, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 430
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body, !llvm.loop !6
+}
+
+attributes #0 = { nofree norecurse nounwind uwtable }
+
+!6 = distinct !{!6, !7, !8}
+!7 = !{!"llvm.loop.vectorize.predicate.enable", i1 true}
+!8 = !{!"llvm.loop.vectorize.enable", i1 true}