[Bug rtl-optimization/50101] New: GCC 4.5 and 4.6 generate suboptimal code on ppc for countdown loops when the CTR register cannot be used

[Bug rtl-optimization/50101] New: GCC 4.5 and 4.6 generate suboptimal code on ppc for countdown loops when the CTR register cannot be used

[meissner at gcc dot gnu.org]

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

             Bug #: 50101
           Summary: GCC 4.5 and 4.6 generate suboptimal code on ppc for
                    countdown loops when the CTR register cannot be used
    Classification: Unclassified
           Product: gcc
           Version: 4.6.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: meissner@gcc.gnu.org
              Host: powerpc64-linux
            Target: powerpc64-linux
             Build: powerpc64-linux


When GCC switched over to the IRA register allocator in GCC 4.5, it made some
loops run slower on the PowerPC.  In particular, the powerpc has a count down
register (CTR) that the compiler can use with the -fbranch-count-reg
optimization.  However, if the CTR register is not available in the loop, the
compiler does not use a GPR register for the loop index, but instead loads the
index value from memory, increments it, and stores it back to the stack.

For example, in the code:

int code[65536];

mike()
{
  int j;
  long addr;

  for (j = 0; j < 65536; j+=4) {
    asm("mtctr %1" : "=c" (addr) : "r" (&code[j]));
    asm("bctrl" : : "c" (addr) : "lr" );
  }
}

It generates the following on 4.3 (Sles 11SP1 host compiler):

.L.mike:
        mflr 0
        ld 9,.LC0@toc(2)
        li 11,16384
        std 0,16(1)
        .p2align 4,,15
.L2:
#APP
 # 10 "test-ppc-ctr.c" 1
        mtctr 9
 # 0 "" 2
 # 11 "test-ppc-ctr.c" 1
        bctrl
 # 0 "" 2
#NO_APP
        addic. 11,11,-1
        addi 9,9,16
        bne 0,.L2
        ld 0,16(1)
        mtlr 0
        blr

If I go to a 4.4 based compiler such as the RHEL6 host compiler I get:

.L.mike:
        mflr 0
        ld 9,.LC0@toc(2)
        std 0,16(1)
        li 0,16384
        std 0,-16(1)
        .p2align 4,,15
.L2:
#APP
 # 10 "test-ppc-ctr.c" 1
        mtctr 9
 # 0 "" 2
 # 11 "test-ppc-ctr.c" 1
        bctrl
 # 0 "" 2
#NO_APP
        ld 0,-16(1)
        addi 9,9,16
        addic. 11,0,-1
        std 11,-16(1)
        bne 0,.L2
        ld 0,16(1)
        mtlr 0
        blr

Notice that it stores and loads the loop index value.  If I use
-fno-branch-count-reg, it generates code to use the GPRS:

.L.mike:
        mflr 0
        ld 9,.LC0@toc(2)
        std 0,16(1)
        addis 0,9,0x4
        .p2align 4,,15
.L2:
#APP
 # 10 "test-ppc-ctr.c" 1
        mtctr 9
 # 0 "" 2
 # 11 "test-ppc-ctr.c" 1
        bctrl
 # 0 "" 2
#NO_APP
        addi 9,9,16
        cmpd 7,9,0
        bne 7,.L2
        ld 0,16(1)
        mtlr 0
        blr

This is fixed in the GCC 4.7 development sources.  The development source
revision that fixed this was subversion id 171649, created on March 28th, 2011
by Vladimir Makarov  <vmakarov@redhat.com>, in his large rewrite of the ira
register allocator.

As an experiment, I built the Spec 2006 benchmark suite with
-fno-branch-count-reg.  As expected, there are a number of benchmarks that
regress if the count register optimization, but there are a few benchmarks that
get a large speed up by disabling this optimization, which probably indicates
they are being mis-optimized.  The benchmarks with the speedup include:
464.h264ref (19.65% improvement), 434.zeusmp (17.92% improvement) and
459.GemsFDTD (13.02% improvement).

[Bug rtl-optimization/50101] GCC 4.5 and 4.6 generate suboptimal code on ppc for countdown loops when the CTR register cannot be used

[meissner at gcc dot gnu.org]

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

--- Comment #1 from Michael Meissner <meissner at gcc dot gnu.org> 2011-08-16 20:57:01 UTC ---
Created attachment 25026
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=25026
Example test case

[Bug rtl-optimization/50101] GCC 4.5 and 4.6 generate suboptimal code on ppc for countdown loops when the CTR register cannot be used

[rguenth at gcc dot gnu.org]

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

--- Comment #2 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-08-17 08:10:03 UTC ---
I suppose the CTR is introduced after RA in machine-dependent reorg?  In which
case can the issue be fixed on branches by adjusting register cost of the CTR?

[Bug rtl-optimization/50101] GCC 4.5 and 4.6 generate suboptimal code on ppc for countdown loops when the CTR register cannot be used

