summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/SelectionDAG
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/CodeGen/SelectionDAG')
-rw-r--r--llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp379
1 files changed, 152 insertions, 227 deletions
diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
index 2724480e03e..406e253fe4c 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
@@ -960,6 +960,43 @@ public:
} // end anonymous namespace
+// This function is used to enforce the topological node id property
+// property leveraged during Instruction selection. Before selection all
+// nodes are given a non-negative id such that all nodes have a larger id than
+// their operands. As this holds transitively we can prune checks that a node N
+// is a predecessor of M another by not recursively checking through M's
+// operands if N's ID is larger than M's ID. This is significantly improves
+// performance of for various legality checks (e.g. IsLegalToFold /
+// UpdateChains).
+
+// However, when we fuse multiple nodes into a single node
+// during selection we may induce a predecessor relationship between inputs and
+// outputs of distinct nodes being merged violating the topological property.
+// Should a fused node have a successor which has yet to be selected, our
+// legality checks would be incorrect. To avoid this we mark all unselected
+// sucessor nodes, i.e. id != -1 as invalid for pruning by bit-negating (x =>
+// (-(x+1))) the ids and modify our pruning check to ignore negative Ids of M.
+// We use bit-negation to more clearly enforce that node id -1 can only be
+// achieved by selected nodes). As the conversion is reversable the original Id,
+// topological pruning can still be leveraged when looking for unselected nodes.
+// This method is call internally in all ISel replacement calls.
+void SelectionDAGISel::EnforceNodeIdInvariant(SDNode *Node) {
+ SmallVector<SDNode *, 4> Nodes;
+ Nodes.push_back(Node);
+
+ while (!Nodes.empty()) {
+ SDNode *N = Nodes.pop_back_val();
+ for (auto *U : N->uses()) {
+ auto UId = U->getNodeId();
+ if (UId > 0) {
+ int InvalidatedUId = -UId + 1;
+ U->setNodeId(InvalidatedUId);
+ Nodes.push_back(U);
+ }
+ }
+ }
+}
+
void SelectionDAGISel::DoInstructionSelection() {
DEBUG(dbgs() << "===== Instruction selection begins: "
<< printMBBReference(*FuncInfo->MBB) << " '"
@@ -995,6 +1032,33 @@ void SelectionDAGISel::DoInstructionSelection() {
if (Node->use_empty())
continue;
+#ifndef NDEBUG
+ SmallVector<SDNode *, 4> Nodes;
+ Nodes.push_back(Node);
+
+ while (!Nodes.empty()) {
+ auto N = Nodes.pop_back_val();
+ if (N->getOpcode() == ISD::TokenFactor || N->getNodeId() < 0)
+ continue;
+ for (const SDValue &Op : N->op_values()) {
+ if (Op->getOpcode() == ISD::TokenFactor)
+ Nodes.push_back(Op.getNode());
+ else {
+ // We rely on topological ordering of node ids for checking for
+ // cycles when fusing nodes during selection. All unselected nodes
+ // successors of an already selected node should have a negative id.
+ // This assertion will catch such cases. If this assertion triggers
+ // it is likely you using DAG-level Value/Node replacement functions
+ // (versus equivalent ISEL replacement) in backend-specific
+ // selections. See comment in EnforceNodeIdInvariant for more
+ // details.
+ assert(Op->getNodeId() != -1 &&
+ "Node has already selected predecessor node");
+ }
+ }
+ }
+#endif
+
// When we are using non-default rounding modes or FP exception behavior
// FP operations are represented by StrictFP pseudo-operations. They
// need to be simplified here so that the target-specific instruction
@@ -2164,54 +2228,44 @@ static SDNode *findGlueUse(SDNode *N) {
return nullptr;
}
-/// 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,
+/// 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,
bool IgnoreChains) {
- // 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;
+ 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;
- // 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)
+ // 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)
continue;
+ if (!Visited.insert(N).second)
+ continue;
+ WorkList.push_back(N);
+ }
- for (const SDValue &Op : Use->op_values()) {
- // Ignore chain uses, they are validated by HandleMergeInputChains.
- if (Op.getValueType() == MVT::Other && IgnoreChains)
- continue;
-
+ // Initialize worklist to operands of Root.
+ if (Root != ImmedUse) {
+ for (const SDValue &Op : Root->op_values()) {
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.
+ // Ignore chains (they are validated by HandleMergeInputChains)
+ if ((Op.getValueType() == MVT::Other && IgnoreChains) || N == Def)
+ continue;
+ if (!Visited.insert(N).second)
+ continue;
WorkList.push_back(N);
}
}
- return false;
+
+ return SDNode::hasPredecessorHelper(Def, Visited, WorkList, 0, true);
}
/// IsProfitableToFold - Returns true if it's profitable to fold the specific
@@ -2283,13 +2337,12 @@ 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, our WalkChainUsers predicate will not consider it. Because of
+ // the chain, HandleMergeInputChains will not consider it. Because of
// this, we cannot ignore chains in this predicate.
IgnoreChains = false;
}
- SmallPtrSet<SDNode*, 16> Visited;
- return !findNonImmUse(Root, N.getNode(), U, Root, Visited, IgnoreChains);
+ return !findNonImmUse(Root, N.getNode(), U, IgnoreChains);
}
void SelectionDAGISel::Select_INLINEASM(SDNode *N) {
@@ -2393,7 +2446,7 @@ void SelectionDAGISel::UpdateChains(
static_cast<SDNode *>(nullptr));
});
if (ChainNode->getOpcode() != ISD::TokenFactor)
- CurDAG->ReplaceAllUsesOfValueWith(ChainVal, InputChain);
+ ReplaceUses(ChainVal, InputChain);
// If the node became dead and we haven't already seen it, delete it.
if (ChainNode != NodeToMatch && ChainNode->use_empty() &&
@@ -2408,143 +2461,6 @@ 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
@@ -2554,47 +2470,56 @@ WalkChainUsers(const SDNode *ChainedNode,
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.
- }
- // Okay, we have walked all the matched nodes and collected TokenFactor nodes
- // that we are interested in. Form our input TokenFactor node.
+ SmallPtrSet<const SDNode *, 16> Visited;
+ SmallVector<const SDNode *, 8> Worklist;
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;
+ unsigned int Max = 8192;
- // Otherwise, add the input chain.
- SDValue InChain = ChainNodesMatched[i]->getOperand(0);
- assert(InChain.getValueType() == MVT::Other && "Not a chain");
- InputChains.push_back(InChain);
- continue;
- }
+ // Quick exit on trivial merge.
+ if (ChainNodesMatched.size() == 1)
+ return ChainNodesMatched[0]->getOperand(0);
- // 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);
- }
+ // 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;
+ if (V->getOpcode() == ISD::TokenFactor) {
+ for (const SDValue &Op : V->op_values())
+ AddChains(Op);
+ } else
+ InputChains.push_back(V);
+ };
+
+ for (auto *N : ChainNodesMatched) {
+ Worklist.push_back(N);
+ Visited.insert(N);
}
+ 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]),
@@ -2639,8 +2564,8 @@ MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList,
// Move the glue if needed.
if ((EmitNodeInfo & OPFL_GlueOutput) && OldGlueResultNo != -1 &&
(unsigned)OldGlueResultNo != ResNumResults-1)
- CurDAG->ReplaceAllUsesOfValueWith(SDValue(Node, OldGlueResultNo),
- SDValue(Res, ResNumResults-1));
+ ReplaceUses(SDValue(Node, OldGlueResultNo),
+ SDValue(Res, ResNumResults - 1));
if ((EmitNodeInfo & OPFL_GlueOutput) != 0)
--ResNumResults;
@@ -2648,14 +2573,15 @@ MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList,
// Move the chain reference if needed.
if ((EmitNodeInfo & OPFL_Chain) && OldChainResultNo != -1 &&
(unsigned)OldChainResultNo != ResNumResults-1)
- CurDAG->ReplaceAllUsesOfValueWith(SDValue(Node, OldChainResultNo),
- SDValue(Res, ResNumResults-1));
+ ReplaceUses(SDValue(Node, OldChainResultNo),
+ SDValue(Res, ResNumResults - 1));
// Otherwise, no replacement happened because the node already exists. Replace
// Uses of the old node with the new one.
if (Res != Node) {
- CurDAG->ReplaceAllUsesWith(Node, Res);
- CurDAG->RemoveDeadNode(Node);
+ ReplaceNode(Node, Res);
+ } else {
+ EnforceNodeIdInvariant(Res);
}
return Res;
@@ -2972,8 +2898,7 @@ void SelectionDAGISel::SelectCodeCommon(SDNode *NodeToMatch,
return;
case ISD::AssertSext:
case ISD::AssertZext:
- CurDAG->ReplaceAllUsesOfValueWith(SDValue(NodeToMatch, 0),
- NodeToMatch->getOperand(0));
+ ReplaceUses(SDValue(NodeToMatch, 0), NodeToMatch->getOperand(0));
CurDAG->RemoveDeadNode(NodeToMatch);
return;
case ISD::INLINEASM:
@@ -3731,7 +3656,7 @@ void SelectionDAGISel::SelectCodeCommon(SDNode *NodeToMatch,
NodeToMatch->getValueType(i).getSizeInBits() ==
Res.getValueSizeInBits()) &&
"invalid replacement");
- CurDAG->ReplaceAllUsesOfValueWith(SDValue(NodeToMatch, i), Res);
+ ReplaceUses(SDValue(NodeToMatch, i), Res);
}
// Update chain uses.
@@ -3744,8 +3669,8 @@ void SelectionDAGISel::SelectCodeCommon(SDNode *NodeToMatch,
if (NodeToMatch->getValueType(NodeToMatch->getNumValues() - 1) ==
MVT::Glue &&
InputGlue.getNode())
- CurDAG->ReplaceAllUsesOfValueWith(
- SDValue(NodeToMatch, NodeToMatch->getNumValues() - 1), InputGlue);
+ ReplaceUses(SDValue(NodeToMatch, NodeToMatch->getNumValues() - 1),
+ InputGlue);
assert(NodeToMatch->use_empty() &&
"Didn't replace all uses of the node?");
OpenPOWER on IntegriCloud