[LoopVectorize] Added address space check when analysing interleaved accesses

[Ka-Ka]

Summary

Prevent memory objects of different address spaces to be part of
the same load/store groups when analysing interleaved accesses.

This is fixing pr31900.

[mssimpso]

Makes sense. I have comment about the test, though. Thanks!

test/Transforms/LoopVectorize/AArch64/pr31900.ll

2

I would prefer that we actually check the resulting IR rather than checking for "no crash". Maybe force vectorization (-force-vector-width) and then check that the loads are scalarized.

[mkuper]

lib/Transforms/Vectorize/LoopVectorize.cpp

5856

Hold on.
Shouldn't this fail the distance check? How can we have pointers in different address spaces where we succeed in computing the distance?

[mkuper]

lib/Transforms/Vectorize/LoopVectorize.cpp

5856

Err, sorry, actually went ahead and read the bug. That was the wrong question to ask.

The right question:
Do getMinusSCEV/getAddExpr require pointers to be in the same address space, as an API requirement? I mean, are they supposed to assert, or should they return something sane? Just trying to figure out whether this should be fixed on the caller side or the callee side.
(This code is a good idea anyway, no point in wasting SCEV's time when we know we won't get a constant distance...)

[efriedma]

lib/Transforms/Vectorize/LoopVectorize.cpp

5856

SCEV getAddExpr doesn't actually check the address space explicitly, but the operation doesn't make sense unless all the operands have the same size.

[Ka-Ka]

lib/Transforms/Vectorize/LoopVectorize.cpp

5856

Do you want me to try to add address space checks in getMinusSCEV/getAddExpr as well?
Is sounds like it is a larger task to add address space checks in ScalarEvolution. Is is better to do this in a separate review/commit?

test/Transforms/LoopVectorize/AArch64/pr31900.ll

2

Sure, I will update the testcase in the next patch.

[Ka-Ka]

Updated the testcase to use FileCheck.

[mssimpso]

This looks good to me (aside from a very minor nit about the test run line). Please give Michael and Eli a chance to respond to your questions, though.

test/Transforms/LoopVectorize/AArch64/pr31900.ll

2

For the run line, we don't need the "-o -", and we now usually input from stdin like "< %s". I think this may make testing faster, but I'm not sure.

[mkuper]

This LGTM to me too, in the sense that I think this check is a good idea here regardless of what SCEV does.
I don't understand SCEV well enough to say whether we need a change of that side, and I didn't quite understand Eli's point.
In any case, I think we can talk about that in post-commit review if there's anything to talk about, but please give Eli some time to object.

[efriedma]

Sorry I wasn't clear. You should check the address spaces of pointers before passing them to getMinusSCEV because the operands of getMinusSCEV are required to have the same bit-width. So this patch is correct as-is.

[mkuper]

In D29717#674077, @efriedma wrote:

Sorry I wasn't clear. You should check the address spaces of pointers before passing them to getMinusSCEV because the operands of getMinusSCEV are required to have the same bit-width. So this patch is correct as-is.

Pointers in different address spaces may or may not have different bitwidths. Will getMinusSCEV assert if the pointers are in different address spaces but have the same bitwidth? And what's the right behavior?

In any case, that's mostly academic. This LGTM.

[efriedma]

The general rule is that SCEV doesn't know anything about pointers; it just handles them as if you converted them to integers using ptrtoint.

[Ka-Ka]

Updated the testcase "run line"

[Ka-Ka]

I had to revert this change due to a buildbot failure. I'm trying to recreate the fault locally ...

lib/Transforms/Vectorize/LoopVectorize.cpp

