utils/TableGen/CodeGenMapTable.cpp

   1 //===- CodeGenMapTable.cpp - Instruction Mapping Table Generator ----------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 // CodeGenMapTable provides functionality for the TabelGen to create
  10 // relation mapping between instructions. Relation models are defined using
  11 // InstrMapping as a base class. This file implements the functionality which
  12 // parses these definitions and generates relation maps using the information
  13 // specified there. These maps are emitted as tables in the XXXGenInstrInfo.inc
  14 // file along with the functions to query them.
  15 //
  16 // A relationship model to relate non-predicate instructions with their
  17 // predicated true/false forms can be defined as follows:
  18 //
  19 // def getPredOpcode : InstrMapping {
  20 //  let FilterClass = "PredRel";
  21 //  let RowFields = ["BaseOpcode"];
  22 //  let ColFields = ["PredSense"];
  23 //  let KeyCol = ["none"];
  24 //  let ValueCols = [["true"], ["false"]]; }
  25 //
  26 // CodeGenMapTable parses this map and generates a table in XXXGenInstrInfo.inc
  27 // file that contains the instructions modeling this relationship. This table
  28 // is defined in the function
  29 // "int getPredOpcode(uint16_t Opcode, enum PredSense inPredSense)"
  30 // that can be used to retrieve the predicated form of the instruction by
  31 // passing its opcode value and the predicate sense (true/false) of the desired
  32 // instruction as arguments.
  33 //
  34 // Short description of the algorithm:
  35 //
  36 // 1) Iterate through all the records that derive from "InstrMapping" class.
  37 // 2) For each record, filter out instructions based on the FilterClass value.
  38 // 3) Iterate through this set of instructions and insert them into
  39 // RowInstrMap map based on their RowFields values. RowInstrMap is keyed by the
  40 // vector of RowFields values and contains vectors of Records (instructions) as
  41 // values. RowFields is a list of fields that are required to have the same
  42 // values for all the instructions appearing in the same row of the relation
  43 // table. All the instructions in a given row of the relation table have some
  44 // sort of relationship with the key instruction defined by the corresponding
  45 // relationship model.
  46 //
  47 // Ex: RowInstrMap(RowVal1, RowVal2, ...) -> [Instr1, Instr2, Instr3, ... ]
  48 // Here Instr1, Instr2, Instr3 have same values (RowVal1, RowVal2) for
  49 // RowFields. These groups of instructions are later matched against ValueCols
  50 // to determine the column they belong to, if any.
  51 //
  52 // While building the RowInstrMap map, collect all the key instructions in
  53 // KeyInstrVec. These are the instructions having the same values as KeyCol
  54 // for all the fields listed in ColFields.
  55 //
  56 // For Example:
  57 //
  58 // Relate non-predicate instructions with their predicated true/false forms.
  59 //
  60 // def getPredOpcode : InstrMapping {
  61 //  let FilterClass = "PredRel";
  62 //  let RowFields = ["BaseOpcode"];
  63 //  let ColFields = ["PredSense"];
  64 //  let KeyCol = ["none"];
  65 //  let ValueCols = [["true"], ["false"]]; }
  66 //
  67 // Here, only instructions that have "none" as PredSense will be selected as key
  68 // instructions.
  69 //
  70 // 4) For each key instruction, get the group of instructions that share the
  71 // same key-value as the key instruction from RowInstrMap. Iterate over the list
  72 // of columns in ValueCols (it is defined as a list<list<string> >. Therefore,
  73 // it can specify multi-column relationships). For each column, find the
  74 // instruction from the group that matches all the values for the column.
  75 // Multiple matches are not allowed.
  76 //
  77 //===----------------------------------------------------------------------===//
  78
  79 #include "CodeGenTarget.h"
  80 #include "llvm/Support/Format.h"
  81 #include "llvm/TableGen/Error.h"
  82 using namespace llvm;
  83 typedef std::map<std::string, std::vector<Record*> > InstrRelMapTy;
  84
  85 typedef std::map<std::vector<Init*>, std::vector<Record*> > RowInstrMapTy;
  86
  87 namespace {
  88
  89 //===----------------------------------------------------------------------===//
  90 // This class is used to represent InstrMapping class defined in Target.td file.
  91 class InstrMap {
  92 private:
  93   std::string Name;
  94   std::string FilterClass;
  95   ListInit *RowFields;
  96   ListInit *ColFields;
  97   ListInit *KeyCol;
  98   std::vector<ListInit*> ValueCols;
  99
 100 public:
 101   InstrMap(Record* MapRec) {
 102     Name = MapRec->getName();
 103
 104     // FilterClass - It's used to reduce the search space only to the
 105     // instructions that define the kind of relationship modeled by
 106     // this InstrMapping object/record.
 107     const RecordVal *Filter = MapRec->getValue("FilterClass");
 108     FilterClass = Filter->getValue()->getAsUnquotedString();
 109
 110     // List of fields/attributes that need to be same across all the
 111     // instructions in a row of the relation table.
 112     RowFields = MapRec->getValueAsListInit("RowFields");
 113
 114     // List of fields/attributes that are constant across all the instruction
 115     // in a column of the relation table. Ex: ColFields = 'predSense'
 116     ColFields = MapRec->getValueAsListInit("ColFields");
 117
 118     // Values for the fields/attributes listed in 'ColFields'.
 119     // Ex: KeyCol = 'noPred' -- key instruction is non predicated
 120     KeyCol = MapRec->getValueAsListInit("KeyCol");
 121
 122     // List of values for the fields/attributes listed in 'ColFields', one for
 123     // each column in the relation table.
 124     //
 125     // Ex: ValueCols = [['true'],['false']] -- it results two columns in the
 126     // table. First column requires all the instructions to have predSense
 127     // set to 'true' and second column requires it to be 'false'.
 128     ListInit *ColValList = MapRec->getValueAsListInit("ValueCols");
 129
 130     // Each instruction map must specify at least one column for it to be valid.
 131     if (ColValList->getSize() == 0)
 132       PrintFatalError(MapRec->getLoc(), "InstrMapping record `" +
 133         MapRec->getName() + "' has empty " + "`ValueCols' field!");
 134
 135     for (unsigned i = 0, e = ColValList->getSize(); i < e; i++) {
 136       ListInit *ColI = dyn_cast<ListInit>(ColValList->getElement(i));
 137
 138       // Make sure that all the sub-lists in 'ValueCols' have same number of
 139       // elements as the fields in 'ColFields'.
 140       if (ColI->getSize() != ColFields->getSize())
 141         PrintFatalError(MapRec->getLoc(), "Record `" + MapRec->getName() +
 142           "', field `ValueCols' entries don't match with " +
 143           " the entries in 'ColFields'!");
 144       ValueCols.push_back(ColI);
 145     }
 146   }
 147
 148   std::string getName() const {
 149     return Name;
 150   }
 151
 152   std::string getFilterClass() {
 153     return FilterClass;
 154   }
 155
 156   ListInit *getRowFields() const {
 157     return RowFields;
 158   }
 159
 160   ListInit *getColFields() const {
 161     return ColFields;
 162   }
 163
 164   ListInit *getKeyCol() const {
 165     return KeyCol;
 166   }
 167
 168   const std::vector<ListInit*> &getValueCols() const {
 169     return ValueCols;
 170   }
 171 };
 172 } // End anonymous namespace.
 173
 174
 175 //===----------------------------------------------------------------------===//
 176 // class MapTableEmitter : It builds the instruction relation maps using
 177 // the information provided in InstrMapping records. It outputs these
 178 // relationship maps as tables into XXXGenInstrInfo.inc file along with the
 179 // functions to query them.
 180
 181 namespace {
 182 class MapTableEmitter {
 183 private:
 184 //  std::string TargetName;
 185   const CodeGenTarget &Target;
 186   // InstrMapDesc - InstrMapping record to be processed.
 187   InstrMap InstrMapDesc;
 188
 189   // InstrDefs - list of instructions filtered using FilterClass defined
 190   // in InstrMapDesc.
 191   std::vector<Record*> InstrDefs;
 192
 193   // RowInstrMap - maps RowFields values to the instructions. It's keyed by the
 194   // values of the row fields and contains vector of records as values.
 195   RowInstrMapTy RowInstrMap;
 196
 197   // KeyInstrVec - list of key instructions.
 198   std::vector<Record*> KeyInstrVec;
 199   DenseMap<Record*, std::vector<Record*> > MapTable;
 200
 201 public:
 202   MapTableEmitter(CodeGenTarget &Target, RecordKeeper &Records, Record *IMRec):
 203                   Target(Target), InstrMapDesc(IMRec) {
 204     const std::string FilterClass = InstrMapDesc.getFilterClass();
 205     InstrDefs = Records.getAllDerivedDefinitions(FilterClass);
 206   }
 207
 208   void buildRowInstrMap();
 209
 210   // Returns true if an instruction is a key instruction, i.e., its ColFields
 211   // have same values as KeyCol.
 212   bool isKeyColInstr(Record* CurInstr);
 213
 214   // Find column instruction corresponding to a key instruction based on the
 215   // constraints for that column.
 216   Record *getInstrForColumn(Record *KeyInstr, ListInit *CurValueCol);
 217
 218   // Find column instructions for each key instruction based
 219   // on ValueCols and store them into MapTable.
 220   void buildMapTable();
 221
 222   void emitBinSearch(raw_ostream &OS, unsigned TableSize);
 223   void emitTablesWithFunc(raw_ostream &OS);
 224   unsigned emitBinSearchTable(raw_ostream &OS);
 225
 226   // Lookup functions to query binary search tables.
 227   void emitMapFuncBody(raw_ostream &OS, unsigned TableSize);
 228
 229 };
 230 } // End anonymous namespace.
 231
 232
 233 //===----------------------------------------------------------------------===//
 234 // Process all the instructions that model this relation (alreday present in
 235 // InstrDefs) and insert them into RowInstrMap which is keyed by the values of
 236 // the fields listed as RowFields. It stores vectors of records as values.
 237 // All the related instructions have the same values for the RowFields thus are
 238 // part of the same key-value pair.
 239 //===----------------------------------------------------------------------===//
 240
 241 void MapTableEmitter::buildRowInstrMap() {
 242   for (unsigned i = 0, e = InstrDefs.size(); i < e; i++) {
 243     std::vector<Record*> InstrList;
 244     Record *CurInstr = InstrDefs[i];
 245     std::vector<Init*> KeyValue;
 246     ListInit *RowFields = InstrMapDesc.getRowFields();
 247     for (unsigned j = 0, endRF = RowFields->getSize(); j < endRF; j++) {
 248       Init *RowFieldsJ = RowFields->getElement(j);
 249       Init *CurInstrVal = CurInstr->getValue(RowFieldsJ)->getValue();
 250       KeyValue.push_back(CurInstrVal);
 251     }
 252
 253     // Collect key instructions into KeyInstrVec. Later, these instructions are
 254     // processed to assign column position to the instructions sharing
 255     // their KeyValue in RowInstrMap.
 256     if (isKeyColInstr(CurInstr))
 257       KeyInstrVec.push_back(CurInstr);
 258
 259     RowInstrMap[KeyValue].push_back(CurInstr);
 260   }
 261 }
 262
 263 //===----------------------------------------------------------------------===//
 264 // Return true if an instruction is a KeyCol instruction.
 265 //===----------------------------------------------------------------------===//
 266
 267 bool MapTableEmitter::isKeyColInstr(Record* CurInstr) {
 268   ListInit *ColFields = InstrMapDesc.getColFields();
 269   ListInit *KeyCol = InstrMapDesc.getKeyCol();
 270
 271   // Check if the instruction is a KeyCol instruction.
 272   bool MatchFound = true;
 273   for (unsigned j = 0, endCF = ColFields->getSize();
 274       (j < endCF) && MatchFound; j++) {
 275     RecordVal *ColFieldName = CurInstr->getValue(ColFields->getElement(j));
 276     std::string CurInstrVal = ColFieldName->getValue()->getAsUnquotedString();
 277     std::string KeyColValue = KeyCol->getElement(j)->getAsUnquotedString();
 278     MatchFound = (CurInstrVal == KeyColValue);
 279   }
 280   return MatchFound;
 281 }
 282
 283 //===----------------------------------------------------------------------===//
 284 // Build a map to link key instructions with the column instructions arranged
 285 // according to their column positions.
 286 //===----------------------------------------------------------------------===//
 287
 288 void MapTableEmitter::buildMapTable() {
 289   // Find column instructions for a given key based on the ColField
 290   // constraints.
 291   const std::vector<ListInit*> &ValueCols = InstrMapDesc.getValueCols();
 292   unsigned NumOfCols = ValueCols.size();
 293   for (unsigned j = 0, endKI = KeyInstrVec.size(); j < endKI; j++) {
 294     Record *CurKeyInstr = KeyInstrVec[j];
 295     std::vector<Record*> ColInstrVec(NumOfCols);
 296
 297     // Find the column instruction based on the constraints for the column.
 298     for (unsigned ColIdx = 0; ColIdx < NumOfCols; ColIdx++) {
 299       ListInit *CurValueCol = ValueCols[ColIdx];
 300       Record *ColInstr = getInstrForColumn(CurKeyInstr, CurValueCol);
 301       ColInstrVec[ColIdx] = ColInstr;
 302     }
 303     MapTable[CurKeyInstr] = ColInstrVec;
 304   }
 305 }
 306
 307 //===----------------------------------------------------------------------===//
 308 // Find column instruction based on the constraints for that column.
 309 //===----------------------------------------------------------------------===//
 310
 311 Record *MapTableEmitter::getInstrForColumn(Record *KeyInstr,
 312                                            ListInit *CurValueCol) {
 313   ListInit *RowFields = InstrMapDesc.getRowFields();
 314   std::vector<Init*> KeyValue;
 315
 316   // Construct KeyValue using KeyInstr's values for RowFields.
 317   for (unsigned j = 0, endRF = RowFields->getSize(); j < endRF; j++) {
 318     Init *RowFieldsJ = RowFields->getElement(j);
 319     Init *KeyInstrVal = KeyInstr->getValue(RowFieldsJ)->getValue();
 320     KeyValue.push_back(KeyInstrVal);
 321   }
 322
 323   // Get all the instructions that share the same KeyValue as the KeyInstr
 324   // in RowInstrMap. We search through these instructions to find a match
 325   // for the current column, i.e., the instruction which has the same values
 326   // as CurValueCol for all the fields in ColFields.
 327   const std::vector<Record*> &RelatedInstrVec = RowInstrMap[KeyValue];
 328
 329   ListInit *ColFields = InstrMapDesc.getColFields();
 330   Record *MatchInstr = NULL;
 331
 332   for (unsigned i = 0, e = RelatedInstrVec.size(); i < e; i++) {
 333     bool MatchFound = true;
 334     Record *CurInstr = RelatedInstrVec[i];
 335     for (unsigned j = 0, endCF = ColFields->getSize();
 336         (j < endCF) && MatchFound; j++) {
 337       Init *ColFieldJ = ColFields->getElement(j);
 338       Init *CurInstrInit = CurInstr->getValue(ColFieldJ)->getValue();
 339       std::string CurInstrVal = CurInstrInit->getAsUnquotedString();
 340       Init *ColFieldJVallue = CurValueCol->getElement(j);
 341       MatchFound = (CurInstrVal == ColFieldJVallue->getAsUnquotedString());
 342     }
 343
 344     if (MatchFound) {
 345       if (MatchInstr) // Already had a match
 346         // Error if multiple matches are found for a column.
 347         PrintFatalError("Multiple matches found for `" + KeyInstr->getName() +
 348               "', for the relation `" + InstrMapDesc.getName());
 349       MatchInstr = CurInstr;
 350     }
 351   }
 352   return MatchInstr;
 353 }
 354
 355 //===----------------------------------------------------------------------===//
 356 // Emit one table per relation. Only instructions with a valid relation of a
 357 // given type are included in the table sorted by their enum values (opcodes).
 358 // Binary search is used for locating instructions in the table.
 359 //===----------------------------------------------------------------------===//
 360
 361 unsigned MapTableEmitter::emitBinSearchTable(raw_ostream &OS) {
 362
 363   const std::vector<const CodeGenInstruction*> &NumberedInstructions =
 364                                             Target.getInstructionsByEnumValue();
 365   std::string TargetName = Target.getName();
 366   const std::vector<ListInit*> &ValueCols = InstrMapDesc.getValueCols();
 367   unsigned NumCol = ValueCols.size();
 368   unsigned TotalNumInstr = NumberedInstructions.size();
 369   unsigned TableSize = 0;
 370
 371   OS << "static const uint16_t "<<InstrMapDesc.getName();
 372   // Number of columns in the table are NumCol+1 because key instructions are
 373   // emitted as first column.
 374   OS << "Table[]["<< NumCol+1 << "] = {\n";
 375   for (unsigned i = 0; i < TotalNumInstr; i++) {
 376     Record *CurInstr = NumberedInstructions[i]->TheDef;
 377     std::vector<Record*> ColInstrs = MapTable[CurInstr];
 378     std::string OutStr("");
 379     unsigned RelExists = 0;
 380     if (ColInstrs.size()) {
 381       for (unsigned j = 0; j < NumCol; j++) {
 382         if (ColInstrs[j] != NULL) {
 383           RelExists = 1;
 384           OutStr += ", ";
 385           OutStr += TargetName;
 386           OutStr += "::";
 387           OutStr += ColInstrs[j]->getName();
 388         } else { OutStr += ", -1";}
 389       }
 390
 391       if (RelExists) {
 392         OS << "  { " << TargetName << "::" << CurInstr->getName();
 393         OS << OutStr <<" },\n";
 394         TableSize++;
 395       }
 396     }
 397   }
 398   if (!TableSize) {
 399     OS << "  { " << TargetName << "::" << "INSTRUCTION_LIST_END, ";
 400     OS << TargetName << "::" << "INSTRUCTION_LIST_END }";
 401   }
 402   OS << "}; // End of " << InstrMapDesc.getName() << "Table\n\n";
 403   return TableSize;
 404 }
 405
 406 //===----------------------------------------------------------------------===//
 407 // Emit binary search algorithm as part of the functions used to query
 408 // relation tables.
 409 //===----------------------------------------------------------------------===//
 410
 411 void MapTableEmitter::emitBinSearch(raw_ostream &OS, unsigned TableSize) {
 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 == " << InstrMapDesc.getName() << "Table[mid][0]) {\n";
 418   OS << "      break;\n";
 419   OS << "    }\n";
 420   OS << "    if (Opcode < " << InstrMapDesc.getName() << "Table[mid][0])\n";
 421   OS << "      end = mid;\n";
 422   OS << "    else\n";
 423   OS << "      start = mid + 1;\n";
 424   OS << "  }\n";
 425   OS << "  if (start == end)\n";
 426   OS << "    return -1; // Instruction doesn't exist in this table.\n\n";
 427 }
 428
 429 //===----------------------------------------------------------------------===//
 430 // Emit functions to query relation tables.
 431 //===----------------------------------------------------------------------===//
 432
 433 void MapTableEmitter::emitMapFuncBody(raw_ostream &OS,
 434                                            unsigned TableSize) {
 435
 436   ListInit *ColFields = InstrMapDesc.getColFields();
 437   const std::vector<ListInit*> &ValueCols = InstrMapDesc.getValueCols();
 438
 439   // Emit binary search algorithm to locate instructions in the
 440   // relation table. If found, return opcode value from the appropriate column
 441   // of the table.
 442   emitBinSearch(OS, TableSize);
 443
 444   if (ValueCols.size() > 1) {
 445     for (unsigned i = 0, e = ValueCols.size(); i < e; i++) {
 446       ListInit *ColumnI = ValueCols[i];
 447       for (unsigned j = 0, ColSize = ColumnI->getSize(); j < ColSize; j++) {
 448         std::string ColName = ColFields->getElement(j)->getAsUnquotedString();
 449         OS << "  if (in" << ColName;
 450         OS << " == ";
 451         OS << ColName << "_" << ColumnI->getElement(j)->getAsUnquotedString();
 452         if (j < ColumnI->getSize() - 1) OS << " && ";
 453         else OS << ")\n";
 454       }
 455       OS << "    return " << InstrMapDesc.getName();
 456       OS << "Table[mid]["<<i+1<<"];\n";
 457     }
 458     OS << "  return -1;";
 459   }
 460   else
 461     OS << "  return " << InstrMapDesc.getName() << "Table[mid][1];\n";
 462
 463   OS <<"}\n\n";
 464 }
 465
 466 //===----------------------------------------------------------------------===//
 467 // Emit relation tables and the functions to query them.
 468 //===----------------------------------------------------------------------===//
 469
 470 void MapTableEmitter::emitTablesWithFunc(raw_ostream &OS) {
 471
 472   // Emit function name and the input parameters : mostly opcode value of the
 473   // current instruction. However, if a table has multiple columns (more than 2
 474   // since first column is used for the key instructions), then we also need
 475   // to pass another input to indicate the column to be selected.
 476
 477   ListInit *ColFields = InstrMapDesc.getColFields();
 478   const std::vector<ListInit*> &ValueCols = InstrMapDesc.getValueCols();
 479   OS << "// "<< InstrMapDesc.getName() << "\n";
 480   OS << "int "<< InstrMapDesc.getName() << "(uint16_t Opcode";
 481   if (ValueCols.size() > 1) {
 482     for (unsigned i = 0, e = ColFields->getSize(); i < e; i++) {
 483       std::string ColName = ColFields->getElement(i)->getAsUnquotedString();
 484       OS << ", enum " << ColName << " in" << ColName << ") {\n";
 485     }
 486   } else { OS << ") {\n"; }
 487
 488   // Emit map table.
 489   unsigned TableSize = emitBinSearchTable(OS);
 490
 491   // Emit rest of the function body.
 492   emitMapFuncBody(OS, TableSize);
 493 }
 494
 495 //===----------------------------------------------------------------------===//
 496 // Emit enums for the column fields across all the instruction maps.
 497 //===----------------------------------------------------------------------===//
 498
 499 static void emitEnums(raw_ostream &OS, RecordKeeper &Records) {
 500
 501   std::vector<Record*> InstrMapVec;
 502   InstrMapVec = Records.getAllDerivedDefinitions("InstrMapping");
 503   std::map<std::string, std::vector<Init*> > ColFieldValueMap;
 504
 505   // Iterate over all InstrMapping records and create a map between column
 506   // fields and their possible values across all records.
 507   for (unsigned i = 0, e = InstrMapVec.size(); i < e; i++) {
 508     Record *CurMap = InstrMapVec[i];
 509     ListInit *ColFields;
 510     ColFields = CurMap->getValueAsListInit("ColFields");
 511     ListInit *List = CurMap->getValueAsListInit("ValueCols");
 512     std::vector<ListInit*> ValueCols;
 513     unsigned ListSize = List->getSize();
 514
 515     for (unsigned j = 0; j < ListSize; j++) {
 516       ListInit *ListJ = dyn_cast<ListInit>(List->getElement(j));
 517
 518       if (ListJ->getSize() != ColFields->getSize())
 519         PrintFatalError("Record `" + CurMap->getName() + "', field "
 520           "`ValueCols' entries don't match with the entries in 'ColFields' !");
 521       ValueCols.push_back(ListJ);
 522     }
 523
 524     for (unsigned j = 0, endCF = ColFields->getSize(); j < endCF; j++) {
 525       for (unsigned k = 0; k < ListSize; k++){
 526         std::string ColName = ColFields->getElement(j)->getAsUnquotedString();
 527         ColFieldValueMap[ColName].push_back((ValueCols[k])->getElement(j));
 528       }
 529     }
 530   }
 531
 532   for (std::map<std::string, std::vector<Init*> >::iterator
 533        II = ColFieldValueMap.begin(), IE = ColFieldValueMap.end();
 534        II != IE; II++) {
 535     std::vector<Init*> FieldValues = (*II).second;
 536
 537     // Delete duplicate entries from ColFieldValueMap
 538     for (unsigned i = 0; i < FieldValues.size() - 1; i++) {
 539       Init *CurVal = FieldValues[i];
 540       for (unsigned j = i+1; j < FieldValues.size(); j++) {
 541         if (CurVal == FieldValues[j]) {
 542           FieldValues.erase(FieldValues.begin()+j);
 543         }
 544       }
 545     }
 546
 547     // Emit enumerated values for the column fields.
 548     OS << "enum " << (*II).first << " {\n";
 549     for (unsigned i = 0, endFV = FieldValues.size(); i < endFV; i++) {
 550       OS << "\t" << (*II).first << "_" << FieldValues[i]->getAsUnquotedString();
 551       if (i != endFV - 1)
 552         OS << ",\n";
 553       else
 554         OS << "\n};\n\n";
 555     }
 556   }
 557 }
 558
 559 namespace llvm {
 560 //===----------------------------------------------------------------------===//
 561 // Parse 'InstrMapping' records and use the information to form relationship
 562 // between instructions. These relations are emitted as a tables along with the
 563 // functions to query them.
 564 //===----------------------------------------------------------------------===//
 565 void EmitMapTable(RecordKeeper &Records, raw_ostream &OS) {
 566   CodeGenTarget Target(Records);
 567   std::string TargetName = Target.getName();
 568   std::vector<Record*> InstrMapVec;
 569   InstrMapVec = Records.getAllDerivedDefinitions("InstrMapping");
 570
 571   if (!InstrMapVec.size())
 572     return;
 573
 574   OS << "#ifdef GET_INSTRMAP_INFO\n";
 575   OS << "#undef GET_INSTRMAP_INFO\n";
 576   OS << "namespace llvm {\n\n";
 577   OS << "namespace " << TargetName << " {\n\n";
 578
 579   // Emit coulumn field names and their values as enums.
 580   emitEnums(OS, Records);
 581
 582   // Iterate over all instruction mapping records and construct relationship
 583   // maps based on the information specified there.
 584   //
 585   for (unsigned i = 0, e = InstrMapVec.size(); i < e; i++) {
 586     MapTableEmitter IMap(Target, Records, InstrMapVec[i]);
 587
 588     // Build RowInstrMap to group instructions based on their values for
 589     // RowFields. In the process, also collect key instructions into
 590     // KeyInstrVec.
 591     IMap.buildRowInstrMap();
 592
 593     // Build MapTable to map key instructions with the corresponding column
 594     // instructions.
 595     IMap.buildMapTable();
 596
 597     // Emit map tables and the functions to query them.
 598     IMap.emitTablesWithFunc(OS);
 599   }
 600   OS << "} // End " << TargetName << " namespace\n";
 601   OS << "} // End llvm namespace\n";
 602   OS << "#endif // GET_INSTRMAP_INFO\n\n";
 603 }
 604
 605 } // End llvm namespace