1 //===- SearchableTableEmitter.cpp - Generate efficiently searchable 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 tablegen backend emits a generic array initialized by specified fields, 11 // together with companion index tables and lookup functions (binary search, 12 // currently). 13 // 14 //===----------------------------------------------------------------------===// 15 16 #include "llvm/ADT/StringExtras.h" 17 #include "llvm/Support/Format.h" 18 #include "llvm/Support/MemoryBuffer.h" 19 #include "llvm/Support/SourceMgr.h" 20 #include "llvm/TableGen/Error.h" 21 #include "llvm/TableGen/Record.h" 22 #include <algorithm> 23 #include <sstream> 24 #include <string> 25 #include <vector> 26 using namespace llvm; 27 28 #define DEBUG_TYPE "searchable-table-emitter" 29 30 namespace { 31 32 class SearchableTableEmitter { 33 RecordKeeper &Records; 34 35 public: 36 SearchableTableEmitter(RecordKeeper &R) : Records(R) {} 37 38 void run(raw_ostream &OS); 39 40 private: 41 typedef std::pair<Init *, int> SearchTableEntry; 42 43 int getAsInt(BitsInit *B) { 44 return cast<IntInit>(B->convertInitializerTo(IntRecTy::get()))->getValue(); 45 } 46 int getInt(Record *R, StringRef Field) { 47 return getAsInt(R->getValueAsBitsInit(Field)); 48 } 49 50 std::string primaryRepresentation(Init *I) { 51 if (StringInit *SI = dyn_cast<StringInit>(I)) 52 return SI->getAsString(); 53 else if (BitsInit *BI = dyn_cast<BitsInit>(I)) 54 return "0x" + utohexstr(getAsInt(BI)); 55 else if (BitInit *BI = dyn_cast<BitInit>(I)) 56 return BI->getValue() ? "true" : "false"; 57 else if (CodeInit *CI = dyn_cast<CodeInit>(I)) { 58 return CI->getValue(); 59 } 60 PrintFatalError(SMLoc(), 61 "invalid field type, expected: string, bits, bit or code"); 62 } 63 64 std::string searchRepresentation(Init *I) { 65 std::string PrimaryRep = primaryRepresentation(I); 66 if (!isa<StringInit>(I)) 67 return PrimaryRep; 68 return StringRef(PrimaryRep).upper(); 69 } 70 71 std::string searchableFieldType(Init *I) { 72 if (isa<StringInit>(I)) 73 return "const char *"; 74 else if (BitsInit *BI = dyn_cast<BitsInit>(I)) { 75 unsigned NumBits = BI->getNumBits(); 76 if (NumBits <= 8) 77 NumBits = 8; 78 else if (NumBits <= 16) 79 NumBits = 16; 80 else if (NumBits <= 32) 81 NumBits = 32; 82 else if (NumBits <= 64) 83 NumBits = 64; 84 else 85 PrintFatalError(SMLoc(), "bitfield too large to search"); 86 return "uint" + utostr(NumBits) + "_t"; 87 } 88 PrintFatalError(SMLoc(), "Unknown type to search by"); 89 } 90 91 void emitMapping(Record *MappingDesc, raw_ostream &OS); 92 void emitMappingEnum(std::vector<Record *> &Items, Record *InstanceClass, 93 raw_ostream &OS); 94 void 95 emitPrimaryTable(StringRef Name, std::vector<std::string> &FieldNames, 96 std::vector<std::string> &SearchFieldNames, 97 std::vector<std::vector<SearchTableEntry>> &SearchTables, 98 std::vector<Record *> &Items, raw_ostream &OS); 99 void emitSearchTable(StringRef Name, StringRef Field, 100 std::vector<SearchTableEntry> &SearchTable, 101 raw_ostream &OS); 102 void emitLookupDeclaration(StringRef Name, StringRef Field, Init *I, 103 raw_ostream &OS); 104 void emitLookupFunction(StringRef Name, StringRef Field, Init *I, 105 raw_ostream &OS); 106 }; 107 108 } // End anonymous namespace. 109 110 /// Emit an enum providing symbolic access to some preferred field from 111 /// C++. 112 void SearchableTableEmitter::emitMappingEnum(std::vector<Record *> &Items, 113 Record *InstanceClass, 114 raw_ostream &OS) { 115 std::string EnumNameField = InstanceClass->getValueAsString("EnumNameField"); 116 std::string EnumValueField; 117 if (!InstanceClass->isValueUnset("EnumValueField")) 118 EnumValueField = InstanceClass->getValueAsString("EnumValueField"); 119 120 OS << "enum " << InstanceClass->getName() << "Values {\n"; 121 for (auto Item : Items) { 122 OS << " " << Item->getValueAsString(EnumNameField); 123 if (EnumValueField != StringRef()) 124 OS << " = " << getInt(Item, EnumValueField); 125 OS << ",\n"; 126 } 127 OS << "};\n\n"; 128 } 129 130 void SearchableTableEmitter::emitPrimaryTable( 131 StringRef Name, std::vector<std::string> &FieldNames, 132 std::vector<std::string> &SearchFieldNames, 133 std::vector<std::vector<SearchTableEntry>> &SearchTables, 134 std::vector<Record *> &Items, raw_ostream &OS) { 135 OS << "const " << Name << " " << Name << "sList[] = {\n"; 136 137 for (auto Item : Items) { 138 OS << " { "; 139 for (unsigned i = 0; i < FieldNames.size(); ++i) { 140 OS << primaryRepresentation(Item->getValueInit(FieldNames[i])); 141 if (i != FieldNames.size() - 1) 142 OS << ", "; 143 } 144 OS << "},\n"; 145 } 146 OS << "};\n\n"; 147 } 148 149 void SearchableTableEmitter::emitSearchTable( 150 StringRef Name, StringRef Field, std::vector<SearchTableEntry> &SearchTable, 151 raw_ostream &OS) { 152 OS << "const std::pair<" << searchableFieldType(SearchTable[0].first) 153 << ", int> " << Name << "sBy" << Field << "[] = {\n"; 154 155 if (isa<BitsInit>(SearchTable[0].first)) { 156 std::stable_sort(SearchTable.begin(), SearchTable.end(), 157 [this](const SearchTableEntry &LHS, 158 const SearchTableEntry &RHS) { 159 return getAsInt(cast<BitsInit>(LHS.first)) < 160 getAsInt(cast<BitsInit>(RHS.first)); 161 }); 162 } else { 163 std::stable_sort(SearchTable.begin(), SearchTable.end(), 164 [this](const SearchTableEntry &LHS, 165 const SearchTableEntry &RHS) { 166 return searchRepresentation(LHS.first) < 167 searchRepresentation(RHS.first); 168 }); 169 } 170 171 for (auto Entry : SearchTable) { 172 OS << " { " << searchRepresentation(Entry.first) << ", " << Entry.second 173 << " },\n"; 174 } 175 OS << "};\n\n"; 176 } 177 178 void SearchableTableEmitter::emitLookupFunction(StringRef Name, StringRef Field, 179 Init *I, raw_ostream &OS) { 180 bool IsIntegral = isa<BitsInit>(I); 181 std::string FieldType = searchableFieldType(I); 182 std::string PairType = "std::pair<" + FieldType + ", int>"; 183 184 // const SysRegs *lookupSysRegByName(const char *Name) { 185 OS << "const " << Name << " *" 186 << "lookup" << Name << "By" << Field; 187 OS << "(" << (IsIntegral ? FieldType : "StringRef") << " " << Field 188 << ") {\n"; 189 190 if (IsIntegral) { 191 OS << " auto CanonicalVal = " << Field << ";\n"; 192 OS << " " << PairType << " Val = {CanonicalVal, 0};\n"; 193 } else { 194 // Make sure the result is null terminated because it's going via "char *". 195 OS << " std::string CanonicalVal = " << Field << ".upper();\n"; 196 OS << " " << PairType << " Val = {CanonicalVal.data(), 0};\n"; 197 } 198 199 OS << " ArrayRef<" << PairType << "> Table(" << Name << "sBy" << Field 200 << ");\n"; 201 OS << " auto Idx = std::lower_bound(Table.begin(), Table.end(), Val"; 202 203 if (IsIntegral) 204 OS << ");\n"; 205 else { 206 OS << ",\n "; 207 OS << "[](const " << PairType << " &LHS, const " << PairType 208 << " &RHS) {\n"; 209 OS << " return StringRef(LHS.first) < StringRef(RHS.first);\n"; 210 OS << " });\n\n"; 211 } 212 213 OS << " if (Idx == Table.end() || CanonicalVal != Idx->first)\n"; 214 OS << " return nullptr;\n"; 215 216 OS << " return &" << Name << "sList[Idx->second];\n"; 217 OS << "}\n\n"; 218 } 219 220 void SearchableTableEmitter::emitLookupDeclaration(StringRef Name, 221 StringRef Field, Init *I, 222 raw_ostream &OS) { 223 bool IsIntegral = isa<BitsInit>(I); 224 std::string FieldType = searchableFieldType(I); 225 OS << "const " << Name << " *" 226 << "lookup" << Name << "By" << Field; 227 OS << "(" << (IsIntegral ? FieldType : "StringRef") << " " << Field 228 << ");\n\n"; 229 } 230 231 void SearchableTableEmitter::emitMapping(Record *InstanceClass, 232 raw_ostream &OS) { 233 const std::string &TableName = InstanceClass->getName(); 234 std::vector<Record *> Items = Records.getAllDerivedDefinitions(TableName); 235 236 // Gather all the records we're going to need for this particular mapping. 237 std::vector<std::vector<SearchTableEntry>> SearchTables; 238 std::vector<std::string> SearchFieldNames; 239 240 std::vector<std::string> FieldNames; 241 for (const RecordVal &Field : InstanceClass->getValues()) { 242 std::string FieldName = Field.getName(); 243 244 // Skip uninteresting fields: either built-in, special to us, or injected 245 // template parameters (if they contain a ':'). 246 if (FieldName.find(':') != std::string::npos || FieldName == "NAME" || 247 FieldName == "SearchableFields" || FieldName == "EnumNameField" || 248 FieldName == "EnumValueField") 249 continue; 250 251 FieldNames.push_back(FieldName); 252 } 253 254 for (auto *Field : *InstanceClass->getValueAsListInit("SearchableFields")) { 255 SearchTables.emplace_back(); 256 SearchFieldNames.push_back(Field->getAsUnquotedString()); 257 } 258 259 int Idx = 0; 260 for (Record *Item : Items) { 261 for (unsigned i = 0; i < SearchFieldNames.size(); ++i) { 262 Init *SearchVal = Item->getValueInit(SearchFieldNames[i]); 263 SearchTables[i].emplace_back(SearchVal, Idx); 264 } 265 ++Idx; 266 } 267 268 OS << "#ifdef GET_" << StringRef(TableName).upper() << "_DECL\n"; 269 OS << "#undef GET_" << StringRef(TableName).upper() << "_DECL\n"; 270 271 // Next emit the enum containing the top-level names for use in C++ code if 272 // requested 273 if (!InstanceClass->isValueUnset("EnumNameField")) { 274 emitMappingEnum(Items, InstanceClass, OS); 275 } 276 277 // And the declarations for the functions that will perform lookup. 278 for (unsigned i = 0; i < SearchFieldNames.size(); ++i) 279 emitLookupDeclaration(TableName, SearchFieldNames[i], 280 SearchTables[i][0].first, OS); 281 282 OS << "#endif\n\n"; 283 284 OS << "#ifdef GET_" << StringRef(TableName).upper() << "_IMPL\n"; 285 OS << "#undef GET_" << StringRef(TableName).upper() << "_IMPL\n"; 286 287 // The primary data table contains all the fields defined for this map. 288 emitPrimaryTable(TableName, FieldNames, SearchFieldNames, SearchTables, Items, 289 OS); 290 291 // Indexes are sorted "{ Thing, PrimaryIdx }" arrays, so that a binary 292 // search can be performed by "Thing". 293 for (unsigned i = 0; i < SearchTables.size(); ++i) { 294 emitSearchTable(TableName, SearchFieldNames[i], SearchTables[i], OS); 295 emitLookupFunction(TableName, SearchFieldNames[i], SearchTables[i][0].first, 296 OS); 297 } 298 299 OS << "#endif\n"; 300 } 301 302 void SearchableTableEmitter::run(raw_ostream &OS) { 303 // Tables are defined to be the direct descendents of "SearchableEntry". 304 Record *SearchableTable = Records.getClass("SearchableTable"); 305 for (auto &NameRec : Records.getClasses()) { 306 Record *Class = NameRec.second.get(); 307 if (Class->getSuperClasses().size() != 1 || 308 !Class->isSubClassOf(SearchableTable)) 309 continue; 310 emitMapping(Class, OS); 311 } 312 } 313 314 namespace llvm { 315 316 void EmitSearchableTables(RecordKeeper &RK, raw_ostream &OS) { 317 SearchableTableEmitter(RK).run(OS); 318 } 319 320 } // End llvm namespace. 321