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/Analysis/FlowSensitive/ASTOps.h"
23#include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
24#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
25#include "clang/Analysis/FlowSensitive/Formula.h"
26#include "clang/Analysis/FlowSensitive/Logger.h"
27#include "clang/Analysis/FlowSensitive/StorageLocation.h"
28#include "clang/Analysis/FlowSensitive/Value.h"
29#include "llvm/ADT/DenseMap.h"
30#include "llvm/ADT/DenseSet.h"
31#include "llvm/ADT/MapVector.h"
32#include "llvm/Support/Compiler.h"
33#include "llvm/Support/ErrorHandling.h"
34#include <cassert>
35#include <memory>
36#include <type_traits>
37#include <utility>
38#include <vector>
39
40namespace clang {
41namespace dataflow {
42
43/// Indicates the result of a tentative comparison.
44enum class ComparisonResult {
45 Same,
46 Different,
47 Unknown,
48};
49
50/// The result of a `widen` operation.
51struct WidenResult {
52 /// Non-null pointer to a potentially widened version of the input value.
53 Value *V;
54 /// Whether `V` represents a "change" (that is, a different value) with
55 /// respect to the previous value in the sequence.
56 LatticeEffect Effect;
57};
58
59/// Holds the state of the program (store and heap) at a given program point.
60///
61/// WARNING: Symbolic values that are created by the environment for static
62/// local and global variables are not currently invalidated on function calls.
63/// This is unsound and should be taken into account when designing dataflow
64/// analyses.
65class Environment {
66public:
67 /// Supplements `Environment` with non-standard comparison and join
68 /// operations.
69 class ValueModel {
70 public:
71 virtual ~ValueModel() = default;
72
73 /// Returns:
74 /// `Same`: `Val1` is equivalent to `Val2`, according to the model.
75 /// `Different`: `Val1` is distinct from `Val2`, according to the model.
76 /// `Unknown`: The model can't determine a relationship between `Val1` and
77 /// `Val2`.
78 ///
79 /// Requirements:
80 ///
81 /// `Val1` and `Val2` must be distinct.
82 ///
83 /// `Val1` and `Val2` must model values of type `Type`.
84 ///
85 /// `Val1` and `Val2` must be assigned to the same storage location in
86 /// `Env1` and `Env2` respectively.
87 virtual ComparisonResult compare(QualType Type, const Value &Val1,
88 const Environment &Env1, const Value &Val2,
89 const Environment &Env2) {
90 // FIXME: Consider adding `QualType` to `Value` and removing the `Type`
91 // argument here.
92 return ComparisonResult::Unknown;
93 }
94
95 /// Modifies `JoinedVal` to approximate both `Val1` and `Val2`. This should
96 /// obey the properties of a lattice join.
97 ///
98 /// `Env1` and `Env2` can be used to query child values and path condition
99 /// implications of `Val1` and `Val2` respectively.
100 ///
101 /// Requirements:
102 ///
103 /// `Val1` and `Val2` must be distinct.
104 ///
105 /// `Val1`, `Val2`, and `JoinedVal` must model values of type `Type`.
106 ///
107 /// `Val1` and `Val2` must be assigned to the same storage location in
108 /// `Env1` and `Env2` respectively.
109 virtual void join(QualType Type, const Value &Val1, const Environment &Env1,
110 const Value &Val2, const Environment &Env2,
111 Value &JoinedVal, Environment &JoinedEnv) {}
112
113 /// This function may widen the current value -- replace it with an
114 /// approximation that can reach a fixed point more quickly than iterated
115 /// application of the transfer function alone. The previous value is
116 /// provided to inform the choice of widened value. The function must also
117 /// serve as a comparison operation, by indicating whether the widened value
118 /// is equivalent to the previous value.
119 ///
120 /// Returns one of the folowing:
121 /// * `std::nullopt`, if this value is not of interest to the
122 /// model.
123 /// * A `WidenResult` with:
124 /// * A non-null `Value *` that points either to `Current` or a widened
125 /// version of `Current`. This value must be consistent with
126 /// the flow condition of `CurrentEnv`. We particularly caution
127 /// against using `Prev`, which is rarely consistent.
128 /// * A `LatticeEffect` indicating whether the value should be
129 /// considered a new value (`Changed`) or one *equivalent* (if not
130 /// necessarily equal) to `Prev` (`Unchanged`).
131 ///
132 /// `PrevEnv` and `CurrentEnv` can be used to query child values and path
133 /// condition implications of `Prev` and `Current`, respectively.
134 ///
135 /// Requirements:
136 ///
137 /// `Prev` and `Current` must model values of type `Type`.
138 ///
139 /// `Prev` and `Current` must be assigned to the same storage location in
140 /// `PrevEnv` and `CurrentEnv`, respectively.
141 virtual std::optional<WidenResult> widen(QualType Type, Value &Prev,
142 const Environment &PrevEnv,
143 Value &Current,
144 Environment &CurrentEnv) {
145 // The default implementation reduces to just comparison, since comparison
146 // is required by the API, even if no widening is performed.
147 switch (compare(Type, Val1: Prev, Env1: PrevEnv, Val2: Current, Env2: CurrentEnv)) {
148 case ComparisonResult::Unknown:
149 return std::nullopt;
150 case ComparisonResult::Same:
151 return WidenResult{.V: &Current, .Effect: LatticeEffect::Unchanged};
152 case ComparisonResult::Different:
153 return WidenResult{.V: &Current, .Effect: LatticeEffect::Changed};
154 }
155 llvm_unreachable("all cases in switch covered");
156 }
157 };
158
159 /// Creates an environment that uses `DACtx` to store objects that encompass
160 /// the state of a program.
161 explicit Environment(DataflowAnalysisContext &DACtx)
162 : DACtx(&DACtx),
163 FlowConditionToken(DACtx.arena().makeFlowConditionToken()) {}
164
165 /// Creates an environment that uses `DACtx` to store objects that encompass
166 /// the state of a program, with `S` as the statement to analyze.
167 Environment(DataflowAnalysisContext &DACtx, Stmt &S) : Environment(DACtx) {
168 InitialTargetStmt = &S;
169 }
170
171 /// Creates an environment that uses `DACtx` to store objects that encompass
172 /// the state of a program, with `FD` as the function to analyze.
173 ///
174 /// Requirements:
175 ///
176 /// The function must have a body, i.e.
177 /// `FunctionDecl::doesThisDecalarationHaveABody()` must be true.
178 Environment(DataflowAnalysisContext &DACtx, const FunctionDecl &FD)
179 : Environment(DACtx, *FD.getBody()) {
180 assert(FD.doesThisDeclarationHaveABody());
181 InitialTargetFunc = &FD;
182 }
183
184 // Copy-constructor is private, Environments should not be copied. See fork().
185 Environment &operator=(const Environment &Other) = delete;
186
187 Environment(Environment &&Other) = default;
188 Environment &operator=(Environment &&Other) = default;
189
190 /// Assigns storage locations and values to all parameters, captures, global
191 /// variables, fields and functions referenced in the `Stmt` or `FunctionDecl`
192 /// passed to the constructor.
193 ///
194 /// If no `Stmt` or `FunctionDecl` was supplied, this function does nothing.
195 void initialize();
196
197 /// Returns a new environment that is a copy of this one.
198 ///
199 /// The state of the program is initially the same, but can be mutated without
200 /// affecting the original.
201 ///
202 /// However the original should not be further mutated, as this may interfere
203 /// with the fork. (In practice, values are stored independently, but the
204 /// forked flow condition references the original).
205 Environment fork() const;
206
207 /// Creates and returns an environment to use for an inline analysis of the
208 /// callee. Uses the storage location from each argument in the `Call` as the
209 /// storage location for the corresponding parameter in the callee.
210 ///
211 /// Requirements:
212 ///
213 /// The callee of `Call` must be a `FunctionDecl`.
214 ///
215 /// The body of the callee must not reference globals.
216 ///
217 /// The arguments of `Call` must map 1:1 to the callee's parameters.
218 Environment pushCall(const CallExpr *Call) const;
219 Environment pushCall(const CXXConstructExpr *Call) const;
220
221 /// Moves gathered information back into `this` from a `CalleeEnv` created via
222 /// `pushCall`.
223 void popCall(const CallExpr *Call, const Environment &CalleeEnv);
224 void popCall(const CXXConstructExpr *Call, const Environment &CalleeEnv);
225
226 /// Returns true if and only if the environment is equivalent to `Other`, i.e
227 /// the two environments:
228 /// - have the same mappings from declarations to storage locations,
229 /// - have the same mappings from expressions to storage locations,
230 /// - have the same or equivalent (according to `Model`) values assigned to
231 /// the same storage locations.
232 ///
233 /// Requirements:
234 ///
235 /// `Other` and `this` must use the same `DataflowAnalysisContext`.
236 bool equivalentTo(const Environment &Other,
237 Environment::ValueModel &Model) const;
238
239 /// How to treat expression state (`ExprToLoc` and `ExprToVal`) in a join.
240 /// If the join happens within a full expression, expression state should be
241 /// kept; otherwise, we can discard it.
242 enum ExprJoinBehavior {
243 DiscardExprState,
244 KeepExprState,
245 };
246
247 /// Joins two environments by taking the intersection of storage locations and
248 /// values that are stored in them. Distinct values that are assigned to the
249 /// same storage locations in `EnvA` and `EnvB` are merged using `Model`.
250 ///
251 /// Requirements:
252 ///
253 /// `EnvA` and `EnvB` must use the same `DataflowAnalysisContext`.
254 static Environment join(const Environment &EnvA, const Environment &EnvB,
255 Environment::ValueModel &Model,
256 ExprJoinBehavior ExprBehavior);
257
258 /// Returns a value that approximates both `Val1` and `Val2`, or null if no
259 /// such value can be produced.
260 ///
261 /// `Env1` and `Env2` can be used to query child values and path condition
262 /// implications of `Val1` and `Val2` respectively. The joined value will be
263 /// produced in `JoinedEnv`.
264 ///
265 /// Requirements:
266 ///
267 /// `Val1` and `Val2` must model values of type `Type`.
268 static Value *joinValues(QualType Ty, Value *Val1, const Environment &Env1,
269 Value *Val2, const Environment &Env2,
270 Environment &JoinedEnv,
271 Environment::ValueModel &Model);
272
273 /// Widens the environment point-wise, using `PrevEnv` as needed to inform the
274 /// approximation.
275 ///
276 /// Requirements:
277 ///
278 /// `PrevEnv` must be the immediate previous version of the environment.
279 /// `PrevEnv` and `this` must use the same `DataflowAnalysisContext`.
280 LatticeEffect widen(const Environment &PrevEnv,
281 Environment::ValueModel &Model);
282
283 // FIXME: Rename `createOrGetStorageLocation` to `getOrCreateStorageLocation`,
284 // `getStableStorageLocation`, or something more appropriate.
285
286 /// Creates a storage location appropriate for `Type`. Does not assign a value
287 /// to the returned storage location in the environment.
288 ///
289 /// Requirements:
290 ///
291 /// `Type` must not be null.
292 StorageLocation &createStorageLocation(QualType Type);
293
294 /// Creates a storage location for `D`. Does not assign the returned storage
295 /// location to `D` in the environment. Does not assign a value to the
296 /// returned storage location in the environment.
297 StorageLocation &createStorageLocation(const ValueDecl &D);
298
299 /// Creates a storage location for `E`. Does not assign the returned storage
300 /// location to `E` in the environment. Does not assign a value to the
301 /// returned storage location in the environment.
302 StorageLocation &createStorageLocation(const Expr &E);
303
304 /// Assigns `Loc` as the storage location of `D` in the environment.
305 ///
306 /// Requirements:
307 ///
308 /// `D` must not already have a storage location in the environment.
309 void setStorageLocation(const ValueDecl &D, StorageLocation &Loc);
310
311 /// Returns the storage location assigned to `D` in the environment, or null
312 /// if `D` isn't assigned a storage location in the environment.
313 StorageLocation *getStorageLocation(const ValueDecl &D) const;
314
315 /// Removes the location assigned to `D` in the environment (if any).
316 void removeDecl(const ValueDecl &D);
317
318 /// Assigns `Loc` as the storage location of the glvalue `E` in the
319 /// environment.
320 ///
321 /// Requirements:
322 ///
323 /// `E` must not be assigned a storage location in the environment.
324 /// `E` must be a glvalue or a `BuiltinType::BuiltinFn`
325 void setStorageLocation(const Expr &E, StorageLocation &Loc);
326
327 /// Returns the storage location assigned to the glvalue `E` in the
328 /// environment, or null if `E` isn't assigned a storage location in the
329 /// environment.
330 ///
331 /// Requirements:
332 /// `E` must be a glvalue or a `BuiltinType::BuiltinFn`
333 StorageLocation *getStorageLocation(const Expr &E) const;
334
335 /// Returns the result of casting `getStorageLocation(...)` to a subclass of
336 /// `StorageLocation` (using `cast_or_null<T>`).
337 /// This assert-fails if the result of `getStorageLocation(...)` is not of
338 /// type `T *`; if the storage location is not guaranteed to have type `T *`,
339 /// consider using `dyn_cast_or_null<T>(getStorageLocation(...))` instead.
340 template <typename T>
341 std::enable_if_t<std::is_base_of_v<StorageLocation, T>, T *>
342 get(const ValueDecl &D) const {
343 return cast_or_null<T>(getStorageLocation(D));
344 }
345 template <typename T>
346 std::enable_if_t<std::is_base_of_v<StorageLocation, T>, T *>
347 get(const Expr &E) const {
348 return cast_or_null<T>(getStorageLocation(E));
349 }
350
351 /// Returns the storage location assigned to the `this` pointee in the
352 /// environment or null if the `this` pointee has no assigned storage location
353 /// in the environment.
354 RecordStorageLocation *getThisPointeeStorageLocation() const {
355 return ThisPointeeLoc;
356 }
357
358 /// Sets the storage location assigned to the `this` pointee in the
359 /// environment.
360 void setThisPointeeStorageLocation(RecordStorageLocation &Loc) {
361 ThisPointeeLoc = &Loc;
362 }
363
364 /// Returns the location of the result object for a record-type prvalue.
365 ///
366 /// In C++, prvalues of record type serve only a limited purpose: They can
367 /// only be used to initialize a result object (e.g. a variable or a
368 /// temporary). This function returns the location of that result object.
369 ///
370 /// When creating a prvalue of record type, we already need the storage
371 /// location of the result object to pass in `this`, even though prvalues are
372 /// otherwise not associated with storage locations.
373 ///
374 /// Requirements:
375 /// `E` must be a prvalue of record type.
376 RecordStorageLocation &
377 getResultObjectLocation(const Expr &RecordPRValue) const;
378
379 /// Returns the return value of the function currently being analyzed.
380 /// This can be null if:
381 /// - The function has a void return type
382 /// - No return value could be determined for the function, for example
383 /// because it calls a function without a body.
384 ///
385 /// Requirements:
386 /// The current analysis target must be a function and must have a
387 /// non-reference return type.
388 Value *getReturnValue() const {
389 assert(getCurrentFunc() != nullptr &&
390 !getCurrentFunc()->getReturnType()->isReferenceType());
391 return ReturnVal;
392 }
393
394 /// Returns the storage location for the reference returned by the function
395 /// currently being analyzed. This can be null if the function doesn't return
396 /// a single consistent reference.
397 ///
398 /// Requirements:
399 /// The current analysis target must be a function and must have a reference
400 /// return type.
401 StorageLocation *getReturnStorageLocation() const {
402 assert(getCurrentFunc() != nullptr &&
403 getCurrentFunc()->getReturnType()->isReferenceType());
404 return ReturnLoc;
405 }
406
407 /// Sets the return value of the function currently being analyzed.
408 ///
409 /// Requirements:
410 /// The current analysis target must be a function and must have a
411 /// non-reference return type.
412 void setReturnValue(Value *Val) {
413 assert(getCurrentFunc() != nullptr &&
414 !getCurrentFunc()->getReturnType()->isReferenceType());
415 ReturnVal = Val;
416 }
417
418 /// Sets the storage location for the reference returned by the function
419 /// currently being analyzed.
420 ///
421 /// Requirements:
422 /// The current analysis target must be a function and must have a reference
423 /// return type.
424 void setReturnStorageLocation(StorageLocation *Loc) {
425 assert(getCurrentFunc() != nullptr &&
426 getCurrentFunc()->getReturnType()->isReferenceType());
427 ReturnLoc = Loc;
428 }
429
430 /// Returns a pointer value that represents a null pointer. Calls with
431 /// `PointeeType` that are canonically equivalent will return the same result.
432 PointerValue &getOrCreateNullPointerValue(QualType PointeeType);
433
434 /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise
435 /// returns null.
436 ///
437 /// If `Type` is a pointer or reference type, creates all the necessary
438 /// storage locations and values for indirections until it finds a
439 /// non-pointer/non-reference type.
440 ///
441 /// If `Type` is one of the following types, this function will always return
442 /// a non-null pointer:
443 /// - `bool`
444 /// - Any integer type
445 ///
446 /// Requirements:
447 ///
448 /// - `Type` must not be null.
449 /// - `Type` must not be a reference type or record type.
450 Value *createValue(QualType Type);
451
452 /// Creates an object (i.e. a storage location with an associated value) of
453 /// type `Ty`. If `InitExpr` is non-null and has a value associated with it,
454 /// initializes the object with this value. Otherwise, initializes the object
455 /// with a value created using `createValue()`.
456 StorageLocation &createObject(QualType Ty, const Expr *InitExpr = nullptr) {
457 return createObjectInternal(D: nullptr, Ty, InitExpr);
458 }
459
460 /// Creates an object for the variable declaration `D`. If `D` has an
461 /// initializer and this initializer is associated with a value, initializes
462 /// the object with this value. Otherwise, initializes the object with a
463 /// value created using `createValue()`. Uses the storage location returned by
464 /// `DataflowAnalysisContext::getStableStorageLocation(D)`.
465 StorageLocation &createObject(const VarDecl &D) {
466 return createObjectInternal(D: &D, Ty: D.getType(), InitExpr: D.getInit());
467 }
468
469 /// Creates an object for the variable declaration `D`. If `InitExpr` is
470 /// non-null and has a value associated with it, initializes the object with
471 /// this value. Otherwise, initializes the object with a value created using
472 /// `createValue()`. Uses the storage location returned by
473 /// `DataflowAnalysisContext::getStableStorageLocation(D)`.
474 StorageLocation &createObject(const ValueDecl &D, const Expr *InitExpr) {
475 return createObjectInternal(D: &D, Ty: D.getType(), InitExpr);
476 }
477
478 /// Initializes the fields (including synthetic fields) of `Loc` with values,
479 /// unless values of the field type are not supported or we hit one of the
480 /// limits at which we stop producing values.
481 /// If a field already has a value, that value is preserved.
482 /// If `Type` is provided, initializes only those fields that are modeled for
483 /// `Type`; this is intended for use in cases where `Loc` is a derived type
484 /// and we only want to initialize the fields of a base type.
485 void initializeFieldsWithValues(RecordStorageLocation &Loc, QualType Type);
486 void initializeFieldsWithValues(RecordStorageLocation &Loc) {
487 initializeFieldsWithValues(Loc, Loc.getType());
488 }
489
490 /// Assigns `Val` as the value of `Loc` in the environment.
491 ///
492 /// Requirements:
493 ///
494 /// `Loc` must not be a `RecordStorageLocation`.
495 void setValue(const StorageLocation &Loc, Value &Val);
496
497 /// Clears any association between `Loc` and a value in the environment.
498 void clearValue(const StorageLocation &Loc) { LocToVal.erase(Key: &Loc); }
499
500 /// Assigns `Val` as the value of the prvalue `E` in the environment.
501 ///
502 /// Requirements:
503 ///
504 /// - `E` must be a prvalue.
505 /// - `E` must not have record type.
506 void setValue(const Expr &E, Value &Val);
507
508 /// Returns the value assigned to `Loc` in the environment or null if `Loc`
509 /// isn't assigned a value in the environment.
510 ///
511 /// Requirements:
512 ///
513 /// `Loc` must not be a `RecordStorageLocation`.
514 Value *getValue(const StorageLocation &Loc) const;
515
516 /// Equivalent to `getValue(getStorageLocation(D))` if `D` is assigned a
517 /// storage location in the environment, otherwise returns null.
518 ///
519 /// Requirements:
520 ///
521 /// `D` must not have record type.
522 Value *getValue(const ValueDecl &D) const;
523
524 /// Equivalent to `getValue(getStorageLocation(E, SP))` if `E` is assigned a
525 /// storage location in the environment, otherwise returns null.
526 Value *getValue(const Expr &E) const;
527
528 /// Returns the result of casting `getValue(...)` to a subclass of `Value`
529 /// (using `cast_or_null<T>`).
530 /// This assert-fails if the result of `getValue(...)` is not of type `T *`;
531 /// if the value is not guaranteed to have type `T *`, consider using
532 /// `dyn_cast_or_null<T>(getValue(...))` instead.
533 template <typename T>
534 std::enable_if_t<std::is_base_of_v<Value, T>, T *>
535 get(const StorageLocation &Loc) const {
536 return cast_or_null<T>(getValue(Loc));
537 }
538 template <typename T>
539 std::enable_if_t<std::is_base_of_v<Value, T>, T *>
540 get(const ValueDecl &D) const {
541 return cast_or_null<T>(getValue(D));
542 }
543 template <typename T>
544 std::enable_if_t<std::is_base_of_v<Value, T>, T *> get(const Expr &E) const {
545 return cast_or_null<T>(getValue(E));
546 }
547
548 // FIXME: should we deprecate the following & call arena().create() directly?
549
550 /// Creates a `T` (some subclass of `Value`), forwarding `args` to the
551 /// constructor, and returns a reference to it.
552 ///
553 /// The analysis context takes ownership of the created object. The object
554 /// will be destroyed when the analysis context is destroyed.
555 template <typename T, typename... Args>
556 std::enable_if_t<std::is_base_of<Value, T>::value, T &>
557 create(Args &&...args) {
558 return arena().create<T>(std::forward<Args>(args)...);
559 }
560
561 /// Returns a symbolic integer value that models an integer literal equal to
562 /// `Value`
563 IntegerValue &getIntLiteralValue(llvm::APInt Value) const {
564 return arena().makeIntLiteral(Value);
565 }
566
567 /// Returns a symbolic boolean value that models a boolean literal equal to
568 /// `Value`
569 BoolValue &getBoolLiteralValue(bool Value) const {
570 return arena().makeBoolValue(arena().makeLiteral(Value));
571 }
572
573 /// Returns an atomic boolean value.
574 BoolValue &makeAtomicBoolValue() const {
575 return arena().makeAtomValue();
576 }
577
578 /// Returns a unique instance of boolean Top.
579 BoolValue &makeTopBoolValue() const {
580 return arena().makeTopValue();
581 }
582
583 /// Returns a boolean value that represents the conjunction of `LHS` and
584 /// `RHS`. Subsequent calls with the same arguments, regardless of their
585 /// order, will return the same result. If the given boolean values represent
586 /// the same value, the result will be the value itself.
587 BoolValue &makeAnd(BoolValue &LHS, BoolValue &RHS) const {
588 return arena().makeBoolValue(
589 arena().makeAnd(LHS: LHS.formula(), RHS: RHS.formula()));
590 }
591
592 /// Returns a boolean value that represents the disjunction of `LHS` and
593 /// `RHS`. Subsequent calls with the same arguments, regardless of their
594 /// order, will return the same result. If the given boolean values represent
595 /// the same value, the result will be the value itself.
596 BoolValue &makeOr(BoolValue &LHS, BoolValue &RHS) const {
597 return arena().makeBoolValue(
598 arena().makeOr(LHS: LHS.formula(), RHS: RHS.formula()));
599 }
600
601 /// Returns a boolean value that represents the negation of `Val`. Subsequent
602 /// calls with the same argument will return the same result.
603 BoolValue &makeNot(BoolValue &Val) const {
604 return arena().makeBoolValue(arena().makeNot(Val: Val.formula()));
605 }
606
607 /// Returns a boolean value represents `LHS` => `RHS`. Subsequent calls with
608 /// the same arguments, will return the same result. If the given boolean
609 /// values represent the same value, the result will be a value that
610 /// represents the true boolean literal.
611 BoolValue &makeImplication(BoolValue &LHS, BoolValue &RHS) const {
612 return arena().makeBoolValue(
613 arena().makeImplies(LHS: LHS.formula(), RHS: RHS.formula()));
614 }
615
616 /// Returns a boolean value represents `LHS` <=> `RHS`. Subsequent calls with
617 /// the same arguments, regardless of their order, will return the same
618 /// result. If the given boolean values represent the same value, the result
619 /// will be a value that represents the true boolean literal.
620 BoolValue &makeIff(BoolValue &LHS, BoolValue &RHS) const {
621 return arena().makeBoolValue(
622 arena().makeEquals(LHS: LHS.formula(), RHS: RHS.formula()));
623 }
624
625 /// Returns a boolean variable that identifies the flow condition (FC).
626 ///
627 /// The flow condition is a set of facts that are necessarily true when the
628 /// program reaches the current point, expressed as boolean formulas.
629 /// The flow condition token is equivalent to the AND of these facts.
630 ///
631 /// These may e.g. constrain the value of certain variables. A pointer
632 /// variable may have a consistent modeled PointerValue throughout, but at a
633 /// given point the Environment may tell us that the value must be non-null.
634 ///
635 /// The FC is necessary but not sufficient for this point to be reachable.
636 /// In particular, where the FC token appears in flow conditions of successor
637 /// environments, it means "point X may have been reached", not
638 /// "point X was reached".
639 Atom getFlowConditionToken() const { return FlowConditionToken; }
640
641 /// Record a fact that must be true if this point in the program is reached.
642 void assume(const Formula &);
643
644 /// Returns true if the formula is always true when this point is reached.
645 /// Returns false if the formula may be false (or the flow condition isn't
646 /// sufficiently precise to prove that it is true) or if the solver times out.
647 ///
648 /// Note that there is an asymmetry between this function and `allows()` in
649 /// that they both return false if the solver times out. The assumption is
650 /// that if `proves()` or `allows()` returns true, this will result in a
651 /// diagnostic, and we want to bias towards false negatives in the case where
652 /// the solver times out.
653 bool proves(const Formula &) const;
654
655 /// Returns true if the formula may be true when this point is reached.
656 /// Returns false if the formula is always false when this point is reached
657 /// (or the flow condition is overly constraining) or if the solver times out.
658 bool allows(const Formula &) const;
659
660 /// Returns the function currently being analyzed, or null if the code being
661 /// analyzed isn't part of a function.
662 const FunctionDecl *getCurrentFunc() const {
663 return CallStack.empty() ? InitialTargetFunc : CallStack.back();
664 }
665
666 /// Returns the size of the call stack, not counting the initial analysis
667 /// target.
668 size_t callStackSize() const { return CallStack.size(); }
669
670 /// Returns whether this `Environment` can be extended to analyze the given
671 /// `Callee` (i.e. if `pushCall` can be used).
672 /// Recursion is not allowed. `MaxDepth` is the maximum size of the call stack
673 /// (i.e. the maximum value that `callStackSize()` may assume after the call).
674 bool canDescend(unsigned MaxDepth, const FunctionDecl *Callee) const;
675
676 /// Returns the `DataflowAnalysisContext` used by the environment.
677 DataflowAnalysisContext &getDataflowAnalysisContext() const { return *DACtx; }
678
679 Arena &arena() const { return DACtx->arena(); }
680
681 LLVM_DUMP_METHOD void dump() const;
682 LLVM_DUMP_METHOD void dump(raw_ostream &OS) const;
683
684private:
685 using PrValueToResultObject =
686 llvm::DenseMap<const Expr *, RecordStorageLocation *>;
687
688 // The copy-constructor is for use in fork() only.
689 Environment(const Environment &) = default;
690
691 /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise
692 /// return null.
693 ///
694 /// Recursively initializes storage locations and values until it sees a
695 /// self-referential pointer or reference type. `Visited` is used to track
696 /// which types appeared in the reference/pointer chain in order to avoid
697 /// creating a cyclic dependency with self-referential pointers/references.
698 ///
699 /// Requirements:
700 ///
701 /// `Type` must not be null.
702 Value *createValueUnlessSelfReferential(QualType Type,
703 llvm::DenseSet<QualType> &Visited,
704 int Depth, int &CreatedValuesCount);
705
706 /// Creates a storage location for `Ty`. Also creates and associates a value
707 /// with the storage location, unless values of this type are not supported or
708 /// we hit one of the limits at which we stop producing values (controlled by
709 /// `Visited`, `Depth`, and `CreatedValuesCount`).
710 StorageLocation &createLocAndMaybeValue(QualType Ty,
711 llvm::DenseSet<QualType> &Visited,
712 int Depth, int &CreatedValuesCount);
713
714 /// Initializes the fields (including synthetic fields) of `Loc` with values,
715 /// unless values of the field type are not supported or we hit one of the
716 /// limits at which we stop producing values (controlled by `Visited`,
717 /// `Depth`, and `CreatedValuesCount`). If `Type` is different from
718 /// `Loc.getType()`, initializes only those fields that are modeled for
719 /// `Type`.
720 void initializeFieldsWithValues(RecordStorageLocation &Loc, QualType Type,
721 llvm::DenseSet<QualType> &Visited, int Depth,
722 int &CreatedValuesCount);
723
724 /// Shared implementation of `createObject()` overloads.
725 /// `D` and `InitExpr` may be null.
726 StorageLocation &createObjectInternal(const ValueDecl *D, QualType Ty,
727 const Expr *InitExpr);
728
729 /// Shared implementation of `pushCall` overloads. Note that unlike
730 /// `pushCall`, this member is invoked on the environment of the callee, not
731 /// of the caller.
732 void pushCallInternal(const FunctionDecl *FuncDecl,
733 ArrayRef<const Expr *> Args);
734
735 /// Assigns storage locations and values to all global variables, fields
736 /// and functions in `Referenced`.
737 void initFieldsGlobalsAndFuncs(const ReferencedDecls &Referenced);
738
739 static PrValueToResultObject
740 buildResultObjectMap(DataflowAnalysisContext *DACtx,
741 const FunctionDecl *FuncDecl,
742 RecordStorageLocation *ThisPointeeLoc,
743 RecordStorageLocation *LocForRecordReturnVal);
744
745 static PrValueToResultObject
746 buildResultObjectMap(DataflowAnalysisContext *DACtx, Stmt *S,
747 RecordStorageLocation *ThisPointeeLoc,
748 RecordStorageLocation *LocForRecordReturnVal);
749
750 // `DACtx` is not null and not owned by this object.
751 DataflowAnalysisContext *DACtx;
752
753 // FIXME: move the fields `CallStack`, `ResultObjectMap`, `ReturnVal`,
754 // `ReturnLoc` and `ThisPointeeLoc` into a separate call-context object,
755 // shared between environments in the same call.
756 // https://github.com/llvm/llvm-project/issues/59005
757
758 // The stack of functions called from the initial analysis target.
759 std::vector<const FunctionDecl *> CallStack;
760
761 // Initial function to analyze, if a function was passed to the constructor.
762 // Null otherwise.
763 const FunctionDecl *InitialTargetFunc = nullptr;
764 // Top-level statement of the initial analysis target.
765 // If a function was passed to the constructor, this is its body.
766 // If a statement was passed to the constructor, this is that statement.
767 // Null if no analysis target was passed to the constructor.
768 Stmt *InitialTargetStmt = nullptr;
769
770 // Maps from prvalues of record type to their result objects. Shared between
771 // all environments for the same analysis target.
772 // FIXME: It's somewhat unsatisfactory that we have to use a `shared_ptr`
773 // here, though the cost is acceptable: The overhead of a `shared_ptr` is
774 // incurred when it is copied, and this happens only relatively rarely (when
775 // we fork the environment). The need for a `shared_ptr` will go away once we
776 // introduce a shared call-context object (see above).
777 std::shared_ptr<PrValueToResultObject> ResultObjectMap;
778
779 // The following three member variables handle various different types of
780 // return values when the current analysis target is a function.
781 // - If the return type is not a reference and not a record: Value returned
782 // by the function.
783 Value *ReturnVal = nullptr;
784 // - If the return type is a reference: Storage location of the reference
785 // returned by the function.
786 StorageLocation *ReturnLoc = nullptr;
787 // - If the return type is a record or the function being analyzed is a
788 // constructor: Storage location into which the return value should be
789 // constructed.
790 RecordStorageLocation *LocForRecordReturnVal = nullptr;
791
792 // The storage location of the `this` pointee. Should only be null if the
793 // analysis target is not a method.
794 RecordStorageLocation *ThisPointeeLoc = nullptr;
795
796 // Maps from declarations and glvalue expression to storage locations that are
797 // assigned to them. Unlike the maps in `DataflowAnalysisContext`, these
798 // include only storage locations that are in scope for a particular basic
799 // block.
800 llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc;
801 llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc;
802 // Maps from prvalue expressions and storage locations to the values that
803 // are assigned to them.
804 // We preserve insertion order so that join/widen process values in
805 // deterministic sequence. This in turn produces deterministic SAT formulas.
806 llvm::MapVector<const Expr *, Value *> ExprToVal;
807 llvm::MapVector<const StorageLocation *, Value *> LocToVal;
808
809 Atom FlowConditionToken;
810};
811
812/// Returns the storage location for the implicit object of a
813/// `CXXMemberCallExpr`, or null if none is defined in the environment.
814/// Dereferences the pointer if the member call expression was written using
815/// `->`.
816RecordStorageLocation *getImplicitObjectLocation(const CXXMemberCallExpr &MCE,
817 const Environment &Env);
818
819/// Returns the storage location for the base object of a `MemberExpr`, or null
820/// if none is defined in the environment. Dereferences the pointer if the
821/// member expression was written using `->`.
822RecordStorageLocation *getBaseObjectLocation(const MemberExpr &ME,
823 const Environment &Env);
824
825} // namespace dataflow
826} // namespace clang
827
828#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H
829

source code of clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h