<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On May 8, 2015, at 10:22 PM, Jingyue Wu <<a href="mailto:jingyue@google.com" class="">jingyue@google.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class=""><div class="">Hi, </div><div class=""><br class=""></div><div class="">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 class=""></div><div class=""><br class=""></div><div class="">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></div></blockquote><div><br class=""></div>I dislike passes that shuffle code for no reason, so regardless of SLSR I agree that LSR should preserve the order of IV users if it’s not too hard. I’m guessing this is just LSR sloppiness.</div><div><br class=""></div><div>Andy</div><div><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class=""><br class=""></div><div class="">More specifically, I ran LSR on</div><div class=""><div class=""><br class=""></div></div><div class=""><div class=""><font face="monospace, monospace" class="">void foo(float *input, int a, int b, int c, int n) {</font></div><div class=""><font face="monospace, monospace" class=""> for (int node_x = 0; node_x < n; ++node_x) {</font></div><div class=""><font face="monospace, monospace" class=""> int pixel_idx = (a + node_x) * b; // {a*b, +, b}</font></div><div class=""><font face="monospace, monospace" class=""> bar(pixel_idx * c); // {a*b*c, +, b*c}</font></div><div class=""><font face="monospace, monospace" class=""> bar((pixel_idx + 1) * c); // {(a*b+1)*c, +, b*c}</font></div><div class=""><font face="monospace, monospace" class=""> bar((pixel_idx + 2) * c); // {(a*b+2)*c, +, b*c}</font></div><div class=""><font face="monospace, monospace" class=""> bar((pixel_idx + 3) * c); // {(a*b+3)*c, +, b*c}</font></div><div class=""><font face="monospace, monospace" class=""> }</font></div><div class=""><font face="monospace, monospace" class="">}</font></div></div><div class=""><br class=""></div><div class="">and LSR produced</div><div class=""><br class=""></div><div class=""><div class=""><font face="monospace, monospace" class="">void foo(float *input, int a, int b, int c, int n) {</font></div><div class=""><b class=""><font face="monospace, monospace" class=""> int arg3 = (a * b + 3) * c;</font></b></div><div class=""><b class=""><font face="monospace, monospace" class=""> int arg2 = (a * b + 2) * c;</font></b></div><div class=""><b class=""><font face="monospace, monospace" class=""> int arg1 = (a * b + 1) * c;</font></b></div><div class=""><b class=""><font face="monospace, monospace" class=""> int arg0 = a * b * c;</font></b></div><div class=""><font face="monospace, monospace" class=""> for (int node_x = 0; node_x < n; ++node_x) {<br class=""></font></div><div class=""><font face="monospace, monospace" class=""> bar(arg0);</font></div><div class=""><font face="monospace, monospace" class=""> bar(arg1);</font></div><div class=""><font face="monospace, monospace" class=""> bar(arg2);</font></div><div class=""><font face="monospace, monospace" class=""> bar(arg3);</font></div><div class=""><font face="monospace, monospace" class=""> arg0 += b * c;</font></div><div class=""><font face="monospace, monospace" class=""> arg1 += b * c;</font></div><div class=""><font face="monospace, monospace" class=""> arg2 += b * c;</font></div><div class=""><font face="monospace, monospace" class=""> arg3 += b * c;</font></div><div class=""><font face="monospace, monospace" class=""> }</font></div><div class=""><font face="monospace, monospace" class="">}</font></div></div><div class="">(with obvious redundant operations, i.e. a * b and b * c, combined). Note that the order of arg0~3 is reversed. </div><div class=""><br class=""></div><div class="">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 class=""><br class=""></div><div class=""><div class="">This creates troubles for SLSR. Given the current order of arg0~arg3<br class=""></div><div class=""><br class=""></div><div class=""><div class=""><div class=""><font face="monospace, monospace" class=""> int arg3 = (a * b + 3) * c;</font></div><div class=""><font face="monospace, monospace" class=""> int arg2 = (a * b + 2) * c;</font></div><div class=""><span style="font-family:monospace,monospace" class=""> int arg1 = (a * b + 1) * c;</span><br class=""></div><div class=""><font face="monospace, monospace" class=""> int arg0 = a * b * c;</font></div><div class=""><br class=""></div></div></div><div class="">SLSR optimizes them to</div><div class=""><br class=""></div><div class=""><font face="monospace, monospace" class=""> int arg3 = (a * b + 3) * c;</font></div><div class=""><font face="monospace, monospace" class=""> int arg2 = arg3 - c;</font></div><div class=""><font face="monospace, monospace" class=""> int arg1 = arg2 - c;</font></div><div class=""><font face="monospace, monospace" class=""> int arg0 = arg1 - c;</font></div><div class=""><font face="monospace, monospace" class=""> // 2 muls and 4 adds/subs</font></div><div class=""><br class=""></div><div class="">In contrast, if arg0~3 were in the order of </div><div class=""><br class=""></div><div class=""><div class=""><font face="monospace, monospace" class=""> int arg0 = a * b * c;</font></div><div class=""><span style="font-family:monospace,monospace" class=""> int arg1 = (a * b + 1) * c;</span><br class=""></div><div class=""><font face="monospace, monospace" class=""> int arg2 = (a * b + 2) * c;</font></div><div class=""><div class=""><font face="monospace, monospace" class=""> int arg3 = (a * b + 3) * c;</font></div></div></div><div class=""><font face="monospace, monospace" class=""><br class=""></font></div><div class=""><font face="arial, helvetica, sans-serif" class="">SLSR would optimize them to</font></div><div class=""><font face="arial, helvetica, sans-serif" class=""><br class=""></font></div><font face="monospace, monospace" class=""> int arg0 = a * b * c;<br class=""> int arg1 = arg0 + c;<br class=""> int arg2 = arg1 + c;<br class=""> int arg3 = arg2 + c;<br class=""> // 2 muls and 3 adds/subs. 1 add/sub less than with the reversed order<br class=""></font><div class=""><font face="arial, helvetica, sans-serif" class=""><br class=""></font></div>I have a proof-of-concept patch (<a href="http://reviews.llvm.org/differential/diff/25402/" class="">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><div class=""><br class=""></div><div class="">Jingyue</div></div>
</div></blockquote></div><br class=""></body></html>