C++ Tail Recursion Using 64-bit variables – Part 2

In my previous post I talked about recursion problems in a Fibonacci function using 64-bit variables as function parameters, compiled using the Microsoft Visual C++ compiler. It turned out that while tail recursion was enabled by the compiler using 32-bit types it didn’t really when switching to 64-bit ones. Just as a reminder, Tail Recursion is an optimization performed by the compiler. It is the process of transforming certain types of tail calls into jumps instead of function calls. More about tail recursion here.

My conclusion was that tail recursion is not handled properly by the Visual C++ compiler and a possible explanation could be the presence of a bug.

The calculation of Fibonacci sequences of big integers is not an everyday task but it can still be a reliable example to show how tail calls are implemented.

Not happy with my conclusions and following several suggestions of users’ comments (here on the blog, on Reddit and on StackOverflow) I wanted to understand more about this issue and to explore other solutions using different compilers.

Let’s pick again the Visual Studio project I used in my previous post and hosted on GitHub. This was the Fibonacci function used:

typedef  unsigned long long ULONG64;

ULONG64 fib_tail_x64(ULONG64 n, ULONG64 res, ULONG64 next)
{
   if (n == 0) {
 	return res;
   }
   return fib_tail_x64(n - 1, next, res + next);
}

As you might recall, compiling it in Release mode (which is generally needed to enable tail recursion due to the compiler optimization command /Ox), and targeting Win32 platforms resulted in having tail recursion disabled:

Fibonacci with x64 variables

Tail Recursion is not Enabled! It’s an ugly assembly though I didn’t omit frame stack pointers

One thing I didn’t try to do (well to be honest I actually completely forgot) was to pay attention to the solution platform chosen to build the project. In Visual Studio Win32, which means to compile the solution using x86 processor instructions, is the default configuration set. Looking carefully at the generated assembly in the picture above it can be seen that registers used, EAX, EBX, etc are, accordingly with the configuration chosen, 32-bit processor registers.

Switching configuration to x64, building and running the project resulted in this assembly:

Tail Recursion is back!!!

Tail Recursion is back!!!

Surprise!! Tail recursion is back, x64 registers are used instead (RAX, RDX, etc.) and the assembly is much shorter and cleaner!

Summarizing what said so far for tail calls we can take the following table as a reference:

 Var Type\Platform x86 x64
32-bit  Tail Call Active  Tail Call Active
64-bit  No Tail Call Tail Call Active

It seems then that the problem is only “restricted” when a x86 platform is targeted and x64 variables used.

At this stage I honestly couldn’t really say “it’s definitely a bug in the MS compiler” so still not satisfied I went trying the same experiment using another compiler.

This time I decided to change operating system altogether and use Clang, installed on my Macbook as part of XCode and based on LLVM.

Terminal - clang version

Terminal – clang version

To view the generated assembly I used a handy tool called Hopper Disassembler, available on both OS X and Linux (but for gdb debugger would have sufficed too I guess).

I repeated the exact same experiment. The following image shows the first generated assembly:

clang-tail-recursion-x64

Tail Recursion is clearly enabled: JNE (Jump Not Equal) is just a conditional jump when ZF (the “zero” flag) is equal to 0. The red arrow on the left points at the address where the program execution jumps if the condition is true. The careful observer might have already noticed that this code is not compiled for 32-bit processors. The assembly registers are actually 64-bit (RBD, RDI, etc.).

Our goal here is to verify instead that targeting a 32-bit platform tail recursion would still be enabled.

It is possible to force the compiler to generate 32-bit code, using the compiler flag m32. Building again the solution in 32-bit mode I obtained:

Tail Recursion enabled!

Tail Recursion enabled!

Bingo!!! By looking at the type of registers we can state that the executable is targeting the correct architecture we chose, and look at the last instruction the surprisingly result: Tail Recursion is enabled for 32-bit too!!!!!

EDIT:

It seemed that a lot of users could not reproduce this problem (see comments below and on Reddit too). I went playing with the compiler optimization options, tweaking some parameters. By default using Release mode this is the default configuration for optimization:

Default optimization options

Default optimization options

After a few attempts I changed ‘Whole Program Optimization’ from /GL (yes) to No. I changed ‘Omit Frame Pointers’ too as I was pointed out that the generated x86 assembly, with frame pointers, is way longer and uglier (and we probably save a few clock cycles avoiding some cache misses too). There is a nice explanation on StackOverflow if you want to read more about omitting frame pointers.

However, with those changes in mind, I recompiled the solution using Win32 and I got this surprising result:

Tail recursion on x86 too disabling 'Whole Program Optimization'

Tail recursion for x86. Worked by disabling ‘Whole Program Optimization’

EDIT 2:

A few users pointed out that regardless of WPO (Whole Program Optimizationthey did not experience any issue with tail recursion. This has puzzled me for a while until I realized I was not paying attention to one important detail: the way I was calling the fibonacci function from the main. Since so far I’ve used this function call to test my x64 fibonacci:

   ULONG64 res = fib_tail_x64(40, 0, 1);

So far so good, nothing special there. I’m just passing literals as parameters.

What if we use a variable, or instead a function pointer? Let’s try this:

   ULONG64 a   = 40;
   ULONG64 res = fib_tail_x64(a, 0, 1);

Although it doesn’t look like a big change, calling the fib_tail_x64 using variables, it enables tail recursion regardless of WPO (as long as an optimization flag >= /O2 is used). A Reddit user highlighted that calling the function indirectly through pointers (regardless of using literals) would produce the same result:

volatile bool a = true;
ULONG64 res = 0;
ULONG64(*ptr)(ULONG64 n, ULONG64 res, ULONG64 next) = NULL;
if (a)
{
    ptr = &fib_tail_x64;
}
res = ptr(40, 0, 1);

Final Thoughts

Although I was initially sure that a possible explanation for the absence of tail recursion was the presence of a bug in the Visual C++ compiler it turned out it is not. The assemblies produced by both VC++ and Clang are very similar for x86 platforms. My first conclusion was to keep in mind is to disable ‘Whole Program Optimization’, if and only if you are calling the x64 recursive function directly and passing literals as parameters.

After a second analysis it emerged that for a few users this was not happening as they were calling the function directly using variables or indirectly through function pointers.

I would be still interested to hear some thoughts from somebody working on the Visual C++ compiler team to know the reason behind this “issue”.

That’s all guys, thanks for reading! If you want to stay in touch drop me an email using the Contact form or follow me on Twitter!

See you soon!

8 thoughts on “C++ Tail Recursion Using 64-bit variables – Part 2

      1. OK I spotted it I think this time. I’m sure in your main function you call the fibonacci function passing variables. Try to pass literals instead, e.g.:

        ULONG64 s = fib_tail_x64(100, 0, 1);

        I realized that by doing this I have tail recursion regardless of WOP

        int a = 10
        ULONG64 s = fib_tail_x64(a, 0, 1);

        Thanks for pointing it out, I’ll update the article🙂

        Like

  1. I can not reproduce these results in MSVC 2013 Ultimate Update 1 with optimizations enabled. Only when optimizations are disabled do I get the same results as you.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s