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