[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

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

698–726

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

698–726

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

698–726

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

698–726

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

151

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

151

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

test/wasm/archive.ll

 }
 
 ; Verify that multually dependant object files in an archive is handled
 ; correctly.
 
 ; CHECK:      00000003 T _start
 ; CHECK-NEXT: 00000001 T bar
 ; CHECK-NEXT: 00000002 T foo
+; CHECK-NEXT:          U missing_func
 
 ; Verify that symbols from unused objects don't appear in the symbol table
 ; CHECK-NOT: hello
 
 ; Specifying the same archive twice is allowed.
 ; RUN: lld -flavor wasm %t.a %t.a %t.o -o %t.wasm

test/wasm/init-fini.ll

 
 
 ; RUN: lld -flavor wasm -r %t.o %t.global-ctor-dtor.o -o %t.reloc.wasm
 ; RUN: obj2yaml %t.reloc.wasm | FileCheck -check-prefix=RELOC %s
 
 ; RELOC:          Name:            linking
 ; RELOC-NEXT:     DataSize:        0
 ; RELOC-NEXT:     SymbolInfo:      
-; RELOC-NEXT:       - Name:            __dso_handle
-; RELOC-NEXT:         Flags:           [ BINDING_WEAK, VISIBILITY_HIDDEN ]
 ; RELOC-NEXT:       - Name:            func1
 ; RELOC-NEXT:         Flags:           [ VISIBILITY_HIDDEN ]
 ; RELOC-NEXT:       - Name:            func2
 ; RELOC-NEXT:         Flags:           [ VISIBILITY_HIDDEN ]
 ; RELOC-NEXT:       - Name:            func3
 ; RELOC-NEXT:         Flags:           [ VISIBILITY_HIDDEN ]
 ; RELOC-NEXT:       - Name:            func4
 ; RELOC-NEXT:         Flags:           [ VISIBILITY_HIDDEN ]

 ; RELOC-NEXT:       - Name:            .Lcall_dtors.202
 ; RELOC-NEXT:         Flags:           [ BINDING_LOCAL ]
 ; RELOC-NEXT:       - Name:            .Lregister_call_dtors.202
 ; RELOC-NEXT:         Flags:           [ BINDING_LOCAL ]
 ; RELOC-NEXT:       - Name:            .Lcall_dtors.2002
 ; RELOC-NEXT:         Flags:           [ BINDING_LOCAL ]
 ; RELOC-NEXT:       - Name:            .Lregister_call_dtors.2002
 ; RELOC-NEXT:         Flags:           [ BINDING_LOCAL ]
+; RELOC-NEXT:       - Name:            __dso_handle
+; RELOC-NEXT:         Flags:           [ BINDING_WEAK, VISIBILITY_HIDDEN ]
 ; RELOC-NEXT:     InitFunctions:
 ; RELOC-NEXT:       - Priority:        101
 ; RELOC-NEXT:         FunctionIndex:   0
 ; RELOC-NEXT:       - Priority:        101
 ; RELOC-NEXT:         FunctionIndex:   1
 ; RELOC-NEXT:       - Priority:        101
 ; RELOC-NEXT:         FunctionIndex:   7
 ; RELOC-NEXT:       - Priority:        101
 ; RELOC-NEXT:         FunctionIndex:   11
 ; RELOC-NEXT:       - Priority:        101
 ; RELOC-NEXT:         FunctionIndex:   14

test/wasm/weak-alias.ll

 ; CHECK-NEXT:   - Type:            EXPORT
 ; CHECK-NEXT:     Exports:
 ; CHECK-NEXT:       - Name:            memory
 ; CHECK-NEXT:         Kind:            MEMORY
 ; CHECK-NEXT:         Index:           0
 ; CHECK-NEXT:       - Name:            _start
 ; CHECK-NEXT:         Kind:            FUNCTION
 ; CHECK-NEXT:         Index:           0
-; CHECK-NEXT:       - Name:            alias_fn
-; CHECK-NEXT:         Kind:            FUNCTION
-; CHECK-NEXT:         Index:           1
 ; CHECK-NEXT:       - Name:            direct_fn
 ; CHECK-NEXT:         Kind:            FUNCTION
 ; CHECK-NEXT:         Index:           1
 ; CHECK-NEXT:       - Name:            call_direct
 ; CHECK-NEXT:         Kind:            FUNCTION
 ; CHECK-NEXT:         Index:           2
 ; CHECK-NEXT:       - Name:            call_alias
 ; CHECK-NEXT:         Kind:            FUNCTION
 ; CHECK-NEXT:         Index:           3
 ; CHECK-NEXT:       - Name:            call_alias_ptr
 ; CHECK-NEXT:         Kind:            FUNCTION
 ; CHECK-NEXT:         Index:           4
 ; CHECK-NEXT:       - Name:            call_direct_ptr
 ; CHECK-NEXT:         Kind:            FUNCTION
 ; CHECK-NEXT:         Index:           5
