[Bug c/18219] New: gcc-4.0.0 bloats code by 31%

[Bug c/18219] New: gcc-4.0.0 bloats code by 31%

[miguel55angel at hotmail dot com]

Hi,
this little function shows an increase in codesize by 31% or 13 byte.
   
void cdt (int *limit, int *base, int minLen, int maxLen)
{
   int i;
   
   for (i = minLen + 1; i <= maxLen; i++)
      base[i] = ((limit[i-1] + 1) << 1) - base[i];
}
   
   
Size  Version Flags
  41  3.4.2   -Os
  54  4.0.0   -Os -fno-ivopts
  63  4.0.0   -Os

3.4.2 disassembly code
00000000 <cdt>:
   0:   55                      push   %ebp
   1:   89 e5                   mov    %esp,%ebp
   3:   8b 4d 14                mov    0x14(%ebp),%ecx
   6:   56                      push   %esi
   7:   8b 55 10                mov    0x10(%ebp),%edx  
   a:   8b 75 08                mov    0x8(%ebp),%esi
   d:   53                      push   %ebx
   e:   8b 5d 0c                mov    0xc(%ebp),%ebx
  11:   42                      inc    %edx
  12:   39 ca                   cmp    %ecx,%edx  
  14:   7f 0f                   jg     25 <cdt+0x25>
  16:   8b 44 96 fc             mov    0xfffffffc(%esi,%edx,4),%eax
  1a:   40                      inc    %eax
  1b:   01 c0                   add    %eax,%eax
  1d:   2b 04 93                sub    (%ebx,%edx,4),%eax
  20:   89 04 93                mov    %eax,(%ebx,%edx,4)
  23:   eb ec                   jmp    11 <cdt+0x11>
  25:   5b                      pop    %ebx
  26:   5e                      pop    %esi
  27:   5d                      pop    %ebp
  28:   c3                      ret


4.0.0-20041028 disassembly code
00000000 <cdt>:
   0:   55                      push   %ebp
   1:   89 e5                   mov    %esp,%ebp
   3:   8b 4d 10                mov    0x10(%ebp),%ecx
   6:   57                      push   %edi
   7:   8b 7d 08                mov    0x8(%ebp),%edi
   a:   56                      push   %esi
   b:   8b 75 14                mov    0x14(%ebp),%esi
   e:   53                      push   %ebx
   f:   8b 5d 0c                mov    0xc(%ebp),%ebx
  12:   41                      inc    %ecx
  13:   8d 14 8d 00 00 00 00    lea    0x0(,%ecx,4),%edx
  1a:   eb 11                   jmp    2d <cdt+0x2d>
  1c:   8b 44 3a fc             mov    0xfffffffc(%edx,%edi,1),%eax
  20:   41                      inc    %ecx
  21:   40                      inc    %eax
  22:   01 c0                   add    %eax,%eax
  24:   2b 04 1a                sub    (%edx,%ebx,1),%eax
  27:   89 04 1a                mov    %eax,(%edx,%ebx,1)
  2a:   83 c2 04                add    $0x4,%edx
  2d:   39 f1                   cmp    %esi,%ecx
  2f:   7e eb                   jle    1c <cdt+0x1c>
  31:   5b                      pop    %ebx
  32:   5e                      pop    %esi
  33:   5f                      pop    %edi
  34:   5d                      pop    %ebp
  35:   c3                      ret
  
This PR may be related to PR17549, but it's much smaller and
hopefully easier to analyse!

-- 
           Summary: gcc-4.0.0 bloats code by 31%
           Product: gcc
           Version: 4.0.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: c
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: miguel55angel at hotmail dot com
                CC: gcc-bugs at gcc dot gnu dot org
  GCC host triplet: i386-linux


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

[Bug tree-optimization/18219] [4.0 Regression] gcc-4.0.0 bloats code by 31%

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
OtherBugsDependingO|                            |17549
              nThis|                            |
          Component|c                           |tree-optimization
           Keywords|                            |missed-optimization
            Summary|gcc-4.0.0 bloats code by 31%|[4.0 Regression] gcc-4.0.0
                   |                            |bloats code by 31%
   Target Milestone|---                         |4.0.0


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

