[SVE][IR] Scalable Vector IR Type with pr42210 fix

[huntergr]

Summary

Same as D32530 except for a (much) lighter-weight method of rejecting scalable vectors in globals, arrays, and structs in the verifier and a couple of comment changes.

Should address pr42210, which had problems with compile time using LTO due to the recursive verifier implementation.

[thakis]

lib/IR/Verifier.cpp

343

That's still a lot of type walking. Did you have a chance to measure time to thinlto-link some large-ish target with and without this change?

[thakis]

lib/IR/Verifier.cpp

343

Just saw your comment on https://bugs.llvm.org/show_bug.cgi?id=42210 . That seems fine to me. (I usually do min-of-3 when timing things, to reduce effects of caches.) So from my point of view this is ready for relanding.

[huntergr]

lib/IR/Verifier.cpp

343

Yeah, I ran them 5 times each (and cleared the thinlto cache directory between each run, though not the linux fs cache).

The main difference is that I'm not recursing into aggregates-within-aggregates; if there's aggregates with scalable types nested in arrays or structs, they'll still be picked up by the (mostly) linear walks. The fully recursive approach was a leftover from when we only rejected scalable vectors from global variables.

[sdesmalen]

Removing the recursion solves the compile-time issue and still catches all invalid cases.
LGTM.

test/Verifier/scalable-aggregates.ll

7

Just pointing out that the Verifier still errors on all the same invalid cases, but now only the reports errors once compared to the previous patch.

docs/LangRef.rst

 Globals can also have a :ref:`DLL storage class <dllstorageclass>`,
 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.
+
 Syntax::
 
       @<GlobalVarName> = [Linkage] [PreemptionSpecifier] [Visibility]
                          [DLLStorageClass] [ThreadLocal]
                          [(unnamed_addr|local_unnamed_addr)] [AddrSpace]
                          [ExternallyInitialized]
                          <global | constant> <Type> [<InitializerConstant>]
                          [, section "name"] [, comdat [($name)]]

 Vector Type
 """""""""""
 
 :Overview:
 
 A vector type is a simple derived type that represents a vector of
 elements. Vector types are used when multiple primitive data are
 operated in parallel using a single instruction (SIMD). A vector type
-requires a size (number of elements) and an underlying primitive data
-type. Vector types are considered :ref:`first class <t_firstclass>`.
+requires a size (number of elements), an underlying primitive data type,
+and a scalable property to represent vectors where the exact hardware
+vector length is unknown at compile time. Vector types are considered
+:ref:`first class <t_firstclass>`.
 
 :Syntax:
 
 ::
 
-      < <# elements> x <elementtype> >
+      < <# elements> x <elementtype> >          ; Fixed-length vector
+      < vscale x <# elements> x <elementtype> > ; Scalable vector
 
 The number of elements is a constant integer value larger than 0;
 elementtype may be any integer, floating-point or pointer type. Vectors
-of size zero are not allowed.
+of size zero are not allowed. For scalable vectors, the total number of
+elements is a constant multiple (called vscale) of the specified number
+of elements; vscale is a positive integer that is unknown at compile time
+and the same hardware-dependent constant for all scalable vectors at run
+time. The size of a specific scalable vector type is thus constant within
+IR, even if the exact size in bytes cannot be determined until run time.
 
 :Examples:
 
-+-------------------+--------------------------------------------------+
-| ``<4 x i32>``     | Vector of 4 32-bit integer values.               |
-+-------------------+--------------------------------------------------+
-| ``<8 x float>``   | Vector of 8 32-bit floating-point values.        |
-+-------------------+--------------------------------------------------+
-| ``<2 x i64>``     | Vector of 2 64-bit integer values.               |
-+-------------------+--------------------------------------------------+
-| ``<4 x i64*>``    | Vector of 4 pointers to 64-bit integer values.   |
-+-------------------+--------------------------------------------------+
++------------------------+----------------------------------------------------+
+| ``<4 x i32>``          | Vector of 4 32-bit integer values.                 |
++------------------------+----------------------------------------------------+
+| ``<8 x float>``        | Vector of 8 32-bit floating-point values.          |
++------------------------+----------------------------------------------------+
+| ``<2 x i64>``          | Vector of 2 64-bit integer values.                 |
++------------------------+----------------------------------------------------+
+| ``<4 x i64*>``         | Vector of 4 pointers to 64-bit integer values.     |
++------------------------+----------------------------------------------------+
+| ``<vscale x 4 x i32>`` | Vector with a multiple of 4 32-bit integer values. |
++------------------------+----------------------------------------------------+
 
 .. _t_label:
 
 Label Type
 ^^^^^^^^^^
 
 :Overview:
 

 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 
 ::
 
       <result> = extractelement <n x <ty>> <val>, <ty2> <idx>  ; yields <ty>
+      <result> = extractelement <vscale x n x <ty>> <val>, <ty2> <idx> ; yields <ty>
 
 Overview:
 """""""""
 
 The '``extractelement``' instruction extracts a single scalar element
 from a vector at a specified index.
 
 Arguments:
 """"""""""
 
 The first operand of an '``extractelement``' instruction is a value of
 :ref:`vector <t_vector>` type. The second operand is an index indicating
 the position from which to extract the element. The index may be a
 variable of any integer type.
 
 Semantics:
 """"""""""
 
 The result is a scalar of the same type as the element type of ``val``.
 Its value is the value at position ``idx`` of ``val``. If ``idx``
-exceeds the length of ``val``, the result is a
+exceeds the length of ``val`` for a fixed-length vector, the result is a
+:ref:`poison value <poisonvalues>`. For a scalable vector, if the value
+of ``idx`` exceeds the runtime length of the vector, the result is a
 :ref:`poison value <poisonvalues>`.
 
 Example:
 """"""""
 
 .. code-block:: text
 
       <result> = extractelement <4 x i32> %vec, i32 0    ; yields i32
 
 .. _i_insertelement:
 
 '``insertelement``' Instruction
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 
 ::
 
       <result> = insertelement <n x <ty>> <val>, <ty> <elt>, <ty2> <idx>    ; yields <n x <ty>>
