Prevent construction of cycle in DAG store merge

[niravd]

Summary

When merging stores, add checks to ensure that no data dependences are introduced. Previously we checked only chain dependencies but ignored data dependencies.
There two checks capture the differences between the cases where we use Anti-aliasing (and can limit the search chain-parallel stores) vs. when we do not and consider direct chains of stores.

[spatel]

Adding reviewers of:
http://reviews.llvm.org/D14834

Does that patch resolve this case?

[yinma]

Changing finding better chain algorithm may hide the problem fixed by this patch, but for our test case, changing the FindBetterChain algorithm doesn't help.

[niravd]

This is incomplete. It's missing the case for UseAA merges (which is also needed to resolve the underlying bug 18321/14834). I have a patch that captures this, though I haven't gotten a test which will exercises the useAA case.

Comandeering to upload patch.

[niravd]

Add check to ensuring no loops in data dependences are constructed from store merging
in the case we use Anti-aliasing analysis.

[jyknight]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

11143

I'm not sure if it's valid to use setNodeId here. But that's irrelevant, because this function shouldn't exist, since the code should be using hasPredecessor.

11167

There are formatting/spacing issues throughout this. Please clang-format.

11177

This is obfuscated; please refactor the hasPredecessor family to have a static function which requires the worklist to be pre-populated, instead of passing in a dummy node here.

11190

Should use hasPredecessor.

test/CodeGen/AArch64/vector_merge_dep_check.ll

11

This test can almost certainly be simplified. It would be nice to spend a bit of time to remove irrelevant stuff from it so it's easier to see what's actually going on is just:
%l1 = load
store half of %l1 -> offset 0
%l2 = load
store half of %l2 -> offset -1
store half of %l2 -> offset 1

And then, merging the store to offsets -1 and 0 into a single store, which results in the %l2 load chain-depending on it, but yet the merged-store requires that load as a value.

(I think)

[niravd]

Test now correctly fails without this patch and succeed with

[yinma]

Hi Nirav, I think the problem need to be solved should be the same with and without AA. It is testing the node predecessors. For your new upload, you use different check with UseAA. For my algorithm, it only tests the latest node in the store array because it is the one that links with the successors. Do you have another test case that shows failure with UseAA? What could be the different with UseAA?

[yinma]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

11169

if UseAA creates a different but broader case. we should try to merge testing with UseAA and without UsaAA to be one testing.

test/CodeGen/AArch64/vector_merge_dep_check.ll

12

My code is reduced by bugpoint, The idea is shown exactly in your suggestion.

[niravd]

• Add useAA case

[niravd]

There are two cases we do. In the case of AA we look for stores which are
parallel in regards to the chain dependencies. Otherwise we walk up the
chain to merge stores. Either way we fail to check if there are data
dependencies that we contradict (i.e. make a cycle).

Your patch handles the later case only because it relies on the fact that
all stores are predecessors to the latest one and there are not multiple
chain descendent. Thus if we walk through uses of that we implicitly are
doing the walk for all of them but it wouldn't necessarily hold in the
parallel case.

You're right about us only needing one path. We could unify them modifying
the parallel case to searching up the non-chain operands and not stores
themselves to avoid chained stores from always failing. Once D14834 is
committed the nonparallel case will disappear and we can return to the
simpler case.

[niravd]

Implement hasPredecessorHelper cleanup and merge two checks as per discussion
cleanup hasPredecessorHelper fixes and merge checks back together as per discussions

[jyknight]

include/llvm/CodeGen/SelectionDAGNodes.h

628–653

Lots of typos. Visitedo. unino. "operand_dependences" sounds like it's referring to a variable or function but isn't actually.

"Null" is strangely capitalized.

Much of the old comment you deleted seems still relevant, too.

634

Why removed the Visited check? It seems to me like that was still a more natural interface.

Then you can just ask all your "is Node X a predecessor" questions with the same interface.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

9645

Why search completely? Isn't it better to escape early if you happen to be able to?

11164–11166

This comment isn't very clear.

11172

That you're skipping the chain operand deserves a mention, here.

test/CodeGen/AArch64/vector_merge_dep_check.ll

13

Yes, I see that. It's just that there's a lot of (probably?) irrelevant metadata args which can be removed, variable names shortened/made clearer, possibly the loop could go away too.

