[LoopAccessAnalysis][SVE] Bail out for scalable vectors

[peterwaller-arm]

Summary

The supplied test case, reduced from real world code, crashes with a
'Invalid size request on a scalable vector.' error.

Since it's similar in spirit to an existing LAA test, rename the file to
generalize it to both.

[david-arm]

llvm/test/Analysis/LoopAccessAnalysis/scalable-vector-regression-tests.ll

23

Is it possible to clean this test up a bit here?

i.e. do something like:

entry:
  br label %vector.body

vector.body:
  %ind = phi i64 [ 0, %entry ], [ %ind.next, %vector.body ]
  ...
  %ind.next = add i64, %ind, 1
  br i1 %cmp, %vector.body, %end

end:
  ret i1 false

I'm just a bit worried about the strength of the test given the br i1 false and br i1 true lines in here. Also, having proper named labels like vector.body or loop.body makes it a bit more readable I think.

[peterwaller-arm]

llvm/test/Analysis/LoopAccessAnalysis/scalable-vector-regression-tests.ll

23

Thanks for your nice suggestions.

I'm just a bit worried about the strength of the test given the br i1 false and br i1 true lines in here.

I tried feeding in an i1 %cond parameter, and branching conditionally on that parameter, but then the testcase fails to reproduce the issue. I also tried having the branch depend on the output of the load, and storing an unguessable value from a parameter, but that didn't work either.

Tempted to leave it as br i1 true for the vector body, unless you strongly counsel otherwise; but I will first try a bit harder to determine why the desired code paths aren't hit in that case.

[madhur13490]

llvm/lib/Analysis/LoopAccessAnalysis.cpp

1127

I think braces are not required. You can hoist the comment above "if" block. It doesn't harm readability.

[peterwaller-arm]

llvm/lib/Analysis/LoopAccessAnalysis.cpp

1127

You are right, thanks! I've been programming too much rust recently :)

[sdesmalen]

The fix looks valid, but maybe you can update the comment a bit to better describe the different scenarios.

llvm/lib/Analysis/LoopAccessAnalysis.cpp

1128

I think there are three possible scenarios to consider:

1. The pointer has a scalable stride (e.g. the PHI is updated with getetelemenptr <vscale x 2 x i64>, <vscale x 2 x i64>*, i64 1 each iteration of the loop), at which point the Step will not be a SCEVConstant, but rather a SCEVUnknown.
2. Case 1, but LAA has replaced the symbolic stride by 1 under the predicate that vscale = 1.
3. The case you have in your tests, where the pointer stride is actually fixed (e.g. Step = {nullptr, +, 1}) and the object is scalable.

For case 1, the dyn_cast on line 1096 would fail. That means the code is already conservative.
For case 2, we could do some extra work to recognize there is a predicate that checks that vscale == 1, and use getKnownMinSize() and allow the code-path here to continue.
For case 3, we can bail out and no further work is required (meaning that the 'yet' can be removed from the comment).

Sorry if I'm being a bit nitpicky, but I think the 'not yet supported' is already the case today, and your comment is a bit misleading in that the 'yet' at this point in the code only applies to 2.

Maybe it's worth capturing these scenarios somewhere in a comment?

llvm/test/Analysis/LoopAccessAnalysis/scalable-vector-regression-tests.ll

24

nit: can you give these names instead of numbers?

[peterwaller-arm]

• Remove comment, replace with debug print statement (per other bailouts above)

For the tests:

• Introduce input pointer parameter
• Introduce a loop counter variable
• Use named bb/insts
• Add another test with scalable vector pointer as input (as opposed to an i8* as input, like before)

[peterwaller-arm]

llvm/lib/Analysis/LoopAccessAnalysis.cpp

1128