+; CHECK-NEXT:       - Name:            alias_fn
+; CHECK-NEXT:         Kind:            FUNCTION
+; CHECK-NEXT:         Index:           1
 ; CHECK-NEXT:       - Name:            __heap_base
 ; CHECK-NEXT:         Kind:            GLOBAL
 ; CHECK-NEXT:         Index:           1
 ; CHECK-NEXT:   - Type:            ELEM
 ; CHECK-NEXT:     Segments:        
 ; CHECK-NEXT:       - Offset:          
 ; CHECK-NEXT:           Opcode:          I32_CONST
 ; CHECK-NEXT:           Value:           1

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 calcNewIndex(const WasmRelocation &Reloc) const;
   uint32_t calcNewValue(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() const { return Symbols; }
   ArrayRef<Symbol *> getFunctionSymbols() const { return FunctionSymbols; }
 
 private:
   uint32_t relocateVirtualAddress(uint32_t Index) const;
   uint32_t relocateTypeIndex(uint32_t Original) const;
-  uint32_t relocateGlobalIndex(uint32_t Original) const;
+  uint32_t relocateFunctionSymbolIndex(uint32_t Original) const;
+  uint32_t relocateGlobalSymbolIndex(uint32_t Original) const;
+  uint32_t relocateFunctionWasmIndex(uint32_t Original) const;
+  uint32_t relocateGlobalWasmIndex(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;
 
   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

log("info for: " + getName() + "\n" +
       "     Function Imports : " + Twine(NumFunctionImports) + "\n" +
       "       Global Imports : " + Twine(NumGlobalImports) + "\n");
 }
 
 uint32_t ObjFile::relocateVirtualAddress(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) << ": "
+  uint32_t Index = Sym->getOutputSymbolIndex();
+  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->getOutputSymbolIndex();
+  DEBUG(dbgs() << "relocateGlobalSymbolIndex: " << toString(*Sym) << ": " << Original
+               << " -> " << Index << "\n");
+  return Index;
 }
 
