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.
320