[Constants] Add "stepvector" to represent the sequence 0,1,2,3... [IR support for SVE scalable vectors 4/4]

[paulwalker-arm]

Summary

[Constants] Add "stepvector" to represent the sequence 0,1,2,3...

The sequence "<i32 0, i32 1, i32 2, i32 3...>" is represented by
a ConstantVector containing an ArrayRef of all element values.
For scalable vectors, where the element count is unknown, such a
representation is impossible.

Instead the complex constant "stepvector" can be used wherever an
integer vector is expected. This allows the majority of vector
sequences required for vectorisation to be produced for all vector
types. Example Usage:

  getelementptr i8, i8* %ptr, <n x 4 x i32> stepvector
  getelementptr i8, i8* %ptr, <4 x i32> stepvector

NOTE: The non-scalable vector case will utilise ConstantVector.

[deadalnix]

include/llvm-c/Core.h

222

Same as D27103 . It is ok to add new enum values in there, but existing entries needs to keep the same value.

[rengolin]

Right, this is the one I'm still unsure about. What is the value of having a whole new construct to build <0, 1, 2, ..., n-1>?

I mean, if the new construct was generic enough to represent all possible sequences (reverse, step, multiplicative, etc), then it would be a change that is guaranteed to extend to all future usages. This one is so restricted that we'll have to change again in the near future to add more functionality.

Of course, we could use this construct to build the sequences in IR. Examples:

for (0..N-1) { a[i] = i; }

would increment i (as %index) like:

%a = PHI (getelementptr, %new.a)
%index = i32 0
...
; create a step vector <0, 1, ... N>
%step = constant <n x 4 x i32> stepvector
; create a splat vector with the start of the sequence
%curidx = insertelement <n x 4 x i32> undef, i32 %index, i32 0
%curidx.1 = shufflevector <n x 4 x i32> %a, <n x 4 x i32> undef, <n x 4 x i32> zeroinitializer
; add them together to get the current sequence
%ind = add <n x 4 x i32> %step, <n x 4 x i32> curidx.1
; store the sequence into a[i]
store <n x 4 x i32> ind, i32* %a
; update the index/address
%index = add i32 %index, i32 vscale
%new.a = toptr( add toint(i32* %a), mul(i32 vscale, i32 4) )

If we had an intrinsic for this, we'd be able to have any scalar evolution. Example:

@llvm.scalable_vector.step(i32 %start, i32 %a, i32 %b) ; as %start + (%a * x + %b)

The above loop would be:

%a = PHI (getelementptr, %new.a)
%index = i32 0
...
; create a step vector <0, 1, ... N>
%step = @llvm.scalable_vector.step.4.i32(i32 %index, i32 1, i32 1)
; store the sequence into a[i]
store <n x 4 x i32> ind, i32* %step
; update the index/address
%index = add i32 %index, i32 vscale
%new.a = toptr( add toint(i32* %a), mul(i32 vscale, i32 4) )

And this would work for all possible induction evolutions: positive, negative, multiples, etc.

Maybe going with ax+b is a bit too far, but certainly a constant step (plus/minus) and a starting point would be a great advantage to the notation, and it wouldn't (for now), change the IR to introduce a concept that is far too localised to be worth breaking compatibility.

Hope this makes sense...

cheers,
--renato

[rengolin]

After reading the SVE docs, I realised that what I requested here (start + step) is exactly what SVE has for the INDEX instruction. I don't think that having a constant step in this way makes sense, even for SVE.

I mean, once could write:

INDEX z0.s, #1, #2

as

%a = splat <n x 4 x i32>, %i32 2
%b = mul <n x 4 x i32> stepvector <n x 4 x i32>, %a

But what about when start != 1?

I retain the position that an intrinsic here would be much better with start/step and would minimise the changes to IR, at least for now.

cheers,
--renato

[aemerson]

In D27105#724054, @rengolin wrote:

After reading the SVE docs, I realised that what I requested here (start + step) is exactly what SVE has for the INDEX instruction. I don't think that having a constant step in this way makes sense, even for SVE.

I mean, once could write:

INDEX z0.s, #1, #2

as

%a = splat <n x 4 x i32>, %i32 2
%b = mul <n x 4 x i32> stepvector <n x 4 x i32>, %a

But what about when start != 1?

