Подтвердить что ты не робот

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

Как узнать, оптимизирует ли gcc (точнее, g++) хвостовую рекурсию в определенной функции? (Потому что это происходит несколько раз: я не хочу проверять, может ли gcc оптимизировать хвостовую рекурсию в целом. Я хочу знать, оптимизирует ли она my хвостовую рекурсивную функцию.)

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

PS. Я знаю, что это выглядит как часть вопроса Который, если есть, компиляторы С++ делают оптимизацию хвостовой рекурсии? от 5 месяцев назад. Однако я не думаю, что эта часть этого вопроса была удовлетворительно удовлетворена. (Ответ был: "Самый простой способ проверить, выполнил ли компилятор оптимизацию (что я знаю), - это вызов, который в противном случае привел бы к переполнению стека - или просмотрел вывод сборки".)

4b9b3361

ОТВЕТЫ

Ответ 1

Используйте пример кода из другого вопроса. Скомпилируйте его, но скажите 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 оба раза), то я думаю, что разумно предположить, что оптимизация также будет выполняться без вашего инструментария, но если тест не удастся, мы не будем знать, произошел ли отказ из-за добавление кода инструментария.

Ответ 2

РЕДАКТИРОВАТЬ Мое первоначальное сообщение также помешало 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;
}

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

При тестировании это выглядит так, что моя версия GCC не оптимизирует первый хвостовой вызов, но остальные хвостовые звонки оптимизированы. Интересно.

Ответ 3

Посмотрите на сгенерированный код сборки и посмотрите, использует ли он инструкцию 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 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

При запуске над указанной функцией этот script печатает "факт хвост рекурсивный". Если вместо -O2 скомпилировать с -O3, это любопытно выводит "факт НЕ является хвостом рекурсивным".

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

Ответ 4

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

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

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

[править]

В качестве примера, когда просто поиск саморекурсивного 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+..> в сгенерированной сборке.

Ответ 5

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

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

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

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

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

Ответ 6

Еще один способ, который я проверил, это:

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

Ответ 7

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

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

Ответ 8

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