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