Migrate CFGReachabilityAnalysis out of the IdempotentOperationsChecker and into its own analysis file.

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

6 files changed, 152 insertions, 84 deletions

diff --git a/include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h b/include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h
new file mode 100644
index 0000000000..72f644aaf0
--- /dev/null
+++ b/include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h
@@ -0,0 +1,49 @@
+//==- CFGReachabilityAnalysis.h - Basic reachability analysis ----*- C++ -*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines a flow-sensitive, (mostly) path-insensitive reachability
+// analysis based on Clang's CFGs.  Clients can query if a given basic block
+// is reachable within the CFG.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef CLANG_ANALYSIS_CFG_REACHABILITY
+#define CLANG_ANALYSIS_CFG_REACHABILITY
+
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/DenseMap.h"
+
+namespace clang {
+
+class CFG;
+class CFGBlock;
+  
+// A class that performs reachability queries for CFGBlocks. Several internal
+// checks in this checker require reachability information. The requests all
+// tend to have a common destination, so we lazily do a predecessor search
+// from the destination node and cache the results to prevent work
+// duplication.
+class CFGReachabilityAnalysis {
+  typedef llvm::BitVector ReachableSet;
+  typedef llvm::DenseMap<unsigned, ReachableSet> ReachableMap;
+  ReachableSet analyzed;
+  ReachableMap reachable;
+public:
+  CFGReachabilityAnalysis(const CFG &cfg);
+
+  /// Returns true if the block 'Dst' can be reached from block 'Src'.
+  bool isReachable(const CFGBlock *Src, const CFGBlock *Dst);
+
+private:
+  void mapReachability(const CFGBlock *Dst);
+};
+  
+}
+
+#endif
diff --git a/include/clang/Analysis/AnalysisContext.h b/include/clang/Analysis/AnalysisContext.h
index 69446eb814..8514514578 100644
--- a/include/clang/Analysis/AnalysisContext.h
+++ b/include/clang/Analysis/AnalysisContext.h
@@ -29,6 +29,7 @@ class Decl;
 class Stmt;
 class CFG;
 class CFGBlock;
+class CFGReachabilityAnalysis;
 class CFGStmtMap;
 class LiveVariables;
 class ParentMap;
@@ -55,6 +56,7 @@ class AnalysisContext {
   LiveVariables *relaxedLiveness;
   ParentMap *PM;
   PseudoConstantAnalysis *PCA;
+  CFGReachabilityAnalysis *CFA;
   llvm::DenseMap<const BlockDecl*,void*> *ReferencedBlockVars;
   llvm::BumpPtrAllocator A;
   bool UseUnoptimizedCFG;  
@@ -69,7 +71,7 @@ public:
                   bool addInitializers = false)
     : D(d), TU(tu), cfg(0), completeCFG(0), cfgStmtMap(0),
       builtCFG(false), builtCompleteCFG(false),
-      liveness(0), relaxedLiveness(0), PM(0), PCA(0),
+      liveness(0), relaxedLiveness(0), PM(0), PCA(0), CFA(0),
       ReferencedBlockVars(0), UseUnoptimizedCFG(useUnoptimizedCFG),
       AddEHEdges(addehedges), AddImplicitDtors(addImplicitDtors),
       AddInitializers(addInitializers) {}
@@ -96,6 +98,8 @@ public:
   
   CFGStmtMap *getCFGStmtMap();
 
+  CFGReachabilityAnalysis *getCFGReachablityAnalysis();
+  
   /// Return a version of the CFG without any edges pruned.
   CFG *getUnoptimizedCFG();
 
diff --git a/lib/Analysis/AnalysisContext.cpp b/lib/Analysis/AnalysisContext.cpp
index a982a5c5be..62097ef20d 100644
--- a/lib/Analysis/AnalysisContext.cpp
+++ b/lib/Analysis/AnalysisContext.cpp
@@ -19,6 +19,7 @@
 #include "clang/AST/StmtVisitor.h"
 #include "clang/Analysis/Analyses/LiveVariables.h"
 #include "clang/Analysis/Analyses/PseudoConstantAnalysis.h"
+#include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h"
 #include "clang/Analysis/AnalysisContext.h"
 #include "clang/Analysis/CFG.h"
 #include "clang/Analysis/CFGStmtMap.h"
@@ -98,7 +99,18 @@ CFGStmtMap *AnalysisContext::getCFGStmtMap() {
     
   return 0;
 }
