include/llvm/CodeGen/DAGISelHeader.h

   1 //==-llvm/CodeGen/DAGISelHeader.h - Common DAG ISel definitions  -*- C++ -*-==//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file provides definitions of the common, target-independent methods and
  11 // data, which is used by SelectionDAG-based instruction selectors.
  12 //
  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.
  18 //
  19 //===----------------------------------------------------------------------===//
  20
  21 #ifndef LLVM_CODEGEN_DAGISEL_HEADER_H
  22 #define LLVM_CODEGEN_DAGISEL_HEADER_H
  23
  24 /// ISelPosition - Node iterator marking the current position of
  25 /// instruction selection as it procedes through the topologically-sorted
  26 /// node list.
  27 SelectionDAG::allnodes_iterator ISelPosition;
  28
  29 /// ChainNotReachable - Returns true if Chain does not reach Op.
  30 static bool ChainNotReachable(SDNode *Chain, SDNode *Op) {
  31   if (Chain->getOpcode() == ISD::EntryToken)
  32     return true;
  33   if (Chain->getOpcode() == ISD::TokenFactor)
  34     return false;
  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);
  39   }
  40   return true;
  41 }
  42
  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);
  49 }
  50
  51
  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;
  56 public:
  57   explicit ISelUpdater(SelectionDAG::allnodes_iterator &isp)
  58     : ISelPosition(isp) {}
  59
  60   /// NodeDeleted - Handle nodes deleted from the graph. If the
  61   /// node being deleted is the current ISelPosition node, update
  62   /// ISelPosition.
  63   ///
  64   virtual void NodeDeleted(SDNode *N, SDNode *E) {
  65     if (ISelPosition == SelectionDAG::allnodes_iterator(N))
  66       ++ISelPosition;
  67   }
  68
  69   /// NodeUpdated - Ignore updates for now.
  70   virtual void NodeUpdated(SDNode *N) {}
  71 };
  72
  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);
  78 }
  79
  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,
  83                                 unsigned Num) {
  84   ISelUpdater ISU(ISelPosition);
  85   CurDAG->ReplaceAllUsesOfValuesWith(F, T, Num, &ISU);
  86 }
  87
  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);
  93 }
  94
  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) {
  98   SelectRootInit();
  99
 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());
 105   ++ISelPosition;
 106
 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
 110   // node).
 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())
 117       continue;
 118
 119     SDNode *ResNode = Select(Node);
 120     // If node should not be replaced, continue with the next one.
 121     if (ResNode == Node)
 122       continue;
 123     // Replace node.
 124     if (ResNode)
 125       ReplaceUses(Node, ResNode);
 126
 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);
 132     }
 133   }
 134
 135   CurDAG->setRoot(Dummy.getValue());
 136 }
 137
 138
 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;
 144 }
 145
 146 /// CheckAndImmediate - Check to see if the specified node is an and with an
 147 /// immediate returning true on failure.
 148 ///
 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))
 154         return false;
 155   return true;
 156 }
 157
 158 /// CheckOrImmediate - Check to see if the specified node is an or with an
 159 /// immediate returning true on failure.
 160 ///
 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))
 166         return false;
 167   return true;
 168 }
 169
 170 void EmitInteger(int64_t Val, MVT::SimpleValueType VT,
 171                  SmallVectorImpl<SDValue> &RecordedNodes) {
 172   RecordedNodes.push_back(CurDAG->getTargetConstant(Val, VT));
 173 }
 174
 175 // These functions are marked always inline so that Idx doesn't get pinned to
 176 // the stack.
 177 ALWAYS_INLINE static int8_t
 178 GetInt1(const unsigned char *MatcherTable, unsigned &Idx) {
 179   return MatcherTable[Idx++];
 180 }
 181
 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;
 186   return Val;
 187 }
 188
 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;
 193   return Val;
 194 }
 195
 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;
 200   return Val;
 201 }
 202
 203 enum BuiltinOpcodes {
 204   OPC_Push,
 205   OPC_RecordNode,
 206   OPC_RecordMemRef,
 207   OPC_CaptureFlagInput,
 208   OPC_MoveChild,
 209   OPC_MoveParent,
 210   OPC_CheckSame,
 211   OPC_CheckPatternPredicate,
 212   OPC_CheckPredicate,
 213   OPC_CheckOpcode,
 214   OPC_CheckType,
 215   OPC_CheckInteger1, OPC_CheckInteger2, OPC_CheckInteger4, OPC_CheckInteger8,
 216   OPC_CheckCondCode,
 217   OPC_CheckValueType,
 218   OPC_CheckComplexPat,
 219   OPC_CheckAndImm1, OPC_CheckAndImm2, OPC_CheckAndImm4, OPC_CheckAndImm8,
 220   OPC_CheckOrImm1, OPC_CheckOrImm2, OPC_CheckOrImm4, OPC_CheckOrImm8,
 221   OPC_CheckFoldableChainNode,
 222   OPC_CheckChainCompatible,
 223
 224   OPC_EmitInteger1, OPC_EmitInteger2, OPC_EmitInteger4, OPC_EmitInteger8,
 225   OPC_EmitRegister,
 226   OPC_EmitConvertToTarget,
 227   OPC_EmitMergeInputChains,
 228   OPC_EmitCopyToReg,
 229   OPC_EmitNodeXForm,
 230   OPC_EmitNode,
 231   OPC_CompleteMatch
 232 };
 233
 234 enum {
 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.
 246
 247   OPFL_VariadicInfo = OPFL_Variadic6
 248 };
 249
 250 /// getNumFixedFromVariadicInfo - Transform an EmitNode flags word into the
 251 /// number of fixed arity values that should be skipped when copying from the
 252 /// root.
 253 static inline int getNumFixedFromVariadicInfo(unsigned Flags) {
 254   return ((Flags&OPFL_VariadicInfo) >> 3)-1;
 255 }
 256
 257 struct MatchScope {
 258   /// FailIndex - If this match fails, this is the index to continue with.
 259   unsigned FailIndex;
 260
 261   /// NodeStackSize - The size of the node stack when the scope was formed.
 262   unsigned NodeStackSize;
 263
 264   /// NumRecordedNodes - The number of recorded nodes when the scope was formed.
 265   unsigned NumRecordedNodes;
 266
 267   /// NumMatchedMemRefs - The number of matched memref entries.
 268   unsigned NumMatchedMemRefs;
 269
 270   /// InputChain/InputFlag - The current chain/flag
 271   SDValue InputChain, InputFlag;
 272
 273   /// HasChainNodesMatched - True if the ChainNodesMatched list is non-empty.
 274   bool HasChainNodesMatched;
 275 };
 276
 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()) {
 281   default:
 282     break;
 283   case ISD::EntryToken:       // These nodes remain the same.
 284   case ISD::BasicBlock:
 285   case ISD::Register:
 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:
 298   case ISD::CopyToReg:
 299     return 0;
 300   case ISD::AssertSext:
 301   case ISD::AssertZext:
 302     ReplaceUses(SDValue(NodeToMatch, 0), NodeToMatch->getOperand(0));
 303     return 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);
 307   }
 308
 309   assert(!NodeToMatch->isMachineOpcode() && "Node already selected!");
 310
 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);
 315
 316   // MatchScopes - Scopes used when matching, if a match failure happens, this
 317   // indicates where to continue checking.
 318   SmallVector<MatchScope, 8> MatchScopes;
 319
 320   // RecordedNodes - This is the set of nodes that have been recorded by the
 321   // state machine.
 322   SmallVector<SDValue, 8> RecordedNodes;
 323
 324   // MatchedMemRefs - This is the set of MemRef's we've seen in the input
 325   // pattern.
 326   SmallVector<MachineMemOperand*, 2> MatchedMemRefs;
 327
 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;
 332
 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;
 338
 339   // Interpreter starts at opcode #0.
 340   unsigned MatcherIndex = 0;
 341   while (1) {
 342     assert(MatcherIndex < TableSize && "Invalid index");
 343     switch ((BuiltinOpcodes)MatcherTable[MatcherIndex++]) {
 344     case OPC_Push: {
 345       unsigned NumToSkip = MatcherTable[MatcherIndex++];
 346       MatchScope NewEntry;
 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);
 355       continue;
 356     }
 357     case OPC_RecordNode:
 358       // Remember this node, it may end up being an operand in the pattern.
 359       RecordedNodes.push_back(N);
 360       continue;
 361     case OPC_RecordMemRef:
 362       MatchedMemRefs.push_back(cast<MemSDNode>(N)->getMemOperand());
 363       continue;
 364
 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);
 370       continue;
 371
 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);
 378       continue;
 379     }
 380
 381     case OPC_MoveParent:
 382       // Pop the current node off the NodeStack.
 383       NodeStack.pop_back();
 384       assert(!NodeStack.empty() && "Node stack imbalance!");
 385       N = NodeStack.back();
 386       continue;
 387
 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;
 393       continue;
 394     }
 395     case OPC_CheckPatternPredicate:
 396       if (!CheckPatternPredicate(MatcherTable[MatcherIndex++])) break;
 397       continue;
 398     case OPC_CheckPredicate:
 399       if (!CheckNodePredicate(N.getNode(), MatcherTable[MatcherIndex++])) break;
 400       continue;
 401     case OPC_CheckComplexPat:
 402       if (!CheckComplexPattern(NodeToMatch, N,
 403                                MatcherTable[MatcherIndex++], RecordedNodes))
 404         break;
 405       continue;
 406     case OPC_CheckOpcode:
 407       if (N->getOpcode() != MatcherTable[MatcherIndex++]) break;
 408       continue;
 409     case OPC_CheckType:
 410       if (N.getValueType() !=
 411           (MVT::SimpleValueType)MatcherTable[MatcherIndex++]) break;
 412       continue;
 413     case OPC_CheckCondCode:
 414       if (cast<CondCodeSDNode>(N)->get() !=
 415           (ISD::CondCode)MatcherTable[MatcherIndex++]) break;
 416       continue;
 417     case OPC_CheckValueType:
 418       if (cast<VTSDNode>(N)->getVT() !=
 419           (MVT::SimpleValueType)MatcherTable[MatcherIndex++]) break;
 420       continue;
 421
 422     case OPC_CheckInteger1:
 423       if (CheckInteger(N, GetInt1(MatcherTable, MatcherIndex))) break;
 424       continue;
 425     case OPC_CheckInteger2:
 426       if (CheckInteger(N, GetInt2(MatcherTable, MatcherIndex))) break;
 427       continue;
 428     case OPC_CheckInteger4:
 429       if (CheckInteger(N, GetInt4(MatcherTable, MatcherIndex))) break;
 430       continue;
 431     case OPC_CheckInteger8:
 432       if (CheckInteger(N, GetInt8(MatcherTable, MatcherIndex))) break;
 433       continue;
 434
 435     case OPC_CheckAndImm1:
 436       if (CheckAndImmediate(N, GetInt1(MatcherTable, MatcherIndex))) break;
 437       continue;
 438     case OPC_CheckAndImm2:
 439       if (CheckAndImmediate(N, GetInt2(MatcherTable, MatcherIndex))) break;
 440       continue;
 441     case OPC_CheckAndImm4:
 442       if (CheckAndImmediate(N, GetInt4(MatcherTable, MatcherIndex))) break;
 443       continue;
 444     case OPC_CheckAndImm8:
 445       if (CheckAndImmediate(N, GetInt8(MatcherTable, MatcherIndex))) break;
 446       continue;
 447
 448     case OPC_CheckOrImm1:
 449       if (CheckOrImmediate(N, GetInt1(MatcherTable, MatcherIndex))) break;
 450       continue;
 451     case OPC_CheckOrImm2:
 452       if (CheckOrImmediate(N, GetInt2(MatcherTable, MatcherIndex))) break;
 453       continue;
 454     case OPC_CheckOrImm4:
 455       if (CheckOrImmediate(N, GetInt4(MatcherTable, MatcherIndex))) break;
 456       continue;
 457     case OPC_CheckOrImm8:
 458       if (CheckOrImmediate(N, GetInt8(MatcherTable, MatcherIndex))) break;
 459       continue;
 460
 461     case OPC_CheckFoldableChainNode: {
 462       assert(!NodeStack.size() == 1 && "No parent node");
 463       // Verify that all intermediate nodes between the root and this one have
 464       // a single use.
 465       bool HasMultipleUses = false;
 466       for (unsigned i = 1, e = NodeStack.size()-1; i != e; ++i)
 467         if (!NodeStack[i].hasOneUse()) {
 468           HasMultipleUses = true;
 469           break;
 470         }
 471       if (HasMultipleUses) break;
 472
 473       // Check to see that the target thinks this is profitable to fold and that
 474       // we can fold it without inducing cycles in the graph.
 475       if (!IsProfitableToFold(N, NodeStack[NodeStack.size()-2].getNode(),
 476                               NodeToMatch) ||
 477           !IsLegalToFold(N, NodeStack[NodeStack.size()-2].getNode(),
 478                          NodeToMatch))
 479         break;
 480
 481       continue;
 482     }
 483     case OPC_CheckChainCompatible: {
 484       unsigned PrevNode = MatcherTable[MatcherIndex++];
 485       assert(PrevNode < RecordedNodes.size() && "Invalid CheckChainCompatible");
 486       SDValue PrevChainedNode = RecordedNodes[PrevNode];
 487       SDValue ThisChainedNode = RecordedNodes.back();
 488
 489       // We have two nodes with chains, verify that their input chains are good.
 490       assert(PrevChainedNode.getOperand(0).getValueType() == MVT::Other &&
 491              ThisChainedNode.getOperand(0).getValueType() == MVT::Other &&
 492              "Invalid chained nodes");
 493
 494       if (!IsChainCompatible(// Input chain of the previous node.
 495                              PrevChainedNode.getOperand(0).getNode(),
 496                              // Node with chain.
 497                              ThisChainedNode.getNode()))
 498         break;
 499       continue;
 500     }
 501
 502     case OPC_EmitInteger1: {
 503       MVT::SimpleValueType VT =
 504         (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
 505       EmitInteger(GetInt1(MatcherTable, MatcherIndex), VT, RecordedNodes);
 506       continue;
 507     }
 508     case OPC_EmitInteger2: {
 509       MVT::SimpleValueType VT =
 510         (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
 511       EmitInteger(GetInt2(MatcherTable, MatcherIndex), VT, RecordedNodes);
 512       continue;
 513     }
 514     case OPC_EmitInteger4: {
 515       MVT::SimpleValueType VT =
 516         (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
 517       EmitInteger(GetInt4(MatcherTable, MatcherIndex), VT, RecordedNodes);
 518       continue;
 519     }
 520     case OPC_EmitInteger8: {
 521       MVT::SimpleValueType VT =
 522        (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
 523       EmitInteger(GetInt8(MatcherTable, MatcherIndex), VT, RecordedNodes);
 524       continue;
 525     }
 526
 527     case OPC_EmitRegister: {
 528       unsigned RegNo = MatcherTable[MatcherIndex++];
 529       MVT::SimpleValueType VT =
 530       (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
 531       SDValue Reg = CurDAG->getRegister(RegNo, VT);
 532       RecordedNodes.push_back(N);
 533       continue;
 534     }
 535
 536     case OPC_EmitConvertToTarget:  {
 537       // Convert from IMM/FPIMM to target version.
 538       unsigned RecNo = MatcherTable[MatcherIndex++];
 539       assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
 540       SDValue Imm = RecordedNodes[RecNo];
 541
 542       if (Imm->getOpcode() == ISD::Constant) {
 543         int64_t Val = cast<ConstantSDNode>(Imm)->getZExtValue();
 544         Imm = CurDAG->getTargetConstant(Val, Imm.getValueType());
 545       } else if (Imm->getOpcode() == ISD::ConstantFP) {
 546         const ConstantFP *Val=cast<ConstantFPSDNode>(Imm)->getConstantFPValue();
 547         Imm = CurDAG->getTargetConstantFP(*Val, Imm.getValueType());
 548       }
 549
 550       RecordedNodes.push_back(Imm);
 551       continue;
 552     }
 553
 554     case OPC_EmitMergeInputChains: {
 555       assert(InputChain.getNode() == 0 &&
 556              "EmitMergeInputChains should be the first chain producing node");
 557       // This node gets a list of nodes we matched in the input that have
 558       // chains.  We want to token factor all of the input chains to these nodes
 559       // together.  However, if any of the input chains is actually one of the
 560       // nodes matched in this pattern, then we have an intra-match reference.
 561       // Ignore these because the newly token factored chain should not refer to
 562       // the old nodes.
 563       unsigned NumChains = MatcherTable[MatcherIndex++];
 564       assert(NumChains != 0 && "Can't TF zero chains");
 565
 566       // The common case here is that we have exactly one chain, which is really
 567       // cheap to handle, just do it.
 568       if (NumChains == 1) {
 569         unsigned RecNo = MatcherTable[MatcherIndex++];
 570         assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
 571         ChainNodesMatched.push_back(RecordedNodes[RecNo].getNode());
 572         InputChain = RecordedNodes[RecNo].getOperand(0);
 573         assert(InputChain.getValueType() == MVT::Other && "Not a chain");
 574         continue;
 575       }
 576
 577       // Read all of the chained nodes.
 578       assert(ChainNodesMatched.empty() &&
 579              "Should only have one EmitMergeInputChains per match");
 580       for (unsigned i = 0; i != NumChains; ++i) {
 581         unsigned RecNo = MatcherTable[MatcherIndex++];
 582         assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
 583         ChainNodesMatched.push_back(RecordedNodes[RecNo].getNode());
 584       }
 585
 586       // Walk all the chained nodes, adding the input chains if they are not in
 587       // ChainedNodes (and this, not in the matched pattern).  This is an N^2
 588       // algorithm, but # chains is usually 2 here, at most 3 for MSP430.
 589       SmallVector<SDValue, 3> InputChains;
 590       for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
 591         SDValue InChain = ChainNodesMatched[i]->getOperand(0);
 592         assert(InChain.getValueType() == MVT::Other && "Not a chain");
 593         bool Invalid = false;
 594         for (unsigned j = 0; j != e; ++j)
 595           Invalid |= ChainNodesMatched[j] == InChain.getNode();
 596         if (!Invalid)
 597           InputChains.push_back(InChain);
 598       }
 599
 600       SDValue Res;
 601       if (InputChains.size() == 1)
 602         InputChain = InputChains[0];
 603       else
 604         InputChain = CurDAG->getNode(ISD::TokenFactor,
 605                                      NodeToMatch->getDebugLoc(), MVT::Other,
 606                                      &InputChains[0], InputChains.size());
 607       continue;
 608     }
 609
 610     case OPC_EmitCopyToReg: {
 611       unsigned RecNo = MatcherTable[MatcherIndex++];
 612       assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
 613       unsigned DestPhysReg = MatcherTable[MatcherIndex++];
 614
 615       if (InputChain.getNode() == 0)
 616         InputChain = CurDAG->getEntryNode();
 617
 618       InputChain = CurDAG->getCopyToReg(InputChain, NodeToMatch->getDebugLoc(),
 619                                         DestPhysReg, RecordedNodes[RecNo],
 620                                         InputFlag);
 621
 622       InputFlag = InputChain.getValue(1);
 623       continue;
 624     }
 625
 626     case OPC_EmitNodeXForm: {
 627       unsigned XFormNo = MatcherTable[MatcherIndex++];
 628       unsigned RecNo = MatcherTable[MatcherIndex++];
 629       assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
 630       RecordedNodes.push_back(RunSDNodeXForm(RecordedNodes[RecNo], XFormNo));
 631       continue;
 632     }
 633
 634     case OPC_EmitNode: {
 635       uint16_t TargetOpc = GetInt2(MatcherTable, MatcherIndex);
 636       unsigned EmitNodeInfo = MatcherTable[MatcherIndex++];
 637       // Get the result VT list.
 638       unsigned NumVTs = MatcherTable[MatcherIndex++];
 639       assert(NumVTs != 0 && "Invalid node result");
 640       SmallVector<EVT, 4> VTs;
 641       for (unsigned i = 0; i != NumVTs; ++i)
 642         VTs.push_back((MVT::SimpleValueType)MatcherTable[MatcherIndex++]);
 643       SDVTList VTList = CurDAG->getVTList(VTs.data(), VTs.size());
 644
 645       // Get the operand list.
 646       unsigned NumOps = MatcherTable[MatcherIndex++];
 647       SmallVector<SDValue, 8> Ops;
 648       for (unsigned i = 0; i != NumOps; ++i) {
 649         unsigned RecNo = MatcherTable[MatcherIndex++];
 650         assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
 651         Ops.push_back(RecordedNodes[RecNo]);
 652       }
 653
 654       // If there are variadic operands to add, handle them now.
 655       if (EmitNodeInfo & OPFL_VariadicInfo) {
 656         // Determine the start index to copy from.
 657         unsigned FirstOpToCopy = getNumFixedFromVariadicInfo(EmitNodeInfo);
 658         FirstOpToCopy += (EmitNodeInfo & OPFL_Chain) ? 1 : 0;
 659         assert(NodeToMatch->getNumOperands() >= FirstOpToCopy &&
 660                "Invalid variadic node");
 661         // Copy all of the variadic operands, not including a potential flag
 662         // input.
 663         for (unsigned i = FirstOpToCopy, e = NodeToMatch->getNumOperands();
 664              i != e; ++i) {
 665           SDValue V = NodeToMatch->getOperand(i);
 666           if (V.getValueType() == MVT::Flag) break;
 667           Ops.push_back(V);
 668         }
 669       }
 670
 671       // If this has chain/flag inputs, add them.
 672       if (EmitNodeInfo & OPFL_Chain)
 673         Ops.push_back(InputChain);
 674       if (EmitNodeInfo & OPFL_Flag)
 675         Ops.push_back(InputFlag);
 676
 677       // Create the node.
 678       MachineSDNode *Res = CurDAG->getMachineNode(TargetOpc,
 679                                                   NodeToMatch->getDebugLoc(),
 680                                                   VTList,
 681                                                   Ops.data(), Ops.size());
 682       RecordedNodes.push_back(SDValue(Res, 0));
 683
 684       // If the node had chain/flag results, update our notion of the current
 685       // chain and flag.
 686       if (VTs.back() == MVT::Flag) {
 687         InputFlag = SDValue(Res, VTs.size()-1);
 688         if (EmitNodeInfo & OPFL_Chain)
 689           InputChain = SDValue(Res, VTs.size()-2);
 690       } else if (EmitNodeInfo & OPFL_Chain)
 691         InputChain = SDValue(Res, VTs.size()-1);
 692
 693       // If the OPFL_MemRefs flag is set on this node, slap all of the
 694       // accumulated memrefs onto it.
 695       //
 696       // FIXME: This is vastly incorrect for patterns with multiple outputs
 697       // instructions that access memory and for ComplexPatterns that match
 698       // loads.
 699       if (EmitNodeInfo & OPFL_MemRefs) {
 700         MachineSDNode::mmo_iterator MemRefs =
 701           MF->allocateMemRefsArray(MatchedMemRefs.size());
 702         std::copy(MatchedMemRefs.begin(), MatchedMemRefs.end(), MemRefs);
 703         Res->setMemRefs(MemRefs, MemRefs + MatchedMemRefs.size());
 704       }
 705       continue;
 706     }
 707
 708     case OPC_CompleteMatch: {
 709       // The match has been completed, and any new nodes (if any) have been
 710       // created.  Patch up references to the matched dag to use the newly
 711       // created nodes.
 712       unsigned NumResults = MatcherTable[MatcherIndex++];
 713
 714       for (unsigned i = 0; i != NumResults; ++i) {
 715         unsigned ResSlot = MatcherTable[MatcherIndex++];
 716         assert(ResSlot < RecordedNodes.size() && "Invalid CheckSame");
 717         SDValue Res = RecordedNodes[ResSlot];
 718         assert(NodeToMatch->getValueType(i) == Res.getValueType() &&
 719                "invalid replacement");
 720         ReplaceUses(SDValue(NodeToMatch, i), Res);
 721       }
 722
 723       // Now that all the normal results are replaced, we replace the chain and
 724       // flag results if present.
 725       if (!ChainNodesMatched.empty()) {
 726         assert(InputChain.getNode() != 0 &&
 727                "Matched input chains but didn't produce a chain");
 728         // Loop over all of the nodes we matched that produced a chain result.
 729         // Replace all the chain results with the final chain we ended up with.
 730         for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
 731           SDNode *ChainNode = ChainNodesMatched[i];
 732           SDValue ChainVal = SDValue(ChainNode, ChainNode->getNumValues()-1);
 733           if (ChainVal.getValueType() == MVT::Flag)
 734             ChainVal = ChainVal.getValue(ChainVal->getNumValues()-2);
 735           assert(ChainVal.getValueType() == MVT::Other && "Not a chain?");
 736           ReplaceUses(ChainVal, InputChain);
 737         }
 738       }
 739       // If the root node produces a flag, make sure to replace its flag
 740       // result with the resultant flag.
 741       if (NodeToMatch->getValueType(NodeToMatch->getNumValues()-1) ==
 742             MVT::Flag)
 743         ReplaceUses(SDValue(NodeToMatch, NodeToMatch->getNumValues()-1),
 744                     InputFlag);
 745
 746       // FIXME: We just return here, which interacts correctly with SelectRoot
 747       // above.  We should fix this to not return an SDNode* anymore.
 748       return 0;
 749     }
 750     }
 751
 752     // If the code reached this point, then the match failed pop out to the next
 753     // match scope.
 754     if (MatchScopes.empty()) {
 755       CannotYetSelect(NodeToMatch);
 756       return 0;
 757     }
 758
 759     const MatchScope &LastScope = MatchScopes.back();
 760     RecordedNodes.resize(LastScope.NumRecordedNodes);
 761     NodeStack.resize(LastScope.NodeStackSize);
 762
 763     if (LastScope.NumMatchedMemRefs != MatchedMemRefs.size())
 764       MatchedMemRefs.resize(LastScope.NumMatchedMemRefs);
 765     MatcherIndex = LastScope.FailIndex;
 766
 767     InputChain = LastScope.InputChain;
 768     InputFlag = LastScope.InputFlag;
 769     if (!LastScope.HasChainNodesMatched)
 770       ChainNodesMatched.clear();
 771
 772     MatchScopes.pop_back();
 773   }
 774 }
 775
 776
 777 #endif /* LLVM_CODEGEN_DAGISEL_HEADER_H */