[MLton] cvs commit: rewrote x86.Block.compress to run in linear time

[Stephen Weeks]

> > Another fix would be to have copyProp turn itself off on large basic
> > blocks.
> 
> That is a possibility.

I ran a couple of compiles of HOL with

	-inline-into-main true
	-native-copy-prop {true, false}
	-native-optimize 1

Here are the summary stats:

 			  -native-copy-prop
			true		false
			----------	----------			
compile time (s)	4993		4192
code size (bytes)	25,179,782	25,293,974
run time (s)		272		278

So, turning off copy prop everywhere helps a lot at compile time
without hurting the other optimizations much.


To get a feel for what copy prop is seeing, I measured the
distribution of block sizes while compiling MLton and HOL.  Here's the
data for MLton

	blocks	statements
	------	----------
      	1	3475
      	1	2168
      	1	952
      	1	886
      	1	764
      	1	688
      	1	661
      	1	659
      	1	584
      	1	308
	233,319	<308

And the data for HOL

	blocks	statements
	------	----------
	1 	6495
	1	5114
	1	4868
	1	4569
	1	4313
	1	4172
	1	4146
	1	3200
	1	3106
	1	2651
	1	2412
	1	2229
	1	2187
	1	2025
	261	1000-2000
	242,066	<1000

So, HOL has quite a few more very large blocks than MLton.  Given the
numbers, I'd say somewhere between 100 and 1000 is a reasonable
cutoff (I'll also add a flag, -copy-prop-cutoff <n>).


As to fixing the problem, I've read through the code for copy
propagation, and while it's certainly more complicated than compress,
it doesn't look too hard to eliminate the quadratic (#statements *
#moves) aspect.  Matthew, your description makes sense

	Rather than iterating, we can maintain a set of seen copies
	and attempt to apply them to each statement.  Its a little
	more complicate because x86 MemLoc.t's correspond to memory
	addressing, in terms of other operands, so you need to abort
	the copy propagation upon encountering an instruction that
	changes the meaning of one of the src/dst operands that is
	being copied.

By abort you mean remove one of the copies from the set, not stop
completely, right?