[IR] Allow scalable vectors in structs to support intrinsics returning multiple values.

[craig.topper]

Summary

RISC-V would like to use a struct of scalable vectors to return multiple
values from intrinsics. This woud also be needed for target independent
intrinsics like llvm.sadd.overflow.

This patch removes the existing restriction for this. I've modified
StructType::isSized to consider a struct containing scalable vectors
as unsized so the verifier won't allow loads/stores/allocas of these
structs.

[sdesmalen]

This change should be mentioned in the LangRef as well, because that currently specifies:

scalable vectors cannot be global variables or members of structs or arrays because their size is unknown at compile time.

Not allowing scalable-vectors in aggregates was one of the restrictions we had to accept in order to get the scalable vector type accepted, so I guess this also needs a ping to the mailing list? I tried to find a pointer to where this was previously discussed, but the closest I can find is this thread: https://groups.google.com/g/llvm-dev/c/TIEJ5-Y4jxU/m/TGHP_2CDBAAJ which mentions discussions @huntergr had at the dev meeting. From what I remember, there was concern that scalable vectors were already complicated and this restriction was a way to avoid issues around struct layout, alignment, offsets in structs with both scalable and non-scalable members, etc. If these types can't be allocated or use getelemenptr, some or most of that complexity probably falls away, so this limited relaxation seems quite elegant.

llvm/test/Other/scalable-vector-struct-intrinsic.ll

7

I guess this patch allows:

declare { <vscale x 2 x i32>, i32 } @foo()

Is that deliberate?

[craig.topper]

Don't allow function arguments or returns to use structs containing scalable vectors unless they are intrinsics.
Update LangRef.

[kito-cheng]

Don't allow function arguments or returns to use structs containing scalable vectors unless they are intrinsics.

This is RISC-V specific question: Does it means we disallow passing register tuple type (NF>1) in future too?

[craig.topper]

In D94142#2484167, @kito-cheng wrote:

Don't allow function arguments or returns to use structs containing scalable vectors unless they are intrinsics.

This is RISC-V specific question: Does it means we disallow passing register tuple type (NF>1) in future too?

I hope we can just break them down to individual values when clang generates IR. The generic code in SelectionDAG for returning a struct depends on being able to compute offsets so we'll definitely need to be careful with returns.

[sdesmalen]

llvm/test/Other/scalable-vector-struct-intrinsic.ll

7

With the example above I actually meant to point out the combination of a scalable-vector and a non-scalable type (i32). I'm not sure if this would still be a problem if the only nodes that can return such a struct are intrinsics. Probably SelectionDAGBuilder can just take return value K from the SDNode for the lowered intrinsic. Can you confirm this won't lead to any issues?

[craig.topper]

llvm/test/Other/scalable-vector-struct-intrinsic.ll

7

Allowing scalable and non-scalable to be mixed was intentional. I'm using it in D94286.

The one issue I did encounter so far is that computeValueVTs called from SelectionDAGBuilder tries to create a StructLayout to compute offsets which causing the warning from TypeSize to trigger. Most callers of computeValueVTs don't want the offsets so I bandaged over it by not creating the StructLayout if the offsets aren't needed.

[craig.topper]

Remove return and argument restriction. I misunderstood what I was being asked.

[craig.topper]

Add assertion to make sure we don't create StructLayout for a struct containing a scalable vector. Previously we only got a warning from TypeSize.

[craig.topper]

Replace assertion in StructLayout::StructLayout with a call to getFixedValue() which will assert for us.

[kito-cheng]

This patch removes the existing restriction for this. I've modified
StructType::isSized to consider a struct containing scalable vectors
as unsized so the verifier won't allow loads/stores/allocas of these
structs.

I worry about this will become a problem when we implement tuple type on C level,
clang will emit alloca & load & store no matter using -O0 or -O1.

For example following program:

struct foo{
    int x;
};

int bar(void)
{
    struct foo a;
    return a.x;
}

Will emit following code:

define i32 @bar() #0 {
  %1 = alloca %struct.foo, align 4
  %2 = getelementptr inbounds %struct.foo, %struct.foo* %1, i32 0, i32 0
  %3 = load i32, i32* %2, align 4
  ret i32 %3
}

