[analyzer] Fix some expressions staying live too long. Add a debug checker.

StaticAnalyzer uses the CFG-based RelaxedLiveVariables analysis in order to,
in particular, figure out values of which expressions are still needed.
When the expression becomes "dead", it is garbage-collected during
the dead binding scan.

Expressions that constitute branches/bodies of control flow statements,
eg. `E1' in `if (C1) E1;' but not `E2' in `if (C2) { E2; }', were kept alive
for too long. This caused false positives in MoveChecker because it relies
on cleaning up loop-local variables when they go out of scope, but some of those
live-for-too-long expressions were keeping a reference to those variables.

Fix liveness analysis to correctly mark these expressions as dead.

Add a debug checker, debug.DumpLiveStmts, in order to test expressions liveness.

Differential Revision: https://reviews.llvm.org/D55566

llvm-svn: 349320

7 files changed, 286 insertions, 3 deletions

diff --git a/clang/docs/analyzer/DebugChecks.rst b/clang/docs/analyzer/DebugChecks.rst
index 7b192f65224f..bb2f37f33955 100644
--- a/clang/docs/analyzer/DebugChecks.rst
+++ b/clang/docs/analyzer/DebugChecks.rst
@@ -30,9 +30,12 @@ using a 'dot' format viewer (such as Graphviz on OS X) instead.
 - debug.DumpLiveVars: Show the results of live variable analysis for each
   top-level function being analyzed.
 
+- debug.DumpLiveStmts: Show the results of live statement analysis for each
+  top-level function being analyzed.
+
 - debug.ViewExplodedGraph: Show the Exploded Graphs generated for the
   analysis of different functions in the input translation unit. When there
-  are several functions analyzed, display one graph per function. Beware 
+  are several functions analyzed, display one graph per function. Beware
   that these graphs may grow very large, even for small functions.
 
 Path Tracking
diff --git a/clang/include/clang/Analysis/Analyses/LiveVariables.h b/clang/include/clang/Analysis/Analyses/LiveVariables.h
index 0cb500fffb95..114597661a67 100644
--- a/clang/include/clang/Analysis/Analyses/LiveVariables.h
+++ b/clang/include/clang/Analysis/Analyses/LiveVariables.h
@@ -88,9 +88,13 @@ public:
   ///  before the given block-level expression (see runOnAllBlocks).
   bool isLive(const Stmt *Loc, const Stmt *StmtVal);
 
-  /// Print to stderr the liveness information associated with
+  /// Print to stderr the variable liveness information associated with
   /// each basic block.
-  void dumpBlockLiveness(const SourceManager& M);
+  void dumpBlockLiveness(const SourceManager &M);
+
+  /// Print to stderr the statement liveness information associated with
+  /// each basic block.
+  void dumpStmtLiveness(const SourceManager &M);
 
   void runOnAllBlocks(Observer &obs);
 
diff --git a/clang/include/clang/StaticAnalyzer/Checkers/Checkers.td b/clang/include/clang/StaticAnalyzer/Checkers/Checkers.td
index 9feb5a876687..5280ad70e9e2 100644
--- a/clang/include/clang/StaticAnalyzer/Checkers/Checkers.td
+++ b/clang/include/clang/StaticAnalyzer/Checkers/Checkers.td
@@ -707,6 +707,9 @@ def DominatorsTreeDumper : Checker<"DumpDominators">,
 def LiveVariablesDumper : Checker<"DumpLiveVars">,
   HelpText<"Print results of live variable analysis">;
 
+def LiveStatementsDumper : Checker<"DumpLiveStmts">,
+  HelpText<"Print results of live statement analysis">;
+
 def CFGViewer : Checker<"ViewCFG">,
   HelpText<"View Control-Flow Graphs using GraphViz">;
 
diff --git a/clang/lib/Analysis/LiveVariables.cpp b/clang/lib/Analysis/LiveVariables.cpp
index 4f22ccc55a77..afe2d264907f 100644
--- a/clang/lib/Analysis/LiveVariables.cpp
+++ b/clang/lib/Analysis/LiveVariables.cpp
@@ -93,6 +93,7 @@ public:
              LiveVariables::Observer *obs = nullptr);
 
   void dumpBlockLiveness(const SourceManager& M);
+  void dumpStmtLiveness(const SourceManager& M);
 
   LiveVariablesImpl(AnalysisDeclContext &ac, bool KillAtAssign)
     : analysisContext(ac),
@@ -327,6 +328,35 @@ void TransferFunctions::Visit(Stmt *S) {
       // No need to unconditionally visit subexpressions.
       return;
     }
+    case Stmt::IfStmtClass: {
+      // If one of the branches is an expression rather than a compound
+      // statement, it will be bad if we mark it as live at the terminator
+      // of the if-statement (i.e., immediately after the condition expression).
+      AddLiveStmt(val.liveStmts, LV.SSetFact, cast<IfStmt>(S)->getCond());
+      return;
+    }
+    case Stmt::WhileStmtClass: {
+      // If the loop body is an expression rather than a compound statement,
+      // it will be bad if we mark it as live at the terminator of the loop
+      // (i.e., immediately after the condition expression).
+      AddLiveStmt(val.liveStmts, LV.SSetFact, cast<WhileStmt>(S)->getCond());
+      return;
+    }
+    case Stmt::DoStmtClass: {
+      // If the loop body is an expression rather than a compound statement,
+      // it will be bad if we mark it as live at the terminator of the loop
+      // (i.e., immediately after the condition expression).
+      AddLiveStmt(val.liveStmts, LV.SSetFact, cast<DoStmt>(S)->getCond());
+      return;
+    }
+    case Stmt::ForStmtClass: {
+      // If the loop body is an expression rather than a compound statement,
+      // it will be bad if we mark it as live at the terminator of the loop
+      // (i.e., immediately after the condition expression).
+      AddLiveStmt(val.liveStmts, LV.SSetFact, cast<ForStmt>(S)->getCond());
+      return;
+    }
+
   }
 
   for (Stmt *Child : S->children()) {
@@ -632,5 +662,23 @@ void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) {
   llvm::errs() << "\n";
 }
 
+void LiveVariables::dumpStmtLiveness(const SourceManager &M) {
+  getImpl(impl).dumpStmtLiveness(M);
+}
+
+void LiveVariablesImpl::dumpStmtLiveness(const SourceManager &M) {
+  // Don't iterate over blockEndsToLiveness directly because it's not sorted.
+  for (auto I : *analysisContext.getCFG()) {
+
+    llvm::errs() << "\n[ B" << I->getBlockID()
+                 << " (live statements at block exit) ]\n";
+    for (auto S : blocksEndToLiveness[I].liveStmts) {
+      llvm::errs() << "\n";
+      S->dump();
+    }
+    llvm::errs() << "\n";
+  }
+}
+
 const void *LiveVariables::getTag() { static int x; return &x; }
 const void *RelaxedLiveVariables::getTag() { static int x; return &x; }
diff --git a/clang/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp b/clang/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp
index 5840ee79133b..90b1111aff0f 100644
--- a/clang/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp
+++ b/clang/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp
@@ -69,6 +69,25 @@ void ento::registerLiveVariablesDumper(CheckerManager &mgr) {
 }
 
 //===----------------------------------------------------------------------===//
+// LiveStatementsDumper
+//===----------------------------------------------------------------------===//
+
+namespace {
+class LiveStatementsDumper : public Checker<check::ASTCodeBody> {
+public:
+  void checkASTCodeBody(const Decl *D, AnalysisManager& Mgr,
+                        BugReporter &BR) const {
+    if (LiveVariables *L = Mgr.getAnalysis<RelaxedLiveVariables>(D))
+      L->dumpStmtLiveness(Mgr.getSourceManager());
+  }
+};
+}
+
+void ento::registerLiveStatementsDumper(CheckerManager &mgr) {
+  mgr.registerChecker<LiveStatementsDumper>();
+}
+
+//===----------------------------------------------------------------------===//
 // CFGViewer
 //===----------------------------------------------------------------------===//
 
diff --git a/clang/test/Analysis/live-stmts.cpp b/clang/test/Analysis/live-stmts.cpp
new file mode 100644
index 000000000000..1b8a750c5e5c
--- /dev/null
+++ b/clang/test/Analysis/live-stmts.cpp
@@ -0,0 +1,167 @@
+// RUN: %clang_analyze_cc1 -w -analyzer-checker=debug.DumpLiveStmts %s 2>&1\
+// RUN:   | FileCheck %s
+
+int coin();
+
+
+int testThatDumperWorks(int x, int y, int z) {
+  return x ? y : z;
+}
+// CHECK: [ B0 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B1 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B2 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-NEXT: DeclRefExpr {{.*}} 'y' 'int'
+// CHECK-EMPTY:
+// CHECK-NEXT: DeclRefExpr {{.*}} 'z' 'int'
+// CHECK-EMPTY:
+// CHECK-NEXT: ImplicitCastExpr {{.*}} <IntegralToBoolean>
+// CHECK-NEXT: `-ImplicitCastExpr {{.*}} <LValueToRValue>
+// CHECK-NEXT:   `-DeclRefExpr {{.*}} 'x' 'int'
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B3 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-NEXT: DeclRefExpr {{.*}} 'y' 'int'
+// CHECK-EMPTY:
+// CHECK-NEXT: DeclRefExpr {{.*}} 'z' 'int'
+// CHECK-EMPTY:
+// CHECK-NEXT: ImplicitCastExpr {{.*}} <IntegralToBoolean>
+// CHECK-NEXT: `-ImplicitCastExpr {{.*}} <LValueToRValue>
+// CHECK-NEXT:   `-DeclRefExpr {{.*}} 'x' 'int'
+// CHECK: [ B4 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-NEXT: DeclRefExpr {{.*}} 'y' 'int'
+// CHECK-EMPTY:
+// CHECK-NEXT: DeclRefExpr {{.*}} 'z' 'int'
+// CHECK-EMPTY:
+// CHECK-NEXT: ImplicitCastExpr {{.*}} <IntegralToBoolean>
+// CHECK-NEXT: `-ImplicitCastExpr {{.*}} <LValueToRValue>
+// CHECK-NEXT:   `-DeclRefExpr {{.*}} 'x' 'int'
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B5 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-NEXT: DeclRefExpr {{.*}} 'y' 'int'
+// CHECK-EMPTY:
+// CHECK-NEXT: DeclRefExpr {{.*}} 'z' 'int'
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+
+
+void testIfBranchExpression(bool flag) {
+  // No expressions should be carried over from one block to another here.
+  while (flag) {
+    int e = 1;
+    if (true)
+      e;
+  }
+}
+// CHECK: [ B0 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B1 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B2 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B3 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B4 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B5 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+
+
+void testWhileBodyExpression(bool flag) {
+  // No expressions should be carried over from one block to another here.
+  while (flag) {
+    int e = 1;
+    while (coin())
+      e;
+  }
+}
+// CHECK: [ B0 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B1 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B2 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B3 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B4 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B5 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+
+
+void testDoWhileBodyExpression(bool flag) {
+  // No expressions should be carried over from one block to another here.
+  while (flag) {
+    int e = 1;
+    do
+      e;
+    while (coin());
+  }
+}
+// CHECK: [ B0 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B1 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B2 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B3 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B4 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B5 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+
+
+void testForBodyExpression(bool flag) {
+  // No expressions should be carried over from one block to another here.
+  while (flag) {
+    int e = 1;
+    for (; coin();)
+      e;
+  }
+}
+// CHECK: [ B0 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B1 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B2 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B3 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B4 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B5 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+
diff --git a/clang/test/Analysis/use-after-move.cpp b/clang/test/Analysis/use-after-move.cpp
index 18e1b3da6ab9..3bb52f164b46 100644
--- a/clang/test/Analysis/use-after-move.cpp
+++ b/clang/test/Analysis/use-after-move.cpp
@@ -778,6 +778,45 @@ void checkLoopZombies() {
   }
 }
 
+void checkMoreLoopZombies1(bool flag) {
+  while (flag) {
+    Empty e{};
+    if (true)
+      e; // expected-warning {{expression result unused}}
+    Empty f = std::move(e); // no-warning
+  }
+}
+
+bool coin();
+
+void checkMoreLoopZombies2(bool flag) {
+  while (flag) {
+    Empty e{};
+    while (coin())
+      e; // expected-warning {{expression result unused}}
+    Empty f = std::move(e); // no-warning
+  }
+}
+
+void checkMoreLoopZombies3(bool flag) {
+  while (flag) {
+    Empty e{};
+    do
+      e; // expected-warning {{expression result unused}}
+    while (coin());
+    Empty f = std::move(e); // no-warning
+  }
+}
+
+void checkMoreLoopZombies4(bool flag) {
+  while (flag) {
+    Empty e{};
+    for (; coin();)
+      e; // expected-warning {{expression result unused}}
+    Empty f = std::move(e); // no-warning
+  }
+}
+
 struct MoveOnlyWithDestructor {
   MoveOnlyWithDestructor();
   ~MoveOnlyWithDestructor();