And a comment in the test about what it is actually intending to test would be good, too.

[niravd]

Cleanup comments and revert removal of early exit in HasPredecessorHelper calls

[niravd]

Simplify test case.

[niravd]

All code and testcase comments resolved.

[jyknight]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

9693

Missed this spot.

11166

"indirectly" is in there twice.

11168

redundant "candidate".

test/CodeGen/AArch64/vector_merge_dep_check.ll

14

Still need to add comment about what the test is testing.

[niravd]

Add missing test case comment

[niravd]

test/CodeGen/AArch64/vector_merge_dep_check.ll

15

Done

[niravd]

Fix comment and stray reference for Visited.count

[niravd]

Separate check into a separate function.
Fix test case to check both AA and non-AA cases.
Do loop dependences check only in AA cases

[jyknight]

Thanks, lgtm.

Note for readers: we spent some time going over this, and noted that 1) The original test case was using UseAA mode (which we'd not noticed before) 2) The bug doesn't actually exist in !UseAA, because of the different way it traverses the chain.

So this final version reflects that.

include/llvm/CodeGen/SelectionDAGNodes.h

public:
   }
 
   /// 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 hasPredecessor(const SDNode *N) const;
 
-  /// 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.
-  /// In this helper the Visited and worklist sets are held externally to
-  /// cache predecessors over multiple invocations. If you want to test for
-  /// multiple predecessors this method is preferable to multiple calls to
-  /// hasPredecessor. Be sure to clear Visited and Worklist if the DAG
-  /// changes.
-  /// NOTE: This is still very expensive. Use carefully.
-  bool hasPredecessorHelper(const SDNode *N,
+  /// Returns true if N is a predecessor of any node in Worklist. This
+  /// helper keeps Visited and Worklist sets externally to allow unions
+  /// searches to be performed in parallel, caching of results across
+  /// queries and incremental addition to Worklist. Stops early if N is
+  /// found but will resume. Remember to clear Visited and Worklists
+  /// if DAG changes.
+  static bool hasPredecessorHelper(const SDNode *N,
                                    SmallPtrSetImpl<const SDNode *> &Visited,
-                            SmallVectorImpl<const SDNode *> &Worklist) const;
+                                   SmallVectorImpl<const SDNode *> &Worklist) {
+    if (Visited.count(N))
+      return true;
+    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;
+  }
 
   /// Return the number of values used by this operation.
   unsigned getNumOperands() const { return NumOperands; }
 
   /// Helper method returns the integer value of a ConstantSDNode operand.
   uint64_t getConstantOperandVal(unsigned Num) const;
 
   const SDValue &getOperand(unsigned Num) const {

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

private:
 
     /// This is a helper function for MergeConsecutiveStores.
     /// Stores that may be merged are placed in StoreNodes.
     /// Loads that may alias with those stores are placed in AliasLoadNodes.
     void getStoreMergeAndAliasCandidates(
         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.
     bool MergeConsecutiveStores(StoreSDNode *N);
 
     /// \brief Try to transform a truncation where C is a constant:
     ///     (trunc (and X, C)) -> (and (trunc X), (trunc C))
     ///
if (!isLoad) {
     SDValue Val = cast<StoreSDNode>(N)->getValue();
     if (Val == BasePtr || BasePtr.getNode()->isPredecessorOf(Val.getNode()))
       return false;
   }
 
   // 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
   // a copy of the original base pointer.
   SmallVector<SDNode *, 16> OtherUses;
   if (isa<ConstantSDNode>(Offset))
     for (SDNode::use_iterator UI = BasePtr.getNode()->use_begin(),
                               UE = BasePtr.getNode()->use_end();
          UI != UE; ++UI) {
       SDUse &Use = UI.getUse();
       // Skip the use that is Ptr and uses of other results from BasePtr's
       // node (important for nodes that return multiple results).
       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 &&
           Use.getUser()->getOpcode() != ISD::SUB) {
         OtherUses.clear();
         break;
       }
 
if (Swapped)
     std::swap(BasePtr, Offset);
 
   // Now check for #3 and #4.
   bool RealUse = false;
 
   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
     // not profitable to do this transformation.
     if (!canFoldInAddressingMode(Ptr.getNode(), Use, DAG, TLI))
       RealUse = true;
   }
 
SDValue DAGCombiner::getMergedConstantVectorStore(SelectionDAG &DAG,
   return DAG.getNode(ISD::BUILD_VECTOR, SL, Ty, BuildVector);
 }
 
 bool DAGCombiner::MergeStoresOfConstantsOrVecElts(
                   SmallVectorImpl<MemOpLink> &StoreNodes, EVT MemVT,
                   unsigned NumStores, bool IsConstantSrc, bool UseVector) {
   // Make sure we have something to merge.
   if (NumStores < 2)
     return false;
 
   int64_t ElementSizeBytes = MemVT.getSizeInBits() / 8;
   LSBaseSDNode *FirstInChain = StoreNodes[0].MemNode;
   unsigned LatestNodeUsed = 0;
 
   for (unsigned i=0; i < NumStores; ++i) {
     // Find a chain for the new wide-store operand. Notice that some
     // of the store nodes that we found may not be selected for inclusion
     // in the wide store. The chain we use needs to be the chain of the
     // latest store node which is *used* and replaced by the wide store.
     if (StoreNodes[i].SequenceNum < StoreNodes[LatestNodeUsed].SequenceNum)
       LatestNodeUsed = i;
   }
 
   SmallVector<SDValue, 8> Chains;
 
   // The latest Node in the DAG.
   LSBaseSDNode *LatestOp = StoreNodes[LatestNodeUsed].MemNode;
   SDLoc DL(StoreNodes[0].MemNode);
 
   SDValue StoredVal;
   if (UseVector) {
     bool IsVec = MemVT.isVector();
     unsigned Elts = NumStores;
     if (IsVec) {
       // When merging vector stores, get the total number of elements.
       Elts *= MemVT.getVectorNumElements();
     }
     // Get the type for the merged vector store.
     EVT Ty = EVT::getVectorVT(*DAG.getContext(), MemVT.getScalarType(), Elts);
     assert(TLI.isTypeLegal(Ty) && "Illegal vector store");
 
     if (IsConstantSrc) {
       StoredVal = getMergedConstantVectorStore(DAG, DL, StoreNodes, Chains, Ty);
     } else {
       SmallVector<SDValue, 8> Ops;
       for (unsigned i = 0; i < NumStores; ++i) {
         StoreSDNode *St = cast<StoreSDNode>(StoreNodes[i].MemNode);
         SDValue Val = St->getValue();
         // All operands of BUILD_VECTOR / CONCAT_VECTOR must have the same type.
         if (Val.getValueType() != MemVT)
           return false;
         Ops.push_back(Val);
         Chains.push_back(St->getChain());
       }
 
       // Build the extracted vector elements back into a vector.
       StoredVal = DAG.getNode(IsVec ? ISD::CONCAT_VECTORS : ISD::BUILD_VECTOR,
                               DL, Ty, Ops);    }
   } else {
     // We should always use a vector store when merging extracted vector
     // elements, so this path implies a store of constants.
     assert(IsConstantSrc && "Merged vector elements should use vector store");
 
     unsigned SizeInBits = NumStores * ElementSizeBytes * 8;
while (1) {
       } else {
         Index = nullptr;
         break;
       }
     }
   }
 }
 
