什麼是尾端遞迴最佳化(Tail Call Optimization)?

摘要

尾端呼叫最佳化(Tail Call Optimization,TCO)是一種編譯器最佳化技術,旨在減少函式於尾端位置進行呼叫時所需的執行狀態與堆疊空間。在符合語義及應用程式二進位介面(Application Binary Interface,ABI)要求的情況下,編譯器可以重用或移除目前函式的堆疊框架,將控制權直接轉移至被呼叫函式,避免不必要的呼叫層級。

當函式在尾端位置呼叫自身時,稱為尾端遞迴(Tail Recursion)。編譯器可以將這類遞迴轉換為迴圈,此技術稱為尾端遞迴消除(Tail Recursion Elimination,TRE)。

本文介紹遞迴與堆疊框架的基本原理、尾端位置的判定方式、尾端呼叫最佳化的實作機制及其限制,並分析 x86-64 與 ARM64 架構下的機器指令、LLVM 中介表示法與 GCC 編譯器的相關最佳化功能。此外,本文亦探討尾端呼叫最佳化對記憶體複雜度、執行效能、偵錯及程式語義的影響。

關鍵詞: 尾端呼叫最佳化、尾端遞迴、編譯器、堆疊框架、尾端遞迴消除、LLVM、GCC、呼叫慣例、機器碼。


一、遞迴與函式呼叫機制

1.1. 什麼是遞迴?

遞迴(Recursion)是指函式直接或間接呼叫自身,以處理可分解為較小子問題的計算過程。

遞迴演算法通常包含兩個部分:

  1. 終止條件(Base Case): 決定何時停止遞迴呼叫。
  2. 遞迴步驟(Recursive Case): 透過新的函式呼叫繼續處理規模較小的問題。

以階乘為例,非負整數 的階乘定義為:

可使用 C 語言表示:

unsigned long long factorial(unsigned int n) {
    if n==0 {
        return 1;
    }

    return n * factorial(n - 1);
}

這是一個直接遞迴函式,因為 factorial 會呼叫自身。

當 n = 4 時,邏輯上的計算過程如下:

factorial(4)
    4 * factorial(3)
        3 * factorial(2)
            2 * factorial(1)
                1 * factorial(0)
                    1

抵達終止條件後,各層函式依序完成剩餘運算:

factorial(0) = 1
factorial(1) = 1 * 1 = 1
factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6
factorial(4) = 4 * 6 = 24

此例的關鍵在於,每次遞迴呼叫返回後,原本的函式仍須執行乘法。

因此,尚未完成的計算狀態必須被保留。

1.2. 堆疊框架(Stack Frame)

當程式呼叫函式時,執行環境通常需要保存與該次呼叫相關的狀態。

這些資訊可能包括:

  • 返回位址(Return Address)。
  • 必須存放於記憶體中的區域變數。
  • 需要保存與還原的暫存器。
  • 無法完全透過暫存器傳遞的參數。
  • 計算過程使用的暫存空間。
  • 與例外處理或偵錯相關的資訊。

用於維持一次函式執行狀態的堆疊區域,通常稱為堆疊框架。

但並非所有函式呼叫都必然建立獨立的實體堆疊框架。實際配置取決於處理器架構、呼叫慣例、編譯器及最佳化設定。

在未進行適當最佳化的情況下,遞迴呼叫可能使多個函式執行狀態同時存在。

例如:

遞迴呼叫期間的邏輯堆疊

┌──────────────────────────┐
│ factorial(0)             │
├──────────────────────────┤
│ factorial(1)             │
├──────────────────────────┤
│ factorial(2)             │
├──────────────────────────┤
│ factorial(3)             │
├──────────────────────────┤
│ factorial(4)             │
├──────────────────────────┤
│ 呼叫 factorial(4) 的函式 │
└──────────────────────────┘

上述為概念示意,並不代表特定 ABI 的實際記憶體配置。

假設每層遞迴皆需保留固定大小的堆疊框架,其堆疊使用量可近似表示為:

其中:

  • :遞迴過程所需的堆疊空間。
  • :原有堆疊使用量。
  • :同時存在的遞迴呼叫層數。
  • :每層呼叫平均需要的堆疊空間。

在上述假設下,堆疊空間需求隨遞迴深度線性增加。


二、什麼是尾端遞迴?

2.1. 尾端位置(Tail Position)

尾端位置是指某個運算式的結果可以直接作為目前函式的結果,而無須在該運算完成後繼續執行其他計算的位置。

例如:

int f(int x) {
    return gx;
}

g 位於尾端位置,因為 f 直接返回 g 的結果。

相對地:

int f(int x) {
    return gx + 1;
}

此處 g 並非尾端呼叫。

原因是 g 返回後,f 仍須執行加法運算。

因此,判定尾端位置的關鍵,不是函式呼叫是否出現在程式碼的最後一行,而是呼叫完成後是否仍有必須執行的工作。

2.2. 尾端呼叫(Tail Call)

尾端呼叫是指位於尾端位置的函式呼叫。

例如:

int process(int x) {
    return calculatex;
}

其中 calculate 是尾端呼叫,但並非遞迴,因為 process 並未呼叫自身。

2.3. 尾端遞迴(Tail Recursion)

尾端遞迴是函式在尾端位置直接或間接再次呼叫自身的情況。

可將階乘函式改寫為使用累加器(Accumulator)的形式:

unsigned long long factorial_acc(
    unsigned int n,
    unsigned long long acc
) {
    if n==0 {
        return acc;
    }

    return factorial_acc(n - 1, acc * n);
}

unsigned long long factorial(unsigned int n) {
    return factorial_acc(n, 1);
}

此時,遞迴函式不再需要於返回後執行乘法。

所有中間結果已經透過 acc 傳遞至下一次呼叫。

執行 factorial(4) 時:

呼叫次序 n acc
1 4 1
2 3 4
3 2 12
4 1 24
5 0 24

尾端遞迴呼叫為:

return factorial_acc(n - 1, acc * n);

函式不必等待下一層遞迴返回後再執行額外運算。

這使該函式具有轉換為迴圈的條件。

2.4. 尾端呼叫與尾端遞迴的差異

概念 英文名稱 說明
尾端位置 Tail Position 結果直接成為函式返回值的位置
尾端呼叫 Tail Call 發生於尾端位置的函式呼叫
尾端遞迴 Tail Recursion 函式在尾端位置呼叫自身
尾端呼叫最佳化 Tail Call Optimization 消除不必要函式呼叫狀態的最佳化
尾端遞迴消除 Tail Recursion Elimination 將自我尾端遞迴轉換為迴圈或等效控制流程

尾端呼叫最佳化的適用範圍比尾端遞迴消除更廣。

因為符合條件的尾端呼叫,也可能發生於不同函式之間。


三、尾端呼叫最佳化的基本原理

3.1. 定義

尾端呼叫最佳化(Tail Call Optimization,TCO)是編譯器利用尾端位置的特性,避免保留不再需要的函式呼叫狀態,從而減少額外堆疊空間與呼叫成本的技術。

考慮以下函式:

int f(int x) {
    return gx;
}

未經最佳化時,其控制流程可能為:

f 呼叫 g
    ↓
g 執行
    ↓
g 返回 f
    ↓
f 返回原呼叫者

若符合最佳化條件,編譯器可以將其轉換為:

f 準備 g 所需的參數
    ↓
釋放或調整 f 不再需要的執行狀態
    ↓
直接跳轉至 g
    ↓
g 返回原本呼叫 f 的函式

這種處理方式可以避免維持不必要的呼叫層級。

但實際最佳化並不一定表現為單純的跳轉指令。編譯器可能需要調整暫存器、堆疊位置及其他執行狀態。

3.2. 堆疊使用方式的差異

未最佳化的遞迴呼叫:

┌────────────────────────┐
│ factorial_acc(0)       │
├────────────────────────┤
│ factorial_acc(1)       │
├────────────────────────┤
│ factorial_acc(2)       │
├────────────────────────┤
│ factorial_acc(3)       │
├────────────────────────┤
│ factorial_acc(4)       │
└────────────────────────┘