[Bug tree-optimization/18219] [4.0 Regression] gcc-4.0.0 bloats code by 31%

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-10-29 14:30 -------
Confirmed, on PPC, IV-OPTS causes a code bloat also, 7 new instructions but note 4.0.0 with IV-OPTS 
on PPC is only one instruction more than 3.3. (on PPC every instruction is the same length).

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2004-10-29 14:30:12
               date|                            |


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

[Bug tree-optimization/18219] [4.0 Regression] gcc-4.0.0 bloats code by 31%

[giovannibajo at libero dot it]

------- Additional Comments From giovannibajo at libero dot it  2004-10-29 15:43 -------
Zdenek, this is another PR about ivopts and -Os. The test case is very very 
simple, so if you could give a look it would be great.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rakdver at gcc dot gnu dot
                   |                            |org, giovannibajo at libero
                   |                            |dot it


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

[Bug tree-optimization/18219] [4.0 Regression] gcc-4.0.0 bloats code by 31%

[rakdver at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |rakdver at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED


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

[Bug tree-optimization/18219] [4.0 Regression] gcc-4.0.0 bloats code by 31%

[rakdver at gcc dot gnu dot org]

------- Additional Comments From rakdver at gcc dot gnu dot org  2004-11-01 13:21 -------
Unfortunately I do not think this will help much in other related PRs.

Patch:

http://gcc.gnu.org/ml/gcc-patches/2004-11/msg00025.html

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |patch


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

[Bug tree-optimization/18219] [4.0 Regression] gcc-4.0.0 bloats code by 31%

[giovannibajo at libero dot it]

------- Additional Comments From giovannibajo at libero dot it  2004-11-01 14:40 -------
Zdenek, thanks for the patch!
What is the generated code like after your patch?

-- 


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

[Bug tree-optimization/18219] [4.0 Regression] gcc-4.0.0 bloats code by 31%

[rakdver at atrey dot karlin dot mff dot cuni dot cz]

------- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni dot cz  2004-11-01 14:57 -------
Subject: Re:  [4.0 Regression] gcc-4.0.0 bloats code by 31%

> Zdenek, thanks for the patch!
> What is the generated code like after your patch?

It seems that the 3.4 code is still smaller (I haven't measured it, just
guessing from looking at your disassembly), but -fno-ivopts no longer
changes it.

        pushl   %ebp
        movl    %esp, %ebp
        pushl   %edi
        pushl   %esi
        pushl   %ebx
        movl    8(%ebp), %edi
        movl    20(%ebp), %esi
        movl    16(%ebp), %ebx
        incl    %ebx
        movl    %ebx, %ecx
        leal    0(,%ebx,4), %edx
        addl    12(%ebp), %edx
        jmp     .L2
.L3:
        movl    -4(%edi,%ecx,4), %eax
        incl    %eax
        sall    %eax
        subl    (%edx), %eax
        movl    %eax, (%edx)
        incl    %ecx
        addl    $4, %edx
.L2:
        cmpl    %esi, %ecx
        jle     .L3
        popl    %ebx
        popl    %esi
        popl    %edi
        leave
        ret



-- 


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

[Bug tree-optimization/18219] [4.0 Regression] gcc-4.0.0 bloats code by 31%

[uros at kss-loka dot si]

------- Additional Comments From uros at kss-loka dot si  2004-11-05 09:10 -------
It looks that this PR is related to PR17647. Should we merge them together?

Uros.

-- 


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

[Bug tree-optimization/18219] [4.0 Regression] gcc-4.0.0 bloats code by 31%

[giovannibajo at libero dot it]

------- Additional Comments From giovannibajo at libero dot it  2004-11-05 10:34 -------
Subject: Re:  [4.0 Regression] gcc-4.0.0 bloats code by 31%

uros at kss-loka dot si wrote:

> It looks that this PR is related to PR17647. Should we
> merge them together?

We are still waiting for Zdenek's patch to be applied. I will reevaluate the PR
after it.

Giovanni Bajo




-- 


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

[Bug tree-optimization/18219] [4.0 Regression] gcc-4.0.0 bloats code by 31%

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-11-05 14:34 -------
Hmm, for -O2 on PPC, we are not using the branch on count register instruction if we do that, -O2 will 
be smaller than -Os.

-- 


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

[Bug tree-optimization/18219] [4.0 Regression] gcc-4.0.0 bloats code by 31%

[neroden at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
OtherBugsDependingO|                            |18693
              nThis|                            |


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

[Bug tree-optimization/18219] [4.0 Regression] gcc-4.0.0 bloats code by 31%

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-01-21 07:57 -------
I think one of the problems is that ivopts causes out of ssa not to Coalesce two SSA_NAME:
Before out of ssa:
  D.1127_16 = *ivtmp.8_9;
  D.1128_21 = *ivtmp.12_30;
  D.1129_22 = D.1127_16 - D.1128_21;
  *ivtmp.12_30 = D.1129_22;
  ivtmp.3_17 = ivtmp.3_18 + 1;

  # ivtmp.12_30 = PHI <ivtmp.12_35(0), ivtmp.12_31(1)>;
  # ivtmp.8_9 = PHI <ivtmp.8_29(0), ivtmp.8_7(1)>;
  # ivtmp.3_18 = PHI <0(0), ivtmp.3_17(1)>;
<L1>:;
  ivtmp.8_7 = ivtmp.8_9 + 4B;
  ivtmp.12_31 = ivtmp.12_30 + 4B;
  D.1171_37 = ivtmp.3_18 + D.1163_6;
  i_38 = (int) D.1171_37;
  if (i_38 <= maxLen_4) goto <L0>; else goto <L2>;


After:
<L0>:;
  *ivtmp.12 = *ivtmp.17 - *ivtmp.12;
  ivtmp.3 = ivtmp.3 + 1;
  ivtmp.17 = ivtmp.8;
  ivtmp.12 = ivtmp.16;

<L1>:;
  ivtmp.8 = ivtmp.17 + 4B;
  ivtmp.16 = ivtmp.12 + 4B;
  if ((int) (ivtmp.3 + D.1163) <= maxLen) goto <L0>; else goto <L2>;

Note how there are two moves in the BB for L0.
Coalesce list: (6)ivtmp.12_30 & (7)ivtmp.12_31 [map: 6, 7] : Fail due to conflict
Coalesce list: (1)ivtmp.8_7 & (2)ivtmp.8_9 [map: 1, 2] : Fail due to conflict


-- 


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

[Bug tree-optimization/18219] [4.0 Regression] gcc-4.0.0 bloats code by 31%

[rakdver at atrey dot karlin dot mff dot cuni dot cz]

------- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni dot cz  2005-01-21 08:18 -------
Subject: Re:  [4.0 Regression] gcc-4.0.0 bloats code by 31%

> ------- Additional Comments From pinskia at gcc dot gnu dot org  2005-01-21 07:57 -------
> I think one of the problems is that ivopts causes out of ssa not to Coalesce two SSA_NAME:
> Before out of ssa:
>   D.1127_16 = *ivtmp.8_9;
>   D.1128_21 = *ivtmp.12_30;
>   D.1129_22 = D.1127_16 - D.1128_21;
>   *ivtmp.12_30 = D.1129_22;
>   ivtmp.3_17 = ivtmp.3_18 + 1;
> 
>   # ivtmp.12_30 = PHI <ivtmp.12_35(0), ivtmp.12_31(1)>;
>   # ivtmp.8_9 = PHI <ivtmp.8_29(0), ivtmp.8_7(1)>;
>   # ivtmp.3_18 = PHI <0(0), ivtmp.3_17(1)>;
> <L1>:;
>   ivtmp.8_7 = ivtmp.8_9 + 4B;
>   ivtmp.12_31 = ivtmp.12_30 + 4B;
>   D.1171_37 = ivtmp.3_18 + D.1163_6;
>   i_38 = (int) D.1171_37;
>   if (i_38 <= maxLen_4) goto <L0>; else goto <L2>;
> 
> 
> After:
> <L0>:;
>   *ivtmp.12 = *ivtmp.17 - *ivtmp.12;
>   ivtmp.3 = ivtmp.3 + 1;
>   ivtmp.17 = ivtmp.8;
>   ivtmp.12 = ivtmp.16;
> 
> <L1>:;
>   ivtmp.8 = ivtmp.17 + 4B;
>   ivtmp.16 = ivtmp.12 + 4B;
>   if ((int) (ivtmp.3 + D.1163) <= maxLen) goto <L0>; else goto <L2>;
> 
> Note how there are two moves in the BB for L0.
> Coalesce list: (6)ivtmp.12_30 & (7)ivtmp.12_31 [map: 6, 7] : Fail due to conflict
> Coalesce list: (1)ivtmp.8_7 & (2)ivtmp.8_9 [map: 1, 2] : Fail due to conflict

I am fairly sure that ivopts themselves create both ivtmp.12 and ivtmp.8
such that life ranges of their ssa names do not overlap.  However some
of the later passes (most probably dom) propagates ivtmp.8_9 to
expressions after definition of ivtmp.8_7.

It might help to add pass that would transform this code to the
following, thus enabling the coalescing of ivs.  I will give it a try.

  D.1127_16 = *ivtmp.8.9;
  D.1128_21 = *ivtmp.12.30;
  D.1129_22 = D.1127_16 - D.1128_21;
  *ivtmp.12.30 = D.1129_22;
  ivtmp.3_17 = ivtmp.3_18 + 1;

  # ivtmp.12_30 = PHI <ivtmp.12_35(0), ivtmp.12_31(1)>;
  # ivtmp.8_9 = PHI <ivtmp.8_29(0), ivtmp.8_7(1)>;
  # ivtmp.3_18 = PHI <0(0), ivtmp.3_17(1)>;
<L1>:;
  ivtmp.8.9 = ivtmp.8_9;
  ivtmp.8_7 = ivtmp.8_9 + 4B;
  ivtmp.12.30 = ivtmp.12_30;
  ivtmp.12_31 = ivtmp.12_30 + 4B;
  D.1171_37 = ivtmp.3_18 + D.1163_6;
  i_38 = (int) D.1171_37;
  if (i_38 <= maxLen_4) goto <L0>; else goto <L2>;


-- 


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

[Bug tree-optimization/18219] [4.0 Regression] gcc-4.0.0 bloats code by 31%

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-01-21 14:04 -------
This actually looks like a duplicate of PR19038 now. 

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
  BugsThisDependsOn|                            |19038


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

[Bug tree-optimization/18219] [4.0 Regression] gcc-4.0.0 bloats code by 31%

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-01-21 21:05 -------
(In reply to comment #11)
> This actually looks like a duplicate of PR19038 now. 
Actually it is not, the problem is related not doing loop copy header for -Os.


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
  BugsThisDependsOn|19038                       |


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

[Bug tree-optimization/18219] [4.0 Regression] gcc-4.0.0 bloats code by 31%

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2005-02-06 18:47 -------
Subject: Bug 18219

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	rakdver@gcc.gnu.org	2005-02-06 18:47:14

Modified files:
	gcc            : ChangeLog tree-ssa-loop-ivopts.c 

Log message:
	PR tree-optimization/18219
	* tree-ssa-loop-ivopts.c (get_computation_at): Produce computations
	in distributed form.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.7394&r2=2.7395
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-ssa-loop-ivopts.c.diff?cvsroot=gcc&r1=2.42&r2=2.43



-- 


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

[Bug tree-optimization/18219] [4.0 Regression] gcc-4.0.0 bloats code by 31%

[andrewhutchinson at cox dot net]

------- Additional Comments From andrewhutchinson at cox dot net  2005-02-08 02:12 -------
Bad post ignore


-- 


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

[Bug tree-optimization/18219] [4.0 Regression] gcc-4.0.0 bloats code by 31%

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-02-10 21:09 -------
On PPC, at least (now), the code size increases come from having more than one IV.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|patch                       |


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

[Bug tree-optimization/18219] [4.0 Regression] gcc-4.0.0 bloats code by 31%

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-02-10 23:57 -------
flags:                  .text size: 
-Os                     86 bytes 
-Os -fno-ivopts         86 bytes 
-m32 -Os                62 bytes 
-m32 -Os -fno-ivopts    54 bytes 
 

-- 


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

[Bug tree-optimization/18219] [4.0/4.1 Regression] gcc-4.0/4.1.0 bloats code by 31%

[mmitchel at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.0.0                       |4.0.1


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

[Bug tree-optimization/18219] [4.0/4.1 Regression] gcc-4.0/4.1.0 bloats code by 31%

[mmitchel at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.0.1                       |4.0.2


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

[Bug tree-optimization/18219] [4.0/4.1 Regression] gcc-4.0/4.1.0 bloats code by 31%

[mmitchel at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.0.2                       |4.0.3


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