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