編譯器如何優化這個階乘函數？

Question

所以我一直在看一些在GCC中的O3的一些魔術（其實我正在使用Clang進行編譯，但它與GCC一樣，我猜猜優化器的很大一部分是從GCC中拉出來的到Clang）。

考慮這個C程序：

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

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

的第一件事，我非常WOW-ED的（這也是在這個問題WOW-ED - 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 

Blimey我想。這很有趣！完全緊密循環做階乘。哇。這不是一個尾巴呼叫優化，因爲它不是尾巴呼叫。但它似乎做了很多類似的優化。

現在看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可以做的更有趣的優化。

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遞歸調用，並依靠要素參數擺脫乘法。

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

（當然，這不是手工編寫函數的最明智的方式。）