SearchableTableEmitter.cpp revision 303231 
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>
26using namespace llvm;
27
28#define DEBUG_TYPE "searchable-table-emitter"
29
30namespace {
31
32class SearchableTableEmitter {
33  RecordKeeper &Records;
34
35public:
36  SearchableTableEmitter(RecordKeeper &R) : Records(R) {}
37
38  void run(raw_ostream &OS);
39
40private:
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++.
112void 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
130void 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
149void 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
178void 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
220void 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
231void 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
302void 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
314namespace llvm {
315
316void EmitSearchableTables(RecordKeeper &RK, raw_ostream &OS) {
317  SearchableTableEmitter(RK).run(OS);
318}
319
320} // End llvm namespace.
321