Add CFGStmtMap, which defines a mapping from Stmt* to CFGBlock*. The immediate intended use is in the unreachable code analysis.

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

3 files changed, 141 insertions, 0 deletions

diff --git a/include/clang/Analysis/CFGStmtMap.h b/include/clang/Analysis/CFGStmtMap.h
new file mode 100644
index 0000000000..6e8e140afb
--- /dev/null
+++ b/include/clang/Analysis/CFGStmtMap.h
@@ -0,0 +1,52 @@
+//===--- CFGStmtMap.h - Map from Stmt* to CFGBlock* -----------*- 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 the CFGStmtMap class, which defines a mapping from
+//  Stmt* to CFGBlock*
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_CFGSTMTMAP_H
+#define LLVM_CLANG_CFGSTMTMAP_H
+
+#include "clang/Analysis/CFG.h"
+
+namespace clang {
+
+class CFG;
+class CFGBlock;
+class ParentMap;
+class Stmt;
+
+class CFGStmtMap {
+  ParentMap *PM;
+  void *M;
+  
+  CFGStmtMap(ParentMap *pm, void *m) : PM(pm), M(m) {}
+  
+public:
+  ~CFGStmtMap();
+  
+  /// Returns a new CFGMap for the given CFG.  It is the caller's
+  /// responsibility to 'delete' this object when done using it.
+  static CFGStmtMap *Build(CFG* C, ParentMap *PM);
+
+  /// Returns the CFGBlock the specified Stmt* appears in.  For Stmt* that
+  /// are terminators, the CFGBlock is the block they appear as a terminator,
+  /// and not the block they appear as a block-level expression (e.g, '&&').
+  /// CaseStmts and LabelStmts map to the CFGBlock they label.
+  CFGBlock *getBlock(Stmt * S);
+
+  const CFGBlock *getBlock(const Stmt * S) const {
+    return const_cast<CFGStmtMap*>(this)->getBlock(const_cast<Stmt*>(S));
+  }
+};
+
+} // end clang namespace
+#endif
diff --git a/lib/Analysis/CFGStmtMap.cpp b/lib/Analysis/CFGStmtMap.cpp
new file mode 100644
index 0000000000..88c90cd50d
--- /dev/null
+++ b/lib/Analysis/CFGStmtMap.cpp
@@ -0,0 +1,88 @@
+//===--- CFGStmtMap.h - Map from Stmt* to CFGBlock* -----------*- 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 the CFGStmtMap class, which defines a mapping from
+//  Stmt* to CFGBlock*
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/DenseMap.h"
+#include "clang/AST/ParentMap.h"
+#include "clang/Analysis/CFG.h"
+#include "clang/Analysis/CFGStmtMap.h"
+
+using namespace clang;
+
+typedef llvm::DenseMap<Stmt*,CFGBlock*> SMap;
+static SMap *AsMap(void *m) { return (SMap*) m; }
+
+CFGStmtMap::~CFGStmtMap() { delete AsMap(M); }
+
+CFGBlock *CFGStmtMap::getBlock(Stmt *S) {  
+  SMap *SM = AsMap(M);
+  Stmt *X = S;
+
+  // If 'S' isn't in the map, walk the ParentMap to see if one of its ancestors
+  // is in the map.
+  while (X) {
+    SMap::iterator I = SM->find(S);
+    if (I != SM->end()) {
+      CFGBlock *B = I->second;
+      // Memoize this lookup.
+      if (X != S)
+        (*SM)[X] = B;
+      return B;
+    }
+
+    Stmt *X = PM->getParentIgnoreParens(X);
+  }
+  
+  return 0;
+}
+
+static void Accumulate(SMap &SM, CFGBlock *B) {
+  // First walk the block-level expressions.
+  for (CFGBlock::iterator I = B->begin(), E = B->end(); I != E; ++I) {
+    const CFGElement &CE = *I;
+    if (Stmt *S = CE.getStmt()) {
+      CFGBlock *&Entry = SM[S];
+      // If 'Entry' is already initialized (e.g., a terminator was already),
+      // skip.
+      if (Entry)
+        continue;
+      
+      Entry = B;
+    }
+  }
+  
+  // Look at the label of the block.
+  if (Stmt *Label = B->getLabel())
+    SM[Label] = B;
+
+  // Finally, look at the terminator.  If the terminator was already added
+  // because it is a block-level expression in another block, overwrite
+  // that mapping.
+  if (Stmt *Term = B->getTerminator())
+    SM[Term] = B;
+}
+
+CFGStmtMap *CFGStmtMap::Build(CFG *C, ParentMap *PM) {
+  if (!C || !PM)
+    return 0;
+
+  SMap *SM = new SMap();
+
+  // Walk all blocks, accumulating the block-level expressions, labels,
+  // and terminators.  
+  for (CFG::iterator I = C->begin(), E = C->end(); I != E; ++I)
+    Accumulate(*SM, *I);
+
+  return new CFGStmtMap(PM, SM);
+}
+
diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt
index d24ae889d5..8d576a9386 100644
--- a/lib/Analysis/CMakeLists.txt
+++ b/lib/Analysis/CMakeLists.txt
@@ -3,6 +3,7 @@ set(LLVM_NO_RTTI 1)
 add_clang_library(clangAnalysis
   AnalysisContext.cpp
   CFG.cpp
+  CFGStmtMap.cpp
   FormatString.cpp
   LiveVariables.cpp
   PrintfFormatString.cpp