CoreEngine.cpp Source File (original) (raw)

31#include "llvm/Support/ErrorHandling.h"

32#include "llvm/Support/FormatVariadic.h"

33#include "llvm/Support/TimeProfiler.h"

34#include

35#include

36#include

37#include

38#include

40using namespace clang;

41using namespace ento;

43#define DEBUG_TYPE "CoreEngine"

46 STAT_COUNTER(NumSTUSteps, "The # of STU steps executed.");

47 STAT_COUNTER(NumCTUSteps, "The # of CTU steps executed.");

49 "The # of times we reached the max number of steps.");

50 STAT_COUNTER(NumPathsExplored, "The # of paths explored by the analyzer.");

70 }

71 llvm_unreachable("Unknown AnalyzerOptions::ExplorationStrategyKind");

72}

78 BCounterFactory(G.getAllocator()), FunctionSummaries(FS) {}

81 WList->setBlockCounter(C);

82 if (CTUWList)

83 CTUWList->setBlockCounter(C);

84}

89 if (G.empty()) {

90 assert(!G.getRoot() && "empty graph must not have a root node");

95 assert(Entry->empty() && "Entry block must be empty.");

97 assert(Entry->succ_size() == 1 && "Entry block must have 1 successor.");

100 FunctionSummaries->markVisitedBasicBlock(Entry->getBlockID(),

103

104

106

107

108

109 BlockEdge StartLoc(Entry, Succ, L);

110

111

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.designateAsRoot(Node);

121

124 ExprEng.processBeginOfFunction(BuilderCtx, Node, DstBegin, StartLoc);

125

127 }

128

129

130 bool UnlimitedSteps = MaxSteps == 0;

131

132

133

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

152

153

155

156

158

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 if (llvm::timeTraceProfilerEnabled()) {

184 return llvm::formatv("dispatchWorkItem {0}",

186 .str();

187 }

188 return "";

189}

190

193

194 assert(llvm::timeTraceProfilerEnabled());

195 std::string Detail = "";

197 if (const Stmt *S = SP->getStmt())

198 Detail = S->getStmtClassName();

199 }

200 auto SLoc = Loc.getSourceLocation();

201 if (!SLoc)

202 return llvm::TimeTraceMetadata{std::move(Detail), ""};

207 auto Line = SM.getPresumedLineNumber(*SLoc);

208 auto Fname = SM.getFilename(*SLoc);

209 return llvm::TimeTraceMetadata{std::move(Detail), Fname.str(),

210 static_cast<int>(Line)};

211}

212

217 }};

219

223 break;

224

227 break;

228

230 assert(false && "BlockExit location never occur in forward analysis.");

231 break;

232

235 break;

236

238 ExprEng.processCallExit(Pred);

239 break;

240

243 "Assume epsilon has exactly one predecessor by construction");

246 break;

247 }

248 default:

256 break;

257 }

258}

259

263

264

269

270

271

276

277

278 return "Virtual base initialization skipped because "

279 "it has already been handled by the most derived class";

280 },

281 true));

282

285 Pred = Bldr.generateNode(P, Pred->getState(), Pred);

286 if (!Pred)

287 return;

288 }

289

290

293 "EXIT block cannot contain Stmts.");

294

295

299 if (std::optional LastStmt = LastElement.getAs<CFGStmt>()) {

300 RS = dyn_cast(LastStmt->getStmt());

301 } else if (std::optional AutoDtor =

302 LastElement.getAs()) {

303 RS = dyn_cast(AutoDtor->getTriggerStmt());

304 }

305 }

306

307 ExplodedNodeSet CheckerNodes;

309 ExprEng.runCheckersForBlockEntrance(BuilderCtx, BE, Pred, CheckerNodes);

310

311

312 for (ExplodedNode *P : CheckerNodes) {

313 ExprEng.processEndOfFunction(BuilderCtx, P, RS);

314 }

315

316

317 return;

318 }

319

320

322 ExplodedNodeSet DstNodes;

323 NodeBuilderWithSinks NodeBuilder(Pred, DstNodes, BuilderCtx, BE);

