<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Jan 30, 2016 at 7:59 AM, David Callahan <span dir="ltr"><<a href="mailto:dcallahan@fb.com" target="_blank">dcallahan@fb.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;color:rgb(0,0,0);font-size:14px;font-family:Calibri,sans-serif">
<div>Maybe I was too quick here. Does gcc record the incoming edge to a phi? </div></div></blockquote><div><br></div><div>Yes, it must, as mentioned, phi nodes have both data and control dependences.</div><div><br></div><div><br></div><div>imagine the following pseudocode:</div><div><br></div><div>if (a)</div><div>;; {block 1}</div><div>else</div><div>;; {block 2}</div><div>c = phi(7 ( block 1), 9 (block 2))<br></div><div><br></div><div>Without the control dependence, you have no idea which value to pick.</div><div> <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;color:rgb(0,0,0);font-size:14px;font-family:Calibri,sans-serif"><div>If so, won’t those change when you delete blocks in a non-trivial manner? </div></div></blockquote><div><br></div><div>They will not. You are guaranteed that the edge will stay live if the phi node is live, because you will mark the control dependent edges on the predecessor block as necessary, and then go and mark the branch instructions that generate those edges as necessary.</div><div><br></div><div>As such, you are guaranteed the incoming edge will not change, because you will have marked them live.</div><div><br></div><div>Even if we lived in a compiler where we could not easily delete dead branches, it's easier to leave unreachable control flow/blocks around.</div><div><br></div><div>That is trivial:</div><div><br></div><div>For each dead branch, connect it to the nearest necessary post dominator of it's old target.</div><div><br></div><div><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;color:rgb(0,0,0);font-size:14px;font-family:Calibri,sans-serif"><div>How are those updated?</div>
<div><br>
</div>
<span>
<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>David Callahan <<a href="mailto:dcallahan@fb.com" target="_blank">dcallahan@fb.com</a>><br>
<span style="font-weight:bold">Date: </span>Saturday, January 30, 2016 at 7:02 AM<br>
<span style="font-weight:bold">To: </span>Daniel Berlin <<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>>, Hal Finkel <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>><div><div class="h5"><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>><br>
<span style="font-weight:bold">Subject: </span>Re: [llvm-dev] DCE in the presence of control flow.<br>
</div></div></div><div><div class="h5">
<div><br>
</div>
<div>
<div style="word-wrap:break-word;color:rgb(0,0,0);font-size:14px;font-family:Calibri,sans-serif">
<div>I had assumed you would treat phi nodes differently from other operations in that they don’t need to keep the block alive just to retain the data flow facts but it would be simplest to do that.</div>
<div>Thanks Daniel</div>
<div><br>
</div>
<span>
<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>Daniel Berlin <<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>><br>
<span style="font-weight:bold">Date: </span>Friday, January 29, 2016 at 10:26 PM<br>
<span style="font-weight:bold">To: </span>David Callahan <<a href="mailto:dcallahan@fb.com" target="_blank">dcallahan@fb.com</a>>, Hal Finkel <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>><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>><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>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" target="_blank">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="https://urldefense.proofpoint.com/v2/url?u=http-3A__dx.doi.org_10.1145_256167.256217&d=CwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=lFyiPUrFdOHdaobP7i4hoA&m=85DfLWatM6urqzYLUvrWBgn5LKUxCbQ3YheI3kh5XdU&s=qJbIjqiOKcfzbhZ33-9K0SGsouUl_rvtRgEareBdqGY&e=" 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://urldefense.proofpoint.com/v2/url?u=https-3A__www.cs.rice.edu_-7Ekeith_512_2011_Lectures_L04Dead-2D1up.pdf&d=CwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=lFyiPUrFdOHdaobP7i4hoA&m=85DfLWatM6urqzYLUvrWBgn5LKUxCbQ3YheI3kh5XdU&s=C3xP_URm9hGCDdAsg-pKQsJ6sWhEVYgyYAGKbhC6ENU&e=" 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>
</div>
</div>
</span></div>
</div>
</div></div></span>
</div>
</blockquote></div><br></div></div>