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