1//===- CodeGenMapTable.cpp - Instruction Mapping Table Generator ----------===//
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// CodeGenMapTable provides functionality for the TableGen to create
9// relation mapping between instructions. Relation models are defined using
10// InstrMapping as a base class. This file implements the functionality which
11// parses these definitions and generates relation maps using the information
12// specified there. These maps are emitted as tables in the XXXGenInstrInfo.inc
13// file along with the functions to query them.
14//
15// A relationship model to relate non-predicate instructions with their
16// predicated true/false forms can be defined as follows:
17//
18// def getPredOpcode : InstrMapping {
19// let FilterClass = "PredRel";
20// let RowFields = ["BaseOpcode"];
21// let ColFields = ["PredSense"];
22// let KeyCol = ["none"];
23// let ValueCols = [["true"], ["false"]]; }
24//
25// CodeGenMapTable parses this map and generates a table in XXXGenInstrInfo.inc
26// file that contains the instructions modeling this relationship. This table
27// is defined in the function
28// "int getPredOpcode(uint16_t Opcode, enum PredSense inPredSense)"
29// that can be used to retrieve the predicated form of the instruction by
30// passing its opcode value and the predicate sense (true/false) of the desired
31// instruction as arguments.
32//
33// Short description of the algorithm:
34//
35// 1) Iterate through all the records that derive from "InstrMapping" class.
36// 2) For each record, filter out instructions based on the FilterClass value.
37// 3) Iterate through this set of instructions and insert them into
38// RowInstrMap map based on their RowFields values. RowInstrMap is keyed by the
39// vector of RowFields values and contains vectors of Records (instructions) as
40// values. RowFields is a list of fields that are required to have the same
41// values for all the instructions appearing in the same row of the relation
42// table. All the instructions in a given row of the relation table have some
43// sort of relationship with the key instruction defined by the corresponding
44// relationship model.
45//
46// Ex: RowInstrMap(RowVal1, RowVal2, ...) -> [Instr1, Instr2, Instr3, ... ]
47// Here Instr1, Instr2, Instr3 have same values (RowVal1, RowVal2) for
48// RowFields. These groups of instructions are later matched against ValueCols
49// to determine the column they belong to, if any.
50//
51// While building the RowInstrMap map, collect all the key instructions in
52// KeyInstrVec. These are the instructions having the same values as KeyCol
53// for all the fields listed in ColFields.
54//
55// For Example:
56//
57// Relate non-predicate instructions with their predicated true/false forms.
58//
59// def getPredOpcode : InstrMapping {
60// let FilterClass = "PredRel";
61// let RowFields = ["BaseOpcode"];
62// let ColFields = ["PredSense"];
63// let KeyCol = ["none"];
64// let ValueCols = [["true"], ["false"]]; }
65//
66// Here, only instructions that have "none" as PredSense will be selected as key
67// instructions.
68//
69// 4) For each key instruction, get the group of instructions that share the
70// same key-value as the key instruction from RowInstrMap. Iterate over the list
71// of columns in ValueCols (it is defined as a list<list<string> >. Therefore,
72// it can specify multi-column relationships). For each column, find the
73// instruction from the group that matches all the values for the column.
74// Multiple matches are not allowed.
75//
76//===----------------------------------------------------------------------===//
77
78#include "Common/CodeGenInstruction.h"
79#include "Common/CodeGenTarget.h"
80#include "TableGenBackends.h"
81#include "llvm/ADT/SetVector.h"
82#include "llvm/ADT/StringExtras.h"
83#include "llvm/TableGen/Error.h"
84#include "llvm/TableGen/Record.h"
85
86using namespace llvm;
87typedef std::map<std::string, std::vector<const Record *>> InstrRelMapTy;
88typedef std::map<std::vector<const Init *>, std::vector<const Record *>>
89 RowInstrMapTy;
90
91namespace {
92
93//===----------------------------------------------------------------------===//
94// This class is used to represent InstrMapping class defined in Target.td file.
95class InstrMap {
96private:
97 std::string Name;
98 std::string FilterClass;
99 const ListInit *RowFields;
100 const ListInit *ColFields;
101 const ListInit *KeyCol;
102 std::vector<const ListInit *> ValueCols;
103
104public:
105 InstrMap(const Record *MapRec) {
106 Name = MapRec->getName().str();
107
108 // FilterClass - It's used to reduce the search space only to the
109 // instructions that define the kind of relationship modeled by
110 // this InstrMapping object/record.
111 const RecordVal *Filter = MapRec->getValue(Name: "FilterClass");
112 FilterClass = Filter->getValue()->getAsUnquotedString();
113
114 // List of fields/attributes that need to be same across all the
115 // instructions in a row of the relation table.
116 RowFields = MapRec->getValueAsListInit(FieldName: "RowFields");
117
118 // List of fields/attributes that are constant across all the instruction
119 // in a column of the relation table. Ex: ColFields = 'predSense'
120 ColFields = MapRec->getValueAsListInit(FieldName: "ColFields");
121
122 // Values for the fields/attributes listed in 'ColFields'.
123 // Ex: KeyCol = 'noPred' -- key instruction is non-predicated
124 KeyCol = MapRec->getValueAsListInit(FieldName: "KeyCol");
125
126 // List of values for the fields/attributes listed in 'ColFields', one for
127 // each column in the relation table.
128 //
129 // Ex: ValueCols = [['true'],['false']] -- it results two columns in the
130 // table. First column requires all the instructions to have predSense
131 // set to 'true' and second column requires it to be 'false'.
132 const ListInit *ColValList = MapRec->getValueAsListInit(FieldName: "ValueCols");
133
134 // Each instruction map must specify at least one column for it to be valid.
135 if (ColValList->empty())
136 PrintFatalError(ErrorLoc: MapRec->getLoc(), Msg: "InstrMapping record `" + Name +
137 "' has empty " +
138 "`ValueCols' field!");
139
140 for (const Init *I : ColValList->getElements()) {
141 const auto *ColI = cast<ListInit>(Val: I);
142
143 // Make sure that all the sub-lists in 'ValueCols' have same number of
144 // elements as the fields in 'ColFields'.
145 if (ColI->size() != ColFields->size())
146 PrintFatalError(ErrorLoc: MapRec->getLoc(),
147 Msg: "Record `" + Name +
148 "', field `ValueCols' entries don't match with " +
149 " the entries in 'ColFields'!");
150 ValueCols.push_back(x: ColI);
151 }
152 }
153
154 const std::string &getName() const { return Name; }
155 const std::string &getFilterClass() const { return FilterClass; }
156 const ListInit *getRowFields() const { return RowFields; }
157 const ListInit *getColFields() const { return ColFields; }
158 const ListInit *getKeyCol() const { return KeyCol; }
159 ArrayRef<const ListInit *> getValueCols() const { return ValueCols; }
160};
161
162//===----------------------------------------------------------------------===//
163// class MapTableEmitter : It builds the instruction relation maps using
164// the information provided in InstrMapping records. It outputs these
165// relationship maps as tables into XXXGenInstrInfo.inc file along with the
166// functions to query them.
167
168class MapTableEmitter {
169private:
170 // std::string TargetName;
171 const CodeGenTarget &Target;
172 // InstrMapDesc - InstrMapping record to be processed.
173 InstrMap InstrMapDesc;
174
175 // InstrDefs - list of instructions filtered using FilterClass defined
176 // in InstrMapDesc.
177 ArrayRef<const Record *> InstrDefs;
178
179 // RowInstrMap - maps RowFields values to the instructions. It's keyed by the
180 // values of the row fields and contains vector of records as values.
181 RowInstrMapTy RowInstrMap;
182
183 // KeyInstrVec - list of key instructions.
184 std::vector<const Record *> KeyInstrVec;
185 DenseMap<const Record *, std::vector<const Record *>> MapTable;
186
187public:
188 MapTableEmitter(const CodeGenTarget &Target, const RecordKeeper &Records,
189 const Record *IMRec)
190 : Target(Target), InstrMapDesc(IMRec) {
191 const std::string &FilterClass = InstrMapDesc.getFilterClass();
192 InstrDefs = Records.getAllDerivedDefinitions(ClassName: FilterClass);
193 }
194
195 void buildRowInstrMap();
196
197 // Returns true if an instruction is a key instruction, i.e., its ColFields
198 // have same values as KeyCol.
199 bool isKeyColInstr(const Record *CurInstr);
200
201 // Find column instruction corresponding to a key instruction based on the
202 // constraints for that column.
203 const Record *getInstrForColumn(const Record *KeyInstr,
204 const ListInit *CurValueCol);
205
206 // Find column instructions for each key instruction based
207 // on ValueCols and store them into MapTable.
208 void buildMapTable();
209
210 void emitBinSearch(raw_ostream &OS, unsigned TableSize);
211 void emitTablesWithFunc(raw_ostream &OS);
212 unsigned emitBinSearchTable(raw_ostream &OS);
213
214 // Lookup functions to query binary search tables.
215 void emitMapFuncBody(raw_ostream &OS, unsigned TableSize);
216};
217} // end anonymous namespace
218
219//===----------------------------------------------------------------------===//
220// Process all the instructions that model this relation (alreday present in
221// InstrDefs) and insert them into RowInstrMap which is keyed by the values of
222// the fields listed as RowFields. It stores vectors of records as values.
223// All the related instructions have the same values for the RowFields thus are
224// part of the same key-value pair.
225//===----------------------------------------------------------------------===//
226
227void MapTableEmitter::buildRowInstrMap() {
228 for (const Record *CurInstr : InstrDefs) {
229 std::vector<const Init *> KeyValue;
230 const ListInit *RowFields = InstrMapDesc.getRowFields();
231 for (const Init *RowField : RowFields->getElements()) {
232 const RecordVal *RecVal = CurInstr->getValue(Name: RowField);
233 if (RecVal == nullptr)
234 PrintFatalError(ErrorLoc: CurInstr->getLoc(),
235 Msg: "No value " + RowField->getAsString() + " found in \"" +
236 CurInstr->getName() +
237 "\" instruction description.");
238 const Init *CurInstrVal = RecVal->getValue();
239 KeyValue.push_back(x: CurInstrVal);
240 }
241
242 // Collect key instructions into KeyInstrVec. Later, these instructions are
243 // processed to assign column position to the instructions sharing
244 // their KeyValue in RowInstrMap.
245 if (isKeyColInstr(CurInstr))
246 KeyInstrVec.push_back(x: CurInstr);
247
248 RowInstrMap[KeyValue].push_back(x: CurInstr);
249 }
250}
251
252//===----------------------------------------------------------------------===//
253// Return true if an instruction is a KeyCol instruction.
254//===----------------------------------------------------------------------===//
255
256bool MapTableEmitter::isKeyColInstr(const Record *CurInstr) {
257 const ListInit *ColFields = InstrMapDesc.getColFields();
258 const ListInit *KeyCol = InstrMapDesc.getKeyCol();
259
260 // Check if the instruction is a KeyCol instruction.
261 bool MatchFound = true;
262 for (unsigned J = 0, EndCf = ColFields->size(); (J < EndCf) && MatchFound;
263 J++) {
264 const RecordVal *ColFieldName =
265 CurInstr->getValue(Name: ColFields->getElement(Idx: J));
266 std::string CurInstrVal = ColFieldName->getValue()->getAsUnquotedString();
267 std::string KeyColValue = KeyCol->getElement(Idx: J)->getAsUnquotedString();
268 MatchFound = CurInstrVal == KeyColValue;
269 }
270 return MatchFound;
271}
272
273//===----------------------------------------------------------------------===//
274// Build a map to link key instructions with the column instructions arranged
275// according to their column positions.
276//===----------------------------------------------------------------------===//
277
278void MapTableEmitter::buildMapTable() {
279 // Find column instructions for a given key based on the ColField
280 // constraints.
281 ArrayRef<const ListInit *> ValueCols = InstrMapDesc.getValueCols();
282 unsigned NumOfCols = ValueCols.size();
283 for (const Record *CurKeyInstr : KeyInstrVec) {
284 std::vector<const Record *> ColInstrVec(NumOfCols);
285
286 // Find the column instruction based on the constraints for the column.
287 for (unsigned ColIdx = 0; ColIdx < NumOfCols; ColIdx++) {
288 const ListInit *CurValueCol = ValueCols[ColIdx];
289 const Record *ColInstr = getInstrForColumn(KeyInstr: CurKeyInstr, CurValueCol);
290 ColInstrVec[ColIdx] = ColInstr;
291 }
292 MapTable[CurKeyInstr] = ColInstrVec;
293 }
294}
295
296//===----------------------------------------------------------------------===//
297// Find column instruction based on the constraints for that column.
298//===----------------------------------------------------------------------===//
299
300const Record *MapTableEmitter::getInstrForColumn(const Record *KeyInstr,
301 const ListInit *CurValueCol) {
302 const ListInit *RowFields = InstrMapDesc.getRowFields();
303 std::vector<const Init *> KeyValue;
304
305 // Construct KeyValue using KeyInstr's values for RowFields.
306 for (const Init *RowField : RowFields->getElements()) {
307 const Init *KeyInstrVal = KeyInstr->getValue(Name: RowField)->getValue();
308 KeyValue.push_back(x: KeyInstrVal);
309 }
310
311 // Get all the instructions that share the same KeyValue as the KeyInstr
312 // in RowInstrMap. We search through these instructions to find a match
313 // for the current column, i.e., the instruction which has the same values
314 // as CurValueCol for all the fields in ColFields.
315 ArrayRef<const Record *> RelatedInstrVec = RowInstrMap[KeyValue];
316
317 const ListInit *ColFields = InstrMapDesc.getColFields();
318 const Record *MatchInstr = nullptr;
319
320 for (const Record *CurInstr : RelatedInstrVec) {
321 bool MatchFound = true;
322 for (unsigned J = 0, EndCf = ColFields->size(); (J < EndCf) && MatchFound;
323 J++) {
324 const Init *ColFieldJ = ColFields->getElement(Idx: J);
325 const Init *CurInstrInit = CurInstr->getValue(Name: ColFieldJ)->getValue();
326 std::string CurInstrVal = CurInstrInit->getAsUnquotedString();
327 const Init *ColFieldJVallue = CurValueCol->getElement(Idx: J);
328 MatchFound = CurInstrVal == ColFieldJVallue->getAsUnquotedString();
329 }
330
331 if (MatchFound) {
332 if (MatchInstr) {
333 // Already had a match
334 // Error if multiple matches are found for a column.
335 std::string KeyValueStr;
336 for (const Init *Value : KeyValue) {
337 if (!KeyValueStr.empty())
338 KeyValueStr += ", ";
339 KeyValueStr += Value->getAsString();
340 }
341
342 PrintFatalError(Msg: "Multiple matches found for `" + KeyInstr->getName() +
343 "', for the relation `" + InstrMapDesc.getName() +
344 "', row fields [" + KeyValueStr + "], column `" +
345 CurValueCol->getAsString() + "'");
346 }
347 MatchInstr = CurInstr;
348 }
349 }
350 return MatchInstr;
351}
352
353//===----------------------------------------------------------------------===//
354// Emit one table per relation. Only instructions with a valid relation of a
355// given type are included in the table sorted by their enum values (opcodes).
356// Binary search is used for locating instructions in the table.
357//===----------------------------------------------------------------------===//
358
359unsigned MapTableEmitter::emitBinSearchTable(raw_ostream &OS) {
360 ArrayRef<const CodeGenInstruction *> NumberedInstructions =
361 Target.getInstructionsByEnumValue();
362 StringRef Namespace = Target.getInstNamespace();
363 ArrayRef<const ListInit *> ValueCols = InstrMapDesc.getValueCols();
364 unsigned NumCol = ValueCols.size();
365 unsigned TableSize = 0;
366
367 OS << " using namespace " << Namespace << ";\n";
368 // Number of columns in the table are NumCol+1 because key instructions are
369 // emitted as first column.
370 for (const CodeGenInstruction *Inst : NumberedInstructions) {
371 const Record *CurInstr = Inst->TheDef;
372 ArrayRef<const Record *> ColInstrs = MapTable[CurInstr];
373 if (ColInstrs.empty())
374 continue;
375 std::string OutStr;
376 bool RelExists = false;
377 for (const Record *ColInstr : ColInstrs) {
378 if (ColInstr) {
379 RelExists = true;
380 OutStr += ", ";
381 OutStr += ColInstr->getName();
382 } else {
383 OutStr += ", (uint16_t)-1U";
384 }
385 }
386
387 if (RelExists) {
388 if (TableSize == 0)
389 OS << " static constexpr uint16_t Table[][" << NumCol + 1 << "] = {\n";
390 OS << " { " << CurInstr->getName() << OutStr << " },\n";
391 ++TableSize;
392 }
393 }
394
395 if (TableSize != 0)
396 OS << " }; // End of Table\n\n";
397 return TableSize;
398}
399
400//===----------------------------------------------------------------------===//
401// Emit binary search algorithm as part of the functions used to query
402// relation tables.
403//===----------------------------------------------------------------------===//
404
405void MapTableEmitter::emitBinSearch(raw_ostream &OS, unsigned TableSize) {
406 if (TableSize == 0) {
407 OS << " return -1;\n";
408 return;
409 }
410
411 OS << " unsigned mid;\n";
412 OS << " unsigned start = 0;\n";
413 OS << " unsigned end = " << TableSize << ";\n";
414 OS << " while (start < end) {\n";
415 OS << " mid = start + (end - start) / 2;\n";
416 OS << " if (Opcode == Table[mid][0]) \n";
417 OS << " break;\n";
418 OS << " if (Opcode < Table[mid][0])\n";
419 OS << " end = mid;\n";
420 OS << " else\n";
421 OS << " start = mid + 1;\n";
422 OS << " }\n";
423 OS << " if (start == end)\n";
424 OS << " return -1; // Instruction doesn't exist in this table.\n\n";
425}
426
427//===----------------------------------------------------------------------===//
428// Emit functions to query relation tables.
429//===----------------------------------------------------------------------===//
430
431void MapTableEmitter::emitMapFuncBody(raw_ostream &OS, unsigned TableSize) {
432 const ListInit *ColFields = InstrMapDesc.getColFields();
433 ArrayRef<const ListInit *> ValueCols = InstrMapDesc.getValueCols();
434
435 // Emit binary search algorithm to locate instructions in the
436 // relation table. If found, return opcode value from the appropriate column
437 // of the table.
438 emitBinSearch(OS, TableSize);
439 if (TableSize == 0)
440 return;
441
442 if (ValueCols.size() > 1) {
443 for (unsigned I = 0, E = ValueCols.size(); I < E; I++) {
444 const ListInit *ColumnI = ValueCols[I];
445 OS << " if (";
446 for (unsigned J = 0, ColSize = ColumnI->size(); J < ColSize; ++J) {
447 std::string ColName = ColFields->getElement(Idx: J)->getAsUnquotedString();
448 OS << "in" << ColName;
449 OS << " == ";
450 OS << ColName << "_" << ColumnI->getElement(Idx: J)->getAsUnquotedString();
451 if (J < ColumnI->size() - 1)
452 OS << " && ";
453 }
454 OS << ")\n";
455 OS << " return Table[mid][" << I + 1 << "];\n";
456 }
457 OS << " return -1;";
458 } else {
459 OS << " return Table[mid][1];\n";
460 }
461}
462
463//===----------------------------------------------------------------------===//
464// Emit relation tables and the functions to query them.
465//===----------------------------------------------------------------------===//
466
467void MapTableEmitter::emitTablesWithFunc(raw_ostream &OS) {
468 // Emit function name and the input parameters : mostly opcode value of the
469 // current instruction. However, if a table has multiple columns (more than 2
470 // since first column is used for the key instructions), then we also need
471 // to pass another input to indicate the column to be selected.
472
473 const ListInit *ColFields = InstrMapDesc.getColFields();
474 ArrayRef<const ListInit *> ValueCols = InstrMapDesc.getValueCols();
475 OS << "// " << InstrMapDesc.getName() << "\nLLVM_READONLY\n";
476 OS << "int " << InstrMapDesc.getName() << "(uint16_t Opcode";
477 if (ValueCols.size() > 1) {
478 for (const Init *CF : ColFields->getElements()) {
479 std::string ColName = CF->getAsUnquotedString();
480 OS << ", enum " << ColName << " in" << ColName;
481 }
482 }
483 OS << ") {\n";
484
485 // Emit map table.
486 unsigned TableSize = emitBinSearchTable(OS);
487
488 // Emit rest of the function body.
489 emitMapFuncBody(OS, TableSize);
490
491 OS << "}\n\n";
492}
493
494//===----------------------------------------------------------------------===//
495// Emit enums for the column fields across all the instruction maps.
496//===----------------------------------------------------------------------===//
497
498static void emitEnums(raw_ostream &OS, const RecordKeeper &Records) {
499 std::map<std::string, SetVector<const Init *>> ColFieldValueMap;
500
501 // Iterate over all InstrMapping records and create a map between column
502 // fields and their possible values across all records.
503 for (const Record *CurMap :
504 Records.getAllDerivedDefinitions(ClassName: "InstrMapping")) {
505 const ListInit *ColFields = CurMap->getValueAsListInit(FieldName: "ColFields");
506 const ListInit *List = CurMap->getValueAsListInit(FieldName: "ValueCols");
507 std::vector<const ListInit *> ValueCols;
508
509 for (const Init *Elem : *List) {
510 const auto *ListJ = cast<ListInit>(Val: Elem);
511
512 if (ListJ->size() != ColFields->size())
513 PrintFatalError(Msg: "Record `" + CurMap->getName() +
514 "', field "
515 "`ValueCols' entries don't match with the entries in "
516 "'ColFields' !");
517 ValueCols.push_back(x: ListJ);
518 }
519
520 for (unsigned J = 0, EndCf = ColFields->size(); J < EndCf; J++) {
521 std::string ColName = ColFields->getElement(Idx: J)->getAsUnquotedString();
522 auto &MapEntry = ColFieldValueMap[ColName];
523 for (const ListInit *List : ValueCols)
524 MapEntry.insert(X: List->getElement(Idx: J));
525 }
526 }
527
528 for (auto &[EnumName, FieldValues] : ColFieldValueMap) {
529 // Emit enumerated values for the column fields.
530 OS << "enum " << EnumName << " {\n";
531 ListSeparator LS(",\n");
532 for (const Init *Field : FieldValues)
533 OS << LS << " " << EnumName << "_" << Field->getAsUnquotedString();
534 OS << "\n};\n\n";
535 }
536}
537
538//===----------------------------------------------------------------------===//
539// Parse 'InstrMapping' records and use the information to form relationship
540// between instructions. These relations are emitted as tables along with the
541// functions to query them.
542//===----------------------------------------------------------------------===//
543void llvm::EmitMapTable(const RecordKeeper &Records, raw_ostream &OS) {
544 CodeGenTarget Target(Records);
545 StringRef NameSpace = Target.getInstNamespace();
546 ArrayRef<const Record *> InstrMapVec =
547 Records.getAllDerivedDefinitions(ClassName: "InstrMapping");
548
549 if (InstrMapVec.empty())
550 return;
551
552 OS << "#ifdef GET_INSTRMAP_INFO\n";
553 OS << "#undef GET_INSTRMAP_INFO\n";
554 OS << "namespace llvm::" << NameSpace << " {\n\n";
555
556 // Emit coulumn field names and their values as enums.
557 emitEnums(OS, Records);
558
559 // Iterate over all instruction mapping records and construct relationship
560 // maps based on the information specified there.
561 //
562 for (const Record *CurMap : InstrMapVec) {
563 MapTableEmitter IMap(Target, Records, CurMap);
564
565 // Build RowInstrMap to group instructions based on their values for
566 // RowFields. In the process, also collect key instructions into
567 // KeyInstrVec.
568 IMap.buildRowInstrMap();
569
570 // Build MapTable to map key instructions with the corresponding column
571 // instructions.
572 IMap.buildMapTable();
573
574 // Emit map tables and the functions to query them.
575 IMap.emitTablesWithFunc(OS);
576 }
577 OS << "} // end namespace llvm::" << NameSpace << '\n';
578 OS << "#endif // GET_INSTRMAP_INFO\n\n";
579}
580