[Bug c/37221] New: GCC for Cell SPU produces poor code when there is load-after-store in different loops

[Bug c/37221] New: GCC for Cell SPU produces poor code when there is load-after-store in different loops

[tehila at il dot ibm dot com]

I have the following testcase:
#include <math.h>

#define N 256
#define M 256

double mat1[N][3];
int mat2[M][4];

double point = 0;
int tmp;

double
foo ()
{
  int i, j, k, l, ntimes;
  int arr[4];

  for (ntimes = 0; ntimes < 50000000; ntimes++)
    {
      for (i = 0; i < M; i++)
        {
          for (j = 0; j < 4; j++)
            arr[j] = mat2[i][j];
          if (arr[0] == tmp || arr[1] == tmp ||
              arr[2] == tmp || arr[3] == tmp)
            {
              for (j = 0; j < 4; j++)
                for (k = 0; k < 3; k++)
                  point += (double) mat1[arr[j]][k];
            }
        }
    }

}


void
init ()
{
  int i, j;
  for (i = 0; i < N; i++)
    {
      mat1[i][0] = (double) i;
      mat1[i][1] = (double) i + 1;
      mat1[i][2] = (double) i + 2;
    }

  for (i = 0; i < M; i++)
    {
      mat2[j][0] = 0;
      mat2[j][1] = 0;
      mat2[j][2] = 0;
      mat2[j][3] = 0;
    }
  tmp = 33;
}

int
main ()
{
  init ();
  foo ();
}

Is there an option that GCC will recognize the load-after-store of 
arr[0], arr[1], arr[2] and arr[3] (after unrolling) and will replace them all
with registers? Is there a flag doing that?

Doing such transformation will improve the testcase by 40%.

I've tried that on GCC4.4.0, r139150, with -O3 (-funroll-loops -fgcse-las makes
it worse).


-- 
           Summary: GCC for Cell SPU produces poor code when there is load-
                    after-store in different loops
           Product: gcc
           Version: 4.4.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: tehila at il dot ibm dot com
GCC target triplet: Cell SPU


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

[Bug middle-end/37221] GCC for Cell SPU produces poor code when there is load-after-store in different loops

[pinskia at gcc dot gnu dot org]

------- Comment #1 from pinskia at gcc dot gnu dot org  2008-08-24 22:04 -------
There are a couple of issues here I think.  The first being that the loop:

          for (j = 0; j < 4; j++)
            arr[j] = mat2[i][j];

is not being unrolled.

If I specify -fpeel-loops, it is unrolled but then we don't SRA arr at all as
we unroll too late.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement
             Status|UNCONFIRMED                 |NEW
          Component|c                           |middle-end
     Ever Confirmed|0                           |1
           Keywords|                            |missed-optimization
   Last reconfirmed|0000-00-00 00:00:00         |2008-08-24 22:04:27
               date|                            |


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

[Bug middle-end/37221] GCC for Cell SPU produces poor code when there is load-after-store in different loops

[tehila at il dot ibm dot com]

------- Comment #2 from tehila at il dot ibm dot com  2008-08-25 08:18 -------
Andrew, thanks for your response and ideas.

>From what we see, if -funroll-loops is on, the loops:
for (j = 0; j < 4; j++)
            arr[j] = mat2[i][j];
 and 

for (k = 0; k < 3; k++)
                  point += (double) mat1[arr[l]][k];

are being unrolled by the early-unrolling (cunrolli pass, that Richard Guenther
has added).
I think, the problem is that the loop

for (j = 0; j < 4; j++)

is not being unrolled.
cunrolli doesn't recognize # of iterations = 4.
I think it doesn't recognize it starts from 0.
Maybe Richard could help us understand why. 

Hopefully, if that loop would be unrolled, the SRA will have the opportunity to
do the transformation we expect it to do.


-- 

tehila at il dot ibm dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |richard dot guenther at
                   |                            |gmail dot com


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

