[MLton] an analysis to flatten refs into tuples

Matthew Fluet fluet@cs.cornell.edu
Sat, 15 May 2004 18:32:56 -0400 (EDT)


> I am planning on implementing an SSA pass to flatten ref cells into
> tuples.

Sounds good.  From the rest of your mail, you don't seem to consider the
more general case of flattening into datatypes.  Maybe that can fall out
as a special case of considering a datatype variant's arguments as a
1-tuple?

> Obviously, implementing this requires changing the SSA type system and
> IL to add the new mutable field in tuple types and new expressions to
> get and set mutable fields.  I think that's all pretty
> straightforward.

It will also ripple into the representation pass, but pretty quickly we
get to a point where mutable fields are in the IL, so that's not a
problem.

> The local analysis checks when a ref creation corresponds
> to a tuple creation (i.e., we see val x = ref y; val z = (x, w)) and
> when a ref that is extracted is only ever assigned to (i.e. we see val
> r = #2 z; val () = r := x).

Don't you also want to allow a dereference in the project case?
Otherwise, it seems like the ref is pretty useless.

I don't know if your examples above were meant to imply that the local
analysis was _really_ local and exclusively looking for these patterns, or
if you were considering a more general, but still local analysis.

This local analysis reminds me a lot of the local ref analysis.  And, I
think you need to be concerned with the same problems of escaping refs.
Remember, in the multi-threaded case, a ref can also escape to the stack
across a non-tail call.

> The global analysis uses abstract values similar to those we use for
> whole-program constant propagation or useless analysis.

Sounds right.

> The only problem I can see is one of space safety.  By keeping the
> containing tuple alive just so we can access the field, we are
> conceivably holding on to data that would otherwise be dead.  In
> practice I don't know if this would be bad.  If it is, perhaps the
> local analysis can be made strict enough to avoid such cases.

True, it doesn't seem like a likely case.  Seems like it would be pretty
easy to modify the local analysis to rule out the refs that would extend
the def-use extent of their corresponding tuples.