| //===-- DataflowEnvironment.h -----------------------------------*- C++ -*-===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file defines an Environment class that is used by dataflow analyses |
| // that run over Control-Flow Graphs (CFGs) to keep track of the state of the |
| // program at given program points. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H |
| #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H |
| |
| #include "clang/AST/Decl.h" |
| #include "clang/AST/DeclBase.h" |
| #include "clang/AST/Expr.h" |
| #include "clang/AST/Type.h" |
| #include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h" |
| #include "clang/Analysis/FlowSensitive/DataflowLattice.h" |
| #include "clang/Analysis/FlowSensitive/Formula.h" |
| #include "clang/Analysis/FlowSensitive/Logger.h" |
| #include "clang/Analysis/FlowSensitive/StorageLocation.h" |
| #include "clang/Analysis/FlowSensitive/Value.h" |
| #include "llvm/ADT/DenseMap.h" |
| #include "llvm/ADT/DenseSet.h" |
| #include "llvm/ADT/MapVector.h" |
| #include "llvm/Support/Compiler.h" |
| #include "llvm/Support/ErrorHandling.h" |
| #include <memory> |
| #include <type_traits> |
| #include <utility> |
| |
| namespace clang { |
| namespace dataflow { |
| |
| /// Indicates the result of a tentative comparison. |
| enum class ComparisonResult { |
| Same, |
| Different, |
| Unknown, |
| }; |
| |
| /// The result of a `widen` operation. |
| struct WidenResult { |
| /// Non-null pointer to a potentially widened version of the input value. |
| Value *V; |
| /// Whether `V` represents a "change" (that is, a different value) with |
| /// respect to the previous value in the sequence. |
| LatticeEffect Effect; |
| }; |
| |
| /// Holds the state of the program (store and heap) at a given program point. |
| /// |
| /// WARNING: Symbolic values that are created by the environment for static |
| /// local and global variables are not currently invalidated on function calls. |
| /// This is unsound and should be taken into account when designing dataflow |
| /// analyses. |
| class Environment { |
| public: |
| /// Supplements `Environment` with non-standard comparison and join |
| /// operations. |
| class ValueModel { |
| public: |
| virtual ~ValueModel() = default; |
| |
| /// Returns: |
| /// `Same`: `Val1` is equivalent to `Val2`, according to the model. |
| /// `Different`: `Val1` is distinct from `Val2`, according to the model. |
| /// `Unknown`: The model can't determine a relationship between `Val1` and |
| /// `Val2`. |
| /// |
| /// Requirements: |
| /// |
| /// `Val1` and `Val2` must be distinct. |
| /// |
| /// `Val1` and `Val2` must model values of type `Type`. |
| /// |
| /// `Val1` and `Val2` must be assigned to the same storage location in |
| /// `Env1` and `Env2` respectively. |
| virtual ComparisonResult compare(QualType Type, const Value &Val1, |
| const Environment &Env1, const Value &Val2, |
| const Environment &Env2) { |
| // FIXME: Consider adding `QualType` to `Value` and removing the `Type` |
| // argument here. |
| return ComparisonResult::Unknown; |
| } |
| |
| /// Modifies `JoinedVal` to approximate both `Val1` and `Val2`. This should |
| /// obey the properties of a lattice join. |
| /// |
| /// `Env1` and `Env2` can be used to query child values and path condition |
| /// implications of `Val1` and `Val2` respectively. |
| /// |
| /// Requirements: |
| /// |
| /// `Val1` and `Val2` must be distinct. |
| /// |
| /// `Val1`, `Val2`, and `JoinedVal` must model values of type `Type`. |
| /// |
| /// `Val1` and `Val2` must be assigned to the same storage location in |
| /// `Env1` and `Env2` respectively. |
| virtual void join(QualType Type, const Value &Val1, const Environment &Env1, |
| const Value &Val2, const Environment &Env2, |
| Value &JoinedVal, Environment &JoinedEnv) {} |
| |
| /// This function may widen the current value -- replace it with an |
| /// approximation that can reach a fixed point more quickly than iterated |
| /// application of the transfer function alone. The previous value is |
| /// provided to inform the choice of widened value. The function must also |
| /// serve as a comparison operation, by indicating whether the widened value |
| /// is equivalent to the previous value. |
| /// |
| /// Returns one of the folowing: |
| /// * `std::nullopt`, if this value is not of interest to the |
| /// model. |
| /// * A `WidenResult` with: |
| /// * A non-null `Value *` that points either to `Current` or a widened |
| /// version of `Current`. This value must be consistent with |
| /// the flow condition of `CurrentEnv`. We particularly caution |
| /// against using `Prev`, which is rarely consistent. |
| /// * A `LatticeEffect` indicating whether the value should be |
| /// considered a new value (`Changed`) or one *equivalent* (if not |
| /// necessarily equal) to `Prev` (`Unchanged`). |
| /// |
| /// `PrevEnv` and `CurrentEnv` can be used to query child values and path |
| /// condition implications of `Prev` and `Current`, respectively. |
| /// |
| /// Requirements: |
| /// |
| /// `Prev` and `Current` must model values of type `Type`. |
| /// |
| /// `Prev` and `Current` must be assigned to the same storage location in |
| /// `PrevEnv` and `CurrentEnv`, respectively. |
| virtual std::optional<WidenResult> widen(QualType Type, Value &Prev, |
| const Environment &PrevEnv, |
| Value &Current, |
| Environment &CurrentEnv) { |
| // The default implementation reduces to just comparison, since comparison |
| // is required by the API, even if no widening is performed. |
| switch (compare(Type, Prev, PrevEnv, Current, CurrentEnv)) { |
| case ComparisonResult::Unknown: |
| return std::nullopt; |
| case ComparisonResult::Same: |
| return WidenResult{&Current, LatticeEffect::Unchanged}; |
| case ComparisonResult::Different: |
| return WidenResult{&Current, LatticeEffect::Changed}; |
| } |
| llvm_unreachable("all cases in switch covered"); |
| } |
| }; |
| |
| /// Creates an environment that uses `DACtx` to store objects that encompass |
| /// the state of a program. |
| explicit Environment(DataflowAnalysisContext &DACtx); |
| |
| // Copy-constructor is private, Environments should not be copied. See fork(). |
| Environment &operator=(const Environment &Other) = delete; |
| |
| Environment(Environment &&Other) = default; |
| Environment &operator=(Environment &&Other) = default; |
| |
| /// Creates an environment that uses `DACtx` to store objects that encompass |
| /// the state of a program. |
| /// |
| /// If `DeclCtx` is a function, initializes the environment with symbolic |
| /// representations of the function parameters. |
| /// |
| /// If `DeclCtx` is a non-static member function, initializes the environment |
| /// with a symbolic representation of the `this` pointee. |
| Environment(DataflowAnalysisContext &DACtx, const DeclContext &DeclCtx); |
| |
| /// Assigns storage locations and values to all parameters, captures, global |
| /// variables, fields and functions referenced in the function currently being |
| /// analyzed. |
| /// |
| /// Requirements: |
| /// |
| /// The function must have a body, i.e. |
| /// `FunctionDecl::doesThisDecalarationHaveABody()` must be true. |
| void initialize(); |
| |
| /// Returns a new environment that is a copy of this one. |
| /// |
| /// The state of the program is initially the same, but can be mutated without |
| /// affecting the original. |
| /// |
| /// However the original should not be further mutated, as this may interfere |
| /// with the fork. (In practice, values are stored independently, but the |
| /// forked flow condition references the original). |
| Environment fork() const; |
| |
| /// Creates and returns an environment to use for an inline analysis of the |
| /// callee. Uses the storage location from each argument in the `Call` as the |
| /// storage location for the corresponding parameter in the callee. |
| /// |
| /// Requirements: |
| /// |
| /// The callee of `Call` must be a `FunctionDecl`. |
| /// |
| /// The body of the callee must not reference globals. |
| /// |
| /// The arguments of `Call` must map 1:1 to the callee's parameters. |
| Environment pushCall(const CallExpr *Call) const; |
| Environment pushCall(const CXXConstructExpr *Call) const; |
| |
| /// Moves gathered information back into `this` from a `CalleeEnv` created via |
| /// `pushCall`. |
| void popCall(const CallExpr *Call, const Environment &CalleeEnv); |
| void popCall(const CXXConstructExpr *Call, const Environment &CalleeEnv); |
| |
| /// Returns true if and only if the environment is equivalent to `Other`, i.e |
| /// the two environments: |
| /// - have the same mappings from declarations to storage locations, |
| /// - have the same mappings from expressions to storage locations, |
| /// - have the same or equivalent (according to `Model`) values assigned to |
| /// the same storage locations. |
| /// |
| /// Requirements: |
| /// |
| /// `Other` and `this` must use the same `DataflowAnalysisContext`. |
| bool equivalentTo(const Environment &Other, |
| Environment::ValueModel &Model) const; |
| |
| /// How to treat expression state (`ExprToLoc` and `ExprToVal`) in a join. |
| /// If the join happens within a full expression, expression state should be |
| /// kept; otherwise, we can discard it. |
| enum ExprJoinBehavior { |
| DiscardExprState, |
| KeepExprState, |
| }; |
| |
| /// Joins two environments by taking the intersection of storage locations and |
| /// values that are stored in them. Distinct values that are assigned to the |
| /// same storage locations in `EnvA` and `EnvB` are merged using `Model`. |
| /// |
| /// Requirements: |
| /// |
| /// `EnvA` and `EnvB` must use the same `DataflowAnalysisContext`. |
| static Environment join(const Environment &EnvA, const Environment &EnvB, |
| Environment::ValueModel &Model, |
| ExprJoinBehavior ExprBehavior); |
| |
| /// Returns a value that approximates both `Val1` and `Val2`, or null if no |
| /// such value can be produced. |
| /// |
| /// `Env1` and `Env2` can be used to query child values and path condition |
| /// implications of `Val1` and `Val2` respectively. The joined value will be |
| /// produced in `JoinedEnv`. |
| /// |
| /// Requirements: |
| /// |
| /// `Val1` and `Val2` must model values of type `Type`. |
| static Value *joinValues(QualType Ty, Value *Val1, const Environment &Env1, |
| Value *Val2, const Environment &Env2, |
| Environment &JoinedEnv, |
| Environment::ValueModel &Model); |
| |
| /// Widens the environment point-wise, using `PrevEnv` as needed to inform the |
| /// approximation. |
| /// |
| /// Requirements: |
| /// |
| /// `PrevEnv` must be the immediate previous version of the environment. |
| /// `PrevEnv` and `this` must use the same `DataflowAnalysisContext`. |
| LatticeEffect widen(const Environment &PrevEnv, |
| Environment::ValueModel &Model); |
| |
| // FIXME: Rename `createOrGetStorageLocation` to `getOrCreateStorageLocation`, |
| // `getStableStorageLocation`, or something more appropriate. |
| |
| /// Creates a storage location appropriate for `Type`. Does not assign a value |
| /// to the returned storage location in the environment. |
| /// |
| /// Requirements: |
| /// |
| /// `Type` must not be null. |
| StorageLocation &createStorageLocation(QualType Type); |
| |
| /// Creates a storage location for `D`. Does not assign the returned storage |
| /// location to `D` in the environment. Does not assign a value to the |
| /// returned storage location in the environment. |
| StorageLocation &createStorageLocation(const ValueDecl &D); |
| |
| /// Creates a storage location for `E`. Does not assign the returned storage |
| /// location to `E` in the environment. Does not assign a value to the |
| /// returned storage location in the environment. |
| StorageLocation &createStorageLocation(const Expr &E); |
| |
| /// Assigns `Loc` as the storage location of `D` in the environment. |
| /// |
| /// Requirements: |
| /// |
| /// `D` must not already have a storage location in the environment. |
| void setStorageLocation(const ValueDecl &D, StorageLocation &Loc); |
| |
| /// Returns the storage location assigned to `D` in the environment, or null |
| /// if `D` isn't assigned a storage location in the environment. |
| StorageLocation *getStorageLocation(const ValueDecl &D) const; |
| |
| /// Removes the location assigned to `D` in the environment (if any). |
| void removeDecl(const ValueDecl &D); |
| |
| /// Assigns `Loc` as the storage location of the glvalue `E` in the |
| /// environment. |
| /// |
| /// Requirements: |
| /// |
| /// `E` must not be assigned a storage location in the environment. |
| /// `E` must be a glvalue or a `BuiltinType::BuiltinFn` |
| void setStorageLocation(const Expr &E, StorageLocation &Loc); |
| |
| /// Returns the storage location assigned to the glvalue `E` in the |
| /// environment, or null if `E` isn't assigned a storage location in the |
| /// environment. |
| /// |
| /// Requirements: |
| /// `E` must be a glvalue or a `BuiltinType::BuiltinFn` |
| StorageLocation *getStorageLocation(const Expr &E) const; |
| |
| /// Returns the result of casting `getStorageLocation(...)` to a subclass of |
| /// `StorageLocation` (using `cast_or_null<T>`). |
| /// This assert-fails if the result of `getStorageLocation(...)` is not of |
| /// type `T *`; if the storage location is not guaranteed to have type `T *`, |
| /// consider using `dyn_cast_or_null<T>(getStorageLocation(...))` instead. |
| template <typename T> |
| std::enable_if_t<std::is_base_of_v<StorageLocation, T>, T *> |
| get(const ValueDecl &D) const { |
| return cast_or_null<T>(getStorageLocation(D)); |
| } |
| template <typename T> |
| std::enable_if_t<std::is_base_of_v<StorageLocation, T>, T *> |
| get(const Expr &E) const { |
| return cast_or_null<T>(getStorageLocation(E)); |
| } |
| |
| /// Returns the storage location assigned to the `this` pointee in the |
| /// environment or null if the `this` pointee has no assigned storage location |
| /// in the environment. |
| RecordStorageLocation *getThisPointeeStorageLocation() const { |
| return ThisPointeeLoc; |
| } |
| |
| /// Sets the storage location assigned to the `this` pointee in the |
| /// environment. |
| void setThisPointeeStorageLocation(RecordStorageLocation &Loc) { |
| ThisPointeeLoc = &Loc; |
| } |
| |
| /// Returns the location of the result object for a record-type prvalue. |
| /// |
| /// In C++, prvalues of record type serve only a limited purpose: They can |
| /// only be used to initialize a result object (e.g. a variable or a |
| /// temporary). This function returns the location of that result object. |
| /// |
| /// When creating a prvalue of record type, we already need the storage |
| /// location of the result object to pass in `this`, even though prvalues are |
| /// otherwise not associated with storage locations. |
| /// |
| /// Requirements: |
| /// `E` must be a prvalue of record type. |
| RecordStorageLocation & |
| getResultObjectLocation(const Expr &RecordPRValue) const; |
| |
| /// Returns the return value of the current function. This can be null if: |
| /// - The function has a void return type |
| /// - No return value could be determined for the function, for example |
| /// because it calls a function without a body. |
| /// |
| /// Requirements: |
| /// The current function must have a non-reference return type. |
| Value *getReturnValue() const { |
| assert(getCurrentFunc() != nullptr && |
| !getCurrentFunc()->getReturnType()->isReferenceType()); |
| return ReturnVal; |
| } |
| |
| /// Returns the storage location for the reference returned by the current |
| /// function. This can be null if function doesn't return a single consistent |
| /// reference. |
| /// |
| /// Requirements: |
| /// The current function must have a reference return type. |
| StorageLocation *getReturnStorageLocation() const { |
| assert(getCurrentFunc() != nullptr && |
| getCurrentFunc()->getReturnType()->isReferenceType()); |
| return ReturnLoc; |
| } |
| |
| /// Sets the return value of the current function. |
| /// |
| /// Requirements: |
| /// The current function must have a non-reference return type. |
| void setReturnValue(Value *Val) { |
| assert(getCurrentFunc() != nullptr && |
| !getCurrentFunc()->getReturnType()->isReferenceType()); |
| ReturnVal = Val; |
| } |
| |
| /// Sets the storage location for the reference returned by the current |
| /// function. |
| /// |
| /// Requirements: |
| /// The current function must have a reference return type. |
| void setReturnStorageLocation(StorageLocation *Loc) { |
| assert(getCurrentFunc() != nullptr && |
| getCurrentFunc()->getReturnType()->isReferenceType()); |
| ReturnLoc = Loc; |
| } |
| |
| /// Returns a pointer value that represents a null pointer. Calls with |
| /// `PointeeType` that are canonically equivalent will return the same result. |
| PointerValue &getOrCreateNullPointerValue(QualType PointeeType); |
| |
| /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise |
| /// returns null. |
| /// |
| /// If `Type` is a pointer or reference type, creates all the necessary |
| /// storage locations and values for indirections until it finds a |
| /// non-pointer/non-reference type. |
| /// |
| /// If `Type` is one of the following types, this function will always return |
| /// a non-null pointer: |
| /// - `bool` |
| /// - Any integer type |
| /// |
| /// Requirements: |
| /// |
| /// - `Type` must not be null. |
| /// - `Type` must not be a reference type or record type. |
| Value *createValue(QualType Type); |
| |
| /// Creates an object (i.e. a storage location with an associated value) of |
| /// type `Ty`. If `InitExpr` is non-null and has a value associated with it, |
| /// initializes the object with this value. Otherwise, initializes the object |
| /// with a value created using `createValue()`. |
| StorageLocation &createObject(QualType Ty, const Expr *InitExpr = nullptr) { |
| return createObjectInternal(nullptr, Ty, InitExpr); |
| } |
| |
| /// Creates an object for the variable declaration `D`. If `D` has an |
| /// initializer and this initializer is associated with a value, initializes |
| /// the object with this value. Otherwise, initializes the object with a |
| /// value created using `createValue()`. Uses the storage location returned by |
| /// `DataflowAnalysisContext::getStableStorageLocation(D)`. |
| StorageLocation &createObject(const VarDecl &D) { |
| return createObjectInternal(&D, D.getType(), D.getInit()); |
| } |
| |
| /// Creates an object for the variable declaration `D`. If `InitExpr` is |
| /// non-null and has a value associated with it, initializes the object with |
| /// this value. Otherwise, initializes the object with a value created using |
| /// `createValue()`. Uses the storage location returned by |
| /// `DataflowAnalysisContext::getStableStorageLocation(D)`. |
| StorageLocation &createObject(const ValueDecl &D, const Expr *InitExpr) { |
| return createObjectInternal(&D, D.getType(), InitExpr); |
| } |
| |
| /// Initializes the fields (including synthetic fields) of `Loc` with values, |
| /// unless values of the field type are not supported or we hit one of the |
| /// limits at which we stop producing values. |
| /// If a field already has a value, that value is preserved. |
| /// If `Type` is provided, initializes only those fields that are modeled for |
| /// `Type`; this is intended for use in cases where `Loc` is a derived type |
| /// and we only want to initialize the fields of a base type. |
| void initializeFieldsWithValues(RecordStorageLocation &Loc, QualType Type); |
| void initializeFieldsWithValues(RecordStorageLocation &Loc) { |
| initializeFieldsWithValues(Loc, Loc.getType()); |
| } |
| |
| /// Assigns `Val` as the value of `Loc` in the environment. |
| /// |
| /// Requirements: |
| /// |
| /// `Loc` must not be a `RecordStorageLocation`. |
| void setValue(const StorageLocation &Loc, Value &Val); |
| |
| /// Clears any association between `Loc` and a value in the environment. |
| void clearValue(const StorageLocation &Loc) { LocToVal.erase(&Loc); } |
| |
| /// Assigns `Val` as the value of the prvalue `E` in the environment. |
| /// |
| /// Requirements: |
| /// |
| /// - `E` must be a prvalue. |
| /// - `E` must not have record type. |
| void setValue(const Expr &E, Value &Val); |
| |
| /// Returns the value assigned to `Loc` in the environment or null if `Loc` |
| /// isn't assigned a value in the environment. |
| /// |
| /// Requirements: |
| /// |
| /// `Loc` must not be a `RecordStorageLocation`. |
| Value *getValue(const StorageLocation &Loc) const; |
| |
| /// Equivalent to `getValue(getStorageLocation(D))` if `D` is assigned a |
| /// storage location in the environment, otherwise returns null. |
| /// |
| /// Requirements: |
| /// |
| /// `D` must not have record type. |
| Value *getValue(const ValueDecl &D) const; |
| |
| /// Equivalent to `getValue(getStorageLocation(E, SP))` if `E` is assigned a |
| /// storage location in the environment, otherwise returns null. |
| Value *getValue(const Expr &E) const; |
| |
| /// Returns the result of casting `getValue(...)` to a subclass of `Value` |
| /// (using `cast_or_null<T>`). |
| /// This assert-fails if the result of `getValue(...)` is not of type `T *`; |
| /// if the value is not guaranteed to have type `T *`, consider using |
| /// `dyn_cast_or_null<T>(getValue(...))` instead. |
| template <typename T> |
| std::enable_if_t<std::is_base_of_v<Value, T>, T *> |
| get(const StorageLocation &Loc) const { |
| return cast_or_null<T>(getValue(Loc)); |
| } |
| template <typename T> |
| std::enable_if_t<std::is_base_of_v<Value, T>, T *> |
| get(const ValueDecl &D) const { |
| return cast_or_null<T>(getValue(D)); |
| } |
| template <typename T> |
| std::enable_if_t<std::is_base_of_v<Value, T>, T *> get(const Expr &E) const { |
| return cast_or_null<T>(getValue(E)); |
| } |
| |
| // FIXME: should we deprecate the following & call arena().create() directly? |
| |
| /// Creates a `T` (some subclass of `Value`), forwarding `args` to the |
| /// constructor, and returns a reference to it. |
| /// |
| /// The analysis context takes ownership of the created object. The object |
| /// will be destroyed when the analysis context is destroyed. |
| template <typename T, typename... Args> |
| std::enable_if_t<std::is_base_of<Value, T>::value, T &> |
| create(Args &&...args) { |
| return arena().create<T>(std::forward<Args>(args)...); |
| } |
| |
| /// Returns a symbolic integer value that models an integer literal equal to |
| /// `Value` |
| IntegerValue &getIntLiteralValue(llvm::APInt Value) const { |
| return arena().makeIntLiteral(Value); |
| } |
| |
| /// Returns a symbolic boolean value that models a boolean literal equal to |
| /// `Value` |
| BoolValue &getBoolLiteralValue(bool Value) const { |
| return arena().makeBoolValue(arena().makeLiteral(Value)); |
| } |
| |
| /// Returns an atomic boolean value. |
| BoolValue &makeAtomicBoolValue() const { |
| return arena().makeAtomValue(); |
| } |
| |
| /// Returns a unique instance of boolean Top. |
| BoolValue &makeTopBoolValue() const { |
| return arena().makeTopValue(); |
| } |
| |
| /// Returns a boolean value that represents the conjunction of `LHS` and |
| /// `RHS`. Subsequent calls with the same arguments, regardless of their |
| /// order, will return the same result. If the given boolean values represent |
| /// the same value, the result will be the value itself. |
| BoolValue &makeAnd(BoolValue &LHS, BoolValue &RHS) const { |
| return arena().makeBoolValue( |
| arena().makeAnd(LHS.formula(), RHS.formula())); |
| } |
| |
| /// Returns a boolean value that represents the disjunction of `LHS` and |
| /// `RHS`. Subsequent calls with the same arguments, regardless of their |
| /// order, will return the same result. If the given boolean values represent |
| /// the same value, the result will be the value itself. |
| BoolValue &makeOr(BoolValue &LHS, BoolValue &RHS) const { |
| return arena().makeBoolValue( |
| arena().makeOr(LHS.formula(), RHS.formula())); |
| } |
| |
| /// Returns a boolean value that represents the negation of `Val`. Subsequent |
| /// calls with the same argument will return the same result. |
| BoolValue &makeNot(BoolValue &Val) const { |
| return arena().makeBoolValue(arena().makeNot(Val.formula())); |
| } |
| |
| /// Returns a boolean value represents `LHS` => `RHS`. Subsequent calls with |
| /// the same arguments, will return the same result. If the given boolean |
| /// values represent the same value, the result will be a value that |
| /// represents the true boolean literal. |
| BoolValue &makeImplication(BoolValue &LHS, BoolValue &RHS) const { |
| return arena().makeBoolValue( |
| arena().makeImplies(LHS.formula(), RHS.formula())); |
| } |
| |
| /// Returns a boolean value represents `LHS` <=> `RHS`. Subsequent calls with |
| /// the same arguments, regardless of their order, will return the same |
| /// result. If the given boolean values represent the same value, the result |
| /// will be a value that represents the true boolean literal. |
| BoolValue &makeIff(BoolValue &LHS, BoolValue &RHS) const { |
| return arena().makeBoolValue( |
| arena().makeEquals(LHS.formula(), RHS.formula())); |
| } |
| |
| /// Returns a boolean variable that identifies the flow condition (FC). |
| /// |
| /// The flow condition is a set of facts that are necessarily true when the |
| /// program reaches the current point, expressed as boolean formulas. |
| /// The flow condition token is equivalent to the AND of these facts. |
| /// |
| /// These may e.g. constrain the value of certain variables. A pointer |
| /// variable may have a consistent modeled PointerValue throughout, but at a |
| /// given point the Environment may tell us that the value must be non-null. |
| /// |
| /// The FC is necessary but not sufficient for this point to be reachable. |
| /// In particular, where the FC token appears in flow conditions of successor |
| /// environments, it means "point X may have been reached", not |
| /// "point X was reached". |
| Atom getFlowConditionToken() const { return FlowConditionToken; } |
| |
| /// Record a fact that must be true if this point in the program is reached. |
| void assume(const Formula &); |
| |
| /// Returns true if the formula is always true when this point is reached. |
| /// Returns false if the formula may be false (or the flow condition isn't |
| /// sufficiently precise to prove that it is true) or if the solver times out. |
| /// |
| /// Note that there is an asymmetry between this function and `allows()` in |
| /// that they both return false if the solver times out. The assumption is |
| /// that if `proves()` or `allows()` returns true, this will result in a |
| /// diagnostic, and we want to bias towards false negatives in the case where |
| /// the solver times out. |
| bool proves(const Formula &) const; |
| |
| /// Returns true if the formula may be true when this point is reached. |
| /// Returns false if the formula is always false when this point is reached |
| /// (or the flow condition is overly constraining) or if the solver times out. |
| bool allows(const Formula &) const; |
| |
| /// Returns the `DeclContext` of the block being analysed, if any. Otherwise, |
| /// returns null. |
| const DeclContext *getDeclCtx() const { return CallStack.back(); } |
| |
| /// Returns the function currently being analyzed, or null if the code being |
| /// analyzed isn't part of a function. |
| const FunctionDecl *getCurrentFunc() const { |
| return dyn_cast<FunctionDecl>(getDeclCtx()); |
| } |
| |
| /// Returns the size of the call stack. |
| size_t callStackSize() const { return CallStack.size(); } |
| |
| /// Returns whether this `Environment` can be extended to analyze the given |
| /// `Callee` (i.e. if `pushCall` can be used), with recursion disallowed and a |
| /// given `MaxDepth`. |
| bool canDescend(unsigned MaxDepth, const DeclContext *Callee) const; |
| |
| /// Returns the `DataflowAnalysisContext` used by the environment. |
| DataflowAnalysisContext &getDataflowAnalysisContext() const { return *DACtx; } |
| |
| Arena &arena() const { return DACtx->arena(); } |
| |
| LLVM_DUMP_METHOD void dump() const; |
| LLVM_DUMP_METHOD void dump(raw_ostream &OS) const; |
| |
| private: |
| using PrValueToResultObject = |
| llvm::DenseMap<const Expr *, RecordStorageLocation *>; |
| |
| // The copy-constructor is for use in fork() only. |
| Environment(const Environment &) = default; |
| |
| /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise |
| /// return null. |
| /// |
| /// Recursively initializes storage locations and values until it sees a |
| /// self-referential pointer or reference type. `Visited` is used to track |
| /// which types appeared in the reference/pointer chain in order to avoid |
| /// creating a cyclic dependency with self-referential pointers/references. |
| /// |
| /// Requirements: |
| /// |
| /// `Type` must not be null. |
| Value *createValueUnlessSelfReferential(QualType Type, |
| llvm::DenseSet<QualType> &Visited, |
| int Depth, int &CreatedValuesCount); |
| |
| /// Creates a storage location for `Ty`. Also creates and associates a value |
| /// with the storage location, unless values of this type are not supported or |
| /// we hit one of the limits at which we stop producing values (controlled by |
| /// `Visited`, `Depth`, and `CreatedValuesCount`). |
| StorageLocation &createLocAndMaybeValue(QualType Ty, |
| llvm::DenseSet<QualType> &Visited, |
| int Depth, int &CreatedValuesCount); |
| |
| /// Initializes the fields (including synthetic fields) of `Loc` with values, |
| /// unless values of the field type are not supported or we hit one of the |
| /// limits at which we stop producing values (controlled by `Visited`, |
| /// `Depth`, and `CreatedValuesCount`). If `Type` is different from |
| /// `Loc.getType()`, initializes only those fields that are modeled for |
| /// `Type`. |
| void initializeFieldsWithValues(RecordStorageLocation &Loc, QualType Type, |
| llvm::DenseSet<QualType> &Visited, int Depth, |
| int &CreatedValuesCount); |
| |
| /// Shared implementation of `createObject()` overloads. |
| /// `D` and `InitExpr` may be null. |
| StorageLocation &createObjectInternal(const ValueDecl *D, QualType Ty, |
| const Expr *InitExpr); |
| |
| /// Shared implementation of `pushCall` overloads. Note that unlike |
| /// `pushCall`, this member is invoked on the environment of the callee, not |
| /// of the caller. |
| void pushCallInternal(const FunctionDecl *FuncDecl, |
| ArrayRef<const Expr *> Args); |
| |
| /// Assigns storage locations and values to all global variables, fields |
| /// and functions referenced in `FuncDecl`. `FuncDecl` must have a body. |
| void initFieldsGlobalsAndFuncs(const FunctionDecl *FuncDecl); |
| |
| static PrValueToResultObject |
| buildResultObjectMap(DataflowAnalysisContext *DACtx, |
| const FunctionDecl *FuncDecl, |
| RecordStorageLocation *ThisPointeeLoc, |
| RecordStorageLocation *LocForRecordReturnVal); |
| |
| // `DACtx` is not null and not owned by this object. |
| DataflowAnalysisContext *DACtx; |
| |
| // FIXME: move the fields `CallStack`, `ResultObjectMap`, `ReturnVal`, |
| // `ReturnLoc` and `ThisPointeeLoc` into a separate call-context object, |
| // shared between environments in the same call. |
| // https://github.com/llvm/llvm-project/issues/59005 |
| |
| // `DeclContext` of the block being analysed if provided. |
| std::vector<const DeclContext *> CallStack; |
| |
| // Maps from prvalues of record type to their result objects. Shared between |
| // all environments for the same function. |
| // FIXME: It's somewhat unsatisfactory that we have to use a `shared_ptr` |
| // here, though the cost is acceptable: The overhead of a `shared_ptr` is |
| // incurred when it is copied, and this happens only relatively rarely (when |
| // we fork the environment). The need for a `shared_ptr` will go away once we |
| // introduce a shared call-context object (see above). |
| std::shared_ptr<PrValueToResultObject> ResultObjectMap; |
| |
| // The following three member variables handle various different types of |
| // return values. |
| // - If the return type is not a reference and not a record: Value returned |
| // by the function. |
| Value *ReturnVal = nullptr; |
| // - If the return type is a reference: Storage location of the reference |
| // returned by the function. |
| StorageLocation *ReturnLoc = nullptr; |
| // - If the return type is a record or the function being analyzed is a |
| // constructor: Storage location into which the return value should be |
| // constructed. |
| RecordStorageLocation *LocForRecordReturnVal = nullptr; |
| |
| // The storage location of the `this` pointee. Should only be null if the |
| // function being analyzed is only a function and not a method. |
| RecordStorageLocation *ThisPointeeLoc = nullptr; |
| |
| // Maps from declarations and glvalue expression to storage locations that are |
| // assigned to them. Unlike the maps in `DataflowAnalysisContext`, these |
| // include only storage locations that are in scope for a particular basic |
| // block. |
| llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc; |
| llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc; |
| // Maps from prvalue expressions and storage locations to the values that |
| // are assigned to them. |
| // We preserve insertion order so that join/widen process values in |
| // deterministic sequence. This in turn produces deterministic SAT formulas. |
| llvm::MapVector<const Expr *, Value *> ExprToVal; |
| llvm::MapVector<const StorageLocation *, Value *> LocToVal; |
| |
| Atom FlowConditionToken; |
| }; |
| |
| /// Returns the storage location for the implicit object of a |
| /// `CXXMemberCallExpr`, or null if none is defined in the environment. |
| /// Dereferences the pointer if the member call expression was written using |
| /// `->`. |
| RecordStorageLocation *getImplicitObjectLocation(const CXXMemberCallExpr &MCE, |
| const Environment &Env); |
| |
| /// Returns the storage location for the base object of a `MemberExpr`, or null |
| /// if none is defined in the environment. Dereferences the pointer if the |
| /// member expression was written using `->`. |
| RecordStorageLocation *getBaseObjectLocation(const MemberExpr &ME, |
| const Environment &Env); |
| |
| } // namespace dataflow |
| } // namespace clang |
| |
| #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H |