[BOLT][DWARF] Change to process and write out TUs first then CUs in batches

[ayermolo]

Summary

To reduce memory footprint changed so that we process and write out TUs first,
reset DIEBuilder and process CUs. CUs are processed in buckets. First bucket
contains all the CUs with cross CU references. Rest processd one at a time.

clang-17 build in debug mode, by clang-17.
before
8:25.81 real, 834.37 user, 86.03 sys, 0 amem, 79525064 mmem
8:02.20 real, 820.46 user, 81.81 sys, 0 amem, 79501616 mmem
7:52.69 real, 802.01 user, 83.99 sys, 0 amem, 79534392 mmem

after
7:49.35 real, 822.04 user, 66.19 sys, 0 amem, 34934260 mmem
7:42.16 real, 825.46 user, 63.52 sys, 0 amem, 34951660 mmem
7:46.71 real, 821.11 user, 63.14 sys, 0 amem, 34981164 mmem

Depends on D151908

[ayermolo]

rebase

[ayermolo]

rebase + fixed cross-cu references when CUs don't share abbrev + tests.

[ayermolo]

rebase

[ayermolo]

rebase

[maksfb]

Did you look into test failures?

[ayermolo]

rebase

[ayermolo]

rebase

[maksfb]

Please update the summary and include runtime memory data.

bolt/include/bolt/Core/DIEBuilder.h

66

Maybe?

bolt/lib/Core/DIEBuilder.cpp

245

253

nit: braces

812

Use braces.

bolt/lib/Rewrite/DWARFRewriter.cpp

247

Not needed.

445

Add documentation.

464

Add braces.

640

1325

Secs?

1447

[ayermolo]

addressed comments

[ayermolo]

rebase

[maksfb]

LGTM

[ayermolo]

fixed mac build + rebase

[ayermolo]

Reduced the scope of variables

bolt/include/bolt/Core/DIEBuilder.h

struct UnitInfo {
     DIE *UnitDie = nullptr;
     uint32_t UnitId = 0;
     uint32_t UnitOffset = 0;
     uint32_t UnitLength = 0;
     bool Isconstructed = false;
     std::unordered_map<uint64_t, uint32_t> DIEIDMap;
   };
 
+  enum class ProcessingType { DWARF4TYPES, DWARF5TYPES, CUs };
+
 private:
   struct LocWithReference {
     LocWithReference(std::vector<uint8_t> &&BlockData, DWARFUnit &U, DIE &Die,
                      dwarf::Form Form, dwarf::Attribute Attr)
         : BlockData(BlockData), U(U), Die(Die), Form(Form), Attr(Attr) {}
     std::vector<uint8_t> BlockData;
     DWARFUnit &U;
     DIE &Die;
     dwarf::Form Form;
     dwarf::Attribute Attr;
   };
   struct ForwardReferenceInfo {
     ForwardReferenceInfo(DIEInfo *Die,
                          DWARFAbbreviationDeclaration::AttributeSpec Spec)
         : Dst(Die), AttrSpec(Spec) {}
     DIEInfo *Dst;
     DWARFAbbreviationDeclaration::AttributeSpec AttrSpec;
   };
 
+  struct State {
     std::unordered_map<uint64_t, uint32_t> UnitIDMap;
     std::unordered_map<DWARFUnit *, DIE *> TypeDIEMap;
-  std::vector<DWARFUnit *> DUList;
+    std::list<DWARFUnit *> DUList;
     std::vector<UnitInfo> CloneUnitCtxMap;
     std::vector<std::pair<DIEInfo *, ForwardReferenceInfo>> ForwardReferences;
-  FoldingSet<DIEAbbrev> AbbreviationsSet;
-  std::vector<std::unique_ptr<DIEAbbrev>> Abbreviations;
     std::vector<DWARFUnit *> DWARF4TUVector;
+    std::vector<DWARFUnit *> DWARF5TUVector;
+    std::vector<DWARFUnit *> DWARFCUVector;
     std::vector<LocWithReference> LocWithReferencesToProcess;
     BumpPtrAllocator DIEAlloc;
+    ProcessingType Type;
+  };
 
+  std::unique_ptr<State> BuilderState;
+  FoldingSet<DIEAbbrev> AbbreviationsSet;
+  std::vector<std::unique_ptr<DIEAbbrev>> Abbreviations;
+  DWARFContext *DwarfContext{nullptr};
+  bool IsDWO{false};
+  uint64_t UnitSize{0};
+  llvm::DenseSet<uint64_t> AllProcessed;
+
+  /// Returns current state of the DIEBuilder
+  State &getState() { return *BuilderState.get(); }
   /// Resolve the reference in DIE, if target is not loaded into IR,
   /// pre-allocate it. \p RefCU will be updated to the Unit specific by \p
   /// RefValue.
-  DWARFDie resolveDIEReference(const DWARFFormValue &RefValue,
-                               DWARFUnit *&RefCU,
-                               DWARFDebugInfoEntry &DwarfDebugInfoEntry,
-                               const std::vector<DWARFUnit *> &DUOffsetList);
+  DWARFDie resolveDIEReference(
+      const DWARFFormValue &RefValue,
+      const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
+      DWARFUnit *&RefCU, DWARFDebugInfoEntry &DwarfDebugInfoEntry);
 
   /// Resolve the reference in DIE, if target is not loaded into IR,
   /// pre-allocate it. \p RefCU will be updated to the Unit specific by \p
   /// RefValue.
-  DWARFDie resolveDIEReference(const uint64_t ReffOffset, DWARFUnit *&RefCU,
-                               DWARFDebugInfoEntry &DwarfDebugInfoEntry,
-                               const std::vector<DWARFUnit *> &DUOffsetList);
+  DWARFDie resolveDIEReference(
+      const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
+      const uint64_t ReffOffset, DWARFUnit *&RefCU,
+      DWARFDebugInfoEntry &DwarfDebugInfoEntry);
 
   /// Clone one attribute according the format. \return the size of this
   /// attribute.
   void
   cloneAttribute(DIE &Die, const DWARFDie &InputDIE, DWARFUnit &U,
                  const DWARFFormValue &Val,
-                 const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
-                 const std::vector<DWARFUnit *> &DUOffsetList);
+                 const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec);
 
   /// Clone an attribute in string format.
   void cloneStringAttribute(
       DIE &Die, const DWARFUnit &U,
       const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
       const DWARFFormValue &Val);
 
   /// Clone an attribute in reference format.
   void cloneDieReferenceAttribute(
       DIE &Die, const DWARFUnit &U, const DWARFDie &InputDIE,
       const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
-      const DWARFFormValue &Val, const std::vector<DWARFUnit *> &DUOffsetList);
+      const DWARFFormValue &Val);
 
   /// Clone an attribute in block format.
   void cloneBlockAttribute(
       DIE &Die, DWARFUnit &U,
       const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
       const DWARFFormValue &Val);
 
   enum class CloneExpressionStage { INIT, PATCH };
void cloneLoclistAttrubute(
       const DWARFFormValue &Val);
 
   /// Update the Cross-CU reference offset.
   void computeReference();
 
   /// Update the Offset and Size of DIE.
   uint32_t computeDIEOffset(const DWARFUnit &CU, DIE &Die, uint32_t &CurOffset);
 
-  void registerUnit(DWARFUnit &DU);
+  void registerUnit(DWARFUnit &DU, bool NeedSort);
 
   /// \return the unique ID of \p U if it exists.
   std::optional<uint32_t> getUnitId(const DWARFUnit &DU);
 
-  UnitInfo &getUnitInfo(uint32_t UnitId) { return CloneUnitCtxMap[UnitId]; }
+  UnitInfo &getUnitInfo(uint32_t UnitId) {
+    return getState().CloneUnitCtxMap[UnitId];
+  }
 
   DIEInfo &getDIEInfo(uint32_t UnitId, uint32_t DIEId) {
-    if (CloneUnitCtxMap[UnitId].DieInfoVector.size() > DIEId)
-      return *CloneUnitCtxMap[UnitId].DieInfoVector[DIEId].get();
+    if (getState().CloneUnitCtxMap[UnitId].DieInfoVector.size() > DIEId)
+      return *getState().CloneUnitCtxMap[UnitId].DieInfoVector[DIEId].get();
 
     errs() << "BOLT-ERROR: The DIE is not allocated before looking up, some"
            << "unexpected corner cases happened.\n";
-    return *CloneUnitCtxMap[UnitId].DieInfoVector.front().get();
+    return *getState().CloneUnitCtxMap[UnitId].DieInfoVector.front().get();
   }
 
   std::optional<uint32_t> getAllocDIEId(const DWARFUnit &DU,
                                         const uint64_t Offset) {
     const UnitInfo &UnitInfo = getUnitInfoByDwarfUnit(DU);
     auto Iter = UnitInfo.DIEIDMap.find(Offset);
     return (Iter == UnitInfo.DIEIDMap.end())
                ? std::nullopt
DIEInfo &getDIEInfoByDwarfDie(DWARFDie &DwarfDie) {
     return getDIEInfo(*UnitId, *HasDieId);
   }
 
   uint32_t allocDIE(const DWARFUnit &DU, const DWARFDie &DDie,
                     BumpPtrAllocator &Alloc, const uint32_t UId);
 
   /// Construct IR for \p DU. \p DUOffsetList specific the Unit in current
   /// Section.
-  void constructFromUnit(DWARFUnit &DU, std::vector<DWARFUnit *> &DUOffsetList);
+  void constructFromUnit(DWARFUnit &DU);
 
   /// Construct a DIE for \p DDie in \p U. \p DUOffsetList specific the Unit in
   /// current Section.
-  DIE *constructDIEFast(DWARFDie &DDie, DWARFUnit &U, uint32_t UnitId,
-                        std::vector<DWARFUnit *> &DUOffsetList);
+  DIE *constructDIEFast(DWARFDie &DDie, DWARFUnit &U, uint32_t UnitId);
 
 public:
   DIEBuilder(DWARFContext *DwarfContext, bool IsDWO = false);
 
+  /// Returns enum to what we are currently processing.
+  ProcessingType getCurrentProcessingState() { return getState().Type; }
+
+  /// Constructs IR for Type Units.
+  void buildTypeUnits(const bool Init = true);
+  /// Constructs IR for all the CUs.
+  void buildCompileUnits(const bool Init = true);
+  /// Constructs IR for CUs in a vector.
+  void buildCompileUnits(const std::vector<DWARFUnit *> &CUs);
+  /// Preventing implicit conversions.
+  template <class T> void buildCompileUnits(T) = delete;
+  void buildBoth();
+
   /// Returns UnitInfo for DWARFUnit
   UnitInfo &getUnitInfoByDwarfUnit(const DWARFUnit &DwarfUnit) {
     std::optional<uint32_t> UnitId = getUnitId(DwarfUnit);
     return getUnitInfo(*UnitId);
   }
 
   const std::vector<std::unique_ptr<DIEInfo>> &getDIEsByUnit(DWARFUnit &DU) {
     UnitInfo &U = getUnitInfoByDwarfUnit(DU);
     return U.DieInfoVector;
   }
   std::vector<std::unique_ptr<DIEAbbrev>> &getAbbrevs() {
     return Abbreviations;
   }
   DIE *getTypeDIE(DWARFUnit &DU) {
-    if (TypeDIEMap.count(&DU))
-      return TypeDIEMap[&DU];
+    if (getState().TypeDIEMap.count(&DU))
+      return getState().TypeDIEMap[&DU];
 
     errs() << "BOLT-ERROR: unable to find TypeUnit for Type Unit at offset 0x"
            << DU.getOffset() << "\n";
     return nullptr;
   }
 
-  std::vector<DWARFUnit *> getDWARF4TUVector() { return DWARF4TUVector; }
-  bool isEmpty() { return CloneUnitCtxMap.empty(); }
+  std::vector<DWARFUnit *> &getDWARF4TUVector() {
+    return getState().DWARF4TUVector;
+  }
+  std::vector<DWARFUnit *> &getDWARF5TUVector() {
+    return getState().DWARF5TUVector;
+  }
+  std::vector<DWARFUnit *> &getDWARFCUVector() {
+    return getState().DWARFCUVector;
+  }
+  /// Returns list of CUs for which IR was build.
+  std::list<DWARFUnit *> &getProcessedCUs() { return getState().DUList; }
+  bool isEmpty() { return getState().CloneUnitCtxMap.empty(); }
 
   DIE *getUnitDIEbyUnit(const DWARFUnit &DU) {
     const UnitInfo &U = getUnitInfoByDwarfUnit(DU);
     return U.UnitDie;
   }
 
   /// Generate and populate all Abbrevs.
   void generateAbbrevs();
   void generateUnitAbbrevs(DIE *Die);
   void assignAbbrev(DIEAbbrev &Abbrev);
 
   /// Finish current DIE construction.
   void finish();
 
   // Interface to edit DIE
-  template <class T> T *allocateDIEValue() { return new (DIEAlloc) T; }
+  template <class T> T *allocateDIEValue() {
+    return new (getState().DIEAlloc) T;
+  }
 
   DIEValueList::value_iterator addValue(DIEValueList *Die, const DIEValue &V) {
-    return Die->addValue(DIEAlloc, V);
+    return Die->addValue(getState().DIEAlloc, V);
   }
 
   template <class T>
   DIEValueList::value_iterator addValue(DIEValueList *Die,
                                         dwarf::Attribute Attribute,
                                         dwarf::Form Form, T &&Value) {
-    return Die->addValue(DIEAlloc, Attribute, Form, std::forward<T>(Value));
+    return Die->addValue(getState().DIEAlloc, Attribute, Form,
+                         std::forward<T>(Value));
   }
 
   template <class T>
   bool replaceValue(DIEValueList *Die, dwarf::Attribute Attribute,
                     dwarf::Form Form, T &&NewValue) {
-    return Die->replaceValue(DIEAlloc, Attribute, Form,
+    return Die->replaceValue(getState().DIEAlloc, Attribute, Form,
                              std::forward<T>(NewValue));
   }
 
   template <class T>
   bool replaceValue(DIEValueList *Die, dwarf::Attribute Attribute,
                     dwarf::Attribute NewAttribute, dwarf::Form Form,
                     T &&NewValue) {
-    return Die->replaceValue(DIEAlloc, Attribute, NewAttribute, Form,
+    return Die->replaceValue(getState().DIEAlloc, Attribute, NewAttribute, Form,
                              std::forward<T>(NewValue));
   }
 
   bool replaceValue(DIEValueList *Die, dwarf::Attribute Attribute,
                     dwarf::Form Form, DIEValue &NewValue) {
-    return Die->replaceValue(DIEAlloc, Attribute, Form, NewValue);
+    return Die->replaceValue(getState().DIEAlloc, Attribute, Form, NewValue);
   }
 
   template <class T>
   bool deleteValue(DIEValueList *Die, dwarf::Attribute Attribute) {
     return Die->deleteValue(Attribute);
   }
 };
 } // namespace bolt
 } // namespace llvm
 
 #endif

bolt/include/bolt/Core/DebugData.h

 #include "llvm/ADT/SmallVector.h"
 #include "llvm/CodeGen/DIE.h"
 #include "llvm/DebugInfo/DWARF/DWARFContext.h"
 #include "llvm/MC/MCDwarf.h"
 #include "llvm/Support/SMLoc.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cstdint>
 #include <map>
