Coverage Report

Created: 2018-09-17 19:50

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/CodeGen/AccelTable.h
Line
Count
Source (jump to first uncovered line)
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"
21
#include "llvm/BinaryFormat/Dwarf.h"
22
#include "llvm/CodeGen/DIE.h"
23
#include "llvm/CodeGen/DwarfStringPoolEntry.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"
29
#include "llvm/Support/raw_ostream.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.
117
class AccelTableData {
118
public:
119
0
  virtual ~AccelTableData() = default;
120
121
421k
  bool operator<(const AccelTableData &Other) const {
122
421k
    return order() < Other.order();
123
421k
  }
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.
138
class AccelTableBase {
139
public:
140
  using HashFn = uint32_t(StringRef);
141
142
  /// Represents a group of entries with identical name (and hence, hash value).
143
  struct HashData {
144
    DwarfStringPoolEntryRef Name;
145
    uint32_t HashValue;
146
    std::vector<AccelTableData *> Values;
147
    MCSymbol *Sym;
148
149
    HashData(DwarfStringPoolEntryRef Name, HashFn *Hash)
150
73.1k
        : 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.
162
  BumpPtrAllocator Allocator;
163
164
  using StringEntries = StringMap<HashData, BumpPtrAllocator &>;
165
  StringEntries Entries;
166
167
  HashFn *Hash;
168
  uint32_t BucketCount;
169
  uint32_t UniqueHashCount;
170
171
  HashList Hashes;
172
  BucketList Buckets;
173
174
  void computeBucketCount();
175
176
163k
  AccelTableBase(HashFn *Hash) : Entries(Allocator), Hash(Hash) {}
177
178
public:
179
  void finalize(AsmPrinter *Asm, StringRef Prefix);
180
44.6k
  ArrayRef<HashList> getBuckets() const { return Buckets; }
181
11.1k
  uint32_t getBucketCount() const { return BucketCount; }
182
11.0k
  uint32_t getUniqueHashCount() const { return UniqueHashCount; }
183
59
  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
162k
  AccelTable() : AccelTableBase(DataT::hash) {}
llvm::AccelTable<llvm::DWARF5AccelTableData>::AccelTable()
Line
Count
Source
201
32.5k
  AccelTable() : AccelTableBase(DataT::hash) {}
llvm::AccelTable<llvm::AppleAccelTableOffsetData>::AccelTable()
Line
Count
Source
201
97.6k
  AccelTable() : AccelTableBase(DataT::hash) {}
llvm::AccelTable<llvm::AppleAccelTableTypeData>::AccelTable()
Line
Count
Source
201
32.5k
  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>
209
void AccelTable<AccelTableDataT>::addName(DwarfStringPoolEntryRef Name,
210
331k
                                          Types &&... Args) {
211
331k
  assert(Buckets.empty() && "Already finalized!");
212
331k
  // If the string is in the list already then add this die to the list
213
331k
  // otherwise add a new one.
214
331k
  auto Iter = Entries.try_emplace(Name.getString(), Name, Hash).first;
215
331k
  assert(Iter->second.Name == Name);
216
331k
  Iter->second.Values.push_back(
217
331k
      new (Allocator) AccelTableDataT(std::forward<Types>(Args)...));
218
331k
}
void llvm::AccelTable<llvm::AppleAccelTableOffsetData>::addName<llvm::DIE const&>(llvm::DwarfStringPoolEntryRef, llvm::DIE const&&&)
Line
Count
Source
210
330k
                                          Types &&... Args) {
211
330k
  assert(Buckets.empty() && "Already finalized!");
212
330k
  // If the string is in the list already then add this die to the list
213
330k
  // otherwise add a new one.
214
330k
  auto Iter = Entries.try_emplace(Name.getString(), Name, Hash).first;
215
330k
  assert(Iter->second.Name == Name);
216
330k
  Iter->second.Values.push_back(
217
330k
      new (Allocator) AccelTableDataT(std::forward<Types>(Args)...));
218
330k
}
void llvm::AccelTable<llvm::DWARF5AccelTableData>::addName<llvm::DIE const&>(llvm::DwarfStringPoolEntryRef, llvm::DIE const&&&)
Line
Count
Source
210
442
                                          Types &&... Args) {
211
442
  assert(Buckets.empty() && "Already finalized!");
212
442
  // If the string is in the list already then add this die to the list
213
442
  // otherwise add a new one.
214
442
  auto Iter = Entries.try_emplace(Name.getString(), Name, Hash).first;
215
442
  assert(Iter->second.Name == Name);
216
442
  Iter->second.Values.push_back(
217
442
      new (Allocator) AccelTableDataT(std::forward<Types>(Args)...));
218
442
}
void llvm::AccelTable<llvm::AppleAccelTableTypeData>::addName<llvm::DIE const&>(llvm::DwarfStringPoolEntryRef, llvm::DIE const&&&)
Line
Count
Source
210
787
                                          Types &&... Args) {
211
787
  assert(Buckets.empty() && "Already finalized!");
212
787
  // If the string is in the list already then add this die to the list
213
787
  // otherwise add a new one.
214
787
  auto Iter = Entries.try_emplace(Name.getString(), Name, Hash).first;
215
787
  assert(Iter->second.Name == Name);
216
787
  Iter->second.Values.push_back(
217
787
      new (Allocator) AccelTableDataT(std::forward<Types>(Args)...));
218
787
}
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.
223
class AppleAccelTableData : public AccelTableData {
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
72.6k
  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.
253
class DWARF5AccelTableData : public AccelTableData {
254
public:
255
434
  static uint32_t hash(StringRef Name) { return caseFoldingDjbHash(Name); }
256
257
442
  DWARF5AccelTableData(const DIE &Die) : Die(Die) {}
258
259
#ifndef NDEBUG
260
  void print(raw_ostream &OS) const override;
261
#endif
262
263
275
  const DIE &getDie() const { return Die; }
264
442
  uint64_t getDieOffset() const { return Die.getOffset(); }
265
884
  unsigned getDieTag() const { return Die.getTag(); }
266
267
protected:
268
  const DIE &Die;
269
270
22
  uint64_t order() const override { return Die.getOffset(); }
271
};
272
273
class DWARF5AccelTableStaticData : public AccelTableData {
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
24
  uint64_t getDieOffset() const { return DieOffset; }
286
48
  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
297
void emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents,
298
                             StringRef Prefix, const MCSymbol *SecBegin,
299
                             ArrayRef<AppleAccelTableData::Atom> Atoms);
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>
305
void emitAppleAccelTable(AsmPrinter *Asm, AccelTable<DataT> &Contents,
306
10.7k
                         StringRef Prefix, const MCSymbol *SecBegin) {
307
10.7k
  static_assert(std::is_convertible<DataT *, AppleAccelTableData *>::value, "");
308
10.7k
  emitAppleAccelTableImpl(Asm, Contents, Prefix, SecBegin, DataT::Atoms);
309
10.7k
}
void llvm::emitAppleAccelTable<llvm::AppleAccelTableOffsetData>(llvm::AsmPrinter*, llvm::AccelTable<llvm::AppleAccelTableOffsetData>&, llvm::StringRef, llvm::MCSymbol const*)
Line
Count
Source
306
8.04k
                         StringRef Prefix, const MCSymbol *SecBegin) {
307
8.04k
  static_assert(std::is_convertible<DataT *, AppleAccelTableData *>::value, "");
308
8.04k
  emitAppleAccelTableImpl(Asm, Contents, Prefix, SecBegin, DataT::Atoms);
309
8.04k
}
void llvm::emitAppleAccelTable<llvm::AppleAccelTableTypeData>(llvm::AsmPrinter*, llvm::AccelTable<llvm::AppleAccelTableTypeData>&, llvm::StringRef, llvm::MCSymbol const*)
Line
Count
Source
306
2.68k
                         StringRef Prefix, const MCSymbol *SecBegin) {
307
2.68k
  static_assert(std::is_convertible<DataT *, AppleAccelTableData *>::value, "");
308
2.68k
  emitAppleAccelTableImpl(Asm, Contents, Prefix, SecBegin, DataT::Atoms);
309
2.68k
}
310
311
void emitDWARF5AccelTable(AsmPrinter *Asm,
312
                          AccelTable<DWARF5AccelTableData> &Contents,
313
                          const DwarfDebug &DD,
314
                          ArrayRef<std::unique_ptr<DwarfCompileUnit>> CUs);
