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 "clang/Analysis/CFG.h" 18 #include "clang/Analysis/ProgramPoint.h" 19 #include "clang/Analysis/FlowSensitive/DataflowValues.h" 20 #include "llvm/ADT/DenseMap.h" 21 #include "llvm/ADT/SmallVector.h" 22 #include "functional" // STL 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 344