[craig.topper]

In D94142#2489466, @kito-cheng wrote:

This patch removes the existing restriction for this. I've modified
StructType::isSized to consider a struct containing scalable vectors
as unsized so the verifier won't allow loads/stores/allocas of these
structs.

I worry about this will become a problem when we implement tuple type on C level,
clang will emit alloca & load & store no matter using -O0 or -O1.

For example following program:

struct foo{
    int x;
};

int bar(void)
{
    struct foo a;
    return a.x;
}

Will emit following code:

define i32 @bar() #0 {
  %1 = alloca %struct.foo, align 4
  %2 = getelementptr inbounds %struct.foo, %struct.foo* %1, i32 0, i32 0
  %3 = load i32, i32* %2, align 4
  ret i32 %3
}

It won't be a struct in clang's type system. It's it own special builtin type. I hope we can control the codegen of that type and emit it as multiple allocas/loads/stores. I haven't looked at this yet. Clang can also emit fixed size memcpys of structs which would be broken for this. So we are going to need to customize clang.

[kito-cheng]

In D94142#2489469, @craig.topper wrote:

It won't be a struct in clang's type system. It's it own special builtin type. I hope we can control the codegen of that type and emit it as multiple allocas/loads/stores. I haven't looked at this yet. Clang can also emit fixed size memcpys of structs which would be broken for this. So we are going to need to customize clang.

OK, I don't have strong opinion on allow or disallow allocas/loads/stores, just make sure we have aware there is potential issue :)

[sdesmalen]

llvm/lib/IR/Type.cpp

398

This line made me realise there's currently no test for the nested case (struct containing a struct with a scalable vector). I'm not sure if this could lead to any complications, for example in CopyTo/FromParts that tries to breaks down the aggregate when passing values to a different basic block.
Is this something you've tried?

[craig.topper]

llvm/lib/IR/Type.cpp

398

I tried something like this

define i32 @foo({ {<vscale x 2 x i32>, <vscale x 2 x i32>}, i32 } %x, <vscale x 2 x i32>* %y, <vscale x 2 x i32>* %z) {                                                                                                                   
entry:                                                                                                                                                                                                                                    
  br label %return                                                                                                                                                                                                                        
                                                                                                                                                                                                                                          
return:                                                                                                                                                                                                                                   
  %a = extractvalue { {<vscale x 2 x i32>, <vscale x 2 x i32>}, i32 } %x, 1                                                                                                                                                               
  %b = extractvalue { {<vscale x 2 x i32>, <vscale x 2 x i32>}, i32 } %x, 0, 0                                                                                                                                                            
  %c = extractvalue { {<vscale x 2 x i32>, <vscale x 2 x i32>}, i32 } %x, 0, 1                                                                                                                                                            
  store <vscale x 2 x i32> %b, <vscale x 2 x i32>* %y                                                                                                                                                                                     
  store <vscale x 2 x i32> %c, <vscale x 2 x i32>* %z                                                                                                                                                                                     
                                                                                                                                                                                                                                          
  ret i32 %a                                                                                                                                                                                                                              
}

The struct gets recursively broken down by ComputeValueVTs. With the fix to ignore struct layout when Offsets is null that I put in https://reviews.llvm.org/D94286, it was able to break it down without issue.

[sdesmalen]

llvm/lib/IR/Type.cpp

398

Thanks for verifying that this works. I think the change to ComputeValueVTs from D94286 should be moved to this patch and the above test added to check it successfully compiles for RVV and/or SVE (I just tried the above test for the latter and can confirm this works). D94286 only has tests for intrinsics that are custom-lowered, the above test doesn't need any custom lowering and fails without the change, so it feels like that should live in this patch. Are you happy to make that change?

[craig.topper]

-Add SelectionDAG test.
-Don't query StructLayout in ComputeValueVTs if we don't need to calculate offsets.
-Use getFixedValue after getting the TypeSize for array elements in ComputeValueVTs instead of relying on uint64_t conversion operator. This will give a more immediate failure if someone ever tries to make arrays of scalable vectors supported.
-Update the GlobalISel version of ComputeValueVTs as well, but I'm not sure if we can test scalable vectors with GlobalISel yet

