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
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"
32 #include <cassert>
33
34 using namespace clang;
35 using namespace ento;
36
ignoreTransparentExprs(const Expr * E)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::ConstantExprClass:
48 E = cast<ConstantExpr>(E)->getSubExpr();
49 break;
50 case Stmt::CXXBindTemporaryExprClass:
51 E = cast<CXXBindTemporaryExpr>(E)->getSubExpr();
52 break;
53 case Stmt::SubstNonTypeTemplateParmExprClass:
54 E = cast<SubstNonTypeTemplateParmExpr>(E)->getReplacement();
55 break;
56 default:
57 // This is the base case: we can't look through more than we already have.
58 return E;
59 }
60
61 return ignoreTransparentExprs(E);
62 }
63
ignoreTransparentExprs(const Stmt * S)64 static const Stmt *ignoreTransparentExprs(const Stmt *S) {
65 if (const auto *E = dyn_cast<Expr>(S))
66 return ignoreTransparentExprs(E);
67 return S;
68 }
69
EnvironmentEntry(const Stmt * S,const LocationContext * L)70 EnvironmentEntry::EnvironmentEntry(const Stmt *S, const LocationContext *L)
71 : std::pair<const Stmt *,
72 const StackFrameContext *>(ignoreTransparentExprs(S),
73 L ? L->getStackFrame()
74 : nullptr) {}
75
lookupExpr(const EnvironmentEntry & E) const76 SVal Environment::lookupExpr(const EnvironmentEntry &E) const {
77 const SVal* X = ExprBindings.lookup(E);
78 if (X) {
79 SVal V = *X;
80 return V;
81 }
82 return UnknownVal();
83 }
84
getSVal(const EnvironmentEntry & Entry,SValBuilder & svalBuilder) const85 SVal Environment::getSVal(const EnvironmentEntry &Entry,
86 SValBuilder& svalBuilder) const {
87 const Stmt *S = Entry.getStmt();
88 const LocationContext *LCtx = Entry.getLocationContext();
89
90 switch (S->getStmtClass()) {
91 case Stmt::CXXBindTemporaryExprClass:
92 case Stmt::ExprWithCleanupsClass:
93 case Stmt::GenericSelectionExprClass:
94 case Stmt::OpaqueValueExprClass:
95 case Stmt::ConstantExprClass:
96 case Stmt::ParenExprClass:
97 case Stmt::SubstNonTypeTemplateParmExprClass:
98 llvm_unreachable("Should have been handled by ignoreTransparentExprs");
99
100 case Stmt::AddrLabelExprClass:
101 case Stmt::CharacterLiteralClass:
102 case Stmt::CXXBoolLiteralExprClass:
103 case Stmt::CXXScalarValueInitExprClass:
104 case Stmt::ImplicitValueInitExprClass:
105 case Stmt::IntegerLiteralClass:
106 case Stmt::ObjCBoolLiteralExprClass:
107 case Stmt::CXXNullPtrLiteralExprClass:
108 case Stmt::ObjCStringLiteralClass:
109 case Stmt::StringLiteralClass:
110 case Stmt::TypeTraitExprClass:
111 // Known constants; defer to SValBuilder.
112 return svalBuilder.getConstantVal(cast<Expr>(S)).getValue();
113
114 case Stmt::ReturnStmtClass: {
115 const auto *RS = cast<ReturnStmt>(S);
116 if (const Expr *RE = RS->getRetValue())
117 return getSVal(EnvironmentEntry(RE, LCtx), svalBuilder);
118 return UndefinedVal();
119 }
120
121 // Handle all other Stmt* using a lookup.
122 default:
123 return lookupExpr(EnvironmentEntry(S, LCtx));
124 }
125 }
126
bindExpr(Environment Env,const EnvironmentEntry & E,SVal V,bool Invalidate)127 Environment EnvironmentManager::bindExpr(Environment Env,
128 const EnvironmentEntry &E,
129 SVal V,
130 bool Invalidate) {
131 if (V.isUnknown()) {
132 if (Invalidate)
133 return Environment(F.remove(Env.ExprBindings, E));
134 else
135 return Env;
136 }
137 return Environment(F.add(Env.ExprBindings, E, V));
138 }
139
140 namespace {
141
142 class MarkLiveCallback final : public SymbolVisitor {
143 SymbolReaper &SymReaper;
144
145 public:
MarkLiveCallback(SymbolReaper & symreaper)146 MarkLiveCallback(SymbolReaper &symreaper) : SymReaper(symreaper) {}
147
VisitSymbol(SymbolRef sym)148 bool VisitSymbol(SymbolRef sym) override {
149 SymReaper.markLive(sym);
150 return true;
151 }
152
VisitMemRegion(const MemRegion * R)153 bool VisitMemRegion(const MemRegion *R) override {
154 SymReaper.markLive(R);
155 return true;
156 }
157 };
158
159 } // namespace
160
161 // removeDeadBindings:
162 // - Remove subexpression bindings.
163 // - Remove dead block expression bindings.
164 // - Keep live block expression bindings:
165 // - Mark their reachable symbols live in SymbolReaper,
166 // see ScanReachableSymbols.
167 // - Mark the region in DRoots if the binding is a loc::MemRegionVal.
168 Environment
removeDeadBindings(Environment Env,SymbolReaper & SymReaper,ProgramStateRef ST)169 EnvironmentManager::removeDeadBindings(Environment Env,
170 SymbolReaper &SymReaper,
171 ProgramStateRef ST) {
172 // We construct a new Environment object entirely, as this is cheaper than
173 // individually removing all the subexpression bindings (which will greatly
174 // outnumber block-level expression bindings).
175 Environment NewEnv = getInitialEnvironment();
176
177 MarkLiveCallback CB(SymReaper);
178 ScanReachableSymbols RSScaner(ST, CB);
179
180 llvm::ImmutableMapRef<EnvironmentEntry, SVal>
181 EBMapRef(NewEnv.ExprBindings.getRootWithoutRetain(),
182 F.getTreeFactory());
183
184 // Iterate over the block-expr bindings.
185 for (Environment::iterator I = Env.begin(), E = Env.end();
186 I != E; ++I) {
187 const EnvironmentEntry &BlkExpr = I.getKey();
188 const SVal &X = I.getData();
189
190 if (SymReaper.isLive(BlkExpr.getStmt(), BlkExpr.getLocationContext())) {
191 // Copy the binding to the new map.
192 EBMapRef = EBMapRef.add(BlkExpr, X);
193
194 // Mark all symbols in the block expr's value live.
195 RSScaner.scan(X);
196 }
197 }
198
199 NewEnv.ExprBindings = EBMapRef.asImmutableMap();
200 return NewEnv;
201 }
202
print(raw_ostream & Out,const char * NL,const char * Sep,const ASTContext & Context,const LocationContext * WithLC) const203 void Environment::print(raw_ostream &Out, const char *NL,
204 const char *Sep,
205 const ASTContext &Context,
206 const LocationContext *WithLC) const {
207 if (ExprBindings.isEmpty())
208 return;
209
210 if (!WithLC) {
211 // Find the freshest location context.
212 llvm::SmallPtrSet<const LocationContext *, 16> FoundContexts;
213 for (auto I : *this) {
214 const LocationContext *LC = I.first.getLocationContext();
215 if (FoundContexts.count(LC) == 0) {
216 // This context is fresher than all other contexts so far.
217 WithLC = LC;
218 for (const LocationContext *LCI = LC; LCI; LCI = LCI->getParent())
219 FoundContexts.insert(LCI);
220 }
221 }
222 }
223
224 assert(WithLC);
225
226 PrintingPolicy PP = Context.getPrintingPolicy();
227
228 Out << 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 << "(LC" << LC->getID() << ", S" << S->getID(Context) << ") ";
238 S->printPretty(Out, /*Helper=*/nullptr, PP);
239 Out << " : " << I.second << NL;
240 }
241 });
242 }
243