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