315
316
void emitDWARF5AccelTable(
317
    AsmPrinter *Asm, AccelTable<DWARF5AccelTableStaticData> &Contents,
318
    ArrayRef<MCSymbol *> CUs,
319
    llvm::function_ref<unsigned(const DWARF5AccelTableStaticData &)>
320
        getCUIndexForEntry);
321
322
/// Accelerator table data implementation for simple Apple accelerator tables
323
/// with just a DIE reference.
324
class AppleAccelTableOffsetData : public AppleAccelTableData {
325
public:
326
331k
  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
843k
  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.
349
class AppleAccelTableTypeData : public AppleAccelTableOffsetData {
350
public:
351
787
  AppleAccelTableTypeData(const DIE &D) : AppleAccelTableOffsetData(D) {}
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.
373
class AppleAccelTableStaticOffsetData : public AppleAccelTableData {
374
public:
375
  AppleAccelTableStaticOffsetData(uint32_t Offset) : Offset(Offset) {}
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
142
  uint64_t order() const override { return Offset; }
393
394
  uint32_t Offset;
395
};
396
397
/// Accelerator table data implementation for type accelerator tables with
398
/// a DIE offset but no actual DIE pointer.
399
class AppleAccelTableStaticTypeData : public AppleAccelTableStaticOffsetData {
400
public:
401
  AppleAccelTableStaticTypeData(uint32_t Offset, uint16_t Tag,
402
                                bool ObjCClassIsImplementation,
403
                                uint32_t QualifiedNameHash)
404
      : AppleAccelTableStaticOffsetData(Offset),
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
216
  uint64_t order() const override { return Offset; }
426
427
  uint32_t QualifiedNameHash;
428
  uint16_t Tag;
429
  bool ObjCClassIsImplementation;
430
};
431
432
} // end namespace llvm
433
434
#endif // LLVM_CODEGEN_DWARFACCELTABLE_H