contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/RegionStore.cpp

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