1 //===- SearchableTableEmitter.cpp - Generate efficiently searchable tables -==// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This tablegen backend emits a generic array initialized by specified fields, 10 // together with companion index tables and lookup functions (binary search, 11 // currently). 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "llvm/ADT/DenseMap.h" 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 "CodeGenIntrinsics.h" 23 #include <algorithm> 24 #include <set> 25 #include <string> 26 #include <vector> 27 28 using namespace llvm; 29 30 #define DEBUG_TYPE "searchable-table-emitter" 31 32 namespace { 33 34 struct GenericTable; 35 36 int getAsInt(Init *B) { 37 return cast<IntInit>(B->convertInitializerTo(IntRecTy::get()))->getValue(); 38 } 39 int getInt(Record *R, StringRef Field) { 40 return getAsInt(R->getValueInit(Field)); 41 } 42 43 struct GenericEnum { 44 using Entry = std::pair<StringRef, int64_t>; 45 46 std::string Name; 47 Record *Class = nullptr; 48 std::string PreprocessorGuard; 49 std::vector<std::unique_ptr<Entry>> Entries; 50 DenseMap<Record *, Entry *> EntryMap; 51 }; 52 53 struct GenericField { 54 std::string Name; 55 RecTy *RecType = nullptr; 56 bool IsIntrinsic = false; 57 bool IsInstruction = false; 58 GenericEnum *Enum = nullptr; 59 60 GenericField(StringRef Name) : Name(std::string(Name)) {} 61 }; 62 63 struct SearchIndex { 64 std::string Name; 65 SmallVector<GenericField, 1> Fields; 66 bool EarlyOut = false; 67 }; 68 69 struct GenericTable { 70 std::string Name; 71 std::string PreprocessorGuard; 72 std::string CppTypeName; 73 SmallVector<GenericField, 2> Fields; 74 std::vector<Record *> Entries; 75 76 std::unique_ptr<SearchIndex> PrimaryKey; 77 SmallVector<std::unique_ptr<SearchIndex>, 2> Indices; 78 79 const GenericField *getFieldByName(StringRef Name) const { 80 for (const auto &Field : Fields) { 81 if (Name == Field.Name) 82 return &Field; 83 } 84 return nullptr; 85 } 86 }; 87 88 class SearchableTableEmitter { 89 RecordKeeper &Records; 90 DenseMap<Init *, std::unique_ptr<CodeGenIntrinsic>> Intrinsics; 91 std::vector<std::unique_ptr<GenericEnum>> Enums; 92 DenseMap<Record *, GenericEnum *> EnumMap; 93 std::set<std::string> PreprocessorGuards; 94 95 public: 96 SearchableTableEmitter(RecordKeeper &R) : Records(R) {} 97 98 void run(raw_ostream &OS); 99 100 private: 101 typedef std::pair<Init *, int> SearchTableEntry; 102 103 enum TypeContext { 104 TypeInStaticStruct, 105 TypeInTempStruct, 106 TypeInArgument, 107 }; 108 109 std::string primaryRepresentation(const GenericField &Field, Init *I) { 110 if (StringInit *SI = dyn_cast<StringInit>(I)) 111 return SI->getAsString(); 112 else if (BitsInit *BI = dyn_cast<BitsInit>(I)) 113 return "0x" + utohexstr(getAsInt(BI)); 114 else if (BitInit *BI = dyn_cast<BitInit>(I)) 115 return BI->getValue() ? "true" : "false"; 116 else if (CodeInit *CI = dyn_cast<CodeInit>(I)) 117 return std::string(CI->getValue()); 118 else if (Field.IsIntrinsic) 119 return "Intrinsic::" + getIntrinsic(I).EnumName; 120 else if (Field.IsInstruction) 121 return I->getAsString(); 122 else if (Field.Enum) { 123 auto *Entry = Field.Enum->EntryMap[cast<DefInit>(I)->getDef()]; 124 if (!Entry) 125 PrintFatalError(Twine("Entry for field '") + Field.Name + "' is null"); 126 return std::string(Entry->first); 127 } 128 PrintFatalError(Twine("invalid field type for field '") + Field.Name + 129 "', expected: string, bits, bit or code"); 130 } 131 132 bool isIntrinsic(Init *I) { 133 if (DefInit *DI = dyn_cast<DefInit>(I)) 134 return DI->getDef()->isSubClassOf("Intrinsic"); 135 return false; 136 } 137 138 CodeGenIntrinsic &getIntrinsic(Init *I) { 139 std::unique_ptr<CodeGenIntrinsic> &Intr = Intrinsics[I]; 140 if (!Intr) 141 Intr = std::make_unique<CodeGenIntrinsic>(cast<DefInit>(I)->getDef()); 142 return *Intr; 143 } 144 145 bool compareBy(Record *LHS, Record *RHS, const SearchIndex &Index); 146 147 bool isIntegral(Init *I) { 148 return isa<BitsInit>(I) || isa<CodeInit>(I) || isIntrinsic(I); 149 } 150 151 std::string searchableFieldType(const GenericField &Field, TypeContext Ctx) { 152 if (isa<StringRecTy>(Field.RecType)) { 153 if (Ctx == TypeInStaticStruct) 154 return "const char *"; 155 if (Ctx == TypeInTempStruct) 156 return "std::string"; 157 return "StringRef"; 158 } else if (BitsRecTy *BI = dyn_cast<BitsRecTy>(Field.RecType)) { 159 unsigned NumBits = BI->getNumBits(); 160 if (NumBits <= 8) 161 return "uint8_t"; 162 if (NumBits <= 16) 163 return "uint16_t"; 164 if (NumBits <= 32) 165 return "uint32_t"; 166 if (NumBits <= 64) 167 return "uint64_t"; 168 PrintFatalError(Twine("bitfield '") + Field.Name + 169 "' too large to search"); 170 } else if (Field.Enum || Field.IsIntrinsic || Field.IsInstruction) 171 return "unsigned"; 172 PrintFatalError(Twine("Field '") + Field.Name + "' has unknown type '" + 173 Field.RecType->getAsString() + "' to search by"); 174 } 175 176 void emitGenericTable(const GenericTable &Table, raw_ostream &OS); 177 void emitGenericEnum(const GenericEnum &Enum, raw_ostream &OS); 178 void emitLookupDeclaration(const GenericTable &Table, 179 const SearchIndex &Index, raw_ostream &OS); 180 void emitLookupFunction(const GenericTable &Table, const SearchIndex &Index, 181 bool IsPrimary, raw_ostream &OS); 182 void emitIfdef(StringRef Guard, raw_ostream &OS); 183 184 bool parseFieldType(GenericField &Field, Init *II); 185 std::unique_ptr<SearchIndex> 186 parseSearchIndex(GenericTable &Table, StringRef Name, 187 const std::vector<StringRef> &Key, bool EarlyOut); 188 void collectEnumEntries(GenericEnum &Enum, StringRef NameField, 189 StringRef ValueField, 190 const std::vector<Record *> &Items); 191 void collectTableEntries(GenericTable &Table, 192 const std::vector<Record *> &Items); 193 }; 194 195 } // End anonymous namespace. 196 197 // For search indices that consists of a single field whose numeric value is 198 // known, return that numeric value. 199 static int64_t getNumericKey(const SearchIndex &Index, Record *Rec) { 200 assert(Index.Fields.size() == 1); 201 202 if (Index.Fields[0].Enum) { 203 Record *EnumEntry = Rec->getValueAsDef(Index.Fields[0].Name); 204 return Index.Fields[0].Enum->EntryMap[EnumEntry]->second; 205 } 206 207 return getInt(Rec, Index.Fields[0].Name); 208 } 209 210 /// Less-than style comparison between \p LHS and \p RHS according to the 211 /// key of \p Index. 212 bool SearchableTableEmitter::compareBy(Record *LHS, Record *RHS, 213 const SearchIndex &Index) { 214 for (const auto &Field : Index.Fields) { 215 Init *LHSI = LHS->getValueInit(Field.Name); 216 Init *RHSI = RHS->getValueInit(Field.Name); 217 218 if (isa<BitsRecTy>(Field.RecType) || isa<IntRecTy>(Field.RecType)) { 219 int64_t LHSi = getAsInt(LHSI); 220 int64_t RHSi = getAsInt(RHSI); 221 if (LHSi < RHSi) 222 return true; 223 if (LHSi > RHSi) 224 return false; 225 } else if (Field.IsIntrinsic) { 226 CodeGenIntrinsic &LHSi = getIntrinsic(LHSI); 227 CodeGenIntrinsic &RHSi = getIntrinsic(RHSI); 228 if (std::tie(LHSi.TargetPrefix, LHSi.Name) < 229 std::tie(RHSi.TargetPrefix, RHSi.Name)) 230 return true; 231 if (std::tie(LHSi.TargetPrefix, LHSi.Name) > 232 std::tie(RHSi.TargetPrefix, RHSi.Name)) 233 return false; 234 } else if (Field.IsInstruction) { 235 // This does not correctly compare the predefined instructions! 236 Record *LHSr = cast<DefInit>(LHSI)->getDef(); 237 Record *RHSr = cast<DefInit>(RHSI)->getDef(); 238 239 bool LHSpseudo = LHSr->getValueAsBit("isPseudo"); 240 bool RHSpseudo = RHSr->getValueAsBit("isPseudo"); 241 if (LHSpseudo && !RHSpseudo) 242 return true; 243 if (!LHSpseudo && RHSpseudo) 244 return false; 245 246 int comp = LHSr->getName().compare(RHSr->getName()); 247 if (comp < 0) 248 return true; 249 if (comp > 0) 250 return false; 251 } else if (Field.Enum) { 252 auto LHSr = cast<DefInit>(LHSI)->getDef(); 253 auto RHSr = cast<DefInit>(RHSI)->getDef(); 254 int64_t LHSv = Field.Enum->EntryMap[LHSr]->second; 255 int64_t RHSv = Field.Enum->EntryMap[RHSr]->second; 256 if (LHSv < RHSv) 257 return true; 258 if (LHSv > RHSv) 259 return false; 260 } else { 261 std::string LHSs = primaryRepresentation(Field, LHSI); 262 std::string RHSs = primaryRepresentation(Field, RHSI); 263 264 if (isa<StringRecTy>(Field.RecType)) { 265 LHSs = StringRef(LHSs).upper(); 266 RHSs = StringRef(RHSs).upper(); 267 } 268 269 int comp = LHSs.compare(RHSs); 270 if (comp < 0) 271 return true; 272 if (comp > 0) 273 return false; 274 } 275 } 276 return false; 277 } 278 279 void SearchableTableEmitter::emitIfdef(StringRef Guard, raw_ostream &OS) { 280 OS << "#ifdef " << Guard << "\n"; 281 PreprocessorGuards.insert(std::string(Guard)); 282 } 283 284 /// Emit a generic enum. 285 void SearchableTableEmitter::emitGenericEnum(const GenericEnum &Enum, 286 raw_ostream &OS) { 287 emitIfdef((Twine("GET_") + Enum.PreprocessorGuard + "_DECL").str(), OS); 288 289 OS << "enum " << Enum.Name << " {\n"; 290 for (const auto &Entry : Enum.Entries) 291 OS << " " << Entry->first << " = " << Entry->second << ",\n"; 292 OS << "};\n"; 293 294 OS << "#endif\n\n"; 295 } 296 297 void SearchableTableEmitter::emitLookupFunction(const GenericTable &Table, 298 const SearchIndex &Index, 299 bool IsPrimary, 300 raw_ostream &OS) { 301 OS << "\n"; 302 emitLookupDeclaration(Table, Index, OS); 303 OS << " {\n"; 304 305 std::vector<Record *> IndexRowsStorage; 306 ArrayRef<Record *> IndexRows; 307 StringRef IndexTypeName; 308 StringRef IndexName; 309 310 if (IsPrimary) { 311 IndexTypeName = Table.CppTypeName; 312 IndexName = Table.Name; 313 IndexRows = Table.Entries; 314 } else { 315 OS << " struct IndexType {\n"; 316 for (const auto &Field : Index.Fields) { 317 OS << " " << searchableFieldType(Field, TypeInStaticStruct) << " " 318 << Field.Name << ";\n"; 319 } 320 OS << " unsigned _index;\n"; 321 OS << " };\n"; 322 323 OS << " static const struct IndexType Index[] = {\n"; 324 325 std::vector<std::pair<Record *, unsigned>> Entries; 326 Entries.reserve(Table.Entries.size()); 327 for (unsigned i = 0; i < Table.Entries.size(); ++i) 328 Entries.emplace_back(Table.Entries[i], i); 329 330 std::stable_sort(Entries.begin(), Entries.end(), 331 [&](const std::pair<Record *, unsigned> &LHS, 332 const std::pair<Record *, unsigned> &RHS) { 333 return compareBy(LHS.first, RHS.first, Index); 334 }); 335 336 IndexRowsStorage.reserve(Entries.size()); 337 for (const auto &Entry : Entries) { 338 IndexRowsStorage.push_back(Entry.first); 339 340 OS << " { "; 341 bool NeedComma = false; 342 for (const auto &Field : Index.Fields) { 343 if (NeedComma) 344 OS << ", "; 345 NeedComma = true; 346 347 std::string Repr = 348 primaryRepresentation(Field, Entry.first->getValueInit(Field.Name)); 349 if (isa<StringRecTy>(Field.RecType)) 350 Repr = StringRef(Repr).upper(); 351 OS << Repr; 352 } 353 OS << ", " << Entry.second << " },\n"; 354 } 355 356 OS << " };\n\n"; 357 358 IndexTypeName = "IndexType"; 359 IndexName = "Index"; 360 IndexRows = IndexRowsStorage; 361 } 362 363 bool IsContiguous = false; 364 365 if (Index.Fields.size() == 1 && 366 (Index.Fields[0].Enum || isa<BitsRecTy>(Index.Fields[0].RecType))) { 367 IsContiguous = true; 368 for (unsigned i = 0; i < IndexRows.size(); ++i) { 369 if (getNumericKey(Index, IndexRows[i]) != i) { 370 IsContiguous = false; 371 break; 372 } 373 } 374 } 375 376 if (IsContiguous) { 377 OS << " auto Table = makeArrayRef(" << IndexName << ");\n"; 378 OS << " size_t Idx = " << Index.Fields[0].Name << ";\n"; 379 OS << " return Idx >= Table.size() ? nullptr : "; 380 if (IsPrimary) 381 OS << "&Table[Idx]"; 382 else 383 OS << "&" << Table.Name << "[Table[Idx]._index]"; 384 OS << ";\n"; 385 OS << "}\n"; 386 return; 387 } 388 389 if (Index.EarlyOut) { 390 const GenericField &Field = Index.Fields[0]; 391 std::string FirstRepr = 392 primaryRepresentation(Field, IndexRows[0]->getValueInit(Field.Name)); 393 std::string LastRepr = primaryRepresentation( 394 Field, IndexRows.back()->getValueInit(Field.Name)); 395 OS << " if ((" << Field.Name << " < " << FirstRepr << ") ||\n"; 396 OS << " (" << Field.Name << " > " << LastRepr << "))\n"; 397 OS << " return nullptr;\n\n"; 398 } 399 400 OS << " struct KeyType {\n"; 401 for (const auto &Field : Index.Fields) { 402 OS << " " << searchableFieldType(Field, TypeInTempStruct) << " " 403 << Field.Name << ";\n"; 404 } 405 OS << " };\n"; 406 OS << " KeyType Key = { "; 407 bool NeedComma = false; 408 for (const auto &Field : Index.Fields) { 409 if (NeedComma) 410 OS << ", "; 411 NeedComma = true; 412 413 OS << Field.Name; 414 if (isa<StringRecTy>(Field.RecType)) { 415 OS << ".upper()"; 416 if (IsPrimary) 417 PrintFatalError(Twine("Use a secondary index for case-insensitive " 418 "comparison of field '") + 419 Field.Name + "' in table '" + Table.Name + "'"); 420 } 421 } 422 OS << " };\n"; 423 424 OS << " auto Table = makeArrayRef(" << IndexName << ");\n"; 425 OS << " auto Idx = std::lower_bound(Table.begin(), Table.end(), Key,\n"; 426 OS << " [](const " << IndexTypeName << " &LHS, const KeyType &RHS) {\n"; 427 428 for (const auto &Field : Index.Fields) { 429 if (isa<StringRecTy>(Field.RecType)) { 430 OS << " int Cmp" << Field.Name << " = StringRef(LHS." << Field.Name 431 << ").compare(RHS." << Field.Name << ");\n"; 432 OS << " if (Cmp" << Field.Name << " < 0) return true;\n"; 433 OS << " if (Cmp" << Field.Name << " > 0) return false;\n"; 434 } else if (Field.Enum) { 435 // Explicitly cast to unsigned, because the signedness of enums is 436 // compiler-dependent. 437 OS << " if ((unsigned)LHS." << Field.Name << " < (unsigned)RHS." 438 << Field.Name << ")\n"; 439 OS << " return true;\n"; 440 OS << " if ((unsigned)LHS." << Field.Name << " > (unsigned)RHS." 441 << Field.Name << ")\n"; 442 OS << " return false;\n"; 443 } else { 444 OS << " if (LHS." << Field.Name << " < RHS." << Field.Name << ")\n"; 445 OS << " return true;\n"; 446 OS << " if (LHS." << Field.Name << " > RHS." << Field.Name << ")\n"; 447 OS << " return false;\n"; 448 } 449 } 450 451 OS << " return false;\n"; 452 OS << " });\n\n"; 453 454 OS << " if (Idx == Table.end()"; 455 456 for (const auto &Field : Index.Fields) 457 OS << " ||\n Key." << Field.Name << " != Idx->" << Field.Name; 458 OS << ")\n return nullptr;\n"; 459 460 if (IsPrimary) 461 OS << " return &*Idx;\n"; 462 else 463 OS << " return &" << Table.Name << "[Idx->_index];\n"; 464 465 OS << "}\n"; 466 } 467 468 void SearchableTableEmitter::emitLookupDeclaration(const GenericTable &Table, 469 const SearchIndex &Index, 470 raw_ostream &OS) { 471 OS << "const " << Table.CppTypeName << " *" << Index.Name << "("; 472 473 bool NeedComma = false; 474 for (const auto &Field : Index.Fields) { 475 if (NeedComma) 476 OS << ", "; 477 NeedComma = true; 478 479 OS << searchableFieldType(Field, TypeInArgument) << " " << Field.Name; 480 } 481 OS << ")"; 482 } 483 484 void SearchableTableEmitter::emitGenericTable(const GenericTable &Table, 485 raw_ostream &OS) { 486 emitIfdef((Twine("GET_") + Table.PreprocessorGuard + "_DECL").str(), OS); 487 488 // Emit the declarations for the functions that will perform lookup. 489 if (Table.PrimaryKey) { 490 emitLookupDeclaration(Table, *Table.PrimaryKey, OS); 491 OS << ";\n"; 492 } 493 for (const auto &Index : Table.Indices) { 494 emitLookupDeclaration(Table, *Index, OS); 495 OS << ";\n"; 496 } 497 498 OS << "#endif\n\n"; 499 500 emitIfdef((Twine("GET_") + Table.PreprocessorGuard + "_IMPL").str(), OS); 501 502 // The primary data table contains all the fields defined for this map. 503 OS << "constexpr " << Table.CppTypeName << " " << Table.Name << "[] = {\n"; 504 for (unsigned i = 0; i < Table.Entries.size(); ++i) { 505 Record *Entry = Table.Entries[i]; 506 OS << " { "; 507 508 bool NeedComma = false; 509 for (const auto &Field : Table.Fields) { 510 if (NeedComma) 511 OS << ", "; 512 NeedComma = true; 513 514 OS << primaryRepresentation(Field, Entry->getValueInit(Field.Name)); 515 } 516 517 OS << " }, // " << i << "\n"; 518 } 519 OS << " };\n"; 520 521 // Indexes are sorted "{ Thing, PrimaryIdx }" arrays, so that a binary 522 // search can be performed by "Thing". 523 if (Table.PrimaryKey) 524 emitLookupFunction(Table, *Table.PrimaryKey, true, OS); 525 for (const auto &Index : Table.Indices) 526 emitLookupFunction(Table, *Index, false, OS); 527 528 OS << "#endif\n\n"; 529 } 530 531 bool SearchableTableEmitter::parseFieldType(GenericField &Field, Init *II) { 532 if (auto DI = dyn_cast<DefInit>(II)) { 533 Record *TypeRec = DI->getDef(); 534 if (TypeRec->isSubClassOf("GenericEnum")) { 535 Field.Enum = EnumMap[TypeRec]; 536 Field.RecType = RecordRecTy::get(Field.Enum->Class); 537 return true; 538 } 539 } 540 541 return false; 542 } 543 544 std::unique_ptr<SearchIndex> 545 SearchableTableEmitter::parseSearchIndex(GenericTable &Table, StringRef Name, 546 const std::vector<StringRef> &Key, 547 bool EarlyOut) { 548 auto Index = std::make_unique<SearchIndex>(); 549 Index->Name = std::string(Name); 550 Index->EarlyOut = EarlyOut; 551 552 for (const auto &FieldName : Key) { 553 const GenericField *Field = Table.getFieldByName(FieldName); 554 if (!Field) 555 PrintFatalError(Twine("Search index '") + Name + 556 "' refers to non-existing field '" + FieldName + 557 "' in table '" + Table.Name + "'"); 558 Index->Fields.push_back(*Field); 559 } 560 561 if (EarlyOut && isa<StringRecTy>(Index->Fields[0].RecType)) { 562 PrintFatalError( 563 "Early-out is not supported for string types (in search index '" + 564 Twine(Name) + "'"); 565 } 566 567 return Index; 568 } 569 570 void SearchableTableEmitter::collectEnumEntries( 571 GenericEnum &Enum, StringRef NameField, StringRef ValueField, 572 const std::vector<Record *> &Items) { 573 for (auto EntryRec : Items) { 574 StringRef Name; 575 if (NameField.empty()) 576 Name = EntryRec->getName(); 577 else 578 Name = EntryRec->getValueAsString(NameField); 579 580 int64_t Value = 0; 581 if (!ValueField.empty()) 582 Value = getInt(EntryRec, ValueField); 583 584 Enum.Entries.push_back(std::make_unique<GenericEnum::Entry>(Name, Value)); 585 Enum.EntryMap.insert(std::make_pair(EntryRec, Enum.Entries.back().get())); 586 } 587 588 if (ValueField.empty()) { 589 std::stable_sort(Enum.Entries.begin(), Enum.Entries.end(), 590 [](const std::unique_ptr<GenericEnum::Entry> &LHS, 591 const std::unique_ptr<GenericEnum::Entry> &RHS) { 592 return LHS->first < RHS->first; 593 }); 594 595 for (size_t i = 0; i < Enum.Entries.size(); ++i) 596 Enum.Entries[i]->second = i; 597 } 598 } 599 600 void SearchableTableEmitter::collectTableEntries( 601 GenericTable &Table, const std::vector<Record *> &Items) { 602 if (Items.empty()) 603 PrintWarning(Twine("Table '") + Table.Name + "' has no items"); 604 605 for (auto EntryRec : Items) { 606 for (auto &Field : Table.Fields) { 607 auto TI = dyn_cast<TypedInit>(EntryRec->getValueInit(Field.Name)); 608 if (!TI || !TI->isComplete()) { 609 PrintFatalError(EntryRec->getLoc(), 610 Twine("Record '") + EntryRec->getName() + 611 "' in table '" + Table.Name + 612 "' is missing field '" + Field.Name + "'"); 613 } 614 if (!Field.RecType) { 615 Field.RecType = TI->getType(); 616 } else { 617 RecTy *Ty = resolveTypes(Field.RecType, TI->getType()); 618 if (!Ty) 619 PrintFatalError(Twine("Field '") + Field.Name + "' of table '" + 620 Table.Name + "' has incompatible type: " + 621 Field.RecType->getAsString() + " vs. " + 622 TI->getType()->getAsString()); 623 Field.RecType = Ty; 624 } 625 } 626 627 Table.Entries.push_back(EntryRec); 628 } 629 630 Record *IntrinsicClass = Records.getClass("Intrinsic"); 631 Record *InstructionClass = Records.getClass("Instruction"); 632 for (auto &Field : Table.Fields) { 633 if (!Field.RecType) 634 PrintFatalError(Twine("Cannot determine type of field '") + Field.Name + 635 "' in table '" + Table.Name + "'. Maybe it is not used?"); 636 637 if (auto RecordTy = dyn_cast<RecordRecTy>(Field.RecType)) { 638 if (IntrinsicClass && RecordTy->isSubClassOf(IntrinsicClass)) 639 Field.IsIntrinsic = true; 640 else if (InstructionClass && RecordTy->isSubClassOf(InstructionClass)) 641 Field.IsInstruction = true; 642 } 643 } 644 } 645 646 void SearchableTableEmitter::run(raw_ostream &OS) { 647 // Emit tables in a deterministic order to avoid needless rebuilds. 648 SmallVector<std::unique_ptr<GenericTable>, 4> Tables; 649 DenseMap<Record *, GenericTable *> TableMap; 650 651 // Collect all definitions first. 652 for (auto EnumRec : Records.getAllDerivedDefinitions("GenericEnum")) { 653 StringRef NameField; 654 if (!EnumRec->isValueUnset("NameField")) 655 NameField = EnumRec->getValueAsString("NameField"); 656 657 StringRef ValueField; 658 if (!EnumRec->isValueUnset("ValueField")) 659 ValueField = EnumRec->getValueAsString("ValueField"); 660 661 auto Enum = std::make_unique<GenericEnum>(); 662 Enum->Name = std::string(EnumRec->getName()); 663 Enum->PreprocessorGuard = std::string(EnumRec->getName()); 664 665 StringRef FilterClass = EnumRec->getValueAsString("FilterClass"); 666 Enum->Class = Records.getClass(FilterClass); 667 if (!Enum->Class) 668 PrintFatalError(EnumRec->getLoc(), Twine("Enum FilterClass '") + 669 FilterClass + "' does not exist"); 670 671 collectEnumEntries(*Enum, NameField, ValueField, 672 Records.getAllDerivedDefinitions(FilterClass)); 673 EnumMap.insert(std::make_pair(EnumRec, Enum.get())); 674 Enums.emplace_back(std::move(Enum)); 675 } 676 677 for (auto TableRec : Records.getAllDerivedDefinitions("GenericTable")) { 678 auto Table = std::make_unique<GenericTable>(); 679 Table->Name = std::string(TableRec->getName()); 680 Table->PreprocessorGuard = std::string(TableRec->getName()); 681 Table->CppTypeName = std::string(TableRec->getValueAsString("CppTypeName")); 682 683 std::vector<StringRef> Fields = TableRec->getValueAsListOfStrings("Fields"); 684 for (const auto &FieldName : Fields) { 685 Table->Fields.emplace_back(FieldName); 686 687 if (auto TypeOfVal = TableRec->getValue(("TypeOf_" + FieldName).str())) { 688 if (!parseFieldType(Table->Fields.back(), TypeOfVal->getValue())) { 689 PrintFatalError(TableRec->getLoc(), 690 Twine("Table '") + Table->Name + 691 "' has bad 'TypeOf_" + FieldName + 692 "': " + TypeOfVal->getValue()->getAsString()); 693 } 694 } 695 } 696 697 collectTableEntries(*Table, Records.getAllDerivedDefinitions( 698 TableRec->getValueAsString("FilterClass"))); 699 700 if (!TableRec->isValueUnset("PrimaryKey")) { 701 Table->PrimaryKey = 702 parseSearchIndex(*Table, TableRec->getValueAsString("PrimaryKeyName"), 703 TableRec->getValueAsListOfStrings("PrimaryKey"), 704 TableRec->getValueAsBit("PrimaryKeyEarlyOut")); 705 706 std::stable_sort(Table->Entries.begin(), Table->Entries.end(), 707 [&](Record *LHS, Record *RHS) { 708 return compareBy(LHS, RHS, *Table->PrimaryKey); 709 }); 710 } 711 712 TableMap.insert(std::make_pair(TableRec, Table.get())); 713 Tables.emplace_back(std::move(Table)); 714 } 715 716 for (Record *IndexRec : Records.getAllDerivedDefinitions("SearchIndex")) { 717 Record *TableRec = IndexRec->getValueAsDef("Table"); 718 auto It = TableMap.find(TableRec); 719 if (It == TableMap.end()) 720 PrintFatalError(IndexRec->getLoc(), 721 Twine("SearchIndex '") + IndexRec->getName() + 722 "' refers to non-existing table '" + 723 TableRec->getName()); 724 725 GenericTable &Table = *It->second; 726 Table.Indices.push_back(parseSearchIndex( 727 Table, IndexRec->getName(), IndexRec->getValueAsListOfStrings("Key"), 728 IndexRec->getValueAsBit("EarlyOut"))); 729 } 730 731 // Translate legacy tables. 732 Record *SearchableTable = Records.getClass("SearchableTable"); 733 for (auto &NameRec : Records.getClasses()) { 734 Record *Class = NameRec.second.get(); 735 if (Class->getSuperClasses().size() != 1 || 736 !Class->isSubClassOf(SearchableTable)) 737 continue; 738 739 StringRef TableName = Class->getName(); 740 std::vector<Record *> Items = Records.getAllDerivedDefinitions(TableName); 741 if (!Class->isValueUnset("EnumNameField")) { 742 StringRef NameField = Class->getValueAsString("EnumNameField"); 743 StringRef ValueField; 744 if (!Class->isValueUnset("EnumValueField")) 745 ValueField = Class->getValueAsString("EnumValueField"); 746 747 auto Enum = std::make_unique<GenericEnum>(); 748 Enum->Name = (Twine(Class->getName()) + "Values").str(); 749 Enum->PreprocessorGuard = Class->getName().upper(); 750 Enum->Class = Class; 751 752 collectEnumEntries(*Enum, NameField, ValueField, Items); 753 754 Enums.emplace_back(std::move(Enum)); 755 } 756 757 auto Table = std::make_unique<GenericTable>(); 758 Table->Name = (Twine(Class->getName()) + "sList").str(); 759 Table->PreprocessorGuard = Class->getName().upper(); 760 Table->CppTypeName = std::string(Class->getName()); 761 762 for (const RecordVal &Field : Class->getValues()) { 763 std::string FieldName = std::string(Field.getName()); 764 765 // Skip uninteresting fields: either special to us, or injected 766 // template parameters (if they contain a ':'). 767 if (FieldName.find(':') != std::string::npos || 768 FieldName == "SearchableFields" || FieldName == "EnumNameField" || 769 FieldName == "EnumValueField") 770 continue; 771 772 Table->Fields.emplace_back(FieldName); 773 } 774 775 collectTableEntries(*Table, Items); 776 777 for (const auto &Field : 778 Class->getValueAsListOfStrings("SearchableFields")) { 779 std::string Name = 780 (Twine("lookup") + Table->CppTypeName + "By" + Field).str(); 781 Table->Indices.push_back(parseSearchIndex(*Table, Name, {Field}, false)); 782 } 783 784 Tables.emplace_back(std::move(Table)); 785 } 786 787 // Emit everything. 788 for (const auto &Enum : Enums) 789 emitGenericEnum(*Enum, OS); 790 791 for (const auto &Table : Tables) 792 emitGenericTable(*Table, OS); 793 794 // Put all #undefs last, to allow multiple sections guarded by the same 795 // define. 796 for (const auto &Guard : PreprocessorGuards) 797 OS << "#undef " << Guard << "\n"; 798 } 799 800 namespace llvm { 801 802 void EmitSearchableTables(RecordKeeper &RK, raw_ostream &OS) { 803 SearchableTableEmitter(RK).run(OS); 804 } 805 806 } // End llvm namespace. 807