324 ExprEng.processCFGBlockEntrance(L, NodeBuilder, Pred);

325

326

328 NodeBuilder.generateNode(Pred->State, Pred);

329 }

330

331 ExplodedNodeSet CheckerNodes;

332 for (auto *N : DstNodes) {

333 ExprEng.runCheckersForBlockEntrance(BuilderCtx, BE, N, CheckerNodes);

334 }

335

336

338}

339

340void CoreEngine::HandleBlockEntrance(const BlockEntrance &L,

342

345 BlockCounter Counter = WList->getBlockCounter();

346 Counter = BCounterFactory.IncrementCount(Counter, LC->getStackFrame(),

347 BlockId);

348 setBlockCounter(Counter);

349

350

353 ExprEng.processCFGElement(*E, Pred, 0, &Ctx);

354 } else

355 HandleBlockExit(L.getBlock(), Pred);

356}

357

358void CoreEngine::HandleBlockExit(const CFGBlock * B, ExplodedNode *Pred) {

360 switch (Term->getStmtClass()) {

361 default:

362 llvm_unreachable("Analysis for this terminator not implemented.");

363

364 case Stmt::CXXBindTemporaryExprClass:

365 HandleCleanupTemporaryBranch(

367 return;

368

369

370 case Stmt::DeclStmtClass:

372 return;

373

374 case Stmt::BinaryOperatorClass:

376 return;

377

378 case Stmt::BinaryConditionalOperatorClass:

379 case Stmt::ConditionalOperatorClass:

381 Term, B, Pred);

382 return;

383

384

385

386

387 case Stmt::ChooseExprClass:

388 HandleBranch(cast(Term)->getCond(), Term, B, Pred);

389 return;

390

391 case Stmt::CXXTryStmtClass:

392

393

395 et = B->succ_end(); it != et; ++it) {

396 if (const CFGBlock *succ = *it) {

398 Pred->State, Pred);

399 }

400 }

401 return;

402

403 case Stmt::DoStmtClass:

404 HandleBranch(cast(Term)->getCond(), Term, B, Pred);

405 return;

406

407 case Stmt::CXXForRangeStmtClass:

409 return;

410

411 case Stmt::ForStmtClass:

412 HandleBranch(cast(Term)->getCond(), Term, B, Pred);

413 return;

414

415 case Stmt::SEHLeaveStmtClass:

416 case Stmt::ContinueStmtClass:

417 case Stmt::BreakStmtClass:

418 case Stmt::GotoStmtClass:

419 break;

420

421 case Stmt::IfStmtClass:

422 HandleBranch(cast(Term)->getCond(), Term, B, Pred);

423 return;

424

425 case Stmt::IndirectGotoStmtClass: {

426

428

432

433 ExprEng.processIndirectGoto(builder);

434 return;

435 }

436

437 case Stmt::ObjCForCollectionStmtClass:

438

439

440

441

442

443

444

445

446

447

448 HandleBranch(Term, Term, B, Pred);

449 return;

450

451 case Stmt::SwitchStmtClass: {

453 this);

454

455 ExprEng.processSwitch(builder);

456 return;

457 }

458

459 case Stmt::WhileStmtClass:

460 HandleBranch(cast(Term)->getCond(), Term, B, Pred);

461 return;

462

463 case Stmt::GCCAsmStmtClass:

464 assert(cast(Term)->isAsmGoto() && "Encountered GCCAsmStmt without labels");

465

466 return;

467 }

468 }

469

471 HandleVirtualBaseBranch(B, Pred);

472 return;

473 }

474

476 "Blocks with no terminator should have at most 1 successor.");

477

479 Pred->State, Pred);

480}

481

482void CoreEngine::HandleCallEnter(const CallEnter &CE, ExplodedNode *Pred) {

484 ExprEng.processCallEnter(BuilderCtx, CE, Pred);

485}

486

487void CoreEngine::HandleBranch(const Stmt *Cond, const Stmt *Term,

491 ExplodedNodeSet Dst;

492 ExprEng.processBranch(Cond, Ctx, Pred, Dst, *(B->succ_begin()),

494 getCompletedIterationCount(B, Pred));

495

497}

