Home | History | Annotate | Download | only in Core 
      1 //==- CoreEngine.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 #define DEBUG_TYPE "CoreEngine"
     16 
     17 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
     18 #include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h"
     19 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
     20 #include "clang/AST/Expr.h"
     21 #include "clang/AST/StmtCXX.h"
     22 #include "llvm/Support/Casting.h"
     23 #include "llvm/ADT/DenseMap.h"
     24 #include "llvm/ADT/Statistic.h"
     25 
     26 using namespace clang;
     27 using namespace ento;
     28 
     29 STATISTIC(NumReachedMaxSteps,
     30             "The # of times we reached the max number of steps.");
     31 STATISTIC(NumPathsExplored,
     32             "The # of paths explored by the analyzer.");
     33 
     34 //===----------------------------------------------------------------------===//
     35 // Worklist classes for exploration of reachable states.
     36 //===----------------------------------------------------------------------===//
     37 
     38 WorkList::Visitor::~Visitor() {}
     39 
     40 namespace {
     41 class DFS : public WorkList {
     42   SmallVector<WorkListUnit,20> Stack;
     43 public:
     44   virtual bool hasWork() const {
     45     return !Stack.empty();
     46   }
     47 
     48   virtual void enqueue(const WorkListUnit& U) {
     49     Stack.push_back(U);
     50   }
     51 
     52   virtual WorkListUnit dequeue() {
     53     assert (!Stack.empty());
     54     const WorkListUnit& U = Stack.back();
     55     Stack.pop_back(); // This technically "invalidates" U, but we are fine.
     56     return U;
     57   }
     58 
     59   virtual bool visitItemsInWorkList(Visitor &V) {
     60     for (SmallVectorImpl<WorkListUnit>::iterator
     61          I = Stack.begin(), E = Stack.end(); I != E; ++I) {
     62       if (V.visit(*I))
     63         return true;
     64     }
     65     return false;
     66   }
     67 };
     68 
     69 class BFS : public WorkList {
     70   std::deque<WorkListUnit> Queue;
     71 public:
     72   virtual bool hasWork() const {
     73     return !Queue.empty();
     74   }
     75 
     76   virtual void enqueue(const WorkListUnit& U) {
     77     Queue.push_front(U);
     78   }
     79 
     80   virtual WorkListUnit dequeue() {
     81     WorkListUnit U = Queue.front();
     82     Queue.pop_front();
     83     return U;
     84   }
     85 
     86   virtual bool visitItemsInWorkList(Visitor &V) {
     87     for (std::deque<WorkListUnit>::iterator
     88          I = Queue.begin(), E = Queue.end(); I != E; ++I) {
     89       if (V.visit(*I))
     90         return true;
     91     }
     92     return false;
     93   }
     94 };
     95 
     96 } // end anonymous namespace
     97 
     98 // Place the dstor for WorkList here because it contains virtual member
     99 // functions, and we the code for the dstor generated in one compilation unit.
    100 WorkList::~WorkList() {}
    101 
    102 WorkList *WorkList::makeDFS() { return new DFS(); }
    103 WorkList *WorkList::makeBFS() { return new BFS(); }
    104 
    105 namespace {
    106   class BFSBlockDFSContents : public WorkList {
    107     std::deque<WorkListUnit> Queue;
    108     SmallVector<WorkListUnit,20> Stack;
    109   public:
    110     virtual bool hasWork() const {
    111       return !Queue.empty() || !Stack.empty();
    112     }
    113 
    114     virtual void enqueue(const WorkListUnit& U) {
    115       if (isa<BlockEntrance>(U.getNode()->getLocation()))
    116         Queue.push_front(U);
    117       else
    118         Stack.push_back(U);
    119     }
    120 
    121     virtual WorkListUnit dequeue() {
    122       // Process all basic blocks to completion.
    123       if (!Stack.empty()) {
    124         const WorkListUnit& U = Stack.back();
    125         Stack.pop_back(); // This technically "invalidates" U, but we are fine.
    126         return U;
    127       }
    128 
    129       assert(!Queue.empty());
    130       // Don't use const reference.  The subsequent pop_back() might make it
    131       // unsafe.
    132       WorkListUnit U = Queue.front();
    133       Queue.pop_front();
    134       return U;
    135     }
    136     virtual bool visitItemsInWorkList(Visitor &V) {
    137       for (SmallVectorImpl<WorkListUnit>::iterator
    138            I = Stack.begin(), E = Stack.end(); I != E; ++I) {
    139         if (V.visit(*I))
    140           return true;
    141       }
    142       for (std::deque<WorkListUnit>::iterator
    143            I = Queue.begin(), E = Queue.end(); I != E; ++I) {
    144         if (V.visit(*I))
    145           return true;
    146       }
    147       return false;
    148     }
    149 
    150   };
    151 } // end anonymous namespace
    152 
    153 WorkList* WorkList::makeBFSBlockDFSContents() {
    154   return new BFSBlockDFSContents();
    155 }
    156 
    157 //===----------------------------------------------------------------------===//
    158 // Core analysis engine.
    159 //===----------------------------------------------------------------------===//
    160 
    161 /// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps.
    162 bool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps,
    163                                    ProgramStateRef InitState) {
    164 
    165   if (G->num_roots() == 0) { // Initialize the analysis by constructing
    166     // the root if none exists.
    167 
    168     const CFGBlock *Entry = &(L->getCFG()->getEntry());
    169 
    170     assert (Entry->empty() &&
    171             "Entry block must be empty.");
    172 
    173     assert (Entry->succ_size() == 1 &&
    174             "Entry block must have 1 successor.");
    175 
    176     // Mark the entry block as visited.
    177     FunctionSummaries->markVisitedBasicBlock(Entry->getBlockID(),
    178                                              L->getDecl(),
    179                                              L->getCFG()->getNumBlockIDs());
    180 
    181     // Get the solitary successor.
    182     const CFGBlock *Succ = *(Entry->succ_begin());
    183 
    184     // Construct an edge representing the
    185     // starting location in the function.
    186     BlockEdge StartLoc(Entry, Succ, L);
    187 
    188     // Set the current block counter to being empty.
    189     WList->setBlockCounter(BCounterFactory.GetEmptyCounter());
    190 
    191     if (!InitState)
    192       // Generate the root.
    193       generateNode(StartLoc, SubEng.getInitialState(L), 0);
    194     else
    195       generateNode(StartLoc, InitState, 0);
    196   }
    197 
    198   // Check if we have a steps limit
    199   bool UnlimitedSteps = Steps == 0;
    200 
    201   while (WList->hasWork()) {
    202     if (!UnlimitedSteps) {
    203       if (Steps == 0) {
    204         NumReachedMaxSteps++;
    205         break;
    206       }
    207       --Steps;
    208     }
    209 
    210     const WorkListUnit& WU = WList->dequeue();
    211 
    212     // Set the current block counter.
    213     WList->setBlockCounter(WU.getBlockCounter());
    214 
    215     // Retrieve the node.
    216     ExplodedNode *Node = WU.getNode();
    217 
    218     dispatchWorkItem(Node, Node->getLocation(), WU);
    219   }
    220   SubEng.processEndWorklist(hasWorkRemaining());
    221   return WList->hasWork();
    222 }
    223 
    224 void CoreEngine::dispatchWorkItem(ExplodedNode* Pred, ProgramPoint Loc,
    225                                   const WorkListUnit& WU) {
    226   // Dispatch on the location type.
    227   switch (Loc.getKind()) {
    228     case ProgramPoint::BlockEdgeKind:
    229       HandleBlockEdge(cast<BlockEdge>(Loc), Pred);
    230       break;
    231 
    232     case ProgramPoint::BlockEntranceKind:
    233       HandleBlockEntrance(cast<BlockEntrance>(Loc), Pred);
    234       break;
    235 
    236     case ProgramPoint::BlockExitKind:
    237       assert (false && "BlockExit location never occur in forward analysis.");
    238       break;
    239 
    240     case ProgramPoint::CallEnterKind: {
    241       CallEnter CEnter = cast<CallEnter>(Loc);
    242       if (AnalyzedCallees)
    243         if (const CallExpr* CE =
    244             dyn_cast_or_null<CallExpr>(CEnter.getCallExpr()))
    245           if (const Decl *CD = CE->getCalleeDecl())
    246             AnalyzedCallees->insert(CD);
    247       SubEng.processCallEnter(CEnter, Pred);
    248       break;
    249     }
    250 
    251     case ProgramPoint::CallExitKind:
    252       SubEng.processCallExit(Pred);
    253       break;
    254 
    255     case ProgramPoint::EpsilonKind: {
    256       assert(Pred->hasSinglePred() &&
    257              "Assume epsilon has exactly one predecessor by construction");
    258       ExplodedNode *PNode = Pred->getFirstPred();
    259       dispatchWorkItem(Pred, PNode->getLocation(), WU);
    260       break;
    261     }
    262     default:
    263       assert(isa<PostStmt>(Loc) ||
    264              isa<PostInitializer>(Loc));
    265       HandlePostStmt(WU.getBlock(), WU.getIndex(), Pred);
    266       break;
    267   }
    268 }
    269 
    270 bool CoreEngine::ExecuteWorkListWithInitialState(const LocationContext *L,
    271                                                  unsigned Steps,
    272                                                  ProgramStateRef InitState,
    273                                                  ExplodedNodeSet &Dst) {
    274   bool DidNotFinish = ExecuteWorkList(L, Steps, InitState);
    275   for (ExplodedGraph::eop_iterator I = G->eop_begin(),
    276                                    E = G->eop_end(); I != E; ++I) {
    277     Dst.Add(*I);
    278   }
    279   return DidNotFinish;
    280 }
    281 
    282 void CoreEngine::HandleBlockEdge(const BlockEdge &L, ExplodedNode *Pred) {
    283 
    284   const CFGBlock *Blk = L.getDst();
    285   NodeBuilderContext BuilderCtx(*this, Blk, Pred);
    286 
    287   // Mark this block as visited.
    288   const LocationContext *LC = Pred->getLocationContext();
    289   FunctionSummaries->markVisitedBasicBlock(Blk->getBlockID(),
    290                                            LC->getDecl(),
    291                                            LC->getCFG()->getNumBlockIDs());
    292 
    293   // Check if we are entering the EXIT block.
    294   if (Blk == &(L.getLocationContext()->getCFG()->getExit())) {
    295 
    296     assert (L.getLocationContext()->getCFG()->getExit().size() == 0
    297             && "EXIT block cannot contain Stmts.");
    298 
    299     // Process the final state transition.
    300     SubEng.processEndOfFunction(BuilderCtx);
    301 
    302     // This path is done. Don't enqueue any more nodes.
    303     return;
    304   }
    305 
    306   // Call into the SubEngine to process entering the CFGBlock.
    307   ExplodedNodeSet dstNodes;
    308   BlockEntrance BE(Blk, Pred->getLocationContext());
    309   NodeBuilderWithSinks nodeBuilder(Pred, dstNodes, BuilderCtx, BE);
    310   SubEng.processCFGBlockEntrance(L, nodeBuilder);
    311 
    312   // Auto-generate a node.
    313   if (!nodeBuilder.hasGeneratedNodes()) {
    314     nodeBuilder.generateNode(Pred->State, Pred);
    315   }
    316 
    317   // Enqueue nodes onto the worklist.
    318   enqueue(dstNodes);
    319 }
    320 
    321 void CoreEngine::HandleBlockEntrance(const BlockEntrance &L,
    322                                        ExplodedNode *Pred) {
    323 
    324   // Increment the block counter.
    325   const LocationContext *LC = Pred->getLocationContext();
    326   unsigned BlockId = L.getBlock()->getBlockID();
    327   BlockCounter Counter = WList->getBlockCounter();
    328   Counter = BCounterFactory.IncrementCount(Counter, LC->getCurrentStackFrame(),
    329                                            BlockId);
    330   WList->setBlockCounter(Counter);
    331 
    332   // Process the entrance of the block.
    333   if (CFGElement E = L.getFirstElement()) {
    334     NodeBuilderContext Ctx(*this, L.getBlock(), Pred);
    335     SubEng.processCFGElement(E, Pred, 0, &Ctx);
    336   }
    337   else
    338     HandleBlockExit(L.getBlock(), Pred);
    339 }
    340 
    341 void CoreEngine::HandleBlockExit(const CFGBlock * B, ExplodedNode *Pred) {
    342 
    343   if (const Stmt *Term = B->getTerminator()) {
    344     switch (Term->getStmtClass()) {
    345       default:
    346         llvm_unreachable("Analysis for this terminator not implemented.");
    347 
    348       case Stmt::BinaryOperatorClass: // '&&' and '||'
    349         HandleBranch(cast<BinaryOperator>(Term)->getLHS(), Term, B, Pred);
    350         return;
    351 
    352       case Stmt::BinaryConditionalOperatorClass:
    353       case Stmt::ConditionalOperatorClass:
    354         HandleBranch(cast<AbstractConditionalOperator>(Term)->getCond(),
    355                      Term, B, Pred);
    356         return;
    357 
    358         // FIXME: Use constant-folding in CFG construction to simplify this
    359         // case.
    360 
    361       case Stmt::ChooseExprClass:
    362         HandleBranch(cast<ChooseExpr>(Term)->getCond(), Term, B, Pred);
    363         return;
    364 
    365       case Stmt::CXXTryStmtClass: {
    366         // Generate a node for each of the successors.
    367         // Our logic for EH analysis can certainly be improved.
    368         for (CFGBlock::const_succ_iterator it = B->succ_begin(),
    369              et = B->succ_end(); it != et; ++it) {
    370           if (const CFGBlock *succ = *it) {
    371             generateNode(BlockEdge(B, succ, Pred->getLocationContext()),
    372                          Pred->State, Pred);
    373           }
    374         }
    375         return;
    376       }
    377 
    378       case Stmt::DoStmtClass:
    379         HandleBranch(cast<DoStmt>(Term)->getCond(), Term, B, Pred);
    380         return;
    381 
    382       case Stmt::CXXForRangeStmtClass:
    383         HandleBranch(cast<CXXForRangeStmt>(Term)->getCond(), Term, B, Pred);
    384         return;
    385 
    386       case Stmt::ForStmtClass:
    387         HandleBranch(cast<ForStmt>(Term)->getCond(), Term, B, Pred);
    388         return;
    389 
    390       case Stmt::ContinueStmtClass:
    391       case Stmt::BreakStmtClass:
    392       case Stmt::GotoStmtClass:
    393         break;
    394 
    395       case Stmt::IfStmtClass:
    396         HandleBranch(cast<IfStmt>(Term)->getCond(), Term, B, Pred);
    397         return;
    398 
    399       case Stmt::IndirectGotoStmtClass: {
    400         // Only 1 successor: the indirect goto dispatch block.
    401         assert (B->succ_size() == 1);
    402 
    403         IndirectGotoNodeBuilder
    404            builder(Pred, B, cast<IndirectGotoStmt>(Term)->getTarget(),
    405                    *(B->succ_begin()), this);
    406 
    407         SubEng.processIndirectGoto(builder);
    408         return;
    409       }
    410 
    411       case Stmt::ObjCForCollectionStmtClass: {
    412         // In the case of ObjCForCollectionStmt, it appears twice in a CFG:
    413         //
    414         //  (1) inside a basic block, which represents the binding of the
    415         //      'element' variable to a value.
    416         //  (2) in a terminator, which represents the branch.
    417         //
    418         // For (1), subengines will bind a value (i.e., 0 or 1) indicating
    419         // whether or not collection contains any more elements.  We cannot
    420         // just test to see if the element is nil because a container can
    421         // contain nil elements.
    422         HandleBranch(Term, Term, B, Pred);
    423         return;
    424       }
    425 
    426       case Stmt::SwitchStmtClass: {
    427         SwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Term)->getCond(),
    428                                     this);
    429 
    430         SubEng.processSwitch(builder);
    431         return;
    432       }
    433 
    434       case Stmt::WhileStmtClass:
    435         HandleBranch(cast<WhileStmt>(Term)->getCond(), Term, B, Pred);
    436         return;
    437     }
    438   }
    439 
    440   assert (B->succ_size() == 1 &&
    441           "Blocks with no terminator should have at most 1 successor.");
    442 
    443   generateNode(BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()),
    444                Pred->State, Pred);
    445 }
    446 
    447 void CoreEngine::HandleBranch(const Stmt *Cond, const Stmt *Term,
    448                                 const CFGBlock * B, ExplodedNode *Pred) {
    449   assert(B->succ_size() == 2);
    450   NodeBuilderContext Ctx(*this, B, Pred);
    451   ExplodedNodeSet Dst;
    452   SubEng.processBranch(Cond, Term, Ctx, Pred, Dst,
    453                        *(B->succ_begin()), *(B->succ_begin()+1));
    454   // Enqueue the new frontier onto the worklist.
    455   enqueue(Dst);
    456 }
    457 
    458 void CoreEngine::HandlePostStmt(const CFGBlock *B, unsigned StmtIdx,
    459                                   ExplodedNode *Pred) {
    460   assert(B);
    461   assert(!B->empty());
    462 
    463   if (StmtIdx == B->size())
    464     HandleBlockExit(B, Pred);
    465   else {
    466     NodeBuilderContext Ctx(*this, B, Pred);
    467     SubEng.processCFGElement((*B)[StmtIdx], Pred, StmtIdx, &Ctx);
    468   }
    469 }
    470 
    471 /// generateNode - Utility method to generate nodes, hook up successors,
    472 ///  and add nodes to the worklist.
    473 void CoreEngine::generateNode(const ProgramPoint &Loc,
    474                               ProgramStateRef State,
    475                               ExplodedNode *Pred) {
    476 
    477   bool IsNew;
    478   ExplodedNode *Node = G->getNode(Loc, State, false, &IsNew);
    479 
    480   if (Pred)
    481     Node->addPredecessor(Pred, *G);  // Link 'Node' with its predecessor.
    482   else {
    483     assert (IsNew);
    484     G->addRoot(Node);  // 'Node' has no predecessor.  Make it a root.
    485   }
    486 
    487   // Only add 'Node' to the worklist if it was freshly generated.
    488   if (IsNew) WList->enqueue(Node);
    489 }
    490 
    491 void CoreEngine::enqueueStmtNode(ExplodedNode *N,
    492                                  const CFGBlock *Block, unsigned Idx) {
    493   assert(Block);
    494   assert (!N->isSink());
    495 
    496   // Check if this node entered a callee.
    497   if (isa<CallEnter>(N->getLocation())) {
    498     // Still use the index of the CallExpr. It's needed to create the callee
    499     // StackFrameContext.
    500     WList->enqueue(N, Block, Idx);
    501     return;
    502   }
    503 
    504   // Do not create extra nodes. Move to the next CFG element.
    505   if (isa<PostInitializer>(N->getLocation())) {
    506     WList->enqueue(N, Block, Idx+1);
    507     return;
    508   }
    509 
    510   if (isa<EpsilonPoint>(N->getLocation())) {
    511     WList->enqueue(N, Block, Idx);
    512     return;
    513   }
    514 
    515   const CFGStmt *CS = (*Block)[Idx].getAs<CFGStmt>();
    516   const Stmt *St = CS ? CS->getStmt() : 0;
    517   PostStmt Loc(St, N->getLocationContext());
    518 
    519   if (Loc == N->getLocation()) {
    520     // Note: 'N' should be a fresh node because otherwise it shouldn't be
    521     // a member of Deferred.
    522     WList->enqueue(N, Block, Idx+1);
    523     return;
    524   }
    525 
    526   bool IsNew;
    527   ExplodedNode *Succ = G->getNode(Loc, N->getState(), false, &IsNew);
    528   Succ->addPredecessor(N, *G);
    529 
    530   if (IsNew)
    531     WList->enqueue(Succ, Block, Idx+1);
    532 }
    533 
    534 ExplodedNode *CoreEngine::generateCallExitNode(ExplodedNode *N) {
    535   // Create a CallExit node and enqueue it.
    536   const StackFrameContext *LocCtx
    537                          = cast<StackFrameContext>(N->getLocationContext());
    538   const Stmt *CE = LocCtx->getCallSite();
    539 
    540   // Use the the callee location context.
    541   CallExit Loc(CE, LocCtx);
    542 
    543   bool isNew;
    544   ExplodedNode *Node = G->getNode(Loc, N->getState(), false, &isNew);
    545   Node->addPredecessor(N, *G);
    546   return isNew ? Node : 0;
    547 }
    548 
    549 
    550 void CoreEngine::enqueue(ExplodedNodeSet &Set) {
    551   for (ExplodedNodeSet::iterator I = Set.begin(),
    552                                  E = Set.end(); I != E; ++I) {
    553     WList->enqueue(*I);
    554   }
    555 }
    556 
    557 void CoreEngine::enqueue(ExplodedNodeSet &Set,
    558                          const CFGBlock *Block, unsigned Idx) {
    559   for (ExplodedNodeSet::iterator I = Set.begin(),
    560                                  E = Set.end(); I != E; ++I) {
    561     enqueueStmtNode(*I, Block, Idx);
    562   }
    563 }
    564 
    565 void CoreEngine::enqueueEndOfFunction(ExplodedNodeSet &Set) {
    566   for (ExplodedNodeSet::iterator I = Set.begin(), E = Set.end(); I != E; ++I) {
    567     ExplodedNode *N = *I;
    568     // If we are in an inlined call, generate CallExit node.
    569     if (N->getLocationContext()->getParent()) {
    570       N = generateCallExitNode(N);
    571       if (N)
    572         WList->enqueue(N);
    573     } else {
    574       G->addEndOfPath(N);
    575       NumPathsExplored++;
    576     }
    577   }
    578 }
    579 
    580 
    581 void NodeBuilder::anchor() { }
    582 
    583 ExplodedNode* NodeBuilder::generateNodeImpl(const ProgramPoint &Loc,
    584                                             ProgramStateRef State,
    585                                             ExplodedNode *FromN,
    586                                             bool MarkAsSink) {
    587   HasGeneratedNodes = true;
    588   bool IsNew;
    589   ExplodedNode *N = C.Eng.G->getNode(Loc, State, MarkAsSink, &IsNew);
    590   N->addPredecessor(FromN, *C.Eng.G);
    591   Frontier.erase(FromN);
    592 
    593   if (!IsNew)
    594     return 0;
    595 
    596   if (!MarkAsSink)
    597     Frontier.Add(N);
    598 
    599   return N;
    600 }
    601 
    602 void NodeBuilderWithSinks::anchor() { }
    603 
    604 StmtNodeBuilder::~StmtNodeBuilder() {
    605   if (EnclosingBldr)
    606     for (ExplodedNodeSet::iterator I = Frontier.begin(),
    607                                    E = Frontier.end(); I != E; ++I )
    608       EnclosingBldr->addNodes(*I);
    609 }
    610 
    611 void BranchNodeBuilder::anchor() { }
    612 
    613 ExplodedNode *BranchNodeBuilder::generateNode(ProgramStateRef State,
    614                                               bool branch,
    615                                               ExplodedNode *NodePred) {
    616   // If the branch has been marked infeasible we should not generate a node.
    617   if (!isFeasible(branch))
    618     return NULL;
    619 
    620   ProgramPoint Loc = BlockEdge(C.Block, branch ? DstT:DstF,
    621                                NodePred->getLocationContext());
    622   ExplodedNode *Succ = generateNodeImpl(Loc, State, NodePred);
    623   return Succ;
    624 }
    625 
    626 ExplodedNode*
    627 IndirectGotoNodeBuilder::generateNode(const iterator &I,
    628                                       ProgramStateRef St,
    629                                       bool IsSink) {
    630   bool IsNew;
    631   ExplodedNode *Succ = Eng.G->getNode(BlockEdge(Src, I.getBlock(),
    632                                       Pred->getLocationContext()), St,
    633                                       IsSink, &IsNew);
    634   Succ->addPredecessor(Pred, *Eng.G);
    635 
    636   if (!IsNew)
    637     return 0;
    638 
    639   if (!IsSink)
    640     Eng.WList->enqueue(Succ);
    641 
    642   return Succ;
    643 }
    644 
    645 
    646 ExplodedNode*
    647 SwitchNodeBuilder::generateCaseStmtNode(const iterator &I,
    648                                         ProgramStateRef St) {
    649 
    650   bool IsNew;
    651   ExplodedNode *Succ = Eng.G->getNode(BlockEdge(Src, I.getBlock(),
    652                                       Pred->getLocationContext()), St,
    653                                       false, &IsNew);
    654   Succ->addPredecessor(Pred, *Eng.G);
    655   if (!IsNew)
    656     return 0;
    657 
    658   Eng.WList->enqueue(Succ);
    659   return Succ;
    660 }
    661 
    662 
    663 ExplodedNode*
    664 SwitchNodeBuilder::generateDefaultCaseNode(ProgramStateRef St,
    665                                            bool IsSink) {
    666   // Get the block for the default case.
    667   assert(Src->succ_rbegin() != Src->succ_rend());
    668   CFGBlock *DefaultBlock = *Src->succ_rbegin();
    669 
    670   // Sanity check for default blocks that are unreachable and not caught
    671   // by earlier stages.
    672   if (!DefaultBlock)
    673     return NULL;
    674 
    675   bool IsNew;
    676   ExplodedNode *Succ = Eng.G->getNode(BlockEdge(Src, DefaultBlock,
    677                                       Pred->getLocationContext()), St,
    678                                       IsSink, &IsNew);
    679   Succ->addPredecessor(Pred, *Eng.G);
    680 
    681   if (!IsNew)
    682     return 0;
    683 
    684   if (!IsSink)
    685     Eng.WList->enqueue(Succ);
    686 
    687   return Succ;
    688 }
    689