[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

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

2317

why does this string need to start with a space?

4111

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.

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")

tools/dsymutil/DebugMap.h

public:
   iterator_range<const_iterator> objects() const {
     return make_range(begin(), end());
   }
 
   const_iterator begin() const { return Objects.begin(); }
 
   const_iterator end() const { return Objects.end(); }
 
+  unsigned getNumberOfObjects() const { return Objects.size(); }
+
   /// This function adds an DebugMapObject to the list owned by this
   /// debug map.
   DebugMapObject &
   addDebugMapObject(StringRef ObjectFilePath,
                     sys::TimePoint<std::chrono::seconds> Timestamp,
                     uint8_t Type = llvm::MachO::N_OSO);
 
   const Triple &getTriple() const { return BinaryTriple; }

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/raw_ostream.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetOptions.h"
 #include <algorithm>
 #include <cassert>
 #include <cinttypes>
 #include <climits>

 #include <utility>
 #include <vector>
 
 namespace llvm {
 namespace dsymutil {
 
 namespace {
 
+/// Helper for making strong types.
+template <typename T, typename S> class StrongType : public T {
+public:
+  template <typename... Args>
+  explicit StrongType(Args... A) : T(std::forward<Args>(A)...) {}
+};
+
+/// It's very easy to introduce bugs by passing the wrong string pool. By using
+/// strong types the interface enforces that the right kind of pool is used.
+struct UniqueTag {};
+struct OffsetsTag {};
+using UniquingStringPool = StrongType<NonRelocatableStringpool, UniqueTag>;
+using OffsetsStringPool = StrongType<NonRelocatableStringpool, OffsetsTag>;
+
 /// Small helper that resolves and caches file paths. This helps reduce the
 /// number of calls to realpath which is expensive. We assume the input are
 /// files, and cache the realpath of their parent. This way we can quickly
 /// resolve different files under the same path.
 class CachedPathResolver {
 public:
   /// Resolve a path by calling realpath and cache its result. The returned
   /// StringRef is interned in the given \p StringPool.
public:
   /// An invalid context means it shouldn't be considered for uniquing, but its
   /// not returning null, because some children of that context might be
   /// uniquing candidates.
   ///
   /// FIXME: The invalid bit along the return value is to emulate some
   /// dsymutil-classic functionality.
   PointerIntPair<DeclContext *, 1>
   getChildDeclContext(DeclContext &Context, const DWARFDie &DIE,
-                      CompileUnit &Unit, NonRelocatableStringpool &StringPool,
+                      CompileUnit &Unit, UniquingStringPool &StringPool,
                       bool InClangModule);
 
   DeclContext &getRoot() { return Root; }
 };
 
 /// Stores all information relating to a compile unit, be it in its original
 /// instance in the object file to its brand new cloned and linked DIE tree.
 class CompileUnit {
void DwarfStreamer::emitFDE(uint32_t CIEOffset, uint32_t AddrSize,
   MS->EmitIntValue(FDEBytes.size() + 4 + AddrSize, 4);
   MS->EmitIntValue(CIEOffset, 4);
   MS->EmitIntValue(Address, AddrSize);
   MS->EmitBytes(FDEBytes);
   FrameSectionSize += FDEBytes.size() + 8 + AddrSize;
 }
 
 namespace {
+/// This map is keyed by the entry PC of functions in that debug object and the
+/// associated value is a pair storing the corresponding end PC and the offset
+/// to apply to get the linked address.
+using RangesTy = std::map<uint64_t, std::pair<uint64_t, int64_t>>;
+
+using UnitListTy = std::vector<std::unique_ptr<CompileUnit>>;
 
 /// The core of the Dwarf linking logic.
 ///
 /// The link of the dwarf information from the object files will be
 /// driven by the selection of 'root DIEs', which are DIEs that
 /// describe variables or functions that are present in the linked
 /// binary (and thus have entries in the debug map). All the debug
 /// information that will be linked (the DIEs, but also the line
 /// tables, ranges, ...) is derived from that set of root DIEs.
 ///
 /// The root DIEs are identified because they contain relocations that
 /// correspond to a debug map entry at specific places (the low_pc for
 /// a function, the location for a variable). These relocations are
 /// called ValidRelocs in the DwarfLinker and are gathered as a very
 /// first step when we start processing a DebugMapObject.
 class DwarfLinker {
 public:
   DwarfLinker(raw_fd_ostream &OutFile, const LinkOptions &Options)
-      : OutFile(OutFile), Options(Options), BinHolder(Options.Verbose) {}
+      : OutFile(OutFile), Options(Options) {}
 
   /// Link the contents of the DebugMap.
   bool link(const DebugMap &);
 
-  void reportWarning(const Twine &Warning, const DWARFDie *DIE = nullptr) const;
+  void reportWarning(const Twine &Warning, const DebugMapObject &DMO,
+                     const DWARFDie *DIE = nullptr) const;
 
 private:
-  /// Called at the start of a debug object link.
-  void startDebugObject(DWARFContext &, DebugMapObject &);
-
-  /// Called at the end of a debug object link.
-  void endDebugObject();
-
   /// Remembers the newest DWARF version we've seen in a unit.
   void maybeUpdateMaxDwarfVersion(unsigned Version) {
     if (MaxDwarfVersion < Version)
       MaxDwarfVersion = Version;
   }
 
   /// Keeps track of relocations.
   class RelocationManager {
     struct ValidReloc {
       uint32_t Offset;
       uint32_t Size;
       uint64_t Addend;
       const DebugMapObject::DebugMapEntry *Mapping;
 
       ValidReloc(uint32_t Offset, uint32_t Size, uint64_t Addend,
                  const DebugMapObject::DebugMapEntry *Mapping)
           : Offset(Offset), Size(Size), Addend(Addend), Mapping(Mapping) {}
 
       bool operator<(const ValidReloc &RHS) const {
         return Offset < RHS.Offset;
       }
     };
 
-    DwarfLinker &Linker;
+    const DwarfLinker &Linker;
 
     /// The valid relocations for the current DebugMapObject.
     /// This vector is sorted by relocation offset.
     std::vector<ValidReloc> ValidRelocs;
 
     /// Index into ValidRelocs of the next relocation to consider. As we walk
     /// the DIEs in acsending file offset and as ValidRelocs is sorted by file
     /// offset, keeping this index up to date is all we have to do to have a
public:
 
     bool hasValidRelocation(uint32_t StartOffset, uint32_t EndOffset,
                             CompileUnit::DIEInfo &Info);
 
     bool applyValidRelocs(MutableArrayRef<char> Data, uint32_t BaseOffset,
                           bool isLittleEndian);
   };
 
+  /// Keeps track of data associated with one object during linking.
+  struct LinkContext {
+    DebugMapObject &DMO;
+    BinaryHolder BinaryHolder;
+    const object::ObjectFile *ObjectFile;
+    RelocationManager RelocMgr;
+    std::unique_ptr<DWARFContext> DwarfContext;
+    RangesTy Ranges;
+    UnitListTy CompileUnits;
+
+    LinkContext(const DebugMap &Map, DwarfLinker &Linker, DebugMapObject &DMO,
+                bool Verbose = false)
+        : DMO(DMO), BinaryHolder(Verbose), RelocMgr(Linker) {
+      auto ErrOrObj = Linker.loadObject(BinaryHolder, DMO, Map);
+      ObjectFile = ErrOrObj ? &*ErrOrObj : nullptr;
+      DwarfContext = ObjectFile ? DWARFContext::create(*ObjectFile) : nullptr;
+    }
+
+    /// Clear compile units and ranges.
+    void Clear() {
+      CompileUnits.clear();
+      Ranges.clear();
+    }
+  };
+
+  /// Called at the start of a debug object link.
+  void startDebugObject(LinkContext &Context);
+
+  /// Called at the end of a debug object link.
+  void endDebugObject(LinkContext &Context);
+
   /// \defgroup FindRootDIEs Find DIEs corresponding to debug map entries.
   ///
   /// @{
   /// Recursively walk the \p DIE tree and look for DIEs to
   /// keep. Store that information in \p CU's DIEInfo.
   ///
   /// The return value indicates whether the DIE is incomplete.
-  bool lookForDIEsToKeep(RelocationManager &RelocMgr, const DWARFDie &DIE,
+  bool lookForDIEsToKeep(RelocationManager &RelocMgr, RangesTy &Ranges,
+                         UnitListTy &Units, const DWARFDie &DIE,
                          const DebugMapObject &DMO, CompileUnit &CU,
                          unsigned Flags);
 
   /// If this compile unit is really a skeleton CU that points to a
   /// clang module, register it in ClangModules and return true.
   ///
   /// A skeleton CU is a CU without children, a DW_AT_gnu_dwo_name
   /// pointing to the module, and a DW_AT_gnu_dwo_id with the module
   /// hash.
   bool registerModuleReference(const DWARFDie &CUDie, const DWARFUnit &Unit,
-                               DebugMap &ModuleMap, unsigned Indent = 0);
+                               DebugMap &ModuleMap, const DebugMapObject &DMO,
+                               RangesTy &Ranges,
+                               OffsetsStringPool &OffsetsStringPool,
+                               UniquingStringPool &UniquingStringPoolStringPool,
+                               DeclContextTree &ODRContexts, unsigned &UnitID,
+                               unsigned Indent = 0);
 
   /// Recursively add the debug info in this clang module .pcm
   /// file (and all the modules imported by it in a bottom-up fashion)
   /// to Units.
   Error loadClangModule(StringRef Filename, StringRef ModulePath,
                         StringRef ModuleName, uint64_t DwoId,
-                        DebugMap &ModuleMap, unsigned Indent = 0);
+                        DebugMap &ModuleMap, const DebugMapObject &DMO,
+                        RangesTy &Ranges, OffsetsStringPool &OffsetsStringPool,
+                        UniquingStringPool &UniquingStringPool,
+                        DeclContextTree &ODRContexts, unsigned &UnitID,
+                        unsigned Indent = 0);
 
   /// Flags passed to DwarfLinker::lookForDIEsToKeep
   enum TravesalFlags {
     TF_Keep = 1 << 0,            ///< Mark the traversed DIEs as kept.
     TF_InFunctionScope = 1 << 1, ///< Current scope is a function scope.
     TF_DependencyWalk = 1 << 2,  ///< Walking the dependencies of a kept DIE.
     TF_ParentWalk = 1 << 3,      ///< Walking up the parents of a kept DIE.
     TF_ODR = 1 << 4,             ///< Use the ODR while keeping dependents.
     TF_SkipPC = 1 << 5,          ///< Skip all location attributes.
   };
 
   /// Mark the passed DIE as well as all the ones it depends on as kept.
-  void keepDIEAndDependencies(RelocationManager &RelocMgr, const DWARFDie &DIE,
+  void keepDIEAndDependencies(RelocationManager &RelocMgr, RangesTy &Ranges,
+                              UnitListTy &Units, const DWARFDie &DIE,
                               CompileUnit::DIEInfo &MyInfo,
                               const DebugMapObject &DMO, CompileUnit &CU,
                               bool UseODR);
 
-  unsigned shouldKeepDIE(RelocationManager &RelocMgr, const DWARFDie &DIE,
+  unsigned shouldKeepDIE(RelocationManager &RelocMgr, RangesTy &Ranges,
+                         const DWARFDie &DIE, const DebugMapObject &DMO,
                          CompileUnit &Unit, CompileUnit::DIEInfo &MyInfo,
                          unsigned Flags);
 
   unsigned shouldKeepVariableDIE(RelocationManager &RelocMgr,
                                  const DWARFDie &DIE, CompileUnit &Unit,
                                  CompileUnit::DIEInfo &MyInfo, unsigned Flags);
 
   unsigned shouldKeepSubprogramDIE(RelocationManager &RelocMgr,
-                                   const DWARFDie &DIE, CompileUnit &Unit,
+                                   RangesTy &Ranges, const DWARFDie &DIE,
+                                   const DebugMapObject &DMO, CompileUnit &Unit,
                                    CompileUnit::DIEInfo &MyInfo,
                                    unsigned Flags);
 
   bool hasValidRelocation(uint32_t StartOffset, uint32_t EndOffset,
                           CompileUnit::DIEInfo &Info);
   /// @}
 
   /// \defgroup Linking Methods used to link the debug information
public:
     /// debug map.
     ///
     /// \param OutOffset is the offset the cloned DIE in the output
     /// compile unit.
     /// \param PCOffset (while cloning a function scope) is the offset
     /// applied to the entry point of the function to get the linked address.
     /// \param Die the output DIE to use, pass NULL to create one.
     /// \returns the root of the cloned tree or null if nothing was selected.
-    DIE *cloneDIE(const DWARFDie &InputDIE, CompileUnit &U, int64_t PCOffset,
-                  uint32_t OutOffset, unsigned Flags, DIE *Die = nullptr);
+    DIE *cloneDIE(const DWARFDie &InputDIE, const DebugMapObject &DMO,
+                  CompileUnit &U, OffsetsStringPool &StringPool,
+                  int64_t PCOffset, uint32_t OutOffset, unsigned Flags,
+                  DIE *Die = nullptr);
 
     /// Construct the output DIE tree by cloning the DIEs we
     /// chose to keep above. If there are no valid relocs, then there's
     /// nothing to clone/emit.
-    void cloneAllCompileUnits(DWARFContext &DwarfContext);
+    void cloneAllCompileUnits(DWARFContext &DwarfContext,
+                              const DebugMapObject &DMO, RangesTy &Ranges,
+                              OffsetsStringPool &StringPool);
 
   private:
     using AttributeSpec = DWARFAbbreviationDeclaration::AttributeSpec;
 
     /// Information gathered and exchanged between the various
     /// clone*Attributes helpers about the attributes of a particular DIE.
     struct AttributesInfo {
       /// Names.
struct AttributesInfo {
 
       /// Is this DIE only a declaration?
       bool IsDeclaration = false;
 
       AttributesInfo() = default;
     };
 
     /// Helper for cloneDIE.
-    unsigned cloneAttribute(DIE &Die, const DWARFDie &InputDIE, CompileUnit &U,
+    unsigned cloneAttribute(DIE &Die, const DWARFDie &InputDIE,
+                            const DebugMapObject &DMO, CompileUnit &U,
+                            OffsetsStringPool &StringPool,
                             const DWARFFormValue &Val,
                             const AttributeSpec AttrSpec, unsigned AttrSize,
                             AttributesInfo &AttrInfo);
 
     /// Clone a string attribute described by \p AttrSpec and add
     /// it to \p Die.
     /// \returns the size of the new attribute.
     unsigned cloneStringAttribute(DIE &Die, AttributeSpec AttrSpec,
                                   const DWARFFormValue &Val, const DWARFUnit &U,
+                                  OffsetsStringPool &StringPool,
                                   AttributesInfo &Info);
 
     /// Clone an attribute referencing another DIE and add
     /// it to \p Die.
     /// \returns the size of the new attribute.
     unsigned cloneDieReferenceAttribute(DIE &Die, const DWARFDie &InputDIE,
                                         AttributeSpec AttrSpec,
                                         unsigned AttrSize,
                                         const DWARFFormValue &Val,
+                                        const DebugMapObject &DMO,
                                         CompileUnit &Unit);
 
     /// Clone an attribute referencing another DIE and add
     /// it to \p Die.
     /// \returns the size of the new attribute.
     unsigned cloneBlockAttribute(DIE &Die, AttributeSpec AttrSpec,
                                  const DWARFFormValue &Val, unsigned AttrSize);
 
     /// Clone an attribute referencing another DIE and add
     /// it to \p Die.
     /// \returns the size of the new attribute.
     unsigned cloneAddressAttribute(DIE &Die, AttributeSpec AttrSpec,
                                    const DWARFFormValue &Val,
                                    const CompileUnit &Unit,
                                    AttributesInfo &Info);
 
     /// Clone a scalar attribute  and add it to \p Die.
     /// \returns the size of the new attribute.
     unsigned cloneScalarAttribute(DIE &Die, const DWARFDie &InputDIE,
-                                  CompileUnit &U, AttributeSpec AttrSpec,
+                                  const DebugMapObject &DMO, CompileUnit &U,
+                                  AttributeSpec AttrSpec,
                                   const DWARFFormValue &Val, unsigned AttrSize,
                                   AttributesInfo &Info);
 
     /// Get the potential name and mangled name for the entity
     /// described by \p Die and store them in \Info if they are not
     /// already there.
     /// \returns is a name was found.
     bool getDIENames(const DWARFDie &Die, AttributesInfo &Info,
-                     bool StripTemplate = false);
+                     OffsetsStringPool &StringPool, bool StripTemplate = false);
 
     /// Create a copy of abbreviation Abbrev.
     void copyAbbrev(const DWARFAbbreviationDeclaration &Abbrev, bool hasODR);
 
     uint32_t hashFullyQualifiedName(DWARFDie DIE, CompileUnit &U,
+                                    const DebugMapObject &DMO,
                                     int RecurseDepth = 0);
 
     /// Helper for cloneDIE.
     void addObjCAccelerator(CompileUnit &Unit, const DIE *Die,
-                            DwarfStringPoolEntryRef Name, bool SkipPubSection);
+                            DwarfStringPoolEntryRef Name,
+                            OffsetsStringPool &StringPool, bool SkipPubSection);
   };
 
   /// Assign an abbreviation number to \p Abbrev
   void AssignAbbrev(DIEAbbrev &Abbrev);
 
   /// Compute and emit debug_ranges section for \p Unit, and
   /// patch the attributes referencing it.
-  void patchRangesForUnit(const CompileUnit &Unit, DWARFContext &Dwarf) const;
+  void patchRangesForUnit(const CompileUnit &Unit, DWARFContext &Dwarf,
+                          const DebugMapObject &DMO) const;
 
   /// Generate and emit the DW_AT_ranges attribute for a compile_unit if it had
   /// one.
   void generateUnitRanges(CompileUnit &Unit) const;
 
   /// Extract the line tables from the original dwarf, extract the relevant
   /// parts according to the linked function ranges and emit the result in the
   /// debug_line section.
-  void patchLineTableForUnit(CompileUnit &Unit, DWARFContext &OrigDwarf);
+  void patchLineTableForUnit(CompileUnit &Unit, DWARFContext &OrigDwarf,
+                             RangesTy &Ranges, const DebugMapObject &DMO);
 
   /// Emit the accelerator entries for \p Unit.
   void emitAcceleratorEntriesForUnit(CompileUnit &Unit);
 
   /// Patch the frame info for an object file and emit it.
-  void patchFrameInfoForObject(const DebugMapObject &, DWARFContext &,
-                               unsigned AddressSize);
+  void patchFrameInfoForObject(const DebugMapObject &, RangesTy &Ranges,
+                               DWARFContext &, unsigned AddressSize);
 
   /// FoldingSet that uniques the abbreviations.
   FoldingSet<DIEAbbrev> AbbreviationsSet;
 
   /// Storage for the unique Abbreviations.
   /// This is passed to AsmPrinter::emitDwarfAbbrevs(), thus it cannot be
   /// changed to a vector of unique_ptrs.
   std::vector<std::unique_ptr<DIEAbbrev>> Abbreviations;
 
   /// DIELoc objects that need to be destructed (but not freed!).
   std::vector<DIELoc *> DIELocs;
 
   /// DIEBlock objects that need to be destructed (but not freed!).
   std::vector<DIEBlock *> DIEBlocks;
 
   /// Allocator used for all the DIEValue objects.
   BumpPtrAllocator DIEAlloc;
   /// @}
 
-  /// ODR Contexts for that link.
-  DeclContextTree ODRContexts;
-
   /// \defgroup Helpers Various helper methods.
   ///
   /// @{
   bool createStreamer(const Triple &TheTriple, raw_fd_ostream &OutFile);
 
   /// Attempt to load a debug object from disk.
   ErrorOr<const object::ObjectFile &> loadObject(BinaryHolder &BinaryHolder,
-                                                 DebugMapObject &Obj,
+                                                 const DebugMapObject &Obj,
                                                  const DebugMap &Map);
   /// @}
 
   raw_fd_ostream &OutFile;
   LinkOptions Options;
-  BinaryHolder BinHolder;
   std::unique_ptr<DwarfStreamer> Streamer;
   uint64_t OutputDebugInfoSize;
-
-  /// A unique ID that identifies each compile unit.
-  unsigned UnitID;
-
   unsigned MaxDwarfVersion = 0;
 
-  /// The units of the current debug map object.
-  std::vector<std::unique_ptr<CompileUnit>> Units;
-
-  /// The debug map object currently under consideration.
-  DebugMapObject *CurrentDebugObject;
-
-  /// The Dwarf string pool.
-  NonRelocatableStringpool StringPool;
-
-  /// This map is keyed by the entry PC of functions in that
-  /// debug object and the associated value is a pair storing the
-  /// corresponding end PC and the offset to apply to get the linked
-  /// address.
-  ///
-  /// See startDebugObject() for a more complete description of its use.
-  std::map<uint64_t, std::pair<uint64_t, int64_t>> Ranges;
-
-  /// The CIEs that have been emitted in the output
-  /// section. The actual CIE data serves a the key to this StringMap,
-  /// this takes care of comparing the semantics of CIEs defined in
-  /// different object files.
+  /// The CIEs that have been emitted in the output section. The actual CIE
+  /// data serves a the key to this StringMap, this takes care of comparing the
+  /// semantics of CIEs defined in different object files.
   StringMap<uint32_t> EmittedCIEs;
 
   /// Offset of the last CIE that has been emitted in the output
   /// debug_frame section.
   uint32_t LastCIEOffset = 0;
 
   /// Apple accelerator tables.
   AccelTable<AppleAccelTableStaticOffsetData> AppleNames;
auto CU = std::upper_bound(
       });
   return CU != Units.end() ? CU->get() : nullptr;
 }
 
 /// Resolve the DIE attribute reference that has been extracted in \p RefValue.
 /// The resulting DIE might be in another CompileUnit which is stored into \p
 /// ReferencedCU. \returns null if resolving fails for any reason.
 static DWARFDie
-resolveDIEReference(const DwarfLinker &Linker,
+resolveDIEReference(const DwarfLinker &Linker, const DebugMapObject &DMO,
                     std::vector<std::unique_ptr<CompileUnit>> &Units,
                     const DWARFFormValue &RefValue, const DWARFUnit &Unit,
                     const DWARFDie &DIE, CompileUnit *&RefCU) {
   assert(RefValue.isFormClass(DWARFFormValue::FC_Reference));
   uint64_t RefOffset = *RefValue.getAsReference();
 
   if ((RefCU = getUnitForOffset(Units, RefOffset)))
     if (const auto RefDie = RefCU->getOrigUnit().getDIEForOffset(RefOffset)) {
       // In a file with broken references, an attribute might point to a NULL
       // DIE.
       if (!RefDie.isNULL())
         return RefDie;
     }
 
-  Linker.reportWarning("could not find referenced DIE", &DIE);
+  Linker.reportWarning("could not find referenced DIE", DMO, &DIE);
   return DWARFDie();
 }
 
 /// \returns whether the passed \a Attr type might contain a DIE reference
 /// suitable for ODR uniquing.
 static bool isODRAttribute(uint16_t Attr) {
   switch (Attr) {
   default:
bool DeclContext::setLastSeenDIE(CompileUnit &U, const DWARFDie &Die) {
 
   LastSeenCompileUnitID = U.getUniqueID();
   LastSeenDIE = Die;
   return true;
 }
 
 PointerIntPair<DeclContext *, 1> DeclContextTree::getChildDeclContext(
     DeclContext &Context, const DWARFDie &DIE, CompileUnit &U,
-    NonRelocatableStringpool &StringPool, bool InClangModule) {
+    UniquingStringPool &StringPool, bool InClangModule) {
   unsigned Tag = DIE.getTag();
 
   // FIXME: dsymutil-classic compat: We should bail out here if we
   // have a specification or an abstract_origin. We will get the
   // parent context wrong here.
 
   switch (Tag) {
   default:
if ((Tag == dwarf::DW_TAG_subprogram &&
       (Tag == dwarf::DW_TAG_union_type))
     return PointerIntPair<DeclContext *, 1>(*ContextIter, /* Invalid= */ 1);
 
   return PointerIntPair<DeclContext *, 1>(*ContextIter);
 }
 
 bool DwarfLinker::DIECloner::getDIENames(const DWARFDie &Die,
                                          AttributesInfo &Info,
+                                         OffsetsStringPool &StringPool,
                                          bool StripTemplate) {
   // This function will be called on DIEs having low_pcs and
   // ranges. As getting the name might be more expansive, filter out
   // blocks directly.
   if (Die.getTag() == dwarf::DW_TAG_lexical_block)
     return false;
 
   // FIXME: a bit wasteful as the first getName might return the
   // short name.
   if (!Info.MangledName)
     if (const char *MangledName = Die.getName(DINameKind::LinkageName))
-      Info.MangledName = Linker.StringPool.getEntry(MangledName);
+      Info.MangledName = StringPool.getEntry(MangledName);
 
   if (!Info.Name)
     if (const char *Name = Die.getName(DINameKind::ShortName))
-      Info.Name = Linker.StringPool.getEntry(Name);
+      Info.Name = StringPool.getEntry(Name);
 
   if (StripTemplate && Info.Name && Info.MangledName != Info.Name) {
     // FIXME: dsymutil compatibility. This is wrong for operator<
     auto Split = Info.Name.getString().split('<');
     if (!Split.second.empty())
-      Info.NameWithoutTemplate = Linker.StringPool.getEntry(Split.first);
+      Info.NameWithoutTemplate = StringPool.getEntry(Split.first);
   }
 
   return Info.Name || Info.MangledName;
 }
 
 /// Report a warning to the user, optionally including information about a
 /// specific \p DIE related to the warning.
-void DwarfLinker::reportWarning(const Twine &Warning,
+void DwarfLinker::reportWarning(const Twine &Warning, const DebugMapObject &DMO,
                                 const DWARFDie *DIE) const {
-  StringRef Context = "<debug map>";
-  if (CurrentDebugObject)
-    Context = CurrentDebugObject->getObjectFilename();
+  StringRef Context = DMO.getObjectFilename();
   warn(Warning, Context);
 
   if (!Options.Verbose || !DIE)
     return;
 
   DIDumpOptions DumpOpts;
   DumpOpts.RecurseDepth = 0;
   DumpOpts.Verbose = Options.Verbose;

 /// Recursive helper to build the global DeclContext information and
 /// gather the child->parent relationships in the original compile unit.
 ///
 /// \return true when this DIE and all of its children are only
 /// forward declarations to types defined in external clang modules
 /// (i.e., forward declarations that are children of a DW_TAG_module).
 static bool analyzeContextInfo(const DWARFDie &DIE, unsigned ParentIdx,
                                CompileUnit &CU, DeclContext *CurrentDeclContext,
-                               NonRelocatableStringpool &StringPool,
+                               UniquingStringPool &StringPool,
                                DeclContextTree &Contexts,
                                bool InImportedModule = false) {
   unsigned MyIdx = CU.getOrigUnit().getDIEIndex(DIE);
   CompileUnit::DIEInfo &Info = CU.getInfo(MyIdx);
 
   // Clang imposes an ODR on modules(!) regardless of the language:
   //  "The module-id should consist of only a single identifier,
   //   which provides the name of the module being defined. Each
static bool dieNeedsChildrenToBeMeaningful(uint32_t Tag) {
   case dwarf::DW_TAG_structure_type:
   case dwarf::DW_TAG_class_type:
   case dwarf::DW_TAG_union_type:
     return true;
   }
   llvm_unreachable("Invalid Tag");
 }
 
-void DwarfLinker::startDebugObject(DWARFContext &Dwarf, DebugMapObject &Obj) {
+void DwarfLinker::startDebugObject(LinkContext &Context) {
   // Iterate over the debug map entries and put all the ones that are
-  // functions (because they have a size) into the Ranges map. This
-  // map is very similar to the FunctionRanges that are stored in each
-  // unit, with 2 notable differences:
-  //  - obviously this one is global, while the other ones are per-unit.
-  //  - this one contains not only the functions described in the DIE
-  // tree, but also the ones that are only in the debug map.
-  // The latter information is required to reproduce dsymutil's logic
-  // while linking line tables. The cases where this information
-  // matters look like bugs that need to be investigated, but for now
-  // we need to reproduce dsymutil's behavior.
+  // functions (because they have a size) into the Ranges map. This map is
+  // very similar to the FunctionRanges that are stored in each unit, with 2
+  // notable differences:
+  //
+  //  1. Obviously this one is global, while the other ones are per-unit.
+  //
+  //  2. This one contains not only the functions described in the DIE
+  //     tree, but also the ones that are only in the debug map.
+  //
+  // The latter information is required to reproduce dsymutil's logic while
+  // linking line tables. The cases where this information matters look like
+  // bugs that need to be investigated, but for now we need to reproduce
+  // dsymutil's behavior.
   // FIXME: Once we understood exactly if that information is needed,
   // maybe totally remove this (or try to use it to do a real
   // -gline-tables-only on Darwin.
-  for (const auto &Entry : Obj.symbols()) {
+  for (const auto &Entry : Context.DMO.symbols()) {
     const auto &Mapping = Entry.getValue();
     if (Mapping.Size && Mapping.ObjectAddress)
-      Ranges[*Mapping.ObjectAddress] = std::make_pair(
+      Context.Ranges[*Mapping.ObjectAddress] = std::make_pair(
           *Mapping.ObjectAddress + Mapping.Size,
           int64_t(Mapping.BinaryAddress) - *Mapping.ObjectAddress);
   }
 }
 
-void DwarfLinker::endDebugObject() {
-  Units.clear();
-  Ranges.clear();
-
+void DwarfLinker::endDebugObject(LinkContext &Context) {
+  Context.Clear();
   for (auto I = DIEBlocks.begin(), E = DIEBlocks.end(); I != E; ++I)
     (*I)->~DIEBlock();
   for (auto I = DIELocs.begin(), E = DIELocs.end(); I != E; ++I)
     (*I)->~DIELoc();
 
   DIEBlocks.clear();
   DIELocs.clear();
   DIEAlloc.Reset();
for (const object::RelocationRef &Reloc : Section.relocations()) {
     }
 
     object::DataRefImpl RelocDataRef = Reloc.getRawDataRefImpl();
     MachO::any_relocation_info MachOReloc = Obj.getRelocation(RelocDataRef);
 
     if (isMachOPairedReloc(Obj.getAnyRelocationType(MachOReloc),
                            Obj.getArch())) {
       SkipNext = true;
-      Linker.reportWarning(" unsupported relocation in debug_info section.");
+      Linker.reportWarning(" unsupported relocation in debug_info section.",
+                           DMO);
       continue;
     }
 
     unsigned RelocSize = 1 << Obj.getAnyRelocationLength(MachOReloc);
     uint64_t Offset64 = Reloc.getOffset();
     if ((RelocSize != 4 && RelocSize != 8)) {
-      Linker.reportWarning(" unsupported relocation in debug_info section.");
+      Linker.reportWarning(" unsupported relocation in debug_info section.",
+                           DMO);
       continue;
     }
     uint32_t Offset = Offset64;
     // Mach-o uses REL relocations, the addend is at the relocation offset.
     uint64_t Addend = Data.getUnsigned(&Offset, RelocSize);
     uint64_t SymAddress;
     int64_t SymOffset;
 
     if (Obj.isRelocationScattered(MachOReloc)) {
       // The address of the base symbol for scattered relocations is
       // stored in the reloc itself. The actual addend will store the
       // base address plus the offset.
       SymAddress = Obj.getScatteredRelocationValue(MachOReloc);
       SymOffset = int64_t(Addend) - SymAddress;
     } else {
       SymAddress = Addend;
       SymOffset = 0;
     }
 
     auto Sym = Reloc.getSymbol();
     if (Sym != Obj.symbol_end()) {
       Expected<StringRef> SymbolName = Sym->getName();
       if (!SymbolName) {
         consumeError(SymbolName.takeError());
-        Linker.reportWarning("error getting relocation symbol name.");
+        Linker.reportWarning("error getting relocation symbol name.", DMO);
         continue;
       }
       if (const auto *Mapping = DMO.lookupSymbol(*SymbolName))
         ValidRelocs.emplace_back(Offset64, RelocSize, Addend, Mapping);
     } else if (const auto *Mapping = DMO.lookupObjectAddress(SymAddress)) {
       // Do not store the addend. The addend was the address of the symbol in
       // the object file, the address in the binary that is stored in the debug
       // map doesn't need to be offset.
       ValidRelocs.emplace_back(Offset64, RelocSize, SymOffset, Mapping);
     }
   }
 }
 
 /// Dispatch the valid relocation finding logic to the
 /// appropriate handler depending on the object file format.
 bool DwarfLinker::RelocationManager::findValidRelocs(
     const object::SectionRef &Section, const object::ObjectFile &Obj,
     const DebugMapObject &DMO) {
   // Dispatch to the right handler depending on the file type.
   if (auto *MachOObj = dyn_cast<object::MachOObjectFile>(&Obj))
     findValidRelocsMachO(Section, *MachOObj, DMO);
   else
-    Linker.reportWarning(Twine("unsupported object file type: ") +
-                         Obj.getFileName());
+    Linker.reportWarning(
+        Twine("unsupported object file type: ") + Obj.getFileName(), DMO);
 
   if (ValidRelocs.empty())
     return false;
 
   // Sort the relocations by offset. We will walk the DIEs linearly in
   // the file, this allows us to just keep an index in the relocation
   // array that we advance during our walk, rather than resorting to
   // some associative container. See DwarfLinker::NextValidReloc.
if (Options.Verbose) {
     DIE.dump(outs(), 8 /* Indent */, DumpOpts);
   }
 
   return Flags | TF_Keep;
 }
 
 /// Check if a function describing DIE should be kept.
 /// \returns updated TraversalFlags.
-unsigned DwarfLinker::shouldKeepSubprogramDIE(RelocationManager &RelocMgr,
-                                              const DWARFDie &DIE,
-                                              CompileUnit &Unit,
-                                              CompileUnit::DIEInfo &MyInfo,
-                                              unsigned Flags) {
+unsigned DwarfLinker::shouldKeepSubprogramDIE(
+    RelocationManager &RelocMgr, RangesTy &Ranges, const DWARFDie &DIE,
+    const DebugMapObject &DMO, CompileUnit &Unit, CompileUnit::DIEInfo &MyInfo,
   const auto *Abbrev = DIE.getAbbreviationDeclarationPtr();
 
   Flags |= TF_InFunctionScope;
 
   Optional<uint32_t> LowPcIdx = Abbrev->findAttributeIndex(dwarf::DW_AT_low_pc);
   if (!LowPcIdx)
     return Flags;
 
if (DIE.getTag() == dwarf::DW_TAG_label) {
     Unit.addLabelLowPc(*LowPc, MyInfo.AddrAdjust);
     return Flags | TF_Keep;
   }
 
   Flags |= TF_Keep;
 
   Optional<uint64_t> HighPc = DIE.getHighPC(*LowPc);
   if (!HighPc) {
-    reportWarning("Function without high_pc. Range will be discarded.\n", &DIE);
+    reportWarning("Function without high_pc. Range will be discarded.\n", DMO,
+                  &DIE);
     return Flags;
   }
 
   // Replace the debug map range with a more accurate one.
   Ranges[*LowPc] = std::make_pair(*HighPc, MyInfo.AddrAdjust);
   Unit.addFunctionRange(*LowPc, *HighPc, MyInfo.AddrAdjust);
   return Flags;
 }
 
 /// Check if a DIE should be kept.
 /// \returns updated TraversalFlags.
 unsigned DwarfLinker::shouldKeepDIE(RelocationManager &RelocMgr,
-                                    const DWARFDie &DIE, CompileUnit &Unit,
+                                    RangesTy &Ranges, const DWARFDie &DIE,
+                                    const DebugMapObject &DMO,
+                                    CompileUnit &Unit,
                                     CompileUnit::DIEInfo &MyInfo,
                                     unsigned Flags) {
   switch (DIE.getTag()) {
   case dwarf::DW_TAG_constant:
   case dwarf::DW_TAG_variable:
     return shouldKeepVariableDIE(RelocMgr, DIE, Unit, MyInfo, Flags);
   case dwarf::DW_TAG_subprogram:
   case dwarf::DW_TAG_label:
-    return shouldKeepSubprogramDIE(RelocMgr, DIE, Unit, MyInfo, Flags);
+    return shouldKeepSubprogramDIE(RelocMgr, Ranges, DIE, DMO, Unit, MyInfo,
+                                   Flags);
   case dwarf::DW_TAG_imported_module:
   case dwarf::DW_TAG_imported_declaration:
   case dwarf::DW_TAG_imported_unit:
     // We always want to keep these.
     return Flags | TF_Keep;
   default:
     break;
   }
 
   return Flags;
 }
 
 /// Mark the passed DIE as well as all the ones it depends on
 /// as kept.
 ///
 /// This function is called by lookForDIEsToKeep on DIEs that are
 /// newly discovered to be needed in the link. It recursively calls
 /// back to lookForDIEsToKeep while adding TF_DependencyWalk to the
 /// TraversalFlags to inform it that it's not doing the primary DIE
 /// tree walk.
 void DwarfLinker::keepDIEAndDependencies(RelocationManager &RelocMgr,
+                                         RangesTy &Ranges, UnitListTy &Units,
                                          const DWARFDie &Die,
                                          CompileUnit::DIEInfo &MyInfo,
                                          const DebugMapObject &DMO,
                                          CompileUnit &CU, bool UseODR) {
   DWARFUnit &Unit = CU.getOrigUnit();
   MyInfo.Keep = true;
 
   // We're looking for incomplete types.
   MyInfo.Incomplete = Die.getTag() != dwarf::DW_TAG_subprogram &&
                       Die.getTag() != dwarf::DW_TAG_member &&
                       dwarf::toUnsigned(Die.find(dwarf::DW_AT_declaration), 0);
 
   // First mark all the parent chain as kept.
   unsigned AncestorIdx = MyInfo.ParentIdx;
   while (!CU.getInfo(AncestorIdx).Keep) {
     unsigned ODRFlag = UseODR ? TF_ODR : 0;
-    lookForDIEsToKeep(RelocMgr, Unit.getDIEAtIndex(AncestorIdx), DMO, CU,
+    lookForDIEsToKeep(RelocMgr, Ranges, Units, Unit.getDIEAtIndex(AncestorIdx),
+                      DMO, CU,
                       TF_ParentWalk | TF_Keep | TF_DependencyWalk | ODRFlag);
     AncestorIdx = CU.getInfo(AncestorIdx).ParentIdx;
   }
 
   // Then we need to mark all the DIEs referenced by this DIE's
   // attributes as kept.
   DWARFDataExtractor Data = Unit.getDebugInfoExtractor();
   const auto *Abbrev = Die.getAbbreviationDeclarationPtr();
   uint32_t Offset = Die.getOffset() + getULEB128Size(Abbrev->getCode());
 
   // Mark all DIEs referenced through attributes as kept.
   for (const auto &AttrSpec : Abbrev->attributes()) {
     DWARFFormValue Val(AttrSpec.Form);
 
     if (!Val.isFormClass(DWARFFormValue::FC_Reference) ||
         AttrSpec.Attr == dwarf::DW_AT_sibling) {
       DWARFFormValue::skipValue(AttrSpec.Form, Data, &Offset,
                                 Unit.getFormParams());
       continue;
     }
 
     Val.extractValue(Data, &Offset, Unit.getFormParams(), &Unit);
     CompileUnit *ReferencedCU;
-    if (auto RefDie =
-            resolveDIEReference(*this, Units, Val, Unit, Die, ReferencedCU)) {
+    if (auto RefDie = resolveDIEReference(*this, DMO, Units, Val, Unit, Die,
+                                          ReferencedCU)) {
       uint32_t RefIdx = ReferencedCU->getOrigUnit().getDIEIndex(RefDie);
       CompileUnit::DIEInfo &Info = ReferencedCU->getInfo(RefIdx);
       bool IsModuleRef = Info.Ctxt && Info.Ctxt->getCanonicalDIEOffset() &&
                          Info.Ctxt->isDefinedInClangModule();
       // If the referenced DIE has a DeclContext that has already been
       // emitted, then do not keep the one in this CU. We'll link to
       // the canonical DIE in cloneDieReferenceAttribute.
       // FIXME: compatibility with dsymutil-classic. UseODR shouldn't
       // be necessary and could be advantageously replaced by
       // ReferencedCU->hasODR() && CU.hasODR().
       // FIXME: compatibility with dsymutil-classic. There is no
       // reason not to unique ref_addr references.
       if (AttrSpec.Form != dwarf::DW_FORM_ref_addr && (UseODR || IsModuleRef) &&
           Info.Ctxt &&
           Info.Ctxt != ReferencedCU->getInfo(Info.ParentIdx).Ctxt &&
           Info.Ctxt->getCanonicalDIEOffset() && isODRAttribute(AttrSpec.Attr))
         continue;
 
       // Keep a module forward declaration if there is no definition.
       if (!(isODRAttribute(AttrSpec.Attr) && Info.Ctxt &&
             Info.Ctxt->getCanonicalDIEOffset()))
         Info.Prune = false;
 
       unsigned ODRFlag = UseODR ? TF_ODR : 0;
-      lookForDIEsToKeep(RelocMgr, RefDie, DMO, *ReferencedCU,
+      lookForDIEsToKeep(RelocMgr, Ranges, Units, RefDie, DMO, *ReferencedCU,
                         TF_Keep | TF_DependencyWalk | ODRFlag);
 
       // The incomplete property is propagated if the current DIE is complete
       // but references an incomplete DIE.
       if (Info.Incomplete && !MyInfo.Incomplete &&
           (Die.getTag() == dwarf::DW_TAG_typedef ||
            Die.getTag() == dwarf::DW_TAG_member ||
            Die.getTag() == dwarf::DW_TAG_reference_type ||

 /// comment).
 /// While walking the dependencies of root DIEs, this function is
 /// also called, but during these dependency walks the file order is
 /// not respected. The TF_DependencyWalk flag tells us which kind of
 /// traversal we are currently doing.
 ///
 /// The return value indicates whether the DIE is incomplete.
 bool DwarfLinker::lookForDIEsToKeep(RelocationManager &RelocMgr,
+                                    RangesTy &Ranges, UnitListTy &Units,
                                     const DWARFDie &Die,
                                     const DebugMapObject &DMO, CompileUnit &CU,
                                     unsigned Flags) {
   unsigned Idx = CU.getOrigUnit().getDIEIndex(Die);
   CompileUnit::DIEInfo &MyInfo = CU.getInfo(Idx);
   bool AlreadyKept = MyInfo.Keep;
   if (MyInfo.Prune)
     return true;
 
   // If the Keep flag is set, we are marking a required DIE's
   // dependencies. If our target is already marked as kept, we're all
   // set.
   if ((Flags & TF_DependencyWalk) && AlreadyKept)
     return MyInfo.Incomplete;
 
   // We must not call shouldKeepDIE while called from keepDIEAndDependencies,
   // because it would screw up the relocation finding logic.
   if (!(Flags & TF_DependencyWalk))
-    Flags = shouldKeepDIE(RelocMgr, Die, CU, MyInfo, Flags);
+    Flags = shouldKeepDIE(RelocMgr, Ranges, Die, DMO, CU, MyInfo, Flags);
 
   // If it is a newly kept DIE mark it as well as all its dependencies as kept.
   if (!AlreadyKept && (Flags & TF_Keep)) {
     bool UseOdr = (Flags & TF_DependencyWalk) ? (Flags & TF_ODR) : CU.hasODR();
-    keepDIEAndDependencies(RelocMgr, Die, MyInfo, DMO, CU, UseOdr);
+    keepDIEAndDependencies(RelocMgr, Ranges, Units, Die, MyInfo, DMO, CU,
+                           UseOdr);
   }
   // The TF_ParentWalk flag tells us that we are currently walking up
   // the parent chain of a required DIE, and we don't want to mark all
   // the children of the parents as kept (consider for example a
   // DW_TAG_namespace node in the parent chain). There are however a
   // set of DIE types for which we want to ignore that directive and still
   // walk their children.
   if (dieNeedsChildrenToBeMeaningful(Die.getTag()))
     Flags &= ~TF_ParentWalk;
 
   if (!Die.hasChildren() || (Flags & TF_ParentWalk))
     return MyInfo.Incomplete;
 
   bool Incomplete = false;
   for (auto Child : Die.children()) {
-    Incomplete |= lookForDIEsToKeep(RelocMgr, Child, DMO, CU, Flags);
+    Incomplete |=
+        lookForDIEsToKeep(RelocMgr, Ranges, Units, Child, DMO, CU, Flags);
 
     // If any of the members are incomplete we propagate the incompleteness.
     if (!MyInfo.Incomplete && Incomplete &&
         (Die.getTag() == dwarf::DW_TAG_structure_type ||
          Die.getTag() == dwarf::DW_TAG_class_type))
       MyInfo.Incomplete = true;
   }
   return MyInfo.Incomplete;
for (const auto &Attr : Abbrev.getData())
       Abbreviations.back()->AddAttribute(Attr.getAttribute(), Attr.getForm());
     AbbreviationsSet.InsertNode(Abbreviations.back().get(), InsertToken);
     // Assign the unique abbreviation number.
     Abbrev.setNumber(Abbreviations.size());
     Abbreviations.back()->setNumber(Abbreviations.size());
   }
 }
 
-unsigned DwarfLinker::DIECloner::cloneStringAttribute(DIE &Die,
-                                                      AttributeSpec AttrSpec,
-                                                      const DWARFFormValue &Val,
-                                                      const DWARFUnit &U,
-                                                      AttributesInfo &Info) {
+unsigned DwarfLinker::DIECloner::cloneStringAttribute(
+    DIE &Die, AttributeSpec AttrSpec, const DWARFFormValue &Val,
+    const DWARFUnit &U, OffsetsStringPool &StringPool, AttributesInfo &Info) {
   // Switch everything to out of line strings.
   const char *String = *Val.getAsCString();
-  auto StringEntry = Linker.StringPool.getEntry(String);
+  auto StringEntry = StringPool.getEntry(String);
+
+  // Update attributes info.
   if (AttrSpec.Attr == dwarf::DW_AT_name)
     Info.Name = StringEntry;
   else if (AttrSpec.Attr == dwarf::DW_AT_MIPS_linkage_name ||
            AttrSpec.Attr == dwarf::DW_AT_linkage_name)
     Info.MangledName = StringEntry;
+
   Die.addValue(DIEAlloc, dwarf::Attribute(AttrSpec.Attr), dwarf::DW_FORM_strp,
                DIEInteger(StringEntry.getOffset()));
+
   return 4;
 }
 
 unsigned DwarfLinker::DIECloner::cloneDieReferenceAttribute(
     DIE &Die, const DWARFDie &InputDIE, AttributeSpec AttrSpec,
-    unsigned AttrSize, const DWARFFormValue &Val, CompileUnit &Unit) {
+    unsigned AttrSize, const DWARFFormValue &Val, const DebugMapObject &DMO,
+    CompileUnit &Unit) {
   const DWARFUnit &U = Unit.getOrigUnit();
   uint32_t Ref = *Val.getAsReference();
   DIE *NewRefDie = nullptr;
   CompileUnit *RefUnit = nullptr;
   DeclContext *Ctxt = nullptr;
 
   DWARFDie RefDie =
-      resolveDIEReference(Linker, CompileUnits, Val, U, InputDIE, RefUnit);
+      resolveDIEReference(Linker, DMO, CompileUnits, Val, U, InputDIE, RefUnit);
 
   // If the referenced DIE is not found,  drop the attribute.
   if (!RefDie || AttrSpec.Attr == dwarf::DW_AT_sibling)
     return 0;
 
   unsigned Idx = RefUnit->getOrigUnit().getDIEIndex(RefDie);
   CompileUnit::DIEInfo &RefInfo = RefUnit->getInfo(Idx);
 
unsigned DwarfLinker::DIECloner::cloneAddressAttribute(
   }
 
   Die.addValue(DIEAlloc, static_cast<dwarf::Attribute>(AttrSpec.Attr),
                static_cast<dwarf::Form>(AttrSpec.Form), DIEInteger(Addr));
   return Unit.getOrigUnit().getAddressByteSize();
 }
 
 unsigned DwarfLinker::DIECloner::cloneScalarAttribute(
-    DIE &Die, const DWARFDie &InputDIE, CompileUnit &Unit,
-    AttributeSpec AttrSpec, const DWARFFormValue &Val, unsigned AttrSize,
-    AttributesInfo &Info) {
+    DIE &Die, const DWARFDie &InputDIE, const DebugMapObject &DMO,
+    CompileUnit &Unit, AttributeSpec AttrSpec, const DWARFFormValue &Val,
+    unsigned AttrSize, AttributesInfo &Info) {
   uint64_t Value;
 
   if (LLVM_UNLIKELY(Linker.Options.Update)) {
     if (auto OptionalValue = Val.getAsUnsignedConstant())
       Value = *OptionalValue;
     else if (auto OptionalValue = Val.getAsSignedConstant())
       Value = *OptionalValue;
     else if (auto OptionalValue = Val.getAsSectionOffset())
       Value = *OptionalValue;
     else {
       Linker.reportWarning(
-          "Unsupported scalar attribute form. Dropping attribute.", &InputDIE);
+          "Unsupported scalar attribute form. Dropping attribute.", DMO,
+          &InputDIE);
       return 0;
     }
     if (AttrSpec.Attr == dwarf::DW_AT_declaration && Value)
       Info.IsDeclaration = true;
     Die.addValue(DIEAlloc, dwarf::Attribute(AttrSpec.Attr),
                  dwarf::Form(AttrSpec.Form), DIEInteger(Value));
     return AttrSize;
   }
 
   if (AttrSpec.Attr == dwarf::DW_AT_high_pc &&
       Die.getTag() == dwarf::DW_TAG_compile_unit) {
     if (Unit.getLowPc() == -1ULL)
       return 0;
     // Dwarf >= 4 high_pc is an size, not an address.
     Value = Unit.getHighPc() - Unit.getLowPc();
   } else if (AttrSpec.Form == dwarf::DW_FORM_sec_offset)
     Value = *Val.getAsSectionOffset();
   else if (AttrSpec.Form == dwarf::DW_FORM_sdata)
     Value = *Val.getAsSignedConstant();
   else if (auto OptionalValue = Val.getAsUnsignedConstant())
     Value = *OptionalValue;
   else {
     Linker.reportWarning(
-        "Unsupported scalar attribute form. Dropping attribute.", &InputDIE);
+        "Unsupported scalar attribute form. Dropping attribute.", DMO,
+        &InputDIE);
     return 0;
   }
   PatchLocation Patch =
       Die.addValue(DIEAlloc, dwarf::Attribute(AttrSpec.Attr),
                    dwarf::Form(AttrSpec.Form), DIEInteger(Value));
   if (AttrSpec.Attr == dwarf::DW_AT_ranges) {
     Unit.noteRangeAttribute(Die, Patch);
     Info.HasRanges = true;
unsigned DwarfLinker::DIECloner::cloneScalarAttribute(
 
   return AttrSize;
 }
 
 /// Clone \p InputDIE's attribute described by \p AttrSpec with
 /// value \p Val, and add it to \p Die.
 /// \returns the size of the cloned attribute.
 unsigned DwarfLinker::DIECloner::cloneAttribute(
-    DIE &Die, const DWARFDie &InputDIE, CompileUnit &Unit,
-    const DWARFFormValue &Val, const AttributeSpec AttrSpec, unsigned AttrSize,
-    AttributesInfo &Info) {
+    DIE &Die, const DWARFDie &InputDIE, const DebugMapObject &DMO,
+    CompileUnit &Unit, OffsetsStringPool &StringPool, const DWARFFormValue &Val,
+    const AttributeSpec AttrSpec, unsigned AttrSize, AttributesInfo &Info) {
   const DWARFUnit &U = Unit.getOrigUnit();
 
   switch (AttrSpec.Form) {
   case dwarf::DW_FORM_strp:
   case dwarf::DW_FORM_string:
-    return cloneStringAttribute(Die, AttrSpec, Val, U, Info);
+    return cloneStringAttribute(Die, AttrSpec, Val, U, StringPool, Info);
   case dwarf::DW_FORM_ref_addr:
   case dwarf::DW_FORM_ref1:
   case dwarf::DW_FORM_ref2:
   case dwarf::DW_FORM_ref4:
   case dwarf::DW_FORM_ref8:
     return cloneDieReferenceAttribute(Die, InputDIE, AttrSpec, AttrSize, Val,
-                                      Unit);
+                                      DMO, Unit);
   case dwarf::DW_FORM_block:
   case dwarf::DW_FORM_block1:
   case dwarf::DW_FORM_block2:
   case dwarf::DW_FORM_block4:
   case dwarf::DW_FORM_exprloc:
     return cloneBlockAttribute(Die, AttrSpec, Val, AttrSize);
   case dwarf::DW_FORM_addr:
     return cloneAddressAttribute(Die, AttrSpec, Val, Unit, Info);
   case dwarf::DW_FORM_data1:
   case dwarf::DW_FORM_data2:
   case dwarf::DW_FORM_data4:
   case dwarf::DW_FORM_data8:
   case dwarf::DW_FORM_udata:
   case dwarf::DW_FORM_sdata:
   case dwarf::DW_FORM_sec_offset:
   case dwarf::DW_FORM_flag:
   case dwarf::DW_FORM_flag_present:
-    return cloneScalarAttribute(Die, InputDIE, Unit, AttrSpec, Val, AttrSize,
-                                Info);
+    return cloneScalarAttribute(Die, InputDIE, DMO, Unit, AttrSpec, Val,
+                                AttrSize, Info);
   default:
     Linker.reportWarning(
-        "Unsupported attribute form in cloneAttribute. Dropping.", &InputDIE);
+        "Unsupported attribute form in cloneAttribute. Dropping.", DMO,
+        &InputDIE);
   }
 
   return 0;
 }
 
 /// Apply the valid relocations found by findValidRelocs() to
 /// the buffer \p Data, taking into account that Data is at \p BaseOffset
 /// in the debug_info section.

 static bool isObjCSelector(StringRef Name) {
   return Name.size() > 2 && (Name[0] == '-' || Name[0] == '+') &&
          (Name[1] == '[');
 }
 
 void DwarfLinker::DIECloner::addObjCAccelerator(CompileUnit &Unit,
                                                 const DIE *Die,
                                                 DwarfStringPoolEntryRef Name,
+                                                OffsetsStringPool &StringPool,
                                                 bool SkipPubSection) {
   assert(isObjCSelector(Name.getString()) && "not an objc selector");
   // Objective C method or class function.
   // "- [Class(Category) selector :withArg ...]"
   StringRef ClassNameStart(Name.getString().drop_front(2));
   size_t FirstSpace = ClassNameStart.find(' ');
   if (FirstSpace == StringRef::npos)
     return;
 
   StringRef SelectorStart(ClassNameStart.data() + FirstSpace + 1);
   if (!SelectorStart.size())
     return;
 
   StringRef Selector(SelectorStart.data(), SelectorStart.size() - 1);
-  Unit.addNameAccelerator(Die, Linker.StringPool.getEntry(Selector),
-                          SkipPubSection);
+  Unit.addNameAccelerator(Die, StringPool.getEntry(Selector), SkipPubSection);
 
   // Add an entry for the class name that points to this
   // method/class function.
   StringRef ClassName(ClassNameStart.data(), FirstSpace);
-  Unit.addObjCAccelerator(Die, Linker.StringPool.getEntry(ClassName),
-                          SkipPubSection);
+  Unit.addObjCAccelerator(Die, StringPool.getEntry(ClassName), SkipPubSection);
 
   if (ClassName[ClassName.size() - 1] == ')') {
     size_t OpenParens = ClassName.find('(');
     if (OpenParens != StringRef::npos) {
       StringRef ClassNameNoCategory(ClassName.data(), OpenParens);
-      Unit.addObjCAccelerator(
-          Die, Linker.StringPool.getEntry(ClassNameNoCategory), SkipPubSection);
+      Unit.addObjCAccelerator(Die, StringPool.getEntry(ClassNameNoCategory),
+                              SkipPubSection);
 
       std::string MethodNameNoCategory(Name.getString().data(), OpenParens + 2);
       // FIXME: The missing space here may be a bug, but
       //        dsymutil-classic also does it this way.
       MethodNameNoCategory.append(SelectorStart);
-      Unit.addNameAccelerator(Die,
-                              Linker.StringPool.getEntry(MethodNameNoCategory),
+      Unit.addNameAccelerator(Die, StringPool.getEntry(MethodNameNoCategory),
                               SkipPubSection);
     }
   }
 }
 
 static bool
 shouldSkipAttribute(DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
                     uint16_t Tag, bool InDebugMap, bool SkipPC,
case dwarf::DW_AT_frame_base:
     // the function wasn't linked.
     return (SkipPC || (!InFunctionScope && Tag == dwarf::DW_TAG_variable &&
                        !InDebugMap)) &&
            !DWARFFormValue(AttrSpec.Form).isFormClass(DWARFFormValue::FC_Block);
   }
 }
 
 DIE *DwarfLinker::DIECloner::cloneDIE(const DWARFDie &InputDIE,
-                                      CompileUnit &Unit, int64_t PCOffset,
-                                      uint32_t OutOffset, unsigned Flags,
-                                      DIE *Die) {
+                                      const DebugMapObject &DMO,
+                                      CompileUnit &Unit,
+                                      OffsetsStringPool &StringPool,
+                                      int64_t PCOffset, uint32_t OutOffset,
+                                      unsigned Flags, DIE *Die) {
   DWARFUnit &U = Unit.getOrigUnit();
   unsigned Idx = U.getDIEIndex(InputDIE);
   CompileUnit::DIEInfo &Info = Unit.getInfo(Idx);
 
   // Should the DIE appear in the output?
   if (!Unit.getInfo(Idx).Keep)
     return nullptr;
 
if (LLVM_LIKELY(!Options.Update) &&
       continue;
     }
 
     DWARFFormValue Val(AttrSpec.Form);
     uint32_t AttrSize = Offset;
     Val.extractValue(Data, &Offset, U.getFormParams(), &U);
     AttrSize = Offset - AttrSize;
 
-    OutOffset +=
-        cloneAttribute(*Die, InputDIE, Unit, Val, AttrSpec, AttrSize, AttrInfo);
+    OutOffset += cloneAttribute(*Die, InputDIE, DMO, Unit, StringPool, Val,
+                                AttrSpec, AttrSize, AttrInfo);
   }
 
   // Look for accelerator entries.
   uint16_t Tag = InputDIE.getTag();
   // FIXME: This is slightly wrong. An inline_subroutine without a
   // low_pc, but with AT_ranges might be interesting to get into the
   // accelerator tables too. For now stick with dsymutil's behavior.
   if ((Info.InDebugMap || AttrInfo.HasLowPc || AttrInfo.HasRanges) &&
       Tag != dwarf::DW_TAG_compile_unit &&
-      getDIENames(InputDIE, AttrInfo,
+      getDIENames(InputDIE, AttrInfo, StringPool,
                   Tag != dwarf::DW_TAG_inlined_subroutine)) {
     if (AttrInfo.MangledName && AttrInfo.MangledName != AttrInfo.Name)
       Unit.addNameAccelerator(Die, AttrInfo.MangledName,
                               Tag == dwarf::DW_TAG_inlined_subroutine);
     if (AttrInfo.Name) {
       if (AttrInfo.NameWithoutTemplate)
         Unit.addNameAccelerator(Die, AttrInfo.NameWithoutTemplate,
                                 /* SkipPubSection */ true);
       Unit.addNameAccelerator(Die, AttrInfo.Name,
                               Tag == dwarf::DW_TAG_inlined_subroutine);
     }
     if (AttrInfo.Name && isObjCSelector(AttrInfo.Name.getString()))
-      addObjCAccelerator(Unit, Die, AttrInfo.Name, /* SkipPubSection =*/true);
+      addObjCAccelerator(Unit, Die, AttrInfo.Name, StringPool,
+                         /* SkipPubSection =*/true);
 
   } else if (Tag == dwarf::DW_TAG_namespace) {
     if (!AttrInfo.Name)
-      AttrInfo.Name = Linker.StringPool.getEntry("(anonymous namespace)");
+      AttrInfo.Name = StringPool.getEntry("(anonymous namespace)");
     Unit.addNamespaceAccelerator(Die, AttrInfo.Name);
   } else if (isTypeTag(Tag) && !AttrInfo.IsDeclaration &&
-             getDIENames(InputDIE, AttrInfo) && AttrInfo.Name &&
+             getDIENames(InputDIE, AttrInfo, StringPool) && AttrInfo.Name &&
              AttrInfo.Name.getString()[0]) {
-    uint32_t Hash = hashFullyQualifiedName(InputDIE, Unit);
+    uint32_t Hash = hashFullyQualifiedName(InputDIE, Unit, DMO);
     uint64_t RuntimeLang =
         dwarf::toUnsigned(InputDIE.find(dwarf::DW_AT_APPLE_runtime_class))
             .getValueOr(0);
     bool ObjCClassIsImplementation =
         (RuntimeLang == dwarf::DW_LANG_ObjC ||
          RuntimeLang == dwarf::DW_LANG_ObjC_plus_plus) &&
         dwarf::toUnsigned(InputDIE.find(dwarf::DW_AT_APPLE_objc_complete_type))
             .getValueOr(0);
DIE *DwarfLinker::DIECloner::cloneDIE(const DWARFDie &InputDIE,
   if (!HasChildren) {
     // Update our size.
     Die->setSize(OutOffset - Die->getOffset());
     return Die;
   }
 
   // Recursively clone children.
   for (auto Child : InputDIE.children()) {
-    if (DIE *Clone = cloneDIE(Child, Unit, PCOffset, OutOffset, Flags)) {
+    if (DIE *Clone = cloneDIE(Child, DMO, Unit, StringPool, PCOffset, OutOffset,
+                              Flags)) {
       Die->addChild(Clone);
       OutOffset = Clone->getOffset() + Clone->getSize();
     }
   }
 
   // Account for the end of children marker.
   OutOffset += sizeof(int8_t);
   // Update our size.
   Die->setSize(OutOffset - Die->getOffset());
   return Die;
 }
 
 /// Patch the input object file relevant debug_ranges entries
 /// and emit them in the output file. Update the relevant attributes
 /// to point at the new entries.
 void DwarfLinker::patchRangesForUnit(const CompileUnit &Unit,
-                                     DWARFContext &OrigDwarf) const {
+                                     DWARFContext &OrigDwarf,
+                                     const DebugMapObject &DMO) const {
   DWARFDebugRangeList RangeList;
   const auto &FunctionRanges = Unit.getFunctionRanges();
   unsigned AddressSize = Unit.getOrigUnit().getAddressByteSize();
   DWARFDataExtractor RangeExtractor(OrigDwarf.getDWARFObj(),
                                     OrigDwarf.getDWARFObj().getRangeSection(),
                                     OrigDwarf.isLittleEndian(), AddressSize);
   auto InvalidRange = FunctionRanges.end(), CurrRange = InvalidRange;
   DWARFUnit &OrigUnit = Unit.getOrigUnit();
if (!Entries.empty()) {
       const DWARFDebugRangeList::RangeListEntry &First = Entries.front();
 
       if (CurrRange == InvalidRange ||
           First.StartAddress + OrigLowPc < CurrRange.start() ||
           First.StartAddress + OrigLowPc >= CurrRange.stop()) {
         CurrRange = FunctionRanges.find(First.StartAddress + OrigLowPc);
         if (CurrRange == InvalidRange ||
             CurrRange.start() > First.StartAddress + OrigLowPc) {
-          reportWarning("no mapping for range.");
+          reportWarning("no mapping for range.", DMO);
           continue;
         }
       }
     }
 
     Streamer->emitRangesEntries(UnitPcOffset, OrigLowPc, CurrRange, Entries,
                                 AddressSize);
   }
static void patchStmtList(DIE &Die, DIEInteger Offset) {
 
   llvm_unreachable("Didn't find DW_AT_stmt_list in cloned DIE!");
 }
 
 /// Extract the line table for \p Unit from \p OrigDwarf, and
 /// recreate a relocated version of these for the address ranges that
 /// are present in the binary.
 void DwarfLinker::patchLineTableForUnit(CompileUnit &Unit,
-                                        DWARFContext &OrigDwarf) {
+                                        DWARFContext &OrigDwarf,
+                                        RangesTy &Ranges,
+                                        const DebugMapObject &DMO) {
   DWARFDie CUDie = Unit.getOrigUnit().getUnitDIE();
   auto StmtList = dwarf::toSectionOffset(CUDie.find(dwarf::DW_AT_stmt_list));
   if (!StmtList)
     return;
 
   // Update the cloned DW_AT_stmt_list with the correct debug_line offset.
   if (auto *OutputDIE = Unit.getOutputUnitDIE())
     patchStmtList(*OutputDIE, DIEInteger(Streamer->getLineSectionSize()));
void DwarfLinker::patchLineTableForUnit(CompileUnit &Unit,
   // FIXME: LLVM hard-codes its prologue values. We just copy the
   // prologue over and that works because we act as both producer and
   // consumer. It would be nicer to have a real configurable line
   // table emitter.
   if (LineTable.Prologue.getVersion() < 2 ||
       LineTable.Prologue.getVersion() > 5 ||
       LineTable.Prologue.DefaultIsStmt != DWARF2_LINE_DEFAULT_IS_STMT ||
       LineTable.Prologue.OpcodeBase > 13)
-    reportWarning("line table parameters mismatch. Cannot emit.");
+    reportWarning("line table parameters mismatch. Cannot emit.", DMO);
   else {
     uint32_t PrologueEnd = *StmtList + 10 + LineTable.Prologue.PrologueLength;
     // DWARF v5 has an extra 2 bytes of information before the header_length
     // field.
     if (LineTable.Prologue.getVersion() == 5)
       PrologueEnd += 2;
     StringRef LineData = OrigDwarf.getDWARFObj().getLineSection().Data;
     MCDwarfLineTableParams Params;

 
 /// Read the frame info stored in the object, and emit the
 /// patched frame descriptions for the linked binary.
 ///
 /// This is actually pretty easy as the data of the CIEs and FDEs can
 /// be considered as black boxes and moved as is. The only thing to do
 /// is to patch the addresses in the headers.
 void DwarfLinker::patchFrameInfoForObject(const DebugMapObject &DMO,
+                                          RangesTy &Ranges,
                                           DWARFContext &OrigDwarf,
                                           unsigned AddrSize) {
   StringRef FrameData = OrigDwarf.getDWARFObj().getDebugFrameSection();
   if (FrameData.empty())
     return;
 
   DataExtractor Data(FrameData, OrigDwarf.isLittleEndian(), 0);
   uint32_t InputOffset = 0;
 
   // Store the data of the CIEs defined in this object, keyed by their
   // offsets.
   DenseMap<uint32_t, StringRef> LocalCIES;
 
   while (Data.isValidOffset(InputOffset)) {
     uint32_t EntryOffset = InputOffset;
     uint32_t InitialLength = Data.getU32(&InputOffset);
     if (InitialLength == 0xFFFFFFFF)
-      return reportWarning("Dwarf64 bits no supported");
+      return reportWarning("Dwarf64 bits no supported", DMO);
 
     uint32_t CIEId = Data.getU32(&InputOffset);
     if (CIEId == 0xFFFFFFFF) {
       // This is a CIE, store it.
       StringRef CIEData = FrameData.substr(EntryOffset, InitialLength + 4);
       LocalCIES[EntryOffset] = CIEData;
       // The -4 is to account for the CIEId we just read.
       InputOffset += InitialLength - 4;
if (Range == Ranges.end() || Range->first > Loc ||
       InputOffset = EntryOffset + InitialLength + 4;
       continue;
     }
 
     // This is an FDE, and we have a mapping.
     // Have we already emitted a corresponding CIE?
     StringRef CIEData = LocalCIES[CIEId];
     if (CIEData.empty())
-      return reportWarning("Inconsistent debug_frame content. Dropping.");
+      return reportWarning("Inconsistent debug_frame content. Dropping.", DMO);
 
     // Look if we already emitted a CIE that corresponds to the
     // referenced one (the CIE data is the key of that lookup).
     auto IteratorInserted = EmittedCIEs.insert(
         std::make_pair(CIEData, Streamer->getFrameSectionSize()));
     // If there is no CIE yet for this ID, emit it.
     if (IteratorInserted.second ||
         // FIXME: dsymutil-classic only caches the last used CIE for
for (const auto &Attr : Abbrev.attributes()) {
     if (hasODR && isODRAttribute(Attr.Attr))
       Form = dwarf::DW_FORM_ref_addr;
     Copy.AddAttribute(dwarf::Attribute(Attr.Attr), dwarf::Form(Form));
   }
 
   Linker.AssignAbbrev(Copy);
 }
 
-uint32_t DwarfLinker::DIECloner::hashFullyQualifiedName(DWARFDie DIE,
-                                                        CompileUnit &U,
-                                                        int RecurseDepth) {
+uint32_t DwarfLinker::DIECloner::hashFullyQualifiedName(
+    DWARFDie DIE, CompileUnit &U, const DebugMapObject &DMO, int RecurseDepth) {
   const char *Name = nullptr;
   DWARFUnit *OrigUnit = &U.getOrigUnit();
   CompileUnit *CU = &U;
   Optional<DWARFFormValue> Ref;
 
   while (1) {
     if (const char *CurrentName = DIE.getName(DINameKind::ShortName))
       Name = CurrentName;
 
     if (!(Ref = DIE.find(dwarf::DW_AT_specification)) &&
         !(Ref = DIE.find(dwarf::DW_AT_abstract_origin)))
       break;
 
     if (!Ref->isFormClass(DWARFFormValue::FC_Reference))
       break;
 
     CompileUnit *RefCU;
-    if (auto RefDIE = resolveDIEReference(Linker, CompileUnits, *Ref,
+    if (auto RefDIE = resolveDIEReference(Linker, DMO, CompileUnits, *Ref,
                                           U.getOrigUnit(), DIE, RefCU)) {
       CU = RefCU;
       OrigUnit = &RefCU->getOrigUnit();
       DIE = RefDIE;
     }
   }
 
   unsigned Idx = OrigUnit->getDIEIndex(DIE);
   if (!Name && DIE.getTag() == dwarf::DW_TAG_namespace)
     Name = "(anonymous namespace)";
 
   if (CU->getInfo(Idx).ParentIdx == 0 ||
       // FIXME: dsymutil-classic compatibility. Ignore modules.
       CU->getOrigUnit().getDIEAtIndex(CU->getInfo(Idx).ParentIdx).getTag() ==
           dwarf::DW_TAG_module)
     return djbHash(Name ? Name : "", djbHash(RecurseDepth ? "" : "::"));
 
   DWARFDie Die = OrigUnit->getDIEAtIndex(CU->getInfo(Idx).ParentIdx);
-  return djbHash((Name ? Name : ""),
-                 djbHash((Name ? "::" : ""),
-                         hashFullyQualifiedName(Die, *CU, ++RecurseDepth)));
+  return djbHash(
+      (Name ? Name : ""),
+              hashFullyQualifiedName(Die, *CU, DMO, ++RecurseDepth)));
 }
 
 static uint64_t getDwoId(const DWARFDie &CUDie, const DWARFUnit &Unit) {
   auto DwoId = dwarf::toUnsigned(
       CUDie.find({dwarf::DW_AT_dwo_id, dwarf::DW_AT_GNU_dwo_id}));
   if (DwoId)
     return *DwoId;
   return 0;
 }
 
-bool DwarfLinker::registerModuleReference(const DWARFDie &CUDie,
-                                          const DWARFUnit &Unit,
-                                          DebugMap &ModuleMap,
-                                          unsigned Indent) {
+bool DwarfLinker::registerModuleReference(
+    const DWARFDie &CUDie, const DWARFUnit &Unit, DebugMap &ModuleMap,
+    const DebugMapObject &DMO, RangesTy &Ranges, OffsetsStringPool &StringPool,
+    UniquingStringPool &UniquingStringPool, DeclContextTree &ODRContexts,
+    unsigned &UnitID, unsigned Indent) {
   std::string PCMfile = dwarf::toString(
       CUDie.find({dwarf::DW_AT_dwo_name, dwarf::DW_AT_GNU_dwo_name}), "");
   if (PCMfile.empty())
     return false;
 
   // Clang module DWARF skeleton CUs abuse this for the path to the module.
   std::string PCMpath = dwarf::toString(CUDie.find(dwarf::DW_AT_comp_dir), "");
   uint64_t DwoId = getDwoId(CUDie, Unit);
 
   std::string Name = dwarf::toString(CUDie.find(dwarf::DW_AT_name), "");
   if (Name.empty()) {
-    reportWarning("Anonymous module skeleton CU for " + PCMfile);
+    reportWarning("Anonymous module skeleton CU for " + PCMfile, DMO);
     return true;
   }
 
   if (Options.Verbose) {
     outs().indent(Indent);
     outs() << "Found clang module reference " << PCMfile;
   }
 
   auto Cached = ClangModules.find(PCMfile);
   if (Cached != ClangModules.end()) {
     // FIXME: Until PR27449 (https://llvm.org/bugs/show_bug.cgi?id=27449) is
     // fixed in clang, only warn about DWO_id mismatches in verbose mode.
     // ASTFileSignatures will change randomly when a module is rebuilt.
     if (Options.Verbose && (Cached->second != DwoId))
       reportWarning(Twine("hash mismatch: this object file was built against a "
                           "different version of the module ") +
-                    PCMfile);
+                        PCMfile,
+                    DMO);
     if (Options.Verbose)
       outs() << " [cached].\n";
     return true;
   }
   if (Options.Verbose)
     outs() << " ...\n";
 
   // Cyclic dependencies are disallowed by Clang, but we still
   // shouldn't run into an infinite loop, so mark it as processed now.
   ClangModules.insert({PCMfile, DwoId});
-  if (Error E = loadClangModule(PCMfile, PCMpath, Name, DwoId, ModuleMap,
-                                Indent + 2)) {
+  if (Error E = loadClangModule(PCMfile, PCMpath, Name, DwoId, ModuleMap, DMO,
+                                Ranges, StringPool, UniquingStringPool,
+                                ODRContexts, UnitID, Indent + 2)) {
     consumeError(std::move(E));
     return false;
   }
   return true;
 }
 
 ErrorOr<const object::ObjectFile &>
-DwarfLinker::loadObject(BinaryHolder &BinaryHolder, DebugMapObject &Obj,
+DwarfLinker::loadObject(BinaryHolder &BinaryHolder, const DebugMapObject &Obj,
                         const DebugMap &Map) {
   auto ErrOrObjs =
       BinaryHolder.GetObjectFiles(Obj.getObjectFilename(), Obj.getTimestamp());
   if (std::error_code EC = ErrOrObjs.getError()) {
-    reportWarning(Twine(Obj.getObjectFilename()) + ": " + EC.message());
+    reportWarning(Twine(Obj.getObjectFilename()) + ": " + EC.message(), Obj);
     return EC;
   }
   auto ErrOrObj = BinaryHolder.Get(Map.getTriple());
   if (std::error_code EC = ErrOrObj.getError())
-    reportWarning(Twine(Obj.getObjectFilename()) + ": " + EC.message());
+    reportWarning(Twine(Obj.getObjectFilename()) + ": " + EC.message(), Obj);
   return ErrOrObj;
 }
 
 Error DwarfLinker::loadClangModule(StringRef Filename, StringRef ModulePath,
                                    StringRef ModuleName, uint64_t DwoId,
-                                   DebugMap &ModuleMap, unsigned Indent) {
+                                   DebugMap &ModuleMap,
+                                   const DebugMapObject &DMO, RangesTy &Ranges,
+                                   OffsetsStringPool &StringPool,
+                                   UniquingStringPool &UniquingStringPool,
+                                   DeclContextTree &ODRContexts,
+                                   unsigned &UnitID, unsigned Indent) {
   SmallString<80> Path(Options.PrependPath);
   if (sys::path::is_relative(Filename))
     sys::path::append(Path, ModulePath, Filename);
   else
     sys::path::append(Path, Filename);
   BinaryHolder ObjHolder(Options.Verbose);
   auto &Obj = ModuleMap.addDebugMapObject(
       Path, sys::TimePoint<std::chrono::seconds>(), MachO::N_OSO);
   auto ErrOrObj = loadObject(ObjHolder, Obj, ModuleMap);
   if (!ErrOrObj) {
     // Try and emit more helpful warnings by applying some heuristics.
-    StringRef ObjFile = CurrentDebugObject->getObjectFilename();
+    StringRef ObjFile = DMO.getObjectFilename();
     bool isClangModule = sys::path::extension(Filename).equals(".pcm");
     bool isArchive = ObjFile.endswith(")");
     if (isClangModule) {
       StringRef ModuleCacheDir = sys::path::parent_path(Path);
       if (sys::fs::exists(ModuleCacheDir)) {
         // If the module's parent directory exists, we assume that the module
         // cache has expired and was pruned by clang.  A more adventurous
         // dsymutil would invoke clang to rebuild the module now.
Error DwarfLinker::loadClangModule(StringRef Filename, StringRef ModulePath,
   // Setup access to the debug info.
   auto DwarfContext = DWARFContext::create(*ErrOrObj);
   RelocationManager RelocMgr(*this);
   for (const auto &CU : DwarfContext->compile_units()) {
     maybeUpdateMaxDwarfVersion(CU->getVersion());
 
     // Recursively get all modules imported by this one.
     auto CUDie = CU->getUnitDIE(false);
-    if (!registerModuleReference(CUDie, *CU, ModuleMap, Indent)) {
+    if (!registerModuleReference(CUDie, *CU, ModuleMap, DMO, Ranges, StringPool,
+                                 UniquingStringPool, ODRContexts, UnitID,
+                                 Indent)) {
       if (Unit) {
         std::string Err =
             (Filename +
              ": Clang modules are expected to have exactly 1 compile unit.\n")
                 .str();
         errs() << Err;
         return make_error<StringError>(Err, inconvertibleErrorCode());
       }
       // FIXME: Until PR27449 (https://llvm.org/bugs/show_bug.cgi?id=27449) is
       // fixed in clang, only warn about DWO_id mismatches in verbose mode.
       // ASTFileSignatures will change randomly when a module is rebuilt.
       uint64_t PCMDwoId = getDwoId(CUDie, *CU);
       if (PCMDwoId != DwoId) {
         if (Options.Verbose)
           reportWarning(
               Twine("hash mismatch: this object file was built against a "
                     "different version of the module ") +
-              Filename);
+                  Filename,
+              DMO);
         // Update the cache entry with the DwoId of the module loaded from disk.
         ClangModules[Filename] = PCMDwoId;
       }
 
       // Add this module.
       Unit = llvm::make_unique<CompileUnit>(*CU, UnitID++, !Options.NoODR,
                                             ModuleName);
       Unit->setHasInterestingContent();
-      analyzeContextInfo(CUDie, 0, *Unit, &ODRContexts.getRoot(), StringPool,
-                         ODRContexts);
+      analyzeContextInfo(CUDie, 0, *Unit, &ODRContexts.getRoot(),
+                         UniquingStringPool, ODRContexts);
       // Keep everything.
       Unit->markEverythingAsKept();
     }
   }
   if (!Unit->getOrigUnit().getUnitDIE().hasChildren())
     return Error::success();
   if (Options.Verbose) {
     outs().indent(Indent);
     outs() << "cloning .debug_info from " << Filename << "\n";
   }
 
   std::vector<std::unique_ptr<CompileUnit>> CompileUnits;
   CompileUnits.push_back(std::move(Unit));
   DIECloner(*this, RelocMgr, DIEAlloc, CompileUnits, Options)
-      .cloneAllCompileUnits(*DwarfContext);
+      .cloneAllCompileUnits(*DwarfContext, DMO, Ranges, StringPool);
   return Error::success();
 }
 
-void DwarfLinker::DIECloner::cloneAllCompileUnits(DWARFContext &DwarfContext) {
+void DwarfLinker::DIECloner::cloneAllCompileUnits(
+    DWARFContext &DwarfContext, const DebugMapObject &DMO, RangesTy &Ranges,
+    OffsetsStringPool &StringPool) {
   if (!Linker.Streamer)
     return;
 
   for (auto &CurrentUnit : CompileUnits) {
     auto InputDIE = CurrentUnit->getOrigUnit().getUnitDIE();
     CurrentUnit->setStartOffset(Linker.OutputDebugInfoSize);
     if (CurrentUnit->getInfo(0).Keep) {
       // Clone the InputDIE into your Unit DIE in our compile unit since it
       // already has a DIE inside of it.
       CurrentUnit->createOutputDIE();
-      cloneDIE(InputDIE, *CurrentUnit, 0 /* PC offset */,
+      cloneDIE(InputDIE, DMO, *CurrentUnit, StringPool, 0 /* PC offset */,
                11 /* Unit Header size */, 0, CurrentUnit->getOutputUnitDIE());
     }
     Linker.OutputDebugInfoSize = CurrentUnit->computeNextUnitOffset();
     if (Linker.Options.NoOutput)
       continue;
 
     if (LLVM_LIKELY(!Linker.Options.Update)) {
       // FIXME: for compatibility with the classic dsymutil, we emit an empty
       // line table for the unit, even if the unit doesn't actually exist in
       // the DIE tree.
-      Linker.patchLineTableForUnit(*CurrentUnit, DwarfContext);
+      Linker.patchLineTableForUnit(*CurrentUnit, DwarfContext, Ranges, DMO);
       Linker.emitAcceleratorEntriesForUnit(*CurrentUnit);
-      Linker.patchRangesForUnit(*CurrentUnit, DwarfContext);
+      Linker.patchRangesForUnit(*CurrentUnit, DwarfContext, DMO);
       Linker.Streamer->emitLocationsForUnit(*CurrentUnit, DwarfContext);
     } else {
       Linker.emitAcceleratorEntriesForUnit(*CurrentUnit);
     }
   }
 
   if (Linker.Options.NoOutput)
     return;

 
 bool DwarfLinker::link(const DebugMap &Map) {
   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.
-  UnitID = 0;
+  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()) {
-    CurrentDebugObject = Obj.get();
+    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 (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 (Obj->getType() == MachO::N_AST) {
-      StringRef File = Obj->getObjectFilename();
+    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";
         continue;
       }
       sys::fs::file_status Stat;
       if (auto errc = sys::fs::status(File, Stat)) {
         errs() << "Warning: " << errc.message() << "\n";
         continue;
       }
-      if (!Options.NoTimestamp && Stat.getLastModificationTime() !=
-                                      sys::TimePoint<>(Obj->getTimestamp())) {
+      if (!Options.NoTimestamp &&
+          Stat.getLastModificationTime() !=
+              sys::TimePoint<>(LinkContext.DMO.getTimestamp())) {
         errs() << "Warning: Timestamp mismatch for " << File << ": "
                << Stat.getLastModificationTime() << " and "
-               << sys::TimePoint<>(Obj->getTimestamp()) << "\n";
+               << sys::TimePoint<>(LinkContext.DMO.getTimestamp()) << "\n";
         continue;
       }
 
       // Copy the module into the .swift_ast section.
       if (!Options.NoOutput)
         Streamer->emitSwiftAST((*ErrorOrMem)->getBuffer());
       continue;
     }
 
-    auto ErrOrObj = loadObject(BinHolder, *Obj, Map);
-    if (!ErrOrObj)
+    if (!LinkContext.ObjectFile)
       continue;
 
     // Look for relocations that correspond to debug map entries.
-    RelocationManager RelocMgr(*this);
     if (LLVM_LIKELY(!Options.Update) &&
-        !RelocMgr.findValidRelocsInDebugInfo(*ErrOrObj, *Obj)) {
+        !LinkContext.RelocMgr.findValidRelocsInDebugInfo(
+            *LinkContext.ObjectFile, LinkContext.DMO)) {
       if (Options.Verbose)
         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.
-    auto DwarfContext = DWARFContext::create(*ErrOrObj);
-    startDebugObject(*DwarfContext, *Obj);
+    if (!LinkContext.DwarfContext)
+      continue;
+
+    startDebugObject(LinkContext);
 
     // In a first phase, just read in the debug info and load all clang modules.
-    for (const auto &CU : DwarfContext->compile_units()) {
+    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)) {
-        Units.push_back(llvm::make_unique<CompileUnit>(
+          !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 : Units)
+      for (auto &CurrentUnit : LinkContext.CompileUnits)
         analyzeContextInfo(CurrentUnit->getOrigUnit().getUnitDIE(), 0,
-                         *CurrentUnit, &ODRContexts.getRoot(), StringPool,
-                         ODRContexts);
+                           *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.
+  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]; });
+        }
+      }
 
-    // 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
+      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 : Units)
+        for (auto &CurrentUnit : LinkContext.CompileUnits)
           CurrentUnit->markEverythingAsKept();
-      Streamer->copyInvariantDebugSection(*ErrOrObj, Options);
+        Streamer->copyInvariantDebugSection(*LinkContext.ObjectFile, Options);
       } else {
-      for (auto &CurrentUnit : Units)
-        lookForDIEsToKeep(RelocMgr, CurrentUnit->getOrigUnit().getUnitDIE(),
-                          *Obj, *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.
-    RelocMgr.resetValidRelocs();
-    if (RelocMgr.hasValidRelocs() || LLVM_UNLIKELY(Options.Update))
-      DIECloner(*this, RelocMgr, DIEAlloc, Units, Options)
-          .cloneAllCompileUnits(*DwarfContext);
-    if (!Options.NoOutput && !Units.empty() && LLVM_LIKELY(!Options.Update))
-      patchFrameInfoForObject(*Obj, *DwarfContext,
-                              Units[0]->getOrigUnit().getAddressByteSize());
+        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());
 
       // Clean-up before starting working on the next object.
-    endDebugObject();
+      endDebugObject(LinkContext);
     }
 
     // Emit everything that's global.
     if (!Options.NoOutput) {
       Streamer->emitAbbrevs(Abbreviations, MaxDwarfVersion);
-    Streamer->emitStrings(StringPool);
+      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";
 }