[MLton] stack-allocated references

[Matthew Fluet]

>> MLton will eliminate a reference cell that doesn't outlive its
>> scope.  A common idiom that is picked up is the following:
> 
>> fun mapAndLength f l =
>>    let val r = ref 0
>>        val l' = map (fn x => (r := !r + 1; f x) l
>>    in
>>      (l', !r)
>>    end
> 
>> The use of the reference is completely local to the function (after 
>> inlining the code for map) and MLton will eliminate heap allocated 
>> reference cell in favor of a stack local integer holding the length.
> 
> Does this happen if the ref is passed into another non-inlined
> function? Or only if it is used solely in the function in which it is
> declared (after inlining, as you mention).

Only if it used solely in the function in which it is declared.  Here 
"function" means the SSA IL functions in the program when the 
optimization is applied.

Also, I should point out that the "ref" actually gets turned into an 
"immutable" SSA variable, which then gets turned into a stack slot.  A 
better way of thinking about the optimization is that it turns:

fun foo l =
   let val r = ref 0
       fun loop ([],acc) = (!r, acc)
         | loop (h::t,acc) = (r := !r + 1
                              ; loop (t, (h+1)::acc))
   in loop (l,[])
   end

into

fun foo l =
   let fun loop (r,[],acc) = (r, acc)
         | loop (r,h::t,acc) = loop (r + 1,t, (h+1)::acc)
   in loop (0,l,[])
   end

Note that it just turned r into another accumulating parameter.

> I ask because I am looking at implementing "stacklets" as part of the
> Cheng-Blelloch collector. The idea is that the stack is a list of
> stacklets (of bounded size) linked together, and only the topmost one
> is mutable. Immutable stacklets can be processed during the
> collection, without a write barrier, and the topmost stacklet can be
> processed in bounded time when the collector is turned off (see
> Cheng's thesis for a fuller description).

I assume that an immutable stacklet can become mutable again when it 
becomes the top-most stacklet.

MLton should work fine with this scheme; MLton only mutates the top-most 
stack frame.  Any mutable data shared between stack frames must be in 
the heap.

> If a stack-allocated ref can be passed into a function, then
> non-topmost stacklets are not immutable and this scheme doesn't work.