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
.getOffset().getQuantity(), 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 const 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());
827 return loc::MemRegionVal(baseReg
);
829 //===----------------------------------------------------------------------===//
830 // Pointer arithmetic.
831 //===----------------------------------------------------------------------===//
833 SVal
RegionStoreManager::evalBinOp(BinaryOperator::Opcode Op
, Loc L
, NonLoc R
,
835 // Assume the base location is MemRegionVal.
836 if (!isa
<loc::MemRegionVal
>(L
))
839 // Special case for zero RHS.
840 if (R
.isZeroConstant()) {
843 // Handle it normally.
847 // FIXME: does this need to be casted to match resultTy?
852 const MemRegion
* MR
= cast
<loc::MemRegionVal
>(L
).getRegion();
853 const ElementRegion
*ER
= 0;
855 switch (MR
->getKind()) {
856 case MemRegion::SymbolicRegionKind
: {
857 const SymbolicRegion
*SR
= cast
<SymbolicRegion
>(MR
);
858 SymbolRef Sym
= SR
->getSymbol();
859 QualType T
= Sym
->getType(Ctx
);
862 if (const PointerType
*PT
= T
->getAs
<PointerType
>())
863 EleTy
= PT
->getPointeeType();
865 EleTy
= T
->getAs
<ObjCObjectPointerType
>()->getPointeeType();
867 const NonLoc
&ZeroIdx
= svalBuilder
.makeZeroArrayIndex();
868 ER
= MRMgr
.getElementRegion(EleTy
, ZeroIdx
, SR
, Ctx
);
871 case MemRegion::AllocaRegionKind
: {
872 const AllocaRegion
*AR
= cast
<AllocaRegion
>(MR
);
873 QualType EleTy
= Ctx
.CharTy
; // Create an ElementRegion of bytes.
874 NonLoc ZeroIdx
= svalBuilder
.makeZeroArrayIndex();
875 ER
= MRMgr
.getElementRegion(EleTy
, ZeroIdx
, AR
, Ctx
);
879 case MemRegion::ElementRegionKind
: {
880 ER
= cast
<ElementRegion
>(MR
);
885 case MemRegion::VarRegionKind
:
886 case MemRegion::StringRegionKind
: {
890 case MemRegion::CompoundLiteralRegionKind
:
891 case MemRegion::FieldRegionKind
:
892 case MemRegion::ObjCIvarRegionKind
:
893 case MemRegion::CXXTempObjectRegionKind
:
894 case MemRegion::CXXBaseObjectRegionKind
:
897 case MemRegion::FunctionTextRegionKind
:
898 case MemRegion::BlockTextRegionKind
:
899 case MemRegion::BlockDataRegionKind
:
900 // Technically this can happen if people do funny things with casts.
903 case MemRegion::CXXThisRegionKind
:
905 "Cannot perform pointer arithmetic on implicit argument 'this'");
906 case MemRegion::GenericMemSpaceRegionKind
:
907 case MemRegion::StackLocalsSpaceRegionKind
:
908 case MemRegion::StackArgumentsSpaceRegionKind
:
909 case MemRegion::HeapSpaceRegionKind
:
910 case MemRegion::NonStaticGlobalSpaceRegionKind
:
911 case MemRegion::StaticGlobalSpaceRegionKind
:
912 case MemRegion::UnknownSpaceRegionKind
:
913 assert(0 && "Cannot perform pointer arithmetic on a MemSpace");
917 SVal Idx
= ER
->getIndex();
918 nonloc::ConcreteInt
* Base
= dyn_cast
<nonloc::ConcreteInt
>(&Idx
);
920 // For now, only support:
921 // (a) concrete integer indices that can easily be resolved
922 // (b) 0 + symbolic index
924 if (nonloc::ConcreteInt
*Offset
= dyn_cast
<nonloc::ConcreteInt
>(&R
)) {
925 // FIXME: Should use SValBuilder here.
927 Base
->evalBinOp(svalBuilder
, Op
,
928 cast
<nonloc::ConcreteInt
>(svalBuilder
.convertToArrayIndex(*Offset
)));
930 if (!isa
<NonLoc
>(NewIdx
))
933 const MemRegion
* NewER
=
934 MRMgr
.getElementRegion(ER
->getElementType(), cast
<NonLoc
>(NewIdx
),
935 ER
->getSuperRegion(), Ctx
);
936 return svalBuilder
.makeLoc(NewER
);
938 if (0 == Base
->getValue()) {
939 const MemRegion
* NewER
=
940 MRMgr
.getElementRegion(ER
->getElementType(), R
,
941 ER
->getSuperRegion(), Ctx
);
942 return svalBuilder
.makeLoc(NewER
);
949 //===----------------------------------------------------------------------===//
950 // Loading values from regions.
951 //===----------------------------------------------------------------------===//
953 Optional
<SVal
> RegionStoreManager::getDirectBinding(RegionBindings B
,
954 const MemRegion
*R
) {
956 if (const SVal
*V
= lookup(B
, R
, BindingKey::Direct
))
959 return Optional
<SVal
>();
962 Optional
<SVal
> RegionStoreManager::getDefaultBinding(RegionBindings B
,
963 const MemRegion
*R
) {
964 if (R
->isBoundable())
965 if (const TypedRegion
*TR
= dyn_cast
<TypedRegion
>(R
))
966 if (TR
->getValueType()->isUnionType())
969 if (const SVal
*V
= lookup(B
, R
, BindingKey::Default
))
972 return Optional
<SVal
>();
975 SVal
RegionStoreManager::Retrieve(Store store
, Loc L
, QualType T
) {
976 assert(!isa
<UnknownVal
>(L
) && "location unknown");
977 assert(!isa
<UndefinedVal
>(L
) && "location undefined");
979 // For access to concrete addresses, return UnknownVal. Checks
980 // for null dereferences (and similar errors) are done by checkers, not
982 // FIXME: We can consider lazily symbolicating such memory, but we really
983 // should defer this when we can reason easily about symbolicating arrays
985 if (isa
<loc::ConcreteInt
>(L
)) {
988 if (!isa
<loc::MemRegionVal
>(L
)) {
992 const MemRegion
*MR
= cast
<loc::MemRegionVal
>(L
).getRegion();
994 if (isa
<AllocaRegion
>(MR
) || isa
<SymbolicRegion
>(MR
)) {
996 const SymbolicRegion
*SR
= cast
<SymbolicRegion
>(MR
);
997 T
= SR
->getSymbol()->getType(Ctx
);
999 MR
= GetElementZeroRegion(MR
, T
);
1002 if (isa
<CodeTextRegion
>(MR
)) {
1003 assert(0 && "Why load from a code text region?");
1004 return UnknownVal();
1007 // FIXME: Perhaps this method should just take a 'const MemRegion*' argument
1008 // instead of 'Loc', and have the other Loc cases handled at a higher level.
1009 const TypedRegion
*R
= cast
<TypedRegion
>(MR
);
1010 QualType RTy
= R
->getValueType();
1012 // FIXME: We should eventually handle funny addressing. e.g.:
1016 // char *q = (char*) p;
1017 // char c = *q; // returns the first byte of 'x'.
1019 // Such funny addressing will occur due to layering of regions.
1021 if (RTy
->isStructureOrClassType())
1022 return RetrieveStruct(store
, R
);
1024 // FIXME: Handle unions.
1025 if (RTy
->isUnionType())
1026 return UnknownVal();
1028 if (RTy
->isArrayType())
1029 return RetrieveArray(store
, R
);
1031 // FIXME: handle Vector types.
1032 if (RTy
->isVectorType())
1033 return UnknownVal();
1035 if (const FieldRegion
* FR
= dyn_cast
<FieldRegion
>(R
))
1036 return CastRetrievedVal(RetrieveField(store
, FR
), FR
, T
, false);
1038 if (const ElementRegion
* ER
= dyn_cast
<ElementRegion
>(R
)) {
1039 // FIXME: Here we actually perform an implicit conversion from the loaded
1040 // value to the element type. Eventually we want to compose these values
1041 // more intelligently. For example, an 'element' can encompass multiple
1042 // bound regions (e.g., several bound bytes), or could be a subset of
1044 return CastRetrievedVal(RetrieveElement(store
, ER
), ER
, T
, false);
1047 if (const ObjCIvarRegion
*IVR
= dyn_cast
<ObjCIvarRegion
>(R
)) {
1048 // FIXME: Here we actually perform an implicit conversion from the loaded
1049 // value to the ivar type. What we should model is stores to ivars
1050 // that blow past the extent of the ivar. If the address of the ivar is
1051 // reinterpretted, it is possible we stored a different value that could
1052 // fit within the ivar. Either we need to cast these when storing them
1053 // or reinterpret them lazily (as we do here).
1054 return CastRetrievedVal(RetrieveObjCIvar(store
, IVR
), IVR
, T
, false);
1057 if (const VarRegion
*VR
= dyn_cast
<VarRegion
>(R
)) {
1058 // FIXME: Here we actually perform an implicit conversion from the loaded
1059 // value to the variable type. What we should model is stores to variables
1060 // that blow past the extent of the variable. If the address of the
1061 // variable is reinterpretted, it is possible we stored a different value
1062 // that could fit within the variable. Either we need to cast these when
1063 // storing them or reinterpret them lazily (as we do here).
1064 return CastRetrievedVal(RetrieveVar(store
, VR
), VR
, T
, false);
1067 RegionBindings B
= GetRegionBindings(store
);
1068 const SVal
*V
= lookup(B
, R
, BindingKey::Direct
);
1070 // Check if the region has a binding.
1074 // The location does not have a bound value. This means that it has
1075 // the value it had upon its creation and/or entry to the analyzed
1076 // function/method. These are either symbolic values or 'undefined'.
1077 if (R
->hasStackNonParametersStorage()) {
1078 // All stack variables are considered to have undefined values
1079 // upon creation. All heap allocated blocks are considered to
1080 // have undefined values as well unless they are explicitly bound
1081 // to specific values.
1082 return UndefinedVal();
1085 // All other values are symbolic.
1086 return svalBuilder
.getRegionValueSymbolVal(R
);
1089 std::pair
<Store
, const MemRegion
*>
1090 RegionStoreManager::GetLazyBinding(RegionBindings B
, const MemRegion
*R
) {
1091 if (Optional
<SVal
> OV
= getDirectBinding(B
, R
))
1092 if (const nonloc::LazyCompoundVal
*V
=
1093 dyn_cast
<nonloc::LazyCompoundVal
>(OV
.getPointer()))
1094 return std::make_pair(V
->getStore(), V
->getRegion());
1096 if (const ElementRegion
*ER
= dyn_cast
<ElementRegion
>(R
)) {
1097 const std::pair
<Store
, const MemRegion
*> &X
=
1098 GetLazyBinding(B
, ER
->getSuperRegion());
1101 return std::make_pair(X
.first
,
1102 MRMgr
.getElementRegionWithSuper(ER
, X
.second
));
1104 else if (const FieldRegion
*FR
= dyn_cast
<FieldRegion
>(R
)) {
1105 const std::pair
<Store
, const MemRegion
*> &X
=
1106 GetLazyBinding(B
, FR
->getSuperRegion());
1109 return std::make_pair(X
.first
,
1110 MRMgr
.getFieldRegionWithSuper(FR
, X
.second
));
1112 // C++ base object region is another kind of region that we should blast
1113 // through to look for lazy compound value. It is like a field region.
1114 else if (const CXXBaseObjectRegion
*baseReg
=
1115 dyn_cast
<CXXBaseObjectRegion
>(R
)) {
1116 const std::pair
<Store
, const MemRegion
*> &X
=
1117 GetLazyBinding(B
, baseReg
->getSuperRegion());
1120 return std::make_pair(X
.first
,
1121 MRMgr
.getCXXBaseObjectRegionWithSuper(baseReg
, X
.second
));
1123 // The NULL MemRegion indicates an non-existent lazy binding. A NULL Store is
1124 // possible for a valid lazy binding.
1125 return std::make_pair((Store
) 0, (const MemRegion
*) 0);
1128 SVal
RegionStoreManager::RetrieveElement(Store store
,
1129 const ElementRegion
* R
) {
1130 // Check if the region has a binding.
1131 RegionBindings B
= GetRegionBindings(store
);
1132 if (const Optional
<SVal
> &V
= getDirectBinding(B
, R
))
1135 const MemRegion
* superR
= R
->getSuperRegion();
1137 // Check if the region is an element region of a string literal.
1138 if (const StringRegion
*StrR
=dyn_cast
<StringRegion
>(superR
)) {
1139 // FIXME: Handle loads from strings where the literal is treated as
1140 // an integer, e.g., *((unsigned int*)"hello")
1141 QualType T
= Ctx
.getAsArrayType(StrR
->getValueType())->getElementType();
1142 if (T
!= Ctx
.getCanonicalType(R
->getElementType()))
1143 return UnknownVal();
1145 const StringLiteral
*Str
= StrR
->getStringLiteral();
1146 SVal Idx
= R
->getIndex();
1147 if (nonloc::ConcreteInt
*CI
= dyn_cast
<nonloc::ConcreteInt
>(&Idx
)) {
1148 int64_t i
= CI
->getValue().getSExtValue();
1149 int64_t byteLength
= Str
->getByteLength();
1150 // Technically, only i == byteLength is guaranteed to be null.
1151 // However, such overflows should be caught before reaching this point;
1152 // the only time such an access would be made is if a string literal was
1153 // used to initialize a larger array.
1154 char c
= (i
>= byteLength
) ? '\0' : Str
->getString()[i
];
1155 return svalBuilder
.makeIntVal(c
, T
);
1159 // Check for loads from a code text region. For such loads, just give up.
1160 if (isa
<CodeTextRegion
>(superR
))
1161 return UnknownVal();
1163 // Handle the case where we are indexing into a larger scalar object.
1164 // For example, this handles:
1168 // FIXME: This is a hack, and doesn't do anything really intelligent yet.
1169 const RegionRawOffset
&O
= R
->getAsArrayOffset();
1170 if (const TypedRegion
*baseR
= dyn_cast_or_null
<TypedRegion
>(O
.getRegion())) {
1171 QualType baseT
= baseR
->getValueType();
1172 if (baseT
->isScalarType()) {
1173 QualType elemT
= R
->getElementType();
1174 if (elemT
->isScalarType()) {
1175 if (Ctx
.getTypeSizeInChars(baseT
) >= Ctx
.getTypeSizeInChars(elemT
)) {
1176 if (const Optional
<SVal
> &V
= getDirectBinding(B
, superR
)) {
1177 if (SymbolRef parentSym
= V
->getAsSymbol())
1178 return svalBuilder
.getDerivedRegionValueSymbolVal(parentSym
, R
);
1180 if (V
->isUnknownOrUndef())
1182 // Other cases: give up. We are indexing into a larger object
1183 // that has some value, but we don't know how to handle that yet.
1184 return UnknownVal();
1190 return RetrieveFieldOrElementCommon(store
, R
, R
->getElementType(), superR
);
1193 SVal
RegionStoreManager::RetrieveField(Store store
,
1194 const FieldRegion
* R
) {
1196 // Check if the region has a binding.
1197 RegionBindings B
= GetRegionBindings(store
);
1198 if (const Optional
<SVal
> &V
= getDirectBinding(B
, R
))
1201 QualType Ty
= R
->getValueType();
1202 return RetrieveFieldOrElementCommon(store
, R
, Ty
, R
->getSuperRegion());
1206 RegionStoreManager::RetrieveDerivedDefaultValue(RegionBindings B
,
1207 const MemRegion
*superR
,
1208 const TypedRegion
*R
,
1211 if (const Optional
<SVal
> &D
= getDefaultBinding(B
, superR
)) {
1212 if (SymbolRef parentSym
= D
->getAsSymbol())
1213 return svalBuilder
.getDerivedRegionValueSymbolVal(parentSym
, R
);
1215 if (D
->isZeroConstant())
1216 return svalBuilder
.makeZeroVal(Ty
);
1218 if (D
->isUnknownOrUndef())
1221 assert(0 && "Unknown default value");
1224 return Optional
<SVal
>();
1227 SVal
RegionStoreManager::RetrieveFieldOrElementCommon(Store store
,
1228 const TypedRegion
*R
,
1230 const MemRegion
*superR
) {
1232 // At this point we have already checked in either RetrieveElement or
1233 // RetrieveField if 'R' has a direct binding.
1235 RegionBindings B
= GetRegionBindings(store
);
1238 if (const Optional
<SVal
> &D
=
1239 RetrieveDerivedDefaultValue(B
, superR
, R
, Ty
))
1242 // If our super region is a field or element itself, walk up the region
1243 // hierarchy to see if there is a default value installed in an ancestor.
1244 if (const SubRegion
*SR
= dyn_cast
<SubRegion
>(superR
)) {
1245 superR
= SR
->getSuperRegion();
1252 Store lazyBindingStore
= NULL
;
1253 const MemRegion
*lazyBindingRegion
= NULL
;
1254 llvm::tie(lazyBindingStore
, lazyBindingRegion
) = GetLazyBinding(B
, R
);
1256 if (lazyBindingRegion
) {
1257 if (const ElementRegion
*ER
= dyn_cast
<ElementRegion
>(lazyBindingRegion
))
1258 return RetrieveElement(lazyBindingStore
, ER
);
1259 return RetrieveField(lazyBindingStore
,
1260 cast
<FieldRegion
>(lazyBindingRegion
));
1263 if (R
->hasStackNonParametersStorage()) {
1264 if (const ElementRegion
*ER
= dyn_cast
<ElementRegion
>(R
)) {
1265 // Currently we don't reason specially about Clang-style vectors. Check
1266 // if superR is a vector and if so return Unknown.
1267 if (const TypedRegion
*typedSuperR
= dyn_cast
<TypedRegion
>(superR
)) {
1268 if (typedSuperR
->getValueType()->isVectorType())
1269 return UnknownVal();
1272 // FIXME: We also need to take ElementRegions with symbolic indexes into
1274 if (!ER
->getIndex().isConstant())
1275 return UnknownVal();
1278 return UndefinedVal();
1281 // All other values are symbolic.
1282 return svalBuilder
.getRegionValueSymbolVal(R
);
1285 SVal
RegionStoreManager::RetrieveObjCIvar(Store store
, const ObjCIvarRegion
* R
){
1287 // Check if the region has a binding.
1288 RegionBindings B
= GetRegionBindings(store
);
1290 if (const Optional
<SVal
> &V
= getDirectBinding(B
, R
))
1293 const MemRegion
*superR
= R
->getSuperRegion();
1295 // Check if the super region has a default binding.
1296 if (const Optional
<SVal
> &V
= getDefaultBinding(B
, superR
)) {
1297 if (SymbolRef parentSym
= V
->getAsSymbol())
1298 return svalBuilder
.getDerivedRegionValueSymbolVal(parentSym
, R
);
1300 // Other cases: give up.
1301 return UnknownVal();
1304 return RetrieveLazySymbol(R
);
1307 SVal
RegionStoreManager::RetrieveVar(Store store
, const VarRegion
*R
) {
1309 // Check if the region has a binding.
1310 RegionBindings B
= GetRegionBindings(store
);
1312 if (const Optional
<SVal
> &V
= getDirectBinding(B
, R
))
1315 // Lazily derive a value for the VarRegion.
1316 const VarDecl
*VD
= R
->getDecl();
1317 QualType T
= VD
->getType();
1318 const MemSpaceRegion
*MS
= R
->getMemorySpace();
1320 if (isa
<UnknownSpaceRegion
>(MS
) ||
1321 isa
<StackArgumentsSpaceRegion
>(MS
))
1322 return svalBuilder
.getRegionValueSymbolVal(R
);
1324 if (isa
<GlobalsSpaceRegion
>(MS
)) {
1325 if (isa
<NonStaticGlobalSpaceRegion
>(MS
)) {
1326 // Is 'VD' declared constant? If so, retrieve the constant value.
1327 QualType CT
= Ctx
.getCanonicalType(T
);
1328 if (CT
.isConstQualified()) {
1329 const Expr
*Init
= VD
->getInit();
1330 // Do the null check first, as we want to call 'IgnoreParenCasts'.
1332 if (const IntegerLiteral
*IL
=
1333 dyn_cast
<IntegerLiteral
>(Init
->IgnoreParenCasts())) {
1334 const nonloc::ConcreteInt
&V
= svalBuilder
.makeIntVal(IL
);
1335 return svalBuilder
.evalCast(V
, Init
->getType(), IL
->getType());
1339 if (const Optional
<SVal
> &V
= RetrieveDerivedDefaultValue(B
, MS
, R
, CT
))
1340 return V
.getValue();
1342 return svalBuilder
.getRegionValueSymbolVal(R
);
1345 if (T
->isIntegerType())
1346 return svalBuilder
.makeIntVal(0, T
);
1347 if (T
->isPointerType())
1348 return svalBuilder
.makeNull();
1350 return UnknownVal();
1353 return UndefinedVal();
1356 SVal
RegionStoreManager::RetrieveLazySymbol(const TypedRegion
*R
) {
1357 // All other values are symbolic.
1358 return svalBuilder
.getRegionValueSymbolVal(R
);
1361 SVal
RegionStoreManager::RetrieveStruct(Store store
, const TypedRegion
* R
) {
1362 QualType T
= R
->getValueType();
1363 assert(T
->isStructureOrClassType());
1364 return svalBuilder
.makeLazyCompoundVal(store
, R
);
1367 SVal
RegionStoreManager::RetrieveArray(Store store
, const TypedRegion
* R
) {
1368 assert(Ctx
.getAsConstantArrayType(R
->getValueType()));
1369 return svalBuilder
.makeLazyCompoundVal(store
, R
);
1372 //===----------------------------------------------------------------------===//
1373 // Binding values to regions.
1374 //===----------------------------------------------------------------------===//
1376 Store
RegionStoreManager::Remove(Store store
, Loc L
) {
1377 if (isa
<loc::MemRegionVal
>(L
))
1378 if (const MemRegion
* R
= cast
<loc::MemRegionVal
>(L
).getRegion())
1379 return removeBinding(GetRegionBindings(store
), R
).getRoot();
1384 Store
RegionStoreManager::Bind(Store store
, Loc L
, SVal V
) {
1385 if (isa
<loc::ConcreteInt
>(L
))
1388 // If we get here, the location should be a region.
1389 const MemRegion
*R
= cast
<loc::MemRegionVal
>(L
).getRegion();
1391 // Check if the region is a struct region.
1392 if (const TypedRegion
* TR
= dyn_cast
<TypedRegion
>(R
))
1393 if (TR
->getValueType()->isStructureOrClassType())
1394 return BindStruct(store
, TR
, V
);
1396 if (const ElementRegion
*ER
= dyn_cast
<ElementRegion
>(R
)) {
1397 if (ER
->getIndex().isZeroConstant()) {
1398 if (const TypedRegion
*superR
=
1399 dyn_cast
<TypedRegion
>(ER
->getSuperRegion())) {
1400 QualType superTy
= superR
->getValueType();
1401 // For now, just invalidate the fields of the struct/union/class.
1402 // This is for test rdar_test_7185607 in misc-ps-region-store.m.
1403 // FIXME: Precisely handle the fields of the record.
1404 if (superTy
->isStructureOrClassType())
1405 return KillStruct(store
, superR
, UnknownVal());
1409 else if (const SymbolicRegion
*SR
= dyn_cast
<SymbolicRegion
>(R
)) {
1410 // Binding directly to a symbolic region should be treated as binding
1412 QualType T
= SR
->getSymbol()->getType(Ctx
);
1414 // FIXME: Is this the right way to handle symbols that are references?
1415 if (const PointerType
*PT
= T
->getAs
<PointerType
>())
1416 T
= PT
->getPointeeType();
1418 T
= T
->getAs
<ReferenceType
>()->getPointeeType();
1420 R
= GetElementZeroRegion(SR
, T
);
1423 // Perform the binding.
1424 RegionBindings B
= GetRegionBindings(store
);
1425 return addBinding(B
, R
, BindingKey::Direct
, V
).getRoot();
1428 Store
RegionStoreManager::BindDecl(Store store
, const VarRegion
*VR
,
1431 QualType T
= VR
->getDecl()->getType();
1433 if (T
->isArrayType())
1434 return BindArray(store
, VR
, InitVal
);
1435 if (T
->isStructureOrClassType())
1436 return BindStruct(store
, VR
, InitVal
);
1438 return Bind(store
, svalBuilder
.makeLoc(VR
), InitVal
);
1441 // FIXME: this method should be merged into Bind().
1442 Store
RegionStoreManager::BindCompoundLiteral(Store store
,
1443 const CompoundLiteralExpr
*CL
,
1444 const LocationContext
*LC
,
1446 return Bind(store
, loc::MemRegionVal(MRMgr
.getCompoundLiteralRegion(CL
, LC
)),
1451 Store
RegionStoreManager::setImplicitDefaultValue(Store store
,
1454 RegionBindings B
= GetRegionBindings(store
);
1457 if (Loc::IsLocType(T
))
1458 V
= svalBuilder
.makeNull();
1459 else if (T
->isIntegerType())
1460 V
= svalBuilder
.makeZeroVal(T
);
1461 else if (T
->isStructureOrClassType() || T
->isArrayType()) {
1462 // Set the default value to a zero constant when it is a structure
1463 // or array. The type doesn't really matter.
1464 V
= svalBuilder
.makeZeroVal(Ctx
.IntTy
);
1470 return addBinding(B
, R
, BindingKey::Default
, V
).getRoot();
1473 Store
RegionStoreManager::BindArray(Store store
, const TypedRegion
* R
,
1476 const ArrayType
*AT
=cast
<ArrayType
>(Ctx
.getCanonicalType(R
->getValueType()));
1477 QualType ElementTy
= AT
->getElementType();
1478 Optional
<uint64_t> Size
;
1480 if (const ConstantArrayType
* CAT
= dyn_cast
<ConstantArrayType
>(AT
))
1481 Size
= CAT
->getSize().getZExtValue();
1483 // Check if the init expr is a string literal.
1484 if (loc::MemRegionVal
*MRV
= dyn_cast
<loc::MemRegionVal
>(&Init
)) {
1485 const StringRegion
*S
= cast
<StringRegion
>(MRV
->getRegion());
1487 // Treat the string as a lazy compound value.
1488 nonloc::LazyCompoundVal LCV
=
1489 cast
<nonloc::LazyCompoundVal
>(svalBuilder
.makeLazyCompoundVal(store
, S
));
1490 return CopyLazyBindings(LCV
, store
, R
);
1493 // Handle lazy compound values.
1494 if (nonloc::LazyCompoundVal
*LCV
= dyn_cast
<nonloc::LazyCompoundVal
>(&Init
))
1495 return CopyLazyBindings(*LCV
, store
, R
);
1497 // Remaining case: explicit compound values.
1499 if (Init
.isUnknown())
1500 return setImplicitDefaultValue(store
, R
, ElementTy
);
1502 nonloc::CompoundVal
& CV
= cast
<nonloc::CompoundVal
>(Init
);
1503 nonloc::CompoundVal::iterator VI
= CV
.begin(), VE
= CV
.end();
1506 for (; Size
.hasValue() ? i
< Size
.getValue() : true ; ++i
, ++VI
) {
1507 // The init list might be shorter than the array length.
1511 const NonLoc
&Idx
= svalBuilder
.makeArrayIndex(i
);
1512 const ElementRegion
*ER
= MRMgr
.getElementRegion(ElementTy
, Idx
, R
, Ctx
);
1514 if (ElementTy
->isStructureOrClassType())
1515 store
= BindStruct(store
, ER
, *VI
);
1516 else if (ElementTy
->isArrayType())
1517 store
= BindArray(store
, ER
, *VI
);
1519 store
= Bind(store
, svalBuilder
.makeLoc(ER
), *VI
);
1522 // If the init list is shorter than the array length, set the
1523 // array default value.
1524 if (Size
.hasValue() && i
< Size
.getValue())
1525 store
= setImplicitDefaultValue(store
, R
, ElementTy
);
1530 Store
RegionStoreManager::BindStruct(Store store
, const TypedRegion
* R
,
1533 if (!Features
.supportsFields())
1536 QualType T
= R
->getValueType();
1537 assert(T
->isStructureOrClassType());
1539 const RecordType
* RT
= T
->getAs
<RecordType
>();
1540 RecordDecl
* RD
= RT
->getDecl();
1542 if (!RD
->isDefinition())
1545 // Handle lazy compound values.
1546 if (const nonloc::LazyCompoundVal
*LCV
=dyn_cast
<nonloc::LazyCompoundVal
>(&V
))
1547 return CopyLazyBindings(*LCV
, store
, R
);
1549 // We may get non-CompoundVal accidentally due to imprecise cast logic or
1550 // that we are binding symbolic struct value. Kill the field values, and if
1551 // the value is symbolic go and bind it as a "default" binding.
1552 if (V
.isUnknown() || !isa
<nonloc::CompoundVal
>(V
)) {
1553 SVal SV
= isa
<nonloc::SymbolVal
>(V
) ? V
: UnknownVal();
1554 return KillStruct(store
, R
, SV
);
1557 nonloc::CompoundVal
& CV
= cast
<nonloc::CompoundVal
>(V
);
1558 nonloc::CompoundVal::iterator VI
= CV
.begin(), VE
= CV
.end();
1560 RecordDecl::field_iterator FI
, FE
;
1562 for (FI
= RD
->field_begin(), FE
= RD
->field_end(); FI
!= FE
; ++FI
, ++VI
) {
1567 QualType FTy
= (*FI
)->getType();
1568 const FieldRegion
* FR
= MRMgr
.getFieldRegion(*FI
, R
);
1570 if (FTy
->isArrayType())
1571 store
= BindArray(store
, FR
, *VI
);
1572 else if (FTy
->isStructureOrClassType())
1573 store
= BindStruct(store
, FR
, *VI
);
1575 store
= Bind(store
, svalBuilder
.makeLoc(FR
), *VI
);
1578 // There may be fewer values in the initialize list than the fields of struct.
1580 RegionBindings B
= GetRegionBindings(store
);
1581 B
= addBinding(B
, R
, BindingKey::Default
, svalBuilder
.makeIntVal(0, false));
1582 store
= B
.getRoot();
1588 Store
RegionStoreManager::KillStruct(Store store
, const TypedRegion
* R
,
1590 BindingKey key
= BindingKey::Make(R
, BindingKey::Default
);
1592 // The BindingKey may be "invalid" if we cannot handle the region binding
1593 // explicitly. One example is something like array[index], where index
1594 // is a symbolic value. In such cases, we want to invalidate the entire
1595 // array, as the index assignment could have been to any element. In
1596 // the case of nested symbolic indices, we need to march up the region
1597 // hierarchy untile we reach a region whose binding we can reason about.
1598 const SubRegion
*subReg
= R
;
1600 while (!key
.isValid()) {
1601 if (const SubRegion
*tmp
= dyn_cast
<SubRegion
>(subReg
->getSuperRegion())) {
1603 key
= BindingKey::Make(tmp
, BindingKey::Default
);
1609 // Remove the old bindings, using 'subReg' as the root of all regions
1610 // we will invalidate.
1611 RegionBindings B
= GetRegionBindings(store
);
1612 llvm::OwningPtr
<RegionStoreSubRegionMap
>
1613 SubRegions(getRegionStoreSubRegionMap(store
));
1614 RemoveSubRegionBindings(B
, subReg
, *SubRegions
);
1616 // Set the default value of the struct region to "unknown".
1620 return addBinding(B
, key
, DefaultVal
).getRoot();
1623 Store
RegionStoreManager::CopyLazyBindings(nonloc::LazyCompoundVal V
,
1624 Store store
, const TypedRegion
*R
) {
1626 // Nuke the old bindings stemming from R.
1627 RegionBindings B
= GetRegionBindings(store
);
1629 llvm::OwningPtr
<RegionStoreSubRegionMap
>
1630 SubRegions(getRegionStoreSubRegionMap(store
));
1632 // B and DVM are updated after the call to RemoveSubRegionBindings.
1633 RemoveSubRegionBindings(B
, R
, *SubRegions
.get());
1635 // Now copy the bindings. This amounts to just binding 'V' to 'R'. This
1636 // results in a zero-copy algorithm.
1637 return addBinding(B
, R
, BindingKey::Direct
, V
).getRoot();
1640 //===----------------------------------------------------------------------===//
1641 // "Raw" retrievals and bindings.
1642 //===----------------------------------------------------------------------===//
1645 RegionBindings
RegionStoreManager::addBinding(RegionBindings B
, BindingKey K
,
1649 return RBFactory
.add(B
, K
, V
);
1652 RegionBindings
RegionStoreManager::addBinding(RegionBindings B
,
1654 BindingKey::Kind k
, SVal V
) {
1655 return addBinding(B
, BindingKey::Make(R
, k
), V
);
1658 const SVal
*RegionStoreManager::lookup(RegionBindings B
, BindingKey K
) {
1664 const SVal
*RegionStoreManager::lookup(RegionBindings B
,
1666 BindingKey::Kind k
) {
1667 return lookup(B
, BindingKey::Make(R
, k
));
1670 RegionBindings
RegionStoreManager::removeBinding(RegionBindings B
,
1674 return RBFactory
.remove(B
, K
);
1677 RegionBindings
RegionStoreManager::removeBinding(RegionBindings B
,
1679 BindingKey::Kind k
){
1680 return removeBinding(B
, BindingKey::Make(R
, k
));
1683 //===----------------------------------------------------------------------===//
1685 //===----------------------------------------------------------------------===//
1688 class removeDeadBindingsWorker
:
1689 public ClusterAnalysis
<removeDeadBindingsWorker
> {
1690 llvm::SmallVector
<const SymbolicRegion
*, 12> Postponed
;
1691 SymbolReaper
&SymReaper
;
1692 const StackFrameContext
*CurrentLCtx
;
1695 removeDeadBindingsWorker(RegionStoreManager
&rm
, GRStateManager
&stateMgr
,
1696 RegionBindings b
, SymbolReaper
&symReaper
,
1697 const StackFrameContext
*LCtx
)
1698 : ClusterAnalysis
<removeDeadBindingsWorker
>(rm
, stateMgr
, b
,
1699 /* includeGlobals = */ false),
1700 SymReaper(symReaper
), CurrentLCtx(LCtx
) {}
1702 // Called by ClusterAnalysis.
1703 void VisitAddedToCluster(const MemRegion
*baseR
, RegionCluster
&C
);
1704 void VisitCluster(const MemRegion
*baseR
, BindingKey
*I
, BindingKey
*E
);
1706 void VisitBindingKey(BindingKey K
);
1707 bool UpdatePostponed();
1708 void VisitBinding(SVal V
);
1712 void removeDeadBindingsWorker::VisitAddedToCluster(const MemRegion
*baseR
,
1715 if (const VarRegion
*VR
= dyn_cast
<VarRegion
>(baseR
)) {
1716 if (SymReaper
.isLive(VR
))
1717 AddToWorkList(baseR
, C
);
1722 if (const SymbolicRegion
*SR
= dyn_cast
<SymbolicRegion
>(baseR
)) {
1723 if (SymReaper
.isLive(SR
->getSymbol()))
1724 AddToWorkList(SR
, C
);
1726 Postponed
.push_back(SR
);
1731 if (isa
<NonStaticGlobalSpaceRegion
>(baseR
)) {
1732 AddToWorkList(baseR
, C
);
1736 // CXXThisRegion in the current or parent location context is live.
1737 if (const CXXThisRegion
*TR
= dyn_cast
<CXXThisRegion
>(baseR
)) {
1738 const StackArgumentsSpaceRegion
*StackReg
=
1739 cast
<StackArgumentsSpaceRegion
>(TR
->getSuperRegion());
1740 const StackFrameContext
*RegCtx
= StackReg
->getStackFrame();
1741 if (RegCtx
== CurrentLCtx
|| RegCtx
->isParentOf(CurrentLCtx
))
1742 AddToWorkList(TR
, C
);
1746 void removeDeadBindingsWorker::VisitCluster(const MemRegion
*baseR
,
1747 BindingKey
*I
, BindingKey
*E
) {
1748 for ( ; I
!= E
; ++I
)
1749 VisitBindingKey(*I
);
1752 void removeDeadBindingsWorker::VisitBinding(SVal V
) {
1753 // Is it a LazyCompoundVal? All referenced regions are live as well.
1754 if (const nonloc::LazyCompoundVal
*LCS
=
1755 dyn_cast
<nonloc::LazyCompoundVal
>(&V
)) {
1757 const MemRegion
*LazyR
= LCS
->getRegion();
1758 RegionBindings B
= RegionStoreManager::GetRegionBindings(LCS
->getStore());
1759 for (RegionBindings::iterator RI
= B
.begin(), RE
= B
.end(); RI
!= RE
; ++RI
){
1760 const SubRegion
*baseR
= dyn_cast
<SubRegion
>(RI
.getKey().getRegion());
1761 if (baseR
&& baseR
->isSubRegionOf(LazyR
))
1762 VisitBinding(RI
.getData());
1767 // If V is a region, then add it to the worklist.
1768 if (const MemRegion
*R
= V
.getAsRegion())
1771 // Update the set of live symbols.
1772 for (SVal::symbol_iterator SI
=V
.symbol_begin(), SE
=V
.symbol_end();
1774 SymReaper
.markLive(*SI
);
1777 void removeDeadBindingsWorker::VisitBindingKey(BindingKey K
) {
1778 const MemRegion
*R
= K
.getRegion();
1780 // Mark this region "live" by adding it to the worklist. This will cause
1781 // use to visit all regions in the cluster (if we haven't visited them
1783 if (AddToWorkList(R
)) {
1784 // Mark the symbol for any live SymbolicRegion as "live". This means we
1785 // should continue to track that symbol.
1786 if (const SymbolicRegion
*SymR
= dyn_cast
<SymbolicRegion
>(R
))
1787 SymReaper
.markLive(SymR
->getSymbol());
1789 // For BlockDataRegions, enqueue the VarRegions for variables marked
1790 // with __block (passed-by-reference).
1791 // via BlockDeclRefExprs.
1792 if (const BlockDataRegion
*BD
= dyn_cast
<BlockDataRegion
>(R
)) {
1793 for (BlockDataRegion::referenced_vars_iterator
1794 RI
= BD
->referenced_vars_begin(), RE
= BD
->referenced_vars_end();
1796 if ((*RI
)->getDecl()->getAttr
<BlocksAttr
>())
1800 // No possible data bindings on a BlockDataRegion.
1805 // Visit the data binding for K.
1806 if (const SVal
*V
= RM
.lookup(B
, K
))
1810 bool removeDeadBindingsWorker::UpdatePostponed() {
1811 // See if any postponed SymbolicRegions are actually live now, after
1812 // having done a scan.
1813 bool changed
= false;
1815 for (llvm::SmallVectorImpl
<const SymbolicRegion
*>::iterator
1816 I
= Postponed
.begin(), E
= Postponed
.end() ; I
!= E
; ++I
) {
1817 if (const SymbolicRegion
*SR
= cast_or_null
<SymbolicRegion
>(*I
)) {
1818 if (SymReaper
.isLive(SR
->getSymbol())) {
1819 changed
|= AddToWorkList(SR
);
1828 Store
RegionStoreManager::removeDeadBindings(Store store
,
1829 const StackFrameContext
*LCtx
,
1830 SymbolReaper
& SymReaper
,
1831 llvm::SmallVectorImpl
<const MemRegion
*>& RegionRoots
)
1833 RegionBindings B
= GetRegionBindings(store
);
1834 removeDeadBindingsWorker
W(*this, StateMgr
, B
, SymReaper
, LCtx
);
1835 W
.GenerateClusters();
1837 // Enqueue the region roots onto the worklist.
1838 for (llvm::SmallVectorImpl
<const MemRegion
*>::iterator I
=RegionRoots
.begin(),
1839 E
=RegionRoots
.end(); I
!=E
; ++I
)
1840 W
.AddToWorkList(*I
);
1842 do W
.RunWorkList(); while (W
.UpdatePostponed());
1844 // We have now scanned the store, marking reachable regions and symbols
1845 // as live. We now remove all the regions that are dead from the store
1846 // as well as update DSymbols with the set symbols that are now dead.
1847 for (RegionBindings::iterator I
= B
.begin(), E
= B
.end(); I
!= E
; ++I
) {
1848 const BindingKey
&K
= I
.getKey();
1850 // If the cluster has been visited, we know the region has been marked.
1851 if (W
.isVisited(K
.getRegion()))
1854 // Remove the dead entry.
1855 B
= removeBinding(B
, K
);
1857 // Mark all non-live symbols that this binding references as dead.
1858 if (const SymbolicRegion
* SymR
= dyn_cast
<SymbolicRegion
>(K
.getRegion()))
1859 SymReaper
.maybeDead(SymR
->getSymbol());
1861 SVal X
= I
.getData();
1862 SVal::symbol_iterator SI
= X
.symbol_begin(), SE
= X
.symbol_end();
1863 for (; SI
!= SE
; ++SI
)
1864 SymReaper
.maybeDead(*SI
);
1871 Store
RegionStoreManager::enterStackFrame(const GRState
*state
,
1872 const StackFrameContext
*frame
) {
1873 FunctionDecl
const *FD
= cast
<FunctionDecl
>(frame
->getDecl());
1874 FunctionDecl::param_const_iterator PI
= FD
->param_begin(),
1875 PE
= FD
->param_end();
1876 Store store
= state
->getStore();
1878 if (CallExpr
const *CE
= dyn_cast
<CallExpr
>(frame
->getCallSite())) {
1879 CallExpr::const_arg_iterator AI
= CE
->arg_begin(), AE
= CE
->arg_end();
1881 // Copy the arg expression value to the arg variables. We check that
1882 // PI != PE because the actual number of arguments may be different than
1883 // the function declaration.
1884 for (; AI
!= AE
&& PI
!= PE
; ++AI
, ++PI
) {
1885 SVal ArgVal
= state
->getSVal(*AI
);
1887 svalBuilder
.makeLoc(MRMgr
.getVarRegion(*PI
, frame
)), ArgVal
);
1889 } else if (const CXXConstructExpr
*CE
=
1890 dyn_cast
<CXXConstructExpr
>(frame
->getCallSite())) {
1891 CXXConstructExpr::const_arg_iterator AI
= CE
->arg_begin(),
1894 // Copy the arg expression value to the arg variables.
1895 for (; AI
!= AE
; ++AI
, ++PI
) {
1896 SVal ArgVal
= state
->getSVal(*AI
);
1898 svalBuilder
.makeLoc(MRMgr
.getVarRegion(*PI
,frame
)), ArgVal
);
1901 assert(isa
<CXXDestructorDecl
>(frame
->getDecl()));
1906 //===----------------------------------------------------------------------===//
1908 //===----------------------------------------------------------------------===//
1910 void RegionStoreManager::print(Store store
, llvm::raw_ostream
& OS
,
1911 const char* nl
, const char *sep
) {
1912 RegionBindings B
= GetRegionBindings(store
);
1913 OS
<< "Store (direct and default bindings):" << nl
;
1915 for (RegionBindings::iterator I
= B
.begin(), E
= B
.end(); I
!= E
; ++I
)
1916 OS
<< ' ' << I
.getKey() << " : " << I
.getData() << nl
;