[Bug rtl-optimization/46556] New: Code size regression in struct access

[Bug rtl-optimization/46556] New: Code size regression in struct access

[amodra at gmail dot com]

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

           Summary: Code size regression in struct access
           Product: gcc
           Version: 4.6.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: amodra@gmail.com


/* -Os -mcpu=405 -msoft-float */
struct x
{
  unsigned int a[16];
  unsigned int b[16];
  unsigned int c[16];
};

void
f (struct x *p, unsigned int n)
{
  extern void foo (int, int, int);
  int a = p->a[n];
  int c = p->c[n];
  int b = p->b[n];

  foo (a, c, b);
}

results in

f:
        stwu 1,-16(1)
        mflr 0
        addi 11,4,32
        stw 0,20(1)
        addi 0,4,16
        mr 9,3
        slwi 10,4,2
        slwi 0,0,2
        slwi 11,11,2
        lwzx 5,9,0
        lwzx 3,3,10
        lwzx 4,9,11
        bl foo
        lwz 0,20(1)
        addi 1,1,16
        mtlr 0
        blr

a four instruction code size regression against gcc-4.2, which produces

f:
        stwu 1,-16(1)
        mflr 0
        slwi 4,4,2
        stw 0,20(1)
        add 9,4,3
        lwz 5,64(9)
        lwzx 3,4,3
        lwz 4,128(9)
        bl foo
        lwz 0,20(1)
        addi 1,1,16
        mtlr 0
        blr

gcc regressed on this testcase at 4.3.0

[Bug rtl-optimization/46556] Code size regression in struct access

[amodra at gmail dot com]

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

--- Comment #1 from Alan Modra <amodra at gmail dot com> 2010-11-21 23:09:13 UTC ---
I believe this code size regression is due to the fix for #32698.  Before that
change, gcc calculated the offset for accessing the array elements as
n*4
64+n*4
128+n*4

After, we get
n*4
(n+16)*4
(n+32)*4

and cse doesn't see the optimization opportunity.

[Bug rtl-optimization/46556] Code size regression in struct access

[rguenth at gcc dot gnu.org]

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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2010.11.22 10:22:43
     Ever Confirmed|0                           |1

--- Comment #2 from Richard Guenther <rguenth at gcc dot gnu.org> 2010-11-22 10:22:43 UTC ---
Well, we obviously can't have it both ways ...

I think RTL fwprop could recognize that propagating (n+CST)*4 isn't resulting
in a valid addressing mode and then rewrite it as n*4 + CST to expose the CSE
opportunity.  Or IVOPTs can be made work on non-loops (I suppose if you
construct an equivalent testcase that has the accesses within a loop it works?)

[Bug rtl-optimization/46556] Code size regression in struct access

[amodra at gmail dot com]

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

Alan Modra <amodra at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |UNCONFIRMED
     Ever Confirmed|1                           |0

--- Comment #3 from Alan Modra <amodra at gmail dot com> 2010-11-22 10:40:01 UTC ---
Yes, within a loop we get the expected addressing.  Updated testcase:

/* -Os -mcpu=405 -msoft-float */
struct x
{
  int a[16];
  int b[16];
  int c[16];
};

extern void foo (int, int, int);

void
f (struct x *p, unsigned int n)
{
  foo (p->a[n], p->c[n], p->b[n]);
}

void
g (struct x *p, unsigned int n)
{
  int i;

  for (i = 0; i < n; i++)
    foo (p->a[i], p->c[i], p->b[i]);
}

[Bug rtl-optimization/46556] Code size regression in struct access

[amodra at gmail dot com]

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

--- Comment #4 from Alan Modra <amodra at gmail dot com> 2010-11-22 10:47:24 UTC ---
But within a loop gcc-4.2 looked quite reasonable too..

Don't we have a pass ordering problem if fwprop is to rewrite addresses?  We
currently have cse1, fwprop1, loop passes, cse2, fwprop2.

[Bug rtl-optimization/46556] Code size regression in struct access

