clang  7.0.0svn
Environment.cpp
Go to the documentation of this file.
1 //===- Environment.cpp - Map from Stmt* to Locations/Values ---------------===//
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 
15 #include "clang/AST/Expr.h"
16 #include "clang/AST/ExprCXX.h"
18 #include "clang/AST/Stmt.h"
20 #include "clang/Basic/LLVM.h"
27 #include "llvm/ADT/ImmutableMap.h"
28 #include "llvm/ADT/SmallPtrSet.h"
29 #include "llvm/Support/Casting.h"
30 #include "llvm/Support/ErrorHandling.h"
31 #include "llvm/Support/raw_ostream.h"
32 #include <cassert>
33 
34 using namespace clang;
35 using namespace ento;
36 
37 static const Expr *ignoreTransparentExprs(const Expr *E) {
38  E = E->IgnoreParens();
39 
40  switch (E->getStmtClass()) {
41  case Stmt::OpaqueValueExprClass:
42  E = cast<OpaqueValueExpr>(E)->getSourceExpr();
43  break;
44  case Stmt::ExprWithCleanupsClass:
45  E = cast<ExprWithCleanups>(E)->getSubExpr();
46  break;
47  case Stmt::CXXBindTemporaryExprClass:
48  E = cast<CXXBindTemporaryExpr>(E)->getSubExpr();
49  break;
50  case Stmt::SubstNonTypeTemplateParmExprClass:
51  E = cast<SubstNonTypeTemplateParmExpr>(E)->getReplacement();
52  break;
53  default:
54  // This is the base case: we can't look through more than we already have.
55  return E;
56  }
57 
58  return ignoreTransparentExprs(E);
59 }
60 
61 static const Stmt *ignoreTransparentExprs(const Stmt *S) {
62  if (const auto *E = dyn_cast<Expr>(S))
63  return ignoreTransparentExprs(E);
64  return S;
65 }
66 
68  : std::pair<const Stmt *,
70  L ? L->getCurrentStackFrame()
71  : nullptr) {}
72 
73 SVal Environment::lookupExpr(const EnvironmentEntry &E) const {
74  const SVal* X = ExprBindings.lookup(E);
75  if (X) {
76  SVal V = *X;
77  return V;
78  }
79  return UnknownVal();
80 }
81 
83  SValBuilder& svalBuilder) const {
84  const Stmt *S = Entry.getStmt();
85  const LocationContext *LCtx = Entry.getLocationContext();
86 
87  switch (S->getStmtClass()) {
88  case Stmt::CXXBindTemporaryExprClass:
89  case Stmt::ExprWithCleanupsClass:
90  case Stmt::GenericSelectionExprClass:
91  case Stmt::OpaqueValueExprClass:
92  case Stmt::ParenExprClass:
93  case Stmt::SubstNonTypeTemplateParmExprClass:
94  llvm_unreachable("Should have been handled by ignoreTransparentExprs");
95 
96  case Stmt::AddrLabelExprClass:
97  case Stmt::CharacterLiteralClass:
98  case Stmt::CXXBoolLiteralExprClass:
99  case Stmt::CXXScalarValueInitExprClass:
100  case Stmt::ImplicitValueInitExprClass:
101  case Stmt::IntegerLiteralClass:
102  case Stmt::ObjCBoolLiteralExprClass:
103  case Stmt::CXXNullPtrLiteralExprClass:
104  case Stmt::ObjCStringLiteralClass:
105  case Stmt::StringLiteralClass:
106  case Stmt::TypeTraitExprClass:
107  // Known constants; defer to SValBuilder.
108  return svalBuilder.getConstantVal(cast<Expr>(S)).getValue();
109 
110  case Stmt::ReturnStmtClass: {
111  const auto *RS = cast<ReturnStmt>(S);
112  if (const Expr *RE = RS->getRetValue())
113  return getSVal(EnvironmentEntry(RE, LCtx), svalBuilder);
114  return UndefinedVal();
115  }
116 
117  // Handle all other Stmt* using a lookup.
118  default:
119  return lookupExpr(EnvironmentEntry(S, LCtx));
120  }
121 }
122 
124  const EnvironmentEntry &E,
125  SVal V,
126  bool Invalidate) {
127  if (V.isUnknown()) {
128  if (Invalidate)
129  return Environment(F.remove(Env.ExprBindings, E));
130  else
131  return Env;
132  }
133  return Environment(F.add(Env.ExprBindings, E, V));
134 }
135 
136 namespace {
137 
138 class MarkLiveCallback final : public SymbolVisitor {
139  SymbolReaper &SymReaper;
140 
141 public:
142  MarkLiveCallback(SymbolReaper &symreaper) : SymReaper(symreaper) {}
143 
144  bool VisitSymbol(SymbolRef sym) override {
145  SymReaper.markLive(sym);
146  return true;
147  }
148 
149  bool VisitMemRegion(const MemRegion *R) override {
150  SymReaper.markLive(R);
151  return true;
152  }
153 };
154 
155 } // namespace
156 
157 // removeDeadBindings:
158 // - Remove subexpression bindings.
159 // - Remove dead block expression bindings.
160 // - Keep live block expression bindings:
161 // - Mark their reachable symbols live in SymbolReaper,
162 // see ScanReachableSymbols.
163 // - Mark the region in DRoots if the binding is a loc::MemRegionVal.
166  SymbolReaper &SymReaper,
167  ProgramStateRef ST) {
168  // We construct a new Environment object entirely, as this is cheaper than
169  // individually removing all the subexpression bindings (which will greatly
170  // outnumber block-level expression bindings).
171  Environment NewEnv = getInitialEnvironment();
172 
173  MarkLiveCallback CB(SymReaper);
174  ScanReachableSymbols RSScaner(ST, CB);
175 
176  llvm::ImmutableMapRef<EnvironmentEntry, SVal>
177  EBMapRef(NewEnv.ExprBindings.getRootWithoutRetain(),
178  F.getTreeFactory());
179 
180  // Iterate over the block-expr bindings.
181  for (Environment::iterator I = Env.begin(), E = Env.end();
182  I != E; ++I) {
183  const EnvironmentEntry &BlkExpr = I.getKey();
184  const SVal &X = I.getData();
185 
186  if (SymReaper.isLive(BlkExpr.getStmt(), BlkExpr.getLocationContext())) {
187  // Copy the binding to the new map.
188  EBMapRef = EBMapRef.add(BlkExpr, X);
189 
190  // Mark all symbols in the block expr's value live.
191  RSScaner.scan(X);
192  continue;
193  } else {
195  for (; SI != SE; ++SI)
196  SymReaper.maybeDead(*SI);
197  }
198  }
199 
200  NewEnv.ExprBindings = EBMapRef.asImmutableMap();
201  return NewEnv;
202 }
203 
204 void Environment::print(raw_ostream &Out, const char *NL,
205  const char *Sep, const LocationContext *WithLC) const {
206  if (ExprBindings.isEmpty())
207  return;
208 
209  if (!WithLC) {
210  // Find the freshest location context.
211  llvm::SmallPtrSet<const LocationContext *, 16> FoundContexts;
212  for (auto I : *this) {
213  const LocationContext *LC = I.first.getLocationContext();
214  if (FoundContexts.count(LC) == 0) {
215  // This context is fresher than all other contexts so far.
216  WithLC = LC;
217  for (const LocationContext *LCI = LC; LCI; LCI = LCI->getParent())
218  FoundContexts.insert(LCI);
219  }
220  }
221  }
222 
223  assert(WithLC);
224 
225  LangOptions LO; // FIXME.
226  PrintingPolicy PP(LO);
227 
228  Out << NL << NL << "Expressions by stack frame:" << NL;
229  WithLC->dumpStack(Out, "", NL, Sep, [&](const LocationContext *LC) {
230  for (auto I : ExprBindings) {
231  if (I.first.getLocationContext() != LC)
232  continue;
233 
234  const Stmt *S = I.first.getStmt();
235  assert(S != nullptr && "Expected non-null Stmt");
236 
237  Out << "(" << (const void *)LC << ',' << (const void *)S << ") ";
238  S->printPretty(Out, nullptr, PP);
239  Out << " : " << I.second << NL;
240  }
241  });
242 }
EnvironmentEntry(const Stmt *s, const LocationContext *L)
Definition: Environment.cpp:67
MemRegion - The root abstract class for all memory regions.
Definition: MemRegion.h:94
void print(raw_ostream &Out, const char *NL, const char *Sep, const LocationContext *WithLC=nullptr) const
Stmt - This represents one statement.
Definition: Stmt.h:66
bool maybeDead(SymbolRef sym)
If a symbol is known to be live, marks the symbol as live.
A utility class that visits the reachable symbols using a custom SymbolVisitor.
Definition: ProgramState.h:900
Describes how types, statements, expressions, and declarations should be printed. ...
Definition: PrettyPrinter.h:38
Defines the clang::Expr interface and subclasses for C++ expressions.
Symbolic value.
Definition: SymExpr.h:30
const Stmt * getStmt() const
Definition: Environment.h:41
Definition: Format.h:2022
void dumpStack(raw_ostream &OS, StringRef Indent={}, const char *NL="\, const char *Sep="", std::function< void(const LocationContext *)> printMoreInfoPerContext=[](const LocationContext *) {}) const
Environment bindExpr(Environment Env, const EnvironmentEntry &E, SVal V, bool Invalidate)
Bind a symbolic value to the given environment entry.
Keeps track of the various options that can be enabled, which controls the dialect of C or C++ that i...
Definition: LangOptions.h:50
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified...
static const Expr * ignoreTransparentExprs(const Expr *E)
Definition: Environment.cpp:37
iterator end() const
Definition: Environment.h:73
const LocationContext * getParent() const
bool isUnknown() const
Definition: SVals.h:137
void printPretty(raw_ostream &OS, PrinterHelper *Helper, const PrintingPolicy &Policy, unsigned Indentation=0, const ASTContext *Context=nullptr) const
SymExpr::symbol_iterator symbol_end() const
Definition: SVals.h:205
iterator begin() const
Definition: Environment.h:72
BindingsTy::iterator iterator
Definition: Environment.h:70
Expr - This represents one expression.
Definition: Expr.h:106
Defines the clang::LangOptions interface.
bool scan(nonloc::LazyCompoundVal val)
SVal getSVal(const EnvironmentEntry &E, SValBuilder &svalBuilder) const
Fetches the current binding of the expression in the Environment.
Definition: Environment.cpp:82
An entry in the environment consists of a Stmt and an LocationContext.
Definition: Environment.h:36
SVal - This represents a symbolic expression, which can be either an L-value or an R-value...
Definition: SVals.h:76
A class responsible for cleaning up unused symbols.
An immutable map from EnvironemntEntries to SVals.
Definition: Environment.h:57
Dataflow Directional Tag Classes.
StmtClass getStmtClass() const
Definition: Stmt.h:389
X
Add a minimal nested name specifier fixit hint to allow lookup of a tag name from an outer enclosing ...
Definition: SemaDecl.cpp:13462
Optional< SVal > getConstantVal(const Expr *E)
Returns the value of E, if it can be determined in a non-path-sensitive manner.
Environment removeDeadBindings(Environment Env, SymbolReaper &SymReaper, ProgramStateRef state)
SymExpr::symbol_iterator symbol_begin() const
Definition: SVals.h:197
bool isLive(SymbolRef sym)
Expr * IgnoreParens() LLVM_READONLY
IgnoreParens - Ignore parentheses.
Definition: Expr.cpp:2439
const LocationContext * getLocationContext() const
Definition: Environment.h:42
Iterator over symbols that the current symbol depends on.
Definition: SymExpr.h:69