[analyzer][Liveness][RFC][NFC] Propose to turn statement liveness into expression liveness

[Szelethus]

Summary

I had a bit of fun with the tags.

Liveness analysis calculates the set of live/dead values in the program. However, statements don't always have a value associated with them, expressions do. For this reason, I found it puzzling why LivenessAnalysis work with "live statements", or answers questions such as "is this statement live". After a bit of digging, I found that the only client of statement liveness is EnvironmentManager::removeDeadBindings (the one modified in this patch), and the only non-expression statement it queries are ObjCForCollectionStmts, but no lit tests crashed on the added asserts.

This patch isn't necesserily intended to be committed -- it more of a request for comments whether it would be safe to change statement liveness to strictly expression liveness. It would be great, because my ultimate goal is to merge the implementation of UninitializedVariable and LivenessAnalaysis, and add Reaching Definitions under the same hood, but the statement liveness was very much out of place and makes the merge very awkward, if even possible.

I have a number of changes planned, but I didn't want to go too far ahead of myself, in case I missed something fundamental that justifies statement liveness as it is.

[NoQ]

I think you're right, this entire thing only makes sense for expressions. I think Environment occasionally carries values of ReturnStmts (by which it means values of their sub-expressions) but even then liveness analysis doesn't need to be aware of that flex.

no lit tests crashed on the added asserts

the only non-expression statement it queries are ObjCForCollectionStmts

Wait, how did you figure that out if not through crashing tests?

[Szelethus]

clang/lib/StaticAnalyzer/Core/Environment.cpp

193

In D82122#2103638, @NoQ wrote:

I think you're right, this entire thing only makes sense for expressions. I think Environment occasionally carries values of ReturnStmts (by which it means values of their sub-expressions) but even then liveness analysis doesn't need to be aware of that flex.

no lit tests crashed on the added asserts

the only non-expression statement it queries are ObjCForCollectionStmts

Wait, how did you figure that out if not through crashing tests?

if (IsBlkExprLive && !isa<Expr>(BlkExpr.getStmt()) {
  BlkExpr.getStmt()->dump();
  llvm_unreachable("Gotcha!");
}

[Szelethus]

Cheers! I'll leave this here for conversation's sake, and start working on refactoring LivenessAnalysis.

[Szelethus]

This revision has done its job.

[Szelethus]

This was accidentally committed as a part of rGb6cbe6cb0399d4671e5384dcc326af56bc6bd122.

clang/lib/StaticAnalyzer/Core/Environment.cpp

EnvironmentManager::removeDeadBindings(Environment Env,
   MarkLiveCallback CB(SymReaper);
   ScanReachableSymbols RSScaner(ST, CB);
 
   llvm::ImmutableMapRef<EnvironmentEntry, SVal>
     EBMapRef(NewEnv.ExprBindings.getRootWithoutRetain(),
              F.getTreeFactory());
 
   // Iterate over the block-expr bindings.
-  for (Environment::iterator I = Env.begin(), E = Env.end();
-       I != E; ++I) {
+  for (Environment::iterator I = Env.begin(), E = Env.end(); I != E; ++I) {
     const EnvironmentEntry &BlkExpr = I.getKey();
     const SVal &X = I.getData();
 
-    if (SymReaper.isLive(BlkExpr.getStmt(), BlkExpr.getLocationContext())) {
+    const bool IsBlkExprLive =
+        SymReaper.isLive(BlkExpr.getStmt(), BlkExpr.getLocationContext());
+
+    assert((isa<Expr>(BlkExpr.getStmt()) || !IsBlkExprLive) &&
+           "Only Exprs can be live, LivenessAnalysis argues about the liveness "
+           "of *values*!");
+
+    if (IsBlkExprLive) {
       // Copy the binding to the new map.
       EBMapRef = EBMapRef.add(BlkExpr, X);
 
       // Mark all symbols in the block expr's value live.
       RSScaner.scan(X);
     }
   }