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