diff options
-rw-r--r-- | include/llvm/CodeGen/SelectionDAGNodes.h | 5 | ||||
-rw-r--r-- | lib/CodeGen/SelectionDAG/DAGCombiner.cpp | 22 |
2 files changed, 21 insertions, 6 deletions
diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h index 051c93601d3f..5fb69ae232af 100644 --- a/include/llvm/CodeGen/SelectionDAGNodes.h +++ b/include/llvm/CodeGen/SelectionDAGNodes.h @@ -801,7 +801,8 @@ public: /// if DAG changes. static bool hasPredecessorHelper(const SDNode *N, SmallPtrSetImpl<const SDNode *> &Visited, - SmallVectorImpl<const SDNode *> &Worklist) { + SmallVectorImpl<const SDNode *> &Worklist, + unsigned int MaxSteps = 0) { if (Visited.count(N)) return true; while (!Worklist.empty()) { @@ -816,6 +817,8 @@ public: } if (Found) return true; + if (MaxSteps != 0 && Visited.size() >= MaxSteps) + return false; } return false; } diff --git a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp index a083f23bf923..432c86dd6f1e 100644 --- a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp +++ b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp @@ -12607,25 +12607,37 @@ void DAGCombiner::getStoreMergeCandidates( } } -// We need to check that merging these stores does not cause a loop -// in the DAG. Any store candidate may depend on another candidate +// We need to check that merging these stores does not cause a loop in +// the DAG. Any store candidate may depend on another candidate // indirectly through its operand (we already consider dependencies // through the chain). Check in parallel by searching up from // non-chain operands of candidates. + bool DAGCombiner::checkMergeStoreCandidatesForDependencies( SmallVectorImpl<MemOpLink> &StoreNodes, unsigned NumStores) { + + // FIXME: We should be able to truncate a full search of + // predecessors by doing a BFS and keeping tabs the originating + // stores from which worklist nodes come from in a similar way to + // TokenFactor simplfication. + SmallPtrSet<const SDNode *, 16> Visited; SmallVector<const SDNode *, 8> Worklist; - // search ops of store candidates + unsigned int Max = 8192; + // Search Ops of store candidates. for (unsigned i = 0; i < NumStores; ++i) { SDNode *n = StoreNodes[i].MemNode; // Potential loops may happen only through non-chain operands for (unsigned j = 1; j < n->getNumOperands(); ++j) Worklist.push_back(n->getOperand(j).getNode()); } - // search through DAG. We can stop early if we find a storenode + // Search through DAG. We can stop early if we find a store node. for (unsigned i = 0; i < NumStores; ++i) { - if (SDNode::hasPredecessorHelper(StoreNodes[i].MemNode, Visited, Worklist)) + if (SDNode::hasPredecessorHelper(StoreNodes[i].MemNode, Visited, Worklist, + Max)) + return false; + // Check if we ended early, failing conservatively if so. + if (Visited.size() >= Max) return false; } return true; |