[Bug other/52391] New: [4.7 regression] genattrtab almost 5X slower for m68k than in 4.6 and earlier releases

[Bug other/52391] New: [4.7 regression] genattrtab almost 5X slower for m68k than in 4.6 and earlier releases

[mikpe at it dot uu.se]

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

             Bug #: 52391
           Summary: [4.7 regression] genattrtab almost 5X slower for m68k
                    than in 4.6 and earlier releases
    Classification: Unclassified
           Product: gcc
           Version: 4.7.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: other
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: mikpe@it.uu.se


Building a gcc-4.7 cross to m68k-linux takes almost twice as long as it takes
for earlier releases, and most of the slowdown comes from genattrtab taking
almost 5 times longer.

Here's some numbers for build times and genattrtab times for the 4 latest gcc
versions (--target=m68k-linux --enable-languages=c --enable-checking=release,
non-parallel "make", on a 2.4GHz C2Q6600):

gcc-4.4-20120221:
    genattrtab: 2:13.31
    total: 9m17s

gcc-4.5-20120223:
    genattrtab: 1:48.17
    total: 9m10s

gcc-4.6-20120224:
    genattrtab: 1.44.05
    total: 9m14s

gcc-4.7-20120225:
    genattrtab: 8:25.99
    total: 16m21s

The genattrtab times are as reported by /usr/bin/time on Fedora 14, i.e.
minutes:seconds.fraction.

I haven't measured other target build times in detail, but my gut feeling is
that they're not nearly as bad as these, so it might be an issue with the m68k
target specifically or perhaps cc0 targets in general.

[Bug other/52391] [4.7 regression] genattrtab almost 5X slower for m68k than in 4.6 and earlier releases

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |WAITING
   Last reconfirmed|                            |2012-02-27
   Target Milestone|---                         |4.7.0
     Ever Confirmed|0                           |1

--- Comment #1 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-02-27 09:31:49 UTC ---
There were not many changes to genattrtab vs. GCC 4.6 - can you profile it
and report differences?

[Bug bootstrap/52391] [4.7 regression] genattrtab almost 5X slower for m68k than in 4.6 and earlier releases

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |build
             Target|                            |m68k-linux
           Priority|P3                          |P4
          Component|other                       |bootstrap
               Host|                            |x86_64-*-*
              Build|                            |x86_64-*-*

--- Comment #2 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-02-27 10:47:38 UTC ---
Cross from sth like x86_64 I assume.  m68k is not primary/secondary.

[Bug bootstrap/52391] [4.7 regression] genattrtab almost 5X slower for m68k than in 4.6 and earlier releases

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-02-27 20:06:03 UTC ---
Looks to be http://gcc.gnu.org/ml/gcc-patches/2011-08/msg01181.html
aka http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=178387

[Bug bootstrap/52391] [4.7 regression] genattrtab almost 5X slower for m68k than in 4.6 and earlier releases

[mikpe at it dot uu.se]

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

--- Comment #4 from Mikael Pettersson <mikpe at it dot uu.se> 2012-02-27 21:40:21 UTC ---
My bisection identified that:
in r178386 genattrtab timings are comparable to gcc-4.6,
in r178387 genattrtab got 8.4 times slower, and
in r178388 genattrtab improved to being "only" 5 times slower than 4.6.

[Bug bootstrap/52391] [4.7 regression] genattrtab almost 5X slower for m68k than in 4.6 and earlier releases

