[ELF] Parallelize output section writing instead of input section writing

[MaskRay]

Summary

For many synthetic sections, their writeTo functions are not parallel and their parent output section has just one input section.
Parallelizing input section writing does not leverage parallelism well.
Switch to parallelizing output section writing instead.

Seems not useful

[MaskRay]

.

lld/ELF/OutputSections.h

public:
   bool inOverlay = false;
 
   // Tracks whether the section has ever had an input section added to it, even
   // if the section was later removed (e.g. because it is a synthetic section
   // that wasn't needed). This is needed for orphan placement.
   bool hasInputSections = false;
 
   void finalize();
-  template <class ELFT> void writeTo(uint8_t *buf);
+  template <class ELFT> void writeTo(uint8_t *buf, bool parallel = true);
   // Check that the addends for dynamic relocations were written correctly.
   void checkDynRelAddends(const uint8_t *bufStart);
   template <class ELFT> void maybeCompress();
 
   void sort(llvm::function_ref<int(InputSectionBase *s)> order);
   void sortInitFini();
   void sortCtorsDtors();
 

lld/ELF/OutputSections.cpp

static void writeInt(uint8_t *buf, uint64_t data, uint64_t size) {
   else if (size == 4)
     write32(buf, data);
   else if (size == 8)
     write64(buf, data);
   else
     llvm_unreachable("unsupported Size argument");
 }
 
-template <class ELFT> void OutputSection::writeTo(uint8_t *buf) {
+template <class IndexTy, class FuncTy>
+void lld_parallel_for_each_n(IndexTy Begin, IndexTy End, FuncTy Fn) {
+  // Limit the number of tasks to MaxTasksPerGroup to limit job scheduling
+  // overhead on large inputs.
+  const ptrdiff_t TaskSize = 128;
+  parallel::detail::TaskGroup TG;
+  IndexTy I = Begin;
+  for (; I + TaskSize < End; I += TaskSize) {
+    TG.spawn([=, &Fn] {
+      for (IndexTy J = I, E = I + TaskSize; J != E; ++J)
+        Fn(J);
+    });
+  }
+  for (IndexTy J = I; J < End; ++J)
+    Fn(J);
+}
+
+template <class ELFT> void OutputSection::writeTo(uint8_t *buf, bool parallel) {
   llvm::TimeTraceScope timeScope("Write sections", name);
   if (type == SHT_NOBITS)
     return;
 
   // If --compress-debug-section is specified and if this is a debug section,
   // we've already compressed section contents. If that's the case,
   // just write it down.
   if (!compressedData.empty()) {
     memcpy(buf, zDebugHeader.data(), zDebugHeader.size());
     memcpy(buf + zDebugHeader.size(), compressedData.data(),
            compressedData.size());
     return;
   }
 
   // Write leading padding.
   SmallVector<InputSection *, 0> sections = getInputSections(*this);
   std::array<uint8_t, 4> filler = getFiller();
   bool nonZeroFiller = read32(filler.data()) != 0;
   if (nonZeroFiller)
     fill(buf, sections.empty() ? size : sections[0]->outSecOff, filler);
 
-  parallelForEachN(0, sections.size(), [&](size_t i) {
+  auto fn = [&](size_t i) {
     InputSection *isec = sections[i];
     isec->writeTo<ELFT>(buf + isec->outSecOff);
 
     // Fill gaps between sections.
     if (nonZeroFiller) {
       uint8_t *start = buf + isec->outSecOff + isec->getSize();
       uint8_t *end;
       if (i + 1 == sections.size())
         end = buf + size;
       else
         end = buf + sections[i + 1]->outSecOff;
       if (isec->nopFiller) {
         assert(target->nopInstrs);
         nopInstrFill(start, end - start);
       } else
         fill(start, end - start, filler);
     }
-  });
+  };
+  if (parallel) {
+    lld_parallel_for_each_n(0, (int)sections.size(), [&](size_t i) { fn(i); });
+  } else {
+    for (size_t i = 0, e = sections.size(); i != e; ++i)
+      fn(i);
+  }
 
   // Linker scripts may have BYTE()-family commands with which you
   // can write arbitrary bytes to the output. Process them if any.
   for (SectionCommand *cmd : commands)
     if (auto *data = dyn_cast<ByteCommand>(cmd))
       writeInt(buf + data->offset, data->expression().getValue(), data->size);
 }
 
void OutputSection::checkDynRelAddends(const uint8_t *bufStart) {
   });
 }
 
 template void OutputSection::writeHeaderTo<ELF32LE>(ELF32LE::Shdr *Shdr);
 template void OutputSection::writeHeaderTo<ELF32BE>(ELF32BE::Shdr *Shdr);
 template void OutputSection::writeHeaderTo<ELF64LE>(ELF64LE::Shdr *Shdr);
 template void OutputSection::writeHeaderTo<ELF64BE>(ELF64BE::Shdr *Shdr);
 
