Added extensions (subclasses) to the StmtVisitor class that

are useful for dataflow analysis: CFGStmtVisitor and DataflowStmtVisitor.

CFGStmtVisitor is the same as StmtVisitor is that it has separate visitors
for "root" statements in a CFGBlock (statements that have a designated
slot int the list of statements in a CFGBlock).  It also recognizes statements
that have implicit control-flow, and calls special visitor methods for those.

DataflowStmtVisitor extends CFGStmtVisitor to serve as a template for
implementing transfer functions.  It does a pre-/post-order traversal of
substatements depending on whether we are doing a forward/backward analysis.
It also has special handling for implicit-control-flow statements so that
they are visited only once.

llvm-svn: 41884

2 files changed, 229 insertions, 0 deletions

diff --git a/clang/include/clang/Analysis/CFGStmtVisitor.h b/clang/include/clang/Analysis/CFGStmtVisitor.h
new file mode 100644
index 000000000000..3e72598767dc
--- /dev/null
+++ b/clang/include/clang/Analysis/CFGStmtVisitor.h
@@ -0,0 +1,99 @@
+//===--- CFGStmtVisitor.h - Visitor for Stmts in a CFG ----------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by Ted Kremenek and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines the CFGStmtVisitor interface, which extends 
+//  StmtVisitor.  This interface is useful for visiting statements in a CFG
+//  where some statements have implicit control-flow and thus should
+//  be treated specially.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_CFGSTMTVISITOR_H
+#define LLVM_CLANG_ANALYSIS_CFGSTMTVISITOR_H
+
+#include "clang/AST/StmtVisitor.h"
+#include "clang/AST/CFG.h"
+
+namespace clang {
+
+#define DISPATCH_CASE(CLASS) \
+case Stmt::CLASS ## Class: return \
+static_cast<ImplClass*>(this)->BlockStmt_Visit ## CLASS(static_cast<CLASS*>(S));  
+
+#define DEFAULT_BLOCKSTMT_VISIT(CLASS) RetTy BlockStmt_Visit ## CLASS(CLASS *S)\
+{ return\
+  static_cast<ImplClass*>(this)->BlockStmt_VisitImplicitControlFlowStmt(S); }  
+
+template <typename ImplClass, typename RetTy=void>
+class CFGStmtVisitor : public StmtVisitor<ImplClass,RetTy> {
+public:
+  /// BlockVisit_XXX - Visitor methods for visiting the "root" statements in
+  /// CFGBlocks.  Root statements are the statements that appear explicitly in 
+  /// the list of statements in a CFGBlock.  For substatements, or when there
+  /// is no implementation provided for a BlockStmt_XXX method, we default
+  /// to using StmtVisitor's Visit method.
+  RetTy BlockStmt_Visit(Stmt* S) {
+    switch (S->getStmtClass()) {    
+      DISPATCH_CASE(CallExpr)
+      DISPATCH_CASE(StmtExpr)
+      DISPATCH_CASE(ConditionalOperator)
+
+      case Stmt::BinaryOperatorClass: {
+        BinaryOperator* B = cast<BinaryOperator>(S);
+        if (B->isLogicalOp())
+          return static_cast<ImplClass*>(this)->BlockStmt_VisitLogicalOp(B);
+        else if (B->getOpcode() == BinaryOperator::Comma)
+          return static_cast<ImplClass*>(this)->BlockStmt_VisitComma(B);
+        // Fall through.
+      }
+      
+      default:
+        return static_cast<ImplClass*>(this)->BlockStmt_VisitStmt(S);                             
+    }
+  }
+
+  DEFAULT_BLOCKSTMT_VISIT(CallExpr)
+  DEFAULT_BLOCKSTMT_VISIT(StmtExpr)
+  DEFAULT_BLOCKSTMT_VISIT(ConditionalOperator)
+  
+  RetTy BlockStmt_VisitImplicitControlFlowStmt(Stmt* S) {
+    return static_cast<ImplClass*>(this)->BlockStmt_VisitStmt(S);
+  }
+  
+  RetTy BlockStmt_VisitStmt(Stmt* S) {
+    return static_cast<ImplClass*>(this)->Visit(S);
+  }
+
+  RetTy BlockStmt_VisitLogicalOp(BinaryOperator* B) {
+    return 
+     static_cast<ImplClass*>(this)->BlockStmt_VisitImplicitControlFlowStmt(B);
+  }
+  
+  RetTy BlockStmt_VisitComma(BinaryOperator* B) {
+    return
+     static_cast<ImplClass*>(this)->BlockStmt_VisitImplicitControlFlowStmt(B);
+  }
+
+  //===--------------------------------------------------------------------===//
+  // Utility methods.  Not called by default (but subclasses may use them).
+  //===--------------------------------------------------------------------===//
+    
+  /// VisitChildren: Call "Visit" on each child of S.
+  void VisitChildren(Stmt* S) {
+    for (Stmt::child_iterator I=S->child_begin(), E=S->child_end(); I != E;++I)
+      static_cast<ImplClass*>(this)->Visit(*I);    
+  }
+};  
+      
+#undef DEFAULT_BLOCKSTMT_VISIT
+#undef DISPATCH_CASE
+
+}  // end namespace clang
+
+#endif
diff --git a/clang/include/clang/Analysis/DataflowStmtVisitor.h b/clang/include/clang/Analysis/DataflowStmtVisitor.h
new file mode 100644
index 000000000000..67c4a75c73ac
--- /dev/null
+++ b/clang/include/clang/Analysis/DataflowStmtVisitor.h
@@ -0,0 +1,130 @@
+//===--- DataFlowStmtVisitor.h - StmtVisitor for Dataflow -------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by Ted Kremenek and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines the DataflowStmtVisitor interface, which extends 
+//  CFGStmtVisitor.  This interface is useful for visiting statements in a CFG
+//  with the understanding that statements are walked in order of the analysis
+//  traversal.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_DATAFLOW_STMTVISITOR_H
+#define LLVM_CLANG_ANALYSIS_DATAFLOW_STMTVISITOR_H
+
+#include "clang/Analysis/CFGStmtVisitor.h"
+
+namespace clang {
+
+// Tag classes describing what direction the dataflow analysis goes.
+namespace dataflow {
+  struct forward_analysis_tag {};
+  struct backward_analysis_tag {};
+}  
+
+template < typename ImplClass, 
+           typename AnalysisTag=dataflow::forward_analysis_tag >
+class DataflowStmtVisitor : public CFGStmtVisitor<ImplClass,void> {
+public:
+  //===--------------------------------------------------------------------===//
+  // Observer methods.  These are called before a statement is visited, and
+  //  there is no special dispatch on statement type.  This allows subclasses
+  //  to inject extra functionality (e.g. monitoring) that applies to all
+  //  visited statements.
+  //===--------------------------------------------------------------------===//
+  
+  void ObserveStmt(Stmt* S) {}
+  
+  void ObserveBlockStmt(Stmt* S) {
+    static_cast<ImplClass*>(this)->ObserveStmt(S);
+  }
+  
+  //===--------------------------------------------------------------------===//
+  // Statment visitor methods.  These modify the behavior of CFGVisitor::Visit
+  //  and CFGVisitor::BlockStmt_Visit by performing a traversal of substatements
+  //  depending on the direction of the dataflow analysis.  For forward
+  //  analyses, the traversal is postorder (representing evaluation order)
+  //  and for backward analysis it is preorder (reverse-evaluation order).
+  //===--------------------------------------------------------------------===//
+
+  void BlockStmt_Visit(Stmt* S) { BlockStmt_Visit(S,AnalysisTag()); }
+
+  void BlockStmt_Visit(Stmt* S, dataflow::forward_analysis_tag) {      
+    // Process statements in a postorder traversal of the AST. 
+    if (!CFG::hasImplicitControlFlow(S) &&
+        S->getStmtClass() != Stmt::CallExprClass)
+      static_cast<ImplClass*>(this)->VisitChildren(S);
+      
+    static_cast<ImplClass*>(this)->ObserveBlockStmt(S);
+    static_cast<CFGStmtVisitor<ImplClass,void>*>(this)->BlockStmt_Visit(S);
+  }
+  
+  void BlockStmt_Visit(Stmt* S, dataflow::backward_analysis_tag) {
+    // Process statements in a preorder traversal of the AST.
+    static_cast<ImplClass*>(this)->ObserveBlockStmt(S);
+    static_cast<CFGStmtVisitor<ImplClass,void>*>(this)->BlockStmt_Visit(S);
+    
+    if (!CFG::hasImplicitControlFlow(S) &&
+        S->getStmtClass() != Stmt::CallExprClass)
+      static_cast<ImplClass*>(this)->VisitChildren(S);
+  }
+  
+  void Visit(Stmt* S) { Visit(S,AnalysisTag()); }
+  
+  void Visit(Stmt* S, dataflow::forward_analysis_tag) {
+    if (CFG::hasImplicitControlFlow(S))
+      return;
+      
+    // Process statements in a postorder traversal of the AST.
+    static_cast<ImplClass*>(this)->VisitChildren(S);
+    static_cast<ImplClass*>(this)->ObserveStmt(S);
+    static_cast<CFGStmtVisitor<ImplClass,void>*>(this)->Visit(S);
+  }
+  
+  void Visit(Stmt* S, dataflow::backward_analysis_tag) {
+    if (CFG::hasImplicitControlFlow(S))
+      return;
+      
+    // Process statements in a preorder traversal of the AST.
+    static_cast<ImplClass*>(this)->ObserveStmt(S);
+    static_cast<CFGStmtVisitor<ImplClass,void>*>(this)->Visit(S);
+    static_cast<ImplClass*>(this)->VisitChildren(S);
+  }    
+  
+  //===--------------------------------------------------------------------===//
+  // Methods for visiting entire CFGBlocks.
+  //===--------------------------------------------------------------------===//
+  
+  void VisitBlockEntry(const CFGBlock* B) {}
+  void VisitBlockExit(const CFGBlock* B) {}
+  
+  void VisitBlock(const CFGBlock* B) { VisitBlock(B,AnalysisTag()); }
+  
+  void VisitBlock(const CFGBlock* B, dataflow::forward_analysis_tag ) {
+    static_cast<ImplClass*>(this)->VisitBlockEntry(B);
+    
+    for (CFGBlock::const_iterator I=B->begin(), E=B->end(); I!=E; ++I)
+      static_cast<ImplClass*>(this)->BlockStmt_Visit(const_cast<Stmt*>(*I));
+    
+    static_cast<ImplClass*>(this)->VisitBlockExit(B);
+  }
+  
+  void VisitBlock(const CFGBlock* B, dataflow::backward_analysis_tag ) {
+    static_cast<ImplClass*>(this)->VisitBlockExit(B);
+        
+    for (CFGBlock::const_reverse_iterator I=B->rbegin(), E=B->rend(); I!=E; ++I)
+      static_cast<ImplClass*>(this)->BlockStmt_Visit(const_cast<Stmt*>(*I));
+   
+    static_cast<ImplClass*>(this)->VisitBlockEntry(B);
+  }
+  
+};  
+
+}  // end namespace clang
+
+#endif