| Message ID | 002d01d8c79f$dc5fe830$951fb890$@nextmovesoftware.com |
|---|---|
| State | New |
| Headers | show |
| Series | Optimize (X<<C)+(Y<<C) as (X+Y)<<C for signed addition. | expand |
On Tue, Sep 13, 2022 at 8:37 PM Roger Sayle <roger@nextmovesoftware.com> wrote: > > > This patch tweaks the match.pd transformation previously added to fold > (X<<C)+(Y<<C) as (X+Y)<<C that was previously restricted to unsigned > (wrapping) types, to also allow signed integer types provided that they > don't trap and the overflow needn't be preserved for sanitization. > i.e. this should now apply (by default) for "int x,y;", but is disabled > with -ftrapv. > > This unsigned transformation has baked on mainline without problems, so it's > time to turn up the heat... LLVM, icc and MSVC perform this optimization. > > > This patch has been tested on x86_64-pc-linux-gnu with make bootstrap and > make -k check, both with and without --target_board=unix{-m32}, with no > new failures. Ok for mainline? OK. Thanks, Richard. > > > 2022-09-13 Roger Sayle <roger@nextmovesoftware.com> > > gcc/ChangeLog > * match.pd (op (lshift @0 @1) (lshift @2 @1)): Optimize the > expression (X<<C) + (Y<<C) to (X+Y)<<C for signed types, that > may have undefined overflow, provided that they don't trap. > > gcc/testsuite/ChangeLog > * gcc.dg/pr71343-3.c: New test case. > > > Thanks in advance, > Roger > -- >
On Tue, 13 Sep 2022, Roger Sayle wrote: > This patch tweaks the match.pd transformation previously added to fold > (X<<C)+(Y<<C) as (X+Y)<<C that was previously restricted to unsigned > (wrapping) types, to also allow signed integer types provided that they > don't trap and the overflow needn't be preserved for sanitization. > i.e. this should now apply (by default) for "int x,y;", but is disabled > with -ftrapv. In https://gcc.gnu.org/onlinedocs/gcc/Integers-implementation.html , I read: "Bitwise operators act on the representation of the value including both the sign and value bits, where the sign bit is considered immediately above the highest-value value bit. Signed ‘>>’ acts on negative numbers by sign extension. As an extension to the C language, GCC does not use the latitude given in C99 and C11 only to treat certain aspects of signed ‘<<’ as undefined." To me, this means that for instance INT_MIN<<1 is well defined and evaluates to 0. But with this patch we turn (INT_MIN<<1)+(INT_MIN<<1) into (INT_MIN+INT_MIN)<<1, which is UB. If we decide not to support this extension anymore, I think we need to change the documentation first.
On Wed, Sep 14, 2022 at 11:42 PM Marc Glisse via Gcc-patches <gcc-patches@gcc.gnu.org> wrote: > > On Tue, 13 Sep 2022, Roger Sayle wrote: > > > This patch tweaks the match.pd transformation previously added to fold > > (X<<C)+(Y<<C) as (X+Y)<<C that was previously restricted to unsigned > > (wrapping) types, to also allow signed integer types provided that they > > don't trap and the overflow needn't be preserved for sanitization. > > i.e. this should now apply (by default) for "int x,y;", but is disabled > > with -ftrapv. > > In https://gcc.gnu.org/onlinedocs/gcc/Integers-implementation.html , I > read: > > "Bitwise operators act on the representation of the value including both > the sign and value bits, where the sign bit is considered immediately > above the highest-value value bit. Signed ‘>>’ acts on negative numbers by > sign extension. > > As an extension to the C language, GCC does not use the latitude given in > C99 and C11 only to treat certain aspects of signed ‘<<’ as undefined." Oh, I wasn't aware of that. > To me, this means that for instance INT_MIN<<1 is well defined and > evaluates to 0. But with this patch we turn (INT_MIN<<1)+(INT_MIN<<1) into > (INT_MIN+INT_MIN)<<1, which is UB. > > If we decide not to support this extension anymore, I think we need to > change the documentation first. Or perform the (X+Y) operation in an unsigned type. Richard. > -- > Marc Glisse
diff --git a/gcc/match.pd b/gcc/match.pd index 17318f52..e1e6af9 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -988,7 +988,8 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (simplify (op (lshift:s @0 @1) (lshift:s @2 @1)) (if (INTEGRAL_TYPE_P (type) - && TYPE_OVERFLOW_WRAPS (type) + && !TYPE_OVERFLOW_SANITIZED (type) + && !TYPE_OVERFLOW_TRAPS (type) && !TYPE_SATURATING (type)) (lshift (op @0 @2) @1)))) diff --git a/gcc/testsuite/gcc.dg/pr71343-3.c b/gcc/testsuite/gcc.dg/pr71343-3.c new file mode 100644 index 0000000..d0bdbae --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr71343-3.c @@ -0,0 +1,15 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int foo(int a, int b) +{ + return (a << 2) + (b << 2); +} + +int bar(int a, int b) +{ + return (a << 2) + (b << 2) == (a + b) << 2; +} + +/* { dg-final { scan-tree-dump-times " << " 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized" } } */
This patch tweaks the match.pd transformation previously added to fold (X<<C)+(Y<<C) as (X+Y)<<C that was previously restricted to unsigned (wrapping) types, to also allow signed integer types provided that they don't trap and the overflow needn't be preserved for sanitization. i.e. this should now apply (by default) for "int x,y;", but is disabled with -ftrapv. This unsigned transformation has baked on mainline without problems, so it's time to turn up the heat... LLVM, icc and MSVC perform this optimization. This patch has been tested on x86_64-pc-linux-gnu with make bootstrap and make -k check, both with and without --target_board=unix{-m32}, with no new failures. Ok for mainline? 2022-09-13 Roger Sayle <roger@nextmovesoftware.com> gcc/ChangeLog * match.pd (op (lshift @0 @1) (lshift @2 @1)): Optimize the expression (X<<C) + (Y<<C) to (X+Y)<<C for signed types, that may have undefined overflow, provided that they don't trap. gcc/testsuite/ChangeLog * gcc.dg/pr71343-3.c: New test case. Thanks in advance, Roger --