ReachableCode.cpp Source File (original) (raw)

27#include "llvm/ADT/BitVector.h"

28#include "llvm/ADT/SmallVector.h"

29#include

31using namespace clang;

38 const DeclRefExpr *DR = dyn_cast(Ex);

39 if (!DR)

40 return false;

41 return isa(DR->getDecl());

42}

46 return isa(Ex) || isa(Ex) ||

47 isa(Ex) || isa(Ex) ||

48 isa(Ex) ||

50}

56 if (const DoStmt *DS = dyn_cast(Term)) {

59 }

60 }

61 return false;

62}

65 if (const auto *DRE = dyn_cast(S))

66 if (const auto *FDecl = dyn_cast(DRE->getDecl()))

67 return FDecl->getIdentifier() &&

68 FDecl->getBuiltinID() == Builtin::BI__builtin_unreachable;

69 return false;

70}

77 return false;

78 }

80 if (const auto *CE = dyn_cast(CS->getStmt())) {

81 return CE->getCallee()->IgnoreCasts() == S && CE->isBuiltinAssumeFalse(C);

82 }

83 }

84 return false;

85}

92 while (true) {

93 for (const CFGElement &CE : llvm::reverse(*Current)) {

94 if (std::optional CS = CE.getAs<CFGStmt>()) {

95 if (const ReturnStmt *RS = dyn_cast(CS->getStmt())) {

96 if (RS == S)

97 return true;

98 if (const Expr *RE = RS->getRetValue()) {

99 RE = RE->IgnoreParenCasts();

100 if (RE == S)

101 return true;

103

104

106 }

107 }

108 break;

109 }

110 }

111

112

113

114 if (Current->getTerminator().isTemporaryDtorsBranch()) {

115

116

117

118

119 assert(Current->succ_size() == 2);

120 Current = *(Current->succ_begin() + 1);

121 } else if (!Current->getTerminatorStmt() && Current->succ_size() == 1) {

122

123

124 Current = *Current->succ_begin();

125 if (Current->pred_size() > 1) {

126

127

128

129 return false;

130 }

131 } else {

132

133 return false;

134 }

135 }

136 llvm_unreachable("Broke out of infinite loop.");

137}

138

142 do {

144 Loc = SM.getImmediateMacroCallerLoc(Loc);

147}

148

149

152 bool IgnoreYES_NO = false) {

153

154

155

156

160 if (IgnoreYES_NO) {

161

162

163

166 if (MacroName == "YES" || MacroName == "NO")

167 return false;

168 } else if (!PP.getLangOpts().CPlusPlus) {

169

172 if (MacroName == "false" || MacroName == "true")

173 return false;

174 }

175 return true;

176 }

177 return false;

178}

179

181

182

183

184

185

186

187

188

191 SourceRange *SilenceableCondVal = nullptr,

192 bool IncludeIntegers = true,

193 bool WrappedInParens = false) {

194 if (!S)

195 return false;

196

197 if (const auto *Ex = dyn_cast(S))

198 S = Ex->IgnoreImplicit();

199

200 if (const auto *Ex = dyn_cast(S))

201 S = Ex->IgnoreCasts();

202

203

204 if (const ParenExpr *PE = dyn_cast(S))

205 if (!PE->getBeginLoc().isMacroID())

207 IncludeIntegers, true);

208

209 if (const Expr *Ex = dyn_cast(S))

210 S = Ex->IgnoreCasts();

211

212 bool IgnoreYES_NO = false;

213

214 switch (S->getStmtClass()) {

215 case Stmt::CallExprClass: {

217 dyn_cast_or_null(cast(S)->getCalleeDecl());

218 return Callee ? Callee->isConstexpr() : false;

219 }

220 case Stmt::DeclRefExprClass:

222 case Stmt::ObjCBoolLiteralExprClass:

223 IgnoreYES_NO = true;

224 [[fallthrough]];

225 case Stmt::CXXBoolLiteralExprClass:

226 case Stmt::IntegerLiteralClass: {

227 const Expr *E = cast(S);

228 if (IncludeIntegers) {

229 if (SilenceableCondVal && !SilenceableCondVal->getBegin().isValid())

231 return WrappedInParens ||

233 }

234 return false;

235 }

236 case Stmt::MemberExprClass:

238 case Stmt::UnaryExprOrTypeTraitExprClass:

239 return true;

240 case Stmt::BinaryOperatorClass: {

242

243

244

247 IncludeIntegers) ||

249 IncludeIntegers);

