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/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>(Val: B))
36 return *BI->convertInitializerToInt();
37 if (const auto *II = dyn_cast<IntInit>(Val: B))
38 return II->getValue();
39 llvm_unreachable("Unexpected initializer");
40}
41
42static int64_t getInt(const Record *R, StringRef Field) {
43 return getAsInt(B: R->getValueInit(FieldName: 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(Key: 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>(Val: I)) {
130 if (Field.IsCode || SI->hasCodeFormat())
131 return SI->getValue().str();
132 else
133 return SI->getAsString();
134 }
135 if (const auto *BI = dyn_cast<BitsInit>(Val: I))
136 return "0x" + utohexstr(X: getAsInt(B: BI));
137 if (const auto *BI = dyn_cast<BitInit>(Val: 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(Def: cast<DefInit>(Val: I)->getDef());
146 if (!Entry)
147 PrintFatalError(ErrorLoc: Loc,
148 Msg: Twine("Entry for field '") + Field.Name + "' is null");
149 return Entry->Name.str();
150 }
151 PrintFatalError(ErrorLoc: Loc, Msg: 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>(Val: I))
157 return DI->getDef()->isSubClassOf(Name: "Intrinsic");
158 return false;
159 }
160
161 const CodeGenIntrinsic &getIntrinsic(const Init *I) {
162 const Record *Def = cast<DefInit>(Val: 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>(Val: 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>(Val: 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(ErrorLoc: Index.Loc, Msg: 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>(Val: Field.RecType))
195 return "bool";
196 if (Field.Enum || Field.IsIntrinsic || Field.IsInstruction)
197 return "unsigned";
198 PrintFatalError(ErrorLoc: Index.Loc,
199 Msg: 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 is
225// 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(FieldName: Field.Name);
235 return Target->getInstrIntValue(R: TheDef);
236 }
237 if (Field.Enum) {
238 const Record *EnumEntry = Rec->getValueAsDef(FieldName: Field.Name);
239 return Field.Enum->getEntry(Def: EnumEntry)->Value;
240 }
241 assert(isa<BitsRecTy>(Field.RecType) && "unexpected field type");
242
243 return getInt(R: Rec, Field: Field.Name);
244}
245
246/// Less-than style comparison between \p LHS and \p RHS according to the
247/// 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 we
264 // 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>(Val: Field.RecType) || isa<IntRecTy>(Val: Field.RecType)) {
277 int64_t LHSi = getAsInt(B: LHSI);
278 int64_t RHSi = getAsInt(B: RHSI);
279 return CmpLTValue(LHSi, RHSi);
280 }
281
282 if (Field.IsIntrinsic) {
283 const CodeGenIntrinsic &LHSi = getIntrinsic(I: LHSI);
284 const CodeGenIntrinsic &RHSi = getIntrinsic(I: 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>(Val: LHSI)->getDef();
293 const Record *RHSr = cast<DefInit>(Val: RHSI)->getDef();
294
295 // Order pseudo instructions before non-pseudo ones.
296 bool LHSNotPseudo = !LHSr->getValueAsBit(FieldName: "isPseudo");
297 bool RHSNotPseudo = !RHSr->getValueAsBit(FieldName: "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>(Val: LHSI)->getDef();
305 const Record *RHSr = cast<DefInit>(Val: RHSI)->getDef();
306 int64_t LHSv = Field.Enum->getEntry(Def: LHSr)->Value;
307 int64_t RHSv = Field.Enum->getEntry(Def: RHSr)->Value;
308 return CmpLTValue(LHSv, RHSv);
309 }
310
311 std::string LHSs = primaryRepresentation(Loc: Index.Loc, Field, I: LHSI);
312 std::string RHSs = primaryRepresentation(Loc: Index.Loc, Field, I: RHSI);
313 if (isa<StringRecTy>(Val: 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(FieldName: Field.Name);
322 const Init *RHSI = RHS->getValueInit(FieldName: 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(x: Guard.str());
332}
333
334/// Emit a generic enum.
335void SearchableTableEmitter::emitGenericEnum(const GenericEnum &Enum,
336 raw_ostream &OS) {
337 emitIfdef(Guard: (Twine("GET_") + Enum.PreprocessorGuard + "_DECL").str(), OS);
338
339 OS << "enum " << Enum.Name << " {\n";
340 for (const auto &[Name, Value] :
341 make_second_range(c: 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, Ctx: 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(n: Table.Entries.size());
379 for (auto [Idx, TblEntry] : enumerate(First: Table.Entries))
380 Entries.emplace_back(args: TblEntry, args&: Idx);
381
382 llvm::stable_sort(Range&: Entries,
383 C: [&](const std::pair<const Record *, unsigned> &LHS,
384 const std::pair<const Record *, unsigned> &RHS) {
385 return compareBy(LHS: LHS.first, RHS: RHS.first, Index);
386 });
387
388 IndexRowsStorage.reserve(n: Entries.size());
389 for (const auto &[EntryRec, EntryIndex] : Entries) {
390 IndexRowsStorage.push_back(x: EntryRec);
391
392 OS << " { ";
393 ListSeparator LS;
394 for (const auto &Field : Index.Fields) {
395 std::string Repr = primaryRepresentation(
396 Loc: Index.Loc, Field, I: EntryRec->getValueInit(FieldName: Field.Name));
397 if (isa<StringRecTy>(Val: 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>(Val: Index.Fields[0].RecType) ||
415 Index.Fields[0].IsInstruction)) {
416 int64_t FirstKeyVal = getNumericKey(Index, Rec: IndexRows[0]);
417 IsContiguous = true;
418 for (const auto &[Idx, IndexRow] : enumerate(First&: IndexRows)) {
419 if (getNumericKey(Index, Rec: 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 Loc: Index.Loc, Field, I: IndexRows[0]->getValueInit(FieldName: Field.Name));
430 std::string LastRepr = primaryRepresentation(
431 Loc: Index.Loc, Field, I: IndexRows.back()->getValueInit(FieldName: Field.Name));
432 std::string TS =
433 searchableFieldType(Table, Index, Field, Ctx: TypeInStaticStruct);
434 OS << " if ((" << TS << ")" << Field.Name << " != std::clamp<" << TS
435 << ">(" << Field.Name << ", " << FirstRepr << ", " << LastRepr << "))\n";
436 OS << " return nullptr;\n\n";
437
438 if (IsContiguous && !Index.EarlyOut) {
439 OS << " auto Table = ArrayRef(" << IndexName << ");\n";
440 OS << " size_t Idx = " << Field.Name << " - " << FirstRepr << ";\n";
441 OS << " return ";
442 if (IsPrimary)
443 OS << "&Table[Idx]";
444 else
445 OS << "&" << Table.Name << "[Table[Idx]._index]";
446 OS << ";\n";
447 OS << "}\n";
448 return;
449 }
450 }
451
452 OS << " struct KeyType {\n";
453 for (const auto &Field : Index.Fields) {
454 OS << " " << searchableFieldType(Table, Index, Field, Ctx: TypeInTempStruct)
455 << " " << Field.Name << ";\n";
456 }
457 OS << " };\n";
458 OS << " KeyType Key = {";
459 ListSeparator LS;
460 for (const auto &Field : Index.Fields) {
461 OS << LS << Field.Name;
462 if (isa<StringRecTy>(Val: Field.RecType)) {
463 OS << ".upper()";
464 if (IsPrimary)
465 PrintFatalError(ErrorLoc: Index.Loc,
466 Msg: Twine("In table '") + Table.Name +
467 "', use a secondary lookup method for "
468 "case-insensitive comparison of field '" +
469 Field.Name + "'");
470 }
471 }
472 OS << "};\n";
473
474 OS << " struct Comp {\n";
475 OS << " bool operator()(const " << IndexTypeName
476 << " &LHS, const KeyType &RHS) const {\n";
477
478 auto emitComparator = [&]() {
479 for (const auto &Field : Index.Fields) {
480 if (isa<StringRecTy>(Val: Field.RecType)) {
481 OS << " int Cmp" << Field.Name << " = StringRef(LHS." << Field.Name
482 << ").compare(RHS." << Field.Name << ");\n";
483 OS << " if (Cmp" << Field.Name << " < 0) return true;\n";
484 OS << " if (Cmp" << Field.Name << " > 0) return false;\n";
485 } else if (Field.Enum) {
486 // Explicitly cast to unsigned, because the signedness of enums is
487 // compiler-dependent.
488 OS << " if ((unsigned)LHS." << Field.Name << " < (unsigned)RHS."
489 << Field.Name << ")\n";
490 OS << " return true;\n";
491 OS << " if ((unsigned)LHS." << Field.Name << " > (unsigned)RHS."
492 << Field.Name << ")\n";
493 OS << " return false;\n";
494 } else {
495 OS << " if (LHS." << Field.Name << " < RHS." << Field.Name
496 << ")\n";
497 OS << " return true;\n";
498 OS << " if (LHS." << Field.Name << " > RHS." << Field.Name
499 << ")\n";
500 OS << " return false;\n";
501 }
502 }
503 OS << " return false;\n";
504 OS << " }\n";
505 };
506 emitComparator();
507 bool ShouldReturnRange = Index.ReturnRange;
508 if (ShouldReturnRange) {
509 OS << " bool operator()(const KeyType &LHS, const " << IndexTypeName
510 << " &RHS) const {\n";
511 emitComparator();
512 }
513
514 OS << " };\n";
515 OS << " auto Table = ArrayRef(" << IndexName << ");\n";
516 if (ShouldReturnRange)
517 OS << " auto It = std::equal_range(Table.begin(), Table.end(), Key, ";
518 else
519 OS << " auto Idx = std::lower_bound(Table.begin(), Table.end(), Key, ";
520 OS << "Comp());\n";
521
522 if (!ShouldReturnRange) {
523 OS << " if (Idx == Table.end()";
524 for (const auto &Field : Index.Fields)
525 OS << " ||\n Key." << Field.Name << " != Idx->" << Field.Name;
526 }
527
528 if (ShouldReturnRange) {
529 OS << " return llvm::make_range(It.first, It.second);\n";
530 } else if (IsPrimary) {
531 OS << ")\n return nullptr;\n\n";
532 OS << " return &*Idx;\n";
533 } else {
534 OS << ")\n return nullptr;\n\n";
535 OS << " return &" << Table.Name << "[Idx->_index];\n";
536 }
537
538 OS << "}\n";
539}
540
541void SearchableTableEmitter::emitLookupDeclaration(const GenericTable &Table,
542 const SearchIndex &Index,
543 raw_ostream &OS) {
544 if (Index.ReturnRange)
545 OS << "llvm::iterator_range<const " << Table.CppTypeName << " *> ";
546 else
547 OS << "const " << Table.CppTypeName << " *";
548 OS << Index.Name << "(";
549 ListSeparator LS;
550 for (const auto &Field : Index.Fields)
551 OS << LS << searchableFieldType(Table, Index, Field, Ctx: TypeInArgument) << " "
552 << Field.Name;
553 OS << ")";
554}
555
556void SearchableTableEmitter::emitGenericTable(const GenericTable &Table,
557 raw_ostream &OS) {
558 emitIfdef(Guard: (Twine("GET_") + Table.PreprocessorGuard + "_DECL").str(), OS);
559
560 // Emit the declarations for the functions that will perform lookup.
561 if (Table.PrimaryKey) {
562 emitLookupDeclaration(Table, Index: *Table.PrimaryKey, OS);
563 OS << ";\n";
564 }
565 for (const auto &Index : Table.Indices) {
566 emitLookupDeclaration(Table, Index: *Index, OS);
567 OS << ";\n";
568 }
569
570 OS << "#endif\n\n";
571
572 emitIfdef(Guard: (Twine("GET_") + Table.PreprocessorGuard + "_IMPL").str(), OS);
573
574 // The primary data table contains all the fields defined for this map.
575 OS << "constexpr " << Table.CppTypeName << " " << Table.Name << "[] = {\n";
576 for (const auto &[Idx, Entry] : enumerate(First: Table.Entries)) {
577 OS << " { ";
578
579 ListSeparator LS;
580 for (const auto &Field : Table.Fields)
581 OS << LS
582 << primaryRepresentation(Loc: Table.Locs[0], Field,
583 I: Entry->getValueInit(FieldName: Field.Name));
584
585 OS << " }, // " << Idx << "\n";
586 }
587 OS << " };\n";
588
589 // Indexes are sorted "{ Thing, PrimaryIdx }" arrays, so that a binary
590 // search can be performed by "Thing".
591 if (Table.PrimaryKey)
592 emitLookupFunction(Table, Index: *Table.PrimaryKey, /*IsPrimary=*/true, OS);
593 for (const auto &Index : Table.Indices)
594 emitLookupFunction(Table, Index: *Index, /*IsPrimary=*/false, OS);
595
596 OS << "#endif\n\n";
597}
598
599bool SearchableTableEmitter::parseFieldType(GenericField &Field,
600 const Init *TypeOf) {
601 auto Type = dyn_cast<StringInit>(Val: TypeOf);
602 if (!Type)
603 return false;
604
605 StringRef TypeStr = Type->getValue();
606
607 if (TypeStr == "code") {
608 Field.IsCode = true;
609 return true;
610 }
611
612 if (const Record *TypeRec = Records.getDef(Name: TypeStr)) {
613 if (TypeRec->isSubClassOf(Name: "GenericEnum")) {
614 Field.Enum = EnumMap[TypeRec];
615 Field.RecType = RecordRecTy::get(Class: Field.Enum->Class);
616 return true;
617 }
618 }
619
620 return false;
621}
622
623std::unique_ptr<SearchIndex> SearchableTableEmitter::parseSearchIndex(
624 GenericTable &Table, const RecordVal *KeyRecVal, StringRef Name,
625 ArrayRef<StringRef> Key, bool EarlyOut, bool ReturnRange) {
626 auto Index = std::make_unique<SearchIndex>();
627 Index->Name = Name.str();
628 Index->Loc = KeyRecVal->getLoc();
629 Index->EarlyOut = EarlyOut;
630 Index->ReturnRange = ReturnRange;
631
632 for (const auto &FieldName : Key) {
633 const GenericField *Field = Table.getFieldByName(Name: FieldName);
634 if (!Field)
635 PrintFatalError(
636 RecVal: KeyRecVal,
637 Msg: Twine("In table '") + Table.Name +
638 "', 'PrimaryKey' or 'Key' refers to nonexistent field '" +
639 FieldName + "'");
640
641 Index->Fields.push_back(Elt: *Field);
642 }
643
644 if (EarlyOut && isa<StringRecTy>(Val: Index->Fields[0].RecType)) {
645 PrintFatalError(
646 RecVal: KeyRecVal, Msg: Twine("In lookup method '") + Name + "', early-out is not " +
647 "supported for a first key field of type string");
648 }
649
650 return Index;
651}
652
653void SearchableTableEmitter::collectEnumEntries(
654 GenericEnum &Enum, StringRef NameField, StringRef ValueField,
655 ArrayRef<const Record *> Items) {
656 Enum.Entries.reserve(NumEntries: Items.size());
657 for (const Record *EntryRec : Items) {
658 StringRef Name = NameField.empty() ? EntryRec->getName()
659 : EntryRec->getValueAsString(FieldName: NameField);
660 int64_t Value = ValueField.empty() ? 0 : getInt(R: EntryRec, Field: ValueField);
661 Enum.Entries.try_emplace(Key: EntryRec, Args&: Name, Args&: Value);
662 }
663
664 // If no values are provided for enums, assign values in the order of sorted
665 // enum names.
666 if (ValueField.empty()) {
667 // Copy the map entries for sorting and clear the map.
668 auto SavedEntries = Enum.Entries.takeVector();
669 using MapVectorEntryTy = std::pair<const Record *, GenericEnum::Entry>;
670 llvm::stable_sort(Range&: SavedEntries, C: [](const MapVectorEntryTy &LHS,
671 const MapVectorEntryTy &RHS) {
672 return LHS.second.Name < RHS.second.Name;
673 });
674
675 // Repopulate entries using the new sorted order.
676 for (auto [Idx, Entry] : enumerate(First&: SavedEntries))
677 Enum.Entries.try_emplace(Key: Entry.first, Args&: Entry.second.Name, Args&: Idx);
678 }
679}
680
681void SearchableTableEmitter::collectTableEntries(
682 GenericTable &Table, ArrayRef<const Record *> Items) {
683 if (Items.empty())
684 PrintFatalError(ErrorLoc: Table.Locs,
685 Msg: Twine("Table '") + Table.Name + "' has no entries");
686
687 for (auto *EntryRec : Items) {
688 for (auto &Field : Table.Fields) {
689 auto TI = dyn_cast<TypedInit>(Val: EntryRec->getValueInit(FieldName: Field.Name));
690 if (!TI || !TI->isComplete()) {
691 PrintFatalError(Rec: EntryRec, Msg: Twine("Record '") + EntryRec->getName() +
692 "' for table '" + Table.Name +
693 "' is missing field '" + Field.Name +
694 "'");
695 }
696 if (!Field.RecType) {
697 Field.RecType = TI->getType();
698 } else {
699 const RecTy *Ty = resolveTypes(T1: Field.RecType, T2: TI->getType());
700 if (!Ty)
701 PrintFatalError(RecVal: EntryRec->getValue(Name: Field.Name),
702 Msg: Twine("Field '") + Field.Name + "' of table '" +
703 Table.Name + "' entry has incompatible type: " +
704 TI->getType()->getAsString() + " vs. " +
705 Field.RecType->getAsString());
706 Field.RecType = Ty;
707 }
708 }
709
710 Table.Entries.push_back(x: EntryRec); // Add record to table's record list.
711 }
712
713 const Record *IntrinsicClass = Records.getClass(Name: "Intrinsic");
714 const Record *InstructionClass = Records.getClass(Name: "Instruction");
715 for (auto &Field : Table.Fields) {
716 if (!Field.RecType)
717 PrintFatalError(Msg: Twine("Cannot determine type of field '") + Field.Name +
718 "' in table '" + Table.Name + "'. Maybe it is not used?");
719
720 if (auto RecordTy = dyn_cast<RecordRecTy>(Val: Field.RecType)) {
721 if (IntrinsicClass && RecordTy->isSubClassOf(Class: IntrinsicClass))
722 Field.IsIntrinsic = true;
723 else if (InstructionClass && RecordTy->isSubClassOf(Class: InstructionClass))
724 Field.IsInstruction = true;
725 }
726 }
727
728 SearchIndex Idx;
729 llvm::append_range(C&: Idx.Fields, R&: Table.Fields);
730 llvm::sort(C&: Table.Entries, Comp: [&](const Record *LHS, const Record *RHS) {
731 return compareBy(LHS, RHS, Index: Idx);
732 });
733}
734
735void SearchableTableEmitter::run(raw_ostream &OS) {
736 // Emit tables in a deterministic order to avoid needless rebuilds.
737 SmallVector<std::unique_ptr<GenericTable>, 4> Tables;
738 DenseMap<const Record *, GenericTable *> TableMap;
739 bool NeedsTarget =
740 !Records.getAllDerivedDefinitionsIfDefined(ClassName: "Instruction").empty() ||
741 !Records.getAllDerivedDefinitionsIfDefined(ClassName: "Intrinsic").empty();
742 if (NeedsTarget)
743 Target = std::make_unique<CodeGenTarget>(args: Records);
744
745 // Collect all definitions first.
746 for (const auto *EnumRec : Records.getAllDerivedDefinitions(ClassName: "GenericEnum")) {
747 StringRef NameField;
748 if (!EnumRec->isValueUnset(FieldName: "NameField"))
749 NameField = EnumRec->getValueAsString(FieldName: "NameField");
750
751 StringRef ValueField;
752 if (!EnumRec->isValueUnset(FieldName: "ValueField"))
753 ValueField = EnumRec->getValueAsString(FieldName: "ValueField");
754
755 auto Enum = std::make_unique<GenericEnum>();
756 Enum->Name = EnumRec->getName().str();
757 Enum->PreprocessorGuard = EnumRec->getName().str();
758
759 StringRef FilterClass = EnumRec->getValueAsString(FieldName: "FilterClass");
760 Enum->Class = Records.getClass(Name: FilterClass);
761 if (!Enum->Class)
762 PrintFatalError(RecVal: EnumRec->getValue(Name: "FilterClass"),
763 Msg: Twine("Enum FilterClass '") + FilterClass +
764 "' does not exist");
765
766 collectEnumEntries(Enum&: *Enum, NameField, ValueField,
767 Items: Records.getAllDerivedDefinitions(ClassName: FilterClass));
768 EnumMap.try_emplace(Key: EnumRec, Args: Enum.get());
769 Enums.emplace_back(args: std::move(Enum));
770 }
771
772 for (const auto *TableRec :
773 Records.getAllDerivedDefinitions(ClassName: "GenericTable")) {
774 auto Table = std::make_unique<GenericTable>();
775 Table->Name = TableRec->getName().str();
776 Table->Locs = TableRec->getLoc();
777 Table->PreprocessorGuard = TableRec->getName().str();
778 Table->CppTypeName = TableRec->getValueAsString(FieldName: "CppTypeName").str();
779
780 std::vector<StringRef> Fields = TableRec->getValueAsListOfStrings(FieldName: "Fields");
781 for (const auto &FieldName : Fields) {
782 Table->Fields.emplace_back(Args: FieldName); // Construct a GenericField.
783
784 if (auto TypeOfRecordVal =
785 TableRec->getValue(Name: ("TypeOf_" + FieldName).str())) {
786 if (!parseFieldType(Field&: Table->Fields.back(),
787 TypeOf: TypeOfRecordVal->getValue())) {
788 PrintError(RecVal: TypeOfRecordVal,
789 Msg: Twine("Table '") + Table->Name + "' has invalid 'TypeOf_" +
790 FieldName +
791 "': " + TypeOfRecordVal->getValue()->getAsString());
792 PrintFatalNote(Msg: "The 'TypeOf_xxx' field must be a string naming a "
793 "GenericEnum record, or \"code\"");
794 }
795 }
796 }
797
798 StringRef FilterClass = TableRec->getValueAsString(FieldName: "FilterClass");
799 if (!Records.getClass(Name: FilterClass))
800 PrintFatalError(RecVal: TableRec->getValue(Name: "FilterClass"),
801 Msg: Twine("Table FilterClass '") + FilterClass +
802 "' does not exist");
803
804 const RecordVal *FilterClassFieldVal =
805 TableRec->getValue(Name: "FilterClassField");
806 std::vector<const Record *> Definitions =
807 Records.getAllDerivedDefinitions(ClassName: FilterClass);
808 if (auto *FilterClassFieldInit =
809 dyn_cast<StringInit>(Val: FilterClassFieldVal->getValue())) {
810 StringRef FilterClassField = FilterClassFieldInit->getValue();
811 llvm::erase_if(C&: Definitions, P: [&](const Record *R) {
812 const RecordVal *Filter = R->getValue(Name: FilterClassField);
813 if (auto *BitV = dyn_cast<BitInit>(Val: Filter->getValue()))
814 return !BitV->getValue();
815
816 PrintFatalError(RecVal: Filter, Msg: Twine("FilterClassField '") + FilterClass +
817 "' should be a bit value");
818 return true;
819 });
820 }
821 collectTableEntries(Table&: *Table, Items: Definitions);
822
823 if (!TableRec->isValueUnset(FieldName: "PrimaryKey")) {
824 Table->PrimaryKey =
825 parseSearchIndex(Table&: *Table, KeyRecVal: TableRec->getValue(Name: "PrimaryKey"),
826 Name: TableRec->getValueAsString(FieldName: "PrimaryKeyName"),
827 Key: TableRec->getValueAsListOfStrings(FieldName: "PrimaryKey"),
828 EarlyOut: TableRec->getValueAsBit(FieldName: "PrimaryKeyEarlyOut"),
829 ReturnRange: TableRec->getValueAsBit(FieldName: "PrimaryKeyReturnRange"));
830
831 llvm::stable_sort(Range&: Table->Entries,
832 C: [&](const Record *LHS, const Record *RHS) {
833 return compareBy(LHS, RHS, Index: *Table->PrimaryKey);
834 });
835 }
836
837 TableMap.try_emplace(Key: TableRec, Args: Table.get());
838 Tables.emplace_back(Args: std::move(Table));
839 }
840
841 for (const Record *IndexRec :
842 Records.getAllDerivedDefinitions(ClassName: "SearchIndex")) {
843 const Record *TableRec = IndexRec->getValueAsDef(FieldName: "Table");
844 auto It = TableMap.find(Val: TableRec);
845 if (It == TableMap.end())
846 PrintFatalError(RecVal: IndexRec->getValue(Name: "Table"),
847 Msg: Twine("SearchIndex '") + IndexRec->getName() +
848 "' refers to nonexistent table '" +
849 TableRec->getName());
850
851 GenericTable &Table = *It->second;
852 Table.Indices.push_back(Elt: parseSearchIndex(
853 Table, KeyRecVal: IndexRec->getValue(Name: "Key"), Name: IndexRec->getName(),
854 Key: IndexRec->getValueAsListOfStrings(FieldName: "Key"),
855 EarlyOut: IndexRec->getValueAsBit(FieldName: "EarlyOut"), /*ReturnRange*/ false));
856 }
857
858 // Translate legacy tables.
859 const Record *SearchableTable = Records.getClass(Name: "SearchableTable");
860 for (auto &NameRec : Records.getClasses()) {
861 const Record *Class = NameRec.second.get();
862 if (Class->getDirectSuperClasses().size() != 1 ||
863 !Class->isSubClassOf(R: SearchableTable))
864 continue;
865
866 StringRef TableName = Class->getName();
867 ArrayRef<const Record *> Items =
868 Records.getAllDerivedDefinitions(ClassName: TableName);
869 if (!Class->isValueUnset(FieldName: "EnumNameField")) {
870 StringRef NameField = Class->getValueAsString(FieldName: "EnumNameField");
871 StringRef ValueField;
872 if (!Class->isValueUnset(FieldName: "EnumValueField"))
873 ValueField = Class->getValueAsString(FieldName: "EnumValueField");
874
875 auto Enum = std::make_unique<GenericEnum>();
876 Enum->Name = (Twine(Class->getName()) + "Values").str();
877 Enum->PreprocessorGuard = Class->getName().upper();
878 Enum->Class = Class;
879
880 collectEnumEntries(Enum&: *Enum, NameField, ValueField, Items);
881
882 Enums.emplace_back(args: std::move(Enum));
883 }
884
885 auto Table = std::make_unique<GenericTable>();
886 Table->Name = (Twine(Class->getName()) + "sList").str();
887 Table->Locs = Class->getLoc();
888 Table->PreprocessorGuard = Class->getName().upper();
889 Table->CppTypeName = Class->getName().str();
890
891 for (const RecordVal &Field : Class->getValues()) {
892 std::string FieldName = Field.getName().str();
893
894 // Skip uninteresting fields: either special to us, or injected
895 // template parameters (if they contain a ':').
896 if (FieldName.find(c: ':') != std::string::npos ||
897 FieldName == "SearchableFields" || FieldName == "EnumNameField" ||
898 FieldName == "EnumValueField")
899 continue;
900
901 Table->Fields.emplace_back(Args&: FieldName);
902 }
903
904 collectTableEntries(Table&: *Table, Items);
905
906 for (const auto &Field :
907 Class->getValueAsListOfStrings(FieldName: "SearchableFields")) {
908 std::string Name =
909 (Twine("lookup") + Table->CppTypeName + "By" + Field).str();
910 Table->Indices.push_back(
911 Elt: parseSearchIndex(Table&: *Table, KeyRecVal: Class->getValue(Name: Field), Name, Key: {Field},
912 /*EarlyOut*/ false, /*ReturnRange*/ false));
913 }
914
915 Tables.emplace_back(Args: std::move(Table));
916 }
917
918 // Emit everything.
919 for (const auto &Enum : Enums)
920 emitGenericEnum(Enum: *Enum, OS);
921
922 for (const auto &Table : Tables)
923 emitGenericTable(Table: *Table, OS);
924
925 // Put all #undefs last, to allow multiple sections guarded by the same
926 // define.
927 for (const auto &Guard : PreprocessorGuards)
928 OS << "#undef " << Guard << "\n";
929}
930
931static TableGen::Emitter::OptClass<SearchableTableEmitter>
932 X("gen-searchable-tables", "Generate generic binary-searchable table");
933