1 //= GRState.cpp - Path-Sensitive "State" for tracking values -----*- 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 implements GRState and GRStateManager.
12 //===----------------------------------------------------------------------===//
14 #include "clang/Analysis/CFG.h"
15 #include "clang/StaticAnalyzer/PathSensitive/GRStateTrait.h"
16 #include "clang/StaticAnalyzer/PathSensitive/GRState.h"
17 #include "clang/StaticAnalyzer/PathSensitive/SubEngine.h"
18 #include "clang/StaticAnalyzer/PathSensitive/TransferFuncs.h"
19 #include "llvm/Support/raw_ostream.h"
21 using namespace clang
;
24 // Give the vtable for ConstraintManager somewhere to live.
25 // FIXME: Move this elsewhere.
26 ConstraintManager::~ConstraintManager() {}
28 GRStateManager::~GRStateManager() {
29 for (std::vector
<GRState::Printer
*>::iterator I
=Printers
.begin(),
30 E
=Printers
.end(); I
!=E
; ++I
)
33 for (GDMContextsTy::iterator I
=GDMContexts
.begin(), E
=GDMContexts
.end();
35 I
->second
.second(I
->second
.first
);
39 GRStateManager::removeDeadBindings(const GRState
* state
,
40 const StackFrameContext
*LCtx
,
41 SymbolReaper
& SymReaper
) {
43 // This code essentially performs a "mark-and-sweep" of the VariableBindings.
44 // The roots are any Block-level exprs and Decls that our liveness algorithm
45 // tells us are live. We then see what Decls they may reference, and keep
46 // those around. This code more than likely can be made faster, and the
47 // frequency of which this method is called should be experimented with
48 // for optimum performance.
49 llvm::SmallVector
<const MemRegion
*, 10> RegionRoots
;
50 GRState NewState
= *state
;
52 NewState
.Env
= EnvMgr
.removeDeadBindings(NewState
.Env
, SymReaper
,
55 // Clean up the store.
56 NewState
.St
= StoreMgr
->removeDeadBindings(NewState
.St
, LCtx
,
57 SymReaper
, RegionRoots
);
58 state
= getPersistentState(NewState
);
59 return ConstraintMgr
->removeDeadBindings(state
, SymReaper
);
62 const GRState
*GRStateManager::MarshalState(const GRState
*state
,
63 const StackFrameContext
*InitLoc
) {
64 // make up an empty state for now.
66 EnvMgr
.getInitialEnvironment(),
67 StoreMgr
->getInitialStore(InitLoc
),
68 GDMFactory
.getEmptyMap());
70 return getPersistentState(State
);
73 const GRState
*GRState::bindCompoundLiteral(const CompoundLiteralExpr
* CL
,
74 const LocationContext
*LC
,
77 getStateManager().StoreMgr
->BindCompoundLiteral(St
, CL
, LC
, V
);
78 return makeWithStore(new_store
);
81 const GRState
*GRState::bindDecl(const VarRegion
* VR
, SVal IVal
) const {
82 Store new_store
= getStateManager().StoreMgr
->BindDecl(St
, VR
, IVal
);
83 return makeWithStore(new_store
);
86 const GRState
*GRState::bindDeclWithNoInit(const VarRegion
* VR
) const {
87 Store new_store
= getStateManager().StoreMgr
->BindDeclWithNoInit(St
, VR
);
88 return makeWithStore(new_store
);
91 const GRState
*GRState::bindLoc(Loc LV
, SVal V
) const {
92 GRStateManager
&Mgr
= getStateManager();
93 Store new_store
= Mgr
.StoreMgr
->Bind(St
, LV
, V
);
94 const GRState
*new_state
= makeWithStore(new_store
);
96 const MemRegion
*MR
= LV
.getAsRegion();
98 return Mgr
.getOwningEngine().processRegionChange(new_state
, MR
);
103 const GRState
*GRState::bindDefault(SVal loc
, SVal V
) const {
104 GRStateManager
&Mgr
= getStateManager();
105 const MemRegion
*R
= cast
<loc::MemRegionVal
>(loc
).getRegion();
106 Store new_store
= Mgr
.StoreMgr
->BindDefault(St
, R
, V
);
107 const GRState
*new_state
= makeWithStore(new_store
);
108 return Mgr
.getOwningEngine().processRegionChange(new_state
, R
);
111 const GRState
*GRState::InvalidateRegions(const MemRegion
* const *Begin
,
112 const MemRegion
* const *End
,
113 const Expr
*E
, unsigned Count
,
114 StoreManager::InvalidatedSymbols
*IS
,
115 bool invalidateGlobals
) const {
116 GRStateManager
&Mgr
= getStateManager();
117 SubEngine
&Eng
= Mgr
.getOwningEngine();
119 if (Eng
.wantsRegionChangeUpdate(this)) {
120 StoreManager::InvalidatedRegions Regions
;
122 Store new_store
= Mgr
.StoreMgr
->InvalidateRegions(St
, Begin
, End
,
126 const GRState
*new_state
= makeWithStore(new_store
);
128 return Eng
.processRegionChanges(new_state
,
133 Store new_store
= Mgr
.StoreMgr
->InvalidateRegions(St
, Begin
, End
,
137 return makeWithStore(new_store
);
140 const GRState
*GRState::unbindLoc(Loc LV
) const {
141 assert(!isa
<loc::MemRegionVal
>(LV
) && "Use InvalidateRegion instead.");
143 Store OldStore
= getStore();
144 Store NewStore
= getStateManager().StoreMgr
->Remove(OldStore
, LV
);
146 if (NewStore
== OldStore
)
149 return makeWithStore(NewStore
);
152 const GRState
*GRState::enterStackFrame(const StackFrameContext
*frame
) const {
153 Store new_store
= getStateManager().StoreMgr
->enterStackFrame(this, frame
);
154 return makeWithStore(new_store
);
157 SVal
GRState::getSValAsScalarOrLoc(const MemRegion
*R
) const {
158 // We only want to do fetches from regions that we can actually bind
159 // values. For example, SymbolicRegions of type 'id<...>' cannot
160 // have direct bindings (but their can be bindings on their subregions).
161 if (!R
->isBoundable())
164 if (const TypedRegion
*TR
= dyn_cast
<TypedRegion
>(R
)) {
165 QualType T
= TR
->getValueType();
166 if (Loc::IsLocType(T
) || T
->isIntegerType())
173 SVal
GRState::getSVal(Loc location
, QualType T
) const {
174 SVal V
= getRawSVal(cast
<Loc
>(location
), T
);
176 // If 'V' is a symbolic value that is *perfectly* constrained to
177 // be a constant value, use that value instead to lessen the burden
178 // on later analysis stages (so we have less symbolic values to reason
181 if (SymbolRef sym
= V
.getAsSymbol()) {
182 if (const llvm::APSInt
*Int
= getSymVal(sym
)) {
183 // FIXME: Because we don't correctly model (yet) sign-extension
184 // and truncation of symbolic values, we need to convert
185 // the integer value to the correct signedness and bitwidth.
187 // This shows up in the following:
190 // unsigned x = foo();
194 // The symbolic value stored to 'x' is actually the conjured
195 // symbol for the call to foo(); the type of that symbol is 'char',
197 const llvm::APSInt
&NewV
= getBasicVals().Convert(T
, *Int
);
200 return loc::ConcreteInt(NewV
);
202 return nonloc::ConcreteInt(NewV
);
210 const GRState
*GRState::BindExpr(const Stmt
* S
, SVal V
, bool Invalidate
) const{
211 Environment NewEnv
= getStateManager().EnvMgr
.bindExpr(Env
, S
, V
,
216 GRState NewSt
= *this;
218 return getStateManager().getPersistentState(NewSt
);
221 const GRState
*GRState::bindExprAndLocation(const Stmt
*S
, SVal location
,
224 getStateManager().EnvMgr
.bindExprAndLocation(Env
, S
, location
, V
);
229 GRState NewSt
= *this;
231 return getStateManager().getPersistentState(NewSt
);
234 const GRState
*GRState::assumeInBound(DefinedOrUnknownSVal Idx
,
235 DefinedOrUnknownSVal UpperBound
,
236 bool Assumption
) const {
237 if (Idx
.isUnknown() || UpperBound
.isUnknown())
240 // Build an expression for 0 <= Idx < UpperBound.
241 // This is the same as Idx + MIN < UpperBound + MIN, if overflow is allowed.
242 // FIXME: This should probably be part of SValBuilder.
243 GRStateManager
&SM
= getStateManager();
244 SValBuilder
&svalBuilder
= SM
.getSValBuilder();
245 ASTContext
&Ctx
= svalBuilder
.getContext();
247 // Get the offset: the minimum value of the array index type.
248 BasicValueFactory
&BVF
= svalBuilder
.getBasicValueFactory();
249 // FIXME: This should be using ValueManager::ArrayindexTy...somehow.
250 QualType indexTy
= Ctx
.IntTy
;
251 nonloc::ConcreteInt
Min(BVF
.getMinValue(indexTy
));
254 SVal newIdx
= svalBuilder
.evalBinOpNN(this, BO_Add
,
255 cast
<NonLoc
>(Idx
), Min
, indexTy
);
256 if (newIdx
.isUnknownOrUndef())
259 // Adjust the upper bound.
261 svalBuilder
.evalBinOpNN(this, BO_Add
, cast
<NonLoc
>(UpperBound
),
264 if (newBound
.isUnknownOrUndef())
267 // Build the actual comparison.
268 SVal inBound
= svalBuilder
.evalBinOpNN(this, BO_LT
,
269 cast
<NonLoc
>(newIdx
), cast
<NonLoc
>(newBound
),
271 if (inBound
.isUnknownOrUndef())
274 // Finally, let the constraint manager take care of it.
275 ConstraintManager
&CM
= SM
.getConstraintManager();
276 return CM
.assume(this, cast
<DefinedSVal
>(inBound
), Assumption
);
279 const GRState
* GRStateManager::getInitialState(const LocationContext
*InitLoc
) {
281 EnvMgr
.getInitialEnvironment(),
282 StoreMgr
->getInitialStore(InitLoc
),
283 GDMFactory
.getEmptyMap());
285 return getPersistentState(State
);
288 void GRStateManager::recycleUnusedStates() {
289 for (std::vector
<GRState
*>::iterator i
= recentlyAllocatedStates
.begin(),
290 e
= recentlyAllocatedStates
.end(); i
!= e
; ++i
) {
292 if (state
->referencedByExplodedNode())
294 StateSet
.RemoveNode(state
);
295 freeStates
.push_back(state
);
297 recentlyAllocatedStates
.clear();
300 const GRState
* GRStateManager::getPersistentState(GRState
& State
) {
302 llvm::FoldingSetNodeID ID
;
306 if (GRState
* I
= StateSet
.FindNodeOrInsertPos(ID
, InsertPos
))
309 GRState
*newState
= 0;
310 if (!freeStates
.empty()) {
311 newState
= freeStates
.back();
312 freeStates
.pop_back();
315 newState
= (GRState
*) Alloc
.Allocate
<GRState
>();
317 new (newState
) GRState(State
);
318 StateSet
.InsertNode(newState
, InsertPos
);
319 recentlyAllocatedStates
.push_back(newState
);
323 const GRState
* GRState::makeWithStore(Store store
) const {
324 GRState NewSt
= *this;
326 return getStateManager().getPersistentState(NewSt
);
329 //===----------------------------------------------------------------------===//
330 // State pretty-printing.
331 //===----------------------------------------------------------------------===//
333 static bool IsEnvLoc(const Stmt
*S
) {
334 // FIXME: This is a layering violation. Should be in environment.
335 return (bool) (((uintptr_t) S
) & 0x1);
338 void GRState::print(llvm::raw_ostream
& Out
, CFG
&C
, const char* nl
,
339 const char* sep
) const {
341 GRStateManager
&Mgr
= getStateManager();
342 Mgr
.getStoreManager().print(getStore(), Out
, nl
, sep
);
344 // Print Subexpression bindings.
347 // FIXME: All environment printing should be moved inside Environment.
348 for (Environment::iterator I
= Env
.begin(), E
= Env
.end(); I
!= E
; ++I
) {
349 if (C
.isBlkExpr(I
.getKey()) || IsEnvLoc(I
.getKey()))
353 Out
<< nl
<< nl
<< "Sub-Expressions:" << nl
;
358 Out
<< " (" << (void*) I
.getKey() << ") ";
359 LangOptions LO
; // FIXME.
360 I
.getKey()->printPretty(Out
, 0, PrintingPolicy(LO
));
361 Out
<< " : " << I
.getData();
364 // Print block-expression bindings.
367 for (Environment::iterator I
= Env
.begin(), E
= Env
.end(); I
!= E
; ++I
) {
368 if (!C
.isBlkExpr(I
.getKey()))
372 Out
<< nl
<< nl
<< "Block-level Expressions:" << nl
;
377 Out
<< " (" << (void*) I
.getKey() << ") ";
378 LangOptions LO
; // FIXME.
379 I
.getKey()->printPretty(Out
, 0, PrintingPolicy(LO
));
380 Out
<< " : " << I
.getData();
386 for (Environment::iterator I
= Env
.begin(), E
= Env
.end(); I
!= E
; ++I
) {
387 if (!IsEnvLoc(I
.getKey()))
391 Out
<< nl
<< nl
<< "Load/store locations:" << nl
;
396 const Stmt
*S
= (Stmt
*) (((uintptr_t) I
.getKey()) & ((uintptr_t) ~0x1));
398 Out
<< " (" << (void*) S
<< ") ";
399 LangOptions LO
; // FIXME.
400 S
->printPretty(Out
, 0, PrintingPolicy(LO
));
401 Out
<< " : " << I
.getData();
404 Mgr
.getConstraintManager().print(this, Out
, nl
, sep
);
406 // Print checker-specific data.
407 for (std::vector
<Printer
*>::iterator I
= Mgr
.Printers
.begin(),
408 E
= Mgr
.Printers
.end(); I
!= E
; ++I
) {
409 (*I
)->Print(Out
, this, nl
, sep
);
413 void GRState::printDOT(llvm::raw_ostream
& Out
, CFG
&C
) const {
414 print(Out
, C
, "\\l", "\\|");
417 void GRState::printStdErr(CFG
&C
) const {
418 print(llvm::errs(), C
);
421 //===----------------------------------------------------------------------===//
423 //===----------------------------------------------------------------------===//
425 void* const* GRState::FindGDM(void* K
) const {
426 return GDM
.lookup(K
);
430 GRStateManager::FindGDMContext(void* K
,
431 void* (*CreateContext
)(llvm::BumpPtrAllocator
&),
432 void (*DeleteContext
)(void*)) {
434 std::pair
<void*, void (*)(void*)>& p
= GDMContexts
[K
];
436 p
.first
= CreateContext(Alloc
);
437 p
.second
= DeleteContext
;
443 const GRState
* GRStateManager::addGDM(const GRState
* St
, void* Key
, void* Data
){
444 GRState::GenericDataMap M1
= St
->getGDM();
445 GRState::GenericDataMap M2
= GDMFactory
.add(M1
, Key
, Data
);
452 return getPersistentState(NewSt
);
455 const GRState
*GRStateManager::removeGDM(const GRState
*state
, void *Key
) {
456 GRState::GenericDataMap OldM
= state
->getGDM();
457 GRState::GenericDataMap NewM
= GDMFactory
.remove(OldM
, Key
);
462 GRState NewState
= *state
;
464 return getPersistentState(NewState
);
467 //===----------------------------------------------------------------------===//
469 //===----------------------------------------------------------------------===//
472 class ScanReachableSymbols
: public SubRegionMap::Visitor
{
473 typedef llvm::DenseSet
<const MemRegion
*> VisitedRegionsTy
;
475 VisitedRegionsTy visited
;
476 const GRState
*state
;
477 SymbolVisitor
&visitor
;
478 llvm::OwningPtr
<SubRegionMap
> SRM
;
481 ScanReachableSymbols(const GRState
*st
, SymbolVisitor
& v
)
482 : state(st
), visitor(v
) {}
484 bool scan(nonloc::CompoundVal val
);
486 bool scan(const MemRegion
*R
);
488 // From SubRegionMap::Visitor.
489 bool Visit(const MemRegion
* Parent
, const MemRegion
* SubRegion
) {
490 return scan(SubRegion
);
495 bool ScanReachableSymbols::scan(nonloc::CompoundVal val
) {
496 for (nonloc::CompoundVal::iterator I
=val
.begin(), E
=val
.end(); I
!=E
; ++I
)
503 bool ScanReachableSymbols::scan(SVal val
) {
504 if (loc::MemRegionVal
*X
= dyn_cast
<loc::MemRegionVal
>(&val
))
505 return scan(X
->getRegion());
507 if (nonloc::LocAsInteger
*X
= dyn_cast
<nonloc::LocAsInteger
>(&val
))
508 return scan(X
->getLoc());
510 if (SymbolRef Sym
= val
.getAsSymbol())
511 return visitor
.VisitSymbol(Sym
);
513 if (nonloc::CompoundVal
*X
= dyn_cast
<nonloc::CompoundVal
>(&val
))
519 bool ScanReachableSymbols::scan(const MemRegion
*R
) {
520 if (isa
<MemSpaceRegion
>(R
) || visited
.count(R
))
525 // If this is a symbolic region, visit the symbol for the region.
526 if (const SymbolicRegion
*SR
= dyn_cast
<SymbolicRegion
>(R
))
527 if (!visitor
.VisitSymbol(SR
->getSymbol()))
530 // If this is a subregion, also visit the parent regions.
531 if (const SubRegion
*SR
= dyn_cast
<SubRegion
>(R
))
532 if (!scan(SR
->getSuperRegion()))
535 // Now look at the binding to this region (if any).
536 if (!scan(state
->getSValAsScalarOrLoc(R
)))
539 // Now look at the subregions.
541 SRM
.reset(state
->getStateManager().getStoreManager().
542 getSubRegionMap(state
->getStore()));
544 return SRM
->iterSubRegions(R
, *this);
547 bool GRState::scanReachableSymbols(SVal val
, SymbolVisitor
& visitor
) const {
548 ScanReachableSymbols
S(this, visitor
);
552 bool GRState::scanReachableSymbols(const SVal
*I
, const SVal
*E
,
553 SymbolVisitor
&visitor
) const {
554 ScanReachableSymbols
S(this, visitor
);
555 for ( ; I
!= E
; ++I
) {
562 bool GRState::scanReachableSymbols(const MemRegion
* const *I
,
563 const MemRegion
* const *E
,
564 SymbolVisitor
&visitor
) const {
565 ScanReachableSymbols
S(this, visitor
);
566 for ( ; I
!= E
; ++I
) {