From 848ec83483ca4ba52ed72c7e29ebc330f8c87252 Mon Sep 17 00:00:00 2001 From: Ted Kremenek Date: Fri, 11 Feb 2011 23:24:26 +0000 Subject: [PATCH] Don't report dead stores on unreachable code paths. Fixes . git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@125415 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../clang/Analysis/Analyses/LiveVariables.h | 3 +- .../Analysis/FlowSensitive/DataflowSolver.h | 4 ++ lib/Analysis/LiveVariables.cpp | 12 ++-- lib/Analysis/UninitializedValues.cpp | 2 + .../Checkers/DeadStoresChecker.cpp | 66 +++++++++++++++++-- test/Analysis/dead-stores.c | 41 +++++++++++- test/Analysis/unreachable-code-path.c | 4 +- 7 files changed, 117 insertions(+), 15 deletions(-) diff --git a/include/clang/Analysis/Analyses/LiveVariables.h b/include/clang/Analysis/Analyses/LiveVariables.h index 237fe14aed..fbbd2613e7 100644 --- a/include/clang/Analysis/Analyses/LiveVariables.h +++ b/include/clang/Analysis/Analyses/LiveVariables.h @@ -55,7 +55,8 @@ struct LiveVariables_ValueTypes { /// ObserveStmt - A callback invoked right before invoking the /// liveness transfer function on the given statement. - virtual void ObserveStmt(Stmt* S, const AnalysisDataTy& AD, + virtual void ObserveStmt(Stmt* S, const CFGBlock *currentBlock, + const AnalysisDataTy& AD, const ValTy& V) {} virtual void ObserverKill(DeclRefExpr* DR) {} diff --git a/include/clang/Analysis/FlowSensitive/DataflowSolver.h b/include/clang/Analysis/FlowSensitive/DataflowSolver.h index 2d61ecaef2..d75d333db6 100644 --- a/include/clang/Analysis/FlowSensitive/DataflowSolver.h +++ b/include/clang/Analysis/FlowSensitive/DataflowSolver.h @@ -273,6 +273,8 @@ private: void ProcessBlock(const CFGBlock* B, bool recordStmtValues, dataflow::forward_analysis_tag) { + TF.setCurrentBlock(B); + for (StmtItr I=ItrTraits::StmtBegin(B), E=ItrTraits::StmtEnd(B); I!=E;++I) { CFGElement El = *I; if (CFGStmt S = El.getAs()) @@ -285,6 +287,8 @@ private: void ProcessBlock(const CFGBlock* B, bool recordStmtValues, dataflow::backward_analysis_tag) { + TF.setCurrentBlock(B); + TF.VisitTerminator(const_cast(B)); for (StmtItr I=ItrTraits::StmtBegin(B), E=ItrTraits::StmtEnd(B); I!=E;++I) { diff --git a/lib/Analysis/LiveVariables.cpp b/lib/Analysis/LiveVariables.cpp index 47b2e3d604..303dc0f604 100644 --- a/lib/Analysis/LiveVariables.cpp +++ b/lib/Analysis/LiveVariables.cpp @@ -104,8 +104,9 @@ namespace { class TransferFuncs : public CFGRecStmtVisitor{ LiveVariables::AnalysisDataTy& AD; LiveVariables::ValTy LiveState; + const CFGBlock *currentBlock; public: - TransferFuncs(LiveVariables::AnalysisDataTy& ad) : AD(ad) {} + TransferFuncs(LiveVariables::AnalysisDataTy& ad) : AD(ad), currentBlock(0) {} LiveVariables::ValTy& getVal() { return LiveState; } CFG& getCFG() { return AD.getCFG(); } @@ -128,7 +129,10 @@ public: void SetTopValue(LiveVariables::ValTy& V) { V = AD.AlwaysLive; } - + + void setCurrentBlock(const CFGBlock *block) { + currentBlock = block; + } }; void TransferFuncs::Visit(Stmt *S) { @@ -136,7 +140,7 @@ void TransferFuncs::Visit(Stmt *S) { if (S == getCurrentBlkStmt()) { if (AD.Observer) - AD.Observer->ObserveStmt(S,AD,LiveState); + AD.Observer->ObserveStmt(S, currentBlock, AD, LiveState); if (getCFG().isBlkExpr(S)) LiveState(S, AD) = Dead; @@ -146,7 +150,7 @@ void TransferFuncs::Visit(Stmt *S) { else if (!getCFG().isBlkExpr(S)) { if (AD.Observer) - AD.Observer->ObserveStmt(S,AD,LiveState); + AD.Observer->ObserveStmt(S, currentBlock, AD, LiveState); StmtVisitor::Visit(S); diff --git a/lib/Analysis/UninitializedValues.cpp b/lib/Analysis/UninitializedValues.cpp index 5e8331f282..73bce8b3b7 100644 --- a/lib/Analysis/UninitializedValues.cpp +++ b/lib/Analysis/UninitializedValues.cpp @@ -79,6 +79,8 @@ public: bool BlockStmt_VisitExpr(Expr* E); void VisitTerminator(CFGBlock* B) { } + + void setCurrentBlock(const CFGBlock *block) {} }; static const bool Initialized = false; diff --git a/lib/StaticAnalyzer/Checkers/DeadStoresChecker.cpp b/lib/StaticAnalyzer/Checkers/DeadStoresChecker.cpp index e2b3d81931..442e1b3af7 100644 --- a/lib/StaticAnalyzer/Checkers/DeadStoresChecker.cpp +++ b/lib/StaticAnalyzer/Checkers/DeadStoresChecker.cpp @@ -28,26 +28,80 @@ using namespace ento; namespace { +// FIXME: Eventually migrate into its own file, and have it managed by +// AnalysisManager. +class ReachableCode { + const CFG &cfg; + llvm::BitVector reachable; +public: + ReachableCode(const CFG &cfg) + : cfg(cfg), reachable(cfg.getNumBlockIDs(), false) {} + + void computeReachableBlocks(); + + bool isReachable(const CFGBlock *block) const { + return reachable[block->getBlockID()]; + } +}; +} + +void ReachableCode::computeReachableBlocks() { + if (!cfg.getNumBlockIDs()) + return; + + llvm::SmallVector worklist; + worklist.push_back(&cfg.getEntry()); + + while (!worklist.empty()) { + const CFGBlock *block = worklist.back(); + worklist.pop_back(); + llvm::BitVector::reference isReachable = reachable[block->getBlockID()]; + if (isReachable) + continue; + isReachable = true; + for (CFGBlock::const_succ_iterator i = block->succ_begin(), + e = block->succ_end(); i != e; ++i) + if (const CFGBlock *succ = *i) + worklist.push_back(succ); + } +} + +namespace { class DeadStoreObs : public LiveVariables::ObserverTy { + const CFG &cfg; ASTContext &Ctx; BugReporter& BR; ParentMap& Parents; llvm::SmallPtrSet Escaped; + llvm::OwningPtr reachableCode; + const CFGBlock *currentBlock; enum DeadStoreKind { Standard, Enclosing, DeadIncrement, DeadInit }; public: - DeadStoreObs(ASTContext &ctx, BugReporter& br, ParentMap& parents, + DeadStoreObs(const CFG &cfg, ASTContext &ctx, + BugReporter& br, ParentMap& parents, llvm::SmallPtrSet &escaped) - : Ctx(ctx), BR(br), Parents(parents), Escaped(escaped) {} + : cfg(cfg), Ctx(ctx), BR(br), Parents(parents), + Escaped(escaped), currentBlock(0) {} virtual ~DeadStoreObs() {} void Report(VarDecl* V, DeadStoreKind dsk, SourceLocation L, SourceRange R) { if (Escaped.count(V)) return; + + // Compute reachable blocks within the CFG for trivial cases + // where a bogus dead store can be reported because itself is unreachable. + if (!reachableCode.get()) { + reachableCode.reset(new ReachableCode(cfg)); + reachableCode->computeReachableBlocks(); + } + + if (!reachableCode->isReachable(currentBlock)) + return; - std::string name = V->getNameAsString(); + const std::string &name = V->getNameAsString(); const char* BugType = 0; std::string msg; @@ -127,10 +181,12 @@ public: return false; } - virtual void ObserveStmt(Stmt* S, + virtual void ObserveStmt(Stmt* S, const CFGBlock *block, const LiveVariables::AnalysisDataTy& AD, const LiveVariables::ValTy& Live) { + currentBlock = block; + // Skip statements in macros. if (S->getLocStart().isMacroID()) return; @@ -284,6 +340,6 @@ void ento::CheckDeadStores(CFG &cfg, LiveVariables &L, ParentMap &pmap, BugReporter& BR) { FindEscaped FS(&cfg); FS.getCFG().VisitBlockStmts(FS); - DeadStoreObs A(BR.getContext(), BR, pmap, FS.Escaped); + DeadStoreObs A(cfg, BR.getContext(), BR, pmap, FS.Escaped); L.runOnAllBlocks(cfg, &A); } diff --git a/test/Analysis/dead-stores.c b/test/Analysis/dead-stores.c index a07138e50d..9e3f736d77 100644 --- a/test/Analysis/dead-stores.c +++ b/test/Analysis/dead-stores.c @@ -175,15 +175,37 @@ int f18() { x = 10; // expected-warning{{Value stored to 'x' is never read}} while (1) x = 10; // expected-warning{{Value stored to 'x' is never read}} + // unreachable. do - x = 10; // expected-warning{{Value stored to 'x' is never read}} + x = 10; // no-warning while (1); + return (x = 10); // no-warning +} - // Don't warn for dead stores in nested expressions. We have yet - // to see a real bug in this scenario. +int f18_a() { + int x = 0; // no-warning return (x = 10); // no-warning } +void f18_b() { + int x = 0; // no-warning + if (1) + x = 10; // expected-warning{{Value stored to 'x' is never read}} +} + +void f18_c() { + int x = 0; + while (1) + x = 10; // expected-warning{{Value stored to 'x' is never read}} +} + +void f18_d() { + int x = 0; // no-warning + do + x = 10; // expected-warning{{Value stored to 'x' is never read}} + while (1); +} + // PR 3514: false positive `dead initialization` warning for init to global // http://llvm.org/bugs/show_bug.cgi?id=3514 extern const int MyConstant; @@ -492,3 +514,16 @@ void rdar8320674(s_rdar8320674 *z, unsigned y, s2_rdar8320674 *st, int m) }while (--m); } +// Avoid dead stores resulting from an assignment (and use) being unreachable. +void rdar8405222_aux(int i); +void rdar8405222() { + const int show = 0; + int i = 0; + + if (show) + i = 5; // no-warning + + if (show) + rdar8405222_aux(i); +} + diff --git a/test/Analysis/unreachable-code-path.c b/test/Analysis/unreachable-code-path.c index acc30f4334..5e7a9872f9 100644 --- a/test/Analysis/unreachable-code-path.c +++ b/test/Analysis/unreachable-code-path.c @@ -114,9 +114,9 @@ void test10() { goto b; // expected-warning {{never executed}} goto a; // expected-warning {{never executed}} b: - i = 1; // expected-warning {{Value stored to 'i' is never read}} + i = 1; // no-warning a: - i = 2; // expected-warning {{Value stored to 'i' is never read}} + i = 2; // no-warning goto f; e: goto d; -- 2.40.0