[Constants] Represent the runtime length of a scalable vector. [IR support for SVE scalable vectors 3/4]

[paulwalker-arm]

Summary

The length of a scalable vector is unknown during compilation.  When
vectorising loops the runtime length is required to update induction
variables and thus a representation is required within the IR.

This patch introduces the 'vscale' identifier to represent the scaling
factor 'n' of a scalable vector of the form '<n x #elements x ty>'.

In use, induction variable updates for scalable vectorisation become:

  ; i += number_of_elements(<n x 4 x i32)
  %i.next = add i32 %i, mul (i32 vscale, i32 4)

[deadalnix]

include/llvm-c/Core.h

223

This changes the enum value in the C API. Please don't. This will cause hard to track failures in user that use the C API to bind other languages.

[mehdi_amini]

include/llvm-c/Core.h

223

We should have a comment before the enum.

Also we could we have a unittest for this:
I have in mind something that just does:

// Check that enum values don't change
if (LLVMArgumentValueKind != 0)
  report_fatal_error("Enum changed value")
If (.... )

Or:

static_assert(LLVMArgumentValueKind != 0, "C-API Enum value changed");

[rengolin]

Assuming we're all happy with vscale, and all noted concerns are addressed, I don't see anything wrong with this patch.

Just reminding, this is not an approval. As we discussed on the list, any final IR change decision will be taken on the list, after extensive review by more than just the few folks that are looking at these patches.

lib/IR/Constants.cpp

1363

Ouch, ok, this is a separate thing that can be done now, independent of vscale. Please move this to a different patch and propose it on a new review on its own.

docs/LangRef.rst

**Zero initialization**
     is always exactly equivalent to using explicit zero initializers.
 **Metadata node**
     A metadata node is a constant tuple without types. For example:
     "``!{!0, !{!2, !0}, !"test"}``". Metadata can reference constant values,
     for example: "``!{!0, i32 0, i8* @global, i64 (i64)* @function, !"str"}``".
     Unlike other typed constants that are meant to be interpreted as part of
     the instruction stream, metadata is a place to attach additional
     information such as debug info.
+**Scalable vector length**
+    Scalable vectors take the form "``< n x <# elements> x <elementtype> >``",
+    where "``n``" is an unknown positive integer constant.  The string
+    '``vscale``' can be used to reference this value wherever an
+    :ref:`integer <t_integer>` is expected.
 
 Global Variable and Function Addresses
 --------------------------------------
 
 The addresses of :ref:`global variables <globalvars>` and
 :ref:`functions <functionstructure>` are always implicitly valid
 (link-time) constants. These constants are explicitly referenced when
 the :ref:`identifier for the global <identifiers>` is used and always have

include/llvm-c/Core.h

