[Bug middle-end/40168] New: missing unrolling/scalarization/reassoc/free

[Bug middle-end/40168] New: missing unrolling/scalarization/reassoc/free

[jv244 at cam dot ac dot uk]

The testcase to be attached can be compiled with

gfortran -O3 -march=native -ffast-math -funroll-loops -ffree-line-length-200
test.f90 

and as discussed in 
http://gcc.gnu.org/ml/gcc/2009-05/msg00416.html
shows some limitations in optimization of gcc 4.3 4.4 and 4.5


-- 
           Summary: missing unrolling/scalarization/reassoc/free
           Product: gcc
           Version: 4.5.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: middle-end
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: jv244 at cam dot ac dot uk


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40168

[Bug middle-end/40168] missing unrolling/scalarization/reassoc/free

[jv244 at cam dot ac dot uk]

------- Comment #1 from jv244 at cam dot ac dot uk  2009-05-16 09:36 -------
Created an attachment (id=17883)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=17883&action=view)
testcase


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40168

[Bug fortran/40168] missing unrolling/scalarization/reassoc/free

[rguenth at gcc dot gnu dot org]

------- Comment #2 from rguenth at gcc dot gnu dot org  2009-05-16 09:54 -------
translating

           buffer1 = 0.0_dp

to

           (void) __builtin_memset ((void *) &buffer1, 0, 648);

