From e0d24eb1060a213ec9820dc02c45f26b2d5b348b Mon Sep 17 00:00:00 2001 From: Jordan Rose Date: Wed, 8 Aug 2012 18:23:27 +0000 Subject: [PATCH] [analyzer] Revamp RegionStore to distinguish regions with symbolic offsets. RegionStore currently uses a (Region, Offset) pair to describe the locations of memory bindings. However, this representation breaks down when we have regions like 'array[index]', where 'index' is unknown. We used to store this as (SubRegion, 0); now we mark them specially as (SubRegion, SYMBOLIC). Furthermore, ProgramState::scanReachableSymbols depended on the existence of a sub-region map, but RegionStore's implementation doesn't provide for such a thing. Moving the store-traversing logic of scanReachableSymbols into the StoreManager allows us to eliminate the notion of SubRegionMap altogether. This fixes some particularly awkward broken test cases, now in array-struct-region.c. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@161510 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../Core/PathSensitive/MemRegion.h | 8 +- .../Core/PathSensitive/ProgramState.h | 9 +- .../StaticAnalyzer/Core/PathSensitive/Store.h | 31 +- lib/StaticAnalyzer/Core/MemRegion.cpp | 49 +++- lib/StaticAnalyzer/Core/ProgramState.cpp | 26 +- lib/StaticAnalyzer/Core/RegionStore.cpp | 271 +++++++++--------- lib/StaticAnalyzer/Core/Store.cpp | 3 - test/Analysis/array-struct-region.c | 92 ++++++ 8 files changed, 287 insertions(+), 202 deletions(-) diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h b/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h index 2e922c0cc3..9bdeb3e09b 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h @@ -52,11 +52,13 @@ class RegionOffset { int64_t Offset; public: - RegionOffset(const MemRegion *r) : R(r), Offset(0) {} + RegionOffset() : R(0) {} RegionOffset(const MemRegion *r, int64_t off) : R(r), Offset(off) {} const MemRegion *getRegion() const { return R; } int64_t getOffset() const { return Offset; } + + bool isValid() const { return R; } }; //===----------------------------------------------------------------------===// @@ -490,6 +492,8 @@ public: return T.getTypePtrOrNull() ? T.getDesugaredType(Context) : T; } + DefinedOrUnknownSVal getExtent(SValBuilder &svalBuilder) const; + static bool classof(const MemRegion* R) { unsigned k = R->getKind(); return k >= BEG_TYPED_VALUE_REGIONS && k <= END_TYPED_VALUE_REGIONS; @@ -806,8 +810,6 @@ public: const Decl *getDecl() const { return D; } void Profile(llvm::FoldingSetNodeID& ID) const; - DefinedOrUnknownSVal getExtent(SValBuilder &svalBuilder) const; - static bool classof(const MemRegion* R) { unsigned k = R->getKind(); return k >= BEG_DECL_REGIONS && k <= END_DECL_REGIONS; diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h index b38f3ac311..84a839819c 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h @@ -795,14 +795,12 @@ CB ProgramState::scanReachableSymbols(const MemRegion * const *beg, /// \class ScanReachableSymbols /// A Utility class that allows to visit the reachable symbols using a custom /// SymbolVisitor. -class ScanReachableSymbols : public SubRegionMap::Visitor { - virtual void anchor(); +class ScanReachableSymbols { typedef llvm::DenseMap VisitedItems; VisitedItems visited; ProgramStateRef state; SymbolVisitor &visitor; - OwningPtr SRM; public: ScanReachableSymbols(ProgramStateRef st, SymbolVisitor& v) @@ -812,11 +810,6 @@ public: bool scan(SVal val); bool scan(const MemRegion *R); bool scan(const SymExpr *sym); - - // From SubRegionMap::Visitor. - bool Visit(const MemRegion* Parent, const MemRegion* SubRegion) { - return scan(SubRegion); - } }; } // end GR namespace diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h b/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h index 828347254c..eb60c92113 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h @@ -32,7 +32,7 @@ namespace ento { class CallEvent; class ProgramState; class ProgramStateManager; -class SubRegionMap; +class ScanReachableSymbols; class StoreManager { protected: @@ -85,11 +85,6 @@ public: /// used to query and manipulate MemRegion objects. MemRegionManager& getRegionManager() { return MRMgr; } - /// getSubRegionMap - Returns an opaque map object that clients can query - /// to get the subregions of a given MemRegion object. It is the - // caller's responsibility to 'delete' the returned map. - virtual SubRegionMap *getSubRegionMap(Store store) = 0; - virtual Loc getLValueVar(const VarDecl *VD, const LocationContext *LC) { return svalBuilder.makeLoc(MRMgr.getVarRegion(VD, LC)); } @@ -203,6 +198,12 @@ public: const CallEvent &Call, const StackFrameContext *CalleeCtx); + /// Finds the transitive closure of symbols within the given region. + /// + /// Returns false if the visitor aborted the scan. + virtual bool scanReachableSymbols(Store S, const MemRegion *R, + ScanReachableSymbols &Visitor) = 0; + virtual void print(Store store, raw_ostream &Out, const char* nl, const char *sep) = 0; @@ -274,24 +275,6 @@ inline StoreRef &StoreRef::operator=(StoreRef const &newStore) { return *this; } -// FIXME: Do we still need this? -/// SubRegionMap - An abstract interface that represents a queryable map -/// between MemRegion objects and their subregions. -class SubRegionMap { - virtual void anchor(); -public: - virtual ~SubRegionMap() {} - - class Visitor { - virtual void anchor(); - public: - virtual ~Visitor() {} - virtual bool Visit(const MemRegion* Parent, const MemRegion* SubRegion) = 0; - }; - - virtual bool iterSubRegions(const MemRegion *region, Visitor& V) const = 0; -}; - // FIXME: Do we need to pass ProgramStateManager anymore? StoreManager *CreateRegionStoreManager(ProgramStateManager& StMgr); StoreManager *CreateFieldsOnlyRegionStoreManager(ProgramStateManager& StMgr); diff --git a/lib/StaticAnalyzer/Core/MemRegion.cpp b/lib/StaticAnalyzer/Core/MemRegion.cpp index 54090783e2..f3a1ff447c 100644 --- a/lib/StaticAnalyzer/Core/MemRegion.cpp +++ b/lib/StaticAnalyzer/Core/MemRegion.cpp @@ -179,7 +179,7 @@ const StackFrameContext *VarRegion::getStackFrame() const { // Region extents. //===----------------------------------------------------------------------===// -DefinedOrUnknownSVal DeclRegion::getExtent(SValBuilder &svalBuilder) const { +DefinedOrUnknownSVal TypedValueRegion::getExtent(SValBuilder &svalBuilder) const { ASTContext &Ctx = svalBuilder.getContext(); QualType T = getDesugaredValueType(Ctx); @@ -470,7 +470,7 @@ void CXXTempObjectRegion::dumpToStream(raw_ostream &os) const { } void CXXBaseObjectRegion::dumpToStream(raw_ostream &os) const { - os << "base " << decl->getName(); + os << "base{" << superRegion << ',' << decl->getName() << '}'; } void CXXThisRegion::dumpToStream(raw_ostream &os) const { @@ -1031,30 +1031,63 @@ RegionOffset MemRegion::getAsOffset() const { while (1) { switch (R->getKind()) { default: - return RegionOffset(0); + return RegionOffset(); case SymbolicRegionKind: case AllocaRegionKind: case CompoundLiteralRegionKind: case CXXThisRegionKind: case StringRegionKind: case VarRegionKind: + case ObjCIvarRegionKind: case CXXTempObjectRegionKind: goto Finish; + case CXXBaseObjectRegionKind: { + const CXXBaseObjectRegion *BOR = cast(R); + R = BOR->getSuperRegion(); + + QualType Ty; + if (const TypedValueRegion *TVR = dyn_cast(R)) { + Ty = TVR->getDesugaredValueType(getContext()); + } else if (const SymbolicRegion *SR = dyn_cast(R)) { + // If our base region is symbolic, we don't know what type it really is. + // Pretend the type of the symbol is the true dynamic type. + // (This will at least be self-consistent for the life of the symbol.) + Ty = SR->getSymbol()->getType(getContext())->getPointeeType(); + } + + const CXXRecordDecl *Child = Ty->getAsCXXRecordDecl(); + if (!Child) { + // We cannot compute the offset of the base class. + return RegionOffset(); + } + const ASTRecordLayout &Layout = getContext().getASTRecordLayout(Child); + + CharUnits BaseOffset; + const CXXRecordDecl *Base = BOR->getDecl(); + if (Child->isVirtuallyDerivedFrom(Base)) + BaseOffset = Layout.getVBaseClassOffset(Base); + else + BaseOffset = Layout.getBaseClassOffset(Base); + + // The base offset is in chars, not in bits. + Offset += BaseOffset.getQuantity() * getContext().getCharWidth(); + break; + } case ElementRegionKind: { const ElementRegion *ER = cast(R); QualType EleTy = ER->getValueType(); if (!IsCompleteType(getContext(), EleTy)) - return RegionOffset(0); + return RegionOffset(); SVal Index = ER->getIndex(); if (const nonloc::ConcreteInt *CI=dyn_cast(&Index)) { int64_t i = CI->getValue().getSExtValue(); - CharUnits Size = getContext().getTypeSizeInChars(EleTy); - Offset += i * Size.getQuantity() * 8; + // This type size is in bits. + Offset += i * getContext().getTypeSize(EleTy); } else { // We cannot compute offset for non-concrete index. - return RegionOffset(0); + return RegionOffset(); } R = ER->getSuperRegion(); break; @@ -1064,7 +1097,7 @@ RegionOffset MemRegion::getAsOffset() const { const RecordDecl *RD = FR->getDecl()->getParent(); if (!RD->isCompleteDefinition()) // We cannot compute offset for incomplete type. - return RegionOffset(0); + return RegionOffset(); // Get the field number. unsigned idx = 0; for (RecordDecl::field_iterator FI = RD->field_begin(), diff --git a/lib/StaticAnalyzer/Core/ProgramState.cpp b/lib/StaticAnalyzer/Core/ProgramState.cpp index c916c1a020..9245a70dd2 100644 --- a/lib/StaticAnalyzer/Core/ProgramState.cpp +++ b/lib/StaticAnalyzer/Core/ProgramState.cpp @@ -499,8 +499,6 @@ ProgramStateRef ProgramStateManager::removeGDM(ProgramStateRef state, void *Key) return getPersistentState(NewState); } -void ScanReachableSymbols::anchor() { } - bool ScanReachableSymbols::scan(nonloc::CompoundVal val) { for (nonloc::CompoundVal::iterator I=val.begin(), E=val.end(); I!=E; ++I) if (!scan(*I)) @@ -578,10 +576,19 @@ bool ScanReachableSymbols::scan(const MemRegion *R) { return false; // If this is a subregion, also visit the parent regions. - if (const SubRegion *SR = dyn_cast(R)) - if (!scan(SR->getSuperRegion())) + if (const SubRegion *SR = dyn_cast(R)) { + const MemRegion *Super = SR->getSuperRegion(); + if (!scan(Super)) return false; + // When we reach the topmost region, scan all symbols in it. + if (isa(Super)) { + StoreManager &StoreMgr = state->getStateManager().getStoreManager(); + if (!StoreMgr.scanReachableSymbols(state->getStore(), SR, *this)) + return false; + } + } + // Regions captured by a block are also implicitly reachable. if (const BlockDataRegion *BDR = dyn_cast(R)) { BlockDataRegion::referenced_vars_iterator I = BDR->referenced_vars_begin(), @@ -592,16 +599,7 @@ bool ScanReachableSymbols::scan(const MemRegion *R) { } } - // Now look at the binding to this region (if any). - if (!scan(state->getSValAsScalarOrLoc(R))) - return false; - - // Now look at the subregions. - if (!SRM.get()) - SRM.reset(state->getStateManager().getStoreManager(). - getSubRegionMap(state->getStore())); - - return SRM->iterSubRegions(R, *this); + return true; } bool ProgramState::scanReachableSymbols(SVal val, SymbolVisitor& visitor) const { diff --git a/lib/StaticAnalyzer/Core/RegionStore.cpp b/lib/StaticAnalyzer/Core/RegionStore.cpp index a912f0250b..90bd0f31a5 100644 --- a/lib/StaticAnalyzer/Core/RegionStore.cpp +++ b/lib/StaticAnalyzer/Core/RegionStore.cpp @@ -42,17 +42,27 @@ class BindingKey { public: enum Kind { Direct = 0x0, Default = 0x1 }; private: - llvm ::PointerIntPair P; + enum { SYMBOLIC = UINT64_MAX }; + + llvm::PointerIntPair P; uint64_t Offset; + explicit BindingKey(const MemRegion *r, Kind k) + : P(r, k), Offset(SYMBOLIC) {} explicit BindingKey(const MemRegion *r, uint64_t offset, Kind k) - : P(r, (unsigned) k), Offset(offset) {} + : P(r, k), Offset(offset) {} public: bool isDirect() const { return P.getInt() == Direct; } + bool hasSymbolicOffset() const { return Offset == SYMBOLIC; } const MemRegion *getRegion() const { return P.getPointer(); } - uint64_t getOffset() const { return Offset; } + uint64_t getOffset() const { + assert(!hasSymbolicOffset()); + return Offset; + } + + const MemRegion *getConcreteOffsetRegion() const; void Profile(llvm::FoldingSetNodeID& ID) const { ID.AddPointer(P.getOpaqueValue()); @@ -82,17 +92,36 @@ public: BindingKey BindingKey::Make(const MemRegion *R, Kind k) { const RegionOffset &RO = R->getAsOffset(); - if (RO.getRegion()) + if (RO.isValid()) return BindingKey(RO.getRegion(), RO.getOffset(), k); - return BindingKey(R, 0, k); + return BindingKey(R, k); +} + +const MemRegion *BindingKey::getConcreteOffsetRegion() const { + const MemRegion *R = getRegion(); + if (!hasSymbolicOffset()) + return R; + + RegionOffset RO; + do { + const SubRegion *SR = dyn_cast(R); + if (!SR) + break; + R = SR->getSuperRegion(); + RO = R->getAsOffset(); + } while (!RO.isValid()); + + return R; } namespace llvm { static inline raw_ostream &operator<<(raw_ostream &os, BindingKey K) { - os << '(' << K.getRegion() << ',' << K.getOffset() - << ',' << (K.isDirect() ? "direct" : "default") + os << '(' << K.getRegion(); + if (!K.hasSymbolicOffset()) + os << ',' << K.getOffset(); + os << ',' << (K.isDirect() ? "direct" : "default") << ')'; return os; } @@ -133,60 +162,6 @@ public: namespace { -class RegionStoreSubRegionMap : public SubRegionMap { -public: - typedef llvm::ImmutableSet Set; - typedef llvm::DenseMap Map; -private: - Set::Factory F; - Map M; -public: - bool add(const MemRegion* Parent, const MemRegion* SubRegion) { - Map::iterator I = M.find(Parent); - - if (I == M.end()) { - M.insert(std::make_pair(Parent, F.add(F.getEmptySet(), SubRegion))); - return true; - } - - I->second = F.add(I->second, SubRegion); - return false; - } - - void process(SmallVectorImpl &WL, const SubRegion *R); - - ~RegionStoreSubRegionMap() {} - - const Set *getSubRegions(const MemRegion *Parent) const { - Map::const_iterator I = M.find(Parent); - return I == M.end() ? NULL : &I->second; - } - - bool iterSubRegions(const MemRegion* Parent, Visitor& V) const { - Map::const_iterator I = M.find(Parent); - - if (I == M.end()) - return true; - - Set S = I->second; - for (Set::iterator SI=S.begin(),SE=S.end(); SI != SE; ++SI) { - if (!V.Visit(Parent, *SI)) - return false; - } - - return true; - } -}; - -void -RegionStoreSubRegionMap::process(SmallVectorImpl &WL, - const SubRegion *R) { - const MemRegion *superR = R->getSuperRegion(); - if (add(superR, R)) - if (const SubRegion *sr = dyn_cast(superR)) - WL.push_back(sr); -} - class RegionStoreManager : public StoreManager { const RegionStoreFeatures Features; RegionBindings::Factory RBFactory; @@ -197,12 +172,6 @@ public: Features(f), RBFactory(mgr.getAllocator()) {} - SubRegionMap *getSubRegionMap(Store store) { - return getRegionStoreSubRegionMap(store); - } - - RegionStoreSubRegionMap *getRegionStoreSubRegionMap(Store store); - Optional getDirectBinding(RegionBindings B, const MemRegion *R); /// getDefaultBinding - Returns an SVal* representing an optional default /// binding associated with a region and its subregions. @@ -255,10 +224,12 @@ public: const CallEvent *Call, InvalidatedRegions *Invalidated); + bool scanReachableSymbols(Store S, const MemRegion *R, + ScanReachableSymbols &Callbacks); + public: // Made public for helper classes. - void RemoveSubRegionBindings(RegionBindings &B, const MemRegion *R, - RegionStoreSubRegionMap &M); + RegionBindings removeSubRegionBindings(RegionBindings B, const SubRegion *R); RegionBindings addBinding(RegionBindings B, BindingKey K, SVal V); @@ -443,28 +414,6 @@ ento::CreateFieldsOnlyRegionStoreManager(ProgramStateManager &StMgr) { } -RegionStoreSubRegionMap* -RegionStoreManager::getRegionStoreSubRegionMap(Store store) { - RegionBindings B = GetRegionBindings(store); - RegionStoreSubRegionMap *M = new RegionStoreSubRegionMap(); - - SmallVector WL; - - for (RegionBindings::iterator I=B.begin(), E=B.end(); I!=E; ++I) - if (const SubRegion *R = dyn_cast(I.getKey().getRegion())) - M->process(WL, R); - - // We also need to record in the subregion map "intermediate" regions that - // don't have direct bindings but are super regions of those that do. - while (!WL.empty()) { - const SubRegion *R = WL.back(); - WL.pop_back(); - M->process(WL, R); - } - - return M; -} - //===----------------------------------------------------------------------===// // Region Cluster analysis. //===----------------------------------------------------------------------===// @@ -584,16 +533,88 @@ public: // Binding invalidation. //===----------------------------------------------------------------------===// -void RegionStoreManager::RemoveSubRegionBindings(RegionBindings &B, - const MemRegion *R, - RegionStoreSubRegionMap &M) { +bool RegionStoreManager::scanReachableSymbols(Store S, const MemRegion *R, + ScanReachableSymbols &Callbacks) { + // FIXME: This linear scan through all bindings could possibly be optimized + // by changing the data structure used for RegionBindings. + + RegionBindings B = GetRegionBindings(S); + for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI) { + BindingKey Key = RI.getKey(); + if (Key.getRegion() == R) { + if (!Callbacks.scan(RI.getData())) + return false; + } else if (Key.hasSymbolicOffset()) { + if (const SubRegion *BaseSR = dyn_cast(Key.getRegion())) + if (BaseSR->isSubRegionOf(R)) + if (!Callbacks.scan(RI.getData())) + return false; + } + } - if (const RegionStoreSubRegionMap::Set *S = M.getSubRegions(R)) - for (RegionStoreSubRegionMap::Set::iterator I = S->begin(), E = S->end(); - I != E; ++I) - RemoveSubRegionBindings(B, *I, M); + return true; +} - B = removeBinding(B, R); +RegionBindings RegionStoreManager::removeSubRegionBindings(RegionBindings B, + const SubRegion *R) { + // FIXME: This linear scan through all bindings could possibly be optimized + // by changing the data structure used for RegionBindings. + + BindingKey SRKey = BindingKey::Make(R, BindingKey::Default); + assert(SRKey.isValid()); + if (SRKey.hasSymbolicOffset()) { + const SubRegion *Base = cast(SRKey.getConcreteOffsetRegion()); + B = removeSubRegionBindings(B, Base); + return addBinding(B, Base, BindingKey::Default, UnknownVal()); + } + + // FIXME: This does the wrong thing for bitfields. + uint64_t Length = UINT64_MAX; + + SVal Extent = R->getExtent(svalBuilder); + if (nonloc::ConcreteInt *ExtentCI = dyn_cast(&Extent)) { + 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(); + } + + // It is safe to iterate over the bindings as they are being changed + // because they are in an ImmutableMap. + for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI) { + BindingKey NextKey = RI.getKey(); + if (NextKey.getRegion() == SRKey.getRegion()) { + // Case 1: The next binding is inside the region we're invalidating. + // Remove it. + if (NextKey.getOffset() > SRKey.getOffset() && + NextKey.getOffset() - SRKey.getOffset() < Length) + B = removeBinding(B, NextKey); + // 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. + else if (NextKey.getOffset() == SRKey.getOffset()) + if (NextKey.isDirect()) + B = removeBinding(B, NextKey); + + } else if (NextKey.hasSymbolicOffset()) { + const MemRegion *Base = NextKey.getConcreteOffsetRegion(); + // 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 (R->isSubRegionOf(Base)) + B = removeBinding(B, NextKey); + // Case 4: The next key is symbolic, but we changed a known super-region. + // In this case the binding is certainly no longer valid. + else if (const SubRegion *BaseSR = dyn_cast(Base)) + if (BaseSR->isSubRegionOf(R)) + B = removeBinding(B, NextKey); + } + } + + return B; } namespace { @@ -1542,20 +1563,7 @@ StoreRef RegionStoreManager::Bind(Store store, Loc L, SVal V) { return BindVector(store, TR, V); } - if (const ElementRegion *ER = dyn_cast(R)) { - if (ER->getIndex().isZeroConstant()) { - if (const TypedValueRegion *superR = - dyn_cast(ER->getSuperRegion())) { - QualType superTy = superR->getValueType(); - // For now, just invalidate the fields of the struct/union/class. - // This is for test rdar_test_7185607 in misc-ps-region-store.m. - // FIXME: Precisely handle the fields of the record. - if (superTy->isStructureOrClassType()) - return KillStruct(store, superR, UnknownVal()); - } - } - } - else if (const SymbolicRegion *SR = dyn_cast(R)) { + if (const SymbolicRegion *SR = dyn_cast(R)) { // Binding directly to a symbolic region should be treated as binding // to element 0. QualType T = SR->getSymbol()->getType(Ctx); @@ -1569,10 +1577,13 @@ StoreRef RegionStoreManager::Bind(Store store, Loc L, SVal V) { R = GetElementZeroRegion(SR, T); } + // Clear out bindings that may overlap with this binding. + // Perform the binding. RegionBindings B = GetRegionBindings(store); - return StoreRef(addBinding(B, R, BindingKey::Direct, - V).getRootWithoutRetain(), *this); + B = removeSubRegionBindings(B, cast(R)); + BindingKey Key = BindingKey::Make(R, BindingKey::Direct); + return StoreRef(addBinding(B, Key, V).getRootWithoutRetain(), *this); } StoreRef RegionStoreManager::BindDecl(Store store, const VarRegion *VR, @@ -1792,30 +1803,11 @@ StoreRef RegionStoreManager::BindStruct(Store store, const TypedValueRegion* R, StoreRef RegionStoreManager::KillStruct(Store store, const TypedRegion* R, SVal DefaultVal) { BindingKey key = BindingKey::Make(R, BindingKey::Default); - - // The BindingKey may be "invalid" if we cannot handle the region binding - // explicitly. One example is something like array[index], where index - // is a symbolic value. In such cases, we want to invalidate the entire - // array, as the index assignment could have been to any element. In - // the case of nested symbolic indices, we need to march up the region - // hierarchy untile we reach a region whose binding we can reason about. - const SubRegion *subReg = R; - - while (!key.isValid()) { - if (const SubRegion *tmp = dyn_cast(subReg->getSuperRegion())) { - subReg = tmp; - key = BindingKey::Make(tmp, BindingKey::Default); - } - else - break; - } - // Remove the old bindings, using 'subReg' as the root of all regions + // Remove the old bindings, using 'R' as the root of all regions // we will invalidate. RegionBindings B = GetRegionBindings(store); - OwningPtr - SubRegions(getRegionStoreSubRegionMap(store)); - RemoveSubRegionBindings(B, subReg, *SubRegions); + B = removeSubRegionBindings(B, R); // Set the default value of the struct region to "unknown". if (!key.isValid()) @@ -1830,12 +1822,7 @@ StoreRef RegionStoreManager::CopyLazyBindings(nonloc::LazyCompoundVal V, // Nuke the old bindings stemming from R. RegionBindings B = GetRegionBindings(store); - - OwningPtr - SubRegions(getRegionStoreSubRegionMap(store)); - - // B and DVM are updated after the call to RemoveSubRegionBindings. - RemoveSubRegionBindings(B, R, *SubRegions.get()); + B = removeSubRegionBindings(B, R); // Now copy the bindings. This amounts to just binding 'V' to 'R'. This // results in a zero-copy algorithm. diff --git a/lib/StaticAnalyzer/Core/Store.cpp b/lib/StaticAnalyzer/Core/Store.cpp index 63a5e382c9..b8097ab7c6 100644 --- a/lib/StaticAnalyzer/Core/Store.cpp +++ b/lib/StaticAnalyzer/Core/Store.cpp @@ -369,6 +369,3 @@ bool StoreManager::FindUniqueBinding::HandleBinding(StoreManager& SMgr, return true; } - -void SubRegionMap::anchor() { } -void SubRegionMap::Visitor::anchor() { } diff --git a/test/Analysis/array-struct-region.c b/test/Analysis/array-struct-region.c index c452709832..244bc977b5 100644 --- a/test/Analysis/array-struct-region.c +++ b/test/Analysis/array-struct-region.c @@ -92,3 +92,95 @@ float struct_in_struct_f() { return c.r; // no-warning } + +int randomInt(); + +int testSymbolicInvalidation(int index) { + int vals[10]; + + vals[0] = 42; + clang_analyzer_eval(vals[0] == 42); // expected-warning{{TRUE}} + + vals[index] = randomInt(); + clang_analyzer_eval(vals[0] == 42); // expected-warning{{UNKNOWN}} + + return vals[index]; // no-warning +} + +int testConcreteInvalidation(int index) { + int vals[10]; + + vals[index] = 42; + clang_analyzer_eval(vals[index] == 42); // expected-warning{{TRUE}} + vals[0] = randomInt(); + clang_analyzer_eval(vals[index] == 42); // expected-warning{{UNKNOWN}} + + return vals[0]; // no-warning +} + + +typedef struct { + int x, y, z; +} S; + +S makeS(); + +int testSymbolicInvalidationStruct(int index) { + S vals[10]; + + vals[0].x = 42; + clang_analyzer_eval(vals[0].x == 42); // expected-warning{{TRUE}} + + vals[index] = makeS(); + clang_analyzer_eval(vals[0].x == 42); // expected-warning{{UNKNOWN}} + + return vals[index].x; // no-warning +} + +int testConcreteInvalidationStruct(int index) { + S vals[10]; + + vals[index].x = 42; + clang_analyzer_eval(vals[index].x == 42); // expected-warning{{TRUE}} + vals[0] = makeS(); + clang_analyzer_eval(vals[index].x == 42); // expected-warning{{UNKNOWN}} + + return vals[0].x; // no-warning +} + +typedef struct { + S a[5]; + S b[5]; +} SS; + +int testSymbolicInvalidationDoubleStruct(int index) { + SS vals; + + vals.a[0].x = 42; + vals.b[0].x = 42; + clang_analyzer_eval(vals.a[0].x == 42); // expected-warning{{TRUE}} + clang_analyzer_eval(vals.b[0].x == 42); // expected-warning{{TRUE}} + + vals.a[index] = makeS(); + clang_analyzer_eval(vals.a[0].x == 42); // expected-warning{{UNKNOWN}} + clang_analyzer_eval(vals.b[0].x == 42); // expected-warning{{TRUE}} + + return vals.b[index].x; // no-warning +} + +int testConcreteInvalidationDoubleStruct(int index) { + SS vals; + + vals.a[index].x = 42; + vals.b[index].x = 42; + clang_analyzer_eval(vals.a[index].x == 42); // expected-warning{{TRUE}} + clang_analyzer_eval(vals.b[index].x == 42); // expected-warning{{TRUE}} + + vals.a[0] = makeS(); + clang_analyzer_eval(vals.a[index].x == 42); // expected-warning{{UNKNOWN}} + clang_analyzer_eval(vals.b[index].x == 42); // expected-warning{{TRUE}} + + return vals.b[0].x; // no-warning +} + + -- 2.40.0