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

[Matthew Fluet]

> 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>).

Sounds about right.

> 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.

I didn't think it would be particularly hard, just a few more fine
details.

> 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?

Correct.