Updated to Clang 3.5a.
Change-Id: I8127eb568f674c2e72635b639a3295381fe8af82
diff --git a/lib/Analysis/ReachableCode.cpp b/lib/Analysis/ReachableCode.cpp
index a2d19c0..3cc8ae4 100644
--- a/lib/Analysis/ReachableCode.cpp
+++ b/lib/Analysis/ReachableCode.cpp
@@ -13,10 +13,12 @@
//===----------------------------------------------------------------------===//
#include "clang/Analysis/Analyses/ReachableCode.h"
+#include "clang/Lex/Preprocessor.h"
#include "clang/AST/Expr.h"
#include "clang/AST/ExprCXX.h"
#include "clang/AST/ExprObjC.h"
#include "clang/AST/StmtCXX.h"
+#include "clang/AST/ParentMap.h"
#include "clang/Analysis/AnalysisContext.h"
#include "clang/Analysis/CFG.h"
#include "clang/Basic/SourceManager.h"
@@ -25,36 +27,324 @@
using namespace clang;
-namespace {
-class DeadCodeScan {
- llvm::BitVector Visited;
- llvm::BitVector &Reachable;
- SmallVector<const CFGBlock *, 10> WorkList;
-
- typedef SmallVector<std::pair<const CFGBlock *, const Stmt *>, 12>
- DeferredLocsTy;
-
- DeferredLocsTy DeferredLocs;
-
-public:
- DeadCodeScan(llvm::BitVector &reachable)
- : Visited(reachable.size()),
- Reachable(reachable) {}
-
- void enqueue(const CFGBlock *block);
- unsigned scanBackwards(const CFGBlock *Start,
- clang::reachable_code::Callback &CB);
-
- bool isDeadCodeRoot(const CFGBlock *Block);
-
- const Stmt *findDeadCode(const CFGBlock *Block);
-
- void reportDeadCode(const Stmt *S,
- clang::reachable_code::Callback &CB);
-};
+//===----------------------------------------------------------------------===//
+// Core Reachability Analysis routines.
+//===----------------------------------------------------------------------===//
+
+static bool isEnumConstant(const Expr *Ex) {
+ const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex);
+ if (!DR)
+ return false;
+ return isa<EnumConstantDecl>(DR->getDecl());
}
-void DeadCodeScan::enqueue(const CFGBlock *block) {
+static bool isTrivialExpression(const Expr *Ex) {
+ Ex = Ex->IgnoreParenCasts();
+ return isa<IntegerLiteral>(Ex) || isa<StringLiteral>(Ex) ||
+ isa<CXXBoolLiteralExpr>(Ex) || isa<ObjCBoolLiteralExpr>(Ex) ||
+ isa<CharacterLiteral>(Ex) ||
+ isEnumConstant(Ex);
+}
+
+static bool isTrivialDoWhile(const CFGBlock *B, const Stmt *S) {
+ // Check if the block ends with a do...while() and see if 'S' is the
+ // condition.
+ if (const Stmt *Term = B->getTerminator()) {
+ if (const DoStmt *DS = dyn_cast<DoStmt>(Term)) {
+ const Expr *Cond = DS->getCond()->IgnoreParenCasts();
+ return Cond == S && isTrivialExpression(Cond);
+ }
+ }
+ return false;
+}
+
+static bool isDeadReturn(const CFGBlock *B, const Stmt *S) {
+ // Look to see if the block ends with a 'return', and see if 'S'
+ // is a substatement. The 'return' may not be the last element in
+ // the block because of destructors.
+ for (CFGBlock::const_reverse_iterator I = B->rbegin(), E = B->rend();
+ I != E; ++I) {
+ if (Optional<CFGStmt> CS = I->getAs<CFGStmt>()) {
+ if (const ReturnStmt *RS = dyn_cast<ReturnStmt>(CS->getStmt())) {
+ if (RS == S)
+ return true;
+ if (const Expr *RE = RS->getRetValue()) {
+ RE = RE->IgnoreParenCasts();
+ if (RE == S)
+ return true;
+ ParentMap PM(const_cast<Expr*>(RE));
+ // If 'S' is in the ParentMap, it is a subexpression of
+ // the return statement. Note also that we are restricting
+ // to looking at return statements in the same CFGBlock,
+ // so this will intentionally not catch cases where the
+ // return statement contains nested control-flow.
+ return PM.getParent(S);
+ }
+ }
+ break;
+ }
+ }
+ return false;
+}
+
+static SourceLocation getTopMostMacro(SourceLocation Loc, SourceManager &SM) {
+ assert(Loc.isMacroID());
+ SourceLocation Last;
+ while (Loc.isMacroID()) {
+ Last = Loc;
+ Loc = SM.getImmediateMacroCallerLoc(Loc);
+ }
+ return Last;
+}
+
+/// Returns true if the statement is expanded from a configuration macro.
+static bool isExpandedFromConfigurationMacro(const Stmt *S,
+ Preprocessor &PP,
+ bool IgnoreYES_NO = false) {
+ // FIXME: This is not very precise. Here we just check to see if the
+ // value comes from a macro, but we can do much better. This is likely
+ // to be over conservative. This logic is factored into a separate function
+ // so that we can refine it later.
+ SourceLocation L = S->getLocStart();
+ if (L.isMacroID()) {
+ if (IgnoreYES_NO) {
+ // The Objective-C constant 'YES' and 'NO'
+ // are defined as macros. Do not treat them
+ // as configuration values.
+ SourceManager &SM = PP.getSourceManager();
+ SourceLocation TopL = getTopMostMacro(L, SM);
+ StringRef MacroName = PP.getImmediateMacroName(TopL);
+ if (MacroName == "YES" || MacroName == "NO")
+ return false;
+ }
+ return true;
+ }
+ return false;
+}
+
+static bool isConfigurationValue(const ValueDecl *D, Preprocessor &PP);
+
+/// Returns true if the statement represents a configuration value.
+///
+/// A configuration value is something usually determined at compile-time
+/// to conditionally always execute some branch. Such guards are for
+/// "sometimes unreachable" code. Such code is usually not interesting
+/// to report as unreachable, and may mask truly unreachable code within
+/// those blocks.
+static bool isConfigurationValue(const Stmt *S,
+ Preprocessor &PP,
+ SourceRange *SilenceableCondVal = nullptr,
+ bool IncludeIntegers = true,
+ bool WrappedInParens = false) {
+ if (!S)
+ return false;
+
+ // Special case looking for the sigil '()' around an integer literal.
+ if (const ParenExpr *PE = dyn_cast<ParenExpr>(S))
+ if (!PE->getLocStart().isMacroID())
+ return isConfigurationValue(PE->getSubExpr(), PP, SilenceableCondVal,
+ IncludeIntegers, true);
+
+ if (const Expr *Ex = dyn_cast<Expr>(S))
+ S = Ex->IgnoreParenCasts();
+
+ bool IgnoreYES_NO = false;
+
+ switch (S->getStmtClass()) {
+ case Stmt::CallExprClass: {
+ const FunctionDecl *Callee =
+ dyn_cast_or_null<FunctionDecl>(cast<CallExpr>(S)->getCalleeDecl());
+ return Callee ? Callee->isConstexpr() : false;
+ }
+ case Stmt::DeclRefExprClass:
+ return isConfigurationValue(cast<DeclRefExpr>(S)->getDecl(), PP);
+ case Stmt::ObjCBoolLiteralExprClass:
+ IgnoreYES_NO = true;
+ // Fallthrough.
+ case Stmt::CXXBoolLiteralExprClass:
+ case Stmt::IntegerLiteralClass: {
+ const Expr *E = cast<Expr>(S);
+ if (IncludeIntegers) {
+ if (SilenceableCondVal && !SilenceableCondVal->getBegin().isValid())
+ *SilenceableCondVal = E->getSourceRange();
+ return WrappedInParens || isExpandedFromConfigurationMacro(E, PP, IgnoreYES_NO);
+ }
+ return false;
+ }
+ case Stmt::MemberExprClass:
+ return isConfigurationValue(cast<MemberExpr>(S)->getMemberDecl(), PP);
+ case Stmt::UnaryExprOrTypeTraitExprClass:
+ return true;
+ case Stmt::BinaryOperatorClass: {
+ const BinaryOperator *B = cast<BinaryOperator>(S);
+ // Only include raw integers (not enums) as configuration
+ // values if they are used in a logical or comparison operator
+ // (not arithmetic).
+ IncludeIntegers &= (B->isLogicalOp() || B->isComparisonOp());
+ return isConfigurationValue(B->getLHS(), PP, SilenceableCondVal,
+ IncludeIntegers) ||
+ isConfigurationValue(B->getRHS(), PP, SilenceableCondVal,
+ IncludeIntegers);
+ }
+ case Stmt::UnaryOperatorClass: {
+ const UnaryOperator *UO = cast<UnaryOperator>(S);
+ if (SilenceableCondVal)
+ *SilenceableCondVal = UO->getSourceRange();
+ return UO->getOpcode() == UO_LNot &&
+ isConfigurationValue(UO->getSubExpr(), PP, SilenceableCondVal,
+ IncludeIntegers, WrappedInParens);
+ }
+ default:
+ return false;
+ }
+}
+
+static bool isConfigurationValue(const ValueDecl *D, Preprocessor &PP) {
+ if (const EnumConstantDecl *ED = dyn_cast<EnumConstantDecl>(D))
+ return isConfigurationValue(ED->getInitExpr(), PP);
+ if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
+ // As a heuristic, treat globals as configuration values. Note
+ // that we only will get here if Sema evaluated this
+ // condition to a constant expression, which means the global
+ // had to be declared in a way to be a truly constant value.
+ // We could generalize this to local variables, but it isn't
+ // clear if those truly represent configuration values that
+ // gate unreachable code.
+ if (!VD->hasLocalStorage())
+ return true;
+
+ // As a heuristic, locals that have been marked 'const' explicitly
+ // can be treated as configuration values as well.
+ return VD->getType().isLocalConstQualified();
+ }
+ return false;
+}
+
+/// Returns true if we should always explore all successors of a block.
+static bool shouldTreatSuccessorsAsReachable(const CFGBlock *B,
+ Preprocessor &PP) {
+ if (const Stmt *Term = B->getTerminator()) {
+ if (isa<SwitchStmt>(Term))
+ return true;
+ // Specially handle '||' and '&&'.
+ if (isa<BinaryOperator>(Term)) {
+ return isConfigurationValue(Term, PP);
+ }
+ }
+
+ const Stmt *Cond = B->getTerminatorCondition(/* stripParens */ false);
+ return isConfigurationValue(Cond, PP);
+}
+
+static unsigned scanFromBlock(const CFGBlock *Start,
+ llvm::BitVector &Reachable,
+ Preprocessor *PP,
+ bool IncludeSometimesUnreachableEdges) {
+ unsigned count = 0;
+
+ // Prep work queue
+ SmallVector<const CFGBlock*, 32> WL;
+
+ // The entry block may have already been marked reachable
+ // by the caller.
+ if (!Reachable[Start->getBlockID()]) {
+ ++count;
+ Reachable[Start->getBlockID()] = true;
+ }
+
+ WL.push_back(Start);
+
+ // Find the reachable blocks from 'Start'.
+ while (!WL.empty()) {
+ const CFGBlock *item = WL.pop_back_val();
+
+ // There are cases where we want to treat all successors as reachable.
+ // The idea is that some "sometimes unreachable" code is not interesting,
+ // and that we should forge ahead and explore those branches anyway.
+ // This allows us to potentially uncover some "always unreachable" code
+ // within the "sometimes unreachable" code.
+ // Look at the successors and mark then reachable.
+ Optional<bool> TreatAllSuccessorsAsReachable;
+ if (!IncludeSometimesUnreachableEdges)
+ TreatAllSuccessorsAsReachable = false;
+
+ for (CFGBlock::const_succ_iterator I = item->succ_begin(),
+ E = item->succ_end(); I != E; ++I) {
+ const CFGBlock *B = *I;
+ if (!B) do {
+ const CFGBlock *UB = I->getPossiblyUnreachableBlock();
+ if (!UB)
+ break;
+
+ if (!TreatAllSuccessorsAsReachable.hasValue()) {
+ assert(PP);
+ TreatAllSuccessorsAsReachable =
+ shouldTreatSuccessorsAsReachable(item, *PP);
+ }
+
+ if (TreatAllSuccessorsAsReachable.getValue()) {
+ B = UB;
+ break;
+ }
+ }
+ while (false);
+
+ if (B) {
+ unsigned blockID = B->getBlockID();
+ if (!Reachable[blockID]) {
+ Reachable.set(blockID);
+ WL.push_back(B);
+ ++count;
+ }
+ }
+ }
+ }
+ return count;
+}
+
+static unsigned scanMaybeReachableFromBlock(const CFGBlock *Start,
+ Preprocessor &PP,
+ llvm::BitVector &Reachable) {
+ return scanFromBlock(Start, Reachable, &PP, true);
+}
+
+//===----------------------------------------------------------------------===//
+// Dead Code Scanner.
+//===----------------------------------------------------------------------===//
+
+namespace {
+ class DeadCodeScan {
+ llvm::BitVector Visited;
+ llvm::BitVector &Reachable;
+ SmallVector<const CFGBlock *, 10> WorkList;
+ Preprocessor &PP;
+
+ typedef SmallVector<std::pair<const CFGBlock *, const Stmt *>, 12>
+ DeferredLocsTy;
+
+ DeferredLocsTy DeferredLocs;
+
+ public:
+ DeadCodeScan(llvm::BitVector &reachable, Preprocessor &PP)
+ : Visited(reachable.size()),
+ Reachable(reachable),
+ PP(PP) {}
+
+ void enqueue(const CFGBlock *block);
+ unsigned scanBackwards(const CFGBlock *Start,
+ clang::reachable_code::Callback &CB);
+
+ bool isDeadCodeRoot(const CFGBlock *Block);
+
+ const Stmt *findDeadCode(const CFGBlock *Block);
+
+ void reportDeadCode(const CFGBlock *B,
+ const Stmt *S,
+ clang::reachable_code::Callback &CB);
+ };
+}
+
+void DeadCodeScan::enqueue(const CFGBlock *block) {
unsigned blockID = block->getBlockID();
if (Reachable[blockID] || Visited[blockID])
return;
@@ -64,9 +354,9 @@
bool DeadCodeScan::isDeadCodeRoot(const clang::CFGBlock *Block) {
bool isDeadRoot = true;
-
+
for (CFGBlock::const_pred_iterator I = Block->pred_begin(),
- E = Block->pred_end(); I != E; ++I) {
+ E = Block->pred_end(); I != E; ++I) {
if (const CFGBlock *PredBlock = *I) {
unsigned blockID = PredBlock->getBlockID();
if (Visited[blockID]) {
@@ -81,7 +371,7 @@
}
}
}
-
+
return isDeadRoot;
}
@@ -100,11 +390,13 @@
if (isValidDeadStmt(S))
return S;
}
-
+
if (CFGTerminator T = Block->getTerminator()) {
- const Stmt *S = T.getStmt();
- if (isValidDeadStmt(S))
- return S;
+ if (!T.isTemporaryDtorsBranch()) {
+ const Stmt *S = T.getStmt();
+ if (isValidDeadStmt(S))
+ return S;
+ }
}
return 0;
@@ -124,7 +416,7 @@
unsigned count = 0;
enqueue(Start);
-
+
while (!WorkList.empty()) {
const CFGBlock *Block = WorkList.pop_back_val();
@@ -135,7 +427,7 @@
// Look for any dead code within the block.
const Stmt *S = findDeadCode(Block);
-
+
if (!S) {
// No dead code. Possibly an empty block. Look at dead predecessors.
for (CFGBlock::const_pred_iterator I = Block->pred_begin(),
@@ -145,16 +437,16 @@
}
continue;
}
-
+
// Specially handle macro-expanded code.
if (S->getLocStart().isMacroID()) {
- count += clang::reachable_code::ScanReachableFromBlock(Block, Reachable);
+ count += scanMaybeReachableFromBlock(Block, PP, Reachable);
continue;
}
if (isDeadCodeRoot(Block)) {
- reportDeadCode(S, CB);
- count += clang::reachable_code::ScanReachableFromBlock(Block, Reachable);
+ reportDeadCode(Block, S, CB);
+ count += scanMaybeReachableFromBlock(Block, PP, Reachable);
}
else {
// Record this statement as the possibly best location in a
@@ -169,15 +461,15 @@
if (!DeferredLocs.empty()) {
llvm::array_pod_sort(DeferredLocs.begin(), DeferredLocs.end(), SrcCmp);
for (DeferredLocsTy::iterator I = DeferredLocs.begin(),
- E = DeferredLocs.end(); I != E; ++I) {
- const CFGBlock *block = I->first;
- if (Reachable[block->getBlockID()])
+ E = DeferredLocs.end(); I != E; ++I) {
+ const CFGBlock *Block = I->first;
+ if (Reachable[Block->getBlockID()])
continue;
- reportDeadCode(I->second, CB);
- count += clang::reachable_code::ScanReachableFromBlock(block, Reachable);
+ reportDeadCode(Block, I->second, CB);
+ count += scanMaybeReachableFromBlock(Block, PP, Reachable);
}
}
-
+
return count;
}
@@ -208,7 +500,7 @@
case Expr::BinaryConditionalOperatorClass:
case Expr::ConditionalOperatorClass: {
const AbstractConditionalOperator *CO =
- cast<AbstractConditionalOperator>(S);
+ cast<AbstractConditionalOperator>(S);
return CO->getQuestionLoc();
}
case Expr::MemberExprClass: {
@@ -246,61 +538,86 @@
return S->getLocStart();
}
-void DeadCodeScan::reportDeadCode(const Stmt *S,
+void DeadCodeScan::reportDeadCode(const CFGBlock *B,
+ const Stmt *S,
clang::reachable_code::Callback &CB) {
+ // Classify the unreachable code found, or suppress it in some cases.
+ reachable_code::UnreachableKind UK = reachable_code::UK_Other;
+
+ if (isa<BreakStmt>(S)) {
+ UK = reachable_code::UK_Break;
+ }
+ else if (isTrivialDoWhile(B, S)) {
+ return;
+ }
+ else if (isDeadReturn(B, S)) {
+ UK = reachable_code::UK_Return;
+ }
+
+ SourceRange SilenceableCondVal;
+
+ if (UK == reachable_code::UK_Other) {
+ // Check if the dead code is part of the "loop target" of
+ // a for/for-range loop. This is the block that contains
+ // the increment code.
+ if (const Stmt *LoopTarget = B->getLoopTarget()) {
+ SourceLocation Loc = LoopTarget->getLocStart();
+ SourceRange R1(Loc, Loc), R2;
+
+ if (const ForStmt *FS = dyn_cast<ForStmt>(LoopTarget)) {
+ const Expr *Inc = FS->getInc();
+ Loc = Inc->getLocStart();
+ R2 = Inc->getSourceRange();
+ }
+
+ CB.HandleUnreachable(reachable_code::UK_Loop_Increment,
+ Loc, SourceRange(), SourceRange(Loc, Loc), R2);
+ return;
+ }
+
+ // Check if the dead block has a predecessor whose branch has
+ // a configuration value that *could* be modified to
+ // silence the warning.
+ CFGBlock::const_pred_iterator PI = B->pred_begin();
+ if (PI != B->pred_end()) {
+ if (const CFGBlock *PredBlock = PI->getPossiblyUnreachableBlock()) {
+ const Stmt *TermCond =
+ PredBlock->getTerminatorCondition(/* strip parens */ false);
+ isConfigurationValue(TermCond, PP, &SilenceableCondVal);
+ }
+ }
+ }
+
SourceRange R1, R2;
SourceLocation Loc = GetUnreachableLoc(S, R1, R2);
- CB.HandleUnreachable(Loc, R1, R2);
+ CB.HandleUnreachable(UK, Loc, SilenceableCondVal, R1, R2);
}
+//===----------------------------------------------------------------------===//
+// Reachability APIs.
+//===----------------------------------------------------------------------===//
+
namespace clang { namespace reachable_code {
-void Callback::anchor() { }
+void Callback::anchor() { }
unsigned ScanReachableFromBlock(const CFGBlock *Start,
llvm::BitVector &Reachable) {
- unsigned count = 0;
-
- // Prep work queue
- SmallVector<const CFGBlock*, 32> WL;
-
- // The entry block may have already been marked reachable
- // by the caller.
- if (!Reachable[Start->getBlockID()]) {
- ++count;
- Reachable[Start->getBlockID()] = true;
- }
-
- WL.push_back(Start);
-
- // Find the reachable blocks from 'Start'.
- while (!WL.empty()) {
- const CFGBlock *item = WL.pop_back_val();
-
- // Look at the successors and mark then reachable.
- for (CFGBlock::const_succ_iterator I = item->succ_begin(),
- E = item->succ_end(); I != E; ++I)
- if (const CFGBlock *B = *I) {
- unsigned blockID = B->getBlockID();
- if (!Reachable[blockID]) {
- Reachable.set(blockID);
- WL.push_back(B);
- ++count;
- }
- }
- }
- return count;
+ return scanFromBlock(Start, Reachable, /* SourceManager* */ 0, false);
}
-
-void FindUnreachableCode(AnalysisDeclContext &AC, Callback &CB) {
+
+void FindUnreachableCode(AnalysisDeclContext &AC, Preprocessor &PP,
+ Callback &CB) {
+
CFG *cfg = AC.getCFG();
if (!cfg)
return;
- // Scan for reachable blocks from the entrance of the CFG.
+ // Scan for reachable blocks from the entrance of the CFG.
// If there are no unreachable blocks, we're done.
llvm::BitVector reachable(cfg->getNumBlockIDs());
- unsigned numReachable = ScanReachableFromBlock(&cfg->getEntry(), reachable);
+ unsigned numReachable =
+ scanMaybeReachableFromBlock(&cfg->getEntry(), PP, reachable);
if (numReachable == cfg->getNumBlockIDs())
return;
@@ -309,7 +626,7 @@
if (!AC.getCFGBuildOptions().AddEHEdges) {
for (CFG::try_block_iterator I = cfg->try_blocks_begin(),
E = cfg->try_blocks_end() ; I != E; ++I) {
- numReachable += ScanReachableFromBlock(*I, reachable);
+ numReachable += scanMaybeReachableFromBlock(*I, PP, reachable);
}
if (numReachable == cfg->getNumBlockIDs())
return;
@@ -323,7 +640,7 @@
if (reachable[block->getBlockID()])
continue;
- DeadCodeScan DS(reachable);
+ DeadCodeScan DS(reachable, PP);
numReachable += DS.scanBackwards(block, CB);
if (numReachable == cfg->getNumBlockIDs())