LLVM  7.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 
265 protected:
266  const DIE &Die;
267 
268  uint64_t order() const override { return Die.getOffset(); }
269 };
270 
272  StringRef Prefix, const MCSymbol *SecBegin,
274 
275 /// Emit an Apple Accelerator Table consisting of entries in the specified
276 /// AccelTable. The DataT template parameter should be derived from
277 /// AppleAccelTableData.
278 template <typename DataT>
280  StringRef Prefix, const MCSymbol *SecBegin) {
281  static_assert(std::is_convertible<DataT *, AppleAccelTableData *>::value, "");
282  emitAppleAccelTableImpl(Asm, Contents, Prefix, SecBegin, DataT::Atoms);
283 }
284 
287  const DwarfDebug &DD,
288  ArrayRef<std::unique_ptr<DwarfCompileUnit>> CUs);
289 
290 /// Accelerator table data implementation for simple Apple accelerator tables
291 /// with just a DIE reference.
293 public:
294  AppleAccelTableOffsetData(const DIE *D) : Die(D) {}
295 
296  void emit(AsmPrinter *Asm) const override;
297 
298 #ifndef _MSC_VER
299  // The line below is rejected by older versions (TBD) of MSVC.
300  static constexpr Atom Atoms[] = {
301  Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
302 #else
303  // FIXME: Erase this path once the minimum MSCV version has been bumped.
304  static const SmallVector<Atom, 4> Atoms;
305 #endif
306 
307 #ifndef NDEBUG
308  void print(raw_ostream &OS) const override;
309 #endif
310 protected:
311  uint64_t order() const override { return Die->getOffset(); }
312 
313  const DIE *Die;
314 };
315 
316 /// Accelerator table data implementation for Apple type accelerator tables.
318 public:
320 
321  void emit(AsmPrinter *Asm) const override;
322 
323 #ifndef _MSC_VER
324  // The line below is rejected by older versions (TBD) of MSVC.
325  static constexpr Atom Atoms[] = {
326  Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
327  Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
328  Atom(dwarf::DW_ATOM_type_flags, dwarf::DW_FORM_data1)};
329 #else
330  // FIXME: Erase this path once the minimum MSCV version has been bumped.
331  static const SmallVector<Atom, 4> Atoms;
332 #endif
333 
334 #ifndef NDEBUG
335  void print(raw_ostream &OS) const override;
336 #endif
337 };
338 
339 /// Accelerator table data implementation for simple Apple accelerator tables
340 /// with a DIE offset but no actual DIE pointer.
342 public:
344 
345  void emit(AsmPrinter *Asm) const override;
346 
347 #ifndef _MSC_VER
348  // The line below is rejected by older versions (TBD) of MSVC.
349  static constexpr Atom Atoms[] = {
350  Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
351 #else
352  // FIXME: Erase this path once the minimum MSCV version has been bumped.
353  static const SmallVector<Atom, 4> Atoms;
354 #endif
355 
356 #ifndef NDEBUG
357  void print(raw_ostream &OS) const override;
358 #endif
359 protected:
360  uint64_t order() const override { return Offset; }
361 
363 };
364 
365 /// Accelerator table data implementation for type accelerator tables with
366 /// a DIE offset but no actual DIE pointer.
368 public:
370  bool ObjCClassIsImplementation,
371  uint32_t QualifiedNameHash)
373  QualifiedNameHash(QualifiedNameHash), Tag(Tag),
374  ObjCClassIsImplementation(ObjCClassIsImplementation) {}
375 
376  void emit(AsmPrinter *Asm) const override;
377 
378 #ifndef _MSC_VER
379  // The line below is rejected by older versions (TBD) of MSVC.
380  static constexpr Atom Atoms[] = {
381  Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
382  Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
383  Atom(5, dwarf::DW_FORM_data1), Atom(6, dwarf::DW_FORM_data4)};
384 #else
385  // FIXME: Erase this path once the minimum MSCV version has been bumped.
386  static const SmallVector<Atom, 4> Atoms;
387 #endif
388 
389 #ifndef NDEBUG
390  void print(raw_ostream &OS) const override;
391 #endif
392 protected:
393  uint64_t order() const override { return Offset; }
394 
396  uint16_t Tag;
398 };
399 
400 } // end namespace llvm
401 
402 #endif // LLVM_CODEGEN_DWARFACCELTABLE_H
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:279
DwarfStringPoolEntryRef Name
Definition: AccelTable.h:144
ArrayRef< HashList > getBuckets() const
Definition: AccelTable.h:180
Compute iterated dominance frontiers using a linear time algorithm.
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:311
static uint32_t hash(StringRef Name)
Definition: AccelTable.h:255
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:367
Collects and handles dwarf debug information.
Definition: DwarfDebug.h:204
This class holds an abstract representation of an Accelerator Table, consisting of a sequence of buck...
Definition: AccelTable.h:199
uint64_t order() const override
Definition: AccelTable.h:360
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:292
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
uint64_t order() const override
Definition: AccelTable.h:268
const uint16_t Type
Atom Type.
Definition: AccelTable.h:230
uint32_t getUniqueHashCount() const
Definition: AccelTable.h:182
unsigned size() const
Definition: StringMap.h:112
String pool entry reference.
void emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents, StringRef Prefix, const MCSymbol *SecBegin, ArrayRef< AppleAccelTableData::Atom > Atoms)
Definition: AccelTable.cpp:533
uint64_t order() const override
Definition: AccelTable.h:393
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:341
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
AppleAccelTableOffsetData(const DIE *D)
Definition: AccelTable.h:294
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:143
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:78
AppleAccelTableTypeData(const DIE *D)
Definition: AccelTable.h:319
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:369
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:540
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
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:862
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:132
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:222
This file contains constants used for implementing Dwarf debug support.
const uint16_t Form
DWARF Form.
Definition: AccelTable.h:232
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:317
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:44
AppleAccelTableStaticOffsetData(uint32_t Offset)
Definition: AccelTable.h:343
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:372
uint32_t getBucketCount() const
Definition: AccelTable.h:181
constexpr char Args[]
Key for Kernel::Metadata::mArgs.