CoreEngine.cpp 22 KB

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