<div dir="ltr">[moving to cfe-dev, it seems like a more appropriate place]<br><div class="gmail_extra"><br><br><div class="gmail_quote">On 26 July 2013 02:19, Jordan Rose <span dir="ltr"><<a href="mailto:jordan_rose@apple.com" target="_blank">jordan_rose@apple.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><div><div class="h5"><br><div><div><span style="color:rgb(34,34,34)">Yeah...about that. Unfortunately, the paths for "A() || B()" don't actually look like what you wrote above; it's something more like this:</span><br>
</div></div></div></div><div><br></div><div><span style="font-family:Courier">    |</span></div><div><font face="Courier">   A()</font></div><div><font face="Courier">   / \</font></div><div><font face="Courier">  /   \</font></div>
<div><font face="Courier">  |  B()</font></div><div><font face="Courier">  |   |</font></div><div><font face="Courier">  |  ~B()</font></div><div><font face="Courier">  \   /</font></div><div><font face="Courier">   \ /</font></div>
<div><font face="Courier">   ~A()</font></div><div><font face="Courier">    |</font></div><div><font face="Courier"><br></font></div><div>...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.</div>
<div><br></div><div>(A() || (B() && C() && D()) || E())</div><div>could require</div><div>~A()</div><div>~A(), ~B(), ~C(), ~D()</div><div>~A(), ~B(), ~E()</div><div>~A(), ~B(), ~C(), ~E()</div><div>~A(), ~B(), ~C(), ~D(), ~E()</div>
<div><br></div><div>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 <a href="http://llvm.org/bugs/show_bug.cgi?id=11645" target="_blank">PR11645</a>, which I didn't realize wasn't yet concluded.</div>
</div></blockquote><div>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.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><div><br></div><div>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.</div>
<div><br></div><div>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.</div><span class="HOEnZb"><font color="#888888"><div><br></div>
<div>Jordan</div></font></span></div></blockquote></div><br></div><div class="gmail_extra">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.</div>
<div class="gmail_extra"><br></div><div class="gmail_extra">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.</div>
<div class="gmail_extra"><br></div><div class="gmail_extra">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.</div>
<div class="gmail_extra"><br></div><div class="gmail_extra">What do you think about this idea?</div><div class="gmail_extra">pavel<br></div><div class="gmail_extra"><br></div><div class="gmail_extra">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.</div>
</div>