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