summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp')
-rw-r--r--llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp294
1 files changed, 215 insertions, 79 deletions
diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
index 12282d92ed8..ab0a2293666 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
@@ -2137,44 +2137,54 @@ static SDNode *findGlueUse(SDNode *N) {
return nullptr;
}
-/// findNonImmUse - Return true if "Def" is a predecessor of "Root" via a path
-/// beyond "ImmedUse". We may ignore chains as they are checked separately.
-static bool findNonImmUse(SDNode *Root, SDNode *Def, SDNode *ImmedUse,
+/// findNonImmUse - Return true if "Use" is a non-immediate use of "Def".
+/// This function iteratively traverses up the operand chain, ignoring
+/// certain nodes.
+static bool findNonImmUse(SDNode *Use, SDNode* Def, SDNode *ImmedUse,
+ SDNode *Root, SmallPtrSetImpl<SDNode*> &Visited,
bool IgnoreChains) {
- SmallPtrSet<const SDNode *, 16> Visited;
- SmallVector<const SDNode *, 16> WorkList;
- // Only check if we have non-immediate uses of Def.
- if (ImmedUse->isOnlyUserOf(Def))
- return false;
-
- // We don't care about paths to Def that go through ImmedUse so mark it
- // visited and mark non-def operands as used.
- Visited.insert(ImmedUse);
- for (const SDValue &Op : ImmedUse->op_values()) {
- SDNode *N = Op.getNode();
- // Ignore chain deps (they are validated by
- // HandleMergeInputChains) and immediate uses
- if ((Op.getValueType() == MVT::Other && IgnoreChains) || N == Def)
+ // The NodeID's are given uniques ID's where a node ID is guaranteed to be
+ // greater than all of its (recursive) operands. If we scan to a point where
+ // 'use' is smaller than the node we're scanning for, then we know we will
+ // never find it.
+ //
+ // The Use may be -1 (unassigned) if it is a newly allocated node. This can
+ // happen because we scan down to newly selected nodes in the case of glue
+ // uses.
+ std::vector<SDNode *> WorkList;
+ WorkList.push_back(Use);
+
+ while (!WorkList.empty()) {
+ Use = WorkList.back();
+ WorkList.pop_back();
+ // NodeId topological order of TokenFactors is not guaranteed. Do not skip.
+ if (Use->getOpcode() != ISD::TokenFactor &&
+ Use->getNodeId() < Def->getNodeId() && Use->getNodeId() != -1)
continue;
- if (!Visited.insert(N).second)
+
+ // Don't revisit nodes if we already scanned it and didn't fail, we know we
+ // won't fail if we scan it again.
+ if (!Visited.insert(Use).second)
continue;
- WorkList.push_back(N);
- }
- // Initialize worklist to operands of Root.
- if (Root != ImmedUse) {
- for (const SDValue &Op : Root->op_values()) {
- SDNode *N = Op.getNode();
- // Ignore chains (they are validated by HandleMergeInputChains)
- if ((Op.getValueType() == MVT::Other && IgnoreChains) || N == Def)
- continue;
- if (!Visited.insert(N).second)
+ for (const SDValue &Op : Use->op_values()) {
+ // Ignore chain uses, they are validated by HandleMergeInputChains.
+ if (Op.getValueType() == MVT::Other && IgnoreChains)
continue;
+
+ SDNode *N = Op.getNode();
+ if (N == Def) {
+ if (Use == ImmedUse || Use == Root)
+ continue; // We are not looking for immediate use.
+ assert(N != Root);
+ return true;
+ }
+
+ // Traverse up the operand chain.
WorkList.push_back(N);
}
}
-
- return SDNode::hasPredecessorHelper(Def, Visited, WorkList, 0, true);
+ return false;
}
/// IsProfitableToFold - Returns true if it's profitable to fold the specific
@@ -2246,12 +2256,13 @@ bool SelectionDAGISel::IsLegalToFold(SDValue N, SDNode *U, SDNode *Root,
// If our query node has a glue result with a use, we've walked up it. If
// the user (which has already been selected) has a chain or indirectly uses
- // the chain, HandleMergeInputChains will not consider it. Because of
+ // the chain, our WalkChainUsers predicate will not consider it. Because of
// this, we cannot ignore chains in this predicate.
IgnoreChains = false;
}
- return !findNonImmUse(Root, N.getNode(), U, IgnoreChains);
+ SmallPtrSet<SDNode*, 16> Visited;
+ return !findNonImmUse(Root, N.getNode(), U, Root, Visited, IgnoreChains);
}
void SelectionDAGISel::Select_INLINEASM(SDNode *N) {
@@ -2370,6 +2381,143 @@ void SelectionDAGISel::UpdateChains(
DEBUG(dbgs() << "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(const SDNode *ChainedNode,
+ SmallVectorImpl<SDNode *> &ChainedNodesInPattern,
+ DenseMap<const SDNode *, ChainResult> &TokenFactorResult,
+ 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 (User->getOpcode() == ISD::HANDLENODE) // Root of the graph.
+ continue;
+
+ // 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.
+ unsigned UserOpcode = User->getOpcode();
+ if (User->isMachineOpcode() ||
+ UserOpcode == ISD::CopyToReg ||
+ UserOpcode == ISD::CopyFromReg ||
+ UserOpcode == ISD::INLINEASM ||
+ UserOpcode == ISD::EH_LABEL ||
+ UserOpcode == ISD::LIFETIME_START ||
+ UserOpcode == ISD::LIFETIME_END) {
+ // If their node ID got reset to -1 then they've already been selected.
+ // Treat them like a MachineOpcode.
+ if (User->getNodeId() == -1)
+ 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.
+ auto MemoizeResult = TokenFactorResult.find(User);
+ bool Visited = MemoizeResult != TokenFactorResult.end();
+ // Recursively walk chain users only if the result is not memoized.
+ if (!Visited) {
+ auto Res = WalkChainUsers(User, ChainedNodesInPattern, TokenFactorResult,
+ InteriorChainedNodes);
+ MemoizeResult = TokenFactorResult.insert(std::make_pair(User, Res)).first;
+ }
+ switch (MemoizeResult->second) {
+ 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;
+ if (!Visited) {
+ ChainedNodesInPattern.push_back(User);
+ InteriorChainedNodes.push_back(User);
+ }
+ }
+
+ return Result;
+}
+
/// HandleMergeInputChains - This implements the OPC_EmitMergeInputChains
/// operation for when the pattern matched at least one node with a chains. The
/// input vector contains a list of all of the chained nodes that we match. We
@@ -2379,59 +2527,47 @@ void SelectionDAGISel::UpdateChains(
static SDValue
HandleMergeInputChains(SmallVectorImpl<SDNode*> &ChainNodesMatched,
SelectionDAG *CurDAG) {
+ // Used for memoization. Without it WalkChainUsers could take exponential
+ // time to run.
+ DenseMap<const SDNode *, ChainResult> TokenFactorResult;
+ // 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,
+ TokenFactorResult,
+ InteriorChainedNodes) == CR_InducesCycle)
+ return SDValue(); // Would induce a cycle.
+ }
- SmallPtrSet<const SDNode *, 16> Visited;
- SmallVector<const SDNode *, 8> Worklist;
+ // 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;
- unsigned int Max = 8192;
-
- // Quick exit on trivial merge.
- if (ChainNodesMatched.size() == 1)
- return ChainNodesMatched[0]->getOperand(0);
+ 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;
- // Add chains that aren't already added (internal). Peek through
- // token factors.
- std::function<void(const SDValue)> AddChains = [&](const SDValue V) {
- if (V.getValueType() != MVT::Other)
- return;
- if (V->getOpcode() == ISD::EntryToken)
- return;
- if (!Visited.insert(V.getNode()).second)
- return;
- // Newly selected nodes (-1) are always added directly.
- if (V->getNodeId() == -1)
- InputChains.push_back(V);
- else if (V->getOpcode() == ISD::TokenFactor) {
- for (int i = 0, e = V->getNumOperands(); i != e; ++i)
- AddChains(V->getOperand(i));
- } else
- InputChains.push_back(V);
- };
+ // Otherwise, add the input chain.
+ SDValue InChain = ChainNodesMatched[i]->getOperand(0);
+ assert(InChain.getValueType() == MVT::Other && "Not a chain");
+ InputChains.push_back(InChain);
+ continue;
+ }
- for (auto *N : ChainNodesMatched) {
- Worklist.push_back(N);
- Visited.insert(N);
+ // 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 (const SDValue &Op : N->op_values()) {
+ if (!std::count(ChainNodesMatched.begin(), ChainNodesMatched.end(),
+ Op.getNode()))
+ InputChains.push_back(Op);
+ }
}
- while (!Worklist.empty())
- AddChains(Worklist.pop_back_val()->getOperand(0));
-
- // Skip the search if there are no chain dependencies.
- if (InputChains.size() == 0)
- return CurDAG->getEntryNode();
-
- // If one of these chains is a successor of input, we must have a
- // node that is both the predecessor and successor of the
- // to-be-merged nodes. Fail.
- Visited.clear();
- for (SDValue V : InputChains)
- Worklist.push_back(V.getNode());
-
- for (auto *N : ChainNodesMatched)
- if (SDNode::hasPredecessorHelper(N, Visited, Worklist, Max, true))
- return SDValue();
-
- // Return merged chain.
if (InputChains.size() == 1)
return InputChains[0];
return CurDAG->getNode(ISD::TokenFactor, SDLoc(ChainNodesMatched[0]),
OpenPOWER on IntegriCloud