Josef “Jeff” Sipek

Recursion with Sun Studio

I mentioned my post about recursion & DTrace in the #dtrace, and one of the folks there asked about Sun’s/Oracle’s compiler — Studio. I happen to have version 12u1, so why not have some more fun? :)

First things first, the results. With -O1, both variants recurse — 6 calls followed by 6 returns. With -O2, the naive code still recurses, while the explicitly-coded-as-tail-recursive code tail-recurses.

Here are the disassemblies (for -O2). Naive-recursive:

08050aa0 <fac>:
 8050aa0:	55                   	push   %ebp
 8050aa1:	8b ec                	mov    %esp,%ebp
 8050aa3:	53                   	push   %ebx
 8050aa4:	83 ec 04             	sub    $0x4,%esp
 8050aa7:	83 e4 f0             	and    $0xfffffff0,%esp
 8050aaa:	8b 5d 08             	mov    0x8(%ebp),%ebx
 8050aad:	83 fb 01             	cmp    $0x1,%ebx
 8050ab0:	7f 07                	jg     8050ab9 <fac+0x19>
 8050ab2:	b8 01 00 00 00       	mov    $0x1,%eax
 8050ab7:	eb 12                	jmp    8050acb <fac+0x2b>
 8050ab9:	83 ec 0c             	sub    $0xc,%esp
 8050abc:	8d 43 ff             	lea    -0x1(%ebx),%eax
 8050abf:	50                   	push   %eax
 8050ac0:	e8 db ff ff ff       	call   8050aa0 <fac>
 8050ac5:	83 c4 10             	add    $0x10,%esp
 8050ac8:	0f af c3             	imul   %ebx,%eax
 8050acb:	8d 65 fc             	lea    -0x4(%ebp),%esp
 8050ace:	5b                   	pop    %ebx
 8050acf:	c9                   	leave  
 8050ad0:	c3                   	ret    

and tail-recursive:

08050aa0 <fac>:
 8050aa0:	55                   	push   %ebp
 8050aa1:	8b ec                	mov    %esp,%ebp
 8050aa3:	8b 55 08             	mov    0x8(%ebp),%edx
 8050aa6:	8b 45 0c             	mov    0xc(%ebp),%eax
 8050aa9:	83 fa 01             	cmp    $0x1,%edx
 8050aac:	7e 0d                	jle    8050abb <fac+0x1b>
 8050aae:	8d 4a ff             	lea    -0x1(%edx),%ecx
 8050ab1:	0f af c2             	imul   %edx,%eax
 8050ab4:	8b d1                	mov    %ecx,%edx
 8050ab6:	83 f9 01             	cmp    $0x1,%ecx
 8050ab9:	7f f3                	jg     8050aae <fac+0xe>
 8050abb:	89 45 0c             	mov    %eax,0xc(%ebp)
 8050abe:	89 55 08             	mov    %edx,0x8(%ebp)
 8050ac1:	c9                   	leave  
 8050ac2:	c3                   	ret 

I find it fascinating that Studio produced nearly identical code to gcc. The big differences that you can see are: (1) Studio defaults to saving the frame pointer while gcc omitted it, (2) gcc inserted a no-op to 16-byte align the loop, and (3) Studio uses an extra register to perform the subtraction (the n-1).

The subtraction surprised me, and so I examined the code more closely. My guess is that Studio attempts to move the subtraction as far up as possible to start it early. This way, by the time we actually need the subtracted value (the cmp instruction) it’s already available. Compare that to gcc’s sub followed immediately by cmp. Some processors are designed in such a way that the result of sub will be available by the time cmp wants to execute. Others are not.

Your Turn

Have you noticed any interesting compiler optimizations? Share them in a comment!

Recursion

Last night while reading about DTrace, I came across an example that involved tracing a simple recursive factorial program. I pointed it out to my girlfriend, Holly, since I thought that she’d find it interesting — the class she teaches has a section about recursion.

Here’s the original code:

extern int fac (int n);

int main(int argc, char **argv)
{
	int f;
	f = fac(6);
	return 0;
}

int fac (int n)
{
	if (n <= 1)
		return 1;
	else
		return n * fac (n - 1);
}

