Don't report dead stores on unreachable code paths. Fixes <rdar://problem/8405222>.

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@125415 91177308-0d34-0410-b5e6-96231b3b80d8

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<CFGStmt>())
@@ -285,6 +287,8 @@ private:
   void ProcessBlock(const CFGBlock* B, bool recordStmtValues,
                     dataflow::backward_analysis_tag) {
 
+    TF.setCurrentBlock(B);
+    
     TF.VisitTerminator(const_cast<CFGBlock*>(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<TransferFuncs>{
   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<TransferFuncs,void>::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<const CFGBlock*, 10> 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<VarDecl*, 20> Escaped;
+  llvm::OwningPtr<ReachableCode> 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<VarDecl*, 20> &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;