14824e7fdSDimitry Andric //===-- DataflowEnvironment.h -----------------------------------*- C++ -*-===// 24824e7fdSDimitry Andric // 34824e7fdSDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 44824e7fdSDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 54824e7fdSDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 64824e7fdSDimitry Andric // 74824e7fdSDimitry Andric //===----------------------------------------------------------------------===// 84824e7fdSDimitry Andric // 94824e7fdSDimitry Andric // This file defines an Environment class that is used by dataflow analyses 104824e7fdSDimitry Andric // that run over Control-Flow Graphs (CFGs) to keep track of the state of the 114824e7fdSDimitry Andric // program at given program points. 124824e7fdSDimitry Andric // 134824e7fdSDimitry Andric //===----------------------------------------------------------------------===// 144824e7fdSDimitry Andric 154824e7fdSDimitry Andric #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H 164824e7fdSDimitry Andric #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H 174824e7fdSDimitry Andric 1804eeddc0SDimitry Andric #include "clang/AST/Decl.h" 1904eeddc0SDimitry Andric #include "clang/AST/DeclBase.h" 2004eeddc0SDimitry Andric #include "clang/AST/Expr.h" 2104eeddc0SDimitry Andric #include "clang/AST/Type.h" 22bdd1243dSDimitry Andric #include "clang/Analysis/FlowSensitive/ControlFlowContext.h" 2304eeddc0SDimitry Andric #include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h" 240eae32dcSDimitry Andric #include "clang/Analysis/FlowSensitive/DataflowLattice.h" 2506c3fb27SDimitry Andric #include "clang/Analysis/FlowSensitive/Formula.h" 2606c3fb27SDimitry Andric #include "clang/Analysis/FlowSensitive/Logger.h" 2704eeddc0SDimitry Andric #include "clang/Analysis/FlowSensitive/StorageLocation.h" 2804eeddc0SDimitry Andric #include "clang/Analysis/FlowSensitive/Value.h" 2904eeddc0SDimitry Andric #include "llvm/ADT/DenseMap.h" 3004eeddc0SDimitry Andric #include "llvm/ADT/DenseSet.h" 3106c3fb27SDimitry Andric #include "llvm/ADT/MapVector.h" 3206c3fb27SDimitry Andric #include "llvm/Support/Compiler.h" 33bdd1243dSDimitry Andric #include "llvm/Support/ErrorHandling.h" 3404eeddc0SDimitry Andric #include <memory> 3504eeddc0SDimitry Andric #include <type_traits> 3604eeddc0SDimitry Andric #include <utility> 370eae32dcSDimitry Andric 384824e7fdSDimitry Andric namespace clang { 394824e7fdSDimitry Andric namespace dataflow { 404824e7fdSDimitry Andric 41bdd1243dSDimitry Andric /// Indicates the result of a tentative comparison. 42bdd1243dSDimitry Andric enum class ComparisonResult { 43bdd1243dSDimitry Andric Same, 44bdd1243dSDimitry Andric Different, 45bdd1243dSDimitry Andric Unknown, 46bdd1243dSDimitry Andric }; 47bdd1243dSDimitry Andric 484824e7fdSDimitry Andric /// Holds the state of the program (store and heap) at a given program point. 4981ad6265SDimitry Andric /// 5081ad6265SDimitry Andric /// WARNING: Symbolic values that are created by the environment for static 5181ad6265SDimitry Andric /// local and global variables are not currently invalidated on function calls. 5281ad6265SDimitry Andric /// This is unsound and should be taken into account when designing dataflow 5381ad6265SDimitry Andric /// analyses. 540eae32dcSDimitry Andric class Environment { 550eae32dcSDimitry Andric public: 561fd87a68SDimitry Andric /// Supplements `Environment` with non-standard comparison and join 571fd87a68SDimitry Andric /// operations. 581fd87a68SDimitry Andric class ValueModel { 5904eeddc0SDimitry Andric public: 601fd87a68SDimitry Andric virtual ~ValueModel() = default; 610eae32dcSDimitry Andric 62bdd1243dSDimitry Andric /// Returns: 63bdd1243dSDimitry Andric /// `Same`: `Val1` is equivalent to `Val2`, according to the model. 64bdd1243dSDimitry Andric /// `Different`: `Val1` is distinct from `Val2`, according to the model. 65bdd1243dSDimitry Andric /// `Unknown`: The model can't determine a relationship between `Val1` and 66bdd1243dSDimitry Andric /// `Val2`. 6704eeddc0SDimitry Andric /// 6804eeddc0SDimitry Andric /// Requirements: 6904eeddc0SDimitry Andric /// 7004eeddc0SDimitry Andric /// `Val1` and `Val2` must be distinct. 711fd87a68SDimitry Andric /// 721fd87a68SDimitry Andric /// `Val1` and `Val2` must model values of type `Type`. 7381ad6265SDimitry Andric /// 7481ad6265SDimitry Andric /// `Val1` and `Val2` must be assigned to the same storage location in 7581ad6265SDimitry Andric /// `Env1` and `Env2` respectively. compare(QualType Type,const Value & Val1,const Environment & Env1,const Value & Val2,const Environment & Env2)76bdd1243dSDimitry Andric virtual ComparisonResult compare(QualType Type, const Value &Val1, 7781ad6265SDimitry Andric const Environment &Env1, const Value &Val2, 7881ad6265SDimitry Andric const Environment &Env2) { 795f757f3fSDimitry Andric // FIXME: Consider adding QualType to RecordValue and removing the Type 801fd87a68SDimitry Andric // argument here. 81bdd1243dSDimitry Andric return ComparisonResult::Unknown; 821fd87a68SDimitry Andric } 831fd87a68SDimitry Andric 841fd87a68SDimitry Andric /// Modifies `MergedVal` to approximate both `Val1` and `Val2`. This could 8581ad6265SDimitry Andric /// be a strict lattice join or a more general widening operation. 8681ad6265SDimitry Andric /// 8781ad6265SDimitry Andric /// If this function returns true, `MergedVal` will be assigned to a storage 8881ad6265SDimitry Andric /// location of type `Type` in `MergedEnv`. 8981ad6265SDimitry Andric /// 9081ad6265SDimitry Andric /// `Env1` and `Env2` can be used to query child values and path condition 9181ad6265SDimitry Andric /// implications of `Val1` and `Val2` respectively. 921fd87a68SDimitry Andric /// 931fd87a68SDimitry Andric /// Requirements: 941fd87a68SDimitry Andric /// 951fd87a68SDimitry Andric /// `Val1` and `Val2` must be distinct. 961fd87a68SDimitry Andric /// 971fd87a68SDimitry Andric /// `Val1`, `Val2`, and `MergedVal` must model values of type `Type`. 9881ad6265SDimitry Andric /// 9981ad6265SDimitry Andric /// `Val1` and `Val2` must be assigned to the same storage location in 10081ad6265SDimitry Andric /// `Env1` and `Env2` respectively. merge(QualType Type,const Value & Val1,const Environment & Env1,const Value & Val2,const Environment & Env2,Value & MergedVal,Environment & MergedEnv)10181ad6265SDimitry Andric virtual bool merge(QualType Type, const Value &Val1, 10281ad6265SDimitry Andric const Environment &Env1, const Value &Val2, 10381ad6265SDimitry Andric const Environment &Env2, Value &MergedVal, 10481ad6265SDimitry Andric Environment &MergedEnv) { 10581ad6265SDimitry Andric return true; 1060eae32dcSDimitry Andric } 107bdd1243dSDimitry Andric 108bdd1243dSDimitry Andric /// This function may widen the current value -- replace it with an 109bdd1243dSDimitry Andric /// approximation that can reach a fixed point more quickly than iterated 110bdd1243dSDimitry Andric /// application of the transfer function alone. The previous value is 111bdd1243dSDimitry Andric /// provided to inform the choice of widened value. The function must also 112bdd1243dSDimitry Andric /// serve as a comparison operation, by indicating whether the widened value 113bdd1243dSDimitry Andric /// is equivalent to the previous value. 114bdd1243dSDimitry Andric /// 115bdd1243dSDimitry Andric /// Returns either: 116bdd1243dSDimitry Andric /// 117bdd1243dSDimitry Andric /// `nullptr`, if this value is not of interest to the model, or 118bdd1243dSDimitry Andric /// 119bdd1243dSDimitry Andric /// `&Prev`, if the widened value is equivalent to `Prev`, or 120bdd1243dSDimitry Andric /// 121bdd1243dSDimitry Andric /// A non-null value that approximates `Current`. `Prev` is available to 122bdd1243dSDimitry Andric /// inform the chosen approximation. 123bdd1243dSDimitry Andric /// 124bdd1243dSDimitry Andric /// `PrevEnv` and `CurrentEnv` can be used to query child values and path 125bdd1243dSDimitry Andric /// condition implications of `Prev` and `Current`, respectively. 126bdd1243dSDimitry Andric /// 127bdd1243dSDimitry Andric /// Requirements: 128bdd1243dSDimitry Andric /// 129bdd1243dSDimitry Andric /// `Prev` and `Current` must model values of type `Type`. 130bdd1243dSDimitry Andric /// 131bdd1243dSDimitry Andric /// `Prev` and `Current` must be assigned to the same storage location in 132bdd1243dSDimitry Andric /// `PrevEnv` and `CurrentEnv`, respectively. widen(QualType Type,Value & Prev,const Environment & PrevEnv,Value & Current,Environment & CurrentEnv)133bdd1243dSDimitry Andric virtual Value *widen(QualType Type, Value &Prev, const Environment &PrevEnv, 134bdd1243dSDimitry Andric Value &Current, Environment &CurrentEnv) { 135bdd1243dSDimitry Andric // The default implementation reduces to just comparison, since comparison 136bdd1243dSDimitry Andric // is required by the API, even if no widening is performed. 137bdd1243dSDimitry Andric switch (compare(Type, Prev, PrevEnv, Current, CurrentEnv)) { 138bdd1243dSDimitry Andric case ComparisonResult::Same: 139bdd1243dSDimitry Andric return &Prev; 140bdd1243dSDimitry Andric case ComparisonResult::Different: 141bdd1243dSDimitry Andric return &Current; 142bdd1243dSDimitry Andric case ComparisonResult::Unknown: 143bdd1243dSDimitry Andric return nullptr; 144bdd1243dSDimitry Andric } 145bdd1243dSDimitry Andric llvm_unreachable("all cases in switch covered"); 146bdd1243dSDimitry Andric } 1470eae32dcSDimitry Andric }; 1484824e7fdSDimitry Andric 14904eeddc0SDimitry Andric /// Creates an environment that uses `DACtx` to store objects that encompass 15004eeddc0SDimitry Andric /// the state of a program. 15181ad6265SDimitry Andric explicit Environment(DataflowAnalysisContext &DACtx); 15281ad6265SDimitry Andric 15306c3fb27SDimitry Andric // Copy-constructor is private, Environments should not be copied. See fork(). 15406c3fb27SDimitry Andric Environment &operator=(const Environment &Other) = delete; 15581ad6265SDimitry Andric 15681ad6265SDimitry Andric Environment(Environment &&Other) = default; 15781ad6265SDimitry Andric Environment &operator=(Environment &&Other) = default; 15804eeddc0SDimitry Andric 15904eeddc0SDimitry Andric /// Creates an environment that uses `DACtx` to store objects that encompass 16004eeddc0SDimitry Andric /// the state of a program. 16104eeddc0SDimitry Andric /// 16204eeddc0SDimitry Andric /// If `DeclCtx` is a function, initializes the environment with symbolic 16304eeddc0SDimitry Andric /// representations of the function parameters. 16404eeddc0SDimitry Andric /// 16504eeddc0SDimitry Andric /// If `DeclCtx` is a non-static member function, initializes the environment 16604eeddc0SDimitry Andric /// with a symbolic representation of the `this` pointee. 16704eeddc0SDimitry Andric Environment(DataflowAnalysisContext &DACtx, const DeclContext &DeclCtx); 16804eeddc0SDimitry Andric 1695f757f3fSDimitry Andric /// Assigns storage locations and values to all parameters, captures, global 1705f757f3fSDimitry Andric /// variables, fields and functions referenced in the function currently being 1715f757f3fSDimitry Andric /// analyzed. 1725f757f3fSDimitry Andric /// 1735f757f3fSDimitry Andric /// Requirements: 1745f757f3fSDimitry Andric /// 175*7a6dacacSDimitry Andric /// The function must have a body, i.e. 176*7a6dacacSDimitry Andric /// `FunctionDecl::doesThisDecalarationHaveABody()` must be true. 1775f757f3fSDimitry Andric void initialize(); 1785f757f3fSDimitry Andric 17906c3fb27SDimitry Andric /// Returns a new environment that is a copy of this one. 18006c3fb27SDimitry Andric /// 18106c3fb27SDimitry Andric /// The state of the program is initially the same, but can be mutated without 18206c3fb27SDimitry Andric /// affecting the original. 18306c3fb27SDimitry Andric /// 18406c3fb27SDimitry Andric /// However the original should not be further mutated, as this may interfere 18506c3fb27SDimitry Andric /// with the fork. (In practice, values are stored independently, but the 18606c3fb27SDimitry Andric /// forked flow condition references the original). 18706c3fb27SDimitry Andric Environment fork() const; 188bdd1243dSDimitry Andric 189972a253aSDimitry Andric /// Creates and returns an environment to use for an inline analysis of the 190972a253aSDimitry Andric /// callee. Uses the storage location from each argument in the `Call` as the 191972a253aSDimitry Andric /// storage location for the corresponding parameter in the callee. 192972a253aSDimitry Andric /// 193972a253aSDimitry Andric /// Requirements: 194972a253aSDimitry Andric /// 195bdd1243dSDimitry Andric /// The callee of `Call` must be a `FunctionDecl`. 196972a253aSDimitry Andric /// 197972a253aSDimitry Andric /// The body of the callee must not reference globals. 198972a253aSDimitry Andric /// 199972a253aSDimitry Andric /// The arguments of `Call` must map 1:1 to the callee's parameters. 200972a253aSDimitry Andric Environment pushCall(const CallExpr *Call) const; 201bdd1243dSDimitry Andric Environment pushCall(const CXXConstructExpr *Call) const; 202bdd1243dSDimitry Andric 203bdd1243dSDimitry Andric /// Moves gathered information back into `this` from a `CalleeEnv` created via 204bdd1243dSDimitry Andric /// `pushCall`. 20506c3fb27SDimitry Andric void popCall(const CallExpr *Call, const Environment &CalleeEnv); 20606c3fb27SDimitry Andric void popCall(const CXXConstructExpr *Call, const Environment &CalleeEnv); 207972a253aSDimitry Andric 2081fd87a68SDimitry Andric /// Returns true if and only if the environment is equivalent to `Other`, i.e 2091fd87a68SDimitry Andric /// the two environments: 2101fd87a68SDimitry Andric /// - have the same mappings from declarations to storage locations, 2111fd87a68SDimitry Andric /// - have the same mappings from expressions to storage locations, 2121fd87a68SDimitry Andric /// - have the same or equivalent (according to `Model`) values assigned to 2131fd87a68SDimitry Andric /// the same storage locations. 2141fd87a68SDimitry Andric /// 2151fd87a68SDimitry Andric /// Requirements: 2161fd87a68SDimitry Andric /// 2171fd87a68SDimitry Andric /// `Other` and `this` must use the same `DataflowAnalysisContext`. 2181fd87a68SDimitry Andric bool equivalentTo(const Environment &Other, 2191fd87a68SDimitry Andric Environment::ValueModel &Model) const; 22004eeddc0SDimitry Andric 22106c3fb27SDimitry Andric /// Joins two environments by taking the intersection of storage locations and 22206c3fb27SDimitry Andric /// values that are stored in them. Distinct values that are assigned to the 22306c3fb27SDimitry Andric /// same storage locations in `EnvA` and `EnvB` are merged using `Model`. 2241fd87a68SDimitry Andric /// 2251fd87a68SDimitry Andric /// Requirements: 2261fd87a68SDimitry Andric /// 22706c3fb27SDimitry Andric /// `EnvA` and `EnvB` must use the same `DataflowAnalysisContext`. 22806c3fb27SDimitry Andric static Environment join(const Environment &EnvA, const Environment &EnvB, 2291fd87a68SDimitry Andric Environment::ValueModel &Model); 23004eeddc0SDimitry Andric 231bdd1243dSDimitry Andric /// Widens the environment point-wise, using `PrevEnv` as needed to inform the 232bdd1243dSDimitry Andric /// approximation. 233bdd1243dSDimitry Andric /// 234bdd1243dSDimitry Andric /// Requirements: 235bdd1243dSDimitry Andric /// 236bdd1243dSDimitry Andric /// `PrevEnv` must be the immediate previous version of the environment. 237bdd1243dSDimitry Andric /// `PrevEnv` and `this` must use the same `DataflowAnalysisContext`. 238bdd1243dSDimitry Andric LatticeJoinEffect widen(const Environment &PrevEnv, 239bdd1243dSDimitry Andric Environment::ValueModel &Model); 240bdd1243dSDimitry Andric 24104eeddc0SDimitry Andric // FIXME: Rename `createOrGetStorageLocation` to `getOrCreateStorageLocation`, 24204eeddc0SDimitry Andric // `getStableStorageLocation`, or something more appropriate. 24304eeddc0SDimitry Andric 24404eeddc0SDimitry Andric /// Creates a storage location appropriate for `Type`. Does not assign a value 24504eeddc0SDimitry Andric /// to the returned storage location in the environment. 24604eeddc0SDimitry Andric /// 24704eeddc0SDimitry Andric /// Requirements: 24804eeddc0SDimitry Andric /// 24904eeddc0SDimitry Andric /// `Type` must not be null. 25004eeddc0SDimitry Andric StorageLocation &createStorageLocation(QualType Type); 25104eeddc0SDimitry Andric 25204eeddc0SDimitry Andric /// Creates a storage location for `D`. Does not assign the returned storage 25304eeddc0SDimitry Andric /// location to `D` in the environment. Does not assign a value to the 25404eeddc0SDimitry Andric /// returned storage location in the environment. 2555f757f3fSDimitry Andric StorageLocation &createStorageLocation(const ValueDecl &D); 25604eeddc0SDimitry Andric 25704eeddc0SDimitry Andric /// Creates a storage location for `E`. Does not assign the returned storage 25804eeddc0SDimitry Andric /// location to `E` in the environment. Does not assign a value to the 25904eeddc0SDimitry Andric /// returned storage location in the environment. 26004eeddc0SDimitry Andric StorageLocation &createStorageLocation(const Expr &E); 26104eeddc0SDimitry Andric 26204eeddc0SDimitry Andric /// Assigns `Loc` as the storage location of `D` in the environment. 26304eeddc0SDimitry Andric /// 26404eeddc0SDimitry Andric /// Requirements: 26504eeddc0SDimitry Andric /// 26606c3fb27SDimitry Andric /// `D` must not already have a storage location in the environment. 26704eeddc0SDimitry Andric void setStorageLocation(const ValueDecl &D, StorageLocation &Loc); 26804eeddc0SDimitry Andric 26906c3fb27SDimitry Andric /// Returns the storage location assigned to `D` in the environment, or null 27006c3fb27SDimitry Andric /// if `D` isn't assigned a storage location in the environment. 27106c3fb27SDimitry Andric StorageLocation *getStorageLocation(const ValueDecl &D) const; 27204eeddc0SDimitry Andric 2735f757f3fSDimitry Andric /// Removes the location assigned to `D` in the environment (if any). 2745f757f3fSDimitry Andric void removeDecl(const ValueDecl &D); 27504eeddc0SDimitry Andric 27606c3fb27SDimitry Andric /// Assigns `Loc` as the storage location of the glvalue `E` in the 27706c3fb27SDimitry Andric /// environment. 27806c3fb27SDimitry Andric /// 27906c3fb27SDimitry Andric /// Requirements: 28006c3fb27SDimitry Andric /// 28106c3fb27SDimitry Andric /// `E` must not be assigned a storage location in the environment. 28206c3fb27SDimitry Andric /// `E` must be a glvalue or a `BuiltinType::BuiltinFn` 2835f757f3fSDimitry Andric void setStorageLocation(const Expr &E, StorageLocation &Loc); 28404eeddc0SDimitry Andric 28506c3fb27SDimitry Andric /// Returns the storage location assigned to the glvalue `E` in the 28606c3fb27SDimitry Andric /// environment, or null if `E` isn't assigned a storage location in the 28706c3fb27SDimitry Andric /// environment. 28806c3fb27SDimitry Andric /// 28906c3fb27SDimitry Andric /// Requirements: 29006c3fb27SDimitry Andric /// `E` must be a glvalue or a `BuiltinType::BuiltinFn` 2915f757f3fSDimitry Andric StorageLocation *getStorageLocation(const Expr &E) const; 29206c3fb27SDimitry Andric 293cb14a3feSDimitry Andric /// Returns the result of casting `getStorageLocation(...)` to a subclass of 294cb14a3feSDimitry Andric /// `StorageLocation` (using `cast_or_null<T>`). 295cb14a3feSDimitry Andric /// This assert-fails if the result of `getStorageLocation(...)` is not of 296cb14a3feSDimitry Andric /// type `T *`; if the storage location is not guaranteed to have type `T *`, 297cb14a3feSDimitry Andric /// consider using `dyn_cast_or_null<T>(getStorageLocation(...))` instead. 298cb14a3feSDimitry Andric template <typename T> 299cb14a3feSDimitry Andric std::enable_if_t<std::is_base_of_v<StorageLocation, T>, T *> get(const ValueDecl & D)300cb14a3feSDimitry Andric get(const ValueDecl &D) const { 301cb14a3feSDimitry Andric return cast_or_null<T>(getStorageLocation(D)); 302cb14a3feSDimitry Andric } 303cb14a3feSDimitry Andric template <typename T> 304cb14a3feSDimitry Andric std::enable_if_t<std::is_base_of_v<StorageLocation, T>, T *> get(const Expr & E)305cb14a3feSDimitry Andric get(const Expr &E) const { 306cb14a3feSDimitry Andric return cast_or_null<T>(getStorageLocation(E)); 307cb14a3feSDimitry Andric } 308cb14a3feSDimitry Andric 30904eeddc0SDimitry Andric /// Returns the storage location assigned to the `this` pointee in the 31004eeddc0SDimitry Andric /// environment or null if the `this` pointee has no assigned storage location 31104eeddc0SDimitry Andric /// in the environment. getThisPointeeStorageLocation()3125f757f3fSDimitry Andric RecordStorageLocation *getThisPointeeStorageLocation() const { 3135f757f3fSDimitry Andric return ThisPointeeLoc; 3145f757f3fSDimitry Andric } 3155f757f3fSDimitry Andric 3165f757f3fSDimitry Andric /// Sets the storage location assigned to the `this` pointee in the 3175f757f3fSDimitry Andric /// environment. setThisPointeeStorageLocation(RecordStorageLocation & Loc)3185f757f3fSDimitry Andric void setThisPointeeStorageLocation(RecordStorageLocation &Loc) { 3195f757f3fSDimitry Andric ThisPointeeLoc = &Loc; 3205f757f3fSDimitry Andric } 32104eeddc0SDimitry Andric 32206c3fb27SDimitry Andric /// Returns the location of the result object for a record-type prvalue. 32306c3fb27SDimitry Andric /// 32406c3fb27SDimitry Andric /// In C++, prvalues of record type serve only a limited purpose: They can 32506c3fb27SDimitry Andric /// only be used to initialize a result object (e.g. a variable or a 32606c3fb27SDimitry Andric /// temporary). This function returns the location of that result object. 32706c3fb27SDimitry Andric /// 32806c3fb27SDimitry Andric /// When creating a prvalue of record type, we already need the storage 32906c3fb27SDimitry Andric /// location of the result object to pass in `this`, even though prvalues are 33006c3fb27SDimitry Andric /// otherwise not associated with storage locations. 33106c3fb27SDimitry Andric /// 33206c3fb27SDimitry Andric /// FIXME: Currently, this simply returns a stable storage location for `E`, 33306c3fb27SDimitry Andric /// but this doesn't do the right thing in scenarios like the following: 33406c3fb27SDimitry Andric /// ``` 33506c3fb27SDimitry Andric /// MyClass c = some_condition()? MyClass(foo) : MyClass(bar); 33606c3fb27SDimitry Andric /// ``` 33706c3fb27SDimitry Andric /// Here, `MyClass(foo)` and `MyClass(bar)` will have two different storage 33806c3fb27SDimitry Andric /// locations, when in fact their storage locations should be the same. 33906c3fb27SDimitry Andric /// Eventually, we want to propagate storage locations from result objects 34006c3fb27SDimitry Andric /// down to the prvalues that initialize them, similar to the way that this is 34106c3fb27SDimitry Andric /// done in Clang's CodeGen. 34206c3fb27SDimitry Andric /// 34306c3fb27SDimitry Andric /// Requirements: 34406c3fb27SDimitry Andric /// `E` must be a prvalue of record type. 345cb14a3feSDimitry Andric RecordStorageLocation & 346cb14a3feSDimitry Andric getResultObjectLocation(const Expr &RecordPRValue) const; 34706c3fb27SDimitry Andric 34806c3fb27SDimitry Andric /// Returns the return value of the current function. This can be null if: 34906c3fb27SDimitry Andric /// - The function has a void return type 35006c3fb27SDimitry Andric /// - No return value could be determined for the function, for example 35106c3fb27SDimitry Andric /// because it calls a function without a body. 35206c3fb27SDimitry Andric /// 35306c3fb27SDimitry Andric /// Requirements: 35406c3fb27SDimitry Andric /// The current function must have a non-reference return type. getReturnValue()35506c3fb27SDimitry Andric Value *getReturnValue() const { 35606c3fb27SDimitry Andric assert(getCurrentFunc() != nullptr && 35706c3fb27SDimitry Andric !getCurrentFunc()->getReturnType()->isReferenceType()); 35806c3fb27SDimitry Andric return ReturnVal; 35906c3fb27SDimitry Andric } 36006c3fb27SDimitry Andric 36106c3fb27SDimitry Andric /// Returns the storage location for the reference returned by the current 36206c3fb27SDimitry Andric /// function. This can be null if function doesn't return a single consistent 36306c3fb27SDimitry Andric /// reference. 36406c3fb27SDimitry Andric /// 36506c3fb27SDimitry Andric /// Requirements: 36606c3fb27SDimitry Andric /// The current function must have a reference return type. getReturnStorageLocation()36706c3fb27SDimitry Andric StorageLocation *getReturnStorageLocation() const { 36806c3fb27SDimitry Andric assert(getCurrentFunc() != nullptr && 36906c3fb27SDimitry Andric getCurrentFunc()->getReturnType()->isReferenceType()); 37006c3fb27SDimitry Andric return ReturnLoc; 37106c3fb27SDimitry Andric } 37206c3fb27SDimitry Andric 37306c3fb27SDimitry Andric /// Sets the return value of the current function. 37406c3fb27SDimitry Andric /// 37506c3fb27SDimitry Andric /// Requirements: 37606c3fb27SDimitry Andric /// The current function must have a non-reference return type. setReturnValue(Value * Val)37706c3fb27SDimitry Andric void setReturnValue(Value *Val) { 37806c3fb27SDimitry Andric assert(getCurrentFunc() != nullptr && 37906c3fb27SDimitry Andric !getCurrentFunc()->getReturnType()->isReferenceType()); 38006c3fb27SDimitry Andric ReturnVal = Val; 38106c3fb27SDimitry Andric } 38206c3fb27SDimitry Andric 38306c3fb27SDimitry Andric /// Sets the storage location for the reference returned by the current 38406c3fb27SDimitry Andric /// function. 38506c3fb27SDimitry Andric /// 38606c3fb27SDimitry Andric /// Requirements: 38706c3fb27SDimitry Andric /// The current function must have a reference return type. setReturnStorageLocation(StorageLocation * Loc)38806c3fb27SDimitry Andric void setReturnStorageLocation(StorageLocation *Loc) { 38906c3fb27SDimitry Andric assert(getCurrentFunc() != nullptr && 39006c3fb27SDimitry Andric getCurrentFunc()->getReturnType()->isReferenceType()); 39106c3fb27SDimitry Andric ReturnLoc = Loc; 39206c3fb27SDimitry Andric } 393bdd1243dSDimitry Andric 39481ad6265SDimitry Andric /// Returns a pointer value that represents a null pointer. Calls with 39581ad6265SDimitry Andric /// `PointeeType` that are canonically equivalent will return the same result. 39681ad6265SDimitry Andric PointerValue &getOrCreateNullPointerValue(QualType PointeeType); 39781ad6265SDimitry Andric 39804eeddc0SDimitry Andric /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise 39906c3fb27SDimitry Andric /// returns null. 40006c3fb27SDimitry Andric /// 40106c3fb27SDimitry Andric /// If `Type` is a pointer or reference type, creates all the necessary 40206c3fb27SDimitry Andric /// storage locations and values for indirections until it finds a 40304eeddc0SDimitry Andric /// non-pointer/non-reference type. 40404eeddc0SDimitry Andric /// 4055f757f3fSDimitry Andric /// If `Type` is a class, struct, or union type, creates values for all 4065f757f3fSDimitry Andric /// modeled fields (including synthetic fields) and calls `setValue()` to 4075f757f3fSDimitry Andric /// associate the `RecordValue` with its storage location 4085f757f3fSDimitry Andric /// (`RecordValue::getLoc()`). 40906c3fb27SDimitry Andric /// 41006c3fb27SDimitry Andric /// If `Type` is one of the following types, this function will always return 41106c3fb27SDimitry Andric /// a non-null pointer: 41206c3fb27SDimitry Andric /// - `bool` 41306c3fb27SDimitry Andric /// - Any integer type 41406c3fb27SDimitry Andric /// - Any class, struct, or union type 41506c3fb27SDimitry Andric /// 41604eeddc0SDimitry Andric /// Requirements: 41704eeddc0SDimitry Andric /// 41804eeddc0SDimitry Andric /// `Type` must not be null. 41904eeddc0SDimitry Andric Value *createValue(QualType Type); 42004eeddc0SDimitry Andric 42106c3fb27SDimitry Andric /// Creates an object (i.e. a storage location with an associated value) of 42206c3fb27SDimitry Andric /// type `Ty`. If `InitExpr` is non-null and has a value associated with it, 42306c3fb27SDimitry Andric /// initializes the object with this value. Otherwise, initializes the object 42406c3fb27SDimitry Andric /// with a value created using `createValue()`. 42506c3fb27SDimitry Andric StorageLocation &createObject(QualType Ty, const Expr *InitExpr = nullptr) { 42606c3fb27SDimitry Andric return createObjectInternal(nullptr, Ty, InitExpr); 42706c3fb27SDimitry Andric } 42806c3fb27SDimitry Andric 42906c3fb27SDimitry Andric /// Creates an object for the variable declaration `D`. If `D` has an 43006c3fb27SDimitry Andric /// initializer and this initializer is associated with a value, initializes 43106c3fb27SDimitry Andric /// the object with this value. Otherwise, initializes the object with a 43206c3fb27SDimitry Andric /// value created using `createValue()`. Uses the storage location returned by 43306c3fb27SDimitry Andric /// `DataflowAnalysisContext::getStableStorageLocation(D)`. createObject(const VarDecl & D)43406c3fb27SDimitry Andric StorageLocation &createObject(const VarDecl &D) { 43506c3fb27SDimitry Andric return createObjectInternal(&D, D.getType(), D.getInit()); 43606c3fb27SDimitry Andric } 43706c3fb27SDimitry Andric 43806c3fb27SDimitry Andric /// Creates an object for the variable declaration `D`. If `InitExpr` is 43906c3fb27SDimitry Andric /// non-null and has a value associated with it, initializes the object with 44006c3fb27SDimitry Andric /// this value. Otherwise, initializes the object with a value created using 44106c3fb27SDimitry Andric /// `createValue()`. Uses the storage location returned by 44206c3fb27SDimitry Andric /// `DataflowAnalysisContext::getStableStorageLocation(D)`. createObject(const ValueDecl & D,const Expr * InitExpr)4435f757f3fSDimitry Andric StorageLocation &createObject(const ValueDecl &D, const Expr *InitExpr) { 44406c3fb27SDimitry Andric return createObjectInternal(&D, D.getType(), InitExpr); 44506c3fb27SDimitry Andric } 44606c3fb27SDimitry Andric 44704eeddc0SDimitry Andric /// Assigns `Val` as the value of `Loc` in the environment. 44804eeddc0SDimitry Andric void setValue(const StorageLocation &Loc, Value &Val); 44904eeddc0SDimitry Andric 45006c3fb27SDimitry Andric /// Clears any association between `Loc` and a value in the environment. clearValue(const StorageLocation & Loc)45106c3fb27SDimitry Andric void clearValue(const StorageLocation &Loc) { LocToVal.erase(&Loc); } 45206c3fb27SDimitry Andric 45306c3fb27SDimitry Andric /// Assigns `Val` as the value of the prvalue `E` in the environment. 45406c3fb27SDimitry Andric /// 45506c3fb27SDimitry Andric /// Requirements: 45606c3fb27SDimitry Andric /// 457cb14a3feSDimitry Andric /// - `E` must be a prvalue 458cb14a3feSDimitry Andric /// - If `Val` is a `RecordValue`, its `RecordStorageLocation` must be 459cb14a3feSDimitry Andric /// `getResultObjectLocation(E)`. An exception to this is if `E` is an 460cb14a3feSDimitry Andric /// expression that originally creates a `RecordValue` (such as a 461cb14a3feSDimitry Andric /// `CXXConstructExpr` or `CallExpr`), as these establish the location of 462cb14a3feSDimitry Andric /// the result object in the first place. 4635f757f3fSDimitry Andric void setValue(const Expr &E, Value &Val); 46406c3fb27SDimitry Andric 46504eeddc0SDimitry Andric /// Returns the value assigned to `Loc` in the environment or null if `Loc` 46604eeddc0SDimitry Andric /// isn't assigned a value in the environment. 46704eeddc0SDimitry Andric Value *getValue(const StorageLocation &Loc) const; 46804eeddc0SDimitry Andric 4695f757f3fSDimitry Andric /// Equivalent to `getValue(getStorageLocation(D))` if `D` is assigned a 4705f757f3fSDimitry Andric /// storage location in the environment, otherwise returns null. 47106c3fb27SDimitry Andric Value *getValue(const ValueDecl &D) const; 47204eeddc0SDimitry Andric 4735f757f3fSDimitry Andric /// Equivalent to `getValue(getStorageLocation(E, SP))` if `E` is assigned a 4745f757f3fSDimitry Andric /// storage location in the environment, otherwise returns null. 4755f757f3fSDimitry Andric Value *getValue(const Expr &E) const; 47606c3fb27SDimitry Andric 477cb14a3feSDimitry Andric /// Returns the result of casting `getValue(...)` to a subclass of `Value` 478cb14a3feSDimitry Andric /// (using `cast_or_null<T>`). 479cb14a3feSDimitry Andric /// This assert-fails if the result of `getValue(...)` is not of type `T *`; 480cb14a3feSDimitry Andric /// if the value is not guaranteed to have type `T *`, consider using 481cb14a3feSDimitry Andric /// `dyn_cast_or_null<T>(getValue(...))` instead. 482cb14a3feSDimitry Andric template <typename T> 483cb14a3feSDimitry Andric std::enable_if_t<std::is_base_of_v<Value, T>, T *> get(const StorageLocation & Loc)484cb14a3feSDimitry Andric get(const StorageLocation &Loc) const { 485cb14a3feSDimitry Andric return cast_or_null<T>(getValue(Loc)); 486cb14a3feSDimitry Andric } 487cb14a3feSDimitry Andric template <typename T> 488cb14a3feSDimitry Andric std::enable_if_t<std::is_base_of_v<Value, T>, T *> get(const ValueDecl & D)489cb14a3feSDimitry Andric get(const ValueDecl &D) const { 490cb14a3feSDimitry Andric return cast_or_null<T>(getValue(D)); 491cb14a3feSDimitry Andric } 492cb14a3feSDimitry Andric template <typename T> get(const Expr & E)493cb14a3feSDimitry Andric std::enable_if_t<std::is_base_of_v<Value, T>, T *> get(const Expr &E) const { 494cb14a3feSDimitry Andric return cast_or_null<T>(getValue(E)); 495cb14a3feSDimitry Andric } 496cb14a3feSDimitry Andric 49706c3fb27SDimitry Andric // FIXME: should we deprecate the following & call arena().create() directly? 49806c3fb27SDimitry Andric 49906c3fb27SDimitry Andric /// Creates a `T` (some subclass of `Value`), forwarding `args` to the 50006c3fb27SDimitry Andric /// constructor, and returns a reference to it. 50106c3fb27SDimitry Andric /// 50206c3fb27SDimitry Andric /// The analysis context takes ownership of the created object. The object 50306c3fb27SDimitry Andric /// will be destroyed when the analysis context is destroyed. 50406c3fb27SDimitry Andric template <typename T, typename... Args> 50506c3fb27SDimitry Andric std::enable_if_t<std::is_base_of<Value, T>::value, T &> create(Args &&...args)50606c3fb27SDimitry Andric create(Args &&...args) { 50706c3fb27SDimitry Andric return arena().create<T>(std::forward<Args>(args)...); 50804eeddc0SDimitry Andric } 50904eeddc0SDimitry Andric 51006c3fb27SDimitry Andric /// Returns a symbolic integer value that models an integer literal equal to 51106c3fb27SDimitry Andric /// `Value` getIntLiteralValue(llvm::APInt Value)51206c3fb27SDimitry Andric IntegerValue &getIntLiteralValue(llvm::APInt Value) const { 51306c3fb27SDimitry Andric return arena().makeIntLiteral(Value); 51404eeddc0SDimitry Andric } 51504eeddc0SDimitry Andric 51604eeddc0SDimitry Andric /// Returns a symbolic boolean value that models a boolean literal equal to 51704eeddc0SDimitry Andric /// `Value` getBoolLiteralValue(bool Value)5185f757f3fSDimitry Andric BoolValue &getBoolLiteralValue(bool Value) const { 5195f757f3fSDimitry Andric return arena().makeBoolValue(arena().makeLiteral(Value)); 52004eeddc0SDimitry Andric } 52104eeddc0SDimitry Andric 52281ad6265SDimitry Andric /// Returns an atomic boolean value. makeAtomicBoolValue()52381ad6265SDimitry Andric BoolValue &makeAtomicBoolValue() const { 52406c3fb27SDimitry Andric return arena().makeAtomValue(); 52581ad6265SDimitry Andric } 52681ad6265SDimitry Andric 527bdd1243dSDimitry Andric /// Returns a unique instance of boolean Top. makeTopBoolValue()528bdd1243dSDimitry Andric BoolValue &makeTopBoolValue() const { 52906c3fb27SDimitry Andric return arena().makeTopValue(); 530bdd1243dSDimitry Andric } 531bdd1243dSDimitry Andric 53281ad6265SDimitry Andric /// Returns a boolean value that represents the conjunction of `LHS` and 53381ad6265SDimitry Andric /// `RHS`. Subsequent calls with the same arguments, regardless of their 53481ad6265SDimitry Andric /// order, will return the same result. If the given boolean values represent 53581ad6265SDimitry Andric /// the same value, the result will be the value itself. makeAnd(BoolValue & LHS,BoolValue & RHS)53681ad6265SDimitry Andric BoolValue &makeAnd(BoolValue &LHS, BoolValue &RHS) const { 53706c3fb27SDimitry Andric return arena().makeBoolValue( 53806c3fb27SDimitry Andric arena().makeAnd(LHS.formula(), RHS.formula())); 53981ad6265SDimitry Andric } 54081ad6265SDimitry Andric 54181ad6265SDimitry Andric /// Returns a boolean value that represents the disjunction of `LHS` and 54281ad6265SDimitry Andric /// `RHS`. Subsequent calls with the same arguments, regardless of their 54381ad6265SDimitry Andric /// order, will return the same result. If the given boolean values represent 54481ad6265SDimitry Andric /// the same value, the result will be the value itself. makeOr(BoolValue & LHS,BoolValue & RHS)54581ad6265SDimitry Andric BoolValue &makeOr(BoolValue &LHS, BoolValue &RHS) const { 54606c3fb27SDimitry Andric return arena().makeBoolValue( 54706c3fb27SDimitry Andric arena().makeOr(LHS.formula(), RHS.formula())); 54881ad6265SDimitry Andric } 54981ad6265SDimitry Andric 55081ad6265SDimitry Andric /// Returns a boolean value that represents the negation of `Val`. Subsequent 55181ad6265SDimitry Andric /// calls with the same argument will return the same result. makeNot(BoolValue & Val)55281ad6265SDimitry Andric BoolValue &makeNot(BoolValue &Val) const { 55306c3fb27SDimitry Andric return arena().makeBoolValue(arena().makeNot(Val.formula())); 55481ad6265SDimitry Andric } 55581ad6265SDimitry Andric 55681ad6265SDimitry Andric /// Returns a boolean value represents `LHS` => `RHS`. Subsequent calls with 55781ad6265SDimitry Andric /// the same arguments, will return the same result. If the given boolean 55881ad6265SDimitry Andric /// values represent the same value, the result will be a value that 55981ad6265SDimitry Andric /// represents the true boolean literal. makeImplication(BoolValue & LHS,BoolValue & RHS)56081ad6265SDimitry Andric BoolValue &makeImplication(BoolValue &LHS, BoolValue &RHS) const { 56106c3fb27SDimitry Andric return arena().makeBoolValue( 56206c3fb27SDimitry Andric arena().makeImplies(LHS.formula(), RHS.formula())); 56381ad6265SDimitry Andric } 56481ad6265SDimitry Andric 56581ad6265SDimitry Andric /// Returns a boolean value represents `LHS` <=> `RHS`. Subsequent calls with 56681ad6265SDimitry Andric /// the same arguments, regardless of their order, will return the same 56781ad6265SDimitry Andric /// result. If the given boolean values represent the same value, the result 56881ad6265SDimitry Andric /// will be a value that represents the true boolean literal. makeIff(BoolValue & LHS,BoolValue & RHS)56981ad6265SDimitry Andric BoolValue &makeIff(BoolValue &LHS, BoolValue &RHS) const { 57006c3fb27SDimitry Andric return arena().makeBoolValue( 57106c3fb27SDimitry Andric arena().makeEquals(LHS.formula(), RHS.formula())); 57281ad6265SDimitry Andric } 57381ad6265SDimitry Andric 57406c3fb27SDimitry Andric /// Returns a boolean variable that identifies the flow condition (FC). 57506c3fb27SDimitry Andric /// 57606c3fb27SDimitry Andric /// The flow condition is a set of facts that are necessarily true when the 57706c3fb27SDimitry Andric /// program reaches the current point, expressed as boolean formulas. 57806c3fb27SDimitry Andric /// The flow condition token is equivalent to the AND of these facts. 57906c3fb27SDimitry Andric /// 58006c3fb27SDimitry Andric /// These may e.g. constrain the value of certain variables. A pointer 58106c3fb27SDimitry Andric /// variable may have a consistent modeled PointerValue throughout, but at a 58206c3fb27SDimitry Andric /// given point the Environment may tell us that the value must be non-null. 58306c3fb27SDimitry Andric /// 58406c3fb27SDimitry Andric /// The FC is necessary but not sufficient for this point to be reachable. 58506c3fb27SDimitry Andric /// In particular, where the FC token appears in flow conditions of successor 58606c3fb27SDimitry Andric /// environments, it means "point X may have been reached", not 58706c3fb27SDimitry Andric /// "point X was reached". getFlowConditionToken()58806c3fb27SDimitry Andric Atom getFlowConditionToken() const { return FlowConditionToken; } 58981ad6265SDimitry Andric 59006c3fb27SDimitry Andric /// Record a fact that must be true if this point in the program is reached. 5915f757f3fSDimitry Andric void assume(const Formula &); 59281ad6265SDimitry Andric 59306c3fb27SDimitry Andric /// Returns true if the formula is always true when this point is reached. 5945f757f3fSDimitry Andric /// Returns false if the formula may be false (or the flow condition isn't 5955f757f3fSDimitry Andric /// sufficiently precise to prove that it is true) or if the solver times out. 5965f757f3fSDimitry Andric /// 5975f757f3fSDimitry Andric /// Note that there is an asymmetry between this function and `allows()` in 5985f757f3fSDimitry Andric /// that they both return false if the solver times out. The assumption is 5995f757f3fSDimitry Andric /// that if `proves()` or `allows()` returns true, this will result in a 6005f757f3fSDimitry Andric /// diagnostic, and we want to bias towards false negatives in the case where 6015f757f3fSDimitry Andric /// the solver times out. 6025f757f3fSDimitry Andric bool proves(const Formula &) const; 6035f757f3fSDimitry Andric 6045f757f3fSDimitry Andric /// Returns true if the formula may be true when this point is reached. 6055f757f3fSDimitry Andric /// Returns false if the formula is always false when this point is reached 6065f757f3fSDimitry Andric /// (or the flow condition is overly constraining) or if the solver times out. 6075f757f3fSDimitry Andric bool allows(const Formula &) const; 60881ad6265SDimitry Andric 609bdd1243dSDimitry Andric /// Returns the `DeclContext` of the block being analysed, if any. Otherwise, 610bdd1243dSDimitry Andric /// returns null. getDeclCtx()611bdd1243dSDimitry Andric const DeclContext *getDeclCtx() const { return CallStack.back(); } 612bdd1243dSDimitry Andric 61306c3fb27SDimitry Andric /// Returns the function currently being analyzed, or null if the code being 61406c3fb27SDimitry Andric /// analyzed isn't part of a function. getCurrentFunc()61506c3fb27SDimitry Andric const FunctionDecl *getCurrentFunc() const { 61606c3fb27SDimitry Andric return dyn_cast<FunctionDecl>(getDeclCtx()); 61706c3fb27SDimitry Andric } 61806c3fb27SDimitry Andric 6195f757f3fSDimitry Andric /// Returns the size of the call stack. callStackSize()6205f757f3fSDimitry Andric size_t callStackSize() const { return CallStack.size(); } 6215f757f3fSDimitry Andric 622bdd1243dSDimitry Andric /// Returns whether this `Environment` can be extended to analyze the given 623bdd1243dSDimitry Andric /// `Callee` (i.e. if `pushCall` can be used), with recursion disallowed and a 624bdd1243dSDimitry Andric /// given `MaxDepth`. 625bdd1243dSDimitry Andric bool canDescend(unsigned MaxDepth, const DeclContext *Callee) const; 626bdd1243dSDimitry Andric 62706c3fb27SDimitry Andric /// Returns the `DataflowAnalysisContext` used by the environment. getDataflowAnalysisContext()62806c3fb27SDimitry Andric DataflowAnalysisContext &getDataflowAnalysisContext() const { return *DACtx; } 62906c3fb27SDimitry Andric arena()63006c3fb27SDimitry Andric Arena &arena() const { return DACtx->arena(); } 631bdd1243dSDimitry Andric 632fcaf7f86SDimitry Andric LLVM_DUMP_METHOD void dump() const; 633bdd1243dSDimitry Andric LLVM_DUMP_METHOD void dump(raw_ostream &OS) const; 634fcaf7f86SDimitry Andric 63504eeddc0SDimitry Andric private: 63606c3fb27SDimitry Andric // The copy-constructor is for use in fork() only. 63706c3fb27SDimitry Andric Environment(const Environment &) = default; 63806c3fb27SDimitry Andric 63904eeddc0SDimitry Andric /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise 64004eeddc0SDimitry Andric /// return null. 64104eeddc0SDimitry Andric /// 64204eeddc0SDimitry Andric /// Recursively initializes storage locations and values until it sees a 64304eeddc0SDimitry Andric /// self-referential pointer or reference type. `Visited` is used to track 64404eeddc0SDimitry Andric /// which types appeared in the reference/pointer chain in order to avoid 64504eeddc0SDimitry Andric /// creating a cyclic dependency with self-referential pointers/references. 64604eeddc0SDimitry Andric /// 64704eeddc0SDimitry Andric /// Requirements: 64804eeddc0SDimitry Andric /// 64904eeddc0SDimitry Andric /// `Type` must not be null. 65004eeddc0SDimitry Andric Value *createValueUnlessSelfReferential(QualType Type, 65181ad6265SDimitry Andric llvm::DenseSet<QualType> &Visited, 65281ad6265SDimitry Andric int Depth, int &CreatedValuesCount); 65304eeddc0SDimitry Andric 65406c3fb27SDimitry Andric /// Creates a storage location for `Ty`. Also creates and associates a value 65506c3fb27SDimitry Andric /// with the storage location, unless values of this type are not supported or 65606c3fb27SDimitry Andric /// we hit one of the limits at which we stop producing values (controlled by 65706c3fb27SDimitry Andric /// `Visited`, `Depth`, and `CreatedValuesCount`). 65806c3fb27SDimitry Andric StorageLocation &createLocAndMaybeValue(QualType Ty, 65906c3fb27SDimitry Andric llvm::DenseSet<QualType> &Visited, 66006c3fb27SDimitry Andric int Depth, int &CreatedValuesCount); 66106c3fb27SDimitry Andric 66206c3fb27SDimitry Andric /// Shared implementation of `createObject()` overloads. 66306c3fb27SDimitry Andric /// `D` and `InitExpr` may be null. 6645f757f3fSDimitry Andric StorageLocation &createObjectInternal(const ValueDecl *D, QualType Ty, 66506c3fb27SDimitry Andric const Expr *InitExpr); 66606c3fb27SDimitry Andric 667bdd1243dSDimitry Andric /// Shared implementation of `pushCall` overloads. Note that unlike 668bdd1243dSDimitry Andric /// `pushCall`, this member is invoked on the environment of the callee, not 669bdd1243dSDimitry Andric /// of the caller. 670bdd1243dSDimitry Andric void pushCallInternal(const FunctionDecl *FuncDecl, 671bdd1243dSDimitry Andric ArrayRef<const Expr *> Args); 672bdd1243dSDimitry Andric 67306c3fb27SDimitry Andric /// Assigns storage locations and values to all global variables, fields 67406c3fb27SDimitry Andric /// and functions referenced in `FuncDecl`. `FuncDecl` must have a body. 67506c3fb27SDimitry Andric void initFieldsGlobalsAndFuncs(const FunctionDecl *FuncDecl); 676bdd1243dSDimitry Andric 67704eeddc0SDimitry Andric // `DACtx` is not null and not owned by this object. 67804eeddc0SDimitry Andric DataflowAnalysisContext *DACtx; 67904eeddc0SDimitry Andric 68006c3fb27SDimitry Andric // FIXME: move the fields `CallStack`, `ReturnVal`, `ReturnLoc` and 68106c3fb27SDimitry Andric // `ThisPointeeLoc` into a separate call-context object, shared between 68206c3fb27SDimitry Andric // environments in the same call. 683bdd1243dSDimitry Andric // https://github.com/llvm/llvm-project/issues/59005 684bdd1243dSDimitry Andric 685bdd1243dSDimitry Andric // `DeclContext` of the block being analysed if provided. 686bdd1243dSDimitry Andric std::vector<const DeclContext *> CallStack; 687bdd1243dSDimitry Andric 68806c3fb27SDimitry Andric // Value returned by the function (if it has non-reference return type). 68906c3fb27SDimitry Andric Value *ReturnVal = nullptr; 69006c3fb27SDimitry Andric // Storage location of the reference returned by the function (if it has 69106c3fb27SDimitry Andric // reference return type). 692bdd1243dSDimitry Andric StorageLocation *ReturnLoc = nullptr; 693bdd1243dSDimitry Andric // The storage location of the `this` pointee. Should only be null if the 694bdd1243dSDimitry Andric // function being analyzed is only a function and not a method. 6955f757f3fSDimitry Andric RecordStorageLocation *ThisPointeeLoc = nullptr; 696bdd1243dSDimitry Andric 6975f757f3fSDimitry Andric // Maps from declarations and glvalue expression to storage locations that are 69804eeddc0SDimitry Andric // assigned to them. Unlike the maps in `DataflowAnalysisContext`, these 69904eeddc0SDimitry Andric // include only storage locations that are in scope for a particular basic 70004eeddc0SDimitry Andric // block. 70104eeddc0SDimitry Andric llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc; 70204eeddc0SDimitry Andric llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc; 7035f757f3fSDimitry Andric // Maps from prvalue expressions and storage locations to the values that 7045f757f3fSDimitry Andric // are assigned to them. 70506c3fb27SDimitry Andric // We preserve insertion order so that join/widen process values in 70606c3fb27SDimitry Andric // deterministic sequence. This in turn produces deterministic SAT formulas. 7075f757f3fSDimitry Andric llvm::MapVector<const Expr *, Value *> ExprToVal; 70806c3fb27SDimitry Andric llvm::MapVector<const StorageLocation *, Value *> LocToVal; 70904eeddc0SDimitry Andric 71006c3fb27SDimitry Andric Atom FlowConditionToken; 71104eeddc0SDimitry Andric }; 71204eeddc0SDimitry Andric 71306c3fb27SDimitry Andric /// Returns the storage location for the implicit object of a 71406c3fb27SDimitry Andric /// `CXXMemberCallExpr`, or null if none is defined in the environment. 71506c3fb27SDimitry Andric /// Dereferences the pointer if the member call expression was written using 71606c3fb27SDimitry Andric /// `->`. 7175f757f3fSDimitry Andric RecordStorageLocation *getImplicitObjectLocation(const CXXMemberCallExpr &MCE, 7185f757f3fSDimitry Andric const Environment &Env); 71906c3fb27SDimitry Andric 72006c3fb27SDimitry Andric /// Returns the storage location for the base object of a `MemberExpr`, or null 72106c3fb27SDimitry Andric /// if none is defined in the environment. Dereferences the pointer if the 72206c3fb27SDimitry Andric /// member expression was written using `->`. 7235f757f3fSDimitry Andric RecordStorageLocation *getBaseObjectLocation(const MemberExpr &ME, 72406c3fb27SDimitry Andric const Environment &Env); 72506c3fb27SDimitry Andric 72606c3fb27SDimitry Andric /// Returns the fields of `RD` that are initialized by an `InitListExpr`, in the 72706c3fb27SDimitry Andric /// order in which they appear in `InitListExpr::inits()`. 72806c3fb27SDimitry Andric std::vector<FieldDecl *> getFieldsForInitListExpr(const RecordDecl *RD); 72906c3fb27SDimitry Andric 7305f757f3fSDimitry Andric /// Associates a new `RecordValue` with `Loc` and returns the new value. 7315f757f3fSDimitry Andric RecordValue &refreshRecordValue(RecordStorageLocation &Loc, Environment &Env); 73206c3fb27SDimitry Andric 7335f757f3fSDimitry Andric /// Associates a new `RecordValue` with `Expr` and returns the new value. 7345f757f3fSDimitry Andric RecordValue &refreshRecordValue(const Expr &Expr, Environment &Env); 73506c3fb27SDimitry Andric 7364824e7fdSDimitry Andric } // namespace dataflow 7374824e7fdSDimitry Andric } // namespace clang 7384824e7fdSDimitry Andric 7394824e7fdSDimitry Andric #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H 740