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