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