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

source code of llvm/utils/TableGen/SearchableTableEmitter.cpp