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

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