utils/TableGen/SearchableTableEmitter.cpp

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