1 //===- SearchableTableEmitter.cpp - Generate efficiently searchable tables -==//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This tablegen backend emits a generic array initialized by specified fields,
11 // together with companion index tables and lookup functions (binary search,
14 //===----------------------------------------------------------------------===//
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"
28 #define DEBUG_TYPE "searchable-table-emitter"
32 class SearchableTableEmitter {
33 RecordKeeper &Records;
36 SearchableTableEmitter(RecordKeeper &R) : Records(R) {}
38 void run(raw_ostream &OS);
41 typedef std::pair<Init *, int> SearchTableEntry;
43 int getAsInt(BitsInit *B) {
44 return cast<IntInit>(B->convertInitializerTo(IntRecTy::get()))->getValue();
46 int getInt(Record *R, StringRef Field) {
47 return getAsInt(R->getValueAsBitsInit(Field));
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();
60 PrintFatalError(SMLoc(),
61 "invalid field type, expected: string, bits, bit or code");
64 std::string searchRepresentation(Init *I) {
65 std::string PrimaryRep = primaryRepresentation(I);
66 if (!isa<StringInit>(I))
68 return StringRef(PrimaryRep).upper();
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();
78 else if (NumBits <= 16)
80 else if (NumBits <= 32)
82 else if (NumBits <= 64)
85 PrintFatalError(SMLoc(), "bitfield too large to search");
86 return "uint" + utostr(NumBits) + "_t";
88 PrintFatalError(SMLoc(), "Unknown type to search by");
91 void emitMapping(Record *MappingDesc, raw_ostream &OS);
92 void emitMappingEnum(std::vector<Record *> &Items, Record *InstanceClass,
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,
102 void emitLookupDeclaration(StringRef Name, StringRef Field, Init *I,
104 void emitLookupFunction(StringRef Name, StringRef Field, Init *I,
108 } // End anonymous namespace.
110 /// Emit an enum providing symbolic access to some preferred field from
112 void SearchableTableEmitter::emitMappingEnum(std::vector<Record *> &Items,
113 Record *InstanceClass,
115 std::string EnumNameField = InstanceClass->getValueAsString("EnumNameField");
116 std::string EnumValueField;
117 if (!InstanceClass->isValueUnset("EnumValueField"))
118 EnumValueField = InstanceClass->getValueAsString("EnumValueField");
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);
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";
137 for (auto Item : Items) {
139 for (unsigned i = 0; i < FieldNames.size(); ++i) {
140 OS << primaryRepresentation(Item->getValueInit(FieldNames[i]));
141 if (i != FieldNames.size() - 1)
149 void SearchableTableEmitter::emitSearchTable(
150 StringRef Name, StringRef Field, std::vector<SearchTableEntry> &SearchTable,
152 OS << "const std::pair<" << searchableFieldType(SearchTable[0].first)
153 << ", int> " << Name << "sBy" << Field << "[] = {\n";
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));
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);
171 for (auto Entry : SearchTable) {
172 OS << " { " << searchRepresentation(Entry.first) << ", " << Entry.second
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>";
184 // const SysRegs *lookupSysRegByName(const char *Name) {
185 OS << "const " << Name << " *"
186 << "lookup" << Name << "By" << Field;
187 OS << "(" << (IsIntegral ? FieldType : "StringRef") << " " << Field
191 OS << " auto CanonicalVal = " << Field << ";\n";
192 OS << " " << PairType << " Val = {CanonicalVal, 0};\n";
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";
199 OS << " ArrayRef<" << PairType << "> Table(" << Name << "sBy" << Field
201 OS << " auto Idx = std::lower_bound(Table.begin(), Table.end(), Val";
207 OS << "[](const " << PairType << " &LHS, const " << PairType
209 OS << " return StringRef(LHS.first) < StringRef(RHS.first);\n";
213 OS << " if (Idx == Table.end() || CanonicalVal != Idx->first)\n";
214 OS << " return nullptr;\n";
216 OS << " return &" << Name << "sList[Idx->second];\n";
220 void SearchableTableEmitter::emitLookupDeclaration(StringRef Name,
221 StringRef Field, Init *I,
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
231 void SearchableTableEmitter::emitMapping(Record *InstanceClass,
233 const std::string &TableName = InstanceClass->getName();
234 std::vector<Record *> Items = Records.getAllDerivedDefinitions(TableName);
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;
240 std::vector<std::string> FieldNames;
241 for (const RecordVal &Field : InstanceClass->getValues()) {
242 std::string FieldName = Field.getName();
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")
251 FieldNames.push_back(FieldName);
254 for (auto *Field : *InstanceClass->getValueAsListInit("SearchableFields")) {
255 SearchTables.emplace_back();
256 SearchFieldNames.push_back(Field->getAsUnquotedString());
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);
268 OS << "#ifdef GET_" << StringRef(TableName).upper() << "_DECL\n";
269 OS << "#undef GET_" << StringRef(TableName).upper() << "_DECL\n";
271 // Next emit the enum containing the top-level names for use in C++ code if
273 if (!InstanceClass->isValueUnset("EnumNameField")) {
274 emitMappingEnum(Items, InstanceClass, OS);
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);
284 OS << "#ifdef GET_" << StringRef(TableName).upper() << "_IMPL\n";
285 OS << "#undef GET_" << StringRef(TableName).upper() << "_IMPL\n";
287 // The primary data table contains all the fields defined for this map.
288 emitPrimaryTable(TableName, FieldNames, SearchFieldNames, SearchTables, Items,
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,
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))
310 emitMapping(Class, OS);
316 void EmitSearchableTables(RecordKeeper &RK, raw_ostream &OS) {
317 SearchableTableEmitter(RK).run(OS);
320 } // End llvm namespace.