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/Checker/PathSensitive/GRStateTrait.h"
16 #include "clang/Checker/PathSensitive/GRState.h"
17 #include "clang/Checker/PathSensitive/GRSubEngine.h"
18 #include "clang/Checker/PathSensitive/GRTransferFuncs.h"
19 #include "llvm/Support/raw_ostream.h"
21 using namespace clang
;
23 // Give the vtable for ConstraintManager somewhere to live.
24 // FIXME: Move this elsewhere.
25 ConstraintManager::~ConstraintManager() {}
27 GRStateManager::~GRStateManager() {
28 for (std::vector
<GRState::Printer
*>::iterator I
=Printers
.begin(),
29 E
=Printers
.end(); I
!=E
; ++I
)
32 for (GDMContextsTy::iterator I
=GDMContexts
.begin(), E
=GDMContexts
.end();
34 I
->second
.second(I
->second
.first
);
38 GRStateManager::RemoveDeadBindings(const GRState
* state
,
39 const StackFrameContext
*LCtx
,
40 SymbolReaper
& SymReaper
) {
42 // This code essentially performs a "mark-and-sweep" of the VariableBindings.
43 // The roots are any Block-level exprs and Decls that our liveness algorithm
44 // tells us are live. We then see what Decls they may reference, and keep
45 // those around. This code more than likely can be made faster, and the
46 // frequency of which this method is called should be experimented with
47 // for optimum performance.
48 llvm::SmallVector
<const MemRegion
*, 10> RegionRoots
;
49 GRState NewState
= *state
;
51 NewState
.Env
= EnvMgr
.RemoveDeadBindings(NewState
.Env
, SymReaper
,
54 // Clean up the store.
55 NewState
.St
= StoreMgr
->RemoveDeadBindings(NewState
.St
, LCtx
,
56 SymReaper
, RegionRoots
);
57 state
= getPersistentState(NewState
);
58 return ConstraintMgr
->RemoveDeadBindings(state
, SymReaper
);
61 const GRState
*GRStateManager::MarshalState(const GRState
*state
,
62 const StackFrameContext
*InitLoc
) {
63 // make up an empty state for now.
65 EnvMgr
.getInitialEnvironment(),
66 StoreMgr
->getInitialStore(InitLoc
),
67 GDMFactory
.getEmptyMap());
69 return getPersistentState(State
);
72 const GRState
*GRState::bindCompoundLiteral(const CompoundLiteralExpr
* CL
,
73 const LocationContext
*LC
,
76 getStateManager().StoreMgr
->BindCompoundLiteral(St
, CL
, LC
, V
);
77 return makeWithStore(new_store
);
80 const GRState
*GRState::bindDecl(const VarRegion
* VR
, SVal IVal
) const {
81 Store new_store
= getStateManager().StoreMgr
->BindDecl(St
, VR
, IVal
);
82 return makeWithStore(new_store
);
85 const GRState
*GRState::bindDeclWithNoInit(const VarRegion
* VR
) const {
86 Store new_store
= getStateManager().StoreMgr
->BindDeclWithNoInit(St
, VR
);
87 return makeWithStore(new_store
);
90 const GRState
*GRState::bindLoc(Loc LV
, SVal V
) const {
91 GRStateManager
&Mgr
= getStateManager();
92 Store new_store
= Mgr
.StoreMgr
->Bind(St
, LV
, V
);
93 const GRState
*new_state
= makeWithStore(new_store
);
95 const MemRegion
*MR
= LV
.getAsRegion();
97 return Mgr
.getOwningEngine().ProcessRegionChange(new_state
, MR
);
102 const GRState
*GRState::bindDefault(SVal loc
, SVal V
) const {
103 GRStateManager
&Mgr
= getStateManager();
104 const MemRegion
*R
= cast
<loc::MemRegionVal
>(loc
).getRegion();
105 Store new_store
= Mgr
.StoreMgr
->BindDefault(St
, R
, V
);
106 const GRState
*new_state
= makeWithStore(new_store
);
107 return Mgr
.getOwningEngine().ProcessRegionChange(new_state
, R
);
110 const GRState
*GRState::InvalidateRegions(const MemRegion
* const *Begin
,
111 const MemRegion
* const *End
,
112 const Expr
*E
, unsigned Count
,
113 StoreManager::InvalidatedSymbols
*IS
,
114 bool invalidateGlobals
) const {
115 GRStateManager
&Mgr
= getStateManager();
116 GRSubEngine
&Eng
= Mgr
.getOwningEngine();
118 if (Eng
.WantsRegionChangeUpdate(this)) {
119 StoreManager::InvalidatedRegions Regions
;
121 Store new_store
= Mgr
.StoreMgr
->InvalidateRegions(St
, Begin
, End
,
125 const GRState
*new_state
= makeWithStore(new_store
);
127 return Eng
.ProcessRegionChanges(new_state
,
132 Store new_store
= Mgr
.StoreMgr
->InvalidateRegions(St
, Begin
, End
,
136 return makeWithStore(new_store
);
139 const GRState
*GRState::unbindLoc(Loc LV
) const {
140 assert(!isa
<loc::MemRegionVal
>(LV
) && "Use InvalidateRegion instead.");
142 Store OldStore
= getStore();
143 Store NewStore
= getStateManager().StoreMgr
->Remove(OldStore
, LV
);
145 if (NewStore
== OldStore
)
148 return makeWithStore(NewStore
);
151 const GRState
*GRState::EnterStackFrame(const StackFrameContext
*frame
) const {
152 Store new_store
= getStateManager().StoreMgr
->EnterStackFrame(this, frame
);
153 return makeWithStore(new_store
);
156 SVal
GRState::getSValAsScalarOrLoc(const MemRegion
*R
) const {
157 // We only want to do fetches from regions that we can actually bind
158 // values. For example, SymbolicRegions of type 'id<...>' cannot
159 // have direct bindings (but their can be bindings on their subregions).
160 if (!R
->isBoundable())
163 if (const TypedRegion
*TR
= dyn_cast
<TypedRegion
>(R
)) {
164 QualType T
= TR
->getValueType();
165 if (Loc::IsLocType(T
) || T
->isIntegerType())
172 SVal
GRState::getSVal(Loc location
, QualType T
) const {
173 SVal V
= getRawSVal(cast
<Loc
>(location
), T
);
175 // If 'V' is a symbolic value that is *perfectly* constrained to
176 // be a constant value, use that value instead to lessen the burden
177 // on later analysis stages (so we have less symbolic values to reason
180 if (SymbolRef sym
= V
.getAsSymbol()) {
181 if (const llvm::APSInt
*Int
= getSymVal(sym
)) {
182 // FIXME: Because we don't correctly model (yet) sign-extension
183 // and truncation of symbolic values, we need to convert
184 // the integer value to the correct signedness and bitwidth.
186 // This shows up in the following:
189 // unsigned x = foo();
193 // The symbolic value stored to 'x' is actually the conjured
194 // symbol for the call to foo(); the type of that symbol is 'char',
196 const llvm::APSInt
&NewV
= getBasicVals().Convert(T
, *Int
);
199 return loc::ConcreteInt(NewV
);
201 return nonloc::ConcreteInt(NewV
);
209 const GRState
*GRState::BindExpr(const Stmt
* S
, SVal V
, bool Invalidate
) const{
210 Environment NewEnv
= getStateManager().EnvMgr
.bindExpr(Env
, S
, V
,
215 GRState NewSt
= *this;
217 return getStateManager().getPersistentState(NewSt
);
220 const GRState
*GRState::bindExprAndLocation(const Stmt
*S
, SVal location
,
223 getStateManager().EnvMgr
.bindExprAndLocation(Env
, S
, location
, V
);
228 GRState NewSt
= *this;
230 return getStateManager().getPersistentState(NewSt
);
233 const GRState
*GRState::AssumeInBound(DefinedOrUnknownSVal Idx
,
234 DefinedOrUnknownSVal UpperBound
,
235 bool Assumption
) const {
236 if (Idx
.isUnknown() || UpperBound
.isUnknown())
239 // Build an expression for 0 <= Idx < UpperBound.
240 // This is the same as Idx + MIN < UpperBound + MIN, if overflow is allowed.
241 // FIXME: This should probably be part of SValBuilder.
242 GRStateManager
&SM
= getStateManager();
243 ValueManager
&VM
= SM
.getValueManager();
244 SValBuilder
&SV
= VM
.getSValBuilder();
245 ASTContext
&Ctx
= VM
.getContext();
247 // Get the offset: the minimum value of the array index type.
248 BasicValueFactory
&BVF
= VM
.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
= SV
.EvalBinOpNN(this, BO_Add
,
255 cast
<NonLoc
>(Idx
), Min
, IndexTy
);
256 if (NewIdx
.isUnknownOrUndef())
259 // Adjust the upper bound.
260 SVal NewBound
= SV
.EvalBinOpNN(this, BO_Add
,
261 cast
<NonLoc
>(UpperBound
), Min
, IndexTy
);
262 if (NewBound
.isUnknownOrUndef())
265 // Build the actual comparison.
266 SVal InBound
= SV
.EvalBinOpNN(this, BO_LT
,
267 cast
<NonLoc
>(NewIdx
), cast
<NonLoc
>(NewBound
),
269 if (InBound
.isUnknownOrUndef())
272 // Finally, let the constraint manager take care of it.
273 ConstraintManager
&CM
= SM
.getConstraintManager();
274 return CM
.Assume(this, cast
<DefinedSVal
>(InBound
), Assumption
);
277 const GRState
* GRStateManager::getInitialState(const LocationContext
*InitLoc
) {
279 EnvMgr
.getInitialEnvironment(),
280 StoreMgr
->getInitialStore(InitLoc
),
281 GDMFactory
.getEmptyMap());
283 return getPersistentState(State
);
286 const GRState
* GRStateManager::getPersistentState(GRState
& State
) {
288 llvm::FoldingSetNodeID ID
;
292 if (GRState
* I
= StateSet
.FindNodeOrInsertPos(ID
, InsertPos
))
295 GRState
* I
= (GRState
*) Alloc
.Allocate
<GRState
>();
296 new (I
) GRState(State
);
297 StateSet
.InsertNode(I
, InsertPos
);
301 const GRState
* GRState::makeWithStore(Store store
) const {
302 GRState NewSt
= *this;
304 return getStateManager().getPersistentState(NewSt
);
307 //===----------------------------------------------------------------------===//
308 // State pretty-printing.
309 //===----------------------------------------------------------------------===//
311 static bool IsEnvLoc(const Stmt
*S
) {
312 // FIXME: This is a layering violation. Should be in environment.
313 return (bool) (((uintptr_t) S
) & 0x1);
316 void GRState::print(llvm::raw_ostream
& Out
, CFG
&C
, const char* nl
,
317 const char* sep
) const {
319 GRStateManager
&Mgr
= getStateManager();
320 Mgr
.getStoreManager().print(getStore(), Out
, nl
, sep
);
322 // Print Subexpression bindings.
325 // FIXME: All environment printing should be moved inside Environment.
326 for (Environment::iterator I
= Env
.begin(), E
= Env
.end(); I
!= E
; ++I
) {
327 if (C
.isBlkExpr(I
.getKey()) || IsEnvLoc(I
.getKey()))
331 Out
<< nl
<< nl
<< "Sub-Expressions:" << nl
;
336 Out
<< " (" << (void*) I
.getKey() << ") ";
337 LangOptions LO
; // FIXME.
338 I
.getKey()->printPretty(Out
, 0, PrintingPolicy(LO
));
339 Out
<< " : " << I
.getData();
342 // Print block-expression bindings.
345 for (Environment::iterator I
= Env
.begin(), E
= Env
.end(); I
!= E
; ++I
) {
346 if (!C
.isBlkExpr(I
.getKey()))
350 Out
<< nl
<< nl
<< "Block-level Expressions:" << nl
;
355 Out
<< " (" << (void*) I
.getKey() << ") ";
356 LangOptions LO
; // FIXME.
357 I
.getKey()->printPretty(Out
, 0, PrintingPolicy(LO
));
358 Out
<< " : " << I
.getData();
364 for (Environment::iterator I
= Env
.begin(), E
= Env
.end(); I
!= E
; ++I
) {
365 if (!IsEnvLoc(I
.getKey()))
369 Out
<< nl
<< nl
<< "Load/store locations:" << nl
;
374 const Stmt
*S
= (Stmt
*) (((uintptr_t) I
.getKey()) & ((uintptr_t) ~0x1));
376 Out
<< " (" << (void*) S
<< ") ";
377 LangOptions LO
; // FIXME.
378 S
->printPretty(Out
, 0, PrintingPolicy(LO
));
379 Out
<< " : " << I
.getData();
382 Mgr
.getConstraintManager().print(this, Out
, nl
, sep
);
384 // Print checker-specific data.
385 for (std::vector
<Printer
*>::iterator I
= Mgr
.Printers
.begin(),
386 E
= Mgr
.Printers
.end(); I
!= E
; ++I
) {
387 (*I
)->Print(Out
, this, nl
, sep
);
391 void GRState::printDOT(llvm::raw_ostream
& Out
, CFG
&C
) const {
392 print(Out
, C
, "\\l", "\\|");
395 void GRState::printStdErr(CFG
&C
) const {
396 print(llvm::errs(), C
);
399 //===----------------------------------------------------------------------===//
401 //===----------------------------------------------------------------------===//
403 void* const* GRState::FindGDM(void* K
) const {
404 return GDM
.lookup(K
);
408 GRStateManager::FindGDMContext(void* K
,
409 void* (*CreateContext
)(llvm::BumpPtrAllocator
&),
410 void (*DeleteContext
)(void*)) {
412 std::pair
<void*, void (*)(void*)>& p
= GDMContexts
[K
];
414 p
.first
= CreateContext(Alloc
);
415 p
.second
= DeleteContext
;
421 const GRState
* GRStateManager::addGDM(const GRState
* St
, void* Key
, void* Data
){
422 GRState::GenericDataMap M1
= St
->getGDM();
423 GRState::GenericDataMap M2
= GDMFactory
.add(M1
, Key
, Data
);
430 return getPersistentState(NewSt
);
433 const GRState
*GRStateManager::removeGDM(const GRState
*state
, void *Key
) {
434 GRState::GenericDataMap OldM
= state
->getGDM();
435 GRState::GenericDataMap NewM
= GDMFactory
.remove(OldM
, Key
);
440 GRState NewState
= *state
;
442 return getPersistentState(NewState
);
445 //===----------------------------------------------------------------------===//
447 //===----------------------------------------------------------------------===//
450 class ScanReachableSymbols
: public SubRegionMap::Visitor
{
451 typedef llvm::DenseSet
<const MemRegion
*> VisitedRegionsTy
;
453 VisitedRegionsTy visited
;
454 const GRState
*state
;
455 SymbolVisitor
&visitor
;
456 llvm::OwningPtr
<SubRegionMap
> SRM
;
459 ScanReachableSymbols(const GRState
*st
, SymbolVisitor
& v
)
460 : state(st
), visitor(v
) {}
462 bool scan(nonloc::CompoundVal val
);
464 bool scan(const MemRegion
*R
);
466 // From SubRegionMap::Visitor.
467 bool Visit(const MemRegion
* Parent
, const MemRegion
* SubRegion
) {
468 return scan(SubRegion
);
473 bool ScanReachableSymbols::scan(nonloc::CompoundVal val
) {
474 for (nonloc::CompoundVal::iterator I
=val
.begin(), E
=val
.end(); I
!=E
; ++I
)
481 bool ScanReachableSymbols::scan(SVal val
) {
482 if (loc::MemRegionVal
*X
= dyn_cast
<loc::MemRegionVal
>(&val
))
483 return scan(X
->getRegion());
485 if (nonloc::LocAsInteger
*X
= dyn_cast
<nonloc::LocAsInteger
>(&val
))
486 return scan(X
->getLoc());
488 if (SymbolRef Sym
= val
.getAsSymbol())
489 return visitor
.VisitSymbol(Sym
);
491 if (nonloc::CompoundVal
*X
= dyn_cast
<nonloc::CompoundVal
>(&val
))
497 bool ScanReachableSymbols::scan(const MemRegion
*R
) {
498 if (isa
<MemSpaceRegion
>(R
) || visited
.count(R
))
503 // If this is a symbolic region, visit the symbol for the region.
504 if (const SymbolicRegion
*SR
= dyn_cast
<SymbolicRegion
>(R
))
505 if (!visitor
.VisitSymbol(SR
->getSymbol()))
508 // If this is a subregion, also visit the parent regions.
509 if (const SubRegion
*SR
= dyn_cast
<SubRegion
>(R
))
510 if (!scan(SR
->getSuperRegion()))
513 // Now look at the binding to this region (if any).
514 if (!scan(state
->getSValAsScalarOrLoc(R
)))
517 // Now look at the subregions.
519 SRM
.reset(state
->getStateManager().getStoreManager().
520 getSubRegionMap(state
->getStore()));
522 return SRM
->iterSubRegions(R
, *this);
525 bool GRState::scanReachableSymbols(SVal val
, SymbolVisitor
& visitor
) const {
526 ScanReachableSymbols
S(this, visitor
);
530 bool GRState::scanReachableSymbols(const SVal
*I
, const SVal
*E
,
531 SymbolVisitor
&visitor
) const {
532 ScanReachableSymbols
S(this, visitor
);
533 for ( ; I
!= E
; ++I
) {
540 bool GRState::scanReachableSymbols(const MemRegion
* const *I
,
541 const MemRegion
* const *E
,
542 SymbolVisitor
&visitor
) const {
543 ScanReachableSymbols
S(this, visitor
);
544 for ( ; I
!= E
; ++I
) {