diff --git a/clang/include/clang/Analysis/AnalysisDeclContext.h b/clang/include/clang/Analysis/AnalysisDeclContext.h --- a/clang/include/clang/Analysis/AnalysisDeclContext.h +++ b/clang/include/clang/Analysis/AnalysisDeclContext.h @@ -251,6 +251,7 @@ const Decl *getDecl() const { return Ctx->getDecl(); } CFG *getCFG() const { return Ctx->getCFG(); } + CFG *getUnoptimizedCFG() const { return Ctx->getUnoptimizedCFG(); } template T *getAnalysis() const { return Ctx->getAnalysis(); } diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h @@ -399,10 +399,18 @@ node_iterator nodes_end() { return Nodes.end(); } + llvm::iterator_range nodes() { + return llvm::make_range(nodes_begin(), nodes_end()); + } + const_node_iterator nodes_begin() const { return Nodes.begin(); } const_node_iterator nodes_end() const { return Nodes.end(); } + llvm::iterator_range nodes() const { + return llvm::make_range(nodes_begin(), nodes_end()); + } + roots_iterator roots_begin() { return Roots.begin(); } roots_iterator roots_end() { return Roots.end(); } diff --git a/clang/lib/StaticAnalyzer/Checkers/UnreachableCodeChecker.cpp b/clang/lib/StaticAnalyzer/Checkers/UnreachableCodeChecker.cpp --- a/clang/lib/StaticAnalyzer/Checkers/UnreachableCodeChecker.cpp +++ b/clang/lib/StaticAnalyzer/Checkers/UnreachableCodeChecker.cpp @@ -12,10 +12,10 @@ // A similar flow-sensitive only check exists in Analysis/ReachableCode.cpp //===----------------------------------------------------------------------===// -#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h" #include "clang/AST/ParentMap.h" #include "clang/Basic/Builtins.h" #include "clang/Basic/SourceManager.h" +#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h" #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" #include "clang/StaticAnalyzer/Core/Checker.h" #include "clang/StaticAnalyzer/Core/CheckerManager.h" @@ -23,200 +23,84 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" -#include "llvm/ADT/SmallSet.h" +#include using namespace clang; using namespace ento; +using namespace llvm; + +using CFGBlocksSet = SmallSet; + +template static auto skippingNulls(Range &&R) { + auto IsNonNull = [](const CFGBlock *B) -> bool { return B; }; + return llvm::make_filter_range(R, IsNonNull); +} namespace { class UnreachableCodeChecker : public Checker { public: void checkEndAnalysis(ExplodedGraph &G, BugReporter &B, ExprEngine &Eng) const; -private: - typedef llvm::SmallSet CFGBlocksSet; - - static inline const Stmt *getUnreachableStmt(const CFGBlock *CB); - static void FindUnreachableEntryPoints(const CFGBlock *CB, - CFGBlocksSet &reachable, - CFGBlocksSet &visited); - static bool isInvalidPath(const CFGBlock *CB, const ParentMap &PM); - static inline bool isEmptyCFGBlock(const CFGBlock *CB); }; -} - -void UnreachableCodeChecker::checkEndAnalysis(ExplodedGraph &G, - BugReporter &B, - ExprEngine &Eng) const { - CFGBlocksSet reachable, visited; - - if (Eng.hasWorkRemaining()) +} // namespace + +// Finds the entry point(s) for this dead CFGBlock in a BFS order. +// Marks reachable all blocks, whose parents are all unreachable. +static void filterUnreachableEntryPoints(const CFGBlock *CB, + CFGBlocksSet &Reachable, + CFGBlocksSet &Visited) { + if (Visited.contains(CB->getBlockID())) return; - const Decl *D = nullptr; - CFG *C = nullptr; - const ParentMap *PM = nullptr; - const LocationContext *LC = nullptr; - // Iterate over ExplodedGraph - for (ExplodedGraph::node_iterator I = G.nodes_begin(), E = G.nodes_end(); - I != E; ++I) { - const ProgramPoint &P = I->getLocation(); - LC = P.getLocationContext(); - if (!LC->inTopFrame()) - continue; - - if (!D) - D = LC->getAnalysisDeclContext()->getDecl(); - - // Save the CFG if we don't have it already - if (!C) - C = LC->getAnalysisDeclContext()->getUnoptimizedCFG(); - if (!PM) - PM = &LC->getParentMap(); - - if (Optional BE = P.getAs()) { - const CFGBlock *CB = BE->getBlock(); - reachable.insert(CB->getBlockID()); - } - } - - // Bail out if we didn't get the CFG or the ParentMap. - if (!D || !C || !PM) - return; - - // Don't do anything for template instantiations. Proving that code - // in a template instantiation is unreachable means proving that it is - // unreachable in all instantiations. - if (const FunctionDecl *FD = dyn_cast(D)) - if (FD->isTemplateInstantiation()) - return; - - // Find CFGBlocks that were not covered by any node - for (CFG::const_iterator I = C->begin(), E = C->end(); I != E; ++I) { - const CFGBlock *CB = *I; - // Check if the block is unreachable - if (reachable.count(CB->getBlockID())) - continue; + auto IsUnreachable = [&Reachable](const CFGBlock *B) -> bool { + return !Reachable.contains(B->getBlockID()); + }; - // Check if the block is empty (an artificial block) - if (isEmptyCFGBlock(CB)) - continue; + std::queue Worklist; + Worklist.push(CB); - // Find the entry points for this block - if (!visited.count(CB->getBlockID())) - FindUnreachableEntryPoints(CB, reachable, visited); + while (!Worklist.empty()) { + const CFGBlock *Current = Worklist.front(); + unsigned CurrentID = Current->getBlockID(); + Worklist.pop(); - // This block may have been pruned; check if we still want to report it - if (reachable.count(CB->getBlockID())) + // Skip if already visited. + if (!Visited.insert(CurrentID).second) continue; - // Check for false positives - if (isInvalidPath(CB, *PM)) - continue; + auto NonNullPreds = skippingNulls(Current->preds()); - // It is good practice to always have a "default" label in a "switch", even - // if we should never get there. It can be used to detect errors, for - // instance. Unreachable code directly under a "default" label is therefore - // likely to be a false positive. - if (const Stmt *label = CB->getLabel()) - if (label->getStmtClass() == Stmt::DefaultStmtClass) - continue; - - // Special case for __builtin_unreachable. - // FIXME: This should be extended to include other unreachable markers, - // such as llvm_unreachable. - if (!CB->empty()) { - bool foundUnreachable = false; - for (CFGBlock::const_iterator ci = CB->begin(), ce = CB->end(); - ci != ce; ++ci) { - if (Optional S = (*ci).getAs()) - if (const CallExpr *CE = dyn_cast(S->getStmt())) { - if (CE->getBuiltinCallee() == Builtin::BI__builtin_unreachable || - CE->isBuiltinAssumeFalse(Eng.getContext())) { - foundUnreachable = true; - break; - } - } - } - if (foundUnreachable) - continue; - } - - // We found a block that wasn't covered - find the statement to report - SourceRange SR; - PathDiagnosticLocation DL; - SourceLocation SL; - if (const Stmt *S = getUnreachableStmt(CB)) { - // In macros, 'do {...} while (0)' is often used. Don't warn about the - // condition 0 when it is unreachable. - if (S->getBeginLoc().isMacroID()) - if (const auto *I = dyn_cast(S)) - if (I->getValue() == 0ULL) - if (const Stmt *Parent = PM->getParent(S)) - if (isa(Parent)) - continue; - SR = S->getSourceRange(); - DL = PathDiagnosticLocation::createBegin(S, B.getSourceManager(), LC); - SL = DL.asLocation(); - if (SR.isInvalid() || !SL.isValid()) - continue; - } - else - continue; + // Schedule the unvisited predecessors. + for (const CFGBlock *Pred : NonNullPreds) + Worklist.push(Pred); - // Check if the SourceLocation is in a system header - const SourceManager &SM = B.getSourceManager(); - if (SM.isInSystemHeader(SL) || SM.isInExternCSystemHeader(SL)) + if (Reachable.contains(CurrentID)) continue; - B.EmitBasicReport(D, this, "Unreachable code", categories::UnusedCode, - "This statement is never executed", DL, SR); + // If all predecessors are unreachable, consider the current block as + // reachable. + if (!NonNullPreds.empty() && all_of(NonNullPreds, IsUnreachable)) + Reachable.insert(CurrentID); } } -// Recursively finds the entry point(s) for this dead CFGBlock. -void UnreachableCodeChecker::FindUnreachableEntryPoints(const CFGBlock *CB, - CFGBlocksSet &reachable, - CFGBlocksSet &visited) { - visited.insert(CB->getBlockID()); - - for (CFGBlock::const_pred_iterator I = CB->pred_begin(), E = CB->pred_end(); - I != E; ++I) { - if (!*I) - continue; - - if (!reachable.count((*I)->getBlockID())) { - // If we find an unreachable predecessor, mark this block as reachable so - // we don't report this block - reachable.insert(CB->getBlockID()); - if (!visited.count((*I)->getBlockID())) - // If we haven't previously visited the unreachable predecessor, recurse - FindUnreachableEntryPoints(*I, reachable, visited); - } - } -} - -// Find the Stmt* in a CFGBlock for reporting a warning -const Stmt *UnreachableCodeChecker::getUnreachableStmt(const CFGBlock *CB) { - for (CFGBlock::const_iterator I = CB->begin(), E = CB->end(); I != E; ++I) { - if (Optional S = I->getAs()) { +/// Find the Stmt* in a CFGBlock for reporting a warning. +/// Might return null. +static const Stmt *getUnreachableStmt(const CFGBlock *CB) { + for (const CFGElement &E : *CB) { + if (auto S = E.getAs()) if (!isa(S->getStmt())) return S->getStmt(); - } } - if (const Stmt *S = CB->getTerminatorStmt()) - return S; - else - return nullptr; + return CB->getTerminatorStmt(); } // Determines if the path to this CFGBlock contained an element that infers this -// block is a false positive. We assume that FindUnreachableEntryPoints has +// block is a false positive. We assume that findUnreachableEntryPoints has // already marked only the entry points to any dead code, so we need only to // find the condition that led to this block (the predecessor of this block.) // There will never be more than one predecessor. -bool UnreachableCodeChecker::isInvalidPath(const CFGBlock *CB, - const ParentMap &PM) { +static bool isInvalidPath(const CFGBlock *CB, const ParentMap &PM) { // We only expect a predecessor size of 0 or 1. If it is >1, then an external // condition has broken our assumption (for example, a sink being placed by // another check). In these cases, we choose not to report. @@ -227,16 +111,16 @@ if (CB->pred_size() == 0) return false; - const CFGBlock *pred = *CB->pred_begin(); - if (!pred) + auto NonNullPreds = skippingNulls(CB->preds()); + if (NonNullPreds.empty()) return false; // Get the predecessor block's terminator condition - const Stmt *cond = pred->getTerminatorCondition(); + const Stmt *cond = (*NonNullPreds.begin())->getTerminatorCondition(); - //assert(cond && "CFGBlock's predecessor has a terminator condition"); - // The previous assertion is invalid in some cases (eg do/while). Leaving - // reporting of these situations on at the moment to help triage these cases. + // assert(cond && "CFGBlock's predecessor has a terminator condition"); + // The previous assertion is invalid in some cases (eg do/while). Leaving + // reporting of these situations on at the moment to help triage these cases. if (!cond) return false; @@ -247,10 +131,171 @@ } // Returns true if the given CFGBlock is empty -bool UnreachableCodeChecker::isEmptyCFGBlock(const CFGBlock *CB) { - return CB->getLabel() == nullptr // No labels - && CB->size() == 0 // No statements - && !CB->getTerminatorStmt(); // No terminator +static bool isEmptyCFGBlock(const CFGBlock *CB) { + return CB->getLabel() == nullptr // No labels + && CB->size() == 0 // No statements + && !CB->getTerminatorStmt(); // No terminator +} + +static bool isBuiltinUnreachable(const CFGBlock *CB, const ASTContext &Ctx) { + for (const CFGElement &E : *CB) { + if (const auto S = E.getAs()) + if (const auto *CE = dyn_cast(S->getStmt())) { + if (CE->getBuiltinCallee() == Builtin::BI__builtin_unreachable || + CE->isBuiltinAssumeFalse(Ctx)) { + return true; + } + } + } + return false; +} + +static bool isDoWhileMacro(const Stmt *S, const ParentMap &PM) { + if (S->getBeginLoc().isMacroID()) + if (const auto *I = dyn_cast(S)) + if (I->getValue() == 0) + if (const Stmt *Parent = PM.getParent(S)) + if (isa(Parent)) + return true; + return false; +} + +/// TODO: Doc this... +static bool shouldIgnoreBlock(const CFGBlock *CB, const ParentMap &PM, + const ASTContext &Ctx) { + // Check for false positives. + if (isInvalidPath(CB, PM)) + return true; + + // It is good practice to always have a "default" label in a "switch", even + // if we should never get there. It can be used to detect errors, for + // instance. Unreachable code directly under a "default" label is therefore + // likely to be a false positive. + if (const Stmt *L = CB->getLabel()) + if (L->getStmtClass() == Stmt::DefaultStmtClass) + return true; + + // Special case for __builtin_unreachable. + // FIXME: This should be extended to include other unreachable markers, + // such as llvm_unreachable. + if (isBuiltinUnreachable(CB, Ctx)) + return true; + + return false; +} + +static const StackFrameContext *getTopFrame(const ExplodedGraph &G) { + for (const ExplodedNode &N : G.nodes()) + if (N.getLocation().getLocationContext()->inTopFrame()) + return cast(N.getLocationContext()); + llvm_unreachable("The top-level frame should always exist."); +} + +/// The sink block should be reachable, but all the non-self successor blocks +/// should be unreachable. +static bool isSink(const CFGBlock *Block, const CFGBlocksSet &Reachables) { + if (!Reachables.contains(Block->getBlockID())) + return false; + + for (const CFGBlock *Succ : skippingNulls(Block->succs())) + if (Reachables.contains(Succ->getBlockID())) + return false; + + return true; +} + +static CFGBlocksSet collectReachableBlocks(const ExplodedGraph &G) { + CFGBlocksSet Reachable; + for (const ExplodedNode &N : G.nodes()) + if (N.getLocation().getLocationContext()->inTopFrame()) + if (auto BE = N.getLocationAs()) + Reachable.insert(BE->getBlock()->getBlockID()); + return Reachable; +} + +static void filterUnreachableBlocksCausedBySinks( + const std::vector &Blocks, CFGBlocksSet &Reachables) { + CFGBlocksSet SuccessorsOfSinks; + for (const CFGBlock *Block : Blocks) { + assert(Block); + if (isSink(Block, Reachables)) + for (const CFGBlock *Succ : skippingNulls(Block->succs())) + SuccessorsOfSinks.insert(Succ->getBlockID()); + } + + // Mark these blocks as 'reachable' to prevent reporting these. + Reachables.insert(SuccessorsOfSinks.begin(), SuccessorsOfSinks.end()); +} + +void UnreachableCodeChecker::checkEndAnalysis(ExplodedGraph &G, BugReporter &B, + ExprEngine &Eng) const { + if (Eng.hasWorkRemaining()) + return; + + const SourceManager &SM = B.getSourceManager(); + const ASTContext &ACtx = Eng.getContext(); + const StackFrameContext *Frame = getTopFrame(G); + const ParentMap &PM = Frame->getParentMap(); + const CFG *C = Frame->getUnoptimizedCFG(); + assert(C); + + // Don't do anything for template instantiations. Proving that code + // in a template instantiation is unreachable means proving that it is + // unreachable in all instantiations. + if (const FunctionDecl *FD = dyn_cast(Frame->getDecl())) + if (FD->isTemplateInstantiation()) + return; + + CFGBlocksSet Visited; + CFGBlocksSet Reachables = collectReachableBlocks(G); + Visited.insert(C->getEntry().getBlockID()); + Reachables.insert(C->getEntry().getBlockID()); + Reachables.insert(C->getExit().getBlockID()); + + filterUnreachableEntryPoints(&C->getExit(), Reachables, Visited); + + std::vector ConsideredBlocks; + ConsideredBlocks.reserve(C->size()); + llvm::append_range(ConsideredBlocks, skippingNulls(*C)); + llvm::erase_if(ConsideredBlocks, isEmptyCFGBlock); + + filterUnreachableBlocksCausedBySinks(ConsideredBlocks, Reachables); + + auto ShouldIgnoreBlock = [&](const CFGBlock *B) { + return shouldIgnoreBlock(B, PM, ACtx); + }; + auto IsReachable = [&](const CFGBlock *B) { + return Reachables.contains(B->getBlockID()); + }; + + llvm::erase_if(ConsideredBlocks, ShouldIgnoreBlock); + llvm::erase_if(ConsideredBlocks, IsReachable); + + for (const CFGBlock *UnreachableBlock : ConsideredBlocks) { + const Stmt *S = getUnreachableStmt(UnreachableBlock); + if (!S) + continue; + + if (isDoWhileMacro(S, PM)) + continue; + + // FIXME: Exceptions and try-catch blocks are modeled by a malformed CFG. + // Let's suppress these for now. + // For more details see: #55621. + if (isa(S)) + continue; + + SourceRange SR = S->getSourceRange(); + PathDiagnosticLocation DL = + PathDiagnosticLocation::createBegin(S, SM, Frame); + SourceLocation SL = DL.asLocation(); + if (SR.isInvalid() || !SL.isValid() || SM.isInSystemHeader(SL)) + continue; + + B.EmitBasicReport(Frame->getDecl(), this, "Unreachable code", + categories::UnusedCode, + "This statement is never executed", DL, SR); + } } void ento::registerUnreachableCodeChecker(CheckerManager &mgr) { diff --git a/clang/test/Analysis/unreachable-code-exceptions.cpp b/clang/test/Analysis/unreachable-code-exceptions.cpp new file mode 100644 --- /dev/null +++ b/clang/test/Analysis/unreachable-code-exceptions.cpp @@ -0,0 +1,14 @@ +// RUN: %clang_analyze_cc1 -verify %s -fcxx-exceptions -fexceptions \ +// RUN: -analyzer-checker=core \ +// RUN: -analyzer-checker=alpha.deadcode.UnreachableCode + +// expected-no-diagnostics + +int test(int a) { + try { // no-warning + a *= 2; + } catch (int) { + return -1; // FIXME: We should mark this dead. + } + return a; +} diff --git a/clang/test/Analysis/unreachable-code-path.c b/clang/test/Analysis/unreachable-code-path.c --- a/clang/test/Analysis/unreachable-code-path.c +++ b/clang/test/Analysis/unreachable-code-path.c @@ -120,10 +120,21 @@ i = 2; // no-warning goto f; e: - goto d; + goto d; // expected-warning {{never executed}} f: ; } +void test10_chained_unreachable(void) { + goto end; +a: + goto b; // expected-warning {{never executed}} +b: + goto c; // expected-warning {{never executed}} +c: + goto a; // expected-warning {{never executed}} +end:; +} + // test11: we can actually end up in the default case, even if it is not // obvious: there might be something wrong with the given argument. enum foobar { FOO, BAR }; @@ -224,3 +235,37 @@ void macro2(void) { MACRO(1); } + +int if_else_if_chain(int x) { + if (x != 0) + return -1; + int v1 = 100 / x; // expected-warning {{Division by zero}} + + /// We should not warn for dead code, caused by a sink node. + int clamped; // no-warning + if (v1 < 0) // no-warning + clamped = 0; // no-warning + else if (v1 > 100) // no-warning + clamped = 100; // no-warning + else if (v1 % 2 == 0) // no-warning + clamped = 0; // no-warning + else if (v1 % 2 == -1) // no-warning + clamped = -1; // no-warning + else // no-warning + clamped = v1; // no-warning + return clamped; +} + +int unreachable_standalone_recursive_block(int a) { + switch (a) { + back: + a += 5; // expected-warning{{never executed}} + a *= 2; // no-warning + goto back; + case 2: + a *= 10; + case 3: + a %= 2; + } + return a; +} diff --git a/clang/test/Analysis/unreachable-code-path.cpp b/clang/test/Analysis/unreachable-code-path.cpp new file mode 100644 --- /dev/null +++ b/clang/test/Analysis/unreachable-code-path.cpp @@ -0,0 +1,23 @@ +// RUN: %clang_analyze_cc1 -verify %s \ +// RUN: -analyzer-checker=core,deadcode,alpha.deadcode + +// expected-no-diagnostics + +struct NonTrivial { + ~NonTrivial(); +}; +struct NonTrivialPair { + NonTrivial a, b; +}; +enum Kind { Kind1 }; + +// This code creates a null CFGBlock in the unoptimized CFG. +// Should not crash. +void NullCFGBlock(enum Kind k) { + { // Block start + NonTrivialPair a; + } + switch (k) { + case Kind1:; + } +}