| Message ID | alpine.DEB.2.02.1604241914370.12491@laptop-mg.saclay.inria.fr |
|---|---|
| State | New |
| Headers | show |
On Sun, Apr 24, 2016 at 7:24 PM, Marc Glisse <marc.glisse@inria.fr> wrote: > On Fri, 22 Apr 2016, Marc Glisse wrote: > >> On Fri, 22 Apr 2016, Richard Biener wrote: >> >>> On Fri, Apr 22, 2016 at 5:29 AM, Marc Glisse <marc.glisse@inria.fr> >>> wrote: >>>> >>>> Hello, >>>> >>>> this optimizes a common pattern for unsigned overflow detection, when >>>> one of >>>> the arguments turns out to be a constant. There are more ways this could >>>> look like, (a + 42 <= 41) in particular, but that'll be for another >>>> patch. >>> >>> >>> This case is also covered by fold_comparison which should be re-written >>> to match.pd patterns (and removed from fold-const.c). >>> >>> fold_binary also as a few interesting/similar equality compare cases >>> like X +- Y CMP X to Y CMP 0 which look related. >>> >>> Also your case is in fold_binary for the case of undefined overflow: >> >> >> As far as I can tell, fold-const.c handles this kind of transformation >> strictly in the case of undefined overflow (or floats), while this is >> strictly in the case of unsigned with wrapping overflow. I thought it would >> be more readable to take advantage of the genmatch machinery and group the >> wrapping transforms in one place, and the undefined overflow ones in another >> place (they don't group the same way by operator, etc). >> >> If you prefer to group by pattern shape and port the related fold-const.c >> bit at the same time, I could try that... >> >>> +/* When one argument is a constant, overflow detection can be >>> simplified. >>> + Currently restricted to single use so as not to interfere too much >>> with >>> + ADD_OVERFLOW detection in tree-ssa-math-opts.c. */ >>> +(for cmp (lt le ge gt) >>> + out (gt gt le le) >>> + (simplify >>> + (cmp (plus@2 @0 integer_nonzerop@1) @0) >>> + (if (TYPE_UNSIGNED (TREE_TYPE (@0)) >>> + && TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0)) >>> + && TYPE_MAX_VALUE (TREE_TYPE (@0)) >>> + && single_use (@2)) >>> + (out @0 (minus { TYPE_MAX_VALUE (TREE_TYPE (@0)); } @1))))) >>> +(for cmp (gt ge le lt) >>> + out (gt gt le le) >>> + (simplify >>> + (cmp @0 (plus@2 @0 integer_nonzerop@1)) >>> + (if (TYPE_UNSIGNED (TREE_TYPE (@0)) >>> + && TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0)) >>> + && TYPE_MAX_VALUE (TREE_TYPE (@0)) >>> + && single_use (@2)) >>> + (out @0 (minus { TYPE_MAX_VALUE (TREE_TYPE (@0)); } @1))))) >>> >>> please add a comment with the actual transform - A + CST CMP A -> A CMP' >>> CST' >>> >>> As we are relying on twos-complement wrapping you shouldn't need >>> TYPE_MAX_VALUE >>> here but you can use wi::max_value (precision, sign). I'm not sure we >>> have sensible >>> TYPE_MAX_VALUE for vector or complex types - the accessor uses >>> NUMERICAL_TYPE_CKECK >>> and TYPE_OVERFLOW_WRAPS checks for ANY_INTEGRAL_TYPE. Thus I wonder >>> if we should restrict this to INTEGRAL_TYPE_P (making the >>> wi::max_value route valid). >> >> >> integer_nonzerop currently already restricts to INTEGER_CST or >> COMPLEX_CST, and I don't think complex can appear in a comparison. I'll go >> back to writing the more explicit INTEGER_CST in the pattern and I'll use >> wide_int. > > > Better this way? > > By the way, it would be cool to be able to write: > (lt:c @0 @1) > > which would expand to both > (lt @0 @1) > (gt @1 @0) > > (as per swap_tree_comparison or swapped_tcc_comparison) Yeah, I know... I was hesitant to overload :c with "slightly" different semantics though. I can give it a shot though - it would avoid quite some repetition I guess. Ok. Thanks, Richard. > -- > Marc Glisse > Index: trunk-ovf/gcc/match.pd > =================================================================== > --- trunk-ovf/gcc/match.pd (revision 235371) > +++ trunk-ovf/gcc/match.pd (working copy) > @@ -3071,10 +3071,36 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) > (simplify > /* signbit(x) -> 0 if x is nonnegative. */ > (SIGNBIT tree_expr_nonnegative_p@0) > { integer_zero_node; }) > > (simplify > /* signbit(x) -> x<0 if x doesn't have signed zeros. */ > (SIGNBIT @0) > (if (!HONOR_SIGNED_ZEROS (@0)) > (convert (lt @0 { build_real (TREE_TYPE (@0), dconst0); })))) > + > +/* When one argument is a constant, overflow detection can be simplified. > + Currently restricted to single use so as not to interfere too much with > + ADD_OVERFLOW detection in tree-ssa-math-opts.c. > + A + CST CMP A -> A CMP' CST' */ > +(for cmp (lt le ge gt) > + out (gt gt le le) > + (simplify > + (cmp (plus@2 @0 INTEGER_CST@1) @0) > + (if (TYPE_UNSIGNED (TREE_TYPE (@0)) > + && TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0)) > + && wi::ne_p (@1, 0) > + && single_use (@2)) > + (out @0 { wide_int_to_tree (TREE_TYPE (@0), wi::max_value > + (TYPE_PRECISION (TREE_TYPE (@0)), UNSIGNED) - @1); })))) > +/* A CMP A + CST -> A CMP' CST' */ > +(for cmp (gt ge le lt) > + out (gt gt le le) > + (simplify > + (cmp @0 (plus@2 @0 INTEGER_CST@1)) > + (if (TYPE_UNSIGNED (TREE_TYPE (@0)) > + && TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0)) > + && wi::ne_p (@1, 0) > + && single_use (@2)) > + (out @0 { wide_int_to_tree (TREE_TYPE (@0), wi::max_value > + (TYPE_PRECISION (TREE_TYPE (@0)), UNSIGNED) - @1); })))) > Index: trunk-ovf/gcc/testsuite/gcc.dg/tree-ssa/overflow-1.c > =================================================================== > --- trunk-ovf/gcc/testsuite/gcc.dg/tree-ssa/overflow-1.c (revision 0) > +++ trunk-ovf/gcc/testsuite/gcc.dg/tree-ssa/overflow-1.c (working > copy) > @@ -0,0 +1,16 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O -fdump-tree-optimized" } */ > + > +int f(unsigned a){ > + unsigned b=5; > + unsigned c=a-b; > + return c>a; > +} > +int g(unsigned a){ > + unsigned b=32; > + unsigned c=a+b; > + return c<a; > +} > + > +/* { dg-final { scan-tree-dump "a_\[0-9\]+.D. <= 4;" "optimized" } } */ > +/* { dg-final { scan-tree-dump "a_\[0-9\]+.D. > 4294967263;" "optimized" } > } */ >
On Tue, Apr 26, 2016 at 1:07 PM, Richard Biener <richard.guenther@gmail.com> wrote: > On Sun, Apr 24, 2016 at 7:24 PM, Marc Glisse <marc.glisse@inria.fr> wrote: >> On Fri, 22 Apr 2016, Marc Glisse wrote: >> >>> On Fri, 22 Apr 2016, Richard Biener wrote: >>> >>>> On Fri, Apr 22, 2016 at 5:29 AM, Marc Glisse <marc.glisse@inria.fr> >>>> wrote: >>>>> >>>>> Hello, >>>>> >>>>> this optimizes a common pattern for unsigned overflow detection, when >>>>> one of >>>>> the arguments turns out to be a constant. There are more ways this could >>>>> look like, (a + 42 <= 41) in particular, but that'll be for another >>>>> patch. >>>> >>>> >>>> This case is also covered by fold_comparison which should be re-written >>>> to match.pd patterns (and removed from fold-const.c). >>>> >>>> fold_binary also as a few interesting/similar equality compare cases >>>> like X +- Y CMP X to Y CMP 0 which look related. >>>> >>>> Also your case is in fold_binary for the case of undefined overflow: >>> >>> >>> As far as I can tell, fold-const.c handles this kind of transformation >>> strictly in the case of undefined overflow (or floats), while this is >>> strictly in the case of unsigned with wrapping overflow. I thought it would >>> be more readable to take advantage of the genmatch machinery and group the >>> wrapping transforms in one place, and the undefined overflow ones in another >>> place (they don't group the same way by operator, etc). >>> >>> If you prefer to group by pattern shape and port the related fold-const.c >>> bit at the same time, I could try that... >>> >>>> +/* When one argument is a constant, overflow detection can be >>>> simplified. >>>> + Currently restricted to single use so as not to interfere too much >>>> with >>>> + ADD_OVERFLOW detection in tree-ssa-math-opts.c. */ >>>> +(for cmp (lt le ge gt) >>>> + out (gt gt le le) >>>> + (simplify >>>> + (cmp (plus@2 @0 integer_nonzerop@1) @0) >>>> + (if (TYPE_UNSIGNED (TREE_TYPE (@0)) >>>> + && TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0)) >>>> + && TYPE_MAX_VALUE (TREE_TYPE (@0)) >>>> + && single_use (@2)) >>>> + (out @0 (minus { TYPE_MAX_VALUE (TREE_TYPE (@0)); } @1))))) >>>> +(for cmp (gt ge le lt) >>>> + out (gt gt le le) >>>> + (simplify >>>> + (cmp @0 (plus@2 @0 integer_nonzerop@1)) >>>> + (if (TYPE_UNSIGNED (TREE_TYPE (@0)) >>>> + && TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0)) >>>> + && TYPE_MAX_VALUE (TREE_TYPE (@0)) >>>> + && single_use (@2)) >>>> + (out @0 (minus { TYPE_MAX_VALUE (TREE_TYPE (@0)); } @1))))) >>>> >>>> please add a comment with the actual transform - A + CST CMP A -> A CMP' >>>> CST' >>>> >>>> As we are relying on twos-complement wrapping you shouldn't need >>>> TYPE_MAX_VALUE >>>> here but you can use wi::max_value (precision, sign). I'm not sure we >>>> have sensible >>>> TYPE_MAX_VALUE for vector or complex types - the accessor uses >>>> NUMERICAL_TYPE_CKECK >>>> and TYPE_OVERFLOW_WRAPS checks for ANY_INTEGRAL_TYPE. Thus I wonder >>>> if we should restrict this to INTEGRAL_TYPE_P (making the >>>> wi::max_value route valid). >>> >>> >>> integer_nonzerop currently already restricts to INTEGER_CST or >>> COMPLEX_CST, and I don't think complex can appear in a comparison. I'll go >>> back to writing the more explicit INTEGER_CST in the pattern and I'll use >>> wide_int. >> >> >> Better this way? >> >> By the way, it would be cool to be able to write: >> (lt:c @0 @1) >> >> which would expand to both >> (lt @0 @1) >> (gt @1 @0) >> >> (as per swap_tree_comparison or swapped_tcc_comparison) > > Yeah, I know... I was hesitant to overload :c with "slightly" different > semantics though. > > I can give it a shot though - it would avoid quite some repetition I guess. Being able to write (lt:c @0 @1) is easy, see attached (didn't check if it works), but being able to write (for cmp (lt gt) (cmp:c @0 @1) is harder (see FIXME), you'd have to create a new for at the nesting level of the old with the operator list adjusted. Not impossible, of course. Includes some verification I added locally at some point (which also exposed we use :c on non-commutative tree codes, thus the new :C ...). Richard. > Ok. > > Thanks, > Richard. > >> -- >> Marc Glisse >> Index: trunk-ovf/gcc/match.pd >> =================================================================== >> --- trunk-ovf/gcc/match.pd (revision 235371) >> +++ trunk-ovf/gcc/match.pd (working copy) >> @@ -3071,10 +3071,36 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) >> (simplify >> /* signbit(x) -> 0 if x is nonnegative. */ >> (SIGNBIT tree_expr_nonnegative_p@0) >> { integer_zero_node; }) >> >> (simplify >> /* signbit(x) -> x<0 if x doesn't have signed zeros. */ >> (SIGNBIT @0) >> (if (!HONOR_SIGNED_ZEROS (@0)) >> (convert (lt @0 { build_real (TREE_TYPE (@0), dconst0); })))) >> + >> +/* When one argument is a constant, overflow detection can be simplified. >> + Currently restricted to single use so as not to interfere too much with >> + ADD_OVERFLOW detection in tree-ssa-math-opts.c. >> + A + CST CMP A -> A CMP' CST' */ >> +(for cmp (lt le ge gt) >> + out (gt gt le le) >> + (simplify >> + (cmp (plus@2 @0 INTEGER_CST@1) @0) >> + (if (TYPE_UNSIGNED (TREE_TYPE (@0)) >> + && TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0)) >> + && wi::ne_p (@1, 0) >> + && single_use (@2)) >> + (out @0 { wide_int_to_tree (TREE_TYPE (@0), wi::max_value >> + (TYPE_PRECISION (TREE_TYPE (@0)), UNSIGNED) - @1); })))) >> +/* A CMP A + CST -> A CMP' CST' */ >> +(for cmp (gt ge le lt) >> + out (gt gt le le) >> + (simplify >> + (cmp @0 (plus@2 @0 INTEGER_CST@1)) >> + (if (TYPE_UNSIGNED (TREE_TYPE (@0)) >> + && TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0)) >> + && wi::ne_p (@1, 0) >> + && single_use (@2)) >> + (out @0 { wide_int_to_tree (TREE_TYPE (@0), wi::max_value >> + (TYPE_PRECISION (TREE_TYPE (@0)), UNSIGNED) - @1); })))) >> Index: trunk-ovf/gcc/testsuite/gcc.dg/tree-ssa/overflow-1.c >> =================================================================== >> --- trunk-ovf/gcc/testsuite/gcc.dg/tree-ssa/overflow-1.c (revision 0) >> +++ trunk-ovf/gcc/testsuite/gcc.dg/tree-ssa/overflow-1.c (working >> copy) >> @@ -0,0 +1,16 @@ >> +/* { dg-do compile } */ >> +/* { dg-options "-O -fdump-tree-optimized" } */ >> + >> +int f(unsigned a){ >> + unsigned b=5; >> + unsigned c=a-b; >> + return c>a; >> +} >> +int g(unsigned a){ >> + unsigned b=32; >> + unsigned c=a+b; >> + return c<a; >> +} >> + >> +/* { dg-final { scan-tree-dump "a_\[0-9\]+.D. <= 4;" "optimized" } } */ >> +/* { dg-final { scan-tree-dump "a_\[0-9\]+.D. > 4294967263;" "optimized" } >> } */ >>
On Tue, 26 Apr 2016, Richard Biener wrote: >>> By the way, it would be cool to be able to write: >>> (lt:c @0 @1) >>> >>> which would expand to both >>> (lt @0 @1) >>> (gt @1 @0) >>> >>> (as per swap_tree_comparison or swapped_tcc_comparison) >> >> Yeah, I know... I was hesitant to overload :c with "slightly" different >> semantics though. >> >> I can give it a shot though - it would avoid quite some repetition I guess. > > Being able to write (lt:c @0 @1) is easy, see attached (didn't check > if it works), > but being able to write > > (for cmp (lt gt) > (cmp:c @0 @1) > > is harder (see FIXME), you'd have to create a new for at the nesting > level of the > old with the operator list adjusted. Not impossible, of course. > > Includes some verification I added locally at some point (which also exposed we > use :c on non-commutative tree codes, thus the new :C ...). Ah, I was hoping it would be as simple as adding op=commuted_op(op) at the place where the regular commutation gets lowered. If it is significantly more complicated, I guess it isn't that urgent...
On Tue, Apr 26, 2016 at 1:57 PM, Marc Glisse <marc.glisse@inria.fr> wrote: > On Tue, 26 Apr 2016, Richard Biener wrote: > >>>> By the way, it would be cool to be able to write: >>>> (lt:c @0 @1) >>>> >>>> which would expand to both >>>> (lt @0 @1) >>>> (gt @1 @0) >>>> >>>> (as per swap_tree_comparison or swapped_tcc_comparison) >>> >>> >>> Yeah, I know... I was hesitant to overload :c with "slightly" different >>> semantics though. >>> >>> I can give it a shot though - it would avoid quite some repetition I >>> guess. >> >> >> Being able to write (lt:c @0 @1) is easy, see attached (didn't check >> if it works), >> but being able to write >> >> (for cmp (lt gt) >> (cmp:c @0 @1) >> >> is harder (see FIXME), you'd have to create a new for at the nesting >> level of the >> old with the operator list adjusted. Not impossible, of course. >> >> Includes some verification I added locally at some point (which also >> exposed we >> use :c on non-commutative tree codes, thus the new :C ...). > > > Ah, I was hoping it would be as simple as adding op=commuted_op(op) at the > place where the regular commutation gets lowered. If it is significantly > more complicated, I guess it isn't that urgent... Yeah, the issue is that lowering of (for ...) has to happen last and thus we have to commutate the (for...)s themselves. Possible, but some work. Richard. > -- > Marc Glisse
Index: trunk-ovf/gcc/match.pd =================================================================== --- trunk-ovf/gcc/match.pd (revision 235371) +++ trunk-ovf/gcc/match.pd (working copy) @@ -3071,10 +3071,36 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (simplify /* signbit(x) -> 0 if x is nonnegative. */ (SIGNBIT tree_expr_nonnegative_p@0) { integer_zero_node; }) (simplify /* signbit(x) -> x<0 if x doesn't have signed zeros. */ (SIGNBIT @0) (if (!HONOR_SIGNED_ZEROS (@0)) (convert (lt @0 { build_real (TREE_TYPE (@0), dconst0); })))) + +/* When one argument is a constant, overflow detection can be simplified. + Currently restricted to single use so as not to interfere too much with + ADD_OVERFLOW detection in tree-ssa-math-opts.c. + A + CST CMP A -> A CMP' CST' */ +(for cmp (lt le ge gt) + out (gt gt le le) + (simplify + (cmp (plus@2 @0 INTEGER_CST@1) @0) + (if (TYPE_UNSIGNED (TREE_TYPE (@0)) + && TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0)) + && wi::ne_p (@1, 0) + && single_use (@2)) + (out @0 { wide_int_to_tree (TREE_TYPE (@0), wi::max_value + (TYPE_PRECISION (TREE_TYPE (@0)), UNSIGNED) - @1); })))) +/* A CMP A + CST -> A CMP' CST' */ +(for cmp (gt ge le lt) + out (gt gt le le) + (simplify + (cmp @0 (plus@2 @0 INTEGER_CST@1)) + (if (TYPE_UNSIGNED (TREE_TYPE (@0)) + && TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0)) + && wi::ne_p (@1, 0) + && single_use (@2)) + (out @0 { wide_int_to_tree (TREE_TYPE (@0), wi::max_value + (TYPE_PRECISION (TREE_TYPE (@0)), UNSIGNED) - @1); })))) Index: trunk-ovf/gcc/testsuite/gcc.dg/tree-ssa/overflow-1.c =================================================================== --- trunk-ovf/gcc/testsuite/gcc.dg/tree-ssa/overflow-1.c (revision 0) +++ trunk-ovf/gcc/testsuite/gcc.dg/tree-ssa/overflow-1.c (working copy) @@ -0,0 +1,16 @@ +/* { dg-do compile } */ +/* { dg-options "-O -fdump-tree-optimized" } */ + +int f(unsigned a){ + unsigned b=5; + unsigned c=a-b; + return c>a; +} +int g(unsigned a){ + unsigned b=32; + unsigned c=a+b; + return c<a; +} + +/* { dg-final { scan-tree-dump "a_\[0-9\]+.D. <= 4;" "optimized" } } */ +/* { dg-final { scan-tree-dump "a_\[0-9\]+.D. > 4294967263;" "optimized" } } */