1 //== BasicStore.cpp - Basic map from Locations to Values --------*- C++ -*--==//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defined the BasicStore and BasicStoreManager classes.
12 //===----------------------------------------------------------------------===//
14 #include "clang/AST/DeclCXX.h"
15 #include "clang/AST/ExprObjC.h"
16 #include "clang/Analysis/Analyses/LiveVariables.h"
17 #include "clang/Analysis/AnalysisContext.h"
18 #include "clang/StaticAnalyzer/Core/PathSensitive/GRState.h"
19 #include "llvm/ADT/ImmutableMap.h"
21 using namespace clang;
24 typedef llvm::ImmutableMap<const MemRegion*,SVal> BindingsTy;
28 class BasicStoreSubRegionMap : public SubRegionMap {
30 BasicStoreSubRegionMap() {}
32 bool iterSubRegions(const MemRegion* R, Visitor& V) const {
33 return true; // Do nothing. No subregions.
37 class BasicStoreManager : public StoreManager {
38 BindingsTy::Factory VBFactory;
40 BasicStoreManager(GRStateManager& mgr)
41 : StoreManager(mgr), VBFactory(mgr.getAllocator()) {}
43 ~BasicStoreManager() {}
45 SubRegionMap *getSubRegionMap(Store store) {
46 return new BasicStoreSubRegionMap();
49 SVal Retrieve(Store store, Loc loc, QualType T = QualType());
51 StoreRef invalidateRegion(Store store, const MemRegion *R, const Expr *E,
52 unsigned Count, InvalidatedSymbols &IS);
54 StoreRef invalidateRegions(Store store, const MemRegion * const *Begin,
55 const MemRegion * const *End, const Expr *E,
56 unsigned Count, InvalidatedSymbols &IS,
57 bool invalidateGlobals,
58 InvalidatedRegions *Regions);
60 StoreRef scanForIvars(Stmt *B, const Decl* SelfDecl,
61 const MemRegion *SelfRegion, Store St);
63 StoreRef Bind(Store St, Loc loc, SVal V);
64 StoreRef Remove(Store St, Loc loc);
65 StoreRef getInitialStore(const LocationContext *InitLoc);
67 StoreRef BindCompoundLiteral(Store store, const CompoundLiteralExpr*,
68 const LocationContext*, SVal val) {
69 return StoreRef(store, *this);
72 /// ArrayToPointer - Used by ExprEngine::VistCast to handle implicit
73 /// conversions between arrays and pointers.
74 SVal ArrayToPointer(Loc Array) { return Array; }
76 /// removeDeadBindings - Scans a BasicStore of 'state' for dead values.
77 /// It updatees the GRState object in place with the values removed.
78 StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx,
79 SymbolReaper& SymReaper,
80 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots);
82 void iterBindings(Store store, BindingsHandler& f);
84 StoreRef BindDecl(Store store, const VarRegion *VR, SVal InitVal) {
85 return BindDeclInternal(store, VR, &InitVal);
88 StoreRef BindDeclWithNoInit(Store store, const VarRegion *VR) {
89 return BindDeclInternal(store, VR, 0);
92 StoreRef BindDeclInternal(Store store, const VarRegion *VR, SVal *InitVal);
94 static inline BindingsTy GetBindings(Store store) {
95 return BindingsTy(static_cast<const BindingsTy::TreeTy*>(store));
98 void print(Store store, llvm::raw_ostream& Out, const char* nl,
102 SVal LazyRetrieve(Store store, const TypedRegion *R);
105 } // end anonymous namespace
108 StoreManager* ento::CreateBasicStoreManager(GRStateManager& StMgr) {
109 return new BasicStoreManager(StMgr);
112 static bool isHigherOrderRawPtr(QualType T, ASTContext &C) {
113 bool foundPointer = false;
115 const PointerType *PT = T->getAs<PointerType>();
120 // intptr_t* or intptr_t**, etc?
121 if (T->isIntegerType() && C.getTypeSize(T) == C.getTypeSize(C.VoidPtrTy))
124 QualType X = C.getCanonicalType(T).getUnqualifiedType();
125 return X == C.VoidTy;
129 T = PT->getPointeeType();
133 SVal BasicStoreManager::LazyRetrieve(Store store, const TypedRegion *R) {
134 const VarRegion *VR = dyn_cast<VarRegion>(R);
138 const VarDecl *VD = VR->getDecl();
139 QualType T = VD->getType();
141 // Only handle simple types that we can symbolicate.
142 if (!SymbolManager::canSymbolicate(T) || !T->isScalarType())
145 // Globals and parameters start with symbolic values.
146 // Local variables initially are undefined.
148 // Non-static globals may have had their values reset by invalidateRegions.
149 const MemSpaceRegion *MS = VR->getMemorySpace();
150 if (isa<NonStaticGlobalSpaceRegion>(MS)) {
151 BindingsTy B = GetBindings(store);
152 // FIXME: Copy-and-pasted from RegionStore.cpp.
153 if (BindingsTy::data_type *Val = B.lookup(MS)) {
154 if (SymbolRef parentSym = Val->getAsSymbol())
155 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
157 if (Val->isZeroConstant())
158 return svalBuilder.makeZeroVal(T);
160 if (Val->isUnknownOrUndef())
163 assert(0 && "Unknown default value.");
167 if (VR->hasGlobalsOrParametersStorage() ||
168 isa<UnknownSpaceRegion>(VR->getMemorySpace()))
169 return svalBuilder.getRegionValueSymbolVal(R);
171 return UndefinedVal();
174 SVal BasicStoreManager::Retrieve(Store store, Loc loc, QualType T) {
175 if (isa<UnknownVal>(loc))
178 assert(!isa<UndefinedVal>(loc));
180 switch (loc.getSubKind()) {
182 case loc::MemRegionKind: {
183 const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion();
185 if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R) ||
186 isa<CXXThisRegion>(R)))
189 BindingsTy B = GetBindings(store);
190 BindingsTy::data_type *Val = B.lookup(R);
191 const TypedRegion *TR = cast<TypedRegion>(R);
194 return CastRetrievedVal(*Val, TR, T);
196 SVal V = LazyRetrieve(store, TR);
197 return V.isUnknownOrUndef() ? V : CastRetrievedVal(V, TR, T);
200 case loc::ObjCPropRefKind:
201 case loc::ConcreteIntKind:
202 // Support direct accesses to memory. It's up to individual checkers
207 assert (false && "Invalid Loc.");
214 StoreRef BasicStoreManager::Bind(Store store, Loc loc, SVal V) {
215 if (isa<loc::ConcreteInt>(loc))
216 return StoreRef(store, *this);
218 const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion();
220 // Special case: a default symbol assigned to the NonStaticGlobalsSpaceRegion
221 // that is used to derive other symbols.
222 if (isa<NonStaticGlobalSpaceRegion>(R)) {
223 BindingsTy B = GetBindings(store);
224 return StoreRef(VBFactory.add(B, R, V).getRoot(), *this);
227 // Special case: handle store of pointer values (Loc) to pointers via
228 // a cast to intXX_t*, void*, etc. This is needed to handle
229 // OSCompareAndSwap32Barrier/OSCompareAndSwap64Barrier.
230 if (isa<Loc>(V) || isa<nonloc::LocAsInteger>(V))
231 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
232 // FIXME: Should check for index 0.
233 QualType T = ER->getLocationType();
235 if (isHigherOrderRawPtr(T, Ctx))
236 R = ER->getSuperRegion();
239 if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R) || isa<CXXThisRegion>(R)))
240 return StoreRef(store, *this);
242 const TypedRegion *TyR = cast<TypedRegion>(R);
244 // Do not bind to arrays. We need to explicitly check for this so that
245 // we do not encounter any weirdness of trying to load/store from arrays.
246 if (TyR->isBoundable() && TyR->getValueType()->isArrayType())
247 return StoreRef(store, *this);
249 if (nonloc::LocAsInteger *X = dyn_cast<nonloc::LocAsInteger>(&V)) {
250 // Only convert 'V' to a location iff the underlying region type
251 // is a location as well.
252 // FIXME: We are allowing a store of an arbitrary location to
253 // a pointer. We may wish to flag a type error here if the types
254 // are incompatible. This may also cause lots of breakage
255 // elsewhere. Food for thought.
256 if (TyR->isBoundable() && Loc::isLocType(TyR->getValueType()))
260 BindingsTy B = GetBindings(store);
261 return StoreRef(V.isUnknown()
262 ? VBFactory.remove(B, R).getRoot()
263 : VBFactory.add(B, R, V).getRoot(), *this);
266 StoreRef BasicStoreManager::Remove(Store store, Loc loc) {
267 switch (loc.getSubKind()) {
268 case loc::MemRegionKind: {
269 const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion();
271 if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R) ||
272 isa<CXXThisRegion>(R)))
273 return StoreRef(store, *this);
275 return StoreRef(VBFactory.remove(GetBindings(store), R).getRoot(), *this);
278 assert ("Remove for given Loc type not yet implemented.");
279 return StoreRef(store, *this);
283 StoreRef BasicStoreManager::removeDeadBindings(Store store,
284 const StackFrameContext *LCtx,
285 SymbolReaper& SymReaper,
286 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots)
288 BindingsTy B = GetBindings(store);
289 typedef SVal::symbol_iterator symbol_iterator;
291 // Iterate over the variable bindings.
292 for (BindingsTy::iterator I=B.begin(), E=B.end(); I!=E ; ++I) {
293 if (const VarRegion *VR = dyn_cast<VarRegion>(I.getKey())) {
294 if (SymReaper.isLive(VR))
295 RegionRoots.push_back(VR);
299 else if (isa<ObjCIvarRegion>(I.getKey()) ||
300 isa<NonStaticGlobalSpaceRegion>(I.getKey()) ||
301 isa<CXXThisRegion>(I.getKey()))
302 RegionRoots.push_back(I.getKey());
306 // Mark the bindings in the data as live.
307 SVal X = I.getData();
308 for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI)
309 SymReaper.markLive(*SI);
312 // Scan for live variables and live symbols.
313 llvm::SmallPtrSet<const MemRegion*, 10> Marked;
315 while (!RegionRoots.empty()) {
316 const MemRegion* MR = RegionRoots.back();
317 RegionRoots.pop_back();
320 if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(MR)) {
321 SymReaper.markLive(SymR->getSymbol());
324 else if (isa<VarRegion>(MR) || isa<ObjCIvarRegion>(MR) ||
325 isa<NonStaticGlobalSpaceRegion>(MR) || isa<CXXThisRegion>(MR)) {
326 if (Marked.count(MR))
330 SVal X = Retrieve(store, loc::MemRegionVal(MR));
332 // FIXME: We need to handle symbols nested in region definitions.
333 for (symbol_iterator SI=X.symbol_begin(),SE=X.symbol_end();SI!=SE;++SI)
334 SymReaper.markLive(*SI);
336 if (!isa<loc::MemRegionVal>(X))
339 const loc::MemRegionVal& LVD = cast<loc::MemRegionVal>(X);
340 RegionRoots.push_back(LVD.getRegion());
343 else if (const SubRegion* R = dyn_cast<SubRegion>(MR))
344 MR = R->getSuperRegion();
350 // Remove dead variable bindings.
351 StoreRef newStore(store, *this);
352 for (BindingsTy::iterator I=B.begin(), E=B.end(); I!=E ; ++I) {
353 const MemRegion* R = I.getKey();
355 if (!Marked.count(R)) {
356 newStore = Remove(newStore.getStore(), svalBuilder.makeLoc(R));
357 SVal X = I.getData();
359 for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI)
360 SymReaper.maybeDead(*SI);
367 StoreRef BasicStoreManager::scanForIvars(Stmt *B, const Decl* SelfDecl,
368 const MemRegion *SelfRegion,
371 StoreRef newStore(St, *this);
373 for (Stmt::child_iterator CI=B->child_begin(), CE=B->child_end();
379 // Check if the statement is an ivar reference. We only
380 // care about self.ivar.
381 if (ObjCIvarRefExpr *IV = dyn_cast<ObjCIvarRefExpr>(*CI)) {
382 const Expr *Base = IV->getBase()->IgnoreParenCasts();
383 if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Base)) {
384 if (DR->getDecl() == SelfDecl) {
385 const ObjCIvarRegion *IVR = MRMgr.getObjCIvarRegion(IV->getDecl(),
387 SVal X = svalBuilder.getRegionValueSymbolVal(IVR);
388 newStore = Bind(newStore.getStore(), svalBuilder.makeLoc(IVR), X);
393 newStore = scanForIvars(*CI, SelfDecl, SelfRegion, newStore.getStore());
399 StoreRef BasicStoreManager::getInitialStore(const LocationContext *InitLoc) {
400 // The LiveVariables information already has a compilation of all VarDecls
401 // used in the function. Iterate through this set, and "symbolicate"
402 // any VarDecl whose value originally comes from outside the function.
403 typedef LiveVariables::AnalysisDataTy LVDataTy;
404 LVDataTy& D = InitLoc->getLiveVariables()->getAnalysisData();
405 StoreRef St(VBFactory.getEmptyMap().getRoot(), *this);
407 for (LVDataTy::decl_iterator I=D.begin_decl(), E=D.end_decl(); I != E; ++I) {
408 const NamedDecl* ND = I->first;
410 // Handle implicit parameters.
411 if (const ImplicitParamDecl* PD = dyn_cast<ImplicitParamDecl>(ND)) {
412 const Decl& CD = *InitLoc->getDecl();
413 if (const ObjCMethodDecl* MD = dyn_cast<ObjCMethodDecl>(&CD)) {
414 if (MD->getSelfDecl() == PD) {
415 // FIXME: Add type constraints (when they become available) to
416 // SelfRegion? (i.e., it implements MD->getClassInterface()).
417 const VarRegion *VR = MRMgr.getVarRegion(PD, InitLoc);
418 const MemRegion *SelfRegion =
419 svalBuilder.getRegionValueSymbolVal(VR).getAsRegion();
421 St = Bind(St.getStore(), svalBuilder.makeLoc(VR),
422 loc::MemRegionVal(SelfRegion));
423 // Scan the method for ivar references. While this requires an
424 // entire AST scan, the cost should not be high in practice.
425 St = scanForIvars(MD->getBody(), PD, SelfRegion, St.getStore());
431 if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(InitLoc->getDecl())) {
432 // For C++ non-static member variables, add a symbolic region for 'this' in
433 // the initial stack frame.
434 if (MD->isInstance()) {
435 QualType ThisT = MD->getThisType(StateMgr.getContext());
436 MemRegionManager &RegMgr = svalBuilder.getRegionManager();
437 const CXXThisRegion *ThisR = RegMgr.getCXXThisRegion(ThisT, InitLoc);
438 SVal ThisV = svalBuilder.getRegionValueSymbolVal(ThisR);
439 St = Bind(St.getStore(), svalBuilder.makeLoc(ThisR), ThisV);
446 StoreRef BasicStoreManager::BindDeclInternal(Store store, const VarRegion* VR,
449 BasicValueFactory& BasicVals = StateMgr.getBasicVals();
450 const VarDecl *VD = VR->getDecl();
451 StoreRef newStore(store, *this);
453 // BasicStore does not model arrays and structs.
454 if (VD->getType()->isArrayType() || VD->getType()->isStructureOrClassType())
457 if (VD->hasGlobalStorage()) {
458 // Handle variables with global storage: extern, static, PrivateExtern.
460 // FIXME:: static variables may have an initializer, but the second time a
461 // function is called those values may not be current. Currently, a function
462 // will not be called more than once.
464 // Static global variables should not be visited here.
465 assert(!(VD->getStorageClass() == SC_Static &&
466 VD->isFileVarDecl()));
468 // Process static variables.
469 if (VD->getStorageClass() == SC_Static) {
470 // C99: 6.7.8 Initialization
471 // If an object that has static storage duration is not initialized
473 // -if it has pointer type, it is initialized to a null pointer;
474 // -if it has arithmetic type, it is initialized to (positive or
477 QualType T = VD->getType();
478 if (Loc::isLocType(T))
479 newStore = Bind(store, loc::MemRegionVal(VR),
480 loc::ConcreteInt(BasicVals.getValue(0, T)));
481 else if (T->isIntegerType() && T->isScalarType())
482 newStore = Bind(store, loc::MemRegionVal(VR),
483 nonloc::ConcreteInt(BasicVals.getValue(0, T)));
485 newStore = Bind(store, loc::MemRegionVal(VR), *InitVal);
489 // Process local scalar variables.
490 QualType T = VD->getType();
491 // BasicStore only supports scalars.
492 if ((T->isScalarType() || T->isReferenceType()) &&
493 svalBuilder.getSymbolManager().canSymbolicate(T)) {
494 SVal V = InitVal ? *InitVal : UndefinedVal();
495 newStore = Bind(store, loc::MemRegionVal(VR), V);
502 void BasicStoreManager::print(Store store, llvm::raw_ostream& Out,
503 const char* nl, const char *sep) {
505 BindingsTy B = GetBindings(store);
506 Out << "Variables:" << nl;
510 for (BindingsTy::iterator I=B.begin(), E=B.end(); I != E; ++I) {
516 Out << ' ' << I.getKey() << " : " << I.getData();
521 void BasicStoreManager::iterBindings(Store store, BindingsHandler& f) {
522 BindingsTy B = GetBindings(store);
524 for (BindingsTy::iterator I=B.begin(), E=B.end(); I != E; ++I)
525 if (!f.HandleBinding(*this, store, I.getKey(), I.getData()))
530 StoreManager::BindingsHandler::~BindingsHandler() {}
532 //===----------------------------------------------------------------------===//
533 // Binding invalidation.
534 //===----------------------------------------------------------------------===//
537 StoreRef BasicStoreManager::invalidateRegions(Store store,
538 const MemRegion * const *I,
539 const MemRegion * const *End,
540 const Expr *E, unsigned Count,
541 InvalidatedSymbols &IS,
542 bool invalidateGlobals,
543 InvalidatedRegions *Regions) {
544 StoreRef newStore(store, *this);
546 if (invalidateGlobals) {
547 BindingsTy B = GetBindings(store);
548 for (BindingsTy::iterator I=B.begin(), End=B.end(); I != End; ++I) {
549 const MemRegion *R = I.getKey();
550 if (isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace()))
551 newStore = invalidateRegion(newStore.getStore(), R, E, Count, IS);
555 for ( ; I != End ; ++I) {
556 const MemRegion *R = *I;
557 // Don't invalidate globals twice.
558 if (invalidateGlobals) {
559 if (isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace()))
562 newStore = invalidateRegion(newStore.getStore(), *I, E, Count, IS);
564 Regions->push_back(R);
567 // FIXME: This is copy-and-paste from RegionStore.cpp.
568 if (invalidateGlobals) {
569 // Bind the non-static globals memory space to a new symbol that we will
570 // use to derive the bindings for all non-static globals.
571 const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion();
573 svalBuilder.getConjuredSymbolVal(/* SymbolTag = */ (void*) GS, E,
574 /* symbol type, doesn't matter */ Ctx.IntTy,
577 newStore = Bind(newStore.getStore(), loc::MemRegionVal(GS), V);
579 Regions->push_back(GS);
586 StoreRef BasicStoreManager::invalidateRegion(Store store,
590 InvalidatedSymbols &IS) {
593 if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R)))
594 return StoreRef(store, *this);
596 BindingsTy B = GetBindings(store);
597 if (BindingsTy::data_type *Val = B.lookup(R)) {
598 if (SymbolRef Sym = Val->getAsSymbol())
602 QualType T = cast<TypedRegion>(R)->getValueType();
603 SVal V = svalBuilder.getConjuredSymbolVal(R, E, T, Count);
604 return Bind(store, loc::MemRegionVal(R), V);