TableGen/SearchableTables: Support more generic enums and tables

Summary:
This is essentially a rewrite of the backend which introduces TableGen
base classes GenericEnum, GenericTable, and SearchIndex. They allow
generating custom enums and tables with lookup functions using
separately defined records as the underlying database.

Also added as part of this change:

- Lookup functions may use indices composed of multiple fields.

- Instruction fields are supported similar to Intrinsic fields.

- When the lookup key has contiguous numeric values, the lookup
  function will directly index into the table instead of using a binary
  search.

The existing SearchableTable functionality is internally mapped to the
new primitives.

Change-Id: I444f3490fa1dbfb262d7286a1660a2c4308e9932

Reviewers: arsenm, tra, t.p.northover

Subscribers: wdng, llvm-commits

Differential Revision: https://reviews.llvm.org/D48013

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@335225 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 634 insertions, 201 deletions

diff --git a/utils/TableGen/SearchableTableEmitter.cpp b/utils/TableGen/SearchableTableEmitter.cpp
index 4c127a0c6f9..664de2217e9 100644
--- a/utils/TableGen/SearchableTableEmitter.cpp
+++ b/utils/TableGen/SearchableTableEmitter.cpp
@@ -22,17 +22,76 @@
 #include "llvm/TableGen/Record.h"
 #include "CodeGenIntrinsics.h"
 #include <algorithm>
+#include <set>
 #include <string>
 #include <vector>
