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