/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===-- DataflowEnvironment.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 an Environment class that is used by dataflow analyses |
10 | | // that run over Control-Flow Graphs (CFGs) to keep track of the state of the |
11 | | // program at given program points. |
12 | | // |
13 | | //===----------------------------------------------------------------------===// |
14 | | |
15 | | #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H |
16 | | #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H |
17 | | |
18 | | #include "clang/AST/Decl.h" |
19 | | #include "clang/AST/DeclBase.h" |
20 | | #include "clang/AST/Expr.h" |
21 | | #include "clang/AST/Type.h" |
22 | | #include "clang/AST/TypeOrdering.h" |
23 | | #include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h" |
24 | | #include "clang/Analysis/FlowSensitive/DataflowLattice.h" |
25 | | #include "clang/Analysis/FlowSensitive/StorageLocation.h" |
26 | | #include "clang/Analysis/FlowSensitive/Value.h" |
27 | | #include "llvm/ADT/DenseMap.h" |
28 | | #include "llvm/ADT/DenseSet.h" |
29 | | #include <memory> |
30 | | #include <type_traits> |
31 | | #include <utility> |
32 | | |
33 | | namespace clang { |
34 | | namespace dataflow { |
35 | | |
36 | | /// Indicates what kind of indirections should be skipped past when retrieving |
37 | | /// storage locations or values. |
38 | | /// |
39 | | /// FIXME: Consider renaming this or replacing it with a more appropriate model. |
40 | | /// See the discussion in https://reviews.llvm.org/D116596 for context. |
41 | | enum class SkipPast { |
42 | | /// No indirections should be skipped past. |
43 | | None, |
44 | | /// An optional reference should be skipped past. |
45 | | Reference, |
46 | | /// An optional reference should be skipped past, then an optional pointer |
47 | | /// should be skipped past. |
48 | | ReferenceThenPointer, |
49 | | }; |
50 | | |
51 | | /// Holds the state of the program (store and heap) at a given program point. |
52 | | /// |
53 | | /// WARNING: Symbolic values that are created by the environment for static |
54 | | /// local and global variables are not currently invalidated on function calls. |
55 | | /// This is unsound and should be taken into account when designing dataflow |
56 | | /// analyses. |
57 | | class Environment { |
58 | | public: |
59 | | /// Supplements `Environment` with non-standard comparison and join |
60 | | /// operations. |
61 | | class ValueModel { |
62 | | public: |
63 | 398 | virtual ~ValueModel() = default; |
64 | | |
65 | | /// Returns true if and only if `Val1` is equivalent to `Val2`. |
66 | | /// |
67 | | /// Requirements: |
68 | | /// |
69 | | /// `Val1` and `Val2` must be distinct. |
70 | | /// |
71 | | /// `Val1` and `Val2` must model values of type `Type`. |
72 | | /// |
73 | | /// `Val1` and `Val2` must be assigned to the same storage location in |
74 | | /// `Env1` and `Env2` respectively. |
75 | | virtual bool compareEquivalent(QualType Type, const Value &Val1, |
76 | | const Environment &Env1, const Value &Val2, |
77 | 5 | const Environment &Env2) { |
78 | | // FIXME: Consider adding QualType to StructValue and removing the Type |
79 | | // argument here. |
80 | | // |
81 | | // FIXME: default to a sound comparison and/or expand the comparison logic |
82 | | // built into the framework to support broader forms of equivalence than |
83 | | // strict pointer equality. |
84 | 5 | return true; |
85 | 5 | } |
86 | | |
87 | | /// Modifies `MergedVal` to approximate both `Val1` and `Val2`. This could |
88 | | /// be a strict lattice join or a more general widening operation. |
89 | | /// |
90 | | /// If this function returns true, `MergedVal` will be assigned to a storage |
91 | | /// location of type `Type` in `MergedEnv`. |
92 | | /// |
93 | | /// `Env1` and `Env2` can be used to query child values and path condition |
94 | | /// implications of `Val1` and `Val2` respectively. |
95 | | /// |
96 | | /// Requirements: |
97 | | /// |
98 | | /// `Val1` and `Val2` must be distinct. |
99 | | /// |
100 | | /// `Val1`, `Val2`, and `MergedVal` must model values of type `Type`. |
101 | | /// |
102 | | /// `Val1` and `Val2` must be assigned to the same storage location in |
103 | | /// `Env1` and `Env2` respectively. |
104 | | virtual bool merge(QualType Type, const Value &Val1, |
105 | | const Environment &Env1, const Value &Val2, |
106 | | const Environment &Env2, Value &MergedVal, |
107 | 2 | Environment &MergedEnv) { |
108 | 2 | return true; |
109 | 2 | } |
110 | | }; |
111 | | |
112 | | /// Creates an environment that uses `DACtx` to store objects that encompass |
113 | | /// the state of a program. |
114 | | explicit Environment(DataflowAnalysisContext &DACtx); |
115 | | |
116 | | Environment(const Environment &Other); |
117 | | Environment &operator=(const Environment &Other); |
118 | | |
119 | 5.22k | Environment(Environment &&Other) = default; |
120 | 512 | Environment &operator=(Environment &&Other) = default; |
121 | | |
122 | | /// Creates an environment that uses `DACtx` to store objects that encompass |
123 | | /// the state of a program. |
124 | | /// |
125 | | /// If `DeclCtx` is a function, initializes the environment with symbolic |
126 | | /// representations of the function parameters. |
127 | | /// |
128 | | /// If `DeclCtx` is a non-static member function, initializes the environment |
129 | | /// with a symbolic representation of the `this` pointee. |
130 | | Environment(DataflowAnalysisContext &DACtx, const DeclContext &DeclCtx); |
131 | | |
132 | | /// Returns true if and only if the environment is equivalent to `Other`, i.e |
133 | | /// the two environments: |
134 | | /// - have the same mappings from declarations to storage locations, |
135 | | /// - have the same mappings from expressions to storage locations, |
136 | | /// - have the same or equivalent (according to `Model`) values assigned to |
137 | | /// the same storage locations. |
138 | | /// |
139 | | /// Requirements: |
140 | | /// |
141 | | /// `Other` and `this` must use the same `DataflowAnalysisContext`. |
142 | | bool equivalentTo(const Environment &Other, |
143 | | Environment::ValueModel &Model) const; |
144 | | |
145 | | /// Joins the environment with `Other` by taking the intersection of storage |
146 | | /// locations and values that are stored in them. Distinct values that are |
147 | | /// assigned to the same storage locations in the environment and `Other` are |
148 | | /// merged using `Model`. |
149 | | /// |
150 | | /// Requirements: |
151 | | /// |
152 | | /// `Other` and `this` must use the same `DataflowAnalysisContext`. |
153 | | LatticeJoinEffect join(const Environment &Other, |
154 | | Environment::ValueModel &Model); |
155 | | |
156 | | // FIXME: Rename `createOrGetStorageLocation` to `getOrCreateStorageLocation`, |
157 | | // `getStableStorageLocation`, or something more appropriate. |
158 | | |
159 | | /// Creates a storage location appropriate for `Type`. Does not assign a value |
160 | | /// to the returned storage location in the environment. |
161 | | /// |
162 | | /// Requirements: |
163 | | /// |
164 | | /// `Type` must not be null. |
165 | | StorageLocation &createStorageLocation(QualType Type); |
166 | | |
167 | | /// Creates a storage location for `D`. Does not assign the returned storage |
168 | | /// location to `D` in the environment. Does not assign a value to the |
169 | | /// returned storage location in the environment. |
170 | | StorageLocation &createStorageLocation(const VarDecl &D); |
171 | | |
172 | | /// Creates a storage location for `E`. Does not assign the returned storage |
173 | | /// location to `E` in the environment. Does not assign a value to the |
174 | | /// returned storage location in the environment. |
175 | | StorageLocation &createStorageLocation(const Expr &E); |
176 | | |
177 | | /// Assigns `Loc` as the storage location of `D` in the environment. |
178 | | /// |
179 | | /// Requirements: |
180 | | /// |
181 | | /// `D` must not be assigned a storage location in the environment. |
182 | | void setStorageLocation(const ValueDecl &D, StorageLocation &Loc); |
183 | | |
184 | | /// Returns the storage location assigned to `D` in the environment, applying |
185 | | /// the `SP` policy for skipping past indirections, or null if `D` isn't |
186 | | /// assigned a storage location in the environment. |
187 | | StorageLocation *getStorageLocation(const ValueDecl &D, SkipPast SP) const; |
188 | | |
189 | | /// Assigns `Loc` as the storage location of `E` in the environment. |
190 | | /// |
191 | | /// Requirements: |
192 | | /// |
193 | | /// `E` must not be assigned a storage location in the environment. |
194 | | void setStorageLocation(const Expr &E, StorageLocation &Loc); |
195 | | |
196 | | /// Returns the storage location assigned to `E` in the environment, applying |
197 | | /// the `SP` policy for skipping past indirections, or null if `E` isn't |
198 | | /// assigned a storage location in the environment. |
199 | | StorageLocation *getStorageLocation(const Expr &E, SkipPast SP) const; |
200 | | |
201 | | /// Returns the storage location assigned to the `this` pointee in the |
202 | | /// environment or null if the `this` pointee has no assigned storage location |
203 | | /// in the environment. |
204 | | StorageLocation *getThisPointeeStorageLocation() const; |
205 | | |
206 | | /// Returns a pointer value that represents a null pointer. Calls with |
207 | | /// `PointeeType` that are canonically equivalent will return the same result. |
208 | | PointerValue &getOrCreateNullPointerValue(QualType PointeeType); |
209 | | |
210 | | /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise |
211 | | /// return null. If `Type` is a pointer or reference type, creates all the |
212 | | /// necessary storage locations and values for indirections until it finds a |
213 | | /// non-pointer/non-reference type. |
214 | | /// |
215 | | /// Requirements: |
216 | | /// |
217 | | /// `Type` must not be null. |
218 | | Value *createValue(QualType Type); |
219 | | |
220 | | /// Assigns `Val` as the value of `Loc` in the environment. |
221 | | void setValue(const StorageLocation &Loc, Value &Val); |
222 | | |
223 | | /// Returns the value assigned to `Loc` in the environment or null if `Loc` |
224 | | /// isn't assigned a value in the environment. |
225 | | Value *getValue(const StorageLocation &Loc) const; |
226 | | |
227 | | /// Equivalent to `getValue(getStorageLocation(D, SP), SkipPast::None)` if `D` |
228 | | /// is assigned a storage location in the environment, otherwise returns null. |
229 | | Value *getValue(const ValueDecl &D, SkipPast SP) const; |
230 | | |
231 | | /// Equivalent to `getValue(getStorageLocation(E, SP), SkipPast::None)` if `E` |
232 | | /// is assigned a storage location in the environment, otherwise returns null. |
233 | | Value *getValue(const Expr &E, SkipPast SP) const; |
234 | | |
235 | | /// Transfers ownership of `Loc` to the analysis context and returns a |
236 | | /// reference to it. |
237 | | /// |
238 | | /// Requirements: |
239 | | /// |
240 | | /// `Loc` must not be null. |
241 | | template <typename T> |
242 | | typename std::enable_if<std::is_base_of<StorageLocation, T>::value, T &>::type |
243 | | takeOwnership(std::unique_ptr<T> Loc) { |
244 | | return DACtx->takeOwnership(std::move(Loc)); |
245 | | } |
246 | | |
247 | | /// Transfers ownership of `Val` to the analysis context and returns a |
248 | | /// reference to it. |
249 | | /// |
250 | | /// Requirements: |
251 | | /// |
252 | | /// `Val` must not be null. |
253 | | template <typename T> |
254 | | typename std::enable_if<std::is_base_of<Value, T>::value, T &>::type |
255 | 4.50k | takeOwnership(std::unique_ptr<T> Val) { |
256 | 4.50k | return DACtx->takeOwnership(std::move(Val)); |
257 | 4.50k | } std::__1::enable_if<std::is_base_of<clang::dataflow::Value, clang::dataflow::IntegerValue>::value, clang::dataflow::IntegerValue&>::type clang::dataflow::Environment::takeOwnership<clang::dataflow::IntegerValue>(std::__1::unique_ptr<clang::dataflow::IntegerValue, std::__1::default_delete<clang::dataflow::IntegerValue> >) Line | Count | Source | 255 | 611 | takeOwnership(std::unique_ptr<T> Val) { | 256 | 611 | return DACtx->takeOwnership(std::move(Val)); | 257 | 611 | } |
std::__1::enable_if<std::is_base_of<clang::dataflow::Value, clang::dataflow::ReferenceValue>::value, clang::dataflow::ReferenceValue&>::type clang::dataflow::Environment::takeOwnership<clang::dataflow::ReferenceValue>(std::__1::unique_ptr<clang::dataflow::ReferenceValue, std::__1::default_delete<clang::dataflow::ReferenceValue> >) Line | Count | Source | 255 | 2.21k | takeOwnership(std::unique_ptr<T> Val) { | 256 | 2.21k | return DACtx->takeOwnership(std::move(Val)); | 257 | 2.21k | } |
std::__1::enable_if<std::is_base_of<clang::dataflow::Value, clang::dataflow::PointerValue>::value, clang::dataflow::PointerValue&>::type clang::dataflow::Environment::takeOwnership<clang::dataflow::PointerValue>(std::__1::unique_ptr<clang::dataflow::PointerValue, std::__1::default_delete<clang::dataflow::PointerValue> >) Line | Count | Source | 255 | 125 | takeOwnership(std::unique_ptr<T> Val) { | 256 | 125 | return DACtx->takeOwnership(std::move(Val)); | 257 | 125 | } |
std::__1::enable_if<std::is_base_of<clang::dataflow::Value, clang::dataflow::StructValue>::value, clang::dataflow::StructValue&>::type clang::dataflow::Environment::takeOwnership<clang::dataflow::StructValue>(std::__1::unique_ptr<clang::dataflow::StructValue, std::__1::default_delete<clang::dataflow::StructValue> >) Line | Count | Source | 255 | 1.54k | takeOwnership(std::unique_ptr<T> Val) { | 256 | 1.54k | return DACtx->takeOwnership(std::move(Val)); | 257 | 1.54k | } |
|
258 | | |
259 | | /// Returns a symbolic boolean value that models a boolean literal equal to |
260 | | /// `Value` |
261 | 454 | AtomicBoolValue &getBoolLiteralValue(bool Value) const { |
262 | 454 | return DACtx->getBoolLiteralValue(Value); |
263 | 454 | } |
264 | | |
265 | | /// Returns an atomic boolean value. |
266 | 696 | BoolValue &makeAtomicBoolValue() const { |
267 | 696 | return DACtx->createAtomicBoolValue(); |
268 | 696 | } |
269 | | |
270 | | /// Returns a boolean value that represents the conjunction of `LHS` and |
271 | | /// `RHS`. Subsequent calls with the same arguments, regardless of their |
272 | | /// order, will return the same result. If the given boolean values represent |
273 | | /// the same value, the result will be the value itself. |
274 | 184 | BoolValue &makeAnd(BoolValue &LHS, BoolValue &RHS) const { |
275 | 184 | return DACtx->getOrCreateConjunction(LHS, RHS); |
276 | 184 | } |
277 | | |
278 | | /// Returns a boolean value that represents the disjunction of `LHS` and |
279 | | /// `RHS`. Subsequent calls with the same arguments, regardless of their |
280 | | /// order, will return the same result. If the given boolean values represent |
281 | | /// the same value, the result will be the value itself. |
282 | 77 | BoolValue &makeOr(BoolValue &LHS, BoolValue &RHS) const { |
283 | 77 | return DACtx->getOrCreateDisjunction(LHS, RHS); |
284 | 77 | } |
285 | | |
286 | | /// Returns a boolean value that represents the negation of `Val`. Subsequent |
287 | | /// calls with the same argument will return the same result. |
288 | 733 | BoolValue &makeNot(BoolValue &Val) const { |
289 | 733 | return DACtx->getOrCreateNegation(Val); |
290 | 733 | } |
291 | | |
292 | | /// Returns a boolean value represents `LHS` => `RHS`. Subsequent calls with |
293 | | /// the same arguments, will return the same result. If the given boolean |
294 | | /// values represent the same value, the result will be a value that |
295 | | /// represents the true boolean literal. |
296 | 30 | BoolValue &makeImplication(BoolValue &LHS, BoolValue &RHS) const { |
297 | 30 | return DACtx->getOrCreateImplication(LHS, RHS); |
298 | 30 | } |
299 | | |
300 | | /// Returns a boolean value represents `LHS` <=> `RHS`. Subsequent calls with |
301 | | /// the same arguments, regardless of their order, will return the same |
302 | | /// result. If the given boolean values represent the same value, the result |
303 | | /// will be a value that represents the true boolean literal. |
304 | 124 | BoolValue &makeIff(BoolValue &LHS, BoolValue &RHS) const { |
305 | 124 | return DACtx->getOrCreateIff(LHS, RHS); |
306 | 124 | } |
307 | | |
308 | | /// Returns the token that identifies the flow condition of the environment. |
309 | 108 | AtomicBoolValue &getFlowConditionToken() const { return *FlowConditionToken; } |
310 | | |
311 | | /// Builds and returns the logical formula defining the flow condition |
312 | | /// identified by `Token`. If a value in the formula is present as a key in |
313 | | /// `Substitutions`, it will be substituted with the value it maps to. |
314 | | BoolValue &buildAndSubstituteFlowCondition( |
315 | | AtomicBoolValue &Token, |
316 | 0 | llvm::DenseMap<AtomicBoolValue *, BoolValue *> Substitutions) { |
317 | 0 | return DACtx->buildAndSubstituteFlowCondition(Token, |
318 | 0 | std::move(Substitutions)); |
319 | 0 | } |
320 | | |
321 | | /// Adds `Val` to the set of clauses that constitute the flow condition. |
322 | | void addToFlowCondition(BoolValue &Val); |
323 | | |
324 | | /// Returns true if and only if the clauses that constitute the flow condition |
325 | | /// imply that `Val` is true. |
326 | | bool flowConditionImplies(BoolValue &Val) const; |
327 | | |
328 | | private: |
329 | | /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise |
330 | | /// return null. |
331 | | /// |
332 | | /// Recursively initializes storage locations and values until it sees a |
333 | | /// self-referential pointer or reference type. `Visited` is used to track |
334 | | /// which types appeared in the reference/pointer chain in order to avoid |
335 | | /// creating a cyclic dependency with self-referential pointers/references. |
336 | | /// |
337 | | /// Requirements: |
338 | | /// |
339 | | /// `Type` must not be null. |
340 | | Value *createValueUnlessSelfReferential(QualType Type, |
341 | | llvm::DenseSet<QualType> &Visited, |
342 | | int Depth, int &CreatedValuesCount); |
343 | | |
344 | | StorageLocation &skip(StorageLocation &Loc, SkipPast SP) const; |
345 | | const StorageLocation &skip(const StorageLocation &Loc, SkipPast SP) const; |
346 | | |
347 | | // `DACtx` is not null and not owned by this object. |
348 | | DataflowAnalysisContext *DACtx; |
349 | | |
350 | | // Maps from program declarations and statements to storage locations that are |
351 | | // assigned to them. Unlike the maps in `DataflowAnalysisContext`, these |
352 | | // include only storage locations that are in scope for a particular basic |
353 | | // block. |
354 | | llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc; |
355 | | llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc; |
356 | | |
357 | | llvm::DenseMap<const StorageLocation *, Value *> LocToVal; |
358 | | |
359 | | // Maps locations of struct members to symbolic values of the structs that own |
360 | | // them and the decls of the struct members. |
361 | | llvm::DenseMap<const StorageLocation *, |
362 | | std::pair<StructValue *, const ValueDecl *>> |
363 | | MemberLocToStruct; |
364 | | |
365 | | AtomicBoolValue *FlowConditionToken; |
366 | | }; |
367 | | |
368 | | } // namespace dataflow |
369 | | } // namespace clang |
370 | | |
371 | | #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H |