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