[WebAssembly] Add symbol table to LLD, 1/2

[ncw]

Summary

WebAssembly object files will now have an explicit symbol table. This commit is the first of two halves, adding support throughout the code for addressing symbols by index; however, the symbols are still written out using a single import/export (depending on whether defined).

This half of the symbol table work is valid on its own, and the second half doesn't need to be committed immediately after. However, the corresponding LLVM change D41954 must be committed simultaneously with this.

[ncw]

Updated:

• Some fixes after rebase
• Most tests now passing (a couple of bugs still to iron out)

Thankfully there's not too much to change in LLD!

[ncw]

More updates, fixed all but two tests.

The remaining two tests are rather hard to fix; my changes unfortunately don't play well with "relocatable" output.

Problem #1

The stack-pointer.ll test uses --emit-relocs but not --relocatable. This means that the __stack_pointer symbol is _not_ imported; it's instead defined, but we can't export it (because it's mutable). Thus, the _global_ has an output index, but there is no _symbol_ index for it (so far, behaviour hasn't changed...). What this breaks is that I've made it so that relocs reference the symbol index - so relocs against the stack pointer won't work with --emit-relocs but not --relocatable.

Hmm. Maybe we can just fix the test to use --relocatable :( at least until we can export mutable globals.

Problem #2

The other failing test is init-fini.ll. What causes the problem is that we take the address of a BINDING_LOCAL symbol. When linking with --relocatable, we try and create a relocation against the function and fail. This is because the function isn't exported as a Symbol in the relocatable output.

This can probably be fixed by just exporting Symbols for the locals as well when doing relocatable. We'd need to budge the names to keep them unique, which they won't be if we export the locals from all object files. That would at least make LLD's relocatable output match what Clang outputs.

Conclusion

Linking (relocating) against Symbols rather than functions/globals does make aliases nice and elegant... but breaks some other things.

Another (less good?) solution might be to split the relocations into "FUNCTION_SYMBOL_INDEX_LEB" and "FUNCTION_WASM_INDEX_LEB", where the SYMBOL_INDEX version in outputted by WasmObjectWriter (Clang) and the WASM_INDEX version is outputted by LLD when it's creating relocatable output. The we can cope with both the cases above, at the expense of even more code handling different types of relocations.

[ncw]

Simple rebase to fix conflicts. The two problems above remain.

[ncw]

Updated: split up the big review into six smaller ones.

The two big "problems" described above are now fixed. Problem #1 (stack pointer incompatible with --emit-relocs is fixed by using --relocatable for that test instead. Problem #2 (taking the address of a local function) is/was fixed in D42105.

[ncw]

test/wasm/archive.ll

32 ↗

(On Diff #129980)

Updated test expectations: Snuck in an test update here that's not strictly required...

test/wasm/data-layout.ll

48 ↗

(On Diff #129980)

Updated test expectations: Because the import has been removed (not part of the test assertions, sadly) this index has now gone down by one.

[ncw]

Updated:

• Simple rebase to fix conflict with __heap_base change

[ncw]

Updated:

• Got rid of change to stack-pointer.ll test. That's now split out into another review, #4b (D42237).

[ncw]

Updated:

• Simple rebase, fixing conflicts along the way

[ncw]

Updated:

• Now follows the symtab proposal! Or at least, it's first half of that work. The various indexes now match the exact values they will have after the symtab refactor, but we're still reading/writing the symbols using the imports+exports rather than the linking metadata section
• Next bits of symtab should follow in another review

[ncw]

Updated to remove conflicts in the hope it can be merged soonish... Getting the relocation indexes right is a prerequisite for the new symtab stuff.

[ncw]

Simple rebase on top of D42751, to allow those changes to be cleared out of the way

[ncw]

Rebased and renamed WasmIndex -> ElementIndex

[ruiu]

wasm/Writer.cpp

597–621

This is not related to this particular patch, but since I found this in this patch, I'll write the comment here. This piece of code is alarming because it uses hash tables. In general, in lld, I'd strongly recommend not to use hash tables or anything that is more complicated than the vector, because hash tables can make the linker noticeably slower.

If you really need to use a hash table, please look it up only once for a new piece of data, just like we do in the SymbolTable. In SymbolTable, we do lookup a new symbol name in the hash table only once to obtain a pointer, and after that, we access the symbols through the pointer. We never look up the symbol table more than once for the same data to minimize the cost of hash table lookup. I designed everything in lld that way, and that is I believe one of the big reasons why lld is so fast.

I'm not sure if it is applicable to this piece of code. If you have a small number of types and look the hash table only a few times, that's perhaps fine. But if each function have a type, and you need to insert/look up a hash table for each function, that's too much. If that's the case, could you revisit this code and redesign?

[sbc100]

wasm/Writer.cpp

597–621

Yes, I think we can eliminate lookupType completely once the symbol table changes land. We can just have the TypeIndex from each symbol as we call registerType.

[ncw]

wasm/Writer.cpp

597–621

In fact I remember making the same change in WasmObjectWriter (then reverting it), using a vector of bool to store whether something had been allocated rather than a DenseMap.

In LLD there are a few hash map lookups we've added I'm afraid :( In fact COMDAT is another one, I think I can rid of the hashmap LLD uses for that as well. That was my fault, before I realised hash maps were forbidden.

[ruiu]

wasm/Writer.cpp

597–621

It's not forbidden. :) For example SymbolTable is a valid use of the hash table -- I can't think of any way to avoid hash table in that class. But it is strongly discouraged because it sometimes has a significant performance impact.

[ncw]

Update: no functional changes, just fixed the compile after the "calculateTypes" change added a conflict

[sbc100]

test/wasm/init-fini.ll

153 ↗

(On Diff #132355)

This should be called "Symbol:" now, right? (at last with 2/2)

test/wasm/many-functions.ll

22 ↗

(On Diff #132355)

Ditto.

[ncw]

Rebased, attended to review comments/renaming

test/wasm/init-fini.ll

153 ↗

(On Diff #132355)

Renamed to "Symbol:"

test/wasm/many-functions.ll

22 ↗

(On Diff #132355)

Hmm, I've left it as just "Index" for the time being. We could rename it in a later commit.

Relocations have a Type/Index/Addend, which is consistent for the different types, whereas if we change it to "Symbol" it would then have to be different for TYPE relocations, which seems uglier to me (initially).

[ncw]

Update: folded D42539 into this patch

wasm/InputChunks.h

public:
   uint32_t getOutputIndex() const { return OutputIndex.getValue(); };
   bool hasOutputIndex() const { return OutputIndex.hasValue(); };
   void setOutputIndex(uint32_t Index) {
     assert(!hasOutputIndex());
     OutputIndex = Index;
   };
 
   const WasmSignature &Signature;
+  const WasmFunction &Function;
 
 protected:
   uint32_t getInputSectionOffset() const override {
     return Function.CodeSectionOffset;
   }
-  const WasmFunction &Function;
   llvm::Optional<uint32_t> OutputIndex;
 };
 
 } // namespace wasm
 } // namespace lld
 
 #endif // LLD_WASM_INPUT_CHUNKS_H

wasm/InputChunks.cpp

for (const WasmRelocation &Reloc : Relocations) {
     DEBUG(dbgs() << "reloc: type=" << Reloc.Type << " index=" << Reloc.Index
                  << " offset=" << Reloc.Offset
                  << " newOffset=" << NewReloc.Reloc.Offset << "\n");
 
     if (Config->EmitRelocs)
       NewReloc.NewIndex = File.calcNewIndex(Reloc);
 
     switch (Reloc.Type) {
+    case R_WEBASSEMBLY_TABLE_INDEX_I32:
+    case R_WEBASSEMBLY_TABLE_INDEX_SLEB:
+      NewReloc.Value = File.relocateTableIndex(Reloc.Index);
+      break;
     case R_WEBASSEMBLY_MEMORY_ADDR_SLEB:
     case R_WEBASSEMBLY_MEMORY_ADDR_I32:
     case R_WEBASSEMBLY_MEMORY_ADDR_LEB:
       NewReloc.Value = File.getRelocatedAddress(Reloc.Index) + Reloc.Addend;
       break;
     default:
       NewReloc.Value = File.calcNewIndex(Reloc);
       break;
     }
 
     OutRelocations.emplace_back(NewReloc);
   }
 }

wasm/InputFiles.h

public:
 
   void parse() override;
 
   // Returns the underlying wasm file.
   const WasmObjectFile *getWasmObj() const { return WasmObj.get(); }
 
   void dumpInfo() const;
 
-  uint32_t relocateFunctionIndex(uint32_t Original) const;
+  uint32_t relocateFunctionSymbolIndex(uint32_t Original) const;
   uint32_t getRelocatedAddress(uint32_t Index) const;
   uint32_t calcNewIndex(const WasmRelocation &Reloc) const;
 
   const WasmSection *CodeSection = nullptr;
   const WasmSection *DataSection = nullptr;
 
   std::vector<uint32_t> TypeMap;
   std::vector<InputSegment *> Segments;
   std::vector<InputFunction *> Functions;
 
-  ArrayRef<Symbol *> getSymbols() { return Symbols; }
-  ArrayRef<Symbol *> getTableSymbols() { return TableSymbols; }
+  ArrayRef<Symbol *> getSymbols() const { return Symbols; }
+  ArrayRef<Symbol *> getFunctionSymbols() const { return FunctionSymbols; }
 
 private:
   uint32_t relocateTypeIndex(uint32_t Original) const;
-  uint32_t relocateGlobalIndex(uint32_t Original) const;
+  uint32_t relocateGlobalSymbolIndex(uint32_t Original) const;
   uint32_t relocateTableIndex(uint32_t Original) const;
 
   Symbol *createDefined(const WasmSymbol &Sym, Symbol::Kind Kind,
                         const InputSegment *Segment = nullptr,
                         InputFunction *Function = nullptr,
                         uint32_t Address = UINT32_MAX);
   Symbol *createUndefined(const WasmSymbol &Sym, Symbol::Kind Kind,
                           const WasmSignature *Signature = nullptr);
   void initializeSymbols();
   InputSegment *getSegment(const WasmSymbol &WasmSym) const;
   const WasmSignature *getFunctionSig(const WasmSymbol &Sym) const;
   uint32_t getGlobalValue(const WasmSymbol &Sym) const;
   InputFunction *getFunction(const WasmSymbol &Sym) const;
   bool isExcludedByComdat(InputChunk *Chunk) const;
 
   // List of all symbols referenced or defined by this file.
   std::vector<Symbol *> Symbols;
 
-  // List of all function symbols indexed by the function index space
+  // List of all function symbols indexed by the function Symbol index space,
+  // that is, function imports followed by function exports (not the Wasm
+  // function definition index space, function imports followed by function
+  // bodies).
   std::vector<Symbol *> FunctionSymbols;
 
-  // List of all global symbols indexed by the global index space
+  // List of all global symbols indexed by the global Symbol index space,
+  // that is, global imports followed by global exports (not the Wasm
+  // global definition index space, global imports followed by global
+  // definitions).
   std::vector<Symbol *> GlobalSymbols;
 
-  // List of all indirect symbols indexed by table index space.
-  std::vector<Symbol *> TableSymbols;
-
   uint32_t NumGlobalImports = 0;
   uint32_t NumFunctionImports = 0;
+  uint32_t NumGlobalExports = 0;
+  uint32_t NumFunctionExports = 0;
   std::unique_ptr<WasmObjectFile> WasmObj;
 };
 
 // Opens a given file.
 llvm::Optional<MemoryBufferRef> readFile(StringRef Path);
 
 } // namespace wasm
 
 std::string toString(const wasm::InputFile *File);
 
 } // namespace lld
 
 #endif

wasm/InputFiles.cpp

Optional<MemoryBufferRef> lld::wasm::readFile(StringRef Path) {
   return MBRef;
 }
 
 void ObjFile::dumpInfo() const {
   log("info for: " + getName() + "\n" +
       "      Total Functions : " + Twine(FunctionSymbols.size()) + "\n" +
       "        Total Globals : " + Twine(GlobalSymbols.size()) + "\n" +
       "     Function Imports : " + Twine(NumFunctionImports) + "\n" +
-      "       Global Imports : " + Twine(NumGlobalImports) + "\n" +
-      "        Table Entries : " + Twine(TableSymbols.size()) + "\n");
+      "       Global Imports : " + Twine(NumGlobalImports) + "\n");
 }
 
 uint32_t ObjFile::getRelocatedAddress(uint32_t GlobalIndex) const {
   return GlobalSymbols[GlobalIndex]->getVirtualAddress();
 }
 
