<html><head><meta http-equiv="Content-Type" content="text/html charset=windows-1252"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Jan 29, 2016, at 8:31 PM, David Callahan via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><div style="font-family: Calibri, sans-serif; font-size: 14px;" class="">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="font-family: Calibri, sans-serif; font-size: 14px;" class=""><br class=""></div><div style="font-family: Calibri; font-size: 14px;" class=""><font face="Calibri,sans-serif" class="">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" class="">http://dx.doi.org/10.1145/256167.256217</a> </font></div><div style="font-family: Calibri; font-size: 14px;" class=""><font face="Calibri,sans-serif" class=""><br class=""></font></div><div class=""><font face="Calibri,sans-serif" class=""><font face="Calibri" class="">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" class=""> 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 style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><font face="Calibri,sans-serif" class=""><font face="Calibri" class="">david</font></font></div></div></blockquote><div><br class=""></div><div>Hi David,</div><div><br class=""></div><div>You may want to consider looking at the implementation of DCE in the Swift optimizer. It should be fairly straightforward to follow despite not being LLVM IR.</div><div><br class=""></div><div>I implemented something inspired by the above paper, but it does not implement the full construction of the sets mentioned in the paper. Instead it precomputes some information to attempt to do a limited walk of the post-dominator tree. I think it has worked well in practice.</div><div><br class=""></div><div>The code for the precomputation portion starts here: <a href="https://github.com/apple/swift/blob/master/lib/SILOptimizer/Transforms/DeadCodeElimination.cpp#L502" class="">https://github.com/apple/swift/blob/master/lib/SILOptimizer/Transforms/DeadCodeElimination.cpp#L502</a></div><div><br class=""></div><div>Feel free to ping me off list if you have any questions about it.</div><div><br class=""></div><div>Mark</div><div><br class=""></div><br class=""><blockquote type="cite" class=""><div class=""><div style="font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; font-family: Calibri, sans-serif; font-size: 14px;" class=""><br class=""></div><span id="OLK_SRC_BODY_SECTION" style="font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; font-family: Calibri, sans-serif; font-size: 14px;" class=""><div style="font-family: Calibri; font-size: 11pt; text-align: left; border-width: 1pt medium medium; border-style: solid none none; padding: 3pt 0in 0in; border-top-color: rgb(181, 196, 223);" class=""><span style="font-weight: bold;" class="">From:<span class="Apple-converted-space"> </span></span>Hal Finkel <<a href="mailto:hfinkel@anl.gov" class="">hfinkel@anl.gov</a>><br class=""><span style="font-weight: bold;" class="">Date:<span class="Apple-converted-space"> </span></span>Friday, January 29, 2016 at 4:50 PM<br class=""><span style="font-weight: bold;" class="">To:<span class="Apple-converted-space"> </span></span>Daniel Berlin <<a href="mailto:dberlin@dberlin.org" class="">dberlin@dberlin.org</a>><br class=""><span style="font-weight: bold;" class="">Cc:<span class="Apple-converted-space"> </span></span>LLVM Dev Mailing list <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>>, David Callahan <<a href="mailto:dcallahan@fb.com" class="">dcallahan@fb.com</a>><br class=""><span style="font-weight: bold;" class="">Subject:<span class="Apple-converted-space"> </span></span>Re: [llvm-dev] DCE in the presence of control flow.<br class=""></div><div class=""><br class=""></div><div class=""><div class=""><div style="font-family: arial, helvetica, sans-serif; font-size: 10pt;" class=""><br class=""><br class=""><hr id="zwchr" class=""><blockquote style="border-left-width: 2px; border-left-style: solid; border-left-color: rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica, Arial, sans-serif; font-size: 12pt;" class=""><b class="">From:<span class="Apple-converted-space"> </span></b>"Daniel Berlin" <<a href="mailto:dberlin@dberlin.org" class="">dberlin@dberlin.org</a>><br class=""><b class="">To:<span class="Apple-converted-space"> </span></b>"Hal Finkel" <<a href="mailto:hfinkel@anl.gov" class="">hfinkel@anl.gov</a>><br class=""><b class="">Cc:<span class="Apple-converted-space"> </span></b>"LLVM Dev Mailing list" <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>>, "David Callahan" <<a href="mailto:dcallahan@fb.com" class="">dcallahan@fb.com</a>><br class=""><b class="">Sent:<span class="Apple-converted-space"> </span></b>Friday, January 29, 2016 12:48:37 AM<br class=""><b class="">Subject:<span class="Apple-converted-space"> </span></b>Re: [llvm-dev] DCE in the presence of control flow.<br class=""><br class=""><div dir="ltr" class=""><br class=""><div class="gmail_extra"><br class=""><div class="gmail_quote">On Thu, Jan 28, 2016 at 10:09 PM, Hal Finkel<span class="Apple-converted-space"> </span><span dir="ltr" class=""><<a href="mailto:hfinkel@anl.gov" target="_blank" class="">hfinkel@anl.gov</a>></span><span class="Apple-converted-space"> </span>wrote:<br class=""><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-style: solid; border-left-color: rgb(204, 204, 204); padding-left: 1ex;"><div class=""><div style="font-family: arial, helvetica, sans-serif; font-size: 10pt;" class=""><br class=""><hr class=""><blockquote style="border-left-width: 2px; border-left-style: solid; border-left-color: rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica, Arial, sans-serif; font-size: 12pt;" class=""><b class="">From:<span class="Apple-converted-space"> </span></b>"David Callahan via llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>><br class=""><b class="">To:<span class="Apple-converted-space"> </span></b>"Daniel Berlin" <<a href="mailto:dberlin@dberlin.org" target="_blank" class="">dberlin@dberlin.org</a>>, "LLVM Dev Mailing list" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>><br class=""><b class="">Sent:<span class="Apple-converted-space"> </span></b>Thursday, January 28, 2016 11:35:49 PM<span class=""><br class=""><b class="">Subject:<span class="Apple-converted-space"> </span></b>Re: [llvm-dev] DCE in the presence of control flow.<br class=""><br class=""><div class="">Thanks</div><div class="">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 class="">odavd</div><div class=""><br class=""></div><span class=""><div style="font-family: Calibri; font-size: 11pt; text-align: left; border-width: 1pt medium medium; border-style: solid none none; padding: 3pt 0in 0in;" class=""><span style="font-weight: bold;" class="">From:<span class="Apple-converted-space"> </span></span>Daniel Berlin <<a href="mailto:dberlin@dberlin.org" target="_blank" class="">dberlin@dberlin.org</a>><br class=""><span style="font-weight: bold;" class="">Date:<span class="Apple-converted-space"> </span></span>Thursday, January 28, 2016 at 8:45 PM<br class=""><span style="font-weight: bold;" class="">To:<span class="Apple-converted-space"> </span></span>David Callahan <<a href="mailto:dcallahan@fb.com" target="_blank" class="">dcallahan@fb.com</a>>, LLVM Dev Mailing list <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>><br class=""><span style="font-weight: bold;" class="">Subject:<span class="Apple-converted-space"> </span></span>Re: [llvm-dev] DCE in the presence of control flow.<br class=""></div><div class=""><br class=""></div><div class=""><div class="">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<span class="Apple-converted-space"> </span></div></div></span></span></blockquote><br class="">A 1-2% reduction in code size seems like it might well be worth a post-dom calculation.</div></div></blockquote><div class=""><br class=""></div><div id="DWT2476" class="">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 class=""><blockquote style="border-left-width: 2px; border-left-style: solid; border-left-color: rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica, Arial, sans-serif; font-size: 12pt;" class=""><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><div class=""></div><div class=""> </div><div class="">The cases are mostly caught by SimplifyCFG/etc anyway<br class=""></div><div class=""><br class=""></div><div class="">In any case, here are the numbers from when it was turned on by default:</div><div class=""><br class=""></div><div class=""><a href="https://gcc.gnu.org/ml/gcc-patches/2004-01/msg00675.html" target="_blank" class="">https://gcc.gnu.org/ml/gcc-patches/2004-01/msg00675.html</a><br class=""></div><div class=""><br class=""></div><div id="DWT2475" class="">Note: GCC is at least 3x faster at computing post-dom than LLVM</div></div></div></div></blockquote>Why?<br class=""><blockquote style="border-left-width: 2px; border-left-style: solid; border-left-color: rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica, Arial, sans-serif; font-size: 12pt;" class=""><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><div class=""></div><div class=""><br class=""></div><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-style: solid; border-left-color: rgb(204, 204, 204); padding-left: 1ex;"><div class=""><div style="font-family: arial, helvetica, sans-serif; font-size: 10pt;" class="">Also, what exactly is the algorithm using post-dom info?<br class=""><br class=""></div></div></blockquote><div class=""><br class=""></div><div class="">So, to review for a second, right now, the algorithm answers the question when is a branch necessary with "always" :)<br class=""></div><div class=""><br class=""></div><div class="">The real answer is "when an already-necessary operation depends on its existence". This is of course, requires control-dependence to answer.</div><div class="">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 class=""><br class=""></div><div class="">(IE </div><div class=""><br class=""></div><div class="">for each block in RDF(useful block):<br class=""> mark terminator of block as useful</div><div id="DWT2949" class=""><br class=""></div></div></div></div></blockquote><br class="">FWIW, Keith Cooper's slide deck on this has a nice explanation:<span class="Apple-converted-space"> </span><a href="https://www.cs.rice.edu/~keith/512/2011/Lectures/L04Dead-1up.pdf" class="">https://www.cs.rice.edu/~keith/512/2011/Lectures/L04Dead-1up.pdf</a><br class=""><br class="">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<span class="Apple-converted-space"> </span> 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 class=""><br class="">Thanks again,<br class="">Hal<br class=""><blockquote style="border-left-width: 2px; border-left-style: solid; border-left-color: rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica, Arial, sans-serif; font-size: 12pt;" class=""><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><div class=""></div><div class=""><br class=""></div><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-style: solid; border-left-color: rgb(204, 204, 204); padding-left: 1ex;"><div class=""><div style="font-family: arial, helvetica, sans-serif; font-size: 10pt;" class="">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 class=""><br class="">Yes. Loops with all dead instructions includes "loops with no side-effects outside of the loop" </div><div class=""> </div><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-style: solid; border-left-color: rgb(204, 204, 204); padding-left: 1ex;"><div class=""><div style="font-family: arial, helvetica, sans-serif; font-size: 10pt;" class=""><span style="font-family: arial, sans-serif; font-size: small; color: rgb(34, 34, 34);" class=""> </span><br class=""></div></div></blockquote><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-style: solid; border-left-color: rgb(204, 204, 204); padding-left: 1ex;"><div class=""><div style="font-family: arial, helvetica, sans-serif; font-size: 10pt;" class="">Thanks again,<br class="">Hal<span class=""><br class=""><blockquote style="border-left-width: 2px; border-left-style: solid; border-left-color: rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica, Arial, sans-serif; font-size: 12pt;" class=""><span class=""><div class=""><div class=""><div class=""><br class=""><div class="gmail_quote"><div dir="ltr" class="">On Wed, Jan 27, 2016, 1:56 PM David Callahan via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>> wrote:<br class=""></div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left-width: 1px; border-left-style: solid; border-left-color: rgb(204, 204, 204); padding-left: 1ex;"><div style="word-wrap: break-word; font-size: 14px; font-family: Calibri, sans-serif;" class=""><div class=""><div style="margin: 0px;" class="">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 class=""></u><u class=""></u></div><div style="margin: 0px;" class=""><u class=""></u> <u class=""></u></div><div style="margin: 0px;" class="">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;" class="">isa<TerminatorInst>(I)). <span class="Apple-converted-space"> </span></span>Doing more requires some approximation to control dependence.<u class=""></u><u class=""></u></div><div style="margin: 0px;" class=""><u class=""></u> <u class=""></u></div><div style="margin: 0px;" class="">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 class=""></u><u class=""></u></div><div style="margin: 0px;" class=""><u class=""></u> <u class=""></u></div><div style="margin: 0px;" class="">Have their been prior attempts strengthen dead code elimination w.r.t. control flow? If so, any guidance on what went wrong?<u class=""></u><u class=""></u></div><div style="margin: 0px;" class=""><u class=""></u> <u class=""></u></div><div style="margin: 0px;" class="">Thanks<u class=""></u><u class=""></u></div><div style="margin: 0px;" class="">David<u class=""></u><u class=""></u></div><p class="MsoNormal" style="margin: 0px;"><span style="font-size: 10pt; font-family: Consolas;" class=""> </span></p></div></div>_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a><br class=""><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" class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br class=""></blockquote></div></div></div></div></span><br class="">_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a><br class=""><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" class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br class=""></blockquote><br class=""><br class=""><br class=""></span><span class="">--<span class="Apple-converted-space"> </span><br class=""><div class=""><span class=""></span>Hal Finkel<br class="">Assistant Computational Scientist<br class="">Leadership Computing Facility<br class="">Argonne National Laboratory<span class=""></span><br class=""></div></span></div></div></blockquote></div><br class=""></div></div></blockquote><br class=""><br class=""><br class="">--<span class="Apple-converted-space"> </span><br class=""><div class=""><span name="x" class=""></span>Hal Finkel<br class="">Assistant Computational Scientist<br class="">Leadership Computing Facility<br class="">Argonne National Laboratory<span name="x" class=""></span><br class=""></div></div></div></div></span><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class=""></span><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">_______________________________________________</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">LLVM Developers mailing list</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class=""><a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a></span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class=""><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a></span></div></blockquote></div><br class=""></body></html>