1 //===- Environment.cpp - Map from Stmt* to Locations/Values ---------------===//
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/StaticAnalyzer/Core/PathSensitive/Environment.h"
15 #include "clang/AST/Expr.h"
16 #include "clang/AST/ExprCXX.h"
17 #include "clang/AST/PrettyPrinter.h"
18 #include "clang/AST/Stmt.h"
19 #include "clang/Analysis/AnalysisDeclContext.h"
20 #include "clang/Basic/LLVM.h"
21 #include "clang/Basic/LangOptions.h"
22 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
23 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
24 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
25 #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
26 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.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"
34 using namespace clang;
37 static const Expr *ignoreTransparentExprs(const Expr *E) {
38 E = E->IgnoreParens();
40 switch (E->getStmtClass()) {
41 case Stmt::OpaqueValueExprClass:
42 E = cast<OpaqueValueExpr>(E)->getSourceExpr();
44 case Stmt::ExprWithCleanupsClass:
45 E = cast<ExprWithCleanups>(E)->getSubExpr();
47 case Stmt::CXXBindTemporaryExprClass:
48 E = cast<CXXBindTemporaryExpr>(E)->getSubExpr();
50 case Stmt::SubstNonTypeTemplateParmExprClass:
51 E = cast<SubstNonTypeTemplateParmExpr>(E)->getReplacement();
54 // This is the base case: we can't look through more than we already have.
58 return ignoreTransparentExprs(E);
61 static const Stmt *ignoreTransparentExprs(const Stmt *S) {
62 if (const auto *E = dyn_cast<Expr>(S))
63 return ignoreTransparentExprs(E);
67 EnvironmentEntry::EnvironmentEntry(const Stmt *S, const LocationContext *L)
68 : std::pair<const Stmt *,
69 const StackFrameContext *>(ignoreTransparentExprs(S),
70 L ? L->getStackFrame()
73 SVal Environment::lookupExpr(const EnvironmentEntry &E) const {
74 const SVal* X = ExprBindings.lookup(E);
82 SVal Environment::getSVal(const EnvironmentEntry &Entry,
83 SValBuilder& svalBuilder) const {
84 const Stmt *S = Entry.getStmt();
85 const LocationContext *LCtx = Entry.getLocationContext();
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");
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();
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();
117 // Handle all other Stmt* using a lookup.
119 return lookupExpr(EnvironmentEntry(S, LCtx));
123 Environment EnvironmentManager::bindExpr(Environment Env,
124 const EnvironmentEntry &E,
129 return Environment(F.remove(Env.ExprBindings, E));
133 return Environment(F.add(Env.ExprBindings, E, V));
138 class MarkLiveCallback final : public SymbolVisitor {
139 SymbolReaper &SymReaper;
142 MarkLiveCallback(SymbolReaper &symreaper) : SymReaper(symreaper) {}
144 bool VisitSymbol(SymbolRef sym) override {
145 SymReaper.markLive(sym);
149 bool VisitMemRegion(const MemRegion *R) override {
150 SymReaper.markLive(R);
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.
165 EnvironmentManager::removeDeadBindings(Environment Env,
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();
173 MarkLiveCallback CB(SymReaper);
174 ScanReachableSymbols RSScaner(ST, CB);
176 llvm::ImmutableMapRef<EnvironmentEntry, SVal>
177 EBMapRef(NewEnv.ExprBindings.getRootWithoutRetain(),
180 // Iterate over the block-expr bindings.
181 for (Environment::iterator I = Env.begin(), E = Env.end();
183 const EnvironmentEntry &BlkExpr = I.getKey();
184 const SVal &X = I.getData();
186 if (SymReaper.isLive(BlkExpr.getStmt(), BlkExpr.getLocationContext())) {
187 // Copy the binding to the new map.
188 EBMapRef = EBMapRef.add(BlkExpr, X);
190 // Mark all symbols in the block expr's value live.
194 SymExpr::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
195 for (; SI != SE; ++SI)
196 SymReaper.maybeDead(*SI);
200 NewEnv.ExprBindings = EBMapRef.asImmutableMap();
204 void Environment::print(raw_ostream &Out, const char *NL,
205 const char *Sep, const LocationContext *WithLC) const {
206 if (ExprBindings.isEmpty())
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.
217 for (const LocationContext *LCI = LC; LCI; LCI = LCI->getParent())
218 FoundContexts.insert(LCI);
225 LangOptions LO; // FIXME.
226 PrintingPolicy PP(LO);
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)
234 const Stmt *S = I.first.getStmt();
235 assert(S != nullptr && "Expected non-null Stmt");
237 Out << "(" << (const void *)LC << ',' << (const void *)S << ") ";
238 S->printPretty(Out, nullptr, PP);
239 Out << " : " << I.second << NL;