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