CoreEngine.cpp revision 868e78d59d2dfaf9cda511925e5a58f3a712db96 
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
23using llvm::cast;
24using llvm::isa;
25using namespace clang;
26
27//===----------------------------------------------------------------------===//
28// Worklist classes for exploration of reachable states.
29//===----------------------------------------------------------------------===//
30
31namespace {
32class DFS : public GRWorkList {
33  llvm::SmallVector<GRWorkListUnit,20> Stack;
34public:
35  virtual bool hasWork() const {
36    return !Stack.empty();
37  }
38
39  virtual void Enqueue(const GRWorkListUnit& U) {
40    Stack.push_back(U);
41  }
42
43  virtual GRWorkListUnit Dequeue() {
44    assert (!Stack.empty());
45    const GRWorkListUnit& U = Stack.back();
46    Stack.pop_back(); // This technically "invalidates" U, but we are fine.
47    return U;
48  }
49};
50
51class BFS : public GRWorkList {
52  std::queue<GRWorkListUnit> Queue;
53public:
54  virtual bool hasWork() const {
55    return !Queue.empty();
56  }
57
58  virtual void Enqueue(const GRWorkListUnit& U) {
59    Queue.push(U);
60  }
61
62  virtual GRWorkListUnit Dequeue() {
63    // Don't use const reference.  The subsequent pop_back() might make it
64    // unsafe.
65    GRWorkListUnit U = Queue.front();
66    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.
75GRWorkList::~GRWorkList() {}
76
77GRWorkList *GRWorkList::MakeDFS() { return new DFS(); }
78GRWorkList *GRWorkList::MakeBFS() { return new BFS(); }
79
80namespace {
81  class BFSBlockDFSContents : public GRWorkList {
82    std::queue<GRWorkListUnit> Queue;
83    llvm::SmallVector<GRWorkListUnit,20> Stack;
84  public:
85    virtual bool hasWork() const {
86      return !Queue.empty() || !Stack.empty();
87    }
88
89    virtual void Enqueue(const GRWorkListUnit& U) {
90      if (isa<BlockEntrance>(U.getNode()->getLocation()))
91        Queue.push(U);
92      else
93        Stack.push_back(U);
94    }
95
96    virtual GRWorkListUnit Dequeue() {
97      // Process all basic blocks to completion.
98      if (!Stack.empty()) {
99        const GRWorkListUnit& U = Stack.back();
100        Stack.pop_back(); // This technically "invalidates" U, but we are fine.
101        return U;
102      }
103
104      assert(!Queue.empty());
105      // Don't use const reference.  The subsequent pop_back() might make it
106      // unsafe.
107      GRWorkListUnit U = Queue.front();
108      Queue.pop();
109      return U;
110    }
111  };
112} // end anonymous namespace
113
114GRWorkList* GRWorkList::MakeBFSBlockDFSContents() {
115  return new BFSBlockDFSContents();
116}
117
118//===----------------------------------------------------------------------===//
119// Core analysis engine.
120//===----------------------------------------------------------------------===//
121void GRCoreEngine::ProcessEndPath(GREndPathNodeBuilder& Builder) {
122  SubEngine.ProcessEndPath(Builder);
123}
124
125void GRCoreEngine::ProcessStmt(CFGElement E, GRStmtNodeBuilder& Builder) {
126  SubEngine.ProcessStmt(E, Builder);
127}
128
129bool GRCoreEngine::ProcessBlockEntrance(CFGBlock* Blk, const ExplodedNode *Pred,
130                                        GRBlockCounter BC) {
131  return SubEngine.ProcessBlockEntrance(Blk, Pred, BC);
132}
133
134void GRCoreEngine::ProcessBranch(Stmt* Condition, Stmt* Terminator,
135                   GRBranchNodeBuilder& Builder) {
136  SubEngine.ProcessBranch(Condition, Terminator, Builder);
137}
138
139void GRCoreEngine::ProcessIndirectGoto(GRIndirectGotoNodeBuilder& Builder) {
140  SubEngine.ProcessIndirectGoto(Builder);
141}
142
143void GRCoreEngine::ProcessSwitch(GRSwitchNodeBuilder& Builder) {
144  SubEngine.ProcessSwitch(Builder);
145}
146
147void GRCoreEngine::ProcessCallEnter(GRCallEnterNodeBuilder &Builder) {
148  SubEngine.ProcessCallEnter(Builder);
149}
150
151void GRCoreEngine::ProcessCallExit(GRCallExitNodeBuilder &Builder) {
152  SubEngine.ProcessCallExit(Builder);
153}
154
155/// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps.
156bool GRCoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps) {
157
158  if (G->num_roots() == 0) { // Initialize the analysis by constructing
159    // the root if none exists.
160
161    CFGBlock* Entry = &(L->getCFG()->getEntry());
162
163    assert (Entry->empty() &&
164            "Entry block must be empty.");
165
166    assert (Entry->succ_size() == 1 &&
167            "Entry block must have 1 successor.");
168
169    // Get the solitary successor.
170    CFGBlock* Succ = *(Entry->succ_begin());
171
172    // Construct an edge representing the
173    // starting location in the function.
174    BlockEdge StartLoc(Entry, Succ, L);
175
176    // Set the current block counter to being empty.
177    WList->setBlockCounter(BCounterFactory.GetEmptyCounter());
178
179    // Generate the root.
180    GenerateNode(StartLoc, getInitialState(L), 0);
181  }
182
183  while (Steps && WList->hasWork()) {
184    --Steps;
185    const GRWorkListUnit& WU = WList->Dequeue();
186
187    // Set the current block counter.
188    WList->setBlockCounter(WU.getBlockCounter());
189
190    // Retrieve the node.
191    ExplodedNode* Node = WU.getNode();
192
193    // Dispatch on the location type.
194    switch (Node->getLocation().getKind()) {
195      case ProgramPoint::BlockEdgeKind:
196        HandleBlockEdge(cast<BlockEdge>(Node->getLocation()), Node);
197        break;
198
199      case ProgramPoint::BlockEntranceKind:
200        HandleBlockEntrance(cast<BlockEntrance>(Node->getLocation()), Node);
201        break;
202
203      case ProgramPoint::BlockExitKind:
204        assert (false && "BlockExit location never occur in forward analysis.");
205        break;
206
207      case ProgramPoint::CallEnterKind:
208        HandleCallEnter(cast<CallEnter>(Node->getLocation()), WU.getBlock(),
209                        WU.getIndex(), Node);
210        break;
211
212      case ProgramPoint::CallExitKind:
213        HandleCallExit(cast<CallExit>(Node->getLocation()), Node);
214        break;
215
216      default:
217        assert(isa<PostStmt>(Node->getLocation()));
218        HandlePostStmt(cast<PostStmt>(Node->getLocation()), WU.getBlock(),
219                       WU.getIndex(), Node);
220        break;
221    }
222  }
223
224  return WList->hasWork();
225}
226
227void GRCoreEngine::HandleCallEnter(const CallEnter &L, const CFGBlock *Block,
228                                   unsigned Index, ExplodedNode *Pred) {
229  GRCallEnterNodeBuilder Builder(*this, Pred, L.getCallExpr(), L.getCallee(),
230                                 Block, Index);
231  ProcessCallEnter(Builder);
232}
233
234void GRCoreEngine::HandleCallExit(const CallExit &L, ExplodedNode *Pred) {
235  GRCallExitNodeBuilder Builder(*this, Pred);
236  ProcessCallExit(Builder);
237}
238
239void GRCoreEngine::HandleBlockEdge(const BlockEdge& L, ExplodedNode* Pred) {
240
241  CFGBlock* Blk = L.getDst();
242
243  // Check if we are entering the EXIT block.
244  if (Blk == &(L.getLocationContext()->getCFG()->getExit())) {
245
246    assert (L.getLocationContext()->getCFG()->getExit().size() == 0
247            && "EXIT block cannot contain Stmts.");
248
249    // Process the final state transition.
250    GREndPathNodeBuilder Builder(Blk, Pred, this);
251    ProcessEndPath(Builder);
252
253    // This path is done. Don't enqueue any more nodes.
254    return;
255  }
256
257  // FIXME: Should we allow ProcessBlockEntrance to also manipulate state?
258
259  if (ProcessBlockEntrance(Blk, Pred, WList->getBlockCounter()))
260    GenerateNode(BlockEntrance(Blk, Pred->getLocationContext()), Pred->State, Pred);
261}
262
263void GRCoreEngine::HandleBlockEntrance(const BlockEntrance& L,
264                                       ExplodedNode* Pred) {
265
266  // Increment the block counter.
267  GRBlockCounter Counter = WList->getBlockCounter();
268  Counter = BCounterFactory.IncrementCount(Counter,
269                             Pred->getLocationContext()->getCurrentStackFrame(),
270                                           L.getBlock()->getBlockID());
271  WList->setBlockCounter(Counter);
272
273  // Process the entrance of the block.
274  if (CFGElement E = L.getFirstElement()) {
275    GRStmtNodeBuilder Builder(L.getBlock(), 0, Pred, this,
276                              SubEngine.getStateManager());
277    ProcessStmt(E, Builder);
278  }
279  else
280    HandleBlockExit(L.getBlock(), Pred);
281}
282
283void GRCoreEngine::HandleBlockExit(CFGBlock * B, ExplodedNode* Pred) {
284
285  if (Stmt* Term = B->getTerminator()) {
286    switch (Term->getStmtClass()) {
287      default:
288        assert(false && "Analysis for this terminator not implemented.");
289        break;
290
291      case Stmt::BinaryOperatorClass: // '&&' and '||'
292        HandleBranch(cast<BinaryOperator>(Term)->getLHS(), Term, B, Pred);
293        return;
294
295      case Stmt::ConditionalOperatorClass:
296        HandleBranch(cast<ConditionalOperator>(Term)->getCond(), Term, B, Pred);
297        return;
298
299        // FIXME: Use constant-folding in CFG construction to simplify this
300        // case.
301
302      case Stmt::ChooseExprClass:
303        HandleBranch(cast<ChooseExpr>(Term)->getCond(), Term, B, Pred);
304        return;
305
306      case Stmt::DoStmtClass:
307        HandleBranch(cast<DoStmt>(Term)->getCond(), Term, B, Pred);
308        return;
309
310      case Stmt::ForStmtClass:
311        HandleBranch(cast<ForStmt>(Term)->getCond(), Term, B, Pred);
312        return;
313
314      case Stmt::ContinueStmtClass:
315      case Stmt::BreakStmtClass:
316      case Stmt::GotoStmtClass:
317        break;
318
319      case Stmt::IfStmtClass:
320        HandleBranch(cast<IfStmt>(Term)->getCond(), Term, B, Pred);
321        return;
322
323      case Stmt::IndirectGotoStmtClass: {
324        // Only 1 successor: the indirect goto dispatch block.
325        assert (B->succ_size() == 1);
326
327        GRIndirectGotoNodeBuilder
328           builder(Pred, B, cast<IndirectGotoStmt>(Term)->getTarget(),
329                   *(B->succ_begin()), this);
330
331        ProcessIndirectGoto(builder);
332        return;
333      }
334
335      case Stmt::ObjCForCollectionStmtClass: {
336        // In the case of ObjCForCollectionStmt, it appears twice in a CFG:
337        //
338        //  (1) inside a basic block, which represents the binding of the
339        //      'element' variable to a value.
340        //  (2) in a terminator, which represents the branch.
341        //
342        // For (1), subengines will bind a value (i.e., 0 or 1) indicating
343        // whether or not collection contains any more elements.  We cannot
344        // just test to see if the element is nil because a container can
345        // contain nil elements.
346        HandleBranch(Term, Term, B, Pred);
347        return;
348      }
349
350      case Stmt::SwitchStmtClass: {
351        GRSwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Term)->getCond(),
352                                    this);
353
354        ProcessSwitch(builder);
355        return;
356      }
357
358      case Stmt::WhileStmtClass:
359        HandleBranch(cast<WhileStmt>(Term)->getCond(), Term, B, Pred);
360        return;
361    }
362  }
363
364  assert (B->succ_size() == 1 &&
365          "Blocks with no terminator should have at most 1 successor.");
366
367  GenerateNode(BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()),
368               Pred->State, Pred);
369}
370
371void GRCoreEngine::HandleBranch(Stmt* Cond, Stmt* Term, CFGBlock * B,
372                                ExplodedNode* Pred) {
373  assert (B->succ_size() == 2);
374
375  GRBranchNodeBuilder Builder(B, *(B->succ_begin()), *(B->succ_begin()+1),
376                              Pred, this);
377
378  ProcessBranch(Cond, Term, Builder);
379}
380
381void GRCoreEngine::HandlePostStmt(const PostStmt& L, CFGBlock* B,
382                                  unsigned StmtIdx, ExplodedNode* Pred) {
383
384  assert (!B->empty());
385
386  if (StmtIdx == B->size())
387    HandleBlockExit(B, Pred);
388  else {
389    GRStmtNodeBuilder Builder(B, StmtIdx, Pred, this,
390                              SubEngine.getStateManager());
391    ProcessStmt((*B)[StmtIdx], Builder);
392  }
393}
394
395/// GenerateNode - Utility method to generate nodes, hook up successors,
396///  and add nodes to the worklist.
397void GRCoreEngine::GenerateNode(const ProgramPoint& Loc,
398                                const GRState* State, ExplodedNode* Pred) {
399
400  bool IsNew;
401  ExplodedNode* Node = G->getNode(Loc, State, &IsNew);
402
403  if (Pred)
404    Node->addPredecessor(Pred, *G);  // Link 'Node' with its predecessor.
405  else {
406    assert (IsNew);
407    G->addRoot(Node);  // 'Node' has no predecessor.  Make it a root.
408  }
409
410  // Only add 'Node' to the worklist if it was freshly generated.
411  if (IsNew) WList->Enqueue(Node);
412}
413
414GRStmtNodeBuilder::GRStmtNodeBuilder(CFGBlock* b, unsigned idx,
415                                     ExplodedNode* N, GRCoreEngine* e,
416                                     GRStateManager &mgr)
417  : Eng(*e), B(*b), Idx(idx), Pred(N), Mgr(mgr), Auditor(0),
418    PurgingDeadSymbols(false), BuildSinks(false), HasGeneratedNode(false),
419    PointKind(ProgramPoint::PostStmtKind), Tag(0) {
420  Deferred.insert(N);
421  CleanedState = Pred->getState();
422}
423
424GRStmtNodeBuilder::~GRStmtNodeBuilder() {
425  for (DeferredTy::iterator I=Deferred.begin(), E=Deferred.end(); I!=E; ++I)
426    if (!(*I)->isSink())
427      GenerateAutoTransition(*I);
428}
429
430void GRStmtNodeBuilder::GenerateAutoTransition(ExplodedNode* N) {
431  assert (!N->isSink());
432
433  // Check if this node entered a callee.
434  if (isa<CallEnter>(N->getLocation())) {
435    // Still use the index of the CallExpr. It's needed to create the callee
436    // StackFrameContext.
437    Eng.WList->Enqueue(N, B, Idx);
438    return;
439  }
440
441  PostStmt Loc(getStmt(), N->getLocationContext());
442
443  if (Loc == N->getLocation()) {
444    // Note: 'N' should be a fresh node because otherwise it shouldn't be
445    // a member of Deferred.
446    Eng.WList->Enqueue(N, B, Idx+1);
447    return;
448  }
449
450  bool IsNew;
451  ExplodedNode* Succ = Eng.G->getNode(Loc, N->State, &IsNew);
452  Succ->addPredecessor(N, *Eng.G);
453
454  if (IsNew)
455    Eng.WList->Enqueue(Succ, B, Idx+1);
456}
457
458ExplodedNode* GRStmtNodeBuilder::MakeNode(ExplodedNodeSet& Dst, Stmt* S,
459                                          ExplodedNode* Pred, const GRState* St,
460                                          ProgramPoint::Kind K) {
461  const GRState* PredState = GetState(Pred);
462
463  // If the state hasn't changed, don't generate a new node.
464  if (!BuildSinks && St == PredState && Auditor == 0) {
465    Dst.Add(Pred);
466    return NULL;
467  }
468
469  ExplodedNode* N = generateNode(S, St, Pred, K);
470
471  if (N) {
472    if (BuildSinks)
473      N->markAsSink();
474    else {
475      if (Auditor && Auditor->Audit(N, Mgr))
476        N->markAsSink();
477
478      Dst.Add(N);
479    }
480  }
481
482  return N;
483}
484
485static ProgramPoint GetProgramPoint(const Stmt *S, ProgramPoint::Kind K,
486                                    const LocationContext *LC, const void *tag){
487  switch (K) {
488    default:
489      assert(false && "Unhandled ProgramPoint kind");
490    case ProgramPoint::PreStmtKind:
491      return PreStmt(S, LC, tag);
492    case ProgramPoint::PostStmtKind:
493      return PostStmt(S, LC, tag);
494    case ProgramPoint::PreLoadKind:
495      return PreLoad(S, LC, tag);
496    case ProgramPoint::PostLoadKind:
497      return PostLoad(S, LC, tag);
498    case ProgramPoint::PreStoreKind:
499      return PreStore(S, LC, tag);
500    case ProgramPoint::PostStoreKind:
501      return PostStore(S, LC, tag);
502    case ProgramPoint::PostLValueKind:
503      return PostLValue(S, LC, tag);
504    case ProgramPoint::PostPurgeDeadSymbolsKind:
505      return PostPurgeDeadSymbols(S, LC, tag);
506  }
507}
508
509ExplodedNode*
510GRStmtNodeBuilder::generateNodeInternal(const Stmt* S, const GRState* state,
511                                        ExplodedNode* Pred,
512                                        ProgramPoint::Kind K,
513                                        const void *tag) {
514
515  const ProgramPoint &L = GetProgramPoint(S, K, Pred->getLocationContext(),tag);
516  return generateNodeInternal(L, state, Pred);
517}
518
519ExplodedNode*
520GRStmtNodeBuilder::generateNodeInternal(const ProgramPoint &Loc,
521                                        const GRState* State,
522                                        ExplodedNode* Pred) {
523  bool IsNew;
524  ExplodedNode* N = Eng.G->getNode(Loc, State, &IsNew);
525  N->addPredecessor(Pred, *Eng.G);
526  Deferred.erase(Pred);
527
528  if (IsNew) {
529    Deferred.insert(N);
530    return N;
531  }
532
533  return NULL;
534}
535
536ExplodedNode* GRBranchNodeBuilder::generateNode(const GRState* State,
537                                                bool branch) {
538
539  // If the branch has been marked infeasible we should not generate a node.
540  if (!isFeasible(branch))
541    return NULL;
542
543  bool IsNew;
544
545  ExplodedNode* Succ =
546    Eng.G->getNode(BlockEdge(Src,branch ? DstT:DstF,Pred->getLocationContext()),
547                   State, &IsNew);
548
549  Succ->addPredecessor(Pred, *Eng.G);
550
551  if (branch)
552    GeneratedTrue = true;
553  else
554    GeneratedFalse = true;
555
556  if (IsNew) {
557    Deferred.push_back(Succ);
558    return Succ;
559  }
560
561  return NULL;
562}
563
564GRBranchNodeBuilder::~GRBranchNodeBuilder() {
565  if (!GeneratedTrue) generateNode(Pred->State, true);
566  if (!GeneratedFalse) generateNode(Pred->State, false);
567
568  for (DeferredTy::iterator I=Deferred.begin(), E=Deferred.end(); I!=E; ++I)
569    if (!(*I)->isSink()) Eng.WList->Enqueue(*I);
570}
571
572
573ExplodedNode*
574GRIndirectGotoNodeBuilder::generateNode(const iterator& I, const GRState* St,
575                                        bool isSink) {
576  bool IsNew;
577
578  ExplodedNode* Succ = Eng.G->getNode(BlockEdge(Src, I.getBlock(),
579                                      Pred->getLocationContext()), St, &IsNew);
580
581  Succ->addPredecessor(Pred, *Eng.G);
582
583  if (IsNew) {
584
585    if (isSink)
586      Succ->markAsSink();
587    else
588      Eng.WList->Enqueue(Succ);
589
590    return Succ;
591  }
592
593  return NULL;
594}
595
596
597ExplodedNode*
598GRSwitchNodeBuilder::generateCaseStmtNode(const iterator& I, const GRState* St){
599
600  bool IsNew;
601
602  ExplodedNode* Succ = Eng.G->getNode(BlockEdge(Src, I.getBlock(),
603                                       Pred->getLocationContext()), St, &IsNew);
604  Succ->addPredecessor(Pred, *Eng.G);
605
606  if (IsNew) {
607    Eng.WList->Enqueue(Succ);
608    return Succ;
609  }
610
611  return NULL;
612}
613
614
615ExplodedNode*
616GRSwitchNodeBuilder::generateDefaultCaseNode(const GRState* St, bool isSink) {
617
618  // Get the block for the default case.
619  assert (Src->succ_rbegin() != Src->succ_rend());
620  CFGBlock* DefaultBlock = *Src->succ_rbegin();
621
622  bool IsNew;
623
624  ExplodedNode* Succ = Eng.G->getNode(BlockEdge(Src, DefaultBlock,
625                                       Pred->getLocationContext()), St, &IsNew);
626  Succ->addPredecessor(Pred, *Eng.G);
627
628  if (IsNew) {
629    if (isSink)
630      Succ->markAsSink();
631    else
632      Eng.WList->Enqueue(Succ);
633
634    return Succ;
635  }
636
637  return NULL;
638}
639
640GREndPathNodeBuilder::~GREndPathNodeBuilder() {
641  // Auto-generate an EOP node if one has not been generated.
642  if (!HasGeneratedNode) {
643    // If we are in an inlined call, generate CallExit node.
644    if (Pred->getLocationContext()->getParent())
645      GenerateCallExitNode(Pred->State);
646    else
647      generateNode(Pred->State);
648  }
649}
650
651ExplodedNode*
652GREndPathNodeBuilder::generateNode(const GRState* State, const void *tag,
653                                   ExplodedNode* P) {
654  HasGeneratedNode = true;
655  bool IsNew;
656
657  ExplodedNode* Node = Eng.G->getNode(BlockEntrance(&B,
658                               Pred->getLocationContext(), tag), State, &IsNew);
659
660  Node->addPredecessor(P ? P : Pred, *Eng.G);
661
662  if (IsNew) {
663    Eng.G->addEndOfPath(Node);
664    return Node;
665  }
666
667  return NULL;
668}
669
670void GREndPathNodeBuilder::GenerateCallExitNode(const GRState *state) {
671  HasGeneratedNode = true;
672  // Create a CallExit node and enqueue it.
673  const StackFrameContext *LocCtx
674                         = cast<StackFrameContext>(Pred->getLocationContext());
675  const Stmt *CE = LocCtx->getCallSite();
676
677  // Use the the callee location context.
678  CallExit Loc(CE, LocCtx);
679
680  bool isNew;
681  ExplodedNode *Node = Eng.G->getNode(Loc, state, &isNew);
682  Node->addPredecessor(Pred, *Eng.G);
683
684  if (isNew)
685    Eng.WList->Enqueue(Node);
686}
687
688
689void GRCallEnterNodeBuilder::GenerateNode(const GRState *state,
690                                          const LocationContext *LocCtx) {
691  // Get the callee entry block.
692  const CFGBlock *Entry = &(LocCtx->getCFG()->getEntry());
693  assert(Entry->empty());
694  assert(Entry->succ_size() == 1);
695
696  // Get the solitary successor.
697  const CFGBlock *SuccB = *(Entry->succ_begin());
698
699  // Construct an edge representing the starting location in the callee.
700  BlockEdge Loc(Entry, SuccB, LocCtx);
701
702  bool isNew;
703  ExplodedNode *Node = Eng.G->getNode(Loc, state, &isNew);
704  Node->addPredecessor(const_cast<ExplodedNode*>(Pred), *Eng.G);
705
706  if (isNew)
707    Eng.WList->Enqueue(Node);
708}
709
710void GRCallExitNodeBuilder::GenerateNode(const GRState *state) {
711  // Get the callee's location context.
712  const StackFrameContext *LocCtx
713                         = cast<StackFrameContext>(Pred->getLocationContext());
714
715  PostStmt Loc(LocCtx->getCallSite(), LocCtx->getParent());
716  bool isNew;
717  ExplodedNode *Node = Eng.G->getNode(Loc, state, &isNew);
718  Node->addPredecessor(const_cast<ExplodedNode*>(Pred), *Eng.G);
719  if (isNew)
720    Eng.WList->Enqueue(Node, *const_cast<CFGBlock*>(LocCtx->getCallSiteBlock()),
721                       LocCtx->getIndex() + 1);
722}
723