[dsymutil] Reduce peak memory usage for the single threaded execution.

[JDevlieghere]

Summary

Keeping the compile units in memory is expensive. For the single threaded case we allocate them in the analyze part and deallocate them again once we've finished cloning. This poses a problem in the single threaded case where we did all the analysis first followed by all the cloning. This meant we had all the link context in memory right after analyzing finished.

This patch changes the way we order work in the single threaded case. Instead of doing all the analysis and cloning in serial, we now interleave the two so we can deallocate the memory as soon as a file is processed. The result is binary identical and peak memory usage went down from 13.43GB to 5.73GB for a debug build of trunk clang.

[aprantl]

It would be good to document in the man page that -j >1 uses more memory.

llvm/tools/dsymutil/DwarfLinker.cpp

2486–2489

... so it is being run in parallel with emitting the previous compile unit.

2620

... analyze and clone are run sequentially, so the LinkContext may be freed.
where is this actually happening?

[JDevlieghere]

• Address Adrian's feedback.

llvm/tools/dsymutil/DwarfLinker.cpp

2620

We clear the context in endDebugObject.

[aprantl]

llvm/tools/dsymutil/DwarfLinker.cpp

2620

The let's spell this out in the comment: ... analyze and clone are run sequentially, so the LinkContext is freed after processing each object in endDebugObject()..

[JDevlieghere]

Rephrase comment to Adrian's suggestion.

[friss]

llvm/tools/dsymutil/DwarfLinker.cpp

2554–2556

Is that just a reformatting? Can you remove it from the patch if so?

2620–2625

This loop doesn't have the LinkContext.Objectfile check which was in CloneLambda before and is in CloneAll. Would it be cleaner to pass a LinkContext to the lambdas and leave the logic there?

[JDevlieghere]

llvm/tools/dsymutil/DwarfLinker.cpp

2554–2556

This is the result of moving this code out of the loop and having one level less of indentation.

2620–2625

That check was moved into the AnalyzeLambda so it still happens, unless you're talking about something else?

[friss]

llvm/tools/dsymutil/DwarfLinker.cpp

2620–2625

Previously CloneLambda would return early if LinkContext.Objectfile was null. Now, in the single threaded case, it will process the object file. I'm not sure something bad can happen, but it's a logic change.

[JDevlieghere]

Move null-check into CloneLambda.

[JDevlieghere]

llvm/tools/dsymutil/DwarfLinker.cpp

2620–2625

Aha, I see, I moved it for analyzeLambda but not for the cloneLambda. Good catch, this would've segfaulted!

[friss]

LGTM

llvm/docs/CommandGuide/dsymutil.rst

 
 .. option:: --no-swiftmodule-timestamp
 
  Don't check the timestamp for swiftmodule files.
 
 .. option:: -j <n>, --num-threads=<n>
 
  Specifies the maximum number (``n``) of simultaneous threads to use when
- linking multiple architectures.
+ linking multiple architectures. Note that multithreading may use more memory.
 
 .. option:: -o <filename>
 
  Specifies an alternate ``path`` to place the dSYM bundle. The default dSYM
  bundle path is created by appending ``.dSYM`` to the executable name.
 
 .. option:: --oso-prepend-path=<path>
 

llvm/tools/dsymutil/DwarfLinker.cpp

if (MaxDwarfVersion == 0)
     MaxDwarfVersion = 3;
 
   // 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.
