[dsymutil] Perform analyzeContextInfo and CloneDIEs in parallel

[JDevlieghere]

Summary

This patch makes dsymutil perform analyzeContextInfo and CloneDIEs in
parallel. For the same object file, there is a dependency between the two.
However, we can do analyzeContextInfo for the next object file while cloning
DIEs for the current. This is exactly the approach taken in this patch.

For WebCore, this leads to a performance improvement of 29% and for clang we
see similar results with at 32% improvement.

A large part of the change is related to passing around objects during linking,
instead of having one "current" counterpart accessible by all the linker's
methods. We group these objects into a new struct called LinkContext which
exists for every object file.

A big thanks to Pete Cooper (@pete) who came up with the idea and a PoC.

---------------------------------------------
WebCore (before)
---------------------------------------------
78.13 real        72.85 user         4.80 sys
77.92 real        72.75 user         4.87 sys
77.91 real        72.69 user         4.91 sys
78.38 real        73.01 user         5.00 sys
79.48 real        73.99 user         5.03 sys
---------------------------------------------
78.36 real
---------------------------------------------

---------------------------------------------
WebCore (after)
---------------------------------------------
55.22 real        74.76 user         6.16 sys
54.22 real        73.72 user         5.89 sys
55.13 real        74.62 user         6.02 sys
55.83 real        74.89 user         6.49 sys
54.87 real        74.23 user         6.10 sys
---------------------------------------------
55.05 real
---------------------------------------------

---------------------------------------------
Clang (before)
---------------------------------------------
82.16 real        78.16 user         3.61 sys
82.92 real        78.79 user         3.69 sys
84.59 real        79.85 user         3.95 sys
84.45 real        79.80 user         3.93 sys
85.11 real        80.23 user         4.07 sys
---------------------------------------------
83.85 real
---------------------------------------------

---------------------------------------------
Clang (after)
---------------------------------------------
56.28 real        81.32 user         6.53 sys
56.04 real        81.24 user         6.39 sys
56.65 real        81.42 user         6.36 sys
57.06 real        81.75 user         6.89 sys
55.65 real        80.40 user         6.59 sys
---------------------------------------------
56.34 real
---------------------------------------------

[friss]

The results looks great! I haven't looked at the patches themselves, but I suppose this patch should have no impact on the output itself. Did you check if your resulting linked DWARF is exactly identical to the one before the patch?

[JDevlieghere]

• Added default argument for Verbose
• Added comment explaining the need for strong types.

[JDevlieghere]

In D43945#1023800, @friss wrote:

The results looks great! I haven't looked at the patches themselves, but I suppose this patch should have no impact on the output itself. Did you check if your resulting linked DWARF is exactly identical to the one before the patch?

Yes, I compared the MD5 hashes for clang and they were identical.

[JDevlieghere]

• Full context diff

[aprantl]

As far as I can tell this looks very good, thanks! Fred may have more to say about the algorithmic side.

tools/dsymutil/DwarfLinker.cpp

1421 ↗

