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