RegionStore.cpp revision 3133f79cf451e6302dd05262b4bb53a3e4fd6300
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 1198 RegionBindings B = GetRegionBindings(store); 1199 1200 while (superR) { 1201 if (const Optional<SVal> &D = 1202 getBindingForDerivedDefaultValue(B, superR, R, Ty)) 1203 return *D; 1204 1205 // If our super region is a field or element itself, walk up the region 1206 // hierarchy to see if there is a default value installed in an ancestor. 1207 if (const SubRegion *SR = dyn_cast<SubRegion>(superR)) { 1208 superR = SR->getSuperRegion(); 1209 continue; 1210 } 1211 break; 1212 } 1213 1214 // Lazy binding? 1215 Store lazyBindingStore = NULL; 1216 const MemRegion *lazyBindingRegion = NULL; 1217 llvm::tie(lazyBindingStore, lazyBindingRegion) = GetLazyBinding(B, R, R); 1218 1219 if (lazyBindingRegion) 1220 return getLazyBinding(lazyBindingRegion, lazyBindingStore); 1221 1222 if (R->hasStackNonParametersStorage()) { 1223 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) { 1224 // Currently we don't reason specially about Clang-style vectors. Check 1225 // if superR is a vector and if so return Unknown. 1226 if (const TypedValueRegion *typedSuperR = 1227 dyn_cast<TypedValueRegion>(superR)) { 1228 if (typedSuperR->getValueType()->isVectorType()) 1229 return UnknownVal(); 1230 } 1231 1232 // FIXME: We also need to take ElementRegions with symbolic indexes into 1233 // account. 1234 if (!ER->getIndex().isConstant()) 1235 return UnknownVal(); 1236 } 1237 1238 return UndefinedVal(); 1239 } 1240 1241 // All other values are symbolic. 1242 return svalBuilder.getRegionValueSymbolVal(R); 1243} 1244 1245SVal RegionStoreManager::getBindingForObjCIvar(Store store, 1246 const ObjCIvarRegion* R) { 1247 1248 // Check if the region has a binding. 1249 RegionBindings B = GetRegionBindings(store); 1250 1251 if (const Optional<SVal> &V = getDirectBinding(B, R)) 1252 return *V; 1253 1254 const MemRegion *superR = R->getSuperRegion(); 1255 1256 // Check if the super region has a default binding. 1257 if (const Optional<SVal> &V = getDefaultBinding(B, superR)) { 1258 if (SymbolRef parentSym = V->getAsSymbol()) 1259 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); 1260 1261 // Other cases: give up. 1262 return UnknownVal(); 1263 } 1264 1265 return getBindingForLazySymbol(R); 1266} 1267 1268SVal RegionStoreManager::getBindingForVar(Store store, const VarRegion *R) { 1269 1270 // Check if the region has a binding. 1271 RegionBindings B = GetRegionBindings(store); 1272 1273 if (const Optional<SVal> &V = getDirectBinding(B, R)) 1274 return *V; 1275 1276 // Lazily derive a value for the VarRegion. 1277 const VarDecl *VD = R->getDecl(); 1278 QualType T = VD->getType(); 1279 const MemSpaceRegion *MS = R->getMemorySpace(); 1280 1281 if (isa<UnknownSpaceRegion>(MS) || 1282 isa<StackArgumentsSpaceRegion>(MS)) 1283 return svalBuilder.getRegionValueSymbolVal(R); 1284 1285 if (isa<GlobalsSpaceRegion>(MS)) { 1286 if (isa<NonStaticGlobalSpaceRegion>(MS)) { 1287 // Is 'VD' declared constant? If so, retrieve the constant value. 1288 QualType CT = Ctx.getCanonicalType(T); 1289 if (CT.isConstQualified()) { 1290 const Expr *Init = VD->getInit(); 1291 // Do the null check first, as we want to call 'IgnoreParenCasts'. 1292 if (Init) 1293 if (const IntegerLiteral *IL = 1294 dyn_cast<IntegerLiteral>(Init->IgnoreParenCasts())) { 1295 const nonloc::ConcreteInt &V = svalBuilder.makeIntVal(IL); 1296 return svalBuilder.evalCast(V, Init->getType(), IL->getType()); 1297 } 1298 } 1299 1300 if (const Optional<SVal> &V 1301 = getBindingForDerivedDefaultValue(B, MS, R, CT)) 1302 return V.getValue(); 1303 1304 return svalBuilder.getRegionValueSymbolVal(R); 1305 } 1306 1307 if (T->isIntegerType()) 1308 return svalBuilder.makeIntVal(0, T); 1309 if (T->isPointerType()) 1310 return svalBuilder.makeNull(); 1311 1312 return UnknownVal(); 1313 } 1314 1315 return UndefinedVal(); 1316} 1317 1318SVal RegionStoreManager::getBindingForLazySymbol(const TypedValueRegion *R) { 1319 // All other values are symbolic. 1320 return svalBuilder.getRegionValueSymbolVal(R); 1321} 1322 1323SVal RegionStoreManager::getBindingForStruct(Store store, 1324 const TypedValueRegion* R) { 1325 assert(R->getValueType()->isStructureOrClassType()); 1326 return svalBuilder.makeLazyCompoundVal(StoreRef(store, *this), R); 1327} 1328 1329SVal RegionStoreManager::getBindingForArray(Store store, 1330 const TypedValueRegion * R) { 1331 assert(Ctx.getAsConstantArrayType(R->getValueType())); 1332 return svalBuilder.makeLazyCompoundVal(StoreRef(store, *this), R); 1333} 1334 1335bool RegionStoreManager::includedInBindings(Store store, 1336 const MemRegion *region) const { 1337 RegionBindings B = GetRegionBindings(store); 1338 region = region->getBaseRegion(); 1339 1340 for (RegionBindings::iterator it = B.begin(), ei = B.end(); it != ei; ++it) { 1341 const BindingKey &K = it.getKey(); 1342 if (region == K.getRegion()) 1343 return true; 1344 const SVal &D = it.getData(); 1345 if (const MemRegion *r = D.getAsRegion()) 1346 if (r == region) 1347 return true; 1348 } 1349 return false; 1350} 1351 1352//===----------------------------------------------------------------------===// 1353// Binding values to regions. 1354//===----------------------------------------------------------------------===// 1355 1356StoreRef RegionStoreManager::Remove(Store store, Loc L) { 1357 if (isa<loc::MemRegionVal>(L)) 1358 if (const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion()) 1359 return StoreRef(removeBinding(GetRegionBindings(store), 1360 R).getRootWithoutRetain(), 1361 *this); 1362 1363 return StoreRef(store, *this); 1364} 1365 1366StoreRef RegionStoreManager::Bind(Store store, Loc L, SVal V) { 1367 if (isa<loc::ConcreteInt>(L)) 1368 return StoreRef(store, *this); 1369 1370 // If we get here, the location should be a region. 1371 const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion(); 1372 1373 // Check if the region is a struct region. 1374 if (const TypedValueRegion* TR = dyn_cast<TypedValueRegion>(R)) 1375 if (TR->getValueType()->isStructureOrClassType()) 1376 return BindStruct(store, TR, V); 1377 1378 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) { 1379 if (ER->getIndex().isZeroConstant()) { 1380 if (const TypedValueRegion *superR = 1381 dyn_cast<TypedValueRegion>(ER->getSuperRegion())) { 1382 QualType superTy = superR->getValueType(); 1383 // For now, just invalidate the fields of the struct/union/class. 1384 // This is for test rdar_test_7185607 in misc-ps-region-store.m. 1385 // FIXME: Precisely handle the fields of the record. 1386 if (superTy->isStructureOrClassType()) 1387 return KillStruct(store, superR, UnknownVal()); 1388 } 1389 } 1390 } 1391 else if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) { 1392 // Binding directly to a symbolic region should be treated as binding 1393 // to element 0. 1394 QualType T = SR->getSymbol()->getType(Ctx); 1395 1396 // FIXME: Is this the right way to handle symbols that are references? 1397 if (const PointerType *PT = T->getAs<PointerType>()) 1398 T = PT->getPointeeType(); 1399 else 1400 T = T->getAs<ReferenceType>()->getPointeeType(); 1401 1402 R = GetElementZeroRegion(SR, T); 1403 } 1404 1405 // Perform the binding. 1406 RegionBindings B = GetRegionBindings(store); 1407 return StoreRef(addBinding(B, R, BindingKey::Direct, 1408 V).getRootWithoutRetain(), *this); 1409} 1410 1411StoreRef RegionStoreManager::BindDecl(Store store, const VarRegion *VR, 1412 SVal InitVal) { 1413 1414 QualType T = VR->getDecl()->getType(); 1415 1416 if (T->isArrayType()) 1417 return BindArray(store, VR, InitVal); 1418 if (T->isStructureOrClassType()) 1419 return BindStruct(store, VR, InitVal); 1420 1421 return Bind(store, svalBuilder.makeLoc(VR), InitVal); 1422} 1423 1424// FIXME: this method should be merged into Bind(). 1425StoreRef RegionStoreManager::BindCompoundLiteral(Store store, 1426 const CompoundLiteralExpr *CL, 1427 const LocationContext *LC, 1428 SVal V) { 1429 return Bind(store, loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL, LC)), 1430 V); 1431} 1432 1433StoreRef RegionStoreManager::setImplicitDefaultValue(Store store, 1434 const MemRegion *R, 1435 QualType T) { 1436 RegionBindings B = GetRegionBindings(store); 1437 SVal V; 1438 1439 if (Loc::isLocType(T)) 1440 V = svalBuilder.makeNull(); 1441 else if (T->isIntegerType()) 1442 V = svalBuilder.makeZeroVal(T); 1443 else if (T->isStructureOrClassType() || T->isArrayType()) { 1444 // Set the default value to a zero constant when it is a structure 1445 // or array. The type doesn't really matter. 1446 V = svalBuilder.makeZeroVal(Ctx.IntTy); 1447 } 1448 else { 1449 // We can't represent values of this type, but we still need to set a value 1450 // to record that the region has been initialized. 1451 // If this assertion ever fires, a new case should be added above -- we 1452 // should know how to default-initialize any value we can symbolicate. 1453 assert(!SymbolManager::canSymbolicate(T) && "This type is representable"); 1454 V = UnknownVal(); 1455 } 1456 1457 return StoreRef(addBinding(B, R, BindingKey::Default, 1458 V).getRootWithoutRetain(), *this); 1459} 1460 1461StoreRef RegionStoreManager::BindArray(Store store, const TypedValueRegion* R, 1462 SVal Init) { 1463 1464 const ArrayType *AT =cast<ArrayType>(Ctx.getCanonicalType(R->getValueType())); 1465 QualType ElementTy = AT->getElementType(); 1466 Optional<uint64_t> Size; 1467 1468 if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(AT)) 1469 Size = CAT->getSize().getZExtValue(); 1470 1471 // Check if the init expr is a string literal. 1472 if (loc::MemRegionVal *MRV = dyn_cast<loc::MemRegionVal>(&Init)) { 1473 const StringRegion *S = cast<StringRegion>(MRV->getRegion()); 1474 1475 // Treat the string as a lazy compound value. 1476 nonloc::LazyCompoundVal LCV = 1477 cast<nonloc::LazyCompoundVal>(svalBuilder. 1478 makeLazyCompoundVal(StoreRef(store, *this), S)); 1479 return CopyLazyBindings(LCV, store, R); 1480 } 1481 1482 // Handle lazy compound values. 1483 if (nonloc::LazyCompoundVal *LCV = dyn_cast<nonloc::LazyCompoundVal>(&Init)) 1484 return CopyLazyBindings(*LCV, store, R); 1485 1486 // Remaining case: explicit compound values. 1487 1488 if (Init.isUnknown()) 1489 return setImplicitDefaultValue(store, R, ElementTy); 1490 1491 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(Init); 1492 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); 1493 uint64_t i = 0; 1494 1495 StoreRef newStore(store, *this); 1496 for (; Size.hasValue() ? i < Size.getValue() : true ; ++i, ++VI) { 1497 // The init list might be shorter than the array length. 1498 if (VI == VE) 1499 break; 1500 1501 const NonLoc &Idx = svalBuilder.makeArrayIndex(i); 1502 const ElementRegion *ER = MRMgr.getElementRegion(ElementTy, Idx, R, Ctx); 1503 1504 if (ElementTy->isStructureOrClassType()) 1505 newStore = BindStruct(newStore.getStore(), ER, *VI); 1506 else if (ElementTy->isArrayType()) 1507 newStore = BindArray(newStore.getStore(), ER, *VI); 1508 else 1509 newStore = Bind(newStore.getStore(), svalBuilder.makeLoc(ER), *VI); 1510 } 1511 1512 // If the init list is shorter than the array length, set the 1513 // array default value. 1514 if (Size.hasValue() && i < Size.getValue()) 1515 newStore = setImplicitDefaultValue(newStore.getStore(), R, ElementTy); 1516 1517 return newStore; 1518} 1519 1520StoreRef RegionStoreManager::BindStruct(Store store, const TypedValueRegion* R, 1521 SVal V) { 1522 1523 if (!Features.supportsFields()) 1524 return StoreRef(store, *this); 1525 1526 QualType T = R->getValueType(); 1527 assert(T->isStructureOrClassType()); 1528 1529 const RecordType* RT = T->getAs<RecordType>(); 1530 RecordDecl *RD = RT->getDecl(); 1531 1532 if (!RD->isCompleteDefinition()) 1533 return StoreRef(store, *this); 1534 1535 // Handle lazy compound values. 1536 if (const nonloc::LazyCompoundVal *LCV=dyn_cast<nonloc::LazyCompoundVal>(&V)) 1537 return CopyLazyBindings(*LCV, store, R); 1538 1539 // We may get non-CompoundVal accidentally due to imprecise cast logic or 1540 // that we are binding symbolic struct value. Kill the field values, and if 1541 // the value is symbolic go and bind it as a "default" binding. 1542 if (V.isUnknown() || !isa<nonloc::CompoundVal>(V)) { 1543 SVal SV = isa<nonloc::SymbolVal>(V) ? V : UnknownVal(); 1544 return KillStruct(store, R, SV); 1545 } 1546 1547 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V); 1548 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); 1549 1550 RecordDecl::field_iterator FI, FE; 1551 StoreRef newStore(store, *this); 1552 1553 for (FI = RD->field_begin(), FE = RD->field_end(); FI != FE; ++FI) { 1554 1555 if (VI == VE) 1556 break; 1557 1558 // Skip any unnamed bitfields to stay in sync with the initializers. 1559 if ((*FI)->isUnnamedBitfield()) 1560 continue; 1561 1562 QualType FTy = (*FI)->getType(); 1563 const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R); 1564 1565 if (FTy->isArrayType()) 1566 newStore = BindArray(newStore.getStore(), FR, *VI); 1567 else if (FTy->isStructureOrClassType()) 1568 newStore = BindStruct(newStore.getStore(), FR, *VI); 1569 else 1570 newStore = Bind(newStore.getStore(), svalBuilder.makeLoc(FR), *VI); 1571 ++VI; 1572 } 1573 1574 // There may be fewer values in the initialize list than the fields of struct. 1575 if (FI != FE) { 1576 RegionBindings B = GetRegionBindings(newStore.getStore()); 1577 B = addBinding(B, R, BindingKey::Default, svalBuilder.makeIntVal(0, false)); 1578 newStore = StoreRef(B.getRootWithoutRetain(), *this); 1579 } 1580 1581 return newStore; 1582} 1583 1584StoreRef RegionStoreManager::KillStruct(Store store, const TypedRegion* R, 1585 SVal DefaultVal) { 1586 BindingKey key = BindingKey::Make(R, BindingKey::Default); 1587 1588 // The BindingKey may be "invalid" if we cannot handle the region binding 1589 // explicitly. One example is something like array[index], where index 1590 // is a symbolic value. In such cases, we want to invalidate the entire 1591 // array, as the index assignment could have been to any element. In 1592 // the case of nested symbolic indices, we need to march up the region 1593 // hierarchy untile we reach a region whose binding we can reason about. 1594 const SubRegion *subReg = R; 1595 1596 while (!key.isValid()) { 1597 if (const SubRegion *tmp = dyn_cast<SubRegion>(subReg->getSuperRegion())) { 1598 subReg = tmp; 1599 key = BindingKey::Make(tmp, BindingKey::Default); 1600 } 1601 else 1602 break; 1603 } 1604 1605 // Remove the old bindings, using 'subReg' as the root of all regions 1606 // we will invalidate. 1607 RegionBindings B = GetRegionBindings(store); 1608 OwningPtr<RegionStoreSubRegionMap> 1609 SubRegions(getRegionStoreSubRegionMap(store)); 1610 RemoveSubRegionBindings(B, subReg, *SubRegions); 1611 1612 // Set the default value of the struct region to "unknown". 1613 if (!key.isValid()) 1614 return StoreRef(B.getRootWithoutRetain(), *this); 1615 1616 return StoreRef(addBinding(B, key, DefaultVal).getRootWithoutRetain(), *this); 1617} 1618 1619StoreRef RegionStoreManager::CopyLazyBindings(nonloc::LazyCompoundVal V, 1620 Store store, 1621 const TypedRegion *R) { 1622 1623 // Nuke the old bindings stemming from R. 1624 RegionBindings B = GetRegionBindings(store); 1625 1626 OwningPtr<RegionStoreSubRegionMap> 1627 SubRegions(getRegionStoreSubRegionMap(store)); 1628 1629 // B and DVM are updated after the call to RemoveSubRegionBindings. 1630 RemoveSubRegionBindings(B, R, *SubRegions.get()); 1631 1632 // Now copy the bindings. This amounts to just binding 'V' to 'R'. This 1633 // results in a zero-copy algorithm. 1634 return StoreRef(addBinding(B, R, BindingKey::Default, 1635 V).getRootWithoutRetain(), *this); 1636} 1637 1638//===----------------------------------------------------------------------===// 1639// "Raw" retrievals and bindings. 1640//===----------------------------------------------------------------------===// 1641 1642 1643RegionBindings RegionStoreManager::addBinding(RegionBindings B, BindingKey K, 1644 SVal V) { 1645 if (!K.isValid()) 1646 return B; 1647 return RBFactory.add(B, K, V); 1648} 1649 1650RegionBindings RegionStoreManager::addBinding(RegionBindings B, 1651 const MemRegion *R, 1652 BindingKey::Kind k, SVal V) { 1653 return addBinding(B, BindingKey::Make(R, k), V); 1654} 1655 1656const SVal *RegionStoreManager::lookup(RegionBindings B, BindingKey K) { 1657 if (!K.isValid()) 1658 return NULL; 1659 return B.lookup(K); 1660} 1661 1662const SVal *RegionStoreManager::lookup(RegionBindings B, 1663 const MemRegion *R, 1664 BindingKey::Kind k) { 1665 return lookup(B, BindingKey::Make(R, k)); 1666} 1667 1668RegionBindings RegionStoreManager::removeBinding(RegionBindings B, 1669 BindingKey K) { 1670 if (!K.isValid()) 1671 return B; 1672 return RBFactory.remove(B, K); 1673} 1674 1675RegionBindings RegionStoreManager::removeBinding(RegionBindings B, 1676 const MemRegion *R, 1677 BindingKey::Kind k){ 1678 return removeBinding(B, BindingKey::Make(R, k)); 1679} 1680 1681//===----------------------------------------------------------------------===// 1682// State pruning. 1683//===----------------------------------------------------------------------===// 1684 1685namespace { 1686class removeDeadBindingsWorker : 1687 public ClusterAnalysis<removeDeadBindingsWorker> { 1688 SmallVector<const SymbolicRegion*, 12> Postponed; 1689 SymbolReaper &SymReaper; 1690 const StackFrameContext *CurrentLCtx; 1691 1692public: 1693 removeDeadBindingsWorker(RegionStoreManager &rm, 1694 ProgramStateManager &stateMgr, 1695 RegionBindings b, SymbolReaper &symReaper, 1696 const StackFrameContext *LCtx) 1697 : ClusterAnalysis<removeDeadBindingsWorker>(rm, stateMgr, b, 1698 /* includeGlobals = */ false), 1699 SymReaper(symReaper), CurrentLCtx(LCtx) {} 1700 1701 // Called by ClusterAnalysis. 1702 void VisitAddedToCluster(const MemRegion *baseR, RegionCluster &C); 1703 void VisitCluster(const MemRegion *baseR, BindingKey *I, BindingKey *E); 1704 1705 void VisitBindingKey(BindingKey K); 1706 bool UpdatePostponed(); 1707 void VisitBinding(SVal V); 1708}; 1709} 1710 1711void removeDeadBindingsWorker::VisitAddedToCluster(const MemRegion *baseR, 1712 RegionCluster &C) { 1713 1714 if (const VarRegion *VR = dyn_cast<VarRegion>(baseR)) { 1715 if (SymReaper.isLive(VR)) 1716 AddToWorkList(baseR, C); 1717 1718 return; 1719 } 1720 1721 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) { 1722 if (SymReaper.isLive(SR->getSymbol())) 1723 AddToWorkList(SR, C); 1724 else 1725 Postponed.push_back(SR); 1726 1727 return; 1728 } 1729 1730 if (isa<NonStaticGlobalSpaceRegion>(baseR)) { 1731 AddToWorkList(baseR, C); 1732 return; 1733 } 1734 1735 // CXXThisRegion in the current or parent location context is live. 1736 if (const CXXThisRegion *TR = dyn_cast<CXXThisRegion>(baseR)) { 1737 const StackArgumentsSpaceRegion *StackReg = 1738 cast<StackArgumentsSpaceRegion>(TR->getSuperRegion()); 1739 const StackFrameContext *RegCtx = StackReg->getStackFrame(); 1740 if (RegCtx == CurrentLCtx || RegCtx->isParentOf(CurrentLCtx)) 1741 AddToWorkList(TR, C); 1742 } 1743} 1744 1745void removeDeadBindingsWorker::VisitCluster(const MemRegion *baseR, 1746 BindingKey *I, BindingKey *E) { 1747 for ( ; I != E; ++I) 1748 VisitBindingKey(*I); 1749} 1750 1751void removeDeadBindingsWorker::VisitBinding(SVal V) { 1752 // Is it a LazyCompoundVal? All referenced regions are live as well. 1753 if (const nonloc::LazyCompoundVal *LCS = 1754 dyn_cast<nonloc::LazyCompoundVal>(&V)) { 1755 1756 const MemRegion *LazyR = LCS->getRegion(); 1757 RegionBindings B = RegionStoreManager::GetRegionBindings(LCS->getStore()); 1758 for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){ 1759 const SubRegion *baseR = dyn_cast<SubRegion>(RI.getKey().getRegion()); 1760 if (baseR && baseR->isSubRegionOf(LazyR)) 1761 VisitBinding(RI.getData()); 1762 } 1763 return; 1764 } 1765 1766 // If V is a region, then add it to the worklist. 1767 if (const MemRegion *R = V.getAsRegion()) 1768 AddToWorkList(R); 1769 1770 // Update the set of live symbols. 1771 for (SymExpr::symbol_iterator SI = V.symbol_begin(), SE = V.symbol_end(); 1772 SI!=SE; ++SI) 1773 SymReaper.markLive(*SI); 1774} 1775 1776void removeDeadBindingsWorker::VisitBindingKey(BindingKey K) { 1777 const MemRegion *R = K.getRegion(); 1778 1779 // Mark this region "live" by adding it to the worklist. This will cause 1780 // use to visit all regions in the cluster (if we haven't visited them 1781 // already). 1782 if (AddToWorkList(R)) { 1783 // Mark the symbol for any live SymbolicRegion as "live". This means we 1784 // should continue to track that symbol. 1785 if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(R)) 1786 SymReaper.markLive(SymR->getSymbol()); 1787 1788 // For BlockDataRegions, enqueue the VarRegions for variables marked 1789 // with __block (passed-by-reference). 1790 // via BlockDeclRefExprs. 1791 if (const BlockDataRegion *BD = dyn_cast<BlockDataRegion>(R)) { 1792 for (BlockDataRegion::referenced_vars_iterator 1793 RI = BD->referenced_vars_begin(), RE = BD->referenced_vars_end(); 1794 RI != RE; ++RI) { 1795 if ((*RI)->getDecl()->getAttr<BlocksAttr>()) 1796 AddToWorkList(*RI); 1797 } 1798 1799 // No possible data bindings on a BlockDataRegion. 1800 return; 1801 } 1802 } 1803 1804 // Visit the data binding for K. 1805 if (const SVal *V = RM.lookup(B, K)) 1806 VisitBinding(*V); 1807} 1808 1809bool removeDeadBindingsWorker::UpdatePostponed() { 1810 // See if any postponed SymbolicRegions are actually live now, after 1811 // having done a scan. 1812 bool changed = false; 1813 1814 for (SmallVectorImpl<const SymbolicRegion*>::iterator 1815 I = Postponed.begin(), E = Postponed.end() ; I != E ; ++I) { 1816 if (const SymbolicRegion *SR = cast_or_null<SymbolicRegion>(*I)) { 1817 if (SymReaper.isLive(SR->getSymbol())) { 1818 changed |= AddToWorkList(SR); 1819 *I = NULL; 1820 } 1821 } 1822 } 1823 1824 return changed; 1825} 1826 1827StoreRef RegionStoreManager::removeDeadBindings(Store store, 1828 const StackFrameContext *LCtx, 1829 SymbolReaper& SymReaper) { 1830 RegionBindings B = GetRegionBindings(store); 1831 removeDeadBindingsWorker W(*this, StateMgr, B, SymReaper, LCtx); 1832 W.GenerateClusters(); 1833 1834 // Enqueue the region roots onto the worklist. 1835 for (SymbolReaper::region_iterator I = SymReaper.region_begin(), 1836 E = SymReaper.region_end(); I != E; ++I) { 1837 W.AddToWorkList(*I); 1838 } 1839 1840 do W.RunWorkList(); while (W.UpdatePostponed()); 1841 1842 // We have now scanned the store, marking reachable regions and symbols 1843 // as live. We now remove all the regions that are dead from the store 1844 // as well as update DSymbols with the set symbols that are now dead. 1845 for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) { 1846 const BindingKey &K = I.getKey(); 1847 1848 // If the cluster has been visited, we know the region has been marked. 1849 if (W.isVisited(K.getRegion())) 1850 continue; 1851 1852 // Remove the dead entry. 1853 B = removeBinding(B, K); 1854 1855 // Mark all non-live symbols that this binding references as dead. 1856 if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(K.getRegion())) 1857 SymReaper.maybeDead(SymR->getSymbol()); 1858 1859 SVal X = I.getData(); 1860 SymExpr::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end(); 1861 for (; SI != SE; ++SI) 1862 SymReaper.maybeDead(*SI); 1863 } 1864 1865 return StoreRef(B.getRootWithoutRetain(), *this); 1866} 1867 1868 1869StoreRef RegionStoreManager::enterStackFrame(ProgramStateRef state, 1870 const LocationContext *callerCtx, 1871 const StackFrameContext *calleeCtx) 1872{ 1873 FunctionDecl const *FD = cast<FunctionDecl>(calleeCtx->getDecl()); 1874 FunctionDecl::param_const_iterator PI = FD->param_begin(), 1875 PE = FD->param_end(); 1876 StoreRef store = StoreRef(state->getStore(), *this); 1877 1878 if (CallExpr const *CE = dyn_cast<CallExpr>(calleeCtx->getCallSite())) { 1879 CallExpr::const_arg_iterator AI = CE->arg_begin(), AE = CE->arg_end(); 1880 1881 // Copy the arg expression value to the arg variables. We check that 1882 // PI != PE because the actual number of arguments may be different than 1883 // the function declaration. 1884 for (; AI != AE && PI != PE; ++AI, ++PI) { 1885 SVal ArgVal = state->getSVal(*AI, callerCtx); 1886 store = Bind(store.getStore(), 1887 svalBuilder.makeLoc(MRMgr.getVarRegion(*PI, calleeCtx)), 1888 ArgVal); 1889 } 1890 } else if (const CXXConstructExpr *CE = 1891 dyn_cast<CXXConstructExpr>(calleeCtx->getCallSite())) { 1892 CXXConstructExpr::const_arg_iterator AI = CE->arg_begin(), 1893 AE = CE->arg_end(); 1894 1895 // Copy the arg expression value to the arg variables. 1896 for (; AI != AE; ++AI, ++PI) { 1897 SVal ArgVal = state->getSVal(*AI, callerCtx); 1898 store = Bind(store.getStore(), 1899 svalBuilder.makeLoc(MRMgr.getVarRegion(*PI, calleeCtx)), 1900 ArgVal); 1901 } 1902 } else 1903 assert(isa<CXXDestructorDecl>(calleeCtx->getDecl())); 1904 1905 return store; 1906} 1907 1908//===----------------------------------------------------------------------===// 1909// Utility methods. 1910//===----------------------------------------------------------------------===// 1911 1912void RegionStoreManager::print(Store store, raw_ostream &OS, 1913 const char* nl, const char *sep) { 1914 RegionBindings B = GetRegionBindings(store); 1915 OS << "Store (direct and default bindings):" << nl; 1916 1917 for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) 1918 OS << ' ' << I.getKey() << " : " << I.getData() << nl; 1919} 1920