250 }

251 case Stmt::UnaryOperatorClass: {

252 const UnaryOperator *UO = cast(S);

254 return false;

255 bool SilenceableCondValNotSet =

256 SilenceableCondVal && SilenceableCondVal->getBegin().isInvalid();

257 bool IsSubExprConfigValue =

259 IncludeIntegers, WrappedInParens);

260

261

262 if (SilenceableCondValNotSet &&

263 SilenceableCondVal->getBegin().isValid() &&

264 *SilenceableCondVal ==

267 return IsSubExprConfigValue;

268 }

269 default:

270 return false;

271 }

272}

273

277 if (const VarDecl *VD = dyn_cast(D)) {

278

279

280

281

282

283

284

285 if (!VD->hasLocalStorage())

286 return true;

287

288

289

290 return VD->getType().isLocalConstQualified();

291 }

292 return false;

293}

294

295

299 if (isa(Term))

300 return true;

301

302 if (isa(Term)) {

304 }

305

306

307

308 if (const auto *IS = dyn_cast(Term);

309 IS != nullptr && IS->isConstexpr())

310 return true;

311 }

312

315}

316

318 llvm::BitVector &Reachable,

320 bool IncludeSometimesUnreachableEdges) {

321 unsigned count = 0;

322

323

325

326

327

328 if (!Reachable[Start->getBlockID()]) {

329 ++count;

330 Reachable[Start->getBlockID()] = true;

331 }

332

333 WL.push_back(Start);

334

335

336 while (!WL.empty()) {

337 const CFGBlock *item = WL.pop_back_val();

338

339

340

341

342

343

344

345 std::optional TreatAllSuccessorsAsReachable;

346 if (!IncludeSometimesUnreachableEdges)

347 TreatAllSuccessorsAsReachable = false;

348

352 if (!B) do {

353 const CFGBlock *UB = I->getPossiblyUnreachableBlock();

354 if (!UB)

355 break;

356

357 if (!TreatAllSuccessorsAsReachable) {

358 assert(PP);

359 TreatAllSuccessorsAsReachable =

361 }

362

363 if (*TreatAllSuccessorsAsReachable) {

364 B = UB;

365 break;

366 }

367 }

368 while (false);

369

370 if (B) {

372 if (!Reachable[blockID]) {

373 Reachable.set(blockID);

374 WL.push_back(B);

375 ++count;

376 }

377 }

378 }

379 }

380 return count;

381}

382

385 llvm::BitVector &Reachable) {

386 return scanFromBlock(Start, Reachable, &PP, true);

387}

388

389

390

391

392

393namespace {

394 class DeadCodeScan {

396 llvm::BitVector &Reachable;

400

402 DeferredLocsTy;

403

404 DeferredLocsTy DeferredLocs;

405

406 public:

408 : Visited(reachable.size()),

409 Reachable(reachable),

410 PP(PP), C(C) {}

411

412 void enqueue(const CFGBlock *block);

413 unsigned scanBackwards(const CFGBlock *Start,

415

417

419

420 void reportDeadCode(const CFGBlock *B,

421 const Stmt *S,

423 };

424}

425

426void DeadCodeScan::enqueue(const CFGBlock *block) {

427 unsigned blockID = block->getBlockID();

428 if (Reachable[blockID] || Visited[blockID])

429 return;

431 WorkList.push_back(block);

432}

433

435 bool isDeadRoot = true;

436

439 if (const CFGBlock *PredBlock = *I) {

440 unsigned blockID = PredBlock->getBlockID();

442 isDeadRoot = false;

443 continue;

444 }

445 if (!Reachable[blockID]) {

446 isDeadRoot = false;

448 WorkList.push_back(PredBlock);

449 continue;

450 }

451 }

452 }