Looking at it, I don't think I observed the dyn_cast on 1096 fail. So with respect to your request I'm uncertain exactly what I am documenting right now (all the scalable cases I've tried appear to flow through the new debug statement) and I've chosen to leave that out. Hope that's OK but can revisit if requested.

[peterwaller-arm]

Run clang-format.

[paulwalker-arm]

llvm/lib/Analysis/LoopAccessAnalysis.cpp

1127–1130

At the top of this function I can see

if (AccessTy->isAggregateType()) {
  LLVM_DEBUG(dbgs() << "LAA: Bad stride - Not a pointer to a scalar type"
                    << *Ptr << "\n");
  return 0;
}

So my question is why not just add a check immediate after this for isa<ScalableVector>(AccessTy)?

[peterwaller-arm]

• Add -S to opt line (output is not checked, but llvm-lit -v output looks funny without it)
• Address review comment, move bailout to top.

[peterwaller-arm]

llvm/lib/Analysis/LoopAccessAnalysis.cpp

1127–1130

My thinking was to plant the bailout logic near the site that would need to be updated should this get extended, but your suggestion makes sense to me, so done.

[paulwalker-arm]

A couple of things to consider but otherwise looks good.

llvm/lib/Analysis/LoopAccessAnalysis.cpp

1061

Looking at the other messages suggests "LAA: Bad stride - scalable object: " would be more consistent.

llvm/test/Analysis/LoopAccessAnalysis/scalable-vector-regression-tests.ll

4–6

To me this suggest this wants to be a REQUIRES: asserts test where the debug messages are verified to be produced/not produced as expected.

[sdesmalen]

llvm/lib/Analysis/LoopAccessAnalysis.cpp

1128

I'd expect that dyn_cast to fail if there's a bitcast in the loop:

%ind_ptr_i8 = bitcast <vscale x 16 x i8>* %ind_ptr to i8*
store i8 0, i8* %ind_ptr_i8
%next_ptr = getelementptr inbounds <vscale x 16 x i8>, <vscale x 16 x i8>* %ind_ptr, i64 1

That would create a SCEV with scalable stride: {%start,+,sizeof(<vscale x 16 x i8>)}.

[peterwaller-arm]

llvm/lib/Analysis/LoopAccessAnalysis.cpp

1128

It does, but replaceSymbolicStrideSCEV appears to replace that:

LAA: Replacing SCEV: {%input_ptr,+,sizeof(<vscale x 16 x i8>)}<nw><%vector.body> by: {%input_ptr,+,1}<nw><%vector.body>

So my read is that it doesn't bail out there, however I have not fully chased this yet.

[peterwaller-arm]

Use REQUIRES: asserts, check debug output lines.

[peterwaller-arm]

Missed in previous update:

• Update debug message text for consistenc with surrounding messages.

[peterwaller-arm]

I made a bit of a mess of the updates here, managing to update one thing but
not the other. This patch should keep everything consistent. I've also removed
the label from the first test which was previously existing and exists to check
if opt exits with a fatal error.

llvm/lib/Analysis/LoopAccessAnalysis.cpp

 int64_t llvm::getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy,
                            Value *Ptr, const Loop *Lp,
                            const ValueToValueMap &StridesMap, bool Assume,
                            bool ShouldCheckWrap) {
   Type *Ty = Ptr->getType();
   assert(Ty->isPointerTy() && "Unexpected non-ptr");
   assert(!AccessTy->isAggregateType() && "Bad stride - Not a pointer to a scalar type");
 
+  if (isa<ScalableVectorType>(AccessTy)) {
+    LLVM_DEBUG(dbgs() << "LAA: Bad stride - Scalable object: " << *AccessTy
+                      << "\n");
+    return 0;
+  }
+
   const SCEV *PtrScev = replaceSymbolicStrideSCEV(PSE, StridesMap, Ptr);
 
   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev);
   if (Assume && !AR)
     AR = PSE.getAsAddRec(Ptr);
 
   if (!AR) {
     LLVM_DEBUG(dbgs() << "LAA: Bad stride - Not an AddRecExpr pointer " << *Ptr
int64_t llvm::getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy,
   const SCEVConstant *C = dyn_cast<SCEVConstant>(Step);
   if (!C) {
     LLVM_DEBUG(dbgs() << "LAA: Bad stride - Not a constant strided " << *Ptr
                       << " SCEV: " << *AR << "\n");
     return 0;
   }
 
   auto &DL = Lp->getHeader()->getModule()->getDataLayout();
-  int64_t Size = DL.getTypeAllocSize(AccessTy);
+  TypeSize AllocSize = DL.getTypeAllocSize(AccessTy);
+  int64_t Size = AllocSize.getFixedSize();
   const APInt &APStepVal = C->getAPInt();
 
   // Huge step value - give up.
   if (APStepVal.getBitWidth() > 64)
     return 0;
 
   int64_t StepVal = APStepVal.getSExtValue();
 
   // Strided access.
   int64_t Stride = StepVal / Size;
   int64_t Rem = StepVal % Size;

llvm/test/Analysis/LoopAccessAnalysis/gep-induction-operand-typesize-warning.ll

-; RUN: opt -loop-load-elim -mtriple=aarch64--linux-gnu -mattr=+sve < %s
-
-; This regression test is verifying that a GEP instruction performed on a
-; scalable vector does not produce a 'assumption that TypeSize is not scalable'
-; warning in the llvm::getGEPInductionOperand function.
-
-define void @get_gep_induction_operand_typesize_warning(i64 %n, <vscale x 4 x i32>* %a) {
-entry:
-  br label %loop.body
-
-loop.body:
-  %0 = phi i64 [ 0, %entry ], [ %1, %loop.body ]
-  %idx = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %a, i64 %0
-  store <vscale x 4 x i32> zeroinitializer, <vscale x 4 x i32>* %idx
-  %1 = add i64 %0, 1
-  %2 = icmp eq i64 %1, %n
-  br i1 %2, label %loop.end, label %loop.body
-
-loop.end:
-  ret void
-}

llvm/test/Analysis/LoopAccessAnalysis/scalable-vector-regression-tests.ll

+; RUN: opt -loop-load-elim -mtriple=aarch64 -mattr=+sve -S -debug < %s 2>&1 | FileCheck %s
+; REQUIRES: asserts
+
+; Regression tests verifying "assumption that TypeSize is not scalable" and
+; "Invalid size request on a scalable vector." are not produced by
+; -load-loop-elim (this would cause the test to fail because opt would exit with
+; a non-zero exit status).
+
+; No output checked for this one, but causes a fatal error if the regression is present.
+
+define void @regression_test_get_gep_induction_operand_typesize_warning(i64 %n, <vscale x 4 x i32>* %a) {
+entry:
+  br label %loop.body
+
+loop.body:
+  %0 = phi i64 [ 0, %entry ], [ %1, %loop.body ]
+  %idx = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %a, i64 %0
+  store <vscale x 4 x i32> zeroinitializer, <vscale x 4 x i32>* %idx
+  %1 = add i64 %0, 1
+  %2 = icmp eq i64 %1, %n
+  br i1 %2, label %loop.end, label %loop.body
+
+loop.end:
+  ret void
+}
+
+; CHECK-LABEL: LAA: Found a loop in regression_test_loop_access_scalable_typesize
+; CHECK: LAA: Bad stride - Scalable object:
+define void @regression_test_loop_access_scalable_typesize(<vscale x 16 x i8>* %input_ptr) {
+entry:
+  br label %vector.body
+vector.body:
+  %ind_ptr = phi <vscale x 16 x i8>* [ %next_ptr, %vector.body ], [ %input_ptr, %entry ]
+  %ind = phi i64 [ %next, %vector.body ], [ 0, %entry ]
+  %ld = load <vscale x 16 x i8>, <vscale x 16 x i8>* %ind_ptr, align 16
+  store <vscale x 16 x i8> zeroinitializer, <vscale x 16 x i8>* %ind_ptr, align 16
+  %next_ptr = getelementptr inbounds <vscale x 16 x i8>, <vscale x 16 x i8>* %ind_ptr, i64 1
+  %next = add i64 %ind, 1
+  %cond = icmp ult i64 %next, 1024
+  br i1 %cond, label %end, label %vector.body
+end:
+  ret void
+}
+
+; CHECK-LABEL: LAA: Found a loop in regression_test_loop_access_scalable_typesize_nonscalable_object
+; CHECK: LAA: Bad stride - Scalable object:
+define void @regression_test_loop_access_scalable_typesize_nonscalable_object(i8* %input_ptr) {
+entry:
+  br label %vector.body
+vector.body:
+  %ind_ptr = phi i8* [ %next_ptr, %vector.body ], [ %input_ptr, %entry ]
+  %ind = phi i64 [ %next, %vector.body ], [ 0, %entry ]
+  %scalable_ptr = bitcast i8* %ind_ptr to <vscale x 16 x i8>*
+  %ld = load <vscale x 16 x i8>, <vscale x 16 x i8>* %scalable_ptr, align 16
+  store <vscale x 16 x i8> zeroinitializer, <vscale x 16 x i8>* %scalable_ptr, align 16
+  %next_ptr = getelementptr inbounds i8, i8* %ind_ptr, i64 1
+  %next = add i64 %ind, 1
+  %cond = icmp ult i64 %next, 1024
+  br i1 %cond, label %end, label %vector.body
+end:
+  ret void
+}