utils/TableGen/DAGISelEmitter.cpp

   1 //===- DAGISelEmitter.cpp - Generate an instruction selector --------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Chris Lattner and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This tablegen backend emits a DAG instruction selector.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "DAGISelEmitter.h"
  15 #include "Record.h"
  16 #include "llvm/ADT/StringExtras.h"
  17 #include "llvm/Support/Debug.h"
  18 #include <set>
  19 using namespace llvm;
  20
  21 //===----------------------------------------------------------------------===//
  22 // SDTypeConstraint implementation
  23 //
  24
  25 SDTypeConstraint::SDTypeConstraint(Record *R) {
  26   OperandNo = R->getValueAsInt("OperandNum");
  27
  28   if (R->isSubClassOf("SDTCisVT")) {
  29     ConstraintType = SDTCisVT;
  30     x.SDTCisVT_Info.VT = getValueType(R->getValueAsDef("VT"));
  31   } else if (R->isSubClassOf("SDTCisInt")) {
  32     ConstraintType = SDTCisInt;
  33   } else if (R->isSubClassOf("SDTCisFP")) {
  34     ConstraintType = SDTCisFP;
  35   } else if (R->isSubClassOf("SDTCisSameAs")) {
  36     ConstraintType = SDTCisSameAs;
  37     x.SDTCisSameAs_Info.OtherOperandNum = R->getValueAsInt("OtherOperandNum");
  38   } else if (R->isSubClassOf("SDTCisVTSmallerThanOp")) {
  39     ConstraintType = SDTCisVTSmallerThanOp;
  40     x.SDTCisVTSmallerThanOp_Info.OtherOperandNum =
  41       R->getValueAsInt("OtherOperandNum");
  42   } else {
  43     std::cerr << "Unrecognized SDTypeConstraint '" << R->getName() << "'!\n";
  44     exit(1);
  45   }
  46 }
  47
  48 /// getOperandNum - Return the node corresponding to operand #OpNo in tree
  49 /// N, which has NumResults results.
  50 TreePatternNode *SDTypeConstraint::getOperandNum(unsigned OpNo,
  51                                                  TreePatternNode *N,
  52                                                  unsigned NumResults) const {
  53   assert(NumResults == 1 && "We only work with single result nodes so far!");
  54
  55   if (OpNo < NumResults)
  56     return N;  // FIXME: need value #
  57   else
  58     return N->getChild(OpNo-NumResults);
  59 }
  60
  61 /// ApplyTypeConstraint - Given a node in a pattern, apply this type
  62 /// constraint to the nodes operands.  This returns true if it makes a
  63 /// change, false otherwise.  If a type contradiction is found, throw an
  64 /// exception.
  65 bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N,
  66                                            const SDNodeInfo &NodeInfo,
  67                                            TreePattern &TP) const {
  68   unsigned NumResults = NodeInfo.getNumResults();
  69   assert(NumResults == 1 && "We only work with single result nodes so far!");
  70
  71   // Check that the number of operands is sane.
  72   if (NodeInfo.getNumOperands() >= 0) {
  73     if (N->getNumChildren() != (unsigned)NodeInfo.getNumOperands())
  74       TP.error(N->getOperator()->getName() + " node requires exactly " +
  75                itostr(NodeInfo.getNumOperands()) + " operands!");
  76   }
  77
  78   TreePatternNode *NodeToApply = getOperandNum(OperandNo, N, NumResults);
  79
  80   switch (ConstraintType) {
  81   default: assert(0 && "Unknown constraint type!");
  82   case SDTCisVT:
  83     // Operand must be a particular type.
  84     return NodeToApply->UpdateNodeType(x.SDTCisVT_Info.VT, TP);
  85   case SDTCisInt:
  86     if (NodeToApply->hasTypeSet() && !MVT::isInteger(NodeToApply->getType()))
  87       NodeToApply->UpdateNodeType(MVT::i1, TP);  // throw an error.
  88
  89     // FIXME: can tell from the target if there is only one Int type supported.
  90     return false;
  91   case SDTCisFP:
  92     if (NodeToApply->hasTypeSet() &&
  93         !MVT::isFloatingPoint(NodeToApply->getType()))
  94       NodeToApply->UpdateNodeType(MVT::f32, TP);  // throw an error.
  95     // FIXME: can tell from the target if there is only one FP type supported.
  96     return false;
  97   case SDTCisSameAs: {
  98     TreePatternNode *OtherNode =
  99       getOperandNum(x.SDTCisSameAs_Info.OtherOperandNum, N, NumResults);
 100     return NodeToApply->UpdateNodeType(OtherNode->getType(), TP) |
 101            OtherNode->UpdateNodeType(NodeToApply->getType(), TP);
 102   }
 103   case SDTCisVTSmallerThanOp: {
 104     // The NodeToApply must be a leaf node that is a VT.  OtherOperandNum must
 105     // have an integer type that is smaller than the VT.
 106     if (!NodeToApply->isLeaf() ||
 107         !dynamic_cast<DefInit*>(NodeToApply->getLeafValue()) ||
 108         !static_cast<DefInit*>(NodeToApply->getLeafValue())->getDef()
 109                ->isSubClassOf("ValueType"))
 110       TP.error(N->getOperator()->getName() + " expects a VT operand!");
 111     MVT::ValueType VT =
 112      getValueType(static_cast<DefInit*>(NodeToApply->getLeafValue())->getDef());
 113     if (!MVT::isInteger(VT))
 114       TP.error(N->getOperator()->getName() + " VT operand must be integer!");
 115
 116     TreePatternNode *OtherNode =
 117       getOperandNum(x.SDTCisVTSmallerThanOp_Info.OtherOperandNum, N,NumResults);
 118     if (OtherNode->hasTypeSet() &&
 119         (!MVT::isInteger(OtherNode->getType()) ||
 120          OtherNode->getType() <= VT))
 121       OtherNode->UpdateNodeType(MVT::Other, TP);  // Throw an error.
 122     return false;
 123   }
 124   }
 125   return false;
 126 }
 127
 128
 129 //===----------------------------------------------------------------------===//
 130 // SDNodeInfo implementation
 131 //
 132 SDNodeInfo::SDNodeInfo(Record *R) : Def(R) {
 133   EnumName    = R->getValueAsString("Opcode");
 134   SDClassName = R->getValueAsString("SDClass");
 135   Record *TypeProfile = R->getValueAsDef("TypeProfile");
 136   NumResults = TypeProfile->getValueAsInt("NumResults");
 137   NumOperands = TypeProfile->getValueAsInt("NumOperands");
 138
 139   // Parse the type constraints.
 140   ListInit *Constraints = TypeProfile->getValueAsListInit("Constraints");
 141   for (unsigned i = 0, e = Constraints->getSize(); i != e; ++i) {
 142     assert(dynamic_cast<DefInit*>(Constraints->getElement(i)) &&
 143            "Constraints list should contain constraint definitions!");
 144     Record *Constraint =
 145       static_cast<DefInit*>(Constraints->getElement(i))->getDef();
 146     TypeConstraints.push_back(Constraint);
 147   }
 148 }
 149
 150 //===----------------------------------------------------------------------===//
 151 // TreePatternNode implementation
 152 //
 153
 154 TreePatternNode::~TreePatternNode() {
 155 #if 0 // FIXME: implement refcounted tree nodes!
 156   for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
 157     delete getChild(i);
 158 #endif
 159 }
 160
 161 /// UpdateNodeType - Set the node type of N to VT if VT contains
 162 /// information.  If N already contains a conflicting type, then throw an
 163 /// exception.  This returns true if any information was updated.
 164 ///
 165 bool TreePatternNode::UpdateNodeType(MVT::ValueType VT, TreePattern &TP) {
 166   if (VT == MVT::LAST_VALUETYPE || getType() == VT) return false;
 167   if (getType() == MVT::LAST_VALUETYPE) {
 168     setType(VT);
 169     return true;
 170   }
 171
 172   TP.error("Type inference contradiction found in node " +
 173            getOperator()->getName() + "!");
 174   return true; // unreachable
 175 }
 176
 177
 178 void TreePatternNode::print(std::ostream &OS) const {
 179   if (isLeaf()) {
 180     OS << *getLeafValue();
 181   } else {
 182     OS << "(" << getOperator()->getName();
 183   }
 184
 185   if (getType() == MVT::Other)
 186     OS << ":Other";
 187   else if (getType() == MVT::LAST_VALUETYPE)
 188     ;//OS << ":?";
 189   else
 190     OS << ":" << getType();
 191
 192   if (!isLeaf()) {
 193     if (getNumChildren() != 0) {
 194       OS << " ";
 195       getChild(0)->print(OS);
 196       for (unsigned i = 1, e = getNumChildren(); i != e; ++i) {
 197         OS << ", ";
 198         getChild(i)->print(OS);
 199       }
 200     }
 201     OS << ")";
 202   }
 203
 204   if (!PredicateFn.empty())
 205     OS << "<<" << PredicateFn << ">>";
 206   if (!getName().empty())
 207     OS << ":$" << getName();
 208
 209 }
 210 void TreePatternNode::dump() const {
 211   print(std::cerr);
 212 }
 213
 214 /// clone - Make a copy of this tree and all of its children.
 215 ///
 216 TreePatternNode *TreePatternNode::clone() const {
 217   TreePatternNode *New;
 218   if (isLeaf()) {
 219     New = new TreePatternNode(getLeafValue());
 220   } else {
 221     std::vector<TreePatternNode*> CChildren;
 222     CChildren.reserve(Children.size());
 223     for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
 224       CChildren.push_back(getChild(i)->clone());
 225     New = new TreePatternNode(getOperator(), CChildren);
 226   }
 227   New->setName(getName());
 228   New->setType(getType());
 229   New->setPredicateFn(getPredicateFn());
 230   return New;
 231 }
 232
 233 /// SubstituteFormalArguments - Replace the formal arguments in this tree
 234 /// with actual values specified by ArgMap.
 235 void TreePatternNode::
 236 SubstituteFormalArguments(std::map<std::string, TreePatternNode*> &ArgMap) {
 237   if (isLeaf()) return;
 238
 239   for (unsigned i = 0, e = getNumChildren(); i != e; ++i) {
 240     TreePatternNode *Child = getChild(i);
 241     if (Child->isLeaf()) {
 242       Init *Val = Child->getLeafValue();
 243       if (dynamic_cast<DefInit*>(Val) &&
 244           static_cast<DefInit*>(Val)->getDef()->getName() == "node") {
 245         // We found a use of a formal argument, replace it with its value.
 246         Child = ArgMap[Child->getName()];
 247         assert(Child && "Couldn't find formal argument!");
 248         setChild(i, Child);
 249       }
 250     } else {
 251       getChild(i)->SubstituteFormalArguments(ArgMap);
 252     }
 253   }
 254 }
 255
 256
 257 /// InlinePatternFragments - If this pattern refers to any pattern
 258 /// fragments, inline them into place, giving us a pattern without any
 259 /// PatFrag references.
 260 TreePatternNode *TreePatternNode::InlinePatternFragments(TreePattern &TP) {
 261   if (isLeaf()) return this;  // nothing to do.
 262   Record *Op = getOperator();
 263
 264   if (!Op->isSubClassOf("PatFrag")) {
 265     // Just recursively inline children nodes.
 266     for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
 267       setChild(i, getChild(i)->InlinePatternFragments(TP));
 268     return this;
 269   }
 270
 271   // Otherwise, we found a reference to a fragment.  First, look up its
 272   // TreePattern record.
 273   TreePattern *Frag = TP.getDAGISelEmitter().getPatternFragment(Op);
 274
 275   // Verify that we are passing the right number of operands.
 276   if (Frag->getNumArgs() != Children.size())
 277     TP.error("'" + Op->getName() + "' fragment requires " +
 278              utostr(Frag->getNumArgs()) + " operands!");
 279
 280   TreePatternNode *FragTree = Frag->getOnlyTree()->clone();
 281
 282   // Resolve formal arguments to their actual value.
 283   if (Frag->getNumArgs()) {
 284     // Compute the map of formal to actual arguments.
 285     std::map<std::string, TreePatternNode*> ArgMap;
 286     for (unsigned i = 0, e = Frag->getNumArgs(); i != e; ++i)
 287       ArgMap[Frag->getArgName(i)] = getChild(i)->InlinePatternFragments(TP);
 288
 289     FragTree->SubstituteFormalArguments(ArgMap);
 290   }
 291
 292   FragTree->setName(getName());
 293
 294   // Get a new copy of this fragment to stitch into here.
 295   //delete this;    // FIXME: implement refcounting!
 296   return FragTree;
 297 }
 298
 299 /// ApplyTypeConstraints - Apply all of the type constraints relevent to
 300 /// this node and its children in the tree.  This returns true if it makes a
 301 /// change, false otherwise.  If a type contradiction is found, throw an
 302 /// exception.
 303 bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP) {
 304   if (isLeaf()) return false;
 305
 306   // special handling for set, which isn't really an SDNode.
 307   if (getOperator()->getName() == "set") {
 308     assert (getNumChildren() == 2 && "Only handle 2 operand set's for now!");
 309     bool MadeChange = getChild(0)->ApplyTypeConstraints(TP);
 310     MadeChange |= getChild(1)->ApplyTypeConstraints(TP);
 311
 312     // Types of operands must match.
 313     MadeChange |= getChild(0)->UpdateNodeType(getChild(1)->getType(), TP);
 314     MadeChange |= getChild(1)->UpdateNodeType(getChild(0)->getType(), TP);
 315     MadeChange |= UpdateNodeType(MVT::isVoid, TP);
 316     return MadeChange;
 317   }
 318
 319   const SDNodeInfo &NI = TP.getDAGISelEmitter().getSDNodeInfo(getOperator());
 320
 321   bool MadeChange = NI.ApplyTypeConstraints(this, TP);
 322   for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
 323     MadeChange |= getChild(i)->ApplyTypeConstraints(TP);
 324   return MadeChange;
 325 }
 326
 327
 328 //===----------------------------------------------------------------------===//
 329 // TreePattern implementation
 330 //
 331
 332 TreePattern::TreePattern(PatternType pty, Record *TheRec,
 333                          const std::vector<DagInit *> &RawPat,
 334                          DAGISelEmitter &ise)
 335   : PTy(pty), TheRecord(TheRec), ISE(ise) {
 336
 337   for (unsigned i = 0, e = RawPat.size(); i != e; ++i)
 338     Trees.push_back(ParseTreePattern(RawPat[i]));
 339
 340   // Sanity checks and cleanup.
 341   switch (PTy) {
 342   case PatFrag: {
 343     assert(Trees.size() == 1 && "How can we have more than one pattern here?");
 344
 345     // Validate arguments list, convert it to map, to discard duplicates.
 346     std::set<std::string> OperandsMap(Args.begin(), Args.end());
 347
 348     if (OperandsMap.count(""))
 349       error("Cannot have unnamed 'node' values in pattern fragment!");
 350
 351     // Parse the operands list.
 352     DagInit *OpsList = TheRec->getValueAsDag("Operands");
 353     if (OpsList->getNodeType()->getName() != "ops")
 354       error("Operands list should start with '(ops ... '!");
 355
 356     // Copy over the arguments.
 357     Args.clear();
 358     for (unsigned i = 0, e = OpsList->getNumArgs(); i != e; ++i) {
 359       if (!dynamic_cast<DefInit*>(OpsList->getArg(i)) ||
 360           static_cast<DefInit*>(OpsList->getArg(i))->
 361                           getDef()->getName() != "node")
 362         error("Operands list should all be 'node' values.");
 363       if (OpsList->getArgName(i).empty())
 364         error("Operands list should have names for each operand!");
 365       if (!OperandsMap.count(OpsList->getArgName(i)))
 366         error("'" + OpsList->getArgName(i) +
 367               "' does not occur in pattern or was multiply specified!");
 368       OperandsMap.erase(OpsList->getArgName(i));
 369       Args.push_back(OpsList->getArgName(i));
 370     }
 371
 372     if (!OperandsMap.empty())
 373       error("Operands list does not contain an entry for operand '" +
 374             *OperandsMap.begin() + "'!");
 375
 376     break;
 377   }
 378   default:
 379     if (!Args.empty())
 380       error("Only pattern fragments can have operands (use 'node' values)!");
 381     break;
 382   }
 383 }
 384
 385 void TreePattern::error(const std::string &Msg) const {
 386   std::string M = "In ";
 387   switch (PTy) {
 388     case PatFrag:     M += "patfrag "; break;
 389     case Instruction: M += "instruction "; break;
 390   }
 391   throw M + TheRecord->getName() + ": " + Msg;
 392 }
 393
 394 /// getIntrinsicType - Check to see if the specified record has an intrinsic
 395 /// type which should be applied to it.  This infer the type of register
 396 /// references from the register file information, for example.
 397 ///
 398 MVT::ValueType TreePattern::getIntrinsicType(Record *R) const {
 399   // Check to see if this is a register or a register class...
 400   if (R->isSubClassOf("RegisterClass"))
 401     return getValueType(R->getValueAsDef("RegType"));
 402   else if (R->isSubClassOf("PatFrag")) {
 403     // Pattern fragment types will be resolved when they are inlined.
 404     return MVT::LAST_VALUETYPE;
 405   } else if (R->isSubClassOf("Register")) {
 406     assert(0 && "Explicit registers not handled here yet!\n");
 407     return MVT::LAST_VALUETYPE;
 408   } else if (R->isSubClassOf("ValueType")) {
 409     // Using a VTSDNode.
 410     return MVT::Other;
 411   } else if (R->getName() == "node") {
 412     // Placeholder.
 413     return MVT::LAST_VALUETYPE;
 414   }
 415
 416   error("Unknown value used: " + R->getName());
 417   return MVT::Other;
 418 }
 419
 420 TreePatternNode *TreePattern::ParseTreePattern(DagInit *Dag) {
 421   Record *Operator = Dag->getNodeType();
 422
 423   if (Operator->isSubClassOf("ValueType")) {
 424     // If the operator is a ValueType, then this must be "type cast" of a leaf
 425     // node.
 426     if (Dag->getNumArgs() != 1)
 427       error("Type cast only valid for a leaf node!");
 428
 429     Init *Arg = Dag->getArg(0);
 430     TreePatternNode *New;
 431     if (DefInit *DI = dynamic_cast<DefInit*>(Arg)) {
 432       New = new TreePatternNode(DI);
 433       // If it's a regclass or something else known, set the type.
 434       New->setType(getIntrinsicType(DI->getDef()));
 435     } else if (DagInit *DI = dynamic_cast<DagInit*>(Arg)) {
 436       New = ParseTreePattern(DI);
 437     } else {
 438       Arg->dump();
 439       error("Unknown leaf value for tree pattern!");
 440       return 0;
 441     }
 442
 443     // Apply the type cast.
 444     New->UpdateNodeType(getValueType(Operator), *this);
 445     return New;
 446   }
 447
 448   // Verify that this is something that makes sense for an operator.
 449   if (!Operator->isSubClassOf("PatFrag") && !Operator->isSubClassOf("SDNode") &&
 450       Operator->getName() != "set")
 451     error("Unrecognized node '" + Operator->getName() + "'!");
 452
 453   std::vector<TreePatternNode*> Children;
 454
 455   for (unsigned i = 0, e = Dag->getNumArgs(); i != e; ++i) {
 456     Init *Arg = Dag->getArg(i);
 457     if (DagInit *DI = dynamic_cast<DagInit*>(Arg)) {
 458       Children.push_back(ParseTreePattern(DI));
 459       Children.back()->setName(Dag->getArgName(i));
 460     } else if (DefInit *DefI = dynamic_cast<DefInit*>(Arg)) {
 461       Record *R = DefI->getDef();
 462       // Direct reference to a leaf DagNode or PatFrag?  Turn it into a
 463       // TreePatternNode if its own.
 464       if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrag")) {
 465         Dag->setArg(i, new DagInit(R,
 466                               std::vector<std::pair<Init*, std::string> >()));
 467         --i;  // Revisit this node...
 468       } else {
 469         TreePatternNode *Node = new TreePatternNode(DefI);
 470         Node->setName(Dag->getArgName(i));
 471         Children.push_back(Node);
 472
 473         // If it's a regclass or something else known, set the type.
 474         Node->setType(getIntrinsicType(R));
 475
 476         // Input argument?
 477         if (R->getName() == "node") {
 478           if (Dag->getArgName(i).empty())
 479             error("'node' argument requires a name to match with operand list");
 480           Args.push_back(Dag->getArgName(i));
 481         }
 482       }
 483     } else {
 484       Arg->dump();
 485       error("Unknown leaf value for tree pattern!");
 486     }
 487   }
 488
 489   return new TreePatternNode(Operator, Children);
 490 }
 491
 492 /// InferAllTypes - Infer/propagate as many types throughout the expression
 493 /// patterns as possible.  Return true if all types are infered, false
 494 /// otherwise.  Throw an exception if a type contradiction is found.
 495 bool TreePattern::InferAllTypes() {
 496   bool MadeChange = true;
 497   while (MadeChange) {
 498     MadeChange = false;
 499     for (unsigned i = 0, e = Trees.size(); i != e; ++i)
 500       MadeChange |= Trees[i]->ApplyTypeConstraints(*this);
 501   }
 502
 503   bool HasUnresolvedTypes = false;
 504   for (unsigned i = 0, e = Trees.size(); i != e; ++i)
 505     HasUnresolvedTypes |= Trees[i]->ContainsUnresolvedType();
 506   return !HasUnresolvedTypes;
 507 }
 508
 509 void TreePattern::print(std::ostream &OS) const {
 510   switch (getPatternType()) {
 511   case TreePattern::PatFrag:     OS << "PatFrag pattern "; break;
 512   case TreePattern::Instruction: OS << "Inst pattern "; break;
 513   }
 514
 515   OS << getRecord()->getName();
 516   if (!Args.empty()) {
 517     OS << "(" << Args[0];
 518     for (unsigned i = 1, e = Args.size(); i != e; ++i)
 519       OS << ", " << Args[i];
 520     OS << ")";
 521   }
 522   OS << ": ";
 523
 524   if (Trees.size() > 1)
 525     OS << "[\n";
 526   for (unsigned i = 0, e = Trees.size(); i != e; ++i) {
 527     OS << "\t";
 528     Trees[i]->print(OS);
 529     OS << "\n";
 530   }
 531
 532   if (Trees.size() > 1)
 533     OS << "]\n";
 534 }
 535
 536 void TreePattern::dump() const { print(std::cerr); }
 537
 538
 539
 540 //===----------------------------------------------------------------------===//
 541 // DAGISelEmitter implementation
 542 //
 543
 544 // Parse all of the SDNode definitions for the target, populating SDNodes.
 545 void DAGISelEmitter::ParseNodeInfo() {
 546   std::vector<Record*> Nodes = Records.getAllDerivedDefinitions("SDNode");
 547   while (!Nodes.empty()) {
 548     SDNodes.insert(std::make_pair(Nodes.back(), Nodes.back()));
 549     Nodes.pop_back();
 550   }
 551 }
 552
 553 /// ParseAndResolvePatternFragments - Parse all of the PatFrag definitions in
 554 /// the .td file, building up the PatternFragments map.  After we've collected
 555 /// them all, inline fragments together as necessary, so that there are no
 556 /// references left inside a pattern fragment to a pattern fragment.
 557 ///
 558 /// This also emits all of the predicate functions to the output file.
 559 ///
 560 void DAGISelEmitter::ParseAndResolvePatternFragments(std::ostream &OS) {
 561   std::vector<Record*> Fragments = Records.getAllDerivedDefinitions("PatFrag");
 562
 563   // First step, parse all of the fragments and emit predicate functions.
 564   OS << "\n// Predicate functions.\n";
 565   for (unsigned i = 0, e = Fragments.size(); i != e; ++i) {
 566     std::vector<DagInit*> Trees;
 567     Trees.push_back(Fragments[i]->getValueAsDag("Fragment"));
 568     TreePattern *P = new TreePattern(TreePattern::PatFrag, Fragments[i],
 569                                      Trees, *this);
 570     PatternFragments[Fragments[i]] = P;
 571
 572     // If there is a code init for this fragment, emit the predicate code and
 573     // keep track of the fact that this fragment uses it.
 574     CodeInit *CI =
 575       dynamic_cast<CodeInit*>(Fragments[i]->getValueInit("Predicate"));
 576     if (!CI->getValue().empty()) {
 577       assert(!P->getOnlyTree()->isLeaf() && "Can't be a leaf!");
 578       std::string ClassName =
 579         getSDNodeInfo(P->getOnlyTree()->getOperator()).getSDClassName();
 580       const char *C2 = ClassName == "SDNode" ? "N" : "inN";
 581
 582       OS << "static inline bool Predicate_" << Fragments[i]->getName()
 583          << "(SDNode *" << C2 << ") {\n";
 584       if (ClassName != "SDNode")
 585         OS << "  " << ClassName << " *N = cast<" << ClassName << ">(inN);\n";
 586       OS << CI->getValue() << "\n}\n";
 587       P->getOnlyTree()->setPredicateFn("Predicate_"+Fragments[i]->getName());
 588     }
 589   }
 590
 591   OS << "\n\n";
 592
 593   // Now that we've parsed all of the tree fragments, do a closure on them so
 594   // that there are not references to PatFrags left inside of them.
 595   for (std::map<Record*, TreePattern*>::iterator I = PatternFragments.begin(),
 596        E = PatternFragments.end(); I != E; ++I) {
 597     TreePattern *ThePat = I->second;
 598     ThePat->InlinePatternFragments();
 599
 600     // Infer as many types as possible.  Don't worry about it if we don't infer
 601     // all of them, some may depend on the inputs of the pattern.
 602     try {
 603       ThePat->InferAllTypes();
 604     } catch (...) {
 605       // If this pattern fragment is not supported by this target (no types can
 606       // satisfy its constraints), just ignore it.  If the bogus pattern is
 607       // actually used by instructions, the type consistency error will be
 608       // reported there.
 609     }
 610
 611     // If debugging, print out the pattern fragment result.
 612     DEBUG(ThePat->dump());
 613   }
 614 }
 615
 616 /// ParseAndResolveInstructions - Parse all of the instructions, inlining and
 617 /// resolving any fragments involved.  This populates the Instructions list with
 618 /// fully resolved instructions.
 619 void DAGISelEmitter::ParseAndResolveInstructions() {
 620   std::vector<Record*> Instrs = Records.getAllDerivedDefinitions("Instruction");
 621
 622   for (unsigned i = 0, e = Instrs.size(); i != e; ++i) {
 623     if (!dynamic_cast<ListInit*>(Instrs[i]->getValueInit("Pattern")))
 624       continue; // no pattern yet, ignore it.
 625
 626     ListInit *LI = Instrs[i]->getValueAsListInit("Pattern");
 627     if (LI->getSize() == 0) continue;  // no pattern.
 628
 629     std::vector<DagInit*> Trees;
 630     for (unsigned j = 0, e = LI->getSize(); j != e; ++j)
 631       Trees.push_back((DagInit*)LI->getElement(j));
 632
 633     // Parse the instruction.
 634     TreePattern *I = new TreePattern(TreePattern::Instruction, Instrs[i],
 635                                      Trees, *this);
 636     // Inline pattern fragments into it.
 637     I->InlinePatternFragments();
 638
 639     // Infer as many types as possible.  If we cannot infer all of them, we can
 640     // never do anything with this instruction pattern: report it to the user.
 641     if (!I->InferAllTypes()) {
 642       I->dump();
 643       I->error("Could not infer all types in pattern!");
 644     }
 645
 646     // Verify that the top-level forms in the instruction are of void type.
 647     for (unsigned j = 0, e = I->getNumTrees(); j != e; ++j)
 648       if (I->getTree(j)->getType() != MVT::isVoid) {
 649         I->dump();
 650         I->error("Top-level forms in instruction pattern should have"
 651                  " void types");
 652       }
 653
 654     DEBUG(I->dump());
 655     Instructions.push_back(I);
 656   }
 657 }
 658
 659 void DAGISelEmitter::EmitInstructionSelector(std::ostream &OS) {
 660   // Emit boilerplate.
 661   OS << "// The main instruction selector code.\n"
 662      << "SDOperand " << Target.getName()
 663      << "DAGToDAGISel::SelectCode(SDOperand Op) {\n"
 664      << "  SDNode *N = Op.Val;\n"
 665      << "  if (N->getOpcode() >= ISD::BUILTIN_OP_END &&\n"
 666      << "      N->getOpcode() < PPCISD::FIRST_NUMBER)\n"
 667      << "    return Op;   // Already selected.\n\n"
 668      << "  switch (N->getOpcode()) {\n"
 669      << "  default: break;\n"
 670      << "  case ISD::EntryToken:       // These leaves remain the same.\n"
 671      << "    return Op;\n"
 672      << "  case ISD::AssertSext:\n"
 673      << "  case ISD::AssertZext:\n"
 674      << "    return Select(N->getOperand(0));\n";
 675
 676
 677
 678   OS << "  } // end of big switch.\n\n"
 679      << "  std::cerr << \"Cannot yet select: \";\n"
 680      << "  N->dump();\n"
 681      << "  std::cerr << '\\n';\n"
 682      << "  abort();\n"
 683      << "}\n";
 684 }
 685
 686
 687 void DAGISelEmitter::run(std::ostream &OS) {
 688   EmitSourceFileHeader("DAG Instruction Selector for the " + Target.getName() +
 689                        " target", OS);
 690
 691   ParseNodeInfo();
 692   ParseAndResolvePatternFragments(OS);
 693   ParseAndResolveInstructions();
 694
 695   // TODO: convert some instructions to expanders if needed or something.
 696
 697   EmitInstructionSelector(OS);
 698
 699   for (std::map<Record*, TreePattern*>::iterator I = PatternFragments.begin(),
 700        E = PatternFragments.end(); I != E; ++I)
 701     delete I->second;
 702   PatternFragments.clear();
 703
 704   for (unsigned i = 0, e = Instructions.size(); i != e; ++i)
 705     delete Instructions[i];
 706   Instructions.clear();
 707 }