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