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 /// \file
9 /// This file contains support for writing accelerator tables.
10 ///
11 //===----------------------------------------------------------------------===//
12
13 #ifndef LLVM_CODEGEN_ACCELTABLE_H
14 #define LLVM_CODEGEN_ACCELTABLE_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 /// \file
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 namespace llvm {
107
108 class AsmPrinter;
109 class DwarfCompileUnit;
110 class DwarfDebug;
111
112 /// Interface which the different types of accelerator table data have to
113 /// conform. It serves as a base class for different values of the template
114 /// argument of the AccelTable class template.
115 class AccelTableData {
116 public:
117 virtual ~AccelTableData() = default;
118
119 bool operator<(const AccelTableData &Other) const {
120 return order() < Other.order();
121 }
122
123 // Subclasses should implement:
124 // static uint32_t hash(StringRef Name);
125
126 #ifndef NDEBUG
127 virtual void print(raw_ostream &OS) const = 0;
128 #endif
129 protected:
130 virtual uint64_t order() const = 0;
131 };
132
133 /// A base class holding non-template-dependant functionality of the AccelTable
134 /// class. Clients should not use this class directly but rather instantiate
135 /// AccelTable with a type derived from AccelTableData.
136 class AccelTableBase {
137 public:
138 using HashFn = uint32_t(StringRef);
139
140 /// Represents a group of entries with identical name (and hence, hash value).
141 struct HashData {
142 DwarfStringPoolEntryRef Name;
143 uint32_t HashValue;
144 std::vector<AccelTableData *> Values;
145 MCSymbol *Sym;
146
HashDataHashData147 HashData(DwarfStringPoolEntryRef Name, HashFn *Hash)
148 : Name(Name), HashValue(Hash(Name.getString())) {}
149
150 #ifndef NDEBUG
151 void print(raw_ostream &OS) const;
dumpHashData152 void dump() const { print(dbgs()); }
153 #endif
154 };
155 using HashList = std::vector<HashData *>;
156 using BucketList = std::vector<HashList>;
157
158 protected:
159 /// Allocator for HashData and Values.
160 BumpPtrAllocator Allocator;
161
162 using StringEntries = StringMap<HashData, BumpPtrAllocator &>;
163 StringEntries Entries;
164
165 HashFn *Hash;
166 uint32_t BucketCount;
167 uint32_t UniqueHashCount;
168
169 HashList Hashes;
170 BucketList Buckets;
171
172 void computeBucketCount();
173
AccelTableBase(HashFn * Hash)174 AccelTableBase(HashFn *Hash) : Entries(Allocator), Hash(Hash) {}
175
176 public:
177 void finalize(AsmPrinter *Asm, StringRef Prefix);
getBuckets()178 ArrayRef<HashList> getBuckets() const { return Buckets; }
getBucketCount()179 uint32_t getBucketCount() const { return BucketCount; }
getUniqueHashCount()180 uint32_t getUniqueHashCount() const { return UniqueHashCount; }
getUniqueNameCount()181 uint32_t getUniqueNameCount() const { return Entries.size(); }
182
183 #ifndef NDEBUG
184 void print(raw_ostream &OS) const;
dump()185 void dump() const { print(dbgs()); }
186 #endif
187
188 AccelTableBase(const AccelTableBase &) = delete;
189 void operator=(const AccelTableBase &) = delete;
190 };
191
192 /// This class holds an abstract representation of an Accelerator Table,
193 /// consisting of a sequence of buckets, each bucket containint a sequence of
194 /// HashData entries. The class is parameterized by the type of entries it
195 /// holds. The type template parameter also defines the hash function to use for
196 /// hashing names.
197 template <typename DataT> class AccelTable : public AccelTableBase {
198 public:
AccelTable()199 AccelTable() : AccelTableBase(DataT::hash) {}
200
201 template <typename... Types>
202 void addName(DwarfStringPoolEntryRef Name, Types &&... Args);
203 };
204
205 template <typename AccelTableDataT>
206 template <typename... Types>
addName(DwarfStringPoolEntryRef Name,Types &&...Args)207 void AccelTable<AccelTableDataT>::addName(DwarfStringPoolEntryRef Name,
208 Types &&... Args) {
209 assert(Buckets.empty() && "Already finalized!");
210 // If the string is in the list already then add this die to the list
211 // otherwise add a new one.
212 auto Iter = Entries.try_emplace(Name.getString(), Name, Hash).first;
213 assert(Iter->second.Name == Name);
214 Iter->second.Values.push_back(
215 new (Allocator) AccelTableDataT(std::forward<Types>(Args)...));
216 }
217
218 /// A base class for different implementations of Data classes for Apple
219 /// Accelerator Tables. The columns in the table are defined by the static Atoms
220 /// variable defined on the subclasses.
221 class AppleAccelTableData : public AccelTableData {
222 public:
223 /// An Atom defines the form of the data in an Apple accelerator table.
224 /// Conceptually it is a column in the accelerator consisting of a type and a
225 /// specification of the form of its data.
226 struct Atom {
227 /// Atom Type.
228 const uint16_t Type;
229 /// DWARF Form.
230 const uint16_t Form;
231
AtomAtom232 constexpr Atom(uint16_t Type, uint16_t Form) : Type(Type), Form(Form) {}
233
234 #ifndef NDEBUG
235 void print(raw_ostream &OS) const;
dumpAtom236 void dump() const { print(dbgs()); }
237 #endif
238 };
239 // Subclasses should define:
240 // static constexpr Atom Atoms[];
241
242 virtual void emit(AsmPrinter *Asm) const = 0;
243
hash(StringRef Buffer)244 static uint32_t hash(StringRef Buffer) { return djbHash(Buffer); }
245 };
246
247 /// The Data class implementation for DWARF v5 accelerator table. Unlike the
248 /// Apple Data classes, this class is just a DIE wrapper, and does not know to
249 /// serialize itself. The complete serialization logic is in the
250 /// emitDWARF5AccelTable function.
251 class DWARF5AccelTableData : public AccelTableData {
252 public:
hash(StringRef Name)253 static uint32_t hash(StringRef Name) { return caseFoldingDjbHash(Name); }
254
DWARF5AccelTableData(const DIE & Die)255 DWARF5AccelTableData(const DIE &Die) : Die(Die) {}
256
257 #ifndef NDEBUG
258 void print(raw_ostream &OS) const override;
259 #endif
260
getDie()261 const DIE &getDie() const { return Die; }
getDieOffset()262 uint64_t getDieOffset() const { return Die.getOffset(); }
getDieTag()263 unsigned getDieTag() const { return Die.getTag(); }
264
265 protected:
266 const DIE &Die;
267
order()268 uint64_t order() const override { return Die.getOffset(); }
269 };
270
271 class DWARF5AccelTableStaticData : public AccelTableData {
272 public:
hash(StringRef Name)273 static uint32_t hash(StringRef Name) { return caseFoldingDjbHash(Name); }
274
DWARF5AccelTableStaticData(uint64_t DieOffset,unsigned DieTag,unsigned CUIndex)275 DWARF5AccelTableStaticData(uint64_t DieOffset, unsigned DieTag,
276 unsigned CUIndex)
277 : DieOffset(DieOffset), DieTag(DieTag), CUIndex(CUIndex) {}
278
279 #ifndef NDEBUG
280 void print(raw_ostream &OS) const override;
281 #endif
282
getDieOffset()283 uint64_t getDieOffset() const { return DieOffset; }
getDieTag()284 unsigned getDieTag() const { return DieTag; }
getCUIndex()285 unsigned getCUIndex() const { return CUIndex; }
286
287 protected:
288 uint64_t DieOffset;
289 unsigned DieTag;
290 unsigned CUIndex;
291
order()292 uint64_t order() const override { return DieOffset; }
293 };
294
295 void emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents,
296 StringRef Prefix, const MCSymbol *SecBegin,
297 ArrayRef<AppleAccelTableData::Atom> Atoms);
298
299 /// Emit an Apple Accelerator Table consisting of entries in the specified
300 /// AccelTable. The DataT template parameter should be derived from
301 /// AppleAccelTableData.
302 template <typename DataT>
emitAppleAccelTable(AsmPrinter * Asm,AccelTable<DataT> & Contents,StringRef Prefix,const MCSymbol * SecBegin)303 void emitAppleAccelTable(AsmPrinter *Asm, AccelTable<DataT> &Contents,
304 StringRef Prefix, const MCSymbol *SecBegin) {
305 static_assert(std::is_convertible<DataT *, AppleAccelTableData *>::value, "");
306 emitAppleAccelTableImpl(Asm, Contents, Prefix, SecBegin, DataT::Atoms);
307 }
308
309 void emitDWARF5AccelTable(AsmPrinter *Asm,
310 AccelTable<DWARF5AccelTableData> &Contents,
311 const DwarfDebug &DD,
312 ArrayRef<std::unique_ptr<DwarfCompileUnit>> CUs);
313
314 void emitDWARF5AccelTable(
315 AsmPrinter *Asm, AccelTable<DWARF5AccelTableStaticData> &Contents,
316 ArrayRef<MCSymbol *> CUs,
317 llvm::function_ref<unsigned(const DWARF5AccelTableStaticData &)>
318 getCUIndexForEntry);
319
320 /// Accelerator table data implementation for simple Apple accelerator tables
321 /// with just a DIE reference.
322 class AppleAccelTableOffsetData : public AppleAccelTableData {
323 public:
AppleAccelTableOffsetData(const DIE & D)324 AppleAccelTableOffsetData(const DIE &D) : Die(D) {}
325
326 void emit(AsmPrinter *Asm) const override;
327
328 static constexpr Atom Atoms[] = {
329 Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
330
331 #ifndef NDEBUG
332 void print(raw_ostream &OS) const override;
333 #endif
334 protected:
order()335 uint64_t order() const override { return Die.getOffset(); }
336
337 const DIE &Die;
338 };
339
340 /// Accelerator table data implementation for Apple type accelerator tables.
341 class AppleAccelTableTypeData : public AppleAccelTableOffsetData {
342 public:
AppleAccelTableTypeData(const DIE & D)343 AppleAccelTableTypeData(const DIE &D) : AppleAccelTableOffsetData(D) {}
344
345 void emit(AsmPrinter *Asm) const override;
346
347 static constexpr Atom Atoms[] = {
348 Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
349 Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
350 Atom(dwarf::DW_ATOM_type_flags, dwarf::DW_FORM_data1)};
351
352 #ifndef NDEBUG
353 void print(raw_ostream &OS) const override;
354 #endif
355 };
356
357 /// Accelerator table data implementation for simple Apple accelerator tables
358 /// with a DIE offset but no actual DIE pointer.
359 class AppleAccelTableStaticOffsetData : public AppleAccelTableData {
360 public:
AppleAccelTableStaticOffsetData(uint32_t Offset)361 AppleAccelTableStaticOffsetData(uint32_t Offset) : Offset(Offset) {}
362
363 void emit(AsmPrinter *Asm) const override;
364
365 static constexpr Atom Atoms[] = {
366 Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
367
368 #ifndef NDEBUG
369 void print(raw_ostream &OS) const override;
370 #endif
371 protected:
order()372 uint64_t order() const override { return Offset; }
373
374 uint32_t Offset;
375 };
376
377 /// Accelerator table data implementation for type accelerator tables with
378 /// a DIE offset but no actual DIE pointer.
379 class AppleAccelTableStaticTypeData : public AppleAccelTableStaticOffsetData {
380 public:
AppleAccelTableStaticTypeData(uint32_t Offset,uint16_t Tag,bool ObjCClassIsImplementation,uint32_t QualifiedNameHash)381 AppleAccelTableStaticTypeData(uint32_t Offset, uint16_t Tag,
382 bool ObjCClassIsImplementation,
383 uint32_t QualifiedNameHash)
384 : AppleAccelTableStaticOffsetData(Offset),
385 QualifiedNameHash(QualifiedNameHash), Tag(Tag),
386 ObjCClassIsImplementation(ObjCClassIsImplementation) {}
387
388 void emit(AsmPrinter *Asm) const override;
389
390 static constexpr Atom Atoms[] = {
391 Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
392 Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
393 Atom(5, dwarf::DW_FORM_data1), Atom(6, dwarf::DW_FORM_data4)};
394
395 #ifndef NDEBUG
396 void print(raw_ostream &OS) const override;
397 #endif
398 protected:
order()399 uint64_t order() const override { return Offset; }
400
401 uint32_t QualifiedNameHash;
402 uint16_t Tag;
403 bool ObjCClassIsImplementation;
404 };
405
406 } // end namespace llvm
407
408 #endif // LLVM_CODEGEN_ACCELTABLE_H
409