<html><head><style type="text/css"><!-- DIV {margin:0px;} --></style></head><body><div style="font-family:times new roman,new york,times,serif;font-size:12pt"><div>Hi Nicolas,<br><br>Your example has more expense in that calculation than you may have intended. Why are you trying to divide by 0? It seems to me that that would trigger an exception on any processor I know of. :-) No wonder it's faster to execute in the if statement!<br><br>That being said, would llvm-gcc or clang have a way to figure stuff like that divide by zero out before you execute the code and get the exception?<br><br>--Sam<br></div><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px;"><div style="font-family: times new roman,new york,times,serif; font-size: 12pt;"><br><div style="font-family: times new roman,new york,times,serif; font-size: 12pt;"><font face="Tahoma" size="2"><b><span style="font-weight:
bold;">From:</span></b> Chris Lattner <clattner@apple.com><br><b><span style="font-weight: bold;">To:</span></b> Nicolas Capens <nicolas@capens.net><br><b><span style="font-weight: bold;">Cc:</span></b> LLVM Developers Mailing List <llvmdev@cs.uiuc.edu><br><b><span style="font-weight: bold;">Sent:</span></b> Wed, October 14, 2009 10:22:53 AM<br><b><span style="font-weight: bold;">Subject:</span></b> Re: [LLVMdev] Moving dependent code into conditional statements<br></font><br>
<meta http-equiv="x-dns-prefetch-control" content="off"><base><br><div><div>On Oct 14, 2009, at 12:21 AM, Nicolas Capens wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; font-family: Helvetica; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px;"><div lang="EN-US"><div class="Section1"><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;">Hi all,</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;"> </div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;">Is there any existing optimization pass that will move as much code into the body of a forward branch as possible?
Consider the following example:</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;"></div></div></div></span></blockquote><div><br></div><div>Hi Nicolas,</div><div><br></div><div>Instcombine does this in simple cases (see "See if we can trivially sink this instruction to a successor basic block.") but it misses this case because the if gets folded into a select early. It was also not handling the "phi use" case very aggressively, which I fixed in r84103. We now sink the divide and add in this example:</div><div><br></div><div><div>int foo(int x)</div><div>{</div><div> for(int i = 0; i < 1000000; i++)</div><div> {</div><div> int y = (x + 1) / x; // Expensive calculation! Result written to memory.</div><div> </div><div> if(x == 0) // Forward branch</div><div>
{</div><div>bar();</div><div> x = y; // Body</div><div> }</div><div> }</div><div> </div><div> return x;</div><div>}</div><div><br></div></div><div><br></div><div>-Chris</div><div><br></div><br><blockquote type="cite"><div lang="EN-US"><div class="Section1"><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;"> </div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;">int foo(int x)</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;">{</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;"> for(int i = 0; i < 1000000; i++)</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;">
{</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;"> int y = (x + 1) / x; // Expensive calculation! Result written to memory.</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;"> </div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;"> if(x == 0) // Forward branch</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;"> {</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;"> x = y; // Body</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;">
}</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;"> }</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;"> </div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;"> return x;</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;">}</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;"> </div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;">It appears that LLVM compiles this quite literally, performing the expensive calculation a million times. Yet it could be rewritten like this:</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;"> </div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family:
Calibri,sans-serif;">int foo(int x)</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;">{</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;"> for(int i = 0; i < 1000000; i++)</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;"> {</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;"> if(x == 0) // Unlikely to hit</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;"> {</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;"> int y = (x + 1) / x;</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt;
font-family: Calibri,sans-serif;"> x = y;</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;"> }</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;"> }</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;"> </div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;"> return x;</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;">}</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;"> </div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;">This runs way faster.</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt;
font-family: Calibri,sans-serif;"> </div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;">I noticed there’s a loop hoisting optimization (moving as many independent operations out of the body of a backward branch), but I’m looking for its twin. Did I overlook it or is it not yet supported?</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;"> </div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;">Thanks,</div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;"> </div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri,sans-serif;">Nicolas</div></div> _______________________________________________<br>LLVM Developers mailing list<br><a rel="nofollow" ymailto="mailto:LLVMdev@cs.uiuc.edu" target="_blank" href="mailto:LLVMdev@cs.uiuc.edu" style="color:
blue; text-decoration: underline;">LLVMdev@cs.uiuc.edu</a><span class="Apple-converted-space"> </span><span> <a target="_blank" href="http://llvm.cs.uiuc.edu">http://llvm.cs.uiuc.edu</a></span><br><span><a target="_blank" href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a></span><br></div></blockquote></div><br><meta http-equiv="x-dns-prefetch-control" content="on"></div></div></blockquote></div><br>
</body></html>