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/Analysis/AnalysisContext.h"
15 #include "clang/Analysis/CFG.h"
16 #include "clang/StaticAnalyzer/Core/PathSensitive/GRState.h"
17 
18 using namespace clang;
19 using namespace ento;
20 
21 SVal Environment::lookupExpr(const Stmt* E) const {
22   const SVal* X = ExprBindings.lookup(E);
23   if (X) {
24     SVal V = *X;
25     return V;
26   }
27   return UnknownVal();
28 }
29 
30 SVal Environment::getSVal(const Stmt *E, SValBuilder& svalBuilder) const {
31   for (;;) {
32     switch (E->getStmtClass()) {
33       case Stmt::AddrLabelExprClass:
34         return svalBuilder.makeLoc(cast<AddrLabelExpr>(E));
35       case Stmt::OpaqueValueExprClass: {
36         const OpaqueValueExpr *ope = cast<OpaqueValueExpr>(E);
37         E = ope->getSourceExpr();
38         continue;
39       }
40       case Stmt::ParenExprClass:
41         // ParenExprs are no-ops.
42         E = cast<ParenExpr>(E)->getSubExpr();
43         continue;
44       case Stmt::GenericSelectionExprClass:
45         // GenericSelectionExprs are no-ops.
46         E = cast<GenericSelectionExpr>(E)->getResultExpr();
47         continue;
48       case Stmt::CharacterLiteralClass: {
49         const CharacterLiteral* C = cast<CharacterLiteral>(E);
50         return svalBuilder.makeIntVal(C->getValue(), C->getType());
51       }
52       case Stmt::CXXBoolLiteralExprClass: {
53         const SVal *X = ExprBindings.lookup(E);
54         if (X)
55           return *X;
56         else
57           return svalBuilder.makeBoolVal(cast<CXXBoolLiteralExpr>(E));
58       }
59       case Stmt::IntegerLiteralClass: {
60         // In C++, this expression may have been bound to a temporary object.
61         SVal const *X = ExprBindings.lookup(E);
62         if (X)
63           return *X;
64         else
65           return svalBuilder.makeIntVal(cast<IntegerLiteral>(E));
66       }
67       case Stmt::ImplicitCastExprClass:
68       case Stmt::CXXFunctionalCastExprClass:
69       case Stmt::CStyleCastExprClass: {
70         // We blast through no-op casts to get the descendant
71         // subexpression that has a value.
72         const CastExpr* C = cast<CastExpr>(E);
73         QualType CT = C->getType();
74         if (CT->isVoidType())
75           return UnknownVal();
76         if (C->getCastKind() == CK_NoOp) {
77           E = C->getSubExpr();
78           continue;
79         }
80         break;
81       }
82       case Stmt::ExprWithCleanupsClass:
83         E = cast<ExprWithCleanups>(E)->getSubExpr();
84         continue;
85       case Stmt::CXXBindTemporaryExprClass:
86         E = cast<CXXBindTemporaryExpr>(E)->getSubExpr();
87         continue;
88       // Handle all other Stmt* using a lookup.
89       default:
90         break;
91     };
92     break;
93   }
94   return lookupExpr(E);
95 }
96 
97 Environment EnvironmentManager::bindExpr(Environment Env, const Stmt *S,
98                                          SVal V, bool Invalidate) {
99   assert(S);
100 
101   if (V.isUnknown()) {
102     if (Invalidate)
103       return Environment(F.remove(Env.ExprBindings, S));
104     else
105       return Env;
106   }
107 
108   return Environment(F.add(Env.ExprBindings, S, V));
109 }
110 
111 static inline const Stmt *MakeLocation(const Stmt *S) {
112   return (const Stmt*) (((uintptr_t) S) | 0x1);
113 }
114 
115 Environment EnvironmentManager::bindExprAndLocation(Environment Env,
116                                                     const Stmt *S,
117                                                     SVal location, SVal V) {
118   return Environment(F.add(F.add(Env.ExprBindings, MakeLocation(S), location),
119                            S, V));
120 }
121 
122 namespace {
123 class MarkLiveCallback : public SymbolVisitor {
124   SymbolReaper &SymReaper;
125 public:
126   MarkLiveCallback(SymbolReaper &symreaper) : SymReaper(symreaper) {}
127   bool VisitSymbol(SymbolRef sym) { SymReaper.markLive(sym); return true; }
128 };
129 } // end anonymous namespace
130 
131 static bool isBlockExprInCallers(const Stmt *E, const LocationContext *LC) {
132   const LocationContext *ParentLC = LC->getParent();
133   while (ParentLC) {
134     CFG &C = *ParentLC->getCFG();
135     if (C.isBlkExpr(E))
136       return true;
137     ParentLC = ParentLC->getParent();
138   }
139 
140   return false;
141 }
142 
143 // In addition to mapping from Stmt * - > SVals in the Environment, we also
144 // maintain a mapping from Stmt * -> SVals (locations) that were used during
145 // a load and store.
146 static inline bool IsLocation(const Stmt *S) {
147   return (bool) (((uintptr_t) S) & 0x1);
148 }
149 
150 // removeDeadBindings:
151 //  - Remove subexpression bindings.
152 //  - Remove dead block expression bindings.
153 //  - Keep live block expression bindings:
154 //   - Mark their reachable symbols live in SymbolReaper,
155 //     see ScanReachableSymbols.
156 //   - Mark the region in DRoots if the binding is a loc::MemRegionVal.
157 Environment
158 EnvironmentManager::removeDeadBindings(Environment Env,
159                                        SymbolReaper &SymReaper,
160                                        const GRState *ST,
161                               llvm::SmallVectorImpl<const MemRegion*> &DRoots) {
162 
163   CFG &C = *SymReaper.getLocationContext()->getCFG();
164 
165   // We construct a new Environment object entirely, as this is cheaper than
166   // individually removing all the subexpression bindings (which will greatly
167   // outnumber block-level expression bindings).
168   Environment NewEnv = getInitialEnvironment();
169 
170   llvm::SmallVector<std::pair<const Stmt*, SVal>, 10> deferredLocations;
171 
172   // Iterate over the block-expr bindings.
173   for (Environment::iterator I = Env.begin(), E = Env.end();
174        I != E; ++I) {
175 
176     const Stmt *BlkExpr = I.getKey();
177 
178     // For recorded locations (used when evaluating loads and stores), we
179     // consider them live only when their associated normal expression is
180     // also live.
181     // NOTE: This assumes that loads/stores that evaluated to UnknownVal
182     // still have an entry in the map.
183     if (IsLocation(BlkExpr)) {
184       deferredLocations.push_back(std::make_pair(BlkExpr, I.getData()));
185       continue;
186     }
187 
188     const SVal &X = I.getData();
189 
190     // Block-level expressions in callers are assumed always live.
191     if (isBlockExprInCallers(BlkExpr, SymReaper.getLocationContext())) {
192       NewEnv.ExprBindings = F.add(NewEnv.ExprBindings, BlkExpr, X);
193 
194       if (isa<loc::MemRegionVal>(X)) {
195         const MemRegion* R = cast<loc::MemRegionVal>(X).getRegion();
196         DRoots.push_back(R);
197       }
198 
199       // Mark all symbols in the block expr's value live.
200       MarkLiveCallback cb(SymReaper);
201       ST->scanReachableSymbols(X, cb);
202       continue;
203     }
204 
205     // Not a block-level expression?
206     if (!C.isBlkExpr(BlkExpr))
207       continue;
208 
209     if (SymReaper.isLive(BlkExpr)) {
210       // Copy the binding to the new map.
211       NewEnv.ExprBindings = F.add(NewEnv.ExprBindings, BlkExpr, X);
212 
213       // If the block expr's value is a memory region, then mark that region.
214       if (isa<loc::MemRegionVal>(X)) {
215         const MemRegion* R = cast<loc::MemRegionVal>(X).getRegion();
216         DRoots.push_back(R);
217       }
218 
219       // Mark all symbols in the block expr's value live.
220       MarkLiveCallback cb(SymReaper);
221       ST->scanReachableSymbols(X, cb);
222       continue;
223     }
224 
225     // Otherwise the expression is dead with a couple exceptions.
226     // Do not misclean LogicalExpr or ConditionalOperator.  It is dead at the
227     // beginning of itself, but we need its UndefinedVal to determine its
228     // SVal.
229     if (X.isUndef() && cast<UndefinedVal>(X).getData())
230       NewEnv.ExprBindings = F.add(NewEnv.ExprBindings, BlkExpr, X);
231   }
232 
233   // Go through he deferred locations and add them to the new environment if
234   // the correspond Stmt* is in the map as well.
235   for (llvm::SmallVectorImpl<std::pair<const Stmt*, SVal> >::iterator
236       I = deferredLocations.begin(), E = deferredLocations.end(); I != E; ++I) {
237     const Stmt *S = (Stmt*) (((uintptr_t) I->first) & (uintptr_t) ~0x1);
238     if (NewEnv.ExprBindings.lookup(S))
239       NewEnv.ExprBindings = F.add(NewEnv.ExprBindings, I->first, I->second);
240   }
241 
242   return NewEnv;
243 }
244