<html xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Title" content="">
<meta name="Keywords" content="">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:Calibri;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
text-decoration:underline;}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0in;
margin-right:0in;
margin-bottom:0in;
margin-left:.5in;
margin-bottom:.0001pt;
mso-add-space:auto;
font-size:12.0pt;
font-family:Calibri;}
p.MsoListParagraphCxSpFirst, li.MsoListParagraphCxSpFirst, div.MsoListParagraphCxSpFirst
{mso-style-priority:34;
mso-style-type:export-only;
margin-top:0in;
margin-right:0in;
margin-bottom:0in;
margin-left:.5in;
margin-bottom:.0001pt;
mso-add-space:auto;
font-size:12.0pt;
font-family:Calibri;}
p.MsoListParagraphCxSpMiddle, li.MsoListParagraphCxSpMiddle, div.MsoListParagraphCxSpMiddle
{mso-style-priority:34;
mso-style-type:export-only;
margin-top:0in;
margin-right:0in;
margin-bottom:0in;
margin-left:.5in;
margin-bottom:.0001pt;
mso-add-space:auto;
font-size:12.0pt;
font-family:Calibri;}
p.MsoListParagraphCxSpLast, li.MsoListParagraphCxSpLast, div.MsoListParagraphCxSpLast
{mso-style-priority:34;
mso-style-type:export-only;
margin-top:0in;
margin-right:0in;
margin-bottom:0in;
margin-left:.5in;
margin-bottom:.0001pt;
mso-add-space:auto;
font-size:12.0pt;
font-family:Calibri;}
span.EmailStyle18
{mso-style-type:personal-reply;
font-family:Calibri;
color:windowtext;}
span.msoIns
{mso-style-type:export-only;
mso-style-name:"";
text-decoration:underline;
color:teal;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:1806045214;
mso-list-type:hybrid;
mso-list-template-ids:1693352680 67698703 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l0:level1
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l0:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l0:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
ol
{margin-bottom:0in;}
ul
{margin-bottom:0in;}
--></style>
</head>
<body bgcolor="white" lang="EN-US" link="#0563C1" vlink="#954F72">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-size:11.0pt">Hi David, <o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt">Thanks for working on this. I’d like to help reviewing your work!
<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt">How much code from the original patch are you leaving around? If you are reusing a lot of code from the original pass then you can refactor, clean and add new functionality. But if you are not keeping much
then maybe it would be useful to develop a new pass (with small incremental reviewable changes), and when the work is done flip the switch and start using the new pass. What do you prefer? <o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt">I think that introducing the new flag that allows the removal of infinite loops is a great idea. LLVM is used for compilation of non-C languages, like Swift, Java, Python, etc, and these languages may benefit
from the new functionality. <o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt">-Nadav<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt"><o:p> </o:p></span></p>
<div style="border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b><span style="color:black">From: </span></b><span style="color:black">David Callahan <dcallahan@fb.com><br>
<b>Date: </b>Monday, August 1, 2016 at 10:45 AM<br>
<b>To: </b>LLVM Dev Mailing list <llvm-dev@lists.llvm.org><br>
<b>Cc: </b>Kevin Frei <freik@fb.com>, Nadav Rotem <nrotem@fb.com>, Chandler Carruth <chandlerc@gmail.com><br>
<b>Subject: </b>[LLVM] New Dead Code Elimination<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Times New Roman""><o:p> </o:p></span></p>
</div>
<div>
<div>
<div>
<p class="MsoNormal"><span style="color:black">I have a rewrite of the aggressive dead code elimination pass which handles control flow and allows may-be-infinite loops to be removed under optional flag. Chandler suggested rather than a large change a series
of small changes and, while that may not get us to small changes easily, there has been no further commentary on the diff:
<a href="https://reviews.llvm.org/D18762">https://reviews.llvm.org/D18762</a>. Given that, I will plan on proposing a series of diffs and would like to recruit some people who are interested in the change to help review those changes.
<o:p></o:p></span></p>
<p class="MsoNormal"><span style="color:black"> <o:p></o:p></span></p>
<p class="MsoNormal"><span style="color:black">I expect to stage as follows:<o:p></o:p></span></p>
<p class="MsoNormal"><span style="color:black"> <o:p></o:p></span></p>
<p class="MsoListParagraphCxSpFirst" style="text-indent:-.25in;mso-list:l0 level1 lfo2">
<![if !supportLists]><span style="color:black"><span style="mso-list:Ignore">1.<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span style="color:black">Rewrite base algorithm to introduce data structures needed to hold extra information (no functional change)<o:p></o:p></span></p>
<p class="MsoListParagraphCxSpMiddle" style="text-indent:-.25in;mso-list:l0 level1 lfo2">
<![if !supportLists]><span style="color:black"><span style="mso-list:Ignore">2.<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span style="color:black">Rewrite base algorithm to allow removing of control flow (under option, off by default). This variant will not be correct in the general case.<o:p></o:p></span></p>
<p class="MsoListParagraphCxSpMiddle" style="text-indent:-.25in;mso-list:l0 level1 lfo2">
<![if !supportLists]><span style="color:black"><span style="mso-list:Ignore">3.<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span style="color:black">Code to rewrite the control flow graph and remove dead basic blocks<o:p></o:p></span></p>
<p class="MsoListParagraphCxSpMiddle" style="text-indent:-.25in;mso-list:l0 level1 lfo2">
<![if !supportLists]><span style="color:black"><span style="mso-list:Ignore">4.<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span style="color:black">Identify Phi nodes with non-instruction reaching definitions and keep the associated source block live. Identify Phi nodes with multiple-live values from dead blocks<o:p></o:p></span></p>
<p class="MsoListParagraphCxSpLast" style="text-indent:-.25in;mso-list:l0 level1 lfo2">
<![if !supportLists]><span style="color:black"><span style="mso-list:Ignore">5.<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span style="color:black">Remove unreachable code discovered by post-order traversal to avoid.<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.25in;text-indent:.25in"><span style="color:black"> (code is functionally correct at this point)<o:p></o:p></span></p>
<p class="MsoListParagraphCxSpFirst" style="text-indent:-.25in;mso-list:l0 level1 lfo2">
<![if !supportLists]><span style="color:black"><span style="mso-list:Ignore">6.<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span style="color:black">Use post-order traversal to identify loop bottoms. By default this will be kept live but include switch to allow loops to be removed.
<o:p></o:p></span></p>
<p class="MsoListParagraphCxSpLast" style="text-indent:-.25in;mso-list:l0 level1 lfo2">
<![if !supportLists]><span style="color:black"><span style="mso-list:Ignore">7.<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span style="color:black">Improve handling of live values out of dead regions<o:p></o:p></span></p>
<p class="MsoNormal"><span style="color:black"> <o:p></o:p></span></p>
<p class="MsoNormal"><span style="color:black">Please respond if you are willing to help or have suggestions on staging or approach.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="color:black"> <o:p></o:p></span></p>
<p class="MsoNormal"><span style="color:black">Thanks<o:p></o:p></span></p>
<p class="MsoNormal"><span style="color:black">David<o:p></o:p></span></p>
</div>
</div>
</div>
</div>
</body>
</html>