453

454 return isDeadRoot;

455}

456

457

458

460

461 const Stmt *CoroStmt = nullptr;

462

463 bool AfterDeadStmt = false;

465 ++I)

466 if (std::optional CS = I->getAs<CFGStmt>()) {

467 const Stmt *S = CS->getStmt();

468 if (S == DeadStmt)

469 AfterDeadStmt = true;

470 if (AfterDeadStmt &&

471

472 (llvm::isa(S) || llvm::isa(S))) {

473 CoroStmt = S;

474 break;

475 }

476 }

477 if (!CoroStmt)

478 return false;

480 const Stmt *DeadStmt;

481 bool CoroutineSubStmt = false;

482 Checker(const Stmt *S) : DeadStmt(S) {

483

484 ShouldVisitImplicitCode = true;

485 }

486

488 if (S == DeadStmt)

489 CoroutineSubStmt = true;

490 return true;

491 }

492 };

493 Checker checker(DeadStmt);

494 checker.TraverseStmt(const_cast<Stmt *>(CoroStmt));

495 return checker.CoroutineSubStmt;

496}

497

499 if (S->getBeginLoc().isInvalid())

500 return false;

501 if (const BinaryOperator *BO = dyn_cast(S))

502 return BO->getOpcode() != BO_Comma;

503

504

505

507}

508

511 if (std::optional CS = I->getAs<CFGStmt>()) {

512 const Stmt *S = CS->getStmt();

514 return S;

515 }

516

518 if (T.isStmtBranch()) {

519 const Stmt *S = T.getStmt();

521 return S;

522 }

523

524 return nullptr;

525}

526

527static int SrcCmp(const std::pair<const CFGBlock *, const Stmt *> *p1,

528 const std::pair<const CFGBlock *, const Stmt *> *p2) {

529 if (p1->second->getBeginLoc() < p2->second->getBeginLoc())

530 return -1;

531 if (p2->second->getBeginLoc() < p1->second->getBeginLoc())

532 return 1;

533 return 0;

534}

535

536unsigned DeadCodeScan::scanBackwards(const clang::CFGBlock *Start,

538

539 unsigned count = 0;

540 enqueue(Start);

541

542 while (!WorkList.empty()) {

544

545

546

548 continue;

549

550

551 const Stmt *S = findDeadCode(Block);

552

553 if (!S) {

554

557 if (const CFGBlock *predBlock = *I)

558 enqueue(predBlock);

559 }

560 continue;

561 }

562

563

564 if (S->getBeginLoc().isMacroID()) {

566 continue;

567 }

568

569 if (isDeadCodeRoot(Block)) {

570 reportDeadCode(Block, S, CB);

572 }

573 else {

574

575

576

577 DeferredLocs.push_back(std::make_pair(Block, S));

578 }

579 }

580

581

582

583 if (!DeferredLocs.empty()) {

584 llvm::array_pod_sort(DeferredLocs.begin(), DeferredLocs.end(), SrcCmp);

585 for (const auto &I : DeferredLocs) {

588 continue;

589 reportDeadCode(Block, I.second, CB);

591 }

592 }

593

594 return count;

595}

596

601

602 if (const Expr *Ex = dyn_cast(S))

603 S = Ex->IgnoreParenImpCasts();

604

605 switch (S->getStmtClass()) {

606 case Expr::BinaryOperatorClass: {

609 }

610 case Expr::UnaryOperatorClass: {

611 const UnaryOperator *UO = cast(S);

614 }

615 case Expr::CompoundAssignOperatorClass: {

620 }

621 case Expr::BinaryConditionalOperatorClass:

622 case Expr::ConditionalOperatorClass: {

624 cast(S);

626 }

627 case Expr::MemberExprClass: {

628 const MemberExpr *ME = cast(S);

631 }

632 case Expr::ArraySubscriptExprClass: {

637 }

638 case Expr::CStyleCastExprClass: {

642 }

643 case Expr::CXXFunctionalCastExprClass: {

647 }

648 case Stmt::CXXTryStmtClass: {

649 return cast(S)->getHandler(0)->getCatchLoc();

650 }

651 case Expr::ObjCBridgedCastExprClass: {

655 }

656 default: ;

657 }