for (auto AI = std::next(BI); AI != E; ++AI) {
       if (isInterleaved(A) || A->mayReadFromMemory() != B->mayReadFromMemory())
         continue;
 
       // Check rules 1 and 2. Ignore A if its stride or size is different from
       // that of B.
       if (DesA.Stride != DesB.Stride || DesA.Size != DesB.Size)
         continue;
 
+      // Ignore A if the memory object of A and B don't belong to the same
+      // address space
+      if (DesA.Scev->getType()->getPointerAddressSpace() !=
+          DesB.Scev->getType()->getPointerAddressSpace())
+        continue;
+
       // Calculate the distance from A to B.
       const SCEVConstant *DistToB = dyn_cast<SCEVConstant>(
           PSE.getSE()->getMinusSCEV(DesA.Scev, DesB.Scev));
       if (!DistToB)
         continue;
       int64_t DistanceToB = DistToB->getAPInt().getSExtValue();
 
       // Check rule 3. Ignore A if its distance to B is not a multiple of the
void InterleavedAccessInfo::analyzeInterleaving(
   } // Iteration over B accesses.
 
   // Remove interleaved store groups with gaps.
   for (InterleaveGroup *Group : StoreGroups)
     if (Group->getNumMembers() != Group->getFactor())
       releaseGroup(Group);
 
   // Remove interleaved groups with gaps (currently only loads) whose memory
-  // accesses may wrap around. We have to revisit the getPtrStride analysis, 
-  // this time with ShouldCheckWrap=true, since collectConstStrideAccesses does 
+  // accesses may wrap around. We have to revisit the getPtrStride analysis,
+  // this time with ShouldCheckWrap=true, since collectConstStrideAccesses does
   // not check wrapping (see documentation there).
-  // FORNOW we use Assume=false; 
-  // TODO: Change to Assume=true but making sure we don't exceed the threshold 
+  // FORNOW we use Assume=false;
+  // TODO: Change to Assume=true but making sure we don't exceed the threshold
   // of runtime SCEV assumptions checks (thereby potentially failing to
-  // vectorize altogether). 
+  // vectorize altogether).
   // Additional optional optimizations:
-  // TODO: If we are peeling the loop and we know that the first pointer doesn't 
+  // TODO: If we are peeling the loop and we know that the first pointer doesn't
   // wrap then we can deduce that all pointers in the group don't wrap.
-  // This means that we can forcefully peel the loop in order to only have to 
-  // check the first pointer for no-wrap. When we'll change to use Assume=true 
+  // This means that we can forcefully peel the loop in order to only have to
+  // check the first pointer for no-wrap. When we'll change to use Assume=true
   // we'll only need at most one runtime check per interleaved group.
   //
   for (InterleaveGroup *Group : LoadGroups) {
 
     // Case 1: A full group. Can Skip the checks; For full groups, if the wide
-    // load would wrap around the address space we would do a memory access at 
-    // nullptr even without the transformation. 
-    if (Group->getNumMembers() == Group->getFactor()) 
+    // load would wrap around the address space we would do a memory access at
+    // nullptr even without the transformation.
+    if (Group->getNumMembers() == Group->getFactor())
       continue;
 
-    // Case 2: If first and last members of the group don't wrap this implies 
+    // Case 2: If first and last members of the group don't wrap this implies
     // that all the pointers in the group don't wrap.
     // So we check only group member 0 (which is always guaranteed to exist),
-    // and group member Factor - 1; If the latter doesn't exist we rely on 
+    // and group member Factor - 1; If the latter doesn't exist we rely on
     // peeling (if it is a non-reveresed accsess -- see Case 3).
     Value *FirstMemberPtr = getPointerOperand(Group->getMember(0));
-    if (!getPtrStride(PSE, FirstMemberPtr, TheLoop, Strides, /*Assume=*/false, 
+    if (!getPtrStride(PSE, FirstMemberPtr, TheLoop, Strides, /*Assume=*/false,
                       /*ShouldCheckWrap=*/true)) {
       DEBUG(dbgs() << "LV: Invalidate candidate interleaved group due to "
                       "first group member potentially pointer-wrapping.\n");
       releaseGroup(Group);
       continue;
     }
     Instruction *LastMember = Group->getMember(Group->getFactor() - 1);
     if (LastMember) {
       Value *LastMemberPtr = getPointerOperand(LastMember);
-      if (!getPtrStride(PSE, LastMemberPtr, TheLoop, Strides, /*Assume=*/false, 
+      if (!getPtrStride(PSE, LastMemberPtr, TheLoop, Strides, /*Assume=*/false,
                         /*ShouldCheckWrap=*/true)) {
         DEBUG(dbgs() << "LV: Invalidate candidate interleaved group due to "
                         "last group member potentially pointer-wrapping.\n");
         releaseGroup(Group);
       }
     }
     else {
       // Case 3: A non-reversed interleaved load group with gaps: We need
-      // to execute at least one scalar epilogue iteration. This will ensure 
+      // to execute at least one scalar epilogue iteration. This will ensure
       // we don't speculatively access memory out-of-bounds. We only need
-      // to look for a member at index factor - 1, since every group must have 
+      // to look for a member at index factor - 1, since every group must have
       // a member at index zero.
       if (Group->isReverse()) {
         releaseGroup(Group);
         continue;
       }
       DEBUG(dbgs() << "LV: Interleaved group requires epilogue iteration.\n");
       RequiresScalarEpilogue = true;
     }

test/Transforms/LoopVectorize/AArch64/pr31900.ll

+; RUN: opt -S -mtriple=aarch64-apple-ios -loop-vectorize -enable-interleaved-mem-accesses -force-vector-width=2 -o - %s | FileCheck %s
+
+; Reproducer for address space fault in the LoopVectorizer (pr31900). Added
+; different sized address space pointers (p:16:16-p4:32:16) to the aarch64
+; datalayout to reproduce the fault.
+
+target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128-p:16:16-p4:32:16"
+
+; Check that all the loads are scalarized
+; CHECK: load i16, i16*
+; CHECK: load i16, i16*
+; CHECK: load i16, i16 addrspace(4)*
+; CHECK: load i16, i16 addrspace(4)*
+
+%rec1445 = type { i16, i16, i16, i16, i16 }
+
+define void @foo() {
+bb1:
+  br label %bb4
+
+bb4:
+  %tmp1 = phi i16 [ undef, %bb1 ], [ %_tmp1013, %bb4 ]
+  %tmp2 = phi %rec1445* [ undef, %bb1 ], [ %_tmp1015, %bb4 ]
+  %tmp3 = phi %rec1445 addrspace(4)* [ undef, %bb1 ], [ %_tmp1017, %bb4 ]
+  %0 = getelementptr %rec1445, %rec1445* %tmp2, i16 0, i32 1
+  %_tmp987 = load i16, i16* %0, align 1
+  %1 = getelementptr %rec1445, %rec1445 addrspace(4)* %tmp3, i32 0, i32 1
+  %_tmp993 = load i16, i16 addrspace(4)* %1, align 1
+  %_tmp1013 = add i16 %tmp1, 1
+  %_tmp1015 = getelementptr %rec1445, %rec1445* %tmp2, i16 1
+  %_tmp1017 = getelementptr %rec1445, %rec1445 addrspace(4)* %tmp3, i32 1
+  %_tmp1019 = icmp ult i16 %_tmp1013, 24
+  br i1 %_tmp1019, label %bb4, label %bb16
+
+bb16:
+  unreachable
+}