1 //==- include/llvm/CodeGen/AccelTable.h - Accelerator Tables -----*- C++ -*-==//
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
7 //===----------------------------------------------------------------------===//
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"
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.
38 /// The Apple accelerator table are output into an on-disk format that looks
41 /// .------------------.
43 /// |------------------|
45 /// |------------------|
47 /// |------------------|
49 /// |------------------|
51 /// `------------------'
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.
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.
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.
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:
71 /// .------------------.
73 /// |------------------|
75 /// |------------------|
77 /// |------------------|
78 /// | FOREIGN TU LIST |
79 /// |------------------|
81 /// |------------------|
83 /// |------------------|
85 /// |------------------|
87 /// `------------------'
89 /// For the full documentation please refer to the DWARF 5 standard.
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
108 class DwarfCompileUnit
;
111 /// Interface which the different types of accelerator table data have to
112 /// conform. It serves as a base class for different values of the template
113 /// argument of the AccelTable class template.
114 class AccelTableData
{
116 virtual ~AccelTableData() = default;
118 bool operator<(const AccelTableData
&Other
) const {
119 return order() < Other
.order();
122 // Subclasses should implement:
123 // static uint32_t hash(StringRef Name);
126 virtual void print(raw_ostream
&OS
) const = 0;
129 virtual uint64_t order() const = 0;
132 /// A base class holding non-template-dependant functionality of the AccelTable
133 /// class. Clients should not use this class directly but rather instantiate
134 /// AccelTable with a type derived from AccelTableData.
135 class AccelTableBase
{
137 using HashFn
= uint32_t(StringRef
);
139 /// Represents a group of entries with identical name (and hence, hash value).
141 DwarfStringPoolEntryRef Name
;
143 std::vector
<AccelTableData
*> Values
;
146 HashData(DwarfStringPoolEntryRef Name
, HashFn
*Hash
)
147 : Name(Name
), HashValue(Hash(Name
.getString())) {}
150 void print(raw_ostream
&OS
) const;
151 void dump() const { print(dbgs()); }
154 using HashList
= std::vector
<HashData
*>;
155 using BucketList
= std::vector
<HashList
>;
158 /// Allocator for HashData and Values.
159 BumpPtrAllocator Allocator
;
161 using StringEntries
= StringMap
<HashData
, BumpPtrAllocator
&>;
162 StringEntries Entries
;
165 uint32_t BucketCount
;
166 uint32_t UniqueHashCount
;
171 void computeBucketCount();
173 AccelTableBase(HashFn
*Hash
) : Entries(Allocator
), Hash(Hash
) {}
176 void finalize(AsmPrinter
*Asm
, StringRef Prefix
);
177 ArrayRef
<HashList
> getBuckets() const { return Buckets
; }
178 uint32_t getBucketCount() const { return BucketCount
; }
179 uint32_t getUniqueHashCount() const { return UniqueHashCount
; }
180 uint32_t getUniqueNameCount() const { return Entries
.size(); }
183 void print(raw_ostream
&OS
) const;
184 void dump() const { print(dbgs()); }
187 AccelTableBase(const AccelTableBase
&) = delete;
188 void operator=(const AccelTableBase
&) = delete;
191 /// This class holds an abstract representation of an Accelerator Table,
192 /// consisting of a sequence of buckets, each bucket containint a sequence of
193 /// HashData entries. The class is parameterized by the type of entries it
194 /// holds. The type template parameter also defines the hash function to use for
196 template <typename DataT
> class AccelTable
: public AccelTableBase
{
198 AccelTable() : AccelTableBase(DataT::hash
) {}
200 template <typename
... Types
>
201 void addName(DwarfStringPoolEntryRef Name
, Types
&&... Args
);
204 template <typename AccelTableDataT
>
205 template <typename
... Types
>
206 void AccelTable
<AccelTableDataT
>::addName(DwarfStringPoolEntryRef Name
,
208 assert(Buckets
.empty() && "Already finalized!");
209 // If the string is in the list already then add this die to the list
210 // otherwise add a new one.
211 auto Iter
= Entries
.try_emplace(Name
.getString(), Name
, Hash
).first
;
212 assert(Iter
->second
.Name
== Name
);
213 Iter
->second
.Values
.push_back(
214 new (Allocator
) AccelTableDataT(std::forward
<Types
>(Args
)...));
217 /// A base class for different implementations of Data classes for Apple
218 /// Accelerator Tables. The columns in the table are defined by the static Atoms
219 /// variable defined on the subclasses.
220 class AppleAccelTableData
: public AccelTableData
{
222 /// An Atom defines the form of the data in an Apple accelerator table.
223 /// Conceptually it is a column in the accelerator consisting of a type and a
224 /// specification of the form of its data.
231 constexpr Atom(uint16_t Type
, uint16_t Form
) : Type(Type
), Form(Form
) {}
234 void print(raw_ostream
&OS
) const;
235 void dump() const { print(dbgs()); }
238 // Subclasses should define:
239 // static constexpr Atom Atoms[];
241 virtual void emit(AsmPrinter
*Asm
) const = 0;
243 static uint32_t hash(StringRef Buffer
) { return djbHash(Buffer
); }
246 /// The Data class implementation for DWARF v5 accelerator table. Unlike the
247 /// Apple Data classes, this class is just a DIE wrapper, and does not know to
248 /// serialize itself. The complete serialization logic is in the
249 /// emitDWARF5AccelTable function.
250 class DWARF5AccelTableData
: public AccelTableData
{
252 static uint32_t hash(StringRef Name
) { return caseFoldingDjbHash(Name
); }
254 DWARF5AccelTableData(const DIE
&Die
) : Die(Die
) {}
257 void print(raw_ostream
&OS
) const override
;
260 const DIE
&getDie() const { return Die
; }
261 uint64_t getDieOffset() const { return Die
.getOffset(); }
262 unsigned getDieTag() const { return Die
.getTag(); }
267 uint64_t order() const override
{ return Die
.getOffset(); }
270 class DWARF5AccelTableStaticData
: public AccelTableData
{
272 static uint32_t hash(StringRef Name
) { return caseFoldingDjbHash(Name
); }
274 DWARF5AccelTableStaticData(uint64_t DieOffset
, unsigned DieTag
,
276 : DieOffset(DieOffset
), DieTag(DieTag
), CUIndex(CUIndex
) {}
279 void print(raw_ostream
&OS
) const override
;
282 uint64_t getDieOffset() const { return DieOffset
; }
283 unsigned getDieTag() const { return DieTag
; }
284 unsigned getCUIndex() const { return CUIndex
; }
291 uint64_t order() const override
{ return DieOffset
; }
294 void emitAppleAccelTableImpl(AsmPrinter
*Asm
, AccelTableBase
&Contents
,
295 StringRef Prefix
, const MCSymbol
*SecBegin
,
296 ArrayRef
<AppleAccelTableData::Atom
> Atoms
);
298 /// Emit an Apple Accelerator Table consisting of entries in the specified
299 /// AccelTable. The DataT template parameter should be derived from
300 /// AppleAccelTableData.
301 template <typename DataT
>
302 void emitAppleAccelTable(AsmPrinter
*Asm
, AccelTable
<DataT
> &Contents
,
303 StringRef Prefix
, const MCSymbol
*SecBegin
) {
304 static_assert(std::is_convertible
<DataT
*, AppleAccelTableData
*>::value
, "");
305 emitAppleAccelTableImpl(Asm
, Contents
, Prefix
, SecBegin
, DataT::Atoms
);
308 void emitDWARF5AccelTable(AsmPrinter
*Asm
,
309 AccelTable
<DWARF5AccelTableData
> &Contents
,
310 const DwarfDebug
&DD
,
311 ArrayRef
<std::unique_ptr
<DwarfCompileUnit
>> CUs
);
313 void emitDWARF5AccelTable(
314 AsmPrinter
*Asm
, AccelTable
<DWARF5AccelTableStaticData
> &Contents
,
315 ArrayRef
<MCSymbol
*> CUs
,
316 llvm::function_ref
<unsigned(const DWARF5AccelTableStaticData
&)>
319 /// Accelerator table data implementation for simple Apple accelerator tables
320 /// with just a DIE reference.
321 class AppleAccelTableOffsetData
: public AppleAccelTableData
{
323 AppleAccelTableOffsetData(const DIE
&D
) : Die(D
) {}
325 void emit(AsmPrinter
*Asm
) const override
;
327 static constexpr Atom Atoms
[] = {
328 Atom(dwarf::DW_ATOM_die_offset
, dwarf::DW_FORM_data4
)};
331 void print(raw_ostream
&OS
) const override
;
334 uint64_t order() const override
{ return Die
.getOffset(); }
339 /// Accelerator table data implementation for Apple type accelerator tables.
340 class AppleAccelTableTypeData
: public AppleAccelTableOffsetData
{
342 AppleAccelTableTypeData(const DIE
&D
) : AppleAccelTableOffsetData(D
) {}
344 void emit(AsmPrinter
*Asm
) const override
;
346 static constexpr Atom Atoms
[] = {
347 Atom(dwarf::DW_ATOM_die_offset
, dwarf::DW_FORM_data4
),
348 Atom(dwarf::DW_ATOM_die_tag
, dwarf::DW_FORM_data2
),
349 Atom(dwarf::DW_ATOM_type_flags
, dwarf::DW_FORM_data1
)};
352 void print(raw_ostream
&OS
) const override
;
356 /// Accelerator table data implementation for simple Apple accelerator tables
357 /// with a DIE offset but no actual DIE pointer.
358 class AppleAccelTableStaticOffsetData
: public AppleAccelTableData
{
360 AppleAccelTableStaticOffsetData(uint32_t Offset
) : Offset(Offset
) {}
362 void emit(AsmPrinter
*Asm
) const override
;
364 static constexpr Atom Atoms
[] = {
365 Atom(dwarf::DW_ATOM_die_offset
, dwarf::DW_FORM_data4
)};
368 void print(raw_ostream
&OS
) const override
;
371 uint64_t order() const override
{ return Offset
; }
376 /// Accelerator table data implementation for type accelerator tables with
377 /// a DIE offset but no actual DIE pointer.
378 class AppleAccelTableStaticTypeData
: public AppleAccelTableStaticOffsetData
{
380 AppleAccelTableStaticTypeData(uint32_t Offset
, uint16_t Tag
,
381 bool ObjCClassIsImplementation
,
382 uint32_t QualifiedNameHash
)
383 : AppleAccelTableStaticOffsetData(Offset
),
384 QualifiedNameHash(QualifiedNameHash
), Tag(Tag
),
385 ObjCClassIsImplementation(ObjCClassIsImplementation
) {}
387 void emit(AsmPrinter
*Asm
) const override
;
389 static constexpr Atom Atoms
[] = {
390 Atom(dwarf::DW_ATOM_die_offset
, dwarf::DW_FORM_data4
),
391 Atom(dwarf::DW_ATOM_die_tag
, dwarf::DW_FORM_data2
),
392 Atom(5, dwarf::DW_FORM_data1
), Atom(6, dwarf::DW_FORM_data4
)};
395 void print(raw_ostream
&OS
) const override
;
398 uint64_t order() const override
{ return Offset
; }
400 uint32_t QualifiedNameHash
;
402 bool ObjCClassIsImplementation
;
405 } // end namespace llvm
407 #endif // LLVM_CODEGEN_DWARFACCELTABLE_H