common block elimination

Matthew Fluet mfluet@intertrust.com
Mon, 6 Aug 2001 14:29:18 -0700 (PDT)


I wrote a dirt simple common block elimination pass, primarily to collapse
all of the overflow raising blocks into one common block.  From my CVS
checkin:  (The [] with the function header indicates an empty handler
stack.)

Rewrites

fun L_X () []
  = raise (global_Y)

to

fun L_X () []
  = L_Y' ()

and adds

fun L_Y' () []
  = raise (global_Y)

to the top of the CPS function.

The shrinker rewrites all uses of L_X to L_Y' and drops L_X.

Thus, all uncaught Overflow exceptions in a CPS function share the
same raising block.  Also works for Subscript, Size, etc.  Need a
constant lifter to get cases like

fun L_X () []
  = let
       val y = Io_0 ()
    in
       raise y
    end

I didn't bother running the benchmarks -- this should have no effect on
performance.  But, it did save about .3MB off the size of a self-compile
executable.

[mfluet@starlinux lib]$ size mlton-compile.G1.*
   text    data     bss     dec     hex filename
6396032  761692   31204 7188928  6db1c0 mlton-compile.G1.wCBE
6695840  761780   31204 7488824  724538 mlton-compile.G1.woCBE

Not sure why data went down, I only expected saving in the text section.

However, here's what has me really puzzled:

            commonBlock starting
               inferHandlers starting
               inferHandlers finished in 0.26 + 0.0 (0.0% GC)
            commonBlock finished in 9.58 + 1.73 (15% GC)

This is a dirt simple pass -- a single walk over the program looking for
the pattern above and doing the appropriate rewrite.  I also got an "Out
of memory" the first time I ran it.  Perhaps the problem is the fact that
I need to reset a property on all of the globals for each CPS function.  I
could extract the set of globals that are of type exn, which are all that
I ever need in for this pass.