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

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