RegionStore.cpp revision f540c54701e3eeb34cb619a3a4eb18f1ac70ef2d
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/CallEvent.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 CallEvent *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 /// BindVector - Bind a compound value to a vector. 306 StoreRef BindVector(Store store, const TypedValueRegion* R, SVal V); 307 308 StoreRef BindArray(Store store, const TypedValueRegion* R, SVal V); 309 310 /// KillStruct - Set the entire struct to unknown. 311 StoreRef KillStruct(Store store, const TypedRegion* R, SVal DefaultVal); 312 313 StoreRef Remove(Store store, Loc LV); 314 315 void incrementReferenceCount(Store store) { 316 GetRegionBindings(store).manualRetain(); 317 } 318 319 /// If the StoreManager supports it, decrement the reference count of 320 /// the specified Store object. If the reference count hits 0, the memory 321 /// associated with the object is recycled. 322 void decrementReferenceCount(Store store) { 323 GetRegionBindings(store).manualRelease(); 324 } 325 326 bool includedInBindings(Store store, const MemRegion *region) const; 327 328 /// \brief Return the value bound to specified location in a given state. 329 /// 330 /// The high level logic for this method is this: 331 /// getBinding (L) 332 /// if L has binding 333 /// return L's binding 334 /// else if L is in killset 335 /// return unknown 336 /// else 337 /// if L is on stack or heap 338 /// return undefined 339 /// else 340 /// return symbolic 341 SVal getBinding(Store store, Loc L, QualType T = QualType()); 342 343 SVal getBindingForElement(Store store, const ElementRegion *R); 344 345 SVal getBindingForField(Store store, const FieldRegion *R); 346 347 SVal getBindingForObjCIvar(Store store, const ObjCIvarRegion *R); 348 349 SVal getBindingForVar(Store store, const VarRegion *R); 350 351 SVal getBindingForLazySymbol(const TypedValueRegion *R); 352 353 SVal getBindingForFieldOrElementCommon(Store store, const TypedValueRegion *R, 354 QualType Ty, const MemRegion *superR); 355 356 SVal getLazyBinding(const MemRegion *lazyBindingRegion, 357 Store lazyBindingStore); 358 359 /// Get bindings for the values in a struct and return a CompoundVal, used 360 /// when doing struct copy: 361 /// struct s x, y; 362 /// x = y; 363 /// y's value is retrieved by this method. 364 SVal getBindingForStruct(Store store, const TypedValueRegion* R); 365 366 SVal getBindingForArray(Store store, const TypedValueRegion* R); 367 368 /// Used to lazily generate derived symbols for bindings that are defined 369 /// implicitly by default bindings in a super region. 370 Optional<SVal> getBindingForDerivedDefaultValue(RegionBindings B, 371 const MemRegion *superR, 372 const TypedValueRegion *R, 373 QualType Ty); 374 375 /// Get the state and region whose binding this region R corresponds to. 376 std::pair<Store, const MemRegion*> 377 GetLazyBinding(RegionBindings B, const MemRegion *R, 378 const MemRegion *originalRegion, 379 bool includeSuffix = false); 380 381 StoreRef CopyLazyBindings(nonloc::LazyCompoundVal V, Store store, 382 const TypedRegion *R); 383 384 //===------------------------------------------------------------------===// 385 // State pruning. 386 //===------------------------------------------------------------------===// 387 388 /// removeDeadBindings - Scans the RegionStore of 'state' for dead values. 389 /// It returns a new Store with these values removed. 390 StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx, 391 SymbolReaper& SymReaper); 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 CallEvent *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 880// This mirrors Type::getCXXRecordDeclForPointerType(), but there doesn't 881// appear to be another need for this in the rest of the codebase. 882static const CXXRecordDecl *GetCXXRecordDeclForReferenceType(QualType Ty) { 883 if (const ReferenceType *RT = Ty->getAs<ReferenceType>()) 884 if (const RecordType *RCT = RT->getPointeeType()->getAs<RecordType>()) 885 return dyn_cast<CXXRecordDecl>(RCT->getDecl()); 886 return 0; 887} 888 889SVal RegionStoreManager::evalDerivedToBase(SVal derived, QualType baseType) { 890 const CXXRecordDecl *baseDecl; 891 892 if (baseType->isPointerType()) 893 baseDecl = baseType->getCXXRecordDeclForPointerType(); 894 else if (baseType->isReferenceType()) 895 baseDecl = GetCXXRecordDeclForReferenceType(baseType); 896 else 897 baseDecl = baseType->getAsCXXRecordDecl(); 898 899 assert(baseDecl && "not a CXXRecordDecl?"); 900 901 loc::MemRegionVal *derivedRegVal = dyn_cast<loc::MemRegionVal>(&derived); 902 if (!derivedRegVal) 903 return derived; 904 905 const MemRegion *baseReg = 906 MRMgr.getCXXBaseObjectRegion(baseDecl, derivedRegVal->getRegion()); 907 908 return loc::MemRegionVal(baseReg); 909} 910 911SVal RegionStoreManager::evalDynamicCast(SVal base, QualType derivedType, 912 bool &Failed) { 913 Failed = false; 914 915 loc::MemRegionVal *baseRegVal = dyn_cast<loc::MemRegionVal>(&base); 916 if (!baseRegVal) 917 return UnknownVal(); 918 const MemRegion *BaseRegion = baseRegVal->stripCasts(); 919 920 // Assume the derived class is a pointer or a reference to a CXX record. 921 derivedType = derivedType->getPointeeType(); 922 assert(!derivedType.isNull()); 923 const CXXRecordDecl *DerivedDecl = derivedType->getAsCXXRecordDecl(); 924 if (!DerivedDecl && !derivedType->isVoidType()) 925 return UnknownVal(); 926 927 // Drill down the CXXBaseObject chains, which represent upcasts (casts from 928 // derived to base). 929 const MemRegion *SR = BaseRegion; 930 while (const TypedRegion *TSR = dyn_cast_or_null<TypedRegion>(SR)) { 931 QualType BaseType = TSR->getLocationType()->getPointeeType(); 932 assert(!BaseType.isNull()); 933 const CXXRecordDecl *SRDecl = BaseType->getAsCXXRecordDecl(); 934 if (!SRDecl) 935 return UnknownVal(); 936 937 // If found the derived class, the cast succeeds. 938 if (SRDecl == DerivedDecl) 939 return loc::MemRegionVal(TSR); 940 941 // If the region type is a subclass of the derived type. 942 if (!derivedType->isVoidType() && SRDecl->isDerivedFrom(DerivedDecl)) { 943 // This occurs in two cases. 944 // 1) We are processing an upcast. 945 // 2) We are processing a downcast but we jumped directly from the 946 // ancestor to a child of the cast value, so conjure the 947 // appropriate region to represent value (the intermediate node). 948 return loc::MemRegionVal(MRMgr.getCXXBaseObjectRegion(DerivedDecl, 949 BaseRegion)); 950 } 951 952 // If super region is not a parent of derived class, the cast definitely 953 // fails. 954 if (!derivedType->isVoidType() && 955 DerivedDecl->isProvablyNotDerivedFrom(SRDecl)) { 956 Failed = true; 957 return UnknownVal(); 958 } 959 960 if (const CXXBaseObjectRegion *R = dyn_cast<CXXBaseObjectRegion>(TSR)) 961 // Drill down the chain to get the derived classes. 962 SR = R->getSuperRegion(); 963 else { 964 // We reached the bottom of the hierarchy. 965 966 // If this is a cast to void*, return the region. 967 if (derivedType->isVoidType()) 968 return loc::MemRegionVal(TSR); 969 970 // We did not find the derived class. We we must be casting the base to 971 // derived, so the cast should fail. 972 Failed = true; 973 return UnknownVal(); 974 } 975 } 976 977 return UnknownVal(); 978} 979 980//===----------------------------------------------------------------------===// 981// Loading values from regions. 982//===----------------------------------------------------------------------===// 983 984Optional<SVal> RegionStoreManager::getDirectBinding(RegionBindings B, 985 const MemRegion *R) { 986 987 if (const SVal *V = lookup(B, R, BindingKey::Direct)) 988 return *V; 989 990 return Optional<SVal>(); 991} 992 993Optional<SVal> RegionStoreManager::getDefaultBinding(RegionBindings B, 994 const MemRegion *R) { 995 if (R->isBoundable()) 996 if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) 997 if (TR->getValueType()->isUnionType()) 998 return UnknownVal(); 999 1000 if (const SVal *V = lookup(B, R, BindingKey::Default)) 1001 return *V; 1002 1003 return Optional<SVal>(); 1004} 1005 1006SVal RegionStoreManager::getBinding(Store store, Loc L, QualType T) { 1007 assert(!isa<UnknownVal>(L) && "location unknown"); 1008 assert(!isa<UndefinedVal>(L) && "location undefined"); 1009 1010 // For access to concrete addresses, return UnknownVal. Checks 1011 // for null dereferences (and similar errors) are done by checkers, not 1012 // the Store. 1013 // FIXME: We can consider lazily symbolicating such memory, but we really 1014 // should defer this when we can reason easily about symbolicating arrays 1015 // of bytes. 1016 if (isa<loc::ConcreteInt>(L)) { 1017 return UnknownVal(); 1018 } 1019 if (!isa<loc::MemRegionVal>(L)) { 1020 return UnknownVal(); 1021 } 1022 1023 const MemRegion *MR = cast<loc::MemRegionVal>(L).getRegion(); 1024 1025 if (isa<AllocaRegion>(MR) || 1026 isa<SymbolicRegion>(MR) || 1027 isa<CodeTextRegion>(MR)) { 1028 if (T.isNull()) { 1029 if (const TypedRegion *TR = dyn_cast<TypedRegion>(MR)) 1030 T = TR->getLocationType(); 1031 else { 1032 const SymbolicRegion *SR = cast<SymbolicRegion>(MR); 1033 T = SR->getSymbol()->getType(Ctx); 1034 } 1035 } 1036 MR = GetElementZeroRegion(MR, T); 1037 } 1038 1039 // FIXME: Perhaps this method should just take a 'const MemRegion*' argument 1040 // instead of 'Loc', and have the other Loc cases handled at a higher level. 1041 const TypedValueRegion *R = cast<TypedValueRegion>(MR); 1042 QualType RTy = R->getValueType(); 1043 1044 // FIXME: We should eventually handle funny addressing. e.g.: 1045 // 1046 // int x = ...; 1047 // int *p = &x; 1048 // char *q = (char*) p; 1049 // char c = *q; // returns the first byte of 'x'. 1050 // 1051 // Such funny addressing will occur due to layering of regions. 1052 1053 if (RTy->isStructureOrClassType()) 1054 return getBindingForStruct(store, R); 1055 1056 // FIXME: Handle unions. 1057 if (RTy->isUnionType()) 1058 return UnknownVal(); 1059 1060 if (RTy->isArrayType()) { 1061 if (RTy->isConstantArrayType()) 1062 return getBindingForArray(store, R); 1063 else 1064 return UnknownVal(); 1065 } 1066 1067 // FIXME: handle Vector types. 1068 if (RTy->isVectorType()) 1069 return UnknownVal(); 1070 1071 if (const FieldRegion* FR = dyn_cast<FieldRegion>(R)) 1072 return CastRetrievedVal(getBindingForField(store, FR), FR, T, false); 1073 1074 if (const ElementRegion* ER = dyn_cast<ElementRegion>(R)) { 1075 // FIXME: Here we actually perform an implicit conversion from the loaded 1076 // value to the element type. Eventually we want to compose these values 1077 // more intelligently. For example, an 'element' can encompass multiple 1078 // bound regions (e.g., several bound bytes), or could be a subset of 1079 // a larger value. 1080 return CastRetrievedVal(getBindingForElement(store, ER), ER, T, false); 1081 } 1082 1083 if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) { 1084 // FIXME: Here we actually perform an implicit conversion from the loaded 1085 // value to the ivar type. What we should model is stores to ivars 1086 // that blow past the extent of the ivar. If the address of the ivar is 1087 // reinterpretted, it is possible we stored a different value that could 1088 // fit within the ivar. Either we need to cast these when storing them 1089 // or reinterpret them lazily (as we do here). 1090 return CastRetrievedVal(getBindingForObjCIvar(store, IVR), IVR, T, false); 1091 } 1092 1093 if (const VarRegion *VR = dyn_cast<VarRegion>(R)) { 1094 // FIXME: Here we actually perform an implicit conversion from the loaded 1095 // value to the variable type. What we should model is stores to variables 1096 // that blow past the extent of the variable. If the address of the 1097 // variable is reinterpretted, it is possible we stored a different value 1098 // that could fit within the variable. Either we need to cast these when 1099 // storing them or reinterpret them lazily (as we do here). 1100 return CastRetrievedVal(getBindingForVar(store, VR), VR, T, false); 1101 } 1102 1103 RegionBindings B = GetRegionBindings(store); 1104 const SVal *V = lookup(B, R, BindingKey::Direct); 1105 1106 // Check if the region has a binding. 1107 if (V) 1108 return *V; 1109 1110 // The location does not have a bound value. This means that it has 1111 // the value it had upon its creation and/or entry to the analyzed 1112 // function/method. These are either symbolic values or 'undefined'. 1113 if (R->hasStackNonParametersStorage()) { 1114 // All stack variables are considered to have undefined values 1115 // upon creation. All heap allocated blocks are considered to 1116 // have undefined values as well unless they are explicitly bound 1117 // to specific values. 1118 return UndefinedVal(); 1119 } 1120 1121 // All other values are symbolic. 1122 return svalBuilder.getRegionValueSymbolVal(R); 1123} 1124 1125std::pair<Store, const MemRegion *> 1126RegionStoreManager::GetLazyBinding(RegionBindings B, const MemRegion *R, 1127 const MemRegion *originalRegion, 1128 bool includeSuffix) { 1129 1130 if (originalRegion != R) { 1131 if (Optional<SVal> OV = getDefaultBinding(B, R)) { 1132 if (const nonloc::LazyCompoundVal *V = 1133 dyn_cast<nonloc::LazyCompoundVal>(OV.getPointer())) 1134 return std::make_pair(V->getStore(), V->getRegion()); 1135 } 1136 } 1137 1138 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) { 1139 const std::pair<Store, const MemRegion *> &X = 1140 GetLazyBinding(B, ER->getSuperRegion(), originalRegion); 1141 1142 if (X.second) 1143 return std::make_pair(X.first, 1144 MRMgr.getElementRegionWithSuper(ER, X.second)); 1145 } 1146 else if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) { 1147 const std::pair<Store, const MemRegion *> &X = 1148 GetLazyBinding(B, FR->getSuperRegion(), originalRegion); 1149 1150 if (X.second) { 1151 if (includeSuffix) 1152 return std::make_pair(X.first, 1153 MRMgr.getFieldRegionWithSuper(FR, X.second)); 1154 return X; 1155 } 1156 1157 } 1158 // C++ base object region is another kind of region that we should blast 1159 // through to look for lazy compound value. It is like a field region. 1160 else if (const CXXBaseObjectRegion *baseReg = 1161 dyn_cast<CXXBaseObjectRegion>(R)) { 1162 const std::pair<Store, const MemRegion *> &X = 1163 GetLazyBinding(B, baseReg->getSuperRegion(), originalRegion); 1164 1165 if (X.second) { 1166 if (includeSuffix) 1167 return std::make_pair(X.first, 1168 MRMgr.getCXXBaseObjectRegionWithSuper(baseReg, 1169 X.second)); 1170 return X; 1171 } 1172 } 1173 1174 // The NULL MemRegion indicates an non-existent lazy binding. A NULL Store is 1175 // possible for a valid lazy binding. 1176 return std::make_pair((Store) 0, (const MemRegion *) 0); 1177} 1178 1179SVal RegionStoreManager::getBindingForElement(Store store, 1180 const ElementRegion* R) { 1181 // We do not currently model bindings of the CompoundLiteralregion. 1182 if (isa<CompoundLiteralRegion>(R->getBaseRegion())) 1183 return UnknownVal(); 1184 1185 // Check if the region has a binding. 1186 RegionBindings B = GetRegionBindings(store); 1187 if (const Optional<SVal> &V = getDirectBinding(B, R)) 1188 return *V; 1189 1190 const MemRegion* superR = R->getSuperRegion(); 1191 1192 // Check if the region is an element region of a string literal. 1193 if (const StringRegion *StrR=dyn_cast<StringRegion>(superR)) { 1194 // FIXME: Handle loads from strings where the literal is treated as 1195 // an integer, e.g., *((unsigned int*)"hello") 1196 QualType T = Ctx.getAsArrayType(StrR->getValueType())->getElementType(); 1197 if (T != Ctx.getCanonicalType(R->getElementType())) 1198 return UnknownVal(); 1199 1200 const StringLiteral *Str = StrR->getStringLiteral(); 1201 SVal Idx = R->getIndex(); 1202 if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&Idx)) { 1203 int64_t i = CI->getValue().getSExtValue(); 1204 // Abort on string underrun. This can be possible by arbitrary 1205 // clients of getBindingForElement(). 1206 if (i < 0) 1207 return UndefinedVal(); 1208 int64_t length = Str->getLength(); 1209 // Technically, only i == length is guaranteed to be null. 1210 // However, such overflows should be caught before reaching this point; 1211 // the only time such an access would be made is if a string literal was 1212 // used to initialize a larger array. 1213 char c = (i >= length) ? '\0' : Str->getCodeUnit(i); 1214 return svalBuilder.makeIntVal(c, T); 1215 } 1216 } 1217 1218 // Check for loads from a code text region. For such loads, just give up. 1219 if (isa<CodeTextRegion>(superR)) 1220 return UnknownVal(); 1221 1222 // Handle the case where we are indexing into a larger scalar object. 1223 // For example, this handles: 1224 // int x = ... 1225 // char *y = &x; 1226 // return *y; 1227 // FIXME: This is a hack, and doesn't do anything really intelligent yet. 1228 const RegionRawOffset &O = R->getAsArrayOffset(); 1229 1230 // If we cannot reason about the offset, return an unknown value. 1231 if (!O.getRegion()) 1232 return UnknownVal(); 1233 1234 if (const TypedValueRegion *baseR = 1235 dyn_cast_or_null<TypedValueRegion>(O.getRegion())) { 1236 QualType baseT = baseR->getValueType(); 1237 if (baseT->isScalarType()) { 1238 QualType elemT = R->getElementType(); 1239 if (elemT->isScalarType()) { 1240 if (Ctx.getTypeSizeInChars(baseT) >= Ctx.getTypeSizeInChars(elemT)) { 1241 if (const Optional<SVal> &V = getDirectBinding(B, superR)) { 1242 if (SymbolRef parentSym = V->getAsSymbol()) 1243 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); 1244 1245 if (V->isUnknownOrUndef()) 1246 return *V; 1247 // Other cases: give up. We are indexing into a larger object 1248 // that has some value, but we don't know how to handle that yet. 1249 return UnknownVal(); 1250 } 1251 } 1252 } 1253 } 1254 } 1255 return getBindingForFieldOrElementCommon(store, R, R->getElementType(), 1256 superR); 1257} 1258 1259SVal RegionStoreManager::getBindingForField(Store store, 1260 const FieldRegion* R) { 1261 1262 // Check if the region has a binding. 1263 RegionBindings B = GetRegionBindings(store); 1264 if (const Optional<SVal> &V = getDirectBinding(B, R)) 1265 return *V; 1266 1267 QualType Ty = R->getValueType(); 1268 return getBindingForFieldOrElementCommon(store, R, Ty, R->getSuperRegion()); 1269} 1270 1271Optional<SVal> 1272RegionStoreManager::getBindingForDerivedDefaultValue(RegionBindings B, 1273 const MemRegion *superR, 1274 const TypedValueRegion *R, 1275 QualType Ty) { 1276 1277 if (const Optional<SVal> &D = getDefaultBinding(B, superR)) { 1278 const SVal &val = D.getValue(); 1279 if (SymbolRef parentSym = val.getAsSymbol()) 1280 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); 1281 1282 if (val.isZeroConstant()) 1283 return svalBuilder.makeZeroVal(Ty); 1284 1285 if (val.isUnknownOrUndef()) 1286 return val; 1287 1288 // Lazy bindings are handled later. 1289 if (isa<nonloc::LazyCompoundVal>(val)) 1290 return Optional<SVal>(); 1291 1292 llvm_unreachable("Unknown default value"); 1293 } 1294 1295 return Optional<SVal>(); 1296} 1297 1298SVal RegionStoreManager::getLazyBinding(const MemRegion *lazyBindingRegion, 1299 Store lazyBindingStore) { 1300 if (const ElementRegion *ER = dyn_cast<ElementRegion>(lazyBindingRegion)) 1301 return getBindingForElement(lazyBindingStore, ER); 1302 1303 return getBindingForField(lazyBindingStore, 1304 cast<FieldRegion>(lazyBindingRegion)); 1305} 1306 1307SVal RegionStoreManager::getBindingForFieldOrElementCommon(Store store, 1308 const TypedValueRegion *R, 1309 QualType Ty, 1310 const MemRegion *superR) { 1311 1312 // At this point we have already checked in either getBindingForElement or 1313 // getBindingForField if 'R' has a direct binding. 1314 RegionBindings B = GetRegionBindings(store); 1315 1316 // Lazy binding? 1317 Store lazyBindingStore = NULL; 1318 const MemRegion *lazyBindingRegion = NULL; 1319 llvm::tie(lazyBindingStore, lazyBindingRegion) = GetLazyBinding(B, R, R, 1320 true); 1321 1322 if (lazyBindingRegion) 1323 return getLazyBinding(lazyBindingRegion, lazyBindingStore); 1324 1325 // Record whether or not we see a symbolic index. That can completely 1326 // be out of scope of our lookup. 1327 bool hasSymbolicIndex = false; 1328 1329 while (superR) { 1330 if (const Optional<SVal> &D = 1331 getBindingForDerivedDefaultValue(B, superR, R, Ty)) 1332 return *D; 1333 1334 if (const ElementRegion *ER = dyn_cast<ElementRegion>(superR)) { 1335 NonLoc index = ER->getIndex(); 1336 if (!index.isConstant()) 1337 hasSymbolicIndex = true; 1338 } 1339 1340 // If our super region is a field or element itself, walk up the region 1341 // hierarchy to see if there is a default value installed in an ancestor. 1342 if (const SubRegion *SR = dyn_cast<SubRegion>(superR)) { 1343 superR = SR->getSuperRegion(); 1344 continue; 1345 } 1346 break; 1347 } 1348 1349 if (R->hasStackNonParametersStorage()) { 1350 if (isa<ElementRegion>(R)) { 1351 // Currently we don't reason specially about Clang-style vectors. Check 1352 // if superR is a vector and if so return Unknown. 1353 if (const TypedValueRegion *typedSuperR = 1354 dyn_cast<TypedValueRegion>(superR)) { 1355 if (typedSuperR->getValueType()->isVectorType()) 1356 return UnknownVal(); 1357 } 1358 } 1359 1360 // FIXME: We also need to take ElementRegions with symbolic indexes into 1361 // account. This case handles both directly accessing an ElementRegion 1362 // with a symbolic offset, but also fields within an element with 1363 // a symbolic offset. 1364 if (hasSymbolicIndex) 1365 return UnknownVal(); 1366 1367 return UndefinedVal(); 1368 } 1369 1370 // All other values are symbolic. 1371 return svalBuilder.getRegionValueSymbolVal(R); 1372} 1373 1374SVal RegionStoreManager::getBindingForObjCIvar(Store store, 1375 const ObjCIvarRegion* R) { 1376 1377 // Check if the region has a binding. 1378 RegionBindings B = GetRegionBindings(store); 1379 1380 if (const Optional<SVal> &V = getDirectBinding(B, R)) 1381 return *V; 1382 1383 const MemRegion *superR = R->getSuperRegion(); 1384 1385 // Check if the super region has a default binding. 1386 if (const Optional<SVal> &V = getDefaultBinding(B, superR)) { 1387 if (SymbolRef parentSym = V->getAsSymbol()) 1388 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); 1389 1390 // Other cases: give up. 1391 return UnknownVal(); 1392 } 1393 1394 return getBindingForLazySymbol(R); 1395} 1396 1397SVal RegionStoreManager::getBindingForVar(Store store, const VarRegion *R) { 1398 1399 // Check if the region has a binding. 1400 RegionBindings B = GetRegionBindings(store); 1401 1402 if (const Optional<SVal> &V = getDirectBinding(B, R)) 1403 return *V; 1404 1405 // Lazily derive a value for the VarRegion. 1406 const VarDecl *VD = R->getDecl(); 1407 QualType T = VD->getType(); 1408 const MemSpaceRegion *MS = R->getMemorySpace(); 1409 1410 if (isa<UnknownSpaceRegion>(MS) || 1411 isa<StackArgumentsSpaceRegion>(MS)) 1412 return svalBuilder.getRegionValueSymbolVal(R); 1413 1414 if (isa<GlobalsSpaceRegion>(MS)) { 1415 if (isa<NonStaticGlobalSpaceRegion>(MS)) { 1416 // Is 'VD' declared constant? If so, retrieve the constant value. 1417 QualType CT = Ctx.getCanonicalType(T); 1418 if (CT.isConstQualified()) { 1419 const Expr *Init = VD->getInit(); 1420 // Do the null check first, as we want to call 'IgnoreParenCasts'. 1421 if (Init) 1422 if (const IntegerLiteral *IL = 1423 dyn_cast<IntegerLiteral>(Init->IgnoreParenCasts())) { 1424 const nonloc::ConcreteInt &V = svalBuilder.makeIntVal(IL); 1425 return svalBuilder.evalCast(V, Init->getType(), IL->getType()); 1426 } 1427 } 1428 1429 if (const Optional<SVal> &V 1430 = getBindingForDerivedDefaultValue(B, MS, R, CT)) 1431 return V.getValue(); 1432 1433 return svalBuilder.getRegionValueSymbolVal(R); 1434 } 1435 1436 if (T->isIntegerType()) 1437 return svalBuilder.makeIntVal(0, T); 1438 if (T->isPointerType()) 1439 return svalBuilder.makeNull(); 1440 1441 return UnknownVal(); 1442 } 1443 1444 return UndefinedVal(); 1445} 1446 1447SVal RegionStoreManager::getBindingForLazySymbol(const TypedValueRegion *R) { 1448 // All other values are symbolic. 1449 return svalBuilder.getRegionValueSymbolVal(R); 1450} 1451 1452static bool mayHaveLazyBinding(QualType Ty) { 1453 return Ty->isArrayType() || Ty->isStructureOrClassType(); 1454} 1455 1456SVal RegionStoreManager::getBindingForStruct(Store store, 1457 const TypedValueRegion* R) { 1458 const RecordDecl *RD = R->getValueType()->castAs<RecordType>()->getDecl(); 1459 if (RD->field_empty()) 1460 return UnknownVal(); 1461 1462 // If we already have a lazy binding, don't create a new one, 1463 // unless the first field might have a lazy binding of its own. 1464 // (Right now we can't tell the difference.) 1465 QualType FirstFieldType = RD->field_begin()->getType(); 1466 if (!mayHaveLazyBinding(FirstFieldType)) { 1467 RegionBindings B = GetRegionBindings(store); 1468 BindingKey K = BindingKey::Make(R, BindingKey::Default); 1469 if (const nonloc::LazyCompoundVal *V = 1470 dyn_cast_or_null<nonloc::LazyCompoundVal>(lookup(B, K))) { 1471 return *V; 1472 } 1473 } 1474 1475 return svalBuilder.makeLazyCompoundVal(StoreRef(store, *this), R); 1476} 1477 1478SVal RegionStoreManager::getBindingForArray(Store store, 1479 const TypedValueRegion * R) { 1480 const ConstantArrayType *Ty = Ctx.getAsConstantArrayType(R->getValueType()); 1481 assert(Ty && "Only constant array types can have compound bindings."); 1482 1483 // If we already have a lazy binding, don't create a new one, 1484 // unless the first element might have a lazy binding of its own. 1485 // (Right now we can't tell the difference.) 1486 if (!mayHaveLazyBinding(Ty->getElementType())) { 1487 RegionBindings B = GetRegionBindings(store); 1488 BindingKey K = BindingKey::Make(R, BindingKey::Default); 1489 if (const nonloc::LazyCompoundVal *V = 1490 dyn_cast_or_null<nonloc::LazyCompoundVal>(lookup(B, K))) { 1491 return *V; 1492 } 1493 } 1494 1495 return svalBuilder.makeLazyCompoundVal(StoreRef(store, *this), R); 1496} 1497 1498bool RegionStoreManager::includedInBindings(Store store, 1499 const MemRegion *region) const { 1500 RegionBindings B = GetRegionBindings(store); 1501 region = region->getBaseRegion(); 1502 1503 for (RegionBindings::iterator it = B.begin(), ei = B.end(); it != ei; ++it) { 1504 const BindingKey &K = it.getKey(); 1505 if (region == K.getRegion()) 1506 return true; 1507 const SVal &D = it.getData(); 1508 if (const MemRegion *r = D.getAsRegion()) 1509 if (r == region) 1510 return true; 1511 } 1512 return false; 1513} 1514 1515//===----------------------------------------------------------------------===// 1516// Binding values to regions. 1517//===----------------------------------------------------------------------===// 1518 1519StoreRef RegionStoreManager::Remove(Store store, Loc L) { 1520 if (isa<loc::MemRegionVal>(L)) 1521 if (const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion()) 1522 return StoreRef(removeBinding(GetRegionBindings(store), 1523 R).getRootWithoutRetain(), 1524 *this); 1525 1526 return StoreRef(store, *this); 1527} 1528 1529StoreRef RegionStoreManager::Bind(Store store, Loc L, SVal V) { 1530 if (isa<loc::ConcreteInt>(L)) 1531 return StoreRef(store, *this); 1532 1533 // If we get here, the location should be a region. 1534 const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion(); 1535 1536 // Check if the region is a struct region. 1537 if (const TypedValueRegion* TR = dyn_cast<TypedValueRegion>(R)) { 1538 QualType Ty = TR->getValueType(); 1539 if (Ty->isStructureOrClassType()) 1540 return BindStruct(store, TR, V); 1541 if (Ty->isVectorType()) 1542 return BindVector(store, TR, V); 1543 } 1544 1545 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) { 1546 if (ER->getIndex().isZeroConstant()) { 1547 if (const TypedValueRegion *superR = 1548 dyn_cast<TypedValueRegion>(ER->getSuperRegion())) { 1549 QualType superTy = superR->getValueType(); 1550 // For now, just invalidate the fields of the struct/union/class. 1551 // This is for test rdar_test_7185607 in misc-ps-region-store.m. 1552 // FIXME: Precisely handle the fields of the record. 1553 if (superTy->isStructureOrClassType()) 1554 return KillStruct(store, superR, UnknownVal()); 1555 } 1556 } 1557 } 1558 else if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) { 1559 // Binding directly to a symbolic region should be treated as binding 1560 // to element 0. 1561 QualType T = SR->getSymbol()->getType(Ctx); 1562 1563 // FIXME: Is this the right way to handle symbols that are references? 1564 if (const PointerType *PT = T->getAs<PointerType>()) 1565 T = PT->getPointeeType(); 1566 else 1567 T = T->getAs<ReferenceType>()->getPointeeType(); 1568 1569 R = GetElementZeroRegion(SR, T); 1570 } 1571 1572 // Perform the binding. 1573 RegionBindings B = GetRegionBindings(store); 1574 return StoreRef(addBinding(B, R, BindingKey::Direct, 1575 V).getRootWithoutRetain(), *this); 1576} 1577 1578StoreRef RegionStoreManager::BindDecl(Store store, const VarRegion *VR, 1579 SVal InitVal) { 1580 1581 QualType T = VR->getDecl()->getType(); 1582 1583 if (T->isArrayType()) 1584 return BindArray(store, VR, InitVal); 1585 if (T->isStructureOrClassType()) 1586 return BindStruct(store, VR, InitVal); 1587 1588 return Bind(store, svalBuilder.makeLoc(VR), InitVal); 1589} 1590 1591// FIXME: this method should be merged into Bind(). 1592StoreRef RegionStoreManager::BindCompoundLiteral(Store store, 1593 const CompoundLiteralExpr *CL, 1594 const LocationContext *LC, 1595 SVal V) { 1596 return Bind(store, loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL, LC)), 1597 V); 1598} 1599 1600StoreRef RegionStoreManager::setImplicitDefaultValue(Store store, 1601 const MemRegion *R, 1602 QualType T) { 1603 RegionBindings B = GetRegionBindings(store); 1604 SVal V; 1605 1606 if (Loc::isLocType(T)) 1607 V = svalBuilder.makeNull(); 1608 else if (T->isIntegerType()) 1609 V = svalBuilder.makeZeroVal(T); 1610 else if (T->isStructureOrClassType() || T->isArrayType()) { 1611 // Set the default value to a zero constant when it is a structure 1612 // or array. The type doesn't really matter. 1613 V = svalBuilder.makeZeroVal(Ctx.IntTy); 1614 } 1615 else { 1616 // We can't represent values of this type, but we still need to set a value 1617 // to record that the region has been initialized. 1618 // If this assertion ever fires, a new case should be added above -- we 1619 // should know how to default-initialize any value we can symbolicate. 1620 assert(!SymbolManager::canSymbolicate(T) && "This type is representable"); 1621 V = UnknownVal(); 1622 } 1623 1624 return StoreRef(addBinding(B, R, BindingKey::Default, 1625 V).getRootWithoutRetain(), *this); 1626} 1627 1628StoreRef RegionStoreManager::BindArray(Store store, const TypedValueRegion* R, 1629 SVal Init) { 1630 1631 const ArrayType *AT =cast<ArrayType>(Ctx.getCanonicalType(R->getValueType())); 1632 QualType ElementTy = AT->getElementType(); 1633 Optional<uint64_t> Size; 1634 1635 if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(AT)) 1636 Size = CAT->getSize().getZExtValue(); 1637 1638 // Check if the init expr is a string literal. 1639 if (loc::MemRegionVal *MRV = dyn_cast<loc::MemRegionVal>(&Init)) { 1640 const StringRegion *S = cast<StringRegion>(MRV->getRegion()); 1641 1642 // Treat the string as a lazy compound value. 1643 nonloc::LazyCompoundVal LCV = 1644 cast<nonloc::LazyCompoundVal>(svalBuilder. 1645 makeLazyCompoundVal(StoreRef(store, *this), S)); 1646 return CopyLazyBindings(LCV, store, R); 1647 } 1648 1649 // Handle lazy compound values. 1650 if (nonloc::LazyCompoundVal *LCV = dyn_cast<nonloc::LazyCompoundVal>(&Init)) 1651 return CopyLazyBindings(*LCV, store, R); 1652 1653 // Remaining case: explicit compound values. 1654 1655 if (Init.isUnknown()) 1656 return setImplicitDefaultValue(store, R, ElementTy); 1657 1658 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(Init); 1659 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); 1660 uint64_t i = 0; 1661 1662 StoreRef newStore(store, *this); 1663 for (; Size.hasValue() ? i < Size.getValue() : true ; ++i, ++VI) { 1664 // The init list might be shorter than the array length. 1665 if (VI == VE) 1666 break; 1667 1668 const NonLoc &Idx = svalBuilder.makeArrayIndex(i); 1669 const ElementRegion *ER = MRMgr.getElementRegion(ElementTy, Idx, R, Ctx); 1670 1671 if (ElementTy->isStructureOrClassType()) 1672 newStore = BindStruct(newStore.getStore(), ER, *VI); 1673 else if (ElementTy->isArrayType()) 1674 newStore = BindArray(newStore.getStore(), ER, *VI); 1675 else 1676 newStore = Bind(newStore.getStore(), svalBuilder.makeLoc(ER), *VI); 1677 } 1678 1679 // If the init list is shorter than the array length, set the 1680 // array default value. 1681 if (Size.hasValue() && i < Size.getValue()) 1682 newStore = setImplicitDefaultValue(newStore.getStore(), R, ElementTy); 1683 1684 return newStore; 1685} 1686 1687StoreRef RegionStoreManager::BindVector(Store store, const TypedValueRegion* R, 1688 SVal V) { 1689 QualType T = R->getValueType(); 1690 assert(T->isVectorType()); 1691 const VectorType *VT = T->getAs<VectorType>(); // Use getAs for typedefs. 1692 1693 // Handle lazy compound values. 1694 if (nonloc::LazyCompoundVal *LCV = dyn_cast<nonloc::LazyCompoundVal>(&V)) 1695 return CopyLazyBindings(*LCV, store, R); 1696 1697 // We may get non-CompoundVal accidentally due to imprecise cast logic or 1698 // that we are binding symbolic struct value. Kill the field values, and if 1699 // the value is symbolic go and bind it as a "default" binding. 1700 if (V.isUnknown() || !isa<nonloc::CompoundVal>(V)) { 1701 SVal SV = isa<nonloc::SymbolVal>(V) ? V : UnknownVal(); 1702 return KillStruct(store, R, SV); 1703 } 1704 1705 QualType ElemType = VT->getElementType(); 1706 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V); 1707 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); 1708 unsigned index = 0, numElements = VT->getNumElements(); 1709 StoreRef newStore(store, *this); 1710 1711 for ( ; index != numElements ; ++index) { 1712 if (VI == VE) 1713 break; 1714 1715 NonLoc Idx = svalBuilder.makeArrayIndex(index); 1716 const ElementRegion *ER = MRMgr.getElementRegion(ElemType, Idx, R, Ctx); 1717 1718 if (ElemType->isArrayType()) 1719 newStore = BindArray(newStore.getStore(), ER, *VI); 1720 else if (ElemType->isStructureOrClassType()) 1721 newStore = BindStruct(newStore.getStore(), ER, *VI); 1722 else 1723 newStore = Bind(newStore.getStore(), svalBuilder.makeLoc(ER), *VI); 1724 } 1725 return newStore; 1726} 1727 1728StoreRef RegionStoreManager::BindStruct(Store store, const TypedValueRegion* R, 1729 SVal V) { 1730 1731 if (!Features.supportsFields()) 1732 return StoreRef(store, *this); 1733 1734 QualType T = R->getValueType(); 1735 assert(T->isStructureOrClassType()); 1736 1737 const RecordType* RT = T->getAs<RecordType>(); 1738 RecordDecl *RD = RT->getDecl(); 1739 1740 if (!RD->isCompleteDefinition()) 1741 return StoreRef(store, *this); 1742 1743 // Handle lazy compound values. 1744 if (const nonloc::LazyCompoundVal *LCV=dyn_cast<nonloc::LazyCompoundVal>(&V)) 1745 return CopyLazyBindings(*LCV, store, R); 1746 1747 // We may get non-CompoundVal accidentally due to imprecise cast logic or 1748 // that we are binding symbolic struct value. Kill the field values, and if 1749 // the value is symbolic go and bind it as a "default" binding. 1750 if (V.isUnknown() || !isa<nonloc::CompoundVal>(V)) { 1751 SVal SV = isa<nonloc::SymbolVal>(V) ? V : UnknownVal(); 1752 return KillStruct(store, R, SV); 1753 } 1754 1755 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V); 1756 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); 1757 1758 RecordDecl::field_iterator FI, FE; 1759 StoreRef newStore(store, *this); 1760 1761 for (FI = RD->field_begin(), FE = RD->field_end(); FI != FE; ++FI) { 1762 1763 if (VI == VE) 1764 break; 1765 1766 // Skip any unnamed bitfields to stay in sync with the initializers. 1767 if (FI->isUnnamedBitfield()) 1768 continue; 1769 1770 QualType FTy = FI->getType(); 1771 const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R); 1772 1773 if (FTy->isArrayType()) 1774 newStore = BindArray(newStore.getStore(), FR, *VI); 1775 else if (FTy->isStructureOrClassType()) 1776 newStore = BindStruct(newStore.getStore(), FR, *VI); 1777 else 1778 newStore = Bind(newStore.getStore(), svalBuilder.makeLoc(FR), *VI); 1779 ++VI; 1780 } 1781 1782 // There may be fewer values in the initialize list than the fields of struct. 1783 if (FI != FE) { 1784 RegionBindings B = GetRegionBindings(newStore.getStore()); 1785 B = addBinding(B, R, BindingKey::Default, svalBuilder.makeIntVal(0, false)); 1786 newStore = StoreRef(B.getRootWithoutRetain(), *this); 1787 } 1788 1789 return newStore; 1790} 1791 1792StoreRef RegionStoreManager::KillStruct(Store store, const TypedRegion* R, 1793 SVal DefaultVal) { 1794 BindingKey key = BindingKey::Make(R, BindingKey::Default); 1795 1796 // The BindingKey may be "invalid" if we cannot handle the region binding 1797 // explicitly. One example is something like array[index], where index 1798 // is a symbolic value. In such cases, we want to invalidate the entire 1799 // array, as the index assignment could have been to any element. In 1800 // the case of nested symbolic indices, we need to march up the region 1801 // hierarchy untile we reach a region whose binding we can reason about. 1802 const SubRegion *subReg = R; 1803 1804 while (!key.isValid()) { 1805 if (const SubRegion *tmp = dyn_cast<SubRegion>(subReg->getSuperRegion())) { 1806 subReg = tmp; 1807 key = BindingKey::Make(tmp, BindingKey::Default); 1808 } 1809 else 1810 break; 1811 } 1812 1813 // Remove the old bindings, using 'subReg' as the root of all regions 1814 // we will invalidate. 1815 RegionBindings B = GetRegionBindings(store); 1816 OwningPtr<RegionStoreSubRegionMap> 1817 SubRegions(getRegionStoreSubRegionMap(store)); 1818 RemoveSubRegionBindings(B, subReg, *SubRegions); 1819 1820 // Set the default value of the struct region to "unknown". 1821 if (!key.isValid()) 1822 return StoreRef(B.getRootWithoutRetain(), *this); 1823 1824 return StoreRef(addBinding(B, key, DefaultVal).getRootWithoutRetain(), *this); 1825} 1826 1827StoreRef RegionStoreManager::CopyLazyBindings(nonloc::LazyCompoundVal V, 1828 Store store, 1829 const TypedRegion *R) { 1830 1831 // Nuke the old bindings stemming from R. 1832 RegionBindings B = GetRegionBindings(store); 1833 1834 OwningPtr<RegionStoreSubRegionMap> 1835 SubRegions(getRegionStoreSubRegionMap(store)); 1836 1837 // B and DVM are updated after the call to RemoveSubRegionBindings. 1838 RemoveSubRegionBindings(B, R, *SubRegions.get()); 1839 1840 // Now copy the bindings. This amounts to just binding 'V' to 'R'. This 1841 // results in a zero-copy algorithm. 1842 return StoreRef(addBinding(B, R, BindingKey::Default, 1843 V).getRootWithoutRetain(), *this); 1844} 1845 1846//===----------------------------------------------------------------------===// 1847// "Raw" retrievals and bindings. 1848//===----------------------------------------------------------------------===// 1849 1850 1851RegionBindings RegionStoreManager::addBinding(RegionBindings B, BindingKey K, 1852 SVal V) { 1853 if (!K.isValid()) 1854 return B; 1855 return RBFactory.add(B, K, V); 1856} 1857 1858RegionBindings RegionStoreManager::addBinding(RegionBindings B, 1859 const MemRegion *R, 1860 BindingKey::Kind k, SVal V) { 1861 return addBinding(B, BindingKey::Make(R, k), V); 1862} 1863 1864const SVal *RegionStoreManager::lookup(RegionBindings B, BindingKey K) { 1865 if (!K.isValid()) 1866 return NULL; 1867 return B.lookup(K); 1868} 1869 1870const SVal *RegionStoreManager::lookup(RegionBindings B, 1871 const MemRegion *R, 1872 BindingKey::Kind k) { 1873 return lookup(B, BindingKey::Make(R, k)); 1874} 1875 1876RegionBindings RegionStoreManager::removeBinding(RegionBindings B, 1877 BindingKey K) { 1878 if (!K.isValid()) 1879 return B; 1880 return RBFactory.remove(B, K); 1881} 1882 1883RegionBindings RegionStoreManager::removeBinding(RegionBindings B, 1884 const MemRegion *R, 1885 BindingKey::Kind k){ 1886 return removeBinding(B, BindingKey::Make(R, k)); 1887} 1888 1889//===----------------------------------------------------------------------===// 1890// State pruning. 1891//===----------------------------------------------------------------------===// 1892 1893namespace { 1894class removeDeadBindingsWorker : 1895 public ClusterAnalysis<removeDeadBindingsWorker> { 1896 SmallVector<const SymbolicRegion*, 12> Postponed; 1897 SymbolReaper &SymReaper; 1898 const StackFrameContext *CurrentLCtx; 1899 1900public: 1901 removeDeadBindingsWorker(RegionStoreManager &rm, 1902 ProgramStateManager &stateMgr, 1903 RegionBindings b, SymbolReaper &symReaper, 1904 const StackFrameContext *LCtx) 1905 : ClusterAnalysis<removeDeadBindingsWorker>(rm, stateMgr, b, 1906 /* includeGlobals = */ false), 1907 SymReaper(symReaper), CurrentLCtx(LCtx) {} 1908 1909 // Called by ClusterAnalysis. 1910 void VisitAddedToCluster(const MemRegion *baseR, RegionCluster &C); 1911 void VisitCluster(const MemRegion *baseR, BindingKey *I, BindingKey *E); 1912 1913 void VisitBindingKey(BindingKey K); 1914 bool UpdatePostponed(); 1915 void VisitBinding(SVal V); 1916}; 1917} 1918 1919void removeDeadBindingsWorker::VisitAddedToCluster(const MemRegion *baseR, 1920 RegionCluster &C) { 1921 1922 if (const VarRegion *VR = dyn_cast<VarRegion>(baseR)) { 1923 if (SymReaper.isLive(VR)) 1924 AddToWorkList(baseR, C); 1925 1926 return; 1927 } 1928 1929 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) { 1930 if (SymReaper.isLive(SR->getSymbol())) 1931 AddToWorkList(SR, C); 1932 else 1933 Postponed.push_back(SR); 1934 1935 return; 1936 } 1937 1938 if (isa<NonStaticGlobalSpaceRegion>(baseR)) { 1939 AddToWorkList(baseR, C); 1940 return; 1941 } 1942 1943 // CXXThisRegion in the current or parent location context is live. 1944 if (const CXXThisRegion *TR = dyn_cast<CXXThisRegion>(baseR)) { 1945 const StackArgumentsSpaceRegion *StackReg = 1946 cast<StackArgumentsSpaceRegion>(TR->getSuperRegion()); 1947 const StackFrameContext *RegCtx = StackReg->getStackFrame(); 1948 if (RegCtx == CurrentLCtx || RegCtx->isParentOf(CurrentLCtx)) 1949 AddToWorkList(TR, C); 1950 } 1951} 1952 1953void removeDeadBindingsWorker::VisitCluster(const MemRegion *baseR, 1954 BindingKey *I, BindingKey *E) { 1955 for ( ; I != E; ++I) 1956 VisitBindingKey(*I); 1957} 1958 1959void removeDeadBindingsWorker::VisitBinding(SVal V) { 1960 // Is it a LazyCompoundVal? All referenced regions are live as well. 1961 if (const nonloc::LazyCompoundVal *LCS = 1962 dyn_cast<nonloc::LazyCompoundVal>(&V)) { 1963 1964 const MemRegion *LazyR = LCS->getRegion(); 1965 RegionBindings B = RegionStoreManager::GetRegionBindings(LCS->getStore()); 1966 for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){ 1967 const SubRegion *baseR = dyn_cast<SubRegion>(RI.getKey().getRegion()); 1968 if (baseR && baseR->isSubRegionOf(LazyR)) 1969 VisitBinding(RI.getData()); 1970 } 1971 return; 1972 } 1973 1974 // If V is a region, then add it to the worklist. 1975 if (const MemRegion *R = V.getAsRegion()) { 1976 AddToWorkList(R); 1977 1978 // All regions captured by a block are also live. 1979 if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(R)) { 1980 BlockDataRegion::referenced_vars_iterator I = BR->referenced_vars_begin(), 1981 E = BR->referenced_vars_end(); 1982 for ( ; I != E; ++I) 1983 AddToWorkList(I.getCapturedRegion()); 1984 } 1985 } 1986 1987 1988 // Update the set of live symbols. 1989 for (SymExpr::symbol_iterator SI = V.symbol_begin(), SE = V.symbol_end(); 1990 SI!=SE; ++SI) 1991 SymReaper.markLive(*SI); 1992} 1993 1994void removeDeadBindingsWorker::VisitBindingKey(BindingKey K) { 1995 const MemRegion *R = K.getRegion(); 1996 1997 // Mark this region "live" by adding it to the worklist. This will cause 1998 // use to visit all regions in the cluster (if we haven't visited them 1999 // already). 2000 if (AddToWorkList(R)) { 2001 // Mark the symbol for any live SymbolicRegion as "live". This means we 2002 // should continue to track that symbol. 2003 if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(R)) 2004 SymReaper.markLive(SymR->getSymbol()); 2005 } 2006 2007 // Visit the data binding for K. 2008 if (const SVal *V = RM.lookup(B, K)) 2009 VisitBinding(*V); 2010} 2011 2012bool removeDeadBindingsWorker::UpdatePostponed() { 2013 // See if any postponed SymbolicRegions are actually live now, after 2014 // having done a scan. 2015 bool changed = false; 2016 2017 for (SmallVectorImpl<const SymbolicRegion*>::iterator 2018 I = Postponed.begin(), E = Postponed.end() ; I != E ; ++I) { 2019 if (const SymbolicRegion *SR = cast_or_null<SymbolicRegion>(*I)) { 2020 if (SymReaper.isLive(SR->getSymbol())) { 2021 changed |= AddToWorkList(SR); 2022 *I = NULL; 2023 } 2024 } 2025 } 2026 2027 return changed; 2028} 2029 2030StoreRef RegionStoreManager::removeDeadBindings(Store store, 2031 const StackFrameContext *LCtx, 2032 SymbolReaper& SymReaper) { 2033 RegionBindings B = GetRegionBindings(store); 2034 removeDeadBindingsWorker W(*this, StateMgr, B, SymReaper, LCtx); 2035 W.GenerateClusters(); 2036 2037 // Enqueue the region roots onto the worklist. 2038 for (SymbolReaper::region_iterator I = SymReaper.region_begin(), 2039 E = SymReaper.region_end(); I != E; ++I) { 2040 W.AddToWorkList(*I); 2041 } 2042 2043 do W.RunWorkList(); while (W.UpdatePostponed()); 2044 2045 // We have now scanned the store, marking reachable regions and symbols 2046 // as live. We now remove all the regions that are dead from the store 2047 // as well as update DSymbols with the set symbols that are now dead. 2048 for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) { 2049 const BindingKey &K = I.getKey(); 2050 2051 // If the cluster has been visited, we know the region has been marked. 2052 if (W.isVisited(K.getRegion())) 2053 continue; 2054 2055 // Remove the dead entry. 2056 B = removeBinding(B, K); 2057 2058 // Mark all non-live symbols that this binding references as dead. 2059 if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(K.getRegion())) 2060 SymReaper.maybeDead(SymR->getSymbol()); 2061 2062 SVal X = I.getData(); 2063 SymExpr::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end(); 2064 for (; SI != SE; ++SI) 2065 SymReaper.maybeDead(*SI); 2066 } 2067 2068 return StoreRef(B.getRootWithoutRetain(), *this); 2069} 2070 2071//===----------------------------------------------------------------------===// 2072// Utility methods. 2073//===----------------------------------------------------------------------===// 2074 2075void RegionStoreManager::print(Store store, raw_ostream &OS, 2076 const char* nl, const char *sep) { 2077 RegionBindings B = GetRegionBindings(store); 2078 OS << "Store (direct and default bindings), " 2079 << (void*) B.getRootWithoutRetain() 2080 << " :" << nl; 2081 2082 for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) 2083 OS << ' ' << I.getKey() << " : " << I.getData() << nl; 2084} 2085