Как проверить, выполняет ли gcc оптимизацию хвостовой рекурсии?

редактировать мой оригинальный пост также помешал 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 параметр check. В противном случае передать в Oracle. Если хвост рекурсивный вызов, который должен был устранено не было, тогда вы будете проинформированы во время выполнения.

при тестировании этого, похоже, что моя версия 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*\(.\)//')
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()). Я не могу думать о более надежный метод на данный момент, который не включает в себя человеческий взгляд на сгенерированную сборку, но, по крайней мере, вы можете использовать этот скрипт, чтобы легко захватить сборку, соответствующую определенной функции в объектном файле.

расширяя ответ Политинкера, вот конкретный пример.

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 <foo>:
   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                   test   %edx,%edx
   b:   74 16                   je     23 <foo+0x23>
   d:   85 c0                   test   %eax,%eax
   f:   74 12                   je     23 <foo+0x23>
  11:   51                      push   %ecx
  12:   48                      dec    %eax
  13:   51                      push   %ecx
  14:   50                      push   %eax
  15:   8d 42 ff                lea    -0x1(%edx),%eax
  18:   50                      push   %eax
  19:   e8 fc ff ff ff          call   1a <foo+0x1a>
  1e:   83 c4 10                add    x10,%esp
  21:   eb 02                   jmp    25 <foo+0x25>
  23:   01 d0                   add    %edx,%eax
  25:   c9                      leave
  26:   c3                      ret

i686-pc-linux-gnu-gcc-4.3.2 -Os выход:

00000000 <foo>:
   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                   test   %edx,%edx
   b:   74 08                   je     15 <foo+0x15>
   d:   85 c0                   test   %eax,%eax
   f:   74 04                   je     15 <foo+0x15>
  11:   48                      dec    %eax
  12:   4a                      dec    %edx
  13:   eb f4                   jmp    9 <foo+0x9>
  15:   5d                      pop    %ebp
  16:   01 d0                   add    %edx,%eax
  18:   c3                      ret

в первом случае <foo+0x11>-<foo+0x1d> толкает аргументы для вызова функции, в то время как во втором случае <foo+0x11>-<foo+0x14> изменяет переменные и jmps к той же функции, где-то после преамбулы. Это то, что вы хотите искать.

я не думаю, что вы можете сделать это программным путем; слишком много возможных вариантов. "Мясо" функции может быть ближе или дальше от начала, и вы не можете различить, что jmp из цикла или условного, не глядя на него. Это может быть условный прыжок вместо jmp. gcc может оставить call в некоторых случаях, но применить оптимизацию вызова брата к другим случаям.

FYI, "братские вызовы" gcc немного более общие, чем хвостовые рекурсивные вызовы-эффективно, любой вызов функции, где повторное использование тот же кадр стека в порядке-это потенциально братский вызов.

[edit]

в качестве примера, когда просто ищет саморекурсивный 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;
}

скомпилируйте и запустите эту программу. Если он работает вечно, хвостовая рекурсия была оптимизирована. если он взрывает стек, это не так.

EDIT: извините, читать слишком быстро, ОП хочет знать, если его особая функция имеет свой хвост-рекурсия оптимизировать его. ЛАДНО...

...принцип все тот же - если хвостовая рекурсия оптимизируется, то кадр стека будет остаться прежним. Вы должны быть в состоянии использовать функция backtrace чтобы захватить кадры стека из вашей функции и определить, растут ли они или нет. Если хвостовая рекурсия оптимизируется, у вас будет только один указатель возврата в буфере.

другой способ, которым я проверил это:

1. скомпилируйте свой код с помощью 'gcc-O2'
2. start 'gdb'
3. поместите точку останова в функцию, которую вы ожидаете, чтобы быть хвост-рекурсия оптимизирована / устранена
4. запустить ваш код
5. Если это был хвостовой вызов устранен, то точка останова будет поражена только один раз или никогда. Подробнее об этом см. этой

простой метод: построить простую программу хвостовой рекурсии, скомпилировать его и скрыть его, чтобы увидеть, если он оптимизирован.

просто понял, что у вас уже было это в вашем вопросе. Если вы знаете, как читать сборку, это довольно легко сказать. Рекурсивные функции будут вызывать себя (с "меткой вызова") из тела функции, а цикл будет просто "меткой jmp".

вы можете создать входные данные, которые приведут к переполнению стека из-за слишком глубокой рекурсии вызовов этой функции, если не будет оптимизации, и посмотреть, произойдет ли это. Конечно, это не тривиально, и иногда достаточно большие входы заставят функцию работать в течение невыносимо длительного периода времени.