diff options
Diffstat (limited to 'include/clang/Analysis/FlowSensitive')
| -rw-r--r-- | include/clang/Analysis/FlowSensitive/DataflowSolver.h | 291 | ||||
| -rw-r--r-- | include/clang/Analysis/FlowSensitive/DataflowValues.h | 172 |
2 files changed, 463 insertions, 0 deletions
diff --git a/include/clang/Analysis/FlowSensitive/DataflowSolver.h b/include/clang/Analysis/FlowSensitive/DataflowSolver.h new file mode 100644 index 0000000..3861259 --- /dev/null +++ b/include/clang/Analysis/FlowSensitive/DataflowSolver.h @@ -0,0 +1,291 @@ +//===--- DataflowSolver.h - Skeleton Dataflow Analysis Code -----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file 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 "clang/Analysis/ProgramPoint.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "functional" // STL + +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(); } +}; + +//===----------------------------------------------------------------------===// +// BlockItrTraits - Traits classes that allow transparent iteration +// over successors/predecessors of a block depending on the direction +// of our dataflow analysis. +//===----------------------------------------------------------------------===// + +namespace dataflow { +template<typename Tag> struct ItrTraits {}; + +template <> struct ItrTraits<forward_analysis_tag> { + typedef CFGBlock::const_pred_iterator PrevBItr; + typedef CFGBlock::const_succ_iterator NextBItr; + typedef CFGBlock::const_iterator StmtItr; + + static PrevBItr PrevBegin(const CFGBlock* B) { return B->pred_begin(); } + static PrevBItr PrevEnd(const CFGBlock* B) { return B->pred_end(); } + + static NextBItr NextBegin(const CFGBlock* B) { return B->succ_begin(); } + static NextBItr NextEnd(const CFGBlock* B) { return B->succ_end(); } + + static StmtItr StmtBegin(const CFGBlock* B) { return B->begin(); } + static StmtItr StmtEnd(const CFGBlock* B) { return B->end(); } + + static BlockEdge PrevEdge(const CFGBlock* B, const CFGBlock* Prev) { + return BlockEdge(Prev, B); + } + + static BlockEdge NextEdge(const CFGBlock* B, const CFGBlock* Next) { + return BlockEdge(B, Next); + } +}; + +template <> struct ItrTraits<backward_analysis_tag> { + typedef CFGBlock::const_succ_iterator PrevBItr; + typedef CFGBlock::const_pred_iterator NextBItr; + typedef CFGBlock::const_reverse_iterator StmtItr; + + static PrevBItr PrevBegin(const CFGBlock* B) { return B->succ_begin(); } + static PrevBItr PrevEnd(const CFGBlock* B) { return B->succ_end(); } + + static NextBItr NextBegin(const CFGBlock* B) { return B->pred_begin(); } + static NextBItr NextEnd(const CFGBlock* B) { return B->pred_end(); } + + static StmtItr StmtBegin(const CFGBlock* B) { return B->rbegin(); } + static StmtItr StmtEnd(const CFGBlock* B) { return B->rend(); } + + static BlockEdge PrevEdge(const CFGBlock* B, const CFGBlock* Prev) { + return BlockEdge(B, Prev); + } + + static BlockEdge NextEdge(const CFGBlock* B, const CFGBlock* Next) { + return BlockEdge(Next, B); + } +}; +} // end namespace dataflow + +//===----------------------------------------------------------------------===// +/// DataflowSolverTy - Generic dataflow solver. +//===----------------------------------------------------------------------===// + +template <typename _DFValuesTy, // Usually a subclass of DataflowValues + typename _TransferFuncsTy, + typename _MergeOperatorTy, + typename _Equal = std::equal_to<typename _DFValuesTy::ValTy> > +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::EdgeDataMapTy EdgeDataMapTy; + typedef typename _DFValuesTy::BlockDataMapTy BlockDataMapTy; + + typedef dataflow::ItrTraits<AnalysisDirTag> ItrTraits; + typedef typename ItrTraits::NextBItr NextBItr; + typedef typename ItrTraits::PrevBItr PrevBItr; + typedef typename ItrTraits::StmtItr StmtItr; + + //===----------------------------------------------------===// + // External interface: constructing and running the solver. + //===----------------------------------------------------===// + +public: + DataflowSolver(DFValuesTy& d) : D(d), TF(d.getAnalysisData()) {} + ~DataflowSolver() {} + + /// runOnCFG - Computes dataflow values for all blocks in a CFG. + void runOnCFG(CFG& cfg, bool recordStmtValues = false) { + // Set initial dataflow values and boundary conditions. + D.InitializeValues(cfg); + // Solve the dataflow equations. This will populate D.EdgeDataMap + // with dataflow values. + SolveDataflowEquations(cfg, recordStmtValues); + } + + /// 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, bool recordStmtValues) { + BlockDataMapTy& M = D.getBlockDataMap(); + typename BlockDataMapTy::iterator I = M.find(B); + + if (I != M.end()) { + TF.getVal().copyValues(I->second); + ProcessBlock(B, recordStmtValues, AnalysisDirTag()); + } + } + + void runOnBlock(const CFGBlock& B, bool recordStmtValues) { + runOnBlock(&B, recordStmtValues); + } + void runOnBlock(CFG::iterator& I, bool recordStmtValues) { + runOnBlock(*I, recordStmtValues); + } + void runOnBlock(CFG::const_iterator& I, bool recordStmtValues) { + runOnBlock(*I, recordStmtValues); + } + + void runOnAllBlocks(const CFG& cfg, bool recordStmtValues = false) { + for (CFG::const_iterator I=cfg.begin(), E=cfg.end(); I!=E; ++I) + runOnBlock(I, recordStmtValues); + } + + //===----------------------------------------------------===// + // Internal solver logic. + //===----------------------------------------------------===// + +private: + + /// SolveDataflowEquations - Perform the actual worklist algorithm + /// to compute dataflow values. + void SolveDataflowEquations(CFG& cfg, bool recordStmtValues) { + // Enqueue all blocks to ensure the dataflow values are computed + // for every block. Not all blocks are guaranteed to reach the exit block. + for (CFG::iterator I=cfg.begin(), E=cfg.end(); I!=E; ++I) + WorkList.enqueue(&*I); + + while (!WorkList.isEmpty()) { + const CFGBlock* B = WorkList.dequeue(); + ProcessMerge(cfg,B); + ProcessBlock(B, recordStmtValues, AnalysisDirTag()); + UpdateEdges(cfg,B,TF.getVal()); + } + } + + void ProcessMerge(CFG& cfg, const CFGBlock* B) { + ValTy& V = TF.getVal(); + TF.SetTopValue(V); + + // Merge dataflow values from all predecessors of this block. + MergeOperatorTy Merge; + + EdgeDataMapTy& M = D.getEdgeDataMap(); + bool firstMerge = true; + + for (PrevBItr I=ItrTraits::PrevBegin(B),E=ItrTraits::PrevEnd(B); I!=E; ++I){ + + typename EdgeDataMapTy::iterator EI = + M.find(ItrTraits::PrevEdge(B, *I)); + + if (EI != M.end()) { + if (firstMerge) { + firstMerge = false; + V.copyValues(EI->second); + } + else Merge(V,EI->second); + } + } + + // Set the data for the block. + D.getBlockDataMap()[B].copyValues(V); + } + + /// ProcessBlock - Process the transfer functions for a given block. + void ProcessBlock(const CFGBlock* B, bool recordStmtValues, + dataflow::forward_analysis_tag) { + + for (StmtItr I=ItrTraits::StmtBegin(B), E=ItrTraits::StmtEnd(B); I!=E;++I) + ProcessStmt(*I, recordStmtValues, AnalysisDirTag()); + + TF.VisitTerminator(const_cast<CFGBlock*>(B)); + } + + void ProcessBlock(const CFGBlock* B, bool recordStmtValues, + dataflow::backward_analysis_tag) { + + TF.VisitTerminator(const_cast<CFGBlock*>(B)); + + for (StmtItr I=ItrTraits::StmtBegin(B), E=ItrTraits::StmtEnd(B); I!=E;++I) + ProcessStmt(*I, recordStmtValues, AnalysisDirTag()); + } + + void ProcessStmt(const Stmt* S, bool record, dataflow::forward_analysis_tag) { + if (record) D.getStmtDataMap()[S] = TF.getVal(); + TF.BlockStmt_Visit(const_cast<Stmt*>(S)); + } + + void ProcessStmt(const Stmt* S, bool record, dataflow::backward_analysis_tag){ + TF.BlockStmt_Visit(const_cast<Stmt*>(S)); + if (record) D.getStmtDataMap()[S] = TF.getVal(); + } + + /// UpdateEdges - After processing the transfer functions for a + /// block, update the dataflow value associated with the block's + /// outgoing/incoming edges (depending on whether we do a + // forward/backward analysis respectively) + void UpdateEdges(CFG& cfg, const CFGBlock* B, ValTy& V) { + for (NextBItr I=ItrTraits::NextBegin(B), E=ItrTraits::NextEnd(B); I!=E; ++I) + UpdateEdgeValue(ItrTraits::NextEdge(B, *I),V,*I); + } + + /// UpdateEdgeValue - Update the value associated with a given edge. + void UpdateEdgeValue(BlockEdge E, ValTy& V, const CFGBlock* TargetBlock) { + EdgeDataMapTy& M = D.getEdgeDataMap(); + typename EdgeDataMapTy::iterator I = M.find(E); + + if (I == M.end()) { // First computed value for this edge? + M[E].copyValues(V); + WorkList.enqueue(TargetBlock); + } + else if (!_Equal()(V,I->second)) { + I->second.copyValues(V); + WorkList.enqueue(TargetBlock); + } + } + +private: + DFValuesTy& D; + DataflowWorkListTy WorkList; + TransferFuncsTy TF; +}; + +} // end namespace clang +#endif diff --git a/include/clang/Analysis/FlowSensitive/DataflowValues.h b/include/clang/Analysis/FlowSensitive/DataflowValues.h new file mode 100644 index 0000000..d6427a5 --- /dev/null +++ b/include/clang/Analysis/FlowSensitive/DataflowValues.h @@ -0,0 +1,172 @@ +//===--- DataflowValues.h - Data structure for dataflow values --*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines a skeleton data structure for encapsulating the dataflow +// values for a CFG. Typically this is subclassed to provide methods for +// computing these values from a CFG. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSES_DATAFLOW_VALUES +#define LLVM_CLANG_ANALYSES_DATAFLOW_VALUES + +#include "clang/AST/CFG.h" +#include "clang/Analysis/ProgramPoint.h" +#include "llvm/ADT/DenseMap.h" + +//===----------------------------------------------------------------------===// +/// Dataflow Directional Tag Classes. These are used for tag dispatching +/// within the dataflow solver/transfer functions to determine what direction +/// a dataflow analysis flows. +//===----------------------------------------------------------------------===// + +namespace clang { +namespace dataflow { + struct forward_analysis_tag {}; + struct backward_analysis_tag {}; +} // end namespace dataflow + +//===----------------------------------------------------------------------===// +/// DataflowValues. Container class to store dataflow values for a CFG. +//===----------------------------------------------------------------------===// + +template <typename ValueTypes, + typename _AnalysisDirTag = dataflow::forward_analysis_tag > +class DataflowValues { + + //===--------------------------------------------------------------------===// + // Type declarations. + //===--------------------------------------------------------------------===// + +public: + typedef typename ValueTypes::ValTy ValTy; + typedef typename ValueTypes::AnalysisDataTy AnalysisDataTy; + typedef _AnalysisDirTag AnalysisDirTag; + typedef llvm::DenseMap<ProgramPoint, ValTy> EdgeDataMapTy; + typedef llvm::DenseMap<const CFGBlock*, ValTy> BlockDataMapTy; + typedef llvm::DenseMap<const Stmt*, ValTy> StmtDataMapTy; + + //===--------------------------------------------------------------------===// + // Predicates. + //===--------------------------------------------------------------------===// + +public: + /// isForwardAnalysis - Returns true if the dataflow values are computed + /// from a forward analysis. + bool isForwardAnalysis() { return isForwardAnalysis(AnalysisDirTag()); } + + /// isBackwardAnalysis - Returns true if the dataflow values are computed + /// from a backward analysis. + bool isBackwardAnalysis() { return !isForwardAnalysis(); } + +private: + bool isForwardAnalysis(dataflow::forward_analysis_tag) { return true; } + bool isForwardAnalysis(dataflow::backward_analysis_tag) { return false; } + + //===--------------------------------------------------------------------===// + // Initialization and accessors methods. + //===--------------------------------------------------------------------===// + +public: + DataflowValues() : StmtDataMap(NULL) {} + ~DataflowValues() { delete StmtDataMap; } + + /// InitializeValues - Invoked by the solver to initialize state needed for + /// dataflow analysis. This method is usually specialized by subclasses. + void InitializeValues(const CFG& cfg) {}; + + + /// getEdgeData - Retrieves the dataflow values associated with a + /// CFG edge. + ValTy& getEdgeData(const BlockEdge& E) { + typename EdgeDataMapTy::iterator I = EdgeDataMap.find(E); + assert (I != EdgeDataMap.end() && "No data associated with Edge."); + return I->second; + } + + const ValTy& getEdgeData(const BlockEdge& E) const { + return reinterpret_cast<DataflowValues*>(this)->getEdgeData(E); + } + + /// getBlockData - Retrieves the dataflow values associated with a + /// specified CFGBlock. If the dataflow analysis is a forward analysis, + /// this data is associated with the END of the block. If the analysis + /// is a backwards analysis, it is associated with the ENTRY of the block. + ValTy& getBlockData(const CFGBlock* B) { + typename BlockDataMapTy::iterator I = BlockDataMap.find(B); + assert (I != BlockDataMap.end() && "No data associated with block."); + return I->second; + } + + const ValTy& getBlockData(const CFGBlock* B) const { + return const_cast<DataflowValues*>(this)->getBlockData(B); + } + + /// getStmtData - Retrieves the dataflow values associated with a + /// specified Stmt. If the dataflow analysis is a forward analysis, + /// this data corresponds to the point immediately before a Stmt. + /// If the analysis is a backwards analysis, it is associated with + /// the point after a Stmt. This data is only computed for block-level + /// expressions, and only when requested when the analysis is executed. + ValTy& getStmtData(const Stmt* S) { + assert (StmtDataMap && "Dataflow values were not computed for statements."); + typename StmtDataMapTy::iterator I = StmtDataMap->find(S); + assert (I != StmtDataMap->end() && "No data associated with statement."); + return I->second; + } + + const ValTy& getStmtData(const Stmt* S) const { + return const_cast<DataflowValues*>(this)->getStmtData(S); + } + + /// getEdgeDataMap - Retrieves the internal map between CFG edges and + /// dataflow values. Usually used by a dataflow solver to compute + /// values for blocks. + EdgeDataMapTy& getEdgeDataMap() { return EdgeDataMap; } + const EdgeDataMapTy& getEdgeDataMap() const { return EdgeDataMap; } + + /// getBlockDataMap - Retrieves the internal map between CFGBlocks and + /// dataflow values. If the dataflow analysis operates in the forward + /// direction, the values correspond to the dataflow values at the start + /// of the block. Otherwise, for a backward analysis, the values correpsond + /// to the dataflow values at the end of the block. + BlockDataMapTy& getBlockDataMap() { return BlockDataMap; } + const BlockDataMapTy& getBlockDataMap() const { return BlockDataMap; } + + /// getStmtDataMap - Retrieves the internal map between Stmts and + /// dataflow values. + StmtDataMapTy& getStmtDataMap() { + if (!StmtDataMap) StmtDataMap = new StmtDataMapTy(); + return *StmtDataMap; + } + + const StmtDataMapTy& getStmtDataMap() const { + return const_cast<DataflowValues*>(this)->getStmtDataMap(); + } + + /// getAnalysisData - Retrieves the meta data associated with a + /// dataflow analysis for analyzing a particular CFG. + /// This is typically consumed by transfer function code (via the solver). + /// This can also be used by subclasses to interpret the dataflow values. + AnalysisDataTy& getAnalysisData() { return AnalysisData; } + const AnalysisDataTy& getAnalysisData() const { return AnalysisData; } + + //===--------------------------------------------------------------------===// + // Internal data. + //===--------------------------------------------------------------------===// + +protected: + EdgeDataMapTy EdgeDataMap; + BlockDataMapTy BlockDataMap; + StmtDataMapTy* StmtDataMap; + AnalysisDataTy AnalysisData; +}; + +} // end namespace clang +#endif |