498

499void CoreEngine::HandleCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE,

500 const CFGBlock *B,

504 ExplodedNodeSet Dst;

505 ExprEng.processCleanupTemporaryBranch(BTE, Ctx, Pred, Dst, *(B->succ_begin()),

507

509}

510

511void CoreEngine::HandleStaticInit(const DeclStmt *DS, const CFGBlock *B,

515 ExplodedNodeSet Dst;

516 ExprEng.processStaticInitializer(DS, Ctx, Pred, Dst,

518

520}

521

522void CoreEngine::HandlePostStmt(const CFGBlock *B, unsigned StmtIdx,

524 assert(B);

525 assert(!B->empty());

526

527 if (StmtIdx == B->size())

528 HandleBlockExit(B, Pred);

529 else {

531 ExprEng.processCFGElement((*B)[StmtIdx], Pred, StmtIdx, &Ctx);

532 }

533}

534

535void CoreEngine::HandleVirtualBaseBranch(const CFGBlock *B,

538 if (const auto *CallerCtor = dyn_cast_or_null(

540 switch (CallerCtor->getConstructionKind()) {

543 BlockEdge Loc(B, *B->succ_begin(), LCtx);

544 HandleBlockEdge(Loc, Pred);

545 return;

546 }

547 default:

548 break;

549 }

550 }

551

552

553

554 BlockEdge Loc(B, *(B->succ_begin() + 1), LCtx);

555 HandleBlockEdge(Loc, Pred);

556}

557

558

559

560void CoreEngine::generateNode(const ProgramPoint &Loc,

563 assert(Pred);

564 bool IsNew;

565 ExplodedNode *Node = G.getNode(Loc, State, false, &IsNew);

566

567 Node->addPredecessor(Pred, G);

568

569

570 if (IsNew) WList->enqueue(Node);

571}

572

576 assert(!N->isSink());

577

578

580

581

582 WList->enqueue(N, Block, Idx);

583 return;

584 }

585

586

590 WList->enqueue(N, Block, Idx+1);

591 return;

592 }

593

595 WList->enqueue(N, Block, Idx);

596 return;

597 }

598

600 WList->enqueue(N, Block, Idx+1);

601 return;

602 }

603

604

607

609

610

611 WList->enqueue(N, Block, Idx+1);

612 return;

613 }

614

615 bool IsNew;

618

619 if (IsNew)

620 WList->enqueue(Succ, Block, Idx+1);

621}

622

625

627

628

630

631 bool isNew;

634 return isNew ? Node : nullptr;

635}

636

637std::optional

638CoreEngine::getCompletedIterationCount(const CFGBlock *B,

641 BlockCounter Counter = WList->getBlockCounter();

642 unsigned BlockCount =

644

647 assert(BlockCount >= 1 &&

648 "Block count of currently analyzed block must be >= 1");

649 return BlockCount - 1;

650 }

652

653

654 return BlockCount;

655 }

656

657

658 return std::nullopt;

659}

660

662 for (const auto I : Set)

663 WList->enqueue(I);

664}

665

668 for (const auto I : Set)

670}

671

673 for (auto *I : Set) {

674

675 if (I->getLocationContext()->getParent()) {

676 I = generateCallExitBeginNode(I, RS);

677 if (I)

678 WList->enqueue(I);

679 } else {

680

681 G.addEndOfPath(I);

682 NumPathsExplored++;

683 }

684 }

685}

686

687void NodeBuilder::anchor() {}

688

692 bool MarkAsSink) {

694 bool IsNew;

695 ExplodedNode *N = C.getEngine().G.getNode(Loc, State, MarkAsSink, &IsNew);

698

699 if (!IsNew)

700 return nullptr;

701

702 if (!MarkAsSink)

704

705 return N;

706}

707

708void NodeBuilderWithSinks::anchor() {}

709

711 if (EnclosingBldr)

712 for (const auto I : Frontier)

713 EnclosingBldr->addNodes(I);

714}

715

716void BranchNodeBuilder::anchor() {}

717

