DWARFLinker/Classic/DWARFLinkerDeclContext.h

0001 //===- DWARFLinkerDeclContext.h ---------------------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef LLVM_DWARFLINKER_CLASSIC_DWARFLINKERDECLCONTEXT_H
0010 #define LLVM_DWARFLINKER_CLASSIC_DWARFLINKERDECLCONTEXT_H
0011
0012 #include "llvm/ADT/DenseMap.h"
0013 #include "llvm/ADT/DenseMapInfo.h"
0014 #include "llvm/ADT/DenseSet.h"
0015 #include "llvm/ADT/StringRef.h"
0016 #include "llvm/CodeGen/NonRelocatableStringpool.h"
0017 #include "llvm/DebugInfo/DWARF/DWARFDebugLine.h"
0018 #include "llvm/DebugInfo/DWARF/DWARFDie.h"
0019 #include "llvm/Support/FileSystem.h"
0020 #include "llvm/Support/Path.h"
0021 #include <atomic>
0022
0023 namespace llvm {
0024 namespace dwarf_linker {
0025 namespace classic {
0026
0027 class CompileUnit;
0028 struct DeclMapInfo;
0029
0030 /// Small helper that resolves and caches file paths. This helps reduce the
0031 /// number of calls to realpath which is expensive. We assume the input are
0032 /// files, and cache the realpath of their parent. This way we can quickly
0033 /// resolve different files under the same path.
0034 class CachedPathResolver {
0035 public:
0036   /// Resolve a path by calling realpath and cache its result. The returned
0037   /// StringRef is interned in the given \p StringPool.
0038   StringRef resolve(const std::string &Path,
0039                     NonRelocatableStringpool &StringPool) {
0040     StringRef FileName = sys::path::filename(Path);
0041     StringRef ParentPath = sys::path::parent_path(Path);
0042
0043     // If the ParentPath has not yet been resolved, resolve and cache it for
0044     // future look-ups.
0045     auto [It, Inserted] = ResolvedPaths.try_emplace(ParentPath);
0046     if (Inserted) {
0047       SmallString<256> RealPath;
0048       sys::fs::real_path(ParentPath, RealPath);
0049       It->second = std::string(RealPath);
0050     }
0051
0052     // Join the file name again with the resolved path.
0053     SmallString<256> ResolvedPath(It->second);
0054     sys::path::append(ResolvedPath, FileName);
0055     return StringPool.internString(ResolvedPath);
0056   }
0057
0058 private:
0059   StringMap<std::string> ResolvedPaths;
0060 };
0061
0062 /// A DeclContext is a named program scope that is used for ODR uniquing of
0063 /// types.
0064 ///
0065 /// The set of DeclContext for the ODR-subject parts of a Dwarf link is
0066 /// expanded (and uniqued) with each new object file processed. We need to
0067 /// determine the context of each DIE in an linked object file to see if the
0068 /// corresponding type has already been emitted.
0069 ///
0070 /// The contexts are conceptually organized as a tree (eg. a function scope is
0071 /// contained in a namespace scope that contains other scopes), but
0072 /// storing/accessing them in an actual tree is too inefficient: we need to be
0073 /// able to very quickly query a context for a given child context by name.
0074 /// Storing a StringMap in each DeclContext would be too space inefficient.
0075 ///
0076 /// The solution here is to give each DeclContext a link to its parent (this
0077 /// allows to walk up the tree), but to query the existence of a specific
0078 /// DeclContext using a separate DenseMap keyed on the hash of the fully
0079 /// qualified name of the context.
0080 class DeclContext {
0081 public:
0082   using Map = DenseSet<DeclContext *, DeclMapInfo>;
0083
0084   DeclContext() : DefinedInClangModule(0), Parent(*this) {}
0085
0086   DeclContext(unsigned Hash, uint32_t Line, uint32_t ByteSize, uint16_t Tag,
0087               StringRef Name, StringRef File, const DeclContext &Parent,
0088               DWARFDie LastSeenDIE = DWARFDie(), unsigned CUId = 0)
0089       : QualifiedNameHash(Hash), Line(Line), ByteSize(ByteSize), Tag(Tag),
0090         DefinedInClangModule(0), Name(Name), File(File), Parent(Parent),
0091         LastSeenDIE(LastSeenDIE), LastSeenCompileUnitID(CUId) {}
0092
0093   uint32_t getQualifiedNameHash() const { return QualifiedNameHash; }
0094
0095   bool setLastSeenDIE(CompileUnit &U, const DWARFDie &Die);
0096
0097   void setHasCanonicalDIE() { HasCanonicalDIE = true; }
0098
0099   bool hasCanonicalDIE() const { return HasCanonicalDIE; }
0100
0101   uint32_t getCanonicalDIEOffset() const { return CanonicalDIEOffset; }
0102   void setCanonicalDIEOffset(uint32_t Offset) { CanonicalDIEOffset = Offset; }
0103
0104   bool isDefinedInClangModule() const { return DefinedInClangModule; }
0105   void setDefinedInClangModule(bool Val) { DefinedInClangModule = Val; }
0106
0107   uint16_t getTag() const { return Tag; }
0108
0109 private:
0110   friend DeclMapInfo;
0111
0112   unsigned QualifiedNameHash = 0;
0113   uint32_t Line = 0;
0114   uint32_t ByteSize = 0;
0115   uint16_t Tag = dwarf::DW_TAG_compile_unit;
0116   unsigned DefinedInClangModule : 1;
0117   StringRef Name;
0118   StringRef File;
0119   const DeclContext &Parent;
0120   DWARFDie LastSeenDIE;
0121   uint32_t LastSeenCompileUnitID = 0;
0122   std::atomic<uint32_t> CanonicalDIEOffset = {0};
0123   bool HasCanonicalDIE = false;
0124 };
0125
0126 /// This class gives a tree-like API to the DenseMap that stores the
0127 /// DeclContext objects. It holds the BumpPtrAllocator where these objects will
0128 /// be allocated.
0129 class DeclContextTree {
0130 public:
0131   /// Get the child of \a Context described by \a DIE in \a Unit. The
0132   /// required strings will be interned in \a StringPool.
0133   /// \returns The child DeclContext along with one bit that is set if
0134   /// this context is invalid.
0135   ///
0136   /// An invalid context means it shouldn't be considered for uniquing, but its
0137   /// not returning null, because some children of that context might be
0138   /// uniquing candidates.
0139   ///
0140   /// FIXME: The invalid bit along the return value is to emulate some
0141   /// dsymutil-classic functionality.
0142   PointerIntPair<DeclContext *, 1> getChildDeclContext(DeclContext &Context,
0143                                                        const DWARFDie &DIE,
0144                                                        CompileUnit &Unit,
0145                                                        bool InClangModule);
0146
0147   DeclContext &getRoot() { return Root; }
0148
0149 private:
0150   BumpPtrAllocator Allocator;
0151   DeclContext Root;
0152   DeclContext::Map Contexts;
0153
0154   /// Cached resolved paths from the line table.
0155   /// The key is <UniqueUnitID, FileIdx>.
0156   using ResolvedPathsMap = DenseMap<std::pair<unsigned, unsigned>, StringRef>;
0157   ResolvedPathsMap ResolvedPaths;
0158
0159   /// Helper that resolves and caches fragments of file paths.
0160   CachedPathResolver PathResolver;
0161
0162   /// String pool keeping real path bodies.
0163   NonRelocatableStringpool StringPool;
0164
0165   StringRef getResolvedPath(CompileUnit &CU, unsigned FileNum,
0166                             const DWARFDebugLine::LineTable &LineTable);
0167 };
0168
0169 /// Info type for the DenseMap storing the DeclContext pointers.
0170 struct DeclMapInfo : private DenseMapInfo<DeclContext *> {
0171   using DenseMapInfo<DeclContext *>::getEmptyKey;
0172   using DenseMapInfo<DeclContext *>::getTombstoneKey;
0173
0174   static unsigned getHashValue(const DeclContext *Ctxt) {
0175     return Ctxt->QualifiedNameHash;
0176   }
0177
0178   static bool isEqual(const DeclContext *LHS, const DeclContext *RHS) {
0179     if (RHS == getEmptyKey() || RHS == getTombstoneKey())
0180       return RHS == LHS;
0181     return LHS->QualifiedNameHash == RHS->QualifiedNameHash &&
0182            LHS->Line == RHS->Line && LHS->ByteSize == RHS->ByteSize &&
0183            LHS->Name.data() == RHS->Name.data() &&
0184            LHS->File.data() == RHS->File.data() &&
0185            LHS->Parent.QualifiedNameHash == RHS->Parent.QualifiedNameHash;
0186   }
0187 };
0188
0189 } // end of namespace classic
0190 } // end of namespace dwarf_linker
0191 } // end of namespace llvm
0192
0193 #endif // LLVM_DWARFLINKER_CLASSIC_DWARFLINKERDECLCONTEXT_H