TableGen/SearchableTables: Support more generic enums and tables

[nhaehnle]

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

[javed.absar]

include/llvm/TableGen/SearchableTable.td

15 ↗

(On Diff #150720)

nitpick - "Is is guarded by..."

[javed.absar]

include/llvm/TableGen/SearchableTable.td

77 ↗

(On Diff #150720)

Maybe change to 'MyEnum' to be consistent with rest of the example.

[tra]

Few nits. LGTM syntax-wise. I'm not very familiar with backend, so will defer to someone who has better idea.

include/llvm/TableGen/SearchableTable.td

22–26 ↗

(On Diff #150720)

What's expected to happen if we have names foo and FOO?

utils/TableGen/SearchableTableEmitter.cpp

166–167 ↗

(On Diff #150720)

Either there's one extra ' or one is missing. There's no closing quote for Field.Name.

660 ↗

(On Diff #150720)

If would be good to check and warn about name clashes if we have records that differ by case only.

695 ↗

(On Diff #150720)

Nit: I'd use auto *IndexRec or even Record *IndexRec, otherwise it makes one wonder whether we are creating unnecessary copies here and why it's not auto const &.

[nhaehnle]

• Address review comments
• Fix formatting
• Fix IsContiguous optimization for non-primary search indices

[nhaehnle]

include/llvm/TableGen/SearchableTable.td

15 ↗

(On Diff #150720)

Fixed, thanks.

22–26 ↗

(On Diff #150720)

Nothing in particular. They will use the same include guard name, like the code that existed before.

Having an enum and a table guarded by the same guard is actually something that happens with the translation of the old SearchableTable, and it's why I've moved the corresponding #undefs to be at the end of the generated file.

So I'm not sure that is something that needs a warning either? I mean, everything should still work if you have two definitions that differ only by case, it's just that you then cannot selectively "GET" only one of them from C++.

77 ↗

(On Diff #150720)

Done.

utils/TableGen/SearchableTableEmitter.cpp

166–167 ↗

(On Diff #150720)

Fixed, thanks.

695 ↗

(On Diff #150720)

Done.

[nhaehnle]

Ping. Does this look alright?

[tra]

include/llvm/TableGen/SearchableTable.td

22–26 ↗

(On Diff #150720)

Poking around at how we use generated files, it appears that including unintended bits may potentially be a problem.

E.g. ARM and AArch64 put individual records into their own namespaces. Accidentally putting multiple conflicting implementations may become a problem if/when, for example, someone attempts to pull both namespaces in with using, then structs/functions from both records will become ambiguous. It's a somewhat contrived scenario easily fixed by renaming an entity in .td, but I'd argue that if a tool provides a feature with constraints on its inputs, then it's the tool's duty to report when those constraints are violated. At the very least it should be clearly documented. Currently the doc is somewhat hard to read in that regard -- the example names GET_name_DECL use *lower*case name, but then say that the name will really be upper case and don't mention naming conflicts at all. The reader can deduce that making the name uppercase can lead to possible conflicts and unintended consequences down the road, but that's removed from the source of such error both in time and space.

Where possible, I'd prefer to make errors obvious as close to the source as we can manage. If that's not worth it, we should at least add a note in the docs that it's user's responsibility to guarantee non-clashing names.

[nhaehnle]

Preserve the case in preprocessor guards for GenericEnum and GenericTable.

We'll still use upper case for SearchableTable, but that is just to
preserve compatibility and not change behavior.

[nhaehnle]

include/llvm/TableGen/SearchableTable.td

22–26 ↗

(On Diff #150720)

I'm changing it to just not make the name upper case for the new primitives. So for a table called MyTable, it'll be guarded by GET_MyTable_IMPL. That way, it's "impossible" to make mistakes.

I'm keeping the behavior of the old SearchableTable as-is though, I don't think it makes sense to change that.

[tra]

LGTM in general. If anyone has comments on the back-end functionality, feel free to chime in.

include/llvm/TableGen/SearchableTable.td

22–26 ↗

(On Diff #150720)

Works for me.

[RKSimon]

llvm/trunk/utils/TableGen/SearchableTableEmitter.cpp

437

@nhaehnle We are still seeing signed/unsigned warnings on MSVC builds - please fix this.

http://lab.llvm.org:8011/builders/lld-x86_64-win7/builds/25901/steps/build%20lld/logs/warnings%20%282%29

[nhaehnle]

llvm/trunk/utils/TableGen/SearchableTableEmitter.cpp

437

Please see D51097.

llvm/trunk/docs/TableGen/BackEnds.rst

 
 **Purpose**: Generate (target) intrinsic information.
 
 OptParserDefs
 -------------
 
 **Purpose**: Print enum values for a class.
 
+SearchableTables
+----------------
+
+**Purpose**: Generate custom searchable tables.
+
+**Output**: Enums, global tables and lookup helper functions.
+
+**Usage**: This backend allows generating free-form, target-specific tables
+from TableGen records. The ARM and AArch64 targets use this backend to generate
+tables of system registers; the AMDGPU target uses it to generate meta-data
+about complex image and memory buffer instructions.
+
+More documentation is available in ``include/llvm/TableGen/SearchableTable.td``,
+which also contains the definitions of TableGen classes which must be
+instantiated in order to define the enums and tables emitted by this backend.
+
 CTags
 -----
 
 **Purpose**: This tablegen backend emits an index of definitions in ctags(1)
 format. A helper script, utils/TableGen/tdtags, provides an easier-to-use
 interface; run 'tdtags -H' for documentation.
 
 X86EVEX2VEX

llvm/trunk/include/llvm/TableGen/SearchableTable.td

 //===- SearchableTable.td ----------------------------------*- tablegen -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines the key top-level classes needed to produce a reasonably
-// generic table that can be binary-searched via int and string entries.
+// generic table that can be binary-searched. Three types of objects can be
+// defined using the classes in this file:
 //
-// Each table must instantiate "Mappingkind", listing the fields that should be
-// included and fields that shoould be searchable. Only two kinds of fields are
-// searchable at the moment: "strings" (which are compared case-insensitively),
-// and "bits".
-//
-// For each "MappingKind" the generated header will create GET_MAPPINGKIND_DECL
-// and GET_MAPPINGKIND_IMPL guards.
-//
-// Inside the DECL guard will be a set of function declarations:
-// "lookup{InstanceClass}By{SearchableField}", returning "const {InstanceClass}
-// *" and accepting either a StringRef or a uintN_t. Additionally, if
-// EnumNameField is still defined, there will be an "enum {InstanceClass}Values"
-// allowing C++ code to reference either the primary data table's entries (if
-// EnumValueField is not defined) or some other field (e.g. encoding) if it is.
-//
-// Inside the IMPL guard will be a primary data table "{InstanceClass}sList" and
-// as many searchable indexes as requested
-// ("{InstanceClass}sBy{SearchableField}"). Additionally implementations of the
-// lookup function will be provided.
+// 1. (Generic) Enums. By instantiating the GenericEnum class once, an enum with
+// the name of the def is generated. It is guarded by the preprocessor define
+// GET_name_DECL, where name is the name of the def.
+//
+// 2. (Generic) Tables and search indices. By instantiating the GenericTable
+// class once, a table with the name of the instantiating def is generated and
+// guarded by the GET_name_IMPL preprocessor guard.
+//
+// Both a primary key and additional secondary keys / search indices can also
+// be defined, which result in the generation of lookup functions. Their
+// declarations and definitions are all guarded by GET_name_DECL and
+// GET_name_IMPL, respectively, where name is the name of the underlying table.
 //
 // See AArch64SystemOperands.td and its generated header for example uses.
 //
 //===----------------------------------------------------------------------===//
 
+// Define a record derived from this class to generate a generic enum.
+//
+// The name of the record is used as the type name of the C++ enum.
+class GenericEnum {
+  // Name of a TableGen class. The enum will have one entry for each record
+  // that derives from that class.
+  string FilterClass;
+
+  // (Optional) Name of a field that is present in all collected records and
+  // contains the name of enum entries.
+  //
+  // If NameField is not set, the record names will be used instead.
+  string NameField;
+
+  // (Optional) Name of a field that is present in all collected records and
+  // contains the numerical value of enum entries.
+  //
+  // If ValueField is not set, enum values will be assigned automatically,
+  // starting at 0, according to a lexicographical sort of the entry names.
+  string ValueField;
+}
+
+// Define a record derived from this class to generate a generic table. This
+// table can have a searchable primary key, and it can also be referenced by
+// external search indices.
+//
+// The name of the record is used as the name of the global primary array of
+// entries of the table in C++.
+class GenericTable {
+  // Name of a class. The table will have one entry for each record that
+  // derives from that class.
+  string FilterClass;
+
+  // Name of the C++ struct/class type that holds table entries. The
+  // declaration of this type is not generated automatically.
+  string CppTypeName = FilterClass;
+
+  // List of the names of fields of collected records that contain the data for
+  // table entries, in the order that is used for initialization in C++.
+  //
+  // For each field of the table named XXX, TableGen will look for a value
+  // called TypeOf_XXX and use that as a more detailed description of the
+  // type of the field if present. This is required for fields whose type
+  // cannot be deduced automatically, such as enum fields. For example:
+  //
+  //   def MyEnum : GenericEnum {
+  //     let FilterClass = "MyEnum";
+  //     ...
+  //   }
+  //
+  //   class MyTableEntry {
+  //     MyEnum V;
+  //     ...
+  //   }
+  //
+  //   def MyTable : GenericTable {
+  //     let FilterClass = "MyTableEntry";
+  //     let Fields = ["V", ...];
+  //     GenericEnum TypeOf_V = MyEnum;
+  //   }
+  //
+  // Fields of type bit, bits<N>, string, Intrinsic, and Instruction (or
+  // derived classes of those) are supported natively.
+  //
+  // Additionally, fields of type `code` can appear, where the value is used
+  // verbatim as an initializer. However, these fields cannot be used as
+  // search keys.
+  list<string> Fields;
+
+  // (Optional) List of fields that make up the primary key.
+  list<string> PrimaryKey;
+
+  // (Optional) Name of the primary key search function.
+  string PrimaryKeyName;
+
+  // See SearchIndex.EarlyOut
+  bit PrimaryKeyEarlyOut = 0;
+}
+
+// Define a record derived from this class to generate an additional search
+// index for a generic table that has been defined earlier.
+//
+// The name of the record will be used as the name of the C++ lookup function.
+class SearchIndex {
+  // Table that this search index refers to.
+  GenericTable Table;
+
+  // List of fields that make up the key.
+  list<string> Key;
+
+  // If true, the lookup function will check the first field of the key against
+  // the minimum and maximum values in the index before entering the binary
+  // search. This is convenient for tables that add extended data for a subset
+  // of a larger enum-based space, e.g. extended data about a subset of
+  // instructions.
+  //
+  // Can only be used when the first field is an integral (non-string) type.
+  bit EarlyOut = 0;
+}
+
+// Legacy table type with integrated enum.
 class SearchableTable {
   list<string> SearchableFields;
   string EnumNameField = "Name";
   string EnumValueField;
 }

llvm/trunk/test/TableGen/generic-tables-instruction.td

+// RUN: llvm-tblgen -gen-searchable-tables -I %p/../../include %s | FileCheck %s
+// XFAIL: vg_leak
+
+include "llvm/TableGen/SearchableTable.td"
+
+// CHECK-LABEL: GET_InstrTable_IMPL
+// CHECK: const MyInstr InstrTable[] = {
+// CHECK:   { B, 0xA },
+// CHECK:   { C, 0x0 },
+// CHECK:   { A, 0x5 },
+// CHECK:   { D, 0x8 },
+// CHECK: };
+
+class Instruction {
+  bit isPseudo = 0;
+}
+
+class MyInstr<int op> : Instruction {
+  Instruction Opcode = !cast<Instruction>(NAME);
+  bits<16> CustomEncoding = op;
+}
+
+def A : MyInstr<5>;
+def D : MyInstr<8>;
+let isPseudo = 1 in {
+  def C : MyInstr<0>;
+  def B : MyInstr<10>;
+}
+
+def InstrTable : GenericTable {
+  let FilterClass = "MyInstr";
+  let Fields = ["Opcode", "CustomEncoding"];
+
+  let PrimaryKey = ["Opcode"];
+  let PrimaryKeyName = "getCustomEncodingHelper";
+}

llvm/trunk/test/TableGen/generic-tables.td

+// RUN: llvm-tblgen -gen-searchable-tables -I %p/../../include %s | FileCheck %s
+// XFAIL: vg_leak
+
+include "llvm/TableGen/SearchableTable.td"
+
+// CHECK-LABEL: GET_BValues_DECL
+// CHECK: enum BValues {
+// CHECK:   BAlice = 172,
+// CHECK:   BBob = 20,
+// CHECK:   BCharlie = 128,
+// CHECK:   BEve = 76,
+// CHECK: }
+
+// CHECK-LABEL: GET_CEnum_DECL
+// CHECK: enum CEnum {
+// CHECK:   CBar
+// CHECK:   CBaz
+// CHECK:   CFoo
+// CHECK: }
+
+// CHECK-LABEL: GET_ATable_DECL
+// CHECK: const AEntry *lookupATableByValues(uint8_t Val1, uint16_t Val2);
+
+// CHECK-LABEL: GET_ATable_IMPL
+// CHECK: const AEntry ATable[] = {
+// CHECK:   { "baz"
+// CHECK:   { "foo"
+// CHECK:   { "foobar"
+// CHECK:   { "bar"
+// CHECK: };
+
+// CHECK: const AEntry *lookupATableByValues(uint8_t Val1, uint16_t Val2) {
+// CHECK:   return &*Idx;
+// CHECK: }
+
+class AEntry<string str, int val1, int val2> {
+  string Str = str;
+  bits<8> Val1 = val1;
+  bits<10> Val2 = val2;
+}
+
+def : AEntry<"bar",    5, 3>;
+def : AEntry<"baz",    2, 6>;
+def : AEntry<"foo",    4, 4>;
+def : AEntry<"foobar", 4, 5>;
+
+def ATable : GenericTable {
+  let FilterClass = "AEntry";
+  let Fields = ["Str", "Val1", "Val2"];
+
+  let PrimaryKey = ["Val1", "Val2"];
+  let PrimaryKeyName = "lookupATableByValues";
+}
+
+
+// CHECK-LABEL: GET_BTable_IMPL
+// CHECK: const BTypeName *lookupBTableByName(StringRef Name) {
+// CHECK:   return &BTable[Idx->_index];
+// CHECK: }
+
+class BEntry<bits<16> enc> {
+  string Name = NAME;
+  bits<16> Encoding = enc;
+}
+
+def BAlice   : BEntry<0xac>;
+def BBob     : BEntry<0x14>;
+def BCharlie : BEntry<0x80>;
+def BEve     : BEntry<0x4c>;
+
+def BValues : GenericEnum {
+  let FilterClass = "BEntry";
+  let NameField = "Name";
+  let ValueField = "Encoding";
+}
+
+def BTable : GenericTable {
+  let FilterClass = "BEntry";
+  string CppTypeName = "BTypeName";
+  let Fields = ["Name", "Encoding"];
+}
+
+def lookupBTableByName : SearchIndex {
+  let Table = BTable;
+  let Key = ["Name"];
+}
+
+
+// CHECK-LABEL: GET_CTable_DECL
+// CHECK: const CEntry *lookupCEntryByEncoding(uint16_t Encoding);
+// CHECK: const CEntry *lookupCEntry(StringRef Name, unsigned Kind);
+// CHECK-LABEL: GET_CTable_IMPL
+// CHECK: const CEntry *lookupCEntryByEncoding(uint16_t Encoding) {
+// CHECK:   if ((Encoding < 0xA) ||
+// CHECK:       (Encoding > 0xF))
+// CHECK:     return nullptr;
+
+// CHECK: const CEntry *lookupCEntry(StringRef Name, unsigned Kind) {
+// CHECK: Index[] = {
+// CHECK:   { "ALICE", CBar, 1 },
+// CHECK:   { "ALICE", CFoo, 0 },
+// CHECK:   { "BOB", CBaz, 2 },
+
+class CEnum;
+
+def CFoo : CEnum;
+def CBar : CEnum;
+def CBaz : CEnum;
+
+def CEnum : GenericEnum {
+  let FilterClass = "CEnum";
+}
+
+class CEntry<string name, CEnum kind, int enc> {
+  string Name = name;
+  CEnum Kind = kind;
+  bits<16> Encoding = enc;
+}
+
+def : CEntry<"alice", CFoo, 10>;
+def : CEntry<"alice", CBar, 13>;
+def : CEntry<"bob",   CBaz, 15>;
+
+def CTable : GenericTable {
+  let FilterClass = "CEntry";
+  let Fields = ["Name", "Kind", "Encoding"];
+
+  GenericEnum TypeOf_Kind = CEnum;
+
+  let PrimaryKey = ["Encoding"];
+  let PrimaryKeyName = "lookupCEntryByEncoding";
+  let PrimaryKeyEarlyOut = 1;
+}
+
+def lookupCEntry : SearchIndex {
+  let Table = CTable;
+  let Key = ["Name", "Kind"];
+}

llvm/trunk/test/TableGen/searchabletables-intrinsic.td

class Table<Intrinsic intr, int payload> : SearchableTable {
   let SearchableFields = ["Intr"];
   let EnumNameField = ?;
 
   Intrinsic Intr = !cast<Intrinsic>(intr);
   bits<16> Payload = payload;
 }
 
 // CHECK-LABEL: TablesList[] = {
-// CHECK-DAG: { Intrinsic::abc, 0x0},
-// CHECK-DAG: { Intrinsic::xyz, 0x1},
-// CHECK-DAG: { Intrinsic::gtarget_def, 0x10},
-// CHECK-DAG: { Intrinsic::gtarget_defg, 0x11},
-// CHECK-DAG: { Intrinsic::gtarget_uvw, 0x12},
-// CHECK-DAG: { Intrinsic::ftarget_ghi, 0x20},
-// CHECK-DAG: { Intrinsic::ftarget_ghi_x, 0x21},
-// CHECK-DAG: { Intrinsic::ftarget_rst, 0x22},
+// CHECK-DAG: { Intrinsic::abc, 0x0 },
+// CHECK-DAG: { Intrinsic::xyz, 0x1 },
+// CHECK-DAG: { Intrinsic::gtarget_def, 0x10 },
+// CHECK-DAG: { Intrinsic::gtarget_defg, 0x11 },
+// CHECK-DAG: { Intrinsic::gtarget_uvw, 0x12 },
+// CHECK-DAG: { Intrinsic::ftarget_ghi, 0x20 },
+// CHECK-DAG: { Intrinsic::ftarget_ghi_x, 0x21 },
+// CHECK-DAG: { Intrinsic::ftarget_rst, 0x22 },
 
 // Check that the index is in the correct order, consistent with the ordering
 // of enums: alphabetically, but target intrinsics after generic intrinsics
 //
-// CHECK-LABEL: TablesByIntr[] = {
+// CHECK-LABEL: lookupTableByIntr(unsigned Intr) {
+// CHECK: Index[] = {
 // CHECK-NEXT: Intrinsic::abc
 // CHECK-NEXT: Intrinsic::xyz
 // CHECK-NEXT: Intrinsic::ftarget_ghi
 // CHECK-NEXT: Intrinsic::ftarget_ghi_x
 // CHECK-NEXT: Intrinsic::ftarget_rst
 // CHECK-NEXT: Intrinsic::gtarget_def
 // CHECK-NEXT: Intrinsic::gtarget_defg
 // CHECK-NEXT: Intrinsic::gtarget_uvw

llvm/trunk/utils/TableGen/SearchableTableEmitter.cpp

 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/SourceMgr.h"
 #include "llvm/TableGen/Error.h"
 #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) {}
 
   void run(raw_ostream &OS);
 
 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))
       return "0x" + utohexstr(getAsInt(BI));
     else if (BitInit *BI = dyn_cast<BitInit>(I))
       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)
+    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) {
     if (DefInit *DI = dyn_cast<DefInit>(I))
       return DI->getDef()->isSubClassOf("Intrinsic");
     return false;
   }
 
   CodeGenIntrinsic &getIntrinsic(Init *I) {
     std::unique_ptr<CodeGenIntrinsic> &Intr = Intrinsics[I];
     if (!Intr)
       Intr = make_unique<CodeGenIntrinsic>(cast<DefInit>(I)->getDef());
     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))
+  std::string searchableFieldType(const GenericField &Field, TypeContext Ctx) {
+    if (isa<StringRecTy>(Field.RecType)) {
+      if (Ctx == TypeInStaticStruct)
         return "const char *";
-    else if (BitsInit *BI = dyn_cast<BitsInit>(I)) {
+      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;
       else if (NumBits <= 16)
         NumBits = 16;
       else if (NumBits <= 32)
         NumBits = 32;
       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;
+  }
+
+  return getInt(Rec, Index.Fields[0].Name);
+}
+
+/// 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();
       }
-  OS << "};\n\n";
+
+      int comp = LHSs.compare(RHSs);
+      if (comp < 0)
+        return true;
+      if (comp > 0)
+        return false;
+    }
+  }
+  return false;
 }
 
-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";
+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 {
+    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);
 
-  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 << "    { ";
+      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 << "},\n";
+      OS << ", " << Entry.second << " },\n";
     }
-  OS << "};\n\n";
+
+    OS << "  };\n\n";
+
+    IndexTypeName = "IndexType";
+    IndexName = "Index";
+    IndexRows = IndexRowsStorage;
   }
 
-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";
+  bool IsContiguous = false;
 
-  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);
-                     });
-  } else {
-    std::stable_sort(SearchTable.begin(), SearchTable.end(),
-                     [this](const SearchTableEntry &LHS,
-                            const SearchTableEntry &RHS) {
-                       return searchRepresentation(LHS.first) <
-                              searchRepresentation(RHS.first);
-                     });
+  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;
       }