尾端遞迴消除後:

┌────────────────────────┐
│ factorial_acc          │
│                        │
│ n   = 當前參數         │
│ acc = 累積結果         │
│                        │
│ 透過迴圈更新狀態       │
└────────────────────────┘

在第二種情況下,程式不必為每次遞迴迭代保留新的函式呼叫狀態。

3.3. 記憶體複雜度

假設每層遞迴需要固定大小的執行狀態,且遞迴深度與 成正比:

未最佳化時:

成功轉換為固定狀態的迴圈後:

這裡的 指的是執行該迴圈所需的額外堆疊空間,不代表程式的所有記憶體使用量都必然為常數。

例如,演算法仍可能配置隨輸入增加的堆積記憶體(Heap Memory)。


四、尾端遞迴消除的實作機制

4.1. 將遞迴轉換為迴圈

考慮以下程式:

unsigned int sum_tail(
    unsigned int n,
    unsigned int acc
) {
    if n==0 {
        return acc;
    }

    return sum_tail(n - 1, acc + n);
}

可以在不改變此範例結果的前提下,將其轉換為:

unsigned int sum_loop(
    unsigned int n,
    unsigned int acc
) {
    while n!=0 {
        acc += n;
        n -= 1;
    }

    return acc;
}

在第二種形式中,原本的遞迴呼叫變成迴圈中的狀態更新。

因此,不再需要每次建立新的呼叫層級。

這是尾端遞迴消除最典型的實作方式之一。

4.2. 中介表示法(Intermediate Representation)

現代編譯器通常會先將原始碼轉換為中介表示法(IR),再透過最佳化階段進行分析與轉換。

在此階段中,編譯器可以辨識:

  1. 函式是否呼叫自身。
  2. 遞迴呼叫是否位於尾端位置。
  3. 呼叫返回後是否仍需執行其他運算。
  4. 是否能安全地將呼叫轉換為控制流程跳轉。
  5. 參數及區域狀態是否可以直接更新。

LLVM 的 tailcallelim 最佳化階段便是相關實作之一。

LLVM 文件說明:

This file transforms calls of the current function (self recursion) followed by a return instruction with a branch to the entry of the function, creating a loop.

(中文譯文:此最佳化將目前函式的自我遞迴呼叫及其後的返回指令,轉換為跳轉至函式入口的分支指令,從而形成迴圈。)

資料來源:LLVM,LLVM's Analysis and Transform Passes,tailcallelim。[1]

除基本形式外,LLVM 亦可在特定條件下處理部分尾端呼叫前後的簡單運算,或透過累加器等方式進行等效轉換。

4.3. x86-64 架構中的實作

在 x86-64 架構中,常見的控制流程指令包括:

指令 功能
call 呼叫函式並保存返回位址
ret 返回呼叫者
jmp 直接跳轉至指定位置

考慮:

extern int calculate(int x);

int process(int x) {
    return calculatex;
}

一般函式呼叫在概念上可表示為:

process:
    call calculate
    ret

在符合最佳化條件時,可以轉換為:

process:
    jmp calculate

使用 jmp 時,處理器不會因該跳轉而建立新的返回位址。

如果函式的執行狀態已經按照 ABI 要求安排完成,被呼叫函式便可以直接返回原先的呼叫者。

上述組語為說明原理的簡化範例,並非所有編譯器與平台必然產生的機器碼。

實際程式可能還需要額外指令來調整堆疊、恢復暫存器或配置參數。

4.4. ARM64 架構中的實作

在 AArch64 架構中,常見的控制流程指令包括:

指令 功能
BL 分支呼叫,同時設定連結暫存器
B 直接分支跳轉
RET 根據返回位址返回

AArch64 通常使用 X30 作為連結暫存器(Link Register)。

一般呼叫形式:

process:
    bl calculate
    ret

在符合條件時,可以使用:

process:
    b calculate

由於 B 不會更新連結暫存器,因此被呼叫函式可以在原有返回位址仍有效的情況下,直接返回最初的呼叫者。

