MLton space pig

[Matthew Fluet]

> Thanks for checking it out.  For now I can just compile it with `-native false'
> on my laptop and by default on my desktop.  It just struck me as being goofed
> up in some way to use that much memory.  Do you have any notion what is taking
> up all the space, and what is different about this program that caused the
> problem with it?

I think I have the explaination for the space blowup.  The live-transfer
analysis is a quick (and naive) heuristic for computing which values
should be passed in registers between basic blocks.  Essentially, it's
computing the average "distance" between the last use/def of a value and
the next use of the value.  The problem is that it is computing a true
average, so for every label at which a value is live, I was computing a
list of all possible distances forward and backward, corresponding to all
possible paths.  For some reason, which isn't obvious to me from the code,
this program ended up with about 15 values live across a sequence of
blocks with lots of case transfers;  each time through a case the length
of the list grows by a factor of 6 to 10.  I'll change the heuristic a bit
so that it only stores the sum of all distances and the number of paths at
each label (instead of a list of distances for each path), which should
eliminate the problem, and also speed it up for other programs.  It means
that we'll be choosing values based on the sum of the average forward and
the average backward (which will in general be different from the average
of the sum forwards and backwards), but I don't think it will make much of
a difference.  The benchmarks I ran a while ago didn't show that this
optimization was a big win (the ratio with the optimization to without the
optimization ranged from 0.87 to 1.10), so I don't think it will hurt to
have a slightly different heuristic.  But I'll run a few benchmarks to
check it out.