+
+CFGReachabilityAnalysis *AnalysisContext::getCFGReachablityAnalysis() {
+  if (CFA)
+    return CFA;
+  
+  if (CFG *c = getCFG()) {
+    CFA = new CFGReachabilityAnalysis(*c);
+    return CFA;
+  }
   
+  return 0;
+}
 
 void AnalysisContext::dumpCFG() {
     getCFG()->dump(getASTContext().getLangOptions());
@@ -365,6 +377,7 @@ AnalysisContext::~AnalysisContext() {
   delete relaxedLiveness;
   delete PM;
   delete PCA;
+  delete CFA;
   delete ReferencedBlockVars;
 }
 
diff --git a/lib/Analysis/CFGReachabilityAnalysis.cpp b/lib/Analysis/CFGReachabilityAnalysis.cpp
new file mode 100644
index 0000000000..7786584901
--- /dev/null
+++ b/lib/Analysis/CFGReachabilityAnalysis.cpp
@@ -0,0 +1,76 @@
+//==- CFGReachabilityAnalysis.cpp - Basic reachability analysis --*- C++ -*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines a flow-sensitive, (mostly) path-insensitive reachability
+// analysis based on Clang's CFGs.  Clients can query if a given basic block
+// is reachable within the CFG.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/SmallVector.h"
+#include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h"
+#include "clang/Analysis/CFG.h"
+
+using namespace clang;
+
+CFGReachabilityAnalysis::CFGReachabilityAnalysis(const CFG &cfg)
+  : analyzed(cfg.getNumBlockIDs(), false) {}
+
+bool CFGReachabilityAnalysis::isReachable(const CFGBlock *Src,
+                                          const CFGBlock *Dst) {
+
+  const unsigned DstBlockID = Dst->getBlockID();
+  
+  // If we haven't analyzed the destination node, run the analysis now
+  if (!analyzed[DstBlockID]) {
+    mapReachability(Dst);
+    analyzed[DstBlockID] = true;
+  }
+  
+  // Return the cached result
+  return reachable[DstBlockID][Src->getBlockID()];
+}
+
+// Maps reachability to a common node by walking the predecessors of the
+// destination node.
+void CFGReachabilityAnalysis::mapReachability(const CFGBlock *Dst) {
+  llvm::SmallVector<const CFGBlock *, 11> worklist;
+  llvm::BitVector visited(analyzed.size());
+  
+  ReachableSet &DstReachability = reachable[Dst->getBlockID()];
+  DstReachability.resize(analyzed.size(), false);
+  
+  // Start searching from the destination node, since we commonly will perform
+  // multiple queries relating to a destination node.
+  worklist.push_back(Dst);
+  bool firstRun = true;
+  
+  while (!worklist.empty()) {    
+    const CFGBlock *block = worklist.back();
+    worklist.pop_back();
+    
+    if (visited[block->getBlockID()])
+      continue;
+    visited[block->getBlockID()] = true;
+    
+    // Update reachability information for this node -> Dst
+    if (!firstRun) {
+      // Don't insert Dst -> Dst unless it was a predecessor of itself
+      DstReachability[block->getBlockID()] = true;
+    }
+    else
+      firstRun = false;
+    
+    // Add the predecessors to the worklist.
+    for (CFGBlock::const_pred_iterator i = block->pred_begin(), 
+         e = block->pred_end(); i != e; ++i) {
+      worklist.push_back(*i);
+    }
+  }
+}
diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt
index 0912f3c874..84b211f2cf 100644
--- a/lib/Analysis/CMakeLists.txt
+++ b/lib/Analysis/CMakeLists.txt
@@ -3,6 +3,7 @@ set(LLVM_USED_LIBS clangBasic clangAST clangIndex)
 add_clang_library(clangAnalysis
   AnalysisContext.cpp
   CFG.cpp
+  CFGReachabilityAnalysis.cpp
   CFGStmtMap.cpp
   CocoaConventions.cpp
   FormatString.cpp
diff --git a/lib/StaticAnalyzer/Checkers/IdempotentOperationChecker.cpp b/lib/StaticAnalyzer/Checkers/IdempotentOperationChecker.cpp
index 0d2ccb955f..171b39efe2 100644
--- a/lib/StaticAnalyzer/Checkers/IdempotentOperationChecker.cpp
+++ b/lib/StaticAnalyzer/Checkers/IdempotentOperationChecker.cpp
@@ -45,6 +45,7 @@
 #include "ClangSACheckers.h"
 #include "clang/Analysis/CFGStmtMap.h"
 #include "clang/Analysis/Analyses/PseudoConstantAnalysis.h"
+#include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h"
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
@@ -83,9 +84,8 @@ private:
   static bool isUnused(const Expr *E, AnalysisContext *AC);
   static bool isTruncationExtensionAssignment(const Expr *LHS,
                                               const Expr *RHS);
-  bool pathWasCompletelyAnalyzed(const CFG *cfg,
+  bool pathWasCompletelyAnalyzed(AnalysisContext *AC,
                                  const CFGBlock *CB,
-                                 const CFGStmtMap *CBM,
                                  const CoreEngine &CE);
   static bool CanVary(const Expr *Ex,
                       AnalysisContext *AC);
@@ -105,26 +105,6 @@ private:
   typedef llvm::DenseMap<const BinaryOperator *, BinaryOperatorData>
       AssumptionMap;
   AssumptionMap hash;
-
-  // A class that performs reachability queries for CFGBlocks. Several internal
-  // checks in this checker require reachability information. The requests all
-  // tend to have a common destination, so we lazily do a predecessor search
-  // from the destination node and cache the results to prevent work
-  // duplication.
-  class CFGReachabilityAnalysis {
-    typedef llvm::BitVector ReachableSet;
-    typedef llvm::DenseMap<unsigned, ReachableSet> ReachableMap;
-    ReachableSet analyzed;
-    ReachableMap reachable;
-  public:
-    CFGReachabilityAnalysis(const CFG &cfg)
-      : analyzed(cfg.getNumBlockIDs(), false) {}
-    
-    inline bool isReachable(const CFGBlock *Src, const CFGBlock *Dst);
-  private:
-    void MapReachability(const CFGBlock *Dst);
-  };
-  llvm::OwningPtr<CFGReachabilityAnalysis> CRA;
 };
 }
 
@@ -397,11 +377,9 @@ void IdempotentOperationChecker::VisitEndAnalysis(ExplodedGraph &G,
     // If the analyzer did not finish, check to see if we can still emit this
     // warning
     if (Eng.hasWorkRemaining()) {
-      const CFGStmtMap *CBM = AC->getCFGStmtMap();
-
       // If we can trace back
-      if (!pathWasCompletelyAnalyzed(AC->getCFG(),
-                                     CBM->getBlock(B), CBM,
+      if (!pathWasCompletelyAnalyzed(AC,
+                                     AC->getCFGStmtMap()->getBlock(B),
                                      Eng.getCoreEngine()))
         continue;
     }
@@ -561,13 +539,11 @@ bool IdempotentOperationChecker::isTruncationExtensionAssignment(
 // Returns false if a path to this block was not completely analyzed, or true
 // otherwise.
 bool
-IdempotentOperationChecker::pathWasCompletelyAnalyzed(const CFG *cfg,
+IdempotentOperationChecker::pathWasCompletelyAnalyzed(AnalysisContext *AC,
                                                       const CFGBlock *CB,
-                                                      const CFGStmtMap *CBM,
                                                       const CoreEngine &CE) {
 
-  if (!CRA.get())
-    CRA.reset(new CFGReachabilityAnalysis(*cfg));
+  CFGReachabilityAnalysis *CRA = AC->getCFGReachablityAnalysis();
   
   // Test for reachability from any aborted blocks to this block
   typedef CoreEngine::BlocksAborted::const_iterator AbortedIterator;
@@ -618,14 +594,14 @@ IdempotentOperationChecker::pathWasCompletelyAnalyzed(const CFG *cfg,
       return CRA.isReachable(B, TargetBlock);
     }
   };
-  VisitWL visitWL(CBM, CB, *CRA.get());
+  VisitWL visitWL(AC->getCFGStmtMap(), CB, *CRA);
   // Were there any items in the worklist that could potentially reach
   // this block?
   if (CE.getWorkList()->visitItemsInWorkList(visitWL))
     return false;
 
   // Verify that this block is reachable from the entry block
-  if (!CRA->isReachable(&cfg->getEntry(), CB))
+  if (!CRA->isReachable(&AC->getCFG()->getEntry(), CB))
     return false;
 
   // If we get to this point, there is no connection to the entry block or an
@@ -763,57 +739,6 @@ bool IdempotentOperationChecker::containsNonLocalVarDecl(const Stmt *S) {
   return false;
 }
 
-bool IdempotentOperationChecker::CFGReachabilityAnalysis::isReachable(
-                                                          const CFGBlock *Src,
-                                                          const CFGBlock *Dst) {
-  const unsigned DstBlockID = Dst->getBlockID();
-
-  // If we haven't analyzed the destination node, run the analysis now
-  if (!analyzed[DstBlockID]) {
-    MapReachability(Dst);
-    analyzed[DstBlockID] = true;
-  }
-
-  // Return the cached result
-  return reachable[DstBlockID][Src->getBlockID()];
-}
 
-// Maps reachability to a common node by walking the predecessors of the
-// destination node.
-void IdempotentOperationChecker::CFGReachabilityAnalysis::MapReachability(
-                                                          const CFGBlock *Dst) {
 
-  llvm::SmallVector<const CFGBlock *, 11> worklist;
-  llvm::BitVector visited(analyzed.size());
-  
-  ReachableSet &DstReachability = reachable[Dst->getBlockID()];
-  DstReachability.resize(analyzed.size(), false);
-
-  // Start searching from the destination node, since we commonly will perform
-  // multiple queries relating to a destination node.
-  worklist.push_back(Dst);
-  bool firstRun = true;
-
-  while (!worklist.empty()) {    
-    const CFGBlock *block = worklist.back();
-    worklist.pop_back();
-    
-    if (visited[block->getBlockID()])
-      continue;
-    visited[block->getBlockID()] = true;
-    
-    // Update reachability information for this node -> Dst
-    if (!firstRun) {
-      // Don't insert Dst -> Dst unless it was a predecessor of itself
-      DstReachability[block->getBlockID()] = true;
-    }
-    else
-      firstRun = false;
 
-    // Add the predecessors to the worklist.
-    for (CFGBlock::const_pred_iterator i = block->pred_begin(), 
-         e = block->pred_end(); i != e; ++i) {
-      worklist.push_back(*i);
-    }
-  }
-}