[Bug rtl-optimization/53125] New: Very slow register allocation on SPARC

[Bug rtl-optimization/53125] New: Very slow register allocation on SPARC

[ian at airs dot com]

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

             Bug #: 53125
           Summary: Very slow register allocation on SPARC
    Classification: Unclassified
           Product: gcc
           Version: 4.7.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: ian@airs.com
                CC: ro@gcc.gnu.org, vmakarov@redhat.com
            Target: sparc-sun-solaris2.11


Created attachment 27244
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27244
Test case

The attached test case is a conversion to C of a machine generated test case in
Go (the machine generated Go source is in
gcc/testsuite/go.test/test/cmpldivide1.go).

When I compile this test case without optimization on an x86_64 GNU/Linux
system, it takes 5.8 seconds.  When I compile it without optimization on a
SPARC Solaris 2.11 system, it takes 2 minutes 32.8 seconds.  The SPARC machine
is slower than the x86_64 machine.  But it's not that much slower.

According to -ftime-report on the SPARC system, 45% of the time is "register
information" and 41% of the time is "integrated RA."

Since the file is machine generated, I would be willing to accept a 2 1/2
minute compilation time with optimization.  But without optimization it is just
too slow.  And the discrepancy with x86_64 is extreme.

[Bug rtl-optimization/53125] Very slow register allocation on SPARC

[ian at airs dot com]

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

--- Comment #1 from Ian Lance Taylor <ian at airs dot com> 2012-04-25 22:34:17 UTC ---
Out of curiousity I tried compiling the test case with -O2.  On x86_64 it took
57.4 seconds, on SPARC it took 20 minutes 33 seconds.

[Bug rtl-optimization/53125] Very slow register allocation on SPARC

[vmakarov at redhat dot com]

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

--- Comment #2 from Vladimir Makarov <vmakarov at redhat dot com> 2012-04-29 00:08:54 UTC ---
I'll look at this PR in a week.

[Bug rtl-optimization/53125] Very slow register allocation on SPARC

[vmakarov at redhat dot com]

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

--- Comment #3 from Vladimir Makarov <vmakarov at redhat dot com> 2012-05-10 18:30:19 UTC ---
  I've tried a recent trunk on gcc63 of the compiler farm with -O0.  The
compilation takes about 300sec.  I checked also gcc-4.3 (this last version with
the old RA), it takes also about 300sec.  The actual old RA is slower (it takes
150sec) than IRA (it takes 55sec) but register information pass (more exactly
regstat_compute_ri which is a part of DF-infrastructure) takes more time in the
trunk than in gcc4.3.  So my times are different what you reported.  Probably
it depends on a machine (gcc63 is relatively modern SPARC machine with NIAGARA
processors).

  After some investigation, I found that the trunk gcc calls regstat_compute_ri
more than gcc-4.3.  That is a result of recent addition to IRA to move some
insns (a month old Bernd's patch).  It is not worth to do for -O0.  So I am
going to switch it off and achieve the same number of regstat_compute_ri calls
(2 of them) as in gcc-4.3 and that means achieving less 200sec of compilation
time. (65% of previous time).  I am going to submit a patch today.

  The futher improvement of regstat_compute_ri is not possible because we need
one call for IRA needs and one call after reload transformations (for
subsequent passes).  Speedup of IRA itself can have only a small impact.  I
don't see how it is possible.  It is very simple and fast enough (3 times
faster than the old RA).

  One might think that not doing RA at all (setting -1 for all reg_renumber
elements) could speed the case up.  But this is not true.  It increases reload
work enormously and generates > 2-3 times more insns which will slow down the
compiler even more.

  So, Ian, if you need more speedup for -O0, regstat_compute_ri should be
improved.  But that is not my responsibility area.  For me, it is strange that
such simple task (which requires 1 pass of RTL) takes so much time for this
case.

[Bug rtl-optimization/53125] Very slow register allocation on SPARC

[steven at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2012-05-10
                 CC|                            |steven at gcc dot gnu.org
         AssignedTo|unassigned at gcc dot       |steven at gcc dot gnu.org
                   |gnu.org                     |
     Ever Confirmed|0                           |1

--- Comment #4 from Steven Bosscher <steven at gcc dot gnu.org> 2012-05-10 18:37:11 UTC ---
DF -> mine to investigate.

[Bug rtl-optimization/53125] Very slow register allocation on SPARC

[vmakarov at gcc dot gnu.org]

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

--- Comment #5 from Vladimir Makarov <vmakarov at gcc dot gnu.org> 2012-05-10 19:58:09 UTC ---
Author: vmakarov
Date: Thu May 10 19:58:01 2012
New Revision: 187373

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=187373
Log:
2012-05-10  Vladimir Makarov  <vmakarov@redhat.com>

    PR rtl-optimization/53125
    * ira.c (ira): Call find_moveable_pseudos or
    move_unallocated_pseudos if only ira_conflicts_p is true.


Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/ira.c

[Bug rtl-optimization/53125] Very slow register allocation on SPARC

[steven at gcc dot gnu.org]

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

--- Comment #6 from Steven Bosscher <steven at gcc dot gnu.org> 2012-05-10 22:17:36 UTC ---
Created attachment 27369
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27369
Compute REG_LIVE_LENGTH smarter

The way local_live is used to compute REG_LIVE_LENGTH is just stupid.

Something like this patch would be helpful (drops from 73s after Vlad's patch
to 39s).

A complete version of this should also handle MW-hardregs.

[Bug rtl-optimization/53125] Very slow compilation on SPARC

[steven at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |alias
            Summary|Very slow register          |Very slow compilation on
                   |allocation on SPARC         |SPARC

--- Comment #7 from Steven Bosscher <steven at gcc dot gnu.org> 2012-05-11 09:17:44 UTC ---
At -O1, with Vlad's patch and mine applied, compile time is ~230s. The "forward
prop" pass takes 18% of that time, and "alias stmt walking" takes 67%.

This is with a cross from x86_64-linux-gnu to sparc-sun-solaris2.11, trunk
r187371, checking enabled.

[Bug rtl-optimization/53125] Very slow compilation on SPARC

[rguenth at gcc dot gnu.org]

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

--- Comment #8 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-05-11 09:33:19 UTC ---
The alias stmt walking time is because of the redundant store removal code
and because of PR52054 it has to re-do the walks (there are 7200 stores in
the function).

[Bug rtl-optimization/53125] Very slow compilation on SPARC

[steven at gcc dot gnu.org]

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

--- Comment #9 from Steven Bosscher <steven at gcc dot gnu.org> 2012-05-17 17:55:01 UTC ---
Author: steven
Date: Thu May 17 17:54:52 2012
New Revision: 187633

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=187633
Log:
    PR rtl-optimization/53125
    * regstat.c (regstat_bb_compute_ri): Take new local_live_last_luid
    argument.  Simplify calculation of REG_LIVE_LENGTH for regnos that
    die in the basic block.  Correctly top off REG_FREQ and
    REG_FREQ_CALLS_CROSSED.
    Remove do_not_gen.
    (regstat_compute_ri): Allocate and free local_live_last_luid.
    Remove do_not_gen.
    (regstat_bb_compute_calls_crossed): Correctly top off
    REG_FREQ_CALLS_CROSSED.


Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/regstat.c

[Bug rtl-optimization/53125] Very slow compilation on SPARC

[steven at gcc dot gnu.org]

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

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

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

--- Comment #10 from Steven Bosscher <steven at gcc dot gnu.org> 2012-05-17 17:57:05 UTC ---
Fixed on trunk for GCC 4.8.