1 //===- llvm/CodeGen/AsmPrinter/AccelTable.cpp - 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 accelerator tables. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/CodeGen/AccelTable.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 <cstddef> 26 #include <cstdint> 27 #include <limits> 28 #include <vector> 29 30 using namespace llvm; 31 32 void AppleAccelTableHeader::emit(AsmPrinter *Asm) { 33 // Emit Header. 34 Asm->OutStreamer->AddComment("Header Magic"); 35 Asm->EmitInt32(Header.Magic); 36 Asm->OutStreamer->AddComment("Header Version"); 37 Asm->EmitInt16(Header.Version); 38 Asm->OutStreamer->AddComment("Header Hash Function"); 39 Asm->EmitInt16(Header.HashFunction); 40 Asm->OutStreamer->AddComment("Header Bucket Count"); 41 Asm->EmitInt32(Header.BucketCount); 42 Asm->OutStreamer->AddComment("Header Hash Count"); 43 Asm->EmitInt32(Header.HashCount); 44 Asm->OutStreamer->AddComment("Header Data Length"); 45 Asm->EmitInt32(Header.HeaderDataLength); 46 47 // Emit Header Data 48 Asm->OutStreamer->AddComment("HeaderData Die Offset Base"); 49 Asm->EmitInt32(HeaderData.DieOffsetBase); 50 Asm->OutStreamer->AddComment("HeaderData Atom Count"); 51 Asm->EmitInt32(HeaderData.Atoms.size()); 52 53 for (size_t i = 0; i < HeaderData.Atoms.size(); i++) { 54 Atom A = HeaderData.Atoms[i]; 55 Asm->OutStreamer->AddComment(dwarf::AtomTypeString(A.Type)); 56 Asm->EmitInt16(A.Type); 57 Asm->OutStreamer->AddComment(dwarf::FormEncodingString(A.Form)); 58 Asm->EmitInt16(A.Form); 59 } 60 } 61 62 void AppleAccelTableHeader::setBucketAndHashCount(uint32_t HashCount) { 63 if (HashCount > 1024) 64 Header.BucketCount = HashCount / 4; 65 else if (HashCount > 16) 66 Header.BucketCount = HashCount / 2; 67 else 68 Header.BucketCount = HashCount > 0 ? HashCount : 1; 69 70 Header.HashCount = HashCount; 71 } 72 73 void AppleAccelTableBase::emitHeader(AsmPrinter *Asm) { Header.emit(Asm); } 74 75 void AppleAccelTableBase::emitBuckets(AsmPrinter *Asm) { 76 unsigned index = 0; 77 for (size_t i = 0, e = Buckets.size(); i < e; ++i) { 78 Asm->OutStreamer->AddComment("Bucket " + Twine(i)); 79 if (!Buckets[i].empty()) 80 Asm->EmitInt32(index); 81 else 82 Asm->EmitInt32(std::numeric_limits<uint32_t>::max()); 83 // Buckets point in the list of hashes, not to the data. Do not increment 84 // the index multiple times in case of hash collisions. 85 uint64_t PrevHash = std::numeric_limits<uint64_t>::max(); 86 for (auto *HD : Buckets[i]) { 87 uint32_t HashValue = HD->HashValue; 88 if (PrevHash != HashValue) 89 ++index; 90 PrevHash = HashValue; 91 } 92 } 93 } 94 95 void AppleAccelTableBase::emitHashes(AsmPrinter *Asm) { 96 uint64_t PrevHash = std::numeric_limits<uint64_t>::max(); 97 unsigned BucketIdx = 0; 98 for (auto &Bucket : Buckets) { 99 for (auto &Hash : Bucket) { 100 uint32_t HashValue = Hash->HashValue; 101 if (PrevHash == HashValue) 102 continue; 103 Asm->OutStreamer->AddComment("Hash in Bucket " + Twine(BucketIdx)); 104 Asm->EmitInt32(HashValue); 105 PrevHash = HashValue; 106 } 107 BucketIdx++; 108 } 109 } 110 111 void AppleAccelTableBase::emitOffsets(AsmPrinter *Asm, 112 const MCSymbol *SecBegin) { 113 uint64_t PrevHash = std::numeric_limits<uint64_t>::max(); 114 for (size_t i = 0, e = Buckets.size(); i < e; ++i) { 115 for (auto HI = Buckets[i].begin(), HE = Buckets[i].end(); HI != HE; ++HI) { 116 uint32_t HashValue = (*HI)->HashValue; 117 if (PrevHash == HashValue) 118 continue; 119 PrevHash = HashValue; 120 Asm->OutStreamer->AddComment("Offset in Bucket " + Twine(i)); 121 MCContext &Context = Asm->OutStreamer->getContext(); 122 const MCExpr *Sub = MCBinaryExpr::createSub( 123 MCSymbolRefExpr::create((*HI)->Sym, Context), 124 MCSymbolRefExpr::create(SecBegin, Context), Context); 125 Asm->OutStreamer->EmitValue(Sub, sizeof(uint32_t)); 126 } 127 } 128 } 129 130 void AppleAccelTableBase::emitData(AsmPrinter *Asm) { 131 for (size_t i = 0, e = Buckets.size(); i < e; ++i) { 132 uint64_t PrevHash = std::numeric_limits<uint64_t>::max(); 133 for (auto &Hash : Buckets[i]) { 134 // Terminate the previous entry if there is no hash collision with the 135 // current one. 136 if (PrevHash != std::numeric_limits<uint64_t>::max() && 137 PrevHash != Hash->HashValue) 138 Asm->EmitInt32(0); 139 // Remember to emit the label for our offset. 140 Asm->OutStreamer->EmitLabel(Hash->Sym); 141 Asm->OutStreamer->AddComment(Hash->Str); 142 Asm->emitDwarfStringOffset(Hash->Data.Name); 143 Asm->OutStreamer->AddComment("Num DIEs"); 144 Asm->EmitInt32(Hash->Data.Values.size()); 145 for (const auto *V : Hash->Data.Values) { 146 V->emit(Asm); 147 } 148 PrevHash = Hash->HashValue; 149 } 150 // Emit the final end marker for the bucket. 151 if (!Buckets[i].empty()) 152 Asm->EmitInt32(0); 153 } 154 } 155 156 void AppleAccelTableBase::computeBucketCount() { 157 // First get the number of unique hashes. 158 std::vector<uint32_t> uniques(Data.size()); 159 for (size_t i = 0, e = Data.size(); i < e; ++i) 160 uniques[i] = Data[i]->HashValue; 161 array_pod_sort(uniques.begin(), uniques.end()); 162 std::vector<uint32_t>::iterator p = 163 std::unique(uniques.begin(), uniques.end()); 164 165 // Compute the hashes count and use it to set that together with the bucket 166 // count in the header. 167 Header.setBucketAndHashCount(std::distance(uniques.begin(), p)); 168 } 169 170 void AppleAccelTableBase::finalizeTable(AsmPrinter *Asm, StringRef Prefix) { 171 // Create the individual hash data outputs. 172 Data.reserve(Entries.size()); 173 for (auto &E : Entries) { 174 // Unique the entries. 175 std::stable_sort(E.second.Values.begin(), E.second.Values.end(), 176 [](const AppleAccelTableData *A, 177 const AppleAccelTableData *B) { return *A < *B; }); 178 E.second.Values.erase( 179 std::unique(E.second.Values.begin(), E.second.Values.end()), 180 E.second.Values.end()); 181 182 HashData *Entry = new (Allocator) HashData(E.first(), E.second); 183 Data.push_back(Entry); 184 } 185 186 // Figure out how many buckets we need, then compute the bucket contents and 187 // the final ordering. We'll emit the hashes and offsets by doing a walk 188 // during the emission phase. We add temporary symbols to the data so that we 189 // can reference them during the offset later, we'll emit them when we emit 190 // the data. 191 computeBucketCount(); 192 193 // Compute bucket contents and final ordering. 194 Buckets.resize(Header.getBucketCount()); 195 for (auto &D : Data) { 196 uint32_t bucket = D->HashValue % Header.getBucketCount(); 197 Buckets[bucket].push_back(D); 198 D->Sym = Asm->createTempSymbol(Prefix); 199 } 200 201 // Sort the contents of the buckets by hash value so that hash collisions end 202 // up together. Stable sort makes testing easier and doesn't cost much more. 203 for (auto &Bucket : Buckets) 204 std::stable_sort(Bucket.begin(), Bucket.end(), 205 [](HashData *LHS, HashData *RHS) { 206 return LHS->HashValue < RHS->HashValue; 207 }); 208 } 209 210 void AppleAccelTableOffsetData::emit(AsmPrinter *Asm) const { 211 Asm->EmitInt32(Die->getDebugSectionOffset()); 212 } 213 214 void AppleAccelTableTypeData::emit(AsmPrinter *Asm) const { 215 Asm->EmitInt32(Die->getDebugSectionOffset()); 216 Asm->EmitInt16(Die->getTag()); 217 Asm->EmitInt8(0); 218 } 219 220 void AppleAccelTableStaticOffsetData::emit(AsmPrinter *Asm) const { 221 Asm->EmitInt32(Offset); 222 } 223 224 void AppleAccelTableStaticTypeData::emit(AsmPrinter *Asm) const { 225 Asm->EmitInt32(Offset); 226 Asm->EmitInt16(Tag); 227 Asm->EmitInt8(ObjCClassIsImplementation ? dwarf::DW_FLAG_type_implementation 228 : 0); 229 Asm->EmitInt32(QualifiedNameHash); 230 } 231 232 #ifndef _MSC_VER 233 // The lines below are rejected by older versions (TBD) of MSVC. 234 constexpr AppleAccelTableHeader::Atom AppleAccelTableTypeData::Atoms[]; 235 constexpr AppleAccelTableHeader::Atom AppleAccelTableOffsetData::Atoms[]; 236 constexpr AppleAccelTableHeader::Atom AppleAccelTableStaticOffsetData::Atoms[]; 237 constexpr AppleAccelTableHeader::Atom AppleAccelTableStaticTypeData::Atoms[]; 238 #else 239 // FIXME: Erase this path once the minimum MSCV version has been bumped. 240 const SmallVector<AppleAccelTableHeader::Atom, 4> 241 AppleAccelTableOffsetData::Atoms = {AppleAccelTableHeader::Atom( 242 dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)}; 243 const SmallVector<AppleAccelTableHeader::Atom, 4> 244 AppleAccelTableTypeData::Atoms = { 245 AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_offset, 246 dwarf::DW_FORM_data4), 247 AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_tag, 248 dwarf::DW_FORM_data2), 249 AppleAccelTableHeader::Atom(dwarf::DW_ATOM_type_flags, 250 dwarf::DW_FORM_data1)}; 251 const SmallVector<AppleAccelTableHeader::Atom, 4> 252 AppleAccelTableStaticOffsetData::Atoms = {AppleAccelTableHeader::Atom( 253 dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)}; 254 const SmallVector<AppleAccelTableHeader::Atom, 4> 255 AppleAccelTableStaticTypeData::Atoms = { 256 AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_offset, 257 dwarf::DW_FORM_data4), 258 AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_tag, 259 dwarf::DW_FORM_data2), 260 AppleAccelTableHeader::Atom(5, dwarf::DW_FORM_data1), 261 AppleAccelTableHeader::Atom(6, dwarf::DW_FORM_data4)}; 262 #endif 263