<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">I've submitted a working patch for review: <a href="http://reviews.llvm.org/D22076" class="">http://reviews.llvm.org/D22076</a><br class=""><div class="">
<br class="Apple-interchange-newline"><span style="color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; display: inline !important; float: none;" class=""> - CL</span>
</div>
<br class=""><div style=""><blockquote type="cite" class=""><div class="">On Jul 6, 2016, at 3:09 PM, Carlos Liam via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><meta http-equiv="Content-Type" content="text/html charset=us-ascii" class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">I have this patch to GVN.cpp, but it doesn't seem to be working; any ideas?<div class=""><br class=""></div><div class=""><div class="">diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp</div><div class="">index a963b2f..97d7b4b 100644</div><div class="">--- a/lib/Transforms/Scalar/GVN.cpp</div><div class="">+++ b/lib/Transforms/Scalar/GVN.cpp</div><div class="">@@ -2036,6 +2036,22 @@ bool GVN::propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,</div><div class=""> if (RootDominatesEnd)</div><div class=""> addToLeaderTable(Num, NotVal, Root.getEnd());</div><div class=""> </div><div class="">+ // If "A > B" or "A < B", then propagate "(A == B) == false".</div><div class="">+ if (ICmpInst *ICmp = dyn_cast<ICmpInst>(Cmp)) {</div><div class="">+ if (ICmp->isRelational() &&</div><div class="">+ ((isKnownTrue && Cmp->isFalseWhenEqual()) ||</div><div class="">+ (isKnownFalse && Cmp->isTrueWhenEqual()))) {</div><div class="">+ Worklist.push_back(</div><div class="">+ std::make_pair(CmpInst::Create(</div><div class="">+ Cmp->getOpcode(),</div><div class="">+ CmpInst::Predicate::ICMP_EQ,</div><div class="">+ A,</div><div class="">+ B</div><div class="">+ ), ConstantInt::getFalse(Cmp->getContext()))</div><div class="">+ );</div><div class="">+ }</div><div class="">+ }</div><div class="">+</div><div class=""> continue;</div><div class=""> }</div><div class=""> }</div><div class=""><br class=""></div><div class="">
<br class="Apple-interchange-newline"><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-ligatures: normal; font-variant-position: normal; font-variant-caps: normal; font-variant-numeric: normal; font-variant-alternates: normal; font-variant-east-asian: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class=""> - CL</span>
</div>
<br class=""><div class=""><blockquote type="cite" class=""><div class="">On Jul 3, 2016, at 8:40 PM, Daniel Berlin <<a href="mailto:dberlin@dberlin.org" class="">dberlin@dberlin.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class="">Sure<br class=""><br class=""><div class="gmail_quote"><div dir="ltr" class="">On Mon, Jul 4, 2016, 9:40 AM Carlos Liam <<a href="mailto:carlos@aarzee.me" class="">carlos@aarzee.me</a>> wrote:<br class=""></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto" class=""><div class="">It looks like there's already something similar in PropagateEquality which eg X >= Y == true and replaces X < Y == false, which is somewhat similar - could I base an addition off of that?</div></div><div dir="auto" class=""><div class=""><br class=""><br class=""> - CL</div></div><div dir="auto" class=""><div class=""><br class="">On Jul 3, 2016, at 7:13 PM, Daniel Berlin <<a href="mailto:dberlin@dberlin.org" target="_blank" class="">dberlin@dberlin.org</a>> wrote:<br class=""><br class=""></div><blockquote type="cite" class=""><div class=""><span class="">It's going to be really hard to do something sane in the current infrastructure.</span><div class="">Its possible, but it would also be slow. You would have to go looking at uses of variables compared in predicates in PropagateEquality and if the uses appear in a comparison that is dominated by the true or false edge of the existing predicate, see if it tells you something about the dominated one.</div><div class=""><br class=""></div><div class=""><div class=""><br class=""><div class="gmail_quote"><div dir="ltr" class="">On Mon, Jul 4, 2016, 8:23 AM Carlos Liam <<a href="mailto:carlos@aarzee.me" target="_blank" class="">carlos@aarzee.me</a>> wrote:<br class=""></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto" class=""><div class="">That seems ominous; should I not bother?</div></div><div dir="auto" class=""><div id="m_-6154320455394911140m_564001926625395306AppleMailSignature" class=""><br class=""> - CL</div></div><div dir="auto" class=""><div class=""><br class="">On Jul 3, 2016, at 5:58 PM, Daniel Berlin <<a href="mailto:dberlin@dberlin.org" target="_blank" class="">dberlin@dberlin.org</a>> wrote:<br class=""><br class=""></div><blockquote type="cite" class=""><div class="">PropagateEquality in gvn.cpp<div class=""><br class=""></div><div class="">However, if you are going to do it, remember the goal is to make the code simpler and easier, not just pile on to the current mess to catch more cases :)<br class=""><br class=""><div class="gmail_quote"><div dir="ltr" class="">On Mon, Jul 4, 2016, 7:51 AM Carlos Liam <<a href="mailto:carlos@aarzee.me" target="_blank" class="">carlos@aarzee.me</a>> wrote:<br class=""></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto" class=""><div class="">Where would I look to change the equality propagation?</div></div><div dir="auto" class=""><div class=""><br class=""><br class=""> - CL</div></div><div dir="auto" class=""><div class=""><br class="">On Jun 30, 2016, at 11:45 PM, Daniel Berlin <<a href="mailto:dberlin@dberlin.org" target="_blank" class="">dberlin@dberlin.org</a>> wrote:<br class=""><br class=""></div><blockquote type="cite" class=""><div class=""><div dir="ltr" class="">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" class=""><br class=""></div><div dir="ltr" class="">It otherwise would get this</div><span class="">
</span><br class=""><div class="gmail_quote"><div dir="ltr" class="">On Thu, Jun 30, 2016, 7:41 PM Sean Silva <<a href="mailto:chisophugis@gmail.com" target="_blank" class="">chisophugis@gmail.com</a>> wrote:<br class=""></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class=""><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" class=""><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>></span> wrote:<br class=""><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" class=""><br class=""><div class="gmail_extra"><br class=""><div class="gmail_quote"><span class="">On Thu, Jun 30, 2016 at 6:09 PM, Carlos Liam via llvm-dev <span dir="ltr" class=""><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>></span> wrote:<br class=""><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 class="">
<br class="">
Consider this C code:<br class="">
<br class="">
#include <stdbool.h><br class="">
<br class="">
bool func(int n1, int n2, bool b) {<br class="">
bool greater = n1 > n2;<br class="">
if (greater && b) {<br class="">
if (n1 == n2) {<br class="">
return false; // unreachable<br class="">
}<br class="">
}<br class="">
return true;<br class="">
}<br class="">
<br class="">
The line marked unreachable cannot be reached, however currently LLVM does not optimize it out</blockquote></span><div class="">?????<br class="">Yes it does.</div></div></div></div></blockquote><div class=""><br class=""></div></div></div></div><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><div class="">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 class=""><br class=""></div><div class=""><div class="">A small modification defeats LLVM's optimizer:</div></div></div></div></div><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><div class=""><div class=""><br class=""></div><div class=""><span style="font-size:12.8px" class="">bool func(int n1, int n2, bool b) {</span><br style="font-size:12.8px" class=""><span style="font-size:12.8px" class=""> bool greater = n1 > n2;</span><br style="font-size:12.8px" class=""><span style="font-size:12.8px" class=""> if (greater && b) {</span></div></div></div></div></div><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><div class=""><div class=""><span style="font-size:12.8px" class=""> foo();</span></div></div></div></div></div><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><div class=""><div class=""><br style="font-size:12.8px" class=""><span style="font-size:12.8px" class=""> if (n1 == n2) {</span><br style="font-size:12.8px" class=""><span style="font-size:12.8px" class=""> return false; // unreachable</span><br style="font-size:12.8px" class=""><span style="font-size:12.8px" class=""> }</span><br style="font-size:12.8px" class=""><span style="font-size:12.8px" class=""> }</span><br style="font-size:12.8px" class=""><span style="font-size:12.8px" class=""> return true;</span><br style="font-size:12.8px" class=""><span style="font-size:12.8px" class="">}</span><br class=""></div></div></div></div></div><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><div class=""><div class=""></div><div class=""><span style="font-size:12.8px" class=""><br class=""></span></div><div class=""><span style="font-size:12.8px" class="">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 class=""><span style="font-size:12.8px" class=""><br class=""></span></div><div class=""><br class=""></div><div class="">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 class=""><br class=""></div><div class="">I'm not familiar with GVN but it doesn't seem to help for this modified test case either.</div><div class=""><br class=""></div><div class="">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" class=""><div class="gmail_extra"><div class="gmail_quote"><div class=""><br class=""></div><div class=""><span style="font-size:12.8px" class="">-- Sean Silva</span></div></div></div></div><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><div class=""> </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" class=""><div class="gmail_extra"><div class="gmail_quote"><div class=""><div class="">[dannyb@dannyb-macbookpro3 18:39:18] ~/sources/llvm (git-svn)-[newgvn-predicates]- :( $ clang -c -emit-llvm ~/greater.c -O1</div><div class="">[dannyb@dannyb-macbookpro3 18:39:22] ~/sources/llvm (git-svn)-[newgvn-predicates]- :) $ debug-build/bin/llvm-dis greater.bc</div><div class="">[dannyb@dannyb-macbookpro3 18:39:24] ~/sources/llvm (git-svn)-[newgvn-predicates]- :) $ cat greater.ll</div></div><div class="">; Function Attrs: norecurse nounwind readnone ssp uwtable</div><div class="">define zeroext i1 @func(i32, i32, i1 zeroext) #0 {</div><div class=""> ret i1 true</div><div class="">} </div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">opt -simplifycfg -instcombine does the same thing to it if you use -O0 with clang </div><span class=""><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 class=""></blockquote><div class=""><br class=""></div><div class=""><br class=""></div></span><div class="">Yes it does. See both GVN's propagateequality and correlatedvaluepropagation, among other things :)</div><div class=""><br class=""></div><div class="">In this case, simplifycfg +instcombine will do it</div><div class=""><br class=""></div><div class="">The new predicate support i'm building for GVN will also do it.</div><span class=""><div class=""> <br class=""></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 class="">
I'm interested in creating a patch to remedy this; is there a file or function I should look at?<br class="">
<br class="">
Thanks in advance.<br class="">
<br class="">
- CL<br class="">
_______________________________________________<br class="">
LLVM Developers mailing list<br class="">
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a><br class="">
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank" class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br class="">
</blockquote></span></div><br class=""></div></div>
<br class="">_______________________________________________<br class="">
LLVM Developers mailing list<br class="">
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a><br class="">
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank" class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br class="">
<br class=""></blockquote></div></div></div></blockquote></div>
</div></blockquote></div></blockquote></div></div>
</div></blockquote></div></blockquote></div></div></div>
</div></blockquote></div></blockquote></div>
</div></blockquote></div><br class=""></div></div>_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a><br class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev<br class=""></div></blockquote></div><br class=""></body></html>