lib/CodeGen/AsmPrinter/DwarfAccelTable.h

   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
  61 namespace llvm {
  62
  63 class AsmPrinter;
  64 class DIE;
  65 class DwarfDebug;
  66
  67 class 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
 114 public:
 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]
 203 public:
 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   };
 219 private:
 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