+
+// 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;
 
   EVT MemVT = St->getMemoryVT();
   int64_t ElementSizeBytes = MemVT.getSizeInBits() / 8;
   bool NoVectors = DAG.getMachineFunction().getFunction()->hasFnAttribute(
       Attribute::NoImplicitFloat);
bool DAGCombiner::MergeConsecutiveStores(StoreSDNode* St) {
   SmallVector<MemOpLink, 8> StoreNodes;
 
   getStoreMergeAndAliasCandidates(St, StoreNodes, AliasLoadNodes);
 
   // Check if there is anything to merge.
   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
   // the non-UseAA case, because we're merging stores into the FINAL
   // store along a chain which potentially contains aliasing stores.
   // Thus, if there are multiple stores to the same address, the last
   // one can be considered for merging but not the others.
   std::sort(StoreNodes.begin(), StoreNodes.end(),

lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

 //===-- LegalizeDAG.cpp - Implement SelectionDAG::Legalize ----------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the SelectionDAG::Legalize method.
 //
 //===----------------------------------------------------------------------===//
 
-#include "llvm/CodeGen/SelectionDAG.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Triple.h"
 #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"
 #include "llvm/IR/DebugInfo.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/Support/Debug.h"
SDValue SelectionDAGLegalize::ExpandExtractFromVectorThroughStack(SDValue Op) {
   // vector operations (using SelectionDAG::UnrollVectorOp for example) a whole
   // series of EXTRACT_VECTOR_ELT nodes are generated, one for each element in
   // the vector. If all are expanded here, we don't want one store per vector
   // element.
 
   // 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) {
     SDNode *User = *UI;
     if (StoreSDNode *ST = dyn_cast<StoreSDNode>(User)) {
       if (ST->isIndexed() || ST->isTruncatingStore() ||
           ST->getValue() != Vec)
         continue;
 
       // Make sure that nothing else could have stored into the destination of
       // this store.
       if (!ST->getChain().reachesChainWithoutSideEffects(DAG.getEntryNode()))
         continue;
 
       // 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();
       Ch = SDValue(ST, 0);
       break;
     }
   }
 

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
   // Loads don't have side effects, look through them.
   if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
     if (!Ld->isVolatile())
       return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
   }
   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;
-  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;
+  return hasPredecessorHelper(N, Visited, Worklist);
 }
 
 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
   assert(Num < NumOperands && "Invalid child # of SDNode!");
   return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
 }
 
 const SDNodeFlags *SDNode::getFlags() const {

test/CodeGen/AArch64/vector_merge_dep_check.ll

+; RUN: llc --combiner-alias-analysis=false < %s | FileCheck %s
+; RUN: llc --combiner-alias-analysis=true  < %s | FileCheck %s
+
+; This test checks that we do not merge stores together which have
+; dependencies through their non-chain operands (e.g. one store is the
+; chain ancestor of a load whose value is used in as the data for the
+; other store). Merging in such cases creates a loop in the DAG.
+
+target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64--linux-android"
+
+%"class.std::__1::complex.0.20.56.60.64.72.76.88.92.112.140.248" = type { float, float }
+
+; Function Attrs: noinline norecurse nounwind ssp uwtable
+define void @fn(<2 x i64>* %argA, <2 x i64>* %argB, i64* %a) #0 align 2 {
+  %_p_vec_full = load <2 x i64>, <2 x i64>* %argA, align 4, !alias.scope !1, !noalias !3
+  %x = extractelement <2 x i64> %_p_vec_full, i32 1
+  store i64 %x, i64* %a, align 8, !alias.scope !4, !noalias !9
+  %_p_vec_full155 = load <2 x i64>, <2 x i64>* %argB, align 4, !alias.scope !1, !noalias !3
+  %y = extractelement <2 x i64> %_p_vec_full155, i32 0
+  %scevgep41 = getelementptr i64, i64* %a, i64 -1
+  store i64 %y, i64* %scevgep41, align 8, !alias.scope !4, !noalias !9
+  ret void
+}
+
+; CHECK: ret
+
+attributes #0 = { noinline norecurse nounwind ssp uwtable "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "polly-optimized" "stack-protector-buffer-size"="8" "target-features"="+crc,+crypto,+neon" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!llvm.ident = !{!0}
+
+!0 = !{!"Snapdragon LLVM ARM Compiler 3.8.0 (based on LLVM 3.8.0)"}
+!1 = distinct !{!1, !2, !"polly.alias.scope.rhs"}
+!2 = distinct !{!2, !"polly.alias.scope.domain"}
+!3 = !{!4, !5, !6, !7, !8}
+!4 = distinct !{!4, !2, !"polly.alias.scope.blockB"}
+!5 = distinct !{!5, !2, !"polly.alias.scope.add28.lcssa.reg2mem"}
+!6 = distinct !{!6, !2, !"polly.alias.scope.count.0.lcssa.reg2mem"}
+!7 = distinct !{!7, !2, !"polly.alias.scope.mul"}
+!8 = distinct !{!8, !2, !"polly.alias.scope.add28.us.lcssa.reg2mem"}
+!9 = !{!1, !5, !6, !7, !8}