MLton space pig

[Matthew Fluet]

On Tue, 29 May 2001, Henry Cejtin wrote:

> Are you really still summing over all paths?  Actually I don't even see how
> this is a finite set.  I.e., if I have a loop with a conditional reference
> in the body and the only definition before the loop, what do you sum?

Right, it's just an approximation.  For every label and every
psueod-register, I want two pairs of numbers:
(total length of paths forwards from label to a use of the pseudo-reg,
 total number of paths forwards from label to a use of the pseudo-reg)
and similarly backwards.

To compute forward from a label, I check to see whether or not a pair has
been registered at the label for that psuedo-reg.  If yes, then we we're
done.  If not, I register the pair (0,1) (i.e., one path of zero length)
at the label for that psuedo-reg, check to see if the pseudo-reg is used
in the basic block, and recursively compute forward from transfer labels
if it does not.  The fact that the pair (0,1) was previously registered
means that the recursion always terminates.  Similarly for computing
backwards.

If you have a situation like you describe above, it will essentially count
the length of the loop twice -- once for the path that exits the loop and
once for the path that re-enters the loop.  Variables used in the loop
will still have a shorter length between the last use or def and the next
use, so they will be kept in registers around the loop.  But this is
rarely an issue, because limit checks at loop headers prevents
pseudo-regs from being live across loops.  There is one exceptional
situation I ran into a few months ago, but it's fairly rare.