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/ProgramState.h"
  24 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.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   raw_ostream &operator<<(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(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(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(ProgramStateManager& 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, ArrayRef<const MemRegion *> Regions,
 240                              const Expr *E, unsigned Count,
 241                              InvalidatedSymbols &IS,
 242                              bool invalidateGlobals,
 243                              InvalidatedRegions *Invalidated);
 244
 245 public:   // Made public for helper classes.
 246
 247   void RemoveSubRegionBindings(RegionBindings &B, const MemRegion *R,
 248                                RegionStoreSubRegionMap &M);
 249
 250   RegionBindings addBinding(RegionBindings B, BindingKey K, SVal V);
 251
 252   RegionBindings addBinding(RegionBindings B, const MemRegion *R,
 253                      BindingKey::Kind k, SVal V);
 254
 255   const SVal *lookup(RegionBindings B, BindingKey K);
 256   const SVal *lookup(RegionBindings B, const MemRegion *R, BindingKey::Kind k);
 257
 258   RegionBindings removeBinding(RegionBindings B, BindingKey K);
 259   RegionBindings removeBinding(RegionBindings B, const MemRegion *R,
 260                         BindingKey::Kind k);
 261
 262   RegionBindings removeBinding(RegionBindings B, const MemRegion *R) {
 263     return removeBinding(removeBinding(B, R, BindingKey::Direct), R,
 264                         BindingKey::Default);
 265   }
 266
 267 public: // Part of public interface to class.
 268
 269   StoreRef Bind(Store store, Loc LV, SVal V);
 270
 271   // BindDefault is only used to initialize a region with a default value.
 272   StoreRef BindDefault(Store store, const MemRegion *R, SVal V) {
 273     RegionBindings B = GetRegionBindings(store);
 274     assert(!lookup(B, R, BindingKey::Default));
 275     assert(!lookup(B, R, BindingKey::Direct));
 276     return StoreRef(addBinding(B, R, BindingKey::Default, V).getRootWithoutRetain(), *this);
 277   }
 278
 279   StoreRef BindCompoundLiteral(Store store, const CompoundLiteralExpr *CL,
 280                                const LocationContext *LC, SVal V);
 281
 282   StoreRef BindDecl(Store store, const VarRegion *VR, SVal InitVal);
 283
 284   StoreRef BindDeclWithNoInit(Store store, const VarRegion *) {
 285     return StoreRef(store, *this);
 286   }
 287
 288   /// BindStruct - Bind a compound value to a structure.
 289   StoreRef BindStruct(Store store, const TypedValueRegion* R, SVal V);
 290
 291   StoreRef BindArray(Store store, const TypedValueRegion* R, SVal V);
 292
 293   /// KillStruct - Set the entire struct to unknown.
 294   StoreRef KillStruct(Store store, const TypedRegion* R, SVal DefaultVal);
 295
 296   StoreRef Remove(Store store, Loc LV);
 297
 298   void incrementReferenceCount(Store store) {
 299     GetRegionBindings(store).manualRetain();
 300   }
 301
 302   /// If the StoreManager supports it, decrement the reference count of
 303   /// the specified Store object.  If the reference count hits 0, the memory
 304   /// associated with the object is recycled.
 305   void decrementReferenceCount(Store store) {
 306     GetRegionBindings(store).manualRelease();
 307   }
 308
 309   bool includedInBindings(Store store, const MemRegion *region) const;
 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 TypedValueRegion *R);
 337
 338   SVal RetrieveFieldOrElementCommon(Store store, const TypedValueRegion *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 TypedValueRegion* R);
 350
 351   SVal RetrieveArray(Store store, const TypedValueRegion* 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 TypedValueRegion *R,
 358                                              QualType Ty);
 359
 360   /// Get the state and region whose binding this region R corresponds to.
 361   std::pair<Store, const MemRegion*>
 362   GetLazyBinding(RegionBindings B, const MemRegion *R,
 363                  const MemRegion *originalRegion);
 364
 365   StoreRef CopyLazyBindings(nonloc::LazyCompoundVal V, Store store,
 366                             const TypedRegion *R);
 367
 368   //===------------------------------------------------------------------===//
 369   // State pruning.
 370   //===------------------------------------------------------------------===//
 371
 372   /// removeDeadBindings - Scans the RegionStore of 'state' for dead values.
 373   ///  It returns a new Store with these values removed.
 374   StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx,
 375                               SymbolReaper& SymReaper);
 376
 377   StoreRef enterStackFrame(const ProgramState *state,
 378                            const StackFrameContext *frame);
 379
 380   //===------------------------------------------------------------------===//
 381   // Region "extents".
 382   //===------------------------------------------------------------------===//
 383
 384   // FIXME: This method will soon be eliminated; see the note in Store.h.
 385   DefinedOrUnknownSVal getSizeInElements(const ProgramState *state,
 386                                          const MemRegion* R, QualType EleTy);
 387
 388   //===------------------------------------------------------------------===//
 389   // Utility methods.
 390   //===------------------------------------------------------------------===//
 391
 392   static inline RegionBindings GetRegionBindings(Store store) {
 393     return RegionBindings(static_cast<const RegionBindings::TreeTy*>(store));
 394   }
 395
 396   void print(Store store, raw_ostream &Out, const char* nl,
 397              const char *sep);
 398
 399   void iterBindings(Store store, BindingsHandler& f) {
 400     RegionBindings B = GetRegionBindings(store);
 401     for (RegionBindings::iterator I=B.begin(), E=B.end(); I!=E; ++I) {
 402       const BindingKey &K = I.getKey();
 403       if (!K.isDirect())
 404         continue;
 405       if (const SubRegion *R = dyn_cast<SubRegion>(I.getKey().getRegion())) {
 406         // FIXME: Possibly incorporate the offset?
 407         if (!f.HandleBinding(*this, store, R, I.getData()))
 408           return;
 409       }
 410     }
 411   }
 412 };
 413
 414 } // end anonymous namespace
 415
 416 //===----------------------------------------------------------------------===//
 417 // RegionStore creation.
 418 //===----------------------------------------------------------------------===//
 419
 420 StoreManager *ento::CreateRegionStoreManager(ProgramStateManager& StMgr) {
 421   RegionStoreFeatures F = maximal_features_tag();
 422   return new RegionStoreManager(StMgr, F);
 423 }
 424
 425 StoreManager *ento::CreateFieldsOnlyRegionStoreManager(ProgramStateManager &StMgr) {
 426   RegionStoreFeatures F = minimal_features_tag();
 427   F.enableFields(true);
 428   return new RegionStoreManager(StMgr, F);
 429 }
 430
 431
 432 RegionStoreSubRegionMap*
 433 RegionStoreManager::getRegionStoreSubRegionMap(Store store) {
 434   RegionBindings B = GetRegionBindings(store);
 435   RegionStoreSubRegionMap *M = new RegionStoreSubRegionMap();
 436
 437   SmallVector<const SubRegion*, 10> WL;
 438
 439   for (RegionBindings::iterator I=B.begin(), E=B.end(); I!=E; ++I)
 440     if (const SubRegion *R = dyn_cast<SubRegion>(I.getKey().getRegion()))
 441       M->process(WL, R);
 442
 443   // We also need to record in the subregion map "intermediate" regions that
 444   // don't have direct bindings but are super regions of those that do.
 445   while (!WL.empty()) {
 446     const SubRegion *R = WL.back();
 447     WL.pop_back();
 448     M->process(WL, R);
 449   }
 450
 451   return M;
 452 }
 453
 454 //===----------------------------------------------------------------------===//
 455 // Region Cluster analysis.
 456 //===----------------------------------------------------------------------===//
 457
 458 namespace {
 459 template <typename DERIVED>
 460 class ClusterAnalysis  {
 461 protected:
 462   typedef BumpVector<BindingKey> RegionCluster;
 463   typedef llvm::DenseMap<const MemRegion *, RegionCluster *> ClusterMap;
 464   llvm::DenseMap<const RegionCluster*, unsigned> Visited;
 465   typedef SmallVector<std::pair<const MemRegion *, RegionCluster*>, 10>
 466     WorkList;
 467
 468   BumpVectorContext BVC;
 469   ClusterMap ClusterM;
 470   WorkList WL;
 471
 472   RegionStoreManager &RM;
 473   ASTContext &Ctx;
 474   SValBuilder &svalBuilder;
 475
 476   RegionBindings B;
 477
 478   const bool includeGlobals;
 479
 480 public:
 481   ClusterAnalysis(RegionStoreManager &rm, ProgramStateManager &StateMgr,
 482                   RegionBindings b, const bool includeGlobals)
 483     : RM(rm), Ctx(StateMgr.getContext()),
 484       svalBuilder(StateMgr.getSValBuilder()),
 485       B(b), includeGlobals(includeGlobals) {}
 486
 487   RegionBindings getRegionBindings() const { return B; }
 488
 489   RegionCluster &AddToCluster(BindingKey K) {
 490     const MemRegion *R = K.getRegion();
 491     const MemRegion *baseR = R->getBaseRegion();
 492     RegionCluster &C = getCluster(baseR);
 493     C.push_back(K, BVC);
 494     static_cast<DERIVED*>(this)->VisitAddedToCluster(baseR, C);
 495     return C;
 496   }
 497
 498   bool isVisited(const MemRegion *R) {
 499     return (bool) Visited[&getCluster(R->getBaseRegion())];
 500   }
 501
 502   RegionCluster& getCluster(const MemRegion *R) {
 503     RegionCluster *&CRef = ClusterM[R];
 504     if (!CRef) {
 505       void *Mem = BVC.getAllocator().template Allocate<RegionCluster>();
 506       CRef = new (Mem) RegionCluster(BVC, 10);
 507     }
 508     return *CRef;
 509   }
 510
 511   void GenerateClusters() {
 512       // Scan the entire set of bindings and make the region clusters.
 513     for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){
 514       RegionCluster &C = AddToCluster(RI.getKey());
 515       if (const MemRegion *R = RI.getData().getAsRegion()) {
 516         // Generate a cluster, but don't add the region to the cluster
 517         // if there aren't any bindings.
 518         getCluster(R->getBaseRegion());
 519       }
 520       if (includeGlobals) {
 521         const MemRegion *R = RI.getKey().getRegion();
 522         if (isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace()))
 523           AddToWorkList(R, C);
 524       }
 525     }
 526   }
 527
 528   bool AddToWorkList(const MemRegion *R, RegionCluster &C) {
 529     if (unsigned &visited = Visited[&C])
 530       return false;
 531     else
 532       visited = 1;
 533
 534     WL.push_back(std::make_pair(R, &C));
 535     return true;
 536   }
 537
 538   bool AddToWorkList(BindingKey K) {
 539     return AddToWorkList(K.getRegion());
 540   }
 541
 542   bool AddToWorkList(const MemRegion *R) {
 543     const MemRegion *baseR = R->getBaseRegion();
 544     return AddToWorkList(baseR, getCluster(baseR));
 545   }
 546
 547   void RunWorkList() {
 548     while (!WL.empty()) {
 549       const MemRegion *baseR;
 550       RegionCluster *C;
 551       llvm::tie(baseR, C) = WL.back();
 552       WL.pop_back();
 553
 554         // First visit the cluster.
 555       static_cast<DERIVED*>(this)->VisitCluster(baseR, C->begin(), C->end());
 556
 557         // Next, visit the base region.
 558       static_cast<DERIVED*>(this)->VisitBaseRegion(baseR);
 559     }
 560   }
 561
 562 public:
 563   void VisitAddedToCluster(const MemRegion *baseR, RegionCluster &C) {}
 564   void VisitCluster(const MemRegion *baseR, BindingKey *I, BindingKey *E) {}
 565   void VisitBaseRegion(const MemRegion *baseR) {}
 566 };
 567 }
 568
 569 //===----------------------------------------------------------------------===//
 570 // Binding invalidation.
 571 //===----------------------------------------------------------------------===//
 572
 573 void RegionStoreManager::RemoveSubRegionBindings(RegionBindings &B,
 574                                                  const MemRegion *R,
 575                                                  RegionStoreSubRegionMap &M) {
 576
 577   if (const RegionStoreSubRegionMap::Set *S = M.getSubRegions(R))
 578     for (RegionStoreSubRegionMap::Set::iterator I = S->begin(), E = S->end();
 579          I != E; ++I)
 580       RemoveSubRegionBindings(B, *I, M);
 581
 582   B = removeBinding(B, R);
 583 }
 584
 585 namespace {
 586 class invalidateRegionsWorker : public ClusterAnalysis<invalidateRegionsWorker>
 587 {
 588   const Expr *Ex;
 589   unsigned Count;
 590   StoreManager::InvalidatedSymbols &IS;
 591   StoreManager::InvalidatedRegions *Regions;
 592 public:
 593   invalidateRegionsWorker(RegionStoreManager &rm,
 594                           ProgramStateManager &stateMgr,
 595                           RegionBindings b,
 596                           const Expr *ex, unsigned count,
 597                           StoreManager::InvalidatedSymbols &is,
 598                           StoreManager::InvalidatedRegions *r,
 599                           bool includeGlobals)
 600     : ClusterAnalysis<invalidateRegionsWorker>(rm, stateMgr, b, includeGlobals),
 601       Ex(ex), Count(count), IS(is), Regions(r) {}
 602
 603   void VisitCluster(const MemRegion *baseR, BindingKey *I, BindingKey *E);
 604   void VisitBaseRegion(const MemRegion *baseR);
 605
 606 private:
 607   void VisitBinding(SVal V);
 608 };
 609 }
 610
 611 void invalidateRegionsWorker::VisitBinding(SVal V) {
 612   // A symbol?  Mark it touched by the invalidation.
 613   if (SymbolRef Sym = V.getAsSymbol())
 614     IS.insert(Sym);
 615
 616   if (const MemRegion *R = V.getAsRegion()) {
 617     AddToWorkList(R);
 618     return;
 619   }
 620
 621   // Is it a LazyCompoundVal?  All references get invalidated as well.
 622   if (const nonloc::LazyCompoundVal *LCS =
 623         dyn_cast<nonloc::LazyCompoundVal>(&V)) {
 624
 625     const MemRegion *LazyR = LCS->getRegion();
 626     RegionBindings B = RegionStoreManager::GetRegionBindings(LCS->getStore());
 627
 628     for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){
 629       const SubRegion *baseR = dyn_cast<SubRegion>(RI.getKey().getRegion());
 630       if (baseR && baseR->isSubRegionOf(LazyR))
 631         VisitBinding(RI.getData());
 632     }
 633
 634     return;
 635   }
 636 }
 637
 638 void invalidateRegionsWorker::VisitCluster(const MemRegion *baseR,
 639                                            BindingKey *I, BindingKey *E) {
 640   for ( ; I != E; ++I) {
 641     // Get the old binding.  Is it a region?  If so, add it to the worklist.
 642     const BindingKey &K = *I;
 643     if (const SVal *V = RM.lookup(B, K))
 644       VisitBinding(*V);
 645
 646     B = RM.removeBinding(B, K);
 647   }
 648 }
 649
 650 void invalidateRegionsWorker::VisitBaseRegion(const MemRegion *baseR) {
 651   // Symbolic region?  Mark that symbol touched by the invalidation.
 652   if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR))
 653     IS.insert(SR->getSymbol());
 654
 655   // BlockDataRegion?  If so, invalidate captured variables that are passed
 656   // by reference.
 657   if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(baseR)) {
 658     for (BlockDataRegion::referenced_vars_iterator
 659          BI = BR->referenced_vars_begin(), BE = BR->referenced_vars_end() ;
 660          BI != BE; ++BI) {
 661       const VarRegion *VR = *BI;
 662       const VarDecl *VD = VR->getDecl();
 663       if (VD->getAttr<BlocksAttr>() || !VD->hasLocalStorage())
 664         AddToWorkList(VR);
 665     }
 666     return;
 667   }
 668
 669   // Otherwise, we have a normal data region. Record that we touched the region.
 670   if (Regions)
 671     Regions->push_back(baseR);
 672
 673   if (isa<AllocaRegion>(baseR) || isa<SymbolicRegion>(baseR)) {
 674     // Invalidate the region by setting its default value to
 675     // conjured symbol. The type of the symbol is irrelavant.
 676     DefinedOrUnknownSVal V =
 677       svalBuilder.getConjuredSymbolVal(baseR, Ex, Ctx.IntTy, Count);
 678     B = RM.addBinding(B, baseR, BindingKey::Default, V);
 679     return;
 680   }
 681
 682   if (!baseR->isBoundable())
 683     return;
 684
 685   const TypedValueRegion *TR = cast<TypedValueRegion>(baseR);
 686   QualType T = TR->getValueType();
 687
 688     // Invalidate the binding.
 689   if (T->isStructureOrClassType()) {
 690     // Invalidate the region by setting its default value to
 691     // conjured symbol. The type of the symbol is irrelavant.
 692     DefinedOrUnknownSVal V =
 693       svalBuilder.getConjuredSymbolVal(baseR, Ex, Ctx.IntTy, Count);
 694     B = RM.addBinding(B, baseR, BindingKey::Default, V);
 695     return;
 696   }
 697
 698   if (const ArrayType *AT = Ctx.getAsArrayType(T)) {
 699       // Set the default value of the array to conjured symbol.
 700     DefinedOrUnknownSVal V =
 701     svalBuilder.getConjuredSymbolVal(baseR, Ex, AT->getElementType(), Count);
 702     B = RM.addBinding(B, baseR, BindingKey::Default, V);
 703     return;
 704   }
 705
 706   if (includeGlobals &&
 707       isa<NonStaticGlobalSpaceRegion>(baseR->getMemorySpace())) {
 708     // If the region is a global and we are invalidating all globals,
 709     // just erase the entry.  This causes all globals to be lazily
 710     // symbolicated from the same base symbol.
 711     B = RM.removeBinding(B, baseR);
 712     return;
 713   }
 714
 715
 716   DefinedOrUnknownSVal V = svalBuilder.getConjuredSymbolVal(baseR, Ex, T, Count);
 717   assert(SymbolManager::canSymbolicate(T) || V.isUnknown());
 718   B = RM.addBinding(B, baseR, BindingKey::Direct, V);
 719 }
 720
 721 StoreRef RegionStoreManager::invalidateRegions(Store store,
 722                                             ArrayRef<const MemRegion *> Regions,
 723                                                const Expr *Ex, unsigned Count,
 724                                                InvalidatedSymbols &IS,
 725                                                bool invalidateGlobals,
 726                                               InvalidatedRegions *Invalidated) {
 727   invalidateRegionsWorker W(*this, StateMgr,
 728                             RegionStoreManager::GetRegionBindings(store),
 729                             Ex, Count, IS, Invalidated, invalidateGlobals);
 730
 731   // Scan the bindings and generate the clusters.
 732   W.GenerateClusters();
 733
 734   // Add the regions to the worklist.
 735   for (ArrayRef<const MemRegion *>::iterator
 736        I = Regions.begin(), E = Regions.end(); I != E; ++I)
 737     W.AddToWorkList(*I);
 738
 739   W.RunWorkList();
 740
 741   // Return the new bindings.
 742   RegionBindings B = W.getRegionBindings();
 743
 744   if (invalidateGlobals) {
 745     // Bind the non-static globals memory space to a new symbol that we will
 746     // use to derive the bindings for all non-static globals.
 747     const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion();
 748     SVal V =
 749       svalBuilder.getConjuredSymbolVal(/* SymbolTag = */ (void*) GS, Ex,
 750                                   /* symbol type, doesn't matter */ Ctx.IntTy,
 751                                   Count);
 752     B = addBinding(B, BindingKey::Make(GS, BindingKey::Default), V);
 753
 754     // Even if there are no bindings in the global scope, we still need to
 755     // record that we touched it.
 756     if (Invalidated)
 757       Invalidated->push_back(GS);
 758   }
 759
 760   return StoreRef(B.getRootWithoutRetain(), *this);
 761 }
 762
 763 //===----------------------------------------------------------------------===//
 764 // Extents for regions.
 765 //===----------------------------------------------------------------------===//
 766
 767 DefinedOrUnknownSVal RegionStoreManager::getSizeInElements(const ProgramState *state,
 768                                                            const MemRegion *R,
 769                                                            QualType EleTy) {
 770   SVal Size = cast<SubRegion>(R)->getExtent(svalBuilder);
 771   const llvm::APSInt *SizeInt = svalBuilder.getKnownValue(state, Size);
 772   if (!SizeInt)
 773     return UnknownVal();
 774
 775   CharUnits RegionSize = CharUnits::fromQuantity(SizeInt->getSExtValue());
 776
 777   if (Ctx.getAsVariableArrayType(EleTy)) {
 778     // FIXME: We need to track extra state to properly record the size
 779     // of VLAs.  Returning UnknownVal here, however, is a stop-gap so that
 780     // we don't have a divide-by-zero below.
 781     return UnknownVal();
 782   }
 783
 784   CharUnits EleSize = Ctx.getTypeSizeInChars(EleTy);
 785
 786   // If a variable is reinterpreted as a type that doesn't fit into a larger
 787   // type evenly, round it down.
 788   // This is a signed value, since it's used in arithmetic with signed indices.
 789   return svalBuilder.makeIntVal(RegionSize / EleSize, false);
 790 }
 791
 792 //===----------------------------------------------------------------------===//
 793 // Location and region casting.
 794 //===----------------------------------------------------------------------===//
 795
 796 /// ArrayToPointer - Emulates the "decay" of an array to a pointer
 797 ///  type.  'Array' represents the lvalue of the array being decayed
 798 ///  to a pointer, and the returned SVal represents the decayed
 799 ///  version of that lvalue (i.e., a pointer to the first element of
 800 ///  the array).  This is called by ExprEngine when evaluating casts
 801 ///  from arrays to pointers.
 802 SVal RegionStoreManager::ArrayToPointer(Loc Array) {
 803   if (!isa<loc::MemRegionVal>(Array))
 804     return UnknownVal();
 805
 806   const MemRegion* R = cast<loc::MemRegionVal>(&Array)->getRegion();
 807   const TypedValueRegion* ArrayR = dyn_cast<TypedValueRegion>(R);
 808
 809   if (!ArrayR)
 810     return UnknownVal();
 811
 812   // Strip off typedefs from the ArrayRegion's ValueType.
 813   QualType T = ArrayR->getValueType().getDesugaredType(Ctx);
 814   const ArrayType *AT = cast<ArrayType>(T);
 815   T = AT->getElementType();
 816
 817   NonLoc ZeroIdx = svalBuilder.makeZeroArrayIndex();
 818   return loc::MemRegionVal(MRMgr.getElementRegion(T, ZeroIdx, ArrayR, Ctx));
 819 }
 820
 821 SVal RegionStoreManager::evalDerivedToBase(SVal derived, QualType baseType) {
 822   const CXXRecordDecl *baseDecl;
 823   if (baseType->isPointerType())
 824     baseDecl = baseType->getCXXRecordDeclForPointerType();
 825   else
 826     baseDecl = baseType->getAsCXXRecordDecl();
 827
 828   assert(baseDecl && "not a CXXRecordDecl?");
 829
 830   loc::MemRegionVal *derivedRegVal = dyn_cast<loc::MemRegionVal>(&derived);
 831   if (!derivedRegVal)
 832     return derived;
 833
 834   const MemRegion *baseReg =
 835     MRMgr.getCXXBaseObjectRegion(baseDecl, derivedRegVal->getRegion());
 836
 837   return loc::MemRegionVal(baseReg);
 838 }
 839
 840 //===----------------------------------------------------------------------===//
 841 // Loading values from regions.
 842 //===----------------------------------------------------------------------===//
 843
 844 Optional<SVal> RegionStoreManager::getDirectBinding(RegionBindings B,
 845                                                     const MemRegion *R) {
 846
 847   if (const SVal *V = lookup(B, R, BindingKey::Direct))
 848     return *V;
 849
 850   return Optional<SVal>();
 851 }
 852
 853 Optional<SVal> RegionStoreManager::getDefaultBinding(RegionBindings B,
 854                                                      const MemRegion *R) {
 855   if (R->isBoundable())
 856     if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R))
 857       if (TR->getValueType()->isUnionType())
 858         return UnknownVal();
 859
 860   if (const SVal *V = lookup(B, R, BindingKey::Default))
 861     return *V;
 862
 863   return Optional<SVal>();
 864 }
 865
 866 SVal RegionStoreManager::Retrieve(Store store, Loc L, QualType T) {
 867   assert(!isa<UnknownVal>(L) && "location unknown");
 868   assert(!isa<UndefinedVal>(L) && "location undefined");
 869
 870   // For access to concrete addresses, return UnknownVal.  Checks
 871   // for null dereferences (and similar errors) are done by checkers, not
 872   // the Store.
 873   // FIXME: We can consider lazily symbolicating such memory, but we really
 874   // should defer this when we can reason easily about symbolicating arrays
 875   // of bytes.
 876   if (isa<loc::ConcreteInt>(L)) {
 877     return UnknownVal();
 878   }
 879   if (!isa<loc::MemRegionVal>(L)) {
 880     return UnknownVal();
 881   }
 882
 883   const MemRegion *MR = cast<loc::MemRegionVal>(L).getRegion();
 884
 885   if (isa<AllocaRegion>(MR) || isa<SymbolicRegion>(MR)) {
 886     if (T.isNull()) {
 887       const SymbolicRegion *SR = cast<SymbolicRegion>(MR);
 888       T = SR->getSymbol()->getType(Ctx);
 889     }
 890     MR = GetElementZeroRegion(MR, T);
 891   }
 892
 893   if (isa<CodeTextRegion>(MR)) {
 894     llvm_unreachable("Why load from a code text region?");
 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 TypedValueRegion *R = cast<TypedValueRegion>(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       // Abort on string underrun.  This can be possible by arbitrary
1046       // clients of RetrieveElement().
1047       if (i < 0)
1048         return UndefinedVal();
1049       int64_t byteLength = Str->getByteLength();
1050       // Technically, only i == byteLength is guaranteed to be null.
1051       // However, such overflows should be caught before reaching this point;
1052       // the only time such an access would be made is if a string literal was
1053       // used to initialize a larger array.
1054       char c = (i >= byteLength) ? '\0' : Str->getString()[i];
1055       return svalBuilder.makeIntVal(c, T);
1056     }
1057   }
1058
1059   // Check for loads from a code text region.  For such loads, just give up.
1060   if (isa<CodeTextRegion>(superR))
1061     return UnknownVal();
1062
1063   // Handle the case where we are indexing into a larger scalar object.
1064   // For example, this handles:
1065   //   int x = ...
1066   //   char *y = &x;
1067   //   return *y;
1068   // FIXME: This is a hack, and doesn't do anything really intelligent yet.
1069   const RegionRawOffset &O = R->getAsArrayOffset();
1070
1071   // If we cannot reason about the offset, return an unknown value.
1072   if (!O.getRegion())
1073     return UnknownVal();
1074
1075   if (const TypedValueRegion *baseR =
1076         dyn_cast_or_null<TypedValueRegion>(O.getRegion())) {
1077     QualType baseT = baseR->getValueType();
1078     if (baseT->isScalarType()) {
1079       QualType elemT = R->getElementType();
1080       if (elemT->isScalarType()) {
1081         if (Ctx.getTypeSizeInChars(baseT) >= Ctx.getTypeSizeInChars(elemT)) {
1082           if (const Optional<SVal> &V = getDirectBinding(B, superR)) {
1083             if (SymbolRef parentSym = V->getAsSymbol())
1084               return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
1085
1086             if (V->isUnknownOrUndef())
1087               return *V;
1088             // Other cases: give up.  We are indexing into a larger object
1089             // that has some value, but we don't know how to handle that yet.
1090             return UnknownVal();
1091           }
1092         }
1093       }
1094     }
1095   }
1096   return RetrieveFieldOrElementCommon(store, R, R->getElementType(), superR);
1097 }
1098
1099 SVal RegionStoreManager::RetrieveField(Store store,
1100                                        const FieldRegion* R) {
1101
1102   // Check if the region has a binding.
1103   RegionBindings B = GetRegionBindings(store);
1104   if (const Optional<SVal> &V = getDirectBinding(B, R))
1105     return *V;
1106
1107   QualType Ty = R->getValueType();
1108   return RetrieveFieldOrElementCommon(store, R, Ty, R->getSuperRegion());
1109 }
1110
1111 Optional<SVal>
1112 RegionStoreManager::RetrieveDerivedDefaultValue(RegionBindings B,
1113                                                 const MemRegion *superR,
1114                                                 const TypedValueRegion *R,
1115                                                 QualType Ty) {
1116
1117   if (const Optional<SVal> &D = getDefaultBinding(B, superR)) {
1118     const SVal &val = D.getValue();
1119     if (SymbolRef parentSym = val.getAsSymbol())
1120       return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
1121
1122     if (val.isZeroConstant())
1123       return svalBuilder.makeZeroVal(Ty);
1124
1125     if (val.isUnknownOrUndef())
1126       return val;
1127
1128     // Lazy bindings are handled later.
1129     if (isa<nonloc::LazyCompoundVal>(val))
1130       return Optional<SVal>();
1131
1132     llvm_unreachable("Unknown default value");
1133   }
1134
1135   return Optional<SVal>();
1136 }
1137
1138 SVal RegionStoreManager::RetrieveLazyBinding(const MemRegion *lazyBindingRegion,
1139                                              Store lazyBindingStore) {
1140   if (const ElementRegion *ER = dyn_cast<ElementRegion>(lazyBindingRegion))
1141     return RetrieveElement(lazyBindingStore, ER);
1142
1143   return RetrieveField(lazyBindingStore,
1144                        cast<FieldRegion>(lazyBindingRegion));
1145 }
1146
1147 SVal RegionStoreManager::RetrieveFieldOrElementCommon(Store store,
1148                                                       const TypedValueRegion *R,
1149                                                       QualType Ty,
1150                                                       const MemRegion *superR) {
1151
1152   // At this point we have already checked in either RetrieveElement or
1153   // RetrieveField if 'R' has a direct binding.
1154
1155   RegionBindings B = GetRegionBindings(store);
1156
1157   while (superR) {
1158     if (const Optional<SVal> &D =
1159         RetrieveDerivedDefaultValue(B, superR, R, Ty))
1160       return *D;
1161
1162     // If our super region is a field or element itself, walk up the region
1163     // hierarchy to see if there is a default value installed in an ancestor.
1164     if (const SubRegion *SR = dyn_cast<SubRegion>(superR)) {
1165       superR = SR->getSuperRegion();
1166       continue;
1167     }
1168     break;
1169   }
1170
1171   // Lazy binding?
1172   Store lazyBindingStore = NULL;
1173   const MemRegion *lazyBindingRegion = NULL;
1174   llvm::tie(lazyBindingStore, lazyBindingRegion) = GetLazyBinding(B, R, R);
1175
1176   if (lazyBindingRegion)
1177     return RetrieveLazyBinding(lazyBindingRegion, lazyBindingStore);
1178
1179   if (R->hasStackNonParametersStorage()) {
1180     if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
1181       // Currently we don't reason specially about Clang-style vectors.  Check
1182       // if superR is a vector and if so return Unknown.
1183       if (const TypedValueRegion *typedSuperR =
1184             dyn_cast<TypedValueRegion>(superR)) {
1185         if (typedSuperR->getValueType()->isVectorType())
1186           return UnknownVal();
1187       }
1188
1189       // FIXME: We also need to take ElementRegions with symbolic indexes into
1190       // account.
1191       if (!ER->getIndex().isConstant())
1192         return UnknownVal();
1193     }
1194
1195     return UndefinedVal();
1196   }
1197
1198   // All other values are symbolic.
1199   return svalBuilder.getRegionValueSymbolVal(R);
1200 }
1201
1202 SVal RegionStoreManager::RetrieveObjCIvar(Store store, const ObjCIvarRegion* R){
1203
1204     // Check if the region has a binding.
1205   RegionBindings B = GetRegionBindings(store);
1206
1207   if (const Optional<SVal> &V = getDirectBinding(B, R))
1208     return *V;
1209
1210   const MemRegion *superR = R->getSuperRegion();
1211
1212   // Check if the super region has a default binding.
1213   if (const Optional<SVal> &V = getDefaultBinding(B, superR)) {
1214     if (SymbolRef parentSym = V->getAsSymbol())
1215       return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
1216
1217     // Other cases: give up.
1218     return UnknownVal();
1219   }
1220
1221   return RetrieveLazySymbol(R);
1222 }
1223
1224 SVal RegionStoreManager::RetrieveVar(Store store, const VarRegion *R) {
1225
1226   // Check if the region has a binding.
1227   RegionBindings B = GetRegionBindings(store);
1228
1229   if (const Optional<SVal> &V = getDirectBinding(B, R))
1230     return *V;
1231
1232   // Lazily derive a value for the VarRegion.
1233   const VarDecl *VD = R->getDecl();
1234   QualType T = VD->getType();
1235   const MemSpaceRegion *MS = R->getMemorySpace();
1236
1237   if (isa<UnknownSpaceRegion>(MS) ||
1238       isa<StackArgumentsSpaceRegion>(MS))
1239     return svalBuilder.getRegionValueSymbolVal(R);
1240
1241   if (isa<GlobalsSpaceRegion>(MS)) {
1242     if (isa<NonStaticGlobalSpaceRegion>(MS)) {
1243       // Is 'VD' declared constant?  If so, retrieve the constant value.
1244       QualType CT = Ctx.getCanonicalType(T);
1245       if (CT.isConstQualified()) {
1246         const Expr *Init = VD->getInit();
1247         // Do the null check first, as we want to call 'IgnoreParenCasts'.
1248         if (Init)
1249           if (const IntegerLiteral *IL =
1250               dyn_cast<IntegerLiteral>(Init->IgnoreParenCasts())) {
1251             const nonloc::ConcreteInt &V = svalBuilder.makeIntVal(IL);
1252             return svalBuilder.evalCast(V, Init->getType(), IL->getType());
1253           }
1254       }
1255
1256       if (const Optional<SVal> &V = RetrieveDerivedDefaultValue(B, MS, R, CT))
1257         return V.getValue();
1258
1259       return svalBuilder.getRegionValueSymbolVal(R);
1260     }
1261
1262     if (T->isIntegerType())
1263       return svalBuilder.makeIntVal(0, T);
1264     if (T->isPointerType())
1265       return svalBuilder.makeNull();
1266
1267     return UnknownVal();
1268   }
1269
1270   return UndefinedVal();
1271 }
1272
1273 SVal RegionStoreManager::RetrieveLazySymbol(const TypedValueRegion *R) {
1274   // All other values are symbolic.
1275   return svalBuilder.getRegionValueSymbolVal(R);
1276 }
1277
1278 SVal RegionStoreManager::RetrieveStruct(Store store,
1279                                         const TypedValueRegion* R) {
1280   QualType T = R->getValueType();
1281   assert(T->isStructureOrClassType());
1282   return svalBuilder.makeLazyCompoundVal(StoreRef(store, *this), R);
1283 }
1284
1285 SVal RegionStoreManager::RetrieveArray(Store store,
1286                                        const TypedValueRegion * R) {
1287   assert(Ctx.getAsConstantArrayType(R->getValueType()));
1288   return svalBuilder.makeLazyCompoundVal(StoreRef(store, *this), R);
1289 }
1290
1291 bool RegionStoreManager::includedInBindings(Store store,
1292                                             const MemRegion *region) const {
1293   RegionBindings B = GetRegionBindings(store);
1294   region = region->getBaseRegion();
1295
1296   for (RegionBindings::iterator it = B.begin(), ei = B.end(); it != ei; ++it) {
1297     const BindingKey &K = it.getKey();
1298     if (region == K.getRegion())
1299       return true;
1300     const SVal &D = it.getData();
1301     if (const MemRegion *r = D.getAsRegion())
1302       if (r == region)
1303         return true;
1304   }
1305   return false;
1306 }
1307
1308 //===----------------------------------------------------------------------===//
1309 // Binding values to regions.
1310 //===----------------------------------------------------------------------===//
1311
1312 StoreRef RegionStoreManager::Remove(Store store, Loc L) {
1313   if (isa<loc::MemRegionVal>(L))
1314     if (const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion())
1315       return StoreRef(removeBinding(GetRegionBindings(store),
1316                                     R).getRootWithoutRetain(),
1317                       *this);
1318
1319   return StoreRef(store, *this);
1320 }
1321
1322 StoreRef RegionStoreManager::Bind(Store store, Loc L, SVal V) {
1323   if (isa<loc::ConcreteInt>(L))
1324     return StoreRef(store, *this);
1325
1326   // If we get here, the location should be a region.
1327   const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion();
1328
1329   // Check if the region is a struct region.
1330   if (const TypedValueRegion* TR = dyn_cast<TypedValueRegion>(R))
1331     if (TR->getValueType()->isStructureOrClassType())
1332       return BindStruct(store, TR, V);
1333
1334   if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
1335     if (ER->getIndex().isZeroConstant()) {
1336       if (const TypedValueRegion *superR =
1337             dyn_cast<TypedValueRegion>(ER->getSuperRegion())) {
1338         QualType superTy = superR->getValueType();
1339         // For now, just invalidate the fields of the struct/union/class.
1340         // This is for test rdar_test_7185607 in misc-ps-region-store.m.
1341         // FIXME: Precisely handle the fields of the record.
1342         if (superTy->isStructureOrClassType())
1343           return KillStruct(store, superR, UnknownVal());
1344       }
1345     }
1346   }
1347   else if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) {
1348     // Binding directly to a symbolic region should be treated as binding
1349     // to element 0.
1350     QualType T = SR->getSymbol()->getType(Ctx);
1351
1352     // FIXME: Is this the right way to handle symbols that are references?
1353     if (const PointerType *PT = T->getAs<PointerType>())
1354       T = PT->getPointeeType();
1355     else
1356       T = T->getAs<ReferenceType>()->getPointeeType();
1357
1358     R = GetElementZeroRegion(SR, T);
1359   }
1360
1361   // Perform the binding.
1362   RegionBindings B = GetRegionBindings(store);
1363   return StoreRef(addBinding(B, R, BindingKey::Direct,
1364                              V).getRootWithoutRetain(), *this);
1365 }
1366
1367 StoreRef RegionStoreManager::BindDecl(Store store, const VarRegion *VR,
1368                                       SVal InitVal) {
1369
1370   QualType T = VR->getDecl()->getType();
1371
1372   if (T->isArrayType())
1373     return BindArray(store, VR, InitVal);
1374   if (T->isStructureOrClassType())
1375     return BindStruct(store, VR, InitVal);
1376
1377   return Bind(store, svalBuilder.makeLoc(VR), InitVal);
1378 }
1379
1380 // FIXME: this method should be merged into Bind().
1381 StoreRef RegionStoreManager::BindCompoundLiteral(Store store,
1382                                                  const CompoundLiteralExpr *CL,
1383                                                  const LocationContext *LC,
1384                                                  SVal V) {
1385   return Bind(store, loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL, LC)),
1386               V);
1387 }
1388
1389 StoreRef RegionStoreManager::setImplicitDefaultValue(Store store,
1390                                                      const MemRegion *R,
1391                                                      QualType T) {
1392   RegionBindings B = GetRegionBindings(store);
1393   SVal V;
1394
1395   if (Loc::isLocType(T))
1396     V = svalBuilder.makeNull();
1397   else if (T->isIntegerType())
1398     V = svalBuilder.makeZeroVal(T);
1399   else if (T->isStructureOrClassType() || T->isArrayType()) {
1400     // Set the default value to a zero constant when it is a structure
1401     // or array.  The type doesn't really matter.
1402     V = svalBuilder.makeZeroVal(Ctx.IntTy);
1403   }
1404   else {
1405     // We can't represent values of this type, but we still need to set a value
1406     // to record that the region has been initialized.
1407     // If this assertion ever fires, a new case should be added above -- we
1408     // should know how to default-initialize any value we can symbolicate.
1409     assert(!SymbolManager::canSymbolicate(T) && "This type is representable");
1410     V = UnknownVal();
1411   }
1412
1413   return StoreRef(addBinding(B, R, BindingKey::Default,
1414                              V).getRootWithoutRetain(), *this);
1415 }
1416
1417 StoreRef RegionStoreManager::BindArray(Store store, const TypedValueRegion* R,
1418                                        SVal Init) {
1419
1420   const ArrayType *AT =cast<ArrayType>(Ctx.getCanonicalType(R->getValueType()));
1421   QualType ElementTy = AT->getElementType();
1422   Optional<uint64_t> Size;
1423
1424   if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(AT))
1425     Size = CAT->getSize().getZExtValue();
1426
1427   // Check if the init expr is a string literal.
1428   if (loc::MemRegionVal *MRV = dyn_cast<loc::MemRegionVal>(&Init)) {
1429     const StringRegion *S = cast<StringRegion>(MRV->getRegion());
1430
1431     // Treat the string as a lazy compound value.
1432     nonloc::LazyCompoundVal LCV =
1433       cast<nonloc::LazyCompoundVal>(svalBuilder.
1434                                 makeLazyCompoundVal(StoreRef(store, *this), S));
1435     return CopyLazyBindings(LCV, store, R);
1436   }
1437
1438   // Handle lazy compound values.
1439   if (nonloc::LazyCompoundVal *LCV = dyn_cast<nonloc::LazyCompoundVal>(&Init))
1440     return CopyLazyBindings(*LCV, store, R);
1441
1442   // Remaining case: explicit compound values.
1443
1444   if (Init.isUnknown())
1445     return setImplicitDefaultValue(store, R, ElementTy);
1446
1447   nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(Init);
1448   nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
1449   uint64_t i = 0;
1450
1451   StoreRef newStore(store, *this);
1452   for (; Size.hasValue() ? i < Size.getValue() : true ; ++i, ++VI) {
1453     // The init list might be shorter than the array length.
1454     if (VI == VE)
1455       break;
1456
1457     const NonLoc &Idx = svalBuilder.makeArrayIndex(i);
1458     const ElementRegion *ER = MRMgr.getElementRegion(ElementTy, Idx, R, Ctx);
1459
1460     if (ElementTy->isStructureOrClassType())
1461       newStore = BindStruct(newStore.getStore(), ER, *VI);
1462     else if (ElementTy->isArrayType())
1463       newStore = BindArray(newStore.getStore(), ER, *VI);
1464     else
1465       newStore = Bind(newStore.getStore(), svalBuilder.makeLoc(ER), *VI);
1466   }
1467
1468   // If the init list is shorter than the array length, set the
1469   // array default value.
1470   if (Size.hasValue() && i < Size.getValue())
1471     newStore = setImplicitDefaultValue(newStore.getStore(), R, ElementTy);
1472
1473   return newStore;
1474 }
1475
1476 StoreRef RegionStoreManager::BindStruct(Store store, const TypedValueRegion* R,
1477                                         SVal V) {
1478
1479   if (!Features.supportsFields())
1480     return StoreRef(store, *this);
1481
1482   QualType T = R->getValueType();
1483   assert(T->isStructureOrClassType());
1484
1485   const RecordType* RT = T->getAs<RecordType>();
1486   RecordDecl *RD = RT->getDecl();
1487
1488   if (!RD->isCompleteDefinition())
1489     return StoreRef(store, *this);
1490
1491   // Handle lazy compound values.
1492   if (const nonloc::LazyCompoundVal *LCV=dyn_cast<nonloc::LazyCompoundVal>(&V))
1493     return CopyLazyBindings(*LCV, store, R);
1494
1495   // We may get non-CompoundVal accidentally due to imprecise cast logic or
1496   // that we are binding symbolic struct value. Kill the field values, and if
1497   // the value is symbolic go and bind it as a "default" binding.
1498   if (V.isUnknown() || !isa<nonloc::CompoundVal>(V)) {
1499     SVal SV = isa<nonloc::SymbolVal>(V) ? V : UnknownVal();
1500     return KillStruct(store, R, SV);
1501   }
1502
1503   nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V);
1504   nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
1505
1506   RecordDecl::field_iterator FI, FE;
1507   StoreRef newStore(store, *this);
1508
1509   for (FI = RD->field_begin(), FE = RD->field_end(); FI != FE; ++FI, ++VI) {
1510
1511     if (VI == VE)
1512       break;
1513
1514     QualType FTy = (*FI)->getType();
1515     const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);
1516
1517     if (FTy->isArrayType())
1518       newStore = BindArray(newStore.getStore(), FR, *VI);
1519     else if (FTy->isStructureOrClassType())
1520       newStore = BindStruct(newStore.getStore(), FR, *VI);
1521     else
1522       newStore = Bind(newStore.getStore(), svalBuilder.makeLoc(FR), *VI);
1523   }
1524
1525   // There may be fewer values in the initialize list than the fields of struct.
1526   if (FI != FE) {
1527     RegionBindings B = GetRegionBindings(newStore.getStore());
1528     B = addBinding(B, R, BindingKey::Default, svalBuilder.makeIntVal(0, false));
1529     newStore = StoreRef(B.getRootWithoutRetain(), *this);
1530   }
1531
1532   return newStore;
1533 }
1534
1535 StoreRef RegionStoreManager::KillStruct(Store store, const TypedRegion* R,
1536                                      SVal DefaultVal) {
1537   BindingKey key = BindingKey::Make(R, BindingKey::Default);
1538
1539   // The BindingKey may be "invalid" if we cannot handle the region binding
1540   // explicitly.  One example is something like array[index], where index
1541   // is a symbolic value.  In such cases, we want to invalidate the entire
1542   // array, as the index assignment could have been to any element.  In
1543   // the case of nested symbolic indices, we need to march up the region
1544   // hierarchy untile we reach a region whose binding we can reason about.
1545   const SubRegion *subReg = R;
1546
1547   while (!key.isValid()) {
1548     if (const SubRegion *tmp = dyn_cast<SubRegion>(subReg->getSuperRegion())) {
1549       subReg = tmp;
1550       key = BindingKey::Make(tmp, BindingKey::Default);
1551     }
1552     else
1553       break;
1554   }
1555
1556   // Remove the old bindings, using 'subReg' as the root of all regions
1557   // we will invalidate.
1558   RegionBindings B = GetRegionBindings(store);
1559   llvm::OwningPtr<RegionStoreSubRegionMap>
1560     SubRegions(getRegionStoreSubRegionMap(store));
1561   RemoveSubRegionBindings(B, subReg, *SubRegions);
1562
1563   // Set the default value of the struct region to "unknown".
1564   if (!key.isValid())
1565     return StoreRef(B.getRootWithoutRetain(), *this);
1566
1567   return StoreRef(addBinding(B, key, DefaultVal).getRootWithoutRetain(), *this);
1568 }
1569
1570 StoreRef RegionStoreManager::CopyLazyBindings(nonloc::LazyCompoundVal V,
1571                                               Store store,
1572                                               const TypedRegion *R) {
1573
1574   // Nuke the old bindings stemming from R.
1575   RegionBindings B = GetRegionBindings(store);
1576
1577   llvm::OwningPtr<RegionStoreSubRegionMap>
1578     SubRegions(getRegionStoreSubRegionMap(store));
1579
1580   // B and DVM are updated after the call to RemoveSubRegionBindings.
1581   RemoveSubRegionBindings(B, R, *SubRegions.get());
1582
1583   // Now copy the bindings.  This amounts to just binding 'V' to 'R'.  This
1584   // results in a zero-copy algorithm.
1585   return StoreRef(addBinding(B, R, BindingKey::Default,
1586                              V).getRootWithoutRetain(), *this);
1587 }
1588
1589 //===----------------------------------------------------------------------===//
1590 // "Raw" retrievals and bindings.
1591 //===----------------------------------------------------------------------===//
1592
1593
1594 RegionBindings RegionStoreManager::addBinding(RegionBindings B, BindingKey K,
1595                                               SVal V) {
1596   if (!K.isValid())
1597     return B;
1598   return RBFactory.add(B, K, V);
1599 }
1600
1601 RegionBindings RegionStoreManager::addBinding(RegionBindings B,
1602                                               const MemRegion *R,
1603                                               BindingKey::Kind k, SVal V) {
1604   return addBinding(B, BindingKey::Make(R, k), V);
1605 }
1606
1607 const SVal *RegionStoreManager::lookup(RegionBindings B, BindingKey K) {
1608   if (!K.isValid())
1609     return NULL;
1610   return B.lookup(K);
1611 }
1612
1613 const SVal *RegionStoreManager::lookup(RegionBindings B,
1614                                        const MemRegion *R,
1615                                        BindingKey::Kind k) {
1616   return lookup(B, BindingKey::Make(R, k));
1617 }
1618
1619 RegionBindings RegionStoreManager::removeBinding(RegionBindings B,
1620                                                  BindingKey K) {
1621   if (!K.isValid())
1622     return B;
1623   return RBFactory.remove(B, K);
1624 }
1625
1626 RegionBindings RegionStoreManager::removeBinding(RegionBindings B,
1627                                                  const MemRegion *R,
1628                                                 BindingKey::Kind k){
1629   return removeBinding(B, BindingKey::Make(R, k));
1630 }
1631
1632 //===----------------------------------------------------------------------===//
1633 // State pruning.
1634 //===----------------------------------------------------------------------===//
1635
1636 namespace {
1637 class removeDeadBindingsWorker :
1638   public ClusterAnalysis<removeDeadBindingsWorker> {
1639   SmallVector<const SymbolicRegion*, 12> Postponed;
1640   SymbolReaper &SymReaper;
1641   const StackFrameContext *CurrentLCtx;
1642
1643 public:
1644   removeDeadBindingsWorker(RegionStoreManager &rm, ProgramStateManager &stateMgr,
1645                            RegionBindings b, SymbolReaper &symReaper,
1646                            const StackFrameContext *LCtx)
1647     : ClusterAnalysis<removeDeadBindingsWorker>(rm, stateMgr, b,
1648                                                 /* includeGlobals = */ false),
1649       SymReaper(symReaper), CurrentLCtx(LCtx) {}
1650
1651   // Called by ClusterAnalysis.
1652   void VisitAddedToCluster(const MemRegion *baseR, RegionCluster &C);
1653   void VisitCluster(const MemRegion *baseR, BindingKey *I, BindingKey *E);
1654
1655   void VisitBindingKey(BindingKey K);
1656   bool UpdatePostponed();
1657   void VisitBinding(SVal V);
1658 };
1659 }
1660
1661 void removeDeadBindingsWorker::VisitAddedToCluster(const MemRegion *baseR,
1662                                                    RegionCluster &C) {
1663
1664   if (const VarRegion *VR = dyn_cast<VarRegion>(baseR)) {
1665     if (SymReaper.isLive(VR))
1666       AddToWorkList(baseR, C);
1667
1668     return;
1669   }
1670
1671   if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) {
1672     if (SymReaper.isLive(SR->getSymbol()))
1673       AddToWorkList(SR, C);
1674     else
1675       Postponed.push_back(SR);
1676
1677     return;
1678   }
1679
1680   if (isa<NonStaticGlobalSpaceRegion>(baseR)) {
1681     AddToWorkList(baseR, C);
1682     return;
1683   }
1684
1685   // CXXThisRegion in the current or parent location context is live.
1686   if (const CXXThisRegion *TR = dyn_cast<CXXThisRegion>(baseR)) {
1687     const StackArgumentsSpaceRegion *StackReg =
1688       cast<StackArgumentsSpaceRegion>(TR->getSuperRegion());
1689     const StackFrameContext *RegCtx = StackReg->getStackFrame();
1690     if (RegCtx == CurrentLCtx || RegCtx->isParentOf(CurrentLCtx))
1691       AddToWorkList(TR, C);
1692   }
1693 }
1694
1695 void removeDeadBindingsWorker::VisitCluster(const MemRegion *baseR,
1696                                             BindingKey *I, BindingKey *E) {
1697   for ( ; I != E; ++I)
1698     VisitBindingKey(*I);
1699 }
1700
1701 void removeDeadBindingsWorker::VisitBinding(SVal V) {
1702   // Is it a LazyCompoundVal?  All referenced regions are live as well.
1703   if (const nonloc::LazyCompoundVal *LCS =
1704       dyn_cast<nonloc::LazyCompoundVal>(&V)) {
1705
1706     const MemRegion *LazyR = LCS->getRegion();
1707     RegionBindings B = RegionStoreManager::GetRegionBindings(LCS->getStore());
1708     for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){
1709       const SubRegion *baseR = dyn_cast<SubRegion>(RI.getKey().getRegion());
1710       if (baseR && baseR->isSubRegionOf(LazyR))
1711         VisitBinding(RI.getData());
1712     }
1713     return;
1714   }
1715
1716   // If V is a region, then add it to the worklist.
1717   if (const MemRegion *R = V.getAsRegion())
1718     AddToWorkList(R);
1719
1720     // Update the set of live symbols.
1721   for (SVal::symbol_iterator SI=V.symbol_begin(), SE=V.symbol_end();
1722        SI!=SE;++SI)
1723     SymReaper.markLive(*SI);
1724 }
1725
1726 void removeDeadBindingsWorker::VisitBindingKey(BindingKey K) {
1727   const MemRegion *R = K.getRegion();
1728
1729   // Mark this region "live" by adding it to the worklist.  This will cause
1730   // use to visit all regions in the cluster (if we haven't visited them
1731   // already).
1732   if (AddToWorkList(R)) {
1733     // Mark the symbol for any live SymbolicRegion as "live".  This means we
1734     // should continue to track that symbol.
1735     if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(R))
1736       SymReaper.markLive(SymR->getSymbol());
1737
1738     // For BlockDataRegions, enqueue the VarRegions for variables marked
1739     // with __block (passed-by-reference).
1740     // via BlockDeclRefExprs.
1741     if (const BlockDataRegion *BD = dyn_cast<BlockDataRegion>(R)) {
1742       for (BlockDataRegion::referenced_vars_iterator
1743            RI = BD->referenced_vars_begin(), RE = BD->referenced_vars_end();
1744            RI != RE; ++RI) {
1745         if ((*RI)->getDecl()->getAttr<BlocksAttr>())
1746           AddToWorkList(*RI);
1747       }
1748
1749       // No possible data bindings on a BlockDataRegion.
1750       return;
1751     }
1752   }
1753
1754   // Visit the data binding for K.
1755   if (const SVal *V = RM.lookup(B, K))
1756     VisitBinding(*V);
1757 }
1758
1759 bool removeDeadBindingsWorker::UpdatePostponed() {
1760   // See if any postponed SymbolicRegions are actually live now, after
1761   // having done a scan.
1762   bool changed = false;
1763
1764   for (SmallVectorImpl<const SymbolicRegion*>::iterator
1765         I = Postponed.begin(), E = Postponed.end() ; I != E ; ++I) {
1766     if (const SymbolicRegion *SR = cast_or_null<SymbolicRegion>(*I)) {
1767       if (SymReaper.isLive(SR->getSymbol())) {
1768         changed |= AddToWorkList(SR);
1769         *I = NULL;
1770       }
1771     }
1772   }
1773
1774   return changed;
1775 }
1776
1777 StoreRef RegionStoreManager::removeDeadBindings(Store store,
1778                                                 const StackFrameContext *LCtx,
1779                                                 SymbolReaper& SymReaper) {
1780   RegionBindings B = GetRegionBindings(store);
1781   removeDeadBindingsWorker W(*this, StateMgr, B, SymReaper, LCtx);
1782   W.GenerateClusters();
1783
1784   // Enqueue the region roots onto the worklist.
1785   for (SymbolReaper::region_iterator I = SymReaper.region_begin(),
1786        E = SymReaper.region_end(); I != E; ++I) {
1787     W.AddToWorkList(*I);
1788   }
1789
1790   do W.RunWorkList(); while (W.UpdatePostponed());
1791
1792   // We have now scanned the store, marking reachable regions and symbols
1793   // as live.  We now remove all the regions that are dead from the store
1794   // as well as update DSymbols with the set symbols that are now dead.
1795   for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) {
1796     const BindingKey &K = I.getKey();
1797
1798     // If the cluster has been visited, we know the region has been marked.
1799     if (W.isVisited(K.getRegion()))
1800       continue;
1801
1802     // Remove the dead entry.
1803     B = removeBinding(B, K);
1804
1805     // Mark all non-live symbols that this binding references as dead.
1806     if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(K.getRegion()))
1807       SymReaper.maybeDead(SymR->getSymbol());
1808
1809     SVal X = I.getData();
1810     SVal::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
1811     for (; SI != SE; ++SI)
1812       SymReaper.maybeDead(*SI);
1813   }
1814
1815   return StoreRef(B.getRootWithoutRetain(), *this);
1816 }
1817
1818
1819 StoreRef RegionStoreManager::enterStackFrame(const ProgramState *state,
1820                                              const StackFrameContext *frame) {
1821   FunctionDecl const *FD = cast<FunctionDecl>(frame->getDecl());
1822   FunctionDecl::param_const_iterator PI = FD->param_begin(),
1823                                      PE = FD->param_end();
1824   StoreRef store = StoreRef(state->getStore(), *this);
1825
1826   if (CallExpr const *CE = dyn_cast<CallExpr>(frame->getCallSite())) {
1827     CallExpr::const_arg_iterator AI = CE->arg_begin(), AE = CE->arg_end();
1828
1829     // Copy the arg expression value to the arg variables.  We check that
1830     // PI != PE because the actual number of arguments may be different than
1831     // the function declaration.
1832     for (; AI != AE && PI != PE; ++AI, ++PI) {
1833       SVal ArgVal = state->getSVal(*AI);
1834       store = Bind(store.getStore(),
1835                    svalBuilder.makeLoc(MRMgr.getVarRegion(*PI, frame)), ArgVal);
1836     }
1837   } else if (const CXXConstructExpr *CE =
1838                dyn_cast<CXXConstructExpr>(frame->getCallSite())) {
1839     CXXConstructExpr::const_arg_iterator AI = CE->arg_begin(),
1840       AE = CE->arg_end();
1841
1842     // Copy the arg expression value to the arg variables.
1843     for (; AI != AE; ++AI, ++PI) {
1844       SVal ArgVal = state->getSVal(*AI);
1845       store = Bind(store.getStore(),
1846                    svalBuilder.makeLoc(MRMgr.getVarRegion(*PI,frame)), ArgVal);
1847     }
1848   } else
1849     assert(isa<CXXDestructorDecl>(frame->getDecl()));
1850
1851   return store;
1852 }
1853
1854 //===----------------------------------------------------------------------===//
1855 // Utility methods.
1856 //===----------------------------------------------------------------------===//
1857
1858 void RegionStoreManager::print(Store store, raw_ostream &OS,
1859                                const char* nl, const char *sep) {
1860   RegionBindings B = GetRegionBindings(store);
1861   OS << "Store (direct and default bindings):" << nl;
1862
1863   for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I)
1864     OS << ' ' << I.getKey() << " : " << I.getData() << nl;
1865 }