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