diff options
Diffstat (limited to 'contrib/llvm/tools/clang/lib/Analysis/ReachableCode.cpp')
-rw-r--r-- | contrib/llvm/tools/clang/lib/Analysis/ReachableCode.cpp | 515 |
1 files changed, 430 insertions, 85 deletions
diff --git a/contrib/llvm/tools/clang/lib/Analysis/ReachableCode.cpp b/contrib/llvm/tools/clang/lib/Analysis/ReachableCode.cpp index a2d19c0..b4a72a7 100644 --- a/contrib/llvm/tools/clang/lib/Analysis/ReachableCode.cpp +++ b/contrib/llvm/tools/clang/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,352 @@ 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) {} +//===----------------------------------------------------------------------===// +// 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()); +} + +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 current control flow ends with a 'return', and see if + // 'S' is a substatement. The 'return' may not be the last element in the + // block, or may be in a subsequent block because of destructors. + const CFGBlock *Current = B; + while (true) { + for (CFGBlock::const_reverse_iterator I = Current->rbegin(), + E = Current->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. + return PM.getParent(S); + } + } + break; + } + } + // Note also that we are restricting the search for the return statement + // to stop at control-flow; only part of a return statement may be dead, + // without the whole return statement being dead. + if (Current->getTerminator().isTemporaryDtorsBranch()) { + // Temporary destructors have a predictable control flow, thus we want to + // look into the next block for the return statement. + // We look into the false branch, as we know the true branch only contains + // the call to the destructor. + assert(Current->succ_size() == 2); + Current = *(Current->succ_begin() + 1); + } else if (!Current->getTerminator() && Current->succ_size() == 1) { + // If there is only one successor, we're not dealing with outgoing control + // flow. Thus, look into the next block. + Current = *Current->succ_begin(); + if (Current->pred_size() > 1) { + // If there is more than one predecessor, we're dealing with incoming + // control flow - if the return statement is in that block, it might + // well be reachable via a different control flow, thus it's not dead. + return false; + } + } else { + // We hit control flow or a dead end. Stop searching. + return false; + } + } + llvm_unreachable("Broke out of infinite loop."); +} + +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; + + if (const Expr *Ex = dyn_cast<Expr>(S)) + S = Ex->IgnoreCasts(); + + // 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->IgnoreCasts(); + + 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; - void enqueue(const CFGBlock *block); - unsigned scanBackwards(const CFGBlock *Start, - clang::reachable_code::Callback &CB); + // Prep work queue + SmallVector<const CFGBlock*, 32> WL; - bool isDeadCodeRoot(const CFGBlock *Block); + // The entry block may have already been marked reachable + // by the caller. + if (!Reachable[Start->getBlockID()]) { + ++count; + Reachable[Start->getBlockID()] = true; + } - const Stmt *findDeadCode(const CFGBlock *Block); + WL.push_back(Start); - void reportDeadCode(const Stmt *S, - clang::reachable_code::Callback &CB); -}; + // 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; } -void DeadCodeScan::enqueue(const CFGBlock *block) { +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 +382,9 @@ void DeadCodeScan::enqueue(const CFGBlock *block) { 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 +399,7 @@ bool DeadCodeScan::isDeadCodeRoot(const clang::CFGBlock *Block) { } } } - + return isDeadRoot; } @@ -100,14 +418,16 @@ const Stmt *DeadCodeScan::findDeadCode(const clang::CFGBlock *Block) { 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; + return nullptr; } static int SrcCmp(const std::pair<const CFGBlock *, const Stmt *> *p1, @@ -124,7 +444,7 @@ unsigned DeadCodeScan::scanBackwards(const clang::CFGBlock *Start, unsigned count = 0; enqueue(Start); - + while (!WorkList.empty()) { const CFGBlock *Block = WorkList.pop_back_val(); @@ -135,7 +455,7 @@ unsigned DeadCodeScan::scanBackwards(const clang::CFGBlock *Start, // 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 +465,16 @@ unsigned DeadCodeScan::scanBackwards(const clang::CFGBlock *Start, } 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 +489,15 @@ unsigned DeadCodeScan::scanBackwards(const clang::CFGBlock *Start, 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 +528,7 @@ static SourceLocation GetUnreachableLoc(const Stmt *S, case Expr::BinaryConditionalOperatorClass: case Expr::ConditionalOperatorClass: { const AbstractConditionalOperator *CO = - cast<AbstractConditionalOperator>(S); + cast<AbstractConditionalOperator>(S); return CO->getQuestionLoc(); } case Expr::MemberExprClass: { @@ -246,61 +566,86 @@ static SourceLocation GetUnreachableLoc(const Stmt *S, 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* */ nullptr, 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 +654,7 @@ void FindUnreachableCode(AnalysisDeclContext &AC, Callback &CB) { 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 +668,7 @@ void FindUnreachableCode(AnalysisDeclContext &AC, Callback &CB) { if (reachable[block->getBlockID()]) continue; - DeadCodeScan DS(reachable); + DeadCodeScan DS(reachable, PP); numReachable += DS.scanBackwards(block, CB); if (numReachable == cfg->getNumBlockIDs()) |