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 //===----------------------------------------------------------------------===//
  23 // TreePatternNode implementation
  24 //
  25
  26 TreePatternNode::~TreePatternNode() {
  27 #if 0 // FIXME: implement refcounted tree nodes!
  28   for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
  29     delete getChild(i);
  30 #endif
  31 }
  32
  33 void TreePatternNode::print(std::ostream &OS) const {
  34   if (isLeaf()) {
  35     OS << *getLeafValue();
  36   } else {
  37     OS << "(" << getOperator()->getName();
  38   }
  39
  40   if (getType() == MVT::Other)
  41     OS << ":Other";
  42   else if (getType() == MVT::LAST_VALUETYPE)
  43     ;//OS << ":?";
  44   else
  45     OS << ":" << getType();
  46
  47   if (!isLeaf()) {
  48     if (getNumChildren() != 0) {
  49       OS << " ";
  50       getChild(0)->print(OS);
  51       for (unsigned i = 1, e = getNumChildren(); i != e; ++i) {
  52         OS << ", ";
  53         getChild(i)->print(OS);
  54       }
  55     }
  56     OS << ")";
  57   }
  58
  59   if (!PredicateFn.empty())
  60     OS << "<<" << PredicateFn << ">>";
  61   if (!getName().empty())
  62     OS << ":$" << getName();
  63
  64 }
  65 void TreePatternNode::dump() const {
  66   print(std::cerr);
  67 }
  68
  69 /// clone - Make a copy of this tree and all of its children.
  70 ///
  71 TreePatternNode *TreePatternNode::clone() const {
  72   TreePatternNode *New;
  73   if (isLeaf()) {
  74     New = new TreePatternNode(getLeafValue());
  75   } else {
  76     std::vector<TreePatternNode*> CChildren;
  77     CChildren.reserve(Children.size());
  78     for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
  79       CChildren.push_back(getChild(i)->clone());
  80     New = new TreePatternNode(getOperator(), CChildren);
  81   }
  82   New->setName(getName());
  83   New->setType(getType());
  84   New->setPredicateFn(getPredicateFn());
  85   return New;
  86 }
  87
  88 void TreePatternNode::
  89 SubstituteFormalArguments(std::map<std::string, TreePatternNode*> &ArgMap) {
  90   if (isLeaf()) return;
  91
  92   for (unsigned i = 0, e = getNumChildren(); i != e; ++i) {
  93     TreePatternNode *Child = getChild(i);
  94     if (Child->isLeaf()) {
  95       Init *Val = Child->getLeafValue();
  96       if (dynamic_cast<DefInit*>(Val) &&
  97           static_cast<DefInit*>(Val)->getDef()->getName() == "node") {
  98         // We found a use of a formal argument, replace it with its value.
  99         Child = ArgMap[Child->getName()];
 100         assert(Child && "Couldn't find formal argument!");
 101         setChild(i, Child);
 102       }
 103     } else {
 104       getChild(i)->SubstituteFormalArguments(ArgMap);
 105     }
 106   }
 107 }
 108
 109
 110 /// InlinePatternFragments - If this pattern refers to any pattern
 111 /// fragments, inline them into place, giving us a pattern without any
 112 /// PatFrag references.
 113 TreePatternNode *TreePatternNode::InlinePatternFragments(TreePattern &TP) {
 114   if (isLeaf()) return this;  // nothing to do.
 115   Record *Op = getOperator();
 116
 117   if (!Op->isSubClassOf("PatFrag")) {
 118     // Just recursively inline children nodes.
 119     for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
 120       setChild(i, getChild(i)->InlinePatternFragments(TP));
 121     return this;
 122   }
 123
 124   // Otherwise, we found a reference to a fragment.  First, look up its
 125   // TreePattern record.
 126   TreePattern *Frag = TP.getDAGISelEmitter().getPatternFragment(Op);
 127
 128   // Verify that we are passing the right number of operands.
 129   if (Frag->getNumArgs() != Children.size())
 130     TP.error("'" + Op->getName() + "' fragment requires " +
 131              utostr(Frag->getNumArgs()) + " operands!");
 132
 133   TreePatternNode *FragTree = Frag->getTrees()[0]->clone();
 134
 135   // Resolve formal arguments to their actual value.
 136   if (Frag->getNumArgs()) {
 137     // Compute the map of formal to actual arguments.
 138     std::map<std::string, TreePatternNode*> ArgMap;
 139     for (unsigned i = 0, e = Frag->getNumArgs(); i != e; ++i)
 140       ArgMap[Frag->getArgName(i)] = getChild(i)->InlinePatternFragments(TP);
 141
 142     FragTree->SubstituteFormalArguments(ArgMap);
 143   }
 144
 145   // Get a new copy of this fragment to stitch into here.
 146   //delete this;    // FIXME: implement refcounting!
 147   return FragTree;
 148 }
 149
 150 //===----------------------------------------------------------------------===//
 151 // TreePattern implementation
 152 //
 153
 154 TreePattern::TreePattern(PatternType pty, Record *TheRec,
 155                          const std::vector<DagInit *> &RawPat,
 156                          DAGISelEmitter &ise)
 157   : PTy(pty), TheRecord(TheRec), ISE(ise) {
 158
 159   for (unsigned i = 0, e = RawPat.size(); i != e; ++i)
 160     Trees.push_back(ParseTreePattern(RawPat[i]));
 161
 162   // Sanity checks and cleanup.
 163   switch (PTy) {
 164   case PatFrag: {
 165     assert(Trees.size() == 1 && "How can we have more than one pattern here?");
 166
 167     // Validate arguments list, convert it to map, to discard duplicates.
 168     std::set<std::string> OperandsMap(Args.begin(), Args.end());
 169
 170     if (OperandsMap.count(""))
 171       error("Cannot have unnamed 'node' values in pattern fragment!");
 172
 173     // Parse the operands list.
 174     DagInit *OpsList = TheRec->getValueAsDag("Operands");
 175     if (OpsList->getNodeType()->getName() != "ops")
 176       error("Operands list should start with '(ops ... '!");
 177
 178     // Copy over the arguments.
 179     Args.clear();
 180     for (unsigned i = 0, e = OpsList->getNumArgs(); i != e; ++i) {
 181       if (!dynamic_cast<DefInit*>(OpsList->getArg(i)) ||
 182           static_cast<DefInit*>(OpsList->getArg(i))->
 183                           getDef()->getName() != "node")
 184         error("Operands list should all be 'node' values.");
 185       if (OpsList->getArgName(i).empty())
 186         error("Operands list should have names for each operand!");
 187       if (!OperandsMap.count(OpsList->getArgName(i)))
 188         error("'" + OpsList->getArgName(i) +
 189               "' does not occur in pattern or was multiply specified!");
 190       OperandsMap.erase(OpsList->getArgName(i));
 191       Args.push_back(OpsList->getArgName(i));
 192     }
 193
 194     if (!OperandsMap.empty())
 195       error("Operands list does not contain an entry for operand '" +
 196             *OperandsMap.begin() + "'!");
 197
 198     break;
 199   }
 200   default:
 201     if (!Args.empty())
 202       error("Only pattern fragments can have operands (use 'node' values)!");
 203     break;
 204   }
 205 }
 206
 207 void TreePattern::error(const std::string &Msg) const {
 208   std::string M = "In ";
 209   switch (PTy) {
 210     case PatFrag:     M += "patfrag "; break;
 211     case Instruction: M += "instruction "; break;
 212   }
 213   throw M + TheRecord->getName() + ": " + Msg;
 214 }
 215
 216 /// getIntrinsicType - Check to see if the specified record has an intrinsic
 217 /// type which should be applied to it.  This infer the type of register
 218 /// references from the register file information, for example.
 219 ///
 220 MVT::ValueType TreePattern::getIntrinsicType(Record *R) const {
 221   // Check to see if this is a register or a register class...
 222   if (R->isSubClassOf("RegisterClass"))
 223     return getValueType(R->getValueAsDef("RegType"));
 224   else if (R->isSubClassOf("PatFrag")) {
 225     //return ISE.ReadNonterminal(R)->getTree()->getType();
 226     return MVT::LAST_VALUETYPE;
 227   } else if (R->isSubClassOf("Register")) {
 228     assert(0 && "Explicit registers not handled here yet!\n");
 229     return MVT::LAST_VALUETYPE;
 230   } else if (R->isSubClassOf("ValueType")) {
 231     // Using a VTSDNode.
 232     return MVT::Other;
 233   } else if (R->getName() == "node") {
 234     // Placeholder.
 235     return MVT::LAST_VALUETYPE;
 236   }
 237
 238   error("Unknown value used: " + R->getName());
 239   return MVT::Other;
 240 }
 241
 242 TreePatternNode *TreePattern::ParseTreePattern(DagInit *Dag) {
 243   Record *Operator = Dag->getNodeType();
 244
 245   if (Operator->isSubClassOf("ValueType")) {
 246     // If the operator is a ValueType, then this must be "type cast" of a leaf
 247     // node.
 248     if (Dag->getNumArgs() != 1)
 249       error("Type cast only valid for a leaf node!");
 250
 251     Init *Arg = Dag->getArg(0);
 252     TreePatternNode *New;
 253     if (DefInit *DI = dynamic_cast<DefInit*>(Arg)) {
 254       New = new TreePatternNode(DI);
 255       // If it's a regclass or something else known, set the type.
 256       New->setType(getIntrinsicType(DI->getDef()));
 257     } else if (DagInit *DI = dynamic_cast<DagInit*>(Arg)) {
 258       New = ParseTreePattern(DI);
 259     } else {
 260       Arg->dump();
 261       error("Unknown leaf value for tree pattern!");
 262       return 0;
 263     }
 264
 265     // Apply the type cast...
 266     assert(0 && "unimp yet");
 267     //New->updateNodeType(getValueType(Operator), TheRecord->getName());
 268     return New;
 269   }
 270
 271   // Verify that this is something that makes sense for an operator.
 272   if (!Operator->isSubClassOf("PatFrag") && !Operator->isSubClassOf("SDNode") &&
 273       Operator->getName() != "set")
 274     error("Unrecognized node '" + Operator->getName() + "'!");
 275
 276   std::vector<TreePatternNode*> Children;
 277
 278   for (unsigned i = 0, e = Dag->getNumArgs(); i != e; ++i) {
 279     Init *Arg = Dag->getArg(i);
 280     if (DagInit *DI = dynamic_cast<DagInit*>(Arg)) {
 281       Children.push_back(ParseTreePattern(DI));
 282       Children.back()->setName(Dag->getArgName(i));
 283     } else if (DefInit *DefI = dynamic_cast<DefInit*>(Arg)) {
 284       Record *R = DefI->getDef();
 285       // Direct reference to a leaf DagNode or PatFrag?  Turn it into a
 286       // TreePatternNode if its own.
 287       if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrag")) {
 288         Dag->setArg(i, new DagInit(R,
 289                               std::vector<std::pair<Init*, std::string> >()));
 290         --i;  // Revisit this node...
 291       } else {
 292         TreePatternNode *Node = new TreePatternNode(DefI);
 293         Node->setName(Dag->getArgName(i));
 294         Children.push_back(Node);
 295
 296         // If it's a regclass or something else known, set the type.
 297         Node->setType(getIntrinsicType(R));
 298
 299         // Input argument?
 300         if (R->getName() == "node") {
 301           if (Dag->getArgName(i).empty())
 302             error("'node' argument requires a name to match with operand list");
 303           Args.push_back(Dag->getArgName(i));
 304         }
 305       }
 306     } else {
 307       Arg->dump();
 308       error("Unknown leaf value for tree pattern!");
 309     }
 310   }
 311
 312   return new TreePatternNode(Operator, Children);
 313 }
 314
 315 void TreePattern::print(std::ostream &OS) const {
 316   switch (getPatternType()) {
 317   case TreePattern::PatFrag:     OS << "PatFrag pattern "; break;
 318   case TreePattern::Instruction: OS << "Inst pattern "; break;
 319   }
 320
 321   OS << getRecord()->getName();
 322   if (!Args.empty()) {
 323     OS << "(" << Args[0];
 324     for (unsigned i = 1, e = Args.size(); i != e; ++i)
 325       OS << ", " << Args[i];
 326     OS << ")";
 327   }
 328   OS << ": ";
 329
 330   if (Trees.size() > 1)
 331     OS << "[\n";
 332   for (unsigned i = 0, e = Trees.size(); i != e; ++i) {
 333     OS << "\t";
 334     Trees[i]->print(OS);
 335     OS << "\n";
 336   }
 337
 338   if (Trees.size() > 1)
 339     OS << "]\n";
 340 }
 341
 342 void TreePattern::dump() const { print(std::cerr); }
 343
 344
 345
 346 //===----------------------------------------------------------------------===//
 347 // DAGISelEmitter implementation
 348 //
 349
 350 /// ParseAndResolvePatternFragments - Parse all of the PatFrag definitions in
 351 /// the .td file, building up the PatternFragments map.  After we've collected
 352 /// them all, inline fragments together as necessary, so that there are no
 353 /// references left inside a pattern fragment to a pattern fragment.
 354 ///
 355 /// This also emits all of the predicate functions to the output file.
 356 ///
 357 void DAGISelEmitter::ParseAndResolvePatternFragments(std::ostream &OS) {
 358   std::vector<Record*> Fragments = Records.getAllDerivedDefinitions("PatFrag");
 359
 360   // First step, parse all of the fragments and emit predicate functions.
 361   OS << "\n// Predicate functions.\n";
 362   for (unsigned i = 0, e = Fragments.size(); i != e; ++i) {
 363     std::vector<DagInit*> Trees;
 364     Trees.push_back(Fragments[i]->getValueAsDag("Fragment"));
 365     TreePattern *P = new TreePattern(TreePattern::PatFrag, Fragments[i],
 366                                      Trees, *this);
 367     PatternFragments[Fragments[i]] = P;
 368
 369     // If there is a code init for this fragment, emit the predicate code and
 370     // keep track of the fact that this fragment uses it.
 371     CodeInit *CI =
 372       dynamic_cast<CodeInit*>(Fragments[i]->getValueInit("Predicate"));
 373     if (!CI->getValue().empty()) {
 374       assert(!P->getTrees()[0]->isLeaf() && "Can't be a leaf!");
 375       std::string ClassName =
 376           P->getTrees()[0]->getOperator()->getValueAsString("SDClass");
 377       const char *C2 = ClassName == "SDNode" ? "N" : "inN";
 378
 379       OS << "static inline bool Predicate_" << Fragments[i]->getName()
 380          << "(SDNode *" << C2 << ") {\n";
 381       if (ClassName != "SDNode")
 382         OS << "  " << ClassName << " *N = cast<" << ClassName << ">(inN);\n";
 383       OS << CI->getValue() << "\n}\n";
 384       P->getTrees()[0]->setPredicateFn("Predicate_"+Fragments[i]->getName());
 385     }
 386   }
 387
 388   OS << "\n\n";
 389
 390   // Now that we've parsed all of the tree fragments, do a closure on them so
 391   // that there are not references to PatFrags left inside of them.
 392   for (std::map<Record*, TreePattern*>::iterator I = PatternFragments.begin(),
 393        E = PatternFragments.end(); I != E; ++I) {
 394     I->second->InlinePatternFragments();
 395     // If debugging, print out the pattern fragment result.
 396     DEBUG(I->second->dump());
 397   }
 398 }
 399
 400 /// ParseAndResolveInstructions - Parse all of the instructions, inlining and
 401 /// resolving any fragments involved.  This populates the Instructions list with
 402 /// fully resolved instructions.
 403 void DAGISelEmitter::ParseAndResolveInstructions() {
 404   std::vector<Record*> Instrs = Records.getAllDerivedDefinitions("Instruction");
 405
 406   for (unsigned i = 0, e = Instrs.size(); i != e; ++i) {
 407     if (!dynamic_cast<ListInit*>(Instrs[i]->getValueInit("Pattern")))
 408       continue; // no pattern yet, ignore it.
 409
 410     ListInit *LI = Instrs[i]->getValueAsListInit("Pattern");
 411     if (LI->getSize() == 0) continue;  // no pattern.
 412
 413     std::vector<DagInit*> Trees;
 414     for (unsigned j = 0, e = LI->getSize(); j != e; ++j)
 415       Trees.push_back((DagInit*)LI->getElement(j));
 416
 417     // Parse the instruction.
 418     Instructions.push_back(new TreePattern(TreePattern::Instruction, Instrs[i],
 419                                            Trees, *this));
 420     // Inline pattern fragments into it.
 421     Instructions.back()->InlinePatternFragments();
 422
 423     DEBUG(std::cerr << Instrs[i]->getName() << ": ");
 424     DEBUG(Instructions.back()->dump());
 425   }
 426 }
 427
 428 void DAGISelEmitter::EmitInstructionSelector(std::ostream &OS) {
 429   // Emit boilerplate.
 430   OS << "// The main instruction selector code.\n"
 431      << "SDOperand " << Target.getName()
 432      << "DAGToDAGISel::SelectCode(SDOperand Op) {\n"
 433      << "  SDNode *N = Op.Val;\n"
 434      << "  if (N->getOpcode() >= ISD::BUILTIN_OP_END &&\n"
 435      << "      N->getOpcode() < PPCISD::FIRST_NUMBER)\n"
 436      << "    return Op;   // Already selected.\n\n"
 437      << "  switch (N->getOpcode()) {\n"
 438      << "  default: break;\n"
 439      << "  case ISD::EntryToken:       // These leaves remain the same.\n"
 440      << "    return Op;\n"
 441      << "  case ISD::AssertSext:\n"
 442      << "  case ISD::AssertZext:\n"
 443      << "    return Select(N->getOperand(0));\n";
 444
 445
 446
 447   OS << "  } // end of big switch.\n\n"
 448      << "  std::cerr << \"Cannot yet select: \";\n"
 449      << "  N->dump();\n"
 450      << "  std::cerr << '\\n';\n"
 451      << "  abort();\n"
 452      << "}\n";
 453 }
 454
 455
 456 void DAGISelEmitter::run(std::ostream &OS) {
 457   EmitSourceFileHeader("DAG Instruction Selector for the " + Target.getName() +
 458                        " target", OS);
 459
 460   ParseAndResolvePatternFragments(OS);
 461   ParseAndResolveInstructions();
 462
 463   // TODO: convert some instructions to expanders if needed or something.
 464
 465   EmitInstructionSelector(OS);
 466
 467   for (std::map<Record*, TreePattern*>::iterator I = PatternFragments.begin(),
 468        E = PatternFragments.end(); I != E; ++I)
 469     delete I->second;
 470   PatternFragments.clear();
 471
 472   for (unsigned i = 0, e = Instructions.size(); i != e; ++i)
 473     delete Instructions[i];
 474   Instructions.clear();
 475 }