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/20160703/d5870582/attachment.html>
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/20160703/e77c513c/attachment-0001.html>
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>