[Bug rtl-optimization/50213] New: Regression in space-optimized code relative to 4.5.x

[Bug rtl-optimization/50213] New: Regression in space-optimized code relative to 4.5.x

[bigotp at acm dot org]

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

             Bug #: 50213
           Summary: Regression in space-optimized code relative to 4.5.x
    Classification: Unclassified
           Product: gcc
           Version: 4.7.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: bigotp@acm.org


Some change between 4.5.x and 4.6.x decreased generated code quality,
especially noticeable with -Os, for the following function:

int checkTLV (unsigned char* tlv)
{
  unsigned int csum;
  extern unsigned int __info_segment_size;
  const unsigned int* p = (const unsigned int*)(tlv + __info_segment_size);

  csum = 0;
  while (--p > (const unsigned int*)tlv)
    csum ^= *p;
  csum += *p;
  return 0 == csum;
}

In 4.5.2 -Os, the loop has an 11 byte body:

  11 000c EB02                  jmp     .L2     # 52    jump    [length = 2]
  12                    .L3:
  13 000e 3310                  xorl    (%rax), %edx    # 15    *xorsi_1/1     
[length = 2]
  14                    .L2:
  15 0010 4883E804              subq    $4, %rax        # 18    *adddi_1/1     
[length = 4]
  16 0014 4839F8                cmpq    %rdi, %rax      # 20    *cmpdi_1/1     
[length = 3]
  17 0017 77F5                  ja      .L3     # 21    *jcc_1  [length = 2]

while in 4.6.1 -Os the loop has a 15 byte body:

  11 000b EB06                  jmp     .L2     # 66    jump    [length = 2]
  12                    .L3:
  13 000d 3350FC                xorl    -4(%rax), %edx  # 29    *xorsi_1/1     
[length = 3]
  14 0010 4889C8                movq    %rcx, %rax      # 21   
*movdi_internal_rex64/2 [length = 3]
  15                    .L2:
  16 0013 488D48FC              leaq    -4(%rax), %rcx  # 57    *lea_1  [length
= 4]
  17 0017 4839F9                cmpq    %rdi, %rcx      # 34    *cmpdi_1/1     
[length = 3]
  18 001a 77F1                  ja      .L3     # 35    *jcc_1  [length = 2]

My hypothesis is that the label L2 is preventing the pseudo registers for the
loop variable and the memory access from being merged into the same hardware
register.  This is not specific to the x86 back-end: I noticed it in an
unsupported back-end, where the suboptimal register allocation causes a spill.

The current trunk (svn 178132) generates the same suboptimal code as 4.6.1.

[Bug rtl-optimization/50213] [4.6/4.7 Regression] Regression in space-optimized code relative to 4.5.x

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
             Target|                            |x86_64-*-*
   Target Milestone|---                         |4.6.2
            Summary|Regression in               |[4.6/4.7 Regression]
                   |space-optimized code        |Regression in
                   |relative to 4.5.x           |space-optimized code
                   |                            |relative to 4.5.x

[Bug rtl-optimization/50213] [4.6/4.7 Regression] Regression in space-optimized code relative to 4.5.x

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

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

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-09-06 15:45:10 UTC ---
This regressed with http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=161655
and with -Os -fno-tree-forwprop you get the same code as you used to get
before.
At the tree level, the difference seems to be in
 <bb 3>:
-  D.2724_9 = *p_8;
+  D.2724_9 = MEM[(const unsigned int *)p_2 + -4B];
   csum_10 = csum_1 ^ D.2724_9;

 <bb 4>:
   # csum_1 = PHI <0(2), csum_10(3)>
   # p_2 = PHI <p_6(2), p_8(3)>
   p_8 = p_2 + -4;
   if (p_8 > tlv_5(D))
     goto <bb 3>;
   else
     goto <bb 5>;

 <bb 5>:
-  D.2724_11 = *p_8;
+  D.2724_11 = MEM[(const unsigned int *)p_2 + -4B];

being now done in forwprop while it wasn't possible before MEM_REF - it wasn't
valid GIMPLE.
While in the loop IVOPTs undoes the undesirable transformation back to
MEM[base: p_8], in bb5 as it is not a loop we keep the longer form and thus use
a var from the middle of the loop instead of p after the loop.  That results in
different expansion.

