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