From 72dba254ae65b06062106910a70d46f21e19d55a Mon Sep 17 00:00:00 2001 From: Nick Lewycky Date: Tue, 13 Aug 2013 00:03:47 +0000 Subject: Fix an oversight in isPotentiallyReachable where we wouldn't do any CFG-walking to find loops if the From and To instructions were in the same block. Refactor the code a little now that we need to fill to start the CFG-walking algorithm with more than one starting basic block sometimes. Special thanks to Andrew Trick for catching an error in my understanding of natural loops in code review. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@188236 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/CFG.cpp | 123 +++++++++++++++++++++++++++++---------------------- 1 file changed, 70 insertions(+), 53 deletions(-) (limited to 'lib/Analysis/CFG.cpp') diff --git a/lib/Analysis/CFG.cpp b/lib/Analysis/CFG.cpp index a5ed21a..be7e9fc 100644 --- a/lib/Analysis/CFG.cpp +++ b/lib/Analysis/CFG.cpp @@ -133,53 +133,9 @@ static bool loopContainsBoth(LoopInfo *LI, return L1 != NULL && L1 == L2; } -static bool isPotentiallyReachableSameBlock(const Instruction *A, - const Instruction *B, - LoopInfo *LI) { - // The same block case is special because it's the only time we're looking - // within a single block to see which comes first. Once we start looking at - // multiple blocks, the first instruction of the block is reachable, so we - // only need to determine reachability between whole blocks. - - const BasicBlock *BB = A->getParent(); - // If the block is in a loop then we can reach any instruction in the block - // from any other instruction in the block by going around the backedge. - // Check whether we're in a loop (or aren't sure). - - // Can't be in a loop if it's the entry block -- the entry block may not - // have predecessors. - bool HasLoop = BB != &BB->getParent()->getEntryBlock(); - - // Can't be in a loop if LoopInfo doesn't know about it. - if (LI && HasLoop) { - HasLoop = LI->getLoopFor(BB) != 0; - } - if (HasLoop) - return true; - - // Linear scan, start at 'A', see whether we hit 'B' or the end first. - for (BasicBlock::const_iterator I = A, E = BB->end(); I != E; ++I) { - if (&*I == B) - return true; - } - return false; -} - -bool llvm::isPotentiallyReachable(const Instruction *A, const Instruction *B, - DominatorTree *DT, LoopInfo *LI) { - assert(A->getParent()->getParent() == B->getParent()->getParent() && - "This analysis is function-local!"); - - const BasicBlock *StopBB = B->getParent(); - - if (A->getParent() == B->getParent()) - return isPotentiallyReachableSameBlock(A, B, LI); - - if (A->getParent() == &A->getParent()->getParent()->getEntryBlock()) - return true; - if (B->getParent() == &A->getParent()->getParent()->getEntryBlock()) - return false; - +static bool isPotentiallyReachableInner(SmallVectorImpl &Worklist, + BasicBlock *StopBB, + DominatorTree *DT, 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)) @@ -188,11 +144,7 @@ bool llvm::isPotentiallyReachable(const Instruction *A, const Instruction *B, // 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; - SmallSet Visited; - SmallVector Worklist; - Worklist.push_back(const_cast(A->getParent())); - do { BasicBlock *BB = Worklist.pop_back_val(); if (!Visited.insert(BB)) @@ -221,7 +173,72 @@ bool llvm::isPotentiallyReachable(const Instruction *A, const Instruction *B, } } while (!Worklist.empty()); - // We have exhaustived all possible paths and are certain that 'To' can not - // be reached from 'From'. + // We have exhausted all possible paths and are certain that 'To' can not be + // reached from 'From'. return false; } + +bool llvm::isPotentiallyReachable(const BasicBlock *A, const BasicBlock *B, + DominatorTree *DT, LoopInfo *LI) { + assert(A->getParent() == B->getParent() && + "This analysis is function-local!"); + + SmallVector Worklist; + Worklist.push_back(const_cast(A)); + + return isPotentiallyReachableInner(Worklist, const_cast(B), + DT, LI); +} + +bool llvm::isPotentiallyReachable(const Instruction *A, const Instruction *B, + DominatorTree *DT, LoopInfo *LI) { + assert(A->getParent()->getParent() == B->getParent()->getParent() && + "This analysis is function-local!"); + + SmallVector Worklist; + + if (A->getParent() == B->getParent()) { + // The same block case is special because it's the only time we're looking + // within a single block to see which instruction comes first. Once we + // start looking at multiple blocks, the first instruction of the block is + // reachable, so we only need to determine reachability between whole + // blocks. + BasicBlock *BB = const_cast(A->getParent()); + + // If the block is in a loop then we can reach any instruction in the block + // from any other instruction in the block by going around a backedge. + if (LI && LI->getLoopFor(BB) != 0) + return true; + + // Linear scan, start at 'A', see whether we hit 'B' or the end first. + for (BasicBlock::const_iterator I = A, E = BB->end(); I != E; ++I) { + if (&*I == B) + return true; + } + + // Can't be in a loop if it's the entry block -- the entry block may not + // have predecessors. + if (BB == &BB->getParent()->getEntryBlock()) + return false; + + // Otherwise, continue doing the normal per-BB CFG walk. + for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) + Worklist.push_back(*I); + + if (Worklist.empty()) { + // We've proven that there's no path! + return false; + } + } else { + Worklist.push_back(const_cast(A->getParent())); + } + + if (A->getParent() == &A->getParent()->getParent()->getEntryBlock()) + return true; + if (B->getParent() == &A->getParent()->getParent()->getEntryBlock()) + return false; + + return isPotentiallyReachableInner(Worklist, + const_cast(B->getParent()), + DT, LI); +} -- cgit v1.1 From 328a4fbfbb778de44d9a738c3efdfd42a58925d9 Mon Sep 17 00:00:00 2001 From: Jakub Staszak Date: Tue, 20 Aug 2013 23:04:15 +0000 Subject: Add some constantness. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@188844 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/CFG.cpp | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-) (limited to 'lib/Analysis/CFG.cpp') diff --git a/lib/Analysis/CFG.cpp b/lib/Analysis/CFG.cpp index be7e9fc..c3f32d3 100644 --- a/lib/Analysis/CFG.cpp +++ b/lib/Analysis/CFG.cpp @@ -116,7 +116,7 @@ bool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum, // LoopInfo contains a mapping from basic block to the innermost loop. Find // the outermost loop in the loop nest that contains BB. -static const Loop *getOutermostLoop(LoopInfo *LI, const BasicBlock *BB) { +static const Loop *getOutermostLoop(const LoopInfo *LI, const BasicBlock *BB) { const Loop *L = LI->getLoopFor(BB); if (L) { while (const Loop *Parent = L->getParentLoop()) @@ -126,7 +126,7 @@ static const Loop *getOutermostLoop(LoopInfo *LI, const BasicBlock *BB) { } // True if there is a loop which contains both BB1 and BB2. -static bool loopContainsBoth(LoopInfo *LI, +static bool loopContainsBoth(const LoopInfo *LI, const BasicBlock *BB1, const BasicBlock *BB2) { const Loop *L1 = getOutermostLoop(LI, BB1); const Loop *L2 = getOutermostLoop(LI, BB2); @@ -135,7 +135,8 @@ static bool loopContainsBoth(LoopInfo *LI, static bool isPotentiallyReachableInner(SmallVectorImpl &Worklist, BasicBlock *StopBB, - DominatorTree *DT, LoopInfo *LI) { + 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)) @@ -179,7 +180,7 @@ static bool isPotentiallyReachableInner(SmallVectorImpl &Worklist, } bool llvm::isPotentiallyReachable(const BasicBlock *A, const BasicBlock *B, - DominatorTree *DT, LoopInfo *LI) { + const DominatorTree *DT, const LoopInfo *LI) { assert(A->getParent() == B->getParent() && "This analysis is function-local!"); @@ -191,7 +192,7 @@ bool llvm::isPotentiallyReachable(const BasicBlock *A, const BasicBlock *B, } bool llvm::isPotentiallyReachable(const Instruction *A, const Instruction *B, - DominatorTree *DT, LoopInfo *LI) { + const DominatorTree *DT, const LoopInfo *LI) { assert(A->getParent()->getParent() == B->getParent()->getParent() && "This analysis is function-local!"); -- cgit v1.1