[rguenther at suse dot de]

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

--- Comment #5 from rguenther at suse dot de <rguenther at suse dot de> 2010-11-22 11:15:01 UTC ---
On Mon, 22 Nov 2010, amodra at gmail dot com wrote:

> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=46556
> 
> --- Comment #4 from Alan Modra <amodra at gmail dot com> 2010-11-22 10:47:24 UTC ---
> But within a loop gcc-4.2 looked quite reasonable too..

Of course.

> Don't we have a pass ordering problem if fwprop is to rewrite addresses?  We
> currently have cse1, fwprop1, loop passes, cse2, fwprop2.

Well, fwprop was only a suggestion (I can't think of something better
right now, maybe apart from expand (ugh), or better a pattern recognizer
before expand).

We really can't rely on expression canonicalization fold does for
addressing mode selection.  We have to do this somewhere else
(and IVOPTs does it for code inside loops).

[Bug rtl-optimization/46556] Code size regression in struct access

[steven at gcc dot gnu.org]

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

Steven Bosscher <steven at gcc dot gnu.org> changed:

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

--- Comment #6 from Steven Bosscher <steven at gcc dot gnu.org> 2010-11-22 11:20:20 UTC ---
In my picture of a better GCC, there would be a late GIMPLE pass that does
address mode selection for MEMs also in straight-line code (like IVopts does
for loops). You would end up with only TARGET_MEM_REFs in GIMPLE and expand
would Do The Right Thing (tm) automatically.

[Bug rtl-optimization/46556] Code size regression in struct access

[amodra at gmail dot com]

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

Alan Modra <amodra at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Target|                            |powerpc-linux
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|2010-11-22 10:22:43         |2011.01.19 06:31:18
     Ever Confirmed|0                           |1

[Bug rtl-optimization/46556] Code size regression in struct access

[steven at gcc dot gnu.org]

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

Steven Bosscher <steven at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |patch
                URL|                            |http://gcc.gnu.org/ml/gcc-p
                   |                            |atches/2011-02/msg00301.htm
                   |                            |l

--- Comment #7 from Steven Bosscher <steven at gcc dot gnu.org> 2011-02-07 11:35:52 UTC ---
Link to proposed new patch. Looks like 4.7 material.

[Bug tree-optimization/46556] Code size regression in struct access

[wschmidt at gcc dot gnu.org]

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

William J. Schmidt <wschmidt at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|patch                       |missed-optimization
             Status|NEW                         |ASSIGNED
          Component|rtl-optimization            |tree-optimization
         AssignedTo|unassigned at gcc dot       |wschmidt at gcc dot gnu.org
                   |gnu.org                     |
   Target Milestone|---                         |4.8.0

--- Comment #8 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2012-06-28 16:10:16 UTC ---
This will be handled as part of GIMPLE strength reduction.

[Bug tree-optimization/46556] Code size regression in struct access

[wschmidt at gcc dot gnu.org]

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

--- Comment #9 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2012-08-01 13:02:46 UTC ---
Author: wschmidt
Date: Wed Aug  1 13:02:38 2012
New Revision: 190037

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=190037
Log:
gcc:

    PR tree-optimization/46556
    * gimple-ssa-strength-reduction.c (enum cand_kind): Add CAND_REF.
    (base_cand_map): Change to hash table.
    (base_cand_hash): New function.
    (base_cand_free): Likewise.
    (base_cand_eq): Likewise.
    (lookup_cand): Change base_cand_map to hash table.
    (find_basis_for_candidate): Likewise.
    (base_cand_from_table): Exclude CAND_REF.
    (restructure_reference): New function.
    (slsr_process_ref): Likewise.
    (find_candidates_in_block): Call slsr_process_ref.
    (dump_candidate): Handle CAND_REF.
    (base_cand_dump_callback): New function.
    (dump_cand_chains): Change base_cand_map to hash table.
    (replace_ref): New function.
    (replace_refs): Likewise.
    (analyze_candidates_and_replace): Call replace_refs.
    (execute_strength_reduction): Change base_cand_map to hash table.

