 |
|
 |
|
| Files: |
1 |
|
Branches Taken: |
79.2% |
61 / 77 |
| Generated: |
2010-02-10 01:31 |
|
Branches Executed: |
100.0% |
77 / 77 |
| |
|
Line Coverage: |
91.6% |
98 / 107 |
| |
 |
|
 |
1 : //== Store.cpp - Interface for maps from Locations to Values ----*- 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 defined the types Store and StoreManager.
11 : //
12 : //===----------------------------------------------------------------------===//
13 :
14 : #include "clang/Checker/PathSensitive/Store.h"
15 : #include "clang/Checker/PathSensitive/GRState.h"
16 : #include "clang/AST/CharUnits.h"
17 :
18 : using namespace clang;
19 :
20 2138: StoreManager::StoreManager(GRStateManager &stateMgr)
21 : : ValMgr(stateMgr.getValueManager()), StateMgr(stateMgr),
22 2138: MRMgr(ValMgr.getRegionManager()), Ctx(stateMgr.getContext()) {}
23 :
24 : const MemRegion *StoreManager::MakeElementRegion(const MemRegion *Base,
25 579: QualType EleTy, uint64_t index) {
26 579: SVal idx = ValMgr.makeArrayIndex(index);
27 579: return MRMgr.getElementRegion(EleTy, idx, Base, ValMgr.getContext());
28 : }
29 :
30 : // FIXME: Merge with the implementation of the same method in MemRegion.cpp
31 18: static bool IsCompleteType(ASTContext &Ctx, QualType Ty) {
3: branch 2 taken
15: branch 3 taken
32 18: if (const RecordType *RT = Ty->getAs<RecordType>()) {
33 3: const RecordDecl *D = RT->getDecl();
3: branch 1 taken
0: branch 2 not taken
34 3: if (!D->getDefinition(Ctx))
35 3: return false;
36 : }
37 :
38 15: return true;
39 : }
40 :
41 1645: const MemRegion *StoreManager::CastRegion(const MemRegion *R, QualType CastToTy) {
42 :
43 1645: ASTContext& Ctx = StateMgr.getContext();
44 :
45 : // Handle casts to Objective-C objects.
612: branch 2 taken
1033: branch 3 taken
46 1645: if (CastToTy->isObjCObjectPointerType())
47 612: return R->StripCasts();
48 :
10: branch 2 taken
1023: branch 3 taken
49 1033: if (CastToTy->isBlockPointerType()) {
50 : // FIXME: We may need different solutions, depending on the symbol
51 : // involved. Blocks can be casted to/from 'id', as they can be treated
52 : // as Objective-C objects. This could possibly be handled by enhancing
53 : // our reasoning of downcasts of symbolic objects.
10: branch 1 taken
0: branch 2 not taken
10: branch 4 taken
0: branch 5 not taken
10: branch 6 taken
0: branch 7 not taken
54 10: if (isa<CodeTextRegion>(R) || isa<SymbolicRegion>(R))
55 10: return R;
56 :
57 : // We don't know what to make of it. Return a NULL region, which
58 : // will be interpretted as UnknownVal.
59 0: return NULL;
60 : }
61 :
62 : // Now assume we are casting from pointer to pointer. Other cases should
63 : // already be handled.
64 1023: QualType PointeeTy = CastToTy->getAs<PointerType>()->getPointeeType();
65 1023: QualType CanonPointeeTy = Ctx.getCanonicalType(PointeeTy);
66 :
67 : // Handle casts to void*. We just pass the region through.
441: branch 3 taken
582: branch 4 taken
68 1023: if (CanonPointeeTy.getLocalUnqualifiedType() == Ctx.VoidTy)
69 441: return R;
70 :
71 : // Handle casts from compatible types.
514: branch 1 taken
68: branch 2 taken
72 582: if (R->isBoundable())
340: branch 1 taken
174: branch 2 taken
73 514: if (const TypedRegion *TR = dyn_cast<TypedRegion>(R)) {
74 340: QualType ObjTy = Ctx.getCanonicalType(TR->getValueType(Ctx));
2: branch 1 taken
338: branch 2 taken
75 340: if (CanonPointeeTy == ObjTy)
76 2: return R;
77 : }
78 :
79 : // Process region cast according to the kind of the region being cast.
0: branch 1 not taken
0: branch 2 not taken
432: branch 3 taken
148: branch 4 taken
0: branch 5 not taken
80 580: switch (R->getKind()) {
81 : case MemRegion::CXXThisRegionKind:
82 : case MemRegion::GenericMemSpaceRegionKind:
83 : case MemRegion::StackLocalsSpaceRegionKind:
84 : case MemRegion::StackArgumentsSpaceRegionKind:
85 : case MemRegion::HeapSpaceRegionKind:
86 : case MemRegion::UnknownSpaceRegionKind:
87 : case MemRegion::GlobalsSpaceRegionKind: {
88 0: assert(0 && "Invalid region cast");
89 : break;
90 : }
91 :
92 : case MemRegion::FunctionTextRegionKind:
93 : case MemRegion::BlockTextRegionKind:
94 : case MemRegion::BlockDataRegionKind: {
95 : // CodeTextRegion should be cast to only a function or block pointer type,
96 : // although they can in practice be casted to anything, e.g, void*, char*,
97 : // etc.
98 : // Just return the region.
99 0: return R;
100 : }
101 :
102 : case MemRegion::StringRegionKind:
103 : // FIXME: Need to handle arbitrary downcasts.
104 : case MemRegion::SymbolicRegionKind:
105 : case MemRegion::AllocaRegionKind:
106 : case MemRegion::CompoundLiteralRegionKind:
107 : case MemRegion::FieldRegionKind:
108 : case MemRegion::ObjCIvarRegionKind:
109 : case MemRegion::VarRegionKind:
110 : case MemRegion::CXXObjectRegionKind:
111 432: return MakeElementRegion(R, PointeeTy);
112 :
113 : case MemRegion::ElementRegionKind: {
114 : // If we are casting from an ElementRegion to another type, the
115 : // algorithm is as follows:
116 : //
117 : // (1) Compute the "raw offset" of the ElementRegion from the
118 : // base region. This is done by calling 'getAsRawOffset()'.
119 : //
120 : // (2a) If we get a 'RegionRawOffset' after calling
121 : // 'getAsRawOffset()', determine if the absolute offset
122 : // can be exactly divided into chunks of the size of the
123 : // casted-pointee type. If so, create a new ElementRegion with
124 : // the pointee-cast type as the new ElementType and the index
125 : // being the offset divded by the chunk size. If not, create
126 : // a new ElementRegion at offset 0 off the raw offset region.
127 : //
128 : // (2b) If we don't a get a 'RegionRawOffset' after calling
129 : // 'getAsRawOffset()', it means that we are at offset 0.
130 : //
131 : // FIXME: Handle symbolic raw offsets.
132 :
133 148: const ElementRegion *elementR = cast<ElementRegion>(R);
134 148: const RegionRawOffset &rawOff = elementR->getAsRawOffset();
135 148: const MemRegion *baseR = rawOff.getRegion();
136 :
137 : // If we cannot compute a raw offset, throw up our hands and return
138 : // a NULL MemRegion*.
4: branch 0 taken
144: branch 1 taken
139 148: if (!baseR)
140 4: return NULL;
141 :
142 144: CharUnits off = CharUnits::fromQuantity(rawOff.getByteOffset());
143 :
126: branch 1 taken
18: branch 2 taken
144 144: if (off.isZero()) {
145 : // Edge case: we are at 0 bytes off the beginning of baseR. We
146 : // check to see if type we are casting to is the same as the base
147 : // region. If so, just return the base region.
108: branch 1 taken
18: branch 2 taken
148 126: if (const TypedRegion *TR = dyn_cast<TypedRegion>(baseR)) {
149 108: QualType ObjTy = Ctx.getCanonicalType(TR->getValueType(Ctx));
150 108: QualType CanonPointeeTy = Ctx.getCanonicalType(PointeeTy);
0: branch 1 not taken
108: branch 2 taken
151 108: if (CanonPointeeTy == ObjTy)
152 0: return baseR;
153 : }
154 :
155 : // Otherwise, create a new ElementRegion at offset 0.
156 126: return MakeElementRegion(baseR, PointeeTy);
157 : }
158 :
159 : // We have a non-zero offset from the base region. We want to determine
160 : // if the offset can be evenly divided by sizeof(PointeeTy). If so,
161 : // we create an ElementRegion whose index is that value. Otherwise, we
162 : // create two ElementRegions, one that reflects a raw offset and the other
163 : // that reflects the cast.
164 :
165 : // Compute the index for the new ElementRegion.
166 18: int64_t newIndex = 0;
167 18: const MemRegion *newSuperR = 0;
168 :
169 : // We can only compute sizeof(PointeeTy) if it is a complete type.
15: branch 1 taken
3: branch 2 taken
170 18: if (IsCompleteType(Ctx, PointeeTy)) {
171 : // Compute the size in **bytes**.
172 15: CharUnits pointeeTySize = Ctx.getTypeSizeInChars(PointeeTy);
173 :
174 : // Is the offset a multiple of the size? If so, we can layer the
175 : // ElementRegion (with elementType == PointeeTy) directly on top of
176 : // the base region.
15: branch 1 taken
0: branch 2 not taken
177 15: if (off % pointeeTySize == 0) {
178 15: newIndex = off / pointeeTySize;
179 15: newSuperR = baseR;
180 : }
181 : }
182 :
3: branch 0 taken
15: branch 1 taken
183 18: if (!newSuperR) {
184 : // Create an intermediate ElementRegion to represent the raw byte.
185 : // This will be the super region of the final ElementRegion.
186 3: newSuperR = MakeElementRegion(baseR, Ctx.CharTy, off.getQuantity());
187 : }
188 :
189 18: return MakeElementRegion(newSuperR, PointeeTy, newIndex);
190 : }
191 : }
192 :
193 0: assert(0 && "unreachable");
194 : return 0;
195 : }
196 :
197 :
198 : /// CastRetrievedVal - Used by subclasses of StoreManager to implement
199 : /// implicit casts that arise from loads from regions that are reinterpreted
200 : /// as another region.
201 : SVal StoreManager::CastRetrievedVal(SVal V, const TypedRegion *R,
202 18164: QualType castTy, bool performTestOnly) {
203 :
10755: branch 1 taken
7409: branch 2 taken
204 18164: if (castTy.isNull())
205 10755: return V;
206 :
207 7409: ASTContext &Ctx = ValMgr.getContext();
208 :
3253: branch 0 taken
4156: branch 1 taken
209 7409: if (performTestOnly) {
210 : // Automatically translate references to pointers.
211 3253: QualType T = R->getValueType(Ctx);
0: branch 2 not taken
3253: branch 3 taken
212 3253: if (const ReferenceType *RT = T->getAs<ReferenceType>())
213 0: T = Ctx.getPointerType(RT->getPointeeType());
214 :
0: branch 2 not taken
3253: branch 3 taken
215 3253: assert(ValMgr.getContext().hasSameUnqualifiedType(castTy, T));
216 3253: return V;
217 : }
218 :
2174: branch 1 taken
1982: branch 2 taken
219 4156: if (const Loc *L = dyn_cast<Loc>(&V))
220 2174: return ValMgr.getSValuator().EvalCastL(*L, castTy);
1826: branch 1 taken
156: branch 2 taken
221 1982: else if (const NonLoc *NL = dyn_cast<NonLoc>(&V))
222 1826: return ValMgr.getSValuator().EvalCastNL(*NL, castTy);
223 :
224 156: return V;
225 : }
226 :
227 : Store StoreManager::InvalidateRegions(Store store,
228 : const MemRegion * const *I,
229 : const MemRegion * const *End,
230 : const Expr *E, unsigned Count,
231 313: InvalidatedSymbols *IS) {
379: branch 0 taken
313: branch 1 taken
232 692: for ( ; I != End ; ++I)
233 379: store = InvalidateRegion(store, *I, E, Count, IS);
234 :
235 313: return store;
236 : }
237 :
238 527: SVal StoreManager::getLValueFieldOrIvar(const Decl* D, SVal Base) {
6: branch 1 taken
521: branch 2 taken
239 527: if (Base.isUnknownOrUndef())
240 6: return Base;
241 :
242 521: Loc BaseL = cast<Loc>(Base);
243 521: const MemRegion* BaseR = 0;
244 :
521: branch 1 taken
0: branch 2 not taken
0: branch 3 not taken
0: branch 4 not taken
245 521: switch (BaseL.getSubKind()) {
246 : case loc::MemRegionKind:
247 521: BaseR = cast<loc::MemRegionVal>(BaseL).getRegion();
248 : break;
249 :
250 : case loc::GotoLabelKind:
251 : // These are anormal cases. Flag an undefined value.
252 0: return UndefinedVal();
253 :
254 : case loc::ConcreteIntKind:
255 : // While these seem funny, this can happen through casts.
256 : // FIXME: What we should return is the field offset. For example,
257 : // add the field offset to the integer value. That way funny things
258 : // like this work properly: &(((struct foo *) 0xa)->f)
259 0: return Base;
260 :
261 : default:
262 0: assert(0 && "Unhandled Base.");
263 : return Base;
264 : }
265 :
266 : // NOTE: We must have this check first because ObjCIvarDecl is a subclass
267 : // of FieldDecl.
148: branch 1 taken
373: branch 2 taken
268 521: if (const ObjCIvarDecl *ID = dyn_cast<ObjCIvarDecl>(D))
269 148: return loc::MemRegionVal(MRMgr.getObjCIvarRegion(ID, BaseR));
270 :
271 373: return loc::MemRegionVal(MRMgr.getFieldRegion(cast<FieldDecl>(D), BaseR));
272 : }
273 :
274 : SVal StoreManager::getLValueElement(QualType elementType, SVal Offset,
275 445: SVal Base) {
276 :
277 : // If the base is an unknown or undefined value, just return it back.
278 : // FIXME: For absolute pointer addresses, we just return that value back as
279 : // well, although in reality we should return the offset added to that
280 : // value.
445: branch 1 taken
0: branch 2 not taken
2: branch 4 taken
443: branch 5 taken
2: branch 6 taken
443: branch 7 taken
281 445: if (Base.isUnknownOrUndef() || isa<loc::ConcreteInt>(Base))
282 2: return Base;
283 :
284 : // Only handle integer offsets... for now.
20: branch 1 taken
423: branch 2 taken
285 443: if (!isa<nonloc::ConcreteInt>(Offset))
286 20: return UnknownVal();
287 :
288 423: const MemRegion* BaseRegion = cast<loc::MemRegionVal>(Base).getRegion();
289 :
290 : // Pointer of any type can be cast and used as array base.
291 423: const ElementRegion *ElemR = dyn_cast<ElementRegion>(BaseRegion);
292 :
293 : // Convert the offset to the appropriate size and signedness.
294 423: Offset = ValMgr.convertToArrayIndex(Offset);
295 :
233: branch 0 taken
190: branch 1 taken
296 423: if (!ElemR) {
297 : //
298 : // If the base region is not an ElementRegion, create one.
299 : // This can happen in the following example:
300 : //
301 : // char *p = __builtin_alloc(10);
302 : // p[1] = 8;
303 : //
304 : // Observe that 'p' binds to an AllocaRegion.
305 : //
306 : return loc::MemRegionVal(MRMgr.getElementRegion(elementType, Offset,
307 233: BaseRegion, Ctx));
308 : }
309 :
310 190: SVal BaseIdx = ElemR->getIndex();
311 :
38: branch 1 taken
152: branch 2 taken
312 190: if (!isa<nonloc::ConcreteInt>(BaseIdx))
313 38: return UnknownVal();
314 :
315 152: const llvm::APSInt& BaseIdxI = cast<nonloc::ConcreteInt>(BaseIdx).getValue();
316 152: const llvm::APSInt& OffI = cast<nonloc::ConcreteInt>(Offset).getValue();
0: branch 1 not taken
152: branch 2 taken
317 152: assert(BaseIdxI.isSigned());
318 :
319 : // Compute the new index.
320 : SVal NewIdx = nonloc::ConcreteInt(
321 152: ValMgr.getBasicValueFactory().getValue(BaseIdxI + OffI));
322 :
323 : // Construct the new ElementRegion.
324 152: const MemRegion *ArrayR = ElemR->getSuperRegion();
325 : return loc::MemRegionVal(MRMgr.getElementRegion(elementType, NewIdx, ArrayR,
326 152: Ctx));
327 : }
Generated: 2010-02-10 01:31 by zcov