Generate tail call opcode

Question

Out of curiosity I was trying to generate a tail call opcode using C#. Fibinacci is an easy one, so my c# example looks like this:

    private static void Main(string[] args)     {         Console.WriteLine(Fib(int.MaxValue, 0));     }      public static int Fib(int i, int acc)     {         if (i == 0)         {             return acc;         }          return Fib(i - 1, acc + i);     } 

If I build it in release and run it without debugging I do not get a stack overflow. Debugging or running it without optimizations and I do get a stack overflow, implying that tail call is working when in release with optimizations on (which is what I expected).

The MSIL for this looks like this:

.method public hidebysig static int32 Fib(int32 i, int32 acc) cil managed {     // Method Start RVA 0x205e     // Code Size 17 (0x11)     .maxstack 8     L_0000: ldarg.0      L_0001: brtrue.s L_0005     L_0003: ldarg.1      L_0004: ret      L_0005: ldarg.0      L_0006: ldc.i4.1      L_0007: sub      L_0008: ldarg.1      L_0009: ldarg.0      L_000a: add      L_000b: call int32 [ConsoleApplication2]ConsoleApplication2.Program::Fib(int32,int32)     L_0010: ret  } 

I would've expected to see a tail opcode, per the msdn, but it's not there. This got me wondering if the JIT compiler was responsible for putting it in there? I tried to ngen the assembly (using ngen install <exe>, navigating to the windows assemblies list to get it) and load it back up in ILSpy but it looks the same to me:

.method public hidebysig static int32 Fib(int32 i, int32 acc) cil managed {     // Method Start RVA 0x3bfe     // Code Size 17 (0x11)     .maxstack 8     L_0000: ldarg.0      L_0001: brtrue.s L_0005     L_0003: ldarg.1      L_0004: ret      L_0005: ldarg.0      L_0006: ldc.i4.1      L_0007: sub      L_0008: ldarg.1      L_0009: ldarg.0      L_000a: add      L_000b: call int32 [ConsoleApplication2]ConsoleApplication2.Program::Fib(int32,int32)     L_0010: ret  } 

I still don't see it.

I know F# handles tail call well, so I wanted to compare what F# did with what C# did. My F# example looks like this:

let rec fibb i acc =       if i = 0 then         acc     else          fibb (i-1) (acc + i)   Console.WriteLine (fibb 3 0) 

And the generated IL for the fib method looks like this:

.method public static int32 fibb(int32 i, int32 acc) cil managed {     // Method Start RVA 0x2068     // Code Size 18 (0x12)     .custom instance void [FSharp.Core]Microsoft.FSharp.Core.CompilationArgumentCountsAttribute::.ctor(int32[]) = { int32[](Mono.Cecil.CustomAttributeArgument[]) }     .maxstack 5     L_0000: nop      L_0001: ldarg.0      L_0002: brtrue.s L_0006     L_0004: ldarg.1      L_0005: ret      L_0006: ldarg.0      L_0007: ldc.i4.1      L_0008: sub      L_0009: ldarg.1      L_000a: ldarg.0      L_000b: add      L_000c: starg.s acc     L_000e: starg.s i     L_0010: br.s L_0000 } 

Which, according to ILSpy, is equivalent to this:

[Microsoft.FSharp.Core.CompilationArgumentCounts(Mono.Cecil.CustomAttributeArgument[])] public static int32 fibb(int32 i, int32 acc) {     label1:     if !(((i != 0)))      {         return acc;     }     (i - 1);     i = acc = (acc + i);;     goto label1; } 

So F# generated tail call using goto statements? This isn't what I was expecting.

I'm not trying to rely on tail call anywhere, but I am just curious where exactly does that opcode get set? How is C# doing this?

Answer 1

C# compiler does not give you any guarantees about tail-call optimizations because C# programs usually use loops and so they do not rely on the tail-call optimizations. So, in C#, this is simply a JIT optimization that may or may not happen (and you cannot rely on it).

F# compiler is designed to handle functional code that uses recursion and so it does give you certain guarantees about tail-calls. This is done in two ways:

• if you write a recursive function that calls itself (like your fib) the compiler turns it into a function that uses loop in the body (this is a simple optimization and the produced code is faster than using a tail-call)

• if you use a recursive call in a more complex position (when using continuation passing style where function is passed as an argument), then the compiler generates a tail-call instruction that tells the JIT that it must use a tail call.

As an example of the second case, compile the following simple F# function (F# does not do this in Debug mode to simplify debugging, so you may need Release mode or add --tailcalls+):

let foo a cont = cont (a + 1) 

The function simply calls the function cont with the first argument incremented by one. In continuation passing style, you have a long sequence of such calls, so the optimization is crucial (you simply cannot use this style without some handling of tail calls). The generates IL code looks like this:

IL_0000: ldarg.1 IL_0001: ldarg.0 IL_0002: ldc.i4.1 IL_0003: add IL_0004: tail.                          // Here is the 'tail' opcode! IL_0006: callvirt instance !1    class [FSharp.Core] Microsoft.FSharp.Core.FSharpFunc`2<int32, !!a>::Invoke(!0) IL_000b: ret