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