blob: 943d64e2b667af1c22ea6f14dadd015b918bf462 [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
Ted Kremenekf684d562009-03-05 18:08:28 +000014#include "clang/AST/ExprObjC.h"
Ted Kremenek5f81c442008-08-28 23:31:31 +000015#include "clang/Analysis/Analyses/LiveVariables.h"
Ted Kremenek1309f9a2010-01-25 04:41:41 +000016#include "clang/Analysis/AnalysisContext.h"
17#include "clang/Checker/PathSensitive/GRState.h"
Benjamin Kramer6cb7c1a2009-08-23 12:08:50 +000018#include "llvm/ADT/ImmutableMap.h"
Ted Kremenek4323a572008-07-10 22:03:41 +000019
20using namespace clang;
21
Mike Stump1eb44332009-09-09 15:08:12 +000022typedef llvm::ImmutableMap<const MemRegion*,SVal> BindingsTy;
Ted Kremenek60dbad82008-09-03 03:06:11 +000023
Ted Kremenek4323a572008-07-10 22:03:41 +000024namespace {
Mike Stump1eb44332009-09-09 15:08:12 +000025
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +000026class BasicStoreSubRegionMap : public SubRegionMap {
Ted Kremenek59e8f112009-03-03 01:35:36 +000027public:
28 BasicStoreSubRegionMap() {}
29
Ted Kremenek5dc27462009-03-03 02:51:43 +000030 bool iterSubRegions(const MemRegion* R, Visitor& V) const {
Ted Kremenek39fc7152009-03-05 16:41:21 +000031 return true; // Do nothing. No subregions.
Ted Kremenek59e8f112009-03-03 01:35:36 +000032 }
33};
Mike Stump1eb44332009-09-09 15:08:12 +000034
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +000035class BasicStoreManager : public StoreManager {
Ted Kremenek2c8e7882009-03-05 16:32:59 +000036 BindingsTy::Factory VBFactory;
Ted Kremenek4323a572008-07-10 22:03:41 +000037public:
Ted Kremenekf7a0cf42009-07-29 21:43:22 +000038 BasicStoreManager(GRStateManager& mgr)
Ted Kremenek82cd37c2009-08-21 23:25:54 +000039 : StoreManager(mgr), VBFactory(mgr.getAllocator()) {}
Mike Stump1eb44332009-09-09 15:08:12 +000040
Ted Kremenek9deb0e32008-10-24 20:32:16 +000041 ~BasicStoreManager() {}
Ted Kremenek4323a572008-07-10 22:03:41 +000042
Zhongxing Xuf5416bd2010-02-05 05:18:47 +000043 SubRegionMap *getSubRegionMap(Store store) {
Ted Kremenek14453bf2009-03-03 19:02:42 +000044 return new BasicStoreSubRegionMap();
Ted Kremenek59e8f112009-03-03 01:35:36 +000045 }
46
Zhongxing Xu576bb922010-02-05 03:01:53 +000047 SVal Retrieve(Store store, Loc loc, QualType T = QualType());
Mike Stump1eb44332009-09-09 15:08:12 +000048
Ted Kremenekdcee3ce2010-07-01 20:16:50 +000049 Store InvalidateRegion(Store store, const MemRegion *R, const Expr *E,
Zhongxing Xub4a9c612010-02-05 05:06:13 +000050 unsigned Count, InvalidatedSymbols *IS);
Zhongxing Xu4193eca2008-12-20 06:32:12 +000051
Ted Kremenekdcee3ce2010-07-01 20:16:50 +000052 Store InvalidateRegions(Store store, const MemRegion * const *Begin,
53 const MemRegion * const *End, const Expr *E,
54 unsigned Count, InvalidatedSymbols *IS,
Jordy Rosec2b7dfa2010-08-14 20:44:32 +000055 bool invalidateGlobals, InvalidatedRegions *Regions);
Ted Kremenekdcee3ce2010-07-01 20:16:50 +000056
Ted Kremenek82cd37c2009-08-21 23:25:54 +000057 Store scanForIvars(Stmt *B, const Decl* SelfDecl,
58 const MemRegion *SelfRegion, Store St);
Mike Stump1eb44332009-09-09 15:08:12 +000059
Zhongxing Xub241cf62010-02-08 08:48:05 +000060 Store Bind(Store St, Loc loc, SVal V);
Ted Kremenekc6ed3842009-01-07 22:56:17 +000061 Store Remove(Store St, Loc loc);
Zhongxing Xu17fd8632009-08-17 06:19:58 +000062 Store getInitialStore(const LocationContext *InitLoc);
Zhongxing Xubc678fd2008-10-07 01:31:04 +000063
Zhongxing Xu6d69b5d2008-10-16 06:09:51 +000064 // FIXME: Investigate what is using this. This method should be removed.
Ted Kremenekd17da2b2009-08-21 22:28:32 +000065 virtual Loc getLoc(const VarDecl* VD, const LocationContext *LC) {
66 return ValMgr.makeLoc(MRMgr.getVarRegion(VD, LC));
Zhongxing Xubc678fd2008-10-07 01:31:04 +000067 }
Mike Stump1eb44332009-09-09 15:08:12 +000068
Zhongxing Xub4a9c612010-02-05 05:06:13 +000069 Store BindCompoundLiteral(Store store, const CompoundLiteralExpr*,
70 const LocationContext*, SVal val) {
71 return store;
Ted Kremenek4f090272008-10-27 21:54:31 +000072 }
Mike Stump1eb44332009-09-09 15:08:12 +000073
Ted Kremenek9deb0e32008-10-24 20:32:16 +000074 /// ArrayToPointer - Used by GRExprEngine::VistCast to handle implicit
75 /// conversions between arrays and pointers.
Zhongxing Xuf1d537f2009-03-30 05:55:46 +000076 SVal ArrayToPointer(Loc Array) { return Array; }
Mike Stump1eb44332009-09-09 15:08:12 +000077
Ted Kremenek2ed14be2008-12-05 00:47:52 +000078 /// RemoveDeadBindings - Scans a BasicStore of 'state' for dead values.
Ted Kremenek2f26bc32009-08-02 04:45:08 +000079 /// It updatees the GRState object in place with the values removed.
Zhongxing Xu5e4cb342010-08-15 12:45:09 +000080 Store RemoveDeadBindings(Store store, const StackFrameContext *LCtx,
81 SymbolReaper& SymReaper,
Ted Kremenek2f26bc32009-08-02 04:45:08 +000082 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots);
Zhongxing Xubbe8ff42008-08-21 22:34:01 +000083
Ted Kremenek9deb0e32008-10-24 20:32:16 +000084 void iterBindings(Store store, BindingsHandler& f);
Ted Kremenek60dbad82008-09-03 03:06:11 +000085
Zhongxing Xub4a9c612010-02-05 05:06:13 +000086 Store BindDecl(Store store, const VarRegion *VR, SVal InitVal) {
87 return BindDeclInternal(store, VR, &InitVal);
Zhongxing Xu4193eca2008-12-20 06:32:12 +000088 }
89
Zhongxing Xub4a9c612010-02-05 05:06:13 +000090 Store BindDeclWithNoInit(Store store, const VarRegion *VR) {
91 return BindDeclInternal(store, VR, 0);
Zhongxing Xu4193eca2008-12-20 06:32:12 +000092 }
93
Ted Kremenekf6f56d42009-11-04 00:09:15 +000094 Store BindDeclInternal(Store store, const VarRegion *VR, SVal *InitVal);
Zhongxing Xubbe8ff42008-08-21 22:34:01 +000095
Ted Kremenek2c8e7882009-03-05 16:32:59 +000096 static inline BindingsTy GetBindings(Store store) {
97 return BindingsTy(static_cast<const BindingsTy::TreeTy*>(store));
Ted Kremeneka622d8c2008-08-19 22:24:03 +000098 }
99
Ted Kremenek53ba0b62009-06-24 23:06:47 +0000100 void print(Store store, llvm::raw_ostream& Out, const char* nl,
101 const char *sep);
Zhongxing Xua1718c72009-04-03 07:33:13 +0000102
103private:
Ted Kremenek5ba290a2010-03-02 21:43:54 +0000104 SVal LazyRetrieve(Store store, const TypedRegion *R);
Ted Kremenek60dbad82008-09-03 03:06:11 +0000105};
Mike Stump1eb44332009-09-09 15:08:12 +0000106
Ted Kremenek4323a572008-07-10 22:03:41 +0000107} // end anonymous namespace
108
109
Ted Kremenek5f81c442008-08-28 23:31:31 +0000110StoreManager* clang::CreateBasicStoreManager(GRStateManager& StMgr) {
111 return new BasicStoreManager(StMgr);
Ted Kremenekd0c4b282008-08-25 19:33:03 +0000112}
Zhongxing Xu933c3e12008-10-21 06:54:23 +0000113
Ted Kremenek5fa93d52009-04-29 16:03:27 +0000114static bool isHigherOrderRawPtr(QualType T, ASTContext &C) {
Ted Kremenek1670e402009-04-11 00:11:10 +0000115 bool foundPointer = false;
Mike Stump1eb44332009-09-09 15:08:12 +0000116 while (1) {
Ted Kremenek6217b802009-07-29 21:53:49 +0000117 const PointerType *PT = T->getAs<PointerType>();
Ted Kremenek1670e402009-04-11 00:11:10 +0000118 if (!PT) {
119 if (!foundPointer)
120 return false;
Mike Stump1eb44332009-09-09 15:08:12 +0000121
Ted Kremenek5fa93d52009-04-29 16:03:27 +0000122 // intptr_t* or intptr_t**, etc?
123 if (T->isIntegerType() && C.getTypeSize(T) == C.getTypeSize(C.VoidPtrTy))
124 return true;
Mike Stump1eb44332009-09-09 15:08:12 +0000125
Ted Kremenek1670e402009-04-11 00:11:10 +0000126 QualType X = C.getCanonicalType(T).getUnqualifiedType();
127 return X == C.VoidTy;
128 }
Mike Stump1eb44332009-09-09 15:08:12 +0000129
Ted Kremenek1670e402009-04-11 00:11:10 +0000130 foundPointer = true;
131 T = PT->getPointeeType();
Mike Stump1eb44332009-09-09 15:08:12 +0000132 }
Ted Kremenek1670e402009-04-11 00:11:10 +0000133}
Mike Stump1eb44332009-09-09 15:08:12 +0000134
Ted Kremenek5ba290a2010-03-02 21:43:54 +0000135SVal BasicStoreManager::LazyRetrieve(Store store, const TypedRegion *R) {
136 const VarRegion *VR = dyn_cast<VarRegion>(R);
137 if (!VR)
138 return UnknownVal();
139
140 const VarDecl *VD = VR->getDecl();
141 QualType T = VD->getType();
142
143 // Only handle simple types that we can symbolicate.
144 if (!SymbolManager::canSymbolicate(T) || !T->isScalarType())
145 return UnknownVal();
146
147 // Globals and parameters start with symbolic values.
148 // Local variables initially are undefined.
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000149
150 // Non-static globals may have had their values reset by InvalidateRegions.
151 const MemSpaceRegion *MS = VR->getMemorySpace();
152 if (isa<NonStaticGlobalSpaceRegion>(MS)) {
153 BindingsTy B = GetBindings(store);
154 // FIXME: Copy-and-pasted from RegionStore.cpp.
155 if (BindingsTy::data_type *Val = B.lookup(MS)) {
156 if (SymbolRef parentSym = Val->getAsSymbol())
157 return ValMgr.getDerivedRegionValueSymbolVal(parentSym, R);
158
159 if (Val->isZeroConstant())
160 return ValMgr.makeZeroVal(T);
161
162 if (Val->isUnknownOrUndef())
163 return *Val;
164
165 assert(0 && "Unknown default value.");
166 }
167 }
168
Ted Kremenek30986dd2010-03-10 00:18:08 +0000169 if (VR->hasGlobalsOrParametersStorage() ||
170 isa<UnknownSpaceRegion>(VR->getMemorySpace()))
Ted Kremenek5ba290a2010-03-02 21:43:54 +0000171 return ValMgr.getRegionValueSymbolVal(R);
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000172
Ted Kremenek5ba290a2010-03-02 21:43:54 +0000173 return UndefinedVal();
174}
175
Zhongxing Xu576bb922010-02-05 03:01:53 +0000176SVal BasicStoreManager::Retrieve(Store store, Loc loc, QualType T) {
Ted Kremenekc6ed3842009-01-07 22:56:17 +0000177 if (isa<UnknownVal>(loc))
Zhongxing Xuc999ed72010-02-04 02:39:47 +0000178 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000179
Ted Kremenek1894dce2009-08-25 20:51:30 +0000180 assert(!isa<UndefinedVal>(loc));
Mike Stump1eb44332009-09-09 15:08:12 +0000181
Ted Kremenekc6ed3842009-01-07 22:56:17 +0000182 switch (loc.getSubKind()) {
Ted Kremenek4323a572008-07-10 22:03:41 +0000183
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000184 case loc::MemRegionKind: {
Ted Kremenekf684d562009-03-05 18:08:28 +0000185 const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion();
Mike Stump1eb44332009-09-09 15:08:12 +0000186
Ted Kremenekf684d562009-03-05 18:08:28 +0000187 if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R)))
Zhongxing Xuc999ed72010-02-04 02:39:47 +0000188 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000189
Zhongxing Xu576bb922010-02-05 03:01:53 +0000190 BindingsTy B = GetBindings(store);
Ted Kremenek1894dce2009-08-25 20:51:30 +0000191 BindingsTy::data_type *Val = B.lookup(R);
Ted Kremenek5ba290a2010-03-02 21:43:54 +0000192 const TypedRegion *TR = cast<TypedRegion>(R);
Mike Stump1eb44332009-09-09 15:08:12 +0000193
Ted Kremenek5ba290a2010-03-02 21:43:54 +0000194 if (Val)
195 return CastRetrievedVal(*Val, TR, T);
Mike Stump1eb44332009-09-09 15:08:12 +0000196
Ted Kremenek5ba290a2010-03-02 21:43:54 +0000197 SVal V = LazyRetrieve(store, TR);
198 return V.isUnknownOrUndef() ? V : CastRetrievedVal(V, TR, T);
Ted Kremenek4323a572008-07-10 22:03:41 +0000199 }
Mike Stump1eb44332009-09-09 15:08:12 +0000200
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000201 case loc::ConcreteIntKind:
202 // Some clients may call GetSVal with such an option simply because
203 // they are doing a quick scan through their Locs (potentially to
Ted Kremenek4323a572008-07-10 22:03:41 +0000204 // invalidate their bindings). Just return Undefined.
Zhongxing Xuc999ed72010-02-04 02:39:47 +0000205 return UndefinedVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000206
Ted Kremenek4323a572008-07-10 22:03:41 +0000207 default:
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000208 assert (false && "Invalid Loc.");
Ted Kremenek4323a572008-07-10 22:03:41 +0000209 break;
210 }
Mike Stump1eb44332009-09-09 15:08:12 +0000211
Zhongxing Xuc999ed72010-02-04 02:39:47 +0000212 return UnknownVal();
Ted Kremenek4323a572008-07-10 22:03:41 +0000213}
Mike Stump1eb44332009-09-09 15:08:12 +0000214
Zhongxing Xub241cf62010-02-08 08:48:05 +0000215Store BasicStoreManager::Bind(Store store, Loc loc, SVal V) {
Zhongxing Xu87453d12009-06-28 10:16:11 +0000216 if (isa<loc::ConcreteInt>(loc))
217 return store;
218
Zhongxing Xuc2a650a2009-06-28 09:26:15 +0000219 const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion();
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000220
221 // Special case: a default symbol assigned to the NonStaticGlobalsSpaceRegion
222 // that is used to derive other symbols.
223 if (isa<NonStaticGlobalSpaceRegion>(R)) {
224 BindingsTy B = GetBindings(store);
225 return VBFactory.Add(B, R, V).getRoot();
226 }
227
Zhongxing Xuc2a650a2009-06-28 09:26:15 +0000228 // Special case: handle store of pointer values (Loc) to pointers via
229 // a cast to intXX_t*, void*, etc. This is needed to handle
230 // OSCompareAndSwap32Barrier/OSCompareAndSwap64Barrier.
231 if (isa<Loc>(V) || isa<nonloc::LocAsInteger>(V))
232 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
233 // FIXME: Should check for index 0.
Zhongxing Xu018220c2010-08-11 06:10:55 +0000234 QualType T = ER->getLocationType();
Mike Stump1eb44332009-09-09 15:08:12 +0000235
Zhongxing Xu57663fe2010-08-15 10:08:38 +0000236 if (isHigherOrderRawPtr(T, Ctx))
Zhongxing Xuc2a650a2009-06-28 09:26:15 +0000237 R = ER->getSuperRegion();
Mike Stump1eb44332009-09-09 15:08:12 +0000238 }
239
Zhongxing Xuc2a650a2009-06-28 09:26:15 +0000240 if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R)))
241 return store;
Ted Kremenek82cd37c2009-08-21 23:25:54 +0000242
Ted Kremenekab2f43c2009-08-25 23:29:04 +0000243 const TypedRegion *TyR = cast<TypedRegion>(R);
Mike Stump1eb44332009-09-09 15:08:12 +0000244
Ted Kremenekab2f43c2009-08-25 23:29:04 +0000245 // Do not bind to arrays. We need to explicitly check for this so that
246 // we do not encounter any weirdness of trying to load/store from arrays.
Zhongxing Xu018220c2010-08-11 06:10:55 +0000247 if (TyR->isBoundable() && TyR->getValueType()->isArrayType())
Mike Stump1eb44332009-09-09 15:08:12 +0000248 return store;
Ted Kremenekab2f43c2009-08-25 23:29:04 +0000249
Zhongxing Xuc2a650a2009-06-28 09:26:15 +0000250 if (nonloc::LocAsInteger *X = dyn_cast<nonloc::LocAsInteger>(&V)) {
251 // Only convert 'V' to a location iff the underlying region type
252 // is a location as well.
253 // FIXME: We are allowing a store of an arbitrary location to
254 // a pointer. We may wish to flag a type error here if the types
255 // are incompatible. This may also cause lots of breakage
256 // elsewhere. Food for thought.
Zhongxing Xu018220c2010-08-11 06:10:55 +0000257 if (TyR->isBoundable() && Loc::IsLocType(TyR->getValueType()))
Ted Kremenekab2f43c2009-08-25 23:29:04 +0000258 V = X->getLoc();
Ted Kremenek4323a572008-07-10 22:03:41 +0000259 }
Zhongxing Xuc2a650a2009-06-28 09:26:15 +0000260
261 BindingsTy B = GetBindings(store);
262 return V.isUnknown()
263 ? VBFactory.Remove(B, R).getRoot()
264 : VBFactory.Add(B, R, V).getRoot();
Ted Kremenek4323a572008-07-10 22:03:41 +0000265}
266
Ted Kremenekc6ed3842009-01-07 22:56:17 +0000267Store BasicStoreManager::Remove(Store store, Loc loc) {
268 switch (loc.getSubKind()) {
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000269 case loc::MemRegionKind: {
Ted Kremenekf684d562009-03-05 18:08:28 +0000270 const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion();
Mike Stump1eb44332009-09-09 15:08:12 +0000271
Ted Kremenekf684d562009-03-05 18:08:28 +0000272 if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R)))
Ted Kremenek9e240492008-10-04 05:50:14 +0000273 return store;
Mike Stump1eb44332009-09-09 15:08:12 +0000274
Ted Kremenekf684d562009-03-05 18:08:28 +0000275 return VBFactory.Remove(GetBindings(store), R).getRoot();
Ted Kremenekf59bf482008-07-17 18:38:48 +0000276 }
Ted Kremenek4323a572008-07-10 22:03:41 +0000277 default:
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000278 assert ("Remove for given Loc type not yet implemented.");
Ted Kremenekf59bf482008-07-17 18:38:48 +0000279 return store;
Ted Kremenek4323a572008-07-10 22:03:41 +0000280 }
281}
Ted Kremenekf59bf482008-07-17 18:38:48 +0000282
Zhongxing Xu5e4cb342010-08-15 12:45:09 +0000283Store BasicStoreManager::RemoveDeadBindings(Store store,
Zhongxing Xu17ddf1c2010-03-17 03:35:08 +0000284 const StackFrameContext *LCtx,
Zhongxing Xu72119c42010-02-05 05:34:29 +0000285 SymbolReaper& SymReaper,
Ted Kremenek2f26bc32009-08-02 04:45:08 +0000286 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots)
Mike Stump1eb44332009-09-09 15:08:12 +0000287{
Ted Kremenek2c8e7882009-03-05 16:32:59 +0000288 BindingsTy B = GetBindings(store);
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000289 typedef SVal::symbol_iterator symbol_iterator;
Mike Stump1eb44332009-09-09 15:08:12 +0000290
Ted Kremenekf59bf482008-07-17 18:38:48 +0000291 // Iterate over the variable bindings.
Ted Kremenek2c8e7882009-03-05 16:32:59 +0000292 for (BindingsTy::iterator I=B.begin(), E=B.end(); I!=E ; ++I) {
Ted Kremenekf684d562009-03-05 18:08:28 +0000293 if (const VarRegion *VR = dyn_cast<VarRegion>(I.getKey())) {
Jordy Rose7dadf792010-07-01 20:09:55 +0000294 if (SymReaper.isLive(VR))
Ted Kremenekf684d562009-03-05 18:08:28 +0000295 RegionRoots.push_back(VR);
296 else
297 continue;
Ted Kremenekf59bf482008-07-17 18:38:48 +0000298 }
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000299 else if (isa<ObjCIvarRegion>(I.getKey()) ||
300 isa<NonStaticGlobalSpaceRegion>(I.getKey()))
Ted Kremenekf684d562009-03-05 18:08:28 +0000301 RegionRoots.push_back(I.getKey());
Ted Kremenekf684d562009-03-05 18:08:28 +0000302 else
303 continue;
Mike Stump1eb44332009-09-09 15:08:12 +0000304
Ted Kremenekf684d562009-03-05 18:08:28 +0000305 // Mark the bindings in the data as live.
306 SVal X = I.getData();
307 for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI)
308 SymReaper.markLive(*SI);
Ted Kremenekbe912242009-03-05 16:31:07 +0000309 }
Mike Stump1eb44332009-09-09 15:08:12 +0000310
Ted Kremenekf59bf482008-07-17 18:38:48 +0000311 // Scan for live variables and live symbols.
Ted Kremenekf684d562009-03-05 18:08:28 +0000312 llvm::SmallPtrSet<const MemRegion*, 10> Marked;
Mike Stump1eb44332009-09-09 15:08:12 +0000313
Ted Kremenek9e240492008-10-04 05:50:14 +0000314 while (!RegionRoots.empty()) {
Ted Kremenek134e7492008-10-17 22:52:40 +0000315 const MemRegion* MR = RegionRoots.back();
Ted Kremenek9e240492008-10-04 05:50:14 +0000316 RegionRoots.pop_back();
Mike Stump1eb44332009-09-09 15:08:12 +0000317
Ted Kremenek134e7492008-10-17 22:52:40 +0000318 while (MR) {
319 if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(MR)) {
Ted Kremenek241677a2009-01-21 22:26:05 +0000320 SymReaper.markLive(SymR->getSymbol());
Ted Kremenek134e7492008-10-17 22:52:40 +0000321 break;
322 }
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000323 else if (isa<VarRegion>(MR) || isa<ObjCIvarRegion>(MR) ||
324 isa<NonStaticGlobalSpaceRegion>(MR)) {
Ted Kremenekf684d562009-03-05 18:08:28 +0000325 if (Marked.count(MR))
Ted Kremenek134e7492008-10-17 22:52:40 +0000326 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000327
328 Marked.insert(MR);
Zhongxing Xu72119c42010-02-05 05:34:29 +0000329 SVal X = Retrieve(store, loc::MemRegionVal(MR));
Mike Stump1eb44332009-09-09 15:08:12 +0000330
Ted Kremenek134e7492008-10-17 22:52:40 +0000331 // FIXME: We need to handle symbols nested in region definitions.
Ted Kremenek241677a2009-01-21 22:26:05 +0000332 for (symbol_iterator SI=X.symbol_begin(),SE=X.symbol_end();SI!=SE;++SI)
333 SymReaper.markLive(*SI);
Mike Stump1eb44332009-09-09 15:08:12 +0000334
Ted Kremenek134e7492008-10-17 22:52:40 +0000335 if (!isa<loc::MemRegionVal>(X))
336 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000337
Ted Kremenek134e7492008-10-17 22:52:40 +0000338 const loc::MemRegionVal& LVD = cast<loc::MemRegionVal>(X);
339 RegionRoots.push_back(LVD.getRegion());
340 break;
341 }
342 else if (const SubRegion* R = dyn_cast<SubRegion>(MR))
343 MR = R->getSuperRegion();
344 else
345 break;
346 }
Ted Kremenekf59bf482008-07-17 18:38:48 +0000347 }
Mike Stump1eb44332009-09-09 15:08:12 +0000348
349 // Remove dead variable bindings.
Ted Kremenek2c8e7882009-03-05 16:32:59 +0000350 for (BindingsTy::iterator I=B.begin(), E=B.end(); I!=E ; ++I) {
Ted Kremenekf684d562009-03-05 18:08:28 +0000351 const MemRegion* R = I.getKey();
Mike Stump1eb44332009-09-09 15:08:12 +0000352
Ted Kremenek9e240492008-10-04 05:50:14 +0000353 if (!Marked.count(R)) {
Zhongxing Xud91ee272009-06-23 09:02:15 +0000354 store = Remove(store, ValMgr.makeLoc(R));
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000355 SVal X = I.getData();
Mike Stump1eb44332009-09-09 15:08:12 +0000356
Ted Kremenekf59bf482008-07-17 18:38:48 +0000357 for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI)
Ted Kremenek241677a2009-01-21 22:26:05 +0000358 SymReaper.maybeDead(*SI);
Ted Kremenekf59bf482008-07-17 18:38:48 +0000359 }
Ted Kremenek9e240492008-10-04 05:50:14 +0000360 }
Ted Kremenekf684d562009-03-05 18:08:28 +0000361
Zhongxing Xu5e4cb342010-08-15 12:45:09 +0000362 return store;
Ted Kremenekf59bf482008-07-17 18:38:48 +0000363}
Ted Kremenekcaa37242008-08-19 16:51:45 +0000364
Ted Kremenek82cd37c2009-08-21 23:25:54 +0000365Store BasicStoreManager::scanForIvars(Stmt *B, const Decl* SelfDecl,
366 const MemRegion *SelfRegion, Store St) {
Ted Kremenekf684d562009-03-05 18:08:28 +0000367 for (Stmt::child_iterator CI=B->child_begin(), CE=B->child_end();
368 CI != CE; ++CI) {
Mike Stump1eb44332009-09-09 15:08:12 +0000369
Ted Kremenekf684d562009-03-05 18:08:28 +0000370 if (!*CI)
371 continue;
Mike Stump1eb44332009-09-09 15:08:12 +0000372
Ted Kremenekf684d562009-03-05 18:08:28 +0000373 // Check if the statement is an ivar reference. We only
374 // care about self.ivar.
375 if (ObjCIvarRefExpr *IV = dyn_cast<ObjCIvarRefExpr>(*CI)) {
376 const Expr *Base = IV->getBase()->IgnoreParenCasts();
377 if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Base)) {
378 if (DR->getDecl() == SelfDecl) {
Zhongxing Xu14d23282010-03-01 06:56:52 +0000379 const ObjCIvarRegion *IVR = MRMgr.getObjCIvarRegion(IV->getDecl(),
Mike Stump1eb44332009-09-09 15:08:12 +0000380 SelfRegion);
381 SVal X = ValMgr.getRegionValueSymbolVal(IVR);
Zhongxing Xub241cf62010-02-08 08:48:05 +0000382 St = Bind(St, ValMgr.makeLoc(IVR), X);
Ted Kremenekf684d562009-03-05 18:08:28 +0000383 }
384 }
385 }
386 else
Ted Kremenek82cd37c2009-08-21 23:25:54 +0000387 St = scanForIvars(*CI, SelfDecl, SelfRegion, St);
Ted Kremenekf684d562009-03-05 18:08:28 +0000388 }
Mike Stump1eb44332009-09-09 15:08:12 +0000389
Ted Kremenekf684d562009-03-05 18:08:28 +0000390 return St;
391}
392
Mike Stump1eb44332009-09-09 15:08:12 +0000393Store BasicStoreManager::getInitialStore(const LocationContext *InitLoc) {
Ted Kremenekcaa37242008-08-19 16:51:45 +0000394 // The LiveVariables information already has a compilation of all VarDecls
395 // used in the function. Iterate through this set, and "symbolicate"
396 // any VarDecl whose value originally comes from outside the function.
Ted Kremenekcaa37242008-08-19 16:51:45 +0000397 typedef LiveVariables::AnalysisDataTy LVDataTy;
Zhongxing Xu17fd8632009-08-17 06:19:58 +0000398 LVDataTy& D = InitLoc->getLiveVariables()->getAnalysisData();
Ted Kremenekcaa37242008-08-19 16:51:45 +0000399 Store St = VBFactory.GetEmptyMap().getRoot();
400
401 for (LVDataTy::decl_iterator I=D.begin_decl(), E=D.end_decl(); I != E; ++I) {
Zhongxing Xuce2bc7e32010-07-20 02:46:11 +0000402 const NamedDecl* ND = I->first;
Ted Kremenekcaa37242008-08-19 16:51:45 +0000403
Ted Kremenek9deb0e32008-10-24 20:32:16 +0000404 // Handle implicit parameters.
Zhongxing Xuce2bc7e32010-07-20 02:46:11 +0000405 if (const ImplicitParamDecl* PD = dyn_cast<ImplicitParamDecl>(ND)) {
Mike Stump1eb44332009-09-09 15:08:12 +0000406 const Decl& CD = *InitLoc->getDecl();
Ted Kremenek9deb0e32008-10-24 20:32:16 +0000407 if (const ObjCMethodDecl* MD = dyn_cast<ObjCMethodDecl>(&CD)) {
408 if (MD->getSelfDecl() == PD) {
Ted Kremenekc410d4d2009-12-16 23:53:37 +0000409 // FIXME: Add type constraints (when they become available) to
410 // SelfRegion? (i.e., it implements MD->getClassInterface()).
Zhongxing Xu14d23282010-03-01 06:56:52 +0000411 const VarRegion *VR = MRMgr.getVarRegion(PD, InitLoc);
Ted Kremenekc410d4d2009-12-16 23:53:37 +0000412 const MemRegion *SelfRegion =
Ted Kremenek5ba290a2010-03-02 21:43:54 +0000413 ValMgr.getRegionValueSymbolVal(VR).getAsRegion();
414 assert(SelfRegion);
Zhongxing Xub241cf62010-02-08 08:48:05 +0000415 St = Bind(St, ValMgr.makeLoc(VR), loc::MemRegionVal(SelfRegion));
Ted Kremenekf684d562009-03-05 18:08:28 +0000416 // Scan the method for ivar references. While this requires an
417 // entire AST scan, the cost should not be high in practice.
Ted Kremenek82cd37c2009-08-21 23:25:54 +0000418 St = scanForIvars(MD->getBody(), PD, SelfRegion, St);
Ted Kremenek9deb0e32008-10-24 20:32:16 +0000419 }
420 }
421 }
Ted Kremenekcaa37242008-08-19 16:51:45 +0000422 }
Ted Kremenek5ba290a2010-03-02 21:43:54 +0000423
Ted Kremenekcaa37242008-08-19 16:51:45 +0000424 return St;
425}
Ted Kremeneka622d8c2008-08-19 22:24:03 +0000426
Ted Kremenekf6f56d42009-11-04 00:09:15 +0000427Store BasicStoreManager::BindDeclInternal(Store store, const VarRegion* VR,
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000428 SVal* InitVal) {
Mike Stump1eb44332009-09-09 15:08:12 +0000429
Ted Kremeneke53c0692008-08-23 00:50:55 +0000430 BasicValueFactory& BasicVals = StateMgr.getBasicVals();
Ted Kremenekf6f56d42009-11-04 00:09:15 +0000431 const VarDecl *VD = VR->getDecl();
Mike Stump1eb44332009-09-09 15:08:12 +0000432
Zhongxing Xubbe8ff42008-08-21 22:34:01 +0000433 // BasicStore does not model arrays and structs.
Douglas Gregorfb87b892010-04-26 21:31:17 +0000434 if (VD->getType()->isArrayType() || VD->getType()->isStructureOrClassType())
Zhongxing Xubbe8ff42008-08-21 22:34:01 +0000435 return store;
436
437 if (VD->hasGlobalStorage()) {
438 // Handle variables with global storage: extern, static, PrivateExtern.
439
440 // FIXME:: static variables may have an initializer, but the second time a
441 // function is called those values may not be current. Currently, a function
442 // will not be called more than once.
443
444 // Static global variables should not be visited here.
445 assert(!(VD->getStorageClass() == VarDecl::Static &&
446 VD->isFileVarDecl()));
Mike Stump1eb44332009-09-09 15:08:12 +0000447
Zhongxing Xubbe8ff42008-08-21 22:34:01 +0000448 // Process static variables.
449 if (VD->getStorageClass() == VarDecl::Static) {
450 // C99: 6.7.8 Initialization
451 // If an object that has static storage duration is not initialized
Mike Stump1eb44332009-09-09 15:08:12 +0000452 // explicitly, then:
453 // —if it has pointer type, it is initialized to a null pointer;
454 // —if it has arithmetic type, it is initialized to (positive or
Zhongxing Xubbe8ff42008-08-21 22:34:01 +0000455 // unsigned) zero;
Ted Kremenek42577d12008-11-12 19:18:35 +0000456 if (!InitVal) {
Zhongxing Xubbe8ff42008-08-21 22:34:01 +0000457 QualType T = VD->getType();
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000458 if (Loc::IsLocType(T))
Zhongxing Xub241cf62010-02-08 08:48:05 +0000459 store = Bind(store, loc::MemRegionVal(VR),
Zhongxing Xu8485ec62008-10-21 06:27:32 +0000460 loc::ConcreteInt(BasicVals.getValue(0, T)));
Ted Kremenekc0708432010-07-29 00:28:40 +0000461 else if (T->isIntegerType() && T->isScalarType())
Zhongxing Xub241cf62010-02-08 08:48:05 +0000462 store = Bind(store, loc::MemRegionVal(VR),
Zhongxing Xu8485ec62008-10-21 06:27:32 +0000463 nonloc::ConcreteInt(BasicVals.getValue(0, T)));
Zhongxing Xubbe8ff42008-08-21 22:34:01 +0000464 } else {
Zhongxing Xub241cf62010-02-08 08:48:05 +0000465 store = Bind(store, loc::MemRegionVal(VR), *InitVal);
Zhongxing Xubbe8ff42008-08-21 22:34:01 +0000466 }
467 }
468 } else {
469 // Process local scalar variables.
470 QualType T = VD->getType();
Ted Kremenekc0708432010-07-29 00:28:40 +0000471 // BasicStore only supports scalars.
472 if (T->isScalarType() && ValMgr.getSymbolManager().canSymbolicate(T)) {
Ted Kremenek42577d12008-11-12 19:18:35 +0000473 SVal V = InitVal ? *InitVal : UndefinedVal();
Zhongxing Xub241cf62010-02-08 08:48:05 +0000474 store = Bind(store, loc::MemRegionVal(VR), V);
Zhongxing Xubbe8ff42008-08-21 22:34:01 +0000475 }
476 }
477
478 return store;
479}
480
Ted Kremenek53ba0b62009-06-24 23:06:47 +0000481void BasicStoreManager::print(Store store, llvm::raw_ostream& Out,
Ted Kremeneka622d8c2008-08-19 22:24:03 +0000482 const char* nl, const char *sep) {
Mike Stump1eb44332009-09-09 15:08:12 +0000483
Ted Kremenek2c8e7882009-03-05 16:32:59 +0000484 BindingsTy B = GetBindings(store);
Ted Kremeneka622d8c2008-08-19 22:24:03 +0000485 Out << "Variables:" << nl;
Mike Stump1eb44332009-09-09 15:08:12 +0000486
Ted Kremeneka622d8c2008-08-19 22:24:03 +0000487 bool isFirst = true;
Mike Stump1eb44332009-09-09 15:08:12 +0000488
Ted Kremenek2c8e7882009-03-05 16:32:59 +0000489 for (BindingsTy::iterator I=B.begin(), E=B.end(); I != E; ++I) {
Ted Kremenek53ba0b62009-06-24 23:06:47 +0000490 if (isFirst)
491 isFirst = false;
492 else
493 Out << nl;
Mike Stump1eb44332009-09-09 15:08:12 +0000494
Ted Kremenek6f9b3a42009-07-13 23:53:06 +0000495 Out << ' ' << I.getKey() << " : " << I.getData();
Ted Kremeneka622d8c2008-08-19 22:24:03 +0000496 }
497}
Ted Kremenek2bc39c62008-08-29 00:47:32 +0000498
Ted Kremenek60dbad82008-09-03 03:06:11 +0000499
500void BasicStoreManager::iterBindings(Store store, BindingsHandler& f) {
Ted Kremenek2c8e7882009-03-05 16:32:59 +0000501 BindingsTy B = GetBindings(store);
Mike Stump1eb44332009-09-09 15:08:12 +0000502
Ted Kremenek2c8e7882009-03-05 16:32:59 +0000503 for (BindingsTy::iterator I=B.begin(), E=B.end(); I != E; ++I)
Ted Kremenek744b3042010-06-17 00:24:37 +0000504 if (!f.HandleBinding(*this, store, I.getKey(), I.getData()))
505 return;
Ted Kremenek9e240492008-10-04 05:50:14 +0000506
Ted Kremenek2bc39c62008-08-29 00:47:32 +0000507}
508
Ted Kremenek60dbad82008-09-03 03:06:11 +0000509StoreManager::BindingsHandler::~BindingsHandler() {}
Ted Kremenek1004a9f2009-07-29 18:16:25 +0000510
511//===----------------------------------------------------------------------===//
512// Binding invalidation.
513//===----------------------------------------------------------------------===//
514
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000515
516Store BasicStoreManager::InvalidateRegions(Store store,
Jordy Rosec2b7dfa2010-08-14 20:44:32 +0000517 const MemRegion * const *I,
518 const MemRegion * const *End,
519 const Expr *E, unsigned Count,
520 InvalidatedSymbols *IS,
521 bool invalidateGlobals,
522 InvalidatedRegions *Regions) {
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000523 if (invalidateGlobals) {
524 BindingsTy B = GetBindings(store);
525 for (BindingsTy::iterator I=B.begin(), End=B.end(); I != End; ++I) {
526 const MemRegion *R = I.getKey();
527 if (isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace()))
528 store = InvalidateRegion(store, R, E, Count, IS);
529 }
530 }
531
532 for ( ; I != End ; ++I) {
533 const MemRegion *R = *I;
534 // Don't invalidate globals twice.
535 if (invalidateGlobals) {
536 if (isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace()))
537 continue;
538 }
539 store = InvalidateRegion(store, *I, E, Count, IS);
Jordy Rosec2b7dfa2010-08-14 20:44:32 +0000540 if (Regions)
541 Regions->push_back(R);
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000542 }
543
544 // FIXME: This is copy-and-paste from RegionStore.cpp.
545 if (invalidateGlobals) {
546 // Bind the non-static globals memory space to a new symbol that we will
547 // use to derive the bindings for all non-static globals.
548 const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion();
549 SVal V =
550 ValMgr.getConjuredSymbolVal(/* SymbolTag = */ (void*) GS, E,
551 /* symbol type, doesn't matter */ Ctx.IntTy,
552 Count);
553
554 store = Bind(store, loc::MemRegionVal(GS), V);
Jordy Rosec2b7dfa2010-08-14 20:44:32 +0000555 if (Regions)
556 Regions->push_back(GS);
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000557 }
558
559 return store;
560}
561
562
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000563Store BasicStoreManager::InvalidateRegion(Store store,
564 const MemRegion *R,
565 const Expr *E,
566 unsigned Count,
567 InvalidatedSymbols *IS) {
Zhongxing Xu479529e2009-11-10 02:17:20 +0000568 R = R->StripCasts();
Mike Stump1eb44332009-09-09 15:08:12 +0000569
Ted Kremenek1004a9f2009-07-29 18:16:25 +0000570 if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R)))
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000571 return store;
Mike Stump1eb44332009-09-09 15:08:12 +0000572
Ted Kremenek473e1672009-10-16 00:30:49 +0000573 if (IS) {
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000574 BindingsTy B = GetBindings(store);
Ted Kremenek473e1672009-10-16 00:30:49 +0000575 if (BindingsTy::data_type *Val = B.lookup(R)) {
576 if (SymbolRef Sym = Val->getAsSymbol())
577 IS->insert(Sym);
578 }
579 }
580
Zhongxing Xu018220c2010-08-11 06:10:55 +0000581 QualType T = cast<TypedRegion>(R)->getValueType();
Ted Kremenek87806792009-09-27 20:45:21 +0000582 SVal V = ValMgr.getConjuredSymbolVal(R, E, T, Count);
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000583 return Bind(store, loc::MemRegionVal(R), V);
Ted Kremenek1004a9f2009-07-29 18:16:25 +0000584}
585