contrib/llvm-project/llvm/utils/TableGen/CodeGenMapTable.cpp

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