Out OF SSA Rewrite Summary

[Andrew MacLeod]

This is a set of patches which constitute the out of ssa rewrite project
I've been working on for the past few months, and represents the sum
effort of the out-of-ssa-the-sequel branch. I've condensed all the work
down into 5 patch groups, and produced a combined patch for each :

- The original list of coalesceable ssa_name pairs was a linear list.
Most of the time that was OK, but some pathological cases caused
significant slowdown. This patch switches the coalesce list to a hash
table.  

- A cleanup patch which removes a bunch of functions and data structures
which are no longer necessary when we drop support for -fno-tree-lrs (no
live range splitting), amongst other things. There were a number of
abstractions in the data structures which are not needed, and simply
convoluted the code.

- The live Range routines were also rewritten.  Previously live on entry
was calculated on a per ssa_name basis, and live on exit on a per-block
basis.  This patch switches to a per-block basis for both.  Most of this
patch was also previously published in
http://gcc.gnu.org/ml/gcc-patches/2006-08/msg00895.html

- I originally wasn't going to bother with TER since it has a limited
life now, but it will remain in the compiler for 4.3 at least. There are
a few PRs open against it, as well as a couple of speed issues, so TER
has been significantly overhauled.  It has been broken out to its own
file (tree-ssa-ter.c) and is both faster and significantly easier to
understand.  It also catches a few more cases than it use to, addressing
some open bugzilla cases.  A portion of this work was previously
published in http://gcc.gnu.org/ml/gcc-patches/2006-08/msg00896.html

- Finally, the coalescer rewrite. This is a very large patch.  The
coalescing work has been removed from tree-ssa-live.c and
tree-outof-ssa.c and moved into tree-ssa-coalesce.c.  Its also been
completely overhauled to be leaner, meaner, and faster.  Its also prep
work for the ssa-name pressure reduction project which is next on my
list.

I'll publish each of the 5 patches in a separate note. They have all
been bootstrapped and regression tested on i686-pc-linux-gnu.  There is
one current regression caused by the new TER, but I will go into that in
the TER note. (Its uncovered a bug in the expander I have to look into)

Performance results... 

As the branch was developed, and each individual change went in, I was
carefully monitoring the performance results over a series of
troublesome test cases. I won't publish individual results here, just
the cumulative result of all the changes.

times are listed as   ssa->normal time / total user compile time
3.0Ghz P4 with 1 GB ram running FC4.

					Mainline	New out of ssa applied

cc1test - all gcc .i files  -O2		 1.96/240	1.74/240
bug2.c (PR 28071) -O2			27.59/155.22	0.16/128.49
bug2.c (PR 28071) -O3			33.02/ 94.48	4.00/ 66.03
tramp3d	-O2				 0.68/116.98	0.43/111.95
cpgram.ii (PR 15855) -O2		 0.21/ 52.25	0.20/ 51.47
all.i (PR 26854) -O2 nopre nofre nortl 312.64/399.35   34.30/120.87

bug2.c at -O3 still takes 4 seconds which, although a big improvement,
isnt ideal yet.  That will be address during the ssa-name pressure
reduction work. The reason it takes a while is that there are about
39,000 basic blocks with almost 1000 ssa_names live on entry to those
blocks. Most of the 4 seconds is spent doing conflict graph resolution
on this obscene situation.  This testcase also demonstrates why a live
range reduction mechanism would be useful :-)

Same thing holds true for the remaining time in all.i.  Its all massive
interference graph issues due to incredibly large numbers of live
ssa_names.

Anyway, as you can see, timings are generally pretty improved.

I don't plan to check this in until I resolve the expand problem TER has
uncovered, so there is a little time for anyone to comment on this, or
ask me to hold off for whatever reason. These changes are very localized
to the out of ssa section of the compiler. I will also make another pass
over each patch as I apply it to look for missed comments/spelling and
such. I know there are a couple of such instances.

The 5 patches will follow shortly...

Andrew