diff options
Diffstat (limited to 'contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/RegionStore.cpp')
-rw-r--r-- | contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/RegionStore.cpp | 308 |
1 files changed, 114 insertions, 194 deletions
diff --git a/contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/RegionStore.cpp b/contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/RegionStore.cpp index bc4e4bb..aed994d 100644 --- a/contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/RegionStore.cpp +++ b/contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/RegionStore.cpp @@ -15,9 +15,6 @@ // //===----------------------------------------------------------------------===// #include "clang/AST/CharUnits.h" -#include "clang/AST/DeclCXX.h" -#include "clang/AST/ExprCXX.h" -#include "clang/AST/CXXInheritance.h" #include "clang/Analysis/Analyses/LiveVariables.h" #include "clang/Analysis/AnalysisContext.h" #include "clang/Basic/TargetInfo.h" @@ -193,19 +190,6 @@ public: /// casts from arrays to pointers. SVal ArrayToPointer(Loc Array); - /// For DerivedToBase casts, create a CXXBaseObjectRegion and return it. - virtual SVal evalDerivedToBase(SVal derived, QualType basePtrType); - - /// \brief Evaluates C++ dynamic_cast cast. - /// The callback may result in the following 3 scenarios: - /// - Successful cast (ex: derived is subclass of base). - /// - Failed cast (ex: derived is definitely not a subclass of base). - /// - We don't know (base is a symbolic region and we don't have - /// enough info to determine if the cast will succeed at run time). - /// The function returns an SVal representing the derived class; it's - /// valid only if Failed flag is set to false. - virtual SVal evalDynamicCast(SVal base, QualType derivedPtrType,bool &Failed); - StoreRef getInitialStore(const LocationContext *InitLoc) { return StoreRef(RBFactory.getEmptyMap().getRootWithoutRetain(), *this); } @@ -244,7 +228,7 @@ public: // Made public for helper classes. RegionBindings removeBinding(RegionBindings B, BindingKey K); RegionBindings removeBinding(RegionBindings B, const MemRegion *R, - BindingKey::Kind k); + BindingKey::Kind k); RegionBindings removeBinding(RegionBindings B, const MemRegion *R) { return removeBinding(removeBinding(B, R, BindingKey::Direct), R, @@ -266,15 +250,20 @@ public: // Part of public interface to class. .getRootWithoutRetain(), *this); } - StoreRef BindCompoundLiteral(Store store, const CompoundLiteralExpr *CL, + /// \brief Create a new store that binds a value to a compound literal. + /// + /// \param ST The original store whose bindings are the basis for the new + /// store. + /// + /// \param CL The compound literal to bind (the binding key). + /// + /// \param LC The LocationContext for the binding. + /// + /// \param V The value to bind to the compound literal. + StoreRef bindCompoundLiteral(Store ST, + const CompoundLiteralExpr *CL, const LocationContext *LC, SVal V); - StoreRef BindDecl(Store store, const VarRegion *VR, SVal InitVal); - - StoreRef BindDeclWithNoInit(Store store, const VarRegion *) { - return StoreRef(store, *this); - } - /// BindStruct - Bind a compound value to a structure. StoreRef BindStruct(Store store, const TypedValueRegion* R, SVal V); @@ -287,7 +276,10 @@ public: // Part of public interface to class. /// as a Default binding. StoreRef BindAggregate(Store store, const TypedRegion *R, SVal DefaultVal); - StoreRef Remove(Store store, Loc LV); + /// \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); void incrementReferenceCount(Store store) { GetRegionBindings(store).manualRetain(); @@ -477,12 +469,8 @@ public: } bool AddToWorkList(const MemRegion *R, const ClusterBindings *C) { - if (C) { - if (Visited.count(C)) - return false; - Visited.insert(C); - } - + if (C && !Visited.insert(C)) + return false; WL.push_back(R); return true; } @@ -534,6 +522,46 @@ bool RegionStoreManager::scanReachableSymbols(Store S, const MemRegion *R, return true; } +static inline bool isUnionField(const FieldRegion *FR) { + return FR->getDecl()->getParent()->isUnion(); +} + +typedef SmallVector<const FieldDecl *, 8> FieldVector; + +void getSymbolicOffsetFields(BindingKey K, FieldVector &Fields) { + assert(K.hasSymbolicOffset() && "Not implemented for concrete offset keys"); + + const MemRegion *Base = K.getConcreteOffsetRegion(); + const MemRegion *R = K.getRegion(); + + while (R != Base) { + if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) + if (!isUnionField(FR)) + Fields.push_back(FR->getDecl()); + + R = cast<SubRegion>(R)->getSuperRegion(); + } +} + +static bool isCompatibleWithFields(BindingKey K, const FieldVector &Fields) { + assert(K.hasSymbolicOffset() && "Not implemented for concrete offset keys"); + + if (Fields.empty()) + return true; + + FieldVector FieldsInBindingKey; + getSymbolicOffsetFields(K, FieldsInBindingKey); + + ptrdiff_t Delta = FieldsInBindingKey.size() - Fields.size(); + if (Delta >= 0) + return std::equal(FieldsInBindingKey.begin() + Delta, + FieldsInBindingKey.end(), + Fields.begin()); + else + return std::equal(FieldsInBindingKey.begin(), FieldsInBindingKey.end(), + Fields.begin() - Delta); +} + RegionBindings RegionStoreManager::removeSubRegionBindings(RegionBindings B, const SubRegion *R) { BindingKey SRKey = BindingKey::Make(R, BindingKey::Default); @@ -543,10 +571,12 @@ RegionBindings RegionStoreManager::removeSubRegionBindings(RegionBindings B, return RBFactory.remove(B, R); } - if (SRKey.hasSymbolicOffset()) { - const SubRegion *Base = cast<SubRegion>(SRKey.getConcreteOffsetRegion()); - B = removeSubRegionBindings(B, Base); - return addBinding(B, Base, BindingKey::Default, UnknownVal()); + FieldVector FieldsInSymbolicSubregions; + bool HasSymbolicOffset = SRKey.hasSymbolicOffset(); + if (HasSymbolicOffset) { + getSymbolicOffsetFields(SRKey, FieldsInSymbolicSubregions); + R = cast<SubRegion>(SRKey.getConcreteOffsetRegion()); + SRKey = BindingKey::Make(R, BindingKey::Default); } // This assumes the region being invalidated is char-aligned. This isn't @@ -574,11 +604,17 @@ RegionBindings RegionStoreManager::removeSubRegionBindings(RegionBindings B, I != E; ++I) { BindingKey NextKey = I.getKey(); if (NextKey.getRegion() == SRKey.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) { // Case 1: The next binding is inside the region we're invalidating. // Remove it. Result = CBFactory.remove(Result, NextKey); + } else if (NextKey.getOffset() == SRKey.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, @@ -589,6 +625,7 @@ RegionBindings RegionStoreManager::removeSubRegionBindings(RegionBindings B, if (NextKey.isDirect()) Result = CBFactory.remove(Result, NextKey); } + } else if (NextKey.hasSymbolicOffset()) { const MemRegion *Base = NextKey.getConcreteOffsetRegion(); if (R->isSubRegionOf(Base)) { @@ -596,16 +633,24 @@ RegionBindings RegionStoreManager::removeSubRegionBindings(RegionBindings B, // its concrete region. We don't know if the binding is still valid, so // we'll be conservative and remove it. if (NextKey.isDirect()) - Result = CBFactory.remove(Result, NextKey); + if (isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions)) + Result = CBFactory.remove(Result, NextKey); } 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)) - Result = CBFactory.remove(Result, NextKey); + if (isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions)) + Result = CBFactory.remove(Result, NextKey); } } } + // 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()); + if (Result.isEmpty()) return RBFactory.remove(B, ClusterHead); return RBFactory.add(B, ClusterHead, Result); @@ -724,7 +769,7 @@ void invalidateRegionsWorker::VisitBaseRegion(const MemRegion *baseR) { // Invalidate the region by setting its default value to // conjured symbol. The type of the symbol is irrelavant. DefinedOrUnknownSVal V = - svalBuilder.getConjuredSymbolVal(baseR, Ex, LCtx, Ctx.IntTy, Count); + svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, Ctx.IntTy, Count); B = RM.addBinding(B, baseR, BindingKey::Default, V); return; } @@ -739,8 +784,8 @@ void invalidateRegionsWorker::VisitBaseRegion(const MemRegion *baseR) { if (T->isStructureOrClassType()) { // Invalidate the region by setting its default value to // conjured symbol. The type of the symbol is irrelavant. - DefinedOrUnknownSVal V = - svalBuilder.getConjuredSymbolVal(baseR, Ex, LCtx, Ctx.IntTy, Count); + DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, + Ctx.IntTy, Count); B = RM.addBinding(B, baseR, BindingKey::Default, V); return; } @@ -748,7 +793,7 @@ void invalidateRegionsWorker::VisitBaseRegion(const MemRegion *baseR) { if (const ArrayType *AT = Ctx.getAsArrayType(T)) { // Set the default value of the array to conjured symbol. DefinedOrUnknownSVal V = - svalBuilder.getConjuredSymbolVal(baseR, Ex, LCtx, + svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, AT->getElementType(), Count); B = RM.addBinding(B, baseR, BindingKey::Default, V); return; @@ -764,8 +809,8 @@ void invalidateRegionsWorker::VisitBaseRegion(const MemRegion *baseR) { } - DefinedOrUnknownSVal V = svalBuilder.getConjuredSymbolVal(baseR, Ex, LCtx, - T,Count); + DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, + T,Count); assert(SymbolManager::canSymbolicate(T) || V.isUnknown()); B = RM.addBinding(B, baseR, BindingKey::Direct, V); } @@ -779,10 +824,9 @@ RegionBindings RegionStoreManager::invalidateGlobalRegion(MemRegion::Kind K, // 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); - SVal V = - svalBuilder.getConjuredSymbolVal(/* SymbolTag = */ (void*) GS, Ex, LCtx, - /* symbol type, doesn't matter */ Ctx.IntTy, - Count); + SVal V = svalBuilder.conjureSymbolVal(/* SymbolTag = */ (const void*) GS, Ex, LCtx, + /* type does not matter */ Ctx.IntTy, + Count); B = removeBinding(B, GS); B = addBinding(B, BindingKey::Make(GS, BindingKey::Default), V); @@ -897,103 +941,6 @@ SVal RegionStoreManager::ArrayToPointer(Loc Array) { return loc::MemRegionVal(MRMgr.getElementRegion(T, ZeroIdx, ArrayR, Ctx)); } -// This mirrors Type::getCXXRecordDeclForPointerType(), but there doesn't -// appear to be another need for this in the rest of the codebase. -static const CXXRecordDecl *GetCXXRecordDeclForReferenceType(QualType Ty) { - if (const ReferenceType *RT = Ty->getAs<ReferenceType>()) - if (const RecordType *RCT = RT->getPointeeType()->getAs<RecordType>()) - return dyn_cast<CXXRecordDecl>(RCT->getDecl()); - return 0; -} - -SVal RegionStoreManager::evalDerivedToBase(SVal derived, QualType baseType) { - const CXXRecordDecl *baseDecl; - - if (baseType->isPointerType()) - baseDecl = baseType->getCXXRecordDeclForPointerType(); - else if (baseType->isReferenceType()) - baseDecl = GetCXXRecordDeclForReferenceType(baseType); - else - baseDecl = baseType->getAsCXXRecordDecl(); - - assert(baseDecl && "not a CXXRecordDecl?"); - - loc::MemRegionVal *derivedRegVal = dyn_cast<loc::MemRegionVal>(&derived); - if (!derivedRegVal) - return derived; - - const MemRegion *baseReg = - MRMgr.getCXXBaseObjectRegion(baseDecl, derivedRegVal->getRegion()); - - return loc::MemRegionVal(baseReg); -} - -SVal RegionStoreManager::evalDynamicCast(SVal base, QualType derivedType, - bool &Failed) { - Failed = false; - - loc::MemRegionVal *baseRegVal = dyn_cast<loc::MemRegionVal>(&base); - if (!baseRegVal) - return UnknownVal(); - const MemRegion *BaseRegion = baseRegVal->stripCasts(/*StripBases=*/false); - - // Assume the derived class is a pointer or a reference to a CXX record. - derivedType = derivedType->getPointeeType(); - assert(!derivedType.isNull()); - const CXXRecordDecl *DerivedDecl = derivedType->getAsCXXRecordDecl(); - if (!DerivedDecl && !derivedType->isVoidType()) - return UnknownVal(); - - // Drill down the CXXBaseObject chains, which represent upcasts (casts from - // derived to base). - const MemRegion *SR = BaseRegion; - while (const TypedRegion *TSR = dyn_cast_or_null<TypedRegion>(SR)) { - QualType BaseType = TSR->getLocationType()->getPointeeType(); - assert(!BaseType.isNull()); - const CXXRecordDecl *SRDecl = BaseType->getAsCXXRecordDecl(); - if (!SRDecl) - return UnknownVal(); - - // If found the derived class, the cast succeeds. - if (SRDecl == DerivedDecl) - return loc::MemRegionVal(TSR); - - if (!derivedType->isVoidType()) { - // Static upcasts are marked as DerivedToBase casts by Sema, so this will - // only happen when multiple or virtual inheritance is involved. - CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/true, - /*DetectVirtual=*/false); - if (SRDecl->isDerivedFrom(DerivedDecl, Paths)) { - SVal Result = loc::MemRegionVal(TSR); - const CXXBasePath &Path = *Paths.begin(); - for (CXXBasePath::const_iterator I = Path.begin(), E = Path.end(); - I != E; ++I) { - Result = evalDerivedToBase(Result, I->Base->getType()); - } - return Result; - } - } - - if (const CXXBaseObjectRegion *R = dyn_cast<CXXBaseObjectRegion>(TSR)) - // Drill down the chain to get the derived classes. - SR = R->getSuperRegion(); - else { - // We reached the bottom of the hierarchy. - - // If this is a cast to void*, return the region. - if (derivedType->isVoidType()) - return loc::MemRegionVal(TSR); - - // We did not find the derived class. We we must be casting the base to - // derived, so the cast should fail. - Failed = true; - return UnknownVal(); - } - } - - return UnknownVal(); -} - //===----------------------------------------------------------------------===// // Loading values from regions. //===----------------------------------------------------------------------===// @@ -1047,7 +994,7 @@ SVal RegionStoreManager::getBinding(Store store, Loc L, QualType T) { T = TR->getLocationType(); else { const SymbolicRegion *SR = cast<SymbolicRegion>(MR); - T = SR->getSymbol()->getType(Ctx); + T = SR->getSymbol()->getType(); } } MR = GetElementZeroRegion(MR, T); @@ -1540,14 +1487,14 @@ bool RegionStoreManager::includedInBindings(Store store, // Binding values to regions. //===----------------------------------------------------------------------===// -StoreRef RegionStoreManager::Remove(Store store, Loc L) { +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(store), + return StoreRef(removeBinding(GetRegionBindings(ST), R).getRootWithoutRetain(), *this); - return StoreRef(store, *this); + return StoreRef(ST, *this); } StoreRef RegionStoreManager::Bind(Store store, Loc L, SVal V) { @@ -1560,6 +1507,8 @@ StoreRef RegionStoreManager::Bind(Store store, Loc L, SVal V) { // 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); if (Ty->isStructureOrClassType()) return BindStruct(store, TR, V); if (Ty->isVectorType()) @@ -1569,13 +1518,9 @@ StoreRef RegionStoreManager::Bind(Store store, Loc L, SVal V) { if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) { // Binding directly to a symbolic region should be treated as binding // to element 0. - QualType T = SR->getSymbol()->getType(Ctx); - - // FIXME: Is this the right way to handle symbols that are references? - if (const PointerType *PT = T->getAs<PointerType>()) - T = PT->getPointeeType(); - else - T = T->getAs<ReferenceType>()->getPointeeType(); + QualType T = SR->getSymbol()->getType(); + if (T->isAnyPointerType() || T->isReferenceType()) + T = T->getPointeeType(); R = GetElementZeroRegion(SR, T); } @@ -1589,26 +1534,12 @@ StoreRef RegionStoreManager::Bind(Store store, Loc L, SVal V) { return StoreRef(addBinding(B, Key, V).getRootWithoutRetain(), *this); } -StoreRef RegionStoreManager::BindDecl(Store store, const VarRegion *VR, - SVal InitVal) { - - QualType T = VR->getDecl()->getType(); - - if (T->isArrayType()) - return BindArray(store, VR, InitVal); - if (T->isStructureOrClassType()) - return BindStruct(store, VR, InitVal); - - return Bind(store, svalBuilder.makeLoc(VR), InitVal); -} - // FIXME: this method should be merged into Bind(). -StoreRef RegionStoreManager::BindCompoundLiteral(Store store, +StoreRef RegionStoreManager::bindCompoundLiteral(Store ST, const CompoundLiteralExpr *CL, const LocationContext *LC, SVal V) { - return Bind(store, loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL, LC)), - V); + return Bind(ST, loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL, LC)), V); } StoreRef RegionStoreManager::setImplicitDefaultValue(Store store, @@ -1864,7 +1795,7 @@ RegionBindings RegionStoreManager::removeBinding(RegionBindings B, RegionBindings RegionStoreManager::removeBinding(RegionBindings B, const MemRegion *R, - BindingKey::Kind k){ + BindingKey::Kind k){ return removeBinding(B, BindingKey::Make(R, k)); } @@ -1897,7 +1828,6 @@ public: void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C); void VisitCluster(const MemRegion *baseR, const ClusterBindings &C); - void VisitBindingKey(BindingKey K); bool UpdatePostponed(); void VisitBinding(SVal V); }; @@ -1932,17 +1862,21 @@ void removeDeadBindingsWorker::VisitAddedToCluster(const MemRegion *baseR, const StackArgumentsSpaceRegion *StackReg = cast<StackArgumentsSpaceRegion>(TR->getSuperRegion()); const StackFrameContext *RegCtx = StackReg->getStackFrame(); - if (RegCtx == CurrentLCtx || RegCtx->isParentOf(CurrentLCtx)) + if (CurrentLCtx && + (RegCtx == CurrentLCtx || RegCtx->isParentOf(CurrentLCtx))) AddToWorkList(TR, &C); } } void removeDeadBindingsWorker::VisitCluster(const MemRegion *baseR, const ClusterBindings &C) { - for (ClusterBindings::iterator I = C.begin(), E = C.end(); I != E; ++I) { - VisitBindingKey(I.getKey()); + // 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) VisitBinding(I.getData()); - } } void removeDeadBindingsWorker::VisitBinding(SVal V) { @@ -1979,8 +1913,8 @@ void removeDeadBindingsWorker::VisitBinding(SVal V) { if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(R)) { BlockDataRegion::referenced_vars_iterator I = BR->referenced_vars_begin(), E = BR->referenced_vars_end(); - for ( ; I != E; ++I) - AddToWorkList(I.getCapturedRegion()); + for ( ; I != E; ++I) + AddToWorkList(I.getCapturedRegion()); } } @@ -1991,20 +1925,6 @@ void removeDeadBindingsWorker::VisitBinding(SVal V) { SymReaper.markLive(*SI); } -void removeDeadBindingsWorker::VisitBindingKey(BindingKey K) { - const MemRegion *R = K.getRegion(); - - // Mark this region "live" by adding it to the worklist. This will cause - // use to visit all regions in the cluster (if we haven't visited them - // already). - if (AddToWorkList(R)) { - // Mark the symbol for any live SymbolicRegion as "live". This means we - // should continue to track that symbol. - if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(R)) - SymReaper.markLive(SymR->getSymbol()); - } -} - bool removeDeadBindingsWorker::UpdatePostponed() { // See if any postponed SymbolicRegions are actually live now, after // having done a scan. @@ -2012,7 +1932,7 @@ bool removeDeadBindingsWorker::UpdatePostponed() { for (SmallVectorImpl<const SymbolicRegion*>::iterator I = Postponed.begin(), E = Postponed.end() ; I != E ; ++I) { - if (const SymbolicRegion *SR = cast_or_null<SymbolicRegion>(*I)) { + if (const SymbolicRegion *SR = *I) { if (SymReaper.isLive(SR->getSymbol())) { changed |= AddToWorkList(SR); *I = NULL; |