<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:"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:Consolas;
panose-1:2 11 6 9 2 2 4 3 2 4;}
/* 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;}
pre
{mso-style-priority:99;
mso-style-link:"HTML Preformatted Char";
margin:0cm;
margin-bottom:.0001pt;
font-size:10.0pt;
font-family:"Courier New";}
span.gmail-m596114956539797037gmail-m7327146177040704443gmail-m2423541276025245453m-9018700274548918466gmail-m2085822097580644453m402989712542517733gmail-m8307257963026143428gmail-
{mso-style-name:gmail-m_596114956539797037gmail-m_7327146177040704443gmail-m_2423541276025245453m_-9018700274548918466gmail-m_2085822097580644453m_402989712542517733gmail-m_8307257963026143428gmail-;}
span.gmail-
{mso-style-name:gmail-;}
span.HTMLPreformattedChar
{mso-style-name:"HTML Preformatted Char";
mso-style-priority:99;
mso-style-link:"HTML Preformatted";
font-family:Consolas;}
span.EmailStyle21
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 90.0pt 72.0pt 90.0pt;}
div.WordSection1
{page:WordSection1;}
--></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">Rebased D41574 to trunk.<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> Saturday, May 19, 2018 00:31<br>
<b>To:</b> Hiroshi Yamauchi <yamauchi@google.com><br>
<b>Cc:</b> Hal Finkel <hfinkel@anl.gov>; 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">I mentioned this earlier in the thread - I would like to see something like D41574 in the optimizer. It's optimizing code that no other pass does currently, and I don't see any other near-term proposal that gets us those optimizations.<br>
<o:p></o:p></p>
<div>
<p class="MsoNormal">Omer, can you rebase that to trunk? I think a header has moved, so it doesn't build as-is. I'd like to know if it can catch the cases in D45842. If not, why not? If it can handle those easily, I'll abandon D45842.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<p class="MsoNormal">Also, I don't know if it's better to include that functionality as another iteration of the existing -reassociate or split it off as its own pass. But I think it should do the distributive simplifications that are currently in -instcombine
(InstCombiner::SimplifyUsingDistributiveLaws). Using that instsimplify logic for analysis lets us decide if the reassociation is worthwhile in the 1st place, it removes the risk that some other pass would somehow mess up the pattern before instcombine could
zap it, and it reduces the burden on instcombine to be the entire optimizer. :)<o:p></o:p></p>
<div>
<div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
</div>
</div>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">On Mon, May 14, 2018 at 1:34 PM, Hiroshi Yamauchi 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>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p> </o:p></span></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<div>
<div>
<p class="MsoNormal">On Fri, May 11, 2018 at 7:20 PM Hal Finkel <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>> wrote:<o:p></o:p></p>
</div>
<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">On 05/11/2018 08:40 PM, Daniel Berlin via llvm-dev wrote:<o:p></o:p></p>
</div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">On Fri, May 11, 2018 at 2:37 PM, Hiroshi Yamauchi <<a href="mailto:yamauchi@google.com" target="_blank">yamauchi@google.com</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>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p> </o:p></span></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<div>
<div>
<p class="MsoNormal">On Thu, May 10, 2018 at 12:49 PM Daniel Berlin <<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>> wrote:<o:p></o:p></p>
</div>
<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"><o:p> </o:p></p>
<div>
<p class="MsoNormal">On Thu, May 10, 2018 at 12:05 PM, Hiroshi Yamauchi <<a href="mailto:yamauchi@google.com" target="_blank">yamauchi@google.com</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>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p> </o:p></span></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal">On Wed, May 9, 2018 at 8:24 PM Daniel Berlin <<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>> wrote:<o:p></o:p></p>
</div>
<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"><o:p> </o:p></p>
<div>
<p class="MsoNormal">On Wed, May 9, 2018 at 10:39 AM, Hiroshi Yamauchi <<a href="mailto:yamauchi@google.com" target="_blank">yamauchi@google.com</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>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p> </o:p></span></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal">On Tue, May 8, 2018 at 11:15 AM Daniel Berlin <<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>> wrote:<o:p></o:p></p>
</div>
<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"><o:p> </o:p></p>
<div>
<p class="MsoNormal">On Tue, May 8, 2018 at 10:38 AM, Hiroshi Yamauchi 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>
<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"><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:#222222">I came across this issue in the context of<o:p></o:p></span></p>
</div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:#222222;background:white"> </span><a href="https://reviews.llvm.org/D46336" target="_blank"><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:#1155CC">D46336</span></a><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:#222222;background:white">.</span>
<o:p></o:p></p>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"> <o:p></o:p></span></p>
</div>
<p class="MsoNormal">Thanks, Sanjay, for starting this discussion.)<o:p></o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">If <o:p></o:p></p>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif">we will<o:p></o:p></span></p>
</div>
<p class="MsoNormal"> move <span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:#222222;background:white">
<o:p></o:p></span></p>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:#222222;background:white">reassociation, <o:p></o:p></span></p>
</div>
<p class="MsoNormal">or keep additional ones <o:p></o:p></p>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif">,<o:p></o:p></span></p>
</div>
<p class="MsoNormal">out of instcombine, <o:p></o:p></p>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif">open questions for me would be<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif">:<o:p></o:p></span></p>
</div>
<p class="MsoNormal"><br>
<br>
1. Since -reassociate isn't a fixed point pass,<o:p></o:p></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">This is fixable, fwiw, without fixpointing it.<o:p></o:p></p>
</div>
</div>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif">How?<o:p></o:p></span></p>
</div>
</div>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Depends on specifically which part you would like to know about ;)<o:p></o:p></p>
</div>
</div>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif">Maybe I misunderstood what you meant by "This is fixable". Did you mean that we won't somehow need to fixpoint between instcombine and reassociate, or that </span><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:#222222;background:white">the
specific motivating examples from the above differentials are foldable without fixpointing?</span><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
</div>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">If by fixpointing you mean "fixpointing reassociate and instcombine", then yes, that is fixable without fixpointing reassociate and instcombine, but would require rewriting instcombine :)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:#222222;background:white">If the latter, that may be the case. The concern was that we may encounter examples that may need many more iterations, if not fixpointing. As
long as it's feasible to fixpoint between instcombine and reassociate, it seems to work, but I guess that would probably need some pass management change.</span><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<div>
<p class="MsoNormal">we might need to repeat "-instcombine -reassociate" multiple times to
<o:p></o:p></p>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif">fold<o:p></o:p></span></p>
</div>
<p class="MsoNormal"> down to what we want (relating to <a href="https://reviews.llvm.org/D46336#1087082" target="_blank">
my comment here</a>). I assumed this isn't not what we want to do <o:p></o:p></p>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif">? My impression is we don't do a fixed-point with passes?<o:p></o:p></span></p>
</div>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Well, i mean there is no practical difference between passes that we fixpoint externally and fixpoint internally.<o:p></o:p></p>
</div>
</div>
</div>
</div>
</blockquote>
<div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:#222222;background:white">I had the following in mind: Does the pass manager support fixpointing externally? Is there any performance difference? Are people okay with that
in general?</span><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif">But if there is no practical difference, I don't see any problem with that :)<o:p></o:p></span></p>
</div>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
</blockquote>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<div>
<p class="MsoNormal">2. <o:p></o:p></p>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif">Since -</span><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:#222222;background:white">reassociate needs to come up with one operand order (at least currently as the only reassociate pass),
would there exist a single, unique operand order that would enable all reassociative/commutative foldings that we want?
</span><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">In what way?<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">Are you asking whether there is a single reassociation order that makes all foldings occur in the same operation or something?<br>
I don't feel like i understand what you are asking.<o:p></o:p></p>
</div>
</div>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif">Does this rephrase help: with the motivating examples (like and-of-shifts or bit check patterns) from the above differentials in mind, can we come up with a single </span><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:#222222;background:white">reassociation
order that solves all those and all the others that may come up in the future? Would we need different reassociation orders to fold different patterns?</span><o:p></o:p></p>
</div>
</div>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">It doesn't quite help.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">When stated that generally, there can be no such ordering at all, that's easy to prove. It is a statically undecidable problem.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">There is however, a different question and answer to a few related problems that maybe you are really asking?<br>
1. Is there a way to determine and apply the a maximal or nearly-maximal set of folds/graph transforms that could be applied to a given set of code in a sane and principled way -> yes<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">(see, e.g., <a href="http://www.cs.cornell.edu/%7Eross/publications/eqsat/" target="_blank">http://www.cs.cornell.edu/~ross/publications/eqsat/</a>)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">2. Is there a way to determine all expressions in the program as it exists that are equivalent or equivalent under constant time constant folding/reassociation, in a reasonable time bound -> yes<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">(not a single easy link, happy to talk about it)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Your original question is basically equivalent to<o:p></o:p></p>
</div>
<div>
<div>
<p class="MsoNormal" style="background:white"><span style="font-family:"Arial",sans-serif;color:#222222">Is there a way to determine all expressions in the program as it exists that are equivalent or could be made equivalent through any type of folding that
one can think up?<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="background:white"><span style="font-family:"Arial",sans-serif;color:#222222">The answer to that is "no", it's provable that this is not statically decidable, so the time bound doesn't matter :)<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="background:white"><span style="font-family:"Arial",sans-serif;color:#222222"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="background:white"><span style="font-family:"Arial",sans-serif;color:#222222">You have to limit the possible folding/evaluation you apply in various ways to make this decidable, and then further limit it to make the time bound reasonable.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="background:white"><span style="font-family:"Arial",sans-serif;color:#222222"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="background:white"><span style="font-family:"Arial",sans-serif;color:#222222">This all quickly devolves into herbrand equivalence and it's variations.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="background:white"><span style="font-family:"Arial",sans-serif;color:#222222"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="background:white"><span style="font-family:"Arial",sans-serif;color:#222222"><o:p> </o:p></span></p>
</div>
</div>
</div>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"></span><o:p></o:p></p>
</div>
</div>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif">Let me try one more time :) May we need multiple reassociate passes to fold different reassociative patterns?</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif">A longer version: If Sanjay wants a particular reassociative pattern to be folded (D45842), Omer wants another particular reassociative
</span><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:#222222;background:white">pattern</span><span style="font-family:"Arial",sans-serif"> to be folded (D41574), and I want yet another particular reassociative
</span><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:#222222;background:white">pattern</span><span style="font-family:"Arial",sans-serif"> to be folded (D46336), would we potentially need three different reassociate passes with each combined
with instcombine, rather than just one that may be able to </span><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:#222222;background:white">somehow </span><span style="font-family:"Arial",sans-serif">handle those cases in one shot, (assuming
we don't want to put those in instcombine)?</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif">And it sounds like the answer is yes?</span><o:p></o:p></p>
</div>
</div>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">If you take the current instcombine as a base, then yes, that is correct.<o:p></o:p></p>
</div>
</div>
</div>
</div>
</blockquote>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<div>
<div>
<div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<p class="MsoNormal">If you are willing to rearchitect instcombine, the answer is no, it's possible to do this all in a single pass in a relatively sane way.<o:p></o:p></p>
</div>
</div>
</div>
</div>
</blockquote>
<div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p> </o:p></span></p>
</div>
</div>
</div>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif">I assume by </span><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:#222222;background:white">rearchitect, you mean a major rewrite as per this comment</span><span style="font-family:"Arial",sans-serif">: "Is
there a way to determine all expressions in the program as it exists that are equivalent or equivalent under constant time constant folding/reassociation, in a reasonable time bound -> yes". Any pointer or time to chat?<o:p></o:p></span></p>
</div>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">I'm happy to do both.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif">I think that an approach like <o:p></o:p></span></p>
</div>
<p class="MsoNormal">D <o:p></o:p></p>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<p class="MsoNormal">4 <o:p></o:p></p>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<p class="MsoNormal">6 <o:p></o:p></p>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<p class="MsoNormal">3 <o:p></o:p></p>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<p class="MsoNormal">3 <o:p></o:p></p>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<p class="MsoNormal">6 <o:p></o:p></p>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"> / <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<p class="MsoNormal">D <o:p></o:p></p>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<p class="MsoNormal">4 <o:p></o:p></p>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<p class="MsoNormal">6 <o:p></o:p></p>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<p class="MsoNormal">5 <o:p></o:p></p>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<p class="MsoNormal">9 <o:p></o:p></p>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<p class="MsoNormal">5 <o:p></o:p></p>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"> has a merit: it would adds a bit of complexity, but would not</span><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:#222222;background:white"> require:</span><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p> </o:p></span></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:#222222;background:white">1. a major rewrite of instcombine,</span><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:#222222;background:white">2. writing multiple (potentially many) reassociate passes and figuring out how to fixpoint them with instcombine, or</span><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:#222222;background:white">3. writing a self-contained folding pass for a specific pattern</span><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p> </o:p></span></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:#222222;background:white">If you look at the diffs in the existing .ll files in </span><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif">D46336 <o:p></o:p></span></p>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif">, it helps fold some previously-unfolded </span><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:#222222;background:white">reassociation patterns beyond the bit check patterns
that it originally targeted.</span><span style="font-family:"Arial",sans-serif"><o:p></o:p></span></p>
</div>
</div>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal">Sure, and it does so by adding another O(N) cost to evaluation in each case. Instcombine doesn't even do lazy reevaluation through tracking dependencies, so it'll do so a lot of times as well.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">To me, that's not a good tradeoff, especially given how slow instcombine is *already*. The code it produces is "good enough" to stop for a while and do something else and not suffer horribly in performance.[1]<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt">Let me ask a different question:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">At what point would anyone here be willing to stop adding things to instcombine and start doing something else instead, instead of waiting for someone else to do it?<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">As far as i can tell, the answer is: "never", which makes most of these discussions just pointless rehashes as we slowly repeat the same disaster that became gcc's instruction combiner :)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">If the answer is "something", great, i'll set a mail filter and ignore these threads until that something happens :)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Personally, in my experience people will never do more here unless pushed somewhat, or the thing becomes such a complete disaster no one wants to touch it.<o:p></o:p></p>
</div>
</div>
</div>
</div>
</blockquote>
<p class="MsoNormal"><br>
I've said this before, but I think a major impediment to forward progress here is coming up with an agreement on what the "something else" should be. Some of us have talked for years about having some TableGen-driven replacement, or maybe we want something
with a syntax more like what is used by the Alive tool, but regardless, in order to gain in efficiency I suspect we need a model that is more restrictive than more-or-less arbitrary C++ code, and so we should pick a model and figure out how things might work.<br>
<br>
<br>
<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div>
<div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">[1] Last year i computed the "improvement in performance on applications" due to instcombine for a bunch of google apps and open source apps that had easy to use benchmarks (IE I isolated about two years of instcombine changes and made
them to a current compiler piece by piece while measuring performance).<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">I also computed the compile time increase in single instcombine passes over the same time period.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">On x86, but the numbers basically said we were basically gaining nearly nothing for high cost. IE our drive for better looking output does not appear to translate into any real gains that i can find. Either improvements to other opts
hid them, or they simply didn't matter on the processors i tested on.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Certainly, apps/workloads/architectures may vary here, and my goal is not to claim it's all worthless.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">My actual goal in all of this was to get a sense of whether my perspective on instcombine was still "reasonable", not to do a true scientific exploration :)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">I didn't have time/energy/etc to run it elsewhere, and again, my goal was not to give certainty/try to give exact percentages.<o:p></o:p></p>
</div>
</div>
</div>
</div>
</blockquote>
<p class="MsoNormal" style="margin-bottom:12.0pt"><br>
This also matches my experience, but I draw a somewhat different lesson. I often tell application developers that *this* is why they must file compiler bug reports. Waiting and assuming that someone else will hit the same problem, and file the report, is a
bad strategy. I think that this is due to two things:<br>
<br>
1. As far as things go, the tail of the distribution is often really long, and probability that the particular thing hampering one piece of hot code is the same thing hampering another piece of hot code is often small.<br>
<br>
2. We tend to add special cases instead of adding more-general algorithms. The more-general work is often hard because figuring out the cost modeling is often highly non-trivial. Also, when it's finally done, the chances that the old special cases are removed
is also small (so we'll still accumulate cruft without specific effort).<o:p></o:p></p>
</div>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</div>
<div>
<div>
<p class="MsoNormal" style="background:white"><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:#222222">I don't have better or larger study results or data<span style="background:white">, but for fixing some smaller but important enough
performance degradations (often in microbenchmarks, but occasionally in larger settings) smaller compiler improvements (not necessarily in instcombine but around that level) do seem to matter at least in individual contexts. It's not clear how much those actually
mattered in a grander scheme of things, though.</span><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="background:white"><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:#222222"><o:p> </o:p></span></p>
</div>
</div>
<div>
<p class="MsoNormal" style="background:white"><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:#222222">It sounds like we don't want to add to instcombine due to added cost/complexity, rearchitecting would be hard, it's not clear if incremental
changes in instcombine did much per cost, which would make it harder to justify <span style="background:white">rearchitecting it...</span><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="background:white"><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:#222222"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="background:white"><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:#222222">What do people think of approaches like D41574 and D45842?<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="background:white"><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:#222222"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<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"> -Hal<br>
<br>
<br>
<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div>
<div>
<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"><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>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</div>
</div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><o:p> </o:p></p>
<pre>_______________________________________________<o:p></o:p></pre>
<pre>LLVM Developers mailing list<o:p></o:p></pre>
<pre><a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><o:p></o:p></pre>
<pre><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></pre>
</blockquote>
<p class="MsoNormal"><br>
<br>
<o:p></o:p></p>
<pre>-- <o:p></o:p></pre>
<pre>Hal Finkel<o:p></o:p></pre>
<pre>Lead, Compiler Technology and Programming Languages<o:p></o:p></pre>
<pre>Leadership Computing Facility<o:p></o:p></pre>
<pre>Argonne National Laboratory<o:p></o:p></pre>
</div>
</blockquote>
</div>
</div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org">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>
</blockquote>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</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>