-uint32_t ObjFile::relocateFunctionIndex(uint32_t Original) const {
+uint32_t ObjFile::relocateTypeIndex(uint32_t Original) const {
+  return TypeMap[Original];
+}
+
+uint32_t ObjFile::relocateFunctionSymbolIndex(uint32_t Original) const {
   Symbol *Sym = FunctionSymbols[Original];
   uint32_t Index = Sym->getOutputIndex();
-  DEBUG(dbgs() << "relocateFunctionIndex: " << toString(*Sym) << ": "
+  DEBUG(dbgs() << "relocateFunctionSymbolIndex: " << toString(*Sym) << ": "
                << Original << " -> " << Index << "\n");
   return Index;
 }
 
-uint32_t ObjFile::relocateTypeIndex(uint32_t Original) const {
-  return TypeMap[Original];
+uint32_t ObjFile::relocateGlobalSymbolIndex(uint32_t Original) const {
+  Symbol *Sym = GlobalSymbols[Original];
+  uint32_t Index = Sym->hasOutputIndex() ? Sym->getOutputIndex() : 0;
+  DEBUG(dbgs() << "relocateGlobalSymbolIndex: " << toString(*Sym) << ": " << Original
+               << " -> " << Index << "\n");
+  return Index;
 }
 
 uint32_t ObjFile::relocateTableIndex(uint32_t Original) const {
-  Symbol *Sym = TableSymbols[Original];
+  Symbol *Sym = FunctionSymbols[Original];
   uint32_t Index = Sym->hasTableIndex() ? Sym->getTableIndex() : 0;
   DEBUG(dbgs() << "relocateTableIndex: " << toString(*Sym) << ": " << Original
                << " -> " << Index << "\n");
   return Index;
 }
 
-uint32_t ObjFile::relocateGlobalIndex(uint32_t Original) const {
-  Symbol *Sym = GlobalSymbols[Original];
-  uint32_t Index = Sym->hasOutputIndex() ? Sym->getOutputIndex() : 0;
-  DEBUG(dbgs() << "relocateGlobalIndex: " << toString(*Sym) << ": " << Original
-               << " -> " << Index << "\n");
-  return Index;
-}
-
 // Relocations contain an index into the function, global or table index
 // space of the input file.  This function takes a relocation and returns the
 // relocated index (i.e. translates from the input index space to the output
 // index space).
 uint32_t ObjFile::calcNewIndex(const WasmRelocation &Reloc) const {
   switch (Reloc.Type) {
   case R_WEBASSEMBLY_TYPE_INDEX_LEB:
     return relocateTypeIndex(Reloc.Index);
   case R_WEBASSEMBLY_FUNCTION_INDEX_LEB:
-    return relocateFunctionIndex(Reloc.Index);
   case R_WEBASSEMBLY_TABLE_INDEX_I32:
   case R_WEBASSEMBLY_TABLE_INDEX_SLEB:
-    return relocateTableIndex(Reloc.Index);
+    return relocateFunctionSymbolIndex(Reloc.Index);
   case R_WEBASSEMBLY_GLOBAL_INDEX_LEB:
   case R_WEBASSEMBLY_MEMORY_ADDR_LEB:
   case R_WEBASSEMBLY_MEMORY_ADDR_SLEB:
   case R_WEBASSEMBLY_MEMORY_ADDR_I32:
-    return relocateGlobalIndex(Reloc.Index);
+    return relocateGlobalSymbolIndex(Reloc.Index);
   default:
     llvm_unreachable("unknown relocation type");
   }
 }
 
 void ObjFile::parse() {
   // Parse a memory buffer as a wasm file.
   DEBUG(dbgs() << "Parsing object: " << toString(this) << "\n");
InputSegment *ObjFile::getSegment(const WasmSymbol &WasmSym) const {
   }
   error("symbol not found in any segment: " + WasmSym.Name);
   return nullptr;
 }
 
 // Get the value stored in the wasm global represented by this symbol.
 // This represents the virtual address of the symbol in the input file.
 uint32_t ObjFile::getGlobalValue(const WasmSymbol &Sym) const {
+  assert(Sym.WasmIndex >= getWasmObj()->getNumImportedGlobals());
   const WasmGlobal &Global =
-      getWasmObj()->globals()[Sym.ElementIndex - NumGlobalImports];
+      getWasmObj()->globals()[Sym.WasmIndex - NumGlobalImports];
   assert(Global.Type == llvm::wasm::WASM_TYPE_I32);
   return Global.InitExpr.Value.Int32;
 }
 
 // Get the signature for a given function symbol, either by looking
 // it up in function sections (for defined functions), of the imports section
 // (for imported functions).
 const WasmSignature *ObjFile::getFunctionSig(const WasmSymbol &Sym) const {
   DEBUG(dbgs() << "getFunctionSig: " << Sym.Name << "\n");
   return &WasmObj->types()[Sym.FunctionType];
 }
 
 InputFunction *ObjFile::getFunction(const WasmSymbol &Sym) const {
-  uint32_t FunctionIndex = Sym.ElementIndex - NumFunctionImports;
+  assert(Sym.WasmIndex >= NumFunctionImports);
+  uint32_t FunctionIndex = Sym.WasmIndex - NumFunctionImports;
   return Functions[FunctionIndex];
 }
 
 bool ObjFile::isExcludedByComdat(InputChunk *Chunk) const {
   StringRef Comdat = Chunk->getComdat();
   return !Comdat.empty() && Symtab->findComdat(Comdat) != this;
 }
 
 void ObjFile::initializeSymbols() {
   Symbols.reserve(WasmObj->getNumberOfSymbols());
 
-  for (const WasmImport &Import : WasmObj->imports()) {
-    switch (Import.Kind) {
-    case WASM_EXTERNAL_FUNCTION:
-      ++NumFunctionImports;
-      break;
-    case WASM_EXTERNAL_GLOBAL:
-      ++NumGlobalImports;
-      break;
-    }
-  }
+  NumFunctionImports = WasmObj->getNumImportedFunctions();
+  NumGlobalImports = WasmObj->getNumImportedGlobals();
+  NumFunctionExports = WasmObj->getNumExportedFunctions();
+  NumGlobalExports = WasmObj->getNumExportedGlobals();
 
   ArrayRef<WasmFunction> Funcs = WasmObj->functions();
   ArrayRef<uint32_t> FuncTypes = WasmObj->functionTypes();
   ArrayRef<WasmSignature> Types = WasmObj->types();
   ArrayRef<WasmGlobal> Globals = WasmObj->globals();
 
   for (const auto &C : WasmObj->comdats())
     Symtab->addComdat(C, this);
case WasmSymbol::SymbolType::GLOBAL_EXPORT: {
       } else {
         Segment->Discarded = true;
         // fall through:
       }
     }
     case WasmSymbol::SymbolType::GLOBAL_IMPORT:
       S = createUndefined(WasmSym, Symbol::Kind::UndefinedGlobalKind);
       break;
-    case WasmSymbol::SymbolType::DEBUG_FUNCTION_NAME:
-      // These are for debugging only, no need to create linker symbols for them
-      continue;
     }
 
     Symbols.push_back(S);
     if (WasmSym.isFunction()) {
-      DEBUG(dbgs() << "Function: " << WasmSym.ElementIndex << " -> "
+      DEBUG(dbgs() << "Function: " << WasmSym.SymbolIndex << " -> "
                    << toString(*S) << "\n");
-      FunctionSymbols[WasmSym.ElementIndex] = S;
-      if (WasmSym.HasAltIndex)
-        FunctionSymbols[WasmSym.AltIndex] = S;
+      FunctionSymbols[WasmSym.SymbolIndex] = S;
+      InputFunction &Func = *Functions[WasmSym.WasmIndex - NumFunctionImports];
     } else {
-      DEBUG(dbgs() << "Global: " << WasmSym.ElementIndex << " -> "
+      DEBUG(dbgs() << "Global: " << WasmSym.SymbolIndex << " -> "
                    << toString(*S) << "\n");
-      GlobalSymbols[WasmSym.ElementIndex] = S;
-      if (WasmSym.HasAltIndex)
-        GlobalSymbols[WasmSym.AltIndex] = S;
+      GlobalSymbols[WasmSym.SymbolIndex] = S;
     }
   }
 
   DEBUG(for (size_t I = 0; I < FunctionSymbols.size(); ++I)
             assert(FunctionSymbols[I] != nullptr);
         for (size_t I = 0; I < GlobalSymbols.size(); ++I)
             assert(GlobalSymbols[I] != nullptr););
 
-  // Populate `TableSymbols` with all symbols that are called indirectly
-  uint32_t SegmentCount = WasmObj->elements().size();
-  if (SegmentCount) {
-    if (SegmentCount > 1)
-      fatal(getName() + ": contains more than one element segment");
-    const WasmElemSegment &Segment = WasmObj->elements()[0];
-    if (Segment.Offset.Opcode != WASM_OPCODE_I32_CONST)
-      fatal(getName() + ": unsupported element segment");
-    if (Segment.TableIndex != 0)
-      fatal(getName() + ": unsupported table index in elem segment");
-    if (Segment.Offset.Value.Int32 != 0)
-      fatal(getName() + ": unsupported element segment offset");
-    TableSymbols.reserve(Segment.Functions.size());
-    for (uint64_t FunctionIndex : Segment.Functions)
-      TableSymbols.push_back(FunctionSymbols[FunctionIndex]);
-  }
-
-  DEBUG(dbgs() << "TableSymbols: " << TableSymbols.size() << "\n");
   DEBUG(dbgs() << "Functions   : " << FunctionSymbols.size() << "\n");
   DEBUG(dbgs() << "Globals     : " << GlobalSymbols.size() << "\n");
 }
 
 Symbol *ObjFile::createUndefined(const WasmSymbol &Sym, Symbol::Kind Kind,
                                  const WasmSignature *Signature) {
   return Symtab->addUndefined(Sym.Name, Kind, Sym.Flags, this, Signature);
 }

wasm/Symbols.h

enum Kind {
     UndefinedFunctionKind,
     UndefinedGlobalKind,
 
     LastDefinedKind = DefinedGlobalKind,
     InvalidKind,
   };
 
   Symbol(StringRef Name, uint32_t Flags)
-      : WrittenToSymtab(0), WrittenToNameSec(0), Flags(Flags), Name(Name) {}
+      : Flags(Flags), Name(Name) {}
 
   Kind getKind() const { return SymbolKind; }
 
   bool isLazy() const { return SymbolKind == LazyKind; }
   bool isDefined() const { return SymbolKind <= LastDefinedKind; }
   bool isUndefined() const {
     return SymbolKind == UndefinedGlobalKind ||
            SymbolKind == UndefinedFunctionKind;
public:
   const WasmSignature &getFunctionType() const;
   void setFunctionType(const WasmSignature *Type);
 
   uint32_t getOutputIndex() const;
 
   // Returns true if an output index has been set for this symbol
   bool hasOutputIndex() const;
 
-  // Set the output index of the symbol (in the function or global index
-  // space of the output object.
+  // Set the output index of the symbol, in the function or global Wasm
+  // index space of the output object - that is, for defined symbols only,
+  // its position in the list of defined function bodies / global decls.
   void setOutputIndex(uint32_t Index);
 
   uint32_t getTableIndex() const { return TableIndex.getValue(); }
 
   // Returns true if a table index has been set for this symbol
   bool hasTableIndex() const { return TableIndex.hasValue(); }
 
   // Set the table index of the symbol
   void setTableIndex(uint32_t Index);
 
   // Returns the virtual address of a defined global.
   // Only works for globals, not functions.
   uint32_t getVirtualAddress() const;
 
   void setVirtualAddress(uint32_t VA);
 
   void update(Kind K, InputFile *F = nullptr, uint32_t Flags = 0,
               const InputSegment *Segment = nullptr,
               const InputFunction *Function = nullptr,
               uint32_t Address = UINT32_MAX);
 
   void setArchiveSymbol(const Archive::Symbol &Sym) { ArchiveSymbol = Sym; }
   const Archive::Symbol &getArchiveSymbol() { return ArchiveSymbol; }
 
-  // This bit is used by Writer::writeNameSection() to prevent
-  // symbols from being written to the symbol table more than once.
-  unsigned WrittenToSymtab : 1;
-  unsigned WrittenToNameSec : 1;
-
 protected:
   uint32_t Flags;
   uint32_t VirtualAddress = 0;
 
   StringRef Name;
   Archive::Symbol ArchiveSymbol = {nullptr, 0, 0};
   Kind SymbolKind = InvalidKind;
   InputFile *File = nullptr;

wasm/Writer.cpp

 
 private:
   void openFile();
 
   uint32_t lookupType(const WasmSignature &Sig);
   uint32_t registerType(const WasmSignature &Sig);
   void assignIndexes();
   void calculateImports();
-  void calculateOffsets();
   void calculateTypes();
   void createOutputSegments();
   void layoutMemory();
   void createHeader();
   void createSections();
   SyntheticSection *createSyntheticSection(uint32_t Type,
                                            StringRef Name = "");
 
private:
   void createNameSection();
 
   void writeHeader();
   void writeSections();
 
   uint64_t FileSize = 0;
   uint32_t DataSize = 0;
   uint32_t NumMemoryPages = 0;
-  uint32_t InitialTableOffset = 0;
+  uint32_t InitialTableOffset = 1;
 
   std::vector<const WasmSignature *> Types;
   DenseMap<WasmSignature, int32_t, WasmSignatureDenseMapInfo> TypeIndices;
   std::vector<const Symbol *> ImportedFunctions;
   std::vector<const Symbol *> ImportedGlobals;
   std::vector<const Symbol *> DefinedGlobals;
   std::vector<InputFunction *> DefinedFunctions;
   std::vector<const Symbol *> IndirectFunctions;
void Writer::createLinkingSection() {
   }
 
   std::vector<WasmInitFunc> InitFunctions;
   for (ObjFile *File : Symtab->ObjectFiles) {
     const WasmLinkingData &L = File->getWasmObj()->linkingData();
     InitFunctions.reserve(InitFunctions.size() + L.InitFunctions.size());
     for (const WasmInitFunc &F : L.InitFunctions)
       InitFunctions.emplace_back(WasmInitFunc{
-          F.Priority, File->relocateFunctionIndex(F.FunctionIndex)});
+          F.Priority, File->relocateFunctionSymbolIndex(F.FunctionIndex)});
   }
 
   if (!InitFunctions.empty()) {
     SubSection SubSection(WASM_INIT_FUNCS);
     writeUleb128(SubSection.getStream(), InitFunctions.size(),
-                 "num init functionsw");
+                 "num init functions");
     for (const WasmInitFunc &F : InitFunctions) {
       writeUleb128(SubSection.getStream(), F.Priority, "priority");
       writeUleb128(SubSection.getStream(), F.FunctionIndex, "function index");
     }
     SubSection.finalizeContents();
     SubSection.writeToStream(OS);
   }
 
