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 /// 53 /// WARNING: Symbolic values that are created by the environment for static 54 /// local and global variables are not currently invalidated on function calls. 55 /// This is unsound and should be taken into account when designing dataflow 56 /// analyses. 57 class Environment { 58 public: 59 /// Supplements `Environment` with non-standard comparison and join 60 /// operations. 61 class ValueModel { 62 public: 63 virtual ~ValueModel() = default; 64 65 /// Returns true if and only if `Val1` is equivalent to `Val2`. 66 /// 67 /// Requirements: 68 /// 69 /// `Val1` and `Val2` must be distinct. 70 /// 71 /// `Val1` and `Val2` must model values of type `Type`. 72 /// 73 /// `Val1` and `Val2` must be assigned to the same storage location in 74 /// `Env1` and `Env2` respectively. 75 virtual bool compareEquivalent(QualType Type, const Value &Val1, 76 const Environment &Env1, const Value &Val2, 77 const Environment &Env2) { 78 // FIXME: Consider adding QualType to StructValue and removing the Type 79 // argument here. 80 // 81 // FIXME: default to a sound comparison and/or expand the comparison logic 82 // built into the framework to support broader forms of equivalence than 83 // strict pointer equality. 84 return true; 85 } 86 87 /// Modifies `MergedVal` to approximate both `Val1` and `Val2`. This could 88 /// be a strict lattice join or a more general widening operation. 89 /// 90 /// If this function returns true, `MergedVal` will be assigned to a storage 91 /// location of type `Type` in `MergedEnv`. 92 /// 93 /// `Env1` and `Env2` can be used to query child values and path condition 94 /// implications of `Val1` and `Val2` respectively. 95 /// 96 /// Requirements: 97 /// 98 /// `Val1` and `Val2` must be distinct. 99 /// 100 /// `Val1`, `Val2`, and `MergedVal` must model values of type `Type`. 101 /// 102 /// `Val1` and `Val2` must be assigned to the same storage location in 103 /// `Env1` and `Env2` respectively. 104 virtual bool merge(QualType Type, const Value &Val1, 105 const Environment &Env1, const Value &Val2, 106 const Environment &Env2, Value &MergedVal, 107 Environment &MergedEnv) { 108 return true; 109 } 110 }; 111 112 /// Creates an environment that uses `DACtx` to store objects that encompass 113 /// the state of a program. 114 explicit Environment(DataflowAnalysisContext &DACtx); 115 116 Environment(const Environment &Other); 117 Environment &operator=(const Environment &Other); 118 119 Environment(Environment &&Other) = default; 120 Environment &operator=(Environment &&Other) = default; 121 122 /// Creates an environment that uses `DACtx` to store objects that encompass 123 /// the state of a program. 124 /// 125 /// If `DeclCtx` is a function, initializes the environment with symbolic 126 /// representations of the function parameters. 127 /// 128 /// If `DeclCtx` is a non-static member function, initializes the environment 129 /// with a symbolic representation of the `this` pointee. 130 Environment(DataflowAnalysisContext &DACtx, const DeclContext &DeclCtx); 131 132 /// Returns true if and only if the environment is equivalent to `Other`, i.e 133 /// the two environments: 134 /// - have the same mappings from declarations to storage locations, 135 /// - have the same mappings from expressions to storage locations, 136 /// - have the same or equivalent (according to `Model`) values assigned to 137 /// the same storage locations. 138 /// 139 /// Requirements: 140 /// 141 /// `Other` and `this` must use the same `DataflowAnalysisContext`. 142 bool equivalentTo(const Environment &Other, 143 Environment::ValueModel &Model) const; 144 145 /// Joins the environment with `Other` by taking the intersection of storage 146 /// locations and values that are stored in them. Distinct values that are 147 /// assigned to the same storage locations in the environment and `Other` are 148 /// merged using `Model`. 149 /// 150 /// Requirements: 151 /// 152 /// `Other` and `this` must use the same `DataflowAnalysisContext`. 153 LatticeJoinEffect join(const Environment &Other, 154 Environment::ValueModel &Model); 155 156 // FIXME: Rename `createOrGetStorageLocation` to `getOrCreateStorageLocation`, 157 // `getStableStorageLocation`, or something more appropriate. 158 159 /// Creates a storage location appropriate for `Type`. Does not assign a value 160 /// to the returned storage location in the environment. 161 /// 162 /// Requirements: 163 /// 164 /// `Type` must not be null. 165 StorageLocation &createStorageLocation(QualType Type); 166 167 /// Creates a storage location for `D`. Does not assign the returned storage 168 /// location to `D` in the environment. Does not assign a value to the 169 /// returned storage location in the environment. 170 StorageLocation &createStorageLocation(const VarDecl &D); 171 172 /// Creates a storage location for `E`. Does not assign the returned storage 173 /// location to `E` in the environment. Does not assign a value to the 174 /// returned storage location in the environment. 175 StorageLocation &createStorageLocation(const Expr &E); 176 177 /// Assigns `Loc` as the storage location of `D` in the environment. 178 /// 179 /// Requirements: 180 /// 181 /// `D` must not be assigned a storage location in the environment. 182 void setStorageLocation(const ValueDecl &D, StorageLocation &Loc); 183 184 /// Returns the storage location assigned to `D` in the environment, applying 185 /// the `SP` policy for skipping past indirections, or null if `D` isn't 186 /// assigned a storage location in the environment. 187 StorageLocation *getStorageLocation(const ValueDecl &D, SkipPast SP) const; 188 189 /// Assigns `Loc` as the storage location of `E` in the environment. 190 /// 191 /// Requirements: 192 /// 193 /// `E` must not be assigned a storage location in the environment. 194 void setStorageLocation(const Expr &E, StorageLocation &Loc); 195 196 /// Returns the storage location assigned to `E` in the environment, applying 197 /// the `SP` policy for skipping past indirections, or null if `E` isn't 198 /// assigned a storage location in the environment. 199 StorageLocation *getStorageLocation(const Expr &E, SkipPast SP) const; 200 201 /// Returns the storage location assigned to the `this` pointee in the 202 /// environment or null if the `this` pointee has no assigned storage location 203 /// in the environment. 204 StorageLocation *getThisPointeeStorageLocation() const; 205 206 /// Returns a pointer value that represents a null pointer. Calls with 207 /// `PointeeType` that are canonically equivalent will return the same result. 208 PointerValue &getOrCreateNullPointerValue(QualType PointeeType); 209 210 /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise 211 /// return null. If `Type` is a pointer or reference type, creates all the 212 /// necessary storage locations and values for indirections until it finds a 213 /// non-pointer/non-reference type. 214 /// 215 /// Requirements: 216 /// 217 /// `Type` must not be null. 218 Value *createValue(QualType Type); 219 220 /// Assigns `Val` as the value of `Loc` in the environment. 221 void setValue(const StorageLocation &Loc, Value &Val); 222 223 /// Returns the value assigned to `Loc` in the environment or null if `Loc` 224 /// isn't assigned a value in the environment. 225 Value *getValue(const StorageLocation &Loc) const; 226 227 /// Equivalent to `getValue(getStorageLocation(D, SP), SkipPast::None)` if `D` 228 /// is assigned a storage location in the environment, otherwise returns null. 229 Value *getValue(const ValueDecl &D, SkipPast SP) const; 230 231 /// Equivalent to `getValue(getStorageLocation(E, SP), SkipPast::None)` if `E` 232 /// is assigned a storage location in the environment, otherwise returns null. 233 Value *getValue(const Expr &E, SkipPast SP) const; 234 235 /// Transfers ownership of `Loc` to the analysis context and returns a 236 /// reference to it. 237 /// 238 /// Requirements: 239 /// 240 /// `Loc` must not be null. 241 template <typename T> 242 typename std::enable_if<std::is_base_of<StorageLocation, T>::value, T &>::type 243 takeOwnership(std::unique_ptr<T> Loc) { 244 return DACtx->takeOwnership(std::move(Loc)); 245 } 246 247 /// Transfers ownership of `Val` to the analysis context and returns a 248 /// reference to it. 249 /// 250 /// Requirements: 251 /// 252 /// `Val` must not be null. 253 template <typename T> 254 typename std::enable_if<std::is_base_of<Value, T>::value, T &>::type 255 takeOwnership(std::unique_ptr<T> Val) { 256 return DACtx->takeOwnership(std::move(Val)); 257 } 258 259 /// Returns a symbolic boolean value that models a boolean literal equal to 260 /// `Value` 261 AtomicBoolValue &getBoolLiteralValue(bool Value) const { 262 return DACtx->getBoolLiteralValue(Value); 263 } 264 265 /// Returns an atomic boolean value. 266 BoolValue &makeAtomicBoolValue() const { 267 return DACtx->createAtomicBoolValue(); 268 } 269 270 /// Returns a boolean value that represents the conjunction of `LHS` and 271 /// `RHS`. Subsequent calls with the same arguments, regardless of their 272 /// order, will return the same result. If the given boolean values represent 273 /// the same value, the result will be the value itself. 274 BoolValue &makeAnd(BoolValue &LHS, BoolValue &RHS) const { 275 return DACtx->getOrCreateConjunction(LHS, RHS); 276 } 277 278 /// Returns a boolean value that represents the disjunction of `LHS` and 279 /// `RHS`. Subsequent calls with the same arguments, regardless of their 280 /// order, will return the same result. If the given boolean values represent 281 /// the same value, the result will be the value itself. 282 BoolValue &makeOr(BoolValue &LHS, BoolValue &RHS) const { 283 return DACtx->getOrCreateDisjunction(LHS, RHS); 284 } 285 286 /// Returns a boolean value that represents the negation of `Val`. Subsequent 287 /// calls with the same argument will return the same result. 288 BoolValue &makeNot(BoolValue &Val) const { 289 return DACtx->getOrCreateNegation(Val); 290 } 291 292 /// Returns a boolean value represents `LHS` => `RHS`. Subsequent calls with 293 /// the same arguments, will return the same result. If the given boolean 294 /// values represent the same value, the result will be a value that 295 /// represents the true boolean literal. 296 BoolValue &makeImplication(BoolValue &LHS, BoolValue &RHS) const { 297 return DACtx->getOrCreateImplication(LHS, RHS); 298 } 299 300 /// Returns a boolean value represents `LHS` <=> `RHS`. Subsequent calls with 301 /// the same arguments, regardless of their order, will return the same 302 /// result. If the given boolean values represent the same value, the result 303 /// will be a value that represents the true boolean literal. 304 BoolValue &makeIff(BoolValue &LHS, BoolValue &RHS) const { 305 return DACtx->getOrCreateIff(LHS, RHS); 306 } 307 308 /// Returns the token that identifies the flow condition of the environment. 309 AtomicBoolValue &getFlowConditionToken() const { return *FlowConditionToken; } 310 311 /// Builds and returns the logical formula defining the flow condition 312 /// identified by `Token`. If a value in the formula is present as a key in 313 /// `Substitutions`, it will be substituted with the value it maps to. 314 BoolValue &buildAndSubstituteFlowCondition( 315 AtomicBoolValue &Token, 316 llvm::DenseMap<AtomicBoolValue *, BoolValue *> Substitutions) { 317 return DACtx->buildAndSubstituteFlowCondition(Token, 318 std::move(Substitutions)); 319 } 320 321 /// Adds `Val` to the set of clauses that constitute the flow condition. 322 void addToFlowCondition(BoolValue &Val); 323 324 /// Returns true if and only if the clauses that constitute the flow condition 325 /// imply that `Val` is true. 326 bool flowConditionImplies(BoolValue &Val) const; 327 328 private: 329 /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise 330 /// return null. 331 /// 332 /// Recursively initializes storage locations and values until it sees a 333 /// self-referential pointer or reference type. `Visited` is used to track 334 /// which types appeared in the reference/pointer chain in order to avoid 335 /// creating a cyclic dependency with self-referential pointers/references. 336 /// 337 /// Requirements: 338 /// 339 /// `Type` must not be null. 340 Value *createValueUnlessSelfReferential(QualType Type, 341 llvm::DenseSet<QualType> &Visited, 342 int Depth, int &CreatedValuesCount); 343 344 StorageLocation &skip(StorageLocation &Loc, SkipPast SP) const; 345 const StorageLocation &skip(const StorageLocation &Loc, SkipPast SP) const; 346 347 // `DACtx` is not null and not owned by this object. 348 DataflowAnalysisContext *DACtx; 349 350 // Maps from program declarations and statements to storage locations that are 351 // assigned to them. Unlike the maps in `DataflowAnalysisContext`, these 352 // include only storage locations that are in scope for a particular basic 353 // block. 354 llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc; 355 llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc; 356 357 llvm::DenseMap<const StorageLocation *, Value *> LocToVal; 358 359 // Maps locations of struct members to symbolic values of the structs that own 360 // them and the decls of the struct members. 361 llvm::DenseMap<const StorageLocation *, 362 std::pair<StructValue *, const ValueDecl *>> 363 MemberLocToStruct; 364 365 AtomicBoolValue *FlowConditionToken; 366 }; 367 368 } // namespace dataflow 369 } // namespace clang 370 371 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H 372