clang 18.0.0git
CoreEngine.cpp
Go to the documentation of this file.
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
15#include "clang/AST/Expr.h"
16#include "clang/AST/ExprCXX.h"
17#include "clang/AST/Stmt.h"
18#include "clang/AST/StmtCXX.h"
20#include "clang/Analysis/CFG.h"
22#include "clang/Basic/LLVM.h"
29#include "llvm/ADT/STLExtras.h"
30#include "llvm/ADT/Statistic.h"
31#include "llvm/Support/Casting.h"
32#include "llvm/Support/ErrorHandling.h"
33#include <algorithm>
34#include <cassert>
35#include <memory>
36#include <optional>
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:
65 case ExplorationStrategyKind::UnexploredFirst:
67 case ExplorationStrategyKind::UnexploredFirstQueue:
69 case ExplorationStrategyKind::UnexploredFirstLocationQueue:
71 }
72 llvm_unreachable("Unknown AnalyzerOptions::ExplorationStrategyKind");
73}
74
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
183 const WorkListUnit& WU) {
184 // Dispatch on the location type.
185 switch (Loc.getKind()) {
187 HandleBlockEdge(Loc.castAs<BlockEdge>(), Pred);
188 break;
189
191 HandleBlockEntrance(Loc.castAs<BlockEntrance>(), Pred);
192 break;
193
195 assert(false && "BlockExit location never occur in forward analysis.");
196 break;
197
199 HandleCallEnter(Loc.castAs<CallEnter>(), Pred);
200 break;
201
203 ExprEng.processCallExit(Pred);
204 break;
205
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>() ||
217 Loc.getAs<CallExitEnd>() ||
218 Loc.getAs<LoopExit>() ||
220 HandlePostStmt(WU.getBlock(), WU.getIndex(), Pred);
221 break;
222 }
223}
224
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.
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 (std::optional<CFGStmt> LastStmt = LastElement.getAs<CFGStmt>()) {
277 RS = dyn_cast<ReturnStmt>(LastStmt->getStmt());
278 } else if (std::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 (std::optional<CFGElement> E = L.getFirstElement()) {
318 NodeBuilderContext Ctx(*this, L.getBlock(), Pred);
319 ExprEng.processCFGElement(*E, Pred, 0, &Ctx);
320 } else
321 HandleBlockExit(L.getBlock(), Pred);
322}
323
324void CoreEngine::HandleBlockExit(const CFGBlock * B, ExplodedNode *Pred) {
325 if (const Stmt *Term = B->getTerminatorStmt()) {
326 switch (Term->getStmtClass()) {
327 default:
328 llvm_unreachable("Analysis for this terminator not implemented.");
329
330 case Stmt::CXXBindTemporaryExprClass:
331 HandleCleanupTemporaryBranch(
332 cast<CXXBindTemporaryExpr>(Term), B, Pred);
333 return;
334
335 // Model static initializers.
336 case Stmt::DeclStmtClass:
337 HandleStaticInit(cast<DeclStmt>(Term), B, Pred);
338 return;
339
340 case Stmt::BinaryOperatorClass: // '&&' and '||'
341 HandleBranch(cast<BinaryOperator>(Term)->getLHS(), Term, B, Pred);
342 return;
343
344 case Stmt::BinaryConditionalOperatorClass:
345 case Stmt::ConditionalOperatorClass:
346 HandleBranch(cast<AbstractConditionalOperator>(Term)->getCond(),
347 Term, B, Pred);
348 return;
349
350 // FIXME: Use constant-folding in CFG construction to simplify this
351 // case.
352
353 case Stmt::ChooseExprClass:
354 HandleBranch(cast<ChooseExpr>(Term)->getCond(), Term, B, Pred);
355 return;
356
357 case Stmt::CXXTryStmtClass:
358 // Generate a node for each of the successors.
359 // Our logic for EH analysis can certainly be improved.
361 et = B->succ_end(); it != et; ++it) {
362 if (const CFGBlock *succ = *it) {
363 generateNode(BlockEdge(B, succ, Pred->getLocationContext()),
364 Pred->State, Pred);
365 }
366 }
367 return;
368
369 case Stmt::DoStmtClass:
370 HandleBranch(cast<DoStmt>(Term)->getCond(), Term, B, Pred);
371 return;
372
373 case Stmt::CXXForRangeStmtClass:
374 HandleBranch(cast<CXXForRangeStmt>(Term)->getCond(), Term, B, Pred);
375 return;
376
377 case Stmt::ForStmtClass:
378 HandleBranch(cast<ForStmt>(Term)->getCond(), Term, B, Pred);
379 return;
380
381 case Stmt::SEHLeaveStmtClass:
382 case Stmt::ContinueStmtClass:
383 case Stmt::BreakStmtClass:
384 case Stmt::GotoStmtClass:
385 break;
386
387 case Stmt::IfStmtClass:
388 HandleBranch(cast<IfStmt>(Term)->getCond(), Term, B, Pred);
389 return;
390
391 case Stmt::IndirectGotoStmtClass: {
392 // Only 1 successor: the indirect goto dispatch block.
393 assert(B->succ_size() == 1);
394
396 builder(Pred, B, cast<IndirectGotoStmt>(Term)->getTarget(),
397 *(B->succ_begin()), this);
398
399 ExprEng.processIndirectGoto(builder);
400 return;
401 }
402
403 case Stmt::ObjCForCollectionStmtClass:
404 // In the case of ObjCForCollectionStmt, it appears twice in a CFG:
405 //
406 // (1) inside a basic block, which represents the binding of the
407 // 'element' variable to a value.
408 // (2) in a terminator, which represents the branch.
409 //
410 // For (1), ExprEngine will bind a value (i.e., 0 or 1) indicating
411 // whether or not collection contains any more elements. We cannot
412 // just test to see if the element is nil because a container can
413 // contain nil elements.
414 HandleBranch(Term, Term, B, Pred);
415 return;
416
417 case Stmt::SwitchStmtClass: {
418 SwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Term)->getCond(),
419 this);
420
421 ExprEng.processSwitch(builder);
422 return;
423 }
424
425 case Stmt::WhileStmtClass:
426 HandleBranch(cast<WhileStmt>(Term)->getCond(), Term, B, Pred);
427 return;
428
429 case Stmt::GCCAsmStmtClass:
430 assert(cast<GCCAsmStmt>(Term)->isAsmGoto() && "Encountered GCCAsmStmt without labels");
431 // TODO: Handle jumping to labels
432 return;
433 }
434 }
435
437 HandleVirtualBaseBranch(B, Pred);
438 return;
439 }
440
441 assert(B->succ_size() == 1 &&
442 "Blocks with no terminator should have at most 1 successor.");
443
444 generateNode(BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()),
445 Pred->State, Pred);
446}
447
448void CoreEngine::HandleCallEnter(const CallEnter &CE, ExplodedNode *Pred) {
449 NodeBuilderContext BuilderCtx(*this, CE.getEntry(), Pred);
450 ExprEng.processCallEnter(BuilderCtx, CE, Pred);
451}
452
453void CoreEngine::HandleBranch(const Stmt *Cond, const Stmt *Term,
454 const CFGBlock * B, ExplodedNode *Pred) {
455 assert(B->succ_size() == 2);
456 NodeBuilderContext Ctx(*this, B, Pred);
457 ExplodedNodeSet Dst;
458 ExprEng.processBranch(Cond, Ctx, Pred, Dst, *(B->succ_begin()),
459 *(B->succ_begin() + 1));
460 // Enqueue the new frontier onto the worklist.
461 enqueue(Dst);
462}
463
464void CoreEngine::HandleCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE,
465 const CFGBlock *B,
466 ExplodedNode *Pred) {
467 assert(B->succ_size() == 2);
468 NodeBuilderContext Ctx(*this, B, Pred);
469 ExplodedNodeSet Dst;
470 ExprEng.processCleanupTemporaryBranch(BTE, Ctx, Pred, Dst, *(B->succ_begin()),
471 *(B->succ_begin() + 1));
472 // Enqueue the new frontier onto the worklist.
473 enqueue(Dst);
474}
475
476void CoreEngine::HandleStaticInit(const DeclStmt *DS, const CFGBlock *B,
477 ExplodedNode *Pred) {
478 assert(B->succ_size() == 2);
479 NodeBuilderContext Ctx(*this, B, Pred);
480 ExplodedNodeSet Dst;
481 ExprEng.processStaticInitializer(DS, Ctx, Pred, Dst,
482 *(B->succ_begin()), *(B->succ_begin()+1));
483 // Enqueue the new frontier onto the worklist.
484 enqueue(Dst);
485}
486
487void CoreEngine::HandlePostStmt(const CFGBlock *B, unsigned StmtIdx,
488 ExplodedNode *Pred) {
489 assert(B);
490 assert(!B->empty());
491
492 if (StmtIdx == B->size())
493 HandleBlockExit(B, Pred);
494 else {
495 NodeBuilderContext Ctx(*this, B, Pred);
496 ExprEng.processCFGElement((*B)[StmtIdx], Pred, StmtIdx, &Ctx);
497 }
498}
499
500void CoreEngine::HandleVirtualBaseBranch(const CFGBlock *B,
501 ExplodedNode *Pred) {
502 const LocationContext *LCtx = Pred->getLocationContext();
503 if (const auto *CallerCtor = dyn_cast_or_null<CXXConstructExpr>(
504 LCtx->getStackFrame()->getCallSite())) {
505 switch (CallerCtor->getConstructionKind()) {
508 BlockEdge Loc(B, *B->succ_begin(), LCtx);
509 HandleBlockEdge(Loc, Pred);
510 return;
511 }
512 default:
513 break;
514 }
515 }
516
517 // We either don't see a parent stack frame because we're in the top frame,
518 // or the parent stack frame doesn't initialize our virtual bases.
519 BlockEdge Loc(B, *(B->succ_begin() + 1), LCtx);
520 HandleBlockEdge(Loc, Pred);
521}
522
523/// generateNode - Utility method to generate nodes, hook up successors,
524/// and add nodes to the worklist.
525void CoreEngine::generateNode(const ProgramPoint &Loc,
526 ProgramStateRef State,
527 ExplodedNode *Pred) {
528 bool IsNew;
529 ExplodedNode *Node = G.getNode(Loc, State, false, &IsNew);
530
531 if (Pred)
532 Node->addPredecessor(Pred, G); // Link 'Node' with its predecessor.
533 else {
534 assert(IsNew);
535 G.addRoot(Node); // 'Node' has no predecessor. Make it a root.
536 }
537
538 // Only add 'Node' to the worklist if it was freshly generated.
539 if (IsNew) WList->enqueue(Node);
540}
541
543 const CFGBlock *Block, unsigned Idx) {
544 assert(Block);
545 assert(!N->isSink());
546
547 // Check if this node entered a callee.
548 if (N->getLocation().getAs<CallEnter>()) {
549 // Still use the index of the CallExpr. It's needed to create the callee
550 // StackFrameContext.
551 WList->enqueue(N, Block, Idx);
552 return;
553 }
554
555 // Do not create extra nodes. Move to the next CFG element.
556 if (N->getLocation().getAs<PostInitializer>() ||
558 N->getLocation().getAs<LoopExit>()) {
559 WList->enqueue(N, Block, Idx+1);
560 return;
561 }
562
563 if (N->getLocation().getAs<EpsilonPoint>()) {
564 WList->enqueue(N, Block, Idx);
565 return;
566 }
567
568 if ((*Block)[Idx].getKind() == CFGElement::NewAllocator) {
569 WList->enqueue(N, Block, Idx+1);
570 return;
571 }
572
573 // At this point, we know we're processing a normal statement.
574 CFGStmt CS = (*Block)[Idx].castAs<CFGStmt>();
576
577 if (Loc == N->getLocation().withTag(nullptr)) {
578 // Note: 'N' should be a fresh node because otherwise it shouldn't be
579 // a member of Deferred.
580 WList->enqueue(N, Block, Idx+1);
581 return;
582 }
583
584 bool IsNew;
585 ExplodedNode *Succ = G.getNode(Loc, N->getState(), false, &IsNew);
586 Succ->addPredecessor(N, G);
587
588 if (IsNew)
589 WList->enqueue(Succ, Block, Idx+1);
590}
591
592ExplodedNode *CoreEngine::generateCallExitBeginNode(ExplodedNode *N,
593 const ReturnStmt *RS) {
594 // Create a CallExitBegin node and enqueue it.
595 const auto *LocCtx = cast<StackFrameContext>(N->getLocationContext());
596
597 // Use the callee location context.
598 CallExitBegin Loc(LocCtx, RS);
599
600 bool isNew;
601 ExplodedNode *Node = G.getNode(Loc, N->getState(), false, &isNew);
602 Node->addPredecessor(N, G);
603 return isNew ? Node : nullptr;
604}
605
607 for (const auto I : Set)
608 WList->enqueue(I);
609}
610
612 const CFGBlock *Block, unsigned Idx) {
613 for (const auto I : Set)
614 enqueueStmtNode(I, Block, Idx);
615}
616
618 for (auto *I : Set) {
619 // If we are in an inlined call, generate CallExitBegin node.
620 if (I->getLocationContext()->getParent()) {
621 I = generateCallExitBeginNode(I, RS);
622 if (I)
623 WList->enqueue(I);
624 } else {
625 // TODO: We should run remove dead bindings here.
626 G.addEndOfPath(I);
627 NumPathsExplored++;
628 }
629 }
630}
631
632void NodeBuilder::anchor() {}
633
635 ProgramStateRef State,
636 ExplodedNode *FromN,
637 bool MarkAsSink) {
638 HasGeneratedNodes = true;
639 bool IsNew;
640 ExplodedNode *N = C.Eng.G.getNode(Loc, State, MarkAsSink, &IsNew);
641 N->addPredecessor(FromN, C.Eng.G);
642 Frontier.erase(FromN);
643
644 if (!IsNew)
645 return nullptr;
646
647 if (!MarkAsSink)
648 Frontier.Add(N);
649
650 return N;
651}
652
653void NodeBuilderWithSinks::anchor() {}
654
656 if (EnclosingBldr)
657 for (const auto I : Frontier)
658 EnclosingBldr->addNodes(I);
659}
660
661void BranchNodeBuilder::anchor() {}
662
664 bool branch,
665 ExplodedNode *NodePred) {
666 // If the branch has been marked infeasible we should not generate a node.
667 if (!isFeasible(branch))
668 return nullptr;
669
670 ProgramPoint Loc = BlockEdge(C.Block, branch ? DstT:DstF,
671 NodePred->getLocationContext());
672 ExplodedNode *Succ = generateNodeImpl(Loc, State, NodePred);
673 return Succ;
674}
675
679 bool IsSink) {
680 bool IsNew;
681 ExplodedNode *Succ =
682 Eng.G.getNode(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()),
683 St, IsSink, &IsNew);
684 Succ->addPredecessor(Pred, Eng.G);
685
686 if (!IsNew)
687 return nullptr;
688
689 if (!IsSink)
690 Eng.WList->enqueue(Succ);
691
692 return Succ;
693}
694
697 ProgramStateRef St) {
698 bool IsNew;
699 ExplodedNode *Succ =
700 Eng.G.getNode(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()),
701 St, false, &IsNew);
702 Succ->addPredecessor(Pred, Eng.G);
703 if (!IsNew)
704 return nullptr;
705
706 Eng.WList->enqueue(Succ);
707 return Succ;
708}
709
712 bool IsSink) {
713 // Get the block for the default case.
714 assert(Src->succ_rbegin() != Src->succ_rend());
715 CFGBlock *DefaultBlock = *Src->succ_rbegin();
716
717 // Basic correctness check for default blocks that are unreachable and not
718 // caught by earlier stages.
719 if (!DefaultBlock)
720 return nullptr;
721
722 bool IsNew;
723 ExplodedNode *Succ =
724 Eng.G.getNode(BlockEdge(Src, DefaultBlock, Pred->getLocationContext()),
725 St, IsSink, &IsNew);
726 Succ->addPredecessor(Pred, Eng.G);
727
728 if (!IsNew)
729 return nullptr;
730
731 if (!IsSink)
732 Eng.WList->enqueue(Succ);
733
734 return Succ;
735}
DynTypedNode Node
StringRef P
This file defines AnalysisDeclContext, a class that manages the analysis context data for context sen...
static std::unique_ptr< WorkList > generateWorkList(AnalyzerOptions &Opts)
Definition: CoreEngine.cpp:57
STATISTIC(NumSteps, "The # of steps executed.")
static Decl::Kind getKind(const Decl *D)
Definition: DeclBase.cpp:1117
Defines the clang::Expr interface and subclasses for C++ expressions.
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified.
Stores options for the analyzer from the command line.
ExplorationStrategyKind getExplorationStrategy() const
const CFGBlock * getSrc() const
Definition: ProgramPoint.h:506
const CFGBlock * getDst() const
Definition: ProgramPoint.h:510
std::optional< CFGElement > getFirstElement() const
Definition: ProgramPoint.h:231
const CFGBlock * getBlock() const
Definition: ProgramPoint.h:227
Represents C++ object destructor implicitly generated for automatic object or temporary bound to cons...
Definition: CFG.h:417
Represents a single basic block in a source-level CFG.
Definition: CFG.h:604
succ_iterator succ_end()
Definition: CFG.h:984
CFGElement back() const
Definition: CFG.h:901
succ_reverse_iterator succ_rend()
Definition: CFG.h:989
unsigned size() const
Definition: CFG.h:945
succ_reverse_iterator succ_rbegin()
Definition: CFG.h:988
bool empty() const
Definition: CFG.h:946
CFGTerminator getTerminator() const
Definition: CFG.h:1076
succ_iterator succ_begin()
Definition: CFG.h:983
Stmt * getTerminatorStmt()
Definition: CFG.h:1078
unsigned getBlockID() const
Definition: CFG.h:1102
AdjacentBlocks::const_iterator const_succ_iterator
Definition: CFG.h:959
unsigned succ_size() const
Definition: CFG.h:1001
Represents a top-level expression in a basic block.
Definition: CFG.h:55
@ NewAllocator
Definition: CFG.h:62
T castAs() const
Convert to the specified CFGElement type, asserting that this CFGElement is of the desired type.
Definition: CFG.h:99
std::optional< T > getAs() const
Convert to the specified CFGElement type, returning std::nullopt if this CFGElement is not of the des...
Definition: CFG.h:109
const Stmt * getStmt() const
Definition: CFG.h:138
bool isVirtualBaseBranch() const
Definition: CFG.h:573
CFGBlock & getExit()
Definition: CFG.h:1319
CFGBlock & getEntry()
Definition: CFG.h:1317
unsigned getNumBlockIDs() const
Returns the total number of BlockIDs allocated (which start at 0).
Definition: CFG.h:1397
Represents binding an expression to a temporary.
Definition: ExprCXX.h:1475
Represents a point when we begin processing an inlined call.
Definition: ProgramPoint.h:628
const CFGBlock * getEntry() const
Returns the entry block in the CFG for the entered function.
Definition: ProgramPoint.h:643
Represents a point when we start the call exit sequence (for inlined call).
Definition: ProgramPoint.h:666
Represents a point when we finish the call exit sequence (for inlined call).
Definition: ProgramPoint.h:686
DeclStmt - Adaptor class for mixing declarations with statements and expressions.
Definition: Stmt.h:1493
This is a meta program point, which should be skipped by all the diagnostic reasoning etc.
Definition: ProgramPoint.h:730
It wraps the AnalysisDeclContext to represent both the call stack with the help of StackFrameContext ...
const Decl * getDecl() const
const StackFrameContext * getStackFrame() const
Represents a point when we exit a loop.
Definition: ProgramPoint.h:711
Represents a program point just after an implicit call event.
Definition: ProgramPoint.h:597
ProgramPoint withTag(const ProgramPointTag *tag) const
Create a new ProgramPoint object that is the same as the original except for using the specified tag ...
Definition: ProgramPoint.h:129
std::optional< T > getAs() const
Convert to the specified ProgramPoint type, returning std::nullopt if this ProgramPoint is not of the...
Definition: ProgramPoint.h:147
const LocationContext * getLocationContext() const
Definition: ProgramPoint.h:175
ReturnStmt - This represents a return, optionally of an expression: return; return 4;.
Definition: Stmt.h:3013
const Stmt * getCallSite() const
Stmt - This represents one statement.
Definition: Stmt.h:84
BlockCounter IncrementCount(BlockCounter BC, const StackFrameContext *CallSite, unsigned BlockID)
An abstract data type used to count the number of times a given block has been visited along a path a...
Definition: BlockCounter.h:29
ExplodedNode * generateNode(ProgramStateRef State, bool branch, ExplodedNode *Pred)
Definition: CoreEngine.cpp:663
bool isFeasible(bool branch)
Definition: CoreEngine.h:476
CoreEngine(ExprEngine &exprengine, FunctionSummariesTy *FS, AnalyzerOptions &Opts)
Construct a CoreEngine object to analyze the provided CFG.
Definition: CoreEngine.cpp:75
DataTag::Factory & getDataTags()
Definition: CoreEngine.h:199
void enqueueStmtNode(ExplodedNode *N, const CFGBlock *Block, unsigned Idx)
Enqueue a single node created as a result of statement processing.
Definition: CoreEngine.cpp:542
void dispatchWorkItem(ExplodedNode *Pred, ProgramPoint Loc, const WorkListUnit &WU)
Dispatch the work list item based on the given location information.
Definition: CoreEngine.cpp:182
bool ExecuteWorkListWithInitialState(const LocationContext *L, unsigned Steps, ProgramStateRef InitState, ExplodedNodeSet &Dst)
Returns true if there is still simulation state on the worklist.
Definition: CoreEngine.cpp:225
bool ExecuteWorkList(const LocationContext *L, unsigned Steps, ProgramStateRef InitState)
ExecuteWorkList - Run the worklist algorithm for a maximum number of steps.
Definition: CoreEngine.cpp:88
void enqueueEndOfFunction(ExplodedNodeSet &Set, const ReturnStmt *RS)
enqueue the nodes corresponding to the end of function onto the end of path / work list.
Definition: CoreEngine.cpp:617
void enqueue(ExplodedNodeSet &Set)
Enqueue the given set of nodes onto the work list.
Definition: CoreEngine.cpp:606
ExplodedNode * addRoot(ExplodedNode *V)
addRoot - Add an untyped node to the set of roots.
void reserve(unsigned NodeCount)
NodeVector::iterator eop_iterator
unsigned num_roots() const
ExplodedNode * getNode(const ProgramPoint &L, ProgramStateRef State, bool IsSink=false, bool *IsNew=nullptr)
Retrieve the node associated with a (Location,State) pair, where the 'Location' is a ProgramPoint in ...
ExplodedNode * addEndOfPath(ExplodedNode *V)
addEndOfPath - Add an untyped node to the set of EOP nodes.
bool erase(ExplodedNode *N)
void Add(ExplodedNode *N)
const ProgramStateRef & getState() const
ProgramPoint getLocation() const
getLocation - Returns the edge associated with the given node.
void addPredecessor(ExplodedNode *V, ExplodedGraph &G)
addPredeccessor - Adds a predecessor to the current node, and in tandem add this node as a successor ...
const LocationContext * getLocationContext() const
ExplodedNode * getFirstPred()
void processEndOfFunction(NodeBuilderContext &BC, ExplodedNode *Pred, const ReturnStmt *RS=nullptr)
Called by CoreEngine.
void processCallEnter(NodeBuilderContext &BC, CallEnter CE, ExplodedNode *Pred)
Generate the entry node of the callee.
void processBeginOfFunction(NodeBuilderContext &BC, ExplodedNode *Pred, ExplodedNodeSet &Dst, const BlockEdge &L)
Called by CoreEngine.
ProgramStateRef getInitialState(const LocationContext *InitLoc)
getInitialState - Return the initial state used for the root vertex in the ExplodedGraph.
Definition: ExprEngine.cpp:244
void processCallExit(ExplodedNode *Pred)
Generate the sequence of nodes that simulate the call exit and the post visit for CallExpr.
void processCFGBlockEntrance(const BlockEdge &L, NodeBuilderWithSinks &nodeBuilder, ExplodedNode *Pred)
Called by CoreEngine when processing the entrance of a CFGBlock.
void processBranch(const Stmt *Condition, NodeBuilderContext &BuilderCtx, ExplodedNode *Pred, ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF)
ProcessBranch - Called by CoreEngine.
void processCFGElement(const CFGElement E, ExplodedNode *Pred, unsigned StmtIdx, NodeBuilderContext *Ctx)
processCFGElement - Called by CoreEngine.
Definition: ExprEngine.cpp:966
void processStaticInitializer(const DeclStmt *DS, NodeBuilderContext &BuilderCtx, ExplodedNode *Pred, ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF)
Called by CoreEngine.
void processSwitch(SwitchNodeBuilder &builder)
ProcessSwitch - Called by CoreEngine.
void processEndWorklist()
Called by CoreEngine when the analysis worklist has terminated.
Definition: ExprEngine.cpp:960
void processCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE, NodeBuilderContext &BldCtx, ExplodedNode *Pred, ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF)
Called by CoreEngine.
AnalysisManager & getAnalysisManager()
Definition: ExprEngine.h:206
void processIndirectGoto(IndirectGotoNodeBuilder &builder)
processIndirectGoto - Called by CoreEngine.
void markVisitedBasicBlock(unsigned ID, const Decl *D, unsigned TotalIDs)
ExplodedNode * generateNode(const iterator &I, ProgramStateRef State, bool isSink=false)
Definition: CoreEngine.cpp:677
This node builder keeps track of the generated sink nodes.
Definition: CoreEngine.h:345
This is the simplest builder which generates nodes in the ExplodedGraph.
Definition: CoreEngine.h:238
const NodeBuilderContext & C
Definition: CoreEngine.h:242
ExplodedNodeSet & Frontier
The frontier set - a set of nodes which need to be propagated after the builder dies.
Definition: CoreEngine.h:252
void addNodes(const ExplodedNodeSet &S)
Definition: CoreEngine.h:339
ExplodedNode * generateNodeImpl(const ProgramPoint &PP, ProgramStateRef State, ExplodedNode *Pred, bool MarkAsSink=false)
Definition: CoreEngine.cpp:634
SValKind getKind() const
Definition: SVals.h:90
std::optional< T > getAs() const
Convert to the specified SVal type, returning std::nullopt if this SVal is not of the desired type.
Definition: SVals.h:86
T castAs() const
Convert to the specified SVal type, asserting that this SVal is of the desired type.
Definition: SVals.h:82
const CFGBlock * getBlock() const
Definition: CoreEngine.h:561
ExplodedNode * generateDefaultCaseNode(ProgramStateRef State, bool isSink=false)
Definition: CoreEngine.cpp:711
ExplodedNode * generateCaseStmtNode(const iterator &I, ProgramStateRef State)
Definition: CoreEngine.cpp:696
ExplodedNode * getNode() const
Returns the node associated with the worklist unit.
Definition: WorkList.h:48
unsigned getIndex() const
Return the index within the CFGBlock for the worklist unit.
Definition: WorkList.h:57
const CFGBlock * getBlock() const
Returns the CFGblock associated with the worklist unit.
Definition: WorkList.h:54
BlockCounter getBlockCounter() const
Returns the block counter map associated with the worklist unit.
Definition: WorkList.h:51
static std::unique_ptr< WorkList > makeUnexploredFirstPriorityLocationQueue()
Definition: WorkList.cpp:299
static std::unique_ptr< WorkList > makeUnexploredFirstPriorityQueue()
Definition: WorkList.cpp:245
static std::unique_ptr< WorkList > makeBFSBlockDFSContents()
Definition: WorkList.cpp:126
static std::unique_ptr< WorkList > makeBFS()
Definition: WorkList.cpp:85
static std::unique_ptr< WorkList > makeDFS()
Definition: WorkList.cpp:81
static std::unique_ptr< WorkList > makeUnexploredFirst()
Definition: WorkList.cpp:188