Prototype implementation of new template-based dataflow solver.

Preliminary implementation of UninitializedValues, which is based on
new solver (doesn't work yet, but compiles).

llvm-svn: 41970

1 files changed, 221 insertions, 0 deletions

diff --git a/clang/Analysis/DataflowSolver.h b/clang/Analysis/DataflowSolver.h
new file mode 100644
index 00000000000..e2150004bb9
--- /dev/null
+++ b/clang/Analysis/DataflowSolver.h
@@ -0,0 +1,221 @@
+//===--- DataflowSolver.h - Skeleton Dataflow Analysis Code -----*- 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 skeleton code for implementing dataflow analyses.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSES_DATAFLOW_SOLVER
+#define LLVM_CLANG_ANALYSES_DATAFLOW_SOLVER
+
+#include "clang/AST/CFG.h"
+#include "llvm/ADT/SmallPtrSet.h"
+
+namespace clang {
+
+//===----------------------------------------------------------------------===//
+/// DataflowWorkListTy - Data structure representing the worklist used for
+///  dataflow algorithms.
+
+class DataflowWorkListTy {
+  typedef llvm::SmallPtrSet<const CFGBlock*,20> BlockSet;
+  BlockSet wlist;
+public:
+  /// enqueue - Add a block to the worklist.  Blocks already on the worklist
+  ///  are not added a second time.  
+  void enqueue(const CFGBlock* B) { wlist.insert(B); }
+  
+  /// dequeue - Remove a block from the worklist.
+  const CFGBlock* dequeue() {
+    assert (!wlist.empty());
+    const CFGBlock* B = *wlist.begin();
+    wlist.erase(B);
+    return B;          
+  }
+  
+  /// isEmpty - Return true if the worklist is empty.
+  bool isEmpty() const { return wlist.empty(); }
+};
+
+//===----------------------------------------------------------------------===//
+/// DataflowSolverTy - Generic dataflow solver.
+template <typename _DFValuesTy,      // Usually a subclass of DataflowValues
+          typename _TransferFuncsTy,
+          typename _MergeOperatorTy >
+class DataflowSolver {
+
+  //===--------------------------------------------------------------------===//
+  // Type declarations.
+  //===--------------------------------------------------------------------===//
+
+public:
+  typedef _DFValuesTy                            DFValuesTy;
+  typedef _TransferFuncsTy                       TransferFuncsTy;
+  typedef _MergeOperatorTy                       MergeOperatorTy;
+
+  typedef typename _DFValuesTy::AnalysisDirTag   AnalysisDirTag;
+  typedef typename _DFValuesTy::ValTy            ValTy;
+  typedef typename _DFValuesTy::BlockDataMapTy   BlockDataMapTy;
+  typedef typename _DFValuesTy::ObserverTy       ObserverTy;
+
+  //===--------------------------------------------------------------------===//
+  // External interface: constructing and running the solver.
+  //===--------------------------------------------------------------------===//
+  
+public:
+  DataflowSolver(DFValuesTy& d, ObserverTy* o = NULL) : D(d), O(o) {}
+  ~DataflowSolver() {}  
+  
+  /// runOnCFG - Computes dataflow values for all blocks in a CFG.
+  void runOnCFG(const CFG& cfg) {
+    // Set initial dataflow values and boundary conditions.
+    D.InitializeValues(cfg);     
+    // Tag dispatch to the kind of analysis we do: forward or backwards.
+    SolveDataflowEquations(cfg,typename _DFValuesTy::AnalysisDirTag());    
+  }
+  
+  /// runOnBlock - Computes dataflow values for a given block.
+  ///  This should usually be invoked only after previously computing
+  ///  dataflow values using runOnCFG, as runOnBlock is intended to
+  ///  only be used for querying the dataflow values within a block with
+  ///  and Observer object.
+  void runOnBlock(const CFGBlock* B) {
+    TransferFuncsTy TF (D.getMetaData(),O);
+    ProcessBlock(B,TF,AnalysisDirTag());
+  }
+  
+  //===--------------------------------------------------------------------===//
+  // Internal solver logic.
+  //===--------------------------------------------------------------------===//
+  
+private:
+ 
+  /// SolveDataflowEquations (FORWARD ANALYSIS) - Perform the actual
+  ///  worklist algorithm to compute dataflow values.
+  void SolveDataflowEquations(const CFG& cfg, dataflow::forward_analysis_tag) {
+    // Create the worklist.
+    DataflowWorkListTy WorkList;
+    
+    // Enqueue the ENTRY block.
+    WorkList.enqueue(&cfg.getEntry());
+    
+    // Create the state for transfer functions.
+    TransferFuncsTy TF(D.getMetaData(),O);
+    
+    // Process the worklist until it is empty.    
+    while (!WorkList.isEmpty()) {
+      const CFGBlock* B = WorkList.dequeue();
+      // If the dataflow values at the block's exit have changed,
+      // enqueue all successor blocks onto the worklist to have
+      // their values updated.
+      if (ProcessBlock(B,TF,AnalysisDirTag()))
+        for (CFGBlock::const_succ_iterator I=B->succ_begin(), E=B->succ_end();
+             I != E; ++I)
+          WorkList.enqueue(*I);    
+    }                     
+  }       
+  
+  /// SolveDataflowEquations (BACKWARD ANALYSIS) - Perform the actual
+  ///  worklist algorithm to compute dataflow values.  
+  void SolveDataflowEquations(const CFG& cfg, dataflow::backward_analysis_tag) {
+    // Create the worklist.
+    DataflowWorkListTy WorkList;
+    
+    // Enqueue the EXIT block.
+    WorkList.enqueue(&cfg.getExit());
+    
+    // Create the state for transfer functions.
+    TransferFuncsTy TF(D.getMetaData(),O);
+    
+    // Process the worklist until it is empty.    
+    while (!WorkList.isEmpty()) {
+      const CFGBlock* B = WorkList.dequeue();
+      // If the dataflow values at the block's entry have changed,
+      // enqueue all predecessor blocks onto the worklist to have
+      // their values updated.
+      if (ProcessBlock(B,TF,AnalysisDirTag()))
+        for (CFGBlock::const_pred_iterator I=B->pred_begin(), E=B->pred_end();
+             I != E; ++I)
+          WorkList.enqueue(*I);    
+    }
+  }
+  
+  /// ProcessBlock (FORWARD ANALYSIS) - Process the transfer functions
+  ///  for a given block based on a forward analysis.
+  bool ProcessBlock(const CFGBlock* B, TransferFuncsTy& TF, 
+                    dataflow::forward_analysis_tag) {
+    
+    ValTy& V = TF.getVal();
+
+    // Merge dataflow values from all predecessors of this block.
+    V.resetValues();
+    MergeOperatorTy Merge;
+  
+    for (CFGBlock::const_pred_iterator I=B->pred_begin(), 
+                                       E=B->pred_end(); I!=E; ++I)
+      Merge(V,D.getBlockData(*I));
+
+    // Process the statements in the block in the forward direction.
+    for (CFGBlock::const_iterator I=B->begin(), E=B->end(); I!=E; ++I)
+      TF.BlockStmt_Visit(const_cast<Stmt*>(*I));
+      
+    return UpdateBlockValue(B,V);
+  }
+  
+  /// ProcessBlock (BACKWARD ANALYSIS) - Process the transfer functions
+  ///  for a given block based on a forward analysis.
+  bool ProcessBlock(const CFGBlock* B, TransferFuncsTy& TF,
+                    dataflow::backward_analysis_tag) {
+    
+    ValTy& V = TF.getVal();
+    
+    // Merge dataflow values from all predecessors of this block.
+    V.resetValues();
+    MergeOperatorTy Merge;
+    
+    for (CFGBlock::const_succ_iterator I=B->succ_begin(), 
+                                       E=B->succ_end(); I!=E; ++I)
+      Merge(V,D.getBlockData(*I));
+    
+    // Process the statements in the block in the forward direction.
+    for (CFGBlock::const_reverse_iterator I=B->begin(), E=B->end(); I!=E; ++I)
+      TF.BlockStmt_Visit(const_cast<Stmt*>(*I));
+    
+    return UpdateBlockValue(B,V);                        
+  }
+  
+  /// UpdateBlockValue - After processing the transfer functions for a block,
+  ///  update the dataflow value associated with the block.  Return true
+  ///  if the block's value has changed.  We do lazy instantiation of block
+  ///  values, so if the block value has not been previously computed we
+  ///  obviously return true.
+  bool UpdateBlockValue(const CFGBlock* B, ValTy& V) {
+    BlockDataMapTy& M = D.getBlockDataMap();
+    typename BlockDataMapTy::iterator I = M.find(B);
+    
+    if (I == M.end()) {
+      M[B].copyValues(V);
+      return true;
+    }
+    else if (!V.equal(I->second)) {
+      I->second.copyValues(V);
+      return true;
+    }
+    
+    return false;
+  }
+
+private:
+  DFValuesTy& D;
+  ObserverTy* O;
+};  
+  
+
+} // end namespace clang
+#endif