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