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