[meissner at gcc dot gnu.org]

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

--- Comment #3 from Michael Meissner <meissner at gcc dot gnu.org> 2011-08-17 15:43:00 UTC ---
(In reply to comment #2)
> I suppose the CTR is introduced after RA in machine-dependent reorg?  In which
> case can the issue be fixed on branches by adjusting register cost of the CTR?

No, the pattern would normally allocate the CTR, and has options to fall back
to register, and memory.  According to the comments in the source, because it
is a JUMP_INSN, it has to provide reloads from memory in case it can't find a
register.  Previously, GCC was able to allocate a register, but now it doesn't
seem to.

Here is the pattern from rs6000.md:

;; We need to be able to do this for any operand, including MEM, or we
;; will cause reload to blow up since we don't allow output reloads on
;; JUMP_INSNs.
;; For the length attribute to be calculated correctly, the
;; label MUST be operand 0.

(define_insn "*ctr<mode>_internal1"
  [(set (pc)
    (if_then_else (ne (match_operand:P 1 "register_operand" "c,*r,*r,*r")
              (const_int 1))
              (label_ref (match_operand 0 "" ""))
              (pc)))
   (set (match_operand:P 2 "nonimmediate_operand" "=1,*r,m,*q*c*l")
    (plus:P (match_dup 1)
         (const_int -1)))
   (clobber (match_scratch:CC 3 "=X,&x,&x,&x"))
   (clobber (match_scratch:P 4 "=X,X,&r,r"))]
  ""
  "*
{
  if (which_alternative != 0)
    return \"#\";
  else if (get_attr_length (insn) == 4)
    return \"{bdn|bdnz} %l0\";
  else
    return \"bdz $+8\;b %l0\";
}"
  [(set_attr "type" "branch")
   (set_attr "length" "*,12,16,16")])

I will upload the rtl dump files as attachments.

[Bug rtl-optimization/50101] GCC 4.5 and 4.6 generate suboptimal code on ppc for countdown loops when the CTR register cannot be used

[meissner at gcc dot gnu.org]

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

--- Comment #6 from Michael Meissner <meissner at gcc dot gnu.org> 2011-08-17 15:45:59 UTC ---
Created attachment 25036
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=25036
Postreload rtl dump file

[Bug rtl-optimization/50101] GCC 4.5 and 4.6 generate suboptimal code on ppc for countdown loops when the CTR register cannot be used

[meissner at gcc dot gnu.org]

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

--- Comment #4 from Michael Meissner <meissner at gcc dot gnu.org> 2011-08-17 15:44:20 UTC ---
Created attachment 25034
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=25034
Sched1 rtl dump file

[Bug rtl-optimization/50101] GCC 4.5 and 4.6 generate suboptimal code on ppc for countdown loops when the CTR register cannot be used

[meissner at gcc dot gnu.org]

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

--- Comment #5 from Michael Meissner <meissner at gcc dot gnu.org> 2011-08-17 15:45:08 UTC ---
Created attachment 25035
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=25035
IRA rtl dump file

[Bug rtl-optimization/50101] GCC 4.5 and 4.6 generate suboptimal code on ppc for countdown loops when the CTR register cannot be used

[rguenth at gcc dot gnu.org]

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

--- Comment #7 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-08-18 08:58:28 UTC ---
(In reply to comment #3)
> (In reply to comment #2)
> > I suppose the CTR is introduced after RA in machine-dependent reorg?  In which
> > case can the issue be fixed on branches by adjusting register cost of the CTR?
> 
> No, the pattern would normally allocate the CTR, and has options to fall back
> to register, and memory.  According to the comments in the source, because it
> is a JUMP_INSN, it has to provide reloads from memory in case it can't find a
> register.  Previously, GCC was able to allocate a register, but now it doesn't
> seem to.
> 
> Here is the pattern from rs6000.md:
> 
> ;; We need to be able to do this for any operand, including MEM, or we
> ;; will cause reload to blow up since we don't allow output reloads on
> ;; JUMP_INSNs.
> ;; For the length attribute to be calculated correctly, the
> ;; label MUST be operand 0.
> 
> (define_insn "*ctr<mode>_internal1"
>   [(set (pc)
>     (if_then_else (ne (match_operand:P 1 "register_operand" "c,*r,*r,*r")
>               (const_int 1))
>               (label_ref (match_operand 0 "" ""))
>               (pc)))
>    (set (match_operand:P 2 "nonimmediate_operand" "=1,*r,m,*q*c*l")
>     (plus:P (match_dup 1)
>          (const_int -1)))
>    (clobber (match_scratch:CC 3 "=X,&x,&x,&x"))
>    (clobber (match_scratch:P 4 "=X,X,&r,r"))]
>   ""
>   "*
> {
>   if (which_alternative != 0)
>     return \"#\";
>   else if (get_attr_length (insn) == 4)
>     return \"{bdn|bdnz} %l0\";
>   else
>     return \"bdz $+8\;b %l0\";
> }"
>   [(set_attr "type" "branch")
>    (set_attr "length" "*,12,16,16")])
> 
> I will upload the rtl dump files as attachments.

Did you try pessimizing the non-ctr reg alternatives (and the memory
alternative even more)?  Like adding ! to the non-ctr alternatives
and ? to the memory one?  Not sure if those markers are looked at
by IRA though.

[Bug rtl-optimization/50101] GCC 4.5 and 4.6 generate suboptimal code on ppc for countdown loops when the CTR register cannot be used

[meissner at linux dot vnet.ibm.com]

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

--- Comment #8 from Michael Meissner <meissner at linux dot vnet.ibm.com> 2011-08-19 14:05:51 UTC ---
On Thu, Aug 18, 2011 at 08:58:28AM +0000, rguenth at gcc dot gnu.org wrote:
> Did you try pessimizing the non-ctr reg alternatives (and the memory
> alternative even more)?  Like adding ! to the non-ctr alternatives
> and ? to the memory one?  Not sure if those markers are looked at
> by IRA though.

Yes, I should have mentioned that I tried various combinations of ?, !, and *
and the combinations I tried aborted.  I've certainly suspected that IRA now
longer looks at !, ?, and * like the previous register allocator did
previously.  It may be that it is  special due to being a JUMP_INSN.

[Bug rtl-optimization/50101] GCC 4.5 and 4.6 generate suboptimal code on ppc for countdown loops when the CTR register cannot be used

[law at redhat dot com]

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

--- Comment #9 from Jeffrey A. Law <law at redhat dot com> 2011-08-19 15:35:36 UTC ---
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 08/19/11 08:05, meissner at linux dot vnet.ibm.com wrote:
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50101
> 
> --- Comment #8 from Michael Meissner <meissner at linux dot
> vnet.ibm.com> 2011-08-19 14:05:51 UTC --- On Thu, Aug 18, 2011 at
> 08:58:28AM +0000, rguenth at gcc dot gnu.org wrote:
>> Did you try pessimizing the non-ctr reg alternatives (and the
>> memory alternative even more)?  Like adding ! to the non-ctr
>> alternatives and ? to the memory one?  Not sure if those markers
>> are looked at by IRA though.
> 
> Yes, I should have mentioned that I tried various combinations of ?,
> !, and * and the combinations I tried aborted.  I've certainly
> suspected that IRA now longer looks at !, ?, and * like the previous
> register allocator did previously.  It may be that it is  special due
> to being a JUMP_INSN.
I wonder if we could record which allocnos correspond to outputs of
JUMP_INSNS, then in the allocno sorting code, move all of them to the
front of the list.

In effect, this makes those allocnos have higher priority for getting a
hard reg than everything else.

Thoughts?

Jeff


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJOToKzAAoJEBRtltQi2kC761UIAK4E0qfQ174Zakhd3JpDuLZ5
teyBgLTnoNMmO1pIdY/SgDP39PvtG9zwFoUwUDljDfZNbwVEHr2EmFgdu6RzmEAM
H6NvI40PPKvN9YIY4hkT007OWKatXU2IrXnHij0ZoEIktobLbC38vz6JHTfNDJkW
Bl9MKBeVfvMma7yzEZ2tgIXwy16SNuebHJuU6718uooMMwZ2agDWad9CsPvVGRtj
yzuvUQH3qg/ZdCfCfHKF+0hKzLe/1S4XNBt8X8Ezj582CR8irDzOngGQkagDvpTz
DXwGKDKBUjMAO3VYEw6GYWbfyxsnv1VFaXezNj/9/QpVKswvRi5vtHhii3LYzlY=
=vmEo
-----END PGP SIGNATURE-----

[Bug rtl-optimization/50101] [4.5/4.6 regression] GCC 4.5 and 4.6 generate suboptimal code on ppc for countdown loops when the CTR register cannot be used

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
   Target Milestone|---                         |4.5.4
            Summary|GCC 4.5 and 4.6 generate    |[4.5/4.6 regression] GCC
                   |suboptimal code on ppc for  |4.5 and 4.6 generate
                   |countdown loops when the    |suboptimal code on ppc for
                   |CTR register cannot be used |countdown loops when the
                   |                            |CTR register cannot be used

[Bug rtl-optimization/50101] [4.5/4.6 regression] GCC 4.5 and 4.6 generate suboptimal code on ppc for countdown loops when the CTR register cannot be used

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #10 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-07-02 12:02:35 UTC ---
The 4.5 branch is being closed, adjusting target milestone.

[Bug rtl-optimization/50101] [4.6 regression] GCC 4.5 and 4.6 generate suboptimal code on ppc for countdown loops when the CTR register cannot be used

[jakub at gcc dot gnu.org]

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

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

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

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