| //== BasicStore.cpp - Basic map from Locations to Values --------*- C++ -*--==// |
| // |
| // The LLVM Compiler Infrastructure |
| // |
| // This file is distributed under the University of Illinois Open Source |
| // License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file defined the BasicStore and BasicStoreManager classes. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "clang/AST/DeclCXX.h" |
| #include "clang/AST/ExprObjC.h" |
| #include "clang/Analysis/Analyses/LiveVariables.h" |
| #include "clang/Analysis/AnalysisContext.h" |
| #include "clang/GR/PathSensitive/GRState.h" |
| #include "llvm/ADT/ImmutableMap.h" |
| |
| using namespace clang; |
| using namespace ento; |
| |
| typedef llvm::ImmutableMap<const MemRegion*,SVal> BindingsTy; |
| |
| namespace { |
| |
| class BasicStoreSubRegionMap : public SubRegionMap { |
| public: |
| BasicStoreSubRegionMap() {} |
| |
| bool iterSubRegions(const MemRegion* R, Visitor& V) const { |
| return true; // Do nothing. No subregions. |
| } |
| }; |
| |
| class BasicStoreManager : public StoreManager { |
| BindingsTy::Factory VBFactory; |
| public: |
| BasicStoreManager(GRStateManager& mgr) |
| : StoreManager(mgr), VBFactory(mgr.getAllocator()) {} |
| |
| ~BasicStoreManager() {} |
| |
| SubRegionMap *getSubRegionMap(Store store) { |
| return new BasicStoreSubRegionMap(); |
| } |
| |
| SVal Retrieve(Store store, Loc loc, QualType T = QualType()); |
| |
| Store InvalidateRegion(Store store, const MemRegion *R, const Expr *E, |
| unsigned Count, InvalidatedSymbols *IS); |
| |
| Store InvalidateRegions(Store store, const MemRegion * const *Begin, |
| const MemRegion * const *End, const Expr *E, |
| unsigned Count, InvalidatedSymbols *IS, |
| bool invalidateGlobals, InvalidatedRegions *Regions); |
| |
| Store scanForIvars(Stmt *B, const Decl* SelfDecl, |
| const MemRegion *SelfRegion, Store St); |
| |
| Store Bind(Store St, Loc loc, SVal V); |
| Store Remove(Store St, Loc loc); |
| Store getInitialStore(const LocationContext *InitLoc); |
| |
| Store BindCompoundLiteral(Store store, const CompoundLiteralExpr*, |
| const LocationContext*, SVal val) { |
| return store; |
| } |
| |
| /// ArrayToPointer - Used by ExprEngine::VistCast to handle implicit |
| /// conversions between arrays and pointers. |
| SVal ArrayToPointer(Loc Array) { return Array; } |
| |
| /// RemoveDeadBindings - Scans a BasicStore of 'state' for dead values. |
| /// It updatees the GRState object in place with the values removed. |
| Store RemoveDeadBindings(Store store, const StackFrameContext *LCtx, |
| SymbolReaper& SymReaper, |
| llvm::SmallVectorImpl<const MemRegion*>& RegionRoots); |
| |
| void iterBindings(Store store, BindingsHandler& f); |
| |
| Store BindDecl(Store store, const VarRegion *VR, SVal InitVal) { |
| return BindDeclInternal(store, VR, &InitVal); |
| } |
| |
| Store BindDeclWithNoInit(Store store, const VarRegion *VR) { |
| return BindDeclInternal(store, VR, 0); |
| } |
| |
| Store BindDeclInternal(Store store, const VarRegion *VR, SVal *InitVal); |
| |
| static inline BindingsTy GetBindings(Store store) { |
| return BindingsTy(static_cast<const BindingsTy::TreeTy*>(store)); |
| } |
| |
| void print(Store store, llvm::raw_ostream& Out, const char* nl, |
| const char *sep); |
| |
| private: |
| SVal LazyRetrieve(Store store, const TypedRegion *R); |
| }; |
| |
| } // end anonymous namespace |
| |
| |
| StoreManager* ento::CreateBasicStoreManager(GRStateManager& StMgr) { |
| return new BasicStoreManager(StMgr); |
| } |
| |
| static bool isHigherOrderRawPtr(QualType T, ASTContext &C) { |
| bool foundPointer = false; |
| while (1) { |
| const PointerType *PT = T->getAs<PointerType>(); |
| if (!PT) { |
| if (!foundPointer) |
| return false; |
| |
| // intptr_t* or intptr_t**, etc? |
| if (T->isIntegerType() && C.getTypeSize(T) == C.getTypeSize(C.VoidPtrTy)) |
| return true; |
| |
| QualType X = C.getCanonicalType(T).getUnqualifiedType(); |
| return X == C.VoidTy; |
| } |
| |
| foundPointer = true; |
| T = PT->getPointeeType(); |
| } |
| } |
| |
| SVal BasicStoreManager::LazyRetrieve(Store store, const TypedRegion *R) { |
| const VarRegion *VR = dyn_cast<VarRegion>(R); |
| if (!VR) |
| return UnknownVal(); |
| |
| const VarDecl *VD = VR->getDecl(); |
| QualType T = VD->getType(); |
| |
| // Only handle simple types that we can symbolicate. |
| if (!SymbolManager::canSymbolicate(T) || !T->isScalarType()) |
| return UnknownVal(); |
| |
| // Globals and parameters start with symbolic values. |
| // Local variables initially are undefined. |
| |
| // Non-static globals may have had their values reset by InvalidateRegions. |
| const MemSpaceRegion *MS = VR->getMemorySpace(); |
| if (isa<NonStaticGlobalSpaceRegion>(MS)) { |
| BindingsTy B = GetBindings(store); |
| // FIXME: Copy-and-pasted from RegionStore.cpp. |
| if (BindingsTy::data_type *Val = B.lookup(MS)) { |
| if (SymbolRef parentSym = Val->getAsSymbol()) |
| return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); |
| |
| if (Val->isZeroConstant()) |
| return svalBuilder.makeZeroVal(T); |
| |
| if (Val->isUnknownOrUndef()) |
| return *Val; |
| |
| assert(0 && "Unknown default value."); |
| } |
| } |
| |
| if (VR->hasGlobalsOrParametersStorage() || |
| isa<UnknownSpaceRegion>(VR->getMemorySpace())) |
| return svalBuilder.getRegionValueSymbolVal(R); |
| |
| return UndefinedVal(); |
| } |
| |
| SVal BasicStoreManager::Retrieve(Store store, Loc loc, QualType T) { |
| if (isa<UnknownVal>(loc)) |
| return UnknownVal(); |
| |
| assert(!isa<UndefinedVal>(loc)); |
| |
| switch (loc.getSubKind()) { |
| |
| case loc::MemRegionKind: { |
| const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion(); |
| |
| if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R) || |
| isa<CXXThisRegion>(R))) |
| return UnknownVal(); |
| |
| BindingsTy B = GetBindings(store); |
| BindingsTy::data_type *Val = B.lookup(R); |
| const TypedRegion *TR = cast<TypedRegion>(R); |
| |
| if (Val) |
| return CastRetrievedVal(*Val, TR, T); |
| |
| SVal V = LazyRetrieve(store, TR); |
| return V.isUnknownOrUndef() ? V : CastRetrievedVal(V, TR, T); |
| } |
| |
| case loc::ConcreteIntKind: |
| // Support direct accesses to memory. It's up to individual checkers |
| // to flag an error. |
| return UnknownVal(); |
| |
| default: |
| assert (false && "Invalid Loc."); |
| break; |
| } |
| |
| return UnknownVal(); |
| } |
| |
| Store BasicStoreManager::Bind(Store store, Loc loc, SVal V) { |
| if (isa<loc::ConcreteInt>(loc)) |
| return store; |
| |
| const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion(); |
| |
| // Special case: a default symbol assigned to the NonStaticGlobalsSpaceRegion |
| // that is used to derive other symbols. |
| if (isa<NonStaticGlobalSpaceRegion>(R)) { |
| BindingsTy B = GetBindings(store); |
| return VBFactory.add(B, R, V).getRoot(); |
| } |
| |
| // Special case: handle store of pointer values (Loc) to pointers via |
| // a cast to intXX_t*, void*, etc. This is needed to handle |
| // OSCompareAndSwap32Barrier/OSCompareAndSwap64Barrier. |
| if (isa<Loc>(V) || isa<nonloc::LocAsInteger>(V)) |
| if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) { |
| // FIXME: Should check for index 0. |
| QualType T = ER->getLocationType(); |
| |
| if (isHigherOrderRawPtr(T, Ctx)) |
| R = ER->getSuperRegion(); |
| } |
| |
| if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R) || isa<CXXThisRegion>(R))) |
| return store; |
| |
| const TypedRegion *TyR = cast<TypedRegion>(R); |
| |
| // Do not bind to arrays. We need to explicitly check for this so that |
| // we do not encounter any weirdness of trying to load/store from arrays. |
| if (TyR->isBoundable() && TyR->getValueType()->isArrayType()) |
| return store; |
| |
| if (nonloc::LocAsInteger *X = dyn_cast<nonloc::LocAsInteger>(&V)) { |
| // Only convert 'V' to a location iff the underlying region type |
| // is a location as well. |
| // FIXME: We are allowing a store of an arbitrary location to |
| // a pointer. We may wish to flag a type error here if the types |
| // are incompatible. This may also cause lots of breakage |
| // elsewhere. Food for thought. |
| if (TyR->isBoundable() && Loc::IsLocType(TyR->getValueType())) |
| V = X->getLoc(); |
| } |
| |
| BindingsTy B = GetBindings(store); |
| return V.isUnknown() |
| ? VBFactory.remove(B, R).getRoot() |
| : VBFactory.add(B, R, V).getRoot(); |
| } |
| |
| Store BasicStoreManager::Remove(Store store, Loc loc) { |
| switch (loc.getSubKind()) { |
| case loc::MemRegionKind: { |
| const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion(); |
| |
| if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R) || |
| isa<CXXThisRegion>(R))) |
| return store; |
| |
| return VBFactory.remove(GetBindings(store), R).getRoot(); |
| } |
| default: |
| assert ("Remove for given Loc type not yet implemented."); |
| return store; |
| } |
| } |
| |
| Store BasicStoreManager::RemoveDeadBindings(Store store, |
| const StackFrameContext *LCtx, |
| SymbolReaper& SymReaper, |
| llvm::SmallVectorImpl<const MemRegion*>& RegionRoots) |
| { |
| BindingsTy B = GetBindings(store); |
| typedef SVal::symbol_iterator symbol_iterator; |
| |
| // Iterate over the variable bindings. |
| for (BindingsTy::iterator I=B.begin(), E=B.end(); I!=E ; ++I) { |
| if (const VarRegion *VR = dyn_cast<VarRegion>(I.getKey())) { |
| if (SymReaper.isLive(VR)) |
| RegionRoots.push_back(VR); |
| else |
| continue; |
| } |
| else if (isa<ObjCIvarRegion>(I.getKey()) || |
| isa<NonStaticGlobalSpaceRegion>(I.getKey()) || |
| isa<CXXThisRegion>(I.getKey())) |
| RegionRoots.push_back(I.getKey()); |
| else |
| continue; |
| |
| // Mark the bindings in the data as live. |
| SVal X = I.getData(); |
| for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI) |
| SymReaper.markLive(*SI); |
| } |
| |
| // Scan for live variables and live symbols. |
| llvm::SmallPtrSet<const MemRegion*, 10> Marked; |
| |
| while (!RegionRoots.empty()) { |
| const MemRegion* MR = RegionRoots.back(); |
| RegionRoots.pop_back(); |
| |
| while (MR) { |
| if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(MR)) { |
| SymReaper.markLive(SymR->getSymbol()); |
| break; |
| } |
| else if (isa<VarRegion>(MR) || isa<ObjCIvarRegion>(MR) || |
| isa<NonStaticGlobalSpaceRegion>(MR) || isa<CXXThisRegion>(MR)) { |
| if (Marked.count(MR)) |
| break; |
| |
| Marked.insert(MR); |
| SVal X = Retrieve(store, loc::MemRegionVal(MR)); |
| |
| // FIXME: We need to handle symbols nested in region definitions. |
| for (symbol_iterator SI=X.symbol_begin(),SE=X.symbol_end();SI!=SE;++SI) |
| SymReaper.markLive(*SI); |
| |
| if (!isa<loc::MemRegionVal>(X)) |
| break; |
| |
| const loc::MemRegionVal& LVD = cast<loc::MemRegionVal>(X); |
| RegionRoots.push_back(LVD.getRegion()); |
| break; |
| } |
| else if (const SubRegion* R = dyn_cast<SubRegion>(MR)) |
| MR = R->getSuperRegion(); |
| else |
| break; |
| } |
| } |
| |
| // Remove dead variable bindings. |
| for (BindingsTy::iterator I=B.begin(), E=B.end(); I!=E ; ++I) { |
| const MemRegion* R = I.getKey(); |
| |
| if (!Marked.count(R)) { |
| store = Remove(store, svalBuilder.makeLoc(R)); |
| SVal X = I.getData(); |
| |
| for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI) |
| SymReaper.maybeDead(*SI); |
| } |
| } |
| |
| return store; |
| } |
| |
| Store BasicStoreManager::scanForIvars(Stmt *B, const Decl* SelfDecl, |
| const MemRegion *SelfRegion, Store St) { |
| for (Stmt::child_iterator CI=B->child_begin(), CE=B->child_end(); |
| CI != CE; ++CI) { |
| |
| if (!*CI) |
| continue; |
| |
| // Check if the statement is an ivar reference. We only |
| // care about self.ivar. |
| if (ObjCIvarRefExpr *IV = dyn_cast<ObjCIvarRefExpr>(*CI)) { |
| const Expr *Base = IV->getBase()->IgnoreParenCasts(); |
| if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Base)) { |
| if (DR->getDecl() == SelfDecl) { |
| const ObjCIvarRegion *IVR = MRMgr.getObjCIvarRegion(IV->getDecl(), |
| SelfRegion); |
| SVal X = svalBuilder.getRegionValueSymbolVal(IVR); |
| St = Bind(St, svalBuilder.makeLoc(IVR), X); |
| } |
| } |
| } |
| else |
| St = scanForIvars(*CI, SelfDecl, SelfRegion, St); |
| } |
| |
| return St; |
| } |
| |
| Store BasicStoreManager::getInitialStore(const LocationContext *InitLoc) { |
| // The LiveVariables information already has a compilation of all VarDecls |
| // used in the function. Iterate through this set, and "symbolicate" |
| // any VarDecl whose value originally comes from outside the function. |
| typedef LiveVariables::AnalysisDataTy LVDataTy; |
| LVDataTy& D = InitLoc->getLiveVariables()->getAnalysisData(); |
| Store St = VBFactory.getEmptyMap().getRoot(); |
| |
| for (LVDataTy::decl_iterator I=D.begin_decl(), E=D.end_decl(); I != E; ++I) { |
| const NamedDecl* ND = I->first; |
| |
| // Handle implicit parameters. |
| if (const ImplicitParamDecl* PD = dyn_cast<ImplicitParamDecl>(ND)) { |
| const Decl& CD = *InitLoc->getDecl(); |
| if (const ObjCMethodDecl* MD = dyn_cast<ObjCMethodDecl>(&CD)) { |
| if (MD->getSelfDecl() == PD) { |
| // FIXME: Add type constraints (when they become available) to |
| // SelfRegion? (i.e., it implements MD->getClassInterface()). |
| const VarRegion *VR = MRMgr.getVarRegion(PD, InitLoc); |
| const MemRegion *SelfRegion = |
| svalBuilder.getRegionValueSymbolVal(VR).getAsRegion(); |
| assert(SelfRegion); |
| St = Bind(St, svalBuilder.makeLoc(VR), loc::MemRegionVal(SelfRegion)); |
| // Scan the method for ivar references. While this requires an |
| // entire AST scan, the cost should not be high in practice. |
| St = scanForIvars(MD->getBody(), PD, SelfRegion, St); |
| } |
| } |
| } |
| } |
| |
| if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(InitLoc->getDecl())) { |
| // For C++ methods add symbolic region for 'this' in initial stack frame. |
| QualType ThisT = MD->getThisType(StateMgr.getContext()); |
| MemRegionManager &RegMgr = svalBuilder.getRegionManager(); |
| const CXXThisRegion *ThisR = RegMgr.getCXXThisRegion(ThisT, InitLoc); |
| SVal ThisV = svalBuilder.getRegionValueSymbolVal(ThisR); |
| St = Bind(St, svalBuilder.makeLoc(ThisR), ThisV); |
| } |
| |
| return St; |
| } |
| |
| Store BasicStoreManager::BindDeclInternal(Store store, const VarRegion* VR, |
| SVal* InitVal) { |
| |
| BasicValueFactory& BasicVals = StateMgr.getBasicVals(); |
| const VarDecl *VD = VR->getDecl(); |
| |
| // BasicStore does not model arrays and structs. |
| if (VD->getType()->isArrayType() || VD->getType()->isStructureOrClassType()) |
| return store; |
| |
| if (VD->hasGlobalStorage()) { |
| // Handle variables with global storage: extern, static, PrivateExtern. |
| |
| // FIXME:: static variables may have an initializer, but the second time a |
| // function is called those values may not be current. Currently, a function |
| // will not be called more than once. |
| |
| // Static global variables should not be visited here. |
| assert(!(VD->getStorageClass() == SC_Static && |
| VD->isFileVarDecl())); |
| |
| // Process static variables. |
| if (VD->getStorageClass() == SC_Static) { |
| // C99: 6.7.8 Initialization |
| // If an object that has static storage duration is not initialized |
| // explicitly, then: |
| // —if it has pointer type, it is initialized to a null pointer; |
| // —if it has arithmetic type, it is initialized to (positive or |
| // unsigned) zero; |
| if (!InitVal) { |
| QualType T = VD->getType(); |
| if (Loc::IsLocType(T)) |
| store = Bind(store, loc::MemRegionVal(VR), |
| loc::ConcreteInt(BasicVals.getValue(0, T))); |
| else if (T->isIntegerType() && T->isScalarType()) |
| store = Bind(store, loc::MemRegionVal(VR), |
| nonloc::ConcreteInt(BasicVals.getValue(0, T))); |
| } else { |
| store = Bind(store, loc::MemRegionVal(VR), *InitVal); |
| } |
| } |
| } else { |
| // Process local scalar variables. |
| QualType T = VD->getType(); |
| // BasicStore only supports scalars. |
| if ((T->isScalarType() || T->isReferenceType()) && |
| svalBuilder.getSymbolManager().canSymbolicate(T)) { |
| SVal V = InitVal ? *InitVal : UndefinedVal(); |
| store = Bind(store, loc::MemRegionVal(VR), V); |
| } |
| } |
| |
| return store; |
| } |
| |
| void BasicStoreManager::print(Store store, llvm::raw_ostream& Out, |
| const char* nl, const char *sep) { |
| |
| BindingsTy B = GetBindings(store); |
| Out << "Variables:" << nl; |
| |
| bool isFirst = true; |
| |
| for (BindingsTy::iterator I=B.begin(), E=B.end(); I != E; ++I) { |
| if (isFirst) |
| isFirst = false; |
| else |
| Out << nl; |
| |
| Out << ' ' << I.getKey() << " : " << I.getData(); |
| } |
| } |
| |
| |
| void BasicStoreManager::iterBindings(Store store, BindingsHandler& f) { |
| BindingsTy B = GetBindings(store); |
| |
| for (BindingsTy::iterator I=B.begin(), E=B.end(); I != E; ++I) |
| if (!f.HandleBinding(*this, store, I.getKey(), I.getData())) |
| return; |
| |
| } |
| |
| StoreManager::BindingsHandler::~BindingsHandler() {} |
| |
| //===----------------------------------------------------------------------===// |
| // Binding invalidation. |
| //===----------------------------------------------------------------------===// |
| |
| |
| Store BasicStoreManager::InvalidateRegions(Store store, |
| const MemRegion * const *I, |
| const MemRegion * const *End, |
| const Expr *E, unsigned Count, |
| InvalidatedSymbols *IS, |
| bool invalidateGlobals, |
| InvalidatedRegions *Regions) { |
| if (invalidateGlobals) { |
| BindingsTy B = GetBindings(store); |
| for (BindingsTy::iterator I=B.begin(), End=B.end(); I != End; ++I) { |
| const MemRegion *R = I.getKey(); |
| if (isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace())) |
| store = InvalidateRegion(store, R, E, Count, IS); |
| } |
| } |
| |
| for ( ; I != End ; ++I) { |
| const MemRegion *R = *I; |
| // Don't invalidate globals twice. |
| if (invalidateGlobals) { |
| if (isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace())) |
| continue; |
| } |
| store = InvalidateRegion(store, *I, E, Count, IS); |
| if (Regions) |
| Regions->push_back(R); |
| } |
| |
| // FIXME: This is copy-and-paste from RegionStore.cpp. |
| if (invalidateGlobals) { |
| // Bind the non-static globals memory space to a new symbol that we will |
| // use to derive the bindings for all non-static globals. |
| const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion(); |
| SVal V = |
| svalBuilder.getConjuredSymbolVal(/* SymbolTag = */ (void*) GS, E, |
| /* symbol type, doesn't matter */ Ctx.IntTy, |
| Count); |
| |
| store = Bind(store, loc::MemRegionVal(GS), V); |
| if (Regions) |
| Regions->push_back(GS); |
| } |
| |
| return store; |
| } |
| |
| |
| Store BasicStoreManager::InvalidateRegion(Store store, |
| const MemRegion *R, |
| const Expr *E, |
| unsigned Count, |
| InvalidatedSymbols *IS) { |
| R = R->StripCasts(); |
| |
| if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R))) |
| return store; |
| |
| if (IS) { |
| BindingsTy B = GetBindings(store); |
| if (BindingsTy::data_type *Val = B.lookup(R)) { |
| if (SymbolRef Sym = Val->getAsSymbol()) |
| IS->insert(Sym); |
| } |
| } |
| |
| QualType T = cast<TypedRegion>(R)->getValueType(); |
| SVal V = svalBuilder.getConjuredSymbolVal(R, E, T, Count); |
| return Bind(store, loc::MemRegionVal(R), V); |
| } |
| |