Как проверить, выполняет ли gcc оптимизацию хвостовой рекурсии?
Как мне узнать, оптимизирует ли gcc (точнее, g++) хвостовую рекурсию в определенной функции? (Потому что это возникало несколько раз: я не хочу проверять, может ли gcc оптимизировать хвостовую рекурсию в целом. Я хочу знать, оптимизирует ли она мою хвостовую рекурсивную функцию.)
Если ваш ответ "посмотрите на сгенерированный ассемблер", я хотел бы точно знать, что я ищу, и могу ли я написать простую программу, которая проверяет ассемблер, чтобы увидеть, есть ли оптимизация.
PS. Я знаю, что это является частью вопроса. Какие компиляторы C++ выполняют оптимизацию хвостовой рекурсии? с 5 месяцев назад. Однако я не думаю, что на эту часть этого вопроса был дан удовлетворительный ответ. (Ответ там был: "Самый простой способ проверить, выполнил ли компилятор оптимизацию (о которой я знаю), - это выполнить вызов, который в противном случае мог бы привести к переполнению стека или просмотру вывода сборки".)
10 ответов
Давайте использовать пример кода из другого вопроса. Скомпилируйте его, но скажите gcc не собирать:
gcc -std = c99 -S -O2 test.c
Теперь давайте посмотрим на _atoi Функция в результирующем файле test.s (gcc 4.0.1 в Mac OS 10.5):
.text
.align 4,0x90
_atoi:
pushl %ebp
testl %eax, %eax
movl %esp, %ebp
movl %eax, %ecx
je L3
.align 4,0x90
L5:
movzbl (%ecx), %eax
testb %al, %al
je L3
leal (%edx,%edx,4), %edx
movsbl %al,%eax
incl %ecx
leal -48(%eax,%edx,2), %edx
jne L5
.align 4,0x90
L3:
leave
movl %edx, %eax
ret
Компилятор выполнил оптимизацию хвостового вызова для этой функции. Мы можем сказать, потому что нет call инструкция в этом коде, тогда как исходный код C явно имел вызов функции. Кроме того, мы можем увидеть jne L5 инструкция, которая переходит назад в функции, указывая цикл, когда в коде C явно не было цикла. Если вы перекомпилируете с отключенной оптимизацией, вы увидите строку с надписью call _atoi, и вы также не увидите никаких скачков назад.
Можете ли вы автоматизировать это другой вопрос. Специфика кода ассемблера будет зависеть от кода, который вы компилируете.
Я думаю, вы могли бы обнаружить это программно. Заставьте функцию распечатать текущее значение указателя стека (зарегистрируйте ESP на x86). Если функция выводит то же значение для первого вызова, что и для рекурсивного вызова, то компилятор выполнил оптимизацию хвостового вызова. Эта идея требует изменения функции, которую вы надеетесь наблюдать, однако, и это может повлиять на то, как компилятор решит оптимизировать функцию. Если тест пройден успешно (печатает одно и то же значение ESP оба раза), то я думаю, что разумно предположить, что оптимизация также будет выполнена без вашего инструментария, но если тест не пройден, мы не будем знать, был ли сбой вызван добавление кода инструментовки.
РЕДАКТИРОВАТЬ Мой оригинальный пост также препятствовал тому, чтобы GCC фактически делал устранения хвостового вызова. Ниже я добавил некоторую хитрость, которая обманывает GCC в любом случае.
Расширяя ответ Стивена, вы можете программно проверить, есть ли у вас тот же фрейм стека:
#include <stdio.h>
// We need to get a reference to the stack without spooking GCC into turning
// off tail-call elimination
int oracle2(void) {
char oracle; int oracle2 = (int)&oracle; return oracle2;
}
void myCoolFunction(params, ..., int tailRecursionCheck) {
int oracle = oracle2();
if( tailRecursionCheck && tailRecursionCheck != oracle ) {
printf("GCC did not optimize this call.\n");
}
// ... more code ...
// The return is significant... GCC won't eliminate the call otherwise
return myCoolFunction( ..., oracle);
}
int main(int argc, char *argv[]) {
myCoolFunction(..., 0);
return 0;
}
При нерекурсивном вызове функции передайте 0 проверочный параметр. В противном случае перейдите в оракул. Если хвостовой рекурсивный вызов, который должен был быть устранен, не был, тогда вы будете проинформированы во время выполнения.
При тестировании это выглядит так, как будто моя версия GCC не оптимизирует первый хвостовой вызов, но остальные хвостовые вызовы оптимизированы. Интересно.
Посмотрите на сгенерированный код сборки и посмотрите, использует ли он call или же jmp инструкция для рекурсивного вызова на x86 (для других архитектур посмотрите соответствующие инструкции). Ты можешь использовать nm а также objdump чтобы получить только сборку, соответствующую вашей функции. Рассмотрим следующую функцию:
int fact(int n)
{
return n <= 1 ? 1 : n * fact(n-1);
}
Компилировать как
gcc fact.c -c -o fact.o -O2
Затем, чтобы проверить, использует ли он хвостовую рекурсию:
# get starting address and size of function fact from nm
ADDR=$(nm --print-size --radix=d fact.o | grep ' fact$' | cut -d ' ' -f 1,2)
# strip leading 0's to avoid being interpreted by objdump as octal addresses
STARTADDR=$(echo $ADDR | cut -d ' ' -f 1 | sed 's/^0*\(.\)/\1/')
SIZE=$(echo $ADDR | cut -d ' ' -f 2 | sed 's/^0*//')
STOPADDR=$(( $STARTADDR + $SIZE ))
# now disassemble the function and look for an instruction of the form
# call addr <fact+offset>
if objdump --disassemble fact.o --start-address=$STARTADDR --stop-address=$STOPADDR | \
grep -qE 'call +[0-9a-f]+ <fact\+'
then
echo "fact is NOT tail recursive"
else
echo "fact is tail recursive"
fi
При запуске на вышеуказанной функции этот скрипт выводит "факт рекурсивен". Когда вместо этого скомпилировано с -O3 вместо -O2это любопытно печатает "факт не хвост рекурсивный".
Обратите внимание, что это может привести к ложным негативам, как указало в своем комментарии. Этот скрипт даст правильный ответ только в том случае, если функция вообще не содержит рекурсивных вызовов и не обнаруживает рекурсию брата (например, где A() звонки B() какие звонки A()). Я не могу придумать более надежный метод в данный момент, который не предполагает человеческого взгляда на сгенерированную сборку, но, по крайней мере, вы можете использовать этот скрипт, чтобы легко получить сборку, соответствующую определенной функции в объектном файле.
Расширяя ответ PolyThinker, вот конкретный пример.
int foo(int a, int b) {
if (a && b)
return foo(a - 1, b - 1);
return a + b;
}
i686-pc-linux-gnu-gcc-4.3.2 -Os -fno-optimize-sibling-calls выход:
00000000: 0: 55 push% ebp 1: 89 e5 mov% esp,% ebp 3: 8b 55 08 mov 0x8 (% ebp),% edx 6: 8b 45 0c mov 0xc (% ebp),% eax 9: 85 d2 тест% edx,% edx b: 74 16 je 23 d: 85 c0 тест% eax,% eax f: 74 12 je 23 11: 51 толчок%ecx 12: 48% уп. 13: 51 толчок%ecx 14: 50 push %eax 15: 8d 42 ff lea -0x1(%edx),%eax 18: 50 push %eax 19: e8 ff ff ff ff call 1a 1e: 83 c4 10 добавить $0x10,%esp 21: отлив 02 jmp 25 23: 01 d0 добавить%edx,%eax 25: с9 оставить 26: с3 рет
i686-pc-linux-gnu-gcc-4.3.2 -Os выход:
00000000: 0: 55 push% ebp 1: 89 e5 mov% esp,% ebp 3: 8b 55 08 mov 0x8 (% ebp),% edx 6: 8b 45 0c mov 0xc (% ebp),% eax 9: 85 d2 тест% edx,% edx b: 74 08 je 15 d: 85 c0 тест% eax,% eax f: 74 04 je 15 11: 48% уп. 12: 4a dec% edx 13: eb f4 jmp 9 15: 5d pop% ebp 16: 01 d0 добавить% edx,% eax 18: с3 рет
В первом случае <foo+0x11>-<foo+0x1d> выдвигает аргументы для вызова функции, а во втором случае <foo+0x11>-<foo+0x14> изменяет переменные и jmps к той же функции, где-то после преамбулы. Это то, что вы хотите искать.
Я не думаю, что вы можете сделать это программно; слишком много возможных вариаций "Мясо" функции может быть ближе или дальше от начала, и вы не можете различить, что jmp из цикла или условного, не глядя на это. Это может быть условный переход вместо jmp, gcc может оставить call в некоторых случаях, но применять оптимизацию вызова родного брата в других случаях.
К вашему сведению, "родственные вызовы" gcc немного более общие, чем хвостовые рекурсивные вызовы - фактически любой вызов функции, когда повторное использование одного и того же стекового фрейма является нормальным, потенциально является родственным вызовом.
[редактировать]
В качестве примера, когда просто ищет саморекурсивный call введет вас в заблуждение,
int bar(int n) {
if (n == 0)
return bar(bar(1));
if (n % 2)
return n;
return bar(n / 2);
}
GCC будет применять оптимизацию вызова одного из двух из трех bar звонки. Я бы по-прежнему назвал его оптимизированным с помощью хвостового вызова, поскольку этот неоптимизированный вызов никогда не идет дальше одного уровня, даже если вы найдете call <bar+..> в сгенерированной сборке.
Я слишком ленив, чтобы посмотреть на разборку. Попробуй это:
void so(long l)
{
++l;
so(l);
}
int main(int argc, char ** argv)
{
so(0);
return 0;
}
скомпилируйте и запустите эту программу. Если он работает вечно, хвостовая рекурсия была оптимизирована. если это дует в стек, это не так.
РЕДАКТИРОВАТЬ: извините, читайте слишком быстро, ОП хочет знать, оптимизирована ли его конкретная функция. ХОРОШО...
... принцип все тот же - если хвостовая рекурсия оптимизируется, то кадр стека останется прежним. Вы должны быть в состоянии использовать функцию обратного отслеживания, чтобы захватывать кадры стека из вашей функции и определять, растут ли они или нет. Если хвостовая рекурсия оптимизируется, у вас будет только один указатель возврата в буфере.
Простой метод: создайте простую программу хвостовой рекурсии, скомпилируйте и разберите ее, чтобы увидеть, оптимизирована ли она.
Просто понял, что у вас уже было это в вашем вопросе. Если вы знаете, как читать сборку, это довольно легко сказать. Рекурсивные функции будут вызывать себя (с "меткой вызова") внутри тела функции, и цикл будет просто "меткой jmp".
Другой способ, которым я проверил это:
- Скомпилируйте ваш код с помощью 'gcc -O2'
- начать "GDB"
- Установите точку останова в функции, которую вы ожидаете оптимизировать / исключить с помощью хвостовой рекурсии
- запустить свой код
- Если это было удалено, то точка останова будет достигнута только один раз или никогда. Подробнее об этом смотрите здесь
В наши дни вы можете проверить DWARF на предметDW_AT_call_tail_callиDW_AT_call_all_callsатрибуты.
gcc -g -O2 foo.c
dwarfdump a.out
Вы получите DW_TAG_call_site, где произошел хвостовой вызов, примерно так:
< 2><0x00000174> DW_TAG_call_site
DW_AT_call_return_pc 0x000011cc
DW_AT_call_tail_call yes(1)
DW_AT_call_origin <0x000001a6>
DW_AT_sibling <0x00000192>
В стандарте DWARF5 есть подробности для этого.
Мы можем использовать
objdumpдля этого. Вот пример. Код вычисляет n-е треугольное число = 1 + 2 + ... + n:
// File tri.c
// See "-O1" vs "-O1 -foptimize-sibling-calls" to see the tail recursion optimization
#include <stdio.h>
int tri(int n, int result)
{
if (0 == n)
{
return result;
}
result += n;
--n;
return tri(n, result);
}
int main()
{
printf("%d\n", tri(36, 0)); // Prints 666 for the 36th triangular number.
return 0;
}
Для gcc 11.3.1 с
-O1отметьте, что вы получаете НЕТ оптимизации хвостовой рекурсии:
; gcc tri.c -O1
; objdump -d a.out
...
0000000000401126 <tri>:
401126: 89 f0 mov %esi,%eax
401128: 85 ff test %edi,%edi
40112a: 75 01 jne 40112d <tri+0x7>
40112c: c3 ret
40112d: 48 83 ec 08 sub $0x8,%rsp
401131: 8d 34 37 lea (%rdi,%rsi,1),%esi
401134: 83 ef 01 sub $0x1,%edi
401137: e8 ea ff ff ff call 401126 <tri> <--- The recursion call
40113c: 48 83 c4 08 add $0x8,%rsp
401140: c3 ret
...
Для gcc 11.3.1 с
-O1 gcc tri.c -O1 -foptimize-sibling-callsуказывает на то, что вы ПОЛУЧАЕТЕ оптимизацию хвостовой рекурсии:
; gcc tri.c -O1 -foptimize-sibling-calls
; objdump -d a.out
...
0000000000401126 <tri>:
401126: 89 f0 mov %esi,%eax
401128: 85 ff test %edi,%edi
40112a: 74 07 je 401133 <tri+0xd>
40112c: 01 f8 add %edi,%eax
40112e: 83 ef 01 sub $0x1,%edi
401131: 75 f9 jne 40112c <tri+0x6>
401133: c3 ret
...
Вы можете обработать входные данные, которые приведут к переполнению стека из-за слишком глубокой рекурсии вызовов этой функции, если не было никакой оптимизации, и посмотрите, произойдет ли это. Конечно, это не тривиально, а иногда достаточно большие входные данные заставят функцию работать недопустимо долго.