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