This is done by partial dead code elimination (PDE), which moves computations forward without them redundant. This was first reported in PLDI 94 (I think) - the basic version is bit-vector based and is O(n^4) in complexity. There is no good SSA version that I am aware of - though there was one which I cant recall at the moment that uses value graphs.<div>
<br></div><div>Vinod</div><div><br><br><div class="gmail_quote">On Wed, Oct 14, 2009 at 10:54 AM, Vikram S. Adve <span dir="ltr"><<a href="mailto:vadve@illinois.edu">vadve@illinois.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div style="word-wrap:break-word"><div class="im"><div>On Oct 14, 2009, at 10:22 AM, Chris Lattner wrote:</div></div><div><div class="im"><br><blockquote type="cite"><div style="word-wrap:break-word"><br><div><div>On Oct 14, 2009, at 12:21 AM, Nicolas Capens wrote:</div>
<br><blockquote type="cite"><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;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><div lang="EN-US" link="blue" vlink="purple">
<div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif">Hi all,</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif">
</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;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-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;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 </div></div></div></blockquote><div><br></div><div><br></div></div><div><span style="font-size:12px">The general version of this looks like classical PRE.</span><br><div><br></div>
<div><span style="font-size:12px"><div style="word-wrap:break-word"><div style="word-wrap:break-word"><div style="word-wrap:break-word"><div style="word-wrap:break-word"><div style="word-wrap:break-word"><span style="font-size:11px"><div style="word-wrap:break-word">
<div style="word-wrap:break-word"><div style="word-wrap:break-word"><div style="word-wrap:break-word"><span style="font-family:Arial;font-size:12px"><div style="word-wrap:break-word"><span style="font-family:Helvetica;font-size:11px"><div style="font-family:Helvetica">
<span style="font-family:Arial"><font size="3"><span style="font-size:12px">--Vikram</span></font></span></div><div><font face="Arial"><i><font size="3"><span style="font-size:12px">Associate Professor, Computer Science</span></font></i></font></div>
<div><font face="Arial"><i><font size="3"><span style="font-size:12px">University of Illinois at Urbana-Champaign</span></font></i></font></div><div><font face="Arial"><i><font size="3"><span style="font-size:12px"><a href="http://llvm.org/~vadve" target="_blank">http://llvm.org/~vadve</a></span></font></i></font></div>
<div><font face="Arial" size="3"><span style="font-size:12px"><i><br></i></span></font></div></span></div></span></div></div></div></div></span></div></div></div></div></div></span></div></div><div><br></div><br><blockquote type="cite">
<div style="word-wrap:break-word"><div><div></div><div class="h5"><div><div>(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" link="blue" vlink="purple"><div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif">
</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif">int foo(int x)</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif">
{</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif"> for(int i = 0; i < 1000000; i++)</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif">
{</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif"> int y = (x + 1) / x; // Expensive calculation! Result written to memory.</div>
<div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif"> </div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif">
if(x == 0) // Forward branch</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif"> {</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif">
x = y; // Body</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif"> }</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif">
}</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif"> </div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif">
return x;</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif">}</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif">
</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;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-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif"> </div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif">
int foo(int x)</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif">{</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif">
for(int i = 0; i < 1000000; i++)</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif"> {</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif">
if(x == 0) // Unlikely to hit</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif"> {</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif">
int y = (x + 1) / x;</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif"> x = y;</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif">
}</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif"> }</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif">
</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif"> return x;</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif">
}</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif"> </div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif">
This runs way faster.</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif"> </div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;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-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif">
</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif">Thanks,</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif">
</div><div style="margin-top:0in;margin-right:0in;margin-bottom:0.0001pt;margin-left:0in;font-size:11pt;font-family:Calibri, sans-serif">Nicolas</div></div>_______________________________________________<br>LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu" style="color:blue;text-decoration:underline" target="_blank">LLVMdev@cs.uiuc.edu</a><span> </span> <a href="http://llvm.cs.uiuc.edu" style="color:blue;text-decoration:underline" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" style="color:blue;text-decoration:underline" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br></div></blockquote></div><br></div></div><span><ATT00001.txt></span></div>
</blockquote></div><br></div><br>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
<br></blockquote></div><br></div>