DataflowValues.h revision e41611aa2237d06a0ef61db4528fb2883a8defcd 
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
29namespace clang {
30namespace 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
39template <typename ValueTypes,
40          typename _AnalysisDirTag = dataflow::forward_analysis_tag >
41class DataflowValues {
42
43  //===--------------------------------------------------------------------===//
44  // Type declarations.
45  //===--------------------------------------------------------------------===//
46
47public:
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
59public:
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
68private:
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
76public:
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
164protected:
165  EdgeDataMapTy      EdgeDataMap;
166  BlockDataMapTy     BlockDataMap;
167  StmtDataMapTy*     StmtDataMap;
168  AnalysisDataTy     AnalysisData;
169};
170
171} // end namespace clang
172#endif
173