typedef enum {
   LLVMGlobalVariableValueKind,
   LLVMBlockAddressValueKind,
   LLVMConstantExprValueKind,
   LLVMConstantArrayValueKind,
   LLVMConstantStructValueKind,
   LLVMConstantVectorValueKind,
 
   LLVMUndefValueValueKind,
+  LLVMVScaleValueValueKind,
   LLVMConstantAggregateZeroValueKind,
   LLVMConstantDataArrayValueKind,
   LLVMConstantDataVectorValueKind,
   LLVMConstantIntValueKind,
   LLVMConstantFPValueKind,
   LLVMConstantPointerNullValueKind,
   LLVMConstantTokenNoneValueKind,
 
macro(Constant)                         \
       macro(ConstantTokenNone)              \
       macro(ConstantVector)                 \
       macro(GlobalValue)                    \
         macro(GlobalAlias)                  \
         macro(GlobalObject)                 \
           macro(Function)                   \
           macro(GlobalVariable)             \
       macro(UndefValue)                     \
+      macro(VScaleValue)                    \
     macro(Instruction)                      \
       macro(BinaryOperator)                 \
       macro(CallInst)                       \
         macro(IntrinsicInst)                \
           macro(DbgInfoIntrinsic)           \
             macro(DbgDeclareInst)           \
           macro(MemIntrinsic)               \
             macro(MemCpyInst)               \

include/llvm/Bitcode/LLVMBitCodes.h

CST_CODE_INLINEASM_OLD = 18,   // INLINEASM:     [sideeffect|alignstack,
                                  //                 asmstr,conststr]
   CST_CODE_CE_SHUFVEC_EX = 19,   // SHUFVEC_EX:    [opty, opval, opval, opval]
   CST_CODE_CE_INBOUNDS_GEP = 20, // INBOUNDS_GEP:  [n x operands]
   CST_CODE_BLOCKADDRESS = 21,    // CST_CODE_BLOCKADDRESS [fnty, fnval, bb#]
   CST_CODE_DATA = 22,            // DATA:          [n x elements]
   CST_CODE_INLINEASM = 23,       // INLINEASM:     [sideeffect|alignstack|
                                  //                 asmdialect,asmstr,conststr]
   CST_CODE_CE_GEP_WITH_INRANGE_INDEX = 24, //      [opty, flags, n x operands]
+  CST_CODE_VSCALE = 25,          // VSCALE
 };
 
 /// CastOpcodes - These are values used in the bitcode files to encode which
 /// cast a CST_CODE_CE_CAST or a XXX refers to.  The values of these enums
 /// have no fixed relation to the LLVM IR enum values.  Changing these will
 /// break compatibility with old files.
 enum CastOpcodes {
   CAST_TRUNC = 0,

include/llvm/IR/Constants.h

public:
   unsigned getNumElements() const;
 
   /// Methods for support type inquiry through isa, cast, and dyn_cast:
   static bool classof(const Value *V) {
     return V->getValueID() == UndefValueVal;
   }
 };
 
+//===----------------------------------------------------------------------===//
+/// A constant representing the scaling factor 'n' of a scalable vector of the
+/// form '<n x #elements x ty>'.
+///
+class VScaleValue final : public ConstantData {
+  VScaleValue(const VScaleValue &) = delete;
+
+  friend class Constant;
+  void destroyConstantImpl();
+
+  explicit VScaleValue(Type *T) : ConstantData(T, VScaleValueVal) {}
+
+public:
+  /// Static factory methods - Return a 'vscale' object of the specified type.
+  static Constant *get(Type *T);
+
+  /// Methods for support type inquiry through isa, cast, and dyn_cast:
+  static bool classof(const Value *V) {
+    return V->getValueID() == VScaleValueVal;
+  }
+};
+
 } // End llvm namespace
 
 #endif

include/llvm/IR/Value.def

 
 // ConstantAggregate.
 HANDLE_CONSTANT(ConstantArray)
 HANDLE_CONSTANT(ConstantStruct)
 HANDLE_CONSTANT(ConstantVector)
 
 // ConstantData.
 HANDLE_CONSTANT(UndefValue)
+HANDLE_CONSTANT(VScaleValue)
 HANDLE_CONSTANT(ConstantAggregateZero)
 HANDLE_CONSTANT(ConstantDataArray)
 HANDLE_CONSTANT(ConstantDataVector)
 HANDLE_CONSTANT(ConstantInt)
 HANDLE_CONSTANT(ConstantFP)
 HANDLE_CONSTANT(ConstantPointerNull)
 HANDLE_CONSTANT(ConstantTokenNone)
 

lib/AsmParser/LLLexer.cpp

#define KEYWORD(STR)                                                           \
   KEYWORD(extern_weak);
   KEYWORD(external);
   KEYWORD(thread_local);
   KEYWORD(localdynamic);
   KEYWORD(initialexec);
   KEYWORD(localexec);
   KEYWORD(zeroinitializer);
   KEYWORD(undef);
+  KEYWORD(vscale);
   KEYWORD(null);
   KEYWORD(none);
   KEYWORD(to);
   KEYWORD(caller);
   KEYWORD(within);
   KEYWORD(from);
   KEYWORD(tail);
   KEYWORD(musttail);

lib/AsmParser/LLParser.h

