lib/CodeGen/AsmPrinter/DwarfAccelTable.cpp

   1 //=-- llvm/CodeGen/DwarfAccelTable.cpp - 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 #include "DwarfAccelTable.h"
  15 #include "DwarfDebug.h"
  16 #include "DIE.h"
  17 #include "llvm/ADT/Twine.h"
  18 #include "llvm/ADT/STLExtras.h"
  19 #include "llvm/CodeGen/AsmPrinter.h"
  20 #include "llvm/MC/MCExpr.h"
  21 #include "llvm/MC/MCStreamer.h"
  22 #include "llvm/MC/MCSymbol.h"
  23 #include "llvm/Support/Debug.h"
  24
  25 using namespace llvm;
  26
  27 const char *DwarfAccelTable::Atom::AtomTypeString(enum AtomType AT) {
  28   switch (AT) {
  29   case eAtomTypeNULL: return "eAtomTypeNULL";
  30   case eAtomTypeDIEOffset: return "eAtomTypeDIEOffset";
  31   case eAtomTypeCUOffset: return "eAtomTypeCUOffset";
  32   case eAtomTypeTag: return "eAtomTypeTag";
  33   case eAtomTypeNameFlags: return "eAtomTypeNameFlags";
  34   case eAtomTypeTypeFlags: return "eAtomTypeTypeFlags";
  35   }
  36   llvm_unreachable("invalid AtomType!");
  37 }
  38
  39 // The general case would need to have a less hard coded size for the
  40 // length of the HeaderData, however, if we're constructing based on a
  41 // single Atom then we know it will always be: 4 + 4 + 2 + 2.
  42 DwarfAccelTable::DwarfAccelTable(DwarfAccelTable::Atom atom) :
  43   Header(12),
  44   HeaderData(atom) {
  45 }
  46
  47 // The length of the header data is always going to be 4 + 4 + 4*NumAtoms.
  48 DwarfAccelTable::DwarfAccelTable(std::vector<DwarfAccelTable::Atom> &atomList) :
  49   Header(8 + (atomList.size() * 4)),
  50   HeaderData(atomList) {
  51 }
  52
  53 DwarfAccelTable::~DwarfAccelTable() {
  54   for (size_t i = 0, e = Data.size(); i < e; ++i)
  55     delete Data[i];
  56   for (StringMap<DataArray>::iterator
  57          EI = Entries.begin(), EE = Entries.end(); EI != EE; ++EI)
  58     for (DataArray::iterator DI = EI->second.begin(),
  59            DE = EI->second.end(); DI != DE; ++DI)
  60       delete (*DI);
  61 }
  62
  63 void DwarfAccelTable::AddName(StringRef Name, DIE* die, char Flags) {
  64   // If the string is in the list already then add this die to the list
  65   // otherwise add a new one.
  66   DataArray &DIEs = Entries[Name];
  67   DIEs.push_back(new HashDataContents(die, Flags));
  68 }
  69
  70 void DwarfAccelTable::ComputeBucketCount(void) {
  71   // First get the number of unique hashes.
  72   std::vector<uint32_t> uniques(Data.size());
  73   for (size_t i = 0, e = Data.size(); i < e; ++i)
  74     uniques[i] = Data[i]->HashValue;
  75   array_pod_sort(uniques.begin(), uniques.end());
  76   std::vector<uint32_t>::iterator p =
  77     std::unique(uniques.begin(), uniques.end());
  78   uint32_t num = std::distance(uniques.begin(), p);
  79
  80   // Then compute the bucket size, minimum of 1 bucket.
  81   if (num > 1024) Header.bucket_count = num/4;
  82   if (num > 16) Header.bucket_count = num/2;
  83   else Header.bucket_count = num > 0 ? num : 1;
  84
  85   Header.hashes_count = num;
  86 }
  87
  88 namespace {
  89   // DIESorter - comparison predicate that sorts DIEs by their offset.
  90   struct DIESorter {
  91     bool operator()(const struct DwarfAccelTable::HashDataContents *A,
  92                     const struct DwarfAccelTable::HashDataContents *B) const {
  93       return A->Die->getOffset() < B->Die->getOffset();
  94     }
  95   };
  96 }
  97
  98 void DwarfAccelTable::FinalizeTable(AsmPrinter *Asm, const char *Prefix) {
  99   // Create the individual hash data outputs.
 100   for (StringMap<DataArray>::iterator
 101          EI = Entries.begin(), EE = Entries.end(); EI != EE; ++EI) {
 102     struct HashData *Entry = new HashData((*EI).getKeyData());
 103
 104     // Unique the entries.
 105     std::stable_sort(EI->second.begin(), EI->second.end(), DIESorter());
 106     EI->second.erase(std::unique(EI->second.begin(), EI->second.end()),
 107                        EI->second.end());
 108
 109     for (DataArray::const_iterator DI = EI->second.begin(),
 110            DE = EI->second.end();
 111          DI != DE; ++DI)
 112       Entry->addData((*DI));
 113     Data.push_back(Entry);
 114   }
 115
 116   // Figure out how many buckets we need, then compute the bucket
 117   // contents and the final ordering. We'll emit the hashes and offsets
 118   // by doing a walk during the emission phase. We add temporary
 119   // symbols to the data so that we can reference them during the offset
 120   // later, we'll emit them when we emit the data.
 121   ComputeBucketCount();
 122
 123   // Compute bucket contents and final ordering.
 124   Buckets.resize(Header.bucket_count);
 125   for (size_t i = 0, e = Data.size(); i < e; ++i) {
 126     uint32_t bucket = Data[i]->HashValue % Header.bucket_count;
 127     Buckets[bucket].push_back(Data[i]);
 128     Data[i]->Sym = Asm->GetTempSymbol(Prefix, i);
 129   }
 130 }
 131
 132 // Emits the header for the table via the AsmPrinter.
 133 void DwarfAccelTable::EmitHeader(AsmPrinter *Asm) {
 134   Asm->OutStreamer.AddComment("Header Magic");
 135   Asm->EmitInt32(Header.magic);
 136   Asm->OutStreamer.AddComment("Header Version");
 137   Asm->EmitInt16(Header.version);
 138   Asm->OutStreamer.AddComment("Header Hash Function");
 139   Asm->EmitInt16(Header.hash_function);
 140   Asm->OutStreamer.AddComment("Header Bucket Count");
 141   Asm->EmitInt32(Header.bucket_count);
 142   Asm->OutStreamer.AddComment("Header Hash Count");
 143   Asm->EmitInt32(Header.hashes_count);
 144   Asm->OutStreamer.AddComment("Header Data Length");
 145   Asm->EmitInt32(Header.header_data_len);
 146   Asm->OutStreamer.AddComment("HeaderData Die Offset Base");
 147   Asm->EmitInt32(HeaderData.die_offset_base);
 148   Asm->OutStreamer.AddComment("HeaderData Atom Count");
 149   Asm->EmitInt32(HeaderData.Atoms.size());
 150   for (size_t i = 0; i < HeaderData.Atoms.size(); i++) {
 151     Atom A = HeaderData.Atoms[i];
 152     Asm->OutStreamer.AddComment(Atom::AtomTypeString(A.type));
 153     Asm->EmitInt16(A.type);
 154     Asm->OutStreamer.AddComment(dwarf::FormEncodingString(A.form));
 155     Asm->EmitInt16(A.form);
 156   }
 157 }
 158
 159 // Walk through and emit the buckets for the table. This will look
 160 // like a list of numbers of how many elements are in each bucket.
 161 void DwarfAccelTable::EmitBuckets(AsmPrinter *Asm) {
 162   unsigned index = 0;
 163   for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
 164     Asm->OutStreamer.AddComment("Bucket " + Twine(i));
 165     if (Buckets[i].size() != 0)
 166       Asm->EmitInt32(index);
 167     else
 168       Asm->EmitInt32(UINT32_MAX);
 169     index += Buckets[i].size();
 170   }
 171 }
 172
 173 // Walk through the buckets and emit the individual hashes for each
 174 // bucket.
 175 void DwarfAccelTable::EmitHashes(AsmPrinter *Asm) {
 176   for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
 177     for (HashList::const_iterator HI = Buckets[i].begin(),
 178            HE = Buckets[i].end(); HI != HE; ++HI) {
 179       Asm->OutStreamer.AddComment("Hash in Bucket " + Twine(i));
 180       Asm->EmitInt32((*HI)->HashValue);
 181     }
 182   }
 183 }
 184
 185 // Walk through the buckets and emit the individual offsets for each
 186 // element in each bucket. This is done via a symbol subtraction from the
 187 // beginning of the section. The non-section symbol will be output later
 188 // when we emit the actual data.
 189 void DwarfAccelTable::EmitOffsets(AsmPrinter *Asm, MCSymbol *SecBegin) {
 190   for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
 191     for (HashList::const_iterator HI = Buckets[i].begin(),
 192            HE = Buckets[i].end(); HI != HE; ++HI) {
 193       Asm->OutStreamer.AddComment("Offset in Bucket " + Twine(i));
 194       MCContext &Context = Asm->OutStreamer.getContext();
 195       const MCExpr *Sub =
 196         MCBinaryExpr::CreateSub(MCSymbolRefExpr::Create((*HI)->Sym, Context),
 197                                 MCSymbolRefExpr::Create(SecBegin, Context),
 198                                 Context);
 199       Asm->OutStreamer.EmitValue(Sub, sizeof(uint32_t), 0);
 200     }
 201   }
 202 }
 203
 204 // Walk through the buckets and emit the full data for each element in
 205 // the bucket. For the string case emit the dies and the various offsets.
 206 // Terminate each HashData bucket with 0.
 207 void DwarfAccelTable::EmitData(AsmPrinter *Asm, DwarfDebug *D) {
 208   uint64_t PrevHash = UINT64_MAX;
 209   for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
 210     for (HashList::const_iterator HI = Buckets[i].begin(),
 211            HE = Buckets[i].end(); HI != HE; ++HI) {
 212       // Remember to emit the label for our offset.
 213       Asm->OutStreamer.EmitLabel((*HI)->Sym);
 214       Asm->OutStreamer.AddComment((*HI)->Str);
 215       Asm->EmitSectionOffset(D->getStringPoolEntry((*HI)->Str),
 216                              D->getStringPool());
 217       Asm->OutStreamer.AddComment("Num DIEs");
 218       Asm->EmitInt32((*HI)->Data.size());
 219       for (std::vector<struct HashDataContents*>::const_iterator
 220              DI = (*HI)->Data.begin(), DE = (*HI)->Data.end();
 221            DI != DE; ++DI) {
 222         // Emit the DIE offset
 223         Asm->EmitInt32((*DI)->Die->getOffset());
 224         // If we have multiple Atoms emit that info too.
 225         // FIXME: A bit of a hack, we either emit only one atom or all info.
 226         if (HeaderData.Atoms.size() > 1) {
 227           Asm->EmitInt16((*DI)->Die->getTag());
 228           Asm->EmitInt8((*DI)->Flags);
 229         }
 230       }
 231       // Emit a 0 to terminate the data unless we have a hash collision.
 232       if (PrevHash != (*HI)->HashValue)
 233         Asm->EmitInt32(0);
 234       PrevHash = (*HI)->HashValue;
 235     }
 236   }
 237 }
 238
 239 // Emit the entire data structure to the output file.
 240 void DwarfAccelTable::Emit(AsmPrinter *Asm, MCSymbol *SecBegin,
 241                            DwarfDebug *D) {
 242   // Emit the header.
 243   EmitHeader(Asm);
 244
 245   // Emit the buckets.
 246   EmitBuckets(Asm);
 247
 248   // Emit the hashes.
 249   EmitHashes(Asm);
 250
 251   // Emit the offsets.
 252   EmitOffsets(Asm, SecBegin);
 253
 254   // Emit the hash data.
 255   EmitData(Asm, D);
 256 }
 257
 258 #ifndef NDEBUG
 259 void DwarfAccelTable::print(raw_ostream &O) {
 260
 261   Header.print(O);
 262   HeaderData.print(O);
 263
 264   O << "Entries: \n";
 265   for (StringMap<DataArray>::const_iterator
 266          EI = Entries.begin(), EE = Entries.end(); EI != EE; ++EI) {
 267     O << "Name: " << EI->getKeyData() << "\n";
 268     for (DataArray::const_iterator DI = EI->second.begin(),
 269            DE = EI->second.end();
 270          DI != DE; ++DI)
 271       (*DI)->print(O);
 272   }
 273
 274   O << "Buckets and Hashes: \n";
 275   for (size_t i = 0, e = Buckets.size(); i < e; ++i)
 276     for (HashList::const_iterator HI = Buckets[i].begin(),
 277            HE = Buckets[i].end(); HI != HE; ++HI)
 278       (*HI)->print(O);
 279
 280   O << "Data: \n";
 281     for (std::vector<HashData*>::const_iterator
 282            DI = Data.begin(), DE = Data.end(); DI != DE; ++DI)
 283       (*DI)->print(O);
 284
 285
 286 }
 287 #endif