[steven at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|WAITING                     |NEW

--- Comment #5 from Steven Bosscher <steven at gcc dot gnu.org> 2012-02-27 22:54:34 UTC ---
Confirmed with a cross from x86_64-linux to m68k-linux.

[Bug bootstrap/52391] [4.7 regression] genattrtab almost 5X slower for m68k than in 4.6 and earlier releases

[mikpe at it dot uu.se]

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

--- Comment #6 from Mikael Pettersson <mikpe at it dot uu.se> 2012-02-27 23:03:00 UTC ---
Top-most lines from gprof profile of genattrtab @ r178388:

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 67.71    437.11   437.11 138244364     0.00     0.00  simplify_and_tree
 22.16    580.15   143.04 532054774     0.00     0.00  attr_equal_p
  6.49    622.06    41.91 1753529513     0.00     0.00  rtx_equal_p
  2.23    636.47    14.41 78398171     0.00     0.00  simplify_or_tree
  0.99    642.88     6.41  2169340     0.00     0.00  simplify_test_exp
  0.24    644.41     1.53 15087810     0.00     0.00  compute_alternative_mask
  0.12    645.20     0.79  2105645     0.00     0.00  attr_rtx

[Bug bootstrap/52391] [4.7 regression] genattrtab almost 5X slower for m68k than in 4.6 and earlier releases

[steven at gcc dot gnu.org]

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

--- Comment #7 from Steven Bosscher <steven at gcc dot gnu.org> 2012-02-27 23:07:00 UTC ---
Created attachment 26767
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=26767
Diff between insn-attrtab.c for r178386 and r178387.

The diff is huge. Diffstat:

 insn-attrtab.c |57850
++++++++-------------------------------------------------
 1 file changed, 8396 insertions(+), 49454 deletions(-)

So insn-attrtab.c is much smaller, but generating it takes much longer.

[Bug bootstrap/52391] [4.7 regression] genattrtab almost 5X slower for m68k than in 4.6 and earlier releases

[jakub at gcc dot gnu.org]

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

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-02-27 23:16:09 UTC ---
Yeah, before that the huge conditions wouldn't be optimized, because the
SYMBOL_REFs in them wouldn't rtx_equal_p even when they had the same strings.

The question is if the test optimization can be improved, but in any case this
doesn't look like a very important regression, it is much more important how
fast is the insn-attrtab.c code than how long it takes to generate it.  The
former is used for all compilations, the latter only once (or 3 times for
bootstrap) during gcc build.

[Bug bootstrap/52391] [4.7 regression] genattrtab almost 5X slower for m68k than in 4.6 and earlier releases

[steven at gcc dot gnu.org]

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

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

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

--- Comment #9 from Steven Bosscher <steven at gcc dot gnu.org> 2012-02-28 00:13:29 UTC ---
Well, we do seem to go a bit to extremes to simplify an expression:
#2212 0x0000000000407445 in simplify_test_exp (exp=0x78f010, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2595
#2213 0x0000000000406f8f in simplify_test_exp (exp=0x78f390, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2506
#2214 0x0000000000407445 in simplify_test_exp (exp=0x78f010, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2595
#2215 0x0000000000406f8f in simplify_test_exp (exp=0x78f350, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2506
#2216 0x0000000000407445 in simplify_test_exp (exp=0x78f010, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2595
#2217 0x0000000000406f8f in simplify_test_exp (exp=0x78f310, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2506
#2218 0x0000000000407445 in simplify_test_exp (exp=0x78f010, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2595
#2219 0x0000000000406f8f in simplify_test_exp (exp=0x78f2d0, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2506
#2220 0x0000000000407445 in simplify_test_exp (exp=0x78f010, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2595
#2221 0x0000000000406f8f in simplify_test_exp (exp=0x78f290, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2506
#2222 0x0000000000407445 in simplify_test_exp (exp=0x78f010, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2595
#2223 0x0000000000406f8f in simplify_test_exp (exp=0x78f250, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2506
#2224 0x0000000000407445 in simplify_test_exp (exp=0x78f010, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2595
#2225 0x0000000000406f8f in simplify_test_exp (exp=0x78f210, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2506
#2226 0x0000000000407445 in simplify_test_exp (exp=0x78f010, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2595
#2227 0x0000000000406f8f in simplify_test_exp (exp=0x78f1d0, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2506
#2228 0x0000000000407445 in simplify_test_exp (exp=0x78f010, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2595
#2229 0x0000000000406f8f in simplify_test_exp (exp=0x78f190, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2506
#2230 0x0000000000407445 in simplify_test_exp (exp=0x78f010, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2595
#2231 0x0000000000406f8f in simplify_test_exp (exp=0x78f150, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2506
#2232 0x0000000000407445 in simplify_test_exp (exp=0x78f010, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2595
#2233 0x0000000000406f8f in simplify_test_exp (exp=0x78f110, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2506
#2234 0x0000000000407445 in simplify_test_exp (exp=0x78f010, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2595
#2235 0x0000000000406f8f in simplify_test_exp (exp=0x78f0d0, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2506
#2236 0x0000000000407445 in simplify_test_exp (exp=0x78f010, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2595
#2237 0x0000000000406f8f in simplify_test_exp (exp=0x78f090, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2506
#2238 0x0000000000407445 in simplify_test_exp (exp=0x78f010, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2595
#2239 0x0000000000406f8f in simplify_test_exp (exp=0x78f050, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2506
#2240 0x0000000000407445 in simplify_test_exp (exp=0x78f010, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2595
#2241 0x00000000004074da in simplify_test_exp (exp=0x76f300, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2602
#2242 0x0000000000406a02 in simplify_test_exp_in_temp (exp=0x76f300,
insn_code=0, insn_index=65) at ../../trunk/gcc/genattrtab.c:2335
#2243 0x0000000000405246 in simplify_cond (exp=0x739890, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:1671
#2244 0x0000000000408225 in optimize_attrs () at
../../trunk/gcc/genattrtab.c:2877
#2245 0x000000000040cfe9 in main (argc=3, argv=0x7fffffffe328) at
../../trunk/gcc/genattrtab.c:5023
(gdb)