-
-  for (auto Entry : SearchTable) {
-    OS << "  { " << searchRepresentation(Entry.first) << ", " << Entry.second
-       << " },\n";
     }
-  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";
+  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 << "  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 {
-    // 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";
-  }
-
-  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 << "      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()";
+
+  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 << "  return &" << Name << "sList[Idx->second];\n";
-  OS << "}\n\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,
+void SearchableTableEmitter::emitGenericTable(const GenericTable &Table,
                                               raw_ostream &OS) {
-  StringRef TableName = InstanceClass->getName();
-  std::vector<Record *> Items = Records.getAllDerivedDefinitions(TableName);
+  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));
     }
 
-  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);
-    }
-    ++Idx;
-  }
+    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";
 
-  OS << "#ifdef GET_" << TableName.upper() << "_DECL\n";
-  OS << "#undef GET_" << TableName.upper() << "_DECL\n";
+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;
+    }
+  }
 
-  // Next emit the enum containing the top-level names for use in C++ code if
-  // requested
-  if (!InstanceClass->isValueUnset("EnumNameField")) {
-    emitMappingEnum(Items, InstanceClass, OS);
-  }
+  return false;
 
-  // 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);
+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);
+  }
+
+  if (EarlyOut && isa<StringRecTy>(Index->Fields[0].RecType)) {
+    PrintFatalError(
+        "Early-out is not supported for string types (in search index '" +
+        Twine(Name) + "'");
+  }
+
+  return Index;
+}
+
+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);
 
-  OS << "#endif\n\n";
+    int64_t Value = 0;
+    if (!ValueField.empty())
+      Value = getInt(EntryRec, ValueField);
 
-  OS << "#ifdef GET_" << TableName.upper() << "_IMPL\n";
-  OS << "#undef GET_" << TableName.upper() << "_IMPL\n";
+    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;
+  }
 
-  OS << "#endif\n";
+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);
+  }
+
+  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 {
 
 void EmitSearchableTables(RecordKeeper &RK, raw_ostream &OS) {
   SearchableTableEmitter(RK).run(OS);
 }
 
 } // End llvm namespace.