In practice, APT is not faster to build than rdf.<div>The df calculator we use is linear time and quite fast.</div><div><br></div><div>Updating is also pretty trivial since it's only deletes of dead and unreachable code. So anything it reached can be replaced with undef in most cases.</div><div><br></div><div>Cd-dce is not slower in GCC than dce </div><div><br><div class="gmail_quote"><div dir="ltr">On Fri, Jan 29, 2016, 8:31 PM David Callahan <<a href="mailto:dcallahan@fb.com">dcallahan@fb.com</a>> wrote:<br></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>
<div style="color:rgb(0,0,0);font-family:Calibri,sans-serif;font-size:14px">
I think you can also avoid the RDF computation using a more directed form of control dependence testing such as described in </div>
<div style="color:rgb(0,0,0);font-family:Calibri,sans-serif;font-size:14px">
<br>
</div>
<div style="color:rgb(0,0,0);font-family:Calibri;font-size:14px"><font face="Calibri,sans-serif">Keshav Pingali and Gianfranco Bilardi. 1997. Optimal control dependence computation and the Roman chariots problem. ACM Trans. Program. Lang. Syst. 19,
3 (May 1997), 462-491. DOI=<a href="http://dx.doi.org/10.1145/256167.256217" target="_blank">http://dx.doi.org/10.1145/256167.256217</a> </font></div>
<div style="color:rgb(0,0,0);font-family:Calibri;font-size:14px"><font face="Calibri,sans-serif"><br>
</font></div>
<div><font face="Calibri,sans-serif"><font face="Calibri">However one challenge seems to be fixing the SSA graph after deleting essentially arbitrary connected regions of the control flow graph. It may be that </font>the<font face="Calibri"> common case where
deleted control flow has a single entry and a common post-dominator which seems straight forward but in the general case it seems much harder. Any prior experience on that problem?</font></font></div>
</div>
<div><font face="Calibri,sans-serif"><font face="Calibri">david</font></font></div>
<div style="color:rgb(0,0,0);font-family:Calibri,sans-serif;font-size:14px">
<br>
</div>
<span style="color:rgb(0,0,0);font-family:Calibri,sans-serif;font-size:14px">
<div style="font-family:Calibri;font-size:11pt;text-align:left;color:black;BORDER-BOTTOM:medium none;BORDER-LEFT:medium none;PADDING-BOTTOM:0in;PADDING-LEFT:0in;PADDING-RIGHT:0in;BORDER-TOP:#b5c4df 1pt solid;BORDER-RIGHT:medium none;PADDING-TOP:3pt">
<span style="font-weight:bold">From: </span>Hal Finkel <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>><br>
<span style="font-weight:bold">Date: </span>Friday, January 29, 2016 at 4:50 PM<br>
<span style="font-weight:bold">To: </span>Daniel Berlin <<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>></div></span></div><div style="word-wrap:break-word"><span style="color:rgb(0,0,0);font-family:Calibri,sans-serif;font-size:14px"><div style="font-family:Calibri;font-size:11pt;text-align:left;color:black;BORDER-BOTTOM:medium none;BORDER-LEFT:medium none;PADDING-BOTTOM:0in;PADDING-LEFT:0in;PADDING-RIGHT:0in;BORDER-TOP:#b5c4df 1pt solid;BORDER-RIGHT:medium none;PADDING-TOP:3pt"><br>
<span style="font-weight:bold">Cc: </span>LLVM Dev Mailing list <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>>, David Callahan <<a href="mailto:dcallahan@fb.com" target="_blank">dcallahan@fb.com</a>><br>
</div></span></div><div style="word-wrap:break-word"><span style="color:rgb(0,0,0);font-family:Calibri,sans-serif;font-size:14px"><div style="font-family:Calibri;font-size:11pt;text-align:left;color:black;BORDER-BOTTOM:medium none;BORDER-LEFT:medium none;PADDING-BOTTOM:0in;PADDING-LEFT:0in;PADDING-RIGHT:0in;BORDER-TOP:#b5c4df 1pt solid;BORDER-RIGHT:medium none;PADDING-TOP:3pt"><span style="font-weight:bold">Subject: </span>Re: [llvm-dev] DCE in the presence of control flow.<br>
</div></span></div><div style="word-wrap:break-word"><span style="color:rgb(0,0,0);font-family:Calibri,sans-serif;font-size:14px">
<div><br>
</div>
<div>
<div>
<div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:#000000">
<br>
<br>
<hr>
<blockquote style="border-left:2px solid rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt">
<b>From: </b>"Daniel Berlin" <<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>><br>
<b>To: </b>"Hal Finkel" <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>><br>
<b>Cc: </b>"LLVM Dev Mailing list" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>>, "David Callahan" <<a href="mailto:dcallahan@fb.com" target="_blank">dcallahan@fb.com</a>><br>
<b>Sent: </b>Friday, January 29, 2016 12:48:37 AM<br>
<b>Subject: </b>Re: [llvm-dev] DCE in the presence of control flow.<br>
<br>
<div dir="ltr"><br>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Thu, Jan 28, 2016 at 10:09 PM, Hal Finkel <span dir="ltr">
<<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div>
<div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:rgb(0,0,0)">
<br>
<hr>
<blockquote style="border-left:2px solid rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt">
<b>From: </b>"David Callahan via llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>><br>
<b>To: </b>"Daniel Berlin" <<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>>, "LLVM Dev Mailing list" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>><br>
<b>Sent: </b>Thursday, January 28, 2016 11:35:49 PM<span><br>
<b>Subject: </b>Re: [llvm-dev] DCE in the presence of control flow.<br>
<br>
<div>Thanks</div>
<div>Also I found that some cases are also caught by a specialized routine to remove dead loops which is missing the case I noticed.</div>
<div>odavd</div>
<div><br>
</div>
<span>
<div style="font-family:Calibri;font-size:11pt;text-align:left;color:black;border-width:1pt medium medium;border-style:solid none none;padding:3pt 0in 0in">
<span style="font-weight:bold">From: </span>Daniel Berlin <<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>><br>
<span style="font-weight:bold">Date: </span>Thursday, January 28, 2016 at 8:45 PM<br>
<span style="font-weight:bold">To: </span>David Callahan <<a href="mailto:dcallahan@fb.com" target="_blank">dcallahan@fb.com</a>>, LLVM Dev Mailing list <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>><br>
<span style="font-weight:bold">Subject: </span>Re: [llvm-dev] DCE in the presence of control flow.<br>
</div>
<div><br>
</div>
<div>
<div>The post dominators computation costs more on llvm than GCC because of how the respective cfgs work under the covers. Even for GCC, when we implemented cd-dce, it only catches 1-2% more cases. It's not really worth the cost in llvm unless postdom comes
free </div>
</div>
</span></span></blockquote>
<br>
A 1-2% reduction in code size seems like it might well be worth a post-dom calculation.</div>
</div>
</blockquote>
<div><br>
</div>
<div>1-2% more cases != 1-2% reduction in code size. In particular, it assumes nothing else will catch those cases :)</div>
</div>
</div>
</div>
</blockquote>
Fair enough.<br>
<blockquote style="border-left:2px solid rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div></div>
<div> </div>
<div>The cases are mostly caught by SimplifyCFG/etc anyway<br>
</div>
<div><br>
</div>
<div>In any case, here are the numbers from when it was turned on by default:</div>
<div><br>
</div>
<div><a href="https://gcc.gnu.org/ml/gcc-patches/2004-01/msg00675.html" target="_blank">https://gcc.gnu.org/ml/gcc-patches/2004-01/msg00675.html</a><br>
</div>
<div><br>
</div>
<div>Note: GCC is at least 3x faster at computing post-dom than LLVM</div>
</div>
</div>
</div>
</blockquote>
Why?<br>
<blockquote style="border-left:2px solid rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div></div>
<div><br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div>
<div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:rgb(0,0,0)">
Also, what exactly is the algorithm using post-dom info?<br>
<br>
</div>
</div>
</blockquote>
<div><br>
</div>
<div>So, to review for a second, right now, the algorithm answers the question when is a branch necessary with "always" :)<br>
</div>
<div><br>
</div>
<div>The real answer is "when an already-necessary operation depends on its existence". This is of course, requires control-dependence to answer.</div>
<div>So if you take our current DCE algorithm, and instead of marking terminators always-live, it simply marks control dependent edges of those operands as necessary, and branches that generate those edges.</div>
<div><br>
</div>
<div>(IE </div>
<div><br>
</div>
<div>for each block in RDF(useful block):<br>
mark terminator of block as useful</div>
<div><br>
</div>
</div>
</div>
</div>
</blockquote>
<br>
FWIW, Keith Cooper's slide deck on this has a nice explanation: <a href="https://www.cs.rice.edu/~keith/512/2011/Lectures/L04Dead-1up.pdf" target="_blank">
https://www.cs.rice.edu/~keith/512/2011/Lectures/L04Dead-1up.pdf</a><br>
<br>
We might be able to do this without precomputing an RDF, however. For example, you could solve a data-flow problem on the reverse CFG, where for each block you solve for the "next" live instruction. Then a branch is alive only if the next live instruction for
each successor is different. You'd need to have "next-live-instruction phi nodes" for cases where there's not a unique answer, etc.<br>
<br>
Thanks again,<br>
Hal<br>
<blockquote style="border-left:2px solid rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div></div>
<div><br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div>
<div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:rgb(0,0,0)">
I suppose that we're looking for cases where we have a CFG diamond with one having only dead instructions, and loops with all dead instructions, etc.</div>
</div>
</blockquote>
<div><br>
Yes. Loops with all dead instructions includes "loops with no side-effects outside of the loop" </div>
<div> </div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div>
<div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:rgb(0,0,0)">
<span style="font-family:arial,sans-serif;font-size:small;color:rgb(34,34,34)"> </span><br>
</div>
</div>
</blockquote>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div>
<div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:rgb(0,0,0)">
Thanks again,<br>
Hal<span><br>
<blockquote style="border-left:2px solid rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt">
<span>
<div>
<div>
<div><br>
<div class="gmail_quote">
<div dir="ltr">On Wed, Jan 27, 2016, 1:56 PM David Callahan via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div style="word-wrap:break-word;color:rgb(0,0,0);font-size:14px;font-family:Calibri,sans-serif">
<div>
<p class="MsoNormal">I have been looking at some internal codes looking for differences between Clang (specifically 3.7.1) and gcc (typically 4.8.1 but sometimes later).<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">One area where I bumped into was dead code elimination in the presence of complex control flow. I note that the “aggressive dead code elimination” (ADCE.cpp) treats all branch operations as live (<span style="font-size:10pt;font-family:Consolas">isa<TerminatorInst>(I)).
</span>Doing more requires some approximation to control dependence.<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">I note SimplifyCFG indirectly handles some simple cases. It will speculate the contents of a basic block into a predecessor but this is insufficient for more complex structures. This probably cherry-picks the most common cases by frequency.<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">Have their been prior attempts strengthen dead code elimination w.r.t. control flow? If so, any guidance on what went wrong?<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">Thanks<u></u><u></u></p>
<p class="MsoNormal">David<u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:10pt;font-family:Consolas"> </span></p>
</div>
</div>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="https://urldefense.proofpoint.com/v2/url?u=http-3A__lists.llvm.org_cgi-2Dbin_mailman_listinfo_llvm-2Ddev&d=CwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=lFyiPUrFdOHdaobP7i4hoA&m=pCcZikgFQttaHaETuHc6G00dgArj_Spf58imKkXlTqk&s=NTh5Q1gE2ANS1rQYN9XFok_t8wvWCu1dzzzvHfv3hlI&e=" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote>
</div>
</div>
</div>
</div>
</span><br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="https://urldefense.proofpoint.com/v2/url?u=http-3A__lists.llvm.org_cgi-2Dbin_mailman_listinfo_llvm-2Ddev&d=CwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=lFyiPUrFdOHdaobP7i4hoA&m=7nHK35pXeFc5plcmZyxIPJwB8O8ZyHCJ4P89mN8BoZQ&s=BIA3X52dktMwTkOdClno4EdVyZHbON1Yd_OB0ZehhB0&e=" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote>
<br>
<br>
<br>
</span><span>-- <br>
<div><span></span>Hal Finkel<br>
Assistant Computational Scientist<br>
Leadership Computing Facility<br>
Argonne National Laboratory<span></span><br>
</div>
</span></div>
</div>
</blockquote>
</div>
<br>
</div>
</div>
</blockquote>
<br>
<br>
<br>
-- <br>
<div><span name="x"></span>Hal Finkel<br>
Assistant Computational Scientist<br>
Leadership Computing Facility<br>
Argonne National Laboratory<span name="x"></span><br>
</div>
</div>
</div>
</div>
</span></div></blockquote></div></div>