<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Tue, May 8, 2018 at 10:38 AM, Hiroshi Yamauchi via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">(<div style="color:rgb(34,34,34);font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;font-family:arial,helvetica,sans-serif;display:inline">I came across this issue in the context of</div><span style="color:rgb(34,34,34);font-family:sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline"> </span><a href="https://reviews.llvm.org/D46336" style="color:rgb(17,85,204);font-family:sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px" target="_blank">D46336</a><span style="color:rgb(34,34,34);font-family:sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">.</span><div style="font-family:arial,helvetica,sans-serif;display:inline"> </div>Thanks, Sanjay, for starting this discussion.)<br><div><br></div><div>If <div style="font-family:arial,helvetica,sans-serif;display:inline">we will</div> move <span style="color:rgb(34,34,34);font-family:sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline"><div style="font-family:arial,helvetica,sans-serif;display:inline">reassociation, </div></span>or keep additional ones<div style="font-family:arial,helvetica,sans-serif;display:inline">,</div> out of instcombine, <div style="font-family:arial,helvetica,sans-serif;display:inline">open questions for me would be</div><div style="font-family:arial,helvetica,sans-serif;display:inline">:</div><br><br>1. Since -reassociate isn't a fixed point pass,</div></div></blockquote><div><br></div><div>This is fixable, fwiw, without fixpointing it.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div> we might need to repeat "-instcombine -reassociate" multiple times to <div style="font-family:arial,helvetica,sans-serif;display:inline">fold</div> 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<div style="font-family:arial,helvetica,sans-serif;display:inline">? My impression is we don't do a fixed-point with passes?</div></div></div></blockquote><div><br></div><div>Well, i mean there is no practical difference between passes that we fixpoint externally and fixpoint internally.</div><div> <br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div> <br></div></div></blockquote><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>2. <div style="font-family:arial,helvetica,sans-serif;display:inline">Since -<span style="color:rgb(34,34,34);font-family:sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">reassociate needs to come up with one operand order (at least currently as the only <span style="color:rgb(34,34,34);font-family:sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">reassociate </span>pass), would there exist a single, unique operand order that would enable all <span style="color:rgb(34,34,34);font-family:arial,helvetica,sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline"><span style="color:rgb(34,34,34);font-family:sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">reassociative/commutative</span> foldings that we want? </span></span></div></div></div></blockquote><div><br></div><div>In what way?</div><div>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.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div style="font-family:arial,helvetica,sans-serif;display:inline"><span style="color:rgb(34,34,34);font-family:sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline"><span style="color:rgb(34,34,34);font-family:arial,helvetica,sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">If not, could there be conflicts among different reassociation orders depending on what folding we want?</span></span></div></div></div></blockquote><div><br></div><div>We actually do try to have a single canonical form at various points in the compiler. </div><div><br></div><div>We may want to canonicalize differently in different parts of the compiler, but it would be nice to at least be self consistent. </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div></div></div><div class="HOEnZb"><div class="h5"><br><br><div class="gmail_quote"><div dir="ltr">On Tue, May 8, 2018 at 9:19 AM Sanjay Patel <<a href="mailto:spatel@rotateright.com" target="_blank">spatel@rotateright.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><div>There are at least 3 active proposals to add reassociative optimizations in IR:<br>[1] <a href="https://reviews.llvm.org/D41574" target="_blank">D41574 </a>- a new pass for reassociation/factoring<br>[2] <a href="https://reviews.llvm.org/D46336" target="_blank">D46336</a> - enhance -instcombine to do more reassociation/factoring<br>[3] <a href="https://reviews.llvm.org/D45842" rel="noreferrer" target="_blank">D45842</a> - add to the existing -reassociate pass to enable factoring<br><br></div>Here's a basic motivating example that we fail to optimize:<br><a href="https://godbolt.org/g/64NmJM" target="_blank">https://godbolt.org/g/64NmJM</a><br><a href="https://rise4fun.com/Alive/wec" target="_blank">https://rise4fun.com/Alive/wec</a><br></div><br></div><div>Currently, responsibility for reassociative transforms is split between -reassociate and -instcombine. I don't know if that split is intentional or just how the code evolved. Debug stats for test-suite compiled with -O3 show:<br>78K "reassociations" by -instcombine.<br>58K "reassociated" by -reassociate<br></div><div><br>A debug stat with D45842 showed that that transform fired 1.3K times.<br><br></div><div>Keep in mind that instcombine runs 1st, runs to fixed-point, and runs 8 times in the -O2 pipeline. Reassociate runs 1 time and doesn't run to fixed-point. Some transforms are unique to 1 pass or the other, but there is some overlapping functionality already there.<br><br></div><div>So the questions are: <br>1. How do we solve these remaining reassociation optimizations?<br></div><div>2. Do we want to consolidate existing reassociation transforms in 1 pass or is there value in splitting the folds across multiple passes?<br></div><br><div><br><br></div></div>
</blockquote></div>
</div></div><br>______________________________<wbr>_________________<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" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
<br></blockquote></div><br></div></div>