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