/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/CodeGen/AccelTable.h
Line | Count | Source (jump to first uncovered line) |
1 | | //==- include/llvm/CodeGen/AccelTable.h - Accelerator Tables -----*- 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 | | // This file contains support for writing accelerator tables. |
10 | | // |
11 | | //===----------------------------------------------------------------------===// |
12 | | |
13 | | #ifndef LLVM_CODEGEN_DWARFACCELTABLE_H |
14 | | #define LLVM_CODEGEN_DWARFACCELTABLE_H |
15 | | |
16 | | #include "llvm/ADT/ArrayRef.h" |
17 | | #include "llvm/ADT/SmallVector.h" |
18 | | #include "llvm/ADT/StringMap.h" |
19 | | #include "llvm/ADT/StringRef.h" |
20 | | #include "llvm/BinaryFormat/Dwarf.h" |
21 | | #include "llvm/CodeGen/DIE.h" |
22 | | #include "llvm/CodeGen/DwarfStringPoolEntry.h" |
23 | | #include "llvm/MC/MCSymbol.h" |
24 | | #include "llvm/Support/Allocator.h" |
25 | | #include "llvm/Support/DJB.h" |
26 | | #include "llvm/Support/Debug.h" |
27 | | #include "llvm/Support/Format.h" |
28 | | #include "llvm/Support/raw_ostream.h" |
29 | | #include <cstddef> |
30 | | #include <cstdint> |
31 | | #include <vector> |
32 | | |
33 | | /// The DWARF and Apple accelerator tables are an indirect hash table optimized |
34 | | /// for null lookup rather than access to known data. The Apple accelerator |
35 | | /// tables are a precursor of the newer DWARF v5 accelerator tables. Both |
36 | | /// formats share common design ideas. |
37 | | /// |
38 | | /// The Apple accelerator table are output into an on-disk format that looks |
39 | | /// like this: |
40 | | /// |
41 | | /// .------------------. |
42 | | /// | HEADER | |
43 | | /// |------------------| |
44 | | /// | BUCKETS | |
45 | | /// |------------------| |
46 | | /// | HASHES | |
47 | | /// |------------------| |
48 | | /// | OFFSETS | |
49 | | /// |------------------| |
50 | | /// | DATA | |
51 | | /// `------------------' |
52 | | /// |
53 | | /// The header contains a magic number, version, type of hash function, |
54 | | /// the number of buckets, total number of hashes, and room for a special struct |
55 | | /// of data and the length of that struct. |
56 | | /// |
57 | | /// The buckets contain an index (e.g. 6) into the hashes array. The hashes |
58 | | /// section contains all of the 32-bit hash values in contiguous memory, and the |
59 | | /// offsets contain the offset into the data area for the particular hash. |
60 | | /// |
61 | | /// For a lookup example, we could hash a function name and take it modulo the |
62 | | /// number of buckets giving us our bucket. From there we take the bucket value |
63 | | /// as an index into the hashes table and look at each successive hash as long |
64 | | /// as the hash value is still the same modulo result (bucket value) as earlier. |
65 | | /// If we have a match we look at that same entry in the offsets table and grab |
66 | | /// the offset in the data for our final match. |
67 | | /// |
68 | | /// The DWARF v5 accelerator table consists of zero or more name indices that |
69 | | /// are output into an on-disk format that looks like this: |
70 | | /// |
71 | | /// .------------------. |
72 | | /// | HEADER | |
73 | | /// |------------------| |
74 | | /// | CU LIST | |
75 | | /// |------------------| |
76 | | /// | LOCAL TU LIST | |
77 | | /// |------------------| |
78 | | /// | FOREIGN TU LIST | |
79 | | /// |------------------| |
80 | | /// | HASH TABLE | |
81 | | /// |------------------| |
82 | | /// | NAME TABLE | |
83 | | /// |------------------| |
84 | | /// | ABBREV TABLE | |
85 | | /// |------------------| |
86 | | /// | ENTRY POOL | |
87 | | /// `------------------' |
88 | | /// |
89 | | /// For the full documentation please refer to the DWARF 5 standard. |
90 | | /// |
91 | | /// |
92 | | /// This file defines the class template AccelTable, which is represents an |
93 | | /// abstract view of an Accelerator table, without any notion of an on-disk |
94 | | /// layout. This class is parameterized by an entry type, which should derive |
95 | | /// from AccelTableData. This is the type of individual entries in the table, |
96 | | /// and it should store the data necessary to emit them. AppleAccelTableData is |
97 | | /// the base class for Apple Accelerator Table entries, which have a uniform |
98 | | /// structure based on a sequence of Atoms. There are different sub-classes |
99 | | /// derived from AppleAccelTable, which differ in the set of Atoms and how they |
100 | | /// obtain their values. |
101 | | /// |
102 | | /// An Apple Accelerator Table can be serialized by calling emitAppleAccelTable |
103 | | /// function. |
104 | | /// |
105 | | /// TODO: Add DWARF v5 emission code. |
106 | | |
107 | | namespace llvm { |
108 | | |
109 | | class AsmPrinter; |
110 | | class DwarfCompileUnit; |
111 | | class DwarfDebug; |
112 | | |
113 | | /// Interface which the different types of accelerator table data have to |
114 | | /// conform. It serves as a base class for different values of the template |
115 | | /// argument of the AccelTable class template. |
116 | | class AccelTableData { |
117 | | public: |
118 | 0 | virtual ~AccelTableData() = default; |
119 | | |
120 | 345k | bool operator<(const AccelTableData &Other) const { |
121 | 345k | return order() < Other.order(); |
122 | 345k | } |
123 | | |
124 | | // Subclasses should implement: |
125 | | // static uint32_t hash(StringRef Name); |
126 | | |
127 | | #ifndef NDEBUG |
128 | | virtual void print(raw_ostream &OS) const = 0; |
129 | | #endif |
130 | | protected: |
131 | | virtual uint64_t order() const = 0; |
132 | | }; |
133 | | |
134 | | /// A base class holding non-template-dependant functionality of the AccelTable |
135 | | /// class. Clients should not use this class directly but rather instantiate |
136 | | /// AccelTable with a type derived from AccelTableData. |
137 | | class AccelTableBase { |
138 | | public: |
139 | | using HashFn = uint32_t(StringRef); |
140 | | |
141 | | /// Represents a group of entries with identical name (and hence, hash value). |
142 | | struct HashData { |
143 | | DwarfStringPoolEntryRef Name; |
144 | | uint32_t HashValue; |
145 | | std::vector<AccelTableData *> Values; |
146 | | MCSymbol *Sym; |
147 | | |
148 | | HashData(DwarfStringPoolEntryRef Name, HashFn *Hash) |
149 | 71.8k | : Name(Name), HashValue(Hash(Name.getString())) {} |
150 | | |
151 | | #ifndef NDEBUG |
152 | | void print(raw_ostream &OS) const; |
153 | | void dump() const { print(dbgs()); } |
154 | | #endif |
155 | | }; |
156 | | using HashList = std::vector<HashData *>; |
157 | | using BucketList = std::vector<HashList>; |
158 | | |
159 | | protected: |
160 | | /// Allocator for HashData and Values. |
161 | | BumpPtrAllocator Allocator; |
162 | | |
163 | | using StringEntries = StringMap<HashData, BumpPtrAllocator &>; |
164 | | StringEntries Entries; |
165 | | |
166 | | HashFn *Hash; |
167 | | uint32_t BucketCount; |
168 | | uint32_t UniqueHashCount; |
169 | | |
170 | | HashList Hashes; |
171 | | BucketList Buckets; |
172 | | |
173 | | void computeBucketCount(); |
174 | | |
175 | 179k | AccelTableBase(HashFn *Hash) : Entries(Allocator), Hash(Hash) {} |
176 | | |
177 | | public: |
178 | | void finalize(AsmPrinter *Asm, StringRef Prefix); |
179 | 42.8k | ArrayRef<HashList> getBuckets() const { return Buckets; } |
180 | 10.6k | uint32_t getBucketCount() const { return BucketCount; } |
181 | 10.6k | uint32_t getUniqueHashCount() const { return UniqueHashCount; } |
182 | 63 | uint32_t getUniqueNameCount() const { return Entries.size(); } |
183 | | |
184 | | #ifndef NDEBUG |
185 | | void print(raw_ostream &OS) const; |
186 | | void dump() const { print(dbgs()); } |
187 | | #endif |
188 | | |
189 | | AccelTableBase(const AccelTableBase &) = delete; |
190 | | void operator=(const AccelTableBase &) = delete; |
191 | | }; |
192 | | |
193 | | /// This class holds an abstract representation of an Accelerator Table, |
194 | | /// consisting of a sequence of buckets, each bucket containint a sequence of |
195 | | /// HashData entries. The class is parameterized by the type of entries it |
196 | | /// holds. The type template parameter also defines the hash function to use for |
197 | | /// hashing names. |
198 | | template <typename DataT> class AccelTable : public AccelTableBase { |
199 | | public: |
200 | 178k | AccelTable() : AccelTableBase(DataT::hash) {} llvm::AccelTable<llvm::DWARF5AccelTableData>::AccelTable() Line | Count | Source | 200 | 35.7k | AccelTable() : AccelTableBase(DataT::hash) {} |
llvm::AccelTable<llvm::AppleAccelTableOffsetData>::AccelTable() Line | Count | Source | 200 | 107k | AccelTable() : AccelTableBase(DataT::hash) {} |
llvm::AccelTable<llvm::AppleAccelTableTypeData>::AccelTable() Line | Count | Source | 200 | 35.7k | AccelTable() : AccelTableBase(DataT::hash) {} |
|
201 | | |
202 | | template <typename... Types> |
203 | | void addName(DwarfStringPoolEntryRef Name, Types &&... Args); |
204 | | }; |
205 | | |
206 | | template <typename AccelTableDataT> |
207 | | template <typename... Types> |
208 | | void AccelTable<AccelTableDataT>::addName(DwarfStringPoolEntryRef Name, |
209 | 315k | Types &&... Args) { |
210 | 315k | assert(Buckets.empty() && "Already finalized!"); |
211 | 315k | // If the string is in the list already then add this die to the list |
212 | 315k | // otherwise add a new one. |
213 | 315k | auto Iter = Entries.try_emplace(Name.getString(), Name, Hash).first; |
214 | 315k | assert(Iter->second.Name == Name); |
215 | 315k | Iter->second.Values.push_back( |
216 | 315k | new (Allocator) AccelTableDataT(std::forward<Types>(Args)...)); |
217 | 315k | } void llvm::AccelTable<llvm::AppleAccelTableOffsetData>::addName<llvm::DIE const&>(llvm::DwarfStringPoolEntryRef, llvm::DIE const&&&) Line | Count | Source | 209 | 314k | Types &&... Args) { | 210 | 314k | assert(Buckets.empty() && "Already finalized!"); | 211 | 314k | // If the string is in the list already then add this die to the list | 212 | 314k | // otherwise add a new one. | 213 | 314k | auto Iter = Entries.try_emplace(Name.getString(), Name, Hash).first; | 214 | 314k | assert(Iter->second.Name == Name); | 215 | 314k | Iter->second.Values.push_back( | 216 | 314k | new (Allocator) AccelTableDataT(std::forward<Types>(Args)...)); | 217 | 314k | } |
void llvm::AccelTable<llvm::DWARF5AccelTableData>::addName<llvm::DIE const&>(llvm::DwarfStringPoolEntryRef, llvm::DIE const&&&) Line | Count | Source | 209 | 456 | Types &&... Args) { | 210 | 456 | assert(Buckets.empty() && "Already finalized!"); | 211 | 456 | // If the string is in the list already then add this die to the list | 212 | 456 | // otherwise add a new one. | 213 | 456 | auto Iter = Entries.try_emplace(Name.getString(), Name, Hash).first; | 214 | 456 | assert(Iter->second.Name == Name); | 215 | 456 | Iter->second.Values.push_back( | 216 | 456 | new (Allocator) AccelTableDataT(std::forward<Types>(Args)...)); | 217 | 456 | } |
void llvm::AccelTable<llvm::AppleAccelTableTypeData>::addName<llvm::DIE const&>(llvm::DwarfStringPoolEntryRef, llvm::DIE const&&&) Line | Count | Source | 209 | 820 | Types &&... Args) { | 210 | 820 | assert(Buckets.empty() && "Already finalized!"); | 211 | 820 | // If the string is in the list already then add this die to the list | 212 | 820 | // otherwise add a new one. | 213 | 820 | auto Iter = Entries.try_emplace(Name.getString(), Name, Hash).first; | 214 | 820 | assert(Iter->second.Name == Name); | 215 | 820 | Iter->second.Values.push_back( | 216 | 820 | new (Allocator) AccelTableDataT(std::forward<Types>(Args)...)); | 217 | 820 | } |
|
218 | | |
219 | | /// A base class for different implementations of Data classes for Apple |
220 | | /// Accelerator Tables. The columns in the table are defined by the static Atoms |
221 | | /// variable defined on the subclasses. |
222 | | class AppleAccelTableData : public AccelTableData { |
223 | | public: |
224 | | /// An Atom defines the form of the data in an Apple accelerator table. |
225 | | /// Conceptually it is a column in the accelerator consisting of a type and a |
226 | | /// specification of the form of its data. |
227 | | struct Atom { |
228 | | /// Atom Type. |
229 | | const uint16_t Type; |
230 | | /// DWARF Form. |
231 | | const uint16_t Form; |
232 | | |
233 | 0 | constexpr Atom(uint16_t Type, uint16_t Form) : Type(Type), Form(Form) {} |
234 | | |
235 | | #ifndef NDEBUG |
236 | | void print(raw_ostream &OS) const; |
237 | | void dump() const { print(dbgs()); } |
238 | | #endif |
239 | | }; |
240 | | // Subclasses should define: |
241 | | // static constexpr Atom Atoms[]; |
242 | | |
243 | | virtual void emit(AsmPrinter *Asm) const = 0; |
244 | | |
245 | 71.3k | static uint32_t hash(StringRef Buffer) { return djbHash(Buffer); } |
246 | | }; |
247 | | |
248 | | /// The Data class implementation for DWARF v5 accelerator table. Unlike the |
249 | | /// Apple Data classes, this class is just a DIE wrapper, and does not know to |
250 | | /// serialize itself. The complete serialization logic is in the |
251 | | /// emitDWARF5AccelTable function. |
252 | | class DWARF5AccelTableData : public AccelTableData { |
253 | | public: |
254 | 448 | static uint32_t hash(StringRef Name) { return caseFoldingDjbHash(Name); } |
255 | | |
256 | 456 | DWARF5AccelTableData(const DIE &Die) : Die(Die) {} |
257 | | |
258 | | #ifndef NDEBUG |
259 | | void print(raw_ostream &OS) const override; |
260 | | #endif |
261 | | |
262 | 275 | const DIE &getDie() const { return Die; } |
263 | 456 | uint64_t getDieOffset() const { return Die.getOffset(); } |
264 | 912 | unsigned getDieTag() const { return Die.getTag(); } |
265 | | |
266 | | protected: |
267 | | const DIE &Die; |
268 | | |
269 | 22 | uint64_t order() const override { return Die.getOffset(); } |
270 | | }; |
271 | | |
272 | | class DWARF5AccelTableStaticData : public AccelTableData { |
273 | | public: |
274 | | static uint32_t hash(StringRef Name) { return caseFoldingDjbHash(Name); } |
275 | | |
276 | | DWARF5AccelTableStaticData(uint64_t DieOffset, unsigned DieTag, |
277 | | unsigned CUIndex) |
278 | | : DieOffset(DieOffset), DieTag(DieTag), CUIndex(CUIndex) {} |
279 | | |
280 | | #ifndef NDEBUG |
281 | | void print(raw_ostream &OS) const override; |
282 | | #endif |
283 | | |
284 | 24 | uint64_t getDieOffset() const { return DieOffset; } |
285 | 48 | unsigned getDieTag() const { return DieTag; } |
286 | | unsigned getCUIndex() const { return CUIndex; } |
287 | | |
288 | | protected: |
289 | | uint64_t DieOffset; |
290 | | unsigned DieTag; |
291 | | unsigned CUIndex; |
292 | | |
293 | | uint64_t order() const override { return DieOffset; } |
294 | | }; |
295 | | |
296 | | void emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents, |
297 | | StringRef Prefix, const MCSymbol *SecBegin, |
298 | | ArrayRef<AppleAccelTableData::Atom> Atoms); |
299 | | |
300 | | /// Emit an Apple Accelerator Table consisting of entries in the specified |
301 | | /// AccelTable. The DataT template parameter should be derived from |
302 | | /// AppleAccelTableData. |
303 | | template <typename DataT> |
304 | | void emitAppleAccelTable(AsmPrinter *Asm, AccelTable<DataT> &Contents, |
305 | 10.2k | StringRef Prefix, const MCSymbol *SecBegin) { |
306 | 10.2k | static_assert(std::is_convertible<DataT *, AppleAccelTableData *>::value, ""); |
307 | 10.2k | emitAppleAccelTableImpl(Asm, Contents, Prefix, SecBegin, DataT::Atoms); |
308 | 10.2k | } void llvm::emitAppleAccelTable<llvm::AppleAccelTableOffsetData>(llvm::AsmPrinter*, llvm::AccelTable<llvm::AppleAccelTableOffsetData>&, llvm::StringRef, llvm::MCSymbol const*) Line | Count | Source | 305 | 7.67k | StringRef Prefix, const MCSymbol *SecBegin) { | 306 | 7.67k | static_assert(std::is_convertible<DataT *, AppleAccelTableData *>::value, ""); | 307 | 7.67k | emitAppleAccelTableImpl(Asm, Contents, Prefix, SecBegin, DataT::Atoms); | 308 | 7.67k | } |
void llvm::emitAppleAccelTable<llvm::AppleAccelTableTypeData>(llvm::AsmPrinter*, llvm::AccelTable<llvm::AppleAccelTableTypeData>&, llvm::StringRef, llvm::MCSymbol const*) Line | Count | Source | 305 | 2.55k | StringRef Prefix, const MCSymbol *SecBegin) { | 306 | 2.55k | static_assert(std::is_convertible<DataT *, AppleAccelTableData *>::value, ""); | 307 | 2.55k | emitAppleAccelTableImpl(Asm, Contents, Prefix, SecBegin, DataT::Atoms); | 308 | 2.55k | } |
|
309 | | |
310 | | void emitDWARF5AccelTable(AsmPrinter *Asm, |
311 | | AccelTable<DWARF5AccelTableData> &Contents, |
312 | | const DwarfDebug &DD, |
313 | | ArrayRef<std::unique_ptr<DwarfCompileUnit>> CUs); |
314 | | |
315 | | void emitDWARF5AccelTable( |
316 | | AsmPrinter *Asm, AccelTable<DWARF5AccelTableStaticData> &Contents, |
317 | | ArrayRef<MCSymbol *> CUs, |
318 | | llvm::function_ref<unsigned(const DWARF5AccelTableStaticData &)> |
319 | | getCUIndexForEntry); |
320 | | |
321 | | /// Accelerator table data implementation for simple Apple accelerator tables |
322 | | /// with just a DIE reference. |
323 | | class AppleAccelTableOffsetData : public AppleAccelTableData { |
324 | | public: |
325 | 315k | AppleAccelTableOffsetData(const DIE &D) : Die(D) {} |
326 | | |
327 | | void emit(AsmPrinter *Asm) const override; |
328 | | |
329 | | static constexpr Atom Atoms[] = { |
330 | | Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)}; |
331 | | |
332 | | #ifndef NDEBUG |
333 | | void print(raw_ostream &OS) const override; |
334 | | #endif |
335 | | protected: |
336 | 690k | uint64_t order() const override { return Die.getOffset(); } |
337 | | |
338 | | const DIE &Die; |
339 | | }; |
340 | | |
341 | | /// Accelerator table data implementation for Apple type accelerator tables. |
342 | | class AppleAccelTableTypeData : public AppleAccelTableOffsetData { |
343 | | public: |
344 | 820 | AppleAccelTableTypeData(const DIE &D) : AppleAccelTableOffsetData(D) {} |
345 | | |
346 | | void emit(AsmPrinter *Asm) const override; |
347 | | |
348 | | static constexpr Atom Atoms[] = { |
349 | | Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4), |
350 | | Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2), |
351 | | Atom(dwarf::DW_ATOM_type_flags, dwarf::DW_FORM_data1)}; |
352 | | |
353 | | #ifndef NDEBUG |
354 | | void print(raw_ostream &OS) const override; |
355 | | #endif |
356 | | }; |
357 | | |
358 | | /// Accelerator table data implementation for simple Apple accelerator tables |
359 | | /// with a DIE offset but no actual DIE pointer. |
360 | | class AppleAccelTableStaticOffsetData : public AppleAccelTableData { |
361 | | public: |
362 | | AppleAccelTableStaticOffsetData(uint32_t Offset) : Offset(Offset) {} |
363 | | |
364 | | void emit(AsmPrinter *Asm) const override; |
365 | | |
366 | | static constexpr Atom Atoms[] = { |
367 | | Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)}; |
368 | | |
369 | | #ifndef NDEBUG |
370 | | void print(raw_ostream &OS) const override; |
371 | | #endif |
372 | | protected: |
373 | 142 | uint64_t order() const override { return Offset; } |
374 | | |
375 | | uint32_t Offset; |
376 | | }; |
377 | | |
378 | | /// Accelerator table data implementation for type accelerator tables with |
379 | | /// a DIE offset but no actual DIE pointer. |
380 | | class AppleAccelTableStaticTypeData : public AppleAccelTableStaticOffsetData { |
381 | | public: |
382 | | AppleAccelTableStaticTypeData(uint32_t Offset, uint16_t Tag, |
383 | | bool ObjCClassIsImplementation, |
384 | | uint32_t QualifiedNameHash) |
385 | | : AppleAccelTableStaticOffsetData(Offset), |
386 | | QualifiedNameHash(QualifiedNameHash), Tag(Tag), |
387 | | ObjCClassIsImplementation(ObjCClassIsImplementation) {} |
388 | | |
389 | | void emit(AsmPrinter *Asm) const override; |
390 | | |
391 | | static constexpr Atom Atoms[] = { |
392 | | Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4), |
393 | | Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2), |
394 | | Atom(5, dwarf::DW_FORM_data1), Atom(6, dwarf::DW_FORM_data4)}; |
395 | | |
396 | | #ifndef NDEBUG |
397 | | void print(raw_ostream &OS) const override; |
398 | | #endif |
399 | | protected: |
400 | 222 | uint64_t order() const override { return Offset; } |
401 | | |
402 | | uint32_t QualifiedNameHash; |
403 | | uint16_t Tag; |
404 | | bool ObjCClassIsImplementation; |
405 | | }; |
406 | | |
407 | | } // end namespace llvm |
408 | | |
409 | | #endif // LLVM_CODEGEN_DWARFACCELTABLE_H |