[cfe-dev] Destructors of temporaries and conditional expressions [was: Re: r186925 - Revert "[analyzer] Add very limited support for temporary destructors"]

[Pavel Labath]

[moving to cfe-dev, it seems like a more appropriate place]


On 26 July 2013 02:19, Jordan Rose <jordan_rose at apple.com> wrote:

>
> Yeah...about that. Unfortunately, the paths for "A() || B()" don't
> actually look like what you wrote above; it's something more like this:
>
>     |
>    A()
>    / \
>   /   \
>   |  B()
>   |   |
>   |  ~B()
>   \   /
>    \ /
>    ~A()
>     |
>
> ...and that's just to evaluate the condition; we still have to branch
> after that. And notice how this gets worse the more you stack logical
> expressions, because you may or may not have to evaluate destructors based
> on other parts of the condition.
>
> (A() || (B() && C() && D()) || E())
> could require
> ~A()
> ~A(), ~B(), ~C(), ~D()
> ~A(), ~B(), ~E()
> ~A(), ~B(), ~C(), ~E()
> ~A(), ~B(), ~C(), ~D(), ~E()
>
> So the current strategy, which works fine for libAnalysis, is just to run
> through all the conditions again, which is at least linear, rather than try
> to be clever about joining up blocks ahead of time. The discussion that led
> to this is in PR11645 <http://llvm.org/bugs/show_bug.cgi?id=11645>, which
> I didn't realize wasn't yet concluded.
>
You are right, of course. I was misled by the simple example I was looking
at. Now I see that the graph can get exponential if I really wanted to
capture all possible control flow paths explicitly. So i think I'll just
leave the CFG alone :). I'll try to go down the
modifying-the-liveness-algorithm path.


>
> The current liveness algorithm lives in LiveVariables.cpp (despite the
> name it includes liveness info for statements and expressions as well). In
> most cases, an expression is only live when it's about to be consumed,
> which is the problem here. We don't want logical operators to be alive
> forever, but we'd need them all to be alive until we get a chance to run
> all of the destructors for that full-expression.
>
> I don't have any ideas yet on this, but I'll keep it in the back of my
> head for a while, and let you know if I think of anything.
>
> Jordan
>

If I understood the algorithm correctly, it tries to do a backwards
traversal of the CFG, marking individual subexpressions as alive when they
are consumed and as dead when they are produced (doing unions when code
paths merge, etc.). With this design I don't think it's a problem if an
expression can be consumed twice: it will just get marked as "live" at the
first consumption point (when looking backwards), stay "live" when
processing the second one and be removed from the live set when we reach
the expression.

The reason (at least one of them) this does not work right now is that the
liveness map uses Stmt* to identify code locations (LiveVariables.cpp:201).
This can be a problem because with temporary destructors we go through the
same Stmt* twice, but in a different location in the CFG. This can create
some problems in the internal logic, so I propose to refactor the class to
use CFGElement* as a location key. I think it's a better choice, since it
(by definition) uniquely identifies a location in the CFG, and it is a step
towards solving the temporary destructor problem.

After this is done, it should be easy to modify the conditional expression
handling code in the analyzer (ResolveCondition, ExprEngine::processBranch)
to work with the new setup, possibly by simply adding a "if we already have
a computed value in the environment, then use the value" check.

What do you think about this idea?
pavel

PS: when I spoke about this liveness extension idea with chandler (cc'ed),
he suggested to avoid doing a full pass over the CFG, as he felt it would
be too slow. Instead, he proposed to compute the liveness in parallel to
the CFG construction. However, as I now see that the analyzer is doing the
pass anyway, I think I'll postpone that idea for now, since it should be
much easier to integrate with the existing framework. If we later determine
that we need more speed, we can think about how to rewrite the whole thing
to work alongside CFG construction.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20130801/799a6610/attachment.html>