[PATCH] Fold sign of LSHIFT_EXPR to eliminate no-op conversions.

[PATCH] Fold sign of LSHIFT_EXPR to eliminate no-op conversions.

[Roger Sayle]

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


This short patch teaches fold that it is "safe" to change the sign
of a left shift, to reduce the number of type conversions in gimple.
As an example:

unsigned int foo(unsigned int i) {
  return (int)i << 8;
}

is currently optimized to:

unsigned int foo (unsigned int i)
{
  int i.0_1;
  int _2;
  unsigned int _4;

  <bb 2> [local count: 1073741824]:
  i.0_1 = (int) i_3(D);
  _2 = i.0_1 << 8;
  _4 = (unsigned int) _2;
  return _4;
}

with this patch, this now becomes:

unsigned int foo (unsigned int i)
{
  unsigned int _2;

  <bb 2> [local count: 1073741824]:
  _2 = i_1(D) << 8;
  return _2;
}

which generates exactly the same assembly language.  Aside from the
reduced memory usage, the real benefit is that no-op conversions tend
to interfere with many folding optimizations.  For example,

unsigned int bar(unsigned char i) {
    return (i ^ (i<<16)) | (i<<8);
}

currently gets (tangled in conversions and) optimized to:

unsigned int bar (unsigned char i)
{
  unsigned int _1;
  unsigned int _2;
  int _3;
  int _4;
  unsigned int _6;
  unsigned int _8;

  <bb 2> [local count: 1073741824]:
  _1 = (unsigned int) i_5(D);
  _2 = _1 * 65537;
  _3 = (int) i_5(D);
  _4 = _3 << 8;
  _8 = (unsigned int) _4;
  _6 = _2 | _8;
  return _6;
}

but with this patch, bar now optimizes down to:

unsigned int bar(unsigned char i)
{
  unsigned int _1;
  unsigned int _4;

  <bb 2> [local count: 1073741824]:
  _1 = (unsigned int) i_3(D);
  _4 = _1 * 65793;
  return _4;

}


This patch has been tested on x86_64-pc-linux-gnu with "make bootstrap"
and "make -k check" with no new failures.  Ok for mainline?


2021-08-23  Roger Sayle  <roger@nextmovesoftware.com>

gcc/ChangeLog
	* match.pd (shift transformations): Change the sign of an
	LSHIFT_EXPR if it reduces the number of explicit conversions.

gcc/testsuite/ChangeLog
	* gcc.dg/fold-convlshift-1.c: New test case.
	* gcc.dg/fold-convlshift-2.c: New test case.


Roger
--


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

diff --git a/gcc/match.pd b/gcc/match.pd
index 0fcfd0e..978a1b0 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -3385,6 +3385,15 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
     (if (integer_zerop (@2) || integer_all_onesp (@2))
      (cmp @0 @2)))))
 
+/* Both signed and unsigned lshift produce the same result, so use
+   the form that minimizes the number of conversions.  */
+(simplify
+ (convert (lshift:s@0 (convert:s@1 @2) INTEGER_CST@3))
+ (if (tree_nop_conversion_p (type, TREE_TYPE (@0))
+      && INTEGRAL_TYPE_P (TREE_TYPE (@2))
+      && TYPE_PRECISION (TREE_TYPE (@2)) <= TYPE_PRECISION (type))
+  (lshift (convert @2) @3)))
+
 /* Simplifications of conversions.  */
 
 /* Basic strip-useless-type-conversions / strip_nops.  */

