578 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8// CodeGenMapTable provides functionality for the TableGen to create9// relation mapping between instructions. Relation models are defined using10// InstrMapping as a base class. This file implements the functionality which11// parses these definitions and generates relation maps using the information12// specified there. These maps are emitted as tables in the XXXGenInstrInfo.inc13// file along with the functions to query them.14//15// A relationship model to relate non-predicate instructions with their16// 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.inc26// file that contains the instructions modeling this relationship. This table27// is defined in the function28// "int getPredOpcode(uint16_t Opcode, enum PredSense inPredSense)"29// that can be used to retrieve the predicated form of the instruction by30// passing its opcode value and the predicate sense (true/false) of the desired31// 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 into38// RowInstrMap map based on their RowFields values. RowInstrMap is keyed by the39// vector of RowFields values and contains vectors of Records (instructions) as40// values. RowFields is a list of fields that are required to have the same41// values for all the instructions appearing in the same row of the relation42// table. All the instructions in a given row of the relation table have some43// sort of relationship with the key instruction defined by the corresponding44// relationship model.45//46// Ex: RowInstrMap(RowVal1, RowVal2, ...) -> [Instr1, Instr2, Instr3, ... ]47// Here Instr1, Instr2, Instr3 have same values (RowVal1, RowVal2) for48// RowFields. These groups of instructions are later matched against ValueCols49// to determine the column they belong to, if any.50//51// While building the RowInstrMap map, collect all the key instructions in52// KeyInstrVec. These are the instructions having the same values as KeyCol53// 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 key67// instructions.68//69// 4) For each key instruction, get the group of instructions that share the70// same key-value as the key instruction from RowInstrMap. Iterate over the list71// of columns in ValueCols (it is defined as a list<list<string> >. Therefore,72// it can specify multi-column relationships). For each column, find the73// 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/CodeGenHelpers.h"84#include "llvm/TableGen/Error.h"85#include "llvm/TableGen/Record.h"86 87using namespace llvm;88using InstrRelMapTy = std::map<std::string, std::vector<const Record *>>;89using RowInstrMapTy =90 std::map<std::vector<const Init *>, std::vector<const Record *>>;91 92namespace {93 94//===----------------------------------------------------------------------===//95// This class is used to represent InstrMapping class defined in Target.td file.96class InstrMap {97private:98 std::string Name;99 std::string FilterClass;100 const ListInit *RowFields;101 const ListInit *ColFields;102 const ListInit *KeyCol;103 std::vector<const ListInit *> ValueCols;104 105public:106 InstrMap(const Record *MapRec) {107 Name = MapRec->getName().str();108 109 // FilterClass - It's used to reduce the search space only to the110 // instructions that define the kind of relationship modeled by111 // this InstrMapping object/record.112 const RecordVal *Filter = MapRec->getValue("FilterClass");113 FilterClass = Filter->getValue()->getAsUnquotedString();114 115 // List of fields/attributes that need to be same across all the116 // instructions in a row of the relation table.117 RowFields = MapRec->getValueAsListInit("RowFields");118 119 // List of fields/attributes that are constant across all the instruction120 // in a column of the relation table. Ex: ColFields = 'predSense'121 ColFields = MapRec->getValueAsListInit("ColFields");122 123 // Values for the fields/attributes listed in 'ColFields'.124 // Ex: KeyCol = 'noPred' -- key instruction is non-predicated125 KeyCol = MapRec->getValueAsListInit("KeyCol");126 127 // List of values for the fields/attributes listed in 'ColFields', one for128 // each column in the relation table.129 //130 // Ex: ValueCols = [['true'],['false']] -- it results two columns in the131 // table. First column requires all the instructions to have predSense132 // set to 'true' and second column requires it to be 'false'.133 const ListInit *ColValList = MapRec->getValueAsListInit("ValueCols");134 135 // Each instruction map must specify at least one column for it to be valid.136 if (ColValList->empty())137 PrintFatalError(MapRec->getLoc(), "InstrMapping record `" + Name +138 "' has empty " +139 "`ValueCols' field!");140 141 for (const Init *I : ColValList->getElements()) {142 const auto *ColI = cast<ListInit>(I);143 144 // Make sure that all the sub-lists in 'ValueCols' have same number of145 // elements as the fields in 'ColFields'.146 if (ColI->size() != ColFields->size())147 PrintFatalError(MapRec->getLoc(),148 "Record `" + Name +149 "', field `ValueCols' entries don't match with " +150 " the entries in 'ColFields'!");151 ValueCols.push_back(ColI);152 }153 }154 155 const std::string &getName() const { return Name; }156 const std::string &getFilterClass() const { return FilterClass; }157 const ListInit *getRowFields() const { return RowFields; }158 const ListInit *getColFields() const { return ColFields; }159 const ListInit *getKeyCol() const { return KeyCol; }160 ArrayRef<const ListInit *> getValueCols() const { return ValueCols; }161};162 163//===----------------------------------------------------------------------===//164// class MapTableEmitter : It builds the instruction relation maps using165// the information provided in InstrMapping records. It outputs these166// relationship maps as tables into XXXGenInstrInfo.inc file along with the167// functions to query them.168 169class MapTableEmitter {170private:171 // std::string TargetName;172 const CodeGenTarget &Target;173 // InstrMapDesc - InstrMapping record to be processed.174 InstrMap InstrMapDesc;175 176 // InstrDefs - list of instructions filtered using FilterClass defined177 // in InstrMapDesc.178 ArrayRef<const Record *> InstrDefs;179 180 // RowInstrMap - maps RowFields values to the instructions. It's keyed by the181 // values of the row fields and contains vector of records as values.182 RowInstrMapTy RowInstrMap;183 184 // KeyInstrVec - list of key instructions.185 std::vector<const Record *> KeyInstrVec;186 DenseMap<const Record *, std::vector<const Record *>> MapTable;187 188public:189 MapTableEmitter(const CodeGenTarget &Target, const RecordKeeper &Records,190 const Record *IMRec)191 : Target(Target), InstrMapDesc(IMRec) {192 const std::string &FilterClass = InstrMapDesc.getFilterClass();193 InstrDefs = Records.getAllDerivedDefinitions(FilterClass);194 }195 196 void buildRowInstrMap();197 198 // Returns true if an instruction is a key instruction, i.e., its ColFields199 // have same values as KeyCol.200 bool isKeyColInstr(const Record *CurInstr);201 202 // Find column instruction corresponding to a key instruction based on the203 // constraints for that column.204 const Record *getInstrForColumn(const Record *KeyInstr,205 const ListInit *CurValueCol);206 207 // Find column instructions for each key instruction based208 // on ValueCols and store them into MapTable.209 void buildMapTable();210 211 void emitBinSearch(raw_ostream &OS, unsigned TableSize);212 void emitTablesWithFunc(raw_ostream &OS);213 unsigned emitBinSearchTable(raw_ostream &OS);214 215 // Lookup functions to query binary search tables.216 void emitMapFuncBody(raw_ostream &OS, unsigned TableSize);217};218} // end anonymous namespace219 220//===----------------------------------------------------------------------===//221// Process all the instructions that model this relation (alreday present in222// InstrDefs) and insert them into RowInstrMap which is keyed by the values of223// the fields listed as RowFields. It stores vectors of records as values.224// All the related instructions have the same values for the RowFields thus are225// part of the same key-value pair.226//===----------------------------------------------------------------------===//227 228void MapTableEmitter::buildRowInstrMap() {229 for (const Record *CurInstr : InstrDefs) {230 std::vector<const Init *> KeyValue;231 const ListInit *RowFields = InstrMapDesc.getRowFields();232 for (const Init *RowField : RowFields->getElements()) {233 const RecordVal *RecVal = CurInstr->getValue(RowField);234 if (RecVal == nullptr)235 PrintFatalError(CurInstr->getLoc(),236 "No value " + RowField->getAsString() + " found in \"" +237 CurInstr->getName() +238 "\" instruction description.");239 const Init *CurInstrVal = RecVal->getValue();240 KeyValue.push_back(CurInstrVal);241 }242 243 // Collect key instructions into KeyInstrVec. Later, these instructions are244 // processed to assign column position to the instructions sharing245 // their KeyValue in RowInstrMap.246 if (isKeyColInstr(CurInstr))247 KeyInstrVec.push_back(CurInstr);248 249 RowInstrMap[KeyValue].push_back(CurInstr);250 }251}252 253//===----------------------------------------------------------------------===//254// Return true if an instruction is a KeyCol instruction.255//===----------------------------------------------------------------------===//256 257bool MapTableEmitter::isKeyColInstr(const Record *CurInstr) {258 const ListInit *ColFields = InstrMapDesc.getColFields();259 const ListInit *KeyCol = InstrMapDesc.getKeyCol();260 261 // Check if the instruction is a KeyCol instruction.262 bool MatchFound = true;263 for (unsigned J = 0, EndCf = ColFields->size(); (J < EndCf) && MatchFound;264 J++) {265 const RecordVal *ColFieldName =266 CurInstr->getValue(ColFields->getElement(J));267 std::string CurInstrVal = ColFieldName->getValue()->getAsUnquotedString();268 std::string KeyColValue = KeyCol->getElement(J)->getAsUnquotedString();269 MatchFound = CurInstrVal == KeyColValue;270 }271 return MatchFound;272}273 274//===----------------------------------------------------------------------===//275// Build a map to link key instructions with the column instructions arranged276// according to their column positions.277//===----------------------------------------------------------------------===//278 279void MapTableEmitter::buildMapTable() {280 // Find column instructions for a given key based on the ColField281 // constraints.282 ArrayRef<const ListInit *> ValueCols = InstrMapDesc.getValueCols();283 unsigned NumOfCols = ValueCols.size();284 for (const Record *CurKeyInstr : KeyInstrVec) {285 std::vector<const Record *> ColInstrVec(NumOfCols);286 287 // Find the column instruction based on the constraints for the column.288 for (unsigned ColIdx = 0; ColIdx < NumOfCols; ColIdx++) {289 const ListInit *CurValueCol = ValueCols[ColIdx];290 const Record *ColInstr = getInstrForColumn(CurKeyInstr, CurValueCol);291 ColInstrVec[ColIdx] = ColInstr;292 }293 MapTable[CurKeyInstr] = ColInstrVec;294 }295}296 297//===----------------------------------------------------------------------===//298// Find column instruction based on the constraints for that column.299//===----------------------------------------------------------------------===//300 301const Record *MapTableEmitter::getInstrForColumn(const Record *KeyInstr,302 const ListInit *CurValueCol) {303 const ListInit *RowFields = InstrMapDesc.getRowFields();304 std::vector<const Init *> KeyValue;305 306 // Construct KeyValue using KeyInstr's values for RowFields.307 for (const Init *RowField : RowFields->getElements()) {308 const Init *KeyInstrVal = KeyInstr->getValue(RowField)->getValue();309 KeyValue.push_back(KeyInstrVal);310 }311 312 // Get all the instructions that share the same KeyValue as the KeyInstr313 // in RowInstrMap. We search through these instructions to find a match314 // for the current column, i.e., the instruction which has the same values315 // as CurValueCol for all the fields in ColFields.316 ArrayRef<const Record *> RelatedInstrVec = RowInstrMap[KeyValue];317 318 const ListInit *ColFields = InstrMapDesc.getColFields();319 const Record *MatchInstr = nullptr;320 321 for (const Record *CurInstr : RelatedInstrVec) {322 bool MatchFound = true;323 for (unsigned J = 0, EndCf = ColFields->size(); (J < EndCf) && MatchFound;324 J++) {325 const Init *ColFieldJ = ColFields->getElement(J);326 const Init *CurInstrInit = CurInstr->getValue(ColFieldJ)->getValue();327 std::string CurInstrVal = CurInstrInit->getAsUnquotedString();328 const Init *ColFieldJVallue = CurValueCol->getElement(J);329 MatchFound = CurInstrVal == ColFieldJVallue->getAsUnquotedString();330 }331 332 if (MatchFound) {333 if (MatchInstr) {334 // Already had a match335 // Error if multiple matches are found for a column.336 std::string KeyValueStr;337 for (const Init *Value : KeyValue) {338 if (!KeyValueStr.empty())339 KeyValueStr += ", ";340 KeyValueStr += Value->getAsString();341 }342 343 PrintFatalError("Multiple matches found for `" + KeyInstr->getName() +344 "', for the relation `" + InstrMapDesc.getName() +345 "', row fields [" + KeyValueStr + "], column `" +346 CurValueCol->getAsString() + "'");347 }348 MatchInstr = CurInstr;349 }350 }351 return MatchInstr;352}353 354//===----------------------------------------------------------------------===//355// Emit one table per relation. Only instructions with a valid relation of a356// given type are included in the table sorted by their enum values (opcodes).357// Binary search is used for locating instructions in the table.358//===----------------------------------------------------------------------===//359 360unsigned MapTableEmitter::emitBinSearchTable(raw_ostream &OS) {361 ArrayRef<const CodeGenInstruction *> NumberedInstructions =362 Target.getInstructions();363 StringRef Namespace = Target.getInstNamespace();364 ArrayRef<const ListInit *> ValueCols = InstrMapDesc.getValueCols();365 unsigned NumCol = ValueCols.size();366 unsigned TableSize = 0;367 368 OS << " using namespace " << Namespace << ";\n";369 // Number of columns in the table are NumCol+1 because key instructions are370 // emitted as first column.371 for (const CodeGenInstruction *Inst : NumberedInstructions) {372 const Record *CurInstr = Inst->TheDef;373 ArrayRef<const Record *> ColInstrs = MapTable[CurInstr];374 if (ColInstrs.empty())375 continue;376 std::string OutStr;377 bool RelExists = false;378 for (const Record *ColInstr : ColInstrs) {379 if (ColInstr) {380 RelExists = true;381 OutStr += ", ";382 OutStr += ColInstr->getName();383 } else {384 OutStr += ", (uint16_t)-1U";385 }386 }387 388 if (RelExists) {389 if (TableSize == 0)390 OS << " static constexpr uint16_t Table[][" << NumCol + 1 << "] = {\n";391 OS << " { " << CurInstr->getName() << OutStr << " },\n";392 ++TableSize;393 }394 }395 396 if (TableSize != 0)397 OS << " }; // End of Table\n\n";398 return TableSize;399}400 401//===----------------------------------------------------------------------===//402// Emit binary search algorithm as part of the functions used to query403// relation tables.404//===----------------------------------------------------------------------===//405 406void MapTableEmitter::emitBinSearch(raw_ostream &OS, unsigned TableSize) {407 if (TableSize == 0) {408 OS << " return -1;\n";409 return;410 }411 412 OS << " unsigned mid;\n";413 OS << " unsigned start = 0;\n";414 OS << " unsigned end = " << TableSize << ";\n";415 OS << " while (start < end) {\n";416 OS << " mid = start + (end - start) / 2;\n";417 OS << " if (Opcode == Table[mid][0]) \n";418 OS << " break;\n";419 OS << " if (Opcode < Table[mid][0])\n";420 OS << " end = mid;\n";421 OS << " else\n";422 OS << " start = mid + 1;\n";423 OS << " }\n";424 OS << " if (start == end)\n";425 OS << " return -1; // Instruction doesn't exist in this table.\n\n";426}427 428//===----------------------------------------------------------------------===//429// Emit functions to query relation tables.430//===----------------------------------------------------------------------===//431 432void MapTableEmitter::emitMapFuncBody(raw_ostream &OS, unsigned TableSize) {433 const ListInit *ColFields = InstrMapDesc.getColFields();434 ArrayRef<const ListInit *> ValueCols = InstrMapDesc.getValueCols();435 436 // Emit binary search algorithm to locate instructions in the437 // relation table. If found, return opcode value from the appropriate column438 // of the table.439 emitBinSearch(OS, TableSize);440 if (TableSize == 0)441 return;442 443 if (ValueCols.size() > 1) {444 for (unsigned I = 0, E = ValueCols.size(); I < E; I++) {445 const ListInit *ColumnI = ValueCols[I];446 OS << " if (";447 for (unsigned J = 0, ColSize = ColumnI->size(); J < ColSize; ++J) {448 std::string ColName = ColFields->getElement(J)->getAsUnquotedString();449 OS << "in" << ColName;450 OS << " == ";451 OS << ColName << "_" << ColumnI->getElement(J)->getAsUnquotedString();452 if (J < ColumnI->size() - 1)453 OS << " && ";454 }455 OS << ")\n";456 OS << " return Table[mid][" << I + 1 << "];\n";457 }458 OS << " return -1;";459 } else {460 OS << " return Table[mid][1];\n";461 }462}463 464//===----------------------------------------------------------------------===//465// Emit relation tables and the functions to query them.466//===----------------------------------------------------------------------===//467 468void MapTableEmitter::emitTablesWithFunc(raw_ostream &OS) {469 // Emit function name and the input parameters : mostly opcode value of the470 // current instruction. However, if a table has multiple columns (more than 2471 // since first column is used for the key instructions), then we also need472 // to pass another input to indicate the column to be selected.473 474 const ListInit *ColFields = InstrMapDesc.getColFields();475 ArrayRef<const ListInit *> ValueCols = InstrMapDesc.getValueCols();476 OS << "// " << InstrMapDesc.getName() << "\nLLVM_READONLY\n";477 OS << "int " << InstrMapDesc.getName() << "(uint16_t Opcode";478 if (ValueCols.size() > 1) {479 for (const Init *CF : ColFields->getElements()) {480 std::string ColName = CF->getAsUnquotedString();481 OS << ", enum " << ColName << " in" << ColName;482 }483 }484 OS << ") {\n";485 486 // Emit map table.487 unsigned TableSize = emitBinSearchTable(OS);488 489 // Emit rest of the function body.490 emitMapFuncBody(OS, TableSize);491 492 OS << "}\n\n";493}494 495//===----------------------------------------------------------------------===//496// Emit enums for the column fields across all the instruction maps.497//===----------------------------------------------------------------------===//498 499static void emitEnums(raw_ostream &OS, const RecordKeeper &Records) {500 std::map<std::string, SetVector<const Init *>> ColFieldValueMap;501 502 // Iterate over all InstrMapping records and create a map between column503 // fields and their possible values across all records.504 for (const Record *CurMap :505 Records.getAllDerivedDefinitions("InstrMapping")) {506 const ListInit *ColFields = CurMap->getValueAsListInit("ColFields");507 const ListInit *List = CurMap->getValueAsListInit("ValueCols");508 std::vector<const ListInit *> ValueCols;509 510 for (const Init *Elem : *List) {511 const auto *ListJ = cast<ListInit>(Elem);512 513 if (ListJ->size() != ColFields->size())514 PrintFatalError("Record `" + CurMap->getName() +515 "', field "516 "`ValueCols' entries don't match with the entries in "517 "'ColFields' !");518 ValueCols.push_back(ListJ);519 }520 521 for (unsigned J = 0, EndCf = ColFields->size(); J < EndCf; J++) {522 std::string ColName = ColFields->getElement(J)->getAsUnquotedString();523 auto &MapEntry = ColFieldValueMap[ColName];524 for (const ListInit *List : ValueCols)525 MapEntry.insert(List->getElement(J));526 }527 }528 529 for (auto &[EnumName, FieldValues] : ColFieldValueMap) {530 // Emit enumerated values for the column fields.531 OS << "enum " << EnumName << " {\n";532 ListSeparator LS(",\n");533 for (const Init *Field : FieldValues)534 OS << LS << " " << EnumName << "_" << Field->getAsUnquotedString();535 OS << "\n};\n\n";536 }537}538 539//===----------------------------------------------------------------------===//540// Parse 'InstrMapping' records and use the information to form relationship541// between instructions. These relations are emitted as tables along with the542// functions to query them.543//===----------------------------------------------------------------------===//544void llvm::EmitMapTable(const RecordKeeper &Records, raw_ostream &OS) {545 CodeGenTarget Target(Records);546 StringRef NameSpace = Target.getInstNamespace();547 ArrayRef<const Record *> InstrMapVec =548 Records.getAllDerivedDefinitions("InstrMapping");549 550 if (InstrMapVec.empty())551 return;552 553 IfDefEmitter IfDef(OS, "GET_INSTRMAP_INFO");554 NamespaceEmitter NS(OS, ("llvm::" + NameSpace).str());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 relationship560 // 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 for566 // RowFields. In the process, also collect key instructions into567 // KeyInstrVec.568 IMap.buildRowInstrMap();569 570 // Build MapTable to map key instructions with the corresponding column571 // instructions.572 IMap.buildMapTable();573 574 // Emit map tables and the functions to query them.575 IMap.emitTablesWithFunc(OS);576 }577}578