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