1 //== RegionStore.cpp - Field-sensitive store model --------------*- C++ -*--==//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
16 //===----------------------------------------------------------------------===//
17 #include "clang/Analysis/PathSensitive/MemRegion.h"
18 #include "clang/Analysis/PathSensitive/GRState.h"
19 #include "clang/Analysis/PathSensitive/GRStateTrait.h"
20 #include "clang/Analysis/Analyses/LiveVariables.h"
21 #include "clang/Basic/TargetInfo.h"
23 #include "llvm/ADT/ImmutableMap.h"
24 #include "llvm/ADT/ImmutableList.h"
25 #include "llvm/Support/raw_ostream.h"
26 #include "llvm/Support/Compiler.h"
28 using namespace clang;
31 typedef llvm::ImmutableMap<const MemRegion*, SVal> RegionBindingsTy;
33 //===----------------------------------------------------------------------===//
34 // Fine-grained control of RegionStoreManager.
35 //===----------------------------------------------------------------------===//
38 struct VISIBILITY_HIDDEN minimal_features_tag {};
39 struct VISIBILITY_HIDDEN maximal_features_tag {};
41 class VISIBILITY_HIDDEN RegionStoreFeatures {
43 bool SupportsRemaining;
46 RegionStoreFeatures(minimal_features_tag) :
47 SupportsFields(false), SupportsRemaining(false) {}
49 RegionStoreFeatures(maximal_features_tag) :
50 SupportsFields(true), SupportsRemaining(false) {}
52 void enableFields(bool t) { SupportsFields = t; }
54 bool supportsFields() const { return SupportsFields; }
55 bool supportsRemaining() const { return SupportsRemaining; }
59 //===----------------------------------------------------------------------===//
61 //===----------------------------------------------------------------------===//
63 // MemRegions can be layered on top of each other. This GDM entry tracks
64 // what are the MemRegions that layer a given MemRegion.
66 typedef llvm::ImmutableSet<const MemRegion*> RegionViews;
67 namespace { class VISIBILITY_HIDDEN RegionViewMap {}; }
68 static int RegionViewMapIndex = 0;
70 template<> struct GRStateTrait<RegionViewMap>
71 : public GRStatePartialTrait<llvm::ImmutableMap<const MemRegion*,
74 static void* GDMIndex() { return &RegionViewMapIndex; }
78 // RegionCasts records the current cast type of a region.
79 namespace { class VISIBILITY_HIDDEN RegionCasts {}; }
80 static int RegionCastsIndex = 0;
82 template<> struct GRStateTrait<RegionCasts>
83 : public GRStatePartialTrait<llvm::ImmutableMap<const MemRegion*,
85 static void* GDMIndex() { return &RegionCastsIndex; }
89 //===----------------------------------------------------------------------===//
91 //===----------------------------------------------------------------------===//
93 // MemRegions represent chunks of memory with a size (their "extent"). This
94 // GDM entry tracks the extents for regions. Extents are in bytes.
96 namespace { class VISIBILITY_HIDDEN RegionExtents {}; }
97 static int RegionExtentsIndex = 0;
99 template<> struct GRStateTrait<RegionExtents>
100 : public GRStatePartialTrait<llvm::ImmutableMap<const MemRegion*, SVal> > {
101 static void* GDMIndex() { return &RegionExtentsIndex; }
105 //===----------------------------------------------------------------------===//
106 // Region "killsets".
107 //===----------------------------------------------------------------------===//
109 // RegionStore lazily adds value bindings to regions when the analyzer handles
110 // assignment statements. Killsets track which default values have been
111 // killed, thus distinguishing between "unknown" values and default
112 // values. Regions are added to killset only when they are assigned "unknown"
113 // directly, otherwise we should have their value in the region bindings.
115 namespace { class VISIBILITY_HIDDEN RegionKills {}; }
116 static int RegionKillsIndex = 0;
118 template<> struct GRStateTrait<RegionKills>
119 : public GRStatePartialTrait< llvm::ImmutableSet<const MemRegion*> > {
120 static void* GDMIndex() { return &RegionKillsIndex; }
124 //===----------------------------------------------------------------------===//
125 // Regions with default values.
126 //===----------------------------------------------------------------------===//
128 // This GDM entry tracks what regions have a default value if they have no bound
129 // value and have not been killed.
131 namespace { class VISIBILITY_HIDDEN RegionDefaultValue {}; }
132 static int RegionDefaultValueIndex = 0;
134 template<> struct GRStateTrait<RegionDefaultValue>
135 : public GRStatePartialTrait<llvm::ImmutableMap<const MemRegion*, SVal> > {
136 static void* GDMIndex() { return &RegionDefaultValueIndex; }
140 //===----------------------------------------------------------------------===//
141 // Main RegionStore logic.
142 //===----------------------------------------------------------------------===//
146 class VISIBILITY_HIDDEN RegionStoreSubRegionMap : public SubRegionMap {
147 typedef llvm::DenseMap<const MemRegion*,
148 llvm::ImmutableSet<const MemRegion*> > Map;
150 llvm::ImmutableSet<const MemRegion*>::Factory F;
154 void add(const MemRegion* Parent, const MemRegion* SubRegion) {
155 Map::iterator I = M.find(Parent);
156 M.insert(std::make_pair(Parent,
157 F.Add(I == M.end() ? F.GetEmptySet() : I->second, SubRegion)));
160 ~RegionStoreSubRegionMap() {}
162 bool iterSubRegions(const MemRegion* Parent, Visitor& V) const {
163 Map::iterator I = M.find(Parent);
168 llvm::ImmutableSet<const MemRegion*> S = I->second;
169 for (llvm::ImmutableSet<const MemRegion*>::iterator SI=S.begin(),SE=S.end();
171 if (!V.Visit(Parent, *SI))
179 class VISIBILITY_HIDDEN RegionStoreManager : public StoreManager {
180 const RegionStoreFeatures Features;
181 RegionBindingsTy::Factory RBFactory;
182 RegionViews::Factory RVFactory;
184 const MemRegion* SelfRegion;
185 const ImplicitParamDecl *SelfDecl;
188 RegionStoreManager(GRStateManager& mgr, const RegionStoreFeatures &f)
191 RBFactory(mgr.getAllocator()),
192 RVFactory(mgr.getAllocator()),
193 SelfRegion(0), SelfDecl(0) {
194 if (const ObjCMethodDecl* MD =
195 dyn_cast<ObjCMethodDecl>(&StateMgr.getCodeDecl()))
196 SelfDecl = MD->getSelfDecl();
199 virtual ~RegionStoreManager() {}
201 SubRegionMap* getSubRegionMap(const GRState *state);
203 /// getLValueString - Returns an SVal representing the lvalue of a
204 /// StringLiteral. Within RegionStore a StringLiteral has an
205 /// associated StringRegion, and the lvalue of a StringLiteral is
206 /// the lvalue of that region.
207 SVal getLValueString(const GRState *state, const StringLiteral* S);
209 /// getLValueCompoundLiteral - Returns an SVal representing the
210 /// lvalue of a compound literal. Within RegionStore a compound
211 /// literal has an associated region, and the lvalue of the
212 /// compound literal is the lvalue of that region.
213 SVal getLValueCompoundLiteral(const GRState *state, const CompoundLiteralExpr*);
215 /// getLValueVar - Returns an SVal that represents the lvalue of a
216 /// variable. Within RegionStore a variable has an associated
217 /// VarRegion, and the lvalue of the variable is the lvalue of that region.
218 SVal getLValueVar(const GRState *state, const VarDecl* VD);
220 SVal getLValueIvar(const GRState *state, const ObjCIvarDecl* D, SVal Base);
222 SVal getLValueField(const GRState *state, SVal Base, const FieldDecl* D);
224 SVal getLValueFieldOrIvar(const GRState *state, SVal Base, const Decl* D);
226 SVal getLValueElement(const GRState *state, QualType elementType,
227 SVal Base, SVal Offset);
230 /// ArrayToPointer - Emulates the "decay" of an array to a pointer
231 /// type. 'Array' represents the lvalue of the array being decayed
232 /// to a pointer, and the returned SVal represents the decayed
233 /// version of that lvalue (i.e., a pointer to the first element of
234 /// the array). This is called by GRExprEngine when evaluating
235 /// casts from arrays to pointers.
236 SVal ArrayToPointer(Loc Array);
238 CastResult CastRegion(const GRState *state, const MemRegion* R,
241 SVal EvalBinOp(const GRState *state, BinaryOperator::Opcode Op,Loc L,NonLoc R);
246 Store getInitialStore() { return RBFactory.GetEmptyMap().getRoot(); }
248 /// getSelfRegion - Returns the region for the 'self' (Objective-C) or
249 /// 'this' object (C++). When used when analyzing a normal function this
250 /// method returns NULL.
251 const MemRegion* getSelfRegion(Store) {
256 const ObjCMethodDecl *MD = cast<ObjCMethodDecl>(&StateMgr.getCodeDecl());
257 SelfRegion = MRMgr.getObjCObjectRegion(MD->getClassInterface(),
258 MRMgr.getHeapRegion());
266 //===-------------------------------------------------------------------===//
267 // Binding values to regions.
268 //===-------------------------------------------------------------------===//
270 const GRState *Bind(const GRState *state, Loc LV, SVal V);
272 const GRState *BindCompoundLiteral(const GRState *state,
273 const CompoundLiteralExpr* CL, SVal V);
275 const GRState *BindDecl(const GRState *state, const VarDecl* VD, SVal InitVal);
277 const GRState *BindDeclWithNoInit(const GRState *state, const VarDecl* VD) {
281 /// BindStruct - Bind a compound value to a structure.
282 const GRState *BindStruct(const GRState *, const TypedRegion* R, SVal V);
284 const GRState *BindArray(const GRState *state, const TypedRegion* R, SVal V);
286 /// KillStruct - Set the entire struct to unknown.
287 const GRState *KillStruct(const GRState *state, const TypedRegion* R);
289 const GRState *setDefaultValue(const GRState *state, const MemRegion* R, SVal V);
291 Store Remove(Store store, Loc LV);
293 //===------------------------------------------------------------------===//
294 // Loading values from regions.
295 //===------------------------------------------------------------------===//
297 /// The high level logic for this method is this:
300 /// return L's binding
301 /// else if L is in killset
304 /// if L is on stack or heap
308 SVal Retrieve(const GRState *state, Loc L, QualType T = QualType());
310 /// Retrieve the values in a struct and return a CompoundVal, used when doing
314 /// y's value is retrieved by this method.
315 SVal RetrieveStruct(const GRState *St, const TypedRegion* R);
317 SVal RetrieveArray(const GRState *St, const TypedRegion* R);
319 //===------------------------------------------------------------------===//
321 //===------------------------------------------------------------------===//
323 /// RemoveDeadBindings - Scans the RegionStore of 'state' for dead values.
324 /// It returns a new Store with these values removed.
325 Store RemoveDeadBindings(const GRState *state, Stmt* Loc, SymbolReaper& SymReaper,
326 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots);
328 //===------------------------------------------------------------------===//
330 //===------------------------------------------------------------------===//
332 const GRState *setExtent(const GRState *state, const MemRegion* R, SVal Extent);
333 SVal getSizeInElements(const GRState *state, const MemRegion* R);
335 //===------------------------------------------------------------------===//
337 //===------------------------------------------------------------------===//
339 const GRState *AddRegionView(const GRState *state, const MemRegion* View,
340 const MemRegion* Base);
342 const GRState *RemoveRegionView(const GRState *state, const MemRegion* View,
343 const MemRegion* Base);
345 //===------------------------------------------------------------------===//
347 //===------------------------------------------------------------------===//
349 const GRState *setCastType(const GRState *state, const MemRegion* R, QualType T);
351 static inline RegionBindingsTy GetRegionBindings(Store store) {
352 return RegionBindingsTy(static_cast<const RegionBindingsTy::TreeTy*>(store));
355 void print(Store store, std::ostream& Out, const char* nl, const char *sep);
357 void iterBindings(Store store, BindingsHandler& f) {
362 BasicValueFactory& getBasicVals() {
363 return StateMgr.getBasicVals();
367 ASTContext& getContext() { return StateMgr.getContext(); }
369 // FIXME: Use ValueManager?
370 SymbolManager& getSymbolManager() { return StateMgr.getSymbolManager(); }
373 } // end anonymous namespace
375 //===----------------------------------------------------------------------===//
376 // RegionStore creation.
377 //===----------------------------------------------------------------------===//
379 StoreManager *clang::CreateRegionStoreManager(GRStateManager& StMgr) {
380 RegionStoreFeatures F = maximal_features_tag();
381 return new RegionStoreManager(StMgr, F);
384 StoreManager *clang::CreateFieldsOnlyRegionStoreManager(GRStateManager &StMgr) {
385 RegionStoreFeatures F = minimal_features_tag();
386 F.enableFields(true);
387 return new RegionStoreManager(StMgr, F);
390 SubRegionMap* RegionStoreManager::getSubRegionMap(const GRState *state) {
391 RegionBindingsTy B = GetRegionBindings(state->getStore());
392 RegionStoreSubRegionMap *M = new RegionStoreSubRegionMap();
394 for (RegionBindingsTy::iterator I=B.begin(), E=B.end(); I!=E; ++I) {
395 if (const SubRegion* R = dyn_cast<SubRegion>(I.getKey()))
396 M->add(R->getSuperRegion(), R);
402 //===----------------------------------------------------------------------===//
403 // getLValueXXX methods.
404 //===----------------------------------------------------------------------===//
406 /// getLValueString - Returns an SVal representing the lvalue of a
407 /// StringLiteral. Within RegionStore a StringLiteral has an
408 /// associated StringRegion, and the lvalue of a StringLiteral is the
409 /// lvalue of that region.
410 SVal RegionStoreManager::getLValueString(const GRState *St,
411 const StringLiteral* S) {
412 return loc::MemRegionVal(MRMgr.getStringRegion(S));
415 /// getLValueVar - Returns an SVal that represents the lvalue of a
416 /// variable. Within RegionStore a variable has an associated
417 /// VarRegion, and the lvalue of the variable is the lvalue of that region.
418 SVal RegionStoreManager::getLValueVar(const GRState *St, const VarDecl* VD) {
419 return loc::MemRegionVal(MRMgr.getVarRegion(VD));
422 /// getLValueCompoundLiteral - Returns an SVal representing the lvalue
423 /// of a compound literal. Within RegionStore a compound literal
424 /// has an associated region, and the lvalue of the compound literal
425 /// is the lvalue of that region.
427 RegionStoreManager::getLValueCompoundLiteral(const GRState *St,
428 const CompoundLiteralExpr* CL) {
429 return loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL));
432 SVal RegionStoreManager::getLValueIvar(const GRState *St, const ObjCIvarDecl* D,
434 return getLValueFieldOrIvar(St, Base, D);
437 SVal RegionStoreManager::getLValueField(const GRState *St, SVal Base,
438 const FieldDecl* D) {
439 return getLValueFieldOrIvar(St, Base, D);
442 SVal RegionStoreManager::getLValueFieldOrIvar(const GRState *St, SVal Base,
444 if (Base.isUnknownOrUndef())
447 Loc BaseL = cast<Loc>(Base);
448 const MemRegion* BaseR = 0;
450 switch (BaseL.getSubKind()) {
451 case loc::MemRegionKind:
452 BaseR = cast<loc::MemRegionVal>(BaseL).getRegion();
455 case loc::GotoLabelKind:
456 // These are anormal cases. Flag an undefined value.
457 return UndefinedVal();
459 case loc::ConcreteIntKind:
460 // While these seem funny, this can happen through casts.
461 // FIXME: What we should return is the field offset. For example,
462 // add the field offset to the integer value. That way funny things
463 // like this work properly: &(((struct foo *) 0xa)->f)
467 assert(0 && "Unhandled Base.");
471 // NOTE: We must have this check first because ObjCIvarDecl is a subclass
473 if (const ObjCIvarDecl *ID = dyn_cast<ObjCIvarDecl>(D))
474 return loc::MemRegionVal(MRMgr.getObjCIvarRegion(ID, BaseR));
476 return loc::MemRegionVal(MRMgr.getFieldRegion(cast<FieldDecl>(D), BaseR));
479 SVal RegionStoreManager::getLValueElement(const GRState *St,
480 QualType elementType,
481 SVal Base, SVal Offset) {
483 // If the base is an unknown or undefined value, just return it back.
484 // FIXME: For absolute pointer addresses, we just return that value back as
485 // well, although in reality we should return the offset added to that
487 if (Base.isUnknownOrUndef() || isa<loc::ConcreteInt>(Base))
490 // Only handle integer offsets... for now.
491 if (!isa<nonloc::ConcreteInt>(Offset))
494 const MemRegion* BaseRegion = cast<loc::MemRegionVal>(Base).getRegion();
496 // Pointer of any type can be cast and used as array base.
497 const ElementRegion *ElemR = dyn_cast<ElementRegion>(BaseRegion);
501 // If the base region is not an ElementRegion, create one.
502 // This can happen in the following example:
504 // char *p = __builtin_alloc(10);
507 // Observe that 'p' binds to an AllocaRegion.
510 // Offset might be unsigned. We have to convert it to signed ConcreteInt.
511 if (nonloc::ConcreteInt* CI = dyn_cast<nonloc::ConcreteInt>(&Offset)) {
512 const llvm::APSInt& OffI = CI->getValue();
513 if (OffI.isUnsigned()) {
514 llvm::APSInt Tmp = OffI;
515 Tmp.setIsSigned(true);
516 Offset = ValMgr.makeIntVal(Tmp);
519 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, Offset,
520 BaseRegion, getContext()));
523 SVal BaseIdx = ElemR->getIndex();
525 if (!isa<nonloc::ConcreteInt>(BaseIdx))
528 const llvm::APSInt& BaseIdxI = cast<nonloc::ConcreteInt>(BaseIdx).getValue();
529 const llvm::APSInt& OffI = cast<nonloc::ConcreteInt>(Offset).getValue();
530 assert(BaseIdxI.isSigned());
532 // FIXME: This appears to be the assumption of this code. We should review
533 // whether or not BaseIdxI.getBitWidth() < OffI.getBitWidth(). If it
534 // can't we need to put a comment here. If it can, we should handle it.
535 assert(BaseIdxI.getBitWidth() >= OffI.getBitWidth());
537 const MemRegion *ArrayR = ElemR->getSuperRegion();
540 if (OffI.isUnsigned() || OffI.getBitWidth() < BaseIdxI.getBitWidth()) {
541 // 'Offset' might be unsigned. We have to convert it to signed and
542 // possibly extend it.
543 llvm::APSInt Tmp = OffI;
545 if (OffI.getBitWidth() < BaseIdxI.getBitWidth())
546 Tmp.extend(BaseIdxI.getBitWidth());
548 Tmp.setIsSigned(true);
549 Tmp += BaseIdxI; // Compute the new offset.
550 NewIdx = ValMgr.makeIntVal(Tmp);
553 NewIdx = nonloc::ConcreteInt(getBasicVals().getValue(BaseIdxI + OffI));
555 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, NewIdx, ArrayR,
559 //===----------------------------------------------------------------------===//
560 // Extents for regions.
561 //===----------------------------------------------------------------------===//
563 SVal RegionStoreManager::getSizeInElements(const GRState *state,
564 const MemRegion* R) {
565 if (const VarRegion* VR = dyn_cast<VarRegion>(R)) {
566 // Get the type of the variable.
567 QualType T = VR->getDesugaredValueType(getContext());
569 // FIXME: Handle variable-length arrays.
570 if (isa<VariableArrayType>(T))
573 if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(T)) {
574 // return the size as signed integer.
575 return ValMgr.makeIntVal(CAT->getSize(), false);
578 const QualType* CastTy = state->get<RegionCasts>(VR);
580 // If the VarRegion is cast to other type, compute the size with respect to
583 QualType EleTy =cast<PointerType>(CastTy->getTypePtr())->getPointeeType();
584 QualType VarTy = VR->getValueType(getContext());
585 uint64_t EleSize = getContext().getTypeSize(EleTy);
586 uint64_t VarSize = getContext().getTypeSize(VarTy);
587 assert(VarSize != 0);
588 return ValMgr.makeIntVal(VarSize/EleSize, false);
591 // Clients can use ordinary variables as if they were arrays. These
592 // essentially are arrays of size 1.
593 return ValMgr.makeIntVal(1, false);
596 if (const StringRegion* SR = dyn_cast<StringRegion>(R)) {
597 const StringLiteral* Str = SR->getStringLiteral();
598 // We intentionally made the size value signed because it participates in
599 // operations with signed indices.
600 return ValMgr.makeIntVal(Str->getByteLength()+1, false);
603 if (const FieldRegion* FR = dyn_cast<FieldRegion>(R)) {
604 // FIXME: Unsupported yet.
609 if (isa<SymbolicRegion>(R)) {
613 if (isa<AllocaRegion>(R)) {
617 if (isa<ElementRegion>(R)) {
621 assert(0 && "Other regions are not supported yet.");
625 const GRState *RegionStoreManager::setExtent(const GRState *state,
626 const MemRegion *region,
628 return state->set<RegionExtents>(region, extent);
631 //===----------------------------------------------------------------------===//
632 // Location and region casting.
633 //===----------------------------------------------------------------------===//
635 /// ArrayToPointer - Emulates the "decay" of an array to a pointer
636 /// type. 'Array' represents the lvalue of the array being decayed
637 /// to a pointer, and the returned SVal represents the decayed
638 /// version of that lvalue (i.e., a pointer to the first element of
639 /// the array). This is called by GRExprEngine when evaluating casts
640 /// from arrays to pointers.
641 SVal RegionStoreManager::ArrayToPointer(Loc Array) {
642 if (!isa<loc::MemRegionVal>(Array))
645 const MemRegion* R = cast<loc::MemRegionVal>(&Array)->getRegion();
646 const TypedRegion* ArrayR = dyn_cast<TypedRegion>(R);
651 // Strip off typedefs from the ArrayRegion's ValueType.
652 QualType T = ArrayR->getValueType(getContext())->getDesugaredType();
653 ArrayType *AT = cast<ArrayType>(T);
654 T = AT->getElementType();
656 nonloc::ConcreteInt Idx(getBasicVals().getZeroWithPtrWidth(false));
657 ElementRegion* ER = MRMgr.getElementRegion(T, Idx, ArrayR, getContext());
659 return loc::MemRegionVal(ER);
662 RegionStoreManager::CastResult
663 RegionStoreManager::CastRegion(const GRState *state, const MemRegion* R,
666 ASTContext& Ctx = StateMgr.getContext();
668 // We need to know the real type of CastToTy.
669 QualType ToTy = Ctx.getCanonicalType(CastToTy);
671 // Check cast to ObjCQualifiedID type.
672 if (ToTy->isObjCQualifiedIdType()) {
673 // FIXME: Record the type information aside.
674 return CastResult(state, R);
677 // CodeTextRegion should be cast to only function pointer type.
678 if (isa<CodeTextRegion>(R)) {
679 assert(CastToTy->isFunctionPointerType() || CastToTy->isBlockPointerType()
680 || (CastToTy->isPointerType()
681 && CastToTy->getAsPointerType()->getPointeeType()->isVoidType()));
682 return CastResult(state, R);
685 // Now assume we are casting from pointer to pointer. Other cases should
686 // already be handled.
687 QualType PointeeTy = cast<PointerType>(ToTy.getTypePtr())->getPointeeType();
689 // Process region cast according to the kind of the region being cast.
691 // FIXME: Need to handle arbitrary downcasts.
692 if (isa<SymbolicRegion>(R) || isa<AllocaRegion>(R)) {
693 state = setCastType(state, R, ToTy);
694 return CastResult(state, R);
697 // VarRegion, ElementRegion, and FieldRegion has an inherent type. Normally
698 // they should not be cast. We only layer an ElementRegion when the cast-to
699 // pointee type is of smaller size. In other cases, we return the original
701 if (isa<VarRegion>(R) || isa<ElementRegion>(R) || isa<FieldRegion>(R)
702 || isa<ObjCIvarRegion>(R) || isa<CompoundLiteralRegion>(R)) {
703 // If the pointee type is incomplete, do not compute its size, and return
704 // the original region.
705 if (const RecordType *RT = dyn_cast<RecordType>(PointeeTy.getTypePtr())) {
706 const RecordDecl *D = RT->getDecl();
707 if (!D->getDefinition(getContext()))
708 return CastResult(state, R);
711 QualType ObjTy = cast<TypedRegion>(R)->getValueType(getContext());
712 uint64_t PointeeTySize = getContext().getTypeSize(PointeeTy);
713 uint64_t ObjTySize = getContext().getTypeSize(ObjTy);
715 if ((PointeeTySize > 0 && PointeeTySize < ObjTySize) ||
716 (ObjTy->isAggregateType() && PointeeTy->isScalarType()) ||
717 ObjTySize == 0 /* R has 'void*' type. */) {
718 // Record the cast type of the region.
719 state = setCastType(state, R, ToTy);
721 SVal Idx = ValMgr.makeZeroArrayIndex();
722 ElementRegion* ER = MRMgr.getElementRegion(PointeeTy, Idx,R,getContext());
723 return CastResult(state, ER);
725 state = setCastType(state, R, ToTy);
726 return CastResult(state, R);
730 if (isa<ObjCObjectRegion>(R)) {
731 return CastResult(state, R);
734 assert(0 && "Unprocessed region.");
738 //===----------------------------------------------------------------------===//
739 // Pointer arithmetic.
740 //===----------------------------------------------------------------------===//
742 SVal RegionStoreManager::EvalBinOp(const GRState *state,
743 BinaryOperator::Opcode Op, Loc L, NonLoc R) {
744 // Assume the base location is MemRegionVal.
745 if (!isa<loc::MemRegionVal>(L))
748 const MemRegion* MR = cast<loc::MemRegionVal>(L).getRegion();
749 const ElementRegion *ER = 0;
751 // If the operand is a symbolic or alloca region, create the first element
753 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR)) {
755 // If the SymbolicRegion was cast to another type, use that type.
756 if (const QualType *t = state->get<RegionCasts>(SR)) {
759 // Otherwise use the symbol's type.
760 SymbolRef Sym = SR->getSymbol();
761 T = Sym->getType(getContext());
763 QualType EleTy = T->getAsPointerType()->getPointeeType();
765 SVal ZeroIdx = ValMgr.makeZeroArrayIndex();
766 ER = MRMgr.getElementRegion(EleTy, ZeroIdx, SR, getContext());
768 else if (const AllocaRegion *AR = dyn_cast<AllocaRegion>(MR)) {
769 // Get the alloca region's current cast type.
772 GRStateTrait<RegionCasts>::lookup_type T = state->get<RegionCasts>(AR);
773 assert(T && "alloca region has no type.");
774 QualType EleTy = cast<PointerType>(T->getTypePtr())->getPointeeType();
775 SVal ZeroIdx = ValMgr.makeZeroArrayIndex();
776 ER = MRMgr.getElementRegion(EleTy, ZeroIdx, AR, getContext());
778 else if (isa<FieldRegion>(MR)) {
779 // Not track pointer arithmetic on struct fields.
783 ER = cast<ElementRegion>(MR);
786 SVal Idx = ER->getIndex();
788 nonloc::ConcreteInt* Base = dyn_cast<nonloc::ConcreteInt>(&Idx);
789 nonloc::ConcreteInt* Offset = dyn_cast<nonloc::ConcreteInt>(&R);
791 // Only support concrete integer indexes for now.
792 if (Base && Offset) {
793 // FIXME: For now, convert the signedness and bitwidth of offset in case
794 // they don't match. This can result from pointer arithmetic. In reality,
795 // we should figure out what are the proper semantics and implement them.
797 // This addresses the test case test/Analysis/ptr-arith.c
799 nonloc::ConcreteInt OffConverted(getBasicVals().Convert(Base->getValue(),
800 Offset->getValue()));
801 SVal NewIdx = Base->EvalBinOp(getBasicVals(), Op, OffConverted);
802 const MemRegion* NewER =
803 MRMgr.getElementRegion(ER->getElementType(), NewIdx,ER->getSuperRegion(),
805 return ValMgr.makeLoc(NewER);
812 //===----------------------------------------------------------------------===//
813 // Loading values from regions.
814 //===----------------------------------------------------------------------===//
816 SVal RegionStoreManager::Retrieve(const GRState *state, Loc L, QualType T) {
818 assert(!isa<UnknownVal>(L) && "location unknown");
819 assert(!isa<UndefinedVal>(L) && "location undefined");
821 // FIXME: Is this even possible? Shouldn't this be treated as a null
822 // dereference at a higher level?
823 if (isa<loc::ConcreteInt>(L))
824 return UndefinedVal();
826 const MemRegion *MR = cast<loc::MemRegionVal>(L).getRegion();
828 // FIXME: return symbolic value for these cases.
830 // void f(int* p) { int x = *p; }
831 // char* p = alloca();
834 if (isa<SymbolicRegion>(MR) || isa<AllocaRegion>(MR))
837 // FIXME: Perhaps this method should just take a 'const MemRegion*' argument
838 // instead of 'Loc', and have the other Loc cases handled at a higher level.
839 const TypedRegion *R = cast<TypedRegion>(MR);
840 assert(R && "bad region");
842 // FIXME: We should eventually handle funny addressing. e.g.:
846 // char *q = (char*) p;
847 // char c = *q; // returns the first byte of 'x'.
849 // Such funny addressing will occur due to layering of regions.
851 QualType RTy = R->getValueType(getContext());
853 if (RTy->isStructureType())
854 return RetrieveStruct(state, R);
856 if (RTy->isArrayType())
857 return RetrieveArray(state, R);
859 // FIXME: handle Vector types.
860 if (RTy->isVectorType())
863 RegionBindingsTy B = GetRegionBindings(state->getStore());
864 RegionBindingsTy::data_type* V = B.lookup(R);
866 // Check if the region has a binding.
870 // Check if the region is in killset.
871 if (state->contains<RegionKills>(R))
874 // Check if the region is an element region of a string literal.
875 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
876 if (const StringRegion *StrR=dyn_cast<StringRegion>(ER->getSuperRegion())) {
877 const StringLiteral *Str = StrR->getStringLiteral();
878 SVal Idx = ER->getIndex();
879 if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&Idx)) {
880 int64_t i = CI->getValue().getSExtValue();
882 if (i == Str->getByteLength())
885 c = Str->getStrData()[i];
886 const llvm::APSInt &V = getBasicVals().getValue(c, getContext().CharTy);
887 return nonloc::ConcreteInt(V);
892 // If the region is an element or field, it may have a default value.
893 if (isa<ElementRegion>(R) || isa<FieldRegion>(R)) {
894 const MemRegion* SuperR = cast<SubRegion>(R)->getSuperRegion();
895 GRStateTrait<RegionDefaultValue>::lookup_type D =
896 state->get<RegionDefaultValue>(SuperR);
898 // If the default value is symbolic, we need to create a new symbol.
899 if (D->hasConjuredSymbol())
900 return ValMgr.getRegionValueSymbolVal(R);
906 if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) {
907 const MemRegion *SR = IVR->getSuperRegion();
909 // If the super region is 'self' then return the symbol representing
910 // the value of the ivar upon entry to the method.
911 if (SR == SelfRegion) {
912 // FIXME: Do we need to handle the case where the super region
913 // has a view? We want to canonicalize the bindings.
914 return ValMgr.getRegionValueSymbolVal(R);
917 // Otherwise, we need a new symbol. For now return Unknown.
921 // The location does not have a bound value. This means that it has
922 // the value it had upon its creation and/or entry to the analyzed
923 // function/method. These are either symbolic values or 'undefined'.
925 // We treat function parameters as symbolic values.
926 if (const VarRegion* VR = dyn_cast<VarRegion>(R)) {
927 const VarDecl *VD = VR->getDecl();
930 return loc::MemRegionVal(getSelfRegion(0));
932 if (isa<ParmVarDecl>(VD) || isa<ImplicitParamDecl>(VD) ||
933 VD->hasGlobalStorage()) {
934 QualType VTy = VD->getType();
935 if (Loc::IsLocType(VTy) || VTy->isIntegerType())
936 return ValMgr.getRegionValueSymbolVal(VR);
942 if (R->hasHeapOrStackStorage()) {
943 // All stack variables are considered to have undefined values
944 // upon creation. All heap allocated blocks are considered to
945 // have undefined values as well unless they are explicitly bound
946 // to specific values.
947 return UndefinedVal();
950 // If the region is already cast to another type, use that type to create the
952 if (const QualType *p = state->get<RegionCasts>(R)) {
954 RTy = T->getAsPointerType()->getPointeeType();
957 // All other integer values are symbolic.
958 if (Loc::IsLocType(RTy) || RTy->isIntegerType())
959 return ValMgr.getRegionValueSymbolVal(R, RTy);
964 SVal RegionStoreManager::RetrieveStruct(const GRState *state,
965 const TypedRegion* R){
966 QualType T = R->getValueType(getContext());
967 assert(T->isStructureType());
969 const RecordType* RT = T->getAsStructureType();
970 RecordDecl* RD = RT->getDecl();
971 assert(RD->isDefinition());
973 llvm::ImmutableList<SVal> StructVal = getBasicVals().getEmptySValList();
975 // FIXME: We shouldn't use a std::vector. If RecordDecl doesn't have a
976 // reverse iterator, we should implement one.
977 std::vector<FieldDecl *> Fields(RD->field_begin(getContext()),
978 RD->field_end(getContext()));
980 for (std::vector<FieldDecl *>::reverse_iterator Field = Fields.rbegin(),
981 FieldEnd = Fields.rend();
982 Field != FieldEnd; ++Field) {
983 FieldRegion* FR = MRMgr.getFieldRegion(*Field, R);
984 QualType FTy = (*Field)->getType();
985 SVal FieldValue = Retrieve(state, loc::MemRegionVal(FR), FTy);
986 StructVal = getBasicVals().consVals(FieldValue, StructVal);
989 return ValMgr.makeCompoundVal(T, StructVal);
992 SVal RegionStoreManager::RetrieveArray(const GRState *state,
993 const TypedRegion * R) {
995 QualType T = R->getValueType(getContext());
996 ConstantArrayType* CAT = cast<ConstantArrayType>(T.getTypePtr());
998 llvm::ImmutableList<SVal> ArrayVal = getBasicVals().getEmptySValList();
999 llvm::APSInt Size(CAT->getSize(), false);
1000 llvm::APSInt i = getBasicVals().getZeroWithPtrWidth(false);
1002 for (; i < Size; ++i) {
1003 SVal Idx = ValMgr.makeIntVal(i);
1004 ElementRegion* ER = MRMgr.getElementRegion(CAT->getElementType(), Idx, R,
1006 QualType ETy = ER->getElementType();
1007 SVal ElementVal = Retrieve(state, loc::MemRegionVal(ER), ETy);
1008 ArrayVal = getBasicVals().consVals(ElementVal, ArrayVal);
1011 return ValMgr.makeCompoundVal(T, ArrayVal);
1014 //===----------------------------------------------------------------------===//
1015 // Binding values to regions.
1016 //===----------------------------------------------------------------------===//
1018 Store RegionStoreManager::Remove(Store store, Loc L) {
1019 const MemRegion* R = 0;
1021 if (isa<loc::MemRegionVal>(L))
1022 R = cast<loc::MemRegionVal>(L).getRegion();
1025 RegionBindingsTy B = GetRegionBindings(store);
1026 return RBFactory.Remove(B, R).getRoot();
1032 const GRState *RegionStoreManager::Bind(const GRState *state, Loc L, SVal V) {
1033 // If we get here, the location should be a region.
1034 const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion();
1036 // Check if the region is a struct region.
1037 if (const TypedRegion* TR = dyn_cast<TypedRegion>(R))
1038 if (TR->getValueType(getContext())->isStructureType())
1039 return BindStruct(state, TR, V);
1041 RegionBindingsTy B = GetRegionBindings(state->getStore());
1043 if (V.isUnknown()) {
1044 B = RBFactory.Remove(B, R); // Remove the binding.
1045 state = state->add<RegionKills>(R); // Add the region to the killset.
1048 B = RBFactory.Add(B, R, V);
1050 return state->makeWithStore(B.getRoot());
1053 const GRState *RegionStoreManager::BindDecl(const GRState *state,
1054 const VarDecl* VD, SVal InitVal) {
1056 QualType T = VD->getType();
1057 VarRegion* VR = MRMgr.getVarRegion(VD);
1059 if (T->isArrayType())
1060 return BindArray(state, VR, InitVal);
1061 if (T->isStructureType())
1062 return BindStruct(state, VR, InitVal);
1064 return Bind(state, ValMgr.makeLoc(VR), InitVal);
1067 // FIXME: this method should be merged into Bind().
1069 RegionStoreManager::BindCompoundLiteral(const GRState *state,
1070 const CompoundLiteralExpr* CL,
1073 CompoundLiteralRegion* R = MRMgr.getCompoundLiteralRegion(CL);
1074 return Bind(state, loc::MemRegionVal(R), V);
1077 const GRState *RegionStoreManager::BindArray(const GRState *state,
1078 const TypedRegion* R,
1081 QualType T = R->getValueType(getContext());
1082 ConstantArrayType* CAT = cast<ConstantArrayType>(T.getTypePtr());
1083 QualType ElementTy = CAT->getElementType();
1085 llvm::APSInt Size(CAT->getSize(), false);
1086 llvm::APSInt i(llvm::APInt::getNullValue(Size.getBitWidth()), false);
1088 // Check if the init expr is a StringLiteral.
1089 if (isa<loc::MemRegionVal>(Init)) {
1090 const MemRegion* InitR = cast<loc::MemRegionVal>(Init).getRegion();
1091 const StringLiteral* S = cast<StringRegion>(InitR)->getStringLiteral();
1092 const char* str = S->getStrData();
1093 unsigned len = S->getByteLength();
1096 // Copy bytes from the string literal into the target array. Trailing bytes
1097 // in the array that are not covered by the string literal are initialized
1099 for (; i < Size; ++i, ++j) {
1103 SVal Idx = ValMgr.makeIntVal(i);
1104 ElementRegion* ER = MRMgr.getElementRegion(ElementTy, Idx,R,getContext());
1106 SVal V = ValMgr.makeIntVal(str[j], sizeof(char)*8, true);
1107 state = Bind(state, loc::MemRegionVal(ER), V);
1113 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(Init);
1114 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
1116 for (; i < Size; ++i, ++VI) {
1117 // The init list might be shorter than the array length.
1121 SVal Idx = ValMgr.makeIntVal(i);
1122 ElementRegion* ER = MRMgr.getElementRegion(ElementTy, Idx, R, getContext());
1124 if (CAT->getElementType()->isStructureType())
1125 state = BindStruct(state, ER, *VI);
1127 state = Bind(state, ValMgr.makeLoc(ER), *VI);
1130 // If the init list is shorter than the array length, bind the rest elements
1132 if (ElementTy->isIntegerType()) {
1134 SVal Idx = ValMgr.makeIntVal(i);
1135 ElementRegion* ER = MRMgr.getElementRegion(ElementTy, Idx,R,getContext());
1136 SVal V = ValMgr.makeZeroVal(ElementTy);
1137 state = Bind(state, ValMgr.makeLoc(ER), V);
1146 RegionStoreManager::BindStruct(const GRState *state, const TypedRegion* R,
1149 if (!Features.supportsFields())
1152 QualType T = R->getValueType(getContext());
1153 assert(T->isStructureType());
1155 const RecordType* RT = T->getAsRecordType();
1156 RecordDecl* RD = RT->getDecl();
1158 if (!RD->isDefinition())
1161 // We may get non-CompoundVal accidentally due to imprecise cast logic.
1162 // Ignore them and kill the field values.
1163 if (V.isUnknown() || !isa<nonloc::CompoundVal>(V))
1164 return KillStruct(state, R);
1166 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V);
1167 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
1169 RecordDecl::field_iterator FI, FE;
1171 for (FI = RD->field_begin(getContext()), FE = RD->field_end(getContext());
1172 FI != FE; ++FI, ++VI) {
1177 QualType FTy = (*FI)->getType();
1178 FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);
1180 if (Loc::IsLocType(FTy) || FTy->isIntegerType())
1181 state = Bind(state, ValMgr.makeLoc(FR), *VI);
1182 else if (FTy->isArrayType())
1183 state = BindArray(state, FR, *VI);
1184 else if (FTy->isStructureType())
1185 state = BindStruct(state, FR, *VI);
1188 // There may be fewer values in the initialize list than the fields of struct.
1190 QualType FTy = (*FI)->getType();
1191 if (FTy->isIntegerType()) {
1192 FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);
1193 state = Bind(state, ValMgr.makeLoc(FR), ValMgr.makeZeroVal(FTy));
1202 const GRState *RegionStoreManager::KillStruct(const GRState *state,
1203 const TypedRegion* R){
1205 // (1) Kill the struct region because it is assigned "unknown".
1206 // (2) Set the default value of the struct region to "unknown".
1207 state = state->add<RegionKills>(R)->set<RegionDefaultValue>(R, UnknownVal());
1208 Store store = state->getStore();
1209 RegionBindingsTy B = GetRegionBindings(store);
1211 // Remove all bindings for the subregions of the struct.
1212 for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
1213 const MemRegion* R = I.getKey();
1214 if (const SubRegion* subRegion = dyn_cast<SubRegion>(R))
1215 if (subRegion->isSubRegionOf(R))
1216 store = Remove(store, ValMgr.makeLoc(subRegion));
1217 // FIXME: Maybe we should also remove the bindings for the "views" of the
1221 return state->makeWithStore(store);
1224 //===----------------------------------------------------------------------===//
1226 //===----------------------------------------------------------------------===//
1228 const GRState *RegionStoreManager::AddRegionView(const GRState *state,
1229 const MemRegion* View,
1230 const MemRegion* Base) {
1232 // First, retrieve the region view of the base region.
1233 const RegionViews* d = state->get<RegionViewMap>(Base);
1234 RegionViews L = d ? *d : RVFactory.GetEmptySet();
1236 // Now add View to the region view.
1237 L = RVFactory.Add(L, View);
1239 // Create a new state with the new region view.
1240 return state->set<RegionViewMap>(Base, L);
1243 const GRState *RegionStoreManager::RemoveRegionView(const GRState *state,
1244 const MemRegion* View,
1245 const MemRegion* Base) {
1246 // Retrieve the region view of the base region.
1247 const RegionViews* d = state->get<RegionViewMap>(Base);
1249 // If the base region has no view, return.
1254 return state->set<RegionViewMap>(Base, RVFactory.Remove(*d, View));
1257 const GRState *RegionStoreManager::setCastType(const GRState *state,
1258 const MemRegion* R, QualType T) {
1259 return state->set<RegionCasts>(R, T);
1262 const GRState *RegionStoreManager::setDefaultValue(const GRState *state,
1263 const MemRegion* R, SVal V) {
1264 return state->set<RegionDefaultValue>(R, V);
1267 //===----------------------------------------------------------------------===//
1269 //===----------------------------------------------------------------------===//
1271 static void UpdateLiveSymbols(SVal X, SymbolReaper& SymReaper) {
1272 if (loc::MemRegionVal *XR = dyn_cast<loc::MemRegionVal>(&X)) {
1273 const MemRegion *R = XR->getRegion();
1276 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) {
1277 SymReaper.markLive(SR->getSymbol());
1281 if (const SubRegion *SR = dyn_cast<SubRegion>(R)) {
1282 R = SR->getSuperRegion();
1292 for (SVal::symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end();SI!=SE;++SI)
1293 SymReaper.markLive(*SI);
1296 Store RegionStoreManager::RemoveDeadBindings(const GRState *state, Stmt* Loc,
1297 SymbolReaper& SymReaper,
1298 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots)
1300 Store store = state->getStore();
1301 RegionBindingsTy B = GetRegionBindings(store);
1303 // Lazily constructed backmap from MemRegions to SubRegions.
1304 typedef llvm::ImmutableSet<const MemRegion*> SubRegionsTy;
1305 typedef llvm::ImmutableMap<const MemRegion*, SubRegionsTy> SubRegionsMapTy;
1307 // FIXME: As a future optimization we can modifiy BumpPtrAllocator to have
1308 // the ability to reuse memory. This way we can keep TmpAlloc around as
1309 // an instance variable of RegionStoreManager (avoiding repeated malloc
1311 llvm::BumpPtrAllocator TmpAlloc;
1314 SubRegionsMapTy::Factory SubRegMapF(TmpAlloc);
1315 SubRegionsTy::Factory SubRegF(TmpAlloc);
1317 // The backmap from regions to subregions.
1318 SubRegionsMapTy SubRegMap = SubRegMapF.GetEmptyMap();
1320 // Do a pass over the regions in the store. For VarRegions we check if
1321 // the variable is still live and if so add it to the list of live roots.
1322 // For other regions we populate our region backmap.
1323 llvm::SmallVector<const MemRegion*, 10> IntermediateRoots;
1325 for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
1326 IntermediateRoots.push_back(I.getKey());
1329 while (!IntermediateRoots.empty()) {
1330 const MemRegion* R = IntermediateRoots.back();
1331 IntermediateRoots.pop_back();
1333 if (const VarRegion* VR = dyn_cast<VarRegion>(R)) {
1334 if (SymReaper.isLive(Loc, VR->getDecl()))
1335 RegionRoots.push_back(VR); // This is a live "root".
1337 else if (const SymbolicRegion* SR = dyn_cast<SymbolicRegion>(R)) {
1338 if (SymReaper.isLive(SR->getSymbol()))
1339 RegionRoots.push_back(SR);
1342 // Get the super region for R.
1343 const MemRegion* SuperR = cast<SubRegion>(R)->getSuperRegion();
1345 // Get the current set of subregions for SuperR.
1346 const SubRegionsTy* SRptr = SubRegMap.lookup(SuperR);
1347 SubRegionsTy SRs = SRptr ? *SRptr : SubRegF.GetEmptySet();
1349 // Add R to the subregions of SuperR.
1350 SubRegMap = SubRegMapF.Add(SubRegMap, SuperR, SubRegF.Add(SRs, R));
1352 // Super region may be VarRegion or subregion of another VarRegion. Add it
1353 // to the work list.
1354 if (isa<SubRegion>(SuperR))
1355 IntermediateRoots.push_back(SuperR);
1359 // Process the worklist of RegionRoots. This performs a "mark-and-sweep"
1360 // of the store. We want to find all live symbols and dead regions.
1361 llvm::SmallPtrSet<const MemRegion*, 10> Marked;
1363 while (!RegionRoots.empty()) {
1364 // Dequeue the next region on the worklist.
1365 const MemRegion* R = RegionRoots.back();
1366 RegionRoots.pop_back();
1368 // Check if we have already processed this region.
1369 if (Marked.count(R)) continue;
1371 // Mark this region as processed. This is needed for termination in case
1372 // a region is referenced more than once.
1375 // Mark the symbol for any live SymbolicRegion as "live". This means we
1376 // should continue to track that symbol.
1377 if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(R))
1378 SymReaper.markLive(SymR->getSymbol());
1380 // Get the data binding for R (if any).
1381 RegionBindingsTy::data_type* Xptr = B.lookup(R);
1384 UpdateLiveSymbols(X, SymReaper); // Update the set of live symbols.
1386 // If X is a region, then add it the RegionRoots.
1387 if (loc::MemRegionVal* RegionX = dyn_cast<loc::MemRegionVal>(&X))
1388 RegionRoots.push_back(RegionX->getRegion());
1391 // Get the subregions of R. These are RegionRoots as well since they
1392 // represent values that are also bound to R.
1393 const SubRegionsTy* SRptr = SubRegMap.lookup(R);
1394 if (!SRptr) continue;
1395 SubRegionsTy SR = *SRptr;
1397 for (SubRegionsTy::iterator I=SR.begin(), E=SR.end(); I!=E; ++I)
1398 RegionRoots.push_back(*I);
1401 // We have now scanned the store, marking reachable regions and symbols
1402 // as live. We now remove all the regions that are dead from the store
1403 // as well as update DSymbols with the set symbols that are now dead.
1404 for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
1405 const MemRegion* R = I.getKey();
1407 // If this region live? Is so, none of its symbols are dead.
1408 if (Marked.count(R))
1411 // Remove this dead region from the store.
1412 store = Remove(store, ValMgr.makeLoc(R));
1414 // Mark all non-live symbols that this region references as dead.
1415 if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(R))
1416 SymReaper.maybeDead(SymR->getSymbol());
1418 SVal X = I.getData();
1419 SVal::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
1420 for (; SI != SE; ++SI) SymReaper.maybeDead(*SI);
1426 //===----------------------------------------------------------------------===//
1428 //===----------------------------------------------------------------------===//
1430 void RegionStoreManager::print(Store store, std::ostream& Out,
1431 const char* nl, const char *sep) {
1432 llvm::raw_os_ostream OS(Out);
1433 RegionBindingsTy B = GetRegionBindings(store);
1434 OS << "Store:" << nl;
1436 for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
1437 OS << ' '; I.getKey()->print(OS); OS << " : ";
1438 I.getData().print(OS); OS << nl;