[SVE] Fix isLoadInvariantInLoop for scalable vectors

[david-arm]

Summary

I've amended the isLoadInvariantInLoop function to bail out for
scalable vectors for now since the invariant.start intrinsic is only
ever generated by the clang frontend for thread locals or struct
and class constructors, neither of which support sizeless types.
In addition, the intrinsic itself does not currently support the
concept of a scaled size, which makes it impossible to compare
the sizes of different scalable objects, e.g. <vscale x 32 x i8>
and <vscale x 16 x i8>.

Added new tests here:

Transforms/LICM/AArch64/sve-load-hoist.ll

[david-arm]

• Added check for -1 argument passed to invariant.start intrinsic.
• Added comments explaining reasons for bailing out in isLoadInvariantInLoop.

[sdesmalen]

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

818 ↗

(On Diff #290427)

It is probably important for isLegalAddressingMode to know whether the Offset and/or Scale is a multiple of vscale, so it makes sense to encode that in a TypeSize. I would prefer to either keep the warning or make isLegalAddressingMode accept a TypeSize, instead of explicitly removing the 'vscale' information here and replacing the warning with a TODO.

llvm/lib/Transforms/Scalar/LICM.cpp

954

This change seems untested, as none of your tests has a llvm.invariant.start intrinsic (and so there is no code-path tested that would otherwise return true)

988

This may be better addressed in a separate patch, because this is unrelated to SVE or scalable vectors.

Just to confirm what's at fault here. If the number of invariant bits of an object is unknown, it is wrong to assume that the load is invariant by checking LocSizeInBits.getFixedSize() <= InvariantSizeInBits. Here InvariantSizeInBits would be (unsigned) -1, so this is always true. Where in fact, we expect it to evaluate to false.

990

It seems odd to assert that here. This is probably better added as a check to the IR Verifier pass, and here bail out with:

if (InvariantSize < 0)
  continue;

llvm/test/Transforms/LICM/AArch64/sve-load-hoist.ll

2

These tests don't test anything from the patch, as they already pass with current master.

[david-arm]

• Added more test cases that fail without my patch and pass with.
• Removed the assert in isLoadInvariantInLoop.
• Added Verifier checks for invariant.start intrinsic parameter.

[david-arm]

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

818 ↗

(On Diff #290427)

OK I'll make the change to isLegalAddressingMode in a separate patch to support compound BaseOffsets that are true polynomials, i.e. pass a BaseOffset and a ScaledBaseOffset to isLegalAddressingMode.

llvm/lib/Transforms/Scalar/LICM.cpp

988

So it is related to SVE in a way, because if the C++ frontend in clang ever did decide to support sizeless types in structs, classes or thread locals (SVE ACLE types are sizeless) then this value may actually be -1 (unless the definition of the intrinsic is changed to formally deal with scalable types).

Yes, the problem is that in the code below we are potentially casting -1 (which can occur for any incomplete type in clang) to unsigned and therefore always hoisting the load out, which is wrong. I think if we expect to never hit the -1 case here then there should probably be an assert instead.

[sdesmalen]

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

818 ↗

(On Diff #290427)

I don't think it needs to be support compound BaseOffsets that are true polynomials. Because scalable vectors are not allowed as members of structs, we can't construct a gep that leads to a compound offset with both unscaled and vscale'd parts.

[sdesmalen]

llvm/test/Transforms/LICM/AArch64/sve-load-hoist.ll

12

If you want to test the new condition you added:

if (LocSizeInBits.isScalable())
return false;

then you need to use a value >= 0 for llvm.invariant.start, as otherwise this test will also pass without your change.

30

No code changes in this patch are tested with this test as it doesn't use llvm.invariant.start. I think you should remove these tests from the patch, as I suspect they produce warnings and thus deserve fixing separately.

[david-arm]

• Removed tests for hoisting/not hoisting scalable vectors that do not have an invariant.start intrinsic.
• Changed the one remaining test in sve-hoist.ll to use a parameter of 16 instead of -1.

[david-arm]

llvm/test/Transforms/LICM/AArch64/sve-load-hoist.ll

12

Without my patch the test fails in the same way for both parameters of -1 and 16 because we hoist in both cases. With my patch the test passes in the same way because we bail out at the same point. However, I think I understand why you prefer using 16.

[sdesmalen]

LGTM!

nit: I don't know if Clang ever really generates a llvm.invariant.start with -1 size in practice, but if it does, you may want to land this patch as two separate patches, one patch that prevents hoisting when size = -1 and another to stop the hoisting for scalable vectors.

llvm/lib/IR/Verifier.cpp

case Intrinsic::llrint: {
     break;
   }
   case Intrinsic::bswap: {
     Type *Ty = Call.getType();
     unsigned Size = Ty->getScalarSizeInBits();
     Assert(Size % 16 == 0, "bswap must be an even number of bytes", &Call);
     break;
   }
+  case Intrinsic::invariant_start: {
+    ConstantInt *InvariantSize = dyn_cast<ConstantInt>(Call.getArgOperand(0));
+    Assert(InvariantSize &&
+               (!InvariantSize->isNegative() || InvariantSize->isMinusOne()),
+           "invariant_start parameter must be -1, 0 or a positive number",
+           &Call);
+    break;
+  }
   case Intrinsic::matrix_multiply:
   case Intrinsic::matrix_transpose:
   case Intrinsic::matrix_column_major_load:
   case Intrinsic::matrix_column_major_store: {
     Function *IF = Call.getCalledFunction();
     ConstantInt *Stride = nullptr;
     ConstantInt *NumRows;
     ConstantInt *NumColumns;

llvm/lib/Transforms/Scalar/LICM.cpp

 // Return true if LI is invariant within scope of the loop. LI is invariant if
 // CurLoop is dominated by an invariant.start representing the same memory
 // location and size as the memory location LI loads from, and also the
 // invariant.start has no uses.
 static bool isLoadInvariantInLoop(LoadInst *LI, DominatorTree *DT,
                                   Loop *CurLoop) {
   Value *Addr = LI->getOperand(0);
   const DataLayout &DL = LI->getModule()->getDataLayout();
-  const uint32_t LocSizeInBits = DL.getTypeSizeInBits(LI->getType());
+  const TypeSize LocSizeInBits = DL.getTypeSizeInBits(LI->getType());
+
+  // It is not currently possible for clang to generate an invariant.start
+  // intrinsic with scalable vector types because we don't support thread local
+  // sizeless types and we don't permit sizeless types in structs or classes.
+  // Furthermore, even if support is added for this in future the intrinsic
+  // itself is defined to have a size of -1 for variable sized objects. This
+  // makes it impossible to verify if the intrinsic envelops our region of
+  // interest. For example, both <vscale x 32 x i8> and <vscale x 16 x i8>
+  // types would have a -1 parameter, but the former is clearly double the size
+  // of the latter.
+  if (LocSizeInBits.isScalable())
+    return false;
 
   // if the type is i8 addrspace(x)*, we know this is the type of
   // llvm.invariant.start operand
   auto *PtrInt8Ty = PointerType::get(Type::getInt8Ty(LI->getContext()),
                                      LI->getPointerAddressSpace());
   unsigned BitcastsVisited = 0;
   // Look through bitcasts until we reach the i8* type (this is invariant.start
   // operand type).
for (auto *U : Addr->users()) {
     if (++UsesVisited > MaxNumUsesTraversed)
       return false;
     IntrinsicInst *II = dyn_cast<IntrinsicInst>(U);
     // If there are escaping uses of invariant.start instruction, the load maybe
     // non-invariant.
     if (!II || II->getIntrinsicID() != Intrinsic::invariant_start ||
         !II->use_empty())
       continue;
-    unsigned InvariantSizeInBits =
-        cast<ConstantInt>(II->getArgOperand(0))->getSExtValue() * 8;
+    ConstantInt *InvariantSize = cast<ConstantInt>(II->getArgOperand(0));
+    // The intrinsic supports having a -1 argument for variable sized objects
+    // so we should check for that here.
+    if (InvariantSize->isNegative())
+      continue;
+    uint64_t InvariantSizeInBits = InvariantSize->getSExtValue() * 8;
     // Confirm the invariant.start location size contains the load operand size
     // in bits. Also, the invariant.start should dominate the load, and we
     // should not hoist the load out of a loop that contains this dominating
     // invariant.start.
-    if (LocSizeInBits <= InvariantSizeInBits &&
+    if (LocSizeInBits.getFixedSize() <= InvariantSizeInBits &&
         DT->properlyDominates(II->getParent(), CurLoop->getHeader()))
       return true;
   }
 
   return false;
 }
 
 namespace {

llvm/test/Transforms/LICM/AArch64/lit.local.cfg

+if not 'AArch64' in config.root.targets:
+    config.unsupported = True

llvm/test/Transforms/LICM/AArch64/sve-load-hoist.ll

+; RUN: opt -licm -mtriple aarch64-linux-gnu -mattr=+sve -S < %s | FileCheck %s
+
+define void @no_hoist_load1_nxv2i64(<vscale x 2 x i64>* %out, i8* %in8, i32 %n) {
+; CHECK-LABEL: @no_hoist_load1_nxv2i64(
+; CHECK: entry:
+; CHECK-NOT: load
+; CHECK: for.body:
+; CHECK: load
+entry:
+  %cmp0 = icmp ugt i32 %n, 0
+  %invst = call {}* @llvm.invariant.start.p0i8(i64 16, i8* %in8)
+  %in = bitcast i8* %in8 to <vscale x 2 x i64>*
+  br i1 %cmp0, label %for.body, label %for.end
+
+for.body:
+  %i = phi i32 [0, %entry], [%inc, %for.body]
+  %i2 = zext i32 %i to i64
+  %ptr = getelementptr <vscale x 2 x i64>, <vscale x 2 x i64>* %out, i64 %i2
+  %val = load <vscale x 2 x i64>, <vscale x 2 x i64>* %in, align 16
+  store <vscale x 2 x i64> %val, <vscale x 2 x i64>* %ptr, align 16
+  %inc = add nuw nsw i32 %i, 1
+  %cmp = icmp ult i32 %inc, %n
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:
+  ret void
+}
+
+declare {}* @llvm.invariant.start.p0i8(i64, i8* nocapture) nounwind readonly
+

llvm/test/Transforms/LICM/hoisting.ll

loop:
   %sum.next = add i32 %sel, %sum
   %indvar.next = add i32 %indvar, 1
   %cond = icmp slt i32 %indvar.next, %n
   br i1 %cond, label %loop, label %loopexit
 
 loopexit:
   ret i32 %sum
 }
+
+; We can't hoist the invariant load out of the loop because
+; the marker is given a variable size (-1).
+define i32 @test_fence5(i8* %addr, i32 %n, i8* %volatile) {
+; CHECK-LABEL: @test_fence5
+; CHECK-LABEL: entry
+; CHECK: invariant.start
+; CHECK-NOT: %addrld = load atomic i32, i32* %addr.i unordered, align 8
+; CHECK: br label %loop
+entry:
+  %gep = getelementptr inbounds i8, i8* %addr, i64 8
+  %addr.i = bitcast i8* %gep to i32 *
+  store atomic i32 5, i32 * %addr.i unordered, align 8
+  fence release
+  %invst = call {}* @llvm.invariant.start.p0i8(i64 -1, i8* %gep)
+  br label %loop
+
+loop:
+  %indvar = phi i32 [ %indvar.next, %loop ], [ 0, %entry ]
+  %sum = phi i32 [ %sum.next, %loop ], [ 0, %entry ]
+  %volload = load atomic i8, i8* %volatile unordered, align 8
+  fence acquire
+  %volchk = icmp eq i8 %volload, 0
+  %addrld = load atomic i32, i32* %addr.i unordered, align 8
+  %sel = select i1 %volchk, i32 0, i32 %addrld
+  %sum.next = add i32 %sel, %sum
+  %indvar.next = add i32 %indvar, 1
+  %cond = icmp slt i32 %indvar.next, %n
+  br i1 %cond, label %loop, label %loopexit
+
+loopexit:
+  ret i32 %sum
+}