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