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

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

[ian at airs dot com]

------- Comment #33 from ian at airs dot com  2005-10-08 05:04 -------
I found the bug report which led to the patch which is the issue in this PR. 
It starts here:
    http://gcc.gnu.org/ml/gcc-patches/2003-05/msg00796.html
and ends with this patch:
    http://gcc.gnu.org/ml/gcc-patches/2003-05/msg01358.html

I will try to recreate this problem.  It looks like we should be able to fix
this specific type of problem without losing any speed.  We should just should
not skip adding the REG_DEAD note if we don't directly set the register.  It
actually looks like the code works that way anyhow, but with luck I will be
able to recreate the problem and figure out what is really happening.


-- 


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

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

[ian at airs dot com]

------- Comment #34 from ian at airs dot com  2005-10-08 05:51 -------
I am able to recreate the problem with a hppa64-hp-hpux11 cross-compiler, in
the sense that combine does lose the REG_DEAD note when compiling the
gcc.c-torture/compile/920501-13.c test case with -O1.  In the current compiler,
the compilation succeeds.  A REG_UNUSED note is added by the
recompute_reg_usage pass, the unused register is allocated, and the allocated
register is later eliminated during the combine_stack_adjustments pass.  So it
works but the overall effect is not ideal since we allocate an unneccessary
register.

I'll see if we can avoid losing the REG_DEAD note in the combine pass.


-- 


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

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

[ian at airs dot com]

------- Comment #35 from ian at airs dot com  2005-10-10 18:19 -------
Created an attachment (id=9952)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=9952&action=view)
Patch

This patch fixes the problem in this PR, and also does not lose the REG_DEAD
note in the hppa64-hp-hpux11 test case.  I won't try to checkin until it has
been tested on hppa64-hp-hpux11.  Unfortunately, that target reportedly does
not bootstrap at the moment for unrelated reasons.


-- 


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

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

[cvs-commit at gcc dot gnu dot org]

------- Comment #36 from cvs-commit at gcc dot gnu dot org  2005-10-11 23:46 -------
Subject: Bug 13931

CVSROOT:        /cvs/gcc
Module name:    gcc
Changes by:     ian@gcc.gnu.org 2005-10-11 23:45:57

Modified files:
        gcc            : ChangeLog combine.c 

Log message:
        PR rtl-optimization/13931
        * combine.c: Revert patch of 2003-05-14, and:
        (try_combine): Only set elim_i1 and elim_i2 if the destination is
        completely killed in the appropriate insn.
        (distribute_notes): Don't skip multiple hard register test for
        elim_i1 and elim_i2.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.10141&r2=2.10142
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/combine.c.diff?cvsroot=gcc&r1=1.504&r2=1.505


-- 


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

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

[ian at airs dot com]

------- Comment #37 from ian at airs dot com  2005-10-11 23:47 -------
Fixed on mainline.  This is a minor compilation time speedup, and I don't think
there is much benefit to porting back to the release branches.


-- 

ian at airs dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|4.0.3                       |4.1.0


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

[Bug rtl-optimization/13931] [3.4/4.0/4.1 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  2005-07-22 21:13 -------
Moving to 4.0.2 pre Mark.

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


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

[Bug rtl-optimization/13931] [3.4/4.0/4.1 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  2005-07-25 02:59 -------
I think this has been fixed on the mainline:
600       .7s
1200    1.899s
1800    3.7s
2400    5.945s

This is all with checking still enabled.

-- 


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

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

[ian at airs dot com]

------- Additional Comments From ian at airs dot com  2005-09-27 05:10 -------
The code in combine is no better than it ever was.  What has changed is this patch:
    http://gcc.gnu.org/ml/gcc-patches/2005-07/msg02021.html
which causes the optimization of incrementing a memory location to be done at
expand time rather than at combine time.  Thus in 4.1 this particular test case
is no longer slow.  I will attach a new test case.

I can see some straightforward potential fixes.  Instead of doing the loop to
look for a place to put the REG_DEAD note, just set the bit in refresh_blocks to
rerun life analysis.  Or if keeping the loop seems useful (after all, the loop
is itself an attempt to control compilation time), at least limit it to looking
back just a few instructions, to avoid the quadratic behaviour.

A more complex way to fix it would be keep track of which registers are
completely set by i1 and i2.  If we find a REG_DEAD note for a register which is
set by i1 or i2, and that register no longer appears in the new i2 and i3, then
we don't care about that REG_DEAD note.

-- 


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

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

[ian at airs dot com]

------- Additional Comments From ian at airs dot com  2005-09-27 05:33 -------
Eric, your patch which caused the quadratic behaviour is here:
    http://gcc.gnu.org/ml/gcc-patches/2003-05/msg01358.html

I know this is a real long-shot, but do you have any recollection of what
problem you were solving?  That is, which test case was failing before you
checked in your patch?  And how was it failing?  The failure case looks
relatively benign to me--we think that a register lives longer than it really does.

To me that old code looks pretty much right--in fact it is one of the
suggestions I made in my previous comment.  In comment #20 you say there was a
comment in the code which indicated that it didn't always do the right thing,
and in fact you removed that comment in your patch:
-   - there are extremely rare cases (see distribute_regnotes) when a
-     REG_DEAD note is lost
But in fact that comment not only was correct but still is correct.  In some
cases, a REG_DEAD note will be lost, and in those cases the code sets a bit in
refresh_blocks and reruns life analysis.

Actually, I can see that there is a bug in the original code in some unusual
cases.  It relies on reg_set_p to see whether the register is set and therefore
the REG_DEAD note can be discarded.  But really we can only casually remove the
REG_DEAD note if the register is completely set, and reg_set_p can return true
if the register is partially set.  For example, if a STRICT_LOW_PART is used
when setting the register, we may wind up losing the REG_DEAD note incorrectly.
 I think that we can only ignore the register if dead_or_set_p returns true for it.

-- 


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

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

[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=13931