1 //== RegionStore.cpp - Field-sensitive store model --------------*- 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 a basic region store model. In this model, we do have field 10 // sensitivity. But we assume nothing about the heap shape. So recursive data 11 // structures are largely ignored. Basically we do 1-limiting analysis. 12 // Parameter pointers are assumed with no aliasing. Pointee objects of 13 // parameters are created lazily. 14 // 15 //===----------------------------------------------------------------------===// 16 17 #include "clang/AST/Attr.h" 18 #include "clang/AST/CharUnits.h" 19 #include "clang/ASTMatchers/ASTMatchFinder.h" 20 #include "clang/Analysis/Analyses/LiveVariables.h" 21 #include "clang/Analysis/AnalysisDeclContext.h" 22 #include "clang/Basic/JsonSupport.h" 23 #include "clang/Basic/TargetInfo.h" 24 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" 25 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 26 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 27 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 28 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 29 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 30 #include "llvm/ADT/ImmutableMap.h" 31 #include "llvm/ADT/Optional.h" 32 #include "llvm/Support/raw_ostream.h" 33 #include <utility> 34 35 using namespace clang; 36 using namespace ento; 37 38 //===----------------------------------------------------------------------===// 39 // Representation of binding keys. 40 //===----------------------------------------------------------------------===// 41 42 namespace { 43 class BindingKey { 44 public: 45 enum Kind { Default = 0x0, Direct = 0x1 }; 46 private: 47 enum { Symbolic = 0x2 }; 48 49 llvm::PointerIntPair<const MemRegion *, 2> P; 50 uint64_t Data; 51 52 /// Create a key for a binding to region \p r, which has a symbolic offset 53 /// from region \p Base. 54 explicit BindingKey(const SubRegion *r, const SubRegion *Base, Kind k) 55 : P(r, k | Symbolic), Data(reinterpret_cast<uintptr_t>(Base)) { 56 assert(r && Base && "Must have known regions."); 57 assert(getConcreteOffsetRegion() == Base && "Failed to store base region"); 58 } 59 60 /// Create a key for a binding at \p offset from base region \p r. 61 explicit BindingKey(const MemRegion *r, uint64_t offset, Kind k) 62 : P(r, k), Data(offset) { 63 assert(r && "Must have known regions."); 64 assert(getOffset() == offset && "Failed to store offset"); 65 assert((r == r->getBaseRegion() || 66 isa<ObjCIvarRegion, CXXDerivedObjectRegion>(r)) && 67 "Not a base"); 68 } 69 public: 70 71 bool isDirect() const { return P.getInt() & Direct; } 72 bool hasSymbolicOffset() const { return P.getInt() & Symbolic; } 73 74 const MemRegion *getRegion() const { return P.getPointer(); } 75 uint64_t getOffset() const { 76 assert(!hasSymbolicOffset()); 77 return Data; 78 } 79 80 const SubRegion *getConcreteOffsetRegion() const { 81 assert(hasSymbolicOffset()); 82 return reinterpret_cast<const SubRegion *>(static_cast<uintptr_t>(Data)); 83 } 84 85 const MemRegion *getBaseRegion() const { 86 if (hasSymbolicOffset()) 87 return getConcreteOffsetRegion()->getBaseRegion(); 88 return getRegion()->getBaseRegion(); 89 } 90 91 void Profile(llvm::FoldingSetNodeID& ID) const { 92 ID.AddPointer(P.getOpaqueValue()); 93 ID.AddInteger(Data); 94 } 95 96 static BindingKey Make(const MemRegion *R, Kind k); 97 98 bool operator<(const BindingKey &X) const { 99 if (P.getOpaqueValue() < X.P.getOpaqueValue()) 100 return true; 101 if (P.getOpaqueValue() > X.P.getOpaqueValue()) 102 return false; 103 return Data < X.Data; 104 } 105 106 bool operator==(const BindingKey &X) const { 107 return P.getOpaqueValue() == X.P.getOpaqueValue() && 108 Data == X.Data; 109 } 110 111 LLVM_DUMP_METHOD void dump() const; 112 }; 113 } // end anonymous namespace 114 115 BindingKey BindingKey::Make(const MemRegion *R, Kind k) { 116 const RegionOffset &RO = R->getAsOffset(); 117 if (RO.hasSymbolicOffset()) 118 return BindingKey(cast<SubRegion>(R), cast<SubRegion>(RO.getRegion()), k); 119 120 return BindingKey(RO.getRegion(), RO.getOffset(), k); 121 } 122 123 namespace llvm { 124 static inline raw_ostream &operator<<(raw_ostream &Out, BindingKey K) { 125 Out << "\"kind\": \"" << (K.isDirect() ? "Direct" : "Default") 126 << "\", \"offset\": "; 127 128 if (!K.hasSymbolicOffset()) 129 Out << K.getOffset(); 130 else 131 Out << "null"; 132 133 return Out; 134 } 135 136 } // namespace llvm 137 138 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 139 void BindingKey::dump() const { llvm::errs() << *this; } 140 #endif 141 142 //===----------------------------------------------------------------------===// 143 // Actual Store type. 144 //===----------------------------------------------------------------------===// 145 146 typedef llvm::ImmutableMap<BindingKey, SVal> ClusterBindings; 147 typedef llvm::ImmutableMapRef<BindingKey, SVal> ClusterBindingsRef; 148 typedef std::pair<BindingKey, SVal> BindingPair; 149 150 typedef llvm::ImmutableMap<const MemRegion *, ClusterBindings> 151 RegionBindings; 152 153 namespace { 154 class RegionBindingsRef : public llvm::ImmutableMapRef<const MemRegion *, 155 ClusterBindings> { 156 ClusterBindings::Factory *CBFactory; 157 158 // This flag indicates whether the current bindings are within the analysis 159 // that has started from main(). It affects how we perform loads from 160 // global variables that have initializers: if we have observed the 161 // program execution from the start and we know that these variables 162 // have not been overwritten yet, we can be sure that their initializers 163 // are still relevant. This flag never gets changed when the bindings are 164 // updated, so it could potentially be moved into RegionStoreManager 165 // (as if it's the same bindings but a different loading procedure) 166 // however that would have made the manager needlessly stateful. 167 bool IsMainAnalysis; 168 169 public: 170 typedef llvm::ImmutableMapRef<const MemRegion *, ClusterBindings> 171 ParentTy; 172 173 RegionBindingsRef(ClusterBindings::Factory &CBFactory, 174 const RegionBindings::TreeTy *T, 175 RegionBindings::TreeTy::Factory *F, 176 bool IsMainAnalysis) 177 : llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>(T, F), 178 CBFactory(&CBFactory), IsMainAnalysis(IsMainAnalysis) {} 179 180 RegionBindingsRef(const ParentTy &P, 181 ClusterBindings::Factory &CBFactory, 182 bool IsMainAnalysis) 183 : llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>(P), 184 CBFactory(&CBFactory), IsMainAnalysis(IsMainAnalysis) {} 185 186 RegionBindingsRef add(key_type_ref K, data_type_ref D) const { 187 return RegionBindingsRef(static_cast<const ParentTy *>(this)->add(K, D), 188 *CBFactory, IsMainAnalysis); 189 } 190 191 RegionBindingsRef remove(key_type_ref K) const { 192 return RegionBindingsRef(static_cast<const ParentTy *>(this)->remove(K), 193 *CBFactory, IsMainAnalysis); 194 } 195 196 RegionBindingsRef addBinding(BindingKey K, SVal V) const; 197 198 RegionBindingsRef addBinding(const MemRegion *R, 199 BindingKey::Kind k, SVal V) const; 200 201 const SVal *lookup(BindingKey K) const; 202 const SVal *lookup(const MemRegion *R, BindingKey::Kind k) const; 203 using llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>::lookup; 204 205 RegionBindingsRef removeBinding(BindingKey K); 206 207 RegionBindingsRef removeBinding(const MemRegion *R, 208 BindingKey::Kind k); 209 210 RegionBindingsRef removeBinding(const MemRegion *R) { 211 return removeBinding(R, BindingKey::Direct). 212 removeBinding(R, BindingKey::Default); 213 } 214 215 Optional<SVal> getDirectBinding(const MemRegion *R) const; 216 217 /// getDefaultBinding - Returns an SVal* representing an optional default 218 /// binding associated with a region and its subregions. 219 Optional<SVal> getDefaultBinding(const MemRegion *R) const; 220 221 /// Return the internal tree as a Store. 222 Store asStore() const { 223 llvm::PointerIntPair<Store, 1, bool> Ptr = { 224 asImmutableMap().getRootWithoutRetain(), IsMainAnalysis}; 225 return reinterpret_cast<Store>(Ptr.getOpaqueValue()); 226 } 227 228 bool isMainAnalysis() const { 229 return IsMainAnalysis; 230 } 231 232 void printJson(raw_ostream &Out, const char *NL = "\n", 233 unsigned int Space = 0, bool IsDot = false) const { 234 for (iterator I = begin(); I != end(); ++I) { 235 // TODO: We might need a .printJson for I.getKey() as well. 236 Indent(Out, Space, IsDot) 237 << "{ \"cluster\": \"" << I.getKey() << "\", \"pointer\": \"" 238 << (const void *)I.getKey() << "\", \"items\": [" << NL; 239 240 ++Space; 241 const ClusterBindings &CB = I.getData(); 242 for (ClusterBindings::iterator CI = CB.begin(); CI != CB.end(); ++CI) { 243 Indent(Out, Space, IsDot) << "{ " << CI.getKey() << ", \"value\": "; 244 CI.getData().printJson(Out, /*AddQuotes=*/true); 245 Out << " }"; 246 if (std::next(CI) != CB.end()) 247 Out << ','; 248 Out << NL; 249 } 250 251 --Space; 252 Indent(Out, Space, IsDot) << "]}"; 253 if (std::next(I) != end()) 254 Out << ','; 255 Out << NL; 256 } 257 } 258 259 LLVM_DUMP_METHOD void dump() const { printJson(llvm::errs()); } 260 }; 261 } // end anonymous namespace 262 263 typedef const RegionBindingsRef& RegionBindingsConstRef; 264 265 Optional<SVal> RegionBindingsRef::getDirectBinding(const MemRegion *R) const { 266 return Optional<SVal>::create(lookup(R, BindingKey::Direct)); 267 } 268 269 Optional<SVal> RegionBindingsRef::getDefaultBinding(const MemRegion *R) const { 270 return Optional<SVal>::create(lookup(R, BindingKey::Default)); 271 } 272 273 RegionBindingsRef RegionBindingsRef::addBinding(BindingKey K, SVal V) const { 274 const MemRegion *Base = K.getBaseRegion(); 275 276 const ClusterBindings *ExistingCluster = lookup(Base); 277 ClusterBindings Cluster = 278 (ExistingCluster ? *ExistingCluster : CBFactory->getEmptyMap()); 279 280 ClusterBindings NewCluster = CBFactory->add(Cluster, K, V); 281 return add(Base, NewCluster); 282 } 283 284 285 RegionBindingsRef RegionBindingsRef::addBinding(const MemRegion *R, 286 BindingKey::Kind k, 287 SVal V) const { 288 return addBinding(BindingKey::Make(R, k), V); 289 } 290 291 const SVal *RegionBindingsRef::lookup(BindingKey K) const { 292 const ClusterBindings *Cluster = lookup(K.getBaseRegion()); 293 if (!Cluster) 294 return nullptr; 295 return Cluster->lookup(K); 296 } 297 298 const SVal *RegionBindingsRef::lookup(const MemRegion *R, 299 BindingKey::Kind k) const { 300 return lookup(BindingKey::Make(R, k)); 301 } 302 303 RegionBindingsRef RegionBindingsRef::removeBinding(BindingKey K) { 304 const MemRegion *Base = K.getBaseRegion(); 305 const ClusterBindings *Cluster = lookup(Base); 306 if (!Cluster) 307 return *this; 308 309 ClusterBindings NewCluster = CBFactory->remove(*Cluster, K); 310 if (NewCluster.isEmpty()) 311 return remove(Base); 312 return add(Base, NewCluster); 313 } 314 315 RegionBindingsRef RegionBindingsRef::removeBinding(const MemRegion *R, 316 BindingKey::Kind k){ 317 return removeBinding(BindingKey::Make(R, k)); 318 } 319 320 //===----------------------------------------------------------------------===// 321 // Main RegionStore logic. 322 //===----------------------------------------------------------------------===// 323 324 namespace { 325 class InvalidateRegionsWorker; 326 327 class RegionStoreManager : public StoreManager { 328 public: 329 RegionBindings::Factory RBFactory; 330 mutable ClusterBindings::Factory CBFactory; 331 332 typedef std::vector<SVal> SValListTy; 333 private: 334 typedef llvm::DenseMap<const LazyCompoundValData *, 335 SValListTy> LazyBindingsMapTy; 336 LazyBindingsMapTy LazyBindingsMap; 337 338 /// The largest number of fields a struct can have and still be 339 /// considered "small". 340 /// 341 /// This is currently used to decide whether or not it is worth "forcing" a 342 /// LazyCompoundVal on bind. 343 /// 344 /// This is controlled by 'region-store-small-struct-limit' option. 345 /// To disable all small-struct-dependent behavior, set the option to "0". 346 unsigned SmallStructLimit; 347 348 /// The largest number of element an array can have and still be 349 /// considered "small". 350 /// 351 /// This is currently used to decide whether or not it is worth "forcing" a 352 /// LazyCompoundVal on bind. 353 /// 354 /// This is controlled by 'region-store-small-struct-limit' option. 355 /// To disable all small-struct-dependent behavior, set the option to "0". 356 unsigned SmallArrayLimit; 357 358 /// A helper used to populate the work list with the given set of 359 /// regions. 360 void populateWorkList(InvalidateRegionsWorker &W, 361 ArrayRef<SVal> Values, 362 InvalidatedRegions *TopLevelRegions); 363 364 public: 365 RegionStoreManager(ProgramStateManager &mgr) 366 : StoreManager(mgr), RBFactory(mgr.getAllocator()), 367 CBFactory(mgr.getAllocator()), SmallStructLimit(0), SmallArrayLimit(0) { 368 ExprEngine &Eng = StateMgr.getOwningEngine(); 369 AnalyzerOptions &Options = Eng.getAnalysisManager().options; 370 SmallStructLimit = Options.RegionStoreSmallStructLimit; 371 SmallArrayLimit = Options.RegionStoreSmallArrayLimit; 372 } 373 374 /// setImplicitDefaultValue - Set the default binding for the provided 375 /// MemRegion to the value implicitly defined for compound literals when 376 /// the value is not specified. 377 RegionBindingsRef setImplicitDefaultValue(RegionBindingsConstRef B, 378 const MemRegion *R, QualType T); 379 380 /// ArrayToPointer - Emulates the "decay" of an array to a pointer 381 /// type. 'Array' represents the lvalue of the array being decayed 382 /// to a pointer, and the returned SVal represents the decayed 383 /// version of that lvalue (i.e., a pointer to the first element of 384 /// the array). This is called by ExprEngine when evaluating 385 /// casts from arrays to pointers. 386 SVal ArrayToPointer(Loc Array, QualType ElementTy) override; 387 388 /// Creates the Store that correctly represents memory contents before 389 /// the beginning of the analysis of the given top-level stack frame. 390 StoreRef getInitialStore(const LocationContext *InitLoc) override { 391 bool IsMainAnalysis = false; 392 if (const auto *FD = dyn_cast<FunctionDecl>(InitLoc->getDecl())) 393 IsMainAnalysis = FD->isMain() && !Ctx.getLangOpts().CPlusPlus; 394 return StoreRef(RegionBindingsRef( 395 RegionBindingsRef::ParentTy(RBFactory.getEmptyMap(), RBFactory), 396 CBFactory, IsMainAnalysis).asStore(), *this); 397 } 398 399 //===-------------------------------------------------------------------===// 400 // Binding values to regions. 401 //===-------------------------------------------------------------------===// 402 RegionBindingsRef invalidateGlobalRegion(MemRegion::Kind K, 403 const Expr *Ex, 404 unsigned Count, 405 const LocationContext *LCtx, 406 RegionBindingsRef B, 407 InvalidatedRegions *Invalidated); 408 409 StoreRef invalidateRegions(Store store, 410 ArrayRef<SVal> Values, 411 const Expr *E, unsigned Count, 412 const LocationContext *LCtx, 413 const CallEvent *Call, 414 InvalidatedSymbols &IS, 415 RegionAndSymbolInvalidationTraits &ITraits, 416 InvalidatedRegions *Invalidated, 417 InvalidatedRegions *InvalidatedTopLevel) override; 418 419 bool scanReachableSymbols(Store S, const MemRegion *R, 420 ScanReachableSymbols &Callbacks) override; 421 422 RegionBindingsRef removeSubRegionBindings(RegionBindingsConstRef B, 423 const SubRegion *R); 424 Optional<SVal> 425 getConstantValFromConstArrayInitializer(RegionBindingsConstRef B, 426 const ElementRegion *R); 427 Optional<SVal> 428 getSValFromInitListExpr(const InitListExpr *ILE, 429 const SmallVector<uint64_t, 2> &ConcreteOffsets, 430 QualType ElemT); 431 SVal getSValFromStringLiteral(const StringLiteral *SL, uint64_t Offset, 432 QualType ElemT); 433 434 public: // Part of public interface to class. 435 436 StoreRef Bind(Store store, Loc LV, SVal V) override { 437 return StoreRef(bind(getRegionBindings(store), LV, V).asStore(), *this); 438 } 439 440 RegionBindingsRef bind(RegionBindingsConstRef B, Loc LV, SVal V); 441 442 // BindDefaultInitial is only used to initialize a region with 443 // a default value. 444 StoreRef BindDefaultInitial(Store store, const MemRegion *R, 445 SVal V) override { 446 RegionBindingsRef B = getRegionBindings(store); 447 // Use other APIs when you have to wipe the region that was initialized 448 // earlier. 449 assert(!(B.getDefaultBinding(R) || B.getDirectBinding(R)) && 450 "Double initialization!"); 451 B = B.addBinding(BindingKey::Make(R, BindingKey::Default), V); 452 return StoreRef(B.asImmutableMap().getRootWithoutRetain(), *this); 453 } 454 455 // BindDefaultZero is used for zeroing constructors that may accidentally 456 // overwrite existing bindings. 457 StoreRef BindDefaultZero(Store store, const MemRegion *R) override { 458 // FIXME: The offsets of empty bases can be tricky because of 459 // of the so called "empty base class optimization". 460 // If a base class has been optimized out 461 // we should not try to create a binding, otherwise we should. 462 // Unfortunately, at the moment ASTRecordLayout doesn't expose 463 // the actual sizes of the empty bases 464 // and trying to infer them from offsets/alignments 465 // seems to be error-prone and non-trivial because of the trailing padding. 466 // As a temporary mitigation we don't create bindings for empty bases. 467 if (const auto *BR = dyn_cast<CXXBaseObjectRegion>(R)) 468 if (BR->getDecl()->isEmpty()) 469 return StoreRef(store, *this); 470 471 RegionBindingsRef B = getRegionBindings(store); 472 SVal V = svalBuilder.makeZeroVal(Ctx.CharTy); 473 B = removeSubRegionBindings(B, cast<SubRegion>(R)); 474 B = B.addBinding(BindingKey::Make(R, BindingKey::Default), V); 475 return StoreRef(B.asImmutableMap().getRootWithoutRetain(), *this); 476 } 477 478 /// Attempt to extract the fields of \p LCV and bind them to the struct region 479 /// \p R. 480 /// 481 /// This path is used when it seems advantageous to "force" loading the values 482 /// within a LazyCompoundVal to bind memberwise to the struct region, rather 483 /// than using a Default binding at the base of the entire region. This is a 484 /// heuristic attempting to avoid building long chains of LazyCompoundVals. 485 /// 486 /// \returns The updated store bindings, or \c None if binding non-lazily 487 /// would be too expensive. 488 Optional<RegionBindingsRef> tryBindSmallStruct(RegionBindingsConstRef B, 489 const TypedValueRegion *R, 490 const RecordDecl *RD, 491 nonloc::LazyCompoundVal LCV); 492 493 /// BindStruct - Bind a compound value to a structure. 494 RegionBindingsRef bindStruct(RegionBindingsConstRef B, 495 const TypedValueRegion* R, SVal V); 496 497 /// BindVector - Bind a compound value to a vector. 498 RegionBindingsRef bindVector(RegionBindingsConstRef B, 499 const TypedValueRegion* R, SVal V); 500 501 Optional<RegionBindingsRef> tryBindSmallArray(RegionBindingsConstRef B, 502 const TypedValueRegion *R, 503 const ArrayType *AT, 504 nonloc::LazyCompoundVal LCV); 505 506 RegionBindingsRef bindArray(RegionBindingsConstRef B, 507 const TypedValueRegion* R, 508 SVal V); 509 510 /// Clears out all bindings in the given region and assigns a new value 511 /// as a Default binding. 512 RegionBindingsRef bindAggregate(RegionBindingsConstRef B, 513 const TypedRegion *R, 514 SVal DefaultVal); 515 516 /// Create a new store with the specified binding removed. 517 /// \param ST the original store, that is the basis for the new store. 518 /// \param L the location whose binding should be removed. 519 StoreRef killBinding(Store ST, Loc L) override; 520 521 void incrementReferenceCount(Store store) override { 522 getRegionBindings(store).manualRetain(); 523 } 524 525 /// If the StoreManager supports it, decrement the reference count of 526 /// the specified Store object. If the reference count hits 0, the memory 527 /// associated with the object is recycled. 528 void decrementReferenceCount(Store store) override { 529 getRegionBindings(store).manualRelease(); 530 } 531 532 bool includedInBindings(Store store, const MemRegion *region) const override; 533 534 /// Return the value bound to specified location in a given state. 535 /// 536 /// The high level logic for this method is this: 537 /// getBinding (L) 538 /// if L has binding 539 /// return L's binding 540 /// else if L is in killset 541 /// return unknown 542 /// else 543 /// if L is on stack or heap 544 /// return undefined 545 /// else 546 /// return symbolic 547 SVal getBinding(Store S, Loc L, QualType T) override { 548 return getBinding(getRegionBindings(S), L, T); 549 } 550 551 Optional<SVal> getDefaultBinding(Store S, const MemRegion *R) override { 552 RegionBindingsRef B = getRegionBindings(S); 553 // Default bindings are always applied over a base region so look up the 554 // base region's default binding, otherwise the lookup will fail when R 555 // is at an offset from R->getBaseRegion(). 556 return B.getDefaultBinding(R->getBaseRegion()); 557 } 558 559 SVal getBinding(RegionBindingsConstRef B, Loc L, QualType T = QualType()); 560 561 SVal getBindingForElement(RegionBindingsConstRef B, const ElementRegion *R); 562 563 SVal getBindingForField(RegionBindingsConstRef B, const FieldRegion *R); 564 565 SVal getBindingForObjCIvar(RegionBindingsConstRef B, const ObjCIvarRegion *R); 566 567 SVal getBindingForVar(RegionBindingsConstRef B, const VarRegion *R); 568 569 SVal getBindingForLazySymbol(const TypedValueRegion *R); 570 571 SVal getBindingForFieldOrElementCommon(RegionBindingsConstRef B, 572 const TypedValueRegion *R, 573 QualType Ty); 574 575 SVal getLazyBinding(const SubRegion *LazyBindingRegion, 576 RegionBindingsRef LazyBinding); 577 578 /// Get bindings for the values in a struct and return a CompoundVal, used 579 /// when doing struct copy: 580 /// struct s x, y; 581 /// x = y; 582 /// y's value is retrieved by this method. 583 SVal getBindingForStruct(RegionBindingsConstRef B, const TypedValueRegion *R); 584 SVal getBindingForArray(RegionBindingsConstRef B, const TypedValueRegion *R); 585 NonLoc createLazyBinding(RegionBindingsConstRef B, const TypedValueRegion *R); 586 587 /// Used to lazily generate derived symbols for bindings that are defined 588 /// implicitly by default bindings in a super region. 589 /// 590 /// Note that callers may need to specially handle LazyCompoundVals, which 591 /// are returned as is in case the caller needs to treat them differently. 592 Optional<SVal> getBindingForDerivedDefaultValue(RegionBindingsConstRef B, 593 const MemRegion *superR, 594 const TypedValueRegion *R, 595 QualType Ty); 596 597 /// Get the state and region whose binding this region \p R corresponds to. 598 /// 599 /// If there is no lazy binding for \p R, the returned value will have a null 600 /// \c second. Note that a null pointer can represents a valid Store. 601 std::pair<Store, const SubRegion *> 602 findLazyBinding(RegionBindingsConstRef B, const SubRegion *R, 603 const SubRegion *originalRegion); 604 605 /// Returns the cached set of interesting SVals contained within a lazy 606 /// binding. 607 /// 608 /// The precise value of "interesting" is determined for the purposes of 609 /// RegionStore's internal analysis. It must always contain all regions and 610 /// symbols, but may omit constants and other kinds of SVal. 611 const SValListTy &getInterestingValues(nonloc::LazyCompoundVal LCV); 612 613 //===------------------------------------------------------------------===// 614 // State pruning. 615 //===------------------------------------------------------------------===// 616 617 /// removeDeadBindings - Scans the RegionStore of 'state' for dead values. 618 /// It returns a new Store with these values removed. 619 StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx, 620 SymbolReaper& SymReaper) override; 621 622 //===------------------------------------------------------------------===// 623 // Utility methods. 624 //===------------------------------------------------------------------===// 625 626 RegionBindingsRef getRegionBindings(Store store) const { 627 llvm::PointerIntPair<Store, 1, bool> Ptr; 628 Ptr.setFromOpaqueValue(const_cast<void *>(store)); 629 return RegionBindingsRef( 630 CBFactory, 631 static_cast<const RegionBindings::TreeTy *>(Ptr.getPointer()), 632 RBFactory.getTreeFactory(), 633 Ptr.getInt()); 634 } 635 636 void printJson(raw_ostream &Out, Store S, const char *NL = "\n", 637 unsigned int Space = 0, bool IsDot = false) const override; 638 639 void iterBindings(Store store, BindingsHandler& f) override { 640 RegionBindingsRef B = getRegionBindings(store); 641 for (RegionBindingsRef::iterator I = B.begin(), E = B.end(); I != E; ++I) { 642 const ClusterBindings &Cluster = I.getData(); 643 for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); 644 CI != CE; ++CI) { 645 const BindingKey &K = CI.getKey(); 646 if (!K.isDirect()) 647 continue; 648 if (const SubRegion *R = dyn_cast<SubRegion>(K.getRegion())) { 649 // FIXME: Possibly incorporate the offset? 650 if (!f.HandleBinding(*this, store, R, CI.getData())) 651 return; 652 } 653 } 654 } 655 } 656 }; 657 658 } // end anonymous namespace 659 660 //===----------------------------------------------------------------------===// 661 // RegionStore creation. 662 //===----------------------------------------------------------------------===// 663 664 std::unique_ptr<StoreManager> 665 ento::CreateRegionStoreManager(ProgramStateManager &StMgr) { 666 return std::make_unique<RegionStoreManager>(StMgr); 667 } 668 669 //===----------------------------------------------------------------------===// 670 // Region Cluster analysis. 671 //===----------------------------------------------------------------------===// 672 673 namespace { 674 /// Used to determine which global regions are automatically included in the 675 /// initial worklist of a ClusterAnalysis. 676 enum GlobalsFilterKind { 677 /// Don't include any global regions. 678 GFK_None, 679 /// Only include system globals. 680 GFK_SystemOnly, 681 /// Include all global regions. 682 GFK_All 683 }; 684 685 template <typename DERIVED> 686 class ClusterAnalysis { 687 protected: 688 typedef llvm::DenseMap<const MemRegion *, const ClusterBindings *> ClusterMap; 689 typedef const MemRegion * WorkListElement; 690 typedef SmallVector<WorkListElement, 10> WorkList; 691 692 llvm::SmallPtrSet<const ClusterBindings *, 16> Visited; 693 694 WorkList WL; 695 696 RegionStoreManager &RM; 697 ASTContext &Ctx; 698 SValBuilder &svalBuilder; 699 700 RegionBindingsRef B; 701 702 703 protected: 704 const ClusterBindings *getCluster(const MemRegion *R) { 705 return B.lookup(R); 706 } 707 708 /// Returns true if all clusters in the given memspace should be initially 709 /// included in the cluster analysis. Subclasses may provide their 710 /// own implementation. 711 bool includeEntireMemorySpace(const MemRegion *Base) { 712 return false; 713 } 714 715 public: 716 ClusterAnalysis(RegionStoreManager &rm, ProgramStateManager &StateMgr, 717 RegionBindingsRef b) 718 : RM(rm), Ctx(StateMgr.getContext()), 719 svalBuilder(StateMgr.getSValBuilder()), B(std::move(b)) {} 720 721 RegionBindingsRef getRegionBindings() const { return B; } 722 723 bool isVisited(const MemRegion *R) { 724 return Visited.count(getCluster(R)); 725 } 726 727 void GenerateClusters() { 728 // Scan the entire set of bindings and record the region clusters. 729 for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end(); 730 RI != RE; ++RI){ 731 const MemRegion *Base = RI.getKey(); 732 733 const ClusterBindings &Cluster = RI.getData(); 734 assert(!Cluster.isEmpty() && "Empty clusters should be removed"); 735 static_cast<DERIVED*>(this)->VisitAddedToCluster(Base, Cluster); 736 737 // If the base's memspace should be entirely invalidated, add the cluster 738 // to the workspace up front. 739 if (static_cast<DERIVED*>(this)->includeEntireMemorySpace(Base)) 740 AddToWorkList(WorkListElement(Base), &Cluster); 741 } 742 } 743 744 bool AddToWorkList(WorkListElement E, const ClusterBindings *C) { 745 if (C && !Visited.insert(C).second) 746 return false; 747 WL.push_back(E); 748 return true; 749 } 750 751 bool AddToWorkList(const MemRegion *R) { 752 return static_cast<DERIVED*>(this)->AddToWorkList(R); 753 } 754 755 void RunWorkList() { 756 while (!WL.empty()) { 757 WorkListElement E = WL.pop_back_val(); 758 const MemRegion *BaseR = E; 759 760 static_cast<DERIVED*>(this)->VisitCluster(BaseR, getCluster(BaseR)); 761 } 762 } 763 764 void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C) {} 765 void VisitCluster(const MemRegion *baseR, const ClusterBindings *C) {} 766 767 void VisitCluster(const MemRegion *BaseR, const ClusterBindings *C, 768 bool Flag) { 769 static_cast<DERIVED*>(this)->VisitCluster(BaseR, C); 770 } 771 }; 772 } 773 774 //===----------------------------------------------------------------------===// 775 // Binding invalidation. 776 //===----------------------------------------------------------------------===// 777 778 bool RegionStoreManager::scanReachableSymbols(Store S, const MemRegion *R, 779 ScanReachableSymbols &Callbacks) { 780 assert(R == R->getBaseRegion() && "Should only be called for base regions"); 781 RegionBindingsRef B = getRegionBindings(S); 782 const ClusterBindings *Cluster = B.lookup(R); 783 784 if (!Cluster) 785 return true; 786 787 for (ClusterBindings::iterator RI = Cluster->begin(), RE = Cluster->end(); 788 RI != RE; ++RI) { 789 if (!Callbacks.scan(RI.getData())) 790 return false; 791 } 792 793 return true; 794 } 795 796 static inline bool isUnionField(const FieldRegion *FR) { 797 return FR->getDecl()->getParent()->isUnion(); 798 } 799 800 typedef SmallVector<const FieldDecl *, 8> FieldVector; 801 802 static void getSymbolicOffsetFields(BindingKey K, FieldVector &Fields) { 803 assert(K.hasSymbolicOffset() && "Not implemented for concrete offset keys"); 804 805 const MemRegion *Base = K.getConcreteOffsetRegion(); 806 const MemRegion *R = K.getRegion(); 807 808 while (R != Base) { 809 if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) 810 if (!isUnionField(FR)) 811 Fields.push_back(FR->getDecl()); 812 813 R = cast<SubRegion>(R)->getSuperRegion(); 814 } 815 } 816 817 static bool isCompatibleWithFields(BindingKey K, const FieldVector &Fields) { 818 assert(K.hasSymbolicOffset() && "Not implemented for concrete offset keys"); 819 820 if (Fields.empty()) 821 return true; 822 823 FieldVector FieldsInBindingKey; 824 getSymbolicOffsetFields(K, FieldsInBindingKey); 825 826 ptrdiff_t Delta = FieldsInBindingKey.size() - Fields.size(); 827 if (Delta >= 0) 828 return std::equal(FieldsInBindingKey.begin() + Delta, 829 FieldsInBindingKey.end(), 830 Fields.begin()); 831 else 832 return std::equal(FieldsInBindingKey.begin(), FieldsInBindingKey.end(), 833 Fields.begin() - Delta); 834 } 835 836 /// Collects all bindings in \p Cluster that may refer to bindings within 837 /// \p Top. 838 /// 839 /// Each binding is a pair whose \c first is the key (a BindingKey) and whose 840 /// \c second is the value (an SVal). 841 /// 842 /// The \p IncludeAllDefaultBindings parameter specifies whether to include 843 /// default bindings that may extend beyond \p Top itself, e.g. if \p Top is 844 /// an aggregate within a larger aggregate with a default binding. 845 static void 846 collectSubRegionBindings(SmallVectorImpl<BindingPair> &Bindings, 847 SValBuilder &SVB, const ClusterBindings &Cluster, 848 const SubRegion *Top, BindingKey TopKey, 849 bool IncludeAllDefaultBindings) { 850 FieldVector FieldsInSymbolicSubregions; 851 if (TopKey.hasSymbolicOffset()) { 852 getSymbolicOffsetFields(TopKey, FieldsInSymbolicSubregions); 853 Top = TopKey.getConcreteOffsetRegion(); 854 TopKey = BindingKey::Make(Top, BindingKey::Default); 855 } 856 857 // Find the length (in bits) of the region being invalidated. 858 uint64_t Length = UINT64_MAX; 859 SVal Extent = Top->getMemRegionManager().getStaticSize(Top, SVB); 860 if (Optional<nonloc::ConcreteInt> ExtentCI = 861 Extent.getAs<nonloc::ConcreteInt>()) { 862 const llvm::APSInt &ExtentInt = ExtentCI->getValue(); 863 assert(ExtentInt.isNonNegative() || ExtentInt.isUnsigned()); 864 // Extents are in bytes but region offsets are in bits. Be careful! 865 Length = ExtentInt.getLimitedValue() * SVB.getContext().getCharWidth(); 866 } else if (const FieldRegion *FR = dyn_cast<FieldRegion>(Top)) { 867 if (FR->getDecl()->isBitField()) 868 Length = FR->getDecl()->getBitWidthValue(SVB.getContext()); 869 } 870 871 for (ClusterBindings::iterator I = Cluster.begin(), E = Cluster.end(); 872 I != E; ++I) { 873 BindingKey NextKey = I.getKey(); 874 if (NextKey.getRegion() == TopKey.getRegion()) { 875 // FIXME: This doesn't catch the case where we're really invalidating a 876 // region with a symbolic offset. Example: 877 // R: points[i].y 878 // Next: points[0].x 879 880 if (NextKey.getOffset() > TopKey.getOffset() && 881 NextKey.getOffset() - TopKey.getOffset() < Length) { 882 // Case 1: The next binding is inside the region we're invalidating. 883 // Include it. 884 Bindings.push_back(*I); 885 886 } else if (NextKey.getOffset() == TopKey.getOffset()) { 887 // Case 2: The next binding is at the same offset as the region we're 888 // invalidating. In this case, we need to leave default bindings alone, 889 // since they may be providing a default value for a regions beyond what 890 // we're invalidating. 891 // FIXME: This is probably incorrect; consider invalidating an outer 892 // struct whose first field is bound to a LazyCompoundVal. 893 if (IncludeAllDefaultBindings || NextKey.isDirect()) 894 Bindings.push_back(*I); 895 } 896 897 } else if (NextKey.hasSymbolicOffset()) { 898 const MemRegion *Base = NextKey.getConcreteOffsetRegion(); 899 if (Top->isSubRegionOf(Base) && Top != Base) { 900 // Case 3: The next key is symbolic and we just changed something within 901 // its concrete region. We don't know if the binding is still valid, so 902 // we'll be conservative and include it. 903 if (IncludeAllDefaultBindings || NextKey.isDirect()) 904 if (isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions)) 905 Bindings.push_back(*I); 906 } else if (const SubRegion *BaseSR = dyn_cast<SubRegion>(Base)) { 907 // Case 4: The next key is symbolic, but we changed a known 908 // super-region. In this case the binding is certainly included. 909 if (BaseSR->isSubRegionOf(Top)) 910 if (isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions)) 911 Bindings.push_back(*I); 912 } 913 } 914 } 915 } 916 917 static void 918 collectSubRegionBindings(SmallVectorImpl<BindingPair> &Bindings, 919 SValBuilder &SVB, const ClusterBindings &Cluster, 920 const SubRegion *Top, bool IncludeAllDefaultBindings) { 921 collectSubRegionBindings(Bindings, SVB, Cluster, Top, 922 BindingKey::Make(Top, BindingKey::Default), 923 IncludeAllDefaultBindings); 924 } 925 926 RegionBindingsRef 927 RegionStoreManager::removeSubRegionBindings(RegionBindingsConstRef B, 928 const SubRegion *Top) { 929 BindingKey TopKey = BindingKey::Make(Top, BindingKey::Default); 930 const MemRegion *ClusterHead = TopKey.getBaseRegion(); 931 932 if (Top == ClusterHead) { 933 // We can remove an entire cluster's bindings all in one go. 934 return B.remove(Top); 935 } 936 937 const ClusterBindings *Cluster = B.lookup(ClusterHead); 938 if (!Cluster) { 939 // If we're invalidating a region with a symbolic offset, we need to make 940 // sure we don't treat the base region as uninitialized anymore. 941 if (TopKey.hasSymbolicOffset()) { 942 const SubRegion *Concrete = TopKey.getConcreteOffsetRegion(); 943 return B.addBinding(Concrete, BindingKey::Default, UnknownVal()); 944 } 945 return B; 946 } 947 948 SmallVector<BindingPair, 32> Bindings; 949 collectSubRegionBindings(Bindings, svalBuilder, *Cluster, Top, TopKey, 950 /*IncludeAllDefaultBindings=*/false); 951 952 ClusterBindingsRef Result(*Cluster, CBFactory); 953 for (SmallVectorImpl<BindingPair>::const_iterator I = Bindings.begin(), 954 E = Bindings.end(); 955 I != E; ++I) 956 Result = Result.remove(I->first); 957 958 // If we're invalidating a region with a symbolic offset, we need to make sure 959 // we don't treat the base region as uninitialized anymore. 960 // FIXME: This isn't very precise; see the example in 961 // collectSubRegionBindings. 962 if (TopKey.hasSymbolicOffset()) { 963 const SubRegion *Concrete = TopKey.getConcreteOffsetRegion(); 964 Result = Result.add(BindingKey::Make(Concrete, BindingKey::Default), 965 UnknownVal()); 966 } 967 968 if (Result.isEmpty()) 969 return B.remove(ClusterHead); 970 return B.add(ClusterHead, Result.asImmutableMap()); 971 } 972 973 namespace { 974 class InvalidateRegionsWorker : public ClusterAnalysis<InvalidateRegionsWorker> 975 { 976 const Expr *Ex; 977 unsigned Count; 978 const LocationContext *LCtx; 979 InvalidatedSymbols &IS; 980 RegionAndSymbolInvalidationTraits &ITraits; 981 StoreManager::InvalidatedRegions *Regions; 982 GlobalsFilterKind GlobalsFilter; 983 public: 984 InvalidateRegionsWorker(RegionStoreManager &rm, 985 ProgramStateManager &stateMgr, 986 RegionBindingsRef b, 987 const Expr *ex, unsigned count, 988 const LocationContext *lctx, 989 InvalidatedSymbols &is, 990 RegionAndSymbolInvalidationTraits &ITraitsIn, 991 StoreManager::InvalidatedRegions *r, 992 GlobalsFilterKind GFK) 993 : ClusterAnalysis<InvalidateRegionsWorker>(rm, stateMgr, b), 994 Ex(ex), Count(count), LCtx(lctx), IS(is), ITraits(ITraitsIn), Regions(r), 995 GlobalsFilter(GFK) {} 996 997 void VisitCluster(const MemRegion *baseR, const ClusterBindings *C); 998 void VisitBinding(SVal V); 999 1000 using ClusterAnalysis::AddToWorkList; 1001 1002 bool AddToWorkList(const MemRegion *R); 1003 1004 /// Returns true if all clusters in the memory space for \p Base should be 1005 /// be invalidated. 1006 bool includeEntireMemorySpace(const MemRegion *Base); 1007 1008 /// Returns true if the memory space of the given region is one of the global 1009 /// regions specially included at the start of invalidation. 1010 bool isInitiallyIncludedGlobalRegion(const MemRegion *R); 1011 }; 1012 } 1013 1014 bool InvalidateRegionsWorker::AddToWorkList(const MemRegion *R) { 1015 bool doNotInvalidateSuperRegion = ITraits.hasTrait( 1016 R, RegionAndSymbolInvalidationTraits::TK_DoNotInvalidateSuperRegion); 1017 const MemRegion *BaseR = doNotInvalidateSuperRegion ? R : R->getBaseRegion(); 1018 return AddToWorkList(WorkListElement(BaseR), getCluster(BaseR)); 1019 } 1020 1021 void InvalidateRegionsWorker::VisitBinding(SVal V) { 1022 // A symbol? Mark it touched by the invalidation. 1023 if (SymbolRef Sym = V.getAsSymbol()) 1024 IS.insert(Sym); 1025 1026 if (const MemRegion *R = V.getAsRegion()) { 1027 AddToWorkList(R); 1028 return; 1029 } 1030 1031 // Is it a LazyCompoundVal? All references get invalidated as well. 1032 if (Optional<nonloc::LazyCompoundVal> LCS = 1033 V.getAs<nonloc::LazyCompoundVal>()) { 1034 1035 const RegionStoreManager::SValListTy &Vals = RM.getInterestingValues(*LCS); 1036 1037 for (RegionStoreManager::SValListTy::const_iterator I = Vals.begin(), 1038 E = Vals.end(); 1039 I != E; ++I) 1040 VisitBinding(*I); 1041 1042 return; 1043 } 1044 } 1045 1046 void InvalidateRegionsWorker::VisitCluster(const MemRegion *baseR, 1047 const ClusterBindings *C) { 1048 1049 bool PreserveRegionsContents = 1050 ITraits.hasTrait(baseR, 1051 RegionAndSymbolInvalidationTraits::TK_PreserveContents); 1052 1053 if (C) { 1054 for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I) 1055 VisitBinding(I.getData()); 1056 1057 // Invalidate regions contents. 1058 if (!PreserveRegionsContents) 1059 B = B.remove(baseR); 1060 } 1061 1062 if (const auto *TO = dyn_cast<TypedValueRegion>(baseR)) { 1063 if (const auto *RD = TO->getValueType()->getAsCXXRecordDecl()) { 1064 1065 // Lambdas can affect all static local variables without explicitly 1066 // capturing those. 1067 // We invalidate all static locals referenced inside the lambda body. 1068 if (RD->isLambda() && RD->getLambdaCallOperator()->getBody()) { 1069 using namespace ast_matchers; 1070 1071 const char *DeclBind = "DeclBind"; 1072 StatementMatcher RefToStatic = stmt(hasDescendant(declRefExpr( 1073 to(varDecl(hasStaticStorageDuration()).bind(DeclBind))))); 1074 auto Matches = 1075 match(RefToStatic, *RD->getLambdaCallOperator()->getBody(), 1076 RD->getASTContext()); 1077 1078 for (BoundNodes &Match : Matches) { 1079 auto *VD = Match.getNodeAs<VarDecl>(DeclBind); 1080 const VarRegion *ToInvalidate = 1081 RM.getRegionManager().getVarRegion(VD, LCtx); 1082 AddToWorkList(ToInvalidate); 1083 } 1084 } 1085 } 1086 } 1087 1088 // BlockDataRegion? If so, invalidate captured variables that are passed 1089 // by reference. 1090 if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(baseR)) { 1091 for (BlockDataRegion::referenced_vars_iterator 1092 BI = BR->referenced_vars_begin(), BE = BR->referenced_vars_end() ; 1093 BI != BE; ++BI) { 1094 const VarRegion *VR = BI.getCapturedRegion(); 1095 const VarDecl *VD = VR->getDecl(); 1096 if (VD->hasAttr<BlocksAttr>() || !VD->hasLocalStorage()) { 1097 AddToWorkList(VR); 1098 } 1099 else if (Loc::isLocType(VR->getValueType())) { 1100 // Map the current bindings to a Store to retrieve the value 1101 // of the binding. If that binding itself is a region, we should 1102 // invalidate that region. This is because a block may capture 1103 // a pointer value, but the thing pointed by that pointer may 1104 // get invalidated. 1105 SVal V = RM.getBinding(B, loc::MemRegionVal(VR)); 1106 if (Optional<Loc> L = V.getAs<Loc>()) { 1107 if (const MemRegion *LR = L->getAsRegion()) 1108 AddToWorkList(LR); 1109 } 1110 } 1111 } 1112 return; 1113 } 1114 1115 // Symbolic region? 1116 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) 1117 IS.insert(SR->getSymbol()); 1118 1119 // Nothing else should be done in the case when we preserve regions context. 1120 if (PreserveRegionsContents) 1121 return; 1122 1123 // Otherwise, we have a normal data region. Record that we touched the region. 1124 if (Regions) 1125 Regions->push_back(baseR); 1126 1127 if (isa<AllocaRegion, SymbolicRegion>(baseR)) { 1128 // Invalidate the region by setting its default value to 1129 // conjured symbol. The type of the symbol is irrelevant. 1130 DefinedOrUnknownSVal V = 1131 svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, Ctx.IntTy, Count); 1132 B = B.addBinding(baseR, BindingKey::Default, V); 1133 return; 1134 } 1135 1136 if (!baseR->isBoundable()) 1137 return; 1138 1139 const TypedValueRegion *TR = cast<TypedValueRegion>(baseR); 1140 QualType T = TR->getValueType(); 1141 1142 if (isInitiallyIncludedGlobalRegion(baseR)) { 1143 // If the region is a global and we are invalidating all globals, 1144 // erasing the entry is good enough. This causes all globals to be lazily 1145 // symbolicated from the same base symbol. 1146 return; 1147 } 1148 1149 if (T->isRecordType()) { 1150 // Invalidate the region by setting its default value to 1151 // conjured symbol. The type of the symbol is irrelevant. 1152 DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, 1153 Ctx.IntTy, Count); 1154 B = B.addBinding(baseR, BindingKey::Default, V); 1155 return; 1156 } 1157 1158 if (const ArrayType *AT = Ctx.getAsArrayType(T)) { 1159 bool doNotInvalidateSuperRegion = ITraits.hasTrait( 1160 baseR, 1161 RegionAndSymbolInvalidationTraits::TK_DoNotInvalidateSuperRegion); 1162 1163 if (doNotInvalidateSuperRegion) { 1164 // We are not doing blank invalidation of the whole array region so we 1165 // have to manually invalidate each elements. 1166 Optional<uint64_t> NumElements; 1167 1168 // Compute lower and upper offsets for region within array. 1169 if (const ConstantArrayType *CAT = dyn_cast<ConstantArrayType>(AT)) 1170 NumElements = CAT->getSize().getZExtValue(); 1171 if (!NumElements) // We are not dealing with a constant size array 1172 goto conjure_default; 1173 QualType ElementTy = AT->getElementType(); 1174 uint64_t ElemSize = Ctx.getTypeSize(ElementTy); 1175 const RegionOffset &RO = baseR->getAsOffset(); 1176 const MemRegion *SuperR = baseR->getBaseRegion(); 1177 if (RO.hasSymbolicOffset()) { 1178 // If base region has a symbolic offset, 1179 // we revert to invalidating the super region. 1180 if (SuperR) 1181 AddToWorkList(SuperR); 1182 goto conjure_default; 1183 } 1184 1185 uint64_t LowerOffset = RO.getOffset(); 1186 uint64_t UpperOffset = LowerOffset + *NumElements * ElemSize; 1187 bool UpperOverflow = UpperOffset < LowerOffset; 1188 1189 // Invalidate regions which are within array boundaries, 1190 // or have a symbolic offset. 1191 if (!SuperR) 1192 goto conjure_default; 1193 1194 const ClusterBindings *C = B.lookup(SuperR); 1195 if (!C) 1196 goto conjure_default; 1197 1198 for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; 1199 ++I) { 1200 const BindingKey &BK = I.getKey(); 1201 Optional<uint64_t> ROffset = 1202 BK.hasSymbolicOffset() ? Optional<uint64_t>() : BK.getOffset(); 1203 1204 // Check offset is not symbolic and within array's boundaries. 1205 // Handles arrays of 0 elements and of 0-sized elements as well. 1206 if (!ROffset || 1207 ((*ROffset >= LowerOffset && *ROffset < UpperOffset) || 1208 (UpperOverflow && 1209 (*ROffset >= LowerOffset || *ROffset < UpperOffset)) || 1210 (LowerOffset == UpperOffset && *ROffset == LowerOffset))) { 1211 B = B.removeBinding(I.getKey()); 1212 // Bound symbolic regions need to be invalidated for dead symbol 1213 // detection. 1214 SVal V = I.getData(); 1215 const MemRegion *R = V.getAsRegion(); 1216 if (isa_and_nonnull<SymbolicRegion>(R)) 1217 VisitBinding(V); 1218 } 1219 } 1220 } 1221 conjure_default: 1222 // Set the default value of the array to conjured symbol. 1223 DefinedOrUnknownSVal V = 1224 svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, 1225 AT->getElementType(), Count); 1226 B = B.addBinding(baseR, BindingKey::Default, V); 1227 return; 1228 } 1229 1230 DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, 1231 T,Count); 1232 assert(SymbolManager::canSymbolicate(T) || V.isUnknown()); 1233 B = B.addBinding(baseR, BindingKey::Direct, V); 1234 } 1235 1236 bool InvalidateRegionsWorker::isInitiallyIncludedGlobalRegion( 1237 const MemRegion *R) { 1238 switch (GlobalsFilter) { 1239 case GFK_None: 1240 return false; 1241 case GFK_SystemOnly: 1242 return isa<GlobalSystemSpaceRegion>(R->getMemorySpace()); 1243 case GFK_All: 1244 return isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace()); 1245 } 1246 1247 llvm_unreachable("unknown globals filter"); 1248 } 1249 1250 bool InvalidateRegionsWorker::includeEntireMemorySpace(const MemRegion *Base) { 1251 if (isInitiallyIncludedGlobalRegion(Base)) 1252 return true; 1253 1254 const MemSpaceRegion *MemSpace = Base->getMemorySpace(); 1255 return ITraits.hasTrait(MemSpace, 1256 RegionAndSymbolInvalidationTraits::TK_EntireMemSpace); 1257 } 1258 1259 RegionBindingsRef 1260 RegionStoreManager::invalidateGlobalRegion(MemRegion::Kind K, 1261 const Expr *Ex, 1262 unsigned Count, 1263 const LocationContext *LCtx, 1264 RegionBindingsRef B, 1265 InvalidatedRegions *Invalidated) { 1266 // Bind the globals memory space to a new symbol that we will use to derive 1267 // the bindings for all globals. 1268 const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion(K); 1269 SVal V = svalBuilder.conjureSymbolVal(/* symbolTag = */ (const void*) GS, Ex, LCtx, 1270 /* type does not matter */ Ctx.IntTy, 1271 Count); 1272 1273 B = B.removeBinding(GS) 1274 .addBinding(BindingKey::Make(GS, BindingKey::Default), V); 1275 1276 // Even if there are no bindings in the global scope, we still need to 1277 // record that we touched it. 1278 if (Invalidated) 1279 Invalidated->push_back(GS); 1280 1281 return B; 1282 } 1283 1284 void RegionStoreManager::populateWorkList(InvalidateRegionsWorker &W, 1285 ArrayRef<SVal> Values, 1286 InvalidatedRegions *TopLevelRegions) { 1287 for (ArrayRef<SVal>::iterator I = Values.begin(), 1288 E = Values.end(); I != E; ++I) { 1289 SVal V = *I; 1290 if (Optional<nonloc::LazyCompoundVal> LCS = 1291 V.getAs<nonloc::LazyCompoundVal>()) { 1292 1293 const SValListTy &Vals = getInterestingValues(*LCS); 1294 1295 for (SValListTy::const_iterator I = Vals.begin(), 1296 E = Vals.end(); I != E; ++I) { 1297 // Note: the last argument is false here because these are 1298 // non-top-level regions. 1299 if (const MemRegion *R = (*I).getAsRegion()) 1300 W.AddToWorkList(R); 1301 } 1302 continue; 1303 } 1304 1305 if (const MemRegion *R = V.getAsRegion()) { 1306 if (TopLevelRegions) 1307 TopLevelRegions->push_back(R); 1308 W.AddToWorkList(R); 1309 continue; 1310 } 1311 } 1312 } 1313 1314 StoreRef 1315 RegionStoreManager::invalidateRegions(Store store, 1316 ArrayRef<SVal> Values, 1317 const Expr *Ex, unsigned Count, 1318 const LocationContext *LCtx, 1319 const CallEvent *Call, 1320 InvalidatedSymbols &IS, 1321 RegionAndSymbolInvalidationTraits &ITraits, 1322 InvalidatedRegions *TopLevelRegions, 1323 InvalidatedRegions *Invalidated) { 1324 GlobalsFilterKind GlobalsFilter; 1325 if (Call) { 1326 if (Call->isInSystemHeader()) 1327 GlobalsFilter = GFK_SystemOnly; 1328 else 1329 GlobalsFilter = GFK_All; 1330 } else { 1331 GlobalsFilter = GFK_None; 1332 } 1333 1334 RegionBindingsRef B = getRegionBindings(store); 1335 InvalidateRegionsWorker W(*this, StateMgr, B, Ex, Count, LCtx, IS, ITraits, 1336 Invalidated, GlobalsFilter); 1337 1338 // Scan the bindings and generate the clusters. 1339 W.GenerateClusters(); 1340 1341 // Add the regions to the worklist. 1342 populateWorkList(W, Values, TopLevelRegions); 1343 1344 W.RunWorkList(); 1345 1346 // Return the new bindings. 1347 B = W.getRegionBindings(); 1348 1349 // For calls, determine which global regions should be invalidated and 1350 // invalidate them. (Note that function-static and immutable globals are never 1351 // invalidated by this.) 1352 // TODO: This could possibly be more precise with modules. 1353 switch (GlobalsFilter) { 1354 case GFK_All: 1355 B = invalidateGlobalRegion(MemRegion::GlobalInternalSpaceRegionKind, 1356 Ex, Count, LCtx, B, Invalidated); 1357 LLVM_FALLTHROUGH; 1358 case GFK_SystemOnly: 1359 B = invalidateGlobalRegion(MemRegion::GlobalSystemSpaceRegionKind, 1360 Ex, Count, LCtx, B, Invalidated); 1361 LLVM_FALLTHROUGH; 1362 case GFK_None: 1363 break; 1364 } 1365 1366 return StoreRef(B.asStore(), *this); 1367 } 1368 1369 //===----------------------------------------------------------------------===// 1370 // Location and region casting. 1371 //===----------------------------------------------------------------------===// 1372 1373 /// ArrayToPointer - Emulates the "decay" of an array to a pointer 1374 /// type. 'Array' represents the lvalue of the array being decayed 1375 /// to a pointer, and the returned SVal represents the decayed 1376 /// version of that lvalue (i.e., a pointer to the first element of 1377 /// the array). This is called by ExprEngine when evaluating casts 1378 /// from arrays to pointers. 1379 SVal RegionStoreManager::ArrayToPointer(Loc Array, QualType T) { 1380 if (isa<loc::ConcreteInt>(Array)) 1381 return Array; 1382 1383 if (!isa<loc::MemRegionVal>(Array)) 1384 return UnknownVal(); 1385 1386 const SubRegion *R = 1387 cast<SubRegion>(Array.castAs<loc::MemRegionVal>().getRegion()); 1388 NonLoc ZeroIdx = svalBuilder.makeZeroArrayIndex(); 1389 return loc::MemRegionVal(MRMgr.getElementRegion(T, ZeroIdx, R, Ctx)); 1390 } 1391 1392 //===----------------------------------------------------------------------===// 1393 // Loading values from regions. 1394 //===----------------------------------------------------------------------===// 1395 1396 SVal RegionStoreManager::getBinding(RegionBindingsConstRef B, Loc L, QualType T) { 1397 assert(!isa<UnknownVal>(L) && "location unknown"); 1398 assert(!isa<UndefinedVal>(L) && "location undefined"); 1399 1400 // For access to concrete addresses, return UnknownVal. Checks 1401 // for null dereferences (and similar errors) are done by checkers, not 1402 // the Store. 1403 // FIXME: We can consider lazily symbolicating such memory, but we really 1404 // should defer this when we can reason easily about symbolicating arrays 1405 // of bytes. 1406 if (L.getAs<loc::ConcreteInt>()) { 1407 return UnknownVal(); 1408 } 1409 if (!L.getAs<loc::MemRegionVal>()) { 1410 return UnknownVal(); 1411 } 1412 1413 const MemRegion *MR = L.castAs<loc::MemRegionVal>().getRegion(); 1414 1415 if (isa<BlockDataRegion>(MR)) { 1416 return UnknownVal(); 1417 } 1418 1419 if (!isa<TypedValueRegion>(MR)) { 1420 if (T.isNull()) { 1421 if (const TypedRegion *TR = dyn_cast<TypedRegion>(MR)) 1422 T = TR->getLocationType()->getPointeeType(); 1423 else if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR)) 1424 T = SR->getSymbol()->getType()->getPointeeType(); 1425 } 1426 assert(!T.isNull() && "Unable to auto-detect binding type!"); 1427 assert(!T->isVoidType() && "Attempting to dereference a void pointer!"); 1428 MR = GetElementZeroRegion(cast<SubRegion>(MR), T); 1429 } else { 1430 T = cast<TypedValueRegion>(MR)->getValueType(); 1431 } 1432 1433 // FIXME: Perhaps this method should just take a 'const MemRegion*' argument 1434 // instead of 'Loc', and have the other Loc cases handled at a higher level. 1435 const TypedValueRegion *R = cast<TypedValueRegion>(MR); 1436 QualType RTy = R->getValueType(); 1437 1438 // FIXME: we do not yet model the parts of a complex type, so treat the 1439 // whole thing as "unknown". 1440 if (RTy->isAnyComplexType()) 1441 return UnknownVal(); 1442 1443 // FIXME: We should eventually handle funny addressing. e.g.: 1444 // 1445 // int x = ...; 1446 // int *p = &x; 1447 // char *q = (char*) p; 1448 // char c = *q; // returns the first byte of 'x'. 1449 // 1450 // Such funny addressing will occur due to layering of regions. 1451 if (RTy->isStructureOrClassType()) 1452 return getBindingForStruct(B, R); 1453 1454 // FIXME: Handle unions. 1455 if (RTy->isUnionType()) 1456 return createLazyBinding(B, R); 1457 1458 if (RTy->isArrayType()) { 1459 if (RTy->isConstantArrayType()) 1460 return getBindingForArray(B, R); 1461 else 1462 return UnknownVal(); 1463 } 1464 1465 // FIXME: handle Vector types. 1466 if (RTy->isVectorType()) 1467 return UnknownVal(); 1468 1469 if (const FieldRegion* FR = dyn_cast<FieldRegion>(R)) 1470 return svalBuilder.evalCast(getBindingForField(B, FR), T, QualType{}); 1471 1472 if (const ElementRegion* ER = dyn_cast<ElementRegion>(R)) { 1473 // FIXME: Here we actually perform an implicit conversion from the loaded 1474 // value to the element type. Eventually we want to compose these values 1475 // more intelligently. For example, an 'element' can encompass multiple 1476 // bound regions (e.g., several bound bytes), or could be a subset of 1477 // a larger value. 1478 return svalBuilder.evalCast(getBindingForElement(B, ER), T, QualType{}); 1479 } 1480 1481 if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) { 1482 // FIXME: Here we actually perform an implicit conversion from the loaded 1483 // value to the ivar type. What we should model is stores to ivars 1484 // that blow past the extent of the ivar. If the address of the ivar is 1485 // reinterpretted, it is possible we stored a different value that could 1486 // fit within the ivar. Either we need to cast these when storing them 1487 // or reinterpret them lazily (as we do here). 1488 return svalBuilder.evalCast(getBindingForObjCIvar(B, IVR), T, QualType{}); 1489 } 1490 1491 if (const VarRegion *VR = dyn_cast<VarRegion>(R)) { 1492 // FIXME: Here we actually perform an implicit conversion from the loaded 1493 // value to the variable type. What we should model is stores to variables 1494 // that blow past the extent of the variable. If the address of the 1495 // variable is reinterpretted, it is possible we stored a different value 1496 // that could fit within the variable. Either we need to cast these when 1497 // storing them or reinterpret them lazily (as we do here). 1498 return svalBuilder.evalCast(getBindingForVar(B, VR), T, QualType{}); 1499 } 1500 1501 const SVal *V = B.lookup(R, BindingKey::Direct); 1502 1503 // Check if the region has a binding. 1504 if (V) 1505 return *V; 1506 1507 // The location does not have a bound value. This means that it has 1508 // the value it had upon its creation and/or entry to the analyzed 1509 // function/method. These are either symbolic values or 'undefined'. 1510 if (R->hasStackNonParametersStorage()) { 1511 // All stack variables are considered to have undefined values 1512 // upon creation. All heap allocated blocks are considered to 1513 // have undefined values as well unless they are explicitly bound 1514 // to specific values. 1515 return UndefinedVal(); 1516 } 1517 1518 // All other values are symbolic. 1519 return svalBuilder.getRegionValueSymbolVal(R); 1520 } 1521 1522 static QualType getUnderlyingType(const SubRegion *R) { 1523 QualType RegionTy; 1524 if (const TypedValueRegion *TVR = dyn_cast<TypedValueRegion>(R)) 1525 RegionTy = TVR->getValueType(); 1526 1527 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) 1528 RegionTy = SR->getSymbol()->getType(); 1529 1530 return RegionTy; 1531 } 1532 1533 /// Checks to see if store \p B has a lazy binding for region \p R. 1534 /// 1535 /// If \p AllowSubregionBindings is \c false, a lazy binding will be rejected 1536 /// if there are additional bindings within \p R. 1537 /// 1538 /// Note that unlike RegionStoreManager::findLazyBinding, this will not search 1539 /// for lazy bindings for super-regions of \p R. 1540 static Optional<nonloc::LazyCompoundVal> 1541 getExistingLazyBinding(SValBuilder &SVB, RegionBindingsConstRef B, 1542 const SubRegion *R, bool AllowSubregionBindings) { 1543 Optional<SVal> V = B.getDefaultBinding(R); 1544 if (!V) 1545 return None; 1546 1547 Optional<nonloc::LazyCompoundVal> LCV = V->getAs<nonloc::LazyCompoundVal>(); 1548 if (!LCV) 1549 return None; 1550 1551 // If the LCV is for a subregion, the types might not match, and we shouldn't 1552 // reuse the binding. 1553 QualType RegionTy = getUnderlyingType(R); 1554 if (!RegionTy.isNull() && 1555 !RegionTy->isVoidPointerType()) { 1556 QualType SourceRegionTy = LCV->getRegion()->getValueType(); 1557 if (!SVB.getContext().hasSameUnqualifiedType(RegionTy, SourceRegionTy)) 1558 return None; 1559 } 1560 1561 if (!AllowSubregionBindings) { 1562 // If there are any other bindings within this region, we shouldn't reuse 1563 // the top-level binding. 1564 SmallVector<BindingPair, 16> Bindings; 1565 collectSubRegionBindings(Bindings, SVB, *B.lookup(R->getBaseRegion()), R, 1566 /*IncludeAllDefaultBindings=*/true); 1567 if (Bindings.size() > 1) 1568 return None; 1569 } 1570 1571 return *LCV; 1572 } 1573 1574 1575 std::pair<Store, const SubRegion *> 1576 RegionStoreManager::findLazyBinding(RegionBindingsConstRef B, 1577 const SubRegion *R, 1578 const SubRegion *originalRegion) { 1579 if (originalRegion != R) { 1580 if (Optional<nonloc::LazyCompoundVal> V = 1581 getExistingLazyBinding(svalBuilder, B, R, true)) 1582 return std::make_pair(V->getStore(), V->getRegion()); 1583 } 1584 1585 typedef std::pair<Store, const SubRegion *> StoreRegionPair; 1586 StoreRegionPair Result = StoreRegionPair(); 1587 1588 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) { 1589 Result = findLazyBinding(B, cast<SubRegion>(ER->getSuperRegion()), 1590 originalRegion); 1591 1592 if (Result.second) 1593 Result.second = MRMgr.getElementRegionWithSuper(ER, Result.second); 1594 1595 } else if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) { 1596 Result = findLazyBinding(B, cast<SubRegion>(FR->getSuperRegion()), 1597 originalRegion); 1598 1599 if (Result.second) 1600 Result.second = MRMgr.getFieldRegionWithSuper(FR, Result.second); 1601 1602 } else if (const CXXBaseObjectRegion *BaseReg = 1603 dyn_cast<CXXBaseObjectRegion>(R)) { 1604 // C++ base object region is another kind of region that we should blast 1605 // through to look for lazy compound value. It is like a field region. 1606 Result = findLazyBinding(B, cast<SubRegion>(BaseReg->getSuperRegion()), 1607 originalRegion); 1608 1609 if (Result.second) 1610 Result.second = MRMgr.getCXXBaseObjectRegionWithSuper(BaseReg, 1611 Result.second); 1612 } 1613 1614 return Result; 1615 } 1616 1617 /// This is a helper function for `getConstantValFromConstArrayInitializer`. 1618 /// 1619 /// Return an array of extents of the declared array type. 1620 /// 1621 /// E.g. for `int x[1][2][3];` returns { 1, 2, 3 }. 1622 static SmallVector<uint64_t, 2> 1623 getConstantArrayExtents(const ConstantArrayType *CAT) { 1624 assert(CAT && "ConstantArrayType should not be null"); 1625 CAT = cast<ConstantArrayType>(CAT->getCanonicalTypeInternal()); 1626 SmallVector<uint64_t, 2> Extents; 1627 do { 1628 Extents.push_back(CAT->getSize().getZExtValue()); 1629 } while ((CAT = dyn_cast<ConstantArrayType>(CAT->getElementType()))); 1630 return Extents; 1631 } 1632 1633 /// This is a helper function for `getConstantValFromConstArrayInitializer`. 1634 /// 1635 /// Return an array of offsets from nested ElementRegions and a root base 1636 /// region. The array is never empty and a base region is never null. 1637 /// 1638 /// E.g. for `Element{Element{Element{VarRegion},1},2},3}` returns { 3, 2, 1 }. 1639 /// This represents an access through indirection: `arr[1][2][3];` 1640 /// 1641 /// \param ER The given (possibly nested) ElementRegion. 1642 /// 1643 /// \note The result array is in the reverse order of indirection expression: 1644 /// arr[1][2][3] -> { 3, 2, 1 }. This helps to provide complexity O(n), where n 1645 /// is a number of indirections. It may not affect performance in real-life 1646 /// code, though. 1647 static std::pair<SmallVector<SVal, 2>, const MemRegion *> 1648 getElementRegionOffsetsWithBase(const ElementRegion *ER) { 1649 assert(ER && "ConstantArrayType should not be null"); 1650 const MemRegion *Base; 1651 SmallVector<SVal, 2> SValOffsets; 1652 do { 1653 SValOffsets.push_back(ER->getIndex()); 1654 Base = ER->getSuperRegion(); 1655 ER = dyn_cast<ElementRegion>(Base); 1656 } while (ER); 1657 return {SValOffsets, Base}; 1658 } 1659 1660 /// This is a helper function for `getConstantValFromConstArrayInitializer`. 1661 /// 1662 /// Convert array of offsets from `SVal` to `uint64_t` in consideration of 1663 /// respective array extents. 1664 /// \param SrcOffsets [in] The array of offsets of type `SVal` in reversed 1665 /// order (expectedly received from `getElementRegionOffsetsWithBase`). 1666 /// \param ArrayExtents [in] The array of extents. 1667 /// \param DstOffsets [out] The array of offsets of type `uint64_t`. 1668 /// \returns: 1669 /// - `None` for successful convertion. 1670 /// - `UndefinedVal` or `UnknownVal` otherwise. It's expected that this SVal 1671 /// will be returned as a suitable value of the access operation. 1672 /// which should be returned as a correct 1673 /// 1674 /// \example: 1675 /// const int arr[10][20][30] = {}; // ArrayExtents { 10, 20, 30 } 1676 /// int x1 = arr[4][5][6]; // SrcOffsets { NonLoc(6), NonLoc(5), NonLoc(4) } 1677 /// // DstOffsets { 4, 5, 6 } 1678 /// // returns None 1679 /// int x2 = arr[42][5][-6]; // returns UndefinedVal 1680 /// int x3 = arr[4][5][x2]; // returns UnknownVal 1681 static Optional<SVal> 1682 convertOffsetsFromSvalToUnsigneds(const SmallVector<SVal, 2> &SrcOffsets, 1683 const SmallVector<uint64_t, 2> ArrayExtents, 1684 SmallVector<uint64_t, 2> &DstOffsets) { 1685 // Check offsets for being out of bounds. 1686 // C++20 [expr.add] 7.6.6.4 (excerpt): 1687 // If P points to an array element i of an array object x with n 1688 // elements, where i < 0 or i > n, the behavior is undefined. 1689 // Dereferencing is not allowed on the "one past the last 1690 // element", when i == n. 1691 // Example: 1692 // const int arr[3][2] = {{1, 2}, {3, 4}}; 1693 // arr[0][0]; // 1 1694 // arr[0][1]; // 2 1695 // arr[0][2]; // UB 1696 // arr[1][0]; // 3 1697 // arr[1][1]; // 4 1698 // arr[1][-1]; // UB 1699 // arr[2][0]; // 0 1700 // arr[2][1]; // 0 1701 // arr[-2][0]; // UB 1702 DstOffsets.resize(SrcOffsets.size()); 1703 auto ExtentIt = ArrayExtents.begin(); 1704 auto OffsetIt = DstOffsets.begin(); 1705 // Reverse `SValOffsets` to make it consistent with `ArrayExtents`. 1706 for (SVal V : llvm::reverse(SrcOffsets)) { 1707 if (auto CI = V.getAs<nonloc::ConcreteInt>()) { 1708 // When offset is out of array's bounds, result is UB. 1709 const llvm::APSInt &Offset = CI->getValue(); 1710 if (Offset.isNegative() || Offset.uge(*(ExtentIt++))) 1711 return UndefinedVal(); 1712 // Store index in a reversive order. 1713 *(OffsetIt++) = Offset.getZExtValue(); 1714 continue; 1715 } 1716 // Symbolic index presented. Return Unknown value. 1717 // FIXME: We also need to take ElementRegions with symbolic indexes into 1718 // account. 1719 return UnknownVal(); 1720 } 1721 return None; 1722 } 1723 1724 Optional<SVal> RegionStoreManager::getConstantValFromConstArrayInitializer( 1725 RegionBindingsConstRef B, const ElementRegion *R) { 1726 assert(R && "ElementRegion should not be null"); 1727 1728 // Treat an n-dimensional array. 1729 SmallVector<SVal, 2> SValOffsets; 1730 const MemRegion *Base; 1731 std::tie(SValOffsets, Base) = getElementRegionOffsetsWithBase(R); 1732 const VarRegion *VR = dyn_cast<VarRegion>(Base); 1733 if (!VR) 1734 return None; 1735 1736 assert(!SValOffsets.empty() && "getElementRegionOffsets guarantees the " 1737 "offsets vector is not empty."); 1738 1739 // Check if the containing array has an initialized value that we can trust. 1740 // We can trust a const value or a value of a global initializer in main(). 1741 const VarDecl *VD = VR->getDecl(); 1742 if (!VD->getType().isConstQualified() && 1743 !R->getElementType().isConstQualified() && 1744 (!B.isMainAnalysis() || !VD->hasGlobalStorage())) 1745 return None; 1746 1747 // Array's declaration should have `ConstantArrayType` type, because only this 1748 // type contains an array extent. It may happen that array type can be of 1749 // `IncompleteArrayType` type. To get the declaration of `ConstantArrayType` 1750 // type, we should find the declaration in the redeclarations chain that has 1751 // the initialization expression. 1752 // NOTE: `getAnyInitializer` has an out-parameter, which returns a new `VD` 1753 // from which an initializer is obtained. We replace current `VD` with the new 1754 // `VD`. If the return value of the function is null than `VD` won't be 1755 // replaced. 1756 const Expr *Init = VD->getAnyInitializer(VD); 1757 // NOTE: If `Init` is non-null, then a new `VD` is non-null for sure. So check 1758 // `Init` for null only and don't worry about the replaced `VD`. 1759 if (!Init) 1760 return None; 1761 1762 // Array's declaration should have ConstantArrayType type, because only this 1763 // type contains an array extent. 1764 const ConstantArrayType *CAT = Ctx.getAsConstantArrayType(VD->getType()); 1765 if (!CAT) 1766 return None; 1767 1768 // Get array extents. 1769 SmallVector<uint64_t, 2> Extents = getConstantArrayExtents(CAT); 1770 1771 // The number of offsets should equal to the numbers of extents, 1772 // otherwise wrong type punning occurred. For instance: 1773 // int arr[1][2][3]; 1774 // auto ptr = (int(*)[42])arr; 1775 // auto x = ptr[4][2]; // UB 1776 // FIXME: Should return UndefinedVal. 1777 if (SValOffsets.size() != Extents.size()) 1778 return None; 1779 1780 SmallVector<uint64_t, 2> ConcreteOffsets; 1781 if (Optional<SVal> V = convertOffsetsFromSvalToUnsigneds(SValOffsets, Extents, 1782 ConcreteOffsets)) 1783 return *V; 1784 1785 // Handle InitListExpr. 1786 // Example: 1787 // const char arr[4][2] = { { 1, 2 }, { 3 }, 4, 5 }; 1788 if (const auto *ILE = dyn_cast<InitListExpr>(Init)) 1789 return getSValFromInitListExpr(ILE, ConcreteOffsets, R->getElementType()); 1790 1791 // Handle StringLiteral. 1792 // Example: 1793 // const char arr[] = "abc"; 1794 if (const auto *SL = dyn_cast<StringLiteral>(Init)) 1795 return getSValFromStringLiteral(SL, ConcreteOffsets.front(), 1796 R->getElementType()); 1797 1798 // FIXME: Handle CompoundLiteralExpr. 1799 1800 return None; 1801 } 1802 1803 /// Returns an SVal, if possible, for the specified position of an 1804 /// initialization list. 1805 /// 1806 /// \param ILE The given initialization list. 1807 /// \param Offsets The array of unsigned offsets. E.g. for the expression 1808 /// `int x = arr[1][2][3];` an array should be { 1, 2, 3 }. 1809 /// \param ElemT The type of the result SVal expression. 1810 /// \return Optional SVal for the particular position in the initialization 1811 /// list. E.g. for the list `{{1, 2},[3, 4],{5, 6}, {}}` offsets: 1812 /// - {1, 1} returns SVal{4}, because it's the second position in the second 1813 /// sublist; 1814 /// - {3, 0} returns SVal{0}, because there's no explicit value at this 1815 /// position in the sublist. 1816 /// 1817 /// NOTE: Inorder to get a valid SVal, a caller shall guarantee valid offsets 1818 /// for the given initialization list. Otherwise SVal can be an equivalent to 0 1819 /// or lead to assertion. 1820 Optional<SVal> RegionStoreManager::getSValFromInitListExpr( 1821 const InitListExpr *ILE, const SmallVector<uint64_t, 2> &Offsets, 1822 QualType ElemT) { 1823 assert(ILE && "InitListExpr should not be null"); 1824 1825 for (uint64_t Offset : Offsets) { 1826 // C++20 [dcl.init.string] 9.4.2.1: 1827 // An array of ordinary character type [...] can be initialized by [...] 1828 // an appropriately-typed string-literal enclosed in braces. 1829 // Example: 1830 // const char arr[] = { "abc" }; 1831 if (ILE->isStringLiteralInit()) 1832 if (const auto *SL = dyn_cast<StringLiteral>(ILE->getInit(0))) 1833 return getSValFromStringLiteral(SL, Offset, ElemT); 1834 1835 // C++20 [expr.add] 9.4.17.5 (excerpt): 1836 // i-th array element is value-initialized for each k < i ≤ n, 1837 // where k is an expression-list size and n is an array extent. 1838 if (Offset >= ILE->getNumInits()) 1839 return svalBuilder.makeZeroVal(ElemT); 1840 1841 const Expr *E = ILE->getInit(Offset); 1842 const auto *IL = dyn_cast<InitListExpr>(E); 1843 if (!IL) 1844 // Return a constant value, if it is presented. 1845 // FIXME: Support other SVals. 1846 return svalBuilder.getConstantVal(E); 1847 1848 // Go to the nested initializer list. 1849 ILE = IL; 1850 } 1851 llvm_unreachable( 1852 "Unhandled InitListExpr sub-expressions or invalid offsets."); 1853 } 1854 1855 /// Returns an SVal, if possible, for the specified position in a string 1856 /// literal. 1857 /// 1858 /// \param SL The given string literal. 1859 /// \param Offset The unsigned offset. E.g. for the expression 1860 /// `char x = str[42];` an offset should be 42. 1861 /// E.g. for the string "abc" offset: 1862 /// - 1 returns SVal{b}, because it's the second position in the string. 1863 /// - 42 returns SVal{0}, because there's no explicit value at this 1864 /// position in the string. 1865 /// \param ElemT The type of the result SVal expression. 1866 /// 1867 /// NOTE: We return `0` for every offset >= the literal length for array 1868 /// declarations, like: 1869 /// const char str[42] = "123"; // Literal length is 4. 1870 /// char c = str[41]; // Offset is 41. 1871 /// FIXME: Nevertheless, we can't do the same for pointer declaraions, like: 1872 /// const char * const str = "123"; // Literal length is 4. 1873 /// char c = str[41]; // Offset is 41. Returns `0`, but Undef 1874 /// // expected. 1875 /// It should be properly handled before reaching this point. 1876 /// The main problem is that we can't distinguish between these declarations, 1877 /// because in case of array we can get the Decl from VarRegion, but in case 1878 /// of pointer the region is a StringRegion, which doesn't contain a Decl. 1879 /// Possible solution could be passing an array extent along with the offset. 1880 SVal RegionStoreManager::getSValFromStringLiteral(const StringLiteral *SL, 1881 uint64_t Offset, 1882 QualType ElemT) { 1883 assert(SL && "StringLiteral should not be null"); 1884 // C++20 [dcl.init.string] 9.4.2.3: 1885 // If there are fewer initializers than there are array elements, each 1886 // element not explicitly initialized shall be zero-initialized [dcl.init]. 1887 uint32_t Code = (Offset >= SL->getLength()) ? 0 : SL->getCodeUnit(Offset); 1888 return svalBuilder.makeIntVal(Code, ElemT); 1889 } 1890 1891 static Optional<SVal> getDerivedSymbolForBinding( 1892 RegionBindingsConstRef B, const TypedValueRegion *BaseRegion, 1893 const TypedValueRegion *SubReg, const ASTContext &Ctx, SValBuilder &SVB) { 1894 assert(BaseRegion); 1895 QualType BaseTy = BaseRegion->getValueType(); 1896 QualType Ty = SubReg->getValueType(); 1897 if (BaseTy->isScalarType() && Ty->isScalarType()) { 1898 if (Ctx.getTypeSizeInChars(BaseTy) >= Ctx.getTypeSizeInChars(Ty)) { 1899 if (const Optional<SVal> &ParentValue = B.getDirectBinding(BaseRegion)) { 1900 if (SymbolRef ParentValueAsSym = ParentValue->getAsSymbol()) 1901 return SVB.getDerivedRegionValueSymbolVal(ParentValueAsSym, SubReg); 1902 1903 if (ParentValue->isUndef()) 1904 return UndefinedVal(); 1905 1906 // Other cases: give up. We are indexing into a larger object 1907 // that has some value, but we don't know how to handle that yet. 1908 return UnknownVal(); 1909 } 1910 } 1911 } 1912 return None; 1913 } 1914 1915 SVal RegionStoreManager::getBindingForElement(RegionBindingsConstRef B, 1916 const ElementRegion* R) { 1917 // Check if the region has a binding. 1918 if (const Optional<SVal> &V = B.getDirectBinding(R)) 1919 return *V; 1920 1921 const MemRegion* superR = R->getSuperRegion(); 1922 1923 // Check if the region is an element region of a string literal. 1924 if (const StringRegion *StrR = dyn_cast<StringRegion>(superR)) { 1925 // FIXME: Handle loads from strings where the literal is treated as 1926 // an integer, e.g., *((unsigned int*)"hello"). Such loads are UB according 1927 // to C++20 7.2.1.11 [basic.lval]. 1928 QualType T = Ctx.getAsArrayType(StrR->getValueType())->getElementType(); 1929 if (!Ctx.hasSameUnqualifiedType(T, R->getElementType())) 1930 return UnknownVal(); 1931 if (const auto CI = R->getIndex().getAs<nonloc::ConcreteInt>()) { 1932 const llvm::APSInt &Idx = CI->getValue(); 1933 if (Idx < 0) 1934 return UndefinedVal(); 1935 const StringLiteral *SL = StrR->getStringLiteral(); 1936 return getSValFromStringLiteral(SL, Idx.getZExtValue(), T); 1937 } 1938 } else if (isa<ElementRegion, VarRegion>(superR)) { 1939 if (Optional<SVal> V = getConstantValFromConstArrayInitializer(B, R)) 1940 return *V; 1941 } 1942 1943 // Check for loads from a code text region. For such loads, just give up. 1944 if (isa<CodeTextRegion>(superR)) 1945 return UnknownVal(); 1946 1947 // Handle the case where we are indexing into a larger scalar object. 1948 // For example, this handles: 1949 // int x = ... 1950 // char *y = &x; 1951 // return *y; 1952 // FIXME: This is a hack, and doesn't do anything really intelligent yet. 1953 const RegionRawOffset &O = R->getAsArrayOffset(); 1954 1955 // If we cannot reason about the offset, return an unknown value. 1956 if (!O.getRegion()) 1957 return UnknownVal(); 1958 1959 if (const TypedValueRegion *baseR = dyn_cast<TypedValueRegion>(O.getRegion())) 1960 if (auto V = getDerivedSymbolForBinding(B, baseR, R, Ctx, svalBuilder)) 1961 return *V; 1962 1963 return getBindingForFieldOrElementCommon(B, R, R->getElementType()); 1964 } 1965 1966 SVal RegionStoreManager::getBindingForField(RegionBindingsConstRef B, 1967 const FieldRegion* R) { 1968 1969 // Check if the region has a binding. 1970 if (const Optional<SVal> &V = B.getDirectBinding(R)) 1971 return *V; 1972 1973 // If the containing record was initialized, try to get its constant value. 1974 const FieldDecl *FD = R->getDecl(); 1975 QualType Ty = FD->getType(); 1976 const MemRegion* superR = R->getSuperRegion(); 1977 if (const auto *VR = dyn_cast<VarRegion>(superR)) { 1978 const VarDecl *VD = VR->getDecl(); 1979 QualType RecordVarTy = VD->getType(); 1980 unsigned Index = FD->getFieldIndex(); 1981 // Either the record variable or the field has an initializer that we can 1982 // trust. We trust initializers of constants and, additionally, respect 1983 // initializers of globals when analyzing main(). 1984 if (RecordVarTy.isConstQualified() || Ty.isConstQualified() || 1985 (B.isMainAnalysis() && VD->hasGlobalStorage())) 1986 if (const Expr *Init = VD->getAnyInitializer()) 1987 if (const auto *InitList = dyn_cast<InitListExpr>(Init)) { 1988 if (Index < InitList->getNumInits()) { 1989 if (const Expr *FieldInit = InitList->getInit(Index)) 1990 if (Optional<SVal> V = svalBuilder.getConstantVal(FieldInit)) 1991 return *V; 1992 } else { 1993 return svalBuilder.makeZeroVal(Ty); 1994 } 1995 } 1996 } 1997 1998 // Handle the case where we are accessing into a larger scalar object. 1999 // For example, this handles: 2000 // struct header { 2001 // unsigned a : 1; 2002 // unsigned b : 1; 2003 // }; 2004 // struct parse_t { 2005 // unsigned bits0 : 1; 2006 // unsigned bits2 : 2; // <-- header 2007 // unsigned bits4 : 4; 2008 // }; 2009 // int parse(parse_t *p) { 2010 // unsigned copy = p->bits2; 2011 // header *bits = (header *)© 2012 // return bits->b; <-- here 2013 // } 2014 if (const auto *Base = dyn_cast<TypedValueRegion>(R->getBaseRegion())) 2015 if (auto V = getDerivedSymbolForBinding(B, Base, R, Ctx, svalBuilder)) 2016 return *V; 2017 2018 return getBindingForFieldOrElementCommon(B, R, Ty); 2019 } 2020 2021 Optional<SVal> 2022 RegionStoreManager::getBindingForDerivedDefaultValue(RegionBindingsConstRef B, 2023 const MemRegion *superR, 2024 const TypedValueRegion *R, 2025 QualType Ty) { 2026 2027 if (const Optional<SVal> &D = B.getDefaultBinding(superR)) { 2028 const SVal &val = *D; 2029 if (SymbolRef parentSym = val.getAsSymbol()) 2030 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); 2031 2032 if (val.isZeroConstant()) 2033 return svalBuilder.makeZeroVal(Ty); 2034 2035 if (val.isUnknownOrUndef()) 2036 return val; 2037 2038 // Lazy bindings are usually handled through getExistingLazyBinding(). 2039 // We should unify these two code paths at some point. 2040 if (isa<nonloc::LazyCompoundVal, nonloc::CompoundVal>(val)) 2041 return val; 2042 2043 llvm_unreachable("Unknown default value"); 2044 } 2045 2046 return None; 2047 } 2048 2049 SVal RegionStoreManager::getLazyBinding(const SubRegion *LazyBindingRegion, 2050 RegionBindingsRef LazyBinding) { 2051 SVal Result; 2052 if (const ElementRegion *ER = dyn_cast<ElementRegion>(LazyBindingRegion)) 2053 Result = getBindingForElement(LazyBinding, ER); 2054 else 2055 Result = getBindingForField(LazyBinding, 2056 cast<FieldRegion>(LazyBindingRegion)); 2057 2058 // FIXME: This is a hack to deal with RegionStore's inability to distinguish a 2059 // default value for /part/ of an aggregate from a default value for the 2060 // /entire/ aggregate. The most common case of this is when struct Outer 2061 // has as its first member a struct Inner, which is copied in from a stack 2062 // variable. In this case, even if the Outer's default value is symbolic, 0, 2063 // or unknown, it gets overridden by the Inner's default value of undefined. 2064 // 2065 // This is a general problem -- if the Inner is zero-initialized, the Outer 2066 // will now look zero-initialized. The proper way to solve this is with a 2067 // new version of RegionStore that tracks the extent of a binding as well 2068 // as the offset. 2069 // 2070 // This hack only takes care of the undefined case because that can very 2071 // quickly result in a warning. 2072 if (Result.isUndef()) 2073 Result = UnknownVal(); 2074 2075 return Result; 2076 } 2077 2078 SVal 2079 RegionStoreManager::getBindingForFieldOrElementCommon(RegionBindingsConstRef B, 2080 const TypedValueRegion *R, 2081 QualType Ty) { 2082 2083 // At this point we have already checked in either getBindingForElement or 2084 // getBindingForField if 'R' has a direct binding. 2085 2086 // Lazy binding? 2087 Store lazyBindingStore = nullptr; 2088 const SubRegion *lazyBindingRegion = nullptr; 2089 std::tie(lazyBindingStore, lazyBindingRegion) = findLazyBinding(B, R, R); 2090 if (lazyBindingRegion) 2091 return getLazyBinding(lazyBindingRegion, 2092 getRegionBindings(lazyBindingStore)); 2093 2094 // Record whether or not we see a symbolic index. That can completely 2095 // be out of scope of our lookup. 2096 bool hasSymbolicIndex = false; 2097 2098 // FIXME: This is a hack to deal with RegionStore's inability to distinguish a 2099 // default value for /part/ of an aggregate from a default value for the 2100 // /entire/ aggregate. The most common case of this is when struct Outer 2101 // has as its first member a struct Inner, which is copied in from a stack 2102 // variable. In this case, even if the Outer's default value is symbolic, 0, 2103 // or unknown, it gets overridden by the Inner's default value of undefined. 2104 // 2105 // This is a general problem -- if the Inner is zero-initialized, the Outer 2106 // will now look zero-initialized. The proper way to solve this is with a 2107 // new version of RegionStore that tracks the extent of a binding as well 2108 // as the offset. 2109 // 2110 // This hack only takes care of the undefined case because that can very 2111 // quickly result in a warning. 2112 bool hasPartialLazyBinding = false; 2113 2114 const SubRegion *SR = R; 2115 while (SR) { 2116 const MemRegion *Base = SR->getSuperRegion(); 2117 if (Optional<SVal> D = getBindingForDerivedDefaultValue(B, Base, R, Ty)) { 2118 if (D->getAs<nonloc::LazyCompoundVal>()) { 2119 hasPartialLazyBinding = true; 2120 break; 2121 } 2122 2123 return *D; 2124 } 2125 2126 if (const ElementRegion *ER = dyn_cast<ElementRegion>(Base)) { 2127 NonLoc index = ER->getIndex(); 2128 if (!index.isConstant()) 2129 hasSymbolicIndex = true; 2130 } 2131 2132 // If our super region is a field or element itself, walk up the region 2133 // hierarchy to see if there is a default value installed in an ancestor. 2134 SR = dyn_cast<SubRegion>(Base); 2135 } 2136 2137 if (R->hasStackNonParametersStorage()) { 2138 if (isa<ElementRegion>(R)) { 2139 // Currently we don't reason specially about Clang-style vectors. Check 2140 // if superR is a vector and if so return Unknown. 2141 if (const TypedValueRegion *typedSuperR = 2142 dyn_cast<TypedValueRegion>(R->getSuperRegion())) { 2143 if (typedSuperR->getValueType()->isVectorType()) 2144 return UnknownVal(); 2145 } 2146 } 2147 2148 // FIXME: We also need to take ElementRegions with symbolic indexes into 2149 // account. This case handles both directly accessing an ElementRegion 2150 // with a symbolic offset, but also fields within an element with 2151 // a symbolic offset. 2152 if (hasSymbolicIndex) 2153 return UnknownVal(); 2154 2155 // Additionally allow introspection of a block's internal layout. 2156 // Try to get direct binding if all other attempts failed thus far. 2157 // Else, return UndefinedVal() 2158 if (!hasPartialLazyBinding && !isa<BlockDataRegion>(R->getBaseRegion())) { 2159 if (const Optional<SVal> &V = B.getDefaultBinding(R)) 2160 return *V; 2161 return UndefinedVal(); 2162 } 2163 } 2164 2165 // All other values are symbolic. 2166 return svalBuilder.getRegionValueSymbolVal(R); 2167 } 2168 2169 SVal RegionStoreManager::getBindingForObjCIvar(RegionBindingsConstRef B, 2170 const ObjCIvarRegion* R) { 2171 // Check if the region has a binding. 2172 if (const Optional<SVal> &V = B.getDirectBinding(R)) 2173 return *V; 2174 2175 const MemRegion *superR = R->getSuperRegion(); 2176 2177 // Check if the super region has a default binding. 2178 if (const Optional<SVal> &V = B.getDefaultBinding(superR)) { 2179 if (SymbolRef parentSym = V->getAsSymbol()) 2180 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); 2181 2182 // Other cases: give up. 2183 return UnknownVal(); 2184 } 2185 2186 return getBindingForLazySymbol(R); 2187 } 2188 2189 SVal RegionStoreManager::getBindingForVar(RegionBindingsConstRef B, 2190 const VarRegion *R) { 2191 2192 // Check if the region has a binding. 2193 if (Optional<SVal> V = B.getDirectBinding(R)) 2194 return *V; 2195 2196 if (Optional<SVal> V = B.getDefaultBinding(R)) 2197 return *V; 2198 2199 // Lazily derive a value for the VarRegion. 2200 const VarDecl *VD = R->getDecl(); 2201 const MemSpaceRegion *MS = R->getMemorySpace(); 2202 2203 // Arguments are always symbolic. 2204 if (isa<StackArgumentsSpaceRegion>(MS)) 2205 return svalBuilder.getRegionValueSymbolVal(R); 2206 2207 // Is 'VD' declared constant? If so, retrieve the constant value. 2208 if (VD->getType().isConstQualified()) { 2209 if (const Expr *Init = VD->getAnyInitializer()) { 2210 if (Optional<SVal> V = svalBuilder.getConstantVal(Init)) 2211 return *V; 2212 2213 // If the variable is const qualified and has an initializer but 2214 // we couldn't evaluate initializer to a value, treat the value as 2215 // unknown. 2216 return UnknownVal(); 2217 } 2218 } 2219 2220 // This must come after the check for constants because closure-captured 2221 // constant variables may appear in UnknownSpaceRegion. 2222 if (isa<UnknownSpaceRegion>(MS)) 2223 return svalBuilder.getRegionValueSymbolVal(R); 2224 2225 if (isa<GlobalsSpaceRegion>(MS)) { 2226 QualType T = VD->getType(); 2227 2228 // If we're in main(), then global initializers have not become stale yet. 2229 if (B.isMainAnalysis()) 2230 if (const Expr *Init = VD->getAnyInitializer()) 2231 if (Optional<SVal> V = svalBuilder.getConstantVal(Init)) 2232 return *V; 2233 2234 // Function-scoped static variables are default-initialized to 0; if they 2235 // have an initializer, it would have been processed by now. 2236 // FIXME: This is only true when we're starting analysis from main(). 2237 // We're losing a lot of coverage here. 2238 if (isa<StaticGlobalSpaceRegion>(MS)) 2239 return svalBuilder.makeZeroVal(T); 2240 2241 if (Optional<SVal> V = getBindingForDerivedDefaultValue(B, MS, R, T)) { 2242 assert(!V->getAs<nonloc::LazyCompoundVal>()); 2243 return *V; 2244 } 2245 2246 return svalBuilder.getRegionValueSymbolVal(R); 2247 } 2248 2249 return UndefinedVal(); 2250 } 2251 2252 SVal RegionStoreManager::getBindingForLazySymbol(const TypedValueRegion *R) { 2253 // All other values are symbolic. 2254 return svalBuilder.getRegionValueSymbolVal(R); 2255 } 2256 2257 const RegionStoreManager::SValListTy & 2258 RegionStoreManager::getInterestingValues(nonloc::LazyCompoundVal LCV) { 2259 // First, check the cache. 2260 LazyBindingsMapTy::iterator I = LazyBindingsMap.find(LCV.getCVData()); 2261 if (I != LazyBindingsMap.end()) 2262 return I->second; 2263 2264 // If we don't have a list of values cached, start constructing it. 2265 SValListTy List; 2266 2267 const SubRegion *LazyR = LCV.getRegion(); 2268 RegionBindingsRef B = getRegionBindings(LCV.getStore()); 2269 2270 // If this region had /no/ bindings at the time, there are no interesting 2271 // values to return. 2272 const ClusterBindings *Cluster = B.lookup(LazyR->getBaseRegion()); 2273 if (!Cluster) 2274 return (LazyBindingsMap[LCV.getCVData()] = std::move(List)); 2275 2276 SmallVector<BindingPair, 32> Bindings; 2277 collectSubRegionBindings(Bindings, svalBuilder, *Cluster, LazyR, 2278 /*IncludeAllDefaultBindings=*/true); 2279 for (SmallVectorImpl<BindingPair>::const_iterator I = Bindings.begin(), 2280 E = Bindings.end(); 2281 I != E; ++I) { 2282 SVal V = I->second; 2283 if (V.isUnknownOrUndef() || V.isConstant()) 2284 continue; 2285 2286 if (Optional<nonloc::LazyCompoundVal> InnerLCV = 2287 V.getAs<nonloc::LazyCompoundVal>()) { 2288 const SValListTy &InnerList = getInterestingValues(*InnerLCV); 2289 List.insert(List.end(), InnerList.begin(), InnerList.end()); 2290 continue; 2291 } 2292 2293 List.push_back(V); 2294 } 2295 2296 return (LazyBindingsMap[LCV.getCVData()] = std::move(List)); 2297 } 2298 2299 NonLoc RegionStoreManager::createLazyBinding(RegionBindingsConstRef B, 2300 const TypedValueRegion *R) { 2301 if (Optional<nonloc::LazyCompoundVal> V = 2302 getExistingLazyBinding(svalBuilder, B, R, false)) 2303 return *V; 2304 2305 return svalBuilder.makeLazyCompoundVal(StoreRef(B.asStore(), *this), R); 2306 } 2307 2308 static bool isRecordEmpty(const RecordDecl *RD) { 2309 if (!RD->field_empty()) 2310 return false; 2311 if (const CXXRecordDecl *CRD = dyn_cast<CXXRecordDecl>(RD)) 2312 return CRD->getNumBases() == 0; 2313 return true; 2314 } 2315 2316 SVal RegionStoreManager::getBindingForStruct(RegionBindingsConstRef B, 2317 const TypedValueRegion *R) { 2318 const RecordDecl *RD = R->getValueType()->castAs<RecordType>()->getDecl(); 2319 if (!RD->getDefinition() || isRecordEmpty(RD)) 2320 return UnknownVal(); 2321 2322 return createLazyBinding(B, R); 2323 } 2324 2325 SVal RegionStoreManager::getBindingForArray(RegionBindingsConstRef B, 2326 const TypedValueRegion *R) { 2327 assert(Ctx.getAsConstantArrayType(R->getValueType()) && 2328 "Only constant array types can have compound bindings."); 2329 2330 return createLazyBinding(B, R); 2331 } 2332 2333 bool RegionStoreManager::includedInBindings(Store store, 2334 const MemRegion *region) const { 2335 RegionBindingsRef B = getRegionBindings(store); 2336 region = region->getBaseRegion(); 2337 2338 // Quick path: if the base is the head of a cluster, the region is live. 2339 if (B.lookup(region)) 2340 return true; 2341 2342 // Slow path: if the region is the VALUE of any binding, it is live. 2343 for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI) { 2344 const ClusterBindings &Cluster = RI.getData(); 2345 for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); 2346 CI != CE; ++CI) { 2347 const SVal &D = CI.getData(); 2348 if (const MemRegion *R = D.getAsRegion()) 2349 if (R->getBaseRegion() == region) 2350 return true; 2351 } 2352 } 2353 2354 return false; 2355 } 2356 2357 //===----------------------------------------------------------------------===// 2358 // Binding values to regions. 2359 //===----------------------------------------------------------------------===// 2360 2361 StoreRef RegionStoreManager::killBinding(Store ST, Loc L) { 2362 if (Optional<loc::MemRegionVal> LV = L.getAs<loc::MemRegionVal>()) 2363 if (const MemRegion* R = LV->getRegion()) 2364 return StoreRef(getRegionBindings(ST).removeBinding(R) 2365 .asImmutableMap() 2366 .getRootWithoutRetain(), 2367 *this); 2368 2369 return StoreRef(ST, *this); 2370 } 2371 2372 RegionBindingsRef 2373 RegionStoreManager::bind(RegionBindingsConstRef B, Loc L, SVal V) { 2374 if (L.getAs<loc::ConcreteInt>()) 2375 return B; 2376 2377 // If we get here, the location should be a region. 2378 const MemRegion *R = L.castAs<loc::MemRegionVal>().getRegion(); 2379 2380 // Check if the region is a struct region. 2381 if (const TypedValueRegion* TR = dyn_cast<TypedValueRegion>(R)) { 2382 QualType Ty = TR->getValueType(); 2383 if (Ty->isArrayType()) 2384 return bindArray(B, TR, V); 2385 if (Ty->isStructureOrClassType()) 2386 return bindStruct(B, TR, V); 2387 if (Ty->isVectorType()) 2388 return bindVector(B, TR, V); 2389 if (Ty->isUnionType()) 2390 return bindAggregate(B, TR, V); 2391 } 2392 2393 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) { 2394 // Binding directly to a symbolic region should be treated as binding 2395 // to element 0. 2396 QualType T = SR->getSymbol()->getType(); 2397 if (T->isAnyPointerType() || T->isReferenceType()) 2398 T = T->getPointeeType(); 2399 2400 R = GetElementZeroRegion(SR, T); 2401 } 2402 2403 assert((!isa<CXXThisRegion>(R) || !B.lookup(R)) && 2404 "'this' pointer is not an l-value and is not assignable"); 2405 2406 // Clear out bindings that may overlap with this binding. 2407 RegionBindingsRef NewB = removeSubRegionBindings(B, cast<SubRegion>(R)); 2408 return NewB.addBinding(BindingKey::Make(R, BindingKey::Direct), V); 2409 } 2410 2411 RegionBindingsRef 2412 RegionStoreManager::setImplicitDefaultValue(RegionBindingsConstRef B, 2413 const MemRegion *R, 2414 QualType T) { 2415 SVal V; 2416 2417 if (Loc::isLocType(T)) 2418 V = svalBuilder.makeNullWithType(T); 2419 else if (T->isIntegralOrEnumerationType()) 2420 V = svalBuilder.makeZeroVal(T); 2421 else if (T->isStructureOrClassType() || T->isArrayType()) { 2422 // Set the default value to a zero constant when it is a structure 2423 // or array. The type doesn't really matter. 2424 V = svalBuilder.makeZeroVal(Ctx.IntTy); 2425 } 2426 else { 2427 // We can't represent values of this type, but we still need to set a value 2428 // to record that the region has been initialized. 2429 // If this assertion ever fires, a new case should be added above -- we 2430 // should know how to default-initialize any value we can symbolicate. 2431 assert(!SymbolManager::canSymbolicate(T) && "This type is representable"); 2432 V = UnknownVal(); 2433 } 2434 2435 return B.addBinding(R, BindingKey::Default, V); 2436 } 2437 2438 Optional<RegionBindingsRef> RegionStoreManager::tryBindSmallArray( 2439 RegionBindingsConstRef B, const TypedValueRegion *R, const ArrayType *AT, 2440 nonloc::LazyCompoundVal LCV) { 2441 2442 auto CAT = dyn_cast<ConstantArrayType>(AT); 2443 2444 // If we don't know the size, create a lazyCompoundVal instead. 2445 if (!CAT) 2446 return None; 2447 2448 QualType Ty = CAT->getElementType(); 2449 if (!(Ty->isScalarType() || Ty->isReferenceType())) 2450 return None; 2451 2452 // If the array is too big, create a LCV instead. 2453 uint64_t ArrSize = CAT->getSize().getLimitedValue(); 2454 if (ArrSize > SmallArrayLimit) 2455 return None; 2456 2457 RegionBindingsRef NewB = B; 2458 2459 for (uint64_t i = 0; i < ArrSize; ++i) { 2460 auto Idx = svalBuilder.makeArrayIndex(i); 2461 const ElementRegion *SrcER = 2462 MRMgr.getElementRegion(Ty, Idx, LCV.getRegion(), Ctx); 2463 SVal V = getBindingForElement(getRegionBindings(LCV.getStore()), SrcER); 2464 2465 const ElementRegion *DstER = MRMgr.getElementRegion(Ty, Idx, R, Ctx); 2466 NewB = bind(NewB, loc::MemRegionVal(DstER), V); 2467 } 2468 2469 return NewB; 2470 } 2471 2472 RegionBindingsRef 2473 RegionStoreManager::bindArray(RegionBindingsConstRef B, 2474 const TypedValueRegion* R, 2475 SVal Init) { 2476 2477 const ArrayType *AT =cast<ArrayType>(Ctx.getCanonicalType(R->getValueType())); 2478 QualType ElementTy = AT->getElementType(); 2479 Optional<uint64_t> Size; 2480 2481 if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(AT)) 2482 Size = CAT->getSize().getZExtValue(); 2483 2484 // Check if the init expr is a literal. If so, bind the rvalue instead. 2485 // FIXME: It's not responsibility of the Store to transform this lvalue 2486 // to rvalue. ExprEngine or maybe even CFG should do this before binding. 2487 if (Optional<loc::MemRegionVal> MRV = Init.getAs<loc::MemRegionVal>()) { 2488 SVal V = getBinding(B.asStore(), *MRV, R->getValueType()); 2489 return bindAggregate(B, R, V); 2490 } 2491 2492 // Handle lazy compound values. 2493 if (Optional<nonloc::LazyCompoundVal> LCV = 2494 Init.getAs<nonloc::LazyCompoundVal>()) { 2495 if (Optional<RegionBindingsRef> NewB = tryBindSmallArray(B, R, AT, *LCV)) 2496 return *NewB; 2497 2498 return bindAggregate(B, R, Init); 2499 } 2500 2501 if (Init.isUnknown()) 2502 return bindAggregate(B, R, UnknownVal()); 2503 2504 // Remaining case: explicit compound values. 2505 const nonloc::CompoundVal& CV = Init.castAs<nonloc::CompoundVal>(); 2506 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); 2507 uint64_t i = 0; 2508 2509 RegionBindingsRef NewB(B); 2510 2511 for (; Size ? i < *Size : true; ++i, ++VI) { 2512 // The init list might be shorter than the array length. 2513 if (VI == VE) 2514 break; 2515 2516 const NonLoc &Idx = svalBuilder.makeArrayIndex(i); 2517 const ElementRegion *ER = MRMgr.getElementRegion(ElementTy, Idx, R, Ctx); 2518 2519 if (ElementTy->isStructureOrClassType()) 2520 NewB = bindStruct(NewB, ER, *VI); 2521 else if (ElementTy->isArrayType()) 2522 NewB = bindArray(NewB, ER, *VI); 2523 else 2524 NewB = bind(NewB, loc::MemRegionVal(ER), *VI); 2525 } 2526 2527 // If the init list is shorter than the array length (or the array has 2528 // variable length), set the array default value. Values that are already set 2529 // are not overwritten. 2530 if (!Size || i < *Size) 2531 NewB = setImplicitDefaultValue(NewB, R, ElementTy); 2532 2533 return NewB; 2534 } 2535 2536 RegionBindingsRef RegionStoreManager::bindVector(RegionBindingsConstRef B, 2537 const TypedValueRegion* R, 2538 SVal V) { 2539 QualType T = R->getValueType(); 2540 const VectorType *VT = T->castAs<VectorType>(); // Use castAs for typedefs. 2541 2542 // Handle lazy compound values and symbolic values. 2543 if (isa<nonloc::LazyCompoundVal, nonloc::SymbolVal>(V)) 2544 return bindAggregate(B, R, V); 2545 2546 // We may get non-CompoundVal accidentally due to imprecise cast logic or 2547 // that we are binding symbolic struct value. Kill the field values, and if 2548 // the value is symbolic go and bind it as a "default" binding. 2549 if (!isa<nonloc::CompoundVal>(V)) { 2550 return bindAggregate(B, R, UnknownVal()); 2551 } 2552 2553 QualType ElemType = VT->getElementType(); 2554 nonloc::CompoundVal CV = V.castAs<nonloc::CompoundVal>(); 2555 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); 2556 unsigned index = 0, numElements = VT->getNumElements(); 2557 RegionBindingsRef NewB(B); 2558 2559 for ( ; index != numElements ; ++index) { 2560 if (VI == VE) 2561 break; 2562 2563 NonLoc Idx = svalBuilder.makeArrayIndex(index); 2564 const ElementRegion *ER = MRMgr.getElementRegion(ElemType, Idx, R, Ctx); 2565 2566 if (ElemType->isArrayType()) 2567 NewB = bindArray(NewB, ER, *VI); 2568 else if (ElemType->isStructureOrClassType()) 2569 NewB = bindStruct(NewB, ER, *VI); 2570 else 2571 NewB = bind(NewB, loc::MemRegionVal(ER), *VI); 2572 } 2573 return NewB; 2574 } 2575 2576 Optional<RegionBindingsRef> 2577 RegionStoreManager::tryBindSmallStruct(RegionBindingsConstRef B, 2578 const TypedValueRegion *R, 2579 const RecordDecl *RD, 2580 nonloc::LazyCompoundVal LCV) { 2581 FieldVector Fields; 2582 2583 if (const CXXRecordDecl *Class = dyn_cast<CXXRecordDecl>(RD)) 2584 if (Class->getNumBases() != 0 || Class->getNumVBases() != 0) 2585 return None; 2586 2587 for (const auto *FD : RD->fields()) { 2588 if (FD->isUnnamedBitfield()) 2589 continue; 2590 2591 // If there are too many fields, or if any of the fields are aggregates, 2592 // just use the LCV as a default binding. 2593 if (Fields.size() == SmallStructLimit) 2594 return None; 2595 2596 QualType Ty = FD->getType(); 2597 if (!(Ty->isScalarType() || Ty->isReferenceType())) 2598 return None; 2599 2600 Fields.push_back(FD); 2601 } 2602 2603 RegionBindingsRef NewB = B; 2604 2605 for (FieldVector::iterator I = Fields.begin(), E = Fields.end(); I != E; ++I){ 2606 const FieldRegion *SourceFR = MRMgr.getFieldRegion(*I, LCV.getRegion()); 2607 SVal V = getBindingForField(getRegionBindings(LCV.getStore()), SourceFR); 2608 2609 const FieldRegion *DestFR = MRMgr.getFieldRegion(*I, R); 2610 NewB = bind(NewB, loc::MemRegionVal(DestFR), V); 2611 } 2612 2613 return NewB; 2614 } 2615 2616 RegionBindingsRef RegionStoreManager::bindStruct(RegionBindingsConstRef B, 2617 const TypedValueRegion *R, 2618 SVal V) { 2619 QualType T = R->getValueType(); 2620 assert(T->isStructureOrClassType()); 2621 2622 const RecordType* RT = T->castAs<RecordType>(); 2623 const RecordDecl *RD = RT->getDecl(); 2624 2625 if (!RD->isCompleteDefinition()) 2626 return B; 2627 2628 // Handle lazy compound values and symbolic values. 2629 if (Optional<nonloc::LazyCompoundVal> LCV = 2630 V.getAs<nonloc::LazyCompoundVal>()) { 2631 if (Optional<RegionBindingsRef> NewB = tryBindSmallStruct(B, R, RD, *LCV)) 2632 return *NewB; 2633 return bindAggregate(B, R, V); 2634 } 2635 if (isa<nonloc::SymbolVal>(V)) 2636 return bindAggregate(B, R, V); 2637 2638 // We may get non-CompoundVal accidentally due to imprecise cast logic or 2639 // that we are binding symbolic struct value. Kill the field values, and if 2640 // the value is symbolic go and bind it as a "default" binding. 2641 if (V.isUnknown() || !isa<nonloc::CompoundVal>(V)) 2642 return bindAggregate(B, R, UnknownVal()); 2643 2644 // The raw CompoundVal is essentially a symbolic InitListExpr: an (immutable) 2645 // list of other values. It appears pretty much only when there's an actual 2646 // initializer list expression in the program, and the analyzer tries to 2647 // unwrap it as soon as possible. 2648 // This code is where such unwrap happens: when the compound value is put into 2649 // the object that it was supposed to initialize (it's an *initializer* list, 2650 // after all), instead of binding the whole value to the whole object, we bind 2651 // sub-values to sub-objects. Sub-values may themselves be compound values, 2652 // and in this case the procedure becomes recursive. 2653 // FIXME: The annoying part about compound values is that they don't carry 2654 // any sort of information about which value corresponds to which sub-object. 2655 // It's simply a list of values in the middle of nowhere; we expect to match 2656 // them to sub-objects, essentially, "by index": first value binds to 2657 // the first field, second value binds to the second field, etc. 2658 // It would have been much safer to organize non-lazy compound values as 2659 // a mapping from fields/bases to values. 2660 const nonloc::CompoundVal& CV = V.castAs<nonloc::CompoundVal>(); 2661 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); 2662 2663 RegionBindingsRef NewB(B); 2664 2665 // In C++17 aggregates may have base classes, handle those as well. 2666 // They appear before fields in the initializer list / compound value. 2667 if (const auto *CRD = dyn_cast<CXXRecordDecl>(RD)) { 2668 // If the object was constructed with a constructor, its value is a 2669 // LazyCompoundVal. If it's a raw CompoundVal, it means that we're 2670 // performing aggregate initialization. The only exception from this 2671 // rule is sending an Objective-C++ message that returns a C++ object 2672 // to a nil receiver; in this case the semantics is to return a 2673 // zero-initialized object even if it's a C++ object that doesn't have 2674 // this sort of constructor; the CompoundVal is empty in this case. 2675 assert((CRD->isAggregate() || (Ctx.getLangOpts().ObjC && VI == VE)) && 2676 "Non-aggregates are constructed with a constructor!"); 2677 2678 for (const auto &B : CRD->bases()) { 2679 // (Multiple inheritance is fine though.) 2680 assert(!B.isVirtual() && "Aggregates cannot have virtual base classes!"); 2681 2682 if (VI == VE) 2683 break; 2684 2685 QualType BTy = B.getType(); 2686 assert(BTy->isStructureOrClassType() && "Base classes must be classes!"); 2687 2688 const CXXRecordDecl *BRD = BTy->getAsCXXRecordDecl(); 2689 assert(BRD && "Base classes must be C++ classes!"); 2690 2691 const CXXBaseObjectRegion *BR = 2692 MRMgr.getCXXBaseObjectRegion(BRD, R, /*IsVirtual=*/false); 2693 2694 NewB = bindStruct(NewB, BR, *VI); 2695 2696 ++VI; 2697 } 2698 } 2699 2700 RecordDecl::field_iterator FI, FE; 2701 2702 for (FI = RD->field_begin(), FE = RD->field_end(); FI != FE; ++FI) { 2703 2704 if (VI == VE) 2705 break; 2706 2707 // Skip any unnamed bitfields to stay in sync with the initializers. 2708 if (FI->isUnnamedBitfield()) 2709 continue; 2710 2711 QualType FTy = FI->getType(); 2712 const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R); 2713 2714 if (FTy->isArrayType()) 2715 NewB = bindArray(NewB, FR, *VI); 2716 else if (FTy->isStructureOrClassType()) 2717 NewB = bindStruct(NewB, FR, *VI); 2718 else 2719 NewB = bind(NewB, loc::MemRegionVal(FR), *VI); 2720 ++VI; 2721 } 2722 2723 // There may be fewer values in the initialize list than the fields of struct. 2724 if (FI != FE) { 2725 NewB = NewB.addBinding(R, BindingKey::Default, 2726 svalBuilder.makeIntVal(0, false)); 2727 } 2728 2729 return NewB; 2730 } 2731 2732 RegionBindingsRef 2733 RegionStoreManager::bindAggregate(RegionBindingsConstRef B, 2734 const TypedRegion *R, 2735 SVal Val) { 2736 // Remove the old bindings, using 'R' as the root of all regions 2737 // we will invalidate. Then add the new binding. 2738 return removeSubRegionBindings(B, R).addBinding(R, BindingKey::Default, Val); 2739 } 2740 2741 //===----------------------------------------------------------------------===// 2742 // State pruning. 2743 //===----------------------------------------------------------------------===// 2744 2745 namespace { 2746 class RemoveDeadBindingsWorker 2747 : public ClusterAnalysis<RemoveDeadBindingsWorker> { 2748 SmallVector<const SymbolicRegion *, 12> Postponed; 2749 SymbolReaper &SymReaper; 2750 const StackFrameContext *CurrentLCtx; 2751 2752 public: 2753 RemoveDeadBindingsWorker(RegionStoreManager &rm, 2754 ProgramStateManager &stateMgr, 2755 RegionBindingsRef b, SymbolReaper &symReaper, 2756 const StackFrameContext *LCtx) 2757 : ClusterAnalysis<RemoveDeadBindingsWorker>(rm, stateMgr, b), 2758 SymReaper(symReaper), CurrentLCtx(LCtx) {} 2759 2760 // Called by ClusterAnalysis. 2761 void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C); 2762 void VisitCluster(const MemRegion *baseR, const ClusterBindings *C); 2763 using ClusterAnalysis<RemoveDeadBindingsWorker>::VisitCluster; 2764 2765 using ClusterAnalysis::AddToWorkList; 2766 2767 bool AddToWorkList(const MemRegion *R); 2768 2769 bool UpdatePostponed(); 2770 void VisitBinding(SVal V); 2771 }; 2772 } 2773 2774 bool RemoveDeadBindingsWorker::AddToWorkList(const MemRegion *R) { 2775 const MemRegion *BaseR = R->getBaseRegion(); 2776 return AddToWorkList(WorkListElement(BaseR), getCluster(BaseR)); 2777 } 2778 2779 void RemoveDeadBindingsWorker::VisitAddedToCluster(const MemRegion *baseR, 2780 const ClusterBindings &C) { 2781 2782 if (const VarRegion *VR = dyn_cast<VarRegion>(baseR)) { 2783 if (SymReaper.isLive(VR)) 2784 AddToWorkList(baseR, &C); 2785 2786 return; 2787 } 2788 2789 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) { 2790 if (SymReaper.isLive(SR->getSymbol())) 2791 AddToWorkList(SR, &C); 2792 else 2793 Postponed.push_back(SR); 2794 2795 return; 2796 } 2797 2798 if (isa<NonStaticGlobalSpaceRegion>(baseR)) { 2799 AddToWorkList(baseR, &C); 2800 return; 2801 } 2802 2803 // CXXThisRegion in the current or parent location context is live. 2804 if (const CXXThisRegion *TR = dyn_cast<CXXThisRegion>(baseR)) { 2805 const auto *StackReg = 2806 cast<StackArgumentsSpaceRegion>(TR->getSuperRegion()); 2807 const StackFrameContext *RegCtx = StackReg->getStackFrame(); 2808 if (CurrentLCtx && 2809 (RegCtx == CurrentLCtx || RegCtx->isParentOf(CurrentLCtx))) 2810 AddToWorkList(TR, &C); 2811 } 2812 } 2813 2814 void RemoveDeadBindingsWorker::VisitCluster(const MemRegion *baseR, 2815 const ClusterBindings *C) { 2816 if (!C) 2817 return; 2818 2819 // Mark the symbol for any SymbolicRegion with live bindings as live itself. 2820 // This means we should continue to track that symbol. 2821 if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(baseR)) 2822 SymReaper.markLive(SymR->getSymbol()); 2823 2824 for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I) { 2825 // Element index of a binding key is live. 2826 SymReaper.markElementIndicesLive(I.getKey().getRegion()); 2827 2828 VisitBinding(I.getData()); 2829 } 2830 } 2831 2832 void RemoveDeadBindingsWorker::VisitBinding(SVal V) { 2833 // Is it a LazyCompoundVal? All referenced regions are live as well. 2834 if (Optional<nonloc::LazyCompoundVal> LCS = 2835 V.getAs<nonloc::LazyCompoundVal>()) { 2836 2837 const RegionStoreManager::SValListTy &Vals = RM.getInterestingValues(*LCS); 2838 2839 for (RegionStoreManager::SValListTy::const_iterator I = Vals.begin(), 2840 E = Vals.end(); 2841 I != E; ++I) 2842 VisitBinding(*I); 2843 2844 return; 2845 } 2846 2847 // If V is a region, then add it to the worklist. 2848 if (const MemRegion *R = V.getAsRegion()) { 2849 AddToWorkList(R); 2850 SymReaper.markLive(R); 2851 2852 // All regions captured by a block are also live. 2853 if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(R)) { 2854 BlockDataRegion::referenced_vars_iterator I = BR->referenced_vars_begin(), 2855 E = BR->referenced_vars_end(); 2856 for ( ; I != E; ++I) 2857 AddToWorkList(I.getCapturedRegion()); 2858 } 2859 } 2860 2861 2862 // Update the set of live symbols. 2863 for (auto SI = V.symbol_begin(), SE = V.symbol_end(); SI!=SE; ++SI) 2864 SymReaper.markLive(*SI); 2865 } 2866 2867 bool RemoveDeadBindingsWorker::UpdatePostponed() { 2868 // See if any postponed SymbolicRegions are actually live now, after 2869 // having done a scan. 2870 bool Changed = false; 2871 2872 for (auto I = Postponed.begin(), E = Postponed.end(); I != E; ++I) { 2873 if (const SymbolicRegion *SR = *I) { 2874 if (SymReaper.isLive(SR->getSymbol())) { 2875 Changed |= AddToWorkList(SR); 2876 *I = nullptr; 2877 } 2878 } 2879 } 2880 2881 return Changed; 2882 } 2883 2884 StoreRef RegionStoreManager::removeDeadBindings(Store store, 2885 const StackFrameContext *LCtx, 2886 SymbolReaper& SymReaper) { 2887 RegionBindingsRef B = getRegionBindings(store); 2888 RemoveDeadBindingsWorker W(*this, StateMgr, B, SymReaper, LCtx); 2889 W.GenerateClusters(); 2890 2891 // Enqueue the region roots onto the worklist. 2892 for (SymbolReaper::region_iterator I = SymReaper.region_begin(), 2893 E = SymReaper.region_end(); I != E; ++I) { 2894 W.AddToWorkList(*I); 2895 } 2896 2897 do W.RunWorkList(); while (W.UpdatePostponed()); 2898 2899 // We have now scanned the store, marking reachable regions and symbols 2900 // as live. We now remove all the regions that are dead from the store 2901 // as well as update DSymbols with the set symbols that are now dead. 2902 for (RegionBindingsRef::iterator I = B.begin(), E = B.end(); I != E; ++I) { 2903 const MemRegion *Base = I.getKey(); 2904 2905 // If the cluster has been visited, we know the region has been marked. 2906 // Otherwise, remove the dead entry. 2907 if (!W.isVisited(Base)) 2908 B = B.remove(Base); 2909 } 2910 2911 return StoreRef(B.asStore(), *this); 2912 } 2913 2914 //===----------------------------------------------------------------------===// 2915 // Utility methods. 2916 //===----------------------------------------------------------------------===// 2917 2918 void RegionStoreManager::printJson(raw_ostream &Out, Store S, const char *NL, 2919 unsigned int Space, bool IsDot) const { 2920 RegionBindingsRef Bindings = getRegionBindings(S); 2921 2922 Indent(Out, Space, IsDot) << "\"store\": "; 2923 2924 if (Bindings.isEmpty()) { 2925 Out << "null," << NL; 2926 return; 2927 } 2928 2929 Out << "{ \"pointer\": \"" << Bindings.asStore() << "\", \"items\": [" << NL; 2930 Bindings.printJson(Out, NL, Space + 1, IsDot); 2931 Indent(Out, Space, IsDot) << "]}," << NL; 2932 } 2933