contrib/llvm/lib/CodeGen/AsmPrinter/DwarfAccelTable.cpp

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