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 21namespace llvm { 22 23struct 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. 29class CachedPathResolver { 30public: 31 /// Resolve a path by calling realpath and cache its result. The returned 32 /// StringRef is interned in the given \p 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 51private: 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. 73class DeclContext { 74public: 75 using Map = DenseSet<DeclContext *, DeclMapInfo>; 76 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) 82 : QualifiedNameHash(Hash), Line(Line), ByteSize(ByteSize), Tag(Tag), 83 DefinedInClangModule(0), Name(Name), File(File), Parent(Parent), 84 LastSeenDIE(LastSeenDIE), LastSeenCompileUnitID(CUId) {} 85 86 uint32_t getQualifiedNameHash() const { return QualifiedNameHash; } 87 88 bool setLastSeenDIE(CompileUnit &U, const DWARFDie &Die); 89 90 uint32_t getCanonicalDIEOffset() const { return CanonicalDIEOffset; } 91 void setCanonicalDIEOffset(uint32_t Offset) { CanonicalDIEOffset = Offset; } 92 93 bool isDefinedInClangModule() const { return DefinedInClangModule; } 94 void setDefinedInClangModule(bool Val) { DefinedInClangModule = Val; } 95 96 uint16_t getTag() const { return Tag; } 97 StringRef getName() const { return Name; } 98 99private: 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. 118class DeclContextTree { 119public: 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 136 DeclContext &getRoot() { return Root; } 137 138private: 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. 148struct DeclMapInfo : private DenseMapInfo<DeclContext *> { 149 using DenseMapInfo<DeclContext *>::getEmptyKey; 150 using DenseMapInfo<DeclContext *>::getTombstoneKey; 151 152 static unsigned getHashValue(const DeclContext *Ctxt) { 153 return Ctxt->QualifiedNameHash; 154 } 155 156 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