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