On Sun, Apr 24, 2016 at 7:24 PM, Marc Glisse <marc.gli...@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.gli...@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" }
> } */
>