+      <result> = insertelement <vscale x n x <ty>> <val>, <ty> <elt>, <ty2> <idx> ; yields <vscale x n x <ty>>
 
 Overview:
 """""""""
 
 The '``insertelement``' instruction inserts a scalar element into a
 vector at a specified index.
 
 Arguments:
 """"""""""
 
 The first operand of an '``insertelement``' instruction is a value of
 :ref:`vector <t_vector>` type. The second operand is a scalar value whose
 type must equal the element type of the first operand. The third operand
 is an index indicating the position at which to insert the value. The
 index may be a variable of any integer type.
 
 Semantics:
 """"""""""
 
 The result is a vector of the same type as ``val``. Its element values
 are those of ``val`` except at position ``idx``, where it gets the value
-``elt``. If ``idx`` exceeds the length of ``val``, the result
+``elt``. If ``idx`` exceeds the length of ``val`` for a fixed-length vector,
+the result is a :ref:`poison value <poisonvalues>`. For a scalable vector,
+if the value of ``idx`` exceeds the runtime length of the vector, the result
 is a :ref:`poison value <poisonvalues>`.
 
 Example:
 """"""""
 
 .. code-block:: text
 
       <result> = insertelement <4 x i32> %vec, i32 1, i32 0    ; yields <4 x i32>
 
 .. _i_shufflevector:
 
 '``shufflevector``' Instruction
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 
 ::
 
       <result> = shufflevector <n x <ty>> <v1>, <n x <ty>> <v2>, <m x i32> <mask>    ; yields <m x <ty>>
+      <result> = shufflevector <vscale x n x <ty>> <v1>, <vscale x n x <ty>> v2, <vscale x m x i32> <mask>  ; yields <vscale x m x <ty>>
 
 Overview:
 """""""""
 
 The '``shufflevector``' instruction constructs a permutation of elements
 from two input vectors, returning a vector with the same element type as
 the input and length that is the same as the shuffle mask.
 

 The elements of the two input vectors are numbered from left to right
 across both of the vectors. The shuffle mask operand specifies, for each
 element of the result vector, which element of the two input vectors the
 result element gets. If the shuffle mask is undef, the result vector is
 undef. If any element of the mask operand is undef, that element of the
 result is undef. If the shuffle mask selects an undef element from one
 of the input vectors, the resulting element is undef.
 
+For scalable vectors, the only valid mask values at present are
+``zeroinitializer`` and ``undef``, since we cannot write all indices as
+literals for a vector with a length unknown at compile time.
+
 Example:
 """"""""
 
 .. code-block:: text
 
       <result> = shufflevector <4 x i32> %v1, <4 x i32> %v2,
                               <4 x i32> <i32 0, i32 4, i32 1, i32 5>  ; yields <4 x i32>
       <result> = shufflevector <4 x i32> %v1, <4 x i32> undef,

include/llvm/ADT/DenseMapInfo.h

 
 #ifndef LLVM_ADT_DENSEMAPINFO_H
 #define LLVM_ADT_DENSEMAPINFO_H
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/PointerLikeTypeTraits.h"
+#include "llvm/Support/ScalableSize.h"
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <utility>
 
 namespace llvm {
 
 template<typename T>

 
 template <> struct DenseMapInfo<hash_code> {
   static inline hash_code getEmptyKey() { return hash_code(-1); }
   static inline hash_code getTombstoneKey() { return hash_code(-2); }
   static unsigned getHashValue(hash_code val) { return val; }
   static bool isEqual(hash_code LHS, hash_code RHS) { return LHS == RHS; }
 };
 
+template <> struct DenseMapInfo<ElementCount> {
+  static inline ElementCount getEmptyKey() { return {~0U, true}; }
+  static inline ElementCount getTombstoneKey() { return {~0U - 1, false}; }
+  static unsigned getHashValue(const ElementCount& EltCnt) {
+    if (EltCnt.Scalable)
+      return (EltCnt.Min * 37U) - 1U;
+
+    return EltCnt.Min * 37U;
+  }
+
+  static bool isEqual(const ElementCount& LHS, const ElementCount& RHS) {
+    return LHS == RHS;
+  }
+};
+
 } // end namespace llvm
 
 #endif // LLVM_ADT_DENSEMAPINFO_H

include/llvm/IR/DerivedTypes.h

 #define LLVM_IR_DERIVEDTYPES_H
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/IR/Type.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Compiler.h"
+#include "llvm/Support/ScalableSize.h"
 #include <cassert>
 #include <cstdint>
 
 namespace llvm {
 
 class Value;
 class APInt;
 class LLVMContext;
SequentialType(TypeID TID, Type *ElType, uint64_t NumElements)
     ContainedTys = &ContainedType;
     NumContainedTys = 1;
   }
 
 public:
   SequentialType(const SequentialType &) = delete;
   SequentialType &operator=(const SequentialType &) = delete;
 
