[MLton] profiling and tail calls

Stephen Weeks MLton@mlton.org
Tue, 16 Nov 2004 12:30:24 -0800


> Is it true or false that -profile XYZ can change the tail-recursive
> nature of a program?

Yes.  :-)

Seriously, to err on the safe side, I would have to say true.
Although, I would think the optimizer should get it.

Here's how it works.  If profiling is on, the front end (elaborator)
inserts Enter/Leave statements into the source program.  For example,

  fun f n = if n = 0 then 0 else 1 + f (n - 1)

becomes

  fun f n = 
     let
        val () = Enter "f"
        val res = (if n = 0 then 0 else 1 + f (n - 1))
                  handle e => (Leave "f"; raise e)
        val () = Leave "f"
     in 
        res
     end
          
Then the Ssa shrinker has an optimization that notices when the only
operations that make a call nontail are profiling operations, and if
so, moves them before the call.

So, I can't think of a case that would slip through.  But I'm a long
ways from a proof.

> Similarly, can -profile XYZ not change the tail-recursive nature of
> the source program, but inhibit optimizations that may have improved
> the number of tail calls.

Does my above explanation answer this question?