[WebAssembly] call_indirect causes indirect function table import

[wingo]

Summary

For wasm-ld table linking work to proceed, object files should indicate
if they use an indirect function table. In the future this will be done
by the usual symbols and relocations mechanism, but until that support
lands in the linker, the presence of an __indirect_function_table in
the object file's import section shows that the object file needs an
indirect function table.

Prior to https://reviews.llvm.org/D91637, this condition was met by all
object files residualizing an __indirect_function_table import.

Since https://reviews.llvm.org/D91637, the intention has been that only
those object files needing an indirect function table would have the
__indirect_function_table import. However, we missed the case of
object files which use the table via call_indirect but which
themselves do not declare any indirect functions.

This changeset makes it so that when we lower a call to call_indirect,
that we ensure that a __indirect_function_table symbol is present and
that it will be propagated to the linker.

A followup patch will revise this mechanism to make an explicit link
between call_indirect and its associated indirect function table; see
https://reviews.llvm.org/D90948.

[wingo]

Fix comments

[sbc100]

lgtm.

I'm not sure how to address the duplication of got and the associated FIXME. Adding some others to the review list who might know a way to deal with that without duplication.

[aheejin]

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

167

I'm not sure if there's an easy way to factor out so all three places can use it, but at least can't we use WebAssemblyUtilities.cpp's getOrCreateFunctionTableSymbol here and not define it again? Can't we do `#include "WebAssemblyUtilities.h" and use its function?

[wingo]

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

167

Sadly we can't directly re-use it here, for reasons I don't fully understand. If you #include the WebAssemblyUtilities.h file, it compiles fine but llvm-mc fails to link. It would seem that one might need to factor WebAssemblyUtilities to a separate cmake component.

[aheejin]

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

167

Does adding WebAssemblyCodeGen under LINK_COMPONENTS in llvm/lib/Target/WebAssembly/AsmParser/CMakeLists.txt work?

[wingo]

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

167

I'll give it a try, but note fwiw that other Target/$foo/AsmParser/CMakeLists.txt don't include the codegen components

[wingo]

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

167

OK so this works :) It will lead to more work for the linker though. @aheejin I can factor out a Target/WebAssembly/Utils/ dir and library component, as e.g. AArch64 and RISCV have, or I can just add WebAssemblyCodeGen to the LINK_COMPONENTS. Do you have a preference?

[aheejin]

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

167

Making Utils directory sounds good to me. As you said, there seems to be already four targets which does that: AArch64, AMDGPU, ARM, and RISCV.

Maybe it would be good to land this as is and do the Utils refactoring as a followup CL.

[wingo]

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

167

Really sorry for the noise here but given that the existing WebAssemblyUtilities pulls in all of CodeGen anyway via use of MachineInstr in the other utility routines, it would appear to be just useless noodling to put it in Utils. I will just make AsmParser use WebAssemblyCodeGen and call it a day. Further feedback still welcome of course!

[wingo]

AsmParser uses WebAssemblyUtilities, links to WebAssemblyCodeGen

[sbc100]

llvm/lib/Target/WebAssembly/AsmParser/CMakeLists.txt

7 ↗

