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

source code of clang/lib/StaticAnalyzer/Core/CoreEngine.cpp