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 <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.c_str(), 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 std::strcmp(LHS.first, RHS.first) < 0;\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.