658 R1 = S->getSourceRange();

659 return S->getBeginLoc();

660}

661

662void DeadCodeScan::reportDeadCode(const CFGBlock *B,

663 const Stmt *S,

665

667

668 if (isa(S)) {

672 return;

673 }

676 }

677

678 const auto *AS = dyn_cast(S);

679 bool HasFallThroughAttr =

680 AS && hasSpecificAttr(AS->getAttrs());

681

683

685

686

687

691

692 if (const ForStmt *FS = dyn_cast(LoopTarget)) {

693 const Expr *Inc = FS->getInc();

694 Loc = Inc->getBeginLoc();

695 R2 = Inc->getSourceRange();

696 }

697

700 HasFallThroughAttr);

701 return;

702 }

703

704

705

706

709 if (const CFGBlock *PredBlock = PI->getPossiblyUnreachableBlock()) {

710 const Stmt *TermCond =

711 PredBlock->getTerminatorCondition( false);

713 }

714 }

715 }

716

719 CB.HandleUnreachable(UK, Loc, SilenceableCondVal, R1, R2, HasFallThroughAttr);

720}

721

722

723

724

725

726namespace clang { namespace reachable_code {

727

728void Callback::anchor() { }

729

731 llvm::BitVector &Reachable) {

732 return scanFromBlock(Start, Reachable, nullptr, false);

733}

734

737

738 CFG *cfg = AC.getCFG();

739 if (!cfg)

740 return;

741

742

743

745 unsigned numReachable =

748 return;

749

750

751

752 if (!AC.getCFGBuildOptions().AddEHEdges) {

756 return;

757 }

758

759

760

761 for (const CFGBlock *block : *cfg) {

762

764 continue;

765

766 DeadCodeScan DS(reachable, PP, AC.getASTContext());

767 numReachable += DS.scanBackwards(block, CB);

768

770 return;

771 }

772}

773

774}}

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

Defines enum values for all the target-independent builtin functions.

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

llvm::DenseSet< const void * > Visited

Defines the clang::Preprocessor interface.

static SourceLocation getTopMostMacro(SourceLocation Loc, SourceManager &SM)

static bool isEnumConstant(const Expr *Ex)

static bool isInCoroutineStmt(const Stmt *DeadStmt, const CFGBlock *Block)

static bool shouldTreatSuccessorsAsReachable(const CFGBlock *B, Preprocessor &PP)

Returns true if we should always explore all successors of a block.

static int SrcCmp(const std::pair< const CFGBlock *, const Stmt * > *p1, const std::pair< const CFGBlock *, const Stmt * > *p2)

static bool isTrivialDoWhile(const CFGBlock *B, const Stmt *S)

static bool isExpandedFromConfigurationMacro(const Stmt *S, Preprocessor &PP, bool IgnoreYES_NO=false)

Returns true if the statement is expanded from a configuration macro.

static bool isValidDeadStmt(const Stmt *S, const clang::CFGBlock *Block)

static unsigned scanFromBlock(const CFGBlock *Start, llvm::BitVector &Reachable, Preprocessor *PP, bool IncludeSometimesUnreachableEdges)

static bool isConfigurationValue(const ValueDecl *D, Preprocessor &PP)

static bool isBuiltinUnreachable(const Stmt *S)

static bool isBuiltinAssumeFalse(const CFGBlock *B, const Stmt *S, ASTContext &C)

static bool isDeadReturn(const CFGBlock *B, const Stmt *S)

static unsigned scanMaybeReachableFromBlock(const CFGBlock *Start, Preprocessor &PP, llvm::BitVector &Reachable)

static SourceLocation GetUnreachableLoc(const Stmt *S, SourceRange &R1, SourceRange &R2)

static bool isTrivialExpression(const Expr *Ex)

Defines the SourceManager interface.

Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...

AbstractConditionalOperator - An abstract base class for ConditionalOperator and BinaryConditionalOpe...

SourceLocation getQuestionLoc() const

AnalysisDeclContext contains the context data for the function, method or block under analysis.

