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