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