719 bool Branch,

721 const CFGBlock *Dst = Branch ? DstT : DstF;

722

723 if (!Dst)

724 return nullptr;

725

729 return Succ;

730}

731

735 bool IsSink) {

736 bool IsNew;

738 Eng.G.getNode(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()),

739 St, IsSink, &IsNew);

741

742 if (!IsNew)

743 return nullptr;

744

745 if (!IsSink)

746 Eng.WList->enqueue(Succ);

747

748 return Succ;

749}

750

754 bool IsNew;

756 Eng.G.getNode(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()),

757 St, false, &IsNew);

759 if (!IsNew)

760 return nullptr;

761

762 Eng.WList->enqueue(Succ);

763 return Succ;

764}

765

768 bool IsSink) {

769

770 assert(Src->succ_rbegin() != Src->succ_rend());

772

773

774

775 if (!DefaultBlock)

776 return nullptr;

777

778 bool IsNew;

780 Eng.G.getNode(BlockEdge(Src, DefaultBlock, Pred->getLocationContext()),

781 St, IsSink, &IsNew);

783

784 if (!IsNew)

785 return nullptr;

786

787 if (!IsSink)

788 Eng.WList->enqueue(Succ);

789

790 return Succ;

791}

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:56

ALWAYS_ENABLED_STATISTIC(NumReachedMaxSteps, "The # of times we reached the max number of steps.")

static std::string timeTraceScopeName(const ProgramPoint &Loc)

Definition CoreEngine.cpp:182

static llvm::TimeTraceMetadata timeTraceMetadata(const ExplodedNode *Pred, const ProgramPoint &Loc)

Definition CoreEngine.cpp:191

static Decl::Kind getKind(const Decl *D)

#define STAT_COUNTER(VARNAME, DESC)

Defines the clang::Expr interface and subclasses for C++ expressions.

Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified.

SourceManager & getSourceManager()

ASTContext & getASTContext() const

Stores options for the analyzer from the command line.

ExplorationStrategyKind getExplorationStrategy() const

const CFGBlock * getSrc() const

const CFGBlock * getDst() const

std::optional< CFGElement > getFirstElement() const

const CFGBlock * getBlock() const

Represents a single basic block in a source-level CFG.

succ_reverse_iterator succ_rbegin()

CFGTerminator getTerminator() const

succ_iterator succ_begin()

Stmt * getTerminatorStmt()

unsigned getBlockID() const

AdjacentBlocks::const_iterator const_succ_iterator

unsigned succ_size() const

Represents a top-level expression in a basic block.

T castAs() const

Convert to the specified CFGElement type, asserting that this CFGElement is of the desired type.

std::optional< T > getAs() const

Convert to the specified CFGElement type, returning std::nullopt if this CFGElement is not of the des...

const Stmt * getStmt() const

bool isVirtualBaseBranch() const

unsigned getNumBlockIDs() const

Returns the total number of BlockIDs allocated (which start at 0).

Represents a point when we begin processing an inlined call.

const CFGBlock * getEntry() const

Returns the entry block in the CFG for the entered function.

Represents a point when we start the call exit sequence (for inlined call).

Represents a point when we finish the call exit sequence (for inlined call).

This is a meta program point, which should be skipped by all the diagnostic reasoning etc.

It wraps the AnalysisDeclContext to represent both the call stack with the help of StackFrameContext ...

const Decl * getDecl() const

LLVM_ATTRIBUTE_RETURNS_NONNULL AnalysisDeclContext * getAnalysisDeclContext() const

const StackFrameContext * getStackFrame() const

Represents a point when we exit a loop.

Represents a program point just after an implicit call event.

static StringRef getProgramPointKindName(Kind K)

ProgramPoint withTag(const ProgramPointTag *tag) const

Create a new ProgramPoint object that is the same as the original except for using the specified tag ...

std::optional< T > getAs() const

Convert to the specified ProgramPoint type, returning std::nullopt if this ProgramPoint is not of the...

const LocationContext * getLocationContext() const

ReturnStmt - This represents a return, optionally of an expression: return; return 4;.

