[Bug optimization/13931] combiner much slower on big functions

[Bug optimization/13931] combiner much slower on big functions

[bonzini at gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |compile-time-hog


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

[Bug optimization/13931] New: combiner much slower on big functions

[bonzini at gnu dot org]

The combiner jumped up from 3.3.2's 8% to 3.4/3.5's 56% in the attached function. 
 
No. of lines in block            Run time 
600                                      0.36 
1200				    2.33 
1800                                    5.77 
2400                                   10.56 
 
There seems to be a quadratic bottleneck in combine.  distribute_notes has a loop that 
goes over all previous instructions.  distribute_notes calls reg_set_p, which calls set_of, 
which calls note_stores, which calls set_of_1, which calls reg_overlap_mentioned_p, 
which calls refers_to_regno_p... and all these show up quite at the top of the profile. 
 
# of instructions       function 
224,203,200  rtlanal.c:refers_to_regno_p 
150,433,200  rtlanal.c:reg_overlap_mentioned_p 
 75,561,636  rtlanal.c:note_stores 
 56,985,600  rtlanal.c:reg_referenced_p 
 49,576,316  regrename.c:validate_value_data 
 40,026,779  rtl.c:rtx_equal_p 
 28,740,658  flow.c:mark_set_1 
 27,562,800  combine.c:distribute_notes 
 25,928,400  rtlanal.c:set_of_1 
 15,840,000  rtlanal.c:reg_set_p 
 
This might be a duplicate of PR13775.

-- 
           Summary: combiner much slower on big functions
           Product: gcc
           Version: 3.4.0
            Status: UNCONFIRMED
          Severity: critical
          Priority: P2
         Component: optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: bonzini at gnu dot org
                CC: gcc-bugs at gcc dot gnu dot org
 GCC build triplet: i686-pc-linux-gnu
  GCC host triplet: i686-pc-linux-gnu
GCC target triplet: i686-pc-linux-gnu


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

[Bug optimization/13931] combiner much slower on big functions

[bonzini at gnu dot org]

------- Additional Comments From bonzini at gnu dot org  2004-01-30 12:42 -------
Created an attachment (id=5617)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=5617&action=view)
testcase


-- 


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

[Bug optimization/13931] [3.4/3.5 Regression] combiner much slower on big functions

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-01-30 17:23 -------
Confirmed, on i686, combine takes most of the time, while on powerpc:

 scheduling            :  22.06 (21%) usr   1.10 (34%) sys  49.98 (19%) wall
 rename registers      :  46.87 (44%) usr   0.38 (12%) sys 122.39 (47%) wall
 scheduling 2          :  20.88 (20%) usr   0.85 (27%) sys  55.33 (21%) wall 
Takes most of the time.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2004-01-30 17:23:26
               date|                            |
            Summary|combiner much slower on big |[3.4/3.5 Regression]
                   |functions                   |combiner much slower on big
                   |                            |functions
   Target Milestone|---                         |3.4.0


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

[Bug optimization/13931] [3.4/3.5 Regression] combiner much slower on big basic blocks

[bonzini at gnu dot org]

------- Additional Comments From bonzini at gnu dot org  2004-01-30 19:26 -------
Ah, is it a regression on PPC?

-- 


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

[Bug optimization/13931] [3.4/3.5 Regression] combiner much slower on big basic blocks

[bonzini at gnu dot org]

