| //===- 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 TerminatorInst *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()); |
| } |
| |
