summaryrefslogtreecommitdiffstats
path: root/contrib/llvm/tools/clang/lib/Checker/BasicStore.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'contrib/llvm/tools/clang/lib/Checker/BasicStore.cpp')
-rw-r--r--contrib/llvm/tools/clang/lib/Checker/BasicStore.cpp580
1 files changed, 0 insertions, 580 deletions
diff --git a/contrib/llvm/tools/clang/lib/Checker/BasicStore.cpp b/contrib/llvm/tools/clang/lib/Checker/BasicStore.cpp
deleted file mode 100644
index f82e1b2..0000000
--- a/contrib/llvm/tools/clang/lib/Checker/BasicStore.cpp
+++ /dev/null
@@ -1,580 +0,0 @@
-//== 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/ExprObjC.h"
-#include "clang/Analysis/Analyses/LiveVariables.h"
-#include "clang/Analysis/AnalysisContext.h"
-#include "clang/Checker/PathSensitive/GRState.h"
-#include "llvm/ADT/ImmutableMap.h"
-
-using namespace clang;
-
-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 GRExprEngine::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* clang::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 ValMgr.getDerivedRegionValueSymbolVal(parentSym, R);
-
- if (Val->isZeroConstant())
- return ValMgr.makeZeroVal(T);
-
- if (Val->isUnknownOrUndef())
- return *Val;
-
- assert(0 && "Unknown default value.");
- }
- }
-
- if (VR->hasGlobalsOrParametersStorage() ||
- isa<UnknownSpaceRegion>(VR->getMemorySpace()))
- return ValMgr.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)))
- 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:
- // Some clients may call GetSVal with such an option simply because
- // they are doing a quick scan through their Locs (potentially to
- // invalidate their bindings). Just return Undefined.
- return UndefinedVal();
-
- 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)))
- 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)))
- 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()))
- 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)) {
- 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, ValMgr.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 = ValMgr.getRegionValueSymbolVal(IVR);
- St = Bind(St, ValMgr.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 =
- ValMgr.getRegionValueSymbolVal(VR).getAsRegion();
- assert(SelfRegion);
- St = Bind(St, ValMgr.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);
- }
- }
- }
- }
-
- 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() && ValMgr.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 =
- ValMgr.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 = ValMgr.getConjuredSymbolVal(R, E, T, Count);
- return Bind(store, loc::MemRegionVal(R), V);
-}
-
OpenPOWER on IntegriCloud