Index: llvm/trunk/include/llvm/Analysis/CFG.h =================================================================== --- llvm/trunk/include/llvm/Analysis/CFG.h +++ llvm/trunk/include/llvm/Analysis/CFG.h @@ -47,8 +47,8 @@ bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges = false); -/// Determine whether instruction 'To' is reachable from 'From', -/// returning true if uncertain. +/// Determine whether instruction 'To' is reachable from 'From', without passing +/// through any blocks in ExclusionSet, returning true if uncertain. /// /// Determine whether there is a path from From to To within a single function. /// Returns false only if we can prove that once 'From' has been executed then @@ -62,9 +62,10 @@ /// we find a block that dominates the block containing 'To'. DT is most useful /// on branchy code but not loops, and LI is most useful on code with loops but /// does not help on branchy code outside loops. -bool isPotentiallyReachable(const Instruction *From, const Instruction *To, - const DominatorTree *DT = nullptr, - const LoopInfo *LI = nullptr); +bool isPotentiallyReachable( + const Instruction *From, const Instruction *To, + const SmallPtrSetImpl *ExclusionSet = nullptr, + const DominatorTree *DT = nullptr, const LoopInfo *LI = nullptr); /// Determine whether block 'To' is reachable from 'From', returning /// true if uncertain. @@ -88,6 +89,20 @@ const DominatorTree *DT = nullptr, const LoopInfo *LI = nullptr); +/// Determine whether there is at least one path from a block in +/// 'Worklist' to 'StopBB' without passing through any blocks in +/// 'ExclusionSet', returning true if uncertain. +/// +/// Determine whether there is a path from at least one block in Worklist to +/// StopBB within a single function without passing through any of the blocks +/// in 'ExclusionSet'. Returns false only if we can prove that once any block +/// in 'Worklist' has been reached then 'StopBB' can not be executed. +/// Conservatively returns true. +bool isPotentiallyReachableFromMany( + SmallVectorImpl &Worklist, BasicBlock *StopBB, + const SmallPtrSetImpl *ExclusionSet, + const DominatorTree *DT = nullptr, const LoopInfo *LI = nullptr); + /// Return true if the control flow in \p RPOTraversal is irreducible. /// /// This is a generic implementation to detect CFG irreducibility based on loop Index: llvm/trunk/lib/Analysis/BasicAliasAnalysis.cpp =================================================================== --- llvm/trunk/lib/Analysis/BasicAliasAnalysis.cpp +++ llvm/trunk/lib/Analysis/BasicAliasAnalysis.cpp @@ -1906,7 +1906,7 @@ // the Values cannot come from different iterations of a potential cycle the // phi nodes could be involved in. for (auto *P : VisitedPhiBBs) - if (isPotentiallyReachable(&P->front(), Inst, DT, LI)) + if (isPotentiallyReachable(&P->front(), Inst, nullptr, DT, LI)) return false; return true; Index: llvm/trunk/lib/Analysis/CFG.cpp =================================================================== --- llvm/trunk/lib/Analysis/CFG.cpp +++ llvm/trunk/lib/Analysis/CFG.cpp @@ -12,6 +12,7 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/CFG.h" +#include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallSet.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/IR/Dominators.h" @@ -119,22 +120,33 @@ return L; } -// True if there is a loop which contains both BB1 and BB2. -static bool loopContainsBoth(const LoopInfo *LI, - const BasicBlock *BB1, const BasicBlock *BB2) { - const Loop *L1 = getOutermostLoop(LI, BB1); - const Loop *L2 = getOutermostLoop(LI, BB2); - return L1 != nullptr && L1 == L2; -} - bool llvm::isPotentiallyReachableFromMany( SmallVectorImpl &Worklist, BasicBlock *StopBB, - const DominatorTree *DT, const LoopInfo *LI) { + const SmallPtrSetImpl *ExclusionSet, const DominatorTree *DT, + const LoopInfo *LI) { // When the stop block is unreachable, it's dominated from everywhere, // regardless of whether there's a path between the two blocks. if (DT && !DT->isReachableFromEntry(StopBB)) DT = nullptr; + // We can't skip directly from a block that dominates the stop block if the + // exclusion block is potentially in between. + if (ExclusionSet && !ExclusionSet->empty()) + DT = nullptr; + + // Normally any block in a loop is reachable from any other block in a loop, + // however excluded blocks might partition the body of a loop to make that + // untrue. + SmallPtrSet LoopsWithHoles; + if (LI && ExclusionSet) { + for (auto BB : *ExclusionSet) { + if (const Loop *L = getOutermostLoop(LI, BB)) + LoopsWithHoles.insert(L); + } + } + + const Loop *StopLoop = LI ? getOutermostLoop(LI, StopBB) : nullptr; + // Limit the number of blocks we visit. The goal is to avoid run-away compile // times on large CFGs without hampering sensible code. Arbitrarily chosen. unsigned Limit = 32; @@ -145,10 +157,23 @@ continue; if (BB == StopBB) return true; + if (ExclusionSet && ExclusionSet->count(BB)) + continue; if (DT && DT->dominates(BB, StopBB)) return true; - if (LI && loopContainsBoth(LI, BB, StopBB)) - return true; + + const Loop *Outer = nullptr; + if (LI) { + Outer = getOutermostLoop(LI, BB); + // If we're in a loop with a hole, not all blocks in the loop are + // reachable from all other blocks. That implies we can't simply jump to + // the loop's exit blocks, as that exit might need to pass through an + // excluded block. Clear Outer so we process BB's successors. + if (LoopsWithHoles.count(Outer)) + Outer = nullptr; + if (StopLoop && Outer == StopLoop) + return true; + } if (!--Limit) { // We haven't been able to prove it one way or the other. Conservatively @@ -156,7 +181,7 @@ return true; } - if (const Loop *Outer = LI ? getOutermostLoop(LI, BB) : nullptr) { + if (Outer) { // All blocks in a single loop are reachable from all other blocks. From // any of these blocks, we can skip directly to the exits of the loop, // ignoring any other blocks inside the loop body. @@ -180,11 +205,13 @@ Worklist.push_back(const_cast(A)); return isPotentiallyReachableFromMany(Worklist, const_cast(B), - DT, LI); + nullptr, DT, LI); } -bool llvm::isPotentiallyReachable(const Instruction *A, const Instruction *B, - const DominatorTree *DT, const LoopInfo *LI) { +bool llvm::isPotentiallyReachable( + const Instruction *A, const Instruction *B, + const SmallPtrSetImpl *ExclusionSet, const DominatorTree *DT, + const LoopInfo *LI) { assert(A->getParent()->getParent() == B->getParent()->getParent() && "This analysis is function-local!"); @@ -230,14 +257,16 @@ if (DT->isReachableFromEntry(A->getParent()) != DT->isReachableFromEntry(B->getParent())) return false; - if (A->getParent() == &A->getParent()->getParent()->getEntryBlock() && - DT->isReachableFromEntry(B->getParent())) - return true; - if (B->getParent() == &A->getParent()->getParent()->getEntryBlock() && - DT->isReachableFromEntry(A->getParent())) - return false; + if (!ExclusionSet || ExclusionSet->empty()) { + if (A->getParent() == &A->getParent()->getParent()->getEntryBlock() && + DT->isReachableFromEntry(B->getParent())) + return true; + if (B->getParent() == &A->getParent()->getParent()->getEntryBlock() && + DT->isReachableFromEntry(A->getParent())) + return false; + } } return isPotentiallyReachableFromMany( - Worklist, const_cast(B->getParent()), DT, LI); + Worklist, const_cast(B->getParent()), ExclusionSet, DT, LI); } Index: llvm/trunk/lib/Analysis/CaptureTracking.cpp =================================================================== --- llvm/trunk/lib/Analysis/CaptureTracking.cpp +++ llvm/trunk/lib/Analysis/CaptureTracking.cpp @@ -101,14 +101,14 @@ SmallVector Worklist; Worklist.append(succ_begin(BB), succ_end(BB)); - return !isPotentiallyReachableFromMany(Worklist, BB, DT); + return !isPotentiallyReachableFromMany(Worklist, BB, nullptr, DT); } // If the value is defined in the same basic block as use and BeforeHere, // there is no need to explore the use if BeforeHere dominates use. // Check whether there is a path from I to BeforeHere. if (BeforeHere != I && DT->dominates(BeforeHere, I) && - !isPotentiallyReachable(I, BeforeHere, DT)) + !isPotentiallyReachable(I, BeforeHere, nullptr, DT)) return true; return false; Index: llvm/trunk/lib/CodeGen/DwarfEHPrepare.cpp =================================================================== --- llvm/trunk/lib/CodeGen/DwarfEHPrepare.cpp +++ llvm/trunk/lib/CodeGen/DwarfEHPrepare.cpp @@ -145,7 +145,7 @@ size_t ResumeIndex = 0; for (auto *RI : Resumes) { for (auto *LP : CleanupLPads) { - if (isPotentiallyReachable(LP, RI, DT)) { + if (isPotentiallyReachable(LP, RI, nullptr, DT)) { ResumeReachable.set(ResumeIndex); break; } Index: llvm/trunk/unittests/Analysis/CFGTest.cpp =================================================================== --- llvm/trunk/unittests/Analysis/CFGTest.cpp +++ llvm/trunk/unittests/Analysis/CFGTest.cpp @@ -7,6 +7,7 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/CFG.h" +#include "llvm/ADT/SmallPtrSet.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/AsmParser/Parser.h" #include "llvm/IR/Dominators.h" @@ -57,24 +58,32 @@ report_fatal_error("@test must have an instruction %A"); if (B == nullptr) report_fatal_error("@test must have an instruction %B"); + + assert(ExclusionSet.empty()); + for (auto I = F->begin(), E = F->end(); I != E; ++I) { + if (I->hasName() && I->getName().startswith("excluded")) + ExclusionSet.insert(&*I); + } } void ExpectPath(bool ExpectedResult) { static char ID; class IsPotentiallyReachableTestPass : public FunctionPass { public: - IsPotentiallyReachableTestPass(bool ExpectedResult, - Instruction *A, Instruction *B) - : FunctionPass(ID), ExpectedResult(ExpectedResult), A(A), B(B) {} - - static int initialize() { - PassInfo *PI = new PassInfo("isPotentiallyReachable testing pass", - "", &ID, nullptr, true, true); - PassRegistry::getPassRegistry()->registerPass(*PI, false); - initializeLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry()); - initializeDominatorTreeWrapperPassPass( - *PassRegistry::getPassRegistry()); - return 0; + IsPotentiallyReachableTestPass(bool ExpectedResult, Instruction *A, + Instruction *B, + SmallPtrSet ExclusionSet) + : FunctionPass(ID), ExpectedResult(ExpectedResult), A(A), B(B), + ExclusionSet(ExclusionSet) {} + + static int initialize() { + PassInfo *PI = new PassInfo("isPotentiallyReachable testing pass", "", + &ID, nullptr, true, true); + PassRegistry::getPassRegistry()->registerPass(*PI, false); + initializeLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry()); + initializeDominatorTreeWrapperPassPass( + *PassRegistry::getPassRegistry()); + return 0; } void getAnalysisUsage(AnalysisUsage &AU) const override { @@ -90,22 +99,26 @@ LoopInfo *LI = &getAnalysis().getLoopInfo(); DominatorTree *DT = &getAnalysis().getDomTree(); - EXPECT_EQ(isPotentiallyReachable(A, B, nullptr, nullptr), + EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, nullptr, nullptr), + ExpectedResult); + EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, DT, nullptr), + ExpectedResult); + EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, nullptr, LI), + ExpectedResult); + EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, DT, LI), ExpectedResult); - EXPECT_EQ(isPotentiallyReachable(A, B, DT, nullptr), ExpectedResult); - EXPECT_EQ(isPotentiallyReachable(A, B, nullptr, LI), ExpectedResult); - EXPECT_EQ(isPotentiallyReachable(A, B, DT, LI), ExpectedResult); return false; } bool ExpectedResult; Instruction *A, *B; + SmallPtrSet ExclusionSet; }; static int initialize = IsPotentiallyReachableTestPass::initialize(); (void)initialize; IsPotentiallyReachableTestPass *P = - new IsPotentiallyReachableTestPass(ExpectedResult, A, B); + new IsPotentiallyReachableTestPass(ExpectedResult, A, B, ExclusionSet); legacy::PassManager PM; PM.add(P); PM.run(*M); @@ -114,6 +127,7 @@ LLVMContext Context; std::unique_ptr M; Instruction *A, *B; + SmallPtrSet ExclusionSet; }; } @@ -425,3 +439,55 @@ "}"); ExpectPath(false); } + +TEST_F(IsPotentiallyReachableTest, SimpleExclusionTest) { + ParseAssembly("define void @test() {\n" + "entry:\n" + " %A = bitcast i8 undef to i8\n" + " br label %excluded\n" + "excluded:\n" + " br label %exit\n" + "exit:\n" + " %B = bitcast i8 undef to i8\n" + " ret void\n" + "}"); + ExpectPath(false); +} + +TEST_F(IsPotentiallyReachableTest, DiamondExcludedTest) { + ParseAssembly("declare i1 @switch()\n" + "\n" + "define void @test() {\n" + "entry:\n" + " %x = call i1 @switch()\n" + " %A = bitcast i8 undef to i8\n" + " br i1 %x, label %excluded.1, label %excluded.2\n" + "excluded.1:\n" + " br label %exit\n" + "excluded.2:\n" + " br label %exit\n" + "exit:\n" + " %B = bitcast i8 undef to i8\n" + " ret void\n" + "}"); + ExpectPath(false); +} + +TEST_F(IsPotentiallyReachableTest, DiamondOneSideExcludedTest) { + ParseAssembly("declare i1 @switch()\n" + "\n" + "define void @test() {\n" + "entry:\n" + " %x = call i1 @switch()\n" + " %A = bitcast i8 undef to i8\n" + " br i1 %x, label %excluded, label %diamond\n" + "excluded:\n" + " br label %exit\n" + "diamond:\n" + " br label %exit\n" + "exit:\n" + " %B = bitcast i8 undef to i8\n" + " ret void\n" + "}"); + ExpectPath(true); +}