I retain the position that an intrinsic here would be much better with start/step and would minimise the changes to IR, at least for now.

cheers,
--renato

An arbitrary start value can be expressed by adding a splat of the start value to the step vector sequence. Composing that with the multiplication of the stepvector to achieve arbitrary steps values covers all use cases of seriesvector.

docs/LangRef.rst

**Array constants**
     prefix. For example: "``c"Hello World\0A\00"``".
 **Vector constants**
     Vector constants are represented with notation similar to vector
     type definitions (a comma separated list of elements, surrounded by
     less-than/greater-than's (``<>``)). For example:
     "``< i32 42, i32 11, i32 74, i32 100 >``". Vector constants
     must have :ref:`vector type <t_vector>`, and the number and types of
     elements must match those specified by the type.
+**Scalable vector constants (unit step vector)**
+    Scalable vector constants cannot be represented by a list of elements
+    because the number of elements required is unknown.  To mitigate this
+    the string '``stepvector``' can be used to represent the constant vector
+    "``<0, 1, 2, 3, 4...``" wherever an :ref:`integer <t_integer>`
+    :ref:`vector <t_vector>` is expected.
 **Zero initialization**
     The string '``zeroinitializer``' can be used to zero initialize a
     value to zero of *any* type, including scalar and
     :ref:`aggregate <t_aggregate>` types. This is often used to avoid
     having to print large zero initializers (e.g. for large arrays) and
     is always exactly equivalent to using explicit zero initializers.
 **Metadata node**
     A metadata node is a constant tuple without types. For example:

include/llvm-c/Core.h

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

include/llvm/Bitcode/LLVMBitCodes.h

enum ConstantsCodes {
   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
+  CST_CODE_STEPVEC = 26,         // STEPVEC
 };
 
 /// 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

 template <>
 struct OperandTraits<ConstantExpr> :
   public VariadicOperandTraits<ConstantExpr, 1> {
 };
 
 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ConstantExpr, Constant)
 
 //===----------------------------------------------------------------------===//
+/// A constant vector representing the numeric sequence "0, 1, 2, 3, 4...".
+///
+class StepVectorValue final : public ConstantData {
+  StepVectorValue(const StepVectorValue &) = delete;
+
+  friend class Constant;
+  void destroyConstantImpl();
+
+  explicit StepVectorValue(Type *T) : ConstantData(T, StepVectorValueVal) {}
+
+public:
+  /// Static factory methods - Return a 'stepvector' object of the specified
+  /// type or a ConstantVector if the result's vector length is known.
+  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() == StepVectorValueVal;
+  }
+};
+
+//===----------------------------------------------------------------------===//
 /// 'undef' values are things that do not have specified contents.
 /// These are used for a variety of purposes, including global variable
 /// initializers and operands to instructions.  'undef' values can occur with
 /// any first-class type.
 ///
 /// Undef values aren't exactly constants; if they have multiple uses, they
 /// can appear to have different bit patterns at each use. See
 /// LangRef.html#undefvalues for details.

include/llvm/IR/Value.def

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

lib/AsmParser/LLLexer.cpp

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

lib/AsmParser/LLParser.h

enum {
       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_VScale                         // No value.
+      t_VScale,                        // No value.
+      t_StepVector                     // 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.ConstantVal = ConstantInt::getTrue(Context);
     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_stepvector: ID.Kind = ValID::t_StepVector; 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();
if (V->getType() != Ty)
                    getTypeString(Ty) + "'");
 
     return false;
   case ValID::t_Null:
     if (!Ty->isPointerTy())
       return Error(ID.Loc, "null must be a pointer type");
     V = ConstantPointerNull::get(cast<PointerType>(Ty));
     return false;
+  case ValID::t_StepVector:
+    if (!Ty->isVectorTy() || !Ty->getVectorElementType()->isIntegerTy())
+      return Error(ID.Loc, "stepvector must be an integer vector type");
+    V = StepVectorValue::get(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())

lib/AsmParser/LLToken.h

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

lib/Bitcode/Reader/BitcodeReader.cpp

while (true) {
 
     // Read a record.
     Record.clear();
     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_STEPVEC:   // STEPVEC
+      V = StepVectorValue::get(CurTy);
+      break;
     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())

lib/Bitcode/Writer/BitcodeWriter.cpp

