 |
|
 |
|
| Files: |
1 |
|
Branches Taken: |
78.3% |
396 / 506 |
| Generated: |
2010-02-10 01:31 |
|
Branches Executed: |
92.1% |
466 / 506 |
| |
|
Line Coverage: |
86.3% |
626 / 725 |
| |
 |
|
 |
1 : //== 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/Checker/PathSensitive/MemRegion.h"
18 : #include "clang/Analysis/AnalysisContext.h"
19 : #include "clang/Checker/PathSensitive/GRState.h"
20 : #include "clang/Checker/PathSensitive/GRStateTrait.h"
21 : #include "clang/Analysis/Analyses/LiveVariables.h"
22 : #include "clang/Analysis/Support/Optional.h"
23 : #include "clang/Basic/TargetInfo.h"
24 : #include "clang/AST/CharUnits.h"
25 :
26 : #include "llvm/ADT/ImmutableMap.h"
27 : #include "llvm/ADT/ImmutableList.h"
28 : #include "llvm/Support/raw_ostream.h"
29 :
30 : using namespace clang;
31 :
32 : #define USE_EXPLICIT_COMPOUND 0
33 :
34 : //===----------------------------------------------------------------------===//
35 : // Representation of binding keys.
36 : //===----------------------------------------------------------------------===//
37 :
38 : namespace {
39 60: class BindingKey {
40 : public:
41 : enum Kind { Direct = 0x0, Default = 0x1 };
42 : private:
43 : llvm ::PointerIntPair<const MemRegion*, 1> P;
44 : uint64_t Offset;
45 :
46 27025: explicit BindingKey(const MemRegion *r, uint64_t offset, Kind k)
0: branch 1 not taken
27025: branch 2 taken
47 27025: : P(r, (unsigned) k), Offset(offset) { assert(r); }
48 : public:
49 :
50 : bool isDefault() const { return P.getInt() == Default; }
51 0: bool isDirect() const { return P.getInt() == Direct; }
52 :
53 27513: const MemRegion *getRegion() const { return P.getPointer(); }
54 0: uint64_t getOffset() const { return Offset; }
55 :
56 10718: void Profile(llvm::FoldingSetNodeID& ID) const {
57 10718: ID.AddPointer(P.getOpaqueValue());
58 10718: ID.AddInteger(Offset);
59 10718: }
60 :
61 : static BindingKey Make(const MemRegion *R, Kind k);
62 :
63 30306: bool operator<(const BindingKey &X) const {
11651: branch 2 taken
18655: branch 3 taken
64 30306: if (P.getOpaqueValue() < X.P.getOpaqueValue())
65 11651: return true;
17806: branch 2 taken
849: branch 3 taken
66 18655: if (P.getOpaqueValue() > X.P.getOpaqueValue())
67 17806: return false;
68 849: return Offset < X.Offset;
69 : }
70 :
71 50273: bool operator==(const BindingKey &X) const {
72 : return P.getOpaqueValue() == X.P.getOpaqueValue() &&
20816: branch 2 taken
29457: branch 3 taken
19967: branch 4 taken
849: branch 5 taken
73 50273: Offset == X.Offset;
74 : }
75 : };
76 : } // end anonymous namespace
77 :
78 : namespace llvm {
79 : static inline
80 0: llvm::raw_ostream& operator<<(llvm::raw_ostream& os, BindingKey K) {
81 : os << '(' << K.getRegion() << ',' << K.getOffset()
82 : << ',' << (K.isDirect() ? "direct" : "default")
0: branch 1 not taken
0: branch 2 not taken
83 0: << ')';
84 0: return os;
85 : }
86 : } // end llvm namespace
87 :
88 : //===----------------------------------------------------------------------===//
89 : // Actual Store type.
90 : //===----------------------------------------------------------------------===//
91 :
92 : typedef llvm::ImmutableMap<BindingKey, SVal> RegionBindings;
93 :
94 : //===----------------------------------------------------------------------===//
95 : // Fine-grained control of RegionStoreManager.
96 : //===----------------------------------------------------------------------===//
97 :
98 : namespace {
99 : struct minimal_features_tag {};
100 : struct maximal_features_tag {};
101 :
102 : class RegionStoreFeatures {
103 : bool SupportsFields;
104 : bool SupportsRemaining;
105 :
106 : public:
107 0: RegionStoreFeatures(minimal_features_tag) :
108 0: SupportsFields(false), SupportsRemaining(false) {}
109 :
110 1170: RegionStoreFeatures(maximal_features_tag) :
111 1170: SupportsFields(true), SupportsRemaining(false) {}
112 :
113 0: void enableFields(bool t) { SupportsFields = t; }
114 :
115 72: bool supportsFields() const { return SupportsFields; }
116 : bool supportsRemaining() const { return SupportsRemaining; }
117 : };
118 : }
119 :
120 : //===----------------------------------------------------------------------===//
121 : // Region "Extents"
122 : //===----------------------------------------------------------------------===//
123 : //
124 : // MemRegions represent chunks of memory with a size (their "extent"). This
125 : // GDM entry tracks the extents for regions. Extents are in bytes.
126 : //
127 : namespace { class RegionExtents {}; }
128 : static int RegionExtentsIndex = 0;
129 : namespace clang {
130 : template<> struct GRStateTrait<RegionExtents>
131 : : public GRStatePartialTrait<llvm::ImmutableMap<const MemRegion*, SVal> > {
132 120: static void* GDMIndex() { return &RegionExtentsIndex; }
133 : };
134 : }
135 :
136 : //===----------------------------------------------------------------------===//
137 : // Utility functions.
138 : //===----------------------------------------------------------------------===//
139 :
140 220: static bool IsAnyPointerOrIntptr(QualType ty, ASTContext &Ctx) {
84: branch 2 taken
136: branch 3 taken
141 220: if (ty->isAnyPointerType())
142 84: return true;
143 :
144 : return ty->isIntegerType() && ty->isScalarType() &&
36: branch 2 taken
100: branch 3 taken
36: branch 6 taken
0: branch 7 not taken
34: branch 11 taken
2: branch 12 taken
145 136: Ctx.getTypeSize(ty) == Ctx.getTypeSize(Ctx.VoidPtrTy);
146 : }
147 :
148 : //===----------------------------------------------------------------------===//
149 : // Main RegionStore logic.
150 : //===----------------------------------------------------------------------===//
151 :
152 : namespace {
153 :
154 6885: class RegionStoreSubRegionMap : public SubRegionMap {
155 : public:
156 : typedef llvm::ImmutableSet<const MemRegion*> Set;
157 : typedef llvm::DenseMap<const MemRegion*, Set> Map;
158 : private:
159 : Set::Factory F;
160 : Map M;
161 : public:
162 9700: bool add(const MemRegion* Parent, const MemRegion* SubRegion) {
163 9700: Map::iterator I = M.find(Parent);
164 :
4956: branch 3 taken
4744: branch 4 taken
165 9700: if (I == M.end()) {
166 4956: M.insert(std::make_pair(Parent, F.Add(F.GetEmptySet(), SubRegion)));
167 4956: return true;
168 : }
169 :
170 4744: I->second = F.Add(I->second, SubRegion);
171 4744: return false;
172 : }
173 :
174 : void process(llvm::SmallVectorImpl<const SubRegion*> &WL, const SubRegion *R);
175 :
6885: branch 3 taken
0: branch 4 not taken
0: branch 9 not taken
0: branch 10 not taken
176 6885: ~RegionStoreSubRegionMap() {}
177 :
178 10747: const Set *getSubRegions(const MemRegion *Parent) const {
179 10747: Map::const_iterator I = M.find(Parent);
10528: branch 2 taken
219: branch 3 taken
180 10747: return I == M.end() ? NULL : &I->second;
181 : }
182 :
183 894: bool iterSubRegions(const MemRegion* Parent, Visitor& V) const {
184 894: Map::const_iterator I = M.find(Parent);
185 :
893: branch 2 taken
1: branch 3 taken
186 894: if (I == M.end())
187 893: return true;
188 :
189 1: Set S = I->second;
3: branch 4 taken
1: branch 5 taken
190 4: for (Set::iterator SI=S.begin(),SE=S.end(); SI != SE; ++SI) {
0: branch 2 not taken
3: branch 3 taken
191 3: if (!V.Visit(Parent, *SI))
192 0: return false;
1: branch 1 taken
0: branch 2 not taken
1: branch 4 taken
0: branch 5 not taken
193 1: }
194 :
195 1: return true;
196 : }
197 : };
198 :
199 :
200 : class RegionStoreManager : public StoreManager {
201 : const RegionStoreFeatures Features;
202 : RegionBindings::Factory RBFactory;
203 :
204 : typedef llvm::DenseMap<Store, RegionStoreSubRegionMap*> SMCache;
205 : SMCache SC;
206 :
207 : public:
208 1170: RegionStoreManager(GRStateManager& mgr, const RegionStoreFeatures &f)
209 : : StoreManager(mgr),
210 : Features(f),
211 1170: RBFactory(mgr.getAllocator()) {}
212 :
213 1170: virtual ~RegionStoreManager() {
6: branch 5 taken
1170: branch 6 taken
0: branch 12 not taken
0: branch 13 not taken
214 1176: for (SMCache::iterator I = SC.begin(), E = SC.end(); I != E; ++I)
6: branch 1 taken
0: branch 2 not taken
0: branch 5 not taken
0: branch 6 not taken
215 6: delete (*I).second;
1170: branch 3 taken
0: branch 4 not taken
0: branch 9 not taken
0: branch 10 not taken
216 1170: }
217 :
218 669: SubRegionMap *getSubRegionMap(Store store) {
219 669: return getRegionStoreSubRegionMap(store);
220 : }
221 :
222 : RegionStoreSubRegionMap *getRegionStoreSubRegionMap(Store store);
223 :
224 : Optional<SVal> getBinding(RegionBindings B, const MemRegion *R);
225 : Optional<SVal> getDirectBinding(RegionBindings B, const MemRegion *R);
226 : /// getDefaultBinding - Returns an SVal* representing an optional default
227 : /// binding associated with a region and its subregions.
228 : Optional<SVal> getDefaultBinding(RegionBindings B, const MemRegion *R);
229 :
230 : /// setImplicitDefaultValue - Set the default binding for the provided
231 : /// MemRegion to the value implicitly defined for compound literals when
232 : /// the value is not specified.
233 : Store setImplicitDefaultValue(Store store, const MemRegion *R, QualType T);
234 :
235 : /// ArrayToPointer - Emulates the "decay" of an array to a pointer
236 : /// type. 'Array' represents the lvalue of the array being decayed
237 : /// to a pointer, and the returned SVal represents the decayed
238 : /// version of that lvalue (i.e., a pointer to the first element of
239 : /// the array). This is called by GRExprEngine when evaluating
240 : /// casts from arrays to pointers.
241 : SVal ArrayToPointer(Loc Array);
242 :
243 : SVal EvalBinOp(BinaryOperator::Opcode Op,Loc L, NonLoc R, QualType resultTy);
244 :
245 1170: Store getInitialStore(const LocationContext *InitLoc) {
246 1170: return RBFactory.GetEmptyMap().getRoot();
247 : }
248 :
249 : //===-------------------------------------------------------------------===//
250 : // Binding values to regions.
251 : //===-------------------------------------------------------------------===//
252 :
253 : Store InvalidateRegion(Store store, const MemRegion *R, const Expr *E,
254 7: unsigned Count, InvalidatedSymbols *IS) {
255 7: return RegionStoreManager::InvalidateRegions(store, &R, &R+1, E, Count, IS);
256 : }
257 :
258 : Store InvalidateRegions(Store store,
259 : const MemRegion * const *Begin,
260 : const MemRegion * const *End,
261 : const Expr *E, unsigned Count,
262 : InvalidatedSymbols *IS);
263 :
264 : public: // Made public for helper classes.
265 :
266 : void RemoveSubRegionBindings(RegionBindings &B, const MemRegion *R,
267 : RegionStoreSubRegionMap &M);
268 :
269 : RegionBindings Add(RegionBindings B, BindingKey K, SVal V);
270 :
271 : RegionBindings Add(RegionBindings B, const MemRegion *R,
272 : BindingKey::Kind k, SVal V);
273 :
274 : const SVal *Lookup(RegionBindings B, BindingKey K);
275 : const SVal *Lookup(RegionBindings B, const MemRegion *R, BindingKey::Kind k);
276 :
277 : RegionBindings Remove(RegionBindings B, BindingKey K);
278 : RegionBindings Remove(RegionBindings B, const MemRegion *R,
279 : BindingKey::Kind k);
280 :
281 78: RegionBindings Remove(RegionBindings B, const MemRegion *R) {
282 78: return Remove(Remove(B, R, BindingKey::Direct), R, BindingKey::Default);
283 : }
284 :
285 : Store Remove(Store store, BindingKey K);
286 :
287 : public: // Part of public interface to class.
288 :
289 : Store Bind(Store store, Loc LV, SVal V);
290 :
291 : Store BindCompoundLiteral(Store store, const CompoundLiteralExpr* CL,
292 : const LocationContext *LC, SVal V);
293 :
294 : Store BindDecl(Store store, const VarRegion *VR, SVal InitVal);
295 :
296 366: Store BindDeclWithNoInit(Store store, const VarRegion *) {
297 366: return store;
298 : }
299 :
300 : /// BindStruct - Bind a compound value to a structure.
301 : Store BindStruct(Store store, const TypedRegion* R, SVal V);
302 :
303 : Store BindArray(Store store, const TypedRegion* R, SVal V);
304 :
305 : /// KillStruct - Set the entire struct to unknown.
306 : Store KillStruct(Store store, const TypedRegion* R);
307 :
308 : Store Remove(Store store, Loc LV);
309 :
310 :
311 : //===------------------------------------------------------------------===//
312 : // Loading values from regions.
313 : //===------------------------------------------------------------------===//
314 :
315 : /// The high level logic for this method is this:
316 : /// Retrieve (L)
317 : /// if L has binding
318 : /// return L's binding
319 : /// else if L is in killset
320 : /// return unknown
321 : /// else
322 : /// if L is on stack or heap
323 : /// return undefined
324 : /// else
325 : /// return symbolic
326 : SVal Retrieve(Store store, Loc L, QualType T = QualType());
327 :
328 : SVal RetrieveElement(Store store, const ElementRegion *R);
329 :
330 : SVal RetrieveField(Store store, const FieldRegion *R);
331 :
332 : SVal RetrieveObjCIvar(Store store, const ObjCIvarRegion *R);
333 :
334 : SVal RetrieveVar(Store store, const VarRegion *R);
335 :
336 : SVal RetrieveLazySymbol(const TypedRegion *R);
337 :
338 : SVal RetrieveFieldOrElementCommon(Store store, const TypedRegion *R,
339 : QualType Ty, const MemRegion *superR);
340 :
341 : /// Retrieve the values in a struct and return a CompoundVal, used when doing
342 : /// struct copy:
343 : /// struct s x, y;
344 : /// x = y;
345 : /// y's value is retrieved by this method.
346 : SVal RetrieveStruct(Store store, const TypedRegion* R);
347 :
348 : SVal RetrieveArray(Store store, const TypedRegion* R);
349 :
350 : /// Get the state and region whose binding this region R corresponds to.
351 : std::pair<Store, const MemRegion*>
352 : GetLazyBinding(RegionBindings B, const MemRegion *R);
353 :
354 : Store CopyLazyBindings(nonloc::LazyCompoundVal V, Store store,
355 : const TypedRegion *R);
356 :
357 : const ElementRegion *GetElementZeroRegion(const MemRegion *R, QualType T);
358 :
359 : //===------------------------------------------------------------------===//
360 : // State pruning.
361 : //===------------------------------------------------------------------===//
362 :
363 : /// RemoveDeadBindings - Scans the RegionStore of 'state' for dead values.
364 : /// It returns a new Store with these values removed.
365 : Store RemoveDeadBindings(Store store, Stmt* Loc, SymbolReaper& SymReaper,
366 : llvm::SmallVectorImpl<const MemRegion*>& RegionRoots);
367 :
368 : const GRState *EnterStackFrame(const GRState *state,
369 : const StackFrameContext *frame);
370 :
371 : //===------------------------------------------------------------------===//
372 : // Region "extents".
373 : //===------------------------------------------------------------------===//
374 :
375 : const GRState *setExtent(const GRState *state,const MemRegion* R,SVal Extent);
376 : DefinedOrUnknownSVal getSizeInElements(const GRState *state,
377 : const MemRegion* R, QualType EleTy);
378 :
379 : //===------------------------------------------------------------------===//
380 : // Utility methods.
381 : //===------------------------------------------------------------------===//
382 :
383 35591: static inline RegionBindings GetRegionBindings(Store store) {
384 35591: return RegionBindings(static_cast<const RegionBindings::TreeTy*>(store));
385 : }
386 :
387 : void print(Store store, llvm::raw_ostream& Out, const char* nl,
388 : const char *sep);
389 :
390 1915: void iterBindings(Store store, BindingsHandler& f) {
391 : // FIXME: Implement.
392 1915: }
393 :
394 : // FIXME: Remove.
395 : BasicValueFactory& getBasicVals() {
396 : return StateMgr.getBasicVals();
397 : }
398 :
399 : // FIXME: Remove.
400 13354: ASTContext& getContext() { return StateMgr.getContext(); }
401 : };
402 :
403 : } // end anonymous namespace
404 :
405 : //===----------------------------------------------------------------------===//
406 : // RegionStore creation.
407 : //===----------------------------------------------------------------------===//
408 :
409 1170: StoreManager *clang::CreateRegionStoreManager(GRStateManager& StMgr) {
410 1170: RegionStoreFeatures F = maximal_features_tag();
411 1170: return new RegionStoreManager(StMgr, F);
412 : }
413 :
414 0: StoreManager *clang::CreateFieldsOnlyRegionStoreManager(GRStateManager &StMgr) {
415 0: RegionStoreFeatures F = minimal_features_tag();
416 0: F.enableFields(true);
417 0: return new RegionStoreManager(StMgr, F);
418 : }
419 :
420 : void
421 : RegionStoreSubRegionMap::process(llvm::SmallVectorImpl<const SubRegion*> &WL,
422 9700: const SubRegion *R) {
423 9700: const MemRegion *superR = R->getSuperRegion();
4956: branch 1 taken
4744: branch 2 taken
424 9700: if (add(superR, R))
182: branch 1 taken
4774: branch 2 taken
425 4956: if (const SubRegion *sr = dyn_cast<SubRegion>(superR))
426 182: WL.push_back(sr);
427 9700: }
428 :
429 : RegionStoreSubRegionMap*
430 6885: RegionStoreManager::getRegionStoreSubRegionMap(Store store) {
431 6885: RegionBindings B = GetRegionBindings(store);
432 6885: RegionStoreSubRegionMap *M = new RegionStoreSubRegionMap();
433 :
434 6885: llvm::SmallVector<const SubRegion*, 10> WL;
435 :
9518: branch 4 taken
6885: branch 5 taken
436 16403: for (RegionBindings::iterator I=B.begin(), E=B.end(); I!=E; ++I)
9518: branch 3 taken
0: branch 4 not taken
437 9518: if (const SubRegion *R = dyn_cast<SubRegion>(I.getKey().getRegion()))
438 16403: M->process(WL, R);
439 :
440 : // We also need to record in the subregion map "intermediate" regions that
441 : // don't have direct bindings but are super regions of those that do.
182: branch 1 taken
6885: branch 2 taken
442 13952: while (!WL.empty()) {
443 182: const SubRegion *R = WL.back();
444 182: WL.pop_back();
445 182: M->process(WL, R);
446 : }
447 :
448 6885: return M;
449 : }
450 :
451 : //===----------------------------------------------------------------------===//
452 : // Binding invalidation.
453 : //===----------------------------------------------------------------------===//
454 :
455 : void RegionStoreManager::RemoveSubRegionBindings(RegionBindings &B,
456 : const MemRegion *R,
457 74: RegionStoreSubRegionMap &M) {
458 :
18: branch 1 taken
56: branch 2 taken
459 74: if (const RegionStoreSubRegionMap::Set *S = M.getSubRegions(R))
32: branch 4 taken
18: branch 5 taken
460 50: for (RegionStoreSubRegionMap::Set::iterator I = S->begin(), E = S->end();
461 : I != E; ++I)
462 50: RemoveSubRegionBindings(B, *I, M);
463 :
464 74: B = Remove(B, R);
465 74: }
466 :
467 : namespace {
468 742: class InvalidateRegionsWorker {
469 : typedef BumpVector<BindingKey> RegionCluster;
470 : typedef llvm::DenseMap<const MemRegion *, RegionCluster *> ClusterMap;
471 : typedef llvm::SmallVector<std::pair<const MemRegion *,RegionCluster*>, 10>
472 : WorkList;
473 :
474 : BumpVectorContext BVC;
475 : ClusterMap ClusterM;
476 : WorkList WL;
477 : public:
478 : Store InvalidateRegions(RegionStoreManager &RM, Store store,
479 : const MemRegion * const *I,const MemRegion * const *E,
480 : const Expr *Ex, unsigned Count,
481 : StoreManager::InvalidatedSymbols *IS,
482 : ASTContext &Ctx, ValueManager &ValMgr);
483 :
484 : private:
485 : void AddToWorkList(BindingKey K);
486 : void AddToWorkList(const MemRegion *R);
487 : void AddToCluster(BindingKey K);
488 : RegionCluster **getCluster(const MemRegion *R);
489 : };
490 : }
491 :
492 419: void InvalidateRegionsWorker::AddToCluster(BindingKey K) {
493 419: const MemRegion *R = K.getRegion();
494 419: const MemRegion *baseR = R->getBaseRegion();
495 419: RegionCluster **CPtr = getCluster(baseR);
0: branch 0 not taken
419: branch 1 taken
496 419: assert(*CPtr);
497 419: (*CPtr)->push_back(K, BVC);
498 419: }
499 :
500 0: void InvalidateRegionsWorker::AddToWorkList(BindingKey K) {
501 0: AddToWorkList(K.getRegion());
502 0: }
503 :
504 558: void InvalidateRegionsWorker::AddToWorkList(const MemRegion *R) {
505 558: const MemRegion *baseR = R->getBaseRegion();
506 558: RegionCluster **CPtr = getCluster(baseR);
558: branch 0 taken
0: branch 1 not taken
507 558: if (RegionCluster *C = *CPtr) {
508 558: WL.push_back(std::make_pair(baseR, C));
509 558: *CPtr = NULL;
510 : }
511 558: }
512 :
513 : InvalidateRegionsWorker::RegionCluster **
514 1160: InvalidateRegionsWorker::getCluster(const MemRegion *R) {
515 1160: RegionCluster *&CRef = ClusterM[R];
910: branch 0 taken
250: branch 1 taken
516 1160: if (!CRef) {
517 910: void *Mem = BVC.getAllocator().Allocate<RegionCluster>();
910: branch 1 taken
0: branch 2 not taken
518 910: CRef = new (Mem) RegionCluster(BVC, 10);
519 : }
520 1160: return &CRef;
521 : }
522 :
523 : Store InvalidateRegionsWorker::InvalidateRegions(RegionStoreManager &RM,
524 : Store store,
525 : const MemRegion * const *I,
526 : const MemRegion * const *E,
527 : const Expr *Ex, unsigned Count,
528 : StoreManager::InvalidatedSymbols *IS,
529 : ASTContext &Ctx,
530 371: ValueManager &ValMgr) {
531 371: RegionBindings B = RegionStoreManager::GetRegionBindings(store);
532 :
533 : // Scan the entire store and make the region clusters.
419: branch 4 taken
371: branch 5 taken
534 790: for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI) {
535 419: AddToCluster(RI.getKey());
183: branch 2 taken
236: branch 3 taken
536 419: if (const MemRegion *R = RI.getData().getAsRegion()) {
537 : // Generate a cluster, but don't add the region to the cluster
538 : // if there aren't any bindings.
539 183: getCluster(R->getBaseRegion());
540 : }
541 371: }
542 :
543 : // Add the cluster for I .. E to a worklist.
489: branch 0 taken
371: branch 1 taken
544 860: for ( ; I != E; ++I)
545 489: AddToWorkList(*I);
546 :
558: branch 2 taken
371: branch 3 taken
547 474: while (!WL.empty()) {
548 : const MemRegion *baseR;
549 : RegionCluster *C;
550 558: llvm::tie(baseR, C) = WL.back();
551 558: WL.pop_back();
552 :
161: branch 2 taken
558: branch 3 taken
553 719: for (RegionCluster::iterator I = C->begin(), E = C->end(); I != E; ++I) {
554 161: BindingKey K = *I;
555 :
556 : // Get the old binding. Is it a region? If so, add it to the worklist.
161: branch 1 taken
0: branch 2 not taken
557 161: if (const SVal *V = RM.Lookup(B, K)) {
32: branch 1 taken
129: branch 2 taken
558 161: if (const MemRegion *R = V->getAsRegion())
559 32: AddToWorkList(R);
560 :
561 : // A symbol? Mark it touched by the invalidation.
157: branch 0 taken
4: branch 1 taken
562 161: if (IS)
43: branch 1 taken
114: branch 2 taken
563 157: if (SymbolRef Sym = V->getAsSymbol())
564 43: IS->insert(Sym);
565 : }
566 :
567 161: B = RM.Remove(B, K);
568 : }
569 :
570 : // Now inspect the base region.
571 :
551: branch 0 taken
7: branch 1 taken
572 558: if (IS) {
573 : // Symbolic region? Mark that symbol touched by the invalidation.
260: branch 1 taken
291: branch 2 taken
574 551: if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR))
575 260: IS->insert(SR->getSymbol());
576 : }
577 :
578 : // BlockDataRegion? If so, invalidate captured variables that are passed
579 : // by reference.
47: branch 1 taken
511: branch 2 taken
580 558: if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(baseR)) {
60: branch 2 taken
47: branch 3 taken
581 107: for (BlockDataRegion::referenced_vars_iterator
582 47: BI = BR->referenced_vars_begin(), BE = BR->referenced_vars_end() ;
583 : BI != BE; ++BI) {
584 60: const VarRegion *VR = *BI;
585 60: const VarDecl *VD = VR->getDecl();
28: branch 1 taken
32: branch 2 taken
5: branch 4 taken
23: branch 5 taken
37: branch 6 taken
23: branch 7 taken
586 60: if (VD->getAttr<BlocksAttr>() || !VD->hasLocalStorage())
587 37: AddToWorkList(VR);
588 : }
589 47: continue;
590 : }
591 :
505: branch 1 taken
6: branch 2 taken
261: branch 4 taken
244: branch 5 taken
267: branch 6 taken
244: branch 7 taken
592 511: if (isa<AllocaRegion>(baseR) || isa<SymbolicRegion>(baseR)) {
593 : // Invalidate the region by setting its default value to
594 : // conjured symbol. The type of the symbol is irrelavant.
595 : DefinedOrUnknownSVal V = ValMgr.getConjuredSymbolVal(baseR, Ex, Ctx.IntTy,
596 267: Count);
597 267: B = RM.Add(B, baseR, BindingKey::Default, V);
598 267: continue;
599 : }
600 :
58: branch 1 taken
186: branch 2 taken
601 244: if (!baseR->isBoundable())
602 58: continue;
603 :
604 186: const TypedRegion *TR = cast<TypedRegion>(baseR);
605 186: QualType T = TR->getValueType(Ctx);
606 :
607 : // Invalidate the binding.
62: branch 2 taken
124: branch 3 taken
608 186: if (const RecordType *RT = T->getAsStructureType()) {
609 62: const RecordDecl *RD = RT->getDecl()->getDefinition(Ctx);
610 : // No record definition. There is nothing we can do.
4: branch 0 taken
58: branch 1 taken
611 62: if (!RD) {
612 4: B = RM.Remove(B, baseR);
613 4: continue;
614 : }
615 :
616 : // Invalidate the region by setting its default value to
617 : // conjured symbol. The type of the symbol is irrelavant.
618 : DefinedOrUnknownSVal V = ValMgr.getConjuredSymbolVal(baseR, Ex, Ctx.IntTy,
619 58: Count);
620 58: B = RM.Add(B, baseR, BindingKey::Default, V);
621 58: continue;
622 : }
623 :
21: branch 1 taken
103: branch 2 taken
624 124: if (const ArrayType *AT = Ctx.getAsArrayType(T)) {
625 : // Set the default value of the array to conjured symbol.
626 : DefinedOrUnknownSVal V =
627 21: ValMgr.getConjuredSymbolVal(baseR, Ex, AT->getElementType(), Count);
628 21: B = RM.Add(B, baseR, BindingKey::Default, V);
629 21: continue;
630 : }
631 :
632 103: DefinedOrUnknownSVal V = ValMgr.getConjuredSymbolVal(baseR, Ex, T, Count);
2: branch 1 taken
101: branch 2 taken
0: branch 4 not taken
2: branch 5 taken
633 103: assert(SymbolManager::canSymbolicate(T) || V.isUnknown());
634 103: B = RM.Add(B, baseR, BindingKey::Direct, V);
635 : }
636 :
637 : // Create a new state with the updated bindings.
638 371: return B.getRoot();
639 : }
640 :
641 : Store RegionStoreManager::InvalidateRegions(Store store,
642 : const MemRegion * const *I,
643 : const MemRegion * const *E,
644 : const Expr *Ex, unsigned Count,
645 371: InvalidatedSymbols *IS) {
646 371: InvalidateRegionsWorker W;
647 : return W.InvalidateRegions(*this, store, I, E, Ex, Count, IS, getContext(),
648 371: StateMgr.getValueManager());
649 : }
650 :
651 : //===----------------------------------------------------------------------===//
652 : // Extents for regions.
653 : //===----------------------------------------------------------------------===//
654 :
655 : DefinedOrUnknownSVal RegionStoreManager::getSizeInElements(const GRState *state,
656 : const MemRegion *R,
657 145: QualType EleTy) {
658 :
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
9: branch 4 taken
69: branch 5 taken
2: branch 6 taken
65: branch 7 taken
0: branch 8 not taken
659 145: switch (R->getKind()) {
660 : case MemRegion::CXXThisRegionKind:
661 0: assert(0 && "Cannot get size of 'this' region");
662 : case MemRegion::GenericMemSpaceRegionKind:
663 : case MemRegion::StackLocalsSpaceRegionKind:
664 : case MemRegion::StackArgumentsSpaceRegionKind:
665 : case MemRegion::HeapSpaceRegionKind:
666 : case MemRegion::GlobalsSpaceRegionKind:
667 : case MemRegion::UnknownSpaceRegionKind:
668 0: assert(0 && "Cannot index into a MemSpace");
669 : return UnknownVal();
670 :
671 : case MemRegion::FunctionTextRegionKind:
672 : case MemRegion::BlockTextRegionKind:
673 : case MemRegion::BlockDataRegionKind:
674 : // Technically this can happen if people do funny things with casts.
675 0: return UnknownVal();
676 :
677 : // Not yet handled.
678 : case MemRegion::AllocaRegionKind:
679 : case MemRegion::CompoundLiteralRegionKind:
680 : case MemRegion::ElementRegionKind:
681 : case MemRegion::FieldRegionKind:
682 : case MemRegion::ObjCIvarRegionKind:
683 : case MemRegion::CXXObjectRegionKind:
684 9: return UnknownVal();
685 :
686 : case MemRegion::SymbolicRegionKind: {
687 69: const SVal *Size = state->get<RegionExtents>(R);
68: branch 0 taken
1: branch 1 taken
688 69: if (!Size)
689 68: return UnknownVal();
690 1: const nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(Size);
0: branch 0 not taken
1: branch 1 taken
691 1: if (!CI)
692 0: return UnknownVal();
693 :
694 : CharUnits RegionSize =
695 1: CharUnits::fromQuantity(CI->getValue().getSExtValue());
696 1: CharUnits EleSize = getContext().getTypeSizeInChars(EleTy);
0: branch 1 not taken
1: branch 2 taken
697 1: assert(RegionSize % EleSize == 0);
698 :
699 1: return ValMgr.makeIntVal(RegionSize / EleSize, false);
700 : }
701 :
702 : case MemRegion::StringRegionKind: {
703 2: const StringLiteral* Str = cast<StringRegion>(R)->getStringLiteral();
704 : // We intentionally made the size value signed because it participates in
705 : // operations with signed indices.
706 2: return ValMgr.makeIntVal(Str->getByteLength()+1, false);
707 : }
708 :
709 : case MemRegion::VarRegionKind: {
710 65: const VarRegion* VR = cast<VarRegion>(R);
711 : // Get the type of the variable.
712 65: QualType T = VR->getDesugaredValueType(getContext());
713 :
714 : // FIXME: Handle variable-length arrays.
0: branch 1 not taken
65: branch 2 taken
715 65: if (isa<VariableArrayType>(T))
716 0: return UnknownVal();
717 :
62: branch 1 taken
3: branch 2 taken
718 65: if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(T)) {
719 : // return the size as signed integer.
720 62: return ValMgr.makeIntVal(CAT->getSize(), false);
721 : }
722 :
723 : // Clients can use ordinary variables as if they were arrays. These
724 : // essentially are arrays of size 1.
725 3: return ValMgr.makeIntVal(1, false);
726 : }
727 : }
728 :
729 0: assert(0 && "Unreachable");
730 : return UnknownVal();
731 : }
732 :
733 : const GRState *RegionStoreManager::setExtent(const GRState *state,
734 : const MemRegion *region,
735 17: SVal extent) {
736 17: return state->set<RegionExtents>(region, extent);
737 : }
738 :
739 : //===----------------------------------------------------------------------===//
740 : // Location and region casting.
741 : //===----------------------------------------------------------------------===//
742 :
743 : /// ArrayToPointer - Emulates the "decay" of an array to a pointer
744 : /// type. 'Array' represents the lvalue of the array being decayed
745 : /// to a pointer, and the returned SVal represents the decayed
746 : /// version of that lvalue (i.e., a pointer to the first element of
747 : /// the array). This is called by GRExprEngine when evaluating casts
748 : /// from arrays to pointers.
749 261: SVal RegionStoreManager::ArrayToPointer(Loc Array) {
0: branch 1 not taken
261: branch 2 taken
750 261: if (!isa<loc::MemRegionVal>(Array))
751 0: return UnknownVal();
752 :
753 261: const MemRegion* R = cast<loc::MemRegionVal>(&Array)->getRegion();
754 261: const TypedRegion* ArrayR = dyn_cast<TypedRegion>(R);
755 :
0: branch 0 not taken
261: branch 1 taken
756 261: if (!ArrayR)
757 0: return UnknownVal();
758 :
759 : // Strip off typedefs from the ArrayRegion's ValueType.
760 261: QualType T = ArrayR->getValueType(getContext()).getDesugaredType();
761 261: ArrayType *AT = cast<ArrayType>(T);
762 261: T = AT->getElementType();
763 :
764 261: SVal ZeroIdx = ValMgr.makeZeroArrayIndex();
765 : return loc::MemRegionVal(MRMgr.getElementRegion(T, ZeroIdx, ArrayR,
766 261: getContext()));
767 : }
768 :
769 : //===----------------------------------------------------------------------===//
770 : // Pointer arithmetic.
771 : //===----------------------------------------------------------------------===//
772 :
773 : SVal RegionStoreManager::EvalBinOp(BinaryOperator::Opcode Op, Loc L, NonLoc R,
774 149: QualType resultTy) {
775 : // Assume the base location is MemRegionVal.
0: branch 1 not taken
149: branch 2 taken
776 149: if (!isa<loc::MemRegionVal>(L))
777 0: return UnknownVal();
778 :
779 149: const MemRegion* MR = cast<loc::MemRegionVal>(L).getRegion();
780 149: const ElementRegion *ER = 0;
781 :
46: branch 1 taken
0: branch 2 not taken
100: branch 3 taken
3: branch 4 taken
0: branch 5 not taken
0: branch 6 not taken
0: branch 7 not taken
0: branch 8 not taken
782 149: switch (MR->getKind()) {
783 : case MemRegion::SymbolicRegionKind: {
784 46: const SymbolicRegion *SR = cast<SymbolicRegion>(MR);
785 46: SymbolRef Sym = SR->getSymbol();
786 46: QualType T = Sym->getType(getContext());
787 46: QualType EleTy;
788 :
46: branch 2 taken
0: branch 3 not taken
789 46: if (const PointerType *PT = T->getAs<PointerType>())
790 46: EleTy = PT->getPointeeType();
791 : else
792 0: EleTy = T->getAs<ObjCObjectPointerType>()->getPointeeType();
793 :
794 46: SVal ZeroIdx = ValMgr.makeZeroArrayIndex();
795 46: ER = MRMgr.getElementRegion(EleTy, ZeroIdx, SR, getContext());
796 46: break;
797 : }
798 : case MemRegion::AllocaRegionKind: {
799 0: const AllocaRegion *AR = cast<AllocaRegion>(MR);
800 0: QualType T = getContext().CharTy; // Create an ElementRegion of bytes.
801 0: QualType EleTy = T->getAs<PointerType>()->getPointeeType();
802 0: SVal ZeroIdx = ValMgr.makeZeroArrayIndex();
803 0: ER = MRMgr.getElementRegion(EleTy, ZeroIdx, AR, getContext());
804 0: break;
805 : }
806 :
807 : case MemRegion::ElementRegionKind: {
808 100: ER = cast<ElementRegion>(MR);
809 100: break;
810 : }
811 :
812 : // Not yet handled.
813 : case MemRegion::VarRegionKind:
814 : case MemRegion::StringRegionKind: {
815 :
816 : }
817 : // Fall-through.
818 : case MemRegion::CompoundLiteralRegionKind:
819 : case MemRegion::FieldRegionKind:
820 : case MemRegion::ObjCIvarRegionKind:
821 : case MemRegion::CXXObjectRegionKind:
822 3: return UnknownVal();
823 :
824 : case MemRegion::FunctionTextRegionKind:
825 : case MemRegion::BlockTextRegionKind:
826 : case MemRegion::BlockDataRegionKind:
827 : // Technically this can happen if people do funny things with casts.
828 0: return UnknownVal();
829 :
830 : case MemRegion::CXXThisRegionKind:
831 : assert(0 &&
832 0: "Cannot perform pointer arithmetic on implicit argument 'this'");
833 : case MemRegion::GenericMemSpaceRegionKind:
834 : case MemRegion::StackLocalsSpaceRegionKind:
835 : case MemRegion::StackArgumentsSpaceRegionKind:
836 : case MemRegion::HeapSpaceRegionKind:
837 : case MemRegion::GlobalsSpaceRegionKind:
838 : case MemRegion::UnknownSpaceRegionKind:
839 0: assert(0 && "Cannot perform pointer arithmetic on a MemSpace");
840 : return UnknownVal();
841 : }
842 :
843 146: SVal Idx = ER->getIndex();
844 146: nonloc::ConcreteInt* Base = dyn_cast<nonloc::ConcreteInt>(&Idx);
845 :
846 : // For now, only support:
847 : // (a) concrete integer indices that can easily be resolved
848 : // (b) 0 + symbolic index
146: branch 0 taken
0: branch 1 not taken
849 146: if (Base) {
136: branch 1 taken
10: branch 2 taken
850 146: if (nonloc::ConcreteInt *Offset = dyn_cast<nonloc::ConcreteInt>(&R)) {
851 : // FIXME: Should use SValuator here.
852 : SVal NewIdx =
853 : Base->evalBinOp(ValMgr, Op,
854 136: cast<nonloc::ConcreteInt>(ValMgr.convertToArrayIndex(*Offset)));
855 : const MemRegion* NewER =
856 : MRMgr.getElementRegion(ER->getElementType(), NewIdx,
857 136: ER->getSuperRegion(), getContext());
858 136: return ValMgr.makeLoc(NewER);
859 : }
10: branch 2 taken
0: branch 3 not taken
860 10: if (0 == Base->getValue()) {
861 : const MemRegion* NewER =
862 : MRMgr.getElementRegion(ER->getElementType(), R,
863 10: ER->getSuperRegion(), getContext());
864 10: return ValMgr.makeLoc(NewER);
865 : }
866 : }
867 :
868 0: return UnknownVal();
869 : }
870 :
871 : //===----------------------------------------------------------------------===//
872 : // Loading values from regions.
873 : //===----------------------------------------------------------------------===//
874 :
875 : Optional<SVal> RegionStoreManager::getDirectBinding(RegionBindings B,
876 16969: const MemRegion *R) {
8762: branch 1 taken
8207: branch 2 taken
877 16969: if (const SVal *V = Lookup(B, R, BindingKey::Direct))
878 8762: return *V;
879 :
880 8207: return Optional<SVal>();
881 : }
882 :
883 : Optional<SVal> RegionStoreManager::getDefaultBinding(RegionBindings B,
884 5214: const MemRegion *R) {
4702: branch 1 taken
512: branch 2 taken
885 5214: if (R->isBoundable())
1828: branch 1 taken
2874: branch 2 taken
886 4702: if (const TypedRegion *TR = dyn_cast<TypedRegion>(R))
13: branch 4 taken
1815: branch 5 taken
887 1828: if (TR->getValueType(getContext())->isUnionType())
888 13: return UnknownVal();
889 :
810: branch 1 taken
4391: branch 2 taken
890 5201: if (const SVal *V = Lookup(B, R, BindingKey::Default))
891 810: return *V;
892 :
893 4391: return Optional<SVal>();
894 : }
895 :
896 : Optional<SVal> RegionStoreManager::getBinding(RegionBindings B,
897 10645: const MemRegion *R) {
898 :
6041: branch 2 taken
4604: branch 3 taken
899 10645: if (Optional<SVal> V = getDirectBinding(B, R))
4604: branch 1 taken
6041: branch 2 taken
900 12082: return V;
901 :
902 4604: return getDefaultBinding(B, R);
903 : }
904 :
905 0: static bool IsReinterpreted(QualType RTy, QualType UsedTy, ASTContext &Ctx) {
906 0: RTy = Ctx.getCanonicalType(RTy);
907 0: UsedTy = Ctx.getCanonicalType(UsedTy);
908 :
0: branch 1 not taken
0: branch 2 not taken
909 0: if (RTy == UsedTy)
910 0: return false;
911 :
912 :
913 : // Recursively check the types. We basically want to see if a pointer value
914 : // is ever reinterpreted as a non-pointer, e.g. void** and intptr_t*
915 : // represents a reinterpretation.
0: branch 1 not taken
0: branch 2 not taken
0: branch 4 not taken
0: branch 5 not taken
0: branch 6 not taken
0: branch 7 not taken
916 0: if (Loc::IsLocType(RTy) && Loc::IsLocType(UsedTy)) {
917 0: const PointerType *PRTy = RTy->getAs<PointerType>();
918 0: const PointerType *PUsedTy = UsedTy->getAs<PointerType>();
919 :
920 : return PUsedTy && PRTy &&
921 : IsReinterpreted(PRTy->getPointeeType(),
0: branch 0 not taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
0: branch 7 not taken
0: branch 8 not taken
922 0: PUsedTy->getPointeeType(), Ctx);
923 : }
924 :
925 0: return true;
926 : }
927 :
928 : const ElementRegion *
929 176: RegionStoreManager::GetElementZeroRegion(const MemRegion *R, QualType T) {
930 176: ASTContext &Ctx = getContext();
931 176: SVal idx = ValMgr.makeZeroArrayIndex();
0: branch 1 not taken
176: branch 2 taken
932 176: assert(!T.isNull());
933 176: return MRMgr.getElementRegion(T, idx, R, Ctx);
934 : }
935 :
936 5169: SVal RegionStoreManager::Retrieve(Store store, Loc L, QualType T) {
5169: branch 1 taken
0: branch 2 not taken
937 5169: assert(!isa<UnknownVal>(L) && "location unknown");
5169: branch 1 taken
0: branch 2 not taken
938 5169: assert(!isa<UndefinedVal>(L) && "location undefined");
939 :
940 : // FIXME: Is this even possible? Shouldn't this be treated as a null
941 : // dereference at a higher level?
0: branch 1 not taken
5169: branch 2 taken
942 5169: if (isa<loc::ConcreteInt>(L))
943 0: return UndefinedVal();
944 :
945 5169: const MemRegion *MR = cast<loc::MemRegionVal>(L).getRegion();
946 :
5169: branch 1 taken
0: branch 2 not taken
95: branch 4 taken
5074: branch 5 taken
95: branch 6 taken
5074: branch 7 taken
947 5169: if (isa<AllocaRegion>(MR) || isa<SymbolicRegion>(MR))
948 95: MR = GetElementZeroRegion(MR, T);
949 :
0: branch 1 not taken
5169: branch 2 taken
950 5169: if (isa<CodeTextRegion>(MR))
951 0: return UnknownVal();
952 :
953 : // FIXME: Perhaps this method should just take a 'const MemRegion*' argument
954 : // instead of 'Loc', and have the other Loc cases handled at a higher level.
955 5169: const TypedRegion *R = cast<TypedRegion>(MR);
956 5169: QualType RTy = R->getValueType(getContext());
957 :
958 : // FIXME: We should eventually handle funny addressing. e.g.:
959 : //
960 : // int x = ...;
961 : // int *p = &x;
962 : // char *q = (char*) p;
963 : // char c = *q; // returns the first byte of 'x'.
964 : //
965 : // Such funny addressing will occur due to layering of regions.
966 :
967 : #if 0
968 : ASTContext &Ctx = getContext();
969 : if (!T.isNull() && IsReinterpreted(RTy, T, Ctx)) {
970 : SVal ZeroIdx = ValMgr.makeZeroArrayIndex();
971 : R = MRMgr.getElementRegion(T, ZeroIdx, R, Ctx);
972 : RTy = T;
973 : assert(Ctx.getCanonicalType(RTy) ==
974 : Ctx.getCanonicalType(R->getValueType(Ctx)));
975 : }
976 : #endif
977 :
52: branch 2 taken
5117: branch 3 taken
978 5169: if (RTy->isStructureType())
979 52: return RetrieveStruct(store, R);
980 :
981 : // FIXME: Handle unions.
2: branch 2 taken
5115: branch 3 taken
982 5117: if (RTy->isUnionType())
983 2: return UnknownVal();
984 :
0: branch 2 not taken
5115: branch 3 taken
985 5115: if (RTy->isArrayType())
986 0: return RetrieveArray(store, R);
987 :
988 : // FIXME: handle Vector types.
0: branch 2 not taken
5115: branch 3 taken
989 5115: if (RTy->isVectorType())
990 0: return UnknownVal();
991 :
139: branch 1 taken
4976: branch 2 taken
992 5115: if (const FieldRegion* FR = dyn_cast<FieldRegion>(R))
993 139: return CastRetrievedVal(RetrieveField(store, FR), FR, T, false);
994 :
486: branch 1 taken
4490: branch 2 taken
995 4976: if (const ElementRegion* ER = dyn_cast<ElementRegion>(R)) {
996 : // FIXME: Here we actually perform an implicit conversion from the loaded
997 : // value to the element type. Eventually we want to compose these values
998 : // more intelligently. For example, an 'element' can encompass multiple
999 : // bound regions (e.g., several bound bytes), or could be a subset of
1000 : // a larger value.
1001 486: return CastRetrievedVal(RetrieveElement(store, ER), ER, T, false);
1002 : }
1003 :
51: branch 1 taken
4439: branch 2 taken
1004 4490: if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) {
1005 : // FIXME: Here we actually perform an implicit conversion from the loaded
1006 : // value to the ivar type. What we should model is stores to ivars
1007 : // that blow past the extent of the ivar. If the address of the ivar is
1008 : // reinterpretted, it is possible we stored a different value that could
1009 : // fit within the ivar. Either we need to cast these when storing them
1010 : // or reinterpret them lazily (as we do here).
1011 51: return CastRetrievedVal(RetrieveObjCIvar(store, IVR), IVR, T, false);
1012 : }
1013 :
4428: branch 1 taken
11: branch 2 taken
1014 4439: if (const VarRegion *VR = dyn_cast<VarRegion>(R)) {
1015 : // FIXME: Here we actually perform an implicit conversion from the loaded
1016 : // value to the variable type. What we should model is stores to variables
1017 : // that blow past the extent of the variable. If the address of the
1018 : // variable is reinterpretted, it is possible we stored a different value
1019 : // that could fit within the variable. Either we need to cast these when
1020 : // storing them or reinterpret them lazily (as we do here).
1021 4428: return CastRetrievedVal(RetrieveVar(store, VR), VR, T, false);
1022 : }
1023 :
1024 11: RegionBindings B = GetRegionBindings(store);
1025 11: const SVal *V = Lookup(B, R, BindingKey::Direct);
1026 :
1027 : // Check if the region has a binding.
1: branch 0 taken
10: branch 1 taken
1028 11: if (V)
1029 1: return *V;
1030 :
1031 : // The location does not have a bound value. This means that it has
1032 : // the value it had upon its creation and/or entry to the analyzed
1033 : // function/method. These are either symbolic values or 'undefined'.
0: branch 1 not taken
10: branch 2 taken
1034 10: if (R->hasStackNonParametersStorage()) {
1035 : // All stack variables are considered to have undefined values
1036 : // upon creation. All heap allocated blocks are considered to
1037 : // have undefined values as well unless they are explicitly bound
1038 : // to specific values.
1039 0: return UndefinedVal();
1040 : }
1041 :
1042 : // All other values are symbolic.
1043 10: return ValMgr.getRegionValueSymbolVal(R, RTy);
1044 : }
1045 :
1046 : std::pair<Store, const MemRegion *>
1047 842: RegionStoreManager::GetLazyBinding(RegionBindings B, const MemRegion *R) {
10: branch 2 taken
832: branch 3 taken
1048 842: if (Optional<SVal> OV = getDirectBinding(B, R))
10: branch 0 taken
0: branch 1 not taken
1049 10: if (const nonloc::LazyCompoundVal *V =
1050 10: dyn_cast<nonloc::LazyCompoundVal>(OV.getPointer()))
832: branch 5 taken
10: branch 6 taken
1051 20: return std::make_pair(V->getStore(), V->getRegion());
1052 :
337: branch 1 taken
495: branch 2 taken
1053 832: if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
1054 : const std::pair<Store, const MemRegion *> &X =
1055 337: GetLazyBinding(B, ER->getSuperRegion());
1056 :
0: branch 0 not taken
337: branch 1 taken
1057 337: if (X.second)
1058 : return std::make_pair(X.first,
1059 0: MRMgr.getElementRegionWithSuper(ER, X.second));
1060 : }
110: branch 1 taken
385: branch 2 taken
1061 495: else if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) {
1062 : const std::pair<Store, const MemRegion *> &X =
1063 110: GetLazyBinding(B, FR->getSuperRegion());
1064 :
14: branch 0 taken
96: branch 1 taken
1065 110: if (X.second)
1066 : return std::make_pair(X.first,
1067 14: MRMgr.getFieldRegionWithSuper(FR, X.second));
1068 : }
1069 : // The NULL MemRegion indicates an non-existent lazy binding. A NULL Store is
1070 : // possible for a valid lazy binding.
1071 818: return std::make_pair((Store) 0, (const MemRegion *) 0);
1072 : }
1073 :
1074 : SVal RegionStoreManager::RetrieveElement(Store store,
1075 486: const ElementRegion* R) {
1076 : // Check if the region has a binding.
1077 486: RegionBindings B = GetRegionBindings(store);
95: branch 2 taken
391: branch 3 taken
1078 486: if (Optional<SVal> V = getDirectBinding(B, R))
391: branch 2 taken
95: branch 3 taken
1079 190: return *V;
1080 :
1081 391: const MemRegion* superR = R->getSuperRegion();
1082 :
1083 : // Check if the region is an element region of a string literal.
23: branch 1 taken
368: branch 2 taken
1084 391: if (const StringRegion *StrR=dyn_cast<StringRegion>(superR)) {
1085 : // FIXME: Handle loads from strings where the literal is treated as
1086 : // an integer, e.g., *((unsigned int*)"hello")
1087 23: ASTContext &Ctx = getContext();
1088 23: QualType T = Ctx.getAsArrayType(StrR->getValueType(Ctx))->getElementType();
2: branch 4 taken
21: branch 5 taken
1089 23: if (T != Ctx.getCanonicalType(R->getElementType()))
1090 2: return UnknownVal();
1091 :
1092 21: const StringLiteral *Str = StrR->getStringLiteral();
1093 21: SVal Idx = R->getIndex();
21: branch 1 taken
0: branch 2 not taken
1094 21: if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&Idx)) {
1095 21: int64_t i = CI->getValue().getSExtValue();
1096 21: int64_t byteLength = Str->getByteLength();
0: branch 0 not taken
21: branch 1 taken
1097 21: if (i > byteLength) {
1098 : // Buffer overflow checking in GRExprEngine should handle this case,
1099 : // but we shouldn't rely on it to not overflow here if that checking
1100 : // is disabled.
1101 0: return UnknownVal();
1102 : }
20: branch 0 taken
1: branch 1 taken
1103 21: char c = (i == byteLength) ? '\0' : Str->getStrData()[i];
1104 21: return ValMgr.makeIntVal(c, T);
0: branch 1 not taken
21: branch 2 taken
1105 21: }
1106 : }
1107 :
1108 : // Check if the immediate super region has a direct binding.
0: branch 2 not taken
368: branch 3 taken
1109 368: if (Optional<SVal> V = getDirectBinding(B, superR)) {
0: branch 2 not taken
0: branch 3 not taken
1110 0: if (SymbolRef parentSym = V->getAsSymbol())
1111 0: return ValMgr.getDerivedRegionValueSymbolVal(parentSym, R);
1112 :
0: branch 2 not taken
0: branch 3 not taken
1113 0: if (V->isUnknownOrUndef())
1114 0: return *V;
1115 :
1116 : // Handle LazyCompoundVals for the immediate super region. Other cases
1117 : // are handled in 'RetrieveFieldOrElementCommon'.
0: branch 0 not taken
0: branch 1 not taken
1118 0: if (const nonloc::LazyCompoundVal *LCV =
1119 0: dyn_cast<nonloc::LazyCompoundVal>(V)) {
1120 :
1121 0: R = MRMgr.getElementRegionWithSuper(R, LCV->getRegion());
1122 0: return RetrieveElement(LCV->getStore(), R);
1123 : }
1124 :
1125 : // Other cases: give up.
1126 0: return UnknownVal();
368: branch 1 taken
0: branch 2 not taken
1127 368: }
1128 :
1129 368: return RetrieveFieldOrElementCommon(store, R, R->getElementType(), superR);
1130 : }
1131 :
1132 : SVal RegionStoreManager::RetrieveField(Store store,
1133 149: const FieldRegion* R) {
1134 :
1135 : // Check if the region has a binding.
1136 149: RegionBindings B = GetRegionBindings(store);
29: branch 2 taken
120: branch 3 taken
1137 149: if (Optional<SVal> V = getDirectBinding(B, R))
120: branch 2 taken
29: branch 3 taken
1138 58: return *V;
1139 :
1140 120: QualType Ty = R->getValueType(getContext());
1141 120: return RetrieveFieldOrElementCommon(store, R, Ty, R->getSuperRegion());
1142 : }
1143 :
1144 : SVal RegionStoreManager::RetrieveFieldOrElementCommon(Store store,
1145 : const TypedRegion *R,
1146 : QualType Ty,
1147 488: const MemRegion *superR) {
1148 :
1149 : // At this point we have already checked in either RetrieveElement or
1150 : // RetrieveField if 'R' has a direct binding.
1151 :
1152 488: RegionBindings B = GetRegionBindings(store);
1153 :
573: branch 0 taken
0: branch 1 not taken
1154 488: while (superR) {
93: branch 2 taken
480: branch 3 taken
1155 573: if (const Optional<SVal> &D = getDefaultBinding(B, superR)) {
80: branch 2 taken
13: branch 3 taken
1156 93: if (SymbolRef parentSym = D->getAsSymbol())
1157 80: return ValMgr.getDerivedRegionValueSymbolVal(parentSym, R);
1158 :
6: branch 2 taken
7: branch 3 taken
1159 13: if (D->isZeroConstant())
1160 6: return ValMgr.makeZeroVal(Ty);
1161 :
7: branch 2 taken
0: branch 3 not taken
1162 7: if (D->isUnknown())
1163 7: return *D;
1164 :
1165 0: assert(0 && "Unknown default value");
480: branch 1 taken
93: branch 2 taken
1166 573: }
1167 :
1168 : // If our super region is a field or element itself, walk up the region
1169 : // hierarchy to see if there is a default value installed in an ancestor.
413: branch 1 taken
67: branch 2 taken
18: branch 4 taken
395: branch 5 taken
85: branch 6 taken
395: branch 7 taken
1170 480: if (isa<FieldRegion>(superR) || isa<ElementRegion>(superR)) {
1171 85: superR = cast<SubRegion>(superR)->getSuperRegion();
1172 85: continue;
1173 : }
1174 :
1175 395: break;
1176 : }
1177 :
1178 : // Lazy binding?
1179 395: Store lazyBindingStore = NULL;
1180 395: const MemRegion *lazyBindingRegion = NULL;
1181 395: llvm::tie(lazyBindingStore, lazyBindingRegion) = GetLazyBinding(B, R);
1182 :
10: branch 0 taken
385: branch 1 taken
1183 395: if (lazyBindingRegion) {
0: branch 1 not taken
10: branch 2 taken
1184 10: if (const ElementRegion *ER = dyn_cast<ElementRegion>(lazyBindingRegion))
1185 0: return RetrieveElement(lazyBindingStore, ER);
1186 : return RetrieveField(lazyBindingStore,
1187 10: cast<FieldRegion>(lazyBindingRegion));
1188 : }
1189 :
42: branch 1 taken
343: branch 2 taken
1190 385: if (R->hasStackNonParametersStorage()) {
36: branch 1 taken
6: branch 2 taken
1191 42: if (isa<ElementRegion>(R)) {
1192 : // Currently we don't reason specially about Clang-style vectors. Check
1193 : // if superR is a vector and if so return Unknown.
34: branch 1 taken
2: branch 2 taken
1194 36: if (const TypedRegion *typedSuperR = dyn_cast<TypedRegion>(superR)) {
0: branch 4 not taken
34: branch 5 taken
1195 34: if (typedSuperR->getValueType(getContext())->isVectorType())
1196 0: return UnknownVal();
1197 : }
1198 : }
1199 :
1200 42: return UndefinedVal();
1201 : }
1202 :
1203 : // All other values are symbolic.
1204 343: return ValMgr.getRegionValueSymbolVal(R, Ty);
1205 : }
1206 :
1207 51: SVal RegionStoreManager::RetrieveObjCIvar(Store store, const ObjCIvarRegion* R){
1208 :
1209 : // Check if the region has a binding.
1210 51: RegionBindings B = GetRegionBindings(store);
1211 :
14: branch 2 taken
37: branch 3 taken
1212 51: if (Optional<SVal> V = getDirectBinding(B, R))
37: branch 2 taken
14: branch 3 taken
1213 28: return *V;
1214 :
1215 37: const MemRegion *superR = R->getSuperRegion();
1216 :
1217 : // Check if the super region has a default binding.
0: branch 2 not taken
37: branch 3 taken
1218 37: if (Optional<SVal> V = getDefaultBinding(B, superR)) {
0: branch 2 not taken
0: branch 3 not taken
1219 0: if (SymbolRef parentSym = V->getAsSymbol())
1220 0: return ValMgr.getDerivedRegionValueSymbolVal(parentSym, R);
1221 :
1222 : // Other cases: give up.
1223 0: return UnknownVal();
37: branch 1 taken
0: branch 2 not taken
1224 37: }
1225 :
1226 37: return RetrieveLazySymbol(R);
1227 : }
1228 :
1229 4428: SVal RegionStoreManager::RetrieveVar(Store store, const VarRegion *R) {
1230 :
1231 : // Check if the region has a binding.
1232 4428: RegionBindings B = GetRegionBindings(store);
1233 :
2573: branch 2 taken
1855: branch 3 taken
1234 4428: if (Optional<SVal> V = getDirectBinding(B, R))
1855: branch 2 taken
2573: branch 3 taken
1235 5146: return *V;
1236 :
1237 : // Lazily derive a value for the VarRegion.
1238 1855: const VarDecl *VD = R->getDecl();
1239 1855: QualType T = VD->getType();
1240 1855: const MemSpaceRegion *MS = R->getMemorySpace();
1241 :
1845: branch 1 taken
10: branch 2 taken
1489: branch 4 taken
356: branch 5 taken
1499: branch 6 taken
356: branch 7 taken
1242 3700: if (isa<UnknownSpaceRegion>(MS) ||
1243 : isa<StackArgumentsSpaceRegion>(MS))
1244 1499: return ValMgr.getRegionValueSymbolVal(R, T);
1245 :
80: branch 1 taken
276: branch 2 taken
1246 356: if (isa<GlobalsSpaceRegion>(MS)) {
63: branch 1 taken
17: branch 2 taken
1247 80: if (VD->isFileVarDecl())
1248 63: return ValMgr.getRegionValueSymbolVal(R, T);
1249 :
9: branch 2 taken
8: branch 3 taken
1250 17: if (T->isIntegerType())
1251 9: return ValMgr.makeIntVal(0, T);
8: branch 2 taken
0: branch 3 not taken
1252 8: if (T->isPointerType())
1253 8: return ValMgr.makeNull();
1254 :
1255 0: return UnknownVal();
1256 : }
1257 :
1258 276: return UndefinedVal();
1259 : }
1260 :
1261 37: SVal RegionStoreManager::RetrieveLazySymbol(const TypedRegion *R) {
1262 :
1263 37: QualType valTy = R->getValueType(getContext());
1264 :
1265 : // All other values are symbolic.
1266 37: return ValMgr.getRegionValueSymbolVal(R, valTy);
1267 : }
1268 :
1269 52: SVal RegionStoreManager::RetrieveStruct(Store store, const TypedRegion* R) {
1270 52: QualType T = R->getValueType(getContext());
0: branch 2 not taken
52: branch 3 taken
1271 52: assert(T->isStructureType());
1272 :
1273 52: const RecordType* RT = T->getAsStructureType();
1274 52: RecordDecl* RD = RT->getDecl();
0: branch 1 not taken
52: branch 2 taken
1275 52: assert(RD->isDefinition());
1276 : (void)RD;
1277 : #if USE_EXPLICIT_COMPOUND
1278 : llvm::ImmutableList<SVal> StructVal = getBasicVals().getEmptySValList();
1279 :
1280 : // FIXME: We shouldn't use a std::vector. If RecordDecl doesn't have a
1281 : // reverse iterator, we should implement one.
1282 : std::vector<FieldDecl *> Fields(RD->field_begin(), RD->field_end());
1283 :
1284 : for (std::vector<FieldDecl *>::reverse_iterator Field = Fields.rbegin(),
1285 : FieldEnd = Fields.rend();
1286 : Field != FieldEnd; ++Field) {
1287 : FieldRegion* FR = MRMgr.getFieldRegion(*Field, R);
1288 : QualType FTy = (*Field)->getType();
1289 : SVal FieldValue = Retrieve(store, loc::MemRegionVal(FR), FTy).getSVal();
1290 : StructVal = getBasicVals().consVals(FieldValue, StructVal);
1291 : }
1292 :
1293 : return ValMgr.makeCompoundVal(T, StructVal);
1294 : #else
1295 52: return ValMgr.makeLazyCompoundVal(store, R);
1296 : #endif
1297 : }
1298 :
1299 0: SVal RegionStoreManager::RetrieveArray(Store store, const TypedRegion * R) {
1300 : #if USE_EXPLICIT_COMPOUND
1301 : QualType T = R->getValueType(getContext());
1302 : ConstantArrayType* CAT = cast<ConstantArrayType>(T.getTypePtr());
1303 :
1304 : llvm::ImmutableList<SVal> ArrayVal = getBasicVals().getEmptySValList();
1305 : uint64_t size = CAT->getSize().getZExtValue();
1306 : for (uint64_t i = 0; i < size; ++i) {
1307 : SVal Idx = ValMgr.makeArrayIndex(i);
1308 : ElementRegion* ER = MRMgr.getElementRegion(CAT->getElementType(), Idx, R,
1309 : getContext());
1310 : QualType ETy = ER->getElementType();
1311 : SVal ElementVal = Retrieve(store, loc::MemRegionVal(ER), ETy).getSVal();
1312 : ArrayVal = getBasicVals().consVals(ElementVal, ArrayVal);
1313 : }
1314 :
1315 : return ValMgr.makeCompoundVal(T, ArrayVal);
1316 : #else
0: branch 3 not taken
0: branch 4 not taken
1317 0: assert(isa<ConstantArrayType>(R->getValueType(getContext())));
1318 0: return ValMgr.makeLazyCompoundVal(store, R);
1319 : #endif
1320 : }
1321 :
1322 : //===----------------------------------------------------------------------===//
1323 : // Binding values to regions.
1324 : //===----------------------------------------------------------------------===//
1325 :
1326 147: Store RegionStoreManager::Remove(Store store, Loc L) {
0: branch 1 not taken
147: branch 2 taken
1327 147: if (isa<loc::MemRegionVal>(L))
0: branch 2 not taken
0: branch 3 not taken
1328 0: if (const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion())
1329 0: return Remove(GetRegionBindings(store), R).getRoot();
1330 :
1331 147: return store;
1332 : }
1333 :
1334 4291: Store RegionStoreManager::Bind(Store store, Loc L, SVal V) {
1: branch 1 taken
4290: branch 2 taken
1335 4291: if (isa<loc::ConcreteInt>(L))
1336 1: return store;
1337 :
1338 : // If we get here, the location should be a region.
1339 4290: const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion();
1340 :
1341 : // Check if the region is a struct region.
4209: branch 1 taken
81: branch 2 taken
1342 4290: if (const TypedRegion* TR = dyn_cast<TypedRegion>(R))
38: branch 4 taken
4171: branch 5 taken
1343 4209: if (TR->getValueType(getContext())->isStructureType())
1344 38: return BindStruct(store, TR, V);
1345 :
1346 : // Special case: the current region represents a cast and it and the super
1347 : // region both have pointer types or intptr_t types. If so, perform the
1348 : // bind to the super region.
1349 : // This is needed to support OSAtomicCompareAndSwap and friends or other
1350 : // loads that treat integers as pointers and vis versa.
331: branch 1 taken
3921: branch 2 taken
1351 4252: if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
180: branch 3 taken
151: branch 4 taken
1352 331: if (ER->getIndex().isZeroConstant()) {
160: branch 0 taken
20: branch 1 taken
1353 180: if (const TypedRegion *superR =
1354 180: dyn_cast<TypedRegion>(ER->getSuperRegion())) {
1355 160: ASTContext &Ctx = getContext();
1356 160: QualType superTy = superR->getValueType(Ctx);
1357 160: QualType erTy = ER->getValueType(Ctx);
1358 :
60: branch 1 taken
100: branch 2 taken
58: branch 4 taken
2: branch 5 taken
58: branch 6 taken
102: branch 7 taken
1359 160: if (IsAnyPointerOrIntptr(superTy, Ctx) &&
1360 : IsAnyPointerOrIntptr(erTy, Ctx)) {
1361 58: V = ValMgr.getSValuator().EvalCast(V, superTy, erTy);
1362 58: return Bind(store, loc::MemRegionVal(superR), V);
1363 : }
1364 : // For now, just invalidate the fields of the struct/union/class.
1365 : // FIXME: Precisely handle the fields of the record.
7: branch 2 taken
95: branch 3 taken
1366 102: if (superTy->isRecordType())
1367 7: return InvalidateRegion(store, superR, NULL, 0, NULL);
1368 : }
1369 : }
1370 : }
81: branch 1 taken
3840: branch 2 taken
1371 3921: else if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) {
1372 : // Binding directly to a symbolic region should be treated as binding
1373 : // to element 0.
1374 81: QualType T = SR->getSymbol()->getType(getContext());
1375 :
1376 : // FIXME: Is this the right way to handle symbols that are references?
77: branch 2 taken
4: branch 3 taken
1377 81: if (const PointerType *PT = T->getAs<PointerType>())
1378 77: T = PT->getPointeeType();
1379 : else
1380 4: T = T->getAs<ReferenceType>()->getPointeeType();
1381 :
1382 81: R = GetElementZeroRegion(SR, T);
1383 : }
1384 :
1385 : // Perform the binding.
1386 4187: RegionBindings B = GetRegionBindings(store);
1387 4187: return Add(B, R, BindingKey::Direct, V).getRoot();
1388 : }
1389 :
1390 : Store RegionStoreManager::BindDecl(Store store, const VarRegion *VR,
1391 990: SVal InitVal) {
1392 :
1393 990: QualType T = VR->getDecl()->getType();
1394 :
26: branch 2 taken
964: branch 3 taken
1395 990: if (T->isArrayType())
1396 26: return BindArray(store, VR, InitVal);
32: branch 2 taken
932: branch 3 taken
1397 964: if (T->isStructureType())
1398 32: return BindStruct(store, VR, InitVal);
1399 :
1400 932: return Bind(store, ValMgr.makeLoc(VR), InitVal);
1401 : }
1402 :
1403 : // FIXME: this method should be merged into Bind().
1404 : Store RegionStoreManager::BindCompoundLiteral(Store store,
1405 : const CompoundLiteralExpr *CL,
1406 : const LocationContext *LC,
1407 17: SVal V) {
1408 : return Bind(store, loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL, LC)),
1409 17: V);
1410 : }
1411 :
1412 : Store RegionStoreManager::setImplicitDefaultValue(Store store,
1413 : const MemRegion *R,
1414 12: QualType T) {
1415 12: RegionBindings B = GetRegionBindings(store);
1416 12: SVal V;
1417 :
0: branch 1 not taken
12: branch 2 taken
1418 12: if (Loc::IsLocType(T))
1419 0: V = ValMgr.makeNull();
6: branch 2 taken
6: branch 3 taken
1420 12: else if (T->isIntegerType())
1421 6: V = ValMgr.makeZeroVal(T);
2: branch 2 taken
4: branch 3 taken
0: branch 6 not taken
2: branch 7 taken
4: branch 8 taken
2: branch 9 taken
1422 6: else if (T->isStructureType() || T->isArrayType()) {
1423 : // Set the default value to a zero constant when it is a structure
1424 : // or array. The type doesn't really matter.
1425 4: V = ValMgr.makeZeroVal(ValMgr.getContext().IntTy);
1426 : }
1427 : else {
1428 2: return store;
1429 : }
1430 :
1431 10: return Add(B, R, BindingKey::Default, V).getRoot();
1432 : }
1433 :
1434 : Store RegionStoreManager::BindArray(Store store, const TypedRegion* R,
1435 38: SVal Init) {
1436 :
1437 38: ASTContext &Ctx = getContext();
1438 : const ArrayType *AT =
1439 38: cast<ArrayType>(Ctx.getCanonicalType(R->getValueType(Ctx)));
1440 38: QualType ElementTy = AT->getElementType();
1441 38: Optional<uint64_t> Size;
1442 :
34: branch 1 taken
4: branch 2 taken
1443 38: if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(AT))
1444 34: Size = CAT->getSize().getZExtValue();
1445 :
1446 : // Check if the init expr is a StringLiteral.
6: branch 1 taken
32: branch 2 taken
1447 38: if (isa<loc::MemRegionVal>(Init)) {
1448 6: const MemRegion* InitR = cast<loc::MemRegionVal>(Init).getRegion();
1449 6: const StringLiteral* S = cast<StringRegion>(InitR)->getStringLiteral();
1450 6: const char* str = S->getStrData();
1451 6: unsigned len = S->getByteLength();
1452 6: unsigned j = 0;
1453 :
1454 : // Copy bytes from the string literal into the target array. Trailing bytes
1455 : // in the array that are not covered by the string literal are initialized
1456 : // to zero.
1457 :
1458 : // We assume that string constants are bound to
1459 : // constant arrays.
1460 6: uint64_t size = Size.getValue();
1461 :
48: branch 2 taken
0: branch 3 not taken
1462 48: for (uint64_t i = 0; i < size; ++i, ++j) {
6: branch 0 taken
42: branch 1 taken
1463 48: if (j >= len)
1464 6: break;
1465 :
1466 42: SVal Idx = ValMgr.makeArrayIndex(i);
1467 : const ElementRegion* ER = MRMgr.getElementRegion(ElementTy, Idx, R,
1468 42: getContext());
1469 :
1470 42: SVal V = ValMgr.makeIntVal(str[j], sizeof(char)*8, true);
1471 42: store = Bind(store, loc::MemRegionVal(ER), V);
1472 : }
1473 :
1474 6: return store;
1475 : }
1476 :
1477 : // Handle lazy compound values.
0: branch 1 not taken
32: branch 2 taken
1478 32: if (nonloc::LazyCompoundVal *LCV = dyn_cast<nonloc::LazyCompoundVal>(&Init))
1479 0: return CopyLazyBindings(*LCV, store, R);
1480 :
1481 : // Remaining case: explicit compound values.
1482 :
6: branch 1 taken
26: branch 2 taken
1483 32: if (Init.isUnknown())
1484 6: return setImplicitDefaultValue(store, R, ElementTy);
1485 :
1486 26: nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(Init);
1487 26: nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
1488 26: uint64_t i = 0;
1489 :
132: branch 3 taken
10: branch 4 taken
126: branch 6 taken
16: branch 7 taken
1490 142: for (; Size.hasValue() ? i < Size.getValue() : true ; ++i, ++VI) {
1491 : // The init list might be shorter than the array length.
10: branch 1 taken
116: branch 2 taken
1492 126: if (VI == VE)
1493 10: break;
1494 :
1495 116: SVal Idx = ValMgr.makeArrayIndex(i);
1496 116: const ElementRegion *ER = MRMgr.getElementRegion(ElementTy, Idx, R, getContext());
1497 :
2: branch 2 taken
114: branch 3 taken
1498 116: if (ElementTy->isStructureType())
1499 2: store = BindStruct(store, ER, *VI);
1500 : else
1501 114: store = Bind(store, ValMgr.makeLoc(ER), *VI);
1502 : }
1503 :
1504 : // If the init list is shorter than the array length, set the
1505 : // array default value.
22: branch 1 taken
4: branch 2 taken
6: branch 4 taken
16: branch 5 taken
6: branch 6 taken
20: branch 7 taken
1506 26: if (Size.hasValue() && i < Size.getValue())
1507 6: store = setImplicitDefaultValue(store, R, ElementTy);
1508 :
1509 26: return store;
1510 : }
1511 :
1512 : Store RegionStoreManager::BindStruct(Store store, const TypedRegion* R,
1513 72: SVal V) {
1514 :
0: branch 1 not taken
72: branch 2 taken
1515 72: if (!Features.supportsFields())
1516 0: return store;
1517 :
1518 72: QualType T = R->getValueType(getContext());
0: branch 2 not taken
72: branch 3 taken
1519 72: assert(T->isStructureType());
1520 :
1521 72: const RecordType* RT = T->getAs<RecordType>();
1522 72: RecordDecl* RD = RT->getDecl();
1523 :
0: branch 1 not taken
72: branch 2 taken
1524 72: if (!RD->isDefinition())
1525 0: return store;
1526 :
1527 : // Handle lazy compound values.
12: branch 1 taken
60: branch 2 taken
1528 72: if (const nonloc::LazyCompoundVal *LCV=dyn_cast<nonloc::LazyCompoundVal>(&V))
1529 12: return CopyLazyBindings(*LCV, store, R);
1530 :
1531 : // We may get non-CompoundVal accidentally due to imprecise cast logic.
1532 : // Ignore them and kill the field values.
30: branch 1 taken
30: branch 2 taken
0: branch 4 not taken
30: branch 5 taken
30: branch 6 taken
30: branch 7 taken
1533 60: if (V.isUnknown() || !isa<nonloc::CompoundVal>(V))
1534 30: return KillStruct(store, R);
1535 :
1536 30: nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V);
1537 30: nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
1538 :
1539 30: RecordDecl::field_iterator FI, FE;
1540 :
58: branch 5 taken
30: branch 6 taken
1541 88: for (FI = RD->field_begin(), FE = RD->field_end(); FI != FE; ++FI, ++VI) {
1542 :
0: branch 1 not taken
58: branch 2 taken
1543 58: if (VI == VE)
1544 0: break;
1545 :
1546 58: QualType FTy = (*FI)->getType();
1547 58: const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);
1548 :
12: branch 2 taken
46: branch 3 taken
1549 58: if (FTy->isArrayType())
1550 12: store = BindArray(store, FR, *VI);
0: branch 2 not taken
46: branch 3 taken
1551 46: else if (FTy->isStructureType())
1552 0: store = BindStruct(store, FR, *VI);
1553 : else
1554 46: store = Bind(store, ValMgr.makeLoc(FR), *VI);
1555 : }
1556 :
1557 : // There may be fewer values in the initialize list than the fields of struct.
0: branch 1 not taken
30: branch 2 taken
1558 30: if (FI != FE) {
1559 0: RegionBindings B = GetRegionBindings(store);
1560 0: B = Add(B, R, BindingKey::Default, ValMgr.makeIntVal(0, false));
1561 0: store = B.getRoot();
1562 : }
1563 :
1564 30: return store;
1565 : }
1566 :
1567 30: Store RegionStoreManager::KillStruct(Store store, const TypedRegion* R) {
1568 30: RegionBindings B = GetRegionBindings(store);
1569 : llvm::OwningPtr<RegionStoreSubRegionMap>
1570 30: SubRegions(getRegionStoreSubRegionMap(store));
1571 30: RemoveSubRegionBindings(B, R, *SubRegions);
1572 :
1573 : // Set the default value of the struct region to "unknown".
1574 30: return Add(B, R, BindingKey::Default, UnknownVal()).getRoot();
1575 : }
1576 :
1577 : Store RegionStoreManager::CopyLazyBindings(nonloc::LazyCompoundVal V,
1578 12: Store store, const TypedRegion *R) {
1579 :
1580 : // Nuke the old bindings stemming from R.
1581 12: RegionBindings B = GetRegionBindings(store);
1582 :
1583 : llvm::OwningPtr<RegionStoreSubRegionMap>
1584 12: SubRegions(getRegionStoreSubRegionMap(store));
1585 :
1586 : // B and DVM are updated after the call to RemoveSubRegionBindings.
1587 12: RemoveSubRegionBindings(B, R, *SubRegions.get());
1588 :
1589 : // Now copy the bindings. This amounts to just binding 'V' to 'R'. This
1590 : // results in a zero-copy algorithm.
1591 12: return Add(B, R, BindingKey::Direct, V).getRoot();
1592 : }
1593 :
1594 : //===----------------------------------------------------------------------===//
1595 : // "Raw" retrievals and bindings.
1596 : //===----------------------------------------------------------------------===//
1597 :
1598 27025: BindingKey BindingKey::Make(const MemRegion *R, Kind k) {
3006: branch 1 taken
24019: branch 2 taken
1599 27025: if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
1600 3006: const RegionRawOffset &O = ER->getAsRawOffset();
1601 :
2562: branch 1 taken
444: branch 2 taken
1602 3006: if (O.getRegion())
1603 2562: return BindingKey(O.getRegion(), O.getByteOffset(), k);
1604 :
1605 : // FIXME: There are some ElementRegions for which we cannot compute
1606 : // raw offsets yet, including regions with symbolic offsets.
1607 : }
1608 :
1609 24463: return BindingKey(R, 0, k);
1610 : }
1611 :
1612 4688: RegionBindings RegionStoreManager::Add(RegionBindings B, BindingKey K, SVal V) {
1613 4688: return RBFactory.Add(B, K, V);
1614 : }
1615 :
1616 : RegionBindings RegionStoreManager::Add(RegionBindings B, const MemRegion *R,
1617 4688: BindingKey::Kind k, SVal V) {
1618 4688: return Add(B, BindingKey::Make(R, k), V);
1619 : }
1620 :
1621 22342: const SVal *RegionStoreManager::Lookup(RegionBindings B, BindingKey K) {
1622 22342: return B.lookup(K);
1623 : }
1624 :
1625 : const SVal *RegionStoreManager::Lookup(RegionBindings B,
1626 : const MemRegion *R,
1627 22181: BindingKey::Kind k) {
1628 22181: return Lookup(B, BindingKey::Make(R, k));
1629 : }
1630 :
1631 1985: RegionBindings RegionStoreManager::Remove(RegionBindings B, BindingKey K) {
1632 1985: return RBFactory.Remove(B, K);
1633 : }
1634 :
1635 : RegionBindings RegionStoreManager::Remove(RegionBindings B, const MemRegion *R,
1636 156: BindingKey::Kind k){
1637 156: return Remove(B, BindingKey::Make(R, k));
1638 : }
1639 :
1640 1668: Store RegionStoreManager::Remove(Store store, BindingKey K) {
1641 1668: RegionBindings B = GetRegionBindings(store);
1642 1668: return Remove(B, K).getRoot();
1643 : }
1644 :
1645 : //===----------------------------------------------------------------------===//
1646 : // State pruning.
1647 : //===----------------------------------------------------------------------===//
1648 :
1649 : Store RegionStoreManager::RemoveDeadBindings(Store store, Stmt* Loc,
1650 : SymbolReaper& SymReaper,
1651 6168: llvm::SmallVectorImpl<const MemRegion*>& RegionRoots)
1652 : {
1653 : typedef std::pair<Store, const MemRegion *> RBDNode;
1654 :
1655 6168: RegionBindings B = GetRegionBindings(store);
1656 :
1657 : // The backmap from regions to subregions.
1658 : llvm::OwningPtr<RegionStoreSubRegionMap>
1659 6168: SubRegions(getRegionStoreSubRegionMap(store));
1660 :
1661 : // Do a pass over the regions in the store. For VarRegions we check if
1662 : // the variable is still live and if so add it to the list of live roots.
1663 : // For other regions we populate our region backmap.
1664 6168: llvm::SmallVector<const MemRegion*, 10> IntermediateRoots;
1665 :
1666 : // Scan the direct bindings for "intermediate" roots.
8788: branch 4 taken
6168: branch 5 taken
1667 14956: for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) {
1668 8788: const MemRegion *R = I.getKey().getRegion();
1669 8788: IntermediateRoots.push_back(R);
1670 6168: }
1671 :
1672 : // Process the "intermediate" roots to find if they are referenced by
1673 : // real roots.
1674 6168: llvm::SmallVector<RBDNode, 10> WorkList;
1675 6168: llvm::SmallVector<RBDNode, 10> Postponed;
1676 :
1677 6168: llvm::DenseSet<const MemRegion*> IntermediateVisited;
1678 :
8989: branch 1 taken
6168: branch 2 taken
1679 21325: while (!IntermediateRoots.empty()) {
1680 8989: const MemRegion* R = IntermediateRoots.back();
1681 8989: IntermediateRoots.pop_back();
1682 :
547: branch 1 taken
8442: branch 2 taken
1683 8989: if (IntermediateVisited.count(R))
1684 547: continue;
1685 8442: IntermediateVisited.insert(R);
1686 :
7543: branch 1 taken
899: branch 2 taken
1687 8442: if (const VarRegion* VR = dyn_cast<VarRegion>(R)) {
5866: branch 1 taken
1677: branch 2 taken
1688 7543: if (SymReaper.isLive(Loc, VR))
1689 5866: WorkList.push_back(std::make_pair(store, VR));
1690 7543: continue;
1691 : }
1692 :
674: branch 1 taken
225: branch 2 taken
1693 899: if (const SymbolicRegion* SR = dyn_cast<SymbolicRegion>(R)) {
1694 : llvm::SmallVectorImpl<RBDNode> &Q =
566: branch 2 taken
108: branch 3 taken
1695 674: SymReaper.isLive(SR->getSymbol()) ? WorkList : Postponed;
1696 :
1697 674: Q.push_back(std::make_pair(store, SR));
1698 :
1699 674: continue;
1700 : }
1701 :
1702 : // Add the super region for R to the worklist if it is a subregion.
201: branch 0 taken
24: branch 1 taken
1703 225: if (const SubRegion* superR =
1704 225: dyn_cast<SubRegion>(cast<SubRegion>(R)->getSuperRegion()))
1705 201: IntermediateRoots.push_back(superR);
1706 : }
1707 :
1708 : // Enqueue the RegionRoots onto WorkList.
1108: branch 1 taken
6168: branch 2 taken
1709 13444: for (llvm::SmallVectorImpl<const MemRegion*>::iterator I=RegionRoots.begin(),
1710 6168: E=RegionRoots.end(); I!=E; ++I) {
1711 1108: WorkList.push_back(std::make_pair(store, *I));
1712 : }
1713 6168: RegionRoots.clear();
1714 :
1715 6168: llvm::DenseSet<RBDNode> Visited;
1716 :
1717 6223: tryAgain:
11274: branch 2 taken
6223: branch 3 taken
1718 16868: while (!WorkList.empty()) {
1719 11274: RBDNode N = WorkList.back();
1720 11274: WorkList.pop_back();
1721 :
1722 : // Have we visited this node before?
601: branch 1 taken
10673: branch 2 taken
1723 11274: if (Visited.count(N))
1724 601: continue;
1725 10673: Visited.insert(N);
1726 :
1727 10673: const MemRegion *R = N.second;
1728 10673: Store store_N = N.first;
1729 :
1730 : // Enqueue subregions.
1731 : RegionStoreSubRegionMap *M;
1732 :
10661: branch 0 taken
12: branch 1 taken
1733 10673: if (store == store_N)
1734 10661: M = SubRegions.get();
1735 : else {
1736 12: RegionStoreSubRegionMap *& SM = SC[store_N];
6: branch 0 taken
6: branch 1 taken
1737 12: if (!SM)
1738 6: SM = getRegionStoreSubRegionMap(store_N);
1739 12: M = SM;
1740 : }
1741 :
201: branch 1 taken
10472: branch 2 taken
1742 10673: if (const RegionStoreSubRegionMap::Set *S = M->getSubRegions(R))
299: branch 4 taken
201: branch 5 taken
1743 500: for (RegionStoreSubRegionMap::Set::iterator I = S->begin(), E = S->end();
1744 : I != E; ++I)
1745 500: WorkList.push_back(std::make_pair(store_N, *I));
1746 :
1747 : // Enqueue the super region.
10239: branch 1 taken
434: branch 2 taken
1748 10673: if (const SubRegion *SR = dyn_cast<SubRegion>(R)) {
1749 10239: const MemRegion *superR = SR->getSuperRegion();
1245: branch 1 taken
8994: branch 2 taken
1750 10239: if (!isa<MemSpaceRegion>(superR)) {
1751 : // If 'R' is a field or an element, we want to keep the bindings
1752 : // for the other fields and elements around. The reason is that
1753 : // pointer arithmetic can get us to the other fields or elements.
1754 : assert(isa<FieldRegion>(R) || isa<ElementRegion>(R)
981: branch 1 taken
264: branch 2 taken
36: branch 4 taken
945: branch 5 taken
0: branch 7 not taken
36: branch 8 taken
1755 1245: || isa<ObjCIvarRegion>(R));
1756 1245: WorkList.push_back(std::make_pair(store_N, superR));
1757 : }
1758 : }
1759 :
1760 : // Mark the symbol for any live SymbolicRegion as "live". This means we
1761 : // should continue to track that symbol.
2538: branch 1 taken
8135: branch 2 taken
1762 10673: if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(R))
1763 2538: SymReaper.markLive(SymR->getSymbol());
1764 :
1765 : // For BlockDataRegions, enqueue the VarRegions for variables marked
1766 : // with __block (passed-by-reference).
1767 : // via BlockDeclRefExprs.
28: branch 1 taken
10645: branch 2 taken
1768 10673: if (const BlockDataRegion *BD = dyn_cast<BlockDataRegion>(R)) {
50: branch 2 taken
28: branch 3 taken
1769 78: for (BlockDataRegion::referenced_vars_iterator
1770 28: RI = BD->referenced_vars_begin(), RE = BD->referenced_vars_end();
1771 : RI != RE; ++RI) {
26: branch 3 taken
24: branch 4 taken
1772 50: if ((*RI)->getDecl()->getAttr<BlocksAttr>())
1773 26: WorkList.push_back(std::make_pair(store_N, *RI));
1774 : }
1775 : // No possible data bindings on a BlockDataRegion. Continue to the
1776 : // next region in the worklist.
1777 28: continue;
1778 : }
1779 :
1780 10645: RegionBindings B_N = GetRegionBindings(store_N);
1781 :
1782 : // Get the data binding for R (if any).
1783 10645: Optional<SVal> V = getBinding(B_N, R);
1784 :
6771: branch 1 taken
3874: branch 2 taken
1785 10645: if (V) {
1786 : // Check for lazy bindings.
8: branch 0 taken
6763: branch 1 taken
1787 6771: if (const nonloc::LazyCompoundVal *LCV =
1788 6771: dyn_cast<nonloc::LazyCompoundVal>(V.getPointer())) {
1789 :
1790 8: const LazyCompoundValData *D = LCV->getCVData();
1791 8: WorkList.push_back(std::make_pair(D->getStore(), D->getRegion()));
1792 : }
1793 : else {
1794 : // Update the set of live symbols.
2540: branch 6 taken
6763: branch 7 taken
1795 9303: for (SVal::symbol_iterator SI=V->symbol_begin(), SE=V->symbol_end();
1796 : SI!=SE;++SI)
1797 9303: SymReaper.markLive(*SI);
1798 :
1799 : // If V is a region, then add it to the worklist.
2093: branch 2 taken
4670: branch 3 taken
1800 6763: if (const MemRegion *RX = V->getAsRegion())
1801 2093: WorkList.push_back(std::make_pair(store_N, RX));
1802 : }
1803 : }
1804 : }
1805 :
1806 : // See if any postponed SymbolicRegions are actually live now, after
1807 : // having done a scan.
176: branch 1 taken
6223: branch 2 taken
1808 12622: for (llvm::SmallVectorImpl<RBDNode>::iterator I = Postponed.begin(),
1809 6223: E = Postponed.end() ; I != E ; ++I) {
111: branch 1 taken
65: branch 2 taken
1810 176: if (const SymbolicRegion *SR = cast_or_null<SymbolicRegion>(I->second)) {
63: branch 2 taken
48: branch 3 taken
1811 111: if (SymReaper.isLive(SR->getSymbol())) {
1812 63: WorkList.push_back(*I);
1813 63: I->second = NULL;
1814 : }
1815 : }
1816 : }
1817 :
55: branch 1 taken
6168: branch 2 taken
1818 6223: if (!WorkList.empty())
1819 55: goto tryAgain;
1820 :
1821 : // We have now scanned the store, marking reachable regions and symbols
1822 : // as live. We now remove all the regions that are dead from the store
1823 : // as well as update DSymbols with the set symbols that are now dead.
1824 6168: Store new_store = store;
8788: branch 7 taken
6168: branch 8 taken
1825 7836: for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) {
1826 8788: const MemRegion* R = I.getKey().getRegion();
1827 : // If this region live? Is so, none of its symbols are dead.
7120: branch 2 taken
1668: branch 3 taken
1828 8788: if (Visited.count(std::make_pair(store, R)))
1829 7120: continue;
1830 :
1831 : // Remove this dead region from the store.
1832 1668: new_store = Remove(new_store, I.getKey());
1833 :
1834 : // Mark all non-live symbols that this region references as dead.
45: branch 1 taken
1623: branch 2 taken
1835 1668: if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(R))
1836 45: SymReaper.maybeDead(SymR->getSymbol());
1837 :
1838 1668: SVal X = I.getData();
1839 1668: SVal::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
483: branch 2 taken
1668: branch 3 taken
1840 2151: for (; SI != SE; ++SI)
1841 483: SymReaper.maybeDead(*SI);
1842 6168: }
1843 :
1844 6168: return new_store;
1845 : }
1846 :
1847 : GRState const *RegionStoreManager::EnterStackFrame(GRState const *state,
1848 0: StackFrameContext const *frame) {
1849 0: FunctionDecl const *FD = cast<FunctionDecl>(frame->getDecl());
1850 0: CallExpr const *CE = cast<CallExpr>(frame->getCallSite());
1851 :
1852 0: FunctionDecl::param_const_iterator PI = FD->param_begin();
1853 :
1854 0: CallExpr::const_arg_iterator AI = CE->arg_begin(), AE = CE->arg_end();
1855 :
1856 : // Copy the arg expression value to the arg variables.
1857 0: Store store = state->getStore();
0: branch 3 not taken
0: branch 4 not taken
1858 0: for (; AI != AE; ++AI, ++PI) {
1859 0: SVal ArgVal = state->getSVal(*AI);
1860 0: store = Bind(store, ValMgr.makeLoc(MRMgr.getVarRegion(*PI, frame)), ArgVal);
1861 : }
1862 :
1863 0: return state->makeWithStore(store);
1864 : }
1865 :
1866 : //===----------------------------------------------------------------------===//
1867 : // Utility methods.
1868 : //===----------------------------------------------------------------------===//
1869 :
1870 : void RegionStoreManager::print(Store store, llvm::raw_ostream& OS,
1871 0: const char* nl, const char *sep) {
1872 0: RegionBindings B = GetRegionBindings(store);
1873 0: OS << "Store (direct and default bindings):" << nl;
1874 :
0: branch 4 not taken
0: branch 5 not taken
1875 0: for (RegionBindings::iterator I = B.begin(), E = B.end(); I != E; ++I)
1876 0: OS << ' ' << I.getKey() << " : " << I.getData() << nl;
1877 0: }
Generated: 2010-02-10 01:31 by zcov