It's not very productive, either:

#2230 0x0000000000407445 in simplify_test_exp (exp=0x78f010, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2595
2595                  return SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
(gdb) call print_rtl (stderr,exp)
(and (eq_attr/u/i ("cpu") ("cfv4"))
    (eq_attr_alt/s 1 1))
(gdb) down
#2229 0x0000000000406f8f in simplify_test_exp (exp=0x78f190, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2506
2506          right = SIMPLIFY_TEST_EXP (XEXP (exp, 1), insn_code, insn_index);
(gdb) call print_rtl (stderr,exp)
(and (eq_attr_alt/s 2 0)
    (and (eq_attr/u/i ("cpu") ("cfv4"))
        (eq_attr_alt/s 1 1)))
(gdb) down
#2228 0x0000000000407445 in simplify_test_exp (exp=0x78f010, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2595
2595                  return SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
(gdb) call print_rtl (stderr,exp)
(and (eq_attr/u/i ("cpu") ("cfv4"))
    (eq_attr_alt/s 1 1))
(gdb) down
#2227 0x0000000000406f8f in simplify_test_exp (exp=0x78f1d0, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2506
2506          right = SIMPLIFY_TEST_EXP (XEXP (exp, 1), insn_code, insn_index);
(gdb) call print_rtl (stderr,exp)
(and (eq_attr_alt/s 2 0)
    (and (eq_attr/u/i ("cpu") ("cfv4"))
        (eq_attr_alt/s 1 1)))
(gdb) down
#2226 0x0000000000407445 in simplify_test_exp (exp=0x78f010, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2595
2595                  return SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
(gdb) call print_rtl (stderr,exp)
(and (eq_attr/u/i ("cpu") ("cfv4"))
    (eq_attr_alt/s 1 1))
(gdb) down
#2225 0x0000000000406f8f in simplify_test_exp (exp=0x78f210, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2506
2506          right = SIMPLIFY_TEST_EXP (XEXP (exp, 1), insn_code, insn_index);
(gdb) call print_rtl (stderr,exp)
(and (eq_attr_alt/s 2 0)
    (and (eq_attr/u/i ("cpu") ("cfv4"))
        (eq_attr_alt/s 1 1)))
(gdb) down
#2224 0x0000000000407445 in simplify_test_exp (exp=0x78f010, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2595
2595                  return SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
(gdb) call print_rtl (stderr,exp)
(and (eq_attr/u/i ("cpu") ("cfv4"))
    (eq_attr_alt/s 1 1))
(gdb) down
#2223 0x0000000000406f8f in simplify_test_exp (exp=0x78f250, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2506
2506          right = SIMPLIFY_TEST_EXP (XEXP (exp, 1), insn_code, insn_index);
(gdb) call print_rtl (stderr,exp)
(and (eq_attr_alt/s 2 0)
    (and (eq_attr/u/i ("cpu") ("cfv4"))
        (eq_attr_alt/s 1 1)))
(gdb) down
#2222 0x0000000000407445 in simplify_test_exp (exp=0x78f010, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2595
2595                  return SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
(gdb) call print_rtl (stderr,exp)
(and (eq_attr/u/i ("cpu") ("cfv4"))
    (eq_attr_alt/s 1 1))
(gdb) down
#2221 0x0000000000406f8f in simplify_test_exp (exp=0x78f290, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2506
2506          right = SIMPLIFY_TEST_EXP (XEXP (exp, 1), insn_code, insn_index);
(gdb) call print_rtl (stderr,exp)
(and (eq_attr_alt/s 2 0)
    (and (eq_attr/u/i ("cpu") ("cfv4"))
        (eq_attr_alt/s 1 1)))
