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