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