• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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:
SearchableTableEmitter(RecordKeeper & R)36   SearchableTableEmitter(RecordKeeper &R) : Records(R) {}
37 
38   void run(raw_ostream &OS);
39 
40 private:
41   typedef std::pair<Init *, int> SearchTableEntry;
42 
getAsInt(BitsInit * B)43   int getAsInt(BitsInit *B) {
44     return cast<IntInit>(B->convertInitializerTo(IntRecTy::get()))->getValue();
45   }
getInt(Record * R,StringRef Field)46   int getInt(Record *R, StringRef Field) {
47     return getAsInt(R->getValueAsBitsInit(Field));
48   }
49 
primaryRepresentation(Init * I)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 
searchRepresentation(Init * I)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 
searchableFieldType(Init * I)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++.
emitMappingEnum(std::vector<Record * > & Items,Record * InstanceClass,raw_ostream & OS)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 
emitPrimaryTable(StringRef Name,std::vector<std::string> & FieldNames,std::vector<std::string> & SearchFieldNames,std::vector<std::vector<SearchTableEntry>> & SearchTables,std::vector<Record * > & Items,raw_ostream & OS)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 
emitSearchTable(StringRef Name,StringRef Field,std::vector<SearchTableEntry> & SearchTable,raw_ostream & OS)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 
emitLookupFunction(StringRef Name,StringRef Field,Init * I,raw_ostream & OS)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 
emitLookupDeclaration(StringRef Name,StringRef Field,Init * I,raw_ostream & OS)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 
emitMapping(Record * InstanceClass,raw_ostream & OS)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 
run(raw_ostream & OS)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 
EmitSearchableTables(RecordKeeper & RK,raw_ostream & OS)316 void EmitSearchableTables(RecordKeeper &RK, raw_ostream &OS) {
317   SearchableTableEmitter(RK).run(OS);
318 }
319 
320 } // End llvm namespace.
321