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