RegionStore.cpp revision 9d688e219caa37e60975ec8d5bebe74a176c9c2b
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 716static void collectSubRegionKeys(SmallVectorImpl<BindingKey> &Keys, 717 SValBuilder &SVB, 718 const ClusterBindings &Cluster, 719 const SubRegion *Top, BindingKey TopKey) { 720 FieldVector FieldsInSymbolicSubregions; 721 if (TopKey.hasSymbolicOffset()) { 722 getSymbolicOffsetFields(TopKey, FieldsInSymbolicSubregions); 723 Top = cast<SubRegion>(TopKey.getConcreteOffsetRegion()); 724 TopKey = BindingKey::Make(Top, BindingKey::Default); 725 } 726 727 // This assumes the region being invalidated is char-aligned. This isn't 728 // true for bitfields, but since bitfields have no subregions they shouldn't 729 // be using this function anyway. 730 uint64_t Length = UINT64_MAX; 731 SVal Extent = Top->getExtent(SVB); 732 if (nonloc::ConcreteInt *ExtentCI = dyn_cast<nonloc::ConcreteInt>(&Extent)) { 733 const llvm::APSInt &ExtentInt = ExtentCI->getValue(); 734 assert(ExtentInt.isNonNegative() || ExtentInt.isUnsigned()); 735 // Extents are in bytes but region offsets are in bits. Be careful! 736 Length = ExtentInt.getLimitedValue() * SVB.getContext().getCharWidth(); 737 } 738 739 for (ClusterBindings::iterator I = Cluster.begin(), E = Cluster.end(); 740 I != E; ++I) { 741 BindingKey NextKey = I.getKey(); 742 if (NextKey.getRegion() == TopKey.getRegion()) { 743 // FIXME: This doesn't catch the case where we're really invalidating a 744 // region with a symbolic offset. Example: 745 // R: points[i].y 746 // Next: points[0].x 747 748 if (NextKey.getOffset() > TopKey.getOffset() && 749 NextKey.getOffset() - TopKey.getOffset() < Length) { 750 // Case 1: The next binding is inside the region we're invalidating. 751 // Remove it. 752 Keys.push_back(NextKey); 753 754 } else if (NextKey.getOffset() == TopKey.getOffset()) { 755 // Case 2: The next binding is at the same offset as the region we're 756 // invalidating. In this case, we need to leave default bindings alone, 757 // since they may be providing a default value for a regions beyond what 758 // we're invalidating. 759 // FIXME: This is probably incorrect; consider invalidating an outer 760 // struct whose first field is bound to a LazyCompoundVal. 761 if (NextKey.isDirect()) 762 Keys.push_back(NextKey); 763 } 764 765 } else if (NextKey.hasSymbolicOffset()) { 766 const MemRegion *Base = NextKey.getConcreteOffsetRegion(); 767 if (Top->isSubRegionOf(Base)) { 768 // Case 3: The next key is symbolic and we just changed something within 769 // its concrete region. We don't know if the binding is still valid, so 770 // we'll be conservative and remove it. 771 if (NextKey.isDirect()) 772 if (isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions)) 773 Keys.push_back(NextKey); 774 } else if (const SubRegion *BaseSR = dyn_cast<SubRegion>(Base)) { 775 // Case 4: The next key is symbolic, but we changed a known 776 // super-region. In this case the binding is certainly no longer valid. 777 if (Top == Base || BaseSR->isSubRegionOf(Top)) 778 if (isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions)) 779 Keys.push_back(NextKey); 780 } 781 } 782 } 783} 784 785RegionBindingsRef 786RegionStoreManager::removeSubRegionBindings(RegionBindingsConstRef B, 787 const SubRegion *Top) { 788 BindingKey TopKey = BindingKey::Make(Top, BindingKey::Default); 789 const MemRegion *ClusterHead = TopKey.getBaseRegion(); 790 if (Top == ClusterHead) { 791 // We can remove an entire cluster's bindings all in one go. 792 return B.remove(Top); 793 } 794 795 const ClusterBindings *Cluster = B.lookup(ClusterHead); 796 if (!Cluster) 797 return B; 798 799 SmallVector<BindingKey, 32> Keys; 800 collectSubRegionKeys(Keys, svalBuilder, *Cluster, Top, TopKey); 801 802 ClusterBindingsRef Result(*Cluster, CBFactory); 803 for (SmallVectorImpl<BindingKey>::const_iterator I = Keys.begin(), 804 E = Keys.end(); 805 I != E; ++I) 806 Result = Result.remove(*I); 807 808 // If we're invalidating a region with a symbolic offset, we need to make sure 809 // we don't treat the base region as uninitialized anymore. 810 // FIXME: This isn't very precise; see the example in the loop. 811 if (TopKey.hasSymbolicOffset()) { 812 const SubRegion *Concrete = TopKey.getConcreteOffsetRegion(); 813 Result = Result.add(BindingKey::Make(Concrete, BindingKey::Default), 814 UnknownVal()); 815 } 816 817 if (Result.isEmpty()) 818 return B.remove(ClusterHead); 819 return B.add(ClusterHead, Result.asImmutableMap()); 820} 821 822namespace { 823class invalidateRegionsWorker : public ClusterAnalysis<invalidateRegionsWorker> 824{ 825 const Expr *Ex; 826 unsigned Count; 827 const LocationContext *LCtx; 828 InvalidatedSymbols &IS; 829 StoreManager::InvalidatedRegions *Regions; 830public: 831 invalidateRegionsWorker(RegionStoreManager &rm, 832 ProgramStateManager &stateMgr, 833 RegionBindingsRef b, 834 const Expr *ex, unsigned count, 835 const LocationContext *lctx, 836 InvalidatedSymbols &is, 837 StoreManager::InvalidatedRegions *r, 838 bool includeGlobals) 839 : ClusterAnalysis<invalidateRegionsWorker>(rm, stateMgr, b, includeGlobals), 840 Ex(ex), Count(count), LCtx(lctx), IS(is), Regions(r) {} 841 842 void VisitCluster(const MemRegion *baseR, const ClusterBindings &C); 843 void VisitBaseRegion(const MemRegion *baseR); 844 845private: 846 void VisitBinding(SVal V); 847}; 848} 849 850void invalidateRegionsWorker::VisitBinding(SVal V) { 851 // A symbol? Mark it touched by the invalidation. 852 if (SymbolRef Sym = V.getAsSymbol()) 853 IS.insert(Sym); 854 855 if (const MemRegion *R = V.getAsRegion()) { 856 AddToWorkList(R); 857 return; 858 } 859 860 // Is it a LazyCompoundVal? All references get invalidated as well. 861 if (const nonloc::LazyCompoundVal *LCS = 862 dyn_cast<nonloc::LazyCompoundVal>(&V)) { 863 864 const MemRegion *LazyR = LCS->getRegion(); 865 RegionBindingsRef B = RM.getRegionBindings(LCS->getStore()); 866 867 // FIXME: This should not have to walk all bindings in the old store. 868 for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){ 869 const ClusterBindings &Cluster = RI.getData(); 870 for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); 871 CI != CE; ++CI) { 872 BindingKey K = CI.getKey(); 873 if (const SubRegion *BaseR = dyn_cast<SubRegion>(K.getRegion())) { 874 if (BaseR == LazyR) 875 VisitBinding(CI.getData()); 876 else if (K.hasSymbolicOffset() && BaseR->isSubRegionOf(LazyR)) 877 VisitBinding(CI.getData()); 878 } 879 } 880 } 881 882 return; 883 } 884} 885 886void invalidateRegionsWorker::VisitCluster(const MemRegion *BaseR, 887 const ClusterBindings &C) { 888 for (ClusterBindings::iterator I = C.begin(), E = C.end(); I != E; ++I) 889 VisitBinding(I.getData()); 890 891 B = B.remove(BaseR); 892} 893 894void invalidateRegionsWorker::VisitBaseRegion(const MemRegion *baseR) { 895 // Symbolic region? Mark that symbol touched by the invalidation. 896 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) 897 IS.insert(SR->getSymbol()); 898 899 // BlockDataRegion? If so, invalidate captured variables that are passed 900 // by reference. 901 if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(baseR)) { 902 for (BlockDataRegion::referenced_vars_iterator 903 BI = BR->referenced_vars_begin(), BE = BR->referenced_vars_end() ; 904 BI != BE; ++BI) { 905 const VarRegion *VR = BI.getCapturedRegion(); 906 const VarDecl *VD = VR->getDecl(); 907 if (VD->getAttr<BlocksAttr>() || !VD->hasLocalStorage()) { 908 AddToWorkList(VR); 909 } 910 else if (Loc::isLocType(VR->getValueType())) { 911 // Map the current bindings to a Store to retrieve the value 912 // of the binding. If that binding itself is a region, we should 913 // invalidate that region. This is because a block may capture 914 // a pointer value, but the thing pointed by that pointer may 915 // get invalidated. 916 SVal V = RM.getBinding(B, loc::MemRegionVal(VR)); 917 if (const Loc *L = dyn_cast<Loc>(&V)) { 918 if (const MemRegion *LR = L->getAsRegion()) 919 AddToWorkList(LR); 920 } 921 } 922 } 923 return; 924 } 925 926 // Otherwise, we have a normal data region. Record that we touched the region. 927 if (Regions) 928 Regions->push_back(baseR); 929 930 if (isa<AllocaRegion>(baseR) || isa<SymbolicRegion>(baseR)) { 931 // Invalidate the region by setting its default value to 932 // conjured symbol. The type of the symbol is irrelavant. 933 DefinedOrUnknownSVal V = 934 svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, Ctx.IntTy, Count); 935 B = B.addBinding(baseR, BindingKey::Default, V); 936 return; 937 } 938 939 if (!baseR->isBoundable()) 940 return; 941 942 const TypedValueRegion *TR = cast<TypedValueRegion>(baseR); 943 QualType T = TR->getValueType(); 944 945 // Invalidate the binding. 946 if (T->isStructureOrClassType()) { 947 // Invalidate the region by setting its default value to 948 // conjured symbol. The type of the symbol is irrelavant. 949 DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, 950 Ctx.IntTy, Count); 951 B = B.addBinding(baseR, BindingKey::Default, V); 952 return; 953 } 954 955 if (const ArrayType *AT = Ctx.getAsArrayType(T)) { 956 // Set the default value of the array to conjured symbol. 957 DefinedOrUnknownSVal V = 958 svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, 959 AT->getElementType(), Count); 960 B = B.addBinding(baseR, BindingKey::Default, V); 961 return; 962 } 963 964 if (includeGlobals && 965 isa<NonStaticGlobalSpaceRegion>(baseR->getMemorySpace())) { 966 // If the region is a global and we are invalidating all globals, 967 // just erase the entry. This causes all globals to be lazily 968 // symbolicated from the same base symbol. 969 B = B.removeBinding(baseR); 970 return; 971 } 972 973 974 DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, 975 T,Count); 976 assert(SymbolManager::canSymbolicate(T) || V.isUnknown()); 977 B = B.addBinding(baseR, BindingKey::Direct, V); 978} 979 980RegionBindingsRef 981RegionStoreManager::invalidateGlobalRegion(MemRegion::Kind K, 982 const Expr *Ex, 983 unsigned Count, 984 const LocationContext *LCtx, 985 RegionBindingsRef B, 986 InvalidatedRegions *Invalidated) { 987 // Bind the globals memory space to a new symbol that we will use to derive 988 // the bindings for all globals. 989 const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion(K); 990 SVal V = svalBuilder.conjureSymbolVal(/* SymbolTag = */ (const void*) GS, Ex, LCtx, 991 /* type does not matter */ Ctx.IntTy, 992 Count); 993 994 B = B.removeBinding(GS) 995 .addBinding(BindingKey::Make(GS, BindingKey::Default), V); 996 997 // Even if there are no bindings in the global scope, we still need to 998 // record that we touched it. 999 if (Invalidated) 1000 Invalidated->push_back(GS); 1001 1002 return B; 1003} 1004 1005StoreRef 1006RegionStoreManager::invalidateRegions(Store store, 1007 ArrayRef<const MemRegion *> Regions, 1008 const Expr *Ex, unsigned Count, 1009 const LocationContext *LCtx, 1010 InvalidatedSymbols &IS, 1011 const CallEvent *Call, 1012 InvalidatedRegions *Invalidated) { 1013 invalidateRegionsWorker W(*this, StateMgr, 1014 RegionStoreManager::getRegionBindings(store), 1015 Ex, Count, LCtx, IS, Invalidated, false); 1016 1017 // Scan the bindings and generate the clusters. 1018 W.GenerateClusters(); 1019 1020 // Add the regions to the worklist. 1021 for (ArrayRef<const MemRegion *>::iterator 1022 I = Regions.begin(), E = Regions.end(); I != E; ++I) 1023 W.AddToWorkList(*I); 1024 1025 W.RunWorkList(); 1026 1027 // Return the new bindings. 1028 RegionBindingsRef B = W.getRegionBindings(); 1029 1030 // For all globals which are not static nor immutable: determine which global 1031 // regions should be invalidated and invalidate them. 1032 // TODO: This could possibly be more precise with modules. 1033 // 1034 // System calls invalidate only system globals. 1035 if (Call && Call->isInSystemHeader()) { 1036 B = invalidateGlobalRegion(MemRegion::GlobalSystemSpaceRegionKind, 1037 Ex, Count, LCtx, B, Invalidated); 1038 // Internal calls might invalidate both system and internal globals. 1039 } else { 1040 B = invalidateGlobalRegion(MemRegion::GlobalSystemSpaceRegionKind, 1041 Ex, Count, LCtx, B, Invalidated); 1042 B = invalidateGlobalRegion(MemRegion::GlobalInternalSpaceRegionKind, 1043 Ex, Count, LCtx, B, Invalidated); 1044 } 1045 1046 return StoreRef(B.asStore(), *this); 1047} 1048 1049//===----------------------------------------------------------------------===// 1050// Extents for regions. 1051//===----------------------------------------------------------------------===// 1052 1053DefinedOrUnknownSVal 1054RegionStoreManager::getSizeInElements(ProgramStateRef state, 1055 const MemRegion *R, 1056 QualType EleTy) { 1057 SVal Size = cast<SubRegion>(R)->getExtent(svalBuilder); 1058 const llvm::APSInt *SizeInt = svalBuilder.getKnownValue(state, Size); 1059 if (!SizeInt) 1060 return UnknownVal(); 1061 1062 CharUnits RegionSize = CharUnits::fromQuantity(SizeInt->getSExtValue()); 1063 1064 if (Ctx.getAsVariableArrayType(EleTy)) { 1065 // FIXME: We need to track extra state to properly record the size 1066 // of VLAs. Returning UnknownVal here, however, is a stop-gap so that 1067 // we don't have a divide-by-zero below. 1068 return UnknownVal(); 1069 } 1070 1071 CharUnits EleSize = Ctx.getTypeSizeInChars(EleTy); 1072 1073 // If a variable is reinterpreted as a type that doesn't fit into a larger 1074 // type evenly, round it down. 1075 // This is a signed value, since it's used in arithmetic with signed indices. 1076 return svalBuilder.makeIntVal(RegionSize / EleSize, false); 1077} 1078 1079//===----------------------------------------------------------------------===// 1080// Location and region casting. 1081//===----------------------------------------------------------------------===// 1082 1083/// ArrayToPointer - Emulates the "decay" of an array to a pointer 1084/// type. 'Array' represents the lvalue of the array being decayed 1085/// to a pointer, and the returned SVal represents the decayed 1086/// version of that lvalue (i.e., a pointer to the first element of 1087/// the array). This is called by ExprEngine when evaluating casts 1088/// from arrays to pointers. 1089SVal RegionStoreManager::ArrayToPointer(Loc Array) { 1090 if (!isa<loc::MemRegionVal>(Array)) 1091 return UnknownVal(); 1092 1093 const MemRegion* R = cast<loc::MemRegionVal>(&Array)->getRegion(); 1094 const TypedValueRegion* ArrayR = dyn_cast<TypedValueRegion>(R); 1095 1096 if (!ArrayR) 1097 return UnknownVal(); 1098 1099 // Strip off typedefs from the ArrayRegion's ValueType. 1100 QualType T = ArrayR->getValueType().getDesugaredType(Ctx); 1101 const ArrayType *AT = cast<ArrayType>(T); 1102 T = AT->getElementType(); 1103 1104 NonLoc ZeroIdx = svalBuilder.makeZeroArrayIndex(); 1105 return loc::MemRegionVal(MRMgr.getElementRegion(T, ZeroIdx, ArrayR, Ctx)); 1106} 1107 1108//===----------------------------------------------------------------------===// 1109// Loading values from regions. 1110//===----------------------------------------------------------------------===// 1111 1112SVal RegionStoreManager::getBinding(RegionBindingsConstRef B, Loc L, QualType T) { 1113 assert(!isa<UnknownVal>(L) && "location unknown"); 1114 assert(!isa<UndefinedVal>(L) && "location undefined"); 1115 1116 // For access to concrete addresses, return UnknownVal. Checks 1117 // for null dereferences (and similar errors) are done by checkers, not 1118 // the Store. 1119 // FIXME: We can consider lazily symbolicating such memory, but we really 1120 // should defer this when we can reason easily about symbolicating arrays 1121 // of bytes. 1122 if (isa<loc::ConcreteInt>(L)) { 1123 return UnknownVal(); 1124 } 1125 if (!isa<loc::MemRegionVal>(L)) { 1126 return UnknownVal(); 1127 } 1128 1129 const MemRegion *MR = cast<loc::MemRegionVal>(L).getRegion(); 1130 1131 if (isa<AllocaRegion>(MR) || 1132 isa<SymbolicRegion>(MR) || 1133 isa<CodeTextRegion>(MR)) { 1134 if (T.isNull()) { 1135 if (const TypedRegion *TR = dyn_cast<TypedRegion>(MR)) 1136 T = TR->getLocationType(); 1137 else { 1138 const SymbolicRegion *SR = cast<SymbolicRegion>(MR); 1139 T = SR->getSymbol()->getType(); 1140 } 1141 } 1142 MR = GetElementZeroRegion(MR, T); 1143 } 1144 1145 // FIXME: Perhaps this method should just take a 'const MemRegion*' argument 1146 // instead of 'Loc', and have the other Loc cases handled at a higher level. 1147 const TypedValueRegion *R = cast<TypedValueRegion>(MR); 1148 QualType RTy = R->getValueType(); 1149 1150 // FIXME: we do not yet model the parts of a complex type, so treat the 1151 // whole thing as "unknown". 1152 if (RTy->isAnyComplexType()) 1153 return UnknownVal(); 1154 1155 // FIXME: We should eventually handle funny addressing. e.g.: 1156 // 1157 // int x = ...; 1158 // int *p = &x; 1159 // char *q = (char*) p; 1160 // char c = *q; // returns the first byte of 'x'. 1161 // 1162 // Such funny addressing will occur due to layering of regions. 1163 if (RTy->isStructureOrClassType()) 1164 return getBindingForStruct(B, R); 1165 1166 // FIXME: Handle unions. 1167 if (RTy->isUnionType()) 1168 return UnknownVal(); 1169 1170 if (RTy->isArrayType()) { 1171 if (RTy->isConstantArrayType()) 1172 return getBindingForArray(B, R); 1173 else 1174 return UnknownVal(); 1175 } 1176 1177 // FIXME: handle Vector types. 1178 if (RTy->isVectorType()) 1179 return UnknownVal(); 1180 1181 if (const FieldRegion* FR = dyn_cast<FieldRegion>(R)) 1182 return CastRetrievedVal(getBindingForField(B, FR), FR, T, false); 1183 1184 if (const ElementRegion* ER = dyn_cast<ElementRegion>(R)) { 1185 // FIXME: Here we actually perform an implicit conversion from the loaded 1186 // value to the element type. Eventually we want to compose these values 1187 // more intelligently. For example, an 'element' can encompass multiple 1188 // bound regions (e.g., several bound bytes), or could be a subset of 1189 // a larger value. 1190 return CastRetrievedVal(getBindingForElement(B, ER), ER, T, false); 1191 } 1192 1193 if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) { 1194 // FIXME: Here we actually perform an implicit conversion from the loaded 1195 // value to the ivar type. What we should model is stores to ivars 1196 // that blow past the extent of the ivar. If the address of the ivar is 1197 // reinterpretted, it is possible we stored a different value that could 1198 // fit within the ivar. Either we need to cast these when storing them 1199 // or reinterpret them lazily (as we do here). 1200 return CastRetrievedVal(getBindingForObjCIvar(B, IVR), IVR, T, false); 1201 } 1202 1203 if (const VarRegion *VR = dyn_cast<VarRegion>(R)) { 1204 // FIXME: Here we actually perform an implicit conversion from the loaded 1205 // value to the variable type. What we should model is stores to variables 1206 // that blow past the extent of the variable. If the address of the 1207 // variable is reinterpretted, it is possible we stored a different value 1208 // that could fit within the variable. Either we need to cast these when 1209 // storing them or reinterpret them lazily (as we do here). 1210 return CastRetrievedVal(getBindingForVar(B, VR), VR, T, false); 1211 } 1212 1213 const SVal *V = B.lookup(R, BindingKey::Direct); 1214 1215 // Check if the region has a binding. 1216 if (V) 1217 return *V; 1218 1219 // The location does not have a bound value. This means that it has 1220 // the value it had upon its creation and/or entry to the analyzed 1221 // function/method. These are either symbolic values or 'undefined'. 1222 if (R->hasStackNonParametersStorage()) { 1223 // All stack variables are considered to have undefined values 1224 // upon creation. All heap allocated blocks are considered to 1225 // have undefined values as well unless they are explicitly bound 1226 // to specific values. 1227 return UndefinedVal(); 1228 } 1229 1230 // All other values are symbolic. 1231 return svalBuilder.getRegionValueSymbolVal(R); 1232} 1233 1234std::pair<Store, const MemRegion *> 1235RegionStoreManager::getLazyBinding(RegionBindingsConstRef B, 1236 const MemRegion *R, 1237 const MemRegion *originalRegion) { 1238 if (originalRegion != R) { 1239 if (Optional<SVal> OV = B.getDefaultBinding(R)) { 1240 if (const nonloc::LazyCompoundVal *V = 1241 dyn_cast<nonloc::LazyCompoundVal>(OV.getPointer())) 1242 return std::make_pair(V->getStore(), V->getRegion()); 1243 } 1244 } 1245 1246 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) { 1247 const std::pair<Store, const MemRegion *> &X = 1248 getLazyBinding(B, ER->getSuperRegion(), originalRegion); 1249 1250 if (X.second) 1251 return std::make_pair(X.first, 1252 MRMgr.getElementRegionWithSuper(ER, X.second)); 1253 } 1254 else if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) { 1255 const std::pair<Store, const MemRegion *> &X = 1256 getLazyBinding(B, FR->getSuperRegion(), originalRegion); 1257 1258 if (X.second) { 1259 return std::make_pair(X.first, 1260 MRMgr.getFieldRegionWithSuper(FR, X.second)); 1261 } 1262 1263 } 1264 // C++ base object region is another kind of region that we should blast 1265 // through to look for lazy compound value. It is like a field region. 1266 else if (const CXXBaseObjectRegion *baseReg = 1267 dyn_cast<CXXBaseObjectRegion>(R)) { 1268 const std::pair<Store, const MemRegion *> &X = 1269 getLazyBinding(B, baseReg->getSuperRegion(), originalRegion); 1270 1271 if (X.second) { 1272 return std::make_pair(X.first, 1273 MRMgr.getCXXBaseObjectRegionWithSuper(baseReg, 1274 X.second)); 1275 } 1276 } 1277 1278 // The NULL MemRegion indicates an non-existent lazy binding. A NULL Store is 1279 // possible for a valid lazy binding. 1280 return std::make_pair((Store) 0, (const MemRegion *) 0); 1281} 1282 1283SVal RegionStoreManager::getBindingForElement(RegionBindingsConstRef B, 1284 const ElementRegion* R) { 1285 // We do not currently model bindings of the CompoundLiteralregion. 1286 if (isa<CompoundLiteralRegion>(R->getBaseRegion())) 1287 return UnknownVal(); 1288 1289 // Check if the region has a binding. 1290 if (const Optional<SVal> &V = B.getDirectBinding(R)) 1291 return *V; 1292 1293 const MemRegion* superR = R->getSuperRegion(); 1294 1295 // Check if the region is an element region of a string literal. 1296 if (const StringRegion *StrR=dyn_cast<StringRegion>(superR)) { 1297 // FIXME: Handle loads from strings where the literal is treated as 1298 // an integer, e.g., *((unsigned int*)"hello") 1299 QualType T = Ctx.getAsArrayType(StrR->getValueType())->getElementType(); 1300 if (T != Ctx.getCanonicalType(R->getElementType())) 1301 return UnknownVal(); 1302 1303 const StringLiteral *Str = StrR->getStringLiteral(); 1304 SVal Idx = R->getIndex(); 1305 if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&Idx)) { 1306 int64_t i = CI->getValue().getSExtValue(); 1307 // Abort on string underrun. This can be possible by arbitrary 1308 // clients of getBindingForElement(). 1309 if (i < 0) 1310 return UndefinedVal(); 1311 int64_t length = Str->getLength(); 1312 // Technically, only i == length is guaranteed to be null. 1313 // However, such overflows should be caught before reaching this point; 1314 // the only time such an access would be made is if a string literal was 1315 // used to initialize a larger array. 1316 char c = (i >= length) ? '\0' : Str->getCodeUnit(i); 1317 return svalBuilder.makeIntVal(c, T); 1318 } 1319 } 1320 1321 // Check for loads from a code text region. For such loads, just give up. 1322 if (isa<CodeTextRegion>(superR)) 1323 return UnknownVal(); 1324 1325 // Handle the case where we are indexing into a larger scalar object. 1326 // For example, this handles: 1327 // int x = ... 1328 // char *y = &x; 1329 // return *y; 1330 // FIXME: This is a hack, and doesn't do anything really intelligent yet. 1331 const RegionRawOffset &O = R->getAsArrayOffset(); 1332 1333 // If we cannot reason about the offset, return an unknown value. 1334 if (!O.getRegion()) 1335 return UnknownVal(); 1336 1337 if (const TypedValueRegion *baseR = 1338 dyn_cast_or_null<TypedValueRegion>(O.getRegion())) { 1339 QualType baseT = baseR->getValueType(); 1340 if (baseT->isScalarType()) { 1341 QualType elemT = R->getElementType(); 1342 if (elemT->isScalarType()) { 1343 if (Ctx.getTypeSizeInChars(baseT) >= Ctx.getTypeSizeInChars(elemT)) { 1344 if (const Optional<SVal> &V = B.getDirectBinding(superR)) { 1345 if (SymbolRef parentSym = V->getAsSymbol()) 1346 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); 1347 1348 if (V->isUnknownOrUndef()) 1349 return *V; 1350 // Other cases: give up. We are indexing into a larger object 1351 // that has some value, but we don't know how to handle that yet. 1352 return UnknownVal(); 1353 } 1354 } 1355 } 1356 } 1357 } 1358 return getBindingForFieldOrElementCommon(B, R, R->getElementType(), 1359 superR); 1360} 1361 1362SVal RegionStoreManager::getBindingForField(RegionBindingsConstRef B, 1363 const FieldRegion* R) { 1364 1365 // Check if the region has a binding. 1366 if (const Optional<SVal> &V = B.getDirectBinding(R)) 1367 return *V; 1368 1369 QualType Ty = R->getValueType(); 1370 return getBindingForFieldOrElementCommon(B, R, Ty, R->getSuperRegion()); 1371} 1372 1373Optional<SVal> 1374RegionStoreManager::getBindingForDerivedDefaultValue(RegionBindingsConstRef B, 1375 const MemRegion *superR, 1376 const TypedValueRegion *R, 1377 QualType Ty) { 1378 1379 if (const Optional<SVal> &D = B.getDefaultBinding(superR)) { 1380 const SVal &val = D.getValue(); 1381 if (SymbolRef parentSym = val.getAsSymbol()) 1382 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); 1383 1384 if (val.isZeroConstant()) 1385 return svalBuilder.makeZeroVal(Ty); 1386 1387 if (val.isUnknownOrUndef()) 1388 return val; 1389 1390 // Lazy bindings are handled later. 1391 if (isa<nonloc::LazyCompoundVal>(val)) 1392 return Optional<SVal>(); 1393 1394 llvm_unreachable("Unknown default value"); 1395 } 1396 1397 return Optional<SVal>(); 1398} 1399 1400SVal RegionStoreManager::getLazyBinding(const MemRegion *LazyBindingRegion, 1401 RegionBindingsRef LazyBinding) { 1402 SVal Result; 1403 if (const ElementRegion *ER = dyn_cast<ElementRegion>(LazyBindingRegion)) 1404 Result = getBindingForElement(LazyBinding, ER); 1405 else 1406 Result = getBindingForField(LazyBinding, 1407 cast<FieldRegion>(LazyBindingRegion)); 1408 1409 // This is a hack to deal with RegionStore's inability to distinguish a 1410 // default value for /part/ of an aggregate from a default value for the 1411 // /entire/ aggregate. The most common case of this is when struct Outer 1412 // has as its first member a struct Inner, which is copied in from a stack 1413 // variable. In this case, even if the Outer's default value is symbolic, 0, 1414 // or unknown, it gets overridden by the Inner's default value of undefined. 1415 // 1416 // This is a general problem -- if the Inner is zero-initialized, the Outer 1417 // will now look zero-initialized. The proper way to solve this is with a 1418 // new version of RegionStore that tracks the extent of a binding as well 1419 // as the offset. 1420 // 1421 // This hack only takes care of the undefined case because that can very 1422 // quickly result in a warning. 1423 if (Result.isUndef()) 1424 Result = UnknownVal(); 1425 1426 return Result; 1427} 1428 1429SVal 1430RegionStoreManager::getBindingForFieldOrElementCommon(RegionBindingsConstRef B, 1431 const TypedValueRegion *R, 1432 QualType Ty, 1433 const MemRegion *superR) { 1434 1435 // At this point we have already checked in either getBindingForElement or 1436 // getBindingForField if 'R' has a direct binding. 1437 1438 // Lazy binding? 1439 Store lazyBindingStore = NULL; 1440 const MemRegion *lazyBindingRegion = NULL; 1441 llvm::tie(lazyBindingStore, lazyBindingRegion) = getLazyBinding(B, R, R); 1442 if (lazyBindingRegion) 1443 return getLazyBinding(lazyBindingRegion, 1444 getRegionBindings(lazyBindingStore)); 1445 1446 // Record whether or not we see a symbolic index. That can completely 1447 // be out of scope of our lookup. 1448 bool hasSymbolicIndex = false; 1449 1450 while (superR) { 1451 if (const Optional<SVal> &D = 1452 getBindingForDerivedDefaultValue(B, superR, R, Ty)) 1453 return *D; 1454 1455 if (const ElementRegion *ER = dyn_cast<ElementRegion>(superR)) { 1456 NonLoc index = ER->getIndex(); 1457 if (!index.isConstant()) 1458 hasSymbolicIndex = true; 1459 } 1460 1461 // If our super region is a field or element itself, walk up the region 1462 // hierarchy to see if there is a default value installed in an ancestor. 1463 if (const SubRegion *SR = dyn_cast<SubRegion>(superR)) { 1464 superR = SR->getSuperRegion(); 1465 continue; 1466 } 1467 break; 1468 } 1469 1470 if (R->hasStackNonParametersStorage()) { 1471 if (isa<ElementRegion>(R)) { 1472 // Currently we don't reason specially about Clang-style vectors. Check 1473 // if superR is a vector and if so return Unknown. 1474 if (const TypedValueRegion *typedSuperR = 1475 dyn_cast<TypedValueRegion>(superR)) { 1476 if (typedSuperR->getValueType()->isVectorType()) 1477 return UnknownVal(); 1478 } 1479 } 1480 1481 // FIXME: We also need to take ElementRegions with symbolic indexes into 1482 // account. This case handles both directly accessing an ElementRegion 1483 // with a symbolic offset, but also fields within an element with 1484 // a symbolic offset. 1485 if (hasSymbolicIndex) 1486 return UnknownVal(); 1487 1488 return UndefinedVal(); 1489 } 1490 1491 // All other values are symbolic. 1492 return svalBuilder.getRegionValueSymbolVal(R); 1493} 1494 1495SVal RegionStoreManager::getBindingForObjCIvar(RegionBindingsConstRef B, 1496 const ObjCIvarRegion* R) { 1497 // Check if the region has a binding. 1498 if (const Optional<SVal> &V = B.getDirectBinding(R)) 1499 return *V; 1500 1501 const MemRegion *superR = R->getSuperRegion(); 1502 1503 // Check if the super region has a default binding. 1504 if (const Optional<SVal> &V = B.getDefaultBinding(superR)) { 1505 if (SymbolRef parentSym = V->getAsSymbol()) 1506 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); 1507 1508 // Other cases: give up. 1509 return UnknownVal(); 1510 } 1511 1512 return getBindingForLazySymbol(R); 1513} 1514 1515static Optional<SVal> getConstValue(SValBuilder &SVB, const VarDecl *VD) { 1516 ASTContext &Ctx = SVB.getContext(); 1517 if (!VD->getType().isConstQualified()) 1518 return Optional<SVal>(); 1519 1520 const Expr *Init = VD->getInit(); 1521 if (!Init) 1522 return Optional<SVal>(); 1523 1524 llvm::APSInt Result; 1525 if (Init->EvaluateAsInt(Result, Ctx)) 1526 return SVB.makeIntVal(Result); 1527 1528 if (Init->isNullPointerConstant(Ctx, Expr::NPC_ValueDependentIsNotNull)) 1529 return SVB.makeNull(); 1530 1531 // FIXME: Handle other possible constant expressions. 1532 return Optional<SVal>(); 1533} 1534 1535SVal RegionStoreManager::getBindingForVar(RegionBindingsConstRef B, 1536 const VarRegion *R) { 1537 1538 // Check if the region has a binding. 1539 if (const Optional<SVal> &V = B.getDirectBinding(R)) 1540 return *V; 1541 1542 // Lazily derive a value for the VarRegion. 1543 const VarDecl *VD = R->getDecl(); 1544 const MemSpaceRegion *MS = R->getMemorySpace(); 1545 1546 // Arguments are always symbolic. 1547 if (isa<StackArgumentsSpaceRegion>(MS)) 1548 return svalBuilder.getRegionValueSymbolVal(R); 1549 1550 // Is 'VD' declared constant? If so, retrieve the constant value. 1551 if (Optional<SVal> V = getConstValue(svalBuilder, VD)) 1552 return *V; 1553 1554 // This must come after the check for constants because closure-captured 1555 // constant variables may appear in UnknownSpaceRegion. 1556 if (isa<UnknownSpaceRegion>(MS)) 1557 return svalBuilder.getRegionValueSymbolVal(R); 1558 1559 if (isa<GlobalsSpaceRegion>(MS)) { 1560 QualType T = VD->getType(); 1561 1562 // Function-scoped static variables are default-initialized to 0; if they 1563 // have an initializer, it would have been processed by now. 1564 if (isa<StaticGlobalSpaceRegion>(MS)) 1565 return svalBuilder.makeZeroVal(T); 1566 1567 if (Optional<SVal> V = getBindingForDerivedDefaultValue(B, MS, R, T)) 1568 return V.getValue(); 1569 1570 return svalBuilder.getRegionValueSymbolVal(R); 1571 } 1572 1573 return UndefinedVal(); 1574} 1575 1576SVal RegionStoreManager::getBindingForLazySymbol(const TypedValueRegion *R) { 1577 // All other values are symbolic. 1578 return svalBuilder.getRegionValueSymbolVal(R); 1579} 1580 1581NonLoc RegionStoreManager::createLazyBinding(RegionBindingsConstRef B, 1582 const TypedValueRegion *R) { 1583 // If we already have a lazy binding, and it's for the whole structure, 1584 // don't create a new lazy binding. 1585 if (Optional<SVal> V = B.getDefaultBinding(R)) { 1586 const nonloc::LazyCompoundVal *LCV = 1587 dyn_cast<nonloc::LazyCompoundVal>(V.getPointer()); 1588 if (LCV) { 1589 QualType RegionTy = R->getValueType(); 1590 QualType SourceRegionTy = LCV->getRegion()->getValueType(); 1591 if (RegionTy.getCanonicalType() == SourceRegionTy.getCanonicalType()) 1592 return *LCV; 1593 } 1594 } 1595 1596 return svalBuilder.makeLazyCompoundVal(StoreRef(B.asStore(), *this), R); 1597} 1598 1599SVal RegionStoreManager::getBindingForStruct(RegionBindingsConstRef B, 1600 const TypedValueRegion *R) { 1601 const RecordDecl *RD = R->getValueType()->castAs<RecordType>()->getDecl(); 1602 if (RD->field_empty()) 1603 return UnknownVal(); 1604 1605 return createLazyBinding(B, R); 1606} 1607 1608SVal RegionStoreManager::getBindingForArray(RegionBindingsConstRef B, 1609 const TypedValueRegion *R) { 1610 assert(Ctx.getAsConstantArrayType(R->getValueType()) && 1611 "Only constant array types can have compound bindings."); 1612 1613 return createLazyBinding(B, R); 1614} 1615 1616bool RegionStoreManager::includedInBindings(Store store, 1617 const MemRegion *region) const { 1618 RegionBindingsRef B = getRegionBindings(store); 1619 region = region->getBaseRegion(); 1620 1621 // Quick path: if the base is the head of a cluster, the region is live. 1622 if (B.lookup(region)) 1623 return true; 1624 1625 // Slow path: if the region is the VALUE of any binding, it is live. 1626 for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI) { 1627 const ClusterBindings &Cluster = RI.getData(); 1628 for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); 1629 CI != CE; ++CI) { 1630 const SVal &D = CI.getData(); 1631 if (const MemRegion *R = D.getAsRegion()) 1632 if (R->getBaseRegion() == region) 1633 return true; 1634 } 1635 } 1636 1637 return false; 1638} 1639 1640//===----------------------------------------------------------------------===// 1641// Binding values to regions. 1642//===----------------------------------------------------------------------===// 1643 1644StoreRef RegionStoreManager::killBinding(Store ST, Loc L) { 1645 if (isa<loc::MemRegionVal>(L)) 1646 if (const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion()) 1647 return StoreRef(getRegionBindings(ST).removeBinding(R) 1648 .asImmutableMap() 1649 .getRootWithoutRetain(), 1650 *this); 1651 1652 return StoreRef(ST, *this); 1653} 1654 1655RegionBindingsRef 1656RegionStoreManager::bind(RegionBindingsConstRef B, Loc L, SVal V) { 1657 if (isa<loc::ConcreteInt>(L)) 1658 return B; 1659 1660 // If we get here, the location should be a region. 1661 const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion(); 1662 1663 // Check if the region is a struct region. 1664 if (const TypedValueRegion* TR = dyn_cast<TypedValueRegion>(R)) { 1665 QualType Ty = TR->getValueType(); 1666 if (Ty->isArrayType()) 1667 return bindArray(B, TR, V); 1668 if (Ty->isStructureOrClassType()) 1669 return bindStruct(B, TR, V); 1670 if (Ty->isVectorType()) 1671 return bindVector(B, TR, V); 1672 } 1673 1674 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) { 1675 // Binding directly to a symbolic region should be treated as binding 1676 // to element 0. 1677 QualType T = SR->getSymbol()->getType(); 1678 if (T->isAnyPointerType() || T->isReferenceType()) 1679 T = T->getPointeeType(); 1680 1681 R = GetElementZeroRegion(SR, T); 1682 } 1683 1684 // Clear out bindings that may overlap with this binding. 1685 RegionBindingsRef NewB = removeSubRegionBindings(B, cast<SubRegion>(R)); 1686 return NewB.addBinding(BindingKey::Make(R, BindingKey::Direct), V); 1687} 1688 1689// FIXME: this method should be merged into Bind(). 1690StoreRef RegionStoreManager::bindCompoundLiteral(Store ST, 1691 const CompoundLiteralExpr *CL, 1692 const LocationContext *LC, 1693 SVal V) { 1694 return Bind(ST, loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL, LC)), V); 1695} 1696 1697RegionBindingsRef 1698RegionStoreManager::setImplicitDefaultValue(RegionBindingsConstRef B, 1699 const MemRegion *R, 1700 QualType T) { 1701 SVal V; 1702 1703 if (Loc::isLocType(T)) 1704 V = svalBuilder.makeNull(); 1705 else if (T->isIntegerType()) 1706 V = svalBuilder.makeZeroVal(T); 1707 else if (T->isStructureOrClassType() || T->isArrayType()) { 1708 // Set the default value to a zero constant when it is a structure 1709 // or array. The type doesn't really matter. 1710 V = svalBuilder.makeZeroVal(Ctx.IntTy); 1711 } 1712 else { 1713 // We can't represent values of this type, but we still need to set a value 1714 // to record that the region has been initialized. 1715 // If this assertion ever fires, a new case should be added above -- we 1716 // should know how to default-initialize any value we can symbolicate. 1717 assert(!SymbolManager::canSymbolicate(T) && "This type is representable"); 1718 V = UnknownVal(); 1719 } 1720 1721 return B.addBinding(R, BindingKey::Default, V); 1722} 1723 1724RegionBindingsRef 1725RegionStoreManager::bindArray(RegionBindingsConstRef B, 1726 const TypedValueRegion* R, 1727 SVal Init) { 1728 1729 const ArrayType *AT =cast<ArrayType>(Ctx.getCanonicalType(R->getValueType())); 1730 QualType ElementTy = AT->getElementType(); 1731 Optional<uint64_t> Size; 1732 1733 if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(AT)) 1734 Size = CAT->getSize().getZExtValue(); 1735 1736 // Check if the init expr is a string literal. 1737 if (loc::MemRegionVal *MRV = dyn_cast<loc::MemRegionVal>(&Init)) { 1738 const StringRegion *S = cast<StringRegion>(MRV->getRegion()); 1739 1740 // Treat the string as a lazy compound value. 1741 StoreRef store(B.asStore(), *this); 1742 nonloc::LazyCompoundVal LCV = 1743 cast<nonloc::LazyCompoundVal>(svalBuilder.makeLazyCompoundVal(store, S)); 1744 return bindAggregate(B, R, LCV); 1745 } 1746 1747 // Handle lazy compound values. 1748 if (isa<nonloc::LazyCompoundVal>(Init)) 1749 return bindAggregate(B, R, Init); 1750 1751 // Remaining case: explicit compound values. 1752 1753 if (Init.isUnknown()) 1754 return setImplicitDefaultValue(B, R, ElementTy); 1755 1756 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(Init); 1757 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); 1758 uint64_t i = 0; 1759 1760 RegionBindingsRef NewB(B); 1761 1762 for (; Size.hasValue() ? i < Size.getValue() : true ; ++i, ++VI) { 1763 // The init list might be shorter than the array length. 1764 if (VI == VE) 1765 break; 1766 1767 const NonLoc &Idx = svalBuilder.makeArrayIndex(i); 1768 const ElementRegion *ER = MRMgr.getElementRegion(ElementTy, Idx, R, Ctx); 1769 1770 if (ElementTy->isStructureOrClassType()) 1771 NewB = bindStruct(NewB, ER, *VI); 1772 else if (ElementTy->isArrayType()) 1773 NewB = bindArray(NewB, ER, *VI); 1774 else 1775 NewB = bind(NewB, svalBuilder.makeLoc(ER), *VI); 1776 } 1777 1778 // If the init list is shorter than the array length, set the 1779 // array default value. 1780 if (Size.hasValue() && i < Size.getValue()) 1781 NewB = setImplicitDefaultValue(NewB, R, ElementTy); 1782 1783 return NewB; 1784} 1785 1786RegionBindingsRef RegionStoreManager::bindVector(RegionBindingsConstRef B, 1787 const TypedValueRegion* R, 1788 SVal V) { 1789 QualType T = R->getValueType(); 1790 assert(T->isVectorType()); 1791 const VectorType *VT = T->getAs<VectorType>(); // Use getAs for typedefs. 1792 1793 // Handle lazy compound values and symbolic values. 1794 if (isa<nonloc::LazyCompoundVal>(V) || isa<nonloc::SymbolVal>(V)) 1795 return bindAggregate(B, R, V); 1796 1797 // We may get non-CompoundVal accidentally due to imprecise cast logic or 1798 // that we are binding symbolic struct value. Kill the field values, and if 1799 // the value is symbolic go and bind it as a "default" binding. 1800 if (!isa<nonloc::CompoundVal>(V)) { 1801 return bindAggregate(B, R, UnknownVal()); 1802 } 1803 1804 QualType ElemType = VT->getElementType(); 1805 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V); 1806 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); 1807 unsigned index = 0, numElements = VT->getNumElements(); 1808 RegionBindingsRef NewB(B); 1809 1810 for ( ; index != numElements ; ++index) { 1811 if (VI == VE) 1812 break; 1813 1814 NonLoc Idx = svalBuilder.makeArrayIndex(index); 1815 const ElementRegion *ER = MRMgr.getElementRegion(ElemType, Idx, R, Ctx); 1816 1817 if (ElemType->isArrayType()) 1818 NewB = bindArray(NewB, ER, *VI); 1819 else if (ElemType->isStructureOrClassType()) 1820 NewB = bindStruct(NewB, ER, *VI); 1821 else 1822 NewB = bind(NewB, svalBuilder.makeLoc(ER), *VI); 1823 } 1824 return NewB; 1825} 1826 1827RegionBindingsRef RegionStoreManager::bindStruct(RegionBindingsConstRef B, 1828 const TypedValueRegion* R, 1829 SVal V) { 1830 if (!Features.supportsFields()) 1831 return B; 1832 1833 QualType T = R->getValueType(); 1834 assert(T->isStructureOrClassType()); 1835 1836 const RecordType* RT = T->getAs<RecordType>(); 1837 RecordDecl *RD = RT->getDecl(); 1838 1839 if (!RD->isCompleteDefinition()) 1840 return B; 1841 1842 // Handle lazy compound values and symbolic values. 1843 if (isa<nonloc::LazyCompoundVal>(V) || isa<nonloc::SymbolVal>(V)) 1844 return bindAggregate(B, R, V); 1845 1846 // We may get non-CompoundVal accidentally due to imprecise cast logic or 1847 // that we are binding symbolic struct value. Kill the field values, and if 1848 // the value is symbolic go and bind it as a "default" binding. 1849 if (V.isUnknown() || !isa<nonloc::CompoundVal>(V)) 1850 return bindAggregate(B, R, UnknownVal()); 1851 1852 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V); 1853 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); 1854 1855 RecordDecl::field_iterator FI, FE; 1856 RegionBindingsRef NewB(B); 1857 1858 for (FI = RD->field_begin(), FE = RD->field_end(); FI != FE; ++FI) { 1859 1860 if (VI == VE) 1861 break; 1862 1863 // Skip any unnamed bitfields to stay in sync with the initializers. 1864 if (FI->isUnnamedBitfield()) 1865 continue; 1866 1867 QualType FTy = FI->getType(); 1868 const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R); 1869 1870 if (FTy->isArrayType()) 1871 NewB = bindArray(NewB, FR, *VI); 1872 else if (FTy->isStructureOrClassType()) 1873 NewB = bindStruct(NewB, FR, *VI); 1874 else 1875 NewB = bind(NewB, svalBuilder.makeLoc(FR), *VI); 1876 ++VI; 1877 } 1878 1879 // There may be fewer values in the initialize list than the fields of struct. 1880 if (FI != FE) { 1881 NewB = NewB.addBinding(R, BindingKey::Default, 1882 svalBuilder.makeIntVal(0, false)); 1883 } 1884 1885 return NewB; 1886} 1887 1888RegionBindingsRef 1889RegionStoreManager::bindAggregate(RegionBindingsConstRef B, 1890 const TypedRegion *R, 1891 SVal Val) { 1892 // Remove the old bindings, using 'R' as the root of all regions 1893 // we will invalidate. Then add the new binding. 1894 return removeSubRegionBindings(B, R).addBinding(R, BindingKey::Default, Val); 1895} 1896 1897//===----------------------------------------------------------------------===// 1898// State pruning. 1899//===----------------------------------------------------------------------===// 1900 1901namespace { 1902class removeDeadBindingsWorker : 1903 public ClusterAnalysis<removeDeadBindingsWorker> { 1904 SmallVector<const SymbolicRegion*, 12> Postponed; 1905 SymbolReaper &SymReaper; 1906 const StackFrameContext *CurrentLCtx; 1907 1908public: 1909 removeDeadBindingsWorker(RegionStoreManager &rm, 1910 ProgramStateManager &stateMgr, 1911 RegionBindingsRef b, SymbolReaper &symReaper, 1912 const StackFrameContext *LCtx) 1913 : ClusterAnalysis<removeDeadBindingsWorker>(rm, stateMgr, b, 1914 /* includeGlobals = */ false), 1915 SymReaper(symReaper), CurrentLCtx(LCtx) {} 1916 1917 // Called by ClusterAnalysis. 1918 void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C); 1919 void VisitCluster(const MemRegion *baseR, const ClusterBindings &C); 1920 1921 bool UpdatePostponed(); 1922 void VisitBinding(SVal V); 1923}; 1924} 1925 1926void removeDeadBindingsWorker::VisitAddedToCluster(const MemRegion *baseR, 1927 const ClusterBindings &C) { 1928 1929 if (const VarRegion *VR = dyn_cast<VarRegion>(baseR)) { 1930 if (SymReaper.isLive(VR)) 1931 AddToWorkList(baseR, &C); 1932 1933 return; 1934 } 1935 1936 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) { 1937 if (SymReaper.isLive(SR->getSymbol())) 1938 AddToWorkList(SR, &C); 1939 else 1940 Postponed.push_back(SR); 1941 1942 return; 1943 } 1944 1945 if (isa<NonStaticGlobalSpaceRegion>(baseR)) { 1946 AddToWorkList(baseR, &C); 1947 return; 1948 } 1949 1950 // CXXThisRegion in the current or parent location context is live. 1951 if (const CXXThisRegion *TR = dyn_cast<CXXThisRegion>(baseR)) { 1952 const StackArgumentsSpaceRegion *StackReg = 1953 cast<StackArgumentsSpaceRegion>(TR->getSuperRegion()); 1954 const StackFrameContext *RegCtx = StackReg->getStackFrame(); 1955 if (CurrentLCtx && 1956 (RegCtx == CurrentLCtx || RegCtx->isParentOf(CurrentLCtx))) 1957 AddToWorkList(TR, &C); 1958 } 1959} 1960 1961void removeDeadBindingsWorker::VisitCluster(const MemRegion *baseR, 1962 const ClusterBindings &C) { 1963 // Mark the symbol for any SymbolicRegion with live bindings as live itself. 1964 // This means we should continue to track that symbol. 1965 if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(baseR)) 1966 SymReaper.markLive(SymR->getSymbol()); 1967 1968 for (ClusterBindings::iterator I = C.begin(), E = C.end(); I != E; ++I) 1969 VisitBinding(I.getData()); 1970} 1971 1972void removeDeadBindingsWorker::VisitBinding(SVal V) { 1973 // Is it a LazyCompoundVal? All referenced regions are live as well. 1974 if (const nonloc::LazyCompoundVal *LCS = 1975 dyn_cast<nonloc::LazyCompoundVal>(&V)) { 1976 1977 const MemRegion *LazyR = LCS->getRegion(); 1978 RegionBindingsRef B = RM.getRegionBindings(LCS->getStore()); 1979 1980 // FIXME: This should not have to walk all bindings in the old store. 1981 for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end(); 1982 RI != RE; ++RI){ 1983 const ClusterBindings &Cluster = RI.getData(); 1984 for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); 1985 CI != CE; ++CI) { 1986 BindingKey K = CI.getKey(); 1987 if (const SubRegion *BaseR = dyn_cast<SubRegion>(K.getRegion())) { 1988 if (BaseR == LazyR) 1989 VisitBinding(CI.getData()); 1990 else if (K.hasSymbolicOffset() && BaseR->isSubRegionOf(LazyR)) 1991 VisitBinding(CI.getData()); 1992 } 1993 } 1994 } 1995 1996 return; 1997 } 1998 1999 // If V is a region, then add it to the worklist. 2000 if (const MemRegion *R = V.getAsRegion()) { 2001 AddToWorkList(R); 2002 2003 // All regions captured by a block are also live. 2004 if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(R)) { 2005 BlockDataRegion::referenced_vars_iterator I = BR->referenced_vars_begin(), 2006 E = BR->referenced_vars_end(); 2007 for ( ; I != E; ++I) 2008 AddToWorkList(I.getCapturedRegion()); 2009 } 2010 } 2011 2012 2013 // Update the set of live symbols. 2014 for (SymExpr::symbol_iterator SI = V.symbol_begin(), SE = V.symbol_end(); 2015 SI!=SE; ++SI) 2016 SymReaper.markLive(*SI); 2017} 2018 2019bool removeDeadBindingsWorker::UpdatePostponed() { 2020 // See if any postponed SymbolicRegions are actually live now, after 2021 // having done a scan. 2022 bool changed = false; 2023 2024 for (SmallVectorImpl<const SymbolicRegion*>::iterator 2025 I = Postponed.begin(), E = Postponed.end() ; I != E ; ++I) { 2026 if (const SymbolicRegion *SR = *I) { 2027 if (SymReaper.isLive(SR->getSymbol())) { 2028 changed |= AddToWorkList(SR); 2029 *I = NULL; 2030 } 2031 } 2032 } 2033 2034 return changed; 2035} 2036 2037StoreRef RegionStoreManager::removeDeadBindings(Store store, 2038 const StackFrameContext *LCtx, 2039 SymbolReaper& SymReaper) { 2040 RegionBindingsRef B = getRegionBindings(store); 2041 removeDeadBindingsWorker W(*this, StateMgr, B, SymReaper, LCtx); 2042 W.GenerateClusters(); 2043 2044 // Enqueue the region roots onto the worklist. 2045 for (SymbolReaper::region_iterator I = SymReaper.region_begin(), 2046 E = SymReaper.region_end(); I != E; ++I) { 2047 W.AddToWorkList(*I); 2048 } 2049 2050 do W.RunWorkList(); while (W.UpdatePostponed()); 2051 2052 // We have now scanned the store, marking reachable regions and symbols 2053 // as live. We now remove all the regions that are dead from the store 2054 // as well as update DSymbols with the set symbols that are now dead. 2055 for (RegionBindingsRef::iterator I = B.begin(), E = B.end(); I != E; ++I) { 2056 const MemRegion *Base = I.getKey(); 2057 2058 // If the cluster has been visited, we know the region has been marked. 2059 if (W.isVisited(Base)) 2060 continue; 2061 2062 // Remove the dead entry. 2063 B = B.remove(Base); 2064 2065 if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(Base)) 2066 SymReaper.maybeDead(SymR->getSymbol()); 2067 2068 // Mark all non-live symbols that this binding references as dead. 2069 const ClusterBindings &Cluster = I.getData(); 2070 for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); 2071 CI != CE; ++CI) { 2072 SVal X = CI.getData(); 2073 SymExpr::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end(); 2074 for (; SI != SE; ++SI) 2075 SymReaper.maybeDead(*SI); 2076 } 2077 } 2078 2079 return StoreRef(B.asStore(), *this); 2080} 2081 2082//===----------------------------------------------------------------------===// 2083// Utility methods. 2084//===----------------------------------------------------------------------===// 2085 2086void RegionStoreManager::print(Store store, raw_ostream &OS, 2087 const char* nl, const char *sep) { 2088 RegionBindingsRef B = getRegionBindings(store); 2089 OS << "Store (direct and default bindings), " 2090 << B.asStore() 2091 << " :" << nl; 2092 B.dump(OS, nl); 2093} 2094