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