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