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