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

[Stephen Weeks]

> How big are the globals in HOL?  I see that the sub-pass that tries to
> move global refs that are only used in one function has complexity:
>   #SSA functions * #SSA globals.
> This is particularly bad if most globals aren't (localizable) refs.

HOL has 283000 globals and 2083 functions at the point LocalRef is
applied.  On the other hand, MLton has 12346 globals and 1531
functions.  Yes, that could hurt.
 
> There is a simple solution using a Func.t property list holding a
> locals:Statement.t list ref.

And indeed that fixes the problem.  I implemented the fix, and
localRef for HOL has gone down to 5 seconds.

> > If we could improve the quadratic-ness of copyPropagate, we could
> > probably get most of that time back.  Any thoughts on the difficulty
> > of that?
> 
> It's definitely possible.  Essentially, for every MOV in a basic block,
> iterate over the remaining statements and replace any occurences of the
> dst operand with the src operand.  Rather than iterating, we can maintain
> a set of seen copies and attempt to apply them to each statement. 

Makes sense.

Another fix would be to have copyProp turn itself off on large basic
blocks.  If we did that, then maybe we could even turn off the hack
that sets native-optimize to 0 for main?