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