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