[lld][WebAssembly] Allow linking of PIC code into static binaries

[sbc100]

Summary

See https://github.com/emscripten-core/emscripten/issues/9013

[sbc100]

add __table_base

[ruiu]

lld/wasm/Relocations.cpp

43 ↗

(On Diff #214059)

nit: space not after but before *

[kripken]

Nothing looks wrong to me here, but I don't know enough to fully understand it, sorry - like what the various indexes are, what a virtual address means here, etc.

Perhaps @tlively can take a look if we need a second reviewer, as he's worked on this code recently?

[dschuff]

lld/wasm/Driver.cpp

541 ↗

(On Diff #214059)

does this mean we create these symbols in the output even when not linking PIC code?

[sbc100]

• clang-format

[sbc100]

lld/wasm/Driver.cpp

541 ↗

(On Diff #214059)

Yes, they go from being imported global to local, globals with a fixed value. wasm-opt can then eliminate them completely. See the comment in addGOTEntry.

As a followup we could instead do linker relaxation to remove references to these.

[sbc100]

@dschuff ptal

lld/trunk/test/wasm/pic-static.ll

+; Test that PIC code can be linked into static binaries.
+; In this case the GOT entries will end up as internalized wasm globals with
+; fixed values.
+; RUN: llc -relocation-model=pic -filetype=obj %p/Inputs/ret32.ll -o %t.ret32.o
+; RUN: llc -relocation-model=pic -filetype=obj %s -o %t.o
+; RUN: wasm-ld -o %t.wasm %t.o %t.ret32.o
+; RUN: obj2yaml %t.wasm | FileCheck %s
+
+target triple = "wasm32-unknown-emscripten"
+
+declare i32 @ret32(float)
+@global_float = global float 1.0
+@hidden_float = hidden global float 2.0
+
+@ret32_ptr = global i32 (float)* @ret32, align 4
+
+define i32 (float)* @getaddr_external() {
+  ret i32 (float)* @ret32;
+}
+
+define i32 ()* @getaddr_hidden() {
+  ret i32 ()* @hidden_func;
+}
+
+define hidden i32 @hidden_func() {
+  ret i32 1
+}
+
+define void @_start() {
+entry:
+  %f = load float, float* @hidden_float, align 4
+  %addr = load i32 (float)*, i32 (float)** @ret32_ptr, align 4
+  %arg = load float, float* @global_float, align 4
+  call i32 %addr(float %arg)
+
+  %addr2 = call i32 (float)* @getaddr_external()
+  %arg2 = load float, float* @hidden_float, align 4
+  call i32 %addr2(float %arg2)
+
+  %addr3 = call i32 ()* @getaddr_hidden()
+  call i32 %addr3()
+
+  ret void
+}
+
+; CHECK:        - Type:            GLOBAL
+; CHECK-NEXT:     Globals:
+
+; __stack_pointer
+; CHECK-NEXT:       - Index:           0
+; CHECK-NEXT:         Type:            I32
+; CHECK-NEXT:         Mutable:         true
+; CHECK-NEXT:         InitExpr:
+; CHECK-NEXT:           Opcode:          I32_CONST
+; CHECK-NEXT:           Value:           66576
+
+; GOT.func.ret32
+; CHECK-NEXT:       - Index:           1
+; CHECK-NEXT:         Type:            I32
+; CHECK-NEXT:         Mutable:         false
+; CHECK-NEXT:         InitExpr:
+; CHECK-NEXT:           Opcode:          I32_CONST
+; CHECK-NEXT:           Value:           2
+
+; __table_base
+; CHECK-NEXT:       - Index:           2
+; CHECK-NEXT:         Type:            I32
+; CHECK-NEXT:         Mutable:         false
+; CHECK-NEXT:         InitExpr:
+; CHECK-NEXT:           Opcode:          I32_CONST
+; CHECK-NEXT:           Value:           1
+
+; GOT.mem.global_float
+; CHECK-NEXT:       - Index:           3
+; CHECK-NEXT:         Type:            I32
+; CHECK-NEXT:         Mutable:         false
+; CHECK-NEXT:         InitExpr:
+; CHECK-NEXT:           Opcode:          I32_CONST
+; CHECK-NEXT:           Value:           1024
+
+; GOT.mem.ret32_ptr
+; CHECK-NEXT:       - Index:           4
+; CHECK-NEXT:         Type:            I32
+; CHECK-NEXT:         Mutable:         false
+; CHECK-NEXT:         InitExpr:
+; CHECK-NEXT:           Opcode:          I32_CONST
+; CHECK-NEXT:           Value:           1032
+
+; __memory_base
+; CHECK-NEXT:       - Index:           5
+; CHECK-NEXT:         Type:            I32
+; CHECK-NEXT:         Mutable:         false
+; CHECK-NEXT:         InitExpr:
+; CHECK-NEXT:           Opcode:          I32_CONST
+; CHECK-NEXT:           Value:           1024

lld/trunk/wasm/Driver.cpp

static void createOptionalSymbols() {
   WasmSym::dsoHandle = symtab->addOptionalDataSymbol("__dso_handle");
 
   if (!config->shared)
     WasmSym::dataEnd = symtab->addOptionalDataSymbol("__data_end");
 
   if (!config->isPic) {
     WasmSym::globalBase = symtab->addOptionalDataSymbol("__global_base");
     WasmSym::heapBase = symtab->addOptionalDataSymbol("__heap_base");
+    WasmSym::definedMemoryBase = symtab->addOptionalDataSymbol("__memory_base");
+    WasmSym::definedTableBase = symtab->addOptionalDataSymbol("__table_base");
   }
 }
 
 // Reconstructs command line arguments so that so that you can re-run
 // the same command with the same inputs. This is for --reproduce.
 static std::string createResponseFile(const opt::InputArgList &args) {
   SmallString<0> data;
   raw_svector_ostream os(data);

lld/trunk/wasm/Relocations.cpp

 
 static void reportUndefined(const Symbol* sym) {
   assert(sym->isUndefined());
   assert(!sym->isWeak());
   if (!allowUndefined(sym))
     error(toString(sym->getFile()) + ": undefined symbol: " + toString(*sym));
 }
 
+static void addGOTEntry(Symbol *sym) {
+  // In PIC mode a GOT entry is an imported global that the dynamic linker
+  // will assign.
+  // In non-PIC mode (i.e. when code compiled as fPIC is linked into a static
+  // binary) we create an internal wasm global with a fixed value that takes the
+  // place of th GOT entry and effectivly acts as an i32 const. This can
+  // potentially be optimized away at runtime or with a post-link tool.
+  // TODO(sbc): Linker relaxation might also be able to optimize this away.
+  if (config->isPic)
+    out.importSec->addGOTEntry(sym);
+  else
+    out.globalSec->addDummyGOTEntry(sym);
+}
+
 void lld::wasm::scanRelocations(InputChunk *chunk) {
   if (!chunk->live)
     return;
   ObjFile *file = chunk->file;
   ArrayRef<WasmSignature> types = file->getWasmObj()->types();
   for (const WasmRelocation &reloc : chunk->getRelocations()) {
     if (reloc.Type == R_WASM_TYPE_INDEX_LEB) {
       // Mark target type as live
for (const WasmRelocation &reloc : chunk->getRelocations()) {
     case R_WASM_TABLE_INDEX_SLEB:
     case R_WASM_TABLE_INDEX_REL_SLEB:
       if (requiresGOTAccess(sym))
         break;
       out.elemSec->addEntry(cast<FunctionSymbol>(sym));
       break;
     case R_WASM_GLOBAL_INDEX_LEB:
       if (!isa<GlobalSymbol>(sym))
-        out.importSec->addGOTEntry(sym);
+        addGOTEntry(sym);
       break;
     }
 
     if (config->isPic) {
       switch (reloc.Type) {
       case R_WASM_TABLE_INDEX_SLEB:
       case R_WASM_MEMORY_ADDR_SLEB:
       case R_WASM_MEMORY_ADDR_LEB:
         // Certain relocation types can't be used when building PIC output,
         // since they would require absolute symbol addresses at link time.
         error(toString(file) + ": relocation " + relocTypeToString(reloc.Type) +
               " cannot be used against symbol " + toString(*sym) +
               "; recompile with -fPIC");
         break;
       case R_WASM_TABLE_INDEX_I32:
       case R_WASM_MEMORY_ADDR_I32:
         // These relocation types are only present in the data section and
         // will be converted into code by `generateRelocationCode`.  This code
         // requires the symbols to have GOT entires.
         if (requiresGOTAccess(sym))
-          out.importSec->addGOTEntry(sym);
+          addGOTEntry(sym);
         break;
       }
     } else {
       // Report undefined symbols
       if (sym->isUndefined() && !config->relocatable && !sym->isWeak())
         reportUndefined(sym);
     }
 
   }
 }

lld/trunk/wasm/Symbols.h

struct WasmSym {
 
   // __dso_handle
   // Symbol used in calls to __cxa_atexit to determine current DLL
   static DefinedData *dsoHandle;
 
   // __table_base
   // Used in PIC code for offset of indirect function table
   static UndefinedGlobal *tableBase;
+  static DefinedData *definedTableBase;
 
   // __memory_base
   // Used in PIC code for offset of global data
   static UndefinedGlobal *memoryBase;
+  static DefinedData *definedMemoryBase;
 };
 
 // A buffer class that is large enough to hold any Symbol-derived
 // object. We allocate memory using this class and instantiate a symbol
 // using the placement new.
 union SymbolUnion {
   alignas(DefinedFunction) char a[sizeof(DefinedFunction)];
   alignas(DefinedData) char b[sizeof(DefinedData)];

lld/trunk/wasm/Symbols.cpp

 DefinedData *WasmSym::dataEnd;
 DefinedData *WasmSym::globalBase;
 DefinedData *WasmSym::heapBase;
 GlobalSymbol *WasmSym::stackPointer;
 GlobalSymbol *WasmSym::tlsBase;
 GlobalSymbol *WasmSym::tlsSize;
 GlobalSymbol *WasmSym::tlsAlign;
 UndefinedGlobal *WasmSym::tableBase;
+DefinedData *WasmSym::definedTableBase;
 UndefinedGlobal *WasmSym::memoryBase;
+DefinedData *WasmSym::definedMemoryBase;
 
 WasmSymbolType Symbol::getWasmType() const {
   if (isa<FunctionSymbol>(this))
     return WASM_SYMBOL_TYPE_FUNCTION;
   if (isa<DataSymbol>(this))
     return WASM_SYMBOL_TYPE_DATA;
   if (isa<GlobalSymbol>(this))
     return WASM_SYMBOL_TYPE_GLOBAL;
LLVM_DEBUG(dbgs() << "setOutputSymbolIndex " << name << " -> " << index
                     << "\n");
   assert(outputSymbolIndex == INVALID_INDEX);
   outputSymbolIndex = index;
 }
 
 void Symbol::setGOTIndex(uint32_t index) {
   LLVM_DEBUG(dbgs() << "setGOTIndex " << name << " -> " << index << "\n");
   assert(gotIndex == INVALID_INDEX);
+  if (config->isPic) {
     // Any symbol that is assigned a GOT entry must be exported othewise the
     // dynamic linker won't be able create the entry that contains it.
     forceExport = true;
+  }
   gotIndex = index;
 }
 
 bool Symbol::isWeak() const {
   return (flags & WASM_SYMBOL_BINDING_MASK) == WASM_SYMBOL_BINDING_WEAK;
 }
 
 bool Symbol::isLocal() const {

lld/trunk/wasm/SyntheticSections.h

void writeTo(uint8_t *buf) override {
     memcpy(buf + offset, header.data(), header.size());
     memcpy(buf + offset + header.size(), body.data(), body.size());
   }
 
   size_t getSize() const override { return header.size() + body.size(); }
 
   virtual void writeBody() {}
 
+  virtual void assignIndexes() {}
+
   void finalizeContents() override {
     writeBody();
     bodyOutputStream.flush();
     createHeader(body.size());
   }
 
   raw_ostream &getStream() { return bodyOutputStream; }
 
public:
 
   void writeBody() override;
 };
 
 class GlobalSection : public SyntheticSection {
 public:
   GlobalSection() : SyntheticSection(llvm::wasm::WASM_SEC_GLOBAL) {}
   uint32_t numGlobals() const {
-    return inputGlobals.size() + definedFakeGlobals.size();
+    return inputGlobals.size() + definedFakeGlobals.size() + gotSymbols.size();
   }
   bool isNeeded() const override { return numGlobals() > 0; }
+  void assignIndexes() override;
   void writeBody() override;
   void addGlobal(InputGlobal *global);
+  void addDummyGOTEntry(Symbol *sym);
 
   std::vector<const DefinedData *> definedFakeGlobals;
   std::vector<InputGlobal *> inputGlobals;
+  std::vector<Symbol *> gotSymbols;
 };
 
 // The event section contains a list of declared wasm events associated with the
 // module. Currently the only supported event kind is exceptions. A single event
 // entry represents a single event with an event tag. All C++ exceptions are
 // represented by a single event. An event entry in this section contains
 // information on what kind of event it is (e.g. exception) and the type of
 // values contained in a single event object. (In wasm, an event can contain

lld/trunk/wasm/SyntheticSections.cpp

if (config->importMemory)
     ++numImports;
   if (config->importTable)
     ++numImports;
   return numImports;
 }
 
 void ImportSection::addGOTEntry(Symbol *sym) {
   assert(!isSealed);
+  LLVM_DEBUG(dbgs() << "addGOTEntry: " << toString(*sym) << "\n");
   if (sym->hasGOTIndex())
     return;
   sym->setGOTIndex(numImportedGlobals++);
   gotSymbols.push_back(sym);
 }
 
 void ImportSection::addImport(Symbol *sym) {
   assert(!isSealed);
void MemorySection::writeBody() {
   if (config->sharedMemory)
     flags |= WASM_LIMITS_FLAG_IS_SHARED;
   writeUleb128(os, flags, "memory limits flags");
   writeUleb128(os, numMemoryPages, "initial pages");
   if (hasMax)
     writeUleb128(os, maxMemoryPages, "max pages");
 }
 
+void GlobalSection::assignIndexes() {
+  uint32_t globalIndex = out.importSec->getNumImportedGlobals();
+  for (InputGlobal *g : inputGlobals)
+    g->setGlobalIndex(globalIndex++);
+  for (Symbol *sym : gotSymbols)
+    sym->setGOTIndex(globalIndex++);
+}
+
+void GlobalSection::addDummyGOTEntry(Symbol *sym) {
+  LLVM_DEBUG(dbgs() << "addDummyGOTEntry: " << toString(*sym) << "\n");
+  if (sym->hasGOTIndex())
+    return;
+  gotSymbols.push_back(sym);
+}
+
 void GlobalSection::writeBody() {
   raw_ostream &os = bodyOutputStream;
 
   writeUleb128(os, numGlobals(), "global count");
-  for (const InputGlobal *g : inputGlobals)
+  for (InputGlobal *g : inputGlobals)
     writeGlobal(os, g->global);
   for (const DefinedData *sym : definedFakeGlobals) {
     WasmGlobal global;
     global.Type = {WASM_TYPE_I32, false};
     global.InitExpr.Opcode = WASM_OPCODE_I32_CONST;
     global.InitExpr.Value.Int32 = sym->getVirtualAddress();
     writeGlobal(os, global);
   }
+  for (const Symbol *sym : gotSymbols) {
+    WasmGlobal global;
+    global.Type = {WASM_TYPE_I32, false};
+    global.InitExpr.Opcode = WASM_OPCODE_I32_CONST;
+    if (auto *d = dyn_cast<DefinedData>(sym))
+      global.InitExpr.Value.Int32 = d->getVirtualAddress();
+    else if (auto *f = cast<DefinedFunction>(sym))
+      global.InitExpr.Value.Int32 = f->getTableIndex();
+    writeGlobal(os, global);
+  }
 }
 
 void GlobalSection::addGlobal(InputGlobal *global) {
   if (!global->live)
     return;
-  uint32_t globalIndex =
-      out.importSec->getNumImportedGlobals() + inputGlobals.size();
-  LLVM_DEBUG(dbgs() << "addGlobal: " << globalIndex << "\n");
-  global->setGlobalIndex(globalIndex);
-  out.globalSec->inputGlobals.push_back(global);
+  inputGlobals.push_back(global);
 }
 
 void EventSection::writeBody() {
   raw_ostream &os = bodyOutputStream;
 
   writeUleb128(os, inputEvents.size(), "event count");
   for (InputEvent *e : inputEvents) {
     e->event.Type.SigIndex = out.typeSec->lookupType(e->signature);

lld/trunk/wasm/Writer.cpp

void Writer::layoutMemory() {
   if (config->stackFirst) {
     placeStack();
   } else {
     memoryPtr = config->globalBase;
     log("mem: global base = " + Twine(config->globalBase));
   }
 
   if (WasmSym::globalBase)
-    WasmSym::globalBase->setVirtualAddress(config->globalBase);
+    WasmSym::globalBase->setVirtualAddress(memoryPtr);
+  if (WasmSym::definedMemoryBase)
+    WasmSym::definedMemoryBase->setVirtualAddress(memoryPtr);
 
   uint32_t dataStart = memoryPtr;
 
   // Arbitrarily set __dso_handle handle to point to the start of the data
   // segments.
   if (WasmSym::dsoHandle)
     WasmSym::dsoHandle->setVirtualAddress(dataStart);
 
for (InputGlobal *global : file->globals)
       out.globalSec->addGlobal(global);
   }
 
   for (ObjFile *file : symtab->objectFiles) {
     LLVM_DEBUG(dbgs() << "Events: " << file->getName() << "\n");
     for (InputEvent *event : file->events)
       out.eventSec->addEvent(event);
   }
+
+  out.globalSec->assignIndexes();
 }
 
 static StringRef getOutputDataSegmentName(StringRef name) {
   // With PIC code we currently only support a single data segment since
   // we only have a single __memory_base to use as our base address.
   if (config->isPic)
     return ".data";
   // We only support one thread-local segment, so we must merge the segments

 }
 
 void Writer::run() {
   if (config->relocatable || config->isPic)
     config->globalBase = 0;
 
   // For PIC code the table base is assigned dynamically by the loader.
   // For non-PIC, we start at 1 so that accessing table index 0 always traps.
-  if (!config->isPic)
+  if (!config->isPic) {
     tableBase = 1;
+    if (WasmSym::definedTableBase)
+      WasmSym::definedTableBase->setVirtualAddress(tableBase);
+  }
 
   log("-- createOutputSegments");
   createOutputSegments();
   log("-- createSyntheticSections");
   createSyntheticSections();
   log("-- populateProducers");
   populateProducers();
   log("-- populateTargetFeatures");