[WebAssembly] Implement ref.null

[wingo]

Summary

This patch adds a new "heap type" operand kind to the WebAssembly MC
layer, used by ref.null. Currently the possible values are "extern" and
"func"; when typed function references come, though, this operand may be
a type index.

Note that the "heap type" production is still known as "refedtype" in
the draft proposal; changing its name in the spec is
ongoing (https://github.com/WebAssembly/reference-types/issues/123).

The register form of ref.null is still untested.

[wingo]

This is baby's first LLVM patch; beyond the review itself, any meta-tips and feedback are very welcome!

[tlively]

Nice! This looks good besides that one question. Also, for the patch description, it seems slightly misleading to say that "the register form of ref.null is still unimplemented"; IIUC, the register form is implemented since the I tablegen multiclass creates both forms, but it's simply not used for anything right now.

Since this is your first LLVM patch, I assume you don't have commit access to LLVM yet? If so, I can land this for you. After a couple more patches, you should request commit access.

llvm/lib/Target/WebAssembly/AsmParser/WebAssemblyAsmParser.cpp

584

Is this last line necessary? It looks like the other cases don't have similar lines.

[sbc100]

lgtm. In a project that primarily deals with C/C++ code I find "heap time" a little confusing because it makes me think of the malloc heap used by C/C++. Why not "managed" or something like that to avoid ambiguity? I guess that is being discussed in the spec and we should probably just follow their lead.

[tlively]

In D90608#2369305, @sbc100 wrote:

lgtm. In a project that primarily deals with C/C++ code I find "heap time" a little confusing because it makes me think of the malloc heap used by C/C++. Why not "managed" or something like that to avoid ambiguity? I guess that is being discussed in the spec and we should probably just follow their lead.

I do think that matching the upstream spec "heap type" terminology is important, even if it's a little confusing in a C++ context.

[sbc100]

In D90608#2369338, @tlively wrote:

In D90608#2369305, @sbc100 wrote:

lgtm. In a project that primarily deals with C/C++ code I find "heap time" a little confusing because it makes me think of the malloc heap used by C/C++. Why not "managed" or something like that to avoid ambiguity? I guess that is being discussed in the spec and we should probably just follow their lead.

I do think that matching the upstream spec "heap type" terminology is important, even if it's a little confusing in a C++ context.

Do you think that upstream term "heap type" is reasonable, given the pre-existing alternate meaning of heap that already exists in the unmanaged world?

[tlively]

In D90608#2369392, @sbc100 wrote:

In D90608#2369338, @tlively wrote:

In D90608#2369305, @sbc100 wrote:

lgtm. In a project that primarily deals with C/C++ code I find "heap time" a little confusing because it makes me think of the malloc heap used by C/C++. Why not "managed" or something like that to avoid ambiguity? I guess that is being discussed in the spec and we should probably just follow their lead.

I do think that matching the upstream spec "heap type" terminology is important, even if it's a little confusing in a C++ context.

Do you think that upstream term "heap type" is reasonable, given the pre-existing alternate meaning of heap that already exists in the unmanaged world?

I've gotten used to that name, so I don't personally have any problems with it. I definitely see the potential for confusion, though. I hope it won't be too bad in practice because it will usually be clear from context whether "heap type" means a WebAssembly heap type or if it means something to do with the C++ heap.

[wingo]

Address feedback.

[wingo]

Thanks for review, Thomas and Sam! Addressed feedback. Thanks also for the tips regarding commit access; for the time being if it looks good to you, would you mind landing this one, @tlively ? Cheers!

[tlively]

Excellent, thanks! I'll land this.

llvm/lib/Target/WebAssembly/AsmParser/WebAssemblyAsmParser.cpp

if (IsLoadStore || IsAtomic) {
         Operands.push_back(std::make_unique<WebAssemblyOperand>(
             WebAssemblyOperand::Integer, Tok.getLoc(), Tok.getEndLoc(),
             WebAssemblyOperand::IntOp{-1}));
       }
     }
     return false;
   }
 
