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