[MLton] cvs commit: rewrote x86.Block.compress to run in linear
Fri, 2 Jul 2004 23:28:10 -0400 (EDT)
> 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
> 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?