pessimizes the middle-end analysis because buffer1 is now addressable and
escapes.  The maybe valid (if not we'll fix it) form

           buffer1 = {};

would be prefered here (CONSTRUCTOR with no elements).


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu dot
                   |                            |org
           Severity|normal                      |enhancement
          Component|middle-end                  |fortran


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40168

[Bug fortran/40168] missing unrolling/scalarization/reassoc/free

[rguenth at gcc dot gnu dot org]

------- Comment #3 from rguenth at gcc dot gnu dot org  2009-05-16 10:04 -------
Like so:

Index: trans-expr.c
===================================================================
--- trans-expr.c        (revision 147583)
+++ trans-expr.c        (working copy)
@@ -4430,7 +4430,8 @@ gfc_trans_zero_assign (gfc_expr * expr)

   /* Convert arguments to the correct types.  */
   if (!POINTER_TYPE_P (TREE_TYPE (dest)))
-    dest = gfc_build_addr_expr (pvoid_type_node, dest);
+    return build2 (MODIFY_EXPR, void_type_node,
+                  dest, build_constructor (TREE_TYPE (dest), NULL));
   else
     dest = fold_convert (pvoid_type_node, dest);
   len = fold_convert (size_type_node, len);


that leaves FRE to figure that it can CSE a zero from

    array1 = {};

in

  buffer1 = {};
  D.2743_415 = buffer1[54];

and similar cases.  buffer2 is later scalarized by SRA.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40168

[Bug fortran/40168] missing unrolling/scalarization/reassoc/free

[jv244 at cam dot ac dot uk]

------- Comment #4 from jv244 at cam dot ac dot uk  2009-05-16 11:19 -------
(In reply to comment #3)
> Like so:
> 
> Index: trans-expr.c
> ===================================================================
> --- trans-expr.c        (revision 147583)
> +++ trans-expr.c        (working copy)
> @@ -4430,7 +4430,8 @@ gfc_trans_zero_assign (gfc_expr * expr)
> 
>    /* Convert arguments to the correct types.  */
>    if (!POINTER_TYPE_P (TREE_TYPE (dest)))
> -    dest = gfc_build_addr_expr (pvoid_type_node, dest);
> +    return build2 (MODIFY_EXPR, void_type_node,
> +                  dest, build_constructor (TREE_TYPE (dest), NULL));
>    else
>      dest = fold_convert (pvoid_type_node, dest);
>    len = fold_convert (size_type_node, len);

this seems to speedup this case by somewhat, but not quite as much as the
hand-coded version (even with the other unroll parameters).

However, another testcase I run automatically when building gcc is much faster
with a patched trunk than unpatched trunk from a week ago. I will try to see if
this is due to this patch alone.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40168

[Bug fortran/40168] missing unrolling/scalarization/reassoc/free

[rguenth at gcc dot gnu dot org]

------- Comment #5 from rguenth at gcc dot gnu dot org  2009-05-16 11:20 -------
With that patch and

-O3 -ffast-math -funroll-loops -mfpmath=sse -msse2 --param
max-completely-peel-times=27 --param max-completely-peeled-insns=1500

--params for allow unrolling of all innermost loops I get

./test
 Sparse: time[s]   0.68804300    
 New: time[s]   0.40802497    
     speedup    1.6862767    
      Glfops    1.5881380    
 Error:   1.11022302462515654E-016

which isn't too bad.  The rest of the difference might be attributed to
unfortunate scheduling or that multiplication thing (PRE skips a lot
of multiplication hoisting opportunities because they look like
induction variables though LIM later hoists them).

With the above flags and -fno-ivopts (looking what dump stuff it does
again...) I get

./test
 Sparse: time[s]   0.58003598    
 New: time[s]   0.62803900    
     speedup   0.92356682    
      Glfops    1.0317831    
 Error:   1.11022302462515654E-016


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40168

[Bug fortran/40168] missing unrolling/scalarization/reassoc/free

[jv244 at cam dot ac dot uk]

------- Comment #6 from jv244 at cam dot ac dot uk  2009-05-16 11:31 -------
(In reply to comment #5)
This looks somewhat different from what I get here.

trunk without patch:

vondele@pcihopt3:/data03/vondele/contract> gfortran -O3 -march=native
-ffast-math -funroll-loops -ffree-line-length-200 --param
max-completely-peel-times=27 --param max-completely-peeled-insns=666 test.f90 ;
./a.out
 Sparse: time[s]   0.70804399
 New: time[s]   0.21201301
     speedup    3.3396254
      Glfops    3.0564163
 Error:   1.11022302462515654E-016

vondele@pcihopt3:/data03/vondele/contract> gfortran -O3 -march=native
-ffast-math -funroll-loops -ffree-line-length-200  test.f90 ; ./a.out
 Sparse: time[s]   0.61203802
 New: time[s]   0.20801300
     speedup    2.9423065
      Glfops    3.1151900
 Error:   1.11022302462515654E-016

with patch:
vondele@pcihopt3:/data03/vondele/contract> gfortran -O3 -march=native
-ffast-math -funroll-loops -ffree-line-length-200 --param
max-completely-peel-times=27 --param max-completely-peeled-insns=666 test.f90 ;
./a.out
 Sparse: time[s]   0.60403699
 New: time[s]   0.21201402
     speedup    2.8490427
      Glfops    3.0564015
 Error:   1.11022302462515654E-016

with 4.4_branch:

vondele@pcihopt3:/data03/vondele/contract> gfortran -O3 -march=native
-ffast-math -funroll-loops -ffree-line-length-200 --param
max-completely-peel-times=27 --param max-completely-peeled-insns=666 test.f90 ;
./a.out
 Sparse: time[s]   0.70404398
 New: time[s]   0.20401198
     speedup    3.4509933
      Glfops    3.1762841
 Error:   1.11022302462515654E-016
vondele@pcihopt3:/data03/vondele/contract> gfortran -O3 -march=native
-ffast-math -funroll-loops -ffree-line-length-200 test.f90 ; ./a.out
 Sparse: time[s]   0.66804200
 New: time[s]   0.20801300
     speedup    3.2115397
      Glfops    3.1151900
 Error:   1.11022302462515654E-016

-march=native goes to :
-march=k8-sse3 -mcx16 -msahf --param l1-cache-size=64 --param
l1-cache-line-size=64 --param l2-cache-size=1024 -mtune=k8


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40168

[Bug fortran/40168] missing unrolling/scalarization/reassoc/free

[rguenther at suse dot de]

------- Comment #7 from rguenther at suse dot de  2009-05-16 11:39 -------
Subject: Re:  missing
 unrolling/scalarization/reassoc/free

On Sat, 16 May 2009, jv244 at cam dot ac dot uk wrote:

> ------- Comment #6 from jv244 at cam dot ac dot uk  2009-05-16 11:31 -------
> (In reply to comment #5)
> This looks somewhat different from what I get here.
> 
> trunk without patch:
> 
> vondele@pcihopt3:/data03/vondele/contract> gfortran -O3 -march=native
> -ffast-math -funroll-loops -ffree-line-length-200 --param
> max-completely-peel-times=27 --param max-completely-peeled-insns=666 test.f90 ;
> ./a.out

try --param max-completely-peeled-insns=1500 to also get the last 
innermost loop unrolled (that blocks scalarization of buffer1, with
the patch).

I'm testing on i?86.

Richard.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40168

[Bug fortran/40168] missing unrolling/scalarization/reassoc/free

[jv244 at cam dot ac dot uk]

------- Comment #8 from jv244 at cam dot ac dot uk  2009-05-16 12:20 -------
(In reply to comment #7)
> Subject: Re:  missing
>  unrolling/scalarization/reassoc/free

so, double good news.

First, the unrelated other testcase that speeds up by 30% does this thanks to
this patch only. This is a really significant gain since it is a real CP2K run,
not a micro-benchmark.

Second, the current testcase gets great results, i.e. reproducing the
hand-optimized code in efficiency using the unroll parameters and the no-ivopts
flag.

gfortran -O3 -march=native -ffast-math -funroll-loops -ffree-line-length-200
--param max-completely-peel-times=27 --param max-completely-peeled-insns=2000
-fno-ivopts test.f90 ; ./a.out
 Sparse: time[s]   0.24001500
 New: time[s]   0.22401398
     speedup    1.0714287
      Glfops    2.8926766
 Error:    0.0000000000000000


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40168

[Bug fortran/40168] missing unrolling/scalarization/reassoc/free

[jv244 at cam dot ac dot uk]

------- Comment #9 from jv244 at cam dot ac dot uk  2009-05-16 12:39 -------
BTW, the patch also applies to 4.4_branch and has the same positive effect...
pretty please ?


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40168

[Bug fortran/40168] missing unrolling/scalarization/reassoc/free

[jvdelisle at gcc dot gnu dot org]

------- Comment #10 from jvdelisle at gcc dot gnu dot org  2009-05-16 13:46 -------
Nice for a one liner patch. 


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40168

[Bug fortran/40168] missing unrolling/scalarization/reassoc/free

[pinskia at gcc dot gnu dot org]

------- Comment #11 from pinskia at gcc dot gnu dot org  2009-05-16 14:48 -------
Part of this optimization could (should) be done in the middle-end see PR
36602.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40168

[Bug fortran/40168] missing unrolling/scalarization/reassoc/free

[rguenth at gcc dot gnu dot org]

------- Comment #12 from rguenth at gcc dot gnu dot org  2009-05-18 08:53 -------
I'm now testing the one-liner.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40168

[Bug fortran/40168] missing unrolling/scalarization/reassoc/free

[rguenth at gcc dot gnu dot org]

------- Comment #13 from rguenth at gcc dot gnu dot org  2009-05-18 10:24 -------
Subject: Bug 40168

Author: rguenth
Date: Mon May 18 10:24:34 2009
New Revision: 147659

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=147659
Log:
2009-05-18  Richard Guenther  <rguenther@suse.de>

        PR fortran/40168
        * trans-expr.c (gfc_trans_zero_assign): For local array
        destinations use an assignment from an empty constructor.

        * gfortran.dg/array_memset_2.f90: Adjust.

Modified:
    trunk/gcc/fortran/ChangeLog
    trunk/gcc/fortran/trans-expr.c
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/gfortran.dg/array_memset_2.f90


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40168

[Bug fortran/40168] missing unrolling/scalarization/reassoc/free

[jv244 at cam dot ac dot uk]

------- Comment #14 from jv244 at cam dot ac dot uk  2009-05-18 12:19 -------
Created an attachment (id=17886)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=17886&action=view)
simplified testcase for common subexpressions.

Richard,

thanks very much for the first patch. I tried to get a better testcase for the
issue with the number of multiplies being too large (compile with gfortran -O3
-march=native -ffast-math -cpp test.f90). This is the newly attached
test_reassoc.f90. The module contains two equivalent subroutines S1 and S2. In
S1,  gcc manages to reduce the multiplies nearly to the optimal one (I believe
optimal is 81+81+9+9=180, gcc finds 198). In S2, which introduces a temporary
array somewhat like in the original, this doesn't happen, and the number of
multiplies is 324. Looks like the introduction of the temporary array blocks
some optimisation.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40168

[Bug fortran/40168] missing unrolling/scalarization/reassoc/free

[rguenth at gcc dot gnu dot org]

------- Comment #15 from rguenth at gcc dot gnu dot org  2009-05-27 11:01 -------
The issue is not the temporary array but the way how CSE works.  In S2 there
are simply no CSE opportunities - for example consider

  t1 = a * b;
  t2 = t1 * c;
  t3 = a * c;
  t4 = t3 * b;

The current CSE implementation cannot see the opportunity here.

(*b_3(D))[79] = (*b_3(D))[1] * (*s_1(D))[2] * (*s_1(D))[5] * (*s_1(D))[8] *
(*s_1(D))[10];

(*b_3(D))[80] = (*b_9(D))[0] * (*s_1(D))[2] * (*s_1(D))[5] * (*s_1(D))[8] *
(*s_1(D))[11];

I will try to do something here.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40168

[Bug fortran/40168] missing unrolling/scalarization/reassoc/free

[jv244 at cam dot ac dot uk]

------- Comment #16 from jv244 at cam dot ac dot uk  2009-06-06 07:08 -------
(In reply to comment #13)
> Subject: Bug 40168

Richard, this empty constructor patch was also OKed for 4.4 and has been on
mainline for a while. 

http://gcc.gnu.org/ml/fortran/2009-05/msg00288.html

Do you intend to commit this to 4.4.1?

Joost

> 
> Author: rguenth
> Date: Mon May 18 10:24:34 2009
> New Revision: 147659
> 
> URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=147659
> Log:
> 2009-05-18  Richard Guenther  <rguenther@suse.de>
> 
>         PR fortran/40168
>         * trans-expr.c (gfc_trans_zero_assign): For local array
>         destinations use an assignment from an empty constructor.
> 
>         * gfortran.dg/array_memset_2.f90: Adjust.
> 
> Modified:
>     trunk/gcc/fortran/ChangeLog
>     trunk/gcc/fortran/trans-expr.c
>     trunk/gcc/testsuite/ChangeLog
>     trunk/gcc/testsuite/gfortran.dg/array_memset_2.f90
> 


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40168

[Bug fortran/40168] missing unrolling/scalarization/reassoc/free

[rguenther at suse dot de]

------- Comment #17 from rguenther at suse dot de  2009-06-14 12:31 -------
Subject: Re:  missing
 unrolling/scalarization/reassoc/free

On Sat, 6 Jun 2009, jv244 at cam dot ac dot uk wrote:

> ------- Comment #16 from jv244 at cam dot ac dot uk  2009-06-06 07:08 -------
> (In reply to comment #13)
> > Subject: Bug 40168
> 
> Richard, this empty constructor patch was also OKed for 4.4 and has been on
> mainline for a while. 
> 
> http://gcc.gnu.org/ml/fortran/2009-05/msg00288.html
> 
> Do you intend to commit this to 4.4.1?

Yes, I had already bootstrapped & tested the patch on the branch.  I just
didn't manage to find the time to commit it yet.

Richard.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40168

[Bug fortran/40168] missing unrolling/scalarization/reassoc/free

[rguenth at gcc dot gnu dot org]

------- Comment #18 from rguenth at gcc dot gnu dot org  2009-06-14 13:39 -------
Subject: Bug 40168

Author: rguenth
Date: Sun Jun 14 13:39:37 2009
New Revision: 148469

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=148469
Log:
2009-06-14  Richard Guenther  <rguenther@suse.de>

        Backport from mainline
        2009-05-18  Richard Guenther  <rguenther@suse.de>

        PR fortran/40168
        * trans-expr.c (gfc_trans_zero_assign): For local array
        destinations use an assignment from an empty constructor.

        * gfortran.dg/array_memset_2.f90: Adjust.

Modified:
    branches/gcc-4_4-branch/gcc/fortran/ChangeLog
    branches/gcc-4_4-branch/gcc/fortran/trans-expr.c
    branches/gcc-4_4-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_4-branch/gcc/testsuite/gfortran.dg/array_memset_2.f90


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40168

[Bug fortran/40168] missing unrolling/scalarization/reassoc/free

[pault at gcc dot gnu dot org]

------- Comment #19 from pault at gcc dot gnu dot org  2009-12-18 14:32 -------
Can this now be closed or has it transmogrified itself into something else?

Paul


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40168

[Bug tree-optimization/40168] missing unrolling/scalarization/reassoc/free

[rguenth at gcc dot gnu dot org]

------- Comment #20 from rguenth at gcc dot gnu dot org  2009-12-18 14:45 -------
There is still the issue about the 2nd testcase.  It needs to be re-analyzed
and possibly simplified.  But it's now a pure optimization issue, not a
frontend issue anymore.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
          Component|fortran                     |tree-optimization
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2009-12-18 14:45:13
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40168