[SCEV] Do not plant SCEV checks unnecessarily

[pawosm01]

Summary

The vectorisation analysis collects strides for loop invariant
pointers, which is wrong because they are not strided. We don't
need to generate SCEV checks (which are costly performancewise)
for such pointers, we just need to do the appropriate aliasing
checks.

This patch fixes the problem by changing getStrideFromPointer()
to treat loop invariant pointers as having no stride.

Originally proposed by David Sherwood with further suggestions
from Florian Hahn.

[ABataev]

llvm/test/Transforms/LoopVectorize/vector-no-scevcheck.ll

1

Could you precommit the test?

4–5

Pass these as arguments of opt call.

7

The attributes can be dropped, assume

63–73

Can you try to drop metadata too?

[pawosm01]

Simplification of the test case (as per reviewer request).

[pawosm01]

llvm/test/Transforms/LoopVectorize/vector-no-scevcheck.ll

1

will do soon(ish)

4–5

Actually, I see no good reason for having them. No need for limiting it to AArch64.

[pawosm01]

llvm/test/Transforms/LoopVectorize/vector-no-scevcheck.ll

1

Released as D146974

Not sure how it's going to fail correctly, Something weird is happening with the CI today.

[pawosm01]

llvm/test/Transforms/LoopVectorize/vector-no-scevcheck.ll

1

The test case released as D146974 has failed as expected.

[pawosm01]

Test case simplified, as per the reviewer request.

[ABataev]

llvm/test/Transforms/LoopVectorize/vector-no-scevcheck.ll

1

Rebase to see the difference

[pawosm01]

I hope reupload of the same diff causes rebase...

[david-arm]

Hi @pawelo12345678, it looks like something went wrong here because now there are no code changes, but also this patch still seems to be adding llvm/test/Transforms/LoopVectorize/vector-no-scevcheck.ll. I think what you can do to show the test changes is to rebase this patch downstream in git based off D146974. You can then show the history by adding D146974 as a parent revision.

[pawosm01]

restored what was lost

[pawosm01]

context will return soon

[pawosm01]

BTW, is there any one-button-click way of rebasing?

[pawosm01]

the context also restored

[ABataev]

llvm/test/Transforms/LoopVectorize/vector-no-scevcheck.ll

1

Looks like the test was not precommitted

[pawosm01]

llvm/test/Transforms/LoopVectorize/vector-no-scevcheck.ll

1

Yeah, I've never been through this scenario before. I need a guidance on how to do that.

[ABataev]

llvm/test/Transforms/LoopVectorize/vector-no-scevcheck.ll

1

You need to commit D146974 at first (after approval), then rebase this patch to see the difference in the test(s).

[pawosm01]

I'm trying to build a relation between D146974 and D146958.

[pawosm01]

following reviewer's advice.

[fhahn]

llvm/lib/Analysis/LoopAccessAnalysis.cpp

2705

Better use a more powerful SCEV based check that the AddRec for the ptr is for TheLoop ( check TheLoop != AR->getLoop() in getStrideFromPointer)

llvm/lib/Analysis/VectorUtils.cpp

1163 ↗

