File: | utils/TableGen/SearchableTableEmitter.cpp |
Warning: | line 614, column 27 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
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 <set> | |||
26 | #include <string> | |||
27 | #include <vector> | |||
28 | ||||
29 | using namespace llvm; | |||
30 | ||||
31 | #define DEBUG_TYPE"searchable-table-emitter" "searchable-table-emitter" | |||
32 | ||||
33 | namespace { | |||
34 | ||||
35 | struct GenericTable; | |||
36 | ||||
37 | int getAsInt(Init *B) { | |||
38 | return cast<IntInit>(B->convertInitializerTo(IntRecTy::get()))->getValue(); | |||
39 | } | |||
40 | int getInt(Record *R, StringRef Field) { | |||
41 | return getAsInt(R->getValueInit(Field)); | |||
42 | } | |||
43 | ||||
44 | struct GenericEnum { | |||
45 | using Entry = std::pair<StringRef, int64_t>; | |||
46 | ||||
47 | std::string Name; | |||
48 | Record *Class; | |||
49 | std::string PreprocessorGuard; | |||
50 | std::vector<std::unique_ptr<Entry>> Entries; | |||
51 | DenseMap<Record *, Entry *> EntryMap; | |||
52 | }; | |||
53 | ||||
54 | struct GenericField { | |||
55 | std::string Name; | |||
56 | RecTy *RecType = nullptr; | |||
57 | bool IsIntrinsic = false; | |||
58 | bool IsInstruction = false; | |||
59 | GenericEnum *Enum = nullptr; | |||
60 | ||||
61 | GenericField(StringRef Name) : Name(Name) {} | |||
62 | }; | |||
63 | ||||
64 | struct SearchIndex { | |||
65 | std::string Name; | |||
66 | SmallVector<GenericField, 1> Fields; | |||
67 | bool EarlyOut; | |||
68 | }; | |||
69 | ||||
70 | struct GenericTable { | |||
71 | std::string Name; | |||
72 | std::string PreprocessorGuard; | |||
73 | std::string CppTypeName; | |||
74 | SmallVector<GenericField, 2> Fields; | |||
75 | std::vector<Record *> Entries; | |||
76 | ||||
77 | std::unique_ptr<SearchIndex> PrimaryKey; | |||
78 | SmallVector<std::unique_ptr<SearchIndex>, 2> Indices; | |||
79 | ||||
80 | const GenericField *getFieldByName(StringRef Name) const { | |||
81 | for (const auto &Field : Fields) { | |||
82 | if (Name == Field.Name) | |||
83 | return &Field; | |||
84 | } | |||
85 | return nullptr; | |||
86 | } | |||
87 | }; | |||
88 | ||||
89 | class SearchableTableEmitter { | |||
90 | RecordKeeper &Records; | |||
91 | DenseMap<Init *, std::unique_ptr<CodeGenIntrinsic>> Intrinsics; | |||
92 | std::vector<std::unique_ptr<GenericEnum>> Enums; | |||
93 | DenseMap<Record *, GenericEnum *> EnumMap; | |||
94 | std::set<std::string> PreprocessorGuards; | |||
95 | ||||
96 | public: | |||
97 | SearchableTableEmitter(RecordKeeper &R) : Records(R) {} | |||
98 | ||||
99 | void run(raw_ostream &OS); | |||
100 | ||||
101 | private: | |||
102 | typedef std::pair<Init *, int> SearchTableEntry; | |||
103 | ||||
104 | enum TypeContext { | |||
105 | TypeInStaticStruct, | |||
106 | TypeInTempStruct, | |||
107 | TypeInArgument, | |||
108 | }; | |||
109 | ||||
110 | std::string primaryRepresentation(const GenericField &Field, Init *I) { | |||
111 | if (StringInit *SI = dyn_cast<StringInit>(I)) | |||
112 | return SI->getAsString(); | |||
113 | else if (BitsInit *BI = dyn_cast<BitsInit>(I)) | |||
114 | return "0x" + utohexstr(getAsInt(BI)); | |||
115 | else if (BitInit *BI = dyn_cast<BitInit>(I)) | |||
116 | return BI->getValue() ? "true" : "false"; | |||
117 | else if (CodeInit *CI = dyn_cast<CodeInit>(I)) | |||
118 | return CI->getValue(); | |||
119 | else if (Field.IsIntrinsic) | |||
120 | return "Intrinsic::" + getIntrinsic(I).EnumName; | |||
121 | else if (Field.IsInstruction) | |||
122 | return I->getAsString(); | |||
123 | else if (Field.Enum) | |||
124 | return Field.Enum->EntryMap[cast<DefInit>(I)->getDef()]->first; | |||
125 | PrintFatalError(Twine("invalid field type for field '") + Field.Name + | |||
126 | "', expected: string, bits, bit or code"); | |||
127 | } | |||
128 | ||||
129 | bool isIntrinsic(Init *I) { | |||
130 | if (DefInit *DI = dyn_cast<DefInit>(I)) | |||
131 | return DI->getDef()->isSubClassOf("Intrinsic"); | |||
132 | return false; | |||
133 | } | |||
134 | ||||
135 | CodeGenIntrinsic &getIntrinsic(Init *I) { | |||
136 | std::unique_ptr<CodeGenIntrinsic> &Intr = Intrinsics[I]; | |||
137 | if (!Intr) | |||
138 | Intr = make_unique<CodeGenIntrinsic>(cast<DefInit>(I)->getDef()); | |||
139 | return *Intr; | |||
140 | } | |||
141 | ||||
142 | bool compareBy(Record *LHS, Record *RHS, const SearchIndex &Index); | |||
143 | ||||
144 | bool isIntegral(Init *I) { | |||
145 | return isa<BitsInit>(I) || isIntrinsic(I); | |||
146 | } | |||
147 | ||||
148 | std::string searchableFieldType(const GenericField &Field, TypeContext Ctx) { | |||
149 | if (isa<StringRecTy>(Field.RecType)) { | |||
150 | if (Ctx == TypeInStaticStruct) | |||
151 | return "const char *"; | |||
152 | if (Ctx == TypeInTempStruct) | |||
153 | return "std::string"; | |||
154 | return "StringRef"; | |||
155 | } else if (BitsRecTy *BI = dyn_cast<BitsRecTy>(Field.RecType)) { | |||
156 | unsigned NumBits = BI->getNumBits(); | |||
157 | if (NumBits <= 8) | |||
158 | return "uint8_t"; | |||
159 | if (NumBits <= 16) | |||
160 | return "uint16_t"; | |||
161 | if (NumBits <= 32) | |||
162 | return "uint32_t"; | |||
163 | if (NumBits <= 64) | |||
164 | return "uint64_t"; | |||
165 | PrintFatalError(Twine("bitfield '") + Field.Name + | |||
166 | "' too large to search"); | |||
167 | } else if (Field.Enum || Field.IsIntrinsic || Field.IsInstruction) | |||
168 | return "unsigned"; | |||
169 | PrintFatalError(Twine("Field '") + Field.Name + "' has unknown type '" + | |||
170 | Field.RecType->getAsString() + "' to search by"); | |||
171 | } | |||
172 | ||||
173 | void emitGenericTable(const GenericTable &Table, raw_ostream &OS); | |||
174 | void emitGenericEnum(const GenericEnum &Enum, raw_ostream &OS); | |||
175 | void emitLookupDeclaration(const GenericTable &Table, | |||
176 | const SearchIndex &Index, raw_ostream &OS); | |||
177 | void emitLookupFunction(const GenericTable &Table, const SearchIndex &Index, | |||
178 | bool IsPrimary, raw_ostream &OS); | |||
179 | void emitIfdef(StringRef Guard, raw_ostream &OS); | |||
180 | ||||
181 | bool parseFieldType(GenericField &Field, Init *II); | |||
182 | std::unique_ptr<SearchIndex> | |||
183 | parseSearchIndex(GenericTable &Table, StringRef Name, | |||
184 | const std::vector<StringRef> &Key, bool EarlyOut); | |||
185 | void collectEnumEntries(GenericEnum &Enum, StringRef NameField, | |||
186 | StringRef ValueField, | |||
187 | const std::vector<Record *> &Items); | |||
188 | void collectTableEntries(GenericTable &Table, | |||
189 | const std::vector<Record *> &Items); | |||
190 | }; | |||
191 | ||||
192 | } // End anonymous namespace. | |||
193 | ||||
194 | // For search indices that consists of a single field whose numeric value is | |||
195 | // known, return that numeric value. | |||
196 | static int64_t getNumericKey(const SearchIndex &Index, Record *Rec) { | |||
197 | assert(Index.Fields.size() == 1)((Index.Fields.size() == 1) ? static_cast<void> (0) : __assert_fail ("Index.Fields.size() == 1", "/build/llvm-toolchain-snapshot-8~svn350071/utils/TableGen/SearchableTableEmitter.cpp" , 197, __PRETTY_FUNCTION__)); | |||
198 | ||||
199 | if (Index.Fields[0].Enum) { | |||
200 | Record *EnumEntry = Rec->getValueAsDef(Index.Fields[0].Name); | |||
201 | return Index.Fields[0].Enum->EntryMap[EnumEntry]->second; | |||
202 | } | |||
203 | ||||
204 | return getInt(Rec, Index.Fields[0].Name); | |||
205 | } | |||
206 | ||||
207 | /// Less-than style comparison between \p LHS and \p RHS according to the | |||
208 | /// key of \p Index. | |||
209 | bool SearchableTableEmitter::compareBy(Record *LHS, Record *RHS, | |||
210 | const SearchIndex &Index) { | |||
211 | for (const auto &Field : Index.Fields) { | |||
212 | Init *LHSI = LHS->getValueInit(Field.Name); | |||
213 | Init *RHSI = RHS->getValueInit(Field.Name); | |||
214 | ||||
215 | if (isa<BitsRecTy>(Field.RecType) || isa<IntRecTy>(Field.RecType)) { | |||
216 | int64_t LHSi = getAsInt(LHSI); | |||
217 | int64_t RHSi = getAsInt(RHSI); | |||
218 | if (LHSi < RHSi) | |||
219 | return true; | |||
220 | if (LHSi > RHSi) | |||
221 | return false; | |||
222 | } else if (Field.IsIntrinsic) { | |||
223 | CodeGenIntrinsic &LHSi = getIntrinsic(LHSI); | |||
224 | CodeGenIntrinsic &RHSi = getIntrinsic(RHSI); | |||
225 | if (std::tie(LHSi.TargetPrefix, LHSi.Name) < | |||
226 | std::tie(RHSi.TargetPrefix, RHSi.Name)) | |||
227 | return true; | |||
228 | if (std::tie(LHSi.TargetPrefix, LHSi.Name) > | |||
229 | std::tie(RHSi.TargetPrefix, RHSi.Name)) | |||
230 | return false; | |||
231 | } else if (Field.IsInstruction) { | |||
232 | // This does not correctly compare the predefined instructions! | |||
233 | Record *LHSr = cast<DefInit>(LHSI)->getDef(); | |||
234 | Record *RHSr = cast<DefInit>(RHSI)->getDef(); | |||
235 | ||||
236 | bool LHSpseudo = LHSr->getValueAsBit("isPseudo"); | |||
237 | bool RHSpseudo = RHSr->getValueAsBit("isPseudo"); | |||
238 | if (LHSpseudo && !RHSpseudo) | |||
239 | return true; | |||
240 | if (!LHSpseudo && RHSpseudo) | |||
241 | return false; | |||
242 | ||||
243 | int comp = LHSr->getName().compare(RHSr->getName()); | |||
244 | if (comp < 0) | |||
245 | return true; | |||
246 | if (comp > 0) | |||
247 | return false; | |||
248 | } else if (Field.Enum) { | |||
249 | auto LHSr = cast<DefInit>(LHSI)->getDef(); | |||
250 | auto RHSr = cast<DefInit>(RHSI)->getDef(); | |||
251 | int64_t LHSv = Field.Enum->EntryMap[LHSr]->second; | |||
252 | int64_t RHSv = Field.Enum->EntryMap[RHSr]->second; | |||
253 | if (LHSv < RHSv) | |||
254 | return true; | |||
255 | if (LHSv > RHSv) | |||
256 | return false; | |||
257 | } else { | |||
258 | std::string LHSs = primaryRepresentation(Field, LHSI); | |||
259 | std::string RHSs = primaryRepresentation(Field, RHSI); | |||
260 | ||||
261 | if (isa<StringRecTy>(Field.RecType)) { | |||
262 | LHSs = StringRef(LHSs).upper(); | |||
263 | RHSs = StringRef(RHSs).upper(); | |||
264 | } | |||
265 | ||||
266 | int comp = LHSs.compare(RHSs); | |||
267 | if (comp < 0) | |||
268 | return true; | |||
269 | if (comp > 0) | |||
270 | return false; | |||
271 | } | |||
272 | } | |||
273 | return false; | |||
274 | } | |||
275 | ||||
276 | void SearchableTableEmitter::emitIfdef(StringRef Guard, raw_ostream &OS) { | |||
277 | OS << "#ifdef " << Guard << "\n"; | |||
278 | PreprocessorGuards.insert(Guard); | |||
279 | } | |||
280 | ||||
281 | /// Emit a generic enum. | |||
282 | void SearchableTableEmitter::emitGenericEnum(const GenericEnum &Enum, | |||
283 | raw_ostream &OS) { | |||
284 | emitIfdef((Twine("GET_") + Enum.PreprocessorGuard + "_DECL").str(), OS); | |||
285 | ||||
286 | OS << "enum " << Enum.Name << " {\n"; | |||
287 | for (const auto &Entry : Enum.Entries) | |||
288 | OS << " " << Entry->first << " = " << Entry->second << ",\n"; | |||
289 | OS << "};\n"; | |||
290 | ||||
291 | OS << "#endif\n\n"; | |||
292 | } | |||
293 | ||||
294 | void SearchableTableEmitter::emitLookupFunction(const GenericTable &Table, | |||
295 | const SearchIndex &Index, | |||
296 | bool IsPrimary, | |||
297 | raw_ostream &OS) { | |||
298 | OS << "\n"; | |||
299 | emitLookupDeclaration(Table, Index, OS); | |||
300 | OS << " {\n"; | |||
301 | ||||
302 | std::vector<Record *> IndexRowsStorage; | |||
303 | ArrayRef<Record *> IndexRows; | |||
304 | StringRef IndexTypeName; | |||
305 | StringRef IndexName; | |||
306 | ||||
307 | if (IsPrimary) { | |||
308 | IndexTypeName = Table.CppTypeName; | |||
309 | IndexName = Table.Name; | |||
310 | IndexRows = Table.Entries; | |||
311 | } else { | |||
312 | OS << " struct IndexType {\n"; | |||
313 | for (const auto &Field : Index.Fields) { | |||
314 | OS << " " << searchableFieldType(Field, TypeInStaticStruct) << " " | |||
315 | << Field.Name << ";\n"; | |||
316 | } | |||
317 | OS << " unsigned _index;\n"; | |||
318 | OS << " };\n"; | |||
319 | ||||
320 | OS << " static const struct IndexType Index[] = {\n"; | |||
321 | ||||
322 | std::vector<std::pair<Record *, unsigned>> Entries; | |||
323 | Entries.reserve(Table.Entries.size()); | |||
324 | for (unsigned i = 0; i < Table.Entries.size(); ++i) | |||
325 | Entries.emplace_back(Table.Entries[i], i); | |||
326 | ||||
327 | std::stable_sort(Entries.begin(), Entries.end(), | |||
328 | [&](const std::pair<Record *, unsigned> &LHS, | |||
329 | const std::pair<Record *, unsigned> &RHS) { | |||
330 | return compareBy(LHS.first, RHS.first, Index); | |||
331 | }); | |||
332 | ||||
333 | IndexRowsStorage.reserve(Entries.size()); | |||
334 | for (const auto &Entry : Entries) { | |||
335 | IndexRowsStorage.push_back(Entry.first); | |||
336 | ||||
337 | OS << " { "; | |||
338 | bool NeedComma = false; | |||
339 | for (const auto &Field : Index.Fields) { | |||
340 | if (NeedComma) | |||
341 | OS << ", "; | |||
342 | NeedComma = true; | |||
343 | ||||
344 | std::string Repr = | |||
345 | primaryRepresentation(Field, Entry.first->getValueInit(Field.Name)); | |||
346 | if (isa<StringRecTy>(Field.RecType)) | |||
347 | Repr = StringRef(Repr).upper(); | |||
348 | OS << Repr; | |||
349 | } | |||
350 | OS << ", " << Entry.second << " },\n"; | |||
351 | } | |||
352 | ||||
353 | OS << " };\n\n"; | |||
354 | ||||
355 | IndexTypeName = "IndexType"; | |||
356 | IndexName = "Index"; | |||
357 | IndexRows = IndexRowsStorage; | |||
358 | } | |||
359 | ||||
360 | bool IsContiguous = false; | |||
361 | ||||
362 | if (Index.Fields.size() == 1 && | |||
363 | (Index.Fields[0].Enum || isa<BitsRecTy>(Index.Fields[0].RecType))) { | |||
364 | IsContiguous = true; | |||
365 | for (unsigned i = 0; i < IndexRows.size(); ++i) { | |||
366 | if (getNumericKey(Index, IndexRows[i]) != i) { | |||
367 | IsContiguous = false; | |||
368 | break; | |||
369 | } | |||
370 | } | |||
371 | } | |||
372 | ||||
373 | if (IsContiguous) { | |||
374 | OS << " auto Table = makeArrayRef(" << IndexName << ");\n"; | |||
375 | OS << " size_t Idx = " << Index.Fields[0].Name << ";\n"; | |||
376 | OS << " return Idx >= Table.size() ? nullptr : "; | |||
377 | if (IsPrimary) | |||
378 | OS << "&Table[Idx]"; | |||
379 | else | |||
380 | OS << "&" << Table.Name << "[Table[Idx]._index]"; | |||
381 | OS << ";\n"; | |||
382 | OS << "}\n"; | |||
383 | return; | |||
384 | } | |||
385 | ||||
386 | if (Index.EarlyOut) { | |||
387 | const GenericField &Field = Index.Fields[0]; | |||
388 | std::string FirstRepr = | |||
389 | primaryRepresentation(Field, IndexRows[0]->getValueInit(Field.Name)); | |||
390 | std::string LastRepr = primaryRepresentation( | |||
391 | Field, IndexRows.back()->getValueInit(Field.Name)); | |||
392 | OS << " if ((" << Field.Name << " < " << FirstRepr << ") ||\n"; | |||
393 | OS << " (" << Field.Name << " > " << LastRepr << "))\n"; | |||
394 | OS << " return nullptr;\n\n"; | |||
395 | } | |||
396 | ||||
397 | OS << " struct KeyType {\n"; | |||
398 | for (const auto &Field : Index.Fields) { | |||
399 | OS << " " << searchableFieldType(Field, TypeInTempStruct) << " " | |||
400 | << Field.Name << ";\n"; | |||
401 | } | |||
402 | OS << " };\n"; | |||
403 | OS << " KeyType Key = { "; | |||
404 | bool NeedComma = false; | |||
405 | for (const auto &Field : Index.Fields) { | |||
406 | if (NeedComma) | |||
407 | OS << ", "; | |||
408 | NeedComma = true; | |||
409 | ||||
410 | OS << Field.Name; | |||
411 | if (isa<StringRecTy>(Field.RecType)) { | |||
412 | OS << ".upper()"; | |||
413 | if (IsPrimary) | |||
414 | PrintFatalError(Twine("Use a secondary index for case-insensitive " | |||
415 | "comparison of field '") + | |||
416 | Field.Name + "' in table '" + Table.Name + "'"); | |||
417 | } | |||
418 | } | |||
419 | OS << " };\n"; | |||
420 | ||||
421 | OS << " auto Table = makeArrayRef(" << IndexName << ");\n"; | |||
422 | OS << " auto Idx = std::lower_bound(Table.begin(), Table.end(), Key,\n"; | |||
423 | OS << " [](const " << IndexTypeName << " &LHS, const KeyType &RHS) {\n"; | |||
424 | ||||
425 | for (const auto &Field : Index.Fields) { | |||
426 | if (isa<StringRecTy>(Field.RecType)) { | |||
427 | OS << " int Cmp" << Field.Name << " = StringRef(LHS." << Field.Name | |||
428 | << ").compare(RHS." << Field.Name << ");\n"; | |||
429 | OS << " if (Cmp" << Field.Name << " < 0) return true;\n"; | |||
430 | OS << " if (Cmp" << Field.Name << " > 0) return false;\n"; | |||
431 | } else if (Field.Enum) { | |||
432 | // Explicitly cast to unsigned, because the signedness of enums is | |||
433 | // compiler-dependent. | |||
434 | OS << " if ((unsigned)LHS." << Field.Name << " < (unsigned)RHS." | |||
435 | << Field.Name << ")\n"; | |||
436 | OS << " return true;\n"; | |||
437 | OS << " if ((unsigned)LHS." << Field.Name << " > (unsigned)RHS." | |||
438 | << Field.Name << ")\n"; | |||
439 | OS << " return false;\n"; | |||
440 | } else { | |||
441 | OS << " if (LHS." << Field.Name << " < RHS." << Field.Name << ")\n"; | |||
442 | OS << " return true;\n"; | |||
443 | OS << " if (LHS." << Field.Name << " > RHS." << Field.Name << ")\n"; | |||
444 | OS << " return false;\n"; | |||
445 | } | |||
446 | } | |||
447 | ||||
448 | OS << " return false;\n"; | |||
449 | OS << " });\n\n"; | |||
450 | ||||
451 | OS << " if (Idx == Table.end()"; | |||
452 | ||||
453 | for (const auto &Field : Index.Fields) | |||
454 | OS << " ||\n Key." << Field.Name << " != Idx->" << Field.Name; | |||
455 | OS << ")\n return nullptr;\n"; | |||
456 | ||||
457 | if (IsPrimary) | |||
458 | OS << " return &*Idx;\n"; | |||
459 | else | |||
460 | OS << " return &" << Table.Name << "[Idx->_index];\n"; | |||
461 | ||||
462 | OS << "}\n"; | |||
463 | } | |||
464 | ||||
465 | void SearchableTableEmitter::emitLookupDeclaration(const GenericTable &Table, | |||
466 | const SearchIndex &Index, | |||
467 | raw_ostream &OS) { | |||
468 | OS << "const " << Table.CppTypeName << " *" << Index.Name << "("; | |||
469 | ||||
470 | bool NeedComma = false; | |||
471 | for (const auto &Field : Index.Fields) { | |||
472 | if (NeedComma) | |||
473 | OS << ", "; | |||
474 | NeedComma = true; | |||
475 | ||||
476 | OS << searchableFieldType(Field, TypeInArgument) << " " << Field.Name; | |||
477 | } | |||
478 | OS << ")"; | |||
479 | } | |||
480 | ||||
481 | void SearchableTableEmitter::emitGenericTable(const GenericTable &Table, | |||
482 | raw_ostream &OS) { | |||
483 | emitIfdef((Twine("GET_") + Table.PreprocessorGuard + "_DECL").str(), OS); | |||
484 | ||||
485 | // Emit the declarations for the functions that will perform lookup. | |||
486 | if (Table.PrimaryKey) { | |||
487 | emitLookupDeclaration(Table, *Table.PrimaryKey, OS); | |||
488 | OS << ";\n"; | |||
489 | } | |||
490 | for (const auto &Index : Table.Indices) { | |||
491 | emitLookupDeclaration(Table, *Index, OS); | |||
492 | OS << ";\n"; | |||
493 | } | |||
494 | ||||
495 | OS << "#endif\n\n"; | |||
496 | ||||
497 | emitIfdef((Twine("GET_") + Table.PreprocessorGuard + "_IMPL").str(), OS); | |||
498 | ||||
499 | // The primary data table contains all the fields defined for this map. | |||
500 | OS << "const " << Table.CppTypeName << " " << Table.Name << "[] = {\n"; | |||
501 | for (unsigned i = 0; i < Table.Entries.size(); ++i) { | |||
502 | Record *Entry = Table.Entries[i]; | |||
503 | OS << " { "; | |||
504 | ||||
505 | bool NeedComma = false; | |||
506 | for (const auto &Field : Table.Fields) { | |||
507 | if (NeedComma) | |||
508 | OS << ", "; | |||
509 | NeedComma = true; | |||
510 | ||||
511 | OS << primaryRepresentation(Field, Entry->getValueInit(Field.Name)); | |||
512 | } | |||
513 | ||||
514 | OS << " }, // " << i << "\n"; | |||
515 | } | |||
516 | OS << " };\n"; | |||
517 | ||||
518 | // Indexes are sorted "{ Thing, PrimaryIdx }" arrays, so that a binary | |||
519 | // search can be performed by "Thing". | |||
520 | if (Table.PrimaryKey) | |||
521 | emitLookupFunction(Table, *Table.PrimaryKey, true, OS); | |||
522 | for (const auto &Index : Table.Indices) | |||
523 | emitLookupFunction(Table, *Index, false, OS); | |||
524 | ||||
525 | OS << "#endif\n\n"; | |||
526 | } | |||
527 | ||||
528 | bool SearchableTableEmitter::parseFieldType(GenericField &Field, Init *II) { | |||
529 | if (auto DI = dyn_cast<DefInit>(II)) { | |||
530 | Record *TypeRec = DI->getDef(); | |||
531 | if (TypeRec->isSubClassOf("GenericEnum")) { | |||
532 | Field.Enum = EnumMap[TypeRec]; | |||
533 | Field.RecType = RecordRecTy::get(Field.Enum->Class); | |||
534 | return true; | |||
535 | } | |||
536 | } | |||
537 | ||||
538 | return false; | |||
539 | } | |||
540 | ||||
541 | std::unique_ptr<SearchIndex> | |||
542 | SearchableTableEmitter::parseSearchIndex(GenericTable &Table, StringRef Name, | |||
543 | const std::vector<StringRef> &Key, | |||
544 | bool EarlyOut) { | |||
545 | auto Index = llvm::make_unique<SearchIndex>(); | |||
546 | Index->Name = Name; | |||
547 | Index->EarlyOut = EarlyOut; | |||
548 | ||||
549 | for (const auto &FieldName : Key) { | |||
550 | const GenericField *Field = Table.getFieldByName(FieldName); | |||
551 | if (!Field) | |||
552 | PrintFatalError(Twine("Search index '") + Name + | |||
553 | "' refers to non-existing field '" + FieldName + | |||
554 | "' in table '" + Table.Name + "'"); | |||
555 | Index->Fields.push_back(*Field); | |||
556 | } | |||
557 | ||||
558 | if (EarlyOut && isa<StringRecTy>(Index->Fields[0].RecType)) { | |||
559 | PrintFatalError( | |||
560 | "Early-out is not supported for string types (in search index '" + | |||
561 | Twine(Name) + "'"); | |||
562 | } | |||
563 | ||||
564 | return Index; | |||
565 | } | |||
566 | ||||
567 | void SearchableTableEmitter::collectEnumEntries( | |||
568 | GenericEnum &Enum, StringRef NameField, StringRef ValueField, | |||
569 | const std::vector<Record *> &Items) { | |||
570 | for (auto EntryRec : Items) { | |||
571 | StringRef Name; | |||
572 | if (NameField.empty()) | |||
573 | Name = EntryRec->getName(); | |||
574 | else | |||
575 | Name = EntryRec->getValueAsString(NameField); | |||
576 | ||||
577 | int64_t Value = 0; | |||
578 | if (!ValueField.empty()) | |||
579 | Value = getInt(EntryRec, ValueField); | |||
580 | ||||
581 | Enum.Entries.push_back(llvm::make_unique<GenericEnum::Entry>(Name, Value)); | |||
582 | Enum.EntryMap.insert(std::make_pair(EntryRec, Enum.Entries.back().get())); | |||
583 | } | |||
584 | ||||
585 | if (ValueField.empty()) { | |||
586 | std::stable_sort(Enum.Entries.begin(), Enum.Entries.end(), | |||
587 | [](const std::unique_ptr<GenericEnum::Entry> &LHS, | |||
588 | const std::unique_ptr<GenericEnum::Entry> &RHS) { | |||
589 | return LHS->first < RHS->first; | |||
590 | }); | |||
591 | ||||
592 | for (size_t i = 0; i < Enum.Entries.size(); ++i) | |||
593 | Enum.Entries[i]->second = i; | |||
594 | } | |||
595 | } | |||
596 | ||||
597 | void SearchableTableEmitter::collectTableEntries( | |||
598 | GenericTable &Table, const std::vector<Record *> &Items) { | |||
599 | for (auto EntryRec : Items) { | |||
600 | for (auto &Field : Table.Fields) { | |||
601 | auto TI = dyn_cast<TypedInit>(EntryRec->getValueInit(Field.Name)); | |||
602 | if (!TI) { | |||
603 | PrintFatalError(Twine("Record '") + EntryRec->getName() + | |||
604 | "' in table '" + Table.Name + "' is missing field '" + | |||
605 | Field.Name + "'"); | |||
606 | } | |||
607 | if (!Field.RecType) { | |||
608 | Field.RecType = TI->getType(); | |||
609 | } else { | |||
610 | RecTy *Ty = resolveTypes(Field.RecType, TI->getType()); | |||
611 | if (!Ty) | |||
612 | PrintFatalError(Twine("Field '") + Field.Name + "' of table '" + | |||
613 | Table.Name + "' has incompatible type: " + | |||
614 | Ty->getAsString() + " vs. " + | |||
| ||||
615 | TI->getType()->getAsString()); | |||
616 | Field.RecType = Ty; | |||
617 | } | |||
618 | } | |||
619 | ||||
620 | Table.Entries.push_back(EntryRec); | |||
621 | } | |||
622 | ||||
623 | Record *IntrinsicClass = Records.getClass("Intrinsic"); | |||
624 | Record *InstructionClass = Records.getClass("Instruction"); | |||
625 | for (auto &Field : Table.Fields) { | |||
626 | if (auto RecordTy = dyn_cast<RecordRecTy>(Field.RecType)) { | |||
627 | if (IntrinsicClass && RecordTy->isSubClassOf(IntrinsicClass)) | |||
628 | Field.IsIntrinsic = true; | |||
629 | else if (InstructionClass && RecordTy->isSubClassOf(InstructionClass)) | |||
630 | Field.IsInstruction = true; | |||
631 | } | |||
632 | } | |||
633 | } | |||
634 | ||||
635 | void SearchableTableEmitter::run(raw_ostream &OS) { | |||
636 | // Emit tables in a deterministic order to avoid needless rebuilds. | |||
637 | SmallVector<std::unique_ptr<GenericTable>, 4> Tables; | |||
638 | DenseMap<Record *, GenericTable *> TableMap; | |||
639 | ||||
640 | // Collect all definitions first. | |||
641 | for (auto EnumRec : Records.getAllDerivedDefinitions("GenericEnum")) { | |||
642 | StringRef NameField; | |||
643 | if (!EnumRec->isValueUnset("NameField")) | |||
644 | NameField = EnumRec->getValueAsString("NameField"); | |||
645 | ||||
646 | StringRef ValueField; | |||
647 | if (!EnumRec->isValueUnset("ValueField")) | |||
648 | ValueField = EnumRec->getValueAsString("ValueField"); | |||
649 | ||||
650 | auto Enum = llvm::make_unique<GenericEnum>(); | |||
651 | Enum->Name = EnumRec->getName(); | |||
652 | Enum->PreprocessorGuard = EnumRec->getName(); | |||
653 | ||||
654 | StringRef FilterClass = EnumRec->getValueAsString("FilterClass"); | |||
655 | Enum->Class = Records.getClass(FilterClass); | |||
656 | if (!Enum->Class) | |||
657 | PrintFatalError(Twine("Enum FilterClass '") + FilterClass + | |||
658 | "' does not exist"); | |||
659 | ||||
660 | collectEnumEntries(*Enum, NameField, ValueField, | |||
661 | Records.getAllDerivedDefinitions(FilterClass)); | |||
662 | EnumMap.insert(std::make_pair(EnumRec, Enum.get())); | |||
663 | Enums.emplace_back(std::move(Enum)); | |||
664 | } | |||
665 | ||||
666 | for (auto TableRec : Records.getAllDerivedDefinitions("GenericTable")) { | |||
667 | auto Table = llvm::make_unique<GenericTable>(); | |||
668 | Table->Name = TableRec->getName(); | |||
669 | Table->PreprocessorGuard = TableRec->getName(); | |||
670 | Table->CppTypeName = TableRec->getValueAsString("CppTypeName"); | |||
671 | ||||
672 | std::vector<StringRef> Fields = TableRec->getValueAsListOfStrings("Fields"); | |||
673 | for (const auto &FieldName : Fields) { | |||
674 | Table->Fields.emplace_back(FieldName); | |||
675 | ||||
676 | if (auto TypeOfVal = TableRec->getValue(("TypeOf_" + FieldName).str())) { | |||
677 | if (!parseFieldType(Table->Fields.back(), TypeOfVal->getValue())) { | |||
678 | PrintFatalError(Twine("Table '") + Table->Name + | |||
679 | "' has bad 'TypeOf_" + FieldName + "': " + | |||
680 | TypeOfVal->getValue()->getAsString()); | |||
681 | } | |||
682 | } | |||
683 | } | |||
684 | ||||
685 | collectTableEntries(*Table, Records.getAllDerivedDefinitions( | |||
686 | TableRec->getValueAsString("FilterClass"))); | |||
687 | ||||
688 | if (!TableRec->isValueUnset("PrimaryKey")) { | |||
689 | Table->PrimaryKey = | |||
690 | parseSearchIndex(*Table, TableRec->getValueAsString("PrimaryKeyName"), | |||
691 | TableRec->getValueAsListOfStrings("PrimaryKey"), | |||
692 | TableRec->getValueAsBit("PrimaryKeyEarlyOut")); | |||
693 | ||||
694 | std::stable_sort(Table->Entries.begin(), Table->Entries.end(), | |||
695 | [&](Record *LHS, Record *RHS) { | |||
696 | return compareBy(LHS, RHS, *Table->PrimaryKey); | |||
697 | }); | |||
698 | } | |||
699 | ||||
700 | TableMap.insert(std::make_pair(TableRec, Table.get())); | |||
701 | Tables.emplace_back(std::move(Table)); | |||
702 | } | |||
703 | ||||
704 | for (Record *IndexRec : Records.getAllDerivedDefinitions("SearchIndex")) { | |||
705 | Record *TableRec = IndexRec->getValueAsDef("Table"); | |||
706 | auto It = TableMap.find(TableRec); | |||
707 | if (It == TableMap.end()) | |||
708 | PrintFatalError(Twine("SearchIndex '") + IndexRec->getName() + | |||
709 | "' refers to non-existing table '" + TableRec->getName()); | |||
710 | ||||
711 | GenericTable &Table = *It->second; | |||
712 | Table.Indices.push_back(parseSearchIndex( | |||
713 | Table, IndexRec->getName(), IndexRec->getValueAsListOfStrings("Key"), | |||
714 | IndexRec->getValueAsBit("EarlyOut"))); | |||
715 | } | |||
716 | ||||
717 | // Translate legacy tables. | |||
718 | Record *SearchableTable = Records.getClass("SearchableTable"); | |||
719 | for (auto &NameRec : Records.getClasses()) { | |||
720 | Record *Class = NameRec.second.get(); | |||
721 | if (Class->getSuperClasses().size() != 1 || | |||
722 | !Class->isSubClassOf(SearchableTable)) | |||
723 | continue; | |||
724 | ||||
725 | StringRef TableName = Class->getName(); | |||
726 | std::vector<Record *> Items = Records.getAllDerivedDefinitions(TableName); | |||
727 | if (!Class->isValueUnset("EnumNameField")) { | |||
728 | StringRef NameField = Class->getValueAsString("EnumNameField"); | |||
729 | StringRef ValueField; | |||
730 | if (!Class->isValueUnset("EnumValueField")) | |||
731 | ValueField = Class->getValueAsString("EnumValueField"); | |||
732 | ||||
733 | auto Enum = llvm::make_unique<GenericEnum>(); | |||
734 | Enum->Name = (Twine(Class->getName()) + "Values").str(); | |||
735 | Enum->PreprocessorGuard = Class->getName().upper(); | |||
736 | Enum->Class = Class; | |||
737 | ||||
738 | collectEnumEntries(*Enum, NameField, ValueField, Items); | |||
739 | ||||
740 | Enums.emplace_back(std::move(Enum)); | |||
741 | } | |||
742 | ||||
743 | auto Table = llvm::make_unique<GenericTable>(); | |||
744 | Table->Name = (Twine(Class->getName()) + "sList").str(); | |||
745 | Table->PreprocessorGuard = Class->getName().upper(); | |||
746 | Table->CppTypeName = Class->getName(); | |||
747 | ||||
748 | for (const RecordVal &Field : Class->getValues()) { | |||
749 | std::string FieldName = Field.getName(); | |||
750 | ||||
751 | // Skip uninteresting fields: either special to us, or injected | |||
752 | // template parameters (if they contain a ':'). | |||
753 | if (FieldName.find(':') != std::string::npos || | |||
754 | FieldName == "SearchableFields" || FieldName == "EnumNameField" || | |||
755 | FieldName == "EnumValueField") | |||
756 | continue; | |||
757 | ||||
758 | Table->Fields.emplace_back(FieldName); | |||
759 | } | |||
760 | ||||
761 | collectTableEntries(*Table, Items); | |||
762 | ||||
763 | for (const auto &Field : | |||
764 | Class->getValueAsListOfStrings("SearchableFields")) { | |||
765 | std::string Name = | |||
766 | (Twine("lookup") + Table->CppTypeName + "By" + Field).str(); | |||
767 | Table->Indices.push_back(parseSearchIndex(*Table, Name, {Field}, false)); | |||
768 | } | |||
769 | ||||
770 | Tables.emplace_back(std::move(Table)); | |||
771 | } | |||
772 | ||||
773 | // Emit everything. | |||
774 | for (const auto &Enum : Enums) | |||
775 | emitGenericEnum(*Enum, OS); | |||
776 | ||||
777 | for (const auto &Table : Tables) | |||
778 | emitGenericTable(*Table, OS); | |||
779 | ||||
780 | // Put all #undefs last, to allow multiple sections guarded by the same | |||
781 | // define. | |||
782 | for (const auto &Guard : PreprocessorGuards) | |||
783 | OS << "#undef " << Guard << "\n"; | |||
784 | } | |||
785 | ||||
786 | namespace llvm { | |||
787 | ||||
788 | void EmitSearchableTables(RecordKeeper &RK, raw_ostream &OS) { | |||
789 | SearchableTableEmitter(RK).run(OS); | |||
| ||||
790 | } | |||
791 | ||||
792 | } // End llvm namespace. |