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       bool NeedComma = false;
352       for (const auto &Field : Index.Fields) {
353         if (NeedComma)
354           OS << ", ";
355         NeedComma = true;
356 
357         std::string Repr = primaryRepresentation(
358             Index.Loc, Field, Entry.first->getValueInit(Field.Name));
359         if (isa<StringRecTy>(Field.RecType))
360           Repr = StringRef(Repr).upper();
361         OS << Repr;
362       }
363       OS << ", " << Entry.second << " },\n";
364     }
365 
366     OS << "  };\n\n";
367 
368     IndexTypeName = "IndexType";
369     IndexName = "Index";
370     IndexRows = IndexRowsStorage;
371   }
372 
373   bool IsContiguous = false;
374 
375   if (Index.Fields.size() == 1 &&
376       (Index.Fields[0].Enum || isa<BitsRecTy>(Index.Fields[0].RecType))) {
377     IsContiguous = true;
378     for (unsigned i = 0; i < IndexRows.size(); ++i) {
379       if (getNumericKey(Index, IndexRows[i]) != i) {
380         IsContiguous = false;
381         break;
382       }
383     }
384   }
385 
386   if (IsContiguous) {
387     OS << "  auto Table = makeArrayRef(" << IndexName << ");\n";
388     OS << "  size_t Idx = " << Index.Fields[0].Name << ";\n";
389     OS << "  return Idx >= Table.size() ? nullptr : ";
390     if (IsPrimary)
391       OS << "&Table[Idx]";
392     else
393       OS << "&" << Table.Name << "[Table[Idx]._index]";
394     OS << ";\n";
395     OS << "}\n";
396     return;
397   }
398 
399   if (Index.EarlyOut) {
400     const GenericField &Field = Index.Fields[0];
401     std::string FirstRepr = primaryRepresentation(
402         Index.Loc, Field, IndexRows[0]->getValueInit(Field.Name));
403     std::string LastRepr = primaryRepresentation(
404         Index.Loc, Field, IndexRows.back()->getValueInit(Field.Name));
405     OS << "  if ((" << Field.Name << " < " << FirstRepr << ") ||\n";
406     OS << "      (" << Field.Name << " > " << LastRepr << "))\n";
407     OS << "    return nullptr;\n\n";
408   }
409 
410   OS << "  struct KeyType {\n";
411   for (const auto &Field : Index.Fields) {
412     OS << "    " << searchableFieldType(Table, Index, Field, TypeInTempStruct)
413        << " " << Field.Name << ";\n";
414   }
415   OS << "  };\n";
416   OS << "  KeyType Key = {";
417   bool NeedComma = false;
418   for (const auto &Field : Index.Fields) {
419     if (NeedComma)
420       OS << ", ";
421     NeedComma = true;
422 
423     OS << Field.Name;
424     if (isa<StringRecTy>(Field.RecType)) {
425       OS << ".upper()";
426       if (IsPrimary)
427         PrintFatalError(Index.Loc,
428                         Twine("In table '") + Table.Name +
429                             "', use a secondary lookup method for "
430                             "case-insensitive comparison of field '" +
431                             Field.Name + "'");
432     }
433   }
434   OS << "};\n";
435 
436   OS << "  auto Table = makeArrayRef(" << IndexName << ");\n";
437   OS << "  auto Idx = std::lower_bound(Table.begin(), Table.end(), Key,\n";
438   OS << "    [](const " << IndexTypeName << " &LHS, const KeyType &RHS) {\n";
439 
440   for (const auto &Field : Index.Fields) {
441     if (isa<StringRecTy>(Field.RecType)) {
442       OS << "      int Cmp" << Field.Name << " = StringRef(LHS." << Field.Name
443          << ").compare(RHS." << Field.Name << ");\n";
444       OS << "      if (Cmp" << Field.Name << " < 0) return true;\n";
445       OS << "      if (Cmp" << Field.Name << " > 0) return false;\n";
446     } else if (Field.Enum) {
447       // Explicitly cast to unsigned, because the signedness of enums is
448       // compiler-dependent.
449       OS << "      if ((unsigned)LHS." << Field.Name << " < (unsigned)RHS."
450          << Field.Name << ")\n";
451       OS << "        return true;\n";
452       OS << "      if ((unsigned)LHS." << Field.Name << " > (unsigned)RHS."
453          << Field.Name << ")\n";
454       OS << "        return false;\n";
455     } else {
456       OS << "      if (LHS." << Field.Name << " < RHS." << Field.Name << ")\n";
457       OS << "        return true;\n";
458       OS << "      if (LHS." << Field.Name << " > RHS." << Field.Name << ")\n";
459       OS << "        return false;\n";
460     }
461   }
462 
463   OS << "      return false;\n";
464   OS << "    });\n\n";
465 
466   OS << "  if (Idx == Table.end()";
467 
468   for (const auto &Field : Index.Fields)
469     OS << " ||\n      Key." << Field.Name << " != Idx->" << Field.Name;
470   OS << ")\n    return nullptr;\n";
471 
472   if (IsPrimary)
473     OS << "  return &*Idx;\n";
474   else
475     OS << "  return &" << Table.Name << "[Idx->_index];\n";
476 
477   OS << "}\n";
478 }
479 
480 void SearchableTableEmitter::emitLookupDeclaration(const GenericTable &Table,
481                                                    const SearchIndex &Index,
482                                                    raw_ostream &OS) {
483   OS << "const " << Table.CppTypeName << " *" << Index.Name << "(";
484 
485   bool NeedComma = false;
486   for (const auto &Field : Index.Fields) {
487     if (NeedComma)
488       OS << ", ";
489     NeedComma = true;
490 
491     OS << searchableFieldType(Table, Index, Field, TypeInArgument) << " "
492        << Field.Name;
493   }
494   OS << ")";
495 }
496 
497 void SearchableTableEmitter::emitGenericTable(const GenericTable &Table,
498                                               raw_ostream &OS) {
499   emitIfdef((Twine("GET_") + Table.PreprocessorGuard + "_DECL").str(), OS);
500 
501   // Emit the declarations for the functions that will perform lookup.
502   if (Table.PrimaryKey) {
503     emitLookupDeclaration(Table, *Table.PrimaryKey, OS);
504     OS << ";\n";
505   }
506   for (const auto &Index : Table.Indices) {
507     emitLookupDeclaration(Table, *Index, OS);
508     OS << ";\n";
509   }
510 
511   OS << "#endif\n\n";
512 
513   emitIfdef((Twine("GET_") + Table.PreprocessorGuard + "_IMPL").str(), OS);
514 
515   // The primary data table contains all the fields defined for this map.
516   OS << "constexpr " << Table.CppTypeName << " " << Table.Name << "[] = {\n";
517   for (unsigned i = 0; i < Table.Entries.size(); ++i) {
518     Record *Entry = Table.Entries[i];
519     OS << "  { ";
520 
521     bool NeedComma = false;
522     for (const auto &Field : Table.Fields) {
523       if (NeedComma)
524         OS << ", ";
525       NeedComma = true;
526 
527       OS << primaryRepresentation(Table.Locs[0], Field,
528                                   Entry->getValueInit(Field.Name));
529     }
530 
531     OS << " }, // " << i << "\n";
532   }
533   OS << " };\n";
534 
535   // Indexes are sorted "{ Thing, PrimaryIdx }" arrays, so that a binary
536   // search can be performed by "Thing".
537   if (Table.PrimaryKey)
538     emitLookupFunction(Table, *Table.PrimaryKey, true, OS);
539   for (const auto &Index : Table.Indices)
540     emitLookupFunction(Table, *Index, false, OS);
541 
542   OS << "#endif\n\n";
543 }
544 
545 bool SearchableTableEmitter::parseFieldType(GenericField &Field, Init *TypeOf) {
546   if (auto Type = dyn_cast<StringInit>(TypeOf)) {
547     if (Type->getValue() == "code") {
548       Field.IsCode = true;
549       return true;
550     } else {
551       if (Record *TypeRec = Records.getDef(Type->getValue())) {
552         if (TypeRec->isSubClassOf("GenericEnum")) {
553           Field.Enum = EnumMap[TypeRec];
554           Field.RecType = RecordRecTy::get(Field.Enum->Class);
555           return true;
556         }
557       }
558     }
559   }
560 
561   return false;
562 }
563 
564 std::unique_ptr<SearchIndex> SearchableTableEmitter::parseSearchIndex(
565     GenericTable &Table, const RecordVal *KeyRecVal, StringRef Name,
566     const std::vector<StringRef> &Key, bool EarlyOut) {
567   auto Index = std::make_unique<SearchIndex>();
568   Index->Name = std::string(Name);
569   Index->Loc = KeyRecVal->getLoc();
570   Index->EarlyOut = EarlyOut;
571 
572   for (const auto &FieldName : Key) {
573     const GenericField *Field = Table.getFieldByName(FieldName);
574     if (!Field)
575       PrintFatalError(
576           KeyRecVal,
577           Twine("In table '") + Table.Name +
578               "', 'PrimaryKey' or 'Key' refers to nonexistent field '" +
579               FieldName + "'");
580 
581     Index->Fields.push_back(*Field);
582   }
583 
584   if (EarlyOut && isa<StringRecTy>(Index->Fields[0].RecType)) {
585     PrintFatalError(
586         KeyRecVal, Twine("In lookup method '") + Name + "', early-out is not " +
587                        "supported for a first key field of type string");
588   }
589 
590   return Index;
591 }
592 
593 void SearchableTableEmitter::collectEnumEntries(
594     GenericEnum &Enum, StringRef NameField, StringRef ValueField,
595     const std::vector<Record *> &Items) {
596   for (auto EntryRec : Items) {
597     StringRef Name;
598     if (NameField.empty())
599       Name = EntryRec->getName();
600     else
601       Name = EntryRec->getValueAsString(NameField);
602 
603     int64_t Value = 0;
604     if (!ValueField.empty())
605       Value = getInt(EntryRec, ValueField);
606 
607     Enum.Entries.push_back(std::make_unique<GenericEnum::Entry>(Name, Value));
608     Enum.EntryMap.insert(std::make_pair(EntryRec, Enum.Entries.back().get()));
609   }
610 
611   if (ValueField.empty()) {
612     llvm::stable_sort(Enum.Entries,
613                       [](const std::unique_ptr<GenericEnum::Entry> &LHS,
614                          const std::unique_ptr<GenericEnum::Entry> &RHS) {
615                         return LHS->first < RHS->first;
616                       });
617 
618     for (size_t i = 0; i < Enum.Entries.size(); ++i)
619       Enum.Entries[i]->second = i;
620   }
621 }
622 
623 void SearchableTableEmitter::collectTableEntries(
624     GenericTable &Table, const std::vector<Record *> &Items) {
625   if (Items.empty())
626     PrintFatalError(Table.Locs,
627                     Twine("Table '") + Table.Name + "' has no entries");
628 
629   for (auto EntryRec : Items) {
630     for (auto &Field : Table.Fields) {
631       auto TI = dyn_cast<TypedInit>(EntryRec->getValueInit(Field.Name));
632       if (!TI || !TI->isComplete()) {
633         PrintFatalError(EntryRec, Twine("Record '") + EntryRec->getName() +
634                                       "' for table '" + Table.Name +
635                                       "' is missing field '" + Field.Name +
636                                       "'");
637       }
638       if (!Field.RecType) {
639         Field.RecType = TI->getType();
640       } else {
641         RecTy *Ty = resolveTypes(Field.RecType, TI->getType());
642         if (!Ty)
643           PrintFatalError(EntryRec->getValue(Field.Name),
644                           Twine("Field '") + Field.Name + "' of table '" +
645                           Table.Name + "' entry has incompatible type: " +
646                           TI->getType()->getAsString() + " vs. " +
647                           Field.RecType->getAsString());
648         Field.RecType = Ty;
649       }
650     }
651 
652     Table.Entries.push_back(EntryRec); // Add record to table's record list.
653   }
654 
655   Record *IntrinsicClass = Records.getClass("Intrinsic");
656   Record *InstructionClass = Records.getClass("Instruction");
657   for (auto &Field : Table.Fields) {
658     if (!Field.RecType)
659       PrintFatalError(Twine("Cannot determine type of field '") + Field.Name +
660                       "' in table '" + Table.Name + "'. Maybe it is not used?");
661 
662     if (auto RecordTy = dyn_cast<RecordRecTy>(Field.RecType)) {
663       if (IntrinsicClass && RecordTy->isSubClassOf(IntrinsicClass))
664         Field.IsIntrinsic = true;
665       else if (InstructionClass && RecordTy->isSubClassOf(InstructionClass))
666         Field.IsInstruction = true;
667     }
668   }
669 }
670 
671 void SearchableTableEmitter::run(raw_ostream &OS) {
672   // Emit tables in a deterministic order to avoid needless rebuilds.
673   SmallVector<std::unique_ptr<GenericTable>, 4> Tables;
674   DenseMap<Record *, GenericTable *> TableMap;
675 
676   // Collect all definitions first.
677   for (auto EnumRec : Records.getAllDerivedDefinitions("GenericEnum")) {
678     StringRef NameField;
679     if (!EnumRec->isValueUnset("NameField"))
680       NameField = EnumRec->getValueAsString("NameField");
681 
682     StringRef ValueField;
683     if (!EnumRec->isValueUnset("ValueField"))
684       ValueField = EnumRec->getValueAsString("ValueField");
685 
686     auto Enum = std::make_unique<GenericEnum>();
687     Enum->Name = std::string(EnumRec->getName());
688     Enum->PreprocessorGuard = std::string(EnumRec->getName());
689 
690     StringRef FilterClass = EnumRec->getValueAsString("FilterClass");
691     Enum->Class = Records.getClass(FilterClass);
692     if (!Enum->Class)
693       PrintFatalError(EnumRec->getValue("FilterClass"),
694                       Twine("Enum FilterClass '") + FilterClass +
695                           "' does not exist");
696 
697     collectEnumEntries(*Enum, NameField, ValueField,
698                        Records.getAllDerivedDefinitions(FilterClass));
699     EnumMap.insert(std::make_pair(EnumRec, Enum.get()));
700     Enums.emplace_back(std::move(Enum));
701   }
702 
703   for (auto TableRec : Records.getAllDerivedDefinitions("GenericTable")) {
704     auto Table = std::make_unique<GenericTable>();
705     Table->Name = std::string(TableRec->getName());
706     Table->Locs = TableRec->getLoc();
707     Table->PreprocessorGuard = std::string(TableRec->getName());
708     Table->CppTypeName = std::string(TableRec->getValueAsString("CppTypeName"));
709 
710     std::vector<StringRef> Fields = TableRec->getValueAsListOfStrings("Fields");
711     for (const auto &FieldName : Fields) {
712       Table->Fields.emplace_back(FieldName); // Construct a GenericField.
713 
714       if (auto TypeOfRecordVal = TableRec->getValue(("TypeOf_" + FieldName).str())) {
715         if (!parseFieldType(Table->Fields.back(), TypeOfRecordVal->getValue())) {
716           PrintError(TypeOfRecordVal,
717                      Twine("Table '") + Table->Name +
718                          "' has invalid 'TypeOf_" + FieldName +
719                          "': " + TypeOfRecordVal->getValue()->getAsString());
720           PrintFatalNote("The 'TypeOf_xxx' field must be a string naming a "
721                          "GenericEnum record, or \"code\"");
722         }
723       }
724     }
725 
726     StringRef FilterClass = TableRec->getValueAsString("FilterClass");
727     if (!Records.getClass(FilterClass))
728       PrintFatalError(TableRec->getValue("FilterClass"),
729                       Twine("Table FilterClass '") +
730                           FilterClass + "' does not exist");
731 
732     collectTableEntries(*Table, Records.getAllDerivedDefinitions(FilterClass));
733 
734     if (!TableRec->isValueUnset("PrimaryKey")) {
735       Table->PrimaryKey =
736           parseSearchIndex(*Table, TableRec->getValue("PrimaryKey"),
737                            TableRec->getValueAsString("PrimaryKeyName"),
738                            TableRec->getValueAsListOfStrings("PrimaryKey"),
739                            TableRec->getValueAsBit("PrimaryKeyEarlyOut"));
740 
741       llvm::stable_sort(Table->Entries, [&](Record *LHS, Record *RHS) {
742         return compareBy(LHS, RHS, *Table->PrimaryKey);
743       });
744     }
745 
746     TableMap.insert(std::make_pair(TableRec, Table.get()));
747     Tables.emplace_back(std::move(Table));
748   }
749 
750   for (Record *IndexRec : Records.getAllDerivedDefinitions("SearchIndex")) {
751     Record *TableRec = IndexRec->getValueAsDef("Table");
752     auto It = TableMap.find(TableRec);
753     if (It == TableMap.end())
754       PrintFatalError(IndexRec->getValue("Table"),
755                       Twine("SearchIndex '") + IndexRec->getName() +
756                           "' refers to nonexistent table '" +
757                           TableRec->getName());
758 
759     GenericTable &Table = *It->second;
760     Table.Indices.push_back(
761         parseSearchIndex(Table, IndexRec->getValue("Key"), IndexRec->getName(),
762                          IndexRec->getValueAsListOfStrings("Key"),
763                          IndexRec->getValueAsBit("EarlyOut")));
764   }
765 
766   // Translate legacy tables.
767   Record *SearchableTable = Records.getClass("SearchableTable");
768   for (auto &NameRec : Records.getClasses()) {
769     Record *Class = NameRec.second.get();
770     if (Class->getSuperClasses().size() != 1 ||
771         !Class->isSubClassOf(SearchableTable))
772       continue;
773 
774     StringRef TableName = Class->getName();
775     std::vector<Record *> Items = Records.getAllDerivedDefinitions(TableName);
776     if (!Class->isValueUnset("EnumNameField")) {
777       StringRef NameField = Class->getValueAsString("EnumNameField");
778       StringRef ValueField;
779       if (!Class->isValueUnset("EnumValueField"))
780         ValueField = Class->getValueAsString("EnumValueField");
781 
782       auto Enum = std::make_unique<GenericEnum>();
783       Enum->Name = (Twine(Class->getName()) + "Values").str();
784       Enum->PreprocessorGuard = Class->getName().upper();
785       Enum->Class = Class;
786 
787       collectEnumEntries(*Enum, NameField, ValueField, Items);
788 
789       Enums.emplace_back(std::move(Enum));
790     }
791 
792     auto Table = std::make_unique<GenericTable>();
793     Table->Name = (Twine(Class->getName()) + "sList").str();
794     Table->Locs = Class->getLoc();
795     Table->PreprocessorGuard = Class->getName().upper();
796     Table->CppTypeName = std::string(Class->getName());
797 
798     for (const RecordVal &Field : Class->getValues()) {
799       std::string FieldName = std::string(Field.getName());
800 
801       // Skip uninteresting fields: either special to us, or injected
802       // template parameters (if they contain a ':').
803       if (FieldName.find(':') != std::string::npos ||
804           FieldName == "SearchableFields" || FieldName == "EnumNameField" ||
805           FieldName == "EnumValueField")
806         continue;
807 
808       Table->Fields.emplace_back(FieldName);
809     }
810 
811     collectTableEntries(*Table, Items);
812 
813     for (const auto &Field :
814          Class->getValueAsListOfStrings("SearchableFields")) {
815       std::string Name =
816           (Twine("lookup") + Table->CppTypeName + "By" + Field).str();
817       Table->Indices.push_back(parseSearchIndex(*Table, Class->getValue(Field),
818                                                 Name, {Field}, false));
819     }
820 
821     Tables.emplace_back(std::move(Table));
822   }
823 
824   // Emit everything.
825   for (const auto &Enum : Enums)
826     emitGenericEnum(*Enum, OS);
827 
828   for (const auto &Table : Tables)
829     emitGenericTable(*Table, OS);
830 
831   // Put all #undefs last, to allow multiple sections guarded by the same
832   // define.
833   for (const auto &Guard : PreprocessorGuards)
834     OS << "#undef " << Guard << "\n";
835 }
836 
837 namespace llvm {
838 
839 void EmitSearchableTables(RecordKeeper &RK, raw_ostream &OS) {
840   SearchableTableEmitter(RK).run(OS);
841 }
842 
843 } // End llvm namespace.
844