CodeGenMapTable.cpp revision 276479
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. 131243789Sdim if (ColValList->getSize() == 0) 132243789Sdim PrintFatalError(MapRec->getLoc(), "InstrMapping record `" + 133243789Sdim MapRec->getName() + "' has empty " + "`ValueCols' field!"); 134243789Sdim 135243789Sdim for (unsigned i = 0, e = ColValList->getSize(); i < e; i++) { 136243789Sdim ListInit *ColI = dyn_cast<ListInit>(ColValList->getElement(i)); 137243789Sdim 138243789Sdim // Make sure that all the sub-lists in 'ValueCols' have same number of 139243789Sdim // elements as the fields in 'ColFields'. 140243789Sdim if (ColI->getSize() != ColFields->getSize()) 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() { 242243789Sdim for (unsigned i = 0, e = InstrDefs.size(); i < e; i++) { 243243789Sdim Record *CurInstr = InstrDefs[i]; 244243789Sdim std::vector<Init*> KeyValue; 245243789Sdim ListInit *RowFields = InstrMapDesc.getRowFields(); 246243789Sdim for (unsigned j = 0, endRF = RowFields->getSize(); j < endRF; j++) { 247243789Sdim Init *RowFieldsJ = RowFields->getElement(j); 248243789Sdim Init *CurInstrVal = CurInstr->getValue(RowFieldsJ)->getValue(); 249243789Sdim KeyValue.push_back(CurInstrVal); 250243789Sdim } 251243789Sdim 252243789Sdim // Collect key instructions into KeyInstrVec. Later, these instructions are 253243789Sdim // processed to assign column position to the instructions sharing 254243789Sdim // their KeyValue in RowInstrMap. 255243789Sdim if (isKeyColInstr(CurInstr)) 256243789Sdim KeyInstrVec.push_back(CurInstr); 257243789Sdim 258243789Sdim RowInstrMap[KeyValue].push_back(CurInstr); 259243789Sdim } 260243789Sdim} 261243789Sdim 262243789Sdim//===----------------------------------------------------------------------===// 263243789Sdim// Return true if an instruction is a KeyCol instruction. 264243789Sdim//===----------------------------------------------------------------------===// 265243789Sdim 266243789Sdimbool MapTableEmitter::isKeyColInstr(Record* CurInstr) { 267243789Sdim ListInit *ColFields = InstrMapDesc.getColFields(); 268243789Sdim ListInit *KeyCol = InstrMapDesc.getKeyCol(); 269243789Sdim 270243789Sdim // Check if the instruction is a KeyCol instruction. 271243789Sdim bool MatchFound = true; 272243789Sdim for (unsigned j = 0, endCF = ColFields->getSize(); 273243789Sdim (j < endCF) && MatchFound; j++) { 274243789Sdim RecordVal *ColFieldName = CurInstr->getValue(ColFields->getElement(j)); 275243789Sdim std::string CurInstrVal = ColFieldName->getValue()->getAsUnquotedString(); 276243789Sdim std::string KeyColValue = KeyCol->getElement(j)->getAsUnquotedString(); 277243789Sdim MatchFound = (CurInstrVal == KeyColValue); 278243789Sdim } 279243789Sdim return MatchFound; 280243789Sdim} 281243789Sdim 282243789Sdim//===----------------------------------------------------------------------===// 283243789Sdim// Build a map to link key instructions with the column instructions arranged 284243789Sdim// according to their column positions. 285243789Sdim//===----------------------------------------------------------------------===// 286243789Sdim 287243789Sdimvoid MapTableEmitter::buildMapTable() { 288243789Sdim // Find column instructions for a given key based on the ColField 289243789Sdim // constraints. 290243789Sdim const std::vector<ListInit*> &ValueCols = InstrMapDesc.getValueCols(); 291243789Sdim unsigned NumOfCols = ValueCols.size(); 292243789Sdim for (unsigned j = 0, endKI = KeyInstrVec.size(); j < endKI; j++) { 293243789Sdim Record *CurKeyInstr = KeyInstrVec[j]; 294243789Sdim std::vector<Record*> ColInstrVec(NumOfCols); 295243789Sdim 296243789Sdim // Find the column instruction based on the constraints for the column. 297243789Sdim for (unsigned ColIdx = 0; ColIdx < NumOfCols; ColIdx++) { 298243789Sdim ListInit *CurValueCol = ValueCols[ColIdx]; 299243789Sdim Record *ColInstr = getInstrForColumn(CurKeyInstr, CurValueCol); 300243789Sdim ColInstrVec[ColIdx] = ColInstr; 301243789Sdim } 302243789Sdim MapTable[CurKeyInstr] = ColInstrVec; 303243789Sdim } 304243789Sdim} 305243789Sdim 306243789Sdim//===----------------------------------------------------------------------===// 307243789Sdim// Find column instruction based on the constraints for that column. 308243789Sdim//===----------------------------------------------------------------------===// 309243789Sdim 310243789SdimRecord *MapTableEmitter::getInstrForColumn(Record *KeyInstr, 311243789Sdim ListInit *CurValueCol) { 312243789Sdim ListInit *RowFields = InstrMapDesc.getRowFields(); 313243789Sdim std::vector<Init*> KeyValue; 314243789Sdim 315243789Sdim // Construct KeyValue using KeyInstr's values for RowFields. 316243789Sdim for (unsigned j = 0, endRF = RowFields->getSize(); j < endRF; j++) { 317243789Sdim Init *RowFieldsJ = RowFields->getElement(j); 318243789Sdim Init *KeyInstrVal = KeyInstr->getValue(RowFieldsJ)->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]; 334243789Sdim for (unsigned j = 0, endCF = ColFields->getSize(); 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) { 344243789Sdim if (MatchInstr) // Already had a match 345243789Sdim // Error if multiple matches are found for a column. 346243789Sdim PrintFatalError("Multiple matches found for `" + KeyInstr->getName() + 347243789Sdim "', for the relation `" + InstrMapDesc.getName()); 348243789Sdim MatchInstr = CurInstr; 349243789Sdim } 350243789Sdim } 351243789Sdim return MatchInstr; 352243789Sdim} 353243789Sdim 354243789Sdim//===----------------------------------------------------------------------===// 355243789Sdim// Emit one table per relation. Only instructions with a valid relation of a 356243789Sdim// given type are included in the table sorted by their enum values (opcodes). 357243789Sdim// Binary search is used for locating instructions in the table. 358243789Sdim//===----------------------------------------------------------------------===// 359243789Sdim 360243789Sdimunsigned MapTableEmitter::emitBinSearchTable(raw_ostream &OS) { 361243789Sdim 362243789Sdim const std::vector<const CodeGenInstruction*> &NumberedInstructions = 363243789Sdim Target.getInstructionsByEnumValue(); 364243789Sdim std::string TargetName = Target.getName(); 365243789Sdim const std::vector<ListInit*> &ValueCols = InstrMapDesc.getValueCols(); 366243789Sdim unsigned NumCol = ValueCols.size(); 367243789Sdim unsigned TotalNumInstr = NumberedInstructions.size(); 368243789Sdim unsigned TableSize = 0; 369243789Sdim 370243789Sdim OS << "static const uint16_t "<<InstrMapDesc.getName(); 371243789Sdim // Number of columns in the table are NumCol+1 because key instructions are 372243789Sdim // emitted as first column. 373243789Sdim OS << "Table[]["<< NumCol+1 << "] = {\n"; 374243789Sdim for (unsigned i = 0; i < TotalNumInstr; i++) { 375243789Sdim Record *CurInstr = NumberedInstructions[i]->TheDef; 376243789Sdim std::vector<Record*> ColInstrs = MapTable[CurInstr]; 377243789Sdim std::string OutStr(""); 378243789Sdim unsigned RelExists = 0; 379243789Sdim if (ColInstrs.size()) { 380243789Sdim for (unsigned j = 0; j < NumCol; j++) { 381276479Sdim if (ColInstrs[j] != nullptr) { 382243789Sdim RelExists = 1; 383243789Sdim OutStr += ", "; 384243789Sdim OutStr += TargetName; 385243789Sdim OutStr += "::"; 386243789Sdim OutStr += ColInstrs[j]->getName(); 387276479Sdim } else { OutStr += ", (uint16_t)-1U";} 388243789Sdim } 389243789Sdim 390243789Sdim if (RelExists) { 391243789Sdim OS << " { " << TargetName << "::" << CurInstr->getName(); 392243789Sdim OS << OutStr <<" },\n"; 393243789Sdim TableSize++; 394243789Sdim } 395243789Sdim } 396243789Sdim } 397243789Sdim if (!TableSize) { 398243789Sdim OS << " { " << TargetName << "::" << "INSTRUCTION_LIST_END, "; 399243789Sdim OS << TargetName << "::" << "INSTRUCTION_LIST_END }"; 400243789Sdim } 401243789Sdim OS << "}; // End of " << InstrMapDesc.getName() << "Table\n\n"; 402243789Sdim return TableSize; 403243789Sdim} 404243789Sdim 405243789Sdim//===----------------------------------------------------------------------===// 406243789Sdim// Emit binary search algorithm as part of the functions used to query 407243789Sdim// relation tables. 408243789Sdim//===----------------------------------------------------------------------===// 409243789Sdim 410243789Sdimvoid MapTableEmitter::emitBinSearch(raw_ostream &OS, unsigned TableSize) { 411243789Sdim OS << " unsigned mid;\n"; 412243789Sdim OS << " unsigned start = 0;\n"; 413243789Sdim OS << " unsigned end = " << TableSize << ";\n"; 414243789Sdim OS << " while (start < end) {\n"; 415243789Sdim OS << " mid = start + (end - start)/2;\n"; 416243789Sdim OS << " if (Opcode == " << InstrMapDesc.getName() << "Table[mid][0]) {\n"; 417243789Sdim OS << " break;\n"; 418243789Sdim OS << " }\n"; 419243789Sdim OS << " if (Opcode < " << InstrMapDesc.getName() << "Table[mid][0])\n"; 420243789Sdim OS << " end = mid;\n"; 421243789Sdim OS << " else\n"; 422243789Sdim OS << " start = mid + 1;\n"; 423243789Sdim OS << " }\n"; 424243789Sdim OS << " if (start == end)\n"; 425243789Sdim OS << " return -1; // Instruction doesn't exist in this table.\n\n"; 426243789Sdim} 427243789Sdim 428243789Sdim//===----------------------------------------------------------------------===// 429243789Sdim// Emit functions to query relation tables. 430243789Sdim//===----------------------------------------------------------------------===// 431243789Sdim 432243789Sdimvoid MapTableEmitter::emitMapFuncBody(raw_ostream &OS, 433243789Sdim unsigned TableSize) { 434243789Sdim 435243789Sdim ListInit *ColFields = InstrMapDesc.getColFields(); 436243789Sdim const std::vector<ListInit*> &ValueCols = InstrMapDesc.getValueCols(); 437243789Sdim 438243789Sdim // Emit binary search algorithm to locate instructions in the 439243789Sdim // relation table. If found, return opcode value from the appropriate column 440243789Sdim // of the table. 441243789Sdim emitBinSearch(OS, TableSize); 442243789Sdim 443243789Sdim if (ValueCols.size() > 1) { 444243789Sdim for (unsigned i = 0, e = ValueCols.size(); i < e; i++) { 445243789Sdim ListInit *ColumnI = ValueCols[i]; 446243789Sdim for (unsigned j = 0, ColSize = ColumnI->getSize(); j < ColSize; j++) { 447243789Sdim std::string ColName = ColFields->getElement(j)->getAsUnquotedString(); 448243789Sdim OS << " if (in" << ColName; 449243789Sdim OS << " == "; 450243789Sdim OS << ColName << "_" << ColumnI->getElement(j)->getAsUnquotedString(); 451243789Sdim if (j < ColumnI->getSize() - 1) OS << " && "; 452243789Sdim else OS << ")\n"; 453243789Sdim } 454243789Sdim OS << " return " << InstrMapDesc.getName(); 455243789Sdim OS << "Table[mid]["<<i+1<<"];\n"; 456243789Sdim } 457243789Sdim OS << " return -1;"; 458243789Sdim } 459243789Sdim else 460243789Sdim OS << " return " << InstrMapDesc.getName() << "Table[mid][1];\n"; 461243789Sdim 462243789Sdim OS <<"}\n\n"; 463243789Sdim} 464243789Sdim 465243789Sdim//===----------------------------------------------------------------------===// 466243789Sdim// Emit relation tables and the functions to query them. 467243789Sdim//===----------------------------------------------------------------------===// 468243789Sdim 469243789Sdimvoid MapTableEmitter::emitTablesWithFunc(raw_ostream &OS) { 470243789Sdim 471243789Sdim // Emit function name and the input parameters : mostly opcode value of the 472243789Sdim // current instruction. However, if a table has multiple columns (more than 2 473243789Sdim // since first column is used for the key instructions), then we also need 474243789Sdim // to pass another input to indicate the column to be selected. 475243789Sdim 476243789Sdim ListInit *ColFields = InstrMapDesc.getColFields(); 477243789Sdim const std::vector<ListInit*> &ValueCols = InstrMapDesc.getValueCols(); 478243789Sdim OS << "// "<< InstrMapDesc.getName() << "\n"; 479243789Sdim OS << "int "<< InstrMapDesc.getName() << "(uint16_t Opcode"; 480243789Sdim if (ValueCols.size() > 1) { 481243789Sdim for (unsigned i = 0, e = ColFields->getSize(); i < e; i++) { 482243789Sdim std::string ColName = ColFields->getElement(i)->getAsUnquotedString(); 483243789Sdim OS << ", enum " << ColName << " in" << ColName << ") {\n"; 484243789Sdim } 485243789Sdim } else { OS << ") {\n"; } 486243789Sdim 487243789Sdim // Emit map table. 488243789Sdim unsigned TableSize = emitBinSearchTable(OS); 489243789Sdim 490243789Sdim // Emit rest of the function body. 491243789Sdim emitMapFuncBody(OS, TableSize); 492243789Sdim} 493243789Sdim 494243789Sdim//===----------------------------------------------------------------------===// 495243789Sdim// Emit enums for the column fields across all the instruction maps. 496243789Sdim//===----------------------------------------------------------------------===// 497243789Sdim 498243789Sdimstatic void emitEnums(raw_ostream &OS, RecordKeeper &Records) { 499243789Sdim 500243789Sdim std::vector<Record*> InstrMapVec; 501243789Sdim InstrMapVec = Records.getAllDerivedDefinitions("InstrMapping"); 502243789Sdim std::map<std::string, std::vector<Init*> > ColFieldValueMap; 503243789Sdim 504243789Sdim // Iterate over all InstrMapping records and create a map between column 505243789Sdim // fields and their possible values across all records. 506243789Sdim for (unsigned i = 0, e = InstrMapVec.size(); i < e; i++) { 507243789Sdim Record *CurMap = InstrMapVec[i]; 508243789Sdim ListInit *ColFields; 509243789Sdim ColFields = CurMap->getValueAsListInit("ColFields"); 510243789Sdim ListInit *List = CurMap->getValueAsListInit("ValueCols"); 511243789Sdim std::vector<ListInit*> ValueCols; 512243789Sdim unsigned ListSize = List->getSize(); 513243789Sdim 514243789Sdim for (unsigned j = 0; j < ListSize; j++) { 515243789Sdim ListInit *ListJ = dyn_cast<ListInit>(List->getElement(j)); 516243789Sdim 517243789Sdim if (ListJ->getSize() != ColFields->getSize()) 518243789Sdim PrintFatalError("Record `" + CurMap->getName() + "', field " 519243789Sdim "`ValueCols' entries don't match with the entries in 'ColFields' !"); 520243789Sdim ValueCols.push_back(ListJ); 521243789Sdim } 522243789Sdim 523243789Sdim for (unsigned j = 0, endCF = ColFields->getSize(); j < endCF; j++) { 524243789Sdim for (unsigned k = 0; k < ListSize; k++){ 525243789Sdim std::string ColName = ColFields->getElement(j)->getAsUnquotedString(); 526243789Sdim ColFieldValueMap[ColName].push_back((ValueCols[k])->getElement(j)); 527243789Sdim } 528243789Sdim } 529243789Sdim } 530243789Sdim 531243789Sdim for (std::map<std::string, std::vector<Init*> >::iterator 532243789Sdim II = ColFieldValueMap.begin(), IE = ColFieldValueMap.end(); 533243789Sdim II != IE; II++) { 534243789Sdim std::vector<Init*> FieldValues = (*II).second; 535243789Sdim 536243789Sdim // Delete duplicate entries from ColFieldValueMap 537249423Sdim for (unsigned i = 0; i < FieldValues.size() - 1; i++) { 538243789Sdim Init *CurVal = FieldValues[i]; 539249423Sdim for (unsigned j = i+1; j < FieldValues.size(); j++) { 540243789Sdim if (CurVal == FieldValues[j]) { 541243789Sdim FieldValues.erase(FieldValues.begin()+j); 542243789Sdim } 543243789Sdim } 544243789Sdim } 545243789Sdim 546243789Sdim // Emit enumerated values for the column fields. 547243789Sdim OS << "enum " << (*II).first << " {\n"; 548249423Sdim for (unsigned i = 0, endFV = FieldValues.size(); i < endFV; i++) { 549243789Sdim OS << "\t" << (*II).first << "_" << FieldValues[i]->getAsUnquotedString(); 550249423Sdim if (i != endFV - 1) 551243789Sdim OS << ",\n"; 552243789Sdim else 553243789Sdim OS << "\n};\n\n"; 554243789Sdim } 555243789Sdim } 556243789Sdim} 557243789Sdim 558243789Sdimnamespace llvm { 559243789Sdim//===----------------------------------------------------------------------===// 560243789Sdim// Parse 'InstrMapping' records and use the information to form relationship 561243789Sdim// between instructions. These relations are emitted as a tables along with the 562243789Sdim// functions to query them. 563243789Sdim//===----------------------------------------------------------------------===// 564243789Sdimvoid EmitMapTable(RecordKeeper &Records, raw_ostream &OS) { 565243789Sdim CodeGenTarget Target(Records); 566243789Sdim std::string TargetName = Target.getName(); 567243789Sdim std::vector<Record*> InstrMapVec; 568243789Sdim InstrMapVec = Records.getAllDerivedDefinitions("InstrMapping"); 569243789Sdim 570243789Sdim if (!InstrMapVec.size()) 571243789Sdim return; 572243789Sdim 573243789Sdim OS << "#ifdef GET_INSTRMAP_INFO\n"; 574243789Sdim OS << "#undef GET_INSTRMAP_INFO\n"; 575243789Sdim OS << "namespace llvm {\n\n"; 576243789Sdim OS << "namespace " << TargetName << " {\n\n"; 577243789Sdim 578243789Sdim // Emit coulumn field names and their values as enums. 579243789Sdim emitEnums(OS, Records); 580243789Sdim 581243789Sdim // Iterate over all instruction mapping records and construct relationship 582243789Sdim // maps based on the information specified there. 583243789Sdim // 584243789Sdim for (unsigned i = 0, e = InstrMapVec.size(); i < e; i++) { 585243789Sdim MapTableEmitter IMap(Target, Records, InstrMapVec[i]); 586243789Sdim 587243789Sdim // Build RowInstrMap to group instructions based on their values for 588243789Sdim // RowFields. In the process, also collect key instructions into 589243789Sdim // KeyInstrVec. 590243789Sdim IMap.buildRowInstrMap(); 591243789Sdim 592243789Sdim // Build MapTable to map key instructions with the corresponding column 593243789Sdim // instructions. 594243789Sdim IMap.buildMapTable(); 595243789Sdim 596243789Sdim // Emit map tables and the functions to query them. 597243789Sdim IMap.emitTablesWithFunc(OS); 598243789Sdim } 599243789Sdim OS << "} // End " << TargetName << " namespace\n"; 600243789Sdim OS << "} // End llvm namespace\n"; 601243789Sdim OS << "#endif // GET_INSTRMAP_INFO\n\n"; 602243789Sdim} 603243789Sdim 604243789Sdim} // End llvm namespace 605