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