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