diff options
Diffstat (limited to 'llvm/lib/CodeGen/SelectionDAG')
| -rw-r--r-- | llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp | 41 | ||||
| -rw-r--r-- | llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp | 7 | ||||
| -rw-r--r-- | llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp | 36 |
3 files changed, 44 insertions, 40 deletions
diff --git a/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp b/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp index 0aecaa44005..09c7971c97d 100644 --- a/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp +++ b/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp @@ -448,6 +448,12 @@ namespace { 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 @@ bool DAGCombiner::CombineToPreIndexedLoadStore(SDNode *N) { // 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 @@ bool DAGCombiner::CombineToPreIndexedLoadStore(SDNode *N) { 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 @@ bool DAGCombiner::CombineToPreIndexedLoadStore(SDNode *N) { 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 @@ void DAGCombiner::getStoreMergeAndAliasCandidates( } } +// 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 @@ bool DAGCombiner::MergeConsecutiveStores(StoreSDNode* St) { 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 c24999b06dd..9357581ed6a 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 @@ SDValue SelectionDAGLegalize::ExpandExtractFromVectorThroughStack(SDValue Op) { // 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 @@ SDValue SelectionDAGLegalize::ExpandExtractFromVectorThroughStack(SDValue Op) { // 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 2daae135045..ebf49b985a3 100644 --- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp +++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp @@ -6866,47 +6866,13 @@ bool SDValue::reachesChainWithoutSideEffects(SDValue Dest, 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(); |
