 |
|
 |
|
| Files: |
1 |
|
Branches Taken: |
61.9% |
96 / 155 |
| Generated: |
2010-02-10 01:31 |
|
Branches Executed: |
71.6% |
111 / 155 |
| |
|
Line Coverage: |
81.6% |
204 / 250 |
| |
 |
|
 |
1 : //==- GRCoreEngine.cpp - Path-Sensitive Dataflow Engine ------------*- 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 defines a generic engine for intraprocedural, path-sensitive,
11 : // dataflow analysis via graph reachability engine.
12 : //
13 : //===----------------------------------------------------------------------===//
14 :
15 : #include "clang/Checker/PathSensitive/GRCoreEngine.h"
16 : #include "clang/Checker/PathSensitive/GRExprEngine.h"
17 : #include "clang/AST/Expr.h"
18 : #include "llvm/Support/Casting.h"
19 : #include "llvm/ADT/DenseMap.h"
20 : #include <vector>
21 : #include <queue>
22 :
23 : using llvm::cast;
24 : using llvm::isa;
25 : using namespace clang;
26 :
27 : //===----------------------------------------------------------------------===//
28 : // Worklist classes for exploration of reachable states.
29 : //===----------------------------------------------------------------------===//
30 :
31 : namespace {
0: branch 4 not taken
0: branch 5 not taken
0: branch 9 not taken
0: branch 10 not taken
32 0: class DFS : public GRWorkList {
33 : llvm::SmallVector<GRWorkListUnit,20> Stack;
34 : public:
35 0: virtual bool hasWork() const {
36 0: return !Stack.empty();
37 : }
38 :
39 0: virtual void Enqueue(const GRWorkListUnit& U) {
40 0: Stack.push_back(U);
41 0: }
42 :
43 0: virtual GRWorkListUnit Dequeue() {
0: branch 1 not taken
0: branch 2 not taken
44 0: assert (!Stack.empty());
45 0: const GRWorkListUnit& U = Stack.back();
46 0: Stack.pop_back(); // This technically "invalidates" U, but we are fine.
47 0: return U;
48 : }
49 : };
50 :
2138: branch 2 taken
0: branch 3 not taken
0: branch 7 not taken
0: branch 8 not taken
51 4276: class BFS : public GRWorkList {
52 : std::queue<GRWorkListUnit> Queue;
53 : public:
54 31606: virtual bool hasWork() const {
55 31606: return !Queue.empty();
56 : }
57 :
58 27330: virtual void Enqueue(const GRWorkListUnit& U) {
59 27330: Queue.push(U);
60 27330: }
61 :
62 27330: virtual GRWorkListUnit Dequeue() {
63 : // Don't use const reference. The subsequent pop_back() might make it
64 : // unsafe.
65 27330: GRWorkListUnit U = Queue.front();
66 27330: Queue.pop();
67 : return U;
68 : }
69 : };
70 :
71 : } // end anonymous namespace
72 :
73 : // Place the dstor for GRWorkList here because it contains virtual member
74 : // functions, and we the code for the dstor generated in one compilation unit.
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
75 2138: GRWorkList::~GRWorkList() {}
76 :
77 0: GRWorkList *GRWorkList::MakeDFS() { return new DFS(); }
78 2138: GRWorkList *GRWorkList::MakeBFS() { return new BFS(); }
79 :
80 : namespace {
0: branch 3 not taken
0: branch 4 not taken
0: branch 9 not taken
0: branch 10 not taken
81 0: class BFSBlockDFSContents : public GRWorkList {
82 : std::queue<GRWorkListUnit> Queue;
83 : llvm::SmallVector<GRWorkListUnit,20> Stack;
84 : public:
85 0: virtual bool hasWork() const {
0: branch 1 not taken
0: branch 2 not taken
0: branch 4 not taken
0: branch 5 not taken
86 0: return !Queue.empty() || !Stack.empty();
87 : }
88 :
89 0: virtual void Enqueue(const GRWorkListUnit& U) {
0: branch 3 not taken
0: branch 4 not taken
90 0: if (isa<BlockEntrance>(U.getNode()->getLocation()))
91 0: Queue.push(U);
92 : else
93 0: Stack.push_back(U);
94 0: }
95 :
96 0: virtual GRWorkListUnit Dequeue() {
97 : // Process all basic blocks to completion.
0: branch 1 not taken
0: branch 2 not taken
98 0: if (!Stack.empty()) {
99 0: const GRWorkListUnit& U = Stack.back();
100 0: Stack.pop_back(); // This technically "invalidates" U, but we are fine.
101 0: return U;
102 : }
103 :
0: branch 1 not taken
0: branch 2 not taken
104 0: assert(!Queue.empty());
105 : // Don't use const reference. The subsequent pop_back() might make it
106 : // unsafe.
107 0: GRWorkListUnit U = Queue.front();
108 0: Queue.pop();
109 0: return U;
110 : }
111 : };
112 : } // end anonymous namespace
113 :
114 0: GRWorkList* GRWorkList::MakeBFSBlockDFSContents() {
115 0: return new BFSBlockDFSContents();
116 : }
117 :
118 : //===----------------------------------------------------------------------===//
119 : // Core analysis engine.
120 : //===----------------------------------------------------------------------===//
121 2600: void GRCoreEngine::ProcessEndPath(GREndPathNodeBuilder& Builder) {
122 2600: SubEngine.ProcessEndPath(Builder);
123 2600: }
124 :
125 11886: void GRCoreEngine::ProcessStmt(CFGElement E, GRStmtNodeBuilder& Builder) {
126 11886: SubEngine.ProcessStmt(E, Builder);
127 11886: }
128 :
129 : bool GRCoreEngine::ProcessBlockEntrance(CFGBlock* Blk, const GRState* State,
130 6739: GRBlockCounter BC) {
131 6739: return SubEngine.ProcessBlockEntrance(Blk, State, BC);
132 : }
133 :
134 : void GRCoreEngine::ProcessBranch(Stmt* Condition, Stmt* Terminator,
135 2262: GRBranchNodeBuilder& Builder) {
136 2262: SubEngine.ProcessBranch(Condition, Terminator, Builder);
137 2262: }
138 :
139 10: void GRCoreEngine::ProcessIndirectGoto(GRIndirectGotoNodeBuilder& Builder) {
140 10: SubEngine.ProcessIndirectGoto(Builder);
141 10: }
142 :
143 20: void GRCoreEngine::ProcessSwitch(GRSwitchNodeBuilder& Builder) {
144 20: SubEngine.ProcessSwitch(Builder);
145 20: }
146 :
147 : /// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps.
148 2138: bool GRCoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps) {
149 :
2138: branch 2 taken
0: branch 3 not taken
150 2138: if (G->num_roots() == 0) { // Initialize the analysis by constructing
151 : // the root if none exists.
152 :
153 2138: CFGBlock* Entry = &(L->getCFG()->getEntry());
154 :
155 : assert (Entry->empty() &&
2138: branch 1 taken
0: branch 2 not taken
156 2138: "Entry block must be empty.");
157 :
158 : assert (Entry->succ_size() == 1 &&
2138: branch 1 taken
0: branch 2 not taken
159 2138: "Entry block must have 1 successor.");
160 :
161 : // Get the solitary successor.
162 2138: CFGBlock* Succ = *(Entry->succ_begin());
163 :
164 : // Construct an edge representing the
165 : // starting location in the function.
166 2138: BlockEdge StartLoc(Entry, Succ, L);
167 :
168 : // Set the current block counter to being empty.
169 2138: WList->setBlockCounter(BCounterFactory.GetEmptyCounter());
170 :
171 : // Generate the root.
172 2138: GenerateNode(StartLoc, getInitialState(L), 0);
173 : }
174 :
29468: branch 0 taken
0: branch 1 not taken
27330: branch 3 taken
2138: branch 4 taken
27330: branch 5 taken
2138: branch 6 taken
175 31606: while (Steps && WList->hasWork()) {
176 27330: --Steps;
177 27330: const GRWorkListUnit& WU = WList->Dequeue();
178 :
179 : // Set the current block counter.
180 27330: WList->setBlockCounter(WU.getBlockCounter());
181 :
182 : // Retrieve the node.
183 27330: ExplodedNode* Node = WU.getNode();
184 :
185 : // Dispatch on the location type.
9339: branch 2 taken
6544: branch 3 taken
0: branch 4 not taken
11447: branch 5 taken
186 27330: switch (Node->getLocation().getKind()) {
187 : case ProgramPoint::BlockEdgeKind:
188 9339: HandleBlockEdge(cast<BlockEdge>(Node->getLocation()), Node);
189 9339: break;
190 :
191 : case ProgramPoint::BlockEntranceKind:
192 6544: HandleBlockEntrance(cast<BlockEntrance>(Node->getLocation()), Node);
193 6544: break;
194 :
195 : case ProgramPoint::BlockExitKind:
196 0: assert (false && "BlockExit location never occur in forward analysis.");
197 : break;
198 :
199 : default:
0: branch 2 not taken
11447: branch 3 taken
200 11447: assert(isa<PostStmt>(Node->getLocation()));
201 : HandlePostStmt(cast<PostStmt>(Node->getLocation()), WU.getBlock(),
202 11447: WU.getIndex(), Node);
203 : break;
204 : }
205 : }
206 :
207 2138: return WList->hasWork();
208 : }
209 :
210 :
211 9339: void GRCoreEngine::HandleBlockEdge(const BlockEdge& L, ExplodedNode* Pred) {
212 :
213 9339: CFGBlock* Blk = L.getDst();
214 :
215 : // Check if we are entering the EXIT block.
2600: branch 3 taken
6739: branch 4 taken
216 9339: if (Blk == &(L.getLocationContext()->getCFG()->getExit())) {
217 :
218 : assert (L.getLocationContext()->getCFG()->getExit().size() == 0
2600: branch 4 taken
0: branch 5 not taken
219 2600: && "EXIT block cannot contain Stmts.");
220 :
221 : // Process the final state transition.
222 2600: GREndPathNodeBuilder Builder(Blk, Pred, this);
223 2600: ProcessEndPath(Builder);
224 :
225 : // This path is done. Don't enqueue any more nodes.
226 2600: return;
227 : }
228 :
229 : // FIXME: Should we allow ProcessBlockEntrance to also manipulate state?
230 :
6544: branch 2 taken
195: branch 3 taken
231 6739: if (ProcessBlockEntrance(Blk, Pred->State, WList->getBlockCounter()))
232 6544: GenerateNode(BlockEntrance(Blk, Pred->getLocationContext()), Pred->State, Pred);
233 : }
234 :
235 : void GRCoreEngine::HandleBlockEntrance(const BlockEntrance& L,
236 6544: ExplodedNode* Pred) {
237 :
238 : // Increment the block counter.
239 6544: GRBlockCounter Counter = WList->getBlockCounter();
240 6544: Counter = BCounterFactory.IncrementCount(Counter, L.getBlock()->getBlockID());
241 6544: WList->setBlockCounter(Counter);
242 :
243 : // Process the entrance of the block.
6314: branch 2 taken
230: branch 3 taken
244 6544: if (CFGElement E = L.getFirstElement()) {
245 : GRStmtNodeBuilder Builder(L.getBlock(), 0, Pred, this,
246 6314: SubEngine.getStateManager());
247 6314: ProcessStmt(E, Builder);
248 : }
249 : else
250 230: HandleBlockExit(L.getBlock(), Pred);
251 6544: }
252 :
253 6105: void GRCoreEngine::HandleBlockExit(CFGBlock * B, ExplodedNode* Pred) {
254 :
2386: branch 1 taken
3719: branch 2 taken
255 6105: if (Stmt* Term = B->getTerminator()) {
0: branch 1 not taken
87: branch 2 taken
161: branch 3 taken
8: branch 4 taken
23: branch 5 taken
426: branch 6 taken
94: branch 7 taken
1431: branch 8 taken
10: branch 9 taken
40: branch 10 taken
20: branch 11 taken
86: branch 12 taken
256 2386: switch (Term->getStmtClass()) {
257 : default:
258 0: assert(false && "Analysis for this terminator not implemented.");
259 : break;
260 :
261 : case Stmt::BinaryOperatorClass: // '&&' and '||'
262 87: HandleBranch(cast<BinaryOperator>(Term)->getLHS(), Term, B, Pred);
263 87: return;
264 :
265 : case Stmt::ConditionalOperatorClass:
266 161: HandleBranch(cast<ConditionalOperator>(Term)->getCond(), Term, B, Pred);
267 161: return;
268 :
269 : // FIXME: Use constant-folding in CFG construction to simplify this
270 : // case.
271 :
272 : case Stmt::ChooseExprClass:
273 8: HandleBranch(cast<ChooseExpr>(Term)->getCond(), Term, B, Pred);
274 8: return;
275 :
276 : case Stmt::DoStmtClass:
277 23: HandleBranch(cast<DoStmt>(Term)->getCond(), Term, B, Pred);
278 23: return;
279 :
280 : case Stmt::ForStmtClass:
281 426: HandleBranch(cast<ForStmt>(Term)->getCond(), Term, B, Pred);
282 426: return;
283 :
284 : case Stmt::ContinueStmtClass:
285 : case Stmt::BreakStmtClass:
286 : case Stmt::GotoStmtClass:
287 94: break;
288 :
289 : case Stmt::IfStmtClass:
290 1431: HandleBranch(cast<IfStmt>(Term)->getCond(), Term, B, Pred);
291 1431: return;
292 :
293 : case Stmt::IndirectGotoStmtClass: {
294 : // Only 1 successor: the indirect goto dispatch block.
0: branch 1 not taken
10: branch 2 taken
295 10: assert (B->succ_size() == 1);
296 :
297 : GRIndirectGotoNodeBuilder
298 : builder(Pred, B, cast<IndirectGotoStmt>(Term)->getTarget(),
299 10: *(B->succ_begin()), this);
300 :
301 10: ProcessIndirectGoto(builder);
302 10: return;
303 : }
304 :
305 : case Stmt::ObjCForCollectionStmtClass: {
306 : // In the case of ObjCForCollectionStmt, it appears twice in a CFG:
307 : //
308 : // (1) inside a basic block, which represents the binding of the
309 : // 'element' variable to a value.
310 : // (2) in a terminator, which represents the branch.
311 : //
312 : // For (1), subengines will bind a value (i.e., 0 or 1) indicating
313 : // whether or not collection contains any more elements. We cannot
314 : // just test to see if the element is nil because a container can
315 : // contain nil elements.
316 40: HandleBranch(Term, Term, B, Pred);
317 40: return;
318 : }
319 :
320 : case Stmt::SwitchStmtClass: {
321 : GRSwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Term)->getCond(),
322 20: this);
323 :
324 20: ProcessSwitch(builder);
325 20: return;
326 : }
327 :
328 : case Stmt::WhileStmtClass:
329 86: HandleBranch(cast<WhileStmt>(Term)->getCond(), Term, B, Pred);
330 86: return;
331 : }
332 : }
333 :
334 : assert (B->succ_size() == 1 &&
3813: branch 1 taken
0: branch 2 not taken
335 3813: "Blocks with no terminator should have at most 1 successor.");
336 :
337 : GenerateNode(BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()),
338 3813: Pred->State, Pred);
339 : }
340 :
341 : void GRCoreEngine::HandleBranch(Stmt* Cond, Stmt* Term, CFGBlock * B,
342 2262: ExplodedNode* Pred) {
0: branch 1 not taken
2262: branch 2 taken
343 2262: assert (B->succ_size() == 2);
344 :
345 : GRBranchNodeBuilder Builder(B, *(B->succ_begin()), *(B->succ_begin()+1),
346 2262: Pred, this);
347 :
348 2262: ProcessBranch(Cond, Term, Builder);
349 2262: }
350 :
351 : void GRCoreEngine::HandlePostStmt(const PostStmt& L, CFGBlock* B,
352 11447: unsigned StmtIdx, ExplodedNode* Pred) {
353 :
0: branch 1 not taken
11447: branch 2 taken
354 11447: assert (!B->empty());
355 :
5875: branch 1 taken
5572: branch 2 taken
356 11447: if (StmtIdx == B->size())
357 5875: HandleBlockExit(B, Pred);
358 : else {
359 : GRStmtNodeBuilder Builder(B, StmtIdx, Pred, this,
360 5572: SubEngine.getStateManager());
361 5572: ProcessStmt((*B)[StmtIdx], Builder);
362 : }
363 11447: }
364 :
365 : /// GenerateNode - Utility method to generate nodes, hook up successors,
366 : /// and add nodes to the worklist.
367 : void GRCoreEngine::GenerateNode(const ProgramPoint& Loc,
368 12495: const GRState* State, ExplodedNode* Pred) {
369 :
370 : bool IsNew;
371 12495: ExplodedNode* Node = G->getNode(Loc, State, &IsNew);
372 :
10357: branch 0 taken
2138: branch 1 taken
373 12495: if (Pred)
374 10357: Node->addPredecessor(Pred, *G); // Link 'Node' with its predecessor.
375 : else {
0: branch 0 not taken
2138: branch 1 taken
376 2138: assert (IsNew);
377 2138: G->addRoot(Node); // 'Node' has no predecessor. Make it a root.
378 : }
379 :
380 : // Only add 'Node' to the worklist if it was freshly generated.
12495: branch 0 taken
0: branch 1 not taken
381 12495: if (IsNew) WList->Enqueue(Node);
382 12495: }
383 :
384 : GRStmtNodeBuilder::GRStmtNodeBuilder(CFGBlock* b, unsigned idx,
385 : ExplodedNode* N, GRCoreEngine* e,
386 11886: GRStateManager &mgr)
387 : : Eng(*e), B(*b), Idx(idx), Pred(N), LastNode(N), Mgr(mgr), Auditor(0),
388 : PurgingDeadSymbols(false), BuildSinks(false), HasGeneratedNode(false),
389 11886: PointKind(ProgramPoint::PostStmtKind), Tag(0) {
390 11886: Deferred.insert(N);
391 11886: CleanedState = getLastNode()->getState();
392 11886: }
393 :
394 11886: GRStmtNodeBuilder::~GRStmtNodeBuilder() {
12154: branch 4 taken
11886: branch 5 taken
0: branch 10 not taken
0: branch 11 not taken
395 24040: for (DeferredTy::iterator I=Deferred.begin(), E=Deferred.end(); I!=E; ++I)
11447: branch 2 taken
707: branch 3 taken
0: branch 6 not taken
0: branch 7 not taken
396 12154: if (!(*I)->isSink())
397 11447: GenerateAutoTransition(*I);
398 11886: }
399 :
400 11447: void GRStmtNodeBuilder::GenerateAutoTransition(ExplodedNode* N) {
0: branch 1 not taken
11447: branch 2 taken
401 11447: assert (!N->isSink());
402 :
403 11447: PostStmt Loc(getStmt(), N->getLocationContext());
404 :
8256: branch 2 taken
3191: branch 3 taken
405 11447: if (Loc == N->getLocation()) {
406 : // Note: 'N' should be a fresh node because otherwise it shouldn't be
407 : // a member of Deferred.
408 8256: Eng.WList->Enqueue(N, B, Idx+1);
409 8256: return;
410 : }
411 :
412 : bool IsNew;
413 3191: ExplodedNode* Succ = Eng.G->getNode(Loc, N->State, &IsNew);
414 3191: Succ->addPredecessor(N, *Eng.G);
415 :
3191: branch 0 taken
0: branch 1 not taken
416 3191: if (IsNew)
417 3191: Eng.WList->Enqueue(Succ, B, Idx+1);
418 : }
419 :
420 : static ProgramPoint GetProgramPoint(const Stmt *S, ProgramPoint::Kind K,
421 36497: const LocationContext *LC, const void *tag){
0: branch 0 not taken
185: branch 1 taken
17373: branch 2 taken
429: branch 3 taken
7942: branch 4 taken
2466: branch 5 taken
2212: branch 6 taken
4980: branch 7 taken
910: branch 8 taken
422 36497: switch (K) {
423 : default:
424 0: assert(false && "Unhandled ProgramPoint kind");
425 : case ProgramPoint::PreStmtKind:
426 185: return PreStmt(S, LC, tag);
427 : case ProgramPoint::PostStmtKind:
428 17373: return PostStmt(S, LC, tag);
429 : case ProgramPoint::PreLoadKind:
430 429: return PreLoad(S, LC, tag);
431 : case ProgramPoint::PostLoadKind:
432 7942: return PostLoad(S, LC, tag);
433 : case ProgramPoint::PreStoreKind:
434 2466: return PreStore(S, LC, tag);
435 : case ProgramPoint::PostStoreKind:
436 2212: return PostStore(S, LC, tag);
437 : case ProgramPoint::PostLValueKind:
438 4980: return PostLValue(S, LC, tag);
439 : case ProgramPoint::PostPurgeDeadSymbolsKind:
440 910: return PostPurgeDeadSymbols(S, LC, tag);
441 : }
442 : }
443 :
444 : ExplodedNode*
445 : GRStmtNodeBuilder::generateNodeInternal(const Stmt* S, const GRState* state,
446 : ExplodedNode* Pred,
447 : ProgramPoint::Kind K,
448 36497: const void *tag) {
449 :
450 36497: const ProgramPoint &L = GetProgramPoint(S, K, Pred->getLocationContext(),tag);
451 36497: return generateNodeInternal(L, state, Pred);
452 : }
453 :
454 : ExplodedNode*
455 : GRStmtNodeBuilder::generateNodeInternal(const ProgramPoint &Loc,
456 : const GRState* State,
457 36622: ExplodedNode* Pred) {
458 : bool IsNew;
459 36622: ExplodedNode* N = Eng.G->getNode(Loc, State, &IsNew);
460 36622: N->addPredecessor(Pred, *Eng.G);
461 36622: Deferred.erase(Pred);
462 :
36486: branch 0 taken
136: branch 1 taken
463 36622: if (IsNew) {
464 36486: Deferred.insert(N);
465 36486: LastNode = N;
466 36486: return N;
467 : }
468 :
469 136: LastNode = NULL;
470 136: return NULL;
471 : }
472 :
473 : ExplodedNode* GRBranchNodeBuilder::generateNode(const GRState* State,
474 3487: bool branch) {
475 :
476 : // If the branch has been marked infeasible we should not generate a node.
209: branch 1 taken
3278: branch 2 taken
477 3487: if (!isFeasible(branch))
478 209: return NULL;
479 :
480 : bool IsNew;
481 :
482 : ExplodedNode* Succ =
483 : Eng.G->getNode(BlockEdge(Src,branch ? DstT:DstF,Pred->getLocationContext()),
1699: branch 1 taken
1579: branch 2 taken
484 3278: State, &IsNew);
485 :
486 3278: Succ->addPredecessor(Pred, *Eng.G);
487 :
1699: branch 0 taken
1579: branch 1 taken
488 3278: if (branch)
489 1699: GeneratedTrue = true;
490 : else
491 1579: GeneratedFalse = true;
492 :
3268: branch 0 taken
10: branch 1 taken
493 3278: if (IsNew) {
494 3268: Deferred.push_back(Succ);
495 3268: return Succ;
496 : }
497 :
498 10: return NULL;
499 : }
500 :
501 2262: GRBranchNodeBuilder::~GRBranchNodeBuilder() {
87: branch 0 taken
2175: branch 1 taken
87: branch 3 taken
87: branch 4 taken
502 2262: if (!GeneratedTrue) generateNode(Pred->State, true);
136: branch 0 taken
2126: branch 1 taken
136: branch 3 taken
136: branch 4 taken
503 2262: if (!GeneratedFalse) generateNode(Pred->State, false);
504 :
3268: branch 2 taken
2262: branch 3 taken
0: branch 6 not taken
0: branch 7 not taken
505 5530: for (DeferredTy::iterator I=Deferred.begin(), E=Deferred.end(); I!=E; ++I)
3238: branch 1 taken
30: branch 2 taken
0: branch 5 not taken
0: branch 6 not taken
506 3268: if (!(*I)->isSink()) Eng.WList->Enqueue(*I);
507 2262: }
508 :
509 :
510 : ExplodedNode*
511 : GRIndirectGotoNodeBuilder::generateNode(const iterator& I, const GRState* St,
512 0: bool isSink) {
513 : bool IsNew;
514 :
515 : ExplodedNode* Succ = Eng.G->getNode(BlockEdge(Src, I.getBlock(),
516 0: Pred->getLocationContext()), St, &IsNew);
517 :
518 0: Succ->addPredecessor(Pred, *Eng.G);
519 :
0: branch 0 not taken
0: branch 1 not taken
520 0: if (IsNew) {
521 :
0: branch 0 not taken
0: branch 1 not taken
522 0: if (isSink)
523 0: Succ->markAsSink();
524 : else
525 0: Eng.WList->Enqueue(Succ);
526 :
527 0: return Succ;
528 : }
529 :
530 0: return NULL;
531 : }
532 :
533 :
534 : ExplodedNode*
535 134: GRSwitchNodeBuilder::generateCaseStmtNode(const iterator& I, const GRState* St){
536 :
537 : bool IsNew;
538 :
539 : ExplodedNode* Succ = Eng.G->getNode(BlockEdge(Src, I.getBlock(),
540 134: Pred->getLocationContext()), St, &IsNew);
541 134: Succ->addPredecessor(Pred, *Eng.G);
542 :
134: branch 0 taken
0: branch 1 not taken
543 134: if (IsNew) {
544 134: Eng.WList->Enqueue(Succ);
545 134: return Succ;
546 : }
547 :
548 0: return NULL;
549 : }
550 :
551 :
552 : ExplodedNode*
553 16: GRSwitchNodeBuilder::generateDefaultCaseNode(const GRState* St, bool isSink) {
554 :
555 : // Get the block for the default case.
0: branch 3 not taken
16: branch 4 taken
556 16: assert (Src->succ_rbegin() != Src->succ_rend());
557 16: CFGBlock* DefaultBlock = *Src->succ_rbegin();
558 :
559 : bool IsNew;
560 :
561 : ExplodedNode* Succ = Eng.G->getNode(BlockEdge(Src, DefaultBlock,
562 16: Pred->getLocationContext()), St, &IsNew);
563 16: Succ->addPredecessor(Pred, *Eng.G);
564 :
16: branch 0 taken
0: branch 1 not taken
565 16: if (IsNew) {
0: branch 0 not taken
16: branch 1 taken
566 16: if (isSink)
567 0: Succ->markAsSink();
568 : else
569 16: Eng.WList->Enqueue(Succ);
570 :
571 16: return Succ;
572 : }
573 :
574 0: return NULL;
575 : }
576 :
577 2600: GREndPathNodeBuilder::~GREndPathNodeBuilder() {
578 : // Auto-generate an EOP node if one has not been generated.
2485: branch 0 taken
115: branch 1 taken
2485: branch 3 taken
2485: branch 4 taken
579 2600: if (!HasGeneratedNode) generateNode(Pred->State);
580 2600: }
581 :
582 : ExplodedNode*
583 : GREndPathNodeBuilder::generateNode(const GRState* State, const void *tag,
584 2609: ExplodedNode* P) {
585 2609: HasGeneratedNode = true;
586 : bool IsNew;
587 :
588 : ExplodedNode* Node = Eng.G->getNode(BlockEntrance(&B,
589 2609: Pred->getLocationContext(), tag), State, &IsNew);
590 :
2608: branch 1 taken
1: branch 2 taken
591 2609: Node->addPredecessor(P ? P : Pred, *Eng.G);
592 :
2555: branch 0 taken
54: branch 1 taken
593 2609: if (IsNew) {
594 2555: Eng.G->addEndOfPath(Node);
595 2555: return Node;
596 : }
597 :
598 54: return NULL;
599 : }
Generated: 2010-02-10 01:31 by zcov