Tail call optimization

I had posted about tail call and how .NET handles it before. However there was some email exchanges and confusion on internal DLs around it and so I thought I'd try to elaborate more on how .NET goes about handling tail calls

Let’s try to break this down a bit.

a) A piece of C# code contains tail recursion .

 static void CountDown(int num)
{ 
    Console.WriteLine("{0} ", num); 
    if (num > 0) 
        CountDown(--num); 
} 

b) The C# compiler does not optimize this and generates a normal recursive call in IL

  IL_000c:  ...
 IL_000d:  ...
 IL_000e:  sub
 IL_000f:  dup
 IL_0010:  starg.s num
 IL_0012:  call void TailRecursion.Program::CountDown(int32)

c) The Jitter on seeing this call doesn’t optimize it in any way and just inserts a normal call instruction for the platform it targets (call for x86)

However, if any compiler is smart enough to add the tail. recursive IL statement then things change.

a) Scheme code

 (define (CountDown n)
    (if (= n 0)
         n
      (CountDown (- n 1))))

b) Hypothetical IronScheme compiler will generate (note for scheme it has to do the optimization)

  IL_000c:  ...
 IL_000d:  ...
 IL_000e:  sub
  tail.
 IL_0023:  call void TailRecursion.Program::CountDown(int32)
 IL_0029:  ret

c) Based on which JIT you are using and various other scenarios the JIT now may honour the tail. IL instruction and optimize this with a jmp when generating machine instruction

Please note the may in the very last point and refer to here for some instances where the optimization still might not take place…

Comments

• Anonymous
  September 27, 2008
  It seems to me that the guarantees for .tail should be a lot stronger, and possibly even be considered an error if it cannot be honoured. Otherwise, depending on it actually working is not a great idea since stuff might just break at the whim of the JIT. Maybe now that MS has a real compiler that uses .tail, the CLR will care a bit more...