1 //===--- DataflowValues.h - Data structure for dataflow values --*- 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 a skeleton data structure for encapsulating the dataflow 11 // values for a CFG. Typically this is subclassed to provide methods for 12 // computing these values from a CFG. 13 // 14 //===----------------------------------------------------------------------===// 15 16 #ifndef LLVM_CLANG_ANALYSES_DATAFLOW_VALUES 17 #define LLVM_CLANG_ANALYSES_DATAFLOW_VALUES 18 19 #include "clang/Analysis/CFG.h" 20 #include "clang/Analysis/ProgramPoint.h" 21 #include "llvm/ADT/DenseMap.h" 22 23 //===----------------------------------------------------------------------===// 24 /// Dataflow Directional Tag Classes. These are used for tag dispatching 25 /// within the dataflow solver/transfer functions to determine what direction 26 /// a dataflow analysis flows. 27 //===----------------------------------------------------------------------===// 28 29 namespace clang { 30 namespace dataflow { 31 struct forward_analysis_tag {}; 32 struct backward_analysis_tag {}; 33 } // end namespace dataflow 34 35 //===----------------------------------------------------------------------===// 36 /// DataflowValues. Container class to store dataflow values for a CFG. 37 //===----------------------------------------------------------------------===// 38 39 template <typename ValueTypes, 40 typename _AnalysisDirTag = dataflow::forward_analysis_tag > 41 class DataflowValues { 42 43 //===--------------------------------------------------------------------===// 44 // Type declarations. 45 //===--------------------------------------------------------------------===// 46 47 public: 48 typedef typename ValueTypes::ValTy ValTy; 49 typedef typename ValueTypes::AnalysisDataTy AnalysisDataTy; 50 typedef _AnalysisDirTag AnalysisDirTag; 51 typedef llvm::DenseMap<ProgramPoint, ValTy> EdgeDataMapTy; 52 typedef llvm::DenseMap<const CFGBlock*, ValTy> BlockDataMapTy; 53 typedef llvm::DenseMap<const Stmt*, ValTy> StmtDataMapTy; 54 55 //===--------------------------------------------------------------------===// 56 // Predicates. 57 //===--------------------------------------------------------------------===// 58 59 public: 60 /// isForwardAnalysis - Returns true if the dataflow values are computed 61 /// from a forward analysis. 62 bool isForwardAnalysis() { return isForwardAnalysis(AnalysisDirTag()); } 63 64 /// isBackwardAnalysis - Returns true if the dataflow values are computed 65 /// from a backward analysis. 66 bool isBackwardAnalysis() { return !isForwardAnalysis(); } 67 68 private: 69 bool isForwardAnalysis(dataflow::forward_analysis_tag) { return true; } 70 bool isForwardAnalysis(dataflow::backward_analysis_tag) { return false; } 71 72 //===--------------------------------------------------------------------===// 73 // Initialization and accessors methods. 74 //===--------------------------------------------------------------------===// 75 76 public: 77 DataflowValues() : StmtDataMap(NULL) {} 78 ~DataflowValues() { delete StmtDataMap; } 79 80 /// InitializeValues - Invoked by the solver to initialize state needed for 81 /// dataflow analysis. This method is usually specialized by subclasses. 82 void InitializeValues(const CFG& cfg) {} 83 84 85 /// getEdgeData - Retrieves the dataflow values associated with a 86 /// CFG edge. 87 ValTy& getEdgeData(const BlockEdge &E) { 88 typename EdgeDataMapTy::iterator I = EdgeDataMap.find(E); 89 assert (I != EdgeDataMap.end() && "No data associated with Edge."); 90 return I->second; 91 } 92 93 const ValTy& getEdgeData(const BlockEdge &E) const { 94 return reinterpret_cast<DataflowValues*>(this)->getEdgeData(E); 95 } 96 97 /// getBlockData - Retrieves the dataflow values associated with a 98 /// specified CFGBlock. If the dataflow analysis is a forward analysis, 99 /// this data is associated with the END of the block. If the analysis 100 /// is a backwards analysis, it is associated with the ENTRY of the block. 101 ValTy& getBlockData(const CFGBlock *B) { 102 typename BlockDataMapTy::iterator I = BlockDataMap.find(B); 103 assert (I != BlockDataMap.end() && "No data associated with block."); 104 return I->second; 105 } 106 107 const ValTy& getBlockData(const CFGBlock *B) const { 108 return const_cast<DataflowValues*>(this)->getBlockData(B); 109 } 110 111 /// getStmtData - Retrieves the dataflow values associated with a 112 /// specified Stmt. If the dataflow analysis is a forward analysis, 113 /// this data corresponds to the point immediately before a Stmt. 114 /// If the analysis is a backwards analysis, it is associated with 115 /// the point after a Stmt. This data is only computed for block-level 116 /// expressions, and only when requested when the analysis is executed. 117 ValTy& getStmtData(const Stmt *S) { 118 assert (StmtDataMap && "Dataflow values were not computed for statements."); 119 typename StmtDataMapTy::iterator I = StmtDataMap->find(S); 120 assert (I != StmtDataMap->end() && "No data associated with statement."); 121 return I->second; 122 } 123 124 const ValTy& getStmtData(const Stmt *S) const { 125 return const_cast<DataflowValues*>(this)->getStmtData(S); 126 } 127 128 /// getEdgeDataMap - Retrieves the internal map between CFG edges and 129 /// dataflow values. Usually used by a dataflow solver to compute 130 /// values for blocks. 131 EdgeDataMapTy& getEdgeDataMap() { return EdgeDataMap; } 132 const EdgeDataMapTy& getEdgeDataMap() const { return EdgeDataMap; } 133 134 /// getBlockDataMap - Retrieves the internal map between CFGBlocks and 135 /// dataflow values. If the dataflow analysis operates in the forward 136 /// direction, the values correspond to the dataflow values at the start 137 /// of the block. Otherwise, for a backward analysis, the values correpsond 138 /// to the dataflow values at the end of the block. 139 BlockDataMapTy& getBlockDataMap() { return BlockDataMap; } 140 const BlockDataMapTy& getBlockDataMap() const { return BlockDataMap; } 141 142 /// getStmtDataMap - Retrieves the internal map between Stmts and 143 /// dataflow values. 144 StmtDataMapTy& getStmtDataMap() { 145 if (!StmtDataMap) StmtDataMap = new StmtDataMapTy(); 146 return *StmtDataMap; 147 } 148 149 const StmtDataMapTy& getStmtDataMap() const { 150 return const_cast<DataflowValues*>(this)->getStmtDataMap(); 151 } 152 153 /// getAnalysisData - Retrieves the meta data associated with a 154 /// dataflow analysis for analyzing a particular CFG. 155 /// This is typically consumed by transfer function code (via the solver). 156 /// This can also be used by subclasses to interpret the dataflow values. 157 AnalysisDataTy& getAnalysisData() { return AnalysisData; } 158 const AnalysisDataTy& getAnalysisData() const { return AnalysisData; } 159 160 //===--------------------------------------------------------------------===// 161 // Internal data. 162 //===--------------------------------------------------------------------===// 163 164 protected: 165 EdgeDataMapTy EdgeDataMap; 166 BlockDataMapTy BlockDataMap; 167 StmtDataMapTy* StmtDataMap; 168 AnalysisDataTy AnalysisData; 169 }; 170 171 } // end namespace clang 172 #endif 173
