diff options
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()); +} |