ssa restore
Matthew Fluet
Matthew Fluet <fluet@CS.Cornell.EDU>
Thu, 6 Dec 2001 12:59:45 -0500 (EST)
> I checked in an ssa restoration pass and ported localRef to use it. See
> the comments in the file for more details.
> The huge code-size increases in lexgen and mlyacc are due to the way
> wrappers are added along with the fact that the restore pass will rewrite
> NonTail calls to push and pop handlers. I'm thinking about a fix for it.
I checked in a fix for the code-size explosion.
See the commit log for more details on the "how".
It solves most of the space problem in lexgen, but not all of it.
The previous version had:
MLton0 -- mlton -drop-pass localRef
MLton1 -- mlton
compile time
benchmark MLton0 MLton1
hamlet 52.85 55.68
lexgen 5.37 5.86
mlyacc 20.93 25.10
size
benchmark MLton0 MLton1
hamlet 1,496,651 1,502,795
lexgen 151,048 168,568
mlyacc 546,264 616,984
The new versions has:
MLton0 -- mlton -drop-pass localRef
MLton1 -- mlton
compile time
benchmark MLton0 MLton1
hamlet 50.99 55.75
lexgen 5.24 5.53
mlyacc 20.91 22.75
size
benchmark MLton0 MLton1
hamlet 1,496,571 1,499,915
lexgen 150,744 157,416
mlyacc 546,728 579,912
(Also, the hashing doesn't seem to be hurting compile times; when there is
significant sharing to be had, it probably helps by reducing program
size.)
As to why there is still a code increase, consider:
val f : unit -> int
val ps : string -> unit
val func = ref ""
val n = (if Word.andb(f (),0wx1) = 0wx0
then (func := "fib";
if Word.andb(f (),0wx1) = 0wx0
then fib 20
else fib 10)
else (func := "tak";
tak (1,2,3)))
handle _ => (ps (!func); 0)
Under the old version, each of the non-tail calls at fib 20, fib 10, and
tak (1,2,3) would get their own new handler that routed the localized func
to the handler. Under the new version, fib 20 and fib 10 share the new
handler. Unfortunately, whereas the original program had one HandlerPush
for the program, the transformed program has 3 HandlerPush's, one at each
non-tail call. Likewise, the original program had one continuation for
each of the non-tail calls, but the transformed program requires one for
tak(1,2,3) (to pop it's handler) and one for fib 20 and fib 10 (to pop
their handler).
Because we are doing a completely local transformation,
nothing recognizes that the handler pushes for fib 20 and fib 10 are the
same and could be hoisted to a single handler push that is shared by both
calls. Something to keep in mind for the exceptions paper.
Something else to keep in mind for the exceptions paper:
without needing to worry about HandlerPush/Pops, I would just have
rewriteTransfer map route over all the labels. Now, with the old version
of route, this would have given each nontail call at a handler with phi
arguments a different route block. Nothing in the simplification pipeline
would eliminate these alpha-equivalent blocks, so implementHandlers would
probably do something costly, particularly in terms of space.
This suggests that we need to be careful at points that rewrite handler
labels. The current version of route is "good" in the sense that when two
rewritten handlers are different, they really are (semantically)
different.