但是否能進行此種轉換,仍須符合平台 ABI 與呼叫慣例。

相關規範可參考 Arm 的 AAPCS64 文件。[7]


五、尾端呼叫最佳化的必要條件

5.1. 呼叫必須處於尾端位置

最基本的條件是呼叫返回後,函式不再需要執行其他運算。

可以作為尾端呼叫:

int f(int x) {
    return gx;
}

不是尾端呼叫:

int f(int x) {
    return gx * 2;
}

第二個例子仍須等待 g 的返回值,並進行乘法運算。

但編譯器仍可能透過其他最佳化技術改寫這類程式。因此,非尾端呼叫不代表完全無法最佳化。

5.2. 必須符合呼叫慣例(Calling Convention)

呼叫慣例規定函式之間如何傳遞參數、返回結果及保存處理器狀態。

相關要求包括:

  • 用於傳遞參數的暫存器。
  • 呼叫者與被呼叫者需要保存的暫存器。
  • 返回值的表示方式。
  • 透過堆疊傳遞參數的方法。
  • 堆疊對齊要求。
  • 可變參數函式的處理方式。
  • 大型結構體或複合資料的返回方式。

即使函式呼叫在語義上處於尾端位置,如果無法遵守 ABI 所要求的狀態配置,編譯器仍可能無法直接將其轉換為尾端跳轉。

5.3. 區域變數的生命週期

考慮:

extern int use_pointer(const int *p);

int fvoid {
    int value = 10;
    return use_pointer(&value);
}

此處 use_pointer 接收區域變數 value 的位址。

若編譯器在 use_pointer 尚未完成之前,便釋放存放 value 的堆疊空間,可能使該指標失去有效的存取對象。

因此,不能在破壞變數生命週期或改變程式語義的情況下,強制移除目前函式的堆疊框架。

5.4. 資源清理與例外處理

部分語言具有在函式結束時必須執行的清理機制。

例如:

  • 物件解構函式。
  • 自動資源釋放。
  • finally 區塊。
  • 例外處理狀態更新。
  • 堆疊安全檢查。

若這些操作必須在被呼叫函式返回後執行,原始呼叫就可能不再符合直接尾端呼叫的條件。

編譯器必須保證所有必要的語義行為仍然正確。

5.5. 平台及後端限制

尾端呼叫最佳化亦受到以下因素影響:

  • CPU 架構。
  • 作業系統 ABI。
  • 編譯器後端。
  • 最佳化等級。
  • 返回值型別。
  • 函式屬性。
  • 呼叫慣例及堆疊配置。

因此,尾端遞迴的語法形式不等於編譯器必然會執行尾端遞迴消除。


六、GCC 與 LLVM 的尾端呼叫最佳化

6.1. GCC

GCC 提供以下最佳化選項:

-foptimize-sibling-calls

GCC 文件說明:

Optimize sibling and tail recursive calls.

(中文譯文:最佳化同層函式呼叫與尾端遞迴呼叫。)

在 GCC 14.3 的文件中,該選項會於 -O2、-O3 及 -Os 最佳化等級啟用。[2]

例如:

gcc -O2 -S example.c -o example.s

此指令可以輸出組合語言,供研究者檢查函式呼叫是否已被最佳化。

不過,啟用選項只代表編譯器可以嘗試相關最佳化,並不保證所有尾端呼叫都能被消除。

6.2. LLVM

LLVM IR 提供多種與尾端呼叫相關的標記。

標記 作用
tail 標示呼叫可以考慮進行尾端最佳化
musttail 在滿足嚴格限制時要求保證尾端呼叫
notail 禁止將指定呼叫標記為尾端呼叫

以下是 LLVM IR 的簡化範例:

define i32 @f(i32 %x) {
entry:
  %result = tail call i32 @g(i32 %x)
  ret i32 %result
}

declare i32 @gi32

tail 標記本身並不保證最終機器碼一定採用尾端跳轉。

相較之下,musttail 具有更嚴格的語義要求。

LLVM Language Reference 對 musttail 規定了函式型別、呼叫慣例、參數、返回型別及呼叫位置等限制。

