Hunting the Elusive ‘tail’ Opcode in F#

Awhile back I wrote a post about tail-call optimizations that the F# compiler used to eliminate stack overflows. Brian McNamera commented about another optimization that I didn’t illustrate – the ‘tail’ opcode that appears when mutually-recursive and indirectly-recursive functions are encountered. Tail-call optimization is one of the really powerful features of F#, so I really wanted to see how this worked under the hood.

The first thing we need is a pair of mutually-recursive functions.  The easiest (laziest? :)) way to do this is to write one function (e.g. f1) and duplicate its implementation as another name (e.g. f2):

// Hunting for tail calls

 

// 6.17.09

 

 

 

open

System

 

 

 

let

rec sum1 n acc =

 

    match n with

 

    | 0 -> acc

 

    | _ -> sum2 (n-1) (acc+n)

 

 

 

and

sum2 n acc =

 

    match n with

 

    | 0 -> acc

 

    | _ -> sum1 (n-1) (acc+n)

 

   

 

let

sum n = sum1 n 0

 

 

 

let

main () =

 

   Console.WriteLine(“Hello”)

 

   printfn “%A” (sum 100000)

 

   Console.WriteLine(“Press Enter to continue…”)

 

   Console.ReadLine() |> ignore

 

   

 

main ()

 

After compiling this, I popped open the resulting executable in Reflector. Of course I wasn’t going to find the ‘tail’ opcode by looking at the C# – I needed to disassemble the IL. I hunted and hunted for the ‘tail’ opcode, but couldn’t find it!  Every call to f1 from f2 (and f2 from f1) used the stack to pass around n and acc. Even stranger – this is the first F# program I’d written using Visual Studio 2010, and I could have sworn that I’d done the same thing with F# in Visual Studio 2008 a couple months ago.

After building the project again, I noticed the command-line arguments passed to fsc:

—— Build started: Project: HuntingTailcalls, Configuration: Debug Any CPU ——

 

              C:\Program Files\Microsoft F#\v4.0\fsc.exe -o:obj\Debug\HuntingTailcalls.exe -g –debug:full –noframework –define:DEBUG –define:TRACE –optimize- –tailcalls- -r:”C:\Program Files\Microsoft F#\v4.0\FSharp.Core.dll” -r:”C:\Program Files\Reference Assemblies\Microsoft\Framework\.NETFramework\v4.0\mscorlib.dll” -r:”C:\Program Files\Reference Assemblies\Microsoft\Framework\.NETFramework\v4.0\System.Core.dll” -r:”C:\Program Files\Reference Assemblies\Microsoft\Framework\.NETFramework\v4.0\System.dll” –target:exe –warn:3 –warnaserror:76 –vserrors –utf8output –fullpaths –flaterrors Program.fs

 

“—tailcalls-“? Somehow tailcalls are being turned off. Maybe there’s something in the project settings that are disabling the tailcalls? Ah-ha! The checkbox was unchecked :)

image

After poking around a bit more, I discovered that by default the “Generate tail calls” box is unchecked fo Debug mode, and checked by default for Release mode.  Hmmm, interesting.

After switching to Release mode, I rebuild the project and opened the .exe in Reflector.  Here we go! There’s the elusive ‘tail’ opcode:

.method

public static int32 sum1(int32 n, int32 acc) cil managed

 

{

 

    .maxstack 5

 

    L_0000: ldarg.0

 

    L_0001: switch (L_0019)

 

    L_000a: nop

 

    L_000b: ldarg.0

 

    L_000c: ldc.i4.1

 

    L_000d: sub

 

    L_000e: ldarg.1

 

    L_000f: ldarg.0

 

    L_0010: add

 

    L_0011: tail

 

    L_0013: call int32 Program::sum2(int32, int32)

 

    L_0018: ret

 

    L_0019: ldarg.1

 

    L_001a: ret

 

}

(The IL code for sum2 looks identical.) Interestingly enough, the C# code from Reflector looks exactly the same between Debug and Release modes (with and without tail calls) – C# doesn’t have the capability to make tail calls.

Well, there you have it! We finally found the elusive ‘tail’ opcode.

That being said, be sure to keep this in mind – the default settings of Visual Studio 2010 for F# development are drastically different between Debug and Release mode.  Bugs might crop up in Debug mode (e.g. StackOverflowExceptions) that don’t rear their heads in Release mode.

I think the motivation for this is that using tail calls severely limit the usefulness of the Visual Studio debugger since it relies on traversing the stack frame (that the tail opcode destroys) to display debugging information.

For example, without tailcall optimizations setting a breakpoint on sum1 looks like this:

image

image

The callstack shows some useful debugging information, specifically the values of n and the accumulator.

However, if we enable tailcall optimization, this breaks down after running through the breakpoint 10 times, each time it shows one line with different information:

image

image

… You get the idea.

Hope that sheds some light on tailcall optimization, as well as some of the new features of F# in Visual Studio 2010!


You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

AddThis Social Bookmark Button

One Response to “Hunting the Elusive ‘tail’ Opcode in F#”

  1. Be sure to check out the blog below for more detail on tail calls on .Net 4.0 for x64.

    http://blogs.msdn.com/clrcodegeneration/archive/2009/05/11/tail-call-improvements-in-net-framework-4.aspx

Leave a Reply