3 files changed, 90 insertions, 0 deletions
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