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         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(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 << "const " << 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 = llvm::make_unique<SearchIndex>();
546   Index->Name = 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(llvm::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) {
603         PrintFatalError(Twine("Record '") + EntryRec->getName() +
604                         "' in table '" + Table.Name + "' is missing field '" +
605                         Field.Name + "'");
606       }
607       if (!Field.RecType) {
608         Field.RecType = TI->getType();
609       } else {
610         RecTy *Ty = resolveTypes(Field.RecType, TI->getType());
611         if (!Ty)
612           PrintFatalError(Twine("Field '") + Field.Name + "' of table '" +
613                           Table.Name + "' has incompatible type: " +
614                           Ty->getAsString() + " vs. " +
615                           TI->getType()->getAsString());
616         Field.RecType = Ty;
617       }
618     }
619 
620     Table.Entries.push_back(EntryRec);
621   }
622 
623   Record *IntrinsicClass = Records.getClass("Intrinsic");
624   Record *InstructionClass = Records.getClass("Instruction");
625   for (auto &Field : Table.Fields) {
626     if (auto RecordTy = dyn_cast<RecordRecTy>(Field.RecType)) {
627       if (IntrinsicClass && RecordTy->isSubClassOf(IntrinsicClass))
628         Field.IsIntrinsic = true;
629       else if (InstructionClass && RecordTy->isSubClassOf(InstructionClass))
630         Field.IsInstruction = true;
631     }
632   }
633 }
634 
635 void SearchableTableEmitter::run(raw_ostream &OS) {
636   // Emit tables in a deterministic order to avoid needless rebuilds.
637   SmallVector<std::unique_ptr<GenericTable>, 4> Tables;
638   DenseMap<Record *, GenericTable *> TableMap;
639 
640   // Collect all definitions first.
641   for (auto EnumRec : Records.getAllDerivedDefinitions("GenericEnum")) {
642     StringRef NameField;
643     if (!EnumRec->isValueUnset("NameField"))
644       NameField = EnumRec->getValueAsString("NameField");
645 
646     StringRef ValueField;
647     if (!EnumRec->isValueUnset("ValueField"))
648       ValueField = EnumRec->getValueAsString("ValueField");
649 
650     auto Enum = llvm::make_unique<GenericEnum>();
651     Enum->Name = EnumRec->getName();
652     Enum->PreprocessorGuard = EnumRec->getName();
653 
654     StringRef FilterClass = EnumRec->getValueAsString("FilterClass");
655     Enum->Class = Records.getClass(FilterClass);
656     if (!Enum->Class)
657       PrintFatalError(Twine("Enum FilterClass '") + FilterClass +
658                       "' does not exist");
659 
660     collectEnumEntries(*Enum, NameField, ValueField,
661                        Records.getAllDerivedDefinitions(FilterClass));
662     EnumMap.insert(std::make_pair(EnumRec, Enum.get()));
663     Enums.emplace_back(std::move(Enum));
664   }
665 
666   for (auto TableRec : Records.getAllDerivedDefinitions("GenericTable")) {
667     auto Table = llvm::make_unique<GenericTable>();
668     Table->Name = TableRec->getName();
669     Table->PreprocessorGuard = TableRec->getName();
670     Table->CppTypeName = TableRec->getValueAsString("CppTypeName");
671 
672     std::vector<StringRef> Fields = TableRec->getValueAsListOfStrings("Fields");
673     for (const auto &FieldName : Fields) {
674       Table->Fields.emplace_back(FieldName);
675 
676       if (auto TypeOfVal = TableRec->getValue(("TypeOf_" + FieldName).str())) {
677         if (!parseFieldType(Table->Fields.back(), TypeOfVal->getValue())) {
678           PrintFatalError(Twine("Table '") + Table->Name +
679                           "' has bad 'TypeOf_" + FieldName + "': " +
680                           TypeOfVal->getValue()->getAsString());
681         }
682       }
683     }
684 
685     collectTableEntries(*Table, Records.getAllDerivedDefinitions(
686                                     TableRec->getValueAsString("FilterClass")));
687 
688     if (!TableRec->isValueUnset("PrimaryKey")) {
689       Table->PrimaryKey =
690           parseSearchIndex(*Table, TableRec->getValueAsString("PrimaryKeyName"),
691                            TableRec->getValueAsListOfStrings("PrimaryKey"),
692                            TableRec->getValueAsBit("PrimaryKeyEarlyOut"));
693 
694       std::stable_sort(Table->Entries.begin(), Table->Entries.end(),
695                        [&](Record *LHS, Record *RHS) {
696                          return compareBy(LHS, RHS, *Table->PrimaryKey);
697                        });
698     }
699 
700     TableMap.insert(std::make_pair(TableRec, Table.get()));
701     Tables.emplace_back(std::move(Table));
702   }
703 
704   for (Record *IndexRec : Records.getAllDerivedDefinitions("SearchIndex")) {
705     Record *TableRec = IndexRec->getValueAsDef("Table");
706     auto It = TableMap.find(TableRec);
707     if (It == TableMap.end())
708       PrintFatalError(Twine("SearchIndex '") + IndexRec->getName() +
709                       "' refers to non-existing table '" + TableRec->getName());
710 
711     GenericTable &Table = *It->second;
712     Table.Indices.push_back(parseSearchIndex(
713         Table, IndexRec->getName(), IndexRec->getValueAsListOfStrings("Key"),
714         IndexRec->getValueAsBit("EarlyOut")));
715   }
716 
717   // Translate legacy tables.
718   Record *SearchableTable = Records.getClass("SearchableTable");
719   for (auto &NameRec : Records.getClasses()) {
720     Record *Class = NameRec.second.get();
721     if (Class->getSuperClasses().size() != 1 ||
722         !Class->isSubClassOf(SearchableTable))
723       continue;
724 
725     StringRef TableName = Class->getName();
726     std::vector<Record *> Items = Records.getAllDerivedDefinitions(TableName);
727     if (!Class->isValueUnset("EnumNameField")) {
728       StringRef NameField = Class->getValueAsString("EnumNameField");
729       StringRef ValueField;
730       if (!Class->isValueUnset("EnumValueField"))
731         ValueField = Class->getValueAsString("EnumValueField");
732 
733       auto Enum = llvm::make_unique<GenericEnum>();
734       Enum->Name = (Twine(Class->getName()) + "Values").str();
735       Enum->PreprocessorGuard = Class->getName().upper();
736       Enum->Class = Class;
737 
738       collectEnumEntries(*Enum, NameField, ValueField, Items);
739 
740       Enums.emplace_back(std::move(Enum));
741     }
742 
743     auto Table = llvm::make_unique<GenericTable>();
744     Table->Name = (Twine(Class->getName()) + "sList").str();
745     Table->PreprocessorGuard = Class->getName().upper();
746     Table->CppTypeName = Class->getName();
747 
748     for (const RecordVal &Field : Class->getValues()) {
749       std::string FieldName = Field.getName();
750 
751       // Skip uninteresting fields: either special to us, or injected
752       // template parameters (if they contain a ':').
753       if (FieldName.find(':') != std::string::npos ||
754           FieldName == "SearchableFields" || FieldName == "EnumNameField" ||
755           FieldName == "EnumValueField")
756         continue;
757 
758       Table->Fields.emplace_back(FieldName);
759     }
760 
761     collectTableEntries(*Table, Items);
762 
763     for (const auto &Field :
764          Class->getValueAsListOfStrings("SearchableFields")) {
765       std::string Name =
766           (Twine("lookup") + Table->CppTypeName + "By" + Field).str();
767       Table->Indices.push_back(parseSearchIndex(*Table, Name, {Field}, false));
768     }
769 
770     Tables.emplace_back(std::move(Table));
771   }
772 
773   // Emit everything.
774   for (const auto &Enum : Enums)
775     emitGenericEnum(*Enum, OS);
776 
777   for (const auto &Table : Tables)
778     emitGenericTable(*Table, OS);
779 
780   // Put all #undefs last, to allow multiple sections guarded by the same
781   // define.
782   for (const auto &Guard : PreprocessorGuards)
783     OS << "#undef " << Guard << "\n";
784 }
785 
786 namespace llvm {
787 
788 void EmitSearchableTables(RecordKeeper &RK, raw_ostream &OS) {
789   SearchableTableEmitter(RK).run(OS);
790 }
791 
792 } // End llvm namespace.
793