Reimplement isPotentiallyReachable to make nocapture deduction much stronger.

Adds unit tests for it too.

Split BasicBlockUtils into an analysis-half and a transforms-half, and put the
analysis bits into a new Analysis/CFG.{h,cpp}. Promote isPotentiallyReachable
into llvm::isPotentiallyReachable and move it into Analysis/CFG.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@187283 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 3 insertions, 22 deletions

diff --git a/lib/Analysis/AliasAnalysis.cpp b/lib/Analysis/AliasAnalysis.cpp
index 5be5613b124..b8b6d37a792 100644
--- a/lib/Analysis/AliasAnalysis.cpp
+++ b/lib/Analysis/AliasAnalysis.cpp
@@ -26,6 +26,7 @@
 
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/CaptureTracking.h"
+#include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/Dominators.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/BasicBlock.h"
@@ -361,26 +362,6 @@ AliasAnalysis::getModRefInfo(const AtomicRMWInst *RMW, const Location &Loc) {
 }
 
 namespace {
-  /// 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.
-  static bool isPotentiallyReachable(const BasicBlock *From,
-                                     const BasicBlock *To) {
-    const unsigned MaxCheck = 5;
-    const BasicBlock *Current = From;
-    for (unsigned I = 0; I < MaxCheck; I++) {
-      unsigned NumSuccs = Current->getTerminator()->getNumSuccessors();
-      if (NumSuccs > 1)
-        return true;
-      if (NumSuccs == 0)
-        return false;
-      Current = Current->getTerminator()->getSuccessor(0);
-      if (Current == To)
-        return true;
-    }
-    return true;
-  }
-
   /// Only find pointer captures which happen before the given instruction. Uses
   /// the dominator tree to determine whether one instruction is before another.
   /// Only support the case where the Value is defined in the same basic block
@@ -402,7 +383,7 @@ namespace {
       // 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(BB, BeforeHere->getParent()))
+          !isPotentiallyReachable(I, BeforeHere, DT))
         return false;
       return true;
     }
@@ -414,7 +395,7 @@ namespace {
       if (BeforeHere != I && !DT->isReachableFromEntry(BB))
         return false;
       if (BeforeHere != I && DT->dominates(BeforeHere, I) &&
-          !isPotentiallyReachable(BB, BeforeHere->getParent()))
+          !isPotentiallyReachable(I, BeforeHere, DT))
         return false;
       Captured = true;
       return true;