blob: 1c8ab11a96b685c1041f9c63ca75385c57dbd8e8 [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"
Argyrios Kyrtzidis98cabba2010-12-22 18:51:49 +000018#include "clang/GR/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;
Argyrios Kyrtzidis5a4f98f2010-12-22 18:53:20 +000022using namespace GR;
Ted Kremenek4323a572008-07-10 22:03:41 +000023
Mike Stump1eb44332009-09-09 15:08:12 +000024typedef llvm::ImmutableMap<const MemRegion*,SVal> BindingsTy;
Ted Kremenek60dbad82008-09-03 03:06:11 +000025
Ted Kremenek4323a572008-07-10 22:03:41 +000026namespace {
Mike Stump1eb44332009-09-09 15:08:12 +000027
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +000028class BasicStoreSubRegionMap : public SubRegionMap {
Ted Kremenek59e8f112009-03-03 01:35:36 +000029public:
30 BasicStoreSubRegionMap() {}
31
Ted Kremenek5dc27462009-03-03 02:51:43 +000032 bool iterSubRegions(const MemRegion* R, Visitor& V) const {
Ted Kremenek39fc7152009-03-05 16:41:21 +000033 return true; // Do nothing. No subregions.
Ted Kremenek59e8f112009-03-03 01:35:36 +000034 }
35};
Mike Stump1eb44332009-09-09 15:08:12 +000036
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +000037class BasicStoreManager : public StoreManager {
Ted Kremenek2c8e7882009-03-05 16:32:59 +000038 BindingsTy::Factory VBFactory;
Ted Kremenek4323a572008-07-10 22:03:41 +000039public:
Ted Kremenekf7a0cf42009-07-29 21:43:22 +000040 BasicStoreManager(GRStateManager& mgr)
Ted Kremenek82cd37c2009-08-21 23:25:54 +000041 : StoreManager(mgr), VBFactory(mgr.getAllocator()) {}
Mike Stump1eb44332009-09-09 15:08:12 +000042
Ted Kremenek9deb0e32008-10-24 20:32:16 +000043 ~BasicStoreManager() {}
Ted Kremenek4323a572008-07-10 22:03:41 +000044
Zhongxing Xuf5416bd2010-02-05 05:18:47 +000045 SubRegionMap *getSubRegionMap(Store store) {
Ted Kremenek14453bf2009-03-03 19:02:42 +000046 return new BasicStoreSubRegionMap();
Ted Kremenek59e8f112009-03-03 01:35:36 +000047 }
48
Zhongxing Xu576bb922010-02-05 03:01:53 +000049 SVal Retrieve(Store store, Loc loc, QualType T = QualType());
Mike Stump1eb44332009-09-09 15:08:12 +000050
Ted Kremenekdcee3ce2010-07-01 20:16:50 +000051 Store InvalidateRegion(Store store, const MemRegion *R, const Expr *E,
Zhongxing Xub4a9c612010-02-05 05:06:13 +000052 unsigned Count, InvalidatedSymbols *IS);
Zhongxing Xu4193eca2008-12-20 06:32:12 +000053
Ted Kremenekdcee3ce2010-07-01 20:16:50 +000054 Store InvalidateRegions(Store store, const MemRegion * const *Begin,
55 const MemRegion * const *End, const Expr *E,
56 unsigned Count, InvalidatedSymbols *IS,
Jordy Rosec2b7dfa2010-08-14 20:44:32 +000057 bool invalidateGlobals, InvalidatedRegions *Regions);
Ted Kremenekdcee3ce2010-07-01 20:16:50 +000058
Ted Kremenek82cd37c2009-08-21 23:25:54 +000059 Store scanForIvars(Stmt *B, const Decl* SelfDecl,
60 const MemRegion *SelfRegion, Store St);
Mike Stump1eb44332009-09-09 15:08:12 +000061
Zhongxing Xub241cf62010-02-08 08:48:05 +000062 Store Bind(Store St, Loc loc, SVal V);
Ted Kremenekc6ed3842009-01-07 22:56:17 +000063 Store Remove(Store St, Loc loc);
Zhongxing Xu17fd8632009-08-17 06:19:58 +000064 Store getInitialStore(const LocationContext *InitLoc);
Zhongxing Xubc678fd2008-10-07 01:31:04 +000065
Zhongxing Xub4a9c612010-02-05 05:06:13 +000066 Store BindCompoundLiteral(Store store, const CompoundLiteralExpr*,
67 const LocationContext*, SVal val) {
68 return store;
Ted Kremenek4f090272008-10-27 21:54:31 +000069 }
Mike Stump1eb44332009-09-09 15:08:12 +000070
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +000071 /// ArrayToPointer - Used by ExprEngine::VistCast to handle implicit
Ted Kremenek9deb0e32008-10-24 20:32:16 +000072 /// conversions between arrays and pointers.
Zhongxing Xuf1d537f2009-03-30 05:55:46 +000073 SVal ArrayToPointer(Loc Array) { return Array; }
Mike Stump1eb44332009-09-09 15:08:12 +000074
Ted Kremenek2ed14be2008-12-05 00:47:52 +000075 /// RemoveDeadBindings - Scans a BasicStore of 'state' for dead values.
Ted Kremenek2f26bc32009-08-02 04:45:08 +000076 /// It updatees the GRState object in place with the values removed.
Zhongxing Xu5e4cb342010-08-15 12:45:09 +000077 Store RemoveDeadBindings(Store store, const StackFrameContext *LCtx,
78 SymbolReaper& SymReaper,
Ted Kremenek2f26bc32009-08-02 04:45:08 +000079 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots);
Zhongxing Xubbe8ff42008-08-21 22:34:01 +000080
Ted Kremenek9deb0e32008-10-24 20:32:16 +000081 void iterBindings(Store store, BindingsHandler& f);
Ted Kremenek60dbad82008-09-03 03:06:11 +000082
Zhongxing Xub4a9c612010-02-05 05:06:13 +000083 Store BindDecl(Store store, const VarRegion *VR, SVal InitVal) {
84 return BindDeclInternal(store, VR, &InitVal);
Zhongxing Xu4193eca2008-12-20 06:32:12 +000085 }
86
Zhongxing Xub4a9c612010-02-05 05:06:13 +000087 Store BindDeclWithNoInit(Store store, const VarRegion *VR) {
88 return BindDeclInternal(store, VR, 0);
Zhongxing Xu4193eca2008-12-20 06:32:12 +000089 }
90
Ted Kremenekf6f56d42009-11-04 00:09:15 +000091 Store BindDeclInternal(Store store, const VarRegion *VR, SVal *InitVal);
Zhongxing Xubbe8ff42008-08-21 22:34:01 +000092
Ted Kremenek2c8e7882009-03-05 16:32:59 +000093 static inline BindingsTy GetBindings(Store store) {
94 return BindingsTy(static_cast<const BindingsTy::TreeTy*>(store));
Ted Kremeneka622d8c2008-08-19 22:24:03 +000095 }
96
Ted Kremenek53ba0b62009-06-24 23:06:47 +000097 void print(Store store, llvm::raw_ostream& Out, const char* nl,
98 const char *sep);
Zhongxing Xua1718c72009-04-03 07:33:13 +000099
100private:
Ted Kremenek5ba290a2010-03-02 21:43:54 +0000101 SVal LazyRetrieve(Store store, const TypedRegion *R);
Ted Kremenek60dbad82008-09-03 03:06:11 +0000102};
Mike Stump1eb44332009-09-09 15:08:12 +0000103
Ted Kremenek4323a572008-07-10 22:03:41 +0000104} // end anonymous namespace
105
106
Argyrios Kyrtzidis5a4f98f2010-12-22 18:53:20 +0000107StoreManager* GR::CreateBasicStoreManager(GRStateManager& StMgr) {
Ted Kremenek5f81c442008-08-28 23:31:31 +0000108 return new BasicStoreManager(StMgr);
Ted Kremenekd0c4b282008-08-25 19:33:03 +0000109}
Zhongxing Xu933c3e12008-10-21 06:54:23 +0000110
Ted Kremenek5fa93d52009-04-29 16:03:27 +0000111static bool isHigherOrderRawPtr(QualType T, ASTContext &C) {
Ted Kremenek1670e402009-04-11 00:11:10 +0000112 bool foundPointer = false;
Mike Stump1eb44332009-09-09 15:08:12 +0000113 while (1) {
Ted Kremenek6217b802009-07-29 21:53:49 +0000114 const PointerType *PT = T->getAs<PointerType>();
Ted Kremenek1670e402009-04-11 00:11:10 +0000115 if (!PT) {
116 if (!foundPointer)
117 return false;
Mike Stump1eb44332009-09-09 15:08:12 +0000118
Ted Kremenek5fa93d52009-04-29 16:03:27 +0000119 // intptr_t* or intptr_t**, etc?
120 if (T->isIntegerType() && C.getTypeSize(T) == C.getTypeSize(C.VoidPtrTy))
121 return true;
Mike Stump1eb44332009-09-09 15:08:12 +0000122
Ted Kremenek1670e402009-04-11 00:11:10 +0000123 QualType X = C.getCanonicalType(T).getUnqualifiedType();
124 return X == C.VoidTy;
125 }
Mike Stump1eb44332009-09-09 15:08:12 +0000126
Ted Kremenek1670e402009-04-11 00:11:10 +0000127 foundPointer = true;
128 T = PT->getPointeeType();
Mike Stump1eb44332009-09-09 15:08:12 +0000129 }
Ted Kremenek1670e402009-04-11 00:11:10 +0000130}
Mike Stump1eb44332009-09-09 15:08:12 +0000131
Ted Kremenek5ba290a2010-03-02 21:43:54 +0000132SVal BasicStoreManager::LazyRetrieve(Store store, const TypedRegion *R) {
133 const VarRegion *VR = dyn_cast<VarRegion>(R);
134 if (!VR)
135 return UnknownVal();
136
137 const VarDecl *VD = VR->getDecl();
138 QualType T = VD->getType();
139
140 // Only handle simple types that we can symbolicate.
141 if (!SymbolManager::canSymbolicate(T) || !T->isScalarType())
142 return UnknownVal();
143
144 // Globals and parameters start with symbolic values.
145 // Local variables initially are undefined.
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000146
147 // Non-static globals may have had their values reset by InvalidateRegions.
148 const MemSpaceRegion *MS = VR->getMemorySpace();
149 if (isa<NonStaticGlobalSpaceRegion>(MS)) {
150 BindingsTy B = GetBindings(store);
151 // FIXME: Copy-and-pasted from RegionStore.cpp.
152 if (BindingsTy::data_type *Val = B.lookup(MS)) {
153 if (SymbolRef parentSym = Val->getAsSymbol())
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000154 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000155
156 if (Val->isZeroConstant())
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000157 return svalBuilder.makeZeroVal(T);
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000158
159 if (Val->isUnknownOrUndef())
160 return *Val;
161
162 assert(0 && "Unknown default value.");
163 }
164 }
165
Ted Kremenek30986dd2010-03-10 00:18:08 +0000166 if (VR->hasGlobalsOrParametersStorage() ||
167 isa<UnknownSpaceRegion>(VR->getMemorySpace()))
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000168 return svalBuilder.getRegionValueSymbolVal(R);
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000169
Ted Kremenek5ba290a2010-03-02 21:43:54 +0000170 return UndefinedVal();
171}
172
Zhongxing Xu576bb922010-02-05 03:01:53 +0000173SVal BasicStoreManager::Retrieve(Store store, Loc loc, QualType T) {
Ted Kremenekc6ed3842009-01-07 22:56:17 +0000174 if (isa<UnknownVal>(loc))
Zhongxing Xuc999ed72010-02-04 02:39:47 +0000175 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000176
Ted Kremenek1894dce2009-08-25 20:51:30 +0000177 assert(!isa<UndefinedVal>(loc));
Mike Stump1eb44332009-09-09 15:08:12 +0000178
Ted Kremenekc6ed3842009-01-07 22:56:17 +0000179 switch (loc.getSubKind()) {
Ted Kremenek4323a572008-07-10 22:03:41 +0000180
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000181 case loc::MemRegionKind: {
Ted Kremenekf684d562009-03-05 18:08:28 +0000182 const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion();
Mike Stump1eb44332009-09-09 15:08:12 +0000183
Marcin Swiderski11b39d42010-11-16 07:15:33 +0000184 if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R) ||
185 isa<CXXThisRegion>(R)))
Zhongxing Xuc999ed72010-02-04 02:39:47 +0000186 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000187
Zhongxing Xu576bb922010-02-05 03:01:53 +0000188 BindingsTy B = GetBindings(store);
Ted Kremenek1894dce2009-08-25 20:51:30 +0000189 BindingsTy::data_type *Val = B.lookup(R);
Ted Kremenek5ba290a2010-03-02 21:43:54 +0000190 const TypedRegion *TR = cast<TypedRegion>(R);
Mike Stump1eb44332009-09-09 15:08:12 +0000191
Ted Kremenek5ba290a2010-03-02 21:43:54 +0000192 if (Val)
193 return CastRetrievedVal(*Val, TR, T);
Mike Stump1eb44332009-09-09 15:08:12 +0000194
Ted Kremenek5ba290a2010-03-02 21:43:54 +0000195 SVal V = LazyRetrieve(store, TR);
196 return V.isUnknownOrUndef() ? V : CastRetrievedVal(V, TR, T);
Ted Kremenek4323a572008-07-10 22:03:41 +0000197 }
Mike Stump1eb44332009-09-09 15:08:12 +0000198
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000199 case loc::ConcreteIntKind:
Ted Kremenek29836f92010-11-11 23:10:10 +0000200 // Support direct accesses to memory. It's up to individual checkers
201 // to flag an error.
202 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000203
Ted Kremenek4323a572008-07-10 22:03:41 +0000204 default:
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000205 assert (false && "Invalid Loc.");
Ted Kremenek4323a572008-07-10 22:03:41 +0000206 break;
207 }
Mike Stump1eb44332009-09-09 15:08:12 +0000208
Zhongxing Xuc999ed72010-02-04 02:39:47 +0000209 return UnknownVal();
Ted Kremenek4323a572008-07-10 22:03:41 +0000210}
Mike Stump1eb44332009-09-09 15:08:12 +0000211
Zhongxing Xub241cf62010-02-08 08:48:05 +0000212Store BasicStoreManager::Bind(Store store, Loc loc, SVal V) {
Zhongxing Xu87453d12009-06-28 10:16:11 +0000213 if (isa<loc::ConcreteInt>(loc))
214 return store;
215
Zhongxing Xuc2a650a2009-06-28 09:26:15 +0000216 const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion();
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000217
218 // Special case: a default symbol assigned to the NonStaticGlobalsSpaceRegion
219 // that is used to derive other symbols.
220 if (isa<NonStaticGlobalSpaceRegion>(R)) {
221 BindingsTy B = GetBindings(store);
Ted Kremenek3baf6722010-11-24 00:54:37 +0000222 return VBFactory.add(B, R, V).getRoot();
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000223 }
224
Zhongxing Xuc2a650a2009-06-28 09:26:15 +0000225 // Special case: handle store of pointer values (Loc) to pointers via
226 // a cast to intXX_t*, void*, etc. This is needed to handle
227 // OSCompareAndSwap32Barrier/OSCompareAndSwap64Barrier.
228 if (isa<Loc>(V) || isa<nonloc::LocAsInteger>(V))
229 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
230 // FIXME: Should check for index 0.
Zhongxing Xu018220c2010-08-11 06:10:55 +0000231 QualType T = ER->getLocationType();
Mike Stump1eb44332009-09-09 15:08:12 +0000232
Zhongxing Xu57663fe2010-08-15 10:08:38 +0000233 if (isHigherOrderRawPtr(T, Ctx))
Zhongxing Xuc2a650a2009-06-28 09:26:15 +0000234 R = ER->getSuperRegion();
Mike Stump1eb44332009-09-09 15:08:12 +0000235 }
236
Marcin Swiderski11b39d42010-11-16 07:15:33 +0000237 if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R) || isa<CXXThisRegion>(R)))
Zhongxing Xuc2a650a2009-06-28 09:26:15 +0000238 return store;
Ted Kremenek82cd37c2009-08-21 23:25:54 +0000239
Ted Kremenekab2f43c2009-08-25 23:29:04 +0000240 const TypedRegion *TyR = cast<TypedRegion>(R);
Mike Stump1eb44332009-09-09 15:08:12 +0000241
Ted Kremenekab2f43c2009-08-25 23:29:04 +0000242 // Do not bind to arrays. We need to explicitly check for this so that
243 // we do not encounter any weirdness of trying to load/store from arrays.
Zhongxing Xu018220c2010-08-11 06:10:55 +0000244 if (TyR->isBoundable() && TyR->getValueType()->isArrayType())
Mike Stump1eb44332009-09-09 15:08:12 +0000245 return store;
Ted Kremenekab2f43c2009-08-25 23:29:04 +0000246
Zhongxing Xuc2a650a2009-06-28 09:26:15 +0000247 if (nonloc::LocAsInteger *X = dyn_cast<nonloc::LocAsInteger>(&V)) {
248 // Only convert 'V' to a location iff the underlying region type
249 // is a location as well.
250 // FIXME: We are allowing a store of an arbitrary location to
251 // a pointer. We may wish to flag a type error here if the types
252 // are incompatible. This may also cause lots of breakage
253 // elsewhere. Food for thought.
Zhongxing Xu018220c2010-08-11 06:10:55 +0000254 if (TyR->isBoundable() && Loc::IsLocType(TyR->getValueType()))
Ted Kremenekab2f43c2009-08-25 23:29:04 +0000255 V = X->getLoc();
Ted Kremenek4323a572008-07-10 22:03:41 +0000256 }
Zhongxing Xuc2a650a2009-06-28 09:26:15 +0000257
258 BindingsTy B = GetBindings(store);
259 return V.isUnknown()
Ted Kremenek3baf6722010-11-24 00:54:37 +0000260 ? VBFactory.remove(B, R).getRoot()
261 : VBFactory.add(B, R, V).getRoot();
Ted Kremenek4323a572008-07-10 22:03:41 +0000262}
263
Ted Kremenekc6ed3842009-01-07 22:56:17 +0000264Store BasicStoreManager::Remove(Store store, Loc loc) {
265 switch (loc.getSubKind()) {
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000266 case loc::MemRegionKind: {
Ted Kremenekf684d562009-03-05 18:08:28 +0000267 const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion();
Mike Stump1eb44332009-09-09 15:08:12 +0000268
Marcin Swiderski11b39d42010-11-16 07:15:33 +0000269 if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R) ||
270 isa<CXXThisRegion>(R)))
Ted Kremenek9e240492008-10-04 05:50:14 +0000271 return store;
Mike Stump1eb44332009-09-09 15:08:12 +0000272
Ted Kremenek3baf6722010-11-24 00:54:37 +0000273 return VBFactory.remove(GetBindings(store), R).getRoot();
Ted Kremenekf59bf482008-07-17 18:38:48 +0000274 }
Ted Kremenek4323a572008-07-10 22:03:41 +0000275 default:
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000276 assert ("Remove for given Loc type not yet implemented.");
Ted Kremenekf59bf482008-07-17 18:38:48 +0000277 return store;
Ted Kremenek4323a572008-07-10 22:03:41 +0000278 }
279}
Ted Kremenekf59bf482008-07-17 18:38:48 +0000280
Zhongxing Xu5e4cb342010-08-15 12:45:09 +0000281Store BasicStoreManager::RemoveDeadBindings(Store store,
Zhongxing Xu17ddf1c2010-03-17 03:35:08 +0000282 const StackFrameContext *LCtx,
Zhongxing Xu72119c42010-02-05 05:34:29 +0000283 SymbolReaper& SymReaper,
Ted Kremenek2f26bc32009-08-02 04:45:08 +0000284 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots)
Mike Stump1eb44332009-09-09 15:08:12 +0000285{
Ted Kremenek2c8e7882009-03-05 16:32:59 +0000286 BindingsTy B = GetBindings(store);
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000287 typedef SVal::symbol_iterator symbol_iterator;
Mike Stump1eb44332009-09-09 15:08:12 +0000288
Ted Kremenekf59bf482008-07-17 18:38:48 +0000289 // Iterate over the variable bindings.
Ted Kremenek2c8e7882009-03-05 16:32:59 +0000290 for (BindingsTy::iterator I=B.begin(), E=B.end(); I!=E ; ++I) {
Ted Kremenekf684d562009-03-05 18:08:28 +0000291 if (const VarRegion *VR = dyn_cast<VarRegion>(I.getKey())) {
Jordy Rose7dadf792010-07-01 20:09:55 +0000292 if (SymReaper.isLive(VR))
Ted Kremenekf684d562009-03-05 18:08:28 +0000293 RegionRoots.push_back(VR);
294 else
295 continue;
Ted Kremenekf59bf482008-07-17 18:38:48 +0000296 }
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000297 else if (isa<ObjCIvarRegion>(I.getKey()) ||
Marcin Swiderski11b39d42010-11-16 07:15:33 +0000298 isa<NonStaticGlobalSpaceRegion>(I.getKey()) ||
299 isa<CXXThisRegion>(I.getKey()))
Ted Kremenekf684d562009-03-05 18:08:28 +0000300 RegionRoots.push_back(I.getKey());
Ted Kremenekf684d562009-03-05 18:08:28 +0000301 else
302 continue;
Mike Stump1eb44332009-09-09 15:08:12 +0000303
Ted Kremenekf684d562009-03-05 18:08:28 +0000304 // Mark the bindings in the data as live.
305 SVal X = I.getData();
306 for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI)
307 SymReaper.markLive(*SI);
Ted Kremenekbe912242009-03-05 16:31:07 +0000308 }
Mike Stump1eb44332009-09-09 15:08:12 +0000309
Ted Kremenekf59bf482008-07-17 18:38:48 +0000310 // Scan for live variables and live symbols.
Ted Kremenekf684d562009-03-05 18:08:28 +0000311 llvm::SmallPtrSet<const MemRegion*, 10> Marked;
Mike Stump1eb44332009-09-09 15:08:12 +0000312
Ted Kremenek9e240492008-10-04 05:50:14 +0000313 while (!RegionRoots.empty()) {
Ted Kremenek134e7492008-10-17 22:52:40 +0000314 const MemRegion* MR = RegionRoots.back();
Ted Kremenek9e240492008-10-04 05:50:14 +0000315 RegionRoots.pop_back();
Mike Stump1eb44332009-09-09 15:08:12 +0000316
Ted Kremenek134e7492008-10-17 22:52:40 +0000317 while (MR) {
318 if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(MR)) {
Ted Kremenek241677a2009-01-21 22:26:05 +0000319 SymReaper.markLive(SymR->getSymbol());
Ted Kremenek134e7492008-10-17 22:52:40 +0000320 break;
321 }
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000322 else if (isa<VarRegion>(MR) || isa<ObjCIvarRegion>(MR) ||
Marcin Swiderski11b39d42010-11-16 07:15:33 +0000323 isa<NonStaticGlobalSpaceRegion>(MR) || isa<CXXThisRegion>(MR)) {
Ted Kremenekf684d562009-03-05 18:08:28 +0000324 if (Marked.count(MR))
Ted Kremenek134e7492008-10-17 22:52:40 +0000325 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000326
327 Marked.insert(MR);
Zhongxing Xu72119c42010-02-05 05:34:29 +0000328 SVal X = Retrieve(store, loc::MemRegionVal(MR));
Mike Stump1eb44332009-09-09 15:08:12 +0000329
Ted Kremenek134e7492008-10-17 22:52:40 +0000330 // FIXME: We need to handle symbols nested in region definitions.
Ted Kremenek241677a2009-01-21 22:26:05 +0000331 for (symbol_iterator SI=X.symbol_begin(),SE=X.symbol_end();SI!=SE;++SI)
332 SymReaper.markLive(*SI);
Mike Stump1eb44332009-09-09 15:08:12 +0000333
Ted Kremenek134e7492008-10-17 22:52:40 +0000334 if (!isa<loc::MemRegionVal>(X))
335 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000336
Ted Kremenek134e7492008-10-17 22:52:40 +0000337 const loc::MemRegionVal& LVD = cast<loc::MemRegionVal>(X);
338 RegionRoots.push_back(LVD.getRegion());
339 break;
340 }
341 else if (const SubRegion* R = dyn_cast<SubRegion>(MR))
342 MR = R->getSuperRegion();
343 else
344 break;
345 }
Ted Kremenekf59bf482008-07-17 18:38:48 +0000346 }
Mike Stump1eb44332009-09-09 15:08:12 +0000347
348 // Remove dead variable bindings.
Ted Kremenek2c8e7882009-03-05 16:32:59 +0000349 for (BindingsTy::iterator I=B.begin(), E=B.end(); I!=E ; ++I) {
Ted Kremenekf684d562009-03-05 18:08:28 +0000350 const MemRegion* R = I.getKey();
Mike Stump1eb44332009-09-09 15:08:12 +0000351
Ted Kremenek9e240492008-10-04 05:50:14 +0000352 if (!Marked.count(R)) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000353 store = Remove(store, svalBuilder.makeLoc(R));
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000354 SVal X = I.getData();
Mike Stump1eb44332009-09-09 15:08:12 +0000355
Ted Kremenekf59bf482008-07-17 18:38:48 +0000356 for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI)
Ted Kremenek241677a2009-01-21 22:26:05 +0000357 SymReaper.maybeDead(*SI);
Ted Kremenekf59bf482008-07-17 18:38:48 +0000358 }
Ted Kremenek9e240492008-10-04 05:50:14 +0000359 }
Ted Kremenekf684d562009-03-05 18:08:28 +0000360
Zhongxing Xu5e4cb342010-08-15 12:45:09 +0000361 return store;
Ted Kremenekf59bf482008-07-17 18:38:48 +0000362}
Ted Kremenekcaa37242008-08-19 16:51:45 +0000363
Ted Kremenek82cd37c2009-08-21 23:25:54 +0000364Store BasicStoreManager::scanForIvars(Stmt *B, const Decl* SelfDecl,
365 const MemRegion *SelfRegion, Store St) {
Ted Kremenekf684d562009-03-05 18:08:28 +0000366 for (Stmt::child_iterator CI=B->child_begin(), CE=B->child_end();
367 CI != CE; ++CI) {
Mike Stump1eb44332009-09-09 15:08:12 +0000368
Ted Kremenekf684d562009-03-05 18:08:28 +0000369 if (!*CI)
370 continue;
Mike Stump1eb44332009-09-09 15:08:12 +0000371
Ted Kremenekf684d562009-03-05 18:08:28 +0000372 // Check if the statement is an ivar reference. We only
373 // care about self.ivar.
374 if (ObjCIvarRefExpr *IV = dyn_cast<ObjCIvarRefExpr>(*CI)) {
375 const Expr *Base = IV->getBase()->IgnoreParenCasts();
376 if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Base)) {
377 if (DR->getDecl() == SelfDecl) {
Zhongxing Xu14d23282010-03-01 06:56:52 +0000378 const ObjCIvarRegion *IVR = MRMgr.getObjCIvarRegion(IV->getDecl(),
Mike Stump1eb44332009-09-09 15:08:12 +0000379 SelfRegion);
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000380 SVal X = svalBuilder.getRegionValueSymbolVal(IVR);
381 St = Bind(St, svalBuilder.makeLoc(IVR), X);
Ted Kremenekf684d562009-03-05 18:08:28 +0000382 }
383 }
384 }
385 else
Ted Kremenek82cd37c2009-08-21 23:25:54 +0000386 St = scanForIvars(*CI, SelfDecl, SelfRegion, St);
Ted Kremenekf684d562009-03-05 18:08:28 +0000387 }
Mike Stump1eb44332009-09-09 15:08:12 +0000388
Ted Kremenekf684d562009-03-05 18:08:28 +0000389 return St;
390}
391
Mike Stump1eb44332009-09-09 15:08:12 +0000392Store BasicStoreManager::getInitialStore(const LocationContext *InitLoc) {
Ted Kremenekcaa37242008-08-19 16:51:45 +0000393 // The LiveVariables information already has a compilation of all VarDecls
394 // used in the function. Iterate through this set, and "symbolicate"
395 // any VarDecl whose value originally comes from outside the function.
Ted Kremenekcaa37242008-08-19 16:51:45 +0000396 typedef LiveVariables::AnalysisDataTy LVDataTy;
Zhongxing Xu17fd8632009-08-17 06:19:58 +0000397 LVDataTy& D = InitLoc->getLiveVariables()->getAnalysisData();
Ted Kremenek3baf6722010-11-24 00:54:37 +0000398 Store St = VBFactory.getEmptyMap().getRoot();
Ted Kremenekcaa37242008-08-19 16:51:45 +0000399
400 for (LVDataTy::decl_iterator I=D.begin_decl(), E=D.end_decl(); I != E; ++I) {
Zhongxing Xuce2bc7e32010-07-20 02:46:11 +0000401 const NamedDecl* ND = I->first;
Ted Kremenekcaa37242008-08-19 16:51:45 +0000402
Ted Kremenek9deb0e32008-10-24 20:32:16 +0000403 // Handle implicit parameters.
Zhongxing Xuce2bc7e32010-07-20 02:46:11 +0000404 if (const ImplicitParamDecl* PD = dyn_cast<ImplicitParamDecl>(ND)) {
Mike Stump1eb44332009-09-09 15:08:12 +0000405 const Decl& CD = *InitLoc->getDecl();
Ted Kremenek9deb0e32008-10-24 20:32:16 +0000406 if (const ObjCMethodDecl* MD = dyn_cast<ObjCMethodDecl>(&CD)) {
407 if (MD->getSelfDecl() == PD) {
Ted Kremenekc410d4d2009-12-16 23:53:37 +0000408 // FIXME: Add type constraints (when they become available) to
409 // SelfRegion? (i.e., it implements MD->getClassInterface()).
Zhongxing Xu14d23282010-03-01 06:56:52 +0000410 const VarRegion *VR = MRMgr.getVarRegion(PD, InitLoc);
Ted Kremenekc410d4d2009-12-16 23:53:37 +0000411 const MemRegion *SelfRegion =
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000412 svalBuilder.getRegionValueSymbolVal(VR).getAsRegion();
Ted Kremenek5ba290a2010-03-02 21:43:54 +0000413 assert(SelfRegion);
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000414 St = Bind(St, svalBuilder.makeLoc(VR), loc::MemRegionVal(SelfRegion));
Ted Kremenekf684d562009-03-05 18:08:28 +0000415 // Scan the method for ivar references. While this requires an
416 // entire AST scan, the cost should not be high in practice.
Ted Kremenek82cd37c2009-08-21 23:25:54 +0000417 St = scanForIvars(MD->getBody(), PD, SelfRegion, St);
Ted Kremenek9deb0e32008-10-24 20:32:16 +0000418 }
419 }
420 }
Ted Kremenekcaa37242008-08-19 16:51:45 +0000421 }
Ted Kremenek5ba290a2010-03-02 21:43:54 +0000422
Marcin Swiderski0aac2ba2010-11-17 06:22:54 +0000423 if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(InitLoc->getDecl())) {
424 // For C++ methods add symbolic region for 'this' in initial stack frame.
425 QualType ThisT = MD->getThisType(StateMgr.getContext());
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000426 MemRegionManager &RegMgr = svalBuilder.getRegionManager();
Marcin Swiderski0aac2ba2010-11-17 06:22:54 +0000427 const CXXThisRegion *ThisR = RegMgr.getCXXThisRegion(ThisT, InitLoc);
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000428 SVal ThisV = svalBuilder.getRegionValueSymbolVal(ThisR);
429 St = Bind(St, svalBuilder.makeLoc(ThisR), ThisV);
Marcin Swiderski0aac2ba2010-11-17 06:22:54 +0000430 }
431
Ted Kremenekcaa37242008-08-19 16:51:45 +0000432 return St;
433}
Ted Kremeneka622d8c2008-08-19 22:24:03 +0000434
Ted Kremenekf6f56d42009-11-04 00:09:15 +0000435Store BasicStoreManager::BindDeclInternal(Store store, const VarRegion* VR,
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000436 SVal* InitVal) {
Mike Stump1eb44332009-09-09 15:08:12 +0000437
Ted Kremeneke53c0692008-08-23 00:50:55 +0000438 BasicValueFactory& BasicVals = StateMgr.getBasicVals();
Ted Kremenekf6f56d42009-11-04 00:09:15 +0000439 const VarDecl *VD = VR->getDecl();
Mike Stump1eb44332009-09-09 15:08:12 +0000440
Zhongxing Xubbe8ff42008-08-21 22:34:01 +0000441 // BasicStore does not model arrays and structs.
Douglas Gregorfb87b892010-04-26 21:31:17 +0000442 if (VD->getType()->isArrayType() || VD->getType()->isStructureOrClassType())
Zhongxing Xubbe8ff42008-08-21 22:34:01 +0000443 return store;
444
445 if (VD->hasGlobalStorage()) {
446 // Handle variables with global storage: extern, static, PrivateExtern.
447
448 // FIXME:: static variables may have an initializer, but the second time a
449 // function is called those values may not be current. Currently, a function
450 // will not be called more than once.
451
452 // Static global variables should not be visited here.
John McCalld931b082010-08-26 03:08:43 +0000453 assert(!(VD->getStorageClass() == SC_Static &&
Zhongxing Xubbe8ff42008-08-21 22:34:01 +0000454 VD->isFileVarDecl()));
Mike Stump1eb44332009-09-09 15:08:12 +0000455
Zhongxing Xubbe8ff42008-08-21 22:34:01 +0000456 // Process static variables.
John McCalld931b082010-08-26 03:08:43 +0000457 if (VD->getStorageClass() == SC_Static) {
Zhongxing Xubbe8ff42008-08-21 22:34:01 +0000458 // C99: 6.7.8 Initialization
459 // If an object that has static storage duration is not initialized
Mike Stump1eb44332009-09-09 15:08:12 +0000460 // explicitly, then:
461 // —if it has pointer type, it is initialized to a null pointer;
462 // —if it has arithmetic type, it is initialized to (positive or
Zhongxing Xubbe8ff42008-08-21 22:34:01 +0000463 // unsigned) zero;
Ted Kremenek42577d12008-11-12 19:18:35 +0000464 if (!InitVal) {
Zhongxing Xubbe8ff42008-08-21 22:34:01 +0000465 QualType T = VD->getType();
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000466 if (Loc::IsLocType(T))
Zhongxing Xub241cf62010-02-08 08:48:05 +0000467 store = Bind(store, loc::MemRegionVal(VR),
Zhongxing Xu8485ec62008-10-21 06:27:32 +0000468 loc::ConcreteInt(BasicVals.getValue(0, T)));
Ted Kremenekc0708432010-07-29 00:28:40 +0000469 else if (T->isIntegerType() && T->isScalarType())
Zhongxing Xub241cf62010-02-08 08:48:05 +0000470 store = Bind(store, loc::MemRegionVal(VR),
Zhongxing Xu8485ec62008-10-21 06:27:32 +0000471 nonloc::ConcreteInt(BasicVals.getValue(0, T)));
Zhongxing Xubbe8ff42008-08-21 22:34:01 +0000472 } else {
Zhongxing Xub241cf62010-02-08 08:48:05 +0000473 store = Bind(store, loc::MemRegionVal(VR), *InitVal);
Zhongxing Xubbe8ff42008-08-21 22:34:01 +0000474 }
475 }
476 } else {
477 // Process local scalar variables.
478 QualType T = VD->getType();
Ted Kremenekc0708432010-07-29 00:28:40 +0000479 // BasicStore only supports scalars.
Marcin Swiderski11b39d42010-11-16 07:15:33 +0000480 if ((T->isScalarType() || T->isReferenceType()) &&
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000481 svalBuilder.getSymbolManager().canSymbolicate(T)) {
Ted Kremenek42577d12008-11-12 19:18:35 +0000482 SVal V = InitVal ? *InitVal : UndefinedVal();
Zhongxing Xub241cf62010-02-08 08:48:05 +0000483 store = Bind(store, loc::MemRegionVal(VR), V);
Zhongxing Xubbe8ff42008-08-21 22:34:01 +0000484 }
485 }
486
487 return store;
488}
489
Ted Kremenek53ba0b62009-06-24 23:06:47 +0000490void BasicStoreManager::print(Store store, llvm::raw_ostream& Out,
Ted Kremeneka622d8c2008-08-19 22:24:03 +0000491 const char* nl, const char *sep) {
Mike Stump1eb44332009-09-09 15:08:12 +0000492
Ted Kremenek2c8e7882009-03-05 16:32:59 +0000493 BindingsTy B = GetBindings(store);
Ted Kremeneka622d8c2008-08-19 22:24:03 +0000494 Out << "Variables:" << nl;
Mike Stump1eb44332009-09-09 15:08:12 +0000495
Ted Kremeneka622d8c2008-08-19 22:24:03 +0000496 bool isFirst = true;
Mike Stump1eb44332009-09-09 15:08:12 +0000497
Ted Kremenek2c8e7882009-03-05 16:32:59 +0000498 for (BindingsTy::iterator I=B.begin(), E=B.end(); I != E; ++I) {
Ted Kremenek53ba0b62009-06-24 23:06:47 +0000499 if (isFirst)
500 isFirst = false;
501 else
502 Out << nl;
Mike Stump1eb44332009-09-09 15:08:12 +0000503
Ted Kremenek6f9b3a42009-07-13 23:53:06 +0000504 Out << ' ' << I.getKey() << " : " << I.getData();
Ted Kremeneka622d8c2008-08-19 22:24:03 +0000505 }
506}
Ted Kremenek2bc39c62008-08-29 00:47:32 +0000507
Ted Kremenek60dbad82008-09-03 03:06:11 +0000508
509void BasicStoreManager::iterBindings(Store store, BindingsHandler& f) {
Ted Kremenek2c8e7882009-03-05 16:32:59 +0000510 BindingsTy B = GetBindings(store);
Mike Stump1eb44332009-09-09 15:08:12 +0000511
Ted Kremenek2c8e7882009-03-05 16:32:59 +0000512 for (BindingsTy::iterator I=B.begin(), E=B.end(); I != E; ++I)
Ted Kremenek744b3042010-06-17 00:24:37 +0000513 if (!f.HandleBinding(*this, store, I.getKey(), I.getData()))
514 return;
Ted Kremenek9e240492008-10-04 05:50:14 +0000515
Ted Kremenek2bc39c62008-08-29 00:47:32 +0000516}
517
Ted Kremenek60dbad82008-09-03 03:06:11 +0000518StoreManager::BindingsHandler::~BindingsHandler() {}
Ted Kremenek1004a9f2009-07-29 18:16:25 +0000519
520//===----------------------------------------------------------------------===//
521// Binding invalidation.
522//===----------------------------------------------------------------------===//
523
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000524
525Store BasicStoreManager::InvalidateRegions(Store store,
Jordy Rosec2b7dfa2010-08-14 20:44:32 +0000526 const MemRegion * const *I,
527 const MemRegion * const *End,
528 const Expr *E, unsigned Count,
529 InvalidatedSymbols *IS,
530 bool invalidateGlobals,
531 InvalidatedRegions *Regions) {
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000532 if (invalidateGlobals) {
533 BindingsTy B = GetBindings(store);
534 for (BindingsTy::iterator I=B.begin(), End=B.end(); I != End; ++I) {
535 const MemRegion *R = I.getKey();
536 if (isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace()))
537 store = InvalidateRegion(store, R, E, Count, IS);
538 }
539 }
540
541 for ( ; I != End ; ++I) {
542 const MemRegion *R = *I;
543 // Don't invalidate globals twice.
544 if (invalidateGlobals) {
545 if (isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace()))
546 continue;
547 }
548 store = InvalidateRegion(store, *I, E, Count, IS);
Jordy Rosec2b7dfa2010-08-14 20:44:32 +0000549 if (Regions)
550 Regions->push_back(R);
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000551 }
552
553 // FIXME: This is copy-and-paste from RegionStore.cpp.
554 if (invalidateGlobals) {
555 // Bind the non-static globals memory space to a new symbol that we will
556 // use to derive the bindings for all non-static globals.
557 const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion();
558 SVal V =
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000559 svalBuilder.getConjuredSymbolVal(/* SymbolTag = */ (void*) GS, E,
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000560 /* symbol type, doesn't matter */ Ctx.IntTy,
561 Count);
562
563 store = Bind(store, loc::MemRegionVal(GS), V);
Jordy Rosec2b7dfa2010-08-14 20:44:32 +0000564 if (Regions)
565 Regions->push_back(GS);
Ted Kremenekdcee3ce2010-07-01 20:16:50 +0000566 }
567
568 return store;
569}
570
571
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000572Store BasicStoreManager::InvalidateRegion(Store store,
573 const MemRegion *R,
574 const Expr *E,
575 unsigned Count,
576 InvalidatedSymbols *IS) {
Zhongxing Xu479529e2009-11-10 02:17:20 +0000577 R = R->StripCasts();
Mike Stump1eb44332009-09-09 15:08:12 +0000578
Ted Kremenek1004a9f2009-07-29 18:16:25 +0000579 if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R)))
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000580 return store;
Mike Stump1eb44332009-09-09 15:08:12 +0000581
Ted Kremenek473e1672009-10-16 00:30:49 +0000582 if (IS) {
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000583 BindingsTy B = GetBindings(store);
Ted Kremenek473e1672009-10-16 00:30:49 +0000584 if (BindingsTy::data_type *Val = B.lookup(R)) {
585 if (SymbolRef Sym = Val->getAsSymbol())
586 IS->insert(Sym);
587 }
588 }
589
Zhongxing Xu018220c2010-08-11 06:10:55 +0000590 QualType T = cast<TypedRegion>(R)->getValueType();
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000591 SVal V = svalBuilder.getConjuredSymbolVal(R, E, T, Count);
Zhongxing Xub4a9c612010-02-05 05:06:13 +0000592 return Bind(store, loc::MemRegionVal(R), V);
Ted Kremenek1004a9f2009-07-29 18:16:25 +0000593}
594