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/GR/PathSensitive/GRState.h"
18 using namespace clang
;
20 SVal
Environment::lookupExpr(const Stmt
* E
) const {
21 const SVal
* X
= ExprBindings
.lookup(E
);
29 SVal
Environment::getSVal(const Stmt
*E
, SValBuilder
& svalBuilder
) const {
31 switch (E
->getStmtClass()) {
32 case Stmt::AddrLabelExprClass
:
33 return svalBuilder
.makeLoc(cast
<AddrLabelExpr
>(E
));
34 case Stmt::ParenExprClass
:
35 // ParenExprs are no-ops.
36 E
= cast
<ParenExpr
>(E
)->getSubExpr();
38 case Stmt::CharacterLiteralClass
: {
39 const CharacterLiteral
* C
= cast
<CharacterLiteral
>(E
);
40 return svalBuilder
.makeIntVal(C
->getValue(), C
->getType());
42 case Stmt::CXXBoolLiteralExprClass
: {
43 const SVal
*X
= ExprBindings
.lookup(E
);
47 return svalBuilder
.makeIntVal(cast
<CXXBoolLiteralExpr
>(E
));
49 case Stmt::IntegerLiteralClass
: {
50 // In C++, this expression may have been bound to a temporary object.
51 SVal
const *X
= ExprBindings
.lookup(E
);
55 return svalBuilder
.makeIntVal(cast
<IntegerLiteral
>(E
));
57 case Stmt::ImplicitCastExprClass
:
58 case Stmt::CStyleCastExprClass
: {
59 // We blast through no-op casts to get the descendant
60 // subexpression that has a value.
61 const CastExpr
* C
= cast
<CastExpr
>(E
);
62 QualType CT
= C
->getType();
65 if (C
->getCastKind() == CK_NoOp
) {
71 case Stmt::ExprWithCleanupsClass
:
72 E
= cast
<ExprWithCleanups
>(E
)->getSubExpr();
74 case Stmt::CXXBindTemporaryExprClass
:
75 E
= cast
<CXXBindTemporaryExpr
>(E
)->getSubExpr();
77 case Stmt::CXXFunctionalCastExprClass
:
78 E
= cast
<CXXFunctionalCastExpr
>(E
)->getSubExpr();
80 // Handle all other Stmt* using a lookup.
89 Environment
EnvironmentManager::bindExpr(Environment Env
, const Stmt
*S
,
90 SVal V
, bool Invalidate
) {
95 return Environment(F
.remove(Env
.ExprBindings
, S
));
100 return Environment(F
.add(Env
.ExprBindings
, S
, V
));
103 static inline const Stmt
*MakeLocation(const Stmt
*S
) {
104 return (const Stmt
*) (((uintptr_t) S
) | 0x1);
107 Environment
EnvironmentManager::bindExprAndLocation(Environment Env
,
109 SVal location
, SVal V
) {
110 return Environment(F
.add(F
.add(Env
.ExprBindings
, MakeLocation(S
), location
),
115 class MarkLiveCallback
: public SymbolVisitor
{
116 SymbolReaper
&SymReaper
;
118 MarkLiveCallback(SymbolReaper
&symreaper
) : SymReaper(symreaper
) {}
119 bool VisitSymbol(SymbolRef sym
) { SymReaper
.markLive(sym
); return true; }
121 } // end anonymous namespace
123 static bool isBlockExprInCallers(const Stmt
*E
, const LocationContext
*LC
) {
124 const LocationContext
*ParentLC
= LC
->getParent();
126 CFG
&C
= *ParentLC
->getCFG();
129 ParentLC
= ParentLC
->getParent();
135 // In addition to mapping from Stmt * - > SVals in the Environment, we also
136 // maintain a mapping from Stmt * -> SVals (locations) that were used during
138 static inline bool IsLocation(const Stmt
*S
) {
139 return (bool) (((uintptr_t) S
) & 0x1);
142 // RemoveDeadBindings:
143 // - Remove subexpression bindings.
144 // - Remove dead block expression bindings.
145 // - Keep live block expression bindings:
146 // - Mark their reachable symbols live in SymbolReaper,
147 // see ScanReachableSymbols.
148 // - Mark the region in DRoots if the binding is a loc::MemRegionVal.
150 EnvironmentManager::RemoveDeadBindings(Environment Env
,
151 SymbolReaper
&SymReaper
,
153 llvm::SmallVectorImpl
<const MemRegion
*> &DRoots
) {
155 CFG
&C
= *SymReaper
.getLocationContext()->getCFG();
157 // We construct a new Environment object entirely, as this is cheaper than
158 // individually removing all the subexpression bindings (which will greatly
159 // outnumber block-level expression bindings).
160 Environment NewEnv
= getInitialEnvironment();
162 llvm::SmallVector
<std::pair
<const Stmt
*, SVal
>, 10> deferredLocations
;
164 // Iterate over the block-expr bindings.
165 for (Environment::iterator I
= Env
.begin(), E
= Env
.end();
168 const Stmt
*BlkExpr
= I
.getKey();
170 // For recorded locations (used when evaluating loads and stores), we
171 // consider them live only when their associated normal expression is
173 // NOTE: This assumes that loads/stores that evaluated to UnknownVal
174 // still have an entry in the map.
175 if (IsLocation(BlkExpr
)) {
176 deferredLocations
.push_back(std::make_pair(BlkExpr
, I
.getData()));
180 const SVal
&X
= I
.getData();
182 // Block-level expressions in callers are assumed always live.
183 if (isBlockExprInCallers(BlkExpr
, SymReaper
.getLocationContext())) {
184 NewEnv
.ExprBindings
= F
.add(NewEnv
.ExprBindings
, BlkExpr
, X
);
186 if (isa
<loc::MemRegionVal
>(X
)) {
187 const MemRegion
* R
= cast
<loc::MemRegionVal
>(X
).getRegion();
191 // Mark all symbols in the block expr's value live.
192 MarkLiveCallback
cb(SymReaper
);
193 ST
->scanReachableSymbols(X
, cb
);
197 // Not a block-level expression?
198 if (!C
.isBlkExpr(BlkExpr
))
201 if (SymReaper
.isLive(BlkExpr
)) {
202 // Copy the binding to the new map.
203 NewEnv
.ExprBindings
= F
.add(NewEnv
.ExprBindings
, BlkExpr
, X
);
205 // If the block expr's value is a memory region, then mark that region.
206 if (isa
<loc::MemRegionVal
>(X
)) {
207 const MemRegion
* R
= cast
<loc::MemRegionVal
>(X
).getRegion();
211 // Mark all symbols in the block expr's value live.
212 MarkLiveCallback
cb(SymReaper
);
213 ST
->scanReachableSymbols(X
, cb
);
217 // Otherwise the expression is dead with a couple exceptions.
218 // Do not misclean LogicalExpr or ConditionalOperator. It is dead at the
219 // beginning of itself, but we need its UndefinedVal to determine its
221 if (X
.isUndef() && cast
<UndefinedVal
>(X
).getData())
222 NewEnv
.ExprBindings
= F
.add(NewEnv
.ExprBindings
, BlkExpr
, X
);
225 // Go through he deferred locations and add them to the new environment if
226 // the correspond Stmt* is in the map as well.
227 for (llvm::SmallVectorImpl
<std::pair
<const Stmt
*, SVal
> >::iterator
228 I
= deferredLocations
.begin(), E
= deferredLocations
.end(); I
!= E
; ++I
) {
229 const Stmt
*S
= (Stmt
*) (((uintptr_t) I
->first
) & (uintptr_t) ~0x1);
230 if (NewEnv
.ExprBindings
.lookup(S
))
231 NewEnv
.ExprBindings
= F
.add(NewEnv
.ExprBindings
, I
->first
, I
->second
);