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