+  WebAssembly::HeapType parseHeapType(StringRef Id) {
+    return StringSwitch<WebAssembly::HeapType>(Id)
+        .Case("extern", WebAssembly::HeapType::Externref)
+        .Case("func", WebAssembly::HeapType::Funcref)
+        .Default(WebAssembly::HeapType::Invalid);
+  }
+
   void addBlockTypeOperand(OperandVector &Operands, SMLoc NameLoc,
                            WebAssembly::BlockType BT) {
     Operands.push_back(std::make_unique<WebAssemblyOperand>(
         WebAssemblyOperand::Integer, NameLoc, NameLoc,
         WebAssemblyOperand::IntOp{static_cast<int64_t>(BT)}));
   }
 
   bool ParseInstruction(ParseInstructionInfo & /*Info*/, StringRef Name,
bool ParseInstruction(ParseInstructionInfo & /*Info*/, StringRef Name,
     Operands.push_back(std::make_unique<WebAssemblyOperand>(
         WebAssemblyOperand::Token, NameLoc, SMLoc::getFromPointer(Name.end()),
         WebAssemblyOperand::TokOp{Name}));
 
     // If this instruction is part of a control flow structure, ensure
     // proper nesting.
     bool ExpectBlockType = false;
     bool ExpectFuncType = false;
+    bool ExpectHeapType = false;
     if (Name == "block") {
       push(Block);
       ExpectBlockType = true;
     } else if (Name == "loop") {
       push(Loop);
       ExpectBlockType = true;
     } else if (Name == "try") {
       push(Try);
if (Name == "block") {
         return true;
     } else if (Name == "end_function") {
       ensureLocals(getStreamer());
       CurrentState = EndFunction;
       if (pop(Name, Function) || ensureEmptyNestingStack())
         return true;
     } else if (Name == "call_indirect" || Name == "return_call_indirect") {
       ExpectFuncType = true;
+    } else if (Name == "ref.null") {
+      ExpectHeapType = true;
     }
 
     if (ExpectFuncType || (ExpectBlockType && Lexer.is(AsmToken::LParen))) {
       // This has a special TYPEINDEX operand which in text we
       // represent as a signature, such that we can re-build this signature,
       // attach it to an anonymous symbol, which is what WasmObjectWriter
       // expects to be able to recreate the actual unique-ified type indices.
       auto Loc = Parser.getTok();
while (Lexer.isNot(AsmToken::EndOfStatement)) {
         auto &Id = Lexer.getTok();
         if (ExpectBlockType) {
           // Assume this identifier is a block_type.
           auto BT = parseBlockType(Id.getString());
           if (BT == WebAssembly::BlockType::Invalid)
             return error("Unknown block type: ", Id);
           addBlockTypeOperand(Operands, NameLoc, BT);
           Parser.Lex();
+        } else if (ExpectHeapType) {
+          auto HeapType = parseHeapType(Id.getString());
+          if (HeapType == WebAssembly::HeapType::Invalid) {
+            return error("Expected a heap type: ", Id);
+          }
+          Operands.push_back(std::make_unique<WebAssemblyOperand>(
+              WebAssemblyOperand::Integer, Id.getLoc(), Id.getEndLoc(),
+              WebAssemblyOperand::IntOp{static_cast<int64_t>(HeapType)}));
+          Parser.Lex();
         } else {
           // Assume this identifier is a label.
           const MCExpr *Val;
           SMLoc End;
           if (Parser.parseExpression(Val, End))
             return error("Cannot parse symbol: ", Lexer.getTok());
           Operands.push_back(std::make_unique<WebAssemblyOperand>(
               WebAssemblyOperand::Symbol, Id.getLoc(), Id.getEndLoc(),
               WebAssemblyOperand::SymOp{Val}));

llvm/lib/Target/WebAssembly/Disassembler/WebAssemblyDisassembler.cpp

case WebAssembly::OPERAND_SIGNATURE: {
         auto *WasmSym = cast<MCSymbolWasm>(Sym);
         WasmSym->setType(wasm::WASM_SYMBOL_TYPE_FUNCTION);
         const MCExpr *Expr = MCSymbolRefExpr::create(
             WasmSym, MCSymbolRefExpr::VK_WASM_TYPEINDEX, getContext());
         MI.addOperand(MCOperand::createExpr(Expr));
       }
       break;
     }
+    // heap_type operands, for e.g. ref.null:
+    case WebAssembly::OPERAND_HEAPTYPE: {
+      int64_t Val;
+      uint64_t PrevSize = Size;
+      if (!nextLEB(Val, Bytes, Size, true))
+        return MCDisassembler::Fail;
+      if (Val < 0 && Size == PrevSize + 1) {
+        // The HeapType encoding is like BlockType, in that encodings that
+        // decode as negative values indicate ValTypes.  In practice we expect
+        // either wasm::ValType::EXTERNREF or wasm::ValType::FUNCREF here.
+        //
+        // The positive SLEB values are reserved for future expansion and are
+        // expected to be type indices in the typed function references
+        // proposal, and should disassemble as MCSymbolRefExpr as in BlockType
+        // above.
+        MI.addOperand(MCOperand::createImm(Val & 0x7f));
+      } else {
+        MI.addOperand(
+            MCOperand::createImm(int64_t(WebAssembly::HeapType::Invalid)));
+      }
+      break;
+    }
     // FP operands.
     case WebAssembly::OPERAND_F32IMM: {
       if (!parseImmediate<float>(MI, Size, Bytes))
         return MCDisassembler::Fail;
       break;
     }
     case WebAssembly::OPERAND_F64IMM: {
       if (!parseImmediate<double>(MI, Size, Bytes))

llvm/lib/Target/WebAssembly/MCTargetDesc/WebAssemblyInstPrinter.h

public:
   // Used by tblegen code.
   void printOperand(const MCInst *MI, unsigned OpNo, raw_ostream &O,
                     bool IsVariadicDef = false);
   void printBrList(const MCInst *MI, unsigned OpNo, raw_ostream &O);
   void printWebAssemblyP2AlignOperand(const MCInst *MI, unsigned OpNo,
                                       raw_ostream &O);
   void printWebAssemblySignatureOperand(const MCInst *MI, unsigned OpNo,
                                         raw_ostream &O);
+  void printWebAssemblyHeapTypeOperand(const MCInst *MI, unsigned OpNo,
+                                       raw_ostream &O);
 
   // Autogenerated by tblgen.
   void printInstruction(const MCInst *MI, uint64_t Address, raw_ostream &O);
   static const char *getRegisterName(unsigned RegNo);
 };
 
 namespace WebAssembly {
 

llvm/lib/Target/WebAssembly/MCTargetDesc/WebAssemblyInstPrinter.cpp

if (Sym->getSignature()) {
       O << WebAssembly::signatureToString(Sym->getSignature());
     } else {
       // Disassembler does not currently produce a signature
       O << "unknown_type";
     }
   }
 }
 
+void WebAssemblyInstPrinter::printWebAssemblyHeapTypeOperand(const MCInst *MI,
+                                                             unsigned OpNo,
+                                                             raw_ostream &O) {
+  const MCOperand &Op = MI->getOperand(OpNo);
+  if (Op.isImm()) {
+    switch (Op.getImm()) {
+    case long(wasm::ValType::EXTERNREF):
+      O << "extern";
+      break;
+    case long(wasm::ValType::FUNCREF):
+      O << "func";
+      break;
+    default:
+      O << "unsupported_heap_type_value";
+      break;
+    }
+  } else {
+    // Typed function references and other subtypes of funcref and externref
+    // currently unimplemented.
+    O << "unsupported_heap_type_operand";
+  }
+}
+
 // We have various enums representing a subset of these types, use this
 // function to convert any of them to text.
 const char *WebAssembly::anyTypeToString(unsigned Ty) {
   switch (Ty) {
   case wasm::WASM_TYPE_I32:
     return "i32";
   case wasm::WASM_TYPE_I64:
     return "i64";

llvm/lib/Target/WebAssembly/MCTargetDesc/WebAssemblyMCCodeEmitter.cpp

if (MO.isReg()) {
           break;
         case WebAssembly::OPERAND_OFFSET32:
           encodeULEB128(uint32_t(MO.getImm()), OS);
           break;
         case WebAssembly::OPERAND_I64IMM:
           encodeSLEB128(int64_t(MO.getImm()), OS);
           break;
         case WebAssembly::OPERAND_SIGNATURE:
+        case WebAssembly::OPERAND_HEAPTYPE:
           OS << uint8_t(MO.getImm());
           break;
         case WebAssembly::OPERAND_VEC_I8IMM:
           support::endian::write<uint8_t>(OS, MO.getImm(), support::little);
           break;
         case WebAssembly::OPERAND_VEC_I16IMM:
           support::endian::write<uint16_t>(OS, MO.getImm(), support::little);
           break;

llvm/lib/Target/WebAssembly/MCTargetDesc/WebAssemblyMCTargetDesc.h

enum OperandType {
   /// type signature immediate for call_indirect.
   OPERAND_TYPEINDEX,
   /// Event index.
   OPERAND_EVENT,
   /// A list of branch targets for br_list.
   OPERAND_BRLIST,
   /// 32-bit unsigned table number.
   OPERAND_TABLE,
+  /// heap type immediate for ref.null.
+  OPERAND_HEAPTYPE,
 };
 } // end namespace WebAssembly
 
 namespace WebAssemblyII {
 
 /// Target Operand Flag enum.
 enum TOF {
   MO_NO_FLAG = 0,
enum class BlockType : unsigned {
   // Multivalue blocks (and other non-void blocks) are only emitted when the
   // blocks will never be exited and are at the ends of functions (see
   // WebAssemblyCFGStackify::fixEndsAtEndOfFunction). They also are never made
   // to pop values off the stack, so the exact multivalue signature can always
   // be inferred from the return type of the parent function in MCInstLower.
   Multivalue = 0xffff,
 };
 
+/// Used as immediate MachineOperands for heap types, e.g. for ref.null.
+enum class HeapType : unsigned {
+  Invalid = 0x00,
+  Externref = unsigned(wasm::ValType::EXTERNREF),
+  Funcref = unsigned(wasm::ValType::FUNCREF),
+};
+
 /// Instruction opcodes emitted via means other than CodeGen.
 static const unsigned Nop = 0x01;
 static const unsigned End = 0x0b;
 
 wasm::ValType toValType(const MVT &Ty);
 
 /// Return the default p2align value for a load or store with the given opcode.
 inline unsigned GetDefaultP2AlignAny(unsigned Opc) {

llvm/lib/Target/WebAssembly/WebAssemblyInstrInfo.td

 
 } // OperandType = "OPERAND_P2ALIGN"
 
 let OperandType = "OPERAND_SIGNATURE" in
 def Signature : Operand<i32> {
   let PrintMethod = "printWebAssemblySignatureOperand";
 }
 
+let OperandType = "OPERAND_HEAPTYPE" in
+def HeapType : Operand<i32> {
+  let PrintMethod = "printWebAssemblyHeapTypeOperand";
+}
+
 let OperandType = "OPERAND_TYPEINDEX" in
 def TypeIndex : Operand<i32>;
 
 } // OperandNamespace = "WebAssembly"
 
 //===----------------------------------------------------------------------===//
 // WebAssembly Register to Stack instruction mapping
 //===----------------------------------------------------------------------===//

llvm/lib/Target/WebAssembly/WebAssemblyInstrRef.td

defm SELECT_EXNREF : I<(outs EXNREF:$dst),
                          (select I32:$cond, EXNREF:$lhs, EXNREF:$rhs))],
                        "exnref.select\t$dst, $lhs, $rhs, $cond",
                        "exnref.select", 0x1b>;
 
 def : Pat<(select (i32 (setne I32:$cond, 0)), EXNREF:$lhs, EXNREF:$rhs),
           (SELECT_EXNREF EXNREF:$lhs, EXNREF:$rhs, I32:$cond)>;
 def : Pat<(select (i32 (seteq I32:$cond, 0)), EXNREF:$lhs, EXNREF:$rhs),
           (SELECT_EXNREF EXNREF:$rhs, EXNREF:$lhs, I32:$cond)>;
+
+multiclass REF<WebAssemblyRegClass rt> {
+  defm REF_NULL_#rt : I<(outs rt:$res), (ins HeapType:$heaptype),
+                        (outs), (ins HeapType:$heaptype),
+                        [],
+                        "ref.null\t$res, $heaptype",
+                        "ref.null\t$heaptype",
+                        0xd0>;
+}
+
+defm "" : REF<FUNCREF>, Requires<[HasReferenceTypes]>;
+defm "" : REF<EXTERNREF>, Requires<[HasReferenceTypes]>;

llvm/lib/Target/WebAssembly/WebAssemblyMCInstLower.cpp

case MachineOperand::MO_Immediate: {
           assert(BT != WebAssembly::BlockType::Invalid);
           if (BT == WebAssembly::BlockType::Multivalue) {
             SmallVector<wasm::ValType, 1> Returns;
             getFunctionReturns(MI, Returns);
             MCOp = lowerTypeIndexOperand(std::move(Returns),
                                          SmallVector<wasm::ValType, 4>());
             break;
           }
+        } else if (Info.OperandType == WebAssembly::OPERAND_HEAPTYPE) {
+          auto HT = static_cast<WebAssembly::HeapType>(MO.getImm());
+          assert(HT != WebAssembly::HeapType::Invalid);
+          // With typed function references, this will need a case for type
+          // index operands.  Otherwise, fall through.
         }
       }
       MCOp = MCOperand::createImm(MO.getImm());
       break;
     }
     case MachineOperand::MO_FPImmediate: {
       // TODO: MC converts all floating point immediate operands to double.
       // This is fine for numeric values, but may cause NaNs to change bits.

llvm/test/MC/WebAssembly/reference-types.s

+# RUN: llvm-mc -show-encoding -triple=wasm32-unknown-unknown -mattr=+reference-types < %s | FileCheck %s
+# RUN: llvm-mc -show-encoding -triple=wasm64-unknown-unknown -mattr=+reference-types < %s | FileCheck %s
+
+#      CHECK: ref_null_externref:
+# CHECK-NEXT:         .functype ref_null_externref () -> (externref)
+#      CHECK: ref.null extern # encoding: [0xd0,0x6f]
+# CHECK-NEXT: end_function
+ref_null_externref:
+  .functype ref_null_externref () -> (externref)
+  ref.null extern
+  end_function
+
+#      CHECK: ref_null_funcref:
+# CHECK-NEXT:         .functype ref_null_funcref () -> (funcref)
+#      CHECK: ref.null func # encoding: [0xd0,0x70]
+# CHECK-NEXT: end_function
+ref_null_funcref:
+  .functype ref_null_funcref () -> (funcref)
+  ref.null func
+  end_function