(gdb) down
#2220 0x0000000000407445 in simplify_test_exp (exp=0x78f010, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2595
2595                  return SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
(gdb) call print_rtl (stderr,exp)
(and (eq_attr/u/i ("cpu") ("cfv4"))
    (eq_attr_alt/s 1 1))
(gdb) down
#2219 0x0000000000406f8f in simplify_test_exp (exp=0x78f2d0, insn_code=0,
insn_index=65) at ../../trunk/gcc/genattrtab.c:2506
2506          right = SIMPLIFY_TEST_EXP (XEXP (exp, 1), insn_code, insn_index);
(gdb) call print_rtl (stderr,exp)
(and (eq_attr_alt/s 2 0)
    (and (eq_attr/u/i ("cpu") ("cfv4"))
        (eq_attr_alt/s 1 1)))
(gdb) (etc...)

[Bug bootstrap/52391] [4.7 regression] genattrtab almost 5X slower for m68k than in 4.6 and earlier releases

[steven at gcc dot gnu.org]

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

--- Comment #10 from Steven Bosscher <steven at gcc dot gnu.org> 2012-02-28 09:00:21 UTC ---
F, that backtrace was due to an error in the patch I had to look at what
simplify_and_tree was doing.

genattrtab is trying to simplify huge and-trees, mostly for m68k_sched_* symbol
refs.

[Bug bootstrap/52391] [4.7/4.8 regression] genattrtab almost 5X slower for m68k than in 4.6 and earlier releases

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.7.0                       |4.7.1

--- Comment #11 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-03-22 08:26:27 UTC ---
GCC 4.7.0 is being released, adjusting target milestone.

[Bug bootstrap/52391] [4.7/4.8 regression] genattrtab almost 5X slower for m68k than in 4.6 and earlier releases

[steven at gcc dot gnu.org]

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

--- Comment #12 from Steven Bosscher <steven at gcc dot gnu.org> 2012-05-05 10:06:32 UTC ---
Created attachment 27315
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27315
Avoid diving deep through generated IOR trees for EQ_ATTR

This patch tries to keep IOR-trees for EQ_ATTR tests together. This improves
genattrtab run time and also the generated code because more get_attr_* results
are cached.

On gcc110, the run time for genattrtab for m68k goes down from 9m3s to 4m15s.
The difference in insn-attrtab looks like an improvement at first glance, but I
could use some help interpreting the differences. (Will attach shortly.)

(The cf.md bit only sorts the attributes alphabetically but doesn't change the
genattrtab run time.)

[Bug bootstrap/52391] [4.7/4.8 regression] genattrtab almost 5X slower for m68k than in 4.6 and earlier releases

[steven at gcc dot gnu.org]

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

--- Comment #13 from Steven Bosscher <steven at gcc dot gnu.org> 2012-05-05 10:13:48 UTC ---
Created attachment 27316
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27316
Difference in insn-attrtab.c before/after applyin
PR52391_compare_IOP_tree_v1.diff

tmp-attrtab.c is *with* the patch applied, insn-attrtab.c is without patch, for
GCC trunk at r186902.

Typical difference:

$ grep m68k_sched_branch_type v1_insn-attrtab.diff | grep "^\-" | wc
    116     464    4524
$ grep m68k_sched_branch_type v1_insn-attrtab.diff | grep "^\+" | wc
   2360    9440   92040

If someone could help interpret the differences, I'd be very grateful. With or
without patch, insn-attrtab is a monster...

[Bug bootstrap/52391] [4.7/4.8 regression] genattrtab almost 5X slower for m68k than in 4.6 and earlier releases

[steven at gcc dot gnu.org]

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

--- Comment #14 from Steven Bosscher <steven at gcc dot gnu.org> 2012-05-06 21:40:18 UTC ---
Created attachment 27328
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27328
Remove unused sched_branch_type stuff from m68k

Patch speaks for itself.

Without patch, trunk r186902, run time for genattrtab is 9m03s.

With the m68k-specific pieces of this patch, genattrtab run time is 1m53s.

[Bug bootstrap/52391] [4.7/4.8 regression] genattrtab almost 5X slower for m68k than in 4.6 and earlier releases

[steven at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Depends on|                            |29442
         Resolution|                            |FIXED

--- Comment #15 from Steven Bosscher <steven at gcc dot gnu.org> 2012-05-07 12:44:28 UTC ---
Fixed with trunk r187234. Could also be easily back-ported to GCC 4.7 if
necessary.

The basic problems with genattrtab optimizations are not yet solved. Some
potential solutions are being discussed in bug 29442.