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