GCC 8.1 doesn't do all the unrolling (some in main() but not in the function itself) but the function is being reduced to one recursive call in a loop.jahboater wrote: ↑Sat Nov 03, 2018 8:19 amI "suspect" that GCC has deduced the relationship between recur_fibo(n-1) and recur_fibo(n-2) and therefore doesn't need to call it a second time.

Its only my guess, as the asm gives me a headache too. GCC 7+ intersperses the original C source code with asm insns but its not making it clearer here.

BTW I changed it to an expression.

static int

recur_fibo( const int n )

{

return n <= 1 ? n : recur_fibo(n-1) + recur_fibo(n-2);

}

GCC 6.3 is further inlining the function 4 times inside itself.

Converting the ARM assembly back into C gives

Code: Select all

```
static int
opt_fibbo( const int n )
{
if (n <= 1)
return n;
int n2 = n - 2;
int n_stop = n - 3 - (n2 & -2);
int total = 0;
for (int x = n - 1; x != n_stop; x -= 2)
total += opt_fibbo(x);
total += n2 & 1;
return total;
}
```

Code: Select all

```
static int
opt_fibbo( const int n )
{
if (n <= 1)
return n;
int total = n & 1;
for (int x = n - 1; x > 0; x -= 2)
total += opt_fibbo(x);
return total;
}
```

Hand-inlining the code (which gives roughly what gcc is doing in 6.3)

Code: Select all

```
static int
fib( const int n )
{
if (n <= 1)
return n;
int t = n & 1;
for (int n1 = n-1; n1 > 0; n1 -= 2) {
t += n1 & 1;
if (n1 <= 1)
break;
for (int n2 = n1-1; n2 > 0; n2 -= 2) {
t += n2 & 1;
if (n2 <= 1)
break;
for (int n3 = n2 - 1; n3 > 0; n3 -= 2) {
t += n3 & 1;
if (n3 <= 1)
break;
for (int n4 = n3 - 1; n4 > 0; n4 -= 2) {
t += n4 & 1;
if (n4 <= 1)
break;
for (int n5 = n4 - 1; n5 > 0; n5 -= 2) {
t += fib( n5 );
}
}
}
}
}
return t;
}
```

Code: Select all

```
import timeit
def recur_fibbo(n):
if n <= 1:
return n
else:
return recur_fibbo(n-1) + recur_fibbo(n-2)
def opt_fibbo(n):
if n <= 1:
return n
else:
total = n & 1
for x in range (n-1, 0, -2):
total = total + opt_fibbo(x)
return total
nterms = 25
def run_recur():
for i in range(nterms):
print(i, recur_fibbo(i))
def run_opt():
for i in range(nterms):
print(i, opt_fibbo(i))
recur_time = timeit.timeit('run_recur()', setup="from __main__ import run_recur", number=10)
opt_time = timeit.timeit('run_opt()', setup="from __main__ import run_opt", number=10)
print('Recur time = {}'.format(recur_time))
print('Opt time = {}'.format(opt_time))
```