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
23namespace llvm {
24namespace dwarf_linker {
25namespace classic {
26
27class CompileUnit;
28struct 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.
34class CachedPathResolver {
35public:
36 /// Resolve a path by calling realpath and cache its result. The returned
37 /// StringRef is interned in the given \p StringPool.
38 StringRef resolve(const std::string &Path,
39 NonRelocatableStringpool &StringPool) {
40 StringRef FileName = sys::path::filename(path: Path);
41 StringRef ParentPath = sys::path::parent_path(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(Key: ParentPath)) {
46 SmallString<256> RealPath;
47 sys::fs::real_path(path: ParentPath, output&: RealPath);
48 ResolvedPaths.insert(
49 KV: {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(path&: ResolvedPath, a: FileName);
55 return StringPool.internString(S: ResolvedPath);
56 }
57
58private:
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.
80class DeclContext {
81public:
82 using Map = DenseSet<DeclContext *, DeclMapInfo>;
83
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)
89 : QualifiedNameHash(Hash), Line(Line), ByteSize(ByteSize), Tag(Tag),
90 DefinedInClangModule(0), Name(Name), File(File), Parent(Parent),
91 LastSeenDIE(LastSeenDIE), LastSeenCompileUnitID(CUId) {}
92
93 uint32_t getQualifiedNameHash() const { return QualifiedNameHash; }
94
95 bool setLastSeenDIE(CompileUnit &U, const DWARFDie &Die);
96
97 void setHasCanonicalDIE() { HasCanonicalDIE = true; }
98
99 bool hasCanonicalDIE() const { return HasCanonicalDIE; }
100
101 uint32_t getCanonicalDIEOffset() const { return CanonicalDIEOffset; }
102 void setCanonicalDIEOffset(uint32_t Offset) { CanonicalDIEOffset = Offset; }
103
104 bool isDefinedInClangModule() const { return DefinedInClangModule; }
105 void setDefinedInClangModule(bool Val) { DefinedInClangModule = Val; }
106
107 uint16_t getTag() const { return Tag; }
108
109private:
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.
129class DeclContextTree {
130public:
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
147 DeclContext &getRoot() { return Root; }
148
149private:
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.
170struct DeclMapInfo : private DenseMapInfo<DeclContext *> {
171 using DenseMapInfo<DeclContext *>::getEmptyKey;
172 using DenseMapInfo<DeclContext *>::getTombstoneKey;
173
174 static unsigned getHashValue(const DeclContext *Ctxt) {
175 return Ctxt->QualifiedNameHash;
176 }
177
178 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