[-- Attachment #3: fold-convlshift-1.c --]
[-- Type: text/plain, Size: 406 bytes --]

/* { dg-do compile } */
/* { dg-options "-O2 -fdump-tree-optimized" } */

unsigned int foo(unsigned int i)
{
  int t1 = i;
  int t2 = t1 << 8;
  return t2;
}

int bar(int i)
{
  unsigned int t1 = i;
  unsigned int t2 = t1 << 8;
  return t2;
}

/* { dg-final { scan-tree-dump-not "\\(int\\)" "optimized" } } */
/* { dg-final { scan-tree-dump-not "\\(unsigned int\\)" "optimized" } } */


[-- Attachment #4: fold-convlshift-2.c --]
[-- Type: text/plain, Size: 425 bytes --]

/* { dg-do compile } */
/* { dg-options "-O2 -fdump-tree-optimized" } */

unsigned int foo(unsigned char c)
{
  int t1 = c;
  int t2 = t1 << 8;
  return t2;
}

int bar(unsigned char c)
{
  unsigned int t1 = c;
  unsigned int t2 = t1 << 8;
  return t2;
}

/* { dg-final { scan-tree-dump-times "\\(int\\)" 1 "optimized" } } */
/* { dg-final { scan-tree-dump-times "\\(unsigned int\\)" 1 "optimized" } } */

Re: [PATCH] Fold sign of LSHIFT_EXPR to eliminate no-op conversions.

[Jeff Law]

On 8/22/2021 6:25 PM, Roger Sayle wrote:
> This short patch teaches fold that it is "safe" to change the sign
> of a left shift, to reduce the number of type conversions in gimple.
> As an example:
>
> unsigned int foo(unsigned int i) {
>    return (int)i << 8;
> }
>
> is currently optimized to:
>
> unsigned int foo (unsigned int i)
> {
>    int i.0_1;
>    int _2;
>    unsigned int _4;
>
>    <bb 2> [local count: 1073741824]:
>    i.0_1 = (int) i_3(D);
>    _2 = i.0_1 << 8;
>    _4 = (unsigned int) _2;
>    return _4;
> }
>
> with this patch, this now becomes:
>
> unsigned int foo (unsigned int i)
> {
>    unsigned int _2;
>
>    <bb 2> [local count: 1073741824]:
>    _2 = i_1(D) << 8;
>    return _2;
> }
>
> which generates exactly the same assembly language.  Aside from the
> reduced memory usage, the real benefit is that no-op conversions tend
> to interfere with many folding optimizations.  For example,
>
> unsigned int bar(unsigned char i) {
>      return (i ^ (i<<16)) | (i<<8);
> }
>
> currently gets (tangled in conversions and) optimized to:
>
> unsigned int bar (unsigned char i)
> {
>    unsigned int _1;
>    unsigned int _2;
>    int _3;
>    int _4;
>    unsigned int _6;
>    unsigned int _8;
>
>    <bb 2> [local count: 1073741824]:
>    _1 = (unsigned int) i_5(D);
>    _2 = _1 * 65537;
>    _3 = (int) i_5(D);
>    _4 = _3 << 8;
>    _8 = (unsigned int) _4;
>    _6 = _2 | _8;
>    return _6;
> }
>
> but with this patch, bar now optimizes down to:
>
> unsigned int bar(unsigned char i)
> {
>    unsigned int _1;
>    unsigned int _4;
>
>    <bb 2> [local count: 1073741824]:
>    _1 = (unsigned int) i_3(D);
>    _4 = _1 * 65793;
>    return _4;
>
> }
>
>
> This patch has been tested on x86_64-pc-linux-gnu with "make bootstrap"
> and "make -k check" with no new failures.  Ok for mainline?
>
>
> 2021-08-23  Roger Sayle  <roger@nextmovesoftware.com>
>
> gcc/ChangeLog
> 	* match.pd (shift transformations): Change the sign of an
> 	LSHIFT_EXPR if it reduces the number of explicit conversions.
>
> gcc/testsuite/ChangeLog
> 	* gcc.dg/fold-convlshift-1.c: New test case.
> 	* gcc.dg/fold-convlshift-2.c: New test case.
Presumably we're relying on the fact that the type of the convert:@1 has 
to be the same type as @0, thus there's no need to check anything 
related to @1.

OK
jeff

Re: [PATCH] Fold sign of LSHIFT_EXPR to eliminate no-op conversions.

[Jakub Jelinek]

On Mon, Aug 23, 2021 at 01:25:13AM +0100, Roger Sayle wrote:
> This patch has been tested on x86_64-pc-linux-gnu with "make bootstrap"
> and "make -k check" with no new failures.  Ok for mainline?
> 
> 
> 2021-08-23  Roger Sayle  <roger@nextmovesoftware.com>
> 
> gcc/ChangeLog
> 	* match.pd (shift transformations): Change the sign of an
> 	LSHIFT_EXPR if it reduces the number of explicit conversions.

This broke bootstrap on i686-linux, where it incorrectly simplifies
a cast from LSHIFT_EXPR with integral type to pointer type of the
same precision into LSHIFT_EXPR performed on the pointer type,
which is invalid IL.

> diff --git a/gcc/match.pd b/gcc/match.pd
> index 0fcfd0e..978a1b0 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -3385,6 +3385,15 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>      (if (integer_zerop (@2) || integer_all_onesp (@2))
>       (cmp @0 @2)))))
>  
> +/* Both signed and unsigned lshift produce the same result, so use
> +   the form that minimizes the number of conversions.  */
> +(simplify
> + (convert (lshift:s@0 (convert:s@1 @2) INTEGER_CST@3))
> + (if (tree_nop_conversion_p (type, TREE_TYPE (@0))

I think you want
	&& INTEGRAL_TYPE_P (TREE_TYPE (@1))
here as well.

> +      && INTEGRAL_TYPE_P (TREE_TYPE (@2))
> +      && TYPE_PRECISION (TREE_TYPE (@2)) <= TYPE_PRECISION (type))
> +  (lshift (convert @2) @3)))
> +

	Jakub