-uint32_t ObjFile::relocateTableIndex(uint32_t Original) const {
+uint32_t ObjFile::relocateFunctionWasmIndex(uint32_t Original) const {
   Symbol *Sym = FunctionSymbols[Original];
-  uint32_t Index = Sym->hasTableIndex() ? Sym->getTableIndex() : 0;
-  DEBUG(dbgs() << "relocateTableIndex: " << toString(*Sym) << ": " << Original
-               << " -> " << Index << "\n");
+  uint32_t Index = Sym->hasOutputIndex() ? Sym->getOutputIndex() : 0;
+  DEBUG(dbgs() << "relocateFunctionWasmIndex: " << toString(*Sym) << ": "
+               << Original << " -> " << Index << "\n");
   return Index;
 }
 
-uint32_t ObjFile::relocateGlobalIndex(uint32_t Original) const {
+uint32_t ObjFile::relocateGlobalWasmIndex(uint32_t Original) const {
   Symbol *Sym = GlobalSymbols[Original];
-  uint32_t Index = Sym->hasOutputIndex() ? Sym->getOutputIndex() : 0;
-  DEBUG(dbgs() << "relocateGlobalIndex: " << toString(*Sym) << ": " << Original
+  uint32_t Index = Sym->hasTableIndex() ? Sym->getOutputIndex() : 0;
+  DEBUG(dbgs() << "relocateGlobalWasmIndex: " << toString(*Sym) << ": " << Original
+               << " -> " << Index << "\n");
+  return Index;
+}
+
+uint32_t ObjFile::relocateTableIndex(uint32_t Original) const {
+  Symbol *Sym = FunctionSymbols[Original];
+  // The null case is possible, if you take the address of a weak function
+  // that's simply not supplied.
+  uint32_t Index = Sym->hasTableIndex() ? Sym->getTableIndex() : 0;
+  DEBUG(dbgs() << "relocateTableIndex: " << 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:
   case R_WEBASSEMBLY_TABLE_INDEX_I32:
   case R_WEBASSEMBLY_TABLE_INDEX_SLEB:
-    return relocateFunctionIndex(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");
   }
 }
 
 // Translate from the relocation's index into the final linked output value.
 uint32_t ObjFile::calcNewValue(const WasmRelocation &Reloc) const {
   switch (Reloc.Type) {
   case R_WEBASSEMBLY_TABLE_INDEX_I32:
   case R_WEBASSEMBLY_TABLE_INDEX_SLEB:
     return relocateTableIndex(Reloc.Index);
   case R_WEBASSEMBLY_MEMORY_ADDR_SLEB:
   case R_WEBASSEMBLY_MEMORY_ADDR_I32:
   case R_WEBASSEMBLY_MEMORY_ADDR_LEB:
     return relocateVirtualAddress(Reloc.Index) + Reloc.Addend;
   case R_WEBASSEMBLY_TYPE_INDEX_LEB:
     return relocateTypeIndex(Reloc.Index);
   case R_WEBASSEMBLY_FUNCTION_INDEX_LEB:
-    return relocateFunctionIndex(Reloc.Index);
+    return relocateFunctionWasmIndex(Reloc.Index);
   case R_WEBASSEMBLY_GLOBAL_INDEX_LEB:
-    return relocateGlobalIndex(Reloc.Index);
+    return relocateGlobalWasmIndex(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();
 
   FunctionSymbols.resize(NumFunctionImports + WasmObj->functions().size());
   GlobalSymbols.resize(NumGlobalImports + WasmObj->globals().size());
 
   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);
 
-  FunctionSymbols.resize(NumFunctionImports + Funcs.size());
-  GlobalSymbols.resize(NumGlobalImports + Globals.size());
+  FunctionSymbols.resize(NumFunctionImports + NumFunctionExports);
+  GlobalSymbols.resize(NumGlobalImports + NumGlobalExports);
 
   for (const WasmSegment &S : WasmObj->dataSegments()) {
     InputSegment *Seg = make<InputSegment>(S, this);
     Seg->copyRelocations(*DataSection);
     Segments.emplace_back(Seg);
   }
 
   for (size_t I = 0; I < Funcs.size(); ++I) {
for (const SymbolRef &Sym : WasmObj->symbols()) {
     }
     case WasmSymbol::SymbolType::GLOBAL_IMPORT:
       S = createUndefined(WasmSym, Symbol::Kind::UndefinedGlobalKind);
       break;
     }
 
     Symbols.push_back(S);
     if (WasmSym.isFunction()) {
-      FunctionSymbols[WasmSym.ElementIndex] = S;
-      if (WasmSym.HasAltIndex)
-        FunctionSymbols[WasmSym.AltIndex] = S;
+      FunctionSymbols[WasmSym.SymbolIndex] = S;
     } else {
-      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););
 

wasm/Symbols.h

public:
   void setFunctionType(const WasmSignature *Type);
   void setHidden(bool IsHidden);
 
   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);
 
+  // Get/set the output symbol index, in the function or global Symbol index
+  // space - that is, the position in the list of imports+exports.  This is
+  // only used for relocatable output.
+  uint32_t getOutputSymbolIndex() const;
+  void setOutputSymbolIndex(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);
 
protected:
 
   StringRef Name;
   Archive::Symbol ArchiveSymbol = {nullptr, 0, 0};
   Kind SymbolKind = InvalidKind;
   InputFile *File = nullptr;
   const InputSegment *Segment = nullptr;
   InputFunction *Function = nullptr;
   llvm::Optional<uint32_t> OutputIndex;
+  llvm::Optional<uint32_t> OutputSymbolIndex;
   llvm::Optional<uint32_t> TableIndex;
   const WasmSignature *FunctionType = nullptr;
 };
 
 } // namespace wasm
 
 // Returns a symbol name for an error message.
 std::string toString(const wasm::Symbol &Sym);
 std::string toString(wasm::Symbol::Kind Kind);
 
 } // namespace lld
 
 #endif

wasm/Symbols.cpp

 }
 
 uint32_t Symbol::getOutputIndex() const {
   if (Function)
     return Function->getOutputIndex();
   return OutputIndex.getValue();
 }
 
+uint32_t Symbol::getOutputSymbolIndex() const {
+  return OutputSymbolIndex.getValue();
+}
+
 void Symbol::setVirtualAddress(uint32_t Value) {
   DEBUG(dbgs() << "setVirtualAddress " << Name << " -> " << Value << "\n");
   assert(isGlobal());
   VirtualAddress = Value;
 }
 
 void Symbol::setOutputIndex(uint32_t Index) {
   DEBUG(dbgs() << "setOutputIndex " << Name << " -> " << Index << "\n");
   assert(!Function);
   assert(!OutputIndex.hasValue());
   OutputIndex = Index;
 }
 
