From 092c5ccf5bdcaa53151645e5628cec77fcf4062b Mon Sep 17 00:00:00 2001 From: Rafael Espindola Date: Fri, 30 Mar 2012 16:46:21 +0000 Subject: [PATCH] Handle unreachable code in the dominates functions. This changes users when needed for correctness, but still doesn't clean up code that now unnecessary checks for reachability. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153755 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/Dominators.h | 31 +++- include/llvm/Analysis/LoopInfo.h | 3 +- lib/VMCore/Dominators.cpp | 18 ++- unittests/CMakeLists.txt | 1 + unittests/VMCore/DominatorTreeTest.cpp | 195 +++++++++++++++++++++++++ unittests/VMCore/Makefile | 2 +- 6 files changed, 239 insertions(+), 11 deletions(-) create mode 100644 unittests/VMCore/DominatorTreeTest.cpp diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h index 0d2222dd0cb..f2ccb6e9626 100644 --- a/include/llvm/Analysis/Dominators.h +++ b/include/llvm/Analysis/Dominators.h @@ -359,8 +359,19 @@ public: bool dominatedBySlowTreeWalk(const DomTreeNodeBase *A, const DomTreeNodeBase *B) const { + // A node trivially dominates itself. + if (B == A) + return true; + + // An unreachable node is dominated by anything. + if (!isReachableFromEntry(B)) + return true; + + // And dominates nothing. + if (!isReachableFromEntry(A)) + return false; + const DomTreeNodeBase *IDom; - if (A == 0 || B == 0) return false; while ((IDom = B->getIDom()) != 0 && IDom != A && IDom != B) B = IDom; // Walk up the tree return IDom != 0; @@ -369,10 +380,14 @@ public: /// isReachableFromEntry - Return true if A is dominated by the entry /// block of the function containing it. - bool isReachableFromEntry(const NodeT* A) { + bool isReachableFromEntry(const NodeT* A) const { assert(!this->isPostDominator() && "This is not implemented for post dominators"); - return dominates(&A->getParent()->front(), A); + return isReachableFromEntry(getNode(const_cast(A))); + } + + inline bool isReachableFromEntry(const DomTreeNodeBase *A) const { + return A; } /// dominates - Returns true iff A dominates B. Note that this is not a @@ -380,10 +395,16 @@ public: /// inline bool dominates(const DomTreeNodeBase *A, const DomTreeNodeBase *B) { + // A node trivially dominates itself. if (B == A) - return true; // A node trivially dominates itself. + return true; - if (A == 0 || B == 0) + // An unreachable node is dominated by anything. + if (!isReachableFromEntry(B)) + return true; + + // And dominates nothing. + if (!isReachableFromEntry(A)) return false; // Compare the result of the tree walk and the dfs numbers, if expensive diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h index 8f44bed9471..4921629a040 100644 --- a/include/llvm/Analysis/LoopInfo.h +++ b/include/llvm/Analysis/LoopInfo.h @@ -762,7 +762,8 @@ public: InvBlockTraits::child_begin(BB), E = InvBlockTraits::child_end(BB); I != E; ++I) { typename InvBlockTraits::NodeType *N = *I; - if (DT.dominates(BB, N)) // If BB dominates its predecessor... + // If BB dominates its predecessor... + if (DT.dominates(BB, N) && DT.isReachableFromEntry(N)) TodoStack.push_back(N); } diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp index af51a05c8b5..6f97774fc64 100644 --- a/lib/VMCore/Dominators.cpp +++ b/lib/VMCore/Dominators.cpp @@ -88,8 +88,13 @@ bool DominatorTree::dominates(const Instruction *Def, const BasicBlock *UseBB = User->getParent(); const BasicBlock *DefBB = Def->getParent(); - assert(isReachableFromEntry(DefBB) && isReachableFromEntry(UseBB) && - "We only handle reachable blocks"); + // Any unreachable use is dominated, even if Def == User. + if (!isReachableFromEntry(UseBB)) + return true; + + // Unreachable definitions don't dominate anything. + if (!isReachableFromEntry(DefBB)) + return false; // An instruction doesn't dominate a use in itself. if (Def == User) @@ -119,8 +124,13 @@ bool DominatorTree::dominates(const Instruction *Def, const BasicBlock *UseBB) const { const BasicBlock *DefBB = Def->getParent(); - assert(isReachableFromEntry(DefBB) && isReachableFromEntry(UseBB) && - "We only handle reachable blocks"); + // Any unreachable use is dominated, even if DefBB == UseBB. + if (!isReachableFromEntry(UseBB)) + return true; + + // Unreachable definitions don't dominate anything. + if (!isReachableFromEntry(DefBB)) + return false; if (DefBB == UseBB) return false; diff --git a/unittests/CMakeLists.txt b/unittests/CMakeLists.txt index 60423f25c25..ce0f5cd8226 100644 --- a/unittests/CMakeLists.txt +++ b/unittests/CMakeLists.txt @@ -139,6 +139,7 @@ set(VMCoreSources VMCore/PassManagerTest.cpp VMCore/ValueMapTest.cpp VMCore/VerifierTest.cpp + VMCore/DominatorTreeTest.cpp ) # MSVC9 and 8 cannot compile ValueMapTest.cpp due to their bug. diff --git a/unittests/VMCore/DominatorTreeTest.cpp b/unittests/VMCore/DominatorTreeTest.cpp new file mode 100644 index 00000000000..f6a90605a71 --- /dev/null +++ b/unittests/VMCore/DominatorTreeTest.cpp @@ -0,0 +1,195 @@ +#include "llvm/Instructions.h" +#include "llvm/LLVMContext.h" +#include "llvm/Module.h" +#include "llvm/PassManager.h" +#include "llvm/Analysis/Dominators.h" +#include "llvm/Assembly/Parser.h" +#include "llvm/Support/SourceMgr.h" +#include "gtest/gtest.h" + +using namespace llvm; + +namespace llvm { + void initializeDPassPass(PassRegistry&); + + namespace { + struct DPass : public FunctionPass { + static char ID; + virtual bool runOnFunction(Function &F) { + DominatorTree *DT = &getAnalysis(); + 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)); + + return false; + } + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired(); + } + DPass() : FunctionPass(ID) { + initializeDPassPass(*PassRegistry::getPassRegistry()); + } + }; + char DPass::ID = 0; + + + Module* makeLLVMModule(DPass *P) { + const char *ModuleStrig = + "declare i32 @g()\n" \ + "define void @f(i32 %x) {\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 personality i32 ()* @g\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"; + LLVMContext &C = getGlobalContext(); + SMDiagnostic Err; + return ParseAssemblyString(ModuleStrig, NULL, Err, C); + } + + TEST(DominatorTree, Unreachable) { + DPass *P = new DPass(); + Module *M = makeLLVMModule(P); + PassManager Passes; + Passes.add(P); + Passes.run(*M); + } + } +} + +INITIALIZE_PASS_BEGIN(DPass, "dpass", "dpass", false, false) +INITIALIZE_PASS_DEPENDENCY(DominatorTree) +INITIALIZE_PASS_END(DPass, "dpass", "dpass", false, false) diff --git a/unittests/VMCore/Makefile b/unittests/VMCore/Makefile index 1b2b69c6d60..df55065e191 100644 --- a/unittests/VMCore/Makefile +++ b/unittests/VMCore/Makefile @@ -9,7 +9,7 @@ LEVEL = ../.. TESTNAME = VMCore -LINK_COMPONENTS := core support target ipa +LINK_COMPONENTS := core support target ipa asmparser include $(LEVEL)/Makefile.config include $(LLVM_SRC_ROOT)/unittests/Makefile.unittest -- 2.34.1