3.4.4.3.4. OPC_EmitMergeInputChainsN等
OPC_EmitInteger，OPC_EmitRegister，OPC_EmitRegister2，OPC_EmitConvertToTarget都是用于部分生成目标指令DAG的操作符。它們與目标機器相關，是以需要目标機器相關的資訊（寄存器目前還是虛拟的，尚與目标機器無關）。
SelectionDAGISel::SelectCodeCommon（續）
2949 case OPC_EmitInteger: {
2950 MVT::SimpleValueType VT =
2951 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
2952 int64_t Val = MatcherTable[MatcherIndex++];
2953 if (Val & 128)
2954 Val = GetVBR(Val, MatcherTable, MatcherIndex);
2955 RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
2956 CurDAG->getTargetConstant(Val, SDLoc(NodeToMatch),
2957 VT), nullptr));
2958 continue;
2959 }
2960 case OPC_EmitRegister: {
2961 MVT::SimpleValueType VT =
2962 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
2963 unsigned RegNo = MatcherTable[MatcherIndex++];
2964 RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
2965 CurDAG->getRegister(RegNo, VT), nullptr));
2966 continue;
2967 }
2968 case OPC_EmitRegister2: {
2969 // For targets w/ more than 256 register names, the register enum
2970 // values are stored in two bytes in the matcher table (just like
2971 // opcodes).
2972 MVT::SimpleValueType VT =
2973 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
2974 unsigned RegNo = MatcherTable[MatcherIndex++];
2975 RegNo |= MatcherTable[MatcherIndex++] << 8;
2976 RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
2977 CurDAG->getRegister(RegNo, VT), nullptr));
2978 continue;
2979 }
2980
2981 case OPC_EmitConvertToTarget: {
2982 // Convert from IMM/FPIMM to target version.
2983 unsigned RecNo = MatcherTable[MatcherIndex++];
2984 assert(RecNo < RecordedNodes.size() && "Invalid EmitConvertToTarget");
2985 SDValue Imm = RecordedNodes[RecNo].first;
2986
2987 if (Imm->getOpcode() == ISD::Constant) {
2988 const ConstantInt *Val=cast<ConstantSDNode>(Imm)->getConstantIntValue();
2989 Imm = CurDAG->getConstant(*Val, SDLoc(NodeToMatch), Imm.getValueType(), <-- v7.0删除
2990 true);
Imm = CurDAG->getTargetConstant(*Val, SDLoc(NodeToMatch), <-- v7.0增加
Imm.getValueType());
2991 } else if (Imm->getOpcode() == ISD::ConstantFP) {
2992 const ConstantFP *Val=cast<ConstantFPSDNode>(Imm)->getConstantFPValue();
2993 Imm = CurDAG->getConstantFP(*Val, SDLoc(NodeToMatch), <-- v7.0删除
2994 Imm.getValueType(), true);
Imm = CurDAG->getTargetConstantFP(*Val, SDLoc(NodeToMatch), <-- v7.0增加
Imm.getValueType());
2995 }
2996
2997 RecordedNodes.push_back(std::make_pair(Imm, RecordedNodes[RecNo].second));
2998 continue;
2999 }
3000
3001 case OPC_EmitMergeInputChains1_0: // OPC_EmitMergeInputChains, 1, 0
3002 case OPC_EmitMergeInputChains1_1: { // OPC_EmitMergeInputChains, 1, 1
case OPC_EmitMergeInputChains1_2: { // OPC_EmitMergeInputChains, 1, 2 <-- v7.0增加
3003 // These are space-optimized forms of OPC_EmitMergeInputChains.
3004 assert(!InputChain.getNode() &&
3005 "EmitMergeInputChains should be the first chain producing node");
3006 assert(ChainNodesMatched.empty() &&
3007 "Should only have one EmitMergeInputChains per match");
3008
3009 // Read all of the chained nodes.
3010 unsigned RecNo = Opcode == OPC_EmitMergeInputChains1_1; <-- v7.0删除
unsigned RecNo = Opcode - OPC_EmitMergeInputChains1_0; <-- v7.0增加
3011 assert(RecNo < RecordedNodes.size() && "Invalid EmitMergeInputChains");
3012 ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode());
3013
3014 // FIXME: What if other value results of the node have uses not matched
3015 // by this pattern?
3016 if (ChainNodesMatched.back() != NodeToMatch &&
3017 !RecordedNodes[RecNo].first.hasOneUse()) {
3018 ChainNodesMatched.clear();
3019 break;
3020 }
3021
3022 // Merge the input chains if they are not intra-pattern references.
3023 InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG);
3024
3025 if (!InputChain.getNode())
3026 break; // Failed to merge.
3027 continue;
3028 }
3029
3030 case OPC_EmitMergeInputChains: {
3031 assert(!InputChain.getNode() &&
3032 "EmitMergeInputChains should be the first chain producing node");
3033 // This node gets a list of nodes we matched in the input that have
3034 // chains. We want to token factor all of the input chains to these nodes
3035 // together. However, if any of the input chains is actually one of the
3036 // nodes matched in this pattern, then we have an intra-match reference.
3037 // Ignore these because the newly token factored chain should not refer to
3038 // the old nodes.
3039 unsigned NumChains = MatcherTable[MatcherIndex++];
3040 assert(NumChains != 0 && "Can't TF zero chains");
3041
3042 assert(ChainNodesMatched.empty() &&
3043 "Should only have one EmitMergeInputChains per match");
3044
3045 // Read all of the chained nodes.
3046 for (unsigned i = 0; i != NumChains; ++i) {
3047 unsigned RecNo = MatcherTable[MatcherIndex++];
3048 assert(RecNo < RecordedNodes.size() && "Invalid EmitMergeInputChains");
3049 ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode());
3050
3051 // FIXME: What if other value results of the node have uses not matched
3052 // by this pattern?
3053 if (ChainNodesMatched.back() != NodeToMatch &&
3054 !RecordedNodes[RecNo].first.hasOneUse()) {
3055 ChainNodesMatched.clear();
3056 break;
3057 }
3058 }
3059
3060 // If the inner loop broke out, the match fails.
3061 if (ChainNodesMatched.empty())
3062 break;
3063
3064 // Merge the input chains if they are not intra-pattern references.
3065 InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG);
3066
3067 if (!InputChain.getNode())
3068 break; // Failed to merge.
3069
3070 continue;
3071 }
OPC_EmitMergeInputChainsN表示比對DAG中有節點需要輸傳入連結節點，指令選擇器需要嘗試産生公共的輸傳入連結節點。首先在容器ChainNodesMatched裡記錄合乎條件的鍊節點的使用者（3016與3053行條件，NodeToMatch以外的SDNode對象隻能有一個使用者）。
注意那些把生成DAG加入RecordedNodes容器的OPC_XXX操作。在前面生成它們對應的Matcher對象時，已經通過NextRecordedOperandNo算好了它們在這個容器的位置。它現在就是加入這個位置，是以前面位置的計算與這裡對RecordedNodes的push_back()是一一對應的。這些位置也已經寫在MatcherTable中，比如OPC_CheckSame操作，它的操作數就是比較對象的索引。
接着調用下面的函數嘗試甄别合并鍊節點使用者是否會導緻環的出現。
2185 static SDValue
2186 HandleMergeInputChains(SmallVectorImpl<SDNode*> &ChainNodesMatched,
2187 SelectionDAG *CurDAG) {
2188 // Walk all of the chained nodes we've matched, recursively scanning down the
2189 // users of the chain result. This adds any TokenFactor nodes that are caught
2190 // in between chained nodes to the chained and interior nodes list.
2191 SmallVector<SDNode*, 3> InteriorChainedNodes;
2192 for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
2193 if (WalkChainUsers(ChainNodesMatched[i], ChainNodesMatched,
2194 InteriorChainedNodes) == CR_InducesCycle)
2195 return SDValue(); // Would induce a cycle.
2196 }
2197
2198 // Okay, we have walked all the matched nodes and collected TokenFactor nodes
2199 // that we are interested in. Form our input TokenFactor node.
2200 SmallVector<SDValue, 3> InputChains;
2201 for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
2202 // Add the input chain of this node to the InputChains list (which will be
2203 // the operands of the generated TokenFactor) if it's not an interior node.
2204 SDNode *N = ChainNodesMatched[i];
2205 if (N->getOpcode() != ISD::TokenFactor) {
2206 if (std::count(InteriorChainedNodes.begin(),InteriorChainedNodes.end(),N))
2207 continue;
2208
2209 // Otherwise, add the input chain.
2210 SDValue InChain = ChainNodesMatched[i]->getOperand(0);
2211 assert(InChain.getValueType() == MVT::Other && "Not a chain");
2212 InputChains.push_back(InChain);
2213 continue;
2214 }
2215
2216 // If we have a token factor, we want to add all inputs of the token factor
2217 // that are not part of the pattern we're matching.
2218 for (const SDValue &Op : N->op_values()) {
2219 if (!std::count(ChainNodesMatched.begin(), ChainNodesMatched.end(),
2220 Op.getNode()))
2221 InputChains.push_back(Op);
2222 }
2223 }
2224
2225 if (InputChains.size() == 1)
2226 return InputChains[0];
2227 return CurDAG->getNode(ISD::TokenFactor, SDLoc(ChainNodesMatched[0]),
2228 MVT::Other, InputChains);
2229 }
2192行的循環通過WalkChainUsers()方法逐個測試ChainNodesMatched内的成員是否會形成誘導環。如果是，處理失敗，進而比對也宣告失敗。
對于ChainNodesMatched中某個成員，在對應的WalkChainUsers()調用中，在2073行查找使用這個鍊節點的使用者。
2067 static ChainResult
2068 WalkChainUsers(const SDNode *ChainedNode,
2069 SmallVectorImpl<SDNode*> &ChainedNodesInPattern,
2070 SmallVectorImpl<SDNode*> &InteriorChainedNodes) {
2071 ChainResult Result = CR_Simple;
2072
2073 for (SDNode::use_iterator UI = ChainedNode->use_begin(),
2074 E = ChainedNode->use_end(); UI != E; ++UI) {
2075 // Make sure the use is of the chain, not some other value we produce.
2076 if (UI.getUse().getValueType() != MVT::Other) continue;
2077
2078 SDNode *User = *UI;
2079
2080 if (User->getOpcode() == ISD::HANDLENODE) // Root of the graph.
2081 continue;
2082
2083 // If we see an already-selected machine node, then we've gone beyond the
2084 // pattern that we're selecting down into the already selected chunk of the
2085 // DAG.
2086 unsigned UserOpcode = User->getOpcode();
2087 if (User->isMachineOpcode() ||
2088 UserOpcode == ISD::CopyToReg ||
2089 UserOpcode == ISD::CopyFromReg ||
2090 UserOpcode == ISD::INLINEASM ||
2091 UserOpcode == ISD::EH_LABEL ||
2092 UserOpcode == ISD::LIFETIME_START ||
2093 UserOpcode == ISD::LIFETIME_END) {
2094 // If their node ID got reset to -1 then they've already been selected.
2095 // Treat them like a MachineOpcode.
2096 if (User->getNodeId() == -1)
2097 continue;
2098 }
2099
2100 // If we have a TokenFactor, we handle it specially.
2101 if (User->getOpcode() != ISD::TokenFactor) {
2102 // If the node isn't a token factor and isn't part of our pattern, then it
2103 // must be a random chained node in between two nodes we're selecting.
2104 // This happens when we have something like:
2105 // x = load ptr
2106 // call
2107 // y = x+4
2108 // store y -> ptr
2109 // Because we structurally match the load/store as a read/modify/write,
2110 // but the call is chained between them. We cannot fold in this case
2111 // because it would induce a cycle in the graph.
2112 if (!std::count(ChainedNodesInPattern.begin(),
2113 ChainedNodesInPattern.end(), User))
2114 return CR_InducesCycle;
2115
2116 // Otherwise we found a node that is part of our pattern. For example in:
2117 // x = load ptr
2118 // y = x+4
2119 // store y -> ptr
2120 // This would happen when we're scanning down from the load and see the
2121 // store as a user. Record that there is a use of ChainedNode that is
2122 // part of the pattern and keep scanning uses.
2123 Result = CR_LeadsToInteriorNode;
2124 InteriorChainedNodes.push_back(User);
2125 continue;
2126 }
2127
2128 // If we found a TokenFactor, there are two cases to consider: first if the
2129 // TokenFactor is just hanging "below" the pattern we're matching (i.e. no
2130 // uses of the TF are in our pattern) we just want to ignore it. Second,
2131 // the TokenFactor can be sandwiched in between two chained nodes, like so:
2132 // [Load chain]
2133 // ^
2134 // |
2135 // [Load]
2136 // ^ ^
2137 // | \ DAG's like cheese
2138 // / \ do you?
2139 // / |
2140 // [TokenFactor] [Op]
2141 // ^ ^
2142 // | |
2143 // \ /
2144 // \ /
2145 // [Store]
2146 //
2147 // In this case, the TokenFactor becomes part of our match and we rewrite it
2148 // as a new TokenFactor.
2149 //
2150 // To distinguish these two cases, do a recursive walk down the uses.
2151 switch (WalkChainUsers(User, ChainedNodesInPattern, InteriorChainedNodes)) {
2152 case CR_Simple:
2153 // If the uses of the TokenFactor are just already-selected nodes, ignore
2154 // it, it is "below" our pattern.
2155 continue;
2156 case CR_InducesCycle:
2157 // If the uses of the TokenFactor lead to nodes that are not part of our
2158 // pattern that are not selected, folding would turn this into a cycle,
2159 // bail out now.
2160 return CR_InducesCycle;
2161 case CR_LeadsToInteriorNode:
2162 break; // Otherwise, keep processing.
2163 }
2164
2165 // Okay, we know we're in the interesting interior case. The TokenFactor
2166 // is now going to be considered part of the pattern so that we rewrite its
2167 // uses (it may have uses that are not part of the pattern) with the
2168 // ultimate chain result of the generated code. We will also add its chain
2169 // inputs as inputs to the ultimate TokenFactor we create.
2170 Result = CR_LeadsToInteriorNode;
2171 ChainedNodesInPattern.push_back(User);
2172 InteriorChainedNodes.push_back(User);
2173 continue;
2174 }
2175
2176 return Result;
2177 }
在2101行，ISD::TokenFactor類型的SDNode節點是我們要産生的（見HandleMergeInputChains()的2227行）。代表有副作用操作的DAG的鍊節點總是成對的，一個輸出，一個輸入。該方法中的注釋已經詳細地解釋了代碼的邏輯，不再重複。
回到HandleMergeInputChains()，如果不會導緻環，就可以建構對應的ISD::TokenFactor節點。并把它傳回給SelectionDAGISel::SelectCodeCommon()中的InputChain。如果這個節點不能成功建立，目前的指令比對就失敗了，需要進入出錯處理，嘗試比對下一個指令。
| V7.0的處理相比之精簡不少，不再需要繁瑣、難懂的WalkChainUsers()： 2489 static SDValue 2490 HandleMergeInputChains(SmallVectorImpl<SDNode*> &ChainNodesMatched, 2491 SelectionDAG *CurDAG) { 2492 2493 SmallPtrSet<const SDNode *, 16> Visited; 2494 SmallVector<const SDNode *, 8> Worklist; 2495 SmallVector<SDValue, 3> InputChains; 2496 unsigned int Max = 8192; 2497 2498 // Quick exit on trivial merge. 2499 if (ChainNodesMatched.size() == 1) 2500 return ChainNodesMatched[0]->getOperand(0); 2501 2502 // Add chains that aren't already added (internal). Peek through 2503 // token factors. 2504 std::function<void(const SDValue)> AddChains = [&](const SDValue V) { 2505 if (V.getValueType() != MVT::Other) 2506 return; 2507 if (V->getOpcode() == ISD::EntryToken) 2508 return; 2509 if (!Visited.insert(V.getNode()).second) 2510 return; 2511 if (V->getOpcode() == ISD::TokenFactor) { 2512 for (const SDValue &Op : V->op_values()) 2513 AddChains(Op); 2514 } else 2515 InputChains.push_back(V); 2516 }; 2517 2518 for (auto *N : ChainNodesMatched) { 2519 Worklist.push_back(N); 2520 Visited.insert(N); 2521 } 2522 2523 while (!Worklist.empty()) 2524 AddChains(Worklist.pop_back_val()->getOperand(0)); 2525 2526 // Skip the search if there are no chain dependencies. 2527 if (InputChains.size() == 0) 2528 return CurDAG->getEntryNode(); 2529 2530 // If one of these chains is a successor of input, we must have a 2531 // node that is both the predecessor and successor of the 2532 // to-be-merged nodes. Fail. 2533 Visited.clear(); 2534 for (SDValue V : InputChains) 2535 Worklist.push_back(V.getNode()); 2536 2537 for (auto *N : ChainNodesMatched) 2538 if (SDNode::hasPredecessorHelper(N, Visited, Worklist, Max, true)) 2539 return SDValue(); 2540 2541 // Return merged chain. 2542 if (InputChains.size() == 1) 2543 return InputChains[0]; 2544 return CurDAG->getNode(ISD::TokenFactor, SDLoc(ChainNodesMatched[0]), 2545 MVT::Other, InputChains); 2546 } HandleMergeInputChains()與前面的findNonImmUse()類似，通過hasPredecessorHelper()方法來查找作為輸入參數的鍊節點中是否存在作為它們操作數（該節點本身是它們的後繼）前驅情形。如果存在，該節點将同時為這些操作數的前驅與後繼，是以不能合并。 |
![LLVM學習筆記（48）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)