[IR] Add support for empty tokens

[majnemer]

Summary

When working with tokens, it is often the case that one has instructions
which consume a token and produce a new token. Currently, we have no
mechanism to represent an initial token state.

Instead, we can create a notional "empty token" by inventing a new
constant which captures the semantics we would like. This new constant
is called ConstantTokenNone and is written textually as "token none".

[rnk]

lgtm

Sweet, no need to even change the bitcode. :)

llvm/trunk/docs/LangRef.rst

**Floating point constants**
     hexadecimal notation (see below). The assembler requires the exact
     decimal value of a floating-point constant. For example, the
     assembler accepts 1.25 but rejects 1.3 because 1.3 is a repeating
     decimal in binary. Floating point constants must have a :ref:`floating
     point <t_floating>` type.
 **Null pointer constants**
     The identifier '``null``' is recognized as a null pointer constant
     and must be of :ref:`pointer type <t_pointer>`.
+**Token constants**
+    The identifier '``none``' is recognized as an empty token constant
+    and must be of :ref:`token type <t_token>`.
 
 The one non-intuitive notation for constants is the hexadecimal form of
 floating point constants. For example, the form
 '``double    0x432ff973cafa8000``' is equivalent to (but harder to read
 than) '``double 4.5e+15``'. The only time hexadecimal floating point
 constants are required (and the only time that they are generated by the
 disassembler) is when a floating point constant must be emitted but it
 cannot be represented as a decimal floating point number in a reasonable

llvm/trunk/include/llvm-c/Core.h

macro(Constant)                         \
       macro(ConstantDataSequential)         \
         macro(ConstantDataArray)            \
         macro(ConstantDataVector)           \
       macro(ConstantExpr)                   \
       macro(ConstantFP)                     \
       macro(ConstantInt)                    \
       macro(ConstantPointerNull)            \
       macro(ConstantStruct)                 \
+      macro(ConstantTokenNone)              \
       macro(ConstantVector)                 \
       macro(GlobalValue)                    \
         macro(GlobalAlias)                  \
         macro(GlobalObject)                 \
           macro(Function)                   \
           macro(GlobalVariable)             \
       macro(UndefValue)                     \
     macro(Instruction)                      \

llvm/trunk/include/llvm/IR/Constants.h

public:
 
   /// Methods for support type inquiry through isa, cast, and dyn_cast:
   ///
   static bool classof(const Value *V) {
     return V->getValueID() == ConstantDataVectorVal;
   }
 };
 