-template void OutputSection::writeTo<ELF32LE>(uint8_t *Buf);
-template void OutputSection::writeTo<ELF32BE>(uint8_t *Buf);
-template void OutputSection::writeTo<ELF64LE>(uint8_t *Buf);
-template void OutputSection::writeTo<ELF64BE>(uint8_t *Buf);
+template void OutputSection::writeTo<ELF32LE>(uint8_t *, bool);
+template void OutputSection::writeTo<ELF32BE>(uint8_t *, bool);
+template void OutputSection::writeTo<ELF64LE>(uint8_t *, bool);
+template void OutputSection::writeTo<ELF64BE>(uint8_t *, bool);
 
 template void OutputSection::maybeCompress<ELF32LE>();
 template void OutputSection::maybeCompress<ELF32BE>();
 template void OutputSection::maybeCompress<ELF64LE>();
 template void OutputSection::maybeCompress<ELF64BE>();

lld/ELF/Writer.cpp

for (PhdrEntry *p : part.phdrs)
         last = p;
 
     if (last && (last->p_flags & PF_X))
       last->p_memsz = last->p_filesz =
           alignTo(last->p_filesz, config->maxPageSize);
   }
 }
 
+static bool shouldParallel(const OutputSection *osec) {
+  if (osec->commands.size() != 1)
+    return false;
+  if (auto *isd = dyn_cast<InputSectionDescription>(osec->commands[0]))
+    return isd->sections.size() == 1 &&
+           !isa<MergeSyntheticSection>(isd->sections[0]);
+  return false;
+}
+
 // Write section contents to a mmap'ed file.
 template <class ELFT> void Writer<ELFT>::writeSections() {
   llvm::TimeTraceScope timeScope("Write sections");
 
   // In -r or --emit-relocs mode, write the relocation sections first as in
   // ELf_Rel targets we might find out that we need to modify the relocated
   // section while doing it.
   for (OutputSection *sec : outputSections)
     if (sec->type == SHT_REL || sec->type == SHT_RELA)
       sec->writeTo<ELFT>(Out::bufferStart + sec->offset);
 
+  SmallVector<OutputSection *, 0> vec;
   for (OutputSection *sec : outputSections)
-    if (sec->type != SHT_REL && sec->type != SHT_RELA)
+    if (sec->type != SHT_REL && sec->type != SHT_RELA) {
+      if (shouldParallel(sec))
+        vec.push_back(sec);
+      else
         sec->writeTo<ELFT>(Out::bufferStart + sec->offset);
+    }
+  parallelForEach(vec, [](OutputSection *sec) {
+    sec->writeTo<ELFT>(Out::bufferStart + sec->offset, false);
+  });
 
   // Finally, check that all dynamic relocation addends were written correctly.
   if (config->checkDynamicRelocs && config->writeAddends) {
     for (OutputSection *sec : outputSections)
       if (sec->type == SHT_REL || sec->type == SHT_RELA)
         sec->checkDynRelAddends(Out::bufferStart);
   }
 }