Fix CombineToPreIndexedLoadStore O(n^2) behavior

[timshen]

Summary

This patch consists of two parts: a performance fix in DAGCombiner.cpp and a correctness fix in SelectionDAG.cpp.

The test case tests the bug that's uncovered by the performance fix, and fixed by the correctness fix.

The performance fix keeps the containers required by the hasPredecessorHelper (which is a lazy DFS) and reuse them. Since hasPredecessorHelper is called in a loop, the overall efficiency reduced from O(n^2) to O(n), where n is the number of SDNodes.

The correctness fix keeps iterating the neighbor list even if it's time to early return. It will return after finishing adding all neighbors to Worklist, so that no neighbors are discarded due to the original early return.

[iteratee]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

9596

Can you add a const annotation to N so that this is obviously correct?

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

6937

Can you add some header comments for hasPredecessorHelper while you're here?

[timshen]

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

6937

I agree with you in technical perspective, but it's conventional not to make a function parameter passed by const value for reasons I don't quite know :P.

Another solution is to make a local const copy of N and use that, but then it's confusing in another way, since there are more variables.

[timshen]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

9596

I agree with you in technical perspective, but it's conventional not to make a function parameter passed by const value for reasons I don't quite know :P.

Another solution is to make a local const copy of N and use that, but then it's confusing in another way, since there are more variables.

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

6937

Sorry - above is the reply for the previous comment.

For this comment - I think we already got complete comment in include/llvm/CodeGen/SelectionDAGNodes.h

[iteratee]

I'm OK with this. If you can find someone in the next few days that's more familiar with this, that would be good, but It looks just fine to me.

[timshen]

Added hfinkel for a double check - got the name from git blame.

[timshen]

Modify test to take input from stdin.

[majnemer]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

9596

Comments should be complete sentences.

9614

Please format this with clang-format

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

6958

Please clang-format this.

6960

And this.

test/CodeGen/PowerPC/combine-to-pre-index-store-crash.ll

2

No FileCheck lines?

[timshen]

Update format and comment.

[timshen]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

9614

I was using a very old version. Re-formanted using trunk version. Thanks!

test/CodeGen/PowerPC/combine-to-pre-index-store-crash.ll

2

Yes, the error is a crash, as the file name indicates

[echristo]

test/CodeGen/PowerPC/combine-to-pre-index-store-crash.ll

3

In general you should still check that the correct code is generated out of the other end if you can.

[timshen]

Add CHECKs for test.

[timshen]

test/CodeGen/PowerPC/combine-to-pre-index-store-crash.ll

4

I didn't put very specific logic check into the test, since that may cause brittle test.

[hfinkel]

LGTM too.

[timshen]

Committed as r259691.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

bool DAGCombiner::CombineToPreIndexedLoadStore(SDNode *N) {
 
   // Check #2.
   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;
+
   // 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 (Use.getUser()->isPredecessorOf(N))
-        continue;
+      if (N->hasPredecessorHelper(Use.getUser(), Visited, Worklist)) continue;
 
       if (Use.getUser()->getOpcode() != ISD::ADD &&
           Use.getUser()->getOpcode() != ISD::SUB) {
         OtherUses.clear();
         break;
       }
 
       SDValue Op1 = Use.getUser()->getOperand((UI.getOperandNo() + 1) & 1);
if (isa<ConstantSDNode>(Offset))
     }
 
   if (Swapped)
     std::swap(BasePtr, Offset);
 
   // Now check for #3 and #4.
   bool RealUse = false;
 
-  // Caches for hasPredecessorHelper
-  SmallPtrSet<const SDNode *, 32> Visited;
-  SmallVector<const SDNode *, 16> Worklist;
-
   for (SDNode *Use : Ptr.getNode()->uses()) {
     if (Use == N)
       continue;
     if (N->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.

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

 /// 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)
-        return true;
+      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();

test/CodeGen/PowerPC/combine-to-pre-index-store-crash.ll

+; RUN: llc %s
+target datalayout = "e-m:e-i64:64-n32:64"
+target triple = "powerpc64le-grtev4-linux-gnu"
+
+%StructA = type <{ i64, { i64, i64 }, { i64, i64 } }>
+
+define void @TestFoo(%StructA* %this) {
+  %tmp = getelementptr inbounds %StructA, %StructA* %this, i64 0, i32 1
+  %tmp11 = getelementptr inbounds %StructA, %StructA* %this, i64 0, i32 1, i32 1
+  %tmp12 = bitcast { i64, i64 }* %tmp to i64**
+  store i64* %tmp11, i64** %tmp12
+  call void @TestBar()
+  %tmp13 = getelementptr inbounds %StructA, %StructA* %this, i64 0, i32 2, i32 1
+  store i64* %tmp13, i64** undef
+  %.cast.i.i.i = bitcast i64* %tmp13 to i8*
+  store i8 0, i8* %.cast.i.i.i
+  ret void
+}
+
+declare void @TestBar()