[MLton] cvs commit: rewrote x86.Block.compress to run in linear
time
Stephen Weeks
MLton@mlton.org
Fri, 2 Jul 2004 15:58:19 -0700
> > 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?