Sure On Mon, Jul 4, 2016, 9:40 AM Carlos Liam <carlos at aarzee.me> wrote:> 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? > > > - CL > > On Jul 3, 2016, at 7:13 PM, Daniel Berlin <dberlin at dberlin.org> wrote: > > It's going to be really hard to do something sane in the current > infrastructure. > 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. > > > On Mon, Jul 4, 2016, 8:23 AM Carlos Liam <carlos at aarzee.me> wrote: > >> That seems ominous; should I not bother? >> >> - CL >> >> On Jul 3, 2016, at 5:58 PM, Daniel Berlin <dberlin at dberlin.org> wrote: >> >> PropagateEquality in gvn.cpp >> >> 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 :) >> >> On Mon, Jul 4, 2016, 7:51 AM Carlos Liam <carlos at aarzee.me> wrote: >> >>> Where would I look to change the equality propagation? >>> >>> >>> - CL >>> >>> On Jun 30, 2016, at 11:45 PM, Daniel Berlin <dberlin at dberlin.org> wrote: >>> >>> 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. >>> >>> It otherwise would get this >>> >>> On Thu, Jun 30, 2016, 7:41 PM Sean Silva <chisophugis at gmail.com> wrote: >>> >>>> On Thu, Jun 30, 2016 at 6:45 PM, Daniel Berlin via llvm-dev < >>>> llvm-dev at lists.llvm.org> wrote: >>>> >>>>> >>>>> >>>>> On Thu, Jun 30, 2016 at 6:09 PM, Carlos Liam via llvm-dev < >>>>> llvm-dev at lists.llvm.org> wrote: >>>>> >>>>>> Hi all, >>>>>> >>>>>> Consider this C code: >>>>>> >>>>>> #include <stdbool.h> >>>>>> >>>>>> bool func(int n1, int n2, bool b) { >>>>>> bool greater = n1 > n2; >>>>>> if (greater && b) { >>>>>> if (n1 == n2) { >>>>>> return false; // unreachable >>>>>> } >>>>>> } >>>>>> return true; >>>>>> } >>>>>> >>>>>> The line marked unreachable cannot be reached, however currently LLVM >>>>>> does not optimize it out >>>>> >>>>> ????? >>>>> Yes it does. >>>>> >>>> >>>> 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. >>>> >>>> A small modification defeats LLVM's optimizer: >>>> >>>> bool func(int n1, int n2, bool b) { >>>> bool greater = n1 > n2; >>>> if (greater && b) { >>>> foo(); >>>> >>>> if (n1 == n2) { >>>> return false; // unreachable >>>> } >>>> } >>>> return true; >>>> } >>>> >>>> In this case, simplifycfg doesn't go wild merging everything into a >>>> single branch-free expression and so we don't get it. >>>> >>>> >>>> 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. >>>> >>>> I'm not familiar with GVN but it doesn't seem to help for this modified >>>> test case either. >>>> >>>> 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 >>>> >>>> -- Sean Silva >>>> >>>> >>>>> [dannyb at dannyb-macbookpro3 18:39:18] ~/sources/llvm >>>>> (git-svn)-[newgvn-predicates]- :( $ clang -c -emit-llvm ~/greater.c -O1 >>>>> [dannyb at dannyb-macbookpro3 18:39:22] ~/sources/llvm >>>>> (git-svn)-[newgvn-predicates]- :) $ debug-build/bin/llvm-dis greater.bc >>>>> [dannyb at dannyb-macbookpro3 18:39:24] ~/sources/llvm >>>>> (git-svn)-[newgvn-predicates]- :) $ cat greater.ll >>>>> ; Function Attrs: norecurse nounwind readnone ssp uwtable >>>>> define zeroext i1 @func(i32, i32, i1 zeroext) #0 { >>>>> ret i1 true >>>>> } >>>>> >>>>> >>>>> opt -simplifycfg -instcombine does the same thing to it if you use -O0 >>>>> with clang >>>>> >>>>>> >>>>> >>>>> 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. >>>>>> >>>>> >>>>> >>>>> Yes it does. See both GVN's propagateequality and >>>>> correlatedvaluepropagation, among other things :) >>>>> >>>>> In this case, simplifycfg +instcombine will do it >>>>> >>>>> The new predicate support i'm building for GVN will also do it. >>>>> >>>>> >>>>>> >>>>>> I'm interested in creating a patch to remedy this; is there a file or >>>>>> function I should look at? >>>>>> >>>>>> Thanks in advance. >>>>>> >>>>>> - CL >>>>>> _______________________________________________ >>>>>> LLVM Developers mailing list >>>>>> llvm-dev at lists.llvm.org >>>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >>>>>> >>>>> >>>>> >>>>> _______________________________________________ >>>>> LLVM Developers mailing list >>>>> llvm-dev at lists.llvm.org >>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >>>>> >>>>>-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160704/9328d902/attachment.html>
I have this patch to GVN.cpp, but it doesn't seem to be working; any ideas?
diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp
index a963b2f..97d7b4b 100644
--- a/lib/Transforms/Scalar/GVN.cpp
+++ b/lib/Transforms/Scalar/GVN.cpp
@@ -2036,6 +2036,22 @@ bool GVN::propagateEquality(Value *LHS, Value *RHS, const
BasicBlockEdge &Root,
if (RootDominatesEnd)
addToLeaderTable(Num, NotVal, Root.getEnd());
+ // If "A > B" or "A < B", then propagate
"(A == B) == false".
+ if (ICmpInst *ICmp = dyn_cast<ICmpInst>(Cmp)) {
+ if (ICmp->isRelational() &&
+ ((isKnownTrue && Cmp->isFalseWhenEqual()) ||
+ (isKnownFalse && Cmp->isTrueWhenEqual()))) {
+ Worklist.push_back(
+ std::make_pair(CmpInst::Create(
+ Cmp->getOpcode(),
+ CmpInst::Predicate::ICMP_EQ,
+ A,
+ B
+ ), ConstantInt::getFalse(Cmp->getContext()))
+ );
+ }
+ }
+
continue;
}
}
- CL
> On Jul 3, 2016, at 8:40 PM, Daniel Berlin <dberlin at dberlin.org>
wrote:
>
> Sure
>
> On Mon, Jul 4, 2016, 9:40 AM Carlos Liam <carlos at aarzee.me
<mailto:carlos at aarzee.me>> wrote:
> 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?
>
>
> - CL
>
> On Jul 3, 2016, at 7:13 PM, Daniel Berlin <dberlin at dberlin.org
<mailto:dberlin at dberlin.org>> wrote:
>
>> It's going to be really hard to do something sane in the current
infrastructure.
>> 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.
>>
>>
>> On Mon, Jul 4, 2016, 8:23 AM Carlos Liam <carlos at aarzee.me
<mailto:carlos at aarzee.me>> wrote:
>> That seems ominous; should I not bother?
>>
>> - CL
>>
>> On Jul 3, 2016, at 5:58 PM, Daniel Berlin <dberlin at dberlin.org
<mailto:dberlin at dberlin.org>> wrote:
>>
>>> PropagateEquality in gvn.cpp
>>>
>>> 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 :)
>>>
>>> On Mon, Jul 4, 2016, 7:51 AM Carlos Liam <carlos at aarzee.me
<mailto:carlos at aarzee.me>> wrote:
>>> Where would I look to change the equality propagation?
>>>
>>>
>>> - CL
>>>
>>> On Jun 30, 2016, at 11:45 PM, Daniel Berlin <dberlin at
dberlin.org <mailto:dberlin at dberlin.org>> wrote:
>>>
>>>> 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.
>>>>
>>>> It otherwise would get this
>>>>
>>>> On Thu, Jun 30, 2016, 7:41 PM Sean Silva <chisophugis at
gmail.com <mailto:chisophugis at gmail.com>> wrote:
>>>> On Thu, Jun 30, 2016 at 6:45 PM, Daniel Berlin via llvm-dev
<llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>>
wrote:
>>>>
>>>>
>>>> On Thu, Jun 30, 2016 at 6:09 PM, Carlos Liam via llvm-dev
<llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>>
wrote:
>>>> Hi all,
>>>>
>>>> Consider this C code:
>>>>
>>>> #include <stdbool.h>
>>>>
>>>> bool func(int n1, int n2, bool b) {
>>>> bool greater = n1 > n2;
>>>> if (greater && b) {
>>>> if (n1 == n2) {
>>>> return false; // unreachable
>>>> }
>>>> }
>>>> return true;
>>>> }
>>>>
>>>> The line marked unreachable cannot be reached, however
currently LLVM does not optimize it out
>>>> ?????
>>>> Yes it does.
>>>>
>>>> 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.
>>>>
>>>> A small modification defeats LLVM's optimizer:
>>>>
>>>> bool func(int n1, int n2, bool b) {
>>>> bool greater = n1 > n2;
>>>> if (greater && b) {
>>>> foo();
>>>>
>>>> if (n1 == n2) {
>>>> return false; // unreachable
>>>> }
>>>> }
>>>> return true;
>>>> }
>>>>
>>>> In this case, simplifycfg doesn't go wild merging
everything into a single branch-free expression and so we don't get it.
>>>>
>>>>
>>>> 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.
>>>>
>>>> I'm not familiar with GVN but it doesn't seem to help
for this modified test case either.
>>>>
>>>> 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
>>>>
>>>> -- Sean Silva
>>>>
>>>> [dannyb at dannyb-macbookpro3 18:39:18] ~/sources/llvm
(git-svn)-[newgvn-predicates]- :( $ clang -c -emit-llvm ~/greater.c -O1
>>>> [dannyb at dannyb-macbookpro3 18:39:22] ~/sources/llvm
(git-svn)-[newgvn-predicates]- :) $ debug-build/bin/llvm-dis greater.bc
>>>> [dannyb at dannyb-macbookpro3 18:39:24] ~/sources/llvm
(git-svn)-[newgvn-predicates]- :) $ cat greater.ll
>>>> ; Function Attrs: norecurse nounwind readnone ssp uwtable
>>>> define zeroext i1 @func(i32, i32, i1 zeroext) #0 {
>>>> ret i1 true
>>>> }
>>>>
>>>>
>>>> opt -simplifycfg -instcombine does the same thing to it if you
use -O0 with clang
>>>>
>>>> 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.
>>>>
>>>>
>>>> Yes it does. See both GVN's propagateequality and
correlatedvaluepropagation, among other things :)
>>>>
>>>> In this case, simplifycfg +instcombine will do it
>>>>
>>>> The new predicate support i'm building for GVN will also do
it.
>>>>
>>>>
>>>> I'm interested in creating a patch to remedy this; is there
a file or function I should look at?
>>>>
>>>> Thanks in advance.
>>>>
>>>> - CL
>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>
>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
<http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
>>>>
>>>>
>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>
>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
<http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
>>>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160706/e1af26e3/attachment.html>
I've submitted a working patch for review: http://reviews.llvm.org/D22076 <http://reviews.llvm.org/D22076> - CL> On Jul 6, 2016, at 3:09 PM, Carlos Liam via llvm-dev <llvm-dev at lists.llvm.org> wrote: > > I have this patch to GVN.cpp, but it doesn't seem to be working; any ideas? > > diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp > index a963b2f..97d7b4b 100644 > --- a/lib/Transforms/Scalar/GVN.cpp > +++ b/lib/Transforms/Scalar/GVN.cpp > @@ -2036,6 +2036,22 @@ bool GVN::propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root, > if (RootDominatesEnd) > addToLeaderTable(Num, NotVal, Root.getEnd()); > > + // If "A > B" or "A < B", then propagate "(A == B) == false". > + if (ICmpInst *ICmp = dyn_cast<ICmpInst>(Cmp)) { > + if (ICmp->isRelational() && > + ((isKnownTrue && Cmp->isFalseWhenEqual()) || > + (isKnownFalse && Cmp->isTrueWhenEqual()))) { > + Worklist.push_back( > + std::make_pair(CmpInst::Create( > + Cmp->getOpcode(), > + CmpInst::Predicate::ICMP_EQ, > + A, > + B > + ), ConstantInt::getFalse(Cmp->getContext())) > + ); > + } > + } > + > continue; > } > } > > > - CL > >> On Jul 3, 2016, at 8:40 PM, Daniel Berlin <dberlin at dberlin.org <mailto:dberlin at dberlin.org>> wrote: >> >> Sure >> >> On Mon, Jul 4, 2016, 9:40 AM Carlos Liam <carlos at aarzee.me <mailto:carlos at aarzee.me>> wrote: >> 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? >> >> >> - CL >> >> On Jul 3, 2016, at 7:13 PM, Daniel Berlin <dberlin at dberlin.org <mailto:dberlin at dberlin.org>> wrote: >> >>> It's going to be really hard to do something sane in the current infrastructure. >>> 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. >>> >>> >>> On Mon, Jul 4, 2016, 8:23 AM Carlos Liam <carlos at aarzee.me <mailto:carlos at aarzee.me>> wrote: >>> That seems ominous; should I not bother? >>> >>> - CL >>> >>> On Jul 3, 2016, at 5:58 PM, Daniel Berlin <dberlin at dberlin.org <mailto:dberlin at dberlin.org>> wrote: >>> >>>> PropagateEquality in gvn.cpp >>>> >>>> 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 :) >>>> >>>> On Mon, Jul 4, 2016, 7:51 AM Carlos Liam <carlos at aarzee.me <mailto:carlos at aarzee.me>> wrote: >>>> Where would I look to change the equality propagation? >>>> >>>> >>>> - CL >>>> >>>> On Jun 30, 2016, at 11:45 PM, Daniel Berlin <dberlin at dberlin.org <mailto:dberlin at dberlin.org>> wrote: >>>> >>>>> 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. >>>>> >>>>> It otherwise would get this >>>>> >>>>> On Thu, Jun 30, 2016, 7:41 PM Sean Silva <chisophugis at gmail.com <mailto:chisophugis at gmail.com>> wrote: >>>>> On Thu, Jun 30, 2016 at 6:45 PM, Daniel Berlin via llvm-dev <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote: >>>>> >>>>> >>>>> On Thu, Jun 30, 2016 at 6:09 PM, Carlos Liam via llvm-dev <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote: >>>>> Hi all, >>>>> >>>>> Consider this C code: >>>>> >>>>> #include <stdbool.h> >>>>> >>>>> bool func(int n1, int n2, bool b) { >>>>> bool greater = n1 > n2; >>>>> if (greater && b) { >>>>> if (n1 == n2) { >>>>> return false; // unreachable >>>>> } >>>>> } >>>>> return true; >>>>> } >>>>> >>>>> The line marked unreachable cannot be reached, however currently LLVM does not optimize it out >>>>> ????? >>>>> Yes it does. >>>>> >>>>> 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. >>>>> >>>>> A small modification defeats LLVM's optimizer: >>>>> >>>>> bool func(int n1, int n2, bool b) { >>>>> bool greater = n1 > n2; >>>>> if (greater && b) { >>>>> foo(); >>>>> >>>>> if (n1 == n2) { >>>>> return false; // unreachable >>>>> } >>>>> } >>>>> return true; >>>>> } >>>>> >>>>> In this case, simplifycfg doesn't go wild merging everything into a single branch-free expression and so we don't get it. >>>>> >>>>> >>>>> 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. >>>>> >>>>> I'm not familiar with GVN but it doesn't seem to help for this modified test case either. >>>>> >>>>> 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 >>>>> >>>>> -- Sean Silva >>>>> >>>>> [dannyb at dannyb-macbookpro3 18:39:18] ~/sources/llvm (git-svn)-[newgvn-predicates]- :( $ clang -c -emit-llvm ~/greater.c -O1 >>>>> [dannyb at dannyb-macbookpro3 18:39:22] ~/sources/llvm (git-svn)-[newgvn-predicates]- :) $ debug-build/bin/llvm-dis greater.bc >>>>> [dannyb at dannyb-macbookpro3 18:39:24] ~/sources/llvm (git-svn)-[newgvn-predicates]- :) $ cat greater.ll >>>>> ; Function Attrs: norecurse nounwind readnone ssp uwtable >>>>> define zeroext i1 @func(i32, i32, i1 zeroext) #0 { >>>>> ret i1 true >>>>> } >>>>> >>>>> >>>>> opt -simplifycfg -instcombine does the same thing to it if you use -O0 with clang >>>>> >>>>> 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. >>>>> >>>>> >>>>> Yes it does. See both GVN's propagateequality and correlatedvaluepropagation, among other things :) >>>>> >>>>> In this case, simplifycfg +instcombine will do it >>>>> >>>>> The new predicate support i'm building for GVN will also do it. >>>>> >>>>> >>>>> I'm interested in creating a patch to remedy this; is there a file or function I should look at? >>>>> >>>>> Thanks in advance. >>>>> >>>>> - CL >>>>> _______________________________________________ >>>>> LLVM Developers mailing list >>>>> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> >>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev> >>>>> >>>>> >>>>> _______________________________________________ >>>>> LLVM Developers mailing list >>>>> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> >>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev> >>>>> > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160706/f4ab334a/attachment.html>