enum {
       t_LocalID, t_GlobalID,           // ID in UIntVal.
       t_LocalName, t_GlobalName,       // Name in StrVal.
       t_APSInt, t_APFloat,             // Value in APSIntVal/APFloatVal.
       t_Null, t_Undef, t_Zero, t_None, // No value.
       t_EmptyArray,                    // No value:  []
       t_Constant,                      // Value in ConstantVal.
       t_InlineAsm,                     // Value in FTy/StrVal/StrVal2/UIntVal.
       t_ConstantStruct,                // Value in ConstantStructElts.
-      t_PackedConstantStruct           // Value in ConstantStructElts.
+      t_PackedConstantStruct,          // Value in ConstantStructElts.
+      t_VScale                         // No value.
     } Kind = t_LocalID;
 
     LLLexer::LocTy Loc;
     unsigned UIntVal;
     FunctionType *FTy = nullptr;
     std::string StrVal, StrVal2;
     APSInt APSIntVal;
     APFloat APFloatVal{0.0};

lib/AsmParser/LLParser.cpp

case lltok::kw_true:
     ID.Kind = ValID::t_Constant;
     break;
   case lltok::kw_false:
     ID.ConstantVal = ConstantInt::getFalse(Context);
     ID.Kind = ValID::t_Constant;
     break;
   case lltok::kw_null: ID.Kind = ValID::t_Null; break;
   case lltok::kw_undef: ID.Kind = ValID::t_Undef; break;