[sdesmalen]

Thanks for the latest changes, the patch looks good to me now!

llvm/docs/LangRef.rst

 an optional :ref:`runtime preemption specifier <runtime_preemption_model>`,
 an optional :ref:`global attributes <glattrs>` and
 an optional list of attached :ref:`metadata <metadata>`.
 
 Variables and aliases can have a
 :ref:`Thread Local Storage Model <tls_model>`.
 
 :ref:`Scalable vectors <t_vector>` cannot be global variables or members of
-structs or arrays because their size is unknown at compile time.
+arrays because their size is unknown at compile time. They are allowed in
+structs to facilitate intrinsics returning multiple values. Structs containing
+scalable vectors cannot be used in loads, stores, allocas, or GEPs.
 
 Syntax::
 
       @<GlobalVarName> = [Linkage] [PreemptionSpecifier] [Visibility]
                          [DLLStorageClass] [ThreadLocal]
                          [(unnamed_addr|local_unnamed_addr)] [AddrSpace]
                          [ExternallyInitialized]
                          <global | constant> <Type> [<InitializerConstant>]

llvm/include/llvm/IR/DerivedTypes.h

public:
 
   /// Return true if this is a type with an identity that has no body specified
   /// yet. These prints as 'opaque' in .ll files.
   bool isOpaque() const { return (getSubclassData() & SCDB_HasBody) == 0; }
 
   /// isSized - Return true if this is a sized type.
   bool isSized(SmallPtrSetImpl<Type *> *Visited = nullptr) const;
 
+  /// Returns true if this struct contains a scalable vector.
+  bool containsScalableVectorType() const;
+
   /// Return true if this is a named struct that has a non-empty name.
   bool hasName() const { return SymbolTableEntry != nullptr; }
 
   /// Return the name for this struct type if it has an identity.
   /// This may return an empty string for an unnamed struct type.  Do not call
   /// this on an literal type.
   StringRef getName() const;
 

llvm/lib/CodeGen/Analysis.cpp

 ///
 void llvm::ComputeValueVTs(const TargetLowering &TLI, const DataLayout &DL,
                            Type *Ty, SmallVectorImpl<EVT> &ValueVTs,
                            SmallVectorImpl<EVT> *MemVTs,
                            SmallVectorImpl<uint64_t> *Offsets,
                            uint64_t StartingOffset) {
   // Given a struct type, recursively traverse the elements.
   if (StructType *STy = dyn_cast<StructType>(Ty)) {
-    const StructLayout *SL = DL.getStructLayout(STy);
+    // If the Offsets aren't needed, don't query the struct layout. This allows
+    // us to support structs with scalable vectors for operations that don't
+    // need offsets.
+    const StructLayout *SL = Offsets ? DL.getStructLayout(STy) : nullptr;
     for (StructType::element_iterator EB = STy->element_begin(),
                                       EI = EB,
                                       EE = STy->element_end();
-         EI != EE; ++EI)
+         EI != EE; ++EI) {
+      // Don't compute the element offset if we didn't get a StructLayout above.
+      uint64_t EltOffset = SL ? SL->getElementOffset(EI - EB) : 0;
       ComputeValueVTs(TLI, DL, *EI, ValueVTs, MemVTs, Offsets,
-                      StartingOffset + SL->getElementOffset(EI - EB));
+                      StartingOffset + EltOffset);
+    }
     return;
   }
   // Given an array type, recursively traverse the elements.
   if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
     Type *EltTy = ATy->getElementType();
