<div dir="ltr">Thoughts? </div><div class="gmail_extra"><br><div class="gmail_quote">On Fri, May 8, 2015 at 10:22 PM, Jingyue Wu <span dir="ltr"><<a href="mailto:jingyue@google.com" target="_blank">jingyue@google.com</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>Hi, </div><div><br></div><div>I was tracking down a performance regression and noticed that LoopStrengthReduce hoists loop invariants (e.g., the initial formulae of indvars) in the reverse order of how they appear in the loop. <br></div><div><br></div><div>This reverse order creates troubles for the StraightLineStrengthReduce pass I recently add. While I understand ultimately SLSR should be able to sort independent candidates in an optimal order, does it make sense to canonicalizing the order of LSR-hoisted loop invariants back to the "natural" order? IMO, the optimized code should in general resemble the original code unless intentionally changed otherwise. </div><div><br></div><div>More specifically, I ran LSR on</div><div><div><br></div></div><div><div><font face="monospace, monospace">void foo(float *input, int a, int b, int c, int n) {</font></div><div><font face="monospace, monospace"> for (int node_x = 0; node_x < n; ++node_x) {</font></div><div><font face="monospace, monospace"> int pixel_idx = (a + node_x) * b; // {a*b, +, b}</font></div><div><font face="monospace, monospace"> bar(pixel_idx * c); // {a*b*c, +, b*c}</font></div><div><font face="monospace, monospace"> bar((pixel_idx + 1) * c); // {(a*b+1)*c, +, b*c}</font></div><div><font face="monospace, monospace"> bar((pixel_idx + 2) * c); // {(a*b+2)*c, +, b*c}</font></div><div><font face="monospace, monospace"> bar((pixel_idx + 3) * c); // {(a*b+3)*c, +, b*c}</font></div><div><font face="monospace, monospace"> }</font></div><div><font face="monospace, monospace">}</font></div></div><div><br></div><div>and LSR produced</div><div><br></div><div><div><font face="monospace, monospace">void foo(float *input, int a, int b, int c, int n) {</font></div><div><b><font face="monospace, monospace"> int arg3 = (a * b + 3) * c;</font></b></div><div><b><font face="monospace, monospace"> int arg2 = (a * b + 2) * c;</font></b></div><div><b><font face="monospace, monospace"> int arg1 = (a * b + 1) * c;</font></b></div><div><b><font face="monospace, monospace"> int arg0 = a * b * c;</font></b></div><div><font face="monospace, monospace"> for (int node_x = 0; node_x < n; ++node_x) {<br></font></div><div><font face="monospace, monospace"> bar(arg0);</font></div><div><font face="monospace, monospace"> bar(arg1);</font></div><div><font face="monospace, monospace"> bar(arg2);</font></div><div><font face="monospace, monospace"> bar(arg3);</font></div><div><font face="monospace, monospace"> arg0 += b * c;</font></div><div><font face="monospace, monospace"> arg1 += b * c;</font></div><div><font face="monospace, monospace"> arg2 += b * c;</font></div><div><font face="monospace, monospace"> arg3 += b * c;</font></div><div><font face="monospace, monospace"> }</font></div><div><font face="monospace, monospace">}</font></div></div><div>(with obvious redundant operations, i.e. a * b and b * c, combined). Note that the order of arg0~3 is reversed. </div><div><br></div><div>Reversing the order of arg0~3 is not intentional. The user list of pixel_idx happens to have pixel_idx+3, pixel_idx+2, and pixel_idx+1 in this order, so LSR simply follows this order when collecting the LSRFixups. </div><div><br></div><div><div>This creates troubles for SLSR. Given the current order of arg0~arg3<br></div><div><br></div><div><div><div><font face="monospace, monospace"> int arg3 = (a * b + 3) * c;</font></div><div><font face="monospace, monospace"> int arg2 = (a * b + 2) * c;</font></div><div><span style="font-family:monospace,monospace"> int arg1 = (a * b + 1) * c;</span><br></div><div><font face="monospace, monospace"> int arg0 = a * b * c;</font></div><div><br></div></div></div><div>SLSR optimizes them to</div><div><br></div><div><font face="monospace, monospace"> int arg3 = (a * b + 3) * c;</font></div><div><font face="monospace, monospace"> int arg2 = arg3 - c;</font></div><div><font face="monospace, monospace"> int arg1 = arg2 - c;</font></div><div><font face="monospace, monospace"> int arg0 = arg1 - c;</font></div><div><font face="monospace, monospace"> // 2 muls and 4 adds/subs</font></div><div><br></div><div>In contrast, if arg0~3 were in the order of </div><div><br></div><div><div><font face="monospace, monospace"> int arg0 = a * b * c;</font></div><div><span style="font-family:monospace,monospace"> int arg1 = (a * b + 1) * c;</span><br></div><div><font face="monospace, monospace"> int arg2 = (a * b + 2) * c;</font></div><div><div><font face="monospace, monospace"> int arg3 = (a * b + 3) * c;</font></div></div></div><div><font face="monospace, monospace"><br></font></div><div><font face="arial, helvetica, sans-serif">SLSR would optimize them to</font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><font face="monospace, monospace"> int arg0 = a * b * c;<br> int arg1 = arg0 + c;<br> int arg2 = arg1 + c;<br> int arg3 = arg2 + c;<br> // 2 muls and 3 adds/subs. 1 add/sub less than with the reversed order<br></font><div><font face="arial, helvetica, sans-serif"><br></font></div>I have a proof-of-concept patch (<a href="http://reviews.llvm.org/differential/diff/25402/" target="_blank">http://reviews.llvm.org/differential/diff/25402/</a>) that has CollectFixupsAndInitialFormulae to sort initial formulae in a dominance order (i.e. if A.getUser() dominates B.getUser(), then we put A before B). It breaks some tests that are too sensitive to order changes; besides that, I don't see significant issues. </div><span class="HOEnZb"><font color="#888888"><div><br></div><div>Jingyue</div></font></span></div>
</blockquote></div><br></div>