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 ')';
435 OS << " if (" << TS << Field.Name << " != std::clamp(" << TS << Field.Name
436 << ", " << 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 else
446 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, Ctx: 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>(Val: Field.RecType)) {
464 OS << ".upper()";
465 if (IsPrimary)
466 PrintFatalError(ErrorLoc: Index.Loc,
467 Msg: 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 " << IndexTypeName
477 << " &LHS, const KeyType &RHS) const {\n";
478
479 auto emitComparator = [&]() {
480 for (const auto &Field : Index.Fields) {
481 if (isa<StringRecTy>(Val: Field.RecType)) {
482 OS << " int Cmp" << Field.Name << " = StringRef(LHS." << Field.Name
483 << ").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 is
488 // 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.Name
497 << ")\n";
498 OS << " return true;\n";
499 OS << " if (LHS." << Field.Name << " > RHS." << Field.Name
500 << ")\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 " << IndexTypeName
511 << " &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 else
520 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 else
548 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, Ctx: TypeInArgument) << " "
553 << Field.Name;
554 OS << ")";
555}
556
557void SearchableTableEmitter::emitGenericTable(const GenericTable &Table,
558 raw_ostream &OS) {
559 emitIfdef(Guard: (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, Index: *Table.PrimaryKey, OS);
564 OS << ";\n";
565 }
566 for (const auto &Index : Table.Indices) {
567 emitLookupDeclaration(Table, Index: *Index, OS);
568 OS << ";\n";
569 }
570
571 OS << "#endif\n\n";
572
573 emitIfdef(Guard: (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(First: Table.Entries)) {
578 OS << " { ";
579
580 ListSeparator LS;
581 for (const auto &Field : Table.Fields)
582 OS << LS
583 << primaryRepresentation(Loc: Table.Locs[0], Field,
584 I: Entry->getValueInit(FieldName: Field.Name));
585
586 OS << " }, // " << Idx << "\n";
587 }
588 OS << " };\n";
589
590 // Indexes are sorted "{ Thing, PrimaryIdx }" arrays, so that a binary
591 // search can be performed by "Thing".
592 if (Table.PrimaryKey)
593 emitLookupFunction(Table, Index: *Table.PrimaryKey, /*IsPrimary=*/true, OS);
594 for (const auto &Index : Table.Indices)
595 emitLookupFunction(Table, Index: *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>(Val: 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(Name: TypeStr)) {
614 if (TypeRec->isSubClassOf(Name: "GenericEnum")) {
615 Field.Enum = EnumMap[TypeRec];
616 Field.RecType = RecordRecTy::get(Class: 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(Name: FieldName);
635 if (!Field)
636 PrintFatalError(
637 RecVal: KeyRecVal,
638 Msg: Twine("In table '") + Table.Name +
639 "', 'PrimaryKey' or 'Key' refers to nonexistent field '" +
640 FieldName + "'");
641
642 Index->Fields.push_back(Elt: *Field);
643 }
644
645 if (EarlyOut && isa<StringRecTy>(Val: Index->Fields[0].RecType)) {
646 PrintFatalError(
647 RecVal: KeyRecVal, Msg: 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(NumEntries: Items.size());
658 for (const Record *EntryRec : Items) {
659 StringRef Name = NameField.empty() ? EntryRec->getName()
660 : EntryRec->getValueAsString(FieldName: NameField);
661 int64_t Value = ValueField.empty() ? 0 : getInt(R: EntryRec, Field: ValueField);
662 Enum.Entries.try_emplace(Key: EntryRec, Args&: Name, Args&: Value);
663 }
664
665 // If no values are provided for enums, assign values in the order of sorted
666 // 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(Range&: SavedEntries, C: [](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(First&: SavedEntries))
678 Enum.Entries.try_emplace(Key: Entry.first, Args&: Entry.second.Name, Args&: Idx);
679 }
680}
681
682void SearchableTableEmitter::collectTableEntries(
683 GenericTable &Table, ArrayRef<const Record *> Items) {
684 if (Items.empty())
685 PrintFatalError(ErrorLoc: Table.Locs,
686 Msg: 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>(Val: EntryRec->getValueInit(FieldName: Field.Name));
691 if (!TI || !TI->isComplete()) {
692 PrintFatalError(Rec: EntryRec, Msg: 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(T1: Field.RecType, T2: TI->getType());
701 if (!Ty)
702 PrintFatalError(RecVal: EntryRec->getValue(Name: Field.Name),
703 Msg: 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(x: EntryRec); // Add record to table's record list.
712 }
713
714 const Record *IntrinsicClass = Records.getClass(Name: "Intrinsic");
715 const Record *InstructionClass = Records.getClass(Name: "Instruction");
716 for (auto &Field : Table.Fields) {
717 if (!Field.RecType)
718 PrintFatalError(Msg: 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>(Val: Field.RecType)) {
722 if (IntrinsicClass && RecordTy->isSubClassOf(Class: IntrinsicClass))
723 Field.IsIntrinsic = true;
724 else if (InstructionClass && RecordTy->isSubClassOf(Class: InstructionClass))
725 Field.IsInstruction = true;
726 }
727 }
728
729 SearchIndex Idx;
730 llvm::append_range(C&: Idx.Fields, R&: Table.Fields);
731 llvm::sort(C&: Table.Entries, Comp: [&](const Record *LHS, const Record *RHS) {
732 return compareBy(LHS, RHS, Index: 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(ClassName: "Instruction").empty() ||
742 !Records.getAllDerivedDefinitionsIfDefined(ClassName: "Intrinsic").empty();
743 if (NeedsTarget)
744 Target = std::make_unique<CodeGenTarget>(args: Records);
745
746 // Collect all definitions first.
747 for (const auto *EnumRec : Records.getAllDerivedDefinitions(ClassName: "GenericEnum")) {
748 StringRef NameField;
749 if (!EnumRec->isValueUnset(FieldName: "NameField"))
750 NameField = EnumRec->getValueAsString(FieldName: "NameField");
751
752 StringRef ValueField;
753 if (!EnumRec->isValueUnset(FieldName: "ValueField"))
754 ValueField = EnumRec->getValueAsString(FieldName: "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(FieldName: "FilterClass");
761 Enum->Class = Records.getClass(Name: FilterClass);
762 if (!Enum->Class)
763 PrintFatalError(RecVal: EnumRec->getValue(Name: "FilterClass"),
764 Msg: Twine("Enum FilterClass '") + FilterClass +
765 "' does not exist");
766
767 collectEnumEntries(Enum&: *Enum, NameField, ValueField,
768 Items: Records.getAllDerivedDefinitions(ClassName: FilterClass));
769 EnumMap.try_emplace(Key: EnumRec, Args: Enum.get());
770 Enums.emplace_back(args: std::move(Enum));
771 }
772
773 for (const auto *TableRec :
774 Records.getAllDerivedDefinitions(ClassName: "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(FieldName: "CppTypeName").str();
780
781 std::vector<StringRef> Fields = TableRec->getValueAsListOfStrings(FieldName: "Fields");
782 for (const auto &FieldName : Fields) {
783 Table->Fields.emplace_back(Args: FieldName); // Construct a GenericField.
784
785 if (auto TypeOfRecordVal =
786 TableRec->getValue(Name: ("TypeOf_" + FieldName).str())) {
787 if (!parseFieldType(Field&: Table->Fields.back(),
788 TypeOf: TypeOfRecordVal->getValue())) {
789 PrintError(RecVal: TypeOfRecordVal,
790 Msg: Twine("Table '") + Table->Name + "' has invalid 'TypeOf_" +
791 FieldName +
792 "': " + TypeOfRecordVal->getValue()->getAsString());
793 PrintFatalNote(Msg: "The 'TypeOf_xxx' field must be a string naming a "
794 "GenericEnum record, or \"code\"");
795 }
796 }
797 }
798
799 StringRef FilterClass = TableRec->getValueAsString(FieldName: "FilterClass");
800 if (!Records.getClass(Name: FilterClass))
801 PrintFatalError(RecVal: TableRec->getValue(Name: "FilterClass"),
802 Msg: Twine("Table FilterClass '") + FilterClass +
803 "' does not exist");
804
805 const RecordVal *FilterClassFieldVal =
806 TableRec->getValue(Name: "FilterClassField");
807 std::vector<const Record *> Definitions =
808 Records.getAllDerivedDefinitions(ClassName: FilterClass);
809 if (auto *FilterClassFieldInit =
810 dyn_cast<StringInit>(Val: FilterClassFieldVal->getValue())) {
811 StringRef FilterClassField = FilterClassFieldInit->getValue();
812 llvm::erase_if(C&: Definitions, P: [&](const Record *R) {
813 const RecordVal *Filter = R->getValue(Name: FilterClassField);
814 if (auto *BitV = dyn_cast<BitInit>(Val: Filter->getValue()))
815 return !BitV->getValue();
816
817 PrintFatalError(RecVal: Filter, Msg: Twine("FilterClassField '") + FilterClass +
818 "' should be a bit value");
819 return true;
820 });
821 }
822 collectTableEntries(Table&: *Table, Items: Definitions);
823
824 if (!TableRec->isValueUnset(FieldName: "PrimaryKey")) {
825 Table->PrimaryKey =
826 parseSearchIndex(Table&: *Table, KeyRecVal: TableRec->getValue(Name: "PrimaryKey"),
827 Name: TableRec->getValueAsString(FieldName: "PrimaryKeyName"),
828 Key: TableRec->getValueAsListOfStrings(FieldName: "PrimaryKey"),
829 EarlyOut: TableRec->getValueAsBit(FieldName: "PrimaryKeyEarlyOut"),
830 ReturnRange: TableRec->getValueAsBit(FieldName: "PrimaryKeyReturnRange"));
831
832 llvm::stable_sort(Range&: Table->Entries,
833 C: [&](const Record *LHS, const Record *RHS) {
834 return compareBy(LHS, RHS, Index: *Table->PrimaryKey);
835 });
836 }
837
838 TableMap.try_emplace(Key: TableRec, Args: Table.get());
839 Tables.emplace_back(Args: std::move(Table));
840 }
841
842 for (const Record *IndexRec :
843 Records.getAllDerivedDefinitions(ClassName: "SearchIndex")) {
844 const Record *TableRec = IndexRec->getValueAsDef(FieldName: "Table");
845 auto It = TableMap.find(Val: TableRec);
846 if (It == TableMap.end())
847 PrintFatalError(RecVal: IndexRec->getValue(Name: "Table"),
848 Msg: Twine("SearchIndex '") + IndexRec->getName() +
849 "' refers to nonexistent table '" +
850 TableRec->getName());
851
852 GenericTable &Table = *It->second;
853 Table.Indices.push_back(Elt: parseSearchIndex(
854 Table, KeyRecVal: IndexRec->getValue(Name: "Key"), Name: IndexRec->getName(),
855 Key: IndexRec->getValueAsListOfStrings(FieldName: "Key"),
856 EarlyOut: IndexRec->getValueAsBit(FieldName: "EarlyOut"), /*ReturnRange*/ false));
857 }
858
859 // Translate legacy tables.
860 const Record *SearchableTable = Records.getClass(Name: "SearchableTable");
861 for (auto &NameRec : Records.getClasses()) {
862 const Record *Class = NameRec.second.get();
863 if (Class->getDirectSuperClasses().size() != 1 ||
864 !Class->isSubClassOf(R: SearchableTable))
865 continue;
866
867 StringRef TableName = Class->getName();
868 ArrayRef<const Record *> Items =
869 Records.getAllDerivedDefinitions(ClassName: TableName);
870 if (!Class->isValueUnset(FieldName: "EnumNameField")) {
871 StringRef NameField = Class->getValueAsString(FieldName: "EnumNameField");
872 StringRef ValueField;
873 if (!Class->isValueUnset(FieldName: "EnumValueField"))
874 ValueField = Class->getValueAsString(FieldName: "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&: *Enum, NameField, ValueField, Items);
882
883 Enums.emplace_back(args: 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 injected
896 // template parameters (if they contain a ':').
897 if (FieldName.find(c: ':') != std::string::npos ||
898 FieldName == "SearchableFields" || FieldName == "EnumNameField" ||
899 FieldName == "EnumValueField")
900 continue;
901
902 Table->Fields.emplace_back(Args&: FieldName);
903 }
904
905 collectTableEntries(Table&: *Table, Items);
906
907 for (const auto &Field :
908 Class->getValueAsListOfStrings(FieldName: "SearchableFields")) {
909 std::string Name =
910 (Twine("lookup") + Table->CppTypeName + "By" + Field).str();
911 Table->Indices.push_back(
912 Elt: parseSearchIndex(Table&: *Table, KeyRecVal: Class->getValue(Name: Field), Name, Key: {Field},
913 /*EarlyOut*/ false, /*ReturnRange*/ false));
914 }
915
916 Tables.emplace_back(Args: std::move(Table));
917 }
918
919 // Emit everything.
920 for (const auto &Enum : Enums)
921 emitGenericEnum(Enum: *Enum, OS);
922
923 for (const auto &Table : Tables)
924 emitGenericTable(Table: *Table, OS);
925
926 // Put all #undefs last, to allow multiple sections guarded by the same
927 // 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