gcc/testsuite:

    PR tree-optimization/46556
    * testsuite/gcc.dg/tree-ssa/slsr-27.c: New.
    * testsuite/gcc.dg/tree-ssa/slsr-28.c: New.
    * testsuite/gcc.dg/tree-ssa/slsr-29.c: New.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/slsr-27.c
    trunk/gcc/testsuite/gcc.dg/tree-ssa/slsr-28.c
    trunk/gcc/testsuite/gcc.dg/tree-ssa/slsr-29.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/gimple-ssa-strength-reduction.c
    trunk/gcc/testsuite/ChangeLog

[Bug tree-optimization/46556] Code size regression in struct access

[wschmidt at gcc dot gnu.org]

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

William J. Schmidt <wschmidt at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED

--- Comment #9 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2012-08-01 13:02:46 UTC ---
Author: wschmidt
Date: Wed Aug  1 13:02:38 2012
New Revision: 190037

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=190037
Log:
gcc:

    PR tree-optimization/46556
    * gimple-ssa-strength-reduction.c (enum cand_kind): Add CAND_REF.
    (base_cand_map): Change to hash table.
    (base_cand_hash): New function.
    (base_cand_free): Likewise.
    (base_cand_eq): Likewise.
    (lookup_cand): Change base_cand_map to hash table.
    (find_basis_for_candidate): Likewise.
    (base_cand_from_table): Exclude CAND_REF.
    (restructure_reference): New function.
    (slsr_process_ref): Likewise.
    (find_candidates_in_block): Call slsr_process_ref.
    (dump_candidate): Handle CAND_REF.
    (base_cand_dump_callback): New function.
    (dump_cand_chains): Change base_cand_map to hash table.
    (replace_ref): New function.
    (replace_refs): Likewise.
    (analyze_candidates_and_replace): Call replace_refs.
    (execute_strength_reduction): Change base_cand_map to hash table.

gcc/testsuite:

    PR tree-optimization/46556
    * testsuite/gcc.dg/tree-ssa/slsr-27.c: New.
    * testsuite/gcc.dg/tree-ssa/slsr-28.c: New.
    * testsuite/gcc.dg/tree-ssa/slsr-29.c: New.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/slsr-27.c
    trunk/gcc/testsuite/gcc.dg/tree-ssa/slsr-28.c
    trunk/gcc/testsuite/gcc.dg/tree-ssa/slsr-29.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/gimple-ssa-strength-reduction.c
    trunk/gcc/testsuite/ChangeLog

--- Comment #10 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2012-08-01 13:03:44 UTC ---
Fixed.

[Bug tree-optimization/46556] Code size regression in struct access

[wschmidt at gcc dot gnu.org]

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

William J. Schmidt <wschmidt at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED

--- Comment #10 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2012-08-01 13:03:44 UTC ---
Fixed.

[Bug tree-optimization/46556] Code size regression in struct access

[steven at gcc dot gnu.org]

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

--- Comment #11 from Steven Bosscher <steven at gcc dot gnu.org> 2012-08-01 17:51:55 UTC ---
(In reply to comment #10)
> Fixed.

Is it still your plan to also do something with the patch to expose target
addressing modes earlier?

[Bug tree-optimization/46556] Code size regression in struct access

[wschmidt at gcc dot gnu.org]

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

--- Comment #12 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2012-08-01 18:42:16 UTC ---
(In reply to comment #11)
> (In reply to comment #10)
> > Fixed.
> 
> Is it still your plan to also do something with the patch to expose target
> addressing modes earlier?

No, I'm afraid not.  I spent more time than I like to remember investigating
that possibility.  My conclusion was that we lose too much structural aliasing
information when we lower to MEM_REFs indiscriminately, resulting in
unnecessary instruction scheduling constraints that harm performance.  If this
is to be done at some point in the future, there needs to be more
infrastructure to allow the structural aliasing information to be retained
throughout GIMPLE.