Проверял GCC на предмет того, как он умеет рекурсию оптимизировать.
Вот такая штука
unsigned int plus(unsigned int a, unsigned int b)
{
if (b == 0) return a;
return plus (a+1, b-1);
}
Относительно успешно сворачивается сложение. Получается такая шняга:
movl %edi, %eax
addl %esi, %eax
ret
Хотя в идеале можно было бы обойтись
leal (%rsi,%rdi), %eax
ret
Что касается умножения, там ситуация более печальная
inline unsigned long int product_0(const unsigned int a, const unsigned int b, const unsigned long int tmp)
{
if (b == 0) return tmp;
return product_0(a, b-1, tmp+a);
}
unsigned long int product(const unsigned int a, const unsigned int b)
{
return product_0(a, b, 0);
}
В ассемблере получается такая фигня
product:
.LFB34:
.cfi_startproc
xorl %eax, %eax
testl %esi, %esi
je .L7
leal -1(%rsi), %eax
mov %edi, %edi
addq $1, %rax
imulq %rdi, %rax
.L7:
rep
ret
.cfi_endproc
Тут оно зачем-то зануляет значение регистра, в котором хранится возврашемое из функции значение и сравнивает с нулем значение регистра, в котором в функцию передается число. Если ноль то прыгаем в конец функции, возвращая 0. Тогда внезапно появляется смысл в этом rep ret http://repzret.org/p/repzret/
Why? Because “The processor is unable to apply a branch prediction to the single-byte near-return form (opcode C3h) of the ret instruction.” Thus, “Use of a two-byte near-return can improve performance”, because it is not affected by this shortcoming.
Ну а дальше через leal из регистра rsi число копируется в eax, уменьшаясь при этом на 1 (нахрена?) и потом из регистра edi двигается в edi (НАХРЕНА??), увеличиваем rax на 1 через addq (ну тут понятно зачем, перед этим ведь оно было непонятно зачем уменьшено на 1, но нахрена уменьшать и потом увеличивать? И вообще, для увеличения на 1 лучше incq использовать) ну и в итоге компилятор таки вставляет инструкцию imulq. Распознать умножение в этой рекурсивной хрени компилятор смог, но при этом как-то через жопу все, нагенерировал кучу говна всякого. Можно было намного проще сделать
movl %esi, %eax
imull %edi, %eax
gcc version 4.5.1 если что
