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