blob: 65afe46bc094fa017842f591d8bb4f4c467362ba [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
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000203 /// getLValueString - Returns an SVal representing the lvalue of a
204 /// StringLiteral. Within RegionStore a StringLiteral has an
205 /// associated StringRegion, and the lvalue of a StringLiteral is
206 /// the lvalue of that region.
Ted Kremenek67f28532009-06-17 22:02:04 +0000207 SVal getLValueString(const GRState *state, const StringLiteral* S);
Zhongxing Xu143bf822008-10-25 14:18:57 +0000208
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000209 /// getLValueCompoundLiteral - Returns an SVal representing the
210 /// lvalue of a compound literal. Within RegionStore a compound
211 /// literal has an associated region, and the lvalue of the
212 /// compound literal is the lvalue of that region.
Ted Kremenek67f28532009-06-17 22:02:04 +0000213 SVal getLValueCompoundLiteral(const GRState *state, const CompoundLiteralExpr*);
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000214
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000215 /// getLValueVar - Returns an SVal that represents the lvalue of a
216 /// variable. Within RegionStore a variable has an associated
217 /// VarRegion, and the lvalue of the variable is the lvalue of that region.
Ted Kremenek67f28532009-06-17 22:02:04 +0000218 SVal getLValueVar(const GRState *state, const VarDecl* VD);
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000219
Ted Kremenek67f28532009-06-17 22:02:04 +0000220 SVal getLValueIvar(const GRState *state, const ObjCIvarDecl* D, SVal Base);
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000221
Ted Kremenek67f28532009-06-17 22:02:04 +0000222 SVal getLValueField(const GRState *state, SVal Base, const FieldDecl* D);
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000223
Ted Kremenek67f28532009-06-17 22:02:04 +0000224 SVal getLValueFieldOrIvar(const GRState *state, SVal Base, const Decl* D);
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000225
Ted Kremenek67f28532009-06-17 22:02:04 +0000226 SVal getLValueElement(const GRState *state, QualType elementType,
Ted Kremenekf936f452009-05-04 06:18:28 +0000227 SVal Base, SVal Offset);
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000228
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000229
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000230 /// ArrayToPointer - Emulates the "decay" of an array to a pointer
231 /// type. 'Array' represents the lvalue of the array being decayed
232 /// to a pointer, and the returned SVal represents the decayed
233 /// version of that lvalue (i.e., a pointer to the first element of
234 /// the array). This is called by GRExprEngine when evaluating
235 /// casts from arrays to pointers.
Zhongxing Xuf1d537f2009-03-30 05:55:46 +0000236 SVal ArrayToPointer(Loc Array);
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000237
Ted Kremenek67f28532009-06-17 22:02:04 +0000238 CastResult CastRegion(const GRState *state, const MemRegion* R,
Zhongxing Xu88980592009-05-06 02:42:32 +0000239 QualType CastToTy);
240
Ted Kremenek53ba0b62009-06-24 23:06:47 +0000241 SVal EvalBinOp(const GRState *state, BinaryOperator::Opcode Op,Loc L,
242 NonLoc R);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000243
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000244 Store getInitialStore() { return RBFactory.GetEmptyMap().getRoot(); }
Ted Kremenek9deb0e32008-10-24 20:32:16 +0000245
246 /// getSelfRegion - Returns the region for the 'self' (Objective-C) or
247 /// 'this' object (C++). When used when analyzing a normal function this
248 /// method returns NULL.
249 const MemRegion* getSelfRegion(Store) {
Ted Kremenek6fd8f912009-01-22 23:43:57 +0000250 if (!SelfDecl)
251 return 0;
252
253 if (!SelfRegion) {
254 const ObjCMethodDecl *MD = cast<ObjCMethodDecl>(&StateMgr.getCodeDecl());
255 SelfRegion = MRMgr.getObjCObjectRegion(MD->getClassInterface(),
256 MRMgr.getHeapRegion());
257 }
258
259 return SelfRegion;
Ted Kremenek9deb0e32008-10-24 20:32:16 +0000260 }
Ted Kremenek67f28532009-06-17 22:02:04 +0000261
262 //===-------------------------------------------------------------------===//
263 // Binding values to regions.
264 //===-------------------------------------------------------------------===//
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000265
Ted Kremenek67f28532009-06-17 22:02:04 +0000266 const GRState *Bind(const GRState *state, Loc LV, SVal V);
267
268 const GRState *BindCompoundLiteral(const GRState *state,
269 const CompoundLiteralExpr* CL, SVal V);
270
271 const GRState *BindDecl(const GRState *state, const VarDecl* VD, SVal InitVal);
272
273 const GRState *BindDeclWithNoInit(const GRState *state, const VarDecl* VD) {
274 return state;
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000275 }
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000276
Ted Kremenek67f28532009-06-17 22:02:04 +0000277 /// BindStruct - Bind a compound value to a structure.
278 const GRState *BindStruct(const GRState *, const TypedRegion* R, SVal V);
279
280 const GRState *BindArray(const GRState *state, const TypedRegion* R, SVal V);
281
282 /// KillStruct - Set the entire struct to unknown.
283 const GRState *KillStruct(const GRState *state, const TypedRegion* R);
284
285 const GRState *setDefaultValue(const GRState *state, const MemRegion* R, SVal V);
286
287 Store Remove(Store store, Loc LV);
288
289 //===------------------------------------------------------------------===//
290 // Loading values from regions.
291 //===------------------------------------------------------------------===//
292
293 /// The high level logic for this method is this:
294 /// Retrieve (L)
295 /// if L has binding
296 /// return L's binding
297 /// else if L is in killset
298 /// return unknown
299 /// else
300 /// if L is on stack or heap
301 /// return undefined
302 /// else
303 /// return symbolic
304 SVal Retrieve(const GRState *state, Loc L, QualType T = QualType());
305
306 /// Retrieve the values in a struct and return a CompoundVal, used when doing
307 /// struct copy:
308 /// struct s x, y;
309 /// x = y;
310 /// y's value is retrieved by this method.
311 SVal RetrieveStruct(const GRState *St, const TypedRegion* R);
312
313 SVal RetrieveArray(const GRState *St, const TypedRegion* R);
314
315 //===------------------------------------------------------------------===//
316 // State pruning.
317 //===------------------------------------------------------------------===//
318
319 /// RemoveDeadBindings - Scans the RegionStore of 'state' for dead values.
320 /// It returns a new Store with these values removed.
321 Store RemoveDeadBindings(const GRState *state, Stmt* Loc, SymbolReaper& SymReaper,
322 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots);
323
324 //===------------------------------------------------------------------===//
325 // Region "extents".
326 //===------------------------------------------------------------------===//
327
328 const GRState *setExtent(const GRState *state, const MemRegion* R, SVal Extent);
329 SVal getSizeInElements(const GRState *state, const MemRegion* R);
330
331 //===------------------------------------------------------------------===//
332 // Region "views".
333 //===------------------------------------------------------------------===//
334
335 const GRState *AddRegionView(const GRState *state, const MemRegion* View,
336 const MemRegion* Base);
337
338 const GRState *RemoveRegionView(const GRState *state, const MemRegion* View,
339 const MemRegion* Base);
340
341 //===------------------------------------------------------------------===//
342 // Utility methods.
343 //===------------------------------------------------------------------===//
344
345 const GRState *setCastType(const GRState *state, const MemRegion* R, QualType T);
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000346
Zhongxing Xu17892752008-10-08 02:50:44 +0000347 static inline RegionBindingsTy GetRegionBindings(Store store) {
Zhongxing Xu9c9ca082008-12-16 02:36:30 +0000348 return RegionBindingsTy(static_cast<const RegionBindingsTy::TreeTy*>(store));
Zhongxing Xu17892752008-10-08 02:50:44 +0000349 }
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000350
Ted Kremenek53ba0b62009-06-24 23:06:47 +0000351 void print(Store store, llvm::raw_ostream& Out, const char* nl,
352 const char *sep);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000353
354 void iterBindings(Store store, BindingsHandler& f) {
355 // FIXME: Implement.
356 }
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000357
Ted Kremenek67f28532009-06-17 22:02:04 +0000358 // FIXME: Remove.
359 BasicValueFactory& getBasicVals() {
360 return StateMgr.getBasicVals();
361 }
362
363 // FIXME: Remove.
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000364 ASTContext& getContext() { return StateMgr.getContext(); }
Zhongxing Xua15f7ac2009-05-08 01:33:18 +0000365
Ted Kremenek67f28532009-06-17 22:02:04 +0000366 // FIXME: Use ValueManager?
367 SymbolManager& getSymbolManager() { return StateMgr.getSymbolManager(); }
Zhongxing Xu17892752008-10-08 02:50:44 +0000368};
369
370} // end anonymous namespace
371
Ted Kremenek9af46f52009-06-16 22:36:44 +0000372//===----------------------------------------------------------------------===//
373// RegionStore creation.
374//===----------------------------------------------------------------------===//
375
376StoreManager *clang::CreateRegionStoreManager(GRStateManager& StMgr) {
377 RegionStoreFeatures F = maximal_features_tag();
378 return new RegionStoreManager(StMgr, F);
379}
380
381StoreManager *clang::CreateFieldsOnlyRegionStoreManager(GRStateManager &StMgr) {
382 RegionStoreFeatures F = minimal_features_tag();
383 F.enableFields(true);
384 return new RegionStoreManager(StMgr, F);
Ted Kremenek95c7b002008-10-24 01:04:59 +0000385}
386
Ted Kremenek14453bf2009-03-03 19:02:42 +0000387SubRegionMap* RegionStoreManager::getSubRegionMap(const GRState *state) {
Ted Kremenek59e8f112009-03-03 01:35:36 +0000388 RegionBindingsTy B = GetRegionBindings(state->getStore());
389 RegionStoreSubRegionMap *M = new RegionStoreSubRegionMap();
390
391 for (RegionBindingsTy::iterator I=B.begin(), E=B.end(); I!=E; ++I) {
392 if (const SubRegion* R = dyn_cast<SubRegion>(I.getKey()))
393 M->add(R->getSuperRegion(), R);
394 }
395
Ted Kremenek14453bf2009-03-03 19:02:42 +0000396 return M;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000397}
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000398
Ted Kremenek9af46f52009-06-16 22:36:44 +0000399//===----------------------------------------------------------------------===//
400// getLValueXXX methods.
401//===----------------------------------------------------------------------===//
402
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000403/// getLValueString - Returns an SVal representing the lvalue of a
404/// StringLiteral. Within RegionStore a StringLiteral has an
405/// associated StringRegion, and the lvalue of a StringLiteral is the
406/// lvalue of that region.
Ted Kremenek67f28532009-06-17 22:02:04 +0000407SVal RegionStoreManager::getLValueString(const GRState *St,
Zhongxing Xu143bf822008-10-25 14:18:57 +0000408 const StringLiteral* S) {
409 return loc::MemRegionVal(MRMgr.getStringRegion(S));
410}
411
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000412/// getLValueVar - Returns an SVal that represents the lvalue of a
413/// variable. Within RegionStore a variable has an associated
414/// VarRegion, and the lvalue of the variable is the lvalue of that region.
Ted Kremenek67f28532009-06-17 22:02:04 +0000415SVal RegionStoreManager::getLValueVar(const GRState *St, const VarDecl* VD) {
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000416 return loc::MemRegionVal(MRMgr.getVarRegion(VD));
417}
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000418
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000419/// getLValueCompoundLiteral - Returns an SVal representing the lvalue
420/// of a compound literal. Within RegionStore a compound literal
421/// has an associated region, and the lvalue of the compound literal
422/// is the lvalue of that region.
423SVal
Ted Kremenek67f28532009-06-17 22:02:04 +0000424RegionStoreManager::getLValueCompoundLiteral(const GRState *St,
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000425 const CompoundLiteralExpr* CL) {
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000426 return loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL));
427}
428
Ted Kremenek67f28532009-06-17 22:02:04 +0000429SVal RegionStoreManager::getLValueIvar(const GRState *St, const ObjCIvarDecl* D,
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000430 SVal Base) {
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000431 return getLValueFieldOrIvar(St, Base, D);
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000432}
433
Ted Kremenek67f28532009-06-17 22:02:04 +0000434SVal RegionStoreManager::getLValueField(const GRState *St, SVal Base,
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000435 const FieldDecl* D) {
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000436 return getLValueFieldOrIvar(St, Base, D);
437}
438
Ted Kremenek67f28532009-06-17 22:02:04 +0000439SVal RegionStoreManager::getLValueFieldOrIvar(const GRState *St, SVal Base,
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000440 const Decl* D) {
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000441 if (Base.isUnknownOrUndef())
442 return Base;
443
444 Loc BaseL = cast<Loc>(Base);
445 const MemRegion* BaseR = 0;
446
447 switch (BaseL.getSubKind()) {
448 case loc::MemRegionKind:
449 BaseR = cast<loc::MemRegionVal>(BaseL).getRegion();
450 break;
451
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000452 case loc::GotoLabelKind:
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000453 // These are anormal cases. Flag an undefined value.
454 return UndefinedVal();
455
456 case loc::ConcreteIntKind:
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000457 // While these seem funny, this can happen through casts.
458 // FIXME: What we should return is the field offset. For example,
459 // add the field offset to the integer value. That way funny things
460 // like this work properly: &(((struct foo *) 0xa)->f)
461 return Base;
462
463 default:
Zhongxing Xu13d1ee22008-11-07 08:57:30 +0000464 assert(0 && "Unhandled Base.");
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000465 return Base;
466 }
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000467
468 // NOTE: We must have this check first because ObjCIvarDecl is a subclass
469 // of FieldDecl.
470 if (const ObjCIvarDecl *ID = dyn_cast<ObjCIvarDecl>(D))
471 return loc::MemRegionVal(MRMgr.getObjCIvarRegion(ID, BaseR));
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000472
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000473 return loc::MemRegionVal(MRMgr.getFieldRegion(cast<FieldDecl>(D), BaseR));
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000474}
475
Ted Kremenek67f28532009-06-17 22:02:04 +0000476SVal RegionStoreManager::getLValueElement(const GRState *St,
Ted Kremenekf936f452009-05-04 06:18:28 +0000477 QualType elementType,
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000478 SVal Base, SVal Offset) {
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000479
Ted Kremenekde7ec632009-03-09 22:44:49 +0000480 // If the base is an unknown or undefined value, just return it back.
481 // FIXME: For absolute pointer addresses, we just return that value back as
482 // well, although in reality we should return the offset added to that
483 // value.
484 if (Base.isUnknownOrUndef() || isa<loc::ConcreteInt>(Base))
Zhongxing Xu4a1513e2008-10-27 12:23:17 +0000485 return Base;
486
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000487 // Only handle integer offsets... for now.
488 if (!isa<nonloc::ConcreteInt>(Offset))
Zhongxing Xue4d13932008-11-13 09:48:44 +0000489 return UnknownVal();
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000490
Zhongxing Xuce760782009-05-09 13:20:07 +0000491 const MemRegion* BaseRegion = cast<loc::MemRegionVal>(Base).getRegion();
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000492
493 // Pointer of any type can be cast and used as array base.
494 const ElementRegion *ElemR = dyn_cast<ElementRegion>(BaseRegion);
495
496 if (!ElemR) {
497 //
498 // If the base region is not an ElementRegion, create one.
499 // This can happen in the following example:
500 //
501 // char *p = __builtin_alloc(10);
502 // p[1] = 8;
503 //
Zhongxing Xuce760782009-05-09 13:20:07 +0000504 // Observe that 'p' binds to an AllocaRegion.
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000505 //
Zhongxing Xu5ea2ffc2009-02-19 08:37:16 +0000506
507 // Offset might be unsigned. We have to convert it to signed ConcreteInt.
508 if (nonloc::ConcreteInt* CI = dyn_cast<nonloc::ConcreteInt>(&Offset)) {
509 const llvm::APSInt& OffI = CI->getValue();
510 if (OffI.isUnsigned()) {
511 llvm::APSInt Tmp = OffI;
512 Tmp.setIsSigned(true);
Zhongxing Xud91ee272009-06-23 09:02:15 +0000513 Offset = ValMgr.makeIntVal(Tmp);
Zhongxing Xu5ea2ffc2009-02-19 08:37:16 +0000514 }
515 }
Ted Kremenekf936f452009-05-04 06:18:28 +0000516 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, Offset,
Zhongxing Xu143b2fc2009-06-16 09:55:50 +0000517 BaseRegion, getContext()));
Zhongxing Xue4d13932008-11-13 09:48:44 +0000518 }
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000519
520 SVal BaseIdx = ElemR->getIndex();
521
522 if (!isa<nonloc::ConcreteInt>(BaseIdx))
523 return UnknownVal();
524
525 const llvm::APSInt& BaseIdxI = cast<nonloc::ConcreteInt>(BaseIdx).getValue();
526 const llvm::APSInt& OffI = cast<nonloc::ConcreteInt>(Offset).getValue();
527 assert(BaseIdxI.isSigned());
528
529 // FIXME: This appears to be the assumption of this code. We should review
530 // whether or not BaseIdxI.getBitWidth() < OffI.getBitWidth(). If it
531 // can't we need to put a comment here. If it can, we should handle it.
532 assert(BaseIdxI.getBitWidth() >= OffI.getBitWidth());
Zhongxing Xue4d13932008-11-13 09:48:44 +0000533
Zhongxing Xuce760782009-05-09 13:20:07 +0000534 const MemRegion *ArrayR = ElemR->getSuperRegion();
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000535 SVal NewIdx;
536
537 if (OffI.isUnsigned() || OffI.getBitWidth() < BaseIdxI.getBitWidth()) {
538 // 'Offset' might be unsigned. We have to convert it to signed and
539 // possibly extend it.
540 llvm::APSInt Tmp = OffI;
541
542 if (OffI.getBitWidth() < BaseIdxI.getBitWidth())
543 Tmp.extend(BaseIdxI.getBitWidth());
544
545 Tmp.setIsSigned(true);
546 Tmp += BaseIdxI; // Compute the new offset.
Zhongxing Xud91ee272009-06-23 09:02:15 +0000547 NewIdx = ValMgr.makeIntVal(Tmp);
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000548 }
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000549 else
550 NewIdx = nonloc::ConcreteInt(getBasicVals().getValue(BaseIdxI + OffI));
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000551
Zhongxing Xu143b2fc2009-06-16 09:55:50 +0000552 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, NewIdx, ArrayR,
553 getContext()));
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000554}
555
Ted Kremenek9af46f52009-06-16 22:36:44 +0000556//===----------------------------------------------------------------------===//
557// Extents for regions.
558//===----------------------------------------------------------------------===//
559
Ted Kremenek67f28532009-06-17 22:02:04 +0000560SVal RegionStoreManager::getSizeInElements(const GRState *state,
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000561 const MemRegion* R) {
562 if (const VarRegion* VR = dyn_cast<VarRegion>(R)) {
563 // Get the type of the variable.
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000564 QualType T = VR->getDesugaredValueType(getContext());
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000565
Ted Kremenek14553ab2009-01-30 00:08:43 +0000566 // FIXME: Handle variable-length arrays.
567 if (isa<VariableArrayType>(T))
568 return UnknownVal();
569
570 if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(T)) {
571 // return the size as signed integer.
Zhongxing Xud91ee272009-06-23 09:02:15 +0000572 return ValMgr.makeIntVal(CAT->getSize(), false);
Ted Kremenek14553ab2009-01-30 00:08:43 +0000573 }
Zhongxing Xu20794942009-05-06 08:33:50 +0000574
Ted Kremenek67f28532009-06-17 22:02:04 +0000575 const QualType* CastTy = state->get<RegionCasts>(VR);
Zhongxing Xu41fd0182009-05-06 11:51:48 +0000576
Zhongxing Xue6536af2009-05-08 02:00:55 +0000577 // If the VarRegion is cast to other type, compute the size with respect to
578 // that type.
Zhongxing Xu41fd0182009-05-06 11:51:48 +0000579 if (CastTy) {
580 QualType EleTy =cast<PointerType>(CastTy->getTypePtr())->getPointeeType();
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000581 QualType VarTy = VR->getValueType(getContext());
Zhongxing Xue6536af2009-05-08 02:00:55 +0000582 uint64_t EleSize = getContext().getTypeSize(EleTy);
583 uint64_t VarSize = getContext().getTypeSize(VarTy);
Zhongxing Xu88c675f2009-06-18 06:29:10 +0000584 assert(VarSize != 0);
Zhongxing Xud91ee272009-06-23 09:02:15 +0000585 return ValMgr.makeIntVal(VarSize/EleSize, false);
Zhongxing Xu41fd0182009-05-06 11:51:48 +0000586 }
587
Ted Kremenek14553ab2009-01-30 00:08:43 +0000588 // Clients can use ordinary variables as if they were arrays. These
589 // essentially are arrays of size 1.
Zhongxing Xud91ee272009-06-23 09:02:15 +0000590 return ValMgr.makeIntVal(1, false);
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000591 }
592
593 if (const StringRegion* SR = dyn_cast<StringRegion>(R)) {
Zhongxing Xu6613d082008-11-24 02:18:56 +0000594 const StringLiteral* Str = SR->getStringLiteral();
Zhongxing Xud0fd3b72008-11-24 02:30:48 +0000595 // We intentionally made the size value signed because it participates in
596 // operations with signed indices.
Zhongxing Xud91ee272009-06-23 09:02:15 +0000597 return ValMgr.makeIntVal(Str->getByteLength()+1, false);
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000598 }
599
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000600 if (const FieldRegion* FR = dyn_cast<FieldRegion>(R)) {
601 // FIXME: Unsupported yet.
602 FR = 0;
603 return UnknownVal();
604 }
Zhongxing Xu369f4292008-11-22 13:23:00 +0000605
Zhongxing Xu02ebefb2009-02-06 08:51:30 +0000606 if (isa<SymbolicRegion>(R)) {
Zhongxing Xua48f7372009-02-06 08:44:27 +0000607 return UnknownVal();
608 }
609
Zhongxing Xuce760782009-05-09 13:20:07 +0000610 if (isa<AllocaRegion>(R)) {
611 return UnknownVal();
612 }
613
Zhongxing Xuccb16162009-05-06 08:08:27 +0000614 if (isa<ElementRegion>(R)) {
615 return UnknownVal();
616 }
617
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000618 assert(0 && "Other regions are not supported yet.");
Ted Kremeneka21362d2009-01-06 19:12:06 +0000619 return UnknownVal();
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000620}
621
Ted Kremenek67f28532009-06-17 22:02:04 +0000622const GRState *RegionStoreManager::setExtent(const GRState *state,
623 const MemRegion *region,
624 SVal extent) {
625 return state->set<RegionExtents>(region, extent);
Ted Kremenek9af46f52009-06-16 22:36:44 +0000626}
627
628//===----------------------------------------------------------------------===//
629// Location and region casting.
630//===----------------------------------------------------------------------===//
631
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000632/// ArrayToPointer - Emulates the "decay" of an array to a pointer
633/// type. 'Array' represents the lvalue of the array being decayed
634/// to a pointer, and the returned SVal represents the decayed
635/// version of that lvalue (i.e., a pointer to the first element of
636/// the array). This is called by GRExprEngine when evaluating casts
637/// from arrays to pointers.
Zhongxing Xuf1d537f2009-03-30 05:55:46 +0000638SVal RegionStoreManager::ArrayToPointer(Loc Array) {
Ted Kremenekabb042f2008-12-13 19:24:37 +0000639 if (!isa<loc::MemRegionVal>(Array))
640 return UnknownVal();
641
642 const MemRegion* R = cast<loc::MemRegionVal>(&Array)->getRegion();
643 const TypedRegion* ArrayR = dyn_cast<TypedRegion>(R);
644
Ted Kremenekbbee1a72009-01-13 01:03:27 +0000645 if (!ArrayR)
Ted Kremenekabb042f2008-12-13 19:24:37 +0000646 return UnknownVal();
647
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000648 // Strip off typedefs from the ArrayRegion's ValueType.
649 QualType T = ArrayR->getValueType(getContext())->getDesugaredType();
Ted Kremenekf936f452009-05-04 06:18:28 +0000650 ArrayType *AT = cast<ArrayType>(T);
651 T = AT->getElementType();
652
Zhongxing Xu63123d82008-11-23 04:30:35 +0000653 nonloc::ConcreteInt Idx(getBasicVals().getZeroWithPtrWidth(false));
Zhongxing Xu143b2fc2009-06-16 09:55:50 +0000654 ElementRegion* ER = MRMgr.getElementRegion(T, Idx, ArrayR, getContext());
Zhongxing Xu0b7e6422008-10-26 02:23:57 +0000655
656 return loc::MemRegionVal(ER);
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000657}
658
Zhongxing Xu88980592009-05-06 02:42:32 +0000659RegionStoreManager::CastResult
Ted Kremenek67f28532009-06-17 22:02:04 +0000660RegionStoreManager::CastRegion(const GRState *state, const MemRegion* R,
Zhongxing Xu41fd0182009-05-06 11:51:48 +0000661 QualType CastToTy) {
Zhongxing Xu88980592009-05-06 02:42:32 +0000662
663 ASTContext& Ctx = StateMgr.getContext();
664
665 // We need to know the real type of CastToTy.
666 QualType ToTy = Ctx.getCanonicalType(CastToTy);
667
668 // Check cast to ObjCQualifiedID type.
Steve Naroffd1b3c2d2009-06-17 22:40:22 +0000669 if (ToTy->isObjCQualifiedIdType()) {
Zhongxing Xu88980592009-05-06 02:42:32 +0000670 // FIXME: Record the type information aside.
671 return CastResult(state, R);
672 }
673
674 // CodeTextRegion should be cast to only function pointer type.
675 if (isa<CodeTextRegion>(R)) {
Zhongxing Xu99823a72009-06-22 08:36:10 +0000676 assert(CastToTy->isFunctionPointerType() || CastToTy->isBlockPointerType()
677 || (CastToTy->isPointerType()
678 && CastToTy->getAsPointerType()->getPointeeType()->isVoidType()));
Zhongxing Xu88980592009-05-06 02:42:32 +0000679 return CastResult(state, R);
680 }
681
Zhongxing Xudb3a0982009-05-09 10:03:08 +0000682 // Now assume we are casting from pointer to pointer. Other cases should
683 // already be handled.
Zhongxing Xu88980592009-05-06 02:42:32 +0000684 QualType PointeeTy = cast<PointerType>(ToTy.getTypePtr())->getPointeeType();
685
Zhongxing Xu88980592009-05-06 02:42:32 +0000686 // Process region cast according to the kind of the region being cast.
687
Zhongxing Xu88980592009-05-06 02:42:32 +0000688 // FIXME: Need to handle arbitrary downcasts.
Zhongxing Xu88980592009-05-06 02:42:32 +0000689 if (isa<SymbolicRegion>(R) || isa<AllocaRegion>(R)) {
Zhongxing Xuce760782009-05-09 13:20:07 +0000690 state = setCastType(state, R, ToTy);
691 return CastResult(state, R);
Zhongxing Xu88980592009-05-06 02:42:32 +0000692 }
693
694 // VarRegion, ElementRegion, and FieldRegion has an inherent type. Normally
695 // they should not be cast. We only layer an ElementRegion when the cast-to
696 // pointee type is of smaller size. In other cases, we return the original
697 // VarRegion.
698 if (isa<VarRegion>(R) || isa<ElementRegion>(R) || isa<FieldRegion>(R)
699 || isa<ObjCIvarRegion>(R) || isa<CompoundLiteralRegion>(R)) {
Zhongxing Xu2572eda2009-05-08 07:28:25 +0000700 // If the pointee type is incomplete, do not compute its size, and return
701 // the original region.
702 if (const RecordType *RT = dyn_cast<RecordType>(PointeeTy.getTypePtr())) {
703 const RecordDecl *D = RT->getDecl();
704 if (!D->getDefinition(getContext()))
705 return CastResult(state, R);
706 }
707
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000708 QualType ObjTy = cast<TypedRegion>(R)->getValueType(getContext());
Zhongxing Xufb1e3312009-05-08 02:12:59 +0000709 uint64_t PointeeTySize = getContext().getTypeSize(PointeeTy);
710 uint64_t ObjTySize = getContext().getTypeSize(ObjTy);
711
Zhongxing Xu5bf32872009-05-09 15:34:29 +0000712 if ((PointeeTySize > 0 && PointeeTySize < ObjTySize) ||
Zhongxing Xu88c675f2009-06-18 06:29:10 +0000713 (ObjTy->isAggregateType() && PointeeTy->isScalarType()) ||
714 ObjTySize == 0 /* R has 'void*' type. */) {
Zhongxing Xu20794942009-05-06 08:33:50 +0000715 // Record the cast type of the region.
716 state = setCastType(state, R, ToTy);
717
Zhongxing Xuccb16162009-05-06 08:08:27 +0000718 SVal Idx = ValMgr.makeZeroArrayIndex();
Zhongxing Xu143b2fc2009-06-16 09:55:50 +0000719 ElementRegion* ER = MRMgr.getElementRegion(PointeeTy, Idx,R,getContext());
Zhongxing Xuccb16162009-05-06 08:08:27 +0000720 return CastResult(state, ER);
Zhongxing Xu88c675f2009-06-18 06:29:10 +0000721 } else {
722 state = setCastType(state, R, ToTy);
Zhongxing Xuccb16162009-05-06 08:08:27 +0000723 return CastResult(state, R);
Zhongxing Xu88c675f2009-06-18 06:29:10 +0000724 }
Zhongxing Xu88980592009-05-06 02:42:32 +0000725 }
726
Zhongxing Xu88980592009-05-06 02:42:32 +0000727 if (isa<ObjCObjectRegion>(R)) {
728 return CastResult(state, R);
729 }
730
731 assert(0 && "Unprocessed region.");
Daniel Dunbar4e609002009-05-18 16:48:48 +0000732 return 0;
Zhongxing Xu88980592009-05-06 02:42:32 +0000733}
734
Ted Kremenek9af46f52009-06-16 22:36:44 +0000735//===----------------------------------------------------------------------===//
736// Pointer arithmetic.
737//===----------------------------------------------------------------------===//
738
Zhongxing Xu262fd032009-05-20 09:00:16 +0000739SVal RegionStoreManager::EvalBinOp(const GRState *state,
740 BinaryOperator::Opcode Op, Loc L, NonLoc R) {
Zhongxing Xuc4761f52009-05-09 15:18:12 +0000741 // Assume the base location is MemRegionVal.
Ted Kremenek5dc27462009-03-03 02:51:43 +0000742 if (!isa<loc::MemRegionVal>(L))
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000743 return UnknownVal();
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000744
Zhongxing Xua1718c72009-04-03 07:33:13 +0000745 const MemRegion* MR = cast<loc::MemRegionVal>(L).getRegion();
Zhongxing Xuc4761f52009-05-09 15:18:12 +0000746 const ElementRegion *ER = 0;
Zhongxing Xu262fd032009-05-20 09:00:16 +0000747
748 // If the operand is a symbolic or alloca region, create the first element
749 // region on it.
Zhongxing Xuc4761f52009-05-09 15:18:12 +0000750 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR)) {
Zhongxing Xu005f07b2009-06-19 04:51:14 +0000751 QualType T;
752 // If the SymbolicRegion was cast to another type, use that type.
753 if (const QualType *t = state->get<RegionCasts>(SR)) {
754 T = *t;
755 } else {
756 // Otherwise use the symbol's type.
757 SymbolRef Sym = SR->getSymbol();
758 T = Sym->getType(getContext());
759 }
Zhongxing Xu53454dc2009-06-12 03:59:12 +0000760 QualType EleTy = T->getAsPointerType()->getPointeeType();
Zhongxing Xua1718c72009-04-03 07:33:13 +0000761
Zhongxing Xuc4761f52009-05-09 15:18:12 +0000762 SVal ZeroIdx = ValMgr.makeZeroArrayIndex();
Zhongxing Xu143b2fc2009-06-16 09:55:50 +0000763 ER = MRMgr.getElementRegion(EleTy, ZeroIdx, SR, getContext());
Zhongxing Xu262fd032009-05-20 09:00:16 +0000764 }
765 else if (const AllocaRegion *AR = dyn_cast<AllocaRegion>(MR)) {
766 // Get the alloca region's current cast type.
Zhongxing Xu262fd032009-05-20 09:00:16 +0000767
Ted Kremenek67f28532009-06-17 22:02:04 +0000768
769 GRStateTrait<RegionCasts>::lookup_type T = state->get<RegionCasts>(AR);
Zhongxing Xu262fd032009-05-20 09:00:16 +0000770 assert(T && "alloca region has no type.");
771 QualType EleTy = cast<PointerType>(T->getTypePtr())->getPointeeType();
772 SVal ZeroIdx = ValMgr.makeZeroArrayIndex();
Zhongxing Xu143b2fc2009-06-16 09:55:50 +0000773 ER = MRMgr.getElementRegion(EleTy, ZeroIdx, AR, getContext());
Zhongxing Xu262fd032009-05-20 09:00:16 +0000774 }
Zhongxing Xu5414a5c2009-06-21 13:24:24 +0000775 else if (isa<FieldRegion>(MR)) {
776 // Not track pointer arithmetic on struct fields.
777 return UnknownVal();
778 }
779 else {
Zhongxing Xuc4761f52009-05-09 15:18:12 +0000780 ER = cast<ElementRegion>(MR);
Zhongxing Xu5414a5c2009-06-21 13:24:24 +0000781 }
Zhongxing Xu2b1dc172009-03-11 07:43:49 +0000782
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000783 SVal Idx = ER->getIndex();
784
785 nonloc::ConcreteInt* Base = dyn_cast<nonloc::ConcreteInt>(&Idx);
786 nonloc::ConcreteInt* Offset = dyn_cast<nonloc::ConcreteInt>(&R);
787
788 // Only support concrete integer indexes for now.
789 if (Base && Offset) {
Ted Kremenek610e81d2009-03-13 15:35:24 +0000790 // FIXME: For now, convert the signedness and bitwidth of offset in case
791 // they don't match. This can result from pointer arithmetic. In reality,
792 // we should figure out what are the proper semantics and implement them.
793 //
Ted Kremenek1060a3c2009-03-13 15:39:16 +0000794 // This addresses the test case test/Analysis/ptr-arith.c
795 //
Ted Kremenek610e81d2009-03-13 15:35:24 +0000796 nonloc::ConcreteInt OffConverted(getBasicVals().Convert(Base->getValue(),
797 Offset->getValue()));
798 SVal NewIdx = Base->EvalBinOp(getBasicVals(), Op, OffConverted);
Ted Kremenekf936f452009-05-04 06:18:28 +0000799 const MemRegion* NewER =
Zhongxing Xu143b2fc2009-06-16 09:55:50 +0000800 MRMgr.getElementRegion(ER->getElementType(), NewIdx,ER->getSuperRegion(),
801 getContext());
Zhongxing Xud91ee272009-06-23 09:02:15 +0000802 return ValMgr.makeLoc(NewER);
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000803
Ted Kremenek5dc27462009-03-03 02:51:43 +0000804 }
805
806 return UnknownVal();
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000807}
808
Ted Kremenek9af46f52009-06-16 22:36:44 +0000809//===----------------------------------------------------------------------===//
810// Loading values from regions.
811//===----------------------------------------------------------------------===//
812
Ted Kremenek67f28532009-06-17 22:02:04 +0000813SVal RegionStoreManager::Retrieve(const GRState *state, Loc L, QualType T) {
814
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000815 assert(!isa<UnknownVal>(L) && "location unknown");
816 assert(!isa<UndefinedVal>(L) && "location undefined");
817
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000818 // FIXME: Is this even possible? Shouldn't this be treated as a null
819 // dereference at a higher level?
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000820 if (isa<loc::ConcreteInt>(L))
821 return UndefinedVal();
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000822
Ted Kremenek67f28532009-06-17 22:02:04 +0000823 const MemRegion *MR = cast<loc::MemRegionVal>(L).getRegion();
Zhongxing Xua1718c72009-04-03 07:33:13 +0000824
Zhongxing Xu91844122009-05-20 09:18:48 +0000825 // FIXME: return symbolic value for these cases.
Zhongxing Xua1718c72009-04-03 07:33:13 +0000826 // Example:
827 // void f(int* p) { int x = *p; }
Zhongxing Xu91844122009-05-20 09:18:48 +0000828 // char* p = alloca();
829 // read(p);
830 // c = *p;
831 if (isa<SymbolicRegion>(MR) || isa<AllocaRegion>(MR))
Zhongxing Xua1718c72009-04-03 07:33:13 +0000832 return UnknownVal();
833
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000834 // FIXME: Perhaps this method should just take a 'const MemRegion*' argument
835 // instead of 'Loc', and have the other Loc cases handled at a higher level.
Ted Kremenek67f28532009-06-17 22:02:04 +0000836 const TypedRegion *R = cast<TypedRegion>(MR);
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000837 assert(R && "bad region");
838
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000839 // FIXME: We should eventually handle funny addressing. e.g.:
840 //
841 // int x = ...;
842 // int *p = &x;
843 // char *q = (char*) p;
844 // char c = *q; // returns the first byte of 'x'.
845 //
846 // Such funny addressing will occur due to layering of regions.
847
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000848 QualType RTy = R->getValueType(getContext());
Zhongxing Xu3e001f32009-05-03 00:27:40 +0000849
Zhongxing Xu1038f9f2009-03-09 09:15:51 +0000850 if (RTy->isStructureType())
Ted Kremenek67f28532009-06-17 22:02:04 +0000851 return RetrieveStruct(state, R);
Zhongxing Xu3e001f32009-05-03 00:27:40 +0000852
853 if (RTy->isArrayType())
Ted Kremenek67f28532009-06-17 22:02:04 +0000854 return RetrieveArray(state, R);
Zhongxing Xu3e001f32009-05-03 00:27:40 +0000855
Zhongxing Xu1038f9f2009-03-09 09:15:51 +0000856 // FIXME: handle Vector types.
857 if (RTy->isVectorType())
Ted Kremenek265a3052009-02-24 02:23:11 +0000858 return UnknownVal();
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000859
Ted Kremenek67f28532009-06-17 22:02:04 +0000860 RegionBindingsTy B = GetRegionBindings(state->getStore());
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000861 RegionBindingsTy::data_type* V = B.lookup(R);
862
863 // Check if the region has a binding.
864 if (V)
865 return *V;
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000866
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000867 // Check if the region is in killset.
Ted Kremenek67f28532009-06-17 22:02:04 +0000868 if (state->contains<RegionKills>(R))
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000869 return UnknownVal();
870
Zhongxing Xuc87d5fb2009-05-11 14:23:36 +0000871 // Check if the region is an element region of a string literal.
872 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
873 if (const StringRegion *StrR=dyn_cast<StringRegion>(ER->getSuperRegion())) {
874 const StringLiteral *Str = StrR->getStringLiteral();
875 SVal Idx = ER->getIndex();
876 if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&Idx)) {
877 int64_t i = CI->getValue().getSExtValue();
878 char c;
879 if (i == Str->getByteLength())
880 c = '\0';
881 else
882 c = Str->getStrData()[i];
883 const llvm::APSInt &V = getBasicVals().getValue(c, getContext().CharTy);
884 return nonloc::ConcreteInt(V);
885 }
886 }
887 }
888
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000889 // If the region is an element or field, it may have a default value.
Zhongxing Xu562c4d92009-01-23 11:22:12 +0000890 if (isa<ElementRegion>(R) || isa<FieldRegion>(R)) {
891 const MemRegion* SuperR = cast<SubRegion>(R)->getSuperRegion();
Zhongxing Xue8ab9ea2009-06-24 01:12:41 +0000892 const SVal* D = state->get<RegionDefaultValue>(SuperR);
Zhongxing Xu264e9372009-05-12 10:10:00 +0000893 if (D) {
894 // If the default value is symbolic, we need to create a new symbol.
895 if (D->hasConjuredSymbol())
896 return ValMgr.getRegionValueSymbolVal(R);
897 else
898 return *D;
899 }
Zhongxing Xu562c4d92009-01-23 11:22:12 +0000900 }
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000901
902 if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) {
903 const MemRegion *SR = IVR->getSuperRegion();
904
905 // If the super region is 'self' then return the symbol representing
906 // the value of the ivar upon entry to the method.
907 if (SR == SelfRegion) {
908 // FIXME: Do we need to handle the case where the super region
909 // has a view? We want to canonicalize the bindings.
Zhongxing Xud9b6ad62009-05-09 04:08:27 +0000910 return ValMgr.getRegionValueSymbolVal(R);
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000911 }
912
913 // Otherwise, we need a new symbol. For now return Unknown.
914 return UnknownVal();
915 }
Zhongxing Xu562c4d92009-01-23 11:22:12 +0000916
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000917 // The location does not have a bound value. This means that it has
918 // the value it had upon its creation and/or entry to the analyzed
919 // function/method. These are either symbolic values or 'undefined'.
920
921 // We treat function parameters as symbolic values.
Ted Kremenek6fd8f912009-01-22 23:43:57 +0000922 if (const VarRegion* VR = dyn_cast<VarRegion>(R)) {
923 const VarDecl *VD = VR->getDecl();
924
Ted Kremenekcec35252009-03-04 00:23:05 +0000925 if (VD == SelfDecl)
926 return loc::MemRegionVal(getSelfRegion(0));
927
928 if (isa<ParmVarDecl>(VD) || isa<ImplicitParamDecl>(VD) ||
929 VD->hasGlobalStorage()) {
Zhongxing Xud8895f62009-02-19 09:56:08 +0000930 QualType VTy = VD->getType();
931 if (Loc::IsLocType(VTy) || VTy->isIntegerType())
Zhongxing Xud9b6ad62009-05-09 04:08:27 +0000932 return ValMgr.getRegionValueSymbolVal(VR);
Zhongxing Xud8895f62009-02-19 09:56:08 +0000933 else
934 return UnknownVal();
935 }
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000936 }
Ted Kremenek265a3052009-02-24 02:23:11 +0000937
Ted Kremenekbb7c96f2009-06-23 18:17:08 +0000938 if (R->hasHeapOrStackStorage()) {
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000939 // All stack variables are considered to have undefined values
940 // upon creation. All heap allocated blocks are considered to
941 // have undefined values as well unless they are explicitly bound
942 // to specific values.
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000943 return UndefinedVal();
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000944 }
945
Zhongxing Xu88c675f2009-06-18 06:29:10 +0000946 // If the region is already cast to another type, use that type to create the
947 // symbol value.
948 if (const QualType *p = state->get<RegionCasts>(R)) {
949 QualType T = *p;
950 RTy = T->getAsPointerType()->getPointeeType();
951 }
952
Zhongxing Xuff8d2042009-03-09 09:31:22 +0000953 // All other integer values are symbolic.
954 if (Loc::IsLocType(RTy) || RTy->isIntegerType())
Zhongxing Xu88c675f2009-06-18 06:29:10 +0000955 return ValMgr.getRegionValueSymbolVal(R, RTy);
Zhongxing Xuff8d2042009-03-09 09:31:22 +0000956 else
957 return UnknownVal();
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000958}
959
Zhongxing Xu88c675f2009-06-18 06:29:10 +0000960SVal RegionStoreManager::RetrieveStruct(const GRState *state,
961 const TypedRegion* R){
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000962 QualType T = R->getValueType(getContext());
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000963 assert(T->isStructureType());
964
Zhongxing Xub7507d12009-06-11 07:27:30 +0000965 const RecordType* RT = T->getAsStructureType();
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000966 RecordDecl* RD = RT->getDecl();
967 assert(RD->isDefinition());
968
969 llvm::ImmutableList<SVal> StructVal = getBasicVals().getEmptySValList();
970
Ted Kremenek67f28532009-06-17 22:02:04 +0000971 // FIXME: We shouldn't use a std::vector. If RecordDecl doesn't have a
972 // reverse iterator, we should implement one.
Douglas Gregor6ab35242009-04-09 21:40:53 +0000973 std::vector<FieldDecl *> Fields(RD->field_begin(getContext()),
974 RD->field_end(getContext()));
Douglas Gregor44b43212008-12-11 16:49:14 +0000975
Douglas Gregore267ff32008-12-11 20:41:00 +0000976 for (std::vector<FieldDecl *>::reverse_iterator Field = Fields.rbegin(),
977 FieldEnd = Fields.rend();
978 Field != FieldEnd; ++Field) {
979 FieldRegion* FR = MRMgr.getFieldRegion(*Field, R);
Zhongxing Xu3e001f32009-05-03 00:27:40 +0000980 QualType FTy = (*Field)->getType();
Ted Kremenek67f28532009-06-17 22:02:04 +0000981 SVal FieldValue = Retrieve(state, loc::MemRegionVal(FR), FTy);
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000982 StructVal = getBasicVals().consVals(FieldValue, StructVal);
983 }
984
Zhongxing Xud91ee272009-06-23 09:02:15 +0000985 return ValMgr.makeCompoundVal(T, StructVal);
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000986}
987
Ted Kremenek67f28532009-06-17 22:02:04 +0000988SVal RegionStoreManager::RetrieveArray(const GRState *state,
989 const TypedRegion * R) {
990
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000991 QualType T = R->getValueType(getContext());
Zhongxing Xu3e001f32009-05-03 00:27:40 +0000992 ConstantArrayType* CAT = cast<ConstantArrayType>(T.getTypePtr());
993
994 llvm::ImmutableList<SVal> ArrayVal = getBasicVals().getEmptySValList();
Zhongxing Xu3e001f32009-05-03 00:27:40 +0000995 llvm::APSInt Size(CAT->getSize(), false);
Zhongxing Xu2ee52142009-05-11 12:48:56 +0000996 llvm::APSInt i = getBasicVals().getZeroWithPtrWidth(false);
Zhongxing Xu3e001f32009-05-03 00:27:40 +0000997
998 for (; i < Size; ++i) {
Zhongxing Xud91ee272009-06-23 09:02:15 +0000999 SVal Idx = ValMgr.makeIntVal(i);
Zhongxing Xu143b2fc2009-06-16 09:55:50 +00001000 ElementRegion* ER = MRMgr.getElementRegion(CAT->getElementType(), Idx, R,
1001 getContext());
Ted Kremenekf936f452009-05-04 06:18:28 +00001002 QualType ETy = ER->getElementType();
Ted Kremenek67f28532009-06-17 22:02:04 +00001003 SVal ElementVal = Retrieve(state, loc::MemRegionVal(ER), ETy);
Zhongxing Xu3e001f32009-05-03 00:27:40 +00001004 ArrayVal = getBasicVals().consVals(ElementVal, ArrayVal);
1005 }
1006
Zhongxing Xud91ee272009-06-23 09:02:15 +00001007 return ValMgr.makeCompoundVal(T, ArrayVal);
Zhongxing Xu3e001f32009-05-03 00:27:40 +00001008}
1009
Ted Kremenek9af46f52009-06-16 22:36:44 +00001010//===----------------------------------------------------------------------===//
1011// Binding values to regions.
1012//===----------------------------------------------------------------------===//
Zhongxing Xu17892752008-10-08 02:50:44 +00001013
Zhongxing Xu9c9ca082008-12-16 02:36:30 +00001014Store RegionStoreManager::Remove(Store store, Loc L) {
Ted Kremenek0964a062009-01-21 06:57:53 +00001015 const MemRegion* R = 0;
1016
1017 if (isa<loc::MemRegionVal>(L))
1018 R = cast<loc::MemRegionVal>(L).getRegion();
Ted Kremenek0964a062009-01-21 06:57:53 +00001019
1020 if (R) {
1021 RegionBindingsTy B = GetRegionBindings(store);
1022 return RBFactory.Remove(B, R).getRoot();
1023 }
1024
1025 return store;
Zhongxing Xu9c9ca082008-12-16 02:36:30 +00001026}
1027
Ted Kremenek67f28532009-06-17 22:02:04 +00001028const GRState *RegionStoreManager::Bind(const GRState *state, Loc L, SVal V) {
Ted Kremenek9af46f52009-06-16 22:36:44 +00001029 // If we get here, the location should be a region.
1030 const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion();
Ted Kremenek9af46f52009-06-16 22:36:44 +00001031
1032 // Check if the region is a struct region.
1033 if (const TypedRegion* TR = dyn_cast<TypedRegion>(R))
1034 if (TR->getValueType(getContext())->isStructureType())
Ted Kremenek67f28532009-06-17 22:02:04 +00001035 return BindStruct(state, TR, V);
Ted Kremenek9af46f52009-06-16 22:36:44 +00001036
Ted Kremenek67f28532009-06-17 22:02:04 +00001037 RegionBindingsTy B = GetRegionBindings(state->getStore());
Ted Kremenek9af46f52009-06-16 22:36:44 +00001038
1039 if (V.isUnknown()) {
Ted Kremenek67f28532009-06-17 22:02:04 +00001040 B = RBFactory.Remove(B, R); // Remove the binding.
1041 state = state->add<RegionKills>(R); // Add the region to the killset.
Ted Kremenek9af46f52009-06-16 22:36:44 +00001042 }
1043 else
Ted Kremenek67f28532009-06-17 22:02:04 +00001044 B = RBFactory.Add(B, R, V);
Ted Kremenek9af46f52009-06-16 22:36:44 +00001045
Ted Kremenek67f28532009-06-17 22:02:04 +00001046 return state->makeWithStore(B.getRoot());
Ted Kremenek9af46f52009-06-16 22:36:44 +00001047}
1048
Ted Kremenek67f28532009-06-17 22:02:04 +00001049const GRState *RegionStoreManager::BindDecl(const GRState *state,
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001050 const VarDecl* VD, SVal InitVal) {
Zhongxing Xua4f28ff2008-11-13 08:41:36 +00001051
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001052 QualType T = VD->getType();
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001053 VarRegion* VR = MRMgr.getVarRegion(VD);
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +00001054
Ted Kremenek0964a062009-01-21 06:57:53 +00001055 if (T->isArrayType())
Ted Kremenek67f28532009-06-17 22:02:04 +00001056 return BindArray(state, VR, InitVal);
Ted Kremenek0964a062009-01-21 06:57:53 +00001057 if (T->isStructureType())
Ted Kremenek67f28532009-06-17 22:02:04 +00001058 return BindStruct(state, VR, InitVal);
Zhongxing Xud463d442008-11-02 12:13:30 +00001059
Zhongxing Xud91ee272009-06-23 09:02:15 +00001060 return Bind(state, ValMgr.makeLoc(VR), InitVal);
Zhongxing Xu17892752008-10-08 02:50:44 +00001061}
Zhongxing Xu53bcdd42008-10-21 05:29:26 +00001062
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001063// FIXME: this method should be merged into Bind().
Ted Kremenek67f28532009-06-17 22:02:04 +00001064const GRState *
1065RegionStoreManager::BindCompoundLiteral(const GRState *state,
1066 const CompoundLiteralExpr* CL,
1067 SVal V) {
1068
Zhongxing Xuf22679e2008-11-07 10:38:33 +00001069 CompoundLiteralRegion* R = MRMgr.getCompoundLiteralRegion(CL);
Ted Kremenek67f28532009-06-17 22:02:04 +00001070 return Bind(state, loc::MemRegionVal(R), V);
Zhongxing Xuf22679e2008-11-07 10:38:33 +00001071}
1072
Ted Kremenek67f28532009-06-17 22:02:04 +00001073const GRState *RegionStoreManager::BindArray(const GRState *state,
1074 const TypedRegion* R,
1075 SVal Init) {
1076
Zhongxing Xua82d8aa2009-05-09 03:57:34 +00001077 QualType T = R->getValueType(getContext());
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001078 ConstantArrayType* CAT = cast<ConstantArrayType>(T.getTypePtr());
Zhongxing Xu087d6c22009-06-23 05:23:38 +00001079 QualType ElementTy = CAT->getElementType();
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001080
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001081 llvm::APSInt Size(CAT->getSize(), false);
Zhongxing Xu087d6c22009-06-23 05:23:38 +00001082 llvm::APSInt i(llvm::APInt::getNullValue(Size.getBitWidth()), false);
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001083
1084 // Check if the init expr is a StringLiteral.
1085 if (isa<loc::MemRegionVal>(Init)) {
1086 const MemRegion* InitR = cast<loc::MemRegionVal>(Init).getRegion();
1087 const StringLiteral* S = cast<StringRegion>(InitR)->getStringLiteral();
1088 const char* str = S->getStrData();
1089 unsigned len = S->getByteLength();
1090 unsigned j = 0;
1091
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001092 // Copy bytes from the string literal into the target array. Trailing bytes
1093 // in the array that are not covered by the string literal are initialized
1094 // to zero.
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001095 for (; i < Size; ++i, ++j) {
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001096 if (j >= len)
1097 break;
1098
Zhongxing Xu3038c5a2009-06-23 06:13:19 +00001099 SVal Idx = ValMgr.makeIntVal(i);
Zhongxing Xu087d6c22009-06-23 05:23:38 +00001100 ElementRegion* ER = MRMgr.getElementRegion(ElementTy, Idx,R,getContext());
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001101
Zhongxing Xud91ee272009-06-23 09:02:15 +00001102 SVal V = ValMgr.makeIntVal(str[j], sizeof(char)*8, true);
Ted Kremenek67f28532009-06-17 22:02:04 +00001103 state = Bind(state, loc::MemRegionVal(ER), V);
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001104 }
1105
Ted Kremenek67f28532009-06-17 22:02:04 +00001106 return state;
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001107 }
1108
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001109 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(Init);
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001110 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
1111
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001112 for (; i < Size; ++i, ++VI) {
Zhongxing Xu087d6c22009-06-23 05:23:38 +00001113 // The init list might be shorter than the array length.
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001114 if (VI == VE)
1115 break;
1116
Zhongxing Xu3038c5a2009-06-23 06:13:19 +00001117 SVal Idx = ValMgr.makeIntVal(i);
Zhongxing Xu087d6c22009-06-23 05:23:38 +00001118 ElementRegion* ER = MRMgr.getElementRegion(ElementTy, Idx, R, getContext());
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001119
1120 if (CAT->getElementType()->isStructureType())
Ted Kremenek67f28532009-06-17 22:02:04 +00001121 state = BindStruct(state, ER, *VI);
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001122 else
Zhongxing Xud91ee272009-06-23 09:02:15 +00001123 state = Bind(state, ValMgr.makeLoc(ER), *VI);
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001124 }
1125
Zhongxing Xue3a765f2009-06-24 00:56:31 +00001126 // If the init list is shorter than the array length, set the array default
1127 // value.
1128 if (i < Size) {
1129 if (ElementTy->isIntegerType()) {
Zhongxing Xu087d6c22009-06-23 05:23:38 +00001130 SVal V = ValMgr.makeZeroVal(ElementTy);
Zhongxing Xue3a765f2009-06-24 00:56:31 +00001131 state = setDefaultValue(state, R, V);
Zhongxing Xu087d6c22009-06-23 05:23:38 +00001132 }
1133 }
1134
Ted Kremenek67f28532009-06-17 22:02:04 +00001135 return state;
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001136}
1137
Ted Kremenek67f28532009-06-17 22:02:04 +00001138const GRState *
1139RegionStoreManager::BindStruct(const GRState *state, const TypedRegion* R,
1140 SVal V) {
1141
1142 if (!Features.supportsFields())
1143 return state;
1144
Zhongxing Xua82d8aa2009-05-09 03:57:34 +00001145 QualType T = R->getValueType(getContext());
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001146 assert(T->isStructureType());
1147
Zhongxing Xub13ecdb2009-03-12 03:45:35 +00001148 const RecordType* RT = T->getAsRecordType();
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001149 RecordDecl* RD = RT->getDecl();
Zhongxing Xuc45a8252009-03-11 09:07:35 +00001150
1151 if (!RD->isDefinition())
Ted Kremenek67f28532009-06-17 22:02:04 +00001152 return state;
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001153
Ted Kremenek67f28532009-06-17 22:02:04 +00001154 // We may get non-CompoundVal accidentally due to imprecise cast logic.
1155 // Ignore them and kill the field values.
1156 if (V.isUnknown() || !isa<nonloc::CompoundVal>(V))
1157 return KillStruct(state, R);
Zhongxing Xu3f6978a2009-06-11 09:11:27 +00001158
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001159 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V);
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001160 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
Zhongxing Xudbdf2192009-06-23 05:43:16 +00001161
1162 RecordDecl::field_iterator FI, FE;
1163
1164 for (FI = RD->field_begin(getContext()), FE = RD->field_end(getContext());
Ted Kremenek67f28532009-06-17 22:02:04 +00001165 FI != FE; ++FI, ++VI) {
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001166
Zhongxing Xudbdf2192009-06-23 05:43:16 +00001167 if (VI == VE)
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001168 break;
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001169
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001170 QualType FTy = (*FI)->getType();
1171 FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);
1172
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001173 if (Loc::IsLocType(FTy) || FTy->isIntegerType())
Zhongxing Xud91ee272009-06-23 09:02:15 +00001174 state = Bind(state, ValMgr.makeLoc(FR), *VI);
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001175 else if (FTy->isArrayType())
Ted Kremenek67f28532009-06-17 22:02:04 +00001176 state = BindArray(state, FR, *VI);
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001177 else if (FTy->isStructureType())
Ted Kremenek67f28532009-06-17 22:02:04 +00001178 state = BindStruct(state, FR, *VI);
Zhongxing Xua82512a2008-10-24 08:42:28 +00001179 }
1180
Zhongxing Xudbdf2192009-06-23 05:43:16 +00001181 // There may be fewer values in the initialize list than the fields of struct.
1182 while (FI != FE) {
1183 QualType FTy = (*FI)->getType();
1184 if (FTy->isIntegerType()) {
1185 FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);
Zhongxing Xud91ee272009-06-23 09:02:15 +00001186 state = Bind(state, ValMgr.makeLoc(FR), ValMgr.makeZeroVal(FTy));
Zhongxing Xudbdf2192009-06-23 05:43:16 +00001187 }
1188
1189 ++FI;
1190 }
1191
Ted Kremenek67f28532009-06-17 22:02:04 +00001192 return state;
Zhongxing Xuc3a05992008-11-19 11:06:24 +00001193}
1194
Ted Kremenek67f28532009-06-17 22:02:04 +00001195const GRState *RegionStoreManager::KillStruct(const GRState *state,
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001196 const TypedRegion* R){
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001197
Ted Kremenek67f28532009-06-17 22:02:04 +00001198 // (1) Kill the struct region because it is assigned "unknown".
1199 // (2) Set the default value of the struct region to "unknown".
1200 state = state->add<RegionKills>(R)->set<RegionDefaultValue>(R, UnknownVal());
1201 Store store = state->getStore();
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001202 RegionBindingsTy B = GetRegionBindings(store);
1203
1204 // Remove all bindings for the subregions of the struct.
1205 for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
Ted Kremenek67f28532009-06-17 22:02:04 +00001206 const MemRegion* R = I.getKey();
1207 if (const SubRegion* subRegion = dyn_cast<SubRegion>(R))
1208 if (subRegion->isSubRegionOf(R))
Zhongxing Xud91ee272009-06-23 09:02:15 +00001209 store = Remove(store, ValMgr.makeLoc(subRegion));
Zhongxing Xu9c2a3db2009-01-13 03:07:41 +00001210 // FIXME: Maybe we should also remove the bindings for the "views" of the
1211 // subregions.
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001212 }
1213
Ted Kremenek67f28532009-06-17 22:02:04 +00001214 return state->makeWithStore(store);
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001215}
1216
Ted Kremenek9af46f52009-06-16 22:36:44 +00001217//===----------------------------------------------------------------------===//
1218// Region views.
1219//===----------------------------------------------------------------------===//
1220
Ted Kremenek67f28532009-06-17 22:02:04 +00001221const GRState *RegionStoreManager::AddRegionView(const GRState *state,
1222 const MemRegion* View,
1223 const MemRegion* Base) {
Zhongxing Xudc0a25d2008-11-16 04:07:26 +00001224
1225 // First, retrieve the region view of the base region.
Ted Kremenek67f28532009-06-17 22:02:04 +00001226 const RegionViews* d = state->get<RegionViewMap>(Base);
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001227 RegionViews L = d ? *d : RVFactory.GetEmptySet();
Zhongxing Xudc0a25d2008-11-16 04:07:26 +00001228
1229 // Now add View to the region view.
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001230 L = RVFactory.Add(L, View);
Zhongxing Xudc0a25d2008-11-16 04:07:26 +00001231
1232 // Create a new state with the new region view.
Ted Kremenek67f28532009-06-17 22:02:04 +00001233 return state->set<RegionViewMap>(Base, L);
Zhongxing Xudc0a25d2008-11-16 04:07:26 +00001234}
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001235
Ted Kremenek67f28532009-06-17 22:02:04 +00001236const GRState *RegionStoreManager::RemoveRegionView(const GRState *state,
1237 const MemRegion* View,
1238 const MemRegion* Base) {
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001239 // Retrieve the region view of the base region.
Ted Kremenek67f28532009-06-17 22:02:04 +00001240 const RegionViews* d = state->get<RegionViewMap>(Base);
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001241
1242 // If the base region has no view, return.
1243 if (!d)
Ted Kremenek67f28532009-06-17 22:02:04 +00001244 return state;
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001245
1246 // Remove the view.
Ted Kremenek67f28532009-06-17 22:02:04 +00001247 return state->set<RegionViewMap>(Base, RVFactory.Remove(*d, View));
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001248}
Zhongxing Xu20794942009-05-06 08:33:50 +00001249
Zhongxing Xu88c675f2009-06-18 06:29:10 +00001250const GRState *RegionStoreManager::setCastType(const GRState *state,
1251 const MemRegion* R, QualType T) {
Ted Kremenek67f28532009-06-17 22:02:04 +00001252 return state->set<RegionCasts>(R, T);
Zhongxing Xu20794942009-05-06 08:33:50 +00001253}
Zhongxing Xu264e9372009-05-12 10:10:00 +00001254
Ted Kremenek67f28532009-06-17 22:02:04 +00001255const GRState *RegionStoreManager::setDefaultValue(const GRState *state,
1256 const MemRegion* R, SVal V) {
1257 return state->set<RegionDefaultValue>(R, V);
Zhongxing Xu264e9372009-05-12 10:10:00 +00001258}
Ted Kremenek9af46f52009-06-16 22:36:44 +00001259
1260//===----------------------------------------------------------------------===//
1261// State pruning.
1262//===----------------------------------------------------------------------===//
1263
1264static void UpdateLiveSymbols(SVal X, SymbolReaper& SymReaper) {
1265 if (loc::MemRegionVal *XR = dyn_cast<loc::MemRegionVal>(&X)) {
1266 const MemRegion *R = XR->getRegion();
1267
1268 while (R) {
1269 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) {
1270 SymReaper.markLive(SR->getSymbol());
1271 return;
1272 }
1273
1274 if (const SubRegion *SR = dyn_cast<SubRegion>(R)) {
1275 R = SR->getSuperRegion();
1276 continue;
1277 }
1278
1279 break;
1280 }
1281
1282 return;
1283 }
1284
1285 for (SVal::symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end();SI!=SE;++SI)
1286 SymReaper.markLive(*SI);
1287}
1288
Ted Kremenek67f28532009-06-17 22:02:04 +00001289Store RegionStoreManager::RemoveDeadBindings(const GRState *state, Stmt* Loc,
Ted Kremenek9af46f52009-06-16 22:36:44 +00001290 SymbolReaper& SymReaper,
1291 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots)
Ted Kremenek67f28532009-06-17 22:02:04 +00001292{
Ted Kremenek9af46f52009-06-16 22:36:44 +00001293 Store store = state->getStore();
1294 RegionBindingsTy B = GetRegionBindings(store);
1295
1296 // Lazily constructed backmap from MemRegions to SubRegions.
1297 typedef llvm::ImmutableSet<const MemRegion*> SubRegionsTy;
1298 typedef llvm::ImmutableMap<const MemRegion*, SubRegionsTy> SubRegionsMapTy;
1299
1300 // FIXME: As a future optimization we can modifiy BumpPtrAllocator to have
1301 // the ability to reuse memory. This way we can keep TmpAlloc around as
1302 // an instance variable of RegionStoreManager (avoiding repeated malloc
1303 // overhead).
1304 llvm::BumpPtrAllocator TmpAlloc;
1305
1306 // Factory objects.
1307 SubRegionsMapTy::Factory SubRegMapF(TmpAlloc);
1308 SubRegionsTy::Factory SubRegF(TmpAlloc);
1309
1310 // The backmap from regions to subregions.
1311 SubRegionsMapTy SubRegMap = SubRegMapF.GetEmptyMap();
1312
1313 // Do a pass over the regions in the store. For VarRegions we check if
1314 // the variable is still live and if so add it to the list of live roots.
Ted Kremenek67f28532009-06-17 22:02:04 +00001315 // For other regions we populate our region backmap.
Ted Kremenek9af46f52009-06-16 22:36:44 +00001316 llvm::SmallVector<const MemRegion*, 10> IntermediateRoots;
1317
1318 for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
1319 IntermediateRoots.push_back(I.getKey());
1320 }
1321
1322 while (!IntermediateRoots.empty()) {
1323 const MemRegion* R = IntermediateRoots.back();
1324 IntermediateRoots.pop_back();
1325
1326 if (const VarRegion* VR = dyn_cast<VarRegion>(R)) {
1327 if (SymReaper.isLive(Loc, VR->getDecl()))
1328 RegionRoots.push_back(VR); // This is a live "root".
1329 }
1330 else if (const SymbolicRegion* SR = dyn_cast<SymbolicRegion>(R)) {
1331 if (SymReaper.isLive(SR->getSymbol()))
1332 RegionRoots.push_back(SR);
1333 }
1334 else {
1335 // Get the super region for R.
1336 const MemRegion* SuperR = cast<SubRegion>(R)->getSuperRegion();
1337
1338 // Get the current set of subregions for SuperR.
1339 const SubRegionsTy* SRptr = SubRegMap.lookup(SuperR);
1340 SubRegionsTy SRs = SRptr ? *SRptr : SubRegF.GetEmptySet();
1341
1342 // Add R to the subregions of SuperR.
1343 SubRegMap = SubRegMapF.Add(SubRegMap, SuperR, SubRegF.Add(SRs, R));
1344
1345 // Super region may be VarRegion or subregion of another VarRegion. Add it
1346 // to the work list.
1347 if (isa<SubRegion>(SuperR))
1348 IntermediateRoots.push_back(SuperR);
1349 }
1350 }
1351
1352 // Process the worklist of RegionRoots. This performs a "mark-and-sweep"
1353 // of the store. We want to find all live symbols and dead regions.
1354 llvm::SmallPtrSet<const MemRegion*, 10> Marked;
1355
1356 while (!RegionRoots.empty()) {
1357 // Dequeue the next region on the worklist.
1358 const MemRegion* R = RegionRoots.back();
1359 RegionRoots.pop_back();
1360
1361 // Check if we have already processed this region.
1362 if (Marked.count(R)) continue;
1363
1364 // Mark this region as processed. This is needed for termination in case
1365 // a region is referenced more than once.
1366 Marked.insert(R);
1367
1368 // Mark the symbol for any live SymbolicRegion as "live". This means we
1369 // should continue to track that symbol.
1370 if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(R))
1371 SymReaper.markLive(SymR->getSymbol());
1372
1373 // Get the data binding for R (if any).
1374 RegionBindingsTy::data_type* Xptr = B.lookup(R);
1375 if (Xptr) {
1376 SVal X = *Xptr;
1377 UpdateLiveSymbols(X, SymReaper); // Update the set of live symbols.
1378
1379 // If X is a region, then add it the RegionRoots.
1380 if (loc::MemRegionVal* RegionX = dyn_cast<loc::MemRegionVal>(&X))
1381 RegionRoots.push_back(RegionX->getRegion());
1382 }
1383
1384 // Get the subregions of R. These are RegionRoots as well since they
1385 // represent values that are also bound to R.
1386 const SubRegionsTy* SRptr = SubRegMap.lookup(R);
1387 if (!SRptr) continue;
1388 SubRegionsTy SR = *SRptr;
1389
1390 for (SubRegionsTy::iterator I=SR.begin(), E=SR.end(); I!=E; ++I)
1391 RegionRoots.push_back(*I);
1392 }
1393
1394 // We have now scanned the store, marking reachable regions and symbols
1395 // as live. We now remove all the regions that are dead from the store
1396 // as well as update DSymbols with the set symbols that are now dead.
1397 for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
1398 const MemRegion* R = I.getKey();
1399
1400 // If this region live? Is so, none of its symbols are dead.
1401 if (Marked.count(R))
1402 continue;
1403
1404 // Remove this dead region from the store.
Zhongxing Xud91ee272009-06-23 09:02:15 +00001405 store = Remove(store, ValMgr.makeLoc(R));
Ted Kremenek9af46f52009-06-16 22:36:44 +00001406
1407 // Mark all non-live symbols that this region references as dead.
1408 if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(R))
1409 SymReaper.maybeDead(SymR->getSymbol());
1410
1411 SVal X = I.getData();
1412 SVal::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
1413 for (; SI != SE; ++SI) SymReaper.maybeDead(*SI);
1414 }
1415
1416 return store;
1417}
1418
1419//===----------------------------------------------------------------------===//
1420// Utility methods.
1421//===----------------------------------------------------------------------===//
1422
Ted Kremenek53ba0b62009-06-24 23:06:47 +00001423void RegionStoreManager::print(Store store, llvm::raw_ostream& OS,
Ted Kremenek9af46f52009-06-16 22:36:44 +00001424 const char* nl, const char *sep) {
Ted Kremenek9af46f52009-06-16 22:36:44 +00001425 RegionBindingsTy B = GetRegionBindings(store);
1426 OS << "Store:" << nl;
1427
1428 for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
1429 OS << ' '; I.getKey()->print(OS); OS << " : ";
1430 I.getData().print(OS); OS << nl;
1431 }
1432}