support/tools/TableGen/InstrSelectorEmitter.cpp

   1 //===- InstrInfoEmitter.cpp - Generate a Instruction Set Desc. ------------===//
   2 //
   3 // This tablegen backend is responsible for emitting a description of the target
   4 // instruction set for the code generator.
   5 //
   6 //===----------------------------------------------------------------------===//
   7
   8 #include "InstrSelectorEmitter.h"
   9 #include "CodeGenWrappers.h"
  10 #include "Record.h"
  11 #include "Support/Debug.h"
  12
  13 NodeType::ArgResultTypes NodeType::Translate(Record *R) {
  14   const std::string &Name = R->getName();
  15   if (Name == "DNVT_void") return Void;
  16   if (Name == "DNVT_val" ) return Val;
  17   if (Name == "DNVT_arg0") return Arg0;
  18   if (Name == "DNVT_ptr" ) return Ptr;
  19   throw "Unknown DagNodeValType '" + Name + "'!";
  20 }
  21
  22
  23 //===----------------------------------------------------------------------===//
  24 // TreePatternNode implementation
  25 //
  26
  27 // updateNodeType - Set the node type of N to VT if VT contains information.  If
  28 // N already contains a conflicting type, then throw an exception
  29 //
  30 bool TreePatternNode::updateNodeType(MVT::ValueType VT,
  31                                      const std::string &RecName) {
  32   if (VT == MVT::Other || getType() == VT) return false;
  33   if (getType() == MVT::Other) {
  34     setType(VT);
  35     return true;
  36   }
  37
  38   throw "Type inferfence contradiction found for pattern " + RecName;
  39 }
  40
  41 /// InstantiateNonterminals - If this pattern refers to any nonterminals which
  42 /// are not themselves completely resolved, clone the nonterminal and resolve it
  43 /// with the using context we provide.
  44 ///
  45 void TreePatternNode::InstantiateNonterminals(InstrSelectorEmitter &ISE) {
  46   if (!isLeaf()) {
  47     for (unsigned i = 0, e = Children.size(); i != e; ++i)
  48       Children[i]->InstantiateNonterminals(ISE);
  49     return;
  50   }
  51
  52   // If this is a leaf, it might be a reference to a nonterminal!  Check now.
  53   if (DefInit *DI = dynamic_cast<DefInit*>(getValue()))
  54     if (DI->getDef()->isSubClassOf("Nonterminal")) {
  55       Pattern *NT = ISE.getPattern(DI->getDef());
  56       if (!NT->isResolved()) {
  57         // We found an unresolved nonterminal reference.  Ask the ISE to clone
  58         // it for us, then update our reference to the fresh, new, resolved,
  59         // nonterminal.
  60
  61         Value = new DefInit(ISE.InstantiateNonterminal(NT, getType()));
  62       }
  63     }
  64 }
  65
  66
  67 /// clone - Make a copy of this tree and all of its children.
  68 ///
  69 TreePatternNode *TreePatternNode::clone() const {
  70   TreePatternNode *New;
  71   if (isLeaf()) {
  72     New = new TreePatternNode(Value);
  73   } else {
  74     std::vector<TreePatternNode*> CChildren(Children.size());
  75     for (unsigned i = 0, e = Children.size(); i != e; ++i)
  76       CChildren[i] = Children[i]->clone();
  77     New = new TreePatternNode(Operator, CChildren);
  78   }
  79   New->setType(Type);
  80   return New;
  81 }
  82
  83
  84 std::ostream &operator<<(std::ostream &OS, const TreePatternNode &N) {
  85   if (N.isLeaf())
  86     return OS << N.getType() << ":" << *N.getValue();
  87   OS << "(" << N.getType() << ":";
  88   OS << N.getOperator()->getName();
  89
  90   const std::vector<TreePatternNode*> &Children = N.getChildren();
  91   if (!Children.empty()) {
  92     OS << " " << *Children[0];
  93     for (unsigned i = 1, e = Children.size(); i != e; ++i)
  94       OS << ", " << *Children[i];
  95   }
  96   return OS << ")";
  97 }
  98
  99 void TreePatternNode::dump() const { std::cerr << *this; }
 100
 101 //===----------------------------------------------------------------------===//
 102 // Pattern implementation
 103 //
 104
 105 // Parse the specified DagInit into a TreePattern which we can use.
 106 //
 107 Pattern::Pattern(PatternType pty, DagInit *RawPat, Record *TheRec,
 108                  InstrSelectorEmitter &ise)
 109   : PTy(pty), TheRecord(TheRec), ISE(ise) {
 110
 111   // First, parse the pattern...
 112   Tree = ParseTreePattern(RawPat);
 113
 114   // Run the type-inference engine...
 115   InferAllTypes();
 116
 117   if (PTy == Instruction || PTy == Expander) {
 118     // Check to make sure there is not any unset types in the tree pattern...
 119     if (!isResolved()) {
 120       std::cerr << "In pattern: " << *Tree << "\n";
 121       error("Could not infer all types!");
 122     }
 123
 124     // Check to see if we have a top-level (set) of a register.
 125     if (Tree->getOperator()->getName() == "set") {
 126       assert(Tree->getChildren().size() == 2 && "Set with != 2 arguments?");
 127       if (!Tree->getChild(0)->isLeaf())
 128         error("Arg #0 of set should be a register or register class!");
 129       DefInit *RegInit = dynamic_cast<DefInit*>(Tree->getChild(0)->getValue());
 130       if (RegInit == 0)
 131         error("LHS of 'set' expected to be a register or register class!");
 132
 133       Result = RegInit->getDef();
 134       Tree = Tree->getChild(1);
 135     }
 136   }
 137 }
 138
 139
 140
 141 void Pattern::error(const std::string &Msg) const {
 142   std::string M = "In ";
 143   switch (PTy) {
 144   case Nonterminal: M += "nonterminal "; break;
 145   case Instruction: M += "instruction "; break;
 146   case Expander   : M += "expander "; break;
 147   }
 148   throw M + TheRecord->getName() + ": " + Msg;
 149 }
 150
 151 /// getIntrinsicType - Check to see if the specified record has an intrinsic
 152 /// type which should be applied to it.  This infer the type of register
 153 /// references from the register file information, for example.
 154 ///
 155 MVT::ValueType Pattern::getIntrinsicType(Record *R) const {
 156   // Check to see if this is a register or a register class...
 157   if (R->isSubClassOf("RegisterClass"))
 158     return getValueType(R->getValueAsDef("RegType"));
 159   else if (R->isSubClassOf("Nonterminal"))
 160     return ISE.ReadNonterminal(R)->getTree()->getType();
 161   else if (R->isSubClassOf("Register")) {
 162     std::cerr << "WARNING: Explicit registers not handled yet!\n";
 163     return MVT::Other;
 164   }
 165
 166   throw "Error: Unknown value used: " + R->getName();
 167 }
 168
 169 TreePatternNode *Pattern::ParseTreePattern(DagInit *DI) {
 170   Record *Operator = DI->getNodeType();
 171   const std::vector<Init*> &Args = DI->getArgs();
 172
 173   if (Operator->isSubClassOf("ValueType")) {
 174     // If the operator is a ValueType, then this must be "type cast" of a leaf
 175     // node.
 176     if (Args.size() != 1)
 177       error("Type cast only valid for a leaf node!");
 178
 179     Init *Arg = Args[0];
 180     TreePatternNode *New;
 181     if (DefInit *DI = dynamic_cast<DefInit*>(Arg)) {
 182       New = new TreePatternNode(DI);
 183       // If it's a regclass or something else known, set the type.
 184       New->setType(getIntrinsicType(DI->getDef()));
 185     } else {
 186       Arg->dump();
 187       error("Unknown leaf value for tree pattern!");
 188     }
 189
 190     // Apply the type cast...
 191     New->updateNodeType(getValueType(Operator), TheRecord->getName());
 192     return New;
 193   }
 194
 195   if (!ISE.getNodeTypes().count(Operator))
 196     error("Unrecognized node '" + Operator->getName() + "'!");
 197
 198   std::vector<TreePatternNode*> Children;
 199
 200   for (unsigned i = 0, e = Args.size(); i != e; ++i) {
 201     Init *Arg = Args[i];
 202     if (DagInit *DI = dynamic_cast<DagInit*>(Arg)) {
 203       Children.push_back(ParseTreePattern(DI));
 204     } else if (DefInit *DI = dynamic_cast<DefInit*>(Arg)) {
 205       Children.push_back(new TreePatternNode(DI));
 206       // If it's a regclass or something else known, set the type.
 207       Children.back()->setType(getIntrinsicType(DI->getDef()));
 208     } else {
 209       Arg->dump();
 210       error("Unknown leaf value for tree pattern!");
 211     }
 212   }
 213
 214   return new TreePatternNode(Operator, Children);
 215 }
 216
 217 void Pattern::InferAllTypes() {
 218   bool MadeChange, AnyUnset;
 219   do {
 220     MadeChange = false;
 221     AnyUnset = InferTypes(Tree, MadeChange);
 222   } while ((AnyUnset || MadeChange) && !(AnyUnset && !MadeChange));
 223   Resolved = !AnyUnset;
 224 }
 225
 226
 227 // InferTypes - Perform type inference on the tree, returning true if there
 228 // are any remaining untyped nodes and setting MadeChange if any changes were
 229 // made.
 230 bool Pattern::InferTypes(TreePatternNode *N, bool &MadeChange) {
 231   if (N->isLeaf()) return N->getType() == MVT::Other;
 232
 233   bool AnyUnset = false;
 234   Record *Operator = N->getOperator();
 235   assert(ISE.getNodeTypes().count(Operator) && "No node info for node!");
 236   const NodeType &NT = ISE.getNodeTypes()[Operator];
 237
 238   // Check to see if we can infer anything about the argument types from the
 239   // return types...
 240   const std::vector<TreePatternNode*> &Children = N->getChildren();
 241   if (Children.size() != NT.ArgTypes.size())
 242     error("Incorrect number of children for " + Operator->getName() + " node!");
 243
 244   for (unsigned i = 0, e = Children.size(); i != e; ++i) {
 245     TreePatternNode *Child = Children[i];
 246     AnyUnset |= InferTypes(Child, MadeChange);
 247
 248     switch (NT.ArgTypes[i]) {
 249     case NodeType::Arg0:
 250       MadeChange |= Child->updateNodeType(Children[0]->getType(),
 251                                           TheRecord->getName());
 252       break;
 253     case NodeType::Val:
 254       if (Child->getType() == MVT::isVoid)
 255         error("Inferred a void node in an illegal place!");
 256       break;
 257     case NodeType::Ptr:
 258       MadeChange |= Child->updateNodeType(ISE.getTarget().getPointerType(),
 259                                           TheRecord->getName());
 260       break;
 261     default: assert(0 && "Invalid argument ArgType!");
 262     }
 263   }
 264
 265   // See if we can infer anything about the return type now...
 266   switch (NT.ResultType) {
 267   case NodeType::Void:
 268     MadeChange |= N->updateNodeType(MVT::isVoid, TheRecord->getName());
 269     break;
 270   case NodeType::Arg0:
 271     MadeChange |= N->updateNodeType(Children[0]->getType(),
 272                                     TheRecord->getName());
 273     break;
 274
 275   case NodeType::Ptr:
 276     MadeChange |= N->updateNodeType(ISE.getTarget().getPointerType(),
 277                                     TheRecord->getName());
 278     break;
 279   case NodeType::Val:
 280     if (N->getType() == MVT::isVoid)
 281       error("Inferred a void node in an illegal place!");
 282     break;
 283   default:
 284     assert(0 && "Unhandled type constraint!");
 285     break;
 286   }
 287
 288   return AnyUnset | N->getType() == MVT::Other;
 289 }
 290
 291 /// clone - This method is used to make an exact copy of the current pattern,
 292 /// then change the "TheRecord" instance variable to the specified record.
 293 ///
 294 Pattern *Pattern::clone(Record *R) const {
 295   assert(PTy == Nonterminal && "Can only clone nonterminals");
 296   return new Pattern(Tree->clone(), R, Resolved, ISE);
 297 }
 298
 299
 300
 301 std::ostream &operator<<(std::ostream &OS, const Pattern &P) {
 302   switch (P.getPatternType()) {
 303   case Pattern::Nonterminal: OS << "Nonterminal pattern "; break;
 304   case Pattern::Instruction: OS << "Instruction pattern "; break;
 305   case Pattern::Expander:    OS << "Expander pattern    "; break;
 306   }
 307
 308   OS << P.getRecord()->getName() << ":\t";
 309
 310   if (Record *Result = P.getResult())
 311     OS << Result->getName() << " = ";
 312   OS << *P.getTree();
 313
 314   if (!P.isResolved())
 315     OS << " [not completely resolved]";
 316   return OS;
 317 }
 318
 319
 320 //===----------------------------------------------------------------------===//
 321 // PatternOrganizer implementation
 322 //
 323
 324 /// addPattern - Add the specified pattern to the appropriate location in the
 325 /// collection.
 326 void PatternOrganizer::addPattern(Pattern *P) {
 327   std::string ValueName;
 328   if (P->getPatternType() == Pattern::Nonterminal) {
 329     // Just use the nonterminal name, which will already include the type if
 330     // it has been cloned.
 331     ValueName = P->getRecord()->getName();
 332   } else {
 333     if (P->getResult())
 334       ValueName += P->getResult()->getName()+"_";
 335     else
 336       ValueName += "Void_";
 337     ValueName += getName(P->getTree()->getType());
 338   }
 339
 340   NodesForSlot &Nodes = AllPatterns[ValueName];
 341   if (!P->getTree()->isLeaf())
 342     Nodes[P->getTree()->getOperator()].push_back(P);
 343   else {
 344     // Right now we only support DefInit's with node types...
 345     DefInit *Val = dynamic_cast<DefInit*>(P->getTree()->getValue());
 346     if (!Val)
 347       throw std::string("We only support def inits in PatternOrganizer"
 348                         "::addPattern so far!");
 349     Nodes[Val->getDef()].push_back(P);
 350   }
 351 }
 352
 353
 354
 355 //===----------------------------------------------------------------------===//
 356 // InstrSelectorEmitter implementation
 357 //
 358
 359 /// ReadNodeTypes - Read in all of the node types in the current RecordKeeper,
 360 /// turning them into the more accessible NodeTypes data structure.
 361 ///
 362 void InstrSelectorEmitter::ReadNodeTypes() {
 363   std::vector<Record*> Nodes = Records.getAllDerivedDefinitions("DagNode");
 364   DEBUG(std::cerr << "Getting node types: ");
 365   for (unsigned i = 0, e = Nodes.size(); i != e; ++i) {
 366     Record *Node = Nodes[i];
 367
 368     // Translate the return type...
 369     NodeType::ArgResultTypes RetTy =
 370       NodeType::Translate(Node->getValueAsDef("RetType"));
 371
 372     // Translate the arguments...
 373     ListInit *Args = Node->getValueAsListInit("ArgTypes");
 374     std::vector<NodeType::ArgResultTypes> ArgTypes;
 375
 376     for (unsigned a = 0, e = Args->getSize(); a != e; ++a) {
 377       if (DefInit *DI = dynamic_cast<DefInit*>(Args->getElement(a)))
 378         ArgTypes.push_back(NodeType::Translate(DI->getDef()));
 379       else
 380         throw "In node " + Node->getName() + ", argument is not a Def!";
 381
 382       if (a == 0 && ArgTypes.back() == NodeType::Arg0)
 383         throw "In node " + Node->getName() + ", arg 0 cannot have type 'arg0'!";
 384       if (ArgTypes.back() == NodeType::Void)
 385         throw "In node " + Node->getName() + ", args cannot be void type!";
 386     }
 387     if (RetTy == NodeType::Arg0 && Args->getSize() == 0)
 388       throw "In node " + Node->getName() +
 389             ", invalid return type for nullary node!";
 390
 391     // Add the node type mapping now...
 392     NodeTypes[Node] = NodeType(RetTy, ArgTypes);
 393     DEBUG(std::cerr << Node->getName() << ", ");
 394   }
 395   DEBUG(std::cerr << "DONE!\n");
 396 }
 397
 398 Pattern *InstrSelectorEmitter::ReadNonterminal(Record *R) {
 399   Pattern *&P = Patterns[R];
 400   if (P) return P;  // Don't reread it!
 401
 402   DagInit *DI = R->getValueAsDag("Pattern");
 403   P = new Pattern(Pattern::Nonterminal, DI, R, *this);
 404   DEBUG(std::cerr << "Parsed " << *P << "\n");
 405   return P;
 406 }
 407
 408
 409 // ReadNonTerminals - Read in all nonterminals and incorporate them into our
 410 // pattern database.
 411 void InstrSelectorEmitter::ReadNonterminals() {
 412   std::vector<Record*> NTs = Records.getAllDerivedDefinitions("Nonterminal");
 413   for (unsigned i = 0, e = NTs.size(); i != e; ++i)
 414     ReadNonterminal(NTs[i]);
 415 }
 416
 417
 418 /// ReadInstructionPatterns - Read in all subclasses of Instruction, and process
 419 /// those with a useful Pattern field.
 420 ///
 421 void InstrSelectorEmitter::ReadInstructionPatterns() {
 422   std::vector<Record*> Insts = Records.getAllDerivedDefinitions("Instruction");
 423   for (unsigned i = 0, e = Insts.size(); i != e; ++i) {
 424     Record *Inst = Insts[i];
 425     if (DagInit *DI = dynamic_cast<DagInit*>(Inst->getValueInit("Pattern"))) {
 426       Patterns[Inst] = new Pattern(Pattern::Instruction, DI, Inst, *this);
 427       DEBUG(std::cerr << "Parsed " << *Patterns[Inst] << "\n");
 428     }
 429   }
 430 }
 431
 432 /// ReadExpanderPatterns - Read in all expander patterns...
 433 ///
 434 void InstrSelectorEmitter::ReadExpanderPatterns() {
 435   std::vector<Record*> Expanders = Records.getAllDerivedDefinitions("Expander");
 436   for (unsigned i = 0, e = Expanders.size(); i != e; ++i) {
 437     Record *Expander = Expanders[i];
 438     DagInit *DI = Expander->getValueAsDag("Pattern");
 439     Patterns[Expander] = new Pattern(Pattern::Expander, DI, Expander, *this);
 440     DEBUG(std::cerr << "Parsed " << *Patterns[Expander] << "\n");
 441   }
 442 }
 443
 444
 445 // InstantiateNonterminals - Instantiate any unresolved nonterminals with
 446 // information from the context that they are used in.
 447 //
 448 void InstrSelectorEmitter::InstantiateNonterminals() {
 449   DEBUG(std::cerr << "Instantiating nonterminals:\n");
 450   for (std::map<Record*, Pattern*>::iterator I = Patterns.begin(),
 451          E = Patterns.end(); I != E; ++I)
 452     if (I->second->isResolved())
 453       I->second->InstantiateNonterminals();
 454 }
 455
 456 /// InstantiateNonterminal - This method takes the nonterminal specified by
 457 /// NT, which should not be completely resolved, clones it, applies ResultTy
 458 /// to its root, then runs the type inference stuff on it.  This should
 459 /// produce a newly resolved nonterminal, which we make a record for and
 460 /// return.  To be extra fancy and efficient, this only makes one clone for
 461 /// each type it is instantiated with.
 462 Record *InstrSelectorEmitter::InstantiateNonterminal(Pattern *NT,
 463                                                      MVT::ValueType ResultTy) {
 464   assert(!NT->isResolved() && "Nonterminal is already resolved!");
 465
 466   // Check to see if we have already instantiated this pair...
 467   Record* &Slot = InstantiatedNTs[std::make_pair(NT, ResultTy)];
 468   if (Slot) return Slot;
 469
 470   Record *New = new Record(NT->getRecord()->getName()+"_"+getName(ResultTy));
 471
 472   DEBUG(std::cerr << "  Nonterminal '" << NT->getRecord()->getName()
 473                   << "' for type '" << getName(ResultTy) << "', producing '"
 474                   << New->getName() << "'\n");
 475
 476   // Copy the pattern...
 477   Pattern *NewPat = NT->clone(New);
 478
 479   // Apply the type to the root...
 480   NewPat->getTree()->updateNodeType(ResultTy, New->getName());
 481
 482   // Infer types...
 483   NewPat->InferAllTypes();
 484
 485   // Make sure everything is good to go now...
 486   if (!NewPat->isResolved())
 487     NewPat->error("Instantiating nonterminal did not resolve all types!");
 488
 489   // Add the pattern to the patterns map, add the record to the RecordKeeper,
 490   // return the new record.
 491   Patterns[New] = NewPat;
 492   Records.addDef(New);
 493   return Slot = New;
 494 }
 495
 496 // CalculateComputableValues - Fill in the ComputableValues map through
 497 // analysis of the patterns we are playing with.
 498 void InstrSelectorEmitter::CalculateComputableValues() {
 499   // Loop over all of the patterns, adding them to the ComputableValues map
 500   for (std::map<Record*, Pattern*>::iterator I = Patterns.begin(),
 501          E = Patterns.end(); I != E; ++I)
 502     if (I->second->isResolved())
 503       ComputableValues.addPattern(I->second);
 504 }
 505
 506 void InstrSelectorEmitter::run(std::ostream &OS) {
 507   // Type-check all of the node types to ensure we "understand" them.
 508   ReadNodeTypes();
 509
 510   // Read in all of the nonterminals, instructions, and expanders...
 511   ReadNonterminals();
 512   ReadInstructionPatterns();
 513   ReadExpanderPatterns();
 514
 515   // Instantiate any unresolved nonterminals with information from the context
 516   // that they are used in.
 517   InstantiateNonterminals();
 518
 519   // Clear InstantiatedNTs, we don't need it anymore...
 520   InstantiatedNTs.clear();
 521
 522   std::cerr << "Patterns aquired:\n";
 523   for (std::map<Record*, Pattern*>::iterator I = Patterns.begin(),
 524          E = Patterns.end(); I != E; ++I)
 525     if (I->second->isResolved())
 526       std::cerr << "  " << *I->second << "\n";
 527
 528   CalculateComputableValues();
 529
 530   // Output the slot number enums...
 531   OS << "\n\nenum { // Slot numbers...\n"
 532      << "  LastBuiltinSlot = ISD::NumBuiltinSlots-1, // Start numbering here\n";
 533   for (PatternOrganizer::iterator I = ComputableValues.begin(),
 534          E = ComputableValues.end(); I != E; ++I)
 535     OS << "  " << I->first << "_Slot,\n";
 536   OS << "  NumSlots\n};\n\n// Reduction value typedefs...\n";
 537
 538   // Output the reduction value typedefs...
 539   for (PatternOrganizer::iterator I = ComputableValues.begin(),
 540          E = ComputableValues.end(); I != E; ++I)
 541     OS << "typedef ReduceValue<unsigned, " << I->first
 542        << "_Slot> ReducedValue_" << I->first << ";\n";
 543
 544   // Output the pattern enums...
 545   OS << "\n\n"
 546      << "enum { // Patterns...\n"
 547      << "  NotComputed = 0,\n"
 548      << "  NoMatchPattern, \n";
 549   for (PatternOrganizer::iterator I = ComputableValues.begin(),
 550          E = ComputableValues.end(); I != E; ++I) {
 551     OS << "  // " << I->first << " patterns...\n";
 552     for (PatternOrganizer::NodesForSlot::iterator J = I->second.begin(),
 553            E = I->second.end(); J != E; ++J)
 554       for (unsigned i = 0, e = J->second.size(); i != e; ++i)
 555         OS << "  " << J->second[i]->getRecord()->getName() << "_Pattern,\n";
 556   }
 557   OS << "};\n\n";
 558
 559   // Start emitting the class...
 560   OS << "namespace {\n"
 561      << "  class " << Target.getName() << "ISel {\n"
 562      << "    SelectionDAG &DAG;\n"
 563      << "  public:\n"
 564      << "    X86ISel(SelectionDag &D) : DAG(D) {}\n"
 565      << "    void generateCode();\n"
 566      << "  private:\n"
 567      << "    unsigned makeAnotherReg(const TargetRegisterClass *RC) {\n"
 568      << "      return DAG.getMachineFunction().getSSARegMap()->createVirt"
 569                                        "ualRegister(RC);\n"
 570      << "    }\n\n"
 571      << "    // DAG matching methods for classes... all of these methods"
 572                                        " return the cost\n"
 573      <<"    // of producing a value of the specified class and type, which"
 574                                        " also gets\n"
 575      << "    // added to the DAG node.\n";
 576
 577   // Output all of the matching prototypes for slots...
 578   for (PatternOrganizer::iterator I = ComputableValues.begin(),
 579          E = ComputableValues.end(); I != E; ++I)
 580     OS << "  unsigned Match_" << I->first << "(SelectionDAGNode *N);\n";
 581   OS << "\n  // DAG matching methods for DAG nodes...\n";
 582
 583   // Output all of the matching prototypes for slot/node pairs
 584   for (PatternOrganizer::iterator I = ComputableValues.begin(),
 585          E = ComputableValues.end(); I != E; ++I)
 586     for (PatternOrganizer::NodesForSlot::iterator J = I->second.begin(),
 587            E = I->second.end(); J != E; ++J)
 588       OS << "  unsigned Match_" << I->first << "_" << J->first->getName()
 589          << "(SelectionDAGNode *N);\n";
 590
 591   // Output all of the dag reduction methods prototypes...
 592   OS << "\n  // DAG reduction methods...\n";
 593   for (PatternOrganizer::iterator I = ComputableValues.begin(),
 594          E = ComputableValues.end(); I != E; ++I)
 595     OS << "  ReducedValue_" << I->first << " *Reduce_" << I->first
 596        << "(SelectionDAGNode *N,\n" << std::string(25+2*I->first.size(), ' ')
 597        << "MachineBasicBlock *MBB);\n";
 598   OS << "  };\n}\n\n";
 599
 600   OS << "void X86ISel::generateCode() {\n"
 601      << "  SelectionDAGNode *Root = DAG.getRoot();\n"
 602      << "  assert(Root->getValueType() == ISD::Void && "
 603                                        "\"Root of DAG produces value??\");\n\n"
 604      << "  std::cerr << \"\\n\";\n"
 605      << "  unsigned Cost = Match_Void_Void(Root);\n"
 606      << "  if (Cost >= ~0U >> 1) {\n"
 607      << "    std::cerr << \"Match failed!\\n\";\n"
 608      << "    Root->dump();\n"
 609      << "    abort();\n"
 610      << "  }\n\n"
 611      << "  std::cerr << \"Total DAG Cost: \" << Cost << \"\\n\\n\";\n\n"
 612      << "  Reduce_Void_Void(Root, 0);\n"
 613      << "}\n\n"
 614      << "//===" << std::string(70, '-') << "===//\n"
 615      << "//  Matching methods...\n"
 616      << "//\n";
 617 }
 618