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

3 files changed, 99 insertions, 53 deletions

diff --git a/include/llvm/Analysis/CFG.h b/include/llvm/Analysis/CFG.h
index 08fdc26..979926b 100644
--- a/include/llvm/Analysis/CFG.h
+++ b/include/llvm/Analysis/CFG.h
@@ -49,6 +49,9 @@ unsigned GetSuccessorNumber(BasicBlock *BB, BasicBlock *Succ);
 bool isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum,
                     bool AllowIdenticalEdges = false);
 
+/// \brief Determine whether instruction 'To' is reachable from 'From',
+/// 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
 /// 'To' can not be executed. Conservatively returns true.
@@ -64,6 +67,15 @@ bool isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum,
 bool isPotentiallyReachable(const Instruction *From, const Instruction *To,
                             DominatorTree *DT = 0, LoopInfo *LI = 0);
 
+/// \brief Determine whether block 'To' is reachable from 'From', 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 reached then
+/// 'To' can not be executed. Conservatively returns true.
+bool isPotentiallyReachable(const BasicBlock *From, const BasicBlock *To,
+                            DominatorTree *DT = 0, LoopInfo *LI = 0);
+
 } // End llvm namespace
 
 #endif
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<BasicBlock *> &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<const BasicBlock*, 64> Visited;
-  SmallVector<BasicBlock*, 32> Worklist;
-  Worklist.push_back(const_cast<BasicBlock*>(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<BasicBlock*, 32> Worklist;
+  Worklist.push_back(const_cast<BasicBlock*>(A));
+
+  return isPotentiallyReachableInner(Worklist, const_cast<BasicBlock*>(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<BasicBlock*, 32> 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<BasicBlock *>(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<BasicBlock*>(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<BasicBlock*>(B->getParent()),
+                                     DT, LI);
+}
diff --git a/unittests/Analysis/CFGTest.cpp b/unittests/Analysis/CFGTest.cpp
index 2358803..e931709 100644
--- a/unittests/Analysis/CFGTest.cpp
+++ b/unittests/Analysis/CFGTest.cpp
@@ -147,6 +147,23 @@ TEST_F(IsPotentiallyReachableTest, SameBlockPath) {
   ExpectPath(true);
 }
 
+TEST_F(IsPotentiallyReachableTest, SameBlockNoLoop) {
+  ParseAssembly(
+      "define void @test() {\n"
+      "entry:\n"
+      "  br label %middle\n"
+      "middle:\n"
+      "  %B = bitcast i8 undef to i8\n"
+      "  bitcast i8 undef to i8\n"
+      "  bitcast i8 undef to i8\n"
+      "  %A = bitcast i8 undef to i8\n"
+      "  br label %nextblock\n"
+      "nextblock:\n"
+      "  ret void\n"
+      "}\n");
+  ExpectPath(false);
+}
+
 TEST_F(IsPotentiallyReachableTest, StraightNoPath) {
   ParseAssembly(
       "define void @test() {\n"