Coverage Report

Created: 2019-02-20 00:17

/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
// 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"
20
#include "llvm/BinaryFormat/Dwarf.h"
21
#include "llvm/CodeGen/DIE.h"
22
#include "llvm/CodeGen/DwarfStringPoolEntry.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"
28
#include "llvm/Support/raw_ostream.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.
116
class AccelTableData {
117
public:
118
0
  virtual ~AccelTableData() = default;
119
120
447k
  bool operator<(const AccelTableData &Other) const {
121
447k
    return order() < Other.order();
122
447k
  }
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.
137
class AccelTableBase {
138
public:
139
  using HashFn = uint32_t(StringRef);
140
141
  /// Represents a group of entries with identical name (and hence, hash value).
142
  struct HashData {
143
    DwarfStringPoolEntryRef Name;
144
    uint32_t HashValue;
145
    std::vector<AccelTableData *> Values;
146
    MCSymbol *Sym;
147
148
    HashData(DwarfStringPoolEntryRef Name, HashFn *Hash)
149
70.6k
        : 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.
161
  BumpPtrAllocator Allocator;
162
163
  using StringEntries = StringMap<HashData, BumpPtrAllocator &>;
164
  StringEntries Entries;
165
166
  HashFn *Hash;
167
  uint32_t BucketCount;
168
  uint32_t UniqueHashCount;
169
170
  HashList Hashes;
171
  BucketList Buckets;
172
173
  void computeBucketCount();
174
175
169k
  AccelTableBase(HashFn *Hash) : Entries(Allocator), Hash(Hash) {}
176
177
public:
178
  void finalize(AsmPrinter *Asm, StringRef Prefix);
179
42.4k
  ArrayRef<HashList> getBuckets() const { return Buckets; }
180
10.5k
  uint32_t getBucketCount() const { return BucketCount; }
181
10.5k
  uint32_t getUniqueHashCount() const { return UniqueHashCount; }
182
64
  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
168k
  AccelTable() : AccelTableBase(DataT::hash) {}
llvm::AccelTable<llvm::DWARF5AccelTableData>::AccelTable()
Line
Count
Source
200
33.7k
  AccelTable() : AccelTableBase(DataT::hash) {}
llvm::AccelTable<llvm::AppleAccelTableOffsetData>::AccelTable()
Line
Count
Source
200
101k
  AccelTable() : AccelTableBase(DataT::hash) {}
llvm::AccelTable<llvm::AppleAccelTableTypeData>::AccelTable()
Line
Count
Source
200
33.7k
  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>
208
void AccelTable<AccelTableDataT>::addName(DwarfStringPoolEntryRef Name,
209
342k
                                          Types &&... Args) {
210
342k
  assert(Buckets.empty() && "Already finalized!");
211
342k
  // If the string is in the list already then add this die to the list
212
342k
  // otherwise add a new one.
213
342k
  auto Iter = Entries.try_emplace(Name.getString(), Name, Hash).first;
214
342k
  assert(Iter->second.Name == Name);
215
342k
  Iter->second.Values.push_back(
216
342k
      new (Allocator) AccelTableDataT(std::forward<Types>(Args)...));
217
342k
}
void llvm::AccelTable<llvm::AppleAccelTableOffsetData>::addName<llvm::DIE const&>(llvm::DwarfStringPoolEntryRef, llvm::DIE const&&&)
Line
Count
Source
209
341k
                                          Types &&... Args) {
210
341k
  assert(Buckets.empty() && "Already finalized!");
211
341k
  // If the string is in the list already then add this die to the list
212
341k
  // otherwise add a new one.
213
341k
  auto Iter = Entries.try_emplace(Name.getString(), Name, Hash).first;
214
341k
  assert(Iter->second.Name == Name);
215
341k
  Iter->second.Values.push_back(
216
341k
      new (Allocator) AccelTableDataT(std::forward<Types>(Args)...));
217
341k
}
void llvm::AccelTable<llvm::DWARF5AccelTableData>::addName<llvm::DIE const&>(llvm::DwarfStringPoolEntryRef, llvm::DIE const&&&)
Line
Count
Source
209
462
                                          Types &&... Args) {
210
462
  assert(Buckets.empty() && "Already finalized!");
211
462
  // If the string is in the list already then add this die to the list
212
462
  // otherwise add a new one.
213
462
  auto Iter = Entries.try_emplace(Name.getString(), Name, Hash).first;
214
462
  assert(Iter->second.Name == Name);
215
462
  Iter->second.Values.push_back(
216
462
      new (Allocator) AccelTableDataT(std::forward<Types>(Args)...));
217
462
}
void llvm::AccelTable<llvm::AppleAccelTableTypeData>::addName<llvm::DIE const&>(llvm::DwarfStringPoolEntryRef, llvm::DIE const&&&)
Line
Count
Source
209
796
                                          Types &&... Args) {
210
796
  assert(Buckets.empty() && "Already finalized!");
211
796
  // If the string is in the list already then add this die to the list
212
796
  // otherwise add a new one.
213
796
  auto Iter = Entries.try_emplace(Name.getString(), Name, Hash).first;
214
796
  assert(Iter->second.Name == Name);
215
796
  Iter->second.Values.push_back(
216
796
      new (Allocator) AccelTableDataT(std::forward<Types>(Args)...));
217
796
}
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.
222
class AppleAccelTableData : public AccelTableData {
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
70.1k
  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.
252
class DWARF5AccelTableData : public AccelTableData {
253
public:
254
454
  static uint32_t hash(StringRef Name) { return caseFoldingDjbHash(Name); }
255
256
462
  DWARF5AccelTableData(const DIE &Die) : Die(Die) {}
257
258
#ifndef NDEBUG
259
  void print(raw_ostream &OS) const override;
260
#endif
261
262
275
  const DIE &getDie() const { return Die; }
263
462
  uint64_t getDieOffset() const { return Die.getOffset(); }
264
924
  unsigned getDieTag() const { return Die.getTag(); }
265
266
protected:
267
  const DIE &Die;
268
269
22
  uint64_t order() const override { return Die.getOffset(); }
270
};
271
272
class DWARF5AccelTableStaticData : public AccelTableData {
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
24
  uint64_t getDieOffset() const { return DieOffset; }
285
48
  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
296
void emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents,
297
                             StringRef Prefix, const MCSymbol *SecBegin,
298
                             ArrayRef<AppleAccelTableData::Atom> Atoms);
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>
304
void emitAppleAccelTable(AsmPrinter *Asm, AccelTable<DataT> &Contents,
305
10.1k
                         StringRef Prefix, const MCSymbol *SecBegin) {
306
10.1k
  static_assert(std::is_convertible<DataT *, AppleAccelTableData *>::value, "");
307
10.1k
  emitAppleAccelTableImpl(Asm, Contents, Prefix, SecBegin, DataT::Atoms);
308
10.1k
}
void llvm::emitAppleAccelTable<llvm::AppleAccelTableOffsetData>(llvm::AsmPrinter*, llvm::AccelTable<llvm::AppleAccelTableOffsetData>&, llvm::StringRef, llvm::MCSymbol const*)
Line
Count
Source
305
7.59k
                         StringRef Prefix, const MCSymbol *SecBegin) {
306
7.59k
  static_assert(std::is_convertible<DataT *, AppleAccelTableData *>::value, "");
307
7.59k
  emitAppleAccelTableImpl(Asm, Contents, Prefix, SecBegin, DataT::Atoms);
308
7.59k
}
void llvm::emitAppleAccelTable<llvm::AppleAccelTableTypeData>(llvm::AsmPrinter*, llvm::AccelTable<llvm::AppleAccelTableTypeData>&, llvm::StringRef, llvm::MCSymbol const*)
Line
Count
Source
305
2.53k
                         StringRef Prefix, const MCSymbol *SecBegin) {
306
2.53k
  static_assert(std::is_convertible<DataT *, AppleAccelTableData *>::value, "");
307
2.53k
  emitAppleAccelTableImpl(Asm, Contents, Prefix, SecBegin, DataT::Atoms);
308
2.53k
}
309
310
void emitDWARF5AccelTable(AsmPrinter *Asm,
311
                          AccelTable<DWARF5AccelTableData> &Contents,
312
                          const DwarfDebug &DD,
313
                          ArrayRef<std::unique_ptr<DwarfCompileUnit>> CUs);
