• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
21 using namespace clang;
22 using namespace ento;
23 
ignoreTransparentExprs(const Expr * E)24 static 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   default:
41     // This is the base case: we can't look through more than we already have.
42     return E;
43   }
44 
45   return ignoreTransparentExprs(E);
46 }
47 
ignoreTransparentExprs(const Stmt * S)48 static const Stmt *ignoreTransparentExprs(const Stmt *S) {
49   if (const Expr *E = dyn_cast<Expr>(S))
50     return ignoreTransparentExprs(E);
51   return S;
52 }
53 
EnvironmentEntry(const Stmt * S,const LocationContext * L)54 EnvironmentEntry::EnvironmentEntry(const Stmt *S, const LocationContext *L)
55   : std::pair<const Stmt *,
56               const StackFrameContext *>(ignoreTransparentExprs(S),
57                                          L ? L->getCurrentStackFrame()
58                                            : nullptr) {}
59 
lookupExpr(const EnvironmentEntry & E) const60 SVal Environment::lookupExpr(const EnvironmentEntry &E) const {
61   const SVal* X = ExprBindings.lookup(E);
62   if (X) {
63     SVal V = *X;
64     return V;
65   }
66   return UnknownVal();
67 }
68 
getSVal(const EnvironmentEntry & Entry,SValBuilder & svalBuilder) const69 SVal Environment::getSVal(const EnvironmentEntry &Entry,
70                           SValBuilder& svalBuilder) const {
71   const Stmt *S = Entry.getStmt();
72   const LocationContext *LCtx = Entry.getLocationContext();
73 
74   switch (S->getStmtClass()) {
75   case Stmt::CXXBindTemporaryExprClass:
76   case Stmt::ExprWithCleanupsClass:
77   case Stmt::GenericSelectionExprClass:
78   case Stmt::OpaqueValueExprClass:
79   case Stmt::ParenExprClass:
80   case Stmt::SubstNonTypeTemplateParmExprClass:
81     llvm_unreachable("Should have been handled by ignoreTransparentExprs");
82 
83   case Stmt::AddrLabelExprClass:
84   case Stmt::CharacterLiteralClass:
85   case Stmt::CXXBoolLiteralExprClass:
86   case Stmt::CXXScalarValueInitExprClass:
87   case Stmt::ImplicitValueInitExprClass:
88   case Stmt::IntegerLiteralClass:
89   case Stmt::ObjCBoolLiteralExprClass:
90   case Stmt::CXXNullPtrLiteralExprClass:
91   case Stmt::ObjCStringLiteralClass:
92   case Stmt::StringLiteralClass:
93   case Stmt::TypeTraitExprClass:
94     // Known constants; defer to SValBuilder.
95     return svalBuilder.getConstantVal(cast<Expr>(S)).getValue();
96 
97   case Stmt::ReturnStmtClass: {
98     const ReturnStmt *RS = cast<ReturnStmt>(S);
99     if (const Expr *RE = RS->getRetValue())
100       return getSVal(EnvironmentEntry(RE, LCtx), svalBuilder);
101     return UndefinedVal();
102   }
103 
104   // Handle all other Stmt* using a lookup.
105   default:
106     return lookupExpr(EnvironmentEntry(S, LCtx));
107   }
108 }
109 
bindExpr(Environment Env,const EnvironmentEntry & E,SVal V,bool Invalidate)110 Environment EnvironmentManager::bindExpr(Environment Env,
111                                          const EnvironmentEntry &E,
112                                          SVal V,
113                                          bool Invalidate) {
114   if (V.isUnknown()) {
115     if (Invalidate)
116       return Environment(F.remove(Env.ExprBindings, E));
117     else
118       return Env;
119   }
120   return Environment(F.add(Env.ExprBindings, E, V));
121 }
122 
123 namespace {
124 class MarkLiveCallback final : public SymbolVisitor {
125   SymbolReaper &SymReaper;
126 public:
MarkLiveCallback(SymbolReaper & symreaper)127   MarkLiveCallback(SymbolReaper &symreaper) : SymReaper(symreaper) {}
VisitSymbol(SymbolRef sym)128   bool VisitSymbol(SymbolRef sym) override {
129     SymReaper.markLive(sym);
130     return true;
131   }
VisitMemRegion(const MemRegion * R)132   bool VisitMemRegion(const MemRegion *R) override {
133     SymReaper.markLive(R);
134     return true;
135   }
136 };
137 } // end anonymous namespace
138 
139 // removeDeadBindings:
140 //  - Remove subexpression bindings.
141 //  - Remove dead block expression bindings.
142 //  - Keep live block expression bindings:
143 //   - Mark their reachable symbols live in SymbolReaper,
144 //     see ScanReachableSymbols.
145 //   - Mark the region in DRoots if the binding is a loc::MemRegionVal.
146 Environment
removeDeadBindings(Environment Env,SymbolReaper & SymReaper,ProgramStateRef ST)147 EnvironmentManager::removeDeadBindings(Environment Env,
148                                        SymbolReaper &SymReaper,
149                                        ProgramStateRef ST) {
150 
151   // We construct a new Environment object entirely, as this is cheaper than
152   // individually removing all the subexpression bindings (which will greatly
153   // outnumber block-level expression bindings).
154   Environment NewEnv = getInitialEnvironment();
155 
156   MarkLiveCallback CB(SymReaper);
157   ScanReachableSymbols RSScaner(ST, CB);
158 
159   llvm::ImmutableMapRef<EnvironmentEntry,SVal>
160     EBMapRef(NewEnv.ExprBindings.getRootWithoutRetain(),
161              F.getTreeFactory());
162 
163   // Iterate over the block-expr bindings.
164   for (Environment::iterator I = Env.begin(), E = Env.end();
165        I != E; ++I) {
166 
167     const EnvironmentEntry &BlkExpr = I.getKey();
168     const SVal &X = I.getData();
169 
170     if (SymReaper.isLive(BlkExpr.getStmt(), BlkExpr.getLocationContext())) {
171       // Copy the binding to the new map.
172       EBMapRef = EBMapRef.add(BlkExpr, X);
173 
174       // Mark all symbols in the block expr's value live.
175       RSScaner.scan(X);
176       continue;
177     } else {
178       SymExpr::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
179       for (; SI != SE; ++SI)
180         SymReaper.maybeDead(*SI);
181     }
182   }
183 
184   NewEnv.ExprBindings = EBMapRef.asImmutableMap();
185   return NewEnv;
186 }
187 
print(raw_ostream & Out,const char * NL,const char * Sep) const188 void Environment::print(raw_ostream &Out, const char *NL,
189                         const char *Sep) const {
190   bool isFirst = true;
191 
192   for (Environment::iterator I = begin(), E = end(); I != E; ++I) {
193     const EnvironmentEntry &En = I.getKey();
194 
195     if (isFirst) {
196       Out << NL << NL
197           << "Expressions:"
198           << NL;
199       isFirst = false;
200     } else {
201       Out << NL;
202     }
203 
204     const Stmt *S = En.getStmt();
205     assert(S != nullptr && "Expected non-null Stmt");
206 
207     Out << " (" << (const void*) En.getLocationContext() << ','
208       << (const void*) S << ") ";
209     LangOptions LO; // FIXME.
210     S->printPretty(Out, nullptr, PrintingPolicy(LO));
211     Out << " : " << I.getData();
212   }
213 }
214