--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tools/dsymutil/DwarfLinker.h	Wed Aug 14 19:46:37 2019 +0900
@@ -0,0 +1,510 @@
+//===- tools/dsymutil/DwarfLinker.h - Dwarf debug info linker ---*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TOOLS_DSYMUTIL_DWARFLINKER_H
+#define LLVM_TOOLS_DSYMUTIL_DWARFLINKER_H
+
+#include "BinaryHolder.h"
+#include "CompileUnit.h"
+#include "DebugMap.h"
+#include "DeclContext.h"
+#include "DwarfStreamer.h"
+#include "LinkUtils.h"
+#include "llvm/DebugInfo/DWARF/DWARFContext.h"
+
+namespace llvm {
+namespace dsymutil {
+
+/// Partial address range for debug map objects. Besides an offset, only the
+/// HighPC is stored. The structure is stored in a map where the LowPC is the
+/// key.
+struct DebugMapObjectRange {
+  /// Function HighPC.
+  uint64_t HighPC;
+  /// Offset to apply to the linked address.
+  int64_t Offset;
+
+  DebugMapObjectRange(uint64_t EndPC, int64_t Offset)
+      : HighPC(EndPC), Offset(Offset) {}
+
+  DebugMapObjectRange() : HighPC(0), Offset(0) {}
+};
+
+/// Map LowPC to DebugMapObjectRange.
+using RangesTy = std::map<uint64_t, DebugMapObjectRange>;
+using UnitListTy = std::vector<std::unique_ptr<CompileUnit>>;
+
+/// The core of the Dwarf linking logic.
+///
+/// The link of the dwarf information from the object files will be
+/// driven by the selection of 'root DIEs', which are DIEs that
+/// describe variables or functions that are present in the linked
+/// binary (and thus have entries in the debug map). All the debug
+/// information that will be linked (the DIEs, but also the line
+/// tables, ranges, ...) is derived from that set of root DIEs.
+///
+/// The root DIEs are identified because they contain relocations that
+/// correspond to a debug map entry at specific places (the low_pc for
+/// a function, the location for a variable). These relocations are
+/// called ValidRelocs in the DwarfLinker and are gathered as a very
+/// first step when we start processing a DebugMapObject.
+class DwarfLinker {
+public:
+  DwarfLinker(raw_fd_ostream &OutFile, BinaryHolder &BinHolder,
+              LinkOptions Options)
+      : OutFile(OutFile), BinHolder(BinHolder), Options(std::move(Options)) {}
+
+  /// Link the contents of the DebugMap.
+  bool link(const DebugMap &);
+
+  void reportWarning(const Twine &Warning, const DebugMapObject &DMO,
+                     const DWARFDie *DIE = nullptr) const;
+
+private:
+  /// Remembers the oldest and newest DWARF version we've seen in a unit.
+  void updateDwarfVersion(unsigned Version) {
+    MaxDwarfVersion = std::max(MaxDwarfVersion, Version);
+    MinDwarfVersion = std::min(MinDwarfVersion, Version);
+  }
+
+  /// Remembers the kinds of accelerator tables we've seen in a unit.
+  void updateAccelKind(DWARFContext &Dwarf);
+
+  /// Emit warnings as Dwarf compile units to leave a trail after linking.
+  bool emitPaperTrailWarnings(const DebugMapObject &DMO, const DebugMap &Map,
+                              OffsetsStringPool &StringPool);
+
+  /// Keeps track of relocations.
+  class RelocationManager {
+    struct ValidReloc {
+      uint64_t Offset;
+      uint32_t Size;
+      uint64_t Addend;
+      const DebugMapObject::DebugMapEntry *Mapping;
+
+      ValidReloc(uint64_t Offset, uint32_t Size, uint64_t Addend,
+                 const DebugMapObject::DebugMapEntry *Mapping)
+          : Offset(Offset), Size(Size), Addend(Addend), Mapping(Mapping) {}
+
+      bool operator<(const ValidReloc &RHS) const {
+        return Offset < RHS.Offset;
+      }
+    };
+
+    const DwarfLinker &Linker;
+
+    /// The valid relocations for the current DebugMapObject.
+    /// This vector is sorted by relocation offset.
+    std::vector<ValidReloc> ValidRelocs;
+
+    /// Index into ValidRelocs of the next relocation to consider. As we walk
+    /// the DIEs in acsending file offset and as ValidRelocs is sorted by file
+    /// offset, keeping this index up to date is all we have to do to have a
+    /// cheap lookup during the root DIE selection and during DIE cloning.
+    unsigned NextValidReloc = 0;
+
+  public:
+    RelocationManager(DwarfLinker &Linker) : Linker(Linker) {}
+
+    bool hasValidRelocs() const { return !ValidRelocs.empty(); }
+
+    /// Reset the NextValidReloc counter.
+    void resetValidRelocs() { NextValidReloc = 0; }
+
+    /// \defgroup FindValidRelocations Translate debug map into a list
+    /// of relevant relocations
+    ///
+    /// @{
+    bool findValidRelocsInDebugInfo(const object::ObjectFile &Obj,
+                                    const DebugMapObject &DMO);
+
+    bool findValidRelocs(const object::SectionRef &Section,
+                         const object::ObjectFile &Obj,
+                         const DebugMapObject &DMO);
+
+    void findValidRelocsMachO(const object::SectionRef &Section,
+                              const object::MachOObjectFile &Obj,
+                              const DebugMapObject &DMO);
+    /// @}
+
+    bool hasValidRelocation(uint64_t StartOffset, uint64_t EndOffset,
+                            CompileUnit::DIEInfo &Info);
+
+    bool applyValidRelocs(MutableArrayRef<char> Data, uint64_t BaseOffset,
+                          bool IsLittleEndian);
+  };
+
+  /// Keeps track of data associated with one object during linking.
+  struct LinkContext {
+    DebugMapObject &DMO;
+    const object::ObjectFile *ObjectFile;
+    RelocationManager RelocMgr;
+    std::unique_ptr<DWARFContext> DwarfContext;
+    RangesTy Ranges;
+    UnitListTy CompileUnits;
+
+    LinkContext(const DebugMap &Map, DwarfLinker &Linker, DebugMapObject &DMO)
+        : DMO(DMO), RelocMgr(Linker) {
+      // Swift ASTs are not object files.
+      if (DMO.getType() == MachO::N_AST) {
+        ObjectFile = nullptr;
+        return;
+      }
+      auto ErrOrObj = Linker.loadObject(DMO, Map);
+      ObjectFile = ErrOrObj ? &*ErrOrObj : nullptr;
+      DwarfContext = ObjectFile ? DWARFContext::create(*ObjectFile) : nullptr;
+    }
+
+    /// Clear part of the context that's no longer needed when we're done with
+    /// the debug object.
+    void Clear() {
+      DwarfContext.reset(nullptr);
+      CompileUnits.clear();
+      Ranges.clear();
+    }
+  };
+
+  /// Called at the start of a debug object link.
+  void startDebugObject(LinkContext &Context);
+
+  /// Called at the end of a debug object link.
+  void endDebugObject(LinkContext &Context);
+
+  /// \defgroup FindRootDIEs Find DIEs corresponding to debug map entries.
+  ///
+  /// @{
+  /// Recursively walk the \p DIE tree and look for DIEs to
+  /// keep. Store that information in \p CU's DIEInfo.
+  ///
+  /// The return value indicates whether the DIE is incomplete.
+  void lookForDIEsToKeep(RelocationManager &RelocMgr, RangesTy &Ranges,
+                         const UnitListTy &Units, const DWARFDie &DIE,
+                         const DebugMapObject &DMO, CompileUnit &CU,
+                         unsigned Flags);
+
+  /// If this compile unit is really a skeleton CU that points to a
+  /// clang module, register it in ClangModules and return true.
+  ///
+  /// A skeleton CU is a CU without children, a DW_AT_gnu_dwo_name
+  /// pointing to the module, and a DW_AT_gnu_dwo_id with the module
+  /// hash.
+  bool registerModuleReference(DWARFDie CUDie, const DWARFUnit &Unit,
+                               DebugMap &ModuleMap, const DebugMapObject &DMO,
+                               RangesTy &Ranges,
+                               OffsetsStringPool &OffsetsStringPool,
+                               UniquingStringPool &UniquingStringPoolStringPool,
+                               DeclContextTree &ODRContexts,
+                               uint64_t ModulesEndOffset, unsigned &UnitID,
+                               bool IsLittleEndian, unsigned Indent = 0,
+                               bool Quiet = false);
+
+  /// Recursively add the debug info in this clang module .pcm
+  /// file (and all the modules imported by it in a bottom-up fashion)
+  /// to Units.
+  Error loadClangModule(DWARFDie CUDie, StringRef FilePath,
+                        StringRef ModuleName, uint64_t DwoId,
+                        DebugMap &ModuleMap, const DebugMapObject &DMO,
+                        RangesTy &Ranges, OffsetsStringPool &OffsetsStringPool,
+                        UniquingStringPool &UniquingStringPool,
+                        DeclContextTree &ODRContexts, uint64_t ModulesEndOffset,
+                        unsigned &UnitID, bool IsLittleEndian,
+                        unsigned Indent = 0, bool Quiet = false);
+
+  /// Flags passed to DwarfLinker::lookForDIEsToKeep
+  enum TraversalFlags {
+    TF_Keep = 1 << 0,            ///< Mark the traversed DIEs as kept.
+    TF_InFunctionScope = 1 << 1, ///< Current scope is a function scope.
+    TF_DependencyWalk = 1 << 2,  ///< Walking the dependencies of a kept DIE.
+    TF_ParentWalk = 1 << 3,      ///< Walking up the parents of a kept DIE.
+    TF_ODR = 1 << 4,             ///< Use the ODR while keeping dependents.
+    TF_SkipPC = 1 << 5,          ///< Skip all location attributes.
+  };
+
+  /// Mark the passed DIE as well as all the ones it depends on as kept.
+  void keepDIEAndDependencies(RelocationManager &RelocMgr, RangesTy &Ranges,
+                              const UnitListTy &Units, const DWARFDie &DIE,
+                              CompileUnit::DIEInfo &MyInfo,
+                              const DebugMapObject &DMO, CompileUnit &CU,
+                              bool UseODR);
+
+  unsigned shouldKeepDIE(RelocationManager &RelocMgr, RangesTy &Ranges,
+                         const DWARFDie &DIE, const DebugMapObject &DMO,
+                         CompileUnit &Unit, CompileUnit::DIEInfo &MyInfo,
+                         unsigned Flags);
+
+  /// Check if a variable describing DIE should be kept.
+  /// \returns updated TraversalFlags.
+  unsigned shouldKeepVariableDIE(RelocationManager &RelocMgr,
+                                 const DWARFDie &DIE, CompileUnit &Unit,
+                                 CompileUnit::DIEInfo &MyInfo, unsigned Flags);
+
+  unsigned shouldKeepSubprogramDIE(RelocationManager &RelocMgr,
+                                   RangesTy &Ranges, const DWARFDie &DIE,
+                                   const DebugMapObject &DMO, CompileUnit &Unit,
+                                   CompileUnit::DIEInfo &MyInfo,
+                                   unsigned Flags);
+
+  bool hasValidRelocation(uint32_t StartOffset, uint32_t EndOffset,
+                          CompileUnit::DIEInfo &Info);
+  /// @}
+
+  /// \defgroup Linking Methods used to link the debug information
+  ///
+  /// @{
+
+  class DIECloner {
+    DwarfLinker &Linker;
+    RelocationManager &RelocMgr;
+
+    /// Allocator used for all the DIEValue objects.
+    BumpPtrAllocator &DIEAlloc;
+
+    std::vector<std::unique_ptr<CompileUnit>> &CompileUnits;
+    LinkOptions Options;
+
+  public:
+    DIECloner(DwarfLinker &Linker, RelocationManager &RelocMgr,
+              BumpPtrAllocator &DIEAlloc,
+              std::vector<std::unique_ptr<CompileUnit>> &CompileUnits,
+              LinkOptions &Options)
+        : Linker(Linker), RelocMgr(RelocMgr), DIEAlloc(DIEAlloc),
+          CompileUnits(CompileUnits), Options(Options) {}
+
+    /// Recursively clone \p InputDIE into an tree of DIE objects
+    /// where useless (as decided by lookForDIEsToKeep()) bits have been
+    /// stripped out and addresses have been rewritten according to the
+    /// debug map.
+    ///
+    /// \param OutOffset is the offset the cloned DIE in the output
+    /// compile unit.
+    /// \param PCOffset (while cloning a function scope) is the offset
+    /// applied to the entry point of the function to get the linked address.
+    /// \param Die the output DIE to use, pass NULL to create one.
+    /// \returns the root of the cloned tree or null if nothing was selected.
+    DIE *cloneDIE(const DWARFDie &InputDIE, const DebugMapObject &DMO,
+                  CompileUnit &U, OffsetsStringPool &StringPool,
+                  int64_t PCOffset, uint32_t OutOffset, unsigned Flags,
+                  bool IsLittleEndian, DIE *Die = nullptr);
+
+    /// Construct the output DIE tree by cloning the DIEs we
+    /// chose to keep above. If there are no valid relocs, then there's
+    /// nothing to clone/emit.
+    void cloneAllCompileUnits(DWARFContext &DwarfContext,
+                              const DebugMapObject &DMO, RangesTy &Ranges,
+                              OffsetsStringPool &StringPool,
+                              bool IsLittleEndian);
+
+  private:
+    using AttributeSpec = DWARFAbbreviationDeclaration::AttributeSpec;
+
+    /// Information gathered and exchanged between the various
+    /// clone*Attributes helpers about the attributes of a particular DIE.
+    struct AttributesInfo {
+      /// Names.
+      DwarfStringPoolEntryRef Name, MangledName, NameWithoutTemplate;
+
+      /// Offsets in the string pool.
+      uint32_t NameOffset = 0;
+      uint32_t MangledNameOffset = 0;
+
+      /// Value of AT_low_pc in the input DIE
+      uint64_t OrigLowPc = std::numeric_limits<uint64_t>::max();
+
+      /// Value of AT_high_pc in the input DIE
+      uint64_t OrigHighPc = 0;
+
+      /// Offset to apply to PC addresses inside a function.
+      int64_t PCOffset = 0;
+
+      /// Does the DIE have a low_pc attribute?
+      bool HasLowPc = false;
+
+      /// Does the DIE have a ranges attribute?
+      bool HasRanges = false;
+
+      /// Is this DIE only a declaration?
+      bool IsDeclaration = false;
+
+      AttributesInfo() = default;
+    };
+
+    /// Helper for cloneDIE.
+    unsigned cloneAttribute(DIE &Die, const DWARFDie &InputDIE,
+                            const DebugMapObject &DMO, CompileUnit &U,
+                            OffsetsStringPool &StringPool,
+                            const DWARFFormValue &Val,
+                            const AttributeSpec AttrSpec, unsigned AttrSize,
+                            AttributesInfo &AttrInfo, bool IsLittleEndian);
+
+    /// Clone a string attribute described by \p AttrSpec and add
+    /// it to \p Die.
+    /// \returns the size of the new attribute.
+    unsigned cloneStringAttribute(DIE &Die, AttributeSpec AttrSpec,
+                                  const DWARFFormValue &Val, const DWARFUnit &U,
+                                  OffsetsStringPool &StringPool,
+                                  AttributesInfo &Info);
+
+    /// Clone an attribute referencing another DIE and add
+    /// it to \p Die.
+    /// \returns the size of the new attribute.
+    unsigned cloneDieReferenceAttribute(DIE &Die, const DWARFDie &InputDIE,
+                                        AttributeSpec AttrSpec,
+                                        unsigned AttrSize,
+                                        const DWARFFormValue &Val,
+                                        const DebugMapObject &DMO,
+                                        CompileUnit &Unit);
+
+    /// Clone a DWARF expression that may be referencing another DIE.
+    void cloneExpression(DataExtractor &Data, DWARFExpression Expression,
+                         const DebugMapObject &DMO, CompileUnit &Unit,
+                         SmallVectorImpl<uint8_t> &OutputBuffer);
+
+    /// Clone an attribute referencing another DIE and add
+    /// it to \p Die.
+    /// \returns the size of the new attribute.
+    unsigned cloneBlockAttribute(DIE &Die, const DebugMapObject &DMO,
+                                 CompileUnit &Unit, AttributeSpec AttrSpec,
+                                 const DWARFFormValue &Val, unsigned AttrSize,
+                                 bool IsLittleEndian);
+
+    /// Clone an attribute referencing another DIE and add
+    /// it to \p Die.
+    /// \returns the size of the new attribute.
+    unsigned cloneAddressAttribute(DIE &Die, AttributeSpec AttrSpec,
+                                   const DWARFFormValue &Val,
+                                   const CompileUnit &Unit,
+                                   AttributesInfo &Info);
+
+    /// Clone a scalar attribute  and add it to \p Die.
+    /// \returns the size of the new attribute.
+    unsigned cloneScalarAttribute(DIE &Die, const DWARFDie &InputDIE,
+                                  const DebugMapObject &DMO, CompileUnit &U,
+                                  AttributeSpec AttrSpec,
+                                  const DWARFFormValue &Val, unsigned AttrSize,
+                                  AttributesInfo &Info);
+
+    /// Get the potential name and mangled name for the entity
+    /// described by \p Die and store them in \Info if they are not
+    /// already there.
+    /// \returns is a name was found.
+    bool getDIENames(const DWARFDie &Die, AttributesInfo &Info,
+                     OffsetsStringPool &StringPool, bool StripTemplate = false);
+
+    /// Create a copy of abbreviation Abbrev.
+    void copyAbbrev(const DWARFAbbreviationDeclaration &Abbrev, bool hasODR);
+
+    uint32_t hashFullyQualifiedName(DWARFDie DIE, CompileUnit &U,
+                                    const DebugMapObject &DMO,
+                                    int RecurseDepth = 0);
+
+    /// Helper for cloneDIE.
+    void addObjCAccelerator(CompileUnit &Unit, const DIE *Die,
+                            DwarfStringPoolEntryRef Name,
+                            OffsetsStringPool &StringPool, bool SkipPubSection);
+  };
+
+  /// Assign an abbreviation number to \p Abbrev
+  void AssignAbbrev(DIEAbbrev &Abbrev);
+
+  /// Compute and emit debug_ranges section for \p Unit, and
+  /// patch the attributes referencing it.
+  void patchRangesForUnit(const CompileUnit &Unit, DWARFContext &Dwarf,
+                          const DebugMapObject &DMO) const;
+
+  /// Generate and emit the DW_AT_ranges attribute for a compile_unit if it had
+  /// one.
+  void generateUnitRanges(CompileUnit &Unit) const;
+
+  /// Extract the line tables from the original dwarf, extract the relevant
+  /// parts according to the linked function ranges and emit the result in the
+  /// debug_line section.
+  void patchLineTableForUnit(CompileUnit &Unit, DWARFContext &OrigDwarf,
+                             RangesTy &Ranges, const DebugMapObject &DMO);
+
+  /// Emit the accelerator entries for \p Unit.
+  void emitAcceleratorEntriesForUnit(CompileUnit &Unit);
+  void emitDwarfAcceleratorEntriesForUnit(CompileUnit &Unit);
+  void emitAppleAcceleratorEntriesForUnit(CompileUnit &Unit);
+
+  /// Patch the frame info for an object file and emit it.
+  void patchFrameInfoForObject(const DebugMapObject &, RangesTy &Ranges,
+                               DWARFContext &, unsigned AddressSize);
+
+  /// FoldingSet that uniques the abbreviations.
+  FoldingSet<DIEAbbrev> AbbreviationsSet;
+
+  /// Storage for the unique Abbreviations.
+  /// This is passed to AsmPrinter::emitDwarfAbbrevs(), thus it cannot be
+  /// changed to a vector of unique_ptrs.
+  std::vector<std::unique_ptr<DIEAbbrev>> Abbreviations;
+
+  /// DIELoc objects that need to be destructed (but not freed!).
+  std::vector<DIELoc *> DIELocs;
+
+  /// DIEBlock objects that need to be destructed (but not freed!).
+  std::vector<DIEBlock *> DIEBlocks;
+
+  /// Allocator used for all the DIEValue objects.
+  BumpPtrAllocator DIEAlloc;
+  /// @}
+
+  /// \defgroup Helpers Various helper methods.
+  ///
+  /// @{
+  bool createStreamer(const Triple &TheTriple, raw_fd_ostream &OutFile);
+
+  /// Attempt to load a debug object from disk.
+  ErrorOr<const object::ObjectFile &> loadObject(const DebugMapObject &Obj,
+                                                 const DebugMap &Map);
+  /// @}
+
+  raw_fd_ostream &OutFile;
+  BinaryHolder &BinHolder;
+  LinkOptions Options;
+  std::unique_ptr<DwarfStreamer> Streamer;
+  uint64_t OutputDebugInfoSize;
+
+  unsigned MaxDwarfVersion = 0;
+  unsigned MinDwarfVersion = std::numeric_limits<unsigned>::max();
+
+  bool AtLeastOneAppleAccelTable = false;
+  bool AtLeastOneDwarfAccelTable = false;
+
+  /// The CIEs that have been emitted in the output section. The actual CIE
+  /// data serves a the key to this StringMap, this takes care of comparing the
+  /// semantics of CIEs defined in different object files.
+  StringMap<uint32_t> EmittedCIEs;
+
+  /// Offset of the last CIE that has been emitted in the output
+  /// debug_frame section.
+  uint32_t LastCIEOffset = 0;
+
+  /// Apple accelerator tables.
+  AccelTable<DWARF5AccelTableStaticData> DebugNames;
+  AccelTable<AppleAccelTableStaticOffsetData> AppleNames;
+  AccelTable<AppleAccelTableStaticOffsetData> AppleNamespaces;
+  AccelTable<AppleAccelTableStaticOffsetData> AppleObjc;
+  AccelTable<AppleAccelTableStaticTypeData> AppleTypes;
+
+  /// Mapping the PCM filename to the DwoId.
+  StringMap<uint64_t> ClangModules;
+
+  /// A list of all .swiftinterface files referenced by the debug
+  /// info, mapping Module name to path on disk. The entries need to
+  /// be uniqued and sorted and there are only few entries expected
+  /// per compile unit, which is why this is a std::map.
+  std::map<std::string, std::string> ParseableSwiftInterfaces;
+
+  bool ModuleCacheHintDisplayed = false;
+  bool ArchiveHintDisplayed = false;
+};
+
+} // end namespace dsymutil
+} // end namespace llvm
+
+#endif // LLVM_TOOLS_DSYMUTIL_DWARFLINKER_H