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