+void Symbol::setOutputSymbolIndex(uint32_t Index) {
+  DEBUG(dbgs() << "setOutputSymbolIndex " << Name << " -> " << Index << "\n");
+  assert(!OutputSymbolIndex.hasValue());
+  OutputSymbolIndex = Index;
+}
+
 void Symbol::setTableIndex(uint32_t Index) {
   DEBUG(dbgs() << "setTableIndex " << Name << " -> " << Index << "\n");
   assert(!TableIndex.hasValue());
   TableIndex = Index;
 }
 
 void Symbol::update(Kind K, InputFile *F, uint32_t Flags_,
                     const InputSegment *Seg, InputFunction *Func,

wasm/Writer.cpp

 };
 
 // A Wasm export to be written into the export section.
 struct WasmExportEntry {
   const Symbol *Sym;
   StringRef FieldName; // may not match the Symbol name
 };
 
+// An init entry to be written to either the synthentic init func or the
+// linking metadata.
+struct WasmInitEntry {
+  const Symbol *Symbol;
+  uint32_t Priority;
+};
+
 // The writer writes a SymbolTable result to a file.
 class Writer {
 public:
   void run();
 
 private:
   void openFile();
 
private:
   uint32_t DataSize = 0;
   uint32_t NumMemoryPages = 0;
 
   std::vector<const WasmSignature *> Types;
   DenseMap<WasmSignature, int32_t, WasmSignatureDenseMapInfo> TypeIndices;
   std::vector<const Symbol *> ImportedFunctions;
   std::vector<const Symbol *> ImportedGlobals;
   std::vector<WasmExportEntry> ExportedSymbols;
-  std::vector<const Symbol *> DefinedGlobals;
+  std::vector<Symbol *> DefinedGlobals;
   std::vector<InputFunction *> DefinedFunctions;
   std::vector<const Symbol *> IndirectFunctions;
-  std::vector<WasmInitFunc> InitFunctions;
+  std::vector<WasmInitEntry> InitFunctions;
 
   // Elements that are used to construct the final output
   std::string Header;
   std::vector<OutputSection *> OutputSections;
 
   std::unique_ptr<FileOutputBuffer> Buffer;
   std::unique_ptr<SyntheticFunction> CtorFunction;
   std::string CtorFunctionBody;
if (Segments.size()) {
     SubSection.finalizeContents();
     SubSection.writeToStream(OS);
   }
 
   if (!InitFunctions.empty()) {
     SubSection SubSection(WASM_INIT_FUNCS);
     writeUleb128(SubSection.getStream(), InitFunctions.size(),
                  "num init functions");
-    for (const WasmInitFunc &F : InitFunctions) {
+    for (const WasmInitEntry &F : InitFunctions) {
       writeUleb128(SubSection.getStream(), F.Priority, "priority");
-      writeUleb128(SubSection.getStream(), F.FunctionIndex, "function index");
+      writeUleb128(SubSection.getStream(), F.Symbol->getOutputSymbolIndex(),
+                   "function index");
     }
     SubSection.finalizeContents();
     SubSection.writeToStream(OS);
   }
 
   struct ComdatEntry { unsigned Kind; uint32_t Index; };
   std::map<StringRef,std::vector<ComdatEntry>> Comdats;
 

 
 void Writer::calculateImports() {
   for (Symbol *Sym : Symtab->getSymbols()) {
     if (!Sym->isUndefined() || (Sym->isWeak() && !Config->EmitRelocs))
       continue;
 
     if (Sym->isFunction()) {
       Sym->setOutputIndex(ImportedFunctions.size());
+      Sym->setOutputSymbolIndex(ImportedFunctions.size());
       ImportedFunctions.push_back(Sym);
     } else {
       Sym->setOutputIndex(ImportedGlobals.size());
+      Sym->setOutputSymbolIndex(ImportedGlobals.size());
       ImportedGlobals.push_back(Sym);
     }
   }
 }
 
 void Writer::calculateExports() {
   Symbol *EntrySym = Symtab->find(Config->Entry);
   bool ExportEntry = !Config->Relocatable && EntrySym && EntrySym->isDefined();
for (unsigned I = 1; ; ++I) {
       if (!UsedNames.count(NameBuf)) {
         StringRef Name = Saver.save(NameBuf);
         UsedNames.insert(Name); // Insert must use safe StringRef from save()
         return Name;
       }
     }
   };
 
-  if (ExportEntry)
+  unsigned FunctionIndex = ImportedFunctions.size();
+  if (ExportEntry) {
+    EntrySym->setOutputSymbolIndex(FunctionIndex++);
     ExportedSymbols.emplace_back(WasmExportEntry{EntrySym, EntrySym->getName()});
+  }
 
   if (Config->CtorSymbol && ExportHidden &&
-      !(ExportEntry && Config->CtorSymbol == EntrySym))
+      !(ExportEntry && Config->CtorSymbol == EntrySym)) {
+    Config->CtorSymbol->setOutputSymbolIndex(FunctionIndex++);
     ExportedSymbols.emplace_back(
         WasmExportEntry{Config->CtorSymbol, Config->CtorSymbol->getName()});
+  }
 
   for (ObjFile *File : Symtab->ObjectFiles) {
     for (Symbol *Sym : File->getSymbols()) {
       if (!Sym->isDefined() || File != Sym->getFile())
         continue;
       if (Sym->isGlobal())
         continue;
       if (Sym->getFunction()->Discarded)
         continue;
 
       if ((Sym->isHidden() || Sym->isLocal()) && !ExportHidden)
         continue;
       if (ExportEntry && Sym == EntrySym)
         continue;
+      Sym->setOutputSymbolIndex(FunctionIndex++);
       ExportedSymbols.emplace_back(WasmExportEntry{Sym, BudgeLocalName(Sym)});
     }
   }
 
-  for (const Symbol *Sym : DefinedGlobals) {
+  unsigned GlobalIndex = ImportedGlobals.size();
+  for (Symbol *Sym : DefinedGlobals) {
     // Can't export the SP right now because its mutable, and mutuable globals
     // are yet supported in the official binary format.  However, for
     // intermediate output we need to export it in case it is the target of any
     // relocations.
     // TODO(sbc): Remove this if/when the "mutable global" proposal is accepted.
     if (Sym == Config->StackPointerSymbol && !Config->EmitRelocs)
       continue;
+    Sym->setOutputSymbolIndex(GlobalIndex++);
     ExportedSymbols.emplace_back(WasmExportEntry{Sym, BudgeLocalName(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));
   }
 
   for (Symbol *Sym : Symtab->getSymbols())
     if (Sym->isFunction())
       registerType(Sym->getFunctionType());
 }
 
 void Writer::assignIndexes() {
   uint32_t GlobalIndex = ImportedGlobals.size() + DefinedGlobals.size();
   uint32_t FunctionIndex = ImportedFunctions.size() + DefinedFunctions.size();
 
   if (Config->StackPointerSymbol) {
     DefinedGlobals.emplace_back(Config->StackPointerSymbol);
     Config->StackPointerSymbol->setOutputIndex(GlobalIndex++);
void Writer::createCtorFunction() {
   Config->CtorSymbol->setOutputIndex(FunctionIndex);
 
   // First write the body bytes to a string.
   std::string FunctionBody;
   static WasmSignature Signature = {{}, WASM_TYPE_NORESULT};
   {
     raw_string_ostream OS(FunctionBody);
     writeUleb128(OS, 0, "num locals");
-    for (const WasmInitFunc &F : InitFunctions) {
+    for (const WasmInitEntry &F : InitFunctions) {
       writeU8(OS, OPCODE_CALL, "CALL");
-      writeUleb128(OS, F.FunctionIndex, "function index");
+      writeUleb128(OS, F.Symbol->getOutputIndex(), "function index");
     }
     writeU8(OS, OPCODE_END, "END");
   }
 
   // Once we know the size of the body we can create the final function body
   raw_string_ostream OS(CtorFunctionBody);
   writeUleb128(OS, FunctionBody.size(), "function size");
   OS.flush();

 // Populate InitFunctions vector with init functions from all input objects.
 // This is then used either when creating the output linking section or to
 // synthesize the "__wasm_call_ctors" function.
 void Writer::calculateInitFunctions() {
   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)});
+      InitFunctions.emplace_back(WasmInitEntry{
+          File->getFunctionSymbols()[F.FunctionIndex], F.Priority});
   }
   // Sort in order of priority (lowest first) so that they are called
   // in the correct order.
-  std::sort(InitFunctions.begin(), InitFunctions.end(),
-            [](const WasmInitFunc &L, const WasmInitFunc &R) {
+  std::stable_sort(InitFunctions.begin(), InitFunctions.end(),
+                   [](const WasmInitEntry &L, const WasmInitEntry &R) {
                      return L.Priority < R.Priority;
                    });
 }
 
 void Writer::run() {
   log("-- calculateTypes");
   calculateTypes();
   log("-- calculateImports");
   calculateImports();
   log("-- assignIndexes");