Index: docs/TableGen/BackEnds.rst =================================================================== --- docs/TableGen/BackEnds.rst +++ docs/TableGen/BackEnds.rst @@ -221,6 +221,22 @@ **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 ----- Index: include/llvm/TableGen/SearchableTable.td =================================================================== --- include/llvm/TableGen/SearchableTable.td +++ include/llvm/TableGen/SearchableTable.td @@ -8,32 +8,128 @@ //===----------------------------------------------------------------------===// // // 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". +// 1. (Generic) Enums. By instantiating the GenericEnum class once, an enum with +// the name of the def is generated. Is is guarded by the preprocessor define +// GET_name_DECL, where name is the name of the def (in upper case). // -// For each "MappingKind" the generated header will create GET_MAPPINGKIND_DECL -// and GET_MAPPINGKIND_IMPL guards. +// 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. // -// 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. +// 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 +// (in upper case). // // 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 SomeEnum : GenericEnum { + // let FilterClass = "SomeEnum"; + // ... + // } + // + // class MyTableEntry { + // SomeEnum V; + // ... + // } + // + // def MyTable : GenericTable { + // let FilterClass = "MyTableEntry"; + // let Fields = ["V", ...]; + // GenericEnum TypeOf_V = SomeEnum; + // } + // + // Fields of type bit, bits, 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 Fields; + + // (Optional) List of fields that make up the primary key. + list 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 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 SearchableFields; string EnumNameField = "Name"; Index: test/TableGen/generic-tables-instruction.td =================================================================== --- /dev/null +++ test/TableGen/generic-tables-instruction.td @@ -0,0 +1,36 @@ +// 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 : Instruction { + Instruction Opcode = !cast(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"; +} Index: test/TableGen/generic-tables.td =================================================================== --- /dev/null +++ test/TableGen/generic-tables.td @@ -0,0 +1,138 @@ +// 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 = 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 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 = 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"]; +} Index: test/TableGen/searchabletables-intrinsic.td =================================================================== --- test/TableGen/searchabletables-intrinsic.td +++ test/TableGen/searchabletables-intrinsic.td @@ -53,19 +53,20 @@ } // 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 Index: utils/TableGen/SearchableTableEmitter.cpp =================================================================== --- utils/TableGen/SearchableTableEmitter.cpp +++ utils/TableGen/SearchableTableEmitter.cpp @@ -22,17 +22,76 @@ #include "llvm/TableGen/Record.h" #include "CodeGenIntrinsics.h" #include +#include #include #include + using namespace llvm; #define DEBUG_TYPE "searchable-table-emitter" namespace { +struct GenericTable; + +int getAsInt(Init *B) { + return cast(B->convertInitializerTo(IntRecTy::get()))->getValue(); +} +int getInt(Record *R, StringRef Field) { + return getAsInt(R->getValueInit(Field)); +} + +struct GenericEnum { + using Entry = std::pair; + + std::string Name; + Record *Class; + std::string PreprocessorGuard; + std::vector> Entries; + DenseMap 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 Fields; + bool EarlyOut; +}; + +struct GenericTable { + std::string Name; + std::string PreprocessorGuard; + std::string CppTypeName; + SmallVector Fields; + std::vector Entries; + + std::unique_ptr PrimaryKey; + SmallVector, 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> Intrinsics; + std::vector> Enums; + DenseMap EnumMap; + std::set PreprocessorGuards; public: SearchableTableEmitter(RecordKeeper &R) : Records(R) {} @@ -42,14 +101,13 @@ private: typedef std::pair SearchTableEntry; - int getAsInt(BitsInit *B) { - return cast(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(I)) return SI->getAsString(); else if (BitsInit *BI = dyn_cast(I)) @@ -58,19 +116,14 @@ return BI->getValue() ? "true" : "false"; else if (CodeInit *CI = dyn_cast(I)) return CI->getValue(); - else if (DefInit *DI = dyn_cast(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(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(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 @@ return *Intr; } + bool compareBy(Record *LHS, Record *RHS, const SearchIndex &Index); + bool isIntegral(Init *I) { return isa(I) || isIntrinsic(I); } - std::string searchableFieldType(Init *I) { - if (isa(I)) - return "const char *"; - else if (BitsInit *BI = dyn_cast(I)) { + std::string searchableFieldType(const GenericField &Field, TypeContext Ctx) { + if (isa(Field.RecType)) { + if (Ctx == TypeInStaticStruct) + return "const char *"; + if (Ctx == TypeInTempStruct) + return "std::string"; + return "StringRef"; + } else if (BitsRecTy *BI = dyn_cast(Field.RecType)) { unsigned NumBits = BI->getNumBits(); if (NumBits <= 8) NumBits = 8; @@ -104,243 +163,617 @@ 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 &Items, Record *InstanceClass, - raw_ostream &OS); - void - emitPrimaryTable(StringRef Name, std::vector &FieldNames, - std::vector &SearchFieldNames, - std::vector> &SearchTables, - std::vector &Items, raw_ostream &OS); - void emitSearchTable(StringRef Name, StringRef Field, - std::vector &SearchTable, - raw_ostream &OS); - void emitLookupDeclaration(StringRef Name, StringRef Field, Init *I, - raw_ostream &OS); - void emitLookupFunction(StringRef Name, StringRef Field, Init *I, + 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 + parseSearchIndex(GenericTable &Table, StringRef Name, + const std::vector &Key, bool EarlyOut); + void collectEnumEntries(GenericEnum &Enum, StringRef NameField, + StringRef ValueField, + const std::vector &Items); + void collectTableEntries(GenericTable &Table, + const std::vector &Items); }; } // End anonymous namespace. -/// Emit an enum providing symbolic access to some preferred field from -/// C++. -void SearchableTableEmitter::emitMappingEnum(std::vector &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 &FieldNames, - std::vector &SearchFieldNames, - std::vector> &SearchTables, - std::vector &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(Field.RecType) || isa(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(LHSI)->getDef(); + Record *RHSr = cast(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(LHSI)->getDef(); + auto RHSr = cast(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(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 &SearchTable, - raw_ostream &OS) { - OS << "const std::pair<" << searchableFieldType(SearchTable[0].first) - << ", int> " << Name << "sBy" << Field << "[] = {\n"; - - if (isa(SearchTable[0].first)) { - std::stable_sort(SearchTable.begin(), SearchTable.end(), - [this](const SearchTableEntry &LHS, - const SearchTableEntry &RHS) { - return getAsInt(cast(LHS.first)) < - getAsInt(cast(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 IndexRowsStorage; + ArrayRef 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> 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 &LHS, + const std::pair &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(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(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() ? &Table[Idx] : nullptr;\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(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(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 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> SearchTables; - std::vector 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 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(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 +SearchableTableEmitter::parseSearchIndex(GenericTable &Table, StringRef Name, + const std::vector &Key, + bool EarlyOut) { + auto Index = llvm::make_unique(); + 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(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 &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(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 &LHS, + const std::unique_ptr &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 &Items) { + for (auto EntryRec : Items) { + for (auto &Field : Table.Fields) { + auto TI = dyn_cast(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(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, 4> Tables; + DenseMap 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(); + Enum->Name = EnumRec->getName(); + Enum->PreprocessorGuard = EnumRec->getName().upper(); + + 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(); + Table->Name = TableRec->getName(); + Table->PreprocessorGuard = TableRec->getName().upper(); + Table->CppTypeName = TableRec->getValueAsString("CppTypeName"); + + std::vector 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 (auto 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 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(); + 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(); + 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 {