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 constexpr AppleAccelTableHeader::Atom AppleAccelTableTypeData::Atoms[]; 74 constexpr AppleAccelTableHeader::Atom AppleAccelTableOffsetData::Atoms[]; 75 76 void AppleAccelTableBase::emitHeader(AsmPrinter *Asm) { Header.emit(Asm); } 77 78 void AppleAccelTableBase::emitBuckets(AsmPrinter *Asm) { 79 unsigned index = 0; 80 for (size_t i = 0, e = Buckets.size(); i < e; ++i) { 81 Asm->OutStreamer->AddComment("Bucket " + Twine(i)); 82 if (!Buckets[i].empty()) 83 Asm->EmitInt32(index); 84 else 85 Asm->EmitInt32(std::numeric_limits<uint32_t>::max()); 86 // Buckets point in the list of hashes, not to the data. Do not increment 87 // the index multiple times in case of hash collisions. 88 uint64_t PrevHash = std::numeric_limits<uint64_t>::max(); 89 for (auto *HD : Buckets[i]) { 90 uint32_t HashValue = HD->HashValue; 91 if (PrevHash != HashValue) 92 ++index; 93 PrevHash = HashValue; 94 } 95 } 96 } 97 98 void AppleAccelTableBase::emitHashes(AsmPrinter *Asm) { 99 uint64_t PrevHash = std::numeric_limits<uint64_t>::max(); 100 unsigned BucketIdx = 0; 101 for (auto &Bucket : Buckets) { 102 for (auto &Hash : Bucket) { 103 uint32_t HashValue = Hash->HashValue; 104 if (PrevHash == HashValue) 105 continue; 106 Asm->OutStreamer->AddComment("Hash in Bucket " + Twine(BucketIdx)); 107 Asm->EmitInt32(HashValue); 108 PrevHash = HashValue; 109 } 110 BucketIdx++; 111 } 112 } 113 114 void AppleAccelTableBase::emitOffsets(AsmPrinter *Asm, 115 const MCSymbol *SecBegin) { 116 uint64_t PrevHash = std::numeric_limits<uint64_t>::max(); 117 for (size_t i = 0, e = Buckets.size(); i < e; ++i) { 118 for (auto HI = Buckets[i].begin(), HE = Buckets[i].end(); HI != HE; ++HI) { 119 uint32_t HashValue = (*HI)->HashValue; 120 if (PrevHash == HashValue) 121 continue; 122 PrevHash = HashValue; 123 Asm->OutStreamer->AddComment("Offset in Bucket " + Twine(i)); 124 MCContext &Context = Asm->OutStreamer->getContext(); 125 const MCExpr *Sub = MCBinaryExpr::createSub( 126 MCSymbolRefExpr::create((*HI)->Sym, Context), 127 MCSymbolRefExpr::create(SecBegin, Context), Context); 128 Asm->OutStreamer->EmitValue(Sub, sizeof(uint32_t)); 129 } 130 } 131 } 132 133 void AppleAccelTableBase::emitData(AsmPrinter *Asm) { 134 for (size_t i = 0, e = Buckets.size(); i < e; ++i) { 135 uint64_t PrevHash = std::numeric_limits<uint64_t>::max(); 136 for (auto &Hash : Buckets[i]) { 137 // Terminate the previous entry if there is no hash collision with the 138 // current one. 139 if (PrevHash != std::numeric_limits<uint64_t>::max() && 140 PrevHash != Hash->HashValue) 141 Asm->EmitInt32(0); 142 // Remember to emit the label for our offset. 143 Asm->OutStreamer->EmitLabel(Hash->Sym); 144 Asm->OutStreamer->AddComment(Hash->Str); 145 Asm->emitDwarfStringOffset(Hash->Data.Name); 146 Asm->OutStreamer->AddComment("Num DIEs"); 147 Asm->EmitInt32(Hash->Data.Values.size()); 148 for (const auto *V : Hash->Data.Values) { 149 V->emit(Asm); 150 } 151 PrevHash = Hash->HashValue; 152 } 153 // Emit the final end marker for the bucket. 154 if (!Buckets[i].empty()) 155 Asm->EmitInt32(0); 156 } 157 } 158 159 void AppleAccelTableBase::computeBucketCount() { 160 // First get the number of unique hashes. 161 std::vector<uint32_t> uniques(Data.size()); 162 for (size_t i = 0, e = Data.size(); i < e; ++i) 163 uniques[i] = Data[i]->HashValue; 164 array_pod_sort(uniques.begin(), uniques.end()); 165 std::vector<uint32_t>::iterator p = 166 std::unique(uniques.begin(), uniques.end()); 167 168 // Compute the hashes count and use it to set that together with the bucket 169 // count in the header. 170 Header.setBucketAndHashCount(std::distance(uniques.begin(), p)); 171 } 172 173 void AppleAccelTableBase::finalizeTable(AsmPrinter *Asm, StringRef Prefix) { 174 // Create the individual hash data outputs. 175 Data.reserve(Entries.size()); 176 for (auto &E : Entries) { 177 // Unique the entries. 178 std::stable_sort(E.second.Values.begin(), E.second.Values.end(), 179 [](const AppleAccelTableData *A, 180 const AppleAccelTableData *B) { return *A < *B; }); 181 E.second.Values.erase( 182 std::unique(E.second.Values.begin(), E.second.Values.end()), 183 E.second.Values.end()); 184 185 HashData *Entry = new (Allocator) HashData(E.first(), E.second); 186 Data.push_back(Entry); 187 } 188 189 // Figure out how many buckets we need, then compute the bucket contents and 190 // the final ordering. We'll emit the hashes and offsets by doing a walk 191 // during the emission phase. We add temporary symbols to the data so that we 192 // can reference them during the offset later, we'll emit them when we emit 193 // the data. 194 computeBucketCount(); 195 196 // Compute bucket contents and final ordering. 197 Buckets.resize(Header.getBucketCount()); 198 for (auto &D : Data) { 199 uint32_t bucket = D->HashValue % Header.getBucketCount(); 200 Buckets[bucket].push_back(D); 201 D->Sym = Asm->createTempSymbol(Prefix); 202 } 203 204 // Sort the contents of the buckets by hash value so that hash collisions end 205 // up together. Stable sort makes testing easier and doesn't cost much more. 206 for (auto &Bucket : Buckets) 207 std::stable_sort(Bucket.begin(), Bucket.end(), 208 [](HashData *LHS, HashData *RHS) { 209 return LHS->HashValue < RHS->HashValue; 210 }); 211 } 212 213 void AppleAccelTableOffsetData::emit(AsmPrinter *Asm) const { 214 Asm->EmitInt32(Die->getDebugSectionOffset()); 215 } 216 217 void AppleAccelTableTypeData::emit(AsmPrinter *Asm) const { 218 Asm->EmitInt32(Die->getDebugSectionOffset()); 219 Asm->EmitInt16(Die->getTag()); 220 Asm->EmitInt8(0); 221 } 222