contrib/llvm/utils/TableGen/SearchableTableEmitter.cpp

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