diff options
Diffstat (limited to 'gnu/llvm/unittests/IR/DominatorTreeTest.cpp')
| -rw-r--r-- | gnu/llvm/unittests/IR/DominatorTreeTest.cpp | 992 |
1 files changed, 0 insertions, 992 deletions
diff --git a/gnu/llvm/unittests/IR/DominatorTreeTest.cpp b/gnu/llvm/unittests/IR/DominatorTreeTest.cpp deleted file mode 100644 index 7539bbc860b..00000000000 --- a/gnu/llvm/unittests/IR/DominatorTreeTest.cpp +++ /dev/null @@ -1,992 +0,0 @@ -//===- llvm/unittests/IR/DominatorTreeTest.cpp - Constants unit tests -----===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#include <random> -#include "llvm/Analysis/PostDominators.h" -#include "llvm/Analysis/IteratedDominanceFrontier.h" -#include "llvm/AsmParser/Parser.h" -#include "llvm/IR/Constants.h" -#include "llvm/IR/Dominators.h" -#include "llvm/IR/Instructions.h" -#include "llvm/IR/LLVMContext.h" -#include "llvm/IR/Module.h" -#include "llvm/Support/SourceMgr.h" -#include "CFGBuilder.h" -#include "gtest/gtest.h" - -using namespace llvm; - - -/// Build the dominator tree for the function and run the Test. -static void runWithDomTree( - Module &M, StringRef FuncName, - function_ref<void(Function &F, DominatorTree *DT, PostDominatorTree *PDT)> - Test) { - auto *F = M.getFunction(FuncName); - ASSERT_NE(F, nullptr) << "Could not find " << FuncName; - // Compute the dominator tree for the function. - DominatorTree DT(*F); - PostDominatorTree PDT(*F); - Test(*F, &DT, &PDT); -} - -static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context, - StringRef ModuleStr) { - SMDiagnostic Err; - std::unique_ptr<Module> M = parseAssemblyString(ModuleStr, Err, Context); - assert(M && "Bad assembly?"); - return M; -} - -TEST(DominatorTree, Unreachable) { - StringRef ModuleString = - "declare i32 @g()\n" - "define void @f(i32 %x) personality i32 ()* @g {\n" - "bb0:\n" - " %y1 = add i32 %x, 1\n" - " %y2 = add i32 %x, 1\n" - " %y3 = invoke i32 @g() to label %bb1 unwind label %bb2\n" - "bb1:\n" - " %y4 = add i32 %x, 1\n" - " br label %bb4\n" - "bb2:\n" - " %y5 = landingpad i32\n" - " cleanup\n" - " br label %bb4\n" - "bb3:\n" - " %y6 = add i32 %x, 1\n" - " %y7 = add i32 %x, 1\n" - " ret void\n" - "bb4:\n" - " %y8 = phi i32 [0, %bb2], [%y4, %bb1]\n" - " %y9 = phi i32 [0, %bb2], [%y4, %bb1]\n" - " ret void\n" - "}\n"; - - // Parse the module. - LLVMContext Context; - std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); - - runWithDomTree( - *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) { - Function::iterator FI = F.begin(); - - BasicBlock *BB0 = &*FI++; - BasicBlock::iterator BBI = BB0->begin(); - Instruction *Y1 = &*BBI++; - Instruction *Y2 = &*BBI++; - Instruction *Y3 = &*BBI++; - - BasicBlock *BB1 = &*FI++; - BBI = BB1->begin(); - Instruction *Y4 = &*BBI++; - - BasicBlock *BB2 = &*FI++; - BBI = BB2->begin(); - Instruction *Y5 = &*BBI++; - - BasicBlock *BB3 = &*FI++; - BBI = BB3->begin(); - Instruction *Y6 = &*BBI++; - Instruction *Y7 = &*BBI++; - - BasicBlock *BB4 = &*FI++; - BBI = BB4->begin(); - Instruction *Y8 = &*BBI++; - Instruction *Y9 = &*BBI++; - - // Reachability - EXPECT_TRUE(DT->isReachableFromEntry(BB0)); - EXPECT_TRUE(DT->isReachableFromEntry(BB1)); - EXPECT_TRUE(DT->isReachableFromEntry(BB2)); - EXPECT_FALSE(DT->isReachableFromEntry(BB3)); - EXPECT_TRUE(DT->isReachableFromEntry(BB4)); - - // BB dominance - EXPECT_TRUE(DT->dominates(BB0, BB0)); - EXPECT_TRUE(DT->dominates(BB0, BB1)); - EXPECT_TRUE(DT->dominates(BB0, BB2)); - EXPECT_TRUE(DT->dominates(BB0, BB3)); - EXPECT_TRUE(DT->dominates(BB0, BB4)); - - EXPECT_FALSE(DT->dominates(BB1, BB0)); - EXPECT_TRUE(DT->dominates(BB1, BB1)); - EXPECT_FALSE(DT->dominates(BB1, BB2)); - EXPECT_TRUE(DT->dominates(BB1, BB3)); - EXPECT_FALSE(DT->dominates(BB1, BB4)); - - EXPECT_FALSE(DT->dominates(BB2, BB0)); - EXPECT_FALSE(DT->dominates(BB2, BB1)); - EXPECT_TRUE(DT->dominates(BB2, BB2)); - EXPECT_TRUE(DT->dominates(BB2, BB3)); - EXPECT_FALSE(DT->dominates(BB2, BB4)); - - EXPECT_FALSE(DT->dominates(BB3, BB0)); - EXPECT_FALSE(DT->dominates(BB3, BB1)); - EXPECT_FALSE(DT->dominates(BB3, BB2)); - EXPECT_TRUE(DT->dominates(BB3, BB3)); - EXPECT_FALSE(DT->dominates(BB3, BB4)); - - // BB proper dominance - EXPECT_FALSE(DT->properlyDominates(BB0, BB0)); - EXPECT_TRUE(DT->properlyDominates(BB0, BB1)); - EXPECT_TRUE(DT->properlyDominates(BB0, BB2)); - EXPECT_TRUE(DT->properlyDominates(BB0, BB3)); - - EXPECT_FALSE(DT->properlyDominates(BB1, BB0)); - EXPECT_FALSE(DT->properlyDominates(BB1, BB1)); - EXPECT_FALSE(DT->properlyDominates(BB1, BB2)); - EXPECT_TRUE(DT->properlyDominates(BB1, BB3)); - - EXPECT_FALSE(DT->properlyDominates(BB2, BB0)); - EXPECT_FALSE(DT->properlyDominates(BB2, BB1)); - EXPECT_FALSE(DT->properlyDominates(BB2, BB2)); - EXPECT_TRUE(DT->properlyDominates(BB2, BB3)); - - EXPECT_FALSE(DT->properlyDominates(BB3, BB0)); - EXPECT_FALSE(DT->properlyDominates(BB3, BB1)); - EXPECT_FALSE(DT->properlyDominates(BB3, BB2)); - EXPECT_FALSE(DT->properlyDominates(BB3, BB3)); - - // Instruction dominance in the same reachable BB - EXPECT_FALSE(DT->dominates(Y1, Y1)); - EXPECT_TRUE(DT->dominates(Y1, Y2)); - EXPECT_FALSE(DT->dominates(Y2, Y1)); - EXPECT_FALSE(DT->dominates(Y2, Y2)); - - // Instruction dominance in the same unreachable BB - EXPECT_TRUE(DT->dominates(Y6, Y6)); - EXPECT_TRUE(DT->dominates(Y6, Y7)); - EXPECT_TRUE(DT->dominates(Y7, Y6)); - EXPECT_TRUE(DT->dominates(Y7, Y7)); - - // Invoke - EXPECT_TRUE(DT->dominates(Y3, Y4)); - EXPECT_FALSE(DT->dominates(Y3, Y5)); - - // Phi - EXPECT_TRUE(DT->dominates(Y2, Y9)); - EXPECT_FALSE(DT->dominates(Y3, Y9)); - EXPECT_FALSE(DT->dominates(Y8, Y9)); - - // Anything dominates unreachable - EXPECT_TRUE(DT->dominates(Y1, Y6)); - EXPECT_TRUE(DT->dominates(Y3, Y6)); - - // Unreachable doesn't dominate reachable - EXPECT_FALSE(DT->dominates(Y6, Y1)); - - // Instruction, BB dominance - EXPECT_FALSE(DT->dominates(Y1, BB0)); - EXPECT_TRUE(DT->dominates(Y1, BB1)); - EXPECT_TRUE(DT->dominates(Y1, BB2)); - EXPECT_TRUE(DT->dominates(Y1, BB3)); - EXPECT_TRUE(DT->dominates(Y1, BB4)); - - EXPECT_FALSE(DT->dominates(Y3, BB0)); - EXPECT_TRUE(DT->dominates(Y3, BB1)); - EXPECT_FALSE(DT->dominates(Y3, BB2)); - EXPECT_TRUE(DT->dominates(Y3, BB3)); - EXPECT_FALSE(DT->dominates(Y3, BB4)); - - EXPECT_TRUE(DT->dominates(Y6, BB3)); - - // Post dominance. - EXPECT_TRUE(PDT->dominates(BB0, BB0)); - EXPECT_FALSE(PDT->dominates(BB1, BB0)); - EXPECT_FALSE(PDT->dominates(BB2, BB0)); - EXPECT_FALSE(PDT->dominates(BB3, BB0)); - EXPECT_TRUE(PDT->dominates(BB4, BB1)); - - // Dominance descendants. - SmallVector<BasicBlock *, 8> DominatedBBs, PostDominatedBBs; - - DT->getDescendants(BB0, DominatedBBs); - PDT->getDescendants(BB0, PostDominatedBBs); - EXPECT_EQ(DominatedBBs.size(), 4UL); - EXPECT_EQ(PostDominatedBBs.size(), 1UL); - - // BB3 is unreachable. It should have no dominators nor postdominators. - DominatedBBs.clear(); - PostDominatedBBs.clear(); - DT->getDescendants(BB3, DominatedBBs); - DT->getDescendants(BB3, PostDominatedBBs); - EXPECT_EQ(DominatedBBs.size(), 0UL); - EXPECT_EQ(PostDominatedBBs.size(), 0UL); - - // Check DFS Numbers before - DT->updateDFSNumbers(); - EXPECT_EQ(DT->getNode(BB0)->getDFSNumIn(), 0UL); - EXPECT_EQ(DT->getNode(BB0)->getDFSNumOut(), 7UL); - EXPECT_EQ(DT->getNode(BB1)->getDFSNumIn(), 1UL); - EXPECT_EQ(DT->getNode(BB1)->getDFSNumOut(), 2UL); - EXPECT_EQ(DT->getNode(BB2)->getDFSNumIn(), 5UL); - EXPECT_EQ(DT->getNode(BB2)->getDFSNumOut(), 6UL); - EXPECT_EQ(DT->getNode(BB4)->getDFSNumIn(), 3UL); - EXPECT_EQ(DT->getNode(BB4)->getDFSNumOut(), 4UL); - - // Check levels before - EXPECT_EQ(DT->getNode(BB0)->getLevel(), 0U); - EXPECT_EQ(DT->getNode(BB1)->getLevel(), 1U); - EXPECT_EQ(DT->getNode(BB2)->getLevel(), 1U); - EXPECT_EQ(DT->getNode(BB4)->getLevel(), 1U); - - // Reattach block 3 to block 1 and recalculate - BB1->getTerminator()->eraseFromParent(); - BranchInst::Create(BB4, BB3, ConstantInt::getTrue(F.getContext()), BB1); - DT->recalculate(F); - - // Check DFS Numbers after - DT->updateDFSNumbers(); - EXPECT_EQ(DT->getNode(BB0)->getDFSNumIn(), 0UL); - EXPECT_EQ(DT->getNode(BB0)->getDFSNumOut(), 9UL); - EXPECT_EQ(DT->getNode(BB1)->getDFSNumIn(), 1UL); - EXPECT_EQ(DT->getNode(BB1)->getDFSNumOut(), 4UL); - EXPECT_EQ(DT->getNode(BB2)->getDFSNumIn(), 7UL); - EXPECT_EQ(DT->getNode(BB2)->getDFSNumOut(), 8UL); - EXPECT_EQ(DT->getNode(BB3)->getDFSNumIn(), 2UL); - EXPECT_EQ(DT->getNode(BB3)->getDFSNumOut(), 3UL); - EXPECT_EQ(DT->getNode(BB4)->getDFSNumIn(), 5UL); - EXPECT_EQ(DT->getNode(BB4)->getDFSNumOut(), 6UL); - - // Check levels after - EXPECT_EQ(DT->getNode(BB0)->getLevel(), 0U); - EXPECT_EQ(DT->getNode(BB1)->getLevel(), 1U); - EXPECT_EQ(DT->getNode(BB2)->getLevel(), 1U); - EXPECT_EQ(DT->getNode(BB3)->getLevel(), 2U); - EXPECT_EQ(DT->getNode(BB4)->getLevel(), 1U); - - // Change root node - EXPECT_TRUE(DT->verify()); - BasicBlock *NewEntry = - BasicBlock::Create(F.getContext(), "new_entry", &F, BB0); - BranchInst::Create(BB0, NewEntry); - EXPECT_EQ(F.begin()->getName(), NewEntry->getName()); - EXPECT_TRUE(&F.getEntryBlock() == NewEntry); - DT->setNewRoot(NewEntry); - EXPECT_TRUE(DT->verify()); - }); -} - -TEST(DominatorTree, NonUniqueEdges) { - StringRef ModuleString = - "define i32 @f(i32 %i, i32 *%p) {\n" - "bb0:\n" - " store i32 %i, i32 *%p\n" - " switch i32 %i, label %bb2 [\n" - " i32 0, label %bb1\n" - " i32 1, label %bb1\n" - " ]\n" - " bb1:\n" - " ret i32 1\n" - " bb2:\n" - " ret i32 4\n" - "}\n"; - - // Parse the module. - LLVMContext Context; - std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); - - runWithDomTree( - *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) { - Function::iterator FI = F.begin(); - - BasicBlock *BB0 = &*FI++; - BasicBlock *BB1 = &*FI++; - BasicBlock *BB2 = &*FI++; - - const Instruction *TI = BB0->getTerminator(); - assert(TI->getNumSuccessors() == 3 && "Switch has three successors"); - - BasicBlockEdge Edge_BB0_BB2(BB0, TI->getSuccessor(0)); - assert(Edge_BB0_BB2.getEnd() == BB2 && - "Default label is the 1st successor"); - - BasicBlockEdge Edge_BB0_BB1_a(BB0, TI->getSuccessor(1)); - assert(Edge_BB0_BB1_a.getEnd() == BB1 && "BB1 is the 2nd successor"); - - BasicBlockEdge Edge_BB0_BB1_b(BB0, TI->getSuccessor(2)); - assert(Edge_BB0_BB1_b.getEnd() == BB1 && "BB1 is the 3rd successor"); - - EXPECT_TRUE(DT->dominates(Edge_BB0_BB2, BB2)); - EXPECT_FALSE(DT->dominates(Edge_BB0_BB2, BB1)); - - EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_a, BB1)); - EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_b, BB1)); - - EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_a, BB2)); - EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_b, BB2)); - }); -} - -// Verify that the PDT is correctly updated in case an edge removal results -// in a new unreachable CFG node. Also make sure that the updated PDT is the -// same as a freshly recalculated one. -// -// 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 C B D -// | \ | -// v \ A -// / D -// C \ -// | \ -// unreachable Exit -// -// Both the blocks that end with ret and with unreachable become trivial -// PostDominatorTree roots, as they have no successors. -// -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<Module> M = makeLLVMModule(Context, ModuleString); - - runWithDomTree( - *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) { - Function::iterator FI = F.begin(); - - FI++; - BasicBlock *B = &*FI++; - BasicBlock *C = &*FI++; - BasicBlock *D = &*FI++; - - ASSERT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); - EXPECT_TRUE(DT->verify()); - EXPECT_TRUE(PDT->verify()); - - C->getTerminator()->eraseFromParent(); - new UnreachableInst(C->getContext(), C); - - DT->deleteEdge(C, B); - PDT->deleteEdge(C, B); - - EXPECT_TRUE(DT->verify()); - EXPECT_TRUE(PDT->verify()); - - EXPECT_FALSE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); - EXPECT_NE(PDT->getNode(C), nullptr); - - DominatorTree NDT(F); - EXPECT_EQ(DT->compare(NDT), 0); - - PostDominatorTree NPDT(F); - EXPECT_EQ(PDT->compare(NPDT), 0); - }); -} - -// Verify that the PDT is correctly updated in case an edge removal results -// in an infinite loop. Also make sure that the updated PDT is the -// same as a freshly recalculated one. -// -// 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 C B D -// | \ | -// v \ A -// / D -// C \ -// / \ v -// ^ v Exit -// \_/ -// -// As C now becomes reverse-unreachable, it forms a new non-trivial root and -// gets connected to the virtual exit. -// D does not postdominate B anymore, because there are two forward paths from -// B to the virtual exit: -// - B -> C -> VirtualExit -// - B -> D -> VirtualExit. -// -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<Module> M = makeLLVMModule(Context, ModuleString); - - runWithDomTree( - *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) { - Function::iterator FI = F.begin(); - - FI++; - BasicBlock *B = &*FI++; - BasicBlock *C = &*FI++; - BasicBlock *D = &*FI++; - - ASSERT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); - EXPECT_TRUE(DT->verify()); - EXPECT_TRUE(PDT->verify()); - - auto SwitchC = cast<SwitchInst>(C->getTerminator()); - SwitchC->removeCase(SwitchC->case_begin()); - DT->deleteEdge(C, B); - EXPECT_TRUE(DT->verify()); - PDT->deleteEdge(C, B); - EXPECT_TRUE(PDT->verify()); - - EXPECT_FALSE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); - EXPECT_NE(PDT->getNode(C), nullptr); - - DominatorTree NDT(F); - EXPECT_EQ(DT->compare(NDT), 0); - - PostDominatorTree NPDT(F); - EXPECT_EQ(PDT->compare(NPDT), 0); - }); -} - -// Verify that the PDT is correctly updated in case an edge removal results -// in an infinite loop. -// -// Test case: -// -// CFG PDT -// -// A Exit -// | / | \ -// B-- C2 B D -// | \ / | -// v \ C 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 C B D -// | \ | -// v \ A -// / D -// C \ -// / \ v -// ^ v Exit -// \_/ -// -// In PDT, D does not post-dominate B. After the edge C -> C2 is removed, -// C becomes a new nontrivial PDT root. -// -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<Module> M = makeLLVMModule(Context, ModuleString); - - runWithDomTree( - *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) { - Function::iterator FI = F.begin(); - - FI++; - BasicBlock *B = &*FI++; - BasicBlock *C = &*FI++; - BasicBlock *C2 = &*FI++; - BasicBlock *D = &*FI++; - - EXPECT_TRUE(DT->verify()); - EXPECT_TRUE(PDT->verify()); - - auto SwitchC = cast<SwitchInst>(C->getTerminator()); - SwitchC->removeCase(SwitchC->case_begin()); - DT->deleteEdge(C, C2); - PDT->deleteEdge(C, C2); - C2->removeFromParent(); - - EXPECT_EQ(DT->getNode(C2), nullptr); - PDT->eraseNode(C2); - delete C2; - - EXPECT_TRUE(DT->verify()); - EXPECT_TRUE(PDT->verify()); - - EXPECT_FALSE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); - EXPECT_NE(PDT->getNode(C), nullptr); - - DominatorTree NDT(F); - EXPECT_EQ(DT->compare(NDT), 0); - - PostDominatorTree NPDT(F); - EXPECT_EQ(PDT->compare(NPDT), 0); - }); -} - -// Verify that the IDF returns blocks in a deterministic way. -// -// Test case: -// -// CFG -// -// (A) -// / \ -// / \ -// (B) (C) -// |\ /| -// | X | -// |/ \| -// (D) (E) -// -// IDF for block B is {D, E}, and the order of blocks in this list is defined by -// their 1) level in dom-tree and 2) DFSIn number if the level is the same. -// -TEST(DominatorTree, IDFDeterminismTest) { - StringRef ModuleString = - "define void @f() {\n" - "A:\n" - " br i1 undef, label %B, label %C\n" - "B:\n" - " br i1 undef, label %D, label %E\n" - "C:\n" - " br i1 undef, label %D, label %E\n" - "D:\n" - " ret void\n" - "E:\n" - " ret void\n" - "}\n"; - - // Parse the module. - LLVMContext Context; - std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); - - runWithDomTree( - *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) { - Function::iterator FI = F.begin(); - - BasicBlock *A = &*FI++; - BasicBlock *B = &*FI++; - BasicBlock *C = &*FI++; - BasicBlock *D = &*FI++; - BasicBlock *E = &*FI++; - (void)C; - - DT->updateDFSNumbers(); - ForwardIDFCalculator IDF(*DT); - SmallPtrSet<BasicBlock *, 1> DefBlocks; - DefBlocks.insert(B); - IDF.setDefiningBlocks(DefBlocks); - - SmallVector<BasicBlock *, 32> IDFBlocks; - SmallPtrSet<BasicBlock *, 32> LiveInBlocks; - IDF.resetLiveInBlocks(); - IDF.calculate(IDFBlocks); - - - EXPECT_EQ(IDFBlocks.size(), 2UL); - EXPECT_EQ(DT->getNode(A)->getDFSNumIn(), 0UL); - EXPECT_EQ(IDFBlocks[0], D); - EXPECT_EQ(IDFBlocks[1], E); - EXPECT_TRUE(DT->getNode(IDFBlocks[0])->getDFSNumIn() < - DT->getNode(IDFBlocks[1])->getDFSNumIn()); - }); -} - -namespace { -const auto Insert = CFGBuilder::ActionKind::Insert; -const auto Delete = CFGBuilder::ActionKind::Delete; - -bool CompUpdates(const CFGBuilder::Update &A, const CFGBuilder::Update &B) { - return std::tie(A.Action, A.Edge.From, A.Edge.To) < - std::tie(B.Action, B.Edge.From, B.Edge.To); -} -} // namespace - -TEST(DominatorTree, InsertReachable) { - CFGHolder Holder; - std::vector<CFGBuilder::Arc> Arcs = { - {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"}, - {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}}; - - std::vector<CFGBuilder::Update> Updates = {{Insert, {"12", "10"}}, - {Insert, {"10", "9"}}, - {Insert, {"7", "6"}}, - {Insert, {"7", "5"}}}; - CFGBuilder B(Holder.F, Arcs, Updates); - DominatorTree DT(*Holder.F); - EXPECT_TRUE(DT.verify()); - PostDominatorTree PDT(*Holder.F); - EXPECT_TRUE(PDT.verify()); - - Optional<CFGBuilder::Update> LastUpdate; - while ((LastUpdate = B.applyUpdate())) { - EXPECT_EQ(LastUpdate->Action, Insert); - BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); - BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); - DT.insertEdge(From, To); - EXPECT_TRUE(DT.verify()); - PDT.insertEdge(From, To); - EXPECT_TRUE(PDT.verify()); - } -} - -TEST(DominatorTree, InsertReachable2) { - CFGHolder Holder; - std::vector<CFGBuilder::Arc> Arcs = { - {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"}, - {"7", "5"}, {"2", "8"}, {"8", "11"}, {"11", "12"}, {"12", "10"}, - {"10", "9"}, {"9", "10"}}; - - std::vector<CFGBuilder::Update> Updates = {{Insert, {"10", "7"}}}; - CFGBuilder B(Holder.F, Arcs, Updates); - DominatorTree DT(*Holder.F); - EXPECT_TRUE(DT.verify()); - PostDominatorTree PDT(*Holder.F); - EXPECT_TRUE(PDT.verify()); - - Optional<CFGBuilder::Update> LastUpdate = B.applyUpdate(); - EXPECT_TRUE(LastUpdate); - - EXPECT_EQ(LastUpdate->Action, Insert); - BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); - BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); - DT.insertEdge(From, To); - EXPECT_TRUE(DT.verify()); - PDT.insertEdge(From, To); - EXPECT_TRUE(PDT.verify()); -} - -TEST(DominatorTree, InsertUnreachable) { - CFGHolder Holder; - std::vector<CFGBuilder::Arc> Arcs = {{"1", "2"}, {"2", "3"}, {"3", "4"}, - {"5", "6"}, {"5", "7"}, {"3", "8"}, - {"9", "10"}, {"11", "12"}}; - - std::vector<CFGBuilder::Update> Updates = {{Insert, {"4", "5"}}, - {Insert, {"8", "9"}}, - {Insert, {"10", "12"}}, - {Insert, {"10", "11"}}}; - CFGBuilder B(Holder.F, Arcs, Updates); - DominatorTree DT(*Holder.F); - EXPECT_TRUE(DT.verify()); - PostDominatorTree PDT(*Holder.F); - EXPECT_TRUE(PDT.verify()); - - Optional<CFGBuilder::Update> LastUpdate; - while ((LastUpdate = B.applyUpdate())) { - EXPECT_EQ(LastUpdate->Action, Insert); - BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); - BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); - DT.insertEdge(From, To); - EXPECT_TRUE(DT.verify()); - PDT.insertEdge(From, To); - EXPECT_TRUE(PDT.verify()); - } -} - -TEST(DominatorTree, InsertFromUnreachable) { - CFGHolder Holder; - std::vector<CFGBuilder::Arc> Arcs = {{"1", "2"}, {"2", "3"}, {"3", "4"}}; - - std::vector<CFGBuilder::Update> Updates = {{Insert, {"3", "5"}}}; - CFGBuilder B(Holder.F, Arcs, Updates); - PostDominatorTree PDT(*Holder.F); - EXPECT_TRUE(PDT.verify()); - - Optional<CFGBuilder::Update> LastUpdate = B.applyUpdate(); - EXPECT_TRUE(LastUpdate); - - EXPECT_EQ(LastUpdate->Action, Insert); - BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); - BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); - PDT.insertEdge(From, To); - EXPECT_TRUE(PDT.verify()); - EXPECT_TRUE(PDT.getRoots().size() == 2); - // Make sure we can use a const pointer with getNode. - const BasicBlock *BB5 = B.getOrAddBlock("5"); - EXPECT_NE(PDT.getNode(BB5), nullptr); -} - -TEST(DominatorTree, InsertMixed) { - CFGHolder Holder; - std::vector<CFGBuilder::Arc> Arcs = { - {"1", "2"}, {"2", "3"}, {"3", "4"}, {"5", "6"}, {"5", "7"}, - {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}, {"7", "3"}}; - - std::vector<CFGBuilder::Update> Updates = { - {Insert, {"4", "5"}}, {Insert, {"2", "5"}}, {Insert, {"10", "9"}}, - {Insert, {"12", "10"}}, {Insert, {"12", "10"}}, {Insert, {"7", "8"}}, - {Insert, {"7", "5"}}}; - CFGBuilder B(Holder.F, Arcs, Updates); - DominatorTree DT(*Holder.F); - EXPECT_TRUE(DT.verify()); - PostDominatorTree PDT(*Holder.F); - EXPECT_TRUE(PDT.verify()); - - Optional<CFGBuilder::Update> LastUpdate; - while ((LastUpdate = B.applyUpdate())) { - EXPECT_EQ(LastUpdate->Action, Insert); - BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); - BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); - DT.insertEdge(From, To); - EXPECT_TRUE(DT.verify()); - PDT.insertEdge(From, To); - EXPECT_TRUE(PDT.verify()); - } -} - -TEST(DominatorTree, InsertPermut) { - std::vector<CFGBuilder::Arc> Arcs = { - {"1", "2"}, {"2", "3"}, {"3", "4"}, {"5", "6"}, {"5", "7"}, - {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}, {"7", "3"}}; - - std::vector<CFGBuilder::Update> Updates = {{Insert, {"4", "5"}}, - {Insert, {"2", "5"}}, - {Insert, {"10", "9"}}, - {Insert, {"12", "10"}}}; - - while (std::next_permutation(Updates.begin(), Updates.end(), CompUpdates)) { - CFGHolder Holder; - CFGBuilder B(Holder.F, Arcs, Updates); - DominatorTree DT(*Holder.F); - EXPECT_TRUE(DT.verify()); - PostDominatorTree PDT(*Holder.F); - EXPECT_TRUE(PDT.verify()); - - Optional<CFGBuilder::Update> LastUpdate; - while ((LastUpdate = B.applyUpdate())) { - EXPECT_EQ(LastUpdate->Action, Insert); - BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); - BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); - DT.insertEdge(From, To); - EXPECT_TRUE(DT.verify()); - PDT.insertEdge(From, To); - EXPECT_TRUE(PDT.verify()); - } - } -} - -TEST(DominatorTree, DeleteReachable) { - CFGHolder Holder; - std::vector<CFGBuilder::Arc> Arcs = { - {"1", "2"}, {"2", "3"}, {"2", "4"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, - {"5", "7"}, {"7", "8"}, {"3", "8"}, {"8", "9"}, {"9", "10"}, {"10", "2"}}; - - std::vector<CFGBuilder::Update> Updates = { - {Delete, {"2", "4"}}, {Delete, {"7", "8"}}, {Delete, {"10", "2"}}}; - CFGBuilder B(Holder.F, Arcs, Updates); - DominatorTree DT(*Holder.F); - EXPECT_TRUE(DT.verify()); - PostDominatorTree PDT(*Holder.F); - EXPECT_TRUE(PDT.verify()); - - Optional<CFGBuilder::Update> LastUpdate; - while ((LastUpdate = B.applyUpdate())) { - EXPECT_EQ(LastUpdate->Action, Delete); - BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); - BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); - DT.deleteEdge(From, To); - EXPECT_TRUE(DT.verify()); - PDT.deleteEdge(From, To); - EXPECT_TRUE(PDT.verify()); - } -} - -TEST(DominatorTree, DeleteUnreachable) { - CFGHolder Holder; - std::vector<CFGBuilder::Arc> Arcs = { - {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"}, - {"7", "8"}, {"3", "8"}, {"8", "9"}, {"9", "10"}, {"10", "2"}}; - - std::vector<CFGBuilder::Update> Updates = { - {Delete, {"8", "9"}}, {Delete, {"7", "8"}}, {Delete, {"3", "4"}}}; - CFGBuilder B(Holder.F, Arcs, Updates); - DominatorTree DT(*Holder.F); - EXPECT_TRUE(DT.verify()); - PostDominatorTree PDT(*Holder.F); - EXPECT_TRUE(PDT.verify()); - - Optional<CFGBuilder::Update> LastUpdate; - while ((LastUpdate = B.applyUpdate())) { - EXPECT_EQ(LastUpdate->Action, Delete); - BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); - BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); - DT.deleteEdge(From, To); - EXPECT_TRUE(DT.verify()); - PDT.deleteEdge(From, To); - EXPECT_TRUE(PDT.verify()); - } -} - -TEST(DominatorTree, InsertDelete) { - std::vector<CFGBuilder::Arc> Arcs = { - {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"}, - {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}}; - - std::vector<CFGBuilder::Update> Updates = { - {Insert, {"2", "4"}}, {Insert, {"12", "10"}}, {Insert, {"10", "9"}}, - {Insert, {"7", "6"}}, {Insert, {"7", "5"}}, {Delete, {"3", "8"}}, - {Insert, {"10", "7"}}, {Insert, {"2", "8"}}, {Delete, {"3", "4"}}, - {Delete, {"8", "9"}}, {Delete, {"11", "12"}}}; - - CFGHolder Holder; - CFGBuilder B(Holder.F, Arcs, Updates); - DominatorTree DT(*Holder.F); - EXPECT_TRUE(DT.verify()); - PostDominatorTree PDT(*Holder.F); - EXPECT_TRUE(PDT.verify()); - - Optional<CFGBuilder::Update> LastUpdate; - while ((LastUpdate = B.applyUpdate())) { - BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); - BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); - if (LastUpdate->Action == Insert) { - DT.insertEdge(From, To); - PDT.insertEdge(From, To); - } else { - DT.deleteEdge(From, To); - PDT.deleteEdge(From, To); - } - - EXPECT_TRUE(DT.verify()); - EXPECT_TRUE(PDT.verify()); - } -} - -TEST(DominatorTree, InsertDeleteExhaustive) { - std::vector<CFGBuilder::Arc> Arcs = { - {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"}, - {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}}; - - std::vector<CFGBuilder::Update> Updates = { - {Insert, {"2", "4"}}, {Insert, {"12", "10"}}, {Insert, {"10", "9"}}, - {Insert, {"7", "6"}}, {Insert, {"7", "5"}}, {Delete, {"3", "8"}}, - {Insert, {"10", "7"}}, {Insert, {"2", "8"}}, {Delete, {"3", "4"}}, - {Delete, {"8", "9"}}, {Delete, {"11", "12"}}}; - - std::mt19937 Generator(0); - for (unsigned i = 0; i < 16; ++i) { - std::shuffle(Updates.begin(), Updates.end(), Generator); - CFGHolder Holder; - CFGBuilder B(Holder.F, Arcs, Updates); - DominatorTree DT(*Holder.F); - EXPECT_TRUE(DT.verify()); - PostDominatorTree PDT(*Holder.F); - EXPECT_TRUE(PDT.verify()); - - Optional<CFGBuilder::Update> LastUpdate; - while ((LastUpdate = B.applyUpdate())) { - BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); - BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); - if (LastUpdate->Action == Insert) { - DT.insertEdge(From, To); - PDT.insertEdge(From, To); - } else { - DT.deleteEdge(From, To); - PDT.deleteEdge(From, To); - } - - EXPECT_TRUE(DT.verify()); - EXPECT_TRUE(PDT.verify()); - } - } -} - -TEST(DominatorTree, InsertIntoIrreducible) { - std::vector<CFGBuilder::Arc> Arcs = { - {"0", "1"}, - {"1", "27"}, {"1", "7"}, - {"10", "18"}, - {"13", "10"}, - {"18", "13"}, {"18", "23"}, - {"23", "13"}, {"23", "24"}, - {"24", "1"}, {"24", "18"}, - {"27", "24"}}; - - CFGHolder Holder; - CFGBuilder B(Holder.F, Arcs, {{Insert, {"7", "23"}}}); - DominatorTree DT(*Holder.F); - EXPECT_TRUE(DT.verify()); - - B.applyUpdate(); - BasicBlock *From = B.getOrAddBlock("7"); - BasicBlock *To = B.getOrAddBlock("23"); - DT.insertEdge(From, To); - - EXPECT_TRUE(DT.verify()); -} - |