------- Additional Comments From bonzini at gnu dot org  2004-01-30 19:24 -------
It is probably because on powerpc the combination attempts fail, while on i686 
they succeed (there is an increment-a-memory-location instruction).  Gee, the 
timings for PPC are even worse. :-(

As far as the combiner is concerned, it seems to be worst case quadratic in the 
number of succeeded combinations in a basic block.  Maybe it is possible to 
just propagate notes just 50 or 100 instruction behind in the basic block after 
a succeeded combination?  Or maybe it screws up the liveness information?

It may also be ok to simply rerun data-flow analysis after combine (instead of 
doing distribute_notes) after 50 or 100 succeeded combinations.

(I don't have a tree here, otherwise I'd try out these two possibilities).

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[3.4/3.5 Regression]        |[3.4/3.5 Regression]
                   |combiner much slower on big |combiner much slower on big
                   |functions                   |basic blocks


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

[Bug optimization/13931] [3.4/3.5 Regression] combiner much slower on big basic blocks

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-02-04 16:39 -------
Actually the regression for PPC-darwin is only for darwin and not PPC linux and is filed in a different PR.

-- 


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

[Bug optimization/13931] [3.4/3.5 Regression] combiner much slower on big basic blocks

[mmitchel at gcc dot gnu dot org]

------- Additional Comments From mmitchel at gcc dot gnu dot org  2004-03-08 23:03 -------
This needs to be fixed, but it would be too risky to try before 3.4.0.

Postponed until 3.4.1.  

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|3.4.0                       |3.4.1


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

[Bug rtl-optimization/13931] [3.4/3.5 Regression] combiner much slower on big basic blocks

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-06-07 03:24 -------
I will take a look at this next week, it might be already helped by the merge of the tree-ssa but I doubt 
that though.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pinskia at gcc dot gnu dot
                   |                            |org


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

[Bug rtl-optimization/13931] [3.3/3.4/3.5 Regression] combiner much slower on big basic blocks

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-06-07 19:08 -------
Actually look into this there is a compile time regression in 3.3.3 also from 3.2.3:
tin:~/src/gnu/gcctest>time gcc -S -O1 pr13931.c
2.050u 0.040s 0:02.15 97.2%     0+0k 0+0io 942pf+0w
tin:~/src/gnu/gcctest>time ~/ia32_linux_gcc3_2/bin/gcc -S -O1 pr13931.c
0.350u 0.040s 0:00.45 86.6%     0+0k 0+0io 687pf+0w
tin:~/src/gnu/gcctest>time ~/ia32_linux_gcc3_3/bin/gcc -S -O1 pr13931.c
1.700u 0.030s 0:01.77 97.7%     0+0k 0+0io 708pf+0w
tin:~/src/gnu/gcctest>time ~/ia32_linux_gcc3_4/bin/gcc -S -O1 pr13931.c
1.790u 0.030s 0:01.86 97.8%     0+0k 0+0io 734pf+0w

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|                            |3.3.3 3.4.0 3.5.0
      Known to work|                            |3.2.3
            Summary|[3.4/3.5 Regression]        |[3.3/3.4/3.5 Regression]
                   |combiner much slower on big |combiner much slower on big
                   |basic blocks                |basic blocks


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

[Bug rtl-optimization/13931] [3.3/3.4/3.5 Regression] combiner much slower on big basic blocks

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-06-07 20:44 -------
For powerpc-apple-darwin, most of the time is being taking in get_cse_reg_info.  But I will note that 
powerpc-apple-darwin is now faster than even the 3.3 release or even Apple's 3.3

Hmm I noticed something, for 3.3.1 20030707 on i686-pc-linux-gnu, the speed of the compile is fast 
but on a released version of 3.3.3 it is just as slow as 3.4.0, so there was a patch between them which 
made this slower.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|3.2.3                       |3.2.3 3.3


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

[Bug rtl-optimization/13931] [3.3/3.4/3.5 Regression] combiner much slower on big basic blocks

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-06-07 20:53 -------
If someone could find the patch which make this slower I could do something about it.
There has only been one patch to combine after 3.3 which might have caused this:

2003-10-06  Eric Botcazou  <ebotcazou@libertysurf.fr>

        PR optimization/11637
        * combine.c (adjust_for_new_dest): New function to adjust the
        notes and LOG_LINKS when the dest of an insn has changed.
        (try_combine): Use it when deleting the first insn of a two-insn
        parallel or splitting a two-load parallel.


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ebotcazou at gcc dot gnu dot
                   |                            |org


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

[Bug rtl-optimization/13931] [3.3/3.4/3.5 Regression] combiner much slower on big basic blocks

[ebotcazou at gcc dot gnu dot org]

------- Additional Comments From ebotcazou at gcc dot gnu dot org  2004-06-07 21:12 -------
Does reverting it fix the problem?  If so, please assign the PR to me.


-- 


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

[Bug rtl-optimization/13931] [3.3/3.4/3.5 Regression] combiner much slower on big basic blocks

[mmitchel at gcc dot gnu dot org]

------- Additional Comments From mmitchel at gcc dot gnu dot org  2004-06-18 23:47 -------
Postponed until GCC 3.4.2.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|3.4.1                       |3.4.2


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

[Bug rtl-optimization/13931] [3.3/3.4/3.5 Regression] combiner much slower on big basic blocks

[mmitchel at gcc dot gnu dot org]

------- Additional Comments From mmitchel at gcc dot gnu dot org  2004-08-29 18:47 -------
Postponed until GCC 3.4.3.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|3.4.2                       |3.4.3


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

[Bug rtl-optimization/13931] [3.3/3.4/4.0 Regression] combiner much slower on big basic blocks

[mmitchel at gcc dot gnu dot org]

------- Additional Comments From mmitchel at gcc dot gnu dot org  2004-10-30 20:02 -------
Postponed until GCC 3.4.4.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|3.4.3                       |3.4.4


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

[Bug rtl-optimization/13931] [3.3/3.4/4.0 Regression] combiner much slower on big basic blocks

[mmitchel at gcc dot gnu dot org]

------- Additional Comments From mmitchel at gcc dot gnu dot org  2004-10-30 20:02 -------
Postponed until GCC 3.4.4.

-- 


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

[Bug rtl-optimization/13931] [3.3/3.4/4.0 Regression] combiner much slower on big basic blocks

[ebotcazou at gcc dot gnu dot org]

------- Additional Comments From ebotcazou at gcc dot gnu dot org  2004-11-15 12:11 -------
Investigating.


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


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

[Bug rtl-optimization/13931] [3.3/3.4/4.0 Regression] combiner much slower on big basic blocks

[ebotcazou at gcc dot gnu dot org]

------- Additional Comments From ebotcazou at gcc dot gnu dot org  2004-11-16 08:05 -------
> There has only been one patch to combine after 3.3 which might have caused
> this:
> 
> 2003-10-06  Eric Botcazou  <ebotcazou@libertysurf.fr>
> 
>         PR optimization/11637
>         * combine.c (adjust_for_new_dest): New function to adjust the
>         notes and LOG_LINKS when the dest of an insn has changed.
>         (try_combine): Use it when deleting the first insn of a two-insn
>         parallel or splitting a two-load parallel.

No, this patch is not responsible for the quadratic behaviour, which is still
present as of today on AMD64: reverting it doesn't change anything on mainline.
Digging a little further would have showed that the patch only adds a call to
distribute_links, not distribute_notes, which contains this comment:

	 Note that this correctly handles the link that used to point from
	 I3 to I2.  Also note that not much searching is typically done here
	 since most links don't point very far away.  */


-- 


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

[Bug rtl-optimization/13931] [3.3/3.4/4.0 Regression] combiner much slower on big basic blocks

[ebotcazou at gcc dot gnu dot org]

------- Additional Comments From ebotcazou at gcc dot gnu dot org  2004-11-16 08:21 -------
And 5 minutes of additional work would have been sufficient to spot the obvious
culprit:

2003-05-14  Eric Christopher  <echristo@redhat.com>

	* combine.c: Fix header comments.
	(distribute_notes): Remove usage of elim_i1, elim_i2. Propagate
	to all calls and prototype.

containing most notably:

@@ -12550,19 +12530,14 @@ reg_bitfield_target_p (x, body)
    as appropriate.  I3 and I2 are the insns resulting from the combination
    insns including FROM (I2 may be zero).
 
-   ELIM_I2 and ELIM_I1 are either zero or registers that we know will
-   not need REG_DEAD notes because they are being substituted for.  This
-   saves searching in the most common cases.
-
    Each note in the list is either ignored or placed on some insns, depending
    on the type of note.  */

Reverting it makes the quadratic behaviour vanish on mainline.

It was backported between 3.3.2 and 3.3.3 by:

2003-12-16  Zack Weinberg  <zack@codesourcery.com>

	Backport the following patches from mainline.
        [...]

    2003-05-14  Eric Christopher  <echristo@redhat.com>

	* combine.c: Fix header comments.
	(distribute_notes): Remove usage of elim_i1, elim_i2. Propagate
	to all calls and prototype.


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|3.2.3 3.3                   |3.2.3 3.3 3.3.2


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

[Bug rtl-optimization/13931] [3.3/3.4/4.0 Regression] combiner much slower on big basic blocks

[ebotcazou at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |echristo at redhat dot com
         AssignedTo|ebotcazou at gcc dot gnu dot|unassigned at gcc dot gnu
                   |org                         |dot org
             Status|ASSIGNED                    |NEW


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

[Bug rtl-optimization/13931] [3.3/3.4/4.0 Regression] combiner much slower on big basic blocks

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-11-18 20:46 -------
Note on the mainline on PPC-darwin we are about twice as fast 1.5 seconds compared to 3.3 (3.2 
seconds).

-- 


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

[Bug rtl-optimization/13931] [3.3/3.4/4.0 Regression] combiner much slower on big basic blocks

[echristo at redhat dot com]

------- Additional Comments From echristo at redhat dot com  2004-12-07 19:54 -------
The patch was put in to stop erroneous REG_DEAD notes from being created where
they shouldn't IIRC. Now, we may be able to rerun cfg as Paolo suggests, but I
don't know for certain. Unless we can prove that new speedups do the right thing
all the time I don't think we can put them back in - there was even a note in
the old code that we didn't always do the right thing.

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


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

[Bug rtl-optimization/13931] [3.3/3.4/4.0 Regression] combiner much slower on big basic blocks

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2004-12-22 19:23 -------
Perhaps someone can give an update on this bug? 
 
 

-- 


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

[Bug rtl-optimization/13931] [3.3/3.4/4.0 Regression] combiner much slower on big basic blocks

[echristo at redhat dot com]

------- Additional Comments From echristo at redhat dot com  2004-12-22 19:48 -------
I thought I did on the 7th. I'm not sure there's anything we can do about this.
The behavior is correct and the previous behavior was proved to be not correct.
If someone has an idea that's guaranteed to be correct in all cases I'm willing
to try to implement it though.

-- 


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