在符合規定的情況下,編譯器必須確保尾端呼叫的正確執行語義,使此類呼叫不因額外保留不必要的呼叫框架而造成無界的堆疊增長。[3]

6.3. 最佳化機會與語義保證

對尾端遞迴的支援可分為三種情況:

  1. 原始碼具有尾端遞迴形式,但語言並未要求編譯器執行最佳化。
  2. 編譯器可以辨識尾端呼叫,並在可行時執行最佳化。
  3. 語言或中介表示法明確要求在特定條件下保證尾端呼叫。

這三種情況具有不同的可靠性要求。

對於使用深度遞迴作為主要控制流程的程式而言,是否具有尾端呼叫保證,會直接影響演算法在有限堆疊空間中的可執行性。

6.4. Scheme 的正確尾端遞迴

Scheme 是研究尾端呼叫的重要語言之一。

在 Scheme 的 R5RS 報告中,正確尾端遞迴(Proper Tail Recursion)被明確規定為語言實作要求。

原文:

Implementations of Scheme are required to be properly tail-recursive.

(中文譯文:Scheme 的實作必須支援正確的尾端遞迴。)

資料來源:Revised⁵ Report on the Algorithmic Language Scheme,第3.5節。[4]

Scheme 的要求不僅是鼓勵編譯器提升效率,而是規定執行環境應能以適當方式處理尾端呼叫,使任意數量的有效尾端呼叫不必因累積無用的返回續體而消耗不斷增加的控制空間。

這並不表示程式擁有無限記憶體,而是要求尾端呼叫本身不應造成不必要的堆疊增長。


七、效能與記憶體影響

7.1. 堆疊記憶體使用量

尾端呼叫最佳化最重要的效果,是減少不必要的堆疊空間消耗。

當尾端遞迴被轉換為迴圈時,程式不再需要為每次迭代保存新的函式呼叫狀態。

此技術對下列類型的程式可能特別重要:

  • 長度較大的序列處理。
  • 遞迴式資料結構演算法。
  • 函數式語言。
  • 直譯器與虛擬機器。
  • 使用函式呼叫表達控制流程的程式。

7.2. 函式呼叫成本

成功的尾端呼叫最佳化可能減少以下成本:

  • 返回位址的保存。
  • 堆疊框架的建立與拆除。
  • 部分暫存器保存與還原。
  • 額外的控制流程轉移。

不過,實際效能改善程度受到 CPU 微架構、編譯器、ABI 及程式特性的影響。

因此,不應假設所有尾端呼叫最佳化都會帶來顯著的執行速度提升。

7.3. 時間複雜度

以前述階乘函式為例,無論是否使用尾端遞迴,計算過程仍須執行與 成比例的乘法。

因此,其時間複雜度仍為:

若成功轉換為固定狀態的迴圈,額外堆疊空間可能由:

降低為:

這表示尾端呼叫最佳化主要改變執行方式與記憶體使用效率,而不必然改變演算法本身的時間複雜度。


八、限制與注意事項

8.1. 並非所有遞迴都是尾端遞迴

例如:

unsigned long long factorial(unsigned int n) {
    if n==0 {
        return 1;
    }

    return n * factorial(n - 1);
}

此函式的遞迴呼叫返回後仍須執行乘法,因此不屬於尾端遞迴。

某些編譯器可能透過其他方法改寫這類遞迴,但不能將其視為必然發生的最佳化。

8.2. 尾端遞迴不保證完全避免堆疊溢位

如果編譯器沒有執行最佳化,即使原始碼符合尾端遞迴形式,也可能因呼叫層級不斷增加而消耗堆疊空間。

此外,程式仍可能因其他函式呼叫、過大的區域資料或執行環境限制而發生堆疊溢位。

因此,必須區分原始碼具有尾端遞迴結構,與執行環境保證尾端呼叫最佳化這兩件事。

8.3. 對偵錯的影響

尾端呼叫被轉換為跳轉或迴圈後,偵錯器中顯示的呼叫堆疊可能與原始碼中的函式呼叫結構不同。

部分呼叫框架可能不再出現。

