Page MenuHomePhabricator

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

Authored by NoQ on Dec 11 2018, 11:42 AM.

Details

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.

Diff Detail

Repository
rL LLVM

Event Timeline

NoQ created this revision.Dec 11 2018, 11:42 AM
NoQ updated this revision to Diff 177753.Dec 11 2018, 11:57 AM

Add documentation, fix checker help message.

Szelethus set the repository for this revision to rC Clang.Dec 11 2018, 2:34 PM

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 added a comment.Dec 16 2018, 2:59 PM

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 added a comment.Dec 16 2018, 3:01 PM

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

This revision was not accepted when it landed; it landed in state Needs Review.Dec 16 2018, 3:47 PM
This revision was automatically updated to reflect the committed changes.

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