1 //== Environment.cpp - Map from Stmt* to Locations/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 defined the Environment and EnvironmentManager classes.
12 //===----------------------------------------------------------------------===//
14 #include "clang/Analysis/AnalysisContext.h"
15 #include "clang/Analysis/CFG.h"
16 #include "clang/StaticAnalyzer/PathSensitive/GRState.h"
18 using namespace clang
;
21 SVal
Environment::lookupExpr(const Stmt
* E
) const {
22 const SVal
* X
= ExprBindings
.lookup(E
);
30 SVal
Environment::getSVal(const Stmt
*E
, SValBuilder
& svalBuilder
) const {
32 switch (E
->getStmtClass()) {
33 case Stmt::AddrLabelExprClass
:
34 return svalBuilder
.makeLoc(cast
<AddrLabelExpr
>(E
));
35 case Stmt::ParenExprClass
:
36 // ParenExprs are no-ops.
37 E
= cast
<ParenExpr
>(E
)->getSubExpr();
39 case Stmt::CharacterLiteralClass
: {
40 const CharacterLiteral
* C
= cast
<CharacterLiteral
>(E
);
41 return svalBuilder
.makeIntVal(C
->getValue(), C
->getType());
43 case Stmt::CXXBoolLiteralExprClass
: {
44 const SVal
*X
= ExprBindings
.lookup(E
);
48 return svalBuilder
.makeIntVal(cast
<CXXBoolLiteralExpr
>(E
));
50 case Stmt::IntegerLiteralClass
: {
51 // In C++, this expression may have been bound to a temporary object.
52 SVal
const *X
= ExprBindings
.lookup(E
);
56 return svalBuilder
.makeIntVal(cast
<IntegerLiteral
>(E
));
58 case Stmt::ImplicitCastExprClass
:
59 case Stmt::CStyleCastExprClass
: {
60 // We blast through no-op casts to get the descendant
61 // subexpression that has a value.
62 const CastExpr
* C
= cast
<CastExpr
>(E
);
63 QualType CT
= C
->getType();
66 if (C
->getCastKind() == CK_NoOp
) {
72 case Stmt::ExprWithCleanupsClass
:
73 E
= cast
<ExprWithCleanups
>(E
)->getSubExpr();
75 case Stmt::CXXBindTemporaryExprClass
:
76 E
= cast
<CXXBindTemporaryExpr
>(E
)->getSubExpr();
78 case Stmt::CXXFunctionalCastExprClass
:
79 E
= cast
<CXXFunctionalCastExpr
>(E
)->getSubExpr();
81 // Handle all other Stmt* using a lookup.
90 Environment
EnvironmentManager::bindExpr(Environment Env
, const Stmt
*S
,
91 SVal V
, bool Invalidate
) {
96 return Environment(F
.remove(Env
.ExprBindings
, S
));
101 return Environment(F
.add(Env
.ExprBindings
, S
, V
));
104 static inline const Stmt
*MakeLocation(const Stmt
*S
) {
105 return (const Stmt
*) (((uintptr_t) S
) | 0x1);
108 Environment
EnvironmentManager::bindExprAndLocation(Environment Env
,
110 SVal location
, SVal V
) {
111 return Environment(F
.add(F
.add(Env
.ExprBindings
, MakeLocation(S
), location
),
116 class MarkLiveCallback
: public SymbolVisitor
{
117 SymbolReaper
&SymReaper
;
119 MarkLiveCallback(SymbolReaper
&symreaper
) : SymReaper(symreaper
) {}
120 bool VisitSymbol(SymbolRef sym
) { SymReaper
.markLive(sym
); return true; }
122 } // end anonymous namespace
124 static bool isBlockExprInCallers(const Stmt
*E
, const LocationContext
*LC
) {
125 const LocationContext
*ParentLC
= LC
->getParent();
127 CFG
&C
= *ParentLC
->getCFG();
130 ParentLC
= ParentLC
->getParent();
136 // In addition to mapping from Stmt * - > SVals in the Environment, we also
137 // maintain a mapping from Stmt * -> SVals (locations) that were used during
139 static inline bool IsLocation(const Stmt
*S
) {
140 return (bool) (((uintptr_t) S
) & 0x1);
143 // removeDeadBindings:
144 // - Remove subexpression bindings.
145 // - Remove dead block expression bindings.
146 // - Keep live block expression bindings:
147 // - Mark their reachable symbols live in SymbolReaper,
148 // see ScanReachableSymbols.
149 // - Mark the region in DRoots if the binding is a loc::MemRegionVal.
151 EnvironmentManager::removeDeadBindings(Environment Env
,
152 SymbolReaper
&SymReaper
,
154 llvm::SmallVectorImpl
<const MemRegion
*> &DRoots
) {
156 CFG
&C
= *SymReaper
.getLocationContext()->getCFG();
158 // We construct a new Environment object entirely, as this is cheaper than
159 // individually removing all the subexpression bindings (which will greatly
160 // outnumber block-level expression bindings).
161 Environment NewEnv
= getInitialEnvironment();
163 llvm::SmallVector
<std::pair
<const Stmt
*, SVal
>, 10> deferredLocations
;
165 // Iterate over the block-expr bindings.
166 for (Environment::iterator I
= Env
.begin(), E
= Env
.end();
169 const Stmt
*BlkExpr
= I
.getKey();
171 // For recorded locations (used when evaluating loads and stores), we
172 // consider them live only when their associated normal expression is
174 // NOTE: This assumes that loads/stores that evaluated to UnknownVal
175 // still have an entry in the map.
176 if (IsLocation(BlkExpr
)) {
177 deferredLocations
.push_back(std::make_pair(BlkExpr
, I
.getData()));
181 const SVal
&X
= I
.getData();
183 // Block-level expressions in callers are assumed always live.
184 if (isBlockExprInCallers(BlkExpr
, SymReaper
.getLocationContext())) {
185 NewEnv
.ExprBindings
= F
.add(NewEnv
.ExprBindings
, BlkExpr
, X
);
187 if (isa
<loc::MemRegionVal
>(X
)) {
188 const MemRegion
* R
= cast
<loc::MemRegionVal
>(X
).getRegion();
192 // Mark all symbols in the block expr's value live.
193 MarkLiveCallback
cb(SymReaper
);
194 ST
->scanReachableSymbols(X
, cb
);
198 // Not a block-level expression?
199 if (!C
.isBlkExpr(BlkExpr
))
202 if (SymReaper
.isLive(BlkExpr
)) {
203 // Copy the binding to the new map.
204 NewEnv
.ExprBindings
= F
.add(NewEnv
.ExprBindings
, BlkExpr
, X
);
206 // If the block expr's value is a memory region, then mark that region.
207 if (isa
<loc::MemRegionVal
>(X
)) {
208 const MemRegion
* R
= cast
<loc::MemRegionVal
>(X
).getRegion();
212 // Mark all symbols in the block expr's value live.
213 MarkLiveCallback
cb(SymReaper
);
214 ST
->scanReachableSymbols(X
, cb
);
218 // Otherwise the expression is dead with a couple exceptions.
219 // Do not misclean LogicalExpr or ConditionalOperator. It is dead at the
220 // beginning of itself, but we need its UndefinedVal to determine its
222 if (X
.isUndef() && cast
<UndefinedVal
>(X
).getData())
223 NewEnv
.ExprBindings
= F
.add(NewEnv
.ExprBindings
, BlkExpr
, X
);
226 // Go through he deferred locations and add them to the new environment if
227 // the correspond Stmt* is in the map as well.
228 for (llvm::SmallVectorImpl
<std::pair
<const Stmt
*, SVal
> >::iterator
229 I
= deferredLocations
.begin(), E
= deferredLocations
.end(); I
!= E
; ++I
) {
230 const Stmt
*S
= (Stmt
*) (((uintptr_t) I
->first
) & (uintptr_t) ~0x1);
231 if (NewEnv
.ExprBindings
.lookup(S
))
232 NewEnv
.ExprBindings
= F
.add(NewEnv
.ExprBindings
, I
->first
, I
->second
);