/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h
Line | Count | Source |
1 | | //===- DataflowAnalysis.h ---------------------------------------*- 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 base types and functions for building dataflow analyses |
10 | | // that run over Control-Flow Graphs (CFGs). |
11 | | // |
12 | | //===----------------------------------------------------------------------===// |
13 | | |
14 | | #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H |
15 | | #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H |
16 | | |
17 | | #include <iterator> |
18 | | #include <utility> |
19 | | #include <vector> |
20 | | |
21 | | #include "clang/AST/ASTContext.h" |
22 | | #include "clang/AST/Stmt.h" |
23 | | #include "clang/Analysis/CFG.h" |
24 | | #include "clang/Analysis/FlowSensitive/ControlFlowContext.h" |
25 | | #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" |
26 | | #include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h" |
27 | | #include "llvm/ADT/Any.h" |
28 | | #include "llvm/ADT/Optional.h" |
29 | | #include "llvm/ADT/STLExtras.h" |
30 | | #include "llvm/Support/Error.h" |
31 | | |
32 | | namespace clang { |
33 | | namespace dataflow { |
34 | | |
35 | | /// Base class template for dataflow analyses built on a single lattice type. |
36 | | /// |
37 | | /// Requirements: |
38 | | /// |
39 | | /// `Derived` must be derived from a specialization of this class template and |
40 | | /// must provide the following public members: |
41 | | /// * `LatticeT initialElement()` - returns a lattice element that models the |
42 | | /// initial state of a basic block; |
43 | | /// * `void transfer(const Stmt *, LatticeT &, Environment &)` - applies the |
44 | | /// analysis transfer function for a given statement and lattice element. |
45 | | /// |
46 | | /// `Derived` can optionally override the following members: |
47 | | /// * `bool merge(QualType, const Value &, const Value &, Value &, |
48 | | /// Environment &)` - joins distinct values. This could be a strict |
49 | | /// lattice join or a more general widening operation. |
50 | | /// |
51 | | /// `LatticeT` is a bounded join-semilattice that is used by `Derived` and must |
52 | | /// provide the following public members: |
53 | | /// * `LatticeJoinEffect join(const LatticeT &)` - joins the object and the |
54 | | /// argument by computing their least upper bound, modifies the object if |
55 | | /// necessary, and returns an effect indicating whether any changes were |
56 | | /// made to it; |
57 | | /// * `bool operator==(const LatticeT &) const` - returns true if and only if |
58 | | /// the object is equal to the argument. |
59 | | template <typename Derived, typename LatticeT> |
60 | | class DataflowAnalysis : public TypeErasedDataflowAnalysis { |
61 | | public: |
62 | | /// Bounded join-semilattice that is used in the analysis. |
63 | | using Lattice = LatticeT; |
64 | | |
65 | 243 | explicit DataflowAnalysis(ASTContext &Context) : Context(Context) {} |
66 | | explicit DataflowAnalysis(ASTContext &Context, bool ApplyBuiltinTransfer) |
67 | | : TypeErasedDataflowAnalysis(ApplyBuiltinTransfer), Context(Context) {} |
68 | | |
69 | 6.91k | ASTContext &getASTContext() final { return Context; } |
70 | | |
71 | 486 | TypeErasedLattice typeErasedInitialElement() final { |
72 | 486 | return {static_cast<Derived *>(this)->initialElement()}; |
73 | 486 | } |
74 | | |
75 | | LatticeJoinEffect joinTypeErased(TypeErasedLattice &E1, |
76 | 315 | const TypeErasedLattice &E2) final { |
77 | 315 | Lattice &L1 = llvm::any_cast<Lattice &>(E1.Value); |
78 | 315 | const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value); |
79 | 315 | return L1.join(L2); |
80 | 315 | } |
81 | | |
82 | | bool isEqualTypeErased(const TypeErasedLattice &E1, |
83 | 39 | const TypeErasedLattice &E2) final { |
84 | 39 | const Lattice &L1 = llvm::any_cast<const Lattice &>(E1.Value); |
85 | 39 | const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value); |
86 | 39 | return L1 == L2; |
87 | 39 | } |
88 | | |
89 | | void transferTypeErased(const Stmt *Stmt, TypeErasedLattice &E, |
90 | 6.91k | Environment &Env) final { |
91 | 6.91k | Lattice &L = llvm::any_cast<Lattice &>(E.Value); |
92 | 6.91k | static_cast<Derived *>(this)->transfer(Stmt, L, Env); |
93 | 6.91k | } |
94 | | |
95 | | private: |
96 | | ASTContext &Context; |
97 | | }; |
98 | | |
99 | | // Model of the program at a given program point. |
100 | | template <typename LatticeT> struct DataflowAnalysisState { |
101 | | // Model of a program property. |
102 | | LatticeT Lattice; |
103 | | |
104 | | // Model of the state of the program (store and heap). |
105 | | Environment Env; |
106 | | }; |
107 | | |
108 | | /// Performs dataflow analysis and returns a mapping from basic block IDs to |
109 | | /// dataflow analysis states that model the respective basic blocks. The |
110 | | /// returned vector, if any, will have the same size as the number of CFG |
111 | | /// blocks, with indices corresponding to basic block IDs. Returns an error if |
112 | | /// the dataflow analysis cannot be performed successfully. Otherwise, calls |
113 | | /// `PostVisitStmt` on each statement with the final analysis results at that |
114 | | /// program point. |
115 | | template <typename AnalysisT> |
116 | | llvm::Expected<std::vector< |
117 | | llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>> |
118 | | runDataflowAnalysis( |
119 | | const ControlFlowContext &CFCtx, AnalysisT &Analysis, |
120 | | const Environment &InitEnv, |
121 | | std::function<void(const Stmt *, const DataflowAnalysisState< |
122 | | typename AnalysisT::Lattice> &)> |
123 | | PostVisitStmt = nullptr) { |
124 | | std::function<void(const Stmt *, const TypeErasedDataflowAnalysisState &)> |
125 | | PostVisitStmtClosure = nullptr; |
126 | | if (PostVisitStmt != nullptr) { |
127 | | PostVisitStmtClosure = [&PostVisitStmt]( |
128 | | const Stmt *Stmt, |
129 | | const TypeErasedDataflowAnalysisState &State) { |
130 | | auto *Lattice = |
131 | | llvm::any_cast<typename AnalysisT::Lattice>(&State.Lattice.Value); |
132 | | PostVisitStmt(Stmt, DataflowAnalysisState<typename AnalysisT::Lattice>{ |
133 | | *Lattice, State.Env}); |
134 | | }; |
135 | | } |
136 | | |
137 | | auto TypeErasedBlockStates = runTypeErasedDataflowAnalysis( |
138 | | CFCtx, Analysis, InitEnv, PostVisitStmtClosure); |
139 | | if (!TypeErasedBlockStates) |
140 | | return TypeErasedBlockStates.takeError(); |
141 | | |
142 | | std::vector< |
143 | | llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>> |
144 | | BlockStates; |
145 | | BlockStates.reserve(TypeErasedBlockStates->size()); |
146 | | |
147 | | llvm::transform(std::move(*TypeErasedBlockStates), |
148 | | std::back_inserter(BlockStates), [](auto &OptState) { |
149 | | return std::move(OptState).map([](auto &&State) { |
150 | | return DataflowAnalysisState<typename AnalysisT::Lattice>{ |
151 | | llvm::any_cast<typename AnalysisT::Lattice>( |
152 | | std::move(State.Lattice.Value)), |
153 | | std::move(State.Env)}; |
154 | | }); |
155 | | }); |
156 | | return BlockStates; |
157 | | } |
158 | | |
159 | | /// Abstract base class for dataflow "models": reusable analysis components that |
160 | | /// model a particular aspect of program semantics in the `Environment`. For |
161 | | /// example, a model may capture a type and its related functions. |
162 | | class DataflowModel : public Environment::ValueModel { |
163 | | public: |
164 | | /// Return value indicates whether the model processed the `Stmt`. |
165 | | virtual bool transfer(const Stmt *Stmt, Environment &Env) = 0; |
166 | | }; |
167 | | |
168 | | } // namespace dataflow |
169 | | } // namespace clang |
170 | | |
171 | | #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H |