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