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/GR/PathSensitive/GRStateTrait.h"
16 #include "clang/GR/PathSensitive/GRState.h"
17 #include "clang/GR/PathSensitive/SubEngine.h"
18 #include "clang/GR/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 const GRState
* GRStateManager::getPersistentState(GRState
& State
) {
290 llvm::FoldingSetNodeID ID
;
294 if (GRState
* I
= StateSet
.FindNodeOrInsertPos(ID
, InsertPos
))
297 GRState
* I
= (GRState
*) Alloc
.Allocate
<GRState
>();
298 new (I
) GRState(State
);
299 StateSet
.InsertNode(I
, InsertPos
);
303 const GRState
* GRState::makeWithStore(Store store
) const {
304 GRState NewSt
= *this;
306 return getStateManager().getPersistentState(NewSt
);
309 //===----------------------------------------------------------------------===//
310 // State pretty-printing.
311 //===----------------------------------------------------------------------===//
313 static bool IsEnvLoc(const Stmt
*S
) {
314 // FIXME: This is a layering violation. Should be in environment.
315 return (bool) (((uintptr_t) S
) & 0x1);
318 void GRState::print(llvm::raw_ostream
& Out
, CFG
&C
, const char* nl
,
319 const char* sep
) const {
321 GRStateManager
&Mgr
= getStateManager();
322 Mgr
.getStoreManager().print(getStore(), Out
, nl
, sep
);
324 // Print Subexpression bindings.
327 // FIXME: All environment printing should be moved inside Environment.
328 for (Environment::iterator I
= Env
.begin(), E
= Env
.end(); I
!= E
; ++I
) {
329 if (C
.isBlkExpr(I
.getKey()) || IsEnvLoc(I
.getKey()))
333 Out
<< nl
<< nl
<< "Sub-Expressions:" << nl
;
338 Out
<< " (" << (void*) I
.getKey() << ") ";
339 LangOptions LO
; // FIXME.
340 I
.getKey()->printPretty(Out
, 0, PrintingPolicy(LO
));
341 Out
<< " : " << I
.getData();
344 // Print block-expression bindings.
347 for (Environment::iterator I
= Env
.begin(), E
= Env
.end(); I
!= E
; ++I
) {
348 if (!C
.isBlkExpr(I
.getKey()))
352 Out
<< nl
<< nl
<< "Block-level Expressions:" << nl
;
357 Out
<< " (" << (void*) I
.getKey() << ") ";
358 LangOptions LO
; // FIXME.
359 I
.getKey()->printPretty(Out
, 0, PrintingPolicy(LO
));
360 Out
<< " : " << I
.getData();
366 for (Environment::iterator I
= Env
.begin(), E
= Env
.end(); I
!= E
; ++I
) {
367 if (!IsEnvLoc(I
.getKey()))
371 Out
<< nl
<< nl
<< "Load/store locations:" << nl
;
376 const Stmt
*S
= (Stmt
*) (((uintptr_t) I
.getKey()) & ((uintptr_t) ~0x1));
378 Out
<< " (" << (void*) S
<< ") ";
379 LangOptions LO
; // FIXME.
380 S
->printPretty(Out
, 0, PrintingPolicy(LO
));
381 Out
<< " : " << I
.getData();
384 Mgr
.getConstraintManager().print(this, Out
, nl
, sep
);
386 // Print checker-specific data.
387 for (std::vector
<Printer
*>::iterator I
= Mgr
.Printers
.begin(),
388 E
= Mgr
.Printers
.end(); I
!= E
; ++I
) {
389 (*I
)->Print(Out
, this, nl
, sep
);
393 void GRState::printDOT(llvm::raw_ostream
& Out
, CFG
&C
) const {
394 print(Out
, C
, "\\l", "\\|");
397 void GRState::printStdErr(CFG
&C
) const {
398 print(llvm::errs(), C
);
401 //===----------------------------------------------------------------------===//
403 //===----------------------------------------------------------------------===//
405 void* const* GRState::FindGDM(void* K
) const {
406 return GDM
.lookup(K
);
410 GRStateManager::FindGDMContext(void* K
,
411 void* (*CreateContext
)(llvm::BumpPtrAllocator
&),
412 void (*DeleteContext
)(void*)) {
414 std::pair
<void*, void (*)(void*)>& p
= GDMContexts
[K
];
416 p
.first
= CreateContext(Alloc
);
417 p
.second
= DeleteContext
;
423 const GRState
* GRStateManager::addGDM(const GRState
* St
, void* Key
, void* Data
){
424 GRState::GenericDataMap M1
= St
->getGDM();
425 GRState::GenericDataMap M2
= GDMFactory
.add(M1
, Key
, Data
);
432 return getPersistentState(NewSt
);
435 const GRState
*GRStateManager::removeGDM(const GRState
*state
, void *Key
) {
436 GRState::GenericDataMap OldM
= state
->getGDM();
437 GRState::GenericDataMap NewM
= GDMFactory
.remove(OldM
, Key
);
442 GRState NewState
= *state
;
444 return getPersistentState(NewState
);
447 //===----------------------------------------------------------------------===//
449 //===----------------------------------------------------------------------===//
452 class ScanReachableSymbols
: public SubRegionMap::Visitor
{
453 typedef llvm::DenseSet
<const MemRegion
*> VisitedRegionsTy
;
455 VisitedRegionsTy visited
;
456 const GRState
*state
;
457 SymbolVisitor
&visitor
;
458 llvm::OwningPtr
<SubRegionMap
> SRM
;
461 ScanReachableSymbols(const GRState
*st
, SymbolVisitor
& v
)
462 : state(st
), visitor(v
) {}
464 bool scan(nonloc::CompoundVal val
);
466 bool scan(const MemRegion
*R
);
468 // From SubRegionMap::Visitor.
469 bool Visit(const MemRegion
* Parent
, const MemRegion
* SubRegion
) {
470 return scan(SubRegion
);
475 bool ScanReachableSymbols::scan(nonloc::CompoundVal val
) {
476 for (nonloc::CompoundVal::iterator I
=val
.begin(), E
=val
.end(); I
!=E
; ++I
)
483 bool ScanReachableSymbols::scan(SVal val
) {
484 if (loc::MemRegionVal
*X
= dyn_cast
<loc::MemRegionVal
>(&val
))
485 return scan(X
->getRegion());
487 if (nonloc::LocAsInteger
*X
= dyn_cast
<nonloc::LocAsInteger
>(&val
))
488 return scan(X
->getLoc());
490 if (SymbolRef Sym
= val
.getAsSymbol())
491 return visitor
.VisitSymbol(Sym
);
493 if (nonloc::CompoundVal
*X
= dyn_cast
<nonloc::CompoundVal
>(&val
))
499 bool ScanReachableSymbols::scan(const MemRegion
*R
) {
500 if (isa
<MemSpaceRegion
>(R
) || visited
.count(R
))
505 // If this is a symbolic region, visit the symbol for the region.
506 if (const SymbolicRegion
*SR
= dyn_cast
<SymbolicRegion
>(R
))
507 if (!visitor
.VisitSymbol(SR
->getSymbol()))
510 // If this is a subregion, also visit the parent regions.
511 if (const SubRegion
*SR
= dyn_cast
<SubRegion
>(R
))
512 if (!scan(SR
->getSuperRegion()))
515 // Now look at the binding to this region (if any).
516 if (!scan(state
->getSValAsScalarOrLoc(R
)))
519 // Now look at the subregions.
521 SRM
.reset(state
->getStateManager().getStoreManager().
522 getSubRegionMap(state
->getStore()));
524 return SRM
->iterSubRegions(R
, *this);
527 bool GRState::scanReachableSymbols(SVal val
, SymbolVisitor
& visitor
) const {
528 ScanReachableSymbols
S(this, visitor
);
532 bool GRState::scanReachableSymbols(const SVal
*I
, const SVal
*E
,
533 SymbolVisitor
&visitor
) const {
534 ScanReachableSymbols
S(this, visitor
);
535 for ( ; I
!= E
; ++I
) {
542 bool GRState::scanReachableSymbols(const MemRegion
* const *I
,
543 const MemRegion
* const *E
,
544 SymbolVisitor
&visitor
) const {
545 ScanReachableSymbols
S(this, visitor
);
546 for ( ; I
!= E
; ++I
) {