Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/AsmPrinter/DwarfAccelTable.h
Line
Count
Source
1
//==- llvm/CodeGen/DwarfAccelTable.h - Dwarf 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 dwarf accelerator tables.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#ifndef LLVM_LIB_CODEGEN_ASMPRINTER_DWARFACCELTABLE_H
15
#define LLVM_LIB_CODEGEN_ASMPRINTER_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/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 accelerator tables are an indirect hash table optimized
34
// for null lookup rather than access to known data. They are output into
35
// an on-disk format that looks like this:
36
//
37
// .-------------.
38
// |  HEADER     |
39
// |-------------|
40
// |  BUCKETS    |
41
// |-------------|
42
// |  HASHES     |
43
// |-------------|
44
// |  OFFSETS    |
45
// |-------------|
46
// |  DATA       |
47
// `-------------'
48
//
49
// where the header contains a magic number, version, type of hash function,
50
// the number of buckets, total number of hashes, and room for a special
51
// struct of data and the length of that struct.
52
//
53
// The buckets contain an index (e.g. 6) into the hashes array. The hashes
54
// section contains all of the 32-bit hash values in contiguous memory, and
55
// the offsets contain the offset into the data area for the particular
56
// hash.
57
//
58
// For a lookup example, we could hash a function name and take it modulo the
59
// number of buckets giving us our bucket. From there we take the bucket value
60
// as an index into the hashes table and look at each successive hash as long
61
// as the hash value is still the same modulo result (bucket value) as earlier.
62
// If we have a match we look at that same entry in the offsets table and
63
// grab the offset in the data for our final match.
64
65
namespace llvm {
66
67
class AsmPrinter;
68
class DwarfDebug;
69
70
class DwarfAccelTable {
71
  // Helper function to compute the number of buckets needed based on
72
  // the number of unique hashes.
73
  void ComputeBucketCount();
74
75
  struct TableHeader {
76
    uint32_t magic = MagicHash; // 'HASH' magic value to allow endian detection
77
    uint16_t version = 1;       // Version number.
78
    uint16_t hash_function = dwarf::DW_hash_function_djb;
79
    // The hash function enumeration that was used.
80
    uint32_t bucket_count = 0;  // The number of buckets in this hash table.
81
    uint32_t hashes_count = 0;  // The total number of unique hash values
82
                                // and hash data offsets in this table.
83
    uint32_t header_data_len;   // The bytes to skip to get to the hash
84
                                // indexes (buckets) for correct alignment.
85
    // Also written to disk is the implementation specific header data.
86
87
    static const uint32_t MagicHash = 0x48415348;
88
89
132k
    TableHeader(uint32_t data_len) : header_data_len(data_len) {}
90
91
#ifndef NDEBUG
92
    void print(raw_ostream &OS) {
93
      OS << "Magic: " << format("0x%x", magic) << "\n"
94
         << "Version: " << version << "\n"
95
         << "Hash Function: " << hash_function << "\n"
96
         << "Bucket Count: " << bucket_count << "\n"
97
         << "Header Data Length: " << header_data_len << "\n";
98
    }
99
100
    void dump() { print(dbgs()); }
101
#endif
102
  };
103
104
public:
105
  // The HeaderData describes the form of each set of data. In general this
106
  // is as a list of atoms (atom_count) where each atom contains a type
107
  // (AtomType type) of data, and an encoding form (form). In the case of
108
  // data that is referenced via DW_FORM_ref_* the die_offset_base is
109
  // used to describe the offset for all forms in the list of atoms.
110
  // This also serves as a public interface of sorts.
111
  // When written to disk this will have the form:
112
  //
113
  // uint32_t die_offset_base
114
  // uint32_t atom_count
115
  // atom_count Atoms
116
117
  // Make these public so that they can be used as a general interface to
118
  // the class.
119
  struct Atom {
120
    uint16_t type; // enum AtomType
121
    uint16_t form; // DWARF DW_FORM_ defines
122
123
99.1k
    constexpr Atom(uint16_t type, uint16_t form) : type(type), form(form) {}
124
125
#ifndef NDEBUG
126
    void print(raw_ostream &OS) {
127
      OS << "Type: " << dwarf::AtomTypeString(type) << "\n"
128
         << "Form: " << dwarf::FormEncodingString(form) << "\n";
129
    }
130
131
    void dump() { print(dbgs()); }
132
#endif
133
  };
134
135
private:
136
  struct TableHeaderData {
137
    uint32_t die_offset_base;
138
    SmallVector<Atom, 3> Atoms;
139
140
    TableHeaderData(ArrayRef<Atom> AtomList, uint32_t offset = 0)
141
132k
        : die_offset_base(offset), Atoms(AtomList.begin(), AtomList.end()) {}
142
143
#ifndef NDEBUG
144
    void print(raw_ostream &OS) {
145
      OS << "die_offset_base: " << die_offset_base << "\n";
146
      for (size_t i = 0; i < Atoms.size(); i++)
147
        Atoms[i].print(OS);
148
    }
149
150
    void dump() { print(dbgs()); }
151
#endif
152
  };
153
154
  // The data itself consists of a str_offset, a count of the DIEs in the
155
  // hash and the offsets to the DIEs themselves.
156
  // On disk each data section is ended with a 0 KeyType as the end of the
157
  // hash chain.
158
  // On output this looks like:
159
  // uint32_t str_offset
160
  // uint32_t hash_data_count
161
  // HashData[hash_data_count]
162
public:
163
  struct HashDataContents {
164
    const DIE *Die;   // Offsets
165
    char Flags; // Specific flags to output
166
167
44.3k
    HashDataContents(const DIE *D, char Flags) : Die(D), Flags(Flags) {}
168
169
#ifndef NDEBUG
170
    void print(raw_ostream &OS) const {
171
      OS << "  Offset: " << Die->getOffset() << "\n"
172
         << "  Tag: " << dwarf::TagString(Die->getTag()) << "\n"
173
         << "  Flags: " << Flags << "\n";
174
    }
175
#endif
176
  };
177
178
private:
179
  // String Data
180
  struct DataArray {
181
    DwarfStringPoolEntryRef Name;
182
    std::vector<HashDataContents *> Values;
183
  };
184
185
  friend struct HashData;
186
187
  struct HashData {
188
    StringRef Str;
189
    uint32_t HashValue;
190
    MCSymbol *Sym;
191
    DwarfAccelTable::DataArray &Data; // offsets
192
193
    HashData(StringRef S, DwarfAccelTable::DataArray &Data)
194
17.1k
        : Str(S), Data(Data) {
195
17.1k
      HashValue = dwarf::djbHash(S);
196
17.1k
    }
197
198
#ifndef NDEBUG
199
    void print(raw_ostream &OS) {
200
      OS << "Name: " << Str << "\n";
201
      OS << "  Hash Value: " << format("0x%x", HashValue) << "\n";
202
      OS << "  Symbol: ";
203
      if (Sym)
204
        OS << *Sym;
205
      else
206
        OS << "<none>";
207
      OS << "\n";
208
      for (HashDataContents *C : Data.Values) {
209
        OS << "  Offset: " << C->Die->getOffset() << "\n";
210
        OS << "  Tag: " << dwarf::TagString(C->Die->getTag()) << "\n";
211
        OS << "  Flags: " << C->Flags << "\n";
212
      }
213
    }
214
215
    void dump() { print(dbgs()); }
216
#endif
217
  };
218
219
  // Internal Functions
220
  void EmitHeader(AsmPrinter *);
221
  void EmitBuckets(AsmPrinter *);
222
  void EmitHashes(AsmPrinter *);
223
  void emitOffsets(AsmPrinter *, const MCSymbol *);
224
  void EmitData(AsmPrinter *, DwarfDebug *D);
225
226
  // Allocator for HashData and HashDataContents.
227
  BumpPtrAllocator Allocator;
228
229
  // Output Variables
230
  TableHeader Header;
231
  TableHeaderData HeaderData;
232
  std::vector<HashData *> Data;
233
234
  using StringEntries = StringMap<DataArray, BumpPtrAllocator &>;
235
236
  StringEntries Entries;
237
238
  // Buckets/Hashes/Offsets
239
  using HashList = std::vector<HashData *>;
240
  using BucketList = std::vector<HashList>;
241
  BucketList Buckets;
242
  HashList Hashes;
243
244
  // Public Implementation
245
public:
246
  DwarfAccelTable(ArrayRef<DwarfAccelTable::Atom>);
247
  DwarfAccelTable(const DwarfAccelTable &) = delete;
248
  DwarfAccelTable &operator=(const DwarfAccelTable &) = delete;
249
250
  void AddName(DwarfStringPoolEntryRef Name, const DIE *Die, char Flags = 0);
251
  void FinalizeTable(AsmPrinter *, StringRef);
252
  void emit(AsmPrinter *, const MCSymbol *, DwarfDebug *);
253
#ifndef NDEBUG
254
  void print(raw_ostream &OS);
255
  void dump() { print(dbgs()); }
256
#endif
257
};
258
259
} // end namespace llvm
260
261
#endif // LLVM_LIB_CODEGEN_ASMPRINTER_DWARFACCELTABLE_H