if (const InlineAsm *IA = dyn_cast<InlineAsm>(V)) {
       Record.clear();
       continue;
     }
     const Constant *C = cast<Constant>(V);
     unsigned Code = -1U;
     unsigned AbbrevToUse = 0;
     if (C->isNullValue()) {
       Code = bitc::CST_CODE_NULL;
+    } else if (isa<StepVectorValue>(C)) {
+      Code = bitc::CST_CODE_STEPVEC;
     } 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);

lib/IR/AsmWriter.cpp

if (isa<ConstantPointerNull>(CV)) {
     return;
   }
 
   if (isa<ConstantTokenNone>(CV)) {
     Out << "none";
     return;
   }
 
+  if (isa<StepVectorValue>(CV)) {
+    Out << "stepvector";
+    return;
+  }
+
   if (isa<UndefValue>(CV)) {
     Out << "undef";
     return;
   }
 
   if (isa<VScaleValue>(CV)) {
     Out << "vscale";
     return;

lib/IR/Constants.cpp

unsigned ConstantAggregateZero::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();
 }
 
 //===----------------------------------------------------------------------===//
+//                      StepVectorValue Implementation
+//===----------------------------------------------------------------------===//
+
+Constant *StepVectorValue::get(Type *Ty) {
+  assert(Ty->isVectorTy() && Ty->getVectorElementType()->isIntegerTy() &&
+         "StepVector must be an integer vector type!");
+
+  if (!Ty->getVectorIsScalable()) {
+    // Always return a constant vector when the vector length is known.
+    Type* EltTy = Ty->getVectorElementType();
+
+    SmallVector<Constant *, 8> Indices;
+    for (int i = 0, e = Ty->getVectorNumElements(); i < e; ++i)
+      Indices.push_back(ConstantInt::get(EltTy, i));
+
+    return ConstantVector::get(Indices);
+  }
+
+  std::unique_ptr<StepVectorValue> &Entry =
+      Ty->getContext().pImpl->SVVConstants[Ty];
+  if (!Entry)
+    Entry.reset(new StepVectorValue(Ty));
+
+  return Entry.get();
+}
+
+/// Remove the constant from the constant table.
+void StepVectorValue::destroyConstantImpl() {
+  // Free the constant and any dangling references to it.
+  getContext().pImpl->SVVConstants.erase(getType());
+}
+
+//===----------------------------------------------------------------------===//
 //                         UndefValue Implementation
 //===----------------------------------------------------------------------===//
 
 UndefValue *UndefValue::get(Type *Ty) {
   std::unique_ptr<UndefValue> &Entry = Ty->getContext().pImpl->UVConstants[Ty];
   if (!Entry)
     Entry.reset(new UndefValue(Ty));
 

lib/IR/LLVMContextImpl.h

#include "llvm/IR/Metadata.def"
   typedef ConstantUniqueMap<ConstantStruct> StructConstantsTy;
   StructConstantsTy StructConstants;
   
   typedef ConstantUniqueMap<ConstantVector> VectorConstantsTy;
   VectorConstantsTy VectorConstants;
 
   DenseMap<PointerType *, std::unique_ptr<ConstantPointerNull>> CPNConstants;
 
+  DenseMap<Type *, std::unique_ptr<StepVectorValue>> SVVConstants;
   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;

lib/IR/LLVMContextImpl.cpp

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

test/Bitcode/compatibility.ll

 @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
 @const.vscale = constant i32 vscale
 ; CHECK: @const.vscale = constant i32 vscale
[e-mail] = constant <n x 4 x i32> stepvector
+; CHECK: @const.stepvector = constant <n x 4 x i32> stepvector
 %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"

test/Transforms/ConstProp/constant-expr.ll

 @select = internal constant
           i32 select (i1 icmp ult (i32 ptrtoint (i8* @X to i32),
                                    i32 ptrtoint (i8* @Y to i32)),
             i32 select (i1 icmp ult (i32 ptrtoint (i8* @X to i32),
                                      i32 ptrtoint (i8* @Y to i32)),
                i32 10, i32 20),
             i32 30)
 ; CHECK: select = internal constant i32 select {{.*}} i32 10, i32 30
+
+@stepvector = constant <4 x i32> stepvector
+; CHECK: @stepvector = constant <4 x i32> <i32 0, i32 1, i32 2, i32 3>