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/StaticAnalyzer/PathSensitive/GRState.h"
24 #include "clang/StaticAnalyzer/PathSensitive/GRStateTrait.h"
25 #include "clang/StaticAnalyzer/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
;
35 //===----------------------------------------------------------------------===//
36 // Representation of binding keys.
37 //===----------------------------------------------------------------------===//
42 enum Kind
{ Direct
= 0x0, Default
= 0x1 };
44 llvm ::PointerIntPair
<const MemRegion
*, 1> P
;
47 explicit BindingKey(const MemRegion
*r
, uint64_t offset
, Kind k
)
48 : P(r
, (unsigned) k
), Offset(offset
) {}
51 bool isDirect() const { return P
.getInt() == Direct
; }
53 const MemRegion
*getRegion() const { return P
.getPointer(); }
54 uint64_t getOffset() const { return Offset
; }
56 void Profile(llvm::FoldingSetNodeID
& ID
) const {
57 ID
.AddPointer(P
.getOpaqueValue());
58 ID
.AddInteger(Offset
);
61 static BindingKey
Make(const MemRegion
*R
, Kind k
);
63 bool operator<(const BindingKey
&X
) const {
64 if (P
.getOpaqueValue() < X
.P
.getOpaqueValue())
66 if (P
.getOpaqueValue() > X
.P
.getOpaqueValue())
68 return Offset
< X
.Offset
;
71 bool operator==(const BindingKey
&X
) const {
72 return P
.getOpaqueValue() == X
.P
.getOpaqueValue() &&
76 bool isValid() const {
77 return getRegion() != NULL
;
80 } // end anonymous namespace
82 BindingKey
BindingKey::Make(const MemRegion
*R
, Kind k
) {
83 if (const ElementRegion
*ER
= dyn_cast
<ElementRegion
>(R
)) {
84 const RegionRawOffset
&O
= ER
->getAsArrayOffset();
86 // FIXME: There are some ElementRegions for which we cannot compute
87 // raw offsets yet, including regions with symbolic offsets. These will be
88 // ignored by the store.
89 return BindingKey(O
.getRegion(), O
.getByteOffset(), k
);
92 return BindingKey(R
, 0, k
);
97 llvm::raw_ostream
& operator<<(llvm::raw_ostream
& os
, BindingKey K
) {
98 os
<< '(' << K
.getRegion() << ',' << K
.getOffset()
99 << ',' << (K
.isDirect() ? "direct" : "default")
103 } // end llvm namespace
105 //===----------------------------------------------------------------------===//
106 // Actual Store type.
107 //===----------------------------------------------------------------------===//
109 typedef llvm::ImmutableMap
<BindingKey
, SVal
> RegionBindings
;
111 //===----------------------------------------------------------------------===//
112 // Fine-grained control of RegionStoreManager.
113 //===----------------------------------------------------------------------===//
116 struct minimal_features_tag
{};
117 struct maximal_features_tag
{};
119 class RegionStoreFeatures
{
122 RegionStoreFeatures(minimal_features_tag
) :
123 SupportsFields(false) {}
125 RegionStoreFeatures(maximal_features_tag
) :
126 SupportsFields(true) {}
128 void enableFields(bool t
) { SupportsFields
= t
; }
130 bool supportsFields() const { return SupportsFields
; }
134 //===----------------------------------------------------------------------===//
135 // Main RegionStore logic.
136 //===----------------------------------------------------------------------===//
140 class RegionStoreSubRegionMap
: public SubRegionMap
{
142 typedef llvm::ImmutableSet
<const MemRegion
*> Set
;
143 typedef llvm::DenseMap
<const MemRegion
*, Set
> Map
;
148 bool add(const MemRegion
* Parent
, const MemRegion
* SubRegion
) {
149 Map::iterator I
= M
.find(Parent
);
152 M
.insert(std::make_pair(Parent
, F
.add(F
.getEmptySet(), SubRegion
)));
156 I
->second
= F
.add(I
->second
, SubRegion
);
160 void process(llvm::SmallVectorImpl
<const SubRegion
*> &WL
, const SubRegion
*R
);
162 ~RegionStoreSubRegionMap() {}
164 const Set
*getSubRegions(const MemRegion
*Parent
) const {
165 Map::const_iterator I
= M
.find(Parent
);
166 return I
== M
.end() ? NULL
: &I
->second
;
169 bool iterSubRegions(const MemRegion
* Parent
, Visitor
& V
) const {
170 Map::const_iterator I
= M
.find(Parent
);
176 for (Set::iterator SI
=S
.begin(),SE
=S
.end(); SI
!= SE
; ++SI
) {
177 if (!V
.Visit(Parent
, *SI
))
186 RegionStoreSubRegionMap::process(llvm::SmallVectorImpl
<const SubRegion
*> &WL
,
187 const SubRegion
*R
) {
188 const MemRegion
*superR
= R
->getSuperRegion();
190 if (const SubRegion
*sr
= dyn_cast
<SubRegion
>(superR
))
194 class RegionStoreManager
: public StoreManager
{
195 const RegionStoreFeatures Features
;
196 RegionBindings::Factory RBFactory
;
199 RegionStoreManager(GRStateManager
& mgr
, const RegionStoreFeatures
&f
)
202 RBFactory(mgr
.getAllocator()) {}
204 SubRegionMap
*getSubRegionMap(Store store
) {
205 return getRegionStoreSubRegionMap(store
);
208 RegionStoreSubRegionMap
*getRegionStoreSubRegionMap(Store store
);
210 Optional
<SVal
> getDirectBinding(RegionBindings B
, const MemRegion
*R
);
211 /// getDefaultBinding - Returns an SVal* representing an optional default
212 /// binding associated with a region and its subregions.
213 Optional
<SVal
> getDefaultBinding(RegionBindings B
, const MemRegion
*R
);
215 /// setImplicitDefaultValue - Set the default binding for the provided
216 /// MemRegion to the value implicitly defined for compound literals when
217 /// the value is not specified.
218 Store
setImplicitDefaultValue(Store store
, const MemRegion
*R
, QualType T
);
220 /// ArrayToPointer - Emulates the "decay" of an array to a pointer
221 /// type. 'Array' represents the lvalue of the array being decayed
222 /// to a pointer, and the returned SVal represents the decayed
223 /// version of that lvalue (i.e., a pointer to the first element of
224 /// the array). This is called by ExprEngine when evaluating
225 /// casts from arrays to pointers.
226 SVal
ArrayToPointer(Loc Array
);
228 /// For DerivedToBase casts, create a CXXBaseObjectRegion and return it.
229 virtual SVal
evalDerivedToBase(SVal derived
, QualType basePtrType
);
231 SVal
evalBinOp(BinaryOperator::Opcode Op
,Loc L
, NonLoc R
, QualType resultTy
);
233 Store
getInitialStore(const LocationContext
*InitLoc
) {
234 return RBFactory
.getEmptyMap().getRoot();
237 //===-------------------------------------------------------------------===//
238 // Binding values to regions.
239 //===-------------------------------------------------------------------===//
241 Store
InvalidateRegions(Store store
,
242 const MemRegion
* const *Begin
,
243 const MemRegion
* const *End
,
244 const Expr
*E
, unsigned Count
,
245 InvalidatedSymbols
*IS
,
246 bool invalidateGlobals
,
247 InvalidatedRegions
*Regions
);
249 public: // Made public for helper classes.
251 void RemoveSubRegionBindings(RegionBindings
&B
, const MemRegion
*R
,
252 RegionStoreSubRegionMap
&M
);
254 RegionBindings
addBinding(RegionBindings B
, BindingKey K
, SVal V
);
256 RegionBindings
addBinding(RegionBindings B
, const MemRegion
*R
,
257 BindingKey::Kind k
, SVal V
);
259 const SVal
*lookup(RegionBindings B
, BindingKey K
);
260 const SVal
*lookup(RegionBindings B
, const MemRegion
*R
, BindingKey::Kind k
);
262 RegionBindings
removeBinding(RegionBindings B
, BindingKey K
);
263 RegionBindings
removeBinding(RegionBindings B
, const MemRegion
*R
,
266 RegionBindings
removeBinding(RegionBindings B
, const MemRegion
*R
) {
267 return removeBinding(removeBinding(B
, R
, BindingKey::Direct
), R
,
268 BindingKey::Default
);
271 public: // Part of public interface to class.
273 Store
Bind(Store store
, Loc LV
, SVal V
);
275 // BindDefault is only used to initialize a region with a default value.
276 Store
BindDefault(Store store
, const MemRegion
*R
, SVal V
) {
277 RegionBindings B
= GetRegionBindings(store
);
278 assert(!lookup(B
, R
, BindingKey::Default
));
279 assert(!lookup(B
, R
, BindingKey::Direct
));
280 return addBinding(B
, R
, BindingKey::Default
, V
).getRoot();
283 Store
BindCompoundLiteral(Store store
, const CompoundLiteralExpr
* CL
,
284 const LocationContext
*LC
, SVal V
);
286 Store
BindDecl(Store store
, const VarRegion
*VR
, SVal InitVal
);
288 Store
BindDeclWithNoInit(Store store
, const VarRegion
*) {
292 /// BindStruct - Bind a compound value to a structure.
293 Store
BindStruct(Store store
, const TypedRegion
* R
, SVal V
);
295 Store
BindArray(Store store
, const TypedRegion
* R
, SVal V
);
297 /// KillStruct - Set the entire struct to unknown.
298 Store
KillStruct(Store store
, const TypedRegion
* R
, SVal DefaultVal
);
300 Store
Remove(Store store
, Loc LV
);
303 //===------------------------------------------------------------------===//
304 // Loading values from regions.
305 //===------------------------------------------------------------------===//
307 /// The high level logic for this method is this:
310 /// return L's binding
311 /// else if L is in killset
314 /// if L is on stack or heap
318 SVal
Retrieve(Store store
, Loc L
, QualType T
= QualType());
320 SVal
RetrieveElement(Store store
, const ElementRegion
*R
);
322 SVal
RetrieveField(Store store
, const FieldRegion
*R
);
324 SVal
RetrieveObjCIvar(Store store
, const ObjCIvarRegion
*R
);
326 SVal
RetrieveVar(Store store
, const VarRegion
*R
);
328 SVal
RetrieveLazySymbol(const TypedRegion
*R
);
330 SVal
RetrieveFieldOrElementCommon(Store store
, const TypedRegion
*R
,
331 QualType Ty
, const MemRegion
*superR
);
333 /// Retrieve the values in a struct and return a CompoundVal, used when doing
337 /// y's value is retrieved by this method.
338 SVal
RetrieveStruct(Store store
, const TypedRegion
* R
);
340 SVal
RetrieveArray(Store store
, const TypedRegion
* R
);
342 /// Used to lazily generate derived symbols for bindings that are defined
343 /// implicitly by default bindings in a super region.
344 Optional
<SVal
> RetrieveDerivedDefaultValue(RegionBindings B
,
345 const MemRegion
*superR
,
346 const TypedRegion
*R
, QualType Ty
);
348 /// Get the state and region whose binding this region R corresponds to.
349 std::pair
<Store
, const MemRegion
*>
350 GetLazyBinding(RegionBindings B
, const MemRegion
*R
);
352 Store
CopyLazyBindings(nonloc::LazyCompoundVal V
, Store store
,
353 const TypedRegion
*R
);
355 //===------------------------------------------------------------------===//
357 //===------------------------------------------------------------------===//
359 /// RemoveDeadBindings - Scans the RegionStore of 'state' for dead values.
360 /// It returns a new Store with these values removed.
361 Store
RemoveDeadBindings(Store store
, const StackFrameContext
*LCtx
,
362 SymbolReaper
& SymReaper
,
363 llvm::SmallVectorImpl
<const MemRegion
*>& RegionRoots
);
365 Store
EnterStackFrame(const GRState
*state
, const StackFrameContext
*frame
);
367 //===------------------------------------------------------------------===//
369 //===------------------------------------------------------------------===//
371 // FIXME: This method will soon be eliminated; see the note in Store.h.
372 DefinedOrUnknownSVal
getSizeInElements(const GRState
*state
,
373 const MemRegion
* R
, QualType EleTy
);
375 //===------------------------------------------------------------------===//
377 //===------------------------------------------------------------------===//
379 static inline RegionBindings
GetRegionBindings(Store store
) {
380 return RegionBindings(static_cast<const RegionBindings::TreeTy
*>(store
));
383 void print(Store store
, llvm::raw_ostream
& Out
, const char* nl
,
386 void iterBindings(Store store
, BindingsHandler
& f
) {
387 RegionBindings B
= GetRegionBindings(store
);
388 for (RegionBindings::iterator I
=B
.begin(), E
=B
.end(); I
!=E
; ++I
) {
389 const BindingKey
&K
= I
.getKey();
392 if (const SubRegion
*R
= dyn_cast
<SubRegion
>(I
.getKey().getRegion())) {
393 // FIXME: Possibly incorporate the offset?
394 if (!f
.HandleBinding(*this, store
, R
, I
.getData()))
401 } // end anonymous namespace
403 //===----------------------------------------------------------------------===//
404 // RegionStore creation.
405 //===----------------------------------------------------------------------===//
407 StoreManager
*ento::CreateRegionStoreManager(GRStateManager
& StMgr
) {
408 RegionStoreFeatures F
= maximal_features_tag();
409 return new RegionStoreManager(StMgr
, F
);
412 StoreManager
*ento::CreateFieldsOnlyRegionStoreManager(GRStateManager
&StMgr
) {
413 RegionStoreFeatures F
= minimal_features_tag();
414 F
.enableFields(true);
415 return new RegionStoreManager(StMgr
, F
);
419 RegionStoreSubRegionMap
*
420 RegionStoreManager::getRegionStoreSubRegionMap(Store store
) {
421 RegionBindings B
= GetRegionBindings(store
);
422 RegionStoreSubRegionMap
*M
= new RegionStoreSubRegionMap();
424 llvm::SmallVector
<const SubRegion
*, 10> WL
;
426 for (RegionBindings::iterator I
=B
.begin(), E
=B
.end(); I
!=E
; ++I
)
427 if (const SubRegion
*R
= dyn_cast
<SubRegion
>(I
.getKey().getRegion()))
430 // We also need to record in the subregion map "intermediate" regions that
431 // don't have direct bindings but are super regions of those that do.
432 while (!WL
.empty()) {
433 const SubRegion
*R
= WL
.back();
441 //===----------------------------------------------------------------------===//
442 // Region Cluster analysis.
443 //===----------------------------------------------------------------------===//
446 template <typename DERIVED
>
447 class ClusterAnalysis
{
449 typedef BumpVector
<BindingKey
> RegionCluster
;
450 typedef llvm::DenseMap
<const MemRegion
*, RegionCluster
*> ClusterMap
;
451 llvm::DenseMap
<const RegionCluster
*, unsigned> Visited
;
452 typedef llvm::SmallVector
<std::pair
<const MemRegion
*, RegionCluster
*>, 10>
455 BumpVectorContext BVC
;
459 RegionStoreManager
&RM
;
461 SValBuilder
&svalBuilder
;
465 const bool includeGlobals
;
468 ClusterAnalysis(RegionStoreManager
&rm
, GRStateManager
&StateMgr
,
469 RegionBindings b
, const bool includeGlobals
)
470 : RM(rm
), Ctx(StateMgr
.getContext()),
471 svalBuilder(StateMgr
.getSValBuilder()),
472 B(b
), includeGlobals(includeGlobals
) {}
474 RegionBindings
getRegionBindings() const { return B
; }
476 RegionCluster
&AddToCluster(BindingKey K
) {
477 const MemRegion
*R
= K
.getRegion();
478 const MemRegion
*baseR
= R
->getBaseRegion();
479 RegionCluster
&C
= getCluster(baseR
);
481 static_cast<DERIVED
*>(this)->VisitAddedToCluster(baseR
, C
);
485 bool isVisited(const MemRegion
*R
) {
486 return (bool) Visited
[&getCluster(R
->getBaseRegion())];
489 RegionCluster
& getCluster(const MemRegion
*R
) {
490 RegionCluster
*&CRef
= ClusterM
[R
];
492 void *Mem
= BVC
.getAllocator().template Allocate
<RegionCluster
>();
493 CRef
= new (Mem
) RegionCluster(BVC
, 10);
498 void GenerateClusters() {
499 // Scan the entire set of bindings and make the region clusters.
500 for (RegionBindings::iterator RI
= B
.begin(), RE
= B
.end(); RI
!= RE
; ++RI
){
501 RegionCluster
&C
= AddToCluster(RI
.getKey());
502 if (const MemRegion
*R
= RI
.getData().getAsRegion()) {
503 // Generate a cluster, but don't add the region to the cluster
504 // if there aren't any bindings.
505 getCluster(R
->getBaseRegion());
507 if (includeGlobals
) {
508 const MemRegion
*R
= RI
.getKey().getRegion();
509 if (isa
<NonStaticGlobalSpaceRegion
>(R
->getMemorySpace()))
515 bool AddToWorkList(const MemRegion
*R
, RegionCluster
&C
) {
516 if (unsigned &visited
= Visited
[&C
])
521 WL
.push_back(std::make_pair(R
, &C
));
525 bool AddToWorkList(BindingKey K
) {
526 return AddToWorkList(K
.getRegion());
529 bool AddToWorkList(const MemRegion
*R
) {
530 const MemRegion
*baseR
= R
->getBaseRegion();
531 return AddToWorkList(baseR
, getCluster(baseR
));
535 while (!WL
.empty()) {
536 const MemRegion
*baseR
;
538 llvm::tie(baseR
, C
) = WL
.back();
541 // First visit the cluster.
542 static_cast<DERIVED
*>(this)->VisitCluster(baseR
, C
->begin(), C
->end());
544 // Next, visit the base region.
545 static_cast<DERIVED
*>(this)->VisitBaseRegion(baseR
);
550 void VisitAddedToCluster(const MemRegion
*baseR
, RegionCluster
&C
) {}
551 void VisitCluster(const MemRegion
*baseR
, BindingKey
*I
, BindingKey
*E
) {}
552 void VisitBaseRegion(const MemRegion
*baseR
) {}
556 //===----------------------------------------------------------------------===//
557 // Binding invalidation.
558 //===----------------------------------------------------------------------===//
560 void RegionStoreManager::RemoveSubRegionBindings(RegionBindings
&B
,
562 RegionStoreSubRegionMap
&M
) {
564 if (const RegionStoreSubRegionMap::Set
*S
= M
.getSubRegions(R
))
565 for (RegionStoreSubRegionMap::Set::iterator I
= S
->begin(), E
= S
->end();
567 RemoveSubRegionBindings(B
, *I
, M
);
569 B
= removeBinding(B
, R
);
573 class InvalidateRegionsWorker
: public ClusterAnalysis
<InvalidateRegionsWorker
>
577 StoreManager::InvalidatedSymbols
*IS
;
578 StoreManager::InvalidatedRegions
*Regions
;
580 InvalidateRegionsWorker(RegionStoreManager
&rm
,
581 GRStateManager
&stateMgr
,
583 const Expr
*ex
, unsigned count
,
584 StoreManager::InvalidatedSymbols
*is
,
585 StoreManager::InvalidatedRegions
*r
,
587 : ClusterAnalysis
<InvalidateRegionsWorker
>(rm
, stateMgr
, b
, includeGlobals
),
588 Ex(ex
), Count(count
), IS(is
), Regions(r
) {}
590 void VisitCluster(const MemRegion
*baseR
, BindingKey
*I
, BindingKey
*E
);
591 void VisitBaseRegion(const MemRegion
*baseR
);
594 void VisitBinding(SVal V
);
598 void InvalidateRegionsWorker::VisitBinding(SVal V
) {
599 // A symbol? Mark it touched by the invalidation.
601 if (SymbolRef Sym
= V
.getAsSymbol())
604 if (const MemRegion
*R
= V
.getAsRegion()) {
609 // Is it a LazyCompoundVal? All references get invalidated as well.
610 if (const nonloc::LazyCompoundVal
*LCS
=
611 dyn_cast
<nonloc::LazyCompoundVal
>(&V
)) {
613 const MemRegion
*LazyR
= LCS
->getRegion();
614 RegionBindings B
= RegionStoreManager::GetRegionBindings(LCS
->getStore());
616 for (RegionBindings::iterator RI
= B
.begin(), RE
= B
.end(); RI
!= RE
; ++RI
){
617 const SubRegion
*baseR
= dyn_cast
<SubRegion
>(RI
.getKey().getRegion());
618 if (baseR
&& baseR
->isSubRegionOf(LazyR
))
619 VisitBinding(RI
.getData());
626 void InvalidateRegionsWorker::VisitCluster(const MemRegion
*baseR
,
627 BindingKey
*I
, BindingKey
*E
) {
628 for ( ; I
!= E
; ++I
) {
629 // Get the old binding. Is it a region? If so, add it to the worklist.
630 const BindingKey
&K
= *I
;
631 if (const SVal
*V
= RM
.lookup(B
, K
))
634 B
= RM
.removeBinding(B
, K
);
638 void InvalidateRegionsWorker::VisitBaseRegion(const MemRegion
*baseR
) {
640 // Symbolic region? Mark that symbol touched by the invalidation.
641 if (const SymbolicRegion
*SR
= dyn_cast
<SymbolicRegion
>(baseR
))
642 IS
->insert(SR
->getSymbol());
645 // BlockDataRegion? If so, invalidate captured variables that are passed
647 if (const BlockDataRegion
*BR
= dyn_cast
<BlockDataRegion
>(baseR
)) {
648 for (BlockDataRegion::referenced_vars_iterator
649 BI
= BR
->referenced_vars_begin(), BE
= BR
->referenced_vars_end() ;
651 const VarRegion
*VR
= *BI
;
652 const VarDecl
*VD
= VR
->getDecl();
653 if (VD
->getAttr
<BlocksAttr
>() || !VD
->hasLocalStorage())
659 // Otherwise, we have a normal data region. Record that we touched the region.
661 Regions
->push_back(baseR
);
663 if (isa
<AllocaRegion
>(baseR
) || isa
<SymbolicRegion
>(baseR
)) {
664 // Invalidate the region by setting its default value to
665 // conjured symbol. The type of the symbol is irrelavant.
666 DefinedOrUnknownSVal V
=
667 svalBuilder
.getConjuredSymbolVal(baseR
, Ex
, Ctx
.IntTy
, Count
);
668 B
= RM
.addBinding(B
, baseR
, BindingKey::Default
, V
);
672 if (!baseR
->isBoundable())
675 const TypedRegion
*TR
= cast
<TypedRegion
>(baseR
);
676 QualType T
= TR
->getValueType();
678 // Invalidate the binding.
679 if (T
->isStructureType()) {
680 // Invalidate the region by setting its default value to
681 // conjured symbol. The type of the symbol is irrelavant.
682 DefinedOrUnknownSVal V
= svalBuilder
.getConjuredSymbolVal(baseR
, Ex
, Ctx
.IntTy
,
684 B
= RM
.addBinding(B
, baseR
, BindingKey::Default
, V
);
688 if (const ArrayType
*AT
= Ctx
.getAsArrayType(T
)) {
689 // Set the default value of the array to conjured symbol.
690 DefinedOrUnknownSVal V
=
691 svalBuilder
.getConjuredSymbolVal(baseR
, Ex
, AT
->getElementType(), Count
);
692 B
= RM
.addBinding(B
, baseR
, BindingKey::Default
, V
);
696 if (includeGlobals
&&
697 isa
<NonStaticGlobalSpaceRegion
>(baseR
->getMemorySpace())) {
698 // If the region is a global and we are invalidating all globals,
699 // just erase the entry. This causes all globals to be lazily
700 // symbolicated from the same base symbol.
701 B
= RM
.removeBinding(B
, baseR
);
706 DefinedOrUnknownSVal V
= svalBuilder
.getConjuredSymbolVal(baseR
, Ex
, T
, Count
);
707 assert(SymbolManager::canSymbolicate(T
) || V
.isUnknown());
708 B
= RM
.addBinding(B
, baseR
, BindingKey::Direct
, V
);
711 Store
RegionStoreManager::InvalidateRegions(Store store
,
712 const MemRegion
* const *I
,
713 const MemRegion
* const *E
,
714 const Expr
*Ex
, unsigned Count
,
715 InvalidatedSymbols
*IS
,
716 bool invalidateGlobals
,
717 InvalidatedRegions
*Regions
) {
718 InvalidateRegionsWorker
W(*this, StateMgr
,
719 RegionStoreManager::GetRegionBindings(store
),
720 Ex
, Count
, IS
, Regions
, invalidateGlobals
);
722 // Scan the bindings and generate the clusters.
723 W
.GenerateClusters();
725 // Add I .. E to the worklist.
731 // Return the new bindings.
732 RegionBindings B
= W
.getRegionBindings();
734 if (invalidateGlobals
) {
735 // Bind the non-static globals memory space to a new symbol that we will
736 // use to derive the bindings for all non-static globals.
737 const GlobalsSpaceRegion
*GS
= MRMgr
.getGlobalsRegion();
739 svalBuilder
.getConjuredSymbolVal(/* SymbolTag = */ (void*) GS
, Ex
,
740 /* symbol type, doesn't matter */ Ctx
.IntTy
,
742 B
= addBinding(B
, BindingKey::Make(GS
, BindingKey::Default
), V
);
744 // Even if there are no bindings in the global scope, we still need to
745 // record that we touched it.
747 Regions
->push_back(GS
);
753 //===----------------------------------------------------------------------===//
754 // Extents for regions.
755 //===----------------------------------------------------------------------===//
757 DefinedOrUnknownSVal
RegionStoreManager::getSizeInElements(const GRState
*state
,
760 SVal Size
= cast
<SubRegion
>(R
)->getExtent(svalBuilder
);
761 const llvm::APSInt
*SizeInt
= svalBuilder
.getKnownValue(state
, Size
);
765 CharUnits RegionSize
= CharUnits::fromQuantity(SizeInt
->getSExtValue());
767 if (Ctx
.getAsVariableArrayType(EleTy
)) {
768 // FIXME: We need to track extra state to properly record the size
769 // of VLAs. Returning UnknownVal here, however, is a stop-gap so that
770 // we don't have a divide-by-zero below.
774 CharUnits EleSize
= Ctx
.getTypeSizeInChars(EleTy
);
776 // If a variable is reinterpreted as a type that doesn't fit into a larger
777 // type evenly, round it down.
778 // This is a signed value, since it's used in arithmetic with signed indices.
779 return svalBuilder
.makeIntVal(RegionSize
/ EleSize
, false);
782 //===----------------------------------------------------------------------===//
783 // Location and region casting.
784 //===----------------------------------------------------------------------===//
786 /// ArrayToPointer - Emulates the "decay" of an array to a pointer
787 /// type. 'Array' represents the lvalue of the array being decayed
788 /// to a pointer, and the returned SVal represents the decayed
789 /// version of that lvalue (i.e., a pointer to the first element of
790 /// the array). This is called by ExprEngine when evaluating casts
791 /// from arrays to pointers.
792 SVal
RegionStoreManager::ArrayToPointer(Loc Array
) {
793 if (!isa
<loc::MemRegionVal
>(Array
))
796 const MemRegion
* R
= cast
<loc::MemRegionVal
>(&Array
)->getRegion();
797 const TypedRegion
* ArrayR
= dyn_cast
<TypedRegion
>(R
);
802 // Strip off typedefs from the ArrayRegion's ValueType.
803 QualType T
= ArrayR
->getValueType().getDesugaredType(Ctx
);
804 ArrayType
*AT
= cast
<ArrayType
>(T
);
805 T
= AT
->getElementType();
807 NonLoc ZeroIdx
= svalBuilder
.makeZeroArrayIndex();
808 return loc::MemRegionVal(MRMgr
.getElementRegion(T
, ZeroIdx
, ArrayR
, Ctx
));
811 SVal
RegionStoreManager::evalDerivedToBase(SVal derived
, QualType baseType
) {
812 const CXXRecordDecl
*baseDecl
;
813 if (baseType
->isPointerType())
814 baseDecl
= baseType
->getCXXRecordDeclForPointerType();
816 baseDecl
= baseType
->getAsCXXRecordDecl();
818 assert(baseDecl
&& "not a CXXRecordDecl?");
820 loc::MemRegionVal
*derivedRegVal
= dyn_cast
<loc::MemRegionVal
>(&derived
);
824 const MemRegion
*baseReg
=
825 MRMgr
.getCXXBaseObjectRegion(baseDecl
, derivedRegVal
->getRegion());
826 return loc::MemRegionVal(baseReg
);
828 //===----------------------------------------------------------------------===//
829 // Pointer arithmetic.
830 //===----------------------------------------------------------------------===//
832 SVal
RegionStoreManager::evalBinOp(BinaryOperator::Opcode Op
, Loc L
, NonLoc R
,
834 // Assume the base location is MemRegionVal.
835 if (!isa
<loc::MemRegionVal
>(L
))
838 // Special case for zero RHS.
839 if (R
.isZeroConstant()) {
842 // Handle it normally.
846 // FIXME: does this need to be casted to match resultTy?
851 const MemRegion
* MR
= cast
<loc::MemRegionVal
>(L
).getRegion();
852 const ElementRegion
*ER
= 0;
854 switch (MR
->getKind()) {
855 case MemRegion::SymbolicRegionKind
: {
856 const SymbolicRegion
*SR
= cast
<SymbolicRegion
>(MR
);
857 SymbolRef Sym
= SR
->getSymbol();
858 QualType T
= Sym
->getType(Ctx
);
861 if (const PointerType
*PT
= T
->getAs
<PointerType
>())
862 EleTy
= PT
->getPointeeType();
864 EleTy
= T
->getAs
<ObjCObjectPointerType
>()->getPointeeType();
866 const NonLoc
&ZeroIdx
= svalBuilder
.makeZeroArrayIndex();
867 ER
= MRMgr
.getElementRegion(EleTy
, ZeroIdx
, SR
, Ctx
);
870 case MemRegion::AllocaRegionKind
: {
871 const AllocaRegion
*AR
= cast
<AllocaRegion
>(MR
);
872 QualType EleTy
= Ctx
.CharTy
; // Create an ElementRegion of bytes.
873 NonLoc ZeroIdx
= svalBuilder
.makeZeroArrayIndex();
874 ER
= MRMgr
.getElementRegion(EleTy
, ZeroIdx
, AR
, Ctx
);
878 case MemRegion::ElementRegionKind
: {
879 ER
= cast
<ElementRegion
>(MR
);
884 case MemRegion::VarRegionKind
:
885 case MemRegion::StringRegionKind
: {
889 case MemRegion::CompoundLiteralRegionKind
:
890 case MemRegion::FieldRegionKind
:
891 case MemRegion::ObjCIvarRegionKind
:
892 case MemRegion::CXXTempObjectRegionKind
:
893 case MemRegion::CXXBaseObjectRegionKind
:
896 case MemRegion::FunctionTextRegionKind
:
897 case MemRegion::BlockTextRegionKind
:
898 case MemRegion::BlockDataRegionKind
:
899 // Technically this can happen if people do funny things with casts.
902 case MemRegion::CXXThisRegionKind
:
904 "Cannot perform pointer arithmetic on implicit argument 'this'");
905 case MemRegion::GenericMemSpaceRegionKind
:
906 case MemRegion::StackLocalsSpaceRegionKind
:
907 case MemRegion::StackArgumentsSpaceRegionKind
:
908 case MemRegion::HeapSpaceRegionKind
:
909 case MemRegion::NonStaticGlobalSpaceRegionKind
:
910 case MemRegion::StaticGlobalSpaceRegionKind
:
911 case MemRegion::UnknownSpaceRegionKind
:
912 assert(0 && "Cannot perform pointer arithmetic on a MemSpace");
916 SVal Idx
= ER
->getIndex();
917 nonloc::ConcreteInt
* Base
= dyn_cast
<nonloc::ConcreteInt
>(&Idx
);
919 // For now, only support:
920 // (a) concrete integer indices that can easily be resolved
921 // (b) 0 + symbolic index
923 if (nonloc::ConcreteInt
*Offset
= dyn_cast
<nonloc::ConcreteInt
>(&R
)) {
924 // FIXME: Should use SValBuilder here.
926 Base
->evalBinOp(svalBuilder
, Op
,
927 cast
<nonloc::ConcreteInt
>(svalBuilder
.convertToArrayIndex(*Offset
)));
929 if (!isa
<NonLoc
>(NewIdx
))
932 const MemRegion
* NewER
=
933 MRMgr
.getElementRegion(ER
->getElementType(), cast
<NonLoc
>(NewIdx
),
934 ER
->getSuperRegion(), Ctx
);
935 return svalBuilder
.makeLoc(NewER
);
937 if (0 == Base
->getValue()) {
938 const MemRegion
* NewER
=
939 MRMgr
.getElementRegion(ER
->getElementType(), R
,
940 ER
->getSuperRegion(), Ctx
);
941 return svalBuilder
.makeLoc(NewER
);
948 //===----------------------------------------------------------------------===//
949 // Loading values from regions.
950 //===----------------------------------------------------------------------===//
952 Optional
<SVal
> RegionStoreManager::getDirectBinding(RegionBindings B
,
953 const MemRegion
*R
) {
955 if (const SVal
*V
= lookup(B
, R
, BindingKey::Direct
))
958 return Optional
<SVal
>();
961 Optional
<SVal
> RegionStoreManager::getDefaultBinding(RegionBindings B
,
962 const MemRegion
*R
) {
963 if (R
->isBoundable())
964 if (const TypedRegion
*TR
= dyn_cast
<TypedRegion
>(R
))
965 if (TR
->getValueType()->isUnionType())
968 if (const SVal
*V
= lookup(B
, R
, BindingKey::Default
))
971 return Optional
<SVal
>();
974 SVal
RegionStoreManager::Retrieve(Store store
, Loc L
, QualType T
) {
975 assert(!isa
<UnknownVal
>(L
) && "location unknown");
976 assert(!isa
<UndefinedVal
>(L
) && "location undefined");
978 // For access to concrete addresses, return UnknownVal. Checks
979 // for null dereferences (and similar errors) are done by checkers, not
981 // FIXME: We can consider lazily symbolicating such memory, but we really
982 // should defer this when we can reason easily about symbolicating arrays
984 if (isa
<loc::ConcreteInt
>(L
)) {
988 const MemRegion
*MR
= cast
<loc::MemRegionVal
>(L
).getRegion();
990 if (isa
<AllocaRegion
>(MR
) || isa
<SymbolicRegion
>(MR
)) {
992 const SymbolicRegion
*SR
= cast
<SymbolicRegion
>(MR
);
993 T
= SR
->getSymbol()->getType(Ctx
);
995 MR
= GetElementZeroRegion(MR
, T
);
998 if (isa
<CodeTextRegion
>(MR
)) {
999 assert(0 && "Why load from a code text region?");
1000 return UnknownVal();
1003 // FIXME: Perhaps this method should just take a 'const MemRegion*' argument
1004 // instead of 'Loc', and have the other Loc cases handled at a higher level.
1005 const TypedRegion
*R
= cast
<TypedRegion
>(MR
);
1006 QualType RTy
= R
->getValueType();
1008 // FIXME: We should eventually handle funny addressing. e.g.:
1012 // char *q = (char*) p;
1013 // char c = *q; // returns the first byte of 'x'.
1015 // Such funny addressing will occur due to layering of regions.
1017 if (RTy
->isStructureOrClassType())
1018 return RetrieveStruct(store
, R
);
1020 // FIXME: Handle unions.
1021 if (RTy
->isUnionType())
1022 return UnknownVal();
1024 if (RTy
->isArrayType())
1025 return RetrieveArray(store
, R
);
1027 // FIXME: handle Vector types.
1028 if (RTy
->isVectorType())
1029 return UnknownVal();
1031 if (const FieldRegion
* FR
= dyn_cast
<FieldRegion
>(R
))
1032 return CastRetrievedVal(RetrieveField(store
, FR
), FR
, T
, false);
1034 if (const ElementRegion
* ER
= dyn_cast
<ElementRegion
>(R
)) {
1035 // FIXME: Here we actually perform an implicit conversion from the loaded
1036 // value to the element type. Eventually we want to compose these values
1037 // more intelligently. For example, an 'element' can encompass multiple
1038 // bound regions (e.g., several bound bytes), or could be a subset of
1040 return CastRetrievedVal(RetrieveElement(store
, ER
), ER
, T
, false);
1043 if (const ObjCIvarRegion
*IVR
= dyn_cast
<ObjCIvarRegion
>(R
)) {
1044 // FIXME: Here we actually perform an implicit conversion from the loaded
1045 // value to the ivar type. What we should model is stores to ivars
1046 // that blow past the extent of the ivar. If the address of the ivar is
1047 // reinterpretted, it is possible we stored a different value that could
1048 // fit within the ivar. Either we need to cast these when storing them
1049 // or reinterpret them lazily (as we do here).
1050 return CastRetrievedVal(RetrieveObjCIvar(store
, IVR
), IVR
, T
, false);
1053 if (const VarRegion
*VR
= dyn_cast
<VarRegion
>(R
)) {
1054 // FIXME: Here we actually perform an implicit conversion from the loaded
1055 // value to the variable type. What we should model is stores to variables
1056 // that blow past the extent of the variable. If the address of the
1057 // variable is reinterpretted, it is possible we stored a different value
1058 // that could fit within the variable. Either we need to cast these when
1059 // storing them or reinterpret them lazily (as we do here).
1060 return CastRetrievedVal(RetrieveVar(store
, VR
), VR
, T
, false);
1063 RegionBindings B
= GetRegionBindings(store
);
1064 const SVal
*V
= lookup(B
, R
, BindingKey::Direct
);
1066 // Check if the region has a binding.
1070 // The location does not have a bound value. This means that it has
1071 // the value it had upon its creation and/or entry to the analyzed
1072 // function/method. These are either symbolic values or 'undefined'.
1073 if (R
->hasStackNonParametersStorage()) {
1074 // All stack variables are considered to have undefined values
1075 // upon creation. All heap allocated blocks are considered to
1076 // have undefined values as well unless they are explicitly bound
1077 // to specific values.
1078 return UndefinedVal();
1081 // All other values are symbolic.
1082 return svalBuilder
.getRegionValueSymbolVal(R
);
1085 std::pair
<Store
, const MemRegion
*>
1086 RegionStoreManager::GetLazyBinding(RegionBindings B
, const MemRegion
*R
) {
1087 if (Optional
<SVal
> OV
= getDirectBinding(B
, R
))
1088 if (const nonloc::LazyCompoundVal
*V
=
1089 dyn_cast
<nonloc::LazyCompoundVal
>(OV
.getPointer()))
1090 return std::make_pair(V
->getStore(), V
->getRegion());
1092 if (const ElementRegion
*ER
= dyn_cast
<ElementRegion
>(R
)) {
1093 const std::pair
<Store
, const MemRegion
*> &X
=
1094 GetLazyBinding(B
, ER
->getSuperRegion());
1097 return std::make_pair(X
.first
,
1098 MRMgr
.getElementRegionWithSuper(ER
, X
.second
));
1100 else if (const FieldRegion
*FR
= dyn_cast
<FieldRegion
>(R
)) {
1101 const std::pair
<Store
, const MemRegion
*> &X
=
1102 GetLazyBinding(B
, FR
->getSuperRegion());
1105 return std::make_pair(X
.first
,
1106 MRMgr
.getFieldRegionWithSuper(FR
, X
.second
));
1108 // The NULL MemRegion indicates an non-existent lazy binding. A NULL Store is
1109 // possible for a valid lazy binding.
1110 return std::make_pair((Store
) 0, (const MemRegion
*) 0);
1113 SVal
RegionStoreManager::RetrieveElement(Store store
,
1114 const ElementRegion
* R
) {
1115 // Check if the region has a binding.
1116 RegionBindings B
= GetRegionBindings(store
);
1117 if (const Optional
<SVal
> &V
= getDirectBinding(B
, R
))
1120 const MemRegion
* superR
= R
->getSuperRegion();
1122 // Check if the region is an element region of a string literal.
1123 if (const StringRegion
*StrR
=dyn_cast
<StringRegion
>(superR
)) {
1124 // FIXME: Handle loads from strings where the literal is treated as
1125 // an integer, e.g., *((unsigned int*)"hello")
1126 QualType T
= Ctx
.getAsArrayType(StrR
->getValueType())->getElementType();
1127 if (T
!= Ctx
.getCanonicalType(R
->getElementType()))
1128 return UnknownVal();
1130 const StringLiteral
*Str
= StrR
->getStringLiteral();
1131 SVal Idx
= R
->getIndex();
1132 if (nonloc::ConcreteInt
*CI
= dyn_cast
<nonloc::ConcreteInt
>(&Idx
)) {
1133 int64_t i
= CI
->getValue().getSExtValue();
1134 int64_t byteLength
= Str
->getByteLength();
1135 // Technically, only i == byteLength is guaranteed to be null.
1136 // However, such overflows should be caught before reaching this point;
1137 // the only time such an access would be made is if a string literal was
1138 // used to initialize a larger array.
1139 char c
= (i
>= byteLength
) ? '\0' : Str
->getString()[i
];
1140 return svalBuilder
.makeIntVal(c
, T
);
1144 // Check for loads from a code text region. For such loads, just give up.
1145 if (isa
<CodeTextRegion
>(superR
))
1146 return UnknownVal();
1148 // Handle the case where we are indexing into a larger scalar object.
1149 // For example, this handles:
1153 // FIXME: This is a hack, and doesn't do anything really intelligent yet.
1154 const RegionRawOffset
&O
= R
->getAsArrayOffset();
1155 if (const TypedRegion
*baseR
= dyn_cast_or_null
<TypedRegion
>(O
.getRegion())) {
1156 QualType baseT
= baseR
->getValueType();
1157 if (baseT
->isScalarType()) {
1158 QualType elemT
= R
->getElementType();
1159 if (elemT
->isScalarType()) {
1160 if (Ctx
.getTypeSizeInChars(baseT
) >= Ctx
.getTypeSizeInChars(elemT
)) {
1161 if (const Optional
<SVal
> &V
= getDirectBinding(B
, superR
)) {
1162 if (SymbolRef parentSym
= V
->getAsSymbol())
1163 return svalBuilder
.getDerivedRegionValueSymbolVal(parentSym
, R
);
1165 if (V
->isUnknownOrUndef())
1167 // Other cases: give up. We are indexing into a larger object
1168 // that has some value, but we don't know how to handle that yet.
1169 return UnknownVal();
1175 return RetrieveFieldOrElementCommon(store
, R
, R
->getElementType(), superR
);
1178 SVal
RegionStoreManager::RetrieveField(Store store
,
1179 const FieldRegion
* R
) {
1181 // Check if the region has a binding.
1182 RegionBindings B
= GetRegionBindings(store
);
1183 if (const Optional
<SVal
> &V
= getDirectBinding(B
, R
))
1186 QualType Ty
= R
->getValueType();
1187 return RetrieveFieldOrElementCommon(store
, R
, Ty
, R
->getSuperRegion());
1191 RegionStoreManager::RetrieveDerivedDefaultValue(RegionBindings B
,
1192 const MemRegion
*superR
,
1193 const TypedRegion
*R
,
1196 if (const Optional
<SVal
> &D
= getDefaultBinding(B
, superR
)) {
1197 if (SymbolRef parentSym
= D
->getAsSymbol())
1198 return svalBuilder
.getDerivedRegionValueSymbolVal(parentSym
, R
);
1200 if (D
->isZeroConstant())
1201 return svalBuilder
.makeZeroVal(Ty
);
1203 if (D
->isUnknownOrUndef())
1206 assert(0 && "Unknown default value");
1209 return Optional
<SVal
>();
1212 SVal
RegionStoreManager::RetrieveFieldOrElementCommon(Store store
,
1213 const TypedRegion
*R
,
1215 const MemRegion
*superR
) {
1217 // At this point we have already checked in either RetrieveElement or
1218 // RetrieveField if 'R' has a direct binding.
1220 RegionBindings B
= GetRegionBindings(store
);
1223 if (const Optional
<SVal
> &D
=
1224 RetrieveDerivedDefaultValue(B
, superR
, R
, Ty
))
1227 // If our super region is a field or element itself, walk up the region
1228 // hierarchy to see if there is a default value installed in an ancestor.
1229 if (const SubRegion
*SR
= dyn_cast
<SubRegion
>(superR
)) {
1230 superR
= SR
->getSuperRegion();
1237 Store lazyBindingStore
= NULL
;
1238 const MemRegion
*lazyBindingRegion
= NULL
;
1239 llvm::tie(lazyBindingStore
, lazyBindingRegion
) = GetLazyBinding(B
, R
);
1241 if (lazyBindingRegion
) {
1242 if (const ElementRegion
*ER
= dyn_cast
<ElementRegion
>(lazyBindingRegion
))
1243 return RetrieveElement(lazyBindingStore
, ER
);
1244 return RetrieveField(lazyBindingStore
,
1245 cast
<FieldRegion
>(lazyBindingRegion
));
1248 if (R
->hasStackNonParametersStorage()) {
1249 if (const ElementRegion
*ER
= dyn_cast
<ElementRegion
>(R
)) {
1250 // Currently we don't reason specially about Clang-style vectors. Check
1251 // if superR is a vector and if so return Unknown.
1252 if (const TypedRegion
*typedSuperR
= dyn_cast
<TypedRegion
>(superR
)) {
1253 if (typedSuperR
->getValueType()->isVectorType())
1254 return UnknownVal();
1257 // FIXME: We also need to take ElementRegions with symbolic indexes into
1259 if (!ER
->getIndex().isConstant())
1260 return UnknownVal();
1263 return UndefinedVal();
1266 // All other values are symbolic.
1267 return svalBuilder
.getRegionValueSymbolVal(R
);
1270 SVal
RegionStoreManager::RetrieveObjCIvar(Store store
, const ObjCIvarRegion
* R
){
1272 // Check if the region has a binding.
1273 RegionBindings B
= GetRegionBindings(store
);
1275 if (const Optional
<SVal
> &V
= getDirectBinding(B
, R
))
1278 const MemRegion
*superR
= R
->getSuperRegion();
1280 // Check if the super region has a default binding.
1281 if (const Optional
<SVal
> &V
= getDefaultBinding(B
, superR
)) {
1282 if (SymbolRef parentSym
= V
->getAsSymbol())
1283 return svalBuilder
.getDerivedRegionValueSymbolVal(parentSym
, R
);
1285 // Other cases: give up.
1286 return UnknownVal();
1289 return RetrieveLazySymbol(R
);
1292 SVal
RegionStoreManager::RetrieveVar(Store store
, const VarRegion
*R
) {
1294 // Check if the region has a binding.
1295 RegionBindings B
= GetRegionBindings(store
);
1297 if (const Optional
<SVal
> &V
= getDirectBinding(B
, R
))
1300 // Lazily derive a value for the VarRegion.
1301 const VarDecl
*VD
= R
->getDecl();
1302 QualType T
= VD
->getType();
1303 const MemSpaceRegion
*MS
= R
->getMemorySpace();
1305 if (isa
<UnknownSpaceRegion
>(MS
) ||
1306 isa
<StackArgumentsSpaceRegion
>(MS
))
1307 return svalBuilder
.getRegionValueSymbolVal(R
);
1309 if (isa
<GlobalsSpaceRegion
>(MS
)) {
1310 if (isa
<NonStaticGlobalSpaceRegion
>(MS
)) {
1311 // Is 'VD' declared constant? If so, retrieve the constant value.
1312 QualType CT
= Ctx
.getCanonicalType(T
);
1313 if (CT
.isConstQualified()) {
1314 const Expr
*Init
= VD
->getInit();
1315 // Do the null check first, as we want to call 'IgnoreParenCasts'.
1317 if (const IntegerLiteral
*IL
=
1318 dyn_cast
<IntegerLiteral
>(Init
->IgnoreParenCasts())) {
1319 const nonloc::ConcreteInt
&V
= svalBuilder
.makeIntVal(IL
);
1320 return svalBuilder
.evalCast(V
, Init
->getType(), IL
->getType());
1324 if (const Optional
<SVal
> &V
= RetrieveDerivedDefaultValue(B
, MS
, R
, CT
))
1325 return V
.getValue();
1327 return svalBuilder
.getRegionValueSymbolVal(R
);
1330 if (T
->isIntegerType())
1331 return svalBuilder
.makeIntVal(0, T
);
1332 if (T
->isPointerType())
1333 return svalBuilder
.makeNull();
1335 return UnknownVal();
1338 return UndefinedVal();
1341 SVal
RegionStoreManager::RetrieveLazySymbol(const TypedRegion
*R
) {
1342 // All other values are symbolic.
1343 return svalBuilder
.getRegionValueSymbolVal(R
);
1346 SVal
RegionStoreManager::RetrieveStruct(Store store
, const TypedRegion
* R
) {
1347 QualType T
= R
->getValueType();
1348 assert(T
->isStructureOrClassType());
1349 return svalBuilder
.makeLazyCompoundVal(store
, R
);
1352 SVal
RegionStoreManager::RetrieveArray(Store store
, const TypedRegion
* R
) {
1353 assert(Ctx
.getAsConstantArrayType(R
->getValueType()));
1354 return svalBuilder
.makeLazyCompoundVal(store
, R
);
1357 //===----------------------------------------------------------------------===//
1358 // Binding values to regions.
1359 //===----------------------------------------------------------------------===//
1361 Store
RegionStoreManager::Remove(Store store
, Loc L
) {
1362 if (isa
<loc::MemRegionVal
>(L
))
1363 if (const MemRegion
* R
= cast
<loc::MemRegionVal
>(L
).getRegion())
1364 return removeBinding(GetRegionBindings(store
), R
).getRoot();
1369 Store
RegionStoreManager::Bind(Store store
, Loc L
, SVal V
) {
1370 if (isa
<loc::ConcreteInt
>(L
))
1373 // If we get here, the location should be a region.
1374 const MemRegion
*R
= cast
<loc::MemRegionVal
>(L
).getRegion();
1376 // Check if the region is a struct region.
1377 if (const TypedRegion
* TR
= dyn_cast
<TypedRegion
>(R
))
1378 if (TR
->getValueType()->isStructureOrClassType())
1379 return BindStruct(store
, TR
, V
);
1381 if (const ElementRegion
*ER
= dyn_cast
<ElementRegion
>(R
)) {
1382 if (ER
->getIndex().isZeroConstant()) {
1383 if (const TypedRegion
*superR
=
1384 dyn_cast
<TypedRegion
>(ER
->getSuperRegion())) {
1385 QualType superTy
= superR
->getValueType();
1386 // For now, just invalidate the fields of the struct/union/class.
1387 // This is for test rdar_test_7185607 in misc-ps-region-store.m.
1388 // FIXME: Precisely handle the fields of the record.
1389 if (superTy
->isStructureOrClassType())
1390 return KillStruct(store
, superR
, UnknownVal());
1394 else if (const SymbolicRegion
*SR
= dyn_cast
<SymbolicRegion
>(R
)) {
1395 // Binding directly to a symbolic region should be treated as binding
1397 QualType T
= SR
->getSymbol()->getType(Ctx
);
1399 // FIXME: Is this the right way to handle symbols that are references?
1400 if (const PointerType
*PT
= T
->getAs
<PointerType
>())
1401 T
= PT
->getPointeeType();
1403 T
= T
->getAs
<ReferenceType
>()->getPointeeType();
1405 R
= GetElementZeroRegion(SR
, T
);
1408 // Perform the binding.
1409 RegionBindings B
= GetRegionBindings(store
);
1410 return addBinding(B
, R
, BindingKey::Direct
, V
).getRoot();
1413 Store
RegionStoreManager::BindDecl(Store store
, const VarRegion
*VR
,
1416 QualType T
= VR
->getDecl()->getType();
1418 if (T
->isArrayType())
1419 return BindArray(store
, VR
, InitVal
);
1420 if (T
->isStructureOrClassType())
1421 return BindStruct(store
, VR
, InitVal
);
1423 return Bind(store
, svalBuilder
.makeLoc(VR
), InitVal
);
1426 // FIXME: this method should be merged into Bind().
1427 Store
RegionStoreManager::BindCompoundLiteral(Store store
,
1428 const CompoundLiteralExpr
*CL
,
1429 const LocationContext
*LC
,
1431 return Bind(store
, loc::MemRegionVal(MRMgr
.getCompoundLiteralRegion(CL
, LC
)),
1436 Store
RegionStoreManager::setImplicitDefaultValue(Store store
,
1439 RegionBindings B
= GetRegionBindings(store
);
1442 if (Loc::IsLocType(T
))
1443 V
= svalBuilder
.makeNull();
1444 else if (T
->isIntegerType())
1445 V
= svalBuilder
.makeZeroVal(T
);
1446 else if (T
->isStructureOrClassType() || T
->isArrayType()) {
1447 // Set the default value to a zero constant when it is a structure
1448 // or array. The type doesn't really matter.
1449 V
= svalBuilder
.makeZeroVal(Ctx
.IntTy
);
1455 return addBinding(B
, R
, BindingKey::Default
, V
).getRoot();
1458 Store
RegionStoreManager::BindArray(Store store
, const TypedRegion
* R
,
1461 const ArrayType
*AT
=cast
<ArrayType
>(Ctx
.getCanonicalType(R
->getValueType()));
1462 QualType ElementTy
= AT
->getElementType();
1463 Optional
<uint64_t> Size
;
1465 if (const ConstantArrayType
* CAT
= dyn_cast
<ConstantArrayType
>(AT
))
1466 Size
= CAT
->getSize().getZExtValue();
1468 // Check if the init expr is a string literal.
1469 if (loc::MemRegionVal
*MRV
= dyn_cast
<loc::MemRegionVal
>(&Init
)) {
1470 const StringRegion
*S
= cast
<StringRegion
>(MRV
->getRegion());
1472 // Treat the string as a lazy compound value.
1473 nonloc::LazyCompoundVal LCV
=
1474 cast
<nonloc::LazyCompoundVal
>(svalBuilder
.makeLazyCompoundVal(store
, S
));
1475 return CopyLazyBindings(LCV
, store
, R
);
1478 // Handle lazy compound values.
1479 if (nonloc::LazyCompoundVal
*LCV
= dyn_cast
<nonloc::LazyCompoundVal
>(&Init
))
1480 return CopyLazyBindings(*LCV
, store
, R
);
1482 // Remaining case: explicit compound values.
1484 if (Init
.isUnknown())
1485 return setImplicitDefaultValue(store
, R
, ElementTy
);
1487 nonloc::CompoundVal
& CV
= cast
<nonloc::CompoundVal
>(Init
);
1488 nonloc::CompoundVal::iterator VI
= CV
.begin(), VE
= CV
.end();
1491 for (; Size
.hasValue() ? i
< Size
.getValue() : true ; ++i
, ++VI
) {
1492 // The init list might be shorter than the array length.
1496 const NonLoc
&Idx
= svalBuilder
.makeArrayIndex(i
);
1497 const ElementRegion
*ER
= MRMgr
.getElementRegion(ElementTy
, Idx
, R
, Ctx
);
1499 if (ElementTy
->isStructureOrClassType())
1500 store
= BindStruct(store
, ER
, *VI
);
1501 else if (ElementTy
->isArrayType())
1502 store
= BindArray(store
, ER
, *VI
);
1504 store
= Bind(store
, svalBuilder
.makeLoc(ER
), *VI
);
1507 // If the init list is shorter than the array length, set the
1508 // array default value.
1509 if (Size
.hasValue() && i
< Size
.getValue())
1510 store
= setImplicitDefaultValue(store
, R
, ElementTy
);
1515 Store
RegionStoreManager::BindStruct(Store store
, const TypedRegion
* R
,
1518 if (!Features
.supportsFields())
1521 QualType T
= R
->getValueType();
1522 assert(T
->isStructureOrClassType());
1524 const RecordType
* RT
= T
->getAs
<RecordType
>();
1525 RecordDecl
* RD
= RT
->getDecl();
1527 if (!RD
->isDefinition())
1530 // Handle lazy compound values.
1531 if (const nonloc::LazyCompoundVal
*LCV
=dyn_cast
<nonloc::LazyCompoundVal
>(&V
))
1532 return CopyLazyBindings(*LCV
, store
, R
);
1534 // We may get non-CompoundVal accidentally due to imprecise cast logic or
1535 // that we are binding symbolic struct value. Kill the field values, and if
1536 // the value is symbolic go and bind it as a "default" binding.
1537 if (V
.isUnknown() || !isa
<nonloc::CompoundVal
>(V
)) {
1538 SVal SV
= isa
<nonloc::SymbolVal
>(V
) ? V
: UnknownVal();
1539 return KillStruct(store
, R
, SV
);
1542 nonloc::CompoundVal
& CV
= cast
<nonloc::CompoundVal
>(V
);
1543 nonloc::CompoundVal::iterator VI
= CV
.begin(), VE
= CV
.end();
1545 RecordDecl::field_iterator FI
, FE
;
1547 for (FI
= RD
->field_begin(), FE
= RD
->field_end(); FI
!= FE
; ++FI
, ++VI
) {
1552 QualType FTy
= (*FI
)->getType();
1553 const FieldRegion
* FR
= MRMgr
.getFieldRegion(*FI
, R
);
1555 if (FTy
->isArrayType())
1556 store
= BindArray(store
, FR
, *VI
);
1557 else if (FTy
->isStructureOrClassType())
1558 store
= BindStruct(store
, FR
, *VI
);
1560 store
= Bind(store
, svalBuilder
.makeLoc(FR
), *VI
);
1563 // There may be fewer values in the initialize list than the fields of struct.
1565 RegionBindings B
= GetRegionBindings(store
);
1566 B
= addBinding(B
, R
, BindingKey::Default
, svalBuilder
.makeIntVal(0, false));
1567 store
= B
.getRoot();
1573 Store
RegionStoreManager::KillStruct(Store store
, const TypedRegion
* R
,
1575 RegionBindings B
= GetRegionBindings(store
);
1576 llvm::OwningPtr
<RegionStoreSubRegionMap
>
1577 SubRegions(getRegionStoreSubRegionMap(store
));
1578 RemoveSubRegionBindings(B
, R
, *SubRegions
);
1580 // Set the default value of the struct region to "unknown".
1581 return addBinding(B
, R
, BindingKey::Default
, DefaultVal
).getRoot();
1584 Store
RegionStoreManager::CopyLazyBindings(nonloc::LazyCompoundVal V
,
1585 Store store
, const TypedRegion
*R
) {
1587 // Nuke the old bindings stemming from R.
1588 RegionBindings B
= GetRegionBindings(store
);
1590 llvm::OwningPtr
<RegionStoreSubRegionMap
>
1591 SubRegions(getRegionStoreSubRegionMap(store
));
1593 // B and DVM are updated after the call to RemoveSubRegionBindings.
1594 RemoveSubRegionBindings(B
, R
, *SubRegions
.get());
1596 // Now copy the bindings. This amounts to just binding 'V' to 'R'. This
1597 // results in a zero-copy algorithm.
1598 return addBinding(B
, R
, BindingKey::Direct
, V
).getRoot();
1601 //===----------------------------------------------------------------------===//
1602 // "Raw" retrievals and bindings.
1603 //===----------------------------------------------------------------------===//
1606 RegionBindings
RegionStoreManager::addBinding(RegionBindings B
, BindingKey K
,
1610 return RBFactory
.add(B
, K
, V
);
1613 RegionBindings
RegionStoreManager::addBinding(RegionBindings B
,
1615 BindingKey::Kind k
, SVal V
) {
1616 return addBinding(B
, BindingKey::Make(R
, k
), V
);
1619 const SVal
*RegionStoreManager::lookup(RegionBindings B
, BindingKey K
) {
1625 const SVal
*RegionStoreManager::lookup(RegionBindings B
,
1627 BindingKey::Kind k
) {
1628 return lookup(B
, BindingKey::Make(R
, k
));
1631 RegionBindings
RegionStoreManager::removeBinding(RegionBindings B
,
1635 return RBFactory
.remove(B
, K
);
1638 RegionBindings
RegionStoreManager::removeBinding(RegionBindings B
,
1640 BindingKey::Kind k
){
1641 return removeBinding(B
, BindingKey::Make(R
, k
));
1644 //===----------------------------------------------------------------------===//
1646 //===----------------------------------------------------------------------===//
1649 class RemoveDeadBindingsWorker
:
1650 public ClusterAnalysis
<RemoveDeadBindingsWorker
> {
1651 llvm::SmallVector
<const SymbolicRegion
*, 12> Postponed
;
1652 SymbolReaper
&SymReaper
;
1653 const StackFrameContext
*CurrentLCtx
;
1656 RemoveDeadBindingsWorker(RegionStoreManager
&rm
, GRStateManager
&stateMgr
,
1657 RegionBindings b
, SymbolReaper
&symReaper
,
1658 const StackFrameContext
*LCtx
)
1659 : ClusterAnalysis
<RemoveDeadBindingsWorker
>(rm
, stateMgr
, b
,
1660 /* includeGlobals = */ false),
1661 SymReaper(symReaper
), CurrentLCtx(LCtx
) {}
1663 // Called by ClusterAnalysis.
1664 void VisitAddedToCluster(const MemRegion
*baseR
, RegionCluster
&C
);
1665 void VisitCluster(const MemRegion
*baseR
, BindingKey
*I
, BindingKey
*E
);
1667 void VisitBindingKey(BindingKey K
);
1668 bool UpdatePostponed();
1669 void VisitBinding(SVal V
);
1673 void RemoveDeadBindingsWorker::VisitAddedToCluster(const MemRegion
*baseR
,
1676 if (const VarRegion
*VR
= dyn_cast
<VarRegion
>(baseR
)) {
1677 if (SymReaper
.isLive(VR
))
1678 AddToWorkList(baseR
, C
);
1683 if (const SymbolicRegion
*SR
= dyn_cast
<SymbolicRegion
>(baseR
)) {
1684 if (SymReaper
.isLive(SR
->getSymbol()))
1685 AddToWorkList(SR
, C
);
1687 Postponed
.push_back(SR
);
1692 if (isa
<NonStaticGlobalSpaceRegion
>(baseR
)) {
1693 AddToWorkList(baseR
, C
);
1697 // CXXThisRegion in the current or parent location context is live.
1698 if (const CXXThisRegion
*TR
= dyn_cast
<CXXThisRegion
>(baseR
)) {
1699 const StackArgumentsSpaceRegion
*StackReg
=
1700 cast
<StackArgumentsSpaceRegion
>(TR
->getSuperRegion());
1701 const StackFrameContext
*RegCtx
= StackReg
->getStackFrame();
1702 if (RegCtx
== CurrentLCtx
|| RegCtx
->isParentOf(CurrentLCtx
))
1703 AddToWorkList(TR
, C
);
1707 void RemoveDeadBindingsWorker::VisitCluster(const MemRegion
*baseR
,
1708 BindingKey
*I
, BindingKey
*E
) {
1709 for ( ; I
!= E
; ++I
)
1710 VisitBindingKey(*I
);
1713 void RemoveDeadBindingsWorker::VisitBinding(SVal V
) {
1714 // Is it a LazyCompoundVal? All referenced regions are live as well.
1715 if (const nonloc::LazyCompoundVal
*LCS
=
1716 dyn_cast
<nonloc::LazyCompoundVal
>(&V
)) {
1718 const MemRegion
*LazyR
= LCS
->getRegion();
1719 RegionBindings B
= RegionStoreManager::GetRegionBindings(LCS
->getStore());
1720 for (RegionBindings::iterator RI
= B
.begin(), RE
= B
.end(); RI
!= RE
; ++RI
){
1721 const SubRegion
*baseR
= dyn_cast
<SubRegion
>(RI
.getKey().getRegion());
1722 if (baseR
&& baseR
->isSubRegionOf(LazyR
))
1723 VisitBinding(RI
.getData());
1728 // If V is a region, then add it to the worklist.
1729 if (const MemRegion
*R
= V
.getAsRegion())
1732 // Update the set of live symbols.
1733 for (SVal::symbol_iterator SI
=V
.symbol_begin(), SE
=V
.symbol_end();
1735 SymReaper
.markLive(*SI
);
1738 void RemoveDeadBindingsWorker::VisitBindingKey(BindingKey K
) {
1739 const MemRegion
*R
= K
.getRegion();
1741 // Mark this region "live" by adding it to the worklist. This will cause
1742 // use to visit all regions in the cluster (if we haven't visited them
1744 if (AddToWorkList(R
)) {
1745 // Mark the symbol for any live SymbolicRegion as "live". This means we
1746 // should continue to track that symbol.
1747 if (const SymbolicRegion
*SymR
= dyn_cast
<SymbolicRegion
>(R
))
1748 SymReaper
.markLive(SymR
->getSymbol());
1750 // For BlockDataRegions, enqueue the VarRegions for variables marked
1751 // with __block (passed-by-reference).
1752 // via BlockDeclRefExprs.
1753 if (const BlockDataRegion
*BD
= dyn_cast
<BlockDataRegion
>(R
)) {
1754 for (BlockDataRegion::referenced_vars_iterator
1755 RI
= BD
->referenced_vars_begin(), RE
= BD
->referenced_vars_end();
1757 if ((*RI
)->getDecl()->getAttr
<BlocksAttr
>())
1761 // No possible data bindings on a BlockDataRegion.
1766 // Visit the data binding for K.
1767 if (const SVal
*V
= RM
.lookup(B
, K
))
1771 bool RemoveDeadBindingsWorker::UpdatePostponed() {
1772 // See if any postponed SymbolicRegions are actually live now, after
1773 // having done a scan.
1774 bool changed
= false;
1776 for (llvm::SmallVectorImpl
<const SymbolicRegion
*>::iterator
1777 I
= Postponed
.begin(), E
= Postponed
.end() ; I
!= E
; ++I
) {
1778 if (const SymbolicRegion
*SR
= cast_or_null
<SymbolicRegion
>(*I
)) {
1779 if (SymReaper
.isLive(SR
->getSymbol())) {
1780 changed
|= AddToWorkList(SR
);
1789 Store
RegionStoreManager::RemoveDeadBindings(Store store
,
1790 const StackFrameContext
*LCtx
,
1791 SymbolReaper
& SymReaper
,
1792 llvm::SmallVectorImpl
<const MemRegion
*>& RegionRoots
)
1794 RegionBindings B
= GetRegionBindings(store
);
1795 RemoveDeadBindingsWorker
W(*this, StateMgr
, B
, SymReaper
, LCtx
);
1796 W
.GenerateClusters();
1798 // Enqueue the region roots onto the worklist.
1799 for (llvm::SmallVectorImpl
<const MemRegion
*>::iterator I
=RegionRoots
.begin(),
1800 E
=RegionRoots
.end(); I
!=E
; ++I
)
1801 W
.AddToWorkList(*I
);
1803 do W
.RunWorkList(); while (W
.UpdatePostponed());
1805 // We have now scanned the store, marking reachable regions and symbols
1806 // as live. We now remove all the regions that are dead from the store
1807 // as well as update DSymbols with the set symbols that are now dead.
1808 for (RegionBindings::iterator I
= B
.begin(), E
= B
.end(); I
!= E
; ++I
) {
1809 const BindingKey
&K
= I
.getKey();
1811 // If the cluster has been visited, we know the region has been marked.
1812 if (W
.isVisited(K
.getRegion()))
1815 // Remove the dead entry.
1816 B
= removeBinding(B
, K
);
1818 // Mark all non-live symbols that this binding references as dead.
1819 if (const SymbolicRegion
* SymR
= dyn_cast
<SymbolicRegion
>(K
.getRegion()))
1820 SymReaper
.maybeDead(SymR
->getSymbol());
1822 SVal X
= I
.getData();
1823 SVal::symbol_iterator SI
= X
.symbol_begin(), SE
= X
.symbol_end();
1824 for (; SI
!= SE
; ++SI
)
1825 SymReaper
.maybeDead(*SI
);
1832 Store
RegionStoreManager::EnterStackFrame(const GRState
*state
,
1833 const StackFrameContext
*frame
) {
1834 FunctionDecl
const *FD
= cast
<FunctionDecl
>(frame
->getDecl());
1835 FunctionDecl::param_const_iterator PI
= FD
->param_begin();
1836 Store store
= state
->getStore();
1838 if (CallExpr
const *CE
= dyn_cast
<CallExpr
>(frame
->getCallSite())) {
1839 CallExpr::const_arg_iterator AI
= CE
->arg_begin(), AE
= CE
->arg_end();
1841 // Copy the arg expression value to the arg variables.
1842 for (; AI
!= AE
; ++AI
, ++PI
) {
1843 SVal ArgVal
= state
->getSVal(*AI
);
1845 svalBuilder
.makeLoc(MRMgr
.getVarRegion(*PI
,frame
)), ArgVal
);
1847 } else if (const CXXConstructExpr
*CE
=
1848 dyn_cast
<CXXConstructExpr
>(frame
->getCallSite())) {
1849 CXXConstructExpr::const_arg_iterator AI
= CE
->arg_begin(),
1852 // Copy the arg expression value to the arg variables.
1853 for (; AI
!= AE
; ++AI
, ++PI
) {
1854 SVal ArgVal
= state
->getSVal(*AI
);
1856 svalBuilder
.makeLoc(MRMgr
.getVarRegion(*PI
,frame
)), ArgVal
);
1859 assert(isa
<CXXDestructorDecl
>(frame
->getDecl()));
1864 //===----------------------------------------------------------------------===//
1866 //===----------------------------------------------------------------------===//
1868 void RegionStoreManager::print(Store store
, llvm::raw_ostream
& OS
,
1869 const char* nl
, const char *sep
) {
1870 RegionBindings B
= GetRegionBindings(store
);
1871 OS
<< "Store (direct and default bindings):" << nl
;
1873 for (RegionBindings::iterator I
= B
.begin(), E
= B
.end(); I
!= E
; ++I
)
1874 OS
<< ' ' << I
.getKey() << " : " << I
.getData() << nl
;