-    uint64_t EltSize = DL.getTypeAllocSize(EltTy);
+    uint64_t EltSize = DL.getTypeAllocSize(EltTy).getFixedValue();
     for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i)
       ComputeValueVTs(TLI, DL, EltTy, ValueVTs, MemVTs, Offsets,
                       StartingOffset + i * EltSize);
     return;
   }
   // Interpret void as zero return values.
   if (Ty->isVoidTy())
     return;

 }
 
 void llvm::computeValueLLTs(const DataLayout &DL, Type &Ty,
                             SmallVectorImpl<LLT> &ValueTys,
                             SmallVectorImpl<uint64_t> *Offsets,
                             uint64_t StartingOffset) {
   // Given a struct type, recursively traverse the elements.
   if (StructType *STy = dyn_cast<StructType>(&Ty)) {
-    const StructLayout *SL = DL.getStructLayout(STy);
-    for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I)
+    // If the Offsets aren't needed, don't query the struct layout. This allows
+    // us to support structs with scalable vectors for operations that don't
+    // need offsets.
+    const StructLayout *SL = Offsets ? DL.getStructLayout(STy) : nullptr;
+    for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I) {
+      uint64_t EltOffset = SL ? SL->getElementOffset(I) : 0;
       computeValueLLTs(DL, *STy->getElementType(I), ValueTys, Offsets,
-                       StartingOffset + SL->getElementOffset(I));
+                       StartingOffset + EltOffset);
+    }
     return;
   }
   // Given an array type, recursively traverse the elements.
   if (ArrayType *ATy = dyn_cast<ArrayType>(&Ty)) {
     Type *EltTy = ATy->getElementType();
-    uint64_t EltSize = DL.getTypeAllocSize(EltTy);
+    uint64_t EltSize = DL.getTypeAllocSize(EltTy).getFixedValue();
     for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i)
       computeValueLLTs(DL, *EltTy, ValueTys, Offsets,
                        StartingOffset + i * EltSize);
     return;
   }
   // Interpret void as zero return values.
   if (Ty.isVoidTy())
     return;

llvm/lib/IR/DataLayout.cpp

if (!isAligned(TyAlign, StructSize)) {
       IsPadded = true;
       StructSize = alignTo(StructSize, TyAlign);
     }
 
     // Keep track of maximum alignment constraint.
     StructAlignment = std::max(TyAlign, StructAlignment);
 
     MemberOffsets[i] = StructSize;
-    StructSize += DL.getTypeAllocSize(Ty); // Consume space for this data item
+    // Consume space for this data item
+    StructSize += DL.getTypeAllocSize(Ty).getFixedValue();
   }
 
   // Add padding to the end of the struct so that it could be put in an array
   // and all array elements would be aligned correctly.
   if (!isAligned(StructAlignment, StructSize)) {
     IsPadded = true;
     StructSize = alignTo(StructSize, StructAlignment);
   }

llvm/lib/IR/Type.cpp

StructType *StructType::get(LLVMContext &Context, ArrayRef<Type*> ETypes,
   } else {
     // The struct type was found. Just return it.
     ST = *Insertion.first;
   }
 
   return ST;
 }
 
