[PATCH] Fix redundant load missed by fre [tree-optimization 92980]

[PATCH] Fix redundant load missed by fre [tree-optimization 92980]

[Hongtao Liu]

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

Hi:
  This patch is to simplify A * C + (-D) -> (A - D/C) * C when C is a
power of 2 and D mod C == 0.
  bootstrap and make check is ok.

changelog
gcc/
        * gcc/match.pd (A * C + (-D) = (A - D/C) * C. when C is a
        power of 2 and D mod C == 0): Add new simplification.

gcc/testsuite
        * gcc.dg/pr92980.c: New test.

-- 
BR,
Hongtao

[-- Attachment #2: 0001-Simplify-A-C-D-A-D-C-C.-when-C-is-a-power-of-2.patch --]
[-- Type: text/x-patch, Size: 2738 bytes --]

From 41f76f29f0070082e29082460efdb0bb9b9869f7 Mon Sep 17 00:00:00 2001
From: liuhongt <hongtao.liu@intel.com>
Date: Fri, 13 Dec 2019 15:52:02 +0800
Subject: [PATCH] Simplify A * C + (-D) = (A - D/C) * C. when C is a power of 2
 and D mod C == 0.

gcc/
	* gcc/match.pd (A * C + (-D) = (A - D/C) * C. when C is a
	power of 2 and D mod C == 0): Add new simplification.

gcc/testsuite
	* gcc.dg/pr92980.c: New test.
---
 gcc/match.pd                   | 20 ++++++++++++++++
 gcc/testsuite/gcc.dg/pr92980.c | 43 ++++++++++++++++++++++++++++++++++
 2 files changed, 63 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/pr92980.c

diff --git a/gcc/match.pd b/gcc/match.pd
index dda86964b4c..a128733e2c3 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -4297,6 +4297,26 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
   (if (tree_single_nonzero_warnv_p (@0, NULL))
    { constant_boolean_node (cmp == NE_EXPR, type); })))
 
