[analyzer] Thoughts on Temporary Destructors

Background: recently Anna had to revert r189090 “Refactor conditional expression evaluating code”, which was added in order to handle temporary destructors that fire conditionally. The motivation for that commit was expressions like “(A() && B()) || (C() && D())”, where the destructors for B, C, and D only fire under certain conditions. In order to make sure these destructors only fire at the right times, Pavel structured the CFG so that the various terminator expressions (“A() && …”, “(A() && B()) || …”, etc.) would be used twice: first during normal expression evaluation, and then again during cleanup. This falls out of a long discussion on PR11645.

The problem was that before his commits, logical operators && and || were computed in the analyzer by walking back up the CFG to see how we got to this point. When we’re deciding whether to run destructors, the CFG blocks where the && or || values were computed is long gone. Pavel’s approach (which both Ted and I reviewed) was to (a) explicitly record whether an expression evaluated to true or false when used as a branch, and (b) keep the leaf expressions of && and || expression trees alive, so that the branch information could be recovered later on.

Unfortunately, two problems fell out of this: first, that in a loop it was possible to accidentally reuse a still-live expr value from the previous iteration, and second, that the GNU binary ?: operator uses the left-hand side as both a condition and a result. (Coincidentally, both of these bugs were reported to us at the same time based on one internal team getting a new Clang build.)

In discussing the first problem, Ted and Anna realized that the liveness information for nested && and || expressions was still incorrect: the outermost expression may potentially depend on all of the inner expressions, but that means that those sub-expressions are always considered live (since expressions are marked dead, in a reverse analysis, at the point of evaluation, and there are paths that don’t evaluate a particular sub-expression in a complex logical expression). This wasn’t an issue before because && and || didn’t actually use those expressions to compute their value, but it’s still incorrect.

Ted remarked that if we were more precisely modeling execution, we’d just have an extra bit on the side that got set to 1 if we needed to run a particular temporary’s destructor. We could do something similar in the CFG by inserting fake boolean variables and using those to decide whether or not to run destructors later; we’re not bound by the limits of the AST (on where variables can be inserted), and we already synthesize fake DeclStmts elsewhere (to break up a DeclStmt with multiple decls in it). I will admit we’ve had a handful of problems related to these fake decls in the past, but that doesn’t automatically invalidate the plan. We just haven’t explored it much, and I thought it was worth mentioning.

Anyway, clearly we’d like to properly evaluate temporary destructors, but just as clearly we don’t want to accept regressions in other parts of the analyzer, especially in pure C code or C++ code with cfg-temporary-dtors still turned off. So that’s where we are today.

Still interested in trying to solve these problems? :wink:
Jordan

Thanks for the overview. This is all pretty new to me, so I'm going to dig
into the problem for a couple of days and hopefully come up with some
intelligent questions.

Background: recently Anna had to revert r189090 "Refactor conditional
expression evaluating code", which was added in order to handle temporary
destructors that fire conditionally. The motivation for that commit was
expressions like "(A() && B()) || (C() && D())", where the destructors for
B, C, and D only fire under certain conditions. In order to make sure these
destructors only fire at the right times, Pavel structured the CFG so that
the various terminator expressions ("A() && ...", "(A() && B()) || ...",
etc.) would be used twice: first during normal expression evaluation, and
then again during cleanup. This falls out of a long discussion on PR11645<http://llvm.org/bugs/show_bug.cgi?id=11645&gt;
.

The problem was that before his commits, logical operators && and || were
computed in the analyzer by walking back up the CFG to see how we got to
this point. When we're deciding whether to run destructors, the CFG blocks
where the && or || values were computed is long gone. Pavel's approach
(which both Ted and I reviewed) was to (a) explicitly record whether an
expression evaluated to true or false when used as a branch, and (b) keep
the leaf expressions of && and || expression trees alive, so that the
branch information could be recovered later on.

Unfortunately, two problems fell out of this: first, that in a loop it was
possible to accidentally reuse a still-live expr value from the *previous*iteration, and second, that the GNU binary ?: operator uses the left-hand
side as both a condition and a result. (Coincidentally, both of these bugs
were reported to us at the same time based on one internal team getting a
new Clang build.)

In discussing the first problem, Ted and Anna realized that the liveness
information for nested && and || expressions was still incorrect: the
outermost expression may potentially depend on all of the inner
expressions, but that means that those sub-expressions are *always* considered
live (since expressions are marked dead, in a reverse analysis, at the
point of evaluation, and there are paths that don't evaluate a particular
sub-expression in a complex logical expression). This wasn't an issue
before because && and || didn't actually use those expressions to compute
their value, but it's still incorrect.

Is this http://llvm.org/bugs/show_bug.cgi?id=18159 ?

Ted remarked that if we were more precisely modeling execution, we'd just
have an extra bit on the side that got set to 1 if we needed to run a
particular temporary's destructor. We could do something similar in the CFG
by inserting fake boolean variables and using *those* to decide whether
or not to run destructors later; we're not bound by the limits of the AST
(on where variables can be inserted), and we already synthesize fake
DeclStmts elsewhere (to break up a DeclStmt with multiple decls in it). I
will admit we've had a handful of problems related to these fake decls in
the past, but that doesn't automatically invalidate the plan. We just
haven't explored it much, and I thought it was worth mentioning.

Cool. I'll look into this approach once I better understand what's going on.

Anyway, clearly we'd like to properly evaluate temporary destructors, but
just as clearly we don't want to accept regressions in other parts of the
analyzer, especially in pure C code or C++ code with cfg-temporary-dtors
still turned off. So that's where we are today.

Still interested in trying to solve these problems? :wink:

Definitely. I need something interesting to work on :slight_smile:

Jordan

(-pavel, who is no longer with Google)

Yes.

