Как компилятор так хорошо оптимизирует эту факториальную функцию?

Question

Итак, я взглянул на магию, которая O3 в GCC (ну, на самом деле, я компилирую с использованием Clang, но то же самое с GCC, и я предполагаю, что большая часть оптимизатора была вытянутаиз GCC в Clang).

Рассмотрим эту программу на C:

int foo(int n) {
    if (n == 0) return 1;
    return n * foo(n-1);
}

int main() {
    return foo(10);
}

Первое, на чем я был довольно удивлен (что было также замечено в этом вопросе - https://stackoverflow.com/a/414774/1068248) - это то, как int foo(int) (базовая факториальная функция) компилируется в плотный цикл. Это ARM-сборка для него:

    .globl  _foo
    .align  2
    .code   16
    .thumb_func _foo
_foo:
    mov r1, r0
    movs    r0, #1
    cbz r1, LBB0_2
LBB0_1:
    muls    r0, r1, r0
    subs    r1, #1
    bne LBB0_1
LBB0_2:
    bx  lr

Блимей, подумал я. Это довольно интересно! Полностью плотный циклчтобы сделать факториал. WOW. Это не оптимизация хвостового вызова, так как, ну, это не хвостовой вызов. Но похоже, что он сделал очень похожую оптимизацию.

Теперь посмотрите на main:

    .globl  _main
    .align  2
    .code   16
    .thumb_func _main
_main:
    movw    r0, #24320
    movt    r0, #55
    bx  lr

Это просто взорвало мой разум, если честно. Это просто полностью игнорирует foo и возвращает 3628800, то есть 10!.

Это заставляет меня действительно понять, как часто ваш компилятор может делатьгораздо лучшая работа, чем вы можете в Optimэто ваш код.Но возникает вопрос, как ему удается делать такую ​​хорошую работу ?Итак, может ли кто-нибудь объяснить (возможно, путем ссылки на соответствующий код), как работают следующие оптимизации:

1. Первоначальная оптимизация foo должна быть жесткой петлей.

2. Оптимизация, при которой main просто идет и возвращает результат напрямую, а не фактически выполняет foo.

Также еще один интересный побочный эффект этого вопроса - показатьеще несколько интересных оптимизаций, которые может выполнять GCC / Clang.

Answer 1

Если вы скомпилируете с gcc -O3 -fdump-tree-all, вы увидите, что первый дамп, в котором рекурсия была превращена в цикл, это foo.c.035t.tailr1.Это означает, что та же самая оптимизация, которая обрабатывает другие хвостовые вызовы, также обрабатывает этот слегка расширенный случай.Рекурсию в форме n * foo(...) или n + foo(...) не так сложно обработать вручную (см. Ниже), и, поскольку можно точно описать, как компилятор может выполнить эту оптимизацию автоматически.

Оптимизацияmain намного проще: встраивание может превратить это в 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * 1, и если все операнды умножения являются константами, то умножение может быть выполнено во время компиляции.

Обновление : Вот как вы можете вручную удалить рекурсию из foo, что можно сделать автоматически.Я не говорю, что это метод, используемый GCC, но это одна из реальных возможностей.

Сначала создайте вспомогательную функцию.Он ведет себя точно так же, как foo(n), за исключением того, что его результаты умножаются на дополнительный параметр f.

int foo(int n)
{
    return foo_helper(n, 1);
}

int foo_helper(int n, int f)
{
    if (n == 0) return f * 1;
    return f * n * foo(n-1);
}

Затем превращайте рекурсивные вызовы foo в рекурсивные вызовы foo_helper и полагайтесьна параметр factor, чтобы избавиться от умножения.

int foo(int n)
{
    return foo_helper(n, 1);
}

int foo_helper(int n, int f)
{
    if (n == 0) return f;
    return foo_helper(n-1, f * n);
}

Превратите это в цикл:

int foo(int n)
{
    return foo_helper(n, 1);
}

int foo_helper(int n, int f)
{
restart:
    if (n == 0) return f;
    {
        int newn = n-1;
        int newf = f * n;
        n = newn;
        f = newf;
        goto restart;
    }
}

Наконец, встроенный foo_helper:

int foo(int n)
{
    int f = 1;
restart:
    if (n == 0) return f;
    {
        int newn = n-1;
        int newf = f * n;
        n = newn;
        f = newf;
        goto restart;
    }
}

(Естественно, это не самый разумный способ написать функцию вручную.)