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