Frits van Bommel wrote:
bearophile wrote:
Some are ignorant (the author concluded that dmd can't optimize tail
recursion by trying it with the non-tail-recursive factorial
function; and I took the time to explain him!).<
If I compile this D2 program with DMD:
import std.stdio: printf;
import std.conv: to;
int sum(int[] a, int start=0) {
if (start >= a.length)
return 0;
else {
return a[start] + sum(a, start+1);
//auto b = a[start];
//return b + sum(a, start+1);
}
}
void main(char[][] args) {
int n = args.length > 1 ? to!int(args[1]) : 1;
auto a = new int[n];
foreach(i, ref x; a)
x = i;
printf("%d\n", sum(a));
}
He's right though; the code isn't properly tail recursive (it performs
an add after the recursion). However, it can be *made* tail recursive by
introducing an accumulator, which is something LLVM does here[1].
Note that if the accumulator is introduced manually, the tail recursion indeed
gets eliminated by DMD (and turned into a loop).
Code: (D1, Phobos or Tango)
-----
extern(C) int printf(char*, ...);
version(Tango)
import tango.text.convert.Integer;
else
import std.conv;
int sum(int[] a, int start=0, int acc = 0) {
if (start >= a.length)
return acc;
else {
return sum(a, start+1, acc + a[start]);
//auto b = a[start];
//return b + sum(a, start+1);
}
}
void main(char[][] args) {
int n = args.length > 1 ? toInt(args[1]) : 1;
auto a = new int[n];
foreach(i, ref x; a)
x = i;
printf("%d\n", sum(a));
}
-----
With dmd -O -release, I get the following objdump output (demangled):
-----
08049b54 <int test.sum(int[], int, int)>:
8049b54: 55 push %ebp
8049b55: 8b ec mov %esp,%ebp
8049b57: 83 ec 10 sub $0x10,%esp
8049b5a: 53 push %ebx
8049b5b: 8b 5d 08 mov 0x8(%ebp),%ebx
8049b5e: 89 c1 mov %eax,%ecx
8049b60: 56 push %esi
8049b61: 57 push %edi
8049b62: 3b 5d 0c cmp 0xc(%ebp),%ebx
8049b65: 72 0b jb 8049b72 <int test.sum(int[],
int, int)+0x1e>
8049b67: 5f pop %edi
8049b68: 8b c1 mov %ecx,%eax
8049b6a: 5e pop %esi
8049b6b: 5b pop %ebx
8049b6c: 8b e5 mov %ebp,%esp
8049b6e: 5d pop %ebp
8049b6f: c2 0c 00 ret $0xc
8049b72: 89 5d 08 mov %ebx,0x8(%ebp)
8049b75: 8b 55 10 mov 0x10(%ebp),%edx
8049b78: 8b 5d 0c mov 0xc(%ebp),%ebx
8049b7b: 89 d7 mov %edx,%edi
8049b7d: 8b 5d 08 mov 0x8(%ebp),%ebx
8049b80: 8b 34 9f mov (%edi,%ebx,4),%esi
8049b83: 03 f1 add %ecx,%esi
8049b85: 8d 53 01 lea 0x1(%ebx),%edx
8049b88: 3b 55 0c cmp 0xc(%ebp),%edx
8049b8b: 89 f1 mov %esi,%ecx
8049b8d: 89 d3 mov %edx,%ebx
8049b8f: 73 d6 jae 8049b67 <int test.sum(int[],
int, int)+0x13>
8049b91: eb ed jmp 8049b80 <int test.sum(int[],
int, int)+0x2c>
8049b93: 90 nop
-----
