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/CharUnits.h" 18 #include "clang/AST/DeclCXX.h" 19 #include "clang/AST/ExprCXX.h" 20 #include "clang/Analysis/Analyses/LiveVariables.h" 21 #include "clang/Analysis/AnalysisContext.h" 22 #include "clang/Basic/TargetInfo.h" 23 #include "clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h" 24 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 25 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 26 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 27 #include "llvm/ADT/ImmutableList.h" 28 #include "llvm/ADT/ImmutableMap.h" 29 #include "llvm/ADT/Optional.h" 30 #include "llvm/Support/raw_ostream.h" 31 32 using namespace clang; 33 using namespace ento; 34 using llvm::Optional; 35 36 //===----------------------------------------------------------------------===// 37 // Representation of binding keys. 38 //===----------------------------------------------------------------------===// 39 40 namespace { 41 class BindingKey { 42 public: 43 enum Kind { Direct = 0x0, Default = 0x1 }; 44 private: 45 llvm ::PointerIntPair<const MemRegion*, 1> P; 46 uint64_t Offset; 47 48 explicit BindingKey(const MemRegion *r, uint64_t offset, Kind k) 49 : P(r, (unsigned) k), Offset(offset) {} 50 public: 51 52 bool isDirect() const { return P.getInt() == Direct; } 53 54 const MemRegion *getRegion() const { return P.getPointer(); } 55 uint64_t getOffset() const { return Offset; } 56 57 void Profile(llvm::FoldingSetNodeID& ID) const { 58 ID.AddPointer(P.getOpaqueValue()); 59 ID.AddInteger(Offset); 60 } 61 62 static BindingKey Make(const MemRegion *R, Kind k); 63 64 bool operator<(const BindingKey &X) const { 65 if (P.getOpaqueValue() < X.P.getOpaqueValue()) 66 return true; 67 if (P.getOpaqueValue() > X.P.getOpaqueValue()) 68 return false; 69 return Offset < X.Offset; 70 } 71 72 bool operator==(const BindingKey &X) const { 73 return P.getOpaqueValue() == X.P.getOpaqueValue() && 74 Offset == X.Offset; 75 } 76 77 bool isValid() const { 78 return getRegion() != NULL; 79 } 80 }; 81 } // end anonymous namespace 82 83 BindingKey BindingKey::Make(const MemRegion *R, Kind k) { 84 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) { 85 const RegionRawOffset &O = ER->getAsArrayOffset(); 86 87 // FIXME: There are some ElementRegions for which we cannot compute 88 // raw offsets yet, including regions with symbolic offsets. These will be 89 // ignored by the store. 90 return BindingKey(O.getRegion(), O.getOffset().getQuantity(), k); 91 } 92 93 return BindingKey(R, 0, k); 94 } 95 96 namespace llvm { 97 static inline 98 raw_ostream &operator<<(raw_ostream &os, BindingKey K) { 99 os << '(' << K.getRegion() << ',' << K.getOffset() 100 << ',' << (K.isDirect() ? "direct" : "default") 101 << ')'; 102 return os; 103 } 104 } // end llvm namespace 105 106 //===----------------------------------------------------------------------===// 107 // Actual Store type. 108 //===----------------------------------------------------------------------===// 109 110 typedef llvm::ImmutableMap<BindingKey, SVal> RegionBindings; 111 112 //===----------------------------------------------------------------------===// 113 // Fine-grained control of RegionStoreManager. 114 //===----------------------------------------------------------------------===// 115 116 namespace { 117 struct minimal_features_tag {}; 118 struct maximal_features_tag {}; 119 120 class RegionStoreFeatures { 121 bool SupportsFields; 122 public: 123 RegionStoreFeatures(minimal_features_tag) : 124 SupportsFields(false) {} 125 126 RegionStoreFeatures(maximal_features_tag) : 127 SupportsFields(true) {} 128 129 void enableFields(bool t) { SupportsFields = t; } 130 131 bool supportsFields() const { return SupportsFields; } 132 }; 133 } 134 135 //===----------------------------------------------------------------------===// 136 // Main RegionStore logic. 137 //===----------------------------------------------------------------------===// 138 139 namespace { 140 141 class RegionStoreSubRegionMap : public SubRegionMap { 142 public: 143 typedef llvm::ImmutableSet<const MemRegion*> Set; 144 typedef llvm::DenseMap<const MemRegion*, Set> Map; 145 private: 146 Set::Factory F; 147 Map M; 148 public: 149 bool add(const MemRegion* Parent, const MemRegion* SubRegion) { 150 Map::iterator I = M.find(Parent); 151 152 if (I == M.end()) { 153 M.insert(std::make_pair(Parent, F.add(F.getEmptySet(), SubRegion))); 154 return true; 155 } 156 157 I->second = F.add(I->second, SubRegion); 158 return false; 159 } 160 161 void process(SmallVectorImpl<const SubRegion*> &WL, const SubRegion *R); 162 163 ~RegionStoreSubRegionMap() {} 164 165 const Set *getSubRegions(const MemRegion *Parent) const { 166 Map::const_iterator I = M.find(Parent); 167 return I == M.end() ? NULL : &I->second; 168 } 169 170 bool iterSubRegions(const MemRegion* Parent, Visitor& V) const { 171 Map::const_iterator I = M.find(Parent); 172 173 if (I == M.end()) 174 return true; 175 176 Set S = I->second; 177 for (Set::iterator SI=S.begin(),SE=S.end(); SI != SE; ++SI) { 178 if (!V.Visit(Parent, *SI)) 179 return false; 180 } 181 182 return true; 183 } 184 }; 185 186 void 187 RegionStoreSubRegionMap::process(SmallVectorImpl<const SubRegion*> &WL, 188 const SubRegion *R) { 189 const MemRegion *superR = R->getSuperRegion(); 190 if (add(superR, R)) 191 if (const SubRegion *sr = dyn_cast<SubRegion>(superR)) 192 WL.push_back(sr); 193 } 194 195 class RegionStoreManager : public StoreManager { 196 const RegionStoreFeatures Features; 197 RegionBindings::Factory RBFactory; 198 199 public: 200 RegionStoreManager(ProgramStateManager& mgr, const RegionStoreFeatures &f) 201 : StoreManager(mgr), 202 Features(f), 203 RBFactory(mgr.getAllocator()) {} 204 205 SubRegionMap *getSubRegionMap(Store store) { 206 return getRegionStoreSubRegionMap(store); 207 } 208 209 RegionStoreSubRegionMap *getRegionStoreSubRegionMap(Store store); 210 211 Optional<SVal> getDirectBinding(RegionBindings B, const MemRegion *R); 212 /// getDefaultBinding - Returns an SVal* representing an optional default 213 /// binding associated with a region and its subregions. 214 Optional<SVal> getDefaultBinding(RegionBindings B, const MemRegion *R); 215 216 /// setImplicitDefaultValue - Set the default binding for the provided 217 /// MemRegion to the value implicitly defined for compound literals when 218 /// the value is not specified. 219 StoreRef setImplicitDefaultValue(Store store, const MemRegion *R, QualType T); 220 221 /// ArrayToPointer - Emulates the "decay" of an array to a pointer 222 /// type. 'Array' represents the lvalue of the array being decayed 223 /// to a pointer, and the returned SVal represents the decayed 224 /// version of that lvalue (i.e., a pointer to the first element of 225 /// the array). This is called by ExprEngine when evaluating 226 /// casts from arrays to pointers. 227 SVal ArrayToPointer(Loc Array); 228 229 /// For DerivedToBase casts, create a CXXBaseObjectRegion and return it. 230 virtual SVal evalDerivedToBase(SVal derived, QualType basePtrType); 231 232 /// \brief Evaluates C++ dynamic_cast cast. 233 /// The callback may result in the following 3 scenarios: 234 /// - Successful cast (ex: derived is subclass of base). 235 /// - Failed cast (ex: derived is definitely not a subclass of base). 236 /// - We don't know (base is a symbolic region and we don't have 237 /// enough info to determine if the cast will succeed at run time). 238 /// The function returns an SVal representing the derived class; it's 239 /// valid only if Failed flag is set to false. 240 virtual SVal evalDynamicCast(SVal base, QualType derivedPtrType,bool &Failed); 241 242 StoreRef getInitialStore(const LocationContext *InitLoc) { 243 return StoreRef(RBFactory.getEmptyMap().getRootWithoutRetain(), *this); 244 } 245 246 //===-------------------------------------------------------------------===// 247 // Binding values to regions. 248 //===-------------------------------------------------------------------===// 249 RegionBindings invalidateGlobalRegion(MemRegion::Kind K, 250 const Expr *Ex, 251 unsigned Count, 252 const LocationContext *LCtx, 253 RegionBindings B, 254 InvalidatedRegions *Invalidated); 255 256 StoreRef invalidateRegions(Store store, ArrayRef<const MemRegion *> Regions, 257 const Expr *E, unsigned Count, 258 const LocationContext *LCtx, 259 InvalidatedSymbols &IS, 260 const CallOrObjCMessage *Call, 261 InvalidatedRegions *Invalidated); 262 263 public: // Made public for helper classes. 264 265 void RemoveSubRegionBindings(RegionBindings &B, const MemRegion *R, 266 RegionStoreSubRegionMap &M); 267 268 RegionBindings addBinding(RegionBindings B, BindingKey K, SVal V); 269 270 RegionBindings addBinding(RegionBindings B, const MemRegion *R, 271 BindingKey::Kind k, SVal V); 272 273 const SVal *lookup(RegionBindings B, BindingKey K); 274 const SVal *lookup(RegionBindings B, const MemRegion *R, BindingKey::Kind k); 275 276 RegionBindings removeBinding(RegionBindings B, BindingKey K); 277 RegionBindings removeBinding(RegionBindings B, const MemRegion *R, 278 BindingKey::Kind k); 279 280 RegionBindings removeBinding(RegionBindings B, const MemRegion *R) { 281 return removeBinding(removeBinding(B, R, BindingKey::Direct), R, 282 BindingKey::Default); 283 } 284 285 public: // Part of public interface to class. 286 287 StoreRef Bind(Store store, Loc LV, SVal V); 288 289 // BindDefault is only used to initialize a region with a default value. 290 StoreRef BindDefault(Store store, const MemRegion *R, SVal V) { 291 RegionBindings B = GetRegionBindings(store); 292 assert(!lookup(B, R, BindingKey::Default)); 293 assert(!lookup(B, R, BindingKey::Direct)); 294 return StoreRef(addBinding(B, R, BindingKey::Default, V) 295 .getRootWithoutRetain(), *this); 296 } 297 298 StoreRef BindCompoundLiteral(Store store, const CompoundLiteralExpr *CL, 299 const LocationContext *LC, SVal V); 300 301 StoreRef BindDecl(Store store, const VarRegion *VR, SVal InitVal); 302 303 StoreRef BindDeclWithNoInit(Store store, const VarRegion *) { 304 return StoreRef(store, *this); 305 } 306 307 /// BindStruct - Bind a compound value to a structure. 308 StoreRef BindStruct(Store store, const TypedValueRegion* R, SVal V); 309 310 StoreRef BindArray(Store store, const TypedValueRegion* R, SVal V); 311 312 /// KillStruct - Set the entire struct to unknown. 313 StoreRef KillStruct(Store store, const TypedRegion* R, SVal DefaultVal); 314 315 StoreRef Remove(Store store, Loc LV); 316 317 void incrementReferenceCount(Store store) { 318 GetRegionBindings(store).manualRetain(); 319 } 320 321 /// If the StoreManager supports it, decrement the reference count of 322 /// the specified Store object. If the reference count hits 0, the memory 323 /// associated with the object is recycled. 324 void decrementReferenceCount(Store store) { 325 GetRegionBindings(store).manualRelease(); 326 } 327 328 bool includedInBindings(Store store, const MemRegion *region) const; 329 330 /// \brief Return the value bound to specified location in a given state. 331 /// 332 /// The high level logic for this method is this: 333 /// getBinding (L) 334 /// if L has binding 335 /// return L's binding 336 /// else if L is in killset 337 /// return unknown 338 /// else 339 /// if L is on stack or heap 340 /// return undefined 341 /// else 342 /// return symbolic 343 SVal getBinding(Store store, Loc L, QualType T = QualType()); 344 345 SVal getBindingForElement(Store store, const ElementRegion *R); 346 347 SVal getBindingForField(Store store, const FieldRegion *R); 348 349 SVal getBindingForObjCIvar(Store store, const ObjCIvarRegion *R); 350 351 SVal getBindingForVar(Store store, const VarRegion *R); 352 353 SVal getBindingForLazySymbol(const TypedValueRegion *R); 354 355 SVal getBindingForFieldOrElementCommon(Store store, const TypedValueRegion *R, 356 QualType Ty, const MemRegion *superR); 357 358 SVal getLazyBinding(const MemRegion *lazyBindingRegion, 359 Store lazyBindingStore); 360 361 /// Get bindings for the values in a struct and return a CompoundVal, used 362 /// when doing struct copy: 363 /// struct s x, y; 364 /// x = y; 365 /// y's value is retrieved by this method. 366 SVal getBindingForStruct(Store store, const TypedValueRegion* R); 367 368 SVal getBindingForArray(Store store, const TypedValueRegion* R); 369 370 /// Used to lazily generate derived symbols for bindings that are defined 371 /// implicitly by default bindings in a super region. 372 Optional<SVal> getBindingForDerivedDefaultValue(RegionBindings B, 373 const MemRegion *superR, 374 const TypedValueRegion *R, 375 QualType Ty); 376 377 /// Get the state and region whose binding this region R corresponds to. 378 std::pair<Store, const MemRegion*> 379 GetLazyBinding(RegionBindings B, const MemRegion *R, 380 const MemRegion *originalRegion); 381 382 StoreRef CopyLazyBindings(nonloc::LazyCompoundVal V, Store store, 383 const TypedRegion *R); 384 385 //===------------------------------------------------------------------===// 386 // State pruning. 387 //===------------------------------------------------------------------===// 388 389 /// removeDeadBindings - Scans the RegionStore of 'state' for dead values. 390 /// It returns a new Store with these values removed. 391 StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx, 392 SymbolReaper& SymReaper); 393 394 StoreRef enterStackFrame(ProgramStateRef state, 395 const LocationContext *callerCtx, 396 const StackFrameContext *calleeCtx); 397 398 //===------------------------------------------------------------------===// 399 // Region "extents". 400 //===------------------------------------------------------------------===// 401 402 // FIXME: This method will soon be eliminated; see the note in Store.h. 403 DefinedOrUnknownSVal getSizeInElements(ProgramStateRef state, 404 const MemRegion* R, QualType EleTy); 405 406 //===------------------------------------------------------------------===// 407 // Utility methods. 408 //===------------------------------------------------------------------===// 409 410 static inline RegionBindings GetRegionBindings(Store store) { 411 return RegionBindings(static_cast<const RegionBindings::TreeTy*>(store)); 412 } 413 414 void print(Store store, raw_ostream &Out, const char* nl, 415 const char *sep); 416 417 void iterBindings(Store store, BindingsHandler& f) { 418 RegionBindings B = GetRegionBindings(store); 419 for (RegionBindings::iterator I=B.begin(), E=B.end(); I!=E; ++I) { 420 const BindingKey &K = I.getKey(); 421 if (!K.isDirect()) 422 continue; 423 if (const SubRegion *R = dyn_cast<SubRegion>(I.getKey().getRegion())) { 424 // FIXME: Possibly incorporate the offset? 425 if (!f.HandleBinding(*this, store, R, I.getData())) 426 return; 427 } 428 } 429 } 430 }; 431 432 } // end anonymous namespace 433 434 //===----------------------------------------------------------------------===// 435 // RegionStore creation. 436 //===----------------------------------------------------------------------===// 437 438 StoreManager *ento::CreateRegionStoreManager(ProgramStateManager& StMgr) { 439 RegionStoreFeatures F = maximal_features_tag(); 440 return new RegionStoreManager(StMgr, F); 441 } 442 443 StoreManager * 444 ento::CreateFieldsOnlyRegionStoreManager(ProgramStateManager &StMgr) { 445 RegionStoreFeatures F = minimal_features_tag(); 446 F.enableFields(true); 447 return new RegionStoreManager(StMgr, F); 448 } 449 450 451 RegionStoreSubRegionMap* 452 RegionStoreManager::getRegionStoreSubRegionMap(Store store) { 453 RegionBindings B = GetRegionBindings(store); 454 RegionStoreSubRegionMap *M = new RegionStoreSubRegionMap(); 455 456 SmallVector<const SubRegion*, 10> WL; 457 458 for (RegionBindings::iterator I=B.begin(), E=B.end(); I!=E; ++I) 459 if (const SubRegion *R = dyn_cast<SubRegion>(I.getKey().getRegion())) 460 M->process(WL, R); 461 462 // We also need to record in the subregion map "intermediate" regions that 463 // don't have direct bindings but are super regions of those that do. 464 while (!WL.empty()) { 465 const SubRegion *R = WL.back(); 466 WL.pop_back(); 467 M->process(WL, R); 468 } 469 470 return M; 471 } 472 473 //===----------------------------------------------------------------------===// 474 // Region Cluster analysis. 475 //===----------------------------------------------------------------------===// 476 477 namespace { 478 template <typename DERIVED> 479 class ClusterAnalysis { 480 protected: 481 typedef BumpVector<BindingKey> RegionCluster; 482 typedef llvm::DenseMap<const MemRegion *, RegionCluster *> ClusterMap; 483 llvm::DenseMap<const RegionCluster*, unsigned> Visited; 484 typedef SmallVector<std::pair<const MemRegion *, RegionCluster*>, 10> 485 WorkList; 486 487 BumpVectorContext BVC; 488 ClusterMap ClusterM; 489 WorkList WL; 490 491 RegionStoreManager &RM; 492 ASTContext &Ctx; 493 SValBuilder &svalBuilder; 494 495 RegionBindings B; 496 497 const bool includeGlobals; 498 499 public: 500 ClusterAnalysis(RegionStoreManager &rm, ProgramStateManager &StateMgr, 501 RegionBindings b, const bool includeGlobals) 502 : RM(rm), Ctx(StateMgr.getContext()), 503 svalBuilder(StateMgr.getSValBuilder()), 504 B(b), includeGlobals(includeGlobals) {} 505 506 RegionBindings getRegionBindings() const { return B; } 507 508 RegionCluster &AddToCluster(BindingKey K) { 509 const MemRegion *R = K.getRegion(); 510 const MemRegion *baseR = R->getBaseRegion(); 511 RegionCluster &C = getCluster(baseR); 512 C.push_back(K, BVC); 513 static_cast<DERIVED*>(this)->VisitAddedToCluster(baseR, C); 514 return C; 515 } 516 517 bool isVisited(const MemRegion *R) { 518 return (bool) Visited[&getCluster(R->getBaseRegion())]; 519 } 520 521 RegionCluster& getCluster(const MemRegion *R) { 522 RegionCluster *&CRef = ClusterM[R]; 523 if (!CRef) { 524 void *Mem = BVC.getAllocator().template Allocate<RegionCluster>(); 525 CRef = new (Mem) RegionCluster(BVC, 10); 526 } 527 return *CRef; 528 } 529 530 void GenerateClusters() { 531 // Scan the entire set of bindings and make the region clusters. 532 for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){ 533 RegionCluster &C = AddToCluster(RI.getKey()); 534 if (const MemRegion *R = RI.getData().getAsRegion()) { 535 // Generate a cluster, but don't add the region to the cluster 536 // if there aren't any bindings. 537 getCluster(R->getBaseRegion()); 538 } 539 if (includeGlobals) { 540 const MemRegion *R = RI.getKey().getRegion(); 541 if (isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace())) 542 AddToWorkList(R, C); 543 } 544 } 545 } 546 547 bool AddToWorkList(const MemRegion *R, RegionCluster &C) { 548 if (unsigned &visited = Visited[&C]) 549 return false; 550 else 551 visited = 1; 552 553 WL.push_back(std::make_pair(R, &C)); 554 return true; 555 } 556 557 bool AddToWorkList(BindingKey K) { 558 return AddToWorkList(K.getRegion()); 559 } 560 561 bool AddToWorkList(const MemRegion *R) { 562 const MemRegion *baseR = R->getBaseRegion(); 563 return AddToWorkList(baseR, getCluster(baseR)); 564 } 565 566 void RunWorkList() { 567 while (!WL.empty()) { 568 const MemRegion *baseR; 569 RegionCluster *C; 570 llvm::tie(baseR, C) = WL.back(); 571 WL.pop_back(); 572 573 // First visit the cluster. 574 static_cast<DERIVED*>(this)->VisitCluster(baseR, C->begin(), C->end()); 575 576 // Next, visit the base region. 577 static_cast<DERIVED*>(this)->VisitBaseRegion(baseR); 578 } 579 } 580 581 public: 582 void VisitAddedToCluster(const MemRegion *baseR, RegionCluster &C) {} 583 void VisitCluster(const MemRegion *baseR, BindingKey *I, BindingKey *E) {} 584 void VisitBaseRegion(const MemRegion *baseR) {} 585 }; 586 } 587 588 //===----------------------------------------------------------------------===// 589 // Binding invalidation. 590 //===----------------------------------------------------------------------===// 591 592 void RegionStoreManager::RemoveSubRegionBindings(RegionBindings &B, 593 const MemRegion *R, 594 RegionStoreSubRegionMap &M) { 595 596 if (const RegionStoreSubRegionMap::Set *S = M.getSubRegions(R)) 597 for (RegionStoreSubRegionMap::Set::iterator I = S->begin(), E = S->end(); 598 I != E; ++I) 599 RemoveSubRegionBindings(B, *I, M); 600 601 B = removeBinding(B, R); 602 } 603 604 namespace { 605 class invalidateRegionsWorker : public ClusterAnalysis<invalidateRegionsWorker> 606 { 607 const Expr *Ex; 608 unsigned Count; 609 const LocationContext *LCtx; 610 StoreManager::InvalidatedSymbols &IS; 611 StoreManager::InvalidatedRegions *Regions; 612 public: 613 invalidateRegionsWorker(RegionStoreManager &rm, 614 ProgramStateManager &stateMgr, 615 RegionBindings b, 616 const Expr *ex, unsigned count, 617 const LocationContext *lctx, 618 StoreManager::InvalidatedSymbols &is, 619 StoreManager::InvalidatedRegions *r, 620 bool includeGlobals) 621 : ClusterAnalysis<invalidateRegionsWorker>(rm, stateMgr, b, includeGlobals), 622 Ex(ex), Count(count), LCtx(lctx), IS(is), Regions(r) {} 623 624 void VisitCluster(const MemRegion *baseR, BindingKey *I, BindingKey *E); 625 void VisitBaseRegion(const MemRegion *baseR); 626 627 private: 628 void VisitBinding(SVal V); 629 }; 630 } 631 632 void invalidateRegionsWorker::VisitBinding(SVal V) { 633 // A symbol? Mark it touched by the invalidation. 634 if (SymbolRef Sym = V.getAsSymbol()) 635 IS.insert(Sym); 636 637 if (const MemRegion *R = V.getAsRegion()) { 638 AddToWorkList(R); 639 return; 640 } 641 642 // Is it a LazyCompoundVal? All references get invalidated as well. 643 if (const nonloc::LazyCompoundVal *LCS = 644 dyn_cast<nonloc::LazyCompoundVal>(&V)) { 645 646 const MemRegion *LazyR = LCS->getRegion(); 647 RegionBindings B = RegionStoreManager::GetRegionBindings(LCS->getStore()); 648 649 for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){ 650 const SubRegion *baseR = dyn_cast<SubRegion>(RI.getKey().getRegion()); 651 if (baseR && baseR->isSubRegionOf(LazyR)) 652 VisitBinding(RI.getData()); 653 } 654 655 return; 656 } 657 } 658 659 void invalidateRegionsWorker::VisitCluster(const MemRegion *baseR, 660 BindingKey *I, BindingKey *E) { 661 for ( ; I != E; ++I) { 662 // Get the old binding. Is it a region? If so, add it to the worklist. 663 const BindingKey &K = *I; 664 if (const SVal *V = RM.lookup(B, K)) 665 VisitBinding(*V); 666 667 B = RM.removeBinding(B, K); 668 } 669 } 670 671 void invalidateRegionsWorker::VisitBaseRegion(const MemRegion *baseR) { 672 // Symbolic region? Mark that symbol touched by the invalidation. 673 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) 674 IS.insert(SR->getSymbol()); 675 676 // BlockDataRegion? If so, invalidate captured variables that are passed 677 // by reference. 678 if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(baseR)) { 679 for (BlockDataRegion::referenced_vars_iterator 680 BI = BR->referenced_vars_begin(), BE = BR->referenced_vars_end() ; 681 BI != BE; ++BI) { 682 const VarRegion *VR = *BI; 683 const VarDecl *VD = VR->getDecl(); 684 if (VD->getAttr<BlocksAttr>() || !VD->hasLocalStorage()) 685 AddToWorkList(VR); 686 } 687 return; 688 } 689 690 // Otherwise, we have a normal data region. Record that we touched the region. 691 if (Regions) 692 Regions->push_back(baseR); 693 694 if (isa<AllocaRegion>(baseR) || isa<SymbolicRegion>(baseR)) { 695 // Invalidate the region by setting its default value to 696 // conjured symbol. The type of the symbol is irrelavant. 697 DefinedOrUnknownSVal V = 698 svalBuilder.getConjuredSymbolVal(baseR, Ex, LCtx, Ctx.IntTy, Count); 699 B = RM.addBinding(B, baseR, BindingKey::Default, V); 700 return; 701 } 702 703 if (!baseR->isBoundable()) 704 return; 705 706 const TypedValueRegion *TR = cast<TypedValueRegion>(baseR); 707 QualType T = TR->getValueType(); 708 709 // Invalidate the binding. 710 if (T->isStructureOrClassType()) { 711 // Invalidate the region by setting its default value to 712 // conjured symbol. The type of the symbol is irrelavant. 713 DefinedOrUnknownSVal V = 714 svalBuilder.getConjuredSymbolVal(baseR, Ex, LCtx, Ctx.IntTy, Count); 715 B = RM.addBinding(B, baseR, BindingKey::Default, V); 716 return; 717 } 718 719 if (const ArrayType *AT = Ctx.getAsArrayType(T)) { 720 // Set the default value of the array to conjured symbol. 721 DefinedOrUnknownSVal V = 722 svalBuilder.getConjuredSymbolVal(baseR, Ex, LCtx, 723 AT->getElementType(), Count); 724 B = RM.addBinding(B, baseR, BindingKey::Default, V); 725 return; 726 } 727 728 if (includeGlobals && 729 isa<NonStaticGlobalSpaceRegion>(baseR->getMemorySpace())) { 730 // If the region is a global and we are invalidating all globals, 731 // just erase the entry. This causes all globals to be lazily 732 // symbolicated from the same base symbol. 733 B = RM.removeBinding(B, baseR); 734 return; 735 } 736 737 738 DefinedOrUnknownSVal V = svalBuilder.getConjuredSymbolVal(baseR, Ex, LCtx, 739 T,Count); 740 assert(SymbolManager::canSymbolicate(T) || V.isUnknown()); 741 B = RM.addBinding(B, baseR, BindingKey::Direct, V); 742 } 743 744 RegionBindings RegionStoreManager::invalidateGlobalRegion(MemRegion::Kind K, 745 const Expr *Ex, 746 unsigned Count, 747 const LocationContext *LCtx, 748 RegionBindings B, 749 InvalidatedRegions *Invalidated) { 750 // Bind the globals memory space to a new symbol that we will use to derive 751 // the bindings for all globals. 752 const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion(K); 753 SVal V = 754 svalBuilder.getConjuredSymbolVal(/* SymbolTag = */ (void*) GS, Ex, LCtx, 755 /* symbol type, doesn't matter */ Ctx.IntTy, 756 Count); 757 758 B = removeBinding(B, GS); 759 B = addBinding(B, BindingKey::Make(GS, BindingKey::Default), V); 760 761 // Even if there are no bindings in the global scope, we still need to 762 // record that we touched it. 763 if (Invalidated) 764 Invalidated->push_back(GS); 765 766 return B; 767 } 768 769 StoreRef RegionStoreManager::invalidateRegions(Store store, 770 ArrayRef<const MemRegion *> Regions, 771 const Expr *Ex, unsigned Count, 772 const LocationContext *LCtx, 773 InvalidatedSymbols &IS, 774 const CallOrObjCMessage *Call, 775 InvalidatedRegions *Invalidated) { 776 invalidateRegionsWorker W(*this, StateMgr, 777 RegionStoreManager::GetRegionBindings(store), 778 Ex, Count, LCtx, IS, Invalidated, false); 779 780 // Scan the bindings and generate the clusters. 781 W.GenerateClusters(); 782 783 // Add the regions to the worklist. 784 for (ArrayRef<const MemRegion *>::iterator 785 I = Regions.begin(), E = Regions.end(); I != E; ++I) 786 W.AddToWorkList(*I); 787 788 W.RunWorkList(); 789 790 // Return the new bindings. 791 RegionBindings B = W.getRegionBindings(); 792 793 // For all globals which are not static nor immutable: determine which global 794 // regions should be invalidated and invalidate them. 795 // TODO: This could possibly be more precise with modules. 796 // 797 // System calls invalidate only system globals. 798 if (Call && Call->isInSystemHeader()) { 799 B = invalidateGlobalRegion(MemRegion::GlobalSystemSpaceRegionKind, 800 Ex, Count, LCtx, B, Invalidated); 801 // Internal calls might invalidate both system and internal globals. 802 } else { 803 B = invalidateGlobalRegion(MemRegion::GlobalSystemSpaceRegionKind, 804 Ex, Count, LCtx, B, Invalidated); 805 B = invalidateGlobalRegion(MemRegion::GlobalInternalSpaceRegionKind, 806 Ex, Count, LCtx, B, Invalidated); 807 } 808 809 return StoreRef(B.getRootWithoutRetain(), *this); 810 } 811 812 //===----------------------------------------------------------------------===// 813 // Extents for regions. 814 //===----------------------------------------------------------------------===// 815 816 DefinedOrUnknownSVal 817 RegionStoreManager::getSizeInElements(ProgramStateRef state, 818 const MemRegion *R, 819 QualType EleTy) { 820 SVal Size = cast<SubRegion>(R)->getExtent(svalBuilder); 821 const llvm::APSInt *SizeInt = svalBuilder.getKnownValue(state, Size); 822 if (!SizeInt) 823 return UnknownVal(); 824 825 CharUnits RegionSize = CharUnits::fromQuantity(SizeInt->getSExtValue()); 826 827 if (Ctx.getAsVariableArrayType(EleTy)) { 828 // FIXME: We need to track extra state to properly record the size 829 // of VLAs. Returning UnknownVal here, however, is a stop-gap so that 830 // we don't have a divide-by-zero below. 831 return UnknownVal(); 832 } 833 834 CharUnits EleSize = Ctx.getTypeSizeInChars(EleTy); 835 836 // If a variable is reinterpreted as a type that doesn't fit into a larger 837 // type evenly, round it down. 838 // This is a signed value, since it's used in arithmetic with signed indices. 839 return svalBuilder.makeIntVal(RegionSize / EleSize, false); 840 } 841 842 //===----------------------------------------------------------------------===// 843 // Location and region casting. 844 //===----------------------------------------------------------------------===// 845 846 /// ArrayToPointer - Emulates the "decay" of an array to a pointer 847 /// type. 'Array' represents the lvalue of the array being decayed 848 /// to a pointer, and the returned SVal represents the decayed 849 /// version of that lvalue (i.e., a pointer to the first element of 850 /// the array). This is called by ExprEngine when evaluating casts 851 /// from arrays to pointers. 852 SVal RegionStoreManager::ArrayToPointer(Loc Array) { 853 if (!isa<loc::MemRegionVal>(Array)) 854 return UnknownVal(); 855 856 const MemRegion* R = cast<loc::MemRegionVal>(&Array)->getRegion(); 857 const TypedValueRegion* ArrayR = dyn_cast<TypedValueRegion>(R); 858 859 if (!ArrayR) 860 return UnknownVal(); 861 862 // Strip off typedefs from the ArrayRegion's ValueType. 863 QualType T = ArrayR->getValueType().getDesugaredType(Ctx); 864 const ArrayType *AT = cast<ArrayType>(T); 865 T = AT->getElementType(); 866 867 NonLoc ZeroIdx = svalBuilder.makeZeroArrayIndex(); 868 return loc::MemRegionVal(MRMgr.getElementRegion(T, ZeroIdx, ArrayR, Ctx)); 869 } 870 871 SVal RegionStoreManager::evalDerivedToBase(SVal derived, QualType baseType) { 872 const CXXRecordDecl *baseDecl; 873 if (baseType->isPointerType()) 874 baseDecl = baseType->getCXXRecordDeclForPointerType(); 875 else 876 baseDecl = baseType->getAsCXXRecordDecl(); 877 878 assert(baseDecl && "not a CXXRecordDecl?"); 879 880 loc::MemRegionVal *derivedRegVal = dyn_cast<loc::MemRegionVal>(&derived); 881 if (!derivedRegVal) 882 return derived; 883 884 const MemRegion *baseReg = 885 MRMgr.getCXXBaseObjectRegion(baseDecl, derivedRegVal->getRegion()); 886 887 return loc::MemRegionVal(baseReg); 888 } 889 890 SVal RegionStoreManager::evalDynamicCast(SVal base, QualType derivedType, 891 bool &Failed) { 892 Failed = false; 893 894 loc::MemRegionVal *baseRegVal = dyn_cast<loc::MemRegionVal>(&base); 895 if (!baseRegVal) 896 return UnknownVal(); 897 const MemRegion *BaseRegion = baseRegVal->stripCasts(); 898 899 // Assume the derived class is a pointer or a reference to a CXX record. 900 derivedType = derivedType->getPointeeType(); 901 assert(!derivedType.isNull()); 902 const CXXRecordDecl *DerivedDecl = derivedType->getAsCXXRecordDecl(); 903 if (!DerivedDecl && !derivedType->isVoidType()) 904 return UnknownVal(); 905 906 // Drill down the CXXBaseObject chains, which represent upcasts (casts from 907 // derived to base). 908 const MemRegion *SR = BaseRegion; 909 while (const TypedRegion *TSR = dyn_cast_or_null<TypedRegion>(SR)) { 910 QualType BaseType = TSR->getLocationType()->getPointeeType(); 911 assert(!BaseType.isNull()); 912 const CXXRecordDecl *SRDecl = BaseType->getAsCXXRecordDecl(); 913 if (!SRDecl) 914 return UnknownVal(); 915 916 // If found the derived class, the cast succeeds. 917 if (SRDecl == DerivedDecl) 918 return loc::MemRegionVal(TSR); 919 920 // If the region type is a subclass of the derived type. 921 if (!derivedType->isVoidType() && SRDecl->isDerivedFrom(DerivedDecl)) { 922 // This occurs in two cases. 923 // 1) We are processing an upcast. 924 // 2) We are processing a downcast but we jumped directly from the 925 // ancestor to a child of the cast value, so conjure the 926 // appropriate region to represent value (the intermediate node). 927 return loc::MemRegionVal(MRMgr.getCXXBaseObjectRegion(DerivedDecl, 928 BaseRegion)); 929 } 930 931 // If super region is not a parent of derived class, the cast definitely 932 // fails. 933 if (!derivedType->isVoidType() && 934 DerivedDecl->isProvablyNotDerivedFrom(SRDecl)) { 935 Failed = true; 936 return UnknownVal(); 937 } 938 939 if (const CXXBaseObjectRegion *R = dyn_cast<CXXBaseObjectRegion>(TSR)) 940 // Drill down the chain to get the derived classes. 941 SR = R->getSuperRegion(); 942 else { 943 // We reached the bottom of the hierarchy. 944 945 // If this is a cast to void*, return the region. 946 if (derivedType->isVoidType()) 947 return loc::MemRegionVal(TSR); 948 949 // We did not find the derived class. We we must be casting the base to 950 // derived, so the cast should fail. 951 Failed = true; 952 return UnknownVal(); 953 } 954 } 955 956 return UnknownVal(); 957 } 958 959 //===----------------------------------------------------------------------===// 960 // Loading values from regions. 961 //===----------------------------------------------------------------------===// 962 963 Optional<SVal> RegionStoreManager::getDirectBinding(RegionBindings B, 964 const MemRegion *R) { 965 966 if (const SVal *V = lookup(B, R, BindingKey::Direct)) 967 return *V; 968 969 return Optional<SVal>(); 970 } 971 972 Optional<SVal> RegionStoreManager::getDefaultBinding(RegionBindings B, 973 const MemRegion *R) { 974 if (R->isBoundable()) 975 if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) 976 if (TR->getValueType()->isUnionType()) 977 return UnknownVal(); 978 979 if (const SVal *V = lookup(B, R, BindingKey::Default)) 980 return *V; 981 982 return Optional<SVal>(); 983 } 984 985 SVal RegionStoreManager::getBinding(Store store, Loc L, QualType T) { 986 assert(!isa<UnknownVal>(L) && "location unknown"); 987 assert(!isa<UndefinedVal>(L) && "location undefined"); 988 989 // For access to concrete addresses, return UnknownVal. Checks 990 // for null dereferences (and similar errors) are done by checkers, not 991 // the Store. 992 // FIXME: We can consider lazily symbolicating such memory, but we really 993 // should defer this when we can reason easily about symbolicating arrays 994 // of bytes. 995 if (isa<loc::ConcreteInt>(L)) { 996 return UnknownVal(); 997 } 998 if (!isa<loc::MemRegionVal>(L)) { 999 return UnknownVal(); 1000 } 1001 1002 const MemRegion *MR = cast<loc::MemRegionVal>(L).getRegion(); 1003 1004 if (isa<AllocaRegion>(MR) || 1005 isa<SymbolicRegion>(MR) || 1006 isa<CodeTextRegion>(MR)) { 1007 if (T.isNull()) { 1008 if (const TypedRegion *TR = dyn_cast<TypedRegion>(MR)) 1009 T = TR->getLocationType(); 1010 else { 1011 const SymbolicRegion *SR = cast<SymbolicRegion>(MR); 1012 T = SR->getSymbol()->getType(Ctx); 1013 } 1014 } 1015 MR = GetElementZeroRegion(MR, T); 1016 } 1017 1018 // FIXME: Perhaps this method should just take a 'const MemRegion*' argument 1019 // instead of 'Loc', and have the other Loc cases handled at a higher level. 1020 const TypedValueRegion *R = cast<TypedValueRegion>(MR); 1021 QualType RTy = R->getValueType(); 1022 1023 // FIXME: We should eventually handle funny addressing. e.g.: 1024 // 1025 // int x = ...; 1026 // int *p = &x; 1027 // char *q = (char*) p; 1028 // char c = *q; // returns the first byte of 'x'. 1029 // 1030 // Such funny addressing will occur due to layering of regions. 1031 1032 if (RTy->isStructureOrClassType()) 1033 return getBindingForStruct(store, R); 1034 1035 // FIXME: Handle unions. 1036 if (RTy->isUnionType()) 1037 return UnknownVal(); 1038 1039 if (RTy->isArrayType()) 1040 return getBindingForArray(store, R); 1041 1042 // FIXME: handle Vector types. 1043 if (RTy->isVectorType()) 1044 return UnknownVal(); 1045 1046 if (const FieldRegion* FR = dyn_cast<FieldRegion>(R)) 1047 return CastRetrievedVal(getBindingForField(store, FR), FR, T, false); 1048 1049 if (const ElementRegion* ER = dyn_cast<ElementRegion>(R)) { 1050 // FIXME: Here we actually perform an implicit conversion from the loaded 1051 // value to the element type. Eventually we want to compose these values 1052 // more intelligently. For example, an 'element' can encompass multiple 1053 // bound regions (e.g., several bound bytes), or could be a subset of 1054 // a larger value. 1055 return CastRetrievedVal(getBindingForElement(store, ER), ER, T, false); 1056 } 1057 1058 if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) { 1059 // FIXME: Here we actually perform an implicit conversion from the loaded 1060 // value to the ivar type. What we should model is stores to ivars 1061 // that blow past the extent of the ivar. If the address of the ivar is 1062 // reinterpretted, it is possible we stored a different value that could 1063 // fit within the ivar. Either we need to cast these when storing them 1064 // or reinterpret them lazily (as we do here). 1065 return CastRetrievedVal(getBindingForObjCIvar(store, IVR), IVR, T, false); 1066 } 1067 1068 if (const VarRegion *VR = dyn_cast<VarRegion>(R)) { 1069 // FIXME: Here we actually perform an implicit conversion from the loaded 1070 // value to the variable type. What we should model is stores to variables 1071 // that blow past the extent of the variable. If the address of the 1072 // variable is reinterpretted, it is possible we stored a different value 1073 // that could fit within the variable. Either we need to cast these when 1074 // storing them or reinterpret them lazily (as we do here). 1075 return CastRetrievedVal(getBindingForVar(store, VR), VR, T, false); 1076 } 1077 1078 RegionBindings B = GetRegionBindings(store); 1079 const SVal *V = lookup(B, R, BindingKey::Direct); 1080 1081 // Check if the region has a binding. 1082 if (V) 1083 return *V; 1084 1085 // The location does not have a bound value. This means that it has 1086 // the value it had upon its creation and/or entry to the analyzed 1087 // function/method. These are either symbolic values or 'undefined'. 1088 if (R->hasStackNonParametersStorage()) { 1089 // All stack variables are considered to have undefined values 1090 // upon creation. All heap allocated blocks are considered to 1091 // have undefined values as well unless they are explicitly bound 1092 // to specific values. 1093 return UndefinedVal(); 1094 } 1095 1096 // All other values are symbolic. 1097 return svalBuilder.getRegionValueSymbolVal(R); 1098 } 1099 1100 std::pair<Store, const MemRegion *> 1101 RegionStoreManager::GetLazyBinding(RegionBindings B, const MemRegion *R, 1102 const MemRegion *originalRegion) { 1103 1104 if (originalRegion != R) { 1105 if (Optional<SVal> OV = getDefaultBinding(B, R)) { 1106 if (const nonloc::LazyCompoundVal *V = 1107 dyn_cast<nonloc::LazyCompoundVal>(OV.getPointer())) 1108 return std::make_pair(V->getStore(), V->getRegion()); 1109 } 1110 } 1111 1112 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) { 1113 const std::pair<Store, const MemRegion *> &X = 1114 GetLazyBinding(B, ER->getSuperRegion(), originalRegion); 1115 1116 if (X.second) 1117 return std::make_pair(X.first, 1118 MRMgr.getElementRegionWithSuper(ER, X.second)); 1119 } 1120 else if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) { 1121 const std::pair<Store, const MemRegion *> &X = 1122 GetLazyBinding(B, FR->getSuperRegion(), originalRegion); 1123 1124 if (X.second) 1125 return std::make_pair(X.first, 1126 MRMgr.getFieldRegionWithSuper(FR, X.second)); 1127 } 1128 // C++ base object region is another kind of region that we should blast 1129 // through to look for lazy compound value. It is like a field region. 1130 else if (const CXXBaseObjectRegion *baseReg = 1131 dyn_cast<CXXBaseObjectRegion>(R)) { 1132 const std::pair<Store, const MemRegion *> &X = 1133 GetLazyBinding(B, baseReg->getSuperRegion(), originalRegion); 1134 1135 if (X.second) 1136 return std::make_pair(X.first, 1137 MRMgr.getCXXBaseObjectRegionWithSuper(baseReg, X.second)); 1138 } 1139 1140 // The NULL MemRegion indicates an non-existent lazy binding. A NULL Store is 1141 // possible for a valid lazy binding. 1142 return std::make_pair((Store) 0, (const MemRegion *) 0); 1143 } 1144 1145 SVal RegionStoreManager::getBindingForElement(Store store, 1146 const ElementRegion* R) { 1147 // Check if the region has a binding. 1148 RegionBindings B = GetRegionBindings(store); 1149 if (const Optional<SVal> &V = getDirectBinding(B, R)) 1150 return *V; 1151 1152 const MemRegion* superR = R->getSuperRegion(); 1153 1154 // Check if the region is an element region of a string literal. 1155 if (const StringRegion *StrR=dyn_cast<StringRegion>(superR)) { 1156 // FIXME: Handle loads from strings where the literal is treated as 1157 // an integer, e.g., *((unsigned int*)"hello") 1158 QualType T = Ctx.getAsArrayType(StrR->getValueType())->getElementType(); 1159 if (T != Ctx.getCanonicalType(R->getElementType())) 1160 return UnknownVal(); 1161 1162 const StringLiteral *Str = StrR->getStringLiteral(); 1163 SVal Idx = R->getIndex(); 1164 if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&Idx)) { 1165 int64_t i = CI->getValue().getSExtValue(); 1166 // Abort on string underrun. This can be possible by arbitrary 1167 // clients of getBindingForElement(). 1168 if (i < 0) 1169 return UndefinedVal(); 1170 int64_t length = Str->getLength(); 1171 // Technically, only i == length is guaranteed to be null. 1172 // However, such overflows should be caught before reaching this point; 1173 // the only time such an access would be made is if a string literal was 1174 // used to initialize a larger array. 1175 char c = (i >= length) ? '\0' : Str->getCodeUnit(i); 1176 return svalBuilder.makeIntVal(c, T); 1177 } 1178 } 1179 1180 // Check for loads from a code text region. For such loads, just give up. 1181 if (isa<CodeTextRegion>(superR)) 1182 return UnknownVal(); 1183 1184 // Handle the case where we are indexing into a larger scalar object. 1185 // For example, this handles: 1186 // int x = ... 1187 // char *y = &x; 1188 // return *y; 1189 // FIXME: This is a hack, and doesn't do anything really intelligent yet. 1190 const RegionRawOffset &O = R->getAsArrayOffset(); 1191 1192 // If we cannot reason about the offset, return an unknown value. 1193 if (!O.getRegion()) 1194 return UnknownVal(); 1195 1196 if (const TypedValueRegion *baseR = 1197 dyn_cast_or_null<TypedValueRegion>(O.getRegion())) { 1198 QualType baseT = baseR->getValueType(); 1199 if (baseT->isScalarType()) { 1200 QualType elemT = R->getElementType(); 1201 if (elemT->isScalarType()) { 1202 if (Ctx.getTypeSizeInChars(baseT) >= Ctx.getTypeSizeInChars(elemT)) { 1203 if (const Optional<SVal> &V = getDirectBinding(B, superR)) { 1204 if (SymbolRef parentSym = V->getAsSymbol()) 1205 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); 1206 1207 if (V->isUnknownOrUndef()) 1208 return *V; 1209 // Other cases: give up. We are indexing into a larger object 1210 // that has some value, but we don't know how to handle that yet. 1211 return UnknownVal(); 1212 } 1213 } 1214 } 1215 } 1216 } 1217 return getBindingForFieldOrElementCommon(store, R, R->getElementType(), 1218 superR); 1219 } 1220 1221 SVal RegionStoreManager::getBindingForField(Store store, 1222 const FieldRegion* R) { 1223 1224 // Check if the region has a binding. 1225 RegionBindings B = GetRegionBindings(store); 1226 if (const Optional<SVal> &V = getDirectBinding(B, R)) 1227 return *V; 1228 1229 QualType Ty = R->getValueType(); 1230 return getBindingForFieldOrElementCommon(store, R, Ty, R->getSuperRegion()); 1231 } 1232 1233 Optional<SVal> 1234 RegionStoreManager::getBindingForDerivedDefaultValue(RegionBindings B, 1235 const MemRegion *superR, 1236 const TypedValueRegion *R, 1237 QualType Ty) { 1238 1239 if (const Optional<SVal> &D = getDefaultBinding(B, superR)) { 1240 const SVal &val = D.getValue(); 1241 if (SymbolRef parentSym = val.getAsSymbol()) 1242 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); 1243 1244 if (val.isZeroConstant()) 1245 return svalBuilder.makeZeroVal(Ty); 1246 1247 if (val.isUnknownOrUndef()) 1248 return val; 1249 1250 // Lazy bindings are handled later. 1251 if (isa<nonloc::LazyCompoundVal>(val)) 1252 return Optional<SVal>(); 1253 1254 llvm_unreachable("Unknown default value"); 1255 } 1256 1257 return Optional<SVal>(); 1258 } 1259 1260 SVal RegionStoreManager::getLazyBinding(const MemRegion *lazyBindingRegion, 1261 Store lazyBindingStore) { 1262 if (const ElementRegion *ER = dyn_cast<ElementRegion>(lazyBindingRegion)) 1263 return getBindingForElement(lazyBindingStore, ER); 1264 1265 return getBindingForField(lazyBindingStore, 1266 cast<FieldRegion>(lazyBindingRegion)); 1267 } 1268 1269 SVal RegionStoreManager::getBindingForFieldOrElementCommon(Store store, 1270 const TypedValueRegion *R, 1271 QualType Ty, 1272 const MemRegion *superR) { 1273 1274 // At this point we have already checked in either getBindingForElement or 1275 // getBindingForField if 'R' has a direct binding. 1276 RegionBindings B = GetRegionBindings(store); 1277 1278 // Record whether or not we see a symbolic index. That can completely 1279 // be out of scope of our lookup. 1280 bool hasSymbolicIndex = false; 1281 1282 while (superR) { 1283 if (const Optional<SVal> &D = 1284 getBindingForDerivedDefaultValue(B, superR, R, Ty)) 1285 return *D; 1286 1287 if (const ElementRegion *ER = dyn_cast<ElementRegion>(superR)) { 1288 NonLoc index = ER->getIndex(); 1289 if (!index.isConstant()) 1290 hasSymbolicIndex = true; 1291 } 1292 1293 // If our super region is a field or element itself, walk up the region 1294 // hierarchy to see if there is a default value installed in an ancestor. 1295 if (const SubRegion *SR = dyn_cast<SubRegion>(superR)) { 1296 superR = SR->getSuperRegion(); 1297 continue; 1298 } 1299 break; 1300 } 1301 1302 // Lazy binding? 1303 Store lazyBindingStore = NULL; 1304 const MemRegion *lazyBindingRegion = NULL; 1305 llvm::tie(lazyBindingStore, lazyBindingRegion) = GetLazyBinding(B, R, R); 1306 1307 if (lazyBindingRegion) 1308 return getLazyBinding(lazyBindingRegion, lazyBindingStore); 1309 1310 if (R->hasStackNonParametersStorage()) { 1311 if (isa<ElementRegion>(R)) { 1312 // Currently we don't reason specially about Clang-style vectors. Check 1313 // if superR is a vector and if so return Unknown. 1314 if (const TypedValueRegion *typedSuperR = 1315 dyn_cast<TypedValueRegion>(superR)) { 1316 if (typedSuperR->getValueType()->isVectorType()) 1317 return UnknownVal(); 1318 } 1319 } 1320 1321 // FIXME: We also need to take ElementRegions with symbolic indexes into 1322 // account. This case handles both directly accessing an ElementRegion 1323 // with a symbolic offset, but also fields within an element with 1324 // a symbolic offset. 1325 if (hasSymbolicIndex) 1326 return UnknownVal(); 1327 1328 return UndefinedVal(); 1329 } 1330 1331 // All other values are symbolic. 1332 return svalBuilder.getRegionValueSymbolVal(R); 1333 } 1334 1335 SVal RegionStoreManager::getBindingForObjCIvar(Store store, 1336 const ObjCIvarRegion* R) { 1337 1338 // Check if the region has a binding. 1339 RegionBindings B = GetRegionBindings(store); 1340 1341 if (const Optional<SVal> &V = getDirectBinding(B, R)) 1342 return *V; 1343 1344 const MemRegion *superR = R->getSuperRegion(); 1345 1346 // Check if the super region has a default binding. 1347 if (const Optional<SVal> &V = getDefaultBinding(B, superR)) { 1348 if (SymbolRef parentSym = V->getAsSymbol()) 1349 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); 1350 1351 // Other cases: give up. 1352 return UnknownVal(); 1353 } 1354 1355 return getBindingForLazySymbol(R); 1356 } 1357 1358 SVal RegionStoreManager::getBindingForVar(Store store, const VarRegion *R) { 1359 1360 // Check if the region has a binding. 1361 RegionBindings B = GetRegionBindings(store); 1362 1363 if (const Optional<SVal> &V = getDirectBinding(B, R)) 1364 return *V; 1365 1366 // Lazily derive a value for the VarRegion. 1367 const VarDecl *VD = R->getDecl(); 1368 QualType T = VD->getType(); 1369 const MemSpaceRegion *MS = R->getMemorySpace(); 1370 1371 if (isa<UnknownSpaceRegion>(MS) || 1372 isa<StackArgumentsSpaceRegion>(MS)) 1373 return svalBuilder.getRegionValueSymbolVal(R); 1374 1375 if (isa<GlobalsSpaceRegion>(MS)) { 1376 if (isa<NonStaticGlobalSpaceRegion>(MS)) { 1377 // Is 'VD' declared constant? If so, retrieve the constant value. 1378 QualType CT = Ctx.getCanonicalType(T); 1379 if (CT.isConstQualified()) { 1380 const Expr *Init = VD->getInit(); 1381 // Do the null check first, as we want to call 'IgnoreParenCasts'. 1382 if (Init) 1383 if (const IntegerLiteral *IL = 1384 dyn_cast<IntegerLiteral>(Init->IgnoreParenCasts())) { 1385 const nonloc::ConcreteInt &V = svalBuilder.makeIntVal(IL); 1386 return svalBuilder.evalCast(V, Init->getType(), IL->getType()); 1387 } 1388 } 1389 1390 if (const Optional<SVal> &V 1391 = getBindingForDerivedDefaultValue(B, MS, R, CT)) 1392 return V.getValue(); 1393 1394 return svalBuilder.getRegionValueSymbolVal(R); 1395 } 1396 1397 if (T->isIntegerType()) 1398 return svalBuilder.makeIntVal(0, T); 1399 if (T->isPointerType()) 1400 return svalBuilder.makeNull(); 1401 1402 return UnknownVal(); 1403 } 1404 1405 return UndefinedVal(); 1406 } 1407 1408 SVal RegionStoreManager::getBindingForLazySymbol(const TypedValueRegion *R) { 1409 // All other values are symbolic. 1410 return svalBuilder.getRegionValueSymbolVal(R); 1411 } 1412 1413 SVal RegionStoreManager::getBindingForStruct(Store store, 1414 const TypedValueRegion* R) { 1415 assert(R->getValueType()->isStructureOrClassType()); 1416 return svalBuilder.makeLazyCompoundVal(StoreRef(store, *this), R); 1417 } 1418 1419 SVal RegionStoreManager::getBindingForArray(Store store, 1420 const TypedValueRegion * R) { 1421 assert(Ctx.getAsConstantArrayType(R->getValueType())); 1422 return svalBuilder.makeLazyCompoundVal(StoreRef(store, *this), R); 1423 } 1424 1425 bool RegionStoreManager::includedInBindings(Store store, 1426 const MemRegion *region) const { 1427 RegionBindings B = GetRegionBindings(store); 1428 region = region->getBaseRegion(); 1429 1430 for (RegionBindings::iterator it = B.begin(), ei = B.end(); it != ei; ++it) { 1431 const BindingKey &K = it.getKey(); 1432 if (region == K.getRegion()) 1433 return true; 1434 const SVal &D = it.getData(); 1435 if (const MemRegion *r = D.getAsRegion()) 1436 if (r == region) 1437 return true; 1438 } 1439 return false; 1440 } 1441 1442 //===----------------------------------------------------------------------===// 1443 // Binding values to regions. 1444 //===----------------------------------------------------------------------===// 1445 1446 StoreRef RegionStoreManager::Remove(Store store, Loc L) { 1447 if (isa<loc::MemRegionVal>(L)) 1448 if (const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion()) 1449 return StoreRef(removeBinding(GetRegionBindings(store), 1450 R).getRootWithoutRetain(), 1451 *this); 1452 1453 return StoreRef(store, *this); 1454 } 1455 1456 StoreRef RegionStoreManager::Bind(Store store, Loc L, SVal V) { 1457 if (isa<loc::ConcreteInt>(L)) 1458 return StoreRef(store, *this); 1459 1460 // If we get here, the location should be a region. 1461 const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion(); 1462 1463 // Check if the region is a struct region. 1464 if (const TypedValueRegion* TR = dyn_cast<TypedValueRegion>(R)) 1465 if (TR->getValueType()->isStructureOrClassType()) 1466 return BindStruct(store, TR, V); 1467 1468 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) { 1469 if (ER->getIndex().isZeroConstant()) { 1470 if (const TypedValueRegion *superR = 1471 dyn_cast<TypedValueRegion>(ER->getSuperRegion())) { 1472 QualType superTy = superR->getValueType(); 1473 // For now, just invalidate the fields of the struct/union/class. 1474 // This is for test rdar_test_7185607 in misc-ps-region-store.m. 1475 // FIXME: Precisely handle the fields of the record. 1476 if (superTy->isStructureOrClassType()) 1477 return KillStruct(store, superR, UnknownVal()); 1478 } 1479 } 1480 } 1481 else if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) { 1482 // Binding directly to a symbolic region should be treated as binding 1483 // to element 0. 1484 QualType T = SR->getSymbol()->getType(Ctx); 1485 1486 // FIXME: Is this the right way to handle symbols that are references? 1487 if (const PointerType *PT = T->getAs<PointerType>()) 1488 T = PT->getPointeeType(); 1489 else 1490 T = T->getAs<ReferenceType>()->getPointeeType(); 1491 1492 R = GetElementZeroRegion(SR, T); 1493 } 1494 1495 // Perform the binding. 1496 RegionBindings B = GetRegionBindings(store); 1497 return StoreRef(addBinding(B, R, BindingKey::Direct, 1498 V).getRootWithoutRetain(), *this); 1499 } 1500 1501 StoreRef RegionStoreManager::BindDecl(Store store, const VarRegion *VR, 1502 SVal InitVal) { 1503 1504 QualType T = VR->getDecl()->getType(); 1505 1506 if (T->isArrayType()) 1507 return BindArray(store, VR, InitVal); 1508 if (T->isStructureOrClassType()) 1509 return BindStruct(store, VR, InitVal); 1510 1511 return Bind(store, svalBuilder.makeLoc(VR), InitVal); 1512 } 1513 1514 // FIXME: this method should be merged into Bind(). 1515 StoreRef RegionStoreManager::BindCompoundLiteral(Store store, 1516 const CompoundLiteralExpr *CL, 1517 const LocationContext *LC, 1518 SVal V) { 1519 return Bind(store, loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL, LC)), 1520 V); 1521 } 1522 1523 StoreRef RegionStoreManager::setImplicitDefaultValue(Store store, 1524 const MemRegion *R, 1525 QualType T) { 1526 RegionBindings B = GetRegionBindings(store); 1527 SVal V; 1528 1529 if (Loc::isLocType(T)) 1530 V = svalBuilder.makeNull(); 1531 else if (T->isIntegerType()) 1532 V = svalBuilder.makeZeroVal(T); 1533 else if (T->isStructureOrClassType() || T->isArrayType()) { 1534 // Set the default value to a zero constant when it is a structure 1535 // or array. The type doesn't really matter. 1536 V = svalBuilder.makeZeroVal(Ctx.IntTy); 1537 } 1538 else { 1539 // We can't represent values of this type, but we still need to set a value 1540 // to record that the region has been initialized. 1541 // If this assertion ever fires, a new case should be added above -- we 1542 // should know how to default-initialize any value we can symbolicate. 1543 assert(!SymbolManager::canSymbolicate(T) && "This type is representable"); 1544 V = UnknownVal(); 1545 } 1546 1547 return StoreRef(addBinding(B, R, BindingKey::Default, 1548 V).getRootWithoutRetain(), *this); 1549 } 1550 1551 StoreRef RegionStoreManager::BindArray(Store store, const TypedValueRegion* R, 1552 SVal Init) { 1553 1554 const ArrayType *AT =cast<ArrayType>(Ctx.getCanonicalType(R->getValueType())); 1555 QualType ElementTy = AT->getElementType(); 1556 Optional<uint64_t> Size; 1557 1558 if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(AT)) 1559 Size = CAT->getSize().getZExtValue(); 1560 1561 // Check if the init expr is a string literal. 1562 if (loc::MemRegionVal *MRV = dyn_cast<loc::MemRegionVal>(&Init)) { 1563 const StringRegion *S = cast<StringRegion>(MRV->getRegion()); 1564 1565 // Treat the string as a lazy compound value. 1566 nonloc::LazyCompoundVal LCV = 1567 cast<nonloc::LazyCompoundVal>(svalBuilder. 1568 makeLazyCompoundVal(StoreRef(store, *this), S)); 1569 return CopyLazyBindings(LCV, store, R); 1570 } 1571 1572 // Handle lazy compound values. 1573 if (nonloc::LazyCompoundVal *LCV = dyn_cast<nonloc::LazyCompoundVal>(&Init)) 1574 return CopyLazyBindings(*LCV, store, R); 1575 1576 // Remaining case: explicit compound values. 1577 1578 if (Init.isUnknown()) 1579 return setImplicitDefaultValue(store, R, ElementTy); 1580 1581 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(Init); 1582 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); 1583 uint64_t i = 0; 1584 1585 StoreRef newStore(store, *this); 1586 for (; Size.hasValue() ? i < Size.getValue() : true ; ++i, ++VI) { 1587 // The init list might be shorter than the array length. 1588 if (VI == VE) 1589 break; 1590 1591 const NonLoc &Idx = svalBuilder.makeArrayIndex(i); 1592 const ElementRegion *ER = MRMgr.getElementRegion(ElementTy, Idx, R, Ctx); 1593 1594 if (ElementTy->isStructureOrClassType()) 1595 newStore = BindStruct(newStore.getStore(), ER, *VI); 1596 else if (ElementTy->isArrayType()) 1597 newStore = BindArray(newStore.getStore(), ER, *VI); 1598 else 1599 newStore = Bind(newStore.getStore(), svalBuilder.makeLoc(ER), *VI); 1600 } 1601 1602 // If the init list is shorter than the array length, set the 1603 // array default value. 1604 if (Size.hasValue() && i < Size.getValue()) 1605 newStore = setImplicitDefaultValue(newStore.getStore(), R, ElementTy); 1606 1607 return newStore; 1608 } 1609 1610 StoreRef RegionStoreManager::BindStruct(Store store, const TypedValueRegion* R, 1611 SVal V) { 1612 1613 if (!Features.supportsFields()) 1614 return StoreRef(store, *this); 1615 1616 QualType T = R->getValueType(); 1617 assert(T->isStructureOrClassType()); 1618 1619 const RecordType* RT = T->getAs<RecordType>(); 1620 RecordDecl *RD = RT->getDecl(); 1621 1622 if (!RD->isCompleteDefinition()) 1623 return StoreRef(store, *this); 1624 1625 // Handle lazy compound values. 1626 if (const nonloc::LazyCompoundVal *LCV=dyn_cast<nonloc::LazyCompoundVal>(&V)) 1627 return CopyLazyBindings(*LCV, store, R); 1628 1629 // We may get non-CompoundVal accidentally due to imprecise cast logic or 1630 // that we are binding symbolic struct value. Kill the field values, and if 1631 // the value is symbolic go and bind it as a "default" binding. 1632 if (V.isUnknown() || !isa<nonloc::CompoundVal>(V)) { 1633 SVal SV = isa<nonloc::SymbolVal>(V) ? V : UnknownVal(); 1634 return KillStruct(store, R, SV); 1635 } 1636 1637 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V); 1638 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); 1639 1640 RecordDecl::field_iterator FI, FE; 1641 StoreRef newStore(store, *this); 1642 1643 for (FI = RD->field_begin(), FE = RD->field_end(); FI != FE; ++FI) { 1644 1645 if (VI == VE) 1646 break; 1647 1648 // Skip any unnamed bitfields to stay in sync with the initializers. 1649 if ((*FI)->isUnnamedBitfield()) 1650 continue; 1651 1652 QualType FTy = (*FI)->getType(); 1653 const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R); 1654 1655 if (FTy->isArrayType()) 1656 newStore = BindArray(newStore.getStore(), FR, *VI); 1657 else if (FTy->isStructureOrClassType()) 1658 newStore = BindStruct(newStore.getStore(), FR, *VI); 1659 else 1660 newStore = Bind(newStore.getStore(), svalBuilder.makeLoc(FR), *VI); 1661 ++VI; 1662 } 1663 1664 // There may be fewer values in the initialize list than the fields of struct. 1665 if (FI != FE) { 1666 RegionBindings B = GetRegionBindings(newStore.getStore()); 1667 B = addBinding(B, R, BindingKey::Default, svalBuilder.makeIntVal(0, false)); 1668 newStore = StoreRef(B.getRootWithoutRetain(), *this); 1669 } 1670 1671 return newStore; 1672 } 1673 1674 StoreRef RegionStoreManager::KillStruct(Store store, const TypedRegion* R, 1675 SVal DefaultVal) { 1676 BindingKey key = BindingKey::Make(R, BindingKey::Default); 1677 1678 // The BindingKey may be "invalid" if we cannot handle the region binding 1679 // explicitly. One example is something like array[index], where index 1680 // is a symbolic value. In such cases, we want to invalidate the entire 1681 // array, as the index assignment could have been to any element. In 1682 // the case of nested symbolic indices, we need to march up the region 1683 // hierarchy untile we reach a region whose binding we can reason about. 1684 const SubRegion *subReg = R; 1685 1686 while (!key.isValid()) { 1687 if (const SubRegion *tmp = dyn_cast<SubRegion>(subReg->getSuperRegion())) { 1688 subReg = tmp; 1689 key = BindingKey::Make(tmp, BindingKey::Default); 1690 } 1691 else 1692 break; 1693 } 1694 1695 // Remove the old bindings, using 'subReg' as the root of all regions 1696 // we will invalidate. 1697 RegionBindings B = GetRegionBindings(store); 1698 OwningPtr<RegionStoreSubRegionMap> 1699 SubRegions(getRegionStoreSubRegionMap(store)); 1700 RemoveSubRegionBindings(B, subReg, *SubRegions); 1701 1702 // Set the default value of the struct region to "unknown". 1703 if (!key.isValid()) 1704 return StoreRef(B.getRootWithoutRetain(), *this); 1705 1706 return StoreRef(addBinding(B, key, DefaultVal).getRootWithoutRetain(), *this); 1707 } 1708 1709 StoreRef RegionStoreManager::CopyLazyBindings(nonloc::LazyCompoundVal V, 1710 Store store, 1711 const TypedRegion *R) { 1712 1713 // Nuke the old bindings stemming from R. 1714 RegionBindings B = GetRegionBindings(store); 1715 1716 OwningPtr<RegionStoreSubRegionMap> 1717 SubRegions(getRegionStoreSubRegionMap(store)); 1718 1719 // B and DVM are updated after the call to RemoveSubRegionBindings. 1720 RemoveSubRegionBindings(B, R, *SubRegions.get()); 1721 1722 // Now copy the bindings. This amounts to just binding 'V' to 'R'. This 1723 // results in a zero-copy algorithm. 1724 return StoreRef(addBinding(B, R, BindingKey::Default, 1725 V).getRootWithoutRetain(), *this); 1726 } 1727 1728 //===----------------------------------------------------------------------===// 1729 // "Raw" retrievals and bindings. 1730 //===----------------------------------------------------------------------===// 1731 1732 1733 RegionBindings RegionStoreManager::addBinding(RegionBindings B, BindingKey K, 1734 SVal V) { 1735 if (!K.isValid()) 1736 return B; 1737 return RBFactory.add(B, K, V); 1738 } 1739 1740 RegionBindings RegionStoreManager::addBinding(RegionBindings B, 1741 const MemRegion *R, 1742 BindingKey::Kind k, SVal V) { 1743 return addBinding(B, BindingKey::Make(R, k), V); 1744 } 1745 1746 const SVal *RegionStoreManager::lookup(RegionBindings B, BindingKey K) { 1747 if (!K.isValid()) 1748 return NULL; 1749 return B.lookup(K); 1750 } 1751 1752 const SVal *RegionStoreManager::lookup(RegionBindings B, 1753 const MemRegion *R, 1754 BindingKey::Kind k) { 1755 return lookup(B, BindingKey::Make(R, k)); 1756 } 1757 1758 RegionBindings RegionStoreManager::removeBinding(RegionBindings B, 1759 BindingKey K) { 1760 if (!K.isValid()) 1761 return B; 1762 return RBFactory.remove(B, K); 1763 } 1764 1765 RegionBindings RegionStoreManager::removeBinding(RegionBindings B, 1766 const MemRegion *R, 1767 BindingKey::Kind k){ 1768 return removeBinding(B, BindingKey::Make(R, k)); 1769 } 1770 1771 //===----------------------------------------------------------------------===// 1772 // State pruning. 1773 //===----------------------------------------------------------------------===// 1774 1775 namespace { 1776 class removeDeadBindingsWorker : 1777 public ClusterAnalysis<removeDeadBindingsWorker> { 1778 SmallVector<const SymbolicRegion*, 12> Postponed; 1779 SymbolReaper &SymReaper; 1780 const StackFrameContext *CurrentLCtx; 1781 1782 public: 1783 removeDeadBindingsWorker(RegionStoreManager &rm, 1784 ProgramStateManager &stateMgr, 1785 RegionBindings b, SymbolReaper &symReaper, 1786 const StackFrameContext *LCtx) 1787 : ClusterAnalysis<removeDeadBindingsWorker>(rm, stateMgr, b, 1788 /* includeGlobals = */ false), 1789 SymReaper(symReaper), CurrentLCtx(LCtx) {} 1790 1791 // Called by ClusterAnalysis. 1792 void VisitAddedToCluster(const MemRegion *baseR, RegionCluster &C); 1793 void VisitCluster(const MemRegion *baseR, BindingKey *I, BindingKey *E); 1794 1795 void VisitBindingKey(BindingKey K); 1796 bool UpdatePostponed(); 1797 void VisitBinding(SVal V); 1798 }; 1799 } 1800 1801 void removeDeadBindingsWorker::VisitAddedToCluster(const MemRegion *baseR, 1802 RegionCluster &C) { 1803 1804 if (const VarRegion *VR = dyn_cast<VarRegion>(baseR)) { 1805 if (SymReaper.isLive(VR)) 1806 AddToWorkList(baseR, C); 1807 1808 return; 1809 } 1810 1811 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) { 1812 if (SymReaper.isLive(SR->getSymbol())) 1813 AddToWorkList(SR, C); 1814 else 1815 Postponed.push_back(SR); 1816 1817 return; 1818 } 1819 1820 if (isa<NonStaticGlobalSpaceRegion>(baseR)) { 1821 AddToWorkList(baseR, C); 1822 return; 1823 } 1824 1825 // CXXThisRegion in the current or parent location context is live. 1826 if (const CXXThisRegion *TR = dyn_cast<CXXThisRegion>(baseR)) { 1827 const StackArgumentsSpaceRegion *StackReg = 1828 cast<StackArgumentsSpaceRegion>(TR->getSuperRegion()); 1829 const StackFrameContext *RegCtx = StackReg->getStackFrame(); 1830 if (RegCtx == CurrentLCtx || RegCtx->isParentOf(CurrentLCtx)) 1831 AddToWorkList(TR, C); 1832 } 1833 } 1834 1835 void removeDeadBindingsWorker::VisitCluster(const MemRegion *baseR, 1836 BindingKey *I, BindingKey *E) { 1837 for ( ; I != E; ++I) 1838 VisitBindingKey(*I); 1839 } 1840 1841 void removeDeadBindingsWorker::VisitBinding(SVal V) { 1842 // Is it a LazyCompoundVal? All referenced regions are live as well. 1843 if (const nonloc::LazyCompoundVal *LCS = 1844 dyn_cast<nonloc::LazyCompoundVal>(&V)) { 1845 1846 const MemRegion *LazyR = LCS->getRegion(); 1847 RegionBindings B = RegionStoreManager::GetRegionBindings(LCS->getStore()); 1848 for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){ 1849 const SubRegion *baseR = dyn_cast<SubRegion>(RI.getKey().getRegion()); 1850 if (baseR && baseR->isSubRegionOf(LazyR)) 1851 VisitBinding(RI.getData()); 1852 } 1853 return; 1854 } 1855 1856 // If V is a region, then add it to the worklist. 1857 if (const MemRegion *R = V.getAsRegion()) 1858 AddToWorkList(R); 1859 1860 // Update the set of live symbols. 1861 for (SymExpr::symbol_iterator SI = V.symbol_begin(), SE = V.symbol_end(); 1862 SI!=SE; ++SI) 1863 SymReaper.markLive(*SI); 1864 } 1865 1866 void removeDeadBindingsWorker::VisitBindingKey(BindingKey K) { 1867 const MemRegion *R = K.getRegion(); 1868 1869 // Mark this region "live" by adding it to the worklist. This will cause 1870 // use to visit all regions in the cluster (if we haven't visited them 1871 // already). 1872 if (AddToWorkList(R)) { 1873 // Mark the symbol for any live SymbolicRegion as "live". This means we 1874 // should continue to track that symbol. 1875 if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(R)) 1876 SymReaper.markLive(SymR->getSymbol()); 1877 1878 // For BlockDataRegions, enqueue the VarRegions for variables marked 1879 // with __block (passed-by-reference). 1880 // via BlockDeclRefExprs. 1881 if (const BlockDataRegion *BD = dyn_cast<BlockDataRegion>(R)) { 1882 for (BlockDataRegion::referenced_vars_iterator 1883 RI = BD->referenced_vars_begin(), RE = BD->referenced_vars_end(); 1884 RI != RE; ++RI) { 1885 if ((*RI)->getDecl()->getAttr<BlocksAttr>()) 1886 AddToWorkList(*RI); 1887 } 1888 1889 // No possible data bindings on a BlockDataRegion. 1890 return; 1891 } 1892 } 1893 1894 // Visit the data binding for K. 1895 if (const SVal *V = RM.lookup(B, K)) 1896 VisitBinding(*V); 1897 } 1898 1899 bool removeDeadBindingsWorker::UpdatePostponed() { 1900 // See if any postponed SymbolicRegions are actually live now, after 1901 // having done a scan. 1902 bool changed = false; 1903 1904 for (SmallVectorImpl<const SymbolicRegion*>::iterator 1905 I = Postponed.begin(), E = Postponed.end() ; I != E ; ++I) { 1906 if (const SymbolicRegion *SR = cast_or_null<SymbolicRegion>(*I)) { 1907 if (SymReaper.isLive(SR->getSymbol())) { 1908 changed |= AddToWorkList(SR); 1909 *I = NULL; 1910 } 1911 } 1912 } 1913 1914 return changed; 1915 } 1916 1917 StoreRef RegionStoreManager::removeDeadBindings(Store store, 1918 const StackFrameContext *LCtx, 1919 SymbolReaper& SymReaper) { 1920 RegionBindings B = GetRegionBindings(store); 1921 removeDeadBindingsWorker W(*this, StateMgr, B, SymReaper, LCtx); 1922 W.GenerateClusters(); 1923 1924 // Enqueue the region roots onto the worklist. 1925 for (SymbolReaper::region_iterator I = SymReaper.region_begin(), 1926 E = SymReaper.region_end(); I != E; ++I) { 1927 W.AddToWorkList(*I); 1928 } 1929 1930 do W.RunWorkList(); while (W.UpdatePostponed()); 1931 1932 // We have now scanned the store, marking reachable regions and symbols 1933 // as live. We now remove all the regions that are dead from the store 1934 // as well as update DSymbols with the set symbols that are now dead. 1935 for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) { 1936 const BindingKey &K = I.getKey(); 1937 1938 // If the cluster has been visited, we know the region has been marked. 1939 if (W.isVisited(K.getRegion())) 1940 continue; 1941 1942 // Remove the dead entry. 1943 B = removeBinding(B, K); 1944 1945 // Mark all non-live symbols that this binding references as dead. 1946 if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(K.getRegion())) 1947 SymReaper.maybeDead(SymR->getSymbol()); 1948 1949 SVal X = I.getData(); 1950 SymExpr::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end(); 1951 for (; SI != SE; ++SI) 1952 SymReaper.maybeDead(*SI); 1953 } 1954 1955 return StoreRef(B.getRootWithoutRetain(), *this); 1956 } 1957 1958 1959 StoreRef RegionStoreManager::enterStackFrame(ProgramStateRef state, 1960 const LocationContext *callerCtx, 1961 const StackFrameContext *calleeCtx) 1962 { 1963 FunctionDecl const *FD = cast<FunctionDecl>(calleeCtx->getDecl()); 1964 FunctionDecl::param_const_iterator PI = FD->param_begin(), 1965 PE = FD->param_end(); 1966 StoreRef store = StoreRef(state->getStore(), *this); 1967 1968 if (CallExpr const *CE = dyn_cast<CallExpr>(calleeCtx->getCallSite())) { 1969 CallExpr::const_arg_iterator AI = CE->arg_begin(), AE = CE->arg_end(); 1970 1971 // Copy the arg expression value to the arg variables. We check that 1972 // PI != PE because the actual number of arguments may be different than 1973 // the function declaration. 1974 for (; AI != AE && PI != PE; ++AI, ++PI) { 1975 SVal ArgVal = state->getSVal(*AI, callerCtx); 1976 store = Bind(store.getStore(), 1977 svalBuilder.makeLoc(MRMgr.getVarRegion(*PI, calleeCtx)), 1978 ArgVal); 1979 } 1980 } else if (const CXXConstructExpr *CE = 1981 dyn_cast<CXXConstructExpr>(calleeCtx->getCallSite())) { 1982 CXXConstructExpr::const_arg_iterator AI = CE->arg_begin(), 1983 AE = CE->arg_end(); 1984 1985 // Copy the arg expression value to the arg variables. 1986 for (; AI != AE; ++AI, ++PI) { 1987 SVal ArgVal = state->getSVal(*AI, callerCtx); 1988 store = Bind(store.getStore(), 1989 svalBuilder.makeLoc(MRMgr.getVarRegion(*PI, calleeCtx)), 1990 ArgVal); 1991 } 1992 } else 1993 assert(isa<CXXDestructorDecl>(calleeCtx->getDecl())); 1994 1995 return store; 1996 } 1997 1998 //===----------------------------------------------------------------------===// 1999 // Utility methods. 2000 //===----------------------------------------------------------------------===// 2001 2002 void RegionStoreManager::print(Store store, raw_ostream &OS, 2003 const char* nl, const char *sep) { 2004 RegionBindings B = GetRegionBindings(store); 2005 OS << "Store (direct and default bindings):" << nl; 2006 2007 for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) 2008 OS << ' ' << I.getKey() << " : " << I.getData() << nl; 2009 } 2010