ArraySubscriptExpr - [C99 6.5.2.1] Array Subscripting.

SourceLocation getRBracketLoc() const

Expr * getLHS()

An array access can be written A[4] or 4[A] (both are equivalent).

A builtin binary operation expression such as "x + y" or "x <= y".

static bool isLogicalOp(Opcode Opc)

static bool isComparisonOp(Opcode Opc)

SourceLocation getOperatorLoc() const

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

ElementList::const_iterator const_iterator

CFGTerminator getTerminator() const

succ_iterator succ_begin()

Stmt * getTerminatorStmt()

const Stmt * getLoopTarget() const

AdjacentBlocks::const_iterator const_pred_iterator

pred_iterator pred_begin()

unsigned getBlockID() const

Stmt * getTerminatorCondition(bool StripParens=true)

AdjacentBlocks::const_iterator const_succ_iterator

Represents a top-level expression in a basic block.

std::optional< T > getAs() const

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

Represents CFGBlock terminator statement.

Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt.

try_block_range try_blocks() const

unsigned getNumBlockIDs() const

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

CStyleCastExpr - An explicit cast in C (C99 6.5.4) or a C-style cast in C++ (C++ [expr....

SourceLocation getLParenLoc() const

Represents an explicit C++ type conversion that uses "functional" notation (C++ [expr....

SourceLocation getBeginLoc() const LLVM_READONLY

CompoundAssignOperator - For compound assignments (e.g.

A reference to a declared variable, function, enum, etc.

DoStmt - This represents a 'do/while' stmt.

Recursive AST visitor that supports extension via dynamic dispatch.

virtual bool VisitStmt(Stmt *S)

An instance of this object exists for each enum constant that is defined.

This represents one expression.

Expr * IgnoreParenCasts() LLVM_READONLY

Skip past any parentheses and casts which might surround this expression until reaching a fixed point...

Expr * IgnoreCasts() LLVM_READONLY

Skip past any casts which might surround this expression until reaching a fixed point.

ForStmt - This represents a 'for (init;cond;inc)' stmt.

Represents a function declaration or definition.

MemberExpr - [C99 6.5.2.3] Structure and Union Members.

SourceLocation getMemberLoc() const

getMemberLoc - Return the location of the "member", in X->F, it is the location of 'F'.

An Objective-C "bridged" cast expression, which casts between Objective-C pointers and C pointers,...

SourceLocation getLParenLoc() const

ParenExpr - This represents a parenthesized expression, e.g.

Stmt * getParent(Stmt *) const

Engages in a tight little dance with the lexer to efficiently preprocess tokens.

SourceManager & getSourceManager() const

StringRef getImmediateMacroName(SourceLocation Loc)

Retrieve the name of the immediate macro expansion.

const LangOptions & getLangOpts() const

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

Encodes a location in the source.

This class handles loading and caching of source files into memory.

A trivial tuple used to represent a source range.

Stmt - This represents one statement.

SourceRange getSourceRange() const LLVM_READONLY

SourceLocation tokens are not useful in isolation - they are low level value objects created/interpre...

UnaryOperator - This represents the unary-expression's (except sizeof and alignof),...

SourceLocation getOperatorLoc() const

getOperatorLoc - Return the location of the operator.

Expr * getSubExpr() const

Represent the declaration of a variable (in which case it is an lvalue) a function (in which case it ...

Represents a variable declaration or definition.

virtual void HandleUnreachable(UnreachableKind UK, SourceLocation L, SourceRange ConditionVal, SourceRange R1, SourceRange R2, bool HasFallThroughAttr)=0

bool Inc(InterpState &S, CodePtr OpPC)

Pops a pointer from the stack 2) Load the value from the pointer 3) Writes the value increased by ...

void FindUnreachableCode(AnalysisDeclContext &AC, Preprocessor &PP, Callback &CB)

unsigned ScanReachableFromBlock(const CFGBlock *Start, llvm::BitVector &Reachable)

ScanReachableFromBlock - Mark all blocks reachable from Start.

UnreachableKind

Classifications of unreachable code.

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

const FunctionProtoType * T