Index: llvm/trunk/unittests/IR/DominatorTreeTest.cpp =================================================================== --- llvm/trunk/unittests/IR/DominatorTreeTest.cpp +++ llvm/trunk/unittests/IR/DominatorTreeTest.cpp @@ -326,6 +326,274 @@ }); } +// Verify that the PDT is correctly updated in case an edge removal results +// in a new unreachable CFG node. +// +// For the following input code and initial PDT: +// +// CFG PDT +// +// A Exit +// | | +// _B D +// / | \ | +// ^ v \ B +// \ / D / \ +// C \ C A +// v +// Exit +// +// we verify that CFG' and PDT-updated is obtained after removal of edge C -> B. +// +// CFG' PDT-updated +// +// A Exit +// | | +// B D +// | \ | +// v \ B +// / D \ +// C \ A +// | v +// unreachable Exit +// +// WARNING: PDT-updated is inconsistent with PDT-recalculated, which is +// constructed from CFG' when recalculating the PDT from scratch. +// +// PDT-recalculated +// +// Exit +// / | \ +// C B D +// | +// A +// +// TODO: document the wanted behavior after resolving this inconsistency. +TEST(DominatorTree, DeletingEdgesIntroducesUnreachables) { + StringRef ModuleString = + "define void @f() {\n" + "A:\n" + " br label %B\n" + "B:\n" + " br i1 undef, label %D, label %C\n" + "C:\n" + " br label %B\n" + "D:\n" + " ret void\n" + "}\n"; + + // Parse the module. + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleString); + + runWithDomTree( + *M, "f", [&](Function &F, DominatorTree *DT, PostDomTree *PDT) { + Function::iterator FI = F.begin(); + + FI++; + BasicBlock *B = &*FI++; + BasicBlock *C = &*FI++; + BasicBlock *D = &*FI++; + + assert(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); + + C->getTerminator()->eraseFromParent(); + new UnreachableInst(C->getContext(), C); + + DT->deleteEdge(C, B); + PDT->deleteEdge(C, B); + + EXPECT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); + EXPECT_EQ(PDT->getNode(C), nullptr); + + PDT->recalculate(F); + + EXPECT_FALSE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); + EXPECT_NE(PDT->getNode(C), nullptr); + }); +} + +// Verify that the PDT is correctly updated in case an edge removal results +// in an infinite loop. +// +// Test case: +// +// CFG PDT +// +// A Exit +// | | +// _B D +// / | \ | +// ^ v \ B +// \ / D / \ +// C \ C A +// / \ v +// ^ v Exit +// \_/ +// +// After deleting the edge C->B, C is part of an infinite reverse-unreachable +// loop: +// +// CFG' PDT' +// +// A Exit +// | | +// B D +// | \ | +// v \ B +// / D \ +// C \ A +// / \ v +// ^ v Exit +// \_/ +// +// In PDT, D post-dominates B. We verify that this post-dominance +// relation is preserved _after_ deleting the edge C->B from CFG. +// +// As C now becomes reverse-unreachable, it is not anymore part of the +// PDT. We also verify this property. +// +// TODO: Can we change the PDT definition such that C remains part of the +// CFG, at best without loosing the dominance relation D postdom B. +TEST(DominatorTree, DeletingEdgesIntroducesInfiniteLoop) { + StringRef ModuleString = + "define void @f() {\n" + "A:\n" + " br label %B\n" + "B:\n" + " br i1 undef, label %D, label %C\n" + "C:\n" + " switch i32 undef, label %C [\n" + " i32 0, label %B\n" + " ]\n" + "D:\n" + " ret void\n" + "}\n"; + + // Parse the module. + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleString); + + runWithDomTree( + *M, "f", [&](Function &F, DominatorTree *DT, PostDomTree *PDT) { + Function::iterator FI = F.begin(); + + FI++; + BasicBlock *B = &*FI++; + BasicBlock *C = &*FI++; + BasicBlock *D = &*FI++; + + assert(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); + + auto SwitchC = cast(C->getTerminator()); + SwitchC->removeCase(SwitchC->case_begin()); + DT->deleteEdge(C, B); + PDT->deleteEdge(C, B); + + EXPECT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); + EXPECT_EQ(PDT->getNode(C), nullptr); + + PDT->recalculate(F); + + EXPECT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); + EXPECT_EQ(PDT->getNode(C), nullptr); + }); +} + +// Verify that the PDT is correctly updated in case an edge removal results +// in an infinite loop. +// +// Test case: +// +// CFG PDT +// +// A Exit +// | / | \ +// B-- C B D +// | \ | +// v \ A +// / D +// C--C2 \ +// / \ \ v +// ^ v --Exit +// \_/ +// +// After deleting the edge C->E, C is part of an infinite reverse-unreachable +// loop: +// +// CFG' PDT' +// +// A Exit +// | | +// B D +// | \ | +// v \ B +// / D \ +// C \ A +// / \ v +// ^ v Exit +// \_/ +// +// In PDT, D does not post-dominate B. After the edge C->E is removed, a new +// post-dominance relation is introduced. +// +// As C now becomes reverse-unreachable, it is not anymore part of the +// PDT. We also verify this property. +// +// TODO: Can we change the PDT definition such that C remains part of the +// CFG, at best without loosing the dominance relation D postdom B. +TEST(DominatorTree, DeletingEdgesIntroducesInfiniteLoop2) { + StringRef ModuleString = + "define void @f() {\n" + "A:\n" + " br label %B\n" + "B:\n" + " br i1 undef, label %D, label %C\n" + "C:\n" + " switch i32 undef, label %C [\n" + " i32 0, label %C2\n" + " ]\n" + "C2:\n" + " ret void\n" + "D:\n" + " ret void\n" + "}\n"; + + // Parse the module. + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleString); + + runWithDomTree( + *M, "f", [&](Function &F, DominatorTree *DT, PostDomTree *PDT) { + Function::iterator FI = F.begin(); + + FI++; + BasicBlock *B = &*FI++; + BasicBlock *C = &*FI++; + BasicBlock *C2 = &*FI++; + BasicBlock *D = &*FI++; + + auto SwitchC = cast(C->getTerminator()); + SwitchC->removeCase(SwitchC->case_begin()); + DT->deleteEdge(C, C2); + PDT->deleteEdge(C, C2); + C2->eraseFromParent(); + + EXPECT_EQ(DT->getNode(C2), nullptr); + PDT->eraseNode(C2); + + EXPECT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); + EXPECT_EQ(PDT->getNode(C), nullptr); + EXPECT_EQ(PDT->getNode(C2), nullptr); + + PDT->recalculate(F); + + EXPECT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); + EXPECT_EQ(PDT->getNode(C), nullptr); + EXPECT_EQ(PDT->getNode(C2), nullptr); + }); +} + namespace { const auto Insert = CFGBuilder::ActionKind::Insert; const auto Delete = CFGBuilder::ActionKind::Delete;