[Bug tree-optimization/23835] [4.1 Regression] case where gcc 4.1.0 -O3 compile takes two times longer earlier versions

[Bug tree-optimization/23835] [4.1 Regression] case where gcc 4.1.0 -O3 compile takes two times longer earlier versions

[jaffe at broad dot mit dot edu]

------- Comment #19 from jaffe at broad dot mit dot edu  2005-10-16 12:20 -------
Is further work planned on this?  Thanks.


-- 


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

[Bug tree-optimization/23835] [4.1 Regression] case where gcc 4.1.0 -O3 compile takes two times longer earlier versions

[steven at gcc dot gnu dot org]

------- Comment #20 from steven at gcc dot gnu dot org  2005-10-17 09:41 -------
Yes, further work is planned on this.  Someone just needs to figure out
what is still eating so much time.  If you can compile with -ftime-report
and report back the top 10 compile time consumers, that'd be helpful ;-)


-- 


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

[Bug tree-optimization/23835] [4.1 Regression] case where gcc 4.1.0 -O3 compile takes two times longer earlier versions

[jaffe at broad dot mit dot edu]

------- Comment #21 from jaffe at broad dot mit dot edu  2005-10-17 10:01 -------
% gcc -O3 -ftime-report -c test.ii |& grep usr | sort -t : +1 -n -r | head -10

 tree SSA incremental  :   3.19 (12%) usr   0.02 ( 2%) sys   3.18 (11%) wall   
8995 kB ( 2%) ggc
 scheduling 2          :   2.03 ( 8%) usr   0.01 ( 1%) sys   2.05 ( 7%) wall  
15312 kB ( 3%) ggc
 scheduling            :   1.52 ( 6%) usr   0.00 ( 0%) sys   1.53 ( 5%) wall   
7838 kB ( 2%) ggc
 expand                :   1.32 ( 5%) usr   0.01 ( 1%) sys   1.34 ( 5%) wall  
26717 kB ( 6%) ggc
 life analysis         :   1.30 ( 5%) usr   0.00 ( 0%) sys   1.27 ( 5%) wall   
3836 kB ( 1%) ggc
 tree alias analysis   :   1.18 ( 4%) usr   0.08 ( 9%) sys   1.23 ( 4%) wall  
13610 kB ( 3%) ggc
 parser                :   1.08 ( 4%) usr   0.18 (20%) sys   1.26 ( 4%) wall  
99497 kB (22%) ggc
 tree PTA              :   1.00 ( 4%) usr   0.00 ( 0%) sys   1.01 ( 4%) wall   
4565 kB ( 1%) ggc
 tree operand scan     :   0.82 ( 3%) usr   0.14 (16%) sys   1.03 ( 4%) wall  
10663 kB ( 2%) ggc
 integration           :   0.82 ( 3%) usr   0.02 ( 2%) sys   0.84 ( 3%) wall  
88155 kB (19%) ggc


-- 


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

[Bug tree-optimization/23835] [4.1 Regression] case where gcc 4.1.0 -O3 compile takes two times longer earlier versions

[mmitchel at gcc dot gnu dot org]

------- Comment #22 from mmitchel at gcc dot gnu dot org  2005-10-31 05:46 -------
Downgrading to P4.  I'd like to see more progress for 4.1, but it's not going
to be release-critical.


-- 

mmitchel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P2                          |P4


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

[Bug tree-optimization/23835] [4.1 Regression] case where gcc 4.1.0 -O3 compile takes two times longer earlier versions

[jaffe at broad dot mit dot edu]

------- Comment #23 from jaffe at broad dot mit dot edu  2005-10-31 10:47 -------
When is this problem likely to be resolved?  I understand that you have to 
prioritize.  I just want to understand what the prospects are.  Thanks.


-- 


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

[Bug tree-optimization/23835] [4.1/4.2 Regression] case where gcc 4.1/4.2.0 -O3 compile takes two times longer earlier versions

[steven at gcc dot gnu dot org]

