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