summaryrefslogtreecommitdiff
path: root/unittests/IR/DominatorTreeBatchUpdatesTest.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'unittests/IR/DominatorTreeBatchUpdatesTest.cpp')
-rw-r--r--unittests/IR/DominatorTreeBatchUpdatesTest.cpp128
1 files changed, 110 insertions, 18 deletions
diff --git a/unittests/IR/DominatorTreeBatchUpdatesTest.cpp b/unittests/IR/DominatorTreeBatchUpdatesTest.cpp
index 4ad1f69030c1..85308685e5dd 100644
--- a/unittests/IR/DominatorTreeBatchUpdatesTest.cpp
+++ b/unittests/IR/DominatorTreeBatchUpdatesTest.cpp
@@ -22,13 +22,10 @@ namespace {
const auto CFGInsert = CFGBuilder::ActionKind::Insert;
const auto CFGDelete = CFGBuilder::ActionKind::Delete;
-struct PostDomTree : PostDomTreeBase<BasicBlock> {
- PostDomTree(Function &F) { recalculate(F); }
-};
using DomUpdate = DominatorTree::UpdateType;
static_assert(
- std::is_same<DomUpdate, PostDomTree::UpdateType>::value,
+ std::is_same<DomUpdate, PostDominatorTree::UpdateType>::value,
"Trees differing only in IsPostDom should have the same update types");
using DomSNCA = DomTreeBuilder::SemiNCAInfo<DomTreeBuilder::BBDomTree>;
using PostDomSNCA = DomTreeBuilder::SemiNCAInfo<DomTreeBuilder::BBPostDomTree>;
@@ -62,9 +59,9 @@ TEST(DominatorTreeBatchUpdates, LegalizeDomUpdates) {
{Insert, B, D}, {Delete, C, D}, {Delete, A, B}};
SmallVector<DomUpdate, 4> Legalized;
DomSNCA::LegalizeUpdates(Updates, Legalized);
- DEBUG(dbgs() << "Legalized updates:\t");
- DEBUG(for (auto &U : Legalized) dbgs() << U << ", ");
- DEBUG(dbgs() << "\n");
+ LLVM_DEBUG(dbgs() << "Legalized updates:\t");
+ LLVM_DEBUG(for (auto &U : Legalized) dbgs() << U << ", ");
+ LLVM_DEBUG(dbgs() << "\n");
EXPECT_EQ(Legalized.size(), 3UL);
EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, B, C}), Legalized.end());
EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, B, D}), Legalized.end());
@@ -85,9 +82,9 @@ TEST(DominatorTreeBatchUpdates, LegalizePostDomUpdates) {
{Insert, B, D}, {Delete, C, D}, {Delete, A, B}};
SmallVector<DomUpdate, 4> Legalized;
PostDomSNCA::LegalizeUpdates(Updates, Legalized);
- DEBUG(dbgs() << "Legalized postdom updates:\t");
- DEBUG(for (auto &U : Legalized) dbgs() << U << ", ");
- DEBUG(dbgs() << "\n");
+ LLVM_DEBUG(dbgs() << "Legalized postdom updates:\t");
+ LLVM_DEBUG(for (auto &U : Legalized) dbgs() << U << ", ");
+ LLVM_DEBUG(dbgs() << "\n");
EXPECT_EQ(Legalized.size(), 3UL);
EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, C, B}), Legalized.end());
EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, D, B}), Legalized.end());
@@ -100,8 +97,8 @@ TEST(DominatorTreeBatchUpdates, SingleInsertion) {
DominatorTree DT(*Holder.F);
EXPECT_TRUE(DT.verify());
- PostDomTree PDT(*Holder.F);
- EXPECT_TRUE(DT.verify());
+ PostDominatorTree PDT(*Holder.F);
+ EXPECT_TRUE(PDT.verify());
BasicBlock *B = Builder.getOrAddBlock("B");
BasicBlock *C = Builder.getOrAddBlock("C");
@@ -122,8 +119,8 @@ TEST(DominatorTreeBatchUpdates, SingleDeletion) {
DominatorTree DT(*Holder.F);
EXPECT_TRUE(DT.verify());
- PostDomTree PDT(*Holder.F);
- EXPECT_TRUE(DT.verify());
+ PostDominatorTree PDT(*Holder.F);
+ EXPECT_TRUE(PDT.verify());
BasicBlock *B = Builder.getOrAddBlock("B");
BasicBlock *C = Builder.getOrAddBlock("C");
@@ -148,7 +145,7 @@ TEST(DominatorTreeBatchUpdates, FewInsertion) {
DominatorTree DT(*Holder.F);
EXPECT_TRUE(DT.verify());
- PostDomTree PDT(*Holder.F);
+ PostDominatorTree PDT(*Holder.F);
EXPECT_TRUE(PDT.verify());
BasicBlock *B = Builder.getOrAddBlock("B");
@@ -181,7 +178,7 @@ TEST(DominatorTreeBatchUpdates, FewDeletions) {
DominatorTree DT(*Holder.F);
EXPECT_TRUE(DT.verify());
- PostDomTree PDT(*Holder.F);
+ PostDominatorTree PDT(*Holder.F);
EXPECT_TRUE(PDT.verify());
auto Updates = ToDomUpdates(Builder, CFGUpdates);
@@ -212,7 +209,7 @@ TEST(DominatorTreeBatchUpdates, InsertDelete) {
CFGBuilder B(Holder.F, Arcs, Updates);
DominatorTree DT(*Holder.F);
EXPECT_TRUE(DT.verify());
- PostDomTree PDT(*Holder.F);
+ PostDominatorTree PDT(*Holder.F);
EXPECT_TRUE(PDT.verify());
while (B.applyUpdate())
@@ -245,7 +242,7 @@ TEST(DominatorTreeBatchUpdates, InsertDeleteExhaustive) {
CFGBuilder B(Holder.F, Arcs, Updates);
DominatorTree DT(*Holder.F);
EXPECT_TRUE(DT.verify());
- PostDomTree PDT(*Holder.F);
+ PostDominatorTree PDT(*Holder.F);
EXPECT_TRUE(PDT.verify());
while (B.applyUpdate())
@@ -258,3 +255,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());
+ PostDominatorTree 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());
+ PostDominatorTree 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());
+ PostDominatorTree 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());
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-09 01:45:10 +0000