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/DenseMap.h"
17 #include "llvm/ADT/StringExtras.h"
18 #include "llvm/Support/Format.h"
19 #include "llvm/Support/MemoryBuffer.h"
20 #include "llvm/Support/SourceMgr.h"
21 #include "llvm/TableGen/Error.h"
22 #include "llvm/TableGen/Record.h"
23 #include "CodeGenIntrinsics.h"
24 #include <algorithm>
25 #include <string>
26 #include <vector>
27 using namespace llvm;
28 
29 #define DEBUG_TYPE "searchable-table-emitter"
30 
31 namespace {
32 
33 class SearchableTableEmitter {
34   RecordKeeper &Records;
35   DenseMap<Init *, std::unique_ptr<CodeGenIntrinsic>> Intrinsics;
36 
37 public:
38   SearchableTableEmitter(RecordKeeper &R) : Records(R) {}
39 
40   void run(raw_ostream &OS);
41 
42 private:
43   typedef std::pair<Init *, int> SearchTableEntry;
44 
45   int getAsInt(BitsInit *B) {
46     return cast<IntInit>(B->convertInitializerTo(IntRecTy::get()))->getValue();
47   }
48   int getInt(Record *R, StringRef Field) {
49     return getAsInt(R->getValueAsBitsInit(Field));
50   }
51 
52   std::string primaryRepresentation(Init *I) {
53     if (StringInit *SI = dyn_cast<StringInit>(I))
54       return SI->getAsString();
55     else if (BitsInit *BI = dyn_cast<BitsInit>(I))
56       return "0x" + utohexstr(getAsInt(BI));
57     else if (BitInit *BI = dyn_cast<BitInit>(I))
58       return BI->getValue() ? "true" : "false";
59     else if (CodeInit *CI = dyn_cast<CodeInit>(I))
60       return CI->getValue();
61     else if (DefInit *DI = dyn_cast<DefInit>(I)) {
62       if (DI->getDef()->isSubClassOf("Intrinsic"))
63         return "Intrinsic::" + getIntrinsic(I).EnumName;
64     }
65     PrintFatalError(SMLoc(),
66                     "invalid field type, expected: string, bits, bit or code");
67   }
68 
69   std::string searchRepresentation(Init *I) {
70     std::string PrimaryRep = primaryRepresentation(I);
71     if (!isa<StringInit>(I))
72       return PrimaryRep;
73     return StringRef(PrimaryRep).upper();
74   }
75 
76   bool isIntrinsic(Init *I) {
77     if (DefInit *DI = dyn_cast<DefInit>(I))
78       return DI->getDef()->isSubClassOf("Intrinsic");
79     return false;
80   }
81 
82   CodeGenIntrinsic &getIntrinsic(Init *I) {
83     std::unique_ptr<CodeGenIntrinsic> &Intr = Intrinsics[I];
84     if (!Intr)
85       Intr = make_unique<CodeGenIntrinsic>(cast<DefInit>(I)->getDef());
86     return *Intr;
87   }
88 
89   bool isIntegral(Init *I) {
90     return isa<BitsInit>(I) || isIntrinsic(I);
91   }
92 
93   std::string searchableFieldType(Init *I) {
94     if (isa<StringInit>(I))
95       return "const char *";
96     else if (BitsInit *BI = dyn_cast<BitsInit>(I)) {
97       unsigned NumBits = BI->getNumBits();
98       if (NumBits <= 8)
99         NumBits = 8;
100       else if (NumBits <= 16)
101         NumBits = 16;
102       else if (NumBits <= 32)
103         NumBits = 32;
104       else if (NumBits <= 64)
105         NumBits = 64;
106       else
107         PrintFatalError(SMLoc(), "bitfield too large to search");
108       return "uint" + utostr(NumBits) + "_t";
109     } else if (isIntrinsic(I))
110       return "unsigned";
111     PrintFatalError(SMLoc(), "Unknown type to search by");
112   }
113 
114   void emitMapping(Record *MappingDesc, raw_ostream &OS);
115   void emitMappingEnum(std::vector<Record *> &Items, Record *InstanceClass,
116                        raw_ostream &OS);
117   void
118   emitPrimaryTable(StringRef Name, std::vector<std::string> &FieldNames,
119                    std::vector<std::string> &SearchFieldNames,
120                    std::vector<std::vector<SearchTableEntry>> &SearchTables,
121                    std::vector<Record *> &Items, raw_ostream &OS);
122   void emitSearchTable(StringRef Name, StringRef Field,
123                        std::vector<SearchTableEntry> &SearchTable,
124                        raw_ostream &OS);
125   void emitLookupDeclaration(StringRef Name, StringRef Field, Init *I,
126                              raw_ostream &OS);
127   void emitLookupFunction(StringRef Name, StringRef Field, Init *I,
128                           raw_ostream &OS);
129 };
130 
131 } // End anonymous namespace.
132 
133 /// Emit an enum providing symbolic access to some preferred field from
134 /// C++.
135 void SearchableTableEmitter::emitMappingEnum(std::vector<Record *> &Items,
136                                              Record *InstanceClass,
137                                              raw_ostream &OS) {
138   StringRef EnumNameField = InstanceClass->getValueAsString("EnumNameField");
139   StringRef EnumValueField;
140   if (!InstanceClass->isValueUnset("EnumValueField"))
141     EnumValueField = InstanceClass->getValueAsString("EnumValueField");
142 
143   OS << "enum " << InstanceClass->getName() << "Values {\n";
144   for (auto Item : Items) {
145     OS << "  " << Item->getValueAsString(EnumNameField);
146     if (EnumValueField != StringRef())
147       OS << " = " << getInt(Item, EnumValueField);
148     OS << ",\n";
149   }
150   OS << "};\n\n";
151 }
152 
153 void SearchableTableEmitter::emitPrimaryTable(
154     StringRef Name, std::vector<std::string> &FieldNames,
155     std::vector<std::string> &SearchFieldNames,
156     std::vector<std::vector<SearchTableEntry>> &SearchTables,
157     std::vector<Record *> &Items, raw_ostream &OS) {
158   OS << "const " << Name << " " << Name << "sList[] = {\n";
159 
160   for (auto Item : Items) {
161     OS << "  { ";
162     for (unsigned i = 0; i < FieldNames.size(); ++i) {
163       OS << primaryRepresentation(Item->getValueInit(FieldNames[i]));
164       if (i != FieldNames.size() - 1)
165         OS << ", ";
166     }
167     OS << "},\n";
168   }
169   OS << "};\n\n";
170 }
171 
172 void SearchableTableEmitter::emitSearchTable(
173     StringRef Name, StringRef Field, std::vector<SearchTableEntry> &SearchTable,
174     raw_ostream &OS) {
175   OS << "const std::pair<" << searchableFieldType(SearchTable[0].first)
176      << ", int> " << Name << "sBy" << Field << "[] = {\n";
177 
178   if (isa<BitsInit>(SearchTable[0].first)) {
179     std::stable_sort(SearchTable.begin(), SearchTable.end(),
180                      [this](const SearchTableEntry &LHS,
181                             const SearchTableEntry &RHS) {
182                        return getAsInt(cast<BitsInit>(LHS.first)) <
183                               getAsInt(cast<BitsInit>(RHS.first));
184                      });
185   } else if (isIntrinsic(SearchTable[0].first)) {
186     std::stable_sort(SearchTable.begin(), SearchTable.end(),
187                      [this](const SearchTableEntry &LHS,
188                             const SearchTableEntry &RHS) {
189                        CodeGenIntrinsic &LHSi = getIntrinsic(LHS.first);
190                        CodeGenIntrinsic &RHSi = getIntrinsic(RHS.first);
191                        return std::tie(LHSi.TargetPrefix, LHSi.Name) <
192                               std::tie(RHSi.TargetPrefix, RHSi.Name);
193                      });
194   } else {
195     std::stable_sort(SearchTable.begin(), SearchTable.end(),
196                      [this](const SearchTableEntry &LHS,
197                             const SearchTableEntry &RHS) {
198                        return searchRepresentation(LHS.first) <
199                               searchRepresentation(RHS.first);
200                      });
201   }
202 
203   for (auto Entry : SearchTable) {
204     OS << "  { " << searchRepresentation(Entry.first) << ", " << Entry.second
205        << " },\n";
206   }
207   OS << "};\n\n";
208 }
209 
210 void SearchableTableEmitter::emitLookupFunction(StringRef Name, StringRef Field,
211                                                 Init *I, raw_ostream &OS) {
212   bool IsIntegral = isIntegral(I);
213   std::string FieldType = searchableFieldType(I);
214   std::string PairType = "std::pair<" + FieldType + ", int>";
215 
216   // const SysRegs *lookupSysRegByName(const char *Name) {
217   OS << "const " << Name << " *"
218      << "lookup" << Name << "By" << Field;
219   OS << "(" << (IsIntegral ? FieldType : "StringRef") << " " << Field
220      << ") {\n";
221 
222   if (IsIntegral) {
223     OS << "  auto CanonicalVal = " << Field << ";\n";
224     OS << " " << PairType << " Val = {CanonicalVal, 0};\n";
225   } else {
226     // Make sure the result is null terminated because it's going via "char *".
227     OS << "  std::string CanonicalVal = " << Field << ".upper();\n";
228     OS << "  " << PairType << " Val = {CanonicalVal.c_str(), 0};\n";
229   }
230 
231   OS << "  ArrayRef<" << PairType << "> Table(" << Name << "sBy" << Field
232      << ");\n";
233   OS << "  auto Idx = std::lower_bound(Table.begin(), Table.end(), Val";
234 
235   if (IsIntegral)
236     OS << ");\n";
237   else {
238     OS << ",\n                              ";
239     OS << "[](const " << PairType << " &LHS, const " << PairType
240        << " &RHS) {\n";
241     OS << "    return std::strcmp(LHS.first, RHS.first) < 0;\n";
242     OS << "  });\n\n";
243   }
244 
245   OS << "  if (Idx == Table.end() || CanonicalVal != Idx->first)\n";
246   OS << "    return nullptr;\n";
247 
248   OS << "  return &" << Name << "sList[Idx->second];\n";
249   OS << "}\n\n";
250 }
251 
252 void SearchableTableEmitter::emitLookupDeclaration(StringRef Name,
253                                                    StringRef Field, Init *I,
254                                                    raw_ostream &OS) {
255   bool IsIntegral = isIntegral(I);
256   std::string FieldType = searchableFieldType(I);
257   OS << "const " << Name << " *"
258      << "lookup" << Name << "By" << Field;
259   OS << "(" << (IsIntegral ? FieldType : "StringRef") << " " << Field
260      << ");\n\n";
261 }
262 
263 void SearchableTableEmitter::emitMapping(Record *InstanceClass,
264                                          raw_ostream &OS) {
265   StringRef TableName = InstanceClass->getName();
266   std::vector<Record *> Items = Records.getAllDerivedDefinitions(TableName);
267 
268   // Gather all the records we're going to need for this particular mapping.
269   std::vector<std::vector<SearchTableEntry>> SearchTables;
270   std::vector<std::string> SearchFieldNames;
271 
272   std::vector<std::string> FieldNames;
273   for (const RecordVal &Field : InstanceClass->getValues()) {
274     std::string FieldName = Field.getName();
275 
276     // Skip uninteresting fields: either built-in, special to us, or injected
277     // template parameters (if they contain a ':').
278     if (FieldName.find(':') != std::string::npos || FieldName == "NAME" ||
279         FieldName == "SearchableFields" || FieldName == "EnumNameField" ||
280         FieldName == "EnumValueField")
281       continue;
282 
283     FieldNames.push_back(FieldName);
284   }
285 
286   for (auto *Field : *InstanceClass->getValueAsListInit("SearchableFields")) {
287     SearchTables.emplace_back();
288     SearchFieldNames.push_back(Field->getAsUnquotedString());
289   }
290 
291   int Idx = 0;
292   for (Record *Item : Items) {
293     for (unsigned i = 0; i < SearchFieldNames.size(); ++i) {
294       Init *SearchVal = Item->getValueInit(SearchFieldNames[i]);
295       SearchTables[i].emplace_back(SearchVal, Idx);
296     }
297     ++Idx;
298   }
299 
300   OS << "#ifdef GET_" << TableName.upper() << "_DECL\n";
301   OS << "#undef GET_" << TableName.upper() << "_DECL\n";
302 
303   // Next emit the enum containing the top-level names for use in C++ code if
304   // requested
305   if (!InstanceClass->isValueUnset("EnumNameField")) {
306     emitMappingEnum(Items, InstanceClass, OS);
307   }
308 
309   // And the declarations for the functions that will perform lookup.
310   for (unsigned i = 0; i < SearchFieldNames.size(); ++i)
311     emitLookupDeclaration(TableName, SearchFieldNames[i],
312                           SearchTables[i][0].first, OS);
313 
314   OS << "#endif\n\n";
315 
316   OS << "#ifdef GET_" << TableName.upper() << "_IMPL\n";
317   OS << "#undef GET_" << TableName.upper() << "_IMPL\n";
318 
319   // The primary data table contains all the fields defined for this map.
320   emitPrimaryTable(TableName, FieldNames, SearchFieldNames, SearchTables, Items,
321                    OS);
322 
323   // Indexes are sorted "{ Thing, PrimaryIdx }" arrays, so that a binary
324   // search can be performed by "Thing".
325   for (unsigned i = 0; i < SearchTables.size(); ++i) {
326     emitSearchTable(TableName, SearchFieldNames[i], SearchTables[i], OS);
327     emitLookupFunction(TableName, SearchFieldNames[i], SearchTables[i][0].first,
328                        OS);
329   }
330 
331   OS << "#endif\n";
332 }
333 
334 void SearchableTableEmitter::run(raw_ostream &OS) {
335   // Tables are defined to be the direct descendents of "SearchableEntry".
336   Record *SearchableTable = Records.getClass("SearchableTable");
337   for (auto &NameRec : Records.getClasses()) {
338     Record *Class = NameRec.second.get();
339     if (Class->getSuperClasses().size() != 1 ||
340         !Class->isSubClassOf(SearchableTable))
341       continue;
342     emitMapping(Class, OS);
343   }
344 }
345 
346 namespace llvm {
347 
348 void EmitSearchableTables(RecordKeeper &RK, raw_ostream &OS) {
349   SearchableTableEmitter(RK).run(OS);
350 }
351 
352 } // End llvm namespace.
353