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

Итак, я посмотрел на некоторые из волшебных возможностей 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! .

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

1. Оптимизация начального foo, чтобы быть узким циклом.

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

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