+bool StructType::containsScalableVectorType() const {
+  for (Type *Ty : elements()) {
+    if (isa<ScalableVectorType>(Ty))
+      return true;
+    if (auto *STy = dyn_cast<StructType>(Ty))
+      if (STy->containsScalableVectorType())
+        return true;
+  }
+
+  return false;
+}
+
 void StructType::setBody(ArrayRef<Type*> Elements, bool isPacked) {
   assert(isOpaque() && "Struct body already set!");
 
   setSubclassData(getSubclassData() | SCDB_HasBody);
   if (isPacked)
     setSubclassData(getSubclassData() | SCDB_Packed);
 
   NumContainedTys = Elements.size();
if (isOpaque())
     return false;
 
   if (Visited && !Visited->insert(const_cast<StructType*>(this)).second)
     return false;
 
   // Okay, our struct is sized if all of the elements are, but if one of the
   // elements is opaque, the struct isn't sized *yet*, but may become sized in
   // the future, so just bail out without caching.
-  for (element_iterator I = element_begin(), E = element_end(); I != E; ++I)
-    if (!(*I)->isSized(Visited))
+  for (Type *Ty : elements()) {
+    // If the struct contains a scalable vector type, don't consider it sized.
+    // This prevents it from being used in loads/stores/allocas/GEPs.
+    if (isa<ScalableVectorType>(Ty))
+      return false;
+    if (!Ty->isSized(Visited))
       return false;
+  }
 
   // Here we cheat a bit and cast away const-ness. The goal is to memoize when
   // we find a sized type, as types can only move from opaque to sized, not the
   // other way.
   const_cast<StructType*>(this)->setSubclassData(
     getSubclassData() | SCDB_IsSized);
   return true;
 }
 
 StringRef StructType::getName() const {
   assert(!isLiteral() && "Literal structs never have names");
   if (!SymbolTableEntry) return StringRef();
 
   return ((StringMapEntry<StructType*> *)SymbolTableEntry)->getKey();
 }
 
 bool StructType::isValidElementType(Type *ElemTy) {
   return !ElemTy->isVoidTy() && !ElemTy->isLabelTy() &&
          !ElemTy->isMetadataTy() && !ElemTy->isFunctionTy() &&
-         !ElemTy->isTokenTy() && !isa<ScalableVectorType>(ElemTy);
+         !ElemTy->isTokenTy();
 }
 
 bool StructType::isLayoutIdentical(StructType *Other) const {
   if (this == Other) return true;
 
   if (isPacked() != Other->isPacked())
     return false;
 

llvm/lib/IR/Verifier.cpp

for (auto *MD : MDs) {
     if (auto *GVE = dyn_cast<DIGlobalVariableExpression>(MD))
       visitDIGlobalVariableExpression(*GVE);
     else
       AssertDI(false, "!dbg attachment of global variable must be a "
                       "DIGlobalVariableExpression");
   }
 
   // Scalable vectors cannot be global variables, since we don't know
-  // the runtime size. If the global is a struct or an array containing
-  // scalable vectors, that will be caught by the isValidElementType methods
-  // in StructType or ArrayType instead.
+  // the runtime size. If the global is an array containing scalable vectors,
+  // that will be caught by the isValidElementType methods in StructType or
+  // ArrayType instead.
   Assert(!isa<ScalableVectorType>(GV.getValueType()),
          "Globals cannot contain scalable vectors", &GV);
 
+  if (auto *STy = dyn_cast<StructType>(GV.getValueType()))
+    Assert(!STy->containsScalableVectorType(),
+           "Globals cannot contain scalable vectors", &GV);
+
   if (!GV.hasInitializer()) {
     visitGlobalValue(GV);
     return;
   }
 
   // Walk any aggregate initializers looking for bitcasts between address spaces
   visitConstantExprsRecursively(GV.getInitializer());
 

llvm/test/CodeGen/RISCV/scalable-vector-struct.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -mtriple=riscv32 -mattr=+experimental-v -verify-machineinstrs < %s | FileCheck %s
+
+; This demonstrates that we can pass a struct containing scalable vectors across
+; a basic block.
+
+define i32 @foo({ {<vscale x 2 x i32>, <vscale x 2 x i32>}, i32 } %x, <vscale x 2 x i32>* %y, <vscale x 2 x i32>* %z) {
+; CHECK-LABEL: foo:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    vsetvli a3, zero, e32,m1,ta,mu
+; CHECK-NEXT:    vse32.v v16, (a1)
+; CHECK-NEXT:    vse32.v v17, (a2)
+; CHECK-NEXT:    ret
+entry:
+  br label %return
+
+return:
+  %a = extractvalue { {<vscale x 2 x i32>, <vscale x 2 x i32>}, i32 } %x, 1
+  %b = extractvalue { {<vscale x 2 x i32>, <vscale x 2 x i32>}, i32 } %x, 0, 0
+  %c = extractvalue { {<vscale x 2 x i32>, <vscale x 2 x i32>}, i32 } %x, 0, 1
+  store <vscale x 2 x i32> %b, <vscale x 2 x i32>* %y
+  store <vscale x 2 x i32> %c, <vscale x 2 x i32>* %z
+
+  ret i32 %a
+}

llvm/test/Other/scalable-vector-struct-intrinsic.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -verify < %s 2>&1 | FileCheck %s
+
+; Make sure we allow scalable vectors in structs for returning multiple
+; values from intrinsics.
+
+declare { <vscale x 2 x i32>, <vscale x 2 x i1> } @llvm.sadd.with.overflow.nxv2i32(<vscale x 2 x i32>, <vscale x 2 x i32>)
+
+define <vscale x 2 x i32> @foo(<vscale x 2 x i32> %x, <vscale x 2 x i32> %y) {
+; CHECK-LABEL: @foo(
+; CHECK-NEXT:    [[A:%.*]] = call { <vscale x 2 x i32>, <vscale x 2 x i1> } @llvm.sadd.with.overflow.nxv2i32(<vscale x 2 x i32> [[X:%.*]], <vscale x 2 x i32> [[Y:%.*]])
+; CHECK-NEXT:    [[B:%.*]] = extractvalue { <vscale x 2 x i32>, <vscale x 2 x i1> } [[A]], 0
+; CHECK-NEXT:    ret <vscale x 2 x i32> [[B]]
+;
+  %a = call { <vscale x 2 x i32>, <vscale x 2 x i1> } @llvm.sadd.with.overflow.nxv2i32(<vscale x 2 x i32> %x, <vscale x 2 x i32> %y)
+  %b = extractvalue { <vscale x 2 x i32>, <vscale x 2 x i1> } %a, 0
+  ret <vscale x 2 x i32> %b
+}

llvm/test/Other/scalable-vector-struct.ll

-; RUN: not opt -S -verify < %s 2>&1 | FileCheck %s
-
-;; Structs cannot contain scalable vectors; make sure we detect them even
-;; when nested inside other aggregates.
-
-%ty = type [2 x { i32, <vscale x 1 x i32> }]
-; CHECK: error: invalid element type for struct
-; CHECK: %ty = type [2 x { i32, <vscale x 1 x i32> }]

llvm/test/Verifier/scalable-global-vars.ll

 ; RUN: not opt -S -verify < %s 2>&1 | FileCheck %s
 
 ;; Global variables cannot be scalable vectors, since we don't
 ;; know the size at compile time.
 
 ; CHECK: Globals cannot contain scalable vectors
 ; CHECK-NEXT: <vscale x 4 x i32>* @ScalableVecGlobal
 @ScalableVecGlobal = global <vscale x 4 x i32> zeroinitializer
 
+; CHECK-NEXT: Globals cannot contain scalable vectors
+; CHECK-NEXT: { i32, <vscale x 4 x i32> }* @ScalableVecStructGlobal
+@ScalableVecStructGlobal = global { i32,  <vscale x 4 x i32> } zeroinitializer
+
 ;; Global _pointers_ to scalable vectors are fine
 ; CHECK-NOT: Globals cannot contain scalable vectors
-@ScalableVecPtr = global <vscale x 8 x i16>* zeroinitializer
+@ScalableVecPtr = global <vscale x 8 x i16>* zeroinitializer
 

llvm/test/Verifier/scalable-vector-struct-alloca.ll

+; RUN: not opt -S -verify < %s 2>&1 | FileCheck %s
+
+define void @alloca() {
+; CHECK: error: Cannot allocate unsized type
+  %a = alloca { i32, <vscale x 1 x i32> }
+  ret void
+}

llvm/test/Verifier/scalable-vector-struct-load.ll

+; RUN: not opt -S -verify < %s 2>&1 | FileCheck %s
+
+define <vscale x 1 x i32> @load({ i32, <vscale x 1 x i32> }* %x) {
+; CHECK: error: loading unsized types is not allowed
+  %a = load { i32, <vscale x 1 x i32> }, { i32, <vscale x 1 x i32> }* %x
+  %b = extractvalue { i32, <vscale x 1 x i32> } %a, 1
+  ret <vscale x 1 x i32> %b
+}

llvm/test/Verifier/scalable-vector-struct-store.ll

+; RUN: not opt -S -verify < %s 2>&1 | FileCheck %s
+
+define void @store({ i32, <vscale x 1 x i32> }* %x, i32 %y, <vscale x 1 x i32> %z) {
+; CHECK: error: storing unsized types is not allowed
+  %a = insertvalue { i32, <vscale x 1 x i32> } undef, i32 %y, 0
+  %b = insertvalue { i32, <vscale x 1 x i32> } %a,  <vscale x 1 x i32> %z, 1
+  store { i32, <vscale x 1 x i32> } %b, { i32, <vscale x 1 x i32> }* %x
+  ret void
+}