blob: 6238ff20ed7a9a0d12ce12fbbb335abc377092c6 [file] [log] [blame]
Zhongxing Xu17892752008-10-08 02:50:44 +00001//== RegionStore.cpp - Field-sensitive store model --------------*- 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 defines a basic region store model. In this model, we do have field
11// sensitivity. But we assume nothing about the heap shape. So recursive data
12// structures are largely ignored. Basically we do 1-limiting analysis.
13// Parameter pointers are assumed with no aliasing. Pointee objects of
14// parameters are created lazily.
15//
16//===----------------------------------------------------------------------===//
17#include "clang/Analysis/PathSensitive/MemRegion.h"
18#include "clang/Analysis/PathSensitive/GRState.h"
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000019#include "clang/Analysis/PathSensitive/GRStateTrait.h"
Zhongxing Xu17892752008-10-08 02:50:44 +000020#include "clang/Analysis/Analyses/LiveVariables.h"
21
22#include "llvm/ADT/ImmutableMap.h"
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000023#include "llvm/ADT/ImmutableList.h"
Zhongxing Xua071eb02008-10-24 06:01:33 +000024#include "llvm/Support/raw_ostream.h"
Zhongxing Xu17892752008-10-08 02:50:44 +000025#include "llvm/Support/Compiler.h"
26
27using namespace clang;
28
Zhongxing Xubaf03a72008-11-24 09:44:56 +000029// Actual Store type.
Zhongxing Xu1c96b242008-10-17 05:57:07 +000030typedef llvm::ImmutableMap<const MemRegion*, SVal> RegionBindingsTy;
Zhongxing Xubaf03a72008-11-24 09:44:56 +000031
Ted Kremenek50dc1b32008-12-24 01:05:03 +000032//===----------------------------------------------------------------------===//
33// Region "Views"
34//===----------------------------------------------------------------------===//
35//
36// MemRegions can be layered on top of each other. This GDM entry tracks
37// what are the MemRegions that layer a given MemRegion.
38//
Zhongxing Xu5834ed62009-01-13 01:49:57 +000039typedef llvm::ImmutableSet<const MemRegion*> RegionViews;
Ted Kremenek50dc1b32008-12-24 01:05:03 +000040namespace { class VISIBILITY_HIDDEN RegionViewMap {}; }
41static int RegionViewMapIndex = 0;
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000042namespace clang {
Ted Kremenek50dc1b32008-12-24 01:05:03 +000043 template<> struct GRStateTrait<RegionViewMap>
44 : public GRStatePartialTrait<llvm::ImmutableMap<const MemRegion*,
45 RegionViews> > {
46
47 static void* GDMIndex() { return &RegionViewMapIndex; }
48 };
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000049}
Zhongxing Xu17892752008-10-08 02:50:44 +000050
Ted Kremenek50dc1b32008-12-24 01:05:03 +000051//===----------------------------------------------------------------------===//
52// Region "Extents"
53//===----------------------------------------------------------------------===//
54//
55// MemRegions represent chunks of memory with a size (their "extent"). This
56// GDM entry tracks the extents for regions. Extents are in bytes.
Ted Kremenekd6cfbe42009-01-07 22:18:50 +000057//
Ted Kremenek50dc1b32008-12-24 01:05:03 +000058namespace { class VISIBILITY_HIDDEN RegionExtents {}; }
59static int RegionExtentsIndex = 0;
Zhongxing Xubaf03a72008-11-24 09:44:56 +000060namespace clang {
Ted Kremenek50dc1b32008-12-24 01:05:03 +000061 template<> struct GRStateTrait<RegionExtents>
62 : public GRStatePartialTrait<llvm::ImmutableMap<const MemRegion*, SVal> > {
63 static void* GDMIndex() { return &RegionExtentsIndex; }
64 };
Zhongxing Xubaf03a72008-11-24 09:44:56 +000065}
66
Ted Kremenek50dc1b32008-12-24 01:05:03 +000067//===----------------------------------------------------------------------===//
68// Region "killsets".
69//===----------------------------------------------------------------------===//
70//
Zhongxing Xu5834ed62009-01-13 01:49:57 +000071// RegionStore lazily adds value bindings to regions when the analyzer handles
72// assignment statements. Killsets track which default values have been
73// killed, thus distinguishing between "unknown" values and default
74// values. Regions are added to killset only when they are assigned "unknown"
75// directly, otherwise we should have their value in the region bindings.
Ted Kremenek50dc1b32008-12-24 01:05:03 +000076//
77namespace { class VISIBILITY_HIDDEN RegionKills {}; }
Ted Kremenek2ed14be2008-12-05 00:47:52 +000078static int RegionKillsIndex = 0;
Ted Kremenekc48ea6e2008-12-04 02:08:27 +000079namespace clang {
Ted Kremenek2ed14be2008-12-05 00:47:52 +000080 template<> struct GRStateTrait<RegionKills>
Ted Kremenek50dc1b32008-12-24 01:05:03 +000081 : public GRStatePartialTrait< llvm::ImmutableSet<const MemRegion*> > {
Ted Kremenek2ed14be2008-12-05 00:47:52 +000082 static void* GDMIndex() { return &RegionKillsIndex; }
Ted Kremenekc48ea6e2008-12-04 02:08:27 +000083 };
84}
85
Ted Kremenek50dc1b32008-12-24 01:05:03 +000086//===----------------------------------------------------------------------===//
Zhongxing Xu5834ed62009-01-13 01:49:57 +000087// Regions with default values.
Ted Kremenek50dc1b32008-12-24 01:05:03 +000088//===----------------------------------------------------------------------===//
89//
Zhongxing Xu5834ed62009-01-13 01:49:57 +000090// This GDM entry tracks what regions have a default value if they have no bound
91// value and have not been killed.
Ted Kremenek50dc1b32008-12-24 01:05:03 +000092//
93namespace { class VISIBILITY_HIDDEN RegionDefaultValue {}; }
94static int RegionDefaultValueIndex = 0;
95namespace clang {
96 template<> struct GRStateTrait<RegionDefaultValue>
97 : public GRStatePartialTrait<llvm::ImmutableMap<const MemRegion*, SVal> > {
98 static void* GDMIndex() { return &RegionDefaultValueIndex; }
99 };
100}
101
102//===----------------------------------------------------------------------===//
103// Main RegionStore logic.
104//===----------------------------------------------------------------------===//
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000105
Zhongxing Xu17892752008-10-08 02:50:44 +0000106namespace {
107
Ted Kremenek59e8f112009-03-03 01:35:36 +0000108class VISIBILITY_HIDDEN RegionStoreSubRegionMap : public SubRegionMap {
109 typedef llvm::DenseMap<const MemRegion*,
110 llvm::ImmutableSet<const MemRegion*> > Map;
111
112 llvm::ImmutableSet<const MemRegion*>::Factory F;
113 Map M;
114
115public:
116 void add(const MemRegion* Parent, const MemRegion* SubRegion) {
117 Map::iterator I = M.find(Parent);
118 M.insert(std::make_pair(Parent,
119 F.Add(I == M.end() ? F.GetEmptySet() : I->second, SubRegion)));
120 }
121
122 ~RegionStoreSubRegionMap() {}
123
Ted Kremenek5dc27462009-03-03 02:51:43 +0000124 bool iterSubRegions(const MemRegion* Parent, Visitor& V) const {
Ted Kremenek59e8f112009-03-03 01:35:36 +0000125 Map::iterator I = M.find(Parent);
126
127 if (I == M.end())
Ted Kremenek5dc27462009-03-03 02:51:43 +0000128 return true;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000129
130 llvm::ImmutableSet<const MemRegion*> S = I->second;
131 for (llvm::ImmutableSet<const MemRegion*>::iterator SI=S.begin(),SE=S.end();
132 SI != SE; ++SI) {
133 if (!V.Visit(Parent, *SI))
Ted Kremenek5dc27462009-03-03 02:51:43 +0000134 return false;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000135 }
Ted Kremenek5dc27462009-03-03 02:51:43 +0000136
137 return true;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000138 }
139};
140
Zhongxing Xu17892752008-10-08 02:50:44 +0000141class VISIBILITY_HIDDEN RegionStoreManager : public StoreManager {
142 RegionBindingsTy::Factory RBFactory;
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000143 RegionViews::Factory RVFactory;
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000144
Zhongxing Xu17892752008-10-08 02:50:44 +0000145 GRStateManager& StateMgr;
Ted Kremenek6fd8f912009-01-22 23:43:57 +0000146 const MemRegion* SelfRegion;
147 const ImplicitParamDecl *SelfDecl;
Zhongxing Xu17892752008-10-08 02:50:44 +0000148
149public:
150 RegionStoreManager(GRStateManager& mgr)
Ted Kremenekd6cfbe42009-01-07 22:18:50 +0000151 : StoreManager(mgr.getAllocator()),
152 RBFactory(mgr.getAllocator()),
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000153 RVFactory(mgr.getAllocator()),
Ted Kremenek6fd8f912009-01-22 23:43:57 +0000154 StateMgr(mgr), SelfRegion(0), SelfDecl(0) {
155 if (const ObjCMethodDecl* MD =
156 dyn_cast<ObjCMethodDecl>(&StateMgr.getCodeDecl()))
157 SelfDecl = MD->getSelfDecl();
158 }
Zhongxing Xu17892752008-10-08 02:50:44 +0000159
160 virtual ~RegionStoreManager() {}
161
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000162 MemRegionManager& getRegionManager() { return MRMgr; }
Ted Kremenek4f090272008-10-27 21:54:31 +0000163
Ted Kremenek59e8f112009-03-03 01:35:36 +0000164 std::auto_ptr<SubRegionMap> getSubRegionMap(const GRState *state);
165
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000166 const GRState* BindCompoundLiteral(const GRState* St,
167 const CompoundLiteralExpr* CL, SVal V);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000168
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000169 /// getLValueString - Returns an SVal representing the lvalue of a
170 /// StringLiteral. Within RegionStore a StringLiteral has an
171 /// associated StringRegion, and the lvalue of a StringLiteral is
172 /// the lvalue of that region.
Zhongxing Xu143bf822008-10-25 14:18:57 +0000173 SVal getLValueString(const GRState* St, const StringLiteral* S);
174
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000175 /// getLValueCompoundLiteral - Returns an SVal representing the
176 /// lvalue of a compound literal. Within RegionStore a compound
177 /// literal has an associated region, and the lvalue of the
178 /// compound literal is the lvalue of that region.
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000179 SVal getLValueCompoundLiteral(const GRState* St, const CompoundLiteralExpr*);
180
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000181 /// getLValueVar - Returns an SVal that represents the lvalue of a
182 /// variable. Within RegionStore a variable has an associated
183 /// VarRegion, and the lvalue of the variable is the lvalue of that region.
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000184 SVal getLValueVar(const GRState* St, const VarDecl* VD);
185
186 SVal getLValueIvar(const GRState* St, const ObjCIvarDecl* D, SVal Base);
187
188 SVal getLValueField(const GRState* St, SVal Base, const FieldDecl* D);
189
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000190 SVal getLValueElement(const GRState* St, SVal Base, SVal Offset);
191
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000192 SVal getSizeInElements(const GRState* St, const MemRegion* R);
193
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000194 /// ArrayToPointer - Emulates the "decay" of an array to a pointer
195 /// type. 'Array' represents the lvalue of the array being decayed
196 /// to a pointer, and the returned SVal represents the decayed
197 /// version of that lvalue (i.e., a pointer to the first element of
198 /// the array). This is called by GRExprEngine when evaluating
199 /// casts from arrays to pointers.
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000200 SVal ArrayToPointer(SVal Array);
201
Ted Kremenek6eddeb12008-12-13 21:49:13 +0000202 /// CastRegion - Used by GRExprEngine::VisitCast to handle casts from
203 /// a MemRegion* to a specific location type. 'R' is the region being
204 /// casted and 'CastToTy' the result type of the cast.
205 CastResult CastRegion(const GRState* state, const MemRegion* R,
206 QualType CastToTy);
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000207
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000208 SVal EvalBinOp(BinaryOperator::Opcode Op, Loc L, NonLoc R);
209
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000210 /// The high level logic for this method is this:
211 /// Retrieve (L)
212 /// if L has binding
213 /// return L's binding
214 /// else if L is in killset
215 /// return unknown
216 /// else
217 /// if L is on stack or heap
218 /// return undefined
219 /// else
220 /// return symbolic
Ted Kremenek2ed14be2008-12-05 00:47:52 +0000221 SVal Retrieve(const GRState* state, Loc L, QualType T = QualType());
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000222
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000223 const GRState* Bind(const GRState* St, Loc LV, SVal V);
Zhongxing Xu17892752008-10-08 02:50:44 +0000224
Zhongxing Xu9c9ca082008-12-16 02:36:30 +0000225 Store Remove(Store store, Loc LV);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000226
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000227 Store getInitialStore() { return RBFactory.GetEmptyMap().getRoot(); }
Ted Kremenek9deb0e32008-10-24 20:32:16 +0000228
229 /// getSelfRegion - Returns the region for the 'self' (Objective-C) or
230 /// 'this' object (C++). When used when analyzing a normal function this
231 /// method returns NULL.
232 const MemRegion* getSelfRegion(Store) {
Ted Kremenek6fd8f912009-01-22 23:43:57 +0000233 if (!SelfDecl)
234 return 0;
235
236 if (!SelfRegion) {
237 const ObjCMethodDecl *MD = cast<ObjCMethodDecl>(&StateMgr.getCodeDecl());
238 SelfRegion = MRMgr.getObjCObjectRegion(MD->getClassInterface(),
239 MRMgr.getHeapRegion());
240 }
241
242 return SelfRegion;
Ted Kremenek9deb0e32008-10-24 20:32:16 +0000243 }
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000244
Ted Kremenek2ed14be2008-12-05 00:47:52 +0000245 /// RemoveDeadBindings - Scans the RegionStore of 'state' for dead values.
246 /// It returns a new Store with these values removed, and populates LSymbols
247 // and DSymbols with the known set of live and dead symbols respectively.
248 Store RemoveDeadBindings(const GRState* state, Stmt* Loc,
Ted Kremenek241677a2009-01-21 22:26:05 +0000249 SymbolReaper& SymReaper,
250 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000251
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000252 const GRState* BindDecl(const GRState* St, const VarDecl* VD, SVal InitVal);
253
254 const GRState* BindDeclWithNoInit(const GRState* St, const VarDecl* VD) {
255 return St;
256 }
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000257
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000258 const GRState* setExtent(const GRState* St, const MemRegion* R, SVal Extent);
259
Zhongxing Xu17892752008-10-08 02:50:44 +0000260 static inline RegionBindingsTy GetRegionBindings(Store store) {
Zhongxing Xu9c9ca082008-12-16 02:36:30 +0000261 return RegionBindingsTy(static_cast<const RegionBindingsTy::TreeTy*>(store));
Zhongxing Xu17892752008-10-08 02:50:44 +0000262 }
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000263
Zhongxing Xu5b8b6f22008-10-24 04:33:15 +0000264 void print(Store store, std::ostream& Out, const char* nl, const char *sep);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000265
266 void iterBindings(Store store, BindingsHandler& f) {
267 // FIXME: Implement.
268 }
Zhongxing Xua82512a2008-10-24 08:42:28 +0000269
270private:
271 Loc getVarLoc(const VarDecl* VD) {
272 return loc::MemRegionVal(MRMgr.getVarRegion(VD));
273 }
274
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000275 const GRState* BindArray(const GRState* St, const TypedRegion* R, SVal V);
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000276
Zhongxing Xu0b242ec2008-12-04 01:12:41 +0000277 /// Retrieve the values in a struct and return a CompoundVal, used when doing
278 /// struct copy:
279 /// struct s x, y;
280 /// x = y;
281 /// y's value is retrieved by this method.
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000282 SVal RetrieveStruct(const GRState* St, const TypedRegion* R);
Zhongxing Xu0b242ec2008-12-04 01:12:41 +0000283
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000284 const GRState* BindStruct(const GRState* St, const TypedRegion* R, SVal V);
Zhongxing Xu63123d82008-11-23 04:30:35 +0000285
Zhongxing Xu5834ed62009-01-13 01:49:57 +0000286 /// KillStruct - Set the entire struct to unknown.
287 const GRState* KillStruct(const GRState* St, const TypedRegion* R);
288
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000289 // Utility methods.
290 BasicValueFactory& getBasicVals() { return StateMgr.getBasicVals(); }
291 ASTContext& getContext() { return StateMgr.getContext(); }
Zhongxing Xu63123d82008-11-23 04:30:35 +0000292 SymbolManager& getSymbolManager() { return StateMgr.getSymbolManager(); }
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000293
294 const GRState* AddRegionView(const GRState* St,
295 const MemRegion* View, const MemRegion* Base);
Zhongxing Xu5834ed62009-01-13 01:49:57 +0000296 const GRState* RemoveRegionView(const GRState* St,
297 const MemRegion* View, const MemRegion* Base);
Zhongxing Xu17892752008-10-08 02:50:44 +0000298};
299
300} // end anonymous namespace
301
Ted Kremenek95c7b002008-10-24 01:04:59 +0000302StoreManager* clang::CreateRegionStoreManager(GRStateManager& StMgr) {
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000303 return new RegionStoreManager(StMgr);
Ted Kremenek95c7b002008-10-24 01:04:59 +0000304}
305
Ted Kremenek59e8f112009-03-03 01:35:36 +0000306std::auto_ptr<SubRegionMap>
307RegionStoreManager::getSubRegionMap(const GRState *state) {
308 RegionBindingsTy B = GetRegionBindings(state->getStore());
309 RegionStoreSubRegionMap *M = new RegionStoreSubRegionMap();
310
311 for (RegionBindingsTy::iterator I=B.begin(), E=B.end(); I!=E; ++I) {
312 if (const SubRegion* R = dyn_cast<SubRegion>(I.getKey()))
313 M->add(R->getSuperRegion(), R);
314 }
315
316 return std::auto_ptr<SubRegionMap>(M);
317}
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000318
319/// getLValueString - Returns an SVal representing the lvalue of a
320/// StringLiteral. Within RegionStore a StringLiteral has an
321/// associated StringRegion, and the lvalue of a StringLiteral is the
322/// lvalue of that region.
Zhongxing Xu143bf822008-10-25 14:18:57 +0000323SVal RegionStoreManager::getLValueString(const GRState* St,
324 const StringLiteral* S) {
325 return loc::MemRegionVal(MRMgr.getStringRegion(S));
326}
327
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000328/// getLValueVar - Returns an SVal that represents the lvalue of a
329/// variable. Within RegionStore a variable has an associated
330/// VarRegion, and the lvalue of the variable is the lvalue of that region.
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000331SVal RegionStoreManager::getLValueVar(const GRState* St, const VarDecl* VD) {
332 return loc::MemRegionVal(MRMgr.getVarRegion(VD));
333}
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000334
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000335/// getLValueCompoundLiteral - Returns an SVal representing the lvalue
336/// of a compound literal. Within RegionStore a compound literal
337/// has an associated region, and the lvalue of the compound literal
338/// is the lvalue of that region.
339SVal
340RegionStoreManager::getLValueCompoundLiteral(const GRState* St,
341 const CompoundLiteralExpr* CL) {
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000342 return loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL));
343}
344
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000345SVal RegionStoreManager::getLValueIvar(const GRState* St, const ObjCIvarDecl* D,
346 SVal Base) {
347 return UnknownVal();
348}
349
350SVal RegionStoreManager::getLValueField(const GRState* St, SVal Base,
351 const FieldDecl* D) {
352 if (Base.isUnknownOrUndef())
353 return Base;
354
355 Loc BaseL = cast<Loc>(Base);
356 const MemRegion* BaseR = 0;
357
358 switch (BaseL.getSubKind()) {
359 case loc::MemRegionKind:
360 BaseR = cast<loc::MemRegionVal>(BaseL).getRegion();
361 break;
362
363 case loc::SymbolValKind:
Zhongxing Xu026c6632009-02-05 06:57:29 +0000364 BaseR = MRMgr.getSymbolicRegion(cast<loc::SymbolVal>(&BaseL)->getSymbol(),
365 StateMgr.getSymbolManager());
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000366 break;
367
368 case loc::GotoLabelKind:
369 case loc::FuncValKind:
370 // These are anormal cases. Flag an undefined value.
371 return UndefinedVal();
372
373 case loc::ConcreteIntKind:
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000374 // While these seem funny, this can happen through casts.
375 // FIXME: What we should return is the field offset. For example,
376 // add the field offset to the integer value. That way funny things
377 // like this work properly: &(((struct foo *) 0xa)->f)
378 return Base;
379
380 default:
Zhongxing Xu13d1ee22008-11-07 08:57:30 +0000381 assert(0 && "Unhandled Base.");
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000382 return Base;
383 }
384
385 return loc::MemRegionVal(MRMgr.getFieldRegion(D, BaseR));
386}
387
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000388SVal RegionStoreManager::getLValueElement(const GRState* St,
389 SVal Base, SVal Offset) {
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000390
Zhongxing Xua48f7372009-02-06 08:44:27 +0000391 if (Base.isUnknownOrUndef())
Zhongxing Xu4a1513e2008-10-27 12:23:17 +0000392 return Base;
393
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000394 // Only handle integer offsets... for now.
395 if (!isa<nonloc::ConcreteInt>(Offset))
Zhongxing Xue4d13932008-11-13 09:48:44 +0000396 return UnknownVal();
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000397
Zhongxing Xua48f7372009-02-06 08:44:27 +0000398 const TypedRegion* BaseRegion = 0;
399
400 if (isa<loc::SymbolVal>(Base))
401 BaseRegion = MRMgr.getSymbolicRegion(cast<loc::SymbolVal>(Base).getSymbol(),
402 StateMgr.getSymbolManager());
403 else
404 BaseRegion = cast<TypedRegion>(cast<loc::MemRegionVal>(Base).getRegion());
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000405
406 // Pointer of any type can be cast and used as array base.
407 const ElementRegion *ElemR = dyn_cast<ElementRegion>(BaseRegion);
408
409 if (!ElemR) {
410 //
411 // If the base region is not an ElementRegion, create one.
412 // This can happen in the following example:
413 //
414 // char *p = __builtin_alloc(10);
415 // p[1] = 8;
416 //
Ted Kremenek0312c0e2009-03-01 05:44:08 +0000417 // Observe that 'p' binds to an TypedViewRegion<AllocaRegion>.
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000418 //
Zhongxing Xu5ea2ffc2009-02-19 08:37:16 +0000419
420 // Offset might be unsigned. We have to convert it to signed ConcreteInt.
421 if (nonloc::ConcreteInt* CI = dyn_cast<nonloc::ConcreteInt>(&Offset)) {
422 const llvm::APSInt& OffI = CI->getValue();
423 if (OffI.isUnsigned()) {
424 llvm::APSInt Tmp = OffI;
425 Tmp.setIsSigned(true);
426 Offset = NonLoc::MakeVal(getBasicVals(), Tmp);
427 }
428 }
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000429 return loc::MemRegionVal(MRMgr.getElementRegion(Offset, BaseRegion));
Zhongxing Xue4d13932008-11-13 09:48:44 +0000430 }
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000431
432 SVal BaseIdx = ElemR->getIndex();
433
434 if (!isa<nonloc::ConcreteInt>(BaseIdx))
435 return UnknownVal();
436
437 const llvm::APSInt& BaseIdxI = cast<nonloc::ConcreteInt>(BaseIdx).getValue();
438 const llvm::APSInt& OffI = cast<nonloc::ConcreteInt>(Offset).getValue();
439 assert(BaseIdxI.isSigned());
440
441 // FIXME: This appears to be the assumption of this code. We should review
442 // whether or not BaseIdxI.getBitWidth() < OffI.getBitWidth(). If it
443 // can't we need to put a comment here. If it can, we should handle it.
444 assert(BaseIdxI.getBitWidth() >= OffI.getBitWidth());
Zhongxing Xue4d13932008-11-13 09:48:44 +0000445
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000446 const TypedRegion *ArrayR = ElemR->getArrayRegion();
447 SVal NewIdx;
448
449 if (OffI.isUnsigned() || OffI.getBitWidth() < BaseIdxI.getBitWidth()) {
450 // 'Offset' might be unsigned. We have to convert it to signed and
451 // possibly extend it.
452 llvm::APSInt Tmp = OffI;
453
454 if (OffI.getBitWidth() < BaseIdxI.getBitWidth())
455 Tmp.extend(BaseIdxI.getBitWidth());
456
457 Tmp.setIsSigned(true);
458 Tmp += BaseIdxI; // Compute the new offset.
Zhongxing Xu5ea2ffc2009-02-19 08:37:16 +0000459 NewIdx = NonLoc::MakeVal(getBasicVals(), Tmp);
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000460 }
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000461 else
462 NewIdx = nonloc::ConcreteInt(getBasicVals().getValue(BaseIdxI + OffI));
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000463
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000464 return loc::MemRegionVal(MRMgr.getElementRegion(NewIdx, ArrayR));
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000465}
466
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000467SVal RegionStoreManager::getSizeInElements(const GRState* St,
468 const MemRegion* R) {
469 if (const VarRegion* VR = dyn_cast<VarRegion>(R)) {
470 // Get the type of the variable.
Ted Kremenek14553ab2009-01-30 00:08:43 +0000471 QualType T = VR->getDesugaredRValueType(getContext());
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000472
Ted Kremenek14553ab2009-01-30 00:08:43 +0000473 // FIXME: Handle variable-length arrays.
474 if (isa<VariableArrayType>(T))
475 return UnknownVal();
476
477 if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(T)) {
478 // return the size as signed integer.
479 return NonLoc::MakeVal(getBasicVals(), CAT->getSize(), false);
480 }
481
482 // Clients can use ordinary variables as if they were arrays. These
483 // essentially are arrays of size 1.
484 return NonLoc::MakeIntVal(getBasicVals(), 1, false);
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000485 }
486
487 if (const StringRegion* SR = dyn_cast<StringRegion>(R)) {
Zhongxing Xu6613d082008-11-24 02:18:56 +0000488 const StringLiteral* Str = SR->getStringLiteral();
Zhongxing Xud0fd3b72008-11-24 02:30:48 +0000489 // We intentionally made the size value signed because it participates in
490 // operations with signed indices.
Ted Kremenek14553ab2009-01-30 00:08:43 +0000491 return NonLoc::MakeIntVal(getBasicVals(), Str->getByteLength()+1, false);
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000492 }
493
Ted Kremenek0312c0e2009-03-01 05:44:08 +0000494 if (const TypedViewRegion* ATR = dyn_cast<TypedViewRegion>(R)) {
Ted Kremenek2e842572009-01-22 23:56:56 +0000495#if 0
496 // FIXME: This logic doesn't really work, as we can have all sorts of
497 // weird cases. For example, this crashes on test case 'rdar-6442306-1.m'.
498 // The weird cases come in when arbitrary casting comes into play, violating
499 // any type-safe programming.
500
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000501 GRStateRef state(St, StateMgr);
502
503 // Get the size of the super region in bytes.
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000504 const SVal* Extent = state.get<RegionExtents>(ATR->getSuperRegion());
505 assert(Extent && "region extent not exist");
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000506
507 // Assume it's ConcreteInt for now.
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000508 llvm::APSInt SSize = cast<nonloc::ConcreteInt>(*Extent).getValue();
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000509
510 // Get the size of the element in bits.
Ted Kremenek6eddeb12008-12-13 21:49:13 +0000511 QualType LvT = ATR->getLValueType(getContext());
512 QualType ElemTy = cast<PointerType>(LvT.getTypePtr())->getPointeeType();
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000513
514 uint64_t X = getContext().getTypeSize(ElemTy);
515
516 const llvm::APSInt& ESize = getBasicVals().getValue(X, SSize.getBitWidth(),
517 false);
518
519 // Calculate the number of elements.
520
521 // FIXME: What do we do with signed-ness problem? Shall we make all APSInts
522 // signed?
523 if (SSize.isUnsigned())
524 SSize.setIsSigned(true);
525
526 // FIXME: move this operation into BasicVals.
527 const llvm::APSInt S =
528 (SSize * getBasicVals().getValue(8, SSize.getBitWidth(), false)) / ESize;
529
530 return NonLoc::MakeVal(getBasicVals(), S);
Ted Kremenek2e842572009-01-22 23:56:56 +0000531#else
532 ATR = ATR;
533 return UnknownVal();
534#endif
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000535 }
536
537 if (const FieldRegion* FR = dyn_cast<FieldRegion>(R)) {
538 // FIXME: Unsupported yet.
539 FR = 0;
540 return UnknownVal();
541 }
Zhongxing Xu369f4292008-11-22 13:23:00 +0000542
Zhongxing Xu02ebefb2009-02-06 08:51:30 +0000543 if (isa<SymbolicRegion>(R)) {
Zhongxing Xua48f7372009-02-06 08:44:27 +0000544 return UnknownVal();
545 }
546
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000547 assert(0 && "Other regions are not supported yet.");
Ted Kremeneka21362d2009-01-06 19:12:06 +0000548 return UnknownVal();
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000549}
550
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000551/// ArrayToPointer - Emulates the "decay" of an array to a pointer
552/// type. 'Array' represents the lvalue of the array being decayed
553/// to a pointer, and the returned SVal represents the decayed
554/// version of that lvalue (i.e., a pointer to the first element of
555/// the array). This is called by GRExprEngine when evaluating casts
556/// from arrays to pointers.
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000557SVal RegionStoreManager::ArrayToPointer(SVal Array) {
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000558 // FIXME: This should be factored into GRExprEngine. This allows
559 // us to pass a "loc" instead of an "SVal" for "Array".
Ted Kremenekabb042f2008-12-13 19:24:37 +0000560 if (Array.isUnknownOrUndef())
561 return Array;
562
563 if (!isa<loc::MemRegionVal>(Array))
564 return UnknownVal();
565
566 const MemRegion* R = cast<loc::MemRegionVal>(&Array)->getRegion();
567 const TypedRegion* ArrayR = dyn_cast<TypedRegion>(R);
568
Ted Kremenekbbee1a72009-01-13 01:03:27 +0000569 if (!ArrayR)
Ted Kremenekabb042f2008-12-13 19:24:37 +0000570 return UnknownVal();
571
Zhongxing Xu63123d82008-11-23 04:30:35 +0000572 nonloc::ConcreteInt Idx(getBasicVals().getZeroWithPtrWidth(false));
Zhongxing Xu0b7e6422008-10-26 02:23:57 +0000573 ElementRegion* ER = MRMgr.getElementRegion(Idx, ArrayR);
574
575 return loc::MemRegionVal(ER);
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000576}
577
Ted Kremenek6eddeb12008-12-13 21:49:13 +0000578StoreManager::CastResult
579RegionStoreManager::CastRegion(const GRState* state, const MemRegion* R,
580 QualType CastToTy) {
581
582 // Return the same region if the region types are compatible.
583 if (const TypedRegion* TR = dyn_cast<TypedRegion>(R)) {
584 ASTContext& Ctx = StateMgr.getContext();
585 QualType Ta = Ctx.getCanonicalType(TR->getLValueType(Ctx));
586 QualType Tb = Ctx.getCanonicalType(CastToTy);
587
588 if (Ta == Tb)
589 return CastResult(state, R);
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000590 }
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000591
592 // FIXME: We should handle the case when we are casting *back* to a
593 // previous type. For example:
594 //
595 // void* x = ...;
596 // char* y = (char*) x;
597 // void* z = (void*) y; // <-- we should get the same region that is
598 // bound to 'x'
Ted Kremenek0312c0e2009-03-01 05:44:08 +0000599 const MemRegion* ViewR = MRMgr.getTypedViewRegion(CastToTy, R);
Ted Kremenek6eddeb12008-12-13 21:49:13 +0000600 return CastResult(AddRegionView(state, ViewR, R), ViewR);
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000601}
602
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000603SVal RegionStoreManager::EvalBinOp(BinaryOperator::Opcode Op, Loc L, NonLoc R) {
604 // Assume the base location is MemRegionVal(ElementRegion).
Ted Kremenek5dc27462009-03-03 02:51:43 +0000605 if (!isa<loc::MemRegionVal>(L))
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000606 return UnknownVal();
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000607
608 const MemRegion* MR = cast<loc::MemRegionVal>(L).getRegion();
609
610 const ElementRegion* ER = cast<ElementRegion>(MR);
611 SVal Idx = ER->getIndex();
612
613 nonloc::ConcreteInt* Base = dyn_cast<nonloc::ConcreteInt>(&Idx);
614 nonloc::ConcreteInt* Offset = dyn_cast<nonloc::ConcreteInt>(&R);
615
616 // Only support concrete integer indexes for now.
617 if (Base && Offset) {
618 SVal NewIdx = Base->EvalBinOp(getBasicVals(), Op, *Offset);
619
620 const MemRegion* NewER = MRMgr.getElementRegion(NewIdx,
621 ER->getArrayRegion());
622 return Loc::MakeVal(NewER);
623
Ted Kremenek5dc27462009-03-03 02:51:43 +0000624 }
625
626 return UnknownVal();
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000627}
628
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000629SVal RegionStoreManager::Retrieve(const GRState* St, Loc L, QualType T) {
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000630 assert(!isa<UnknownVal>(L) && "location unknown");
631 assert(!isa<UndefinedVal>(L) && "location undefined");
632
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000633 // FIXME: What does loc::SymbolVal represent? It represents the value
634 // of a location but that value is not known. In the future we should
635 // handle potential aliasing relationships; e.g. a loc::SymbolVal could
636 // be an alias for a particular region.
Zhongxing Xu779747c2009-02-20 05:19:30 +0000637 // Example:
638 // void foo(char* buf) {
639 // char c = *buf;
640 // }
641 if (isa<loc::SymbolVal>(L)) {
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000642 return UnknownVal();
Zhongxing Xu779747c2009-02-20 05:19:30 +0000643 }
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000644
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000645 // FIXME: Is this even possible? Shouldn't this be treated as a null
646 // dereference at a higher level?
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000647 if (isa<loc::ConcreteInt>(L))
648 return UndefinedVal();
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000649
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000650 // FIXME: Should this be refactored into GRExprEngine or GRStateManager?
651 // It seems that all StoreManagers would do the same thing here.
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000652 if (isa<loc::FuncVal>(L))
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000653 return L;
654
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000655 // FIXME: Perhaps this method should just take a 'const MemRegion*' argument
656 // instead of 'Loc', and have the other Loc cases handled at a higher level.
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000657 const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion();
658 assert(R && "bad region");
659
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000660 // FIXME: We should eventually handle funny addressing. e.g.:
661 //
662 // int x = ...;
663 // int *p = &x;
664 // char *q = (char*) p;
665 // char c = *q; // returns the first byte of 'x'.
666 //
667 // Such funny addressing will occur due to layering of regions.
668
Ted Kremenek265a3052009-02-24 02:23:11 +0000669 if (const TypedRegion* TR = dyn_cast<TypedRegion>(R)) {
670 QualType T =TR->getRValueType(getContext());
671 if (T->isStructureType())
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000672 return RetrieveStruct(St, TR);
Ted Kremenek265a3052009-02-24 02:23:11 +0000673 // FIXME: handle Vector types.
674 if (T->isVectorType())
675 return UnknownVal();
676 }
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000677
678 RegionBindingsTy B = GetRegionBindings(St->getStore());
679 RegionBindingsTy::data_type* V = B.lookup(R);
680
681 // Check if the region has a binding.
682 if (V)
683 return *V;
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000684
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000685 GRStateRef state(St, StateMgr);
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000686
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000687 // Check if the region is in killset.
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000688 if (state.contains<RegionKills>(R))
689 return UnknownVal();
690
Zhongxing Xu562c4d92009-01-23 11:22:12 +0000691 // If the region is an element of field, it may have a default value.
692 if (isa<ElementRegion>(R) || isa<FieldRegion>(R)) {
693 const MemRegion* SuperR = cast<SubRegion>(R)->getSuperRegion();
694 GRStateTrait<RegionDefaultValue>::lookup_type D =
695 state.get<RegionDefaultValue>(SuperR);
696 if (D)
697 return *D;
698 }
699
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000700 // The location does not have a bound value. This means that it has
701 // the value it had upon its creation and/or entry to the analyzed
702 // function/method. These are either symbolic values or 'undefined'.
703
704 // We treat function parameters as symbolic values.
Ted Kremenek6fd8f912009-01-22 23:43:57 +0000705 if (const VarRegion* VR = dyn_cast<VarRegion>(R)) {
706 const VarDecl *VD = VR->getDecl();
707
Zhongxing Xud8895f62009-02-19 09:56:08 +0000708 if (isa<ParmVarDecl>(VD) || VD->hasGlobalStorage()) {
709 QualType VTy = VD->getType();
710 if (Loc::IsLocType(VTy) || VTy->isIntegerType())
711 return SVal::GetRValueSymbolVal(getSymbolManager(), VR);
712 else
713 return UnknownVal();
714 }
Ted Kremenek6fd8f912009-01-22 23:43:57 +0000715 else if (VD == SelfDecl)
716 return loc::MemRegionVal(getSelfRegion(0));
717 }
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000718
Ted Kremenek265a3052009-02-24 02:23:11 +0000719
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000720 if (MRMgr.onStack(R) || MRMgr.onHeap(R)) {
721 // All stack variables are considered to have undefined values
722 // upon creation. All heap allocated blocks are considered to
723 // have undefined values as well unless they are explicitly bound
724 // to specific values.
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000725 return UndefinedVal();
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000726 }
727
728 // All other values are symbolic.
Ted Kremenek9ab6b9c2009-01-22 18:23:34 +0000729 return SVal::GetRValueSymbolVal(getSymbolManager(), R);
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000730}
731
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000732SVal RegionStoreManager::RetrieveStruct(const GRState* St,const TypedRegion* R){
733
734 Store store = St->getStore();
735 GRStateRef state(St, StateMgr);
736
Ted Kremenek6eddeb12008-12-13 21:49:13 +0000737 // FIXME: Verify we want getRValueType instead of getLValueType.
738 QualType T = R->getRValueType(getContext());
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000739 assert(T->isStructureType());
740
741 const RecordType* RT = cast<RecordType>(T.getTypePtr());
742 RecordDecl* RD = RT->getDecl();
743 assert(RD->isDefinition());
744
745 llvm::ImmutableList<SVal> StructVal = getBasicVals().getEmptySValList();
746
Douglas Gregore267ff32008-12-11 20:41:00 +0000747 std::vector<FieldDecl *> Fields(RD->field_begin(), RD->field_end());
Douglas Gregor44b43212008-12-11 16:49:14 +0000748
Douglas Gregore267ff32008-12-11 20:41:00 +0000749 for (std::vector<FieldDecl *>::reverse_iterator Field = Fields.rbegin(),
750 FieldEnd = Fields.rend();
751 Field != FieldEnd; ++Field) {
752 FieldRegion* FR = MRMgr.getFieldRegion(*Field, R);
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000753 RegionBindingsTy B = GetRegionBindings(store);
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +0000754 RegionBindingsTy::data_type* data = B.lookup(FR);
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000755
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000756 SVal FieldValue;
757 if (data)
758 FieldValue = *data;
759 else if (state.contains<RegionKills>(FR))
760 FieldValue = UnknownVal();
761 else {
762 if (MRMgr.onStack(FR) || MRMgr.onHeap(FR))
763 FieldValue = UndefinedVal();
764 else
Ted Kremenek9ab6b9c2009-01-22 18:23:34 +0000765 FieldValue = SVal::GetRValueSymbolVal(getSymbolManager(), FR);
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000766 }
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000767
768 StructVal = getBasicVals().consVals(FieldValue, StructVal);
769 }
770
771 return NonLoc::MakeCompoundVal(T, StructVal, getBasicVals());
772}
773
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000774const GRState* RegionStoreManager::Bind(const GRState* St, Loc L, SVal V) {
775 // Currently we don't bind value to symbolic location. But if the logic is
776 // made clear, we might change this decision.
777 if (isa<loc::SymbolVal>(L))
778 return St;
Zhongxing Xu8fe63af2008-10-27 09:24:07 +0000779
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000780 // If we get here, the location should be a region.
781 const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion();
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +0000782 assert(R);
783
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000784 // Check if the region is a struct region.
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +0000785 if (const TypedRegion* TR = dyn_cast<TypedRegion>(R))
Ted Kremenek6eddeb12008-12-13 21:49:13 +0000786 // FIXME: Verify we want getRValueType().
787 if (TR->getRValueType(getContext())->isStructureType())
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000788 return BindStruct(St, TR, V);
Zhongxing Xu17892752008-10-08 02:50:44 +0000789
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000790 Store store = St->getStore();
Zhongxing Xu17892752008-10-08 02:50:44 +0000791 RegionBindingsTy B = GetRegionBindings(store);
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000792
793 if (V.isUnknown()) {
794 // Remove the binding.
795 store = RBFactory.Remove(B, R).getRoot();
796
797 // Add the region to the killset.
798 GRStateRef state(St, StateMgr);
799 St = state.add<RegionKills>(R);
800 }
801 else
802 store = RBFactory.Add(B, R, V).getRoot();
803
804 return StateMgr.MakeStateWithStore(St, store);
Zhongxing Xu17892752008-10-08 02:50:44 +0000805}
806
Zhongxing Xu9c9ca082008-12-16 02:36:30 +0000807Store RegionStoreManager::Remove(Store store, Loc L) {
Ted Kremenek0964a062009-01-21 06:57:53 +0000808 const MemRegion* R = 0;
809
810 if (isa<loc::MemRegionVal>(L))
811 R = cast<loc::MemRegionVal>(L).getRegion();
812 else if (isa<loc::SymbolVal>(L))
Zhongxing Xu026c6632009-02-05 06:57:29 +0000813 R = MRMgr.getSymbolicRegion(cast<loc::SymbolVal>(L).getSymbol(),
814 StateMgr.getSymbolManager());
Ted Kremenek0964a062009-01-21 06:57:53 +0000815
816 if (R) {
817 RegionBindingsTy B = GetRegionBindings(store);
818 return RBFactory.Remove(B, R).getRoot();
819 }
820
821 return store;
Zhongxing Xu9c9ca082008-12-16 02:36:30 +0000822}
823
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000824const GRState* RegionStoreManager::BindDecl(const GRState* St,
825 const VarDecl* VD, SVal InitVal) {
Zhongxing Xua4f28ff2008-11-13 08:41:36 +0000826
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000827 QualType T = VD->getType();
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000828 VarRegion* VR = MRMgr.getVarRegion(VD);
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +0000829
Ted Kremenek0964a062009-01-21 06:57:53 +0000830 if (T->isArrayType())
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000831 return BindArray(St, VR, InitVal);
Ted Kremenek0964a062009-01-21 06:57:53 +0000832 if (T->isStructureType())
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000833 return BindStruct(St, VR, InitVal);
Zhongxing Xud463d442008-11-02 12:13:30 +0000834
Ted Kremenek0964a062009-01-21 06:57:53 +0000835 return Bind(St, Loc::MakeVal(VR), InitVal);
Zhongxing Xu17892752008-10-08 02:50:44 +0000836}
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000837
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000838// FIXME: this method should be merged into Bind().
839const GRState*
840RegionStoreManager::BindCompoundLiteral(const GRState* St,
841 const CompoundLiteralExpr* CL, SVal V) {
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000842 CompoundLiteralRegion* R = MRMgr.getCompoundLiteralRegion(CL);
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000843 return Bind(St, loc::MemRegionVal(R), V);
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000844}
845
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000846const GRState* RegionStoreManager::setExtent(const GRState* St,
847 const MemRegion* R, SVal Extent) {
848 GRStateRef state(St, StateMgr);
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000849 return state.set<RegionExtents>(R, Extent);
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000850}
851
852
Ted Kremenek241677a2009-01-21 22:26:05 +0000853static void UpdateLiveSymbols(SVal X, SymbolReaper& SymReaper) {
854 for (SVal::symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end();SI!=SE;++SI)
855 SymReaper.markLive(*SI);
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000856}
857
Ted Kremenek2ed14be2008-12-05 00:47:52 +0000858Store RegionStoreManager::RemoveDeadBindings(const GRState* state, Stmt* Loc,
Ted Kremenek241677a2009-01-21 22:26:05 +0000859 SymbolReaper& SymReaper,
860 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots)
861{
Zhongxing Xu8916d5b2008-11-10 09:39:04 +0000862
Ted Kremenek2ed14be2008-12-05 00:47:52 +0000863 Store store = state->getStore();
Zhongxing Xu8916d5b2008-11-10 09:39:04 +0000864 RegionBindingsTy B = GetRegionBindings(store);
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000865
866 // Lazily constructed backmap from MemRegions to SubRegions.
867 typedef llvm::ImmutableSet<const MemRegion*> SubRegionsTy;
868 typedef llvm::ImmutableMap<const MemRegion*, SubRegionsTy> SubRegionsMapTy;
869
870 // FIXME: As a future optimization we can modifiy BumpPtrAllocator to have
871 // the ability to reuse memory. This way we can keep TmpAlloc around as
872 // an instance variable of RegionStoreManager (avoiding repeated malloc
873 // overhead).
874 llvm::BumpPtrAllocator TmpAlloc;
875
876 // Factory objects.
877 SubRegionsMapTy::Factory SubRegMapF(TmpAlloc);
878 SubRegionsTy::Factory SubRegF(TmpAlloc);
879
880 // The backmap from regions to subregions.
881 SubRegionsMapTy SubRegMap = SubRegMapF.GetEmptyMap();
882
883 // Do a pass over the regions in the store. For VarRegions we check if
884 // the variable is still live and if so add it to the list of live roots.
885 // For other regions we populate our region backmap.
Zhongxing Xu8916d5b2008-11-10 09:39:04 +0000886 for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000887 const MemRegion* R = I.getKey();
888 if (const VarRegion* VR = dyn_cast<VarRegion>(R)) {
Ted Kremenek241677a2009-01-21 22:26:05 +0000889 if (SymReaper.isLive(Loc, VR->getDecl()))
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000890 RegionRoots.push_back(VR); // This is a live "root".
891 }
892 else {
893 // Get the super region for R.
894 const MemRegion* SuperR = cast<SubRegion>(R)->getSuperRegion();
895 // Get the current set of subregions for SuperR.
896 const SubRegionsTy* SRptr = SubRegMap.lookup(SuperR);
897 SubRegionsTy SR = SRptr ? *SRptr : SubRegF.GetEmptySet();
898 // Add R to the subregions of SuperR.
899 SubRegMap = SubRegMapF.Add(SubRegMap, SuperR, SubRegF.Add(SR, R));
900
901 // Finally, check if SuperR is a VarRegion. We need to do this
902 // to also mark SuperR as a root (as it may not have a value directly
903 // bound to it in the store).
904 if (const VarRegion* VR = dyn_cast<VarRegion>(SuperR)) {
Ted Kremenek241677a2009-01-21 22:26:05 +0000905 if (SymReaper.isLive(Loc, VR->getDecl()))
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000906 RegionRoots.push_back(VR); // This is a live "root".
907 }
908 }
Zhongxing Xu8916d5b2008-11-10 09:39:04 +0000909 }
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000910
911 // Process the worklist of RegionRoots. This performs a "mark-and-sweep"
912 // of the store. We want to find all live symbols and dead regions.
913 llvm::SmallPtrSet<const MemRegion*, 10> Marked;
914
915 while (!RegionRoots.empty()) {
916 // Dequeue the next region on the worklist.
917 const MemRegion* R = RegionRoots.back();
918 RegionRoots.pop_back();
Zhongxing Xu8916d5b2008-11-10 09:39:04 +0000919
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000920 // Check if we have already processed this region.
921 if (Marked.count(R)) continue;
922
923 // Mark this region as processed. This is needed for termination in case
924 // a region is referenced more than once.
925 Marked.insert(R);
926
927 // Mark the symbol for any live SymbolicRegion as "live". This means we
928 // should continue to track that symbol.
929 if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(R))
Ted Kremenek241677a2009-01-21 22:26:05 +0000930 SymReaper.markLive(SymR->getSymbol());
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000931
932 // Get the data binding for R (if any).
933 RegionBindingsTy::data_type* Xptr = B.lookup(R);
934 if (Xptr) {
935 SVal X = *Xptr;
Ted Kremenek241677a2009-01-21 22:26:05 +0000936 UpdateLiveSymbols(X, SymReaper); // Update the set of live symbols.
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000937
938 // If X is a region, then add it the RegionRoots.
939 if (loc::MemRegionVal* RegionX = dyn_cast<loc::MemRegionVal>(&X))
940 RegionRoots.push_back(RegionX->getRegion());
941 }
942
943 // Get the subregions of R. These are RegionRoots as well since they
944 // represent values that are also bound to R.
945 const SubRegionsTy* SRptr = SubRegMap.lookup(R);
946 if (!SRptr) continue;
947 SubRegionsTy SR = *SRptr;
948
949 for (SubRegionsTy::iterator I=SR.begin(), E=SR.end(); I!=E; ++I)
950 RegionRoots.push_back(*I);
951 }
952
953 // We have now scanned the store, marking reachable regions and symbols
954 // as live. We now remove all the regions that are dead from the store
955 // as well as update DSymbols with the set symbols that are now dead.
956
957 for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
958 const MemRegion* R = I.getKey();
959
960 // If this region live? Is so, none of its symbols are dead.
961 if (Marked.count(R))
962 continue;
963
964 // Remove this dead region from the store.
Zhongxing Xu9c9ca082008-12-16 02:36:30 +0000965 store = Remove(store, Loc::MakeVal(R));
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000966
967 // Mark all non-live symbols that this region references as dead.
Ted Kremenek241677a2009-01-21 22:26:05 +0000968 if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(R))
969 SymReaper.maybeDead(SymR->getSymbol());
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000970
971 SVal X = I.getData();
972 SVal::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
Ted Kremenek241677a2009-01-21 22:26:05 +0000973 for (; SI != SE; ++SI) SymReaper.maybeDead(*SI);
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000974 }
975
Zhongxing Xu8916d5b2008-11-10 09:39:04 +0000976 return store;
977}
978
Zhongxing Xua071eb02008-10-24 06:01:33 +0000979void RegionStoreManager::print(Store store, std::ostream& Out,
980 const char* nl, const char *sep) {
981 llvm::raw_os_ostream OS(Out);
982 RegionBindingsTy B = GetRegionBindings(store);
983 OS << "Store:" << nl;
984
985 for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
986 OS << ' '; I.getKey()->print(OS); OS << " : ";
987 I.getData().print(OS); OS << nl;
988 }
Zhongxing Xu5b8b6f22008-10-24 04:33:15 +0000989}
Zhongxing Xua82512a2008-10-24 08:42:28 +0000990
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000991const GRState* RegionStoreManager::BindArray(const GRState* St,
992 const TypedRegion* R, SVal Init) {
Ted Kremenek6eddeb12008-12-13 21:49:13 +0000993
994 // FIXME: Verify we should use getLValueType or getRValueType.
Zhongxing Xu2ef93722008-12-14 03:14:52 +0000995 QualType T = R->getRValueType(getContext());
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +0000996 assert(T->isArrayType());
997
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000998 // When we are binding the whole array, it always has default value 0.
999 GRStateRef state(St, StateMgr);
Ted Kremenek14553ab2009-01-30 00:08:43 +00001000 St = state.set<RegionDefaultValue>(R, NonLoc::MakeIntVal(getBasicVals(), 0,
1001 false));
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001002
1003 Store store = St->getStore();
1004
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001005 ConstantArrayType* CAT = cast<ConstantArrayType>(T.getTypePtr());
1006
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001007 llvm::APSInt Size(CAT->getSize(), false);
Sebastian Redl1be3da52009-01-26 19:54:12 +00001008 llvm::APSInt i = getBasicVals().getValue(0, Size.getBitWidth(),
1009 Size.isUnsigned());
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001010
1011 // Check if the init expr is a StringLiteral.
1012 if (isa<loc::MemRegionVal>(Init)) {
1013 const MemRegion* InitR = cast<loc::MemRegionVal>(Init).getRegion();
1014 const StringLiteral* S = cast<StringRegion>(InitR)->getStringLiteral();
1015 const char* str = S->getStrData();
1016 unsigned len = S->getByteLength();
1017 unsigned j = 0;
1018
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001019 // Copy bytes from the string literal into the target array. Trailing bytes
1020 // in the array that are not covered by the string literal are initialized
1021 // to zero.
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001022 for (; i < Size; ++i, ++j) {
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001023 if (j >= len)
1024 break;
1025
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001026 SVal Idx = NonLoc::MakeVal(getBasicVals(), i);
1027 ElementRegion* ER = MRMgr.getElementRegion(Idx, R);
1028
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001029 SVal V = NonLoc::MakeVal(getBasicVals(), str[j], sizeof(char)*8, true);
1030 St = Bind(St, loc::MemRegionVal(ER), V);
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001031 }
1032
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001033 return StateMgr.MakeStateWithStore(St, store);
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001034 }
1035
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001036
1037 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(Init);
1038
1039 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
1040
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001041 for (; i < Size; ++i, ++VI) {
1042 // The init list might be shorter than the array decl.
1043 if (VI == VE)
1044 break;
1045
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001046 SVal Idx = NonLoc::MakeVal(getBasicVals(), i);
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001047 ElementRegion* ER = MRMgr.getElementRegion(Idx, R);
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001048
1049 if (CAT->getElementType()->isStructureType())
1050 St = BindStruct(St, ER, *VI);
1051 else
1052 St = Bind(St, Loc::MakeVal(ER), *VI);
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001053 }
1054
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001055 return StateMgr.MakeStateWithStore(St, store);
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001056}
1057
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001058const GRState*
1059RegionStoreManager::BindStruct(const GRState* St, const TypedRegion* R, SVal V){
Ted Kremenek6eddeb12008-12-13 21:49:13 +00001060 // FIXME: Verify that we should use getRValueType or getLValueType.
1061 QualType T = R->getRValueType(getContext());
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001062 assert(T->isStructureType());
1063
1064 RecordType* RT = cast<RecordType>(T.getTypePtr());
1065 RecordDecl* RD = RT->getDecl();
1066 assert(RD->isDefinition());
1067
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001068 if (V.isUnknown())
1069 return KillStruct(St, R);
1070
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001071 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V);
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001072 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
1073 RecordDecl::field_iterator FI = RD->field_begin(), FE = RD->field_end();
1074
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001075 for (; FI != FE; ++FI, ++VI) {
1076
1077 // There may be fewer values than fields only when we are initializing a
1078 // struct decl. In this case, mark the region as having default value.
1079 if (VI == VE) {
Zhongxing Xu13020162008-12-24 07:29:24 +00001080 GRStateRef state(St, StateMgr);
Ted Kremenek14553ab2009-01-30 00:08:43 +00001081 const NonLoc& Idx = NonLoc::MakeIntVal(getBasicVals(), 0, false);
1082 St = state.set<RegionDefaultValue>(R, Idx);
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001083 break;
1084 }
1085
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001086 QualType FTy = (*FI)->getType();
1087 FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);
1088
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001089 if (Loc::IsLocType(FTy) || FTy->isIntegerType())
1090 St = Bind(St, Loc::MakeVal(FR), *VI);
Zhongxing Xua82512a2008-10-24 08:42:28 +00001091
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001092 else if (FTy->isArrayType())
1093 St = BindArray(St, FR, *VI);
Zhongxing Xua82512a2008-10-24 08:42:28 +00001094
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001095 else if (FTy->isStructureType())
1096 St = BindStruct(St, FR, *VI);
Zhongxing Xua82512a2008-10-24 08:42:28 +00001097 }
1098
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001099 return St;
Zhongxing Xuc3a05992008-11-19 11:06:24 +00001100}
1101
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001102const GRState* RegionStoreManager::KillStruct(const GRState* St,
1103 const TypedRegion* R){
1104 GRStateRef state(St, StateMgr);
1105
1106 // Kill the struct region because it is assigned "unknown".
1107 St = state.add<RegionKills>(R);
1108
1109 // Set the default value of the struct region to "unknown".
1110 St = state.set<RegionDefaultValue>(R, UnknownVal());
1111
1112 Store store = St->getStore();
1113 RegionBindingsTy B = GetRegionBindings(store);
1114
1115 // Remove all bindings for the subregions of the struct.
1116 for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
1117 const MemRegion* r = I.getKey();
1118 if (const SubRegion* sr = dyn_cast<SubRegion>(r))
1119 if (sr->isSubRegionOf(R))
1120 store = Remove(store, Loc::MakeVal(sr));
Zhongxing Xu9c2a3db2009-01-13 03:07:41 +00001121 // FIXME: Maybe we should also remove the bindings for the "views" of the
1122 // subregions.
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001123 }
1124
1125 return StateMgr.MakeStateWithStore(St, store);
1126}
1127
Zhongxing Xudc0a25d2008-11-16 04:07:26 +00001128const GRState* RegionStoreManager::AddRegionView(const GRState* St,
1129 const MemRegion* View,
1130 const MemRegion* Base) {
1131 GRStateRef state(St, StateMgr);
1132
1133 // First, retrieve the region view of the base region.
Ted Kremenek50dc1b32008-12-24 01:05:03 +00001134 const RegionViews* d = state.get<RegionViewMap>(Base);
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001135 RegionViews L = d ? *d : RVFactory.GetEmptySet();
Zhongxing Xudc0a25d2008-11-16 04:07:26 +00001136
1137 // Now add View to the region view.
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001138 L = RVFactory.Add(L, View);
Zhongxing Xudc0a25d2008-11-16 04:07:26 +00001139
1140 // Create a new state with the new region view.
Ted Kremenek50dc1b32008-12-24 01:05:03 +00001141 return state.set<RegionViewMap>(Base, L);
Zhongxing Xudc0a25d2008-11-16 04:07:26 +00001142}
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001143
1144const GRState* RegionStoreManager::RemoveRegionView(const GRState* St,
1145 const MemRegion* View,
1146 const MemRegion* Base) {
1147 GRStateRef state(St, StateMgr);
1148
1149 // Retrieve the region view of the base region.
1150 const RegionViews* d = state.get<RegionViewMap>(Base);
1151
1152 // If the base region has no view, return.
1153 if (!d)
1154 return St;
1155
1156 // Remove the view.
1157 RegionViews V = *d;
1158 V = RVFactory.Remove(V, View);
1159
1160 return state.set<RegionViewMap>(Base, V);
1161}