現代編譯器優化竟然可以作國中等級的代數運算？
這篇是我 2018 年在 stackoverflow 發的問題，當時在 stackoverflow 上也有不少討論，也讓我賺了不少 stackoverflow 點數，最近有機會重新整理一下這篇文章，寫在自己的網站上。
在進入程式主題之前，我們來看一個國中等級的遞迴數學式： $$ \left\lbrace\begin{aligned} a_1 &= 1\\a_n &= a_{n-1}+1 \end{aligned}\right. $$
隨便帶入幾個數字 $$a_1 = 1,~a_2 = 2,~a_3 = 3\cdots$$
有學過國中數學的話都可以用歸納法算出： $$a_n = n \qquad \forall n \in \mathcal{Z}$$
把這個數學式寫成 C++ 程式也不是什麼困難的事情：
1int Identity(int i) {
2 if (i == 1)
3 return 1;
4 else
5 return Identity(i-1)+1;
6}現在重要的問題來了，把這個程式碼交給現代編譯器優化之後會得到什麼呢？
1$ gcc -c a.c -O2 && objdump -d a.o # gcc 10.2.0
2.text 區段的反組譯：
3
40000000000000000 <Identity>:
5 0: 89 f8 mov %edi,%eax
6 2: c3 retq嗯？只有一行耶，這行的意思是什麼呢？x86_64 裡面 %edi 是放第一個函數傳入值的（也就是那個 i），%eax 是回傳值。把 %edi 移動到 %eax 就是說這個函數經過 compiler 優化後就是直接 return i。這也太神奇了吧，難道現在的 compiler 內建人工智慧，會算我到了國中才會的運算嗎？
Stackoverflow 的解答
現代的編譯器具有 tail call optimization (TCO) 的功能，最基本的功能就是說假設一個函數的最後一個動作是呼叫另外一個函數，則可以把呼叫的動作直接改成跳躍。例如：
1int foo1(int data) { // TCO
2 int ret = a(data);
3 return ret;
4}上面這個是 TCO，而下面這個因為多了一個加法的步驟，所以不是：
1int foo2(int data) { // no TCO
2 return a(data) + 1;
3}回到前面的 int Identity(int i)，看起來遠比上面的例子複雜，不僅包含了遞迴、也包含了額外的一個加法，感覺無法應用 TCO。幸好，現代編譯器的功能遠超過 TCO，透過程式碼區段的分析，可以把程式碼變成迴圈：
1// Equivalent to return i
2int Identity_v2(int x) {
3 int ans = 1;
4 for (int i = x; i != 1; i--, ans++) {}
5 return ans;
6}接著，現代的編譯器對於等差級數的變數也會作優化，這種優化對於 loop 時存取連續位置的 pointer 很實用（最常見的就是 std::vector），可以簡化許多共通的計算。具體而言，本例中的優化步驟大致如下：
- 經過 L 次迴圈之後，
i = x-L且ans = 1+L - 因為迴圈在
i = 1的時候會結束，也就是L = x-1 - 帶入之後得到迴圈結束時
ans = L。←得到我們要的結論了！
為了驗證這件事情，我測試了下面的程式碼：
1// Equivalent to return i >= 0 ? i : 0
2int Identity_v3(int x) {
3 int ans = 0;
4 for (int i = x; i >= 0; i--, ans++) {}
5 return ans;
6}編譯出來的成品的確是等同於 i >= 0 ? i : 0 的指令。
透過這樣的說明，我們知道了編譯器當然不是用人工智慧在算國中數學，而是透過多個步驟的轉換把程式碼轉為常數計算而已。
最後，有一個小地方可以補充說明，不論是 Identity 或是 Identity_v2 把負數傳進去都會減到 overflow 為止，應該是要 return INT_MAX 才對。不過因為 C++ 中 signed overflow 的規範是 undefined behaviour，所以編譯器直接無視這個可能了。