+
 using namespace llvm;
 
 #define DEBUG_TYPE "searchable-table-emitter"
 
 namespace {
 
+struct GenericTable;
+
+int getAsInt(Init *B) {
+  return cast<IntInit>(B->convertInitializerTo(IntRecTy::get()))->getValue();
+}
+int getInt(Record *R, StringRef Field) {
+  return getAsInt(R->getValueInit(Field));
+}
+
+struct GenericEnum {
+  using Entry = std::pair<StringRef, int64_t>;
+
+  std::string Name;
+  Record *Class;
+  std::string PreprocessorGuard;
+  std::vector<std::unique_ptr<Entry>> Entries;
+  DenseMap<Record *, Entry *> EntryMap;
+};
+
+struct GenericField {
+  std::string Name;
+  RecTy *RecType = nullptr;
+  bool IsIntrinsic = false;
+  bool IsInstruction = false;
+  GenericEnum *Enum = nullptr;
+
+  GenericField(StringRef Name) : Name(Name) {}
+};
+
+struct SearchIndex {
+  std::string Name;
+  SmallVector<GenericField, 1> Fields;
+  bool EarlyOut;
+};
+
+struct GenericTable {
+  std::string Name;
+  std::string PreprocessorGuard;
+  std::string CppTypeName;
+  SmallVector<GenericField, 2> Fields;
+  std::vector<Record *> Entries;
+
+  std::unique_ptr<SearchIndex> PrimaryKey;
+  SmallVector<std::unique_ptr<SearchIndex>, 2> Indices;
+
+  const GenericField *getFieldByName(StringRef Name) const {
+    for (const auto &Field : Fields) {
+      if (Name == Field.Name)
+        return &Field;
+    }
+    return nullptr;
+  }
+};
+
 class SearchableTableEmitter {
   RecordKeeper &Records;
   DenseMap<Init *, std::unique_ptr<CodeGenIntrinsic>> Intrinsics;
+  std::vector<std::unique_ptr<GenericEnum>> Enums;
+  DenseMap<Record *, GenericEnum *> EnumMap;
+  std::set<std::string> PreprocessorGuards;
 
 public:
   SearchableTableEmitter(RecordKeeper &R) : Records(R) {}
@@ -42,14 +101,13 @@ public:
 private:
   typedef std::pair<Init *, int> SearchTableEntry;
 
-  int getAsInt(BitsInit *B) {
-    return cast<IntInit>(B->convertInitializerTo(IntRecTy::get()))->getValue();
-  }
-  int getInt(Record *R, StringRef Field) {
-    return getAsInt(R->getValueAsBitsInit(Field));
-  }
+  enum TypeContext {
+    TypeInStaticStruct,
+    TypeInTempStruct,
+    TypeInArgument,
+  };
 
-  std::string primaryRepresentation(Init *I) {
+  std::string primaryRepresentation(const GenericField &Field, Init *I) {
     if (StringInit *SI = dyn_cast<StringInit>(I))
       return SI->getAsString();
     else if (BitsInit *BI = dyn_cast<BitsInit>(I))
@@ -58,19 +116,14 @@ private:
       return BI->getValue() ? "true" : "false";
     else if (CodeInit *CI = dyn_cast<CodeInit>(I))
       return CI->getValue();
-    else if (DefInit *DI = dyn_cast<DefInit>(I)) {
-      if (DI->getDef()->isSubClassOf("Intrinsic"))
-        return "Intrinsic::" + getIntrinsic(I).EnumName;
-    }
-    PrintFatalError(SMLoc(),
-                    "invalid field type, expected: string, bits, bit or code");
-  }
-
-  std::string searchRepresentation(Init *I) {
-    std::string PrimaryRep = primaryRepresentation(I);
-    if (!isa<StringInit>(I))
-      return PrimaryRep;
-    return StringRef(PrimaryRep).upper();
+    else if (Field.IsIntrinsic)
+      return "Intrinsic::" + getIntrinsic(I).EnumName;
+    else if (Field.IsInstruction)
+      return I->getAsString();
+    else if (Field.Enum)
+      return Field.Enum->EntryMap[cast<DefInit>(I)->getDef()]->first;
+    PrintFatalError(Twine("invalid field type for field '") + Field.Name +
+                    "', expected: string, bits, bit or code");
   }
 
   bool isIntrinsic(Init *I) {
@@ -86,14 +139,20 @@ private:
     return *Intr;
   }
 
+  bool compareBy(Record *LHS, Record *RHS, const SearchIndex &Index);
+
   bool isIntegral(Init *I) {
     return isa<BitsInit>(I) || isIntrinsic(I);
   }
 
-  std::string searchableFieldType(Init *I) {
-    if (isa<StringInit>(I))
-      return "const char *";
-    else if (BitsInit *BI = dyn_cast<BitsInit>(I)) {
+  std::string searchableFieldType(const GenericField &Field, TypeContext Ctx) {
+    if (isa<StringRecTy>(Field.RecType)) {
+      if (Ctx == TypeInStaticStruct)
+        return "const char *";
+      if (Ctx == TypeInTempStruct)
+        return "std::string";
+      return "StringRef";
+    } else if (BitsRecTy *BI = dyn_cast<BitsRecTy>(Field.RecType)) {
       unsigned NumBits = BI->getNumBits();
       if (NumBits <= 8)
         NumBits = 8;
@@ -104,243 +163,617 @@ private:
       else if (NumBits <= 64)
         NumBits = 64;
       else
-        PrintFatalError(SMLoc(), "bitfield too large to search");
+        PrintFatalError(Twine("bitfield '") + Field.Name +
+                        "' too large to search");
       return "uint" + utostr(NumBits) + "_t";
-    } else if (isIntrinsic(I))
+    } else if (Field.Enum || Field.IsIntrinsic || Field.IsInstruction)
       return "unsigned";
-    PrintFatalError(SMLoc(), "Unknown type to search by");
+    PrintFatalError(Twine("Field '") + Field.Name + "' has unknown type '" +
+                    Field.RecType->getAsString() + "' to search by");
   }
 
-  void emitMapping(Record *MappingDesc, raw_ostream &OS);
-  void emitMappingEnum(std::vector<Record *> &Items, Record *InstanceClass,
-                       raw_ostream &OS);
-  void
-  emitPrimaryTable(StringRef Name, std::vector<std::string> &FieldNames,
-                   std::vector<std::string> &SearchFieldNames,
-                   std::vector<std::vector<SearchTableEntry>> &SearchTables,
-                   std::vector<Record *> &Items, raw_ostream &OS);
-  void emitSearchTable(StringRef Name, StringRef Field,
-                       std::vector<SearchTableEntry> &SearchTable,
-                       raw_ostream &OS);
-  void emitLookupDeclaration(StringRef Name, StringRef Field, Init *I,
-                             raw_ostream &OS);
-  void emitLookupFunction(StringRef Name, StringRef Field, Init *I,
-                          raw_ostream &OS);
+  void emitGenericTable(const GenericTable &Table, raw_ostream &OS);
+  void emitGenericEnum(const GenericEnum &Enum, raw_ostream &OS);
+  void emitLookupDeclaration(const GenericTable &Table,
+                             const SearchIndex &Index, raw_ostream &OS);
+  void emitLookupFunction(const GenericTable &Table, const SearchIndex &Index,
+                          bool IsPrimary, raw_ostream &OS);
+  void emitIfdef(StringRef Guard, raw_ostream &OS);
+
+  bool parseFieldType(GenericField &Field, Init *II);
+  std::unique_ptr<SearchIndex>
+  parseSearchIndex(GenericTable &Table, StringRef Name,
+                   const std::vector<StringRef> &Key, bool EarlyOut);
+  void collectEnumEntries(GenericEnum &Enum, StringRef NameField,
+                          StringRef ValueField,
+                          const std::vector<Record *> &Items);
+  void collectTableEntries(GenericTable &Table,
+                           const std::vector<Record *> &Items);
 };
 
 } // End anonymous namespace.
 
-/// Emit an enum providing symbolic access to some preferred field from
-/// C++.
-void SearchableTableEmitter::emitMappingEnum(std::vector<Record *> &Items,
-                                             Record *InstanceClass,
-                                             raw_ostream &OS) {
-  StringRef EnumNameField = InstanceClass->getValueAsString("EnumNameField");
-  StringRef EnumValueField;
-  if (!InstanceClass->isValueUnset("EnumValueField"))
-    EnumValueField = InstanceClass->getValueAsString("EnumValueField");
-
-  OS << "enum " << InstanceClass->getName() << "Values {\n";
-  for (auto Item : Items) {
-    OS << "  " << Item->getValueAsString(EnumNameField);
-    if (EnumValueField != StringRef())
-      OS << " = " << getInt(Item, EnumValueField);
-    OS << ",\n";
+// For search indices that consists of a single field whose numeric value is
+// known, return that numeric value.
+static int64_t getNumericKey(const SearchIndex &Index, Record *Rec) {
+  assert(Index.Fields.size() == 1);
+
+  if (Index.Fields[0].Enum) {
+    Record *EnumEntry = Rec->getValueAsDef(Index.Fields[0].Name);
+    return Index.Fields[0].Enum->EntryMap[EnumEntry]->second;
   }
-  OS << "};\n\n";
-}
 
-void SearchableTableEmitter::emitPrimaryTable(
-    StringRef Name, std::vector<std::string> &FieldNames,
-    std::vector<std::string> &SearchFieldNames,
-    std::vector<std::vector<SearchTableEntry>> &SearchTables,
-    std::vector<Record *> &Items, raw_ostream &OS) {
-  OS << "const " << Name << " " << Name << "sList[] = {\n";
+  return getInt(Rec, Index.Fields[0].Name);
+}
 
-  for (auto Item : Items) {
-    OS << "  { ";
-    for (unsigned i = 0; i < FieldNames.size(); ++i) {
-      OS << primaryRepresentation(Item->getValueInit(FieldNames[i]));
-      if (i != FieldNames.size() - 1)
-        OS << ", ";
+/// Less-than style comparison between \p LHS and \p RHS according to the
+/// key of \p Index.
+bool SearchableTableEmitter::compareBy(Record *LHS, Record *RHS,
+                                       const SearchIndex &Index) {
+  for (const auto &Field : Index.Fields) {
+    Init *LHSI = LHS->getValueInit(Field.Name);
+    Init *RHSI = RHS->getValueInit(Field.Name);
+
+    if (isa<BitsRecTy>(Field.RecType) || isa<IntRecTy>(Field.RecType)) {
+      int64_t LHSi = getAsInt(LHSI);
+      int64_t RHSi = getAsInt(RHSI);
+      if (LHSi < RHSi)
+        return true;
+      if (LHSi > RHSi)
+        return false;
+    } else if (Field.IsIntrinsic) {
+      CodeGenIntrinsic &LHSi = getIntrinsic(LHSI);
+      CodeGenIntrinsic &RHSi = getIntrinsic(RHSI);
+      if (std::tie(LHSi.TargetPrefix, LHSi.Name) <
+          std::tie(RHSi.TargetPrefix, RHSi.Name))
+        return true;
+      if (std::tie(LHSi.TargetPrefix, LHSi.Name) >
+          std::tie(RHSi.TargetPrefix, RHSi.Name))
+        return false;
+    } else if (Field.IsInstruction) {
+      // This does not correctly compare the predefined instructions!
+      Record *LHSr = cast<DefInit>(LHSI)->getDef();
+      Record *RHSr = cast<DefInit>(RHSI)->getDef();
+
+      bool LHSpseudo = LHSr->getValueAsBit("isPseudo");
+      bool RHSpseudo = RHSr->getValueAsBit("isPseudo");
+      if (LHSpseudo && !RHSpseudo)
+        return true;
+      if (!LHSpseudo && RHSpseudo)
+        return false;
+
+      int comp = LHSr->getName().compare(RHSr->getName());
+      if (comp < 0)
+        return true;
+      if (comp > 0)
+        return false;
+    } else if (Field.Enum) {
+      auto LHSr = cast<DefInit>(LHSI)->getDef();
+      auto RHSr = cast<DefInit>(RHSI)->getDef();
+      int64_t LHSv = Field.Enum->EntryMap[LHSr]->second;
+      int64_t RHSv = Field.Enum->EntryMap[RHSr]->second;
+      if (LHSv < RHSv)
+        return true;
+      if (LHSv > RHSv)
+        return false;
+    } else {
+      std::string LHSs = primaryRepresentation(Field, LHSI);
+      std::string RHSs = primaryRepresentation(Field, RHSI);
+
+      if (isa<StringRecTy>(Field.RecType)) {
+        LHSs = StringRef(LHSs).upper();
+        RHSs = StringRef(RHSs).upper();
+      }
+
+      int comp = LHSs.compare(RHSs);
+      if (comp < 0)
+        return true;
+      if (comp > 0)
+        return false;
     }
-    OS << "},\n";
   }
-  OS << "};\n\n";
+  return false;
 }
 
-void SearchableTableEmitter::emitSearchTable(
-    StringRef Name, StringRef Field, std::vector<SearchTableEntry> &SearchTable,
-    raw_ostream &OS) {
-  OS << "const std::pair<" << searchableFieldType(SearchTable[0].first)
-     << ", int> " << Name << "sBy" << Field << "[] = {\n";
-
-  if (isa<BitsInit>(SearchTable[0].first)) {
-    std::stable_sort(SearchTable.begin(), SearchTable.end(),
-                     [this](const SearchTableEntry &LHS,
-                            const SearchTableEntry &RHS) {
-                       return getAsInt(cast<BitsInit>(LHS.first)) <
-                              getAsInt(cast<BitsInit>(RHS.first));
-                     });
-  } else if (isIntrinsic(SearchTable[0].first)) {
-    std::stable_sort(SearchTable.begin(), SearchTable.end(),
-                     [this](const SearchTableEntry &LHS,
-                            const SearchTableEntry &RHS) {
-                       CodeGenIntrinsic &LHSi = getIntrinsic(LHS.first);
-                       CodeGenIntrinsic &RHSi = getIntrinsic(RHS.first);
-                       return std::tie(LHSi.TargetPrefix, LHSi.Name) <
-                              std::tie(RHSi.TargetPrefix, RHSi.Name);
-                     });
+void SearchableTableEmitter::emitIfdef(StringRef Guard, raw_ostream &OS) {
+  OS << "#ifdef " << Guard << "\n";
+  PreprocessorGuards.insert(Guard);
+}
+
+/// Emit a generic enum.
+void SearchableTableEmitter::emitGenericEnum(const GenericEnum &Enum,
+                                             raw_ostream &OS) {
+  emitIfdef((Twine("GET_") + Enum.PreprocessorGuard + "_DECL").str(), OS);
+
+  OS << "enum " << Enum.Name << " {\n";
+  for (const auto &Entry : Enum.Entries)
+    OS << "  " << Entry->first << " = " << Entry->second << ",\n";
+  OS << "};\n";
+
+  OS << "#endif\n\n";
+}
+
+void SearchableTableEmitter::emitLookupFunction(const GenericTable &Table,
+                                                const SearchIndex &Index,
+                                                bool IsPrimary,
+                                                raw_ostream &OS) {
+  OS << "\n";
+  emitLookupDeclaration(Table, Index, OS);
+  OS << " {\n";
+
+  std::vector<Record *> IndexRowsStorage;
+  ArrayRef<Record *> IndexRows;
+  StringRef IndexTypeName;
+  StringRef IndexName;
+
+  if (IsPrimary) {
+    IndexTypeName = Table.CppTypeName;
+    IndexName = Table.Name;
+    IndexRows = Table.Entries;
   } else {
-    std::stable_sort(SearchTable.begin(), SearchTable.end(),
-                     [this](const SearchTableEntry &LHS,
-                            const SearchTableEntry &RHS) {
-                       return searchRepresentation(LHS.first) <
-                              searchRepresentation(RHS.first);
+    OS << "  struct IndexType {\n";
+    for (const auto &Field : Index.Fields) {
+      OS << "    " << searchableFieldType(Field, TypeInStaticStruct) << " "
+         << Field.Name << ";\n";
+    }
+    OS << "    unsigned _index;\n";
+    OS << "  };\n";
+
+    OS << "  static const struct IndexType Index[] = {\n";
+
+    std::vector<std::pair<Record *, unsigned>> Entries;
+    Entries.reserve(Table.Entries.size());
+    for (unsigned i = 0; i < Table.Entries.size(); ++i)
+      Entries.emplace_back(Table.Entries[i], i);
+
+    std::stable_sort(Entries.begin(), Entries.end(),
+                     [&](const std::pair<Record *, unsigned> &LHS,
+                         const std::pair<Record *, unsigned> &RHS) {
+                       return compareBy(LHS.first, RHS.first, Index);
                      });
+
+    IndexRowsStorage.reserve(Entries.size());
+    for (const auto &Entry : Entries) {
+      IndexRowsStorage.push_back(Entry.first);
+
+      OS << "    { ";
+      bool NeedComma = false;
+      for (const auto &Field : Index.Fields) {
+        if (NeedComma)
+          OS << ", ";
+        NeedComma = true;
+
+        std::string Repr =
+            primaryRepresentation(Field, Entry.first->getValueInit(Field.Name));
+        if (isa<StringRecTy>(Field.RecType))
+          Repr = StringRef(Repr).upper();
+        OS << Repr;
+      }
+      OS << ", " << Entry.second << " },\n";
+    }
+
+    OS << "  };\n\n";
+
+    IndexTypeName = "IndexType";
+    IndexName = "Index";
+    IndexRows = IndexRowsStorage;
   }
 
-  for (auto Entry : SearchTable) {
-    OS << "  { " << searchRepresentation(Entry.first) << ", " << Entry.second
-       << " },\n";
+  bool IsContiguous = false;
+
+  if (Index.Fields.size() == 1 &&
+      (Index.Fields[0].Enum || isa<BitsRecTy>(Index.Fields[0].RecType))) {
+    IsContiguous = true;
+    for (unsigned i = 0; i < IndexRows.size(); ++i) {
+      if (getNumericKey(Index, IndexRows[i]) != i) {
+        IsContiguous = false;
+        break;
+      }
+    }
   }
-  OS << "};\n\n";
-}
 
-void SearchableTableEmitter::emitLookupFunction(StringRef Name, StringRef Field,
-                                                Init *I, raw_ostream &OS) {
-  bool IsIntegral = isIntegral(I);
-  std::string FieldType = searchableFieldType(I);
-  std::string PairType = "std::pair<" + FieldType + ", int>";
-
-  // const SysRegs *lookupSysRegByName(const char *Name) {
-  OS << "const " << Name << " *"
-     << "lookup" << Name << "By" << Field;
-  OS << "(" << (IsIntegral ? FieldType : "StringRef") << " " << Field
-     << ") {\n";
-
-  if (IsIntegral) {
-    OS << "  auto CanonicalVal = " << Field << ";\n";
-    OS << " " << PairType << " Val = {CanonicalVal, 0};\n";
-  } else {
-    // Make sure the result is null terminated because it's going via "char *".
-    OS << "  std::string CanonicalVal = " << Field << ".upper();\n";
-    OS << "  " << PairType << " Val = {CanonicalVal.c_str(), 0};\n";
+  if (IsContiguous) {
+    OS << "  auto Table = makeArrayRef(" << IndexName << ");\n";
+    OS << "  size_t Idx = " << Index.Fields[0].Name << ";\n";
+    OS << "  return Idx >= Table.size() ? nullptr : ";
+    if (IsPrimary)
+      OS << "&Table[Idx]";
+    else
+      OS << "&" << Table.Name << "[Table[Idx]._index]";
+    OS << ";\n";
+    OS << "}\n";
+    return;
+  }
+
+  if (Index.EarlyOut) {
+    const GenericField &Field = Index.Fields[0];
+    std::string FirstRepr =
+        primaryRepresentation(Field, IndexRows[0]->getValueInit(Field.Name));
+    std::string LastRepr = primaryRepresentation(
+        Field, IndexRows.back()->getValueInit(Field.Name));
+    OS << "  if ((" << Field.Name << " < " << FirstRepr << ") ||\n";
+    OS << "      (" << Field.Name << " > " << LastRepr << "))\n";
+    OS << "    return nullptr;\n\n";
   }
 
-  OS << "  ArrayRef<" << PairType << "> Table(" << Name << "sBy" << Field
-     << ");\n";
-  OS << "  auto Idx = std::lower_bound(Table.begin(), Table.end(), Val";
-
-  if (IsIntegral)
-    OS << ");\n";
-  else {
-    OS << ",\n                              ";
-    OS << "[](const " << PairType << " &LHS, const " << PairType
-       << " &RHS) {\n";
-    OS << "    return std::strcmp(LHS.first, RHS.first) < 0;\n";
-    OS << "  });\n\n";
+  OS << "  struct KeyType {\n";
+  for (const auto &Field : Index.Fields) {
+    OS << "    " << searchableFieldType(Field, TypeInTempStruct) << " "
+       << Field.Name << ";\n";
+  }
+  OS << "  };\n";
+  OS << "  KeyType Key = { ";
+  bool NeedComma = false;
+  for (const auto &Field : Index.Fields) {
+    if (NeedComma)
+      OS << ", ";
+    NeedComma = true;
+
+    OS << Field.Name;
+    if (isa<StringRecTy>(Field.RecType)) {
+      OS << ".upper()";
+      if (IsPrimary)
+        PrintFatalError(Twine("Use a secondary index for case-insensitive "
+                              "comparison of field '") +
+                        Field.Name + "' in table '" + Table.Name + "'");
+    }
+  }
+  OS << " };\n";
+
+  OS << "  auto Table = makeArrayRef(" << IndexName << ");\n";
+  OS << "  auto Idx = std::lower_bound(Table.begin(), Table.end(), Key,\n";
+  OS << "    [](const " << IndexTypeName << " &LHS, const KeyType &RHS) {\n";
+
+  for (const auto &Field : Index.Fields) {
+    if (isa<StringRecTy>(Field.RecType)) {
+      OS << "      int Cmp" << Field.Name << " = StringRef(LHS." << Field.Name
+         << ").compare(RHS." << Field.Name << ");\n";
+      OS << "      if (Cmp" << Field.Name << " < 0) return true;\n";
+      OS << "      if (Cmp" << Field.Name << " > 0) return false;\n";
+    } else {
+      OS << "      if (LHS." << Field.Name << " < RHS." << Field.Name << ")\n";
+      OS << "        return true;\n";
+      OS << "      if (LHS." << Field.Name << " > RHS." << Field.Name << ")\n";
+      OS << "        return false;\n";
+    }
   }
 
-  OS << "  if (Idx == Table.end() || CanonicalVal != Idx->first)\n";
-  OS << "    return nullptr;\n";
+  OS << "      return false;\n";
+  OS << "    });\n\n";
+
+  OS << "  if (Idx == Table.end()";
 
-  OS << "  return &" << Name << "sList[Idx->second];\n";
-  OS << "}\n\n";
+  for (const auto &Field : Index.Fields)
+    OS << " ||\n      Key." << Field.Name << " != Idx->" << Field.Name;
+  OS << ")\n    return nullptr;\n";
+
+  if (IsPrimary)
+    OS << "  return &*Idx;\n";
+  else
+    OS << "  return &" << Table.Name << "[Idx->_index];\n";
+
+  OS << "}\n";
 }
 
-void SearchableTableEmitter::emitLookupDeclaration(StringRef Name,
-                                                   StringRef Field, Init *I,
+void SearchableTableEmitter::emitLookupDeclaration(const GenericTable &Table,
+                                                   const SearchIndex &Index,
                                                    raw_ostream &OS) {
-  bool IsIntegral = isIntegral(I);
-  std::string FieldType = searchableFieldType(I);
-  OS << "const " << Name << " *"
-     << "lookup" << Name << "By" << Field;
-  OS << "(" << (IsIntegral ? FieldType : "StringRef") << " " << Field
-     << ");\n\n";
+  OS << "const " << Table.CppTypeName << " *" << Index.Name << "(";
+
+  bool NeedComma = false;
+  for (const auto &Field : Index.Fields) {
+    if (NeedComma)
+      OS << ", ";
+    NeedComma = true;
+
+    OS << searchableFieldType(Field, TypeInArgument) << " " << Field.Name;
+  }
+  OS << ")";
 }
 
-void SearchableTableEmitter::emitMapping(Record *InstanceClass,
-                                         raw_ostream &OS) {
-  StringRef TableName = InstanceClass->getName();
-  std::vector<Record *> Items = Records.getAllDerivedDefinitions(TableName);
+void SearchableTableEmitter::emitGenericTable(const GenericTable &Table,
+                                              raw_ostream &OS) {
+  emitIfdef((Twine("GET_") + Table.PreprocessorGuard + "_DECL").str(), OS);
 
-  // Gather all the records we're going to need for this particular mapping.
-  std::vector<std::vector<SearchTableEntry>> SearchTables;
-  std::vector<std::string> SearchFieldNames;
+  // Emit the declarations for the functions that will perform lookup.
+  if (Table.PrimaryKey) {
+    emitLookupDeclaration(Table, *Table.PrimaryKey, OS);
+    OS << ";\n";
+  }
+  for (const auto &Index : Table.Indices) {
+    emitLookupDeclaration(Table, *Index, OS);
+    OS << ";\n";
+  }
 
-  std::vector<std::string> FieldNames;
-  for (const RecordVal &Field : InstanceClass->getValues()) {
-    std::string FieldName = Field.getName();
+  OS << "#endif\n\n";
 
-    // Skip uninteresting fields: either built-in, special to us, or injected
-    // template parameters (if they contain a ':').
-    if (FieldName.find(':') != std::string::npos || FieldName == "NAME" ||
-        FieldName == "SearchableFields" || FieldName == "EnumNameField" ||
-        FieldName == "EnumValueField")
-      continue;
+  emitIfdef((Twine("GET_") + Table.PreprocessorGuard + "_IMPL").str(), OS);
 
-    FieldNames.push_back(FieldName);
-  }
+  // The primary data table contains all the fields defined for this map.
+  OS << "const " << Table.CppTypeName << " " << Table.Name << "[] = {\n";
+  for (unsigned i = 0; i < Table.Entries.size(); ++i) {
+    Record *Entry = Table.Entries[i];
+    OS << "  { ";
 
-  for (auto *Field : *InstanceClass->getValueAsListInit("SearchableFields")) {
-    SearchTables.emplace_back();
-    SearchFieldNames.push_back(Field->getAsUnquotedString());
+    bool NeedComma = false;
+    for (const auto &Field : Table.Fields) {
+      if (NeedComma)
+        OS << ", ";
+      NeedComma = true;
+
+      OS << primaryRepresentation(Field, Entry->getValueInit(Field.Name));
+    }
+
+    OS << " }, // " << i << "\n";
   }
+  OS << " };\n";
+
+  // Indexes are sorted "{ Thing, PrimaryIdx }" arrays, so that a binary
+  // search can be performed by "Thing".
+  if (Table.PrimaryKey)
+    emitLookupFunction(Table, *Table.PrimaryKey, true, OS);
+  for (const auto &Index : Table.Indices)
+    emitLookupFunction(Table, *Index, false, OS);
+
+  OS << "#endif\n\n";
+}
 
-  int Idx = 0;
-  for (Record *Item : Items) {
-    for (unsigned i = 0; i < SearchFieldNames.size(); ++i) {
-      Init *SearchVal = Item->getValueInit(SearchFieldNames[i]);
-      SearchTables[i].emplace_back(SearchVal, Idx);
+bool SearchableTableEmitter::parseFieldType(GenericField &Field, Init *II) {
+  if (auto DI = dyn_cast<DefInit>(II)) {
+    Record *TypeRec = DI->getDef();
+    if (TypeRec->isSubClassOf("GenericEnum")) {
+      Field.Enum = EnumMap[TypeRec];
+      Field.RecType = RecordRecTy::get(Field.Enum->Class);
+      return true;
     }
-    ++Idx;
   }
 
-  OS << "#ifdef GET_" << TableName.upper() << "_DECL\n";
-  OS << "#undef GET_" << TableName.upper() << "_DECL\n";
+  return false;
+}
 
-  // Next emit the enum containing the top-level names for use in C++ code if
-  // requested
-  if (!InstanceClass->isValueUnset("EnumNameField")) {
-    emitMappingEnum(Items, InstanceClass, OS);
+std::unique_ptr<SearchIndex>
+SearchableTableEmitter::parseSearchIndex(GenericTable &Table, StringRef Name,
+                                         const std::vector<StringRef> &Key,
+                                         bool EarlyOut) {
+  auto Index = llvm::make_unique<SearchIndex>();
+  Index->Name = Name;
+  Index->EarlyOut = EarlyOut;
+
+  for (const auto &FieldName : Key) {
+    const GenericField *Field = Table.getFieldByName(FieldName);
+    if (!Field)
+      PrintFatalError(Twine("Search index '") + Name +
+                      "' refers to non-existing field '" + FieldName +
+                      "' in table '" + Table.Name + "'");
+    Index->Fields.push_back(*Field);
   }
 
-  // And the declarations for the functions that will perform lookup.
-  for (unsigned i = 0; i < SearchFieldNames.size(); ++i)
-    emitLookupDeclaration(TableName, SearchFieldNames[i],
-                          SearchTables[i][0].first, OS);
+  if (EarlyOut && isa<StringRecTy>(Index->Fields[0].RecType)) {
+    PrintFatalError(
+        "Early-out is not supported for string types (in search index '" +
+        Twine(Name) + "'");
+  }
 
-  OS << "#endif\n\n";
+  return Index;
+}
 
-  OS << "#ifdef GET_" << TableName.upper() << "_IMPL\n";
-  OS << "#undef GET_" << TableName.upper() << "_IMPL\n";
+void SearchableTableEmitter::collectEnumEntries(
+    GenericEnum &Enum, StringRef NameField, StringRef ValueField,
+    const std::vector<Record *> &Items) {
+  for (auto EntryRec : Items) {
+    StringRef Name;
+    if (NameField.empty())
+      Name = EntryRec->getName();
+    else
+      Name = EntryRec->getValueAsString(NameField);
+
+    int64_t Value = 0;
+    if (!ValueField.empty())
+      Value = getInt(EntryRec, ValueField);
+
+    Enum.Entries.push_back(llvm::make_unique<GenericEnum::Entry>(Name, Value));
+    Enum.EntryMap.insert(std::make_pair(EntryRec, Enum.Entries.back().get()));
+  }
 
-  // The primary data table contains all the fields defined for this map.
-  emitPrimaryTable(TableName, FieldNames, SearchFieldNames, SearchTables, Items,
-                   OS);
+  if (ValueField.empty()) {
+    std::stable_sort(Enum.Entries.begin(), Enum.Entries.end(),
+                     [](const std::unique_ptr<GenericEnum::Entry> &LHS,
+                        const std::unique_ptr<GenericEnum::Entry> &RHS) {
+                       return LHS->first < RHS->first;
+                     });
 
-  // Indexes are sorted "{ Thing, PrimaryIdx }" arrays, so that a binary
-  // search can be performed by "Thing".
-  for (unsigned i = 0; i < SearchTables.size(); ++i) {
-    emitSearchTable(TableName, SearchFieldNames[i], SearchTables[i], OS);
-    emitLookupFunction(TableName, SearchFieldNames[i], SearchTables[i][0].first,
-                       OS);
+    for (size_t i = 0; i < Enum.Entries.size(); ++i)
+      Enum.Entries[i]->second = i;
+  }
+}
+
+void SearchableTableEmitter::collectTableEntries(
+    GenericTable &Table, const std::vector<Record *> &Items) {
+  for (auto EntryRec : Items) {
+    for (auto &Field : Table.Fields) {
+      auto TI = dyn_cast<TypedInit>(EntryRec->getValueInit(Field.Name));
+      if (!TI) {
+        PrintFatalError(Twine("Record '") + EntryRec->getName() +
+                        "' in table '" + Table.Name + "' is missing field '" +
+                        Field.Name + "'");
+      }
+      if (!Field.RecType) {
+        Field.RecType = TI->getType();
+      } else {
+        RecTy *Ty = resolveTypes(Field.RecType, TI->getType());
+        if (!Ty)
+          PrintFatalError(Twine("Field '") + Field.Name + "' of table '" +
+                          Table.Name + "' has incompatible type: " +
+                          Ty->getAsString() + " vs. " +
+                          TI->getType()->getAsString());
+        Field.RecType = Ty;
+      }
+    }
+
+    Table.Entries.push_back(EntryRec);
   }
 
-  OS << "#endif\n";
+  Record *IntrinsicClass = Records.getClass("Intrinsic");
+  Record *InstructionClass = Records.getClass("Instruction");
+  for (auto &Field : Table.Fields) {
+    if (auto RecordTy = dyn_cast<RecordRecTy>(Field.RecType)) {
+      if (IntrinsicClass && RecordTy->isSubClassOf(IntrinsicClass))
+        Field.IsIntrinsic = true;
+      else if (InstructionClass && RecordTy->isSubClassOf(InstructionClass))
+        Field.IsInstruction = true;
+    }
+  }
 }
 
 void SearchableTableEmitter::run(raw_ostream &OS) {
-  // Tables are defined to be the direct descendents of "SearchableEntry".
+  // Emit tables in a deterministic order to avoid needless rebuilds.
+  SmallVector<std::unique_ptr<GenericTable>, 4> Tables;
+  DenseMap<Record *, GenericTable *> TableMap;
+
+  // Collect all definitions first.
+  for (auto EnumRec : Records.getAllDerivedDefinitions("GenericEnum")) {
+    StringRef NameField;
+    if (!EnumRec->isValueUnset("NameField"))
+      NameField = EnumRec->getValueAsString("NameField");
+
+    StringRef ValueField;
+    if (!EnumRec->isValueUnset("ValueField"))
+      ValueField = EnumRec->getValueAsString("ValueField");
+
+    auto Enum = llvm::make_unique<GenericEnum>();
+    Enum->Name = EnumRec->getName();
+    Enum->PreprocessorGuard = EnumRec->getName();
+
+    StringRef FilterClass = EnumRec->getValueAsString("FilterClass");
+    Enum->Class = Records.getClass(FilterClass);
+    if (!Enum->Class)
+      PrintFatalError(Twine("Enum FilterClass '") + FilterClass +
+                      "' does not exist");
+
+    collectEnumEntries(*Enum, NameField, ValueField,
+                       Records.getAllDerivedDefinitions(FilterClass));
+    EnumMap.insert(std::make_pair(EnumRec, Enum.get()));
+    Enums.emplace_back(std::move(Enum));
+  }
+
+  for (auto TableRec : Records.getAllDerivedDefinitions("GenericTable")) {
+    auto Table = llvm::make_unique<GenericTable>();
+    Table->Name = TableRec->getName();
+    Table->PreprocessorGuard = TableRec->getName();
+    Table->CppTypeName = TableRec->getValueAsString("CppTypeName");
+
+    std::vector<StringRef> Fields = TableRec->getValueAsListOfStrings("Fields");
+    for (const auto &FieldName : Fields) {
+      Table->Fields.emplace_back(FieldName);
+
+      if (auto TypeOfVal = TableRec->getValue(("TypeOf_" + FieldName).str())) {
+        if (!parseFieldType(Table->Fields.back(), TypeOfVal->getValue())) {
+          PrintFatalError(Twine("Table '") + Table->Name +
+                          "' has bad 'TypeOf_" + FieldName + "': " +
+                          TypeOfVal->getValue()->getAsString());
+        }
+      }
+    }
+
+    collectTableEntries(*Table, Records.getAllDerivedDefinitions(
+                                    TableRec->getValueAsString("FilterClass")));
+
+    if (!TableRec->isValueUnset("PrimaryKey")) {
+      Table->PrimaryKey =
+          parseSearchIndex(*Table, TableRec->getValueAsString("PrimaryKeyName"),
+                           TableRec->getValueAsListOfStrings("PrimaryKey"),
+                           TableRec->getValueAsBit("PrimaryKeyEarlyOut"));
+
+      std::stable_sort(Table->Entries.begin(), Table->Entries.end(),
+                       [&](Record *LHS, Record *RHS) {
+                         return compareBy(LHS, RHS, *Table->PrimaryKey);
+                       });
+    }
+
+    TableMap.insert(std::make_pair(TableRec, Table.get()));
+    Tables.emplace_back(std::move(Table));
+  }
+
+  for (Record *IndexRec : Records.getAllDerivedDefinitions("SearchIndex")) {
+    Record *TableRec = IndexRec->getValueAsDef("Table");
+    auto It = TableMap.find(TableRec);
+    if (It == TableMap.end())
+      PrintFatalError(Twine("SearchIndex '") + IndexRec->getName() +
+                      "' refers to non-existing table '" + TableRec->getName());
+
+    GenericTable &Table = *It->second;
+    Table.Indices.push_back(parseSearchIndex(
+        Table, IndexRec->getName(), IndexRec->getValueAsListOfStrings("Key"),
+        IndexRec->getValueAsBit("EarlyOut")));
+  }
+
+  // Translate legacy tables.
   Record *SearchableTable = Records.getClass("SearchableTable");
   for (auto &NameRec : Records.getClasses()) {
     Record *Class = NameRec.second.get();
     if (Class->getSuperClasses().size() != 1 ||
         !Class->isSubClassOf(SearchableTable))
       continue;
-    emitMapping(Class, OS);
+
+    StringRef TableName = Class->getName();
+    std::vector<Record *> Items = Records.getAllDerivedDefinitions(TableName);
+    if (!Class->isValueUnset("EnumNameField")) {
+      StringRef NameField = Class->getValueAsString("EnumNameField");
+      StringRef ValueField;
+      if (!Class->isValueUnset("EnumValueField"))
+        ValueField = Class->getValueAsString("EnumValueField");
+
+      auto Enum = llvm::make_unique<GenericEnum>();
+      Enum->Name = (Twine(Class->getName()) + "Values").str();
+      Enum->PreprocessorGuard = Class->getName().upper();
+      Enum->Class = Class;
+
+      collectEnumEntries(*Enum, NameField, ValueField, Items);
+
+      Enums.emplace_back(std::move(Enum));
+    }
+
+    auto Table = llvm::make_unique<GenericTable>();
+    Table->Name = (Twine(Class->getName()) + "sList").str();
+    Table->PreprocessorGuard = Class->getName().upper();
+    Table->CppTypeName = Class->getName();
+
+    for (const RecordVal &Field : Class->getValues()) {
+      std::string FieldName = Field.getName();
+
+      // Skip uninteresting fields: either special to us, or injected
+      // template parameters (if they contain a ':').
+      if (FieldName.find(':') != std::string::npos ||
+          FieldName == "SearchableFields" || FieldName == "EnumNameField" ||
+          FieldName == "EnumValueField")
+        continue;
+
+      Table->Fields.emplace_back(FieldName);
+    }
+
+    collectTableEntries(*Table, Items);
+
+    for (const auto &Field :
+         Class->getValueAsListOfStrings("SearchableFields")) {
+      std::string Name =
+          (Twine("lookup") + Table->CppTypeName + "By" + Field).str();
+      Table->Indices.push_back(parseSearchIndex(*Table, Name, {Field}, false));
+    }
+
+    Tables.emplace_back(std::move(Table));
   }
+
+  // Emit everything.
+  for (const auto &Enum : Enums)
+    emitGenericEnum(*Enum, OS);
+
+  for (const auto &Table : Tables)
+    emitGenericTable(*Table, OS);
+
+  // Put all #undefs last, to allow multiple sections guarded by the same
+  // define.
+  for (const auto &Guard : PreprocessorGuards)
+    OS << "#undef " << Guard << "\n";
 }
 
 namespace llvm {