| Message ID | CAAgBjMk7p7xR2Zk4uqWhyoXsAzehN+vo53yUoNb2RiXdxxs5MQ@mail.gmail.com |
|---|---|
| State | New |
| Headers | show |
| Series | Transform (x / y) != 0 to x >=y and (x / y) == 0 to x < y if x, y are unsigned | expand |
On Fri, 15 Sep 2017, Prathamesh Kulkarni wrote: +/* (X / Y) == 0 -> X < Y if X, Y are unsigned. */ +(simplify + (eq (trunc_div @0 @1) integer_zerop) + (if (TYPE_UNSIGNED (TREE_TYPE(@0)) && TYPE_UNSIGNED (TREE_TYPE (@1))) + (lt @0 @1))) + +/* (X / Y) != 0 -> X >= Y, if X, Y are unsigned. */ +(simplify + (ne (trunc_div @0 @1) integer_zerop) + (if (TYPE_UNSIGNED (TREE_TYPE(@0)) && TYPE_UNSIGNED (TREE_TYPE (@1))) + (ge @0 @1))) + Hello, you can merge the 2 transforms using "for". Also, no need to test the type of @1 since you are already testing @0. - do we want a single_use restriction on the result of the division? - do we also want to handle (x>>4)==0? - do we also want a special case when X is 1 that produces Y==1, as asked in a recent PR? - once in a while, someone mentions that eq, on vectors, can either do elementwise comparison and return a vector, or return a single boolean, which would fail here. However, I don't remember ever seeing an example. -- Marc Glisse
On 09/15/2017 07:09 AM, Marc Glisse wrote: > On Fri, 15 Sep 2017, Prathamesh Kulkarni wrote: > > +/* (X / Y) == 0 -> X < Y if X, Y are unsigned. */ > +(simplify > + (eq (trunc_div @0 @1) integer_zerop) > + (if (TYPE_UNSIGNED (TREE_TYPE(@0)) && TYPE_UNSIGNED (TREE_TYPE (@1))) > + (lt @0 @1))) > + > +/* (X / Y) != 0 -> X >= Y, if X, Y are unsigned. */ > +(simplify > + (ne (trunc_div @0 @1) integer_zerop) > + (if (TYPE_UNSIGNED (TREE_TYPE(@0)) && TYPE_UNSIGNED (TREE_TYPE (@1))) > + (ge @0 @1))) > + > > Hello, > > you can merge the 2 transforms using "for". Also, no need to test the > type of @1 since you are already testing @0. Right. > > - do we want a single_use restriction on the result of the division? I think so. If x/y is a common subexpression, then ideally we'd compute it once. > - do we also want to handle (x>>4)==0? I think so, but that can be a follow-up IMHO. > - do we also want a special case when X is 1 that produces Y==1, as > asked in a recent PR? Seems like a reasonable follow-up as well. The other follow-up to consider is detecting these cases in VRP to produce suitable ASSERT_EXPRs and ranges. > - once in a while, someone mentions that eq, on vectors, can either do > elementwise comparison and return a vector, or return a single boolean, > which would fail here. However, I don't remember ever seeing an example. We could always restrict to the integral types. Probably wise to explicitly do that anyway. jeff
On Fri, 15 Sep 2017, Jeff Law wrote: > On 09/15/2017 07:09 AM, Marc Glisse wrote: >> On Fri, 15 Sep 2017, Prathamesh Kulkarni wrote: >> >> +/* (X / Y) == 0 -> X < Y if X, Y are unsigned. */ >> +(simplify >> + (eq (trunc_div @0 @1) integer_zerop) >> + (if (TYPE_UNSIGNED (TREE_TYPE(@0)) && TYPE_UNSIGNED (TREE_TYPE (@1))) >> + (lt @0 @1))) >> + >> +/* (X / Y) != 0 -> X >= Y, if X, Y are unsigned. */ >> +(simplify >> + (ne (trunc_div @0 @1) integer_zerop) >> + (if (TYPE_UNSIGNED (TREE_TYPE(@0)) && TYPE_UNSIGNED (TREE_TYPE (@1))) >> + (ge @0 @1))) >> + >> >> Hello, >> >> you can merge the 2 transforms using "for". Also, no need to test the >> type of @1 since you are already testing @0. > Right. > >> >> - do we want a single_use restriction on the result of the division? > I think so. If x/y is a common subexpression, then ideally we'd compute > it once. The question is whether, having computed c=a/b, it is cheaper to test a<b or c!=0. I think it is usually the second one, but not for all types on all targets. Although since you mention VRP, it is easier to do further optimizations using the information a<b. >> - do we also want to handle (x>>4)==0? > I think so, but that can be a follow-up IMHO. Yes, I forgot to specify it in my email, but these are not meant as requirements for this patch to move forward. >> - do we also want a special case when X is 1 that produces Y==1, as >> asked in a recent PR? > Seems like a reasonable follow-up as well. > > The other follow-up to consider is detecting these cases in VRP to > produce suitable ASSERT_EXPRs and ranges. > >> - once in a while, someone mentions that eq, on vectors, can either do >> elementwise comparison and return a vector, or return a single boolean, >> which would fail here. However, I don't remember ever seeing an example. > We could always restrict to the integral types. Probably wise to > explicitly do that anyway. VECTOR_TYPE_P (type) || !VECTOR_TYPE_P (TREE_TYPE (@0)) should be enough to avoid the problematic case, the transformation can still be nice for vectors. -- Marc Glisse
On 09/15/2017 09:55 AM, Marc Glisse wrote: > On Fri, 15 Sep 2017, Jeff Law wrote: > >> On 09/15/2017 07:09 AM, Marc Glisse wrote: >>> On Fri, 15 Sep 2017, Prathamesh Kulkarni wrote: >>> >>> +/* (X / Y) == 0 -> X < Y if X, Y are unsigned. */ >>> +(simplify >>> + (eq (trunc_div @0 @1) integer_zerop) >>> + (if (TYPE_UNSIGNED (TREE_TYPE(@0)) && TYPE_UNSIGNED (TREE_TYPE (@1))) >>> + (lt @0 @1))) >>> + >>> +/* (X / Y) != 0 -> X >= Y, if X, Y are unsigned. */ >>> +(simplify >>> + (ne (trunc_div @0 @1) integer_zerop) >>> + (if (TYPE_UNSIGNED (TREE_TYPE(@0)) && TYPE_UNSIGNED (TREE_TYPE (@1))) >>> + (ge @0 @1))) >>> + >>> >>> Hello, >>> >>> you can merge the 2 transforms using "for". Also, no need to test the >>> type of @1 since you are already testing @0. >> Right. >> >>> >>> - do we want a single_use restriction on the result of the division? >> I think so. If x/y is a common subexpression, then ideally we'd compute >> it once. > > The question is whether, having computed c=a/b, it is cheaper to test > a<b or c!=0. I think it is usually the second one, but not for all types > on all targets. Although since you mention VRP, it is easier to do > further optimizations using the information a<b. The c != 0 is easier to test. WRT VRP we're working to solve that problem. The framework Andrew's built allows us to see the c != 0 test and easily derive a < b or a >= b for the two sides of the branch. It falls out quite naturally, so I wouldn't let which is easier for VRP to use play a significant role here. >>> - do we also want a special case when X is 1 that produces Y==1, as >>> asked in a recent PR? >> Seems like a reasonable follow-up as well. >> >> The other follow-up to consider is detecting these cases in VRP to >> produce suitable ASSERT_EXPRs and ranges. >> >>> - once in a while, someone mentions that eq, on vectors, can either do >>> elementwise comparison and return a vector, or return a single boolean, >>> which would fail here. However, I don't remember ever seeing an example. >> We could always restrict to the integral types. Probably wise to >> explicitly do that anyway. > > VECTOR_TYPE_P (type) || !VECTOR_TYPE_P (TREE_TYPE (@0)) > > should be enough to avoid the problematic case, the transformation can > still be nice for vectors. Seems reasonable to me. Richi, further comments? Prathamesh, I think you've got a few things to address, but hopefully nothing terribly complex. jeff-0 >
diff --git a/gcc/match.pd b/gcc/match.pd index dbfceaf10a5..0e1b59c9c10 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -1266,6 +1266,18 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) || TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0)))) (op @1 @0)))) +/* (X / Y) == 0 -> X < Y if X, Y are unsigned. */ +(simplify + (eq (trunc_div @0 @1) integer_zerop) + (if (TYPE_UNSIGNED (TREE_TYPE(@0)) && TYPE_UNSIGNED (TREE_TYPE (@1))) + (lt @0 @1))) + +/* (X / Y) != 0 -> X >= Y, if X, Y are unsigned. */ +(simplify + (ne (trunc_div @0 @1) integer_zerop) + (if (TYPE_UNSIGNED (TREE_TYPE(@0)) && TYPE_UNSIGNED (TREE_TYPE (@1))) + (ge @0 @1))) + /* X == C - X can never be true if C is odd. */ (for cmp (eq ne) (simplify diff --git a/gcc/testsuite/gcc.dg/tree-ssa/cmpdiv.c b/gcc/testsuite/gcc.dg/tree-ssa/cmpdiv.c new file mode 100644 index 00000000000..14161f5ea6f --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/cmpdiv.c @@ -0,0 +1,18 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized-raw" } */ + +_Bool f1(unsigned x, unsigned y) +{ + unsigned t1 = x / y; + _Bool t2 = (t1 != 0); + return t2; +} + +_Bool f2(unsigned x, unsigned y) +{ + unsigned t1 = x / y; + _Bool t2 = (t1 == 0); + return t2; +} + +/* { dg-final { scan-tree-dump-not "trunc_div_expr" "optimized" } } */