Re: [PATCH] Fold sign of LSHIFT_EXPR to eliminate no-op conversions.

[Andrew Pinski]

On Mon, Aug 23, 2021 at 1:09 PM Jakub Jelinek via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> On Mon, Aug 23, 2021 at 01:25:13AM +0100, Roger Sayle wrote:
> > This patch has been tested on x86_64-pc-linux-gnu with "make bootstrap"
> > and "make -k check" with no new failures.  Ok for mainline?
> >
> >
> > 2021-08-23  Roger Sayle  <roger@nextmovesoftware.com>
> >
> > gcc/ChangeLog
> >       * match.pd (shift transformations): Change the sign of an
> >       LSHIFT_EXPR if it reduces the number of explicit conversions.
>
> This broke bootstrap on i686-linux, where it incorrectly simplifies
> a cast from LSHIFT_EXPR with integral type to pointer type of the
> same precision into LSHIFT_EXPR performed on the pointer type,
> which is invalid IL.

And a reduced testcase for that failure can be found in PR 102029 too.

Thanks,
Andrew

>
> > diff --git a/gcc/match.pd b/gcc/match.pd
> > index 0fcfd0e..978a1b0 100644
> > --- a/gcc/match.pd
> > +++ b/gcc/match.pd
> > @@ -3385,6 +3385,15 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> >      (if (integer_zerop (@2) || integer_all_onesp (@2))
> >       (cmp @0 @2)))))
> >
> > +/* Both signed and unsigned lshift produce the same result, so use
> > +   the form that minimizes the number of conversions.  */
> > +(simplify
> > + (convert (lshift:s@0 (convert:s@1 @2) INTEGER_CST@3))
> > + (if (tree_nop_conversion_p (type, TREE_TYPE (@0))
>
> I think you want
>         && INTEGRAL_TYPE_P (TREE_TYPE (@1))
> here as well.
>
> > +      && INTEGRAL_TYPE_P (TREE_TYPE (@2))
> > +      && TYPE_PRECISION (TREE_TYPE (@2)) <= TYPE_PRECISION (type))
> > +  (lshift (convert @2) @3)))
> > +
>
>         Jakub
>