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/ControlFlowContext.h" 23 #include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h" 24 #include "clang/Analysis/FlowSensitive/DataflowLattice.h" 25 #include "clang/Analysis/FlowSensitive/Formula.h" 26 #include "clang/Analysis/FlowSensitive/Logger.h" 27 #include "clang/Analysis/FlowSensitive/StorageLocation.h" 28 #include "clang/Analysis/FlowSensitive/Value.h" 29 #include "llvm/ADT/DenseMap.h" 30 #include "llvm/ADT/DenseSet.h" 31 #include "llvm/ADT/MapVector.h" 32 #include "llvm/Support/Compiler.h" 33 #include "llvm/Support/ErrorHandling.h" 34 #include <memory> 35 #include <type_traits> 36 #include <utility> 37 38 namespace clang { 39 namespace dataflow { 40 41 /// Indicates the result of a tentative comparison. 42 enum class ComparisonResult { 43 Same, 44 Different, 45 Unknown, 46 }; 47 48 /// Holds the state of the program (store and heap) at a given program point. 49 /// 50 /// WARNING: Symbolic values that are created by the environment for static 51 /// local and global variables are not currently invalidated on function calls. 52 /// This is unsound and should be taken into account when designing dataflow 53 /// analyses. 54 class Environment { 55 public: 56 /// Supplements `Environment` with non-standard comparison and join 57 /// operations. 58 class ValueModel { 59 public: 60 virtual ~ValueModel() = default; 61 62 /// Returns: 63 /// `Same`: `Val1` is equivalent to `Val2`, according to the model. 64 /// `Different`: `Val1` is distinct from `Val2`, according to the model. 65 /// `Unknown`: The model can't determine a relationship between `Val1` and 66 /// `Val2`. 67 /// 68 /// Requirements: 69 /// 70 /// `Val1` and `Val2` must be distinct. 71 /// 72 /// `Val1` and `Val2` must model values of type `Type`. 73 /// 74 /// `Val1` and `Val2` must be assigned to the same storage location in 75 /// `Env1` and `Env2` respectively. 76 virtual ComparisonResult compare(QualType Type, const Value &Val1, 77 const Environment &Env1, const Value &Val2, 78 const Environment &Env2) { 79 // FIXME: Consider adding QualType to RecordValue and removing the Type 80 // argument here. 81 return ComparisonResult::Unknown; 82 } 83 84 /// Modifies `MergedVal` to approximate both `Val1` and `Val2`. This could 85 /// be a strict lattice join or a more general widening operation. 86 /// 87 /// If this function returns true, `MergedVal` will be assigned to a storage 88 /// location of type `Type` in `MergedEnv`. 89 /// 90 /// `Env1` and `Env2` can be used to query child values and path condition 91 /// implications of `Val1` and `Val2` respectively. 92 /// 93 /// Requirements: 94 /// 95 /// `Val1` and `Val2` must be distinct. 96 /// 97 /// `Val1`, `Val2`, and `MergedVal` must model values of type `Type`. 98 /// 99 /// `Val1` and `Val2` must be assigned to the same storage location in 100 /// `Env1` and `Env2` respectively. 101 virtual bool merge(QualType Type, const Value &Val1, 102 const Environment &Env1, const Value &Val2, 103 const Environment &Env2, Value &MergedVal, 104 Environment &MergedEnv) { 105 return true; 106 } 107 108 /// This function may widen the current value -- replace it with an 109 /// approximation that can reach a fixed point more quickly than iterated 110 /// application of the transfer function alone. The previous value is 111 /// provided to inform the choice of widened value. The function must also 112 /// serve as a comparison operation, by indicating whether the widened value 113 /// is equivalent to the previous value. 114 /// 115 /// Returns either: 116 /// 117 /// `nullptr`, if this value is not of interest to the model, or 118 /// 119 /// `&Prev`, if the widened value is equivalent to `Prev`, or 120 /// 121 /// A non-null value that approximates `Current`. `Prev` is available to 122 /// inform the chosen approximation. 123 /// 124 /// `PrevEnv` and `CurrentEnv` can be used to query child values and path 125 /// condition implications of `Prev` and `Current`, respectively. 126 /// 127 /// Requirements: 128 /// 129 /// `Prev` and `Current` must model values of type `Type`. 130 /// 131 /// `Prev` and `Current` must be assigned to the same storage location in 132 /// `PrevEnv` and `CurrentEnv`, respectively. 133 virtual Value *widen(QualType Type, Value &Prev, const Environment &PrevEnv, 134 Value &Current, Environment &CurrentEnv) { 135 // The default implementation reduces to just comparison, since comparison 136 // is required by the API, even if no widening is performed. 137 switch (compare(Type, Prev, PrevEnv, Current, CurrentEnv)) { 138 case ComparisonResult::Same: 139 return &Prev; 140 case ComparisonResult::Different: 141 return &Current; 142 case ComparisonResult::Unknown: 143 return nullptr; 144 } 145 llvm_unreachable("all cases in switch covered"); 146 } 147 }; 148 149 /// Creates an environment that uses `DACtx` to store objects that encompass 150 /// the state of a program. 151 explicit Environment(DataflowAnalysisContext &DACtx); 152 153 // Copy-constructor is private, Environments should not be copied. See fork(). 154 Environment &operator=(const Environment &Other) = delete; 155 156 Environment(Environment &&Other) = default; 157 Environment &operator=(Environment &&Other) = default; 158 159 /// Creates an environment that uses `DACtx` to store objects that encompass 160 /// the state of a program. 161 /// 162 /// If `DeclCtx` is a function, initializes the environment with symbolic 163 /// representations of the function parameters. 164 /// 165 /// If `DeclCtx` is a non-static member function, initializes the environment 166 /// with a symbolic representation of the `this` pointee. 167 Environment(DataflowAnalysisContext &DACtx, const DeclContext &DeclCtx); 168 169 /// Assigns storage locations and values to all parameters, captures, global 170 /// variables, fields and functions referenced in the function currently being 171 /// analyzed. 172 /// 173 /// Requirements: 174 /// 175 /// The function must have a body. 176 void initialize(); 177 178 /// Returns a new environment that is a copy of this one. 179 /// 180 /// The state of the program is initially the same, but can be mutated without 181 /// affecting the original. 182 /// 183 /// However the original should not be further mutated, as this may interfere 184 /// with the fork. (In practice, values are stored independently, but the 185 /// forked flow condition references the original). 186 Environment fork() const; 187 188 /// Creates and returns an environment to use for an inline analysis of the 189 /// callee. Uses the storage location from each argument in the `Call` as the 190 /// storage location for the corresponding parameter in the callee. 191 /// 192 /// Requirements: 193 /// 194 /// The callee of `Call` must be a `FunctionDecl`. 195 /// 196 /// The body of the callee must not reference globals. 197 /// 198 /// The arguments of `Call` must map 1:1 to the callee's parameters. 199 Environment pushCall(const CallExpr *Call) const; 200 Environment pushCall(const CXXConstructExpr *Call) const; 201 202 /// Moves gathered information back into `this` from a `CalleeEnv` created via 203 /// `pushCall`. 204 void popCall(const CallExpr *Call, const Environment &CalleeEnv); 205 void popCall(const CXXConstructExpr *Call, const Environment &CalleeEnv); 206 207 /// Returns true if and only if the environment is equivalent to `Other`, i.e 208 /// the two environments: 209 /// - have the same mappings from declarations to storage locations, 210 /// - have the same mappings from expressions to storage locations, 211 /// - have the same or equivalent (according to `Model`) values assigned to 212 /// the same storage locations. 213 /// 214 /// Requirements: 215 /// 216 /// `Other` and `this` must use the same `DataflowAnalysisContext`. 217 bool equivalentTo(const Environment &Other, 218 Environment::ValueModel &Model) const; 219 220 /// Joins two environments by taking the intersection of storage locations and 221 /// values that are stored in them. Distinct values that are assigned to the 222 /// same storage locations in `EnvA` and `EnvB` are merged using `Model`. 223 /// 224 /// Requirements: 225 /// 226 /// `EnvA` and `EnvB` must use the same `DataflowAnalysisContext`. 227 static Environment join(const Environment &EnvA, const Environment &EnvB, 228 Environment::ValueModel &Model); 229 230 /// Widens the environment point-wise, using `PrevEnv` as needed to inform the 231 /// approximation. 232 /// 233 /// Requirements: 234 /// 235 /// `PrevEnv` must be the immediate previous version of the environment. 236 /// `PrevEnv` and `this` must use the same `DataflowAnalysisContext`. 237 LatticeJoinEffect widen(const Environment &PrevEnv, 238 Environment::ValueModel &Model); 239 240 // FIXME: Rename `createOrGetStorageLocation` to `getOrCreateStorageLocation`, 241 // `getStableStorageLocation`, or something more appropriate. 242 243 /// Creates a storage location appropriate for `Type`. Does not assign a value 244 /// to the returned storage location in the environment. 245 /// 246 /// Requirements: 247 /// 248 /// `Type` must not be null. 249 StorageLocation &createStorageLocation(QualType Type); 250 251 /// Creates a storage location for `D`. Does not assign the returned storage 252 /// location to `D` in the environment. Does not assign a value to the 253 /// returned storage location in the environment. 254 StorageLocation &createStorageLocation(const ValueDecl &D); 255 256 /// Creates a storage location for `E`. Does not assign the returned storage 257 /// location to `E` in the environment. Does not assign a value to the 258 /// returned storage location in the environment. 259 StorageLocation &createStorageLocation(const Expr &E); 260 261 /// Assigns `Loc` as the storage location of `D` in the environment. 262 /// 263 /// Requirements: 264 /// 265 /// `D` must not already have a storage location in the environment. 266 void setStorageLocation(const ValueDecl &D, StorageLocation &Loc); 267 268 /// Returns the storage location assigned to `D` in the environment, or null 269 /// if `D` isn't assigned a storage location in the environment. 270 StorageLocation *getStorageLocation(const ValueDecl &D) const; 271 272 /// Removes the location assigned to `D` in the environment (if any). 273 void removeDecl(const ValueDecl &D); 274 275 /// Assigns `Loc` as the storage location of the glvalue `E` in the 276 /// environment. 277 /// 278 /// Requirements: 279 /// 280 /// `E` must not be assigned a storage location in the environment. 281 /// `E` must be a glvalue or a `BuiltinType::BuiltinFn` 282 void setStorageLocation(const Expr &E, StorageLocation &Loc); 283 284 /// Returns the storage location assigned to the glvalue `E` in the 285 /// environment, or null if `E` isn't assigned a storage location in the 286 /// environment. 287 /// 288 /// Requirements: 289 /// `E` must be a glvalue or a `BuiltinType::BuiltinFn` 290 StorageLocation *getStorageLocation(const Expr &E) const; 291 292 /// Returns the storage location assigned to the `this` pointee in the 293 /// environment or null if the `this` pointee has no assigned storage location 294 /// in the environment. 295 RecordStorageLocation *getThisPointeeStorageLocation() const { 296 return ThisPointeeLoc; 297 } 298 299 /// Sets the storage location assigned to the `this` pointee in the 300 /// environment. 301 void setThisPointeeStorageLocation(RecordStorageLocation &Loc) { 302 ThisPointeeLoc = &Loc; 303 } 304 305 /// Returns the location of the result object for a record-type prvalue. 306 /// 307 /// In C++, prvalues of record type serve only a limited purpose: They can 308 /// only be used to initialize a result object (e.g. a variable or a 309 /// temporary). This function returns the location of that result object. 310 /// 311 /// When creating a prvalue of record type, we already need the storage 312 /// location of the result object to pass in `this`, even though prvalues are 313 /// otherwise not associated with storage locations. 314 /// 315 /// FIXME: Currently, this simply returns a stable storage location for `E`, 316 /// but this doesn't do the right thing in scenarios like the following: 317 /// ``` 318 /// MyClass c = some_condition()? MyClass(foo) : MyClass(bar); 319 /// ``` 320 /// Here, `MyClass(foo)` and `MyClass(bar)` will have two different storage 321 /// locations, when in fact their storage locations should be the same. 322 /// Eventually, we want to propagate storage locations from result objects 323 /// down to the prvalues that initialize them, similar to the way that this is 324 /// done in Clang's CodeGen. 325 /// 326 /// Requirements: 327 /// `E` must be a prvalue of record type. 328 RecordStorageLocation &getResultObjectLocation(const Expr &RecordPRValue); 329 330 /// Returns the return value of the current function. This can be null if: 331 /// - The function has a void return type 332 /// - No return value could be determined for the function, for example 333 /// because it calls a function without a body. 334 /// 335 /// Requirements: 336 /// The current function must have a non-reference return type. 337 Value *getReturnValue() const { 338 assert(getCurrentFunc() != nullptr && 339 !getCurrentFunc()->getReturnType()->isReferenceType()); 340 return ReturnVal; 341 } 342 343 /// Returns the storage location for the reference returned by the current 344 /// function. This can be null if function doesn't return a single consistent 345 /// reference. 346 /// 347 /// Requirements: 348 /// The current function must have a reference return type. 349 StorageLocation *getReturnStorageLocation() const { 350 assert(getCurrentFunc() != nullptr && 351 getCurrentFunc()->getReturnType()->isReferenceType()); 352 return ReturnLoc; 353 } 354 355 /// Sets the return value of the current function. 356 /// 357 /// Requirements: 358 /// The current function must have a non-reference return type. 359 void setReturnValue(Value *Val) { 360 assert(getCurrentFunc() != nullptr && 361 !getCurrentFunc()->getReturnType()->isReferenceType()); 362 ReturnVal = Val; 363 } 364 365 /// Sets the storage location for the reference returned by the current 366 /// function. 367 /// 368 /// Requirements: 369 /// The current function must have a reference return type. 370 void setReturnStorageLocation(StorageLocation *Loc) { 371 assert(getCurrentFunc() != nullptr && 372 getCurrentFunc()->getReturnType()->isReferenceType()); 373 ReturnLoc = Loc; 374 } 375 376 /// Returns a pointer value that represents a null pointer. Calls with 377 /// `PointeeType` that are canonically equivalent will return the same result. 378 PointerValue &getOrCreateNullPointerValue(QualType PointeeType); 379 380 /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise 381 /// returns null. 382 /// 383 /// If `Type` is a pointer or reference type, creates all the necessary 384 /// storage locations and values for indirections until it finds a 385 /// non-pointer/non-reference type. 386 /// 387 /// If `Type` is a class, struct, or union type, creates values for all 388 /// modeled fields (including synthetic fields) and calls `setValue()` to 389 /// associate the `RecordValue` with its storage location 390 /// (`RecordValue::getLoc()`). 391 /// 392 /// If `Type` is one of the following types, this function will always return 393 /// a non-null pointer: 394 /// - `bool` 395 /// - Any integer type 396 /// - Any class, struct, or union type 397 /// 398 /// Requirements: 399 /// 400 /// `Type` must not be null. 401 Value *createValue(QualType Type); 402 403 /// Creates an object (i.e. a storage location with an associated value) of 404 /// type `Ty`. If `InitExpr` is non-null and has a value associated with it, 405 /// initializes the object with this value. Otherwise, initializes the object 406 /// with a value created using `createValue()`. 407 StorageLocation &createObject(QualType Ty, const Expr *InitExpr = nullptr) { 408 return createObjectInternal(nullptr, Ty, InitExpr); 409 } 410 411 /// Creates an object for the variable declaration `D`. If `D` has an 412 /// initializer and this initializer is associated with a value, initializes 413 /// the object with this value. Otherwise, initializes the object with a 414 /// value created using `createValue()`. Uses the storage location returned by 415 /// `DataflowAnalysisContext::getStableStorageLocation(D)`. 416 StorageLocation &createObject(const VarDecl &D) { 417 return createObjectInternal(&D, D.getType(), D.getInit()); 418 } 419 420 /// Creates an object for the variable declaration `D`. If `InitExpr` is 421 /// non-null and has a value associated with it, initializes the object with 422 /// this value. Otherwise, initializes the object with a value created using 423 /// `createValue()`. Uses the storage location returned by 424 /// `DataflowAnalysisContext::getStableStorageLocation(D)`. 425 StorageLocation &createObject(const ValueDecl &D, const Expr *InitExpr) { 426 return createObjectInternal(&D, D.getType(), InitExpr); 427 } 428 429 /// Assigns `Val` as the value of `Loc` in the environment. 430 void setValue(const StorageLocation &Loc, Value &Val); 431 432 /// Clears any association between `Loc` and a value in the environment. 433 void clearValue(const StorageLocation &Loc) { LocToVal.erase(&Loc); } 434 435 /// Assigns `Val` as the value of the prvalue `E` in the environment. 436 /// 437 /// If `E` is not yet associated with a storage location, associates it with 438 /// a newly created storage location. In any case, associates the storage 439 /// location of `E` with `Val`. 440 /// 441 /// Once the migration to strict handling of value categories is complete 442 /// (see https://discourse.llvm.org/t/70086), this function will be renamed to 443 /// `setValue()`. At this point, prvalue expressions will be associated 444 /// directly with `Value`s, and the legacy behavior of associating prvalue 445 /// expressions with storage locations (as described above) will be 446 /// eliminated. 447 /// 448 /// Requirements: 449 /// 450 /// `E` must be a prvalue 451 /// If `Val` is a `RecordValue`, its `RecordStorageLocation` must be the 452 /// same as that of any `RecordValue` that has already been associated with 453 /// `E`. This is to guarantee that the result object initialized by a prvalue 454 /// `RecordValue` has a durable storage location. 455 void setValue(const Expr &E, Value &Val); 456 457 /// Returns the value assigned to `Loc` in the environment or null if `Loc` 458 /// isn't assigned a value in the environment. 459 Value *getValue(const StorageLocation &Loc) const; 460 461 /// Equivalent to `getValue(getStorageLocation(D))` if `D` is assigned a 462 /// storage location in the environment, otherwise returns null. 463 Value *getValue(const ValueDecl &D) const; 464 465 /// Equivalent to `getValue(getStorageLocation(E, SP))` if `E` is assigned a 466 /// storage location in the environment, otherwise returns null. 467 Value *getValue(const Expr &E) const; 468 469 // FIXME: should we deprecate the following & call arena().create() directly? 470 471 /// Creates a `T` (some subclass of `Value`), forwarding `args` to the 472 /// constructor, and returns a reference to it. 473 /// 474 /// The analysis context takes ownership of the created object. The object 475 /// will be destroyed when the analysis context is destroyed. 476 template <typename T, typename... Args> 477 std::enable_if_t<std::is_base_of<Value, T>::value, T &> 478 create(Args &&...args) { 479 return arena().create<T>(std::forward<Args>(args)...); 480 } 481 482 /// Returns a symbolic integer value that models an integer literal equal to 483 /// `Value` 484 IntegerValue &getIntLiteralValue(llvm::APInt Value) const { 485 return arena().makeIntLiteral(Value); 486 } 487 488 /// Returns a symbolic boolean value that models a boolean literal equal to 489 /// `Value` 490 BoolValue &getBoolLiteralValue(bool Value) const { 491 return arena().makeBoolValue(arena().makeLiteral(Value)); 492 } 493 494 /// Returns an atomic boolean value. 495 BoolValue &makeAtomicBoolValue() const { 496 return arena().makeAtomValue(); 497 } 498 499 /// Returns a unique instance of boolean Top. 500 BoolValue &makeTopBoolValue() const { 501 return arena().makeTopValue(); 502 } 503 504 /// Returns a boolean value that represents the conjunction of `LHS` and 505 /// `RHS`. Subsequent calls with the same arguments, regardless of their 506 /// order, will return the same result. If the given boolean values represent 507 /// the same value, the result will be the value itself. 508 BoolValue &makeAnd(BoolValue &LHS, BoolValue &RHS) const { 509 return arena().makeBoolValue( 510 arena().makeAnd(LHS.formula(), RHS.formula())); 511 } 512 513 /// Returns a boolean value that represents the disjunction of `LHS` and 514 /// `RHS`. Subsequent calls with the same arguments, regardless of their 515 /// order, will return the same result. If the given boolean values represent 516 /// the same value, the result will be the value itself. 517 BoolValue &makeOr(BoolValue &LHS, BoolValue &RHS) const { 518 return arena().makeBoolValue( 519 arena().makeOr(LHS.formula(), RHS.formula())); 520 } 521 522 /// Returns a boolean value that represents the negation of `Val`. Subsequent 523 /// calls with the same argument will return the same result. 524 BoolValue &makeNot(BoolValue &Val) const { 525 return arena().makeBoolValue(arena().makeNot(Val.formula())); 526 } 527 528 /// Returns a boolean value represents `LHS` => `RHS`. Subsequent calls with 529 /// the same arguments, will return the same result. If the given boolean 530 /// values represent the same value, the result will be a value that 531 /// represents the true boolean literal. 532 BoolValue &makeImplication(BoolValue &LHS, BoolValue &RHS) const { 533 return arena().makeBoolValue( 534 arena().makeImplies(LHS.formula(), RHS.formula())); 535 } 536 537 /// Returns a boolean value represents `LHS` <=> `RHS`. Subsequent calls with 538 /// the same arguments, regardless of their order, will return the same 539 /// result. If the given boolean values represent the same value, the result 540 /// will be a value that represents the true boolean literal. 541 BoolValue &makeIff(BoolValue &LHS, BoolValue &RHS) const { 542 return arena().makeBoolValue( 543 arena().makeEquals(LHS.formula(), RHS.formula())); 544 } 545 546 /// Returns a boolean variable that identifies the flow condition (FC). 547 /// 548 /// The flow condition is a set of facts that are necessarily true when the 549 /// program reaches the current point, expressed as boolean formulas. 550 /// The flow condition token is equivalent to the AND of these facts. 551 /// 552 /// These may e.g. constrain the value of certain variables. A pointer 553 /// variable may have a consistent modeled PointerValue throughout, but at a 554 /// given point the Environment may tell us that the value must be non-null. 555 /// 556 /// The FC is necessary but not sufficient for this point to be reachable. 557 /// In particular, where the FC token appears in flow conditions of successor 558 /// environments, it means "point X may have been reached", not 559 /// "point X was reached". 560 Atom getFlowConditionToken() const { return FlowConditionToken; } 561 562 /// Record a fact that must be true if this point in the program is reached. 563 void assume(const Formula &); 564 565 /// Returns true if the formula is always true when this point is reached. 566 /// Returns false if the formula may be false (or the flow condition isn't 567 /// sufficiently precise to prove that it is true) or if the solver times out. 568 /// 569 /// Note that there is an asymmetry between this function and `allows()` in 570 /// that they both return false if the solver times out. The assumption is 571 /// that if `proves()` or `allows()` returns true, this will result in a 572 /// diagnostic, and we want to bias towards false negatives in the case where 573 /// the solver times out. 574 bool proves(const Formula &) const; 575 576 /// Returns true if the formula may be true when this point is reached. 577 /// Returns false if the formula is always false when this point is reached 578 /// (or the flow condition is overly constraining) or if the solver times out. 579 bool allows(const Formula &) const; 580 581 /// Returns the `DeclContext` of the block being analysed, if any. Otherwise, 582 /// returns null. 583 const DeclContext *getDeclCtx() const { return CallStack.back(); } 584 585 /// Returns the function currently being analyzed, or null if the code being 586 /// analyzed isn't part of a function. 587 const FunctionDecl *getCurrentFunc() const { 588 return dyn_cast<FunctionDecl>(getDeclCtx()); 589 } 590 591 /// Returns the size of the call stack. 592 size_t callStackSize() const { return CallStack.size(); } 593 594 /// Returns whether this `Environment` can be extended to analyze the given 595 /// `Callee` (i.e. if `pushCall` can be used), with recursion disallowed and a 596 /// given `MaxDepth`. 597 bool canDescend(unsigned MaxDepth, const DeclContext *Callee) const; 598 599 /// Returns the `DataflowAnalysisContext` used by the environment. 600 DataflowAnalysisContext &getDataflowAnalysisContext() const { return *DACtx; } 601 602 Arena &arena() const { return DACtx->arena(); } 603 604 LLVM_DUMP_METHOD void dump() const; 605 LLVM_DUMP_METHOD void dump(raw_ostream &OS) const; 606 607 private: 608 // The copy-constructor is for use in fork() only. 609 Environment(const Environment &) = default; 610 611 /// Internal version of `setStorageLocation()` that doesn't check if the 612 /// expression is a prvalue. 613 void setStorageLocationInternal(const Expr &E, StorageLocation &Loc); 614 615 /// Internal version of `getStorageLocation()` that doesn't check if the 616 /// expression is a prvalue. 617 StorageLocation *getStorageLocationInternal(const Expr &E) const; 618 619 /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise 620 /// return null. 621 /// 622 /// Recursively initializes storage locations and values until it sees a 623 /// self-referential pointer or reference type. `Visited` is used to track 624 /// which types appeared in the reference/pointer chain in order to avoid 625 /// creating a cyclic dependency with self-referential pointers/references. 626 /// 627 /// Requirements: 628 /// 629 /// `Type` must not be null. 630 Value *createValueUnlessSelfReferential(QualType Type, 631 llvm::DenseSet<QualType> &Visited, 632 int Depth, int &CreatedValuesCount); 633 634 /// Creates a storage location for `Ty`. Also creates and associates a value 635 /// with the storage location, unless values of this type are not supported or 636 /// we hit one of the limits at which we stop producing values (controlled by 637 /// `Visited`, `Depth`, and `CreatedValuesCount`). 638 StorageLocation &createLocAndMaybeValue(QualType Ty, 639 llvm::DenseSet<QualType> &Visited, 640 int Depth, int &CreatedValuesCount); 641 642 /// Shared implementation of `createObject()` overloads. 643 /// `D` and `InitExpr` may be null. 644 StorageLocation &createObjectInternal(const ValueDecl *D, QualType Ty, 645 const Expr *InitExpr); 646 647 /// Shared implementation of `pushCall` overloads. Note that unlike 648 /// `pushCall`, this member is invoked on the environment of the callee, not 649 /// of the caller. 650 void pushCallInternal(const FunctionDecl *FuncDecl, 651 ArrayRef<const Expr *> Args); 652 653 /// Assigns storage locations and values to all global variables, fields 654 /// and functions referenced in `FuncDecl`. `FuncDecl` must have a body. 655 void initFieldsGlobalsAndFuncs(const FunctionDecl *FuncDecl); 656 657 // `DACtx` is not null and not owned by this object. 658 DataflowAnalysisContext *DACtx; 659 660 // FIXME: move the fields `CallStack`, `ReturnVal`, `ReturnLoc` and 661 // `ThisPointeeLoc` into a separate call-context object, shared between 662 // environments in the same call. 663 // https://github.com/llvm/llvm-project/issues/59005 664 665 // `DeclContext` of the block being analysed if provided. 666 std::vector<const DeclContext *> CallStack; 667 668 // Value returned by the function (if it has non-reference return type). 669 Value *ReturnVal = nullptr; 670 // Storage location of the reference returned by the function (if it has 671 // reference return type). 672 StorageLocation *ReturnLoc = nullptr; 673 // The storage location of the `this` pointee. Should only be null if the 674 // function being analyzed is only a function and not a method. 675 RecordStorageLocation *ThisPointeeLoc = nullptr; 676 677 // Maps from declarations and glvalue expression to storage locations that are 678 // assigned to them. Unlike the maps in `DataflowAnalysisContext`, these 679 // include only storage locations that are in scope for a particular basic 680 // block. 681 llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc; 682 llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc; 683 // Maps from prvalue expressions and storage locations to the values that 684 // are assigned to them. 685 // We preserve insertion order so that join/widen process values in 686 // deterministic sequence. This in turn produces deterministic SAT formulas. 687 llvm::MapVector<const Expr *, Value *> ExprToVal; 688 llvm::MapVector<const StorageLocation *, Value *> LocToVal; 689 690 Atom FlowConditionToken; 691 }; 692 693 /// Returns the storage location for the implicit object of a 694 /// `CXXMemberCallExpr`, or null if none is defined in the environment. 695 /// Dereferences the pointer if the member call expression was written using 696 /// `->`. 697 RecordStorageLocation *getImplicitObjectLocation(const CXXMemberCallExpr &MCE, 698 const Environment &Env); 699 700 /// Returns the storage location for the base object of a `MemberExpr`, or null 701 /// if none is defined in the environment. Dereferences the pointer if the 702 /// member expression was written using `->`. 703 RecordStorageLocation *getBaseObjectLocation(const MemberExpr &ME, 704 const Environment &Env); 705 706 /// Returns the fields of `RD` that are initialized by an `InitListExpr`, in the 707 /// order in which they appear in `InitListExpr::inits()`. 708 std::vector<FieldDecl *> getFieldsForInitListExpr(const RecordDecl *RD); 709 710 /// Associates a new `RecordValue` with `Loc` and returns the new value. 711 /// It is not defined whether the field values remain the same or not. 712 /// 713 /// This function is primarily intended for use by checks that set custom 714 /// properties on `RecordValue`s to model the state of these values. Such checks 715 /// should avoid modifying the properties of an existing `RecordValue` because 716 /// these changes would be visible to other `Environment`s that share the same 717 /// `RecordValue`. Instead, call `refreshRecordValue()`, then set the properties 718 /// on the new `RecordValue` that it returns. Typical usage: 719 /// 720 /// refreshRecordValue(Loc, Env).setProperty("my_prop", MyPropValue); 721 RecordValue &refreshRecordValue(RecordStorageLocation &Loc, Environment &Env); 722 723 /// Associates a new `RecordValue` with `Expr` and returns the new value. 724 /// See also documentation for the overload above. 725 RecordValue &refreshRecordValue(const Expr &Expr, Environment &Env); 726 727 } // namespace dataflow 728 } // namespace clang 729 730 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H 731