-  auto AnalyzeLambda = [&]() {
-    for (unsigned i = 0, e = NumObjects; i != e; ++i) {
-      auto &LinkContext = ObjectContexts[i];
+  //  Analyzing the context info is particularly expensive so it is executed in
+  //  parallel with emitting the previous compile unit.
+  auto AnalyzeLambda = [&](size_t i) {
 
-      if (!LinkContext.ObjectFile || !LinkContext.DwarfContext) {
-        std::unique_lock<std::mutex> LockGuard(ProcessedFilesMutex);
-        ProcessedFiles.set(i);
-        ProcessedFilesConditionVariable.notify_one();
-        continue;
-      }
+    if (!LinkContext.ObjectFile || !LinkContext.DwarfContext)
+      return;
 
-      for (const auto &CU : LinkContext.DwarfContext->compile_units()) {
-        updateDwarfVersion(CU->getVersion());
-        // The !registerModuleReference() condition effectively skips
-        // over fully resolved skeleton units. This second pass of
-        // registerModuleReferences doesn't do any new work, but it
-        // will collect top-level errors, which are suppressed. Module
-        // warnings were already displayed in the first iteration.
-        bool Quiet = true;
-        auto CUDie = CU->getUnitDIE(false);
-        if (!CUDie || LLVM_UNLIKELY(Options.Update) ||
-            !registerModuleReference(CUDie, *CU, ModuleMap, LinkContext.DMO,
-                                     LinkContext.Ranges, OffsetsStringPool,
-                                     UniquingStringPool, ODRContexts, UnitID,
-                                     Quiet)) {
-          LinkContext.CompileUnits.push_back(llvm::make_unique<CompileUnit>(
-              *CU, UnitID++, !Options.NoODR && !Options.Update, ""));
-        }
-      }
-      
-      // Now build the DIE parent links that we will use during the next phase.
-      for (auto &CurrentUnit : LinkContext.CompileUnits) {
-        auto CUDie = CurrentUnit->getOrigUnit().getUnitDIE();
-        if (!CUDie)
-          continue;
-        analyzeContextInfo(CurrentUnit->getOrigUnit().getUnitDIE(), 0,
-                           *CurrentUnit, &ODRContexts.getRoot(),
-                           UniquingStringPool, ODRContexts);
-      }
-
-      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.
-  auto CloneLambda = [&]() {
-    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;
+  auto CloneLambda = [&](size_t i) {
 
-      // 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);
-      } 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.
-      LinkContext.RelocMgr.resetValidRelocs();
-      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());
+    if (LinkContext.RelocMgr.hasValidRelocs() || LLVM_UNLIKELY(Options.Update))
+      DIECloner(*this, LinkContext.RelocMgr, DIEAlloc, LinkContext.CompileUnits,
+                Options)
 
-      // Clean-up before starting working on the next object.
-      endDebugObject(LinkContext);
-    }
+  };
 
+  auto EmitLambda = [&]() {
     // Emit everything that's global.
     if (!Options.NoOutput) {
       Streamer->emitAbbrevs(Abbreviations, MaxDwarfVersion);
       Streamer->emitStrings(OffsetsStringPool);
       switch (Options.TheAccelTableKind) {
       case AccelTableKind::Apple:
         Streamer->emitAppleNames(AppleNames);
         Streamer->emitAppleNamespaces(AppleNamespaces);
         Streamer->emitAppleTypes(AppleTypes);
         Streamer->emitAppleObjc(AppleObjc);
         break;
       case AccelTableKind::Dwarf:
         Streamer->emitDebugNames(DebugNames);
         break;
       case AccelTableKind::Default:
         llvm_unreachable("Default should have already been resolved.");
         break;
       }
     }
   };
 
-  // FIXME: The DwarfLinker can have some very deep recursion that can max
-  // out the (significantly smaller) stack when using threads. We don't
-  // want this limitation when we only have a single thread.
+  auto AnalyzeAll = [&]() {
+    for (unsigned i = 0, e = NumObjects; i != e; ++i) {
+      AnalyzeLambda(i);
+
+      std::unique_lock<std::mutex> LockGuard(ProcessedFilesMutex);
+      ProcessedFiles.set(i);
+      ProcessedFilesConditionVariable.notify_one();
+    }
+  };
+
+  auto CloneAll = [&]() {
+    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]; });
+        }
+      }
+
+      CloneLambda(i);
+    }
+    EmitLambda();
+  };
+
+  // To limit memory usage in the single threaded case, analyze and clone are
+  // run sequentially so the LinkContext is freed after processing each object
+  // in endDebugObject.
   if (Options.Threads == 1) {
-    AnalyzeLambda();
-    CloneLambda();
+    for (unsigned i = 0, e = NumObjects; i != e; ++i) {
+      AnalyzeLambda(i);
+      CloneLambda(i);
+    }
+    EmitLambda();
   } else {
     ThreadPool pool(2);
-    pool.async(AnalyzeLambda);
-    pool.async(CloneLambda);
+    pool.async(AnalyzeAll);
+    pool.async(CloneAll);
     pool.wait();
   }
 
   return Options.NoOutput ? true : Streamer->finish(Map);
 } // namespace dsymutil
 
 bool linkDwarf(raw_fd_ostream &OutFile, BinaryHolder &BinHolder,
                const DebugMap &DM, const LinkOptions &Options) {
   DwarfLinker Linker(OutFile, BinHolder, Options);
   return Linker.link(DM);
 }
 
 } // namespace dsymutil
 } // namespace llvm