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 
654 void SearchableTableEmitter::run(raw_ostream &OS) {
655   // Emit tables in a deterministic order to avoid needless rebuilds.
656   SmallVector<std::unique_ptr<GenericTable>, 4> Tables;
657   DenseMap<Record *, GenericTable *> TableMap;
658 
659   // Collect all definitions first.
660   for (auto EnumRec : Records.getAllDerivedDefinitions("GenericEnum")) {
661     StringRef NameField;
662     if (!EnumRec->isValueUnset("NameField"))
663       NameField = EnumRec->getValueAsString("NameField");
664 
665     StringRef ValueField;
666     if (!EnumRec->isValueUnset("ValueField"))
667       ValueField = EnumRec->getValueAsString("ValueField");
668 
669     auto Enum = std::make_unique<GenericEnum>();
670     Enum->Name = std::string(EnumRec->getName());
671     Enum->PreprocessorGuard = std::string(EnumRec->getName());
672 
673     StringRef FilterClass = EnumRec->getValueAsString("FilterClass");
674     Enum->Class = Records.getClass(FilterClass);
675     if (!Enum->Class)
676       PrintFatalError(EnumRec->getValue("FilterClass"),
677                       Twine("Enum FilterClass '") + FilterClass +
678                           "' does not exist");
679 
680     collectEnumEntries(*Enum, NameField, ValueField,
681                        Records.getAllDerivedDefinitions(FilterClass));
682     EnumMap.insert(std::make_pair(EnumRec, Enum.get()));
683     Enums.emplace_back(std::move(Enum));
684   }
685 
686   for (auto TableRec : Records.getAllDerivedDefinitions("GenericTable")) {
687     auto Table = std::make_unique<GenericTable>();
688     Table->Name = std::string(TableRec->getName());
689     Table->Locs = TableRec->getLoc();
690     Table->PreprocessorGuard = std::string(TableRec->getName());
691     Table->CppTypeName = std::string(TableRec->getValueAsString("CppTypeName"));
692 
693     std::vector<StringRef> Fields = TableRec->getValueAsListOfStrings("Fields");
694     for (const auto &FieldName : Fields) {
695       Table->Fields.emplace_back(FieldName); // Construct a GenericField.
696 
697       if (auto TypeOfRecordVal = TableRec->getValue(("TypeOf_" + FieldName).str())) {
698         if (!parseFieldType(Table->Fields.back(), TypeOfRecordVal->getValue())) {
699           PrintError(TypeOfRecordVal,
700                      Twine("Table '") + Table->Name +
701                          "' has invalid 'TypeOf_" + FieldName +
702                          "': " + TypeOfRecordVal->getValue()->getAsString());
703           PrintFatalNote("The 'TypeOf_xxx' field must be a string naming a "
704                          "GenericEnum record, or \"code\"");
705         }
706       }
707     }
708 
709     StringRef FilterClass = TableRec->getValueAsString("FilterClass");
710     if (!Records.getClass(FilterClass))
711       PrintFatalError(TableRec->getValue("FilterClass"),
712                       Twine("Table FilterClass '") +
713                           FilterClass + "' does not exist");
714 
715     collectTableEntries(*Table, Records.getAllDerivedDefinitions(FilterClass));
716 
717     if (!TableRec->isValueUnset("PrimaryKey")) {
718       Table->PrimaryKey =
719           parseSearchIndex(*Table, TableRec->getValue("PrimaryKey"),
720                            TableRec->getValueAsString("PrimaryKeyName"),
721                            TableRec->getValueAsListOfStrings("PrimaryKey"),
722                            TableRec->getValueAsBit("PrimaryKeyEarlyOut"));
723 
724       llvm::stable_sort(Table->Entries, [&](Record *LHS, Record *RHS) {
725         return compareBy(LHS, RHS, *Table->PrimaryKey);
726       });
727     }
728 
729     TableMap.insert(std::make_pair(TableRec, Table.get()));
730     Tables.emplace_back(std::move(Table));
731   }
732 
733   for (Record *IndexRec : Records.getAllDerivedDefinitions("SearchIndex")) {
734     Record *TableRec = IndexRec->getValueAsDef("Table");
735     auto It = TableMap.find(TableRec);
736     if (It == TableMap.end())
737       PrintFatalError(IndexRec->getValue("Table"),
738                       Twine("SearchIndex '") + IndexRec->getName() +
739                           "' refers to nonexistent table '" +
740                           TableRec->getName());
741 
742     GenericTable &Table = *It->second;
743     Table.Indices.push_back(
744         parseSearchIndex(Table, IndexRec->getValue("Key"), IndexRec->getName(),
745                          IndexRec->getValueAsListOfStrings("Key"),
746                          IndexRec->getValueAsBit("EarlyOut")));
747   }
748 
749   // Translate legacy tables.
750   Record *SearchableTable = Records.getClass("SearchableTable");
751   for (auto &NameRec : Records.getClasses()) {
752     Record *Class = NameRec.second.get();
753     if (Class->getSuperClasses().size() != 1 ||
754         !Class->isSubClassOf(SearchableTable))
755       continue;
756 
757     StringRef TableName = Class->getName();
758     std::vector<Record *> Items = Records.getAllDerivedDefinitions(TableName);
759     if (!Class->isValueUnset("EnumNameField")) {
760       StringRef NameField = Class->getValueAsString("EnumNameField");
761       StringRef ValueField;
762       if (!Class->isValueUnset("EnumValueField"))
763         ValueField = Class->getValueAsString("EnumValueField");
764 
765       auto Enum = std::make_unique<GenericEnum>();
766       Enum->Name = (Twine(Class->getName()) + "Values").str();
767       Enum->PreprocessorGuard = Class->getName().upper();
768       Enum->Class = Class;
769 
770       collectEnumEntries(*Enum, NameField, ValueField, Items);
771 
772       Enums.emplace_back(std::move(Enum));
773     }
774 
775     auto Table = std::make_unique<GenericTable>();
776     Table->Name = (Twine(Class->getName()) + "sList").str();
777     Table->Locs = Class->getLoc();
778     Table->PreprocessorGuard = Class->getName().upper();
779     Table->CppTypeName = std::string(Class->getName());
780 
781     for (const RecordVal &Field : Class->getValues()) {
782       std::string FieldName = std::string(Field.getName());
783 
784       // Skip uninteresting fields: either special to us, or injected
785       // template parameters (if they contain a ':').
786       if (FieldName.find(':') != std::string::npos ||
787           FieldName == "SearchableFields" || FieldName == "EnumNameField" ||
788           FieldName == "EnumValueField")
789         continue;
790 
791       Table->Fields.emplace_back(FieldName);
792     }
793 
794     collectTableEntries(*Table, Items);
795 
796     for (const auto &Field :
797          Class->getValueAsListOfStrings("SearchableFields")) {
798       std::string Name =
799           (Twine("lookup") + Table->CppTypeName + "By" + Field).str();
800       Table->Indices.push_back(parseSearchIndex(*Table, Class->getValue(Field),
801                                                 Name, {Field}, false));
802     }
803 
804     Tables.emplace_back(std::move(Table));
805   }
806 
807   // Emit everything.
808   for (const auto &Enum : Enums)
809     emitGenericEnum(*Enum, OS);
810 
811   for (const auto &Table : Tables)
812     emitGenericTable(*Table, OS);
813 
814   // Put all #undefs last, to allow multiple sections guarded by the same
815   // define.
816   for (const auto &Guard : PreprocessorGuards)
817     OS << "#undef " << Guard << "\n";
818 }
819 
820 namespace llvm {
821 
822 void EmitSearchableTables(RecordKeeper &RK, raw_ostream &OS) {
823   SearchableTableEmitter(RK).run(OS);
824 }
825 
826 } // End llvm namespace.
827