[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

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)

982

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.

984

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

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

982

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

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/include/llvm/Analysis/TargetTransformInfoImpl.h

for (auto I = Operands.begin(); I != Operands.end(); ++I, ++GTI) {
         if (auto Splat = getSplatValue(*I))
           ConstIdx = dyn_cast<ConstantInt>(Splat);
       if (StructType *STy = GTI.getStructTypeOrNull()) {
         // For structures the index is always splat or scalar constant
         assert(ConstIdx && "Unexpected GEP index");
         uint64_t Field = ConstIdx->getZExtValue();
         BaseOffset += DL.getStructLayout(STy)->getElementOffset(Field);
       } else {
-        int64_t ElementSize = DL.getTypeAllocSize(GTI.getIndexedType());
-        if (ConstIdx) {
-          BaseOffset +=
-              ConstIdx->getValue().sextOrTrunc(PtrSizeBits) * ElementSize;
+        TypeSize ElementSize = DL.getTypeAllocSize(GTI.getIndexedType());
+        // TODO: Add support for base offsets made up of scalable types.
+        if (ConstIdx && !ElementSize.isScalable()) {
+          BaseOffset += ConstIdx->getValue().sextOrTrunc(PtrSizeBits) *
+                        ElementSize.getFixedSize();
         } else {
           // Needs scale register.
           if (Scale != 0)
             // No addressing mode takes two scale registers.
             return TTI::TCC_Basic;
-          Scale = ElementSize;
+          // If this is a scalable type we are effectively still scaling by
+          // vscale and the target must be able to cope with that.
+          Scale = ElementSize.getKnownMinSize();
         }
       }
     }
 
     if (static_cast<T *>(this)->isLegalAddressingMode(
             TargetType, const_cast<GlobalValue *>(BaseGV),
             BaseOffset.sextOrTrunc(64).getSExtValue(), HasBaseReg, Scale,
             Ptr->getType()->getPointerAddressSpace()))

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());
+
+  // The invariant_start intrinsic currently doesn't support scalable types
+  // sizes so we bail out for now.
+  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).
   while (Addr->getType() != PtrInt8Ty) {
     auto *BC = dyn_cast<BitCastInst>(Addr);
     // Avoid traversing high number of bitcast uses.
     if (++BitcastsVisited > MaxNumUsesTraversed || !BC)
       return false;
     Addr = BC->getOperand(0);
for (auto *U : Addr->users()) {
     // non-invariant.
     if (!II || II->getIntrinsicID() != Intrinsic::invariant_start ||
         !II->use_empty())
       continue;
     unsigned InvariantSizeInBits =
         cast<ConstantInt>(II->getArgOperand(0))->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 2>%t | FileCheck %s
+; RUN: FileCheck --check-prefix=WARN --allow-empty %s <%t
+
+; If this check fails please read test/CodeGen/AArch64/README for instructions on how to resolve it.
+; WARN-NOT: warning
+
+define void @no_hoist_load(<vscale x 2 x i64>* %out, <vscale x 2 x i64>* %in, i32 %n) {
+; CHECK-LABEL: @no_hoist_load(
+; CHECK: entry:
+; CHECK-NOT: load
+; CHECK: for.body:
+; CHECK: load
+entry:
+  %cmp0 = icmp ugt i32 %n, 0
+  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
+}
+
+define void @hoist_load(<vscale x 2 x i64>* %out, <vscale x 2 x i64>* noalias %in, i32 %n) {
+; CHECK-LABEL: @hoist_load(
+; CHECK: entry:
+; CHECK: load
+; CHECK: for.body:
+; CHECK-NOT: load
+entry:
+  %cmp0 = icmp ugt i32 %n, 0
+  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
+}