[Bug tree-optimization/50213] [4.6/4.7 Regression] Regression in space-optimized code relative to 4.5.x

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2011-09-06
          Component|rtl-optimization            |tree-optimization
         AssignedTo|unassigned at gcc dot       |rguenth at gcc dot gnu.org
                   |gnu.org                     |
     Ever Confirmed|0                           |1

--- Comment #2 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-09-06 15:51:29 UTC ---
Mine.

[Bug tree-optimization/50213] [4.6/4.7 Regression] Regression in space-optimized code relative to 4.5.x

[jakub at gcc dot gnu.org]

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

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-09-06 17:08:57 UTC ---
It seems that in the loop it is changed then again by RTL fwprop2.  Why it
isn't done by fwprop2 with -fno-tree-forwprop is a question...

[Bug tree-optimization/50213] [4.6/4.7 Regression] Regression in space-optimized code relative to 4.5.x

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-09-07 08:59:01 UTC ---
With

Index: gcc/tree-ssa-forwprop.c
===================================================================
--- gcc/tree-ssa-forwprop.c     (revision 178628)
+++ gcc/tree-ssa-forwprop.c     (working copy)
@@ -34,6 +34,7 @@ along with GCC; see the file COPYING3.
 #include "flags.h"
 #include "gimple.h"
 #include "expr.h"
