LLVM 18.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"
17#include "llvm/ADT/MapVector.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 <variant>
28#include <vector>
29
30/// \file
31/// The DWARF and Apple accelerator tables are an indirect hash table optimized
32/// for null lookup rather than access to known data. The Apple accelerator
33/// tables are a precursor of the newer DWARF v5 accelerator tables. Both
34/// formats share common design ideas.
35///
36/// The Apple accelerator table are output into an on-disk format that looks
37/// like this:
38///
39/// .------------------.
40/// | HEADER |
41/// |------------------|
42/// | BUCKETS |
43/// |------------------|
44/// | HASHES |
45/// |------------------|
46/// | OFFSETS |
47/// |------------------|
48/// | DATA |
49/// `------------------'
50///
51/// The header contains a magic number, version, type of hash function,
52/// the number of buckets, total number of hashes, and room for a special struct
53/// of data and the length of that struct.
54///
55/// The buckets contain an index (e.g. 6) into the hashes array. The hashes
56/// section contains all of the 32-bit hash values in contiguous memory, and the
57/// offsets contain the offset into the data area for the particular hash.
58///
59/// For a lookup example, we could hash a function name and take it modulo the
60/// number of buckets giving us our bucket. From there we take the bucket value
61/// as an index into the hashes table and look at each successive hash as long
62/// as the hash value is still the same modulo result (bucket value) as earlier.
63/// If we have a match we look at that same entry in the offsets table and grab
64/// the offset in the data for our final match.
65///
66/// The DWARF v5 accelerator table consists of zero or more name indices that
67/// are output into an on-disk format that looks like this:
68///
69/// .------------------.
70/// | HEADER |
71/// |------------------|
72/// | CU LIST |
73/// |------------------|
74/// | LOCAL TU LIST |
75/// |------------------|
76/// | FOREIGN TU LIST |
77/// |------------------|
78/// | HASH TABLE |
79/// |------------------|
80/// | NAME TABLE |
81/// |------------------|
82/// | ABBREV TABLE |
83/// |------------------|
84/// | ENTRY POOL |
85/// `------------------'
86///
87/// For the full documentation please refer to the DWARF 5 standard.
88///
89///
90/// This file defines the class template AccelTable, which is represents an
91/// abstract view of an Accelerator table, without any notion of an on-disk
92/// layout. This class is parameterized by an entry type, which should derive
93/// from AccelTableData. This is the type of individual entries in the table,
94/// and it should store the data necessary to emit them. AppleAccelTableData is
95/// the base class for Apple Accelerator Table entries, which have a uniform
96/// structure based on a sequence of Atoms. There are different sub-classes
97/// derived from AppleAccelTable, which differ in the set of Atoms and how they
98/// obtain their values.
99///
100/// An Apple Accelerator Table can be serialized by calling emitAppleAccelTable
101/// function.
102
103namespace llvm {
104
105class AsmPrinter;
106class DwarfUnit;
107class DwarfDebug;
108class DwarfTypeUnit;
109class MCSymbol;
110class raw_ostream;
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.
116public:
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
129protected:
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.
137public:
139
140 /// Represents a group of entries with identical name (and hence, hash value).
141 struct HashData {
144 std::vector<AccelTableData *> Values;
146
147#ifndef NDEBUG
148 void print(raw_ostream &OS) const;
149 void dump() const { print(dbgs()); }
150#endif
151 };
152 using HashList = std::vector<HashData *>;
153 using BucketList = std::vector<HashList>;
154
155protected:
156 /// Allocator for HashData and Values.
158
161
165
168
169 void computeBucketCount();
170
172
173public:
174 void finalize(AsmPrinter *Asm, StringRef Prefix);
179
180#ifndef NDEBUG
181 void print(raw_ostream &OS) const;
182 void dump() const { print(dbgs()); }
183#endif
184
186 void operator=(const AccelTableBase &) = delete;
187};
188
189/// This class holds an abstract representation of an Accelerator Table,
190/// consisting of a sequence of buckets, each bucket containint a sequence of
191/// HashData entries. The class is parameterized by the type of entries it
192/// holds. The type template parameter also defines the hash function to use for
193/// hashing names.
194template <typename DataT> class AccelTable : public AccelTableBase {
195public:
196 AccelTable() : AccelTableBase(DataT::hash) {}
197
198 template <typename... Types>
199 void addName(DwarfStringPoolEntryRef Name, Types &&... Args);
200 void clear() { Entries.clear(); }
202 const StringEntries getEntries() const { return Entries; }
203};
204
205template <typename AccelTableDataT>
206template <typename... Types>
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 &It = Entries[Name.getString()];
213 if (It.Values.empty()) {
214 It.Name = Name;
215 It.HashValue = Hash(Name.getString());
216 }
217 It.Values.push_back(new (Allocator)
218 AccelTableDataT(std::forward<Types>(Args)...));
219}
220
221/// A base class for different implementations of Data classes for Apple
222/// Accelerator Tables. The columns in the table are defined by the static Atoms
223/// variable defined on the subclasses.
225public:
226 /// An Atom defines the form of the data in an Apple accelerator table.
227 /// Conceptually it is a column in the accelerator consisting of a type and a
228 /// specification of the form of its data.
229 struct Atom {
230 /// Atom Type.
232 /// DWARF Form.
234
236
237#ifndef NDEBUG
238 void print(raw_ostream &OS) const;
239 void dump() const { print(dbgs()); }
240#endif
241 };
242 // Subclasses should define:
243 // static constexpr Atom Atoms[];
244
245 virtual void emit(AsmPrinter *Asm) const = 0;
246
247 static uint32_t hash(StringRef Buffer) { return djbHash(Buffer); }
248};
249
250/// The Data class implementation for DWARF v5 accelerator table. Unlike the
251/// Apple Data classes, this class is just a DIE wrapper, and does not know to
252/// serialize itself. The complete serialization logic is in the
253/// emitDWARF5AccelTable function.
255public:
259 };
260
262
263 DWARF5AccelTableData(const DIE &Die, const uint32_t UnitID,
264 const bool IsTU = false);
265 DWARF5AccelTableData(const uint64_t DieOffset, const unsigned DieTag,
266 const unsigned UnitID, const bool IsTU = false)
267 : OffsetVal(DieOffset), DieTag(DieTag), UnitID(UnitID), IsTU(IsTU) {}
268
269#ifndef NDEBUG
270 void print(raw_ostream &OS) const override;
271#endif
272
274 assert(std::holds_alternative<uint64_t>(OffsetVal) &&
275 "Accessing DIE Offset before normalizing.");
276 return std::get<uint64_t>(OffsetVal);
277 }
278 unsigned getDieTag() const { return DieTag; }
279 unsigned getUnitID() const { return UnitID; }
280 bool isTU() const { return IsTU; }
282 assert(std::holds_alternative<const DIE *>(OffsetVal) &&
283 "Accessing offset after normalizing.");
284 OffsetVal = std::get<const DIE *>(OffsetVal)->getOffset();
285 }
286 bool isNormalized() const {
287 return std::holds_alternative<uint64_t>(OffsetVal);
288 }
289
290protected:
291 std::variant<const DIE *, uint64_t> OffsetVal;
295
296 uint64_t order() const override { return getDieOffset(); }
297};
298
300 // Symbol for start of the TU section.
302 // Unique ID of Type Unit.
303 unsigned UniqueID;
304};
306class DWARF5AccelTable : public AccelTable<DWARF5AccelTableData> {
307 // Symbols to start of all the TU sections that were generated.
308 TUVectorTy TUSymbols;
309
310public:
312 unsigned Index;
314 };
315 /// Returns type units that were constructed.
316 const TUVectorTy &getTypeUnitsSymbols() { return TUSymbols; }
317 /// Add a type unit start symbol.
319 /// Convert DIE entries to explicit offset.
320 /// Needs to be called after DIE offsets are computed.
322 for (auto &Entry : Entries) {
323 for (AccelTableData *Value : Entry.second.Values) {
325 // For TU we normalize as each Unit is emitted.
326 // So when this is invoked after CU construction we will be in mixed
327 // state.
328 if (!Data->isNormalized())
329 Data->normalizeDIEToOffset();
330 }
331 }
332 }
333
335 for (auto &Entry : Table.getEntries()) {
336 for (AccelTableData *Value : Entry.second.Values) {
338 addName(Entry.second.Name, Data->getDieOffset(), Data->getDieTag(),
339 Data->getUnitID(), true);
340 }
341 }
342 }
343};
344
345void emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents,
346 StringRef Prefix, const MCSymbol *SecBegin,
347 ArrayRef<AppleAccelTableData::Atom> Atoms);
348
349/// Emit an Apple Accelerator Table consisting of entries in the specified
350/// AccelTable. The DataT template parameter should be derived from
351/// AppleAccelTableData.
352template <typename DataT>
354 StringRef Prefix, const MCSymbol *SecBegin) {
355 static_assert(std::is_convertible<DataT *, AppleAccelTableData *>::value);
356 emitAppleAccelTableImpl(Asm, Contents, Prefix, SecBegin, DataT::Atoms);
357}
358
359void emitDWARF5AccelTable(AsmPrinter *Asm, DWARF5AccelTable &Contents,
360 const DwarfDebug &DD,
361 ArrayRef<std::unique_ptr<DwarfCompileUnit>> CUs);
362
363/// Emit a DWARFv5 Accelerator Table consisting of entries in the specified
364/// AccelTable. The \p CUs contains either symbols keeping offsets to the
365/// start of compilation unit, either offsets to the start of compilation
366/// unit themselves.
368 AsmPrinter *Asm, DWARF5AccelTable &Contents,
369 ArrayRef<std::variant<MCSymbol *, uint64_t>> CUs,
370 llvm::function_ref<std::optional<DWARF5AccelTable::UnitIndexAndEncoding>(
371 const DWARF5AccelTableData &)>
372 getIndexForEntry);
373
374/// Accelerator table data implementation for simple Apple accelerator tables
375/// with just a DIE reference.
377public:
379
380 void emit(AsmPrinter *Asm) const override;
381
382 static constexpr Atom Atoms[] = {
383 Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
384
385#ifndef NDEBUG
386 void print(raw_ostream &OS) const override;
387#endif
388protected:
389 uint64_t order() const override { return Die.getOffset(); }
390
391 const DIE &Die;
392};
393
394/// Accelerator table data implementation for Apple type accelerator tables.
396public:
398
399 void emit(AsmPrinter *Asm) const override;
400
401 static constexpr Atom Atoms[] = {
402 Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
403 Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
404 Atom(dwarf::DW_ATOM_type_flags, dwarf::DW_FORM_data1)};
405
406#ifndef NDEBUG
407 void print(raw_ostream &OS) const override;
408#endif
409};
410
411/// Accelerator table data implementation for simple Apple accelerator tables
412/// with a DIE offset but no actual DIE pointer.
414public:
416
417 void emit(AsmPrinter *Asm) const override;
418
419 static constexpr Atom Atoms[] = {
420 Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
421
422#ifndef NDEBUG
423 void print(raw_ostream &OS) const override;
424#endif
425protected:
426 uint64_t order() const override { return Offset; }
427
429};
430
431/// Accelerator table data implementation for type accelerator tables with
432/// a DIE offset but no actual DIE pointer.
434public:
441
442 void emit(AsmPrinter *Asm) const override;
443
444 static constexpr Atom Atoms[] = {
445 Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
446 Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
447 Atom(5, dwarf::DW_FORM_data1), Atom(6, dwarf::DW_FORM_data4)};
448
449#ifndef NDEBUG
450 void print(raw_ostream &OS) const override;
451#endif
452protected:
453 uint64_t order() const override { return Offset; }
454
458};
459
460} // end namespace llvm
461
462#endif // LLVM_CODEGEN_ACCELTABLE_H
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
This file implements a map that provides insertion order iteration.
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:136
BucketList Buckets
Definition: AccelTable.h:167
uint32_t getUniqueNameCount() const
Definition: AccelTable.h:178
std::vector< HashData * > HashList
Definition: AccelTable.h:152
std::vector< HashList > BucketList
Definition: AccelTable.h:153
BumpPtrAllocator Allocator
Allocator for HashData and Values.
Definition: AccelTable.h:157
void operator=(const AccelTableBase &)=delete
uint32_t getUniqueHashCount() const
Definition: AccelTable.h:177
void print(raw_ostream &OS) const
Definition: AccelTable.cpp:728
void dump() const
Definition: AccelTable.h:182
AccelTableBase(const AccelTableBase &)=delete
AccelTableBase(HashFn *Hash)
Definition: AccelTable.h:171
ArrayRef< HashList > getBuckets() const
Definition: AccelTable.h:175
uint32_t getBucketCount() const
Definition: AccelTable.h:176
uint32_t(StringRef) HashFn
Definition: AccelTable.h:138
uint32_t UniqueHashCount
Definition: AccelTable.h:164
StringEntries Entries
Definition: AccelTable.h:160
Interface which the different types of accelerator table data have to conform.
Definition: AccelTable.h:115
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:119
This class holds an abstract representation of an Accelerator Table, consisting of a sequence of buck...
Definition: AccelTable.h:194
const StringEntries getEntries() const
Definition: AccelTable.h:202
void addEntries(AccelTable< DataT > &Table)
void addName(DwarfStringPoolEntryRef Name, Types &&... Args)
Definition: AccelTable.h:207
A base class for different implementations of Data classes for Apple Accelerator Tables.
Definition: AccelTable.h:224
virtual void emit(AsmPrinter *Asm) const =0
static uint32_t hash(StringRef Buffer)
Definition: AccelTable.h:247
Accelerator table data implementation for simple Apple accelerator tables with just a DIE reference.
Definition: AccelTable.h:376
uint64_t order() const override
Definition: AccelTable.h:389
void print(raw_ostream &OS) const override
Definition: AccelTable.cpp:752
static constexpr Atom Atoms[]
Definition: AccelTable.h:382
AppleAccelTableOffsetData(const DIE &D)
Definition: AccelTable.h:378
Accelerator table data implementation for simple Apple accelerator tables with a DIE offset but no ac...
Definition: AccelTable.h:413
AppleAccelTableStaticOffsetData(uint32_t Offset)
Definition: AccelTable.h:415
static constexpr Atom Atoms[]
Definition: AccelTable.h:419
void print(raw_ostream &OS) const override
Definition: AccelTable.cpp:761
uint64_t order() const override
Definition: AccelTable.h:426
Accelerator table data implementation for type accelerator tables with a DIE offset but no actual DIE...
Definition: AccelTable.h:433
void print(raw_ostream &OS) const override
Definition: AccelTable.cpp:765
static constexpr Atom Atoms[]
Definition: AccelTable.h:444
uint64_t order() const override
Definition: AccelTable.h:453
AppleAccelTableStaticTypeData(uint32_t Offset, uint16_t Tag, bool ObjCClassIsImplementation, uint32_t QualifiedNameHash)
Definition: AccelTable.h:435
Accelerator table data implementation for Apple type accelerator tables.
Definition: AccelTable.h:395
void print(raw_ostream &OS) const override
Definition: AccelTable.cpp:756
AppleAccelTableTypeData(const DIE &D)
Definition: AccelTable.h:397
static constexpr Atom Atoms[]
Definition: AccelTable.h:401
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:819
unsigned getOffset() const
Get the compile/type unit relative offset of this DIE.
Definition: DIE.h:857
The Data class implementation for DWARF v5 accelerator table.
Definition: AccelTable.h:254
static uint32_t hash(StringRef Name)
Definition: AccelTable.h:261
void print(raw_ostream &OS) const override
Definition: AccelTable.cpp:747
unsigned getDieTag() const
Definition: AccelTable.h:278
std::variant< const DIE *, uint64_t > OffsetVal
Definition: AccelTable.h:291
unsigned getUnitID() const
Definition: AccelTable.h:279
uint64_t order() const override
Definition: AccelTable.h:296
uint64_t getDieOffset() const
Definition: AccelTable.h:273
DWARF5AccelTableData(const uint64_t DieOffset, const unsigned DieTag, const unsigned UnitID, const bool IsTU=false)
Definition: AccelTable.h:265
void convertDieToOffset()
Convert DIE entries to explicit offset.
Definition: AccelTable.h:321
const TUVectorTy & getTypeUnitsSymbols()
Returns type units that were constructed.
Definition: AccelTable.h:316
void addTypeUnitSymbol(DwarfTypeUnit &U)
Add a type unit start symbol.
Definition: AccelTable.cpp:640
void addTypeEntries(DWARF5AccelTable &Table)
Definition: AccelTable.h:334
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:40
size_type size() const
Definition: MapVector.h:60
void clear()
Definition: MapVector.h:88
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
LLVM Value Representation.
Definition: Value.h:74
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:599
@ DW_ATOM_die_tag
Definition: Dwarf.h:598
@ DW_ATOM_die_offset
Marker as the end of a list of atoms.
Definition: Dwarf.h:595
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:577
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
@ Other
Any other memory.
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:353
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
void emitDWARF5AccelTable(AsmPrinter *Asm, DWARF5AccelTable &Contents, const DwarfDebug &DD, ArrayRef< std::unique_ptr< DwarfCompileUnit > > CUs)
Definition: AccelTable.cpp:584
Represents a group of entries with identical name (and hence, hash value).
Definition: AccelTable.h:141
void print(raw_ostream &OS) const
Definition: AccelTable.cpp:715
DwarfStringPoolEntryRef Name
Definition: AccelTable.h:142
std::vector< AccelTableData * > Values
Definition: AccelTable.h:144
An Atom defines the form of the data in an Apple accelerator table.
Definition: AccelTable.h:229
const uint16_t Form
DWARF Form.
Definition: AccelTable.h:233
void print(raw_ostream &OS) const
Definition: AccelTable.cpp:697
const uint16_t Type
Atom Type.
Definition: AccelTable.h:231
constexpr Atom(uint16_t Type, uint16_t Form)
Definition: AccelTable.h:235
DWARF5AccelTableData::AttributeEncoding Endoding
Definition: AccelTable.h:313