1 //===- DAGISelEmitter.cpp - Generate an instruction selector --------------===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
10 // This tablegen backend emits a DAG instruction selector.
12 //===----------------------------------------------------------------------===//
14 #include "DAGISelEmitter.h"
16 #include "llvm/ADT/StringExtras.h"
17 #include "llvm/Support/Debug.h"
22 //===----------------------------------------------------------------------===//
23 // SDTypeConstraint implementation
26 SDTypeConstraint::SDTypeConstraint(Record *R) {
27 OperandNo = R->getValueAsInt("OperandNum");
29 if (R->isSubClassOf("SDTCisVT")) {
30 ConstraintType = SDTCisVT;
31 x.SDTCisVT_Info.VT = getValueType(R->getValueAsDef("VT"));
32 } else if (R->isSubClassOf("SDTCisInt")) {
33 ConstraintType = SDTCisInt;
34 } else if (R->isSubClassOf("SDTCisFP")) {
35 ConstraintType = SDTCisFP;
36 } else if (R->isSubClassOf("SDTCisSameAs")) {
37 ConstraintType = SDTCisSameAs;
38 x.SDTCisSameAs_Info.OtherOperandNum = R->getValueAsInt("OtherOperandNum");
39 } else if (R->isSubClassOf("SDTCisVTSmallerThanOp")) {
40 ConstraintType = SDTCisVTSmallerThanOp;
41 x.SDTCisVTSmallerThanOp_Info.OtherOperandNum =
42 R->getValueAsInt("OtherOperandNum");
44 std::cerr << "Unrecognized SDTypeConstraint '" << R->getName() << "'!\n";
49 /// getOperandNum - Return the node corresponding to operand #OpNo in tree
50 /// N, which has NumResults results.
51 TreePatternNode *SDTypeConstraint::getOperandNum(unsigned OpNo,
53 unsigned NumResults) const {
54 assert(NumResults == 1 && "We only work with single result nodes so far!");
56 if (OpNo < NumResults)
57 return N; // FIXME: need value #
59 return N->getChild(OpNo-NumResults);
62 /// ApplyTypeConstraint - Given a node in a pattern, apply this type
63 /// constraint to the nodes operands. This returns true if it makes a
64 /// change, false otherwise. If a type contradiction is found, throw an
66 bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N,
67 const SDNodeInfo &NodeInfo,
68 TreePattern &TP) const {
69 unsigned NumResults = NodeInfo.getNumResults();
70 assert(NumResults == 1 && "We only work with single result nodes so far!");
72 // Check that the number of operands is sane.
73 if (NodeInfo.getNumOperands() >= 0) {
74 if (N->getNumChildren() != (unsigned)NodeInfo.getNumOperands())
75 TP.error(N->getOperator()->getName() + " node requires exactly " +
76 itostr(NodeInfo.getNumOperands()) + " operands!");
79 TreePatternNode *NodeToApply = getOperandNum(OperandNo, N, NumResults);
81 switch (ConstraintType) {
82 default: assert(0 && "Unknown constraint type!");
84 // Operand must be a particular type.
85 return NodeToApply->UpdateNodeType(x.SDTCisVT_Info.VT, TP);
87 if (NodeToApply->hasTypeSet() && !MVT::isInteger(NodeToApply->getType()))
88 NodeToApply->UpdateNodeType(MVT::i1, TP); // throw an error.
90 // FIXME: can tell from the target if there is only one Int type supported.
93 if (NodeToApply->hasTypeSet() &&
94 !MVT::isFloatingPoint(NodeToApply->getType()))
95 NodeToApply->UpdateNodeType(MVT::f32, TP); // throw an error.
96 // FIXME: can tell from the target if there is only one FP type supported.
99 TreePatternNode *OtherNode =
100 getOperandNum(x.SDTCisSameAs_Info.OtherOperandNum, N, NumResults);
101 return NodeToApply->UpdateNodeType(OtherNode->getType(), TP) |
102 OtherNode->UpdateNodeType(NodeToApply->getType(), TP);
104 case SDTCisVTSmallerThanOp: {
105 // The NodeToApply must be a leaf node that is a VT. OtherOperandNum must
106 // have an integer type that is smaller than the VT.
107 if (!NodeToApply->isLeaf() ||
108 !dynamic_cast<DefInit*>(NodeToApply->getLeafValue()) ||
109 !static_cast<DefInit*>(NodeToApply->getLeafValue())->getDef()
110 ->isSubClassOf("ValueType"))
111 TP.error(N->getOperator()->getName() + " expects a VT operand!");
113 getValueType(static_cast<DefInit*>(NodeToApply->getLeafValue())->getDef());
114 if (!MVT::isInteger(VT))
115 TP.error(N->getOperator()->getName() + " VT operand must be integer!");
117 TreePatternNode *OtherNode =
118 getOperandNum(x.SDTCisVTSmallerThanOp_Info.OtherOperandNum, N,NumResults);
119 if (OtherNode->hasTypeSet() &&
120 (!MVT::isInteger(OtherNode->getType()) ||
121 OtherNode->getType() <= VT))
122 OtherNode->UpdateNodeType(MVT::Other, TP); // Throw an error.
130 //===----------------------------------------------------------------------===//
131 // SDNodeInfo implementation
133 SDNodeInfo::SDNodeInfo(Record *R) : Def(R) {
134 EnumName = R->getValueAsString("Opcode");
135 SDClassName = R->getValueAsString("SDClass");
136 Record *TypeProfile = R->getValueAsDef("TypeProfile");
137 NumResults = TypeProfile->getValueAsInt("NumResults");
138 NumOperands = TypeProfile->getValueAsInt("NumOperands");
140 // Parse the properties.
142 ListInit *LI = R->getValueAsListInit("Properties");
143 for (unsigned i = 0, e = LI->getSize(); i != e; ++i) {
144 DefInit *DI = dynamic_cast<DefInit*>(LI->getElement(i));
145 assert(DI && "Properties list must be list of defs!");
146 if (DI->getDef()->getName() == "SDNPCommutative") {
147 Properties |= 1 << SDNPCommutative;
149 std::cerr << "Unknown SD Node property '" << DI->getDef()->getName()
150 << "' on node '" << R->getName() << "'!\n";
156 // Parse the type constraints.
157 ListInit *Constraints = TypeProfile->getValueAsListInit("Constraints");
158 for (unsigned i = 0, e = Constraints->getSize(); i != e; ++i) {
159 assert(dynamic_cast<DefInit*>(Constraints->getElement(i)) &&
160 "Constraints list should contain constraint definitions!");
162 static_cast<DefInit*>(Constraints->getElement(i))->getDef();
163 TypeConstraints.push_back(Constraint);
167 //===----------------------------------------------------------------------===//
168 // TreePatternNode implementation
171 TreePatternNode::~TreePatternNode() {
172 #if 0 // FIXME: implement refcounted tree nodes!
173 for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
178 /// UpdateNodeType - Set the node type of N to VT if VT contains
179 /// information. If N already contains a conflicting type, then throw an
180 /// exception. This returns true if any information was updated.
182 bool TreePatternNode::UpdateNodeType(MVT::ValueType VT, TreePattern &TP) {
183 if (VT == MVT::LAST_VALUETYPE || getType() == VT) return false;
184 if (getType() == MVT::LAST_VALUETYPE) {
189 TP.error("Type inference contradiction found in node " +
190 getOperator()->getName() + "!");
191 return true; // unreachable
195 void TreePatternNode::print(std::ostream &OS) const {
197 OS << *getLeafValue();
199 OS << "(" << getOperator()->getName();
202 if (getType() == MVT::Other)
204 else if (getType() == MVT::LAST_VALUETYPE)
207 OS << ":" << getType();
210 if (getNumChildren() != 0) {
212 getChild(0)->print(OS);
213 for (unsigned i = 1, e = getNumChildren(); i != e; ++i) {
215 getChild(i)->print(OS);
221 if (!PredicateFn.empty())
222 OS << "<<P:" << PredicateFn << ">>";
224 OS << "<<X:" << TransformFn->getName() << ">>";
225 if (!getName().empty())
226 OS << ":$" << getName();
229 void TreePatternNode::dump() const {
233 /// clone - Make a copy of this tree and all of its children.
235 TreePatternNode *TreePatternNode::clone() const {
236 TreePatternNode *New;
238 New = new TreePatternNode(getLeafValue());
240 std::vector<TreePatternNode*> CChildren;
241 CChildren.reserve(Children.size());
242 for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
243 CChildren.push_back(getChild(i)->clone());
244 New = new TreePatternNode(getOperator(), CChildren);
246 New->setName(getName());
247 New->setType(getType());
248 New->setPredicateFn(getPredicateFn());
249 New->setTransformFn(getTransformFn());
253 /// SubstituteFormalArguments - Replace the formal arguments in this tree
254 /// with actual values specified by ArgMap.
255 void TreePatternNode::
256 SubstituteFormalArguments(std::map<std::string, TreePatternNode*> &ArgMap) {
257 if (isLeaf()) return;
259 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) {
260 TreePatternNode *Child = getChild(i);
261 if (Child->isLeaf()) {
262 Init *Val = Child->getLeafValue();
263 if (dynamic_cast<DefInit*>(Val) &&
264 static_cast<DefInit*>(Val)->getDef()->getName() == "node") {
265 // We found a use of a formal argument, replace it with its value.
266 Child = ArgMap[Child->getName()];
267 assert(Child && "Couldn't find formal argument!");
271 getChild(i)->SubstituteFormalArguments(ArgMap);
277 /// InlinePatternFragments - If this pattern refers to any pattern
278 /// fragments, inline them into place, giving us a pattern without any
279 /// PatFrag references.
280 TreePatternNode *TreePatternNode::InlinePatternFragments(TreePattern &TP) {
281 if (isLeaf()) return this; // nothing to do.
282 Record *Op = getOperator();
284 if (!Op->isSubClassOf("PatFrag")) {
285 // Just recursively inline children nodes.
286 for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
287 setChild(i, getChild(i)->InlinePatternFragments(TP));
291 // Otherwise, we found a reference to a fragment. First, look up its
292 // TreePattern record.
293 TreePattern *Frag = TP.getDAGISelEmitter().getPatternFragment(Op);
295 // Verify that we are passing the right number of operands.
296 if (Frag->getNumArgs() != Children.size())
297 TP.error("'" + Op->getName() + "' fragment requires " +
298 utostr(Frag->getNumArgs()) + " operands!");
300 TreePatternNode *FragTree = Frag->getOnlyTree()->clone();
302 // Resolve formal arguments to their actual value.
303 if (Frag->getNumArgs()) {
304 // Compute the map of formal to actual arguments.
305 std::map<std::string, TreePatternNode*> ArgMap;
306 for (unsigned i = 0, e = Frag->getNumArgs(); i != e; ++i)
307 ArgMap[Frag->getArgName(i)] = getChild(i)->InlinePatternFragments(TP);
309 FragTree->SubstituteFormalArguments(ArgMap);
312 FragTree->setName(getName());
314 // Get a new copy of this fragment to stitch into here.
315 //delete this; // FIXME: implement refcounting!
319 /// ApplyTypeConstraints - Apply all of the type constraints relevent to
320 /// this node and its children in the tree. This returns true if it makes a
321 /// change, false otherwise. If a type contradiction is found, throw an
323 bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP) {
324 if (isLeaf()) return false;
326 // special handling for set, which isn't really an SDNode.
327 if (getOperator()->getName() == "set") {
328 assert (getNumChildren() == 2 && "Only handle 2 operand set's for now!");
329 bool MadeChange = getChild(0)->ApplyTypeConstraints(TP);
330 MadeChange |= getChild(1)->ApplyTypeConstraints(TP);
332 // Types of operands must match.
333 MadeChange |= getChild(0)->UpdateNodeType(getChild(1)->getType(), TP);
334 MadeChange |= getChild(1)->UpdateNodeType(getChild(0)->getType(), TP);
335 MadeChange |= UpdateNodeType(MVT::isVoid, TP);
337 } else if (getOperator()->isSubClassOf("SDNode")) {
338 const SDNodeInfo &NI = TP.getDAGISelEmitter().getSDNodeInfo(getOperator());
340 bool MadeChange = NI.ApplyTypeConstraints(this, TP);
341 for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
342 MadeChange |= getChild(i)->ApplyTypeConstraints(TP);
344 } else if (getOperator()->isSubClassOf("Instruction")) {
345 const DAGInstruction &Inst =
346 TP.getDAGISelEmitter().getInstruction(getOperator());
348 assert(Inst.getNumResults() == 1 && "Only supports one result instrs!");
349 // Apply the result type to the node
350 bool MadeChange = UpdateNodeType(Inst.getResultType(0), TP);
352 if (getNumChildren() != Inst.getNumOperands())
353 TP.error("Instruction '" + getOperator()->getName() + " expects " +
354 utostr(Inst.getNumOperands()) + " operands, not " +
355 utostr(getNumChildren()) + " operands!");
356 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) {
357 MadeChange |= getChild(i)->UpdateNodeType(Inst.getOperandType(i), TP);
358 MadeChange |= getChild(i)->ApplyTypeConstraints(TP);
362 assert(getOperator()->isSubClassOf("SDNodeXForm") && "Unknown node type!");
364 // Node transforms always take one operand, and take and return the same
366 if (getNumChildren() != 1)
367 TP.error("Node transform '" + getOperator()->getName() +
368 "' requires one operand!");
369 bool MadeChange = UpdateNodeType(getChild(0)->getType(), TP);
370 MadeChange |= getChild(0)->UpdateNodeType(getType(), TP);
375 /// canPatternMatch - If it is impossible for this pattern to match on this
376 /// target, fill in Reason and return false. Otherwise, return true. This is
377 /// used as a santity check for .td files (to prevent people from writing stuff
378 /// that can never possibly work), and to prevent the pattern permuter from
379 /// generating stuff that is useless.
380 bool TreePatternNode::canPatternMatch(std::string &Reason, DAGISelEmitter &ISE) {
381 if (isLeaf()) return true;
383 for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
384 if (!getChild(i)->canPatternMatch(Reason, ISE))
387 // If this node is a commutative operator, check that the LHS isn't an
389 const SDNodeInfo &NodeInfo = ISE.getSDNodeInfo(getOperator());
390 if (NodeInfo.hasProperty(SDNodeInfo::SDNPCommutative)) {
391 // Scan all of the operands of the node and make sure that only the last one
392 // is a constant node.
393 for (unsigned i = 0, e = getNumChildren()-1; i != e; ++i)
394 if (!getChild(i)->isLeaf() &&
395 getChild(i)->getOperator()->getName() == "imm") {
396 Reason = "Immediate value must be on the RHS of commutative operators!";
404 //===----------------------------------------------------------------------===//
405 // TreePattern implementation
408 TreePattern::TreePattern(Record *TheRec, ListInit *RawPat,
409 DAGISelEmitter &ise) : TheRecord(TheRec), ISE(ise) {
410 for (unsigned i = 0, e = RawPat->getSize(); i != e; ++i)
411 Trees.push_back(ParseTreePattern((DagInit*)RawPat->getElement(i)));
414 TreePattern::TreePattern(Record *TheRec, DagInit *Pat,
415 DAGISelEmitter &ise) : TheRecord(TheRec), ISE(ise) {
416 Trees.push_back(ParseTreePattern(Pat));
419 TreePattern::TreePattern(Record *TheRec, TreePatternNode *Pat,
420 DAGISelEmitter &ise) : TheRecord(TheRec), ISE(ise) {
421 Trees.push_back(Pat);
426 void TreePattern::error(const std::string &Msg) const {
428 throw "In " + TheRecord->getName() + ": " + Msg;
431 /// getIntrinsicType - Check to see if the specified record has an intrinsic
432 /// type which should be applied to it. This infer the type of register
433 /// references from the register file information, for example.
435 MVT::ValueType TreePattern::getIntrinsicType(Record *R) const {
436 // Check to see if this is a register or a register class...
437 if (R->isSubClassOf("RegisterClass"))
438 return getValueType(R->getValueAsDef("RegType"));
439 else if (R->isSubClassOf("PatFrag")) {
440 // Pattern fragment types will be resolved when they are inlined.
441 return MVT::LAST_VALUETYPE;
442 } else if (R->isSubClassOf("Register")) {
443 assert(0 && "Explicit registers not handled here yet!\n");
444 return MVT::LAST_VALUETYPE;
445 } else if (R->isSubClassOf("ValueType")) {
448 } else if (R->getName() == "node") {
450 return MVT::LAST_VALUETYPE;
453 error("Unknown node flavor used in pattern: " + R->getName());
457 TreePatternNode *TreePattern::ParseTreePattern(DagInit *Dag) {
458 Record *Operator = Dag->getNodeType();
460 if (Operator->isSubClassOf("ValueType")) {
461 // If the operator is a ValueType, then this must be "type cast" of a leaf
463 if (Dag->getNumArgs() != 1)
464 error("Type cast only valid for a leaf node!");
466 Init *Arg = Dag->getArg(0);
467 TreePatternNode *New;
468 if (DefInit *DI = dynamic_cast<DefInit*>(Arg)) {
469 Record *R = DI->getDef();
470 if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrag")) {
471 Dag->setArg(0, new DagInit(R,
472 std::vector<std::pair<Init*, std::string> >()));
473 TreePatternNode *TPN = ParseTreePattern(Dag);
474 TPN->setName(Dag->getArgName(0));
478 New = new TreePatternNode(DI);
479 // If it's a regclass or something else known, set the type.
480 New->setType(getIntrinsicType(DI->getDef()));
481 } else if (DagInit *DI = dynamic_cast<DagInit*>(Arg)) {
482 New = ParseTreePattern(DI);
485 error("Unknown leaf value for tree pattern!");
489 // Apply the type cast.
490 New->UpdateNodeType(getValueType(Operator), *this);
494 // Verify that this is something that makes sense for an operator.
495 if (!Operator->isSubClassOf("PatFrag") && !Operator->isSubClassOf("SDNode") &&
496 !Operator->isSubClassOf("Instruction") &&
497 !Operator->isSubClassOf("SDNodeXForm") &&
498 Operator->getName() != "set")
499 error("Unrecognized node '" + Operator->getName() + "'!");
501 std::vector<TreePatternNode*> Children;
503 for (unsigned i = 0, e = Dag->getNumArgs(); i != e; ++i) {
504 Init *Arg = Dag->getArg(i);
505 if (DagInit *DI = dynamic_cast<DagInit*>(Arg)) {
506 Children.push_back(ParseTreePattern(DI));
507 Children.back()->setName(Dag->getArgName(i));
508 } else if (DefInit *DefI = dynamic_cast<DefInit*>(Arg)) {
509 Record *R = DefI->getDef();
510 // Direct reference to a leaf DagNode or PatFrag? Turn it into a
511 // TreePatternNode if its own.
512 if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrag")) {
513 Dag->setArg(i, new DagInit(R,
514 std::vector<std::pair<Init*, std::string> >()));
515 --i; // Revisit this node...
517 TreePatternNode *Node = new TreePatternNode(DefI);
518 Node->setName(Dag->getArgName(i));
519 Children.push_back(Node);
521 // If it's a regclass or something else known, set the type.
522 Node->setType(getIntrinsicType(R));
525 if (R->getName() == "node") {
526 if (Dag->getArgName(i).empty())
527 error("'node' argument requires a name to match with operand list");
528 Args.push_back(Dag->getArgName(i));
533 error("Unknown leaf value for tree pattern!");
537 return new TreePatternNode(Operator, Children);
540 /// InferAllTypes - Infer/propagate as many types throughout the expression
541 /// patterns as possible. Return true if all types are infered, false
542 /// otherwise. Throw an exception if a type contradiction is found.
543 bool TreePattern::InferAllTypes() {
544 bool MadeChange = true;
547 for (unsigned i = 0, e = Trees.size(); i != e; ++i)
548 MadeChange |= Trees[i]->ApplyTypeConstraints(*this);
551 bool HasUnresolvedTypes = false;
552 for (unsigned i = 0, e = Trees.size(); i != e; ++i)
553 HasUnresolvedTypes |= Trees[i]->ContainsUnresolvedType();
554 return !HasUnresolvedTypes;
557 void TreePattern::print(std::ostream &OS) const {
558 OS << getRecord()->getName();
560 OS << "(" << Args[0];
561 for (unsigned i = 1, e = Args.size(); i != e; ++i)
562 OS << ", " << Args[i];
567 if (Trees.size() > 1)
569 for (unsigned i = 0, e = Trees.size(); i != e; ++i) {
575 if (Trees.size() > 1)
579 void TreePattern::dump() const { print(std::cerr); }
583 //===----------------------------------------------------------------------===//
584 // DAGISelEmitter implementation
587 // Parse all of the SDNode definitions for the target, populating SDNodes.
588 void DAGISelEmitter::ParseNodeInfo() {
589 std::vector<Record*> Nodes = Records.getAllDerivedDefinitions("SDNode");
590 while (!Nodes.empty()) {
591 SDNodes.insert(std::make_pair(Nodes.back(), Nodes.back()));
596 /// ParseNodeTransforms - Parse all SDNodeXForm instances into the SDNodeXForms
597 /// map, and emit them to the file as functions.
598 void DAGISelEmitter::ParseNodeTransforms(std::ostream &OS) {
599 OS << "\n// Node transformations.\n";
600 std::vector<Record*> Xforms = Records.getAllDerivedDefinitions("SDNodeXForm");
601 while (!Xforms.empty()) {
602 Record *XFormNode = Xforms.back();
603 Record *SDNode = XFormNode->getValueAsDef("Opcode");
604 std::string Code = XFormNode->getValueAsCode("XFormFunction");
605 SDNodeXForms.insert(std::make_pair(XFormNode,
606 std::make_pair(SDNode, Code)));
609 std::string ClassName = getSDNodeInfo(SDNode).getSDClassName();
610 const char *C2 = ClassName == "SDNode" ? "N" : "inN";
612 OS << "inline SDOperand Transform_" << XFormNode->getName()
613 << "(SDNode *" << C2 << ") {\n";
614 if (ClassName != "SDNode")
615 OS << " " << ClassName << " *N = cast<" << ClassName << ">(inN);\n";
616 OS << Code << "\n}\n";
625 /// ParsePatternFragments - Parse all of the PatFrag definitions in the .td
626 /// file, building up the PatternFragments map. After we've collected them all,
627 /// inline fragments together as necessary, so that there are no references left
628 /// inside a pattern fragment to a pattern fragment.
630 /// This also emits all of the predicate functions to the output file.
632 void DAGISelEmitter::ParsePatternFragments(std::ostream &OS) {
633 std::vector<Record*> Fragments = Records.getAllDerivedDefinitions("PatFrag");
635 // First step, parse all of the fragments and emit predicate functions.
636 OS << "\n// Predicate functions.\n";
637 for (unsigned i = 0, e = Fragments.size(); i != e; ++i) {
638 DagInit *Tree = Fragments[i]->getValueAsDag("Fragment");
639 TreePattern *P = new TreePattern(Fragments[i], Tree, *this);
640 PatternFragments[Fragments[i]] = P;
642 // Validate the argument list, converting it to map, to discard duplicates.
643 std::vector<std::string> &Args = P->getArgList();
644 std::set<std::string> OperandsMap(Args.begin(), Args.end());
646 if (OperandsMap.count(""))
647 P->error("Cannot have unnamed 'node' values in pattern fragment!");
649 // Parse the operands list.
650 DagInit *OpsList = Fragments[i]->getValueAsDag("Operands");
651 if (OpsList->getNodeType()->getName() != "ops")
652 P->error("Operands list should start with '(ops ... '!");
654 // Copy over the arguments.
656 for (unsigned j = 0, e = OpsList->getNumArgs(); j != e; ++j) {
657 if (!dynamic_cast<DefInit*>(OpsList->getArg(j)) ||
658 static_cast<DefInit*>(OpsList->getArg(j))->
659 getDef()->getName() != "node")
660 P->error("Operands list should all be 'node' values.");
661 if (OpsList->getArgName(j).empty())
662 P->error("Operands list should have names for each operand!");
663 if (!OperandsMap.count(OpsList->getArgName(j)))
664 P->error("'" + OpsList->getArgName(j) +
665 "' does not occur in pattern or was multiply specified!");
666 OperandsMap.erase(OpsList->getArgName(j));
667 Args.push_back(OpsList->getArgName(j));
670 if (!OperandsMap.empty())
671 P->error("Operands list does not contain an entry for operand '" +
672 *OperandsMap.begin() + "'!");
674 // If there is a code init for this fragment, emit the predicate code and
675 // keep track of the fact that this fragment uses it.
676 std::string Code = Fragments[i]->getValueAsCode("Predicate");
678 assert(!P->getOnlyTree()->isLeaf() && "Can't be a leaf!");
679 std::string ClassName =
680 getSDNodeInfo(P->getOnlyTree()->getOperator()).getSDClassName();
681 const char *C2 = ClassName == "SDNode" ? "N" : "inN";
683 OS << "inline bool Predicate_" << Fragments[i]->getName()
684 << "(SDNode *" << C2 << ") {\n";
685 if (ClassName != "SDNode")
686 OS << " " << ClassName << " *N = cast<" << ClassName << ">(inN);\n";
687 OS << Code << "\n}\n";
688 P->getOnlyTree()->setPredicateFn("Predicate_"+Fragments[i]->getName());
691 // If there is a node transformation corresponding to this, keep track of
693 Record *Transform = Fragments[i]->getValueAsDef("OperandTransform");
694 if (!getSDNodeTransform(Transform).second.empty()) // not noop xform?
695 P->getOnlyTree()->setTransformFn(Transform);
700 // Now that we've parsed all of the tree fragments, do a closure on them so
701 // that there are not references to PatFrags left inside of them.
702 for (std::map<Record*, TreePattern*>::iterator I = PatternFragments.begin(),
703 E = PatternFragments.end(); I != E; ++I) {
704 TreePattern *ThePat = I->second;
705 ThePat->InlinePatternFragments();
707 // Infer as many types as possible. Don't worry about it if we don't infer
708 // all of them, some may depend on the inputs of the pattern.
710 ThePat->InferAllTypes();
712 // If this pattern fragment is not supported by this target (no types can
713 // satisfy its constraints), just ignore it. If the bogus pattern is
714 // actually used by instructions, the type consistency error will be
718 // If debugging, print out the pattern fragment result.
719 DEBUG(ThePat->dump());
723 /// HandleUse - Given "Pat" a leaf in the pattern, check to see if it is an
724 /// instruction input. Return true if this is a real use.
725 static bool HandleUse(TreePattern *I, TreePatternNode *Pat,
726 std::map<std::string, TreePatternNode*> &InstInputs) {
727 // No name -> not interesting.
728 if (Pat->getName().empty()) {
730 DefInit *DI = dynamic_cast<DefInit*>(Pat->getLeafValue());
731 if (DI && DI->getDef()->isSubClassOf("RegisterClass"))
732 I->error("Input " + DI->getDef()->getName() + " must be named!");
740 DefInit *DI = dynamic_cast<DefInit*>(Pat->getLeafValue());
741 if (!DI) I->error("Input $" + Pat->getName() + " must be an identifier!");
744 assert(Pat->getNumChildren() == 0 && "can't be a use with children!");
745 Rec = Pat->getOperator();
748 TreePatternNode *&Slot = InstInputs[Pat->getName()];
753 if (Slot->isLeaf()) {
754 SlotRec = dynamic_cast<DefInit*>(Slot->getLeafValue())->getDef();
756 assert(Slot->getNumChildren() == 0 && "can't be a use with children!");
757 SlotRec = Slot->getOperator();
760 // Ensure that the inputs agree if we've already seen this input.
762 I->error("All $" + Pat->getName() + " inputs must agree with each other");
763 if (Slot->getType() != Pat->getType())
764 I->error("All $" + Pat->getName() + " inputs must agree with each other");
769 /// FindPatternInputsAndOutputs - Scan the specified TreePatternNode (which is
770 /// part of "I", the instruction), computing the set of inputs and outputs of
771 /// the pattern. Report errors if we see anything naughty.
772 void DAGISelEmitter::
773 FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat,
774 std::map<std::string, TreePatternNode*> &InstInputs,
775 std::map<std::string, Record*> &InstResults) {
777 bool isUse = HandleUse(I, Pat, InstInputs);
778 if (!isUse && Pat->getTransformFn())
779 I->error("Cannot specify a transform function for a non-input value!");
781 } else if (Pat->getOperator()->getName() != "set") {
782 // If this is not a set, verify that the children nodes are not void typed,
784 for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) {
785 if (Pat->getChild(i)->getType() == MVT::isVoid)
786 I->error("Cannot have void nodes inside of patterns!");
787 FindPatternInputsAndOutputs(I, Pat->getChild(i), InstInputs, InstResults);
790 // If this is a non-leaf node with no children, treat it basically as if
791 // it were a leaf. This handles nodes like (imm).
793 if (Pat->getNumChildren() == 0)
794 isUse = HandleUse(I, Pat, InstInputs);
796 if (!isUse && Pat->getTransformFn())
797 I->error("Cannot specify a transform function for a non-input value!");
801 // Otherwise, this is a set, validate and collect instruction results.
802 if (Pat->getNumChildren() == 0)
803 I->error("set requires operands!");
804 else if (Pat->getNumChildren() & 1)
805 I->error("set requires an even number of operands");
807 if (Pat->getTransformFn())
808 I->error("Cannot specify a transform function on a set node!");
810 // Check the set destinations.
811 unsigned NumValues = Pat->getNumChildren()/2;
812 for (unsigned i = 0; i != NumValues; ++i) {
813 TreePatternNode *Dest = Pat->getChild(i);
815 I->error("set destination should be a virtual register!");
817 DefInit *Val = dynamic_cast<DefInit*>(Dest->getLeafValue());
819 I->error("set destination should be a virtual register!");
821 if (!Val->getDef()->isSubClassOf("RegisterClass"))
822 I->error("set destination should be a virtual register!");
823 if (Dest->getName().empty())
824 I->error("set destination must have a name!");
825 if (InstResults.count(Dest->getName()))
826 I->error("cannot set '" + Dest->getName() +"' multiple times");
827 InstResults[Dest->getName()] = Val->getDef();
829 // Verify and collect info from the computation.
830 FindPatternInputsAndOutputs(I, Pat->getChild(i+NumValues),
831 InstInputs, InstResults);
836 /// ParseInstructions - Parse all of the instructions, inlining and resolving
837 /// any fragments involved. This populates the Instructions list with fully
838 /// resolved instructions.
839 void DAGISelEmitter::ParseInstructions() {
840 std::vector<Record*> Instrs = Records.getAllDerivedDefinitions("Instruction");
842 for (unsigned i = 0, e = Instrs.size(); i != e; ++i) {
843 if (!dynamic_cast<ListInit*>(Instrs[i]->getValueInit("Pattern")))
844 continue; // no pattern yet, ignore it.
846 ListInit *LI = Instrs[i]->getValueAsListInit("Pattern");
847 if (LI->getSize() == 0) continue; // no pattern.
849 // Parse the instruction.
850 TreePattern *I = new TreePattern(Instrs[i], LI, *this);
851 // Inline pattern fragments into it.
852 I->InlinePatternFragments();
854 // Infer as many types as possible. If we cannot infer all of them, we can
855 // never do anything with this instruction pattern: report it to the user.
856 if (!I->InferAllTypes())
857 I->error("Could not infer all types in pattern!");
859 // InstInputs - Keep track of all of the inputs of the instruction, along
860 // with the record they are declared as.
861 std::map<std::string, TreePatternNode*> InstInputs;
863 // InstResults - Keep track of all the virtual registers that are 'set'
864 // in the instruction, including what reg class they are.
865 std::map<std::string, Record*> InstResults;
867 // Verify that the top-level forms in the instruction are of void type, and
868 // fill in the InstResults map.
869 for (unsigned j = 0, e = I->getNumTrees(); j != e; ++j) {
870 TreePatternNode *Pat = I->getTree(j);
871 if (Pat->getType() != MVT::isVoid) {
873 I->error("Top-level forms in instruction pattern should have"
877 // Find inputs and outputs, and verify the structure of the uses/defs.
878 FindPatternInputsAndOutputs(I, Pat, InstInputs, InstResults);
881 // Now that we have inputs and outputs of the pattern, inspect the operands
882 // list for the instruction. This determines the order that operands are
883 // added to the machine instruction the node corresponds to.
884 unsigned NumResults = InstResults.size();
886 // Parse the operands list from the (ops) list, validating it.
887 std::vector<std::string> &Args = I->getArgList();
888 assert(Args.empty() && "Args list should still be empty here!");
889 CodeGenInstruction &CGI = Target.getInstruction(Instrs[i]->getName());
891 // Check that all of the results occur first in the list.
892 std::vector<MVT::ValueType> ResultTypes;
893 for (unsigned i = 0; i != NumResults; ++i) {
894 if (i == CGI.OperandList.size())
895 I->error("'" + InstResults.begin()->first +
896 "' set but does not appear in operand list!");
897 const std::string &OpName = CGI.OperandList[i].Name;
899 // Check that it exists in InstResults.
900 Record *R = InstResults[OpName];
902 I->error("Operand $" + OpName + " should be a set destination: all "
903 "outputs must occur before inputs in operand list!");
905 if (CGI.OperandList[i].Rec != R)
906 I->error("Operand $" + OpName + " class mismatch!");
908 // Remember the return type.
909 ResultTypes.push_back(CGI.OperandList[i].Ty);
911 // Okay, this one checks out.
912 InstResults.erase(OpName);
915 // Loop over the inputs next. Make a copy of InstInputs so we can destroy
916 // the copy while we're checking the inputs.
917 std::map<std::string, TreePatternNode*> InstInputsCheck(InstInputs);
919 std::vector<TreePatternNode*> ResultNodeOperands;
920 std::vector<MVT::ValueType> OperandTypes;
921 for (unsigned i = NumResults, e = CGI.OperandList.size(); i != e; ++i) {
922 const std::string &OpName = CGI.OperandList[i].Name;
924 I->error("Operand #" + utostr(i) + " in operands list has no name!");
926 if (!InstInputsCheck.count(OpName))
927 I->error("Operand $" + OpName +
928 " does not appear in the instruction pattern");
929 TreePatternNode *InVal = InstInputsCheck[OpName];
930 InstInputsCheck.erase(OpName); // It occurred, remove from map.
931 if (CGI.OperandList[i].Ty != InVal->getType())
932 I->error("Operand $" + OpName +
933 "'s type disagrees between the operand and pattern");
934 OperandTypes.push_back(InVal->getType());
936 // Construct the result for the dest-pattern operand list.
937 TreePatternNode *OpNode = InVal->clone();
939 // No predicate is useful on the result.
940 OpNode->setPredicateFn("");
942 // Promote the xform function to be an explicit node if set.
943 if (Record *Xform = OpNode->getTransformFn()) {
944 OpNode->setTransformFn(0);
945 std::vector<TreePatternNode*> Children;
946 Children.push_back(OpNode);
947 OpNode = new TreePatternNode(Xform, Children);
950 ResultNodeOperands.push_back(OpNode);
953 if (!InstInputsCheck.empty())
954 I->error("Input operand $" + InstInputsCheck.begin()->first +
955 " occurs in pattern but not in operands list!");
957 TreePatternNode *ResultPattern =
958 new TreePatternNode(I->getRecord(), ResultNodeOperands);
960 // Create and insert the instruction.
961 DAGInstruction TheInst(I, ResultTypes, OperandTypes);
962 Instructions.insert(std::make_pair(I->getRecord(), TheInst));
964 // Use a temporary tree pattern to infer all types and make sure that the
965 // constructed result is correct. This depends on the instruction already
966 // being inserted into the Instructions map.
967 TreePattern Temp(I->getRecord(), ResultPattern, *this);
968 Temp.InferAllTypes();
970 DAGInstruction &TheInsertedInst = Instructions.find(I->getRecord())->second;
971 TheInsertedInst.setResultPattern(Temp.getOnlyTree());
976 // If we can, convert the instructions to be patterns that are matched!
977 for (std::map<Record*, DAGInstruction>::iterator II = Instructions.begin(),
978 E = Instructions.end(); II != E; ++II) {
979 TreePattern *I = II->second.getPattern();
981 if (I->getNumTrees() != 1) {
982 std::cerr << "CANNOT HANDLE: " << I->getRecord()->getName() << " yet!";
985 TreePatternNode *Pattern = I->getTree(0);
986 if (Pattern->getOperator()->getName() != "set")
987 continue; // Not a set (store or something?)
989 if (Pattern->getNumChildren() != 2)
990 continue; // Not a set of a single value (not handled so far)
992 TreePatternNode *SrcPattern = Pattern->getChild(1)->clone();
995 if (!SrcPattern->canPatternMatch(Reason, *this))
996 I->error("Instruction can never match: " + Reason);
998 TreePatternNode *DstPattern = II->second.getResultPattern();
999 PatternsToMatch.push_back(std::make_pair(SrcPattern, DstPattern));
1003 void DAGISelEmitter::ParsePatterns() {
1004 std::vector<Record*> Patterns = Records.getAllDerivedDefinitions("Pattern");
1006 for (unsigned i = 0, e = Patterns.size(); i != e; ++i) {
1007 DagInit *Tree = Patterns[i]->getValueAsDag("PatternToMatch");
1008 TreePattern *Pattern = new TreePattern(Patterns[i], Tree, *this);
1010 // Inline pattern fragments into it.
1011 Pattern->InlinePatternFragments();
1013 // Infer as many types as possible. If we cannot infer all of them, we can
1014 // never do anything with this pattern: report it to the user.
1015 if (!Pattern->InferAllTypes())
1016 Pattern->error("Could not infer all types in pattern!");
1018 ListInit *LI = Patterns[i]->getValueAsListInit("ResultInstrs");
1019 if (LI->getSize() == 0) continue; // no pattern.
1021 // Parse the instruction.
1022 TreePattern *Result = new TreePattern(Patterns[i], LI, *this);
1024 // Inline pattern fragments into it.
1025 Result->InlinePatternFragments();
1027 // Infer as many types as possible. If we cannot infer all of them, we can
1028 // never do anything with this pattern: report it to the user.
1029 if (!Result->InferAllTypes())
1030 Result->error("Could not infer all types in pattern result!");
1032 if (Result->getNumTrees() != 1)
1033 Result->error("Cannot handle instructions producing instructions "
1034 "with temporaries yet!");
1037 if (!Pattern->getOnlyTree()->canPatternMatch(Reason, *this))
1038 Pattern->error("Pattern can never match: " + Reason);
1040 PatternsToMatch.push_back(std::make_pair(Pattern->getOnlyTree(),
1041 Result->getOnlyTree()));
1044 DEBUG(std::cerr << "\n\nPARSED PATTERNS TO MATCH:\n\n";
1045 for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i) {
1046 std::cerr << "PATTERN: "; PatternsToMatch[i].first->dump();
1047 std::cerr << "\nRESULT: ";PatternsToMatch[i].second->dump();
1052 // GenerateVariants - Generate variants. For example, commutative patterns can
1053 // match multiple ways. Add them to PatternsToMatch as well.
1054 void DAGISelEmitter::GenerateVariants() {
1058 /// getPatternSize - Return the 'size' of this pattern. We want to match large
1059 /// patterns before small ones. This is used to determine the size of a
1061 static unsigned getPatternSize(TreePatternNode *P) {
1062 assert(MVT::isInteger(P->getType()) || MVT::isFloatingPoint(P->getType()) &&
1063 "Not a valid pattern node to size!");
1064 unsigned Size = 1; // The node itself.
1066 // Count children in the count if they are also nodes.
1067 for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) {
1068 TreePatternNode *Child = P->getChild(i);
1069 if (!Child->isLeaf() && Child->getType() != MVT::Other)
1070 Size += getPatternSize(Child);
1076 /// getResultPatternCost - Compute the number of instructions for this pattern.
1077 /// This is a temporary hack. We should really include the instruction
1078 /// latencies in this calculation.
1079 static unsigned getResultPatternCost(TreePatternNode *P) {
1080 if (P->isLeaf()) return 0;
1082 unsigned Cost = P->getOperator()->isSubClassOf("Instruction");
1083 for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i)
1084 Cost += getResultPatternCost(P->getChild(i));
1088 // PatternSortingPredicate - return true if we prefer to match LHS before RHS.
1089 // In particular, we want to match maximal patterns first and lowest cost within
1090 // a particular complexity first.
1091 struct PatternSortingPredicate {
1092 bool operator()(DAGISelEmitter::PatternToMatch *LHS,
1093 DAGISelEmitter::PatternToMatch *RHS) {
1094 unsigned LHSSize = getPatternSize(LHS->first);
1095 unsigned RHSSize = getPatternSize(RHS->first);
1096 if (LHSSize > RHSSize) return true; // LHS -> bigger -> less cost
1097 if (LHSSize < RHSSize) return false;
1099 // If the patterns have equal complexity, compare generated instruction cost
1100 return getResultPatternCost(LHS->second) <getResultPatternCost(RHS->second);
1104 /// EmitMatchForPattern - Emit a matcher for N, going to the label for PatternNo
1105 /// if the match fails. At this point, we already know that the opcode for N
1106 /// matches, and the SDNode for the result has the RootName specified name.
1107 void DAGISelEmitter::EmitMatchForPattern(TreePatternNode *N,
1108 const std::string &RootName,
1109 std::map<std::string,std::string> &VarMap,
1110 unsigned PatternNo, std::ostream &OS) {
1111 assert(!N->isLeaf() && "Cannot match against a leaf!");
1113 // If this node has a name associated with it, capture it in VarMap. If
1114 // we already saw this in the pattern, emit code to verify dagness.
1115 if (!N->getName().empty()) {
1116 std::string &VarMapEntry = VarMap[N->getName()];
1117 if (VarMapEntry.empty()) {
1118 VarMapEntry = RootName;
1120 // If we get here, this is a second reference to a specific name. Since
1121 // we already have checked that the first reference is valid, we don't
1122 // have to recursively match it, just check that it's the same as the
1123 // previously named thing.
1124 OS << " if (" << VarMapEntry << " != " << RootName
1125 << ") goto P" << PatternNo << "Fail;\n";
1130 // Emit code to load the child nodes and match their contents recursively.
1131 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) {
1132 OS << " SDOperand " << RootName << i <<" = " << RootName
1133 << ".getOperand(" << i << ");\n";
1134 TreePatternNode *Child = N->getChild(i);
1136 if (!Child->isLeaf()) {
1137 // If it's not a leaf, recursively match.
1138 const SDNodeInfo &CInfo = getSDNodeInfo(Child->getOperator());
1139 OS << " if (" << RootName << i << ".getOpcode() != "
1140 << CInfo.getEnumName() << ") goto P" << PatternNo << "Fail;\n";
1141 EmitMatchForPattern(Child, RootName + utostr(i), VarMap, PatternNo, OS);
1143 // If this child has a name associated with it, capture it in VarMap. If
1144 // we already saw this in the pattern, emit code to verify dagness.
1145 if (!Child->getName().empty()) {
1146 std::string &VarMapEntry = VarMap[Child->getName()];
1147 if (VarMapEntry.empty()) {
1148 VarMapEntry = RootName + utostr(i);
1150 // If we get here, this is a second reference to a specific name. Since
1151 // we already have checked that the first reference is valid, we don't
1152 // have to recursively match it, just check that it's the same as the
1153 // previously named thing.
1154 OS << " if (" << VarMapEntry << " != " << RootName << i
1155 << ") goto P" << PatternNo << "Fail;\n";
1160 // Handle leaves of various types.
1161 Init *LeafVal = Child->getLeafValue();
1162 Record *LeafRec = dynamic_cast<DefInit*>(LeafVal)->getDef();
1163 if (LeafRec->isSubClassOf("RegisterClass")) {
1164 // Handle register references. Nothing to do here.
1165 } else if (LeafRec->isSubClassOf("ValueType")) {
1166 // Make sure this is the specified value type.
1167 OS << " if (cast<VTSDNode>(" << RootName << i << ")->getVT() != "
1168 << "MVT::" << LeafRec->getName() << ") goto P" << PatternNo
1172 assert(0 && "Unknown leaf type!");
1177 // If there is a node predicate for this, emit the call.
1178 if (!N->getPredicateFn().empty())
1179 OS << " if (!" << N->getPredicateFn() << "(" << RootName
1180 << ".Val)) goto P" << PatternNo << "Fail;\n";
1183 /// CodeGenPatternResult - Emit the action for a pattern. Now that it has
1184 /// matched, we actually have to build a DAG!
1185 unsigned DAGISelEmitter::
1186 CodeGenPatternResult(TreePatternNode *N, unsigned &Ctr,
1187 std::map<std::string,std::string> &VariableMap,
1189 // This is something selected from the pattern we matched.
1190 if (!N->getName().empty()) {
1191 std::string &Val = VariableMap[N->getName()];
1192 assert(!Val.empty() &&
1193 "Variable referenced but not defined and not caught earlier!");
1194 if (Val[0] == 'T' && Val[1] == 'm' && Val[2] == 'p') {
1195 // Already selected this operand, just return the tmpval.
1196 return atoi(Val.c_str()+3);
1199 unsigned ResNo = Ctr++;
1200 if (!N->isLeaf() && N->getOperator()->getName() == "imm") {
1201 switch (N->getType()) {
1202 default: assert(0 && "Unknown type for constant node!");
1203 case MVT::i1: OS << " bool Tmp"; break;
1204 case MVT::i8: OS << " unsigned char Tmp"; break;
1205 case MVT::i16: OS << " unsigned short Tmp"; break;
1206 case MVT::i32: OS << " unsigned Tmp"; break;
1207 case MVT::i64: OS << " uint64_t Tmp"; break;
1209 OS << ResNo << "C = cast<ConstantSDNode>(" << Val << ")->getValue();\n";
1210 OS << " SDOperand Tmp" << ResNo << " = CurDAG->getTargetConstant(Tmp"
1211 << ResNo << "C, MVT::" << getEnumName(N->getType()) << ");\n";
1213 OS << " SDOperand Tmp" << ResNo << " = Select(" << Val << ");\n";
1215 // Add Tmp<ResNo> to VariableMap, so that we don't multiply select this
1216 // value if used multiple times by this pattern result.
1217 Val = "Tmp"+utostr(ResNo);
1223 assert(0 && "Unknown leaf type!");
1227 Record *Op = N->getOperator();
1228 if (Op->isSubClassOf("Instruction")) {
1229 // Emit all of the operands.
1230 std::vector<unsigned> Ops;
1231 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i)
1232 Ops.push_back(CodeGenPatternResult(N->getChild(i), Ctr, VariableMap, OS));
1234 CodeGenInstruction &II = Target.getInstruction(Op->getName());
1235 unsigned ResNo = Ctr++;
1237 OS << " SDOperand Tmp" << ResNo << " = CurDAG->getTargetNode("
1238 << II.Namespace << "::" << II.TheDef->getName() << ", MVT::"
1239 << getEnumName(N->getType());
1240 for (unsigned i = 0, e = Ops.size(); i != e; ++i)
1241 OS << ", Tmp" << Ops[i];
1244 } else if (Op->isSubClassOf("SDNodeXForm")) {
1245 assert(N->getNumChildren() == 1 && "node xform should have one child!");
1246 unsigned OpVal = CodeGenPatternResult(N->getChild(0), Ctr, VariableMap, OS);
1248 unsigned ResNo = Ctr++;
1249 OS << " SDOperand Tmp" << ResNo << " = Transform_" << Op->getName()
1250 << "(Tmp" << OpVal << ".Val);\n";
1254 assert(0 && "Unknown node in result pattern!");
1260 /// EmitCodeForPattern - Given a pattern to match, emit code to the specified
1261 /// stream to match the pattern, and generate the code for the match if it
1263 void DAGISelEmitter::EmitCodeForPattern(PatternToMatch &Pattern,
1265 static unsigned PatternCount = 0;
1266 unsigned PatternNo = PatternCount++;
1267 OS << " { // Pattern #" << PatternNo << ": ";
1268 Pattern.first->print(OS);
1269 OS << "\n // Emits: ";
1270 Pattern.second->print(OS);
1272 OS << " // Pattern complexity = " << getPatternSize(Pattern.first)
1273 << " cost = " << getResultPatternCost(Pattern.second) << "\n";
1275 // Emit the matcher, capturing named arguments in VariableMap.
1276 std::map<std::string,std::string> VariableMap;
1277 EmitMatchForPattern(Pattern.first, "N", VariableMap, PatternNo, OS);
1280 unsigned Res = CodeGenPatternResult(Pattern.second, TmpNo, VariableMap, OS);
1282 // Add the result to the map if it has multiple uses.
1283 OS << " if (!N.Val->hasOneUse()) CodeGenMap[N] = Tmp" << Res << ";\n";
1284 OS << " return Tmp" << Res << ";\n";
1285 OS << " }\n P" << PatternNo << "Fail:\n";
1290 /// CompareByRecordName - An ordering predicate that implements less-than by
1291 /// comparing the names records.
1292 struct CompareByRecordName {
1293 bool operator()(const Record *LHS, const Record *RHS) const {
1294 // Sort by name first.
1295 if (LHS->getName() < RHS->getName()) return true;
1296 // If both names are equal, sort by pointer.
1297 return LHS->getName() == RHS->getName() && LHS < RHS;
1302 void DAGISelEmitter::EmitInstructionSelector(std::ostream &OS) {
1303 // Emit boilerplate.
1304 OS << "// The main instruction selector code.\n"
1305 << "SDOperand SelectCode(SDOperand N) {\n"
1306 << " if (N.getOpcode() >= ISD::BUILTIN_OP_END &&\n"
1307 << " N.getOpcode() < PPCISD::FIRST_NUMBER)\n"
1308 << " return N; // Already selected.\n\n"
1309 << " if (!N.Val->hasOneUse()) {\n"
1310 << " std::map<SDOperand, SDOperand>::iterator CGMI = CodeGenMap.find(N);\n"
1311 << " if (CGMI != CodeGenMap.end()) return CGMI->second;\n"
1313 << " switch (N.getOpcode()) {\n"
1314 << " default: break;\n"
1315 << " case ISD::EntryToken: // These leaves remain the same.\n"
1317 << " case ISD::AssertSext:\n"
1318 << " case ISD::AssertZext: {\n"
1319 << " SDOperand Tmp0 = Select(N.getOperand(0));\n"
1320 << " if (!N.Val->hasOneUse()) CodeGenMap[N] = Tmp0;\n"
1321 << " return Tmp0;\n"
1324 // Group the patterns by their top-level opcodes.
1325 std::map<Record*, std::vector<PatternToMatch*>,
1326 CompareByRecordName> PatternsByOpcode;
1327 for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i)
1328 PatternsByOpcode[PatternsToMatch[i].first->getOperator()]
1329 .push_back(&PatternsToMatch[i]);
1331 // Loop over all of the case statements.
1332 for (std::map<Record*, std::vector<PatternToMatch*>,
1333 CompareByRecordName>::iterator PBOI = PatternsByOpcode.begin(),
1334 E = PatternsByOpcode.end(); PBOI != E; ++PBOI) {
1335 const SDNodeInfo &OpcodeInfo = getSDNodeInfo(PBOI->first);
1336 std::vector<PatternToMatch*> &Patterns = PBOI->second;
1338 OS << " case " << OpcodeInfo.getEnumName() << ":\n";
1340 // We want to emit all of the matching code now. However, we want to emit
1341 // the matches in order of minimal cost. Sort the patterns so the least
1342 // cost one is at the start.
1343 std::stable_sort(Patterns.begin(), Patterns.end(),
1344 PatternSortingPredicate());
1346 for (unsigned i = 0, e = Patterns.size(); i != e; ++i)
1347 EmitCodeForPattern(*Patterns[i], OS);
1348 OS << " break;\n\n";
1352 OS << " } // end of big switch.\n\n"
1353 << " std::cerr << \"Cannot yet select: \";\n"
1354 << " N.Val->dump();\n"
1355 << " std::cerr << '\\n';\n"
1360 void DAGISelEmitter::run(std::ostream &OS) {
1361 EmitSourceFileHeader("DAG Instruction Selector for the " + Target.getName() +
1364 OS << "// *** NOTE: This file is #included into the middle of the target\n"
1365 << "// *** instruction selector class. These functions are really "
1368 OS << "// Instance var to keep track of multiply used nodes that have \n"
1369 << "// already been selected.\n"
1370 << "std::map<SDOperand, SDOperand> CodeGenMap;\n";
1373 ParseNodeTransforms(OS);
1374 ParsePatternFragments(OS);
1375 ParseInstructions();
1378 // Generate variants. For example, commutative patterns can match
1379 // multiple ways. Add them to PatternsToMatch as well.
1382 // At this point, we have full information about the 'Patterns' we need to
1383 // parse, both implicitly from instructions as well as from explicit pattern
1384 // definitions. Emit the resultant instruction selector.
1385 EmitInstructionSelector(OS);
1387 for (std::map<Record*, TreePattern*>::iterator I = PatternFragments.begin(),
1388 E = PatternFragments.end(); I != E; ++I)
1390 PatternFragments.clear();
1392 Instructions.clear();