blob: 9183fd782fff6ae3f3aac4e9d971cba2a2dce0f1 [file] [log] [blame]
Zhongxing Xu79c57f82008-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"
19#include "clang/Analysis/Analyses/LiveVariables.h"
20
21#include "llvm/ADT/ImmutableMap.h"
22#include "llvm/Support/Compiler.h"
23
24using namespace clang;
25
Zhongxing Xu097fc982008-10-17 05:57:07 +000026typedef llvm::ImmutableMap<const MemRegion*, SVal> RegionBindingsTy;
Zhongxing Xu79c57f82008-10-08 02:50:44 +000027
28namespace {
29
30class VISIBILITY_HIDDEN RegionStoreManager : public StoreManager {
31 RegionBindingsTy::Factory RBFactory;
32 GRStateManager& StateMgr;
33 MemRegionManager MRMgr;
34
35public:
36 RegionStoreManager(GRStateManager& mgr)
37 : StateMgr(mgr), MRMgr(StateMgr.getAllocator()) {}
38
39 virtual ~RegionStoreManager() {}
40
Zhongxing Xu6f1b5152008-10-22 13:44:38 +000041 SVal getLValueVar(const GRState* St, const VarDecl* VD);
42
43 SVal getLValueIvar(const GRState* St, const ObjCIvarDecl* D, SVal Base);
44
45 SVal getLValueField(const GRState* St, SVal Base, const FieldDecl* D);
46
Zhongxing Xu73249322008-10-21 06:27:32 +000047 SVal Retrieve(Store S, Loc L, QualType T);
Zhongxing Xu6f1b5152008-10-22 13:44:38 +000048
Zhongxing Xu73249322008-10-21 06:27:32 +000049 Store Bind(Store St, Loc LV, SVal V);
Zhongxing Xu79c57f82008-10-08 02:50:44 +000050
51 Store getInitialStore();
52
Zhongxing Xue3954d12008-10-21 05:29:26 +000053 Store AddDecl(Store store, const VarDecl* VD, Expr* Ex, SVal InitVal,
54 unsigned Count);
55
56 Loc getVarLoc(const VarDecl* VD) {
57 return loc::MemRegionVal(MRMgr.getVarRegion(VD));
58 }
59
60 Loc getElementLoc(const VarDecl* VD, SVal Idx);
61
Zhongxing Xu79c57f82008-10-08 02:50:44 +000062 static inline RegionBindingsTy GetRegionBindings(Store store) {
63 return RegionBindingsTy(static_cast<const RegionBindingsTy::TreeTy*>(store));
64 }
65};
66
67} // end anonymous namespace
68
Zhongxing Xue3954d12008-10-21 05:29:26 +000069Loc RegionStoreManager::getElementLoc(const VarDecl* VD, SVal Idx) {
70 MemRegion* R = MRMgr.getVarRegion(VD);
71 ElementRegion* ER = MRMgr.getElementRegion(Idx, R);
72 return loc::MemRegionVal(ER);
73}
74
Zhongxing Xu6f1b5152008-10-22 13:44:38 +000075SVal RegionStoreManager::getLValueVar(const GRState* St, const VarDecl* VD) {
76 return loc::MemRegionVal(MRMgr.getVarRegion(VD));
77}
78
79SVal RegionStoreManager::getLValueIvar(const GRState* St, const ObjCIvarDecl* D,
80 SVal Base) {
81 return UnknownVal();
82}
83
84SVal RegionStoreManager::getLValueField(const GRState* St, SVal Base,
85 const FieldDecl* D) {
86 if (Base.isUnknownOrUndef())
87 return Base;
88
89 Loc BaseL = cast<Loc>(Base);
90 const MemRegion* BaseR = 0;
91
92 switch (BaseL.getSubKind()) {
93 case loc::MemRegionKind:
94 BaseR = cast<loc::MemRegionVal>(BaseL).getRegion();
95 break;
96
97 case loc::SymbolValKind:
98 BaseR = MRMgr.getSymbolicRegion(cast<loc::SymbolVal>(&BaseL)->getSymbol());
99 break;
100
101 case loc::GotoLabelKind:
102 case loc::FuncValKind:
103 // These are anormal cases. Flag an undefined value.
104 return UndefinedVal();
105
106 case loc::ConcreteIntKind:
107 case loc::StringLiteralValKind:
108 // While these seem funny, this can happen through casts.
109 // FIXME: What we should return is the field offset. For example,
110 // add the field offset to the integer value. That way funny things
111 // like this work properly: &(((struct foo *) 0xa)->f)
112 return Base;
113
114 default:
115 assert("Unhandled Base.");
116 return Base;
117 }
118
119 return loc::MemRegionVal(MRMgr.getFieldRegion(D, BaseR));
120}
121
Zhongxing Xu73249322008-10-21 06:27:32 +0000122SVal RegionStoreManager::Retrieve(Store S, Loc L, QualType T) {
Zhongxing Xue3954d12008-10-21 05:29:26 +0000123 assert(!isa<UnknownVal>(L) && "location unknown");
124 assert(!isa<UndefinedVal>(L) && "location undefined");
125
126 switch (L.getSubKind()) {
127 case loc::MemRegionKind: {
128 const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion();
129 assert(R && "bad region");
130
131 RegionBindingsTy B(static_cast<const RegionBindingsTy::TreeTy*>(S));
132 RegionBindingsTy::data_type* V = B.lookup(R);
133 return V ? *V : UnknownVal();
134 }
135
136 case loc::SymbolValKind:
137 return UnknownVal();
138
139 case loc::ConcreteIntKind:
140 return UndefinedVal(); // As in BasicStoreManager.
141
142 case loc::FuncValKind:
143 return L;
144
145 case loc::StringLiteralValKind:
146 return UnknownVal();
147
148 default:
149 assert(false && "Invalid Location");
150 break;
151 }
152}
153
Zhongxing Xu73249322008-10-21 06:27:32 +0000154Store RegionStoreManager::Bind(Store store, Loc LV, SVal V) {
Zhongxing Xu097fc982008-10-17 05:57:07 +0000155 assert(LV.getSubKind() == loc::MemRegionKind);
Zhongxing Xu79c57f82008-10-08 02:50:44 +0000156
Ted Kremenek38a4b4b2008-10-17 20:28:54 +0000157 const MemRegion* R = cast<loc::MemRegionVal>(LV).getRegion();
Zhongxing Xu79c57f82008-10-08 02:50:44 +0000158
159 if (!R)
160 return store;
161
162 RegionBindingsTy B = GetRegionBindings(store);
163 return V.isUnknown()
164 ? RBFactory.Remove(B, R).getRoot()
165 : RBFactory.Add(B, R, V).getRoot();
166}
167
168Store RegionStoreManager::getInitialStore() {
169 typedef LiveVariables::AnalysisDataTy LVDataTy;
170 LVDataTy& D = StateMgr.getLiveVariables().getAnalysisData();
171
172 Store St = RBFactory.GetEmptyMap().getRoot();
173
174 for (LVDataTy::decl_iterator I=D.begin_decl(), E=D.end_decl(); I != E; ++I) {
Douglas Gregord2baafd2008-10-21 16:13:35 +0000175 NamedDecl* ND = const_cast<NamedDecl*>(I->first);
Zhongxing Xu79c57f82008-10-08 02:50:44 +0000176
Douglas Gregord2baafd2008-10-21 16:13:35 +0000177 if (VarDecl* VD = dyn_cast<VarDecl>(ND)) {
Zhongxing Xu79c57f82008-10-08 02:50:44 +0000178 // Punt on static variables for now.
179 if (VD->getStorageClass() == VarDecl::Static)
180 continue;
181
182 QualType T = VD->getType();
183 // Only handle pointers and integers for now.
Zhongxing Xu097fc982008-10-17 05:57:07 +0000184 if (Loc::IsLocType(T) || T->isIntegerType()) {
Zhongxing Xu79c57f82008-10-08 02:50:44 +0000185 // Initialize globals and parameters to symbolic values.
186 // Initialize local variables to undefined.
Zhongxing Xu097fc982008-10-17 05:57:07 +0000187 SVal X = (VD->hasGlobalStorage() || isa<ParmVarDecl>(VD) ||
Zhongxing Xu79c57f82008-10-08 02:50:44 +0000188 isa<ImplicitParamDecl>(VD))
Zhongxing Xu097fc982008-10-17 05:57:07 +0000189 ? SVal::GetSymbolValue(StateMgr.getSymbolManager(), VD)
Zhongxing Xu79c57f82008-10-08 02:50:44 +0000190 : UndefinedVal();
191
Zhongxing Xu73249322008-10-21 06:27:32 +0000192 St = Bind(St, getVarLoc(VD), X);
Zhongxing Xu79c57f82008-10-08 02:50:44 +0000193 }
194 }
195 }
196 return St;
197}
Zhongxing Xue3954d12008-10-21 05:29:26 +0000198
199Store RegionStoreManager::AddDecl(Store store,
200 const VarDecl* VD, Expr* Ex,
201 SVal InitVal, unsigned Count) {
202 BasicValueFactory& BasicVals = StateMgr.getBasicVals();
203 SymbolManager& SymMgr = StateMgr.getSymbolManager();
204
205 if (VD->hasGlobalStorage()) {
206 // Static global variables should not be visited here.
207 assert(!(VD->getStorageClass() == VarDecl::Static &&
208 VD->isFileVarDecl()));
209 // Process static variables.
210 if (VD->getStorageClass() == VarDecl::Static) {
211 if (!Ex) {
212 // Only handle pointer and integer static variables.
213
214 QualType T = VD->getType();
215
216 if (Loc::IsLocType(T))
Zhongxing Xu73249322008-10-21 06:27:32 +0000217 store = Bind(store, getVarLoc(VD),
218 loc::ConcreteInt(BasicVals.getValue(0, T)));
Zhongxing Xue3954d12008-10-21 05:29:26 +0000219
220 else if (T->isIntegerType())
Zhongxing Xu73249322008-10-21 06:27:32 +0000221 store = Bind(store, getVarLoc(VD),
222 loc::ConcreteInt(BasicVals.getValue(0, T)));
Zhongxing Xue3954d12008-10-21 05:29:26 +0000223 else
224 assert("ignore other types of variables");
225 } else {
Zhongxing Xu73249322008-10-21 06:27:32 +0000226 store = Bind(store, getVarLoc(VD), InitVal);
Zhongxing Xue3954d12008-10-21 05:29:26 +0000227 }
228 }
229 } else {
230 // Process local variables.
231
232 QualType T = VD->getType();
233
234 if (Loc::IsLocType(T) || T->isIntegerType()) {
235 SVal V = Ex ? InitVal : UndefinedVal();
236 if (Ex && InitVal.isUnknown()) {
237 // "Conjured" symbols.
238 SymbolID Sym = SymMgr.getConjuredSymbol(Ex, Count);
239 V = Loc::IsLocType(Ex->getType())
240 ? cast<SVal>(loc::SymbolVal(Sym))
241 : cast<SVal>(nonloc::SymbolVal(Sym));
242 }
Zhongxing Xu73249322008-10-21 06:27:32 +0000243 store = Bind(store, getVarLoc(VD), V);
Zhongxing Xue3954d12008-10-21 05:29:26 +0000244
245 } else if (T->isArrayType()) {
246 // Only handle constant size array.
247 if (ConstantArrayType* CAT=dyn_cast<ConstantArrayType>(T.getTypePtr())) {
248
249 llvm::APInt Size = CAT->getSize();
250
251 for (llvm::APInt i = llvm::APInt::getNullValue(Size.getBitWidth());
252 i != Size; ++i) {
253 nonloc::ConcreteInt Idx(BasicVals.getValue(llvm::APSInt(i)));
Zhongxing Xu73249322008-10-21 06:27:32 +0000254 store = Bind(store, getElementLoc(VD, Idx), UndefinedVal());
Zhongxing Xue3954d12008-10-21 05:29:26 +0000255 }
256 }
257 } else if (T->isStructureType()) {
258 // FIXME: Implement struct initialization.
259 }
260 }
261 return store;
262}
263