[WebAssembly] Apply data relocation in parallel. NFC.

[sbc100]

Summary

Store data relocations with their respective segment.
This allows reloctions to be applied as each segment
is written (and therefore in parallel).

[sbc100]

rebase

[sbc100]

• store relocs in input segments

[ncw]

Looks nice. My changes for pruning functions/segments rely on the relocations happening nice and late, so that we don't try and generate the index of a function that's being pruned. There changes all help with that, ensuring that we don't need the relocations to be "resolvable" for code that we're discarding.

lld/trunk/wasm/InputSegment.h

 // For example, by default, clang will produce a separate data section for
 // each global variable.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_WASM_INPUT_SEGMENT_H
 #define LLD_WASM_INPUT_SEGMENT_H
 
+#include "WriterUtils.h"
 #include "lld/Common/ErrorHandler.h"
 #include "llvm/Object/Wasm.h"
 
 using llvm::object::WasmSegment;
 using llvm::wasm::WasmRelocation;
 
 namespace lld {
 namespace wasm {
public:
   uint32_t getAlignment() const { return Segment->Data.Alignment; }
   uint32_t startVA() const { return Segment->Data.Offset.Value.Int32; }
   uint32_t endVA() const { return startVA() + getSize(); }
   StringRef getName() const { return Segment->Data.Name; }
 
   const WasmSegment *Segment;
   const ObjFile *File;
   std::vector<WasmRelocation> Relocations;
+  std::vector<OutputRelocation> OutRelocations;
 
 protected:
   const OutputSegment *OutputSeg = nullptr;
   uint32_t OutputSegmentOffset = 0;
 };
 
 } // namespace wasm
 } // namespace lld
 
 #endif // LLD_WASM_INPUT_SEGMENT_H

lld/trunk/wasm/OutputSections.h

protected:
   size_t BodySize = 0;
 };
 
 class DataSection : public OutputSection {
 public:
   explicit DataSection(ArrayRef<OutputSegment *> Segments);
   size_t getSize() const override { return Header.size() + BodySize; }
   void writeTo(uint8_t *Buf) override;
-  uint32_t numRelocations() const override { return Relocations.size(); }
+  uint32_t numRelocations() const override;
   void writeRelocations(raw_ostream &OS) const override;
 
 protected:
-  std::vector<OutputRelocation> Relocations;
   ArrayRef<OutputSegment *> Segments;
   std::string DataSectionHeader;
   size_t BodySize = 0;
 };
 
 } // namespace wasm
 } // namespace lld
 
 #endif // LLD_WASM_OUTPUT_SECTIONS_H

lld/trunk/wasm/OutputSections.cpp

case R_WEBASSEMBLY_MEMORY_ADDR_I32:
     support::endian::write32<support::little>(Buf, Reloc.Value);
     break;
   default:
     llvm_unreachable("unknown relocation type");
   }
 }
 
 static void applyRelocations(uint8_t *Buf, ArrayRef<OutputRelocation> Relocs) {
+  if (!Relocs.size())
+    return;
   log("applyRelocations: count=" + Twine(Relocs.size()));
-  for (const OutputRelocation &Reloc : Relocs) {
+  for (const OutputRelocation &Reloc : Relocs)
     applyRelocation(Buf, Reloc);
-  }
-}
 
 // 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).
 static uint32_t calcNewIndex(const ObjFile &File, const WasmRelocation &Reloc) {
   switch (Reloc.Type) {
   case R_WEBASSEMBLY_TYPE_INDEX_LEB:
parallelForEach(InputObjects, [ContentsStart](ObjFile *File) {
     unsigned HeaderSize = 0;
     decodeULEB128(Content.data(), &HeaderSize);
 
     size_t PayloadSize = Content.size() - HeaderSize;
     memcpy(ContentsStart + File->CodeOffset, Content.data() + HeaderSize,
            PayloadSize);
 
     log("applying relocations for: " + File->getName());
-    if (File->CodeRelocations.size())
-      applyRelocations(ContentsStart, File->CodeRelocations);
   });
 }
 
 uint32_t CodeSection::numRelocations() const {
   uint32_t Count = 0;
   for (ObjFile *File : InputObjects)
     Count += File->CodeRelocations.size();
   return Count;
for (OutputSegment *Segment : Segments) {
     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();
     log("Data segment: size=" + Twine(Segment->Size));
-    for (const InputSegment *InputSeg : Segment->InputSegments) {
+    for (InputSegment *InputSeg : Segment->InputSegments) {
       uint32_t InputOffset = InputSeg->getInputSectionOffset();
       uint32_t OutputOffset = Segment->getSectionOffset() +
                               Segment->Header.size() +
                               InputSeg->getOutputSegmentOffset();
-      calcRelocations(*InputSeg->File, InputSeg->Relocations, Relocations,
-                      OutputOffset - InputOffset);
+      calcRelocations(*InputSeg->File, InputSeg->Relocations,
+                      InputSeg->OutRelocations, OutputOffset - InputOffset);
     }
     BodySize += Segment->Size;
   }
 
   createHeader(BodySize);
 }
 
 void DataSection::writeTo(uint8_t *Buf) {
parallelForEach(Segments, [ContentsStart](const OutputSegment *Segment) {
     memcpy(SegStart, Segment->Header.data(), Segment->Header.size());
 
     // Write segment data payload
     for (const InputSegment *Input : Segment->InputSegments) {
       ArrayRef<uint8_t> Content(Input->Segment->Data.Content);
       memcpy(SegStart + Segment->Header.size() +
                  Input->getOutputSegmentOffset(),
              Content.data(), Content.size());
+      applyRelocations(ContentsStart, Input->OutRelocations);
     }
   });
+}
 
-  applyRelocations(ContentsStart, Relocations);
+uint32_t DataSection::numRelocations() const {
+  uint32_t Count = 0;
+  for (const OutputSegment *Seg : Segments)
+    for (const InputSegment *InputSeg : Seg->InputSegments)
+      Count += InputSeg->OutRelocations.size();
+  return Count;
 }
 
 void DataSection::writeRelocations(raw_ostream &OS) const {
-  for (const OutputRelocation &Reloc : Relocations)
+  for (const OutputSegment *Seg : Segments)
+    for (const InputSegment *InputSeg : Seg->InputSegments)
+      for (const OutputRelocation &Reloc : InputSeg->OutRelocations)
         writeReloc(OS, Reloc);
 }

lld/trunk/wasm/OutputSegment.h

public:
 
   uint32_t getSectionOffset() const { return SectionOffset; }
 
   void setSectionOffset(uint32_t Offset) { SectionOffset = Offset; }
 
   StringRef Name;
   uint32_t Alignment = 0;
   uint32_t StartVA = 0;
-  std::vector<const InputSegment *> InputSegments;
+  std::vector<InputSegment *> InputSegments;
 
   // Sum of the size of the all the input segments
   uint32_t Size = 0;
 
   // Segment header
   std::string Header;
 
 private:
   uint32_t SectionOffset = 0;
 };
 
 } // namespace wasm
 } // namespace lld
 
 #endif // LLD_WASM_OUTPUT_SEGMENT_H