[lld-macho] Parallelize __LINKEDIT generation

[int3]

Summary

Benchmarking chromium_framework on a 3.2 GHz 16-Core Intel Xeon W Mac Pro:

    N           Min           Max        Median           Avg        Stddev
x  20          4.33          4.42          4.37          4.37   0.021026299
+  20          4.12          4.23          4.18         4.175   0.035318103
Difference at 95.0% confidence
  -0.195 +/- 0.0186025
  -4.46224% +/- 0.425686%
  (Student's t, pooled s = 0.0290644)

[gkm]

LGTM

lld/MachO/SyntheticSections.h

 // All sections in __LINKEDIT should inherit from this.
 class LinkEditSection : public SyntheticSection {
 public:
   LinkEditSection(const char *segname, const char *name)
       : SyntheticSection(segname, name) {
     align = target->wordSize;
   }
 
+  virtual void finalizeContents() {}
+
   // Sections in __LINKEDIT are special: their offsets are recorded in the
   // load commands like LC_DYLD_INFO_ONLY and LC_SYMTAB, instead of in section
   // headers.
   bool isHidden() const override final { return true; }
 
   virtual uint64_t getRawSize() const = 0;
 
   // codesign (or more specifically libstuff) checks that each section in

 };
 
 // Stores rebase opcodes, which tell dyld where absolute addresses have been
 // encoded in the binary. If the binary is not loaded at its preferred address,
 // dyld has to rebase these addresses by adding an offset to them.
 class RebaseSection : public LinkEditSection {
 public:
   RebaseSection();
-  void finalizeContents();
+  void finalizeContents() override;
   uint64_t getRawSize() const override { return contents.size(); }
   bool isNeeded() const override { return !locations.empty(); }
   void writeTo(uint8_t *buf) const override;
 
   void addEntry(const InputSection *isec, uint64_t offset) {
     if (config->isPic)
       locations.push_back({isec, offset});
   }
struct BindingEntry {
   BindingEntry(const DylibSymbol *dysym, int64_t addend, Location target)
       : dysym(dysym), addend(addend), target(std::move(target)) {}
 };
 
 // Stores bind opcodes for telling dyld which symbols to load non-lazily.
 class BindingSection : public LinkEditSection {
 public:
   BindingSection();
-  void finalizeContents();
+  void finalizeContents() override;
   uint64_t getRawSize() const override { return contents.size(); }
   bool isNeeded() const override { return !bindings.empty(); }
   void writeTo(uint8_t *buf) const override;
 
   void addEntry(const DylibSymbol *dysym, const InputSection *isec,
                 uint64_t offset, int64_t addend = 0) {
     bindings.emplace_back(dysym, addend, Location(isec, offset));
   }

 //
 //   2) Weak bindings: These tell dyld that a given symbol reference should
 //   coalesce to a non-weak definition if one is found. Note that unlike in the
 //   entries in the BindingSection, the bindings here only refer to these
 //   symbols by name, but do not specify which dylib to load them from.
 class WeakBindingSection : public LinkEditSection {
 public:
   WeakBindingSection();
-  void finalizeContents();
+  void finalizeContents() override;
   uint64_t getRawSize() const override { return contents.size(); }
   bool isNeeded() const override {
     return !bindings.empty() || !definitions.empty();
   }
 
   void writeTo(uint8_t *buf) const override;
 
   void addEntry(const Symbol *symbol, const InputSection *isec, uint64_t offset,
public:
   uint64_t getSize() const override;
   bool isNeeded() const override;
   void writeTo(uint8_t *buf) const override;
 };
 
 class LazyBindingSection : public LinkEditSection {
 public:
   LazyBindingSection();
-  void finalizeContents();
+  void finalizeContents() override;
   uint64_t getRawSize() const override { return contents.size(); }
   bool isNeeded() const override { return !entries.empty(); }
   void writeTo(uint8_t *buf) const override;
   // Note that every entry here will by referenced by a corresponding entry in
   // the StubHelperSection.
   void addEntry(DylibSymbol *dysym);
   const llvm::SetVector<DylibSymbol *> &getEntries() const { return entries; }
 
 private:
   uint32_t encode(const DylibSymbol &);
 
   llvm::SetVector<DylibSymbol *> entries;
   SmallVector<char, 128> contents;
   llvm::raw_svector_ostream os{contents};
 };
 
 // Stores a trie that describes the set of exported symbols.
 class ExportSection : public LinkEditSection {
 public:
   ExportSection();
-  void finalizeContents();
+  void finalizeContents() override;
   uint64_t getRawSize() const override { return size; }
   void writeTo(uint8_t *buf) const override;
 
   bool hasWeakSymbol = false;
 
 private:
   TrieBuilder trieBuilder;
   size_t size = 0;
 };
 
 class FunctionStartsSection : public LinkEditSection {
 public:
   FunctionStartsSection();
-  void finalizeContents();
+  void finalizeContents() override;
   uint64_t getRawSize() const override { return contents.size(); }
   void writeTo(uint8_t *buf) const override;
 
 private:
   SmallVector<char, 128> contents;
 };
 
 // Stores the strings referenced by the symbol table.

 };
 
 // Symbols of the same type must be laid out contiguously: we choose to emit
 // all local symbols first, then external symbols, and finally undefined
 // symbols. For each symbol type, the LC_DYSYMTAB load command will record the
 // range (start index and total number) of those symbols in the symbol table.
 class SymtabSection : public LinkEditSection {
 public:
-  void finalizeContents();
+  void finalizeContents() override;
   uint32_t getNumSymbols() const;
   uint32_t getNumLocalSymbols() const {
     return stabs.size() + localSymbols.size();
   }
   uint32_t getNumExternalSymbols() const { return externalSymbols.size(); }
   uint32_t getNumUndefinedSymbols() const { return undefinedSymbols.size(); }
 
 private:

 //
 // These sub-arrays provide symbol information for sections that store
 // contiguous sequences of symbol references. These references can be pointers
 // (e.g. those in the GOT and TLVP sections) or assembly sequences (e.g.
 // function stubs).
 class IndirectSymtabSection : public LinkEditSection {
 public:
   IndirectSymtabSection();
-  void finalizeContents();
+  void finalizeContents() override;
   uint32_t getNumSymbols() const;
   uint64_t getRawSize() const override {
     return getNumSymbols() * sizeof(uint32_t);
   }
   bool isNeeded() const override;
   void writeTo(uint8_t *buf) const override;
 };
 

lld/MachO/Writer.cpp

 class Writer {
 public:
   Writer() : buffer(errorHandler().outputBuffer) {}
 
   void scanRelocations();
   void scanSymbols();
   template <class LP> void createOutputSections();
   template <class LP> void createLoadCommands();
-  void finalizeAddressses();
+  void finalizeAddresses();
   void finalizeLinkEditSegment();
   void assignAddresses(OutputSegment *);
 
   void openFile();
   void writeSections();
   void writeUuid();
   void writeCodeSignature();
   void writeOutputFile();
if (it == mergedOutputSections.end()) {
             ssec->name);
     }
   }
 
   // dyld requires __LINKEDIT segment to always exist (even if empty).
   linkEditSegment = getOrCreateOutputSegment(segment_names::linkEdit);
 }
 
-void Writer::finalizeAddressses() {
+void Writer::finalizeAddresses() {
   TimeTraceScope timeScope("Finalize addresses");
   // Ensure that segments (and the sections they contain) are allocated
   // addresses in ascending order, which dyld requires.
   //
   // Note that at this point, __LINKEDIT sections are empty, but we need to
   // determine addresses of other segments/sections before generating its
   // contents.
   for (OutputSegment *seg : outputSegments)
     if (seg != linkEditSegment)
       assignAddresses(seg);
 
   // FIXME(gkm): create branch-extension thunks here, then adjust addresses
 }
 
 void Writer::finalizeLinkEditSegment() {
   TimeTraceScope timeScope("Finalize __LINKEDIT segment");
   // Fill __LINKEDIT contents.
-  in.rebase->finalizeContents();
-  in.binding->finalizeContents();
-  in.weakBinding->finalizeContents();
-  in.lazyBinding->finalizeContents();
-  in.exports->finalizeContents();
-  symtabSection->finalizeContents();
-  indirectSymtabSection->finalizeContents();
-
-  if (functionStartsSection)
-    functionStartsSection->finalizeContents();
+  std::vector<LinkEditSection *> linkEditSections{
+      in.rebase,  in.binding,    in.weakBinding,        in.lazyBinding,
+      in.exports, symtabSection, indirectSymtabSection, functionStartsSection,
+  };
+  parallelForEach(linkEditSections, [](LinkEditSection *osec) {
+    if (osec)
+      osec->finalizeContents();
+  });
 
   // Now that __LINKEDIT is filled out, do a proper calculation of its
   // addresses and offsets.
   assignAddresses(linkEditSegment);
 }
 
 void Writer::assignAddresses(OutputSegment *seg) {
   uint64_t pageSize = target->getPageSize();
template <class LP> void Writer::run() {
   scanRelocations();
   if (in.stubHelper->isNeeded())
     in.stubHelper->setup();
   scanSymbols();
   createOutputSections<LP>();
   // No more sections nor segments are created beyond this point.
   sortSegmentsAndSections();
   createLoadCommands<LP>();
-  finalizeAddressses();
+  finalizeAddresses();
   finalizeLinkEditSegment();
   writeMapFile();
   writeOutputFile();
 }
 
 template <class LP> void macho::writeResult() { Writer().run<LP>(); }
 
 template <class LP> void macho::createSyntheticSections() {