+//===----------------------------------------------------------------------===//
+/// ConstantTokenNone - a constant token which is empty
+///
+class ConstantTokenNone : public Constant {
+  void *operator new(size_t, unsigned) = delete;
+  ConstantTokenNone(const ConstantTokenNone &) = delete;
+
+  friend class Constant;
+  void destroyConstantImpl();
+  Value *handleOperandChangeImpl(Value *From, Value *To, Use *U);
+
+protected:
+  explicit ConstantTokenNone(LLVMContext &Context)
+      : Constant(Type::getTokenTy(Context), ConstantTokenNoneVal, nullptr, 0) {}
+  // allocate space for exactly zero operands
+  void *operator new(size_t s) { return User::operator new(s, 0); }
+
+public:
+  /// Return the ConstantTokenNone.
+  static ConstantTokenNone *get(LLVMContext &Context);
 
+  /// @brief Methods to support type inquiry through isa, cast, and dyn_cast.
+  static bool classof(const Value *V) {
+    return V->getValueID() == ConstantTokenNoneVal;
+  }
+};
 
 /// BlockAddress - The address of a basic block.
 ///
 class BlockAddress : public Constant {
   void *operator new(size_t, unsigned) = delete;
   void *operator new(size_t s) { return User::operator new(s, 2); }
   BlockAddress(Function *F, BasicBlock *BB);
 

llvm/trunk/include/llvm/IR/Value.def

 HANDLE_CONSTANT(ConstantDataArray)
 HANDLE_CONSTANT(ConstantDataVector)
 HANDLE_CONSTANT(ConstantInt)
 HANDLE_CONSTANT(ConstantFP)
 HANDLE_CONSTANT(ConstantArray)
 HANDLE_CONSTANT(ConstantStruct)
 HANDLE_CONSTANT(ConstantVector)
 HANDLE_CONSTANT(ConstantPointerNull)
+HANDLE_CONSTANT(ConstantTokenNone)
 
 HANDLE_METADATA_VALUE(MetadataAsValue)
 HANDLE_INLINE_ASM_VALUE(InlineAsm)
 
 HANDLE_INSTRUCTION(Instruction)
 // Enum values starting at InstructionVal are used for Instructions;
 // don't add new values here!
 
 HANDLE_CONSTANT_MARKER(ConstantFirstVal, Function)
-HANDLE_CONSTANT_MARKER(ConstantLastVal, ConstantPointerNull)
+HANDLE_CONSTANT_MARKER(ConstantLastVal, ConstantTokenNone)
 
 #undef HANDLE_GLOBAL_VALUE
 #undef HANDLE_CONSTANT
 #undef HANDLE_INSTRUCTION
 #undef HANDLE_METADATA_VALUE
 #undef HANDLE_INLINE_ASM_VALUE
 #undef HANDLE_VALUE
 #undef HANDLE_CONSTANT_MARKER

llvm/trunk/lib/AsmParser/LLLexer.cpp

#define KEYWORD(STR)                                                           \
   KEYWORD(external);
   KEYWORD(thread_local);
   KEYWORD(localdynamic);
   KEYWORD(initialexec);
   KEYWORD(localexec);
   KEYWORD(zeroinitializer);
   KEYWORD(undef);
   KEYWORD(null);
+  KEYWORD(none);
   KEYWORD(to);
   KEYWORD(caller);
   KEYWORD(tail);
   KEYWORD(musttail);
   KEYWORD(notail);
   KEYWORD(target);
   KEYWORD(triple);
   KEYWORD(unwind);

llvm/trunk/lib/AsmParser/LLParser.h

namespace llvm {
   class StructType;
 
   /// ValID - Represents a reference of a definition of some sort with no type.
   /// There are several cases where we have to parse the value but where the
   /// type can depend on later context.  This may either be a numeric reference
   /// or a symbolic (%var) reference.  This is just a discriminated union.
   struct ValID {
     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,    // 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_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.
     } Kind = t_LocalID;
 
     LLLexer::LocTy Loc;
     unsigned UIntVal;
     FunctionType *FTy = nullptr;
     std::string StrVal, StrVal2;
     APSInt APSIntVal;
     APFloat APFloatVal{0.0};

llvm/trunk/lib/AsmParser/LLParser.cpp

case lltok::kw_true:
     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_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) ||
         ParseToken(lltok::rbrace, "expected end of struct constant"))
       return true;
case ValID::t_EmptyArray:
     V = UndefValue::get(Ty);
     return false;
   case ValID::t_Zero:
     // FIXME: LabelTy should not be a first-class type.
     if (!Ty->isFirstClassType() || Ty->isLabelTy())
       return Error(ID.Loc, "invalid type for null constant");
     V = Constant::getNullValue(Ty);
     return false;
+  case ValID::t_None:
+    if (!Ty->isTokenTy())
+      return Error(ID.Loc, "invalid type for none constant");
+    V = Constant::getNullValue(Ty);
+    return false;
   case ValID::t_Constant:
     if (ID.ConstantVal->getType() != Ty)
       return Error(ID.Loc, "constant expression type mismatch");
 
     V = ID.ConstantVal;
     return false;
   case ValID::t_ConstantStruct:
   case ValID::t_PackedConstantStruct:

llvm/trunk/lib/AsmParser/LLToken.h

