LLVM学习笔记（30-2）
3.4.4.3. 选择过程
3.4.4.3.1. 概述
现在我们先看一下下面这个MatcherTable的片段如何指引指令选择。
/*0*/ OPC_SwitchOpcode /*284 cases */, 41|128,120/*15401*/, TARGET_VAL(ISD::STORE),// ->15406
/*5*/ OPC_RecordMemRef,
/*6*/ OPC_RecordNode, // #0 = 'st' chained node
/*7*/ OPC_Scope, 20|128,5/*660*/, /*->670*/ // 10 children in Scope
/*10*/ OPC_RecordChild1, // #1 = $src
/*11*/ OPC_Scope, 64, /*->77*/ // 17 children in Scope
/*13*/ OPC_CheckChild1Type, MVT::v4f32,
/*15*/ OPC_RecordChild2, // #2 = $dst
/*16*/ OPC_CheckPredicate, 0, // Predicate_alignednontemporalstore
/*18*/ OPC_Scope, 18, /*->38*/ // 3 children in Scope
/*20*/ OPC_CheckPatternPredicate, 0, // (Subtarget->hasAVX()) && (!Subtarget->hasVLX())
/*22*/ OPC_CheckComplexPat, /*CP*/0, /*#*/2, // SelectAddr:$dst #3 #4 #5 #6 #7
/*25*/ OPC_EmitMergeInputChains1_0,
/*26*/ OPC_MorphNodeTo, TARGET_VAL(X86::VMOVNTPSmr), 0|OPFL_Chain|OPFL_MemRefs,
0/*#VTs*/, 6/*#Ops*/, 3, 4, 5, 6, 7, 1,
// Src: (st VR128:v4f32:$src, addr:iPTR:$dst)<<P:Predicate_alignednontemporalstore>> - Complexity = 422
// Dst: (VMOVNTPSmr addr:iPTR:$dst, VR128:v4f32:$src)
/*38*/ /*Scope*/ 18, /*->57*/
/*39*/ OPC_CheckPatternPredicate, 1, // (Subtarget->hasSSE1() && !Subtarget->hasAVX())
/*41*/ OPC_CheckComplexPat, /*CP*/0, /*#*/2, // SelectAddr:$dst #3 #4 #5 #6 #7
/*44*/ OPC_EmitMergeInputChains1_0,
/*45*/ OPC_MorphNodeTo, TARGET_VAL(X86::MOVNTPSmr), 0|OPFL_Chain|OPFL_MemRefs,
0/*#VTs*/, 6/*#Ops*/, 3, 4, 5, 6, 7, 1,
// Src: (st VR128:v4f32:$src, addr:iPTR:$dst)<<P:Predicate_alignednontemporalstore>> - Complexity = 422
// Dst: (MOVNTPSmr addr:iPTR:$dst, VR128:v4f32:$src)
/*57*/ /*Scope*/ 18, /*->76*/
/*58*/ OPC_CheckPatternPredicate, 2, // (Subtarget->hasAVX512()) && (Subtarget->hasVLX())
/*60*/ OPC_CheckComplexPat, /*CP*/0, /*#*/2, // SelectAddr:$dst #3 #4 #5 #6 #7
/*63*/ OPC_EmitMergeInputChains1_0,
/*64*/ OPC_MorphNodeTo, TARGET_VAL(X86::VMOVNTPSZ128mr), 0|OPFL_Chain|OPFL_MemRefs,
0/*#VTs*/, 6/*#Ops*/, 3, 4, 5, 6, 7, 1,
// Src: (st VR128X:v4f32:$src, addr:iPTR:$dst)<<P:Predicate_alignednontemporalstore>> - Complexity = 422
// Dst: (VMOVNTPSZ128mr addr:iPTR:$dst, VR128X:v4f32:$src)
/*76*/ 0, /*End of Scope*/
首先，OPC_SwitchOpcode的第一个分支是ISD::STORE，它一直到偏移15406字节处结束。Store含有对内存的操作，因此第5字节处是OPC_RecordMemRef。在第6字节处，是这些可能匹配指令的第一个操作数——链节点（它是这些指令公用的）。第7字节处的OPC_Scope宣示着Store的子节点有10种可能，第一种可能子节点的匹配横跨第10~670字节。第10字节要求保存该子节点。接着在第11字节，又出现了17种可能的子节点，第一种可能从第13~76字节（我们将只看到这里）。第13字节要求该子节点的类型必须是MVT::v4f32。如果失败，选择器将前进到第77字节尝试下一个匹配。第15字节要求保存第二个子节点（这是Store的输入操作数，保存操作将返回它在容器RecordedNodes的索引，最终作为目标DAG的操作数）。第16字节执行alignednontemporalstore所定义的谓词（定义在X86InstrFragments.td的PatFrag）。如果谓词成立，第18字节表示还有3种可能。第20字节要求执行对应模式给出的谓词，第22字节则要求检查是否为指定的ComplexPattern。如果这些检查都通过，该模式匹配成功，否则跳到第38字节进行下一个匹配。第25字节的OPC_EmitMergeInputChains1_0是由于匹配的DAG节点中包含链节点产生的，指令选择器需要为生成的结果节点产生相应的链节点。第26字节的OPC_MorphNodeTo则会让指令选择器将结果、链、对标记寄存器的修改信息更新到代表选中目标指令的SDNode的派生对象。很显然，前面对Matcher对象链的优化是重要的，尤其是公用节点的提取，能大大加快匹配的速度。下面结合代码仔细看一下指令选择器到底是怎么做的。
MatcherTable的结构在生成Matcher对象时已经确定了，而Matcher对象则是根据TD的指令描述生成的。所以，这里的选择过程实际上是由这些TD定义决定的。对于TD无法描述的指令，目前LLVM只能通过手写代码进行指令选择。让所有执行指令选择的代码自动生成是LLVM的目标之一。
3.4.4.3.2. OPC_SwitchOpcode与谓词匹配
在文件ISDOpcodes.h中，在名字空间ISD里，枚举类型NodeType定义了SDNode的NodeType所可能出现的操作类型。在TargetSelectionDAG.td等描述目标机器的TableGen源代码里，也能看到同样的枚举值。但下面2561~2582行所指定的类型都没有TD的描述。
SelectCodeCommon()是一个庞大的函数，一共有1217行。它不是自动生成的，是SelectionDAG的核心部分之一。所有目标机器的指令选择都是通过这个函数完成，通过使用每个目标机器自己的MatcherTable，在必要时调用目标机器定制的虚函数，SelectCodeCommon()能很好地完成工作。
首先，参数NodeToMatch是要匹配的DAG（SDNode节点），比如前面看到的表示储存操作的Store节点。参数MatcherTable就是前面生成的MatcherTable表，TableSize则是这个表的大小。
2554 SDNode *SelectionDAGISel:: <-- v7.0不返回值
2555 SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable,
2556 unsigned TableSize) {
2557 // FIXME: Should these even be selected? Handle these cases in the caller?
2558 switch (NodeToMatch->getOpcode()) {
2559 default:
2560 break;
2561 case ISD::EntryToken: // These nodes remain the same.
2562 case ISD::BasicBlock:
2563 case ISD::Register:
2564 case ISD::RegisterMask:
2565 case ISD::HANDLENODE:
2566 case ISD::MDNODE_SDNODE:
2567 case ISD::TargetConstant:
2568 case ISD::TargetConstantFP:
2569 case ISD::TargetConstantPool:
2570 case ISD::TargetFrameIndex:
2571 case ISD::TargetExternalSymbol:
2572 case ISD::MCSymbol:
2573 case ISD::TargetBlockAddress:
2574 case ISD::TargetJumpTable:
2575 case ISD::TargetGlobalTLSAddress:
2576 case ISD::TargetGlobalAddress:
2577 case ISD::TokenFactor:
2578 case ISD::CopyFromReg:
2579 case ISD::CopyToReg:
2580 case ISD::EH_LABEL:
2581 case ISD::LIFETIME_START:
2582 case ISD::LIFETIME_END:
2583 NodeToMatch->setNodeId(-1); // Mark selected.
2584 return nullptr;
2585 case ISD::AssertSext:
2586 case ISD::AssertZext:
2587 CurDAG->ReplaceAllUsesOfValueWith(SDValue(NodeToMatch, 0),
2588 NodeToMatch->getOperand(0));
2589 return nullptr;
2590 case ISD::INLINEASM: return Select_INLINEASM(NodeToMatch); return;
2591 case ISD::READ_REGISTER: return Select_READ_REGISTER(NodeToMatch); return;
2592 case ISD::WRITE_REGISTER: return Select_WRITE_REGISTER(NodeToMatch); return;
2593 case ISD::UNDEF: return Select_UNDEF(NodeToMatch); return;
2594 }
2595
2596 assert(!NodeToMatch->isMachineOpcode() && "Node already selected!");
2597
2598 // Set up the node stack with NodeToMatch as the only node on the stack.
2599 SmallVector<SDValue, 8> NodeStack;
2600 SDValue N = SDValue(NodeToMatch, 0);
2601 NodeStack.push_back(N);
2602
2603 // MatchScopes - Scopes used when matching, if a match failure happens, this
2604 // indicates where to continue checking.
2605 SmallVector<MatchScope, 8> MatchScopes;
2606
2607 // RecordedNodes - This is the set of nodes that have been recorded by the
2608 // state machine. The second value is the parent of the node, or null if the
2609 // root is recorded.
2610 SmallVector<std::pair<SDValue, SDNode*>, 8> RecordedNodes;
2611
2612 // MatchedMemRefs - This is the set of MemRef's we've seen in the input
2613 // pattern.
2614 SmallVector<MachineMemOperand*, 2> MatchedMemRefs;
2615
2616 // These are the current input chain and glue for use when generating nodes.
2617 // Various Emit operations change these. For example, emitting a copytoreg
2618 // uses and updates these.
2619 SDValue InputChain, InputGlue;
2620
2621 // ChainNodesMatched - If a pattern matches nodes that have input/output
2622 // chains, the OPC_EmitMergeInputChains operation is emitted which indicates
2623 // which ones they are. The result is captured into this list so that we can
2624 // update the chain results when the pattern is complete.
2625 SmallVector<SDNode*, 3> ChainNodesMatched;
2626 SmallVector<SDNode*, 3> GlueResultNodesMatched; <-- v7.0删除
2627
2628 DEBUG(dbgs() << "ISEL: Starting pattern match on root node: ";
2629 NodeToMatch->dump(CurDAG);
2630 dbgs() << '\n');
2631
2632 // Determine where to start the interpreter. Normally we start at opcode #0,
2633 // but if the state machine starts with an OPC_SwitchOpcode, then we
2634 // accelerate the first lookup (which is guaranteed to be hot) with the
2635 // OpcodeOffset table.
2636 unsigned MatcherIndex = 0;
在2600行构建一个SDValue实例，参数0表示它是NodeToMatch的第一个结果。在其后声明的容器中，NodeStack用于追踪NodeToMatch中子节点的进入与退出情况。容器MatchScopes用于记录当前的匹配Scope域所形成的栈。前面准备Matcher对象时，我们使用了NextRecordedOperandNo来追踪需要保存在容器RecordedNodes里的SDNode对象。这些对象将随着选择的进行，保存在这个容器里，它们在容器里序号则已输出在MatcherTable里。容器MatchedMemRefs用于记录匹配模式中出现的内存引用。容器ChainNodesMatched记录链节点SDNode对象，GlueResultNodesMatched容器则记录修改标志寄存器的SDNode对象。
在2638行容器OpcodeOffset的类型是std::vector<unsigned>，它是SelectionDAGISel的成员，2649行循环处理使用它来记录当前SwitchOpcode所有分支的偏移。通常情况下，2638行的条件是不满足的。从指定位置开始匹配，估计这是为了调试给出的功能。
SelectionDAGISel::SelectCodeCommon（续）
2638 if (!OpcodeOffset.empty()) {
2639 // Already computed the OpcodeOffset table, just index into it.
2640 if (N.getOpcode() < OpcodeOffset.size())
2641 MatcherIndex = OpcodeOffset[N.getOpcode()];
2642 DEBUG(dbgs() << " Initial Opcode index to " << MatcherIndex << "\n");
2643
2644 } else if (MatcherTable[0] == OPC_SwitchOpcode) {
2645 // Otherwise, the table isn't computed, but the state machine does start
2646 // with an OPC_SwitchOpcode instruction. Populate the table now, since this
2647 // is the first time we're selecting an instruction.
2648 unsigned Idx = 1;
2649 while (1) {
2650 // Get the size of this case.
2651 unsigned CaseSize = MatcherTable[Idx++];
2652 if (CaseSize & 128)
2653 CaseSize = GetVBR(CaseSize, MatcherTable, Idx);
2654 if (CaseSize == 0) break;
2655
2656 // Get the opcode, add the index to the table.
2657 uint16_t Opc = MatcherTable[Idx++];
2658 Opc |= (unsigned short)MatcherTable[Idx++] << 8;
2659 if (Opc >= OpcodeOffset.size())
2660 OpcodeOffset.resize((Opc+1)*2);
2661 OpcodeOffset[Opc] = Idx;
2662 Idx += CaseSize;
2663 }
2664
2665 // Okay, do the lookup for the first opcode.
2666 if (N.getOpcode() < OpcodeOffset.size())
2667 MatcherIndex = OpcodeOffset[N.getOpcode()];
2668 }
2669
2670 while (1) {
2671 assert(MatcherIndex < TableSize && "Invalid index");
2672 #ifndef NDEBUG
2673 unsigned CurrentOpcodeIndex = MatcherIndex;
2674 #endif
2675 BuiltinOpcodes Opcode = (BuiltinOpcodes)MatcherTable[MatcherIndex++];
2676 switch (Opcode) {
2677 case OPC_Scope: {
2678 // Okay, the semantics of this operation are that we should push a scope
2679 // then evaluate the first child. However, pushing a scope only to have
2680 // the first check fail (which then pops it) is inefficient. If we can
2681 // determine immediately that the first check (or first several) will
2682 // immediately fail, don't even bother pushing a scope for them.
2683 unsigned FailIndex;
2684
2685 while (1) {
2686 unsigned NumToSkip = MatcherTable[MatcherIndex++];
2687 if (NumToSkip & 128)
2688 NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);
2689 // Found the end of the scope with no match.
2690 if (NumToSkip == 0) {
2691 FailIndex = 0;
2692 break;
2693 }
2694
2695 FailIndex = MatcherIndex+NumToSkip;
2696
2697 unsigned MatcherIndexOfPredicate = MatcherIndex;
2698 (void)MatcherIndexOfPredicate; // silence warning.
2699
2700 // If we can't evaluate this predicate without pushing a scope (e.g. if
2701 // it is a 'MoveParent') or if the predicate succeeds on this node, we
2702 // push the scope and evaluate the full predicate chain.
2703 bool Result;
2704 MatcherIndex = IsPredicateKnownToFail(MatcherTable, MatcherIndex, N,
2705 Result, *this, RecordedNodes);
2706 if (!Result)
2707 break;
2708
2709 DEBUG(dbgs() << " Skipped scope entry (due to false predicate) at "
2710 << "index " << MatcherIndexOfPredicate
2711 << ", continuing at " << FailIndex << "\n");
2712 ++NumDAGIselRetries;
2713
2714 // Otherwise, we know that this case of the Scope is guaranteed to fail,
2715 // move to the next case.
2716 MatcherIndex = FailIndex;
2717 }
2718
2719 // If the whole scope failed to match, bail.
2720 if (FailIndex == 0) break;
2721
2722 // Push a MatchScope which indicates where to go if the first child fails
2723 // to match.
2724 MatchScope NewEntry;
2725 NewEntry.FailIndex = FailIndex;
2726 NewEntry.NodeStack.append(NodeStack.begin(), NodeStack.end());
2727 NewEntry.NumRecordedNodes = RecordedNodes.size();
2728 NewEntry.NumMatchedMemRefs = MatchedMemRefs.size();
2729 NewEntry.InputChain = InputChain;
2730 NewEntry.InputGlue = InputGlue;
2731 NewEntry.HasChainNodesMatched = !ChainNodesMatched.empty();
2732 NewEntry.HasGlueResultNodesMatched = !GlueResultNodesMatched.empty();
2733 MatchScopes.push_back(NewEntry);
2734 continue;
2735 }
2670行开始的大while循环开启了NodeToMatch的指令选择之旅。主角是MatcherTable，因为整个选择需要在MatcherTable的指引下进行。就像我们前面看到的，MatcherTable将选则过程组织为一棵树。从根节点开始，到达叶子结束。在每个分支处是一个OPC_Scope记录。OPC_Scope后面可能有一个谓词，也可能没有，因此在2704行通过IsPredicateKnownToFail()试一下。如果不是谓词，就从2431行返回，回退一个字节，并且标记匹配成功。否则执行匹配。
2423 static unsigned IsPredicateKnownToFail(const unsigned char *Table,
2424 unsigned Index, SDValue N,
2425 bool &Result,
2426 const SelectionDAGISel &SDISel,
2427 SmallVectorImpl<std::pair<SDValue, SDNode*> > &RecordedNodes) {
2428 switch (Table[Index++]) {
2429 default:
2430 Result = false;
2431 return Index-1; // Could not evaluate this predicate.
2432 case SelectionDAGISel::OPC_CheckSame:
2433 Result = !::CheckSame(Table, Index, N, RecordedNodes);
2434 return Index;
2435 case SelectionDAGISel::OPC_CheckChild0Same:
2436 case SelectionDAGISel::OPC_CheckChild1Same:
2437 case SelectionDAGISel::OPC_CheckChild2Same:
2438 case SelectionDAGISel::OPC_CheckChild3Same:
2439 Result = !::CheckChildSame(Table, Index, N, RecordedNodes,
2440 Table[Index-1] - SelectionDAGISel::OPC_CheckChild0Same);
2441 return Index;
2442 case SelectionDAGISel::OPC_CheckPatternPredicate:
2443 Result = !::CheckPatternPredicate(Table, Index, SDISel);
2444 return Index;
2445 case SelectionDAGISel::OPC_CheckPredicate:
2446 Result = !::CheckNodePredicate(Table, Index, SDISel, N.getNode());
2447 return Index;
2448 case SelectionDAGISel::OPC_CheckOpcode:
2449 Result = !::CheckOpcode(Table, Index, N.getNode());
2450 return Index;
2451 case SelectionDAGISel::OPC_CheckType:
2452 Result = !::CheckType(Table, Index, N, SDISel.TLI,
2453 SDISel.CurDAG->getDataLayout());
2454 return Index;
2455 case SelectionDAGISel::OPC_CheckChild0Type:
2456 case SelectionDAGISel::OPC_CheckChild1Type:
2457 case SelectionDAGISel::OPC_CheckChild2Type:
2458 case SelectionDAGISel::OPC_CheckChild3Type:
2459 case SelectionDAGISel::OPC_CheckChild4Type:
2460 case SelectionDAGISel::OPC_CheckChild5Type:
2461 case SelectionDAGISel::OPC_CheckChild6Type:
2462 case SelectionDAGISel::OPC_CheckChild7Type:
2463 Result = !::CheckChildType(
2464 Table, Index, N, SDISel.TLI, SDISel.CurDAG->getDataLayout(),
2465 Table[Index - 1] - SelectionDAGISel::OPC_CheckChild0Type);
2466 return Index;
2467 case SelectionDAGISel::OPC_CheckCondCode:
2468 Result = !::CheckCondCode(Table, Index, N);
2469 return Index;
2470 case SelectionDAGISel::OPC_CheckValueType:
2471 Result = !::CheckValueType(Table, Index, N, SDISel.TLI,
2472 SDISel.CurDAG->getDataLayout());
2473 return Index;
2474 case SelectionDAGISel::OPC_CheckInteger:
2475 Result = !::CheckInteger(Table, Index, N);
2476 return Index;
2477 case SelectionDAGISel::OPC_CheckChild0Integer:
2478 case SelectionDAGISel::OPC_CheckChild1Integer:
2479 case SelectionDAGISel::OPC_CheckChild2Integer:
2480 case SelectionDAGISel::OPC_CheckChild3Integer:
2481 case SelectionDAGISel::OPC_CheckChild4Integer:
2482 Result = !::CheckChildInteger(Table, Index, N,
2483 Table[Index-1] - SelectionDAGISel::OPC_CheckChild0Integer);
2484 return Index;
2485 case SelectionDAGISel::OPC_CheckAndImm:
2486 Result = !::CheckAndImm(Table, Index, N, SDISel);
2487 return Index;
2488 case SelectionDAGISel::OPC_CheckOrImm:
2489 Result = !::CheckOrImm(Table, Index, N, SDISel);
2490 return Index;
2491 }
2492 }
上面援引的各种比较方法分别定义在下面。2432行的SelectionDAGISel::OPC_CheckSame()最初的源头在MatcherGen::recordUniqueNode()方法，在匹配模板中重复援引一个已存在的具名节点时，就会在MatcherTable中产生一个SelectionDAGISel::OPC_CheckSame()项检查节点是否相同。
2290 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
2291 CheckSame(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2292 SDValue N,
2293 const SmallVectorImpl<std::pair<SDValue, SDNode*> > &RecordedNodes) {
2294 // Accept if it is exactly the same as a previously recorded node.
2295 unsigned RecNo = MatcherTable[MatcherIndex++];
2296 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
2297 return N == RecordedNodes[RecNo].first;
2298 }
参数RecordedNodes也就是SelectCodeCommon()方法里的容器RecordedNodes，它按顺序记录MatcherTable中的OPC_RecordNode，这个顺序也是MatcherTable里用于援引SDNode对象的索引。
类似的，SelectionDAGISel::OPC_CheckChildXSame是对MoveChildMatcher+CheckSameMatcher优化的结果。它的作用与SelectionDAGISel::OPC_CheckSame()相类。
2301 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
2302 CheckChildSame(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2303 SDValue N,
2304 const SmallVectorImpl<std::pair<SDValue, SDNode*>> &RecordedNodes,
2305 unsigned ChildNo) {
2306 if (ChildNo >= N.getNumOperands())
2307 return false; // Match fails if out of range child #.
2308 return ::CheckSame(MatcherTable, MatcherIndex, N.getOperand(ChildNo),
2309 RecordedNodes);
2310 }
前面已经为模式的谓词生成了一个检查方法，这个方法以谓词的序号来执行相关的代码。因此，CheckPatternPredicate()只需要是这个检查方法的一个简单外覆即可。CheckNodePredicate()也是类似的。其他的检查方法也并不复杂。
2313 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
2314 CheckPatternPredicate(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2315 const SelectionDAGISel &SDISel) {
2316 return SDISel.CheckPatternPredicate(MatcherTable[MatcherIndex++]);
2317 }
2320 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
2321 CheckNodePredicate(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2322 const SelectionDAGISel &SDISel, SDNode *N) {
2323 return SDISel.CheckNodePredicate(N, MatcherTable[MatcherIndex++]);
2324 }
2326 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
2327 CheckOpcode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2328 SDNode *N) {
2329 uint16_t Opc = MatcherTable[MatcherIndex++];
2330 Opc |= (unsigned short)MatcherTable[MatcherIndex++] << 8;
2331 return N->getOpcode() == Opc;
2332 }
2334 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
2335 CheckType(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N,
2336 const TargetLowering *TLI, const DataLayout &DL) {
2337 MVT::SimpleValueType VT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
2338 if (N.getValueType() == VT) return true;
2339
2340 // Handle the case when VT is iPTR.
2341 return VT == MVT::iPTR && N.getValueType() == TLI->getPointerTy(DL);
2342 }
2343
2344 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
2345 CheckChildType(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2346 SDValue N, const TargetLowering *TLI, const DataLayout &DL,
2347 unsigned ChildNo) {
2348 if (ChildNo >= N.getNumOperands())
2349 return false; // Match fails if out of range child #.
2350 return ::CheckType(MatcherTable, MatcherIndex, N.getOperand(ChildNo), TLI,
2351 DL);
2352 }
2353 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
2354 CheckCondCode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2355 SDValue N) {
2356 return cast<CondCodeSDNode>(N)->get() ==
2357 (ISD::CondCode)MatcherTable[MatcherIndex++];
2358 }
2360 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
2361 CheckValueType(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2362 SDValue N, const TargetLowering *TLI, const DataLayout &DL) {
2363 MVT::SimpleValueType VT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
2364 if (cast<VTSDNode>(N)->getVT() == VT)
2365 return true;
2366
2367 // Handle the case when VT is iPTR.
2368 return VT == MVT::iPTR && cast<VTSDNode>(N)->getVT() == TLI->getPointerTy(DL);
2369 }
2371 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
2372 CheckInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2373 SDValue N) {
2374 int64_t Val = MatcherTable[MatcherIndex++];
2375 if (Val & 128)
2376 Val = GetVBR(Val, MatcherTable, MatcherIndex);
2377
2378 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N);
2379 return C && C->getSExtValue() == Val;
2380 }
2383 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
2384 CheckChildInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2385 SDValue N, unsigned ChildNo) {
2386 if (ChildNo >= N.getNumOperands())
2387 return false; // Match fails if out of range child #.
2388 return ::CheckInteger(MatcherTable, MatcherIndex, N.getOperand(ChildNo));
2389 }
2391 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
2392 CheckAndImm(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2393 SDValue N, const SelectionDAGISel &SDISel) {
2394 int64_t Val = MatcherTable[MatcherIndex++];
2395 if (Val & 128)
2396 Val = GetVBR(Val, MatcherTable, MatcherIndex);
2397
2398 if (N->getOpcode() != ISD::AND) return false;
2399
2400 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
2401 return C && SDISel.CheckAndMask(N.getOperand(0), C, Val);
2402 }
2404 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
2405 CheckOrImm(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2406 SDValue N, const SelectionDAGISel &SDISel) {
2407 int64_t Val = MatcherTable[MatcherIndex++];
2408 if (Val & 128)
2409 Val = GetVBR(Val, MatcherTable, MatcherIndex);
2410
2411 if (N->getOpcode() != ISD::OR) return false;
2412
2413 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
2414 return C && SDISel.CheckOrMask(N.getOperand(0), C, Val);
2415 }
如果IsPredicateKnownToFail()返回false，就跳出了2685行开始的循环。否则前进到下一个分支，直到穷尽所有分支，这时FailIndex为0。这样在2720行跳出2676行开始的switch语句，到3322行进行出错处理。如果有分支匹配成功，在2733行向MatchScopes容器加入代表这个分支的MatchScope对象。该对象记录了当前匹配的快照，在出错时我们才有机会从这个分支之后继续匹配。