Prevent construction of cycle in DAG store merge
When merging stores in DAGCombiner, add check to ensure that no
dependenices exist that would cause the construction of a cycle in our
DAG. This may happen if one store has a data dependence on another
instruction (e.g. a load) which itself has a (chain) dependence on
another store being merged. These stores cannot be merged safely and
doing so results in a cycle that is discovered in LegalizeDAG.
This test is only done in cases where Antialias analysis is used (UseAA)
as non-AA store merge candidates will be merged logically after all
loads which have been checked to not alias.
Reviewers: ahatanak, spatel, niravd, arsenm, hfinkel, tstellarAMD, jyknight
Subscribers: llvm-commits, tberghammer, danalbert, srhines
Differential Revision: http://reviews.llvm.org/D18336
llvm-svn: 264461
diff --git a/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp b/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
index 0aecaa4..09c7971 100644
--- a/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
@@ -448,6 +448,12 @@
StoreSDNode* St, SmallVectorImpl<MemOpLink> &StoreNodes,
SmallVectorImpl<LSBaseSDNode*> &AliasLoadNodes);
+ /// Helper function for MergeConsecutiveStores. Checks if
+ /// Candidate stores have indirect dependency through their
+ /// operands. \return True if safe to merge
+ bool checkMergeStoreCandidatesForDependencies(
+ SmallVectorImpl<MemOpLink> &StoreNodes);
+
/// Merge consecutive store operations into a wide store.
/// This optimization uses wide integers or vectors when possible.
/// \return True if some memory operations were changed.
@@ -9636,6 +9642,7 @@
// Caches for hasPredecessorHelper.
SmallPtrSet<const SDNode *, 32> Visited;
SmallVector<const SDNode *, 16> Worklist;
+ Worklist.push_back(N);
// If the offset is a constant, there may be other adds of constants that
// can be folded with this one. We should do this to avoid having to keep
@@ -9651,7 +9658,7 @@
if (Use.getUser() == Ptr.getNode() || Use != BasePtr)
continue;
- if (N->hasPredecessorHelper(Use.getUser(), Visited, Worklist))
+ if (SDNode::hasPredecessorHelper(Use.getUser(), Visited, Worklist))
continue;
if (Use.getUser()->getOpcode() != ISD::ADD &&
@@ -9684,7 +9691,7 @@
for (SDNode *Use : Ptr.getNode()->uses()) {
if (Use == N)
continue;
- if (N->hasPredecessorHelper(Use, Visited, Worklist))
+ if (SDNode::hasPredecessorHelper(Use, Visited, Worklist))
return false;
// If Ptr may be folded in addressing mode of other use, then it's
@@ -11365,6 +11372,30 @@
}
}
+// 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) {
+ SmallPtrSet<const SDNode *, 16> Visited;
+ SmallVector<const SDNode *, 8> Worklist;
+ // search ops of store candidates
+ for (unsigned i = 0; i < StoreNodes.size(); ++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
+ for (unsigned i = 0; i < StoreNodes.size(); ++i) {
+ if (SDNode::hasPredecessorHelper(StoreNodes[i].MemNode, Visited, Worklist))
+ return false;
+ }
+ return true;
+}
+
bool DAGCombiner::MergeConsecutiveStores(StoreSDNode* St) {
if (OptLevel == CodeGenOpt::None)
return false;
@@ -11418,6 +11449,12 @@
if (StoreNodes.size() < 2)
return false;
+ // only do dep endence check in AA case
+ bool UseAA = CombinerAA.getNumOccurrences() > 0 ? CombinerAA
+ : DAG.getSubtarget().useAA();
+ if (UseAA && !checkMergeStoreCandidatesForDependencies(StoreNodes))
+ return false;
+
// Sort the memory operands according to their distance from the
// base pointer. As a secondary criteria: make sure stores coming
// later in the code come first in the list. This is important for
diff --git a/llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp b/llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
index c24999b..9357581 100644
--- a/llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
@@ -11,7 +11,6 @@
//
//===----------------------------------------------------------------------===//
-#include "llvm/CodeGen/SelectionDAG.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
@@ -20,6 +19,8 @@
#include "llvm/CodeGen/Analysis.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineJumpTableInfo.h"
+#include "llvm/CodeGen/SelectionDAG.h"
+#include "llvm/CodeGen/SelectionDAGNodes.h"
#include "llvm/IR/CallingConv.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
@@ -1471,7 +1472,7 @@
// Caches for hasPredecessorHelper
SmallPtrSet<const SDNode *, 32> Visited;
SmallVector<const SDNode *, 16> Worklist;
-
+ Worklist.push_back(Idx.getNode());
SDValue StackPtr, Ch;
for (SDNode::use_iterator UI = Vec.getNode()->use_begin(),
UE = Vec.getNode()->use_end(); UI != UE; ++UI) {
@@ -1489,7 +1490,7 @@
// If the index is dependent on the store we will introduce a cycle when
// creating the load (the load uses the index, and by replacing the chain
// we will make the index dependent on the load).
- if (Idx.getNode()->hasPredecessorHelper(ST, Visited, Worklist))
+ if (SDNode::hasPredecessorHelper(ST, Visited, Worklist))
continue;
StackPtr = ST->getBasePtr();
diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index 2daae13..ebf49b9 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -6866,47 +6866,13 @@
return false;
}
-/// hasPredecessor - Return true if N is a predecessor of this node.
-/// N is either an operand of this node, or can be reached by recursively
-/// traversing up the operands.
-/// NOTE: This is an expensive method. Use it carefully.
bool SDNode::hasPredecessor(const SDNode *N) const {
SmallPtrSet<const SDNode *, 32> Visited;
SmallVector<const SDNode *, 16> Worklist;
+ Worklist.push_back(this);
return hasPredecessorHelper(N, Visited, Worklist);
}
-bool
-SDNode::hasPredecessorHelper(const SDNode *N,
- SmallPtrSetImpl<const SDNode *> &Visited,
- SmallVectorImpl<const SDNode *> &Worklist) const {
- if (Visited.empty()) {
- Worklist.push_back(this);
- } else {
- // Take a look in the visited set. If we've already encountered this node
- // we needn't search further.
- if (Visited.count(N))
- return true;
- }
-
- // Haven't visited N yet. Continue the search.
- while (!Worklist.empty()) {
- const SDNode *M = Worklist.pop_back_val();
- bool Found = false;
- for (const SDValue &OpV : M->op_values()) {
- SDNode *Op = OpV.getNode();
- if (Visited.insert(Op).second)
- Worklist.push_back(Op);
- if (Op == N)
- Found = true;
- }
- if (Found)
- return true;
- }
-
- return false;
-}
-
uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
assert(Num < NumOperands && "Invalid child # of SDNode!");
return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();