enum Kind {
     kw_dllimport, kw_dllexport, kw_common, kw_available_externally,
     kw_default, kw_hidden, kw_protected,
     kw_unnamed_addr,
     kw_externally_initialized,
     kw_extern_weak,
     kw_external, kw_thread_local,
     kw_localdynamic, kw_initialexec, kw_localexec,
     kw_zeroinitializer,
-    kw_undef, kw_null,
+    kw_undef, kw_null, kw_none,
     kw_to,
     kw_caller,
     kw_tail,
     kw_musttail,
     kw_notail,
     kw_target,
     kw_triple,
     kw_unwind,

llvm/trunk/lib/IR/AsmWriter.cpp

if (isa<ConstantVector>(CV) || isa<ConstantDataVector>(CV)) {
     return;
   }
 
   if (isa<ConstantPointerNull>(CV)) {
     Out << "null";
     return;
   }
 
+  if (isa<ConstantTokenNone>(CV)) {
+    Out << "none";
+    return;
+  }
+
   if (isa<UndefValue>(CV)) {
     Out << "undef";
     return;
   }
 
   if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(CV)) {
     Out << CE->getOpcodeName();
     WriteOptimizationInfo(Out, CE);

llvm/trunk/lib/IR/Constants.cpp

bool Constant::isNullValue() const {
   // 0 is null.
   if (const ConstantInt *CI = dyn_cast<ConstantInt>(this))
     return CI->isZero();
 
   // +0.0 is null.
   if (const ConstantFP *CFP = dyn_cast<ConstantFP>(this))
     return CFP->isZero() && !CFP->isNegative();
 
-  // constant zero is zero for aggregates and cpnull is null for pointers.
-  return isa<ConstantAggregateZero>(this) || isa<ConstantPointerNull>(this);
+  // constant zero is zero for aggregates, cpnull is null for pointers, none for
+  // tokens.
+  return isa<ConstantAggregateZero>(this) || isa<ConstantPointerNull>(this) ||
+         isa<ConstantTokenNone>(this);
 }
 
 bool Constant::isAllOnesValue() const {
   // Check for -1 integers
   if (const ConstantInt *CI = dyn_cast<ConstantInt>(this))
     return CI->isMinusOne();
 
   // Check for FP which are bitcasted from -1 integers
return ConstantFP::get(Ty->getContext(),
                            APFloat(APFloat::PPCDoubleDouble,
                                    APInt::getNullValue(128)));
   case Type::PointerTyID:
     return ConstantPointerNull::get(cast<PointerType>(Ty));
   case Type::StructTyID:
   case Type::ArrayTyID:
   case Type::VectorTyID:
     return ConstantAggregateZero::get(Ty);
+  case Type::TokenTyID:
+    return ConstantTokenNone::get(Ty->getContext());
   default:
     // Function, Label, or Opaque type?
     llvm_unreachable("Cannot create a null constant of that type!");
   }
 }
 
 Constant *Constant::getIntegerValue(Type *Ty, const APInt &V) {
   Type *ScalarTy = Ty->getScalarType();
Constant *ConstantVector::getSplat(unsigned NumElts, Constant *V) {
   if ((isa<ConstantFP>(V) || isa<ConstantInt>(V)) &&
       ConstantDataSequential::isElementTypeCompatible(V->getType()))
     return ConstantDataVector::getSplat(NumElts, V);
 
   SmallVector<Constant*, 32> Elts(NumElts, V);
   return get(Elts);
 }
 
+ConstantTokenNone *ConstantTokenNone::get(LLVMContext &Context) {
+  LLVMContextImpl *pImpl = Context.pImpl;
+  if (!pImpl->TheNoneToken)
+    pImpl->TheNoneToken = new ConstantTokenNone(Context);
+  return pImpl->TheNoneToken;
+}
+
+/// Remove the constant from the constant table.
+void ConstantTokenNone::destroyConstantImpl() {
+  llvm_unreachable("You can't ConstantTokenNone->destroyConstantImpl()!");
+}
 
 // Utility function for determining if a ConstantExpr is a CastOp or not. This
 // can't be inline because we don't want to #include Instruction.h into
 // Constant.h
 bool ConstantExpr::isCast() const {
   return Instruction::isCast(getOpcode());
 }
 

 Value *ConstantInt::handleOperandChangeImpl(Value *From, Value *To, Use *U) {
   llvm_unreachable("Unsupported class for handleOperandChange()!");
 }
 
 Value *ConstantFP::handleOperandChangeImpl(Value *From, Value *To, Use *U) {
   llvm_unreachable("Unsupported class for handleOperandChange()!");
 }
 
+Value *ConstantTokenNone::handleOperandChangeImpl(Value *From, Value *To,
+                                                  Use *U) {
+  llvm_unreachable("Unsupported class for handleOperandChange()!");
+}
+
 Value *UndefValue::handleOperandChangeImpl(Value *From, Value *To, Use *U) {
   llvm_unreachable("Unsupported class for handleOperandChange()!");
 }
 
 Value *ConstantPointerNull::handleOperandChangeImpl(Value *From, Value *To,
                                                     Use *U) {
   llvm_unreachable("Unsupported class for handleOperandChange()!");
 }

llvm/trunk/lib/IR/LLVMContextImpl.h

DenseMap<std::pair<const Function *, const BasicBlock *>, BlockAddress *>
     BlockAddresses;
   ConstantUniqueMap<ConstantExpr> ExprConstants;
 
   ConstantUniqueMap<InlineAsm> InlineAsms;
 
   ConstantInt *TheTrueVal;
   ConstantInt *TheFalseVal;
 
+  ConstantTokenNone *TheNoneToken;
+
   // Basic type instances.
   Type VoidTy, LabelTy, HalfTy, FloatTy, DoubleTy, MetadataTy, TokenTy;
   Type X86_FP80Ty, FP128Ty, PPC_FP128Ty, X86_MMXTy;
   IntegerType Int1Ty, Int8Ty, Int16Ty, Int32Ty, Int64Ty, Int128Ty;
 
   
   /// TypeAllocator - All dynamically allocated types are allocated from this.
   /// They live forever until the context is torn down.

llvm/trunk/lib/IR/LLVMContextImpl.cpp

 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/Module.h"
 #include <algorithm>
 using namespace llvm;
 
 LLVMContextImpl::LLVMContextImpl(LLVMContext &C)
   : TheTrueVal(nullptr), TheFalseVal(nullptr),
+    TheNoneToken(nullptr),
     VoidTy(C, Type::VoidTyID),
     LabelTy(C, Type::LabelTyID),
     HalfTy(C, Type::HalfTyID),
     FloatTy(C, Type::FloatTyID),
     DoubleTy(C, Type::DoubleTyID),
     MetadataTy(C, Type::MetadataTyID),
     TokenTy(C, Type::TokenTyID),
     X86_FP80Ty(C, Type::X86_FP80TyID),

llvm/trunk/lib/Transforms/IPO/MergeFunctions.cpp

if (const auto *SeqL = dyn_cast<ConstantDataSequential>(L)) {
     // compare the two raw data arrays, which might differ depending on the host
     // endianness. This isn't a problem though, because the endiness of a module
     // will affect the order of the constants, but this order is the same
     // for a given input module and host platform.
     return cmpMem(SeqL->getRawDataValues(), SeqR->getRawDataValues());
   }
 
   switch (L->getValueID()) {
-  case Value::UndefValueVal: return TypesRes;
+  case Value::UndefValueVal:
+  case Value::ConstantTokenNoneVal:
+    return TypesRes;
   case Value::ConstantIntVal: {
     const APInt &LInt = cast<ConstantInt>(L)->getValue();
     const APInt &RInt = cast<ConstantInt>(R)->getValue();
     return cmpAPInts(LInt, RInt);
   }
   case Value::ConstantFPVal: {
     const APFloat &LAPF = cast<ConstantFP>(L)->getValueAPF();
     const APFloat &RAPF = cast<ConstantFP>(R)->getValueAPF();

llvm/trunk/test/Assembler/token.ll

 ; RUN: llvm-as < %s | llvm-dis | FileCheck %s
 ; RUN: verify-uselistorder %s
 ; Basic smoke test for token type.
 
 ; CHECK: declare void @llvm.token.foobar(token)
 declare void @llvm.token.foobar(token)
+
+define void @f() {
+  call void @llvm.token.foobar(token none)
+  ret void
+}