diff options
author | Hans Wennborg <hans@hanshq.net> | 2018-01-22 15:16:37 +0000 |
---|---|---|
committer | Hans Wennborg <hans@hanshq.net> | 2018-01-22 15:16:37 +0000 |
commit | d9e6eecc10dfd8a1c40aa85a276b03f41e868cac (patch) | |
tree | eb7a7794ee0728fe103edf9554982365384633e2 /unittests | |
parent | 8d72e720adbb8f3718426af9b046c5da2c3cf486 (diff) |
Merging r323034:
------------------------------------------------------------------------
r323034 | dmgreen | 2018-01-20 11:29:37 +0100 (Sat, 20 Jan 2018) | 9 lines
[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
------------------------------------------------------------------------
git-svn-id: https://llvm.org/svn/llvm-project/llvm/branches/release_60@323121 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'unittests')
-rw-r--r-- | unittests/IR/DominatorTreeBatchUpdatesTest.cpp | 95 |
1 files changed, 95 insertions, 0 deletions
diff --git a/unittests/IR/DominatorTreeBatchUpdatesTest.cpp b/unittests/IR/DominatorTreeBatchUpdatesTest.cpp index 4ad1f69030c..e362afd8404 100644 --- a/unittests/IR/DominatorTreeBatchUpdatesTest.cpp +++ b/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()); +} |