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