CoreEngine.cpp Source File (original) (raw)

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

34#include

35#include

36#include

37#include

39using namespace clang;

40using namespace ento;

42#define DEBUG_TYPE "CoreEngine"

45 "The # of steps executed.");

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

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

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

51 "The # of paths explored by the analyzer.");

59 case ExplorationStrategyKind::DFS:

61 case ExplorationStrategyKind::BFS:

63 case ExplorationStrategyKind::BFSBlockDFSContents:

65 case ExplorationStrategyKind::UnexploredFirst:

67 case ExplorationStrategyKind::UnexploredFirstQueue:

69 case ExplorationStrategyKind::UnexploredFirstLocationQueue:

71 }

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

73}

78 CTUWList(Opts.IsNaiveCTUEnabled ? generateWorkList(Opts) : nullptr),

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

82 WList->setBlockCounter(C);

83 if (CTUWList)

84 CTUWList->setBlockCounter(C);

85}

90 if (G.num_roots() == 0) {

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

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

103

104

106

107

108

109 BlockEdge StartLoc(Entry, Succ, L);

110

111

113

114 if (!InitState)

116

117 bool IsNew;

119 assert(IsNew);

121

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 =

169 const unsigned Pct =

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

179 return WList->hasWork();

180}

181

184

188 break;

189

192 break;

193

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

196 break;

197

200 break;

201

204 break;

205

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

211 break;

212 }

213 default:

221 break;

222 }

223}

224

228

229

234

235

236

241

242

243 return "Virtual base initialization skipped because "

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

245 },

246 true));

247

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

251 if (!Pred)

252 return;

253 }

254

255

258 "EXIT block cannot contain Stmts.");

259

260

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

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

266 } else if (std::optional AutoDtor =

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

269 }

270 }

271

272

274

275

276 return;

277 }

278

279

284

285

286 if (!nodeBuilder.hasGeneratedNodes()) {

287 nodeBuilder.generateNode(Pred->State, Pred);

288 }

289

290

292}

293

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

296

299 BlockCounter Counter = WList->getBlockCounter();

301 BlockId);

302 setBlockCounter(Counter);

303

304

308 } else

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

310}

311

314 switch (Term->getStmtClass()) {

315 default:

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

317

318 case Stmt::CXXBindTemporaryExprClass:

319 HandleCleanupTemporaryBranch(

320 cast(Term), B, Pred);

321 return;

322

323

324 case Stmt::DeclStmtClass:

325 HandleStaticInit(cast(Term), B, Pred);

326 return;

327

328 case Stmt::BinaryOperatorClass:

329 HandleBranch(cast(Term)->getLHS(), Term, B, Pred);

330 return;

331

332 case Stmt::BinaryConditionalOperatorClass:

333 case Stmt::ConditionalOperatorClass:

334 HandleBranch(cast(Term)->getCond(),

335 Term, B, Pred);

336 return;

337

338

339

340

341 case Stmt::ChooseExprClass:

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

343 return;

344

345 case Stmt::CXXTryStmtClass:

346

347

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

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

352 Pred->State, Pred);

353 }

354 }

355 return;

356

357 case Stmt::DoStmtClass:

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

359 return;

360

361 case Stmt::CXXForRangeStmtClass:

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

363 return;

364

365 case Stmt::ForStmtClass:

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

367 return;

368

369 case Stmt::SEHLeaveStmtClass:

370 case Stmt::ContinueStmtClass:

371 case Stmt::BreakStmtClass:

372 case Stmt::GotoStmtClass:

373 break;

374

375 case Stmt::IfStmtClass:

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

377 return;

378

379 case Stmt::IndirectGotoStmtClass: {

380

382

384 builder(Pred, B, cast(Term)->getTarget(),

386

388 return;

389 }

390

391 case Stmt::ObjCForCollectionStmtClass:

392

393

394

395

396

397

398

399

400

401

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

403 return;

404

405 case Stmt::SwitchStmtClass: {

406 SwitchNodeBuilder builder(Pred, B, cast(Term)->getCond(),

407 this);

408

410 return;

411 }

412

413 case Stmt::WhileStmtClass:

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

415 return;

416

417 case Stmt::GCCAsmStmtClass:

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

419

420 return;

421 }

422 }

423

425 HandleVirtualBaseBranch(B, Pred);

426 return;

427 }

428

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

431

433 Pred->State, Pred);

434}

435

439}

440

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

448 getCompletedIterationCount(B, Pred));

449

451}

452

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

461

463}

464

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

472

474}

475

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

478 assert(B);

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

480

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

482 HandleBlockExit(B, Pred);

483 else {

486 }

487}

488

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

492 if (const auto *CallerCtor = dyn_cast_or_null(

494 switch (CallerCtor->getConstructionKind()) {

498 HandleBlockEdge(Loc, Pred);

499 return;

500 }

501 default:

502 break;

503 }

504 }

505

506

507

509 HandleBlockEdge(Loc, Pred);

510}

511

512

513

517 bool IsNew;

519

520 if (Pred)

521 Node->addPredecessor(Pred, G);

522 else {

523 assert(IsNew);

524 G.addRoot(Node);

525 }

526

527

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

529}

530

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

535

536

538

539

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

541 return;

542 }

543

544

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

549 return;

550 }

551

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

554 return;

555 }

556

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

559 return;

560 }

561

