LLVM  10.0.0svn
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 //
9 // This file contains support for writing accelerator tables.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_CODEGEN_DWARFACCELTABLE_H
14 #define LLVM_CODEGEN_DWARFACCELTABLE_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"
21 #include "llvm/CodeGen/DIE.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"
29 #include <cstddef>
30 #include <cstdint>
31 #include <vector>
32 
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.
101 ///
102 /// An Apple Accelerator Table can be serialized by calling emitAppleAccelTable
103 /// function.
104 ///
105 /// TODO: Add DWARF v5 emission code.
106 
107 namespace llvm {
108 
109 class AsmPrinter;
110 class DwarfCompileUnit;
111 class DwarfDebug;
112 
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.
117 public:
118  virtual ~AccelTableData() = default;
119 
120  bool operator<(const AccelTableData &Other) const {
121  return order() < Other.order();
122  }
123 
124  // Subclasses should implement:
125  // static uint32_t hash(StringRef Name);
126 
127 #ifndef NDEBUG
128  virtual void print(raw_ostream &OS) const = 0;
129 #endif
130 protected:
131  virtual uint64_t order() const = 0;
132 };
133 
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.
138 public:
140 
141  /// Represents a group of entries with identical name (and hence, hash value).
142  struct HashData {
145  std::vector<AccelTableData *> Values;
147 
149  : Name(Name), HashValue(Hash(Name.getString())) {}
150 
151 #ifndef NDEBUG
152  void print(raw_ostream &OS) const;
153  void dump() const { print(dbgs()); }
154 #endif
155  };
156  using HashList = std::vector<HashData *>;
157  using BucketList = std::vector<HashList>;
158 
159 protected:
160  /// Allocator for HashData and Values.
162 
165 
169 
172 
173  void computeBucketCount();
174 
175  AccelTableBase(HashFn *Hash) : Entries(Allocator), Hash(Hash) {}
176 
177 public:
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(); }
183 
184 #ifndef NDEBUG
185  void print(raw_ostream &OS) const;
186  void dump() const { print(dbgs()); }
187 #endif
188 
189  AccelTableBase(const AccelTableBase &) = delete;
190  void operator=(const AccelTableBase &) = delete;
191 };
192 
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) {}
201 
202  template <typename... Types>
203  void addName(DwarfStringPoolEntryRef Name, Types &&... Args);
204 };
205 
206 template <typename AccelTableDataT>
207 template <typename... Types>
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)...));
217 }
218 
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.
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;
232 
233  constexpr Atom(uint16_t Type, uint16_t Form) : Type(Type), Form(Form) {}
234 
235 #ifndef NDEBUG
236  void print(raw_ostream &OS) const;
237  void dump() const { print(dbgs()); }
238 #endif
239  };
240  // Subclasses should define:
241  // static constexpr Atom Atoms[];
242 
243  virtual void emit(AsmPrinter *Asm) const = 0;
244 
245  static uint32_t hash(StringRef Buffer) { return djbHash(Buffer); }
246 };
247 
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.
253 public:
254  static uint32_t hash(StringRef Name) { return caseFoldingDjbHash(Name); }
255 
256  DWARF5AccelTableData(const DIE &Die) : Die(Die) {}
257 
258 #ifndef NDEBUG
259  void print(raw_ostream &OS) const override;
260 #endif
261 
262  const DIE &getDie() const { return Die; }
263  uint64_t getDieOffset() const { return Die.getOffset(); }
264  unsigned getDieTag() const { return Die.getTag(); }
265 
266 protected:
267  const DIE &Die;
268 
269  uint64_t order() const override { return Die.getOffset(); }
270 };
271 
273 public:
274  static uint32_t hash(StringRef Name) { return caseFoldingDjbHash(Name); }
275 
276  DWARF5AccelTableStaticData(uint64_t DieOffset, unsigned DieTag,
277  unsigned CUIndex)
278  : DieOffset(DieOffset), DieTag(DieTag), CUIndex(CUIndex) {}
279 
280 #ifndef NDEBUG
281  void print(raw_ostream &OS) const override;
282 #endif
283 
284  uint64_t getDieOffset() const { return DieOffset; }
285  unsigned getDieTag() const { return DieTag; }
286  unsigned getCUIndex() const { return CUIndex; }
287 
288 protected:
289  uint64_t DieOffset;
290  unsigned DieTag;
291  unsigned CUIndex;
292 
293  uint64_t order() const override { return DieOffset; }
294 };
295 
297  StringRef Prefix, const MCSymbol *SecBegin,
299 
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>
305  StringRef Prefix, const MCSymbol *SecBegin) {
306  static_assert(std::is_convertible<DataT *, AppleAccelTableData *>::value, "");
307  emitAppleAccelTableImpl(Asm, Contents, Prefix, SecBegin, DataT::Atoms);
308 }
309 
312  const DwarfDebug &DD,
313  ArrayRef<std::unique_ptr<DwarfCompileUnit>> CUs);
314 
319  getCUIndexForEntry);
320 
321 /// Accelerator table data implementation for simple Apple accelerator tables
322 /// with just a DIE reference.
324 public:
325  AppleAccelTableOffsetData(const DIE &D) : Die(D) {}
326 
327  void emit(AsmPrinter *Asm) const override;
328 
329  static constexpr Atom Atoms[] = {
330  Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
331 
332 #ifndef NDEBUG
333  void print(raw_ostream &OS) const override;
334 #endif
335 protected:
336  uint64_t order() const override { return Die.getOffset(); }
337 
338  const DIE &Die;
339 };
340 
341 /// Accelerator table data implementation for Apple type accelerator tables.
343 public:
345 
346  void emit(AsmPrinter *Asm) const override;
347 
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)};
352 
353 #ifndef NDEBUG
354  void print(raw_ostream &OS) const override;
355 #endif
356 };
357 
358 /// Accelerator table data implementation for simple Apple accelerator tables
359 /// with a DIE offset but no actual DIE pointer.
361 public:
363 
364  void emit(AsmPrinter *Asm) const override;
365 
366  static constexpr Atom Atoms[] = {
367  Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
368 
369 #ifndef NDEBUG
370  void print(raw_ostream &OS) const override;
371 #endif
372 protected:
373  uint64_t order() const override { return Offset; }
374 
376 };
377 
378 /// Accelerator table data implementation for type accelerator tables with
379 /// a DIE offset but no actual DIE pointer.
381 public:
383  bool ObjCClassIsImplementation,
384  uint32_t QualifiedNameHash)
386  QualifiedNameHash(QualifiedNameHash), Tag(Tag),
387  ObjCClassIsImplementation(ObjCClassIsImplementation) {}
388 
389  void emit(AsmPrinter *Asm) const override;
390 
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)};
395 
396 #ifndef NDEBUG
397  void print(raw_ostream &OS) const override;
398 #endif
399 protected:
400  uint64_t order() const override { return Offset; }
401 
403  uint16_t Tag;
405 };
406 
407 } // end namespace llvm
408 
409 #endif // LLVM_CODEGEN_DWARFACCELTABLE_H
static uint32_t hash(StringRef Name)
Definition: AccelTable.h:274
std::vector< HashData * > HashList
Definition: AccelTable.h:156
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:304
DwarfStringPoolEntryRef Name
Definition: AccelTable.h:143
ArrayRef< HashList > getBuckets() const
Definition: AccelTable.h:179
This class represents lattice values for constants.
Definition: AllocatorList.h:23
arc branch finalize
An Atom defines the form of the data in an Apple accelerator table.
Definition: AccelTable.h:227
MCSymbol - Instances of this class represent a symbol name in the MC file, and MCSymbols are created ...
Definition: MCSymbol.h:41
uint64_t order() const override
Definition: AccelTable.h:336
amdgpu Simplify well known AMD library false FunctionCallee Value const Twine & Name
static uint32_t hash(StringRef Name)
Definition: AccelTable.h:254
uint64_t getDieOffset() const
Definition: AccelTable.h:263
AccelTableBase(HashFn *Hash)
Definition: AccelTable.h:175
DWARF5AccelTableData(const DIE &Die)
Definition: AccelTable.h:256
Accelerator table data implementation for type accelerator tables with a DIE offset but no actual DIE...
Definition: AccelTable.h:380
Collects and handles dwarf debug information.
Definition: DwarfDebug.h:293
This class holds an abstract representation of an Accelerator Table, consisting of a sequence of buck...
Definition: AccelTable.h:198
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:116
uint64_t order() const override
Definition: AccelTable.h:373
void addName(DwarfStringPoolEntryRef Name, Types &&... Args)
Definition: AccelTable.h:208
Accelerator table data implementation for simple Apple accelerator tables with just a DIE reference...
Definition: AccelTable.h:323
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
uint64_t order() const override
Definition: AccelTable.h:269
const uint16_t Type
Atom Type.
Definition: AccelTable.h:229
uint32_t getUniqueHashCount() const
Definition: AccelTable.h:181
unsigned size() const
Definition: StringMap.h:111
void emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents, StringRef Prefix, const MCSymbol *SecBegin, ArrayRef< AppleAccelTableData::Atom > Atoms)
Definition: AccelTable.cpp:544
DWARF5AccelTableStaticData(uint64_t DieOffset, unsigned DieTag, unsigned CUIndex)
Definition: AccelTable.h:276
uint64_t order() const override
Definition: AccelTable.h:400
constexpr Atom(uint16_t Type, uint16_t Form)
Definition: AccelTable.h:233
Accelerator table data implementation for simple Apple accelerator tables with a DIE offset but no ac...
Definition: AccelTable.h:360
virtual ~AccelTableData()=default
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
virtual void print(raw_ostream &OS) const =0
static uint32_t hash(StringRef Buffer)
Definition: AccelTable.h:245
unsigned getDieTag() const
Definition: AccelTable.h:264
uint32_t getUniqueNameCount() const
Definition: AccelTable.h:182
static uint32_t computeBucketCount(uint32_t NumStrings)
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:140
A structured debug information entry.
Definition: DIE.h:700
std::vector< HashList > BucketList
Definition: AccelTable.h:157
This class is intended to be used as a driving class for all asm writers.
Definition: AsmPrinter.h:78
const DIE & getDie() const
Definition: AccelTable.h:262
StringEntries Entries
Definition: AccelTable.h:164
AppleAccelTableStaticTypeData(uint32_t Offset, uint16_t Tag, bool ObjCClassIsImplementation, uint32_t QualifiedNameHash)
Definition: AccelTable.h:382
uint64_t order() const override
Definition: AccelTable.h:293
BucketList Buckets
Definition: AccelTable.h:171
void emitDWARF5AccelTable(AsmPrinter *Asm, AccelTable< DWARF5AccelTableData > &Contents, const DwarfDebug &DD, ArrayRef< std::unique_ptr< DwarfCompileUnit >> CUs)
Definition: AccelTable.cpp:551
uint32_t djbHash(StringRef Buffer, uint32_t H=5381)
The Bernstein hash function used by the DWARF accelerator tables.
Definition: DJB.h:21
A base class for different implementations of Data classes for Apple Accelerator Tables.
Definition: AccelTable.h:222
std::vector< AccelTableData * > Values
Definition: AccelTable.h:145
AppleAccelTableTypeData(const DIE &D)
Definition: AccelTable.h:344
unsigned first
Interface which the different types of accelerator table data have to conform.
Definition: AccelTable.h:116
Basic Register Allocator
void dump() const
Definition: AccelTable.h:186
virtual uint64_t order() const =0
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:71
BumpPtrAllocator Allocator
Allocator for HashData and Values.
Definition: AccelTable.h:161
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
A base class holding non-template-dependant functionality of the AccelTable class.
Definition: AccelTable.h:137
StringMap - This is an unconventional map that is specialized for handling keys that are "strings"...
Definition: StringMap.h:219
This file contains constants used for implementing Dwarf debug support.
const uint16_t Form
DWARF Form.
Definition: AccelTable.h:231
String pool entry reference.
AppleAccelTableOffsetData(const DIE &D)
Definition: AccelTable.h:325
Represents a group of entries with identical name (and hence, hash value).
Definition: AccelTable.h:142
The Data class implementation for DWARF v5 accelerator table.
Definition: AccelTable.h:252
Accelerator table data implementation for Apple type accelerator tables.
Definition: AccelTable.h:342
HashData(DwarfStringPoolEntryRef Name, HashFn *Hash)
Definition: AccelTable.h:148
bool operator<(const AccelTableData &Other) const
Definition: AccelTable.h:120
uint32_t UniqueHashCount
Definition: AccelTable.h:168
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
uint32_t(StringRef) HashFn
Definition: AccelTable.h:139
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
AppleAccelTableStaticOffsetData(uint32_t Offset)
Definition: AccelTable.h:362
unsigned getOffset() const
Get the compile/type unit relative offset of this DIE.
Definition: DIE.h:738
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
Marker as the end of a list of atoms.
Definition: Dwarf.h:363
uint32_t getBucketCount() const
Definition: AccelTable.h:180
constexpr char Args[]
Key for Kernel::Metadata::mArgs.