[tree-ssa] un-ssa - part 1

[Diego Novillo]

On Mon, 31 Mar 2003, Andrew Macleod wrote:

> This patch takes a first crack at the un-ssa pass. It implements a basic 
> partitioner which doesn't do anything different than we have today (ie, it 
> puts all versions of a variable into the same partition, so we still
> aren't taking care of overlapping live ranges.).
> 
Great!  However, this version imposes a rather severe performance
regression.  Compile times have gone through the roof.  These are
the timings for compiling all the files in the C front end
without the SSA->normal patch:

-----------------------------------------------------------------------------
Total compilation time for everything 		505.74 secs.
Total compilation time for tree optimizers	30.55 secs.
Total compilation time for SSA->normal		0.87 secs.

Top 5 compile times for everything
insn-attrtab.c:					56.36 secs.
insn-recog.c: 					34.22 secs.
expr.c: 					24.38 secs.
fold-const.c: 					22.84 secs.
i386.c: 					11.96 secs.

Top 5 compile times for tree optimizers
insn-recog.c:					1.78 secs.
insn-attrtab.c:					1.59 secs.
expr.c:						1.01 secs.
fold-const.c:					0.93 secs.
dwarf2out.c:					0.85 secs.

Top 5 compile times for SSA->normal
insn-recog.c: 					0.06 secs.
insn-attrtab.c: 				0.06 secs.
genautomata.c: 					0.04 secs.
dwarfout.c: 					0.04 secs.
stmt.c:						0.03 secs.
-----------------------------------------------------------------------------


These are the times after applying the SSA->normal patch:

-----------------------------------------------------------------------------
Total compilation time for everything 		915.06 secs.
Total compilation time for tree optimizers 	439.16 secs.
Total compilation time for SSA->normal		400.52 secs.

Top 5 compile times for everything
insn-attrtab.c: 				385.73 secs.
expr.c: 					48.69 secs.
insn-recog.c: 					47.83 secs.
fold-const.c: 					44.04 secs.
i386.c: 					12.22 secs.

Top 5 compile times for tree optimizers
insn-attrtab.c: 				331.43 secs.
expr.c: 					25.13 secs.
fold-const.c: 					22.2 secs.
insn-recog.c: 					15.5 secs.
c-parse.c: 					2.94 secs.

Top 5 compile times for SSA->normal
insn-attrtab.c: 				329.65 secs.
expr.c: 					23.99 secs.
fold-const.c: 					21.2 secs.
insn-recog.c: 					13.51 secs.
c-parse.c: 					2.63 secs.
-----------------------------------------------------------------------------

> It also implements the un-ssa algorithm out of Morgans book. Since everything 
> is in the same partition, it doesn't really do a lot of work just yet :-).
> 
Ouch.  A 1337% performance degradation.  And it still doesn't do
the partitioning.  On the bright side, there's plenty of room for
improvement ;)

I'm wondering if it's not something trivial.  It's late, so I
still haven't looked at the patch real close.  I'll check it out
tomorrow.


Diego.