LLVM  6.0.0svn
DwarfAccelTable.cpp
Go to the documentation of this file.
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"
20 #include "llvm/CodeGen/DIE.h"
21 #include "llvm/MC/MCExpr.h"
22 #include "llvm/MC/MCStreamer.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.
36  : Header(8 + (atomList.size() * 4)), HeaderData(atomList),
37  Entries(Allocator) {}
38 
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.
74  return A->Die->getOffset() < B->Die->getOffset();
75 }
76 
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
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
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
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:244
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
LLVMContext & Context
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:235
std::unique_ptr< MCStreamer > OutStreamer
This is the MCStreamer object for the file we are generating.
Definition: AsmPrinter.h:92
static const MCSymbolRefExpr * create(const MCSymbol *Symbol, MCContext &Ctx)
Definition: MCExpr.h:305
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
StringRef AtomTypeString(unsigned Atom)
Definition: Dwarf.cpp:490
void EmitInt8(int Value) const
Emit a byte directive and value.
MCSymbol - Instances of this class represent a symbol name in the MC file, and MCSymbols are created ...
Definition: MCSymbol.h:42
Collects and handles dwarf debug information.
Definition: DwarfDebug.h:196
void emit(AsmPrinter *, const MCSymbol *, DwarfDebug *)
void print(raw_ostream &OS) const
void emitDwarfStringOffset(DwarfStringPoolEntryRef S) const
Emit the 4-byte offset of a string from the start of its section.
unsigned size() const
Definition: StringMap.h:112
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
StringRef FormEncodingString(unsigned Encoding)
Definition: Dwarf.cpp:105
String pool entry reference.
DwarfAccelTable(ArrayRef< DwarfAccelTable::Atom >)
Base class for the full range of assembler expressions which are needed for parsing.
Definition: MCExpr.h:36
Context object for machine code objects.
Definition: MCContext.h:59
static const MCBinaryExpr * createSub(const MCExpr *LHS, const MCExpr *RHS, MCContext &Ctx)
Definition: MCExpr.h:528
void FinalizeTable(AsmPrinter *, StringRef)
void EmitInt16(int Value) const
Emit a short directive and value.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
void AddName(DwarfStringPoolEntryRef Name, const DIE *Die, char Flags=0)
void EmitInt32(int Value) const
Emit a long directive and value.
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
Definition: STLExtras.h:713
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
A structured debug information entry.
Definition: DIE.h:662
This class is intended to be used as a driving class for all asm writers.
Definition: AsmPrinter.h:77
static bool compareDIEs(const DwarfAccelTable::HashDataContents *A, const DwarfAccelTable::HashDataContents *B)
Basic Register Allocator
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
This file contains constants used for implementing Dwarf debug support.
dwarf::Tag getTag() const
Definition: DIE.h:698
iterator begin()
Definition: StringMap.h:319
void print(raw_ostream &OS)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
unsigned getOffset() const
Get the compile/type unit relative offset of this DIE.
Definition: DIE.h:700
unsigned getDebugSectionOffset() const
Get the absolute offset within the .debug_info or .debug_types section for this DIE.
Definition: DIE.cpp:196
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
MCSymbol * createTempSymbol(const Twine &Name) const
iterator end()
Definition: StringMap.h:322