Pretty simple. I compiled it, and ran it with DTrace:

$ gcc -o fac orig.c 
$ cat fac.d 
pid$target::fac:entry
{
        trace (arg0);
}
pid$target::fac:return
{
        trace (arg1);
}
$ sudo dtrace -Fs fac.d -c ./fac
dtrace: script 'fac.d' matched 2 probes
dtrace: pid 1146 has exited
CPU FUNCTION                                 
  0  -> fac                                                   6
  0    -> fac                                                 5
  0      -> fac                                               4
  0        -> fac                                             3
  0          -> fac                                           2
  0            -> fac                                         1
  0            <- fac                                         1
  0          <- fac                                           2
  0        <- fac                                             6
  0      <- fac                                              24
  0    <- fac                                               120
  0  <- fac                                                 720

Cool! I thought I was done. Holly asked whether it would work with tail-recursion. Interesting, I thought…it might - depending on how gcc handles the function prologue and epilogue. The D script is a little different to dump both of the arguments. Here’s the result:

$ gcc -o fact tail.c
$ cat fact.d 
pid$target::fac:entry
{
        trace (arg0); trace(arg1);
}
pid$target::fac:return
{
        trace (arg1);
}
$ sudo dtrace -Fs fact.d -c ./fact
dtrace: script 'fact.d' matched 2 probes
dtrace: pid 1233 has exited
CPU FUNCTION                                 
  2  -> fac                                                   6                1
  2    -> fac                                                 5                6
  2      -> fac                                               4               30
  2        -> fac                                             3              120
  2          -> fac                                           2              360
  2            -> fac                                         1              720
  2            <- fac                                       720
  2          <- fac                                         720
  2        <- fac                                           720
  2      <- fac                                             720
  2    <- fac                                               720
  2  <- fac                                                 720

You can see the values getting calculated and passed down versus them getting calculated on during the return. That was fun to see. But wait! If this function is tail recursive, why are we seeing all these returns? It should be just one return! Doh! I didn’t compile with optimizations so gcc emitted the stupidest possible code. Easy enough to fix:

$ gcc -o fact -O2 tail.c 
$ sudo dtrace -Fs fact.d -c ./fact
dtrace: script 'fact.d' matched 2 probes
dtrace: pid 1304 has exited

$

Huh… nothing happened! fac was never called. Let’s see what gcc emitted:

$ objdump -S fact
...
Disassembly of section .text.startup:

08050d10 <main>:
 8050d10:       31 c0                   xor    %eax,%eax
 8050d12:       c3                      ret  

Great, the main function turned into a return 0 because the value returned by fac() was never used. Easy enough, let’s just return the value from main.

$ cat tail.c 
extern int fac (int n);

int main(int argc, char **argv)
{
        return fac(6);
}

int fac (int n)
{
        if (n <= 1)
                return 1;
        else
                return n * fac (n - 1);
}
$ gcc -o fact -O2 tail.c 
$ objdump -S fact
...
Disassembly of section .text.startup:

08050d10 <main>:
 8050d10:       b8 d0 02 00 00          mov    $0x2d0,%eax
 8050d15:       c3                      ret    

Argh! Thanks gcc, you replaced my fac(6) function call with the value 720 — that is the factorial of 6. Fine, let’s do this the hard way: get an int from the first argument and print it out. Also, to prevent inlining, let’s put it in a separate file. So, now we have:

$ cat fac.c
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

extern int fac (int n);

int main(int argc, char **argv)
{
        printf("%d\n", fac(atoi(argv[1])));
        return 0;
}
$ cat fac_2.c
int fac (int n)
{
        if (n <= 1)
                return 1;
        else
                return n * fac (n - 1);
}
$ cat fact.c
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

extern int fac (int n, int v);

int main(int argc, char **argv)
{
        printf("%d\n", fac(atoi(argv[1]), 1));
        return 0;
}
$ cat fact_2.c
int fac (int n, int v)
{
        if (n <= 1)
                return v;
        else
                return fac(n-1, n*v);
}

Now, if we run the two variants compiled with -O2, we get:

$ sudo dtrace -Fs fac.d -c "./fac 6"
dtrace: script 'fac.d' matched 2 probes
720
dtrace: pid 1397 has exited
CPU FUNCTION                                 
  2  -> fac                                                   6
  2  <- fac                                                 720

