1 //===-- DataflowEnvironment.h -----------------------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines an Environment class that is used by dataflow analyses 10 // that run over Control-Flow Graphs (CFGs) to keep track of the state of the 11 // program at given program points. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H 16 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H 17 18 #include "clang/AST/Decl.h" 19 #include "clang/AST/DeclBase.h" 20 #include "clang/AST/Expr.h" 21 #include "clang/AST/Type.h" 22 #include "clang/AST/TypeOrdering.h" 23 #include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h" 24 #include "clang/Analysis/FlowSensitive/DataflowLattice.h" 25 #include "clang/Analysis/FlowSensitive/StorageLocation.h" 26 #include "clang/Analysis/FlowSensitive/Value.h" 27 #include "llvm/ADT/DenseMap.h" 28 #include "llvm/ADT/DenseSet.h" 29 #include <memory> 30 #include <type_traits> 31 #include <utility> 32 33 namespace clang { 34 namespace dataflow { 35 36 /// Indicates what kind of indirections should be skipped past when retrieving 37 /// storage locations or values. 38 /// 39 /// FIXME: Consider renaming this or replacing it with a more appropriate model. 40 /// See the discussion in https://reviews.llvm.org/D116596 for context. 41 enum class SkipPast { 42 /// No indirections should be skipped past. 43 None, 44 /// An optional reference should be skipped past. 45 Reference, 46 /// An optional reference should be skipped past, then an optional pointer 47 /// should be skipped past. 48 ReferenceThenPointer, 49 }; 50 51 /// Holds the state of the program (store and heap) at a given program point. 52 class Environment { 53 public: 54 /// Supplements `Environment` with non-standard comparison and join 55 /// operations. 56 class ValueModel { 57 public: 58 virtual ~ValueModel() = default; 59 60 /// Returns true if and only if `Val1` is equivalent to `Val2`. 61 /// 62 /// Requirements: 63 /// 64 /// `Val1` and `Val2` must be distinct. 65 /// 66 /// `Val1` and `Val2` must model values of type `Type`. 67 virtual bool compareEquivalent(QualType Type, const Value &Val1, 68 const Value &Val2) { 69 // FIXME: Consider adding QualType to StructValue and removing the Type 70 // argument here. 71 return false; 72 } 73 74 /// Modifies `MergedVal` to approximate both `Val1` and `Val2`. This could 75 /// be a strict lattice join or a more general widening operation. If this 76 /// function returns true, `MergedVal` will be assigned to a storage 77 /// location of type `Type` in `Env`. 78 /// 79 /// Requirements: 80 /// 81 /// `Val1` and `Val2` must be distinct. 82 /// 83 /// `Val1`, `Val2`, and `MergedVal` must model values of type `Type`. 84 virtual bool merge(QualType Type, const Value &Val1, const Value &Val2, 85 Value &MergedVal, Environment &Env) { 86 return false; 87 } 88 }; 89 90 /// Creates an environment that uses `DACtx` to store objects that encompass 91 /// the state of a program. 92 explicit Environment(DataflowAnalysisContext &DACtx) : DACtx(&DACtx) {} 93 94 /// Creates an environment that uses `DACtx` to store objects that encompass 95 /// the state of a program. 96 /// 97 /// If `DeclCtx` is a function, initializes the environment with symbolic 98 /// representations of the function parameters. 99 /// 100 /// If `DeclCtx` is a non-static member function, initializes the environment 101 /// with a symbolic representation of the `this` pointee. 102 Environment(DataflowAnalysisContext &DACtx, const DeclContext &DeclCtx); 103 104 /// Returns true if and only if the environment is equivalent to `Other`, i.e 105 /// the two environments: 106 /// - have the same mappings from declarations to storage locations, 107 /// - have the same mappings from expressions to storage locations, 108 /// - have the same or equivalent (according to `Model`) values assigned to 109 /// the same storage locations. 110 /// 111 /// Requirements: 112 /// 113 /// `Other` and `this` must use the same `DataflowAnalysisContext`. 114 bool equivalentTo(const Environment &Other, 115 Environment::ValueModel &Model) const; 116 117 /// Joins the environment with `Other` by taking the intersection of storage 118 /// locations and values that are stored in them. Distinct values that are 119 /// assigned to the same storage locations in the environment and `Other` are 120 /// merged using `Model`. 121 /// 122 /// Requirements: 123 /// 124 /// `Other` and `this` must use the same `DataflowAnalysisContext`. 125 LatticeJoinEffect join(const Environment &Other, 126 Environment::ValueModel &Model); 127 128 // FIXME: Rename `createOrGetStorageLocation` to `getOrCreateStorageLocation`, 129 // `getStableStorageLocation`, or something more appropriate. 130 131 /// Creates a storage location appropriate for `Type`. Does not assign a value 132 /// to the returned storage location in the environment. 133 /// 134 /// Requirements: 135 /// 136 /// `Type` must not be null. 137 StorageLocation &createStorageLocation(QualType Type); 138 139 /// Creates a storage location for `D`. Does not assign the returned storage 140 /// location to `D` in the environment. Does not assign a value to the 141 /// returned storage location in the environment. 142 StorageLocation &createStorageLocation(const VarDecl &D); 143 144 /// Creates a storage location for `E`. Does not assign the returned storage 145 /// location to `E` in the environment. Does not assign a value to the 146 /// returned storage location in the environment. 147 StorageLocation &createStorageLocation(const Expr &E); 148 149 /// Assigns `Loc` as the storage location of `D` in the environment. 150 /// 151 /// Requirements: 152 /// 153 /// `D` must not be assigned a storage location in the environment. 154 void setStorageLocation(const ValueDecl &D, StorageLocation &Loc); 155 156 /// Returns the storage location assigned to `D` in the environment, applying 157 /// the `SP` policy for skipping past indirections, or null if `D` isn't 158 /// assigned a storage location in the environment. 159 StorageLocation *getStorageLocation(const ValueDecl &D, SkipPast SP) const; 160 161 /// Assigns `Loc` as the storage location of `E` in the environment. 162 /// 163 /// Requirements: 164 /// 165 /// `E` must not be assigned a storage location in the environment. 166 void setStorageLocation(const Expr &E, StorageLocation &Loc); 167 168 /// Returns the storage location assigned to `E` in the environment, applying 169 /// the `SP` policy for skipping past indirections, or null if `E` isn't 170 /// assigned a storage location in the environment. 171 StorageLocation *getStorageLocation(const Expr &E, SkipPast SP) const; 172 173 /// Returns the storage location assigned to the `this` pointee in the 174 /// environment or null if the `this` pointee has no assigned storage location 175 /// in the environment. 176 StorageLocation *getThisPointeeStorageLocation() const; 177 178 /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise 179 /// return null. If `Type` is a pointer or reference type, creates all the 180 /// necessary storage locations and values for indirections until it finds a 181 /// non-pointer/non-reference type. 182 /// 183 /// Requirements: 184 /// 185 /// `Type` must not be null. 186 Value *createValue(QualType Type); 187 188 /// Assigns `Val` as the value of `Loc` in the environment. 189 void setValue(const StorageLocation &Loc, Value &Val); 190 191 /// Returns the value assigned to `Loc` in the environment or null if `Loc` 192 /// isn't assigned a value in the environment. 193 Value *getValue(const StorageLocation &Loc) const; 194 195 /// Equivalent to `getValue(getStorageLocation(D, SP), SkipPast::None)` if `D` 196 /// is assigned a storage location in the environment, otherwise returns null. 197 Value *getValue(const ValueDecl &D, SkipPast SP) const; 198 199 /// Equivalent to `getValue(getStorageLocation(E, SP), SkipPast::None)` if `E` 200 /// is assigned a storage location in the environment, otherwise returns null. 201 Value *getValue(const Expr &E, SkipPast SP) const; 202 203 /// Transfers ownership of `Loc` to the analysis context and returns a 204 /// reference to it. 205 /// 206 /// Requirements: 207 /// 208 /// `Loc` must not be null. 209 template <typename T> 210 typename std::enable_if<std::is_base_of<StorageLocation, T>::value, T &>::type 211 takeOwnership(std::unique_ptr<T> Loc) { 212 return DACtx->takeOwnership(std::move(Loc)); 213 } 214 215 /// Transfers ownership of `Val` to the analysis context and returns a 216 /// reference to it. 217 /// 218 /// Requirements: 219 /// 220 /// `Val` must not be null. 221 template <typename T> 222 typename std::enable_if<std::is_base_of<Value, T>::value, T &>::type 223 takeOwnership(std::unique_ptr<T> Val) { 224 return DACtx->takeOwnership(std::move(Val)); 225 } 226 227 /// Returns a symbolic boolean value that models a boolean literal equal to 228 /// `Value` 229 BoolValue &getBoolLiteralValue(bool Value) const { 230 return DACtx->getBoolLiteralValue(Value); 231 } 232 233 private: 234 /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise 235 /// return null. 236 /// 237 /// Recursively initializes storage locations and values until it sees a 238 /// self-referential pointer or reference type. `Visited` is used to track 239 /// which types appeared in the reference/pointer chain in order to avoid 240 /// creating a cyclic dependency with self-referential pointers/references. 241 /// 242 /// Requirements: 243 /// 244 /// `Type` must not be null. 245 Value *createValueUnlessSelfReferential(QualType Type, 246 llvm::DenseSet<QualType> &Visited); 247 248 StorageLocation &skip(StorageLocation &Loc, SkipPast SP) const; 249 const StorageLocation &skip(const StorageLocation &Loc, SkipPast SP) const; 250 251 // `DACtx` is not null and not owned by this object. 252 DataflowAnalysisContext *DACtx; 253 254 // Maps from program declarations and statements to storage locations that are 255 // assigned to them. Unlike the maps in `DataflowAnalysisContext`, these 256 // include only storage locations that are in scope for a particular basic 257 // block. 258 llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc; 259 llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc; 260 261 llvm::DenseMap<const StorageLocation *, Value *> LocToVal; 262 263 // FIXME: Add flow condition constraints. 264 }; 265 266 } // namespace dataflow 267 } // namespace clang 268 269 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H 270