After digging into this for a couple of weeks across the 2013/2014 boundary, I now doubt that my 20% time will be enough to properly implement this support. Anybody who’s interested should feel free to work on this instead, as I’ll not be moving forward with it. Jordan, thanks for the pointers and the summary of the problem!

(cc: klimek@google.com, djasper@google.com)

As a bit of a follow-up, we are still very interested in getting this worked out, as it’s a significant barrier to the Analyzer’s usefulness. All of our C++ projects make extensive use of custom assertions. For example,

CHECK(condition) << “something happened with the hydrospanners”;

which logs a message and kills the program if the condition isn’t met. None of these custom assertions are pruning code paths due to the missing conditional expression support. For example, when building Chromium, the difference between running without and with the reverted patch is 1982 reported errors vs. 3210 reported errors. This number is a bit conservative, since we also have this problem in dependent libraries that don’t (but could) use analyzer_noreturn on their assertions; the real cost is that about 50% of all errors reported by the analyzer are false positives of this form.

So, given the 50% false positive rate for C++ code I’d be curious what regressions were there in C/Obj-C code that tip the scale towards reverting the patch rather than living with the regressions.

Thanks!
/Manuel

Ted, Jordan, Anna: ping.

This is really important for us - we love the analyzer, but without this patch, we basically cannot use it (apart from maintaining our own private fork, which we would rather not do, if at all possible). Every time somebody follows a code path that leads to an incorrect handling of temporary destructors, we loose a bunch of engineering time - might we be able to get this patch re-applied under a flag?

/Manuel

Ted, Jordan, Anna: ping.

This is really important for us - we love the analyzer, but without this
patch, we basically cannot use it (apart from maintaining our own private
fork, which we would rather not do, if at all possible). Every time
somebody follows a code path that leads to an incorrect handling of
temporary destructors, we loose a bunch of engineering time - might we be
able to get this patch re-applied under a flag?

I haven't at all looked at the actual patch or the false positives, but a
few questions come to mind:

My understanding is that this helps fix C++ quality, but regresses some
ObjC cases, yes?

If so, why don't we only do this when compiling C++ (and, maybe, ObjC++ - I
assume it helps more than it hurts there) - in that way we wouldn't regress
ObjC quality and wouldn't need a flag?

What are the specific ObjC regressions? Are they a matter of luck in the
current design, or intentional but the design that works for them is
inflexible to this enhancement? (this is a difficult question to explain -
but I'm kind of drawing an analogy from the LLVM optimization pipeline -
sometimes improving one optimization exposes flaws in another, through no
fault of the improvement. We still care about the overall regression and
work diligently to fix or revert, etc)

It isn’t just Objective-C code. Pavel’s patch revealed a hole in liveness tracking that meant impossible paths were getting reported, but only in very specific circumstances involving nested logical expressions. This can happen in any language mode. None of us have put in the time to do more than triage this and talk about possible solutions, which were in my original e-mail to Daniel. (The liveness issue is described in PR18159, and the original ||/&& discussion is PR11645. It’s entirely possible to come up with answers that don’t fix the liveness issue, too.)

If temporary destructor false positives are bad, how about a path that explicitly says “if (!x)” and then “if (x)”? That’s just not a trade worth making.

Jordan

So if I understand you correctly, you're saying that a path that says "if
(!x)" and then "if (x)" will be handled incorrectly with Pavel's patch?
My question about the option of putting it in under a flag / getting a
better idea about the type of regressions it causes comes from the
observation that when we included Pavel's patch the false positives went
drastically down (at least on our code bases).

Cheers,
/Manuel

That’s correct, for particular values of “x”.

You can still turn on temporary destructors with the cfg-temporary-dtors config option. I’m just not sure what will happen when there are logical expressions containing types with cleanups.

I am very much against putting something subtly wrong in ways we don’t fully understand back into the analyzer to get around a known issue with well-defined limitations, even if that known issue makes the analyzer unusable on a particular codebase of interest. I would be thrilled if someone found the time to (re-)solve the problem of cleanups within expressions with flow control, but to be fully up-front about this I don’t think Ted, Anna, or I will be able to dedicate time to this for the next few months.

On the other hand, if you can find someone like Daniel who is able to spend a good chunk of time working on this, I’ll try to be more available to answer questions and provide feedback, because you’re right: not having this feature means the analyzer can’t reliably be used on a whole class of codebases.

Jordan

Is it possible to have the same (similar) positive results just by teaching the analyzer about the custom assertions? If yes, I’d suggest you to use that as a patch on your private branch. Or you might consider teaching the TOT analyzer to accept a list of such assertions. This could be used in cases the source code cannot be annotated with ‘noreturn’.

As Jordan and Ted had mentioned, just reverting the patch results in unexpected behavior in both ObjC and C++.

See cfe/trunk/test/Analysis/live-variables.cpp for the C++ example. There, even though the dereference of 'p’ is guarded by ‘p != 0’, we reported a null pointer dereference.

Anna.

Is it possible to have the same (similar) positive results just by
teaching the analyzer about the custom assertions? If yes, I’d suggest you
to use that as a patch on your private branch. Or you might consider
teaching the TOT analyzer to accept a list of such assertions. This could
be used in cases the source code cannot be annotated with ‘noreturn'.

As Jordan and Ted had mentioned, just reverting the patch results in
unexpected behavior in both ObjC and C++.
See cfe/trunk/test/Analysis/live-variables.cpp for the C++ example. There,
even though the dereference of 'p’ is guarded by ‘p != 0’, we reported a
null pointer dereference.

Hi Anna,

thx for the tip; we'll basically evaluate each warning on its own (we want

90% true positive rate) and see how far we can get without needing to

patch, or which warnings the patch affects in which ways.

Cheers,
/Manuel