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