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