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 /// 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.
 208
 209   unsigned Shift = 7;
 210   unsigned NextBits;
 211   do {
 212     NextBits = GetInt1(MatcherTable, Idx);
 213     Val |= (NextBits&127) << Shift;
 214     Shift += 7;
 215   } while (NextBits & 128);
 216
 217   return Val;
 218 }
 219
 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,
 224                           SDValue InputFlag,
 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];
 236
 237       // Don't replace the results of the root node if we're doing a
 238       // MorphNodeTo.
 239       if (ChainNode == NodeToMatch && isMorphNodeTo)
 240         continue;
 241
 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);
 247     }
 248   }
 249
 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);
 259     }
 260   }
 261
 262   DEBUG(errs() << "ISEL: Match complete!\n");
 263 }
 264
 265
 266 enum BuiltinOpcodes {
 267   OPC_Scope,
 268   OPC_RecordNode,
 269   OPC_RecordChild0, OPC_RecordChild1, OPC_RecordChild2, OPC_RecordChild3,
 270   OPC_RecordChild4, OPC_RecordChild5, OPC_RecordChild6, OPC_RecordChild7,
 271   OPC_RecordMemRef,
 272   OPC_CaptureFlagInput,
 273   OPC_MoveChild,
 274   OPC_MoveParent,
 275   OPC_CheckSame,
 276   OPC_CheckPatternPredicate,
 277   OPC_CheckPredicate,
 278   OPC_CheckOpcode,
 279   OPC_CheckMultiOpcode,
 280   OPC_CheckType,
 281   OPC_CheckChild0Type, OPC_CheckChild1Type, OPC_CheckChild2Type,
 282   OPC_CheckChild3Type, OPC_CheckChild4Type, OPC_CheckChild5Type,
 283   OPC_CheckChild6Type, OPC_CheckChild7Type,
 284   OPC_CheckInteger1, OPC_CheckInteger2, OPC_CheckInteger4, OPC_CheckInteger8,
 285   OPC_CheckCondCode,
 286   OPC_CheckValueType,
 287   OPC_CheckComplexPat,
 288   OPC_CheckAndImm1, OPC_CheckAndImm2, OPC_CheckAndImm4, OPC_CheckAndImm8,
 289   OPC_CheckOrImm1, OPC_CheckOrImm2, OPC_CheckOrImm4, OPC_CheckOrImm8,
 290   OPC_CheckFoldableChainNode,
 291   OPC_CheckChainCompatible,
 292
 293   OPC_EmitInteger1, OPC_EmitInteger2, OPC_EmitInteger4, OPC_EmitInteger8,
 294   OPC_EmitRegister,
 295   OPC_EmitConvertToTarget,
 296   OPC_EmitMergeInputChains,
 297   OPC_EmitCopyToReg,
 298   OPC_EmitNodeXForm,
 299   OPC_EmitNode,
 300   OPC_MorphNodeTo,
 301   OPC_MarkFlagResults,
 302   OPC_CompleteMatch
 303 };
 304
 305 enum {
 306   OPFL_None       = 0,     // Node has no chain or flag input and isn't variadic.
 307   OPFL_Chain      = 1,     // Node has a chain input.
 308   OPFL_FlagInput  = 2,     // Node has a flag input.
 309   OPFL_FlagOutput = 4,     // Node has a flag output.
 310   OPFL_MemRefs    = 8,     // Node gets accumulated MemRefs.
 311   OPFL_Variadic0  = 1<<4,  // Node is variadic, root has 0 fixed inputs.
 312   OPFL_Variadic1  = 2<<4,  // Node is variadic, root has 1 fixed inputs.
 313   OPFL_Variadic2  = 3<<4,  // Node is variadic, root has 2 fixed inputs.
 314   OPFL_Variadic3  = 4<<4,  // Node is variadic, root has 3 fixed inputs.
 315   OPFL_Variadic4  = 5<<4,  // Node is variadic, root has 4 fixed inputs.
 316   OPFL_Variadic5  = 6<<4,  // Node is variadic, root has 5 fixed inputs.
 317   OPFL_Variadic6  = 7<<4,  // Node is variadic, root has 6 fixed inputs.
 318
 319   OPFL_VariadicInfo = OPFL_Variadic6
 320 };
 321
 322 /// getNumFixedFromVariadicInfo - Transform an EmitNode flags word into the
 323 /// number of fixed arity values that should be skipped when copying from the
 324 /// root.
 325 static inline int getNumFixedFromVariadicInfo(unsigned Flags) {
 326   return ((Flags&OPFL_VariadicInfo) >> 4)-1;
 327 }
 328
 329 struct MatchScope {
 330   /// FailIndex - If this match fails, this is the index to continue with.
 331   unsigned FailIndex;
 332
 333   /// NodeStack - The node stack when the scope was formed.
 334   SmallVector<SDValue, 4> NodeStack;
 335
 336   /// NumRecordedNodes - The number of recorded nodes when the scope was formed.
 337   unsigned NumRecordedNodes;
 338
 339   /// NumMatchedMemRefs - The number of matched memref entries.
 340   unsigned NumMatchedMemRefs;
 341
 342   /// InputChain/InputFlag - The current chain/flag
 343   SDValue InputChain, InputFlag;
 344
 345   /// HasChainNodesMatched - True if the ChainNodesMatched list is non-empty.
 346   bool HasChainNodesMatched, HasFlagResultNodesMatched;
 347 };
 348
 349 SDNode *SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable,
 350                          unsigned TableSize) {
 351   // FIXME: Should these even be selected?  Handle these cases in the caller?
 352   switch (NodeToMatch->getOpcode()) {
 353   default:
 354     break;
 355   case ISD::EntryToken:       // These nodes remain the same.
 356   case ISD::BasicBlock:
 357   case ISD::Register:
 358   case ISD::HANDLENODE:
 359   case ISD::TargetConstant:
 360   case ISD::TargetConstantFP:
 361   case ISD::TargetConstantPool:
 362   case ISD::TargetFrameIndex:
 363   case ISD::TargetExternalSymbol:
 364   case ISD::TargetBlockAddress:
 365   case ISD::TargetJumpTable:
 366   case ISD::TargetGlobalTLSAddress:
 367   case ISD::TargetGlobalAddress:
 368   case ISD::TokenFactor:
 369   case ISD::CopyFromReg:
 370   case ISD::CopyToReg:
 371     return 0;
 372   case ISD::AssertSext:
 373   case ISD::AssertZext:
 374     ReplaceUses(SDValue(NodeToMatch, 0), NodeToMatch->getOperand(0));
 375     return 0;
 376   case ISD::INLINEASM: return Select_INLINEASM(NodeToMatch);
 377   case ISD::EH_LABEL:  return Select_EH_LABEL(NodeToMatch);
 378   case ISD::UNDEF:     return Select_UNDEF(NodeToMatch);
 379   }
 380
 381   assert(!NodeToMatch->isMachineOpcode() && "Node already selected!");
 382
 383   // Set up the node stack with NodeToMatch as the only node on the stack.
 384   SmallVector<SDValue, 8> NodeStack;
 385   SDValue N = SDValue(NodeToMatch, 0);
 386   NodeStack.push_back(N);
 387
 388   // MatchScopes - Scopes used when matching, if a match failure happens, this
 389   // indicates where to continue checking.
 390   SmallVector<MatchScope, 8> MatchScopes;
 391
 392   // RecordedNodes - This is the set of nodes that have been recorded by the
 393   // state machine.
 394   SmallVector<SDValue, 8> RecordedNodes;
 395
 396   // MatchedMemRefs - This is the set of MemRef's we've seen in the input
 397   // pattern.
 398   SmallVector<MachineMemOperand*, 2> MatchedMemRefs;
 399
 400   // These are the current input chain and flag for use when generating nodes.
 401   // Various Emit operations change these.  For example, emitting a copytoreg
 402   // uses and updates these.
 403   SDValue InputChain, InputFlag;
 404
 405   // ChainNodesMatched - If a pattern matches nodes that have input/output
 406   // chains, the OPC_EmitMergeInputChains operation is emitted which indicates
 407   // which ones they are.  The result is captured into this list so that we can
 408   // update the chain results when the pattern is complete.
 409   SmallVector<SDNode*, 3> ChainNodesMatched;
 410   SmallVector<SDNode*, 3> FlagResultNodesMatched;
 411
 412   DEBUG(errs() << "ISEL: Starting pattern match on root node: ";
 413         NodeToMatch->dump(CurDAG);
 414         errs() << '\n');
 415
 416   // Interpreter starts at opcode #0.
 417   unsigned MatcherIndex = 0;
 418   while (1) {
 419     assert(MatcherIndex < TableSize && "Invalid index");
 420     BuiltinOpcodes Opcode = (BuiltinOpcodes)MatcherTable[MatcherIndex++];
 421     switch (Opcode) {
 422     case OPC_Scope: {
 423       unsigned NumToSkip = MatcherTable[MatcherIndex++];
 424       if (NumToSkip & 128)
 425         NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);
 426       assert(NumToSkip != 0 &&
 427              "First entry of OPC_Scope shouldn't be 0, scope has no children?");
 428
 429       // Push a MatchScope which indicates where to go if the first child fails
 430       // to match.
 431       MatchScope NewEntry;
 432       NewEntry.FailIndex = MatcherIndex+NumToSkip;
 433       NewEntry.NodeStack.append(NodeStack.begin(), NodeStack.end());
 434       NewEntry.NumRecordedNodes = RecordedNodes.size();
 435       NewEntry.NumMatchedMemRefs = MatchedMemRefs.size();
 436       NewEntry.InputChain = InputChain;
 437       NewEntry.InputFlag = InputFlag;
 438       NewEntry.HasChainNodesMatched = !ChainNodesMatched.empty();
 439       NewEntry.HasFlagResultNodesMatched = !FlagResultNodesMatched.empty();
 440       MatchScopes.push_back(NewEntry);
 441       continue;
 442     }
 443     case OPC_RecordNode:
 444       // Remember this node, it may end up being an operand in the pattern.
 445       RecordedNodes.push_back(N);
 446       continue;
 447
 448     case OPC_RecordChild0: case OPC_RecordChild1:
 449     case OPC_RecordChild2: case OPC_RecordChild3:
 450     case OPC_RecordChild4: case OPC_RecordChild5:
 451     case OPC_RecordChild6: case OPC_RecordChild7: {
 452       unsigned ChildNo = Opcode-OPC_RecordChild0;
 453       if (ChildNo >= N.getNumOperands())
 454         break;  // Match fails if out of range child #.
 455
 456       RecordedNodes.push_back(N->getOperand(ChildNo));
 457       continue;
 458     }
 459     case OPC_RecordMemRef:
 460       MatchedMemRefs.push_back(cast<MemSDNode>(N)->getMemOperand());
 461       continue;
 462
 463     case OPC_CaptureFlagInput:
 464       // If the current node has an input flag, capture it in InputFlag.
 465       if (N->getNumOperands() != 0 &&
 466           N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag)
 467         InputFlag = N->getOperand(N->getNumOperands()-1);
 468       continue;
 469
 470     case OPC_MoveChild: {
 471       unsigned ChildNo = MatcherTable[MatcherIndex++];
 472       if (ChildNo >= N.getNumOperands())
 473         break;  // Match fails if out of range child #.
 474       N = N.getOperand(ChildNo);
 475       NodeStack.push_back(N);
 476       continue;
 477     }
 478
 479     case OPC_MoveParent:
 480       // Pop the current node off the NodeStack.
 481       NodeStack.pop_back();
 482       assert(!NodeStack.empty() && "Node stack imbalance!");
 483       N = NodeStack.back();
 484       continue;
 485
 486     case OPC_CheckSame: {
 487       // Accept if it is exactly the same as a previously recorded node.
 488       unsigned RecNo = MatcherTable[MatcherIndex++];
 489       assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
 490       if (N != RecordedNodes[RecNo]) break;
 491       continue;
 492     }
 493     case OPC_CheckPatternPredicate:
 494       if (!CheckPatternPredicate(MatcherTable[MatcherIndex++])) break;
 495       continue;
 496     case OPC_CheckPredicate:
 497       if (!CheckNodePredicate(N.getNode(), MatcherTable[MatcherIndex++])) break;
 498       continue;
 499     case OPC_CheckComplexPat:
 500       if (!CheckComplexPattern(NodeToMatch, N,
 501                                MatcherTable[MatcherIndex++], RecordedNodes))
 502         break;
 503       continue;
 504     case OPC_CheckOpcode:
 505       if (N->getOpcode() != MatcherTable[MatcherIndex++]) break;
 506       continue;
 507
 508     case OPC_CheckMultiOpcode: {
 509       unsigned NumOps = MatcherTable[MatcherIndex++];
 510       bool OpcodeEquals = false;
 511       for (unsigned i = 0; i != NumOps; ++i)
 512         OpcodeEquals |= N->getOpcode() == MatcherTable[MatcherIndex++];
 513       if (!OpcodeEquals) break;
 514       continue;
 515     }
 516
 517     case OPC_CheckType: {
 518       MVT::SimpleValueType VT =
 519         (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
 520       if (N.getValueType() != VT) {
 521         // Handle the case when VT is iPTR.
 522         if (VT != MVT::iPTR || N.getValueType() != TLI.getPointerTy())
 523           break;
 524       }
 525       continue;
 526     }
 527     case OPC_CheckChild0Type: case OPC_CheckChild1Type:
 528     case OPC_CheckChild2Type: case OPC_CheckChild3Type:
 529     case OPC_CheckChild4Type: case OPC_CheckChild5Type:
 530     case OPC_CheckChild6Type: case OPC_CheckChild7Type: {
 531       unsigned ChildNo = Opcode-OPC_CheckChild0Type;
 532       if (ChildNo >= N.getNumOperands())
 533         break;  // Match fails if out of range child #.
 534
 535       MVT::SimpleValueType VT =
 536         (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
 537       EVT ChildVT = N.getOperand(ChildNo).getValueType();
 538       if (ChildVT != VT) {
 539         // Handle the case when VT is iPTR.
 540         if (VT != MVT::iPTR || ChildVT != TLI.getPointerTy())
 541           break;
 542       }
 543       continue;
 544     }
 545     case OPC_CheckCondCode:
 546       if (cast<CondCodeSDNode>(N)->get() !=
 547           (ISD::CondCode)MatcherTable[MatcherIndex++]) break;
 548       continue;
 549     case OPC_CheckValueType: {
 550       MVT::SimpleValueType VT =
 551         (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
 552       if (cast<VTSDNode>(N)->getVT() != VT) {
 553         // Handle the case when VT is iPTR.
 554         if (VT != MVT::iPTR || cast<VTSDNode>(N)->getVT() != TLI.getPointerTy())
 555           break;
 556       }
 557       continue;
 558     }
 559     case OPC_CheckInteger1:
 560       if (CheckInteger(N, GetInt1(MatcherTable, MatcherIndex))) break;
 561       continue;
 562     case OPC_CheckInteger2:
 563       if (CheckInteger(N, GetInt2(MatcherTable, MatcherIndex))) break;
 564       continue;
 565     case OPC_CheckInteger4:
 566       if (CheckInteger(N, GetInt4(MatcherTable, MatcherIndex))) break;
 567       continue;
 568     case OPC_CheckInteger8:
 569       if (CheckInteger(N, GetInt8(MatcherTable, MatcherIndex))) break;
 570       continue;
 571
 572     case OPC_CheckAndImm1:
 573       if (CheckAndImmediate(N, GetInt1(MatcherTable, MatcherIndex))) break;
 574       continue;
 575     case OPC_CheckAndImm2:
 576       if (CheckAndImmediate(N, GetInt2(MatcherTable, MatcherIndex))) break;
 577       continue;
 578     case OPC_CheckAndImm4:
 579       if (CheckAndImmediate(N, GetInt4(MatcherTable, MatcherIndex))) break;
 580       continue;
 581     case OPC_CheckAndImm8:
 582       if (CheckAndImmediate(N, GetInt8(MatcherTable, MatcherIndex))) break;
 583       continue;
 584
 585     case OPC_CheckOrImm1:
 586       if (CheckOrImmediate(N, GetInt1(MatcherTable, MatcherIndex))) break;
 587       continue;
 588     case OPC_CheckOrImm2:
 589       if (CheckOrImmediate(N, GetInt2(MatcherTable, MatcherIndex))) break;
 590       continue;
 591     case OPC_CheckOrImm4:
 592       if (CheckOrImmediate(N, GetInt4(MatcherTable, MatcherIndex))) break;
 593       continue;
 594     case OPC_CheckOrImm8:
 595       if (CheckOrImmediate(N, GetInt8(MatcherTable, MatcherIndex))) break;
 596       continue;
 597
 598     case OPC_CheckFoldableChainNode: {
 599       assert(NodeStack.size() != 1 && "No parent node");
 600       // Verify that all intermediate nodes between the root and this one have
 601       // a single use.
 602       bool HasMultipleUses = false;
 603       for (unsigned i = 1, e = NodeStack.size()-1; i != e; ++i)
 604         if (!NodeStack[i].hasOneUse()) {
 605           HasMultipleUses = true;
 606           break;
 607         }
 608       if (HasMultipleUses) break;
 609
 610       // Check to see that the target thinks this is profitable to fold and that
 611       // we can fold it without inducing cycles in the graph.
 612       if (!IsProfitableToFold(N, NodeStack[NodeStack.size()-2].getNode(),
 613                               NodeToMatch) ||
 614           !IsLegalToFold(N, NodeStack[NodeStack.size()-2].getNode(),
 615                          NodeToMatch))
 616         break;
 617
 618       continue;
 619     }
 620     case OPC_CheckChainCompatible: {
 621       unsigned PrevNode = MatcherTable[MatcherIndex++];
 622       assert(PrevNode < RecordedNodes.size() && "Invalid CheckChainCompatible");
 623       SDValue PrevChainedNode = RecordedNodes[PrevNode];
 624       SDValue ThisChainedNode = RecordedNodes.back();
 625
 626       // We have two nodes with chains, verify that their input chains are good.
 627       assert(PrevChainedNode.getOperand(0).getValueType() == MVT::Other &&
 628              ThisChainedNode.getOperand(0).getValueType() == MVT::Other &&
 629              "Invalid chained nodes");
 630
 631       if (!IsChainCompatible(// Input chain of the previous node.
 632                              PrevChainedNode.getOperand(0).getNode(),
 633                              // Node with chain.
 634                              ThisChainedNode.getNode()))
 635         break;
 636       continue;
 637     }
 638
 639     case OPC_EmitInteger1: {
 640       MVT::SimpleValueType VT =
 641         (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
 642       EmitInteger(GetInt1(MatcherTable, MatcherIndex), VT, RecordedNodes);
 643       continue;
 644     }
 645     case OPC_EmitInteger2: {
 646       MVT::SimpleValueType VT =
 647         (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
 648       EmitInteger(GetInt2(MatcherTable, MatcherIndex), VT, RecordedNodes);
 649       continue;
 650     }
 651     case OPC_EmitInteger4: {
 652       MVT::SimpleValueType VT =
 653         (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
 654       EmitInteger(GetInt4(MatcherTable, MatcherIndex), VT, RecordedNodes);
 655       continue;
 656     }
 657     case OPC_EmitInteger8: {
 658       MVT::SimpleValueType VT =
 659        (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
 660       EmitInteger(GetInt8(MatcherTable, MatcherIndex), VT, RecordedNodes);
 661       continue;
 662     }
 663
 664     case OPC_EmitRegister: {
 665       MVT::SimpleValueType VT =
 666         (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
 667       unsigned RegNo = MatcherTable[MatcherIndex++];
 668       RecordedNodes.push_back(CurDAG->getRegister(RegNo, VT));
 669       continue;
 670     }
 671
 672     case OPC_EmitConvertToTarget:  {
 673       // Convert from IMM/FPIMM to target version.
 674       unsigned RecNo = MatcherTable[MatcherIndex++];
 675       assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
 676       SDValue Imm = RecordedNodes[RecNo];
 677
 678       if (Imm->getOpcode() == ISD::Constant) {
 679         int64_t Val = cast<ConstantSDNode>(Imm)->getZExtValue();
 680         Imm = CurDAG->getTargetConstant(Val, Imm.getValueType());
 681       } else if (Imm->getOpcode() == ISD::ConstantFP) {
 682         const ConstantFP *Val=cast<ConstantFPSDNode>(Imm)->getConstantFPValue();
 683         Imm = CurDAG->getTargetConstantFP(*Val, Imm.getValueType());
 684       }
 685
 686       RecordedNodes.push_back(Imm);
 687       continue;
 688     }
 689
 690     case OPC_EmitMergeInputChains: {
 691       assert(InputChain.getNode() == 0 &&
 692              "EmitMergeInputChains should be the first chain producing node");
 693       // This node gets a list of nodes we matched in the input that have
 694       // chains.  We want to token factor all of the input chains to these nodes
 695       // together.  However, if any of the input chains is actually one of the
 696       // nodes matched in this pattern, then we have an intra-match reference.
 697       // Ignore these because the newly token factored chain should not refer to
 698       // the old nodes.
 699       unsigned NumChains = MatcherTable[MatcherIndex++];
 700       assert(NumChains != 0 && "Can't TF zero chains");
 701
 702       assert(ChainNodesMatched.empty() &&
 703              "Should only have one EmitMergeInputChains per match");
 704
 705       // Handle the first chain.
 706       unsigned RecNo = MatcherTable[MatcherIndex++];
 707       assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
 708       ChainNodesMatched.push_back(RecordedNodes[RecNo].getNode());
 709
 710       // If the chained node is not the root, we can't fold it if it has
 711       // multiple uses.
 712       // FIXME: What if other value results of the node have uses not matched by
 713       // this pattern?
 714       if (ChainNodesMatched.back() != NodeToMatch &&
 715           !RecordedNodes[RecNo].hasOneUse()) {
 716         ChainNodesMatched.clear();
 717         break;
 718       }
 719
 720       // The common case here is that we have exactly one chain, which is really
 721       // cheap to handle, just do it.
 722       if (NumChains == 1) {
 723         InputChain = RecordedNodes[RecNo].getOperand(0);
 724         assert(InputChain.getValueType() == MVT::Other && "Not a chain");
 725         continue;
 726       }
 727
 728       // Read all of the chained nodes.
 729       for (unsigned i = 1; i != NumChains; ++i) {
 730         RecNo = MatcherTable[MatcherIndex++];
 731         assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
 732         ChainNodesMatched.push_back(RecordedNodes[RecNo].getNode());
 733
 734         // FIXME: What if other value results of the node have uses not matched by
 735         // this pattern?
 736         if (ChainNodesMatched.back() != NodeToMatch &&
 737             !RecordedNodes[RecNo].hasOneUse()) {
 738           ChainNodesMatched.clear();
 739           break;
 740         }
 741       }
 742
 743       // Walk all the chained nodes, adding the input chains if they are not in
 744       // ChainedNodes (and this, not in the matched pattern).  This is an N^2
 745       // algorithm, but # chains is usually 2 here, at most 3 for MSP430.
 746       SmallVector<SDValue, 3> InputChains;
 747       for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
 748         SDValue InChain = ChainNodesMatched[i]->getOperand(0);
 749         assert(InChain.getValueType() == MVT::Other && "Not a chain");
 750         bool Invalid = false;
 751         for (unsigned j = 0; j != e; ++j)
 752           Invalid |= ChainNodesMatched[j] == InChain.getNode();
 753         if (!Invalid)
 754           InputChains.push_back(InChain);
 755       }
 756
 757       SDValue Res;
 758       if (InputChains.size() == 1)
 759         InputChain = InputChains[0];
 760       else
 761         InputChain = CurDAG->getNode(ISD::TokenFactor,
 762                                      NodeToMatch->getDebugLoc(), MVT::Other,
 763                                      &InputChains[0], InputChains.size());
 764       continue;
 765     }
 766
 767     case OPC_EmitCopyToReg: {
 768       unsigned RecNo = MatcherTable[MatcherIndex++];
 769       assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
 770       unsigned DestPhysReg = MatcherTable[MatcherIndex++];
 771
 772       if (InputChain.getNode() == 0)
 773         InputChain = CurDAG->getEntryNode();
 774
 775       InputChain = CurDAG->getCopyToReg(InputChain, NodeToMatch->getDebugLoc(),
 776                                         DestPhysReg, RecordedNodes[RecNo],
 777                                         InputFlag);
 778
 779       InputFlag = InputChain.getValue(1);
 780       continue;
 781     }
 782
 783     case OPC_EmitNodeXForm: {
 784       unsigned XFormNo = MatcherTable[MatcherIndex++];
 785       unsigned RecNo = MatcherTable[MatcherIndex++];
 786       assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
 787       RecordedNodes.push_back(RunSDNodeXForm(RecordedNodes[RecNo], XFormNo));
 788       continue;
 789     }
 790
 791     case OPC_EmitNode:
 792     case OPC_MorphNodeTo: {
 793       uint16_t TargetOpc = GetInt2(MatcherTable, MatcherIndex);
 794       unsigned EmitNodeInfo = MatcherTable[MatcherIndex++];
 795       // Get the result VT list.
 796       unsigned NumVTs = MatcherTable[MatcherIndex++];
 797       SmallVector<EVT, 4> VTs;
 798       for (unsigned i = 0; i != NumVTs; ++i) {
 799         MVT::SimpleValueType VT =
 800           (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
 801         if (VT == MVT::iPTR) VT = TLI.getPointerTy().SimpleTy;
 802         VTs.push_back(VT);
 803       }
 804
 805       if (EmitNodeInfo & OPFL_Chain)
 806         VTs.push_back(MVT::Other);
 807       if (EmitNodeInfo & OPFL_FlagOutput)
 808         VTs.push_back(MVT::Flag);
 809
 810       // FIXME: Use faster version for the common 'one VT' case?
 811       SDVTList VTList = CurDAG->getVTList(VTs.data(), VTs.size());
 812
 813       // Get the operand list.
 814       unsigned NumOps = MatcherTable[MatcherIndex++];
 815       SmallVector<SDValue, 8> Ops;
 816       for (unsigned i = 0; i != NumOps; ++i) {
 817         unsigned RecNo = MatcherTable[MatcherIndex++];
 818         if (RecNo & 128)
 819           RecNo = GetVBR(RecNo, MatcherTable, MatcherIndex);
 820
 821         assert(RecNo < RecordedNodes.size() && "Invalid EmitNode");
 822         Ops.push_back(RecordedNodes[RecNo]);
 823       }
 824
 825       // If there are variadic operands to add, handle them now.
 826       if (EmitNodeInfo & OPFL_VariadicInfo) {
 827         // Determine the start index to copy from.
 828         unsigned FirstOpToCopy = getNumFixedFromVariadicInfo(EmitNodeInfo);
 829         FirstOpToCopy += (EmitNodeInfo & OPFL_Chain) ? 1 : 0;
 830         assert(NodeToMatch->getNumOperands() >= FirstOpToCopy &&
 831                "Invalid variadic node");
 832         // Copy all of the variadic operands, not including a potential flag
 833         // input.
 834         for (unsigned i = FirstOpToCopy, e = NodeToMatch->getNumOperands();
 835              i != e; ++i) {
 836           SDValue V = NodeToMatch->getOperand(i);
 837           if (V.getValueType() == MVT::Flag) break;
 838           Ops.push_back(V);
 839         }
 840       }
 841
 842       // If this has chain/flag inputs, add them.
 843       if (EmitNodeInfo & OPFL_Chain)
 844         Ops.push_back(InputChain);
 845       if ((EmitNodeInfo & OPFL_FlagInput) && InputFlag.getNode() != 0)
 846         Ops.push_back(InputFlag);
 847
 848       // Create the node.
 849       SDNode *Res = 0;
 850       if (Opcode != OPC_MorphNodeTo) {
 851         // If this is a normal EmitNode command, just create the new node and
 852         // add the results to the RecordedNodes list.
 853         Res = CurDAG->getMachineNode(TargetOpc, NodeToMatch->getDebugLoc(),
 854                                      VTList, Ops.data(), Ops.size());
 855
 856         // Add all the non-flag/non-chain results to the RecordedNodes list.
 857         for (unsigned i = 0, e = VTs.size(); i != e; ++i) {
 858           if (VTs[i] == MVT::Other || VTs[i] == MVT::Flag) break;
 859           RecordedNodes.push_back(SDValue(Res, i));
 860         }
 861
 862       } else {
 863         // It is possible we're using MorphNodeTo to replace a node with no
 864         // normal results with one that has a normal result (or we could be
 865         // adding a chain) and the input could have flags and chains as well.
 866         // In this case we need to shifting the operands down.
 867         // FIXME: This is a horrible hack and broken in obscure cases, no worse
 868         // than the old isel though.  We should sink this into MorphNodeTo.
 869         int OldFlagResultNo = -1, OldChainResultNo = -1;
 870
 871         unsigned NTMNumResults = NodeToMatch->getNumValues();
 872         if (NodeToMatch->getValueType(NTMNumResults-1) == MVT::Flag) {
 873           OldFlagResultNo = NTMNumResults-1;
 874           if (NTMNumResults != 1 &&
 875               NodeToMatch->getValueType(NTMNumResults-2) == MVT::Other)
 876             OldChainResultNo = NTMNumResults-2;
 877         } else if (NodeToMatch->getValueType(NTMNumResults-1) == MVT::Other)
 878           OldChainResultNo = NTMNumResults-1;
 879
 880         Res = CurDAG->MorphNodeTo(NodeToMatch, ~TargetOpc, VTList,
 881                                   Ops.data(), Ops.size());
 882
 883         // MorphNodeTo can operate in two ways: if an existing node with the
 884         // specified operands exists, it can just return it.  Otherwise, it
 885         // updates the node in place to have the requested operands.
 886         if (Res == NodeToMatch) {
 887           // If we updated the node in place, reset the node ID.  To the isel,
 888           // this should be just like a newly allocated machine node.
 889           Res->setNodeId(-1);
 890         }
 891
 892         // FIXME: Whether the selected node has a flag result should come from
 893         // flags on the node.
 894         unsigned ResNumResults = Res->getNumValues();
 895         if (Res->getValueType(ResNumResults-1) == MVT::Flag) {
 896           // Move the flag if needed.
 897           if (OldFlagResultNo != -1 &&
 898               (unsigned)OldFlagResultNo != ResNumResults-1)
 899             ReplaceUses(SDValue(NodeToMatch, OldFlagResultNo),
 900                         SDValue(Res, ResNumResults-1));
 901           --ResNumResults;
 902         }
 903
 904         // Move the chain reference if needed.
 905         if ((EmitNodeInfo & OPFL_Chain) && OldChainResultNo != -1 &&
 906             (unsigned)OldChainResultNo != ResNumResults-1)
 907           ReplaceUses(SDValue(NodeToMatch, OldChainResultNo),
 908                       SDValue(Res, ResNumResults-1));
 909
 910         if (Res != NodeToMatch) {
 911           // Otherwise, no replacement happened because the node already exists.
 912           ReplaceUses(NodeToMatch, Res);
 913         }
 914       }
 915
 916       // If the node had chain/flag results, update our notion of the current
 917       // chain and flag.
 918       if (VTs.back() == MVT::Flag) {
 919         InputFlag = SDValue(Res, VTs.size()-1);
 920         if (EmitNodeInfo & OPFL_Chain)
 921           InputChain = SDValue(Res, VTs.size()-2);
 922       } else if (EmitNodeInfo & OPFL_Chain)
 923         InputChain = SDValue(Res, VTs.size()-1);
 924
 925       // If the OPFL_MemRefs flag is set on this node, slap all of the
 926       // accumulated memrefs onto it.
 927       //
 928       // FIXME: This is vastly incorrect for patterns with multiple outputs
 929       // instructions that access memory and for ComplexPatterns that match
 930       // loads.
 931       if (EmitNodeInfo & OPFL_MemRefs) {
 932         MachineSDNode::mmo_iterator MemRefs =
 933           MF->allocateMemRefsArray(MatchedMemRefs.size());
 934         std::copy(MatchedMemRefs.begin(), MatchedMemRefs.end(), MemRefs);
 935         cast<MachineSDNode>(Res)
 936           ->setMemRefs(MemRefs, MemRefs + MatchedMemRefs.size());
 937       }
 938
 939       DEBUG(errs() << "  "
 940                    << (Opcode == OPC_MorphNodeTo ? "Morphed" : "Created")
 941                    << " node: "; Res->dump(CurDAG); errs() << "\n");
 942
 943       // If this was a MorphNodeTo then we're completely done!
 944       if (Opcode == OPC_MorphNodeTo) {
 945         // Update chain and flag uses.
 946         UpdateChainsAndFlags(NodeToMatch, InputChain, ChainNodesMatched,
 947                              InputFlag, FlagResultNodesMatched, true);
 948         return 0;
 949       }
 950
 951       continue;
 952     }
 953
 954     case OPC_MarkFlagResults: {
 955       unsigned NumNodes = MatcherTable[MatcherIndex++];
 956
 957       // Read and remember all the flag-result nodes.
 958       for (unsigned i = 0; i != NumNodes; ++i) {
 959         unsigned RecNo = MatcherTable[MatcherIndex++];
 960         if (RecNo & 128)
 961           RecNo = GetVBR(RecNo, MatcherTable, MatcherIndex);
 962
 963         assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
 964         FlagResultNodesMatched.push_back(RecordedNodes[RecNo].getNode());
 965       }
 966       continue;
 967     }
 968
 969     case OPC_CompleteMatch: {
 970       // The match has been completed, and any new nodes (if any) have been
 971       // created.  Patch up references to the matched dag to use the newly
 972       // created nodes.
 973       unsigned NumResults = MatcherTable[MatcherIndex++];
 974
 975       for (unsigned i = 0; i != NumResults; ++i) {
 976         unsigned ResSlot = MatcherTable[MatcherIndex++];
 977         if (ResSlot & 128)
 978           ResSlot = GetVBR(ResSlot, MatcherTable, MatcherIndex);
 979
 980         assert(ResSlot < RecordedNodes.size() && "Invalid CheckSame");
 981         SDValue Res = RecordedNodes[ResSlot];
 982
 983         // FIXME2: Eliminate this horrible hack by fixing the 'Gen' program
 984         // after (parallel) on input patterns are removed.  This would also
 985         // allow us to stop encoding #results in OPC_CompleteMatch's table
 986         // entry.
 987         if (NodeToMatch->getNumValues() <= i ||
 988             NodeToMatch->getValueType(i) == MVT::Other ||
 989             NodeToMatch->getValueType(i) == MVT::Flag)
 990           break;
 991         assert((NodeToMatch->getValueType(i) == Res.getValueType() ||
 992                 NodeToMatch->getValueType(i) == MVT::iPTR ||
 993                 Res.getValueType() == MVT::iPTR ||
 994                 NodeToMatch->getValueType(i).getSizeInBits() ==
 995                     Res.getValueType().getSizeInBits()) &&
 996                "invalid replacement");
 997         ReplaceUses(SDValue(NodeToMatch, i), Res);
 998       }
 999
1000       // If the root node defines a flag, add it to the flag nodes to update
1001       // list.
1002       if (NodeToMatch->getValueType(NodeToMatch->getNumValues()-1) == MVT::Flag)
1003         FlagResultNodesMatched.push_back(NodeToMatch);
1004
1005       // Update chain and flag uses.
1006       UpdateChainsAndFlags(NodeToMatch, InputChain, ChainNodesMatched,
1007                            InputFlag, FlagResultNodesMatched, false);
1008
1009       assert(NodeToMatch->use_empty() &&
1010              "Didn't replace all uses of the node?");
1011
1012       // FIXME: We just return here, which interacts correctly with SelectRoot
1013       // above.  We should fix this to not return an SDNode* anymore.
1014       return 0;
1015     }
1016     }
1017
1018     // If the code reached this point, then the match failed.  See if there is
1019     // another child to try in the current 'Scope', otherwise pop it until we
1020     // find a case to check.
1021     while (1) {
1022       if (MatchScopes.empty()) {
1023         CannotYetSelect(NodeToMatch);
1024         return 0;
1025       }
1026
1027       // Restore the interpreter state back to the point where the scope was
1028       // formed.
1029       MatchScope &LastScope = MatchScopes.back();
1030       RecordedNodes.resize(LastScope.NumRecordedNodes);
1031       NodeStack.clear();
1032       NodeStack.append(LastScope.NodeStack.begin(), LastScope.NodeStack.end());
1033       N = NodeStack.back();
1034
1035       DEBUG(errs() << "  Match failed at index " << MatcherIndex
1036                    << " continuing at " << LastScope.FailIndex << "\n");
1037
1038       if (LastScope.NumMatchedMemRefs != MatchedMemRefs.size())
1039         MatchedMemRefs.resize(LastScope.NumMatchedMemRefs);
1040       MatcherIndex = LastScope.FailIndex;
1041
1042       InputChain = LastScope.InputChain;
1043       InputFlag = LastScope.InputFlag;
1044       if (!LastScope.HasChainNodesMatched)
1045         ChainNodesMatched.clear();
1046       if (!LastScope.HasFlagResultNodesMatched)
1047         FlagResultNodesMatched.clear();
1048
1049       // Check to see what the offset is at the new MatcherIndex.  If it is zero
1050       // we have reached the end of this scope, otherwise we have another child
1051       // in the current scope to try.
1052       unsigned NumToSkip = MatcherTable[MatcherIndex++];
1053       if (NumToSkip & 128)
1054         NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);
1055
1056       // If we have another child in this scope to match, update FailIndex and
1057       // try it.
1058       if (NumToSkip != 0) {
1059         LastScope.FailIndex = MatcherIndex+NumToSkip;
1060         break;
1061       }
1062
1063       // End of this scope, pop it and try the next child in the containing
1064       // scope.
1065       MatchScopes.pop_back();
1066     }
1067   }
1068 }
1069
1070
1071 #endif /* LLVM_CODEGEN_DAGISEL_HEADER_H */