2 files changed, 59 insertions, 2 deletions

diff --git a/include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h b/include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h
new file mode 100644
index 0000000..72f644a
--- /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 2ecbfdc..8514514 100644
--- a/include/clang/Analysis/AnalysisContext.h
+++ b/include/clang/Analysis/AnalysisContext.h
@@ -29,6 +29,8 @@ class Decl;
 class Stmt;
 class CFG;
 class CFGBlock;
+class CFGReachabilityAnalysis;
+class CFGStmtMap;
 class LiveVariables;
 class ParentMap;
 class PseudoConstantAnalysis;
@@ -48,11 +50,13 @@ class AnalysisContext {
 
   // AnalysisContext owns the following data.
   CFG *cfg, *completeCFG;
+  CFGStmtMap *cfgStmtMap;
   bool builtCFG, builtCompleteCFG;
   LiveVariables *liveness;
   LiveVariables *relaxedLiveness;
   ParentMap *PM;
   PseudoConstantAnalysis *PCA;
+  CFGReachabilityAnalysis *CFA;
   llvm::DenseMap<const BlockDecl*,void*> *ReferencedBlockVars;
   llvm::BumpPtrAllocator A;
   bool UseUnoptimizedCFG;  
@@ -65,9 +69,9 @@ public:
                   bool addehedges = false,
                   bool addImplicitDtors = false,
                   bool addInitializers = false)
-    : D(d), TU(tu), cfg(0), completeCFG(0),
+    : 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) {}
@@ -91,7 +95,11 @@ public:
 
   Stmt *getBody();
   CFG *getCFG();
+  
+  CFGStmtMap *getCFGStmtMap();
 
+  CFGReachabilityAnalysis *getCFGReachablityAnalysis();
+  
   /// Return a version of the CFG without any edges pruned.
   CFG *getUnoptimizedCFG();