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