+  /// For scalable vectors, this will return the minimum number of elements
+  /// in the vector.
   uint64_t getNumElements() const { return NumElements; }
   Type *getElementType() const { return ContainedType; }
 
   /// Methods for support type inquiry through isa, cast, and dyn_cast.
   static bool classof(const Type *T) {
     return T->getTypeID() == ArrayTyID || T->getTypeID() == VectorTyID;
   }
 };

 };
 
 uint64_t Type::getArrayNumElements() const {
   return cast<ArrayType>(this)->getNumElements();
 }
 
 /// Class to represent vector types.
 class VectorType : public SequentialType {
-  VectorType(Type *ElType, unsigned NumEl);
+  /// A fully specified VectorType is of the form <vscale x n x Ty>. 'n' is the
+  /// minimum number of elements of type Ty contained within the vector, and
+  /// 'vscale x' indicates that the total element count is an integer multiple
+  /// of 'n', where the multiple is either guaranteed to be one, or is
+  /// statically unknown at compile time.
+  ///
+  /// If the multiple is known to be 1, then the extra term is discarded in
+  /// textual IR:
+  ///
+  /// <4 x i32>          - a vector containing 4 i32s
+  /// <vscale x 4 x i32> - a vector containing an unknown integer multiple
+  ///                      of 4 i32s
+
+  VectorType(Type *ElType, unsigned NumEl, bool Scalable = false);
+  VectorType(Type *ElType, ElementCount EC);
+
+  // If true, the total number of elements is an unknown multiple of the
+  // minimum 'NumElements' from SequentialType. Otherwise the total number
+  // of elements is exactly equal to 'NumElements'.
+  bool Scalable;
 
 public:
   VectorType(const VectorType &) = delete;
   VectorType &operator=(const VectorType &) = delete;
 
   /// This static method is the primary way to construct an VectorType.
-  static VectorType *get(Type *ElementType, unsigned NumElements);
+  static VectorType *get(Type *ElementType, ElementCount EC);
+  static VectorType *get(Type *ElementType, unsigned NumElements,
+                         bool Scalable = false) {
+    return VectorType::get(ElementType, {NumElements, Scalable});
+  }
 
   /// This static method gets a VectorType with the same number of elements as
   /// the input type, and the element type is an integer type of the same width
   /// as the input element type.
   static VectorType *getInteger(VectorType *VTy) {
     unsigned EltBits = VTy->getElementType()->getPrimitiveSizeInBits();
     assert(EltBits && "Element size must be of a non-zero size");
     Type *EltTy = IntegerType::get(VTy->getContext(), EltBits);
-    return VectorType::get(EltTy, VTy->getNumElements());
+    return VectorType::get(EltTy, VTy->getElementCount());
   }
 
   /// This static method is like getInteger except that the element types are
   /// twice as wide as the elements in the input type.
   static VectorType *getExtendedElementVectorType(VectorType *VTy) {
     unsigned EltBits = VTy->getElementType()->getPrimitiveSizeInBits();
     Type *EltTy = IntegerType::get(VTy->getContext(), EltBits * 2);
-    return VectorType::get(EltTy, VTy->getNumElements());
+    return VectorType::get(EltTy, VTy->getElementCount());
   }
 
   /// This static method is like getInteger except that the element types are
   /// half as wide as the elements in the input type.
   static VectorType *getTruncatedElementVectorType(VectorType *VTy) {
     unsigned EltBits = VTy->getElementType()->getPrimitiveSizeInBits();
     assert((EltBits & 1) == 0 &&
            "Cannot truncate vector element with odd bit-width");
     Type *EltTy = IntegerType::get(VTy->getContext(), EltBits / 2);
-    return VectorType::get(EltTy, VTy->getNumElements());
+    return VectorType::get(EltTy, VTy->getElementCount());
   }
 
   /// This static method returns a VectorType with half as many elements as the
   /// input type and the same element type.
   static VectorType *getHalfElementsVectorType(VectorType *VTy) {
-    unsigned NumElts = VTy->getNumElements();
-    assert ((NumElts & 1) == 0 &&
+    auto EltCnt = VTy->getElementCount();
+    assert ((EltCnt.Min & 1) == 0 &&
             "Cannot halve vector with odd number of elements.");
-    return VectorType::get(VTy->getElementType(), NumElts/2);
+    return VectorType::get(VTy->getElementType(), EltCnt/2);
   }
 
   /// This static method returns a VectorType with twice as many elements as the
   /// input type and the same element type.
   static VectorType *getDoubleElementsVectorType(VectorType *VTy) {
-    unsigned NumElts = VTy->getNumElements();
-    return VectorType::get(VTy->getElementType(), NumElts*2);
+    auto EltCnt = VTy->getElementCount();
+    assert((VTy->getNumElements() * 2ull) <= UINT_MAX &&
+           "Too many elements in vector");
+    return VectorType::get(VTy->getElementType(), EltCnt*2);
   }
 
   /// Return true if the specified type is valid as a element type.
   static bool isValidElementType(Type *ElemTy);
 
-  /// Return the number of bits in the Vector type.
+  /// Return an ElementCount instance to represent the (possibly scalable)
+  /// number of elements in the vector.
+  ElementCount getElementCount() const {
+    uint64_t MinimumEltCnt = getNumElements();
+    assert(MinimumEltCnt <= UINT_MAX && "Too many elements in vector");
+    return { (unsigned)MinimumEltCnt, Scalable };
+  }
+
+  /// Returns whether or not this is a scalable vector (meaning the total
+  /// element count is a multiple of the minimum).
+  bool isScalable() const {
+    return Scalable;
+  }
+
+  /// Return the minimum number of bits in the Vector type.
   /// Returns zero when the vector is a vector of pointers.
   unsigned getBitWidth() const {
     return getNumElements() * getElementType()->getPrimitiveSizeInBits();
   }
 
   /// Methods for support type inquiry through isa, cast, and dyn_cast.
   static bool classof(const Type *T) {
     return T->getTypeID() == VectorTyID;
   }
 };
 
 unsigned Type::getVectorNumElements() const {
   return cast<VectorType>(this)->getNumElements();
 }
 
+bool Type::getVectorIsScalable() const {
+  return cast<VectorType>(this)->isScalable();
+}
+
 /// Class to represent pointers.
 class PointerType : public Type {
   explicit PointerType(Type *ElType, unsigned AddrSpace);
 
   Type *PointeeTy;
 
 public:
   PointerType(const PointerType &) = delete;

include/llvm/IR/Type.h

public:
 
   inline uint64_t getArrayNumElements() const;
 
   Type *getArrayElementType() const {
     assert(getTypeID() == ArrayTyID);
     return ContainedTys[0];
   }
 
+  inline bool getVectorIsScalable() const;
   inline unsigned getVectorNumElements() const;
   Type *getVectorElementType() const {
     assert(getTypeID() == VectorTyID);
     return ContainedTys[0];
   }
 
   Type *getPointerElementType() const {
     assert(getTypeID() == PointerTyID);

include/llvm/Support/ScalableSize.h

+//===- ScalableSize.h - Scalable vector size info ---------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file provides a struct that can be used to query the size of IR types
+// which may be scalable vectors. It provides convenience operators so that
+// it can be used in much the same way as a single scalar value.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_SCALABLESIZE_H
+#define LLVM_SUPPORT_SCALABLESIZE_H
+
+namespace llvm {
+
+class ElementCount {
+public:
+  unsigned Min;  // Minimum number of vector elements.
+  bool Scalable; // If true, NumElements is a multiple of 'Min' determined
+                 // at runtime rather than compile time.
+
+  ElementCount(unsigned Min, bool Scalable)
+  : Min(Min), Scalable(Scalable) {}
+
+  ElementCount operator*(unsigned RHS) {
+    return { Min * RHS, Scalable };
+  }
+  ElementCount operator/(unsigned RHS) {
+    return { Min / RHS, Scalable };
+  }
+
+  bool operator==(const ElementCount& RHS) const {
+    return Min == RHS.Min && Scalable == RHS.Scalable;
+  }
+};
+
+} // end namespace llvm
+
+#endif // LLVM_SUPPORT_SCALABLESIZE_H

lib/AsmParser/LLLexer.cpp

#define KEYWORD(STR)                                                           \
   KEYWORD(eq); KEYWORD(ne); KEYWORD(slt); KEYWORD(sgt); KEYWORD(sle);
   KEYWORD(sge); KEYWORD(ult); KEYWORD(ugt); KEYWORD(ule); KEYWORD(uge);
   KEYWORD(oeq); KEYWORD(one); KEYWORD(olt); KEYWORD(ogt); KEYWORD(ole);
   KEYWORD(oge); KEYWORD(ord); KEYWORD(uno); KEYWORD(ueq); KEYWORD(une);
 
   KEYWORD(xchg); KEYWORD(nand); KEYWORD(max); KEYWORD(min); KEYWORD(umax);
   KEYWORD(umin);
 
+  KEYWORD(vscale);
   KEYWORD(x);
   KEYWORD(blockaddress);
 
   // Metadata types.
   KEYWORD(distinct);
 
   // Use-list order directives.
   KEYWORD(uselistorder);

lib/AsmParser/LLParser.cpp

bool LLParser::ParseStructBody(SmallVectorImpl<Type*> &Body) {
   return ParseToken(lltok::rbrace, "expected '}' at end of struct");
 }
 
 /// ParseArrayVectorType - Parse an array or vector type, assuming the first
 /// token has already been consumed.
 ///   Type
 ///     ::= '[' APSINTVAL 'x' Types ']'
 ///     ::= '<' APSINTVAL 'x' Types '>'
+///     ::= '<' 'vscale' 'x' APSINTVAL 'x' Types '>'
 bool LLParser::ParseArrayVectorType(Type *&Result, bool isVector) {
+  bool Scalable = false;
+
+  if (isVector && Lex.getKind() == lltok::kw_vscale) {
+    Lex.Lex(); // consume the 'vscale'
+    if (ParseToken(lltok::kw_x, "expected 'x' after vscale"))
+      return true;
+
+    Scalable = true;
+  }
+
   if (Lex.getKind() != lltok::APSInt || Lex.getAPSIntVal().isSigned() ||
       Lex.getAPSIntVal().getBitWidth() > 64)
     return TokError("expected number in address space");
 
   LocTy SizeLoc = Lex.getLoc();
   uint64_t Size = Lex.getAPSIntVal().getZExtValue();
   Lex.Lex();
 
bool LLParser::ParseArrayVectorType(Type *&Result, bool isVector) {
 
   if (isVector) {
     if (Size == 0)
       return Error(SizeLoc, "zero element vector is illegal");
     if ((unsigned)Size != Size)
       return Error(SizeLoc, "size too large for vector");
     if (!VectorType::isValidElementType(EltTy))
       return Error(TypeLoc, "invalid vector element type");
-    Result = VectorType::get(EltTy, unsigned(Size));
+    Result = VectorType::get(EltTy, unsigned(Size), Scalable);
   } else {
     if (!ArrayType::isValidElementType(EltTy))
       return Error(TypeLoc, "invalid array element type");
     Result = ArrayType::get(EltTy, Size);
   }
   return false;
 }
 

lib/AsmParser/LLToken.h

enum Kind {
   less,
   greater, // <  >
   lparen,
   rparen,  // (  )
   exclaim, // !
   bar,     // |
   colon,   // :
 
+  kw_vscale,
   kw_x,
   kw_true,
   kw_false,
   kw_declare,
   kw_define,
   kw_global,
   kw_constant,
 

lib/Bitcode/Reader/BitcodeReader.cpp

while (true) {
     case bitc::TYPE_CODE_ARRAY:     // ARRAY: [numelts, eltty]
       if (Record.size() < 2)
         return error("Invalid record");
       ResultTy = getTypeByID(Record[1]);
       if (!ResultTy || !ArrayType::isValidElementType(ResultTy))
         return error("Invalid type");
       ResultTy = ArrayType::get(ResultTy, Record[0]);
       break;
-    case bitc::TYPE_CODE_VECTOR:    // VECTOR: [numelts, eltty]
+    case bitc::TYPE_CODE_VECTOR:    // VECTOR: [numelts, eltty] or
+                                    //         [numelts, eltty, scalable]
       if (Record.size() < 2)
         return error("Invalid record");
       if (Record[0] == 0)
         return error("Invalid vector length");
       ResultTy = getTypeByID(Record[1]);
       if (!ResultTy || !StructType::isValidElementType(ResultTy))
         return error("Invalid type");
-      ResultTy = VectorType::get(ResultTy, Record[0]);
+      bool Scalable = Record.size() > 2 ? Record[2] : false;
+      ResultTy = VectorType::get(ResultTy, Record[0], Scalable);
       break;
     }
 
     if (NumRecords >= TypeList.size())
       return error("Invalid TYPE table");
     if (TypeList[NumRecords])
       return error(
           "Invalid TYPE table: Only named structs can be forward referenced");

lib/Bitcode/Writer/BitcodeWriter.cpp

case Type::ArrayTyID: {
       Code = bitc::TYPE_CODE_ARRAY;
       TypeVals.push_back(AT->getNumElements());
       TypeVals.push_back(VE.getTypeID(AT->getElementType()));
       AbbrevToUse = ArrayAbbrev;
       break;
     }
     case Type::VectorTyID: {
       VectorType *VT = cast<VectorType>(T);
-      // VECTOR [numelts, eltty]
+      // VECTOR [numelts, eltty] or
+      //        [numelts, eltty, scalable]
       Code = bitc::TYPE_CODE_VECTOR;
       TypeVals.push_back(VT->getNumElements());
       TypeVals.push_back(VE.getTypeID(VT->getElementType()));
+      if (VT->isScalable())
+        TypeVals.push_back(VT->isScalable());
       break;
     }
     }
 
     // Emit the finished record.
     Stream.EmitRecord(Code, TypeVals, AbbrevToUse);
     TypeVals.clear();
   }

lib/IR/AsmWriter.cpp

case Type::ArrayTyID: {
     ArrayType *ATy = cast<ArrayType>(Ty);
     OS << '[' << ATy->getNumElements() << " x ";
     print(ATy->getElementType(), OS);
     OS << ']';
     return;
   }
   case Type::VectorTyID: {
     VectorType *PTy = cast<VectorType>(Ty);
-    OS << "<" << PTy->getNumElements() << " x ";
+    OS << "<";
+    if (PTy->isScalable())
+      OS << "vscale x ";
+    OS << PTy->getNumElements() << " x ";
     print(PTy->getElementType(), OS);
     OS << '>';
     return;
   }
   }
   llvm_unreachable("Invalid TypeID");
 }
 

lib/IR/LLVMContextImpl.h

#include "llvm/IR/Metadata.def"
   using FunctionTypeSet = DenseSet<FunctionType *, FunctionTypeKeyInfo>;
   FunctionTypeSet FunctionTypes;
   using StructTypeSet = DenseSet<StructType *, AnonStructTypeKeyInfo>;
   StructTypeSet AnonStructTypes;
   StringMap<StructType*> NamedStructTypes;
   unsigned NamedStructTypesUniqueID = 0;
 
   DenseMap<std::pair<Type *, uint64_t>, ArrayType*> ArrayTypes;
-  DenseMap<std::pair<Type *, unsigned>, VectorType*> VectorTypes;
+  DenseMap<std::pair<Type *, ElementCount>, VectorType*> VectorTypes;
   DenseMap<Type*, PointerType*> PointerTypes;  // Pointers in AddrSpace = 0
   DenseMap<std::pair<Type*, unsigned>, PointerType*> ASPointerTypes;
 
   /// ValueHandles - This map keeps track of all of the value handles that are
   /// watching a Value*.  The Value::HasValueHandle bit is used to know
   /// whether or not a value has an entry in this map.
   using ValueHandlesTy = DenseMap<Value *, ValueHandleBase *>;
   ValueHandlesTy ValueHandles;

lib/IR/Type.cpp

return !ElemTy->isVoidTy() && !ElemTy->isLabelTy() &&
          !ElemTy->isMetadataTy() && !ElemTy->isFunctionTy() &&
          !ElemTy->isTokenTy();
 }
 
 //===----------------------------------------------------------------------===//
 //                          VectorType Implementation
 //===----------------------------------------------------------------------===//
 