+/* Simplify A * C + (-D) = (A - D/C) * C. when C is a power of 2
+   and D mod C == 0.  */
+(simplify
+ (plus (mult @0 integer_pow2p@1) INTEGER_CST@2)
+ (if (TREE_CODE (TREE_TYPE (@0)) == INTEGER_TYPE
+     && TYPE_UNSIGNED (TREE_TYPE (@0))
+     && tree_fits_uhwi_p (@1)
+     && tree_fits_uhwi_p (@2))
+  (with
+   {
+     unsigned HOST_WIDE_INT c = tree_to_uhwi (@1);
+     unsigned HOST_WIDE_INT d = tree_to_uhwi (@2);
+     HOST_WIDE_INT neg_p = wi::sign_mask (d);
+     unsigned HOST_WIDE_INT negd = HOST_WIDE_INT_0U - d;
+     unsigned HOST_WIDE_INT modd = negd % c;
+     unsigned HOST_WIDE_INT divd = negd / c;
+    }
+   (if (neg_p && modd == HOST_WIDE_INT_0U)
+    (mult (minus @0 { build_int_cst (TREE_TYPE (@2), divd);}) @1)))))
+
 /* If we have (A & C) == C where C is a power of 2, convert this into
    (A & C) != 0.  Similarly for NE_EXPR.  */
 (for cmp (eq ne)
diff --git a/gcc/testsuite/gcc.dg/pr92980.c b/gcc/testsuite/gcc.dg/pr92980.c
new file mode 100644
index 00000000000..d7abf20788e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr92980.c
@@ -0,0 +1,43 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-fre" }  */
+
+int f1(short *src1, int i, int k, int n)
+{
+  int j = k + n;
+  short sum = src1[j];
+  sum += src1[j-1];
+  if (i <= k)
+    {
+      j+=2;
+      sum += src1[j-3];
+    }
+  return sum + j;
+}
+
+int f2(int *src1, int i, int k, int n)
+{
+  int j = k + n;
+  int sum = src1[j];
+  sum += src1[j-1];
+  if (i <= k)
+    {
+      j+=2;
+      sum += src1[j-3];
+    }
+  return sum + j;
+}
+
+int f3(long long *src1, int i, int k, int n)
+{
+  int j = k + n;
+  long long sum = src1[j];
+  sum += src1[j-1];
+  if (i <= k)
+    {
+      j+=2;
+      sum += src1[j-3];
+    }
+  return sum + j;
+}
+
+/* { dg-final { scan-tree-dump-times "= \\*" 6 "fre1" } }  */
-- 
2.18.1

Re: [PATCH] Fix redundant load missed by fre [tree-optimization 92980]

[Andrew Pinski]

On Tue, Dec 17, 2019 at 6:33 PM Hongtao Liu <crazylht@gmail.com> wrote:
>
> Hi:
>   This patch is to simplify A * C + (-D) -> (A - D/C) * C when C is a
> power of 2 and D mod C == 0.
>   bootstrap and make check is ok.

I don't see why D has to be negative here.


>TREE_CODE (TREE_TYPE (@0)) == INTEGER_TYPE
+     && TYPE_UNSIGNED (TREE_TYPE (@0))

This is the wrong check here.
Use INTEGRAL_TYPE_P .

>+ (plus (mult @0 integer_pow2p@1) INTEGER_CST@2)

 You might want a :s here for the mult and/or plus.

unsigned HOST_WIDE_INT d = tree_to_uhwi (@2);
...
Maybe use wide_int math instead of HOST_WIDE_INT here, then you don't
need the tree_fits_uhwi_p check.

Add a testcase should tests the pattern directly rather than indirectly.

Also we are in stage 3 which means bug fixes only so this might/should
wait until stage 1.

Thanks,
Andrew Pinski

>
> changelog
> gcc/
>         * gcc/match.pd (A * C + (-D) = (A - D/C) * C. when C is a
>         power of 2 and D mod C == 0): Add new simplification.
>
> gcc/testsuite
>         * gcc.dg/pr92980.c: New test.
>
> --
> BR,
> Hongtao

Re: [PATCH] Fix redundant load missed by fre [tree-optimization 92980]

[Hongtao Liu]

On Wed, Dec 18, 2019 at 10:50 AM Andrew Pinski <pinskia@gmail.com> wrote:
>
> On Tue, Dec 17, 2019 at 6:33 PM Hongtao Liu <crazylht@gmail.com> wrote:
> >
> > Hi:
> >   This patch is to simplify A * C + (-D) -> (A - D/C) * C when C is a
> > power of 2 and D mod C == 0.
> >   bootstrap and make check is ok.
>
> I don't see why D has to be negative here.
>
>
> >TREE_CODE (TREE_TYPE (@0)) == INTEGER_TYPE
> +     && TYPE_UNSIGNED (TREE_TYPE (@0))
>
> This is the wrong check here.
> Use INTEGRAL_TYPE_P .
>
> >+ (plus (mult @0 integer_pow2p@1) INTEGER_CST@2)
>
>  You might want a :s here for the mult and/or plus.
>
> unsigned HOST_WIDE_INT d = tree_to_uhwi (@2);
> ...
> Maybe use wide_int math instead of HOST_WIDE_INT here, then you don't
> need the tree_fits_uhwi_p check.
>
> Add a testcase should tests the pattern directly rather than indirectly.
>
> Also we are in stage 3 which means bug fixes only so this might/should
> wait until stage 1.

Yes, thanks.

>
> Thanks,
> Andrew Pinski
>
> >
> > changelog
> > gcc/
> >         * gcc/match.pd (A * C + (-D) = (A - D/C) * C. when C is a
> >         power of 2 and D mod C == 0): Add new simplification.
> >
> > gcc/testsuite
> >         * gcc.dg/pr92980.c: New test.
> >
> > --
> > BR,
> > Hongtao



-- 
BR,
Hongtao

Re: [PATCH] Fix redundant load missed by fre [tree-optimization 92980]

[Segher Boessenkool]

On Wed, Dec 18, 2019 at 10:37:11AM +0800, Hongtao Liu wrote:
> Hi:
>   This patch is to simplify A * C + (-D) -> (A - D/C) * C when C is a
> power of 2 and D mod C == 0.
>   bootstrap and make check is ok.

Why would this be a good idea?  It is not reducing the number of
operators or similar?


Segher

Re: [PATCH] Fix redundant load missed by fre [tree-optimization 92980]

[Hongtao Liu]

On Wed, Dec 18, 2019 at 4:26 PM Segher Boessenkool
<segher@kernel.crashing.org> wrote:
>
> On Wed, Dec 18, 2019 at 10:37:11AM +0800, Hongtao Liu wrote:
> > Hi:
> >   This patch is to simplify A * C + (-D) -> (A - D/C) * C when C is a
> > power of 2 and D mod C == 0.
> >   bootstrap and make check is ok.
>
> Why would this be a good idea?  It is not reducing the number of
> operators or similar?
>
It helps VN, so that fre will delete redundant load.
>
> Segher



-- 
BR,
Hongtao

Re: [PATCH] Fix redundant load missed by fre [tree-optimization 92980]

[Andrew Pinski]

On Wed, Dec 18, 2019 at 1:18 AM Hongtao Liu <crazylht@gmail.com> wrote:
>
> On Wed, Dec 18, 2019 at 4:26 PM Segher Boessenkool
> <segher@kernel.crashing.org> wrote:
> >
> > On Wed, Dec 18, 2019 at 10:37:11AM +0800, Hongtao Liu wrote:
> > > Hi:
> > >   This patch is to simplify A * C + (-D) -> (A - D/C) * C when C is a
> > > power of 2 and D mod C == 0.
> > >   bootstrap and make check is ok.
> >
> > Why would this be a good idea?  It is not reducing the number of
> > operators or similar?
> >
> It helps VN, so that fre will delete redundant load.

It is basically doing a factoring and undoing an optimization that was
done in the front-end (see pointer_int_sum in c-common.c).
But I think the optimization in the front-end should be removed.  It
dates from 1992, a time when GCC did not anything on the tree level
and there was no GCSE (PRE) and the CSE was limited.

Thanks,
Andrew Pinski


> >
> > Segher
>
>
>
> --
> BR,
> Hongtao

Re: [PATCH] Fix redundant load missed by fre [tree-optimization 92980]

[Richard Biener]

On Wed, Dec 18, 2019 at 10:59 AM Andrew Pinski <pinskia@gmail.com> wrote:
>
> On Wed, Dec 18, 2019 at 1:18 AM Hongtao Liu <crazylht@gmail.com> wrote:
> >
> > On Wed, Dec 18, 2019 at 4:26 PM Segher Boessenkool
> > <segher@kernel.crashing.org> wrote:
> > >
> > > On Wed, Dec 18, 2019 at 10:37:11AM +0800, Hongtao Liu wrote:
> > > > Hi:
> > > >   This patch is to simplify A * C + (-D) -> (A - D/C) * C when C is a
> > > > power of 2 and D mod C == 0.

Looks like a subset of what fold_plusminus_mult_expr does?

> > > >   bootstrap and make check is ok.
> > >
> > > Why would this be a good idea?  It is not reducing the number of
> > > operators or similar?
> > >
> > It helps VN, so that fre will delete redundant load.

So it's basically a canonicalization.  What you have to watch for is
code doing the reverse (extract_muldiv and the associate: cases in
fold-const.c are a bad example here).

> It is basically doing a factoring and undoing an optimization that was
> done in the front-end (see pointer_int_sum in c-common.c).
> But I think the optimization in the front-end should be removed.  It
> dates from 1992, a time when GCC did not anything on the tree level
> and there was no GCSE (PRE) and the CSE was limited.

Agreed (as this is a premature point).  But not at this point - I think I tried
this and there's quite some fallout.

Also always watch for unefined overflow issues.

Richard.

> Thanks,
> Andrew Pinski
>
>
> > >
> > > Segher
> >
> >
> >
> > --
> > BR,
> > Hongtao