/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===-- DataflowAnalysisContext.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 a DataflowAnalysisContext class that owns objects that |
10 | | // encompass the state of a program and stores context that is used during |
11 | | // dataflow analysis. |
12 | | // |
13 | | //===----------------------------------------------------------------------===// |
14 | | |
15 | | #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H |
16 | | #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H |
17 | | |
18 | | #include "clang/AST/Decl.h" |
19 | | #include "clang/AST/Expr.h" |
20 | | #include "clang/Analysis/FlowSensitive/Solver.h" |
21 | | #include "clang/Analysis/FlowSensitive/StorageLocation.h" |
22 | | #include "clang/Analysis/FlowSensitive/Value.h" |
23 | | #include "llvm/ADT/DenseMap.h" |
24 | | #include "llvm/ADT/DenseSet.h" |
25 | | #include <cassert> |
26 | | #include <memory> |
27 | | #include <type_traits> |
28 | | #include <utility> |
29 | | #include <vector> |
30 | | |
31 | | namespace clang { |
32 | | namespace dataflow { |
33 | | |
34 | | /// Skip past nodes that the CFG does not emit. These nodes are invisible to |
35 | | /// flow-sensitive analysis, and should be ignored as they will effectively not |
36 | | /// exist. |
37 | | /// |
38 | | /// * `ParenExpr` - The CFG takes the operator precedence into account, but |
39 | | /// otherwise omits the node afterwards. |
40 | | /// |
41 | | /// * `ExprWithCleanups` - The CFG will generate the appropriate calls to |
42 | | /// destructors and then omit the node. |
43 | | /// |
44 | | const Expr &ignoreCFGOmittedNodes(const Expr &E); |
45 | | const Stmt &ignoreCFGOmittedNodes(const Stmt &S); |
46 | | |
47 | | /// Owns objects that encompass the state of a program and stores context that |
48 | | /// is used during dataflow analysis. |
49 | | class DataflowAnalysisContext { |
50 | | public: |
51 | | /// Constructs a dataflow analysis context. |
52 | | /// |
53 | | /// Requirements: |
54 | | /// |
55 | | /// `S` must not be null. |
56 | | DataflowAnalysisContext(std::unique_ptr<Solver> S) |
57 | | : S(std::move(S)), TrueVal(createAtomicBoolValue()), |
58 | | FalseVal(createAtomicBoolValue()) { |
59 | | assert(this->S != nullptr); |
60 | | } |
61 | | |
62 | | /// Takes ownership of `Loc` and returns a reference to it. |
63 | | /// |
64 | | /// Requirements: |
65 | | /// |
66 | | /// `Loc` must not be null. |
67 | | template <typename T> |
68 | | typename std::enable_if<std::is_base_of<StorageLocation, T>::value, T &>::type |
69 | 1.66k | takeOwnership(std::unique_ptr<T> Loc) { |
70 | 1.66k | assert(Loc != nullptr); |
71 | 0 | Locs.push_back(std::move(Loc)); |
72 | 1.66k | return *cast<T>(Locs.back().get()); |
73 | 1.66k | } std::__1::enable_if<std::is_base_of<clang::dataflow::StorageLocation, clang::dataflow::AggregateStorageLocation>::value, clang::dataflow::AggregateStorageLocation&>::type clang::dataflow::DataflowAnalysisContext::takeOwnership<clang::dataflow::AggregateStorageLocation>(std::__1::unique_ptr<clang::dataflow::AggregateStorageLocation, std::__1::default_delete<clang::dataflow::AggregateStorageLocation> >) Line | Count | Source | 69 | 864 | takeOwnership(std::unique_ptr<T> Loc) { | 70 | 864 | assert(Loc != nullptr); | 71 | 0 | Locs.push_back(std::move(Loc)); | 72 | 864 | return *cast<T>(Locs.back().get()); | 73 | 864 | } |
std::__1::enable_if<std::is_base_of<clang::dataflow::StorageLocation, clang::dataflow::ScalarStorageLocation>::value, clang::dataflow::ScalarStorageLocation&>::type clang::dataflow::DataflowAnalysisContext::takeOwnership<clang::dataflow::ScalarStorageLocation>(std::__1::unique_ptr<clang::dataflow::ScalarStorageLocation, std::__1::default_delete<clang::dataflow::ScalarStorageLocation> >) Line | Count | Source | 69 | 799 | takeOwnership(std::unique_ptr<T> Loc) { | 70 | 799 | assert(Loc != nullptr); | 71 | 0 | Locs.push_back(std::move(Loc)); | 72 | 799 | return *cast<T>(Locs.back().get()); | 73 | 799 | } |
|
74 | | |
75 | | /// Takes ownership of `Val` and returns a reference to it. |
76 | | /// |
77 | | /// Requirements: |
78 | | /// |
79 | | /// `Val` must not be null. |
80 | | template <typename T> |
81 | | typename std::enable_if<std::is_base_of<Value, T>::value, T &>::type |
82 | 789k | takeOwnership(std::unique_ptr<T> Val) { |
83 | 789k | assert(Val != nullptr); |
84 | 0 | Vals.push_back(std::move(Val)); |
85 | 789k | return *cast<T>(Vals.back().get()); |
86 | 789k | } std::__1::enable_if<std::is_base_of<clang::dataflow::Value, clang::dataflow::AtomicBoolValue>::value, clang::dataflow::AtomicBoolValue&>::type clang::dataflow::DataflowAnalysisContext::takeOwnership<clang::dataflow::AtomicBoolValue>(std::__1::unique_ptr<clang::dataflow::AtomicBoolValue, std::__1::default_delete<clang::dataflow::AtomicBoolValue> >) Line | Count | Source | 82 | 202k | takeOwnership(std::unique_ptr<T> Val) { | 83 | 202k | assert(Val != nullptr); | 84 | 0 | Vals.push_back(std::move(Val)); | 85 | 202k | return *cast<T>(Vals.back().get()); | 86 | 202k | } |
std::__1::enable_if<std::is_base_of<clang::dataflow::Value, clang::dataflow::ConjunctionValue>::value, clang::dataflow::ConjunctionValue&>::type clang::dataflow::DataflowAnalysisContext::takeOwnership<clang::dataflow::ConjunctionValue>(std::__1::unique_ptr<clang::dataflow::ConjunctionValue, std::__1::default_delete<clang::dataflow::ConjunctionValue> >) Line | Count | Source | 82 | 60 | takeOwnership(std::unique_ptr<T> Val) { | 83 | 60 | assert(Val != nullptr); | 84 | 0 | Vals.push_back(std::move(Val)); | 85 | 60 | return *cast<T>(Vals.back().get()); | 86 | 60 | } |
std::__1::enable_if<std::is_base_of<clang::dataflow::Value, clang::dataflow::DisjunctionValue>::value, clang::dataflow::DisjunctionValue&>::type clang::dataflow::DataflowAnalysisContext::takeOwnership<clang::dataflow::DisjunctionValue>(std::__1::unique_ptr<clang::dataflow::DisjunctionValue, std::__1::default_delete<clang::dataflow::DisjunctionValue> >) Line | Count | Source | 82 | 382k | takeOwnership(std::unique_ptr<T> Val) { | 83 | 382k | assert(Val != nullptr); | 84 | 0 | Vals.push_back(std::move(Val)); | 85 | 382k | return *cast<T>(Vals.back().get()); | 86 | 382k | } |
std::__1::enable_if<std::is_base_of<clang::dataflow::Value, clang::dataflow::NegationValue>::value, clang::dataflow::NegationValue&>::type clang::dataflow::DataflowAnalysisContext::takeOwnership<clang::dataflow::NegationValue>(std::__1::unique_ptr<clang::dataflow::NegationValue, std::__1::default_delete<clang::dataflow::NegationValue> >) Line | Count | Source | 82 | 202k | takeOwnership(std::unique_ptr<T> Val) { | 83 | 202k | assert(Val != nullptr); | 84 | 0 | Vals.push_back(std::move(Val)); | 85 | 202k | return *cast<T>(Vals.back().get()); | 86 | 202k | } |
std::__1::enable_if<std::is_base_of<clang::dataflow::Value, clang::dataflow::IntegerValue>::value, clang::dataflow::IntegerValue&>::type clang::dataflow::DataflowAnalysisContext::takeOwnership<clang::dataflow::IntegerValue>(std::__1::unique_ptr<clang::dataflow::IntegerValue, std::__1::default_delete<clang::dataflow::IntegerValue> >) Line | Count | Source | 82 | 210 | takeOwnership(std::unique_ptr<T> Val) { | 83 | 210 | assert(Val != nullptr); | 84 | 0 | Vals.push_back(std::move(Val)); | 85 | 210 | return *cast<T>(Vals.back().get()); | 86 | 210 | } |
std::__1::enable_if<std::is_base_of<clang::dataflow::Value, clang::dataflow::ReferenceValue>::value, clang::dataflow::ReferenceValue&>::type clang::dataflow::DataflowAnalysisContext::takeOwnership<clang::dataflow::ReferenceValue>(std::__1::unique_ptr<clang::dataflow::ReferenceValue, std::__1::default_delete<clang::dataflow::ReferenceValue> >) Line | Count | Source | 82 | 1.07k | takeOwnership(std::unique_ptr<T> Val) { | 83 | 1.07k | assert(Val != nullptr); | 84 | 0 | Vals.push_back(std::move(Val)); | 85 | 1.07k | return *cast<T>(Vals.back().get()); | 86 | 1.07k | } |
std::__1::enable_if<std::is_base_of<clang::dataflow::Value, clang::dataflow::PointerValue>::value, clang::dataflow::PointerValue&>::type clang::dataflow::DataflowAnalysisContext::takeOwnership<clang::dataflow::PointerValue>(std::__1::unique_ptr<clang::dataflow::PointerValue, std::__1::default_delete<clang::dataflow::PointerValue> >) Line | Count | Source | 82 | 58 | takeOwnership(std::unique_ptr<T> Val) { | 83 | 58 | assert(Val != nullptr); | 84 | 0 | Vals.push_back(std::move(Val)); | 85 | 58 | return *cast<T>(Vals.back().get()); | 86 | 58 | } |
std::__1::enable_if<std::is_base_of<clang::dataflow::Value, clang::dataflow::StructValue>::value, clang::dataflow::StructValue&>::type clang::dataflow::DataflowAnalysisContext::takeOwnership<clang::dataflow::StructValue>(std::__1::unique_ptr<clang::dataflow::StructValue, std::__1::default_delete<clang::dataflow::StructValue> >) Line | Count | Source | 82 | 818 | takeOwnership(std::unique_ptr<T> Val) { | 83 | 818 | assert(Val != nullptr); | 84 | 0 | Vals.push_back(std::move(Val)); | 85 | 818 | return *cast<T>(Vals.back().get()); | 86 | 818 | } |
|
87 | | |
88 | | /// Assigns `Loc` as the storage location of `D`. |
89 | | /// |
90 | | /// Requirements: |
91 | | /// |
92 | | /// `D` must not be assigned a storage location. |
93 | 471 | void setStorageLocation(const ValueDecl &D, StorageLocation &Loc) { |
94 | 471 | assert(DeclToLoc.find(&D) == DeclToLoc.end()); |
95 | 0 | DeclToLoc[&D] = &Loc; |
96 | 471 | } |
97 | | |
98 | | /// Returns the storage location assigned to `D` or null if `D` has no |
99 | | /// assigned storage location. |
100 | 761 | StorageLocation *getStorageLocation(const ValueDecl &D) const { |
101 | 761 | auto It = DeclToLoc.find(&D); |
102 | 761 | return It == DeclToLoc.end() ? nullptr471 : It->second290 ; |
103 | 761 | } |
104 | | |
105 | | /// Assigns `Loc` as the storage location of `E`. |
106 | | /// |
107 | | /// Requirements: |
108 | | /// |
109 | | /// `E` must not be assigned a storage location. |
110 | 1.00k | void setStorageLocation(const Expr &E, StorageLocation &Loc) { |
111 | 1.00k | const Expr &CanonE = ignoreCFGOmittedNodes(E); |
112 | 1.00k | assert(ExprToLoc.find(&CanonE) == ExprToLoc.end()); |
113 | 0 | ExprToLoc[&CanonE] = &Loc; |
114 | 1.00k | } |
115 | | |
116 | | /// Returns the storage location assigned to `E` or null if `E` has no |
117 | | /// assigned storage location. |
118 | 2.04k | StorageLocation *getStorageLocation(const Expr &E) const { |
119 | 2.04k | auto It = ExprToLoc.find(&ignoreCFGOmittedNodes(E)); |
120 | 2.04k | return It == ExprToLoc.end() ? nullptr1.00k : It->second1.03k ; |
121 | 2.04k | } |
122 | | |
123 | | /// Assigns `Loc` as the storage location of the `this` pointee. |
124 | | /// |
125 | | /// Requirements: |
126 | | /// |
127 | | /// The `this` pointee must not be assigned a storage location. |
128 | 5 | void setThisPointeeStorageLocation(StorageLocation &Loc) { |
129 | 5 | assert(ThisPointeeLoc == nullptr); |
130 | 0 | ThisPointeeLoc = &Loc; |
131 | 5 | } |
132 | | |
133 | | /// Returns the storage location assigned to the `this` pointee or null if the |
134 | | /// `this` pointee has no assigned storage location. |
135 | 37 | StorageLocation *getThisPointeeStorageLocation() const { |
136 | 37 | return ThisPointeeLoc; |
137 | 37 | } |
138 | | |
139 | | /// Returns a symbolic boolean value that models a boolean literal equal to |
140 | | /// `Value`. |
141 | 1.20k | AtomicBoolValue &getBoolLiteralValue(bool Value) const { |
142 | 1.20k | return Value ? TrueVal671 : FalseVal530 ; |
143 | 1.20k | } |
144 | | |
145 | | /// Creates an atomic boolean value. |
146 | 202k | AtomicBoolValue &createAtomicBoolValue() { |
147 | 202k | return takeOwnership(std::make_unique<AtomicBoolValue>()); |
148 | 202k | } |
149 | | |
150 | | /// Returns a boolean value that represents the conjunction of `LHS` and |
151 | | /// `RHS`. Subsequent calls with the same arguments, regardless of their |
152 | | /// order, will return the same result. If the given boolean values represent |
153 | | /// the same value, the result will be the value itself. |
154 | | BoolValue &getOrCreateConjunctionValue(BoolValue &LHS, BoolValue &RHS); |
155 | | |
156 | | /// Returns a boolean value that represents the disjunction of `LHS` and |
157 | | /// `RHS`. Subsequent calls with the same arguments, regardless of their |
158 | | /// order, will return the same result. If the given boolean values represent |
159 | | /// the same value, the result will be the value itself. |
160 | | BoolValue &getOrCreateDisjunctionValue(BoolValue &LHS, BoolValue &RHS); |
161 | | |
162 | | /// Returns a boolean value that represents the negation of `Val`. Subsequent |
163 | | /// calls with the same argument will return the same result. |
164 | | BoolValue &getOrCreateNegationValue(BoolValue &Val); |
165 | | |
166 | | /// Creates a fresh flow condition and returns a token that identifies it. The |
167 | | /// token can be used to perform various operations on the flow condition such |
168 | | /// as adding constraints to it, forking it, joining it with another flow |
169 | | /// condition, or checking implications. |
170 | | AtomicBoolValue &makeFlowConditionToken(); |
171 | | |
172 | | /// Adds `Constraint` to the flow condition identified by `Token`. |
173 | | void addFlowConditionConstraint(AtomicBoolValue &Token, |
174 | | BoolValue &Constraint); |
175 | | |
176 | | /// Creates a new flow condition with the same constraints as the flow |
177 | | /// condition identified by `Token` and returns its token. |
178 | | AtomicBoolValue &forkFlowCondition(AtomicBoolValue &Token); |
179 | | |
180 | | /// Creates a new flow condition that represents the disjunction of the flow |
181 | | /// conditions identified by `FirstToken` and `SecondToken`, and returns its |
182 | | /// token. |
183 | | AtomicBoolValue &joinFlowConditions(AtomicBoolValue &FirstToken, |
184 | | AtomicBoolValue &SecondToken); |
185 | | |
186 | | /// Returns true if and only if the constraints of the flow condition |
187 | | /// identified by `Token` imply that `Val` is true. |
188 | | bool flowConditionImplies(AtomicBoolValue &Token, BoolValue &Val); |
189 | | |
190 | | /// Returns true if and only if the constraints of the flow condition |
191 | | /// identified by `Token` are always true. |
192 | | bool flowConditionIsTautology(AtomicBoolValue &Token); |
193 | | |
194 | | private: |
195 | | /// Adds all constraints of the flow condition identified by `Token` and all |
196 | | /// of its transitive dependencies to `Constraints`. `VisitedTokens` is used |
197 | | /// to track tokens of flow conditions that were already visited by recursive |
198 | | /// calls. |
199 | | void addTransitiveFlowConditionConstraints( |
200 | | AtomicBoolValue &Token, llvm::DenseSet<BoolValue *> &Constraints, |
201 | | llvm::DenseSet<AtomicBoolValue *> &VisitedTokens) const; |
202 | | |
203 | | std::unique_ptr<Solver> S; |
204 | | |
205 | | // Storage for the state of a program. |
206 | | std::vector<std::unique_ptr<StorageLocation>> Locs; |
207 | | std::vector<std::unique_ptr<Value>> Vals; |
208 | | |
209 | | // Maps from program declarations and statements to storage locations that are |
210 | | // assigned to them. These assignments are global (aggregated across all basic |
211 | | // blocks) and are used to produce stable storage locations when the same |
212 | | // basic blocks are evaluated multiple times. The storage locations that are |
213 | | // in scope for a particular basic block are stored in `Environment`. |
214 | | llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc; |
215 | | llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc; |
216 | | |
217 | | StorageLocation *ThisPointeeLoc = nullptr; |
218 | | |
219 | | AtomicBoolValue &TrueVal; |
220 | | AtomicBoolValue &FalseVal; |
221 | | |
222 | | // Indices that are used to avoid recreating the same composite boolean |
223 | | // values. |
224 | | llvm::DenseMap<std::pair<BoolValue *, BoolValue *>, ConjunctionValue *> |
225 | | ConjunctionVals; |
226 | | llvm::DenseMap<std::pair<BoolValue *, BoolValue *>, DisjunctionValue *> |
227 | | DisjunctionVals; |
228 | | llvm::DenseMap<BoolValue *, NegationValue *> NegationVals; |
229 | | |
230 | | // Flow conditions are tracked symbolically: each unique flow condition is |
231 | | // associated with a fresh symbolic variable (token), bound to the clause that |
232 | | // defines the flow condition. Conceptually, each binding corresponds to an |
233 | | // "iff" of the form `FC <=> (C1 ^ C2 ^ ...)` where `FC` is a flow condition |
234 | | // token (an atomic boolean) and `Ci`s are the set of constraints in the flow |
235 | | // flow condition clause. Internally, we do not record the formula directly as |
236 | | // an "iff". Instead, a flow condition clause is encoded as conjuncts of the |
237 | | // form `(FC v !C1 v !C2 v ...) ^ (C1 v !FC) ^ (C2 v !FC) ^ ...`. The first |
238 | | // conjuct is stored in the `FlowConditionFirstConjuncts` map and the set of |
239 | | // remaining conjuncts are stored in the `FlowConditionRemainingConjuncts` |
240 | | // map, both keyed by the token of the flow condition. |
241 | | // |
242 | | // Flow conditions depend on other flow conditions if they are created using |
243 | | // `forkFlowCondition` or `joinFlowConditions`. The graph of flow condition |
244 | | // dependencies is stored in the `FlowConditionDeps` map. |
245 | | llvm::DenseMap<AtomicBoolValue *, llvm::DenseSet<AtomicBoolValue *>> |
246 | | FlowConditionDeps; |
247 | | llvm::DenseMap<AtomicBoolValue *, BoolValue *> FlowConditionFirstConjuncts; |
248 | | llvm::DenseMap<AtomicBoolValue *, llvm::DenseSet<BoolValue *>> |
249 | | FlowConditionRemainingConjuncts; |
250 | | }; |
251 | | |
252 | | } // namespace dataflow |
253 | | } // namespace clang |
254 | | |
255 | | #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H |