const Stmt * getCallSite() const

Stmt - This represents one statement.

An abstract data type used to count the number of times a given block has been visited along a path a...

unsigned getNumVisited(const StackFrameContext *CallSite, unsigned BlockID) const

ExplodedNode * generateNode(ProgramStateRef State, bool branch, ExplodedNode *Pred)

Definition CoreEngine.cpp:718

friend class SwitchNodeBuilder

CoreEngine(ExprEngine &exprengine, FunctionSummariesTy *FS, AnalyzerOptions &Opts)

Construct a CoreEngine object to analyze the provided CFG.

Definition CoreEngine.cpp:74

DataTag::Factory & getDataTags()

void enqueueStmtNode(ExplodedNode *N, const CFGBlock *Block, unsigned Idx)

Enqueue a single node created as a result of statement processing.

Definition CoreEngine.cpp:573

void dispatchWorkItem(ExplodedNode *Pred, ProgramPoint Loc, const WorkListUnit &WU)

Dispatch the work list item based on the given location information.

Definition CoreEngine.cpp:213

friend class IndirectGotoNodeBuilder

friend class NodeBuilderContext

bool ExecuteWorkList(const LocationContext *L, unsigned Steps, ProgramStateRef InitState)

ExecuteWorkList - Run the worklist algorithm for a maximum number of steps.

Definition CoreEngine.cpp:87

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:672

void enqueue(ExplodedNodeSet &Set)

Enqueue the given set of nodes onto the work list.

Definition CoreEngine.cpp:661

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...

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 ...

bool hasSinglePred() const

const LocationContext * getLocationContext() const

ExplodedNode * getFirstPred()

void markVisitedBasicBlock(unsigned ID, const Decl *D, unsigned TotalIDs)

const CFGBlock * getBlock() const

ExplodedNode * generateNode(const iterator &I, ProgramStateRef State, bool isSink=false)

Definition CoreEngine.cpp:733

This is the simplest builder which generates nodes in the ExplodedGraph.

const NodeBuilderContext & C

ExplodedNodeSet & Frontier

The frontier set - a set of nodes which need to be propagated after the builder dies.

ExplodedNode * generateNodeImpl(const ProgramPoint &PP, ProgramStateRef State, ExplodedNode *Pred, bool MarkAsSink=false)

Definition CoreEngine.cpp:689

While alive, includes the current analysis stack in a crash trace.

std::optional< T > getAs() const

Convert to the specified SVal type, returning std::nullopt if this SVal is not of the desired type.

T castAs() const

Convert to the specified SVal type, asserting that this SVal is of the desired type.

~StmtNodeBuilder() override

Definition CoreEngine.cpp:710

const CFGBlock * getBlock() const

ExplodedNode * generateDefaultCaseNode(ProgramStateRef State, bool isSink=false)

Definition CoreEngine.cpp:767

ExplodedNode * generateCaseStmtNode(const iterator &I, ProgramStateRef State)

Definition CoreEngine.cpp:752

ExplodedNode * getNode() const

Returns the node associated with the worklist unit.

unsigned getIndex() const

Return the index within the CFGBlock for the worklist unit.

const CFGBlock * getBlock() const

Returns the CFGblock associated with the worklist unit.

BlockCounter getBlockCounter() const

Returns the block counter map associated with the worklist unit.

static std::unique_ptr< WorkList > makeUnexploredFirstPriorityLocationQueue()

static std::unique_ptr< WorkList > makeUnexploredFirstPriorityQueue()

static std::unique_ptr< WorkList > makeBFSBlockDFSContents()

static std::unique_ptr< WorkList > makeBFS()

static std::unique_ptr< WorkList > makeDFS()

static std::unique_ptr< WorkList > makeUnexploredFirst()

IntrusiveRefCntPtr< const ProgramState > ProgramStateRef

The JSON file list parser is used to communicate input to InstallAPI.

bool isa(CodeGen::Address addr)

nullptr

This class represents a compute construct, representing a 'Kind' of ‘parallel’, 'serial',...

U cast(CodeGen::Address addr)

@ UnexploredFirstLocationQueue