314
315
void emitDWARF5AccelTable(
316
    AsmPrinter *Asm, AccelTable<DWARF5AccelTableStaticData> &Contents,
317
    ArrayRef<MCSymbol *> CUs,
318
    llvm::function_ref<unsigned(const DWARF5AccelTableStaticData &)>
319
        getCUIndexForEntry);
320
321
/// Accelerator table data implementation for simple Apple accelerator tables
322
/// with just a DIE reference.
323
class AppleAccelTableOffsetData : public AppleAccelTableData {
324
public:
325
342k
  AppleAccelTableOffsetData(const DIE &D) : Die(D) {}
326
327
  void emit(AsmPrinter *Asm) const override;
328
329
#ifndef _MSC_VER
330
  // The line below is rejected by older versions (TBD) of MSVC.
331
  static constexpr Atom Atoms[] = {
332
      Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
333
#else
334
  // FIXME: Erase this path once the minimum MSCV version has been bumped.
335
  static const SmallVector<Atom, 4> Atoms;
336
#endif
337
338
#ifndef NDEBUG
339
  void print(raw_ostream &OS) const override;
340
#endif
341
protected:
342
894k
  uint64_t order() const override { return Die.getOffset(); }
343
344
  const DIE &Die;
345
};
346
347
/// Accelerator table data implementation for Apple type accelerator tables.
348
class AppleAccelTableTypeData : public AppleAccelTableOffsetData {
349
public:
350
796
  AppleAccelTableTypeData(const DIE &D) : AppleAccelTableOffsetData(D) {}
351
352
  void emit(AsmPrinter *Asm) const override;
353
354
#ifndef _MSC_VER
355
  // The line below is rejected by older versions (TBD) of MSVC.
356
  static constexpr Atom Atoms[] = {
357
      Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
358
      Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
359
      Atom(dwarf::DW_ATOM_type_flags, dwarf::DW_FORM_data1)};
360
#else
361
  // FIXME: Erase this path once the minimum MSCV version has been bumped.
362
  static const SmallVector<Atom, 4> Atoms;
363
#endif
364
365
#ifndef NDEBUG
366
  void print(raw_ostream &OS) const override;
367
#endif
368
};
369
370
/// Accelerator table data implementation for simple Apple accelerator tables
371
/// with a DIE offset but no actual DIE pointer.
372
class AppleAccelTableStaticOffsetData : public AppleAccelTableData {
373
public:
374
  AppleAccelTableStaticOffsetData(uint32_t Offset) : Offset(Offset) {}
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
#else
383
  // FIXME: Erase this path once the minimum MSCV version has been bumped.
384
  static const SmallVector<Atom, 4> Atoms;
385
#endif
386
387
#ifndef NDEBUG
388
  void print(raw_ostream &OS) const override;
389
#endif
390
protected:
391
142
  uint64_t order() const override { return Offset; }
392
393
  uint32_t Offset;
394
};
395
396
/// Accelerator table data implementation for type accelerator tables with
397
/// a DIE offset but no actual DIE pointer.
398
class AppleAccelTableStaticTypeData : public AppleAccelTableStaticOffsetData {
399
public:
400
  AppleAccelTableStaticTypeData(uint32_t Offset, uint16_t Tag,
401
                                bool ObjCClassIsImplementation,
402
                                uint32_t QualifiedNameHash)
403
      : AppleAccelTableStaticOffsetData(Offset),
404
        QualifiedNameHash(QualifiedNameHash), Tag(Tag),
405
        ObjCClassIsImplementation(ObjCClassIsImplementation) {}
406
407
  void emit(AsmPrinter *Asm) const override;
408
409
#ifndef _MSC_VER
410
  // The line below is rejected by older versions (TBD) of MSVC.
411
  static constexpr Atom Atoms[] = {
412
      Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
413
      Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
414
      Atom(5, dwarf::DW_FORM_data1), Atom(6, dwarf::DW_FORM_data4)};
415
#else
416
  // FIXME: Erase this path once the minimum MSCV version has been bumped.
417
  static const SmallVector<Atom, 4> Atoms;
418
#endif
419
420
#ifndef NDEBUG
421
  void print(raw_ostream &OS) const override;
422
#endif
423
protected:
424
216
  uint64_t order() const override { return Offset; }
425
426
  uint32_t QualifiedNameHash;
427
  uint16_t Tag;
428
  bool ObjCClassIsImplementation;
429
};
430
431
} // end namespace llvm
432
433
#endif // LLVM_CODEGEN_DWARFACCELTABLE_H