Home | History | Annotate | Download | only in TableGen 
      1 //===- SearchableTableEmitter.cpp - Generate efficiently searchable tables -==//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // This tablegen backend emits a generic array initialized by specified fields,
     11 // together with companion index tables and lookup functions (binary search,
     12 // currently).
     13 //
     14 //===----------------------------------------------------------------------===//
     15 
     16 #include "llvm/ADT/StringExtras.h"
     17 #include "llvm/Support/Format.h"
     18 #include "llvm/Support/MemoryBuffer.h"
     19 #include "llvm/Support/SourceMgr.h"
     20 #include "llvm/TableGen/Error.h"
     21 #include "llvm/TableGen/Record.h"
     22 #include <algorithm>
     23 #include <sstream>
     24 #include <string>
     25 #include <vector>
     26 using namespace llvm;
     27 
     28 #define DEBUG_TYPE "searchable-table-emitter"
     29 
     30 namespace {
     31 
     32 class SearchableTableEmitter {
     33   RecordKeeper &Records;
     34 
     35 public:
     36   SearchableTableEmitter(RecordKeeper &R) : Records(R) {}
     37 
     38   void run(raw_ostream &OS);
     39 
     40 private:
     41   typedef std::pair<Init *, int> SearchTableEntry;
     42 
     43   int getAsInt(BitsInit *B) {
     44     return cast<IntInit>(B->convertInitializerTo(IntRecTy::get()))->getValue();
     45   }
     46   int getInt(Record *R, StringRef Field) {
     47     return getAsInt(R->getValueAsBitsInit(Field));
     48   }
     49 
     50   std::string primaryRepresentation(Init *I) {
     51     if (StringInit *SI = dyn_cast<StringInit>(I))
     52       return SI->getAsString();
     53     else if (BitsInit *BI = dyn_cast<BitsInit>(I))
     54       return "0x" + utohexstr(getAsInt(BI));
     55     else if (BitInit *BI = dyn_cast<BitInit>(I))
     56       return BI->getValue() ? "true" : "false";
     57     else if (CodeInit *CI = dyn_cast<CodeInit>(I)) {
     58       return CI->getValue();
     59     }
     60     PrintFatalError(SMLoc(),
     61                     "invalid field type, expected: string, bits, bit or code");
     62   }
     63 
     64   std::string searchRepresentation(Init *I) {
     65     std::string PrimaryRep = primaryRepresentation(I);
     66     if (!isa<StringInit>(I))
     67       return PrimaryRep;
     68     return StringRef(PrimaryRep).upper();
     69   }
     70 
     71   std::string searchableFieldType(Init *I) {
     72     if (isa<StringInit>(I))
     73       return "const char *";
     74     else if (BitsInit *BI = dyn_cast<BitsInit>(I)) {
     75       unsigned NumBits = BI->getNumBits();
     76       if (NumBits <= 8)
     77         NumBits = 8;
     78       else if (NumBits <= 16)
     79         NumBits = 16;
     80       else if (NumBits <= 32)
     81         NumBits = 32;
     82       else if (NumBits <= 64)
     83         NumBits = 64;
     84       else
     85         PrintFatalError(SMLoc(), "bitfield too large to search");
     86       return "uint" + utostr(NumBits) + "_t";
     87     }
     88     PrintFatalError(SMLoc(), "Unknown type to search by");
     89   }
     90 
     91   void emitMapping(Record *MappingDesc, raw_ostream &OS);
     92   void emitMappingEnum(std::vector<Record *> &Items, Record *InstanceClass,
     93                        raw_ostream &OS);
     94   void
     95   emitPrimaryTable(StringRef Name, std::vector<std::string> &FieldNames,
     96                    std::vector<std::string> &SearchFieldNames,
     97                    std::vector<std::vector<SearchTableEntry>> &SearchTables,
     98                    std::vector<Record *> &Items, raw_ostream &OS);
     99   void emitSearchTable(StringRef Name, StringRef Field,
    100                        std::vector<SearchTableEntry> &SearchTable,
    101                        raw_ostream &OS);
    102   void emitLookupDeclaration(StringRef Name, StringRef Field, Init *I,
    103                              raw_ostream &OS);
    104   void emitLookupFunction(StringRef Name, StringRef Field, Init *I,
    105                           raw_ostream &OS);
    106 };
    107 
    108 } // End anonymous namespace.
    109 
    110 /// Emit an enum providing symbolic access to some preferred field from
    111 /// C++.
    112 void SearchableTableEmitter::emitMappingEnum(std::vector<Record *> &Items,
    113                                              Record *InstanceClass,
    114                                              raw_ostream &OS) {
    115   std::string EnumNameField = InstanceClass->getValueAsString("EnumNameField");
    116   std::string EnumValueField;
    117   if (!InstanceClass->isValueUnset("EnumValueField"))
    118     EnumValueField = InstanceClass->getValueAsString("EnumValueField");
    119 
    120   OS << "enum " << InstanceClass->getName() << "Values {\n";
    121   for (auto Item : Items) {
    122     OS << "  " << Item->getValueAsString(EnumNameField);
    123     if (EnumValueField != StringRef())
    124       OS << " = " << getInt(Item, EnumValueField);
    125     OS << ",\n";
    126   }
    127   OS << "};\n\n";
    128 }
    129 
    130 void SearchableTableEmitter::emitPrimaryTable(
    131     StringRef Name, std::vector<std::string> &FieldNames,
    132     std::vector<std::string> &SearchFieldNames,
    133     std::vector<std::vector<SearchTableEntry>> &SearchTables,
    134     std::vector<Record *> &Items, raw_ostream &OS) {
    135   OS << "const " << Name << " " << Name << "sList[] = {\n";
    136 
    137   for (auto Item : Items) {
    138     OS << "  { ";
    139     for (unsigned i = 0; i < FieldNames.size(); ++i) {
    140       OS << primaryRepresentation(Item->getValueInit(FieldNames[i]));
    141       if (i != FieldNames.size() - 1)
    142         OS << ", ";
    143     }
    144     OS << "},\n";
    145   }
    146   OS << "};\n\n";
    147 }
    148 
    149 void SearchableTableEmitter::emitSearchTable(
    150     StringRef Name, StringRef Field, std::vector<SearchTableEntry> &SearchTable,
    151     raw_ostream &OS) {
    152   OS << "const std::pair<" << searchableFieldType(SearchTable[0].first)
    153      << ", int> " << Name << "sBy" << Field << "[] = {\n";
    154 
    155   if (isa<BitsInit>(SearchTable[0].first)) {
    156     std::stable_sort(SearchTable.begin(), SearchTable.end(),
    157                      [this](const SearchTableEntry &LHS,
    158                             const SearchTableEntry &RHS) {
    159                        return getAsInt(cast<BitsInit>(LHS.first)) <
    160                               getAsInt(cast<BitsInit>(RHS.first));
    161                      });
    162   } else {
    163     std::stable_sort(SearchTable.begin(), SearchTable.end(),
    164                      [this](const SearchTableEntry &LHS,
    165                             const SearchTableEntry &RHS) {
    166                        return searchRepresentation(LHS.first) <
    167                               searchRepresentation(RHS.first);
    168                      });
    169   }
    170 
    171   for (auto Entry : SearchTable) {
    172     OS << "  { " << searchRepresentation(Entry.first) << ", " << Entry.second
    173        << " },\n";
    174   }
    175   OS << "};\n\n";
    176 }
    177 
    178 void SearchableTableEmitter::emitLookupFunction(StringRef Name, StringRef Field,
    179                                                 Init *I, raw_ostream &OS) {
    180   bool IsIntegral = isa<BitsInit>(I);
    181   std::string FieldType = searchableFieldType(I);
    182   std::string PairType = "std::pair<" + FieldType + ", int>";
    183 
    184   // const SysRegs *lookupSysRegByName(const char *Name) {
    185   OS << "const " << Name << " *"
    186      << "lookup" << Name << "By" << Field;
    187   OS << "(" << (IsIntegral ? FieldType : "StringRef") << " " << Field
    188      << ") {\n";
    189 
    190   if (IsIntegral) {
    191     OS << "  auto CanonicalVal = " << Field << ";\n";
    192     OS << " " << PairType << " Val = {CanonicalVal, 0};\n";
    193   } else {
    194     // Make sure the result is null terminated because it's going via "char *".
    195     OS << "  std::string CanonicalVal = " << Field << ".upper();\n";
    196     OS << "  " << PairType << " Val = {CanonicalVal.data(), 0};\n";
    197   }
    198 
    199   OS << "  ArrayRef<" << PairType << "> Table(" << Name << "sBy" << Field
    200      << ");\n";
    201   OS << "  auto Idx = std::lower_bound(Table.begin(), Table.end(), Val";
    202 
    203   if (IsIntegral)
    204     OS << ");\n";
    205   else {
    206     OS << ",\n                              ";
    207     OS << "[](const " << PairType << " &LHS, const " << PairType
    208        << " &RHS) {\n";
    209     OS << "    return StringRef(LHS.first) < StringRef(RHS.first);\n";
    210     OS << "  });\n\n";
    211   }
    212 
    213   OS << "  if (Idx == Table.end() || CanonicalVal != Idx->first)\n";
    214   OS << "    return nullptr;\n";
    215 
    216   OS << "  return &" << Name << "sList[Idx->second];\n";
    217   OS << "}\n\n";
    218 }
    219 
    220 void SearchableTableEmitter::emitLookupDeclaration(StringRef Name,
    221                                                    StringRef Field, Init *I,
    222                                                    raw_ostream &OS) {
    223   bool IsIntegral = isa<BitsInit>(I);
    224   std::string FieldType = searchableFieldType(I);
    225   OS << "const " << Name << " *"
    226      << "lookup" << Name << "By" << Field;
    227   OS << "(" << (IsIntegral ? FieldType : "StringRef") << " " << Field
    228      << ");\n\n";
    229 }
    230 
    231 void SearchableTableEmitter::emitMapping(Record *InstanceClass,
    232                                          raw_ostream &OS) {
    233   const std::string &TableName = InstanceClass->getName();
    234   std::vector<Record *> Items = Records.getAllDerivedDefinitions(TableName);
    235 
    236   // Gather all the records we're going to need for this particular mapping.
    237   std::vector<std::vector<SearchTableEntry>> SearchTables;
    238   std::vector<std::string> SearchFieldNames;
    239 
    240   std::vector<std::string> FieldNames;
    241   for (const RecordVal &Field : InstanceClass->getValues()) {
    242     std::string FieldName = Field.getName();
    243 
    244     // Skip uninteresting fields: either built-in, special to us, or injected
    245     // template parameters (if they contain a ':').
    246     if (FieldName.find(':') != std::string::npos || FieldName == "NAME" ||
    247         FieldName == "SearchableFields" || FieldName == "EnumNameField" ||
    248         FieldName == "EnumValueField")
    249       continue;
    250 
    251     FieldNames.push_back(FieldName);
    252   }
    253 
    254   for (auto *Field : *InstanceClass->getValueAsListInit("SearchableFields")) {
    255     SearchTables.emplace_back();
    256     SearchFieldNames.push_back(Field->getAsUnquotedString());
    257   }
    258 
    259   int Idx = 0;
    260   for (Record *Item : Items) {
    261     for (unsigned i = 0; i < SearchFieldNames.size(); ++i) {
    262       Init *SearchVal = Item->getValueInit(SearchFieldNames[i]);
    263       SearchTables[i].emplace_back(SearchVal, Idx);
    264     }
    265     ++Idx;
    266   }
    267 
    268   OS << "#ifdef GET_" << StringRef(TableName).upper() << "_DECL\n";
    269   OS << "#undef GET_" << StringRef(TableName).upper() << "_DECL\n";
    270 
    271   // Next emit the enum containing the top-level names for use in C++ code if
    272   // requested
    273   if (!InstanceClass->isValueUnset("EnumNameField")) {
    274     emitMappingEnum(Items, InstanceClass, OS);
    275   }
    276 
    277   // And the declarations for the functions that will perform lookup.
    278   for (unsigned i = 0; i < SearchFieldNames.size(); ++i)
    279     emitLookupDeclaration(TableName, SearchFieldNames[i],
    280                           SearchTables[i][0].first, OS);
    281 
    282   OS << "#endif\n\n";
    283 
    284   OS << "#ifdef GET_" << StringRef(TableName).upper() << "_IMPL\n";
    285   OS << "#undef GET_" << StringRef(TableName).upper() << "_IMPL\n";
    286 
    287   // The primary data table contains all the fields defined for this map.
    288   emitPrimaryTable(TableName, FieldNames, SearchFieldNames, SearchTables, Items,
    289                    OS);
    290 
    291   // Indexes are sorted "{ Thing, PrimaryIdx }" arrays, so that a binary
    292   // search can be performed by "Thing".
    293   for (unsigned i = 0; i < SearchTables.size(); ++i) {
    294     emitSearchTable(TableName, SearchFieldNames[i], SearchTables[i], OS);
    295     emitLookupFunction(TableName, SearchFieldNames[i], SearchTables[i][0].first,
    296                        OS);
    297   }
    298 
    299   OS << "#endif\n";
    300 }
    301 
    302 void SearchableTableEmitter::run(raw_ostream &OS) {
    303   // Tables are defined to be the direct descendents of "SearchableEntry".
    304   Record *SearchableTable = Records.getClass("SearchableTable");
    305   for (auto &NameRec : Records.getClasses()) {
    306     Record *Class = NameRec.second.get();
    307     if (Class->getSuperClasses().size() != 1 ||
    308         !Class->isSubClassOf(SearchableTable))
    309       continue;
    310     emitMapping(Class, OS);
    311   }
    312 }
    313 
    314 namespace llvm {
    315 
    316 void EmitSearchableTables(RecordKeeper &RK, raw_ostream &OS) {
    317   SearchableTableEmitter(RK).run(OS);
    318 }
    319 
    320 } // End llvm namespace.
    321