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