+#include <memory>
 #include <mutex>
 #include <string>
 #include <unordered_map>
 #include <unordered_set>
 #include <utility>
 #include <vector>
 
 #define DWARF2_FLAG_END_SEQUENCE (1 << 4)
public:
   virtual ~DebugAddrWriter(){};
   /// Given an address returns an index in .debug_addr.
   /// Adds Address to map.
   uint32_t getIndexFromAddress(uint64_t Address, DWARFUnit &CU);
 
   /// Adds {\p Address, \p Index} to \p CU.
   void addIndexAddress(uint64_t Address, uint32_t Index, DWARFUnit &CU);
 
-  /// Creates consolidated .debug_addr section, and builds DWOID to offset map.
-  virtual AddressSectionBuffer finalize();
+  /// Write out entries in to .debug_addr section for CUs.
+  virtual void update(DIEBuilder &DIEBlder, DWARFUnit &CUs);
 
-  /// Given DWARFUnit \p Unit returns offset of this CU in to .debug_addr
-  /// section.
-  virtual uint64_t getOffset(DWARFUnit &Unit);
-
-  /// Returns True if CU exists in the DebugAddrWriter.
-  bool doesCUExist(DWARFUnit &Unit) {
-    return DWOIdToOffsetMap.count(getCUID(Unit)) > 0;
-  }
+  /// Return buffer with all the entries in .debug_addr already writen out using
+  /// update(...).
+  virtual AddressSectionBuffer &finalize() { return *Buffer; }
 
   /// Returns False if .debug_addr section was created..
   bool isInitialized() const { return !AddressMaps.empty(); }
 
 protected:
   class AddressForDWOCU {
   public:
     AddressToIndexMap::iterator find(uint64_t Address) {
protected:
   virtual uint64_t getCUID(DWARFUnit &Unit) {
     assert(Unit.getDWOId() && "Unit is not Skeleton CU.");
     return *Unit.getDWOId();
   }
 
   BinaryContext *BC;
   /// Maps DWOID to AddressForDWOCU.
   std::unordered_map<uint64_t, AddressForDWOCU> AddressMaps;
-  /// Maps DWOID to offset within .debug_addr section.
-  std::unordered_map<uint64_t, uint64_t> DWOIdToOffsetMap;
   /// Mutex used for parallel processing of debug info.
   std::mutex WriterMutex;
+  std::unique_ptr<AddressSectionBuffer> Buffer;
+  std::unique_ptr<raw_svector_ostream> AddressStream;
+  /// Used to track sections that were not modified so that they can be re-used.
+  DenseMap<uint64_t, uint64_t> UnmodifiedAddressOffsets;
 };
 
 class DebugAddrWriterDwarf5 : public DebugAddrWriter {
 public:
   DebugAddrWriterDwarf5() = delete;
   DebugAddrWriterDwarf5(BinaryContext *BC) : DebugAddrWriter(BC) {}
 
-  /// Creates consolidated .debug_addr section, and builds DWOID to offset map.
-  AddressSectionBuffer finalize() override;
-  /// Given DWARFUnit \p Unit returns offset of this CU in to .debug_addr
-  /// section.
-  uint64_t getOffset(DWARFUnit &Unit) override;
+  /// Write out entries in to .debug_addr section for CUs.
+  virtual void update(DIEBuilder &DIEBlder, DWARFUnit &CUs) override;
 
 protected:
   /// Given DWARFUnit \p Unit returns either DWO ID or it's offset within
   /// .debug_info.
   uint64_t getCUID(DWARFUnit &Unit) override {
     if (Unit.isDWOUnit()) {
       DWARFUnit *SkeletonCU = Unit.getLinkedUnit();
       return SkeletonCU->getOffset();
public:
   /// Initializes Buffer and Stream.
   void initialize(const DWARFSection &StrOffsetsSection,
                   const std::optional<StrOffsetsContributionDescriptor> Contr);
 
   /// Update Str offset in .debug_str in .debug_str_offsets.
   void updateAddressMap(uint32_t Index, uint32_t Address);
 
   /// Writes out current sections entry into .debug_str_offsets.
-  void finalizeSection(DWARFUnit &Unit);
+  void finalizeSection(DWARFUnit &Unit, DIEBuilder &DIEBldr);
 
   /// Returns False if no strings were added to .debug_str.
   bool isFinalized() const { return !StrOffsetsBuffer->empty(); }
 
   /// Returns buffer containing .debug_str_offsets.
   std::unique_ptr<DebugStrOffsetsBufferVector> releaseBuffer() {
     return std::move(StrOffsetsBuffer);
   }
 
 private:
   std::unique_ptr<DebugStrOffsetsBufferVector> StrOffsetsBuffer;
   std::unique_ptr<raw_svector_ostream> StrOffsetsStream;
   std::map<uint32_t, uint32_t> IndexToAddressMap;
-  DenseSet<uint64_t> ProcessedBaseOffsets;
+  std::unordered_map<uint64_t, uint64_t> ProcessedBaseOffsets;
   // Section size not including header.
   uint32_t CurrentSectionSize{0};
   bool StrOffsetSectionWasModified = false;
 };
 
 using DebugStrBufferVector = SmallVector<char, 16>;
 class DebugStrWriter {
 public:

bolt/include/bolt/Rewrite/DWARFRewriter.h

private:
 
   /// Entries for GDB Index Types CU List
   using GDBIndexTUEntryType = std::vector<GDBIndexTUEntry>;
   GDBIndexTUEntryType GDBIndexTUEntryVector;
 
   /// DWARFLegacy is all DWARF versions before DWARF 5.
   enum class DWARFVersion { DWARFLegacy, DWARF5 };
 
+  /// Used to track last CU offset for GDB Index.
+  uint32_t CUOffset{0};
+
   /// Update debug info for all DIEs in \p Unit.
   void updateUnitDebugInfo(DWARFUnit &Unit, DIEBuilder &DIEBldr,
                            DebugLocWriter &DebugLocWriter,
                            DebugRangesSectionWriter &RangesSectionWriter,
                            std::optional<uint64_t> RangesBase = std::nullopt);
 
   /// Patches the binary for an object's address ranges to be updated.
   /// The object can be anything that has associated address ranges via either
   /// DW_AT_low/high_pc or DW_AT_ranges (i.e. functions, lexical blocks, etc).
   /// \p DebugRangesOffset is the offset in .debug_ranges of the object's
   /// new address ranges in the output binary.
   /// \p Unit Compile unit the object belongs to.
   /// \p DIE is the object's DIE in the input binary.
   /// \p RangesBase if present, update \p DIE to use  DW_AT_GNU_ranges_base
   ///    attribute.
   void updateDWARFObjectAddressRanges(
       DWARFUnit &Unit, DIEBuilder &DIEBldr, DIE &Die,
       uint64_t DebugRangesOffset, uint64_t LowPCToUse,
       std::optional<uint64_t> RangesBase = std::nullopt);
 
   std::unique_ptr<DebugBufferVector>
   makeFinalLocListsSection(DWARFVersion Version);
 
+  /// Finalize type sections in the main binary.
+  CUOffsetMap finalizeTypeSections(DIEBuilder &DIEBlder, DIEStreamer &Streamer);
+
+  /// Process and write out CUs that are passsed in.
+  void finalizeCompileUnits(DIEBuilder &DIEBlder, DIEStreamer &Streamer,
+                            CUOffsetMap &CUMap,
+                            const std::list<DWARFUnit *> &CUs);
+
   /// Finalize debug sections in the main binary.
-  CUOffsetMap finalizeDebugSections(DIEBuilder &DIEBlder);
+  void finalizeDebugSections(DIEBuilder &DIEBlder, DIEStreamer &Streamer,
+                             raw_svector_ostream &ObjOS, CUOffsetMap &CUMap);
 
   /// Patches the binary for DWARF address ranges (e.g. in functions and lexical
   /// blocks) to be updated.
   void updateDebugAddressRanges();
 
   /// Rewrite .gdb_index section if present.
   void updateGdbIndexSection(CUOffsetMap &CUMap, uint32_t NumCUs);
 

bolt/lib/Core/DIEBuilder.cpp

 #include "llvm/Support/YAMLTraits.h"
 
 #include <algorithm>
 #include <cstdint>
 #include <memory>
 #include <string>
 #include <unordered_map>
 #include <utility>
+#include <vector>
 
 #undef DEBUG_TYPE
 #define DEBUG_TYPE "bolt"
 namespace llvm {
 namespace bolt {
 
 void DIEBuilder::computeReference() {
-  for (auto &[SrcDIEInfo, ReferenceInfo] : ForwardReferences) {
+  for (auto &[SrcDIEInfo, ReferenceInfo] : getState().ForwardReferences) {
     DIEInfo *DstDIEInfo = ReferenceInfo.Dst;
     UnitInfo &DstUnitInfo = getUnitInfo(DstDIEInfo->UnitId);
     dwarf::Attribute Attr = ReferenceInfo.AttrSpec.Attr;
     dwarf::Form Form = ReferenceInfo.AttrSpec.Form;
 
     uint64_t NewAddr = DstDIEInfo->Die->getOffset() + DstUnitInfo.UnitOffset;
-    SrcDIEInfo->Die->replaceValue(DIEAlloc, Attr, Form, DIEInteger(NewAddr));
+    SrcDIEInfo->Die->replaceValue(getState().DIEAlloc, Attr, Form,
+                                  DIEInteger(NewAddr));
   }
 
   // Handling referenes in location expressions.
-  for (LocWithReference &LocExpr : LocWithReferencesToProcess) {
+  for (LocWithReference &LocExpr : getState().LocWithReferencesToProcess) {
     SmallVector<uint8_t, 32> Buffer;
     DataExtractor Data(StringRef((const char *)LocExpr.BlockData.data(),
                                  LocExpr.BlockData.size()),
                        LocExpr.U.isLittleEndian(),
                        LocExpr.U.getAddressByteSize());
     DWARFExpression Expr(Data, LocExpr.U.getAddressByteSize(),
                          LocExpr.U.getFormParams().Format);
     cloneExpression(Data, Expr, LocExpr.U, Buffer, CloneExpressionStage::PATCH);
 
     DIEValueList *AttrVal;
     if (LocExpr.Form == dwarf::DW_FORM_exprloc) {
-      DIELoc *DL = new (DIEAlloc) DIELoc;
+      DIELoc *DL = new (getState().DIEAlloc) DIELoc;
       DL->setSize(Buffer.size());
       AttrVal = static_cast<DIEValueList *>(DL);
     } else {
-      DIEBlock *DBL = new (DIEAlloc) DIEBlock;
+      DIEBlock *DBL = new (getState().DIEAlloc) DIEBlock;
       DBL->setSize(Buffer.size());
       AttrVal = static_cast<DIEValueList *>(DBL);
     }
     for (auto Byte : Buffer)
-      AttrVal->addValue(DIEAlloc, static_cast<dwarf::Attribute>(0),
+      AttrVal->addValue(getState().DIEAlloc, static_cast<dwarf::Attribute>(0),
                         dwarf::DW_FORM_data1, DIEInteger(Byte));
 
     DIEValue Value;
     if (LocExpr.Form == dwarf::DW_FORM_exprloc)
       Value =
           DIEValue(dwarf::Attribute(LocExpr.Attr), dwarf::Form(LocExpr.Form),
                    static_cast<DIELoc *>(AttrVal));
     else
       Value =
           DIEValue(dwarf::Attribute(LocExpr.Attr), dwarf::Form(LocExpr.Form),
                    static_cast<DIEBlock *>(AttrVal));
 
-    LocExpr.Die.replaceValue(DIEAlloc, LocExpr.Attr, LocExpr.Form, Value);
+    LocExpr.Die.replaceValue(getState().DIEAlloc, LocExpr.Attr, LocExpr.Form,
+                             Value);
   }
 
   return;
 }
 
 uint32_t DIEBuilder::allocDIE(const DWARFUnit &DU, const DWARFDie &DDie,
                               BumpPtrAllocator &Alloc, const uint32_t UId) {
   UnitInfo &UnitInfo = getUnitInfo(UId);
   const uint64_t DDieOffset = DDie.getOffset();
   if (UnitInfo.DIEIDMap.count(DDieOffset))
     return UnitInfo.DIEIDMap[DDieOffset];
 
   DIE *Die = DIE::get(Alloc, dwarf::Tag(DDie.getTag()));
   const uint32_t DId = UnitInfo.DieInfoVector.size();
   UnitInfo.DIEIDMap[DDieOffset] = DId;
   UnitInfo.DieInfoVector.emplace_back(
       std::make_unique<DIEInfo>(DIEInfo{Die, DId, UId}));
   return DId;
 }
 
-void DIEBuilder::constructFromUnit(DWARFUnit &DU,
-                                   std::vector<DWARFUnit *> &DUOffsetList) {
+void DIEBuilder::constructFromUnit(DWARFUnit &DU) {
   std::optional<uint32_t> UnitId = getUnitId(DU);
   if (!UnitId) {
     errs() << "BOLT-WARNING: [internal-dwarf-error]: "
            << "Skip Unit at " << Twine::utohexstr(DU.getOffset()) << "\n";
     return;
   }
 
   const uint32_t UnitHeaderSize = DU.getHeaderSize();
do {
     if (!DIEEntry.extractFast(DU, &DIEOffset, DebugInfoData, NextCUOffset,
                               Parents.back()))
       break;
 
     if (const DWARFAbbreviationDeclaration *AbbrDecl =
             DIEEntry.getAbbreviationDeclarationPtr()) {
       DWARFDie DDie(&DU, &DIEEntry);
 
-      DIE *CurDIE = constructDIEFast(DDie, DU, *UnitId, DUOffsetList);
+      DIE *CurDIE = constructDIEFast(DDie, DU, *UnitId);
       UnitInfo &UI = getUnitInfo(*UnitId);
       // Can't rely on first element in DieVector due to cross CU forward
       // references.
       if (!UI.UnitDie)
         UI.UnitDie = CurDIE;
       if (IsTypeDIE)
-        TypeDIEMap[&DU] = CurDIE;
+        getState().TypeDIEMap[&DU] = CurDIE;
 
       if (!CurParentDIEStack.empty())
         CurParentDIEStack.back()->addChild(CurDIE);
 
       if (AbbrDecl->hasChildren())
         CurParentDIEStack.push_back(CurDIE);
     } else {
       // NULL DIE: finishes current children scope.
       CurParentDIEStack.pop_back();
     }
   } while (CurParentDIEStack.size() > 0);
 
-  CloneUnitCtxMap[*UnitId].Isconstructed = true;
+  getState().CloneUnitCtxMap[*UnitId].Isconstructed = true;
 }
 
-DIEBuilder::DIEBuilder(DWARFContext *DwarfContext, bool IsDWO) {
-  const DWARFUnitIndex &TUIndex = DwarfContext->getTUIndex();
-  if (!TUIndex.getRows().empty()) {
-    for (auto &Row : TUIndex.getRows()) {
-      uint64_t Signature = Row.getSignature();
-      // manually populate TypeUnit to UnitVector
-      DwarfContext->getTypeUnitForHash(DwarfContext->getMaxVersion(), Signature,
-                                       true);
-    }
-  }
+DIEBuilder::DIEBuilder(DWARFContext *DwarfContext, bool IsDWO)
+    : DwarfContext(DwarfContext), IsDWO(IsDWO) {}
 
+static unsigned int getCUNum(DWARFContext *DwarfContext, bool IsDWO) {
   unsigned int CUNum = IsDWO ? DwarfContext->getNumDWOCompileUnits()
                              : DwarfContext->getNumCompileUnits();
   CUNum += IsDWO ? DwarfContext->getNumDWOTypeUnits()
                  : DwarfContext->getNumTypeUnits();
+  return CUNum;
+}
+
+void DIEBuilder::buildTypeUnits(const bool Init) {
+  if (Init)
+    BuilderState.reset(new State());
 
-  CloneUnitCtxMap.resize(CUNum);
+  unsigned int CUNum = getCUNum(DwarfContext, IsDWO);
+  getState().CloneUnitCtxMap.resize(CUNum);
   DWARFContext::unit_iterator_range CU4TURanges =
       IsDWO ? DwarfContext->dwo_types_section_units()
             : DwarfContext->types_section_units();
 
-  for (std::unique_ptr<DWARFUnit> &DU : CU4TURanges) {
-    registerUnit(*DU.get());
-    DWARF4TUVector.push_back(DU.get());
+  const DWARFUnitIndex &TUIndex = DwarfContext->getTUIndex();
+  if (!TUIndex.getRows().empty()) {
+    for (auto &Row : TUIndex.getRows()) {
+      uint64_t Signature = Row.getSignature();
+      // manually populate TypeUnit to UnitVector
+      DwarfContext->getTypeUnitForHash(DwarfContext->getMaxVersion(), Signature,
+                                       true);
     }
+  }
+
+  getState().Type = ProcessingType::DWARF4TYPES;
   for (std::unique_ptr<DWARFUnit> &DU : CU4TURanges)
-    constructFromUnit(*DU.get(), DWARF4TUVector);
+    registerUnit(*DU.get(), false);
+
+  for (std::unique_ptr<DWARFUnit> &DU : CU4TURanges)
+    constructFromUnit(*DU.get());
 
   DWARFContext::unit_iterator_range CURanges =
       IsDWO ? DwarfContext->dwo_info_section_units()
             : DwarfContext->info_section_units();
 
   // This handles DWARF4 CUs and DWARF5 CU/TUs.
   // Creating a vector so that for reference handling only DWARF5 CU/TUs are
   // used, and not DWARF4 TUs.
-  std::vector<DWARFUnit *> DWARF5CUTUVector;
+  getState().Type = ProcessingType::DWARF5TYPES;
+  for (std::unique_ptr<DWARFUnit> &DU : CURanges) {
+    if (!DU->isTypeUnit())
+      continue;
+    registerUnit(*DU.get(), false);
+  }
+
+  for (DWARFUnit *DU : getState().DWARF5TUVector)
+    constructFromUnit(*DU);
+}
+
+void DIEBuilder::buildCompileUnits(const bool Init) {
+  if (Init)
+    BuilderState.reset(new State());
+
+  unsigned int CUNum = getCUNum(DwarfContext, IsDWO);
+  getState().CloneUnitCtxMap.resize(CUNum);
+  DWARFContext::unit_iterator_range CURanges =
+      IsDWO ? DwarfContext->dwo_info_section_units()
+            : DwarfContext->info_section_units();
+
+  // This handles DWARF4 CUs and DWARF5 CU/TUs.
+  // Creating a vector so that for reference handling only DWARF5 CU/TUs are
+  // used, and not DWARF4 TUs.getState().DUList
+  getState().Type = ProcessingType::CUs;
   for (std::unique_ptr<DWARFUnit> &DU : CURanges) {
-    registerUnit(*DU.get());
-    DWARF5CUTUVector.push_back(DU.get());
-  }
+    if (DU->isTypeUnit())
+      continue;
+    registerUnit(*DU.get(), false);
+  }
+
+  // Using DULIst since it can be modified by cross CU refrence resolution.
+  for (DWARFUnit *DU : getState().DUList) {
+    if (DU->isTypeUnit())
+      continue;
+    constructFromUnit(*DU);
+  }
+}
+void DIEBuilder::buildCompileUnits(const std::vector<DWARFUnit *> &CUs) {
+  BuilderState.reset(new State());
+  getState().CloneUnitCtxMap.resize(CUs.size());
+  getState().Type = ProcessingType::CUs;
+  for (DWARFUnit *CU : CUs) {
+    registerUnit(*CU, false);
+  }
+
+  for (DWARFUnit *DU : getState().DUList)
+    constructFromUnit(*DU);
+
+  if (getState().DUList.size() > 1)
+    dbgs() << "Size of CUs being processed: "
+           << Twine::utohexstr(getState().DUList.size()) << '\n';
 
-  for (std::unique_ptr<DWARFUnit> &DU : CURanges)
-    constructFromUnit(*DU.get(), DWARF5CUTUVector);
+void DIEBuilder::buildBoth() {
+  BuilderState.release();
+  BuilderState = std::make_unique<State>();
+  buildTypeUnits(false);
+  buildCompileUnits(false);
 }
 
-DIE *DIEBuilder::constructDIEFast(DWARFDie &DDie, DWARFUnit &U, uint32_t UnitId,
-                                  std::vector<DWARFUnit *> &DUOffsetList) {
+DIE *DIEBuilder::constructDIEFast(DWARFDie &DDie, DWARFUnit &U,
+                                  uint32_t UnitId) {
 
   std::optional<uint32_t> Idx = getAllocDIEId(U, DDie);
   if (Idx) {
     UnitInfo &UnitInfo = getUnitInfo(UnitId);
     DIEInfo &DieInfo = getDIEInfo(UnitId, *Idx);
     if (UnitInfo.Isconstructed && DieInfo.Die)
       return DieInfo.Die;
   } else {
-    Idx = allocDIE(U, DDie, DIEAlloc, UnitId);
+    Idx = allocDIE(U, DDie, getState().DIEAlloc, UnitId);
   }
 
   DIEInfo &DieInfo = getDIEInfo(UnitId, *Idx);
 
   uint64_t Offset = DDie.getOffset();
   uint64_t NextOffset = Offset;
   DWARFDataExtractor Data = U.getDebugInfoExtractor();
   DWARFDebugInfoEntry DDIEntry;
DIE *DIEBuilder::constructDIEFast(DWARFDie &DDie, DWARFUnit &U,
   const DWARFAbbreviationDeclaration *Abbrev =
       DDie.getAbbreviationDeclarationPtr();
   uint64_t AttrOffset = getULEB128Size(Abbrev->getCode());
 
   using AttrSpec = DWARFAbbreviationDeclaration::AttributeSpec;
   for (const AttrSpec &AttrSpec : Abbrev->attributes()) {
     DWARFFormValue Val(AttrSpec.Form);
     Val.extractValue(Data, &AttrOffset, U.getFormParams(), &U);
-    cloneAttribute(*DieInfo.Die, DDie, U, Val, AttrSpec, DUOffsetList);
+    cloneAttribute(*DieInfo.Die, DDie, U, Val, AttrSpec);
   }
   return DieInfo.Die;
 }
 
-static DWARFUnit *getUnitForOffset(const std::vector<DWARFUnit *> &Units,
-                                   const uint64_t Offset) {
-  auto CU =
-      llvm::upper_bound(Units, Offset, [](uint64_t LHS, const DWARFUnit *RHS) {
+static DWARFUnit *
+getUnitForOffset(DIEBuilder &Builder, DWARFContext &DWCtx,
+                 const uint64_t Offset,
+                 const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec) {
+  auto findUnit = [&](std::vector<DWARFUnit *> &Units) -> DWARFUnit * {
+    auto CU = llvm::upper_bound(Units, Offset,
+                                [](uint64_t LHS, const DWARFUnit *RHS) {
                                   return LHS < RHS->getNextUnitOffset();
                                 });
     return CU != Units.end() ? *CU : nullptr;
+  };
+
+  switch (Builder.getCurrentProcessingState()) {
+  case DIEBuilder::ProcessingType::DWARF4TYPES:
+    return findUnit(Builder.getDWARF4TUVector());
+  case DIEBuilder::ProcessingType::DWARF5TYPES:
+    return findUnit(Builder.getDWARF5TUVector());
+  case DIEBuilder::ProcessingType::CUs:
+    return findUnit(Builder.getDWARFCUVector());
+  };
+
+  return nullptr;
 }
 
 uint32_t DIEBuilder::computeDIEOffset(const DWARFUnit &CU, DIE &Die,
                                       uint32_t &CurOffset) {
   uint32_t CurSize = 0;
   Die.setOffset(CurOffset);
   for (DIEValue &Val : Die.values())
     CurSize += Val.sizeOf(CU.getFormParams());
uint32_t DIEBuilder::computeDIEOffset(const DWARFUnit &CU, DIE &Die,
   }
 
   Die.setSize(CurSize);
 
   return CurSize;
 }
 
 void DIEBuilder::finish() {
-  uint64_t UnitStartOffset = 0;
-  auto computeOffset = [&](const DWARFUnit &CU) -> void {
+  auto computeOffset = [&](const DWARFUnit &CU,
+                           uint64_t &UnitStartOffset) -> void {
     DIE *UnitDIE = getUnitDIEbyUnit(CU);
     uint32_t HeaderSize = CU.getHeaderSize();
     uint32_t CurOffset = HeaderSize;
     computeDIEOffset(CU, *UnitDIE, CurOffset);
 
     UnitInfo &CurUnitInfo = getUnitInfoByDwarfUnit(CU);
     CurUnitInfo.UnitOffset = UnitStartOffset;
     CurUnitInfo.UnitLength = HeaderSize + UnitDIE->getSize();
     UnitStartOffset += CurUnitInfo.UnitLength;
   };
-  unsigned Index = 0;
-  unsigned Size = DUList.size();
   // Computing offsets for .debug_types section.
   // It's processed first when CU is registered so will be at the begginnig of
   // the vector.
-  for (; Index < Size; ++Index) {
-    const DWARFUnit &CU = *DUList[Index];
-    if (!(CU.getVersion() < 5 && CU.isTypeUnit()))
+  uint64_t TypeUnitStartOffset = 0;
+  for (const DWARFUnit *CU : getState().DUList) {
+    // We process DWARF$ types first.
+    if (!(CU->getVersion() < 5 && CU->isTypeUnit()))
       break;
-    computeOffset(CU);
+    computeOffset(*CU, TypeUnitStartOffset);
   }
-  UnitStartOffset = 0;
-  for (; Index < Size; ++Index)
-    computeOffset(*DUList[Index]);
 
+  for (const DWARFUnit *CU : getState().DUList) {
+    // Skipping DWARF4 types.
+    if (CU->getVersion() < 5 && CU->isTypeUnit())
+      continue;
+    computeOffset(*CU, UnitSize);
+  }
   computeReference();
 }
 
-DWARFDie
-DIEBuilder::resolveDIEReference(const DWARFFormValue &RefValue,
-                                DWARFUnit *&RefCU,
-                                DWARFDebugInfoEntry &DwarfDebugInfoEntry,
-                                const std::vector<DWARFUnit *> &DUOffsetList) {
+DWARFDie DIEBuilder::resolveDIEReference(
+    const DWARFFormValue &RefValue,
+    const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
+    DWARFUnit *&RefCU, DWARFDebugInfoEntry &DwarfDebugInfoEntry) {
   assert(RefValue.isFormClass(DWARFFormValue::FC_Reference));
   uint64_t RefOffset = *RefValue.getAsReference();
-  return resolveDIEReference(RefOffset, RefCU, DwarfDebugInfoEntry,
-                             DUOffsetList);
+  return resolveDIEReference(AttrSpec, RefOffset, RefCU, DwarfDebugInfoEntry);
 }
 
-DWARFDie
-DIEBuilder::resolveDIEReference(const uint64_t RefOffset, DWARFUnit *&RefCU,
-                                DWARFDebugInfoEntry &DwarfDebugInfoEntry,
-                                const std::vector<DWARFUnit *> &DUOffsetList) {
+DWARFDie DIEBuilder::resolveDIEReference(
+    const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
+    const uint64_t RefOffset, DWARFUnit *&RefCU,
+    DWARFDebugInfoEntry &DwarfDebugInfoEntry) {
   uint64_t TmpRefOffset = RefOffset;
-  if ((RefCU = getUnitForOffset(DUOffsetList, TmpRefOffset))) {
+  if ((RefCU =
+           getUnitForOffset(*this, *DwarfContext, TmpRefOffset, AttrSpec))) {
+    /// Trying to add to current working set in case it's cross CU reference.
+    registerUnit(*RefCU, true);
     DWARFDataExtractor DebugInfoData = RefCU->getDebugInfoExtractor();
     if (DwarfDebugInfoEntry.extractFast(*RefCU, &TmpRefOffset, DebugInfoData,
                                         RefCU->getNextUnitOffset(), 0)) {
       // In a file with broken references, an attribute might point to a NULL
       // DIE.
       DWARFDie RefDie = DWARFDie(RefCU, &DwarfDebugInfoEntry);
       if (!RefDie.isNULL()) {
         std::optional<uint32_t> UnitId = getUnitId(*RefCU);
 
         // forward reference
-        if (UnitId && !CloneUnitCtxMap[*UnitId].Isconstructed &&
+        if (UnitId && !getState().CloneUnitCtxMap[*UnitId].Isconstructed &&
             !getAllocDIEId(*RefCU, RefDie))
-          allocDIE(*RefCU, RefDie, DIEAlloc, *UnitId);
+          allocDIE(*RefCU, RefDie, getState().DIEAlloc, *UnitId);
         return RefDie;
       }
     }
   }
 
   errs() << "BOLT-WARNING: [internal-dwarf-error]: could not find referenced "
             "CU.\n";
   return DWARFDie();
 }
 
 void DIEBuilder::cloneDieReferenceAttribute(
     DIE &Die, const DWARFUnit &U, const DWARFDie &InputDIE,
     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
-    const DWARFFormValue &Val, const std::vector<DWARFUnit *> &DUOffsetList) {
+    const DWARFFormValue &Val) {
   const uint64_t Ref = *Val.getAsReference();
 
   DIE *NewRefDie = nullptr;
   DWARFUnit *RefUnit = nullptr;
 
   DWARFDebugInfoEntry DDIEntry;
-  const DWARFDie RefDie =
-      resolveDIEReference(Val, RefUnit, DDIEntry, DUOffsetList);
+  const DWARFDie RefDie = resolveDIEReference(Val, AttrSpec, RefUnit, DDIEntry);
 
   if (!RefDie)
     return;
 
   const std::optional<uint32_t> UnitId = getUnitId(*RefUnit);
   const std::optional<uint32_t> IsAllocId = getAllocDIEId(*RefUnit, RefDie);
   assert(IsAllocId.has_value() && "Encountered unexpected unallocated DIE.");
   const uint32_t DIEId = *IsAllocId;
   DIEInfo &DieInfo = getDIEInfo(*UnitId, DIEId);
 
   if (!DieInfo.Die) {
     assert(Ref > InputDIE.getOffset());
     errs() << "BOLT-WARNING: [internal-dwarf-error]: encounter unexpected "
               "unallocated DIE. Should be alloc!\n";
     // We haven't cloned this DIE yet. Just create an empty one and
     // store it. It'll get really cloned when we process it.
-    DieInfo.Die = DIE::get(DIEAlloc, dwarf::Tag(RefDie.getTag()));
+    DieInfo.Die = DIE::get(getState().DIEAlloc, dwarf::Tag(RefDie.getTag()));
   }
   NewRefDie = DieInfo.Die;
 
   if (AttrSpec.Form == dwarf::DW_FORM_ref_addr) {
     // no matter forward reference or backward reference, we are supposed
     // to calculate them in `finish` due to the possible modification of
     // the DIE.
     DWARFDie CurDie = const_cast<DWARFDie &>(InputDIE);
     DIEInfo *CurDieInfo = &getDIEInfoByDwarfDie(CurDie);
-    ForwardReferences.push_back(
+    getState().ForwardReferences.push_back(
         std::make_pair(CurDieInfo, ForwardReferenceInfo(&DieInfo, AttrSpec)));
 
-    Die.addValue(DIEAlloc, AttrSpec.Attr, dwarf::DW_FORM_ref_addr,
+    Die.addValue(getState().DIEAlloc, AttrSpec.Attr, dwarf::DW_FORM_ref_addr,
                  DIEInteger(0xDEADBEEF));
     return;
   }
 
-  Die.addValue(DIEAlloc, AttrSpec.Attr, AttrSpec.Form, DIEEntry(*NewRefDie));
+  Die.addValue(getState().DIEAlloc, AttrSpec.Attr, AttrSpec.Form,
+               DIEEntry(*NewRefDie));
 }
 
 void DIEBuilder::cloneStringAttribute(
     DIE &Die, const DWARFUnit &U,
     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
     const DWARFFormValue &Val) {
   if (AttrSpec.Form == dwarf::DW_FORM_string) {
     Expected<const char *> StrAddr = Val.getAsCString();
     if (!StrAddr) {
       consumeError(StrAddr.takeError());
       return;
     }
-    Die.addValue(DIEAlloc, AttrSpec.Attr, dwarf::DW_FORM_string,
-                 new (DIEAlloc) DIEInlineString(StrAddr.get(), DIEAlloc));
+    Die.addValue(getState().DIEAlloc, AttrSpec.Attr, dwarf::DW_FORM_string,
+                 new (getState().DIEAlloc)
+                     DIEInlineString(StrAddr.get(), getState().DIEAlloc));
   } else {
     std::optional<uint64_t> OffsetIndex = Val.getRawUValue();
-    Die.addValue(DIEAlloc, AttrSpec.Attr, AttrSpec.Form,
+    Die.addValue(getState().DIEAlloc, AttrSpec.Attr, AttrSpec.Form,
                  DIEInteger(*OffsetIndex));
   }
 }
 
 bool DIEBuilder::cloneExpression(const DataExtractor &Data,
                                  const DWARFExpression &Expression,
                                  DWARFUnit &U,
                                  SmallVectorImpl<uint8_t> &OutputBuffer,
void DIEBuilder::cloneBlockAttribute(
     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
     const DWARFFormValue &Val) {
   DIEValueList *Attr;
   DIEValue Value;
   DIELoc *Loc = nullptr;
   DIEBlock *Block = nullptr;
 
   if (AttrSpec.Form == dwarf::DW_FORM_exprloc) {
-    Loc = new (DIEAlloc) DIELoc;
+    Loc = new (getState().DIEAlloc) DIELoc;
   } else if (doesFormBelongToClass(AttrSpec.Form, DWARFFormValue::FC_Block,
                                    U.getVersion())) {
-    Block = new (DIEAlloc) DIEBlock;
+    Block = new (getState().DIEAlloc) DIEBlock;
   } else {
     errs() << "BOLT-WARNING: [internal-dwarf-error]: Unexpected Form value in "
               "cloneBlockAttribute\n";
     return;
   }
   Attr = Loc ? static_cast<DIEValueList *>(Loc)
              : static_cast<DIEValueList *>(Block);
 
   SmallVector<uint8_t, 32> Buffer;
   ArrayRef<uint8_t> Bytes = *Val.getAsBlock();
   if (DWARFAttribute::mayHaveLocationExpr(AttrSpec.Attr) &&
       (Val.isFormClass(DWARFFormValue::FC_Block) ||
        Val.isFormClass(DWARFFormValue::FC_Exprloc))) {
     DataExtractor Data(StringRef((const char *)Bytes.data(), Bytes.size()),
                        U.isLittleEndian(), U.getAddressByteSize());
     DWARFExpression Expr(Data, U.getAddressByteSize(),
                          U.getFormParams().Format);
     if (cloneExpression(Data, Expr, U, Buffer, CloneExpressionStage::INIT))
-      LocWithReferencesToProcess.emplace_back(Bytes.vec(), U, Die,
-                                              AttrSpec.Form, AttrSpec.Attr);
+      getState().LocWithReferencesToProcess.emplace_back(
+          Bytes.vec(), U, Die, AttrSpec.Form, AttrSpec.Attr);
     Bytes = Buffer;
   }
   for (auto Byte : Bytes)
-    Attr->addValue(DIEAlloc, static_cast<dwarf::Attribute>(0),
+    Attr->addValue(getState().DIEAlloc, static_cast<dwarf::Attribute>(0),
                    dwarf::DW_FORM_data1, DIEInteger(Byte));
 
   if (Loc)
     Loc->setSize(Bytes.size());
   else
     Block->setSize(Bytes.size());
 
   if (Loc)
     Value = DIEValue(dwarf::Attribute(AttrSpec.Attr),
                      dwarf::Form(AttrSpec.Form), Loc);
   else
     Value = DIEValue(dwarf::Attribute(AttrSpec.Attr),
                      dwarf::Form(AttrSpec.Form), Block);
-  Die.addValue(DIEAlloc, Value);
+  Die.addValue(getState().DIEAlloc, Value);
 }
 
 void DIEBuilder::cloneAddressAttribute(
     DIE &Die, const DWARFUnit &U,
     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
     const DWARFFormValue &Val) {
-  Die.addValue(DIEAlloc, AttrSpec.Attr, AttrSpec.Form,
+  Die.addValue(getState().DIEAlloc, AttrSpec.Attr, AttrSpec.Form,
                DIEInteger(Val.getRawUValue()));
 }
 
 void DIEBuilder::cloneRefsigAttribute(
     DIE &Die, DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
     const DWARFFormValue &Val) {
   const std::optional<uint64_t> SigVal = Val.getRawUValue();
-  Die.addValue(DIEAlloc, AttrSpec.Attr, dwarf::DW_FORM_ref_sig8,
+  Die.addValue(getState().DIEAlloc, AttrSpec.Attr, dwarf::DW_FORM_ref_sig8,
                DIEInteger(*SigVal));
 }
 
 void DIEBuilder::cloneScalarAttribute(
     DIE &Die, const DWARFDie &InputDIE,
     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
     const DWARFFormValue &Val) {
   uint64_t Value;
 
   if (auto OptionalValue = Val.getAsUnsignedConstant())
     Value = *OptionalValue;
   else if (auto OptionalValue = Val.getAsSignedConstant())
     Value = *OptionalValue;
   else if (auto OptionalValue = Val.getAsSectionOffset())
     Value = *OptionalValue;
   else {
     errs() << "BOLT-WARNING: [internal-dwarf-error]: Unsupported scalar "
               "attribute form. Dropping "
               "attribute.\n";
     return;
   }
 
-  Die.addValue(DIEAlloc, AttrSpec.Attr, AttrSpec.Form, DIEInteger(Value));
+  Die.addValue(getState().DIEAlloc, AttrSpec.Attr, AttrSpec.Form,
+               DIEInteger(Value));
 }
 
 void DIEBuilder::cloneLoclistAttrubute(
     DIE &Die, const DWARFDie &InputDIE,
     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
     const DWARFFormValue &Val) {
   uint64_t Value;
 
   if (auto OptionalValue = Val.getAsUnsignedConstant())
     Value = *OptionalValue;
   else if (auto OptionalValue = Val.getAsSignedConstant())
     Value = *OptionalValue;
   else if (auto OptionalValue = Val.getAsSectionOffset())
     Value = *OptionalValue;
   else {
     errs() << "BOLT-WARNING: [internal-dwarf-error]: Unsupported scalar "
               "attribute form. Dropping "
               "attribute.\n";
     return;
   }
 
-  Die.addValue(DIEAlloc, AttrSpec.Attr, AttrSpec.Form, DIELocList(Value));
+  Die.addValue(getState().DIEAlloc, AttrSpec.Attr, AttrSpec.Form,
+               DIELocList(Value));
 }
 
 void DIEBuilder::cloneAttribute(
     DIE &Die, const DWARFDie &InputDIE, DWARFUnit &U, const DWARFFormValue &Val,
-    const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
-    const std::vector<DWARFUnit *> &DUOffsetList) {
+    const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec) {
   switch (AttrSpec.Form) {
   case dwarf::DW_FORM_strp:
   case dwarf::DW_FORM_string:
   case dwarf::DW_FORM_strx:
   case dwarf::DW_FORM_strx1:
   case dwarf::DW_FORM_strx2:
   case dwarf::DW_FORM_strx3:
   case dwarf::DW_FORM_strx4:
   case dwarf::DW_FORM_GNU_str_index:
   case dwarf::DW_FORM_line_strp:
     cloneStringAttribute(Die, U, AttrSpec, Val);
     break;
   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:
-    cloneDieReferenceAttribute(Die, U, InputDIE, AttrSpec, Val, DUOffsetList);
+    cloneDieReferenceAttribute(Die, U, InputDIE, AttrSpec, Val);
     break;
   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:
     cloneBlockAttribute(Die, U, AttrSpec, Val);
     break;
if (InSet) {
     Abbreviations.back()->setNumber(Abbreviations.size());
   }
 }
 
 void DIEBuilder::generateAbbrevs() {
   if (isEmpty())
     return;
 
-  for (DWARFUnit *DU : DUList) {
+  for (DWARFUnit *DU : getState().DUList) {
     DIE *UnitDIE = getUnitDIEbyUnit(*DU);
     generateUnitAbbrevs(UnitDIE);
   }
 }
 
 void DIEBuilder::generateUnitAbbrevs(DIE *Die) {
   DIEAbbrev NewAbbrev = Die->generateAbbrev();
 
if (DU.getVersion() < 5 && DU.isTypeUnit()) {
     uint64_t Offset = DU.getOffset();
     Hash.update(llvm::ArrayRef((uint8_t *)&TypeUnitHash, sizeof(TypeUnitHash)));
     Hash.update(llvm::ArrayRef((uint8_t *)&Offset, sizeof(Offset)));
     return Hash.final().high();
   }
   return DU.getOffset();
 }
 
-void DIEBuilder::registerUnit(DWARFUnit &DU) {
-  UnitIDMap[getHash(DU)] = DUList.size();
-  DUList.push_back(&DU);
+void DIEBuilder::registerUnit(DWARFUnit &DU, bool NeedSort) {
+  auto IterGlobal = AllProcessed.insert(getHash(DU));
+  // If DU is already in a current working set or was already processed we can
+  // skip it.
+  if (!IterGlobal.second)
+    return;
+  if (getState().Type == ProcessingType::DWARF4TYPES)
+    getState().DWARF4TUVector.push_back(&DU);
+  else if (getState().Type == ProcessingType::DWARF5TYPES)
+    getState().DWARF5TUVector.push_back(&DU);
+  else {
+    getState().DWARFCUVector.push_back(&DU);
+    /// Sorting for cross CU reference resolution.
+    if (NeedSort)
+      std::sort(getState().DWARFCUVector.begin(),
+                getState().DWARFCUVector.end(),
+                [](const DWARFUnit *A, const DWARFUnit *B) {
+                  return A->getOffset() < B->getOffset();
+                });
+  }
+  getState().UnitIDMap[getHash(DU)] = getState().DUList.size();
+  getState().DUList.push_back(&DU);
 }
 
 std::optional<uint32_t> DIEBuilder::getUnitId(const DWARFUnit &DU) {
-  auto Iter = UnitIDMap.find(getHash(DU));
-  if (Iter != UnitIDMap.end())
+  auto Iter = getState().UnitIDMap.find(getHash(DU));
+  if (Iter != getState().UnitIDMap.end())
     return Iter->second;
   return std::nullopt;
 }
 
 } // namespace bolt
 } // namespace llvm

bolt/lib/Core/DebugData.cpp

 #include "llvm/Support/EndianStream.h"
 #include "llvm/Support/LEB128.h"
 #include "llvm/Support/SHA1.h"
 #include <algorithm>
 #include <cassert>
 #include <cstdint>
 #include <functional>
 #include <limits>
+#include <memory>
 #include <unordered_map>
 #include <vector>
 
 #define DEBUG_TYPE "bolt-debug-info"
 
 namespace opts {
 extern llvm::cl::opt<unsigned> Verbosity;
 } // namespace opts
for (const auto &CUOffsetAddressRangesPair : CUAddressRanges) {
     // Padding before address table - 4 bytes in the 64-bit-pointer case.
     support::endian::write(RangesStream, static_cast<uint32_t>(0),
                            support::little);
 
     writeAddressRanges(RangesStream, AddressRanges, true);
   }
 }
 
-DebugAddrWriter::DebugAddrWriter(BinaryContext *Bc) { BC = Bc; }
+DebugAddrWriter::DebugAddrWriter(BinaryContext *BC) : BC(BC) {
+  Buffer = std::make_unique<AddressSectionBuffer>();
+  AddressStream = std::make_unique<raw_svector_ostream>(*Buffer);
+}
 
 void DebugAddrWriter::AddressForDWOCU::dump() {
   std::vector<IndexAddressPair> SortedMap(indexToAddressBegin(),
                                           indexToAdddessEnd());
   // Sorting address in increasing order of indices.
   llvm::sort(SortedMap, llvm::less_first());
   for (auto &Pair : SortedMap)
     dbgs() << Twine::utohexstr(Pair.second) << "\t" << Pair.first << "\n";
if (Entry != Map.end()) {
     if (Entry->second > Index)
       Map.updateAddressToIndex(Address, Index);
     Map.updateIndexToAddrss(Address, Index);
   } else {
     Map.insert(Address, Index);
   }
 }
 
-AddressSectionBuffer DebugAddrWriter::finalize() {
-  // Need to layout all sections within .debug_addr
-  // Within each section sort Address by index.
-  AddressSectionBuffer Buffer;
-  raw_svector_ostream AddressStream(Buffer);
-  for (std::unique_ptr<DWARFUnit> &CU : BC->DwCtx->compile_units()) {
-    // Handling the case wehre debug information is a mix of Debug fission and
-    // monolitic.
-    if (!CU->getDWOId())
-      continue;
-    const uint64_t CUID = getCUID(*CU.get());
-    auto AM = AddressMaps.find(CUID);
-    // Adding to map even if it did not contribute to .debug_addr.
-    // The Skeleton CU might still have DW_AT_GNU_addr_base.
-    DWOIdToOffsetMap[CUID] = Buffer.size();
-    // If does not exist this CUs DWO section didn't contribute to .debug_addr.
-    if (AM == AddressMaps.end())
-      continue;
-    std::vector<IndexAddressPair> SortedMap(AM->second.indexToAddressBegin(),
-                                            AM->second.indexToAdddessEnd());
-    // Sorting address in increasing order of indices.
-    llvm::sort(SortedMap, llvm::less_first());
+static void updateAddressBase(DIEBuilder &DIEBlder, DebugAddrWriter &AddrWriter,
+                              DWARFUnit &CU, const uint64_t Offset) {
+  DIE *Die = DIEBlder.getUnitDIEbyUnit(CU);
+  DIEValue GnuAddrBaseAttrInfo = Die->findAttribute(dwarf::DW_AT_GNU_addr_base);
+  DIEValue AddrBaseAttrInfo = Die->findAttribute(dwarf::DW_AT_addr_base);
+  dwarf::Form BaseAttrForm;
+  dwarf::Attribute BaseAttr;
+  // For cases where Skeleton CU does not have DW_AT_GNU_addr_base
+  if (!GnuAddrBaseAttrInfo && CU.getVersion() < 5)
+    return;
+
+  if (GnuAddrBaseAttrInfo) {
+    BaseAttrForm = GnuAddrBaseAttrInfo.getForm();
+    BaseAttr = GnuAddrBaseAttrInfo.getAttribute();
+  }
+
+  if (AddrBaseAttrInfo) {
+    BaseAttrForm = AddrBaseAttrInfo.getForm();
+    BaseAttr = AddrBaseAttrInfo.getAttribute();
+  }
+
+  if (GnuAddrBaseAttrInfo || AddrBaseAttrInfo) {
+    DIEBlder.replaceValue(Die, BaseAttr, BaseAttrForm, DIEInteger(Offset));
+  } else if (CU.getVersion() >= 5) {
+    // A case where we were not using .debug_addr section, but after update
+    // now using it.
+    DIEBlder.addValue(Die, dwarf::DW_AT_addr_base, dwarf::DW_FORM_sec_offset,
+                      DIEInteger(Offset));
+  }
+}
+
+void DebugAddrWriter::update(DIEBuilder &DIEBlder, DWARFUnit &CU) {
+  if (!CU.getDWOId())
+    return;
+  const uint64_t CUID = getCUID(CU);
+  uint64_t Offset = Buffer->size();
+    return;
 
-    uint8_t AddrSize = CU->getAddressByteSize();
-    uint32_t Counter = 0;
-    auto WriteAddress = [&](uint64_t Address) -> void {
-      ++Counter;
-      switch (AddrSize) {
-      default:
-        assert(false && "Address Size is invalid.");
-        break;
-      case 4:
-        support::endian::write(AddressStream, static_cast<uint32_t>(Address),
-                               support::little);
-        break;
-      case 8:
-        support::endian::write(AddressStream, Address, support::little);
-        break;
-      }
-    };
+  uint8_t AddrSize = CU.getAddressByteSize();
+      support::endian::write(*AddressStream, static_cast<uint32_t>(Address),
+      support::endian::write(*AddressStream, Address, support::little);
 
-    for (const IndexAddressPair &Val : SortedMap) {
-      while (Val.first > Counter)
-        WriteAddress(0);
-      WriteAddress(Val.second);
-    }
-  }
+  updateAddressBase(DIEBlder, *this, CU, Offset);
 
-  return Buffer;
-}
-AddressSectionBuffer DebugAddrWriterDwarf5::finalize() {
+void DebugAddrWriterDwarf5::update(DIEBuilder &DIEBlder, DWARFUnit &CU) {
   // Need to layout all sections within .debug_addr
   // Within each section sort Address by index.
-  AddressSectionBuffer Buffer;
-  raw_svector_ostream AddressStream(Buffer);
   const endianness Endian =
       BC->DwCtx->isLittleEndian() ? support::little : support::big;
   const DWARFSection &AddrSec = BC->DwCtx->getDWARFObj().getAddrSection();
   DWARFDataExtractor AddrData(BC->DwCtx->getDWARFObj(), AddrSec, Endian, 0);
   DWARFDebugAddrTable AddrTable;
   DIDumpOptions DumpOpts;
   constexpr uint32_t HeaderSize = 8;
-  DenseMap<uint64_t, uint64_t> UnmodifiedAddressOffsets;
-  for (std::unique_ptr<DWARFUnit> &CU : BC->DwCtx->compile_units()) {
-    const uint64_t CUID = getCUID(*CU.get());
-    const uint8_t AddrSize = CU->getAddressByteSize();
-    auto AMIter = AddressMaps.find(CUID);
-    // A case where CU has entry in .debug_addr, but we don't modify addresses
-    // for it.
-    if (AMIter == AddressMaps.end()) {
-      AMIter = AddressMaps.insert({CUID, AddressForDWOCU()}).first;
-      std::optional<uint64_t> BaseOffset = CU->getAddrOffsetSectionBase();
-      if (!BaseOffset)
-        continue;
-      // Address base offset is to the first entry.
-      // The size of header is 8 bytes.
-      uint64_t Offset = *BaseOffset - HeaderSize;
-      auto Iter = UnmodifiedAddressOffsets.find(Offset);
-      if (Iter != UnmodifiedAddressOffsets.end()) {
-        DWOIdToOffsetMap[CUID] = Iter->getSecond();
-        continue;
-      }
-      UnmodifiedAddressOffsets[Offset] = Buffer.size() + HeaderSize;
-      if (Error Err = AddrTable.extract(AddrData, &Offset, 5, AddrSize,
-                                        DumpOpts.WarningHandler)) {
-        DumpOpts.RecoverableErrorHandler(std::move(Err));
-        continue;
-      }
+  const uint64_t CUID = getCUID(CU);
+  const uint8_t AddrSize = CU.getAddressByteSize();
+    std::optional<uint64_t> BaseOffset = CU.getAddrOffsetSectionBase();
+      return;
+      updateAddressBase(DIEBlder, *this, CU, Iter->getSecond());
+      return;
+    UnmodifiedAddressOffsets[Offset] = Buffer->size() + HeaderSize;
+      return;
 
-      uint32_t Index = 0;
-      for (uint64_t Addr : AddrTable.getAddressEntries())
-        AMIter->second.insert(Addr, Index++);
-    }
 
-    DWOIdToOffsetMap[CUID] = Buffer.size() + HeaderSize;
+  updateAddressBase(DIEBlder, *this, CU, Buffer->size() + HeaderSize);
 
-    std::vector<IndexAddressPair> SortedMap(
-        AMIter->second.indexToAddressBegin(),
+  std::vector<IndexAddressPair> SortedMap(AMIter->second.indexToAddressBegin(),
                                           AMIter->second.indexToAdddessEnd());
-    // Sorting address in increasing order of indices.
-    llvm::sort(SortedMap, llvm::less_first());
-    // Writing out Header
-    const uint32_t Length = SortedMap.size() * AddrSize + 4;
-    support::endian::write(AddressStream, Length, Endian);
-    support::endian::write(AddressStream, static_cast<uint16_t>(5), Endian);
-    support::endian::write(AddressStream, static_cast<uint8_t>(AddrSize),
-                           Endian);
-    support::endian::write(AddressStream, static_cast<uint8_t>(0), Endian);
+  support::endian::write(*AddressStream, Length, Endian);
+  support::endian::write(*AddressStream, static_cast<uint16_t>(5), Endian);
+  support::endian::write(*AddressStream, static_cast<uint8_t>(AddrSize),
+  support::endian::write(*AddressStream, static_cast<uint8_t>(0), Endian);
 
-    uint32_t Counter = 0;
-    auto writeAddress = [&](uint64_t Address) -> void {
-      ++Counter;
-      switch (AddrSize) {
-      default:
-        llvm_unreachable("Address Size is invalid.");
-        break;
-      case 4:
-        support::endian::write(AddressStream, static_cast<uint32_t>(Address),
-                               Endian);
-        break;
-      case 8:
-        support::endian::write(AddressStream, Address, Endian);
-        break;
-      }
-    };
+      support::endian::write(*AddressStream, static_cast<uint32_t>(Address),
+      support::endian::write(*AddressStream, Address, Endian);
 
-    for (const IndexAddressPair &Val : SortedMap) {
-      while (Val.first > Counter)
-        writeAddress(0);
-      writeAddress(Val.second);
-    }
-  }
 
-  return Buffer;
-}
-
-uint64_t DebugAddrWriter::getOffset(DWARFUnit &Unit) {
-  const uint64_t CUID = getCUID(Unit);
-  assert(CUID && "Can't get offset, not a skeleton CU.");
-  auto Iter = DWOIdToOffsetMap.find(CUID);
-  assert(Iter != DWOIdToOffsetMap.end() &&
-         "Offset in to.debug_addr was not found for DWO ID.");
-  return Iter->second;
-}
-
-uint64_t DebugAddrWriterDwarf5::getOffset(DWARFUnit &Unit) {
-  auto Iter = DWOIdToOffsetMap.find(getCUID(Unit));
-  assert(Iter != DWOIdToOffsetMap.end() &&
-         "Offset in to.debug_addr was not found for CU ID.");
-  return Iter->second;
-}
-
 void DebugLocWriter::init() {
   LocBuffer = std::make_unique<DebugBufferVector>();
   LocStream = std::make_unique<raw_svector_ostream>(*LocBuffer);
   // Writing out empty location list to which all references to empty location
   // lists will point.
   if (!LocSectionOffset && DwarfVersion < 5) {
     const char Zeroes[16] = {0};
     *LocStream << StringRef(Zeroes, 16);

 }
 
 void DebugStrOffsetsWriter::updateAddressMap(uint32_t Index, uint32_t Address) {
   assert(IndexToAddressMap.count(Index) > 0 && "Index is not found.");
   IndexToAddressMap[Index] = Address;
   StrOffsetSectionWasModified = true;
 }
 
-void DebugStrOffsetsWriter::finalizeSection(DWARFUnit &Unit) {
+void DebugStrOffsetsWriter::finalizeSection(DWARFUnit &Unit,
+                                            DIEBuilder &DIEBldr) {
   if (IndexToAddressMap.empty())
     return;
 
   std::optional<AttrInfo> AttrVal =
       findAttributeInfo(Unit.getUnitDIE(), dwarf::DW_AT_str_offsets_base);
   assert(AttrVal && "DW_AT_str_offsets_base not present.");
   std::optional<uint64_t> Val = AttrVal->V.getAsSectionOffset();
   assert(Val && "DW_AT_str_offsets_base Value not present.");
-  auto RetVal = ProcessedBaseOffsets.insert(*Val);
-  if (RetVal.second) {
+  DIE &Die = *DIEBldr.getUnitDIEbyUnit(Unit);
+  DIEValue StrListBaseAttrInfo =
+      Die.findAttribute(dwarf::DW_AT_str_offsets_base);
+  auto RetVal = ProcessedBaseOffsets.find(*Val);
+  // Handling re-use of str-offsets section.
+  if (RetVal == ProcessedBaseOffsets.end() || StrOffsetSectionWasModified) {
     // Writing out the header for each section.
     support::endian::write(*StrOffsetsStream, CurrentSectionSize + 4,
                            support::little);
     support::endian::write(*StrOffsetsStream, static_cast<uint16_t>(5),
                            support::little);
     support::endian::write(*StrOffsetsStream, static_cast<uint16_t>(0),
                            support::little);
+
+    uint64_t BaseOffset = StrOffsetsBuffer->size();
+    ProcessedBaseOffsets[*Val] = BaseOffset;
+    if (StrListBaseAttrInfo.getType())
+      DIEBldr.replaceValue(&Die, dwarf::DW_AT_str_offsets_base,
+                           StrListBaseAttrInfo.getForm(),
+                           DIEInteger(BaseOffset));
     for (const auto &Entry : IndexToAddressMap)
       support::endian::write(*StrOffsetsStream, Entry.second, support::little);
+  } else {
+    DIEBldr.replaceValue(&Die, dwarf::DW_AT_str_offsets_base,
+                         StrListBaseAttrInfo.getForm(),
+                         DIEInteger(RetVal->second));
   }
-  // Will print error if we already processed this contribution, and now
-  // skipping it, but it was modified.
-  if (!RetVal.second && StrOffsetSectionWasModified)
-    errs() << "BOLT-WARNING: skipping string offsets section for CU at offset "
-           << Twine::utohexstr(Unit.getOffset()) << ", but it was modified\n";
 
   StrOffsetSectionWasModified = false;
   IndexToAddressMap.clear();
 }
 
 void DebugStrWriter::create() {
   StrBuffer = std::make_unique<DebugStrBufferVector>();
   StrStream = std::make_unique<raw_svector_ostream>(*StrBuffer);

bolt/lib/Rewrite/DWARFRewriter.cpp

 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/BinaryFormat/Dwarf.h"
 #include "llvm/CodeGen/AsmPrinter.h"
 #include "llvm/CodeGen/DIE.h"
 #include "llvm/DWARFLinker/DWARFStreamer.h"
 #include "llvm/DebugInfo/DWARF/DWARFContext.h"
+#include "llvm/DebugInfo/DWARF/DWARFDebugAbbrev.h"
 #include "llvm/DebugInfo/DWARF/DWARFDebugLoc.h"
 #include "llvm/DebugInfo/DWARF/DWARFExpression.h"
 #include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
 #include "llvm/DebugInfo/DWARF/DWARFTypeUnit.h"
 #include "llvm/DebugInfo/DWARF/DWARFUnit.h"
 #include "llvm/MC/MCAsmBackend.h"
 #include "llvm/MC/MCAsmLayout.h"
 #include "llvm/MC/MCObjectWriter.h"
WriteDWP("write-dwp",
              cl::init(false), cl::cat(BoltCategory));
 
 static cl::opt<bool>
     DebugSkeletonCu("debug-skeleton-cu",
                     cl::desc("prints out offsetrs for abbrev and debu_info of "
                              "Skeleton CUs that get patched."),
                     cl::ZeroOrMore, cl::Hidden, cl::init(false),
                     cl::cat(BoltCategory));
+
+static cl::opt<unsigned> BatchSize(
+    "cu-processing-batch-size",
+    cl::desc(
+        "Specifies the size of batches for processing CUs. Higher number has "
+        "better performance, but more memory usage. Default value is 1."),
+    cl::ZeroOrMore, cl::Hidden, cl::init(1), cl::cat(BoltCategory));
 } // namespace opts
 
 static bool getLowAndHighPC(const DIE &Die, const DWARFUnit &DU,
                             uint64_t &LowPC, uint64_t &HighPC,
                             uint64_t &SectionIndex) {
   DIEValue DvalLowPc = Die.findAttribute(dwarf::DW_AT_low_pc);
   DIEValue DvalHighPc = Die.findAttribute(dwarf::DW_AT_high_pc);
   if (!DvalLowPc || !DvalHighPc)
std::unique_ptr<DIEStreamer> Streamer = std::make_unique<DIEStreamer>(
       &DIEBldr, Rewriter, OutputFileType::Object, OutFile,
       [](StringRef Input) -> StringRef { return Input; },
       [&](const Twine &Error, StringRef Context, const DWARFDie *) {},
       [&](const Twine &Warning, StringRef Context, const DWARFDie *) {});
   Streamer->init(TheTriple, Swift5ReflectionSegmentName);
   return Streamer;
 }
 
-static DWARFRewriter::UnitMeta emitUnit(DIEBuilder &DIEBldr,
-                                        std::unique_ptr<DIEStreamer> &Streamer,
-                                        DWARFUnit &Unit) {
+static DWARFRewriter::UnitMeta
+emitUnit(DIEBuilder &DIEBldr, DIEStreamer &Streamer, DWARFUnit &Unit) {
   DIE *UnitDIE = DIEBldr.getUnitDIEbyUnit(Unit);
   const DIEBuilder::UnitInfo &U = DIEBldr.getUnitInfoByDwarfUnit(Unit);
-  Streamer->emitUnit(Unit, *UnitDIE);
+  Streamer.emitUnit(Unit, *UnitDIE);
   uint64_t TypeHash = 0;
   if (DWARFTypeUnit *DTU = dyn_cast_or_null<DWARFTypeUnit>(&Unit))
     TypeHash = DTU->getTypeHash();
   return {U.UnitOffset, U.UnitLength, TypeHash};
 }
 
 static void emitDWOBuilder(const std::string &DWOName, DIEBuilder &DwoDIEBlder,
                            DWARFRewriter &Rewriter, const DWARFUnit &SplitCU,
std::unique_ptr<DIEStreamer> Streamer = createDIEStreamer(
       *TheTriple, *ObjOS, "DwoStreamerInitAug2", DwoDIEBlder, Rewriter);
   DWARFRewriter::UnitMetaVectorType TUMetaVector;
   DWARFRewriter::UnitMeta CUMI = {0, 0, 0};
   if (SplitCU.getContext().getMaxDWOVersion() >= 5) {
     // TODO: Handle DWP as input. Right now it will iterate over all of CUs and
     // TUs
     for (std::unique_ptr<llvm::DWARFUnit> &CU :
          SplitCU.getContext().dwo_info_section_units()) {
-      DWARFRewriter::UnitMeta MI = emitUnit(DwoDIEBlder, Streamer, *CU.get());
+      DWARFRewriter::UnitMeta MI = emitUnit(DwoDIEBlder, *Streamer, *CU.get());
       if (CU->isTypeUnit())
         TUMetaVector.emplace_back(MI);
       else
         CUMI = MI;
     }
   } else {
     for (std::unique_ptr<llvm::DWARFUnit> &CU :
          SplitCU.getContext().dwo_compile_units())
-      emitUnit(DwoDIEBlder, Streamer, *CU.get());
+      emitUnit(DwoDIEBlder, *Streamer, *CU.get());
 
     // emit debug_types sections for dwarf4
     for (DWARFUnit *CU : DwoDIEBlder.getDWARF4TUVector()) {
-      DWARFRewriter::UnitMeta MI = emitUnit(DwoDIEBlder, Streamer, *CU);
+      DWARFRewriter::UnitMeta MI = emitUnit(DwoDIEBlder, *Streamer, *CU);
       TUMetaVector.emplace_back(MI);
     }
   }
 
   Streamer->emitAbbrevs(DwoDIEBlder.getAbbrevs(),
                         SplitCU.getContext().getMaxVersion());
   Streamer->finish();
 
if (Unit.getVersion() == 5) {
     StrOffstsWriter->updateAddressMap(DIEAttrInfo.getDIEInteger().getValue(),
                                       NewOffset);
     return;
   }
   DIEBldr.replaceValue(&Die, DIEAttrInfo.getAttribute(), DIEAttrInfo.getForm(),
                        DIEInteger(NewOffset));
 }
 
+using DWARFUnitVec = std::vector<DWARFUnit *>;
+using CUPartitionVector = std::vector<DWARFUnitVec>;
+static CUPartitionVector partitionCUs(DWARFContext &DwCtx) {
+  CUPartitionVector Vec(2);
+  unsigned Counter = 0;
+  const DWARFDebugAbbrev *Abbr = DwCtx.getDebugAbbrev();
+  for (std::unique_ptr<DWARFUnit> &CU : DwCtx.compile_units()) {
+    const DWARFAbbreviationDeclarationSet *AbbrDeclSet =
+        Abbr->getAbbreviationDeclarationSet(CU->getAbbreviationsOffset());
+    bool CrossCURefFound = false;
+    for (const DWARFAbbreviationDeclaration &Decl : *AbbrDeclSet) {
+      for (const DWARFAbbreviationDeclaration::AttributeSpec &Attr :
+           Decl.attributes()) {
+        if (Attr.Form == dwarf::DW_FORM_ref_addr) {
+          CrossCURefFound = true;
+          break;
+        }
+      }
+      if (CrossCURefFound)
+        break;
+    }
+    if (CrossCURefFound)
+      Vec[0].push_back(CU.get());
+    else {
+      ++Counter;
+      Vec.back().push_back(CU.get());
+    }
+    if (Counter % opts::BatchSize == 0 && !Vec.back().empty())
+      Vec.push_back({});
+  }
+  return Vec;
+}
+
 void DWARFRewriter::updateDebugInfo() {
   ErrorOr<BinarySection &> DebugInfo = BC.getUniqueSectionByName(".debug_info");
   if (!DebugInfo)
     return;
 
   ARangesSectionWriter = std::make_unique<DebugARangesSectionWriter>();
   StrWriter = std::make_unique<DebugStrWriter>(BC);
 
auto processUnitDIE = [&](size_t CUIndex, DWARFUnit *Unit,
 
     DebugLocWriter *DebugLocWriter = nullptr;
     DebugRangesSectionWriter *RangesSectionWriter =
         Unit->getVersion() >= 5 ? RangeListsSectionWriter.get()
                                 : LegacyRangesSectionWriter.get();
     // Skipping CUs that failed to load.
     if (SplitCU) {
       DIEBuilder DwoDIEBlder(&(*SplitCU)->getContext(), true);
+      DwoDIEBlder.buildBoth();
       std::string DWOName = updateDWONameCompDir(
           *Unit, *DIEBlder, *DIEBlder->getUnitDIEbyUnit(*Unit));
 
       DebugLoclistWriter DebugLocDWoWriter(*Unit, Unit->getVersion(), true);
       DebugRangesSectionWriter *TempRangesSectionWriter = RangesSectionWriter;
       if (Unit->getVersion() >= 5) {
         TempRangesSectionWriter = RangeListsWritersByCU[*DWOId].get();
       } else {
if (SplitCU) {
       auto LocListWriterIter = LocListWritersByCU.find(CUIndex);
       if (LocListWriterIter != LocListWritersByCU.end())
         DebugLocWriter = LocListWriterIter->second.get();
     }
     if (Unit->getVersion() >= 5) {
       RangesBase = RangesSectionWriter->getSectionOffset() +
                    getDWARF5RngListLocListHeaderSize();
       RangesSectionWriter->initSection(*Unit);
-      StrOffstsWriter->finalizeSection(*Unit);
+      StrOffstsWriter->finalizeSection(*Unit, *DIEBlder);
     }
 
     updateUnitDebugInfo(*Unit, *DIEBlder, *DebugLocWriter, *RangesSectionWriter,
                         RangesBase);
     DebugLocWriter->finalize(*DIEBlder, *DIEBlder->getUnitDIEbyUnit(*Unit));
     if (Unit->getVersion() >= 5)
       RangesSectionWriter->finalizeSection();
+    AddrWriter->update(*DIEBlder, *Unit);
   };
 
   CUIndex = 0;
   DIEBuilder DIEBlder(BC.DwCtx.get());
-  if (opts::NoThreads || opts::DeterministicDebugInfo) {
-    for (std::unique_ptr<DWARFUnit> &CU : BC.DwCtx->compile_units()) {
-      processUnitDIE(CUIndex++, CU.get(), &DIEBlder);
+  DIEBlder.buildTypeUnits();
+  SmallVector<char, 20> OutBuffer;
+  std::unique_ptr<raw_svector_ostream> ObjOS =
+      std::make_unique<raw_svector_ostream>(OutBuffer);
+  const object::ObjectFile *File = BC.DwCtx->getDWARFObj().getFile();
+  auto TheTriple = std::make_unique<Triple>(File->makeTriple());
+  std::unique_ptr<DIEStreamer> Streamer =
+      createDIEStreamer(*TheTriple, *ObjOS, "TypeStreamer", DIEBlder, *this);
+  CUOffsetMap OffsetMap = finalizeTypeSections(DIEBlder, *Streamer);
+
+  bool SingleMode = opts::NoThreads || opts::DeterministicDebugInfo;
+  if (!SingleMode)
+    DIEBlder.buildCompileUnits();
+  if (SingleMode) {
+    CUPartitionVector PartVec = partitionCUs(*BC.DwCtx);
+    for (std::vector<DWARFUnit *> &Vec : PartVec) {
+      DIEBlder.buildCompileUnits(Vec);
+      for (DWARFUnit *CU : DIEBlder.getProcessedCUs())
+        processUnitDIE(CUIndex++, CU, &DIEBlder);
+      finalizeCompileUnits(DIEBlder, *Streamer, OffsetMap,
+                           DIEBlder.getProcessedCUs());
     }
   } else {
     // Update unit debug info in parallel
     ThreadPool &ThreadPool = ParallelUtilities::getThreadPool();
     for (std::unique_ptr<DWARFUnit> &CU : BC.DwCtx->compile_units()) {
       ThreadPool.async(processUnitDIE, CUIndex, CU.get(), &DIEBlder);
       CUIndex++;
     }
     ThreadPool.wait();
   }
 
   if (opts::WriteDWP)
     finalizeDWP(State);
 
-  CUOffsetMap OffsetMap = finalizeDebugSections(DIEBlder);
+  finalizeDebugSections(DIEBlder, *Streamer, *ObjOS, OffsetMap);
   updateGdbIndexSection(OffsetMap, CUIndex);
 }
 
 void DWARFRewriter::updateUnitDebugInfo(
     DWARFUnit &Unit, DIEBuilder &DIEBldr, DebugLocWriter &DebugLocWriter,
     DebugRangesSectionWriter &RangesSectionWriter,
     std::optional<uint64_t> RangesBase) {
   // Cache debug ranges so that the offset for identical ranges could be reused.
void DWARFRewriter::updateLineTableOffsets(const MCAsmLayout &Layout) {
   // that the pending relocations will be processed and not ignored.
   if (DbgInfoSection)
     DbgInfoSection->setIsFinalized();
 
   if (TypeInfoSection)
     TypeInfoSection->setIsFinalized();
 }
 
-CUOffsetMap DWARFRewriter::finalizeDebugSections(DIEBuilder &DIEBlder) {
+CUOffsetMap DWARFRewriter::finalizeTypeSections(DIEBuilder &DIEBlder,
+                                                DIEStreamer &Streamer) {
+  // update TypeUnit DW_AT_stmt_list with new .debug_line information.
+  for (const std::unique_ptr<DWARFUnit> &TU : BC.DwCtx->types_section_units()) {
+    DIE *UnitDIE = DIEBlder.getUnitDIEbyUnit(*TU.get());
+    DIEValue StmtAttrInfo = UnitDIE->findAttribute(dwarf::DW_AT_stmt_list);
+    if (!StmtAttrInfo || !TypeUnitRelocMap.count(TU.get()))
+      continue;
+    DIEBlder.replaceValue(UnitDIE, dwarf::DW_AT_stmt_list,
+                          StmtAttrInfo.getForm(),
+                          DIEInteger(TypeUnitRelocMap[TU.get()]));
+  }
+
+  // generate and populate abbrevs here
+  DIEBlder.generateAbbrevs();
+  DIEBlder.finish();
+  SmallVector<char, 20> OutBuffer;
+  std::shared_ptr<raw_svector_ostream> ObjOS =
+      std::make_shared<raw_svector_ostream>(OutBuffer);
+  const object::ObjectFile *File = BC.DwCtx->getDWARFObj().getFile();
+  auto TheTriple = std::make_unique<Triple>(File->makeTriple());
+  std::unique_ptr<DIEStreamer> TypeStreamer =
+      createDIEStreamer(*TheTriple, *ObjOS, "TypeStreamer", DIEBlder, *this);
+
+  // generate debug_info and CUMap
+  CUOffsetMap CUMap;
+  for (std::unique_ptr<llvm::DWARFUnit> &CU : BC.DwCtx->info_section_units()) {
+    if (!CU->isTypeUnit())
+      continue;
+    emitUnit(DIEBlder, Streamer, *CU.get());
+    uint32_t StartOffset = CUOffset;
+    DIE *UnitDIE = DIEBlder.getUnitDIEbyUnit(*CU.get());
+    CUOffset += CU.get()->getHeaderSize();
+    CUOffset += UnitDIE->getSize();
+    CUMap[CU.get()->getOffset()] = {StartOffset, CUOffset - StartOffset - 4};
+  }
+
+  // Emit Type Unit of DWARF 4 to .debug_type section
+  for (DWARFUnit *TU : DIEBlder.getDWARF4TUVector())
+    emitUnit(DIEBlder, *TypeStreamer, *TU);
+
+  TypeStreamer->finish();
+
+  std::unique_ptr<MemoryBuffer> ObjectMemBuffer =
+      MemoryBuffer::getMemBuffer(ObjOS->str(), "in-memory object file", false);
+  std::unique_ptr<object::ObjectFile> Obj = cantFail(
+      object::ObjectFile::createObjectFile(ObjectMemBuffer->getMemBufferRef()),
+      "error creating in-memory object");
+
+  for (const SectionRef &Secs : Obj->sections()) {
+    StringRef Contents = cantFail(Secs.getContents());
+    StringRef Name = cantFail(Secs.getName());
+    if (Name.equals(".debug_types"))
+      BC.registerOrUpdateNoteSection(".debug_types", copyByteArray(Contents),
+                                     Contents.size());
+  }
+  return CUMap;
+}
+
+void DWARFRewriter::finalizeDebugSections(DIEBuilder &DIEBlder,
+                                          DIEStreamer &Streamer,
+                                          raw_svector_ostream &ObjOS,
+                                          CUOffsetMap &CUMap) {
   if (StrWriter->isInitialized()) {
     RewriteInstance::addToDebugSectionsToOverwrite(".debug_str");
     std::unique_ptr<DebugStrBufferVector> DebugStrSectionContents =
         StrWriter->releaseBuffer();
     BC.registerOrUpdateNoteSection(".debug_str",
                                    copyByteArray(*DebugStrSectionContents),
                                    DebugStrSectionContents->size());
   }
void DWARFRewriter::finalizeDebugSections(DIEBuilder &DIEBlder,
 
   // AddrWriter should be finalized after debug_loc since more addresses can be
   // added there.
   if (AddrWriter->isInitialized()) {
     AddressSectionBuffer AddressSectionContents = AddrWriter->finalize();
     BC.registerOrUpdateNoteSection(".debug_addr",
                                    copyByteArray(AddressSectionContents),
                                    AddressSectionContents.size());
-    for (std::unique_ptr<llvm::DWARFUnit> &CU : BC.DwCtx->compile_units()) {
-      DIE *Die = DIEBlder.getUnitDIEbyUnit(*CU.get());
-      uint64_t Offset = 0;
-      DIEValue GnuAddrBaseAttrInfo =
-          Die->findAttribute(dwarf::DW_AT_GNU_addr_base);
-      DIEValue AddrBaseAttrInfo = Die->findAttribute(dwarf::DW_AT_addr_base);
-      dwarf::Form BaseAttrForm;
-      dwarf::Attribute BaseAttr;
-      // For cases where Skeleton CU does not have DW_AT_GNU_addr_base
-      if (!GnuAddrBaseAttrInfo && CU->getVersion() < 5)
-        continue;
-
-      if (!AddrBaseAttrInfo && CU->getVersion() >= 5 &&
-          !AddrWriter->doesCUExist(*CU))
-        continue;
-
-      Offset = AddrWriter->getOffset(*CU);
-
-      if (GnuAddrBaseAttrInfo) {
-        BaseAttrForm = GnuAddrBaseAttrInfo.getForm();
-        BaseAttr = GnuAddrBaseAttrInfo.getAttribute();
-      }
-
-      if (AddrBaseAttrInfo) {
-        BaseAttrForm = AddrBaseAttrInfo.getForm();
-        BaseAttr = AddrBaseAttrInfo.getAttribute();
-      }
-
-      if (GnuAddrBaseAttrInfo || AddrBaseAttrInfo) {
-        DIEBlder.replaceValue(Die, BaseAttr, BaseAttrForm, DIEInteger(Offset));
-      } else if (CU->getVersion() >= 5) {
-        // A case where we were not using .debug_addr section, but after update
-        // now using it.
-        DIEBlder.addValue(Die, dwarf::DW_AT_addr_base,
-                          dwarf::DW_FORM_sec_offset, DIEInteger(Offset));
-      }
-    }
   }
 
-  // update TypeUnit DW_AT_stmt_list with new .debug_line information.
-  for (const std::unique_ptr<DWARFUnit> &TU : BC.DwCtx->types_section_units()) {
-    DIE *UnitDIE = DIEBlder.getUnitDIEbyUnit(*TU.get());
-    DIEValue StmtAttrInfo = UnitDIE->findAttribute(dwarf::DW_AT_stmt_list);
-    if (!StmtAttrInfo || !TypeUnitRelocMap.count(TU.get()))
-      continue;
-    DIEBlder.replaceValue(UnitDIE, dwarf::DW_AT_stmt_list,
-                          StmtAttrInfo.getForm(),
-                          DIEInteger(TypeUnitRelocMap[TU.get()]));
-  }
-
-  // generate and populate abbrevs here
-  DIEBlder.generateAbbrevs();
-  DIEBlder.finish();
-  SmallVector<char, 20> OutBuffer;
-  std::shared_ptr<raw_svector_ostream> ObjOS =
-      std::make_shared<raw_svector_ostream>(OutBuffer);
-  const object::ObjectFile *File = BC.DwCtx->getDWARFObj().getFile();
-  auto TheTriple = std::make_unique<Triple>(File->makeTriple());
-  std::unique_ptr<DIEStreamer> Streamer = createDIEStreamer(
-      *TheTriple, *ObjOS, "AbbrevStreamerInitAug2", DIEBlder, *this);
-
-  // generate debug_info and CUMap
-  CUOffsetMap CUMap;
-  uint32_t CUOffset = 0;
-  for (std::unique_ptr<llvm::DWARFUnit> &CU : BC.DwCtx->info_section_units()) {
-    emitUnit(DIEBlder, Streamer, *CU.get());
-
-    uint32_t StartOffset = CUOffset;
-    DIE *UnitDIE = DIEBlder.getUnitDIEbyUnit(*CU.get());
-    CUOffset += CU.get()->getHeaderSize();
-    CUOffset += UnitDIE->getSize();
-    CUMap[CU.get()->getOffset()] = {StartOffset, CUOffset - StartOffset - 4};
-  }
-
-  // Emit Type Unit of DWARF 4 to .debug_type section
-  for (DWARFUnit *TU : DIEBlder.getDWARF4TUVector())
-    emitUnit(DIEBlder, Streamer, *TU);
-
-  Streamer->emitAbbrevs(DIEBlder.getAbbrevs(), BC.DwCtx->getMaxVersion());
-  Streamer->finish();
+  Streamer.emitAbbrevs(DIEBlder.getAbbrevs(), BC.DwCtx->getMaxVersion());
+  Streamer.finish();
 
   std::unique_ptr<MemoryBuffer> ObjectMemBuffer =
-      MemoryBuffer::getMemBuffer(ObjOS->str(), "in-memory object file", false);
+      MemoryBuffer::getMemBuffer(ObjOS.str(), "in-memory object file", false);
   std::unique_ptr<object::ObjectFile> Obj = cantFail(
       object::ObjectFile::createObjectFile(ObjectMemBuffer->getMemBufferRef()),
       "error creating in-memory object");
 
   for (const SectionRef &Secs : Obj->sections()) {
     StringRef Contents = cantFail(Secs.getContents());
     StringRef Name = cantFail(Secs.getName());
     if (Name.equals(".debug_abbrev")) {
       BC.registerOrUpdateNoteSection(".debug_abbrev", copyByteArray(Contents),
                                      Contents.size());
     } else if (Name.equals(".debug_info")) {
       BC.registerOrUpdateNoteSection(".debug_info", copyByteArray(Contents),
                                      Contents.size());
-    } else if (Name.equals(".debug_types")) {
-      BC.registerOrUpdateNoteSection(".debug_types", copyByteArray(Contents),
-                                     Contents.size());
     }
   }
 
   // Skip .debug_aranges if we are re-generating .gdb_index.
   if (opts::KeepARanges || !BC.getGdbIndexSection()) {
     SmallVector<char, 16> ARangesBuffer;
     raw_svector_ostream OS(ARangesBuffer);
 
     auto MAB = std::unique_ptr<MCAsmBackend>(
         BC.TheTarget->createMCAsmBackend(*BC.STI, *BC.MRI, MCTargetOptions()));
 
     ARangesSectionWriter->writeARangesSection(OS, CUMap);
     const StringRef &ARangesContents = OS.str();
 
     BC.registerOrUpdateNoteSection(".debug_aranges",
                                    copyByteArray(ARangesContents),
                                    ARangesContents.size());
   }
-  return CUMap;
+}
+
+void DWARFRewriter::finalizeCompileUnits(DIEBuilder &DIEBlder,
+                                         DIEStreamer &Streamer,
+                                         CUOffsetMap &CUMap,
+                                         const std::list<DWARFUnit *> &CUs) {
+  DIEBlder.generateAbbrevs();
+  DIEBlder.finish();
+  // generate debug_info and CUMap
+  for (DWARFUnit *CU : CUs) {
+    emitUnit(DIEBlder, Streamer, *CU);
+    uint32_t StartOffset = CUOffset;
+    DIE *UnitDIE = DIEBlder.getUnitDIEbyUnit(*CU);
+    CUOffset += CU->getHeaderSize();
+    CUOffset += UnitDIE->getSize();
+    CUMap[CU->getOffset()] = {StartOffset, CUOffset - StartOffset - 4};
+  }
 }
 
 // Creates all the data structures necessary for creating MCStreamer.
 // They are passed by reference because they need to be kept around.
 // Also creates known debug sections. These are sections handled by
 // handleDebugDataPatching.
 namespace {
 
void DWARFRewriter::updateGdbIndexSection(CUOffsetMap &CUMap, uint32_t NumCUs) {
   write32le(Buffer, Version);
   write32le(Buffer + 4, CUListOffset);
   write32le(Buffer + 8, CUTypesOffset);
   write32le(Buffer + 12, AddressTableOffset);
   write32le(Buffer + 16, SymbolTableOffset + Delta);
   write32le(Buffer + 20, ConstantPoolOffset + Delta);
   Buffer += 24;
 
+  using MapEntry = std::pair<uint32_t, CUInfo>;
+  std::vector<MapEntry> CUVector(CUMap.begin(), CUMap.end());
+  // Need to sort since we write out all of TUs in .debug_info before CUs.
+  std::sort(CUVector.begin(), CUVector.end(),
+            [](const MapEntry &E1, const MapEntry &E2) -> bool {
+              return E1.second.Offset < E2.second.Offset;
+            });
   // Writing out CU List <Offset, Size>
-  for (auto &CUInfo : CUMap) {
+  for (auto &CUInfo : CUVector) {
     // Skipping TU for DWARF5 when they are not included in CU list.
     if (!OriginalOffsets.count(CUInfo.first))
       continue;
     write64le(Buffer, CUInfo.second.Offset);
     // Length encoded in CU doesn't contain first 4 bytes that encode length.
     write64le(Buffer + 8, CUInfo.second.Length + 4);
     Buffer += 16;
   }

bolt/test/X86/Inputs/dwarf5-helper1-addr-section-reuse.s

.Ldebug_info_start0:
   .long 0x8                             # DW_AT_addr_base
   .byte 2                               # Abbrev [2] 0x23:0x10 DW_TAG_subprogram
   .byte 1                               # DW_AT_frame_base
   .byte 86
   .byte 3                               # DW_AT_linkage_name
   .byte 4                               # DW_AT_name
   .byte 0                               # DW_AT_decl_file
   .byte 1                               # DW_AT_decl_line
-  .long 51                              # DW_AT_type
+  .long 41                              # DW_AT_type
                                         # DW_AT_external
   .byte 3                               # Abbrev [3] 0x33:0x4 DW_TAG_base_type
   .byte 5                               # DW_AT_name
   .byte 5                               # DW_AT_encoding
   .byte 4                               # DW_AT_byte_size
   .byte 0                               # End Of Children Mark
 .Ldebug_info_end0:
   .section  .debug_str_offsets,"",@progbits

bolt/test/X86/Inputs/dwarf5-helper2-addr-section-reuse.s

.Ldebug_info_start0:
   .long 0x8                             # DW_AT_addr_base
   .byte 2                               # Abbrev [2] 0x23:0x10 DW_TAG_subprogram
   .byte 1                               # DW_AT_frame_base
   .byte 86
   .byte 3                               # DW_AT_linkage_name
   .byte 4                               # DW_AT_name
   .byte 0                               # DW_AT_decl_file
   .byte 1                               # DW_AT_decl_line
-  .long 51                              # DW_AT_type
+  .long 41                              # DW_AT_type
                                         # DW_AT_external
   .byte 3                               # Abbrev [3] 0x33:0x4 DW_TAG_base_type
   .byte 5                               # DW_AT_name
   .byte 5                               # DW_AT_encoding
   .byte 4                               # DW_AT_byte_size
   .byte 0                               # End Of Children Mark
 .Ldebug_info_end0:
   .section  .debug_str_offsets,"",@progbits

bolt/test/X86/dwarf4-types-dwarf5-types.test

 # REQUIRES: system-linux
 
 # RUN: llvm-mc -dwarf-version=4 -filetype=obj -triple x86_64-unknown-linux %p/Inputs/dwarf4-types-dwarf5-types-main.s -o %tmain.o
 # RUN: llvm-mc -dwarf-version=5 -filetype=obj -triple x86_64-unknown-linux %p/Inputs/dwarf4-types-dwarf5-types-helper.s -o %thelper.o
 # RUN: %clang %cflags %tmain.o %thelper.o -o %t.exe -Wl,-q
 # RUN: llvm-bolt %t.exe -o %t.bolt --update-debug-sections
 # RUN: llvm-dwarfdump --show-form --verbose --debug-info %t.bolt | FileCheck --check-prefix=POSTCHECK %s
 # RUN: llvm-dwarfdump --show-form --verbose --debug-types %t.bolt | FileCheck --check-prefix=POSTCHECKTU %s
 
 # Check BOLT handles DWARF4/5 with fdebug-types.
 
-# POSTCHECK: version = 0x0004
-# POSTCHECK: DW_TAG_compile_unit [6]
-# POSTCHECK: DW_TAG_subprogram [7]
-# POSTCHECK: DW_AT_type [DW_FORM_ref4] (cu + 0x007c => {0x0000007c} "int")
-# POSTCHECK: DW_TAG_formal_parameter [8]
-# POSTCHECK: DW_AT_type [DW_FORM_ref4] (cu + 0x007c => {0x0000007c} "int")
-# POSTCHECK: DW_TAG_formal_parameter [8]
-# POSTCHECK: DW_AT_type [DW_FORM_ref4] (cu + 0x0083 => {0x00000083} "char **")
-# POSTCHECK: DW_TAG_variable [9]
-# POSTCHECK: DW_AT_type [DW_FORM_ref4] (cu + 0x0094 => {0x00000094} "Foo")
-# POSTCHECK: DW_TAG_base_type [5]
-# POSTCHECK: DW_TAG_pointer_type [4]
-
 # POSTCHECK: version = 0x0005
-# POSTCHECK: DW_TAG_type_unit [11]
-# POSTCHECK: DW_TAG_member [13]
-# POSTCHECK: DW_AT_type [DW_FORM_ref4] (cu + 0x0045 => {0x000000ec} "char *")
+# POSTCHECK: DW_TAG_type_unit
+# POSTCHECK: DW_TAG_member
+# POSTCHECK: DW_AT_type [DW_FORM_ref4] (cu + 0x0045 => {0x{{[0-9a-f]+}}} "char *")
 # POSTCHECK: DW_TAG_pointer_type [4]
-# POSTCHECK-NEXT: DW_AT_type [DW_FORM_ref4] (cu + 0x004a => {0x000000f1} "char")
+# POSTCHECK-NEXT: DW_AT_type [DW_FORM_ref4] (cu + 0x004a => {0x{{[0-9a-f]+}}} "char")
 
 # POSTCHECK: version = 0x0005
-# POSTCHECK: DW_TAG_type_unit [11]
-# POSTCHECK: DW_TAG_structure_type [12]
-# POSTCHECK: DW_TAG_member [13]
-# POSTCHECK: DW_AT_type [DW_FORM_ref4] (cu + 0x003c => {0x00000132} "char *")
-# POSTCHECK: DW_TAG_member [13]
-# POSTCHECK: DW_AT_type [DW_FORM_ref4] (cu + 0x003c => {0x00000132} "char *")
+# POSTCHECK: DW_TAG_type_unit
+# POSTCHECK: DW_TAG_structure_type
+# POSTCHECK: DW_TAG_member
+# POSTCHECK: DW_AT_type [DW_FORM_ref4] (cu + 0x003c => {0x{{[0-9a-f]+}}} "char *")
+# POSTCHECK: DW_TAG_member
+# POSTCHECK: DW_AT_type [DW_FORM_ref4] (cu + 0x003c => {0x{{[0-9a-f]+}}} "char *")
 # POSTCHECK: DW_TAG_pointer_type [4]
-# POSTCHECK-NEXT: DW_AT_type [DW_FORM_ref4] (cu + 0x0041 => {0x00000137} "char")
+# POSTCHECK-NEXT: DW_AT_type [DW_FORM_ref4] (cu + 0x0041 => {0x{{[0-9a-f]+}}} "char")
+
+# POSTCHECK: version = 0x0004
+# POSTCHECK: DW_TAG_compile_unit
+# POSTCHECK: DW_TAG_subprogram
+# POSTCHECK: DW_AT_type [DW_FORM_ref4] (cu + 0x007c => {0x{{[0-9a-f]+}}} "int")
+# POSTCHECK: DW_TAG_formal_parameter
+# POSTCHECK: DW_AT_type [DW_FORM_ref4] (cu + 0x007c => {0x{{[0-9a-f]+}}} "int")
+# POSTCHECK: DW_TAG_formal_parameter
+# POSTCHECK: DW_AT_type [DW_FORM_ref4] (cu + 0x0083 => {0x{{[0-9a-f]+}}} "char **")
+# POSTCHECK: DW_TAG_variable
+# POSTCHECK: DW_AT_type [DW_FORM_ref4] (cu + 0x0094 => {0x{{[0-9a-f]+}}} "Foo")
+# POSTCHECK: DW_TAG_base_type
+# POSTCHECK: DW_TAG_pointer_type
 
 # POSTCHECK: version = 0x0005
-# POSTCHECK: DW_TAG_compile_unit [15]
-# POSTCHECK: DW_TAG_subprogram [16]
-# POSTCHECK: DW_AT_type [DW_FORM_ref4] (cu + 0x0048 => {0x00000184} "int")
-# POSTCHECK: DW_TAG_variable [17]
-# POSTCHECK: DW_AT_type [DW_FORM_ref4] (cu + 0x004c => {0x00000188} "Foo2a")
-# POSTCHECK: DW_TAG_base_type [14]
-# POSTCHECK: DW_TAG_structure_type [10]
+# POSTCHECK: DW_TAG_compile_unit
+# POSTCHECK: DW_TAG_subprogram
+# POSTCHECK: DW_AT_type [DW_FORM_ref4] (cu + 0x0048 => {0x{{[0-9a-f]+}}} "int")
+# POSTCHECK: DW_TAG_variable
+# POSTCHECK: DW_AT_type [DW_FORM_ref4] (cu + 0x004c => {0x{{[0-9a-f]+}}} "Foo2a")
+# POSTCHECK: DW_TAG_base_type
+# POSTCHECK: DW_TAG_structure_type
 # POSTCHECK: DW_AT_signature [DW_FORM_ref_sig8]  (0x104ec427d2ebea6f)
-# POSTCHECK: DW_TAG_structure_type [10]
+# POSTCHECK: DW_TAG_structure_type
 # POSTCHECK: DW_AT_signature [DW_FORM_ref_sig8]  (0xb4580bc1535df1e4)
 
 # POSTCHECKTU: version = 0x0004
 # POSTCHECKTU-SAME: type_signature = 0x675d23e4f33235f2
 # POSTCHECKTU-SAME: type_offset = 0x001e
-# POSTCHECKTU: DW_TAG_type_unit [1]
-# POSTCHECKTU: DW_TAG_member [3]
-# POSTCHECKTU: DW_AT_type [DW_FORM_ref4] (cu + 0x004c => {0x0000004c} "char *")
-# POSTCHECKTU: DW_TAG_member [3]
-# POSTCHECKTU: DW_AT_type [DW_FORM_ref4] (cu + 0x004c => {0x0000004c} "char *")
-# POSTCHECKTU: DW_TAG_pointer_type [4]
-# POSTCHECKTU-NEXT: DW_AT_type [DW_FORM_ref4] (cu + 0x0051 => {0x00000051} "char")
-# POSTCHECKTU: DW_TAG_base_type [5]
+# POSTCHECKTU: DW_TAG_type_unit
+# POSTCHECKTU: DW_TAG_member
+# POSTCHECKTU: DW_AT_type [DW_FORM_ref4] (cu + 0x004c => {0x{{[0-9a-f]+}}} "char *")
+# POSTCHECKTU: DW_TAG_member
+# POSTCHECKTU: DW_AT_type [DW_FORM_ref4] (cu + 0x004c => {0x{{[0-9a-f]+}}} "char *")
+# POSTCHECKTU: DW_TAG_pointer_type
+# POSTCHECKTU-NEXT: DW_AT_type [DW_FORM_ref4] (cu + 0x0051 => {0x{{[0-9a-f]+}}} "char")
+# POSTCHECKTU: DW_TAG_base_type
 # POSTCHECKTU: DW_AT_name [DW_FORM_strp] ( .debug_str[0x0000000e] = "char")
 
 # POSTCHECKTU: version = 0x0004
 # POSTCHECKTU-SAME: type_signature = 0x49dc260088be7e56
 # POSTCHECKTU-SAME: type_offset = 0x001e
-# POSTCHECKTU: DW_TAG_type_unit [1]
-# POSTCHECKTU: DW_TAG_structure_type [2]
-# POSTCHECKTU: DW_TAG_member [3]
-# POSTCHECKTU: DW_AT_type [DW_FORM_ref4] (cu + 0x0040 => {0x00000099} "char *")
-# POSTCHECKTU: DW_TAG_member [3]
-# POSTCHECKTU: DW_AT_type [DW_FORM_ref4] (cu + 0x0040 => {0x00000099} "char *")
-# POSTCHECKTU: DW_TAG_pointer_type [4]
-# POSTCHECKTU-NEXT: DW_AT_type [DW_FORM_ref4] (cu + 0x0045 => {0x0000009e} "char")
-# POSTCHECKTU: DW_TAG_base_type [5]
+# POSTCHECKTU: DW_TAG_type_unit
+# POSTCHECKTU: DW_TAG_structure_type
+# POSTCHECKTU: DW_TAG_member
+# POSTCHECKTU: DW_AT_type [DW_FORM_ref4] (cu + 0x0040 => {0x{{[0-9a-f]+}}} "char *")
+# POSTCHECKTU: DW_TAG_member
+# POSTCHECKTU: DW_AT_type [DW_FORM_ref4] (cu + 0x0040 => {0x{{[0-9a-f]+}}} "char *")
+# POSTCHECKTU: DW_TAG_pointer_type
+# POSTCHECKTU-NEXT: DW_AT_type [DW_FORM_ref4] (cu + 0x0045 => {0x{{[0-9a-f]+}}} "char")
+# POSTCHECKTU: DW_TAG_base_type
 # POSTCHECKTU-NEXT: DW_AT_name [DW_FORM_strp] ( .debug_str[0x0000000e] = "char")

bolt/test/X86/dwarf5-gdb-index-types-gdb-generated-gdb11.test

 # REQUIRES: system-linux
 
 # RUN: llvm-mc -dwarf-version=5 -filetype=obj -triple x86_64-unknown-linux %p/Inputs/dwarf5-gdb-index-types-main.s -o %tmaingdb.o
 # RUN: llvm-mc -dwarf-version=5 -filetype=obj -triple x86_64-unknown-linux %p/Inputs/dwarf5-gdb-index-types-helper.s -o %thelpergdb.o
 # RUN: %clang %cflags %tmaingdb.o %thelpergdb.o -o %tgdb.exe -Wl,-q
 # RUN: llvm-objcopy %tgdb.exe --add-section=.gdb_index=%p/Inputs/dwarf5-gdb-index-types-v8.generted-gdb11.gdb-index
 # RUN: llvm-bolt %tgdb.exe -o %tgdb.bolt --update-debug-sections
 # RUN: llvm-dwarfdump --gdb-index %tgdb.bolt | FileCheck --check-prefix=POSTCHECK %s
 
 # Tests that BOLT correctly handles gdb-index generated by GDB.
 
 # POSTCHECK:          Version = 8
 # POSTCHECK:          CU list offset = 0x18, has 2 entries
-# POSTCHECK-NEXT:         0: Offset = 0x40, Length = 0x52
+# POSTCHECK-NEXT:         0: Offset = 0x80, Length = 0x52
 # POSTCHECK-NEXT:         1: Offset = 0xd2, Length = 0x53
 # POSTCHECK:          Types CU list offset = 0x38, has 2 entries
 # POSTCHECK-NEXT:       0: offset = 0x00000000, type_offset = 0x00000023, type_signature = 0x418503b8111e9a7b
-# POSTCHECK-NEXT:       1: offset = 0x00000092, type_offset = 0x00000023, type_signature = 0x00f6cca4e3a15118
+# POSTCHECK-NEXT:       1: offset = 0x00000040, type_offset = 0x00000023, type_signature = 0x00f6cca4e3a15118
 # POSTCHECK:          Address area offset = 0x68, has 2 entries
 # POSTCHECK-NEXT:       Low/High address = [0x1310, 0x131f) (Size: 0xf), CU id = 1
 # POSTCHECK-NEXT:       Low/High address = [0x1320, 0x132d) (Size: 0xd), CU id = 3
 # POSTCHECK:          Symbol table offset = 0x90, size = 1024, filled slots
 # POSTCHECK-NEXT:       2: Name offset = 0x28, CU vector offset = 0x0
 # POSTCHECK-NEXT:         String name: S, CU vector index: 0
 # POSTCHECK-NEXT:       71: Name offset = 0x2a, CU vector offset = 0x8
 # POSTCHECK-NEXT:         String name: S2, CU vector index: 1

bolt/test/X86/dwarf5-gdb-index-types-gdb-generated-gdb9.test

 # REQUIRES: system-linux
 
 # RUN: llvm-mc -dwarf-version=5 -filetype=obj -triple x86_64-unknown-linux %p/Inputs/dwarf5-gdb-index-types-main.s -o %tmaingdb.o
 # RUN: llvm-mc -dwarf-version=5 -filetype=obj -triple x86_64-unknown-linux %p/Inputs/dwarf5-gdb-index-types-helper.s -o %thelpergdb.o
 # RUN: %clang %cflags %tmaingdb.o %thelpergdb.o -o %tgdb.exe -Wl,-q
 # RUN: llvm-objcopy %tgdb.exe --add-section=.gdb_index=%p/Inputs/dwarf5-gdb-index-types-v8.generted-gdb9.gdb-index
 # RUN: llvm-bolt %tgdb.exe -o %tgdb.bolt --update-debug-sections
 # RUN: llvm-dwarfdump --gdb-index %tgdb.bolt | FileCheck --check-prefix=POSTCHECK %s
 
 # Tests that BOLT correctly handles gdb-index generated by GDB.
 
 # POSTCHECK:          Version = 8
 # POSTCHECK:          CU list offset = 0x18, has 4 entries
 # POSTCHECK-NEXT:       0: Offset = 0x0, Length = 0x40
-# POSTCHECK-NEXT:       1: Offset = 0x40, Length = 0x52
-# POSTCHECK-NEXT:       2: Offset = 0x92, Length = 0x40
+# POSTCHECK-NEXT:       1: Offset = 0x40, Length = 0x40
+# POSTCHECK-NEXT:       2: Offset = 0x80, Length = 0x52
 # POSTCHECK-NEXT:       3: Offset = 0xd2, Length = 0x53
 # POSTCHECK:          Types CU list offset = 0x58, has 2 entries
 # POSTCHECK-NEXT:       0: offset = 0x00000000, type_offset = 0x00000023, type_signature = 0x418503b8111e9a7b
-# POSTCHECK-NEXT:       1: offset = 0x00000092, type_offset = 0x00000023, type_signature = 0x00f6cca4e3a15118
+# POSTCHECK-NEXT:       1: offset = 0x00000040, type_offset = 0x00000023, type_signature = 0x00f6cca4e3a15118
 # POSTCHECK:          Address area offset = 0x88, has 2 entries
 # POSTCHECK-NEXT:       Low/High address = [0x1310, 0x131f) (Size: 0xf), CU id = 1
 # POSTCHECK-NEXT:       Low/High address = [0x1320, 0x132d) (Size: 0xd), CU id = 3
 # POSTCHECK:          Symbol table offset = 0xb0, size = 1024, filled slots
 # POSTCHECK-NEXT:       2: Name offset = 0x28, CU vector offset = 0x0
 # POSTCHECK-NEXT:         String name: S, CU vector index: 0
 # POSTCHECK-NEXT:       71: Name offset = 0x2a, CU vector offset = 0x8
 # POSTCHECK-NEXT:         String name: S2, CU vector index: 1

bolt/test/X86/dwarf5-gdb-index-types-lld-generated.test

 # REQUIRES: system-linux
 
 # RUN: llvm-mc -dwarf-version=5 -filetype=obj -triple x86_64-unknown-linux %p/Inputs/dwarf5-gdb-index-types-main.s -o %tmain.o
 # RUN: llvm-mc -dwarf-version=5 -filetype=obj -triple x86_64-unknown-linux %p/Inputs/dwarf5-gdb-index-types-helper.s -o %thelper.o
 # RUN: %clang %cflags %tmain.o %thelper.o -o %t.exe -Wl,-q -Wl,--gdb-index
 # RUN: llvm-bolt %t.exe -o %t.bolt --update-debug-sections
 # RUN: llvm-dwarfdump --gdb-index %t.bolt | FileCheck --check-prefix=POSTCHECK %s
 
 # Tests that BOLT correctly handles gdb-index generated by LLD.
 
 # POSTCHECK:          Version = 7
 # POSTCHECK:          CU list offset = 0x18, has 2 entries
-# POSTCHECK-NEXT:         0: Offset = 0x40, Length = 0x52
+# POSTCHECK-NEXT:         0: Offset = 0x80, Length = 0x52
 # POSTCHECK-NEXT:         1: Offset = 0xd2, Length = 0x53
 # POSTCHECK:          Types CU list offset = 0x38, has 0 entries
 # POSTCHECK:          Address area offset = 0x38, has 2 entries
 # POSTCHECK-NEXT:         Low/High address = [0x1310, 0x131f) (Size: 0xf), CU id = 1
 # POSTCHECK-NEXT:         Low/High address = [0x1320, 0x132d) (Size: 0xd), CU id = 3
 # POSTCHECK:          Symbol table offset = 0x60, size = 1024, filled slots
 # POSTCHECK-NEXT:         2: Name offset = 0x38, CU vector offset = 0x0
 # POSTCHECK-NEXT:             String name: S, CU vector index: 0

bolt/test/X86/dwarf5-locexpr-referrence.test

 # REQUIRES: system-linux
 
 # RUN: llvm-mc -dwarf-version=5 -filetype=obj -triple x86_64-unknown-linux %p/Inputs/dwarf5-locexpr-referrence-main.s -o %tmain.o
 # RUN: llvm-mc -dwarf-version=5 -filetype=obj -triple x86_64-unknown-linux %p/Inputs/dwarf5-locexpr-referrence-helper.s -o %thelper.o
 # RUN: %clang %cflags -dwarf-5 %tmain.o %thelper.o -o %t.exe -Wl,-q
 # RUN: llvm-bolt %t.exe -o %t.bolt --update-debug-sections
 # RUN: llvm-dwarfdump --show-form --verbose --debug-info %t.bolt | FileCheck --check-prefix=CHECK %s
 
 # This test checks that we update relative DIE references with DW_OP_convert that are in locexpr.
 
 # CHECK: version = 0x0005
-# CHECK: version = 0x0005
 # CHECK: DW_TAG_variable
 # CHECK-NEXT: DW_AT_location
-# CHECK-SAME: DW_OP_convert (0x00000028 -> 0x0000005d)
-# CHECK-SAME: DW_OP_convert (0x0000002c -> 0x00000061)
+# CHECK-SAME: DW_OP_convert (0x00000028 -> 0x00000028)
+# CHECK-SAME: DW_OP_convert (0x0000002c -> 0x0000002c)
 # CHECK: version = 0x0005
 # CHECK: DW_TAG_variable
 # CHECK-NEXT: DW_AT_location
-# CHECK-SAME: DW_OP_convert (0x00000028 -> 0x000000c4)
-# CHECK-SAME: DW_OP_convert (0x0000002c -> 0x000000c8)
+# CHECK-SAME: DW_OP_convert (0x00000028 -> 0x0000008f)
+# CHECK-SAME: DW_OP_convert (0x0000002c -> 0x00000093)
+# CHECK: version = 0x0005