blob: af141892e0f816cd48dccb530c9f410e0dbd306b [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"
Zhongxing Xu41fd0182009-05-06 11:51:48 +000021#include "clang/Basic/TargetInfo.h"
Zhongxing Xu17892752008-10-08 02:50:44 +000022
23#include "llvm/ADT/ImmutableMap.h"
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000024#include "llvm/ADT/ImmutableList.h"
Zhongxing Xua071eb02008-10-24 06:01:33 +000025#include "llvm/Support/raw_ostream.h"
Zhongxing Xu17892752008-10-08 02:50:44 +000026#include "llvm/Support/Compiler.h"
27
28using namespace clang;
29
Zhongxing Xubaf03a72008-11-24 09:44:56 +000030// Actual Store type.
Zhongxing Xu1c96b242008-10-17 05:57:07 +000031typedef llvm::ImmutableMap<const MemRegion*, SVal> RegionBindingsTy;
Zhongxing Xubaf03a72008-11-24 09:44:56 +000032
Ted Kremenek50dc1b32008-12-24 01:05:03 +000033//===----------------------------------------------------------------------===//
Ted Kremenek9af46f52009-06-16 22:36:44 +000034// Fine-grained control of RegionStoreManager.
35//===----------------------------------------------------------------------===//
36
37namespace {
38struct VISIBILITY_HIDDEN minimal_features_tag {};
39struct VISIBILITY_HIDDEN maximal_features_tag {};
40
41class VISIBILITY_HIDDEN RegionStoreFeatures {
42 bool SupportsFields;
43 bool SupportsRemaining;
44
45public:
46 RegionStoreFeatures(minimal_features_tag) :
47 SupportsFields(false), SupportsRemaining(false) {}
48
49 RegionStoreFeatures(maximal_features_tag) :
50 SupportsFields(true), SupportsRemaining(false) {}
51
52 void enableFields(bool t) { SupportsFields = t; }
53
54 bool supportsFields() const { return SupportsFields; }
55 bool supportsRemaining() const { return SupportsRemaining; }
56};
57}
58
59//===----------------------------------------------------------------------===//
Ted Kremenek50dc1b32008-12-24 01:05:03 +000060// Region "Views"
61//===----------------------------------------------------------------------===//
62//
63// MemRegions can be layered on top of each other. This GDM entry tracks
64// what are the MemRegions that layer a given MemRegion.
65//
Zhongxing Xu5834ed62009-01-13 01:49:57 +000066typedef llvm::ImmutableSet<const MemRegion*> RegionViews;
Ted Kremenek50dc1b32008-12-24 01:05:03 +000067namespace { class VISIBILITY_HIDDEN RegionViewMap {}; }
68static int RegionViewMapIndex = 0;
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000069namespace clang {
Ted Kremenek50dc1b32008-12-24 01:05:03 +000070 template<> struct GRStateTrait<RegionViewMap>
71 : public GRStatePartialTrait<llvm::ImmutableMap<const MemRegion*,
72 RegionViews> > {
73
74 static void* GDMIndex() { return &RegionViewMapIndex; }
75 };
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000076}
Zhongxing Xu17892752008-10-08 02:50:44 +000077
Zhongxing Xu20794942009-05-06 08:33:50 +000078// RegionCasts records the current cast type of a region.
79namespace { class VISIBILITY_HIDDEN RegionCasts {}; }
80static int RegionCastsIndex = 0;
81namespace clang {
82 template<> struct GRStateTrait<RegionCasts>
83 : public GRStatePartialTrait<llvm::ImmutableMap<const MemRegion*,
84 QualType> > {
85 static void* GDMIndex() { return &RegionCastsIndex; }
86 };
87}
88
Ted Kremenek50dc1b32008-12-24 01:05:03 +000089//===----------------------------------------------------------------------===//
90// Region "Extents"
91//===----------------------------------------------------------------------===//
92//
93// MemRegions represent chunks of memory with a size (their "extent"). This
94// GDM entry tracks the extents for regions. Extents are in bytes.
Ted Kremenekd6cfbe42009-01-07 22:18:50 +000095//
Ted Kremenek50dc1b32008-12-24 01:05:03 +000096namespace { class VISIBILITY_HIDDEN RegionExtents {}; }
97static int RegionExtentsIndex = 0;
Zhongxing Xubaf03a72008-11-24 09:44:56 +000098namespace clang {
Ted Kremenek50dc1b32008-12-24 01:05:03 +000099 template<> struct GRStateTrait<RegionExtents>
100 : public GRStatePartialTrait<llvm::ImmutableMap<const MemRegion*, SVal> > {
101 static void* GDMIndex() { return &RegionExtentsIndex; }
102 };
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000103}
104
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000105//===----------------------------------------------------------------------===//
106// Region "killsets".
107//===----------------------------------------------------------------------===//
108//
Zhongxing Xu5834ed62009-01-13 01:49:57 +0000109// RegionStore lazily adds value bindings to regions when the analyzer handles
110// assignment statements. Killsets track which default values have been
111// killed, thus distinguishing between "unknown" values and default
112// values. Regions are added to killset only when they are assigned "unknown"
113// directly, otherwise we should have their value in the region bindings.
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000114//
115namespace { class VISIBILITY_HIDDEN RegionKills {}; }
Ted Kremenek2ed14be2008-12-05 00:47:52 +0000116static int RegionKillsIndex = 0;
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000117namespace clang {
Ted Kremenek2ed14be2008-12-05 00:47:52 +0000118 template<> struct GRStateTrait<RegionKills>
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000119 : public GRStatePartialTrait< llvm::ImmutableSet<const MemRegion*> > {
Ted Kremenek2ed14be2008-12-05 00:47:52 +0000120 static void* GDMIndex() { return &RegionKillsIndex; }
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000121 };
122}
123
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000124//===----------------------------------------------------------------------===//
Zhongxing Xu5834ed62009-01-13 01:49:57 +0000125// Regions with default values.
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000126//===----------------------------------------------------------------------===//
127//
Zhongxing Xu5834ed62009-01-13 01:49:57 +0000128// This GDM entry tracks what regions have a default value if they have no bound
129// value and have not been killed.
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000130//
131namespace { class VISIBILITY_HIDDEN RegionDefaultValue {}; }
132static int RegionDefaultValueIndex = 0;
133namespace clang {
134 template<> struct GRStateTrait<RegionDefaultValue>
135 : public GRStatePartialTrait<llvm::ImmutableMap<const MemRegion*, SVal> > {
136 static void* GDMIndex() { return &RegionDefaultValueIndex; }
137 };
138}
139
140//===----------------------------------------------------------------------===//
141// Main RegionStore logic.
142//===----------------------------------------------------------------------===//
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000143
Zhongxing Xu17892752008-10-08 02:50:44 +0000144namespace {
145
Ted Kremenek59e8f112009-03-03 01:35:36 +0000146class VISIBILITY_HIDDEN RegionStoreSubRegionMap : public SubRegionMap {
147 typedef llvm::DenseMap<const MemRegion*,
148 llvm::ImmutableSet<const MemRegion*> > Map;
149
150 llvm::ImmutableSet<const MemRegion*>::Factory F;
151 Map M;
152
153public:
154 void add(const MemRegion* Parent, const MemRegion* SubRegion) {
155 Map::iterator I = M.find(Parent);
156 M.insert(std::make_pair(Parent,
157 F.Add(I == M.end() ? F.GetEmptySet() : I->second, SubRegion)));
158 }
159
160 ~RegionStoreSubRegionMap() {}
161
Ted Kremenek5dc27462009-03-03 02:51:43 +0000162 bool iterSubRegions(const MemRegion* Parent, Visitor& V) const {
Ted Kremenek59e8f112009-03-03 01:35:36 +0000163 Map::iterator I = M.find(Parent);
164
165 if (I == M.end())
Ted Kremenek5dc27462009-03-03 02:51:43 +0000166 return true;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000167
168 llvm::ImmutableSet<const MemRegion*> S = I->second;
169 for (llvm::ImmutableSet<const MemRegion*>::iterator SI=S.begin(),SE=S.end();
170 SI != SE; ++SI) {
171 if (!V.Visit(Parent, *SI))
Ted Kremenek5dc27462009-03-03 02:51:43 +0000172 return false;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000173 }
Ted Kremenek5dc27462009-03-03 02:51:43 +0000174
175 return true;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000176 }
177};
178
Zhongxing Xu17892752008-10-08 02:50:44 +0000179class VISIBILITY_HIDDEN RegionStoreManager : public StoreManager {
Ted Kremenek9af46f52009-06-16 22:36:44 +0000180 const RegionStoreFeatures Features;
Zhongxing Xu17892752008-10-08 02:50:44 +0000181 RegionBindingsTy::Factory RBFactory;
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000182 RegionViews::Factory RVFactory;
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000183
Ted Kremenek6fd8f912009-01-22 23:43:57 +0000184 const MemRegion* SelfRegion;
185 const ImplicitParamDecl *SelfDecl;
Zhongxing Xu17892752008-10-08 02:50:44 +0000186
187public:
Ted Kremenek9af46f52009-06-16 22:36:44 +0000188 RegionStoreManager(GRStateManager& mgr, const RegionStoreFeatures &f)
Ted Kremenekc62abc12009-04-21 21:51:34 +0000189 : StoreManager(mgr),
Ted Kremenek9af46f52009-06-16 22:36:44 +0000190 Features(f),
Ted Kremenekd6cfbe42009-01-07 22:18:50 +0000191 RBFactory(mgr.getAllocator()),
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000192 RVFactory(mgr.getAllocator()),
Ted Kremenekc62abc12009-04-21 21:51:34 +0000193 SelfRegion(0), SelfDecl(0) {
Ted Kremenek6fd8f912009-01-22 23:43:57 +0000194 if (const ObjCMethodDecl* MD =
195 dyn_cast<ObjCMethodDecl>(&StateMgr.getCodeDecl()))
196 SelfDecl = MD->getSelfDecl();
197 }
Zhongxing Xu17892752008-10-08 02:50:44 +0000198
199 virtual ~RegionStoreManager() {}
200
Ted Kremenek14453bf2009-03-03 19:02:42 +0000201 SubRegionMap* getSubRegionMap(const GRState *state);
Ted Kremenek59e8f112009-03-03 01:35:36 +0000202
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000203 const GRState* BindCompoundLiteral(const GRState* St,
204 const CompoundLiteralExpr* CL, SVal V);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000205
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000206 /// getLValueString - Returns an SVal representing the lvalue of a
207 /// StringLiteral. Within RegionStore a StringLiteral has an
208 /// associated StringRegion, and the lvalue of a StringLiteral is
209 /// the lvalue of that region.
Zhongxing Xu143bf822008-10-25 14:18:57 +0000210 SVal getLValueString(const GRState* St, const StringLiteral* S);
211
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000212 /// getLValueCompoundLiteral - Returns an SVal representing the
213 /// lvalue of a compound literal. Within RegionStore a compound
214 /// literal has an associated region, and the lvalue of the
215 /// compound literal is the lvalue of that region.
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000216 SVal getLValueCompoundLiteral(const GRState* St, const CompoundLiteralExpr*);
217
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000218 /// getLValueVar - Returns an SVal that represents the lvalue of a
219 /// variable. Within RegionStore a variable has an associated
220 /// VarRegion, and the lvalue of the variable is the lvalue of that region.
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000221 SVal getLValueVar(const GRState* St, const VarDecl* VD);
222
223 SVal getLValueIvar(const GRState* St, const ObjCIvarDecl* D, SVal Base);
224
225 SVal getLValueField(const GRState* St, SVal Base, const FieldDecl* D);
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000226
227 SVal getLValueFieldOrIvar(const GRState* St, SVal Base, const Decl* D);
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000228
Ted Kremenekf936f452009-05-04 06:18:28 +0000229 SVal getLValueElement(const GRState* St, QualType elementType,
230 SVal Base, SVal Offset);
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000231
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000232 SVal getSizeInElements(const GRState* St, const MemRegion* R);
233
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000234 /// ArrayToPointer - Emulates the "decay" of an array to a pointer
235 /// type. 'Array' represents the lvalue of the array being decayed
236 /// to a pointer, and the returned SVal represents the decayed
237 /// version of that lvalue (i.e., a pointer to the first element of
238 /// the array). This is called by GRExprEngine when evaluating
239 /// casts from arrays to pointers.
Zhongxing Xuf1d537f2009-03-30 05:55:46 +0000240 SVal ArrayToPointer(Loc Array);
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000241
Zhongxing Xu88980592009-05-06 02:42:32 +0000242 CastResult CastRegion(const GRState* state, const MemRegion* R,
243 QualType CastToTy);
244
Zhongxing Xu262fd032009-05-20 09:00:16 +0000245 SVal EvalBinOp(const GRState *state,BinaryOperator::Opcode Op,Loc L,NonLoc R);
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000246
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000247 /// The high level logic for this method is this:
248 /// Retrieve (L)
249 /// if L has binding
250 /// return L's binding
251 /// else if L is in killset
252 /// return unknown
253 /// else
254 /// if L is on stack or heap
255 /// return undefined
256 /// else
257 /// return symbolic
Ted Kremenek2ed14be2008-12-05 00:47:52 +0000258 SVal Retrieve(const GRState* state, Loc L, QualType T = QualType());
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000259
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000260 const GRState* Bind(const GRState* St, Loc LV, SVal V);
Zhongxing Xu17892752008-10-08 02:50:44 +0000261
Zhongxing Xu9c9ca082008-12-16 02:36:30 +0000262 Store Remove(Store store, Loc LV);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000263
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000264 Store getInitialStore() { return RBFactory.GetEmptyMap().getRoot(); }
Ted Kremenek9deb0e32008-10-24 20:32:16 +0000265
266 /// getSelfRegion - Returns the region for the 'self' (Objective-C) or
267 /// 'this' object (C++). When used when analyzing a normal function this
268 /// method returns NULL.
269 const MemRegion* getSelfRegion(Store) {
Ted Kremenek6fd8f912009-01-22 23:43:57 +0000270 if (!SelfDecl)
271 return 0;
272
273 if (!SelfRegion) {
274 const ObjCMethodDecl *MD = cast<ObjCMethodDecl>(&StateMgr.getCodeDecl());
275 SelfRegion = MRMgr.getObjCObjectRegion(MD->getClassInterface(),
276 MRMgr.getHeapRegion());
277 }
278
279 return SelfRegion;
Ted Kremenek9deb0e32008-10-24 20:32:16 +0000280 }
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000281
Ted Kremenek2ed14be2008-12-05 00:47:52 +0000282 /// RemoveDeadBindings - Scans the RegionStore of 'state' for dead values.
283 /// It returns a new Store with these values removed, and populates LSymbols
284 // and DSymbols with the known set of live and dead symbols respectively.
285 Store RemoveDeadBindings(const GRState* state, Stmt* Loc,
Ted Kremenek241677a2009-01-21 22:26:05 +0000286 SymbolReaper& SymReaper,
287 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000288
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000289 const GRState* BindDecl(const GRState* St, const VarDecl* VD, SVal InitVal);
290
291 const GRState* BindDeclWithNoInit(const GRState* St, const VarDecl* VD) {
292 return St;
293 }
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000294
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000295 const GRState* setExtent(const GRState* St, const MemRegion* R, SVal Extent);
Zhongxing Xu20794942009-05-06 08:33:50 +0000296 const GRState* setCastType(const GRState* St, const MemRegion* R, QualType T);
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000297
Zhongxing Xu17892752008-10-08 02:50:44 +0000298 static inline RegionBindingsTy GetRegionBindings(Store store) {
Zhongxing Xu9c9ca082008-12-16 02:36:30 +0000299 return RegionBindingsTy(static_cast<const RegionBindingsTy::TreeTy*>(store));
Zhongxing Xu17892752008-10-08 02:50:44 +0000300 }
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000301
Zhongxing Xu5b8b6f22008-10-24 04:33:15 +0000302 void print(Store store, std::ostream& Out, const char* nl, const char *sep);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000303
304 void iterBindings(Store store, BindingsHandler& f) {
305 // FIXME: Implement.
306 }
Zhongxing Xu264e9372009-05-12 10:10:00 +0000307 const GRState* setDefaultValue(const GRState* St, const MemRegion* R, SVal V);
Zhongxing Xua82512a2008-10-24 08:42:28 +0000308private:
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000309 const GRState* BindArray(const GRState* St, const TypedRegion* R, SVal V);
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000310
Zhongxing Xu0b242ec2008-12-04 01:12:41 +0000311 /// Retrieve the values in a struct and return a CompoundVal, used when doing
312 /// struct copy:
313 /// struct s x, y;
314 /// x = y;
315 /// y's value is retrieved by this method.
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000316 SVal RetrieveStruct(const GRState* St, const TypedRegion* R);
Zhongxing Xu0b242ec2008-12-04 01:12:41 +0000317
Zhongxing Xu3e001f32009-05-03 00:27:40 +0000318 SVal RetrieveArray(const GRState* St, const TypedRegion* R);
319
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000320 const GRState* BindStruct(const GRState* St, const TypedRegion* R, SVal V);
Zhongxing Xu63123d82008-11-23 04:30:35 +0000321
Zhongxing Xu5834ed62009-01-13 01:49:57 +0000322 /// KillStruct - Set the entire struct to unknown.
323 const GRState* KillStruct(const GRState* St, const TypedRegion* R);
324
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000325 // Utility methods.
326 BasicValueFactory& getBasicVals() { return StateMgr.getBasicVals(); }
327 ASTContext& getContext() { return StateMgr.getContext(); }
Zhongxing Xua15f7ac2009-05-08 01:33:18 +0000328
Zhongxing Xu63123d82008-11-23 04:30:35 +0000329 SymbolManager& getSymbolManager() { return StateMgr.getSymbolManager(); }
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000330
331 const GRState* AddRegionView(const GRState* St,
332 const MemRegion* View, const MemRegion* Base);
Zhongxing Xu5834ed62009-01-13 01:49:57 +0000333 const GRState* RemoveRegionView(const GRState* St,
334 const MemRegion* View, const MemRegion* Base);
Zhongxing Xu17892752008-10-08 02:50:44 +0000335};
336
337} // end anonymous namespace
338
Ted Kremenek9af46f52009-06-16 22:36:44 +0000339//===----------------------------------------------------------------------===//
340// RegionStore creation.
341//===----------------------------------------------------------------------===//
342
343StoreManager *clang::CreateRegionStoreManager(GRStateManager& StMgr) {
344 RegionStoreFeatures F = maximal_features_tag();
345 return new RegionStoreManager(StMgr, F);
346}
347
348StoreManager *clang::CreateFieldsOnlyRegionStoreManager(GRStateManager &StMgr) {
349 RegionStoreFeatures F = minimal_features_tag();
350 F.enableFields(true);
351 return new RegionStoreManager(StMgr, F);
Ted Kremenek95c7b002008-10-24 01:04:59 +0000352}
353
Ted Kremenek14453bf2009-03-03 19:02:42 +0000354SubRegionMap* RegionStoreManager::getSubRegionMap(const GRState *state) {
Ted Kremenek59e8f112009-03-03 01:35:36 +0000355 RegionBindingsTy B = GetRegionBindings(state->getStore());
356 RegionStoreSubRegionMap *M = new RegionStoreSubRegionMap();
357
358 for (RegionBindingsTy::iterator I=B.begin(), E=B.end(); I!=E; ++I) {
359 if (const SubRegion* R = dyn_cast<SubRegion>(I.getKey()))
360 M->add(R->getSuperRegion(), R);
361 }
362
Ted Kremenek14453bf2009-03-03 19:02:42 +0000363 return M;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000364}
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000365
Ted Kremenek9af46f52009-06-16 22:36:44 +0000366//===----------------------------------------------------------------------===//
367// getLValueXXX methods.
368//===----------------------------------------------------------------------===//
369
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000370/// getLValueString - Returns an SVal representing the lvalue of a
371/// StringLiteral. Within RegionStore a StringLiteral has an
372/// associated StringRegion, and the lvalue of a StringLiteral is the
373/// lvalue of that region.
Zhongxing Xu143bf822008-10-25 14:18:57 +0000374SVal RegionStoreManager::getLValueString(const GRState* St,
375 const StringLiteral* S) {
376 return loc::MemRegionVal(MRMgr.getStringRegion(S));
377}
378
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000379/// getLValueVar - Returns an SVal that represents the lvalue of a
380/// variable. Within RegionStore a variable has an associated
381/// VarRegion, and the lvalue of the variable is the lvalue of that region.
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000382SVal RegionStoreManager::getLValueVar(const GRState* St, const VarDecl* VD) {
383 return loc::MemRegionVal(MRMgr.getVarRegion(VD));
384}
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000385
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000386/// getLValueCompoundLiteral - Returns an SVal representing the lvalue
387/// of a compound literal. Within RegionStore a compound literal
388/// has an associated region, and the lvalue of the compound literal
389/// is the lvalue of that region.
390SVal
391RegionStoreManager::getLValueCompoundLiteral(const GRState* St,
392 const CompoundLiteralExpr* CL) {
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000393 return loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL));
394}
395
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000396SVal RegionStoreManager::getLValueIvar(const GRState* St, const ObjCIvarDecl* D,
397 SVal Base) {
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000398 return getLValueFieldOrIvar(St, Base, D);
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000399}
400
401SVal RegionStoreManager::getLValueField(const GRState* St, SVal Base,
402 const FieldDecl* D) {
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000403 return getLValueFieldOrIvar(St, Base, D);
404}
405
406SVal RegionStoreManager::getLValueFieldOrIvar(const GRState* St, SVal Base,
407 const Decl* D) {
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000408 if (Base.isUnknownOrUndef())
409 return Base;
410
411 Loc BaseL = cast<Loc>(Base);
412 const MemRegion* BaseR = 0;
413
414 switch (BaseL.getSubKind()) {
415 case loc::MemRegionKind:
416 BaseR = cast<loc::MemRegionVal>(BaseL).getRegion();
417 break;
418
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000419 case loc::GotoLabelKind:
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000420 // These are anormal cases. Flag an undefined value.
421 return UndefinedVal();
422
423 case loc::ConcreteIntKind:
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000424 // While these seem funny, this can happen through casts.
425 // FIXME: What we should return is the field offset. For example,
426 // add the field offset to the integer value. That way funny things
427 // like this work properly: &(((struct foo *) 0xa)->f)
428 return Base;
429
430 default:
Zhongxing Xu13d1ee22008-11-07 08:57:30 +0000431 assert(0 && "Unhandled Base.");
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000432 return Base;
433 }
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000434
435 // NOTE: We must have this check first because ObjCIvarDecl is a subclass
436 // of FieldDecl.
437 if (const ObjCIvarDecl *ID = dyn_cast<ObjCIvarDecl>(D))
438 return loc::MemRegionVal(MRMgr.getObjCIvarRegion(ID, BaseR));
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000439
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000440 return loc::MemRegionVal(MRMgr.getFieldRegion(cast<FieldDecl>(D), BaseR));
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000441}
442
Ted Kremenekf936f452009-05-04 06:18:28 +0000443SVal RegionStoreManager::getLValueElement(const GRState* St,
444 QualType elementType,
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000445 SVal Base, SVal Offset) {
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000446
Ted Kremenekde7ec632009-03-09 22:44:49 +0000447 // If the base is an unknown or undefined value, just return it back.
448 // FIXME: For absolute pointer addresses, we just return that value back as
449 // well, although in reality we should return the offset added to that
450 // value.
451 if (Base.isUnknownOrUndef() || isa<loc::ConcreteInt>(Base))
Zhongxing Xu4a1513e2008-10-27 12:23:17 +0000452 return Base;
453
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000454 // Only handle integer offsets... for now.
455 if (!isa<nonloc::ConcreteInt>(Offset))
Zhongxing Xue4d13932008-11-13 09:48:44 +0000456 return UnknownVal();
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000457
Zhongxing Xuce760782009-05-09 13:20:07 +0000458 const MemRegion* BaseRegion = cast<loc::MemRegionVal>(Base).getRegion();
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000459
460 // Pointer of any type can be cast and used as array base.
461 const ElementRegion *ElemR = dyn_cast<ElementRegion>(BaseRegion);
462
463 if (!ElemR) {
464 //
465 // If the base region is not an ElementRegion, create one.
466 // This can happen in the following example:
467 //
468 // char *p = __builtin_alloc(10);
469 // p[1] = 8;
470 //
Zhongxing Xuce760782009-05-09 13:20:07 +0000471 // Observe that 'p' binds to an AllocaRegion.
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000472 //
Zhongxing Xu5ea2ffc2009-02-19 08:37:16 +0000473
474 // Offset might be unsigned. We have to convert it to signed ConcreteInt.
475 if (nonloc::ConcreteInt* CI = dyn_cast<nonloc::ConcreteInt>(&Offset)) {
476 const llvm::APSInt& OffI = CI->getValue();
477 if (OffI.isUnsigned()) {
478 llvm::APSInt Tmp = OffI;
479 Tmp.setIsSigned(true);
480 Offset = NonLoc::MakeVal(getBasicVals(), Tmp);
481 }
482 }
Ted Kremenekf936f452009-05-04 06:18:28 +0000483 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, Offset,
Zhongxing Xu143b2fc2009-06-16 09:55:50 +0000484 BaseRegion, getContext()));
Zhongxing Xue4d13932008-11-13 09:48:44 +0000485 }
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000486
487 SVal BaseIdx = ElemR->getIndex();
488
489 if (!isa<nonloc::ConcreteInt>(BaseIdx))
490 return UnknownVal();
491
492 const llvm::APSInt& BaseIdxI = cast<nonloc::ConcreteInt>(BaseIdx).getValue();
493 const llvm::APSInt& OffI = cast<nonloc::ConcreteInt>(Offset).getValue();
494 assert(BaseIdxI.isSigned());
495
496 // FIXME: This appears to be the assumption of this code. We should review
497 // whether or not BaseIdxI.getBitWidth() < OffI.getBitWidth(). If it
498 // can't we need to put a comment here. If it can, we should handle it.
499 assert(BaseIdxI.getBitWidth() >= OffI.getBitWidth());
Zhongxing Xue4d13932008-11-13 09:48:44 +0000500
Zhongxing Xuce760782009-05-09 13:20:07 +0000501 const MemRegion *ArrayR = ElemR->getSuperRegion();
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000502 SVal NewIdx;
503
504 if (OffI.isUnsigned() || OffI.getBitWidth() < BaseIdxI.getBitWidth()) {
505 // 'Offset' might be unsigned. We have to convert it to signed and
506 // possibly extend it.
507 llvm::APSInt Tmp = OffI;
508
509 if (OffI.getBitWidth() < BaseIdxI.getBitWidth())
510 Tmp.extend(BaseIdxI.getBitWidth());
511
512 Tmp.setIsSigned(true);
513 Tmp += BaseIdxI; // Compute the new offset.
Zhongxing Xu5ea2ffc2009-02-19 08:37:16 +0000514 NewIdx = NonLoc::MakeVal(getBasicVals(), Tmp);
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000515 }
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000516 else
517 NewIdx = nonloc::ConcreteInt(getBasicVals().getValue(BaseIdxI + OffI));
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000518
Zhongxing Xu143b2fc2009-06-16 09:55:50 +0000519 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, NewIdx, ArrayR,
520 getContext()));
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000521}
522
Ted Kremenek9af46f52009-06-16 22:36:44 +0000523//===----------------------------------------------------------------------===//
524// Extents for regions.
525//===----------------------------------------------------------------------===//
526
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000527SVal RegionStoreManager::getSizeInElements(const GRState* St,
528 const MemRegion* R) {
529 if (const VarRegion* VR = dyn_cast<VarRegion>(R)) {
530 // Get the type of the variable.
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000531 QualType T = VR->getDesugaredValueType(getContext());
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000532
Ted Kremenek14553ab2009-01-30 00:08:43 +0000533 // FIXME: Handle variable-length arrays.
534 if (isa<VariableArrayType>(T))
535 return UnknownVal();
536
537 if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(T)) {
538 // return the size as signed integer.
539 return NonLoc::MakeVal(getBasicVals(), CAT->getSize(), false);
540 }
Zhongxing Xu20794942009-05-06 08:33:50 +0000541
Zhongxing Xu41fd0182009-05-06 11:51:48 +0000542 GRStateRef state(St, StateMgr);
543 const QualType* CastTy = state.get<RegionCasts>(VR);
544
Zhongxing Xue6536af2009-05-08 02:00:55 +0000545 // If the VarRegion is cast to other type, compute the size with respect to
546 // that type.
Zhongxing Xu41fd0182009-05-06 11:51:48 +0000547 if (CastTy) {
548 QualType EleTy =cast<PointerType>(CastTy->getTypePtr())->getPointeeType();
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000549 QualType VarTy = VR->getValueType(getContext());
Zhongxing Xue6536af2009-05-08 02:00:55 +0000550 uint64_t EleSize = getContext().getTypeSize(EleTy);
551 uint64_t VarSize = getContext().getTypeSize(VarTy);
552 return NonLoc::MakeIntVal(getBasicVals(), VarSize / EleSize, false);
Zhongxing Xu41fd0182009-05-06 11:51:48 +0000553 }
554
Ted Kremenek14553ab2009-01-30 00:08:43 +0000555 // Clients can use ordinary variables as if they were arrays. These
556 // essentially are arrays of size 1.
557 return NonLoc::MakeIntVal(getBasicVals(), 1, false);
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000558 }
559
560 if (const StringRegion* SR = dyn_cast<StringRegion>(R)) {
Zhongxing Xu6613d082008-11-24 02:18:56 +0000561 const StringLiteral* Str = SR->getStringLiteral();
Zhongxing Xud0fd3b72008-11-24 02:30:48 +0000562 // We intentionally made the size value signed because it participates in
563 // operations with signed indices.
Ted Kremenek14553ab2009-01-30 00:08:43 +0000564 return NonLoc::MakeIntVal(getBasicVals(), Str->getByteLength()+1, false);
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000565 }
566
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000567 if (const FieldRegion* FR = dyn_cast<FieldRegion>(R)) {
568 // FIXME: Unsupported yet.
569 FR = 0;
570 return UnknownVal();
571 }
Zhongxing Xu369f4292008-11-22 13:23:00 +0000572
Zhongxing Xu02ebefb2009-02-06 08:51:30 +0000573 if (isa<SymbolicRegion>(R)) {
Zhongxing Xua48f7372009-02-06 08:44:27 +0000574 return UnknownVal();
575 }
576
Zhongxing Xuce760782009-05-09 13:20:07 +0000577 if (isa<AllocaRegion>(R)) {
578 return UnknownVal();
579 }
580
Zhongxing Xuccb16162009-05-06 08:08:27 +0000581 if (isa<ElementRegion>(R)) {
582 return UnknownVal();
583 }
584
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000585 assert(0 && "Other regions are not supported yet.");
Ted Kremeneka21362d2009-01-06 19:12:06 +0000586 return UnknownVal();
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000587}
588
Ted Kremenek9af46f52009-06-16 22:36:44 +0000589const GRState* RegionStoreManager::setExtent(const GRState* St,
590 const MemRegion* R, SVal Extent) {
591 GRStateRef state(St, StateMgr);
592 return state.set<RegionExtents>(R, Extent);
593}
594
595//===----------------------------------------------------------------------===//
596// Location and region casting.
597//===----------------------------------------------------------------------===//
598
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000599/// ArrayToPointer - Emulates the "decay" of an array to a pointer
600/// type. 'Array' represents the lvalue of the array being decayed
601/// to a pointer, and the returned SVal represents the decayed
602/// version of that lvalue (i.e., a pointer to the first element of
603/// the array). This is called by GRExprEngine when evaluating casts
604/// from arrays to pointers.
Zhongxing Xuf1d537f2009-03-30 05:55:46 +0000605SVal RegionStoreManager::ArrayToPointer(Loc Array) {
Ted Kremenekabb042f2008-12-13 19:24:37 +0000606 if (!isa<loc::MemRegionVal>(Array))
607 return UnknownVal();
608
609 const MemRegion* R = cast<loc::MemRegionVal>(&Array)->getRegion();
610 const TypedRegion* ArrayR = dyn_cast<TypedRegion>(R);
611
Ted Kremenekbbee1a72009-01-13 01:03:27 +0000612 if (!ArrayR)
Ted Kremenekabb042f2008-12-13 19:24:37 +0000613 return UnknownVal();
614
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000615 // Strip off typedefs from the ArrayRegion's ValueType.
616 QualType T = ArrayR->getValueType(getContext())->getDesugaredType();
Ted Kremenekf936f452009-05-04 06:18:28 +0000617 ArrayType *AT = cast<ArrayType>(T);
618 T = AT->getElementType();
619
Zhongxing Xu63123d82008-11-23 04:30:35 +0000620 nonloc::ConcreteInt Idx(getBasicVals().getZeroWithPtrWidth(false));
Zhongxing Xu143b2fc2009-06-16 09:55:50 +0000621 ElementRegion* ER = MRMgr.getElementRegion(T, Idx, ArrayR, getContext());
Zhongxing Xu0b7e6422008-10-26 02:23:57 +0000622
623 return loc::MemRegionVal(ER);
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000624}
625
Zhongxing Xu88980592009-05-06 02:42:32 +0000626RegionStoreManager::CastResult
627RegionStoreManager::CastRegion(const GRState* state, const MemRegion* R,
Zhongxing Xu41fd0182009-05-06 11:51:48 +0000628 QualType CastToTy) {
Zhongxing Xu88980592009-05-06 02:42:32 +0000629
630 ASTContext& Ctx = StateMgr.getContext();
631
632 // We need to know the real type of CastToTy.
633 QualType ToTy = Ctx.getCanonicalType(CastToTy);
634
635 // Check cast to ObjCQualifiedID type.
636 if (isa<ObjCQualifiedIdType>(ToTy)) {
637 // FIXME: Record the type information aside.
638 return CastResult(state, R);
639 }
640
641 // CodeTextRegion should be cast to only function pointer type.
642 if (isa<CodeTextRegion>(R)) {
643 assert(CastToTy->isFunctionPointerType() || CastToTy->isBlockPointerType());
644 return CastResult(state, R);
645 }
646
Zhongxing Xudb3a0982009-05-09 10:03:08 +0000647 // Now assume we are casting from pointer to pointer. Other cases should
648 // already be handled.
Zhongxing Xu88980592009-05-06 02:42:32 +0000649 QualType PointeeTy = cast<PointerType>(ToTy.getTypePtr())->getPointeeType();
650
Zhongxing Xu88980592009-05-06 02:42:32 +0000651 // Process region cast according to the kind of the region being cast.
652
Zhongxing Xu88980592009-05-06 02:42:32 +0000653 // FIXME: Need to handle arbitrary downcasts.
Zhongxing Xu88980592009-05-06 02:42:32 +0000654 if (isa<SymbolicRegion>(R) || isa<AllocaRegion>(R)) {
Zhongxing Xuce760782009-05-09 13:20:07 +0000655 state = setCastType(state, R, ToTy);
656 return CastResult(state, R);
Zhongxing Xu88980592009-05-06 02:42:32 +0000657 }
658
659 // VarRegion, ElementRegion, and FieldRegion has an inherent type. Normally
660 // they should not be cast. We only layer an ElementRegion when the cast-to
661 // pointee type is of smaller size. In other cases, we return the original
662 // VarRegion.
663 if (isa<VarRegion>(R) || isa<ElementRegion>(R) || isa<FieldRegion>(R)
664 || isa<ObjCIvarRegion>(R) || isa<CompoundLiteralRegion>(R)) {
Zhongxing Xu2572eda2009-05-08 07:28:25 +0000665 // If the pointee type is incomplete, do not compute its size, and return
666 // the original region.
667 if (const RecordType *RT = dyn_cast<RecordType>(PointeeTy.getTypePtr())) {
668 const RecordDecl *D = RT->getDecl();
669 if (!D->getDefinition(getContext()))
670 return CastResult(state, R);
671 }
672
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000673 QualType ObjTy = cast<TypedRegion>(R)->getValueType(getContext());
Zhongxing Xufb1e3312009-05-08 02:12:59 +0000674 uint64_t PointeeTySize = getContext().getTypeSize(PointeeTy);
675 uint64_t ObjTySize = getContext().getTypeSize(ObjTy);
676
Zhongxing Xu5bf32872009-05-09 15:34:29 +0000677 if ((PointeeTySize > 0 && PointeeTySize < ObjTySize) ||
678 (ObjTy->isAggregateType() && PointeeTy->isScalarType())) {
Zhongxing Xu20794942009-05-06 08:33:50 +0000679 // Record the cast type of the region.
680 state = setCastType(state, R, ToTy);
681
Zhongxing Xuccb16162009-05-06 08:08:27 +0000682 SVal Idx = ValMgr.makeZeroArrayIndex();
Zhongxing Xu143b2fc2009-06-16 09:55:50 +0000683 ElementRegion* ER = MRMgr.getElementRegion(PointeeTy, Idx,R,getContext());
Zhongxing Xuccb16162009-05-06 08:08:27 +0000684 return CastResult(state, ER);
685 } else
686 return CastResult(state, R);
Zhongxing Xu88980592009-05-06 02:42:32 +0000687 }
688
Zhongxing Xu88980592009-05-06 02:42:32 +0000689 if (isa<ObjCObjectRegion>(R)) {
690 return CastResult(state, R);
691 }
692
693 assert(0 && "Unprocessed region.");
Daniel Dunbar4e609002009-05-18 16:48:48 +0000694 return 0;
Zhongxing Xu88980592009-05-06 02:42:32 +0000695}
696
Ted Kremenek9af46f52009-06-16 22:36:44 +0000697//===----------------------------------------------------------------------===//
698// Pointer arithmetic.
699//===----------------------------------------------------------------------===//
700
Zhongxing Xu262fd032009-05-20 09:00:16 +0000701SVal RegionStoreManager::EvalBinOp(const GRState *state,
702 BinaryOperator::Opcode Op, Loc L, NonLoc R) {
Zhongxing Xuc4761f52009-05-09 15:18:12 +0000703 // Assume the base location is MemRegionVal.
Ted Kremenek5dc27462009-03-03 02:51:43 +0000704 if (!isa<loc::MemRegionVal>(L))
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000705 return UnknownVal();
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000706
Zhongxing Xua1718c72009-04-03 07:33:13 +0000707 const MemRegion* MR = cast<loc::MemRegionVal>(L).getRegion();
Zhongxing Xuc4761f52009-05-09 15:18:12 +0000708 const ElementRegion *ER = 0;
Zhongxing Xu262fd032009-05-20 09:00:16 +0000709
710 // If the operand is a symbolic or alloca region, create the first element
711 // region on it.
Zhongxing Xuc4761f52009-05-09 15:18:12 +0000712 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR)) {
713 // Get symbol's type. It should be a pointer type.
714 SymbolRef Sym = SR->getSymbol();
715 QualType T = Sym->getType(getContext());
Zhongxing Xu53454dc2009-06-12 03:59:12 +0000716 QualType EleTy = T->getAsPointerType()->getPointeeType();
Zhongxing Xua1718c72009-04-03 07:33:13 +0000717
Zhongxing Xuc4761f52009-05-09 15:18:12 +0000718 SVal ZeroIdx = ValMgr.makeZeroArrayIndex();
Zhongxing Xu143b2fc2009-06-16 09:55:50 +0000719 ER = MRMgr.getElementRegion(EleTy, ZeroIdx, SR, getContext());
Zhongxing Xu262fd032009-05-20 09:00:16 +0000720 }
721 else if (const AllocaRegion *AR = dyn_cast<AllocaRegion>(MR)) {
722 // Get the alloca region's current cast type.
723 GRStateRef StRef(state, StateMgr);
724
725 GRStateTrait<RegionCasts>::lookup_type T = StRef.get<RegionCasts>(AR);
726 assert(T && "alloca region has no type.");
727 QualType EleTy = cast<PointerType>(T->getTypePtr())->getPointeeType();
728 SVal ZeroIdx = ValMgr.makeZeroArrayIndex();
Zhongxing Xu143b2fc2009-06-16 09:55:50 +0000729 ER = MRMgr.getElementRegion(EleTy, ZeroIdx, AR, getContext());
Zhongxing Xu262fd032009-05-20 09:00:16 +0000730 }
731 else
Zhongxing Xuc4761f52009-05-09 15:18:12 +0000732 ER = cast<ElementRegion>(MR);
Zhongxing Xu2b1dc172009-03-11 07:43:49 +0000733
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000734 SVal Idx = ER->getIndex();
735
736 nonloc::ConcreteInt* Base = dyn_cast<nonloc::ConcreteInt>(&Idx);
737 nonloc::ConcreteInt* Offset = dyn_cast<nonloc::ConcreteInt>(&R);
738
739 // Only support concrete integer indexes for now.
740 if (Base && Offset) {
Ted Kremenek610e81d2009-03-13 15:35:24 +0000741 // FIXME: For now, convert the signedness and bitwidth of offset in case
742 // they don't match. This can result from pointer arithmetic. In reality,
743 // we should figure out what are the proper semantics and implement them.
744 //
Ted Kremenek1060a3c2009-03-13 15:39:16 +0000745 // This addresses the test case test/Analysis/ptr-arith.c
746 //
Ted Kremenek610e81d2009-03-13 15:35:24 +0000747 nonloc::ConcreteInt OffConverted(getBasicVals().Convert(Base->getValue(),
748 Offset->getValue()));
749 SVal NewIdx = Base->EvalBinOp(getBasicVals(), Op, OffConverted);
Ted Kremenekf936f452009-05-04 06:18:28 +0000750 const MemRegion* NewER =
Zhongxing Xu143b2fc2009-06-16 09:55:50 +0000751 MRMgr.getElementRegion(ER->getElementType(), NewIdx,ER->getSuperRegion(),
752 getContext());
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000753 return Loc::MakeVal(NewER);
754
Ted Kremenek5dc27462009-03-03 02:51:43 +0000755 }
756
757 return UnknownVal();
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000758}
759
Ted Kremenek9af46f52009-06-16 22:36:44 +0000760//===----------------------------------------------------------------------===//
761// Loading values from regions.
762//===----------------------------------------------------------------------===//
763
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000764SVal RegionStoreManager::Retrieve(const GRState* St, Loc L, QualType T) {
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000765 assert(!isa<UnknownVal>(L) && "location unknown");
766 assert(!isa<UndefinedVal>(L) && "location undefined");
767
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000768 // FIXME: Is this even possible? Shouldn't this be treated as a null
769 // dereference at a higher level?
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000770 if (isa<loc::ConcreteInt>(L))
771 return UndefinedVal();
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000772
Zhongxing Xua1718c72009-04-03 07:33:13 +0000773 const MemRegion* MR = cast<loc::MemRegionVal>(L).getRegion();
774
Zhongxing Xu91844122009-05-20 09:18:48 +0000775 // FIXME: return symbolic value for these cases.
Zhongxing Xua1718c72009-04-03 07:33:13 +0000776 // Example:
777 // void f(int* p) { int x = *p; }
Zhongxing Xu91844122009-05-20 09:18:48 +0000778 // char* p = alloca();
779 // read(p);
780 // c = *p;
781 if (isa<SymbolicRegion>(MR) || isa<AllocaRegion>(MR))
Zhongxing Xua1718c72009-04-03 07:33:13 +0000782 return UnknownVal();
783
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000784 // FIXME: Perhaps this method should just take a 'const MemRegion*' argument
785 // instead of 'Loc', and have the other Loc cases handled at a higher level.
Zhongxing Xua1718c72009-04-03 07:33:13 +0000786 const TypedRegion* R = cast<TypedRegion>(MR);
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000787 assert(R && "bad region");
788
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000789 // FIXME: We should eventually handle funny addressing. e.g.:
790 //
791 // int x = ...;
792 // int *p = &x;
793 // char *q = (char*) p;
794 // char c = *q; // returns the first byte of 'x'.
795 //
796 // Such funny addressing will occur due to layering of regions.
797
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000798 QualType RTy = R->getValueType(getContext());
Zhongxing Xu3e001f32009-05-03 00:27:40 +0000799
Zhongxing Xu1038f9f2009-03-09 09:15:51 +0000800 if (RTy->isStructureType())
801 return RetrieveStruct(St, R);
Zhongxing Xu3e001f32009-05-03 00:27:40 +0000802
803 if (RTy->isArrayType())
804 return RetrieveArray(St, R);
805
Zhongxing Xu1038f9f2009-03-09 09:15:51 +0000806 // FIXME: handle Vector types.
807 if (RTy->isVectorType())
Ted Kremenek265a3052009-02-24 02:23:11 +0000808 return UnknownVal();
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000809
810 RegionBindingsTy B = GetRegionBindings(St->getStore());
811 RegionBindingsTy::data_type* V = B.lookup(R);
812
813 // Check if the region has a binding.
814 if (V)
815 return *V;
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000816
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000817 GRStateRef state(St, StateMgr);
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000818
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000819 // Check if the region is in killset.
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000820 if (state.contains<RegionKills>(R))
821 return UnknownVal();
822
Zhongxing Xuc87d5fb2009-05-11 14:23:36 +0000823 // Check if the region is an element region of a string literal.
824 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
825 if (const StringRegion *StrR=dyn_cast<StringRegion>(ER->getSuperRegion())) {
826 const StringLiteral *Str = StrR->getStringLiteral();
827 SVal Idx = ER->getIndex();
828 if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&Idx)) {
829 int64_t i = CI->getValue().getSExtValue();
830 char c;
831 if (i == Str->getByteLength())
832 c = '\0';
833 else
834 c = Str->getStrData()[i];
835 const llvm::APSInt &V = getBasicVals().getValue(c, getContext().CharTy);
836 return nonloc::ConcreteInt(V);
837 }
838 }
839 }
840
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000841 // If the region is an element or field, it may have a default value.
Zhongxing Xu562c4d92009-01-23 11:22:12 +0000842 if (isa<ElementRegion>(R) || isa<FieldRegion>(R)) {
843 const MemRegion* SuperR = cast<SubRegion>(R)->getSuperRegion();
844 GRStateTrait<RegionDefaultValue>::lookup_type D =
845 state.get<RegionDefaultValue>(SuperR);
Zhongxing Xu264e9372009-05-12 10:10:00 +0000846 if (D) {
847 // If the default value is symbolic, we need to create a new symbol.
848 if (D->hasConjuredSymbol())
849 return ValMgr.getRegionValueSymbolVal(R);
850 else
851 return *D;
852 }
Zhongxing Xu562c4d92009-01-23 11:22:12 +0000853 }
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000854
855 if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) {
856 const MemRegion *SR = IVR->getSuperRegion();
857
858 // If the super region is 'self' then return the symbol representing
859 // the value of the ivar upon entry to the method.
860 if (SR == SelfRegion) {
861 // FIXME: Do we need to handle the case where the super region
862 // has a view? We want to canonicalize the bindings.
Zhongxing Xud9b6ad62009-05-09 04:08:27 +0000863 return ValMgr.getRegionValueSymbolVal(R);
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000864 }
865
866 // Otherwise, we need a new symbol. For now return Unknown.
867 return UnknownVal();
868 }
Zhongxing Xu562c4d92009-01-23 11:22:12 +0000869
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000870 // The location does not have a bound value. This means that it has
871 // the value it had upon its creation and/or entry to the analyzed
872 // function/method. These are either symbolic values or 'undefined'.
873
874 // We treat function parameters as symbolic values.
Ted Kremenek6fd8f912009-01-22 23:43:57 +0000875 if (const VarRegion* VR = dyn_cast<VarRegion>(R)) {
876 const VarDecl *VD = VR->getDecl();
877
Ted Kremenekcec35252009-03-04 00:23:05 +0000878 if (VD == SelfDecl)
879 return loc::MemRegionVal(getSelfRegion(0));
880
881 if (isa<ParmVarDecl>(VD) || isa<ImplicitParamDecl>(VD) ||
882 VD->hasGlobalStorage()) {
Zhongxing Xud8895f62009-02-19 09:56:08 +0000883 QualType VTy = VD->getType();
884 if (Loc::IsLocType(VTy) || VTy->isIntegerType())
Zhongxing Xud9b6ad62009-05-09 04:08:27 +0000885 return ValMgr.getRegionValueSymbolVal(VR);
Zhongxing Xud8895f62009-02-19 09:56:08 +0000886 else
887 return UnknownVal();
888 }
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000889 }
Ted Kremenek265a3052009-02-24 02:23:11 +0000890
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000891 if (MRMgr.onStack(R) || MRMgr.onHeap(R)) {
892 // All stack variables are considered to have undefined values
893 // upon creation. All heap allocated blocks are considered to
894 // have undefined values as well unless they are explicitly bound
895 // to specific values.
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000896 return UndefinedVal();
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000897 }
898
Zhongxing Xuff8d2042009-03-09 09:31:22 +0000899 // All other integer values are symbolic.
900 if (Loc::IsLocType(RTy) || RTy->isIntegerType())
Zhongxing Xud9b6ad62009-05-09 04:08:27 +0000901 return ValMgr.getRegionValueSymbolVal(R);
Zhongxing Xuff8d2042009-03-09 09:31:22 +0000902 else
903 return UnknownVal();
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000904}
905
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000906SVal RegionStoreManager::RetrieveStruct(const GRState* St,const TypedRegion* R){
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000907 QualType T = R->getValueType(getContext());
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000908 assert(T->isStructureType());
909
Zhongxing Xub7507d12009-06-11 07:27:30 +0000910 const RecordType* RT = T->getAsStructureType();
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000911 RecordDecl* RD = RT->getDecl();
912 assert(RD->isDefinition());
913
914 llvm::ImmutableList<SVal> StructVal = getBasicVals().getEmptySValList();
915
Douglas Gregor6ab35242009-04-09 21:40:53 +0000916 std::vector<FieldDecl *> Fields(RD->field_begin(getContext()),
917 RD->field_end(getContext()));
Douglas Gregor44b43212008-12-11 16:49:14 +0000918
Douglas Gregore267ff32008-12-11 20:41:00 +0000919 for (std::vector<FieldDecl *>::reverse_iterator Field = Fields.rbegin(),
920 FieldEnd = Fields.rend();
921 Field != FieldEnd; ++Field) {
922 FieldRegion* FR = MRMgr.getFieldRegion(*Field, R);
Zhongxing Xu3e001f32009-05-03 00:27:40 +0000923 QualType FTy = (*Field)->getType();
924 SVal FieldValue = Retrieve(St, loc::MemRegionVal(FR), FTy);
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000925 StructVal = getBasicVals().consVals(FieldValue, StructVal);
926 }
927
928 return NonLoc::MakeCompoundVal(T, StructVal, getBasicVals());
929}
930
Zhongxing Xu3e001f32009-05-03 00:27:40 +0000931SVal RegionStoreManager::RetrieveArray(const GRState* St, const TypedRegion* R){
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000932 QualType T = R->getValueType(getContext());
Zhongxing Xu3e001f32009-05-03 00:27:40 +0000933 ConstantArrayType* CAT = cast<ConstantArrayType>(T.getTypePtr());
934
935 llvm::ImmutableList<SVal> ArrayVal = getBasicVals().getEmptySValList();
Zhongxing Xu3e001f32009-05-03 00:27:40 +0000936 llvm::APSInt Size(CAT->getSize(), false);
Zhongxing Xu2ee52142009-05-11 12:48:56 +0000937 llvm::APSInt i = getBasicVals().getZeroWithPtrWidth(false);
Zhongxing Xu3e001f32009-05-03 00:27:40 +0000938
939 for (; i < Size; ++i) {
940 SVal Idx = NonLoc::MakeVal(getBasicVals(), i);
Zhongxing Xu143b2fc2009-06-16 09:55:50 +0000941 ElementRegion* ER = MRMgr.getElementRegion(CAT->getElementType(), Idx, R,
942 getContext());
Ted Kremenekf936f452009-05-04 06:18:28 +0000943 QualType ETy = ER->getElementType();
Zhongxing Xu3e001f32009-05-03 00:27:40 +0000944 SVal ElementVal = Retrieve(St, loc::MemRegionVal(ER), ETy);
945 ArrayVal = getBasicVals().consVals(ElementVal, ArrayVal);
946 }
947
948 return NonLoc::MakeCompoundVal(T, ArrayVal, getBasicVals());
949}
950
Ted Kremenek9af46f52009-06-16 22:36:44 +0000951//===----------------------------------------------------------------------===//
952// Binding values to regions.
953//===----------------------------------------------------------------------===//
Zhongxing Xu17892752008-10-08 02:50:44 +0000954
Zhongxing Xu9c9ca082008-12-16 02:36:30 +0000955Store RegionStoreManager::Remove(Store store, Loc L) {
Ted Kremenek0964a062009-01-21 06:57:53 +0000956 const MemRegion* R = 0;
957
958 if (isa<loc::MemRegionVal>(L))
959 R = cast<loc::MemRegionVal>(L).getRegion();
Ted Kremenek0964a062009-01-21 06:57:53 +0000960
961 if (R) {
962 RegionBindingsTy B = GetRegionBindings(store);
963 return RBFactory.Remove(B, R).getRoot();
964 }
965
966 return store;
Zhongxing Xu9c9ca082008-12-16 02:36:30 +0000967}
968
Ted Kremenek9af46f52009-06-16 22:36:44 +0000969const GRState* RegionStoreManager::Bind(const GRState* St, Loc L, SVal V) {
970 // If we get here, the location should be a region.
971 const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion();
972 assert(R);
973
974 // Check if the region is a struct region.
975 if (const TypedRegion* TR = dyn_cast<TypedRegion>(R))
976 if (TR->getValueType(getContext())->isStructureType())
977 return BindStruct(St, TR, V);
978
979 Store store = St->getStore();
980 RegionBindingsTy B = GetRegionBindings(store);
981
982 if (V.isUnknown()) {
983 // Remove the binding.
984 store = RBFactory.Remove(B, R).getRoot();
985
986 // Add the region to the killset.
987 GRStateRef state(St, StateMgr);
988 St = state.add<RegionKills>(R);
989 }
990 else
991 store = RBFactory.Add(B, R, V).getRoot();
992
993 return StateMgr.MakeStateWithStore(St, store);
994}
995
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000996const GRState* RegionStoreManager::BindDecl(const GRState* St,
997 const VarDecl* VD, SVal InitVal) {
Zhongxing Xua4f28ff2008-11-13 08:41:36 +0000998
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000999 QualType T = VD->getType();
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001000 VarRegion* VR = MRMgr.getVarRegion(VD);
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +00001001
Ted Kremenek0964a062009-01-21 06:57:53 +00001002 if (T->isArrayType())
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001003 return BindArray(St, VR, InitVal);
Ted Kremenek0964a062009-01-21 06:57:53 +00001004 if (T->isStructureType())
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001005 return BindStruct(St, VR, InitVal);
Zhongxing Xud463d442008-11-02 12:13:30 +00001006
Ted Kremenek0964a062009-01-21 06:57:53 +00001007 return Bind(St, Loc::MakeVal(VR), InitVal);
Zhongxing Xu17892752008-10-08 02:50:44 +00001008}
Zhongxing Xu53bcdd42008-10-21 05:29:26 +00001009
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001010// FIXME: this method should be merged into Bind().
1011const GRState*
1012RegionStoreManager::BindCompoundLiteral(const GRState* St,
1013 const CompoundLiteralExpr* CL, SVal V) {
Zhongxing Xuf22679e2008-11-07 10:38:33 +00001014 CompoundLiteralRegion* R = MRMgr.getCompoundLiteralRegion(CL);
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001015 return Bind(St, loc::MemRegionVal(R), V);
Zhongxing Xuf22679e2008-11-07 10:38:33 +00001016}
1017
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001018const GRState* RegionStoreManager::BindArray(const GRState* St,
1019 const TypedRegion* R, SVal Init) {
Zhongxing Xua82d8aa2009-05-09 03:57:34 +00001020 QualType T = R->getValueType(getContext());
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001021 assert(T->isArrayType());
1022
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001023 // When we are binding the whole array, it always has default value 0.
1024 GRStateRef state(St, StateMgr);
Ted Kremenek14553ab2009-01-30 00:08:43 +00001025 St = state.set<RegionDefaultValue>(R, NonLoc::MakeIntVal(getBasicVals(), 0,
1026 false));
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001027
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001028 ConstantArrayType* CAT = cast<ConstantArrayType>(T.getTypePtr());
1029
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001030 llvm::APSInt Size(CAT->getSize(), false);
Sebastian Redl1be3da52009-01-26 19:54:12 +00001031 llvm::APSInt i = getBasicVals().getValue(0, Size.getBitWidth(),
1032 Size.isUnsigned());
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001033
1034 // Check if the init expr is a StringLiteral.
1035 if (isa<loc::MemRegionVal>(Init)) {
1036 const MemRegion* InitR = cast<loc::MemRegionVal>(Init).getRegion();
1037 const StringLiteral* S = cast<StringRegion>(InitR)->getStringLiteral();
1038 const char* str = S->getStrData();
1039 unsigned len = S->getByteLength();
1040 unsigned j = 0;
1041
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001042 // Copy bytes from the string literal into the target array. Trailing bytes
1043 // in the array that are not covered by the string literal are initialized
1044 // to zero.
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001045 for (; i < Size; ++i, ++j) {
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001046 if (j >= len)
1047 break;
1048
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001049 SVal Idx = NonLoc::MakeVal(getBasicVals(), i);
Ted Kremenekf936f452009-05-04 06:18:28 +00001050 ElementRegion* ER =
1051 MRMgr.getElementRegion(cast<ArrayType>(T)->getElementType(),
Zhongxing Xu143b2fc2009-06-16 09:55:50 +00001052 Idx, R, getContext());
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001053
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001054 SVal V = NonLoc::MakeVal(getBasicVals(), str[j], sizeof(char)*8, true);
1055 St = Bind(St, loc::MemRegionVal(ER), V);
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001056 }
1057
Zhongxing Xubd4f7452009-03-09 06:49:50 +00001058 return St;
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001059 }
1060
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001061 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(Init);
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001062 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
1063
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001064 for (; i < Size; ++i, ++VI) {
1065 // The init list might be shorter than the array decl.
1066 if (VI == VE)
1067 break;
1068
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001069 SVal Idx = NonLoc::MakeVal(getBasicVals(), i);
Ted Kremenekf936f452009-05-04 06:18:28 +00001070 ElementRegion* ER =
1071 MRMgr.getElementRegion(cast<ArrayType>(T)->getElementType(),
Zhongxing Xu143b2fc2009-06-16 09:55:50 +00001072 Idx, R, getContext());
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001073
1074 if (CAT->getElementType()->isStructureType())
1075 St = BindStruct(St, ER, *VI);
1076 else
1077 St = Bind(St, Loc::MakeVal(ER), *VI);
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001078 }
1079
Zhongxing Xubd4f7452009-03-09 06:49:50 +00001080 return St;
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001081}
1082
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001083const GRState*
1084RegionStoreManager::BindStruct(const GRState* St, const TypedRegion* R, SVal V){
Zhongxing Xua82d8aa2009-05-09 03:57:34 +00001085 QualType T = R->getValueType(getContext());
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001086 assert(T->isStructureType());
1087
Zhongxing Xub13ecdb2009-03-12 03:45:35 +00001088 const RecordType* RT = T->getAsRecordType();
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001089 RecordDecl* RD = RT->getDecl();
Zhongxing Xuc45a8252009-03-11 09:07:35 +00001090
1091 if (!RD->isDefinition())
1092 return St;
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001093
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001094 if (V.isUnknown())
1095 return KillStruct(St, R);
1096
Zhongxing Xuf0ec39a2009-06-13 01:31:11 +00001097 // We may get non-CompoundVal accidentally due to imprecise cast logic. Ignore
1098 // them and make struct unknown.
1099 if (!isa<nonloc::CompoundVal>(V))
1100 return KillStruct(St, R);
Zhongxing Xu3f6978a2009-06-11 09:11:27 +00001101
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001102 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V);
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001103 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
Douglas Gregor6ab35242009-04-09 21:40:53 +00001104 RecordDecl::field_iterator FI = RD->field_begin(getContext()),
1105 FE = RD->field_end(getContext());
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001106
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001107 for (; FI != FE; ++FI, ++VI) {
1108
1109 // There may be fewer values than fields only when we are initializing a
1110 // struct decl. In this case, mark the region as having default value.
1111 if (VI == VE) {
Zhongxing Xu13020162008-12-24 07:29:24 +00001112 GRStateRef state(St, StateMgr);
Ted Kremenek14553ab2009-01-30 00:08:43 +00001113 const NonLoc& Idx = NonLoc::MakeIntVal(getBasicVals(), 0, false);
1114 St = state.set<RegionDefaultValue>(R, Idx);
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001115 break;
1116 }
1117
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001118 QualType FTy = (*FI)->getType();
1119 FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);
1120
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001121 if (Loc::IsLocType(FTy) || FTy->isIntegerType())
1122 St = Bind(St, Loc::MakeVal(FR), *VI);
Zhongxing Xua82512a2008-10-24 08:42:28 +00001123
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001124 else if (FTy->isArrayType())
1125 St = BindArray(St, FR, *VI);
Zhongxing Xua82512a2008-10-24 08:42:28 +00001126
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001127 else if (FTy->isStructureType())
1128 St = BindStruct(St, FR, *VI);
Zhongxing Xua82512a2008-10-24 08:42:28 +00001129 }
1130
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001131 return St;
Zhongxing Xuc3a05992008-11-19 11:06:24 +00001132}
1133
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001134const GRState* RegionStoreManager::KillStruct(const GRState* St,
1135 const TypedRegion* R){
1136 GRStateRef state(St, StateMgr);
1137
1138 // Kill the struct region because it is assigned "unknown".
1139 St = state.add<RegionKills>(R);
1140
1141 // Set the default value of the struct region to "unknown".
1142 St = state.set<RegionDefaultValue>(R, UnknownVal());
1143
1144 Store store = St->getStore();
1145 RegionBindingsTy B = GetRegionBindings(store);
1146
1147 // Remove all bindings for the subregions of the struct.
1148 for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
1149 const MemRegion* r = I.getKey();
1150 if (const SubRegion* sr = dyn_cast<SubRegion>(r))
1151 if (sr->isSubRegionOf(R))
1152 store = Remove(store, Loc::MakeVal(sr));
Zhongxing Xu9c2a3db2009-01-13 03:07:41 +00001153 // FIXME: Maybe we should also remove the bindings for the "views" of the
1154 // subregions.
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001155 }
1156
1157 return StateMgr.MakeStateWithStore(St, store);
1158}
1159
Ted Kremenek9af46f52009-06-16 22:36:44 +00001160//===----------------------------------------------------------------------===//
1161// Region views.
1162//===----------------------------------------------------------------------===//
1163
Zhongxing Xudc0a25d2008-11-16 04:07:26 +00001164const GRState* RegionStoreManager::AddRegionView(const GRState* St,
1165 const MemRegion* View,
1166 const MemRegion* Base) {
1167 GRStateRef state(St, StateMgr);
1168
1169 // First, retrieve the region view of the base region.
Ted Kremenek50dc1b32008-12-24 01:05:03 +00001170 const RegionViews* d = state.get<RegionViewMap>(Base);
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001171 RegionViews L = d ? *d : RVFactory.GetEmptySet();
Zhongxing Xudc0a25d2008-11-16 04:07:26 +00001172
1173 // Now add View to the region view.
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001174 L = RVFactory.Add(L, View);
Zhongxing Xudc0a25d2008-11-16 04:07:26 +00001175
1176 // Create a new state with the new region view.
Ted Kremenek50dc1b32008-12-24 01:05:03 +00001177 return state.set<RegionViewMap>(Base, L);
Zhongxing Xudc0a25d2008-11-16 04:07:26 +00001178}
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001179
1180const GRState* RegionStoreManager::RemoveRegionView(const GRState* St,
1181 const MemRegion* View,
1182 const MemRegion* Base) {
1183 GRStateRef state(St, StateMgr);
1184
1185 // Retrieve the region view of the base region.
1186 const RegionViews* d = state.get<RegionViewMap>(Base);
1187
1188 // If the base region has no view, return.
1189 if (!d)
1190 return St;
1191
1192 // Remove the view.
1193 RegionViews V = *d;
1194 V = RVFactory.Remove(V, View);
1195
1196 return state.set<RegionViewMap>(Base, V);
1197}
Zhongxing Xu20794942009-05-06 08:33:50 +00001198
1199const GRState* RegionStoreManager::setCastType(const GRState* St,
1200 const MemRegion* R, QualType T) {
1201 GRStateRef state(St, StateMgr);
1202 return state.set<RegionCasts>(R, T);
1203}
Zhongxing Xu264e9372009-05-12 10:10:00 +00001204
1205const GRState* RegionStoreManager::setDefaultValue(const GRState* St,
1206 const MemRegion* R, SVal V) {
1207 GRStateRef state(St, StateMgr);
1208 return state.set<RegionDefaultValue>(R, V);
1209}
Ted Kremenek9af46f52009-06-16 22:36:44 +00001210
1211//===----------------------------------------------------------------------===//
1212// State pruning.
1213//===----------------------------------------------------------------------===//
1214
1215static void UpdateLiveSymbols(SVal X, SymbolReaper& SymReaper) {
1216 if (loc::MemRegionVal *XR = dyn_cast<loc::MemRegionVal>(&X)) {
1217 const MemRegion *R = XR->getRegion();
1218
1219 while (R) {
1220 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) {
1221 SymReaper.markLive(SR->getSymbol());
1222 return;
1223 }
1224
1225 if (const SubRegion *SR = dyn_cast<SubRegion>(R)) {
1226 R = SR->getSuperRegion();
1227 continue;
1228 }
1229
1230 break;
1231 }
1232
1233 return;
1234 }
1235
1236 for (SVal::symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end();SI!=SE;++SI)
1237 SymReaper.markLive(*SI);
1238}
1239
1240Store RegionStoreManager::RemoveDeadBindings(const GRState* state, Stmt* Loc,
1241 SymbolReaper& SymReaper,
1242 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots)
1243{
1244
1245 Store store = state->getStore();
1246 RegionBindingsTy B = GetRegionBindings(store);
1247
1248 // Lazily constructed backmap from MemRegions to SubRegions.
1249 typedef llvm::ImmutableSet<const MemRegion*> SubRegionsTy;
1250 typedef llvm::ImmutableMap<const MemRegion*, SubRegionsTy> SubRegionsMapTy;
1251
1252 // FIXME: As a future optimization we can modifiy BumpPtrAllocator to have
1253 // the ability to reuse memory. This way we can keep TmpAlloc around as
1254 // an instance variable of RegionStoreManager (avoiding repeated malloc
1255 // overhead).
1256 llvm::BumpPtrAllocator TmpAlloc;
1257
1258 // Factory objects.
1259 SubRegionsMapTy::Factory SubRegMapF(TmpAlloc);
1260 SubRegionsTy::Factory SubRegF(TmpAlloc);
1261
1262 // The backmap from regions to subregions.
1263 SubRegionsMapTy SubRegMap = SubRegMapF.GetEmptyMap();
1264
1265 // Do a pass over the regions in the store. For VarRegions we check if
1266 // the variable is still live and if so add it to the list of live roots.
1267 // For other regions we populate our region backmap.
1268
1269 llvm::SmallVector<const MemRegion*, 10> IntermediateRoots;
1270
1271 for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
1272 IntermediateRoots.push_back(I.getKey());
1273 }
1274
1275 while (!IntermediateRoots.empty()) {
1276 const MemRegion* R = IntermediateRoots.back();
1277 IntermediateRoots.pop_back();
1278
1279 if (const VarRegion* VR = dyn_cast<VarRegion>(R)) {
1280 if (SymReaper.isLive(Loc, VR->getDecl()))
1281 RegionRoots.push_back(VR); // This is a live "root".
1282 }
1283 else if (const SymbolicRegion* SR = dyn_cast<SymbolicRegion>(R)) {
1284 if (SymReaper.isLive(SR->getSymbol()))
1285 RegionRoots.push_back(SR);
1286 }
1287 else {
1288 // Get the super region for R.
1289 const MemRegion* SuperR = cast<SubRegion>(R)->getSuperRegion();
1290
1291 // Get the current set of subregions for SuperR.
1292 const SubRegionsTy* SRptr = SubRegMap.lookup(SuperR);
1293 SubRegionsTy SRs = SRptr ? *SRptr : SubRegF.GetEmptySet();
1294
1295 // Add R to the subregions of SuperR.
1296 SubRegMap = SubRegMapF.Add(SubRegMap, SuperR, SubRegF.Add(SRs, R));
1297
1298 // Super region may be VarRegion or subregion of another VarRegion. Add it
1299 // to the work list.
1300 if (isa<SubRegion>(SuperR))
1301 IntermediateRoots.push_back(SuperR);
1302 }
1303 }
1304
1305 // Process the worklist of RegionRoots. This performs a "mark-and-sweep"
1306 // of the store. We want to find all live symbols and dead regions.
1307 llvm::SmallPtrSet<const MemRegion*, 10> Marked;
1308
1309 while (!RegionRoots.empty()) {
1310 // Dequeue the next region on the worklist.
1311 const MemRegion* R = RegionRoots.back();
1312 RegionRoots.pop_back();
1313
1314 // Check if we have already processed this region.
1315 if (Marked.count(R)) continue;
1316
1317 // Mark this region as processed. This is needed for termination in case
1318 // a region is referenced more than once.
1319 Marked.insert(R);
1320
1321 // Mark the symbol for any live SymbolicRegion as "live". This means we
1322 // should continue to track that symbol.
1323 if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(R))
1324 SymReaper.markLive(SymR->getSymbol());
1325
1326 // Get the data binding for R (if any).
1327 RegionBindingsTy::data_type* Xptr = B.lookup(R);
1328 if (Xptr) {
1329 SVal X = *Xptr;
1330 UpdateLiveSymbols(X, SymReaper); // Update the set of live symbols.
1331
1332 // If X is a region, then add it the RegionRoots.
1333 if (loc::MemRegionVal* RegionX = dyn_cast<loc::MemRegionVal>(&X))
1334 RegionRoots.push_back(RegionX->getRegion());
1335 }
1336
1337 // Get the subregions of R. These are RegionRoots as well since they
1338 // represent values that are also bound to R.
1339 const SubRegionsTy* SRptr = SubRegMap.lookup(R);
1340 if (!SRptr) continue;
1341 SubRegionsTy SR = *SRptr;
1342
1343 for (SubRegionsTy::iterator I=SR.begin(), E=SR.end(); I!=E; ++I)
1344 RegionRoots.push_back(*I);
1345 }
1346
1347 // We have now scanned the store, marking reachable regions and symbols
1348 // as live. We now remove all the regions that are dead from the store
1349 // as well as update DSymbols with the set symbols that are now dead.
1350 for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
1351 const MemRegion* R = I.getKey();
1352
1353 // If this region live? Is so, none of its symbols are dead.
1354 if (Marked.count(R))
1355 continue;
1356
1357 // Remove this dead region from the store.
1358 store = Remove(store, Loc::MakeVal(R));
1359
1360 // Mark all non-live symbols that this region references as dead.
1361 if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(R))
1362 SymReaper.maybeDead(SymR->getSymbol());
1363
1364 SVal X = I.getData();
1365 SVal::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
1366 for (; SI != SE; ++SI) SymReaper.maybeDead(*SI);
1367 }
1368
1369 return store;
1370}
1371
1372//===----------------------------------------------------------------------===//
1373// Utility methods.
1374//===----------------------------------------------------------------------===//
1375
1376void RegionStoreManager::print(Store store, std::ostream& Out,
1377 const char* nl, const char *sep) {
1378 llvm::raw_os_ostream OS(Out);
1379 RegionBindingsTy B = GetRegionBindings(store);
1380 OS << "Store:" << nl;
1381
1382 for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
1383 OS << ' '; I.getKey()->print(OS); OS << " : ";
1384 I.getData().print(OS); OS << nl;
1385 }
1386}