contrib/llvm/tools/clang/include/clang/Analysis/FlowSensitive/DataflowSolver.h

   1 //===--- DataflowSolver.h - Skeleton Dataflow Analysis Code -----*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines skeleton code for implementing dataflow analyses.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_CLANG_ANALYSES_DATAFLOW_SOLVER
  15 #define LLVM_CLANG_ANALYSES_DATAFLOW_SOLVER
  16
  17 #include "functional" // STL
  18 #include "clang/Analysis/CFG.h"
  19 #include "clang/Analysis/FlowSensitive/DataflowValues.h"
  20 #include "clang/Analysis/ProgramPoint.h"
  21 #include "llvm/ADT/DenseMap.h"
  22 #include "llvm/ADT/SmallVector.h"
  23
  24 namespace clang {
  25
  26 //===----------------------------------------------------------------------===//
  27 /// DataflowWorkListTy - Data structure representing the worklist used for
  28 ///  dataflow algorithms.
  29 //===----------------------------------------------------------------------===//
  30
  31 class DataflowWorkListTy {
  32   llvm::DenseMap<const CFGBlock*, unsigned char> BlockSet;
  33   SmallVector<const CFGBlock *, 10> BlockQueue;
  34 public:
  35   /// enqueue - Add a block to the worklist.  Blocks already on the
  36   ///  worklist are not added a second time.
  37   void enqueue(const CFGBlock *B) {
  38     unsigned char &x = BlockSet[B];
  39     if (x == 1)
  40       return;
  41     x = 1;
  42     BlockQueue.push_back(B);
  43   }
  44
  45   /// dequeue - Remove a block from the worklist.
  46   const CFGBlock *dequeue() {
  47     assert(!BlockQueue.empty());
  48     const CFGBlock *B = BlockQueue.back();
  49     BlockQueue.pop_back();
  50     BlockSet[B] = 0;
  51     return B;
  52   }
  53
  54   /// isEmpty - Return true if the worklist is empty.
  55   bool isEmpty() const { return BlockQueue.empty(); }
  56 };
  57
  58 //===----------------------------------------------------------------------===//
  59 // BlockItrTraits - Traits classes that allow transparent iteration
  60 //  over successors/predecessors of a block depending on the direction
  61 //  of our dataflow analysis.
  62 //===----------------------------------------------------------------------===//
  63
  64 namespace dataflow {
  65 template<typename Tag> struct ItrTraits {};
  66
  67 template <> struct ItrTraits<forward_analysis_tag> {
  68   typedef CFGBlock::const_pred_iterator PrevBItr;
  69   typedef CFGBlock::const_succ_iterator NextBItr;
  70   typedef CFGBlock::const_iterator      StmtItr;
  71
  72   static PrevBItr PrevBegin(const CFGBlock *B) { return B->pred_begin(); }
  73   static PrevBItr PrevEnd(const CFGBlock *B) { return B->pred_end(); }
  74
  75   static NextBItr NextBegin(const CFGBlock *B) { return B->succ_begin(); }
  76   static NextBItr NextEnd(const CFGBlock *B) { return B->succ_end(); }
  77
  78   static StmtItr StmtBegin(const CFGBlock *B) { return B->begin(); }
  79   static StmtItr StmtEnd(const CFGBlock *B) { return B->end(); }
  80
  81   static BlockEdge PrevEdge(const CFGBlock *B, const CFGBlock *Prev) {
  82     return BlockEdge(Prev, B, 0);
  83   }
  84
  85   static BlockEdge NextEdge(const CFGBlock *B, const CFGBlock *Next) {
  86     return BlockEdge(B, Next, 0);
  87   }
  88 };
  89
  90 template <> struct ItrTraits<backward_analysis_tag> {
  91   typedef CFGBlock::const_succ_iterator    PrevBItr;
  92   typedef CFGBlock::const_pred_iterator    NextBItr;
  93   typedef CFGBlock::const_reverse_iterator StmtItr;
  94
  95   static PrevBItr PrevBegin(const CFGBlock *B) { return B->succ_begin(); }
  96   static PrevBItr PrevEnd(const CFGBlock *B) { return B->succ_end(); }
  97
  98   static NextBItr NextBegin(const CFGBlock *B) { return B->pred_begin(); }
  99   static NextBItr NextEnd(const CFGBlock *B) { return B->pred_end(); }
 100
 101   static StmtItr StmtBegin(const CFGBlock *B) { return B->rbegin(); }
 102   static StmtItr StmtEnd(const CFGBlock *B) { return B->rend(); }
 103
 104   static BlockEdge PrevEdge(const CFGBlock *B, const CFGBlock *Prev) {
 105     return BlockEdge(B, Prev, 0);
 106   }
 107
 108   static BlockEdge NextEdge(const CFGBlock *B, const CFGBlock *Next) {
 109     return BlockEdge(Next, B, 0);
 110   }
 111 };
 112 } // end namespace dataflow
 113
 114 //===----------------------------------------------------------------------===//
 115 /// DataflowSolverTy - Generic dataflow solver.
 116 //===----------------------------------------------------------------------===//
 117
 118 template <typename _DFValuesTy,      // Usually a subclass of DataflowValues
 119           typename _TransferFuncsTy,
 120           typename _MergeOperatorTy,
 121           typename _Equal = std::equal_to<typename _DFValuesTy::ValTy> >
 122 class DataflowSolver {
 123
 124   //===----------------------------------------------------===//
 125   // Type declarations.
 126   //===----------------------------------------------------===//
 127
 128 public:
 129   typedef _DFValuesTy                              DFValuesTy;
 130   typedef _TransferFuncsTy                         TransferFuncsTy;
 131   typedef _MergeOperatorTy                         MergeOperatorTy;
 132
 133   typedef typename _DFValuesTy::AnalysisDirTag     AnalysisDirTag;
 134   typedef typename _DFValuesTy::ValTy              ValTy;
 135   typedef typename _DFValuesTy::EdgeDataMapTy      EdgeDataMapTy;
 136   typedef typename _DFValuesTy::BlockDataMapTy     BlockDataMapTy;
 137
 138   typedef dataflow::ItrTraits<AnalysisDirTag>      ItrTraits;
 139   typedef typename ItrTraits::NextBItr             NextBItr;
 140   typedef typename ItrTraits::PrevBItr             PrevBItr;
 141   typedef typename ItrTraits::StmtItr              StmtItr;
 142
 143   //===----------------------------------------------------===//
 144   // External interface: constructing and running the solver.
 145   //===----------------------------------------------------===//
 146
 147 public:
 148   DataflowSolver(DFValuesTy& d) : D(d), TF(d.getAnalysisData()) {}
 149   ~DataflowSolver() {}
 150
 151   /// runOnCFG - Computes dataflow values for all blocks in a CFG.
 152   void runOnCFG(CFG& cfg, bool recordStmtValues = false) {
 153     // Set initial dataflow values and boundary conditions.
 154     D.InitializeValues(cfg);
 155     // Solve the dataflow equations.  This will populate D.EdgeDataMap
 156     // with dataflow values.
 157     SolveDataflowEquations(cfg, recordStmtValues);
 158   }
 159
 160   /// runOnBlock - Computes dataflow values for a given block.  This
 161   ///  should usually be invoked only after previously computing
 162   ///  dataflow values using runOnCFG, as runOnBlock is intended to
 163   ///  only be used for querying the dataflow values within a block
 164   ///  with and Observer object.
 165   void runOnBlock(const CFGBlock *B, bool recordStmtValues) {
 166     BlockDataMapTy& M = D.getBlockDataMap();
 167     typename BlockDataMapTy::iterator I = M.find(B);
 168
 169     if (I != M.end()) {
 170       TF.getVal().copyValues(I->second);
 171       ProcessBlock(B, recordStmtValues, AnalysisDirTag());
 172     }
 173   }
 174
 175   void runOnBlock(const CFGBlock &B, bool recordStmtValues) {
 176     runOnBlock(&B, recordStmtValues);
 177   }
 178   void runOnBlock(CFG::iterator &I, bool recordStmtValues) {
 179     runOnBlock(*I, recordStmtValues);
 180   }
 181   void runOnBlock(CFG::const_iterator &I, bool recordStmtValues) {
 182     runOnBlock(*I, recordStmtValues);
 183   }
 184
 185   void runOnAllBlocks(const CFG& cfg, bool recordStmtValues = false) {
 186     for (CFG::const_iterator I=cfg.begin(), E=cfg.end(); I!=E; ++I)
 187       runOnBlock(I, recordStmtValues);
 188   }
 189
 190   //===----------------------------------------------------===//
 191   // Internal solver logic.
 192   //===----------------------------------------------------===//
 193
 194 private:
 195
 196   /// SolveDataflowEquations - Perform the actual worklist algorithm
 197   ///  to compute dataflow values.
 198   void SolveDataflowEquations(CFG& cfg, bool recordStmtValues) {
 199     EnqueueBlocksOnWorklist(cfg, AnalysisDirTag());
 200
 201     while (!WorkList.isEmpty()) {
 202       const CFGBlock *B = WorkList.dequeue();
 203       ProcessMerge(cfg, B);
 204       ProcessBlock(B, recordStmtValues, AnalysisDirTag());
 205       UpdateEdges(cfg, B, TF.getVal());
 206     }
 207   }
 208
 209   void EnqueueBlocksOnWorklist(CFG &cfg, dataflow::forward_analysis_tag) {
 210     // Enqueue all blocks to ensure the dataflow values are computed
 211     // for every block.  Not all blocks are guaranteed to reach the exit block.
 212     for (CFG::iterator I=cfg.begin(), E=cfg.end(); I!=E; ++I)
 213       WorkList.enqueue(&**I);
 214   }
 215
 216   void EnqueueBlocksOnWorklist(CFG &cfg, dataflow::backward_analysis_tag) {
 217     // Enqueue all blocks to ensure the dataflow values are computed
 218     // for every block.  Not all blocks are guaranteed to reach the exit block.
 219     // Enqueue in reverse order since that will more likely match with
 220     // the order they should ideally processed by the dataflow algorithm.
 221     for (CFG::reverse_iterator I=cfg.rbegin(), E=cfg.rend(); I!=E; ++I)
 222       WorkList.enqueue(&**I);
 223   }
 224
 225   void ProcessMerge(CFG& cfg, const CFGBlock *B) {
 226     ValTy& V = TF.getVal();
 227     TF.SetTopValue(V);
 228
 229     // Merge dataflow values from all predecessors of this block.
 230     MergeOperatorTy Merge;
 231
 232     EdgeDataMapTy& M = D.getEdgeDataMap();
 233     bool firstMerge = true;
 234     bool noEdges = true;
 235     for (PrevBItr I=ItrTraits::PrevBegin(B),E=ItrTraits::PrevEnd(B); I!=E; ++I){
 236
 237       CFGBlock *PrevBlk = *I;
 238
 239       if (!PrevBlk)
 240         continue;
 241
 242       typename EdgeDataMapTy::iterator EI =
 243         M.find(ItrTraits::PrevEdge(B, PrevBlk));
 244
 245       if (EI != M.end()) {
 246         noEdges = false;
 247         if (firstMerge) {
 248           firstMerge = false;
 249           V.copyValues(EI->second);
 250         }
 251         else
 252           Merge(V, EI->second);
 253       }
 254     }
 255
 256     bool isInitialized = true;
 257     typename BlockDataMapTy::iterator BI = D.getBlockDataMap().find(B);
 258     if(BI == D.getBlockDataMap().end()) {
 259       isInitialized = false;
 260       BI = D.getBlockDataMap().insert( std::make_pair(B,ValTy()) ).first;
 261     }
 262     // If no edges have been found, it means this is the first time the solver
 263     // has been called on block B, we copy the initialization values (if any)
 264     // as current value for V (which will be used as edge data)
 265     if(noEdges && isInitialized)
 266       Merge(V, BI->second);
 267
 268     // Set the data for the block.
 269     BI->second.copyValues(V);
 270   }
 271
 272   /// ProcessBlock - Process the transfer functions for a given block.
 273   void ProcessBlock(const CFGBlock *B, bool recordStmtValues,
 274                     dataflow::forward_analysis_tag) {
 275
 276     TF.setCurrentBlock(B);
 277
 278     for (StmtItr I=ItrTraits::StmtBegin(B), E=ItrTraits::StmtEnd(B); I!=E;++I) {
 279       CFGElement El = *I;
 280       if (const CFGStmt *S = El.getAs<CFGStmt>())
 281         ProcessStmt(S->getStmt(), recordStmtValues, AnalysisDirTag());
 282     }
 283
 284     TF.VisitTerminator(const_cast<CFGBlock*>(B));
 285   }
 286
 287   void ProcessBlock(const CFGBlock *B, bool recordStmtValues,
 288                     dataflow::backward_analysis_tag) {
 289
 290     TF.setCurrentBlock(B);
 291
 292     TF.VisitTerminator(const_cast<CFGBlock*>(B));
 293
 294     for (StmtItr I=ItrTraits::StmtBegin(B), E=ItrTraits::StmtEnd(B); I!=E;++I) {
 295       CFGElement El = *I;
 296       if (const CFGStmt *S = El.getAs<CFGStmt>())
 297         ProcessStmt(S->getStmt(), recordStmtValues, AnalysisDirTag());
 298     }
 299   }
 300
 301   void ProcessStmt(const Stmt *S, bool record, dataflow::forward_analysis_tag) {
 302     if (record) D.getStmtDataMap()[S] = TF.getVal();
 303     TF.BlockStmt_Visit(const_cast<Stmt*>(S));
 304   }
 305
 306   void ProcessStmt(const Stmt *S, bool record, dataflow::backward_analysis_tag){
 307     TF.BlockStmt_Visit(const_cast<Stmt*>(S));
 308     if (record) D.getStmtDataMap()[S] = TF.getVal();
 309   }
 310
 311   /// UpdateEdges - After processing the transfer functions for a
 312   ///   block, update the dataflow value associated with the block's
 313   ///   outgoing/incoming edges (depending on whether we do a
 314   //    forward/backward analysis respectively)
 315   void UpdateEdges(CFG& cfg, const CFGBlock *B, ValTy& V) {
 316     for (NextBItr I=ItrTraits::NextBegin(B), E=ItrTraits::NextEnd(B); I!=E; ++I)
 317       if (CFGBlock *NextBlk = *I)
 318         UpdateEdgeValue(ItrTraits::NextEdge(B, NextBlk),V, NextBlk);
 319   }
 320
 321   /// UpdateEdgeValue - Update the value associated with a given edge.
 322   void UpdateEdgeValue(BlockEdge E, ValTy& V, const CFGBlock *TargetBlock) {
 323     EdgeDataMapTy& M = D.getEdgeDataMap();
 324     typename EdgeDataMapTy::iterator I = M.find(E);
 325
 326     if (I == M.end()) {  // First computed value for this edge?
 327       M[E].copyValues(V);
 328       WorkList.enqueue(TargetBlock);
 329     }
 330     else if (!_Equal()(V,I->second)) {
 331       I->second.copyValues(V);
 332       WorkList.enqueue(TargetBlock);
 333     }
 334   }
 335
 336 private:
 337   DFValuesTy& D;
 338   DataflowWorkListTy WorkList;
 339   TransferFuncsTy TF;
 340 };
 341
 342 } // end namespace clang
 343 #endif