[Dominators] Fix some edge cases for PostDomTree updating

These fix some odd cfg cases where batch-updating the post
dom tree fails. Usually around infinite loops and roots
ending up being different.

Differential Revision: https://reviews.llvm.org/D42247

llvm-svn: 323034

1 files changed, 95 insertions, 0 deletions

diff --git a/llvm/unittests/IR/DominatorTreeBatchUpdatesTest.cpp b/llvm/unittests/IR/DominatorTreeBatchUpdatesTest.cpp
index 4ad1f69030c..e362afd8404 100644
--- a/llvm/unittests/IR/DominatorTreeBatchUpdatesTest.cpp
+++ b/llvm/unittests/IR/DominatorTreeBatchUpdatesTest.cpp
@@ -258,3 +258,98 @@ TEST(DominatorTreeBatchUpdates, InsertDeleteExhaustive) {
     EXPECT_TRUE(PDT.verify());
   }
 }
+
+// These are some odd flowgraphs, usually generated from csmith cases,
+// which are difficult on post dom trees.
+TEST(DominatorTreeBatchUpdates, InfiniteLoop) {
+  std::vector<CFGBuilder::Arc> Arcs = {
+      {"1", "2"},
+      {"2", "3"},
+      {"3", "6"}, {"3", "5"},
+      {"4", "5"},
+      {"5", "2"},
+      {"6", "3"}, {"6", "4"}};
+
+  // SplitBlock on 3 -> 5
+  std::vector<CFGBuilder::Update> Updates = {
+      {CFGInsert, {"N", "5"}},  {CFGInsert, {"3", "N"}}, {CFGDelete, {"3", "5"}}};
+
+  CFGHolder Holder;
+  CFGBuilder B(Holder.F, Arcs, Updates);
+  DominatorTree DT(*Holder.F);
+  EXPECT_TRUE(DT.verify());
+  PostDomTree PDT(*Holder.F);
+  EXPECT_TRUE(PDT.verify());
+
+  while (B.applyUpdate())
+    ;
+
+  auto DomUpdates = ToDomUpdates(B, Updates);
+  DT.applyUpdates(DomUpdates);
+  EXPECT_TRUE(DT.verify());
+  PDT.applyUpdates(DomUpdates);
+  EXPECT_TRUE(PDT.verify());
+}
+
+TEST(DominatorTreeBatchUpdates, DeadBlocks) {
+  std::vector<CFGBuilder::Arc> Arcs = {
+      {"1", "2"},
+      {"2", "3"},
+      {"3", "4"}, {"3", "7"},
+      {"4", "4"},
+      {"5", "6"}, {"5", "7"},
+      {"6", "7"},
+      {"7", "2"}, {"7", "8"}};
+
+  // Remove dead 5 and 7,
+  // plus SplitBlock on 7 -> 8
+  std::vector<CFGBuilder::Update> Updates = {
+      {CFGDelete, {"6", "7"}},  {CFGDelete, {"5", "7"}}, {CFGDelete, {"5", "6"}},
+      {CFGInsert, {"N", "8"}},  {CFGInsert, {"7", "N"}}, {CFGDelete, {"7", "8"}}};
+
+  CFGHolder Holder;
+  CFGBuilder B(Holder.F, Arcs, Updates);
+  DominatorTree DT(*Holder.F);
+  EXPECT_TRUE(DT.verify());
+  PostDomTree PDT(*Holder.F);
+  EXPECT_TRUE(PDT.verify());
+
+  while (B.applyUpdate())
+    ;
+
+  auto DomUpdates = ToDomUpdates(B, Updates);
+  DT.applyUpdates(DomUpdates);
+  EXPECT_TRUE(DT.verify());
+  PDT.applyUpdates(DomUpdates);
+  EXPECT_TRUE(PDT.verify());
+}
+
+TEST(DominatorTreeBatchUpdates, InfiniteLoop2) {
+  std::vector<CFGBuilder::Arc> Arcs = {
+      {"1", "2"},
+      {"2", "6"}, {"2", "3"},
+      {"3", "4"},
+      {"4", "5"}, {"4", "6"},
+      {"5", "4"},
+      {"6", "2"}};
+
+  // SplitBlock on 4 -> 6
+  std::vector<CFGBuilder::Update> Updates = {
+      {CFGInsert, {"N", "6"}},  {CFGInsert, {"4", "N"}}, {CFGDelete, {"4", "6"}}};
+
+  CFGHolder Holder;
+  CFGBuilder B(Holder.F, Arcs, Updates);
+  DominatorTree DT(*Holder.F);
+  EXPECT_TRUE(DT.verify());
+  PostDomTree PDT(*Holder.F);
+  EXPECT_TRUE(PDT.verify());
+
+  while (B.applyUpdate())
+    ;
+
+  auto DomUpdates = ToDomUpdates(B, Updates);
+  DT.applyUpdates(DomUpdates);
+  EXPECT_TRUE(DT.verify());
+  PDT.applyUpdates(DomUpdates);
+  EXPECT_TRUE(PDT.verify());
+}