[PATCH] Optimize (X<<C)+(Y<<C) as (X+Y)<<C for signed addition.

[PATCH] Optimize (X<<C)+(Y<<C) as (X+Y)<<C for signed addition.

[Roger Sayle]

[-- Attachment #1: Type: text/plain, Size: 1077 bytes --]


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
--


[-- Attachment #2: patchfd3.txt --]
[-- Type: text/plain, Size: 1011 bytes --]

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" } } */

Re: [PATCH] Optimize (X<<C)+(Y<<C) as (X+Y)<<C for signed addition.

[Richard Biener]

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
> --
>

Re: [PATCH] Optimize (X<<C)+(Y<<C) as (X+Y)<<C for signed addition.

[Marc Glisse]

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.

-- 
Marc Glisse

Re: [PATCH] Optimize (X<<C)+(Y<<C) as (X+Y)<<C for signed addition.

[Richard Biener]

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