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