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