Environment.cpp revision 84c484545c5906ba55143e212b4a5275ab55889f 
1//== Environment.cpp - Map from Stmt* to Locations/Values -------*- C++ -*--==//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10//  This file defined the Environment and EnvironmentManager classes.
11//
12//===----------------------------------------------------------------------===//
13
14#include "clang/AST/ExprCXX.h"
15#include "clang/AST/ExprObjC.h"
16#include "clang/Analysis/AnalysisContext.h"
17#include "clang/Analysis/CFG.h"
18#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
19
20using namespace clang;
21using namespace ento;
22
23static const Expr *ignoreTransparentExprs(const Expr *E) {
24  E = E->IgnoreParens();
25
26  switch (E->getStmtClass()) {
27  case Stmt::OpaqueValueExprClass:
28    E = cast<OpaqueValueExpr>(E)->getSourceExpr();
29    break;
30  case Stmt::ExprWithCleanupsClass:
31    E = cast<ExprWithCleanups>(E)->getSubExpr();
32    break;
33  case Stmt::CXXBindTemporaryExprClass:
34    E = cast<CXXBindTemporaryExpr>(E)->getSubExpr();
35    break;
36  case Stmt::SubstNonTypeTemplateParmExprClass:
37    E = cast<SubstNonTypeTemplateParmExpr>(E)->getReplacement();
38    break;
39  case Stmt::CXXDefaultArgExprClass:
40    E = cast<CXXDefaultArgExpr>(E)->getExpr();
41    break;
42  default:
43    // This is the base case: we can't look through more than we already have.
44    return E;
45  }
46
47  return ignoreTransparentExprs(E);
48}
49
50static const Stmt *ignoreTransparentExprs(const Stmt *S) {
51  if (const Expr *E = dyn_cast<Expr>(S))
52    return ignoreTransparentExprs(E);
53  return S;
54}
55
56EnvironmentEntry::EnvironmentEntry(const Stmt *S, const LocationContext *L)
57  : std::pair<const Stmt *,
58              const StackFrameContext *>(ignoreTransparentExprs(S),
59                                         L ? L->getCurrentStackFrame() : 0) {}
60
61SVal Environment::lookupExpr(const EnvironmentEntry &E) const {
62  const SVal* X = ExprBindings.lookup(E);
63  if (X) {
64    SVal V = *X;
65    return V;
66  }
67  return UnknownVal();
68}
69
70SVal Environment::getSVal(const EnvironmentEntry &Entry,
71                          SValBuilder& svalBuilder) const {
72  const Stmt *S = Entry.getStmt();
73  const LocationContext *LCtx = Entry.getLocationContext();
74
75  switch (S->getStmtClass()) {
76  case Stmt::CXXBindTemporaryExprClass:
77  case Stmt::CXXDefaultArgExprClass:
78  case Stmt::ExprWithCleanupsClass:
79  case Stmt::GenericSelectionExprClass:
80  case Stmt::OpaqueValueExprClass:
81  case Stmt::ParenExprClass:
82  case Stmt::SubstNonTypeTemplateParmExprClass:
83    llvm_unreachable("Should have been handled by ignoreTransparentExprs");
84
85  case Stmt::AddrLabelExprClass:
86    return svalBuilder.makeLoc(cast<AddrLabelExpr>(S));
87
88  case Stmt::CharacterLiteralClass: {
89    const CharacterLiteral *C = cast<CharacterLiteral>(S);
90    return svalBuilder.makeIntVal(C->getValue(), C->getType());
91  }
92
93  case Stmt::CXXBoolLiteralExprClass:
94    return svalBuilder.makeBoolVal(cast<CXXBoolLiteralExpr>(S));
95
96  case Stmt::CXXScalarValueInitExprClass:
97  case Stmt::ImplicitValueInitExprClass: {
98    QualType Ty = cast<Expr>(S)->getType();
99    return svalBuilder.makeZeroVal(Ty);
100  }
101
102  case Stmt::IntegerLiteralClass:
103    return svalBuilder.makeIntVal(cast<IntegerLiteral>(S));
104
105  case Stmt::ObjCBoolLiteralExprClass:
106    return svalBuilder.makeBoolVal(cast<ObjCBoolLiteralExpr>(S));
107
108  // For special C0xx nullptr case, make a null pointer SVal.
109  case Stmt::CXXNullPtrLiteralExprClass:
110    return svalBuilder.makeNull();
111
112  case Stmt::ObjCStringLiteralClass: {
113    MemRegionManager &MRMgr = svalBuilder.getRegionManager();
114    const ObjCStringLiteral *SL = cast<ObjCStringLiteral>(S);
115    return svalBuilder.makeLoc(MRMgr.getObjCStringRegion(SL));
116  }
117
118  case Stmt::StringLiteralClass: {
119    MemRegionManager &MRMgr = svalBuilder.getRegionManager();
120    const StringLiteral *SL = cast<StringLiteral>(S);
121    return svalBuilder.makeLoc(MRMgr.getStringRegion(SL));
122  }
123
124  case Stmt::ReturnStmtClass: {
125    const ReturnStmt *RS = cast<ReturnStmt>(S);
126    if (const Expr *RE = RS->getRetValue())
127      return getSVal(EnvironmentEntry(RE, LCtx), svalBuilder);
128    return UndefinedVal();
129  }
130
131  // Handle all other Stmt* using a lookup.
132  default:
133    break;
134  }
135
136  return lookupExpr(EnvironmentEntry(S, LCtx));
137}
138
139Environment EnvironmentManager::bindExpr(Environment Env,
140                                         const EnvironmentEntry &E,
141                                         SVal V,
142                                         bool Invalidate) {
143  if (V.isUnknown()) {
144    if (Invalidate)
145      return Environment(F.remove(Env.ExprBindings, E));
146    else
147      return Env;
148  }
149  return Environment(F.add(Env.ExprBindings, E, V));
150}
151
152EnvironmentEntry EnvironmentEntry::makeLocation() const {
153  EnvironmentEntry Result = *this;
154  reinterpret_cast<uintptr_t &>(Result.first) |= 0x1;
155  return Result;
156}
157
158Environment EnvironmentManager::bindExprAndLocation(Environment Env,
159                                                    const EnvironmentEntry &E,
160                                                    SVal location, SVal V) {
161  return Environment(F.add(F.add(Env.ExprBindings, E.makeLocation(), location),
162                           E, V));
163}
164
165namespace {
166class MarkLiveCallback : public SymbolVisitor {
167  SymbolReaper &SymReaper;
168public:
169  MarkLiveCallback(SymbolReaper &symreaper) : SymReaper(symreaper) {}
170  bool VisitSymbol(SymbolRef sym) {
171    SymReaper.markLive(sym);
172    return true;
173  }
174  bool VisitMemRegion(const MemRegion *R) {
175    SymReaper.markLive(R);
176    return true;
177  }
178};
179} // end anonymous namespace
180
181// In addition to mapping from EnvironmentEntry - > SVals in the Environment,
182// we also maintain a mapping from EnvironmentEntry -> SVals (locations)
183// that were used during a load and store.
184static inline bool IsLocation(const EnvironmentEntry &E) {
185  const Stmt *S = E.getStmt();
186  return (bool) (((uintptr_t) S) & 0x1);
187}
188
189// removeDeadBindings:
190//  - Remove subexpression bindings.
191//  - Remove dead block expression bindings.
192//  - Keep live block expression bindings:
193//   - Mark their reachable symbols live in SymbolReaper,
194//     see ScanReachableSymbols.
195//   - Mark the region in DRoots if the binding is a loc::MemRegionVal.
196Environment
197EnvironmentManager::removeDeadBindings(Environment Env,
198                                       SymbolReaper &SymReaper,
199                                       ProgramStateRef ST) {
200
201  // We construct a new Environment object entirely, as this is cheaper than
202  // individually removing all the subexpression bindings (which will greatly
203  // outnumber block-level expression bindings).
204  Environment NewEnv = getInitialEnvironment();
205
206  SmallVector<std::pair<EnvironmentEntry, SVal>, 10> deferredLocations;
207
208  MarkLiveCallback CB(SymReaper);
209  ScanReachableSymbols RSScaner(ST, CB);
210
211  llvm::ImmutableMapRef<EnvironmentEntry,SVal>
212    EBMapRef(NewEnv.ExprBindings.getRootWithoutRetain(),
213             F.getTreeFactory());
214
215  // Iterate over the block-expr bindings.
216  for (Environment::iterator I = Env.begin(), E = Env.end();
217       I != E; ++I) {
218
219    const EnvironmentEntry &BlkExpr = I.getKey();
220    // For recorded locations (used when evaluating loads and stores), we
221    // consider them live only when their associated normal expression is
222    // also live.
223    // NOTE: This assumes that loads/stores that evaluated to UnknownVal
224    // still have an entry in the map.
225    if (IsLocation(BlkExpr)) {
226      deferredLocations.push_back(std::make_pair(BlkExpr, I.getData()));
227      continue;
228    }
229    const SVal &X = I.getData();
230
231    if (SymReaper.isLive(BlkExpr.getStmt(), BlkExpr.getLocationContext())) {
232      // Copy the binding to the new map.
233      EBMapRef = EBMapRef.add(BlkExpr, X);
234
235      // If the block expr's value is a memory region, then mark that region.
236      if (isa<loc::MemRegionVal>(X)) {
237        const MemRegion *R = cast<loc::MemRegionVal>(X).getRegion();
238        SymReaper.markLive(R);
239      }
240
241      // Mark all symbols in the block expr's value live.
242      RSScaner.scan(X);
243      continue;
244    } else {
245      SymExpr::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
246      for (; SI != SE; ++SI)
247        SymReaper.maybeDead(*SI);
248    }
249  }
250
251  // Go through he deferred locations and add them to the new environment if
252  // the correspond Stmt* is in the map as well.
253  for (SmallVectorImpl<std::pair<EnvironmentEntry, SVal> >::iterator
254      I = deferredLocations.begin(), E = deferredLocations.end(); I != E; ++I) {
255    const EnvironmentEntry &En = I->first;
256    const Stmt *S = (Stmt*) (((uintptr_t) En.getStmt()) & (uintptr_t) ~0x1);
257    if (EBMapRef.lookup(EnvironmentEntry(S, En.getLocationContext())))
258      EBMapRef = EBMapRef.add(En, I->second);
259  }
260
261  NewEnv.ExprBindings = EBMapRef.asImmutableMap();
262  return NewEnv;
263}
264
265void Environment::print(raw_ostream &Out, const char *NL,
266                        const char *Sep) const {
267  printAux(Out, false, NL, Sep);
268  printAux(Out, true, NL, Sep);
269}
270
271void Environment::printAux(raw_ostream &Out, bool printLocations,
272                           const char *NL,
273                           const char *Sep) const{
274
275  bool isFirst = true;
276
277  for (Environment::iterator I = begin(), E = end(); I != E; ++I) {
278    const EnvironmentEntry &En = I.getKey();
279    if (IsLocation(En)) {
280      if (!printLocations)
281        continue;
282    }
283    else {
284      if (printLocations)
285        continue;
286    }
287
288    if (isFirst) {
289      Out << NL << NL
290          << (printLocations ? "Load/Store locations:" : "Expressions:")
291          << NL;
292      isFirst = false;
293    } else {
294      Out << NL;
295    }
296
297    const Stmt *S = En.getStmt();
298    if (printLocations) {
299      S = (Stmt*) (((uintptr_t) S) & ((uintptr_t) ~0x1));
300    }
301
302    Out << " (" << (const void*) En.getLocationContext() << ','
303      << (const void*) S << ") ";
304    LangOptions LO; // FIXME.
305    S->printPretty(Out, 0, PrintingPolicy(LO));
306    Out << " : " << I.getData();
307  }
308}
309