CoreEngine.cpp 21 KB

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