------- Comment #24 from steven at gcc dot gnu dot org  2006-01-10 22:39 -------
Realistically, the prospects are that this problem won't be fixed until compile
time gets on the GCC developers' radar for real.  The next release always
promises  to be faster, but usually turns out to be disappointingly slow in the
end.

Note that in your case, there really is only one real bug.  The other slow
passes are inherently slow for very large functions.  The top 3 slow passes of
your latest time report was:

 tree SSA incremental  :   3.19 (12%) usr
 scheduling 2          :   2.03 ( 8%) usr
 scheduling            :   1.52 ( 6%) usr

The tree SSA incremental bit is non-linear behavior when computing dominance
frontiers (inevitable) plus non-linear behavior due to massive bitmap abuse. 
This incremental update tries to work on portions of the CFG, but in practice
it almost always works on the whole function, so you end up doing far more work
than strictly necessary.  What's required to fix this is a region based
compilation model such that the SSA updater can work on dirty regions (i.e.
regions where an update is needed) without worrying about the other regions.  I
don't think this will be fixed any time soon :-(

As for the scheduler, well, list scheduling is just a quadratic algorithm:
O(n_insns_to_schedule^2) where n_insns_to_schedule is the number of insns in
the region or trace that you're scheduling.  This is one of the reasons why no
compiler schedules whole functions at once: You have to split them up to keep
compile times reasonable.  The fact that scheduling got slower for IA-64 has
two reasons.  First, basic blocks are typically larger for IA-64 in GCC 4.x
than in GCC 3.x, and typically GCC 4.x can find longer traces than GCC 3.x, so
your n_insns_to_schedule is larger (I measured this on ia64-linux).  Second,
the scheduler model for IA-64 is just incredibly complicated, and a significant
amount of time is simply lost there because the IA-64 automaton is _huge_.


-- 


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

[Bug tree-optimization/23835] [4.1/4.2 Regression] case where gcc 4.1/4.2.0 -O3 compile takes two times longer earlier versions

[mmitchel at gcc dot gnu dot org]

-- 

mmitchel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.1.0                       |4.1.1


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

[Bug tree-optimization/23835] [4.1/4.2 Regression] case where gcc 4.1/4.2.0 -O3 compile takes two times longer earlier versions

[mmitchel at gcc dot gnu dot org]

------- Comment #25 from mmitchel at gcc dot gnu dot org  2006-05-25 02:35 -------
Will not be fixed in 4.1.1; adjust target milestone to 4.1.2.


-- 

mmitchel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.1.1                       |4.1.2


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

[Bug tree-optimization/23835] [4.1/4.2/4.3 Regression] case where gcc 4.1/4.2/4.3.0 -O3 compile takes two times longer earlier versions

[mmitchel at gcc dot gnu dot org]

-- 

mmitchel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.1.2                       |4.1.3


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

[Bug tree-optimization/23835] [4.1/4.2/4.3 Regression] case where gcc 4.1/4.2/4.3.0 -O3 compile takes two times longer earlier versions

[steven at gcc dot gnu dot org]

------- Comment #26 from steven at gcc dot gnu dot org  2007-12-18 20:09 -------
Bring back on the radar for the release manager.
New timings would be much appreciated.  Anyone?


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P4                          |P3


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

[Bug tree-optimization/23835] [4.1/4.2/4.3 Regression] case where gcc 4.1/4.2/4.3.0 -O3 compile takes two times longer earlier versions

[ubizjak at gmail dot com]