+#include "cfgloop.h"

 /* This pass propagates the RHS of assignment statements into use
    sites of the LHS of the assignment.  It's basically a specialized
@@ -1069,10 +1070,11 @@ forward_propagate_addr_expr (tree name,
          continue;
        }

-      /* If the use is in a deeper loop nest, then we do not want
-        to propagate non-invariant ADDR_EXPRs into the loop as that
-        is likely adding expression evaluations into the loop.  */
-      if (gimple_bb (use_stmt)->loop_depth > stmt_loop_depth
+      /* If the use is in a different loop nest, then we do not want
+        to propagate non-invariant ADDR_EXPRs into or out of the loop
+        as that is likely adding expression evaluations into the loop
+        or extends register lifetimes across loop boundaries.  */
+      if (gimple_bb (use_stmt)->loop_depth != stmt_loop_depth
          && !is_gimple_min_invariant (rhs))
        {
          all = false;
@@ -2322,6 +2324,13 @@ ssa_forward_propagate_and_combine (void)
 {
   basic_block bb;
   unsigned int todoflags = 0;
+  bool cleanup_loops = false;
+
+  if (!current_loops)
+    {
+      loop_optimizer_init (LOOPS_NORMAL);
+      cleanup_loops = true;
+    }

   cfg_changed = false;

@@ -2517,6 +2526,9 @@ ssa_forward_propagate_and_combine (void)
        }
     }

+  if (cleanup_loops)
+    loop_optimizer_finalize ();
+
   if (cfg_changed)
     todoflags |= TODO_cleanup_cfg;


This is fixed.  Of course computing loops all over the place is ... not
the cheapest thing.

I'll see if we can easily avoid some of them.

[Bug tree-optimization/50213] [4.6/4.7 Regression] Regression in space-optimized code relative to 4.5.x

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-09-07 09:08:16 UTC ---
It will of course no longer combine offsets that way, like for

  p_2 = p_1 + 4;

  loop
    p_4 = MEM[p_2 - 4];

so it's clearly not a win-win situation to base the decision on loop
depth.

[Bug tree-optimization/50213] [4.6/4.7 Regression] Regression in space-optimized code relative to 4.5.x

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-09-07 09:31:02 UTC ---
Other simple heuristic would be to not propagate the IV increment (see what
DOM does in simple_iv_increment_p).  I'm going to test a patch like that.

[Bug tree-optimization/50213] [4.6/4.7 Regression] Regression in space-optimized code relative to 4.5.x

[rguenth at gcc dot gnu.org]

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

--- Comment #7 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-09-07 11:28:43 UTC ---
Author: rguenth
Date: Wed Sep  7 11:28:39 2011
New Revision: 178633

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=178633
Log:
2011-09-07  Richard Guenther  <rguenther@suse.de>

    PR tree-optimization/50213
    * tree-flow.h (simple_iv_increment_p): Declare.
    * tree-ssa-dom.c (simple_iv_increment_p): Export.  Also handle
    POINTER_PLUS_EXPR.
    * tree-ssa-forwprop.c (ssa_forward_propagate_and_combine): Do
    not propagate simple IV counter increments.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-flow.h
    trunk/gcc/tree-ssa-dom.c
    trunk/gcc/tree-ssa-forwprop.c

[Bug tree-optimization/50213] [4.6 Regression] Regression in space-optimized code relative to 4.5.x

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |4.7.0
            Summary|[4.6/4.7 Regression]        |[4.6 Regression] Regression
                   |Regression in               |in space-optimized code
                   |space-optimized code        |relative to 4.5.x
                   |relative to 4.5.x           |

--- Comment #8 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-09-07 11:50:26 UTC ---
Fixed on trunk sofar.

[Bug tree-optimization/50213] [4.6 Regression] Regression in space-optimized code relative to 4.5.x

[propolice at gmail dot com]

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

Eduardo Tongson <propolice at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |propolice at gmail dot com

--- Comment #9 from Eduardo Tongson <propolice at gmail dot com> 2011-10-17 06:47:31 UTC ---
Seems trivial to backport to 4.6.1 (at least) or it is not?

[Bug tree-optimization/50213] [4.6 Regression] Regression in space-optimized code relative to 4.5.x

[rguenther at suse dot de]

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

--- Comment #10 from rguenther at suse dot de <rguenther at suse dot de> 2011-10-17 09:33:49 UTC ---
On Mon, 17 Oct 2011, propolice at gmail dot com wrote:

> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50213
> 
> Eduardo Tongson <propolice at gmail dot com> changed:
> 
>            What    |Removed                     |Added
> ----------------------------------------------------------------------------
>                  CC|                            |propolice at gmail dot com
> 
> --- Comment #9 from Eduardo Tongson <propolice at gmail dot com> 2011-10-17 06:47:31 UTC ---
> Seems trivial to backport to 4.6.1 (at least) or it is not?

We don't backport this kind of patches generally, they may expose
more serious bugs on release branches.

[Bug tree-optimization/50213] [4.6 Regression] Regression in space-optimized code relative to 4.5.x

[bigotp at acm dot org]

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

--- Comment #11 from Peter A. Bigot <bigotp at acm dot org> 2011-10-17 11:16:16 UTC ---
Richard: Thanks for the fix.

For my non-integrated target I don't need it backported to 4.6 since I have a
separate way to provide the patch.  As I recall, the original patch didn't
apply to 4.6 cleanly due to subsequent changes to tree-ssa-forwprop.c; a patch
at the fork of gcc-4_6-branch from trunk is available at:

http://mspgcc.git.sourceforge.net/git/gitweb.cgi?p=mspgcc/gcc;a=commit;h=21a41ea517c2e60d3a910aca8012a2c0d57b1005

[Bug tree-optimization/50213] [4.6 Regression] Regression in space-optimized code relative to 4.5.x

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.6.2                       |4.6.3

--- Comment #12 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-10-26 17:13:59 UTC ---
GCC 4.6.2 is being released.

[Bug tree-optimization/50213] [4.6 Regression] Regression in space-optimized code relative to 4.5.x

[pinskia at gcc dot gnu.org]

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

--- Comment #13 from Andrew Pinski <pinskia at gcc dot gnu.org> 2011-11-11 00:47:50 UTC ---
(In reply to comment #10)
> We don't backport this kind of patches generally, they may expose
> more serious bugs on release branches.

I do get one failure with this patch applied in pr48335-2.c .

[Bug tree-optimization/50213] [4.6 Regression] Regression in space-optimized code relative to 4.5.x

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.6.3                       |4.6.4

--- Comment #14 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-03-01 14:39:19 UTC ---
GCC 4.6.3 is being released.

[Bug tree-optimization/50213] [4.6 Regression] Regression in space-optimized code relative to 4.5.x

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

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

--- Comment #15 from Jakub Jelinek <jakub at gcc dot gnu.org> 2013-04-12 16:18:01 UTC ---
The 4.6 branch has been closed, fixed in GCC 4.7.0.