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.