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) || isa<CodeInit>(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(EntryRec->getLoc(),
603                         Twine("Record '") + EntryRec->getName() +
604                             "' in table '" + Table.Name +
605                             "' is missing field '" + 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                           Field.RecType->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(EnumRec->getLoc(), Twine("Enum FilterClass '") +
658                                              FilterClass + "' 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(TableRec->getLoc(),
679                           Twine("Table '") + Table->Name +
680                               "' has bad 'TypeOf_" + FieldName +
681                               "': " + TypeOfVal->getValue()->getAsString());
682         }
683       }
684     }
685 
686     collectTableEntries(*Table, Records.getAllDerivedDefinitions(
687                                     TableRec->getValueAsString("FilterClass")));
688 
689     if (!TableRec->isValueUnset("PrimaryKey")) {
690       Table->PrimaryKey =
691           parseSearchIndex(*Table, TableRec->getValueAsString("PrimaryKeyName"),
692                            TableRec->getValueAsListOfStrings("PrimaryKey"),
693                            TableRec->getValueAsBit("PrimaryKeyEarlyOut"));
694 
695       std::stable_sort(Table->Entries.begin(), Table->Entries.end(),
696                        [&](Record *LHS, Record *RHS) {
697                          return compareBy(LHS, RHS, *Table->PrimaryKey);
698                        });
699     }
700 
701     TableMap.insert(std::make_pair(TableRec, Table.get()));
702     Tables.emplace_back(std::move(Table));
703   }
704 
705   for (Record *IndexRec : Records.getAllDerivedDefinitions("SearchIndex")) {
706     Record *TableRec = IndexRec->getValueAsDef("Table");
707     auto It = TableMap.find(TableRec);
708     if (It == TableMap.end())
709       PrintFatalError(IndexRec->getLoc(),
710                       Twine("SearchIndex '") + IndexRec->getName() +
711                           "' refers to non-existing table '" +
712                           TableRec->getName());
713 
714     GenericTable &Table = *It->second;
715     Table.Indices.push_back(parseSearchIndex(
716         Table, IndexRec->getName(), IndexRec->getValueAsListOfStrings("Key"),
717         IndexRec->getValueAsBit("EarlyOut")));
718   }
719 
720   // Translate legacy tables.
721   Record *SearchableTable = Records.getClass("SearchableTable");
722   for (auto &NameRec : Records.getClasses()) {
723     Record *Class = NameRec.second.get();
724     if (Class->getSuperClasses().size() != 1 ||
725         !Class->isSubClassOf(SearchableTable))
726       continue;
727 
728     StringRef TableName = Class->getName();
729     std::vector<Record *> Items = Records.getAllDerivedDefinitions(TableName);
730     if (!Class->isValueUnset("EnumNameField")) {
731       StringRef NameField = Class->getValueAsString("EnumNameField");
732       StringRef ValueField;
733       if (!Class->isValueUnset("EnumValueField"))
734         ValueField = Class->getValueAsString("EnumValueField");
735 
736       auto Enum = llvm::make_unique<GenericEnum>();
737       Enum->Name = (Twine(Class->getName()) + "Values").str();
738       Enum->PreprocessorGuard = Class->getName().upper();
739       Enum->Class = Class;
740 
741       collectEnumEntries(*Enum, NameField, ValueField, Items);
742 
743       Enums.emplace_back(std::move(Enum));
744     }
745 
746     auto Table = llvm::make_unique<GenericTable>();
747     Table->Name = (Twine(Class->getName()) + "sList").str();
748     Table->PreprocessorGuard = Class->getName().upper();
749     Table->CppTypeName = Class->getName();
750 
751     for (const RecordVal &Field : Class->getValues()) {
752       std::string FieldName = Field.getName();
753 
754       // Skip uninteresting fields: either special to us, or injected
755       // template parameters (if they contain a ':').
756       if (FieldName.find(':') != std::string::npos ||
757           FieldName == "SearchableFields" || FieldName == "EnumNameField" ||
758           FieldName == "EnumValueField")
759         continue;
760 
761       Table->Fields.emplace_back(FieldName);
762     }
763 
764     collectTableEntries(*Table, Items);
765 
766     for (const auto &Field :
767          Class->getValueAsListOfStrings("SearchableFields")) {
768       std::string Name =
769           (Twine("lookup") + Table->CppTypeName + "By" + Field).str();
770       Table->Indices.push_back(parseSearchIndex(*Table, Name, {Field}, false));
771     }
772 
773     Tables.emplace_back(std::move(Table));
774   }
775 
776   // Emit everything.
777   for (const auto &Enum : Enums)
778     emitGenericEnum(*Enum, OS);
779 
780   for (const auto &Table : Tables)
781     emitGenericTable(*Table, OS);
782 
783   // Put all #undefs last, to allow multiple sections guarded by the same
784   // define.
785   for (const auto &Guard : PreprocessorGuards)
786     OS << "#undef " << Guard << "\n";
787 }
788 
789 namespace llvm {
790 
791 void EmitSearchableTables(RecordKeeper &RK, raw_ostream &OS) {
792   SearchableTableEmitter(RK).run(OS);
793 }
794 
795 } // End llvm namespace.
796