1243789Sdim//===- CodeGenMapTable.cpp - Instruction Mapping Table Generator ----------===// 2243789Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6243789Sdim// 7243789Sdim//===----------------------------------------------------------------------===// 8243789Sdim// CodeGenMapTable provides functionality for the TabelGen to create 9243789Sdim// relation mapping between instructions. Relation models are defined using 10243789Sdim// InstrMapping as a base class. This file implements the functionality which 11243789Sdim// parses these definitions and generates relation maps using the information 12243789Sdim// specified there. These maps are emitted as tables in the XXXGenInstrInfo.inc 13243789Sdim// file along with the functions to query them. 14243789Sdim// 15243789Sdim// A relationship model to relate non-predicate instructions with their 16243789Sdim// predicated true/false forms can be defined as follows: 17243789Sdim// 18243789Sdim// def getPredOpcode : InstrMapping { 19243789Sdim// let FilterClass = "PredRel"; 20243789Sdim// let RowFields = ["BaseOpcode"]; 21243789Sdim// let ColFields = ["PredSense"]; 22243789Sdim// let KeyCol = ["none"]; 23243789Sdim// let ValueCols = [["true"], ["false"]]; } 24243789Sdim// 25243789Sdim// CodeGenMapTable parses this map and generates a table in XXXGenInstrInfo.inc 26243789Sdim// file that contains the instructions modeling this relationship. This table 27243789Sdim// is defined in the function 28243789Sdim// "int getPredOpcode(uint16_t Opcode, enum PredSense inPredSense)" 29243789Sdim// that can be used to retrieve the predicated form of the instruction by 30243789Sdim// passing its opcode value and the predicate sense (true/false) of the desired 31243789Sdim// instruction as arguments. 32243789Sdim// 33243789Sdim// Short description of the algorithm: 34243789Sdim// 35243789Sdim// 1) Iterate through all the records that derive from "InstrMapping" class. 36243789Sdim// 2) For each record, filter out instructions based on the FilterClass value. 37243789Sdim// 3) Iterate through this set of instructions and insert them into 38243789Sdim// RowInstrMap map based on their RowFields values. RowInstrMap is keyed by the 39243789Sdim// vector of RowFields values and contains vectors of Records (instructions) as 40243789Sdim// values. RowFields is a list of fields that are required to have the same 41243789Sdim// values for all the instructions appearing in the same row of the relation 42243789Sdim// table. All the instructions in a given row of the relation table have some 43243789Sdim// sort of relationship with the key instruction defined by the corresponding 44243789Sdim// relationship model. 45243789Sdim// 46243789Sdim// Ex: RowInstrMap(RowVal1, RowVal2, ...) -> [Instr1, Instr2, Instr3, ... ] 47243789Sdim// Here Instr1, Instr2, Instr3 have same values (RowVal1, RowVal2) for 48243789Sdim// RowFields. These groups of instructions are later matched against ValueCols 49243789Sdim// to determine the column they belong to, if any. 50243789Sdim// 51243789Sdim// While building the RowInstrMap map, collect all the key instructions in 52243789Sdim// KeyInstrVec. These are the instructions having the same values as KeyCol 53243789Sdim// for all the fields listed in ColFields. 54243789Sdim// 55243789Sdim// For Example: 56243789Sdim// 57243789Sdim// Relate non-predicate instructions with their predicated true/false forms. 58243789Sdim// 59243789Sdim// def getPredOpcode : InstrMapping { 60243789Sdim// let FilterClass = "PredRel"; 61243789Sdim// let RowFields = ["BaseOpcode"]; 62243789Sdim// let ColFields = ["PredSense"]; 63243789Sdim// let KeyCol = ["none"]; 64243789Sdim// let ValueCols = [["true"], ["false"]]; } 65243789Sdim// 66243789Sdim// Here, only instructions that have "none" as PredSense will be selected as key 67243789Sdim// instructions. 68243789Sdim// 69243789Sdim// 4) For each key instruction, get the group of instructions that share the 70243789Sdim// same key-value as the key instruction from RowInstrMap. Iterate over the list 71243789Sdim// of columns in ValueCols (it is defined as a list<list<string> >. Therefore, 72243789Sdim// it can specify multi-column relationships). For each column, find the 73243789Sdim// instruction from the group that matches all the values for the column. 74243789Sdim// Multiple matches are not allowed. 75243789Sdim// 76243789Sdim//===----------------------------------------------------------------------===// 77243789Sdim 78243789Sdim#include "CodeGenTarget.h" 79243789Sdim#include "llvm/Support/Format.h" 80243789Sdim#include "llvm/TableGen/Error.h" 81243789Sdimusing namespace llvm; 82243789Sdimtypedef std::map<std::string, std::vector<Record*> > InstrRelMapTy; 83243789Sdim 84243789Sdimtypedef std::map<std::vector<Init*>, std::vector<Record*> > RowInstrMapTy; 85243789Sdim 86243789Sdimnamespace { 87243789Sdim 88243789Sdim//===----------------------------------------------------------------------===// 89243789Sdim// This class is used to represent InstrMapping class defined in Target.td file. 90243789Sdimclass InstrMap { 91243789Sdimprivate: 92243789Sdim std::string Name; 93243789Sdim std::string FilterClass; 94243789Sdim ListInit *RowFields; 95243789Sdim ListInit *ColFields; 96243789Sdim ListInit *KeyCol; 97243789Sdim std::vector<ListInit*> ValueCols; 98243789Sdim 99243789Sdimpublic: 100243789Sdim InstrMap(Record* MapRec) { 101243789Sdim Name = MapRec->getName(); 102243789Sdim 103243789Sdim // FilterClass - It's used to reduce the search space only to the 104243789Sdim // instructions that define the kind of relationship modeled by 105243789Sdim // this InstrMapping object/record. 106243789Sdim const RecordVal *Filter = MapRec->getValue("FilterClass"); 107243789Sdim FilterClass = Filter->getValue()->getAsUnquotedString(); 108243789Sdim 109243789Sdim // List of fields/attributes that need to be same across all the 110243789Sdim // instructions in a row of the relation table. 111243789Sdim RowFields = MapRec->getValueAsListInit("RowFields"); 112243789Sdim 113243789Sdim // List of fields/attributes that are constant across all the instruction 114243789Sdim // in a column of the relation table. Ex: ColFields = 'predSense' 115243789Sdim ColFields = MapRec->getValueAsListInit("ColFields"); 116243789Sdim 117243789Sdim // Values for the fields/attributes listed in 'ColFields'. 118276479Sdim // Ex: KeyCol = 'noPred' -- key instruction is non-predicated 119243789Sdim KeyCol = MapRec->getValueAsListInit("KeyCol"); 120243789Sdim 121243789Sdim // List of values for the fields/attributes listed in 'ColFields', one for 122243789Sdim // each column in the relation table. 123243789Sdim // 124243789Sdim // Ex: ValueCols = [['true'],['false']] -- it results two columns in the 125243789Sdim // table. First column requires all the instructions to have predSense 126243789Sdim // set to 'true' and second column requires it to be 'false'. 127243789Sdim ListInit *ColValList = MapRec->getValueAsListInit("ValueCols"); 128243789Sdim 129243789Sdim // Each instruction map must specify at least one column for it to be valid. 130288943Sdim if (ColValList->empty()) 131243789Sdim PrintFatalError(MapRec->getLoc(), "InstrMapping record `" + 132243789Sdim MapRec->getName() + "' has empty " + "`ValueCols' field!"); 133243789Sdim 134288943Sdim for (Init *I : ColValList->getValues()) { 135360784Sdim auto *ColI = cast<ListInit>(I); 136243789Sdim 137243789Sdim // Make sure that all the sub-lists in 'ValueCols' have same number of 138243789Sdim // elements as the fields in 'ColFields'. 139288943Sdim if (ColI->size() != ColFields->size()) 140243789Sdim PrintFatalError(MapRec->getLoc(), "Record `" + MapRec->getName() + 141243789Sdim "', field `ValueCols' entries don't match with " + 142243789Sdim " the entries in 'ColFields'!"); 143243789Sdim ValueCols.push_back(ColI); 144243789Sdim } 145243789Sdim } 146243789Sdim 147243789Sdim std::string getName() const { 148243789Sdim return Name; 149243789Sdim } 150243789Sdim 151243789Sdim std::string getFilterClass() { 152243789Sdim return FilterClass; 153243789Sdim } 154243789Sdim 155243789Sdim ListInit *getRowFields() const { 156243789Sdim return RowFields; 157243789Sdim } 158243789Sdim 159243789Sdim ListInit *getColFields() const { 160243789Sdim return ColFields; 161243789Sdim } 162243789Sdim 163243789Sdim ListInit *getKeyCol() const { 164243789Sdim return KeyCol; 165243789Sdim } 166243789Sdim 167243789Sdim const std::vector<ListInit*> &getValueCols() const { 168243789Sdim return ValueCols; 169243789Sdim } 170243789Sdim}; 171360784Sdim} // end anonymous namespace 172243789Sdim 173243789Sdim 174243789Sdim//===----------------------------------------------------------------------===// 175243789Sdim// class MapTableEmitter : It builds the instruction relation maps using 176243789Sdim// the information provided in InstrMapping records. It outputs these 177243789Sdim// relationship maps as tables into XXXGenInstrInfo.inc file along with the 178243789Sdim// functions to query them. 179243789Sdim 180243789Sdimnamespace { 181243789Sdimclass MapTableEmitter { 182243789Sdimprivate: 183243789Sdim// std::string TargetName; 184243789Sdim const CodeGenTarget &Target; 185243789Sdim // InstrMapDesc - InstrMapping record to be processed. 186243789Sdim InstrMap InstrMapDesc; 187243789Sdim 188243789Sdim // InstrDefs - list of instructions filtered using FilterClass defined 189243789Sdim // in InstrMapDesc. 190243789Sdim std::vector<Record*> InstrDefs; 191243789Sdim 192243789Sdim // RowInstrMap - maps RowFields values to the instructions. It's keyed by the 193243789Sdim // values of the row fields and contains vector of records as values. 194243789Sdim RowInstrMapTy RowInstrMap; 195243789Sdim 196243789Sdim // KeyInstrVec - list of key instructions. 197243789Sdim std::vector<Record*> KeyInstrVec; 198243789Sdim DenseMap<Record*, std::vector<Record*> > MapTable; 199243789Sdim 200243789Sdimpublic: 201243789Sdim MapTableEmitter(CodeGenTarget &Target, RecordKeeper &Records, Record *IMRec): 202243789Sdim Target(Target), InstrMapDesc(IMRec) { 203243789Sdim const std::string FilterClass = InstrMapDesc.getFilterClass(); 204243789Sdim InstrDefs = Records.getAllDerivedDefinitions(FilterClass); 205243789Sdim } 206243789Sdim 207243789Sdim void buildRowInstrMap(); 208243789Sdim 209243789Sdim // Returns true if an instruction is a key instruction, i.e., its ColFields 210243789Sdim // have same values as KeyCol. 211243789Sdim bool isKeyColInstr(Record* CurInstr); 212243789Sdim 213243789Sdim // Find column instruction corresponding to a key instruction based on the 214243789Sdim // constraints for that column. 215243789Sdim Record *getInstrForColumn(Record *KeyInstr, ListInit *CurValueCol); 216243789Sdim 217243789Sdim // Find column instructions for each key instruction based 218243789Sdim // on ValueCols and store them into MapTable. 219243789Sdim void buildMapTable(); 220243789Sdim 221243789Sdim void emitBinSearch(raw_ostream &OS, unsigned TableSize); 222243789Sdim void emitTablesWithFunc(raw_ostream &OS); 223243789Sdim unsigned emitBinSearchTable(raw_ostream &OS); 224243789Sdim 225243789Sdim // Lookup functions to query binary search tables. 226243789Sdim void emitMapFuncBody(raw_ostream &OS, unsigned TableSize); 227243789Sdim 228243789Sdim}; 229360784Sdim} // end anonymous namespace 230243789Sdim 231243789Sdim 232243789Sdim//===----------------------------------------------------------------------===// 233243789Sdim// Process all the instructions that model this relation (alreday present in 234243789Sdim// InstrDefs) and insert them into RowInstrMap which is keyed by the values of 235243789Sdim// the fields listed as RowFields. It stores vectors of records as values. 236243789Sdim// All the related instructions have the same values for the RowFields thus are 237243789Sdim// part of the same key-value pair. 238243789Sdim//===----------------------------------------------------------------------===// 239243789Sdim 240243789Sdimvoid MapTableEmitter::buildRowInstrMap() { 241288943Sdim for (Record *CurInstr : InstrDefs) { 242243789Sdim std::vector<Init*> KeyValue; 243243789Sdim ListInit *RowFields = InstrMapDesc.getRowFields(); 244288943Sdim for (Init *RowField : RowFields->getValues()) { 245341825Sdim RecordVal *RecVal = CurInstr->getValue(RowField); 246341825Sdim if (RecVal == nullptr) 247341825Sdim PrintFatalError(CurInstr->getLoc(), "No value " + 248341825Sdim RowField->getAsString() + " found in \"" + 249341825Sdim CurInstr->getName() + "\" instruction description."); 250341825Sdim Init *CurInstrVal = RecVal->getValue(); 251243789Sdim KeyValue.push_back(CurInstrVal); 252243789Sdim } 253243789Sdim 254243789Sdim // Collect key instructions into KeyInstrVec. Later, these instructions are 255243789Sdim // processed to assign column position to the instructions sharing 256243789Sdim // their KeyValue in RowInstrMap. 257243789Sdim if (isKeyColInstr(CurInstr)) 258243789Sdim KeyInstrVec.push_back(CurInstr); 259243789Sdim 260243789Sdim RowInstrMap[KeyValue].push_back(CurInstr); 261243789Sdim } 262243789Sdim} 263243789Sdim 264243789Sdim//===----------------------------------------------------------------------===// 265243789Sdim// Return true if an instruction is a KeyCol instruction. 266243789Sdim//===----------------------------------------------------------------------===// 267243789Sdim 268243789Sdimbool MapTableEmitter::isKeyColInstr(Record* CurInstr) { 269243789Sdim ListInit *ColFields = InstrMapDesc.getColFields(); 270243789Sdim ListInit *KeyCol = InstrMapDesc.getKeyCol(); 271243789Sdim 272243789Sdim // Check if the instruction is a KeyCol instruction. 273243789Sdim bool MatchFound = true; 274288943Sdim for (unsigned j = 0, endCF = ColFields->size(); 275243789Sdim (j < endCF) && MatchFound; j++) { 276243789Sdim RecordVal *ColFieldName = CurInstr->getValue(ColFields->getElement(j)); 277243789Sdim std::string CurInstrVal = ColFieldName->getValue()->getAsUnquotedString(); 278243789Sdim std::string KeyColValue = KeyCol->getElement(j)->getAsUnquotedString(); 279243789Sdim MatchFound = (CurInstrVal == KeyColValue); 280243789Sdim } 281243789Sdim return MatchFound; 282243789Sdim} 283243789Sdim 284243789Sdim//===----------------------------------------------------------------------===// 285243789Sdim// Build a map to link key instructions with the column instructions arranged 286243789Sdim// according to their column positions. 287243789Sdim//===----------------------------------------------------------------------===// 288243789Sdim 289243789Sdimvoid MapTableEmitter::buildMapTable() { 290243789Sdim // Find column instructions for a given key based on the ColField 291243789Sdim // constraints. 292243789Sdim const std::vector<ListInit*> &ValueCols = InstrMapDesc.getValueCols(); 293243789Sdim unsigned NumOfCols = ValueCols.size(); 294288943Sdim for (Record *CurKeyInstr : KeyInstrVec) { 295243789Sdim std::vector<Record*> ColInstrVec(NumOfCols); 296243789Sdim 297243789Sdim // Find the column instruction based on the constraints for the column. 298243789Sdim for (unsigned ColIdx = 0; ColIdx < NumOfCols; ColIdx++) { 299243789Sdim ListInit *CurValueCol = ValueCols[ColIdx]; 300243789Sdim Record *ColInstr = getInstrForColumn(CurKeyInstr, CurValueCol); 301243789Sdim ColInstrVec[ColIdx] = ColInstr; 302243789Sdim } 303243789Sdim MapTable[CurKeyInstr] = ColInstrVec; 304243789Sdim } 305243789Sdim} 306243789Sdim 307243789Sdim//===----------------------------------------------------------------------===// 308243789Sdim// Find column instruction based on the constraints for that column. 309243789Sdim//===----------------------------------------------------------------------===// 310243789Sdim 311243789SdimRecord *MapTableEmitter::getInstrForColumn(Record *KeyInstr, 312243789Sdim ListInit *CurValueCol) { 313243789Sdim ListInit *RowFields = InstrMapDesc.getRowFields(); 314243789Sdim std::vector<Init*> KeyValue; 315243789Sdim 316243789Sdim // Construct KeyValue using KeyInstr's values for RowFields. 317288943Sdim for (Init *RowField : RowFields->getValues()) { 318288943Sdim Init *KeyInstrVal = KeyInstr->getValue(RowField)->getValue(); 319243789Sdim KeyValue.push_back(KeyInstrVal); 320243789Sdim } 321243789Sdim 322243789Sdim // Get all the instructions that share the same KeyValue as the KeyInstr 323243789Sdim // in RowInstrMap. We search through these instructions to find a match 324243789Sdim // for the current column, i.e., the instruction which has the same values 325243789Sdim // as CurValueCol for all the fields in ColFields. 326243789Sdim const std::vector<Record*> &RelatedInstrVec = RowInstrMap[KeyValue]; 327243789Sdim 328243789Sdim ListInit *ColFields = InstrMapDesc.getColFields(); 329276479Sdim Record *MatchInstr = nullptr; 330243789Sdim 331243789Sdim for (unsigned i = 0, e = RelatedInstrVec.size(); i < e; i++) { 332243789Sdim bool MatchFound = true; 333243789Sdim Record *CurInstr = RelatedInstrVec[i]; 334288943Sdim for (unsigned j = 0, endCF = ColFields->size(); 335243789Sdim (j < endCF) && MatchFound; j++) { 336243789Sdim Init *ColFieldJ = ColFields->getElement(j); 337243789Sdim Init *CurInstrInit = CurInstr->getValue(ColFieldJ)->getValue(); 338243789Sdim std::string CurInstrVal = CurInstrInit->getAsUnquotedString(); 339243789Sdim Init *ColFieldJVallue = CurValueCol->getElement(j); 340243789Sdim MatchFound = (CurInstrVal == ColFieldJVallue->getAsUnquotedString()); 341243789Sdim } 342243789Sdim 343243789Sdim if (MatchFound) { 344309124Sdim if (MatchInstr) { 345309124Sdim // Already had a match 346243789Sdim // Error if multiple matches are found for a column. 347309124Sdim std::string KeyValueStr; 348309124Sdim for (Init *Value : KeyValue) { 349309124Sdim if (!KeyValueStr.empty()) 350309124Sdim KeyValueStr += ", "; 351309124Sdim KeyValueStr += Value->getAsString(); 352309124Sdim } 353309124Sdim 354243789Sdim PrintFatalError("Multiple matches found for `" + KeyInstr->getName() + 355309124Sdim "', for the relation `" + InstrMapDesc.getName() + "', row fields [" + 356309124Sdim KeyValueStr + "], column `" + CurValueCol->getAsString() + "'"); 357309124Sdim } 358243789Sdim MatchInstr = CurInstr; 359243789Sdim } 360243789Sdim } 361243789Sdim return MatchInstr; 362243789Sdim} 363243789Sdim 364243789Sdim//===----------------------------------------------------------------------===// 365243789Sdim// Emit one table per relation. Only instructions with a valid relation of a 366243789Sdim// given type are included in the table sorted by their enum values (opcodes). 367243789Sdim// Binary search is used for locating instructions in the table. 368243789Sdim//===----------------------------------------------------------------------===// 369243789Sdim 370243789Sdimunsigned MapTableEmitter::emitBinSearchTable(raw_ostream &OS) { 371243789Sdim 372309124Sdim ArrayRef<const CodeGenInstruction*> NumberedInstructions = 373243789Sdim Target.getInstructionsByEnumValue(); 374321369Sdim StringRef Namespace = Target.getInstNamespace(); 375243789Sdim const std::vector<ListInit*> &ValueCols = InstrMapDesc.getValueCols(); 376243789Sdim unsigned NumCol = ValueCols.size(); 377243789Sdim unsigned TotalNumInstr = NumberedInstructions.size(); 378243789Sdim unsigned TableSize = 0; 379243789Sdim 380243789Sdim OS << "static const uint16_t "<<InstrMapDesc.getName(); 381243789Sdim // Number of columns in the table are NumCol+1 because key instructions are 382243789Sdim // emitted as first column. 383243789Sdim OS << "Table[]["<< NumCol+1 << "] = {\n"; 384243789Sdim for (unsigned i = 0; i < TotalNumInstr; i++) { 385243789Sdim Record *CurInstr = NumberedInstructions[i]->TheDef; 386243789Sdim std::vector<Record*> ColInstrs = MapTable[CurInstr]; 387243789Sdim std::string OutStr(""); 388243789Sdim unsigned RelExists = 0; 389288943Sdim if (!ColInstrs.empty()) { 390243789Sdim for (unsigned j = 0; j < NumCol; j++) { 391276479Sdim if (ColInstrs[j] != nullptr) { 392243789Sdim RelExists = 1; 393243789Sdim OutStr += ", "; 394321369Sdim OutStr += Namespace; 395243789Sdim OutStr += "::"; 396243789Sdim OutStr += ColInstrs[j]->getName(); 397276479Sdim } else { OutStr += ", (uint16_t)-1U";} 398243789Sdim } 399243789Sdim 400243789Sdim if (RelExists) { 401321369Sdim OS << " { " << Namespace << "::" << CurInstr->getName(); 402243789Sdim OS << OutStr <<" },\n"; 403243789Sdim TableSize++; 404243789Sdim } 405243789Sdim } 406243789Sdim } 407243789Sdim if (!TableSize) { 408321369Sdim OS << " { " << Namespace << "::" << "INSTRUCTION_LIST_END, "; 409321369Sdim OS << Namespace << "::" << "INSTRUCTION_LIST_END }"; 410243789Sdim } 411243789Sdim OS << "}; // End of " << InstrMapDesc.getName() << "Table\n\n"; 412243789Sdim return TableSize; 413243789Sdim} 414243789Sdim 415243789Sdim//===----------------------------------------------------------------------===// 416243789Sdim// Emit binary search algorithm as part of the functions used to query 417243789Sdim// relation tables. 418243789Sdim//===----------------------------------------------------------------------===// 419243789Sdim 420243789Sdimvoid MapTableEmitter::emitBinSearch(raw_ostream &OS, unsigned TableSize) { 421243789Sdim OS << " unsigned mid;\n"; 422243789Sdim OS << " unsigned start = 0;\n"; 423243789Sdim OS << " unsigned end = " << TableSize << ";\n"; 424243789Sdim OS << " while (start < end) {\n"; 425243789Sdim OS << " mid = start + (end - start)/2;\n"; 426243789Sdim OS << " if (Opcode == " << InstrMapDesc.getName() << "Table[mid][0]) {\n"; 427243789Sdim OS << " break;\n"; 428243789Sdim OS << " }\n"; 429243789Sdim OS << " if (Opcode < " << InstrMapDesc.getName() << "Table[mid][0])\n"; 430243789Sdim OS << " end = mid;\n"; 431243789Sdim OS << " else\n"; 432243789Sdim OS << " start = mid + 1;\n"; 433243789Sdim OS << " }\n"; 434243789Sdim OS << " if (start == end)\n"; 435243789Sdim OS << " return -1; // Instruction doesn't exist in this table.\n\n"; 436243789Sdim} 437243789Sdim 438243789Sdim//===----------------------------------------------------------------------===// 439243789Sdim// Emit functions to query relation tables. 440243789Sdim//===----------------------------------------------------------------------===// 441243789Sdim 442243789Sdimvoid MapTableEmitter::emitMapFuncBody(raw_ostream &OS, 443243789Sdim unsigned TableSize) { 444243789Sdim 445243789Sdim ListInit *ColFields = InstrMapDesc.getColFields(); 446243789Sdim const std::vector<ListInit*> &ValueCols = InstrMapDesc.getValueCols(); 447243789Sdim 448243789Sdim // Emit binary search algorithm to locate instructions in the 449243789Sdim // relation table. If found, return opcode value from the appropriate column 450243789Sdim // of the table. 451243789Sdim emitBinSearch(OS, TableSize); 452243789Sdim 453243789Sdim if (ValueCols.size() > 1) { 454243789Sdim for (unsigned i = 0, e = ValueCols.size(); i < e; i++) { 455243789Sdim ListInit *ColumnI = ValueCols[i]; 456288943Sdim for (unsigned j = 0, ColSize = ColumnI->size(); j < ColSize; ++j) { 457243789Sdim std::string ColName = ColFields->getElement(j)->getAsUnquotedString(); 458243789Sdim OS << " if (in" << ColName; 459243789Sdim OS << " == "; 460243789Sdim OS << ColName << "_" << ColumnI->getElement(j)->getAsUnquotedString(); 461288943Sdim if (j < ColumnI->size() - 1) OS << " && "; 462243789Sdim else OS << ")\n"; 463243789Sdim } 464243789Sdim OS << " return " << InstrMapDesc.getName(); 465243789Sdim OS << "Table[mid]["<<i+1<<"];\n"; 466243789Sdim } 467243789Sdim OS << " return -1;"; 468243789Sdim } 469243789Sdim else 470243789Sdim OS << " return " << InstrMapDesc.getName() << "Table[mid][1];\n"; 471243789Sdim 472243789Sdim OS <<"}\n\n"; 473243789Sdim} 474243789Sdim 475243789Sdim//===----------------------------------------------------------------------===// 476243789Sdim// Emit relation tables and the functions to query them. 477243789Sdim//===----------------------------------------------------------------------===// 478243789Sdim 479243789Sdimvoid MapTableEmitter::emitTablesWithFunc(raw_ostream &OS) { 480243789Sdim 481243789Sdim // Emit function name and the input parameters : mostly opcode value of the 482243789Sdim // current instruction. However, if a table has multiple columns (more than 2 483243789Sdim // since first column is used for the key instructions), then we also need 484243789Sdim // to pass another input to indicate the column to be selected. 485243789Sdim 486243789Sdim ListInit *ColFields = InstrMapDesc.getColFields(); 487243789Sdim const std::vector<ListInit*> &ValueCols = InstrMapDesc.getValueCols(); 488296417Sdim OS << "// "<< InstrMapDesc.getName() << "\nLLVM_READONLY\n"; 489243789Sdim OS << "int "<< InstrMapDesc.getName() << "(uint16_t Opcode"; 490243789Sdim if (ValueCols.size() > 1) { 491288943Sdim for (Init *CF : ColFields->getValues()) { 492288943Sdim std::string ColName = CF->getAsUnquotedString(); 493243789Sdim OS << ", enum " << ColName << " in" << ColName << ") {\n"; 494243789Sdim } 495243789Sdim } else { OS << ") {\n"; } 496243789Sdim 497243789Sdim // Emit map table. 498243789Sdim unsigned TableSize = emitBinSearchTable(OS); 499243789Sdim 500243789Sdim // Emit rest of the function body. 501243789Sdim emitMapFuncBody(OS, TableSize); 502243789Sdim} 503243789Sdim 504243789Sdim//===----------------------------------------------------------------------===// 505243789Sdim// Emit enums for the column fields across all the instruction maps. 506243789Sdim//===----------------------------------------------------------------------===// 507243789Sdim 508243789Sdimstatic void emitEnums(raw_ostream &OS, RecordKeeper &Records) { 509243789Sdim 510243789Sdim std::vector<Record*> InstrMapVec; 511243789Sdim InstrMapVec = Records.getAllDerivedDefinitions("InstrMapping"); 512243789Sdim std::map<std::string, std::vector<Init*> > ColFieldValueMap; 513243789Sdim 514243789Sdim // Iterate over all InstrMapping records and create a map between column 515243789Sdim // fields and their possible values across all records. 516309124Sdim for (Record *CurMap : InstrMapVec) { 517243789Sdim ListInit *ColFields; 518243789Sdim ColFields = CurMap->getValueAsListInit("ColFields"); 519243789Sdim ListInit *List = CurMap->getValueAsListInit("ValueCols"); 520243789Sdim std::vector<ListInit*> ValueCols; 521288943Sdim unsigned ListSize = List->size(); 522243789Sdim 523243789Sdim for (unsigned j = 0; j < ListSize; j++) { 524360784Sdim auto *ListJ = cast<ListInit>(List->getElement(j)); 525243789Sdim 526288943Sdim if (ListJ->size() != ColFields->size()) 527243789Sdim PrintFatalError("Record `" + CurMap->getName() + "', field " 528243789Sdim "`ValueCols' entries don't match with the entries in 'ColFields' !"); 529243789Sdim ValueCols.push_back(ListJ); 530243789Sdim } 531243789Sdim 532288943Sdim for (unsigned j = 0, endCF = ColFields->size(); j < endCF; j++) { 533243789Sdim for (unsigned k = 0; k < ListSize; k++){ 534243789Sdim std::string ColName = ColFields->getElement(j)->getAsUnquotedString(); 535243789Sdim ColFieldValueMap[ColName].push_back((ValueCols[k])->getElement(j)); 536243789Sdim } 537243789Sdim } 538243789Sdim } 539243789Sdim 540309124Sdim for (auto &Entry : ColFieldValueMap) { 541309124Sdim std::vector<Init*> FieldValues = Entry.second; 542243789Sdim 543243789Sdim // Delete duplicate entries from ColFieldValueMap 544249423Sdim for (unsigned i = 0; i < FieldValues.size() - 1; i++) { 545243789Sdim Init *CurVal = FieldValues[i]; 546249423Sdim for (unsigned j = i+1; j < FieldValues.size(); j++) { 547243789Sdim if (CurVal == FieldValues[j]) { 548243789Sdim FieldValues.erase(FieldValues.begin()+j); 549314564Sdim --j; 550243789Sdim } 551243789Sdim } 552243789Sdim } 553243789Sdim 554243789Sdim // Emit enumerated values for the column fields. 555309124Sdim OS << "enum " << Entry.first << " {\n"; 556249423Sdim for (unsigned i = 0, endFV = FieldValues.size(); i < endFV; i++) { 557309124Sdim OS << "\t" << Entry.first << "_" << FieldValues[i]->getAsUnquotedString(); 558249423Sdim if (i != endFV - 1) 559243789Sdim OS << ",\n"; 560243789Sdim else 561243789Sdim OS << "\n};\n\n"; 562243789Sdim } 563243789Sdim } 564243789Sdim} 565243789Sdim 566243789Sdimnamespace llvm { 567243789Sdim//===----------------------------------------------------------------------===// 568243789Sdim// Parse 'InstrMapping' records and use the information to form relationship 569243789Sdim// between instructions. These relations are emitted as a tables along with the 570243789Sdim// functions to query them. 571243789Sdim//===----------------------------------------------------------------------===// 572243789Sdimvoid EmitMapTable(RecordKeeper &Records, raw_ostream &OS) { 573243789Sdim CodeGenTarget Target(Records); 574321369Sdim StringRef NameSpace = Target.getInstNamespace(); 575243789Sdim std::vector<Record*> InstrMapVec; 576243789Sdim InstrMapVec = Records.getAllDerivedDefinitions("InstrMapping"); 577243789Sdim 578288943Sdim if (InstrMapVec.empty()) 579243789Sdim return; 580243789Sdim 581243789Sdim OS << "#ifdef GET_INSTRMAP_INFO\n"; 582243789Sdim OS << "#undef GET_INSTRMAP_INFO\n"; 583243789Sdim OS << "namespace llvm {\n\n"; 584321369Sdim OS << "namespace " << NameSpace << " {\n\n"; 585243789Sdim 586243789Sdim // Emit coulumn field names and their values as enums. 587243789Sdim emitEnums(OS, Records); 588243789Sdim 589243789Sdim // Iterate over all instruction mapping records and construct relationship 590243789Sdim // maps based on the information specified there. 591243789Sdim // 592309124Sdim for (Record *CurMap : InstrMapVec) { 593309124Sdim MapTableEmitter IMap(Target, Records, CurMap); 594243789Sdim 595243789Sdim // Build RowInstrMap to group instructions based on their values for 596243789Sdim // RowFields. In the process, also collect key instructions into 597243789Sdim // KeyInstrVec. 598243789Sdim IMap.buildRowInstrMap(); 599243789Sdim 600243789Sdim // Build MapTable to map key instructions with the corresponding column 601243789Sdim // instructions. 602243789Sdim IMap.buildMapTable(); 603243789Sdim 604243789Sdim // Emit map tables and the functions to query them. 605243789Sdim IMap.emitTablesWithFunc(OS); 606243789Sdim } 607360784Sdim OS << "} // end namespace " << NameSpace << "\n"; 608360784Sdim OS << "} // end namespace llvm\n"; 609243789Sdim OS << "#endif // GET_INSTRMAP_INFO\n\n"; 610243789Sdim} 611243789Sdim 612243789Sdim} // End llvm namespace 613