<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><div>Where would I look to change the equality propagation?<br><br> - CL</div><div><br>On Jun 30, 2016, at 11:45 PM, Daniel Berlin <<a href="mailto:dberlin@dberlin.org">dberlin@dberlin.org</a>> wrote:<br><br></div><blockquote type="cite"><div><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><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">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></blockquote></body></html>