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