(On Diff #136542)

maybe use a struct instead of a pair for better readability? Up to you.

2317 ↗

(On Diff #136542)

why does this string need to start with a space?

4111 ↗

(On Diff #136542)

could skip the braces

[JDevlieghere]

• Feedback Adrian

[friss]

It would be nice to land this in 2 commits, one NFC that does the refactoring up to creating the LinkContext and the other one that introduces the parallel processing. Otherwise, LGTM

[JDevlieghere]

In D43945#1035464, @friss wrote:

It would be nice to land this in 2 commits, one NFC that does the refactoring up to creating the LinkContext and the other one that introduces the parallel processing. Otherwise, LGTM

Landed LinkContext in rL327382.

llvm/trunk/test/tools/dsymutil/basic-linking.test

 RUN: llvm-dsymutil -no-output -verbose -oso-prepend-path=%p %p/Inputs/basic.macho.x86_64 | FileCheck %s
 RUN: llvm-dsymutil -no-output -verbose -oso-prepend-path=%p %p/Inputs/basic-lto.macho.x86_64 | FileCheck %s --check-prefix=CHECK-LTO
 RUN: llvm-dsymutil -no-output -verbose -oso-prepend-path=%p %p/Inputs/basic-archive.macho.x86_64 | FileCheck %s --check-prefix=CHECK-ARCHIVE
-RUN: llvm-dsymutil -no-output -verbose -oso-prepend-path=%p %p/Inputs/basic.macho.x86_64 %p/Inputs/basic-lto.macho.x86_64 %p/Inputs/basic-archive.macho.x86_64 | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-LTO --check-prefix=CHECK-ARCHIVE 
+RUN: llvm-dsymutil -no-output -verbose -oso-prepend-path=%p %p/Inputs/basic.macho.x86_64 %p/Inputs/basic-lto.macho.x86_64 %p/Inputs/basic-archive.macho.x86_64 | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-LTO --check-prefix=CHECK-ARCHIVE
 
 This test check the basic Dwarf linking process through the debug dumps.
 
 ================================= Simple link ================================
 CHECK: DEBUG MAP OBJECT: {{.*}}basic1.macho.x86_64.o
 CHECK: Input compilation unit:
 CHECK-NEXT: TAG_compile_unit
 CHECK-NOT: TAG
 CHECK: AT_name {{.*}}basic1.c
-CHECK-NOT: Found valid debug map entry
-CHECK: Found valid debug map entry: _main   0000000000000000 => 0000000100000ea0
-CHECK-NEXT: DW_TAG_subprogram
-CHECK-NEXT:   DW_AT_name{{.*}}"main"
 
 CHECK: DEBUG MAP OBJECT: {{.*}}basic2.macho.x86_64.o
 CHECK: Input compilation unit:
 CHECK-NEXT: TAG_compile_unit
 CHECK-NOT: TAG
 CHECK: AT_name {{.*}}basic2.c
+
+CHECK: DEBUG MAP OBJECT: {{.*}}basic3.macho.x86_64.o
+CHECK: Input compilation unit:
+CHECK-NEXT: TAG_compile_unit
+CHECK-NOT: TAG
+CHECK: AT_name {{.*}}basic3.c
+
 CHECK-NOT: Found valid debug map entry
+CHECK: Found valid debug map entry: _main   0000000000000000 => 0000000100000ea0
+CHECK-NEXT: DW_TAG_subprogram
+CHECK-NEXT:   DW_AT_name{{.*}}"main"
+
 CHECK: Found valid debug map entry: _private_int  0000000000000560 => 0000000100001008
 CHECK-NEXT: DW_TAG_variable
 CHECK-NEXT:   DW_AT_name {{.*}}"private_int"
 CHECK-NOT: Found valid debug map entry
 CHECK: Found valid debug map entry: _baz  0000000000000310 => 0000000100001000
 CHECK-NEXT: DW_TAG_variable
 CHECK-NEXT:   DW_AT_name {{.*}}"baz"
 CHECK-NOT: Found valid debug map entry
 CHECK: Found valid debug map entry: _foo  0000000000000020 => 0000000100000ed0
 CHECK-NEXT: DW_TAG_subprogram
 CHECK-NEXT:   DW_AT_name {{.*}}"foo"
 CHECK-NOT: Found valid debug map entry
 CHECK: Found valid debug map entry: _inc  0000000000000070 => 0000000100000f20
 CHECK-NEXT: DW_TAG_subprogram
 CHECK-NEXT:   DW_AT_name {{.*}}"inc"
 
-CHECK: DEBUG MAP OBJECT: {{.*}}basic3.macho.x86_64.o
-CHECK: Input compilation unit:
-CHECK-NEXT: TAG_compile_unit
-CHECK-NOT: TAG
-CHECK: AT_name {{.*}}basic3.c
 CHECK-NOT: Found valid debug map entry
 CHECK: Found valid debug map entry: _val  ffffffffffffffff => 0000000100001004
 CHECK-NEXT: DW_TAG_variable
 CHECK-NEXT:   DW_AT_name {{.*}}"val"
 CHECK-NOT: Found valid debug map entry
 CHECK: Found valid debug map entry: _bar  0000000000000020 => 0000000100000f40
 CHECK-NEXT: DW_TAG_subprogram
 CHECK-NEXT:   DW_AT_name {{.*}}"bar"

 
 
 ================================= Archive link ================================
 CHECK-ARCHIVE: DEBUG MAP OBJECT: {{.*}}basic1.macho.x86_64.o
 CHECK-ARCHIVE: Input compilation unit:
 CHECK-ARCHIVE-NEXT: TAG_compile_unit
 CHECK-ARCHIVE-NOT: TAG
 CHECK-ARCHIVE: AT_name {{.*}}basic1.c
-CHECK-ARCHIVE-NOT: Found valid debug map entry
-CHECK-ARCHIVE: Found valid debug map entry: _main   0000000000000000 => 0000000100000ea0
-CHECK-ARCHIVE-NEXT: DW_TAG_subprogram
-CHECK-ARCHIVE-NEXT:   DW_AT_name{{.*}}"main"
 
 CHECK-ARCHIVE: DEBUG MAP OBJECT: {{.*}}libbasic.a(basic2.macho.x86_64.o)
 CHECK-ARCHIVE: Input compilation unit:
 CHECK-ARCHIVE-NEXT: TAG_compile_unit
 CHECK-ARCHIVE-NOT: TAG
 CHECK-ARCHIVE: AT_name {{.*}}basic2.c
+
+CHECK-ARCHIVE: DEBUG MAP OBJECT: {{.*}}libbasic.a(basic3.macho.x86_64.o)
+CHECK-ARCHIVE: Input compilation unit:
+CHECK-ARCHIVE-NEXT: TAG_compile_unit
+CHECK-ARCHIVE-NOT: TAG
+CHECK-ARCHIVE: AT_name {{.*}}basic3.c
+
+CHECK-ARCHIVE-NOT: Found valid debug map entry
+CHECK-ARCHIVE: Found valid debug map entry: _main   0000000000000000 => 0000000100000ea0
+CHECK-ARCHIVE-NEXT: DW_TAG_subprogram
+CHECK-ARCHIVE-NEXT:   DW_AT_name{{.*}}"main"
+
 CHECK-ARCHIVE-NOT: Found valid debug map entry
 CHECK-ARCHIVE: Found valid debug map entry: _private_int  0000000000000560 => 0000000100001004
 CHECK-ARCHIVE-NEXT: DW_TAG_variable
 CHECK-ARCHIVE-NEXT:   DW_AT_name {{.*}}"private_int"
 CHECK-ARCHIVE-NOT: Found valid debug map entry
 CHECK-ARCHIVE: Found valid debug map entry: _baz  0000000000000310 => 0000000100001000
 CHECK-ARCHIVE-NEXT: DW_TAG_variable
 CHECK-ARCHIVE-NEXT:   DW_AT_name {{.*}}"baz"
 CHECK-ARCHIVE-NOT: Found valid debug map entry
 CHECK-ARCHIVE: Found valid debug map entry: _foo  0000000000000020 => 0000000100000ed0
 CHECK-ARCHIVE-NEXT: DW_TAG_subprogram
 CHECK-ARCHIVE-NEXT:   DW_AT_name {{.*}}"foo"
 CHECK-ARCHIVE-NOT: Found valid debug map entry
 CHECK-ARCHIVE: Found valid debug map entry: _inc  0000000000000070 => 0000000100000f20
 CHECK-ARCHIVE-NEXT: DW_TAG_subprogram
 CHECK-ARCHIVE-NEXT:   DW_AT_name {{.*}}"inc"
 
-CHECK-ARCHIVE: DEBUG MAP OBJECT: {{.*}}libbasic.a(basic3.macho.x86_64.o)
-CHECK-ARCHIVE: Input compilation unit:
-CHECK-ARCHIVE-NEXT: TAG_compile_unit
-CHECK-ARCHIVE-NOT: TAG
-CHECK-ARCHIVE: AT_name {{.*}}basic3.c
 CHECK-ARCHIVE-NOT: Found valid debug map entry
 CHECK-ARCHIVE: Found valid debug map entry: _val  ffffffffffffffff => 0000000100001008
 CHECK-ARCHIVE-NEXT: DW_TAG_variable
 CHECK-ARCHIVE-NEXT:   DW_AT_name {{.*}}"val"
 CHECK-ARCHIVE-NOT: Found valid debug map entry
 CHECK-ARCHIVE: Found valid debug map entry: _bar  0000000000000020 => 0000000100000f40
 CHECK-ARCHIVE-NEXT: DW_TAG_subprogram
 CHECK-ARCHIVE-NEXT:   DW_AT_name {{.*}}"bar"
 CHECK-ARCHIVE-NOT: Found valid debug map entry
 CHECK-ARCHIVE: Found valid debug map entry: _inc  0000000000000070 => 0000000100000f90
 CHECK-ARCHIVE-NEXT: DW_TAG_subprogram
 CHECK-ARCHIVE-NEXT:   DW_AT_name {{.*}}"inc")

llvm/trunk/tools/dsymutil/DwarfLinker.cpp

 //===- tools/dsymutil/DwarfLinker.cpp - Dwarf debug info linker -----------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "BinaryHolder.h"
 #include "DebugMap.h"
 #include "MachOUtils.h"
 #include "NonRelocatableStringpool.h"
 #include "dsymutil.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/IntervalMap.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"

 #include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/LEB128.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/TargetRegistry.h"
+#include "llvm/Support/ThreadPool.h"
 #include "llvm/Support/ToolOutputFile.h"
 #include "llvm/Support/WithColor.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetOptions.h"
 #include <algorithm>
 #include <cassert>
 #include <cinttypes>
if (!createStreamer(Map.getTriple(), OutFile))
     return false;
 
   // Size of the DIEs (and headers) generated for the linked output.
   OutputDebugInfoSize = 0;
   // A unique ID that identifies each compile unit.
   unsigned UnitID = 0;
   DebugMap ModuleMap(Map.getTriple(), Map.getBinaryPath());
 
+  // First populate the data structure we need for each iteration of the
+  // parallel loop.
+  unsigned NumObjects = Map.getNumberOfObjects();
+  std::vector<LinkContext> ObjectContexts;
+  ObjectContexts.reserve(NumObjects);
+  for (const auto &Obj : Map.objects())
+    ObjectContexts.emplace_back(Map, *this, *Obj.get(), Options.Verbose);
+
   // This Dwarf string pool which is only used for uniquing. This one should
   // never be used for offsets as its not thread-safe or predictable.
   UniquingStringPool UniquingStringPool;
 
   // This Dwarf string pool which is used for emission. It must be used
   // serially as the order of calling getStringOffset matters for
   // reproducibility.
   OffsetsStringPool OffsetsStringPool;
 
   // ODR Contexts for the link.
   DeclContextTree ODRContexts;
 
-  for (const auto &Obj : Map.objects()) {
-    LinkContext LinkContext(Map, *this, *Obj.get(), Options.Verbose);
-
+  for (LinkContext &LinkContext : ObjectContexts) {
     if (Options.Verbose)
-      outs() << "DEBUG MAP OBJECT: " << Obj->getObjectFilename() << "\n";
+      outs() << "DEBUG MAP OBJECT: " << LinkContext.DMO.getObjectFilename()
+             << "\n";
 
     // N_AST objects (swiftmodule files) should get dumped directly into the
     // appropriate DWARF section.
     if (LinkContext.DMO.getType() == MachO::N_AST) {
       StringRef File = LinkContext.DMO.getObjectFilename();
       auto ErrorOrMem = MemoryBuffer::getFile(File);
       if (!ErrorOrMem) {
         errs() << "Warning: Could not open " << File << "\n";
if (LinkContext.DMO.getType() == MachO::N_AST) {
 
       // Copy the module into the .swift_ast section.
       if (!Options.NoOutput)
         Streamer->emitSwiftAST((*ErrorOrMem)->getBuffer());
       continue;
     }
 
     if (!LinkContext.ObjectFile)
+
       continue;
 
     // Look for relocations that correspond to debug map entries.
+
     if (LLVM_LIKELY(!Options.Update) &&
         !LinkContext.RelocMgr.findValidRelocsInDebugInfo(
             *LinkContext.ObjectFile, LinkContext.DMO)) {
       if (Options.Verbose)
-        warn("No valid relocations found: skipping\n");
+        outs() << "No valid relocations found. Skipping.\n";
+
+      // Clear this ObjFile entry as a signal to other loops that we should not
+      // process this iteration.
+      LinkContext.ObjectFile = nullptr;
       continue;
     }
 
     // Setup access to the debug info.
     if (!LinkContext.DwarfContext)
       continue;
 
+    startDebugObject(LinkContext);
+
     // In a first phase, just read in the debug info and load all clang modules.
     LinkContext.CompileUnits.reserve(
         LinkContext.DwarfContext->getNumCompileUnits());
     for (const auto &CU : LinkContext.DwarfContext->compile_units()) {
       auto CUDie = CU->getUnitDIE(false);
       if (Options.Verbose) {
         outs() << "Input compilation unit:";
         DIDumpOptions DumpOpts;
         DumpOpts.RecurseDepth = 0;
         DumpOpts.Verbose = Options.Verbose;
         CUDie.dump(outs(), 0, DumpOpts);
       }
 
       if (!CUDie || LLVM_UNLIKELY(Options.Update) ||
           !registerModuleReference(CUDie, *CU, ModuleMap, LinkContext.DMO,
                                    LinkContext.Ranges, OffsetsStringPool,
                                    UniquingStringPool, ODRContexts, UnitID)) {
         LinkContext.CompileUnits.push_back(llvm::make_unique<CompileUnit>(
             *CU, UnitID++, !Options.NoODR && !Options.Update, ""));
         maybeUpdateMaxDwarfVersion(CU->getVersion());
       }
     }
+  }
+
+  ThreadPool pool(2);
+
+  // These variables manage the list of processed object files.
+  // The mutex and condition variable are to ensure that this is thread safe.
+  std::mutex ProcessedFilesMutex;
+  std::condition_variable ProcessedFilesConditionVariable;
+  BitVector ProcessedFiles(NumObjects, false);
+
+  // Now do analyzeContextInfo in parallel as it is particularly expensive.
+  pool.async([&]() {
+    for (unsigned i = 0, e = NumObjects; i != e; ++i) {
+      auto &LinkContext = ObjectContexts[i];
+
+      if (!LinkContext.ObjectFile) {
+        std::unique_lock<std::mutex> LockGuard(ProcessedFilesMutex);
+        ProcessedFiles.set(i);
+        ProcessedFilesConditionVariable.notify_one();
+        continue;
+      }
 
       // Now build the DIE parent links that we will use during the next phase.
       for (auto &CurrentUnit : LinkContext.CompileUnits)
         analyzeContextInfo(CurrentUnit->getOrigUnit().getUnitDIE(), 0,
                            *CurrentUnit, &ODRContexts.getRoot(),
                            UniquingStringPool, ODRContexts);
 
-    // Then mark all the DIEs that need to be present in the linked
-    // output and collect some information about them. Note that this
-    // loop can not be merged with the previous one because cross-CU
-    // references require the ParentIdx to be setup for every CU in
+      std::unique_lock<std::mutex> LockGuard(ProcessedFilesMutex);
+      ProcessedFiles.set(i);
+      ProcessedFilesConditionVariable.notify_one();
+    }
+  });
+
+  // And then the remaining work in serial again.
+  // Note, although this loop runs in serial, it can run in parallel with
+  // the analyzeContextInfo loop so long as we process files with indices >=
+  // than those processed by analyzeContextInfo.
+  pool.async([&]() {
+    for (unsigned i = 0, e = NumObjects; i != e; ++i) {
+      {
+        std::unique_lock<std::mutex> LockGuard(ProcessedFilesMutex);
+        if (!ProcessedFiles[i]) {
+          ProcessedFilesConditionVariable.wait(
+              LockGuard, [&]() { return ProcessedFiles[i]; });
+        }
+      }
+
+      auto &LinkContext = ObjectContexts[i];
+      if (!LinkContext.ObjectFile)
+        continue;
+
+      // Then mark all the DIEs that need to be present in the linked output
+      // and collect some information about them.
+      // Note that this loop can not be merged with the previous one because
+      // cross-cu references require the ParentIdx to be setup for every CU in
       // the object file before calling this.
       if (LLVM_UNLIKELY(Options.Update)) {
         for (auto &CurrentUnit : LinkContext.CompileUnits)
           CurrentUnit->markEverythingAsKept();
         Streamer->copyInvariantDebugSection(*LinkContext.ObjectFile, Options);
       } else {
         for (auto &CurrentUnit : LinkContext.CompileUnits)
           lookForDIEsToKeep(LinkContext.RelocMgr, LinkContext.Ranges,
                             LinkContext.CompileUnits,
                             CurrentUnit->getOrigUnit().getUnitDIE(),
                             LinkContext.DMO, *CurrentUnit, 0);
       }
 
-    // The calls to applyValidRelocs inside cloneDIE will walk the
-    // reloc array again (in the same way findValidRelocsInDebugInfo()
-    // did). We need to reset the NextValidReloc index to the beginning.
+      // The calls to applyValidRelocs inside cloneDIE will walk the reloc
+      // array again (in the same way findValidRelocsInDebugInfo() did). We
+      // need to reset the NextValidReloc index to the beginning.
       LinkContext.RelocMgr.resetValidRelocs();
-    if (LinkContext.RelocMgr.hasValidRelocs() || LLVM_UNLIKELY(Options.Update))
-      DIECloner(*this, LinkContext.RelocMgr, DIEAlloc, LinkContext.CompileUnits,
-                Options)
+      if (LinkContext.RelocMgr.hasValidRelocs() ||
+          LLVM_UNLIKELY(Options.Update))
+        DIECloner(*this, LinkContext.RelocMgr, DIEAlloc,
+                  LinkContext.CompileUnits, Options)
             .cloneAllCompileUnits(*LinkContext.DwarfContext, LinkContext.DMO,
                                   LinkContext.Ranges, OffsetsStringPool);
       if (!Options.NoOutput && !LinkContext.CompileUnits.empty() &&
           LLVM_LIKELY(!Options.Update))
         patchFrameInfoForObject(
             LinkContext.DMO, LinkContext.Ranges, *LinkContext.DwarfContext,
             LinkContext.CompileUnits[0]->getOrigUnit().getAddressByteSize());
 
       // Clean-up before starting working on the next object.
       endDebugObject(LinkContext);
     }
 
     // Emit everything that's global.
     if (!Options.NoOutput) {
       Streamer->emitAbbrevs(Abbreviations, MaxDwarfVersion);
       Streamer->emitStrings(OffsetsStringPool);
       Streamer->emitAppleNames(AppleNames);
       Streamer->emitAppleNamespaces(AppleNamespaces);
       Streamer->emitAppleTypes(AppleTypes);
       Streamer->emitAppleObjc(AppleObjc);
     }
+  });
+
+  pool.wait();
 
   return Options.NoOutput ? true : Streamer->finish(Map);
 }
 
 void warn(const Twine &Warning, const Twine &Context) {
   errs() << Twine("while processing ") + Context + ":\n";
   errs() << Twine("warning: ") + Warning + "\n";
 }