 |
|
 |
|
| Files: |
1 |
|
Branches Taken: |
58.8% |
60 / 102 |
| Generated: |
2010-02-10 01:31 |
|
Branches Executed: |
70.6% |
72 / 102 |
| |
|
Line Coverage: |
65.7% |
113 / 172 |
| |
 |
|
 |
1 : //= GRState.cpp - Path-Sensitive "State" for tracking 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 implements GRState and GRStateManager.
11 : //
12 : //===----------------------------------------------------------------------===//
13 :
14 : #include "clang/Checker/PathSensitive/GRStateTrait.h"
15 : #include "clang/Checker/PathSensitive/GRState.h"
16 : #include "clang/Checker/PathSensitive/GRTransferFuncs.h"
17 : #include "llvm/ADT/SmallSet.h"
18 : #include "llvm/Support/raw_ostream.h"
19 :
20 : using namespace clang;
21 :
22 : // Give the vtable for ConstraintManager somewhere to live.
23 : // FIXME: Move this elsewhere.
2138: branch 0 taken
2138: branch 1 taken
0: branch 3 not taken
0: branch 4 not taken
0: branch 6 not taken
2138: branch 7 taken
24 2138: ConstraintManager::~ConstraintManager() {}
25 :
26 2138: GRStateManager::~GRStateManager() {
2138: branch 3 taken
2138: branch 4 taken
0: branch 8 not taken
0: branch 9 not taken
27 6414: for (std::vector<GRState::Printer*>::iterator I=Printers.begin(),
28 2138: E=Printers.end(); I!=E; ++I)
2138: branch 1 taken
0: branch 2 not taken
0: branch 5 not taken
0: branch 6 not taken
29 2138: delete *I;
30 :
3864: branch 5 taken
2138: branch 6 taken
0: branch 12 not taken
0: branch 13 not taken
31 6002: for (GDMContextsTy::iterator I=GDMContexts.begin(), E=GDMContexts.end();
32 : I!=E; ++I)
33 3864: I->second.second(I->second.first);
34 2138: }
35 :
36 : const GRState*
37 : GRStateManager::RemoveDeadBindings(const GRState* state, Stmt* Loc,
38 11706: SymbolReaper& SymReaper) {
39 :
40 : // This code essentially performs a "mark-and-sweep" of the VariableBindings.
41 : // The roots are any Block-level exprs and Decls that our liveness algorithm
42 : // tells us are live. We then see what Decls they may reference, and keep
43 : // those around. This code more than likely can be made faster, and the
44 : // frequency of which this method is called should be experimented with
45 : // for optimum performance.
46 11706: llvm::SmallVector<const MemRegion*, 10> RegionRoots;
47 11706: GRState NewState = *state;
48 :
49 : NewState.Env = EnvMgr.RemoveDeadBindings(NewState.Env, Loc, SymReaper,
50 11706: state, RegionRoots);
51 :
52 : // Clean up the store.
53 : NewState.St = StoreMgr->RemoveDeadBindings(NewState.St, Loc, SymReaper,
54 11706: RegionRoots);
55 :
56 : return ConstraintMgr->RemoveDeadBindings(getPersistentState(NewState),
57 11706: SymReaper);
58 : }
59 :
60 297: const GRState *GRState::unbindLoc(Loc LV) const {
61 297: Store OldStore = getStore();
62 297: Store NewStore = getStateManager().StoreMgr->Remove(OldStore, LV);
63 :
297: branch 0 taken
0: branch 1 not taken
64 297: if (NewStore == OldStore)
65 297: return this;
66 :
67 0: GRState NewSt = *this;
68 0: NewSt.St = NewStore;
69 0: return getStateManager().getPersistentState(NewSt);
70 : }
71 :
72 1490: SVal GRState::getSValAsScalarOrLoc(const MemRegion *R) const {
73 : // We only want to do fetches from regions that we can actually bind
74 : // values. For example, SymbolicRegions of type 'id<...>' cannot
75 : // have direct bindings (but their can be bindings on their subregions).
52: branch 1 taken
1438: branch 2 taken
76 1490: if (!R->isBoundable())
77 52: return UnknownVal();
78 :
425: branch 1 taken
1013: branch 2 taken
79 1438: if (const TypedRegion *TR = dyn_cast<TypedRegion>(R)) {
80 425: QualType T = TR->getValueType(getStateManager().getContext());
359: branch 1 taken
66: branch 2 taken
234: branch 5 taken
125: branch 6 taken
300: branch 7 taken
125: branch 8 taken
81 425: if (Loc::IsLocType(T) || T->isIntegerType())
82 300: return getSVal(R);
83 : }
84 :
85 1138: return UnknownVal();
86 : }
87 :
88 :
89 28058: const GRState *GRState::BindExpr(const Stmt* Ex, SVal V, bool Invalidate) const{
90 : Environment NewEnv = getStateManager().EnvMgr.BindExpr(Env, Ex, V,
91 28058: Invalidate);
1018: branch 1 taken
27040: branch 2 taken
92 28058: if (NewEnv == Env)
93 1018: return this;
94 :
95 27040: GRState NewSt = *this;
96 27040: NewSt.Env = NewEnv;
97 27040: return getStateManager().getPersistentState(NewSt);
98 : }
99 :
100 2138: const GRState* GRStateManager::getInitialState(const LocationContext *InitLoc) {
101 : GRState State(this,
102 : EnvMgr.getInitialEnvironment(InitLoc->getAnalysisContext()),
103 : StoreMgr->getInitialStore(InitLoc),
104 2138: GDMFactory.GetEmptyMap());
105 :
106 2138: return getPersistentState(State);
107 : }
108 :
109 61592: const GRState* GRStateManager::getPersistentState(GRState& State) {
110 :
111 61592: llvm::FoldingSetNodeID ID;
112 61592: State.Profile(ID);
113 : void* InsertPos;
114 :
7470: branch 1 taken
54122: branch 2 taken
115 61592: if (GRState* I = StateSet.FindNodeOrInsertPos(ID, InsertPos))
116 7470: return I;
117 :
118 54122: GRState* I = (GRState*) Alloc.Allocate<GRState>();
54122: branch 1 taken
0: branch 2 not taken
119 54122: new (I) GRState(State);
120 54122: StateSet.InsertNode(I, InsertPos);
121 54122: return I;
122 : }
123 :
124 8939: const GRState* GRState::makeWithStore(Store store) const {
125 8939: GRState NewSt = *this;
126 8939: NewSt.St = store;
127 8939: return getStateManager().getPersistentState(NewSt);
128 : }
129 :
130 : //===----------------------------------------------------------------------===//
131 : // State pretty-printing.
132 : //===----------------------------------------------------------------------===//
133 :
134 : void GRState::print(llvm::raw_ostream& Out, const char* nl,
135 0: const char* sep) const {
136 : // Print the store.
137 0: GRStateManager &Mgr = getStateManager();
138 0: Mgr.getStoreManager().print(getStore(), Out, nl, sep);
139 :
140 0: CFG &C = *getAnalysisContext().getCFG();
141 :
142 : // Print Subexpression bindings.
143 0: bool isFirst = true;
144 :
0: branch 5 not taken
0: branch 6 not taken
145 0: for (Environment::iterator I = Env.begin(), E = Env.end(); I != E; ++I) {
0: branch 2 not taken
0: branch 3 not taken
146 0: if (C.isBlkExpr(I.getKey()))
147 0: continue;
148 :
0: branch 0 not taken
0: branch 1 not taken
149 0: if (isFirst) {
150 0: Out << nl << nl << "Sub-Expressions:" << nl;
151 0: isFirst = false;
152 : }
153 0: else { Out << nl; }
154 :
155 0: Out << " (" << (void*) I.getKey() << ") ";
156 0: LangOptions LO; // FIXME.
157 0: I.getKey()->printPretty(Out, 0, PrintingPolicy(LO));
158 0: Out << " : " << I.getData();
159 0: }
160 :
161 : // Print block-expression bindings.
162 0: isFirst = true;
163 :
0: branch 5 not taken
0: branch 6 not taken
164 0: for (Environment::iterator I = Env.begin(), E = Env.end(); I != E; ++I) {
0: branch 2 not taken
0: branch 3 not taken
165 0: if (!C.isBlkExpr(I.getKey()))
166 0: continue;
167 :
0: branch 0 not taken
0: branch 1 not taken
168 0: if (isFirst) {
169 0: Out << nl << nl << "Block-level Expressions:" << nl;
170 0: isFirst = false;
171 : }
172 0: else { Out << nl; }
173 :
174 0: Out << " (" << (void*) I.getKey() << ") ";
175 0: LangOptions LO; // FIXME.
176 0: I.getKey()->printPretty(Out, 0, PrintingPolicy(LO));
177 0: Out << " : " << I.getData();
178 0: }
179 :
180 0: Mgr.getConstraintManager().print(this, Out, nl, sep);
181 :
182 : // Print checker-specific data.
0: branch 3 not taken
0: branch 4 not taken
183 0: for (std::vector<Printer*>::iterator I = Mgr.Printers.begin(),
184 0: E = Mgr.Printers.end(); I != E; ++I) {
185 0: (*I)->Print(Out, this, nl, sep);
186 : }
187 0: }
188 :
189 0: void GRState::printDOT(llvm::raw_ostream& Out) const {
190 0: print(Out, "\\l", "\\|");
191 0: }
192 :
193 0: void GRState::printStdErr() const {
194 0: print(llvm::errs());
195 0: }
196 :
197 : //===----------------------------------------------------------------------===//
198 : // Generic Data Map.
199 : //===----------------------------------------------------------------------===//
200 :
201 74939: void* const* GRState::FindGDM(void* K) const {
202 74939: return GDM.lookup(K);
203 : }
204 :
205 : void*
206 : GRStateManager::FindGDMContext(void* K,
207 : void* (*CreateContext)(llvm::BumpPtrAllocator&),
208 28345: void (*DeleteContext)(void*)) {
209 :
210 28345: std::pair<void*, void (*)(void*)>& p = GDMContexts[K];
3864: branch 0 taken
24481: branch 1 taken
211 28345: if (!p.first) {
212 3864: p.first = CreateContext(Alloc);
213 3864: p.second = DeleteContext;
214 : }
215 :
216 28345: return p.first;
217 : }
218 :
219 26171: const GRState* GRStateManager::addGDM(const GRState* St, void* Key, void* Data){
220 26171: GRState::GenericDataMap M1 = St->getGDM();
221 26171: GRState::GenericDataMap M2 = GDMFactory.Add(M1, Key, Data);
222 :
14402: branch 1 taken
11769: branch 2 taken
223 26171: if (M1 == M2)
224 14402: return St;
225 :
226 11769: GRState NewSt = *St;
227 11769: NewSt.GDM = M2;
228 11769: return getPersistentState(NewSt);
229 : }
230 :
231 : //===----------------------------------------------------------------------===//
232 : // Utility.
233 : //===----------------------------------------------------------------------===//
234 :
235 : namespace {
0: branch 3 not taken
0: branch 4 not taken
0: branch 9 not taken
3124: branch 10 taken
236 3124: class ScanReachableSymbols : public SubRegionMap::Visitor {
237 : typedef llvm::DenseSet<const MemRegion*> VisitedRegionsTy;
238 :
239 : VisitedRegionsTy visited;
240 : const GRState *state;
241 : SymbolVisitor &visitor;
242 : llvm::OwningPtr<SubRegionMap> SRM;
243 : public:
244 :
245 3124: ScanReachableSymbols(const GRState *st, SymbolVisitor& v)
246 3124: : state(st), visitor(v) {}
247 :
248 : bool scan(nonloc::CompoundVal val);
249 : bool scan(SVal val);
250 : bool scan(const MemRegion *R);
251 :
252 : // From SubRegionMap::Visitor.
253 3: bool Visit(const MemRegion* Parent, const MemRegion* SubRegion) {
254 3: return scan(SubRegion);
255 : }
256 : };
257 : }
258 :
259 125: bool ScanReachableSymbols::scan(nonloc::CompoundVal val) {
459: branch 4 taken
125: branch 5 taken
260 584: for (nonloc::CompoundVal::iterator I=val.begin(), E=val.end(); I!=E; ++I)
0: branch 3 not taken
459: branch 4 taken
261 459: if (!scan(*I))
262 0: return false;
263 :
264 125: return true;
265 : }
266 :
267 5048: bool ScanReachableSymbols::scan(SVal val) {
1175: branch 1 taken
3873: branch 2 taken
268 5048: if (loc::MemRegionVal *X = dyn_cast<loc::MemRegionVal>(&val))
269 1175: return scan(X->getRegion());
270 :
26: branch 1 taken
3847: branch 2 taken
271 3873: if (nonloc::LocAsInteger *X = dyn_cast<nonloc::LocAsInteger>(&val))
272 26: return scan(X->getLoc());
273 :
413: branch 1 taken
3434: branch 2 taken
274 3847: if (SymbolRef Sym = val.getAsSymbol())
275 413: return visitor.VisitSymbol(Sym);
276 :
125: branch 1 taken
3309: branch 2 taken
277 3434: if (nonloc::CompoundVal *X = dyn_cast<nonloc::CompoundVal>(&val))
278 125: return scan(*X);
279 :
280 3309: return true;
281 : }
282 :
283 2740: bool ScanReachableSymbols::scan(const MemRegion *R) {
1493: branch 1 taken
1247: branch 2 taken
3: branch 4 taken
1490: branch 5 taken
1250: branch 6 taken
1490: branch 7 taken
284 2740: if (isa<MemSpaceRegion>(R) || visited.count(R))
285 1250: return true;
286 :
287 1490: visited.insert(R);
288 :
289 : // If this is a symbolic region, visit the symbol for the region.
1003: branch 1 taken
487: branch 2 taken
290 1490: if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
0: branch 2 not taken
1003: branch 3 taken
291 1003: if (!visitor.VisitSymbol(SR->getSymbol()))
292 0: return false;
293 :
294 : // If this is a subregion, also visit the parent regions.
1490: branch 1 taken
0: branch 2 not taken
295 1490: if (const SubRegion *SR = dyn_cast<SubRegion>(R))
0: branch 2 not taken
1490: branch 3 taken
296 1490: if (!scan(SR->getSuperRegion()))
297 0: return false;
298 :
299 : // Now look at the binding to this region (if any).
0: branch 3 not taken
1490: branch 4 taken
300 1490: if (!scan(state->getSValAsScalarOrLoc(R)))
301 0: return false;
302 :
303 : // Now look at the subregions.
1140: branch 1 taken
350: branch 2 taken
304 1490: if (!SRM.get())
305 : SRM.reset(state->getStateManager().getStoreManager().
306 1140: getSubRegionMap(state->getStore()));
307 :
308 1490: return SRM->iterSubRegions(R, *this);
309 : }
310 :
311 3073: bool GRState::scanReachableSymbols(SVal val, SymbolVisitor& visitor) const {
312 3073: ScanReachableSymbols S(this, visitor);
313 3073: return S.scan(val);
314 : }
315 :
316 : bool GRState::scanReachableSymbols(const SVal *I, const SVal *E,
317 0: SymbolVisitor &visitor) const {
318 0: ScanReachableSymbols S(this, visitor);
0: branch 0 not taken
0: branch 1 not taken
319 0: for ( ; I != E; ++I) {
0: branch 2 not taken
0: branch 3 not taken
320 0: if (!S.scan(*I))
321 0: return false;
322 : }
323 0: return true;
324 : }
325 :
326 : bool GRState::scanReachableSymbols(const MemRegion * const *I,
327 : const MemRegion * const *E,
328 51: SymbolVisitor &visitor) const {
329 51: ScanReachableSymbols S(this, visitor);
72: branch 0 taken
51: branch 1 taken
330 123: for ( ; I != E; ++I) {
0: branch 1 not taken
72: branch 2 taken
331 72: if (!S.scan(*I))
332 0: return false;
333 : }
334 51: return true;
335 : }
336 :
337 : //===----------------------------------------------------------------------===//
338 : // Queries.
339 : //===----------------------------------------------------------------------===//
340 :
341 : bool GRStateManager::isEqual(const GRState* state, const Expr* Ex,
342 144: const llvm::APSInt& Y) {
343 :
344 144: SVal V = state->getSVal(Ex);
345 :
0: branch 1 not taken
144: branch 2 taken
346 144: if (loc::ConcreteInt* X = dyn_cast<loc::ConcreteInt>(&V))
347 0: return X->getValue() == Y;
348 :
0: branch 1 not taken
144: branch 2 taken
349 144: if (nonloc::ConcreteInt* X = dyn_cast<nonloc::ConcreteInt>(&V))
350 0: return X->getValue() == Y;
351 :
144: branch 1 taken
0: branch 2 not taken
352 144: if (SymbolRef Sym = V.getAsSymbol())
353 144: return ConstraintMgr->isEqual(state, Sym, Y);
354 :
355 0: return false;
356 : }
357 :
358 144: bool GRStateManager::isEqual(const GRState* state, const Expr* Ex, uint64_t x) {
359 144: return isEqual(state, Ex, getBasicVals().getValue(x, Ex->getType()));
360 0: }
Generated: 2010-02-10 01:31 by zcov