diff options
Diffstat (limited to 'include/clang/Analysis/FlowSensitive')
| -rw-r--r-- | include/clang/Analysis/FlowSensitive/DataflowSolver.h | 100 | ||||
| -rw-r--r-- | include/clang/Analysis/FlowSensitive/DataflowValues.h | 56 |
2 files changed, 78 insertions, 78 deletions
diff --git a/include/clang/Analysis/FlowSensitive/DataflowSolver.h b/include/clang/Analysis/FlowSensitive/DataflowSolver.h index b0614e824f..da4913206d 100644 --- a/include/clang/Analysis/FlowSensitive/DataflowSolver.h +++ b/include/clang/Analysis/FlowSensitive/DataflowSolver.h @@ -33,15 +33,15 @@ 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; + return B; } - + /// isEmpty - Return true if the worklist is empty. bool isEmpty() const { return wlist.empty(); } }; @@ -59,20 +59,20 @@ 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 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, 0); } - + static BlockEdge NextEdge(const CFGBlock* B, const CFGBlock* Next) { return BlockEdge(B, Next, 0); } @@ -82,20 +82,20 @@ 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 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 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 StmtItr StmtEnd(const CFGBlock* B) { return B->rend(); } + static BlockEdge PrevEdge(const CFGBlock* B, const CFGBlock* Prev) { return BlockEdge(B, Prev, 0); } - + static BlockEdge NextEdge(const CFGBlock* B, const CFGBlock* Next) { return BlockEdge(Next, B, 0); } @@ -105,7 +105,7 @@ template <> struct ItrTraits<backward_analysis_tag> { //===----------------------------------------------------------------------===// /// DataflowSolverTy - Generic dataflow solver. //===----------------------------------------------------------------------===// - + template <typename _DFValuesTy, // Usually a subclass of DataflowValues typename _TransferFuncsTy, typename _MergeOperatorTy, @@ -120,7 +120,7 @@ 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; @@ -130,24 +130,24 @@ public: 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() {} - + ~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); + 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 @@ -162,10 +162,10 @@ public: ProcessBlock(B, recordStmtValues, AnalysisDirTag()); } } - + void runOnBlock(const CFGBlock& B, bool recordStmtValues) { runOnBlock(&B, recordStmtValues); - } + } void runOnBlock(CFG::iterator& I, bool recordStmtValues) { runOnBlock(*I, recordStmtValues); } @@ -177,13 +177,13 @@ public: 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) { @@ -191,27 +191,27 @@ private: // 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(); + 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){ - + CFGBlock *PrevBlk = *I; if (!PrevBlk) @@ -229,35 +229,35 @@ private: 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)); + + 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)); + 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(); @@ -272,12 +272,12 @@ private: if (CFGBlock *NextBlk = *I) UpdateEdgeValue(ItrTraits::NextEdge(B, NextBlk),V, NextBlk); } - + /// 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); @@ -287,7 +287,7 @@ private: WorkList.enqueue(TargetBlock); } } - + private: DFValuesTy& D; DataflowWorkListTy WorkList; diff --git a/include/clang/Analysis/FlowSensitive/DataflowValues.h b/include/clang/Analysis/FlowSensitive/DataflowValues.h index 8d7ba94b46..648fe33ab0 100644 --- a/include/clang/Analysis/FlowSensitive/DataflowValues.h +++ b/include/clang/Analysis/FlowSensitive/DataflowValues.h @@ -24,7 +24,7 @@ /// 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 { @@ -34,19 +34,19 @@ 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 typename ValueTypes::AnalysisDataTy AnalysisDataTy; typedef _AnalysisDirTag AnalysisDirTag; typedef llvm::DenseMap<ProgramPoint, ValTy> EdgeDataMapTy; typedef llvm::DenseMap<const CFGBlock*, ValTy> BlockDataMapTy; @@ -60,15 +60,15 @@ 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; } - + bool isForwardAnalysis(dataflow::backward_analysis_tag) { return false; } + //===--------------------------------------------------------------------===// // Initialization and accessors methods. //===--------------------------------------------------------------------===// @@ -76,10 +76,10 @@ private: 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) {}; + void InitializeValues(const CFG& cfg) {}; /// getEdgeData - Retrieves the dataflow values associated with a @@ -89,28 +89,28 @@ public: 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 + /// 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. + /// 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 + + /// 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. + /// 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. @@ -120,11 +120,11 @@ public: 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. @@ -138,35 +138,35 @@ public: /// 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. + /// 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 |