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
24namespace clang {
25
26//===----------------------------------------------------------------------===//
27/// DataflowWorkListTy - Data structure representing the worklist used for
28///  dataflow algorithms.
29//===----------------------------------------------------------------------===//
30
31class DataflowWorkListTy {
32  llvm::DenseMap<const CFGBlock*, unsigned char> BlockSet;
33  SmallVector<const CFGBlock *, 10> BlockQueue;
34public:
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
64namespace dataflow {
65template<typename Tag> struct ItrTraits {};
66
67template <> 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
90template <> 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
118template <typename _DFValuesTy,      // Usually a subclass of DataflowValues
119          typename _TransferFuncsTy,
120          typename _MergeOperatorTy,
121          typename _Equal = std::equal_to<typename _DFValuesTy::ValTy> >
122class DataflowSolver {
123
124  //===----------------------------------------------------===//
125  // Type declarations.
126  //===----------------------------------------------------===//
127
128public:
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
147public:
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
194private:
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
336private:
337  DFValuesTy& D;
338  DataflowWorkListTy WorkList;
339  TransferFuncsTy TF;
340};
341
342} // end namespace clang
343#endif
344