[Bug middle-end/37221] GCC for Cell SPU produces poor code when there is load-after-store in different loops

[tehila at il dot ibm dot com]

------- Comment #3 from tehila at il dot ibm dot com  2008-08-25 08:45 -------
(In reply to comment #2)
> Andrew, thanks for your response and ideas.
> From what we see, if -funroll-loops is on, the loops:
> for (j = 0; j < 4; j++)
>             arr[j] = mat2[i][j];
>  and 
> for (k = 0; k < 3; k++)
>                   point += (double) mat1[arr[l]][k];
> are being unrolled by the early-unrolling (cunrolli pass, that Richard Guenther
> has added).
> I think, the problem is that the loop
> for (j = 0; j < 4; j++)
> is not being unrolled.

The meaning here is to the second 
for (j = 0; j < 4; j++)
loop. 
It's loop #4 in cunrolli pass.

> cunrolli doesn't recognize # of iterations = 4.
> I think it doesn't recognize it starts from 0.
> Maybe Richard could help us understand why. 
> Hopefully, if that loop would be unrolled, the SRA will have the opportunity to
> do the transformation we expect it to do.


-- 


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

[Bug middle-end/37221] GCC for Cell SPU produces poor code when there is load-after-store in different loops

[tehila at il dot ibm dot com]

------- Comment #4 from tehila at il dot ibm dot com  2008-08-25 14:52 -------
(In reply to comment #2)

> Hopefully, if that loop would be unrolled, the SRA will have the opportunity 
> to do the transformation we expect it to do.

I've tried it manually, and that indeed works.
i.e., if we'll be able to unroll the loop we currently don't, the SRA will do
the work.


-- 


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

[Bug middle-end/37221] GCC for Cell SPU produces poor code when there is load-after-store in different loops

[tehila at il dot ibm dot com]

------- Comment #5 from tehila at il dot ibm dot com  2008-08-26 20:47 -------
(In reply to comment #3)
> The meaning here is to the second 
> for (j = 0; j < 4; j++)
> loop. 
> It's loop #4 in cunrolli pass.
> > cunrolli doesn't recognize # of iterations = 4.
> > I think it doesn't recognize it starts from 0.

We think the problem is that j=0 are somewhere before got hoisted into some
part above.
If I add 'printf' before the loop (i.e., after the if) the loop does get
unrolled and with SRA optimization the performance get improved.


-- 


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

[Bug middle-end/37221] Missed early loop-unroll optimization - causes 40% degradation on SPU

[rguenth at gcc dot gnu dot org]

------- Comment #6 from rguenth at gcc dot gnu dot org  2008-09-02 09:04 -------
It looks like SCEV does not see that for

(number_of_iterations_in_loop
(analyze_scalar_evolution
  (loop_nb = 4)
  (scalar = j_3)
(get_scalar_evolution
  (scalar = j_3)
  (scalar_evolution = ))
(analyze_initial_condition
  (loop_phi_node =
j_3 = PHI <j_26(4), j_31(7)>
)
  (init_cond = j_26))
(analyze_evolution_in_loop
  (loop_phi_node = j_3 = PHI <j_26(4), j_31(7)>
)
(add_to_evolution
  (loop_nb = 4)
  (chrec_before = j_26)
  (to_add = 1)
  (res = {j_26, +, 1}_4))
  (evolution_function = {j_26, +, 1}_4))
(set_scalar_evolution
  (scalar = j_3)
  (scalar_evolution = {j_26, +, 1}_4))
)

j_26 is defined by

<bb 4>:
  # j_26 = PHI <0(3), 0(5), 0(12), 0(6)>

so it is all zeros.  This is because the "iterative" unrolling only does
a cfg cleanup between iterations and not a full constant-prop.

We can "fix" this special case in analyze_initial_condition, but a real
fix would be to run a (partial) CCP pass after each set of unrolling.


-- 


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

[Bug middle-end/37221] Missed early loop-unroll optimization - causes 40% degradation on SPU

[rguenth at gcc dot gnu dot org]

------- Comment #7 from rguenth at gcc dot gnu dot org  2008-09-02 09:09 -------
Created an attachment (id=16188)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16188&action=view)
patch

Like with this patch.


-- 


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

[Bug middle-end/37221] Missed early loop-unroll optimization - causes 40% degradation on SPU

[tehila at il dot ibm dot com]

------- Comment #8 from tehila at il dot ibm dot com  2008-09-02 12:47 -------
Thank you, Richard!

This patch indeed does the work and unrolls the loop.
The SRA works fine and we get 40% improvement.


-- 


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

[Bug middle-end/37221] Missed early loop-unroll optimization - causes 40% degradation on SPU

[rguenther at suse dot de]

------- Comment #9 from rguenther at suse dot de  2008-09-02 13:10 -------
Subject: Re:  Missed early loop-unroll optimization -
 causes 40% degradation on SPU

On Tue, 2 Sep 2008, tehila at il dot ibm dot com wrote:

> ------- Comment #8 from tehila at il dot ibm dot com  2008-09-02 12:47 -------
> Thank you, Richard!
> 
> This patch indeed does the work and unrolls the loop.
> The SRA works fine and we get 40% improvement.

If you give the patch bootstrap & testing I'll approve it for trunk.

Richard.


-- 


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

[Bug middle-end/37221] Missed early loop-unroll optimization - causes 40% degradation on SPU

[tehila at il dot ibm dot com]

------- Comment #10 from tehila at il dot ibm dot com  2008-09-03 06:58 -------
(In reply to comment #9)
> If you give the patch bootstrap & testing I'll approve it for trunk.
> Richard.

Great.
I'm bootstraping and testing it on x86 now.


-- 


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

[Bug middle-end/37221] Missed early loop-unroll optimization - causes 40% degradation on SPU

[tehila at il dot ibm dot com]

------- Comment #11 from tehila at il dot ibm dot com  2008-09-04 19:46 -------
(In reply to comment #10)
> I'm bootstraping and testing it on x86 now.
Bootstrap fails (at least on x86_64) (with ICE).

Tehila.


-- 


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

[Bug middle-end/37221] Missed early loop-unroll optimization - causes 40% degradation on SPU

[tehila at il dot ibm dot com]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 2681 bytes --]



------- Comment #12 from tehila at il dot ibm dot com  2008-09-08 08:21 -------
(In reply to comment #11)
> (In reply to comment #10)
> > I'm bootstraping and testing it on x86 now.
> Bootstrap fails (at least on x86_64) (with ICE).
> Tehila.

It fails at tree-ssa-loop-manip.c:424 (+-, I've changed it a little bit), on:
gcc_assert (!def_bb
              || flow_bb_inside_loop_p (def_bb->loop_father, bb));

Error:
In file included from ../../gcc/libiberty/regex.c:638:
../../gcc/libiberty/regex.c: In function ⁁byte_regex_compile⁁:
../../gcc/libiberty/regex.c:2285: internal compiler error: in
check_loop_closed_ssa_use, at tree-ssa-loop-manip.c:424


Here is some info GDB gives:
#0  check_loop_closed_ssa_use (bb=0x2b9638623f00, use=0x2b963870c460) at
../../gcc/gcc/tree-ssa-loop-manip.c:422
#1  0x00000000009cffdc in check_loop_closed_ssa_stmt (bb=0x2b9638623f00,
stmt=0x2b963822b150) at ../../gcc/gcc/tree-ssa-loop-manip.c:436
#2  0x00000000009d0179 in verify_loop_closed_ssa () at
../../gcc/gcc/tree-ssa-loop-manip.c:466
#3  0x00000000007a14bf in execute_function_todo (data=0x63) at
../../gcc/gcc/passes.c:1004
#4  0x00000000007a0f2e in do_per_function (callback=0x7a11cb
<execute_function_todo>, data=0x63) at ../../gcc/gcc/passes.c:840
#5  0x00000000007a1541 in execute_todo (flags=99) at
../../gcc/gcc/passes.c:1024
#6  0x00000000007a1fc5 in execute_one_pass (pass=0x13494c0) at
../../gcc/gcc/passes.c:1300
#7  0x00000000007a214d in execute_pass_list (pass=0x13494c0) at
../../gcc/gcc/passes.c:1326
#8  0x00000000007a216b in execute_pass_list (pass=0x13490a0) at
../../gcc/gcc/passes.c:1327
#9  0x00000000007a216b in execute_pass_list (pass=0x1348560) at
../../gcc/gcc/passes.c:1327
#10 0x00000000009140c6 in tree_rest_of_compilation (fndecl=0x2b9638292900) at
../../gcc/gcc/tree-optimize.c:418
#11 0x0000000000b49808 in cgraph_expand_function (node=0x2b96382b3f00) at
../../gcc/gcc/cgraphunit.c:1039
#12 0x0000000000b499a2 in cgraph_expand_all_functions () at
../../gcc/gcc/cgraphunit.c:1101
#13 0x0000000000b49f43 in cgraph_optimize () at ../../gcc/gcc/cgraphunit.c:1306
#14 0x000000000042f789 in c_write_global_declarations () at
../../gcc/gcc/c-decl.c:8080
#15 0x000000000089c5a9 in compile_file () at ../../gcc/gcc/toplev.c:979
#16 0x000000000089e3f6 in do_compile () at ../../gcc/gcc/toplev.c:2181
#17 0x000000000089e45a in toplev_main (argc=30, argv=0x7fff730801f8) at
../../gcc/gcc/toplev.c:2213
#18 0x00000000004d3bb7 in main (argc=30, argv=0x7fff730801f8) at
../../gcc/gcc/main.c:35

stmt is:
D.9310_4596 = b_3442 + -1;

def stmt is:
b_3442 = PHI <b_2310(130), b_620(141)>


HTH,
Tehila.


-- 


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

[Bug middle-end/37221] Missed early loop-unroll optimization - causes 40% degradation on SPU

[rguenth at gcc dot gnu dot org]

-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |rguenth at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2008-08-24 22:04:27         |2008-09-30 10:37:35
               date|                            |


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

[Bug middle-end/37221] Missed early loop-unroll optimization - causes 40% degradation on SPU

[rguenth at gcc dot gnu dot org]

------- Comment #13 from rguenth at gcc dot gnu dot org  2009-03-31 11:31 -------
Reduced testcase:

struct re_pattern_buffer {
    unsigned char *buffer;
    unsigned long int allocated;
};
void byte_regex_compile (struct re_pattern_buffer *bufp, 
                         unsigned char *begalt, unsigned char *b)
{
  unsigned char *pfrom;
  unsigned char *pto;

  while ((unsigned long) (b - bufp->buffer + 3) > bufp->allocated)       
    { 
      unsigned char *old_buffer = bufp->buffer; 
      bufp->allocated <<= 1; 
      if (old_buffer != bufp->buffer) 
        {
          int incr = bufp->buffer - old_buffer;
          b += incr;  
        }
    }
  pfrom = b;
  pto = b + 3;
  while (pfrom != begalt)
    *--pto = *--pfrom;
}

./cc1 -quiet -O2 regex.3.3.i -Wall
regex.3.3.i: In function 'byte_regex_compile':
regex.3.3.i:5: internal compiler error: in check_loop_closed_ssa_use, at
tree-ssa-loop-manip.c:420
Please submit a full bug report,
with preprocessed source if appropriate.
See <http://gcc.gnu.org/bugs.html> for instructions.


-- 


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

[Bug middle-end/37221] Missed early loop-unroll optimization - causes 40% degradation on SPU

[rguenth at gcc dot gnu dot org]

------- Comment #14 from rguenth at gcc dot gnu dot org  2009-03-31 11:42 -------
I have a fix (I think).


-- 


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

[Bug middle-end/37221] Missed early loop-unroll optimization - causes 40% degradation on SPU

[rguenth at gcc dot gnu dot org]

------- Comment #15 from rguenth at gcc dot gnu dot org  2009-04-02 09:11 -------
Fixed.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.5.0


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

[Bug middle-end/37221] Missed early loop-unroll optimization - causes 40% degradation on SPU

[rguenth at gcc dot gnu dot org]

------- Comment #16 from rguenth at gcc dot gnu dot org  2009-04-02 09:11 -------
Subject: Bug 37221

Author: rguenth
Date: Thu Apr  2 09:10:53 2009
New Revision: 145439

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

        PR tree-optimization/37221
        * tree-flow.h (degenerate_phi_result): Declare.
        * tree-ssa-dom.c (degenerate_phi_result): Export.
        * tree-scalar-evolution.c (analyze_initial_condition): If
        the initial condition is defined by a degenerate PHI node
        use the degenerate value.

        * gcc.c-torture/compile/20090331-1.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.c-torture/compile/20090331-1.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-flow.h
    trunk/gcc/tree-scalar-evolution.c
    trunk/gcc/tree-ssa-dom.c


-- 


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

[Bug middle-end/37221] Missed early loop-unroll optimization - causes 40% degradation on SPU

[tkoenig at gcc dot gnu.org]

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

Thomas Koenig <tkoenig at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |tkoenig at gcc dot gnu.org

--- Comment #18 from Thomas Koenig <tkoenig at gcc dot gnu.org> 2011-08-05 23:18:21 UTC ---
(In reply to comment #17)
> Author: tkoenig
> Date: Fri Aug  5 21:51:59 2011
> New Revision: 177486
> 
> URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=177486

That was a typo in the PR number.

[Bug middle-end/37221] Missed early loop-unroll optimization - causes 40% degradation on SPU

[tkoenig at gcc dot gnu.org]

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

--- Comment #17 from Thomas Koenig <tkoenig at gcc dot gnu.org> 2011-08-05 21:52:03 UTC ---
Author: tkoenig
Date: Fri Aug  5 21:51:59 2011
New Revision: 177486

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=177486
Log:
2011-08-05  Thomas Koenig  <tkoenig@gcc.gnu.org>

    PR fortran/37221
    * gfortran.h (gfc_calculate_transfer_sizes):  Add prototype.
    * target-memory.h (gfc_target_interpret_expr):  Add boolean
    argument wether to convert wide characters.
    * target-memory.c (gfc_target_expr_size):  Also return length
    of characters for non-constant expressions if these can be
    determined from the cl.
    (interpret_array):  Add argument for gfc_target_interpret_expr.
    (gfc_interpret_derived):  Likewise.
    (gfc_target_interpret_expr):  Likewise.
    * check.c:  Include target-memory.h.
    (gfc_calculate_transfer_sizes):  New function.
    (gfc_check_transfer):  When -Wsurprising is in force, calculate
    sizes and warn if result is larger than size (check moved from
    gfc_simplify_transfer).
    * simplify.c (gfc_simplify_transfer):  Use
    gfc_calculate_transfer_sizes.  Remove warning.

2011-08-05  Thomas Koenig  <tkoenig@gcc.gnu.org>

    PR fortran/37221
    * gfortran.dg/transfer_check_2.f90:  New test case.


Added:
    trunk/gcc/testsuite/gfortran.dg/transfer_check_2.f90
Modified:
    trunk/gcc/fortran/ChangeLog
    trunk/gcc/fortran/check.c
    trunk/gcc/fortran/gfortran.h
    trunk/gcc/fortran/simplify.c
    trunk/gcc/fortran/target-memory.c
    trunk/gcc/fortran/target-memory.h
    trunk/gcc/testsuite/ChangeLog