• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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.
isForwardAnalysis()62   bool isForwardAnalysis() { return isForwardAnalysis(AnalysisDirTag()); }
63 
64   /// isBackwardAnalysis - Returns true if the dataflow values are computed
65   ///  from a backward analysis.
isBackwardAnalysis()66   bool isBackwardAnalysis() { return !isForwardAnalysis(); }
67 
68 private:
isForwardAnalysis(dataflow::forward_analysis_tag)69   bool isForwardAnalysis(dataflow::forward_analysis_tag)  { return true; }
isForwardAnalysis(dataflow::backward_analysis_tag)70   bool isForwardAnalysis(dataflow::backward_analysis_tag) { return false; }
71 
72   //===--------------------------------------------------------------------===//
73   // Initialization and accessors methods.
74   //===--------------------------------------------------------------------===//
75 
76 public:
DataflowValues()77   DataflowValues() : StmtDataMap(NULL) {}
~DataflowValues()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.
InitializeValues(const CFG & cfg)82   void InitializeValues(const CFG& cfg) {}
83 
84 
85   /// getEdgeData - Retrieves the dataflow values associated with a
86   ///  CFG edge.
getEdgeData(const BlockEdge & E)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 
getEdgeData(const BlockEdge & E)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.
getBlockData(const CFGBlock * B)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 
getBlockData(const CFGBlock * B)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.
getStmtData(const Stmt * S)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 
getStmtData(const Stmt * S)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.
getEdgeDataMap()131   EdgeDataMapTy& getEdgeDataMap() { return EdgeDataMap; }
getEdgeDataMap()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.
getBlockDataMap()139   BlockDataMapTy& getBlockDataMap() { return BlockDataMap; }
getBlockDataMap()140   const BlockDataMapTy& getBlockDataMap() const { return BlockDataMap; }
141 
142   /// getStmtDataMap - Retrieves the internal map between Stmts and
143   /// dataflow values.
getStmtDataMap()144   StmtDataMapTy& getStmtDataMap() {
145     if (!StmtDataMap) StmtDataMap = new StmtDataMapTy();
146     return *StmtDataMap;
147   }
148 
getStmtDataMap()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.
getAnalysisData()157   AnalysisDataTy& getAnalysisData() { return AnalysisData; }
getAnalysisData()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