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