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 if (LHSIsKey)
501 OS << " StringRef LHSStr = LHS." << Field.Name << ";\n";
502 else
503 OS << " StringRef LHSStr = " << Table.Name << "Strings[LHS."
504 << Field.Name << "];\n";
505 if (RHSIsKey)
506 OS << " StringRef RHSStr = RHS." << Field.Name << ";\n";
507 else
508 OS << " StringRef RHSStr = " << Table.Name << "Strings[RHS."
509 << Field.Name << "];\n";
510 OS << " int Cmp" << Field.Name << " = LHSStr.compare(RHSStr);\n";
511 OS << " if (Cmp" << Field.Name << " < 0) return true;\n";
512 OS << " if (Cmp" << Field.Name << " > 0) return false;\n";
513 } else if (Field.Enum) {
514 // Explicitly cast to unsigned, because the signedness of enums is
515 // compiler-dependent.
516 OS << " if ((unsigned)LHS." << Field.Name << " < (unsigned)RHS."
517 << Field.Name << ")\n";
518 OS << " return true;\n";
519 OS << " if ((unsigned)LHS." << Field.Name << " > (unsigned)RHS."
520 << Field.Name << ")\n";
521 OS << " return false;\n";
522 } else {
523 OS << " if (LHS." << Field.Name << " < RHS." << Field.Name
524 << ")\n";
525 OS << " return true;\n";
526 OS << " if (LHS." << Field.Name << " > RHS." << Field.Name
527 << ")\n";
528 OS << " return false;\n";
529 }
530 }
531 OS << " return false;\n";
532 OS << " }\n";
533 };
534 emitComparator(false, true);
535 bool ShouldReturnRange = Index.ReturnRange;
536 if (ShouldReturnRange) {
537 OS << " bool operator()(const KeyType &LHS, const " << IndexTypeName
538 << " &RHS) const {\n";
539 emitComparator(true, false);
540 }
541
542 OS << " };\n";
543 OS << " auto Table = ArrayRef(" << IndexName << ");\n";
544 if (ShouldReturnRange)
545 OS << " auto It = std::equal_range(Table.begin(), Table.end(), Key, ";
546 else
547 OS << " auto Idx = std::lower_bound(Table.begin(), Table.end(), Key, ";
548 OS << "Comp());\n";
549
550 if (!ShouldReturnRange) {
551 OS << " if (Idx == Table.end()";
552 for (const auto &Field : Index.Fields) {
553 OS << " ||\n Key." << Field.Name << " != ";
554 if (isa<StringRecTy>(Val: Field.RecType))
555 OS << Table.Name << "Strings[Idx->" << Field.Name << "]";
556 else
557 OS << "Idx->" << Field.Name;
558 }
559 }
560
561 if (ShouldReturnRange) {
562 OS << " return llvm::make_range(It.first, It.second);\n";
563 } else if (IsPrimary) {
564 OS << ")\n return nullptr;\n\n";
565 OS << " return &*Idx;\n";
566 } else {
567 OS << ")\n return nullptr;\n\n";
568 OS << " return &" << Table.Name << "[Idx->_index];\n";
569 }
570
571 OS << "}\n";
572}
573
574void SearchableTableEmitter::emitLookupDeclaration(const GenericTable &Table,
575 const SearchIndex &Index,
576 raw_ostream &OS) {
577 if (Index.ReturnRange)
578 OS << "llvm::iterator_range<const " << Table.CppTypeName << " *> ";
579 else
580 OS << "const " << Table.CppTypeName << " *";
581 OS << Index.Name << "(";
582 ListSeparator LS;
583 for (const auto &Field : Index.Fields)
584 OS << LS << searchableFieldType(Table, Index, Field, Ctx: TypeInArgument) << " "
585 << Field.Name;
586 OS << ")";
587}
588
589void SearchableTableEmitter::emitGenericTable(const GenericTable &Table,
590 raw_ostream &OS) {
591 emitIfdef(Guard: (Twine("GET_") + Table.PreprocessorGuard + "_DECL").str(), OS);
592
593 // Emit the declarations for the functions that will perform lookup.
594 if (Table.PrimaryKey) {
595 emitLookupDeclaration(Table, Index: *Table.PrimaryKey, OS);
596 OS << ";\n";
597 }
598 for (const auto &Index : Table.Indices) {
599 emitLookupDeclaration(Table, Index: *Index, OS);
600 OS << ";\n";
601 }
602
603 bool HasStrings = false;
604 for (const auto &Field : Table.Fields)
605 HasStrings |= isa<StringRecTy>(Val: Field.RecType);
606 if (HasStrings)
607 OS << "StringRef get" << Table.CppTypeName << "Str(StringTable::Offset);\n";
608
609 OS << "#endif\n\n";
610
611 emitIfdef(Guard: (Twine("GET_") + Table.PreprocessorGuard + "_IMPL").str(), OS);
612
613 StringToOffsetTable StrTab;
614
615 SmallVector<const Record *, 0> SparseEntries;
616 ArrayRef<const Record *> Entries;
617 unsigned DirectLookupSlots = 0;
618 if (Table.AllowSparseTable) {
619 const auto *KeyBits = cast<BitsRecTy>(Val: Table.PrimaryKey->Fields[0].RecType);
620 DirectLookupSlots = 1u << KeyBits->getNumBits();
621 SparseEntries.resize(N: DirectLookupSlots);
622 StringRef KeyFieldName = Table.PrimaryKey->Fields[0].Name;
623 for (const Record *Entry : Table.Entries) {
624 uint64_t Key = static_cast<uint64_t>(getInt(R: Entry, Field: KeyFieldName));
625 assert(Key < DirectLookupSlots && "key exceeds table size");
626 if (SparseEntries[Key])
627 PrintFatalError(Rec: Entry, Msg: Twine("In table '") + Table.Name +
628 "', duplicate primary key value " +
629 Twine(Key));
630 SparseEntries[Key] = Entry;
631 }
632 Entries = SparseEntries;
633 } else {
634 Entries = Table.Entries;
635 }
636
637 // The primary data table contains all the fields defined for this map.
638 OS << "constexpr " << Table.CppTypeName << " " << Table.Name << "[] = {\n";
639 for (const auto &[Idx, Entry] : enumerate(First&: Entries)) {
640 OS << " { ";
641 ListSeparator LS;
642 if (Entry) {
643 for (const auto &Field : Table.Fields) {
644 OS << LS;
645 const Init *Value = Entry->getValueInit(FieldName: Field.Name);
646 if (const auto *SI = dyn_cast<StringInit>(Val: Value);
647 SI && !Field.IsCode && !SI->hasCodeFormat()) {
648 OS << StrTab.GetOrAddStringOffset(Str: Value->getAsUnquotedString())
649 << " /* " << primaryRepresentation(Loc: Table.Locs[0], Field, I: Value)
650 << " */";
651 } else {
652 OS << primaryRepresentation(Loc: Table.Locs[0], Field, I: Value);
653 }
654 }
655 } else if (Table.AllowSparseTable) {
656 // For empty rows emit a sentinel value as a key, so we can return null
657 // during lookup. Value is constructed such that LookupKey != KeyField.
658 for (const auto &Field : Table.Fields) {
659 OS << LS;
660 if (Field.Name == Table.PrimaryKey->Fields[0].Name)
661 OS << "0x" << (Idx == 0 ? 1 : 0);
662 else
663 OS << "{}";
664 }
665 }
666 OS << " }, // " << Idx << "\n";
667 }
668 OS << " };\n";
669
670 // Emit into string first so we can put the string table before the function.
671 // The lookup function might add more strings.
672 std::string LookupFunction;
673 raw_string_ostream LFOS(LookupFunction);
674 if (Table.AllowSparseTable) {
675 LFOS << "\n";
676 emitLookupDeclaration(Table, Index: *Table.PrimaryKey, OS&: LFOS);
677 LFOS << " {\n";
678 const GenericField &Field = Table.PrimaryKey->Fields[0];
679 LFOS << " if (" << Field.Name << " >= " << DirectLookupSlots << ")\n";
680 LFOS << " return nullptr;\n";
681 LFOS << " const auto *Entry = &" << Table.Name << "[" << Field.Name
682 << "];\n";
683 LFOS << " return Entry->" << Field.Name << " == " << Field.Name
684 << " ? Entry : nullptr;\n";
685 LFOS << "}\n";
686 } else if (Table.PrimaryKey) {
687 // Indexes are sorted "{ Thing, PrimaryIdx }" arrays, so that a binary
688 // search can be performed by "Thing".
689 emitLookupFunction(Table, Index: *Table.PrimaryKey, /*IsPrimary=*/true, StrTab,
690 OS&: LFOS);
691 }
692 for (const auto &Index : Table.Indices)
693 emitLookupFunction(Table, Index: *Index, /*IsPrimary=*/false, StrTab, OS&: LFOS);
694
695 if (HasStrings) {
696 StrTab.EmitStringTableDef(OS, Name: Table.Name + Twine("Strings"));
697 OS << "\nStringRef get" << Table.CppTypeName
698 << "Str(StringTable::Offset Offset) {\n";
699 OS << " return " << Table.Name << "Strings[Offset];\n";
700 OS << "}\n";
701 }
702
703 OS << LookupFunction;
704
705 OS << "#endif\n\n";
706}
707
708bool SearchableTableEmitter::parseFieldType(GenericField &Field,
709 const Init *TypeOf) {
710 auto Type = dyn_cast<StringInit>(Val: TypeOf);
711 if (!Type)
712 return false;
713
714 StringRef TypeStr = Type->getValue();
715
716 if (TypeStr == "code") {
717 Field.IsCode = true;
718 return true;
719 }
720
721 if (const Record *TypeRec = Records.getDef(Name: TypeStr)) {
722 if (TypeRec->isSubClassOf(Name: "GenericEnum")) {
723 Field.Enum = EnumMap[TypeRec];
724 Field.RecType = RecordRecTy::get(Class: Field.Enum->Class);
725 return true;
726 }
727 }
728
729 return false;
730}
731
732std::unique_ptr<SearchIndex> SearchableTableEmitter::parseSearchIndex(
733 GenericTable &Table, const RecordVal *KeyRecVal, StringRef Name,
734 ArrayRef<StringRef> Key, bool EarlyOut, bool ReturnRange) {
735 auto Index = std::make_unique<SearchIndex>();
736 Index->Name = Name.str();
737 Index->Loc = KeyRecVal->getLoc();
738 Index->EarlyOut = EarlyOut;
739 Index->ReturnRange = ReturnRange;
740
741 for (const auto &FieldName : Key) {
742 const GenericField *Field = Table.getFieldByName(Name: FieldName);
743 if (!Field)
744 PrintFatalError(
745 RecVal: KeyRecVal,
746 Msg: Twine("In table '") + Table.Name +
747 "', 'PrimaryKey' or 'Key' refers to nonexistent field '" +
748 FieldName + "'");
749
750 Index->Fields.push_back(Elt: *Field);
751 }
752
753 if (EarlyOut && isa<StringRecTy>(Val: Index->Fields[0].RecType)) {
754 PrintFatalError(
755 RecVal: KeyRecVal, Msg: Twine("In lookup method '") + Name + "', early-out is not " +
756 "supported for a first key field of type string");
757 }
758
759 return Index;
760}
761
762void SearchableTableEmitter::collectEnumEntries(
763 GenericEnum &Enum, StringRef NameField, StringRef ValueField,
764 ArrayRef<const Record *> Items) {
765 Enum.Entries.reserve(NumEntries: Items.size());
766 for (const Record *EntryRec : Items) {
767 StringRef Name = NameField.empty() ? EntryRec->getName()
768 : EntryRec->getValueAsString(FieldName: NameField);
769 int64_t Value = ValueField.empty() ? 0 : getInt(R: EntryRec, Field: ValueField);
770 Enum.Entries.try_emplace(Key: EntryRec, Args&: Name, Args&: Value);
771 }
772
773 // If no values are provided for enums, assign values in the order of sorted
774 // enum names.
775 if (ValueField.empty()) {
776 // Copy the map entries for sorting and clear the map.
777 auto SavedEntries = Enum.Entries.takeVector();
778 using MapVectorEntryTy = std::pair<const Record *, GenericEnum::Entry>;
779 llvm::stable_sort(Range&: SavedEntries, C: [](const MapVectorEntryTy &LHS,
780 const MapVectorEntryTy &RHS) {
781 return LHS.second.Name < RHS.second.Name;
782 });
783
784 // Repopulate entries using the new sorted order.
785 for (auto [Idx, Entry] : enumerate(First&: SavedEntries))
786 Enum.Entries.try_emplace(Key: Entry.first, Args&: Entry.second.Name, Args&: Idx);
787 }
788}
789
790void SearchableTableEmitter::collectTableEntries(
791 GenericTable &Table, ArrayRef<const Record *> Items) {
792 if (Items.empty())
793 PrintFatalError(ErrorLoc: Table.Locs,
794 Msg: Twine("Table '") + Table.Name + "' has no entries");
795
796 for (auto *EntryRec : Items) {
797 for (auto &Field : Table.Fields) {
798 auto TI = dyn_cast<TypedInit>(Val: EntryRec->getValueInit(FieldName: Field.Name));
799 if (!TI || !TI->isComplete()) {
800 PrintFatalError(Rec: EntryRec, Msg: Twine("Record '") + EntryRec->getName() +
801 "' for table '" + Table.Name +
802 "' is missing field '" + Field.Name +
803 "'");
804 }
805 if (!Field.RecType) {
806 Field.RecType = TI->getType();
807 } else {
808 const RecTy *Ty = resolveTypes(T1: Field.RecType, T2: TI->getType());
809 if (!Ty)
810 PrintFatalError(RecVal: EntryRec->getValue(Name: Field.Name),
811 Msg: Twine("Field '") + Field.Name + "' of table '" +
812 Table.Name + "' entry has incompatible type: " +
813 TI->getType()->getAsString() + " vs. " +
814 Field.RecType->getAsString());
815 Field.RecType = Ty;
816 }
817 }
818
819 Table.Entries.push_back(x: EntryRec); // Add record to table's record list.
820 }
821
822 const Record *IntrinsicClass = Records.getClass(Name: "Intrinsic");
823 const Record *InstructionClass = Records.getClass(Name: "Instruction");
824 for (auto &Field : Table.Fields) {
825 if (!Field.RecType)
826 PrintFatalError(Msg: Twine("Cannot determine type of field '") + Field.Name +
827 "' in table '" + Table.Name + "'. Maybe it is not used?");
828
829 if (auto RecordTy = dyn_cast<RecordRecTy>(Val: Field.RecType)) {
830 if (IntrinsicClass && RecordTy->isSubClassOf(Class: IntrinsicClass))
831 Field.IsIntrinsic = true;
832 else if (InstructionClass && RecordTy->isSubClassOf(Class: InstructionClass))
833 Field.IsInstruction = true;
834 }
835 }
836
837 SearchIndex Idx;
838 llvm::append_range(C&: Idx.Fields, R&: Table.Fields);
839 llvm::sort(C&: Table.Entries, Comp: [&](const Record *LHS, const Record *RHS) {
840 return compareBy(LHS, RHS, Index: Idx);
841 });
842}
843
844static bool canUseSparseTable(const Record *TableRec,
845 const std::unique_ptr<GenericTable> &Table) {
846 if (TableRec->getValueAsBit(FieldName: "DisallowSparseTable"))
847 return false;
848
849 // Sparse tables are only supported with a single primary key.
850 if (Table->PrimaryKey->Fields.size() != 1)
851 return false;
852
853 const auto *KeyBits =
854 dyn_cast<BitsRecTy>(Val: Table->PrimaryKey->Fields[0].RecType);
855
856 // Sparse tables only support `bits` key.
857 if (!KeyBits)
858 return false;
859
860 // Sparse tables are not compatible with PrimaryKeyReturnRange.
861 if (TableRec->getValueAsBit(FieldName: "PrimaryKeyReturnRange"))
862 return false;
863
864 // Only support tables up to 4k in size.
865 constexpr unsigned MaxKeyBits = 12;
866 if (KeyBits->getNumBits() > MaxKeyBits)
867 return false;
868
869 return true;
870}
871
872void SearchableTableEmitter::run(raw_ostream &OS) {
873 // Emit tables in a deterministic order to avoid needless rebuilds.
874 SmallVector<std::unique_ptr<GenericTable>, 4> Tables;
875 DenseMap<const Record *, GenericTable *> TableMap;
876 bool NeedsTarget =
877 !Records.getAllDerivedDefinitionsIfDefined(ClassName: "Instruction").empty() ||
878 !Records.getAllDerivedDefinitionsIfDefined(ClassName: "Intrinsic").empty();
879 if (NeedsTarget)
880 Target = std::make_unique<CodeGenTarget>(args: Records);
881
882 // Collect all definitions first.
883 for (const auto *EnumRec : Records.getAllDerivedDefinitions(ClassName: "GenericEnum")) {
884 StringRef NameField;
885 if (!EnumRec->isValueUnset(FieldName: "NameField"))
886 NameField = EnumRec->getValueAsString(FieldName: "NameField");
887
888 StringRef ValueField;
889 if (!EnumRec->isValueUnset(FieldName: "ValueField"))
890 ValueField = EnumRec->getValueAsString(FieldName: "ValueField");
891
892 auto Enum = std::make_unique<GenericEnum>();
893 Enum->Name = EnumRec->getName().str();
894 Enum->PreprocessorGuard = EnumRec->getName().str();
895
896 StringRef FilterClass = EnumRec->getValueAsString(FieldName: "FilterClass");
897 Enum->Class = Records.getClass(Name: FilterClass);
898 if (!Enum->Class)
899 PrintFatalError(RecVal: EnumRec->getValue(Name: "FilterClass"),
900 Msg: Twine("Enum FilterClass '") + FilterClass +
901 "' does not exist");
902
903 if (!EnumRec->isValueUnset(FieldName: "UnderlyingType"))
904 Enum->UnderlyingType = EnumRec->getValueAsString(FieldName: "UnderlyingType");
905
906 collectEnumEntries(Enum&: *Enum, NameField, ValueField,
907 Items: Records.getAllDerivedDefinitions(ClassName: FilterClass));
908 EnumMap.try_emplace(Key: EnumRec, Args: Enum.get());
909 Enums.emplace_back(args: std::move(Enum));
910 }
911
912 for (const auto *TableRec :
913 Records.getAllDerivedDefinitions(ClassName: "GenericTable")) {
914 auto Table = std::make_unique<GenericTable>();
915 Table->Name = TableRec->getName().str();
916 Table->Locs = TableRec->getLoc();
917 Table->PreprocessorGuard = TableRec->getName().str();
918 Table->CppTypeName = TableRec->getValueAsString(FieldName: "CppTypeName").str();
919
920 std::vector<StringRef> Fields = TableRec->getValueAsListOfStrings(FieldName: "Fields");
921 for (const auto &FieldName : Fields) {
922 Table->Fields.emplace_back(Args: FieldName); // Construct a GenericField.
923
924 if (auto TypeOfRecordVal =
925 TableRec->getValue(Name: ("TypeOf_" + FieldName).str())) {
926 if (!parseFieldType(Field&: Table->Fields.back(),
927 TypeOf: TypeOfRecordVal->getValue())) {
928 PrintError(RecVal: TypeOfRecordVal,
929 Msg: Twine("Table '") + Table->Name + "' has invalid 'TypeOf_" +
930 FieldName +
931 "': " + TypeOfRecordVal->getValue()->getAsString());
932 PrintFatalNote(Msg: "The 'TypeOf_xxx' field must be a string naming a "
933 "GenericEnum record, or \"code\"");
934 }
935 }
936 }
937
938 StringRef FilterClass = TableRec->getValueAsString(FieldName: "FilterClass");
939 if (!Records.getClass(Name: FilterClass))
940 PrintFatalError(RecVal: TableRec->getValue(Name: "FilterClass"),
941 Msg: Twine("Table FilterClass '") + FilterClass +
942 "' does not exist");
943
944 const RecordVal *FilterClassFieldVal =
945 TableRec->getValue(Name: "FilterClassField");
946 std::vector<const Record *> Definitions =
947 Records.getAllDerivedDefinitions(ClassName: FilterClass);
948 if (auto *FilterClassFieldInit =
949 dyn_cast<StringInit>(Val: FilterClassFieldVal->getValue())) {
950 StringRef FilterClassField = FilterClassFieldInit->getValue();
951 llvm::erase_if(C&: Definitions, P: [&](const Record *R) {
952 const RecordVal *Filter = R->getValue(Name: FilterClassField);
953 if (auto *BitV = dyn_cast<BitInit>(Val: Filter->getValue()))
954 return !BitV->getValue();
955
956 PrintFatalError(RecVal: Filter, Msg: Twine("FilterClassField '") + FilterClass +
957 "' should be a bit value");
958 return true;
959 });
960 }
961 collectTableEntries(Table&: *Table, Items: Definitions);
962
963 if (!TableRec->isValueUnset(FieldName: "PrimaryKey")) {
964 Table->PrimaryKey =
965 parseSearchIndex(Table&: *Table, KeyRecVal: TableRec->getValue(Name: "PrimaryKey"),
966 Name: TableRec->getValueAsString(FieldName: "PrimaryKeyName"),
967 Key: TableRec->getValueAsListOfStrings(FieldName: "PrimaryKey"),
968 EarlyOut: TableRec->getValueAsBit(FieldName: "PrimaryKeyEarlyOut"),
969 ReturnRange: TableRec->getValueAsBit(FieldName: "PrimaryKeyReturnRange"));
970
971 llvm::stable_sort(Range&: Table->Entries,
972 C: [&](const Record *LHS, const Record *RHS) {
973 return compareBy(LHS, RHS, Index: *Table->PrimaryKey);
974 });
975
976 Table->AllowSparseTable = canUseSparseTable(TableRec, Table);
977 }
978
979 TableMap.try_emplace(Key: TableRec, Args: Table.get());
980 Tables.emplace_back(Args: std::move(Table));
981 }
982
983 for (const Record *IndexRec :
984 Records.getAllDerivedDefinitions(ClassName: "SearchIndex")) {
985 const Record *TableRec = IndexRec->getValueAsDef(FieldName: "Table");
986 auto It = TableMap.find(Val: TableRec);
987 if (It == TableMap.end())
988 PrintFatalError(RecVal: IndexRec->getValue(Name: "Table"),
989 Msg: Twine("SearchIndex '") + IndexRec->getName() +
990 "' refers to nonexistent table '" +
991 TableRec->getName());
992
993 GenericTable &Table = *It->second;
994 Table.Indices.push_back(Elt: parseSearchIndex(
995 Table, KeyRecVal: IndexRec->getValue(Name: "Key"), Name: IndexRec->getName(),
996 Key: IndexRec->getValueAsListOfStrings(FieldName: "Key"),
997 EarlyOut: IndexRec->getValueAsBit(FieldName: "EarlyOut"), /*ReturnRange*/ false));
998
999 // Sparse tables with secondary search indices are not supported.
1000 Table.AllowSparseTable = false;
1001 }
1002
1003 // Translate legacy tables.
1004 const Record *SearchableTable = Records.getClass(Name: "SearchableTable");
1005 for (auto &NameRec : Records.getClasses()) {
1006 const Record *Class = NameRec.second.get();
1007 if (Class->getDirectSuperClasses().size() != 1 ||
1008 !Class->isSubClassOf(R: SearchableTable))
1009 continue;
1010
1011 StringRef TableName = Class->getName();
1012 ArrayRef<const Record *> Items =
1013 Records.getAllDerivedDefinitions(ClassName: TableName);
1014 if (!Class->isValueUnset(FieldName: "EnumNameField")) {
1015 StringRef NameField = Class->getValueAsString(FieldName: "EnumNameField");
1016 StringRef ValueField;
1017 if (!Class->isValueUnset(FieldName: "EnumValueField"))
1018 ValueField = Class->getValueAsString(FieldName: "EnumValueField");
1019
1020 auto Enum = std::make_unique<GenericEnum>();
1021 Enum->Name = (Twine(Class->getName()) + "Values").str();
1022 Enum->PreprocessorGuard = Class->getName().upper();
1023 Enum->Class = Class;
1024
1025 collectEnumEntries(Enum&: *Enum, NameField, ValueField, Items);
1026
1027 Enums.emplace_back(args: std::move(Enum));
1028 }
1029
1030 auto Table = std::make_unique<GenericTable>();
1031 Table->Name = (Twine(Class->getName()) + "sList").str();
1032 Table->Locs = Class->getLoc();
1033 Table->PreprocessorGuard = Class->getName().upper();
1034 Table->CppTypeName = Class->getName().str();
1035
1036 for (const RecordVal &Field : Class->getValues()) {
1037 std::string FieldName = Field.getName().str();
1038
1039 // Skip uninteresting fields: either special to us, or injected
1040 // template parameters (if they contain a ':').
1041 if (FieldName.find(c: ':') != std::string::npos ||
1042 FieldName == "SearchableFields" || FieldName == "EnumNameField" ||
1043 FieldName == "EnumValueField")
1044 continue;
1045
1046 Table->Fields.emplace_back(Args&: FieldName);
1047 }
1048
1049 collectTableEntries(Table&: *Table, Items);
1050
1051 for (const auto &Field :
1052 Class->getValueAsListOfStrings(FieldName: "SearchableFields")) {
1053 std::string Name =
1054 (Twine("lookup") + Table->CppTypeName + "By" + Field).str();
1055 Table->Indices.push_back(
1056 Elt: parseSearchIndex(Table&: *Table, KeyRecVal: Class->getValue(Name: Field), Name, Key: {Field},
1057 /*EarlyOut*/ false, /*ReturnRange*/ false));
1058 }
1059
1060 Tables.emplace_back(Args: std::move(Table));
1061 }
1062
1063 // Emit everything.
1064 for (const auto &Enum : Enums)
1065 emitGenericEnum(Enum: *Enum, OS);
1066
1067 for (const auto &Table : Tables)
1068 emitGenericTable(Table: *Table, OS);
1069
1070 // Put all #undefs last, to allow multiple sections guarded by the same
1071 // define.
1072 for (const auto &Guard : PreprocessorGuards)
1073 OS << "#undef " << Guard << "\n";
1074}
1075
1076static TableGen::Emitter::OptClass<SearchableTableEmitter>
1077 X("gen-searchable-tables", "Generate generic binary-searchable table");
1078