1 //=- ReachableCodePathInsensitive.cpp ---------------------------*- C++ --*-==//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a flow-sensitive, path-insensitive analysis of
11 // determining reachable blocks within a CFG.
13 //===----------------------------------------------------------------------===//
15 #include "clang/Analysis/Analyses/ReachableCode.h"
16 #include "clang/AST/Expr.h"
17 #include "clang/AST/ExprCXX.h"
18 #include "clang/AST/ExprObjC.h"
19 #include "clang/AST/ParentMap.h"
20 #include "clang/AST/StmtCXX.h"
21 #include "clang/Analysis/AnalysisContext.h"
22 #include "clang/Analysis/CFG.h"
23 #include "clang/Basic/SourceManager.h"
24 #include "clang/Lex/Preprocessor.h"
25 #include "llvm/ADT/BitVector.h"
26 #include "llvm/ADT/SmallVector.h"
28 using namespace clang;
30 //===----------------------------------------------------------------------===//
31 // Core Reachability Analysis routines.
32 //===----------------------------------------------------------------------===//
34 static bool isEnumConstant(const Expr *Ex) {
35 const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex);
38 return isa<EnumConstantDecl>(DR->getDecl());
41 static bool isTrivialExpression(const Expr *Ex) {
42 Ex = Ex->IgnoreParenCasts();
43 return isa<IntegerLiteral>(Ex) || isa<StringLiteral>(Ex) ||
44 isa<CXXBoolLiteralExpr>(Ex) || isa<ObjCBoolLiteralExpr>(Ex) ||
45 isa<CharacterLiteral>(Ex) ||
49 static bool isTrivialDoWhile(const CFGBlock *B, const Stmt *S) {
50 // Check if the block ends with a do...while() and see if 'S' is the
52 if (const Stmt *Term = B->getTerminator()) {
53 if (const DoStmt *DS = dyn_cast<DoStmt>(Term)) {
54 const Expr *Cond = DS->getCond()->IgnoreParenCasts();
55 return Cond == S && isTrivialExpression(Cond);
61 static bool isDeadReturn(const CFGBlock *B, const Stmt *S) {
62 // Look to see if the current control flow ends with a 'return', and see if
63 // 'S' is a substatement. The 'return' may not be the last element in the
64 // block, or may be in a subsequent block because of destructors.
65 const CFGBlock *Current = B;
67 for (CFGBlock::const_reverse_iterator I = Current->rbegin(),
70 if (Optional<CFGStmt> CS = I->getAs<CFGStmt>()) {
71 if (const ReturnStmt *RS = dyn_cast<ReturnStmt>(CS->getStmt())) {
74 if (const Expr *RE = RS->getRetValue()) {
75 RE = RE->IgnoreParenCasts();
78 ParentMap PM(const_cast<Expr *>(RE));
79 // If 'S' is in the ParentMap, it is a subexpression of
80 // the return statement.
81 return PM.getParent(S);
87 // Note also that we are restricting the search for the return statement
88 // to stop at control-flow; only part of a return statement may be dead,
89 // without the whole return statement being dead.
90 if (Current->getTerminator().isTemporaryDtorsBranch()) {
91 // Temporary destructors have a predictable control flow, thus we want to
92 // look into the next block for the return statement.
93 // We look into the false branch, as we know the true branch only contains
94 // the call to the destructor.
95 assert(Current->succ_size() == 2);
96 Current = *(Current->succ_begin() + 1);
97 } else if (!Current->getTerminator() && Current->succ_size() == 1) {
98 // If there is only one successor, we're not dealing with outgoing control
99 // flow. Thus, look into the next block.
100 Current = *Current->succ_begin();
101 if (Current->pred_size() > 1) {
102 // If there is more than one predecessor, we're dealing with incoming
103 // control flow - if the return statement is in that block, it might
104 // well be reachable via a different control flow, thus it's not dead.
108 // We hit control flow or a dead end. Stop searching.
112 llvm_unreachable("Broke out of infinite loop.");
115 static SourceLocation getTopMostMacro(SourceLocation Loc, SourceManager &SM) {
116 assert(Loc.isMacroID());
118 while (Loc.isMacroID()) {
120 Loc = SM.getImmediateMacroCallerLoc(Loc);
125 /// Returns true if the statement is expanded from a configuration macro.
126 static bool isExpandedFromConfigurationMacro(const Stmt *S,
128 bool IgnoreYES_NO = false) {
129 // FIXME: This is not very precise. Here we just check to see if the
130 // value comes from a macro, but we can do much better. This is likely
131 // to be over conservative. This logic is factored into a separate function
132 // so that we can refine it later.
133 SourceLocation L = S->getLocStart();
136 // The Objective-C constant 'YES' and 'NO'
137 // are defined as macros. Do not treat them
138 // as configuration values.
139 SourceManager &SM = PP.getSourceManager();
140 SourceLocation TopL = getTopMostMacro(L, SM);
141 StringRef MacroName = PP.getImmediateMacroName(TopL);
142 if (MacroName == "YES" || MacroName == "NO")
150 static bool isConfigurationValue(const ValueDecl *D, Preprocessor &PP);
152 /// Returns true if the statement represents a configuration value.
154 /// A configuration value is something usually determined at compile-time
155 /// to conditionally always execute some branch. Such guards are for
156 /// "sometimes unreachable" code. Such code is usually not interesting
157 /// to report as unreachable, and may mask truly unreachable code within
159 static bool isConfigurationValue(const Stmt *S,
161 SourceRange *SilenceableCondVal = nullptr,
162 bool IncludeIntegers = true,
163 bool WrappedInParens = false) {
167 S = S->IgnoreImplicit();
169 if (const Expr *Ex = dyn_cast<Expr>(S))
170 S = Ex->IgnoreCasts();
172 // Special case looking for the sigil '()' around an integer literal.
173 if (const ParenExpr *PE = dyn_cast<ParenExpr>(S))
174 if (!PE->getLocStart().isMacroID())
175 return isConfigurationValue(PE->getSubExpr(), PP, SilenceableCondVal,
176 IncludeIntegers, true);
178 if (const Expr *Ex = dyn_cast<Expr>(S))
179 S = Ex->IgnoreCasts();
181 bool IgnoreYES_NO = false;
183 switch (S->getStmtClass()) {
184 case Stmt::CallExprClass: {
185 const FunctionDecl *Callee =
186 dyn_cast_or_null<FunctionDecl>(cast<CallExpr>(S)->getCalleeDecl());
187 return Callee ? Callee->isConstexpr() : false;
189 case Stmt::DeclRefExprClass:
190 return isConfigurationValue(cast<DeclRefExpr>(S)->getDecl(), PP);
191 case Stmt::ObjCBoolLiteralExprClass:
194 case Stmt::CXXBoolLiteralExprClass:
195 case Stmt::IntegerLiteralClass: {
196 const Expr *E = cast<Expr>(S);
197 if (IncludeIntegers) {
198 if (SilenceableCondVal && !SilenceableCondVal->getBegin().isValid())
199 *SilenceableCondVal = E->getSourceRange();
200 return WrappedInParens || isExpandedFromConfigurationMacro(E, PP, IgnoreYES_NO);
204 case Stmt::MemberExprClass:
205 return isConfigurationValue(cast<MemberExpr>(S)->getMemberDecl(), PP);
206 case Stmt::UnaryExprOrTypeTraitExprClass:
208 case Stmt::BinaryOperatorClass: {
209 const BinaryOperator *B = cast<BinaryOperator>(S);
210 // Only include raw integers (not enums) as configuration
211 // values if they are used in a logical or comparison operator
213 IncludeIntegers &= (B->isLogicalOp() || B->isComparisonOp());
214 return isConfigurationValue(B->getLHS(), PP, SilenceableCondVal,
216 isConfigurationValue(B->getRHS(), PP, SilenceableCondVal,
219 case Stmt::UnaryOperatorClass: {
220 const UnaryOperator *UO = cast<UnaryOperator>(S);
221 if (SilenceableCondVal)
222 *SilenceableCondVal = UO->getSourceRange();
223 return UO->getOpcode() == UO_LNot &&
224 isConfigurationValue(UO->getSubExpr(), PP, SilenceableCondVal,
225 IncludeIntegers, WrappedInParens);
232 static bool isConfigurationValue(const ValueDecl *D, Preprocessor &PP) {
233 if (const EnumConstantDecl *ED = dyn_cast<EnumConstantDecl>(D))
234 return isConfigurationValue(ED->getInitExpr(), PP);
235 if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
236 // As a heuristic, treat globals as configuration values. Note
237 // that we only will get here if Sema evaluated this
238 // condition to a constant expression, which means the global
239 // had to be declared in a way to be a truly constant value.
240 // We could generalize this to local variables, but it isn't
241 // clear if those truly represent configuration values that
242 // gate unreachable code.
243 if (!VD->hasLocalStorage())
246 // As a heuristic, locals that have been marked 'const' explicitly
247 // can be treated as configuration values as well.
248 return VD->getType().isLocalConstQualified();
253 /// Returns true if we should always explore all successors of a block.
254 static bool shouldTreatSuccessorsAsReachable(const CFGBlock *B,
256 if (const Stmt *Term = B->getTerminator()) {
257 if (isa<SwitchStmt>(Term))
259 // Specially handle '||' and '&&'.
260 if (isa<BinaryOperator>(Term)) {
261 return isConfigurationValue(Term, PP);
265 const Stmt *Cond = B->getTerminatorCondition(/* stripParens */ false);
266 return isConfigurationValue(Cond, PP);
269 static unsigned scanFromBlock(const CFGBlock *Start,
270 llvm::BitVector &Reachable,
272 bool IncludeSometimesUnreachableEdges) {
276 SmallVector<const CFGBlock*, 32> WL;
278 // The entry block may have already been marked reachable
280 if (!Reachable[Start->getBlockID()]) {
282 Reachable[Start->getBlockID()] = true;
287 // Find the reachable blocks from 'Start'.
288 while (!WL.empty()) {
289 const CFGBlock *item = WL.pop_back_val();
291 // There are cases where we want to treat all successors as reachable.
292 // The idea is that some "sometimes unreachable" code is not interesting,
293 // and that we should forge ahead and explore those branches anyway.
294 // This allows us to potentially uncover some "always unreachable" code
295 // within the "sometimes unreachable" code.
296 // Look at the successors and mark then reachable.
297 Optional<bool> TreatAllSuccessorsAsReachable;
298 if (!IncludeSometimesUnreachableEdges)
299 TreatAllSuccessorsAsReachable = false;
301 for (CFGBlock::const_succ_iterator I = item->succ_begin(),
302 E = item->succ_end(); I != E; ++I) {
303 const CFGBlock *B = *I;
305 const CFGBlock *UB = I->getPossiblyUnreachableBlock();
309 if (!TreatAllSuccessorsAsReachable.hasValue()) {
311 TreatAllSuccessorsAsReachable =
312 shouldTreatSuccessorsAsReachable(item, *PP);
315 if (TreatAllSuccessorsAsReachable.getValue()) {
323 unsigned blockID = B->getBlockID();
324 if (!Reachable[blockID]) {
325 Reachable.set(blockID);
335 static unsigned scanMaybeReachableFromBlock(const CFGBlock *Start,
337 llvm::BitVector &Reachable) {
338 return scanFromBlock(Start, Reachable, &PP, true);
341 //===----------------------------------------------------------------------===//
342 // Dead Code Scanner.
343 //===----------------------------------------------------------------------===//
347 llvm::BitVector Visited;
348 llvm::BitVector &Reachable;
349 SmallVector<const CFGBlock *, 10> WorkList;
352 typedef SmallVector<std::pair<const CFGBlock *, const Stmt *>, 12>
355 DeferredLocsTy DeferredLocs;
358 DeadCodeScan(llvm::BitVector &reachable, Preprocessor &PP)
359 : Visited(reachable.size()),
360 Reachable(reachable),
363 void enqueue(const CFGBlock *block);
364 unsigned scanBackwards(const CFGBlock *Start,
365 clang::reachable_code::Callback &CB);
367 bool isDeadCodeRoot(const CFGBlock *Block);
369 const Stmt *findDeadCode(const CFGBlock *Block);
371 void reportDeadCode(const CFGBlock *B,
373 clang::reachable_code::Callback &CB);
377 void DeadCodeScan::enqueue(const CFGBlock *block) {
378 unsigned blockID = block->getBlockID();
379 if (Reachable[blockID] || Visited[blockID])
381 Visited[blockID] = true;
382 WorkList.push_back(block);
385 bool DeadCodeScan::isDeadCodeRoot(const clang::CFGBlock *Block) {
386 bool isDeadRoot = true;
388 for (CFGBlock::const_pred_iterator I = Block->pred_begin(),
389 E = Block->pred_end(); I != E; ++I) {
390 if (const CFGBlock *PredBlock = *I) {
391 unsigned blockID = PredBlock->getBlockID();
392 if (Visited[blockID]) {
396 if (!Reachable[blockID]) {
398 Visited[blockID] = true;
399 WorkList.push_back(PredBlock);
408 static bool isValidDeadStmt(const Stmt *S) {
409 if (S->getLocStart().isInvalid())
411 if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(S))
412 return BO->getOpcode() != BO_Comma;
416 const Stmt *DeadCodeScan::findDeadCode(const clang::CFGBlock *Block) {
417 for (CFGBlock::const_iterator I = Block->begin(), E = Block->end(); I!=E; ++I)
418 if (Optional<CFGStmt> CS = I->getAs<CFGStmt>()) {
419 const Stmt *S = CS->getStmt();
420 if (isValidDeadStmt(S))
424 if (CFGTerminator T = Block->getTerminator()) {
425 if (!T.isTemporaryDtorsBranch()) {
426 const Stmt *S = T.getStmt();
427 if (isValidDeadStmt(S))
435 static int SrcCmp(const std::pair<const CFGBlock *, const Stmt *> *p1,
436 const std::pair<const CFGBlock *, const Stmt *> *p2) {
437 if (p1->second->getLocStart() < p2->second->getLocStart())
439 if (p2->second->getLocStart() < p1->second->getLocStart())
444 unsigned DeadCodeScan::scanBackwards(const clang::CFGBlock *Start,
445 clang::reachable_code::Callback &CB) {
450 while (!WorkList.empty()) {
451 const CFGBlock *Block = WorkList.pop_back_val();
453 // It is possible that this block has been marked reachable after
455 if (Reachable[Block->getBlockID()])
458 // Look for any dead code within the block.
459 const Stmt *S = findDeadCode(Block);
462 // No dead code. Possibly an empty block. Look at dead predecessors.
463 for (CFGBlock::const_pred_iterator I = Block->pred_begin(),
464 E = Block->pred_end(); I != E; ++I) {
465 if (const CFGBlock *predBlock = *I)
471 // Specially handle macro-expanded code.
472 if (S->getLocStart().isMacroID()) {
473 count += scanMaybeReachableFromBlock(Block, PP, Reachable);
477 if (isDeadCodeRoot(Block)) {
478 reportDeadCode(Block, S, CB);
479 count += scanMaybeReachableFromBlock(Block, PP, Reachable);
482 // Record this statement as the possibly best location in a
483 // strongly-connected component of dead code for emitting a
485 DeferredLocs.push_back(std::make_pair(Block, S));
489 // If we didn't find a dead root, then report the dead code with the
490 // earliest location.
491 if (!DeferredLocs.empty()) {
492 llvm::array_pod_sort(DeferredLocs.begin(), DeferredLocs.end(), SrcCmp);
493 for (DeferredLocsTy::iterator I = DeferredLocs.begin(),
494 E = DeferredLocs.end(); I != E; ++I) {
495 const CFGBlock *Block = I->first;
496 if (Reachable[Block->getBlockID()])
498 reportDeadCode(Block, I->second, CB);
499 count += scanMaybeReachableFromBlock(Block, PP, Reachable);
506 static SourceLocation GetUnreachableLoc(const Stmt *S,
509 R1 = R2 = SourceRange();
511 if (const Expr *Ex = dyn_cast<Expr>(S))
512 S = Ex->IgnoreParenImpCasts();
514 switch (S->getStmtClass()) {
515 case Expr::BinaryOperatorClass: {
516 const BinaryOperator *BO = cast<BinaryOperator>(S);
517 return BO->getOperatorLoc();
519 case Expr::UnaryOperatorClass: {
520 const UnaryOperator *UO = cast<UnaryOperator>(S);
521 R1 = UO->getSubExpr()->getSourceRange();
522 return UO->getOperatorLoc();
524 case Expr::CompoundAssignOperatorClass: {
525 const CompoundAssignOperator *CAO = cast<CompoundAssignOperator>(S);
526 R1 = CAO->getLHS()->getSourceRange();
527 R2 = CAO->getRHS()->getSourceRange();
528 return CAO->getOperatorLoc();
530 case Expr::BinaryConditionalOperatorClass:
531 case Expr::ConditionalOperatorClass: {
532 const AbstractConditionalOperator *CO =
533 cast<AbstractConditionalOperator>(S);
534 return CO->getQuestionLoc();
536 case Expr::MemberExprClass: {
537 const MemberExpr *ME = cast<MemberExpr>(S);
538 R1 = ME->getSourceRange();
539 return ME->getMemberLoc();
541 case Expr::ArraySubscriptExprClass: {
542 const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(S);
543 R1 = ASE->getLHS()->getSourceRange();
544 R2 = ASE->getRHS()->getSourceRange();
545 return ASE->getRBracketLoc();
547 case Expr::CStyleCastExprClass: {
548 const CStyleCastExpr *CSC = cast<CStyleCastExpr>(S);
549 R1 = CSC->getSubExpr()->getSourceRange();
550 return CSC->getLParenLoc();
552 case Expr::CXXFunctionalCastExprClass: {
553 const CXXFunctionalCastExpr *CE = cast <CXXFunctionalCastExpr>(S);
554 R1 = CE->getSubExpr()->getSourceRange();
555 return CE->getLocStart();
557 case Stmt::CXXTryStmtClass: {
558 return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc();
560 case Expr::ObjCBridgedCastExprClass: {
561 const ObjCBridgedCastExpr *CSC = cast<ObjCBridgedCastExpr>(S);
562 R1 = CSC->getSubExpr()->getSourceRange();
563 return CSC->getLParenLoc();
567 R1 = S->getSourceRange();
568 return S->getLocStart();
571 void DeadCodeScan::reportDeadCode(const CFGBlock *B,
573 clang::reachable_code::Callback &CB) {
574 // Classify the unreachable code found, or suppress it in some cases.
575 reachable_code::UnreachableKind UK = reachable_code::UK_Other;
577 if (isa<BreakStmt>(S)) {
578 UK = reachable_code::UK_Break;
580 else if (isTrivialDoWhile(B, S)) {
583 else if (isDeadReturn(B, S)) {
584 UK = reachable_code::UK_Return;
587 SourceRange SilenceableCondVal;
589 if (UK == reachable_code::UK_Other) {
590 // Check if the dead code is part of the "loop target" of
591 // a for/for-range loop. This is the block that contains
592 // the increment code.
593 if (const Stmt *LoopTarget = B->getLoopTarget()) {
594 SourceLocation Loc = LoopTarget->getLocStart();
595 SourceRange R1(Loc, Loc), R2;
597 if (const ForStmt *FS = dyn_cast<ForStmt>(LoopTarget)) {
598 const Expr *Inc = FS->getInc();
599 Loc = Inc->getLocStart();
600 R2 = Inc->getSourceRange();
603 CB.HandleUnreachable(reachable_code::UK_Loop_Increment,
604 Loc, SourceRange(), SourceRange(Loc, Loc), R2);
608 // Check if the dead block has a predecessor whose branch has
609 // a configuration value that *could* be modified to
610 // silence the warning.
611 CFGBlock::const_pred_iterator PI = B->pred_begin();
612 if (PI != B->pred_end()) {
613 if (const CFGBlock *PredBlock = PI->getPossiblyUnreachableBlock()) {
614 const Stmt *TermCond =
615 PredBlock->getTerminatorCondition(/* strip parens */ false);
616 isConfigurationValue(TermCond, PP, &SilenceableCondVal);
622 SourceLocation Loc = GetUnreachableLoc(S, R1, R2);
623 CB.HandleUnreachable(UK, Loc, SilenceableCondVal, R1, R2);
626 //===----------------------------------------------------------------------===//
627 // Reachability APIs.
628 //===----------------------------------------------------------------------===//
630 namespace clang { namespace reachable_code {
632 void Callback::anchor() { }
634 unsigned ScanReachableFromBlock(const CFGBlock *Start,
635 llvm::BitVector &Reachable) {
636 return scanFromBlock(Start, Reachable, /* SourceManager* */ nullptr, false);
639 void FindUnreachableCode(AnalysisDeclContext &AC, Preprocessor &PP,
642 CFG *cfg = AC.getCFG();
646 // Scan for reachable blocks from the entrance of the CFG.
647 // If there are no unreachable blocks, we're done.
648 llvm::BitVector reachable(cfg->getNumBlockIDs());
649 unsigned numReachable =
650 scanMaybeReachableFromBlock(&cfg->getEntry(), PP, reachable);
651 if (numReachable == cfg->getNumBlockIDs())
654 // If there aren't explicit EH edges, we should include the 'try' dispatch
656 if (!AC.getCFGBuildOptions().AddEHEdges) {
657 for (CFG::try_block_iterator I = cfg->try_blocks_begin(),
658 E = cfg->try_blocks_end() ; I != E; ++I) {
659 numReachable += scanMaybeReachableFromBlock(*I, PP, reachable);
661 if (numReachable == cfg->getNumBlockIDs())
665 // There are some unreachable blocks. We need to find the root blocks that
666 // contain code that should be considered unreachable.
667 for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) {
668 const CFGBlock *block = *I;
669 // A block may have been marked reachable during this loop.
670 if (reachable[block->getBlockID()])
673 DeadCodeScan DS(reachable, PP);
674 numReachable += DS.scanBackwards(block, CB);
676 if (numReachable == cfg->getNumBlockIDs())
681 }} // end namespace clang::reachable_code