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

Question

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

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

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

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

Answer 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;
}

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

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

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

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

Я не думаю, что вы можете сделать это программно; слишком много возможных вариаций «Мясо» функции может быть ближе или дальше от начала, и вы не сможете отличить это 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. Я бы по-прежнему назвал его оптимизированным с помощью tail-call, поскольку этот неоптимизированный вызов никогда не идет дальше одного уровня, даже если вы найдете call <bar+..> в сгенерированной сборке.

Answer 5

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

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

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

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

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

Answer 6

Другой способ проверить это:

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

Answer 7

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

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

Answer 8

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