[analyzer] LiveVariables: Fix a zombie expression problem, add testing infrastructure.

[NoQ]

Summary

For the first time in years, there seems to be a bug in our "live variables" analysis, which is an auxiliary data flow analysis that decides which variables and expressions are live, so that we could collect dead symbols, clean up the program state, and, ultimately, find memory leaks.

The bug shows up on the move-checker, as demonstrated on attached tests (except the do-while test, which worked fine, but i added it to make sure it stays that way). It was originally hidden by D54372 and seems to have been another reason why the hack that was removed in D54372 was introduced in the first place.

Consider checkMoreLoopZombies1() (other tests are similar). LiveVariables analysis reports that expression e that constitutes the true-branch of if is live throughout almost the whole body of the loop (!), namely, until the beginning of if (true) "on the next iteration" (quotes because it doesn't really make sense for live variables analysis, but kinda makes sense for us to think of it this way). There's a brief period when it doesn't live, but it quickly becomes live again. The expression, being an lvalue, evaluates to the VarRegion for variable e. This means that at least one of the two - the variable e itself and the expression that evaluates to the region e - is always live, and region e never becomes dead, and the moved-from state never gets cleaned up, which leads to an invalid use-after-move report on the second iteration of the loop.

Expressions don't need to be live after the first statement that contains them is evaluated. So the liveness analysis was overly conservative in this case, and it caused problems for a checker that relies on values being cleaned up perfectly.

It was essential that the expression e appears directly as a sub-statement of if, i.e. written without {...}. Otherwise the compound statement would have been marked as live instead, which is kinda fine, even if it doesn't make sense.

Because of that, when the if-statement is being evaluated as a terminator, the generic code that works for pretty much all statements was marking the expression as live:

for (Stmt *Child : S->children()) {
  if (Child)
    AddLiveStmt(val.liveStmts, LV.SSetFact, Child);

This caused e to be incorrectly marked as live at the end of block that terminates at if (true), which is propagated to the beginning of that block (similarly to how in x ? y : z expressions y and z need to live at operator x ?, so that the operator could have been evaluated), which is then propagated to the while-loop terminator.

This is fixed by specializing the generic case for these control flow operators to avoid the unnecessary propagation of non-compound-statement branch liveness.

---

Because i wanted to add more direct tests for this stuff (as we had none), i had to introduce a new debug checker to dump statement liveness: debug.DumpLiveStmts. Dumps should be human-readable and testable.

These direct tests indicate that the same incorrect behavior does indeed occur in the do-while loop case, even if it doesn't have much consequences for the move-checker.

---

I'll add more tests if i notice that this change increases the number of leaks Static Analyzer finds.

[NoQ]

Add documentation, fix checker help message.

[Szelethus]

Makes sense! I like the summary a lot, and the fact that you added a new debug checker. I feel like I'm not yet qualified to give meaningful feedback though, but if you are not in a hurry, I'll happily play around with this patch next week, and both learn a bit and possibly give a better review.

But looking at it right now, this looks great.

[NoQ]

Tested it a little bit. It causes an extremely slight skew in warnings. I'll reduce a few of them to see if this is mostly just budgets reached earlier or later, or these are sensible improvements/regressions, but generally this looks pretty safe, so i'll try to commit.

[NoQ]

@Szelethus: i'm very happy that someone's reading this :)

[dcoughlin]

This looks good to me. It is great to see a dumper for this!

cfe/trunk/docs/analyzer/DebugChecks.rst

- debug.DumpCFG, debug.ViewCFG: Show the CFG generated for each top-level
   function being analyzed.
 
 - debug.DumpDominators: Shows the dominance tree for the CFG of each top-level
   function.
 
 - 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
 =============
 
 These checkers print information about the path taken by the analyzer engine.
 
 - debug.DumpCalls: Prints out every function or method call encountered during a

cfe/trunk/include/clang/Analysis/Analyses/LiveVariables.h

public:
   ///  has been recorded at the statement level (see runOnAllBlocks), and
   ///  only returns liveness information for block-level expressions.
   bool isLive(const Stmt *S, const VarDecl *D);
 
   /// Returns true the block-level expression "value" is live
   ///  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);
 
   static LiveVariables *create(AnalysisDeclContext &analysisContext) {
     return computeLiveness(analysisContext, true);
   }
 
   static const void *getTag();
 

cfe/trunk/include/clang/StaticAnalyzer/Checkers/Checkers.td

def AnalysisOrderChecker : Checker<"AnalysisOrder">,
   HelpText<"Print callbacks that are called during analysis in order">;
 
 def DominatorsTreeDumper : Checker<"DumpDominators">,
   HelpText<"Print the dominance tree for a given CFG">;
 
 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">;
 
 def CFGDumper : Checker<"DumpCFG">,
   HelpText<"Display Control-Flow Graphs">;
 
 def CallGraphViewer : Checker<"ViewCallGraph">,
   HelpText<"View Call Graph using GraphViz">;

cfe/trunk/lib/Analysis/LiveVariables.cpp

public:
   merge(LiveVariables::LivenessValues valsA,
         LiveVariables::LivenessValues valsB);
 
   LiveVariables::LivenessValues
   runOnBlock(const CFGBlock *block, LiveVariables::LivenessValues val,
              LiveVariables::Observer *obs = nullptr);
 
   void dumpBlockLiveness(const SourceManager& M);
+  void dumpStmtLiveness(const SourceManager& M);
 
   LiveVariablesImpl(AnalysisDeclContext &ac, bool KillAtAssign)
     : analysisContext(ac),
       SSetFact(false), // Do not canonicalize ImmutableSets by default.
       DSetFact(false), // This is a *major* performance win.
       BSetFact(false),
       killAtAssign(KillAtAssign) {}
 };
switch (S->getStmtClass()) {
     case Stmt::CXXBindTemporaryExprClass: {
       S = cast<CXXBindTemporaryExpr>(S)->getSubExpr();
       break;
     }
     case Stmt::UnaryExprOrTypeTraitExprClass: {
       // 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()) {
     if (Child)
       AddLiveStmt(val.liveStmts, LV.SSetFact, Child);
   }
 }
 
for (std::vector<const VarDecl*>::iterator di = declVec.begin(),
                    << " <";
       (*di)->getLocation().print(llvm::errs(), M);
       llvm::errs() << ">\n";
     }
   }
   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; }

cfe/trunk/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp

 };
 }
 
 void ento::registerLiveVariablesDumper(CheckerManager &mgr) {
   mgr.registerChecker<LiveVariablesDumper>();
 }
 
 //===----------------------------------------------------------------------===//
+// 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
 //===----------------------------------------------------------------------===//
 
 namespace {
 class CFGViewer : public Checker<check::ASTCodeBody> {
 public:
   void checkASTCodeBody(const Decl *D, AnalysisManager& mgr,
                         BugReporter &BR) const {

cfe/trunk/test/Analysis/live-stmts.cpp

+// 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:
+

cfe/trunk/test/Analysis/use-after-move.cpp

 
 void checkLoopZombies() {
   while (true) {
     Empty e{};
     Empty f = std::move(e); // no-warning
   }
 }
 
+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();
   MoveOnlyWithDestructor(const MoveOnlyWithDestructor &m) = delete;
   MoveOnlyWithDestructor(MoveOnlyWithDestructor &&m);
 };
 
 MoveOnlyWithDestructor foo() {