+  case lltok::kw_vscale: ID.Kind = ValID::t_VScale; break;
   case lltok::kw_zeroinitializer: ID.Kind = ValID::t_Zero; break;
   case lltok::kw_none: ID.Kind = ValID::t_None; break;
 
   case lltok::lbrace: {
     // ValID ::= '{' ConstVector '}'
     Lex.Lex();
     SmallVector<Constant*, 16> Elts;
     if (ParseGlobalValueVector(Elts) ||
case ValID::t_Null:
     V = ConstantPointerNull::get(cast<PointerType>(Ty));
     return false;
   case ValID::t_Undef:
     // FIXME: LabelTy should not be a first-class type.
     if (!Ty->isFirstClassType() || Ty->isLabelTy())
       return Error(ID.Loc, "invalid type for undef constant");
     V = UndefValue::get(Ty);
     return false;
+  case ValID::t_VScale:
+    if (!Ty->isIntegerTy())
+      return Error(ID.Loc, "vscale must be an integer type");
+    V = VScaleValue::get(Ty);
+    return false;
   case ValID::t_EmptyArray:
     if (!Ty->isArrayTy() || cast<ArrayType>(Ty)->getNumElements() != 0)
       return Error(ID.Loc, "invalid empty array initializer");
     V = UndefValue::get(Ty);
     return false;
   case ValID::t_Zero:
     // FIXME: LabelTy should not be a first-class type.
     if (!Ty->isFirstClassType() || Ty->isLabelTy())
bool LLParser::parseConstantValue(Type *Ty, Constant *&C) {
   ValID ID;
   auto Loc = Lex.getLoc();
   if (ParseValID(ID, /*PFS=*/nullptr))
     return true;
   switch (ID.Kind) {
   case ValID::t_APSInt:
   case ValID::t_APFloat:
   case ValID::t_Undef:
+  case ValID::t_VScale:
   case ValID::t_Constant:
   case ValID::t_ConstantStruct:
   case ValID::t_PackedConstantStruct: {
     Value *V;
     if (ConvertValIDToValue(Ty, ID, V, /*PFS=*/nullptr))
       return true;
     assert(isa<Constant>(V) && "Expected a constant value");
     C = cast<Constant>(V);

lib/AsmParser/LLToken.h

enum Kind {
   kw_extern_weak,
   kw_external,
   kw_thread_local,
   kw_localdynamic,
   kw_initialexec,
   kw_localexec,
   kw_zeroinitializer,
   kw_undef,
+  kw_vscale,
   kw_null,
   kw_none,
   kw_to,
   kw_caller,
   kw_within,
   kw_from,
   kw_tail,
   kw_musttail,

lib/Bitcode/Reader/BitcodeReader.cpp

while (true) {
     Type *VoidType = Type::getVoidTy(Context);
     Value *V = nullptr;
     unsigned BitCode = Stream.readRecord(Entry.ID, Record);
     switch (BitCode) {
     default:  // Default behavior: unknown constant
     case bitc::CST_CODE_UNDEF:     // UNDEF
       V = UndefValue::get(CurTy);
       break;
+    case bitc::CST_CODE_VSCALE:    // VSCALE
+      V = VScaleValue::get(CurTy);
+      break;
     case bitc::CST_CODE_SETTYPE:   // SETTYPE: [typeid]
       if (Record.empty())
         return error("Invalid record");
       if (Record[0] >= TypeList.size() || !TypeList[Record[0]])
         return error("Invalid record");
       if (TypeList[Record[0]] == VoidType)
         return error("Invalid constant type");
       CurTy = TypeList[Record[0]];

lib/Bitcode/Writer/BitcodeWriter.cpp

for (unsigned i = FirstVal; i != LastVal; ++i) {
     }
     const Constant *C = cast<Constant>(V);
     unsigned Code = -1U;
     unsigned AbbrevToUse = 0;
     if (C->isNullValue()) {
       Code = bitc::CST_CODE_NULL;
     } else if (isa<UndefValue>(C)) {
       Code = bitc::CST_CODE_UNDEF;
+    } else if (isa<VScaleValue>(C)) {
+      Code = bitc::CST_CODE_VSCALE;
     } else if (const ConstantInt *IV = dyn_cast<ConstantInt>(C)) {
       if (IV->getBitWidth() <= 64) {
         uint64_t V = IV->getSExtValue();
         emitSignedInt64(Record, V);
         Code = bitc::CST_CODE_INTEGER;
         AbbrevToUse = CONSTANTS_INTEGER_ABBREV;
       } else {                             // Wide integers, > 64 bits in size.
         // We have an arbitrary precision integer value to write whose

lib/IR/AsmWriter.cpp

if (isa<ConstantTokenNone>(CV)) {
     return;
   }
 
   if (isa<UndefValue>(CV)) {
     Out << "undef";
     return;
   }
 
+  if (isa<VScaleValue>(CV)) {
+    Out << "vscale";
+    return;
+  }
+
   if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(CV)) {
     Out << CE->getOpcodeName();
     WriteOptimizationInfo(Out, CE);
     if (CE->isCompare())
       Out << ' ' << CmpInst::getPredicateName(
                         static_cast<CmpInst::Predicate>(CE->getPredicate()));
     Out << " (";
 

lib/IR/Constants.cpp

if (auto *VT = dyn_cast<VectorType>(Ty))
     return VT->getNumElements();
   return Ty->getStructNumElements();
 }
 
 //===----------------------------------------------------------------------===//
 //                         UndefValue Implementation
 //===----------------------------------------------------------------------===//
 
+UndefValue *UndefValue::get(Type *Ty) {
+  std::unique_ptr<UndefValue> &Entry = Ty->getContext().pImpl->UVConstants[Ty];
+  if (!Entry)
+    Entry.reset(new UndefValue(Ty));
+
+  return Entry.get();
+}
+
+/// Remove the constant from the constant table.
+void UndefValue::destroyConstantImpl() {
+  // Free the constant and any dangling references to it.
+  getContext().pImpl->UVConstants.erase(getType());
+}
+
 UndefValue *UndefValue::getSequentialElement() const {
   return UndefValue::get(getType()->getSequentialElementType());
 }
 
 UndefValue *UndefValue::getStructElement(unsigned Elt) const {
   return UndefValue::get(getType()->getStructElementType(Elt));
 }
 
unsigned UndefValue::getNumElements() const {
   if (auto *AT = dyn_cast<ArrayType>(Ty))
     return AT->getNumElements();
   if (auto *VT = dyn_cast<VectorType>(Ty))
     return VT->getNumElements();
   return Ty->getStructNumElements();
 }
 
 //===----------------------------------------------------------------------===//
+//                        VScaleValue Implementation
+//===----------------------------------------------------------------------===//
+
+Constant *VScaleValue::get(Type *Ty) {
+  assert(Ty->isIntegerTy() && "VScale must be an integer type!");
+
+  std::unique_ptr<VScaleValue> &Entry =
+      Ty->getContext().pImpl->VSVConstants[Ty];
+  if (!Entry)
+    Entry.reset(new VScaleValue(Ty));
+
+  return Entry.get();
+}
+
+/// Remove the constant from the constant table.
+void VScaleValue::destroyConstantImpl() {
+  // Free the constant and any dangling references to it.
+  getContext().pImpl->VSVConstants.erase(getType());
+}
+
+//===----------------------------------------------------------------------===//
 //                            ConstantXXX Classes
 //===----------------------------------------------------------------------===//
 
 template <typename ItTy, typename EltTy>
 static bool rangeOnlyContains(ItTy Start, ItTy End, EltTy Elt) {
   for (; Start != End; ++Start)
     if (*Start != Elt)
       return false;
ConstantPointerNull *ConstantPointerNull::get(PointerType *Ty) {
   return Entry.get();
 }
 
 /// Remove the constant from the constant table.
 void ConstantPointerNull::destroyConstantImpl() {
   getContext().pImpl->CPNConstants.erase(getType());
 }
 
-UndefValue *UndefValue::get(Type *Ty) {
-  std::unique_ptr<UndefValue> &Entry = Ty->getContext().pImpl->UVConstants[Ty];
-  if (!Entry)
-    Entry.reset(new UndefValue(Ty));
-
-  return Entry.get();
-}
-
-/// Remove the constant from the constant table.
-void UndefValue::destroyConstantImpl() {
-  // Free the constant and any dangling references to it.
-  getContext().pImpl->UVConstants.erase(getType());
-}
-
 BlockAddress *BlockAddress::get(BasicBlock *BB) {
   assert(BB->getParent() && "Block must have a parent");
   return get(BB->getParent(), BB);
 }
 
 BlockAddress *BlockAddress::get(Function *F, BasicBlock *BB) {
   BlockAddress *&BA =
     F->getContext().pImpl->BlockAddresses[std::make_pair(F, BB)];

lib/IR/LLVMContextImpl.h

#include "llvm/IR/Metadata.def"
   StructConstantsTy StructConstants;
   
   typedef ConstantUniqueMap<ConstantVector> VectorConstantsTy;
   VectorConstantsTy VectorConstants;
 
   DenseMap<PointerType *, std::unique_ptr<ConstantPointerNull>> CPNConstants;
 
   DenseMap<Type *, std::unique_ptr<UndefValue>> UVConstants;
+  DenseMap<Type *, std::unique_ptr<VScaleValue>> VSVConstants;
 
   StringMap<ConstantDataSequential*> CDSConstants;
 
   DenseMap<std::pair<const Function *, const BasicBlock *>, BlockAddress *>
     BlockAddresses;
   ConstantUniqueMap<ConstantExpr> ExprConstants;
 
   ConstantUniqueMap<InlineAsm> InlineAsms;

lib/IR/LLVMContextImpl.cpp

#include "llvm/IR/Metadata.def"
   ArrayConstants.freeConstants();
   StructConstants.freeConstants();
   VectorConstants.freeConstants();
   InlineAsms.freeConstants();
 
   CAZConstants.clear();
   CPNConstants.clear();
   UVConstants.clear();
+  VSVConstants.clear();
   IntConstants.clear();
   FPConstants.clear();
 
   for (auto &CDSConstant : CDSConstants)
     delete CDSConstant.second;
   CDSConstants.clear();
 
   // Destroy attributes.

test/Bitcode/compatibility.ll

 @const.false = constant i1 false
 ; CHECK: @const.false = constant i1 false
 @const.int = constant i32 zeroinitializer
 ; CHECK: @const.int = constant i32 0
 @const.float = constant double 0.0
 ; CHECK: @const.float = constant double 0.0
 @const.null = constant i8* null
 ; CHECK: @const.null = constant i8* null
[e-mail] = constant i32 vscale
+; CHECK: @const.vscale = constant i32 vscale
 %const.struct.type = type { i32, i8 }
 %const.struct.type.packed = type <{ i32, i8 }>
 @const.struct = constant %const.struct.type { i32 -1, i8 undef }
 ; CHECK: @const.struct = constant %const.struct.type { i32 -1, i8 undef }
 @const.struct.packed = constant %const.struct.type.packed <{ i32 -1, i8 1 }>
 ; CHECK: @const.struct.packed = constant %const.struct.type.packed <{ i32 -1, i8 1 }>
 
 ; CHECK: @constant.array.i8  = constant [3 x i8] c"\00\01\00"