這可能影響:

  • 呼叫堆疊追蹤。
  • 函式執行順序分析。
  • 堆疊回溯。
  • 效能分析及取樣。

編譯器與偵錯工具可能利用額外資訊補充這些差異,但不保證所有經最佳化的呼叫歷程都能完整還原。

8.4. 與其他最佳化技術的關係

尾端呼叫最佳化可能與其他編譯器最佳化共同作用,例如:

  • 函式內聯(Inlining)。
  • 常數傳播(Constant Propagation)。
  • 死碼消除(Dead Code Elimination)。
  • 迴圈最佳化(Loop Optimization)。
  • 控制流程簡化(Control Flow Simplification)。

因此,若最終機器碼中不再出現原本的遞迴呼叫,仍需進一步分析是哪些最佳化共同產生了該結果。


九、如何驗證尾端呼叫最佳化?

9.1. 測試程式

以下使用 C 語言建立一個簡單範例:

__attribute__((noinline))
unsigned long long sum_tail(
    unsigned int n,
    unsigned long long acc
) {
    if n==0 {
        return acc;
    }

    return sum_tail(n - 1, acc + n);
}

int mainvoid {
    return sum_tail(10, 0) != 55;
}

noinline 屬性用於限制 GCC 或 Clang 將函式直接內聯至呼叫者,使其函式本身的機器碼較容易觀察。

但此屬性不會禁止所有其他最佳化,也不會自動阻止尾端遞迴消除。

9.2. 使用 GCC 測試

分別以未最佳化及較高最佳化等級編譯:

gcc -O0 -S test.c -o test_O0.s
gcc -O2 -S test.c -o test_O2.s

比較兩個輸出的組合語言檔案。

應觀察:

  • 是否仍存在對 sum_tail 的遞迴呼叫。
  • 是否出現迴圈結構。
  • 是否使用分支指令取代呼叫指令。
  • 是否減少堆疊框架的建立與拆除。

具體結果依 GCC 版本、目標架構及最佳化設定而異。

9.3. 使用 Clang 測試

clang -O0 -S test.c -o test_O0.s
clang -O2 -S test.c -o test_O2.s

若要檢查 LLVM IR,可使用:

clang -O2 -S -emit-llvm test.c -o test.ll

在 IR 或機器碼中,可以尋找下列特徵:

  • 原本的遞迴呼叫已被迴圈取代。
  • 呼叫具有與尾端最佳化相關的標記。
  • 出現取代函式呼叫的分支控制流程。
  • 堆疊配置方式發生改變。

不過,這些只是需要進一步分析的技術跡象,不能僅憑某個單一指令便確定完整的最佳化過程。


十、結論

尾端呼叫最佳化是編譯器設計與實作中的重要技術。

它利用尾端位置不再需要保留呼叫者後續運算狀態的特性,使編譯器能夠在適當條件下消除多餘的函式呼叫層級。

對於尾端遞迴而言,編譯器可以將遞迴呼叫轉換為迴圈,使執行過程不必隨著遞迴深度持續增加堆疊框架。

然而,尾端呼叫最佳化並非單純的語法轉換,其正確性受到函式呼叫慣例、ABI、資料生命週期、例外處理及編譯器後端等因素限制。

因此,理解尾端呼叫、尾端遞迴、尾端呼叫最佳化與尾端遞迴消除之間的差異,是正確認識此技術的基礎。

對編譯器研究而言,尾端呼叫最佳化亦提供了一個典型案例,展示程式語義、中介表示法、控制流程轉換及機器碼生成之間的關係。


附錄一:技術術語

