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