LLVM  6.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/Debug.h"
27 #include "llvm/Support/Format.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 
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  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  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  : 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:
164  const DIE *Die; // Offsets
165  char Flags; // Specific flags to output
166 
167  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 {
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  : Str(S), Data(Data) {
195  HashValue = dwarf::djbHash(S);
196  }
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.
228 
229  // Output Variables
230  TableHeader Header;
231  TableHeaderData HeaderData;
232  std::vector<HashData *> Data;
233 
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:
247  DwarfAccelTable(const DwarfAccelTable &) = delete;
248  DwarfAccelTable &operator=(const DwarfAccelTable &) = delete;
249 
250  void AddName(DwarfStringPoolEntryRef Name, const DIE *Die, char Flags = 0);
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
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:138
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
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:864
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:224
This file contains constants used for implementing Dwarf debug support.
uint32_t djbHash(StringRef Buffer)
The Bernstein hash function used by the accelerator tables.
Definition: Dwarf.cpp:579
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