if (!Comdats.empty()) {
     }
     SubSection.finalizeContents();
     SubSection.writeToStream(OS);
   }
 }
 
 // Create the custom "name" section containing debug symbol names.
 void Writer::createNameSection() {
-  // Create an array of all function sorted by function index space
-  std::vector<const Symbol *> Names;
-
-  for (ObjFile *File : Symtab->ObjectFiles) {
-    Names.reserve(Names.size() + File->getSymbols().size());
-    for (Symbol *S : File->getSymbols()) {
-      if (!S->isFunction() || S->isWeak() || S->WrittenToNameSec)
-        continue;
-      S->WrittenToNameSec = true;
-      Names.emplace_back(S);
-    }
-  }
+  unsigned Names = 0;
+  for (const InputFunction *F : DefinedFunctions)
+    if (!F->Function.Name.empty())
+      ++Names;
 
   SyntheticSection *Section = createSyntheticSection(WASM_SEC_CUSTOM, "name");
 
-  std::sort(Names.begin(), Names.end(), [](const Symbol *A, const Symbol *B) {
-    return A->getOutputIndex() < B->getOutputIndex();
-  });
-
   SubSection FunctionSubsection(WASM_NAMES_FUNCTION);
   raw_ostream &OS = FunctionSubsection.getStream();
-  writeUleb128(OS, Names.size(), "name count");
+  writeUleb128(OS, Names, "name count");
 
-  // We have to iterate through the inputs twice so that all the imports
-  // appear first before any of the local function names.
-  for (const Symbol *S : Names) {
-    writeUleb128(OS, S->getOutputIndex(), "func index");
-    writeStr(OS, S->getName(), "symbol name");
+  for (const InputFunction *F : DefinedFunctions) {
+    if (!F->Function.Name.empty()) {
+      writeUleb128(OS, F->getOutputIndex(), "func index");
+      writeStr(OS, F->Function.Name, "symbol name");
+    }
   }
 
   FunctionSubsection.finalizeContents();
   FunctionSubsection.writeToStream(Section->getStream());
 }
 
 void Writer::writeHeader() {
   memcpy(Buffer->getBufferStart(), Header.data(), Header.size());
if (Sym->isFunction()) {
       ImportedFunctions.push_back(Sym);
     } else {
       Sym->setOutputIndex(ImportedGlobals.size());
       ImportedGlobals.push_back(Sym);
     }
   }
 }
 
 uint32_t Writer::lookupType(const WasmSignature &Sig) {
   auto It = TypeIndices.find(Sig);
   if (It == TypeIndices.end()) {
     error("type not found: " + toString(Sig));
     return 0;
   }
   return It->second;
 }
 
 uint32_t Writer::registerType(const WasmSignature &Sig) {
   auto Pair = TypeIndices.insert(std::make_pair(Sig, Types.size()));
   if (Pair.second) {
     DEBUG(dbgs() << "type " << toString(Sig) << "\n");
     Types.push_back(&Sig);
   }
   return Pair.first->second;
 }
 
 void Writer::calculateTypes() {
   for (ObjFile *File : Symtab->ObjectFiles) {
     File->TypeMap.reserve(File->getWasmObj()->types().size());
     for (const WasmSignature &Sig : File->getWasmObj()->types())
       File->TypeMap.push_back(registerType(Sig));
   }
 }
 
 void Writer::assignIndexes() {
   uint32_t GlobalIndex = ImportedGlobals.size();
   uint32_t FunctionIndex = ImportedFunctions.size();
 
   if (Config->StackPointerSymbol) {
     DefinedGlobals.emplace_back(Config->StackPointerSymbol);
     Config->StackPointerSymbol->setOutputIndex(GlobalIndex++);
for (InputFunction *Func : File->Functions) {
         continue;
       DefinedFunctions.emplace_back(Func);
       Func->setOutputIndex(FunctionIndex++);
     }
   }
 
   for (ObjFile *File : Symtab->ObjectFiles) {
     DEBUG(dbgs() << "Table Indexes: " << File->getName() << "\n");
-    for (Symbol *Sym : File->getTableSymbols()) {
+    auto HandleRelocs = [&](ArrayRef<WasmRelocation> Relocations) {
+        for (const WasmRelocation& Reloc : Relocations) {
+          if (Reloc.Type != R_WEBASSEMBLY_TABLE_INDEX_I32 &&
+              Reloc.Type != R_WEBASSEMBLY_TABLE_INDEX_SLEB)
+            continue;
+          Symbol *Sym = File->getFunctionSymbols()[Reloc.Index];
           if (Sym->hasTableIndex() || !Sym->hasOutputIndex())
             continue;
           Sym->setTableIndex(TableIndex++);
           IndirectFunctions.emplace_back(Sym);
         }
+    };
+    for (InputFunction* Func : File->Functions) {
+      if (Func->Discarded)
+        continue;
+      HandleRelocs(Func->Relocations);
+    }
+    for (InputSegment* Seg : File->Segments) {
+      if (Seg->Discarded)
+        continue;
+      HandleRelocs(Seg->Relocations);
+    }
   }
 }
 
 static StringRef getOutputDataSegmentName(StringRef Name) {
   if (Config->Relocatable)
     return Name;
 
   for (StringRef V :
for (InputSegment *Segment : File->Segments) {
       }
       S->addInputSegment(Segment);
       DEBUG(dbgs() << "added data: " << Name << ": " << S->Size << "\n");
     }
   }
 }
 
 void Writer::run() {
-  if (!Config->Relocatable)
-    InitialTableOffset = 1;
-
   log("-- calculateTypes");
   calculateTypes();
   log("-- calculateImports");
   calculateImports();
   log("-- assignIndexes");
   assignIndexes();
 
   if (errorHandler().Verbose) {