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