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