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 namespace llvm {
106 
107 class AsmPrinter;
108 class DwarfCompileUnit;
109 class DwarfDebug;
110 
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.
115 public:
116  virtual ~AccelTableData() = default;
117 
118  bool operator<(const AccelTableData &Other) const {
119  return order() < Other.order();
120  }
121 
122  // Subclasses should implement:
123  // static uint32_t hash(StringRef Name);
124 
125 #ifndef NDEBUG
126  virtual void print(raw_ostream &OS) const = 0;
127 #endif
128 protected:
129  virtual uint64_t order() const = 0;
130 };
131 
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.
136 public:
138 
139  /// Represents a group of entries with identical name (and hence, hash value).
140  struct HashData {
143  std::vector<AccelTableData *> Values;
145 
147  : Name(Name), HashValue(Hash(Name.getString())) {}
148 
149 #ifndef NDEBUG
150  void print(raw_ostream &OS) const;
151  void dump() const { print(dbgs()); }
152 #endif
153  };
154  using HashList = std::vector<HashData *>;
155  using BucketList = std::vector<HashList>;
156 
157 protected:
158  /// Allocator for HashData and Values.
160 
163 
167 
170 
171  void computeBucketCount();
172 
173  AccelTableBase(HashFn *Hash) : Entries(Allocator), Hash(Hash) {}
174 
175 public:
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(); }
181 
182 #ifndef NDEBUG
183  void print(raw_ostream &OS) const;
184  void dump() const { print(dbgs()); }
185 #endif
186 
187  AccelTableBase(const AccelTableBase &) = delete;
188  void operator=(const AccelTableBase &) = delete;
189 };
190 
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
195 /// hashing names.
196 template <typename DataT> class AccelTable : public AccelTableBase {
197 public:
198  AccelTable() : AccelTableBase(DataT::hash) {}
199 
200  template <typename... Types>
201  void addName(DwarfStringPoolEntryRef Name, Types &&... Args);
202 };
203 
204 template <typename AccelTableDataT>
205 template <typename... Types>
207  Types &&... Args) {
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)...));
215 }
216 
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.
221 public:
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.
225  struct Atom {
226  /// Atom Type.
227  const uint16_t Type;
228  /// DWARF Form.
229  const uint16_t Form;
230 
231  constexpr Atom(uint16_t Type, uint16_t Form) : Type(Type), Form(Form) {}
232 
233 #ifndef NDEBUG
234  void print(raw_ostream &OS) const;
235  void dump() const { print(dbgs()); }
236 #endif
237  };
238  // Subclasses should define:
239  // static constexpr Atom Atoms[];
240 
241  virtual void emit(AsmPrinter *Asm) const = 0;
242 
243  static uint32_t hash(StringRef Buffer) { return djbHash(Buffer); }
244 };
245 
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.
251 public:
252  static uint32_t hash(StringRef Name) { return caseFoldingDjbHash(Name); }
253 
254  DWARF5AccelTableData(const DIE &Die) : Die(Die) {}
255 
256 #ifndef NDEBUG
257  void print(raw_ostream &OS) const override;
258 #endif
259 
260  const DIE &getDie() const { return Die; }
261  uint64_t getDieOffset() const { return Die.getOffset(); }
262  unsigned getDieTag() const { return Die.getTag(); }
263 
264 protected:
265  const DIE &Die;
266 
267  uint64_t order() const override { return Die.getOffset(); }
268 };
269 
271 public:
272  static uint32_t hash(StringRef Name) { return caseFoldingDjbHash(Name); }
273 
274  DWARF5AccelTableStaticData(uint64_t DieOffset, unsigned DieTag,
275  unsigned CUIndex)
276  : DieOffset(DieOffset), DieTag(DieTag), CUIndex(CUIndex) {}
277 
278 #ifndef NDEBUG
279  void print(raw_ostream &OS) const override;
280 #endif
281 
282  uint64_t getDieOffset() const { return DieOffset; }
283  unsigned getDieTag() const { return DieTag; }
284  unsigned getCUIndex() const { return CUIndex; }
285 
286 protected:
287  uint64_t DieOffset;
288  unsigned DieTag;
289  unsigned CUIndex;
290 
291  uint64_t order() const override { return DieOffset; }
292 };
293 
295  StringRef Prefix, const MCSymbol *SecBegin,
297 
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>
303  StringRef Prefix, const MCSymbol *SecBegin) {
304  static_assert(std::is_convertible<DataT *, AppleAccelTableData *>::value, "");
305  emitAppleAccelTableImpl(Asm, Contents, Prefix, SecBegin, DataT::Atoms);
306 }
307 
310  const DwarfDebug &DD,
311  ArrayRef<std::unique_ptr<DwarfCompileUnit>> CUs);
312 
317  getCUIndexForEntry);
318 
319 /// Accelerator table data implementation for simple Apple accelerator tables
320 /// with just a DIE reference.
322 public:
323  AppleAccelTableOffsetData(const DIE &D) : Die(D) {}
324 
325  void emit(AsmPrinter *Asm) const override;
326 
327  static constexpr Atom Atoms[] = {
328  Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
329 
330 #ifndef NDEBUG
331  void print(raw_ostream &OS) const override;
332 #endif
333 protected:
334  uint64_t order() const override { return Die.getOffset(); }
335 
336  const DIE &Die;
337 };
338 
339 /// Accelerator table data implementation for Apple type accelerator tables.
341 public:
343 
344  void emit(AsmPrinter *Asm) const override;
345 
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)};
350 
351 #ifndef NDEBUG
352  void print(raw_ostream &OS) const override;
353 #endif
354 };
355 
356 /// Accelerator table data implementation for simple Apple accelerator tables
357 /// with a DIE offset but no actual DIE pointer.
359 public:
361 
362  void emit(AsmPrinter *Asm) const override;
363 
364  static constexpr Atom Atoms[] = {
365  Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
366 
367 #ifndef NDEBUG
368  void print(raw_ostream &OS) const override;
369 #endif
370 protected:
371  uint64_t order() const override { return Offset; }
372 
374 };
375 
376 /// Accelerator table data implementation for type accelerator tables with
377 /// a DIE offset but no actual DIE pointer.
379 public:
381  bool ObjCClassIsImplementation,
382  uint32_t QualifiedNameHash)
384  QualifiedNameHash(QualifiedNameHash), Tag(Tag),
385  ObjCClassIsImplementation(ObjCClassIsImplementation) {}
386 
387  void emit(AsmPrinter *Asm) const override;
388 
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)};
393 
394 #ifndef NDEBUG
395  void print(raw_ostream &OS) const override;
396 #endif
397 protected:
398  uint64_t order() const override { return Offset; }
399 
401  uint16_t Tag;
403 };
404 
405 } // end namespace llvm
406 
407 #endif // LLVM_CODEGEN_DWARFACCELTABLE_H
static uint32_t hash(StringRef Name)
Definition: AccelTable.h:272
std::vector< HashData * > HashList
Definition: AccelTable.h:154
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:302
DwarfStringPoolEntryRef Name
Definition: AccelTable.h:141
ArrayRef< HashList > getBuckets() const
Definition: AccelTable.h:177
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:225
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:334
amdgpu Simplify well known AMD library false FunctionCallee Value const Twine & Name
static uint32_t hash(StringRef Name)
Definition: AccelTable.h:252
uint64_t getDieOffset() const
Definition: AccelTable.h:261
AccelTableBase(HashFn *Hash)
Definition: AccelTable.h:173
DWARF5AccelTableData(const DIE &Die)
Definition: AccelTable.h:254
Accelerator table data implementation for type accelerator tables with a DIE offset but no actual DIE...
Definition: AccelTable.h:378
Collects and handles dwarf debug information.
Definition: DwarfDebug.h:292
This class holds an abstract representation of an Accelerator Table, consisting of a sequence of buck...
Definition: AccelTable.h:196
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:104
uint64_t order() const override
Definition: AccelTable.h:371
void addName(DwarfStringPoolEntryRef Name, Types &&... Args)
Definition: AccelTable.h:206
Accelerator table data implementation for simple Apple accelerator tables with just a DIE reference...
Definition: AccelTable.h:321
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
uint64_t order() const override
Definition: AccelTable.h:267
const uint16_t Type
Atom Type.
Definition: AccelTable.h:227
uint32_t getUniqueHashCount() const
Definition: AccelTable.h:179
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:274
uint64_t order() const override
Definition: AccelTable.h:398
constexpr Atom(uint16_t Type, uint16_t Form)
Definition: AccelTable.h:231
Accelerator table data implementation for simple Apple accelerator tables with a DIE offset but no ac...
Definition: AccelTable.h:358
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:243
unsigned getDieTag() const
Definition: AccelTable.h:262
uint32_t getUniqueNameCount() const
Definition: AccelTable.h:180
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:155
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:260
StringEntries Entries
Definition: AccelTable.h:162
AppleAccelTableStaticTypeData(uint32_t Offset, uint16_t Tag, bool ObjCClassIsImplementation, uint32_t QualifiedNameHash)
Definition: AccelTable.h:380
uint64_t order() const override
Definition: AccelTable.h:291
BucketList Buckets
Definition: AccelTable.h:169
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:220
std::vector< AccelTableData * > Values
Definition: AccelTable.h:143
AppleAccelTableTypeData(const DIE &D)
Definition: AccelTable.h:342
unsigned first
Interface which the different types of accelerator table data have to conform.
Definition: AccelTable.h:114
Basic Register Allocator
void dump() const
Definition: AccelTable.h:184
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:159
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:135
StringMap - This is an unconventional map that is specialized for handling keys that are "strings"...
Definition: StringMap.h:242
This file contains constants used for implementing Dwarf debug support.
const uint16_t Form
DWARF Form.
Definition: AccelTable.h:229
String pool entry reference.
AppleAccelTableOffsetData(const DIE &D)
Definition: AccelTable.h:323
Represents a group of entries with identical name (and hence, hash value).
Definition: AccelTable.h:140
The Data class implementation for DWARF v5 accelerator table.
Definition: AccelTable.h:250
Accelerator table data implementation for Apple type accelerator tables.
Definition: AccelTable.h:340
HashData(DwarfStringPoolEntryRef Name, HashFn *Hash)
Definition: AccelTable.h:146
bool operator<(const AccelTableData &Other) const
Definition: AccelTable.h:118
uint32_t UniqueHashCount
Definition: AccelTable.h:166
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
uint32_t(StringRef) HashFn
Definition: AccelTable.h:137
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:360
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:409
uint32_t getBucketCount() const
Definition: AccelTable.h:178
constexpr char Args[]
Key for Kernel::Metadata::mArgs.