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/AST/CharUnits.h"
18 #include "clang/AST/DeclCXX.h"
19 #include "clang/AST/ExprCXX.h"
20 #include "clang/Analysis/Analyses/LiveVariables.h"
21 #include "clang/Analysis/AnalysisContext.h"
22 #include "clang/Basic/TargetInfo.h"
23 #include "clang/Checker/PathSensitive/GRState.h"
24 #include "clang/Checker/PathSensitive/GRStateTrait.h"
25 #include "clang/Checker/PathSensitive/MemRegion.h"
26 #include "llvm/ADT/ImmutableList.h"
27 #include "llvm/ADT/ImmutableMap.h"
28 #include "llvm/ADT/Optional.h"
29 #include "llvm/Support/raw_ostream.h"
31 using namespace clang
;
34 //===----------------------------------------------------------------------===//
35 // Representation of binding keys.
36 //===----------------------------------------------------------------------===//
41 enum Kind
{ Direct
= 0x0, Default
= 0x1 };
43 llvm ::PointerIntPair
<const MemRegion
*, 1> P
;
46 explicit BindingKey(const MemRegion
*r
, uint64_t offset
, Kind k
)
47 : P(r
, (unsigned) k
), Offset(offset
) {}
50 bool isDirect() const { return P
.getInt() == Direct
; }
52 const MemRegion
*getRegion() const { return P
.getPointer(); }
53 uint64_t getOffset() const { return Offset
; }
55 void Profile(llvm::FoldingSetNodeID
& ID
) const {
56 ID
.AddPointer(P
.getOpaqueValue());
57 ID
.AddInteger(Offset
);
60 static BindingKey
Make(const MemRegion
*R
, Kind k
);
62 bool operator<(const BindingKey
&X
) const {
63 if (P
.getOpaqueValue() < X
.P
.getOpaqueValue())
65 if (P
.getOpaqueValue() > X
.P
.getOpaqueValue())
67 return Offset
< X
.Offset
;
70 bool operator==(const BindingKey
&X
) const {
71 return P
.getOpaqueValue() == X
.P
.getOpaqueValue() &&
75 bool isValid() const {
76 return getRegion() != NULL
;
79 } // end anonymous namespace
81 BindingKey
BindingKey::Make(const MemRegion
*R
, Kind k
) {
82 if (const ElementRegion
*ER
= dyn_cast
<ElementRegion
>(R
)) {
83 const RegionRawOffset
&O
= ER
->getAsArrayOffset();
85 // FIXME: There are some ElementRegions for which we cannot compute
86 // raw offsets yet, including regions with symbolic offsets. These will be
87 // ignored by the store.
88 return BindingKey(O
.getRegion(), O
.getByteOffset(), k
);
91 return BindingKey(R
, 0, k
);
96 llvm::raw_ostream
& operator<<(llvm::raw_ostream
& os
, BindingKey K
) {
97 os
<< '(' << K
.getRegion() << ',' << K
.getOffset()
98 << ',' << (K
.isDirect() ? "direct" : "default")
102 } // end llvm namespace
104 //===----------------------------------------------------------------------===//
105 // Actual Store type.
106 //===----------------------------------------------------------------------===//
108 typedef llvm::ImmutableMap
<BindingKey
, SVal
> RegionBindings
;
110 //===----------------------------------------------------------------------===//
111 // Fine-grained control of RegionStoreManager.
112 //===----------------------------------------------------------------------===//
115 struct minimal_features_tag
{};
116 struct maximal_features_tag
{};
118 class RegionStoreFeatures
{
121 RegionStoreFeatures(minimal_features_tag
) :
122 SupportsFields(false) {}
124 RegionStoreFeatures(maximal_features_tag
) :
125 SupportsFields(true) {}
127 void enableFields(bool t
) { SupportsFields
= t
; }
129 bool supportsFields() const { return SupportsFields
; }
133 //===----------------------------------------------------------------------===//
134 // Main RegionStore logic.
135 //===----------------------------------------------------------------------===//
139 class RegionStoreSubRegionMap
: public SubRegionMap
{
141 typedef llvm::ImmutableSet
<const MemRegion
*> Set
;
142 typedef llvm::DenseMap
<const MemRegion
*, Set
> Map
;
147 bool add(const MemRegion
* Parent
, const MemRegion
* SubRegion
) {
148 Map::iterator I
= M
.find(Parent
);
151 M
.insert(std::make_pair(Parent
, F
.Add(F
.GetEmptySet(), SubRegion
)));
155 I
->second
= F
.Add(I
->second
, SubRegion
);
159 void process(llvm::SmallVectorImpl
<const SubRegion
*> &WL
, const SubRegion
*R
);
161 ~RegionStoreSubRegionMap() {}
163 const Set
*getSubRegions(const MemRegion
*Parent
) const {
164 Map::const_iterator I
= M
.find(Parent
);
165 return I
== M
.end() ? NULL
: &I
->second
;
168 bool iterSubRegions(const MemRegion
* Parent
, Visitor
& V
) const {
169 Map::const_iterator I
= M
.find(Parent
);
175 for (Set::iterator SI
=S
.begin(),SE
=S
.end(); SI
!= SE
; ++SI
) {
176 if (!V
.Visit(Parent
, *SI
))
185 RegionStoreSubRegionMap::process(llvm::SmallVectorImpl
<const SubRegion
*> &WL
,
186 const SubRegion
*R
) {
187 const MemRegion
*superR
= R
->getSuperRegion();
189 if (const SubRegion
*sr
= dyn_cast
<SubRegion
>(superR
))
193 class RegionStoreManager
: public StoreManager
{
194 const RegionStoreFeatures Features
;
195 RegionBindings::Factory RBFactory
;
198 RegionStoreManager(GRStateManager
& mgr
, const RegionStoreFeatures
&f
)
201 RBFactory(mgr
.getAllocator()) {}
203 SubRegionMap
*getSubRegionMap(Store store
) {
204 return getRegionStoreSubRegionMap(store
);
207 RegionStoreSubRegionMap
*getRegionStoreSubRegionMap(Store store
);
209 Optional
<SVal
> getDirectBinding(RegionBindings B
, const MemRegion
*R
);
210 /// getDefaultBinding - Returns an SVal* representing an optional default
211 /// binding associated with a region and its subregions.
212 Optional
<SVal
> getDefaultBinding(RegionBindings B
, const MemRegion
*R
);
214 /// setImplicitDefaultValue - Set the default binding for the provided
215 /// MemRegion to the value implicitly defined for compound literals when
216 /// the value is not specified.
217 Store
setImplicitDefaultValue(Store store
, const MemRegion
*R
, QualType T
);
219 /// ArrayToPointer - Emulates the "decay" of an array to a pointer
220 /// type. 'Array' represents the lvalue of the array being decayed
221 /// to a pointer, and the returned SVal represents the decayed
222 /// version of that lvalue (i.e., a pointer to the first element of
223 /// the array). This is called by GRExprEngine when evaluating
224 /// casts from arrays to pointers.
225 SVal
ArrayToPointer(Loc Array
);
227 SVal
EvalBinOp(BinaryOperator::Opcode Op
,Loc L
, NonLoc R
, QualType resultTy
);
229 Store
getInitialStore(const LocationContext
*InitLoc
) {
230 return RBFactory
.GetEmptyMap().getRoot();
233 //===-------------------------------------------------------------------===//
234 // Binding values to regions.
235 //===-------------------------------------------------------------------===//
237 Store
InvalidateRegions(Store store
,
238 const MemRegion
* const *Begin
,
239 const MemRegion
* const *End
,
240 const Expr
*E
, unsigned Count
,
241 InvalidatedSymbols
*IS
,
242 bool invalidateGlobals
,
243 InvalidatedRegions
*Regions
);
245 public: // Made public for helper classes.
247 void RemoveSubRegionBindings(RegionBindings
&B
, const MemRegion
*R
,
248 RegionStoreSubRegionMap
&M
);
250 RegionBindings
Add(RegionBindings B
, BindingKey K
, SVal V
);
252 RegionBindings
Add(RegionBindings B
, const MemRegion
*R
,
253 BindingKey::Kind k
, SVal V
);
255 const SVal
*Lookup(RegionBindings B
, BindingKey K
);
256 const SVal
*Lookup(RegionBindings B
, const MemRegion
*R
, BindingKey::Kind k
);
258 RegionBindings
Remove(RegionBindings B
, BindingKey K
);
259 RegionBindings
Remove(RegionBindings B
, const MemRegion
*R
,
262 RegionBindings
Remove(RegionBindings B
, const MemRegion
*R
) {
263 return Remove(Remove(B
, R
, BindingKey::Direct
), R
, BindingKey::Default
);
266 public: // Part of public interface to class.
268 Store
Bind(Store store
, Loc LV
, SVal V
);
270 // BindDefault is only used to initialize a region with a default value.
271 Store
BindDefault(Store store
, const MemRegion
*R
, SVal V
) {
272 RegionBindings B
= GetRegionBindings(store
);
273 assert(!Lookup(B
, R
, BindingKey::Default
));
274 assert(!Lookup(B
, R
, BindingKey::Direct
));
275 return Add(B
, R
, BindingKey::Default
, V
).getRoot();
278 Store
BindCompoundLiteral(Store store
, const CompoundLiteralExpr
* CL
,
279 const LocationContext
*LC
, SVal V
);
281 Store
BindDecl(Store store
, const VarRegion
*VR
, SVal InitVal
);
283 Store
BindDeclWithNoInit(Store store
, const VarRegion
*) {
287 /// BindStruct - Bind a compound value to a structure.
288 Store
BindStruct(Store store
, const TypedRegion
* R
, SVal V
);
290 Store
BindArray(Store store
, const TypedRegion
* R
, SVal V
);
292 /// KillStruct - Set the entire struct to unknown.
293 Store
KillStruct(Store store
, const TypedRegion
* R
, SVal DefaultVal
);
295 Store
Remove(Store store
, Loc LV
);
298 //===------------------------------------------------------------------===//
299 // Loading values from regions.
300 //===------------------------------------------------------------------===//
302 /// The high level logic for this method is this:
305 /// return L's binding
306 /// else if L is in killset
309 /// if L is on stack or heap
313 SVal
Retrieve(Store store
, Loc L
, QualType T
= QualType());
315 SVal
RetrieveElement(Store store
, const ElementRegion
*R
);
317 SVal
RetrieveField(Store store
, const FieldRegion
*R
);
319 SVal
RetrieveObjCIvar(Store store
, const ObjCIvarRegion
*R
);
321 SVal
RetrieveVar(Store store
, const VarRegion
*R
);
323 SVal
RetrieveLazySymbol(const TypedRegion
*R
);
325 SVal
RetrieveFieldOrElementCommon(Store store
, const TypedRegion
*R
,
326 QualType Ty
, const MemRegion
*superR
);
328 /// Retrieve the values in a struct and return a CompoundVal, used when doing
332 /// y's value is retrieved by this method.
333 SVal
RetrieveStruct(Store store
, const TypedRegion
* R
);
335 SVal
RetrieveArray(Store store
, const TypedRegion
* R
);
337 /// Used to lazily generate derived symbols for bindings that are defined
338 /// implicitly by default bindings in a super region.
339 Optional
<SVal
> RetrieveDerivedDefaultValue(RegionBindings B
,
340 const MemRegion
*superR
,
341 const TypedRegion
*R
, QualType Ty
);
343 /// Get the state and region whose binding this region R corresponds to.
344 std::pair
<Store
, const MemRegion
*>
345 GetLazyBinding(RegionBindings B
, const MemRegion
*R
);
347 Store
CopyLazyBindings(nonloc::LazyCompoundVal V
, Store store
,
348 const TypedRegion
*R
);
350 //===------------------------------------------------------------------===//
352 //===------------------------------------------------------------------===//
354 /// RemoveDeadBindings - Scans the RegionStore of 'state' for dead values.
355 /// It returns a new Store with these values removed.
356 Store
RemoveDeadBindings(Store store
, const StackFrameContext
*LCtx
,
357 SymbolReaper
& SymReaper
,
358 llvm::SmallVectorImpl
<const MemRegion
*>& RegionRoots
);
360 Store
EnterStackFrame(const GRState
*state
, const StackFrameContext
*frame
);
362 //===------------------------------------------------------------------===//
364 //===------------------------------------------------------------------===//
366 // FIXME: This method will soon be eliminated; see the note in Store.h.
367 DefinedOrUnknownSVal
getSizeInElements(const GRState
*state
,
368 const MemRegion
* R
, QualType EleTy
);
370 //===------------------------------------------------------------------===//
372 //===------------------------------------------------------------------===//
374 static inline RegionBindings
GetRegionBindings(Store store
) {
375 return RegionBindings(static_cast<const RegionBindings::TreeTy
*>(store
));
378 void print(Store store
, llvm::raw_ostream
& Out
, const char* nl
,
381 void iterBindings(Store store
, BindingsHandler
& f
) {
382 RegionBindings B
= GetRegionBindings(store
);
383 for (RegionBindings::iterator I
=B
.begin(), E
=B
.end(); I
!=E
; ++I
) {
384 const BindingKey
&K
= I
.getKey();
387 if (const SubRegion
*R
= dyn_cast
<SubRegion
>(I
.getKey().getRegion())) {
388 // FIXME: Possibly incorporate the offset?
389 if (!f
.HandleBinding(*this, store
, R
, I
.getData()))
396 } // end anonymous namespace
398 //===----------------------------------------------------------------------===//
399 // RegionStore creation.
400 //===----------------------------------------------------------------------===//
402 StoreManager
*clang::CreateRegionStoreManager(GRStateManager
& StMgr
) {
403 RegionStoreFeatures F
= maximal_features_tag();
404 return new RegionStoreManager(StMgr
, F
);
407 StoreManager
*clang::CreateFieldsOnlyRegionStoreManager(GRStateManager
&StMgr
) {
408 RegionStoreFeatures F
= minimal_features_tag();
409 F
.enableFields(true);
410 return new RegionStoreManager(StMgr
, F
);
414 RegionStoreSubRegionMap
*
415 RegionStoreManager::getRegionStoreSubRegionMap(Store store
) {
416 RegionBindings B
= GetRegionBindings(store
);
417 RegionStoreSubRegionMap
*M
= new RegionStoreSubRegionMap();
419 llvm::SmallVector
<const SubRegion
*, 10> WL
;
421 for (RegionBindings::iterator I
=B
.begin(), E
=B
.end(); I
!=E
; ++I
)
422 if (const SubRegion
*R
= dyn_cast
<SubRegion
>(I
.getKey().getRegion()))
425 // We also need to record in the subregion map "intermediate" regions that
426 // don't have direct bindings but are super regions of those that do.
427 while (!WL
.empty()) {
428 const SubRegion
*R
= WL
.back();
436 //===----------------------------------------------------------------------===//
437 // Region Cluster analysis.
438 //===----------------------------------------------------------------------===//
441 template <typename DERIVED
>
442 class ClusterAnalysis
{
444 typedef BumpVector
<BindingKey
> RegionCluster
;
445 typedef llvm::DenseMap
<const MemRegion
*, RegionCluster
*> ClusterMap
;
446 llvm::DenseMap
<const RegionCluster
*, unsigned> Visited
;
447 typedef llvm::SmallVector
<std::pair
<const MemRegion
*, RegionCluster
*>, 10>
450 BumpVectorContext BVC
;
454 RegionStoreManager
&RM
;
456 ValueManager
&ValMgr
;
460 const bool includeGlobals
;
463 ClusterAnalysis(RegionStoreManager
&rm
, GRStateManager
&StateMgr
,
464 RegionBindings b
, const bool includeGlobals
)
465 : RM(rm
), Ctx(StateMgr
.getContext()), ValMgr(StateMgr
.getValueManager()),
466 B(b
), includeGlobals(includeGlobals
) {}
468 RegionBindings
getRegionBindings() const { return B
; }
470 RegionCluster
&AddToCluster(BindingKey K
) {
471 const MemRegion
*R
= K
.getRegion();
472 const MemRegion
*baseR
= R
->getBaseRegion();
473 RegionCluster
&C
= getCluster(baseR
);
475 static_cast<DERIVED
*>(this)->VisitAddedToCluster(baseR
, C
);
479 bool isVisited(const MemRegion
*R
) {
480 return (bool) Visited
[&getCluster(R
->getBaseRegion())];
483 RegionCluster
& getCluster(const MemRegion
*R
) {
484 RegionCluster
*&CRef
= ClusterM
[R
];
486 void *Mem
= BVC
.getAllocator().template Allocate
<RegionCluster
>();
487 CRef
= new (Mem
) RegionCluster(BVC
, 10);
492 void GenerateClusters() {
493 // Scan the entire set of bindings and make the region clusters.
494 for (RegionBindings::iterator RI
= B
.begin(), RE
= B
.end(); RI
!= RE
; ++RI
){
495 RegionCluster
&C
= AddToCluster(RI
.getKey());
496 if (const MemRegion
*R
= RI
.getData().getAsRegion()) {
497 // Generate a cluster, but don't add the region to the cluster
498 // if there aren't any bindings.
499 getCluster(R
->getBaseRegion());
501 if (includeGlobals
) {
502 const MemRegion
*R
= RI
.getKey().getRegion();
503 if (isa
<NonStaticGlobalSpaceRegion
>(R
->getMemorySpace()))
509 bool AddToWorkList(const MemRegion
*R
, RegionCluster
&C
) {
510 if (unsigned &visited
= Visited
[&C
])
515 WL
.push_back(std::make_pair(R
, &C
));
519 bool AddToWorkList(BindingKey K
) {
520 return AddToWorkList(K
.getRegion());
523 bool AddToWorkList(const MemRegion
*R
) {
524 const MemRegion
*baseR
= R
->getBaseRegion();
525 return AddToWorkList(baseR
, getCluster(baseR
));
529 while (!WL
.empty()) {
530 const MemRegion
*baseR
;
532 llvm::tie(baseR
, C
) = WL
.back();
535 // First visit the cluster.
536 static_cast<DERIVED
*>(this)->VisitCluster(baseR
, C
->begin(), C
->end());
538 // Next, visit the base region.
539 static_cast<DERIVED
*>(this)->VisitBaseRegion(baseR
);
544 void VisitAddedToCluster(const MemRegion
*baseR
, RegionCluster
&C
) {}
545 void VisitCluster(const MemRegion
*baseR
, BindingKey
*I
, BindingKey
*E
) {}
546 void VisitBaseRegion(const MemRegion
*baseR
) {}
550 //===----------------------------------------------------------------------===//
551 // Binding invalidation.
552 //===----------------------------------------------------------------------===//
554 void RegionStoreManager::RemoveSubRegionBindings(RegionBindings
&B
,
556 RegionStoreSubRegionMap
&M
) {
558 if (const RegionStoreSubRegionMap::Set
*S
= M
.getSubRegions(R
))
559 for (RegionStoreSubRegionMap::Set::iterator I
= S
->begin(), E
= S
->end();
561 RemoveSubRegionBindings(B
, *I
, M
);
567 class InvalidateRegionsWorker
: public ClusterAnalysis
<InvalidateRegionsWorker
>
571 StoreManager::InvalidatedSymbols
*IS
;
572 StoreManager::InvalidatedRegions
*Regions
;
574 InvalidateRegionsWorker(RegionStoreManager
&rm
,
575 GRStateManager
&stateMgr
,
577 const Expr
*ex
, unsigned count
,
578 StoreManager::InvalidatedSymbols
*is
,
579 StoreManager::InvalidatedRegions
*r
,
581 : ClusterAnalysis
<InvalidateRegionsWorker
>(rm
, stateMgr
, b
, includeGlobals
),
582 Ex(ex
), Count(count
), IS(is
), Regions(r
) {}
584 void VisitCluster(const MemRegion
*baseR
, BindingKey
*I
, BindingKey
*E
);
585 void VisitBaseRegion(const MemRegion
*baseR
);
588 void VisitBinding(SVal V
);
592 void InvalidateRegionsWorker::VisitBinding(SVal V
) {
593 // A symbol? Mark it touched by the invalidation.
595 if (SymbolRef Sym
= V
.getAsSymbol())
598 if (const MemRegion
*R
= V
.getAsRegion()) {
603 // Is it a LazyCompoundVal? All references get invalidated as well.
604 if (const nonloc::LazyCompoundVal
*LCS
=
605 dyn_cast
<nonloc::LazyCompoundVal
>(&V
)) {
607 const MemRegion
*LazyR
= LCS
->getRegion();
608 RegionBindings B
= RegionStoreManager::GetRegionBindings(LCS
->getStore());
610 for (RegionBindings::iterator RI
= B
.begin(), RE
= B
.end(); RI
!= RE
; ++RI
){
611 const SubRegion
*baseR
= dyn_cast
<SubRegion
>(RI
.getKey().getRegion());
612 if (baseR
&& baseR
->isSubRegionOf(LazyR
))
613 VisitBinding(RI
.getData());
620 void InvalidateRegionsWorker::VisitCluster(const MemRegion
*baseR
,
621 BindingKey
*I
, BindingKey
*E
) {
622 for ( ; I
!= E
; ++I
) {
623 // Get the old binding. Is it a region? If so, add it to the worklist.
624 const BindingKey
&K
= *I
;
625 if (const SVal
*V
= RM
.Lookup(B
, K
))
632 void InvalidateRegionsWorker::VisitBaseRegion(const MemRegion
*baseR
) {
634 // Symbolic region? Mark that symbol touched by the invalidation.
635 if (const SymbolicRegion
*SR
= dyn_cast
<SymbolicRegion
>(baseR
))
636 IS
->insert(SR
->getSymbol());
639 // BlockDataRegion? If so, invalidate captured variables that are passed
641 if (const BlockDataRegion
*BR
= dyn_cast
<BlockDataRegion
>(baseR
)) {
642 for (BlockDataRegion::referenced_vars_iterator
643 BI
= BR
->referenced_vars_begin(), BE
= BR
->referenced_vars_end() ;
645 const VarRegion
*VR
= *BI
;
646 const VarDecl
*VD
= VR
->getDecl();
647 if (VD
->getAttr
<BlocksAttr
>() || !VD
->hasLocalStorage())
653 // Otherwise, we have a normal data region. Record that we touched the region.
655 Regions
->push_back(baseR
);
657 if (isa
<AllocaRegion
>(baseR
) || isa
<SymbolicRegion
>(baseR
)) {
658 // Invalidate the region by setting its default value to
659 // conjured symbol. The type of the symbol is irrelavant.
660 DefinedOrUnknownSVal V
= ValMgr
.getConjuredSymbolVal(baseR
, Ex
, Ctx
.IntTy
,
662 B
= RM
.Add(B
, baseR
, BindingKey::Default
, V
);
666 if (!baseR
->isBoundable())
669 const TypedRegion
*TR
= cast
<TypedRegion
>(baseR
);
670 QualType T
= TR
->getValueType();
672 // Invalidate the binding.
673 if (T
->isStructureType()) {
674 // Invalidate the region by setting its default value to
675 // conjured symbol. The type of the symbol is irrelavant.
676 DefinedOrUnknownSVal V
= ValMgr
.getConjuredSymbolVal(baseR
, Ex
, Ctx
.IntTy
,
678 B
= RM
.Add(B
, baseR
, BindingKey::Default
, V
);
682 if (const ArrayType
*AT
= Ctx
.getAsArrayType(T
)) {
683 // Set the default value of the array to conjured symbol.
684 DefinedOrUnknownSVal V
=
685 ValMgr
.getConjuredSymbolVal(baseR
, Ex
, AT
->getElementType(), Count
);
686 B
= RM
.Add(B
, baseR
, BindingKey::Default
, V
);
690 if (includeGlobals
&&
691 isa
<NonStaticGlobalSpaceRegion
>(baseR
->getMemorySpace())) {
692 // If the region is a global and we are invalidating all globals,
693 // just erase the entry. This causes all globals to be lazily
694 // symbolicated from the same base symbol.
695 B
= RM
.Remove(B
, baseR
);
700 DefinedOrUnknownSVal V
= ValMgr
.getConjuredSymbolVal(baseR
, Ex
, T
, Count
);
701 assert(SymbolManager::canSymbolicate(T
) || V
.isUnknown());
702 B
= RM
.Add(B
, baseR
, BindingKey::Direct
, V
);
705 Store
RegionStoreManager::InvalidateRegions(Store store
,
706 const MemRegion
* const *I
,
707 const MemRegion
* const *E
,
708 const Expr
*Ex
, unsigned Count
,
709 InvalidatedSymbols
*IS
,
710 bool invalidateGlobals
,
711 InvalidatedRegions
*Regions
) {
712 InvalidateRegionsWorker
W(*this, StateMgr
,
713 RegionStoreManager::GetRegionBindings(store
),
714 Ex
, Count
, IS
, Regions
, invalidateGlobals
);
716 // Scan the bindings and generate the clusters.
717 W
.GenerateClusters();
719 // Add I .. E to the worklist.
725 // Return the new bindings.
726 RegionBindings B
= W
.getRegionBindings();
728 if (invalidateGlobals
) {
729 // Bind the non-static globals memory space to a new symbol that we will
730 // use to derive the bindings for all non-static globals.
731 const GlobalsSpaceRegion
*GS
= MRMgr
.getGlobalsRegion();
733 ValMgr
.getConjuredSymbolVal(/* SymbolTag = */ (void*) GS
, Ex
,
734 /* symbol type, doesn't matter */ Ctx
.IntTy
,
736 B
= Add(B
, BindingKey::Make(GS
, BindingKey::Default
), V
);
738 // Even if there are no bindings in the global scope, we still need to
739 // record that we touched it.
741 Regions
->push_back(GS
);
747 //===----------------------------------------------------------------------===//
748 // Extents for regions.
749 //===----------------------------------------------------------------------===//
751 DefinedOrUnknownSVal
RegionStoreManager::getSizeInElements(const GRState
*state
,
754 SVal Size
= cast
<SubRegion
>(R
)->getExtent(ValMgr
);
755 SValuator
&SVator
= ValMgr
.getSValuator();
756 const llvm::APSInt
*SizeInt
= SVator
.getKnownValue(state
, Size
);
760 CharUnits RegionSize
= CharUnits::fromQuantity(SizeInt
->getSExtValue());
762 if (Ctx
.getAsVariableArrayType(EleTy
)) {
763 // FIXME: We need to track extra state to properly record the size
764 // of VLAs. Returning UnknownVal here, however, is a stop-gap so that
765 // we don't have a divide-by-zero below.
769 CharUnits EleSize
= Ctx
.getTypeSizeInChars(EleTy
);
771 // If a variable is reinterpreted as a type that doesn't fit into a larger
772 // type evenly, round it down.
773 // This is a signed value, since it's used in arithmetic with signed indices.
774 return ValMgr
.makeIntVal(RegionSize
/ EleSize
, false);
777 //===----------------------------------------------------------------------===//
778 // Location and region casting.
779 //===----------------------------------------------------------------------===//
781 /// ArrayToPointer - Emulates the "decay" of an array to a pointer
782 /// type. 'Array' represents the lvalue of the array being decayed
783 /// to a pointer, and the returned SVal represents the decayed
784 /// version of that lvalue (i.e., a pointer to the first element of
785 /// the array). This is called by GRExprEngine when evaluating casts
786 /// from arrays to pointers.
787 SVal
RegionStoreManager::ArrayToPointer(Loc Array
) {
788 if (!isa
<loc::MemRegionVal
>(Array
))
791 const MemRegion
* R
= cast
<loc::MemRegionVal
>(&Array
)->getRegion();
792 const TypedRegion
* ArrayR
= dyn_cast
<TypedRegion
>(R
);
797 // Strip off typedefs from the ArrayRegion's ValueType.
798 QualType T
= ArrayR
->getValueType().getDesugaredType();
799 ArrayType
*AT
= cast
<ArrayType
>(T
);
800 T
= AT
->getElementType();
802 NonLoc ZeroIdx
= ValMgr
.makeZeroArrayIndex();
803 return loc::MemRegionVal(MRMgr
.getElementRegion(T
, ZeroIdx
, ArrayR
, Ctx
));
806 //===----------------------------------------------------------------------===//
807 // Pointer arithmetic.
808 //===----------------------------------------------------------------------===//
810 SVal
RegionStoreManager::EvalBinOp(BinaryOperator::Opcode Op
, Loc L
, NonLoc R
,
812 // Assume the base location is MemRegionVal.
813 if (!isa
<loc::MemRegionVal
>(L
))
816 // Special case for zero RHS.
817 if (R
.isZeroConstant()) {
820 // Handle it normally.
824 // FIXME: does this need to be casted to match resultTy?
829 const MemRegion
* MR
= cast
<loc::MemRegionVal
>(L
).getRegion();
830 const ElementRegion
*ER
= 0;
832 switch (MR
->getKind()) {
833 case MemRegion::SymbolicRegionKind
: {
834 const SymbolicRegion
*SR
= cast
<SymbolicRegion
>(MR
);
835 SymbolRef Sym
= SR
->getSymbol();
836 QualType T
= Sym
->getType(Ctx
);
839 if (const PointerType
*PT
= T
->getAs
<PointerType
>())
840 EleTy
= PT
->getPointeeType();
842 EleTy
= T
->getAs
<ObjCObjectPointerType
>()->getPointeeType();
844 const NonLoc
&ZeroIdx
= ValMgr
.makeZeroArrayIndex();
845 ER
= MRMgr
.getElementRegion(EleTy
, ZeroIdx
, SR
, Ctx
);
848 case MemRegion::AllocaRegionKind
: {
849 const AllocaRegion
*AR
= cast
<AllocaRegion
>(MR
);
850 QualType EleTy
= Ctx
.CharTy
; // Create an ElementRegion of bytes.
851 NonLoc ZeroIdx
= ValMgr
.makeZeroArrayIndex();
852 ER
= MRMgr
.getElementRegion(EleTy
, ZeroIdx
, AR
, Ctx
);
856 case MemRegion::ElementRegionKind
: {
857 ER
= cast
<ElementRegion
>(MR
);
862 case MemRegion::VarRegionKind
:
863 case MemRegion::StringRegionKind
: {
867 case MemRegion::CompoundLiteralRegionKind
:
868 case MemRegion::FieldRegionKind
:
869 case MemRegion::ObjCIvarRegionKind
:
870 case MemRegion::CXXObjectRegionKind
:
873 case MemRegion::FunctionTextRegionKind
:
874 case MemRegion::BlockTextRegionKind
:
875 case MemRegion::BlockDataRegionKind
:
876 // Technically this can happen if people do funny things with casts.
879 case MemRegion::CXXThisRegionKind
:
881 "Cannot perform pointer arithmetic on implicit argument 'this'");
882 case MemRegion::GenericMemSpaceRegionKind
:
883 case MemRegion::StackLocalsSpaceRegionKind
:
884 case MemRegion::StackArgumentsSpaceRegionKind
:
885 case MemRegion::HeapSpaceRegionKind
:
886 case MemRegion::NonStaticGlobalSpaceRegionKind
:
887 case MemRegion::StaticGlobalSpaceRegionKind
:
888 case MemRegion::UnknownSpaceRegionKind
:
889 assert(0 && "Cannot perform pointer arithmetic on a MemSpace");
893 SVal Idx
= ER
->getIndex();
894 nonloc::ConcreteInt
* Base
= dyn_cast
<nonloc::ConcreteInt
>(&Idx
);
896 // For now, only support:
897 // (a) concrete integer indices that can easily be resolved
898 // (b) 0 + symbolic index
900 if (nonloc::ConcreteInt
*Offset
= dyn_cast
<nonloc::ConcreteInt
>(&R
)) {
901 // FIXME: Should use SValuator here.
903 Base
->evalBinOp(ValMgr
, Op
,
904 cast
<nonloc::ConcreteInt
>(ValMgr
.convertToArrayIndex(*Offset
)));
906 if (!isa
<NonLoc
>(NewIdx
))
909 const MemRegion
* NewER
=
910 MRMgr
.getElementRegion(ER
->getElementType(), cast
<NonLoc
>(NewIdx
),
911 ER
->getSuperRegion(), Ctx
);
912 return ValMgr
.makeLoc(NewER
);
914 if (0 == Base
->getValue()) {
915 const MemRegion
* NewER
=
916 MRMgr
.getElementRegion(ER
->getElementType(), R
,
917 ER
->getSuperRegion(), Ctx
);
918 return ValMgr
.makeLoc(NewER
);
925 //===----------------------------------------------------------------------===//
926 // Loading values from regions.
927 //===----------------------------------------------------------------------===//
929 Optional
<SVal
> RegionStoreManager::getDirectBinding(RegionBindings B
,
930 const MemRegion
*R
) {
932 if (const SVal
*V
= Lookup(B
, R
, BindingKey::Direct
))
935 return Optional
<SVal
>();
938 Optional
<SVal
> RegionStoreManager::getDefaultBinding(RegionBindings B
,
939 const MemRegion
*R
) {
940 if (R
->isBoundable())
941 if (const TypedRegion
*TR
= dyn_cast
<TypedRegion
>(R
))
942 if (TR
->getValueType()->isUnionType())
945 if (const SVal
*V
= Lookup(B
, R
, BindingKey::Default
))
948 return Optional
<SVal
>();
951 SVal
RegionStoreManager::Retrieve(Store store
, Loc L
, QualType T
) {
952 assert(!isa
<UnknownVal
>(L
) && "location unknown");
953 assert(!isa
<UndefinedVal
>(L
) && "location undefined");
955 // For access to concrete addresses, return UnknownVal. Checks
956 // for null dereferences (and similar errors) are done by checkers, not
958 // FIXME: We can consider lazily symbolicating such memory, but we really
959 // should defer this when we can reason easily about symbolicating arrays
961 if (isa
<loc::ConcreteInt
>(L
)) {
965 const MemRegion
*MR
= cast
<loc::MemRegionVal
>(L
).getRegion();
967 if (isa
<AllocaRegion
>(MR
) || isa
<SymbolicRegion
>(MR
)) {
969 const SymbolicRegion
*SR
= cast
<SymbolicRegion
>(MR
);
970 T
= SR
->getSymbol()->getType(Ctx
);
972 MR
= GetElementZeroRegion(MR
, T
);
975 if (isa
<CodeTextRegion
>(MR
)) {
976 assert(0 && "Why load from a code text region?");
980 // FIXME: Perhaps this method should just take a 'const MemRegion*' argument
981 // instead of 'Loc', and have the other Loc cases handled at a higher level.
982 const TypedRegion
*R
= cast
<TypedRegion
>(MR
);
983 QualType RTy
= R
->getValueType();
985 // FIXME: We should eventually handle funny addressing. e.g.:
989 // char *q = (char*) p;
990 // char c = *q; // returns the first byte of 'x'.
992 // Such funny addressing will occur due to layering of regions.
994 if (RTy
->isStructureOrClassType())
995 return RetrieveStruct(store
, R
);
997 // FIXME: Handle unions.
998 if (RTy
->isUnionType())
1001 if (RTy
->isArrayType())
1002 return RetrieveArray(store
, R
);
1004 // FIXME: handle Vector types.
1005 if (RTy
->isVectorType())
1006 return UnknownVal();
1008 if (const FieldRegion
* FR
= dyn_cast
<FieldRegion
>(R
))
1009 return CastRetrievedVal(RetrieveField(store
, FR
), FR
, T
, false);
1011 if (const ElementRegion
* ER
= dyn_cast
<ElementRegion
>(R
)) {
1012 // FIXME: Here we actually perform an implicit conversion from the loaded
1013 // value to the element type. Eventually we want to compose these values
1014 // more intelligently. For example, an 'element' can encompass multiple
1015 // bound regions (e.g., several bound bytes), or could be a subset of
1017 return CastRetrievedVal(RetrieveElement(store
, ER
), ER
, T
, false);
1020 if (const ObjCIvarRegion
*IVR
= dyn_cast
<ObjCIvarRegion
>(R
)) {
1021 // FIXME: Here we actually perform an implicit conversion from the loaded
1022 // value to the ivar type. What we should model is stores to ivars
1023 // that blow past the extent of the ivar. If the address of the ivar is
1024 // reinterpretted, it is possible we stored a different value that could
1025 // fit within the ivar. Either we need to cast these when storing them
1026 // or reinterpret them lazily (as we do here).
1027 return CastRetrievedVal(RetrieveObjCIvar(store
, IVR
), IVR
, T
, false);
1030 if (const VarRegion
*VR
= dyn_cast
<VarRegion
>(R
)) {
1031 // FIXME: Here we actually perform an implicit conversion from the loaded
1032 // value to the variable type. What we should model is stores to variables
1033 // that blow past the extent of the variable. If the address of the
1034 // variable is reinterpretted, it is possible we stored a different value
1035 // that could fit within the variable. Either we need to cast these when
1036 // storing them or reinterpret them lazily (as we do here).
1037 return CastRetrievedVal(RetrieveVar(store
, VR
), VR
, T
, false);
1040 RegionBindings B
= GetRegionBindings(store
);
1041 const SVal
*V
= Lookup(B
, R
, BindingKey::Direct
);
1043 // Check if the region has a binding.
1047 // The location does not have a bound value. This means that it has
1048 // the value it had upon its creation and/or entry to the analyzed
1049 // function/method. These are either symbolic values or 'undefined'.
1050 if (R
->hasStackNonParametersStorage()) {
1051 // All stack variables are considered to have undefined values
1052 // upon creation. All heap allocated blocks are considered to
1053 // have undefined values as well unless they are explicitly bound
1054 // to specific values.
1055 return UndefinedVal();
1058 // All other values are symbolic.
1059 return ValMgr
.getRegionValueSymbolVal(R
);
1062 std::pair
<Store
, const MemRegion
*>
1063 RegionStoreManager::GetLazyBinding(RegionBindings B
, const MemRegion
*R
) {
1064 if (Optional
<SVal
> OV
= getDirectBinding(B
, R
))
1065 if (const nonloc::LazyCompoundVal
*V
=
1066 dyn_cast
<nonloc::LazyCompoundVal
>(OV
.getPointer()))
1067 return std::make_pair(V
->getStore(), V
->getRegion());
1069 if (const ElementRegion
*ER
= dyn_cast
<ElementRegion
>(R
)) {
1070 const std::pair
<Store
, const MemRegion
*> &X
=
1071 GetLazyBinding(B
, ER
->getSuperRegion());
1074 return std::make_pair(X
.first
,
1075 MRMgr
.getElementRegionWithSuper(ER
, X
.second
));
1077 else if (const FieldRegion
*FR
= dyn_cast
<FieldRegion
>(R
)) {
1078 const std::pair
<Store
, const MemRegion
*> &X
=
1079 GetLazyBinding(B
, FR
->getSuperRegion());
1082 return std::make_pair(X
.first
,
1083 MRMgr
.getFieldRegionWithSuper(FR
, X
.second
));
1085 // The NULL MemRegion indicates an non-existent lazy binding. A NULL Store is
1086 // possible for a valid lazy binding.
1087 return std::make_pair((Store
) 0, (const MemRegion
*) 0);
1090 SVal
RegionStoreManager::RetrieveElement(Store store
,
1091 const ElementRegion
* R
) {
1092 // Check if the region has a binding.
1093 RegionBindings B
= GetRegionBindings(store
);
1094 if (const Optional
<SVal
> &V
= getDirectBinding(B
, R
))
1097 const MemRegion
* superR
= R
->getSuperRegion();
1099 // Check if the region is an element region of a string literal.
1100 if (const StringRegion
*StrR
=dyn_cast
<StringRegion
>(superR
)) {
1101 // FIXME: Handle loads from strings where the literal is treated as
1102 // an integer, e.g., *((unsigned int*)"hello")
1103 QualType T
= Ctx
.getAsArrayType(StrR
->getValueType())->getElementType();
1104 if (T
!= Ctx
.getCanonicalType(R
->getElementType()))
1105 return UnknownVal();
1107 const StringLiteral
*Str
= StrR
->getStringLiteral();
1108 SVal Idx
= R
->getIndex();
1109 if (nonloc::ConcreteInt
*CI
= dyn_cast
<nonloc::ConcreteInt
>(&Idx
)) {
1110 int64_t i
= CI
->getValue().getSExtValue();
1111 int64_t byteLength
= Str
->getByteLength();
1112 // Technically, only i == byteLength is guaranteed to be null.
1113 // However, such overflows should be caught before reaching this point;
1114 // the only time such an access would be made is if a string literal was
1115 // used to initialize a larger array.
1116 char c
= (i
>= byteLength
) ? '\0' : Str
->getString()[i
];
1117 return ValMgr
.makeIntVal(c
, T
);
1121 // Check for loads from a code text region. For such loads, just give up.
1122 if (isa
<CodeTextRegion
>(superR
))
1123 return UnknownVal();
1125 // Handle the case where we are indexing into a larger scalar object.
1126 // For example, this handles:
1130 // FIXME: This is a hack, and doesn't do anything really intelligent yet.
1131 const RegionRawOffset
&O
= R
->getAsArrayOffset();
1132 if (const TypedRegion
*baseR
= dyn_cast_or_null
<TypedRegion
>(O
.getRegion())) {
1133 QualType baseT
= baseR
->getValueType();
1134 if (baseT
->isScalarType()) {
1135 QualType elemT
= R
->getElementType();
1136 if (elemT
->isScalarType()) {
1137 if (Ctx
.getTypeSizeInChars(baseT
) >= Ctx
.getTypeSizeInChars(elemT
)) {
1138 if (const Optional
<SVal
> &V
= getDirectBinding(B
, superR
)) {
1139 if (SymbolRef parentSym
= V
->getAsSymbol())
1140 return ValMgr
.getDerivedRegionValueSymbolVal(parentSym
, R
);
1142 if (V
->isUnknownOrUndef())
1144 // Other cases: give up. We are indexing into a larger object
1145 // that has some value, but we don't know how to handle that yet.
1146 return UnknownVal();
1152 return RetrieveFieldOrElementCommon(store
, R
, R
->getElementType(), superR
);
1155 SVal
RegionStoreManager::RetrieveField(Store store
,
1156 const FieldRegion
* R
) {
1158 // Check if the region has a binding.
1159 RegionBindings B
= GetRegionBindings(store
);
1160 if (const Optional
<SVal
> &V
= getDirectBinding(B
, R
))
1163 QualType Ty
= R
->getValueType();
1164 return RetrieveFieldOrElementCommon(store
, R
, Ty
, R
->getSuperRegion());
1168 RegionStoreManager::RetrieveDerivedDefaultValue(RegionBindings B
,
1169 const MemRegion
*superR
,
1170 const TypedRegion
*R
,
1173 if (const Optional
<SVal
> &D
= getDefaultBinding(B
, superR
)) {
1174 if (SymbolRef parentSym
= D
->getAsSymbol())
1175 return ValMgr
.getDerivedRegionValueSymbolVal(parentSym
, R
);
1177 if (D
->isZeroConstant())
1178 return ValMgr
.makeZeroVal(Ty
);
1180 if (D
->isUnknownOrUndef())
1183 assert(0 && "Unknown default value");
1186 return Optional
<SVal
>();
1189 SVal
RegionStoreManager::RetrieveFieldOrElementCommon(Store store
,
1190 const TypedRegion
*R
,
1192 const MemRegion
*superR
) {
1194 // At this point we have already checked in either RetrieveElement or
1195 // RetrieveField if 'R' has a direct binding.
1197 RegionBindings B
= GetRegionBindings(store
);
1200 if (const Optional
<SVal
> &D
=
1201 RetrieveDerivedDefaultValue(B
, superR
, R
, Ty
))
1204 // If our super region is a field or element itself, walk up the region
1205 // hierarchy to see if there is a default value installed in an ancestor.
1206 if (const SubRegion
*SR
= dyn_cast
<SubRegion
>(superR
)) {
1207 superR
= SR
->getSuperRegion();
1214 Store lazyBindingStore
= NULL
;
1215 const MemRegion
*lazyBindingRegion
= NULL
;
1216 llvm::tie(lazyBindingStore
, lazyBindingRegion
) = GetLazyBinding(B
, R
);
1218 if (lazyBindingRegion
) {
1219 if (const ElementRegion
*ER
= dyn_cast
<ElementRegion
>(lazyBindingRegion
))
1220 return RetrieveElement(lazyBindingStore
, ER
);
1221 return RetrieveField(lazyBindingStore
,
1222 cast
<FieldRegion
>(lazyBindingRegion
));
1225 if (R
->hasStackNonParametersStorage()) {
1226 if (const ElementRegion
*ER
= dyn_cast
<ElementRegion
>(R
)) {
1227 // Currently we don't reason specially about Clang-style vectors. Check
1228 // if superR is a vector and if so return Unknown.
1229 if (const TypedRegion
*typedSuperR
= dyn_cast
<TypedRegion
>(superR
)) {
1230 if (typedSuperR
->getValueType()->isVectorType())
1231 return UnknownVal();
1234 // FIXME: We also need to take ElementRegions with symbolic indexes into
1236 if (!ER
->getIndex().isConstant())
1237 return UnknownVal();
1240 return UndefinedVal();
1243 // All other values are symbolic.
1244 return ValMgr
.getRegionValueSymbolVal(R
);
1247 SVal
RegionStoreManager::RetrieveObjCIvar(Store store
, const ObjCIvarRegion
* R
){
1249 // Check if the region has a binding.
1250 RegionBindings B
= GetRegionBindings(store
);
1252 if (const Optional
<SVal
> &V
= getDirectBinding(B
, R
))
1255 const MemRegion
*superR
= R
->getSuperRegion();
1257 // Check if the super region has a default binding.
1258 if (const Optional
<SVal
> &V
= getDefaultBinding(B
, superR
)) {
1259 if (SymbolRef parentSym
= V
->getAsSymbol())
1260 return ValMgr
.getDerivedRegionValueSymbolVal(parentSym
, R
);
1262 // Other cases: give up.
1263 return UnknownVal();
1266 return RetrieveLazySymbol(R
);
1269 SVal
RegionStoreManager::RetrieveVar(Store store
, const VarRegion
*R
) {
1271 // Check if the region has a binding.
1272 RegionBindings B
= GetRegionBindings(store
);
1274 if (const Optional
<SVal
> &V
= getDirectBinding(B
, R
))
1277 // Lazily derive a value for the VarRegion.
1278 const VarDecl
*VD
= R
->getDecl();
1279 QualType T
= VD
->getType();
1280 const MemSpaceRegion
*MS
= R
->getMemorySpace();
1282 if (isa
<UnknownSpaceRegion
>(MS
) ||
1283 isa
<StackArgumentsSpaceRegion
>(MS
))
1284 return ValMgr
.getRegionValueSymbolVal(R
);
1286 if (isa
<GlobalsSpaceRegion
>(MS
)) {
1287 if (isa
<NonStaticGlobalSpaceRegion
>(MS
)) {
1288 // Is 'VD' declared constant? If so, retrieve the constant value.
1289 QualType CT
= Ctx
.getCanonicalType(T
);
1290 if (CT
.isConstQualified()) {
1291 const Expr
*Init
= VD
->getInit();
1292 // Do the null check first, as we want to call 'IgnoreParenCasts'.
1294 if (const IntegerLiteral
*IL
=
1295 dyn_cast
<IntegerLiteral
>(Init
->IgnoreParenCasts())) {
1296 const nonloc::ConcreteInt
&V
= ValMgr
.makeIntVal(IL
);
1297 return ValMgr
.getSValuator().EvalCast(V
, Init
->getType(),
1302 if (const Optional
<SVal
> &V
= RetrieveDerivedDefaultValue(B
, MS
, R
, CT
))
1303 return V
.getValue();
1305 return ValMgr
.getRegionValueSymbolVal(R
);
1308 if (T
->isIntegerType())
1309 return ValMgr
.makeIntVal(0, T
);
1310 if (T
->isPointerType())
1311 return ValMgr
.makeNull();
1313 return UnknownVal();
1316 return UndefinedVal();
1319 SVal
RegionStoreManager::RetrieveLazySymbol(const TypedRegion
*R
) {
1320 // All other values are symbolic.
1321 return ValMgr
.getRegionValueSymbolVal(R
);
1324 SVal
RegionStoreManager::RetrieveStruct(Store store
, const TypedRegion
* R
) {
1325 QualType T
= R
->getValueType();
1326 assert(T
->isStructureOrClassType());
1327 return ValMgr
.makeLazyCompoundVal(store
, R
);
1330 SVal
RegionStoreManager::RetrieveArray(Store store
, const TypedRegion
* R
) {
1331 assert(Ctx
.getAsConstantArrayType(R
->getValueType()));
1332 return ValMgr
.makeLazyCompoundVal(store
, R
);
1335 //===----------------------------------------------------------------------===//
1336 // Binding values to regions.
1337 //===----------------------------------------------------------------------===//
1339 Store
RegionStoreManager::Remove(Store store
, Loc L
) {
1340 if (isa
<loc::MemRegionVal
>(L
))
1341 if (const MemRegion
* R
= cast
<loc::MemRegionVal
>(L
).getRegion())
1342 return Remove(GetRegionBindings(store
), R
).getRoot();
1347 Store
RegionStoreManager::Bind(Store store
, Loc L
, SVal V
) {
1348 if (isa
<loc::ConcreteInt
>(L
))
1351 // If we get here, the location should be a region.
1352 const MemRegion
*R
= cast
<loc::MemRegionVal
>(L
).getRegion();
1354 // Check if the region is a struct region.
1355 if (const TypedRegion
* TR
= dyn_cast
<TypedRegion
>(R
))
1356 if (TR
->getValueType()->isStructureOrClassType())
1357 return BindStruct(store
, TR
, V
);
1359 if (const ElementRegion
*ER
= dyn_cast
<ElementRegion
>(R
)) {
1360 if (ER
->getIndex().isZeroConstant()) {
1361 if (const TypedRegion
*superR
=
1362 dyn_cast
<TypedRegion
>(ER
->getSuperRegion())) {
1363 QualType superTy
= superR
->getValueType();
1364 // For now, just invalidate the fields of the struct/union/class.
1365 // This is for test rdar_test_7185607 in misc-ps-region-store.m.
1366 // FIXME: Precisely handle the fields of the record.
1367 if (superTy
->isStructureOrClassType())
1368 return KillStruct(store
, superR
, UnknownVal());
1372 else if (const SymbolicRegion
*SR
= dyn_cast
<SymbolicRegion
>(R
)) {
1373 // Binding directly to a symbolic region should be treated as binding
1375 QualType T
= SR
->getSymbol()->getType(Ctx
);
1377 // FIXME: Is this the right way to handle symbols that are references?
1378 if (const PointerType
*PT
= T
->getAs
<PointerType
>())
1379 T
= PT
->getPointeeType();
1381 T
= T
->getAs
<ReferenceType
>()->getPointeeType();
1383 R
= GetElementZeroRegion(SR
, T
);
1386 // Perform the binding.
1387 RegionBindings B
= GetRegionBindings(store
);
1388 return Add(B
, R
, BindingKey::Direct
, V
).getRoot();
1391 Store
RegionStoreManager::BindDecl(Store store
, const VarRegion
*VR
,
1394 QualType T
= VR
->getDecl()->getType();
1396 if (T
->isArrayType())
1397 return BindArray(store
, VR
, InitVal
);
1398 if (T
->isStructureOrClassType())
1399 return BindStruct(store
, VR
, InitVal
);
1401 return Bind(store
, ValMgr
.makeLoc(VR
), InitVal
);
1404 // FIXME: this method should be merged into Bind().
1405 Store
RegionStoreManager::BindCompoundLiteral(Store store
,
1406 const CompoundLiteralExpr
*CL
,
1407 const LocationContext
*LC
,
1409 return Bind(store
, loc::MemRegionVal(MRMgr
.getCompoundLiteralRegion(CL
, LC
)),
1414 Store
RegionStoreManager::setImplicitDefaultValue(Store store
,
1417 RegionBindings B
= GetRegionBindings(store
);
1420 if (Loc::IsLocType(T
))
1421 V
= ValMgr
.makeNull();
1422 else if (T
->isIntegerType())
1423 V
= ValMgr
.makeZeroVal(T
);
1424 else if (T
->isStructureOrClassType() || T
->isArrayType()) {
1425 // Set the default value to a zero constant when it is a structure
1426 // or array. The type doesn't really matter.
1427 V
= ValMgr
.makeZeroVal(Ctx
.IntTy
);
1433 return Add(B
, R
, BindingKey::Default
, V
).getRoot();
1436 Store
RegionStoreManager::BindArray(Store store
, const TypedRegion
* R
,
1439 const ArrayType
*AT
=cast
<ArrayType
>(Ctx
.getCanonicalType(R
->getValueType()));
1440 QualType ElementTy
= AT
->getElementType();
1441 Optional
<uint64_t> Size
;
1443 if (const ConstantArrayType
* CAT
= dyn_cast
<ConstantArrayType
>(AT
))
1444 Size
= CAT
->getSize().getZExtValue();
1446 // Check if the init expr is a string literal.
1447 if (loc::MemRegionVal
*MRV
= dyn_cast
<loc::MemRegionVal
>(&Init
)) {
1448 const StringRegion
*S
= cast
<StringRegion
>(MRV
->getRegion());
1450 // Treat the string as a lazy compound value.
1451 nonloc::LazyCompoundVal LCV
=
1452 cast
<nonloc::LazyCompoundVal
>(ValMgr
.makeLazyCompoundVal(store
, S
));
1453 return CopyLazyBindings(LCV
, store
, R
);
1456 // Handle lazy compound values.
1457 if (nonloc::LazyCompoundVal
*LCV
= dyn_cast
<nonloc::LazyCompoundVal
>(&Init
))
1458 return CopyLazyBindings(*LCV
, store
, R
);
1460 // Remaining case: explicit compound values.
1462 if (Init
.isUnknown())
1463 return setImplicitDefaultValue(store
, R
, ElementTy
);
1465 nonloc::CompoundVal
& CV
= cast
<nonloc::CompoundVal
>(Init
);
1466 nonloc::CompoundVal::iterator VI
= CV
.begin(), VE
= CV
.end();
1469 for (; Size
.hasValue() ? i
< Size
.getValue() : true ; ++i
, ++VI
) {
1470 // The init list might be shorter than the array length.
1474 const NonLoc
&Idx
= ValMgr
.makeArrayIndex(i
);
1475 const ElementRegion
*ER
= MRMgr
.getElementRegion(ElementTy
, Idx
, R
, Ctx
);
1477 if (ElementTy
->isStructureOrClassType())
1478 store
= BindStruct(store
, ER
, *VI
);
1479 else if (ElementTy
->isArrayType())
1480 store
= BindArray(store
, ER
, *VI
);
1482 store
= Bind(store
, ValMgr
.makeLoc(ER
), *VI
);
1485 // If the init list is shorter than the array length, set the
1486 // array default value.
1487 if (Size
.hasValue() && i
< Size
.getValue())
1488 store
= setImplicitDefaultValue(store
, R
, ElementTy
);
1493 Store
RegionStoreManager::BindStruct(Store store
, const TypedRegion
* R
,
1496 if (!Features
.supportsFields())
1499 QualType T
= R
->getValueType();
1500 assert(T
->isStructureOrClassType());
1502 const RecordType
* RT
= T
->getAs
<RecordType
>();
1503 RecordDecl
* RD
= RT
->getDecl();
1505 if (!RD
->isDefinition())
1508 // Handle lazy compound values.
1509 if (const nonloc::LazyCompoundVal
*LCV
=dyn_cast
<nonloc::LazyCompoundVal
>(&V
))
1510 return CopyLazyBindings(*LCV
, store
, R
);
1512 // We may get non-CompoundVal accidentally due to imprecise cast logic or
1513 // that we are binding symbolic struct value. Kill the field values, and if
1514 // the value is symbolic go and bind it as a "default" binding.
1515 if (V
.isUnknown() || !isa
<nonloc::CompoundVal
>(V
)) {
1516 SVal SV
= isa
<nonloc::SymbolVal
>(V
) ? V
: UnknownVal();
1517 return KillStruct(store
, R
, SV
);
1520 nonloc::CompoundVal
& CV
= cast
<nonloc::CompoundVal
>(V
);
1521 nonloc::CompoundVal::iterator VI
= CV
.begin(), VE
= CV
.end();
1523 RecordDecl::field_iterator FI
, FE
;
1525 for (FI
= RD
->field_begin(), FE
= RD
->field_end(); FI
!= FE
; ++FI
, ++VI
) {
1530 QualType FTy
= (*FI
)->getType();
1531 const FieldRegion
* FR
= MRMgr
.getFieldRegion(*FI
, R
);
1533 if (FTy
->isArrayType())
1534 store
= BindArray(store
, FR
, *VI
);
1535 else if (FTy
->isStructureOrClassType())
1536 store
= BindStruct(store
, FR
, *VI
);
1538 store
= Bind(store
, ValMgr
.makeLoc(FR
), *VI
);
1541 // There may be fewer values in the initialize list than the fields of struct.
1543 RegionBindings B
= GetRegionBindings(store
);
1544 B
= Add(B
, R
, BindingKey::Default
, ValMgr
.makeIntVal(0, false));
1545 store
= B
.getRoot();
1551 Store
RegionStoreManager::KillStruct(Store store
, const TypedRegion
* R
,
1553 RegionBindings B
= GetRegionBindings(store
);
1554 llvm::OwningPtr
<RegionStoreSubRegionMap
>
1555 SubRegions(getRegionStoreSubRegionMap(store
));
1556 RemoveSubRegionBindings(B
, R
, *SubRegions
);
1558 // Set the default value of the struct region to "unknown".
1559 return Add(B
, R
, BindingKey::Default
, DefaultVal
).getRoot();
1562 Store
RegionStoreManager::CopyLazyBindings(nonloc::LazyCompoundVal V
,
1563 Store store
, const TypedRegion
*R
) {
1565 // Nuke the old bindings stemming from R.
1566 RegionBindings B
= GetRegionBindings(store
);
1568 llvm::OwningPtr
<RegionStoreSubRegionMap
>
1569 SubRegions(getRegionStoreSubRegionMap(store
));
1571 // B and DVM are updated after the call to RemoveSubRegionBindings.
1572 RemoveSubRegionBindings(B
, R
, *SubRegions
.get());
1574 // Now copy the bindings. This amounts to just binding 'V' to 'R'. This
1575 // results in a zero-copy algorithm.
1576 return Add(B
, R
, BindingKey::Direct
, V
).getRoot();
1579 //===----------------------------------------------------------------------===//
1580 // "Raw" retrievals and bindings.
1581 //===----------------------------------------------------------------------===//
1584 RegionBindings
RegionStoreManager::Add(RegionBindings B
, BindingKey K
, SVal V
) {
1587 return RBFactory
.Add(B
, K
, V
);
1590 RegionBindings
RegionStoreManager::Add(RegionBindings B
, const MemRegion
*R
,
1591 BindingKey::Kind k
, SVal V
) {
1592 return Add(B
, BindingKey::Make(R
, k
), V
);
1595 const SVal
*RegionStoreManager::Lookup(RegionBindings B
, BindingKey K
) {
1601 const SVal
*RegionStoreManager::Lookup(RegionBindings B
,
1603 BindingKey::Kind k
) {
1604 return Lookup(B
, BindingKey::Make(R
, k
));
1607 RegionBindings
RegionStoreManager::Remove(RegionBindings B
, BindingKey K
) {
1610 return RBFactory
.Remove(B
, K
);
1613 RegionBindings
RegionStoreManager::Remove(RegionBindings B
, const MemRegion
*R
,
1614 BindingKey::Kind k
){
1615 return Remove(B
, BindingKey::Make(R
, k
));
1618 //===----------------------------------------------------------------------===//
1620 //===----------------------------------------------------------------------===//
1623 class RemoveDeadBindingsWorker
:
1624 public ClusterAnalysis
<RemoveDeadBindingsWorker
> {
1625 llvm::SmallVector
<const SymbolicRegion
*, 12> Postponed
;
1626 SymbolReaper
&SymReaper
;
1627 const StackFrameContext
*CurrentLCtx
;
1630 RemoveDeadBindingsWorker(RegionStoreManager
&rm
, GRStateManager
&stateMgr
,
1631 RegionBindings b
, SymbolReaper
&symReaper
,
1632 const StackFrameContext
*LCtx
)
1633 : ClusterAnalysis
<RemoveDeadBindingsWorker
>(rm
, stateMgr
, b
,
1634 /* includeGlobals = */ false),
1635 SymReaper(symReaper
), CurrentLCtx(LCtx
) {}
1637 // Called by ClusterAnalysis.
1638 void VisitAddedToCluster(const MemRegion
*baseR
, RegionCluster
&C
);
1639 void VisitCluster(const MemRegion
*baseR
, BindingKey
*I
, BindingKey
*E
);
1641 void VisitBindingKey(BindingKey K
);
1642 bool UpdatePostponed();
1643 void VisitBinding(SVal V
);
1647 void RemoveDeadBindingsWorker::VisitAddedToCluster(const MemRegion
*baseR
,
1650 if (const VarRegion
*VR
= dyn_cast
<VarRegion
>(baseR
)) {
1651 if (SymReaper
.isLive(VR
))
1652 AddToWorkList(baseR
, C
);
1657 if (const SymbolicRegion
*SR
= dyn_cast
<SymbolicRegion
>(baseR
)) {
1658 if (SymReaper
.isLive(SR
->getSymbol()))
1659 AddToWorkList(SR
, C
);
1661 Postponed
.push_back(SR
);
1666 if (isa
<NonStaticGlobalSpaceRegion
>(baseR
)) {
1667 AddToWorkList(baseR
, C
);
1671 // CXXThisRegion in the current or parent location context is live.
1672 if (const CXXThisRegion
*TR
= dyn_cast
<CXXThisRegion
>(baseR
)) {
1673 const StackArgumentsSpaceRegion
*StackReg
=
1674 cast
<StackArgumentsSpaceRegion
>(TR
->getSuperRegion());
1675 const StackFrameContext
*RegCtx
= StackReg
->getStackFrame();
1676 if (RegCtx
== CurrentLCtx
|| RegCtx
->isParentOf(CurrentLCtx
))
1677 AddToWorkList(TR
, C
);
1681 void RemoveDeadBindingsWorker::VisitCluster(const MemRegion
*baseR
,
1682 BindingKey
*I
, BindingKey
*E
) {
1683 for ( ; I
!= E
; ++I
)
1684 VisitBindingKey(*I
);
1687 void RemoveDeadBindingsWorker::VisitBinding(SVal V
) {
1688 // Is it a LazyCompoundVal? All referenced regions are live as well.
1689 if (const nonloc::LazyCompoundVal
*LCS
=
1690 dyn_cast
<nonloc::LazyCompoundVal
>(&V
)) {
1692 const MemRegion
*LazyR
= LCS
->getRegion();
1693 RegionBindings B
= RegionStoreManager::GetRegionBindings(LCS
->getStore());
1694 for (RegionBindings::iterator RI
= B
.begin(), RE
= B
.end(); RI
!= RE
; ++RI
){
1695 const SubRegion
*baseR
= dyn_cast
<SubRegion
>(RI
.getKey().getRegion());
1696 if (baseR
&& baseR
->isSubRegionOf(LazyR
))
1697 VisitBinding(RI
.getData());
1702 // If V is a region, then add it to the worklist.
1703 if (const MemRegion
*R
= V
.getAsRegion())
1706 // Update the set of live symbols.
1707 for (SVal::symbol_iterator SI
=V
.symbol_begin(), SE
=V
.symbol_end();
1709 SymReaper
.markLive(*SI
);
1712 void RemoveDeadBindingsWorker::VisitBindingKey(BindingKey K
) {
1713 const MemRegion
*R
= K
.getRegion();
1715 // Mark this region "live" by adding it to the worklist. This will cause
1716 // use to visit all regions in the cluster (if we haven't visited them
1718 if (AddToWorkList(R
)) {
1719 // Mark the symbol for any live SymbolicRegion as "live". This means we
1720 // should continue to track that symbol.
1721 if (const SymbolicRegion
*SymR
= dyn_cast
<SymbolicRegion
>(R
))
1722 SymReaper
.markLive(SymR
->getSymbol());
1724 // For BlockDataRegions, enqueue the VarRegions for variables marked
1725 // with __block (passed-by-reference).
1726 // via BlockDeclRefExprs.
1727 if (const BlockDataRegion
*BD
= dyn_cast
<BlockDataRegion
>(R
)) {
1728 for (BlockDataRegion::referenced_vars_iterator
1729 RI
= BD
->referenced_vars_begin(), RE
= BD
->referenced_vars_end();
1731 if ((*RI
)->getDecl()->getAttr
<BlocksAttr
>())
1735 // No possible data bindings on a BlockDataRegion.
1740 // Visit the data binding for K.
1741 if (const SVal
*V
= RM
.Lookup(B
, K
))
1745 bool RemoveDeadBindingsWorker::UpdatePostponed() {
1746 // See if any postponed SymbolicRegions are actually live now, after
1747 // having done a scan.
1748 bool changed
= false;
1750 for (llvm::SmallVectorImpl
<const SymbolicRegion
*>::iterator
1751 I
= Postponed
.begin(), E
= Postponed
.end() ; I
!= E
; ++I
) {
1752 if (const SymbolicRegion
*SR
= cast_or_null
<SymbolicRegion
>(*I
)) {
1753 if (SymReaper
.isLive(SR
->getSymbol())) {
1754 changed
|= AddToWorkList(SR
);
1763 Store
RegionStoreManager::RemoveDeadBindings(Store store
,
1764 const StackFrameContext
*LCtx
,
1765 SymbolReaper
& SymReaper
,
1766 llvm::SmallVectorImpl
<const MemRegion
*>& RegionRoots
)
1768 RegionBindings B
= GetRegionBindings(store
);
1769 RemoveDeadBindingsWorker
W(*this, StateMgr
, B
, SymReaper
, LCtx
);
1770 W
.GenerateClusters();
1772 // Enqueue the region roots onto the worklist.
1773 for (llvm::SmallVectorImpl
<const MemRegion
*>::iterator I
=RegionRoots
.begin(),
1774 E
=RegionRoots
.end(); I
!=E
; ++I
)
1775 W
.AddToWorkList(*I
);
1777 do W
.RunWorkList(); while (W
.UpdatePostponed());
1779 // We have now scanned the store, marking reachable regions and symbols
1780 // as live. We now remove all the regions that are dead from the store
1781 // as well as update DSymbols with the set symbols that are now dead.
1782 for (RegionBindings::iterator I
= B
.begin(), E
= B
.end(); I
!= E
; ++I
) {
1783 const BindingKey
&K
= I
.getKey();
1785 // If the cluster has been visited, we know the region has been marked.
1786 if (W
.isVisited(K
.getRegion()))
1789 // Remove the dead entry.
1792 // Mark all non-live symbols that this binding references as dead.
1793 if (const SymbolicRegion
* SymR
= dyn_cast
<SymbolicRegion
>(K
.getRegion()))
1794 SymReaper
.maybeDead(SymR
->getSymbol());
1796 SVal X
= I
.getData();
1797 SVal::symbol_iterator SI
= X
.symbol_begin(), SE
= X
.symbol_end();
1798 for (; SI
!= SE
; ++SI
)
1799 SymReaper
.maybeDead(*SI
);
1806 Store
RegionStoreManager::EnterStackFrame(const GRState
*state
,
1807 const StackFrameContext
*frame
) {
1808 FunctionDecl
const *FD
= cast
<FunctionDecl
>(frame
->getDecl());
1809 FunctionDecl::param_const_iterator PI
= FD
->param_begin();
1810 Store store
= state
->getStore();
1812 if (CallExpr
const *CE
= dyn_cast
<CallExpr
>(frame
->getCallSite())) {
1813 CallExpr::const_arg_iterator AI
= CE
->arg_begin(), AE
= CE
->arg_end();
1815 // Copy the arg expression value to the arg variables.
1816 for (; AI
!= AE
; ++AI
, ++PI
) {
1817 SVal ArgVal
= state
->getSVal(*AI
);
1818 store
= Bind(store
, ValMgr
.makeLoc(MRMgr
.getVarRegion(*PI
,frame
)),ArgVal
);
1820 } else if (const CXXConstructExpr
*CE
=
1821 dyn_cast
<CXXConstructExpr
>(frame
->getCallSite())) {
1822 CXXConstructExpr::const_arg_iterator AI
= CE
->arg_begin(),
1825 // Copy the arg expression value to the arg variables.
1826 for (; AI
!= AE
; ++AI
, ++PI
) {
1827 SVal ArgVal
= state
->getSVal(*AI
);
1828 store
= Bind(store
, ValMgr
.makeLoc(MRMgr
.getVarRegion(*PI
,frame
)),ArgVal
);
1831 llvm_unreachable("Unhandled call expression.");
1836 //===----------------------------------------------------------------------===//
1838 //===----------------------------------------------------------------------===//
1840 void RegionStoreManager::print(Store store
, llvm::raw_ostream
& OS
,
1841 const char* nl
, const char *sep
) {
1842 RegionBindings B
= GetRegionBindings(store
);
1843 OS
<< "Store (direct and default bindings):" << nl
;
1845 for (RegionBindings::iterator I
= B
.begin(), E
= B
.end(); I
!= E
; ++I
)
1846 OS
<< ' ' << I
.getKey() << " : " << I
.getData() << nl
;