CoreEngine.cpp 23 KB

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