$ sudo dtrace -Fs fact.d -c "./fact 6"
dtrace: script 'fact.d' matched 2 probes
720
dtrace: pid 1399 has exited
CPU FUNCTION                                 
  5  -> fac                                                   6                1
  5  <- fac                                                 720

Weird, for both we can see only one function entry and return. Let’s try with -O1:

$ sudo dtrace -Fs fac.d -c "./fac 6"
dtrace: script 'fac.d' matched 2 probes
720
dtrace: pid 1393 has exited
CPU FUNCTION                                 
  6  -> fac                                                   6
  6    -> fac                                                 5
  6      -> fac                                               4
  6        -> fac                                             3
  6          -> fac                                           2
  6            -> fac                                         1
  6            <- fac                                         1
  6          <- fac                                           2
  6        <- fac                                             6
  6      <- fac                                              24
  6    <- fac                                               120
  6  <- fac                                                 720

$ sudo dtrace -Fs fact.d -c "./fact 6"
dtrace: script 'fact.d' matched 2 probes
720
dtrace: pid 1395 has exited
CPU FUNCTION                                 
  2  -> fac                                                   6                1
  2    -> fac                                                 5                6
  2      -> fac                                               4               30
  2        -> fac                                             3              120
  2          -> fac                                           2              360
  2            -> fac                                         1              720
  2            <- fac                                       720
  2          <- fac                                         720
  2        <- fac                                           720
  2      <- fac                                             720
  2    <- fac                                               720
  2  <- fac                                                 720

Ok, now were back to having call and return instructions for both cases — the tail recursive function is not actually tail recursing when it should. So, first moral of the story is: -O1 is not enough to make tail recursive functions tail recurse. The odd behavior of the non-tail recursive code with -O2 is still weird. Let’s disassemble it; first the simple recursive code:

08050d00 <fac>:
 8050d00:       8b 54 24 04             mov    0x4(%esp),%edx
 8050d04:       b8 01 00 00 00          mov    $0x1,%eax
 8050d09:       83 fa 01                cmp    $0x1,%edx
 8050d0c:       7e 0d                   jle    8050d1b <fac+0x1b>
 8050d0e:       66 90                   xchg   %ax,%ax
 8050d10:       0f af c2                imul   %edx,%eax
 8050d13:       83 ea 01                sub    $0x1,%edx
 8050d16:       83 fa 01                cmp    $0x1,%edx
 8050d19:       75 f5                   jne    8050d10 <fac+0x10>
 8050d1b:       f3 c3                   repz ret 
 8050d1d:       90                      nop    
 8050d1e:       90                      nop    
 8050d1f:       90                      nop    

Whoa! gcc turned the plain recursive code into a tail-recursive one. For comparison, here’s the disassembly of the explicitly-coded-as-tail-recursive function:

08050d00 <fac>:
 8050d00:       8b 54 24 04             mov    0x4(%esp),%edx
 8050d04:       8b 44 24 08             mov    0x8(%esp),%eax
 8050d08:       83 fa 01                cmp    $0x1,%edx
 8050d0b:       7e 0e                   jle    8050d1b <fac+0x1b>
 8050d0d:       8d 76 00                lea    0x0(%esi),%esi
 8050d10:       0f af c2                imul   %edx,%eax
 8050d13:       83 ea 01                sub    $0x1,%edx
 8050d16:       83 fa 01                cmp    $0x1,%edx
 8050d19:       75 f5                   jne    8050d10 <fac+0x10>
 8050d1b:       f3 c3                   repz ret 
 8050d1d:       90                      nop    
 8050d1e:       90                      nop    
 8050d1f:       90                      nop

Do you see it? It’s virtually identical to what gcc emitted for the naive code.

So there you have it folks. The compiler is smarter than you, more consistent than you, and less likely to screw up compared to you when converting a recursive function into a tail-recursive one. In general, you should not prematurely optimize.

In case you care, I’ve used gcc 4.6.1 for these experiments on OpenIndiana.

Your Turn

Do you have an interesting compiler optimization story? Share it in a comment!

Powered by blahgd