1 //===--- DataflowSolver.h - Skeleton Dataflow Analysis Code -----*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines skeleton code for implementing dataflow analyses.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_CLANG_ANALYSES_DATAFLOW_SOLVER
15 #define LLVM_CLANG_ANALYSES_DATAFLOW_SOLVER
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"
26 //===----------------------------------------------------------------------===//
27 /// DataflowWorkListTy - Data structure representing the worklist used for
28 /// dataflow algorithms.
29 //===----------------------------------------------------------------------===//
31 class DataflowWorkListTy {
32 llvm::DenseMap<const CFGBlock*, unsigned char> BlockSet;
33 SmallVector<const CFGBlock *, 10> BlockQueue;
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];
42 BlockQueue.push_back(B);
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();
54 /// isEmpty - Return true if the worklist is empty.
55 bool isEmpty() const { return BlockQueue.empty(); }
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 //===----------------------------------------------------------------------===//
65 template<typename Tag> struct ItrTraits {};
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;
72 static PrevBItr PrevBegin(const CFGBlock *B) { return B->pred_begin(); }
73 static PrevBItr PrevEnd(const CFGBlock *B) { return B->pred_end(); }
75 static NextBItr NextBegin(const CFGBlock *B) { return B->succ_begin(); }
76 static NextBItr NextEnd(const CFGBlock *B) { return B->succ_end(); }
78 static StmtItr StmtBegin(const CFGBlock *B) { return B->begin(); }
79 static StmtItr StmtEnd(const CFGBlock *B) { return B->end(); }
81 static BlockEdge PrevEdge(const CFGBlock *B, const CFGBlock *Prev) {
82 return BlockEdge(Prev, B, 0);
85 static BlockEdge NextEdge(const CFGBlock *B, const CFGBlock *Next) {
86 return BlockEdge(B, Next, 0);
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;
95 static PrevBItr PrevBegin(const CFGBlock *B) { return B->succ_begin(); }
96 static PrevBItr PrevEnd(const CFGBlock *B) { return B->succ_end(); }
98 static NextBItr NextBegin(const CFGBlock *B) { return B->pred_begin(); }
99 static NextBItr NextEnd(const CFGBlock *B) { return B->pred_end(); }
101 static StmtItr StmtBegin(const CFGBlock *B) { return B->rbegin(); }
102 static StmtItr StmtEnd(const CFGBlock *B) { return B->rend(); }
104 static BlockEdge PrevEdge(const CFGBlock *B, const CFGBlock *Prev) {
105 return BlockEdge(B, Prev, 0);
108 static BlockEdge NextEdge(const CFGBlock *B, const CFGBlock *Next) {
109 return BlockEdge(Next, B, 0);
112 } // end namespace dataflow
114 //===----------------------------------------------------------------------===//
115 /// DataflowSolverTy - Generic dataflow solver.
116 //===----------------------------------------------------------------------===//
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 {
124 //===----------------------------------------------------===//
125 // Type declarations.
126 //===----------------------------------------------------===//
129 typedef _DFValuesTy DFValuesTy;
130 typedef _TransferFuncsTy TransferFuncsTy;
131 typedef _MergeOperatorTy MergeOperatorTy;
133 typedef typename _DFValuesTy::AnalysisDirTag AnalysisDirTag;
134 typedef typename _DFValuesTy::ValTy ValTy;
135 typedef typename _DFValuesTy::EdgeDataMapTy EdgeDataMapTy;
136 typedef typename _DFValuesTy::BlockDataMapTy BlockDataMapTy;
138 typedef dataflow::ItrTraits<AnalysisDirTag> ItrTraits;
139 typedef typename ItrTraits::NextBItr NextBItr;
140 typedef typename ItrTraits::PrevBItr PrevBItr;
141 typedef typename ItrTraits::StmtItr StmtItr;
143 //===----------------------------------------------------===//
144 // External interface: constructing and running the solver.
145 //===----------------------------------------------------===//
148 DataflowSolver(DFValuesTy& d) : D(d), TF(d.getAnalysisData()) {}
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);
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);
170 TF.getVal().copyValues(I->second);
171 ProcessBlock(B, recordStmtValues, AnalysisDirTag());
175 void runOnBlock(const CFGBlock &B, bool recordStmtValues) {
176 runOnBlock(&B, recordStmtValues);
178 void runOnBlock(CFG::iterator &I, bool recordStmtValues) {
179 runOnBlock(*I, recordStmtValues);
181 void runOnBlock(CFG::const_iterator &I, bool recordStmtValues) {
182 runOnBlock(*I, recordStmtValues);
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);
190 //===----------------------------------------------------===//
191 // Internal solver logic.
192 //===----------------------------------------------------===//
196 /// SolveDataflowEquations - Perform the actual worklist algorithm
197 /// to compute dataflow values.
198 void SolveDataflowEquations(CFG& cfg, bool recordStmtValues) {
199 EnqueueBlocksOnWorklist(cfg, AnalysisDirTag());
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());
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);
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);
225 void ProcessMerge(CFG& cfg, const CFGBlock *B) {
226 ValTy& V = TF.getVal();
229 // Merge dataflow values from all predecessors of this block.
230 MergeOperatorTy Merge;
232 EdgeDataMapTy& M = D.getEdgeDataMap();
233 bool firstMerge = true;
235 for (PrevBItr I=ItrTraits::PrevBegin(B),E=ItrTraits::PrevEnd(B); I!=E; ++I){
237 CFGBlock *PrevBlk = *I;
242 typename EdgeDataMapTy::iterator EI =
243 M.find(ItrTraits::PrevEdge(B, PrevBlk));
249 V.copyValues(EI->second);
252 Merge(V, EI->second);
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;
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);
268 // Set the data for the block.
269 BI->second.copyValues(V);
272 /// ProcessBlock - Process the transfer functions for a given block.
273 void ProcessBlock(const CFGBlock *B, bool recordStmtValues,
274 dataflow::forward_analysis_tag) {
276 TF.setCurrentBlock(B);
278 for (StmtItr I=ItrTraits::StmtBegin(B), E=ItrTraits::StmtEnd(B); I!=E;++I) {
280 if (const CFGStmt *S = El.getAs<CFGStmt>())
281 ProcessStmt(S->getStmt(), recordStmtValues, AnalysisDirTag());
284 TF.VisitTerminator(const_cast<CFGBlock*>(B));
287 void ProcessBlock(const CFGBlock *B, bool recordStmtValues,
288 dataflow::backward_analysis_tag) {
290 TF.setCurrentBlock(B);
292 TF.VisitTerminator(const_cast<CFGBlock*>(B));
294 for (StmtItr I=ItrTraits::StmtBegin(B), E=ItrTraits::StmtEnd(B); I!=E;++I) {
296 if (const CFGStmt *S = El.getAs<CFGStmt>())
297 ProcessStmt(S->getStmt(), recordStmtValues, AnalysisDirTag());
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));
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();
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);
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);
326 if (I == M.end()) { // First computed value for this edge?
328 WorkList.enqueue(TargetBlock);
330 else if (!_Equal()(V,I->second)) {
331 I->second.copyValues(V);
332 WorkList.enqueue(TargetBlock);
338 DataflowWorkListTy WorkList;
342 } // end namespace clang