<html xmlns:v="urn:schemas-microsoft-com:vml" 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="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Wingdings;
panose-1:5 0 0 0 0 0 0 0 0 0;}
@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;}
@font-face
{font-family:"Segoe UI";
panose-1:2 11 5 2 4 2 4 2 2 3;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0cm;
margin-right:0cm;
margin-bottom:0cm;
margin-left:36.0pt;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
span.m3383979024771043645hoenzb
{mso-style-name:m_3383979024771043645hoenzb;}
span.EmailStyle18
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 90.0pt 72.0pt 90.0pt;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:775095337;
mso-list-type:hybrid;
mso-list-template-ids:-1312378800 67698689 67698691 67698693 67698689 67698691 67698693 67698689 67698691 67698693;}
@list l0:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l0:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level5
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l0:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level8
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
ol
{margin-bottom:0cm;}
ul
{margin-bottom:0cm;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Here are my thoughts on the issue at hand:<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">As far as I understand the current reassociate pass is a rather niche pass, not intended for extensive use. It also has quite a few weaknesses, the most prominent
one is its aggressive re-arrangement of the topology of the associative operator tree into "linear tree", e.g. for addition you’ll get
</span><span style="font-size:10.0pt;font-family:"Courier New";color:black;background:white">a_0 + (a_1 + (a_2 + ... (a_n-1 + a_n))...)</span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> regardless of the topology you started
with.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Due to that, and because reassociations of all kinds and types are sometimes a key component of a transformation (which is either missing from an InstCombine
transformation or unnaturally added to it), these reassociations, as of today, don’t have a “home”. For example, when I suggested
<a href="https://reviews.llvm.org/D41574">https://reviews.llvm.org/D41574</a>, the “Weak reassociation pass”, it was to complement a transformation I’m adding to InstCombine – My transformation involved a reassociation of the form
</span><span style="font-size:10.0pt;font-family:"Courier New";color:black;background:white">(a_0 + a_1) + (a_2 + a_3) -> (a_0 + a_2) + (a_1 + a_3)</span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> which can’t be expressed
in the existing reassociate pass, so I had to write a new pass. That is, amongst the rest, why It’s called “weak” - it doesn’t change the topology of the associative operator tree.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">I believe that a new reassociation pass that will complement InstCombine and will run with it under a “parent” pass is the way to go. However, there is clearly
much work involved in such a process.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Omer<o:p></o:p></span></p>
<p class="MsoNormal"><a name="_MailEndCompose"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></a></p>
<p class="MsoNormal"><a name="_____replyseparator"></a><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> Sanjay Patel [mailto:spatel@rotateright.com]
<br>
<b>Sent:</b> Wednesday, May 09, 2018 16:09<br>
<b>To:</b> Chris Lattner <clattner@nondot.org><br>
<b>Cc:</b> Daniel Berlin <dberlin@dberlin.org>; llvm-dev <llvm-dev@lists.llvm.org>; Paparo Bivas, Omer <omer.paparo.bivas@intel.com><br>
<b>Subject:</b> Re: [llvm-dev] more reassociation in IR<o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt">When you say that distribution shouldn't be used, do you mean within instcombine rather than some other pass? Or not all as an IR optimization?<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">A dedicated optimization pass that looks for and makes factoring/distribution folds to eliminate instructions seems like it would solve the problems that I'm seeing.
<br>
Ie, I'm leaning towards the proposal here: <a href="https://reviews.llvm.org/D41574" target="_blank">
https://reviews.llvm.org/D41574</a><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">But I'd make it less "weak". :)<br>
<br>
Ideally, that allows removing duplicate functionality from instcombine, but I'm guessing that it will take a lot of work to cut that cord without causing regressions. Note that instcombine even has a specialized reassociation pass-within-a-pass for fadd/fsub
alone:<br>
<a href="https://reviews.llvm.org/rL170471" target="_blank">https://reviews.llvm.org/rL170471</a><o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">On Tue, May 8, 2018 at 9:22 PM, Chris Lattner <<a href="mailto:clattner@nondot.org" target="_blank">clattner@nondot.org</a>> wrote:<o:p></o:p></p>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal"><br>
<br>
<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal">On May 8, 2018, at 9:50 AM, Daniel Berlin via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal">1. The reassociate pass that exists right now was *originally* (AFAIK) written to enable CSE/GVN to do better.<o:p></o:p></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Agreed. The original mindset included a (naive) belief that going with a canonical form was better than teaching redundancy elimination to handle abstractions (as a matter of separation of concerns). I think that that was a failed experiment
at this point :-). We should still canonicalize x*x*x into powi, but the more aggressive canonicalization (like distribution) shouldn’t be used IMO.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="color:#888888"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:#888888">-Chris<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:#888888"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:#888888"><o:p> </o:p></span></p>
</div>
<p class="MsoNormal"><span style="color:#888888"><br>
<br>
</span><o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div>
<p class="MsoNormal">That particular issue is solvable in other ways, because there are good ways to integrate reassociation into CSE/GVN (and at this point, it would probably be cheaper than -reassociate since it would modify code less, only changing it when
there are actual redundancies )<o:p></o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif;color:#222222">I don't know what other things people are trying to target with reassociate these days, it would be good to understand what others see as the use cases.<o:p></o:p></span></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">My only other fear with removing it is that we have a tendency to try to make every optimization do everything, so i fear removing reassociate might just have people try to improve every pass to do reassociation instead of declaring what
is good enough.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">(For example, GVN already does some reassociation, as do some analysis. Other analysis relies more on a canonical form existing and don't, for example, try to perform commutativity on their own. IMHO, we should just declare one or the
other to be the case, and hold that line, rather than generate a mishmash)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<div>
<p class="MsoNormal">2. "<span style="font-size:9.5pt">Keep in mind that instcombine runs 1st, runs to fixed-point, and runs 8 times in the -O2 pipeline."</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<div>
<p class="MsoNormal" style="background:white"><span style="font-size:9.5pt;font-family:"Arial",sans-serif;color:#222222">Y'all know how i feel about this one, so i'll leave it alone :)</span><span style="font-family:"Arial",sans-serif;color:#222222"><o:p></o:p></span></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">--Dan<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal">_______________________________________________<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="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><o:p></o:p></p>
</div>
</blockquote>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</blockquote>
</div>
<div>
<div>
<div>
<div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</div>
</div>
</div>
</div>
<p>---------------------------------------------------------------------<br>
Intel Israel (74) Limited</p>
<p>This e-mail and any attachments may contain confidential material for<br>
the sole use of the intended recipient(s). Any review or distribution<br>
by others is strictly prohibited. If you are not the intended<br>
recipient, please contact the sender and delete all copies.</p></body>
</html>