[LoopVectorize] Emit runtime checks correctly for nested loops

[kpdev42]

Summary

Fixes https://github.com/llvm/llvm-project/issues/57315

~~~

OS Laboratory. Huawei RRI. Saint-Petersburg

[kpdev42]

Remove unrelated changes

[fhahn]

Thanks for the patch! I don't think this is the ideal solution, it looks like the source of the issue is a missing check that the AddRecs for step expressions are both in the inner loop. I'll include a diff with the fix below which I am planning to submit.

As you already shared a test case, it would be great if you could clean it up a bit and land just the patch to start with. I left some comments inline. What do you think?

index 5a01a8e4b055..220e48643245 100644
--- a/llvm/include/llvm/Analysis/LoopAccessAnalysis.h
+++ b/llvm/include/llvm/Analysis/LoopAccessAnalysis.h
@@ -253,6 +253,10 @@ public:
     return {};
   }

+  const Loop *getInnermostLoop() const {
+    return InnermostLoop;
+  }
+
 private:
   /// A wrapper around ScalarEvolution, used to add runtime SCEV checks, and
   /// applies dynamic knowledge to simplify SCEV expressions and convert them
diff --git a/llvm/lib/Analysis/LoopAccessAnalysis.cpp b/llvm/lib/Analysis/LoopAccessAnalysis.cpp
index a9a4a820db50..4febf0bfd62c 100644
--- a/llvm/lib/Analysis/LoopAccessAnalysis.cpp
+++ b/llvm/lib/Analysis/LoopAccessAnalysis.cpp
@@ -281,7 +281,7 @@ void RuntimePointerChecking::tryToCreateDiffCheck(

   auto *SrcAR = dyn_cast<SCEVAddRecExpr>(Src->Expr);
   auto *SinkAR = dyn_cast<SCEVAddRecExpr>(Sink->Expr);
-  if (!SrcAR || !SinkAR) {
+  if (!SrcAR || !SinkAR || SrcAR->getLoop() != DC.getInnermostLoop() || SinkAR->getLoop() != DC.getInnermostLoop()) {
     CanUseDiffCheck = false;
     return;
   }

llvm/test/Transforms/LoopVectorize/nested-loop.ll

9

I don't think this test needs the X86 cost model. target triple could probably be dropped and replaced by passing -force-vector-width=4 -force-vector-interleave=1 to opt. If it requires the target triple, it needs to be moved to the X86 sub-directory.

17

This check shouldn't be really needed.

20

could pass %Len as i64

23

block names could be simplified. e.g. %for.cond1.preheader.us -> %outer.header, %for.cond1.for.end_crit_edge.us: -> %outer.latch, %for.body3.us -> %inner for.end12 -> %exit.

31

same could be simplified by dropping indvars. prefix.

35

!tbaa shouldn't be needed.

42

This could be simplified, if a use of %sub.us.lcssa is needed then a function that only takes an i32 should be sufficient.

57

attributes shouldn't be needed

60

none of the metadata should be needed

[fhahn]

Thanks for the update. As I mentioned in the previous message, I think it would be good to just land the test in this patch and I'll submit the code change separately. The test looks good to me.

[kpdev42]

In D132490#3746679, @fhahn wrote:

Thanks for the update. As I mentioned in the previous message, I think it would be good to just land the test in this patch and I'll submit the code change separately. The test looks good to me.

Thank you fer the review.
Lets keep buildbot green. Please land both fix and test case on your own

[fhahn]

In D132490#3748231, @kpdev42 wrote:

In D132490#3746679, @fhahn wrote:

Thanks for the update. As I mentioned in the previous message, I think it would be good to just land the test in this patch and I'll submit the code change separately. The test looks good to me.

Thank you fer the review.
Lets keep buildbot green. Please land both fix and test case on your own

Thanks, the idea would be to commit the test first with the checks so it passes without the fix. The fix then only shows the improvements on the test case, so the bots would stay green at all time.

[kpdev42]

In D132490#3748233, @fhahn wrote:

In D132490#3748231, @kpdev42 wrote:

In D132490#3746679, @fhahn wrote:

Thanks for the update. As I mentioned in the previous message, I think it would be good to just land the test in this patch and I'll submit the code change separately. The test looks good to me.

Thank you fer the review.
Lets keep buildbot green. Please land both fix and test case on your own

Thanks, the idea would be to commit the test first with the checks so it passes without the fix. The fix then only shows the improvements on the test case, so the bots would stay green at all time.

I am afraid that this test does not pass without fix, so far would you like to (a) modify the test, so that it would pass (diff check instead of overlap check) or (b) XFAIL the test or (c) maybe something else?

[fhahn]

In D132490#3770109, @kpdev42 wrote:

In D132490#3748233, @fhahn wrote:

In D132490#3748231, @kpdev42 wrote:

In D132490#3746679, @fhahn wrote:

Thanks for the update. As I mentioned in the previous message, I think it would be good to just land the test in this patch and I'll submit the code change separately. The test looks good to me.

Thank you fer the review.
Lets keep buildbot green. Please land both fix and test case on your own

Thanks, the idea would be to commit the test first with the checks so it passes without the fix. The fix then only shows the improvements on the test case, so the bots would stay green at all time.

I am afraid that this test does not pass without fix, so far would you like to (a) modify the test, so that it would pass (diff check instead of overlap check) or (b) XFAIL the test or (c) maybe something else?

Oh right, common practice is to generate the (incorrect) check lines for the test so they pass on current main, together with a FIXME comment explaining what the current issue is. I did something like that in 6e56779e6bc168a3acd14f9bf2c4fd3fd9d86bd1.

Anyways, it should be fixed on current main by now.

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

public:
   /// Returns an empty ArrayRef if there are no accesses for the location.
   ArrayRef<unsigned> getOrderForAccess(Value *Ptr, bool IsWrite) const {
     auto I = Accesses.find({Ptr, IsWrite});
     if (I != Accesses.end())
       return I->second;
     return {};
   }
 
+  const Loop *getInnermostLoop() const { return InnermostLoop; }
+
 private:
   /// A wrapper around ScalarEvolution, used to add runtime SCEV checks, and
   /// applies dynamic knowledge to simplify SCEV expressions and convert them
   /// to a more usable form. We need this in case assumptions about SCEV
   /// expressions need to be made in order to avoid unknown dependences. For
   /// example we might assume a unit stride for a pointer in order to prove
   /// that a memory access is strided and doesn't wrap.
   PredicatedScalarEvolution &PSE;

llvm/lib/Analysis/LoopAccessAnalysis.cpp

if (AccSrc.size() != 1 || AccSink.size() != 1) {
     return;
   }
   // If the sink is accessed before src, swap src/sink.
   if (AccSink[0] < AccSrc[0])
     std::swap(Src, Sink);
 
   auto *SrcAR = dyn_cast<SCEVAddRecExpr>(Src->Expr);
   auto *SinkAR = dyn_cast<SCEVAddRecExpr>(Sink->Expr);
-  if (!SrcAR || !SinkAR) {
+  if (!SrcAR || !SinkAR || SrcAR->getLoop() != DC.getInnermostLoop() ||
+      SinkAR->getLoop() != DC.getInnermostLoop()) {
     CanUseDiffCheck = false;
     return;
   }
 
   const DataLayout &DL =
       SinkAR->getLoop()->getHeader()->getModule()->getDataLayout();
   SmallVector<Instruction *, 4> SrcInsts =
       DC.getInstructionsForAccess(Src->PointerValue, Src->IsWritePtr);

llvm/test/Transforms/LoopVectorize/nested-loop.ll

+; RUN: opt -loop-vectorize -force-vector-width=4 -force-vector-interleave=1 -S %s -o - | FileCheck %s
+; CHECK:       vector.memcheck:
+; CHECK-NEXT:    %bound0 = icmp ult ptr
+; CHECK-NEXT:    %bound1 = icmp ult ptr
+; CHECK-NEXT:    %found.conflict = and i1 %bound0, %bound1
+
+define dso_local void @array_magick(ptr nocapture noundef %a, ptr nocapture noundef readonly %b, i64 noundef %len) local_unnamed_addr {
+entry:
+  br label %outer.header
+
+outer.header:                              ; preds = %entry, %outer.latch
+  %iv28 = phi i64 [ %iv.next29, %outer.latch ], [ 0, %entry ]
+  %arrayidx = getelementptr inbounds i32, ptr %a, i64 %iv28
+  %.pre = load i32, ptr %arrayidx, align 4
+  br label %inner.body
+
+inner.body:                                        ; preds = %outer.header, %inner.body
+  %0 = phi i32 [ %.pre, %outer.header ], [ %sub, %inner.body ]
+  %iv = phi i64 [ 0, %outer.header ], [ %iv.next, %inner.body ]
+  %arrayidx8 = getelementptr inbounds i32, ptr %b, i64 %iv
+  %1 = load i32, ptr %arrayidx8, align 4
+  %sub = sub i32 %0, %1
+  store i32 %sub, ptr %arrayidx, align 4
+  %iv.next = add nuw nsw i64 %iv, 1
+  %exitcond.not = icmp eq i64 %iv.next, %len
+  br i1 %exitcond.not, label %outer.latch, label %inner.body
+
+outer.latch:                    ; preds = %inner.body
+  %iv.next29 = add nuw nsw i64 %iv28, 1
+  %exitcond31.not = icmp eq i64 %iv.next29, %len
+  br i1 %exitcond31.not, label %exit, label %outer.header
+
+exit:                                             ; preds = %outer.latch
+  ret void
+}