[WebAssembly] Symbol changes #2: Table relocs, LLD

[ncw]

Summary

Second chunk split out of D41955.

Must be committed simultaneously with LLVM change, D42080.

Changes:

• LLD updated to handle new table reloc data (see D42080)
• Now, we build the output table by iterating over all the non-Discarded Functions and Segments, rather than iterating over all the Symbols. This means that when we implement GC, the function table will actually be pruned properly.
• A small block of code in InputChunks::calcRelocations has been factored out into ObjFile::calcNewValue to match ObjFile::calcNewIndex.
• Relocatable output has been updated in the same way as for D42080, so the change to that test is correct

[sbc100]

wasm/InputFiles.cpp

70

Can this function now be removed?

wasm/InputFiles.h

111

perhaps call this relocateAddress, relocateVirtualAddress or relocateMemoryLocation or something similar to match the functions below?

wasm/Writer.cpp

756–757

If the lamda takes and InputChunk* then can this condition move there and we can just have:

for (InputFunction* Func : File->Functions)
  HandleRelocs(Func);
for (InputSegment* Seg : File->Segments)
  HandleRelocs(Seg);

756–757

Maybe call this handleTableRelocs?

[ncw]

Updated:

• Responded to comments (formatting/tidying changes)

wasm/InputFiles.cpp

70

I don't think it can be removed. Function indexes are definitely different to table indexes: relocateTableIndex calls getTableIndex which is necessary for performing the actual relocation.

[ncw]

Updated:

• Straightforward rebase

[ncw]

Updated:

• Another rebase after #4c and #4d landed

[ncw]

The LLVM change was merged in rL323165, and the LLD change was merged in rLLD323168.

However, the LLD commit did not reference this review in the commit message, so a think the only way to close the review is to abandon it.

test/wasm/locals-duplicate.test

 ; RELOC-NEXT:         Offset:          0x00000058
 ; RELOC-NEXT:       - Type:            R_WEBASSEMBLY_MEMORY_ADDR_SLEB
 ; RELOC-NEXT:         Index:           4
 ; RELOC-NEXT:         Offset:          0x00000061
 ; RELOC-NEXT:       - Type:            R_WEBASSEMBLY_MEMORY_ADDR_SLEB
 ; RELOC-NEXT:         Index:           5
 ; RELOC-NEXT:         Offset:          0x0000006A
 ; RELOC-NEXT:       - Type:            R_WEBASSEMBLY_TABLE_INDEX_SLEB
-; RELOC-NEXT:         Index:           3
+; RELOC-NEXT:         Index:           9
 ; RELOC-NEXT:         Offset:          0x00000073
 ; RELOC-NEXT:       - Type:            R_WEBASSEMBLY_TABLE_INDEX_SLEB
-; RELOC-NEXT:         Index:           4
+; RELOC-NEXT:         Index:           10
 ; RELOC-NEXT:         Offset:          0x0000007C
 ; RELOC-NEXT:       - Type:            R_WEBASSEMBLY_TABLE_INDEX_SLEB
-; RELOC-NEXT:         Index:           5
+; RELOC-NEXT:         Index:           11
 ; RELOC-NEXT:         Offset:          0x00000085
 ; RELOC-NEXT:     Functions:       
 ; RELOC-NEXT:       - Index:           0
 ; RELOC-NEXT:         Locals:          
 ; RELOC-NEXT:         Body:            41020B
 ; RELOC-NEXT:       - Index:           1
 ; RELOC-NEXT:         Locals:          
 ; RELOC-NEXT:         Body:            41020B

test/wasm/relocatable.ll

 ; CHECK-NEXT:         Locals:
 ; CHECK-NEXT:         Body:          1081808080001A1082808080001A41010B
 ; CHECK-NEXT:       - Index:         5
 ; CHECK-NEXT:         Locals:
 ; CHECK-NEXT:         Body:          419C808080000B
 ; CHECK-NEXT:   - Type:            DATA
 ; CHECK-NEXT:     Relocations:
 ; CHECK-NEXT:       - Type:            R_WEBASSEMBLY_TABLE_INDEX_I32
-; CHECK-NEXT:         Index:           0
+; CHECK-NEXT:         Index:           4
 ; CHECK-NEXT:         Offset:          0x00000012
 ; CHECK-NEXT:       - Type:            R_WEBASSEMBLY_TABLE_INDEX_I32
 ; CHECK-NEXT:         Index:           1
 ; CHECK-NEXT:         Offset:          0x0000001B
 ; CHECK-NEXT:       - Type:            R_WEBASSEMBLY_TABLE_INDEX_I32
 ; CHECK-NEXT:         Index:           2
 ; CHECK-NEXT:         Offset:          0x00000024
 ; CHECK-NEXT:       - Type:            R_WEBASSEMBLY_MEMORY_ADDR_I32

wasm/InputChunks.h

