[Alignment][NFC] Migrate Instructions to Align
[llvm-core.git] / include / llvm / CodeGen / AccelTable.h
blob734531a65d505339220e908efeef5814f3fe97f2
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.
11 //===----------------------------------------------------------------------===//
13 #ifndef LLVM_CODEGEN_DWARFACCELTABLE_H
14 #define LLVM_CODEGEN_DWARFACCELTABLE_H
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>
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.
102 /// An Apple Accelerator Table can be serialized by calling emitAppleAccelTable
103 /// function.
105 /// TODO: Add DWARF v5 emission code.
107 namespace llvm {
109 class AsmPrinter;
110 class DwarfCompileUnit;
111 class DwarfDebug;
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 virtual ~AccelTableData() = default;
120 bool operator<(const AccelTableData &Other) const {
121 return order() < Other.order();
124 // Subclasses should implement:
125 // static uint32_t hash(StringRef Name);
127 #ifndef NDEBUG
128 virtual void print(raw_ostream &OS) const = 0;
129 #endif
130 protected:
131 virtual uint64_t order() const = 0;
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);
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;
148 HashData(DwarfStringPoolEntryRef Name, HashFn *Hash)
149 : Name(Name), HashValue(Hash(Name.getString())) {}
151 #ifndef NDEBUG
152 void print(raw_ostream &OS) const;
153 void dump() const { print(dbgs()); }
154 #endif
156 using HashList = std::vector<HashData *>;
157 using BucketList = std::vector<HashList>;
159 protected:
160 /// Allocator for HashData and Values.
161 BumpPtrAllocator Allocator;
163 using StringEntries = StringMap<HashData, BumpPtrAllocator &>;
164 StringEntries Entries;
166 HashFn *Hash;
167 uint32_t BucketCount;
168 uint32_t UniqueHashCount;
170 HashList Hashes;
171 BucketList Buckets;
173 void computeBucketCount();
175 AccelTableBase(HashFn *Hash) : Entries(Allocator), Hash(Hash) {}
177 public:
178 void finalize(AsmPrinter *Asm, StringRef Prefix);
179 ArrayRef<HashList> getBuckets() const { return Buckets; }
180 uint32_t getBucketCount() const { return BucketCount; }
181 uint32_t getUniqueHashCount() const { return UniqueHashCount; }
182 uint32_t getUniqueNameCount() const { return Entries.size(); }
184 #ifndef NDEBUG
185 void print(raw_ostream &OS) const;
186 void dump() const { print(dbgs()); }
187 #endif
189 AccelTableBase(const AccelTableBase &) = delete;
190 void operator=(const AccelTableBase &) = delete;
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 AccelTable() : AccelTableBase(DataT::hash) {}
202 template <typename... Types>
203 void addName(DwarfStringPoolEntryRef Name, Types &&... Args);
206 template <typename AccelTableDataT>
207 template <typename... Types>
208 void AccelTable<AccelTableDataT>::addName(DwarfStringPoolEntryRef Name,
209 Types &&... Args) {
210 assert(Buckets.empty() && "Already finalized!");
211 // If the string is in the list already then add this die to the list
212 // otherwise add a new one.
213 auto Iter = Entries.try_emplace(Name.getString(), Name, Hash).first;
214 assert(Iter->second.Name == Name);
215 Iter->second.Values.push_back(
216 new (Allocator) AccelTableDataT(std::forward<Types>(Args)...));
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;
233 constexpr Atom(uint16_t Type, uint16_t Form) : Type(Type), Form(Form) {}
235 #ifndef NDEBUG
236 void print(raw_ostream &OS) const;
237 void dump() const { print(dbgs()); }
238 #endif
240 // Subclasses should define:
241 // static constexpr Atom Atoms[];
243 virtual void emit(AsmPrinter *Asm) const = 0;
245 static uint32_t hash(StringRef Buffer) { return djbHash(Buffer); }
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 static uint32_t hash(StringRef Name) { return caseFoldingDjbHash(Name); }
256 DWARF5AccelTableData(const DIE &Die) : Die(Die) {}
258 #ifndef NDEBUG
259 void print(raw_ostream &OS) const override;
260 #endif
262 const DIE &getDie() const { return Die; }
263 uint64_t getDieOffset() const { return Die.getOffset(); }
264 unsigned getDieTag() const { return Die.getTag(); }
266 protected:
267 const DIE &Die;
269 uint64_t order() const override { return Die.getOffset(); }
272 class DWARF5AccelTableStaticData : public AccelTableData {
273 public:
274 static uint32_t hash(StringRef Name) { return caseFoldingDjbHash(Name); }
276 DWARF5AccelTableStaticData(uint64_t DieOffset, unsigned DieTag,
277 unsigned CUIndex)
278 : DieOffset(DieOffset), DieTag(DieTag), CUIndex(CUIndex) {}
280 #ifndef NDEBUG
281 void print(raw_ostream &OS) const override;
282 #endif
284 uint64_t getDieOffset() const { return DieOffset; }
285 unsigned getDieTag() const { return DieTag; }
286 unsigned getCUIndex() const { return CUIndex; }
288 protected:
289 uint64_t DieOffset;
290 unsigned DieTag;
291 unsigned CUIndex;
293 uint64_t order() const override { return DieOffset; }
296 void emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents,
297 StringRef Prefix, const MCSymbol *SecBegin,
298 ArrayRef<AppleAccelTableData::Atom> Atoms);
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 StringRef Prefix, const MCSymbol *SecBegin) {
306 static_assert(std::is_convertible<DataT *, AppleAccelTableData *>::value, "");
307 emitAppleAccelTableImpl(Asm, Contents, Prefix, SecBegin, DataT::Atoms);
310 void emitDWARF5AccelTable(AsmPrinter *Asm,
311 AccelTable<DWARF5AccelTableData> &Contents,
312 const DwarfDebug &DD,
313 ArrayRef<std::unique_ptr<DwarfCompileUnit>> CUs);
315 void emitDWARF5AccelTable(
316 AsmPrinter *Asm, AccelTable<DWARF5AccelTableStaticData> &Contents,
317 ArrayRef<MCSymbol *> CUs,
318 llvm::function_ref<unsigned(const DWARF5AccelTableStaticData &)>
319 getCUIndexForEntry);
321 /// Accelerator table data implementation for simple Apple accelerator tables
322 /// with just a DIE reference.
323 class AppleAccelTableOffsetData : public AppleAccelTableData {
324 public:
325 AppleAccelTableOffsetData(const DIE &D) : Die(D) {}
327 void emit(AsmPrinter *Asm) const override;
329 static constexpr Atom Atoms[] = {
330 Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
332 #ifndef NDEBUG
333 void print(raw_ostream &OS) const override;
334 #endif
335 protected:
336 uint64_t order() const override { return Die.getOffset(); }
338 const DIE &Die;
341 /// Accelerator table data implementation for Apple type accelerator tables.
342 class AppleAccelTableTypeData : public AppleAccelTableOffsetData {
343 public:
344 AppleAccelTableTypeData(const DIE &D) : AppleAccelTableOffsetData(D) {}
346 void emit(AsmPrinter *Asm) const override;
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)};
353 #ifndef NDEBUG
354 void print(raw_ostream &OS) const override;
355 #endif
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) {}
364 void emit(AsmPrinter *Asm) const override;
366 static constexpr Atom Atoms[] = {
367 Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
369 #ifndef NDEBUG
370 void print(raw_ostream &OS) const override;
371 #endif
372 protected:
373 uint64_t order() const override { return Offset; }
375 uint32_t Offset;
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) {}
389 void emit(AsmPrinter *Asm) const override;
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)};
396 #ifndef NDEBUG
397 void print(raw_ostream &OS) const override;
398 #endif
399 protected:
400 uint64_t order() const override { return Offset; }
402 uint32_t QualifiedNameHash;
403 uint16_t Tag;
404 bool ObjCClassIsImplementation;
407 } // end namespace llvm
409 #endif // LLVM_CODEGEN_DWARFACCELTABLE_H