[SelectionDAG] Fix CombineToPreIndexedLoadStore O(n^2) behavior

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.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@259691 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 25 insertions, 0 deletions

diff --git a/test/CodeGen/PowerPC/combine-to-pre-index-store-crash.ll b/test/CodeGen/PowerPC/combine-to-pre-index-store-crash.ll
new file mode 100644
index 00000000000..9bd0dd874b4
--- /dev/null
+++ b/test/CodeGen/PowerPC/combine-to-pre-index-store-crash.ll
@@ -0,0 +1,25 @@
+; RUN: llc -mtriple=powerpc64le-unknown-linux-gnu < %s | FileCheck %s
+
+; CHECK-LABEL: TestFoo:
+; CHECK: std
+; CHECK: bl TestBar
+; CHECK: stbu
+; CHECK: std
+; CHECK: blr
+
+%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()