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 type constraints.
141 ListInit *Constraints = TypeProfile->getValueAsListInit("Constraints");
142 for (unsigned i = 0, e = Constraints->getSize(); i != e; ++i) {
143 assert(dynamic_cast<DefInit*>(Constraints->getElement(i)) &&
144 "Constraints list should contain constraint definitions!");
146 static_cast<DefInit*>(Constraints->getElement(i))->getDef();
147 TypeConstraints.push_back(Constraint);
151 //===----------------------------------------------------------------------===//
152 // TreePatternNode implementation
155 TreePatternNode::~TreePatternNode() {
156 #if 0 // FIXME: implement refcounted tree nodes!
157 for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
162 /// UpdateNodeType - Set the node type of N to VT if VT contains
163 /// information. If N already contains a conflicting type, then throw an
164 /// exception. This returns true if any information was updated.
166 bool TreePatternNode::UpdateNodeType(MVT::ValueType VT, TreePattern &TP) {
167 if (VT == MVT::LAST_VALUETYPE || getType() == VT) return false;
168 if (getType() == MVT::LAST_VALUETYPE) {
173 TP.error("Type inference contradiction found in node " +
174 getOperator()->getName() + "!");
175 return true; // unreachable
179 void TreePatternNode::print(std::ostream &OS) const {
181 OS << *getLeafValue();
183 OS << "(" << getOperator()->getName();
186 if (getType() == MVT::Other)
188 else if (getType() == MVT::LAST_VALUETYPE)
191 OS << ":" << getType();
194 if (getNumChildren() != 0) {
196 getChild(0)->print(OS);
197 for (unsigned i = 1, e = getNumChildren(); i != e; ++i) {
199 getChild(i)->print(OS);
205 if (!PredicateFn.empty())
206 OS << "<<P:" << PredicateFn << ">>";
208 OS << "<<X:" << TransformFn->getName() << ">>";
209 if (!getName().empty())
210 OS << ":$" << getName();
213 void TreePatternNode::dump() const {
217 /// clone - Make a copy of this tree and all of its children.
219 TreePatternNode *TreePatternNode::clone() const {
220 TreePatternNode *New;
222 New = new TreePatternNode(getLeafValue());
224 std::vector<TreePatternNode*> CChildren;
225 CChildren.reserve(Children.size());
226 for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
227 CChildren.push_back(getChild(i)->clone());
228 New = new TreePatternNode(getOperator(), CChildren);
230 New->setName(getName());
231 New->setType(getType());
232 New->setPredicateFn(getPredicateFn());
233 New->setTransformFn(getTransformFn());
237 /// SubstituteFormalArguments - Replace the formal arguments in this tree
238 /// with actual values specified by ArgMap.
239 void TreePatternNode::
240 SubstituteFormalArguments(std::map<std::string, TreePatternNode*> &ArgMap) {
241 if (isLeaf()) return;
243 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) {
244 TreePatternNode *Child = getChild(i);
245 if (Child->isLeaf()) {
246 Init *Val = Child->getLeafValue();
247 if (dynamic_cast<DefInit*>(Val) &&
248 static_cast<DefInit*>(Val)->getDef()->getName() == "node") {
249 // We found a use of a formal argument, replace it with its value.
250 Child = ArgMap[Child->getName()];
251 assert(Child && "Couldn't find formal argument!");
255 getChild(i)->SubstituteFormalArguments(ArgMap);
261 /// InlinePatternFragments - If this pattern refers to any pattern
262 /// fragments, inline them into place, giving us a pattern without any
263 /// PatFrag references.
264 TreePatternNode *TreePatternNode::InlinePatternFragments(TreePattern &TP) {
265 if (isLeaf()) return this; // nothing to do.
266 Record *Op = getOperator();
268 if (!Op->isSubClassOf("PatFrag")) {
269 // Just recursively inline children nodes.
270 for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
271 setChild(i, getChild(i)->InlinePatternFragments(TP));
275 // Otherwise, we found a reference to a fragment. First, look up its
276 // TreePattern record.
277 TreePattern *Frag = TP.getDAGISelEmitter().getPatternFragment(Op);
279 // Verify that we are passing the right number of operands.
280 if (Frag->getNumArgs() != Children.size())
281 TP.error("'" + Op->getName() + "' fragment requires " +
282 utostr(Frag->getNumArgs()) + " operands!");
284 TreePatternNode *FragTree = Frag->getOnlyTree()->clone();
286 // Resolve formal arguments to their actual value.
287 if (Frag->getNumArgs()) {
288 // Compute the map of formal to actual arguments.
289 std::map<std::string, TreePatternNode*> ArgMap;
290 for (unsigned i = 0, e = Frag->getNumArgs(); i != e; ++i)
291 ArgMap[Frag->getArgName(i)] = getChild(i)->InlinePatternFragments(TP);
293 FragTree->SubstituteFormalArguments(ArgMap);
296 FragTree->setName(getName());
298 // Get a new copy of this fragment to stitch into here.
299 //delete this; // FIXME: implement refcounting!
303 /// ApplyTypeConstraints - Apply all of the type constraints relevent to
304 /// this node and its children in the tree. This returns true if it makes a
305 /// change, false otherwise. If a type contradiction is found, throw an
307 bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP) {
308 if (isLeaf()) return false;
310 // special handling for set, which isn't really an SDNode.
311 if (getOperator()->getName() == "set") {
312 assert (getNumChildren() == 2 && "Only handle 2 operand set's for now!");
313 bool MadeChange = getChild(0)->ApplyTypeConstraints(TP);
314 MadeChange |= getChild(1)->ApplyTypeConstraints(TP);
316 // Types of operands must match.
317 MadeChange |= getChild(0)->UpdateNodeType(getChild(1)->getType(), TP);
318 MadeChange |= getChild(1)->UpdateNodeType(getChild(0)->getType(), TP);
319 MadeChange |= UpdateNodeType(MVT::isVoid, TP);
321 } else if (getOperator()->isSubClassOf("SDNode")) {
322 const SDNodeInfo &NI = TP.getDAGISelEmitter().getSDNodeInfo(getOperator());
324 bool MadeChange = NI.ApplyTypeConstraints(this, TP);
325 for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
326 MadeChange |= getChild(i)->ApplyTypeConstraints(TP);
328 } else if (getOperator()->isSubClassOf("Instruction")) {
329 const DAGInstruction &Inst =
330 TP.getDAGISelEmitter().getInstruction(getOperator());
332 assert(Inst.getNumResults() == 1 && "Only supports one result instrs!");
333 // Apply the result type to the node
334 bool MadeChange = UpdateNodeType(Inst.getResultType(0), TP);
336 if (getNumChildren() != Inst.getNumOperands())
337 TP.error("Instruction '" + getOperator()->getName() + " expects " +
338 utostr(Inst.getNumOperands()) + " operands, not " +
339 utostr(getNumChildren()) + " operands!");
340 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) {
341 MadeChange |= getChild(i)->UpdateNodeType(Inst.getOperandType(i), TP);
342 MadeChange |= getChild(i)->ApplyTypeConstraints(TP);
346 assert(getOperator()->isSubClassOf("SDNodeXForm") && "Unknown node type!");
348 // Node transforms always take one operand, and take and return the same
350 if (getNumChildren() != 1)
351 TP.error("Node transform '" + getOperator()->getName() +
352 "' requires one operand!");
353 bool MadeChange = UpdateNodeType(getChild(0)->getType(), TP);
354 MadeChange |= getChild(0)->UpdateNodeType(getType(), TP);
360 //===----------------------------------------------------------------------===//
361 // TreePattern implementation
364 TreePattern::TreePattern(Record *TheRec, ListInit *RawPat,
365 DAGISelEmitter &ise) : TheRecord(TheRec), ISE(ise) {
366 for (unsigned i = 0, e = RawPat->getSize(); i != e; ++i)
367 Trees.push_back(ParseTreePattern((DagInit*)RawPat->getElement(i)));
370 TreePattern::TreePattern(Record *TheRec, DagInit *Pat,
371 DAGISelEmitter &ise) : TheRecord(TheRec), ISE(ise) {
372 Trees.push_back(ParseTreePattern(Pat));
375 TreePattern::TreePattern(Record *TheRec, TreePatternNode *Pat,
376 DAGISelEmitter &ise) : TheRecord(TheRec), ISE(ise) {
377 Trees.push_back(Pat);
382 void TreePattern::error(const std::string &Msg) const {
384 throw "In " + TheRecord->getName() + ": " + Msg;
387 /// getIntrinsicType - Check to see if the specified record has an intrinsic
388 /// type which should be applied to it. This infer the type of register
389 /// references from the register file information, for example.
391 MVT::ValueType TreePattern::getIntrinsicType(Record *R) const {
392 // Check to see if this is a register or a register class...
393 if (R->isSubClassOf("RegisterClass"))
394 return getValueType(R->getValueAsDef("RegType"));
395 else if (R->isSubClassOf("PatFrag")) {
396 // Pattern fragment types will be resolved when they are inlined.
397 return MVT::LAST_VALUETYPE;
398 } else if (R->isSubClassOf("Register")) {
399 assert(0 && "Explicit registers not handled here yet!\n");
400 return MVT::LAST_VALUETYPE;
401 } else if (R->isSubClassOf("ValueType")) {
404 } else if (R->getName() == "node") {
406 return MVT::LAST_VALUETYPE;
409 error("Unknown node flavor used in pattern: " + R->getName());
413 TreePatternNode *TreePattern::ParseTreePattern(DagInit *Dag) {
414 Record *Operator = Dag->getNodeType();
416 if (Operator->isSubClassOf("ValueType")) {
417 // If the operator is a ValueType, then this must be "type cast" of a leaf
419 if (Dag->getNumArgs() != 1)
420 error("Type cast only valid for a leaf node!");
422 Init *Arg = Dag->getArg(0);
423 TreePatternNode *New;
424 if (DefInit *DI = dynamic_cast<DefInit*>(Arg)) {
425 Record *R = DI->getDef();
426 if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrag")) {
427 Dag->setArg(0, new DagInit(R,
428 std::vector<std::pair<Init*, std::string> >()));
429 TreePatternNode *TPN = ParseTreePattern(Dag);
430 TPN->setName(Dag->getArgName(0));
434 New = new TreePatternNode(DI);
435 // If it's a regclass or something else known, set the type.
436 New->setType(getIntrinsicType(DI->getDef()));
437 } else if (DagInit *DI = dynamic_cast<DagInit*>(Arg)) {
438 New = ParseTreePattern(DI);
441 error("Unknown leaf value for tree pattern!");
445 // Apply the type cast.
446 New->UpdateNodeType(getValueType(Operator), *this);
450 // Verify that this is something that makes sense for an operator.
451 if (!Operator->isSubClassOf("PatFrag") && !Operator->isSubClassOf("SDNode") &&
452 !Operator->isSubClassOf("Instruction") &&
453 !Operator->isSubClassOf("SDNodeXForm") &&
454 Operator->getName() != "set")
455 error("Unrecognized node '" + Operator->getName() + "'!");
457 std::vector<TreePatternNode*> Children;
459 for (unsigned i = 0, e = Dag->getNumArgs(); i != e; ++i) {
460 Init *Arg = Dag->getArg(i);
461 if (DagInit *DI = dynamic_cast<DagInit*>(Arg)) {
462 Children.push_back(ParseTreePattern(DI));
463 Children.back()->setName(Dag->getArgName(i));
464 } else if (DefInit *DefI = dynamic_cast<DefInit*>(Arg)) {
465 Record *R = DefI->getDef();
466 // Direct reference to a leaf DagNode or PatFrag? Turn it into a
467 // TreePatternNode if its own.
468 if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrag")) {
469 Dag->setArg(i, new DagInit(R,
470 std::vector<std::pair<Init*, std::string> >()));
471 --i; // Revisit this node...
473 TreePatternNode *Node = new TreePatternNode(DefI);
474 Node->setName(Dag->getArgName(i));
475 Children.push_back(Node);
477 // If it's a regclass or something else known, set the type.
478 Node->setType(getIntrinsicType(R));
481 if (R->getName() == "node") {
482 if (Dag->getArgName(i).empty())
483 error("'node' argument requires a name to match with operand list");
484 Args.push_back(Dag->getArgName(i));
489 error("Unknown leaf value for tree pattern!");
493 return new TreePatternNode(Operator, Children);
496 /// InferAllTypes - Infer/propagate as many types throughout the expression
497 /// patterns as possible. Return true if all types are infered, false
498 /// otherwise. Throw an exception if a type contradiction is found.
499 bool TreePattern::InferAllTypes() {
500 bool MadeChange = true;
503 for (unsigned i = 0, e = Trees.size(); i != e; ++i)
504 MadeChange |= Trees[i]->ApplyTypeConstraints(*this);
507 bool HasUnresolvedTypes = false;
508 for (unsigned i = 0, e = Trees.size(); i != e; ++i)
509 HasUnresolvedTypes |= Trees[i]->ContainsUnresolvedType();
510 return !HasUnresolvedTypes;
513 void TreePattern::print(std::ostream &OS) const {
514 OS << getRecord()->getName();
516 OS << "(" << Args[0];
517 for (unsigned i = 1, e = Args.size(); i != e; ++i)
518 OS << ", " << Args[i];
523 if (Trees.size() > 1)
525 for (unsigned i = 0, e = Trees.size(); i != e; ++i) {
531 if (Trees.size() > 1)
535 void TreePattern::dump() const { print(std::cerr); }
539 //===----------------------------------------------------------------------===//
540 // DAGISelEmitter implementation
543 // Parse all of the SDNode definitions for the target, populating SDNodes.
544 void DAGISelEmitter::ParseNodeInfo() {
545 std::vector<Record*> Nodes = Records.getAllDerivedDefinitions("SDNode");
546 while (!Nodes.empty()) {
547 SDNodes.insert(std::make_pair(Nodes.back(), Nodes.back()));
552 /// ParseNodeTransforms - Parse all SDNodeXForm instances into the SDNodeXForms
553 /// map, and emit them to the file as functions.
554 void DAGISelEmitter::ParseNodeTransforms(std::ostream &OS) {
555 OS << "\n// Node transformations.\n";
556 std::vector<Record*> Xforms = Records.getAllDerivedDefinitions("SDNodeXForm");
557 while (!Xforms.empty()) {
558 Record *XFormNode = Xforms.back();
559 Record *SDNode = XFormNode->getValueAsDef("Opcode");
560 std::string Code = XFormNode->getValueAsCode("XFormFunction");
561 SDNodeXForms.insert(std::make_pair(XFormNode,
562 std::make_pair(SDNode, Code)));
565 std::string ClassName = getSDNodeInfo(SDNode).getSDClassName();
566 const char *C2 = ClassName == "SDNode" ? "N" : "inN";
568 OS << "inline SDOperand Transform_" << XFormNode->getName()
569 << "(SDNode *" << C2 << ") {\n";
570 if (ClassName != "SDNode")
571 OS << " " << ClassName << " *N = cast<" << ClassName << ">(inN);\n";
572 OS << Code << "\n}\n";
581 /// ParsePatternFragments - Parse all of the PatFrag definitions in the .td
582 /// file, building up the PatternFragments map. After we've collected them all,
583 /// inline fragments together as necessary, so that there are no references left
584 /// inside a pattern fragment to a pattern fragment.
586 /// This also emits all of the predicate functions to the output file.
588 void DAGISelEmitter::ParsePatternFragments(std::ostream &OS) {
589 std::vector<Record*> Fragments = Records.getAllDerivedDefinitions("PatFrag");
591 // First step, parse all of the fragments and emit predicate functions.
592 OS << "\n// Predicate functions.\n";
593 for (unsigned i = 0, e = Fragments.size(); i != e; ++i) {
594 DagInit *Tree = Fragments[i]->getValueAsDag("Fragment");
595 TreePattern *P = new TreePattern(Fragments[i], Tree, *this);
596 PatternFragments[Fragments[i]] = P;
598 // Validate the argument list, converting it to map, to discard duplicates.
599 std::vector<std::string> &Args = P->getArgList();
600 std::set<std::string> OperandsMap(Args.begin(), Args.end());
602 if (OperandsMap.count(""))
603 P->error("Cannot have unnamed 'node' values in pattern fragment!");
605 // Parse the operands list.
606 DagInit *OpsList = Fragments[i]->getValueAsDag("Operands");
607 if (OpsList->getNodeType()->getName() != "ops")
608 P->error("Operands list should start with '(ops ... '!");
610 // Copy over the arguments.
612 for (unsigned j = 0, e = OpsList->getNumArgs(); j != e; ++j) {
613 if (!dynamic_cast<DefInit*>(OpsList->getArg(j)) ||
614 static_cast<DefInit*>(OpsList->getArg(j))->
615 getDef()->getName() != "node")
616 P->error("Operands list should all be 'node' values.");
617 if (OpsList->getArgName(j).empty())
618 P->error("Operands list should have names for each operand!");
619 if (!OperandsMap.count(OpsList->getArgName(j)))
620 P->error("'" + OpsList->getArgName(j) +
621 "' does not occur in pattern or was multiply specified!");
622 OperandsMap.erase(OpsList->getArgName(j));
623 Args.push_back(OpsList->getArgName(j));
626 if (!OperandsMap.empty())
627 P->error("Operands list does not contain an entry for operand '" +
628 *OperandsMap.begin() + "'!");
630 // If there is a code init for this fragment, emit the predicate code and
631 // keep track of the fact that this fragment uses it.
632 std::string Code = Fragments[i]->getValueAsCode("Predicate");
634 assert(!P->getOnlyTree()->isLeaf() && "Can't be a leaf!");
635 std::string ClassName =
636 getSDNodeInfo(P->getOnlyTree()->getOperator()).getSDClassName();
637 const char *C2 = ClassName == "SDNode" ? "N" : "inN";
639 OS << "inline bool Predicate_" << Fragments[i]->getName()
640 << "(SDNode *" << C2 << ") {\n";
641 if (ClassName != "SDNode")
642 OS << " " << ClassName << " *N = cast<" << ClassName << ">(inN);\n";
643 OS << Code << "\n}\n";
644 P->getOnlyTree()->setPredicateFn("Predicate_"+Fragments[i]->getName());
647 // If there is a node transformation corresponding to this, keep track of
649 Record *Transform = Fragments[i]->getValueAsDef("OperandTransform");
650 if (!getSDNodeTransform(Transform).second.empty()) // not noop xform?
651 P->getOnlyTree()->setTransformFn(Transform);
656 // Now that we've parsed all of the tree fragments, do a closure on them so
657 // that there are not references to PatFrags left inside of them.
658 for (std::map<Record*, TreePattern*>::iterator I = PatternFragments.begin(),
659 E = PatternFragments.end(); I != E; ++I) {
660 TreePattern *ThePat = I->second;
661 ThePat->InlinePatternFragments();
663 // Infer as many types as possible. Don't worry about it if we don't infer
664 // all of them, some may depend on the inputs of the pattern.
666 ThePat->InferAllTypes();
668 // If this pattern fragment is not supported by this target (no types can
669 // satisfy its constraints), just ignore it. If the bogus pattern is
670 // actually used by instructions, the type consistency error will be
674 // If debugging, print out the pattern fragment result.
675 DEBUG(ThePat->dump());
679 /// HandleUse - Given "Pat" a leaf in the pattern, check to see if it is an
680 /// instruction input. Return true if this is a real use.
681 static bool HandleUse(TreePattern *I, TreePatternNode *Pat,
682 std::map<std::string, TreePatternNode*> &InstInputs) {
683 // No name -> not interesting.
684 if (Pat->getName().empty()) {
686 DefInit *DI = dynamic_cast<DefInit*>(Pat->getLeafValue());
687 if (DI && DI->getDef()->isSubClassOf("RegisterClass"))
688 I->error("Input " + DI->getDef()->getName() + " must be named!");
696 DefInit *DI = dynamic_cast<DefInit*>(Pat->getLeafValue());
697 if (!DI) I->error("Input $" + Pat->getName() + " must be an identifier!");
700 assert(Pat->getNumChildren() == 0 && "can't be a use with children!");
701 Rec = Pat->getOperator();
704 TreePatternNode *&Slot = InstInputs[Pat->getName()];
709 if (Slot->isLeaf()) {
710 SlotRec = dynamic_cast<DefInit*>(Slot->getLeafValue())->getDef();
712 assert(Slot->getNumChildren() == 0 && "can't be a use with children!");
713 SlotRec = Slot->getOperator();
716 // Ensure that the inputs agree if we've already seen this input.
718 I->error("All $" + Pat->getName() + " inputs must agree with each other");
719 if (Slot->getType() != Pat->getType())
720 I->error("All $" + Pat->getName() + " inputs must agree with each other");
725 /// FindPatternInputsAndOutputs - Scan the specified TreePatternNode (which is
726 /// part of "I", the instruction), computing the set of inputs and outputs of
727 /// the pattern. Report errors if we see anything naughty.
728 void DAGISelEmitter::
729 FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat,
730 std::map<std::string, TreePatternNode*> &InstInputs,
731 std::map<std::string, Record*> &InstResults) {
733 bool isUse = HandleUse(I, Pat, InstInputs);
734 if (!isUse && Pat->getTransformFn())
735 I->error("Cannot specify a transform function for a non-input value!");
737 } else if (Pat->getOperator()->getName() != "set") {
738 // If this is not a set, verify that the children nodes are not void typed,
740 for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) {
741 if (Pat->getChild(i)->getType() == MVT::isVoid)
742 I->error("Cannot have void nodes inside of patterns!");
743 FindPatternInputsAndOutputs(I, Pat->getChild(i), InstInputs, InstResults);
746 // If this is a non-leaf node with no children, treat it basically as if
747 // it were a leaf. This handles nodes like (imm).
749 if (Pat->getNumChildren() == 0)
750 isUse = HandleUse(I, Pat, InstInputs);
752 if (!isUse && Pat->getTransformFn())
753 I->error("Cannot specify a transform function for a non-input value!");
757 // Otherwise, this is a set, validate and collect instruction results.
758 if (Pat->getNumChildren() == 0)
759 I->error("set requires operands!");
760 else if (Pat->getNumChildren() & 1)
761 I->error("set requires an even number of operands");
763 if (Pat->getTransformFn())
764 I->error("Cannot specify a transform function on a set node!");
766 // Check the set destinations.
767 unsigned NumValues = Pat->getNumChildren()/2;
768 for (unsigned i = 0; i != NumValues; ++i) {
769 TreePatternNode *Dest = Pat->getChild(i);
771 I->error("set destination should be a virtual register!");
773 DefInit *Val = dynamic_cast<DefInit*>(Dest->getLeafValue());
775 I->error("set destination should be a virtual register!");
777 if (!Val->getDef()->isSubClassOf("RegisterClass"))
778 I->error("set destination should be a virtual register!");
779 if (Dest->getName().empty())
780 I->error("set destination must have a name!");
781 if (InstResults.count(Dest->getName()))
782 I->error("cannot set '" + Dest->getName() +"' multiple times");
783 InstResults[Dest->getName()] = Val->getDef();
785 // Verify and collect info from the computation.
786 FindPatternInputsAndOutputs(I, Pat->getChild(i+NumValues),
787 InstInputs, InstResults);
792 /// ParseInstructions - Parse all of the instructions, inlining and resolving
793 /// any fragments involved. This populates the Instructions list with fully
794 /// resolved instructions.
795 void DAGISelEmitter::ParseInstructions() {
796 std::vector<Record*> Instrs = Records.getAllDerivedDefinitions("Instruction");
798 for (unsigned i = 0, e = Instrs.size(); i != e; ++i) {
799 if (!dynamic_cast<ListInit*>(Instrs[i]->getValueInit("Pattern")))
800 continue; // no pattern yet, ignore it.
802 ListInit *LI = Instrs[i]->getValueAsListInit("Pattern");
803 if (LI->getSize() == 0) continue; // no pattern.
805 // Parse the instruction.
806 TreePattern *I = new TreePattern(Instrs[i], LI, *this);
807 // Inline pattern fragments into it.
808 I->InlinePatternFragments();
810 // Infer as many types as possible. If we cannot infer all of them, we can
811 // never do anything with this instruction pattern: report it to the user.
812 if (!I->InferAllTypes())
813 I->error("Could not infer all types in pattern!");
815 // InstInputs - Keep track of all of the inputs of the instruction, along
816 // with the record they are declared as.
817 std::map<std::string, TreePatternNode*> InstInputs;
819 // InstResults - Keep track of all the virtual registers that are 'set'
820 // in the instruction, including what reg class they are.
821 std::map<std::string, Record*> InstResults;
823 // Verify that the top-level forms in the instruction are of void type, and
824 // fill in the InstResults map.
825 for (unsigned j = 0, e = I->getNumTrees(); j != e; ++j) {
826 TreePatternNode *Pat = I->getTree(j);
827 if (Pat->getType() != MVT::isVoid) {
829 I->error("Top-level forms in instruction pattern should have"
833 // Find inputs and outputs, and verify the structure of the uses/defs.
834 FindPatternInputsAndOutputs(I, Pat, InstInputs, InstResults);
837 // Now that we have inputs and outputs of the pattern, inspect the operands
838 // list for the instruction. This determines the order that operands are
839 // added to the machine instruction the node corresponds to.
840 unsigned NumResults = InstResults.size();
842 // Parse the operands list from the (ops) list, validating it.
843 std::vector<std::string> &Args = I->getArgList();
844 assert(Args.empty() && "Args list should still be empty here!");
845 CodeGenInstruction &CGI = Target.getInstruction(Instrs[i]->getName());
847 // Check that all of the results occur first in the list.
848 std::vector<MVT::ValueType> ResultTypes;
849 for (unsigned i = 0; i != NumResults; ++i) {
850 if (i == CGI.OperandList.size())
851 I->error("'" + InstResults.begin()->first +
852 "' set but does not appear in operand list!");
853 const std::string &OpName = CGI.OperandList[i].Name;
855 // Check that it exists in InstResults.
856 Record *R = InstResults[OpName];
858 I->error("Operand $" + OpName + " should be a set destination: all "
859 "outputs must occur before inputs in operand list!");
861 if (CGI.OperandList[i].Rec != R)
862 I->error("Operand $" + OpName + " class mismatch!");
864 // Remember the return type.
865 ResultTypes.push_back(CGI.OperandList[i].Ty);
867 // Okay, this one checks out.
868 InstResults.erase(OpName);
871 // Loop over the inputs next. Make a copy of InstInputs so we can destroy
872 // the copy while we're checking the inputs.
873 std::map<std::string, TreePatternNode*> InstInputsCheck(InstInputs);
875 std::vector<TreePatternNode*> ResultNodeOperands;
876 std::vector<MVT::ValueType> OperandTypes;
877 for (unsigned i = NumResults, e = CGI.OperandList.size(); i != e; ++i) {
878 const std::string &OpName = CGI.OperandList[i].Name;
880 I->error("Operand #" + utostr(i) + " in operands list has no name!");
882 if (!InstInputsCheck.count(OpName))
883 I->error("Operand $" + OpName +
884 " does not appear in the instruction pattern");
885 TreePatternNode *InVal = InstInputsCheck[OpName];
886 InstInputsCheck.erase(OpName); // It occurred, remove from map.
887 if (CGI.OperandList[i].Ty != InVal->getType())
888 I->error("Operand $" + OpName +
889 "'s type disagrees between the operand and pattern");
890 OperandTypes.push_back(InVal->getType());
892 // Construct the result for the dest-pattern operand list.
893 TreePatternNode *OpNode = InVal->clone();
895 // No predicate is useful on the result.
896 OpNode->setPredicateFn("");
898 // Promote the xform function to be an explicit node if set.
899 if (Record *Xform = OpNode->getTransformFn()) {
900 OpNode->setTransformFn(0);
901 std::vector<TreePatternNode*> Children;
902 Children.push_back(OpNode);
903 OpNode = new TreePatternNode(Xform, Children);
906 ResultNodeOperands.push_back(OpNode);
909 if (!InstInputsCheck.empty())
910 I->error("Input operand $" + InstInputsCheck.begin()->first +
911 " occurs in pattern but not in operands list!");
913 TreePatternNode *ResultPattern =
914 new TreePatternNode(I->getRecord(), ResultNodeOperands);
916 // Create and insert the instruction.
917 DAGInstruction TheInst(I, ResultTypes, OperandTypes);
918 Instructions.insert(std::make_pair(I->getRecord(), TheInst));
920 // Use a temporary tree pattern to infer all types and make sure that the
921 // constructed result is correct. This depends on the instruction already
922 // being inserted into the Instructions map.
923 TreePattern Temp(I->getRecord(), ResultPattern, *this);
924 Temp.InferAllTypes();
926 DAGInstruction &TheInsertedInst = Instructions.find(I->getRecord())->second;
927 TheInsertedInst.setResultPattern(Temp.getOnlyTree());
932 // If we can, convert the instructions to be patterns that are matched!
933 for (std::map<Record*, DAGInstruction>::iterator II = Instructions.begin(),
934 E = Instructions.end(); II != E; ++II) {
935 TreePattern *I = II->second.getPattern();
937 if (I->getNumTrees() != 1) {
938 std::cerr << "CANNOT HANDLE: " << I->getRecord()->getName() << " yet!";
941 TreePatternNode *Pattern = I->getTree(0);
942 if (Pattern->getOperator()->getName() != "set")
943 continue; // Not a set (store or something?)
945 if (Pattern->getNumChildren() != 2)
946 continue; // Not a set of a single value (not handled so far)
948 TreePatternNode *SrcPattern = Pattern->getChild(1)->clone();
949 TreePatternNode *DstPattern = II->second.getResultPattern();
950 PatternsToMatch.push_back(std::make_pair(SrcPattern, DstPattern));
954 void DAGISelEmitter::ParsePatterns() {
955 std::vector<Record*> Patterns = Records.getAllDerivedDefinitions("Pattern");
957 for (unsigned i = 0, e = Patterns.size(); i != e; ++i) {
958 DagInit *Tree = Patterns[i]->getValueAsDag("PatternToMatch");
959 TreePattern *Pattern = new TreePattern(Patterns[i], Tree, *this);
961 // Inline pattern fragments into it.
962 Pattern->InlinePatternFragments();
964 // Infer as many types as possible. If we cannot infer all of them, we can
965 // never do anything with this pattern: report it to the user.
966 if (!Pattern->InferAllTypes())
967 Pattern->error("Could not infer all types in pattern!");
969 ListInit *LI = Patterns[i]->getValueAsListInit("ResultInstrs");
970 if (LI->getSize() == 0) continue; // no pattern.
972 // Parse the instruction.
973 TreePattern *Result = new TreePattern(Patterns[i], LI, *this);
975 // Inline pattern fragments into it.
976 Result->InlinePatternFragments();
978 // Infer as many types as possible. If we cannot infer all of them, we can
979 // never do anything with this pattern: report it to the user.
980 if (!Result->InferAllTypes())
981 Result->error("Could not infer all types in pattern result!");
983 if (Result->getNumTrees() != 1)
984 Result->error("Cannot handle instructions producing instructions "
985 "with temporaries yet!");
986 PatternsToMatch.push_back(std::make_pair(Pattern->getOnlyTree(),
987 Result->getOnlyTree()));
990 DEBUG(std::cerr << "\n\nPARSED PATTERNS TO MATCH:\n\n";
991 for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i) {
992 std::cerr << "PATTERN: "; PatternsToMatch[i].first->dump();
993 std::cerr << "\nRESULT: ";PatternsToMatch[i].second->dump();
998 /// EmitMatchForPattern - Emit a matcher for N, going to the label for PatternNo
999 /// if the match fails. At this point, we already know that the opcode for N
1000 /// matches, and the SDNode for the result has the RootName specified name.
1001 void DAGISelEmitter::EmitMatchForPattern(TreePatternNode *N,
1002 const std::string &RootName,
1003 std::map<std::string,std::string> &VarMap,
1004 unsigned PatternNo, std::ostream &OS) {
1005 assert(!N->isLeaf() && "Cannot match against a leaf!");
1007 // If this node has a name associated with it, capture it in VarMap. If
1008 // we already saw this in the pattern, emit code to verify dagness.
1009 if (!N->getName().empty()) {
1010 std::string &VarMapEntry = VarMap[N->getName()];
1011 if (VarMapEntry.empty()) {
1012 VarMapEntry = RootName;
1014 // If we get here, this is a second reference to a specific name. Since
1015 // we already have checked that the first reference is valid, we don't
1016 // have to recursively match it, just check that it's the same as the
1017 // previously named thing.
1018 OS << " if (" << VarMapEntry << " != " << RootName
1019 << ") goto P" << PatternNo << "Fail;\n";
1024 // Emit code to load the child nodes and match their contents recursively.
1025 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) {
1026 OS << " SDOperand " << RootName << i <<" = " << RootName
1027 << ".getOperand(" << i << ");\n";
1028 TreePatternNode *Child = N->getChild(i);
1030 if (!Child->isLeaf()) {
1031 // If it's not a leaf, recursively match.
1032 const SDNodeInfo &CInfo = getSDNodeInfo(Child->getOperator());
1033 OS << " if (" << RootName << i << ".getOpcode() != "
1034 << CInfo.getEnumName() << ") goto P" << PatternNo << "Fail;\n";
1035 EmitMatchForPattern(Child, RootName + utostr(i), VarMap, PatternNo, OS);
1037 // If this child has a name associated with it, capture it in VarMap. If
1038 // we already saw this in the pattern, emit code to verify dagness.
1039 if (!Child->getName().empty()) {
1040 std::string &VarMapEntry = VarMap[Child->getName()];
1041 if (VarMapEntry.empty()) {
1042 VarMapEntry = RootName + utostr(i);
1044 // If we get here, this is a second reference to a specific name. Since
1045 // we already have checked that the first reference is valid, we don't
1046 // have to recursively match it, just check that it's the same as the
1047 // previously named thing.
1048 OS << " if (" << VarMapEntry << " != " << RootName << i
1049 << ") goto P" << PatternNo << "Fail;\n";
1054 // Handle leaves of various types.
1055 Init *LeafVal = Child->getLeafValue();
1056 Record *LeafRec = dynamic_cast<DefInit*>(LeafVal)->getDef();
1057 if (LeafRec->isSubClassOf("RegisterClass")) {
1058 // Handle register references. Nothing to do here.
1059 } else if (LeafRec->isSubClassOf("ValueType")) {
1060 // Make sure this is the specified value type.
1061 OS << " if (cast<VTSDNode>(" << RootName << i << ")->getVT() != "
1062 << "MVT::" << LeafRec->getName() << ") goto P" << PatternNo
1066 assert(0 && "Unknown leaf type!");
1071 // If there is a node predicate for this, emit the call.
1072 if (!N->getPredicateFn().empty())
1073 OS << " if (!" << N->getPredicateFn() << "(" << RootName
1074 << ".Val)) goto P" << PatternNo << "Fail;\n";
1078 unsigned DAGISelEmitter::
1079 CodeGenPatternResult(TreePatternNode *N, unsigned &Ctr,
1080 std::map<std::string,std::string> &VariableMap,
1082 // This is something selected from the pattern we matched.
1083 if (!N->getName().empty()) {
1084 const std::string &Val = VariableMap[N->getName()];
1085 assert(!Val.empty() &&
1086 "Variable referenced but not defined and not caught earlier!");
1087 if (Val[0] == 'T' && Val[1] == 'm' && Val[2] == 'p') {
1088 // Already selected this operand, just return the tmpval.
1091 unsigned ResNo = Ctr++;
1092 OS << " SDOperand Tmp" << ResNo << " = Select(" << Val << ");\n";
1093 // FIXME: Add Tmp<ResNo> to VariableMap.
1100 assert(0 && "Unknown leaf type!");
1104 Record *Op = N->getOperator();
1105 if (Op->isSubClassOf("Instruction")) {
1106 // Emit all of the operands.
1107 std::vector<unsigned> Ops;
1108 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i)
1109 Ops.push_back(CodeGenPatternResult(N->getChild(i), Ctr, VariableMap, OS));
1111 CodeGenInstruction &II = Target.getInstruction(Op->getName());
1112 unsigned ResNo = Ctr++;
1114 OS << " SDOperand Tmp" << ResNo << " = CurDAG->getTargetNode("
1115 << II.Namespace << "::" << II.TheDef->getName() << ", MVT::"
1116 << getEnumName(N->getType());
1117 for (unsigned i = 0, e = Ops.size(); i != e; ++i)
1118 OS << ", Tmp" << Ops[i];
1121 } else if (Op->isSubClassOf("SDNodeXForm")) {
1122 assert(N->getNumChildren() == 1 && "node xform should have one child!");
1123 unsigned OpVal = CodeGenPatternResult(N->getChild(0), Ctr, VariableMap, OS);
1125 unsigned ResNo = Ctr++;
1126 OS << " SDOperand Tmp" << ResNo << " = Transform_" << Op->getName()
1127 << "(Tmp" << OpVal << ".Val);\n";
1131 assert(0 && "Unknown node in result pattern!");
1137 /// EmitCodeForPattern - Given a pattern to match, emit code to the specified
1138 /// stream to match the pattern, and generate the code for the match if it
1140 void DAGISelEmitter::EmitCodeForPattern(PatternToMatch &Pattern,
1142 static unsigned PatternCount = 0;
1143 unsigned PatternNo = PatternCount++;
1144 OS << " { // Pattern #" << PatternNo << ": ";
1145 Pattern.first->print(OS);
1148 // Emit the matcher, capturing named arguments in VariableMap.
1149 std::map<std::string,std::string> VariableMap;
1150 EmitMatchForPattern(Pattern.first, "N", VariableMap, PatternNo, OS);
1153 Pattern.second->print(OS);
1157 unsigned Res = CodeGenPatternResult(Pattern.second, TmpNo, VariableMap, OS);
1159 // Add the result to the map if it has multiple uses.
1160 OS << " if (!N.Val->hasOneUse()) CodeGenMap[N] = Tmp" << Res << ";\n";
1161 OS << " return Tmp" << Res << ";\n";
1162 OS << " }\n P" << PatternNo << "Fail:\n";
1165 /// getPatternSize - Return the 'size' of this pattern. We want to match large
1166 /// patterns before small ones. This is used to determine the size of a
1168 static unsigned getPatternSize(TreePatternNode *P) {
1169 assert(MVT::isInteger(P->getType()) || MVT::isFloatingPoint(P->getType()) &&
1170 "Not a valid pattern node to size!");
1171 unsigned Size = 1; // The node itself.
1173 // Count children in the count if they are also nodes.
1174 for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) {
1175 TreePatternNode *Child = P->getChild(i);
1176 if (!Child->isLeaf() && Child->getType() != MVT::Other)
1177 Size += getPatternSize(Child);
1183 // PatternSortingPredicate - return true if we prefer to match LHS before RHS.
1184 // In particular, we want to match maximal patterns first and lowest cost within
1185 // a particular complexity first.
1186 struct PatternSortingPredicate {
1187 bool operator()(DAGISelEmitter::PatternToMatch *LHS,
1188 DAGISelEmitter::PatternToMatch *RHS) {
1189 unsigned LHSSize = getPatternSize(LHS->first);
1190 unsigned RHSSize = getPatternSize(RHS->first);
1191 if (LHSSize > RHSSize) return true; // LHS -> bigger -> less cost
1192 if (LHSSize < RHSSize) return false;
1194 // If they are equal, compare cost.
1195 // FIXME: Compute cost!
1200 void DAGISelEmitter::EmitInstructionSelector(std::ostream &OS) {
1201 // Emit boilerplate.
1202 OS << "// The main instruction selector code.\n"
1203 << "SDOperand SelectCode(SDOperand N) {\n"
1204 << " if (N.getOpcode() >= ISD::BUILTIN_OP_END &&\n"
1205 << " N.getOpcode() < PPCISD::FIRST_NUMBER)\n"
1206 << " return N; // Already selected.\n\n"
1207 << " if (!N.Val->hasOneUse()) {\n"
1208 << " std::map<SDOperand, SDOperand>::iterator CGMI = CodeGenMap.find(N);\n"
1209 << " if (CGMI != CodeGenMap.end()) return CGMI->second;\n"
1211 << " switch (N.getOpcode()) {\n"
1212 << " default: break;\n"
1213 << " case ISD::EntryToken: // These leaves remain the same.\n"
1215 << " case ISD::AssertSext:\n"
1216 << " case ISD::AssertZext:\n"
1217 << " return Select(N.getOperand(0));\n";
1219 // Group the patterns by their top-level opcodes.
1220 std::map<Record*, std::vector<PatternToMatch*> > PatternsByOpcode;
1221 for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i)
1222 PatternsByOpcode[PatternsToMatch[i].first->getOperator()]
1223 .push_back(&PatternsToMatch[i]);
1225 // Loop over all of the case statements.
1226 for (std::map<Record*, std::vector<PatternToMatch*> >::iterator
1227 PBOI = PatternsByOpcode.begin(), E = PatternsByOpcode.end(); PBOI != E;
1229 const SDNodeInfo &OpcodeInfo = getSDNodeInfo(PBOI->first);
1230 std::vector<PatternToMatch*> &Patterns = PBOI->second;
1232 OS << " case " << OpcodeInfo.getEnumName() << ":\n";
1234 // We want to emit all of the matching code now. However, we want to emit
1235 // the matches in order of minimal cost. Sort the patterns so the least
1236 // cost one is at the start.
1237 std::stable_sort(Patterns.begin(), Patterns.end(),
1238 PatternSortingPredicate());
1240 for (unsigned i = 0, e = Patterns.size(); i != e; ++i)
1241 EmitCodeForPattern(*Patterns[i], OS);
1242 OS << " break;\n\n";
1246 OS << " } // end of big switch.\n\n"
1247 << " std::cerr << \"Cannot yet select: \";\n"
1248 << " N.Val->dump();\n"
1249 << " std::cerr << '\\n';\n"
1254 void DAGISelEmitter::run(std::ostream &OS) {
1255 EmitSourceFileHeader("DAG Instruction Selector for the " + Target.getName() +
1258 OS << "// *** NOTE: This file is #included into the middle of the target\n"
1259 << "// *** instruction selector class. These functions are really "
1262 OS << "// Instance var to keep track of multiply used nodes that have \n"
1263 << "// already been selected.\n"
1264 << "std::map<SDOperand, SDOperand> CodeGenMap;\n";
1267 ParseNodeTransforms(OS);
1268 ParsePatternFragments(OS);
1269 ParseInstructions();
1272 // FIXME: Generate variants. For example, commutative patterns can match
1273 // multiple ways. Add them to PatternsToMatch as well.
1275 // At this point, we have full information about the 'Patterns' we need to
1276 // parse, both implicitly from instructions as well as from explicit pattern
1279 EmitInstructionSelector(OS);
1281 for (std::map<Record*, TreePattern*>::iterator I = PatternFragments.begin(),
1282 E = PatternFragments.end(); I != E; ++I)
1284 PatternFragments.clear();
1286 Instructions.clear();