1218887Sdim//== RegionStore.cpp - Field-sensitive store model --------------*- C++ -*--==// 2218887Sdim// 3218887Sdim// The LLVM Compiler Infrastructure 4218887Sdim// 5218887Sdim// This file is distributed under the University of Illinois Open Source 6218887Sdim// License. See LICENSE.TXT for details. 7218887Sdim// 8218887Sdim//===----------------------------------------------------------------------===// 9218887Sdim// 10218887Sdim// This file defines a basic region store model. In this model, we do have field 11218887Sdim// sensitivity. But we assume nothing about the heap shape. So recursive data 12218887Sdim// structures are largely ignored. Basically we do 1-limiting analysis. 13218887Sdim// Parameter pointers are assumed with no aliasing. Pointee objects of 14218887Sdim// parameters are created lazily. 15218887Sdim// 16218887Sdim//===----------------------------------------------------------------------===// 17249423Sdim#include "clang/AST/Attr.h" 18218887Sdim#include "clang/AST/CharUnits.h" 19218887Sdim#include "clang/Analysis/Analyses/LiveVariables.h" 20218887Sdim#include "clang/Analysis/AnalysisContext.h" 21218887Sdim#include "clang/Basic/TargetInfo.h" 22251662Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" 23239462Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 24249423Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 25226633Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 26226633Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 27251662Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h" 28218887Sdim#include "llvm/ADT/ImmutableList.h" 29218887Sdim#include "llvm/ADT/ImmutableMap.h" 30218887Sdim#include "llvm/ADT/Optional.h" 31218887Sdim#include "llvm/Support/raw_ostream.h" 32218887Sdim 33218887Sdimusing namespace clang; 34218887Sdimusing namespace ento; 35218887Sdim 36218887Sdim//===----------------------------------------------------------------------===// 37218887Sdim// Representation of binding keys. 38218887Sdim//===----------------------------------------------------------------------===// 39218887Sdim 40218887Sdimnamespace { 41218887Sdimclass BindingKey { 42218887Sdimpublic: 43239462Sdim enum Kind { Default = 0x0, Direct = 0x1 }; 44218887Sdimprivate: 45239462Sdim enum { Symbolic = 0x2 }; 46218887Sdim 47239462Sdim llvm::PointerIntPair<const MemRegion *, 2> P; 48239462Sdim uint64_t Data; 49239462Sdim 50249423Sdim /// Create a key for a binding to region \p r, which has a symbolic offset 51249423Sdim /// from region \p Base. 52249423Sdim explicit BindingKey(const SubRegion *r, const SubRegion *Base, Kind k) 53239462Sdim : P(r, k | Symbolic), Data(reinterpret_cast<uintptr_t>(Base)) { 54239462Sdim assert(r && Base && "Must have known regions."); 55239462Sdim assert(getConcreteOffsetRegion() == Base && "Failed to store base region"); 56239462Sdim } 57249423Sdim 58249423Sdim /// Create a key for a binding at \p offset from base region \p r. 59218887Sdim explicit BindingKey(const MemRegion *r, uint64_t offset, Kind k) 60239462Sdim : P(r, k), Data(offset) { 61239462Sdim assert(r && "Must have known regions."); 62239462Sdim assert(getOffset() == offset && "Failed to store offset"); 63239462Sdim assert((r == r->getBaseRegion() || isa<ObjCIvarRegion>(r)) && "Not a base"); 64239462Sdim } 65218887Sdimpublic: 66218887Sdim 67239462Sdim bool isDirect() const { return P.getInt() & Direct; } 68239462Sdim bool hasSymbolicOffset() const { return P.getInt() & Symbolic; } 69218887Sdim 70218887Sdim const MemRegion *getRegion() const { return P.getPointer(); } 71239462Sdim uint64_t getOffset() const { 72239462Sdim assert(!hasSymbolicOffset()); 73239462Sdim return Data; 74239462Sdim } 75218887Sdim 76249423Sdim const SubRegion *getConcreteOffsetRegion() const { 77239462Sdim assert(hasSymbolicOffset()); 78249423Sdim return reinterpret_cast<const SubRegion *>(static_cast<uintptr_t>(Data)); 79239462Sdim } 80239462Sdim 81239462Sdim const MemRegion *getBaseRegion() const { 82239462Sdim if (hasSymbolicOffset()) 83239462Sdim return getConcreteOffsetRegion()->getBaseRegion(); 84239462Sdim return getRegion()->getBaseRegion(); 85239462Sdim } 86239462Sdim 87218887Sdim void Profile(llvm::FoldingSetNodeID& ID) const { 88218887Sdim ID.AddPointer(P.getOpaqueValue()); 89239462Sdim ID.AddInteger(Data); 90218887Sdim } 91218887Sdim 92218887Sdim static BindingKey Make(const MemRegion *R, Kind k); 93218887Sdim 94218887Sdim bool operator<(const BindingKey &X) const { 95218887Sdim if (P.getOpaqueValue() < X.P.getOpaqueValue()) 96218887Sdim return true; 97218887Sdim if (P.getOpaqueValue() > X.P.getOpaqueValue()) 98218887Sdim return false; 99239462Sdim return Data < X.Data; 100218887Sdim } 101218887Sdim 102218887Sdim bool operator==(const BindingKey &X) const { 103218887Sdim return P.getOpaqueValue() == X.P.getOpaqueValue() && 104239462Sdim Data == X.Data; 105218887Sdim } 106218887Sdim 107239462Sdim LLVM_ATTRIBUTE_USED void dump() const; 108218887Sdim}; 109218887Sdim} // end anonymous namespace 110218887Sdim 111218887SdimBindingKey BindingKey::Make(const MemRegion *R, Kind k) { 112239462Sdim const RegionOffset &RO = R->getAsOffset(); 113239462Sdim if (RO.hasSymbolicOffset()) 114249423Sdim return BindingKey(cast<SubRegion>(R), cast<SubRegion>(RO.getRegion()), k); 115218887Sdim 116239462Sdim return BindingKey(RO.getRegion(), RO.getOffset(), k); 117218887Sdim} 118218887Sdim 119218887Sdimnamespace llvm { 120218887Sdim static inline 121226633Sdim raw_ostream &operator<<(raw_ostream &os, BindingKey K) { 122239462Sdim os << '(' << K.getRegion(); 123239462Sdim if (!K.hasSymbolicOffset()) 124239462Sdim os << ',' << K.getOffset(); 125239462Sdim os << ',' << (K.isDirect() ? "direct" : "default") 126218887Sdim << ')'; 127218887Sdim return os; 128218887Sdim } 129249423Sdim 130249423Sdim template <typename T> struct isPodLike; 131249423Sdim template <> struct isPodLike<BindingKey> { 132249423Sdim static const bool value = true; 133249423Sdim }; 134218887Sdim} // end llvm namespace 135218887Sdim 136239462Sdimvoid BindingKey::dump() const { 137239462Sdim llvm::errs() << *this; 138239462Sdim} 139239462Sdim 140218887Sdim//===----------------------------------------------------------------------===// 141218887Sdim// Actual Store type. 142218887Sdim//===----------------------------------------------------------------------===// 143218887Sdim 144249423Sdimtypedef llvm::ImmutableMap<BindingKey, SVal> ClusterBindings; 145249423Sdimtypedef llvm::ImmutableMapRef<BindingKey, SVal> ClusterBindingsRef; 146249423Sdimtypedef std::pair<BindingKey, SVal> BindingPair; 147218887Sdim 148249423Sdimtypedef llvm::ImmutableMap<const MemRegion *, ClusterBindings> 149249423Sdim RegionBindings; 150249423Sdim 151249423Sdimnamespace { 152249423Sdimclass RegionBindingsRef : public llvm::ImmutableMapRef<const MemRegion *, 153249423Sdim ClusterBindings> { 154249423Sdim ClusterBindings::Factory &CBFactory; 155249423Sdimpublic: 156249423Sdim typedef llvm::ImmutableMapRef<const MemRegion *, ClusterBindings> 157249423Sdim ParentTy; 158249423Sdim 159249423Sdim RegionBindingsRef(ClusterBindings::Factory &CBFactory, 160249423Sdim const RegionBindings::TreeTy *T, 161249423Sdim RegionBindings::TreeTy::Factory *F) 162249423Sdim : llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>(T, F), 163249423Sdim CBFactory(CBFactory) {} 164249423Sdim 165249423Sdim RegionBindingsRef(const ParentTy &P, ClusterBindings::Factory &CBFactory) 166249423Sdim : llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>(P), 167249423Sdim CBFactory(CBFactory) {} 168249423Sdim 169249423Sdim RegionBindingsRef add(key_type_ref K, data_type_ref D) const { 170249423Sdim return RegionBindingsRef(static_cast<const ParentTy*>(this)->add(K, D), 171249423Sdim CBFactory); 172249423Sdim } 173249423Sdim 174249423Sdim RegionBindingsRef remove(key_type_ref K) const { 175249423Sdim return RegionBindingsRef(static_cast<const ParentTy*>(this)->remove(K), 176249423Sdim CBFactory); 177249423Sdim } 178249423Sdim 179249423Sdim RegionBindingsRef addBinding(BindingKey K, SVal V) const; 180249423Sdim 181249423Sdim RegionBindingsRef addBinding(const MemRegion *R, 182249423Sdim BindingKey::Kind k, SVal V) const; 183249423Sdim 184249423Sdim RegionBindingsRef &operator=(const RegionBindingsRef &X) { 185249423Sdim *static_cast<ParentTy*>(this) = X; 186249423Sdim return *this; 187249423Sdim } 188249423Sdim 189249423Sdim const SVal *lookup(BindingKey K) const; 190249423Sdim const SVal *lookup(const MemRegion *R, BindingKey::Kind k) const; 191249423Sdim const ClusterBindings *lookup(const MemRegion *R) const { 192249423Sdim return static_cast<const ParentTy*>(this)->lookup(R); 193249423Sdim } 194249423Sdim 195249423Sdim RegionBindingsRef removeBinding(BindingKey K); 196249423Sdim 197249423Sdim RegionBindingsRef removeBinding(const MemRegion *R, 198249423Sdim BindingKey::Kind k); 199249423Sdim 200249423Sdim RegionBindingsRef removeBinding(const MemRegion *R) { 201249423Sdim return removeBinding(R, BindingKey::Direct). 202249423Sdim removeBinding(R, BindingKey::Default); 203249423Sdim } 204249423Sdim 205249423Sdim Optional<SVal> getDirectBinding(const MemRegion *R) const; 206249423Sdim 207249423Sdim /// getDefaultBinding - Returns an SVal* representing an optional default 208249423Sdim /// binding associated with a region and its subregions. 209249423Sdim Optional<SVal> getDefaultBinding(const MemRegion *R) const; 210249423Sdim 211249423Sdim /// Return the internal tree as a Store. 212249423Sdim Store asStore() const { 213249423Sdim return asImmutableMap().getRootWithoutRetain(); 214249423Sdim } 215249423Sdim 216249423Sdim void dump(raw_ostream &OS, const char *nl) const { 217249423Sdim for (iterator I = begin(), E = end(); I != E; ++I) { 218249423Sdim const ClusterBindings &Cluster = I.getData(); 219249423Sdim for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); 220249423Sdim CI != CE; ++CI) { 221249423Sdim OS << ' ' << CI.getKey() << " : " << CI.getData() << nl; 222249423Sdim } 223249423Sdim OS << nl; 224249423Sdim } 225249423Sdim } 226249423Sdim 227249423Sdim LLVM_ATTRIBUTE_USED void dump() const { 228249423Sdim dump(llvm::errs(), "\n"); 229249423Sdim } 230249423Sdim}; 231249423Sdim} // end anonymous namespace 232249423Sdim 233249423Sdimtypedef const RegionBindingsRef& RegionBindingsConstRef; 234249423Sdim 235249423SdimOptional<SVal> RegionBindingsRef::getDirectBinding(const MemRegion *R) const { 236249423Sdim return Optional<SVal>::create(lookup(R, BindingKey::Direct)); 237249423Sdim} 238249423Sdim 239249423SdimOptional<SVal> RegionBindingsRef::getDefaultBinding(const MemRegion *R) const { 240249423Sdim if (R->isBoundable()) 241249423Sdim if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) 242249423Sdim if (TR->getValueType()->isUnionType()) 243249423Sdim return UnknownVal(); 244249423Sdim 245249423Sdim return Optional<SVal>::create(lookup(R, BindingKey::Default)); 246249423Sdim} 247249423Sdim 248249423SdimRegionBindingsRef RegionBindingsRef::addBinding(BindingKey K, SVal V) const { 249249423Sdim const MemRegion *Base = K.getBaseRegion(); 250249423Sdim 251249423Sdim const ClusterBindings *ExistingCluster = lookup(Base); 252249423Sdim ClusterBindings Cluster = (ExistingCluster ? *ExistingCluster 253249423Sdim : CBFactory.getEmptyMap()); 254249423Sdim 255249423Sdim ClusterBindings NewCluster = CBFactory.add(Cluster, K, V); 256249423Sdim return add(Base, NewCluster); 257249423Sdim} 258249423Sdim 259249423Sdim 260249423SdimRegionBindingsRef RegionBindingsRef::addBinding(const MemRegion *R, 261249423Sdim BindingKey::Kind k, 262249423Sdim SVal V) const { 263249423Sdim return addBinding(BindingKey::Make(R, k), V); 264249423Sdim} 265249423Sdim 266249423Sdimconst SVal *RegionBindingsRef::lookup(BindingKey K) const { 267249423Sdim const ClusterBindings *Cluster = lookup(K.getBaseRegion()); 268249423Sdim if (!Cluster) 269249423Sdim return 0; 270249423Sdim return Cluster->lookup(K); 271249423Sdim} 272249423Sdim 273249423Sdimconst SVal *RegionBindingsRef::lookup(const MemRegion *R, 274249423Sdim BindingKey::Kind k) const { 275249423Sdim return lookup(BindingKey::Make(R, k)); 276249423Sdim} 277249423Sdim 278249423SdimRegionBindingsRef RegionBindingsRef::removeBinding(BindingKey K) { 279249423Sdim const MemRegion *Base = K.getBaseRegion(); 280249423Sdim const ClusterBindings *Cluster = lookup(Base); 281249423Sdim if (!Cluster) 282249423Sdim return *this; 283249423Sdim 284249423Sdim ClusterBindings NewCluster = CBFactory.remove(*Cluster, K); 285249423Sdim if (NewCluster.isEmpty()) 286249423Sdim return remove(Base); 287249423Sdim return add(Base, NewCluster); 288249423Sdim} 289249423Sdim 290249423SdimRegionBindingsRef RegionBindingsRef::removeBinding(const MemRegion *R, 291249423Sdim BindingKey::Kind k){ 292249423Sdim return removeBinding(BindingKey::Make(R, k)); 293249423Sdim} 294249423Sdim 295218887Sdim//===----------------------------------------------------------------------===// 296218887Sdim// Fine-grained control of RegionStoreManager. 297218887Sdim//===----------------------------------------------------------------------===// 298218887Sdim 299218887Sdimnamespace { 300218887Sdimstruct minimal_features_tag {}; 301218887Sdimstruct maximal_features_tag {}; 302218887Sdim 303218887Sdimclass RegionStoreFeatures { 304218887Sdim bool SupportsFields; 305218887Sdimpublic: 306218887Sdim RegionStoreFeatures(minimal_features_tag) : 307218887Sdim SupportsFields(false) {} 308218887Sdim 309218887Sdim RegionStoreFeatures(maximal_features_tag) : 310218887Sdim SupportsFields(true) {} 311218887Sdim 312218887Sdim void enableFields(bool t) { SupportsFields = t; } 313218887Sdim 314218887Sdim bool supportsFields() const { return SupportsFields; } 315218887Sdim}; 316218887Sdim} 317218887Sdim 318218887Sdim//===----------------------------------------------------------------------===// 319218887Sdim// Main RegionStore logic. 320218887Sdim//===----------------------------------------------------------------------===// 321218887Sdim 322218887Sdimnamespace { 323249423Sdimclass invalidateRegionsWorker; 324218887Sdim 325218887Sdimclass RegionStoreManager : public StoreManager { 326249423Sdimpublic: 327218887Sdim const RegionStoreFeatures Features; 328251662Sdim 329218887Sdim RegionBindings::Factory RBFactory; 330249423Sdim mutable ClusterBindings::Factory CBFactory; 331218887Sdim 332249423Sdim typedef std::vector<SVal> SValListTy; 333249423Sdimprivate: 334249423Sdim typedef llvm::DenseMap<const LazyCompoundValData *, 335249423Sdim SValListTy> LazyBindingsMapTy; 336249423Sdim LazyBindingsMapTy LazyBindingsMap; 337249423Sdim 338251662Sdim /// The largest number of fields a struct can have and still be 339251662Sdim /// considered "small". 340251662Sdim /// 341251662Sdim /// This is currently used to decide whether or not it is worth "forcing" a 342251662Sdim /// LazyCompoundVal on bind. 343251662Sdim /// 344251662Sdim /// This is controlled by 'region-store-small-struct-limit' option. 345251662Sdim /// To disable all small-struct-dependent behavior, set the option to "0". 346251662Sdim unsigned SmallStructLimit; 347251662Sdim 348249423Sdim /// \brief A helper used to populate the work list with the given set of 349249423Sdim /// regions. 350249423Sdim void populateWorkList(invalidateRegionsWorker &W, 351249423Sdim ArrayRef<SVal> Values, 352249423Sdim bool IsArrayOfConstRegions, 353249423Sdim InvalidatedRegions *TopLevelRegions); 354249423Sdim 355218887Sdimpublic: 356226633Sdim RegionStoreManager(ProgramStateManager& mgr, const RegionStoreFeatures &f) 357239462Sdim : StoreManager(mgr), Features(f), 358251662Sdim RBFactory(mgr.getAllocator()), CBFactory(mgr.getAllocator()), 359251662Sdim SmallStructLimit(0) { 360251662Sdim if (SubEngine *Eng = StateMgr.getOwningEngine()) { 361251662Sdim AnalyzerOptions &Options = Eng->getAnalysisManager().options; 362251662Sdim SmallStructLimit = 363251662Sdim Options.getOptionAsInteger("region-store-small-struct-limit", 2); 364251662Sdim } 365251662Sdim } 366218887Sdim 367218887Sdim 368218887Sdim /// setImplicitDefaultValue - Set the default binding for the provided 369218887Sdim /// MemRegion to the value implicitly defined for compound literals when 370218887Sdim /// the value is not specified. 371249423Sdim RegionBindingsRef setImplicitDefaultValue(RegionBindingsConstRef B, 372249423Sdim const MemRegion *R, QualType T); 373218887Sdim 374218887Sdim /// ArrayToPointer - Emulates the "decay" of an array to a pointer 375218887Sdim /// type. 'Array' represents the lvalue of the array being decayed 376218887Sdim /// to a pointer, and the returned SVal represents the decayed 377218887Sdim /// version of that lvalue (i.e., a pointer to the first element of 378218887Sdim /// the array). This is called by ExprEngine when evaluating 379218887Sdim /// casts from arrays to pointers. 380218887Sdim SVal ArrayToPointer(Loc Array); 381218887Sdim 382218887Sdim StoreRef getInitialStore(const LocationContext *InitLoc) { 383218887Sdim return StoreRef(RBFactory.getEmptyMap().getRootWithoutRetain(), *this); 384218887Sdim } 385218887Sdim 386218887Sdim //===-------------------------------------------------------------------===// 387218887Sdim // Binding values to regions. 388218887Sdim //===-------------------------------------------------------------------===// 389249423Sdim RegionBindingsRef invalidateGlobalRegion(MemRegion::Kind K, 390249423Sdim const Expr *Ex, 391249423Sdim unsigned Count, 392249423Sdim const LocationContext *LCtx, 393249423Sdim RegionBindingsRef B, 394249423Sdim InvalidatedRegions *Invalidated); 395218887Sdim 396249423Sdim StoreRef invalidateRegions(Store store, 397249423Sdim ArrayRef<SVal> Values, 398249423Sdim ArrayRef<SVal> ConstValues, 399218887Sdim const Expr *E, unsigned Count, 400234353Sdim const LocationContext *LCtx, 401249423Sdim const CallEvent *Call, 402223017Sdim InvalidatedSymbols &IS, 403249423Sdim InvalidatedSymbols &ConstIS, 404249423Sdim InvalidatedRegions *Invalidated, 405249423Sdim InvalidatedRegions *InvalidatedTopLevel, 406249423Sdim InvalidatedRegions *InvalidatedTopLevelConst); 407218887Sdim 408239462Sdim bool scanReachableSymbols(Store S, const MemRegion *R, 409239462Sdim ScanReachableSymbols &Callbacks); 410239462Sdim 411249423Sdim RegionBindingsRef removeSubRegionBindings(RegionBindingsConstRef B, 412249423Sdim const SubRegion *R); 413218887Sdim 414249423Sdimpublic: // Part of public interface to class. 415218887Sdim 416249423Sdim virtual StoreRef Bind(Store store, Loc LV, SVal V) { 417249423Sdim return StoreRef(bind(getRegionBindings(store), LV, V).asStore(), *this); 418218887Sdim } 419218887Sdim 420249423Sdim RegionBindingsRef bind(RegionBindingsConstRef B, Loc LV, SVal V); 421239462Sdim 422218887Sdim // BindDefault is only used to initialize a region with a default value. 423218887Sdim StoreRef BindDefault(Store store, const MemRegion *R, SVal V) { 424249423Sdim RegionBindingsRef B = getRegionBindings(store); 425249423Sdim assert(!B.lookup(R, BindingKey::Default)); 426249423Sdim assert(!B.lookup(R, BindingKey::Direct)); 427249423Sdim return StoreRef(B.addBinding(R, BindingKey::Default, V) 428249423Sdim .asImmutableMap() 429249423Sdim .getRootWithoutRetain(), *this); 430218887Sdim } 431218887Sdim 432251662Sdim /// Attempt to extract the fields of \p LCV and bind them to the struct region 433251662Sdim /// \p R. 434243830Sdim /// 435251662Sdim /// This path is used when it seems advantageous to "force" loading the values 436251662Sdim /// within a LazyCompoundVal to bind memberwise to the struct region, rather 437251662Sdim /// than using a Default binding at the base of the entire region. This is a 438251662Sdim /// heuristic attempting to avoid building long chains of LazyCompoundVals. 439243830Sdim /// 440251662Sdim /// \returns The updated store bindings, or \c None if binding non-lazily 441251662Sdim /// would be too expensive. 442251662Sdim Optional<RegionBindingsRef> tryBindSmallStruct(RegionBindingsConstRef B, 443251662Sdim const TypedValueRegion *R, 444251662Sdim const RecordDecl *RD, 445251662Sdim nonloc::LazyCompoundVal LCV); 446218887Sdim 447218887Sdim /// BindStruct - Bind a compound value to a structure. 448249423Sdim RegionBindingsRef bindStruct(RegionBindingsConstRef B, 449249423Sdim const TypedValueRegion* R, SVal V); 450218887Sdim 451239462Sdim /// BindVector - Bind a compound value to a vector. 452249423Sdim RegionBindingsRef bindVector(RegionBindingsConstRef B, 453249423Sdim const TypedValueRegion* R, SVal V); 454239462Sdim 455249423Sdim RegionBindingsRef bindArray(RegionBindingsConstRef B, 456249423Sdim const TypedValueRegion* R, 457249423Sdim SVal V); 458218887Sdim 459239462Sdim /// Clears out all bindings in the given region and assigns a new value 460239462Sdim /// as a Default binding. 461249423Sdim RegionBindingsRef bindAggregate(RegionBindingsConstRef B, 462249423Sdim const TypedRegion *R, 463249423Sdim SVal DefaultVal); 464218887Sdim 465243830Sdim /// \brief Create a new store with the specified binding removed. 466243830Sdim /// \param ST the original store, that is the basis for the new store. 467243830Sdim /// \param L the location whose binding should be removed. 468249423Sdim virtual StoreRef killBinding(Store ST, Loc L); 469218887Sdim 470218887Sdim void incrementReferenceCount(Store store) { 471249423Sdim getRegionBindings(store).manualRetain(); 472218887Sdim } 473218887Sdim 474218887Sdim /// If the StoreManager supports it, decrement the reference count of 475218887Sdim /// the specified Store object. If the reference count hits 0, the memory 476218887Sdim /// associated with the object is recycled. 477218887Sdim void decrementReferenceCount(Store store) { 478249423Sdim getRegionBindings(store).manualRelease(); 479218887Sdim } 480226633Sdim 481226633Sdim bool includedInBindings(Store store, const MemRegion *region) const; 482218887Sdim 483234353Sdim /// \brief Return the value bound to specified location in a given state. 484234353Sdim /// 485218887Sdim /// The high level logic for this method is this: 486234353Sdim /// getBinding (L) 487218887Sdim /// if L has binding 488218887Sdim /// return L's binding 489218887Sdim /// else if L is in killset 490218887Sdim /// return unknown 491218887Sdim /// else 492218887Sdim /// if L is on stack or heap 493218887Sdim /// return undefined 494218887Sdim /// else 495218887Sdim /// return symbolic 496249423Sdim virtual SVal getBinding(Store S, Loc L, QualType T) { 497249423Sdim return getBinding(getRegionBindings(S), L, T); 498249423Sdim } 499218887Sdim 500249423Sdim SVal getBinding(RegionBindingsConstRef B, Loc L, QualType T = QualType()); 501218887Sdim 502249423Sdim SVal getBindingForElement(RegionBindingsConstRef B, const ElementRegion *R); 503218887Sdim 504249423Sdim SVal getBindingForField(RegionBindingsConstRef B, const FieldRegion *R); 505218887Sdim 506249423Sdim SVal getBindingForObjCIvar(RegionBindingsConstRef B, const ObjCIvarRegion *R); 507218887Sdim 508249423Sdim SVal getBindingForVar(RegionBindingsConstRef B, const VarRegion *R); 509249423Sdim 510234353Sdim SVal getBindingForLazySymbol(const TypedValueRegion *R); 511218887Sdim 512249423Sdim SVal getBindingForFieldOrElementCommon(RegionBindingsConstRef B, 513249423Sdim const TypedValueRegion *R, 514251662Sdim QualType Ty); 515221345Sdim 516249423Sdim SVal getLazyBinding(const SubRegion *LazyBindingRegion, 517249423Sdim RegionBindingsRef LazyBinding); 518218887Sdim 519234353Sdim /// Get bindings for the values in a struct and return a CompoundVal, used 520234353Sdim /// when doing struct copy: 521218887Sdim /// struct s x, y; 522218887Sdim /// x = y; 523218887Sdim /// y's value is retrieved by this method. 524249423Sdim SVal getBindingForStruct(RegionBindingsConstRef B, const TypedValueRegion *R); 525249423Sdim SVal getBindingForArray(RegionBindingsConstRef B, const TypedValueRegion *R); 526249423Sdim NonLoc createLazyBinding(RegionBindingsConstRef B, const TypedValueRegion *R); 527218887Sdim 528218887Sdim /// Used to lazily generate derived symbols for bindings that are defined 529249423Sdim /// implicitly by default bindings in a super region. 530249423Sdim /// 531249423Sdim /// Note that callers may need to specially handle LazyCompoundVals, which 532249423Sdim /// are returned as is in case the caller needs to treat them differently. 533249423Sdim Optional<SVal> getBindingForDerivedDefaultValue(RegionBindingsConstRef B, 534234353Sdim const MemRegion *superR, 535234353Sdim const TypedValueRegion *R, 536234353Sdim QualType Ty); 537218887Sdim 538249423Sdim /// Get the state and region whose binding this region \p R corresponds to. 539249423Sdim /// 540249423Sdim /// If there is no lazy binding for \p R, the returned value will have a null 541249423Sdim /// \c second. Note that a null pointer can represents a valid Store. 542249423Sdim std::pair<Store, const SubRegion *> 543249423Sdim findLazyBinding(RegionBindingsConstRef B, const SubRegion *R, 544249423Sdim const SubRegion *originalRegion); 545218887Sdim 546249423Sdim /// Returns the cached set of interesting SVals contained within a lazy 547249423Sdim /// binding. 548249423Sdim /// 549249423Sdim /// The precise value of "interesting" is determined for the purposes of 550249423Sdim /// RegionStore's internal analysis. It must always contain all regions and 551249423Sdim /// symbols, but may omit constants and other kinds of SVal. 552249423Sdim const SValListTy &getInterestingValues(nonloc::LazyCompoundVal LCV); 553249423Sdim 554218887Sdim //===------------------------------------------------------------------===// 555218887Sdim // State pruning. 556218887Sdim //===------------------------------------------------------------------===// 557218887Sdim 558218887Sdim /// removeDeadBindings - Scans the RegionStore of 'state' for dead values. 559218887Sdim /// It returns a new Store with these values removed. 560218887Sdim StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx, 561226633Sdim SymbolReaper& SymReaper); 562239462Sdim 563218887Sdim //===------------------------------------------------------------------===// 564218887Sdim // Region "extents". 565218887Sdim //===------------------------------------------------------------------===// 566218887Sdim 567218887Sdim // FIXME: This method will soon be eliminated; see the note in Store.h. 568234353Sdim DefinedOrUnknownSVal getSizeInElements(ProgramStateRef state, 569218887Sdim const MemRegion* R, QualType EleTy); 570218887Sdim 571218887Sdim //===------------------------------------------------------------------===// 572218887Sdim // Utility methods. 573218887Sdim //===------------------------------------------------------------------===// 574218887Sdim 575249423Sdim RegionBindingsRef getRegionBindings(Store store) const { 576249423Sdim return RegionBindingsRef(CBFactory, 577249423Sdim static_cast<const RegionBindings::TreeTy*>(store), 578249423Sdim RBFactory.getTreeFactory()); 579218887Sdim } 580218887Sdim 581226633Sdim void print(Store store, raw_ostream &Out, const char* nl, 582218887Sdim const char *sep); 583218887Sdim 584218887Sdim void iterBindings(Store store, BindingsHandler& f) { 585249423Sdim RegionBindingsRef B = getRegionBindings(store); 586249423Sdim for (RegionBindingsRef::iterator I = B.begin(), E = B.end(); I != E; ++I) { 587239462Sdim const ClusterBindings &Cluster = I.getData(); 588239462Sdim for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); 589239462Sdim CI != CE; ++CI) { 590239462Sdim const BindingKey &K = CI.getKey(); 591239462Sdim if (!K.isDirect()) 592239462Sdim continue; 593239462Sdim if (const SubRegion *R = dyn_cast<SubRegion>(K.getRegion())) { 594239462Sdim // FIXME: Possibly incorporate the offset? 595239462Sdim if (!f.HandleBinding(*this, store, R, CI.getData())) 596239462Sdim return; 597239462Sdim } 598218887Sdim } 599218887Sdim } 600218887Sdim } 601218887Sdim}; 602218887Sdim 603218887Sdim} // end anonymous namespace 604218887Sdim 605218887Sdim//===----------------------------------------------------------------------===// 606218887Sdim// RegionStore creation. 607218887Sdim//===----------------------------------------------------------------------===// 608218887Sdim 609226633SdimStoreManager *ento::CreateRegionStoreManager(ProgramStateManager& StMgr) { 610218887Sdim RegionStoreFeatures F = maximal_features_tag(); 611218887Sdim return new RegionStoreManager(StMgr, F); 612218887Sdim} 613218887Sdim 614234353SdimStoreManager * 615234353Sdimento::CreateFieldsOnlyRegionStoreManager(ProgramStateManager &StMgr) { 616218887Sdim RegionStoreFeatures F = minimal_features_tag(); 617218887Sdim F.enableFields(true); 618218887Sdim return new RegionStoreManager(StMgr, F); 619218887Sdim} 620218887Sdim 621218887Sdim 622218887Sdim//===----------------------------------------------------------------------===// 623218887Sdim// Region Cluster analysis. 624218887Sdim//===----------------------------------------------------------------------===// 625218887Sdim 626218887Sdimnamespace { 627251662Sdim/// Used to determine which global regions are automatically included in the 628251662Sdim/// initial worklist of a ClusterAnalysis. 629251662Sdimenum GlobalsFilterKind { 630251662Sdim /// Don't include any global regions. 631251662Sdim GFK_None, 632251662Sdim /// Only include system globals. 633251662Sdim GFK_SystemOnly, 634251662Sdim /// Include all global regions. 635251662Sdim GFK_All 636251662Sdim}; 637251662Sdim 638218887Sdimtemplate <typename DERIVED> 639218887Sdimclass ClusterAnalysis { 640218887Sdimprotected: 641239462Sdim typedef llvm::DenseMap<const MemRegion *, const ClusterBindings *> ClusterMap; 642249423Sdim typedef llvm::PointerIntPair<const MemRegion *, 1, bool> WorkListElement; 643249423Sdim typedef SmallVector<WorkListElement, 10> WorkList; 644218887Sdim 645239462Sdim llvm::SmallPtrSet<const ClusterBindings *, 16> Visited; 646239462Sdim 647218887Sdim WorkList WL; 648218887Sdim 649218887Sdim RegionStoreManager &RM; 650218887Sdim ASTContext &Ctx; 651218887Sdim SValBuilder &svalBuilder; 652218887Sdim 653249423Sdim RegionBindingsRef B; 654218887Sdim 655251662Sdimprivate: 656251662Sdim GlobalsFilterKind GlobalsFilter; 657251662Sdim 658251662Sdimprotected: 659239462Sdim const ClusterBindings *getCluster(const MemRegion *R) { 660239462Sdim return B.lookup(R); 661239462Sdim } 662239462Sdim 663251662Sdim /// Returns true if the memory space of the given region is one of the global 664251662Sdim /// regions specially included at the start of analysis. 665251662Sdim bool isInitiallyIncludedGlobalRegion(const MemRegion *R) { 666251662Sdim switch (GlobalsFilter) { 667251662Sdim case GFK_None: 668251662Sdim return false; 669251662Sdim case GFK_SystemOnly: 670251662Sdim return isa<GlobalSystemSpaceRegion>(R->getMemorySpace()); 671251662Sdim case GFK_All: 672251662Sdim return isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace()); 673251662Sdim } 674251662Sdim 675251662Sdim llvm_unreachable("unknown globals filter"); 676251662Sdim } 677251662Sdim 678218887Sdimpublic: 679226633Sdim ClusterAnalysis(RegionStoreManager &rm, ProgramStateManager &StateMgr, 680251662Sdim RegionBindingsRef b, GlobalsFilterKind GFK) 681218887Sdim : RM(rm), Ctx(StateMgr.getContext()), 682218887Sdim svalBuilder(StateMgr.getSValBuilder()), 683251662Sdim B(b), GlobalsFilter(GFK) {} 684218887Sdim 685249423Sdim RegionBindingsRef getRegionBindings() const { return B; } 686218887Sdim 687218887Sdim bool isVisited(const MemRegion *R) { 688239462Sdim return Visited.count(getCluster(R)); 689218887Sdim } 690218887Sdim 691218887Sdim void GenerateClusters() { 692239462Sdim // Scan the entire set of bindings and record the region clusters. 693249423Sdim for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end(); 694249423Sdim RI != RE; ++RI){ 695239462Sdim const MemRegion *Base = RI.getKey(); 696239462Sdim 697239462Sdim const ClusterBindings &Cluster = RI.getData(); 698239462Sdim assert(!Cluster.isEmpty() && "Empty clusters should be removed"); 699239462Sdim static_cast<DERIVED*>(this)->VisitAddedToCluster(Base, Cluster); 700239462Sdim 701251662Sdim // If this is an interesting global region, add it the work list up front. 702251662Sdim if (isInitiallyIncludedGlobalRegion(Base)) 703251662Sdim AddToWorkList(WorkListElement(Base), &Cluster); 704218887Sdim } 705218887Sdim } 706218887Sdim 707249423Sdim bool AddToWorkList(WorkListElement E, const ClusterBindings *C) { 708243830Sdim if (C && !Visited.insert(C)) 709243830Sdim return false; 710249423Sdim WL.push_back(E); 711218887Sdim return true; 712218887Sdim } 713218887Sdim 714249423Sdim bool AddToWorkList(const MemRegion *R, bool Flag = false) { 715249423Sdim const MemRegion *BaseR = R->getBaseRegion(); 716249423Sdim return AddToWorkList(WorkListElement(BaseR, Flag), getCluster(BaseR)); 717218887Sdim } 718218887Sdim 719218887Sdim void RunWorkList() { 720218887Sdim while (!WL.empty()) { 721249423Sdim WorkListElement E = WL.pop_back_val(); 722249423Sdim const MemRegion *BaseR = E.getPointer(); 723218887Sdim 724249423Sdim static_cast<DERIVED*>(this)->VisitCluster(BaseR, getCluster(BaseR), 725249423Sdim E.getInt()); 726218887Sdim } 727218887Sdim } 728218887Sdim 729239462Sdim void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C) {} 730249423Sdim void VisitCluster(const MemRegion *baseR, const ClusterBindings *C) {} 731249423Sdim 732249423Sdim void VisitCluster(const MemRegion *BaseR, const ClusterBindings *C, 733249423Sdim bool Flag) { 734249423Sdim static_cast<DERIVED*>(this)->VisitCluster(BaseR, C); 735249423Sdim } 736218887Sdim}; 737218887Sdim} 738218887Sdim 739218887Sdim//===----------------------------------------------------------------------===// 740218887Sdim// Binding invalidation. 741218887Sdim//===----------------------------------------------------------------------===// 742218887Sdim 743239462Sdimbool RegionStoreManager::scanReachableSymbols(Store S, const MemRegion *R, 744239462Sdim ScanReachableSymbols &Callbacks) { 745239462Sdim assert(R == R->getBaseRegion() && "Should only be called for base regions"); 746249423Sdim RegionBindingsRef B = getRegionBindings(S); 747239462Sdim const ClusterBindings *Cluster = B.lookup(R); 748218887Sdim 749239462Sdim if (!Cluster) 750239462Sdim return true; 751218887Sdim 752239462Sdim for (ClusterBindings::iterator RI = Cluster->begin(), RE = Cluster->end(); 753239462Sdim RI != RE; ++RI) { 754239462Sdim if (!Callbacks.scan(RI.getData())) 755239462Sdim return false; 756239462Sdim } 757239462Sdim 758239462Sdim return true; 759218887Sdim} 760218887Sdim 761243830Sdimstatic inline bool isUnionField(const FieldRegion *FR) { 762243830Sdim return FR->getDecl()->getParent()->isUnion(); 763243830Sdim} 764243830Sdim 765243830Sdimtypedef SmallVector<const FieldDecl *, 8> FieldVector; 766243830Sdim 767243830Sdimvoid getSymbolicOffsetFields(BindingKey K, FieldVector &Fields) { 768243830Sdim assert(K.hasSymbolicOffset() && "Not implemented for concrete offset keys"); 769243830Sdim 770243830Sdim const MemRegion *Base = K.getConcreteOffsetRegion(); 771243830Sdim const MemRegion *R = K.getRegion(); 772243830Sdim 773243830Sdim while (R != Base) { 774243830Sdim if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) 775243830Sdim if (!isUnionField(FR)) 776243830Sdim Fields.push_back(FR->getDecl()); 777243830Sdim 778243830Sdim R = cast<SubRegion>(R)->getSuperRegion(); 779243830Sdim } 780243830Sdim} 781243830Sdim 782243830Sdimstatic bool isCompatibleWithFields(BindingKey K, const FieldVector &Fields) { 783243830Sdim assert(K.hasSymbolicOffset() && "Not implemented for concrete offset keys"); 784243830Sdim 785243830Sdim if (Fields.empty()) 786243830Sdim return true; 787243830Sdim 788243830Sdim FieldVector FieldsInBindingKey; 789243830Sdim getSymbolicOffsetFields(K, FieldsInBindingKey); 790243830Sdim 791243830Sdim ptrdiff_t Delta = FieldsInBindingKey.size() - Fields.size(); 792243830Sdim if (Delta >= 0) 793243830Sdim return std::equal(FieldsInBindingKey.begin() + Delta, 794243830Sdim FieldsInBindingKey.end(), 795243830Sdim Fields.begin()); 796243830Sdim else 797243830Sdim return std::equal(FieldsInBindingKey.begin(), FieldsInBindingKey.end(), 798243830Sdim Fields.begin() - Delta); 799243830Sdim} 800243830Sdim 801249423Sdim/// Collects all bindings in \p Cluster that may refer to bindings within 802249423Sdim/// \p Top. 803249423Sdim/// 804249423Sdim/// Each binding is a pair whose \c first is the key (a BindingKey) and whose 805249423Sdim/// \c second is the value (an SVal). 806249423Sdim/// 807249423Sdim/// The \p IncludeAllDefaultBindings parameter specifies whether to include 808249423Sdim/// default bindings that may extend beyond \p Top itself, e.g. if \p Top is 809249423Sdim/// an aggregate within a larger aggregate with a default binding. 810249423Sdimstatic void 811249423SdimcollectSubRegionBindings(SmallVectorImpl<BindingPair> &Bindings, 812249423Sdim SValBuilder &SVB, const ClusterBindings &Cluster, 813249423Sdim const SubRegion *Top, BindingKey TopKey, 814249423Sdim bool IncludeAllDefaultBindings) { 815243830Sdim FieldVector FieldsInSymbolicSubregions; 816249423Sdim if (TopKey.hasSymbolicOffset()) { 817249423Sdim getSymbolicOffsetFields(TopKey, FieldsInSymbolicSubregions); 818249423Sdim Top = cast<SubRegion>(TopKey.getConcreteOffsetRegion()); 819249423Sdim TopKey = BindingKey::Make(Top, BindingKey::Default); 820239462Sdim } 821239462Sdim 822249423Sdim // Find the length (in bits) of the region being invalidated. 823239462Sdim uint64_t Length = UINT64_MAX; 824249423Sdim SVal Extent = Top->getExtent(SVB); 825249423Sdim if (Optional<nonloc::ConcreteInt> ExtentCI = 826249423Sdim Extent.getAs<nonloc::ConcreteInt>()) { 827239462Sdim const llvm::APSInt &ExtentInt = ExtentCI->getValue(); 828239462Sdim assert(ExtentInt.isNonNegative() || ExtentInt.isUnsigned()); 829239462Sdim // Extents are in bytes but region offsets are in bits. Be careful! 830249423Sdim Length = ExtentInt.getLimitedValue() * SVB.getContext().getCharWidth(); 831249423Sdim } else if (const FieldRegion *FR = dyn_cast<FieldRegion>(Top)) { 832249423Sdim if (FR->getDecl()->isBitField()) 833249423Sdim Length = FR->getDecl()->getBitWidthValue(SVB.getContext()); 834239462Sdim } 835239462Sdim 836249423Sdim for (ClusterBindings::iterator I = Cluster.begin(), E = Cluster.end(); 837239462Sdim I != E; ++I) { 838239462Sdim BindingKey NextKey = I.getKey(); 839249423Sdim if (NextKey.getRegion() == TopKey.getRegion()) { 840243830Sdim // FIXME: This doesn't catch the case where we're really invalidating a 841243830Sdim // region with a symbolic offset. Example: 842243830Sdim // R: points[i].y 843243830Sdim // Next: points[0].x 844243830Sdim 845249423Sdim if (NextKey.getOffset() > TopKey.getOffset() && 846249423Sdim NextKey.getOffset() - TopKey.getOffset() < Length) { 847239462Sdim // Case 1: The next binding is inside the region we're invalidating. 848249423Sdim // Include it. 849249423Sdim Bindings.push_back(*I); 850243830Sdim 851249423Sdim } else if (NextKey.getOffset() == TopKey.getOffset()) { 852239462Sdim // Case 2: The next binding is at the same offset as the region we're 853239462Sdim // invalidating. In this case, we need to leave default bindings alone, 854239462Sdim // since they may be providing a default value for a regions beyond what 855239462Sdim // we're invalidating. 856239462Sdim // FIXME: This is probably incorrect; consider invalidating an outer 857239462Sdim // struct whose first field is bound to a LazyCompoundVal. 858249423Sdim if (IncludeAllDefaultBindings || NextKey.isDirect()) 859249423Sdim Bindings.push_back(*I); 860239462Sdim } 861249423Sdim 862239462Sdim } else if (NextKey.hasSymbolicOffset()) { 863239462Sdim const MemRegion *Base = NextKey.getConcreteOffsetRegion(); 864249423Sdim if (Top->isSubRegionOf(Base)) { 865239462Sdim // Case 3: The next key is symbolic and we just changed something within 866239462Sdim // its concrete region. We don't know if the binding is still valid, so 867249423Sdim // we'll be conservative and include it. 868249423Sdim if (IncludeAllDefaultBindings || NextKey.isDirect()) 869243830Sdim if (isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions)) 870249423Sdim Bindings.push_back(*I); 871239462Sdim } else if (const SubRegion *BaseSR = dyn_cast<SubRegion>(Base)) { 872239462Sdim // Case 4: The next key is symbolic, but we changed a known 873249423Sdim // super-region. In this case the binding is certainly included. 874249423Sdim if (Top == Base || BaseSR->isSubRegionOf(Top)) 875243830Sdim if (isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions)) 876249423Sdim Bindings.push_back(*I); 877239462Sdim } 878239462Sdim } 879239462Sdim } 880249423Sdim} 881239462Sdim 882249423Sdimstatic void 883249423SdimcollectSubRegionBindings(SmallVectorImpl<BindingPair> &Bindings, 884249423Sdim SValBuilder &SVB, const ClusterBindings &Cluster, 885249423Sdim const SubRegion *Top, bool IncludeAllDefaultBindings) { 886249423Sdim collectSubRegionBindings(Bindings, SVB, Cluster, Top, 887249423Sdim BindingKey::Make(Top, BindingKey::Default), 888249423Sdim IncludeAllDefaultBindings); 889249423Sdim} 890249423Sdim 891249423SdimRegionBindingsRef 892249423SdimRegionStoreManager::removeSubRegionBindings(RegionBindingsConstRef B, 893249423Sdim const SubRegion *Top) { 894249423Sdim BindingKey TopKey = BindingKey::Make(Top, BindingKey::Default); 895249423Sdim const MemRegion *ClusterHead = TopKey.getBaseRegion(); 896249423Sdim 897249423Sdim if (Top == ClusterHead) { 898249423Sdim // We can remove an entire cluster's bindings all in one go. 899249423Sdim return B.remove(Top); 900249423Sdim } 901249423Sdim 902249423Sdim const ClusterBindings *Cluster = B.lookup(ClusterHead); 903249423Sdim if (!Cluster) { 904249423Sdim // If we're invalidating a region with a symbolic offset, we need to make 905249423Sdim // sure we don't treat the base region as uninitialized anymore. 906249423Sdim if (TopKey.hasSymbolicOffset()) { 907249423Sdim const SubRegion *Concrete = TopKey.getConcreteOffsetRegion(); 908249423Sdim return B.addBinding(Concrete, BindingKey::Default, UnknownVal()); 909249423Sdim } 910249423Sdim return B; 911249423Sdim } 912249423Sdim 913249423Sdim SmallVector<BindingPair, 32> Bindings; 914249423Sdim collectSubRegionBindings(Bindings, svalBuilder, *Cluster, Top, TopKey, 915249423Sdim /*IncludeAllDefaultBindings=*/false); 916249423Sdim 917249423Sdim ClusterBindingsRef Result(*Cluster, CBFactory); 918249423Sdim for (SmallVectorImpl<BindingPair>::const_iterator I = Bindings.begin(), 919249423Sdim E = Bindings.end(); 920249423Sdim I != E; ++I) 921249423Sdim Result = Result.remove(I->first); 922249423Sdim 923243830Sdim // If we're invalidating a region with a symbolic offset, we need to make sure 924243830Sdim // we don't treat the base region as uninitialized anymore. 925249423Sdim // FIXME: This isn't very precise; see the example in 926249423Sdim // collectSubRegionBindings. 927249423Sdim if (TopKey.hasSymbolicOffset()) { 928249423Sdim const SubRegion *Concrete = TopKey.getConcreteOffsetRegion(); 929249423Sdim Result = Result.add(BindingKey::Make(Concrete, BindingKey::Default), 930249423Sdim UnknownVal()); 931249423Sdim } 932243830Sdim 933239462Sdim if (Result.isEmpty()) 934249423Sdim return B.remove(ClusterHead); 935249423Sdim return B.add(ClusterHead, Result.asImmutableMap()); 936239462Sdim} 937239462Sdim 938218887Sdimnamespace { 939218887Sdimclass invalidateRegionsWorker : public ClusterAnalysis<invalidateRegionsWorker> 940218887Sdim{ 941218887Sdim const Expr *Ex; 942218887Sdim unsigned Count; 943234353Sdim const LocationContext *LCtx; 944249423Sdim InvalidatedSymbols &IS; 945249423Sdim InvalidatedSymbols &ConstIS; 946218887Sdim StoreManager::InvalidatedRegions *Regions; 947218887Sdimpublic: 948218887Sdim invalidateRegionsWorker(RegionStoreManager &rm, 949226633Sdim ProgramStateManager &stateMgr, 950249423Sdim RegionBindingsRef b, 951218887Sdim const Expr *ex, unsigned count, 952234353Sdim const LocationContext *lctx, 953249423Sdim InvalidatedSymbols &is, 954249423Sdim InvalidatedSymbols &inConstIS, 955218887Sdim StoreManager::InvalidatedRegions *r, 956251662Sdim GlobalsFilterKind GFK) 957251662Sdim : ClusterAnalysis<invalidateRegionsWorker>(rm, stateMgr, b, GFK), 958249423Sdim Ex(ex), Count(count), LCtx(lctx), IS(is), ConstIS(inConstIS), Regions(r){} 959218887Sdim 960249423Sdim /// \param IsConst Specifies if the region we are invalidating is constant. 961249423Sdim /// If it is, we invalidate all subregions, but not the base region itself. 962249423Sdim void VisitCluster(const MemRegion *baseR, const ClusterBindings *C, 963249423Sdim bool IsConst); 964218887Sdim void VisitBinding(SVal V); 965218887Sdim}; 966218887Sdim} 967218887Sdim 968218887Sdimvoid invalidateRegionsWorker::VisitBinding(SVal V) { 969218887Sdim // A symbol? Mark it touched by the invalidation. 970223017Sdim if (SymbolRef Sym = V.getAsSymbol()) 971223017Sdim IS.insert(Sym); 972218887Sdim 973218887Sdim if (const MemRegion *R = V.getAsRegion()) { 974218887Sdim AddToWorkList(R); 975218887Sdim return; 976218887Sdim } 977218887Sdim 978218887Sdim // Is it a LazyCompoundVal? All references get invalidated as well. 979249423Sdim if (Optional<nonloc::LazyCompoundVal> LCS = 980249423Sdim V.getAs<nonloc::LazyCompoundVal>()) { 981218887Sdim 982249423Sdim const RegionStoreManager::SValListTy &Vals = RM.getInterestingValues(*LCS); 983218887Sdim 984249423Sdim for (RegionStoreManager::SValListTy::const_iterator I = Vals.begin(), 985249423Sdim E = Vals.end(); 986249423Sdim I != E; ++I) 987249423Sdim VisitBinding(*I); 988218887Sdim 989218887Sdim return; 990218887Sdim } 991218887Sdim} 992218887Sdim 993249423Sdimvoid invalidateRegionsWorker::VisitCluster(const MemRegion *baseR, 994249423Sdim const ClusterBindings *C, 995249423Sdim bool IsConst) { 996249423Sdim if (C) { 997249423Sdim for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I) 998249423Sdim VisitBinding(I.getData()); 999218887Sdim 1000251662Sdim // Invalidate the contents of a non-const base region. 1001249423Sdim if (!IsConst) 1002249423Sdim B = B.remove(baseR); 1003249423Sdim } 1004218887Sdim 1005218887Sdim // BlockDataRegion? If so, invalidate captured variables that are passed 1006218887Sdim // by reference. 1007218887Sdim if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(baseR)) { 1008218887Sdim for (BlockDataRegion::referenced_vars_iterator 1009218887Sdim BI = BR->referenced_vars_begin(), BE = BR->referenced_vars_end() ; 1010218887Sdim BI != BE; ++BI) { 1011249423Sdim const VarRegion *VR = BI.getCapturedRegion(); 1012218887Sdim const VarDecl *VD = VR->getDecl(); 1013239462Sdim if (VD->getAttr<BlocksAttr>() || !VD->hasLocalStorage()) { 1014218887Sdim AddToWorkList(VR); 1015239462Sdim } 1016239462Sdim else if (Loc::isLocType(VR->getValueType())) { 1017239462Sdim // Map the current bindings to a Store to retrieve the value 1018239462Sdim // of the binding. If that binding itself is a region, we should 1019239462Sdim // invalidate that region. This is because a block may capture 1020239462Sdim // a pointer value, but the thing pointed by that pointer may 1021239462Sdim // get invalidated. 1022249423Sdim SVal V = RM.getBinding(B, loc::MemRegionVal(VR)); 1023249423Sdim if (Optional<Loc> L = V.getAs<Loc>()) { 1024239462Sdim if (const MemRegion *LR = L->getAsRegion()) 1025239462Sdim AddToWorkList(LR); 1026239462Sdim } 1027239462Sdim } 1028218887Sdim } 1029218887Sdim return; 1030218887Sdim } 1031218887Sdim 1032249423Sdim // Symbolic region? 1033251662Sdim if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) { 1034251662Sdim SymbolRef RegionSym = SR->getSymbol(); 1035249423Sdim 1036249423Sdim // Mark that symbol touched by the invalidation. 1037251662Sdim if (IsConst) 1038251662Sdim ConstIS.insert(RegionSym); 1039251662Sdim else 1040251662Sdim IS.insert(RegionSym); 1041249423Sdim } 1042249423Sdim 1043251662Sdim // Nothing else should be done for a const region. 1044251662Sdim if (IsConst) 1045251662Sdim return; 1046251662Sdim 1047218887Sdim // Otherwise, we have a normal data region. Record that we touched the region. 1048218887Sdim if (Regions) 1049218887Sdim Regions->push_back(baseR); 1050218887Sdim 1051218887Sdim if (isa<AllocaRegion>(baseR) || isa<SymbolicRegion>(baseR)) { 1052218887Sdim // Invalidate the region by setting its default value to 1053218887Sdim // conjured symbol. The type of the symbol is irrelavant. 1054218887Sdim DefinedOrUnknownSVal V = 1055243830Sdim svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, Ctx.IntTy, Count); 1056249423Sdim B = B.addBinding(baseR, BindingKey::Default, V); 1057218887Sdim return; 1058218887Sdim } 1059218887Sdim 1060218887Sdim if (!baseR->isBoundable()) 1061218887Sdim return; 1062218887Sdim 1063226633Sdim const TypedValueRegion *TR = cast<TypedValueRegion>(baseR); 1064218887Sdim QualType T = TR->getValueType(); 1065218887Sdim 1066251662Sdim if (isInitiallyIncludedGlobalRegion(baseR)) { 1067251662Sdim // If the region is a global and we are invalidating all globals, 1068251662Sdim // erasing the entry is good enough. This causes all globals to be lazily 1069251662Sdim // symbolicated from the same base symbol. 1070251662Sdim return; 1071251662Sdim } 1072251662Sdim 1073221345Sdim if (T->isStructureOrClassType()) { 1074218887Sdim // Invalidate the region by setting its default value to 1075218887Sdim // conjured symbol. The type of the symbol is irrelavant. 1076243830Sdim DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, 1077243830Sdim Ctx.IntTy, Count); 1078249423Sdim B = B.addBinding(baseR, BindingKey::Default, V); 1079218887Sdim return; 1080218887Sdim } 1081218887Sdim 1082218887Sdim if (const ArrayType *AT = Ctx.getAsArrayType(T)) { 1083218887Sdim // Set the default value of the array to conjured symbol. 1084218887Sdim DefinedOrUnknownSVal V = 1085243830Sdim svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, 1086234353Sdim AT->getElementType(), Count); 1087249423Sdim B = B.addBinding(baseR, BindingKey::Default, V); 1088218887Sdim return; 1089218887Sdim } 1090218887Sdim 1091243830Sdim DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, 1092243830Sdim T,Count); 1093218887Sdim assert(SymbolManager::canSymbolicate(T) || V.isUnknown()); 1094249423Sdim B = B.addBinding(baseR, BindingKey::Direct, V); 1095218887Sdim} 1096218887Sdim 1097249423SdimRegionBindingsRef 1098249423SdimRegionStoreManager::invalidateGlobalRegion(MemRegion::Kind K, 1099249423Sdim const Expr *Ex, 1100249423Sdim unsigned Count, 1101249423Sdim const LocationContext *LCtx, 1102249423Sdim RegionBindingsRef B, 1103249423Sdim InvalidatedRegions *Invalidated) { 1104234353Sdim // Bind the globals memory space to a new symbol that we will use to derive 1105234353Sdim // the bindings for all globals. 1106234353Sdim const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion(K); 1107243830Sdim SVal V = svalBuilder.conjureSymbolVal(/* SymbolTag = */ (const void*) GS, Ex, LCtx, 1108243830Sdim /* type does not matter */ Ctx.IntTy, 1109243830Sdim Count); 1110234353Sdim 1111249423Sdim B = B.removeBinding(GS) 1112249423Sdim .addBinding(BindingKey::Make(GS, BindingKey::Default), V); 1113234353Sdim 1114234353Sdim // Even if there are no bindings in the global scope, we still need to 1115234353Sdim // record that we touched it. 1116234353Sdim if (Invalidated) 1117234353Sdim Invalidated->push_back(GS); 1118234353Sdim 1119234353Sdim return B; 1120234353Sdim} 1121234353Sdim 1122249423Sdimvoid RegionStoreManager::populateWorkList(invalidateRegionsWorker &W, 1123249423Sdim ArrayRef<SVal> Values, 1124249423Sdim bool IsArrayOfConstRegions, 1125249423Sdim InvalidatedRegions *TopLevelRegions) { 1126249423Sdim for (ArrayRef<SVal>::iterator I = Values.begin(), 1127249423Sdim E = Values.end(); I != E; ++I) { 1128249423Sdim SVal V = *I; 1129249423Sdim if (Optional<nonloc::LazyCompoundVal> LCS = 1130249423Sdim V.getAs<nonloc::LazyCompoundVal>()) { 1131218887Sdim 1132249423Sdim const SValListTy &Vals = getInterestingValues(*LCS); 1133249423Sdim 1134249423Sdim for (SValListTy::const_iterator I = Vals.begin(), 1135249423Sdim E = Vals.end(); I != E; ++I) { 1136249423Sdim // Note: the last argument is false here because these are 1137249423Sdim // non-top-level regions. 1138249423Sdim if (const MemRegion *R = (*I).getAsRegion()) 1139249423Sdim W.AddToWorkList(R, /*IsConst=*/ false); 1140249423Sdim } 1141249423Sdim continue; 1142249423Sdim } 1143249423Sdim 1144249423Sdim if (const MemRegion *R = V.getAsRegion()) { 1145249423Sdim if (TopLevelRegions) 1146249423Sdim TopLevelRegions->push_back(R); 1147249423Sdim W.AddToWorkList(R, /*IsConst=*/ IsArrayOfConstRegions); 1148249423Sdim continue; 1149249423Sdim } 1150249423Sdim } 1151249423Sdim} 1152249423Sdim 1153249423SdimStoreRef 1154249423SdimRegionStoreManager::invalidateRegions(Store store, 1155249423Sdim ArrayRef<SVal> Values, 1156249423Sdim ArrayRef<SVal> ConstValues, 1157249423Sdim const Expr *Ex, unsigned Count, 1158249423Sdim const LocationContext *LCtx, 1159249423Sdim const CallEvent *Call, 1160249423Sdim InvalidatedSymbols &IS, 1161249423Sdim InvalidatedSymbols &ConstIS, 1162249423Sdim InvalidatedRegions *TopLevelRegions, 1163249423Sdim InvalidatedRegions *TopLevelConstRegions, 1164249423Sdim InvalidatedRegions *Invalidated) { 1165251662Sdim GlobalsFilterKind GlobalsFilter; 1166251662Sdim if (Call) { 1167251662Sdim if (Call->isInSystemHeader()) 1168251662Sdim GlobalsFilter = GFK_SystemOnly; 1169251662Sdim else 1170251662Sdim GlobalsFilter = GFK_All; 1171251662Sdim } else { 1172251662Sdim GlobalsFilter = GFK_None; 1173251662Sdim } 1174251662Sdim 1175251662Sdim RegionBindingsRef B = getRegionBindings(store); 1176249423Sdim invalidateRegionsWorker W(*this, StateMgr, B, Ex, Count, LCtx, IS, ConstIS, 1177251662Sdim Invalidated, GlobalsFilter); 1178249423Sdim 1179218887Sdim // Scan the bindings and generate the clusters. 1180218887Sdim W.GenerateClusters(); 1181218887Sdim 1182226633Sdim // Add the regions to the worklist. 1183249423Sdim populateWorkList(W, Values, /*IsArrayOfConstRegions*/ false, 1184249423Sdim TopLevelRegions); 1185249423Sdim populateWorkList(W, ConstValues, /*IsArrayOfConstRegions*/ true, 1186249423Sdim TopLevelConstRegions); 1187218887Sdim 1188218887Sdim W.RunWorkList(); 1189218887Sdim 1190218887Sdim // Return the new bindings. 1191249423Sdim B = W.getRegionBindings(); 1192218887Sdim 1193249423Sdim // For calls, determine which global regions should be invalidated and 1194249423Sdim // invalidate them. (Note that function-static and immutable globals are never 1195249423Sdim // invalidated by this.) 1196234353Sdim // TODO: This could possibly be more precise with modules. 1197251662Sdim switch (GlobalsFilter) { 1198251662Sdim case GFK_All: 1199251662Sdim B = invalidateGlobalRegion(MemRegion::GlobalInternalSpaceRegionKind, 1200251662Sdim Ex, Count, LCtx, B, Invalidated); 1201251662Sdim // FALLTHROUGH 1202251662Sdim case GFK_SystemOnly: 1203234353Sdim B = invalidateGlobalRegion(MemRegion::GlobalSystemSpaceRegionKind, 1204234353Sdim Ex, Count, LCtx, B, Invalidated); 1205251662Sdim // FALLTHROUGH 1206251662Sdim case GFK_None: 1207251662Sdim break; 1208218887Sdim } 1209218887Sdim 1210249423Sdim return StoreRef(B.asStore(), *this); 1211218887Sdim} 1212218887Sdim 1213218887Sdim//===----------------------------------------------------------------------===// 1214218887Sdim// Extents for regions. 1215218887Sdim//===----------------------------------------------------------------------===// 1216218887Sdim 1217234353SdimDefinedOrUnknownSVal 1218234353SdimRegionStoreManager::getSizeInElements(ProgramStateRef state, 1219234353Sdim const MemRegion *R, 1220234353Sdim QualType EleTy) { 1221218887Sdim SVal Size = cast<SubRegion>(R)->getExtent(svalBuilder); 1222218887Sdim const llvm::APSInt *SizeInt = svalBuilder.getKnownValue(state, Size); 1223218887Sdim if (!SizeInt) 1224218887Sdim return UnknownVal(); 1225218887Sdim 1226218887Sdim CharUnits RegionSize = CharUnits::fromQuantity(SizeInt->getSExtValue()); 1227218887Sdim 1228218887Sdim if (Ctx.getAsVariableArrayType(EleTy)) { 1229218887Sdim // FIXME: We need to track extra state to properly record the size 1230218887Sdim // of VLAs. Returning UnknownVal here, however, is a stop-gap so that 1231218887Sdim // we don't have a divide-by-zero below. 1232218887Sdim return UnknownVal(); 1233218887Sdim } 1234218887Sdim 1235218887Sdim CharUnits EleSize = Ctx.getTypeSizeInChars(EleTy); 1236218887Sdim 1237218887Sdim // If a variable is reinterpreted as a type that doesn't fit into a larger 1238218887Sdim // type evenly, round it down. 1239218887Sdim // This is a signed value, since it's used in arithmetic with signed indices. 1240218887Sdim return svalBuilder.makeIntVal(RegionSize / EleSize, false); 1241218887Sdim} 1242218887Sdim 1243218887Sdim//===----------------------------------------------------------------------===// 1244218887Sdim// Location and region casting. 1245218887Sdim//===----------------------------------------------------------------------===// 1246218887Sdim 1247218887Sdim/// ArrayToPointer - Emulates the "decay" of an array to a pointer 1248218887Sdim/// type. 'Array' represents the lvalue of the array being decayed 1249218887Sdim/// to a pointer, and the returned SVal represents the decayed 1250218887Sdim/// version of that lvalue (i.e., a pointer to the first element of 1251218887Sdim/// the array). This is called by ExprEngine when evaluating casts 1252218887Sdim/// from arrays to pointers. 1253218887SdimSVal RegionStoreManager::ArrayToPointer(Loc Array) { 1254249423Sdim if (!Array.getAs<loc::MemRegionVal>()) 1255218887Sdim return UnknownVal(); 1256218887Sdim 1257249423Sdim const MemRegion* R = Array.castAs<loc::MemRegionVal>().getRegion(); 1258226633Sdim const TypedValueRegion* ArrayR = dyn_cast<TypedValueRegion>(R); 1259218887Sdim 1260218887Sdim if (!ArrayR) 1261218887Sdim return UnknownVal(); 1262218887Sdim 1263218887Sdim // Strip off typedefs from the ArrayRegion's ValueType. 1264218887Sdim QualType T = ArrayR->getValueType().getDesugaredType(Ctx); 1265218887Sdim const ArrayType *AT = cast<ArrayType>(T); 1266218887Sdim T = AT->getElementType(); 1267218887Sdim 1268218887Sdim NonLoc ZeroIdx = svalBuilder.makeZeroArrayIndex(); 1269218887Sdim return loc::MemRegionVal(MRMgr.getElementRegion(T, ZeroIdx, ArrayR, Ctx)); 1270218887Sdim} 1271218887Sdim 1272218887Sdim//===----------------------------------------------------------------------===// 1273218887Sdim// Loading values from regions. 1274218887Sdim//===----------------------------------------------------------------------===// 1275218887Sdim 1276249423SdimSVal RegionStoreManager::getBinding(RegionBindingsConstRef B, Loc L, QualType T) { 1277249423Sdim assert(!L.getAs<UnknownVal>() && "location unknown"); 1278249423Sdim assert(!L.getAs<UndefinedVal>() && "location undefined"); 1279218887Sdim 1280218887Sdim // For access to concrete addresses, return UnknownVal. Checks 1281218887Sdim // for null dereferences (and similar errors) are done by checkers, not 1282218887Sdim // the Store. 1283218887Sdim // FIXME: We can consider lazily symbolicating such memory, but we really 1284218887Sdim // should defer this when we can reason easily about symbolicating arrays 1285218887Sdim // of bytes. 1286249423Sdim if (L.getAs<loc::ConcreteInt>()) { 1287218887Sdim return UnknownVal(); 1288218887Sdim } 1289249423Sdim if (!L.getAs<loc::MemRegionVal>()) { 1290218887Sdim return UnknownVal(); 1291218887Sdim } 1292218887Sdim 1293249423Sdim const MemRegion *MR = L.castAs<loc::MemRegionVal>().getRegion(); 1294218887Sdim 1295234353Sdim if (isa<AllocaRegion>(MR) || 1296234353Sdim isa<SymbolicRegion>(MR) || 1297234353Sdim isa<CodeTextRegion>(MR)) { 1298218887Sdim if (T.isNull()) { 1299234353Sdim if (const TypedRegion *TR = dyn_cast<TypedRegion>(MR)) 1300234353Sdim T = TR->getLocationType(); 1301234353Sdim else { 1302234353Sdim const SymbolicRegion *SR = cast<SymbolicRegion>(MR); 1303243830Sdim T = SR->getSymbol()->getType(); 1304234353Sdim } 1305218887Sdim } 1306218887Sdim MR = GetElementZeroRegion(MR, T); 1307218887Sdim } 1308218887Sdim 1309218887Sdim // FIXME: Perhaps this method should just take a 'const MemRegion*' argument 1310218887Sdim // instead of 'Loc', and have the other Loc cases handled at a higher level. 1311226633Sdim const TypedValueRegion *R = cast<TypedValueRegion>(MR); 1312218887Sdim QualType RTy = R->getValueType(); 1313218887Sdim 1314249423Sdim // FIXME: we do not yet model the parts of a complex type, so treat the 1315249423Sdim // whole thing as "unknown". 1316249423Sdim if (RTy->isAnyComplexType()) 1317249423Sdim return UnknownVal(); 1318249423Sdim 1319218887Sdim // FIXME: We should eventually handle funny addressing. e.g.: 1320218887Sdim // 1321218887Sdim // int x = ...; 1322218887Sdim // int *p = &x; 1323218887Sdim // char *q = (char*) p; 1324218887Sdim // char c = *q; // returns the first byte of 'x'. 1325218887Sdim // 1326218887Sdim // Such funny addressing will occur due to layering of regions. 1327218887Sdim if (RTy->isStructureOrClassType()) 1328249423Sdim return getBindingForStruct(B, R); 1329218887Sdim 1330218887Sdim // FIXME: Handle unions. 1331218887Sdim if (RTy->isUnionType()) 1332218887Sdim return UnknownVal(); 1333218887Sdim 1334239462Sdim if (RTy->isArrayType()) { 1335239462Sdim if (RTy->isConstantArrayType()) 1336249423Sdim return getBindingForArray(B, R); 1337239462Sdim else 1338239462Sdim return UnknownVal(); 1339239462Sdim } 1340218887Sdim 1341218887Sdim // FIXME: handle Vector types. 1342218887Sdim if (RTy->isVectorType()) 1343218887Sdim return UnknownVal(); 1344218887Sdim 1345218887Sdim if (const FieldRegion* FR = dyn_cast<FieldRegion>(R)) 1346249423Sdim return CastRetrievedVal(getBindingForField(B, FR), FR, T, false); 1347218887Sdim 1348218887Sdim if (const ElementRegion* ER = dyn_cast<ElementRegion>(R)) { 1349218887Sdim // FIXME: Here we actually perform an implicit conversion from the loaded 1350218887Sdim // value to the element type. Eventually we want to compose these values 1351218887Sdim // more intelligently. For example, an 'element' can encompass multiple 1352218887Sdim // bound regions (e.g., several bound bytes), or could be a subset of 1353218887Sdim // a larger value. 1354249423Sdim return CastRetrievedVal(getBindingForElement(B, ER), ER, T, false); 1355218887Sdim } 1356218887Sdim 1357218887Sdim if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) { 1358218887Sdim // FIXME: Here we actually perform an implicit conversion from the loaded 1359218887Sdim // value to the ivar type. What we should model is stores to ivars 1360218887Sdim // that blow past the extent of the ivar. If the address of the ivar is 1361218887Sdim // reinterpretted, it is possible we stored a different value that could 1362218887Sdim // fit within the ivar. Either we need to cast these when storing them 1363218887Sdim // or reinterpret them lazily (as we do here). 1364249423Sdim return CastRetrievedVal(getBindingForObjCIvar(B, IVR), IVR, T, false); 1365218887Sdim } 1366218887Sdim 1367218887Sdim if (const VarRegion *VR = dyn_cast<VarRegion>(R)) { 1368218887Sdim // FIXME: Here we actually perform an implicit conversion from the loaded 1369218887Sdim // value to the variable type. What we should model is stores to variables 1370218887Sdim // that blow past the extent of the variable. If the address of the 1371218887Sdim // variable is reinterpretted, it is possible we stored a different value 1372218887Sdim // that could fit within the variable. Either we need to cast these when 1373218887Sdim // storing them or reinterpret them lazily (as we do here). 1374249423Sdim return CastRetrievedVal(getBindingForVar(B, VR), VR, T, false); 1375218887Sdim } 1376218887Sdim 1377249423Sdim const SVal *V = B.lookup(R, BindingKey::Direct); 1378218887Sdim 1379218887Sdim // Check if the region has a binding. 1380218887Sdim if (V) 1381218887Sdim return *V; 1382218887Sdim 1383218887Sdim // The location does not have a bound value. This means that it has 1384218887Sdim // the value it had upon its creation and/or entry to the analyzed 1385218887Sdim // function/method. These are either symbolic values or 'undefined'. 1386218887Sdim if (R->hasStackNonParametersStorage()) { 1387218887Sdim // All stack variables are considered to have undefined values 1388218887Sdim // upon creation. All heap allocated blocks are considered to 1389218887Sdim // have undefined values as well unless they are explicitly bound 1390218887Sdim // to specific values. 1391218887Sdim return UndefinedVal(); 1392218887Sdim } 1393218887Sdim 1394218887Sdim // All other values are symbolic. 1395218887Sdim return svalBuilder.getRegionValueSymbolVal(R); 1396218887Sdim} 1397218887Sdim 1398249423Sdimstatic QualType getUnderlyingType(const SubRegion *R) { 1399249423Sdim QualType RegionTy; 1400249423Sdim if (const TypedValueRegion *TVR = dyn_cast<TypedValueRegion>(R)) 1401249423Sdim RegionTy = TVR->getValueType(); 1402249423Sdim 1403249423Sdim if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) 1404249423Sdim RegionTy = SR->getSymbol()->getType(); 1405249423Sdim 1406249423Sdim return RegionTy; 1407249423Sdim} 1408249423Sdim 1409249423Sdim/// Checks to see if store \p B has a lazy binding for region \p R. 1410249423Sdim/// 1411249423Sdim/// If \p AllowSubregionBindings is \c false, a lazy binding will be rejected 1412249423Sdim/// if there are additional bindings within \p R. 1413249423Sdim/// 1414249423Sdim/// Note that unlike RegionStoreManager::findLazyBinding, this will not search 1415249423Sdim/// for lazy bindings for super-regions of \p R. 1416249423Sdimstatic Optional<nonloc::LazyCompoundVal> 1417249423SdimgetExistingLazyBinding(SValBuilder &SVB, RegionBindingsConstRef B, 1418249423Sdim const SubRegion *R, bool AllowSubregionBindings) { 1419249423Sdim Optional<SVal> V = B.getDefaultBinding(R); 1420249423Sdim if (!V) 1421249423Sdim return None; 1422249423Sdim 1423249423Sdim Optional<nonloc::LazyCompoundVal> LCV = V->getAs<nonloc::LazyCompoundVal>(); 1424249423Sdim if (!LCV) 1425249423Sdim return None; 1426249423Sdim 1427249423Sdim // If the LCV is for a subregion, the types might not match, and we shouldn't 1428249423Sdim // reuse the binding. 1429249423Sdim QualType RegionTy = getUnderlyingType(R); 1430249423Sdim if (!RegionTy.isNull() && 1431249423Sdim !RegionTy->isVoidPointerType()) { 1432249423Sdim QualType SourceRegionTy = LCV->getRegion()->getValueType(); 1433249423Sdim if (!SVB.getContext().hasSameUnqualifiedType(RegionTy, SourceRegionTy)) 1434249423Sdim return None; 1435249423Sdim } 1436249423Sdim 1437249423Sdim if (!AllowSubregionBindings) { 1438249423Sdim // If there are any other bindings within this region, we shouldn't reuse 1439249423Sdim // the top-level binding. 1440249423Sdim SmallVector<BindingPair, 16> Bindings; 1441249423Sdim collectSubRegionBindings(Bindings, SVB, *B.lookup(R->getBaseRegion()), R, 1442249423Sdim /*IncludeAllDefaultBindings=*/true); 1443249423Sdim if (Bindings.size() > 1) 1444249423Sdim return None; 1445249423Sdim } 1446249423Sdim 1447249423Sdim return *LCV; 1448249423Sdim} 1449249423Sdim 1450249423Sdim 1451249423Sdimstd::pair<Store, const SubRegion *> 1452249423SdimRegionStoreManager::findLazyBinding(RegionBindingsConstRef B, 1453249423Sdim const SubRegion *R, 1454249423Sdim const SubRegion *originalRegion) { 1455221345Sdim if (originalRegion != R) { 1456249423Sdim if (Optional<nonloc::LazyCompoundVal> V = 1457249423Sdim getExistingLazyBinding(svalBuilder, B, R, true)) 1458249423Sdim return std::make_pair(V->getStore(), V->getRegion()); 1459221345Sdim } 1460249423Sdim 1461249423Sdim typedef std::pair<Store, const SubRegion *> StoreRegionPair; 1462249423Sdim StoreRegionPair Result = StoreRegionPair(); 1463249423Sdim 1464218887Sdim if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) { 1465249423Sdim Result = findLazyBinding(B, cast<SubRegion>(ER->getSuperRegion()), 1466249423Sdim originalRegion); 1467218887Sdim 1468249423Sdim if (Result.second) 1469249423Sdim Result.second = MRMgr.getElementRegionWithSuper(ER, Result.second); 1470218887Sdim 1471249423Sdim } else if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) { 1472249423Sdim Result = findLazyBinding(B, cast<SubRegion>(FR->getSuperRegion()), 1473249423Sdim originalRegion); 1474249423Sdim 1475249423Sdim if (Result.second) 1476249423Sdim Result.second = MRMgr.getFieldRegionWithSuper(FR, Result.second); 1477249423Sdim 1478249423Sdim } else if (const CXXBaseObjectRegion *BaseReg = 1479249423Sdim dyn_cast<CXXBaseObjectRegion>(R)) { 1480249423Sdim // C++ base object region is another kind of region that we should blast 1481249423Sdim // through to look for lazy compound value. It is like a field region. 1482249423Sdim Result = findLazyBinding(B, cast<SubRegion>(BaseReg->getSuperRegion()), 1483249423Sdim originalRegion); 1484218887Sdim 1485249423Sdim if (Result.second) 1486249423Sdim Result.second = MRMgr.getCXXBaseObjectRegionWithSuper(BaseReg, 1487249423Sdim Result.second); 1488218887Sdim } 1489221345Sdim 1490249423Sdim return Result; 1491218887Sdim} 1492218887Sdim 1493249423SdimSVal RegionStoreManager::getBindingForElement(RegionBindingsConstRef B, 1494239462Sdim const ElementRegion* R) { 1495239462Sdim // We do not currently model bindings of the CompoundLiteralregion. 1496239462Sdim if (isa<CompoundLiteralRegion>(R->getBaseRegion())) 1497239462Sdim return UnknownVal(); 1498239462Sdim 1499218887Sdim // Check if the region has a binding. 1500249423Sdim if (const Optional<SVal> &V = B.getDirectBinding(R)) 1501218887Sdim return *V; 1502218887Sdim 1503218887Sdim const MemRegion* superR = R->getSuperRegion(); 1504218887Sdim 1505218887Sdim // Check if the region is an element region of a string literal. 1506218887Sdim if (const StringRegion *StrR=dyn_cast<StringRegion>(superR)) { 1507218887Sdim // FIXME: Handle loads from strings where the literal is treated as 1508218887Sdim // an integer, e.g., *((unsigned int*)"hello") 1509218887Sdim QualType T = Ctx.getAsArrayType(StrR->getValueType())->getElementType(); 1510218887Sdim if (T != Ctx.getCanonicalType(R->getElementType())) 1511218887Sdim return UnknownVal(); 1512218887Sdim 1513218887Sdim const StringLiteral *Str = StrR->getStringLiteral(); 1514218887Sdim SVal Idx = R->getIndex(); 1515249423Sdim if (Optional<nonloc::ConcreteInt> CI = Idx.getAs<nonloc::ConcreteInt>()) { 1516218887Sdim int64_t i = CI->getValue().getSExtValue(); 1517226633Sdim // Abort on string underrun. This can be possible by arbitrary 1518234353Sdim // clients of getBindingForElement(). 1519226633Sdim if (i < 0) 1520226633Sdim return UndefinedVal(); 1521234353Sdim int64_t length = Str->getLength(); 1522234353Sdim // Technically, only i == length is guaranteed to be null. 1523218887Sdim // However, such overflows should be caught before reaching this point; 1524218887Sdim // the only time such an access would be made is if a string literal was 1525218887Sdim // used to initialize a larger array. 1526234353Sdim char c = (i >= length) ? '\0' : Str->getCodeUnit(i); 1527218887Sdim return svalBuilder.makeIntVal(c, T); 1528218887Sdim } 1529218887Sdim } 1530218887Sdim 1531218887Sdim // Check for loads from a code text region. For such loads, just give up. 1532218887Sdim if (isa<CodeTextRegion>(superR)) 1533218887Sdim return UnknownVal(); 1534218887Sdim 1535218887Sdim // Handle the case where we are indexing into a larger scalar object. 1536218887Sdim // For example, this handles: 1537218887Sdim // int x = ... 1538218887Sdim // char *y = &x; 1539218887Sdim // return *y; 1540218887Sdim // FIXME: This is a hack, and doesn't do anything really intelligent yet. 1541218887Sdim const RegionRawOffset &O = R->getAsArrayOffset(); 1542223017Sdim 1543223017Sdim // If we cannot reason about the offset, return an unknown value. 1544223017Sdim if (!O.getRegion()) 1545223017Sdim return UnknownVal(); 1546223017Sdim 1547226633Sdim if (const TypedValueRegion *baseR = 1548226633Sdim dyn_cast_or_null<TypedValueRegion>(O.getRegion())) { 1549218887Sdim QualType baseT = baseR->getValueType(); 1550218887Sdim if (baseT->isScalarType()) { 1551218887Sdim QualType elemT = R->getElementType(); 1552218887Sdim if (elemT->isScalarType()) { 1553218887Sdim if (Ctx.getTypeSizeInChars(baseT) >= Ctx.getTypeSizeInChars(elemT)) { 1554249423Sdim if (const Optional<SVal> &V = B.getDirectBinding(superR)) { 1555218887Sdim if (SymbolRef parentSym = V->getAsSymbol()) 1556218887Sdim return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); 1557218887Sdim 1558218887Sdim if (V->isUnknownOrUndef()) 1559218887Sdim return *V; 1560218887Sdim // Other cases: give up. We are indexing into a larger object 1561218887Sdim // that has some value, but we don't know how to handle that yet. 1562218887Sdim return UnknownVal(); 1563218887Sdim } 1564218887Sdim } 1565218887Sdim } 1566218887Sdim } 1567218887Sdim } 1568251662Sdim return getBindingForFieldOrElementCommon(B, R, R->getElementType()); 1569218887Sdim} 1570218887Sdim 1571249423SdimSVal RegionStoreManager::getBindingForField(RegionBindingsConstRef B, 1572249423Sdim const FieldRegion* R) { 1573218887Sdim 1574218887Sdim // Check if the region has a binding. 1575249423Sdim if (const Optional<SVal> &V = B.getDirectBinding(R)) 1576218887Sdim return *V; 1577218887Sdim 1578218887Sdim QualType Ty = R->getValueType(); 1579251662Sdim return getBindingForFieldOrElementCommon(B, R, Ty); 1580218887Sdim} 1581218887Sdim 1582218887SdimOptional<SVal> 1583249423SdimRegionStoreManager::getBindingForDerivedDefaultValue(RegionBindingsConstRef B, 1584234353Sdim const MemRegion *superR, 1585234353Sdim const TypedValueRegion *R, 1586234353Sdim QualType Ty) { 1587218887Sdim 1588249423Sdim if (const Optional<SVal> &D = B.getDefaultBinding(superR)) { 1589221345Sdim const SVal &val = D.getValue(); 1590221345Sdim if (SymbolRef parentSym = val.getAsSymbol()) 1591218887Sdim return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); 1592218887Sdim 1593221345Sdim if (val.isZeroConstant()) 1594218887Sdim return svalBuilder.makeZeroVal(Ty); 1595218887Sdim 1596221345Sdim if (val.isUnknownOrUndef()) 1597221345Sdim return val; 1598218887Sdim 1599249423Sdim // Lazy bindings are usually handled through getExistingLazyBinding(). 1600249423Sdim // We should unify these two code paths at some point. 1601249423Sdim if (val.getAs<nonloc::LazyCompoundVal>()) 1602249423Sdim return val; 1603221345Sdim 1604226633Sdim llvm_unreachable("Unknown default value"); 1605218887Sdim } 1606218887Sdim 1607249423Sdim return None; 1608218887Sdim} 1609218887Sdim 1610249423SdimSVal RegionStoreManager::getLazyBinding(const SubRegion *LazyBindingRegion, 1611249423Sdim RegionBindingsRef LazyBinding) { 1612249423Sdim SVal Result; 1613249423Sdim if (const ElementRegion *ER = dyn_cast<ElementRegion>(LazyBindingRegion)) 1614249423Sdim Result = getBindingForElement(LazyBinding, ER); 1615249423Sdim else 1616249423Sdim Result = getBindingForField(LazyBinding, 1617249423Sdim cast<FieldRegion>(LazyBindingRegion)); 1618249423Sdim 1619249423Sdim // FIXME: This is a hack to deal with RegionStore's inability to distinguish a 1620249423Sdim // default value for /part/ of an aggregate from a default value for the 1621249423Sdim // /entire/ aggregate. The most common case of this is when struct Outer 1622249423Sdim // has as its first member a struct Inner, which is copied in from a stack 1623249423Sdim // variable. In this case, even if the Outer's default value is symbolic, 0, 1624249423Sdim // or unknown, it gets overridden by the Inner's default value of undefined. 1625249423Sdim // 1626249423Sdim // This is a general problem -- if the Inner is zero-initialized, the Outer 1627249423Sdim // will now look zero-initialized. The proper way to solve this is with a 1628249423Sdim // new version of RegionStore that tracks the extent of a binding as well 1629249423Sdim // as the offset. 1630249423Sdim // 1631249423Sdim // This hack only takes care of the undefined case because that can very 1632249423Sdim // quickly result in a warning. 1633249423Sdim if (Result.isUndef()) 1634249423Sdim Result = UnknownVal(); 1635249423Sdim 1636249423Sdim return Result; 1637221345Sdim} 1638221345Sdim 1639249423SdimSVal 1640249423SdimRegionStoreManager::getBindingForFieldOrElementCommon(RegionBindingsConstRef B, 1641226633Sdim const TypedValueRegion *R, 1642251662Sdim QualType Ty) { 1643218887Sdim 1644234353Sdim // At this point we have already checked in either getBindingForElement or 1645234353Sdim // getBindingForField if 'R' has a direct binding. 1646239462Sdim 1647239462Sdim // Lazy binding? 1648239462Sdim Store lazyBindingStore = NULL; 1649249423Sdim const SubRegion *lazyBindingRegion = NULL; 1650249423Sdim llvm::tie(lazyBindingStore, lazyBindingRegion) = findLazyBinding(B, R, R); 1651239462Sdim if (lazyBindingRegion) 1652249423Sdim return getLazyBinding(lazyBindingRegion, 1653249423Sdim getRegionBindings(lazyBindingStore)); 1654239462Sdim 1655234353Sdim // Record whether or not we see a symbolic index. That can completely 1656234353Sdim // be out of scope of our lookup. 1657234353Sdim bool hasSymbolicIndex = false; 1658218887Sdim 1659249423Sdim // FIXME: This is a hack to deal with RegionStore's inability to distinguish a 1660249423Sdim // default value for /part/ of an aggregate from a default value for the 1661249423Sdim // /entire/ aggregate. The most common case of this is when struct Outer 1662249423Sdim // has as its first member a struct Inner, which is copied in from a stack 1663249423Sdim // variable. In this case, even if the Outer's default value is symbolic, 0, 1664249423Sdim // or unknown, it gets overridden by the Inner's default value of undefined. 1665249423Sdim // 1666249423Sdim // This is a general problem -- if the Inner is zero-initialized, the Outer 1667249423Sdim // will now look zero-initialized. The proper way to solve this is with a 1668249423Sdim // new version of RegionStore that tracks the extent of a binding as well 1669249423Sdim // as the offset. 1670249423Sdim // 1671249423Sdim // This hack only takes care of the undefined case because that can very 1672249423Sdim // quickly result in a warning. 1673249423Sdim bool hasPartialLazyBinding = false; 1674249423Sdim 1675251662Sdim const SubRegion *SR = dyn_cast<SubRegion>(R); 1676251662Sdim while (SR) { 1677251662Sdim const MemRegion *Base = SR->getSuperRegion(); 1678249423Sdim if (Optional<SVal> D = getBindingForDerivedDefaultValue(B, Base, R, Ty)) { 1679249423Sdim if (D->getAs<nonloc::LazyCompoundVal>()) { 1680249423Sdim hasPartialLazyBinding = true; 1681249423Sdim break; 1682249423Sdim } 1683249423Sdim 1684218887Sdim return *D; 1685249423Sdim } 1686218887Sdim 1687249423Sdim if (const ElementRegion *ER = dyn_cast<ElementRegion>(Base)) { 1688234353Sdim NonLoc index = ER->getIndex(); 1689234353Sdim if (!index.isConstant()) 1690234353Sdim hasSymbolicIndex = true; 1691234353Sdim } 1692234353Sdim 1693218887Sdim // If our super region is a field or element itself, walk up the region 1694218887Sdim // hierarchy to see if there is a default value installed in an ancestor. 1695251662Sdim SR = dyn_cast<SubRegion>(Base); 1696218887Sdim } 1697218887Sdim 1698218887Sdim if (R->hasStackNonParametersStorage()) { 1699234353Sdim if (isa<ElementRegion>(R)) { 1700218887Sdim // Currently we don't reason specially about Clang-style vectors. Check 1701218887Sdim // if superR is a vector and if so return Unknown. 1702226633Sdim if (const TypedValueRegion *typedSuperR = 1703251662Sdim dyn_cast<TypedValueRegion>(R->getSuperRegion())) { 1704218887Sdim if (typedSuperR->getValueType()->isVectorType()) 1705218887Sdim return UnknownVal(); 1706218887Sdim } 1707218887Sdim } 1708218887Sdim 1709234353Sdim // FIXME: We also need to take ElementRegions with symbolic indexes into 1710234353Sdim // account. This case handles both directly accessing an ElementRegion 1711234353Sdim // with a symbolic offset, but also fields within an element with 1712234353Sdim // a symbolic offset. 1713234353Sdim if (hasSymbolicIndex) 1714234353Sdim return UnknownVal(); 1715249423Sdim 1716249423Sdim if (!hasPartialLazyBinding) 1717249423Sdim return UndefinedVal(); 1718218887Sdim } 1719218887Sdim 1720218887Sdim // All other values are symbolic. 1721218887Sdim return svalBuilder.getRegionValueSymbolVal(R); 1722218887Sdim} 1723218887Sdim 1724249423SdimSVal RegionStoreManager::getBindingForObjCIvar(RegionBindingsConstRef B, 1725234353Sdim const ObjCIvarRegion* R) { 1726249423Sdim // Check if the region has a binding. 1727249423Sdim if (const Optional<SVal> &V = B.getDirectBinding(R)) 1728218887Sdim return *V; 1729218887Sdim 1730218887Sdim const MemRegion *superR = R->getSuperRegion(); 1731218887Sdim 1732218887Sdim // Check if the super region has a default binding. 1733249423Sdim if (const Optional<SVal> &V = B.getDefaultBinding(superR)) { 1734218887Sdim if (SymbolRef parentSym = V->getAsSymbol()) 1735218887Sdim return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); 1736218887Sdim 1737218887Sdim // Other cases: give up. 1738218887Sdim return UnknownVal(); 1739218887Sdim } 1740218887Sdim 1741234353Sdim return getBindingForLazySymbol(R); 1742218887Sdim} 1743218887Sdim 1744249423SdimSVal RegionStoreManager::getBindingForVar(RegionBindingsConstRef B, 1745249423Sdim const VarRegion *R) { 1746249423Sdim 1747218887Sdim // Check if the region has a binding. 1748249423Sdim if (const Optional<SVal> &V = B.getDirectBinding(R)) 1749218887Sdim return *V; 1750218887Sdim 1751218887Sdim // Lazily derive a value for the VarRegion. 1752218887Sdim const VarDecl *VD = R->getDecl(); 1753218887Sdim const MemSpaceRegion *MS = R->getMemorySpace(); 1754218887Sdim 1755249423Sdim // Arguments are always symbolic. 1756249423Sdim if (isa<StackArgumentsSpaceRegion>(MS)) 1757218887Sdim return svalBuilder.getRegionValueSymbolVal(R); 1758218887Sdim 1759249423Sdim // Is 'VD' declared constant? If so, retrieve the constant value. 1760251662Sdim if (VD->getType().isConstQualified()) 1761251662Sdim if (const Expr *Init = VD->getInit()) 1762251662Sdim if (Optional<SVal> V = svalBuilder.getConstantVal(Init)) 1763251662Sdim return *V; 1764249423Sdim 1765249423Sdim // This must come after the check for constants because closure-captured 1766249423Sdim // constant variables may appear in UnknownSpaceRegion. 1767249423Sdim if (isa<UnknownSpaceRegion>(MS)) 1768249423Sdim return svalBuilder.getRegionValueSymbolVal(R); 1769249423Sdim 1770218887Sdim if (isa<GlobalsSpaceRegion>(MS)) { 1771249423Sdim QualType T = VD->getType(); 1772218887Sdim 1773249423Sdim // Function-scoped static variables are default-initialized to 0; if they 1774249423Sdim // have an initializer, it would have been processed by now. 1775249423Sdim if (isa<StaticGlobalSpaceRegion>(MS)) 1776249423Sdim return svalBuilder.makeZeroVal(T); 1777218887Sdim 1778249423Sdim if (Optional<SVal> V = getBindingForDerivedDefaultValue(B, MS, R, T)) { 1779249423Sdim assert(!V->getAs<nonloc::LazyCompoundVal>()); 1780249423Sdim return V.getValue(); 1781218887Sdim } 1782218887Sdim 1783249423Sdim return svalBuilder.getRegionValueSymbolVal(R); 1784218887Sdim } 1785218887Sdim 1786218887Sdim return UndefinedVal(); 1787218887Sdim} 1788218887Sdim 1789234353SdimSVal RegionStoreManager::getBindingForLazySymbol(const TypedValueRegion *R) { 1790218887Sdim // All other values are symbolic. 1791218887Sdim return svalBuilder.getRegionValueSymbolVal(R); 1792218887Sdim} 1793218887Sdim 1794249423Sdimconst RegionStoreManager::SValListTy & 1795249423SdimRegionStoreManager::getInterestingValues(nonloc::LazyCompoundVal LCV) { 1796249423Sdim // First, check the cache. 1797249423Sdim LazyBindingsMapTy::iterator I = LazyBindingsMap.find(LCV.getCVData()); 1798249423Sdim if (I != LazyBindingsMap.end()) 1799249423Sdim return I->second; 1800249423Sdim 1801249423Sdim // If we don't have a list of values cached, start constructing it. 1802249423Sdim SValListTy List; 1803249423Sdim 1804249423Sdim const SubRegion *LazyR = LCV.getRegion(); 1805249423Sdim RegionBindingsRef B = getRegionBindings(LCV.getStore()); 1806249423Sdim 1807249423Sdim // If this region had /no/ bindings at the time, there are no interesting 1808249423Sdim // values to return. 1809249423Sdim const ClusterBindings *Cluster = B.lookup(LazyR->getBaseRegion()); 1810249423Sdim if (!Cluster) 1811249423Sdim return (LazyBindingsMap[LCV.getCVData()] = llvm_move(List)); 1812249423Sdim 1813249423Sdim SmallVector<BindingPair, 32> Bindings; 1814249423Sdim collectSubRegionBindings(Bindings, svalBuilder, *Cluster, LazyR, 1815249423Sdim /*IncludeAllDefaultBindings=*/true); 1816249423Sdim for (SmallVectorImpl<BindingPair>::const_iterator I = Bindings.begin(), 1817249423Sdim E = Bindings.end(); 1818249423Sdim I != E; ++I) { 1819249423Sdim SVal V = I->second; 1820249423Sdim if (V.isUnknownOrUndef() || V.isConstant()) 1821249423Sdim continue; 1822249423Sdim 1823249423Sdim if (Optional<nonloc::LazyCompoundVal> InnerLCV = 1824249423Sdim V.getAs<nonloc::LazyCompoundVal>()) { 1825249423Sdim const SValListTy &InnerList = getInterestingValues(*InnerLCV); 1826249423Sdim List.insert(List.end(), InnerList.begin(), InnerList.end()); 1827249423Sdim continue; 1828249423Sdim } 1829249423Sdim 1830249423Sdim List.push_back(V); 1831249423Sdim } 1832249423Sdim 1833249423Sdim return (LazyBindingsMap[LCV.getCVData()] = llvm_move(List)); 1834239462Sdim} 1835239462Sdim 1836249423SdimNonLoc RegionStoreManager::createLazyBinding(RegionBindingsConstRef B, 1837249423Sdim const TypedValueRegion *R) { 1838249423Sdim if (Optional<nonloc::LazyCompoundVal> V = 1839249423Sdim getExistingLazyBinding(svalBuilder, B, R, false)) 1840249423Sdim return *V; 1841249423Sdim 1842249423Sdim return svalBuilder.makeLazyCompoundVal(StoreRef(B.asStore(), *this), R); 1843249423Sdim} 1844249423Sdim 1845249423SdimSVal RegionStoreManager::getBindingForStruct(RegionBindingsConstRef B, 1846249423Sdim const TypedValueRegion *R) { 1847239462Sdim const RecordDecl *RD = R->getValueType()->castAs<RecordType>()->getDecl(); 1848239462Sdim if (RD->field_empty()) 1849239462Sdim return UnknownVal(); 1850239462Sdim 1851249423Sdim return createLazyBinding(B, R); 1852218887Sdim} 1853218887Sdim 1854249423SdimSVal RegionStoreManager::getBindingForArray(RegionBindingsConstRef B, 1855249423Sdim const TypedValueRegion *R) { 1856249423Sdim assert(Ctx.getAsConstantArrayType(R->getValueType()) && 1857249423Sdim "Only constant array types can have compound bindings."); 1858239462Sdim 1859249423Sdim return createLazyBinding(B, R); 1860218887Sdim} 1861218887Sdim 1862226633Sdimbool RegionStoreManager::includedInBindings(Store store, 1863226633Sdim const MemRegion *region) const { 1864249423Sdim RegionBindingsRef B = getRegionBindings(store); 1865226633Sdim region = region->getBaseRegion(); 1866239462Sdim 1867239462Sdim // Quick path: if the base is the head of a cluster, the region is live. 1868239462Sdim if (B.lookup(region)) 1869239462Sdim return true; 1870239462Sdim 1871239462Sdim // Slow path: if the region is the VALUE of any binding, it is live. 1872249423Sdim for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI) { 1873239462Sdim const ClusterBindings &Cluster = RI.getData(); 1874239462Sdim for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); 1875239462Sdim CI != CE; ++CI) { 1876239462Sdim const SVal &D = CI.getData(); 1877239462Sdim if (const MemRegion *R = D.getAsRegion()) 1878239462Sdim if (R->getBaseRegion() == region) 1879239462Sdim return true; 1880239462Sdim } 1881226633Sdim } 1882239462Sdim 1883226633Sdim return false; 1884226633Sdim} 1885226633Sdim 1886218887Sdim//===----------------------------------------------------------------------===// 1887218887Sdim// Binding values to regions. 1888218887Sdim//===----------------------------------------------------------------------===// 1889218887Sdim 1890243830SdimStoreRef RegionStoreManager::killBinding(Store ST, Loc L) { 1891249423Sdim if (Optional<loc::MemRegionVal> LV = L.getAs<loc::MemRegionVal>()) 1892249423Sdim if (const MemRegion* R = LV->getRegion()) 1893249423Sdim return StoreRef(getRegionBindings(ST).removeBinding(R) 1894249423Sdim .asImmutableMap() 1895249423Sdim .getRootWithoutRetain(), 1896218887Sdim *this); 1897218887Sdim 1898243830Sdim return StoreRef(ST, *this); 1899218887Sdim} 1900218887Sdim 1901249423SdimRegionBindingsRef 1902249423SdimRegionStoreManager::bind(RegionBindingsConstRef B, Loc L, SVal V) { 1903249423Sdim if (L.getAs<loc::ConcreteInt>()) 1904249423Sdim return B; 1905218887Sdim 1906218887Sdim // If we get here, the location should be a region. 1907249423Sdim const MemRegion *R = L.castAs<loc::MemRegionVal>().getRegion(); 1908218887Sdim 1909218887Sdim // Check if the region is a struct region. 1910239462Sdim if (const TypedValueRegion* TR = dyn_cast<TypedValueRegion>(R)) { 1911239462Sdim QualType Ty = TR->getValueType(); 1912243830Sdim if (Ty->isArrayType()) 1913249423Sdim return bindArray(B, TR, V); 1914239462Sdim if (Ty->isStructureOrClassType()) 1915249423Sdim return bindStruct(B, TR, V); 1916239462Sdim if (Ty->isVectorType()) 1917249423Sdim return bindVector(B, TR, V); 1918239462Sdim } 1919218887Sdim 1920239462Sdim if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) { 1921218887Sdim // Binding directly to a symbolic region should be treated as binding 1922218887Sdim // to element 0. 1923243830Sdim QualType T = SR->getSymbol()->getType(); 1924243830Sdim if (T->isAnyPointerType() || T->isReferenceType()) 1925243830Sdim T = T->getPointeeType(); 1926218887Sdim 1927218887Sdim R = GetElementZeroRegion(SR, T); 1928218887Sdim } 1929218887Sdim 1930239462Sdim // Clear out bindings that may overlap with this binding. 1931249423Sdim RegionBindingsRef NewB = removeSubRegionBindings(B, cast<SubRegion>(R)); 1932249423Sdim return NewB.addBinding(BindingKey::Make(R, BindingKey::Direct), V); 1933218887Sdim} 1934218887Sdim 1935249423SdimRegionBindingsRef 1936249423SdimRegionStoreManager::setImplicitDefaultValue(RegionBindingsConstRef B, 1937249423Sdim const MemRegion *R, 1938249423Sdim QualType T) { 1939218887Sdim SVal V; 1940218887Sdim 1941218887Sdim if (Loc::isLocType(T)) 1942218887Sdim V = svalBuilder.makeNull(); 1943251662Sdim else if (T->isIntegralOrEnumerationType()) 1944218887Sdim V = svalBuilder.makeZeroVal(T); 1945218887Sdim else if (T->isStructureOrClassType() || T->isArrayType()) { 1946218887Sdim // Set the default value to a zero constant when it is a structure 1947218887Sdim // or array. The type doesn't really matter. 1948218887Sdim V = svalBuilder.makeZeroVal(Ctx.IntTy); 1949218887Sdim } 1950218887Sdim else { 1951224145Sdim // We can't represent values of this type, but we still need to set a value 1952224145Sdim // to record that the region has been initialized. 1953224145Sdim // If this assertion ever fires, a new case should be added above -- we 1954224145Sdim // should know how to default-initialize any value we can symbolicate. 1955224145Sdim assert(!SymbolManager::canSymbolicate(T) && "This type is representable"); 1956224145Sdim V = UnknownVal(); 1957218887Sdim } 1958218887Sdim 1959249423Sdim return B.addBinding(R, BindingKey::Default, V); 1960218887Sdim} 1961218887Sdim 1962249423SdimRegionBindingsRef 1963249423SdimRegionStoreManager::bindArray(RegionBindingsConstRef B, 1964249423Sdim const TypedValueRegion* R, 1965249423Sdim SVal Init) { 1966218887Sdim 1967218887Sdim const ArrayType *AT =cast<ArrayType>(Ctx.getCanonicalType(R->getValueType())); 1968218887Sdim QualType ElementTy = AT->getElementType(); 1969218887Sdim Optional<uint64_t> Size; 1970218887Sdim 1971218887Sdim if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(AT)) 1972218887Sdim Size = CAT->getSize().getZExtValue(); 1973218887Sdim 1974218887Sdim // Check if the init expr is a string literal. 1975249423Sdim if (Optional<loc::MemRegionVal> MRV = Init.getAs<loc::MemRegionVal>()) { 1976218887Sdim const StringRegion *S = cast<StringRegion>(MRV->getRegion()); 1977218887Sdim 1978218887Sdim // Treat the string as a lazy compound value. 1979249423Sdim StoreRef store(B.asStore(), *this); 1980249423Sdim nonloc::LazyCompoundVal LCV = svalBuilder.makeLazyCompoundVal(store, S) 1981249423Sdim .castAs<nonloc::LazyCompoundVal>(); 1982249423Sdim return bindAggregate(B, R, LCV); 1983218887Sdim } 1984218887Sdim 1985218887Sdim // Handle lazy compound values. 1986249423Sdim if (Init.getAs<nonloc::LazyCompoundVal>()) 1987249423Sdim return bindAggregate(B, R, Init); 1988218887Sdim 1989218887Sdim // Remaining case: explicit compound values. 1990218887Sdim 1991218887Sdim if (Init.isUnknown()) 1992249423Sdim return setImplicitDefaultValue(B, R, ElementTy); 1993218887Sdim 1994249423Sdim const nonloc::CompoundVal& CV = Init.castAs<nonloc::CompoundVal>(); 1995218887Sdim nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); 1996218887Sdim uint64_t i = 0; 1997218887Sdim 1998249423Sdim RegionBindingsRef NewB(B); 1999249423Sdim 2000218887Sdim for (; Size.hasValue() ? i < Size.getValue() : true ; ++i, ++VI) { 2001218887Sdim // The init list might be shorter than the array length. 2002218887Sdim if (VI == VE) 2003218887Sdim break; 2004218887Sdim 2005218887Sdim const NonLoc &Idx = svalBuilder.makeArrayIndex(i); 2006218887Sdim const ElementRegion *ER = MRMgr.getElementRegion(ElementTy, Idx, R, Ctx); 2007218887Sdim 2008218887Sdim if (ElementTy->isStructureOrClassType()) 2009249423Sdim NewB = bindStruct(NewB, ER, *VI); 2010218887Sdim else if (ElementTy->isArrayType()) 2011249423Sdim NewB = bindArray(NewB, ER, *VI); 2012218887Sdim else 2013251662Sdim NewB = bind(NewB, loc::MemRegionVal(ER), *VI); 2014218887Sdim } 2015218887Sdim 2016218887Sdim // If the init list is shorter than the array length, set the 2017218887Sdim // array default value. 2018218887Sdim if (Size.hasValue() && i < Size.getValue()) 2019249423Sdim NewB = setImplicitDefaultValue(NewB, R, ElementTy); 2020218887Sdim 2021249423Sdim return NewB; 2022218887Sdim} 2023218887Sdim 2024249423SdimRegionBindingsRef RegionStoreManager::bindVector(RegionBindingsConstRef B, 2025249423Sdim const TypedValueRegion* R, 2026249423Sdim SVal V) { 2027239462Sdim QualType T = R->getValueType(); 2028239462Sdim assert(T->isVectorType()); 2029239462Sdim const VectorType *VT = T->getAs<VectorType>(); // Use getAs for typedefs. 2030239462Sdim 2031239462Sdim // Handle lazy compound values and symbolic values. 2032249423Sdim if (V.getAs<nonloc::LazyCompoundVal>() || V.getAs<nonloc::SymbolVal>()) 2033249423Sdim return bindAggregate(B, R, V); 2034239462Sdim 2035239462Sdim // We may get non-CompoundVal accidentally due to imprecise cast logic or 2036239462Sdim // that we are binding symbolic struct value. Kill the field values, and if 2037239462Sdim // the value is symbolic go and bind it as a "default" binding. 2038249423Sdim if (!V.getAs<nonloc::CompoundVal>()) { 2039249423Sdim return bindAggregate(B, R, UnknownVal()); 2040239462Sdim } 2041239462Sdim 2042239462Sdim QualType ElemType = VT->getElementType(); 2043249423Sdim nonloc::CompoundVal CV = V.castAs<nonloc::CompoundVal>(); 2044239462Sdim nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); 2045239462Sdim unsigned index = 0, numElements = VT->getNumElements(); 2046249423Sdim RegionBindingsRef NewB(B); 2047249423Sdim 2048239462Sdim for ( ; index != numElements ; ++index) { 2049239462Sdim if (VI == VE) 2050239462Sdim break; 2051239462Sdim 2052239462Sdim NonLoc Idx = svalBuilder.makeArrayIndex(index); 2053239462Sdim const ElementRegion *ER = MRMgr.getElementRegion(ElemType, Idx, R, Ctx); 2054251662Sdim 2055239462Sdim if (ElemType->isArrayType()) 2056249423Sdim NewB = bindArray(NewB, ER, *VI); 2057239462Sdim else if (ElemType->isStructureOrClassType()) 2058249423Sdim NewB = bindStruct(NewB, ER, *VI); 2059239462Sdim else 2060251662Sdim NewB = bind(NewB, loc::MemRegionVal(ER), *VI); 2061239462Sdim } 2062249423Sdim return NewB; 2063239462Sdim} 2064239462Sdim 2065251662SdimOptional<RegionBindingsRef> 2066251662SdimRegionStoreManager::tryBindSmallStruct(RegionBindingsConstRef B, 2067251662Sdim const TypedValueRegion *R, 2068251662Sdim const RecordDecl *RD, 2069251662Sdim nonloc::LazyCompoundVal LCV) { 2070251662Sdim FieldVector Fields; 2071251662Sdim 2072251662Sdim if (const CXXRecordDecl *Class = dyn_cast<CXXRecordDecl>(RD)) 2073251662Sdim if (Class->getNumBases() != 0 || Class->getNumVBases() != 0) 2074251662Sdim return None; 2075251662Sdim 2076251662Sdim for (RecordDecl::field_iterator I = RD->field_begin(), E = RD->field_end(); 2077251662Sdim I != E; ++I) { 2078251662Sdim const FieldDecl *FD = *I; 2079251662Sdim if (FD->isUnnamedBitfield()) 2080251662Sdim continue; 2081251662Sdim 2082251662Sdim // If there are too many fields, or if any of the fields are aggregates, 2083251662Sdim // just use the LCV as a default binding. 2084251662Sdim if (Fields.size() == SmallStructLimit) 2085251662Sdim return None; 2086251662Sdim 2087251662Sdim QualType Ty = FD->getType(); 2088251662Sdim if (!(Ty->isScalarType() || Ty->isReferenceType())) 2089251662Sdim return None; 2090251662Sdim 2091251662Sdim Fields.push_back(*I); 2092251662Sdim } 2093251662Sdim 2094251662Sdim RegionBindingsRef NewB = B; 2095251662Sdim 2096251662Sdim for (FieldVector::iterator I = Fields.begin(), E = Fields.end(); I != E; ++I){ 2097251662Sdim const FieldRegion *SourceFR = MRMgr.getFieldRegion(*I, LCV.getRegion()); 2098251662Sdim SVal V = getBindingForField(getRegionBindings(LCV.getStore()), SourceFR); 2099251662Sdim 2100251662Sdim const FieldRegion *DestFR = MRMgr.getFieldRegion(*I, R); 2101251662Sdim NewB = bind(NewB, loc::MemRegionVal(DestFR), V); 2102251662Sdim } 2103251662Sdim 2104251662Sdim return NewB; 2105251662Sdim} 2106251662Sdim 2107249423SdimRegionBindingsRef RegionStoreManager::bindStruct(RegionBindingsConstRef B, 2108249423Sdim const TypedValueRegion* R, 2109249423Sdim SVal V) { 2110218887Sdim if (!Features.supportsFields()) 2111249423Sdim return B; 2112218887Sdim 2113218887Sdim QualType T = R->getValueType(); 2114218887Sdim assert(T->isStructureOrClassType()); 2115218887Sdim 2116218887Sdim const RecordType* RT = T->getAs<RecordType>(); 2117251662Sdim const RecordDecl *RD = RT->getDecl(); 2118218887Sdim 2119226633Sdim if (!RD->isCompleteDefinition()) 2120249423Sdim return B; 2121218887Sdim 2122239462Sdim // Handle lazy compound values and symbolic values. 2123251662Sdim if (Optional<nonloc::LazyCompoundVal> LCV = 2124251662Sdim V.getAs<nonloc::LazyCompoundVal>()) { 2125251662Sdim if (Optional<RegionBindingsRef> NewB = tryBindSmallStruct(B, R, RD, *LCV)) 2126251662Sdim return *NewB; 2127249423Sdim return bindAggregate(B, R, V); 2128251662Sdim } 2129251662Sdim if (V.getAs<nonloc::SymbolVal>()) 2130251662Sdim return bindAggregate(B, R, V); 2131218887Sdim 2132218887Sdim // We may get non-CompoundVal accidentally due to imprecise cast logic or 2133218887Sdim // that we are binding symbolic struct value. Kill the field values, and if 2134218887Sdim // the value is symbolic go and bind it as a "default" binding. 2135249423Sdim if (V.isUnknown() || !V.getAs<nonloc::CompoundVal>()) 2136249423Sdim return bindAggregate(B, R, UnknownVal()); 2137218887Sdim 2138249423Sdim const nonloc::CompoundVal& CV = V.castAs<nonloc::CompoundVal>(); 2139218887Sdim nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); 2140218887Sdim 2141218887Sdim RecordDecl::field_iterator FI, FE; 2142249423Sdim RegionBindingsRef NewB(B); 2143249423Sdim 2144234353Sdim for (FI = RD->field_begin(), FE = RD->field_end(); FI != FE; ++FI) { 2145218887Sdim 2146218887Sdim if (VI == VE) 2147218887Sdim break; 2148218887Sdim 2149234353Sdim // Skip any unnamed bitfields to stay in sync with the initializers. 2150239462Sdim if (FI->isUnnamedBitfield()) 2151234353Sdim continue; 2152234353Sdim 2153239462Sdim QualType FTy = FI->getType(); 2154218887Sdim const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R); 2155218887Sdim 2156218887Sdim if (FTy->isArrayType()) 2157249423Sdim NewB = bindArray(NewB, FR, *VI); 2158218887Sdim else if (FTy->isStructureOrClassType()) 2159249423Sdim NewB = bindStruct(NewB, FR, *VI); 2160218887Sdim else 2161251662Sdim NewB = bind(NewB, loc::MemRegionVal(FR), *VI); 2162234353Sdim ++VI; 2163218887Sdim } 2164218887Sdim 2165218887Sdim // There may be fewer values in the initialize list than the fields of struct. 2166218887Sdim if (FI != FE) { 2167249423Sdim NewB = NewB.addBinding(R, BindingKey::Default, 2168249423Sdim svalBuilder.makeIntVal(0, false)); 2169218887Sdim } 2170218887Sdim 2171249423Sdim return NewB; 2172218887Sdim} 2173218887Sdim 2174249423SdimRegionBindingsRef 2175249423SdimRegionStoreManager::bindAggregate(RegionBindingsConstRef B, 2176249423Sdim const TypedRegion *R, 2177249423Sdim SVal Val) { 2178239462Sdim // Remove the old bindings, using 'R' as the root of all regions 2179239462Sdim // we will invalidate. Then add the new binding. 2180249423Sdim return removeSubRegionBindings(B, R).addBinding(R, BindingKey::Default, Val); 2181218887Sdim} 2182218887Sdim 2183218887Sdim//===----------------------------------------------------------------------===// 2184218887Sdim// State pruning. 2185218887Sdim//===----------------------------------------------------------------------===// 2186218887Sdim 2187218887Sdimnamespace { 2188218887Sdimclass removeDeadBindingsWorker : 2189218887Sdim public ClusterAnalysis<removeDeadBindingsWorker> { 2190226633Sdim SmallVector<const SymbolicRegion*, 12> Postponed; 2191218887Sdim SymbolReaper &SymReaper; 2192218887Sdim const StackFrameContext *CurrentLCtx; 2193218887Sdim 2194218887Sdimpublic: 2195234353Sdim removeDeadBindingsWorker(RegionStoreManager &rm, 2196234353Sdim ProgramStateManager &stateMgr, 2197249423Sdim RegionBindingsRef b, SymbolReaper &symReaper, 2198218887Sdim const StackFrameContext *LCtx) 2199251662Sdim : ClusterAnalysis<removeDeadBindingsWorker>(rm, stateMgr, b, GFK_None), 2200218887Sdim SymReaper(symReaper), CurrentLCtx(LCtx) {} 2201218887Sdim 2202218887Sdim // Called by ClusterAnalysis. 2203239462Sdim void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C); 2204249423Sdim void VisitCluster(const MemRegion *baseR, const ClusterBindings *C); 2205249423Sdim using ClusterAnalysis<removeDeadBindingsWorker>::VisitCluster; 2206218887Sdim 2207218887Sdim bool UpdatePostponed(); 2208218887Sdim void VisitBinding(SVal V); 2209218887Sdim}; 2210218887Sdim} 2211218887Sdim 2212218887Sdimvoid removeDeadBindingsWorker::VisitAddedToCluster(const MemRegion *baseR, 2213239462Sdim const ClusterBindings &C) { 2214218887Sdim 2215218887Sdim if (const VarRegion *VR = dyn_cast<VarRegion>(baseR)) { 2216218887Sdim if (SymReaper.isLive(VR)) 2217239462Sdim AddToWorkList(baseR, &C); 2218218887Sdim 2219218887Sdim return; 2220218887Sdim } 2221218887Sdim 2222218887Sdim if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) { 2223218887Sdim if (SymReaper.isLive(SR->getSymbol())) 2224239462Sdim AddToWorkList(SR, &C); 2225218887Sdim else 2226218887Sdim Postponed.push_back(SR); 2227218887Sdim 2228218887Sdim return; 2229218887Sdim } 2230218887Sdim 2231218887Sdim if (isa<NonStaticGlobalSpaceRegion>(baseR)) { 2232239462Sdim AddToWorkList(baseR, &C); 2233218887Sdim return; 2234218887Sdim } 2235218887Sdim 2236218887Sdim // CXXThisRegion in the current or parent location context is live. 2237218887Sdim if (const CXXThisRegion *TR = dyn_cast<CXXThisRegion>(baseR)) { 2238218887Sdim const StackArgumentsSpaceRegion *StackReg = 2239218887Sdim cast<StackArgumentsSpaceRegion>(TR->getSuperRegion()); 2240218887Sdim const StackFrameContext *RegCtx = StackReg->getStackFrame(); 2241243830Sdim if (CurrentLCtx && 2242243830Sdim (RegCtx == CurrentLCtx || RegCtx->isParentOf(CurrentLCtx))) 2243239462Sdim AddToWorkList(TR, &C); 2244218887Sdim } 2245218887Sdim} 2246218887Sdim 2247218887Sdimvoid removeDeadBindingsWorker::VisitCluster(const MemRegion *baseR, 2248249423Sdim const ClusterBindings *C) { 2249249423Sdim if (!C) 2250249423Sdim return; 2251249423Sdim 2252243830Sdim // Mark the symbol for any SymbolicRegion with live bindings as live itself. 2253243830Sdim // This means we should continue to track that symbol. 2254243830Sdim if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(baseR)) 2255243830Sdim SymReaper.markLive(SymR->getSymbol()); 2256243830Sdim 2257249423Sdim for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I) 2258239462Sdim VisitBinding(I.getData()); 2259218887Sdim} 2260218887Sdim 2261218887Sdimvoid removeDeadBindingsWorker::VisitBinding(SVal V) { 2262218887Sdim // Is it a LazyCompoundVal? All referenced regions are live as well. 2263249423Sdim if (Optional<nonloc::LazyCompoundVal> LCS = 2264249423Sdim V.getAs<nonloc::LazyCompoundVal>()) { 2265218887Sdim 2266249423Sdim const RegionStoreManager::SValListTy &Vals = RM.getInterestingValues(*LCS); 2267239462Sdim 2268249423Sdim for (RegionStoreManager::SValListTy::const_iterator I = Vals.begin(), 2269249423Sdim E = Vals.end(); 2270249423Sdim I != E; ++I) 2271249423Sdim VisitBinding(*I); 2272239462Sdim 2273218887Sdim return; 2274218887Sdim } 2275218887Sdim 2276218887Sdim // If V is a region, then add it to the worklist. 2277239462Sdim if (const MemRegion *R = V.getAsRegion()) { 2278218887Sdim AddToWorkList(R); 2279239462Sdim 2280239462Sdim // All regions captured by a block are also live. 2281239462Sdim if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(R)) { 2282239462Sdim BlockDataRegion::referenced_vars_iterator I = BR->referenced_vars_begin(), 2283239462Sdim E = BR->referenced_vars_end(); 2284243830Sdim for ( ; I != E; ++I) 2285243830Sdim AddToWorkList(I.getCapturedRegion()); 2286239462Sdim } 2287239462Sdim } 2288239462Sdim 2289218887Sdim 2290234353Sdim // Update the set of live symbols. 2291234353Sdim for (SymExpr::symbol_iterator SI = V.symbol_begin(), SE = V.symbol_end(); 2292234353Sdim SI!=SE; ++SI) 2293218887Sdim SymReaper.markLive(*SI); 2294218887Sdim} 2295218887Sdim 2296218887Sdimbool removeDeadBindingsWorker::UpdatePostponed() { 2297218887Sdim // See if any postponed SymbolicRegions are actually live now, after 2298218887Sdim // having done a scan. 2299218887Sdim bool changed = false; 2300218887Sdim 2301226633Sdim for (SmallVectorImpl<const SymbolicRegion*>::iterator 2302218887Sdim I = Postponed.begin(), E = Postponed.end() ; I != E ; ++I) { 2303243830Sdim if (const SymbolicRegion *SR = *I) { 2304218887Sdim if (SymReaper.isLive(SR->getSymbol())) { 2305218887Sdim changed |= AddToWorkList(SR); 2306218887Sdim *I = NULL; 2307218887Sdim } 2308218887Sdim } 2309218887Sdim } 2310218887Sdim 2311218887Sdim return changed; 2312218887Sdim} 2313218887Sdim 2314218887SdimStoreRef RegionStoreManager::removeDeadBindings(Store store, 2315218887Sdim const StackFrameContext *LCtx, 2316226633Sdim SymbolReaper& SymReaper) { 2317249423Sdim RegionBindingsRef B = getRegionBindings(store); 2318218887Sdim removeDeadBindingsWorker W(*this, StateMgr, B, SymReaper, LCtx); 2319218887Sdim W.GenerateClusters(); 2320218887Sdim 2321218887Sdim // Enqueue the region roots onto the worklist. 2322226633Sdim for (SymbolReaper::region_iterator I = SymReaper.region_begin(), 2323226633Sdim E = SymReaper.region_end(); I != E; ++I) { 2324218887Sdim W.AddToWorkList(*I); 2325226633Sdim } 2326218887Sdim 2327218887Sdim do W.RunWorkList(); while (W.UpdatePostponed()); 2328218887Sdim 2329218887Sdim // We have now scanned the store, marking reachable regions and symbols 2330218887Sdim // as live. We now remove all the regions that are dead from the store 2331218887Sdim // as well as update DSymbols with the set symbols that are now dead. 2332249423Sdim for (RegionBindingsRef::iterator I = B.begin(), E = B.end(); I != E; ++I) { 2333239462Sdim const MemRegion *Base = I.getKey(); 2334218887Sdim 2335218887Sdim // If the cluster has been visited, we know the region has been marked. 2336239462Sdim if (W.isVisited(Base)) 2337218887Sdim continue; 2338218887Sdim 2339218887Sdim // Remove the dead entry. 2340249423Sdim B = B.remove(Base); 2341218887Sdim 2342239462Sdim if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(Base)) 2343218887Sdim SymReaper.maybeDead(SymR->getSymbol()); 2344218887Sdim 2345239462Sdim // Mark all non-live symbols that this binding references as dead. 2346239462Sdim const ClusterBindings &Cluster = I.getData(); 2347239462Sdim for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); 2348239462Sdim CI != CE; ++CI) { 2349239462Sdim SVal X = CI.getData(); 2350239462Sdim SymExpr::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end(); 2351239462Sdim for (; SI != SE; ++SI) 2352239462Sdim SymReaper.maybeDead(*SI); 2353239462Sdim } 2354218887Sdim } 2355218887Sdim 2356249423Sdim return StoreRef(B.asStore(), *this); 2357218887Sdim} 2358218887Sdim 2359218887Sdim//===----------------------------------------------------------------------===// 2360218887Sdim// Utility methods. 2361218887Sdim//===----------------------------------------------------------------------===// 2362218887Sdim 2363226633Sdimvoid RegionStoreManager::print(Store store, raw_ostream &OS, 2364218887Sdim const char* nl, const char *sep) { 2365249423Sdim RegionBindingsRef B = getRegionBindings(store); 2366239462Sdim OS << "Store (direct and default bindings), " 2367249423Sdim << B.asStore() 2368239462Sdim << " :" << nl; 2369249423Sdim B.dump(OS, nl); 2370218887Sdim} 2371