| //===--- DataflowSolver.h - Skeleton Dataflow Analysis Code -----*- C++ -*-===// |
| // |
| // The LLVM Compiler Infrastructure |
| // |
| // This file was developed by Ted Kremenek and is distributed under |
| // the University of Illinois Open Source License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file defines skeleton code for implementing dataflow analyses. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef LLVM_CLANG_ANALYSES_DATAFLOW_SOLVER |
| #define LLVM_CLANG_ANALYSES_DATAFLOW_SOLVER |
| |
| #include "clang/AST/CFG.h" |
| #include "llvm/ADT/SmallPtrSet.h" |
| |
| namespace clang { |
| |
| //===----------------------------------------------------------------------===// |
| /// DataflowWorkListTy - Data structure representing the worklist used for |
| /// dataflow algorithms. |
| |
| class DataflowWorkListTy { |
| typedef llvm::SmallPtrSet<const CFGBlock*,20> BlockSet; |
| BlockSet wlist; |
| public: |
| /// enqueue - Add a block to the worklist. Blocks already on the worklist |
| /// are not added a second time. |
| void enqueue(const CFGBlock* B) { wlist.insert(B); } |
| |
| /// dequeue - Remove a block from the worklist. |
| const CFGBlock* dequeue() { |
| assert (!wlist.empty()); |
| const CFGBlock* B = *wlist.begin(); |
| wlist.erase(B); |
| return B; |
| } |
| |
| /// isEmpty - Return true if the worklist is empty. |
| bool isEmpty() const { return wlist.empty(); } |
| }; |
| |
| //===----------------------------------------------------------------------===// |
| /// DataflowSolverTy - Generic dataflow solver. |
| template <typename _DFValuesTy, // Usually a subclass of DataflowValues |
| typename _TransferFuncsTy, |
| typename _MergeOperatorTy > |
| class DataflowSolver { |
| |
| //===--------------------------------------------------------------------===// |
| // Type declarations. |
| //===--------------------------------------------------------------------===// |
| |
| public: |
| typedef _DFValuesTy DFValuesTy; |
| typedef _TransferFuncsTy TransferFuncsTy; |
| typedef _MergeOperatorTy MergeOperatorTy; |
| |
| typedef typename _DFValuesTy::AnalysisDirTag AnalysisDirTag; |
| typedef typename _DFValuesTy::ValTy ValTy; |
| typedef typename _DFValuesTy::BlockDataMapTy BlockDataMapTy; |
| |
| //===--------------------------------------------------------------------===// |
| // External interface: constructing and running the solver. |
| //===--------------------------------------------------------------------===// |
| |
| public: |
| DataflowSolver(DFValuesTy& d) : D(d) {} |
| ~DataflowSolver() {} |
| |
| /// runOnCFG - Computes dataflow values for all blocks in a CFG. |
| void runOnCFG(const CFG& cfg) { |
| // Set initial dataflow values and boundary conditions. |
| D.InitializeValues(cfg); |
| // Tag dispatch to the kind of analysis we do: forward or backwards. |
| SolveDataflowEquations(cfg,typename _DFValuesTy::AnalysisDirTag()); |
| } |
| |
| /// runOnBlock - Computes dataflow values for a given block. |
| /// This should usually be invoked only after previously computing |
| /// dataflow values using runOnCFG, as runOnBlock is intended to |
| /// only be used for querying the dataflow values within a block with |
| /// and Observer object. |
| void runOnBlock(const CFGBlock* B) { |
| if (D.getBlockDataMap().find(B) == D.getBlockDataMap().end()) |
| return; |
| |
| TransferFuncsTy TF (D.getAnalysisData()); |
| ProcessBlock(B,TF,AnalysisDirTag()); |
| } |
| |
| //===--------------------------------------------------------------------===// |
| // Internal solver logic. |
| //===--------------------------------------------------------------------===// |
| |
| private: |
| |
| /// SolveDataflowEquations (FORWARD ANALYSIS) - Perform the actual |
| /// worklist algorithm to compute dataflow values. |
| void SolveDataflowEquations(const CFG& cfg, dataflow::forward_analysis_tag) { |
| // Create the worklist. |
| DataflowWorkListTy WorkList; |
| |
| // Enqueue the ENTRY block. |
| WorkList.enqueue(&cfg.getEntry()); |
| |
| // Create the state for transfer functions. |
| TransferFuncsTy TF(D.getAnalysisData()); |
| |
| // Process the worklist until it is empty. |
| while (!WorkList.isEmpty()) { |
| const CFGBlock* B = WorkList.dequeue(); |
| // If the dataflow values at the block's exit have changed, |
| // enqueue all successor blocks onto the worklist to have |
| // their values updated. |
| if (ProcessBlock(B,TF,AnalysisDirTag())) |
| for (CFGBlock::const_succ_iterator I=B->succ_begin(), E=B->succ_end(); |
| I != E; ++I) |
| WorkList.enqueue(*I); |
| } |
| } |
| |
| /// SolveDataflowEquations (BACKWARD ANALYSIS) - Perform the actual |
| /// worklist algorithm to compute dataflow values. |
| void SolveDataflowEquations(const CFG& cfg, dataflow::backward_analysis_tag) { |
| // Create the worklist. |
| DataflowWorkListTy WorkList; |
| |
| // Enqueue the EXIT block. |
| WorkList.enqueue(&cfg.getExit()); |
| |
| // Create the state for transfer functions. |
| TransferFuncsTy TF(D.getAnalysisData()); |
| |
| // Process the worklist until it is empty. |
| while (!WorkList.isEmpty()) { |
| const CFGBlock* B = WorkList.dequeue(); |
| // If the dataflow values at the block's entry have changed, |
| // enqueue all predecessor blocks onto the worklist to have |
| // their values updated. |
| if (ProcessBlock(B,TF,AnalysisDirTag())) |
| for (CFGBlock::const_pred_iterator I=B->pred_begin(), E=B->pred_end(); |
| I != E; ++I) |
| WorkList.enqueue(*I); |
| } |
| } |
| |
| /// ProcessBlock (FORWARD ANALYSIS) - Process the transfer functions |
| /// for a given block based on a forward analysis. |
| bool ProcessBlock(const CFGBlock* B, TransferFuncsTy& TF, |
| dataflow::forward_analysis_tag) { |
| |
| ValTy& V = TF.getVal(); |
| |
| // Merge dataflow values from all predecessors of this block. |
| V.resetValues(D.getAnalysisData()); |
| MergeOperatorTy Merge; |
| |
| BlockDataMapTy& M = D.getBlockDataMap(); |
| bool firstMerge = true; |
| |
| for (CFGBlock::const_pred_iterator I=B->pred_begin(), |
| E=B->pred_end(); I!=E; ++I) { |
| typename BlockDataMapTy::iterator BI = M.find(*I); |
| if (BI != M.end()) { |
| if (firstMerge) { |
| firstMerge = false; |
| V.copyValues(BI->second); |
| } |
| else |
| Merge(V,BI->second); |
| } |
| } |
| |
| // Process the statements in the block in the forward direction. |
| for (CFGBlock::const_iterator I=B->begin(), E=B->end(); I!=E; ++I) |
| TF.BlockStmt_Visit(const_cast<Stmt*>(*I)); |
| |
| return UpdateBlockValue(B,V); |
| } |
| |
| /// ProcessBlock (BACKWARD ANALYSIS) - Process the transfer functions |
| /// for a given block based on a forward analysis. |
| bool ProcessBlock(const CFGBlock* B, TransferFuncsTy& TF, |
| dataflow::backward_analysis_tag) { |
| |
| ValTy& V = TF.getVal(); |
| |
| // Merge dataflow values from all predecessors of this block. |
| V.resetValues(D.getAnalysisData()); |
| MergeOperatorTy Merge; |
| |
| BlockDataMapTy& M = D.getBlockDataMap(); |
| bool firstMerge = true; |
| |
| for (CFGBlock::const_succ_iterator I=B->succ_begin(), |
| E=B->succ_end(); I!=E; ++I) { |
| typename BlockDataMapTy::iterator BI = M.find(*I); |
| if (BI != M.end()) { |
| if (firstMerge) { |
| firstMerge = false; |
| V.copyValues(BI->second); |
| } |
| else |
| Merge(V,BI->second); |
| } |
| } |
| |
| // Process the statements in the block in the forward direction. |
| for (CFGBlock::const_reverse_iterator I=B->begin(), E=B->end(); I!=E; ++I) |
| TF.BlockStmt_Visit(const_cast<Stmt*>(*I)); |
| |
| return UpdateBlockValue(B,V); |
| } |
| |
| /// UpdateBlockValue - After processing the transfer functions for a block, |
| /// update the dataflow value associated with the block. Return true |
| /// if the block's value has changed. We do lazy instantiation of block |
| /// values, so if the block value has not been previously computed we |
| /// obviously return true. |
| bool UpdateBlockValue(const CFGBlock* B, ValTy& V) { |
| BlockDataMapTy& M = D.getBlockDataMap(); |
| typename BlockDataMapTy::iterator I = M.find(B); |
| |
| if (I == M.end()) { |
| M[B].copyValues(V); |
| return true; |
| } |
| else if (!V.equal(I->second)) { |
| I->second.copyValues(V); |
| return true; |
| } |
| |
| return false; |
| } |
| |
| private: |
| DFValuesTy& D; |
| }; |
| |
| |
| } // end namespace clang |
| #endif |