[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 ↗

(On Diff #134983)

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

lld/trunk/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();
-  }
-
-  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;
+  int32_t OutputOffset = 0;
 
   // 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;
 };
 
 // Represents a WebAssembly data segment which can be included as part of
 // an output data segments.  Note that in WebAssembly, unlike ELF and other
 // formats, used the term "data segment" to refer to the continous regions of
 // memory that make on the data section. See:
 // https://webassembly.github.io/spec/syntax/modules.html#syntax-data

lld/trunk/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 + OutputOffset, data().data(), data().size());
+
+  // Apply relocations
+  if (Relocations.empty())
+    return;
 
-  Buf += Reloc.Reloc.Offset;
+  DEBUG(dbgs() << "applyRelocations: count=" << Relocations.size() << "\n");
+  int32_t Off = OutputOffset - getInputSectionOffset();
 
-  switch (Reloc.Reloc.Type) {
+  for (const WasmRelocation &Rel : Relocations) {
+    uint8_t *Loc = Buf + Rel.Offset + Off;
+    uint64_t Value = File->calcNewValue(Rel);
+
+    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 used only when a user passes "-r". For a regular link,
+// we consume relocations instead of copying them to an output file.
+void InputChunk::writeRelocations(raw_ostream &OS) const {
   if (Relocations.empty())
     return;
-  int32_t Off = getOutputOffset() - getInputSectionOffset();
-  DEBUG(dbgs() << "calcRelocations: " << File->getName()
+
+  int32_t Off = OutputOffset - getInputSectionOffset();
+  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/trunk/wasm/OutputSections.cpp

CodeSection::CodeSection(ArrayRef<InputFunction *> Functions)
   assert(Functions.size() > 0);
 
   raw_string_ostream OS(CodeSectionHeader);
   writeUleb128(OS, Functions.size(), "function count");
   OS.flush();
   BodySize = CodeSectionHeader.size();
 
   for (InputChunk *Func : Functions) {
-    Func->setOutputOffset(BodySize);
+    Func->OutputOffset = BodySize;
     BodySize += Func->getSize();
   }
 
   createHeader(BodySize);
 }
 
 void CodeSection::writeTo(uint8_t *Buf) {
   log("writing " + toString(*this));
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();
   BodySize = DataSectionHeader.size();
 
   for (OutputSegment *Segment : Segments) {
     raw_string_ostream OS(Segment->Header);
     writeUleb128(OS, 0, "memory index");
     writeUleb128(OS, WASM_OPCODE_I32_CONST, "opcode:i32const");
     writeSleb128(OS, Segment->StartVA, "memory offset");
     writeUleb128(OS, WASM_OPCODE_END, "opcode:end");
     writeUleb128(OS, Segment->Size, "segment size");
     OS.flush();
     Segment->setSectionOffset(BodySize);
     BodySize += Segment->Header.size() + Segment->Size;
     log("Data segment: size=" + Twine(Segment->Size));
     for (InputSegment *InputSeg : Segment->InputSegments)
-      InputSeg->setOutputOffset(Segment->getSectionOffset() +
-                                Segment->Header.size() +
-                                InputSeg->OutputSegmentOffset);
+      InputSeg->OutputOffset = Segment->getSectionOffset() +
+                               InputSeg->OutputSegmentOffset;
   }
 
   createHeader(BodySize);
 }
 
 void DataSection::writeTo(uint8_t *Buf) {
   log("writing " + toString(*this) + " size=" + Twine(getSize()) +
       " body=" + Twine(BodySize));
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);
 }

lld/trunk/wasm/WriterUtils.h

 inline bool operator!=(const llvm::wasm::WasmSignature &LHS,
                        const llvm::wasm::WasmSignature &RHS) {
   return !(LHS == RHS);
 }
 
 namespace lld {
 namespace wasm {
 
-struct OutputRelocation {
-  llvm::wasm::WasmRelocation Reloc;
-  uint32_t NewIndex;
-  uint32_t Value;
-};
-
 void debugWrite(uint64_t Offset, const Twine &Msg);
 
 void writeUleb128(raw_ostream &OS, uint32_t Number, StringRef Msg);
 
 void writeSleb128(raw_ostream &OS, int32_t Number, StringRef Msg);
 
 void writeBytes(raw_ostream &OS, const char *Bytes, size_t count, StringRef Msg);
 

 void writeGlobalType(raw_ostream &OS, const llvm::wasm::WasmGlobalType &Type);
 
 void writeGlobal(raw_ostream &OS, const llvm::wasm::WasmGlobal &Global);
 
 void writeImport(raw_ostream &OS, const llvm::wasm::WasmImport &Import);
 
 void writeExport(raw_ostream &OS, const llvm::wasm::WasmExport &Export);
 
-void writeReloc(raw_ostream &OS, const OutputRelocation &Reloc);
-
 } // namespace wasm
 
 std::string toString(const llvm::wasm::ValType Type);
 std::string toString(const llvm::wasm::WasmSignature &Sig);
 
 } // namespace lld
 
 #endif // LLD_WASM_WRITERUTILS_H

lld/trunk/wasm/WriterUtils.cpp

case WASM_EXTERNAL_GLOBAL:
     break;
   case WASM_EXTERNAL_MEMORY:
     writeUleb128(OS, Export.Index, "memory index");
     break;
   default:
     fatal("unsupported export type: " + Twine(Export.Kind));
   }
 }
-
-void wasm::writeReloc(raw_ostream &OS, const OutputRelocation &Reloc) {
-  writeUleb128(OS, Reloc.Reloc.Type, "reloc type");
-  writeUleb128(OS, Reloc.Reloc.Offset, "reloc offset");
-  writeUleb128(OS, Reloc.NewIndex, "reloc index");
-
-  switch (Reloc.Reloc.Type) {
-  case R_WEBASSEMBLY_MEMORY_ADDR_LEB:
-  case R_WEBASSEMBLY_MEMORY_ADDR_SLEB:
-  case R_WEBASSEMBLY_MEMORY_ADDR_I32:
-    writeUleb128(OS, Reloc.Reloc.Addend, "reloc addend");
-    break;
-  default:
-    break;
-  }
-}
-
 } // namespace lld
 
 std::string lld::toString(ValType Type) {
   switch (Type) {
   case ValType::I32:
     return "I32";
   case ValType::I64:
     return "I64";