contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/RegionStore.cpp

   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
  31 using namespace clang;
  32 using namespace ento;
  33 using llvm::Optional;
  34
  35 //===----------------------------------------------------------------------===//
  36 // Representation of binding keys.
  37 //===----------------------------------------------------------------------===//
  38
  39 namespace {
  40 class BindingKey {
  41 public:
  42   enum Kind { Direct = 0x0, Default = 0x1 };
  43 private:
  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) {}
  49 public:
  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
  82 BindingKey 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
  95 namespace 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
 109 typedef llvm::ImmutableMap<BindingKey, SVal> RegionBindings;
 110
 111 //===----------------------------------------------------------------------===//
 112 // Fine-grained control of RegionStoreManager.
 113 //===----------------------------------------------------------------------===//
 114
 115 namespace {
 116 struct minimal_features_tag {};
 117 struct maximal_features_tag {};
 118
 119 class RegionStoreFeatures {
 120   bool SupportsFields;
 121 public:
 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
 138 namespace {
 139
 140 class RegionStoreSubRegionMap : public SubRegionMap {
 141 public:
 142   typedef llvm::ImmutableSet<const MemRegion*> Set;
 143   typedef llvm::DenseMap<const MemRegion*, Set> Map;
 144 private:
 145   Set::Factory F;
 146   Map M;
 147 public:
 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
 185 void
 186 RegionStoreSubRegionMap::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
 194 class RegionStoreManager : public StoreManager {
 195   const RegionStoreFeatures Features;
 196   RegionBindings::Factory RBFactory;
 197
 198 public:
 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
 247 public:   // 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
 269 public: // 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
 419 StoreManager *ento::CreateRegionStoreManager(GRStateManager& StMgr) {
 420   RegionStoreFeatures F = maximal_features_tag();
 421   return new RegionStoreManager(StMgr, F);
 422 }
 423
 424 StoreManager *ento::CreateFieldsOnlyRegionStoreManager(GRStateManager &StMgr) {
 425   RegionStoreFeatures F = minimal_features_tag();
 426   F.enableFields(true);
 427   return new RegionStoreManager(StMgr, F);
 428 }
 429
 430
 431 RegionStoreSubRegionMap*
 432 RegionStoreManager::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
 457 namespace {
 458 template <typename DERIVED>
 459 class ClusterAnalysis  {
 460 protected:
 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
 479 public:
 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
 561 public:
 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
 572 void 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
 584 namespace {
 585 class invalidateRegionsWorker : public ClusterAnalysis<invalidateRegionsWorker>
 586 {
 587   const Expr *Ex;
 588   unsigned Count;
 589   StoreManager::InvalidatedSymbols &IS;
 590   StoreManager::InvalidatedRegions *Regions;
 591 public:
 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
 605 private:
 606   void VisitBinding(SVal V);
 607 };
 608 }
 609
 610 void 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
 637 void 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
 649 void 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
 720 StoreRef 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
 766 DefinedOrUnknownSVal 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.
 801 SVal 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
 820 SVal 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
 843 Optional<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
 852 Optional<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
 865 SVal 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
 979 std::pair<Store, const MemRegion *>
 980 RegionStoreManager::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
1024 SVal 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
1094 SVal 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
1106 Optional<SVal>
1107 RegionStoreManager::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
1133 SVal 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
1142 SVal 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
1196 SVal 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
1218 SVal 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
1267 SVal RegionStoreManager::RetrieveLazySymbol(const TypedRegion *R) {
1268   // All other values are symbolic.
1269   return svalBuilder.getRegionValueSymbolVal(R);
1270 }
1271
1272 SVal 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
1278 SVal 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
1287 StoreRef 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
1297 StoreRef 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
1342 StoreRef 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().
1356 StoreRef 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
1364 StoreRef 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
1392 StoreRef 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
1451 StoreRef 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
1510 StoreRef 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
1545 StoreRef 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
1569 RegionBindings 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
1576 RegionBindings 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
1582 const SVal *RegionStoreManager::lookup(RegionBindings B, BindingKey K) {
1583   if (!K.isValid())
1584     return NULL;
1585   return B.lookup(K);
1586 }
1587
1588 const SVal *RegionStoreManager::lookup(RegionBindings B,
1589                                        const MemRegion *R,
1590                                        BindingKey::Kind k) {
1591   return lookup(B, BindingKey::Make(R, k));
1592 }
1593
1594 RegionBindings RegionStoreManager::removeBinding(RegionBindings B,
1595                                                  BindingKey K) {
1596   if (!K.isValid())
1597     return B;
1598   return RBFactory.remove(B, K);
1599 }
1600
1601 RegionBindings 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
1611 namespace {
1612 class removeDeadBindingsWorker :
1613   public ClusterAnalysis<removeDeadBindingsWorker> {
1614   llvm::SmallVector<const SymbolicRegion*, 12> Postponed;
1615   SymbolReaper &SymReaper;
1616   const StackFrameContext *CurrentLCtx;
1617
1618 public:
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
1636 void 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
1670 void removeDeadBindingsWorker::VisitCluster(const MemRegion *baseR,
1671                                             BindingKey *I, BindingKey *E) {
1672   for ( ; I != E; ++I)
1673     VisitBindingKey(*I);
1674 }
1675
1676 void 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
1701 void 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
1734 bool 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
1752 StoreRef 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
1795 StoreRef 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
1834 void 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 }