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

РЕДАКТИРОВАНИЕ Мое исходное сообщение также предотвратило GCC от фактического выполнения последнего вызова eliminations. Я добавил, что некоторая дополнительная ловкость ниже этого дурачит GCC в выполнение устранения последнего вызова так или иначе.

Подробно останавливающийся на ответе Steven, можно программно проверить, чтобы видеть, есть ли у Вас тот же стековый фрейм:

#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);
}

Компиляция как [1 113]

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 
, Когда работал на вышеупомянутой функции, этот факт "печати сценария является рекурсивным хвостом". Когда вместо этого скомпилировано с -O3 вместо -O2, это любопытно печатает "факт, не рекурсивный хвост". 
 
 Примечание, что это могло бы привести к ложным отрицательным сторонам, как ehemient указанный в его комментарии. Этот сценарий только приведет к правильному ответу, если функция не будет содержать рекурсивных вызовов себя вообще, и это также не обнаруживает одноуровневую рекурсию (например, где A() вызовы B(), который звонит A()). Я не могу думать о более устойчивом методе в данный момент, который не включает наличие человека, смотрят на сгенерированный блок, но по крайней мере можно использовать этот сценарий для легкого захвата блока, соответствующего конкретной функции в объектном файле. 
 | 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, это любопытно печатает "факт, не рекурсивный хвост".

Примечание, что это могло бы привести к ложным отрицательным сторонам, как ehemient указанный в его комментарии. Этот сценарий только приведет к правильному ответу, если функция не будет содержать рекурсивных вызовов себя вообще, и это также не обнаруживает одноуровневую рекурсию (например, где A() вызовы B(), который звонит A()). Я не могу думать о более устойчивом методе в данный момент, который не включает наличие человека, смотрят на сгенерированный блок, но по крайней мере можно использовать этот сценарий для легкого захвата блока, соответствующего конкретной функции в объектном файле.

я слишком ленив для рассмотрения дизассемблирования. Попробуйте это:

void so(long l)
{
    ++l;
    so(l);
}
int main(int argc, char ** argv)
{
    so(0);
    return 0;
}

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

РЕДАКТИРОВАНИЕ: извините, читайте слишком быстро, OP хочет знать, оптимизировали ли его конкретной функции ее хвостовую рекурсию далеко. Хорошо...

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

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

Просто понял, что у Вас уже было это в Вашем вопросе. Если Вы знаете, как считать блок, довольно легко сказать. Рекурсивные функции назовут себя (с "вызовом, маркируют") from within the function body, and a loop will be just "jmp маркировкой".

Подробно останавливаясь на ответе 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 <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    $0x10,%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 от цикла или условного выражения, не смотря на него. Это мог бы быть условный переход вместо a jmp. gcc мог бы оставить a 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 вызовы. Я все еще назвал бы оптимизированным последним вызовом, с тех пор который единственный неоптимизированный вызов никогда не идет далее, чем единственный уровень, даже при том, что Вы найдете a call <bar+..> в сгенерированном блоке.

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

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