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