1 //===- CodeGenMapTable.cpp - Instruction Mapping Table Generator ----------===//
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
7 //===----------------------------------------------------------------------===//
8 // CodeGenMapTable provides functionality for the TabelGen 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.
15 // A relationship model to relate non-predicate instructions with their
16 // predicated true/false forms can be defined as follows:
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"]]; }
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.
33 // Short description of the algorithm:
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.
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.
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.
57 // Relate non-predicate instructions with their predicated true/false forms.
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"]]; }
66 // Here, only instructions that have "none" as PredSense will be selected as key
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.
76 //===----------------------------------------------------------------------===//
78 #include "CodeGenTarget.h"
79 #include "llvm/Support/Format.h"
80 #include "llvm/TableGen/Error.h"
82 typedef std::map
<std::string
, std::vector
<Record
*> > InstrRelMapTy
;
84 typedef std::map
<std::vector
<Init
*>, std::vector
<Record
*> > RowInstrMapTy
;
88 //===----------------------------------------------------------------------===//
89 // This class is used to represent InstrMapping class defined in Target.td file.
93 std::string FilterClass
;
97 std::vector
<ListInit
*> ValueCols
;
100 InstrMap(Record
* MapRec
) {
101 Name
= MapRec
->getName();
103 // FilterClass - It's used to reduce the search space only to the
104 // instructions that define the kind of relationship modeled by
105 // this InstrMapping object/record.
106 const RecordVal
*Filter
= MapRec
->getValue("FilterClass");
107 FilterClass
= Filter
->getValue()->getAsUnquotedString();
109 // List of fields/attributes that need to be same across all the
110 // instructions in a row of the relation table.
111 RowFields
= MapRec
->getValueAsListInit("RowFields");
113 // List of fields/attributes that are constant across all the instruction
114 // in a column of the relation table. Ex: ColFields = 'predSense'
115 ColFields
= MapRec
->getValueAsListInit("ColFields");
117 // Values for the fields/attributes listed in 'ColFields'.
118 // Ex: KeyCol = 'noPred' -- key instruction is non-predicated
119 KeyCol
= MapRec
->getValueAsListInit("KeyCol");
121 // List of values for the fields/attributes listed in 'ColFields', one for
122 // each column in the relation table.
124 // Ex: ValueCols = [['true'],['false']] -- it results two columns in the
125 // table. First column requires all the instructions to have predSense
126 // set to 'true' and second column requires it to be 'false'.
127 ListInit
*ColValList
= MapRec
->getValueAsListInit("ValueCols");
129 // Each instruction map must specify at least one column for it to be valid.
130 if (ColValList
->empty())
131 PrintFatalError(MapRec
->getLoc(), "InstrMapping record `" +
132 MapRec
->getName() + "' has empty " + "`ValueCols' field!");
134 for (Init
*I
: ColValList
->getValues()) {
135 auto *ColI
= cast
<ListInit
>(I
);
137 // Make sure that all the sub-lists in 'ValueCols' have same number of
138 // elements as the fields in 'ColFields'.
139 if (ColI
->size() != ColFields
->size())
140 PrintFatalError(MapRec
->getLoc(), "Record `" + MapRec
->getName() +
141 "', field `ValueCols' entries don't match with " +
142 " the entries in 'ColFields'!");
143 ValueCols
.push_back(ColI
);
147 std::string
getName() const {
151 std::string
getFilterClass() {
155 ListInit
*getRowFields() const {
159 ListInit
*getColFields() const {
163 ListInit
*getKeyCol() const {
167 const std::vector
<ListInit
*> &getValueCols() const {
171 } // end anonymous namespace
174 //===----------------------------------------------------------------------===//
175 // class MapTableEmitter : It builds the instruction relation maps using
176 // the information provided in InstrMapping records. It outputs these
177 // relationship maps as tables into XXXGenInstrInfo.inc file along with the
178 // functions to query them.
181 class MapTableEmitter
{
183 // std::string TargetName;
184 const CodeGenTarget
&Target
;
185 // InstrMapDesc - InstrMapping record to be processed.
186 InstrMap InstrMapDesc
;
188 // InstrDefs - list of instructions filtered using FilterClass defined
190 std::vector
<Record
*> InstrDefs
;
192 // RowInstrMap - maps RowFields values to the instructions. It's keyed by the
193 // values of the row fields and contains vector of records as values.
194 RowInstrMapTy RowInstrMap
;
196 // KeyInstrVec - list of key instructions.
197 std::vector
<Record
*> KeyInstrVec
;
198 DenseMap
<Record
*, std::vector
<Record
*> > MapTable
;
201 MapTableEmitter(CodeGenTarget
&Target
, RecordKeeper
&Records
, Record
*IMRec
):
202 Target(Target
), InstrMapDesc(IMRec
) {
203 const std::string FilterClass
= InstrMapDesc
.getFilterClass();
204 InstrDefs
= Records
.getAllDerivedDefinitions(FilterClass
);
207 void buildRowInstrMap();
209 // Returns true if an instruction is a key instruction, i.e., its ColFields
210 // have same values as KeyCol.
211 bool isKeyColInstr(Record
* CurInstr
);
213 // Find column instruction corresponding to a key instruction based on the
214 // constraints for that column.
215 Record
*getInstrForColumn(Record
*KeyInstr
, ListInit
*CurValueCol
);
217 // Find column instructions for each key instruction based
218 // on ValueCols and store them into MapTable.
219 void buildMapTable();
221 void emitBinSearch(raw_ostream
&OS
, unsigned TableSize
);
222 void emitTablesWithFunc(raw_ostream
&OS
);
223 unsigned emitBinSearchTable(raw_ostream
&OS
);
225 // Lookup functions to query binary search tables.
226 void emitMapFuncBody(raw_ostream
&OS
, unsigned TableSize
);
229 } // end anonymous namespace
232 //===----------------------------------------------------------------------===//
233 // Process all the instructions that model this relation (alreday present in
234 // InstrDefs) and insert them into RowInstrMap which is keyed by the values of
235 // the fields listed as RowFields. It stores vectors of records as values.
236 // All the related instructions have the same values for the RowFields thus are
237 // part of the same key-value pair.
238 //===----------------------------------------------------------------------===//
240 void MapTableEmitter::buildRowInstrMap() {
241 for (Record
*CurInstr
: InstrDefs
) {
242 std::vector
<Init
*> KeyValue
;
243 ListInit
*RowFields
= InstrMapDesc
.getRowFields();
244 for (Init
*RowField
: RowFields
->getValues()) {
245 RecordVal
*RecVal
= CurInstr
->getValue(RowField
);
246 if (RecVal
== nullptr)
247 PrintFatalError(CurInstr
->getLoc(), "No value " +
248 RowField
->getAsString() + " found in \"" +
249 CurInstr
->getName() + "\" instruction description.");
250 Init
*CurInstrVal
= RecVal
->getValue();
251 KeyValue
.push_back(CurInstrVal
);
254 // Collect key instructions into KeyInstrVec. Later, these instructions are
255 // processed to assign column position to the instructions sharing
256 // their KeyValue in RowInstrMap.
257 if (isKeyColInstr(CurInstr
))
258 KeyInstrVec
.push_back(CurInstr
);
260 RowInstrMap
[KeyValue
].push_back(CurInstr
);
264 //===----------------------------------------------------------------------===//
265 // Return true if an instruction is a KeyCol instruction.
266 //===----------------------------------------------------------------------===//
268 bool MapTableEmitter::isKeyColInstr(Record
* CurInstr
) {
269 ListInit
*ColFields
= InstrMapDesc
.getColFields();
270 ListInit
*KeyCol
= InstrMapDesc
.getKeyCol();
272 // Check if the instruction is a KeyCol instruction.
273 bool MatchFound
= true;
274 for (unsigned j
= 0, endCF
= ColFields
->size();
275 (j
< endCF
) && MatchFound
; j
++) {
276 RecordVal
*ColFieldName
= CurInstr
->getValue(ColFields
->getElement(j
));
277 std::string CurInstrVal
= ColFieldName
->getValue()->getAsUnquotedString();
278 std::string KeyColValue
= KeyCol
->getElement(j
)->getAsUnquotedString();
279 MatchFound
= (CurInstrVal
== KeyColValue
);
284 //===----------------------------------------------------------------------===//
285 // Build a map to link key instructions with the column instructions arranged
286 // according to their column positions.
287 //===----------------------------------------------------------------------===//
289 void MapTableEmitter::buildMapTable() {
290 // Find column instructions for a given key based on the ColField
292 const std::vector
<ListInit
*> &ValueCols
= InstrMapDesc
.getValueCols();
293 unsigned NumOfCols
= ValueCols
.size();
294 for (Record
*CurKeyInstr
: KeyInstrVec
) {
295 std::vector
<Record
*> ColInstrVec(NumOfCols
);
297 // Find the column instruction based on the constraints for the column.
298 for (unsigned ColIdx
= 0; ColIdx
< NumOfCols
; ColIdx
++) {
299 ListInit
*CurValueCol
= ValueCols
[ColIdx
];
300 Record
*ColInstr
= getInstrForColumn(CurKeyInstr
, CurValueCol
);
301 ColInstrVec
[ColIdx
] = ColInstr
;
303 MapTable
[CurKeyInstr
] = ColInstrVec
;
307 //===----------------------------------------------------------------------===//
308 // Find column instruction based on the constraints for that column.
309 //===----------------------------------------------------------------------===//
311 Record
*MapTableEmitter::getInstrForColumn(Record
*KeyInstr
,
312 ListInit
*CurValueCol
) {
313 ListInit
*RowFields
= InstrMapDesc
.getRowFields();
314 std::vector
<Init
*> KeyValue
;
316 // Construct KeyValue using KeyInstr's values for RowFields.
317 for (Init
*RowField
: RowFields
->getValues()) {
318 Init
*KeyInstrVal
= KeyInstr
->getValue(RowField
)->getValue();
319 KeyValue
.push_back(KeyInstrVal
);
322 // Get all the instructions that share the same KeyValue as the KeyInstr
323 // in RowInstrMap. We search through these instructions to find a match
324 // for the current column, i.e., the instruction which has the same values
325 // as CurValueCol for all the fields in ColFields.
326 const std::vector
<Record
*> &RelatedInstrVec
= RowInstrMap
[KeyValue
];
328 ListInit
*ColFields
= InstrMapDesc
.getColFields();
329 Record
*MatchInstr
= nullptr;
331 for (unsigned i
= 0, e
= RelatedInstrVec
.size(); i
< e
; i
++) {
332 bool MatchFound
= true;
333 Record
*CurInstr
= RelatedInstrVec
[i
];
334 for (unsigned j
= 0, endCF
= ColFields
->size();
335 (j
< endCF
) && MatchFound
; j
++) {
336 Init
*ColFieldJ
= ColFields
->getElement(j
);
337 Init
*CurInstrInit
= CurInstr
->getValue(ColFieldJ
)->getValue();
338 std::string CurInstrVal
= CurInstrInit
->getAsUnquotedString();
339 Init
*ColFieldJVallue
= CurValueCol
->getElement(j
);
340 MatchFound
= (CurInstrVal
== ColFieldJVallue
->getAsUnquotedString());
345 // Already had a match
346 // Error if multiple matches are found for a column.
347 std::string KeyValueStr
;
348 for (Init
*Value
: KeyValue
) {
349 if (!KeyValueStr
.empty())
351 KeyValueStr
+= Value
->getAsString();
354 PrintFatalError("Multiple matches found for `" + KeyInstr
->getName() +
355 "', for the relation `" + InstrMapDesc
.getName() + "', row fields [" +
356 KeyValueStr
+ "], column `" + CurValueCol
->getAsString() + "'");
358 MatchInstr
= CurInstr
;
364 //===----------------------------------------------------------------------===//
365 // Emit one table per relation. Only instructions with a valid relation of a
366 // given type are included in the table sorted by their enum values (opcodes).
367 // Binary search is used for locating instructions in the table.
368 //===----------------------------------------------------------------------===//
370 unsigned MapTableEmitter::emitBinSearchTable(raw_ostream
&OS
) {
372 ArrayRef
<const CodeGenInstruction
*> NumberedInstructions
=
373 Target
.getInstructionsByEnumValue();
374 StringRef Namespace
= Target
.getInstNamespace();
375 const std::vector
<ListInit
*> &ValueCols
= InstrMapDesc
.getValueCols();
376 unsigned NumCol
= ValueCols
.size();
377 unsigned TotalNumInstr
= NumberedInstructions
.size();
378 unsigned TableSize
= 0;
380 OS
<< "static const uint16_t "<<InstrMapDesc
.getName();
381 // Number of columns in the table are NumCol+1 because key instructions are
382 // emitted as first column.
383 OS
<< "Table[]["<< NumCol
+1 << "] = {\n";
384 for (unsigned i
= 0; i
< TotalNumInstr
; i
++) {
385 Record
*CurInstr
= NumberedInstructions
[i
]->TheDef
;
386 std::vector
<Record
*> ColInstrs
= MapTable
[CurInstr
];
387 std::string
OutStr("");
388 unsigned RelExists
= 0;
389 if (!ColInstrs
.empty()) {
390 for (unsigned j
= 0; j
< NumCol
; j
++) {
391 if (ColInstrs
[j
] != nullptr) {
396 OutStr
+= ColInstrs
[j
]->getName();
397 } else { OutStr
+= ", (uint16_t)-1U";}
401 OS
<< " { " << Namespace
<< "::" << CurInstr
->getName();
402 OS
<< OutStr
<<" },\n";
408 OS
<< " { " << Namespace
<< "::" << "INSTRUCTION_LIST_END, ";
409 OS
<< Namespace
<< "::" << "INSTRUCTION_LIST_END }";
411 OS
<< "}; // End of " << InstrMapDesc
.getName() << "Table\n\n";
415 //===----------------------------------------------------------------------===//
416 // Emit binary search algorithm as part of the functions used to query
418 //===----------------------------------------------------------------------===//
420 void MapTableEmitter::emitBinSearch(raw_ostream
&OS
, unsigned TableSize
) {
421 OS
<< " unsigned mid;\n";
422 OS
<< " unsigned start = 0;\n";
423 OS
<< " unsigned end = " << TableSize
<< ";\n";
424 OS
<< " while (start < end) {\n";
425 OS
<< " mid = start + (end - start)/2;\n";
426 OS
<< " if (Opcode == " << InstrMapDesc
.getName() << "Table[mid][0]) {\n";
429 OS
<< " if (Opcode < " << InstrMapDesc
.getName() << "Table[mid][0])\n";
430 OS
<< " end = mid;\n";
432 OS
<< " start = mid + 1;\n";
434 OS
<< " if (start == end)\n";
435 OS
<< " return -1; // Instruction doesn't exist in this table.\n\n";
438 //===----------------------------------------------------------------------===//
439 // Emit functions to query relation tables.
440 //===----------------------------------------------------------------------===//
442 void MapTableEmitter::emitMapFuncBody(raw_ostream
&OS
,
443 unsigned TableSize
) {
445 ListInit
*ColFields
= InstrMapDesc
.getColFields();
446 const std::vector
<ListInit
*> &ValueCols
= InstrMapDesc
.getValueCols();
448 // Emit binary search algorithm to locate instructions in the
449 // relation table. If found, return opcode value from the appropriate column
451 emitBinSearch(OS
, TableSize
);
453 if (ValueCols
.size() > 1) {
454 for (unsigned i
= 0, e
= ValueCols
.size(); i
< e
; i
++) {
455 ListInit
*ColumnI
= ValueCols
[i
];
456 for (unsigned j
= 0, ColSize
= ColumnI
->size(); j
< ColSize
; ++j
) {
457 std::string ColName
= ColFields
->getElement(j
)->getAsUnquotedString();
458 OS
<< " if (in" << ColName
;
460 OS
<< ColName
<< "_" << ColumnI
->getElement(j
)->getAsUnquotedString();
461 if (j
< ColumnI
->size() - 1) OS
<< " && ";
464 OS
<< " return " << InstrMapDesc
.getName();
465 OS
<< "Table[mid]["<<i
+1<<"];\n";
470 OS
<< " return " << InstrMapDesc
.getName() << "Table[mid][1];\n";
475 //===----------------------------------------------------------------------===//
476 // Emit relation tables and the functions to query them.
477 //===----------------------------------------------------------------------===//
479 void MapTableEmitter::emitTablesWithFunc(raw_ostream
&OS
) {
481 // Emit function name and the input parameters : mostly opcode value of the
482 // current instruction. However, if a table has multiple columns (more than 2
483 // since first column is used for the key instructions), then we also need
484 // to pass another input to indicate the column to be selected.
486 ListInit
*ColFields
= InstrMapDesc
.getColFields();
487 const std::vector
<ListInit
*> &ValueCols
= InstrMapDesc
.getValueCols();
488 OS
<< "// "<< InstrMapDesc
.getName() << "\nLLVM_READONLY\n";
489 OS
<< "int "<< InstrMapDesc
.getName() << "(uint16_t Opcode";
490 if (ValueCols
.size() > 1) {
491 for (Init
*CF
: ColFields
->getValues()) {
492 std::string ColName
= CF
->getAsUnquotedString();
493 OS
<< ", enum " << ColName
<< " in" << ColName
<< ") {\n";
495 } else { OS
<< ") {\n"; }
498 unsigned TableSize
= emitBinSearchTable(OS
);
500 // Emit rest of the function body.
501 emitMapFuncBody(OS
, TableSize
);
504 //===----------------------------------------------------------------------===//
505 // Emit enums for the column fields across all the instruction maps.
506 //===----------------------------------------------------------------------===//
508 static void emitEnums(raw_ostream
&OS
, RecordKeeper
&Records
) {
510 std::vector
<Record
*> InstrMapVec
;
511 InstrMapVec
= Records
.getAllDerivedDefinitions("InstrMapping");
512 std::map
<std::string
, std::vector
<Init
*> > ColFieldValueMap
;
514 // Iterate over all InstrMapping records and create a map between column
515 // fields and their possible values across all records.
516 for (Record
*CurMap
: InstrMapVec
) {
518 ColFields
= CurMap
->getValueAsListInit("ColFields");
519 ListInit
*List
= CurMap
->getValueAsListInit("ValueCols");
520 std::vector
<ListInit
*> ValueCols
;
521 unsigned ListSize
= List
->size();
523 for (unsigned j
= 0; j
< ListSize
; j
++) {
524 auto *ListJ
= cast
<ListInit
>(List
->getElement(j
));
526 if (ListJ
->size() != ColFields
->size())
527 PrintFatalError("Record `" + CurMap
->getName() + "', field "
528 "`ValueCols' entries don't match with the entries in 'ColFields' !");
529 ValueCols
.push_back(ListJ
);
532 for (unsigned j
= 0, endCF
= ColFields
->size(); j
< endCF
; j
++) {
533 for (unsigned k
= 0; k
< ListSize
; k
++){
534 std::string ColName
= ColFields
->getElement(j
)->getAsUnquotedString();
535 ColFieldValueMap
[ColName
].push_back((ValueCols
[k
])->getElement(j
));
540 for (auto &Entry
: ColFieldValueMap
) {
541 std::vector
<Init
*> FieldValues
= Entry
.second
;
543 // Delete duplicate entries from ColFieldValueMap
544 for (unsigned i
= 0; i
< FieldValues
.size() - 1; i
++) {
545 Init
*CurVal
= FieldValues
[i
];
546 for (unsigned j
= i
+1; j
< FieldValues
.size(); j
++) {
547 if (CurVal
== FieldValues
[j
]) {
548 FieldValues
.erase(FieldValues
.begin()+j
);
554 // Emit enumerated values for the column fields.
555 OS
<< "enum " << Entry
.first
<< " {\n";
556 for (unsigned i
= 0, endFV
= FieldValues
.size(); i
< endFV
; i
++) {
557 OS
<< "\t" << Entry
.first
<< "_" << FieldValues
[i
]->getAsUnquotedString();
567 //===----------------------------------------------------------------------===//
568 // Parse 'InstrMapping' records and use the information to form relationship
569 // between instructions. These relations are emitted as a tables along with the
570 // functions to query them.
571 //===----------------------------------------------------------------------===//
572 void EmitMapTable(RecordKeeper
&Records
, raw_ostream
&OS
) {
573 CodeGenTarget
Target(Records
);
574 StringRef NameSpace
= Target
.getInstNamespace();
575 std::vector
<Record
*> InstrMapVec
;
576 InstrMapVec
= Records
.getAllDerivedDefinitions("InstrMapping");
578 if (InstrMapVec
.empty())
581 OS
<< "#ifdef GET_INSTRMAP_INFO\n";
582 OS
<< "#undef GET_INSTRMAP_INFO\n";
583 OS
<< "namespace llvm {\n\n";
584 OS
<< "namespace " << NameSpace
<< " {\n\n";
586 // Emit coulumn field names and their values as enums.
587 emitEnums(OS
, Records
);
589 // Iterate over all instruction mapping records and construct relationship
590 // maps based on the information specified there.
592 for (Record
*CurMap
: InstrMapVec
) {
593 MapTableEmitter
IMap(Target
, Records
, CurMap
);
595 // Build RowInstrMap to group instructions based on their values for
596 // RowFields. In the process, also collect key instructions into
598 IMap
.buildRowInstrMap();
600 // Build MapTable to map key instructions with the corresponding column
602 IMap
.buildMapTable();
604 // Emit map tables and the functions to query them.
605 IMap
.emitTablesWithFunc(OS
);
607 OS
<< "} // end namespace " << NameSpace
<< "\n";
608 OS
<< "} // end namespace llvm\n";
609 OS
<< "#endif // GET_INSTRMAP_INFO\n\n";
612 } // End llvm namespace