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