diff options
| author | dim <dim@FreeBSD.org> | 2013-04-08 18:45:10 +0000 |
|---|---|---|
| committer | dim <dim@FreeBSD.org> | 2013-04-08 18:45:10 +0000 |
| commit | c72c57c9e9b69944e3e009cd5e209634839581d3 (patch) | |
| tree | 4fc2f184c499d106f29a386c452b49e5197bf63d /lib/StaticAnalyzer/Core/RegionStore.cpp | |
| parent | 5b20025c30d23d521e12c1f33ec8fa6b821952cd (diff) | |
| download | FreeBSD-src-c72c57c9e9b69944e3e009cd5e209634839581d3.zip FreeBSD-src-c72c57c9e9b69944e3e009cd5e209634839581d3.tar.gz | |
Vendor import of clang trunk r178860:
http://llvm.org/svn/llvm-project/cfe/trunk@178860
Diffstat (limited to 'lib/StaticAnalyzer/Core/RegionStore.cpp')
| -rw-r--r-- | lib/StaticAnalyzer/Core/RegionStore.cpp | 1506 |
1 files changed, 893 insertions, 613 deletions
diff --git a/lib/StaticAnalyzer/Core/RegionStore.cpp b/lib/StaticAnalyzer/Core/RegionStore.cpp index aed994d..0f4a682 100644 --- a/lib/StaticAnalyzer/Core/RegionStore.cpp +++ b/lib/StaticAnalyzer/Core/RegionStore.cpp @@ -14,14 +14,15 @@ // parameters are created lazily. // //===----------------------------------------------------------------------===// +#include "clang/AST/Attr.h" #include "clang/AST/CharUnits.h" #include "clang/Analysis/Analyses/LiveVariables.h" #include "clang/Analysis/AnalysisContext.h" #include "clang/Basic/TargetInfo.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" #include "llvm/ADT/ImmutableList.h" #include "llvm/ADT/ImmutableMap.h" #include "llvm/ADT/Optional.h" @@ -29,7 +30,6 @@ using namespace clang; using namespace ento; -using llvm::Optional; //===----------------------------------------------------------------------===// // Representation of binding keys. @@ -45,11 +45,15 @@ private: llvm::PointerIntPair<const MemRegion *, 2> P; uint64_t Data; - explicit BindingKey(const MemRegion *r, const MemRegion *Base, Kind k) + /// Create a key for a binding to region \p r, which has a symbolic offset + /// from region \p Base. + explicit BindingKey(const SubRegion *r, const SubRegion *Base, Kind k) : P(r, k | Symbolic), Data(reinterpret_cast<uintptr_t>(Base)) { assert(r && Base && "Must have known regions."); assert(getConcreteOffsetRegion() == Base && "Failed to store base region"); } + + /// Create a key for a binding at \p offset from base region \p r. explicit BindingKey(const MemRegion *r, uint64_t offset, Kind k) : P(r, k), Data(offset) { assert(r && "Must have known regions."); @@ -67,9 +71,9 @@ public: return Data; } - const MemRegion *getConcreteOffsetRegion() const { + const SubRegion *getConcreteOffsetRegion() const { assert(hasSymbolicOffset()); - return reinterpret_cast<const MemRegion *>(static_cast<uintptr_t>(Data)); + return reinterpret_cast<const SubRegion *>(static_cast<uintptr_t>(Data)); } const MemRegion *getBaseRegion() const { @@ -105,7 +109,7 @@ public: BindingKey BindingKey::Make(const MemRegion *R, Kind k) { const RegionOffset &RO = R->getAsOffset(); if (RO.hasSymbolicOffset()) - return BindingKey(R, RO.getRegion(), k); + return BindingKey(cast<SubRegion>(R), cast<SubRegion>(RO.getRegion()), k); return BindingKey(RO.getRegion(), RO.getOffset(), k); } @@ -120,6 +124,11 @@ namespace llvm { << ')'; return os; } + + template <typename T> struct isPodLike; + template <> struct isPodLike<BindingKey> { + static const bool value = true; + }; } // end llvm namespace void BindingKey::dump() const { @@ -130,8 +139,156 @@ void BindingKey::dump() const { // Actual Store type. //===----------------------------------------------------------------------===// -typedef llvm::ImmutableMap<BindingKey, SVal> ClusterBindings; -typedef llvm::ImmutableMap<const MemRegion *, ClusterBindings> RegionBindings; +typedef llvm::ImmutableMap<BindingKey, SVal> ClusterBindings; +typedef llvm::ImmutableMapRef<BindingKey, SVal> ClusterBindingsRef; +typedef std::pair<BindingKey, SVal> BindingPair; + +typedef llvm::ImmutableMap<const MemRegion *, ClusterBindings> + RegionBindings; + +namespace { +class RegionBindingsRef : public llvm::ImmutableMapRef<const MemRegion *, + ClusterBindings> { + ClusterBindings::Factory &CBFactory; +public: + typedef llvm::ImmutableMapRef<const MemRegion *, ClusterBindings> + ParentTy; + + RegionBindingsRef(ClusterBindings::Factory &CBFactory, + const RegionBindings::TreeTy *T, + RegionBindings::TreeTy::Factory *F) + : llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>(T, F), + CBFactory(CBFactory) {} + + RegionBindingsRef(const ParentTy &P, ClusterBindings::Factory &CBFactory) + : llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>(P), + CBFactory(CBFactory) {} + + RegionBindingsRef add(key_type_ref K, data_type_ref D) const { + return RegionBindingsRef(static_cast<const ParentTy*>(this)->add(K, D), + CBFactory); + } + + RegionBindingsRef remove(key_type_ref K) const { + return RegionBindingsRef(static_cast<const ParentTy*>(this)->remove(K), + CBFactory); + } + + RegionBindingsRef addBinding(BindingKey K, SVal V) const; + + RegionBindingsRef addBinding(const MemRegion *R, + BindingKey::Kind k, SVal V) const; + + RegionBindingsRef &operator=(const RegionBindingsRef &X) { + *static_cast<ParentTy*>(this) = X; + return *this; + } + + const SVal *lookup(BindingKey K) const; + const SVal *lookup(const MemRegion *R, BindingKey::Kind k) const; + const ClusterBindings *lookup(const MemRegion *R) const { + return static_cast<const ParentTy*>(this)->lookup(R); + } + + RegionBindingsRef removeBinding(BindingKey K); + + RegionBindingsRef removeBinding(const MemRegion *R, + BindingKey::Kind k); + + RegionBindingsRef removeBinding(const MemRegion *R) { + return removeBinding(R, BindingKey::Direct). + removeBinding(R, BindingKey::Default); + } + + Optional<SVal> getDirectBinding(const MemRegion *R) const; + + /// getDefaultBinding - Returns an SVal* representing an optional default + /// binding associated with a region and its subregions. + Optional<SVal> getDefaultBinding(const MemRegion *R) const; + + /// Return the internal tree as a Store. + Store asStore() const { + return asImmutableMap().getRootWithoutRetain(); + } + + void dump(raw_ostream &OS, const char *nl) const { + for (iterator I = begin(), E = end(); I != E; ++I) { + const ClusterBindings &Cluster = I.getData(); + for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); + CI != CE; ++CI) { + OS << ' ' << CI.getKey() << " : " << CI.getData() << nl; + } + OS << nl; + } + } + + LLVM_ATTRIBUTE_USED void dump() const { + dump(llvm::errs(), "\n"); + } +}; +} // end anonymous namespace + +typedef const RegionBindingsRef& RegionBindingsConstRef; + +Optional<SVal> RegionBindingsRef::getDirectBinding(const MemRegion *R) const { + return Optional<SVal>::create(lookup(R, BindingKey::Direct)); +} + +Optional<SVal> RegionBindingsRef::getDefaultBinding(const MemRegion *R) const { + if (R->isBoundable()) + if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) + if (TR->getValueType()->isUnionType()) + return UnknownVal(); + + return Optional<SVal>::create(lookup(R, BindingKey::Default)); +} + +RegionBindingsRef RegionBindingsRef::addBinding(BindingKey K, SVal V) const { + const MemRegion *Base = K.getBaseRegion(); + + const ClusterBindings *ExistingCluster = lookup(Base); + ClusterBindings Cluster = (ExistingCluster ? *ExistingCluster + : CBFactory.getEmptyMap()); + + ClusterBindings NewCluster = CBFactory.add(Cluster, K, V); + return add(Base, NewCluster); +} + + +RegionBindingsRef RegionBindingsRef::addBinding(const MemRegion *R, + BindingKey::Kind k, + SVal V) const { + return addBinding(BindingKey::Make(R, k), V); +} + +const SVal *RegionBindingsRef::lookup(BindingKey K) const { + const ClusterBindings *Cluster = lookup(K.getBaseRegion()); + if (!Cluster) + return 0; + return Cluster->lookup(K); +} + +const SVal *RegionBindingsRef::lookup(const MemRegion *R, + BindingKey::Kind k) const { + return lookup(BindingKey::Make(R, k)); +} + +RegionBindingsRef RegionBindingsRef::removeBinding(BindingKey K) { + const MemRegion *Base = K.getBaseRegion(); + const ClusterBindings *Cluster = lookup(Base); + if (!Cluster) + return *this; + + ClusterBindings NewCluster = CBFactory.remove(*Cluster, K); + if (NewCluster.isEmpty()) + return remove(Base); + return add(Base, NewCluster); +} + +RegionBindingsRef RegionBindingsRef::removeBinding(const MemRegion *R, + BindingKey::Kind k){ + return removeBinding(BindingKey::Make(R, k)); +} //===----------------------------------------------------------------------===// // Fine-grained control of RegionStoreManager. @@ -161,26 +318,38 @@ public: //===----------------------------------------------------------------------===// namespace { +class invalidateRegionsWorker; class RegionStoreManager : public StoreManager { +public: const RegionStoreFeatures Features; RegionBindings::Factory RBFactory; - ClusterBindings::Factory CBFactory; + mutable ClusterBindings::Factory CBFactory; + + typedef std::vector<SVal> SValListTy; +private: + typedef llvm::DenseMap<const LazyCompoundValData *, + SValListTy> LazyBindingsMapTy; + LazyBindingsMapTy LazyBindingsMap; + + /// \brief A helper used to populate the work list with the given set of + /// regions. + void populateWorkList(invalidateRegionsWorker &W, + ArrayRef<SVal> Values, + bool IsArrayOfConstRegions, + InvalidatedRegions *TopLevelRegions); public: RegionStoreManager(ProgramStateManager& mgr, const RegionStoreFeatures &f) : StoreManager(mgr), Features(f), RBFactory(mgr.getAllocator()), CBFactory(mgr.getAllocator()) {} - Optional<SVal> getDirectBinding(RegionBindings B, const MemRegion *R); - /// getDefaultBinding - Returns an SVal* representing an optional default - /// binding associated with a region and its subregions. - Optional<SVal> getDefaultBinding(RegionBindings B, const MemRegion *R); /// setImplicitDefaultValue - Set the default binding for the provided /// MemRegion to the value implicitly defined for compound literals when /// the value is not specified. - StoreRef setImplicitDefaultValue(Store store, const MemRegion *R, QualType T); + RegionBindingsRef setImplicitDefaultValue(RegionBindingsConstRef B, + const MemRegion *R, QualType T); /// ArrayToPointer - Emulates the "decay" of an array to a pointer /// type. 'Array' represents the lvalue of the array being decayed @@ -197,57 +366,47 @@ public: //===-------------------------------------------------------------------===// // Binding values to regions. //===-------------------------------------------------------------------===// - RegionBindings invalidateGlobalRegion(MemRegion::Kind K, - const Expr *Ex, - unsigned Count, - const LocationContext *LCtx, - RegionBindings B, - InvalidatedRegions *Invalidated); - - StoreRef invalidateRegions(Store store, ArrayRef<const MemRegion *> Regions, + RegionBindingsRef invalidateGlobalRegion(MemRegion::Kind K, + const Expr *Ex, + unsigned Count, + const LocationContext *LCtx, + RegionBindingsRef B, + InvalidatedRegions *Invalidated); + + StoreRef invalidateRegions(Store store, + ArrayRef<SVal> Values, + ArrayRef<SVal> ConstValues, const Expr *E, unsigned Count, const LocationContext *LCtx, - InvalidatedSymbols &IS, const CallEvent *Call, - InvalidatedRegions *Invalidated); + InvalidatedSymbols &IS, + InvalidatedSymbols &ConstIS, + InvalidatedRegions *Invalidated, + InvalidatedRegions *InvalidatedTopLevel, + InvalidatedRegions *InvalidatedTopLevelConst); bool scanReachableSymbols(Store S, const MemRegion *R, ScanReachableSymbols &Callbacks); -public: // Made public for helper classes. - - RegionBindings removeSubRegionBindings(RegionBindings B, const SubRegion *R); - - RegionBindings addBinding(RegionBindings B, BindingKey K, SVal V); - - RegionBindings addBinding(RegionBindings B, const MemRegion *R, - BindingKey::Kind k, SVal V); - - const SVal *lookup(RegionBindings B, BindingKey K); - const SVal *lookup(RegionBindings B, const MemRegion *R, BindingKey::Kind k); + RegionBindingsRef removeSubRegionBindings(RegionBindingsConstRef B, + const SubRegion *R); - RegionBindings removeBinding(RegionBindings B, BindingKey K); - RegionBindings removeBinding(RegionBindings B, const MemRegion *R, - BindingKey::Kind k); +public: // Part of public interface to class. - RegionBindings removeBinding(RegionBindings B, const MemRegion *R) { - return removeBinding(removeBinding(B, R, BindingKey::Direct), R, - BindingKey::Default); + virtual StoreRef Bind(Store store, Loc LV, SVal V) { + return StoreRef(bind(getRegionBindings(store), LV, V).asStore(), *this); } - RegionBindings removeCluster(RegionBindings B, const MemRegion *R); - -public: // Part of public interface to class. - - StoreRef Bind(Store store, Loc LV, SVal V); + RegionBindingsRef bind(RegionBindingsConstRef B, Loc LV, SVal V); // BindDefault is only used to initialize a region with a default value. StoreRef BindDefault(Store store, const MemRegion *R, SVal V) { - RegionBindings B = GetRegionBindings(store); - assert(!lookup(B, R, BindingKey::Default)); - assert(!lookup(B, R, BindingKey::Direct)); - return StoreRef(addBinding(B, R, BindingKey::Default, V) - .getRootWithoutRetain(), *this); + RegionBindingsRef B = getRegionBindings(store); + assert(!B.lookup(R, BindingKey::Default)); + assert(!B.lookup(R, BindingKey::Direct)); + return StoreRef(B.addBinding(R, BindingKey::Default, V) + .asImmutableMap() + .getRootWithoutRetain(), *this); } /// \brief Create a new store that binds a value to a compound literal. @@ -265,31 +424,37 @@ public: // Part of public interface to class. const LocationContext *LC, SVal V); /// BindStruct - Bind a compound value to a structure. - StoreRef BindStruct(Store store, const TypedValueRegion* R, SVal V); + RegionBindingsRef bindStruct(RegionBindingsConstRef B, + const TypedValueRegion* R, SVal V); /// BindVector - Bind a compound value to a vector. - StoreRef BindVector(Store store, const TypedValueRegion* R, SVal V); + RegionBindingsRef bindVector(RegionBindingsConstRef B, + const TypedValueRegion* R, SVal V); - StoreRef BindArray(Store store, const TypedValueRegion* R, SVal V); + RegionBindingsRef bindArray(RegionBindingsConstRef B, + const TypedValueRegion* R, + SVal V); /// Clears out all bindings in the given region and assigns a new value /// as a Default binding. - StoreRef BindAggregate(Store store, const TypedRegion *R, SVal DefaultVal); + RegionBindingsRef bindAggregate(RegionBindingsConstRef B, + const TypedRegion *R, + SVal DefaultVal); /// \brief Create a new store with the specified binding removed. /// \param ST the original store, that is the basis for the new store. /// \param L the location whose binding should be removed. - StoreRef killBinding(Store ST, Loc L); + virtual StoreRef killBinding(Store ST, Loc L); void incrementReferenceCount(Store store) { - GetRegionBindings(store).manualRetain(); + getRegionBindings(store).manualRetain(); } /// If the StoreManager supports it, decrement the reference count of /// the specified Store object. If the reference count hits 0, the memory /// associated with the object is recycled. void decrementReferenceCount(Store store) { - GetRegionBindings(store).manualRelease(); + getRegionBindings(store).manualRelease(); } bool includedInBindings(Store store, const MemRegion *region) const; @@ -307,45 +472,64 @@ public: // Part of public interface to class. /// return undefined /// else /// return symbolic - SVal getBinding(Store store, Loc L, QualType T = QualType()); + virtual SVal getBinding(Store S, Loc L, QualType T) { + return getBinding(getRegionBindings(S), L, T); + } - SVal getBindingForElement(Store store, const ElementRegion *R); + SVal getBinding(RegionBindingsConstRef B, Loc L, QualType T = QualType()); - SVal getBindingForField(Store store, const FieldRegion *R); + SVal getBindingForElement(RegionBindingsConstRef B, const ElementRegion *R); - SVal getBindingForObjCIvar(Store store, const ObjCIvarRegion *R); + SVal getBindingForField(RegionBindingsConstRef B, const FieldRegion *R); - SVal getBindingForVar(Store store, const VarRegion *R); + SVal getBindingForObjCIvar(RegionBindingsConstRef B, const ObjCIvarRegion *R); + + SVal getBindingForVar(RegionBindingsConstRef B, const VarRegion *R); SVal getBindingForLazySymbol(const TypedValueRegion *R); - SVal getBindingForFieldOrElementCommon(Store store, const TypedValueRegion *R, - QualType Ty, const MemRegion *superR); + SVal getBindingForFieldOrElementCommon(RegionBindingsConstRef B, + const TypedValueRegion *R, + QualType Ty, + const MemRegion *superR); - SVal getLazyBinding(const MemRegion *lazyBindingRegion, - Store lazyBindingStore); + SVal getLazyBinding(const SubRegion *LazyBindingRegion, + RegionBindingsRef LazyBinding); /// Get bindings for the values in a struct and return a CompoundVal, used /// when doing struct copy: /// struct s x, y; /// x = y; /// y's value is retrieved by this method. - SVal getBindingForStruct(Store store, const TypedValueRegion* R); - - SVal getBindingForArray(Store store, const TypedValueRegion* R); + SVal getBindingForStruct(RegionBindingsConstRef B, const TypedValueRegion *R); + SVal getBindingForArray(RegionBindingsConstRef B, const TypedValueRegion *R); + NonLoc createLazyBinding(RegionBindingsConstRef B, const TypedValueRegion *R); /// Used to lazily generate derived symbols for bindings that are defined - /// implicitly by default bindings in a super region. - Optional<SVal> getBindingForDerivedDefaultValue(RegionBindings B, + /// implicitly by default bindings in a super region. + /// + /// Note that callers may need to specially handle LazyCompoundVals, which + /// are returned as is in case the caller needs to treat them differently. + Optional<SVal> getBindingForDerivedDefaultValue(RegionBindingsConstRef B, const MemRegion *superR, const TypedValueRegion *R, QualType Ty); - /// Get the state and region whose binding this region R corresponds to. - std::pair<Store, const MemRegion*> - GetLazyBinding(RegionBindings B, const MemRegion *R, - const MemRegion *originalRegion, - bool includeSuffix = false); + /// Get the state and region whose binding this region \p R corresponds to. + /// + /// If there is no lazy binding for \p R, the returned value will have a null + /// \c second. Note that a null pointer can represents a valid Store. + std::pair<Store, const SubRegion *> + findLazyBinding(RegionBindingsConstRef B, const SubRegion *R, + const SubRegion *originalRegion); + + /// Returns the cached set of interesting SVals contained within a lazy + /// binding. + /// + /// The precise value of "interesting" is determined for the purposes of + /// RegionStore's internal analysis. It must always contain all regions and + /// symbols, but may omit constants and other kinds of SVal. + const SValListTy &getInterestingValues(nonloc::LazyCompoundVal LCV); //===------------------------------------------------------------------===// // State pruning. @@ -368,16 +552,18 @@ public: // Part of public interface to class. // Utility methods. //===------------------------------------------------------------------===// - static inline RegionBindings GetRegionBindings(Store store) { - return RegionBindings(static_cast<const RegionBindings::TreeTy*>(store)); + RegionBindingsRef getRegionBindings(Store store) const { + return RegionBindingsRef(CBFactory, + static_cast<const RegionBindings::TreeTy*>(store), + RBFactory.getTreeFactory()); } void print(Store store, raw_ostream &Out, const char* nl, const char *sep); void iterBindings(Store store, BindingsHandler& f) { - RegionBindings B = GetRegionBindings(store); - for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) { + RegionBindingsRef B = getRegionBindings(store); + for (RegionBindingsRef::iterator I = B.begin(), E = B.end(); I != E; ++I) { const ClusterBindings &Cluster = I.getData(); for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); CI != CE; ++CI) { @@ -422,7 +608,8 @@ template <typename DERIVED> class ClusterAnalysis { protected: typedef llvm::DenseMap<const MemRegion *, const ClusterBindings *> ClusterMap; - typedef SmallVector<const MemRegion *, 10> WorkList; + typedef llvm::PointerIntPair<const MemRegion *, 1, bool> WorkListElement; + typedef SmallVector<WorkListElement, 10> WorkList; llvm::SmallPtrSet<const ClusterBindings *, 16> Visited; @@ -432,7 +619,7 @@ protected: ASTContext &Ctx; SValBuilder &svalBuilder; - RegionBindings B; + RegionBindingsRef B; const bool includeGlobals; @@ -442,12 +629,12 @@ protected: public: ClusterAnalysis(RegionStoreManager &rm, ProgramStateManager &StateMgr, - RegionBindings b, const bool includeGlobals) + RegionBindingsRef b, const bool includeGlobals) : RM(rm), Ctx(StateMgr.getContext()), svalBuilder(StateMgr.getSValBuilder()), B(b), includeGlobals(includeGlobals) {} - RegionBindings getRegionBindings() const { return B; } + RegionBindingsRef getRegionBindings() const { return B; } bool isVisited(const MemRegion *R) { return Visited.count(getCluster(R)); @@ -455,7 +642,8 @@ public: void GenerateClusters() { // Scan the entire set of bindings and record the region clusters. - for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){ + for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end(); + RI != RE; ++RI){ const MemRegion *Base = RI.getKey(); const ClusterBindings &Cluster = RI.getData(); @@ -468,35 +656,35 @@ public: } } - bool AddToWorkList(const MemRegion *R, const ClusterBindings *C) { + bool AddToWorkList(WorkListElement E, const ClusterBindings *C) { if (C && !Visited.insert(C)) return false; - WL.push_back(R); + WL.push_back(E); return true; } - bool AddToWorkList(const MemRegion *R) { - const MemRegion *baseR = R->getBaseRegion(); - return AddToWorkList(baseR, getCluster(baseR)); + bool AddToWorkList(const MemRegion *R, bool Flag = false) { + const MemRegion *BaseR = R->getBaseRegion(); + return AddToWorkList(WorkListElement(BaseR, Flag), getCluster(BaseR)); } void RunWorkList() { while (!WL.empty()) { - const MemRegion *baseR = WL.pop_back_val(); + WorkListElement E = WL.pop_back_val(); + const MemRegion *BaseR = E.getPointer(); - // First visit the cluster. - if (const ClusterBindings *Cluster = getCluster(baseR)) - static_cast<DERIVED*>(this)->VisitCluster(baseR, *Cluster); - - // Next, visit the base region. - static_cast<DERIVED*>(this)->VisitBaseRegion(baseR); + static_cast<DERIVED*>(this)->VisitCluster(BaseR, getCluster(BaseR), + E.getInt()); } } -public: void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C) {} - void VisitCluster(const MemRegion *baseR, const ClusterBindings &C) {} - void VisitBaseRegion(const MemRegion *baseR) {} + void VisitCluster(const MemRegion *baseR, const ClusterBindings *C) {} + + void VisitCluster(const MemRegion *BaseR, const ClusterBindings *C, + bool Flag) { + static_cast<DERIVED*>(this)->VisitCluster(BaseR, C); + } }; } @@ -507,7 +695,7 @@ public: bool RegionStoreManager::scanReachableSymbols(Store S, const MemRegion *R, ScanReachableSymbols &Callbacks) { assert(R == R->getBaseRegion() && "Should only be called for base regions"); - RegionBindings B = GetRegionBindings(S); + RegionBindingsRef B = getRegionBindings(S); const ClusterBindings *Cluster = B.lookup(R); if (!Cluster) @@ -562,98 +750,141 @@ static bool isCompatibleWithFields(BindingKey K, const FieldVector &Fields) { Fields.begin() - Delta); } -RegionBindings RegionStoreManager::removeSubRegionBindings(RegionBindings B, - const SubRegion *R) { - BindingKey SRKey = BindingKey::Make(R, BindingKey::Default); - const MemRegion *ClusterHead = SRKey.getBaseRegion(); - if (R == ClusterHead) { - // We can remove an entire cluster's bindings all in one go. - return RBFactory.remove(B, R); - } - +/// Collects all bindings in \p Cluster that may refer to bindings within +/// \p Top. +/// +/// Each binding is a pair whose \c first is the key (a BindingKey) and whose +/// \c second is the value (an SVal). +/// +/// The \p IncludeAllDefaultBindings parameter specifies whether to include +/// default bindings that may extend beyond \p Top itself, e.g. if \p Top is +/// an aggregate within a larger aggregate with a default binding. +static void +collectSubRegionBindings(SmallVectorImpl<BindingPair> &Bindings, + SValBuilder &SVB, const ClusterBindings &Cluster, + const SubRegion *Top, BindingKey TopKey, + bool IncludeAllDefaultBindings) { FieldVector FieldsInSymbolicSubregions; - bool HasSymbolicOffset = SRKey.hasSymbolicOffset(); - if (HasSymbolicOffset) { - getSymbolicOffsetFields(SRKey, FieldsInSymbolicSubregions); - R = cast<SubRegion>(SRKey.getConcreteOffsetRegion()); - SRKey = BindingKey::Make(R, BindingKey::Default); + if (TopKey.hasSymbolicOffset()) { + getSymbolicOffsetFields(TopKey, FieldsInSymbolicSubregions); + Top = cast<SubRegion>(TopKey.getConcreteOffsetRegion()); + TopKey = BindingKey::Make(Top, BindingKey::Default); } - // This assumes the region being invalidated is char-aligned. This isn't - // true for bitfields, but since bitfields have no subregions they shouldn't - // be using this function anyway. + // Find the length (in bits) of the region being invalidated. uint64_t Length = UINT64_MAX; - - SVal Extent = R->getExtent(svalBuilder); - if (nonloc::ConcreteInt *ExtentCI = dyn_cast<nonloc::ConcreteInt>(&Extent)) { + SVal Extent = Top->getExtent(SVB); + if (Optional<nonloc::ConcreteInt> ExtentCI = + Extent.getAs<nonloc::ConcreteInt>()) { const llvm::APSInt &ExtentInt = ExtentCI->getValue(); assert(ExtentInt.isNonNegative() || ExtentInt.isUnsigned()); // Extents are in bytes but region offsets are in bits. Be careful! - Length = ExtentInt.getLimitedValue() * Ctx.getCharWidth(); + Length = ExtentInt.getLimitedValue() * SVB.getContext().getCharWidth(); + } else if (const FieldRegion *FR = dyn_cast<FieldRegion>(Top)) { + if (FR->getDecl()->isBitField()) + Length = FR->getDecl()->getBitWidthValue(SVB.getContext()); } - const ClusterBindings *Cluster = B.lookup(ClusterHead); - if (!Cluster) - return B; - - ClusterBindings Result = *Cluster; - - // It is safe to iterate over the bindings as they are being changed - // because they are in an ImmutableMap. - for (ClusterBindings::iterator I = Cluster->begin(), E = Cluster->end(); + for (ClusterBindings::iterator I = Cluster.begin(), E = Cluster.end(); I != E; ++I) { BindingKey NextKey = I.getKey(); - if (NextKey.getRegion() == SRKey.getRegion()) { + if (NextKey.getRegion() == TopKey.getRegion()) { // FIXME: This doesn't catch the case where we're really invalidating a // region with a symbolic offset. Example: // R: points[i].y // Next: points[0].x - if (NextKey.getOffset() > SRKey.getOffset() && - NextKey.getOffset() - SRKey.getOffset() < Length) { + if (NextKey.getOffset() > TopKey.getOffset() && + NextKey.getOffset() - TopKey.getOffset() < Length) { // Case 1: The next binding is inside the region we're invalidating. - // Remove it. - Result = CBFactory.remove(Result, NextKey); + // Include it. + Bindings.push_back(*I); - } else if (NextKey.getOffset() == SRKey.getOffset()) { + } else if (NextKey.getOffset() == TopKey.getOffset()) { // Case 2: The next binding is at the same offset as the region we're // invalidating. In this case, we need to leave default bindings alone, // since they may be providing a default value for a regions beyond what // we're invalidating. // FIXME: This is probably incorrect; consider invalidating an outer // struct whose first field is bound to a LazyCompoundVal. - if (NextKey.isDirect()) - Result = CBFactory.remove(Result, NextKey); + if (IncludeAllDefaultBindings || NextKey.isDirect()) + Bindings.push_back(*I); } - + } else if (NextKey.hasSymbolicOffset()) { const MemRegion *Base = NextKey.getConcreteOffsetRegion(); - if (R->isSubRegionOf(Base)) { + if (Top->isSubRegionOf(Base)) { // Case 3: The next key is symbolic and we just changed something within // its concrete region. We don't know if the binding is still valid, so - // we'll be conservative and remove it. - if (NextKey.isDirect()) + // we'll be conservative and include it. + if (IncludeAllDefaultBindings || NextKey.isDirect()) if (isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions)) - Result = CBFactory.remove(Result, NextKey); + Bindings.push_back(*I); } else if (const SubRegion *BaseSR = dyn_cast<SubRegion>(Base)) { // Case 4: The next key is symbolic, but we changed a known - // super-region. In this case the binding is certainly no longer valid. - if (R == Base || BaseSR->isSubRegionOf(R)) + // super-region. In this case the binding is certainly included. + if (Top == Base || BaseSR->isSubRegionOf(Top)) if (isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions)) - Result = CBFactory.remove(Result, NextKey); + Bindings.push_back(*I); } } } +} + +static void +collectSubRegionBindings(SmallVectorImpl<BindingPair> &Bindings, + SValBuilder &SVB, const ClusterBindings &Cluster, + const SubRegion *Top, bool IncludeAllDefaultBindings) { + collectSubRegionBindings(Bindings, SVB, Cluster, Top, + BindingKey::Make(Top, BindingKey::Default), + IncludeAllDefaultBindings); +} + +RegionBindingsRef +RegionStoreManager::removeSubRegionBindings(RegionBindingsConstRef B, + const SubRegion *Top) { + BindingKey TopKey = BindingKey::Make(Top, BindingKey::Default); + const MemRegion *ClusterHead = TopKey.getBaseRegion(); + + if (Top == ClusterHead) { + // We can remove an entire cluster's bindings all in one go. + return B.remove(Top); + } + + const ClusterBindings *Cluster = B.lookup(ClusterHead); + if (!Cluster) { + // If we're invalidating a region with a symbolic offset, we need to make + // sure we don't treat the base region as uninitialized anymore. + if (TopKey.hasSymbolicOffset()) { + const SubRegion *Concrete = TopKey.getConcreteOffsetRegion(); + return B.addBinding(Concrete, BindingKey::Default, UnknownVal()); + } + return B; + } + + SmallVector<BindingPair, 32> Bindings; + collectSubRegionBindings(Bindings, svalBuilder, *Cluster, Top, TopKey, + /*IncludeAllDefaultBindings=*/false); + + ClusterBindingsRef Result(*Cluster, CBFactory); + for (SmallVectorImpl<BindingPair>::const_iterator I = Bindings.begin(), + E = Bindings.end(); + I != E; ++I) + Result = Result.remove(I->first); // If we're invalidating a region with a symbolic offset, we need to make sure // we don't treat the base region as uninitialized anymore. - // FIXME: This isn't very precise; see the example in the loop. - if (HasSymbolicOffset) - Result = CBFactory.add(Result, SRKey, UnknownVal()); + // FIXME: This isn't very precise; see the example in + // collectSubRegionBindings. + if (TopKey.hasSymbolicOffset()) { + const SubRegion *Concrete = TopKey.getConcreteOffsetRegion(); + Result = Result.add(BindingKey::Make(Concrete, BindingKey::Default), + UnknownVal()); + } if (Result.isEmpty()) - return RBFactory.remove(B, ClusterHead); - return RBFactory.add(B, ClusterHead, Result); + return B.remove(ClusterHead); + return B.add(ClusterHead, Result.asImmutableMap()); } namespace { @@ -662,24 +893,26 @@ class invalidateRegionsWorker : public ClusterAnalysis<invalidateRegionsWorker> const Expr *Ex; unsigned Count; const LocationContext *LCtx; - StoreManager::InvalidatedSymbols &IS; + InvalidatedSymbols &IS; + InvalidatedSymbols &ConstIS; StoreManager::InvalidatedRegions *Regions; public: invalidateRegionsWorker(RegionStoreManager &rm, ProgramStateManager &stateMgr, - RegionBindings b, + RegionBindingsRef b, const Expr *ex, unsigned count, const LocationContext *lctx, - StoreManager::InvalidatedSymbols &is, + InvalidatedSymbols &is, + InvalidatedSymbols &inConstIS, StoreManager::InvalidatedRegions *r, bool includeGlobals) : ClusterAnalysis<invalidateRegionsWorker>(rm, stateMgr, b, includeGlobals), - Ex(ex), Count(count), LCtx(lctx), IS(is), Regions(r) {} + Ex(ex), Count(count), LCtx(lctx), IS(is), ConstIS(inConstIS), Regions(r){} - void VisitCluster(const MemRegion *baseR, const ClusterBindings &C); - void VisitBaseRegion(const MemRegion *baseR); - -private: + /// \param IsConst Specifies if the region we are invalidating is constant. + /// If it is, we invalidate all subregions, but not the base region itself. + void VisitCluster(const MemRegion *baseR, const ClusterBindings *C, + bool IsConst); void VisitBinding(SVal V); }; } @@ -695,43 +928,30 @@ void invalidateRegionsWorker::VisitBinding(SVal V) { } // Is it a LazyCompoundVal? All references get invalidated as well. - if (const nonloc::LazyCompoundVal *LCS = - dyn_cast<nonloc::LazyCompoundVal>(&V)) { + if (Optional<nonloc::LazyCompoundVal> LCS = + V.getAs<nonloc::LazyCompoundVal>()) { - const MemRegion *LazyR = LCS->getRegion(); - RegionBindings B = RegionStoreManager::GetRegionBindings(LCS->getStore()); + const RegionStoreManager::SValListTy &Vals = RM.getInterestingValues(*LCS); - // FIXME: This should not have to walk all bindings in the old store. - for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){ - const ClusterBindings &Cluster = RI.getData(); - for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); - CI != CE; ++CI) { - BindingKey K = CI.getKey(); - if (const SubRegion *BaseR = dyn_cast<SubRegion>(K.getRegion())) { - if (BaseR == LazyR) - VisitBinding(CI.getData()); - else if (K.hasSymbolicOffset() && BaseR->isSubRegionOf(LazyR)) - VisitBinding(CI.getData()); - } - } - } + for (RegionStoreManager::SValListTy::const_iterator I = Vals.begin(), + E = Vals.end(); + I != E; ++I) + VisitBinding(*I); return; } } -void invalidateRegionsWorker::VisitCluster(const MemRegion *BaseR, - const ClusterBindings &C) { - for (ClusterBindings::iterator I = C.begin(), E = C.end(); I != E; ++I) - VisitBinding(I.getData()); - - B = RM.removeCluster(B, BaseR); -} +void invalidateRegionsWorker::VisitCluster(const MemRegion *baseR, + const ClusterBindings *C, + bool IsConst) { + if (C) { + for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I) + VisitBinding(I.getData()); -void invalidateRegionsWorker::VisitBaseRegion(const MemRegion *baseR) { - // Symbolic region? Mark that symbol touched by the invalidation. - if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) - IS.insert(SR->getSymbol()); + if (!IsConst) + B = B.remove(baseR); + } // BlockDataRegion? If so, invalidate captured variables that are passed // by reference. @@ -739,7 +959,7 @@ void invalidateRegionsWorker::VisitBaseRegion(const MemRegion *baseR) { for (BlockDataRegion::referenced_vars_iterator BI = BR->referenced_vars_begin(), BE = BR->referenced_vars_end() ; BI != BE; ++BI) { - const VarRegion *VR = *BI; + const VarRegion *VR = BI.getCapturedRegion(); const VarDecl *VD = VR->getDecl(); if (VD->getAttr<BlocksAttr>() || !VD->hasLocalStorage()) { AddToWorkList(VR); @@ -750,9 +970,8 @@ void invalidateRegionsWorker::VisitBaseRegion(const MemRegion *baseR) { // invalidate that region. This is because a block may capture // a pointer value, but the thing pointed by that pointer may // get invalidated. - Store store = B.getRootWithoutRetain(); - SVal V = RM.getBinding(store, loc::MemRegionVal(VR)); - if (const Loc *L = dyn_cast<Loc>(&V)) { + SVal V = RM.getBinding(B, loc::MemRegionVal(VR)); + if (Optional<Loc> L = V.getAs<Loc>()) { if (const MemRegion *LR = L->getAsRegion()) AddToWorkList(LR); } @@ -761,6 +980,20 @@ void invalidateRegionsWorker::VisitBaseRegion(const MemRegion *baseR) { return; } + // Symbolic region? + SymbolRef RegionSym = 0; + if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) + RegionSym = SR->getSymbol(); + + if (IsConst) { + // Mark that symbol touched by the invalidation. + ConstIS.insert(RegionSym); + return; + } + + // Mark that symbol touched by the invalidation. + IS.insert(RegionSym); + // Otherwise, we have a normal data region. Record that we touched the region. if (Regions) Regions->push_back(baseR); @@ -770,7 +1003,7 @@ void invalidateRegionsWorker::VisitBaseRegion(const MemRegion *baseR) { // conjured symbol. The type of the symbol is irrelavant. DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, Ctx.IntTy, Count); - B = RM.addBinding(B, baseR, BindingKey::Default, V); + B = B.addBinding(baseR, BindingKey::Default, V); return; } @@ -786,7 +1019,7 @@ void invalidateRegionsWorker::VisitBaseRegion(const MemRegion *baseR) { // conjured symbol. The type of the symbol is irrelavant. DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, Ctx.IntTy, Count); - B = RM.addBinding(B, baseR, BindingKey::Default, V); + B = B.addBinding(baseR, BindingKey::Default, V); return; } @@ -795,7 +1028,7 @@ void invalidateRegionsWorker::VisitBaseRegion(const MemRegion *baseR) { DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, AT->getElementType(), Count); - B = RM.addBinding(B, baseR, BindingKey::Default, V); + B = B.addBinding(baseR, BindingKey::Default, V); return; } @@ -804,7 +1037,7 @@ void invalidateRegionsWorker::VisitBaseRegion(const MemRegion *baseR) { // If the region is a global and we are invalidating all globals, // just erase the entry. This causes all globals to be lazily // symbolicated from the same base symbol. - B = RM.removeBinding(B, baseR); + B = B.removeBinding(baseR); return; } @@ -812,15 +1045,16 @@ void invalidateRegionsWorker::VisitBaseRegion(const MemRegion *baseR) { DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, T,Count); assert(SymbolManager::canSymbolicate(T) || V.isUnknown()); - B = RM.addBinding(B, baseR, BindingKey::Direct, V); + B = B.addBinding(baseR, BindingKey::Direct, V); } -RegionBindings RegionStoreManager::invalidateGlobalRegion(MemRegion::Kind K, - const Expr *Ex, - unsigned Count, - const LocationContext *LCtx, - RegionBindings B, - InvalidatedRegions *Invalidated) { +RegionBindingsRef +RegionStoreManager::invalidateGlobalRegion(MemRegion::Kind K, + const Expr *Ex, + unsigned Count, + const LocationContext *LCtx, + RegionBindingsRef B, + InvalidatedRegions *Invalidated) { // Bind the globals memory space to a new symbol that we will use to derive // the bindings for all globals. const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion(K); @@ -828,8 +1062,8 @@ RegionBindings RegionStoreManager::invalidateGlobalRegion(MemRegion::Kind K, /* type does not matter */ Ctx.IntTy, Count); - B = removeBinding(B, GS); - B = addBinding(B, BindingKey::Make(GS, BindingKey::Default), V); + B = B.removeBinding(GS) + .addBinding(BindingKey::Make(GS, BindingKey::Default), V); // Even if there are no bindings in the global scope, we still need to // record that we touched it. @@ -839,47 +1073,82 @@ RegionBindings RegionStoreManager::invalidateGlobalRegion(MemRegion::Kind K, return B; } -StoreRef RegionStoreManager::invalidateRegions(Store store, - ArrayRef<const MemRegion *> Regions, - const Expr *Ex, unsigned Count, - const LocationContext *LCtx, - InvalidatedSymbols &IS, - const CallEvent *Call, - InvalidatedRegions *Invalidated) { - invalidateRegionsWorker W(*this, StateMgr, - RegionStoreManager::GetRegionBindings(store), - Ex, Count, LCtx, IS, Invalidated, false); +void RegionStoreManager::populateWorkList(invalidateRegionsWorker &W, + ArrayRef<SVal> Values, + bool IsArrayOfConstRegions, + InvalidatedRegions *TopLevelRegions) { + for (ArrayRef<SVal>::iterator I = Values.begin(), + E = Values.end(); I != E; ++I) { + SVal V = *I; + if (Optional<nonloc::LazyCompoundVal> LCS = + V.getAs<nonloc::LazyCompoundVal>()) { + + const SValListTy &Vals = getInterestingValues(*LCS); + + for (SValListTy::const_iterator I = Vals.begin(), + E = Vals.end(); I != E; ++I) { + // Note: the last argument is false here because these are + // non-top-level regions. + if (const MemRegion *R = (*I).getAsRegion()) + W.AddToWorkList(R, /*IsConst=*/ false); + } + continue; + } + + if (const MemRegion *R = V.getAsRegion()) { + if (TopLevelRegions) + TopLevelRegions->push_back(R); + W.AddToWorkList(R, /*IsConst=*/ IsArrayOfConstRegions); + continue; + } + } +} + +StoreRef +RegionStoreManager::invalidateRegions(Store store, + ArrayRef<SVal> Values, + ArrayRef<SVal> ConstValues, + const Expr *Ex, unsigned Count, + const LocationContext *LCtx, + const CallEvent *Call, + InvalidatedSymbols &IS, + InvalidatedSymbols &ConstIS, + InvalidatedRegions *TopLevelRegions, + InvalidatedRegions *TopLevelConstRegions, + InvalidatedRegions *Invalidated) { + RegionBindingsRef B = RegionStoreManager::getRegionBindings(store); + invalidateRegionsWorker W(*this, StateMgr, B, Ex, Count, LCtx, IS, ConstIS, + Invalidated, false); // Scan the bindings and generate the clusters. W.GenerateClusters(); // Add the regions to the worklist. - for (ArrayRef<const MemRegion *>::iterator - I = Regions.begin(), E = Regions.end(); I != E; ++I) - W.AddToWorkList(*I); + populateWorkList(W, Values, /*IsArrayOfConstRegions*/ false, + TopLevelRegions); + populateWorkList(W, ConstValues, /*IsArrayOfConstRegions*/ true, + TopLevelConstRegions); W.RunWorkList(); // Return the new bindings. - RegionBindings B = W.getRegionBindings(); + B = W.getRegionBindings(); - // For all globals which are not static nor immutable: determine which global - // regions should be invalidated and invalidate them. + // For calls, determine which global regions should be invalidated and + // invalidate them. (Note that function-static and immutable globals are never + // invalidated by this.) // TODO: This could possibly be more precise with modules. - // - // System calls invalidate only system globals. - if (Call && Call->isInSystemHeader()) { + if (Call) { B = invalidateGlobalRegion(MemRegion::GlobalSystemSpaceRegionKind, Ex, Count, LCtx, B, Invalidated); - // Internal calls might invalidate both system and internal globals. - } else { - B = invalidateGlobalRegion(MemRegion::GlobalSystemSpaceRegionKind, - Ex, Count, LCtx, B, Invalidated); - B = invalidateGlobalRegion(MemRegion::GlobalInternalSpaceRegionKind, - Ex, Count, LCtx, B, Invalidated); + + if (!Call->isInSystemHeader()) { + B = invalidateGlobalRegion(MemRegion::GlobalInternalSpaceRegionKind, + Ex, Count, LCtx, B, Invalidated); + } } - return StoreRef(B.getRootWithoutRetain(), *this); + return StoreRef(B.asStore(), *this); } //===----------------------------------------------------------------------===// @@ -923,10 +1192,10 @@ RegionStoreManager::getSizeInElements(ProgramStateRef state, /// the array). This is called by ExprEngine when evaluating casts /// from arrays to pointers. SVal RegionStoreManager::ArrayToPointer(Loc Array) { - if (!isa<loc::MemRegionVal>(Array)) + if (!Array.getAs<loc::MemRegionVal>()) return UnknownVal(); - const MemRegion* R = cast<loc::MemRegionVal>(&Array)->getRegion(); + const MemRegion* R = Array.castAs<loc::MemRegionVal>().getRegion(); const TypedValueRegion* ArrayR = dyn_cast<TypedValueRegion>(R); if (!ArrayR) @@ -945,31 +1214,9 @@ SVal RegionStoreManager::ArrayToPointer(Loc Array) { // Loading values from regions. //===----------------------------------------------------------------------===// -Optional<SVal> RegionStoreManager::getDirectBinding(RegionBindings B, - const MemRegion *R) { - - if (const SVal *V = lookup(B, R, BindingKey::Direct)) - return *V; - - return Optional<SVal>(); -} - -Optional<SVal> RegionStoreManager::getDefaultBinding(RegionBindings B, - const MemRegion *R) { - if (R->isBoundable()) - if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) - if (TR->getValueType()->isUnionType()) - return UnknownVal(); - - if (const SVal *V = lookup(B, R, BindingKey::Default)) - return *V; - - return Optional<SVal>(); -} - -SVal RegionStoreManager::getBinding(Store store, Loc L, QualType T) { - assert(!isa<UnknownVal>(L) && "location unknown"); - assert(!isa<UndefinedVal>(L) && "location undefined"); +SVal RegionStoreManager::getBinding(RegionBindingsConstRef B, Loc L, QualType T) { + assert(!L.getAs<UnknownVal>() && "location unknown"); + assert(!L.getAs<UndefinedVal>() && "location undefined"); // For access to concrete addresses, return UnknownVal. Checks // for null dereferences (and similar errors) are done by checkers, not @@ -977,14 +1224,14 @@ SVal RegionStoreManager::getBinding(Store store, Loc L, QualType T) { // FIXME: We can consider lazily symbolicating such memory, but we really // should defer this when we can reason easily about symbolicating arrays // of bytes. - if (isa<loc::ConcreteInt>(L)) { + if (L.getAs<loc::ConcreteInt>()) { return UnknownVal(); } - if (!isa<loc::MemRegionVal>(L)) { + if (!L.getAs<loc::MemRegionVal>()) { return UnknownVal(); } - const MemRegion *MR = cast<loc::MemRegionVal>(L).getRegion(); + const MemRegion *MR = L.castAs<loc::MemRegionVal>().getRegion(); if (isa<AllocaRegion>(MR) || isa<SymbolicRegion>(MR) || @@ -1005,6 +1252,11 @@ SVal RegionStoreManager::getBinding(Store store, Loc L, QualType T) { const TypedValueRegion *R = cast<TypedValueRegion>(MR); QualType RTy = R->getValueType(); + // FIXME: we do not yet model the parts of a complex type, so treat the + // whole thing as "unknown". + if (RTy->isAnyComplexType()) + return UnknownVal(); + // FIXME: We should eventually handle funny addressing. e.g.: // // int x = ...; @@ -1013,9 +1265,8 @@ SVal RegionStoreManager::getBinding(Store store, Loc L, QualType T) { // char c = *q; // returns the first byte of 'x'. // // Such funny addressing will occur due to layering of regions. - if (RTy->isStructureOrClassType()) - return getBindingForStruct(store, R); + return getBindingForStruct(B, R); // FIXME: Handle unions. if (RTy->isUnionType()) @@ -1023,7 +1274,7 @@ SVal RegionStoreManager::getBinding(Store store, Loc L, QualType T) { if (RTy->isArrayType()) { if (RTy->isConstantArrayType()) - return getBindingForArray(store, R); + return getBindingForArray(B, R); else return UnknownVal(); } @@ -1033,7 +1284,7 @@ SVal RegionStoreManager::getBinding(Store store, Loc L, QualType T) { return UnknownVal(); if (const FieldRegion* FR = dyn_cast<FieldRegion>(R)) - return CastRetrievedVal(getBindingForField(store, FR), FR, T, false); + return CastRetrievedVal(getBindingForField(B, FR), FR, T, false); if (const ElementRegion* ER = dyn_cast<ElementRegion>(R)) { // FIXME: Here we actually perform an implicit conversion from the loaded @@ -1041,7 +1292,7 @@ SVal RegionStoreManager::getBinding(Store store, Loc L, QualType T) { // more intelligently. For example, an 'element' can encompass multiple // bound regions (e.g., several bound bytes), or could be a subset of // a larger value. - return CastRetrievedVal(getBindingForElement(store, ER), ER, T, false); + return CastRetrievedVal(getBindingForElement(B, ER), ER, T, false); } if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) { @@ -1051,7 +1302,7 @@ SVal RegionStoreManager::getBinding(Store store, Loc L, QualType T) { // reinterpretted, it is possible we stored a different value that could // fit within the ivar. Either we need to cast these when storing them // or reinterpret them lazily (as we do here). - return CastRetrievedVal(getBindingForObjCIvar(store, IVR), IVR, T, false); + return CastRetrievedVal(getBindingForObjCIvar(B, IVR), IVR, T, false); } if (const VarRegion *VR = dyn_cast<VarRegion>(R)) { @@ -1061,11 +1312,10 @@ SVal RegionStoreManager::getBinding(Store store, Loc L, QualType T) { // variable is reinterpretted, it is possible we stored a different value // that could fit within the variable. Either we need to cast these when // storing them or reinterpret them lazily (as we do here). - return CastRetrievedVal(getBindingForVar(store, VR), VR, T, false); + return CastRetrievedVal(getBindingForVar(B, VR), VR, T, false); } - RegionBindings B = GetRegionBindings(store); - const SVal *V = lookup(B, R, BindingKey::Direct); + const SVal *V = B.lookup(R, BindingKey::Direct); // Check if the region has a binding. if (V) @@ -1086,69 +1336,109 @@ SVal RegionStoreManager::getBinding(Store store, Loc L, QualType T) { return svalBuilder.getRegionValueSymbolVal(R); } -std::pair<Store, const MemRegion *> -RegionStoreManager::GetLazyBinding(RegionBindings B, const MemRegion *R, - const MemRegion *originalRegion, - bool includeSuffix) { - +static QualType getUnderlyingType(const SubRegion *R) { + QualType RegionTy; + if (const TypedValueRegion *TVR = dyn_cast<TypedValueRegion>(R)) + RegionTy = TVR->getValueType(); + + if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) + RegionTy = SR->getSymbol()->getType(); + + return RegionTy; +} + +/// Checks to see if store \p B has a lazy binding for region \p R. +/// +/// If \p AllowSubregionBindings is \c false, a lazy binding will be rejected +/// if there are additional bindings within \p R. +/// +/// Note that unlike RegionStoreManager::findLazyBinding, this will not search +/// for lazy bindings for super-regions of \p R. +static Optional<nonloc::LazyCompoundVal> +getExistingLazyBinding(SValBuilder &SVB, RegionBindingsConstRef B, + const SubRegion *R, bool AllowSubregionBindings) { + Optional<SVal> V = B.getDefaultBinding(R); + if (!V) + return None; + + Optional<nonloc::LazyCompoundVal> LCV = V->getAs<nonloc::LazyCompoundVal>(); + if (!LCV) + return None; + + // If the LCV is for a subregion, the types might not match, and we shouldn't + // reuse the binding. + QualType RegionTy = getUnderlyingType(R); + if (!RegionTy.isNull() && + !RegionTy->isVoidPointerType()) { + QualType SourceRegionTy = LCV->getRegion()->getValueType(); + if (!SVB.getContext().hasSameUnqualifiedType(RegionTy, SourceRegionTy)) + return None; + } + + if (!AllowSubregionBindings) { + // If there are any other bindings within this region, we shouldn't reuse + // the top-level binding. + SmallVector<BindingPair, 16> Bindings; + collectSubRegionBindings(Bindings, SVB, *B.lookup(R->getBaseRegion()), R, + /*IncludeAllDefaultBindings=*/true); + if (Bindings.size() > 1) + return None; + } + + return *LCV; +} + + +std::pair<Store, const SubRegion *> +RegionStoreManager::findLazyBinding(RegionBindingsConstRef B, + const SubRegion *R, + const SubRegion *originalRegion) { if (originalRegion != R) { - if (Optional<SVal> OV = getDefaultBinding(B, R)) { - if (const nonloc::LazyCompoundVal *V = - dyn_cast<nonloc::LazyCompoundVal>(OV.getPointer())) - return std::make_pair(V->getStore(), V->getRegion()); - } + if (Optional<nonloc::LazyCompoundVal> V = + getExistingLazyBinding(svalBuilder, B, R, true)) + return std::make_pair(V->getStore(), V->getRegion()); } - + + typedef std::pair<Store, const SubRegion *> StoreRegionPair; + StoreRegionPair Result = StoreRegionPair(); + if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) { - const std::pair<Store, const MemRegion *> &X = - GetLazyBinding(B, ER->getSuperRegion(), originalRegion); - - if (X.second) - return std::make_pair(X.first, - MRMgr.getElementRegionWithSuper(ER, X.second)); - } - else if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) { - const std::pair<Store, const MemRegion *> &X = - GetLazyBinding(B, FR->getSuperRegion(), originalRegion); - - if (X.second) { - if (includeSuffix) - return std::make_pair(X.first, - MRMgr.getFieldRegionWithSuper(FR, X.second)); - return X; - } - - } - // C++ base object region is another kind of region that we should blast - // through to look for lazy compound value. It is like a field region. - else if (const CXXBaseObjectRegion *baseReg = - dyn_cast<CXXBaseObjectRegion>(R)) { - const std::pair<Store, const MemRegion *> &X = - GetLazyBinding(B, baseReg->getSuperRegion(), originalRegion); + Result = findLazyBinding(B, cast<SubRegion>(ER->getSuperRegion()), + originalRegion); + + if (Result.second) + Result.second = MRMgr.getElementRegionWithSuper(ER, Result.second); + + } else if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) { + Result = findLazyBinding(B, cast<SubRegion>(FR->getSuperRegion()), + originalRegion); + + if (Result.second) + Result.second = MRMgr.getFieldRegionWithSuper(FR, Result.second); + + } else if (const CXXBaseObjectRegion *BaseReg = + dyn_cast<CXXBaseObjectRegion>(R)) { + // C++ base object region is another kind of region that we should blast + // through to look for lazy compound value. It is like a field region. + Result = findLazyBinding(B, cast<SubRegion>(BaseReg->getSuperRegion()), + originalRegion); - if (X.second) { - if (includeSuffix) - return std::make_pair(X.first, - MRMgr.getCXXBaseObjectRegionWithSuper(baseReg, - X.second)); - return X; - } + if (Result.second) + Result.second = MRMgr.getCXXBaseObjectRegionWithSuper(BaseReg, + Result.second); } - // The NULL MemRegion indicates an non-existent lazy binding. A NULL Store is - // possible for a valid lazy binding. - return std::make_pair((Store) 0, (const MemRegion *) 0); + return Result; } -SVal RegionStoreManager::getBindingForElement(Store store, +SVal RegionStoreManager::getBindingForElement(RegionBindingsConstRef B, const ElementRegion* R) { // We do not currently model bindings of the CompoundLiteralregion. if (isa<CompoundLiteralRegion>(R->getBaseRegion())) return UnknownVal(); // Check if the region has a binding. - RegionBindings B = GetRegionBindings(store); - if (const Optional<SVal> &V = getDirectBinding(B, R)) + if (const Optional<SVal> &V = B.getDirectBinding(R)) return *V; const MemRegion* superR = R->getSuperRegion(); @@ -1163,7 +1453,7 @@ SVal RegionStoreManager::getBindingForElement(Store store, const StringLiteral *Str = StrR->getStringLiteral(); SVal Idx = R->getIndex(); - if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&Idx)) { + if (Optional<nonloc::ConcreteInt> CI = Idx.getAs<nonloc::ConcreteInt>()) { int64_t i = CI->getValue().getSExtValue(); // Abort on string underrun. This can be possible by arbitrary // clients of getBindingForElement(). @@ -1202,7 +1492,7 @@ SVal RegionStoreManager::getBindingForElement(Store store, QualType elemT = R->getElementType(); if (elemT->isScalarType()) { if (Ctx.getTypeSizeInChars(baseT) >= Ctx.getTypeSizeInChars(elemT)) { - if (const Optional<SVal> &V = getDirectBinding(B, superR)) { + if (const Optional<SVal> &V = B.getDirectBinding(superR)) { if (SymbolRef parentSym = V->getAsSymbol()) return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); @@ -1216,29 +1506,27 @@ SVal RegionStoreManager::getBindingForElement(Store store, } } } - return getBindingForFieldOrElementCommon(store, R, R->getElementType(), - superR); + return getBindingForFieldOrElementCommon(B, R, R->getElementType(),superR); } -SVal RegionStoreManager::getBindingForField(Store store, - const FieldRegion* R) { +SVal RegionStoreManager::getBindingForField(RegionBindingsConstRef B, + const FieldRegion* R) { // Check if the region has a binding. - RegionBindings B = GetRegionBindings(store); - if (const Optional<SVal> &V = getDirectBinding(B, R)) + if (const Optional<SVal> &V = B.getDirectBinding(R)) return *V; QualType Ty = R->getValueType(); - return getBindingForFieldOrElementCommon(store, R, Ty, R->getSuperRegion()); + return getBindingForFieldOrElementCommon(B, R, Ty, R->getSuperRegion()); } Optional<SVal> -RegionStoreManager::getBindingForDerivedDefaultValue(RegionBindings B, +RegionStoreManager::getBindingForDerivedDefaultValue(RegionBindingsConstRef B, const MemRegion *superR, const TypedValueRegion *R, QualType Ty) { - if (const Optional<SVal> &D = getDefaultBinding(B, superR)) { + if (const Optional<SVal> &D = B.getDefaultBinding(superR)) { const SVal &val = D.getValue(); if (SymbolRef parentSym = val.getAsSymbol()) return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); @@ -1249,53 +1537,95 @@ RegionStoreManager::getBindingForDerivedDefaultValue(RegionBindings B, if (val.isUnknownOrUndef()) return val; - // Lazy bindings are handled later. - if (isa<nonloc::LazyCompoundVal>(val)) - return Optional<SVal>(); + // Lazy bindings are usually handled through getExistingLazyBinding(). + // We should unify these two code paths at some point. + if (val.getAs<nonloc::LazyCompoundVal>()) + return val; llvm_unreachable("Unknown default value"); } - return Optional<SVal>(); + return None; } -SVal RegionStoreManager::getLazyBinding(const MemRegion *lazyBindingRegion, - Store lazyBindingStore) { - if (const ElementRegion *ER = dyn_cast<ElementRegion>(lazyBindingRegion)) - return getBindingForElement(lazyBindingStore, ER); - - return getBindingForField(lazyBindingStore, - cast<FieldRegion>(lazyBindingRegion)); +SVal RegionStoreManager::getLazyBinding(const SubRegion *LazyBindingRegion, + RegionBindingsRef LazyBinding) { + SVal Result; + if (const ElementRegion *ER = dyn_cast<ElementRegion>(LazyBindingRegion)) + Result = getBindingForElement(LazyBinding, ER); + else + Result = getBindingForField(LazyBinding, + cast<FieldRegion>(LazyBindingRegion)); + + // FIXME: This is a hack to deal with RegionStore's inability to distinguish a + // default value for /part/ of an aggregate from a default value for the + // /entire/ aggregate. The most common case of this is when struct Outer + // has as its first member a struct Inner, which is copied in from a stack + // variable. In this case, even if the Outer's default value is symbolic, 0, + // or unknown, it gets overridden by the Inner's default value of undefined. + // + // This is a general problem -- if the Inner is zero-initialized, the Outer + // will now look zero-initialized. The proper way to solve this is with a + // new version of RegionStore that tracks the extent of a binding as well + // as the offset. + // + // This hack only takes care of the undefined case because that can very + // quickly result in a warning. + if (Result.isUndef()) + Result = UnknownVal(); + + return Result; } -SVal RegionStoreManager::getBindingForFieldOrElementCommon(Store store, +SVal +RegionStoreManager::getBindingForFieldOrElementCommon(RegionBindingsConstRef B, const TypedValueRegion *R, QualType Ty, const MemRegion *superR) { // At this point we have already checked in either getBindingForElement or // getBindingForField if 'R' has a direct binding. - RegionBindings B = GetRegionBindings(store); // Lazy binding? Store lazyBindingStore = NULL; - const MemRegion *lazyBindingRegion = NULL; - llvm::tie(lazyBindingStore, lazyBindingRegion) = GetLazyBinding(B, R, R, - true); - + const SubRegion *lazyBindingRegion = NULL; + llvm::tie(lazyBindingStore, lazyBindingRegion) = findLazyBinding(B, R, R); if (lazyBindingRegion) - return getLazyBinding(lazyBindingRegion, lazyBindingStore); + return getLazyBinding(lazyBindingRegion, + getRegionBindings(lazyBindingStore)); // Record whether or not we see a symbolic index. That can completely // be out of scope of our lookup. bool hasSymbolicIndex = false; - while (superR) { - if (const Optional<SVal> &D = - getBindingForDerivedDefaultValue(B, superR, R, Ty)) + // FIXME: This is a hack to deal with RegionStore's inability to distinguish a + // default value for /part/ of an aggregate from a default value for the + // /entire/ aggregate. The most common case of this is when struct Outer + // has as its first member a struct Inner, which is copied in from a stack + // variable. In this case, even if the Outer's default value is symbolic, 0, + // or unknown, it gets overridden by the Inner's default value of undefined. + // + // This is a general problem -- if the Inner is zero-initialized, the Outer + // will now look zero-initialized. The proper way to solve this is with a + // new version of RegionStore that tracks the extent of a binding as well + // as the offset. + // + // This hack only takes care of the undefined case because that can very + // quickly result in a warning. + bool hasPartialLazyBinding = false; + + const SubRegion *Base = dyn_cast<SubRegion>(superR); + while (Base) { + if (Optional<SVal> D = getBindingForDerivedDefaultValue(B, Base, R, Ty)) { + if (D->getAs<nonloc::LazyCompoundVal>()) { + hasPartialLazyBinding = true; + break; + } + return *D; + } - if (const ElementRegion *ER = dyn_cast<ElementRegion>(superR)) { + if (const ElementRegion *ER = dyn_cast<ElementRegion>(Base)) { NonLoc index = ER->getIndex(); if (!index.isConstant()) hasSymbolicIndex = true; @@ -1303,11 +1633,7 @@ SVal RegionStoreManager::getBindingForFieldOrElementCommon(Store store, // If our super region is a field or element itself, walk up the region // hierarchy to see if there is a default value installed in an ancestor. - if (const SubRegion *SR = dyn_cast<SubRegion>(superR)) { - superR = SR->getSuperRegion(); - continue; - } - break; + Base = dyn_cast<SubRegion>(Base->getSuperRegion()); } if (R->hasStackNonParametersStorage()) { @@ -1327,27 +1653,25 @@ SVal RegionStoreManager::getBindingForFieldOrElementCommon(Store store, // a symbolic offset. if (hasSymbolicIndex) return UnknownVal(); - - return UndefinedVal(); + + if (!hasPartialLazyBinding) + return UndefinedVal(); } // All other values are symbolic. return svalBuilder.getRegionValueSymbolVal(R); } -SVal RegionStoreManager::getBindingForObjCIvar(Store store, +SVal RegionStoreManager::getBindingForObjCIvar(RegionBindingsConstRef B, const ObjCIvarRegion* R) { - - // Check if the region has a binding. - RegionBindings B = GetRegionBindings(store); - - if (const Optional<SVal> &V = getDirectBinding(B, R)) + // Check if the region has a binding. + if (const Optional<SVal> &V = B.getDirectBinding(R)) return *V; const MemRegion *superR = R->getSuperRegion(); // Check if the super region has a default binding. - if (const Optional<SVal> &V = getDefaultBinding(B, superR)) { + if (const Optional<SVal> &V = B.getDefaultBinding(superR)) { if (SymbolRef parentSym = V->getAsSymbol()) return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); @@ -1358,51 +1682,64 @@ SVal RegionStoreManager::getBindingForObjCIvar(Store store, return getBindingForLazySymbol(R); } -SVal RegionStoreManager::getBindingForVar(Store store, const VarRegion *R) { +static Optional<SVal> getConstValue(SValBuilder &SVB, const VarDecl *VD) { + ASTContext &Ctx = SVB.getContext(); + if (!VD->getType().isConstQualified()) + return None; - // Check if the region has a binding. - RegionBindings B = GetRegionBindings(store); + const Expr *Init = VD->getInit(); + if (!Init) + return None; + + llvm::APSInt Result; + if (!Init->isGLValue() && Init->EvaluateAsInt(Result, Ctx)) + return SVB.makeIntVal(Result); + + if (Init->isNullPointerConstant(Ctx, Expr::NPC_ValueDependentIsNotNull)) + return SVB.makeNull(); - if (const Optional<SVal> &V = getDirectBinding(B, R)) + // FIXME: Handle other possible constant expressions. + return None; +} + +SVal RegionStoreManager::getBindingForVar(RegionBindingsConstRef B, + const VarRegion *R) { + + // Check if the region has a binding. + if (const Optional<SVal> &V = B.getDirectBinding(R)) return *V; // Lazily derive a value for the VarRegion. const VarDecl *VD = R->getDecl(); - QualType T = VD->getType(); const MemSpaceRegion *MS = R->getMemorySpace(); - if (isa<UnknownSpaceRegion>(MS) || - isa<StackArgumentsSpaceRegion>(MS)) + // Arguments are always symbolic. + if (isa<StackArgumentsSpaceRegion>(MS)) + return svalBuilder.getRegionValueSymbolVal(R); + + // Is 'VD' declared constant? If so, retrieve the constant value. + if (Optional<SVal> V = getConstValue(svalBuilder, VD)) + return *V; + + // This must come after the check for constants because closure-captured + // constant variables may appear in UnknownSpaceRegion. + if (isa<UnknownSpaceRegion>(MS)) return svalBuilder.getRegionValueSymbolVal(R); if (isa<GlobalsSpaceRegion>(MS)) { - if (isa<NonStaticGlobalSpaceRegion>(MS)) { - // Is 'VD' declared constant? If so, retrieve the constant value. - QualType CT = Ctx.getCanonicalType(T); - if (CT.isConstQualified()) { - const Expr *Init = VD->getInit(); - // Do the null check first, as we want to call 'IgnoreParenCasts'. - if (Init) - if (const IntegerLiteral *IL = - dyn_cast<IntegerLiteral>(Init->IgnoreParenCasts())) { - const nonloc::ConcreteInt &V = svalBuilder.makeIntVal(IL); - return svalBuilder.evalCast(V, Init->getType(), IL->getType()); - } - } + QualType T = VD->getType(); - if (const Optional<SVal> &V - = getBindingForDerivedDefaultValue(B, MS, R, CT)) - return V.getValue(); + // Function-scoped static variables are default-initialized to 0; if they + // have an initializer, it would have been processed by now. + if (isa<StaticGlobalSpaceRegion>(MS)) + return svalBuilder.makeZeroVal(T); - return svalBuilder.getRegionValueSymbolVal(R); + if (Optional<SVal> V = getBindingForDerivedDefaultValue(B, MS, R, T)) { + assert(!V->getAs<nonloc::LazyCompoundVal>()); + return V.getValue(); } - if (T->isIntegerType()) - return svalBuilder.makeIntVal(0, T); - if (T->isPointerType()) - return svalBuilder.makeNull(); - - return UnknownVal(); + return svalBuilder.getRegionValueSymbolVal(R); } return UndefinedVal(); @@ -1413,55 +1750,77 @@ SVal RegionStoreManager::getBindingForLazySymbol(const TypedValueRegion *R) { return svalBuilder.getRegionValueSymbolVal(R); } -static bool mayHaveLazyBinding(QualType Ty) { - return Ty->isArrayType() || Ty->isStructureOrClassType(); +const RegionStoreManager::SValListTy & +RegionStoreManager::getInterestingValues(nonloc::LazyCompoundVal LCV) { + // First, check the cache. + LazyBindingsMapTy::iterator I = LazyBindingsMap.find(LCV.getCVData()); + if (I != LazyBindingsMap.end()) + return I->second; + + // If we don't have a list of values cached, start constructing it. + SValListTy List; + + const SubRegion *LazyR = LCV.getRegion(); + RegionBindingsRef B = getRegionBindings(LCV.getStore()); + + // If this region had /no/ bindings at the time, there are no interesting + // values to return. + const ClusterBindings *Cluster = B.lookup(LazyR->getBaseRegion()); + if (!Cluster) + return (LazyBindingsMap[LCV.getCVData()] = llvm_move(List)); + + SmallVector<BindingPair, 32> Bindings; + collectSubRegionBindings(Bindings, svalBuilder, *Cluster, LazyR, + /*IncludeAllDefaultBindings=*/true); + for (SmallVectorImpl<BindingPair>::const_iterator I = Bindings.begin(), + E = Bindings.end(); + I != E; ++I) { + SVal V = I->second; + if (V.isUnknownOrUndef() || V.isConstant()) + continue; + + if (Optional<nonloc::LazyCompoundVal> InnerLCV = + V.getAs<nonloc::LazyCompoundVal>()) { + const SValListTy &InnerList = getInterestingValues(*InnerLCV); + List.insert(List.end(), InnerList.begin(), InnerList.end()); + continue; + } + + List.push_back(V); + } + + return (LazyBindingsMap[LCV.getCVData()] = llvm_move(List)); +} + +NonLoc RegionStoreManager::createLazyBinding(RegionBindingsConstRef B, + const TypedValueRegion *R) { + if (Optional<nonloc::LazyCompoundVal> V = + getExistingLazyBinding(svalBuilder, B, R, false)) + return *V; + + return svalBuilder.makeLazyCompoundVal(StoreRef(B.asStore(), *this), R); } -SVal RegionStoreManager::getBindingForStruct(Store store, - const TypedValueRegion* R) { +SVal RegionStoreManager::getBindingForStruct(RegionBindingsConstRef B, + const TypedValueRegion *R) { const RecordDecl *RD = R->getValueType()->castAs<RecordType>()->getDecl(); if (RD->field_empty()) return UnknownVal(); - // If we already have a lazy binding, don't create a new one, - // unless the first field might have a lazy binding of its own. - // (Right now we can't tell the difference.) - QualType FirstFieldType = RD->field_begin()->getType(); - if (!mayHaveLazyBinding(FirstFieldType)) { - RegionBindings B = GetRegionBindings(store); - BindingKey K = BindingKey::Make(R, BindingKey::Default); - if (const nonloc::LazyCompoundVal *V = - dyn_cast_or_null<nonloc::LazyCompoundVal>(lookup(B, K))) { - return *V; - } - } - - return svalBuilder.makeLazyCompoundVal(StoreRef(store, *this), R); + return createLazyBinding(B, R); } -SVal RegionStoreManager::getBindingForArray(Store store, - const TypedValueRegion * R) { - const ConstantArrayType *Ty = Ctx.getAsConstantArrayType(R->getValueType()); - assert(Ty && "Only constant array types can have compound bindings."); +SVal RegionStoreManager::getBindingForArray(RegionBindingsConstRef B, + const TypedValueRegion *R) { + assert(Ctx.getAsConstantArrayType(R->getValueType()) && + "Only constant array types can have compound bindings."); - // If we already have a lazy binding, don't create a new one, - // unless the first element might have a lazy binding of its own. - // (Right now we can't tell the difference.) - if (!mayHaveLazyBinding(Ty->getElementType())) { - RegionBindings B = GetRegionBindings(store); - BindingKey K = BindingKey::Make(R, BindingKey::Default); - if (const nonloc::LazyCompoundVal *V = - dyn_cast_or_null<nonloc::LazyCompoundVal>(lookup(B, K))) { - return *V; - } - } - - return svalBuilder.makeLazyCompoundVal(StoreRef(store, *this), R); + return createLazyBinding(B, R); } bool RegionStoreManager::includedInBindings(Store store, const MemRegion *region) const { - RegionBindings B = GetRegionBindings(store); + RegionBindingsRef B = getRegionBindings(store); region = region->getBaseRegion(); // Quick path: if the base is the head of a cluster, the region is live. @@ -1469,7 +1828,7 @@ bool RegionStoreManager::includedInBindings(Store store, return true; // Slow path: if the region is the VALUE of any binding, it is live. - for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI) { + for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI) { const ClusterBindings &Cluster = RI.getData(); for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); CI != CE; ++CI) { @@ -1488,31 +1847,33 @@ bool RegionStoreManager::includedInBindings(Store store, //===----------------------------------------------------------------------===// StoreRef RegionStoreManager::killBinding(Store ST, Loc L) { - if (isa<loc::MemRegionVal>(L)) - if (const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion()) - return StoreRef(removeBinding(GetRegionBindings(ST), - R).getRootWithoutRetain(), + if (Optional<loc::MemRegionVal> LV = L.getAs<loc::MemRegionVal>()) + if (const MemRegion* R = LV->getRegion()) + return StoreRef(getRegionBindings(ST).removeBinding(R) + .asImmutableMap() + .getRootWithoutRetain(), *this); return StoreRef(ST, *this); } -StoreRef RegionStoreManager::Bind(Store store, Loc L, SVal V) { - if (isa<loc::ConcreteInt>(L)) - return StoreRef(store, *this); +RegionBindingsRef +RegionStoreManager::bind(RegionBindingsConstRef B, Loc L, SVal V) { + if (L.getAs<loc::ConcreteInt>()) + return B; // If we get here, the location should be a region. - const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion(); + const MemRegion *R = L.castAs<loc::MemRegionVal>().getRegion(); // Check if the region is a struct region. if (const TypedValueRegion* TR = dyn_cast<TypedValueRegion>(R)) { QualType Ty = TR->getValueType(); if (Ty->isArrayType()) - return BindArray(store, TR, V); + return bindArray(B, TR, V); if (Ty->isStructureOrClassType()) - return BindStruct(store, TR, V); + return bindStruct(B, TR, V); if (Ty->isVectorType()) - return BindVector(store, TR, V); + return bindVector(B, TR, V); } if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) { @@ -1526,12 +1887,8 @@ StoreRef RegionStoreManager::Bind(Store store, Loc L, SVal V) { } // Clear out bindings that may overlap with this binding. - - // Perform the binding. - RegionBindings B = GetRegionBindings(store); - B = removeSubRegionBindings(B, cast<SubRegion>(R)); - BindingKey Key = BindingKey::Make(R, BindingKey::Direct); - return StoreRef(addBinding(B, Key, V).getRootWithoutRetain(), *this); + RegionBindingsRef NewB = removeSubRegionBindings(B, cast<SubRegion>(R)); + return NewB.addBinding(BindingKey::Make(R, BindingKey::Direct), V); } // FIXME: this method should be merged into Bind(). @@ -1542,10 +1899,10 @@ StoreRef RegionStoreManager::bindCompoundLiteral(Store ST, return Bind(ST, loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL, LC)), V); } -StoreRef RegionStoreManager::setImplicitDefaultValue(Store store, - const MemRegion *R, - QualType T) { - RegionBindings B = GetRegionBindings(store); +RegionBindingsRef +RegionStoreManager::setImplicitDefaultValue(RegionBindingsConstRef B, + const MemRegion *R, + QualType T) { SVal V; if (Loc::isLocType(T)) @@ -1566,12 +1923,13 @@ StoreRef RegionStoreManager::setImplicitDefaultValue(Store store, V = UnknownVal(); } - return StoreRef(addBinding(B, R, BindingKey::Default, - V).getRootWithoutRetain(), *this); + return B.addBinding(R, BindingKey::Default, V); } -StoreRef RegionStoreManager::BindArray(Store store, const TypedValueRegion* R, - SVal Init) { +RegionBindingsRef +RegionStoreManager::bindArray(RegionBindingsConstRef B, + const TypedValueRegion* R, + SVal Init) { const ArrayType *AT =cast<ArrayType>(Ctx.getCanonicalType(R->getValueType())); QualType ElementTy = AT->getElementType(); @@ -1581,30 +1939,31 @@ StoreRef RegionStoreManager::BindArray(Store store, const TypedValueRegion* R, Size = CAT->getSize().getZExtValue(); // Check if the init expr is a string literal. - if (loc::MemRegionVal *MRV = dyn_cast<loc::MemRegionVal>(&Init)) { + if (Optional<loc::MemRegionVal> MRV = Init.getAs<loc::MemRegionVal>()) { const StringRegion *S = cast<StringRegion>(MRV->getRegion()); // Treat the string as a lazy compound value. - nonloc::LazyCompoundVal LCV = - cast<nonloc::LazyCompoundVal>(svalBuilder. - makeLazyCompoundVal(StoreRef(store, *this), S)); - return BindAggregate(store, R, LCV); + StoreRef store(B.asStore(), *this); + nonloc::LazyCompoundVal LCV = svalBuilder.makeLazyCompoundVal(store, S) + .castAs<nonloc::LazyCompoundVal>(); + return bindAggregate(B, R, LCV); } // Handle lazy compound values. - if (isa<nonloc::LazyCompoundVal>(Init)) - return BindAggregate(store, R, Init); + if (Init.getAs<nonloc::LazyCompoundVal>()) + return bindAggregate(B, R, Init); // Remaining case: explicit compound values. if (Init.isUnknown()) - return setImplicitDefaultValue(store, R, ElementTy); + return setImplicitDefaultValue(B, R, ElementTy); - nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(Init); + const nonloc::CompoundVal& CV = Init.castAs<nonloc::CompoundVal>(); nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); uint64_t i = 0; - StoreRef newStore(store, *this); + RegionBindingsRef NewB(B); + for (; Size.hasValue() ? i < Size.getValue() : true ; ++i, ++VI) { // The init list might be shorter than the array length. if (VI == VE) @@ -1614,44 +1973,45 @@ StoreRef RegionStoreManager::BindArray(Store store, const TypedValueRegion* R, const ElementRegion *ER = MRMgr.getElementRegion(ElementTy, Idx, R, Ctx); if (ElementTy->isStructureOrClassType()) - newStore = BindStruct(newStore.getStore(), ER, *VI); + NewB = bindStruct(NewB, ER, *VI); else if (ElementTy->isArrayType()) - newStore = BindArray(newStore.getStore(), ER, *VI); + NewB = bindArray(NewB, ER, *VI); else - newStore = Bind(newStore.getStore(), svalBuilder.makeLoc(ER), *VI); + NewB = bind(NewB, svalBuilder.makeLoc(ER), *VI); } // If the init list is shorter than the array length, set the // array default value. if (Size.hasValue() && i < Size.getValue()) - newStore = setImplicitDefaultValue(newStore.getStore(), R, ElementTy); + NewB = setImplicitDefaultValue(NewB, R, ElementTy); - return newStore; + return NewB; } -StoreRef RegionStoreManager::BindVector(Store store, const TypedValueRegion* R, - SVal V) { +RegionBindingsRef RegionStoreManager::bindVector(RegionBindingsConstRef B, + const TypedValueRegion* R, + SVal V) { QualType T = R->getValueType(); assert(T->isVectorType()); const VectorType *VT = T->getAs<VectorType>(); // Use getAs for typedefs. // Handle lazy compound values and symbolic values. - if (isa<nonloc::LazyCompoundVal>(V) || isa<nonloc::SymbolVal>(V)) - return BindAggregate(store, R, V); + if (V.getAs<nonloc::LazyCompoundVal>() || V.getAs<nonloc::SymbolVal>()) + return bindAggregate(B, R, V); // We may get non-CompoundVal accidentally due to imprecise cast logic or // that we are binding symbolic struct value. Kill the field values, and if // the value is symbolic go and bind it as a "default" binding. - if (!isa<nonloc::CompoundVal>(V)) { - return BindAggregate(store, R, UnknownVal()); + if (!V.getAs<nonloc::CompoundVal>()) { + return bindAggregate(B, R, UnknownVal()); } QualType ElemType = VT->getElementType(); - nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V); + nonloc::CompoundVal CV = V.castAs<nonloc::CompoundVal>(); nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); unsigned index = 0, numElements = VT->getNumElements(); - StoreRef newStore(store, *this); - + RegionBindingsRef NewB(B); + for ( ; index != numElements ; ++index) { if (VI == VE) break; @@ -1660,20 +2020,20 @@ StoreRef RegionStoreManager::BindVector(Store store, const TypedValueRegion* R, const ElementRegion *ER = MRMgr.getElementRegion(ElemType, Idx, R, Ctx); if (ElemType->isArrayType()) - newStore = BindArray(newStore.getStore(), ER, *VI); + NewB = bindArray(NewB, ER, *VI); else if (ElemType->isStructureOrClassType()) - newStore = BindStruct(newStore.getStore(), ER, *VI); + NewB = bindStruct(NewB, ER, *VI); else - newStore = Bind(newStore.getStore(), svalBuilder.makeLoc(ER), *VI); + NewB = bind(NewB, svalBuilder.makeLoc(ER), *VI); } - return newStore; + return NewB; } -StoreRef RegionStoreManager::BindStruct(Store store, const TypedValueRegion* R, - SVal V) { - +RegionBindingsRef RegionStoreManager::bindStruct(RegionBindingsConstRef B, + const TypedValueRegion* R, + SVal V) { if (!Features.supportsFields()) - return StoreRef(store, *this); + return B; QualType T = R->getValueType(); assert(T->isStructureOrClassType()); @@ -1682,24 +2042,24 @@ StoreRef RegionStoreManager::BindStruct(Store store, const TypedValueRegion* R, RecordDecl *RD = RT->getDecl(); if (!RD->isCompleteDefinition()) - return StoreRef(store, *this); + return B; // Handle lazy compound values and symbolic values. - if (isa<nonloc::LazyCompoundVal>(V) || isa<nonloc::SymbolVal>(V)) - return BindAggregate(store, R, V); + if (V.getAs<nonloc::LazyCompoundVal>() || V.getAs<nonloc::SymbolVal>()) + return bindAggregate(B, R, V); // We may get non-CompoundVal accidentally due to imprecise cast logic or // that we are binding symbolic struct value. Kill the field values, and if // the value is symbolic go and bind it as a "default" binding. - if (V.isUnknown() || !isa<nonloc::CompoundVal>(V)) - return BindAggregate(store, R, UnknownVal()); + if (V.isUnknown() || !V.getAs<nonloc::CompoundVal>()) + return bindAggregate(B, R, UnknownVal()); - nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V); + const nonloc::CompoundVal& CV = V.castAs<nonloc::CompoundVal>(); nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); RecordDecl::field_iterator FI, FE; - StoreRef newStore(store, *this); - + RegionBindingsRef NewB(B); + for (FI = RD->field_begin(), FE = RD->field_end(); FI != FE; ++FI) { if (VI == VE) @@ -1713,95 +2073,30 @@ StoreRef RegionStoreManager::BindStruct(Store store, const TypedValueRegion* R, const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R); if (FTy->isArrayType()) - newStore = BindArray(newStore.getStore(), FR, *VI); + NewB = bindArray(NewB, FR, *VI); else if (FTy->isStructureOrClassType()) - newStore = BindStruct(newStore.getStore(), FR, *VI); + NewB = bindStruct(NewB, FR, *VI); else - newStore = Bind(newStore.getStore(), svalBuilder.makeLoc(FR), *VI); + NewB = bind(NewB, svalBuilder.makeLoc(FR), *VI); ++VI; } // There may be fewer values in the initialize list than the fields of struct. if (FI != FE) { - RegionBindings B = GetRegionBindings(newStore.getStore()); - B = addBinding(B, R, BindingKey::Default, svalBuilder.makeIntVal(0, false)); - newStore = StoreRef(B.getRootWithoutRetain(), *this); + NewB = NewB.addBinding(R, BindingKey::Default, + svalBuilder.makeIntVal(0, false)); } - return newStore; + return NewB; } -StoreRef RegionStoreManager::BindAggregate(Store store, const TypedRegion *R, - SVal Val) { +RegionBindingsRef +RegionStoreManager::bindAggregate(RegionBindingsConstRef B, + const TypedRegion *R, + SVal Val) { // Remove the old bindings, using 'R' as the root of all regions // we will invalidate. Then add the new binding. - RegionBindings B = GetRegionBindings(store); - - B = removeSubRegionBindings(B, R); - B = addBinding(B, R, BindingKey::Default, Val); - - return StoreRef(B.getRootWithoutRetain(), *this); -} - -//===----------------------------------------------------------------------===// -// "Raw" retrievals and bindings. -//===----------------------------------------------------------------------===// - - -RegionBindings RegionStoreManager::addBinding(RegionBindings B, BindingKey K, - SVal V) { - const MemRegion *Base = K.getBaseRegion(); - - const ClusterBindings *ExistingCluster = B.lookup(Base); - ClusterBindings Cluster = (ExistingCluster ? *ExistingCluster - : CBFactory.getEmptyMap()); - - ClusterBindings NewCluster = CBFactory.add(Cluster, K, V); - return RBFactory.add(B, Base, NewCluster); -} - -RegionBindings RegionStoreManager::addBinding(RegionBindings B, - const MemRegion *R, - BindingKey::Kind k, SVal V) { - return addBinding(B, BindingKey::Make(R, k), V); -} - -const SVal *RegionStoreManager::lookup(RegionBindings B, BindingKey K) { - const ClusterBindings *Cluster = B.lookup(K.getBaseRegion()); - if (!Cluster) - return 0; - - return Cluster->lookup(K); -} - -const SVal *RegionStoreManager::lookup(RegionBindings B, - const MemRegion *R, - BindingKey::Kind k) { - return lookup(B, BindingKey::Make(R, k)); -} - -RegionBindings RegionStoreManager::removeBinding(RegionBindings B, - BindingKey K) { - const MemRegion *Base = K.getBaseRegion(); - const ClusterBindings *Cluster = B.lookup(Base); - if (!Cluster) - return B; - - ClusterBindings NewCluster = CBFactory.remove(*Cluster, K); - if (NewCluster.isEmpty()) - return RBFactory.remove(B, Base); - return RBFactory.add(B, Base, NewCluster); -} - -RegionBindings RegionStoreManager::removeBinding(RegionBindings B, - const MemRegion *R, - BindingKey::Kind k){ - return removeBinding(B, BindingKey::Make(R, k)); -} - -RegionBindings RegionStoreManager::removeCluster(RegionBindings B, - const MemRegion *Base) { - return RBFactory.remove(B, Base); + return removeSubRegionBindings(B, R).addBinding(R, BindingKey::Default, Val); } //===----------------------------------------------------------------------===// @@ -1818,7 +2113,7 @@ class removeDeadBindingsWorker : public: removeDeadBindingsWorker(RegionStoreManager &rm, ProgramStateManager &stateMgr, - RegionBindings b, SymbolReaper &symReaper, + RegionBindingsRef b, SymbolReaper &symReaper, const StackFrameContext *LCtx) : ClusterAnalysis<removeDeadBindingsWorker>(rm, stateMgr, b, /* includeGlobals = */ false), @@ -1826,7 +2121,8 @@ public: // Called by ClusterAnalysis. void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C); - void VisitCluster(const MemRegion *baseR, const ClusterBindings &C); + void VisitCluster(const MemRegion *baseR, const ClusterBindings *C); + using ClusterAnalysis<removeDeadBindingsWorker>::VisitCluster; bool UpdatePostponed(); void VisitBinding(SVal V); @@ -1869,38 +2165,30 @@ void removeDeadBindingsWorker::VisitAddedToCluster(const MemRegion *baseR, } void removeDeadBindingsWorker::VisitCluster(const MemRegion *baseR, - const ClusterBindings &C) { + const ClusterBindings *C) { + if (!C) + return; + // Mark the symbol for any SymbolicRegion with live bindings as live itself. // This means we should continue to track that symbol. if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(baseR)) SymReaper.markLive(SymR->getSymbol()); - for (ClusterBindings::iterator I = C.begin(), E = C.end(); I != E; ++I) + for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I) VisitBinding(I.getData()); } void removeDeadBindingsWorker::VisitBinding(SVal V) { // Is it a LazyCompoundVal? All referenced regions are live as well. - if (const nonloc::LazyCompoundVal *LCS = - dyn_cast<nonloc::LazyCompoundVal>(&V)) { + if (Optional<nonloc::LazyCompoundVal> LCS = + V.getAs<nonloc::LazyCompoundVal>()) { - const MemRegion *LazyR = LCS->getRegion(); - RegionBindings B = RegionStoreManager::GetRegionBindings(LCS->getStore()); + const RegionStoreManager::SValListTy &Vals = RM.getInterestingValues(*LCS); - // FIXME: This should not have to walk all bindings in the old store. - for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI){ - const ClusterBindings &Cluster = RI.getData(); - for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); - CI != CE; ++CI) { - BindingKey K = CI.getKey(); - if (const SubRegion *BaseR = dyn_cast<SubRegion>(K.getRegion())) { - if (BaseR == LazyR) - VisitBinding(CI.getData()); - else if (K.hasSymbolicOffset() && BaseR->isSubRegionOf(LazyR)) - VisitBinding(CI.getData()); - } - } - } + for (RegionStoreManager::SValListTy::const_iterator I = Vals.begin(), + E = Vals.end(); + I != E; ++I) + VisitBinding(*I); return; } @@ -1946,7 +2234,7 @@ bool removeDeadBindingsWorker::UpdatePostponed() { StoreRef RegionStoreManager::removeDeadBindings(Store store, const StackFrameContext *LCtx, SymbolReaper& SymReaper) { - RegionBindings B = GetRegionBindings(store); + RegionBindingsRef B = getRegionBindings(store); removeDeadBindingsWorker W(*this, StateMgr, B, SymReaper, LCtx); W.GenerateClusters(); @@ -1961,7 +2249,7 @@ StoreRef RegionStoreManager::removeDeadBindings(Store store, // We have now scanned the store, marking reachable regions and symbols // as live. We now remove all the regions that are dead from the store // as well as update DSymbols with the set symbols that are now dead. - for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) { + for (RegionBindingsRef::iterator I = B.begin(), E = B.end(); I != E; ++I) { const MemRegion *Base = I.getKey(); // If the cluster has been visited, we know the region has been marked. @@ -1969,7 +2257,7 @@ StoreRef RegionStoreManager::removeDeadBindings(Store store, continue; // Remove the dead entry. - B = removeCluster(B, Base); + B = B.remove(Base); if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(Base)) SymReaper.maybeDead(SymR->getSymbol()); @@ -1985,7 +2273,7 @@ StoreRef RegionStoreManager::removeDeadBindings(Store store, } } - return StoreRef(B.getRootWithoutRetain(), *this); + return StoreRef(B.asStore(), *this); } //===----------------------------------------------------------------------===// @@ -1994,17 +2282,9 @@ StoreRef RegionStoreManager::removeDeadBindings(Store store, void RegionStoreManager::print(Store store, raw_ostream &OS, const char* nl, const char *sep) { - RegionBindings B = GetRegionBindings(store); + RegionBindingsRef B = getRegionBindings(store); OS << "Store (direct and default bindings), " - << (void*) B.getRootWithoutRetain() + << B.asStore() << " :" << nl; - - for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) { - const ClusterBindings &Cluster = I.getData(); - for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); - CI != CE; ++CI) { - OS << ' ' << CI.getKey() << " : " << CI.getData() << nl; - } - OS << nl; - } + B.dump(OS, nl); } |
