MVT::Other, Tmp, Chain);
}
-
-/// ChainNotReachable - Returns true if Chain does not reach Op.
-static bool ChainNotReachable(SDNode *Chain, SDNode *Op) {
- if (Chain->getOpcode() == ISD::EntryToken)
- return true;
- if (Chain->getOpcode() == ISD::TokenFactor)
- return false;
- if (Chain->getNumOperands() > 0) {
- SDValue C0 = Chain->getOperand(0);
- if (C0.getValueType() == MVT::Other)
- return C0.getNode() != Op && ChainNotReachable(C0.getNode(), Op);
- }
- return true;
-}
-
-/// IsChainCompatible - Returns true if Chain is Op or Chain does not reach Op.
-/// This is used to ensure that there are no nodes trapped between Chain, which
-/// is the first chain node discovered in a pattern and Op, a later node, that
-/// will not be selected into the pattern.
-static bool IsChainCompatible(SDNode *Chain, SDNode *Op) {
- return Chain == Op || ChainNotReachable(Chain, Op);
-}
-
-
/// GetVBR - decode a vbr encoding whose top bit is set.
ALWAYS_INLINE static uint64_t
GetVBR(uint64_t Val, const unsigned char *MatcherTable, unsigned &Idx) {
return Val;
}
-/// ISelUpdater - helper class to handle updates of the
-/// instruciton selection graph.
-namespace {
-class ISelUpdater : public SelectionDAG::DAGUpdateListener {
- SelectionDAG::allnodes_iterator &ISelPosition;
-public:
- explicit ISelUpdater(SelectionDAG::allnodes_iterator &isp)
- : ISelPosition(isp) {}
-
- /// NodeDeleted - Handle nodes deleted from the graph. If the
- /// node being deleted is the current ISelPosition node, update
- /// ISelPosition.
- ///
- virtual void NodeDeleted(SDNode *N, SDNode *E) {
- if (ISelPosition == SelectionDAG::allnodes_iterator(N))
- ++ISelPosition;
- }
-
- /// NodeUpdated - Ignore updates for now.
- virtual void NodeUpdated(SDNode *N) {}
-};
-}
-
-#if 0
-/// ReplaceUses - replace all uses of the old node F with the use
-/// of the new node T.
-static void ReplaceUses(SDValue F, SDValue T) {
- ISelUpdater ISU(ISelPosition);
- CurDAG->ReplaceAllUsesOfValueWith(F, T, &ISU);
-}
-#endif
/// UpdateChainsAndFlags - When a match is complete, this method updates uses of
/// interior flag and chain results to use the new flag and chain results.
DEBUG(errs() << "ISEL: Match complete!\n");
}
+enum ChainResult {
+ CR_Simple,
+ CR_InducesCycle,
+ CR_LeadsToInteriorNode
+};
+
+/// WalkChainUsers - Walk down the users of the specified chained node that is
+/// part of the pattern we're matching, looking at all of the users we find.
+/// This determines whether something is an interior node, whether we have a
+/// non-pattern node in between two pattern nodes (which prevent folding because
+/// it would induce a cycle) and whether we have a TokenFactor node sandwiched
+/// between pattern nodes (in which case the TF becomes part of the pattern).
+///
+/// The walk we do here is guaranteed to be small because we quickly get down to
+/// already selected nodes "below" us.
+static ChainResult
+WalkChainUsers(SDNode *ChainedNode,
+ SmallVectorImpl<SDNode*> &ChainedNodesInPattern,
+ SmallVectorImpl<SDNode*> &InteriorChainedNodes) {
+ ChainResult Result = CR_Simple;
+
+ for (SDNode::use_iterator UI = ChainedNode->use_begin(),
+ E = ChainedNode->use_end(); UI != E; ++UI) {
+ // Make sure the use is of the chain, not some other value we produce.
+ if (UI.getUse().getValueType() != MVT::Other) continue;
+
+ SDNode *User = *UI;
+
+ // If we see an already-selected machine node, then we've gone beyond the
+ // pattern that we're selecting down into the already selected chunk of the
+ // DAG.
+ if (User->isMachineOpcode() ||
+ User->getOpcode() == ISD::CopyToReg ||
+ User->getOpcode() == ISD::CopyFromReg ||
+ User->getOpcode() == ISD::INLINEASM ||
+ User->getOpcode() == ISD::HANDLENODE) // Root of the graph.
+ continue;
+
+ // If we have a TokenFactor, we handle it specially.
+ if (User->getOpcode() != ISD::TokenFactor) {
+ // If the node isn't a token factor and isn't part of our pattern, then it
+ // must be a random chained node in between two nodes we're selecting.
+ // This happens when we have something like:
+ // x = load ptr
+ // call
+ // y = x+4
+ // store y -> ptr
+ // Because we structurally match the load/store as a read/modify/write,
+ // but the call is chained between them. We cannot fold in this case
+ // because it would induce a cycle in the graph.
+ if (!std::count(ChainedNodesInPattern.begin(),
+ ChainedNodesInPattern.end(), User))
+ return CR_InducesCycle;
+
+ // Otherwise we found a node that is part of our pattern. For example in:
+ // x = load ptr
+ // y = x+4
+ // store y -> ptr
+ // This would happen when we're scanning down from the load and see the
+ // store as a user. Record that there is a use of ChainedNode that is
+ // part of the pattern and keep scanning uses.
+ Result = CR_LeadsToInteriorNode;
+ InteriorChainedNodes.push_back(User);
+ continue;
+ }
+
+ // If we found a TokenFactor, there are two cases to consider: first if the
+ // TokenFactor is just hanging "below" the pattern we're matching (i.e. no
+ // uses of the TF are in our pattern) we just want to ignore it. Second,
+ // the TokenFactor can be sandwiched in between two chained nodes, like so:
+ // [Load chain]
+ // ^
+ // |
+ // [Load]
+ // ^ ^
+ // | \ DAG's like cheese
+ // / \ do you?
+ // / |
+ // [TokenFactor] [Op]
+ // ^ ^
+ // | |
+ // \ /
+ // \ /
+ // [Store]
+ //
+ // In this case, the TokenFactor becomes part of our match and we rewrite it
+ // as a new TokenFactor.
+ //
+ // To distinguish these two cases, do a recursive walk down the uses.
+ switch (WalkChainUsers(User, ChainedNodesInPattern, InteriorChainedNodes)) {
+ case CR_Simple:
+ // If the uses of the TokenFactor are just already-selected nodes, ignore
+ // it, it is "below" our pattern.
+ continue;
+ case CR_InducesCycle:
+ // If the uses of the TokenFactor lead to nodes that are not part of our
+ // pattern that are not selected, folding would turn this into a cycle,
+ // bail out now.
+ return CR_InducesCycle;
+ case CR_LeadsToInteriorNode:
+ break; // Otherwise, keep processing.
+ }
+
+ // Okay, we know we're in the interesting interior case. The TokenFactor
+ // is now going to be considered part of the pattern so that we rewrite its
+ // uses (it may have uses that are not part of the pattern) with the
+ // ultimate chain result of the generated code. We will also add its chain
+ // inputs as inputs to the ultimate TokenFactor we create.
+ Result = CR_LeadsToInteriorNode;
+ ChainedNodesInPattern.push_back(User);
+ InteriorChainedNodes.push_back(User);
+ continue;
+ }
+
+ return Result;
+}
+/// HandleMergeInputChains - This implements the OPC_EmitMergeInputChains
+/// operation for when the pattern matched multiple nodes with chains. The
+/// input vector contains a list of all of the chained nodes that we match. We
+/// must determine if this is a valid thing to cover (i.e. matching it won't
+/// induce cycles in the DAG) and if so, creating a TokenFactor node. that will
+/// be used as the input node chain for the generated nodes.
+static SDValue
+HandleMergeInputChains(SmallVectorImpl<SDNode*> &ChainNodesMatched,
+ SelectionDAG *CurDAG) {
+ assert(ChainNodesMatched.size() > 1 &&
+ "Should only happen for multi chain node case");
+
+ // Walk all of the chained nodes we've matched, recursively scanning down the
+ // users of the chain result. This adds any TokenFactor nodes that are caught
+ // in between chained nodes to the chained and interior nodes list.
+ SmallVector<SDNode*, 3> InteriorChainedNodes;
+ for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
+ if (WalkChainUsers(ChainNodesMatched[i], ChainNodesMatched,
+ InteriorChainedNodes) == CR_InducesCycle)
+ return SDValue(); // Would induce a cycle.
+ }
+
+ // Okay, we have walked all the matched nodes and collected TokenFactor nodes
+ // that we are interested in. Form our input TokenFactor node.
+ SmallVector<SDValue, 3> InputChains;
+ for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
+ // Add the input chain of this node to the InputChains list (which will be
+ // the operands of the generated TokenFactor) if it's not an interior node.
+ SDNode *N = ChainNodesMatched[i];
+ if (N->getOpcode() != ISD::TokenFactor) {
+ if (std::count(InteriorChainedNodes.begin(),InteriorChainedNodes.end(),N))
+ continue;
+
+ // Otherwise, add the input chain.
+ SDValue InChain = ChainNodesMatched[i]->getOperand(0);
+ assert(InChain.getValueType() == MVT::Other && "Not a chain");
+ InputChains.push_back(InChain);
+ continue;
+ }
+
+ // If we have a token factor, we want to add all inputs of the token factor
+ // that are not part of the pattern we're matching.
+ for (unsigned op = 0, e = N->getNumOperands(); op != e; ++op) {
+ if (!std::count(ChainNodesMatched.begin(), ChainNodesMatched.end(),
+ N->getOperand(op).getNode()))
+ InputChains.push_back(N->getOperand(op));
+ }
+ }
+
+ SDValue Res;
+ if (InputChains.size() == 1)
+ return InputChains[0];
+ return CurDAG->getNode(ISD::TokenFactor, ChainNodesMatched[0]->getDebugLoc(),
+ MVT::Other, &InputChains[0], InputChains.size());
+}
struct MatchScope {
/// FailIndex - If this match fails, this is the index to continue with.
continue;
}
- case OPC_CheckChainCompatible: {
- unsigned PrevNode = MatcherTable[MatcherIndex++];
- assert(PrevNode < RecordedNodes.size() && "Invalid CheckChainCompatible");
- SDValue PrevChainedNode = RecordedNodes[PrevNode];
- SDValue ThisChainedNode = RecordedNodes.back();
-
- // We have two nodes with chains, verify that their input chains are good.
- assert(PrevChainedNode.getOperand(0).getValueType() == MVT::Other &&
- ThisChainedNode.getOperand(0).getValueType() == MVT::Other &&
- "Invalid chained nodes");
-
- if (!IsChainCompatible(// Input chain of the previous node.
- PrevChainedNode.getOperand(0).getNode(),
- // Node with chain.
- ThisChainedNode.getNode()))
- break;
- continue;
- }
-
case OPC_EmitInteger: {
MVT::SimpleValueType VT =
(MVT::SimpleValueType)MatcherTable[MatcherIndex++];
break;
}
}
+
+ // If the inner loop broke out, the match fails.
+ if (ChainNodesMatched.empty())
+ break;
- // Walk all the chained nodes, adding the input chains if they are not in
- // ChainedNodes (and this, not in the matched pattern). This is an N^2
- // algorithm, but # chains is usually 2 here, at most 3 for MSP430.
- SmallVector<SDValue, 3> InputChains;
- for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
- SDValue InChain = ChainNodesMatched[i]->getOperand(0);
- assert(InChain.getValueType() == MVT::Other && "Not a chain");
- bool Invalid = false;
- for (unsigned j = 0; j != e; ++j)
- Invalid |= ChainNodesMatched[j] == InChain.getNode();
- if (!Invalid)
- InputChains.push_back(InChain);
- }
+ // Merge the input chains if they are not intra-pattern references.
+ InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG);
+
+ if (InputChain.getNode() == 0)
+ break; // Failed to merge.
- SDValue Res;
- if (InputChains.size() == 1)
- InputChain = InputChains[0];
- else
- InputChain = CurDAG->getNode(ISD::TokenFactor,
- NodeToMatch->getDebugLoc(), MVT::Other,
- &InputChains[0], InputChains.size());
continue;
}
} else if (NodeToMatch->getValueType(NTMNumResults-1) == MVT::Other)
OldChainResultNo = NTMNumResults-1;
+ // FIXME: If this matches multiple nodes it will just leave them here
+ // dead with noone to love them. These dead nodes can block future
+ // matches (!).
Res = CurDAG->MorphNodeTo(NodeToMatch, ~TargetOpc, VTList,
Ops.data(), Ops.size());
projects / oota-llvm.git / blobdiff