------- Comment #27 from ubizjak at gmail dot com  2007-12-19 22:02 -------
(In reply to comment #26)
> Bring back on the radar for the release manager.
> New timings would be much appreciated.  Anyone?

Attached preprocessed source doesn't compile out-of-the-box with gcc-4.3.


-- 


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

[Bug tree-optimization/23835] [4.2/4.3/4.4 Regression] case where gcc 4.1/4.2/4.3/4.4.0 -O3 compile takes two times longer earlier versions

[jsm28 at gcc dot gnu dot org]

------- Comment #29 from jsm28 at gcc dot gnu dot org  2008-07-04 20:03 -------
Closing 4.1 branch.


-- 

jsm28 at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.1.3                       |4.2.5


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

[Bug tree-optimization/23835] [4.3/4.4/4.5 Regression] -O3 compile takes two times longer

[jsm28 at gcc dot gnu dot org]

------- Comment #30 from jsm28 at gcc dot gnu dot org  2009-03-31 18:56 -------
Closing 4.2 branch.


-- 

jsm28 at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[4.2/4.3/4.4/4.5 Regression]|[4.3/4.4/4.5 Regression] -O3
                   |-O3 compile takes two times |compile takes two times
                   |longer                      |longer
   Target Milestone|4.2.5                       |4.3.4


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

[Bug tree-optimization/23835] [4.3/4.4/4.5 Regression] -O3 compile takes two times longer

[rguenth at gcc dot gnu dot org]

------- Comment #31 from rguenth at gcc dot gnu dot org  2009-08-04 12:26 -------
GCC 4.3.4 is being released, adjusting target milestone.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.3.4                       |4.3.5


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

[Bug tree-optimization/23835] [4.3/4.4/4.5/4.6 Regression] -O3 compile takes two times longer

[rguenth at gcc dot gnu dot org]

------- Comment #32 from rguenth at gcc dot gnu dot org  2010-05-22 18:10 -------
GCC 4.3.5 is being released, adjusting target milestone.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.3.5                       |4.3.6


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

[Bug tree-optimization/23835] [4.1 Regression] case where gcc 4.1.0 -O3 compile takes two times longer earlier versions

[jaffe at broad dot mit dot edu]

------- Additional Comments From jaffe at broad dot mit dot edu  2005-09-28 09:45 -------
That's an improvement!

Still, here are the stats again, updated for 4.1.0:

Compile time in seconds for test.ii:

         -O0     -O1    -O2     -O3

3.4.3   5.659   9.515  13.811  14.779
4.1.0   5.829  16.398  24.618  27.066

% gcc -v
Using built-in specs.
Target: ia64-unknown-linux-gnu
Configured with: ../configure --prefix=/wga1/gcc --enable-checking=release
Thread model: posix
gcc version 4.1.0 20050926 (experimental)



-- 


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

[Bug tree-optimization/23835] [4.1 Regression] case where gcc 4.1.0 -O3 compile takes two times longer earlier versions

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-09-15 16:50 -------
Looking at the numbers for -fno-inline, I noticed it drops back down to the 4.0.0 numbers.

-- 


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

[Bug tree-optimization/23835] [4.1 Regression] case where gcc 4.1.0 -O3 compile takes two times longer earlier versions

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-09-15 16:49 -------
on x86_64, there is only about 2x compile time increase at -O3.  Though it is much faster now, than it 
was a couple of days ago.

-- 


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

[Bug tree-optimization/23835] [4.1 Regression] case where gcc 4.1.0 -O3 compile takes two times longer earlier versions

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-09-15 16:40 -------
This is much better now but still more improvements can happen.  I am going to unassign Daniel for 
now as the aliasing pass takes much less now.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|dberlin 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=23835

[Bug tree-optimization/23835] [4.1 Regression] case where gcc 4.1.0 -O3 compile takes two times longer earlier versions

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2005-09-15 01:28 -------
Subject: Bug 23835

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	dberlin@gcc.gnu.org	2005-09-15 01:28:14

Modified files:
	gcc            : ChangeLog tree-ssa-alias.c 

Log message:
	2005-09-14  Daniel Berlin  <dberlin@dberlin.org>
	
	PR tree-optimization/23835
	* tree-ssa-alias.c (sort_pointers_by_pt_vars): New function.
	(create_name_tags): Rewrite to be not O(num_ssa_names^2).

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.9957&r2=2.9958
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-ssa-alias.c.diff?cvsroot=gcc&r1=2.109&r2=2.110



-- 


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