Fix PR6047

Nodes that had children outside of the post dominator tree (infinite loops)
where removed from the post dominator tree. This seems to be wrong. Leave them
in the tree.

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

5 files changed, 206 insertions, 13 deletions

diff --git a/include/llvm/Analysis/DominatorInternals.h b/include/llvm/Analysis/DominatorInternals.h
index 5ecb348144..8cea96d356 100644
--- a/include/llvm/Analysis/DominatorInternals.h
+++ b/include/llvm/Analysis/DominatorInternals.h
@@ -262,29 +262,17 @@ void Calculate(DominatorTreeBase<typename GraphTraits<NodeT>::NodeType>& DT,
                                                                      DT.Info[W];
 
     // Step #2: Calculate the semidominators of all vertices
-    bool HasChildOutsideDFS = false;
 
     // initialize the semi dominator to point to the parent node
     WInfo.Semi = WInfo.Parent;
     for (typename GraphTraits<Inverse<NodeT> >::ChildIteratorType CI =
          GraphTraits<Inverse<NodeT> >::child_begin(W),
-         E = GraphTraits<Inverse<NodeT> >::child_end(W); CI != E; ++CI) {
+         E = GraphTraits<Inverse<NodeT> >::child_end(W); CI != E; ++CI)
       if (DT.Info.count(*CI)) {  // Only if this predecessor is reachable!
         unsigned SemiU = DT.Info[Eval<GraphT>(DT, *CI)].Semi;
         if (SemiU < WInfo.Semi)
           WInfo.Semi = SemiU;
       }
-      else {
-        // if the child has no DFS number it is not post-dominated by any exit, 
-        // and so is the current block.
-        HasChildOutsideDFS = true;
-      }
-    }
-
-    // if some child has no DFS number it is not post-dominated by any exit, 
-    // and so is the current block.
-    if (DT.isPostDominator() && HasChildOutsideDFS)
-      WInfo.Semi = 0;
 
     DT.Info[DT.Vertex[WInfo.Semi]].Bucket.push_back(W);
 
diff --git a/test/Analysis/PostDominators/pr6047_a.ll b/test/Analysis/PostDominators/pr6047_a.ll
new file mode 100644
index 0000000000..ec1455b46f
--- /dev/null
+++ b/test/Analysis/PostDominators/pr6047_a.ll
@@ -0,0 +1,15 @@
+; RUN: opt < %s -postdomtree -analyze | FileCheck %s
+define internal void @f() {
+entry:
+  br i1 undef, label %bb35, label %bb3.i
+
+bb3.i:
+  br label %bb3.i
+
+bb35.loopexit3:
+  br label %bb35
+
+bb35:
+  ret void
+}
+; CHECK: [3] %entry
diff --git a/test/Analysis/PostDominators/pr6047_b.ll b/test/Analysis/PostDominators/pr6047_b.ll
new file mode 100644
index 0000000000..7bd2c86b73
--- /dev/null
+++ b/test/Analysis/PostDominators/pr6047_b.ll
@@ -0,0 +1,19 @@
+; RUN: opt < %s -postdomtree -analyze | FileCheck %s
+define internal void @f() {
+entry:
+  br i1 undef, label %a, label %bb3.i
+
+a:
+  br i1 undef, label %bb35, label %bb3.i
+
+bb3.i:
+  br label %bb3.i
+
+
+bb35.loopexit3:
+  br label %bb35
+
+bb35:
+  ret void
+}
+; CHECK: [4] %entry
diff --git a/test/Analysis/PostDominators/pr6047_c.ll b/test/Analysis/PostDominators/pr6047_c.ll
new file mode 100644
index 0000000000..08c9551f15
--- /dev/null
+++ b/test/Analysis/PostDominators/pr6047_c.ll
@@ -0,0 +1,147 @@
+; RUN: opt < %s -postdomtree -analyze | FileCheck %s
+define internal void @f() {
+entry:
+  br i1 undef, label %bb35, label %bb3.i
+
+bb3.i:
+  br label %bb3.i
+
+bb:
+  br label %bb35
+
+bb.i:
+  br label %bb35
+
+_float32_unpack.exit:
+  br label %bb35
+
+bb.i5:
+  br label %bb35
+
+_float32_unpack.exit8:
+  br label %bb35
+
+bb32.preheader:
+  br label %bb35
+
+bb3:
+  br label %bb35
+
+bb3.split.us:
+  br label %bb35
+
+bb.i4.us:
+  br label %bb35
+
+bb7.i.us:
+  br label %bb35
+
+bb.i4.us.backedge:
+  br label %bb35
+
+bb1.i.us:
+  br label %bb35
+
+bb6.i.us:
+  br label %bb35
+
+bb4.i.us:
+  br label %bb35
+
+bb8.i.us:
+  br label %bb35
+
+bb3.i.loopexit.us:
+  br label %bb35
+
+bb.nph21:
+  br label %bb35
+
+bb4:
+  br label %bb35
+
+bb5:
+  br label %bb35
+
+bb14.preheader:
+  br label %bb35
+
+bb.nph18:
+  br label %bb35
+
+bb8.us.preheader:
+  br label %bb35
+
+bb8.preheader:
+  br label %bb35
+
+bb8.us:
+  br label %bb35
+
+bb8:
+  br label %bb35
+
+bb15.loopexit:
+  br label %bb35
+
+bb15.loopexit2:
+  br label %bb35
+
+bb15:
+  br label %bb35
+
+bb16:
+  br label %bb35
+
+bb17.loopexit.split:
+  br label %bb35
+
+bb.nph14:
+  br label %bb35
+
+bb19:
+  br label %bb35
+
+bb20:
+  br label %bb35
+
+bb29.preheader:
+  br label %bb35
+
+bb.nph:
+  br label %bb35
+
+bb23.us.preheader:
+  br label %bb35
+
+bb23.preheader:
+  br label %bb35
+
+bb23.us:
+  br label %bb35
+
+bb23:
+  br label %bb35
+
+bb30.loopexit:
+  br label %bb35
+
+bb30.loopexit1:
+  br label %bb35
+
+bb30:
+  br label %bb35
+
+bb31:
+  br label %bb35
+
+bb35.loopexit:
+  br label %bb35
+
+bb35.loopexit3:
+  br label %bb35
+
+bb35:
+  ret void
+}
+; CHECK: [3] %entry
diff --git a/test/Analysis/PostDominators/pr6047_d.ll b/test/Analysis/PostDominators/pr6047_d.ll
new file mode 100644
index 0000000000..4cfa88029a
--- /dev/null
+++ b/test/Analysis/PostDominators/pr6047_d.ll
@@ -0,0 +1,24 @@
+; RUN: opt < %s -postdomtree -analyze | FileCheck %s
+define internal void @f() {
+entry:
+  br i1 1, label %a, label %b
+
+a:
+br label %c
+
+b:
+br label %c
+
+c:
+  br i1 undef, label %bb35, label %bb3.i
+
+bb3.i:
+  br label %bb3.i
+
+bb35.loopexit3:
+  br label %bb35
+
+bb35:
+  ret void
+}
+; CHECK: [4] %entry