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