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