GCC a tail-call recursion

GCC so zapnutými optimalizáciami dokáže preložiť nasledujúci kód (ktorý nie je správne napísaná tail-call recursion) optimalizovane:

long fact(long x) {
    if (x <= 0)
        return 1;
 
    return x*fact(x-1);
}

Výsledok:

0000000000400494 <fact>:
  400494:	b8 01 00 00 00       	mov    $0x1,%eax
  400499:	48 85 ff             	test   %rdi,%rdi
  40049c:	7e 09                	jle    4004a7 <fact+0x13>
  40049e:	48 0f af c7          	imul   %rdi,%rax
  4004a2:	48 ff cf             	dec    %rdi
  4004a5:	eb f2                	jmp    400499 <fact+0x5>
  4004a7:	c3                   	retq   

Zdroj tohoto zázraku:

In addition to the standard tail recursion elimination, we handle the most trivial cases of making the call tail recursive by creating accumulators. For example the following function
int sum (int n)
{
  if (n > 0)
    return n + sum (n - 1);
  else
    return 0;
}


is transformed into

int sum (int n)
{
  int acc = 0;
 
  while (n > 0)
    acc += n--;
 
  return acc;
}

(http://gcc.gnu.org/viewcvs/trunk/gcc/tree-tailcall.c?revision=151935&view=markup)

Comments

weblog/2010-03-09/gcc_a_tail-call_recursion.txt · Last modified: 2010/08/03 06:21 by 127.0.0.1