public:
   void writeTo(uint8_t *SectionStart) const;
 
   void setOutputOffset(uint32_t Offset) {
     OutputOffset = Offset;
     calcRelocations();
   }
 
   uint32_t getOutputOffset() const { return OutputOffset; }
+  ArrayRef<WasmRelocation> getRelocations() const { return Relocations; }
 
   virtual StringRef getComdat() const = 0;
 
   bool Discarded = false;
   std::vector<OutputRelocation> OutRelocations;
 
 protected:
   InputChunk(const ObjFile *F) : File(F) {}

wasm/InputChunks.cpp

if (ExistingValue != Reloc.Reloc.Index) {
       assert(decodeULEB128(Buf) == Reloc.Reloc.Index);
     }
     LLVM_FALLTHROUGH;
   case R_WEBASSEMBLY_MEMORY_ADDR_LEB:
   case R_WEBASSEMBLY_GLOBAL_INDEX_LEB:
     encodeULEB128(Reloc.Value, Buf, 5);
     break;
   case R_WEBASSEMBLY_TABLE_INDEX_SLEB:
-    ExistingValue = decodeSLEB128(Buf);
-    if (ExistingValue != Reloc.Reloc.Index) {
-      DEBUG(dbgs() << "existing value: " << decodeSLEB128(Buf) << "\n");
-      assert(decodeSLEB128(Buf) == Reloc.Reloc.Index);
-    }
-    LLVM_FALLTHROUGH;
   case R_WEBASSEMBLY_MEMORY_ADDR_SLEB:
     encodeSLEB128(static_cast<int32_t>(Reloc.Value), Buf, 5);
     break;
   case R_WEBASSEMBLY_TABLE_INDEX_I32:
   case R_WEBASSEMBLY_MEMORY_ADDR_I32:
     support::endian::write32<support::little>(Buf, Reloc.Value);
     break;
   default:
for (const WasmRelocation &Reloc : Relocations) {
     assert(Reloc.Offset + Off > 0);
     NewReloc.Reloc.Offset += Off;
     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_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;
-    }
+    NewReloc.Value = File->calcNewValue(Reloc);
 
     OutRelocations.emplace_back(NewReloc);
   }
 }
 
 void InputFunction::setOutputIndex(uint32_t Index) {
   DEBUG(dbgs() << "InputFunction::setOutputIndex: " << Index << "\n");
   assert(!hasOutputIndex());
   OutputIndex = Index;
 }

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 getRelocatedAddress(uint32_t Index) 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() { return Symbols; }
-  ArrayRef<Symbol *> getTableSymbols() { return TableSymbols; }
+  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 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);
private:
   std::vector<Symbol *> Symbols;
 
   // List of all function symbols indexed by the function index space
   std::vector<Symbol *> FunctionSymbols;
 
   // List of all global symbols indexed by the global index space
   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;
   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 {
+uint32_t ObjFile::relocateVirtualAddress(uint32_t GlobalIndex) const {
   return GlobalSymbols[GlobalIndex]->getVirtualAddress();
 }
 
 uint32_t ObjFile::relocateFunctionIndex(uint32_t Original) const {
   Symbol *Sym = FunctionSymbols[Original];
   uint32_t Index = Sym->getOutputIndex();
   DEBUG(dbgs() << "relocateFunctionIndex: " << toString(*Sym) << ": "
                << Original << " -> " << Index << "\n");
   return Index;
 }
 
 uint32_t ObjFile::relocateTypeIndex(uint32_t Original) const {
   return TypeMap[Original];
 }
 
 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 relocateFunctionIndex(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);
   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);
+  case R_WEBASSEMBLY_GLOBAL_INDEX_LEB:
+    return relocateGlobalIndex(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");
   std::unique_ptr<Binary> Bin = CHECK(createBinary(MB), toString(this));
 
   auto *Obj = dyn_cast<WasmObjectFile>(Bin.get());
   if (!Obj)
     fatal(toString(this) + ": not a wasm file");
for (const SymbolRef &Sym : WasmObj->symbols()) {
     }
   }
 
   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");
-    uint32_t Offset = Segment.Offset.Value.Int32;
-    TableSymbols.resize(Offset);
-    TableSymbols.reserve(Offset + 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/Writer.cpp

for (InputFunction *Func : File->Functions) {
       if (Func->Discarded)
         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()) {
-      if (!Sym || Sym->hasTableIndex() || !Sym->hasOutputIndex())
+    auto HandleTableRelocs = [&](InputChunk *Chunk) {
+      if (Chunk->Discarded)
+        return;
+      for (const WasmRelocation& Reloc : Chunk->getRelocations()) {
+        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* Function : File->Functions)
+      HandleTableRelocs(Function);
+    for (InputSegment* Segment : File->Segments)
+      HandleTableRelocs(Segment);
   }
 }
 
 static StringRef getOutputDataSegmentName(StringRef Name) {
   if (Config->Relocatable)
     return Name;
 
   for (StringRef V :