DwarfAccelTable.h revision 4302a4965c4fffcecee23210dd1910d8d2c88259 
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 CODEGEN_ASMPRINTER_DWARFACCELTABLE_H__
15#define CODEGEN_ASMPRINTER_DWARFACCELTABLE_H__
16
17#include "llvm/ADT/StringMap.h"
18#include "llvm/MC/MCSymbol.h"
19#include "llvm/Support/Dwarf.h"
20#include "llvm/Support/DataTypes.h"
21#include "llvm/Support/Debug.h"
22#include "llvm/Support/ErrorHandling.h"
23#include "llvm/Support/Format.h"
24#include "llvm/Support/FormattedStream.h"
25#include "DIE.h"
26#include <vector>
27#include <map>
28
29// The dwarf accelerator tables are an indirect hash table optimized
30// for null lookup rather than access to known data. They are output into
31// an on-disk format that looks like this:
32//
33// .-------------.
34// |  HEADER     |
35// |-------------|
36// |  BUCKETS    |
37// |-------------|
38// |  HASHES     |
39// |-------------|
40// |  OFFSETS    |
41// |-------------|
42// |  DATA       |
43// `-------------'
44//
45// where the header contains a magic number, version, type of hash function,
46// the number of buckets, total number of hashes, and room for a special
47// struct of data and the length of that struct.
48//
49// The buckets contain an index (e.g. 6) into the hashes array. The hashes
50// section contains all of the 32-bit hash values in contiguous memory, and
51// the offsets contain the offset into the data area for the particular
52// hash.
53//
54// For a lookup example, we could hash a function name and take it modulo the
55// number of buckets giving us our bucket. From there we take the bucket value
56// as an index into the hashes table and look at each successive hash as long
57// as the hash value is still the same modulo result (bucket value) as earlier.
58// If we have a match we look at that same entry in the offsets table and
59// grab the offset in the data for our final match.
60
61namespace llvm {
62
63class AsmPrinter;
64class DIE;
65class DwarfDebug;
66
67class DwarfAccelTable {
68
69  enum HashFunctionType {
70    eHashFunctionDJB = 0u
71  };
72
73  static uint32_t HashDJB (StringRef Str) {
74    uint32_t h = 5381;
75    for (unsigned i = 0, e = Str.size(); i != e; ++i)
76      h = ((h << 5) + h) + Str[i];
77    return h;
78  }
79
80  // Helper function to compute the number of buckets needed based on
81  // the number of unique hashes.
82  void ComputeBucketCount (void);
83
84  struct TableHeader {
85    uint32_t   magic;           // 'HASH' magic value to allow endian detection
86    uint16_t   version;         // Version number.
87    uint16_t   hash_function;   // The hash function enumeration that was used.
88    uint32_t   bucket_count;    // The number of buckets in this hash table.
89    uint32_t   hashes_count;    // The total number of unique hash values
90                                // and hash data offsets in this table.
91    uint32_t   header_data_len; // The bytes to skip to get to the hash
92                                // indexes (buckets) for correct alignment.
93    // Also written to disk is the implementation specific header data.
94
95    static const uint32_t MagicHash = 0x48415348;
96
97    TableHeader (uint32_t data_len) :
98      magic (MagicHash), version (1), hash_function (eHashFunctionDJB),
99      bucket_count (0), hashes_count (0), header_data_len (data_len)
100    {}
101
102#ifndef NDEBUG
103    void print(raw_ostream &O) {
104      O << "Magic: " << format("0x%x", magic) << "\n"
105        << "Version: " << version << "\n"
106        << "Hash Function: " << hash_function << "\n"
107        << "Bucket Count: " << bucket_count << "\n"
108        << "Header Data Length: " << header_data_len << "\n";
109    }
110    void dump() { print(dbgs()); }
111#endif
112  };
113
114public:
115  // The HeaderData describes the form of each set of data. In general this
116  // is as a list of atoms (atom_count) where each atom contains a type
117  // (AtomType type) of data, and an encoding form (form). In the case of
118  // data that is referenced via DW_FORM_ref_* the die_offset_base is
119  // used to describe the offset for all forms in the list of atoms.
120  // This also serves as a public interface of sorts.
121  // When written to disk this will have the form:
122  //
123  // uint32_t die_offset_base
124  // uint32_t atom_count
125  // atom_count Atoms
126  enum AtomType {
127    eAtomTypeNULL       = 0u,
128    eAtomTypeDIEOffset  = 1u,   // DIE offset, check form for encoding
129    eAtomTypeCUOffset   = 2u,   // DIE offset of the compiler unit header that
130                                // contains the item in question
131    eAtomTypeTag        = 3u,   // DW_TAG_xxx value, should be encoded as
132                                // DW_FORM_data1 (if no tags exceed 255) or
133                                // DW_FORM_data2.
134    eAtomTypeNameFlags  = 4u,   // Flags from enum NameFlags
135    eAtomTypeTypeFlags  = 5u    // Flags from enum TypeFlags
136  };
137
138  enum TypeFlags {
139    eTypeFlagClassMask = 0x0000000fu,
140
141    // Always set for C++, only set for ObjC if this is the
142    // @implementation for a class.
143    eTypeFlagClassIsImplementation  = ( 1u << 1 )
144  };
145
146  // Make these public so that they can be used as a general interface to
147  // the class.
148  struct Atom {
149    AtomType type; // enum AtomType
150    uint16_t form; // DWARF DW_FORM_ defines
151
152    Atom(AtomType type, uint16_t form) : type(type), form(form) {}
153    static const char * AtomTypeString(enum AtomType);
154#ifndef NDEBUG
155    void print(raw_ostream &O) {
156      O << "Type: " << AtomTypeString(type) << "\n"
157        << "Form: " << dwarf::FormEncodingString(form) << "\n";
158    }
159    void dump() {
160      print(dbgs());
161    }
162#endif
163  };
164
165 private:
166  struct TableHeaderData {
167
168    uint32_t die_offset_base;
169    std::vector<Atom> Atoms;
170
171    TableHeaderData(std::vector<DwarfAccelTable::Atom> &AtomList,
172                    uint32_t offset = 0) :
173      die_offset_base(offset) {
174      for (size_t i = 0, e = AtomList.size(); i != e; ++i)
175        Atoms.push_back(AtomList[i]);
176    }
177
178    TableHeaderData(DwarfAccelTable::Atom Atom, uint32_t offset = 0)
179    : die_offset_base(offset) {
180      Atoms.push_back(Atom);
181    }
182
183#ifndef NDEBUG
184    void print (raw_ostream &O) {
185      O << "die_offset_base: " << die_offset_base << "\n";
186      for (size_t i = 0; i < Atoms.size(); i++)
187        Atoms[i].print(O);
188    }
189    void dump() {
190      print(dbgs());
191    }
192#endif
193  };
194
195  // The data itself consists of a str_offset, a count of the DIEs in the
196  // hash and the offsets to the DIEs themselves.
197  // On disk each data section is ended with a 0 KeyType as the end of the
198  // hash chain.
199  // On output this looks like:
200  // uint32_t str_offset
201  // uint32_t hash_data_count
202  // HashData[hash_data_count]
203public:
204  struct HashDataContents {
205    DIE *Die; // Offsets
206    char Flags; // Specific flags to output
207
208    HashDataContents(DIE *D, char Flags) :
209      Die(D),
210      Flags(Flags) { }
211    #ifndef NDEBUG
212    void print(raw_ostream &O) const {
213      O << "  Offset: " << Die->getOffset() << "\n";
214      O << "  Tag: " << dwarf::TagString(Die->getTag()) << "\n";
215      O << "  Flags: " << Flags << "\n";
216    }
217    #endif
218  };
219private:
220  struct HashData {
221    StringRef Str;
222    uint32_t HashValue;
223    MCSymbol *Sym;
224    std::vector<struct HashDataContents*> Data; // offsets
225    HashData(StringRef S) : Str(S) {
226      HashValue = DwarfAccelTable::HashDJB(S);
227    }
228    void addData(struct HashDataContents *Datum) { Data.push_back(Datum); }
229    #ifndef NDEBUG
230    void print(raw_ostream &O) {
231      O << "Name: " << Str << "\n";
232      O << "  Hash Value: " << format("0x%x", HashValue) << "\n";
233      O << "  Symbol: " ;
234      if (Sym) Sym->print(O);
235      else O << "<none>";
236      O << "\n";
237      for (size_t i = 0; i < Data.size(); i++) {
238        O << "  Offset: " << Data[i]->Die->getOffset() << "\n";
239        O << "  Tag: " << dwarf::TagString(Data[i]->Die->getTag()) << "\n";
240        O << "  Flags: " << Data[i]->Flags << "\n";
241      }
242    }
243    void dump() {
244      print(dbgs());
245    }
246    #endif
247  };
248
249  DwarfAccelTable(const DwarfAccelTable&); // DO NOT IMPLEMENT
250  void operator=(const DwarfAccelTable&);  // DO NOT IMPLEMENT
251
252  // Internal Functions
253  void EmitHeader(AsmPrinter *);
254  void EmitBuckets(AsmPrinter *);
255  void EmitHashes(AsmPrinter *);
256  void EmitOffsets(AsmPrinter *, MCSymbol *);
257  void EmitData(AsmPrinter *, DwarfDebug *D);
258
259  // Output Variables
260  TableHeader Header;
261  TableHeaderData HeaderData;
262  std::vector<HashData*> Data;
263
264  // String Data
265  typedef std::vector<struct HashDataContents*> DataArray;
266  typedef StringMap<DataArray> StringEntries;
267  StringEntries Entries;
268
269  // Buckets/Hashes/Offsets
270  typedef std::vector<HashData*> HashList;
271  typedef std::vector<HashList> BucketList;
272  BucketList Buckets;
273  HashList Hashes;
274
275  // Public Implementation
276 public:
277  DwarfAccelTable(DwarfAccelTable::Atom);
278  DwarfAccelTable(std::vector<DwarfAccelTable::Atom> &);
279  ~DwarfAccelTable();
280  void AddName(StringRef, DIE*, char = 0);
281  void FinalizeTable(AsmPrinter *, const char *);
282  void Emit(AsmPrinter *, MCSymbol *, DwarfDebug *);
283#ifndef NDEBUG
284  void print(raw_ostream &O);
285  void dump() { print(dbgs()); }
286#endif
287};
288
289}
290#endif
291