1 //===- DWARFLinkerDeclContext.h ---------------------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef LLVM_DWARFLINKER_DWARFLINKERDECLCONTEXT_H 10 #define LLVM_DWARFLINKER_DWARFLINKERDECLCONTEXT_H 11 12 #include "llvm/ADT/DenseMap.h" 13 #include "llvm/ADT/DenseMapInfo.h" 14 #include "llvm/ADT/DenseSet.h" 15 #include "llvm/ADT/StringRef.h" 16 #include "llvm/CodeGen/NonRelocatableStringpool.h" 17 #include "llvm/DWARFLinker/DWARFLinkerCompileUnit.h" 18 #include "llvm/DebugInfo/DWARF/DWARFDebugLine.h" 19 #include "llvm/DebugInfo/DWARF/DWARFDie.h" 20 #include "llvm/Support/FileSystem.h" 21 #include "llvm/Support/Path.h" 22 23 namespace llvm { 24 25 struct DeclMapInfo; 26 27 /// Small helper that resolves and caches file paths. This helps reduce the 28 /// number of calls to realpath which is expensive. We assume the input are 29 /// files, and cache the realpath of their parent. This way we can quickly 30 /// resolve different files under the same path. 31 class CachedPathResolver { 32 public: 33 /// Resolve a path by calling realpath and cache its result. The returned 34 /// StringRef is interned in the given \p StringPool. resolve(const std::string & Path,NonRelocatableStringpool & StringPool)35 StringRef resolve(const std::string &Path, 36 NonRelocatableStringpool &StringPool) { 37 StringRef FileName = sys::path::filename(Path); 38 StringRef ParentPath = sys::path::parent_path(Path); 39 40 // If the ParentPath has not yet been resolved, resolve and cache it for 41 // future look-ups. 42 if (!ResolvedPaths.count(ParentPath)) { 43 SmallString<256> RealPath; 44 sys::fs::real_path(ParentPath, RealPath); 45 ResolvedPaths.insert( 46 {ParentPath, std::string(RealPath.c_str(), RealPath.size())}); 47 } 48 49 // Join the file name again with the resolved path. 50 SmallString<256> ResolvedPath(ResolvedPaths[ParentPath]); 51 sys::path::append(ResolvedPath, FileName); 52 return StringPool.internString(ResolvedPath); 53 } 54 55 private: 56 StringMap<std::string> ResolvedPaths; 57 }; 58 59 /// A DeclContext is a named program scope that is used for ODR uniquing of 60 /// types. 61 /// 62 /// The set of DeclContext for the ODR-subject parts of a Dwarf link is 63 /// expanded (and uniqued) with each new object file processed. We need to 64 /// determine the context of each DIE in an linked object file to see if the 65 /// corresponding type has already been emitted. 66 /// 67 /// The contexts are conceptually organized as a tree (eg. a function scope is 68 /// contained in a namespace scope that contains other scopes), but 69 /// storing/accessing them in an actual tree is too inefficient: we need to be 70 /// able to very quickly query a context for a given child context by name. 71 /// Storing a StringMap in each DeclContext would be too space inefficient. 72 /// 73 /// The solution here is to give each DeclContext a link to its parent (this 74 /// allows to walk up the tree), but to query the existence of a specific 75 /// DeclContext using a separate DenseMap keyed on the hash of the fully 76 /// qualified name of the context. 77 class DeclContext { 78 public: 79 using Map = DenseSet<DeclContext *, DeclMapInfo>; 80 DeclContext()81 DeclContext() : DefinedInClangModule(0), Parent(*this) {} 82 83 DeclContext(unsigned Hash, uint32_t Line, uint32_t ByteSize, uint16_t Tag, 84 StringRef Name, StringRef File, const DeclContext &Parent, 85 DWARFDie LastSeenDIE = DWARFDie(), unsigned CUId = 0) QualifiedNameHash(Hash)86 : QualifiedNameHash(Hash), Line(Line), ByteSize(ByteSize), Tag(Tag), 87 DefinedInClangModule(0), Name(Name), File(File), Parent(Parent), 88 LastSeenDIE(LastSeenDIE), LastSeenCompileUnitID(CUId) {} 89 getQualifiedNameHash()90 uint32_t getQualifiedNameHash() const { return QualifiedNameHash; } 91 92 bool setLastSeenDIE(CompileUnit &U, const DWARFDie &Die); 93 getCanonicalDIEOffset()94 uint32_t getCanonicalDIEOffset() const { return CanonicalDIEOffset; } setCanonicalDIEOffset(uint32_t Offset)95 void setCanonicalDIEOffset(uint32_t Offset) { CanonicalDIEOffset = Offset; } 96 isDefinedInClangModule()97 bool isDefinedInClangModule() const { return DefinedInClangModule; } setDefinedInClangModule(bool Val)98 void setDefinedInClangModule(bool Val) { DefinedInClangModule = Val; } 99 getTag()100 uint16_t getTag() const { return Tag; } 101 102 private: 103 friend DeclMapInfo; 104 105 unsigned QualifiedNameHash = 0; 106 uint32_t Line = 0; 107 uint32_t ByteSize = 0; 108 uint16_t Tag = dwarf::DW_TAG_compile_unit; 109 unsigned DefinedInClangModule : 1; 110 StringRef Name; 111 StringRef File; 112 const DeclContext &Parent; 113 DWARFDie LastSeenDIE; 114 uint32_t LastSeenCompileUnitID = 0; 115 uint32_t CanonicalDIEOffset = 0; 116 }; 117 118 /// This class gives a tree-like API to the DenseMap that stores the 119 /// DeclContext objects. It holds the BumpPtrAllocator where these objects will 120 /// be allocated. 121 class DeclContextTree { 122 public: 123 /// Get the child of \a Context described by \a DIE in \a Unit. The 124 /// required strings will be interned in \a StringPool. 125 /// \returns The child DeclContext along with one bit that is set if 126 /// this context is invalid. 127 /// 128 /// An invalid context means it shouldn't be considered for uniquing, but its 129 /// not returning null, because some children of that context might be 130 /// uniquing candidates. 131 /// 132 /// FIXME: The invalid bit along the return value is to emulate some 133 /// dsymutil-classic functionality. 134 PointerIntPair<DeclContext *, 1> getChildDeclContext(DeclContext &Context, 135 const DWARFDie &DIE, 136 CompileUnit &Unit, 137 bool InClangModule); 138 getRoot()139 DeclContext &getRoot() { return Root; } 140 141 private: 142 BumpPtrAllocator Allocator; 143 DeclContext Root; 144 DeclContext::Map Contexts; 145 146 /// Cached resolved paths from the line table. 147 /// The key is <UniqueUnitID, FileIdx>. 148 using ResolvedPathsMap = DenseMap<std::pair<unsigned, unsigned>, StringRef>; 149 ResolvedPathsMap ResolvedPaths; 150 151 /// Helper that resolves and caches fragments of file paths. 152 CachedPathResolver PathResolver; 153 154 /// String pool keeping real path bodies. 155 NonRelocatableStringpool StringPool; 156 157 StringRef getResolvedPath(CompileUnit &CU, unsigned FileNum, 158 const DWARFDebugLine::LineTable &LineTable); 159 }; 160 161 /// Info type for the DenseMap storing the DeclContext pointers. 162 struct DeclMapInfo : private DenseMapInfo<DeclContext *> { 163 using DenseMapInfo<DeclContext *>::getEmptyKey; 164 using DenseMapInfo<DeclContext *>::getTombstoneKey; 165 getHashValueDeclMapInfo166 static unsigned getHashValue(const DeclContext *Ctxt) { 167 return Ctxt->QualifiedNameHash; 168 } 169 isEqualDeclMapInfo170 static bool isEqual(const DeclContext *LHS, const DeclContext *RHS) { 171 if (RHS == getEmptyKey() || RHS == getTombstoneKey()) 172 return RHS == LHS; 173 return LHS->QualifiedNameHash == RHS->QualifiedNameHash && 174 LHS->Line == RHS->Line && LHS->ByteSize == RHS->ByteSize && 175 LHS->Name.data() == RHS->Name.data() && 176 LHS->File.data() == RHS->File.data() && 177 LHS->Parent.QualifiedNameHash == RHS->Parent.QualifiedNameHash; 178 } 179 }; 180 181 } // end namespace llvm 182 183 #endif // LLVM_DWARFLINKER_DWARFLINKERDECLCONTEXT_H 184