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