(On Diff #310513)

It could be that MC may be designed to specifically not include CodeGen stuff? Separation of concerns and all that.

Perhaps this oversteps some boundary? I'm not familiar enough the design goals of llvm WRT compartmentalization to know if this is some kind of violation. Does anyone know if this is problem?

[aheejin]

llvm/lib/Target/WebAssembly/AsmParser/CMakeLists.txt

7 ↗

(On Diff #310513)

I don't know; I just discovered the linking works that way, but I'm not sure whether it violates some LLVM convention or something. Other AsmParser directories don't seem to make use of their corresponding CodeGen libraries though.

[wingo]

llvm/lib/Target/WebAssembly/AsmParser/CMakeLists.txt

7 ↗

(On Diff #310513)

I am both heartened and disheartened to see that you all share my ignorance in this regard :) I am happy to do whatever you all think best. The possibilities I see are:

1. method on MCContext (discussion: https://reviews.llvm.org/D90948?id=305170#inline-851687)
2. WebAssemblyUtilities, and link to codegen
3. just copy-paste the functionality
4. make a new utils library including just this one function.

Let me know your preference please :)

[sbc100]

Lets just go with duplicating the function for now (along with a TODO to followup).

Other than that this lgtm

[aardappel]

llvm/lib/Target/WebAssembly/AsmParser/CMakeLists.txt

7 ↗

(On Diff #310513)

Yes, this doesn't seem like a good idea. The MC code is used by quite a few utilities and is intended to be separate from CodeGen. We've had to jump thru hoops a few times before to keep the two separate. I believe there is already a header that contains shared utility functions (either in the WebAssemblyInfo target, or a header like WebAssemblyMCTargetDesc.h)

[wingo]

Rebase

[wingo]

Copy/paste GetOrCreateFunctionTableSymbol into WebAssemblyAsmParser

[wingo]

Landing, given @sbc100's lgtm-with-nit. Thanks all for your patience and happy new year :)

[tlively]

This commit appears to be the source of ongoing object file ABI breakage that is causing older versions of lld that do not know about table index relocations to fail to link objects produced by versions of LLVM after this change. This can be fixed by only adding the __indirect_function_table import when the reference-types feature is enabled.

cc @sbc100

[sbc100]

@wingo can we revert this for the llvm 12 branch which is about to occur (tomorrow I think)? And then we can look at moving forward after the branch?

llvm/lib/MC/WasmObjectWriter.cpp

 // Emit the Wasm header.
 void WasmObjectWriter::writeHeader(const MCAssembler &Asm) {
   W->OS.write(wasm::WasmMagic, sizeof(wasm::WasmMagic));
   W->write<uint32_t>(wasm::WasmVersion);
 }
 
 void WasmObjectWriter::executePostLayoutBinding(MCAssembler &Asm,
                                                 const MCAsmLayout &Layout) {
+  // As a stopgap measure until call_indirect instructions start explicitly
+  // referencing the indirect function table via TABLE_NUMBER relocs, ensure
+  // that the indirect function table import makes it to the output if anything
+  // in the compilation unit has caused it to be present.
+  if (auto *Sym = Asm.getContext().lookupSymbol("__indirect_function_table"))
+    Asm.registerSymbol(*Sym);
+
   // Build a map of sections to the function that defines them, for use
   // in recordRelocation.
   for (const MCSymbol &S : Asm.symbols()) {
     const auto &WS = static_cast<const MCSymbolWasm &>(S);
     if (WS.isDefined() && WS.isFunction() && !WS.isVariable()) {
       const auto &Sec = static_cast<const MCSectionWasm &>(S.getSection());
       auto Pair = SectionFunctions.insert(std::make_pair(&Sec, &S));
       if (!Pair.second)

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

case Symbol:
       break;
     case BrList:
       OS << "BrList:" << BrL.List.size();
       break;
     }
   }
 };
 
+static MCSymbolWasm *GetOrCreateFunctionTableSymbol(MCContext &Ctx,
+                                                    const StringRef &Name) {
+  // FIXME: Duplicates functionality from
+  // MC/WasmObjectWriter::recordRelocation, as well as WebAssemblyCodegen's
+  // WebAssembly:getOrCreateFunctionTableSymbol.
+  MCSymbolWasm *Sym = cast_or_null<MCSymbolWasm>(Ctx.lookupSymbol(Name));
+  if (Sym) {
+    if (!Sym->isFunctionTable())
+      Ctx.reportError(SMLoc(), "symbol is not a wasm funcref table");
+  } else {
+    Sym = cast<MCSymbolWasm>(Ctx.getOrCreateSymbol(Name));
+    Sym->setFunctionTable();
+    // The default function table is synthesized by the linker.
+    Sym->setUndefined();
+  }
+  return Sym;
+}
+
 class WebAssemblyAsmParser final : public MCTargetAsmParser {
   MCAsmParser &Parser;
   MCAsmLexer &Lexer;
 
   // Much like WebAssemblyAsmPrinter in the backend, we have to own these.
   std::vector<std::unique_ptr<wasm::WasmSignature>> Signatures;
   std::vector<std::unique_ptr<std::string>> Names;
 
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;
+      // Ensure that the object file has a __indirect_function_table import, as
+      // we call_indirect against it.
+      auto &Ctx = getStreamer().getContext();
+      MCSymbolWasm *Sym =
+          GetOrCreateFunctionTableSymbol(Ctx, "__indirect_function_table");
+      // Until call_indirect emits TABLE_NUMBER relocs against this symbol, mark
+      // it as NO_STRIP so as to ensure that the indirect function table makes
+      // it to linked output.
+      Sym->setNoStrip();
     } 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

llvm/lib/Target/WebAssembly/WebAssemblyFastISel.cpp

 ///
 //===----------------------------------------------------------------------===//
 
 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
 #include "WebAssembly.h"
 #include "WebAssemblyMachineFunctionInfo.h"
 #include "WebAssemblySubtarget.h"
 #include "WebAssemblyTargetMachine.h"
+#include "WebAssemblyUtilities.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/CodeGen/FastISel.h"
 #include "llvm/CodeGen/FunctionLoweringInfo.h"
 #include "llvm/CodeGen/MachineConstantPool.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/GlobalAlias.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/Instructions.h"
if (!IsVoid)
     MIB.addReg(ResultReg, RegState::Define);
 
   if (IsDirect) {
     MIB.addGlobalAddress(Func);
   } else {
     // Add placeholders for the type index and immediate flags
     MIB.addImm(0);
     MIB.addImm(0);
+
+    // Ensure that the object file has a __indirect_function_table import, as we
+    // call_indirect against it.
+    MCSymbolWasm *Sym = WebAssembly::getOrCreateFunctionTableSymbol(
+        MF->getMMI().getContext(), "__indirect_function_table");
+    // Until call_indirect emits TABLE_NUMBER relocs against this symbol, mark
+    // it as NO_STRIP so as to ensure that the indirect function table makes it
+    // to linked output.
+    Sym->setNoStrip();
   }
 
   for (unsigned ArgReg : Args)
     MIB.addReg(ArgReg);
 
   if (!IsDirect)
     MIB.addReg(CalleeReg);
 

llvm/lib/Target/WebAssembly/WebAssemblyISelLowering.cpp

 ///
 //===----------------------------------------------------------------------===//
 
 #include "WebAssemblyISelLowering.h"
 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
 #include "WebAssemblyMachineFunctionInfo.h"
 #include "WebAssemblySubtarget.h"
 #include "WebAssemblyTargetMachine.h"
+#include "WebAssemblyUtilities.h"
 #include "llvm/CodeGen/Analysis.h"
 #include "llvm/CodeGen/CallingConvLower.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineJumpTableInfo.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/SelectionDAG.h"
 #include "llvm/CodeGen/WasmEHFuncInfo.h"
static MachineBasicBlock *LowerCallResults(MachineInstr &CallResults,
 
   for (auto Def : CallResults.defs())
     MIB.add(Def);
 
   // Add placeholders for the type index and immediate flags
   if (IsIndirect) {
     MIB.addImm(0);
     MIB.addImm(0);
+
+    // Ensure that the object file has a __indirect_function_table import, as we
+    // call_indirect against it.
+    MCSymbolWasm *Sym = WebAssembly::getOrCreateFunctionTableSymbol(
+        MF.getContext(), "__indirect_function_table");
+    // Until call_indirect emits TABLE_NUMBER relocs against this symbol, mark
+    // it as NO_STRIP so as to ensure that the indirect function table makes it
+    // to linked output.
+    Sym->setNoStrip();
   }
 
   for (auto Use : CallParams.uses())
     MIB.add(Use);
 
   BB->insert(CallResults.getIterator(), MIB);
   CallParams.eraseFromParent();
   CallResults.eraseFromParent();

llvm/lib/Target/WebAssembly/WebAssemblyUtilities.h

 
 #ifndef LLVM_LIB_TARGET_WEBASSEMBLY_WEBASSEMBLYUTILITIES_H
 #define LLVM_LIB_TARGET_WEBASSEMBLY_WEBASSEMBLYUTILITIES_H
 
 namespace llvm {
 
 class MachineInstr;
 class MachineOperand;
+class MCContext;
+class MCSymbolWasm;
+class StringRef;
 class WebAssemblyFunctionInfo;
 
 namespace WebAssembly {
 
 bool isChild(const MachineInstr &MI, const WebAssemblyFunctionInfo &MFI);
 bool mayThrow(const MachineInstr &MI);
 
 // Exception-related function names
 extern const char *const ClangCallTerminateFn;
 extern const char *const CxaBeginCatchFn;
 extern const char *const CxaRethrowFn;
 extern const char *const StdTerminateFn;
 extern const char *const PersonalityWrapperFn;
 
 /// Returns the operand number of a callee, assuming the argument is a call
 /// instruction.
 const MachineOperand &getCalleeOp(const MachineInstr &MI);
 
+/// Returns the operand number of a callee, assuming the argument is a call
+/// instruction.
+MCSymbolWasm *getOrCreateFunctionTableSymbol(MCContext &Ctx,
+                                             const StringRef &Name);
+
 } // end namespace WebAssembly
 
 } // end namespace llvm
 
 #endif

llvm/lib/Target/WebAssembly/WebAssemblyUtilities.cpp

 /// This file implements several utility functions for WebAssembly.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "WebAssemblyUtilities.h"
 #include "WebAssemblyMachineFunctionInfo.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
+#include "llvm/MC/MCContext.h"
 using namespace llvm;
 
 const char *const WebAssembly::ClangCallTerminateFn = "__clang_call_terminate";
 const char *const WebAssembly::CxaBeginCatchFn = "__cxa_begin_catch";
 const char *const WebAssembly::CxaRethrowFn = "__cxa_rethrow";
 const char *const WebAssembly::StdTerminateFn = "_ZSt9terminatev";
 const char *const WebAssembly::PersonalityWrapperFn =
     "_Unwind_Wasm_CallPersonality";
const MachineOperand &WebAssembly::getCalleeOp(const MachineInstr &MI) {
   case WebAssembly::CALL_INDIRECT_S:
   case WebAssembly::RET_CALL_INDIRECT:
   case WebAssembly::RET_CALL_INDIRECT_S:
     return MI.getOperand(MI.getNumOperands() - 1);
   default:
     llvm_unreachable("Not a call instruction");
   }
 }
+
+MCSymbolWasm *
+WebAssembly::getOrCreateFunctionTableSymbol(MCContext &Ctx,
+                                            const StringRef &Name) {
+  // FIXME: Duplicates functionality from
+  // MC/WasmObjectWriter::recordRelocation.
+  MCSymbolWasm *Sym = cast_or_null<MCSymbolWasm>(Ctx.lookupSymbol(Name));
+  if (Sym) {
+    if (!Sym->isFunctionTable())
+      Ctx.reportError(SMLoc(), "symbol is not a wasm funcref table");
+  } else {
+    Sym = cast<MCSymbolWasm>(Ctx.getOrCreateSymbol(Name));
+    Sym->setFunctionTable();
+    // The default function table is synthesized by the linker.
+    Sym->setUndefined();
+  }
+  return Sym;
+}

llvm/test/CodeGen/WebAssembly/call-indirect.ll

+; RUN: llc < %s -asm-verbose=false -O2 | FileCheck --check-prefix=CHECK %s
+; RUN: llc < %s -asm-verbose=false -O2 --filetype=obj | obj2yaml | FileCheck --check-prefix=OBJ %s
+
+; Test that compilation units with call_indirect but without any
+; function pointer declarations still get a table.
+
+target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
+target triple = "wasm32-unknown-unknown"
+
+; CHECK-LABEL: call_indirect_void:
+; CHECK-NEXT: .functype call_indirect_void (i32) -> ()
+; CHECK-NEXT: local.get 0
+; CHECK-NEXT: call_indirect () -> ()
+; CHECK-NEXT: end_function
+define void @call_indirect_void(void ()* %callee) {
+  call void %callee()
+  ret void
+}
+
+; OBJ:    Imports:
+; OBJ-NEXT:      - Module:          env
+; OBJ-NEXT:        Field:           __linear_memory
+; OBJ-NEXT:        Kind:            MEMORY
+; OBJ-NEXT:        Memory:
+; OBJ-NEXT:          Initial:         0x0
+; OBJ-NEXT:      - Module:          env
+; OBJ-NEXT:        Field:           __indirect_function_table
+; OBJ-NEXT:        Kind:            TABLE

llvm/test/MC/WebAssembly/type-index.s

 # BIN-NEXT:           - F64
 # BIN-NEXT:   - Type:            IMPORT
 # BIN-NEXT:     Imports:
 # BIN-NEXT:       - Module:          env
 # BIN-NEXT:         Field:           __linear_memory
 # BIN-NEXT:         Kind:            MEMORY
 # BIN-NEXT:         Memory:
 # BIN-NEXT:           Initial:         0x0
+# BIN-NEXT:       - Module:          env
+# BIN-NEXT:         Field:           __indirect_function_table
+# BIN-NEXT:         Kind:            TABLE
+# BIN-NEXT:         Table:
+# BIN-NEXT:           Index:           0
+# BIN-NEXT:           ElemType:        FUNCREF
+# BIN-NEXT:           Limits:
+# BIN-NEXT:             Initial:         0x0
 # BIN-NEXT:   - Type:            FUNCTION
 # BIN-NEXT:     FunctionTypes:   [ 0 ]
 # BIN-NEXT:   - Type:            CODE
 # BIN-NEXT:     Relocations:
 # BIN-NEXT:       - Type:            R_WASM_TYPE_INDEX_LEB
 # BIN-NEXT:         Index:           1
 # BIN-NEXT:         Offset:          0x4
 # BIN-NEXT:     Functions: