blob: 4fb0387ed58c2b578ee48a2c16dbbdc151ea81d8 [file] [log] [blame]
Ted Kremenek4323a572008-07-10 22:03:41 +00001//== BasicStore.cpp - Basic map from Locations to Values --------*- C++ -*--==//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defined the BasicStore and BasicStoreManager classes.
11//
12//===----------------------------------------------------------------------===//
13
Marcin Swiderski11b39d42010-11-16 07:15:33 +000014#include "clang/AST/DeclCXX.h"
Ted Kremenekf684d562009-03-05 18:08:28 +000015#include "clang/AST/ExprObjC.h"
Ted Kremenek5f81c442008-08-28 23:31:31 +000016#include "clang/Analysis/Analyses/LiveVariables.h"
Ted Kremenek1309f9a2010-01-25 04:41:41 +000017#include "clang/Analysis/AnalysisContext.h"
18#include "clang/Checker/PathSensitive/GRState.h"
Benjamin Kramer6cb7c1a2009-08-23 12:08:50 +000019#include "llvm/ADT/ImmutableMap.h"
Ted Kremenek4323a572008-07-10 22:03:41 +000020
21using namespace clang;
22
Mike Stump1eb44332009-09-09 15:08:12 +000023typedef llvm::ImmutableMap<const MemRegion*,SVal> BindingsTy;
Ted Kremenek60dbad82008-09-03 03:06:11 +000024
Ted Kremenek4323a572008-07-10 22:03:41 +000025namespace {
Mike Stump1eb44332009-09-09 15:08:12 +000026
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +000027class BasicStoreSubRegionMap : public SubRegionMap {
Ted Kremenek59e8f112009-03-03 01:35:36 +000028public:
29 BasicStoreSubRegionMap() {}
30
Ted Kremenek5dc27462009-03-03 02:51:43 +000031 bool iterSubRegions(const MemRegion* R, Visitor& V) const {
Ted Kremenek39fc7152009-03-05 16:41:21 +000032 return true; // Do nothing. No subregions.
Ted Kremenek59e8f112009-03-03 01:35:36 +000033 }
34};
Mike Stump1eb44332009-09-09 15:08:12 +000035
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +000036class BasicStoreManager : public StoreManager {
Ted Kremenek2c8e7882009-03-05 16:32:59 +000037 BindingsTy::Factory VBFactory;
Ted Kremenek4323a572008-07-10 22:03:41 +000038public:
Ted Kremenekf7a0cf42009-07-29 21:43:22 +000039 BasicStoreManager(GRStateManager& mgr)
Ted Kremenek82cd37c2009-08-21 23:25:54 +000040 : StoreManager(mgr), VBFactory(mgr.getAllocator()) {}
Mike Stump1eb44332009-09-09 15:08:12 +000041
Ted Kremenek9deb0e32008-10-24 20:32:16 +000042 ~BasicStoreManager() {}
Ted Kremenek4323a572008-07-10 22:03:41 +000043
Zhongxing Xuf5416bd2010-02-05 05:18:47 +000044 SubRegionMap *getSubRegionMap(Store store) {
Ted Kremenek14453bf2009-03-03 19:02:42 +000045 return new BasicStoreSubRegionMap();
Ted Kremenek59e8f112009-03-03 01:35:36 +000046 }
47
Zhongxing Xu576bb922010-02-05 03:01:53 +000048 SVal Retrieve(Store store, Loc loc, QualType T = QualType());
Mike Stump1eb44332009-09-09 15:08:12 +000049
Ted Kremenekdcee3ce2010-07-01 20:16:50 +000050 Store InvalidateRegion(Store store, const MemRegion *R, const Expr *E,
Zhongxing Xub4a9c612010-02-05 05:06:13 +000051 unsigned Count, InvalidatedSymbols *IS);
Zhongxing Xu4193eca2008-12-20 06:32:12 +000052
Ted Kremenekdcee3ce2010-07-01 20:16:50 +000053 Store InvalidateRegions(Store store, const MemRegion * const *Begin,
54 const MemRegion * const *End, const Expr *E,
55 unsigned Count, InvalidatedSymbols *IS,
Jordy Rosec2b7dfa2010-08-14 20:44:32 +000056 bool invalidateGlobals, InvalidatedRegions *Regions);
Ted Kremenekdcee3ce2010-07-01 20:16:50 +000057
Ted Kremenek82cd37c2009-08-21 23:25:54 +000058 Store scanForIvars(Stmt *B, const Decl* SelfDecl,
59 const MemRegion *SelfRegion, Store St);
Mike Stump1eb44332009-09-09 15:08:12 +000060
Zhongxing Xub241cf62010-02-08 08:48:05 +000061 Store Bind(Store St, Loc loc, SVal V);
Ted Kremenekc6ed3842009-01-07 22:56:17 +000062 Store Remove(Store St, Loc loc);
Zhongxing Xu17fd8632009-08-17 06:19:58 +000063 Store getInitialStore(const LocationContext *InitLoc);
Zhongxing Xubc678fd2008-10-07 01:31:04 +000064
Zhongxing Xub4a9c612010-02-05 05:06:13 +000065 Store BindCompoundLiteral(Store store, const CompoundLiteralExpr*,
66 const LocationContext*, SVal val) {
67 return store;
Ted Kremenek4f090272008-10-27 21:54:31 +000068 }
Mike Stump1eb44332009-09-09 15:08:12 +000069
Ted Kremenek9deb0e32008-10-24 20:32:16 +000070 /// ArrayToPointer - Used by GRExprEngine::VistCast to handle implicit
71 /// conversions between arrays and pointers.
Zhongxing Xuf1d537f2009-03-30 05:55:46 +000072 SVal ArrayToPointer(Loc Array) { return Array; }
Mike Stump1eb44332009-09-09 15:08:12 +000073
Ted Kremenek2ed14be2008-12-05 00:47:52 +000074 /// RemoveDeadBindings - Scans a BasicStore of 'state' for dead values.
Ted Kremenek2f26bc32009-08-02 04:45:08 +000075 /// It updatees the GRState object in place with the values removed.
Zhongxing Xu5e4cb342010-08-15 12:45:09 +000076 Store RemoveDeadBindings(Store store, const StackFrameContext *LCtx,
77 SymbolReaper& SymReaper,
Ted Kremenek2f26bc32009-08-02 04:45:08 +000078 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots);
Zhongxing Xubbe8ff42008-08-21 22:34:01 +000079
Ted Kremenek9deb0e32008-10-24 20:32:16 +000080 void iterBindings(Store store, BindingsHandler& f);
Ted Kremenek60dbad82008-09-03 03:06:11 +000081
Zhongxing Xub4a9c612010-02-05 05:06:13 +000082 Store BindDecl(Store store, const VarRegion *VR, SVal InitVal) {
83 return BindDeclInternal(store, VR, &InitVal);
Zhongxing Xu4193eca2008-12-20 06:32:12 +000084 }
85
Zhongxing Xub4a9c612010-02-05 05:06:13 +000086 Store BindDeclWithNoInit(Store store, const VarRegion *VR) {
87 return BindDeclInternal(store, VR, 0);
Zhongxing Xu4193eca2008-12-20 06:32:12 +000088 }
89
Ted Kremenekf6f56d42009-11-04 00:09:15 +000090 Store BindDeclInternal(Store store, const VarRegion *VR, SVal *InitVal);
Zhongxing Xubbe8ff42008-08-21 22:34:01 +000091
Ted Kremenek2c8e7882009-03-05 16:32:59 +000092 static inline BindingsTy GetBindings(Store store) {
93 return BindingsTy(static_cast<const BindingsTy::TreeTy*>(store));
Ted Kremeneka622d8c2008-08-19 22:24:03 +000094 }
95
Ted Kremenek53ba0b62009-06-24 23:06:47 +000096 void print(Store store, llvm::raw_ostream& Out, const char* nl,
97 const char *sep);
Zhongxing Xua1718c72009-04-03 07:33:13 +000098
99private:
Ted Kremenek5ba290a2010-03-02 21:43:54 +0000100 SVal LazyRetrieve(Store store, const TypedRegion *R);
Ted Kremenek60dbad82008-09-03 03:06:11 +0000101};
Mike Stump1eb44332009-09-09 15:08:12 +0000102
Ted Kremenek4323a572008-07-10 22:03:41 +0000103} // end anonymous namespace
104
105
Ted Kremenek5f81c442008-08-28 23:31:31 +0000106StoreManager* clang::CreateBasicStoreManager(GRStateManager& StMgr) {
107 return new BasicStoreManager(StMgr);
Ted Kremenekd0c4b282008-08-25 19:33:03 +0000108}
Zhongxing Xu933c3e12008-10-21 06:54:23 +0000109
Ted Kremenek5fa93d52009-04-29 16:03:27 +0000110static bool isHigherOrderRawPtr(QualType T, ASTContext &C) {
Ted Kremenek1670e402009-04-11 00:11:10 +0000111 bool foundPointer = false;
Mike Stump1eb44332009-09-09 15:08:12 +0000112 while (1) {
Ted Kremenek6217b802009-07-29 21:53:49 +0000113 const PointerType *PT = T->getAs<PointerType>();
Ted Kremenek1670e402009-04-11 00:11:10 +0000114 if (!PT) {
115 if (!foundPointer)
116 return false;
Mike Stump1eb44332009-09-09 15:08:12 +0000117
Ted Kremenek5fa93d52009-04-29 16:03:27 +0000118 // intptr_t* or intptr_t**, etc?
119 if (T->isIntegerType() && C.getTypeSize(T) == C.getTypeSize(C.VoidPtrTy))
120 return true;
Mike Stump1eb44332009-09-09 15:08:12 +0000121
Ted Kremenek1670e402009-04-11 00:11:10 +0000122 QualType X = C.getCanonicalType(T).getUnqualifiedType();
123 return X == C.VoidTy;
124 }
Mike Stump1eb44332009-09-09 15:08:12 +0000125
Ted Kremenek1670e402009-04-11 00:11:10 +0000126 foundPointer = true;
127 T = PT->getPointeeType();
Mike Stump1eb44332009-09-09 15:08:12 +0000128 }
Ted Kremenek1670e402009-04-11 00:11:10 +0000129}
Mike Stump1eb44332009-09-09 15:08:12 +0000130
Ted Kremenek5ba290a2010-03-02 21:43:54 +0000131SVal BasicStoreManager::LazyRetrieve(Store store, const TypedRegion *R) {
132 const VarRegion *VR = dyn_cast<VarRegion>(R);
133 if (!VR)
134 return UnknownVal();
135
136 const VarDecl *VD = VR->getDecl();
137 QualType T = VD->getType();
138
139 // Only handle simple types that we can symbolicate.
140 if (!SymbolManager::canSymbolicate(T) || !T->isScalarType())
141 return UnknownVal();
142
143 // Globals and parameters start with symbolic values.
144 // Local variables initially are undefined.
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000145
146 // Non-static globals may have had their values reset by InvalidateRegions.
147 const MemSpaceRegion *MS = VR->getMemorySpace();
148 if (isa<NonStaticGlobalSpaceRegion>(MS)) {
149 BindingsTy B = GetBindings(store);
150 // FIXME: Copy-and-pasted from RegionStore.cpp.
151 if (BindingsTy::data_type *Val = B.lookup(MS)) {
152 if (SymbolRef parentSym = Val->getAsSymbol())
153 return ValMgr.getDerivedRegionValueSymbolVal(parentSym, R);
154
155 if (Val->isZeroConstant())
156 return ValMgr.makeZeroVal(T);
157
158 if (Val->isUnknownOrUndef())
159 return *Val;
160
161 assert(0 && "Unknown default value.");
162 }
163 }
164
Ted Kremenek30986dd2010-03-10 00:18:08 +0000165 if (VR->hasGlobalsOrParametersStorage() ||
166 isa<UnknownSpaceRegion>(VR->getMemorySpace()))
Ted Kremenek5ba290a2010-03-02 21:43:54 +0000167 return ValMgr.getRegionValueSymbolVal(R);
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000168
Ted Kremenek5ba290a2010-03-02 21:43:54 +0000169 return UndefinedVal();
170}
171
Zhongxing Xu576bb922010-02-05 03:01:53 +0000172SVal BasicStoreManager::Retrieve(Store store, Loc loc, QualType T) {
Ted Kremenekc6ed3842009-01-07 22:56:17 +0000173 if (isa<UnknownVal>(loc))
Zhongxing Xuc999ed72010-02-04 02:39:47 +0000174 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000175
Ted Kremenek1894dce2009-08-25 20:51:30 +0000176 assert(!isa<UndefinedVal>(loc));
Mike Stump1eb44332009-09-09 15:08:12 +0000177
Ted Kremenekc6ed3842009-01-07 22:56:17 +0000178 switch (loc.getSubKind()) {
Ted Kremenek4323a572008-07-10 22:03:41 +0000179
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000180 case loc::MemRegionKind: {
Ted Kremenekf684d562009-03-05 18:08:28 +0000181 const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion();
Mike Stump1eb44332009-09-09 15:08:12 +0000182
Marcin Swiderski11b39d42010-11-16 07:15:33 +0000183 if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R) ||
184 isa<CXXThisRegion>(R)))
Zhongxing Xuc999ed72010-02-04 02:39:47 +0000185 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000186
Zhongxing Xu576bb922010-02-05 03:01:53 +0000187 BindingsTy B = GetBindings(store);
Ted Kremenek1894dce2009-08-25 20:51:30 +0000188 BindingsTy::data_type *Val = B.lookup(R);
Ted Kremenek5ba290a2010-03-02 21:43:54 +0000189 const TypedRegion *TR = cast<TypedRegion>(R);
Mike Stump1eb44332009-09-09 15:08:12 +0000190
Ted Kremenek5ba290a2010-03-02 21:43:54 +0000191 if (Val)
192 return CastRetrievedVal(*Val, TR, T);
Mike Stump1eb44332009-09-09 15:08:12 +0000193
Ted Kremenek5ba290a2010-03-02 21:43:54 +0000194 SVal V = LazyRetrieve(store, TR);
195 return V.isUnknownOrUndef() ? V : CastRetrievedVal(V, TR, T);
Ted Kremenek4323a572008-07-10 22:03:41 +0000196 }
Mike Stump1eb44332009-09-09 15:08:12 +0000197
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000198 case loc::ConcreteIntKind:
Ted Kremenek29836f92010-11-11 23:10:10 +0000199 // Support direct accesses to memory. It's up to individual checkers
200 // to flag an error.
201 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000202
Ted Kremenek4323a572008-07-10 22:03:41 +0000203 default:
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000204 assert (false && "Invalid Loc.");
Ted Kremenek4323a572008-07-10 22:03:41 +0000205 break;
206 }
Mike Stump1eb44332009-09-09 15:08:12 +0000207
Zhongxing Xuc999ed72010-02-04 02:39:47 +0000208 return UnknownVal();
Ted Kremenek4323a572008-07-10 22:03:41 +0000209}
Mike Stump1eb44332009-09-09 15:08:12 +0000210
Zhongxing Xub241cf62010-02-08 08:48:05 +0000211Store BasicStoreManager::Bind(Store store, Loc loc, SVal V) {
Zhongxing Xu87453d12009-06-28 10:16:11 +0000212 if (isa<loc::ConcreteInt>(loc))
213 return store;
214
Zhongxing Xuc2a650a2009-06-28 09:26:15 +0000215 const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion();
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000216
217 // Special case: a default symbol assigned to the NonStaticGlobalsSpaceRegion
218 // that is used to derive other symbols.
219 if (isa<NonStaticGlobalSpaceRegion>(R)) {
220 BindingsTy B = GetBindings(store);
Ted Kremenek3baf6722010-11-24 00:54:37 +0000221 return VBFactory.add(B, R, V).getRoot();
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000222 }
223
Zhongxing Xuc2a650a2009-06-28 09:26:15 +0000224 // Special case: handle store of pointer values (Loc) to pointers via
225 // a cast to intXX_t*, void*, etc. This is needed to handle
226 // OSCompareAndSwap32Barrier/OSCompareAndSwap64Barrier.
227 if (isa<Loc>(V) || isa<nonloc::LocAsInteger>(V))
228 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
229 // FIXME: Should check for index 0.
Zhongxing Xu018220c2010-08-11 06:10:55 +0000230 QualType T = ER->getLocationType();
Mike Stump1eb44332009-09-09 15:08:12 +0000231
Zhongxing Xu57663fe2010-08-15 10:08:38 +0000232 if (isHigherOrderRawPtr(T, Ctx))
Zhongxing Xuc2a650a2009-06-28 09:26:15 +0000233 R = ER->getSuperRegion();
Mike Stump1eb44332009-09-09 15:08:12 +0000234 }
235
Marcin Swiderski11b39d42010-11-16 07:15:33 +0000236 if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R) || isa<CXXThisRegion>(R)))
Zhongxing Xuc2a650a2009-06-28 09:26:15 +0000237 return store;
Ted Kremenek82cd37c2009-08-21 23:25:54 +0000238
Ted Kremenekab2f43c2009-08-25 23:29:04 +0000239 const TypedRegion *TyR = cast<TypedRegion>(R);
Mike Stump1eb44332009-09-09 15:08:12 +0000240
Ted Kremenekab2f43c2009-08-25 23:29:04 +0000241 // Do not bind to arrays. We need to explicitly check for this so that
242 // we do not encounter any weirdness of trying to load/store from arrays.
Zhongxing Xu018220c2010-08-11 06:10:55 +0000243 if (TyR->isBoundable() && TyR->getValueType()->isArrayType())
Mike Stump1eb44332009-09-09 15:08:12 +0000244 return store;
Ted Kremenekab2f43c2009-08-25 23:29:04 +0000245
Zhongxing Xuc2a650a2009-06-28 09:26:15 +0000246 if (nonloc::LocAsInteger *X = dyn_cast<nonloc::LocAsInteger>(&V)) {
247 // Only convert 'V' to a location iff the underlying region type
248 // is a location as well.
249 // FIXME: We are allowing a store of an arbitrary location to
250 // a pointer. We may wish to flag a type error here if the types
251 // are incompatible. This may also cause lots of breakage
252 // elsewhere. Food for thought.
Zhongxing Xu018220c2010-08-11 06:10:55 +0000253 if (TyR->isBoundable() && Loc::IsLocType(TyR->getValueType()))
Ted Kremenekab2f43c2009-08-25 23:29:04 +0000254 V = X->getLoc();
Ted Kremenek4323a572008-07-10 22:03:41 +0000255 }
Zhongxing Xuc2a650a2009-06-28 09:26:15 +0000256
257 BindingsTy B = GetBindings(store);
258 return V.isUnknown()
Ted Kremenek3baf6722010-11-24 00:54:37 +0000259 ? VBFactory.remove(B, R).getRoot()
260 : VBFactory.add(B, R, V).getRoot();
Ted Kremenek4323a572008-07-10 22:03:41 +0000261}
262
Ted Kremenekc6ed3842009-01-07 22:56:17 +0000263Store BasicStoreManager::Remove(Store store, Loc loc) {
264 switch (loc.getSubKind()) {
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000265 case loc::MemRegionKind: {
Ted Kremenekf684d562009-03-05 18:08:28 +0000266 const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion();
Mike Stump1eb44332009-09-09 15:08:12 +0000267
Marcin Swiderski11b39d42010-11-16 07:15:33 +0000268 if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R) ||
269 isa<CXXThisRegion>(R)))
Ted Kremenek9e240492008-10-04 05:50:14 +0000270 return store;
Mike Stump1eb44332009-09-09 15:08:12 +0000271
Ted Kremenek3baf6722010-11-24 00:54:37 +0000272 return VBFactory.remove(GetBindings(store), R).getRoot();
Ted Kremenekf59bf482008-07-17 18:38:48 +0000273 }
Ted Kremenek4323a572008-07-10 22:03:41 +0000274 default:
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000275 assert ("Remove for given Loc type not yet implemented.");
Ted Kremenekf59bf482008-07-17 18:38:48 +0000276 return store;
Ted Kremenek4323a572008-07-10 22:03:41 +0000277 }
278}
Ted Kremenekf59bf482008-07-17 18:38:48 +0000279
Zhongxing Xu5e4cb342010-08-15 12:45:09 +0000280Store BasicStoreManager::RemoveDeadBindings(Store store,
Zhongxing Xu17ddf1c2010-03-17 03:35:08 +0000281 const StackFrameContext *LCtx,
Zhongxing Xu72119c42010-02-05 05:34:29 +0000282 SymbolReaper& SymReaper,
Ted Kremenek2f26bc32009-08-02 04:45:08 +0000283 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots)
Mike Stump1eb44332009-09-09 15:08:12 +0000284{
Ted Kremenek2c8e7882009-03-05 16:32:59 +0000285 BindingsTy B = GetBindings(store);
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000286 typedef SVal::symbol_iterator symbol_iterator;
Mike Stump1eb44332009-09-09 15:08:12 +0000287
Ted Kremenekf59bf482008-07-17 18:38:48 +0000288 // Iterate over the variable bindings.
Ted Kremenek2c8e7882009-03-05 16:32:59 +0000289 for (BindingsTy::iterator I=B.begin(), E=B.end(); I!=E ; ++I) {
Ted Kremenekf684d562009-03-05 18:08:28 +0000290 if (const VarRegion *VR = dyn_cast<VarRegion>(I.getKey())) {
Jordy Rose7dadf792010-07-01 20:09:55 +0000291 if (SymReaper.isLive(VR))
Ted Kremenekf684d562009-03-05 18:08:28 +0000292 RegionRoots.push_back(VR);
293 else
294 continue;
Ted Kremenekf59bf482008-07-17 18:38:48 +0000295 }
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000296 else if (isa<ObjCIvarRegion>(I.getKey()) ||
Marcin Swiderski11b39d42010-11-16 07:15:33 +0000297 isa<NonStaticGlobalSpaceRegion>(I.getKey()) ||
298 isa<CXXThisRegion>(I.getKey()))
Ted Kremenekf684d562009-03-05 18:08:28 +0000299 RegionRoots.push_back(I.getKey());
Ted Kremenekf684d562009-03-05 18:08:28 +0000300 else
301 continue;
Mike Stump1eb44332009-09-09 15:08:12 +0000302
Ted Kremenekf684d562009-03-05 18:08:28 +0000303 // Mark the bindings in the data as live.
304 SVal X = I.getData();
305 for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI)
306 SymReaper.markLive(*SI);
Ted Kremenekbe912242009-03-05 16:31:07 +0000307 }
Mike Stump1eb44332009-09-09 15:08:12 +0000308
Ted Kremenekf59bf482008-07-17 18:38:48 +0000309 // Scan for live variables and live symbols.
Ted Kremenekf684d562009-03-05 18:08:28 +0000310 llvm::SmallPtrSet<const MemRegion*, 10> Marked;
Mike Stump1eb44332009-09-09 15:08:12 +0000311
Ted Kremenek9e240492008-10-04 05:50:14 +0000312 while (!RegionRoots.empty()) {
Ted Kremenek134e7492008-10-17 22:52:40 +0000313 const MemRegion* MR = RegionRoots.back();
Ted Kremenek9e240492008-10-04 05:50:14 +0000314 RegionRoots.pop_back();
Mike Stump1eb44332009-09-09 15:08:12 +0000315
Ted Kremenek134e7492008-10-17 22:52:40 +0000316 while (MR) {
317 if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(MR)) {
Ted Kremenek241677a2009-01-21 22:26:05 +0000318 SymReaper.markLive(SymR->getSymbol());
Ted Kremenek134e7492008-10-17 22:52:40 +0000319 break;
320 }
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000321 else if (isa<VarRegion>(MR) || isa<ObjCIvarRegion>(MR) ||
Marcin Swiderski11b39d42010-11-16 07:15:33 +0000322 isa<NonStaticGlobalSpaceRegion>(MR) || isa<CXXThisRegion>(MR)) {
Ted Kremenekf684d562009-03-05 18:08:28 +0000323 if (Marked.count(MR))
Ted Kremenek134e7492008-10-17 22:52:40 +0000324 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000325
326 Marked.insert(MR);
Zhongxing Xu72119c42010-02-05 05:34:29 +0000327 SVal X = Retrieve(store, loc::MemRegionVal(MR));
Mike Stump1eb44332009-09-09 15:08:12 +0000328
Ted Kremenek134e7492008-10-17 22:52:40 +0000329 // FIXME: We need to handle symbols nested in region definitions.
Ted Kremenek241677a2009-01-21 22:26:05 +0000330 for (symbol_iterator SI=X.symbol_begin(),SE=X.symbol_end();SI!=SE;++SI)
331 SymReaper.markLive(*SI);
Mike Stump1eb44332009-09-09 15:08:12 +0000332
Ted Kremenek134e7492008-10-17 22:52:40 +0000333 if (!isa<loc::MemRegionVal>(X))
334 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000335
Ted Kremenek134e7492008-10-17 22:52:40 +0000336 const loc::MemRegionVal& LVD = cast<loc::MemRegionVal>(X);
337 RegionRoots.push_back(LVD.getRegion());
338 break;
339 }
340 else if (const SubRegion* R = dyn_cast<SubRegion>(MR))
341 MR = R->getSuperRegion();
342 else
343 break;
344 }
Ted Kremenekf59bf482008-07-17 18:38:48 +0000345 }
Mike Stump1eb44332009-09-09 15:08:12 +0000346
347 // Remove dead variable bindings.
Ted Kremenek2c8e7882009-03-05 16:32:59 +0000348 for (BindingsTy::iterator I=B.begin(), E=B.end(); I!=E ; ++I) {
Ted Kremenekf684d562009-03-05 18:08:28 +0000349 const MemRegion* R = I.getKey();
Mike Stump1eb44332009-09-09 15:08:12 +0000350
Ted Kremenek9e240492008-10-04 05:50:14 +0000351 if (!Marked.count(R)) {
Zhongxing Xud91ee272009-06-23 09:02:15 +0000352 store = Remove(store, ValMgr.makeLoc(R));
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000353 SVal X = I.getData();
Mike Stump1eb44332009-09-09 15:08:12 +0000354
Ted Kremenekf59bf482008-07-17 18:38:48 +0000355 for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI)
Ted Kremenek241677a2009-01-21 22:26:05 +0000356 SymReaper.maybeDead(*SI);
Ted Kremenekf59bf482008-07-17 18:38:48 +0000357 }
Ted Kremenek9e240492008-10-04 05:50:14 +0000358 }
Ted Kremenekf684d562009-03-05 18:08:28 +0000359
Zhongxing Xu5e4cb342010-08-15 12:45:09 +0000360 return store;
Ted Kremenekf59bf482008-07-17 18:38:48 +0000361}
Ted Kremenekcaa37242008-08-19 16:51:45 +0000362
Ted Kremenek82cd37c2009-08-21 23:25:54 +0000363Store BasicStoreManager::scanForIvars(Stmt *B, const Decl* SelfDecl,
364 const MemRegion *SelfRegion, Store St) {
Ted Kremenekf684d562009-03-05 18:08:28 +0000365 for (Stmt::child_iterator CI=B->child_begin(), CE=B->child_end();
366 CI != CE; ++CI) {
Mike Stump1eb44332009-09-09 15:08:12 +0000367
Ted Kremenekf684d562009-03-05 18:08:28 +0000368 if (!*CI)
369 continue;
Mike Stump1eb44332009-09-09 15:08:12 +0000370
Ted Kremenekf684d562009-03-05 18:08:28 +0000371 // Check if the statement is an ivar reference. We only
372 // care about self.ivar.
373 if (ObjCIvarRefExpr *IV = dyn_cast<ObjCIvarRefExpr>(*CI)) {
374 const Expr *Base = IV->getBase()->IgnoreParenCasts();
375 if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Base)) {
376 if (DR->getDecl() == SelfDecl) {
Zhongxing Xu14d23282010-03-01 06:56:52 +0000377 const ObjCIvarRegion *IVR = MRMgr.getObjCIvarRegion(IV->getDecl(),
Mike Stump1eb44332009-09-09 15:08:12 +0000378 SelfRegion);
379 SVal X = ValMgr.getRegionValueSymbolVal(IVR);
Zhongxing Xub241cf62010-02-08 08:48:05 +0000380 St = Bind(St, ValMgr.makeLoc(IVR), X);
Ted Kremenekf684d562009-03-05 18:08:28 +0000381 }
382 }
383 }
384 else
Ted Kremenek82cd37c2009-08-21 23:25:54 +0000385 St = scanForIvars(*CI, SelfDecl, SelfRegion, St);
Ted Kremenekf684d562009-03-05 18:08:28 +0000386 }
Mike Stump1eb44332009-09-09 15:08:12 +0000387
Ted Kremenekf684d562009-03-05 18:08:28 +0000388 return St;
389}
390
Mike Stump1eb44332009-09-09 15:08:12 +0000391Store BasicStoreManager::getInitialStore(const LocationContext *InitLoc) {
Ted Kremenekcaa37242008-08-19 16:51:45 +0000392 // The LiveVariables information already has a compilation of all VarDecls
393 // used in the function. Iterate through this set, and "symbolicate"
394 // any VarDecl whose value originally comes from outside the function.
Ted Kremenekcaa37242008-08-19 16:51:45 +0000395 typedef LiveVariables::AnalysisDataTy LVDataTy;
Zhongxing Xu17fd8632009-08-17 06:19:58 +0000396 LVDataTy& D = InitLoc->getLiveVariables()->getAnalysisData();
Ted Kremenek3baf6722010-11-24 00:54:37 +0000397 Store St = VBFactory.getEmptyMap().getRoot();
Ted Kremenekcaa37242008-08-19 16:51:45 +0000398
399 for (LVDataTy::decl_iterator I=D.begin_decl(), E=D.end_decl(); I != E; ++I) {
Zhongxing Xuce2bc7e32010-07-20 02:46:11 +0000400 const NamedDecl* ND = I->first;
Ted Kremenekcaa37242008-08-19 16:51:45 +0000401
Ted Kremenek9deb0e32008-10-24 20:32:16 +0000402 // Handle implicit parameters.
Zhongxing Xuce2bc7e32010-07-20 02:46:11 +0000403 if (const ImplicitParamDecl* PD = dyn_cast<ImplicitParamDecl>(ND)) {
Mike Stump1eb44332009-09-09 15:08:12 +0000404 const Decl& CD = *InitLoc->getDecl();
Ted Kremenek9deb0e32008-10-24 20:32:16 +0000405 if (const ObjCMethodDecl* MD = dyn_cast<ObjCMethodDecl>(&CD)) {
406 if (MD->getSelfDecl() == PD) {
Ted Kremenekc410d4d2009-12-16 23:53:37 +0000407 // FIXME: Add type constraints (when they become available) to
408 // SelfRegion? (i.e., it implements MD->getClassInterface()).
Zhongxing Xu14d23282010-03-01 06:56:52 +0000409 const VarRegion *VR = MRMgr.getVarRegion(PD, InitLoc);
Ted Kremenekc410d4d2009-12-16 23:53:37 +0000410 const MemRegion *SelfRegion =
Ted Kremenek5ba290a2010-03-02 21:43:54 +0000411 ValMgr.getRegionValueSymbolVal(VR).getAsRegion();
412 assert(SelfRegion);
Zhongxing Xub241cf62010-02-08 08:48:05 +0000413 St = Bind(St, ValMgr.makeLoc(VR), loc::MemRegionVal(SelfRegion));
Ted Kremenekf684d562009-03-05 18:08:28 +0000414 // Scan the method for ivar references. While this requires an
415 // entire AST scan, the cost should not be high in practice.
Ted Kremenek82cd37c2009-08-21 23:25:54 +0000416 St = scanForIvars(MD->getBody(), PD, SelfRegion, St);
Ted Kremenek9deb0e32008-10-24 20:32:16 +0000417 }
418 }
419 }
Ted Kremenekcaa37242008-08-19 16:51:45 +0000420 }
Ted Kremenek5ba290a2010-03-02 21:43:54 +0000421
Marcin Swiderski0aac2ba2010-11-17 06:22:54 +0000422 if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(InitLoc->getDecl())) {
423 // For C++ methods add symbolic region for 'this' in initial stack frame.
424 QualType ThisT = MD->getThisType(StateMgr.getContext());
425 MemRegionManager &RegMgr = ValMgr.getRegionManager();
426 const CXXThisRegion *ThisR = RegMgr.getCXXThisRegion(ThisT, InitLoc);
427 SVal ThisV = ValMgr.getRegionValueSymbolVal(ThisR);
428 St = Bind(St, ValMgr.makeLoc(ThisR), ThisV);
429 }
430
Ted Kremenekcaa37242008-08-19 16:51:45 +0000431 return St;
432}
Ted Kremeneka622d8c2008-08-19 22:24:03 +0000433
Ted Kremenekf6f56d42009-11-04 00:09:15 +0000434Store BasicStoreManager::BindDeclInternal(Store store, const VarRegion* VR,
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000435 SVal* InitVal) {
Mike Stump1eb44332009-09-09 15:08:12 +0000436
Ted Kremeneke53c0692008-08-23 00:50:55 +0000437 BasicValueFactory& BasicVals = StateMgr.getBasicVals();
Ted Kremenekf6f56d42009-11-04 00:09:15 +0000438 const VarDecl *VD = VR->getDecl();
Mike Stump1eb44332009-09-09 15:08:12 +0000439
Zhongxing Xubbe8ff42008-08-21 22:34:01 +0000440 // BasicStore does not model arrays and structs.
Douglas Gregorfb87b892010-04-26 21:31:17 +0000441 if (VD->getType()->isArrayType() || VD->getType()->isStructureOrClassType())
Zhongxing Xubbe8ff42008-08-21 22:34:01 +0000442 return store;
443
444 if (VD->hasGlobalStorage()) {
445 // Handle variables with global storage: extern, static, PrivateExtern.
446
447 // FIXME:: static variables may have an initializer, but the second time a
448 // function is called those values may not be current. Currently, a function
449 // will not be called more than once.
450
451 // Static global variables should not be visited here.
John McCalld931b082010-08-26 03:08:43 +0000452 assert(!(VD->getStorageClass() == SC_Static &&
Zhongxing Xubbe8ff42008-08-21 22:34:01 +0000453 VD->isFileVarDecl()));
Mike Stump1eb44332009-09-09 15:08:12 +0000454
Zhongxing Xubbe8ff42008-08-21 22:34:01 +0000455 // Process static variables.
John McCalld931b082010-08-26 03:08:43 +0000456 if (VD->getStorageClass() == SC_Static) {
Zhongxing Xubbe8ff42008-08-21 22:34:01 +0000457 // C99: 6.7.8 Initialization
458 // If an object that has static storage duration is not initialized
Mike Stump1eb44332009-09-09 15:08:12 +0000459 // explicitly, then:
460 // —if it has pointer type, it is initialized to a null pointer;
461 // —if it has arithmetic type, it is initialized to (positive or
Zhongxing Xubbe8ff42008-08-21 22:34:01 +0000462 // unsigned) zero;
Ted Kremenek42577d12008-11-12 19:18:35 +0000463 if (!InitVal) {
Zhongxing Xubbe8ff42008-08-21 22:34:01 +0000464 QualType T = VD->getType();
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000465 if (Loc::IsLocType(T))
Zhongxing Xub241cf62010-02-08 08:48:05 +0000466 store = Bind(store, loc::MemRegionVal(VR),
Zhongxing Xu8485ec62008-10-21 06:27:32 +0000467 loc::ConcreteInt(BasicVals.getValue(0, T)));
Ted Kremenekc0708432010-07-29 00:28:40 +0000468 else if (T->isIntegerType() && T->isScalarType())
Zhongxing Xub241cf62010-02-08 08:48:05 +0000469 store = Bind(store, loc::MemRegionVal(VR),
Zhongxing Xu8485ec62008-10-21 06:27:32 +0000470 nonloc::ConcreteInt(BasicVals.getValue(0, T)));
Zhongxing Xubbe8ff42008-08-21 22:34:01 +0000471 } else {
Zhongxing Xub241cf62010-02-08 08:48:05 +0000472 store = Bind(store, loc::MemRegionVal(VR), *InitVal);
Zhongxing Xubbe8ff42008-08-21 22:34:01 +0000473 }
474 }
475 } else {
476 // Process local scalar variables.
477 QualType T = VD->getType();
Ted Kremenekc0708432010-07-29 00:28:40 +0000478 // BasicStore only supports scalars.
Marcin Swiderski11b39d42010-11-16 07:15:33 +0000479 if ((T->isScalarType() || T->isReferenceType()) &&
480 ValMgr.getSymbolManager().canSymbolicate(T)) {
Ted Kremenek42577d12008-11-12 19:18:35 +0000481 SVal V = InitVal ? *InitVal : UndefinedVal();
Zhongxing Xub241cf62010-02-08 08:48:05 +0000482 store = Bind(store, loc::MemRegionVal(VR), V);
Zhongxing Xubbe8ff42008-08-21 22:34:01 +0000483 }
484 }
485
486 return store;
487}
488
Ted Kremenek53ba0b62009-06-24 23:06:47 +0000489void BasicStoreManager::print(Store store, llvm::raw_ostream& Out,
Ted Kremeneka622d8c2008-08-19 22:24:03 +0000490 const char* nl, const char *sep) {
Mike Stump1eb44332009-09-09 15:08:12 +0000491
Ted Kremenek2c8e7882009-03-05 16:32:59 +0000492 BindingsTy B = GetBindings(store);
Ted Kremeneka622d8c2008-08-19 22:24:03 +0000493 Out << "Variables:" << nl;
Mike Stump1eb44332009-09-09 15:08:12 +0000494
Ted Kremeneka622d8c2008-08-19 22:24:03 +0000495 bool isFirst = true;
Mike Stump1eb44332009-09-09 15:08:12 +0000496
Ted Kremenek2c8e7882009-03-05 16:32:59 +0000497 for (BindingsTy::iterator I=B.begin(), E=B.end(); I != E; ++I) {
Ted Kremenek53ba0b62009-06-24 23:06:47 +0000498 if (isFirst)
499 isFirst = false;
500 else
501 Out << nl;
Mike Stump1eb44332009-09-09 15:08:12 +0000502
Ted Kremenek6f9b3a42009-07-13 23:53:06 +0000503 Out << ' ' << I.getKey() << " : " << I.getData();
Ted Kremeneka622d8c2008-08-19 22:24:03 +0000504 }
505}
Ted Kremenek2bc39c62008-08-29 00:47:32 +0000506
Ted Kremenek60dbad82008-09-03 03:06:11 +0000507
508void BasicStoreManager::iterBindings(Store store, BindingsHandler& f) {
Ted Kremenek2c8e7882009-03-05 16:32:59 +0000509 BindingsTy B = GetBindings(store);
Mike Stump1eb44332009-09-09 15:08:12 +0000510
Ted Kremenek2c8e7882009-03-05 16:32:59 +0000511 for (BindingsTy::iterator I=B.begin(), E=B.end(); I != E; ++I)
Ted Kremenek744b3042010-06-17 00:24:37 +0000512 if (!f.HandleBinding(*this, store, I.getKey(), I.getData()))
513 return;
Ted Kremenek9e240492008-10-04 05:50:14 +0000514
Ted Kremenek2bc39c62008-08-29 00:47:32 +0000515}
516
Ted Kremenek60dbad82008-09-03 03:06:11 +0000517StoreManager::BindingsHandler::~BindingsHandler() {}
Ted Kremenek1004a9f2009-07-29 18:16:25 +0000518
519//===----------------------------------------------------------------------===//
520// Binding invalidation.
521//===----------------------------------------------------------------------===//
522
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000523
524Store BasicStoreManager::InvalidateRegions(Store store,
Jordy Rosec2b7dfa2010-08-14 20:44:32 +0000525 const MemRegion * const *I,
526 const MemRegion * const *End,
527 const Expr *E, unsigned Count,
528 InvalidatedSymbols *IS,
529 bool invalidateGlobals,
530 InvalidatedRegions *Regions) {
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000531 if (invalidateGlobals) {
532 BindingsTy B = GetBindings(store);
533 for (BindingsTy::iterator I=B.begin(), End=B.end(); I != End; ++I) {
534 const MemRegion *R = I.getKey();
535 if (isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace()))
536 store = InvalidateRegion(store, R, E, Count, IS);
537 }
538 }
539
540 for ( ; I != End ; ++I) {
541 const MemRegion *R = *I;
542 // Don't invalidate globals twice.
543 if (invalidateGlobals) {
544 if (isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace()))
545 continue;
546 }
547 store = InvalidateRegion(store, *I, E, Count, IS);
Jordy Rosec2b7dfa2010-08-14 20:44:32 +0000548 if (Regions)
549 Regions->push_back(R);
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000550 }
551
552 // FIXME: This is copy-and-paste from RegionStore.cpp.
553 if (invalidateGlobals) {
554 // Bind the non-static globals memory space to a new symbol that we will
555 // use to derive the bindings for all non-static globals.
556 const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion();
557 SVal V =
558 ValMgr.getConjuredSymbolVal(/* SymbolTag = */ (void*) GS, E,
559 /* symbol type, doesn't matter */ Ctx.IntTy,
560 Count);
561
562 store = Bind(store, loc::MemRegionVal(GS), V);
Jordy Rosec2b7dfa2010-08-14 20:44:32 +0000563 if (Regions)
564 Regions->push_back(GS);
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000565 }
566
567 return store;
568}
569
570
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000571Store BasicStoreManager::InvalidateRegion(Store store,
572 const MemRegion *R,
573 const Expr *E,
574 unsigned Count,
575 InvalidatedSymbols *IS) {
Zhongxing Xu479529e2009-11-10 02:17:20 +0000576 R = R->StripCasts();
Mike Stump1eb44332009-09-09 15:08:12 +0000577
Ted Kremenek1004a9f2009-07-29 18:16:25 +0000578 if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R)))
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000579 return store;
Mike Stump1eb44332009-09-09 15:08:12 +0000580
Ted Kremenek473e1672009-10-16 00:30:49 +0000581 if (IS) {
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000582 BindingsTy B = GetBindings(store);
Ted Kremenek473e1672009-10-16 00:30:49 +0000583 if (BindingsTy::data_type *Val = B.lookup(R)) {
584 if (SymbolRef Sym = Val->getAsSymbol())
585 IS->insert(Sym);
586 }
587 }
588
Zhongxing Xu018220c2010-08-11 06:10:55 +0000589 QualType T = cast<TypedRegion>(R)->getValueType();
Ted Kremenek87806792009-09-27 20:45:21 +0000590 SVal V = ValMgr.getConjuredSymbolVal(R, E, T, Count);
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000591 return Bind(store, loc::MemRegionVal(R), V);
Ted Kremenek1004a9f2009-07-29 18:16:25 +0000592}
593