blob: cc7715a98a098f4e9ab7e0da62313682007ecfdf [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 Xu1c96b242008-10-17 05:57:07 +000029typedef llvm::ImmutableMap<const MemRegion*, SVal> RegionBindingsTy;
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000030typedef llvm::ImmutableList<const MemRegion*> RegionViewTy;
31typedef llvm::ImmutableMap<const MemRegion*, RegionViewTy> RegionViewMapTy;
32
33static int RegionViewMapTyIndex = 0;
34
35namespace clang {
36template<> struct GRStateTrait<RegionViewMapTy>
37 : public GRStatePartialTrait<RegionViewMapTy> {
38 static void* GDMIndex() { return &RegionViewMapTyIndex; }
39};
40}
Zhongxing Xu17892752008-10-08 02:50:44 +000041
42namespace {
43
44class VISIBILITY_HIDDEN RegionStoreManager : public StoreManager {
45 RegionBindingsTy::Factory RBFactory;
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000046 RegionViewTy::Factory RVFactory;
47 RegionViewMapTy::Factory RVMFactory;
48
Zhongxing Xu17892752008-10-08 02:50:44 +000049 GRStateManager& StateMgr;
50 MemRegionManager MRMgr;
51
52public:
53 RegionStoreManager(GRStateManager& mgr)
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000054 : RBFactory(mgr.getAllocator()),
55 RVFactory(mgr.getAllocator()),
56 RVMFactory(mgr.getAllocator()),
57 StateMgr(mgr),
58 MRMgr(StateMgr.getAllocator()) {}
Zhongxing Xu17892752008-10-08 02:50:44 +000059
60 virtual ~RegionStoreManager() {}
61
Zhongxing Xu24194ef2008-10-24 01:38:55 +000062 MemRegionManager& getRegionManager() { return MRMgr; }
63
64 // FIXME: Is this function necessary?
65 SVal GetRegionSVal(Store St, const MemRegion* R) {
66 return Retrieve(St, loc::MemRegionVal(R));
67 }
Ted Kremenek4f090272008-10-27 21:54:31 +000068
Zhongxing Xuf22679e2008-11-07 10:38:33 +000069 Store BindCompoundLiteral(Store store, const CompoundLiteralExpr* CL, SVal V);
Zhongxing Xu24194ef2008-10-24 01:38:55 +000070
Zhongxing Xu143bf822008-10-25 14:18:57 +000071 SVal getLValueString(const GRState* St, const StringLiteral* S);
72
Zhongxing Xuf22679e2008-11-07 10:38:33 +000073 SVal getLValueCompoundLiteral(const GRState* St, const CompoundLiteralExpr*);
74
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +000075 SVal getLValueVar(const GRState* St, const VarDecl* VD);
76
77 SVal getLValueIvar(const GRState* St, const ObjCIvarDecl* D, SVal Base);
78
79 SVal getLValueField(const GRState* St, SVal Base, const FieldDecl* D);
80
Zhongxing Xub1d542a2008-10-24 01:09:32 +000081 SVal getLValueElement(const GRState* St, SVal Base, SVal Offset);
82
Zhongxing Xue8a964b2008-11-22 13:21:46 +000083 SVal getSizeInElements(const GRState* St, const MemRegion* R);
84
Zhongxing Xub1d542a2008-10-24 01:09:32 +000085 SVal ArrayToPointer(SVal Array);
86
Zhongxing Xucb529b52008-11-16 07:06:26 +000087 std::pair<const GRState*, SVal>
88 CastRegion(const GRState* St, SVal VoidPtr, QualType CastToTy, Stmt* CastE);
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000089
Zhongxing Xu24194ef2008-10-24 01:38:55 +000090 SVal Retrieve(Store S, Loc L, QualType T = QualType());
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +000091
Zhongxing Xu8485ec62008-10-21 06:27:32 +000092 Store Bind(Store St, Loc LV, SVal V);
Zhongxing Xu17892752008-10-08 02:50:44 +000093
Zhongxing Xu24194ef2008-10-24 01:38:55 +000094 Store Remove(Store store, Loc LV) {
95 // FIXME: Implement.
96 return store;
97 }
98
Zhongxing Xu17892752008-10-08 02:50:44 +000099 Store getInitialStore();
Ted Kremenek9deb0e32008-10-24 20:32:16 +0000100
101 /// getSelfRegion - Returns the region for the 'self' (Objective-C) or
102 /// 'this' object (C++). When used when analyzing a normal function this
103 /// method returns NULL.
104 const MemRegion* getSelfRegion(Store) {
105 assert (false && "Not implemented.");
106 return 0;
107 }
Zhongxing Xu17892752008-10-08 02:50:44 +0000108
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000109 Store RemoveDeadBindings(Store store, Stmt* Loc, const LiveVariables& Live,
110 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots,
Zhongxing Xu8916d5b2008-11-10 09:39:04 +0000111 LiveSymbolsTy& LSymbols, DeadSymbolsTy& DSymbols);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000112
Ted Kremenek42577d12008-11-12 19:18:35 +0000113 Store BindDecl(Store store, const VarDecl* VD, SVal* InitVal, unsigned Count);
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000114
Zhongxing Xu17892752008-10-08 02:50:44 +0000115 static inline RegionBindingsTy GetRegionBindings(Store store) {
116 return RegionBindingsTy(static_cast<const RegionBindingsTy::TreeTy*>(store));
117 }
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000118
Zhongxing Xu5b8b6f22008-10-24 04:33:15 +0000119 void print(Store store, std::ostream& Out, const char* nl, const char *sep);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000120
121 void iterBindings(Store store, BindingsHandler& f) {
122 // FIXME: Implement.
123 }
Zhongxing Xua82512a2008-10-24 08:42:28 +0000124
125private:
126 Loc getVarLoc(const VarDecl* VD) {
127 return loc::MemRegionVal(MRMgr.getVarRegion(VD));
128 }
129
Zhongxing Xuc3a05992008-11-19 11:06:24 +0000130 SymbolManager& getSymbolManager() { return StateMgr.getSymbolManager(); }
131
Zhongxing Xud463d442008-11-02 12:13:30 +0000132 Store InitializeArray(Store store, const TypedRegion* R, SVal Init);
133 Store BindArrayToVal(Store store, const TypedRegion* BaseR, SVal V);
Zhongxing Xuc3a05992008-11-19 11:06:24 +0000134 Store BindArrayToSymVal(Store store, const TypedRegion* BaseR);
135
Zhongxing Xud463d442008-11-02 12:13:30 +0000136 Store InitializeStruct(Store store, const TypedRegion* R, SVal Init);
137 Store BindStructToVal(Store store, const TypedRegion* BaseR, SVal V);
Zhongxing Xuc3a05992008-11-19 11:06:24 +0000138 Store BindStructToSymVal(Store store, const TypedRegion* BaseR);
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000139
140 SVal RetrieveStruct(Store store, const TypedRegion* R);
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +0000141 Store BindStruct(Store store, const TypedRegion* R, SVal V);
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000142 // Utility methods.
143 BasicValueFactory& getBasicVals() { return StateMgr.getBasicVals(); }
144 ASTContext& getContext() { return StateMgr.getContext(); }
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000145
146 const GRState* AddRegionView(const GRState* St,
147 const MemRegion* View, const MemRegion* Base);
Zhongxing Xu17892752008-10-08 02:50:44 +0000148};
149
150} // end anonymous namespace
151
Ted Kremenek95c7b002008-10-24 01:04:59 +0000152StoreManager* clang::CreateRegionStoreManager(GRStateManager& StMgr) {
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000153 return new RegionStoreManager(StMgr);
Ted Kremenek95c7b002008-10-24 01:04:59 +0000154}
155
Zhongxing Xu143bf822008-10-25 14:18:57 +0000156SVal RegionStoreManager::getLValueString(const GRState* St,
157 const StringLiteral* S) {
158 return loc::MemRegionVal(MRMgr.getStringRegion(S));
159}
160
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000161SVal RegionStoreManager::getLValueVar(const GRState* St, const VarDecl* VD) {
162 return loc::MemRegionVal(MRMgr.getVarRegion(VD));
163}
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000164
165SVal RegionStoreManager::getLValueCompoundLiteral(const GRState* St,
166 const CompoundLiteralExpr* CL) {
167 return loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL));
168}
169
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000170SVal RegionStoreManager::getLValueIvar(const GRState* St, const ObjCIvarDecl* D,
171 SVal Base) {
172 return UnknownVal();
173}
174
175SVal RegionStoreManager::getLValueField(const GRState* St, SVal Base,
176 const FieldDecl* D) {
177 if (Base.isUnknownOrUndef())
178 return Base;
179
180 Loc BaseL = cast<Loc>(Base);
181 const MemRegion* BaseR = 0;
182
183 switch (BaseL.getSubKind()) {
184 case loc::MemRegionKind:
185 BaseR = cast<loc::MemRegionVal>(BaseL).getRegion();
186 break;
187
188 case loc::SymbolValKind:
189 BaseR = MRMgr.getSymbolicRegion(cast<loc::SymbolVal>(&BaseL)->getSymbol());
190 break;
191
192 case loc::GotoLabelKind:
193 case loc::FuncValKind:
194 // These are anormal cases. Flag an undefined value.
195 return UndefinedVal();
196
197 case loc::ConcreteIntKind:
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000198 // While these seem funny, this can happen through casts.
199 // FIXME: What we should return is the field offset. For example,
200 // add the field offset to the integer value. That way funny things
201 // like this work properly: &(((struct foo *) 0xa)->f)
202 return Base;
203
204 default:
Zhongxing Xu13d1ee22008-11-07 08:57:30 +0000205 assert(0 && "Unhandled Base.");
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000206 return Base;
207 }
208
209 return loc::MemRegionVal(MRMgr.getFieldRegion(D, BaseR));
210}
211
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000212SVal RegionStoreManager::getLValueElement(const GRState* St,
213 SVal Base, SVal Offset) {
214 if (Base.isUnknownOrUndef())
215 return Base;
216
Zhongxing Xu4a1513e2008-10-27 12:23:17 +0000217 if (isa<loc::SymbolVal>(Base))
218 return Base;
219
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000220 loc::MemRegionVal& BaseL = cast<loc::MemRegionVal>(Base);
221
Zhongxing Xue4d13932008-11-13 09:48:44 +0000222 // Pointer of any type can be cast and used as array base. We do not support
223 // that case yet.
224 if (!isa<ElementRegion>(BaseL.getRegion())) {
225 // Record what we have seen in real code.
226 assert(isa<FieldRegion>(BaseL.getRegion()));
227 return UnknownVal();
228 }
229
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000230 // We expect BaseR is an ElementRegion, not a base VarRegion.
231
232 const ElementRegion* ElemR = cast<ElementRegion>(BaseL.getRegion());
233
234 SVal Idx = ElemR->getIndex();
235
236 nonloc::ConcreteInt *CI1, *CI2;
237
238 // Only handle integer indices for now.
239 if ((CI1 = dyn_cast<nonloc::ConcreteInt>(&Idx)) &&
240 (CI2 = dyn_cast<nonloc::ConcreteInt>(&Offset))) {
Zhongxing Xucc0d0ec2008-11-13 09:15:14 +0000241
242 // Temporary SVal to hold a potential signed APSInt.
243 SVal SignedInt;
244
245 // Index might be unsigned. We have to convert it to signed.
246 if (CI2->getValue().isUnsigned()) {
247 llvm::APSInt SI = CI2->getValue();
248 SI.setIsSigned(true);
249 SignedInt = nonloc::ConcreteInt(getBasicVals().getValue(SI));
250 CI2 = cast<nonloc::ConcreteInt>(&SignedInt);
251 }
252
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000253 SVal NewIdx = CI1->EvalBinOp(StateMgr.getBasicVals(), BinaryOperator::Add,
254 *CI2);
255 return loc::MemRegionVal(MRMgr.getElementRegion(NewIdx,
256 ElemR->getSuperRegion()));
257 }
258
259 return UnknownVal();
260}
261
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000262SVal RegionStoreManager::getSizeInElements(const GRState* St,
263 const MemRegion* R) {
264 if (const VarRegion* VR = dyn_cast<VarRegion>(R)) {
265 // Get the type of the variable.
266 QualType T = VR->getType(getContext());
267
268 // It must be of array type.
269 const ConstantArrayType* CAT = cast<ConstantArrayType>(T.getTypePtr());
270
271 // return the size as signed integer.
272 return NonLoc::MakeVal(getBasicVals(), CAT->getSize(), false);
273 }
274
275 if (const StringRegion* SR = dyn_cast<StringRegion>(R)) {
276 // FIXME: Unsupported yet.
277 SR = 0;
278 return UnknownVal();
279 }
280
281 if (const AnonTypedRegion* ATR = dyn_cast<AnonTypedRegion>(R)) {
282 // FIXME: Unsupported yet.
283 ATR = 0;
284 return UnknownVal();
285 }
286
287 if (const FieldRegion* FR = dyn_cast<FieldRegion>(R)) {
288 // FIXME: Unsupported yet.
289 FR = 0;
290 return UnknownVal();
291 }
292 printf("kidn = %d\n", R->getKind());
293 assert(0 && "Other regions are not supported yet.");
294}
295
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000296// Cast 'pointer to array' to 'pointer to the first element of array'.
297
298SVal RegionStoreManager::ArrayToPointer(SVal Array) {
299 const MemRegion* ArrayR = cast<loc::MemRegionVal>(&Array)->getRegion();
Zhongxing Xu143bf822008-10-25 14:18:57 +0000300 BasicValueFactory& BasicVals = StateMgr.getBasicVals();
301
Zhongxing Xua09300a2008-11-15 05:18:50 +0000302 nonloc::ConcreteInt Idx(BasicVals.getZeroWithPtrWidth(false));
Zhongxing Xu0b7e6422008-10-26 02:23:57 +0000303 ElementRegion* ER = MRMgr.getElementRegion(Idx, ArrayR);
304
305 return loc::MemRegionVal(ER);
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000306}
307
Zhongxing Xucb529b52008-11-16 07:06:26 +0000308std::pair<const GRState*, SVal>
309RegionStoreManager::CastRegion(const GRState* St, SVal VoidPtr,
310 QualType CastToTy, Stmt* CastE) {
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000311 if (const AllocaRegion* AR =
312 dyn_cast<AllocaRegion>(cast<loc::MemRegionVal>(VoidPtr).getRegion())) {
313
314 // Create a new region to attach type information to it.
315 const AnonTypedRegion* TR = MRMgr.getAnonTypedRegion(CastToTy, AR);
316
317 // Get the pointer to the first element.
318 nonloc::ConcreteInt Idx(getBasicVals().getZeroWithPtrWidth(false));
319 const ElementRegion* ER = MRMgr.getElementRegion(Idx, TR);
320
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000321 // Add a RegionView to base region.
Zhongxing Xucb529b52008-11-16 07:06:26 +0000322 return std::pair<const GRState*, SVal>(AddRegionView(St, TR, AR),
323 loc::MemRegionVal(ER));
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000324 }
325
326 // Default case.
Zhongxing Xucb529b52008-11-16 07:06:26 +0000327 return std::pair<const GRState*, SVal>(St, UnknownVal());
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000328}
329
Zhongxing Xu8485ec62008-10-21 06:27:32 +0000330SVal RegionStoreManager::Retrieve(Store S, Loc L, QualType T) {
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000331 assert(!isa<UnknownVal>(L) && "location unknown");
332 assert(!isa<UndefinedVal>(L) && "location undefined");
333
334 switch (L.getSubKind()) {
335 case loc::MemRegionKind: {
336 const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion();
337 assert(R && "bad region");
338
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000339 if (const TypedRegion* TR = dyn_cast<TypedRegion>(R))
340 if (TR->getType(getContext())->isStructureType())
341 return RetrieveStruct(S, TR);
342
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000343 RegionBindingsTy B(static_cast<const RegionBindingsTy::TreeTy*>(S));
344 RegionBindingsTy::data_type* V = B.lookup(R);
345 return V ? *V : UnknownVal();
346 }
347
348 case loc::SymbolValKind:
349 return UnknownVal();
350
351 case loc::ConcreteIntKind:
352 return UndefinedVal(); // As in BasicStoreManager.
353
354 case loc::FuncValKind:
355 return L;
356
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000357 default:
358 assert(false && "Invalid Location");
Ted Kremenekab7b32b2008-11-19 00:27:37 +0000359 return L;
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000360 }
361}
362
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000363SVal RegionStoreManager::RetrieveStruct(Store store, const TypedRegion* R) {
364 QualType T = R->getType(getContext());
365 assert(T->isStructureType());
366
367 const RecordType* RT = cast<RecordType>(T.getTypePtr());
368 RecordDecl* RD = RT->getDecl();
369 assert(RD->isDefinition());
370
371 llvm::ImmutableList<SVal> StructVal = getBasicVals().getEmptySValList();
372
373 for (int i = RD->getNumMembers() - 1; i >= 0; --i) {
374 FieldRegion* FR = MRMgr.getFieldRegion(RD->getMember(i), R);
375 RegionBindingsTy B(static_cast<const RegionBindingsTy::TreeTy*>(store));
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +0000376 RegionBindingsTy::data_type* data = B.lookup(FR);
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000377
378 SVal FieldValue = data ? *data : UnknownVal();
379
380 StructVal = getBasicVals().consVals(FieldValue, StructVal);
381 }
382
383 return NonLoc::MakeCompoundVal(T, StructVal, getBasicVals());
384}
385
Zhongxing Xu8485ec62008-10-21 06:27:32 +0000386Store RegionStoreManager::Bind(Store store, Loc LV, SVal V) {
Zhongxing Xu8fe63af2008-10-27 09:24:07 +0000387 if (LV.getSubKind() == loc::SymbolValKind)
388 return store;
389
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000390 assert(LV.getSubKind() == loc::MemRegionKind);
Zhongxing Xu17892752008-10-08 02:50:44 +0000391
Ted Kremenek993f1c72008-10-17 20:28:54 +0000392 const MemRegion* R = cast<loc::MemRegionVal>(LV).getRegion();
Zhongxing Xu17892752008-10-08 02:50:44 +0000393
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +0000394 assert(R);
395
396 if (const TypedRegion* TR = dyn_cast<TypedRegion>(R))
397 if (TR->getType(getContext())->isStructureType())
398 return BindStruct(store, TR, V);
Zhongxing Xu17892752008-10-08 02:50:44 +0000399
400 RegionBindingsTy B = GetRegionBindings(store);
401 return V.isUnknown()
402 ? RBFactory.Remove(B, R).getRoot()
403 : RBFactory.Add(B, R, V).getRoot();
404}
405
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +0000406Store RegionStoreManager::BindStruct(Store store, const TypedRegion* R, SVal V){
407 QualType T = R->getType(getContext());
408 assert(T->isStructureType());
409
410 const RecordType* RT = cast<RecordType>(T.getTypePtr());
411 RecordDecl* RD = RT->getDecl();
Zhongxing Xua4f28ff2008-11-13 08:41:36 +0000412
413 if (!RD->isDefinition()) {
Zhongxing Xuc3a05992008-11-19 11:06:24 +0000414 // This can only occur when a pointer of incomplete struct type is used as a
Zhongxing Xua4f28ff2008-11-13 08:41:36 +0000415 // function argument.
416 assert(V.isUnknown());
417 return store;
418 }
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +0000419
420 RegionBindingsTy B = GetRegionBindings(store);
421
Zhongxing Xud463d442008-11-02 12:13:30 +0000422 if (isa<UnknownVal>(V))
423 return BindStructToVal(store, R, UnknownVal());
424
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +0000425 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V);
426
427 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
428 RecordDecl::field_iterator FI = RD->field_begin(), FE = RD->field_end();
429
430 for (; FI != FE; ++FI, ++VI) {
431 assert(VI != VE);
432
433 FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);
434
435 B = RBFactory.Add(B, FR, *VI);
436 }
437
438 return B.getRoot();
439}
440
Zhongxing Xu17892752008-10-08 02:50:44 +0000441Store RegionStoreManager::getInitialStore() {
442 typedef LiveVariables::AnalysisDataTy LVDataTy;
443 LVDataTy& D = StateMgr.getLiveVariables().getAnalysisData();
444
445 Store St = RBFactory.GetEmptyMap().getRoot();
446
447 for (LVDataTy::decl_iterator I=D.begin_decl(), E=D.end_decl(); I != E; ++I) {
Douglas Gregor8e9bebd2008-10-21 16:13:35 +0000448 NamedDecl* ND = const_cast<NamedDecl*>(I->first);
Zhongxing Xu17892752008-10-08 02:50:44 +0000449
Douglas Gregor8e9bebd2008-10-21 16:13:35 +0000450 if (VarDecl* VD = dyn_cast<VarDecl>(ND)) {
Zhongxing Xu17892752008-10-08 02:50:44 +0000451 // Punt on static variables for now.
452 if (VD->getStorageClass() == VarDecl::Static)
453 continue;
454
Zhongxing Xuc3a05992008-11-19 11:06:24 +0000455 VarRegion* VR = MRMgr.getVarRegion(VD);
456
Zhongxing Xu17892752008-10-08 02:50:44 +0000457 QualType T = VD->getType();
458 // Only handle pointers and integers for now.
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000459 if (Loc::IsLocType(T) || T->isIntegerType()) {
Zhongxing Xu17892752008-10-08 02:50:44 +0000460 // Initialize globals and parameters to symbolic values.
461 // Initialize local variables to undefined.
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000462 SVal X = (VD->hasGlobalStorage() || isa<ParmVarDecl>(VD) ||
Zhongxing Xu17892752008-10-08 02:50:44 +0000463 isa<ImplicitParamDecl>(VD))
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000464 ? SVal::GetSymbolValue(StateMgr.getSymbolManager(), VD)
Zhongxing Xu17892752008-10-08 02:50:44 +0000465 : UndefinedVal();
466
Zhongxing Xu8485ec62008-10-21 06:27:32 +0000467 St = Bind(St, getVarLoc(VD), X);
Zhongxing Xuc3a05992008-11-19 11:06:24 +0000468 }
469 else if (T->isArrayType()) {
470 if (VD->hasGlobalStorage()) // Params cannot have array type.
471 St = BindArrayToSymVal(St, VR);
472 else
473 St = BindArrayToVal(St, VR, UndefinedVal());
474 }
475 else if (T->isStructureType()) {
476 if (VD->hasGlobalStorage() || isa<ParmVarDecl>(VD) ||
477 isa<ImplicitParamDecl>(VD))
478 St = BindStructToSymVal(St, VR);
479 else
480 St = BindStructToVal(St, VR, UndefinedVal());
Zhongxing Xu17892752008-10-08 02:50:44 +0000481 }
482 }
483 }
484 return St;
485}
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000486
Ted Kremenek42577d12008-11-12 19:18:35 +0000487Store RegionStoreManager::BindDecl(Store store, const VarDecl* VD,
488 SVal* InitVal, unsigned Count) {
489
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000490 BasicValueFactory& BasicVals = StateMgr.getBasicVals();
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000491
492 if (VD->hasGlobalStorage()) {
493 // Static global variables should not be visited here.
494 assert(!(VD->getStorageClass() == VarDecl::Static &&
495 VD->isFileVarDecl()));
496 // Process static variables.
497 if (VD->getStorageClass() == VarDecl::Static) {
Ted Kremenek42577d12008-11-12 19:18:35 +0000498 if (!InitVal) {
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000499 // Only handle pointer and integer static variables.
500
501 QualType T = VD->getType();
502
503 if (Loc::IsLocType(T))
Zhongxing Xu8485ec62008-10-21 06:27:32 +0000504 store = Bind(store, getVarLoc(VD),
505 loc::ConcreteInt(BasicVals.getValue(0, T)));
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000506
507 else if (T->isIntegerType())
Zhongxing Xu8485ec62008-10-21 06:27:32 +0000508 store = Bind(store, getVarLoc(VD),
509 loc::ConcreteInt(BasicVals.getValue(0, T)));
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +0000510
511 // Other types of static local variables are not handled yet.
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000512 } else {
Ted Kremenek42577d12008-11-12 19:18:35 +0000513 store = Bind(store, getVarLoc(VD), *InitVal);
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000514 }
515 }
516 } else {
517 // Process local variables.
518
519 QualType T = VD->getType();
520
Zhongxing Xua82512a2008-10-24 08:42:28 +0000521 VarRegion* VR = MRMgr.getVarRegion(VD);
522
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000523 if (Loc::IsLocType(T) || T->isIntegerType()) {
Ted Kremenek42577d12008-11-12 19:18:35 +0000524 SVal V = InitVal ? *InitVal : UndefinedVal();
Zhongxing Xua82512a2008-10-24 08:42:28 +0000525 store = Bind(store, loc::MemRegionVal(VR), V);
Ted Kremenek42577d12008-11-12 19:18:35 +0000526 }
527 else if (T->isArrayType()) {
528 if (!InitVal)
Zhongxing Xud463d442008-11-02 12:13:30 +0000529 store = BindArrayToVal(store, VR, UndefinedVal());
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +0000530 else
Ted Kremenek42577d12008-11-12 19:18:35 +0000531 store = InitializeArray(store, VR, *InitVal);
532 }
533 else if (T->isStructureType()) {
534 if (!InitVal)
Zhongxing Xud463d442008-11-02 12:13:30 +0000535 store = BindStructToVal(store, VR, UndefinedVal());
Zhongxing Xuaf0a8442008-10-31 10:53:01 +0000536 else
Ted Kremenek42577d12008-11-12 19:18:35 +0000537 store = InitializeStruct(store, VR, *InitVal);
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000538 }
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +0000539
540 // Other types of local variables are not handled yet.
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000541 }
542 return store;
543}
544
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000545Store RegionStoreManager::BindCompoundLiteral(Store store,
546 const CompoundLiteralExpr* CL,
547 SVal V) {
548 CompoundLiteralRegion* R = MRMgr.getCompoundLiteralRegion(CL);
549 store = Bind(store, loc::MemRegionVal(R), V);
550 return store;
551}
552
Zhongxing Xu8916d5b2008-11-10 09:39:04 +0000553Store RegionStoreManager::RemoveDeadBindings(Store store, Stmt* Loc,
554 const LiveVariables& Live,
555 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots,
556 LiveSymbolsTy& LSymbols, DeadSymbolsTy& DSymbols) {
557
558 RegionBindingsTy B = GetRegionBindings(store);
559 typedef SVal::symbol_iterator symbol_iterator;
560
561 // FIXME: Mark all region binding value's symbol as live. We also omit symbols
562 // in SymbolicRegions.
563 for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
564 SVal X = I.getData();
565 for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI)
566 LSymbols.insert(*SI);
567 }
568
569 return store;
570}
571
Zhongxing Xua071eb02008-10-24 06:01:33 +0000572void RegionStoreManager::print(Store store, std::ostream& Out,
573 const char* nl, const char *sep) {
574 llvm::raw_os_ostream OS(Out);
575 RegionBindingsTy B = GetRegionBindings(store);
576 OS << "Store:" << nl;
577
578 for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
579 OS << ' '; I.getKey()->print(OS); OS << " : ";
580 I.getData().print(OS); OS << nl;
581 }
Zhongxing Xu5b8b6f22008-10-24 04:33:15 +0000582}
Zhongxing Xua82512a2008-10-24 08:42:28 +0000583
Zhongxing Xud463d442008-11-02 12:13:30 +0000584Store RegionStoreManager::InitializeArray(Store store, const TypedRegion* R,
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +0000585 SVal Init) {
586 QualType T = R->getType(getContext());
587 assert(T->isArrayType());
588
589 ConstantArrayType* CAT = cast<ConstantArrayType>(T.getTypePtr());
590
591 llvm::APInt Size = CAT->getSize();
592
593 llvm::APInt i = llvm::APInt::getNullValue(Size.getBitWidth());
594
595 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(Init);
596
597 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
598
599 for (; i != Size; ++i) {
600 nonloc::ConcreteInt Idx(getBasicVals().getValue(llvm::APSInt(i)));
601
602 ElementRegion* ER = MRMgr.getElementRegion(Idx, R);
603
604 store = Bind(store, loc::MemRegionVal(ER), (VI!=VE) ? *VI : UndefinedVal());
605 // The init list might be shorter than the array decl.
606 if (VI != VE) ++VI;
607 }
608
609 return store;
610}
611
Zhongxing Xud463d442008-11-02 12:13:30 +0000612// Bind all elements of the array to some value.
613Store RegionStoreManager::BindArrayToVal(Store store, const TypedRegion* BaseR,
614 SVal V){
Zhongxing Xuea8a1852008-10-31 11:02:48 +0000615 QualType T = BaseR->getType(getContext());
Zhongxing Xua82512a2008-10-24 08:42:28 +0000616 assert(T->isArrayType());
617
Zhongxing Xua82512a2008-10-24 08:42:28 +0000618 // Only handle constant size array for now.
619 if (ConstantArrayType* CAT=dyn_cast<ConstantArrayType>(T.getTypePtr())) {
620
621 llvm::APInt Size = CAT->getSize();
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +0000622 llvm::APInt i = llvm::APInt::getNullValue(Size.getBitWidth());
623 for (; i != Size; ++i) {
Zhongxing Xuea8a1852008-10-31 11:02:48 +0000624 nonloc::ConcreteInt Idx(getBasicVals().getValue(llvm::APSInt(i)));
Zhongxing Xua82512a2008-10-24 08:42:28 +0000625
626 ElementRegion* ER = MRMgr.getElementRegion(Idx, BaseR);
627
Zhongxing Xu9b6ceb12008-11-18 13:11:04 +0000628 if (CAT->getElementType()->isStructureType())
629 store = BindStructToVal(store, ER, V);
630 else
631 store = Bind(store, loc::MemRegionVal(ER), V);
Zhongxing Xua82512a2008-10-24 08:42:28 +0000632 }
633 }
634
635 return store;
636}
637
Zhongxing Xuc3a05992008-11-19 11:06:24 +0000638Store RegionStoreManager::BindArrayToSymVal(Store store,
639 const TypedRegion* BaseR) {
640 QualType T = BaseR->getType(getContext());
641 assert(T->isArrayType());
642
643 if (ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(T.getTypePtr())) {
644 llvm::APInt Size = CAT->getSize();
645 llvm::APInt i = llvm::APInt::getNullValue(Size.getBitWidth());
646 for (; i != Size; ++i) {
647 nonloc::ConcreteInt Idx(getBasicVals().getValue(llvm::APSInt(i)));
648
649 ElementRegion* ER = MRMgr.getElementRegion(Idx, BaseR);
650
651 if (CAT->getElementType()->isStructureType()) {
652 store = BindStructToSymVal(store, ER);
653 }
654 else {
655 SVal V = SVal::getSymbolValue(getSymbolManager(), BaseR,
656 &Idx.getValue(), CAT->getElementType());
657 store = Bind(store, loc::MemRegionVal(ER), V);
658 }
659 }
660 }
661
662 return store;
663}
664
Zhongxing Xud463d442008-11-02 12:13:30 +0000665Store RegionStoreManager::InitializeStruct(Store store, const TypedRegion* R,
Zhongxing Xuea8a1852008-10-31 11:02:48 +0000666 SVal Init) {
Zhongxing Xuaf0a8442008-10-31 10:53:01 +0000667 QualType T = R->getType(getContext());
668 assert(T->isStructureType());
669
670 RecordType* RT = cast<RecordType>(T.getTypePtr());
671 RecordDecl* RD = RT->getDecl();
672 assert(RD->isDefinition());
673
674 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(Init);
675 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
676 RecordDecl::field_iterator FI = RD->field_begin(), FE = RD->field_end();
677
678 for (; FI != FE; ++FI) {
679 QualType FTy = (*FI)->getType();
680 FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);
681
682 if (Loc::IsLocType(FTy) || FTy->isIntegerType()) {
683 if (VI != VE) {
684 store = Bind(store, loc::MemRegionVal(FR), *VI);
685 ++VI;
686 } else
687 store = Bind(store, loc::MemRegionVal(FR), UndefinedVal());
688 }
689 else if (FTy->isArrayType()) {
690 if (VI != VE) {
691 store = InitializeArray(store, FR, *VI);
692 ++VI;
693 } else
Zhongxing Xud463d442008-11-02 12:13:30 +0000694 store = BindArrayToVal(store, FR, UndefinedVal());
Zhongxing Xuaf0a8442008-10-31 10:53:01 +0000695 }
696 else if (FTy->isStructureType()) {
697 if (VI != VE) {
698 store = InitializeStruct(store, FR, *VI);
699 ++VI;
700 } else
Zhongxing Xud463d442008-11-02 12:13:30 +0000701 store = BindStructToVal(store, FR, UndefinedVal());
Zhongxing Xuaf0a8442008-10-31 10:53:01 +0000702 }
703 }
704 return store;
705}
706
Zhongxing Xud463d442008-11-02 12:13:30 +0000707// Bind all fields of the struct to some value.
708Store RegionStoreManager::BindStructToVal(Store store, const TypedRegion* BaseR,
709 SVal V) {
Zhongxing Xuea8a1852008-10-31 11:02:48 +0000710 QualType T = BaseR->getType(getContext());
711 assert(T->isStructureType());
712
713 const RecordType* RT = cast<RecordType>(T.getTypePtr());
Zhongxing Xua82512a2008-10-24 08:42:28 +0000714 RecordDecl* RD = RT->getDecl();
715 assert(RD->isDefinition());
Zhongxing Xuea8a1852008-10-31 11:02:48 +0000716
717 RecordDecl::field_iterator I = RD->field_begin(), E = RD->field_end();
718
719 for (; I != E; ++I) {
Zhongxing Xua82512a2008-10-24 08:42:28 +0000720
721 QualType FTy = (*I)->getType();
722 FieldRegion* FR = MRMgr.getFieldRegion(*I, BaseR);
723
724 if (Loc::IsLocType(FTy) || FTy->isIntegerType()) {
Zhongxing Xud463d442008-11-02 12:13:30 +0000725 store = Bind(store, loc::MemRegionVal(FR), V);
Zhongxing Xua82512a2008-10-24 08:42:28 +0000726
727 } else if (FTy->isArrayType()) {
Zhongxing Xud463d442008-11-02 12:13:30 +0000728 store = BindArrayToVal(store, FR, V);
Zhongxing Xua82512a2008-10-24 08:42:28 +0000729
730 } else if (FTy->isStructureType()) {
Zhongxing Xud463d442008-11-02 12:13:30 +0000731 store = BindStructToVal(store, FR, V);
Zhongxing Xua82512a2008-10-24 08:42:28 +0000732 }
733 }
734
735 return store;
736}
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000737
Zhongxing Xuc3a05992008-11-19 11:06:24 +0000738Store RegionStoreManager::BindStructToSymVal(Store store,
739 const TypedRegion* BaseR) {
740 QualType T = BaseR->getType(getContext());
741 assert(T->isStructureType());
742
743 const RecordType* RT = cast<RecordType>(T.getTypePtr());
744 RecordDecl* RD = RT->getDecl();
745 assert(RD->isDefinition());
746
747 RecordDecl::field_iterator I = RD->field_begin(), E = RD->field_end();
748
749 for (; I != E; ++I) {
750 QualType FTy = (*I)->getType();
751 FieldRegion* FR = MRMgr.getFieldRegion(*I, BaseR);
752
753 if (Loc::IsLocType(FTy) || FTy->isIntegerType()) {
754 store = Bind(store, loc::MemRegionVal(FR),
755 SVal::getSymbolValue(getSymbolManager(), BaseR, *I, FTy));
756 }
757 else if (FTy->isArrayType()) {
758 store = BindArrayToSymVal(store, FR);
759 }
760 else if (FTy->isStructureType()) {
761 store = BindStructToSymVal(store, FR);
762 }
763 }
764
765 return store;
766}
767
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000768const GRState* RegionStoreManager::AddRegionView(const GRState* St,
769 const MemRegion* View,
770 const MemRegion* Base) {
771 GRStateRef state(St, StateMgr);
772
773 // First, retrieve the region view of the base region.
774 RegionViewMapTy::data_type* d = state.get<RegionViewMapTy>(Base);
775 RegionViewTy L = d ? *d : RVFactory.GetEmptyList();
776
777 // Now add View to the region view.
778 L = RVFactory.Add(View, L);
779
780 // Create a new state with the new region view.
781 return state.set<RegionViewMapTy>(Base, L);
782}