562

565

567

568

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

570 return;

571 }

572

573 bool IsNew;

576

577 if (IsNew)

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

579}

580

583

584 const auto *LocCtx = cast(N->getLocationContext());

585

586

588

589 bool isNew;

591 Node->addPredecessor(N, G);

592 return isNew ? Node : nullptr;

593}

594

595std::optional

596CoreEngine::getCompletedIterationCount(const CFGBlock *B,

599 BlockCounter Counter = WList->getBlockCounter();

600 unsigned BlockCount =

602

604 if (isa<ForStmt, WhileStmt, CXXForRangeStmt>(Term)) {

605 assert(BlockCount >= 1 &&

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

607 return BlockCount - 1;

608 }

609 if (isa(Term)) {

610

611

612 return BlockCount;

613 }

614

615

616 return std::nullopt;

617}

618

620 for (const auto I : Set)

621 WList->enqueue(I);

622}

623

626 for (const auto I : Set)

628}

629

631 for (auto *I : Set) {

632

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

634 I = generateCallExitBeginNode(I, RS);

635 if (I)

636 WList->enqueue(I);

637 } else {

638

640 NumPathsExplored++;

641 }

642 }

643}

644

645void NodeBuilder::anchor() {}

646

650 bool MarkAsSink) {

652 bool IsNew;

656

657 if (!IsNew)

658 return nullptr;

659

660 if (!MarkAsSink)

662

663 return N;

664}

665

666void NodeBuilderWithSinks::anchor() {}

667

669 if (EnclosingBldr)

670 for (const auto I : Frontier)

672}

673

674void BranchNodeBuilder::anchor() {}

675

677 bool Branch,

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

680

681 if (!Dst)

682 return nullptr;

683

687 return Succ;

688}

689

693 bool IsSink) {

694 bool IsNew;

697 St, IsSink, &IsNew);

699

700 if (!IsNew)

701 return nullptr;

702

703 if (!IsSink)

704 Eng.WList->enqueue(Succ);

705

706 return Succ;

707}

708

712 bool IsNew;

715 St, false, &IsNew);

717 if (!IsNew)

718 return nullptr;

719

720 Eng.WList->enqueue(Succ);

721 return Succ;

722}

723

726 bool IsSink) {

727

730

731

732

733 if (!DefaultBlock)

734 return nullptr;

735

736 bool IsNew;

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}

This file defines AnalysisDeclContext, a class that manages the analysis context data for context sen...

static std::unique_ptr< WorkList > generateWorkList(AnalyzerOptions &Opts)

STATISTIC(NumSteps, "The # of steps executed.")

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

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

const CFGBlock * getDst() const

std::optional< CFGElement > getFirstElement() const

const CFGBlock * getBlock() const

Represents C++ object destructor implicitly generated for automatic object or temporary bound to cons...

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

succ_reverse_iterator succ_rend()

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 binding an expression to a temporary.

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

DeclStmt - Adaptor class for mixing declarations with statements and expressions.

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

const StackFrameContext * getStackFrame() const

Represents a point when we exit a loop.

Represents a program point just after an implicit call event.

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.

AnalyzerOptions & options

BlockCounter IncrementCount(BlockCounter BC, const StackFrameContext *CallSite, unsigned BlockID)

BlockCounter GetEmptyCounter()

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)

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

Construct a CoreEngine object to analyze the provided CFG.

DataTag::Factory & getDataTags()

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

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

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

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

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

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

void enqueueEndOfFunction(ExplodedNodeSet &Set, const ReturnStmt *RS)

enqueue the nodes corresponding to the end of function onto the end of path / work list.

void enqueue(ExplodedNodeSet &Set)

Enqueue the given set of nodes onto the work list.

ExplodedNode * addRoot(ExplodedNode *V)

addRoot - Add an untyped node to the set of roots.

void reserve(unsigned NodeCount)

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

bool hasSinglePred() const

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.

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 processCFGElement(const CFGElement E, ExplodedNode *Pred, unsigned StmtIdx, NodeBuilderContext *Ctx)

processCFGElement - Called by CoreEngine.

void processStaticInitializer(const DeclStmt *DS, NodeBuilderContext &BuilderCtx, ExplodedNode *Pred, ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF)

Called by CoreEngine.

void processBranch(const Stmt *Condition, NodeBuilderContext &BuilderCtx, ExplodedNode *Pred, ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF, std::optional< unsigned > IterationsCompletedInLoop)

ProcessBranch - Called by CoreEngine.

void processSwitch(SwitchNodeBuilder &builder)

ProcessSwitch - Called by CoreEngine.

void processEndWorklist()

Called by CoreEngine when the analysis worklist has terminated.

void processCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE, NodeBuilderContext &BldCtx, ExplodedNode *Pred, ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF)

Called by CoreEngine.

AnalysisManager & getAnalysisManager()

void processIndirectGoto(IndirectGotoNodeBuilder &builder)

processIndirectGoto - Called by CoreEngine.

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

const CFGBlock * getBlock() const

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

const CoreEngine & getEngine() const

Return the CoreEngine associated with this builder.

const CFGBlock * getBlock() const

Return the CFGBlock associated with this builder.

This node builder keeps track of the generated sink nodes.

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.

void addNodes(const ExplodedNodeSet &S)

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

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

const CFGBlock * getBlock() const

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

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

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()

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