blob: 157248f21bd25b9ef11cbfab9bb394b77730c210 [file] [log] [blame]
Zhongxing Xu17892752008-10-08 02:50:44 +00001//== RegionStore.cpp - Field-sensitive store model --------------*- C++ -*--==//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines a basic region store model. In this model, we do have field
11// sensitivity. But we assume nothing about the heap shape. So recursive data
12// structures are largely ignored. Basically we do 1-limiting analysis.
13// Parameter pointers are assumed with no aliasing. Pointee objects of
14// parameters are created lazily.
15//
16//===----------------------------------------------------------------------===//
17#include "clang/Analysis/PathSensitive/MemRegion.h"
18#include "clang/Analysis/PathSensitive/GRState.h"
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000019#include "clang/Analysis/PathSensitive/GRStateTrait.h"
Zhongxing Xu17892752008-10-08 02:50:44 +000020#include "clang/Analysis/Analyses/LiveVariables.h"
21
22#include "llvm/ADT/ImmutableMap.h"
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000023#include "llvm/ADT/ImmutableList.h"
Zhongxing Xua071eb02008-10-24 06:01:33 +000024#include "llvm/Support/raw_ostream.h"
Zhongxing Xu17892752008-10-08 02:50:44 +000025#include "llvm/Support/Compiler.h"
26
27using namespace clang;
28
Zhongxing Xubaf03a72008-11-24 09:44:56 +000029// Actual Store type.
Zhongxing Xu1c96b242008-10-17 05:57:07 +000030typedef llvm::ImmutableMap<const MemRegion*, SVal> RegionBindingsTy;
Zhongxing Xubaf03a72008-11-24 09:44:56 +000031
32// RegionView GDM stuff.
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000033typedef llvm::ImmutableList<const MemRegion*> RegionViewTy;
34typedef llvm::ImmutableMap<const MemRegion*, RegionViewTy> RegionViewMapTy;
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000035static int RegionViewMapTyIndex = 0;
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000036namespace clang {
37template<> struct GRStateTrait<RegionViewMapTy>
38 : public GRStatePartialTrait<RegionViewMapTy> {
39 static void* GDMIndex() { return &RegionViewMapTyIndex; }
40};
41}
Zhongxing Xu17892752008-10-08 02:50:44 +000042
Zhongxing Xubaf03a72008-11-24 09:44:56 +000043// RegionExtents GDM stuff.
44// Currently RegionExtents are in bytes. We can change this representation when
45// there are real requirements.
46typedef llvm::ImmutableMap<const MemRegion*, SVal> RegionExtentsTy;
47static int RegionExtentsTyIndex = 0;
48namespace clang {
49template<> struct GRStateTrait<RegionExtentsTy>
50 : public GRStatePartialTrait<RegionExtentsTy> {
51 static void* GDMIndex() { return &RegionExtentsTyIndex; }
52};
53}
54
Zhongxing Xu17892752008-10-08 02:50:44 +000055namespace {
56
57class VISIBILITY_HIDDEN RegionStoreManager : public StoreManager {
58 RegionBindingsTy::Factory RBFactory;
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000059 RegionViewTy::Factory RVFactory;
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000060
Zhongxing Xu17892752008-10-08 02:50:44 +000061 GRStateManager& StateMgr;
62 MemRegionManager MRMgr;
63
64public:
65 RegionStoreManager(GRStateManager& mgr)
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000066 : RBFactory(mgr.getAllocator()),
67 RVFactory(mgr.getAllocator()),
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000068 StateMgr(mgr),
69 MRMgr(StateMgr.getAllocator()) {}
Zhongxing Xu17892752008-10-08 02:50:44 +000070
71 virtual ~RegionStoreManager() {}
72
Zhongxing Xu24194ef2008-10-24 01:38:55 +000073 MemRegionManager& getRegionManager() { return MRMgr; }
74
75 // FIXME: Is this function necessary?
76 SVal GetRegionSVal(Store St, const MemRegion* R) {
77 return Retrieve(St, loc::MemRegionVal(R));
78 }
Ted Kremenek4f090272008-10-27 21:54:31 +000079
Zhongxing Xuf22679e2008-11-07 10:38:33 +000080 Store BindCompoundLiteral(Store store, const CompoundLiteralExpr* CL, SVal V);
Zhongxing Xu24194ef2008-10-24 01:38:55 +000081
Zhongxing Xu143bf822008-10-25 14:18:57 +000082 SVal getLValueString(const GRState* St, const StringLiteral* S);
83
Zhongxing Xuf22679e2008-11-07 10:38:33 +000084 SVal getLValueCompoundLiteral(const GRState* St, const CompoundLiteralExpr*);
85
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +000086 SVal getLValueVar(const GRState* St, const VarDecl* VD);
87
88 SVal getLValueIvar(const GRState* St, const ObjCIvarDecl* D, SVal Base);
89
90 SVal getLValueField(const GRState* St, SVal Base, const FieldDecl* D);
91
Zhongxing Xub1d542a2008-10-24 01:09:32 +000092 SVal getLValueElement(const GRState* St, SVal Base, SVal Offset);
93
Zhongxing Xue8a964b2008-11-22 13:21:46 +000094 SVal getSizeInElements(const GRState* St, const MemRegion* R);
95
Zhongxing Xub1d542a2008-10-24 01:09:32 +000096 SVal ArrayToPointer(SVal Array);
97
Zhongxing Xucb529b52008-11-16 07:06:26 +000098 std::pair<const GRState*, SVal>
99 CastRegion(const GRState* St, SVal VoidPtr, QualType CastToTy, Stmt* CastE);
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000100
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000101 SVal Retrieve(Store S, Loc L, QualType T = QualType());
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000102
Zhongxing Xu8485ec62008-10-21 06:27:32 +0000103 Store Bind(Store St, Loc LV, SVal V);
Zhongxing Xu17892752008-10-08 02:50:44 +0000104
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000105 Store Remove(Store store, Loc LV) {
106 // FIXME: Implement.
107 return store;
108 }
109
Zhongxing Xu17892752008-10-08 02:50:44 +0000110 Store getInitialStore();
Ted Kremenek9deb0e32008-10-24 20:32:16 +0000111
112 /// getSelfRegion - Returns the region for the 'self' (Objective-C) or
113 /// 'this' object (C++). When used when analyzing a normal function this
114 /// method returns NULL.
115 const MemRegion* getSelfRegion(Store) {
116 assert (false && "Not implemented.");
117 return 0;
118 }
Zhongxing Xu17892752008-10-08 02:50:44 +0000119
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000120 Store RemoveDeadBindings(Store store, Stmt* Loc, const LiveVariables& Live,
121 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots,
Zhongxing Xu8916d5b2008-11-10 09:39:04 +0000122 LiveSymbolsTy& LSymbols, DeadSymbolsTy& DSymbols);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000123
Ted Kremenek42577d12008-11-12 19:18:35 +0000124 Store BindDecl(Store store, const VarDecl* VD, SVal* InitVal, unsigned Count);
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000125
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000126 const GRState* setExtent(const GRState* St, const MemRegion* R, SVal Extent);
127
Zhongxing Xu17892752008-10-08 02:50:44 +0000128 static inline RegionBindingsTy GetRegionBindings(Store store) {
129 return RegionBindingsTy(static_cast<const RegionBindingsTy::TreeTy*>(store));
130 }
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000131
Zhongxing Xu5b8b6f22008-10-24 04:33:15 +0000132 void print(Store store, std::ostream& Out, const char* nl, const char *sep);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000133
134 void iterBindings(Store store, BindingsHandler& f) {
135 // FIXME: Implement.
136 }
Zhongxing Xua82512a2008-10-24 08:42:28 +0000137
138private:
139 Loc getVarLoc(const VarDecl* VD) {
140 return loc::MemRegionVal(MRMgr.getVarRegion(VD));
141 }
142
Zhongxing Xud463d442008-11-02 12:13:30 +0000143 Store InitializeArray(Store store, const TypedRegion* R, SVal Init);
144 Store BindArrayToVal(Store store, const TypedRegion* BaseR, SVal V);
Zhongxing Xuc3a05992008-11-19 11:06:24 +0000145 Store BindArrayToSymVal(Store store, const TypedRegion* BaseR);
146
Zhongxing Xud463d442008-11-02 12:13:30 +0000147 Store InitializeStruct(Store store, const TypedRegion* R, SVal Init);
148 Store BindStructToVal(Store store, const TypedRegion* BaseR, SVal V);
Zhongxing Xuc3a05992008-11-19 11:06:24 +0000149 Store BindStructToSymVal(Store store, const TypedRegion* BaseR);
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000150
151 SVal RetrieveStruct(Store store, const TypedRegion* R);
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +0000152 Store BindStruct(Store store, const TypedRegion* R, SVal V);
Zhongxing Xu63123d82008-11-23 04:30:35 +0000153
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000154 // Utility methods.
155 BasicValueFactory& getBasicVals() { return StateMgr.getBasicVals(); }
156 ASTContext& getContext() { return StateMgr.getContext(); }
Zhongxing Xu63123d82008-11-23 04:30:35 +0000157 SymbolManager& getSymbolManager() { return StateMgr.getSymbolManager(); }
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000158
159 const GRState* AddRegionView(const GRState* St,
160 const MemRegion* View, const MemRegion* Base);
Zhongxing Xu17892752008-10-08 02:50:44 +0000161};
162
163} // end anonymous namespace
164
Ted Kremenek95c7b002008-10-24 01:04:59 +0000165StoreManager* clang::CreateRegionStoreManager(GRStateManager& StMgr) {
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000166 return new RegionStoreManager(StMgr);
Ted Kremenek95c7b002008-10-24 01:04:59 +0000167}
168
Zhongxing Xu143bf822008-10-25 14:18:57 +0000169SVal RegionStoreManager::getLValueString(const GRState* St,
170 const StringLiteral* S) {
171 return loc::MemRegionVal(MRMgr.getStringRegion(S));
172}
173
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000174SVal RegionStoreManager::getLValueVar(const GRState* St, const VarDecl* VD) {
175 return loc::MemRegionVal(MRMgr.getVarRegion(VD));
176}
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000177
178SVal RegionStoreManager::getLValueCompoundLiteral(const GRState* St,
179 const CompoundLiteralExpr* CL) {
180 return loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL));
181}
182
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000183SVal RegionStoreManager::getLValueIvar(const GRState* St, const ObjCIvarDecl* D,
184 SVal Base) {
185 return UnknownVal();
186}
187
188SVal RegionStoreManager::getLValueField(const GRState* St, SVal Base,
189 const FieldDecl* D) {
190 if (Base.isUnknownOrUndef())
191 return Base;
192
193 Loc BaseL = cast<Loc>(Base);
194 const MemRegion* BaseR = 0;
195
196 switch (BaseL.getSubKind()) {
197 case loc::MemRegionKind:
198 BaseR = cast<loc::MemRegionVal>(BaseL).getRegion();
199 break;
200
201 case loc::SymbolValKind:
202 BaseR = MRMgr.getSymbolicRegion(cast<loc::SymbolVal>(&BaseL)->getSymbol());
203 break;
204
205 case loc::GotoLabelKind:
206 case loc::FuncValKind:
207 // These are anormal cases. Flag an undefined value.
208 return UndefinedVal();
209
210 case loc::ConcreteIntKind:
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000211 // While these seem funny, this can happen through casts.
212 // FIXME: What we should return is the field offset. For example,
213 // add the field offset to the integer value. That way funny things
214 // like this work properly: &(((struct foo *) 0xa)->f)
215 return Base;
216
217 default:
Zhongxing Xu13d1ee22008-11-07 08:57:30 +0000218 assert(0 && "Unhandled Base.");
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000219 return Base;
220 }
221
222 return loc::MemRegionVal(MRMgr.getFieldRegion(D, BaseR));
223}
224
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000225SVal RegionStoreManager::getLValueElement(const GRState* St,
226 SVal Base, SVal Offset) {
227 if (Base.isUnknownOrUndef())
228 return Base;
229
Zhongxing Xu4a1513e2008-10-27 12:23:17 +0000230 if (isa<loc::SymbolVal>(Base))
231 return Base;
232
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000233 loc::MemRegionVal& BaseL = cast<loc::MemRegionVal>(Base);
234
Zhongxing Xue4d13932008-11-13 09:48:44 +0000235 // Pointer of any type can be cast and used as array base. We do not support
236 // that case yet.
237 if (!isa<ElementRegion>(BaseL.getRegion())) {
238 // Record what we have seen in real code.
239 assert(isa<FieldRegion>(BaseL.getRegion()));
240 return UnknownVal();
241 }
242
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000243 // We expect BaseR is an ElementRegion, not a base VarRegion.
244
245 const ElementRegion* ElemR = cast<ElementRegion>(BaseL.getRegion());
246
247 SVal Idx = ElemR->getIndex();
248
249 nonloc::ConcreteInt *CI1, *CI2;
250
251 // Only handle integer indices for now.
252 if ((CI1 = dyn_cast<nonloc::ConcreteInt>(&Idx)) &&
253 (CI2 = dyn_cast<nonloc::ConcreteInt>(&Offset))) {
Zhongxing Xucc0d0ec2008-11-13 09:15:14 +0000254
Sebastian Redle95db4f2008-11-24 19:35:33 +0000255 // Temporary SVal to hold a potential signed and extended APSInt.
Zhongxing Xucc0d0ec2008-11-13 09:15:14 +0000256 SVal SignedInt;
257
Sebastian Redle95db4f2008-11-24 19:35:33 +0000258 // Index might be unsigned. We have to convert it to signed. It might also
259 // be less wide than the size. We have to extend it.
260 if (CI2->getValue().isUnsigned() ||
261 CI2->getValue().getBitWidth() < CI1->getValue().getBitWidth()) {
Zhongxing Xucc0d0ec2008-11-13 09:15:14 +0000262 llvm::APSInt SI = CI2->getValue();
Sebastian Redlddee68b2008-11-24 19:39:40 +0000263 if (CI2->getValue().getBitWidth() < CI1->getValue().getBitWidth())
264 SI.extend(CI1->getValue().getBitWidth());
Zhongxing Xucc0d0ec2008-11-13 09:15:14 +0000265 SI.setIsSigned(true);
266 SignedInt = nonloc::ConcreteInt(getBasicVals().getValue(SI));
267 CI2 = cast<nonloc::ConcreteInt>(&SignedInt);
268 }
269
Zhongxing Xu63123d82008-11-23 04:30:35 +0000270 SVal NewIdx = CI1->EvalBinOp(getBasicVals(), BinaryOperator::Add, *CI2);
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000271 return loc::MemRegionVal(MRMgr.getElementRegion(NewIdx,
272 ElemR->getSuperRegion()));
273 }
274
275 return UnknownVal();
276}
277
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000278SVal RegionStoreManager::getSizeInElements(const GRState* St,
279 const MemRegion* R) {
280 if (const VarRegion* VR = dyn_cast<VarRegion>(R)) {
281 // Get the type of the variable.
282 QualType T = VR->getType(getContext());
283
284 // It must be of array type.
285 const ConstantArrayType* CAT = cast<ConstantArrayType>(T.getTypePtr());
286
287 // return the size as signed integer.
288 return NonLoc::MakeVal(getBasicVals(), CAT->getSize(), false);
289 }
290
291 if (const StringRegion* SR = dyn_cast<StringRegion>(R)) {
Zhongxing Xu6613d082008-11-24 02:18:56 +0000292 const StringLiteral* Str = SR->getStringLiteral();
Zhongxing Xud0fd3b72008-11-24 02:30:48 +0000293 // We intentionally made the size value signed because it participates in
294 // operations with signed indices.
Zhongxing Xu4b89e032008-11-24 05:16:01 +0000295 return NonLoc::MakeVal(getBasicVals(), Str->getByteLength() + 1, false);
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000296 }
297
298 if (const AnonTypedRegion* ATR = dyn_cast<AnonTypedRegion>(R)) {
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000299 GRStateRef state(St, StateMgr);
300
301 // Get the size of the super region in bytes.
302 RegionExtentsTy::data_type* T
303 = state.get<RegionExtentsTy>(ATR->getSuperRegion());
304
305 assert(T && "region extent not exist");
306
307 // Assume it's ConcreteInt for now.
308 llvm::APSInt SSize = cast<nonloc::ConcreteInt>(*T).getValue();
309
310 // Get the size of the element in bits.
311 QualType ElemTy = cast<PointerType>(ATR->getType(getContext()).getTypePtr())
312 ->getPointeeType();
313
314 uint64_t X = getContext().getTypeSize(ElemTy);
315
316 const llvm::APSInt& ESize = getBasicVals().getValue(X, SSize.getBitWidth(),
317 false);
318
319 // Calculate the number of elements.
320
321 // FIXME: What do we do with signed-ness problem? Shall we make all APSInts
322 // signed?
323 if (SSize.isUnsigned())
324 SSize.setIsSigned(true);
325
326 // FIXME: move this operation into BasicVals.
327 const llvm::APSInt S =
328 (SSize * getBasicVals().getValue(8, SSize.getBitWidth(), false)) / ESize;
329
330 return NonLoc::MakeVal(getBasicVals(), S);
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000331 }
332
333 if (const FieldRegion* FR = dyn_cast<FieldRegion>(R)) {
334 // FIXME: Unsupported yet.
335 FR = 0;
336 return UnknownVal();
337 }
Zhongxing Xu369f4292008-11-22 13:23:00 +0000338
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000339 assert(0 && "Other regions are not supported yet.");
340}
341
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000342// Cast 'pointer to array' to 'pointer to the first element of array'.
343
344SVal RegionStoreManager::ArrayToPointer(SVal Array) {
345 const MemRegion* ArrayR = cast<loc::MemRegionVal>(&Array)->getRegion();
Zhongxing Xu143bf822008-10-25 14:18:57 +0000346
Zhongxing Xu63123d82008-11-23 04:30:35 +0000347 nonloc::ConcreteInt Idx(getBasicVals().getZeroWithPtrWidth(false));
Zhongxing Xu0b7e6422008-10-26 02:23:57 +0000348 ElementRegion* ER = MRMgr.getElementRegion(Idx, ArrayR);
349
350 return loc::MemRegionVal(ER);
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000351}
352
Zhongxing Xucb529b52008-11-16 07:06:26 +0000353std::pair<const GRState*, SVal>
354RegionStoreManager::CastRegion(const GRState* St, SVal VoidPtr,
355 QualType CastToTy, Stmt* CastE) {
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000356 if (const AllocaRegion* AR =
357 dyn_cast<AllocaRegion>(cast<loc::MemRegionVal>(VoidPtr).getRegion())) {
358
359 // Create a new region to attach type information to it.
360 const AnonTypedRegion* TR = MRMgr.getAnonTypedRegion(CastToTy, AR);
361
362 // Get the pointer to the first element.
363 nonloc::ConcreteInt Idx(getBasicVals().getZeroWithPtrWidth(false));
364 const ElementRegion* ER = MRMgr.getElementRegion(Idx, TR);
365
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000366 // Add a RegionView to base region.
Zhongxing Xu353cbe12008-11-28 03:55:52 +0000367 return std::make_pair(AddRegionView(St, TR, AR), loc::MemRegionVal(ER));
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000368 }
369
370 // Default case.
Zhongxing Xu353cbe12008-11-28 03:55:52 +0000371 return std::make_pair(St, UnknownVal());
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000372}
373
Zhongxing Xu8485ec62008-10-21 06:27:32 +0000374SVal RegionStoreManager::Retrieve(Store S, Loc L, QualType T) {
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000375 assert(!isa<UnknownVal>(L) && "location unknown");
376 assert(!isa<UndefinedVal>(L) && "location undefined");
377
378 switch (L.getSubKind()) {
379 case loc::MemRegionKind: {
380 const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion();
381 assert(R && "bad region");
382
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000383 if (const TypedRegion* TR = dyn_cast<TypedRegion>(R))
384 if (TR->getType(getContext())->isStructureType())
385 return RetrieveStruct(S, TR);
386
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000387 RegionBindingsTy B(static_cast<const RegionBindingsTy::TreeTy*>(S));
388 RegionBindingsTy::data_type* V = B.lookup(R);
389 return V ? *V : UnknownVal();
390 }
391
392 case loc::SymbolValKind:
393 return UnknownVal();
394
395 case loc::ConcreteIntKind:
396 return UndefinedVal(); // As in BasicStoreManager.
397
398 case loc::FuncValKind:
399 return L;
400
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000401 default:
402 assert(false && "Invalid Location");
Ted Kremenekab7b32b2008-11-19 00:27:37 +0000403 return L;
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000404 }
405}
406
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000407SVal RegionStoreManager::RetrieveStruct(Store store, const TypedRegion* R) {
408 QualType T = R->getType(getContext());
409 assert(T->isStructureType());
410
411 const RecordType* RT = cast<RecordType>(T.getTypePtr());
412 RecordDecl* RD = RT->getDecl();
413 assert(RD->isDefinition());
414
415 llvm::ImmutableList<SVal> StructVal = getBasicVals().getEmptySValList();
416
417 for (int i = RD->getNumMembers() - 1; i >= 0; --i) {
418 FieldRegion* FR = MRMgr.getFieldRegion(RD->getMember(i), R);
419 RegionBindingsTy B(static_cast<const RegionBindingsTy::TreeTy*>(store));
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +0000420 RegionBindingsTy::data_type* data = B.lookup(FR);
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000421
422 SVal FieldValue = data ? *data : UnknownVal();
423
424 StructVal = getBasicVals().consVals(FieldValue, StructVal);
425 }
426
427 return NonLoc::MakeCompoundVal(T, StructVal, getBasicVals());
428}
429
Zhongxing Xu8485ec62008-10-21 06:27:32 +0000430Store RegionStoreManager::Bind(Store store, Loc LV, SVal V) {
Zhongxing Xu8fe63af2008-10-27 09:24:07 +0000431 if (LV.getSubKind() == loc::SymbolValKind)
432 return store;
433
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000434 assert(LV.getSubKind() == loc::MemRegionKind);
Zhongxing Xu17892752008-10-08 02:50:44 +0000435
Ted Kremenek993f1c72008-10-17 20:28:54 +0000436 const MemRegion* R = cast<loc::MemRegionVal>(LV).getRegion();
Zhongxing Xu17892752008-10-08 02:50:44 +0000437
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +0000438 assert(R);
439
440 if (const TypedRegion* TR = dyn_cast<TypedRegion>(R))
441 if (TR->getType(getContext())->isStructureType())
442 return BindStruct(store, TR, V);
Zhongxing Xu17892752008-10-08 02:50:44 +0000443
444 RegionBindingsTy B = GetRegionBindings(store);
445 return V.isUnknown()
446 ? RBFactory.Remove(B, R).getRoot()
447 : RBFactory.Add(B, R, V).getRoot();
448}
449
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +0000450Store RegionStoreManager::BindStruct(Store store, const TypedRegion* R, SVal V){
451 QualType T = R->getType(getContext());
452 assert(T->isStructureType());
453
454 const RecordType* RT = cast<RecordType>(T.getTypePtr());
455 RecordDecl* RD = RT->getDecl();
Zhongxing Xua4f28ff2008-11-13 08:41:36 +0000456
457 if (!RD->isDefinition()) {
Zhongxing Xuc3a05992008-11-19 11:06:24 +0000458 // This can only occur when a pointer of incomplete struct type is used as a
Zhongxing Xua4f28ff2008-11-13 08:41:36 +0000459 // function argument.
460 assert(V.isUnknown());
461 return store;
462 }
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +0000463
464 RegionBindingsTy B = GetRegionBindings(store);
465
Zhongxing Xud463d442008-11-02 12:13:30 +0000466 if (isa<UnknownVal>(V))
467 return BindStructToVal(store, R, UnknownVal());
468
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +0000469 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V);
470
471 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
472 RecordDecl::field_iterator FI = RD->field_begin(), FE = RD->field_end();
473
474 for (; FI != FE; ++FI, ++VI) {
475 assert(VI != VE);
476
477 FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);
478
479 B = RBFactory.Add(B, FR, *VI);
480 }
481
482 return B.getRoot();
483}
484
Zhongxing Xu17892752008-10-08 02:50:44 +0000485Store RegionStoreManager::getInitialStore() {
486 typedef LiveVariables::AnalysisDataTy LVDataTy;
487 LVDataTy& D = StateMgr.getLiveVariables().getAnalysisData();
488
489 Store St = RBFactory.GetEmptyMap().getRoot();
490
491 for (LVDataTy::decl_iterator I=D.begin_decl(), E=D.end_decl(); I != E; ++I) {
Douglas Gregor8e9bebd2008-10-21 16:13:35 +0000492 NamedDecl* ND = const_cast<NamedDecl*>(I->first);
Zhongxing Xu17892752008-10-08 02:50:44 +0000493
Douglas Gregor8e9bebd2008-10-21 16:13:35 +0000494 if (VarDecl* VD = dyn_cast<VarDecl>(ND)) {
Zhongxing Xu17892752008-10-08 02:50:44 +0000495 // Punt on static variables for now.
496 if (VD->getStorageClass() == VarDecl::Static)
497 continue;
498
Zhongxing Xuc3a05992008-11-19 11:06:24 +0000499 VarRegion* VR = MRMgr.getVarRegion(VD);
500
Zhongxing Xu17892752008-10-08 02:50:44 +0000501 QualType T = VD->getType();
502 // Only handle pointers and integers for now.
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000503 if (Loc::IsLocType(T) || T->isIntegerType()) {
Zhongxing Xu17892752008-10-08 02:50:44 +0000504 // Initialize globals and parameters to symbolic values.
505 // Initialize local variables to undefined.
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000506 SVal X = (VD->hasGlobalStorage() || isa<ParmVarDecl>(VD) ||
Zhongxing Xu17892752008-10-08 02:50:44 +0000507 isa<ImplicitParamDecl>(VD))
Zhongxing Xu63123d82008-11-23 04:30:35 +0000508 ? SVal::GetSymbolValue(getSymbolManager(), VD)
Zhongxing Xu17892752008-10-08 02:50:44 +0000509 : UndefinedVal();
510
Zhongxing Xu8485ec62008-10-21 06:27:32 +0000511 St = Bind(St, getVarLoc(VD), X);
Zhongxing Xuc3a05992008-11-19 11:06:24 +0000512 }
513 else if (T->isArrayType()) {
514 if (VD->hasGlobalStorage()) // Params cannot have array type.
515 St = BindArrayToSymVal(St, VR);
516 else
517 St = BindArrayToVal(St, VR, UndefinedVal());
518 }
519 else if (T->isStructureType()) {
520 if (VD->hasGlobalStorage() || isa<ParmVarDecl>(VD) ||
521 isa<ImplicitParamDecl>(VD))
522 St = BindStructToSymVal(St, VR);
523 else
524 St = BindStructToVal(St, VR, UndefinedVal());
Zhongxing Xu17892752008-10-08 02:50:44 +0000525 }
526 }
527 }
528 return St;
529}
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000530
Ted Kremenek42577d12008-11-12 19:18:35 +0000531Store RegionStoreManager::BindDecl(Store store, const VarDecl* VD,
532 SVal* InitVal, unsigned Count) {
533
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000534 if (VD->hasGlobalStorage()) {
535 // Static global variables should not be visited here.
536 assert(!(VD->getStorageClass() == VarDecl::Static &&
537 VD->isFileVarDecl()));
538 // Process static variables.
539 if (VD->getStorageClass() == VarDecl::Static) {
Ted Kremenek42577d12008-11-12 19:18:35 +0000540 if (!InitVal) {
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000541 // Only handle pointer and integer static variables.
542
543 QualType T = VD->getType();
544
545 if (Loc::IsLocType(T))
Zhongxing Xu8485ec62008-10-21 06:27:32 +0000546 store = Bind(store, getVarLoc(VD),
Zhongxing Xu63123d82008-11-23 04:30:35 +0000547 loc::ConcreteInt(getBasicVals().getValue(0, T)));
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000548
549 else if (T->isIntegerType())
Zhongxing Xu8485ec62008-10-21 06:27:32 +0000550 store = Bind(store, getVarLoc(VD),
Zhongxing Xu63123d82008-11-23 04:30:35 +0000551 loc::ConcreteInt(getBasicVals().getValue(0, T)));
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +0000552
553 // Other types of static local variables are not handled yet.
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000554 } else {
Ted Kremenek42577d12008-11-12 19:18:35 +0000555 store = Bind(store, getVarLoc(VD), *InitVal);
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000556 }
557 }
558 } else {
559 // Process local variables.
560
561 QualType T = VD->getType();
562
Zhongxing Xua82512a2008-10-24 08:42:28 +0000563 VarRegion* VR = MRMgr.getVarRegion(VD);
564
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000565 if (Loc::IsLocType(T) || T->isIntegerType()) {
Ted Kremenek42577d12008-11-12 19:18:35 +0000566 SVal V = InitVal ? *InitVal : UndefinedVal();
Zhongxing Xua82512a2008-10-24 08:42:28 +0000567 store = Bind(store, loc::MemRegionVal(VR), V);
Ted Kremenek42577d12008-11-12 19:18:35 +0000568 }
569 else if (T->isArrayType()) {
570 if (!InitVal)
Zhongxing Xud463d442008-11-02 12:13:30 +0000571 store = BindArrayToVal(store, VR, UndefinedVal());
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +0000572 else
Ted Kremenek42577d12008-11-12 19:18:35 +0000573 store = InitializeArray(store, VR, *InitVal);
574 }
575 else if (T->isStructureType()) {
576 if (!InitVal)
Zhongxing Xud463d442008-11-02 12:13:30 +0000577 store = BindStructToVal(store, VR, UndefinedVal());
Zhongxing Xuaf0a8442008-10-31 10:53:01 +0000578 else
Ted Kremenek42577d12008-11-12 19:18:35 +0000579 store = InitializeStruct(store, VR, *InitVal);
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000580 }
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +0000581
582 // Other types of local variables are not handled yet.
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000583 }
584 return store;
585}
586
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000587Store RegionStoreManager::BindCompoundLiteral(Store store,
588 const CompoundLiteralExpr* CL,
589 SVal V) {
590 CompoundLiteralRegion* R = MRMgr.getCompoundLiteralRegion(CL);
591 store = Bind(store, loc::MemRegionVal(R), V);
592 return store;
593}
594
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000595const GRState* RegionStoreManager::setExtent(const GRState* St,
596 const MemRegion* R, SVal Extent) {
597 GRStateRef state(St, StateMgr);
598 return state.set<RegionExtentsTy>(R, Extent);
599}
600
601
Zhongxing Xu8916d5b2008-11-10 09:39:04 +0000602Store RegionStoreManager::RemoveDeadBindings(Store store, Stmt* Loc,
603 const LiveVariables& Live,
604 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots,
605 LiveSymbolsTy& LSymbols, DeadSymbolsTy& DSymbols) {
606
607 RegionBindingsTy B = GetRegionBindings(store);
608 typedef SVal::symbol_iterator symbol_iterator;
609
610 // FIXME: Mark all region binding value's symbol as live. We also omit symbols
611 // in SymbolicRegions.
612 for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
613 SVal X = I.getData();
614 for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI)
615 LSymbols.insert(*SI);
616 }
617
618 return store;
619}
620
Zhongxing Xua071eb02008-10-24 06:01:33 +0000621void RegionStoreManager::print(Store store, std::ostream& Out,
622 const char* nl, const char *sep) {
623 llvm::raw_os_ostream OS(Out);
624 RegionBindingsTy B = GetRegionBindings(store);
625 OS << "Store:" << nl;
626
627 for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
628 OS << ' '; I.getKey()->print(OS); OS << " : ";
629 I.getData().print(OS); OS << nl;
630 }
Zhongxing Xu5b8b6f22008-10-24 04:33:15 +0000631}
Zhongxing Xua82512a2008-10-24 08:42:28 +0000632
Zhongxing Xud463d442008-11-02 12:13:30 +0000633Store RegionStoreManager::InitializeArray(Store store, const TypedRegion* R,
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +0000634 SVal Init) {
635 QualType T = R->getType(getContext());
636 assert(T->isArrayType());
637
638 ConstantArrayType* CAT = cast<ConstantArrayType>(T.getTypePtr());
639
640 llvm::APInt Size = CAT->getSize();
641
642 llvm::APInt i = llvm::APInt::getNullValue(Size.getBitWidth());
643
644 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(Init);
645
646 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
647
648 for (; i != Size; ++i) {
649 nonloc::ConcreteInt Idx(getBasicVals().getValue(llvm::APSInt(i)));
650
651 ElementRegion* ER = MRMgr.getElementRegion(Idx, R);
652
653 store = Bind(store, loc::MemRegionVal(ER), (VI!=VE) ? *VI : UndefinedVal());
654 // The init list might be shorter than the array decl.
655 if (VI != VE) ++VI;
656 }
657
658 return store;
659}
660
Zhongxing Xud463d442008-11-02 12:13:30 +0000661// Bind all elements of the array to some value.
662Store RegionStoreManager::BindArrayToVal(Store store, const TypedRegion* BaseR,
663 SVal V){
Zhongxing Xuea8a1852008-10-31 11:02:48 +0000664 QualType T = BaseR->getType(getContext());
Zhongxing Xua82512a2008-10-24 08:42:28 +0000665 assert(T->isArrayType());
666
Zhongxing Xua82512a2008-10-24 08:42:28 +0000667 // Only handle constant size array for now.
668 if (ConstantArrayType* CAT=dyn_cast<ConstantArrayType>(T.getTypePtr())) {
669
670 llvm::APInt Size = CAT->getSize();
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +0000671 llvm::APInt i = llvm::APInt::getNullValue(Size.getBitWidth());
672 for (; i != Size; ++i) {
Zhongxing Xuea8a1852008-10-31 11:02:48 +0000673 nonloc::ConcreteInt Idx(getBasicVals().getValue(llvm::APSInt(i)));
Zhongxing Xua82512a2008-10-24 08:42:28 +0000674
675 ElementRegion* ER = MRMgr.getElementRegion(Idx, BaseR);
676
Zhongxing Xu9b6ceb12008-11-18 13:11:04 +0000677 if (CAT->getElementType()->isStructureType())
678 store = BindStructToVal(store, ER, V);
679 else
680 store = Bind(store, loc::MemRegionVal(ER), V);
Zhongxing Xua82512a2008-10-24 08:42:28 +0000681 }
682 }
683
684 return store;
685}
686
Zhongxing Xuc3a05992008-11-19 11:06:24 +0000687Store RegionStoreManager::BindArrayToSymVal(Store store,
688 const TypedRegion* BaseR) {
689 QualType T = BaseR->getType(getContext());
690 assert(T->isArrayType());
691
692 if (ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(T.getTypePtr())) {
693 llvm::APInt Size = CAT->getSize();
694 llvm::APInt i = llvm::APInt::getNullValue(Size.getBitWidth());
695 for (; i != Size; ++i) {
696 nonloc::ConcreteInt Idx(getBasicVals().getValue(llvm::APSInt(i)));
697
698 ElementRegion* ER = MRMgr.getElementRegion(Idx, BaseR);
699
700 if (CAT->getElementType()->isStructureType()) {
701 store = BindStructToSymVal(store, ER);
702 }
703 else {
704 SVal V = SVal::getSymbolValue(getSymbolManager(), BaseR,
705 &Idx.getValue(), CAT->getElementType());
706 store = Bind(store, loc::MemRegionVal(ER), V);
707 }
708 }
709 }
710
711 return store;
712}
713
Zhongxing Xud463d442008-11-02 12:13:30 +0000714Store RegionStoreManager::InitializeStruct(Store store, const TypedRegion* R,
Zhongxing Xuea8a1852008-10-31 11:02:48 +0000715 SVal Init) {
Zhongxing Xuaf0a8442008-10-31 10:53:01 +0000716 QualType T = R->getType(getContext());
717 assert(T->isStructureType());
718
719 RecordType* RT = cast<RecordType>(T.getTypePtr());
720 RecordDecl* RD = RT->getDecl();
721 assert(RD->isDefinition());
722
723 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(Init);
724 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
725 RecordDecl::field_iterator FI = RD->field_begin(), FE = RD->field_end();
726
727 for (; FI != FE; ++FI) {
728 QualType FTy = (*FI)->getType();
729 FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);
730
731 if (Loc::IsLocType(FTy) || FTy->isIntegerType()) {
732 if (VI != VE) {
733 store = Bind(store, loc::MemRegionVal(FR), *VI);
734 ++VI;
735 } else
736 store = Bind(store, loc::MemRegionVal(FR), UndefinedVal());
737 }
738 else if (FTy->isArrayType()) {
739 if (VI != VE) {
740 store = InitializeArray(store, FR, *VI);
741 ++VI;
742 } else
Zhongxing Xud463d442008-11-02 12:13:30 +0000743 store = BindArrayToVal(store, FR, UndefinedVal());
Zhongxing Xuaf0a8442008-10-31 10:53:01 +0000744 }
745 else if (FTy->isStructureType()) {
746 if (VI != VE) {
747 store = InitializeStruct(store, FR, *VI);
748 ++VI;
749 } else
Zhongxing Xud463d442008-11-02 12:13:30 +0000750 store = BindStructToVal(store, FR, UndefinedVal());
Zhongxing Xuaf0a8442008-10-31 10:53:01 +0000751 }
752 }
753 return store;
754}
755
Zhongxing Xud463d442008-11-02 12:13:30 +0000756// Bind all fields of the struct to some value.
757Store RegionStoreManager::BindStructToVal(Store store, const TypedRegion* BaseR,
758 SVal V) {
Zhongxing Xuea8a1852008-10-31 11:02:48 +0000759 QualType T = BaseR->getType(getContext());
760 assert(T->isStructureType());
761
762 const RecordType* RT = cast<RecordType>(T.getTypePtr());
Zhongxing Xua82512a2008-10-24 08:42:28 +0000763 RecordDecl* RD = RT->getDecl();
764 assert(RD->isDefinition());
Zhongxing Xuea8a1852008-10-31 11:02:48 +0000765
766 RecordDecl::field_iterator I = RD->field_begin(), E = RD->field_end();
767
768 for (; I != E; ++I) {
Zhongxing Xua82512a2008-10-24 08:42:28 +0000769
770 QualType FTy = (*I)->getType();
771 FieldRegion* FR = MRMgr.getFieldRegion(*I, BaseR);
772
773 if (Loc::IsLocType(FTy) || FTy->isIntegerType()) {
Zhongxing Xud463d442008-11-02 12:13:30 +0000774 store = Bind(store, loc::MemRegionVal(FR), V);
Zhongxing Xua82512a2008-10-24 08:42:28 +0000775
776 } else if (FTy->isArrayType()) {
Zhongxing Xud463d442008-11-02 12:13:30 +0000777 store = BindArrayToVal(store, FR, V);
Zhongxing Xua82512a2008-10-24 08:42:28 +0000778
779 } else if (FTy->isStructureType()) {
Zhongxing Xud463d442008-11-02 12:13:30 +0000780 store = BindStructToVal(store, FR, V);
Zhongxing Xua82512a2008-10-24 08:42:28 +0000781 }
782 }
783
784 return store;
785}
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000786
Zhongxing Xuc3a05992008-11-19 11:06:24 +0000787Store RegionStoreManager::BindStructToSymVal(Store store,
788 const TypedRegion* BaseR) {
789 QualType T = BaseR->getType(getContext());
790 assert(T->isStructureType());
791
792 const RecordType* RT = cast<RecordType>(T.getTypePtr());
793 RecordDecl* RD = RT->getDecl();
794 assert(RD->isDefinition());
795
796 RecordDecl::field_iterator I = RD->field_begin(), E = RD->field_end();
797
798 for (; I != E; ++I) {
799 QualType FTy = (*I)->getType();
800 FieldRegion* FR = MRMgr.getFieldRegion(*I, BaseR);
801
802 if (Loc::IsLocType(FTy) || FTy->isIntegerType()) {
803 store = Bind(store, loc::MemRegionVal(FR),
804 SVal::getSymbolValue(getSymbolManager(), BaseR, *I, FTy));
805 }
806 else if (FTy->isArrayType()) {
807 store = BindArrayToSymVal(store, FR);
808 }
809 else if (FTy->isStructureType()) {
810 store = BindStructToSymVal(store, FR);
811 }
812 }
813
814 return store;
815}
816
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000817const GRState* RegionStoreManager::AddRegionView(const GRState* St,
818 const MemRegion* View,
819 const MemRegion* Base) {
820 GRStateRef state(St, StateMgr);
821
822 // First, retrieve the region view of the base region.
823 RegionViewMapTy::data_type* d = state.get<RegionViewMapTy>(Base);
824 RegionViewTy L = d ? *d : RVFactory.GetEmptyList();
825
826 // Now add View to the region view.
827 L = RVFactory.Add(View, L);
828
829 // Create a new state with the new region view.
830 return state.set<RegionViewMapTy>(Base, L);
831}