The Takeuchi Benchmark

Some of you may be familiar with the "Takeuchi Benchmark", one of the earliest attempts at Lisp compiler and system benchmarking. Similar to the Ackerman function the Takeuchi function is defined as

int takeuchi( int x, int y, int z ) {

if( y >= x ) return z;
return takeuchi( takeuchi( x-1, y , z ),
takeuchi( y-1, z, x ),
takeuchi( z-1, x, y ) );
}

Compiler generated code for this function is interesting to look at for several reasons.

I used the command line

cc -xchip=opteron -xO5 -S /tmp/takeuchi.c

Sun Studio 12 compilers generate this assembly for Opteron optimized code.
/ BLOCK: 6, pred: 14 5, succ: 12, count: 8.000000


/ 5 ! if( y >= x ) return z;
/ 6 ! return takeuchi( takeuchi(x-1, y, z),
/ 7 ! takeuchi(y-1, z, x),
/ 8 ! takeuchi(z-1, x, y));

{ int[ 2] 8 } leal -1(%r12),%edi
{ int[ 1] 8 } movl %r14d,%esi
{ int[ 1] 8 } movl %ebx,%edx
{ 8 } call takeuchi


The code for SPARC is also instructive for RISC style:
! 1 !// (C) Sandeep Koranne, 2009
! 2 !// Licensed under GPL
! 3 !// Compute codes for comparison between processors
! 5 !#include
! 7 !unsigned long int takeuchi(
! 8 ! unsigned long int x,
! 9 ! unsigned long int y,
! 10 ! unsigned long int z) {

!
! SUBROUTINE __1cItakeuchi6FLLL_L_
!
! OFFSET SOURCE LINE LABEL INSTRUCTION

.global __1cItakeuchi6FLLL_L_


__1cItakeuchi6FLLL_L_:

! Registers live out of __1cItakeuchi6FLLL_L_:
! o0 o2 sp i0 i1 i2 fp i7 gsr
!


.L900000106:
/* 000000 10 */ save %sp,-176,%sp
/* 0x0004 */ cmp %i1,%i0
/* 0x0008 */ bcc,pn %xcc,.L77000030
/* 0x000c 13 */ or %g0,%i2,%o2

! 12 ! if( y >= x ) return z;
! 13 ! else return( takeuchi( takeuchi(x-1,y,z),


! predecessor blocks: .L900000104 .L900000106

.L900000104:
/* 0x0010 13 */ or %g0,%i1,%o1
/* 0x0014 */ call __1cItakeuchi6FLLL_L_ ! params = %o0
%o1 %o2 ! Result = %o0
/* 0x0018 */ add %i0,-1,%o0
/* 0x001c */ or %g0,%o0,%i5
/* 0x0020 */ or %g0,%i0,%o2
/* 0x0024 */ or %g0,%i2,%o1
/* 0x0028 */ call __1cItakeuchi6FLLL_L_ ! params = %o0
%o1 %o2 ! Result = %o0
/* 0x002c */ add %i1,-1,%o0
/* 0x0030 */ or %g0,%o0,%i4
/* 0x0034 */ or %g0,%i1,%o2
/* 0x0038 */ or %g0,%i0,%o1
/* 0x003c */ or %g0,%i5,%i0
/* 0x0040 */ call __1cItakeuchi6FLLL_L_ ! params = %o0
%o1 %o2 ! Result = %o0
/* 0x0044 */ add %i2,-1,%o0
/* 0x0048 */ cmp %i4,%i5
/* 0x004c */ or %g0,%i4,%i1
/* 0x0050 */ or %g0,%o0,%i2
/* 0x0054 */ bcs,pt %xcc,.L900000104