-VectorType::VectorType(Type *ElType, unsigned NumEl)
-  : SequentialType(VectorTyID, ElType, NumEl) {}
+VectorType::VectorType(Type *ElType, ElementCount EC)
+  : SequentialType(VectorTyID, ElType, EC.Min), Scalable(EC.Scalable) {}
 
-VectorType *VectorType::get(Type *ElementType, unsigned NumElements) {
-  assert(NumElements > 0 && "#Elements of a VectorType must be greater than 0");
+VectorType *VectorType::get(Type *ElementType, ElementCount EC) {
+  assert(EC.Min > 0 && "#Elements of a VectorType must be greater than 0");
   assert(isValidElementType(ElementType) && "Element type of a VectorType must "
                                             "be an integer, floating point, or "
                                             "pointer type.");
 
   LLVMContextImpl *pImpl = ElementType->getContext().pImpl;
   VectorType *&Entry = ElementType->getContext().pImpl
-    ->VectorTypes[std::make_pair(ElementType, NumElements)];
-
+                                 ->VectorTypes[std::make_pair(ElementType, EC)];
   if (!Entry)
-    Entry = new (pImpl->Alloc) VectorType(ElementType, NumElements);
+    Entry = new (pImpl->Alloc) VectorType(ElementType, EC);
   return Entry;
 }
 
 bool VectorType::isValidElementType(Type *ElemTy) {
   return ElemTy->isIntegerTy() || ElemTy->isFloatingPointTy() ||
     ElemTy->isPointerTy();
 }
 

lib/IR/Verifier.cpp

 //    only by the unwind edge of an invoke instruction.
 //  * A landingpad instruction must be the first non-PHI instruction in the
 //    block.
 //  * Landingpad instructions must be in a function with a personality function.
 //  * All other things that are tested by asserts spread about the code...
 //
 //===----------------------------------------------------------------------===//
 
+#include "LLVMContextImpl.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/ADT/APFloat.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
explicit Verifier(raw_ostream *OS, bool ShouldTreatBrokenDebugInfoAsError,
                     const Module &M)
       : VerifierSupport(OS, M), LandingPadResultTy(nullptr),
         SawFrameEscape(false), TBAAVerifyHelper(this) {
     TreatBrokenDebugInfoAsError = ShouldTreatBrokenDebugInfoAsError;
   }
 
   bool hasBrokenDebugInfo() const { return BrokenDebugInfo; }
 
+  void verifyTypes() {
+    LLVMContext &Ctx = M.getContext();
+    for (auto &Entry : Ctx.pImpl->ArrayTypes) {
+      Type *EltTy = Entry.second->getElementType();
+      if (auto *VTy = dyn_cast<VectorType>(EltTy))
+        if (VTy->isScalable())
+          CheckFailed("Arrays cannot contain scalable vectors",
+                      Entry.second, &M);
+    }
+
+    for (StructType* STy : Ctx.pImpl->AnonStructTypes)
+      for (Type *EltTy : STy->elements())
+        if (auto *VTy = dyn_cast<VectorType>(EltTy))
+          if (VTy->isScalable())
+            CheckFailed("Structs cannot contain scalable vectors", STy, &M);
+
+    for (auto &Entry : Ctx.pImpl->NamedStructTypes) {
+      StructType *STy = Entry.second;
+      for (Type *EltTy : STy->elements())
+        if (auto *VTy = dyn_cast<VectorType>(EltTy))
+          if (VTy->isScalable())
+            CheckFailed("Structs cannot contain scalable vectors", STy, &M);
+    }
+  }
+
   bool verify(const Function &F) {
     assert(F.getParent() == &M &&
            "An instance of this class only works with a specific module!");
 
     // First ensure the function is well-enough formed to compute dominance
     // information, and directly compute a dominance tree. We don't rely on the
     // pass manager to provide this as it isolates us from a potentially
     // out-of-date dominator tree and makes it significantly more complex to run
for (const StringMapEntry<Comdat> &SMEC : M.getComdatSymbolTable())
       visitComdat(SMEC.getValue());
 
     visitModuleFlags(M);
     visitModuleIdents(M);
     visitModuleCommandLines(M);
 
     verifyCompileUnits();
 
+    verifyTypes();
+
     verifyDeoptimizeCallingConvs();
     DISubprogramAttachments.clear();
     return !Broken;
   }
 
 private:
   // Verification methods...
   void visitGlobalValue(const GlobalValue &GV);
void Verifier::visitGlobalVariable(const GlobalVariable &GV) {
   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 be verifyTypes instead.
+  if (auto *VTy = dyn_cast<VectorType>(GV.getValueType()))
+    if (VTy->isScalable())
+      CheckFailed("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());
 

test/Bitcode/compatibility.ll

define void @typesystem() {
   %t5 = alloca x86_fp80
   ; CHECK: %t5 = alloca x86_fp80
   %t6 = alloca ppc_fp128
   ; CHECK: %t6 = alloca ppc_fp128
   %t7 = alloca x86_mmx
   ; CHECK: %t7 = alloca x86_mmx
   %t8 = alloca %opaquety*
   ; CHECK: %t8 = alloca %opaquety*
+  %t9 = alloca <4 x i32>
+  ; CHECK: %t9 = alloca <4 x i32>
+  %t10 = alloca <vscale x 4 x i32>
+  ; CHECK: %t10 = alloca <vscale x 4 x i32>
 
   ret void
 }
 
 declare void @llvm.token(token)
 ; CHECK: declare void @llvm.token(token)
 
 ;; Inline Assembler Expressions

test/Verifier/scalable-aggregates.ll

+; RUN: not opt -S -verify < %s 2>&1 | FileCheck %s
+
+;; Arrays and Structs cannot contain scalable vectors, since we don't
+;; know the size at compile time and the container types need to have
+;; a known size.
+
+; CHECK-DAG: Arrays cannot contain scalable vectors
+; CHECK-DAG:  [4 x <vscale x 256 x i1>]; ModuleID = '<stdin>'
+; CHECK-DAG: Arrays cannot contain scalable vectors
+; CHECK-DAG:  [2 x <vscale x 4 x i32>]; ModuleID = '<stdin>'
+; CHECK-DAG: Structs cannot contain scalable vectors
+; CHECK-DAG:  { i32, <vscale x 1 x i32> }; ModuleID = '<stdin>'
+;; CHECK-DAG: Structs cannot contain scalable vectors
+; CHECK-DAG: { <vscale x 16 x i8>, <vscale x 2 x double> }; ModuleID = '<stdin>'
+; CHECK-DAG: Structs cannot contain scalable vectors
+; CHECK-DAG:  %sty = type { i64, <vscale x 32 x i16> }; ModuleID = '<stdin>'
+
+%sty = type { i64, <vscale x 32 x i16> }
+
+define void @scalable_aggregates() {
+  %array = alloca [2 x <vscale x 4 x i32>]
+  %struct = alloca { <vscale x 16 x i8>, <vscale x 2 x double> }
+  %named_struct = alloca %sty
+  %s_in_a = alloca [2 x { i32, <vscale x 1 x i32> } ]
+  %a_in_s = alloca { i64, [4 x <vscale x 256 x i1> ] }
+  ret void
+}
 No newline at end of file

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
+
+;; Global _pointers_ to scalable vectors are fine
+; CHECK-NOT: Globals cannot contain scalable vectors
+@ScalableVecPtr = global <vscale x 8 x i16>* zeroinitializer
+
+;; The following errors don't explicitly mention global variables, but
+;; do still guarantee that the error will be caught.
+; CHECK-DAG: Arrays cannot contain scalable vectors
+; CHECK-DAG:  [64 x <vscale x 2 x double>]; ModuleID = '<stdin>'
+@ScalableVecGlobalArray = global [64 x <vscale x 2 x double>] zeroinitializer
+
+; CHECK-DAG: Structs cannot contain scalable vectors
+; CHECK-DAG:  { <vscale x 16 x i64>, <vscale x 16 x i1> }; ModuleID = '<stdin>'
+@ScalableVecGlobalStruct = global { <vscale x 16 x i64>, <vscale x 16 x i1> } zeroinitializer
+
+; CHECK-DAG: Structs cannot contain scalable vectors
+; CHECK-DAG  { <vscale x 4 x i64>, <vscale x 32 x i8> }; ModuleID = '<stdin>'
+@ScalableVecMixed = global { [4 x i32], [2 x { <vscale x 4 x i64>,  <vscale x 32 x i8> }]} zeroinitializer

unittests/IR/CMakeLists.txt

add_llvm_unittest(IRTests
   PatternMatch.cpp
   TimePassesTest.cpp
   TypesTest.cpp
   UseTest.cpp
   UserTest.cpp
   ValueHandleTest.cpp
   ValueMapTest.cpp
   ValueTest.cpp
+  VectorTypesTest.cpp
   VerifierTest.cpp
   WaymarkTest.cpp
   )
 
 target_link_libraries(IRTests PRIVATE LLVMTestingSupport)

unittests/IR/VectorTypesTest.cpp

+//===--- llvm/unittest/IR/VectorTypesTest.cpp - vector types unit tests ---===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/Support/ScalableSize.h"
+#include "gtest/gtest.h"
+using namespace llvm;
+
+namespace {
+TEST(VectorTypesTest, FixedLength) {
+  LLVMContext Ctx;
+
+  Type *Int16Ty = Type::getInt16Ty(Ctx);
+  Type *Int32Ty = Type::getInt32Ty(Ctx);
+  Type *Int64Ty = Type::getInt64Ty(Ctx);
+  Type *Float64Ty = Type::getDoubleTy(Ctx);
+
+  VectorType *V8Int32Ty = VectorType::get(Int32Ty, 8);
+  ASSERT_FALSE(V8Int32Ty->isScalable());
+  EXPECT_EQ(V8Int32Ty->getNumElements(), 8U);
+  EXPECT_EQ(V8Int32Ty->getElementType()->getScalarSizeInBits(), 32U);
+
+  VectorType *V8Int16Ty = VectorType::get(Int16Ty, {8, false});
+  ASSERT_FALSE(V8Int16Ty->isScalable());
+  EXPECT_EQ(V8Int16Ty->getNumElements(), 8U);
+  EXPECT_EQ(V8Int16Ty->getElementType()->getScalarSizeInBits(), 16U);
+
+  ElementCount EltCnt(4, false);
+  VectorType *V4Int64Ty = VectorType::get(Int64Ty, EltCnt);
+  ASSERT_FALSE(V4Int64Ty->isScalable());
+  EXPECT_EQ(V4Int64Ty->getNumElements(), 4U);
+  EXPECT_EQ(V4Int64Ty->getElementType()->getScalarSizeInBits(), 64U);
+
+  VectorType *V2Int64Ty = VectorType::get(Int64Ty, EltCnt/2);
+  ASSERT_FALSE(V2Int64Ty->isScalable());
+  EXPECT_EQ(V2Int64Ty->getNumElements(), 2U);
+  EXPECT_EQ(V2Int64Ty->getElementType()->getScalarSizeInBits(), 64U);
+
+  VectorType *V8Int64Ty = VectorType::get(Int64Ty, EltCnt*2);
+  ASSERT_FALSE(V8Int64Ty->isScalable());
+  EXPECT_EQ(V8Int64Ty->getNumElements(), 8U);
+  EXPECT_EQ(V8Int64Ty->getElementType()->getScalarSizeInBits(), 64U);
+
+  VectorType *V4Float64Ty = VectorType::get(Float64Ty, EltCnt);
+  ASSERT_FALSE(V4Float64Ty->isScalable());
+  EXPECT_EQ(V4Float64Ty->getNumElements(), 4U);
+  EXPECT_EQ(V4Float64Ty->getElementType()->getScalarSizeInBits(), 64U);
+
+  VectorType *ExtTy = VectorType::getExtendedElementVectorType(V8Int16Ty);
+  EXPECT_EQ(ExtTy, V8Int32Ty);
+  ASSERT_FALSE(ExtTy->isScalable());
+  EXPECT_EQ(ExtTy->getNumElements(), 8U);
+  EXPECT_EQ(ExtTy->getElementType()->getScalarSizeInBits(), 32U);
+
+  VectorType *TruncTy = VectorType::getTruncatedElementVectorType(V8Int32Ty);
+  EXPECT_EQ(TruncTy, V8Int16Ty);
+  ASSERT_FALSE(TruncTy->isScalable());
+  EXPECT_EQ(TruncTy->getNumElements(), 8U);
+  EXPECT_EQ(TruncTy->getElementType()->getScalarSizeInBits(), 16U);
+
+  VectorType *HalvedTy = VectorType::getHalfElementsVectorType(V4Int64Ty);
+  EXPECT_EQ(HalvedTy, V2Int64Ty);
+  ASSERT_FALSE(HalvedTy->isScalable());
+  EXPECT_EQ(HalvedTy->getNumElements(), 2U);
+  EXPECT_EQ(HalvedTy->getElementType()->getScalarSizeInBits(), 64U);
+
+  VectorType *DoubledTy = VectorType::getDoubleElementsVectorType(V4Int64Ty);
+  EXPECT_EQ(DoubledTy, V8Int64Ty);
+  ASSERT_FALSE(DoubledTy->isScalable());
+  EXPECT_EQ(DoubledTy->getNumElements(), 8U);
+  EXPECT_EQ(DoubledTy->getElementType()->getScalarSizeInBits(), 64U);
+
+  VectorType *ConvTy = VectorType::getInteger(V4Float64Ty);
+  EXPECT_EQ(ConvTy, V4Int64Ty);
+  ASSERT_FALSE(ConvTy->isScalable());
+  EXPECT_EQ(ConvTy->getNumElements(), 4U);
+  EXPECT_EQ(ConvTy->getElementType()->getScalarSizeInBits(), 64U);
+
+  EltCnt = V8Int64Ty->getElementCount();
+  EXPECT_EQ(EltCnt.Min, 8U);
+  ASSERT_FALSE(EltCnt.Scalable);
+}
+
+TEST(VectorTypesTest, Scalable) {
+  LLVMContext Ctx;
+
+  Type *Int16Ty = Type::getInt16Ty(Ctx);
+  Type *Int32Ty = Type::getInt32Ty(Ctx);
+  Type *Int64Ty = Type::getInt64Ty(Ctx);
+  Type *Float64Ty = Type::getDoubleTy(Ctx);
+
+  VectorType *ScV8Int32Ty = VectorType::get(Int32Ty, 8, true);
+  ASSERT_TRUE(ScV8Int32Ty->isScalable());
+  EXPECT_EQ(ScV8Int32Ty->getNumElements(), 8U);
+  EXPECT_EQ(ScV8Int32Ty->getElementType()->getScalarSizeInBits(), 32U);
+
+  VectorType *ScV8Int16Ty = VectorType::get(Int16Ty, {8, true});
+  ASSERT_TRUE(ScV8Int16Ty->isScalable());
+  EXPECT_EQ(ScV8Int16Ty->getNumElements(), 8U);
+  EXPECT_EQ(ScV8Int16Ty->getElementType()->getScalarSizeInBits(), 16U);
+
+  ElementCount EltCnt(4, true);
+  VectorType *ScV4Int64Ty = VectorType::get(Int64Ty, EltCnt);
+  ASSERT_TRUE(ScV4Int64Ty->isScalable());
+  EXPECT_EQ(ScV4Int64Ty->getNumElements(), 4U);
+  EXPECT_EQ(ScV4Int64Ty->getElementType()->getScalarSizeInBits(), 64U);
+
+  VectorType *ScV2Int64Ty = VectorType::get(Int64Ty, EltCnt/2);
+  ASSERT_TRUE(ScV2Int64Ty->isScalable());
+  EXPECT_EQ(ScV2Int64Ty->getNumElements(), 2U);
+  EXPECT_EQ(ScV2Int64Ty->getElementType()->getScalarSizeInBits(), 64U);
+
+  VectorType *ScV8Int64Ty = VectorType::get(Int64Ty, EltCnt*2);
+  ASSERT_TRUE(ScV8Int64Ty->isScalable());
+  EXPECT_EQ(ScV8Int64Ty->getNumElements(), 8U);
+  EXPECT_EQ(ScV8Int64Ty->getElementType()->getScalarSizeInBits(), 64U);
+
+  VectorType *ScV4Float64Ty = VectorType::get(Float64Ty, EltCnt);
+  ASSERT_TRUE(ScV4Float64Ty->isScalable());
+  EXPECT_EQ(ScV4Float64Ty->getNumElements(), 4U);
+  EXPECT_EQ(ScV4Float64Ty->getElementType()->getScalarSizeInBits(), 64U);
+
+  VectorType *ExtTy = VectorType::getExtendedElementVectorType(ScV8Int16Ty);
+  EXPECT_EQ(ExtTy, ScV8Int32Ty);
+  ASSERT_TRUE(ExtTy->isScalable());
+  EXPECT_EQ(ExtTy->getNumElements(), 8U);
+  EXPECT_EQ(ExtTy->getElementType()->getScalarSizeInBits(), 32U);
+
+  VectorType *TruncTy = VectorType::getTruncatedElementVectorType(ScV8Int32Ty);
+  EXPECT_EQ(TruncTy, ScV8Int16Ty);
+  ASSERT_TRUE(TruncTy->isScalable());
+  EXPECT_EQ(TruncTy->getNumElements(), 8U);
+  EXPECT_EQ(TruncTy->getElementType()->getScalarSizeInBits(), 16U);
+
+  VectorType *HalvedTy = VectorType::getHalfElementsVectorType(ScV4Int64Ty);
+  EXPECT_EQ(HalvedTy, ScV2Int64Ty);
+  ASSERT_TRUE(HalvedTy->isScalable());
+  EXPECT_EQ(HalvedTy->getNumElements(), 2U);
+  EXPECT_EQ(HalvedTy->getElementType()->getScalarSizeInBits(), 64U);
+
+  VectorType *DoubledTy = VectorType::getDoubleElementsVectorType(ScV4Int64Ty);
+  EXPECT_EQ(DoubledTy, ScV8Int64Ty);
+  ASSERT_TRUE(DoubledTy->isScalable());
+  EXPECT_EQ(DoubledTy->getNumElements(), 8U);
+  EXPECT_EQ(DoubledTy->getElementType()->getScalarSizeInBits(), 64U);
+
+  VectorType *ConvTy = VectorType::getInteger(ScV4Float64Ty);
+  EXPECT_EQ(ConvTy, ScV4Int64Ty);
+  ASSERT_TRUE(ConvTy->isScalable());
+  EXPECT_EQ(ConvTy->getNumElements(), 4U);
+  EXPECT_EQ(ConvTy->getElementType()->getScalarSizeInBits(), 64U);
+
+  EltCnt = ScV8Int64Ty->getElementCount();
+  EXPECT_EQ(EltCnt.Min, 8U);
+  ASSERT_TRUE(EltCnt.Scalable);
+}
+
+} // end anonymous namespace