中文術語 英文術語 說明
遞迴 Recursion 函式直接或間接呼叫自身
尾端位置 Tail Position 運算結果直接作為函式結果的位置
尾端呼叫 Tail Call 發生於尾端位置的函式呼叫
尾端遞迴 Tail Recursion 函式在尾端位置呼叫自身
尾端呼叫最佳化 Tail Call Optimization 避免保留不必要呼叫狀態的最佳化
尾端遞迴消除 Tail Recursion Elimination 將自我尾端遞迴轉換為迴圈或等效控制流程
堆疊框架 Stack Frame 維持一次函式執行狀態的記憶體與相關資訊
呼叫慣例 Calling Convention 函式間傳遞參數、返回結果及保存狀態的規則
應用程式二進位介面 Application Binary Interface 規範程式二進位層級互動的介面
中介表示法 Intermediate Representation 編譯器用於分析及最佳化的程式表示形式
累加器 Accumulator 保存中間計算結果的變數或狀態
返回位址 Return Address 函式結束後繼續執行的位置
函式內聯 Inlining 將函式呼叫轉換為相應函式內容的最佳化

附錄二:參考文獻與延伸閱讀

A. 編譯器技術文件

[1] LLVM Project, LLVM's Analysis and Transform Passes.

說明 LLVM 的 tailcallelim 最佳化階段,以及將自我尾端遞迴轉換為迴圈的原理。

https://llvm.org/docs/Passes.html

[2] GNU Compiler Collection, Optimize Options.

說明 -foptimize-sibling-calls 選項及不同最佳化等級的相關設定。

https://gcc.gnu.org/onlinedocs/gcc-14.3.0/gcc/Optimize-Options.html

[3] LLVM Project, LLVM Language Reference Manual.

LLVM IR 官方規格,包含 tail、musttail、notail 及呼叫慣例等內容。

https://llvm.org/docs/LangRef.html

[4] Clang Project, Attribute Reference.

提供 musttail 等函式呼叫相關屬性的規範與限制。

https://clang.llvm.org/docs/AttributeReference.html

B. 程式語言與尾端遞迴研究

[5] Richard Kelsey, William Clinger, Jonathan Rees(編),Revised⁵ Report on the Algorithmic Language Scheme,1998。

第3.5節「Proper Tail Recursion」規定 Scheme 正確尾端遞迴的要求。

https://www.gnu.org/software/guile/manual/r5rs/Proper-tail-recursion.html

[6] Guy L. Steele Jr.、Gerald Jay Sussman,Lambda: The Ultimate Imperative,MIT Artificial Intelligence Laboratory,AI Memo 353,1976。

探討 Scheme 語言、續體及函式呼叫執行模型的重要早期研究。

C. 處理器架構與 ABI 規範

[7] Arm Limited, Procedure Call Standard for the Arm 64-bit Architecture(AAPCS64).

AArch64 的官方程序呼叫規範,涉及暫存器、參數傳遞、返回值及堆疊使用。

https://github.com/ARM-software/abi-aa/blob/main/aapcs64/aapcs64.rst

[8] System V Application Binary Interface, AMD64 Architecture Processor Supplement.

x86-64 System V ABI 規範,包含函式呼叫慣例、暫存器使用及堆疊配置。

https://gitlab.com/x86-psABIs/x86-64-ABI

[9] Intel, Intel 64 and IA-32 Architectures Software Developer's Manuals.

x86 指令集官方文件,包含 CALL、RET、JMP 等指令。

https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html

D. 建議延伸閱讀主題

  1. 堆疊框架(Stack Frame)的構造與生命週期。
  2. 堆疊溢位(Stack Overflow)的成因與防護。
  3. 呼叫慣例與應用程式二進位介面(ABI)。
  4. 中介表示法(IR)與控制流程最佳化。
  5. 連結器(Linker)在編譯與執行流程中的角色。

註釋

  1. LLVM Project, LLVM's Analysis and Transform Passes, tailcallelim。https://llvm.org/docs/Passes.html ↩
  2. GNU Compiler Collection, Optimize Options, GCC 14.3,-foptimize-sibling-calls。https://gcc.gnu.org/onlinedocs/gcc-14.3.0/gcc/Optimize-Options.html ↩
  3. LLVM Project, LLVM Language Reference Manual, call、tail、musttail。https://llvm.org/docs/LangRef.html ↩
  4. Revised⁵ Report on the Algorithmic Language Scheme, §3.5, Proper Tail Recursion。https://www.gnu.org/software/guile/manual/r5rs/Proper-tail-recursion.html ↩