(On Diff #510884)

Is this needed?

[pawosm01]

Changes applied according to the reviewer's suggestion. With summary update.

[pawosm01]

llvm/lib/Analysis/LoopAccessAnalysis.cpp

2705

Indeed it worked. And the other test case that you'd suggested is also passing too.

[pawosm01]

llvm/lib/Analysis/VectorUtils.cpp

1163 ↗

(On Diff #510884)

Apparently not.

[fhahn]

LGTM, thanks!

llvm/lib/Analysis/LoopAccessAnalysis.cpp

if (Ptr != OrigPtr)
     // Strip off casts.
     while (const SCEVIntegralCastExpr *C = dyn_cast<SCEVIntegralCastExpr>(V))
       V = C->getOperand();
 
   const SCEVAddRecExpr *S = dyn_cast<SCEVAddRecExpr>(V);
   if (!S)
     return nullptr;
 
+  // If the pointer is invariant then there is no stride and it makes no
+  // sense to add it here.
+  if (Lp != S->getLoop())
+    return nullptr;
+
   V = S->getStepRecurrence(*SE);
   if (!V)
     return nullptr;
 
   // Strip off the size of access multiplication if we are still analyzing the
   // pointer.
   if (OrigPtr == Ptr) {
     if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(V)) {

 
 void LoopAccessInfo::collectStridedAccess(Value *MemAccess) {
   Value *Ptr = getLoadStorePointerOperand(MemAccess);
   if (!Ptr)
     return;
 
   Value *Stride = getStrideFromPointer(Ptr, PSE->getSE(), TheLoop);
   if (!Stride)
     return;
 
   LLVM_DEBUG(dbgs() << "LAA: Found a strided access that is a candidate for "
                        "versioning:");
   LLVM_DEBUG(dbgs() << "  Ptr: " << *Ptr << " Stride: " << *Stride << "\n");
 
   // Avoid adding the "Stride == 1" predicate when we know that
   // Stride >= Trip-Count. Such a predicate will effectively optimize a single
   // or zero iteration loop, as Trip-Count <= Stride == 1.

llvm/test/Transforms/LoopVectorize/vector-no-scevcheck.ll

 ; RUN: opt -passes=loop-vectorize -force-vector-width=2 -force-vector-interleave=1 -S < %s | FileCheck %s
 
 ; This test is to ensure that SCEV checks (which are costly performancewise) are
 ; not generated when appropriate aliasing checks are sufficient.
 
 define void @foo(ptr %pout, ptr %pin, i64 %val0, i64 %val1, i64 %val2) {
 ; CHECK-LABEL: @foo(
-; FIXME: CHECK below needs to be changed to CHECK-NOT to confirm the change.
-; CHECK: vector.scevcheck
+; CHECK-NOT: vector.scevcheck
 ; CHECK: vector.body
 entry:
   %0 = getelementptr double, ptr %pin, i64 %val0
   br label %loop1.header
 
 loop1.header:                                     ; preds = %loop1.latch, %entry
   %i = phi i64 [ %i.next, %loop1.latch ], [ 0, %entry ]
   %mul0 = mul nsw i64 %i, %val2

 exit:                                             ; preds = %loop1.latch
   ret void
 }
 
 ; Similar test to the above but with the %arrayidx0 moved to the loop2.header
 
 define void @bar(ptr %pout, ptr %pin, i64 %val0, i64 %val1, i64 %val2) {
 ; CHECK-LABEL: @bar(
-; FIXME: CHECK below needs to be changed to CHECK-NOT to confirm the change.
-; CHECK: vector.scevcheck
+; CHECK-NOT: vector.scevcheck
 ; CHECK: vector.body
 entry:
   %0 = getelementptr double, ptr %pin, i64 %val0
   br label %loop1.header
 
 loop1.header:                                     ; preds = %loop1.latch, %entry
   %i = phi i64 [ %i.next, %loop1.latch ], [ 0, %entry ]
   %mul0 = mul nsw i64 %i, %val2
   %mul1 = mul nsw i64 %i, %val1
   br label %loop2.header
 
 loop2.header:                                     ; preds = %loop1.header, %loop2.header
   %j = phi i64 [ 0, %loop1.header ], [ %j.next, %loop2.header ]
   %arrayidx0 = getelementptr inbounds double, ptr %0, i64 %mul0
   %1 = load double, ptr %arrayidx0, align 8
   %arrayidx1 = getelementptr inbounds double, ptr %0, i64 %j
   %2 = load double, ptr %arrayidx1, align 8
   %sum = fadd contract double %1, %2
   %3 = getelementptr double, ptr %pout, i64 %mul1
   %arrayidx2 = getelementptr inbounds double, ptr %3, i64 %j
   store double %sum, ptr %arrayidx2, align 8
   %j.next = add nuw nsw i64 %j, 1
   %cmp = icmp slt i64 %j.next, %val1
   br i1 %cmp, label %loop2.header, label %loop1.latch
 
 loop1.latch:                                      ; preds = %loop2.header
   %i.next = add nuw nsw i64 %i, 1
   %exitcond = icmp eq i64 %i.next, %val1
   br i1 %exitcond, label %exit, label %loop1.header
 
 exit:                                             ; preds = %loop1.latch
   ret void
 }