1 //==-llvm/CodeGen/DAGISelHeader.h - Common DAG ISel definitions -*- C++ -*-==//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file provides definitions of the common, target-independent methods and
11 // data, which is used by SelectionDAG-based instruction selectors.
13 // *** NOTE: This file is #included into the middle of the target
14 // instruction selector class. These functions are really methods.
15 // This is a little awkward, but it allows this code to be shared
16 // by all the targets while still being able to call into
17 // target-specific code without using a virtual function call.
19 //===----------------------------------------------------------------------===//
21 #ifndef LLVM_CODEGEN_DAGISEL_HEADER_H
22 #define LLVM_CODEGEN_DAGISEL_HEADER_H
24 /// ISelPosition - Node iterator marking the current position of
25 /// instruction selection as it procedes through the topologically-sorted
27 SelectionDAG::allnodes_iterator ISelPosition;
29 /// ChainNotReachable - Returns true if Chain does not reach Op.
30 static bool ChainNotReachable(SDNode *Chain, SDNode *Op) {
31 if (Chain->getOpcode() == ISD::EntryToken)
33 if (Chain->getOpcode() == ISD::TokenFactor)
35 if (Chain->getNumOperands() > 0) {
36 SDValue C0 = Chain->getOperand(0);
37 if (C0.getValueType() == MVT::Other)
38 return C0.getNode() != Op && ChainNotReachable(C0.getNode(), Op);
43 /// IsChainCompatible - Returns true if Chain is Op or Chain does not reach Op.
44 /// This is used to ensure that there are no nodes trapped between Chain, which
45 /// is the first chain node discovered in a pattern and Op, a later node, that
46 /// will not be selected into the pattern.
47 static bool IsChainCompatible(SDNode *Chain, SDNode *Op) {
48 return Chain == Op || ChainNotReachable(Chain, Op);
52 /// ISelUpdater - helper class to handle updates of the
53 /// instruciton selection graph.
54 class VISIBILITY_HIDDEN ISelUpdater : public SelectionDAG::DAGUpdateListener {
55 SelectionDAG::allnodes_iterator &ISelPosition;
57 explicit ISelUpdater(SelectionDAG::allnodes_iterator &isp)
58 : ISelPosition(isp) {}
60 /// NodeDeleted - Handle nodes deleted from the graph. If the
61 /// node being deleted is the current ISelPosition node, update
64 virtual void NodeDeleted(SDNode *N, SDNode *E) {
65 if (ISelPosition == SelectionDAG::allnodes_iterator(N))
69 /// NodeUpdated - Ignore updates for now.
70 virtual void NodeUpdated(SDNode *N) {}
73 /// ReplaceUses - replace all uses of the old node F with the use
74 /// of the new node T.
75 DISABLE_INLINE void ReplaceUses(SDValue F, SDValue T) {
76 ISelUpdater ISU(ISelPosition);
77 CurDAG->ReplaceAllUsesOfValueWith(F, T, &ISU);
80 /// ReplaceUses - replace all uses of the old nodes F with the use
81 /// of the new nodes T.
82 DISABLE_INLINE void ReplaceUses(const SDValue *F, const SDValue *T,
84 ISelUpdater ISU(ISelPosition);
85 CurDAG->ReplaceAllUsesOfValuesWith(F, T, Num, &ISU);
88 /// ReplaceUses - replace all uses of the old node F with the use
89 /// of the new node T.
90 DISABLE_INLINE void ReplaceUses(SDNode *F, SDNode *T) {
91 ISelUpdater ISU(ISelPosition);
92 CurDAG->ReplaceAllUsesWith(F, T, &ISU);
95 /// SelectRoot - Top level entry to DAG instruction selector.
96 /// Selects instructions starting at the root of the current DAG.
97 void SelectRoot(SelectionDAG &DAG) {
100 // Create a dummy node (which is not added to allnodes), that adds
101 // a reference to the root node, preventing it from being deleted,
102 // and tracking any changes of the root.
103 HandleSDNode Dummy(CurDAG->getRoot());
104 ISelPosition = SelectionDAG::allnodes_iterator(CurDAG->getRoot().getNode());
107 // The AllNodes list is now topological-sorted. Visit the
108 // nodes by starting at the end of the list (the root of the
109 // graph) and preceding back toward the beginning (the entry
111 while (ISelPosition != CurDAG->allnodes_begin()) {
112 SDNode *Node = --ISelPosition;
113 // Skip dead nodes. DAGCombiner is expected to eliminate all dead nodes,
114 // but there are currently some corner cases that it misses. Also, this
115 // makes it theoretically possible to disable the DAGCombiner.
116 if (Node->use_empty())
119 SDNode *ResNode = Select(Node);
120 // If node should not be replaced, continue with the next one.
125 ReplaceUses(Node, ResNode);
127 // If after the replacement this node is not used any more,
128 // remove this dead node.
129 if (Node->use_empty()) { // Don't delete EntryToken, etc.
130 ISelUpdater ISU(ISelPosition);
131 CurDAG->RemoveDeadNode(Node, &ISU);
135 CurDAG->setRoot(Dummy.getValue());
139 /// CheckInteger - Return true if the specified node is not a ConstantSDNode or
140 /// if it doesn't have the specified value.
141 static bool CheckInteger(SDValue V, int64_t Val) {
142 ConstantSDNode *C = dyn_cast<ConstantSDNode>(V);
143 return C == 0 || C->getSExtValue() != Val;
146 /// CheckAndImmediate - Check to see if the specified node is an and with an
147 /// immediate returning true on failure.
149 /// FIXME: Inline this gunk into CheckAndMask.
150 bool CheckAndImmediate(SDValue V, int64_t Val) {
151 if (V->getOpcode() == ISD::AND)
152 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(V->getOperand(1)))
153 if (CheckAndMask(V.getOperand(0), C, Val))
158 /// CheckOrImmediate - Check to see if the specified node is an or with an
159 /// immediate returning true on failure.
161 /// FIXME: Inline this gunk into CheckOrMask.
162 bool CheckOrImmediate(SDValue V, int64_t Val) {
163 if (V->getOpcode() == ISD::OR)
164 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(V->getOperand(1)))
165 if (CheckOrMask(V.getOperand(0), C, Val))
170 void EmitInteger(int64_t Val, MVT::SimpleValueType VT,
171 SmallVectorImpl<SDValue> &RecordedNodes) {
172 RecordedNodes.push_back(CurDAG->getTargetConstant(Val, VT));
175 // These functions are marked always inline so that Idx doesn't get pinned to
177 ALWAYS_INLINE static int8_t
178 GetInt1(const unsigned char *MatcherTable, unsigned &Idx) {
179 return MatcherTable[Idx++];
182 ALWAYS_INLINE static int16_t
183 GetInt2(const unsigned char *MatcherTable, unsigned &Idx) {
184 int16_t Val = (uint8_t)GetInt1(MatcherTable, Idx);
185 Val |= int16_t(GetInt1(MatcherTable, Idx)) << 8;
189 ALWAYS_INLINE static int32_t
190 GetInt4(const unsigned char *MatcherTable, unsigned &Idx) {
191 int32_t Val = (uint16_t)GetInt2(MatcherTable, Idx);
192 Val |= int32_t(GetInt2(MatcherTable, Idx)) << 16;
196 ALWAYS_INLINE static int64_t
197 GetInt8(const unsigned char *MatcherTable, unsigned &Idx) {
198 int64_t Val = (uint32_t)GetInt4(MatcherTable, Idx);
199 Val |= int64_t(GetInt4(MatcherTable, Idx)) << 32;
203 enum BuiltinOpcodes {
207 OPC_CaptureFlagInput,
211 OPC_CheckPatternPredicate,
215 OPC_CheckInteger1, OPC_CheckInteger2, OPC_CheckInteger4, OPC_CheckInteger8,
219 OPC_CheckAndImm1, OPC_CheckAndImm2, OPC_CheckAndImm4, OPC_CheckAndImm8,
220 OPC_CheckOrImm1, OPC_CheckOrImm2, OPC_CheckOrImm4, OPC_CheckOrImm8,
221 OPC_CheckFoldableChainNode,
222 OPC_CheckChainCompatible,
224 OPC_EmitInteger1, OPC_EmitInteger2, OPC_EmitInteger4, OPC_EmitInteger8,
226 OPC_EmitConvertToTarget,
227 OPC_EmitMergeInputChains,
235 OPFL_None = 0, // Node has no chain or flag input and isn't variadic.
236 OPFL_Chain = 1, // Node has a chain input.
237 OPFL_Flag = 2, // Node has a flag input.
238 OPFL_MemRefs = 4, // Node gets accumulated MemRefs.
239 OPFL_Variadic0 = 1<<3, // Node is variadic, root has 0 fixed inputs.
240 OPFL_Variadic1 = 2<<3, // Node is variadic, root has 1 fixed inputs.
241 OPFL_Variadic2 = 3<<3, // Node is variadic, root has 2 fixed inputs.
242 OPFL_Variadic3 = 4<<3, // Node is variadic, root has 3 fixed inputs.
243 OPFL_Variadic4 = 5<<3, // Node is variadic, root has 4 fixed inputs.
244 OPFL_Variadic5 = 6<<3, // Node is variadic, root has 5 fixed inputs.
245 OPFL_Variadic6 = 7<<3, // Node is variadic, root has 6 fixed inputs.
247 OPFL_VariadicInfo = OPFL_Variadic6
250 /// getNumFixedFromVariadicInfo - Transform an EmitNode flags word into the
251 /// number of fixed arity values that should be skipped when copying from the
253 static inline int getNumFixedFromVariadicInfo(unsigned Flags) {
254 return ((Flags&OPFL_VariadicInfo) >> 3)-1;
258 /// FailIndex - If this match fails, this is the index to continue with.
261 /// NodeStackSize - The size of the node stack when the scope was formed.
262 unsigned NodeStackSize;
264 /// NumRecordedNodes - The number of recorded nodes when the scope was formed.
265 unsigned NumRecordedNodes;
267 /// NumMatchedMemRefs - The number of matched memref entries.
268 unsigned NumMatchedMemRefs;
270 /// InputChain/InputFlag - The current chain/flag
271 SDValue InputChain, InputFlag;
273 /// HasChainNodesMatched - True if the ChainNodesMatched list is non-empty.
274 bool HasChainNodesMatched;
277 SDNode *SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable,
278 unsigned TableSize) {
279 // FIXME: Should these even be selected? Handle these cases in the caller?
280 switch (NodeToMatch->getOpcode()) {
283 case ISD::EntryToken: // These nodes remain the same.
284 case ISD::BasicBlock:
286 case ISD::HANDLENODE:
287 case ISD::TargetConstant:
288 case ISD::TargetConstantFP:
289 case ISD::TargetConstantPool:
290 case ISD::TargetFrameIndex:
291 case ISD::TargetExternalSymbol:
292 case ISD::TargetBlockAddress:
293 case ISD::TargetJumpTable:
294 case ISD::TargetGlobalTLSAddress:
295 case ISD::TargetGlobalAddress:
296 case ISD::TokenFactor:
297 case ISD::CopyFromReg:
300 case ISD::AssertSext:
301 case ISD::AssertZext:
302 ReplaceUses(SDValue(NodeToMatch, 0), NodeToMatch->getOperand(0));
304 case ISD::INLINEASM: return Select_INLINEASM(NodeToMatch);
305 case ISD::EH_LABEL: return Select_EH_LABEL(NodeToMatch);
306 case ISD::UNDEF: return Select_UNDEF(NodeToMatch);
309 assert(!NodeToMatch->isMachineOpcode() && "Node already selected!");
311 // Set up the node stack with NodeToMatch as the only node on the stack.
312 SmallVector<SDValue, 8> NodeStack;
313 SDValue N = SDValue(NodeToMatch, 0);
314 NodeStack.push_back(N);
316 // MatchScopes - Scopes used when matching, if a match failure happens, this
317 // indicates where to continue checking.
318 SmallVector<MatchScope, 8> MatchScopes;
320 // RecordedNodes - This is the set of nodes that have been recorded by the
322 SmallVector<SDValue, 8> RecordedNodes;
324 // MatchedMemRefs - This is the set of MemRef's we've seen in the input
326 SmallVector<MachineMemOperand*, 2> MatchedMemRefs;
328 // These are the current input chain and flag for use when generating nodes.
329 // Various Emit operations change these. For example, emitting a copytoreg
330 // uses and updates these.
331 SDValue InputChain, InputFlag;
333 // ChainNodesMatched - If a pattern matches nodes that have input/output
334 // chains, the OPC_EmitMergeInputChains operation is emitted which indicates
335 // which ones they are. The result is captured into this list so that we can
336 // update the chain results when the pattern is complete.
337 SmallVector<SDNode*, 3> ChainNodesMatched;
339 // Interpreter starts at opcode #0.
340 unsigned MatcherIndex = 0;
342 assert(MatcherIndex < TableSize && "Invalid index");
343 switch ((BuiltinOpcodes)MatcherTable[MatcherIndex++]) {
345 unsigned NumToSkip = MatcherTable[MatcherIndex++];
347 NewEntry.FailIndex = MatcherIndex+NumToSkip;
348 NewEntry.NodeStackSize = NodeStack.size();
349 NewEntry.NumRecordedNodes = RecordedNodes.size();
350 NewEntry.NumMatchedMemRefs = MatchedMemRefs.size();
351 NewEntry.InputChain = InputChain;
352 NewEntry.InputFlag = InputFlag;
353 NewEntry.HasChainNodesMatched = !ChainNodesMatched.empty();
354 MatchScopes.push_back(NewEntry);
358 // Remember this node, it may end up being an operand in the pattern.
359 RecordedNodes.push_back(N);
361 case OPC_RecordMemRef:
362 MatchedMemRefs.push_back(cast<MemSDNode>(N)->getMemOperand());
365 case OPC_CaptureFlagInput:
366 // If the current node has an input flag, capture it in InputFlag.
367 if (N->getNumOperands() != 0 &&
368 N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag)
369 InputFlag = N->getOperand(N->getNumOperands()-1);
372 case OPC_MoveChild: {
373 unsigned Child = MatcherTable[MatcherIndex++];
374 if (Child >= N.getNumOperands())
375 break; // Match fails if out of range child #.
376 N = N.getOperand(Child);
377 NodeStack.push_back(N);
382 // Pop the current node off the NodeStack.
383 NodeStack.pop_back();
384 assert(!NodeStack.empty() && "Node stack imbalance!");
385 N = NodeStack.back();
388 case OPC_CheckSame: {
389 // Accept if it is exactly the same as a previously recorded node.
390 unsigned RecNo = MatcherTable[MatcherIndex++];
391 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
392 if (N != RecordedNodes[RecNo]) break;
395 case OPC_CheckPatternPredicate:
396 if (!CheckPatternPredicate(MatcherTable[MatcherIndex++])) break;
398 case OPC_CheckPredicate:
399 if (!CheckNodePredicate(N.getNode(), MatcherTable[MatcherIndex++])) break;
401 case OPC_CheckComplexPat:
402 if (!CheckComplexPattern(NodeToMatch, N,
403 MatcherTable[MatcherIndex++], RecordedNodes))
406 case OPC_CheckOpcode:
407 if (N->getOpcode() != MatcherTable[MatcherIndex++]) break;
409 case OPC_CheckType: {
410 MVT::SimpleValueType VT =
411 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
412 if (N.getValueType() != VT) {
413 // Handle the case when VT is iPTR.
414 if (VT != MVT::iPTR || N.getValueType() != TLI.getPointerTy())
419 case OPC_CheckCondCode:
420 if (cast<CondCodeSDNode>(N)->get() !=
421 (ISD::CondCode)MatcherTable[MatcherIndex++]) break;
423 case OPC_CheckValueType: {
424 MVT::SimpleValueType VT =
425 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
426 if (cast<VTSDNode>(N)->getVT() != VT) {
427 // Handle the case when VT is iPTR.
428 if (VT != MVT::iPTR || cast<VTSDNode>(N)->getVT() != TLI.getPointerTy())
433 case OPC_CheckInteger1:
434 if (CheckInteger(N, GetInt1(MatcherTable, MatcherIndex))) break;
436 case OPC_CheckInteger2:
437 if (CheckInteger(N, GetInt2(MatcherTable, MatcherIndex))) break;
439 case OPC_CheckInteger4:
440 if (CheckInteger(N, GetInt4(MatcherTable, MatcherIndex))) break;
442 case OPC_CheckInteger8:
443 if (CheckInteger(N, GetInt8(MatcherTable, MatcherIndex))) break;
446 case OPC_CheckAndImm1:
447 if (CheckAndImmediate(N, GetInt1(MatcherTable, MatcherIndex))) break;
449 case OPC_CheckAndImm2:
450 if (CheckAndImmediate(N, GetInt2(MatcherTable, MatcherIndex))) break;
452 case OPC_CheckAndImm4:
453 if (CheckAndImmediate(N, GetInt4(MatcherTable, MatcherIndex))) break;
455 case OPC_CheckAndImm8:
456 if (CheckAndImmediate(N, GetInt8(MatcherTable, MatcherIndex))) break;
459 case OPC_CheckOrImm1:
460 if (CheckOrImmediate(N, GetInt1(MatcherTable, MatcherIndex))) break;
462 case OPC_CheckOrImm2:
463 if (CheckOrImmediate(N, GetInt2(MatcherTable, MatcherIndex))) break;
465 case OPC_CheckOrImm4:
466 if (CheckOrImmediate(N, GetInt4(MatcherTable, MatcherIndex))) break;
468 case OPC_CheckOrImm8:
469 if (CheckOrImmediate(N, GetInt8(MatcherTable, MatcherIndex))) break;
472 case OPC_CheckFoldableChainNode: {
473 assert(!NodeStack.size() == 1 && "No parent node");
474 // Verify that all intermediate nodes between the root and this one have
476 bool HasMultipleUses = false;
477 for (unsigned i = 1, e = NodeStack.size()-1; i != e; ++i)
478 if (!NodeStack[i].hasOneUse()) {
479 HasMultipleUses = true;
482 if (HasMultipleUses) break;
484 // Check to see that the target thinks this is profitable to fold and that
485 // we can fold it without inducing cycles in the graph.
486 if (!IsProfitableToFold(N, NodeStack[NodeStack.size()-2].getNode(),
488 !IsLegalToFold(N, NodeStack[NodeStack.size()-2].getNode(),
494 case OPC_CheckChainCompatible: {
495 unsigned PrevNode = MatcherTable[MatcherIndex++];
496 assert(PrevNode < RecordedNodes.size() && "Invalid CheckChainCompatible");
497 SDValue PrevChainedNode = RecordedNodes[PrevNode];
498 SDValue ThisChainedNode = RecordedNodes.back();
500 // We have two nodes with chains, verify that their input chains are good.
501 assert(PrevChainedNode.getOperand(0).getValueType() == MVT::Other &&
502 ThisChainedNode.getOperand(0).getValueType() == MVT::Other &&
503 "Invalid chained nodes");
505 if (!IsChainCompatible(// Input chain of the previous node.
506 PrevChainedNode.getOperand(0).getNode(),
508 ThisChainedNode.getNode()))
513 case OPC_EmitInteger1: {
514 MVT::SimpleValueType VT =
515 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
516 EmitInteger(GetInt1(MatcherTable, MatcherIndex), VT, RecordedNodes);
519 case OPC_EmitInteger2: {
520 MVT::SimpleValueType VT =
521 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
522 EmitInteger(GetInt2(MatcherTable, MatcherIndex), VT, RecordedNodes);
525 case OPC_EmitInteger4: {
526 MVT::SimpleValueType VT =
527 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
528 EmitInteger(GetInt4(MatcherTable, MatcherIndex), VT, RecordedNodes);
531 case OPC_EmitInteger8: {
532 MVT::SimpleValueType VT =
533 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
534 EmitInteger(GetInt8(MatcherTable, MatcherIndex), VT, RecordedNodes);
538 case OPC_EmitRegister: {
539 MVT::SimpleValueType VT =
540 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
541 unsigned RegNo = MatcherTable[MatcherIndex++];
542 RecordedNodes.push_back(CurDAG->getRegister(RegNo, VT));
546 case OPC_EmitConvertToTarget: {
547 // Convert from IMM/FPIMM to target version.
548 unsigned RecNo = MatcherTable[MatcherIndex++];
549 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
550 SDValue Imm = RecordedNodes[RecNo];
552 if (Imm->getOpcode() == ISD::Constant) {
553 int64_t Val = cast<ConstantSDNode>(Imm)->getZExtValue();
554 Imm = CurDAG->getTargetConstant(Val, Imm.getValueType());
555 } else if (Imm->getOpcode() == ISD::ConstantFP) {
556 const ConstantFP *Val=cast<ConstantFPSDNode>(Imm)->getConstantFPValue();
557 Imm = CurDAG->getTargetConstantFP(*Val, Imm.getValueType());
560 RecordedNodes.push_back(Imm);
564 case OPC_EmitMergeInputChains: {
565 assert(InputChain.getNode() == 0 &&
566 "EmitMergeInputChains should be the first chain producing node");
567 // This node gets a list of nodes we matched in the input that have
568 // chains. We want to token factor all of the input chains to these nodes
569 // together. However, if any of the input chains is actually one of the
570 // nodes matched in this pattern, then we have an intra-match reference.
571 // Ignore these because the newly token factored chain should not refer to
573 unsigned NumChains = MatcherTable[MatcherIndex++];
574 assert(NumChains != 0 && "Can't TF zero chains");
576 // The common case here is that we have exactly one chain, which is really
577 // cheap to handle, just do it.
578 if (NumChains == 1) {
579 unsigned RecNo = MatcherTable[MatcherIndex++];
580 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
581 ChainNodesMatched.push_back(RecordedNodes[RecNo].getNode());
582 InputChain = RecordedNodes[RecNo].getOperand(0);
583 assert(InputChain.getValueType() == MVT::Other && "Not a chain");
587 // Read all of the chained nodes.
588 assert(ChainNodesMatched.empty() &&
589 "Should only have one EmitMergeInputChains per match");
590 for (unsigned i = 0; i != NumChains; ++i) {
591 unsigned RecNo = MatcherTable[MatcherIndex++];
592 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
593 ChainNodesMatched.push_back(RecordedNodes[RecNo].getNode());
596 // Walk all the chained nodes, adding the input chains if they are not in
597 // ChainedNodes (and this, not in the matched pattern). This is an N^2
598 // algorithm, but # chains is usually 2 here, at most 3 for MSP430.
599 SmallVector<SDValue, 3> InputChains;
600 for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
601 SDValue InChain = ChainNodesMatched[i]->getOperand(0);
602 assert(InChain.getValueType() == MVT::Other && "Not a chain");
603 bool Invalid = false;
604 for (unsigned j = 0; j != e; ++j)
605 Invalid |= ChainNodesMatched[j] == InChain.getNode();
607 InputChains.push_back(InChain);
611 if (InputChains.size() == 1)
612 InputChain = InputChains[0];
614 InputChain = CurDAG->getNode(ISD::TokenFactor,
615 NodeToMatch->getDebugLoc(), MVT::Other,
616 &InputChains[0], InputChains.size());
620 case OPC_EmitCopyToReg: {
621 unsigned RecNo = MatcherTable[MatcherIndex++];
622 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
623 unsigned DestPhysReg = MatcherTable[MatcherIndex++];
625 if (InputChain.getNode() == 0)
626 InputChain = CurDAG->getEntryNode();
628 InputChain = CurDAG->getCopyToReg(InputChain, NodeToMatch->getDebugLoc(),
629 DestPhysReg, RecordedNodes[RecNo],
632 InputFlag = InputChain.getValue(1);
636 case OPC_EmitNodeXForm: {
637 unsigned XFormNo = MatcherTable[MatcherIndex++];
638 unsigned RecNo = MatcherTable[MatcherIndex++];
639 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
640 RecordedNodes.push_back(RunSDNodeXForm(RecordedNodes[RecNo], XFormNo));
645 uint16_t TargetOpc = GetInt2(MatcherTable, MatcherIndex);
646 unsigned EmitNodeInfo = MatcherTable[MatcherIndex++];
647 // Get the result VT list.
648 unsigned NumVTs = MatcherTable[MatcherIndex++];
649 assert(NumVTs != 0 && "Invalid node result");
650 SmallVector<EVT, 4> VTs;
651 for (unsigned i = 0; i != NumVTs; ++i) {
652 MVT::SimpleValueType VT =
653 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
654 if (VT == MVT::iPTR) VT = TLI.getPointerTy().SimpleTy;
658 // FIXME: Use faster version for the common 'one VT' case?
659 SDVTList VTList = CurDAG->getVTList(VTs.data(), VTs.size());
661 // Get the operand list.
662 unsigned NumOps = MatcherTable[MatcherIndex++];
663 SmallVector<SDValue, 8> Ops;
664 for (unsigned i = 0; i != NumOps; ++i) {
665 unsigned RecNo = MatcherTable[MatcherIndex++];
666 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
667 Ops.push_back(RecordedNodes[RecNo]);
670 // If there are variadic operands to add, handle them now.
671 if (EmitNodeInfo & OPFL_VariadicInfo) {
672 // Determine the start index to copy from.
673 unsigned FirstOpToCopy = getNumFixedFromVariadicInfo(EmitNodeInfo);
674 FirstOpToCopy += (EmitNodeInfo & OPFL_Chain) ? 1 : 0;
675 assert(NodeToMatch->getNumOperands() >= FirstOpToCopy &&
676 "Invalid variadic node");
677 // Copy all of the variadic operands, not including a potential flag
679 for (unsigned i = FirstOpToCopy, e = NodeToMatch->getNumOperands();
681 SDValue V = NodeToMatch->getOperand(i);
682 if (V.getValueType() == MVT::Flag) break;
687 // If this has chain/flag inputs, add them.
688 if (EmitNodeInfo & OPFL_Chain)
689 Ops.push_back(InputChain);
690 if ((EmitNodeInfo & OPFL_Flag) && InputFlag.getNode() != 0)
691 Ops.push_back(InputFlag);
694 MachineSDNode *Res = CurDAG->getMachineNode(TargetOpc,
695 NodeToMatch->getDebugLoc(),
697 Ops.data(), Ops.size());
698 RecordedNodes.push_back(SDValue(Res, 0));
700 // If the node had chain/flag results, update our notion of the current
702 if (VTs.back() == MVT::Flag) {
703 InputFlag = SDValue(Res, VTs.size()-1);
704 if (EmitNodeInfo & OPFL_Chain)
705 InputChain = SDValue(Res, VTs.size()-2);
706 } else if (EmitNodeInfo & OPFL_Chain)
707 InputChain = SDValue(Res, VTs.size()-1);
709 // If the OPFL_MemRefs flag is set on this node, slap all of the
710 // accumulated memrefs onto it.
712 // FIXME: This is vastly incorrect for patterns with multiple outputs
713 // instructions that access memory and for ComplexPatterns that match
715 if (EmitNodeInfo & OPFL_MemRefs) {
716 MachineSDNode::mmo_iterator MemRefs =
717 MF->allocateMemRefsArray(MatchedMemRefs.size());
718 std::copy(MatchedMemRefs.begin(), MatchedMemRefs.end(), MemRefs);
719 Res->setMemRefs(MemRefs, MemRefs + MatchedMemRefs.size());
724 case OPC_CompleteMatch: {
725 // The match has been completed, and any new nodes (if any) have been
726 // created. Patch up references to the matched dag to use the newly
728 unsigned NumResults = MatcherTable[MatcherIndex++];
730 for (unsigned i = 0; i != NumResults; ++i) {
731 unsigned ResSlot = MatcherTable[MatcherIndex++];
732 assert(ResSlot < RecordedNodes.size() && "Invalid CheckSame");
733 SDValue Res = RecordedNodes[ResSlot];
734 assert((NodeToMatch->getValueType(i) == Res.getValueType() ||
735 NodeToMatch->getValueType(i) == MVT::iPTR ||
736 Res.getValueType() == MVT::iPTR ||
737 NodeToMatch->getValueType(i).getSizeInBits() ==
738 Res.getValueType().getSizeInBits()) &&
739 "invalid replacement");
740 ReplaceUses(SDValue(NodeToMatch, i), Res);
743 // Now that all the normal results are replaced, we replace the chain and
744 // flag results if present.
745 if (!ChainNodesMatched.empty()) {
746 assert(InputChain.getNode() != 0 &&
747 "Matched input chains but didn't produce a chain");
748 // Loop over all of the nodes we matched that produced a chain result.
749 // Replace all the chain results with the final chain we ended up with.
750 for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
751 SDNode *ChainNode = ChainNodesMatched[i];
752 SDValue ChainVal = SDValue(ChainNode, ChainNode->getNumValues()-1);
753 if (ChainVal.getValueType() == MVT::Flag)
754 ChainVal = ChainVal.getValue(ChainVal->getNumValues()-2);
755 assert(ChainVal.getValueType() == MVT::Other && "Not a chain?");
756 ReplaceUses(ChainVal, InputChain);
759 // If the root node produces a flag, make sure to replace its flag
760 // result with the resultant flag.
761 if (NodeToMatch->getValueType(NodeToMatch->getNumValues()-1) ==
763 ReplaceUses(SDValue(NodeToMatch, NodeToMatch->getNumValues()-1),
766 // FIXME: We just return here, which interacts correctly with SelectRoot
767 // above. We should fix this to not return an SDNode* anymore.
772 // If the code reached this point, then the match failed pop out to the next
774 if (MatchScopes.empty()) {
775 CannotYetSelect(NodeToMatch);
779 const MatchScope &LastScope = MatchScopes.back();
780 RecordedNodes.resize(LastScope.NumRecordedNodes);
781 NodeStack.resize(LastScope.NodeStackSize);
782 N = NodeStack.back();
784 if (LastScope.NumMatchedMemRefs != MatchedMemRefs.size())
785 MatchedMemRefs.resize(LastScope.NumMatchedMemRefs);
786 MatcherIndex = LastScope.FailIndex;
788 InputChain = LastScope.InputChain;
789 InputFlag = LastScope.InputFlag;
790 if (!LastScope.HasChainNodesMatched)
791 ChainNodesMatched.clear();
793 MatchScopes.pop_back();
798 #endif /* LLVM_CODEGEN_DAGISEL_HEADER_H */