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