On Tue, Apr 26, 2016 at 1:07 PM, Richard Biener
<richard.guent...@gmail.com> wrote:
> 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.
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" }
>> } */
>>
p
Description: Binary data
