Message ID | trinity-6f9490aa-8fd5-4347-8e27-0f07fdb2a3ac-1534777649342@3c-app-mailcom-bs06 |
---|---|
State | New |
Headers | show |
Series | Optimize more boolean functions | expand |
On Mon, 20 Aug 2018, MCC CS wrote: > this patch optimizes ~(~x | y), (~x | y) & (x | ~y) and > (~x | y) ^ (x | ~y). Thank you. I didn't mean to force you to add the extra transformations to your patch, but now that they are here, that's good :-) > gcc/ > PR tree-optimization/87009 > * match.pd: Improve boolean optimizations (maybe the mailer ate the initial TAB) "." at the end of the description. Maybe "new" instead of "improve" since you are adding new transformations and not modifying existing ones. Some people list the patterns in parentheses here, but not all, so I guess that's ok. > gcc/testsuite/ > PR tree-optimization/87009 > * gcc.dg/pr87009.c: Add boolean optimization tests You can simply go with "New file." or "New test.", like most entries in this ChangeLog, though the longer version is ok. > Index: gcc/match.pd > =================================================================== > --- gcc/match.pd (revision 263646) > +++ gcc/match.pd (working copy) > @@ -776,6 +776,11 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) > (bit_not (bit_and:cs (bit_not @0) @1)) > (bit_ior @0 (bit_not @1))) > > +/* ~(~a | b) --> a & ~b */ > +(simplify > + (bit_not (bit_ior:cs (bit_not @0) @1)) > + (bit_and @0 (bit_not @1))) > + > /* Simplify (~X & Y) to X ^ Y if we know that (X & ~Y) is 0. */ > #if GIMPLE > (simplify > @@ -981,6 +986,16 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) > (bit_and:c (bit_ior:c @0 @1) (bit_xor:c @1 (bit_not @0))) > (bit_and @0 @1)) > > +/* (~x | y) & (x | ~y) -> ~(x ^ y) */ > +(simplify > + (bit_and (bit_ior:c (bit_not @0) @1) (bit_ior:c @0 (bit_not @1))) > + (bit_not (bit_xor @0 @1))) > + > +/* (~x | y) ^ (x | ~y) -> x ^ y */ > +(simplify > + (bit_xor (bit_ior:c (bit_not @0) @1) (bit_ior:c @0 (bit_not @1))) > + (bit_xor @0 @1)) > + For what it's worth, I think that's good, though you need to wait for an official reviewer. (I wondered about a single_use check on the second transformation, but I hope it isn't needed) > /* ~x & ~y -> ~(x | y) > ~x | ~y -> ~(x & y) */ > (for op (bit_and bit_ior) > Index: gcc/testsuite/gcc.dg/pr87009.c > =================================================================== > --- gcc/testsuite/gcc.dg/pr87009.c (nonexistent) > +++ gcc/testsuite/gcc.dg/pr87009.c (working copy) > @@ -0,0 +1,23 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O2 -fdump-tree-original" } */ If -O is sufficient, that would be better. > +/* { dg-final { scan-tree-dump-times " \\^ " 4 "original" } } */ You may also want to check that there are no unexpected &|~ , to be sure that you are getting the expected output. > + > +int f1 (int x, int s) > +{ > + return ~(~(x|s)|x)|~(~(x|s)|s); > +} > + > +int f2 (int x, int s) > +{ > + return ~(~(~x&s)&~(x&~s)); > +} > + > +int f3 (int x, int s) > +{ > + return ~((x|~s)&(~x|s)); > +} > + > +int f4 (int x, int s) > +{ > + return (~x|s)&(x|~s); > +} >
Hello all, I have updated the testcase and run "make check" on Ubuntu x86_64. All of them passed. (However the last part "do-check" couldn't be run, probably due to a missing testsuite dependency?) The match.pd is the same as the original patch, and I have updated change-summaries and improved tests. 2018-08-21 MCC CS <deswurstes@users.noreply.github.com> gcc/ PR tree-optimization/87009 * match.pd: Add boolean optimizations. 2018-08-21 MCC CS <deswurstes@users.noreply.github.com> gcc/testsuite/ PR tree-optimization/87009 * gcc.dg/pr87009.c: New test. Index: gcc/match.pd =================================================================== --- gcc/match.pd (revision 263646) +++ gcc/match.pd (working copy) @@ -776,6 +776,11 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (bit_not (bit_and:cs (bit_not @0) @1)) (bit_ior @0 (bit_not @1))) +/* ~(~a | b) --> a & ~b */ +(simplify + (bit_not (bit_ior:cs (bit_not @0) @1)) + (bit_and @0 (bit_not @1))) + /* Simplify (~X & Y) to X ^ Y if we know that (X & ~Y) is 0. */ #if GIMPLE (simplify @@ -981,6 +986,16 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (bit_and:c (bit_ior:c @0 @1) (bit_xor:c @1 (bit_not @0))) (bit_and @0 @1)) +/* (~x | y) & (x | ~y) -> ~(x ^ y) */ +(simplify + (bit_and (bit_ior:c (bit_not @0) @1) (bit_ior:c @0 (bit_not @1))) + (bit_not (bit_xor @0 @1))) + +/* (~x | y) ^ (x | ~y) -> x ^ y */ +(simplify + (bit_xor (bit_ior:c (bit_not @0) @1) (bit_ior:c @0 (bit_not @1))) + (bit_xor @0 @1)) + /* ~x & ~y -> ~(x | y) ~x | ~y -> ~(x & y) */ (for op (bit_and bit_ior) Index: gcc/testsuite/gcc.dg/pr87009.c =================================================================== --- gcc/testsuite/gcc.dg/pr87009.c (nonexistent) +++ gcc/testsuite/gcc.dg/pr87009.c (working copy) @@ -0,0 +1,23 @@ +/* { dg-do compile } */ +/* { dg-options "-O -fdump-tree-original" } */ +/* { dg-final { scan-tree-dump-times "return s \\^ x;" 4 "original" } } */ + +int f1 (int x, int s) +{ + return ~(~(x|s)|x)|~(~(x|s)|s); +} + +int f2 (int x, int s) +{ + return ~(~(~x&s)&~(x&~s)); +} + +int f3 (int x, int s) +{ + return ~((x|~s)&(~x|s)); +} + +int f4 (int x, int s) +{ + return (x|~s)^(~x|s); +}
On Tue, Aug 21, 2018 at 7:20 PM MCC CS <mcccs@gmx.com> wrote: > > Hello all, > > I have updated the testcase and run "make check" on Ubuntu x86_64. > All of them passed. (However the last part "do-check" couldn't be > run, probably due to a missing testsuite dependency?) > > The match.pd is the same as the original patch, and I have > updated change-summaries and improved tests. > > 2018-08-21 MCC CS <deswurstes@users.noreply.github.com> > > gcc/ > PR tree-optimization/87009 > * match.pd: Add boolean optimizations. > > 2018-08-21 MCC CS <deswurstes@users.noreply.github.com> > > gcc/testsuite/ > PR tree-optimization/87009 > * gcc.dg/pr87009.c: New test. > > Index: gcc/match.pd > =================================================================== > --- gcc/match.pd (revision 263646) > +++ gcc/match.pd (working copy) > @@ -776,6 +776,11 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) > (bit_not (bit_and:cs (bit_not @0) @1)) > (bit_ior @0 (bit_not @1))) > > +/* ~(~a | b) --> a & ~b */ > +(simplify > + (bit_not (bit_ior:cs (bit_not @0) @1)) > + (bit_and @0 (bit_not @1))) > + > /* Simplify (~X & Y) to X ^ Y if we know that (X & ~Y) is 0. */ > #if GIMPLE > (simplify > @@ -981,6 +986,16 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) > (bit_and:c (bit_ior:c @0 @1) (bit_xor:c @1 (bit_not @0))) > (bit_and @0 @1)) > > +/* (~x | y) & (x | ~y) -> ~(x ^ y) */ > +(simplify > + (bit_and (bit_ior:c (bit_not @0) @1) (bit_ior:c @0 (bit_not @1))) Please add single-use markers after the existing 'c' markers of the bit_ior's > + (bit_not (bit_xor @0 @1))) > + > +/* (~x | y) ^ (x | ~y) -> x ^ y */ > +(simplify > + (bit_xor (bit_ior:c (bit_not @0) @1) (bit_ior:c @0 (bit_not @1))) > + (bit_xor @0 @1)) Likewise. OK with that change. Richard. > + > /* ~x & ~y -> ~(x | y) > ~x | ~y -> ~(x & y) */ > (for op (bit_and bit_ior) > Index: gcc/testsuite/gcc.dg/pr87009.c > =================================================================== > --- gcc/testsuite/gcc.dg/pr87009.c (nonexistent) > +++ gcc/testsuite/gcc.dg/pr87009.c (working copy) > @@ -0,0 +1,23 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O -fdump-tree-original" } */ > +/* { dg-final { scan-tree-dump-times "return s \\^ x;" 4 "original" } } */ > + > +int f1 (int x, int s) > +{ > + return ~(~(x|s)|x)|~(~(x|s)|s); > +} > + > +int f2 (int x, int s) > +{ > + return ~(~(~x&s)&~(x&~s)); > +} > + > +int f3 (int x, int s) > +{ > + return ~((x|~s)&(~x|s)); > +} > + > +int f4 (int x, int s) > +{ > + return (x|~s)^(~x|s); > +}
On Mon, 27 Aug 2018, Richard Biener wrote: > On Tue, Aug 21, 2018 at 7:20 PM MCC CS <mcccs@gmx.com> wrote: >> >> Hello all, >> >> I have updated the testcase and run "make check" on Ubuntu x86_64. >> All of them passed. (However the last part "do-check" couldn't be >> run, probably due to a missing testsuite dependency?) >> >> The match.pd is the same as the original patch, and I have >> updated change-summaries and improved tests. >> >> 2018-08-21 MCC CS <deswurstes@users.noreply.github.com> >> >> gcc/ >> PR tree-optimization/87009 >> * match.pd: Add boolean optimizations. >> >> 2018-08-21 MCC CS <deswurstes@users.noreply.github.com> >> >> gcc/testsuite/ >> PR tree-optimization/87009 >> * gcc.dg/pr87009.c: New test. >> >> Index: gcc/match.pd >> =================================================================== >> --- gcc/match.pd (revision 263646) >> +++ gcc/match.pd (working copy) >> @@ -776,6 +776,11 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) >> (bit_not (bit_and:cs (bit_not @0) @1)) >> (bit_ior @0 (bit_not @1))) >> >> +/* ~(~a | b) --> a & ~b */ >> +(simplify >> + (bit_not (bit_ior:cs (bit_not @0) @1)) >> + (bit_and @0 (bit_not @1))) >> + >> /* Simplify (~X & Y) to X ^ Y if we know that (X & ~Y) is 0. */ >> #if GIMPLE >> (simplify >> @@ -981,6 +986,16 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) >> (bit_and:c (bit_ior:c @0 @1) (bit_xor:c @1 (bit_not @0))) >> (bit_and @0 @1)) >> >> +/* (~x | y) & (x | ~y) -> ~(x ^ y) */ >> +(simplify >> + (bit_and (bit_ior:c (bit_not @0) @1) (bit_ior:c @0 (bit_not @1))) > > Please add single-use markers after the existing 'c' markers of the bit_ior's > >> + (bit_not (bit_xor @0 @1))) >> + >> +/* (~x | y) ^ (x | ~y) -> x ^ y */ >> +(simplify >> + (bit_xor (bit_ior:c (bit_not @0) @1) (bit_ior:c @0 (bit_not @1))) >> + (bit_xor @0 @1)) > > Likewise. Wouldn't :s be ignored here, since there is a single instruction in the output?
On Mon, Aug 27, 2018 at 1:52 PM Marc Glisse <marc.glisse@inria.fr> wrote: > > On Mon, 27 Aug 2018, Richard Biener wrote: > > > On Tue, Aug 21, 2018 at 7:20 PM MCC CS <mcccs@gmx.com> wrote: > >> > >> Hello all, > >> > >> I have updated the testcase and run "make check" on Ubuntu x86_64. > >> All of them passed. (However the last part "do-check" couldn't be > >> run, probably due to a missing testsuite dependency?) > >> > >> The match.pd is the same as the original patch, and I have > >> updated change-summaries and improved tests. > >> > >> 2018-08-21 MCC CS <deswurstes@users.noreply.github.com> > >> > >> gcc/ > >> PR tree-optimization/87009 > >> * match.pd: Add boolean optimizations. > >> > >> 2018-08-21 MCC CS <deswurstes@users.noreply.github.com> > >> > >> gcc/testsuite/ > >> PR tree-optimization/87009 > >> * gcc.dg/pr87009.c: New test. > >> > >> Index: gcc/match.pd > >> =================================================================== > >> --- gcc/match.pd (revision 263646) > >> +++ gcc/match.pd (working copy) > >> @@ -776,6 +776,11 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) > >> (bit_not (bit_and:cs (bit_not @0) @1)) > >> (bit_ior @0 (bit_not @1))) > >> > >> +/* ~(~a | b) --> a & ~b */ > >> +(simplify > >> + (bit_not (bit_ior:cs (bit_not @0) @1)) > >> + (bit_and @0 (bit_not @1))) > >> + > >> /* Simplify (~X & Y) to X ^ Y if we know that (X & ~Y) is 0. */ > >> #if GIMPLE > >> (simplify > >> @@ -981,6 +986,16 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) > >> (bit_and:c (bit_ior:c @0 @1) (bit_xor:c @1 (bit_not @0))) > >> (bit_and @0 @1)) > >> > >> +/* (~x | y) & (x | ~y) -> ~(x ^ y) */ > >> +(simplify > >> + (bit_and (bit_ior:c (bit_not @0) @1) (bit_ior:c @0 (bit_not @1))) > > > > Please add single-use markers after the existing 'c' markers of the bit_ior's > > > >> + (bit_not (bit_xor @0 @1))) > >> + > >> +/* (~x | y) ^ (x | ~y) -> x ^ y */ > >> +(simplify > >> + (bit_xor (bit_ior:c (bit_not @0) @1) (bit_ior:c @0 (bit_not @1))) > >> + (bit_xor @0 @1)) > > > > Likewise. > > Wouldn't :s be ignored here, since there is a single instruction in the > output? Yes, indeed. Not in the first pattern though. I guess it's only not profitable if both iors are re-used though. Richard. > > -- > Marc Glisse
Added :s to the second pattern, updated dates. Thank you so much for your reviews! 2018-08-27 MCC CS <deswurstes@users.noreply.github.com> gcc/ PR tree-optimization/87009 * match.pd: Add boolean optimizations. 2018-08-27 MCC CS <deswurstes@users.noreply.github.com> gcc/testsuite/ PR tree-optimization/87009 * gcc.dg/pr87009.c: New test. Index: gcc/match.pd =================================================================== --- gcc/match.pd (revision 263646) +++ gcc/match.pd (working copy) @@ -776,6 +776,11 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (bit_not (bit_and:cs (bit_not @0) @1)) (bit_ior @0 (bit_not @1))) +/* ~(~a | b) --> a & ~b */ +(simplify + (bit_not (bit_ior:cs (bit_not @0) @1)) + (bit_and @0 (bit_not @1))) + /* Simplify (~X & Y) to X ^ Y if we know that (X & ~Y) is 0. */ #if GIMPLE (simplify @@ -981,6 +986,16 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (bit_and:c (bit_ior:c @0 @1) (bit_xor:c @1 (bit_not @0))) (bit_and @0 @1)) +/* (~x | y) & (x | ~y) -> ~(x ^ y) */ +(simplify + (bit_and (bit_ior:cs (bit_not @0) @1) (bit_ior:cs @0 (bit_not @1))) + (bit_not (bit_xor @0 @1))) + +/* (~x | y) ^ (x | ~y) -> x ^ y */ +(simplify + (bit_xor (bit_ior:c (bit_not @0) @1) (bit_ior:c @0 (bit_not @1))) + (bit_xor @0 @1)) + /* ~x & ~y -> ~(x | y) ~x | ~y -> ~(x & y) */ (for op (bit_and bit_ior) Index: gcc/testsuite/gcc.dg/pr87009.c =================================================================== --- gcc/testsuite/gcc.dg/pr87009.c (nonexistent) +++ gcc/testsuite/gcc.dg/pr87009.c (working copy) @@ -0,0 +1,23 @@ +/* { dg-do compile } */ +/* { dg-options "-O -fdump-tree-original" } */ +/* { dg-final { scan-tree-dump-times "return s \\^ x;" 4 "original" } } */ + +int f1 (int x, int s) +{ + return ~(~(x|s)|x)|~(~(x|s)|s); +} + +int f2 (int x, int s) +{ + return ~(~(~x&s)&~(x&~s)); +} + +int f3 (int x, int s) +{ + return ~((x|~s)&(~x|s)); +} + +int f4 (int x, int s) +{ + return (x|~s)^(~x|s); +}
Index: gcc/match.pd =================================================================== --- gcc/match.pd (revision 263646) +++ gcc/match.pd (working copy) @@ -776,6 +776,11 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (bit_not (bit_and:cs (bit_not @0) @1)) (bit_ior @0 (bit_not @1))) +/* ~(~a | b) --> a & ~b */ +(simplify + (bit_not (bit_ior:cs (bit_not @0) @1)) + (bit_and @0 (bit_not @1))) + /* Simplify (~X & Y) to X ^ Y if we know that (X & ~Y) is 0. */ #if GIMPLE (simplify @@ -981,6 +986,16 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (bit_and:c (bit_ior:c @0 @1) (bit_xor:c @1 (bit_not @0))) (bit_and @0 @1)) +/* (~x | y) & (x | ~y) -> ~(x ^ y) */ +(simplify + (bit_and (bit_ior:c (bit_not @0) @1) (bit_ior:c @0 (bit_not @1))) + (bit_not (bit_xor @0 @1))) + +/* (~x | y) ^ (x | ~y) -> x ^ y */ +(simplify + (bit_xor (bit_ior:c (bit_not @0) @1) (bit_ior:c @0 (bit_not @1))) + (bit_xor @0 @1)) + /* ~x & ~y -> ~(x | y) ~x | ~y -> ~(x & y) */ (for op (bit_and bit_ior) Index: gcc/testsuite/gcc.dg/pr87009.c =================================================================== --- gcc/testsuite/gcc.dg/pr87009.c (nonexistent) +++ gcc/testsuite/gcc.dg/pr87009.c (working copy) @@ -0,0 +1,23 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-original" } */ +/* { dg-final { scan-tree-dump-times " \\^ " 4 "original" } } */ + +int f1 (int x, int s) +{ + return ~(~(x|s)|x)|~(~(x|s)|s); +} + +int f2 (int x, int s) +{ + return ~(~(~x&s)&~(x&~s)); +} + +int f3 (int x, int s) +{ + return ~((x|~s)&(~x|s)); +} + +int f4 (int x, int s) +{ + return (~x|s)&(x|~s); +}