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