[WebAssembly] Initial implementation of PIC code generation

[sbc100]

Summary

This change implements lowering of references global symbols in
PIC mode.

This change implements lowering of global references in PIC mode using
a new @GOT reference type. @GOT references can be used with function
or data symbol names combined with the get_global instruction. In
this case the linker will insert the wasm global that stores the address of
the symbol (either in memory for data symbols or in the wasm table
for function symbols).

For now I'm continuing to use the R_WASM_GLOBAL_INDEX_LEB relocation
type for this type of reference which means that this relocation type can
refer to either a global or a function or data symbol. We could choose to
introduce specific relocation types for GOT entries in the future.

See the current dynamic linking proposal:
https://github.com/WebAssembly/tool-conventions/blob/master/DynamicLinking.md

[sbc100]

@dschuff can you take a look at the WebAssemblyFastISel.cpp part? I want to make sure I'm on the right track.

I'm currently looking at extending this to all the cases in test/CodeGen/WebAssembly/address-offsets.ll

[sbc100]

get parts of address-offsets.ll passing

[aheejin]

lib/Target/WebAssembly/WebAssemblyAsmPrinter.cpp

94 ↗

(On Diff #174481)

Delete this?

109 ↗

(On Diff #174481)

Delete this too?

lib/Target/WebAssembly/WebAssemblyFastISel.cpp

799 ↗

(On Diff #174481)

Delete?

lib/Target/WebAssembly/WebAssemblyISelLowering.cpp

736 ↗

(On Diff #174481)

Delete?

[sbc100]

lib/Target/WebAssembly/WebAssemblyAsmPrinter.cpp

94 ↗

(On Diff #174481)

Sorry, this change is just WIP, not ready to commit yet. I'll remove this stuff before then

[sbc100]

rebase

[sbc100]

• move to monorepo

[sbc100]

update

[sbc100]

revert parts

[sbc100]

• isel start

[sbc100]

• selection dag working

[sbc100]

• improve test

[sbc100]

• cleaup test code
• add MC test

[tlively]

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

94 ↗

(On Diff #190914)

Is there a reason to use 1 << 3 instead of 0x8 to match the other enum values?

llvm/lib/Target/WebAssembly/WebAssemblyFastISel.cpp

422 ↗

(On Diff #190914)

Should this be dependent on Subtarget->hasAddr64() like Opc is?

428 ↗

(On Diff #190914)

Same question for OpcAdd.

476 ↗

(On Diff #190914)

Should this commented code be deleted?

llvm/lib/Target/WebAssembly/WebAssemblyISelLowering.cpp

765 ↗

(On Diff #190914)

More commented code here.

llvm/test/MC/WebAssembly/reloc-pic.s

1 ↗

(On Diff #190914)

If you want, you can avoid the temp file and output to stdout using -o -. I find that having the entire test on one line with no intermediate files makes the test easier to debug when something changes.

[sbc100]

• feedback
• cleanup

[sbc100]

• clang-format
• remove 64

[sbc100]

llvm/lib/Target/WebAssembly/WebAssemblyFastISel.cpp

422 ↗

(On Diff #190914)

Hmm , good question. I'm temped to not to add to much wasm64 code because we have no way of testing it and its premature .. so I think I'll just remove the ternary above.

llvm/test/MC/WebAssembly/reloc-pic.s

1 ↗

(On Diff #190914)

Thanks (looks like i don't even need -o - as its the default.

[tlively]

llvm/lib/Target/WebAssembly/WebAssemblyFastISel.cpp

422 ↗

(On Diff #190914)

sounds good to me!

[dschuff]

llvm/include/llvm/MC/MCSymbolWasm.h

21 ↗

(On Diff #190925)

sad how often mutable is used in LLVM. I guess maybe it means we're too aggressive about const overall?

[dschuff]

wow that's a very large meme.

[sbc100]

llvm/include/llvm/MC/MCSymbolWasm.h

21 ↗

(On Diff #190925)

I only dun it cos they already dun it before guvnor: https://github.com/llvm-mirror/llvm/blob/7feefc2fe73c27062407322a14241d1a4497cdb1/include/llvm/MC/MCSymbol.h#L106

TBH I didn't even know about this keyword! And its seems crazy but it seems like that is the solution in this case.

[sbc100]

• remove_lld_todo

[aheejin]

llvm/test/CodeGen/WebAssembly/address-offsets.ll

43 ↗

(On Diff #190940)

Are these temporarily disabled? (Same for other occurrences below) If so, can we add a comment why? If it's not temporary we can maybe delete them?

[sbc100]

• add more tests

[sbc100]

llvm/test/CodeGen/WebAssembly/address-offsets.ll

43 ↗

(On Diff #190940)

These tests we deliberately disabled in https://reviews.llvm.org/D24053. See the TODO comment above.

Whoever gets around to fixing them will need to make the fast-isel compatible too.

[sbc100]

• cleanup test
• revert fast isel changes for now

[sbc100]

• revert fast isel changes
• cleanup

[sbc100]

• cleanup

[sbc100]

• add GOT.mem and GOT.func

[sbc100]

• cleanup

[dschuff]

still LGTM. In a followup CL it should be straightforward to add back fast-isel and you might be able to re-use the same checks in load-store-pic.ll. (but you wouldn't need to add fast-isel+PIC to address-offsets.ll because that's testing an optimization that fast-isel doesn't do.)

[kripken]

This broke wasm2.test_openjpeg on CI, reproducible locally. Errors on error: undefined symbol: __memory_base

test/wasm/shared.ll

-; RUN: llc -O0 -filetype=obj %s -o %t.o
+; RUN: llc -relocation-model=pic -filetype=obj %s -o %t.o
 ; RUN: wasm-ld -shared -o %t.wasm %t.o
 ; RUN: obj2yaml %t.wasm | FileCheck %s
 
 target triple = "wasm32-unknown-unknown"
 
 @data = hidden global i32 2, align 4
+@data_external = external global i32
 @indirect_func = local_unnamed_addr global i32 ()* @foo, align 4
 @indirect_func_external = local_unnamed_addr global void ()* @func_external, align 4
 
 define default i32 @foo() {
 entry:
   ; To ensure we use __stack_pointer
   %ptr = alloca i32
   %0 = load i32, i32* @data, align 4
-  ; TODO(sbc): Re-enable once the codegen supports generating the correct
-  ; relocation type when referencing external data in shared libraries.
-  ; %1 = load i32, i32* @data_external, align 4
   %1 = load i32 ()*, i32 ()** @indirect_func, align 4
   call i32 %1()
   ret i32 %0
 }
 
-declare void @func_external()
+define default i32* @get_data_address() {
+entry:
+  ret i32* @data_external
+}
 
-@data_external = external global i32
+define default i8* @get_func_address() {
+entry:
+  ret i8* bitcast (void ()* @func_external to i8*)
+}
 
+declare void @func_external()
 
 ; check for dylink section at start
 
 ; CHECK:      Sections:
 ; CHECK-NEXT:   - Type:            CUSTOM
 ; CHECK-NEXT:     Name:            dylink
 ; CHECK-NEXT:     MemorySize:      12
 ; CHECK-NEXT:     MemoryAlignment: 2
 ; CHECK-NEXT:     TableSize:       2
 ; CHECK-NEXT:     TableAlignment:  0
 ; CHECK-NEXT:     Needed:          []
 ; CHECK-NEXT:   - Type:            TYPE
 
 ; check for import of __table_base and __memory_base globals
 
 ; CHECK:        - Type:            IMPORT
 ; CHECK-NEXT:     Imports:
 ; CHECK-NEXT:       - Module:          env
+; CHECK-NEXT:         Field:           memory
+; CHECK-NEXT:         Kind:            MEMORY
+; CHECK-NEXT:         Memory:
+; CHECK-NEXT:           Initial:       0x0000000
+; CHECK-NEXT:       - Module:          env
 ; CHECK-NEXT:         Field:           __indirect_function_table
 ; CHECK-NEXT:         Kind:            TABLE
 ; CHECK-NEXT:         Table:
 ; CHECK-NEXT:           ElemType:        FUNCREF
 ; CHECK-NEXT:           Limits:
 ; CHECK-NEXT:             Initial:         0x00000002
 ; CHECK-NEXT:       - Module:          env
 ; CHECK-NEXT:         Field:           __stack_pointer
 ; CHECK-NEXT:         Kind:            GLOBAL
 ; CHECK-NEXT:         GlobalType:      I32
 ; CHECK-NEXT:         GlobalMutable:   true
 ; CHECK-NEXT:       - Module:          env
 ; CHECK-NEXT:         Field:           __memory_base
 ; CHECK-NEXT:         Kind:            GLOBAL
 ; CHECK-NEXT:         GlobalType:      I32
 ; CHECK-NEXT:         GlobalMutable:   false
 ; CHECK-NEXT:       - Module:          env
 ; CHECK-NEXT:         Field:           __table_base
 ; CHECK-NEXT:         Kind:            GLOBAL
 ; CHECK-NEXT:         GlobalType:      I32
 ; CHECK-NEXT:         GlobalMutable:   false
-; XCHECK-NEXT:       - Module:          env
-; XCHECK-NEXT:         Field:           data_external
-; XCHECK-NEXT:         Kind:            GLOBAL
-; XCHECK-NEXT:         GlobalType:      I32
-; XCHECK-NEXT:         GlobalMutable:   true
 ; CHECK-NEXT:       - Module:          env
 ; CHECK-NEXT:         Field:           func_external
 ; CHECK-NEXT:         Kind:            FUNCTION
 ; CHECK-NEXT:         SigIndex:        1
+; CHECK-NEXT:       - Module:          GOT.mem
+; CHECK-NEXT:         Field:           data_external
+; CHECK-NEXT:         Kind:            GLOBAL
+; CHECK-NEXT:         GlobalType:      I32
+; CHECK-NEXT:         GlobalMutable:   true
+; CHECK-NEXT:       - Module:          GOT.func
+; CHECK-NEXT:         Field:           func_external
+; CHECK-NEXT:         Kind:            GLOBAL
+; CHECK-NEXT:         GlobalType:      I32
+; CHECK-NEXT:         GlobalMutable:   true
+; CHECK-NEXT:   - Type:            FUNCTION
 
 ; check for elem segment initialized with __table_base global as offset
 
 ; CHECK:        - Type:            ELEM
 ; CHECK-NEXT:     Segments:
 ; CHECK-NEXT:       - Offset:
 ; CHECK-NEXT:           Opcode:          GLOBAL_GET
 ; CHECK-NEXT:           Index:           2

wasm/Driver.cpp

void LinkerDriver::link(ArrayRef<const char *> ArgsArr) {
 
   if (Config->Pic) {
     if (Config->ExportTable)
       error("-shared/-pie is incompatible with --export-table");
     Config->ImportTable = true;
   }
 
   if (Config->Shared) {
+    Config->ImportMemory = true;
     Config->ExportDynamic = true;
     Config->AllowUndefined = true;
   }
 
   // Handle --trace-symbol.
   for (auto *Arg : Args.filtered(OPT_trace_symbol))
     Symtab->trace(Arg->getValue());
 

wasm/InputChunks.cpp

case R_WASM_SECTION_OFFSET_I32:
       ExistingValue = static_cast<uint32_t>(read32le(Loc));
       break;
     default:
       llvm_unreachable("unknown relocation type");
     }
 
     if (BytesRead && BytesRead != 5)
       warn("expected LEB at relocation site be 5-byte padded");
+
+    if (Rel.Type != R_WASM_GLOBAL_INDEX_LEB) {
       uint32_t ExpectedValue = File->calcExpectedValue(Rel);
       if (ExpectedValue != ExistingValue)
         warn("unexpected existing value for " + reloctTypeToString(Rel.Type) +
              ": existing=" + Twine(ExistingValue) +
              " expected=" + Twine(ExpectedValue));
     }
   }
+}
 
 // Copy this input chunk to an mmap'ed output file and apply relocations.
 void InputChunk::writeTo(uint8_t *Buf) const {
   // Copy contents
   memcpy(Buf + OutputOffset, data().data(), data().size());
 
   // Apply relocations
   if (Relocations.empty())

wasm/InputFiles.cpp

case R_WASM_MEMORY_ADDR_LEB:
     if (auto *Sym = dyn_cast<DefinedData>(getDataSymbol(Reloc.Index)))
       if (Sym->isLive())
         return Sym->getVirtualAddress() + Reloc.Addend;
     return 0;
   case R_WASM_TYPE_INDEX_LEB:
     return TypeMap[Reloc.Index];
   case R_WASM_FUNCTION_INDEX_LEB:
     return getFunctionSymbol(Reloc.Index)->getFunctionIndex();
-  case R_WASM_GLOBAL_INDEX_LEB:
-    return getGlobalSymbol(Reloc.Index)->getGlobalIndex();
-  case R_WASM_EVENT_INDEX_LEB:
+  case R_WASM_GLOBAL_INDEX_LEB: {
+    const Symbol* Sym = Symbols[Reloc.Index];
+    if (auto GS = dyn_cast<GlobalSymbol>(Sym))
+      return GS->getGlobalIndex();
+    return Sym->getGOTIndex();
+  } case R_WASM_EVENT_INDEX_LEB:
     return getEventSymbol(Reloc.Index)->getEventIndex();
   case R_WASM_FUNCTION_OFFSET_I32:
     if (auto *Sym = dyn_cast<DefinedFunction>(getFunctionSymbol(Reloc.Index))) {
       if (Sym->isLive())
         return Sym->Function->OutputOffset +
                Sym->Function->getFunctionCodeOffset() + Reloc.Addend;
     }
     return 0;

wasm/Symbols.h

public:
   // command line flag)
   unsigned ForceExport : 1;
 
   // True if this symbol is specified by --trace-symbol option.
   unsigned Traced : 1;
 
   const WasmSignature* getSignature() const;
 
+  bool isInGOT() const { return GOTIndex != INVALID_INDEX; }
+
+  uint32_t getGOTIndex() const {
+    assert(GOTIndex != INVALID_INDEX);
+    return GOTIndex;
+  }
+
+  void setGOTIndex(uint32_t Index);
+  bool hasGOTIndex() const { return GOTIndex != INVALID_INDEX; }
+
 protected:
   Symbol(StringRef Name, Kind K, uint32_t Flags, InputFile *F)
       : IsUsedInRegularObj(false), ForceExport(false), Traced(false),
         Name(Name), SymbolKind(K), Flags(Flags), File(F),
         Referenced(!Config->GcSections) {}
 
   StringRef Name;
   Kind SymbolKind;
   uint32_t Flags;
   InputFile *File;
   uint32_t OutputSymbolIndex = INVALID_INDEX;
+  uint32_t GOTIndex = INVALID_INDEX;
   bool Referenced;
 };
 
 class FunctionSymbol : public Symbol {
 public:
   static bool classof(const Symbol *S) {
     return S->kind() == DefinedFunctionKind ||
            S->kind() == UndefinedFunctionKind;

 
 class UndefinedData : public DataSymbol {
 public:
   UndefinedData(StringRef Name, uint32_t Flags, InputFile *File = nullptr)
       : DataSymbol(Name, UndefinedDataKind, Flags, File) {}
   static bool classof(const Symbol *S) {
     return S->kind() == UndefinedDataKind;
   }
-
-  // Undefined data symbols are imported as wasm globals so also have a global
-  // index.
-  uint32_t getGlobalIndex() const {
-    assert(GlobalIndex != INVALID_INDEX);
-    return GlobalIndex;
-  }
-  void setGlobalIndex(uint32_t Index) {
-    assert(GlobalIndex == INVALID_INDEX);
-    GlobalIndex = Index;
-  }
-  bool hasGlobalIndex() const { return GlobalIndex != INVALID_INDEX; }
-
-protected:
-  uint32_t GlobalIndex = INVALID_INDEX;
 };
 
 class GlobalSymbol : public Symbol {
 public:
   static bool classof(const Symbol *S) {
     return S->kind() == DefinedGlobalKind || S->kind() == UndefinedGlobalKind;
   }
 

wasm/Symbols.cpp

 
 void Symbol::setOutputSymbolIndex(uint32_t Index) {
   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);
+  GOTIndex = Index;
+}
+
 bool Symbol::isWeak() const {
   return (Flags & WASM_SYMBOL_BINDING_MASK) == WASM_SYMBOL_BINDING_WEAK;
 }
 
 bool Symbol::isLocal() const {
   return (Flags & WASM_SYMBOL_BINDING_MASK) == WASM_SYMBOL_BINDING_LOCAL;
 }
 

wasm/Writer.cpp

private:
   // Memory size and aligment. Written to the "dylink" section
   // when build with -shared or -pie.
   uint32_t MemAlign = 0;
   uint32_t MemSize = 0;
 
   std::vector<const WasmSignature *> Types;
   DenseMap<WasmSignature, int32_t> TypeIndices;
   std::vector<const Symbol *> ImportedSymbols;
+  std::vector<const Symbol *> GOTSymbols;
   unsigned NumImportedFunctions = 0;
   unsigned NumImportedGlobals = 0;
   unsigned NumImportedEvents = 0;
   std::vector<WasmExport> Exports;
   std::vector<const DefinedData *> DefinedFakeGlobals;
   std::vector<InputGlobal *> InputGlobals;
   std::vector<InputFunction *> InputFunctions;
   std::vector<InputEvent *> InputEvents;
private:
 
   std::vector<OutputSegment *> Segments;
   llvm::SmallDenseMap<StringRef, OutputSegment *> SegmentMap;
 };
 
 } // anonymous namespace
 
 void Writer::createImportSection() {
-  uint32_t NumImports = ImportedSymbols.size();
+  uint32_t NumImports = ImportedSymbols.size() + GOTSymbols.size();
   if (Config->ImportMemory)
     ++NumImports;
   if (Config->ImportTable)
     ++NumImports;
 
   if (NumImports == 0)
     return;
 
for (const Symbol *Sym : ImportedSymbols) {
     } else {
       Import.Field = Sym->getName();
       Import.Module = DefaultModule;
     }
 
     if (auto *FunctionSym = dyn_cast<FunctionSymbol>(Sym)) {
       Import.Kind = WASM_EXTERNAL_FUNCTION;
       Import.SigIndex = lookupType(*FunctionSym->Signature);
-    } else if (auto *DataSym = dyn_cast<UndefinedData>(Sym)) {
-      Import.Kind = WASM_EXTERNAL_GLOBAL;
-      Import.Global = {WASM_TYPE_I32, true};
     } else if (auto *GlobalSym = dyn_cast<GlobalSymbol>(Sym)) {
       Import.Kind = WASM_EXTERNAL_GLOBAL;
       Import.Global = *GlobalSym->getGlobalType();
     } else {
       auto *EventSym = cast<EventSymbol>(Sym);
       Import.Kind = WASM_EXTERNAL_EVENT;
       Import.Event.Attribute = EventSym->getEventType()->Attribute;
       Import.Event.SigIndex = lookupType(*EventSym->Signature);
     }
     writeImport(OS, Import);
   }
+
+  for (const Symbol *Sym : GOTSymbols) {
+    WasmImport Import;
+    Import.Kind = WASM_EXTERNAL_GLOBAL;
+    Import.Global = {WASM_TYPE_I32, true};
+    if (isa<DataSymbol>(Sym))
+      Import.Module = "GOT.mem";
+    else
+      Import.Module = "GOT.func";
+    Import.Field = Sym->getName();
+    writeImport(OS, Import);
+  }
 }
 
 void Writer::createTypeSection() {
   SyntheticSection *Section = createSyntheticSection(WASM_SEC_TYPE);
   raw_ostream &OS = Section->getStream();
   writeUleb128(OS, Types.size(), "type count");
   for (const WasmSignature *Sig : Types)
     writeSig(OS, *Sig);
for (Symbol *Sym : Symtab->getSymbols()) {
     if (!Sym->isUndefined())
       continue;
     if (Sym->isWeak() && !Config->Relocatable)
       continue;
     if (!Sym->isLive())
       continue;
     if (!Sym->IsUsedInRegularObj)
       continue;
-    // In relocatable output we don't generate imports for data symbols.
-    // These live only in the symbol table.
-    if (Config->Relocatable && isa<DataSymbol>(Sym))
+    // We don't generate imports for data symbols. They however can be imported
+    // as GOT entries.
+    if (isa<DataSymbol>(Sym))
       continue;
 
     LLVM_DEBUG(dbgs() << "import: " << Sym->getName() << "\n");
     ImportedSymbols.emplace_back(Sym);
     if (auto *F = dyn_cast<FunctionSymbol>(Sym))
       F->setFunctionIndex(NumImportedFunctions++);
     else if (auto *G = dyn_cast<GlobalSymbol>(Sym))
       G->setGlobalIndex(NumImportedGlobals++);
-    else if (auto *D = dyn_cast<UndefinedData>(Sym))
-      D->setGlobalIndex(NumImportedGlobals++);
     else
       cast<EventSymbol>(Sym)->setEventIndex(NumImportedEvents++);
   }
 }
 
 void Writer::calculateExports() {
   if (Config->Relocatable)
     return;
case R_WASM_MEMORY_ADDR_LEB: {
       if (!Config->Relocatable && !isa<DefinedData>(DataSym) &&
           !DataSym->isWeak())
         error(File->getName() +
               ": relocation of type R_WASM_MEMORY_ADDR_* "
               "against undefined data symbol: " +
               DataSym->getName());
       break;
     }
+    case R_WASM_GLOBAL_INDEX_LEB: {
+      auto* Sym = File->getSymbols()[Reloc.Index];
+      if (!isa<GlobalSymbol>(Sym) && !Sym->isInGOT()) {
+        Sym->setGOTIndex(NumImportedGlobals++);
+        GOTSymbols.push_back(Sym);
+      }
+    }
     }
   }
 }
 
 void Writer::assignIndexes() {
   assert(InputFunctions.empty());
   uint32_t FunctionIndex = NumImportedFunctions;
   auto AddDefinedFunction = [&](InputFunction *Func) {