<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jun 30, 2016 at 8:45 PM, Daniel Berlin <span dir="ltr"><<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.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">The current gvn equality propagation is not powerful enough to get this because it doesn't try to infer values in predicates based on other predicates, so it never realizes a>b -> a !=b in a useful way.</div><div dir="ltr"><br></div><div dir="ltr">It otherwise would get this</div></blockquote><div><br></div><div>Sorry if this is a bit of a stupid question, but what exactly is the scope of what a GVN pass does?</div><div><br></div><div>I've read various "textbook" definitions of GVN but they all seem to revolve around proving that different expressions in the program are equivalent. What you're talking about here seems to go outside that; e.g. being more like what one would expect CorrelatedValuePropagation to do.</div><div><br></div><div>-- Sean Silva</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="HOEnZb"><div class="h5"><span>
</span><br><div class="gmail_quote"><div dir="ltr">On Thu, Jun 30, 2016, 7:41 PM Sean Silva <<a href="mailto:chisophugis@gmail.com" target="_blank">chisophugis@gmail.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 class="gmail_extra"><div class="gmail_quote">On Thu, Jun 30, 2016 at 6:45 PM, Daniel Berlin 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:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote"><span>On Thu, Jun 30, 2016 at 6:09 PM, Carlos Liam 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:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">Hi all,<br>
<br>
Consider this C code:<br>
<br>
#include <stdbool.h><br>
<br>
bool func(int n1, int n2, bool b) {<br>
bool greater = n1 > n2;<br>
if (greater && b) {<br>
if (n1 == n2) {<br>
return false; // unreachable<br>
}<br>
}<br>
return true;<br>
}<br>
<br>
The line marked unreachable cannot be reached, however currently LLVM does not optimize it out</blockquote></span><div>?????<br>Yes it does.</div></div></div></div></blockquote><div><br></div></div></div></div><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div>It seems like we get this almost by accident though. I find that I need `-mem2reg -instcombine -simplifycfg -instcombine` (on clang -O0 IR; the `-mem2reg -instcombine` are just cleanup) and essentially it boils down to simplifycfg merging everything into a single branch-free expression and then instcombine algebraically merging the comparisons.</div><div><br></div><div><div>A small modification defeats LLVM's optimizer:</div></div></div></div></div><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div><div><br></div><div><span style="font-size:12.8px">bool func(int n1, int n2, bool b) {</span><br style="font-size:12.8px"><span style="font-size:12.8px"> bool greater = n1 > n2;</span><br style="font-size:12.8px"><span style="font-size:12.8px"> if (greater && b) {</span></div></div></div></div></div><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div><div><span style="font-size:12.8px"> foo();</span></div></div></div></div></div><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div><div><br style="font-size:12.8px"><span style="font-size:12.8px"> if (n1 == n2) {</span><br style="font-size:12.8px"><span style="font-size:12.8px"> return false; // unreachable</span><br style="font-size:12.8px"><span style="font-size:12.8px"> }</span><br style="font-size:12.8px"><span style="font-size:12.8px"> }</span><br style="font-size:12.8px"><span style="font-size:12.8px"> return true;</span><br style="font-size:12.8px"><span style="font-size:12.8px">}</span><br></div></div></div></div></div><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div><div></div><div><span style="font-size:12.8px"><br></span></div><div><span style="font-size:12.8px">In this case, simplifycfg doesn't go wild merging everything into a single branch-free expression and so we don't get it.</span></div></div><div><span style="font-size:12.8px"><br></span></div><div><br></div><div>CorrelatedValuePropagation doesn't get this because its processCmp is quite weak (it bails out if one operand isn't a constant). JumpThreading is the only other pass that uses LazyValueInfo and it can't fold this since it can't thread a jump around the side-effecting `foo()` call.</div><div><br></div><div>I'm not familiar with GVN but it doesn't seem to help for this modified test case either.</div><div><br></div><div>Carlos, in answer to your original question, you may want to see if you can make LLVM get this case by modifying processCmp in lib/Transforms/Scalar/CorrelatedValuePropagation.cpp</div></div></div></div><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div><br></div><div><span style="font-size:12.8px">-- Sean Silva</span></div></div></div></div><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div><div>[dannyb@dannyb-macbookpro3 18:39:18] ~/sources/llvm (git-svn)-[newgvn-predicates]- :( $ clang -c -emit-llvm ~/greater.c -O1</div><div>[dannyb@dannyb-macbookpro3 18:39:22] ~/sources/llvm (git-svn)-[newgvn-predicates]- :) $ debug-build/bin/llvm-dis greater.bc</div><div>[dannyb@dannyb-macbookpro3 18:39:24] ~/sources/llvm (git-svn)-[newgvn-predicates]- :) $ cat greater.ll</div></div><div>; Function Attrs: norecurse nounwind readnone ssp uwtable</div><div>define zeroext i1 @func(i32, i32, i1 zeroext) #0 {</div><div> ret i1 true</div><div>} </div><div><br></div><div><br></div><div>opt -simplifycfg -instcombine does the same thing to it if you use -O0 with clang </div><span><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"> </blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"> I believe this is because LLVM does not recognize that meeting path conditions like, for example, X && Y logically means that X is true and Y is true.<br></blockquote><div><br></div><div><br></div></span><div>Yes it does. See both GVN's propagateequality and correlatedvaluepropagation, among other things :)</div><div><br></div><div>In this case, simplifycfg +instcombine will do it</div><div><br></div><div>The new predicate support i'm building for GVN will also do it.</div><span><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<br>
I'm interested in creating a patch to remedy this; is there a file or function I should look at?<br>
<br>
Thanks in advance.<br>
<br>
- CL<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">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/mailman/listinfo/llvm-dev</a><br>
</blockquote></span></div><br></div></div>
<br>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">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/mailman/listinfo/llvm-dev</a><br>
<br></blockquote></div></div></div></blockquote></div>
</div></div></blockquote></div><br></div></div>