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 /// GetVBR - decode a vbr encoding whose top bit is set.
204 ALWAYS_INLINE static unsigned
205 GetVBR(unsigned Val, const unsigned char *MatcherTable, unsigned &Idx) {
206 assert(Val >= 128 && "Not a VBR");
207 Val &= 127; // Remove first vbr bit.
212 NextBits = GetInt1(MatcherTable, Idx);
213 Val |= (NextBits&127) << Shift;
215 } while (NextBits & 128);
220 /// UpdateChainsAndFlags - When a match is complete, this method updates uses of
221 /// interior flag and chain results to use the new flag and chain results.
222 void UpdateChainsAndFlags(SDNode *NodeToMatch, SDValue InputChain,
223 const SmallVectorImpl<SDNode*> &ChainNodesMatched,
225 const SmallVectorImpl<SDNode*>&FlagResultNodesMatched,
226 bool isMorphNodeTo) {
227 // Now that all the normal results are replaced, we replace the chain and
228 // flag results if present.
229 if (!ChainNodesMatched.empty()) {
230 assert(InputChain.getNode() != 0 &&
231 "Matched input chains but didn't produce a chain");
232 // Loop over all of the nodes we matched that produced a chain result.
233 // Replace all the chain results with the final chain we ended up with.
234 for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
235 SDNode *ChainNode = ChainNodesMatched[i];
237 // Don't replace the results of the root node if we're doing a
239 if (ChainNode == NodeToMatch && isMorphNodeTo)
242 SDValue ChainVal = SDValue(ChainNode, ChainNode->getNumValues()-1);
243 if (ChainVal.getValueType() == MVT::Flag)
244 ChainVal = ChainVal.getValue(ChainVal->getNumValues()-2);
245 assert(ChainVal.getValueType() == MVT::Other && "Not a chain?");
246 ReplaceUses(ChainVal, InputChain);
250 // If the result produces a flag, update any flag results in the matched
251 // pattern with the flag result.
252 if (InputFlag.getNode() != 0) {
253 // Handle any interior nodes explicitly marked.
254 for (unsigned i = 0, e = FlagResultNodesMatched.size(); i != e; ++i) {
255 SDNode *FRN = FlagResultNodesMatched[i];
256 assert(FRN->getValueType(FRN->getNumValues()-1) == MVT::Flag &&
257 "Doesn't have a flag result");
258 ReplaceUses(SDValue(FRN, FRN->getNumValues()-1), InputFlag);
262 DEBUG(errs() << "ISEL: Match complete!\n");
267 /// getNumFixedFromVariadicInfo - Transform an EmitNode flags word into the
268 /// number of fixed arity values that should be skipped when copying from the
270 static inline int getNumFixedFromVariadicInfo(unsigned Flags) {
271 return ((Flags&OPFL_VariadicInfo) >> 4)-1;
275 /// FailIndex - If this match fails, this is the index to continue with.
278 /// NodeStack - The node stack when the scope was formed.
279 SmallVector<SDValue, 4> NodeStack;
281 /// NumRecordedNodes - The number of recorded nodes when the scope was formed.
282 unsigned NumRecordedNodes;
284 /// NumMatchedMemRefs - The number of matched memref entries.
285 unsigned NumMatchedMemRefs;
287 /// InputChain/InputFlag - The current chain/flag
288 SDValue InputChain, InputFlag;
290 /// HasChainNodesMatched - True if the ChainNodesMatched list is non-empty.
291 bool HasChainNodesMatched, HasFlagResultNodesMatched;
294 SDNode *SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable,
295 unsigned TableSize) {
296 // FIXME: Should these even be selected? Handle these cases in the caller?
297 switch (NodeToMatch->getOpcode()) {
300 case ISD::EntryToken: // These nodes remain the same.
301 case ISD::BasicBlock:
303 case ISD::HANDLENODE:
304 case ISD::TargetConstant:
305 case ISD::TargetConstantFP:
306 case ISD::TargetConstantPool:
307 case ISD::TargetFrameIndex:
308 case ISD::TargetExternalSymbol:
309 case ISD::TargetBlockAddress:
310 case ISD::TargetJumpTable:
311 case ISD::TargetGlobalTLSAddress:
312 case ISD::TargetGlobalAddress:
313 case ISD::TokenFactor:
314 case ISD::CopyFromReg:
317 case ISD::AssertSext:
318 case ISD::AssertZext:
319 ReplaceUses(SDValue(NodeToMatch, 0), NodeToMatch->getOperand(0));
321 case ISD::INLINEASM: return Select_INLINEASM(NodeToMatch);
322 case ISD::EH_LABEL: return Select_EH_LABEL(NodeToMatch);
323 case ISD::UNDEF: return Select_UNDEF(NodeToMatch);
326 assert(!NodeToMatch->isMachineOpcode() && "Node already selected!");
328 // Set up the node stack with NodeToMatch as the only node on the stack.
329 SmallVector<SDValue, 8> NodeStack;
330 SDValue N = SDValue(NodeToMatch, 0);
331 NodeStack.push_back(N);
333 // MatchScopes - Scopes used when matching, if a match failure happens, this
334 // indicates where to continue checking.
335 SmallVector<MatchScope, 8> MatchScopes;
337 // RecordedNodes - This is the set of nodes that have been recorded by the
339 SmallVector<SDValue, 8> RecordedNodes;
341 // MatchedMemRefs - This is the set of MemRef's we've seen in the input
343 SmallVector<MachineMemOperand*, 2> MatchedMemRefs;
345 // These are the current input chain and flag for use when generating nodes.
346 // Various Emit operations change these. For example, emitting a copytoreg
347 // uses and updates these.
348 SDValue InputChain, InputFlag;
350 // ChainNodesMatched - If a pattern matches nodes that have input/output
351 // chains, the OPC_EmitMergeInputChains operation is emitted which indicates
352 // which ones they are. The result is captured into this list so that we can
353 // update the chain results when the pattern is complete.
354 SmallVector<SDNode*, 3> ChainNodesMatched;
355 SmallVector<SDNode*, 3> FlagResultNodesMatched;
357 DEBUG(errs() << "ISEL: Starting pattern match on root node: ";
358 NodeToMatch->dump(CurDAG);
361 // Interpreter starts at opcode #0.
362 unsigned MatcherIndex = 0;
364 assert(MatcherIndex < TableSize && "Invalid index");
365 BuiltinOpcodes Opcode = (BuiltinOpcodes)MatcherTable[MatcherIndex++];
368 unsigned NumToSkip = MatcherTable[MatcherIndex++];
370 NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);
371 assert(NumToSkip != 0 &&
372 "First entry of OPC_Scope shouldn't be 0, scope has no children?");
374 // Push a MatchScope which indicates where to go if the first child fails
377 NewEntry.FailIndex = MatcherIndex+NumToSkip;
378 NewEntry.NodeStack.append(NodeStack.begin(), NodeStack.end());
379 NewEntry.NumRecordedNodes = RecordedNodes.size();
380 NewEntry.NumMatchedMemRefs = MatchedMemRefs.size();
381 NewEntry.InputChain = InputChain;
382 NewEntry.InputFlag = InputFlag;
383 NewEntry.HasChainNodesMatched = !ChainNodesMatched.empty();
384 NewEntry.HasFlagResultNodesMatched = !FlagResultNodesMatched.empty();
385 MatchScopes.push_back(NewEntry);
389 // Remember this node, it may end up being an operand in the pattern.
390 RecordedNodes.push_back(N);
393 case OPC_RecordChild0: case OPC_RecordChild1:
394 case OPC_RecordChild2: case OPC_RecordChild3:
395 case OPC_RecordChild4: case OPC_RecordChild5:
396 case OPC_RecordChild6: case OPC_RecordChild7: {
397 unsigned ChildNo = Opcode-OPC_RecordChild0;
398 if (ChildNo >= N.getNumOperands())
399 break; // Match fails if out of range child #.
401 RecordedNodes.push_back(N->getOperand(ChildNo));
404 case OPC_RecordMemRef:
405 MatchedMemRefs.push_back(cast<MemSDNode>(N)->getMemOperand());
408 case OPC_CaptureFlagInput:
409 // If the current node has an input flag, capture it in InputFlag.
410 if (N->getNumOperands() != 0 &&
411 N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag)
412 InputFlag = N->getOperand(N->getNumOperands()-1);
415 case OPC_MoveChild: {
416 unsigned ChildNo = MatcherTable[MatcherIndex++];
417 if (ChildNo >= N.getNumOperands())
418 break; // Match fails if out of range child #.
419 N = N.getOperand(ChildNo);
420 NodeStack.push_back(N);
425 // Pop the current node off the NodeStack.
426 NodeStack.pop_back();
427 assert(!NodeStack.empty() && "Node stack imbalance!");
428 N = NodeStack.back();
431 case OPC_CheckSame: {
432 // Accept if it is exactly the same as a previously recorded node.
433 unsigned RecNo = MatcherTable[MatcherIndex++];
434 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
435 if (N != RecordedNodes[RecNo]) break;
438 case OPC_CheckPatternPredicate:
439 if (!CheckPatternPredicate(MatcherTable[MatcherIndex++])) break;
441 case OPC_CheckPredicate:
442 if (!CheckNodePredicate(N.getNode(), MatcherTable[MatcherIndex++])) break;
444 case OPC_CheckComplexPat:
445 if (!CheckComplexPattern(NodeToMatch, N,
446 MatcherTable[MatcherIndex++], RecordedNodes))
449 case OPC_CheckOpcode:
450 if (N->getOpcode() != MatcherTable[MatcherIndex++]) break;
453 case OPC_CheckMultiOpcode: {
454 unsigned NumOps = MatcherTable[MatcherIndex++];
455 bool OpcodeEquals = false;
456 for (unsigned i = 0; i != NumOps; ++i)
457 OpcodeEquals |= N->getOpcode() == MatcherTable[MatcherIndex++];
458 if (!OpcodeEquals) break;
462 case OPC_CheckType: {
463 MVT::SimpleValueType VT =
464 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
465 if (N.getValueType() != VT) {
466 // Handle the case when VT is iPTR.
467 if (VT != MVT::iPTR || N.getValueType() != TLI.getPointerTy())
472 case OPC_CheckChild0Type: case OPC_CheckChild1Type:
473 case OPC_CheckChild2Type: case OPC_CheckChild3Type:
474 case OPC_CheckChild4Type: case OPC_CheckChild5Type:
475 case OPC_CheckChild6Type: case OPC_CheckChild7Type: {
476 unsigned ChildNo = Opcode-OPC_CheckChild0Type;
477 if (ChildNo >= N.getNumOperands())
478 break; // Match fails if out of range child #.
480 MVT::SimpleValueType VT =
481 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
482 EVT ChildVT = N.getOperand(ChildNo).getValueType();
484 // Handle the case when VT is iPTR.
485 if (VT != MVT::iPTR || ChildVT != TLI.getPointerTy())
490 case OPC_CheckCondCode:
491 if (cast<CondCodeSDNode>(N)->get() !=
492 (ISD::CondCode)MatcherTable[MatcherIndex++]) break;
494 case OPC_CheckValueType: {
495 MVT::SimpleValueType VT =
496 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
497 if (cast<VTSDNode>(N)->getVT() != VT) {
498 // Handle the case when VT is iPTR.
499 if (VT != MVT::iPTR || cast<VTSDNode>(N)->getVT() != TLI.getPointerTy())
504 case OPC_CheckInteger1:
505 if (CheckInteger(N, GetInt1(MatcherTable, MatcherIndex))) break;
507 case OPC_CheckInteger2:
508 if (CheckInteger(N, GetInt2(MatcherTable, MatcherIndex))) break;
510 case OPC_CheckInteger4:
511 if (CheckInteger(N, GetInt4(MatcherTable, MatcherIndex))) break;
513 case OPC_CheckInteger8:
514 if (CheckInteger(N, GetInt8(MatcherTable, MatcherIndex))) break;
517 case OPC_CheckAndImm1:
518 if (CheckAndImmediate(N, GetInt1(MatcherTable, MatcherIndex))) break;
520 case OPC_CheckAndImm2:
521 if (CheckAndImmediate(N, GetInt2(MatcherTable, MatcherIndex))) break;
523 case OPC_CheckAndImm4:
524 if (CheckAndImmediate(N, GetInt4(MatcherTable, MatcherIndex))) break;
526 case OPC_CheckAndImm8:
527 if (CheckAndImmediate(N, GetInt8(MatcherTable, MatcherIndex))) break;
530 case OPC_CheckOrImm1:
531 if (CheckOrImmediate(N, GetInt1(MatcherTable, MatcherIndex))) break;
533 case OPC_CheckOrImm2:
534 if (CheckOrImmediate(N, GetInt2(MatcherTable, MatcherIndex))) break;
536 case OPC_CheckOrImm4:
537 if (CheckOrImmediate(N, GetInt4(MatcherTable, MatcherIndex))) break;
539 case OPC_CheckOrImm8:
540 if (CheckOrImmediate(N, GetInt8(MatcherTable, MatcherIndex))) break;
543 case OPC_CheckFoldableChainNode: {
544 assert(NodeStack.size() != 1 && "No parent node");
545 // Verify that all intermediate nodes between the root and this one have
547 bool HasMultipleUses = false;
548 for (unsigned i = 1, e = NodeStack.size()-1; i != e; ++i)
549 if (!NodeStack[i].hasOneUse()) {
550 HasMultipleUses = true;
553 if (HasMultipleUses) break;
555 // Check to see that the target thinks this is profitable to fold and that
556 // we can fold it without inducing cycles in the graph.
557 if (!IsProfitableToFold(N, NodeStack[NodeStack.size()-2].getNode(),
559 !IsLegalToFold(N, NodeStack[NodeStack.size()-2].getNode(),
565 case OPC_CheckChainCompatible: {
566 unsigned PrevNode = MatcherTable[MatcherIndex++];
567 assert(PrevNode < RecordedNodes.size() && "Invalid CheckChainCompatible");
568 SDValue PrevChainedNode = RecordedNodes[PrevNode];
569 SDValue ThisChainedNode = RecordedNodes.back();
571 // We have two nodes with chains, verify that their input chains are good.
572 assert(PrevChainedNode.getOperand(0).getValueType() == MVT::Other &&
573 ThisChainedNode.getOperand(0).getValueType() == MVT::Other &&
574 "Invalid chained nodes");
576 if (!IsChainCompatible(// Input chain of the previous node.
577 PrevChainedNode.getOperand(0).getNode(),
579 ThisChainedNode.getNode()))
584 case OPC_EmitInteger1: {
585 MVT::SimpleValueType VT =
586 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
587 EmitInteger(GetInt1(MatcherTable, MatcherIndex), VT, RecordedNodes);
590 case OPC_EmitInteger2: {
591 MVT::SimpleValueType VT =
592 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
593 EmitInteger(GetInt2(MatcherTable, MatcherIndex), VT, RecordedNodes);
596 case OPC_EmitInteger4: {
597 MVT::SimpleValueType VT =
598 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
599 EmitInteger(GetInt4(MatcherTable, MatcherIndex), VT, RecordedNodes);
602 case OPC_EmitInteger8: {
603 MVT::SimpleValueType VT =
604 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
605 EmitInteger(GetInt8(MatcherTable, MatcherIndex), VT, RecordedNodes);
609 case OPC_EmitRegister: {
610 MVT::SimpleValueType VT =
611 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
612 unsigned RegNo = MatcherTable[MatcherIndex++];
613 RecordedNodes.push_back(CurDAG->getRegister(RegNo, VT));
617 case OPC_EmitConvertToTarget: {
618 // Convert from IMM/FPIMM to target version.
619 unsigned RecNo = MatcherTable[MatcherIndex++];
620 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
621 SDValue Imm = RecordedNodes[RecNo];
623 if (Imm->getOpcode() == ISD::Constant) {
624 int64_t Val = cast<ConstantSDNode>(Imm)->getZExtValue();
625 Imm = CurDAG->getTargetConstant(Val, Imm.getValueType());
626 } else if (Imm->getOpcode() == ISD::ConstantFP) {
627 const ConstantFP *Val=cast<ConstantFPSDNode>(Imm)->getConstantFPValue();
628 Imm = CurDAG->getTargetConstantFP(*Val, Imm.getValueType());
631 RecordedNodes.push_back(Imm);
635 case OPC_EmitMergeInputChains: {
636 assert(InputChain.getNode() == 0 &&
637 "EmitMergeInputChains should be the first chain producing node");
638 // This node gets a list of nodes we matched in the input that have
639 // chains. We want to token factor all of the input chains to these nodes
640 // together. However, if any of the input chains is actually one of the
641 // nodes matched in this pattern, then we have an intra-match reference.
642 // Ignore these because the newly token factored chain should not refer to
644 unsigned NumChains = MatcherTable[MatcherIndex++];
645 assert(NumChains != 0 && "Can't TF zero chains");
647 assert(ChainNodesMatched.empty() &&
648 "Should only have one EmitMergeInputChains per match");
650 // Handle the first chain.
651 unsigned RecNo = MatcherTable[MatcherIndex++];
652 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
653 ChainNodesMatched.push_back(RecordedNodes[RecNo].getNode());
655 // If the chained node is not the root, we can't fold it if it has
657 // FIXME: What if other value results of the node have uses not matched by
659 if (ChainNodesMatched.back() != NodeToMatch &&
660 !RecordedNodes[RecNo].hasOneUse()) {
661 ChainNodesMatched.clear();
665 // The common case here is that we have exactly one chain, which is really
666 // cheap to handle, just do it.
667 if (NumChains == 1) {
668 InputChain = RecordedNodes[RecNo].getOperand(0);
669 assert(InputChain.getValueType() == MVT::Other && "Not a chain");
673 // Read all of the chained nodes.
674 for (unsigned i = 1; i != NumChains; ++i) {
675 RecNo = MatcherTable[MatcherIndex++];
676 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
677 ChainNodesMatched.push_back(RecordedNodes[RecNo].getNode());
679 // FIXME: What if other value results of the node have uses not matched by
681 if (ChainNodesMatched.back() != NodeToMatch &&
682 !RecordedNodes[RecNo].hasOneUse()) {
683 ChainNodesMatched.clear();
688 // Walk all the chained nodes, adding the input chains if they are not in
689 // ChainedNodes (and this, not in the matched pattern). This is an N^2
690 // algorithm, but # chains is usually 2 here, at most 3 for MSP430.
691 SmallVector<SDValue, 3> InputChains;
692 for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
693 SDValue InChain = ChainNodesMatched[i]->getOperand(0);
694 assert(InChain.getValueType() == MVT::Other && "Not a chain");
695 bool Invalid = false;
696 for (unsigned j = 0; j != e; ++j)
697 Invalid |= ChainNodesMatched[j] == InChain.getNode();
699 InputChains.push_back(InChain);
703 if (InputChains.size() == 1)
704 InputChain = InputChains[0];
706 InputChain = CurDAG->getNode(ISD::TokenFactor,
707 NodeToMatch->getDebugLoc(), MVT::Other,
708 &InputChains[0], InputChains.size());
712 case OPC_EmitCopyToReg: {
713 unsigned RecNo = MatcherTable[MatcherIndex++];
714 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
715 unsigned DestPhysReg = MatcherTable[MatcherIndex++];
717 if (InputChain.getNode() == 0)
718 InputChain = CurDAG->getEntryNode();
720 InputChain = CurDAG->getCopyToReg(InputChain, NodeToMatch->getDebugLoc(),
721 DestPhysReg, RecordedNodes[RecNo],
724 InputFlag = InputChain.getValue(1);
728 case OPC_EmitNodeXForm: {
729 unsigned XFormNo = MatcherTable[MatcherIndex++];
730 unsigned RecNo = MatcherTable[MatcherIndex++];
731 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
732 RecordedNodes.push_back(RunSDNodeXForm(RecordedNodes[RecNo], XFormNo));
737 case OPC_MorphNodeTo: {
738 uint16_t TargetOpc = GetInt2(MatcherTable, MatcherIndex);
739 unsigned EmitNodeInfo = MatcherTable[MatcherIndex++];
740 // Get the result VT list.
741 unsigned NumVTs = MatcherTable[MatcherIndex++];
742 SmallVector<EVT, 4> VTs;
743 for (unsigned i = 0; i != NumVTs; ++i) {
744 MVT::SimpleValueType VT =
745 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
746 if (VT == MVT::iPTR) VT = TLI.getPointerTy().SimpleTy;
750 if (EmitNodeInfo & OPFL_Chain)
751 VTs.push_back(MVT::Other);
752 if (EmitNodeInfo & OPFL_FlagOutput)
753 VTs.push_back(MVT::Flag);
755 // FIXME: Use faster version for the common 'one VT' case?
756 SDVTList VTList = CurDAG->getVTList(VTs.data(), VTs.size());
758 // Get the operand list.
759 unsigned NumOps = MatcherTable[MatcherIndex++];
760 SmallVector<SDValue, 8> Ops;
761 for (unsigned i = 0; i != NumOps; ++i) {
762 unsigned RecNo = MatcherTable[MatcherIndex++];
764 RecNo = GetVBR(RecNo, MatcherTable, MatcherIndex);
766 assert(RecNo < RecordedNodes.size() && "Invalid EmitNode");
767 Ops.push_back(RecordedNodes[RecNo]);
770 // If there are variadic operands to add, handle them now.
771 if (EmitNodeInfo & OPFL_VariadicInfo) {
772 // Determine the start index to copy from.
773 unsigned FirstOpToCopy = getNumFixedFromVariadicInfo(EmitNodeInfo);
774 FirstOpToCopy += (EmitNodeInfo & OPFL_Chain) ? 1 : 0;
775 assert(NodeToMatch->getNumOperands() >= FirstOpToCopy &&
776 "Invalid variadic node");
777 // Copy all of the variadic operands, not including a potential flag
779 for (unsigned i = FirstOpToCopy, e = NodeToMatch->getNumOperands();
781 SDValue V = NodeToMatch->getOperand(i);
782 if (V.getValueType() == MVT::Flag) break;
787 // If this has chain/flag inputs, add them.
788 if (EmitNodeInfo & OPFL_Chain)
789 Ops.push_back(InputChain);
790 if ((EmitNodeInfo & OPFL_FlagInput) && InputFlag.getNode() != 0)
791 Ops.push_back(InputFlag);
795 if (Opcode != OPC_MorphNodeTo) {
796 // If this is a normal EmitNode command, just create the new node and
797 // add the results to the RecordedNodes list.
798 Res = CurDAG->getMachineNode(TargetOpc, NodeToMatch->getDebugLoc(),
799 VTList, Ops.data(), Ops.size());
801 // Add all the non-flag/non-chain results to the RecordedNodes list.
802 for (unsigned i = 0, e = VTs.size(); i != e; ++i) {
803 if (VTs[i] == MVT::Other || VTs[i] == MVT::Flag) break;
804 RecordedNodes.push_back(SDValue(Res, i));
808 // It is possible we're using MorphNodeTo to replace a node with no
809 // normal results with one that has a normal result (or we could be
810 // adding a chain) and the input could have flags and chains as well.
811 // In this case we need to shifting the operands down.
812 // FIXME: This is a horrible hack and broken in obscure cases, no worse
813 // than the old isel though. We should sink this into MorphNodeTo.
814 int OldFlagResultNo = -1, OldChainResultNo = -1;
816 unsigned NTMNumResults = NodeToMatch->getNumValues();
817 if (NodeToMatch->getValueType(NTMNumResults-1) == MVT::Flag) {
818 OldFlagResultNo = NTMNumResults-1;
819 if (NTMNumResults != 1 &&
820 NodeToMatch->getValueType(NTMNumResults-2) == MVT::Other)
821 OldChainResultNo = NTMNumResults-2;
822 } else if (NodeToMatch->getValueType(NTMNumResults-1) == MVT::Other)
823 OldChainResultNo = NTMNumResults-1;
825 Res = CurDAG->MorphNodeTo(NodeToMatch, ~TargetOpc, VTList,
826 Ops.data(), Ops.size());
828 // MorphNodeTo can operate in two ways: if an existing node with the
829 // specified operands exists, it can just return it. Otherwise, it
830 // updates the node in place to have the requested operands.
831 if (Res == NodeToMatch) {
832 // If we updated the node in place, reset the node ID. To the isel,
833 // this should be just like a newly allocated machine node.
837 unsigned ResNumResults = Res->getNumValues();
838 // Move the flag if needed.
839 if ((EmitNodeInfo & OPFL_FlagOutput) && OldFlagResultNo != -1 &&
840 (unsigned)OldFlagResultNo != ResNumResults-1)
841 ReplaceUses(SDValue(NodeToMatch, OldFlagResultNo),
842 SDValue(Res, ResNumResults-1));
844 if ((EmitNodeInfo & OPFL_FlagOutput) != 0)
847 // Move the chain reference if needed.
848 if ((EmitNodeInfo & OPFL_Chain) && OldChainResultNo != -1 &&
849 (unsigned)OldChainResultNo != ResNumResults-1)
850 ReplaceUses(SDValue(NodeToMatch, OldChainResultNo),
851 SDValue(Res, ResNumResults-1));
853 if (Res != NodeToMatch) {
854 // Otherwise, no replacement happened because the node already exists.
855 ReplaceUses(NodeToMatch, Res);
859 // If the node had chain/flag results, update our notion of the current
861 if (VTs.back() == MVT::Flag) {
862 InputFlag = SDValue(Res, VTs.size()-1);
863 if (EmitNodeInfo & OPFL_Chain)
864 InputChain = SDValue(Res, VTs.size()-2);
865 } else if (EmitNodeInfo & OPFL_Chain)
866 InputChain = SDValue(Res, VTs.size()-1);
868 // If the OPFL_MemRefs flag is set on this node, slap all of the
869 // accumulated memrefs onto it.
871 // FIXME: This is vastly incorrect for patterns with multiple outputs
872 // instructions that access memory and for ComplexPatterns that match
874 if (EmitNodeInfo & OPFL_MemRefs) {
875 MachineSDNode::mmo_iterator MemRefs =
876 MF->allocateMemRefsArray(MatchedMemRefs.size());
877 std::copy(MatchedMemRefs.begin(), MatchedMemRefs.end(), MemRefs);
878 cast<MachineSDNode>(Res)
879 ->setMemRefs(MemRefs, MemRefs + MatchedMemRefs.size());
883 << (Opcode == OPC_MorphNodeTo ? "Morphed" : "Created")
884 << " node: "; Res->dump(CurDAG); errs() << "\n");
886 // If this was a MorphNodeTo then we're completely done!
887 if (Opcode == OPC_MorphNodeTo) {
888 // Update chain and flag uses.
889 UpdateChainsAndFlags(NodeToMatch, InputChain, ChainNodesMatched,
890 InputFlag, FlagResultNodesMatched, true);
897 case OPC_MarkFlagResults: {
898 unsigned NumNodes = MatcherTable[MatcherIndex++];
900 // Read and remember all the flag-result nodes.
901 for (unsigned i = 0; i != NumNodes; ++i) {
902 unsigned RecNo = MatcherTable[MatcherIndex++];
904 RecNo = GetVBR(RecNo, MatcherTable, MatcherIndex);
906 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
907 FlagResultNodesMatched.push_back(RecordedNodes[RecNo].getNode());
912 case OPC_CompleteMatch: {
913 // The match has been completed, and any new nodes (if any) have been
914 // created. Patch up references to the matched dag to use the newly
916 unsigned NumResults = MatcherTable[MatcherIndex++];
918 for (unsigned i = 0; i != NumResults; ++i) {
919 unsigned ResSlot = MatcherTable[MatcherIndex++];
921 ResSlot = GetVBR(ResSlot, MatcherTable, MatcherIndex);
923 assert(ResSlot < RecordedNodes.size() && "Invalid CheckSame");
924 SDValue Res = RecordedNodes[ResSlot];
926 // FIXME2: Eliminate this horrible hack by fixing the 'Gen' program
927 // after (parallel) on input patterns are removed. This would also
928 // allow us to stop encoding #results in OPC_CompleteMatch's table
930 if (NodeToMatch->getNumValues() <= i ||
931 NodeToMatch->getValueType(i) == MVT::Other ||
932 NodeToMatch->getValueType(i) == MVT::Flag)
934 assert((NodeToMatch->getValueType(i) == Res.getValueType() ||
935 NodeToMatch->getValueType(i) == MVT::iPTR ||
936 Res.getValueType() == MVT::iPTR ||
937 NodeToMatch->getValueType(i).getSizeInBits() ==
938 Res.getValueType().getSizeInBits()) &&
939 "invalid replacement");
940 ReplaceUses(SDValue(NodeToMatch, i), Res);
943 // If the root node defines a flag, add it to the flag nodes to update
945 if (NodeToMatch->getValueType(NodeToMatch->getNumValues()-1) == MVT::Flag)
946 FlagResultNodesMatched.push_back(NodeToMatch);
948 // Update chain and flag uses.
949 UpdateChainsAndFlags(NodeToMatch, InputChain, ChainNodesMatched,
950 InputFlag, FlagResultNodesMatched, false);
952 assert(NodeToMatch->use_empty() &&
953 "Didn't replace all uses of the node?");
955 // FIXME: We just return here, which interacts correctly with SelectRoot
956 // above. We should fix this to not return an SDNode* anymore.
961 // If the code reached this point, then the match failed. See if there is
962 // another child to try in the current 'Scope', otherwise pop it until we
963 // find a case to check.
965 if (MatchScopes.empty()) {
966 CannotYetSelect(NodeToMatch);
970 // Restore the interpreter state back to the point where the scope was
972 MatchScope &LastScope = MatchScopes.back();
973 RecordedNodes.resize(LastScope.NumRecordedNodes);
975 NodeStack.append(LastScope.NodeStack.begin(), LastScope.NodeStack.end());
976 N = NodeStack.back();
978 DEBUG(errs() << " Match failed at index " << MatcherIndex
979 << " continuing at " << LastScope.FailIndex << "\n");
981 if (LastScope.NumMatchedMemRefs != MatchedMemRefs.size())
982 MatchedMemRefs.resize(LastScope.NumMatchedMemRefs);
983 MatcherIndex = LastScope.FailIndex;
985 InputChain = LastScope.InputChain;
986 InputFlag = LastScope.InputFlag;
987 if (!LastScope.HasChainNodesMatched)
988 ChainNodesMatched.clear();
989 if (!LastScope.HasFlagResultNodesMatched)
990 FlagResultNodesMatched.clear();
992 // Check to see what the offset is at the new MatcherIndex. If it is zero
993 // we have reached the end of this scope, otherwise we have another child
994 // in the current scope to try.
995 unsigned NumToSkip = MatcherTable[MatcherIndex++];
997 NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);
999 // If we have another child in this scope to match, update FailIndex and
1001 if (NumToSkip != 0) {
1002 LastScope.FailIndex = MatcherIndex+NumToSkip;
1006 // End of this scope, pop it and try the next child in the containing
1008 MatchScopes.pop_back();
1014 #endif /* LLVM_CODEGEN_DAGISEL_HEADER_H */