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