[WebAssembly] Do not create a temporary data structure for relocations.

[ruiu]

Summary

This patch removes OutRelocations vector from the InputChunk and
directly consume Relocations vector instead. This should make the linker
faster because we don't create a temporary data structure, and it matches
the lld's design principle that we don't create temporary data structures
for object files but instead directly consume mmap'ed data whenever possible.

[ruiu]

• remove dead code

[sbc100]

This is much better. Thank you. I particularly like the elimination of that random struct.

[sbc100]

lld/wasm/InputChunks.h

54

I guess we might as well get rid of this pair get/setters now and just expose OutputOffset.

lld/wasm/InputChunks.h

 #include "llvm/Object/Wasm.h"
 
 using llvm::object::WasmSegment;
 using llvm::wasm::WasmFunction;
 using llvm::wasm::WasmRelocation;
 using llvm::wasm::WasmSignature;
 using llvm::object::WasmSection;
 
+namespace llvm {
+class raw_ostream;
+}
+
 namespace lld {
 namespace wasm {
 
 class ObjFile;
 class OutputSegment;
 
 class InputChunk {
 public:
   enum Kind { DataSegment, Function };
 
   Kind kind() const { return SectionKind; }
 
   uint32_t getSize() const { return data().size(); }
 
   void copyRelocations(const WasmSection &Section);
 
   void writeTo(uint8_t *SectionStart) const;
 
-  void setOutputOffset(uint32_t Offset) {
-    OutputOffset = Offset;
-    calcRelocations();
-  }
+  void setOutputOffset(uint32_t Offset) { OutputOffset = Offset; }
 
   uint32_t getOutputOffset() const { return OutputOffset; }
   ArrayRef<WasmRelocation> getRelocations() const { return Relocations; }
 
   virtual StringRef getComdat() const = 0;
   virtual StringRef getName() const = 0;
 
-  std::vector<OutputRelocation> OutRelocations;
+  size_t NumRelocations() const { return Relocations.size(); }
+  void writeRelocations(llvm::raw_ostream &OS) const;
+
   ObjFile *File;
 
   // Signals that the section is part of the output.  The garbage collector,
   // and COMDAT handling can set a sections' Live bit.
   // If GC is disabled, all sections start out as live by default.
   unsigned Live : 1;
 
 protected:
   InputChunk(ObjFile *F, Kind K)
       : File(F), Live(!Config->GcSections), SectionKind(K) {}
   virtual ~InputChunk() = default;
-  void calcRelocations();
   virtual ArrayRef<uint8_t> data() const = 0;
   virtual uint32_t getInputSectionOffset() const = 0;
 
   std::vector<WasmRelocation> Relocations;
   int32_t OutputOffset = 0;
   Kind SectionKind;
 };
 

lld/wasm/InputChunks.cpp

 //===- InputChunks.cpp ----------------------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "InputChunks.h"
 #include "Config.h"
 #include "OutputSegment.h"
+#include "WriterUtils.h"
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/LLVM.h"
 #include "llvm/Support/LEB128.h"
 
 #define DEBUG_TYPE "lld"
 
 using namespace llvm;
 using namespace llvm::wasm;
if (Section.Relocations.empty())
     return;
   size_t Start = getInputSectionOffset();
   size_t Size = getSize();
   for (const WasmRelocation &R : Section.Relocations)
     if (R.Offset >= Start && R.Offset < Start + Size)
       Relocations.push_back(R);
 }
 
-static void applyRelocation(uint8_t *Buf, const OutputRelocation &Reloc) {
-  DEBUG(dbgs() << "write reloc: type=" << Reloc.Reloc.Type
-               << " index=" << Reloc.Reloc.Index << " value=" << Reloc.Value
-               << " offset=" << Reloc.Reloc.Offset << "\n");
+// Copy this input chunk to an mmap'ed output file and apply relocations.
+void InputChunk::writeTo(uint8_t *Buf) const {
+  // Copy contents
+  memcpy(Buf + getOutputOffset(), data().data(), data().size());
+
+  // Apply relocations
+  if (Relocations.empty())
+    return;
+
+  DEBUG(dbgs() << "applyRelocations: count=" << Relocations.size() << "\n");
+  int32_t Off = getOutputOffset() - getInputSectionOffset();
 
-  Buf += Reloc.Reloc.Offset;
+  for (const WasmRelocation &Rel : Relocations) {
+    uint8_t *Loc = Buf + Rel.Offset + Off;
+    uint64_t Value = File->calcNewValue(Rel);
 
-  switch (Reloc.Reloc.Type) {
+    DEBUG(dbgs() << "write reloc: type=" << Rel.Type << " index=" << Rel.Index
+                 << " value=" << Value << " offset=" << Rel.Offset << "\n");
+
+    switch (Rel.Type) {
     case R_WEBASSEMBLY_TYPE_INDEX_LEB:
     case R_WEBASSEMBLY_FUNCTION_INDEX_LEB:
     case R_WEBASSEMBLY_GLOBAL_INDEX_LEB:
-    // Additional check to verify that the existing value that the location
-    // matches our expectations.
-    if (decodeULEB128(Buf) != Reloc.Reloc.Index) {
-      DEBUG(dbgs() << "existing value: " << decodeULEB128(Buf) << "\n");
-      assert(decodeULEB128(Buf) == Reloc.Reloc.Index);
-    }
-    LLVM_FALLTHROUGH;
     case R_WEBASSEMBLY_MEMORY_ADDR_LEB:
-    encodeULEB128(Reloc.Value, Buf, 5);
+      encodeULEB128(Value, Loc, 5);
       break;
     case R_WEBASSEMBLY_TABLE_INDEX_SLEB:
     case R_WEBASSEMBLY_MEMORY_ADDR_SLEB:
-    encodeSLEB128(static_cast<int32_t>(Reloc.Value), Buf, 5);
+      encodeSLEB128(static_cast<int32_t>(Value), Loc, 5);
       break;
     case R_WEBASSEMBLY_TABLE_INDEX_I32:
     case R_WEBASSEMBLY_MEMORY_ADDR_I32:
-    write32le(Buf, Reloc.Value);
+      write32le(Loc, Value);
       break;
     default:
       llvm_unreachable("unknown relocation type");
     }
   }
-
-// Copy this input chunk to an mmap'ed output file.
-void InputChunk::writeTo(uint8_t *Buf) const {
-  // Copy contents
-  memcpy(Buf + getOutputOffset(), data().data(), data().size());
-
-  // Apply relocations
-  if (OutRelocations.empty())
-    return;
-  DEBUG(dbgs() << "applyRelocations: count=" << OutRelocations.size() << "\n");
-  for (const OutputRelocation &Reloc : OutRelocations)
-    applyRelocation(Buf, Reloc);
 }
 
-// Populate OutRelocations based on the input relocations and offset within the
-// output section.  Calculates the updated index and offset for each relocation
-// as well as the value to write out in the final binary.
-void InputChunk::calcRelocations() {
+// Copy relocation entries to a given output stream.
+// This function is not invoked when we are doing a regular link because
+// we consume relocations instead of copying them to an output file.
+// So, this function is used only when a user passes "-r".
+void InputChunk::writeRelocations(raw_ostream &OS) const {
   if (Relocations.empty())
     return;
+
   int32_t Off = getOutputOffset() - getInputSectionOffset();
-  DEBUG(dbgs() << "calcRelocations: " << File->getName()
+  DEBUG(dbgs() << "writeRelocations: " << File->getName()
                << " offset=" << Twine(Off) << "\n");
-  for (const WasmRelocation &Reloc : Relocations) {
-    OutputRelocation NewReloc;
-    NewReloc.Reloc = Reloc;
-    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->Relocatable)
-      NewReloc.NewIndex = File->calcNewIndex(Reloc);
+  for (const WasmRelocation &Rel : Relocations) {
+    writeUleb128(OS, Rel.Type, "reloc type");
+    writeUleb128(OS, Rel.Offset + Off, "reloc offset");
+    writeUleb128(OS, File->calcNewIndex(Rel), "reloc index");
 
-    NewReloc.Value = File->calcNewValue(Reloc);
-    OutRelocations.emplace_back(NewReloc);
+    switch (Rel.Type) {
+    case R_WEBASSEMBLY_MEMORY_ADDR_LEB:
+    case R_WEBASSEMBLY_MEMORY_ADDR_SLEB:
+    case R_WEBASSEMBLY_MEMORY_ADDR_I32:
+      writeUleb128(OS, Rel.Addend, "reloc addend");
+      break;
+    }
   }
 }
 
 void InputFunction::setOutputIndex(uint32_t Index) {
   DEBUG(dbgs() << "InputFunction::setOutputIndex: " << getName() << " -> " << Index << "\n");
   assert(!hasOutputIndex());
   OutputIndex = Index;
 }
 
 void InputFunction::setTableIndex(uint32_t Index) {
   DEBUG(dbgs() << "InputFunction::setTableIndex: " << getName() << " -> " << Index << "\n");
   assert(!hasTableIndex());
   TableIndex = Index;
 }

lld/wasm/OutputSections.cpp

void CodeSection::writeTo(uint8_t *Buf) {
   parallelForEach(Functions, [ContentsStart](const InputChunk *Chunk) {
     Chunk->writeTo(ContentsStart);
   });
 }
 
 uint32_t CodeSection::numRelocations() const {
   uint32_t Count = 0;
   for (const InputChunk *Func : Functions)
-    Count += Func->OutRelocations.size();
+    Count += Func->NumRelocations();
   return Count;
 }
 
 void CodeSection::writeRelocations(raw_ostream &OS) const {
-  for (const InputChunk *Func : Functions)
-    for (const OutputRelocation &Reloc : Func->OutRelocations)
-      writeReloc(OS, Reloc);
+  for (const InputChunk *C : Functions)
+    C->writeRelocations(OS);
 }
 
 DataSection::DataSection(ArrayRef<OutputSegment *> Segments)
     : OutputSection(WASM_SEC_DATA), Segments(Segments) {
   raw_string_ostream OS(DataSectionHeader);
 
   writeUleb128(OS, Segments.size(), "data segment count");
   OS.flush();
for (const InputChunk *Chunk : Segment->InputSegments)
       Chunk->writeTo(ContentsStart);
   });
 }
 
 uint32_t DataSection::numRelocations() const {
   uint32_t Count = 0;
   for (const OutputSegment *Seg : Segments)
     for (const InputChunk *InputSeg : Seg->InputSegments)
-      Count += InputSeg->OutRelocations.size();
+      Count += InputSeg->NumRelocations();
   return Count;
 }
 
 void DataSection::writeRelocations(raw_ostream &OS) const {
   for (const OutputSegment *Seg : Segments)
-    for (const InputChunk *InputSeg : Seg->InputSegments)
-      for (const OutputRelocation &Reloc : InputSeg->OutRelocations)
-        writeReloc(OS, Reloc);
+    for (const InputChunk *C : Seg->InputSegments)
+      C->writeRelocations(OS);
 }