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