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