Message ID  CAAgBjMk7p7xR2Zk4uqWhyoXsAzehN+vo53yUoNb2RiXdxxs5MQ@mail.gmail.com 

State  New 
Headers  show 
Series 

Related  show 
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 followup 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 followup as well. The other followup 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 followup 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 followup as well. > > The other followup 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 followup as well. >> >> The other followup 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. jeff0 >
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/treessa/cmpdiv.c b/gcc/testsuite/gcc.dg/treessa/cmpdiv.c new file mode 100644 index 00000000000..14161f5ea6f  /dev/null +++ b/gcc/testsuite/gcc.dg/treessa/cmpdiv.c @@ 0,0 +1,18 @@ +/* { dgdo compile } */ +/* { dgoptions "O2 fdumptreeoptimizedraw" } */ + +_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; +} + +/* { dgfinal { scantreedumpnot "trunc_div_expr" "optimized" } } */