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