2000-LLVM#

案件摘要#

2000 年，伊利諾大學香檳分校（UIUC）的研究生 Chris Lattner 開始一項學術專案：把編譯器拆成「可重用的模組化庫」，以 SSA 為核心的低階虛擬機 IR（LLVM IR）連接任何前端與任何後端。2003 年論文發表，2005 年 Apple 資助讓專案起飛。二十多年後，LLVM 從一份學術計畫變成全世界編譯器的基礎建設——Rust、Swift、Julia、Zig、Clang，連 AMD 與 NVIDIA 的 GPU 編譯器皆基於它。編譯器從「一體成型」變成「樂高積木」。

前因 -- 為什麼會有這個案子#

• GCC 的巨大與封閉：GCC 是 1990s 的事實標準，但它是「一體成型」的巨獸——數十萬行 C 代碼，內部耦合緊密；授權是 GPL（連結 GPL 庫會傳染授權），商業公司（如 Apple）無法安心用它做產品與 IDE 整合。
• 新語言的困局：每個新語言（C、Fortran、Ada…）要支援 \(M\) 個平台（x86、ARM、PowerPC…），就得寫 \(M\) 套後端；每個新平台要支援 \(N\) 種語言，就得寫 \(N\) 套前端。三段式架構（前端 → IR → 後端）的概念早就存在，但沒有一個真正可重用的 IR 實現。
• 1991 的線索：SSA 形式（見 1991-SSA形式）已成為優化的最佳骨架，但 GCC 把 SSA 埋在內部深處，外部無法取用。Lattner 的推理：何不以 SSA 為核心，做一個乾淨、模組化、可連結的編譯器基礎設施？
• 蘋果的困境：Apple 的 Xcode 需要「解析 + 補全 + 重構 + 編譯」一體的編譯器服務，GCC 的架構與授權都做不到——Apple 成為 LLVM 的最大金主（2005 年起）。

線索與推理 -- 數學式、程式、理論#

核心推理：編譯器 = 可重用的模組化庫#

Lattner 的宣言：編譯器不該是一體成型的巨獸，而該是一堆可獨立連結的庫（libraries）——前端庫、優化庫、後端庫，任何一塊都能單獨拆下來重用。LLVM 的三段式架構：

中間層 LLVM IR 是一種 SSA 風格、型別化、顯式控制流的低階語言——它足夠低階（能表達任何機器的運算），又足夠高階（保留型別與別名資訊供優化）。

前端 × 後端的組合數分析#

這是三段式架構的數學核心。若有 \(m\) 種語言、 \(n\) 個平台：

• 一體成型（無 IR）：每種語言要為每個平台寫一個編譯器，總工作量 \(m \times n\) 。
• 三段式（有共用 IR）： \(m\) 個前端 + \(n\) 個後端，總工作量 \(m + n\) 。

當 \(m = n = 20\) ： \(400\) 個編譯器 vs \(40\) 個模組——節省一個數量級。這就是 LLVM 讓「任何前端 + 任何後端自由組合」的數學理由，也是所有新語言（Swift、Rust、Julia、Zig）選擇 LLVM 而不自建後端的原因。

LLVM IR 範例：SSA 風格的 .ll 代碼#

C 函數 int add(int a, int b) { return a + b * 2; } 編譯成 LLVM IR：

; add.ll — LLVM IR 是 SSA 形式：%1, %2, %3 各只賦值一次
define i32 @add(i32 %a, i32 %b) {
entry:
  %1 = mul i32 %b, 2        ; %b * 2
  %2 = add i32 %a, %1       ; %a + (%b * 2)
  ret i32 %2
}

優化（opt -O2）後再 lowering，x86-64 會變成：

add:
        lea  eax, [rdi + rsi*2]   ; 一條指令完成 a + b*2（位址運算的複用）
        ret

關鍵意義：IR 中的 %1、%2 是 SSA 版本，優化器（如 GVN）可無痛追蹤值；lea 指令選擇則展現後端的機器相關智慧——前端與後端各自專精，IR 是兩者的通用語言。

Python 模擬：模組化組合數#

# 三段式架構的組合數分析：m*n vs m+n
langs = ['C', 'C++', 'Swift', 'Rust', 'Julia', 'Zig', 'Fortran', 'Ada']  # m = 8
targets = ['x86', 'ARM', 'RISCV', 'AMDGPU', 'WASM', 'PowerPC']           # n = 6

monolithic = len(langs) * len(targets)   # 一體成型：8 × 6 = 48 套編譯器
modular    = len(langs) + len(targets)   # 三段式：8 前端 + 6 後端 = 14 個模組

print(f"一體成型: {monolithic} 套   三段式: {modular} 個模組")
print(f"節省: {monolithic/modular:.1f}x")

# 新增一種語言的邊際成本：
# 一體成型要寫 n 套後端（6 套），三段式只要寫 1 個前端（連接現有 IR）。
print(f"新增 1 種語言的成本: 一體成型 {len(targets)} 套後端 vs 三段式 1 個前端")

輸出顯示 48 vs 14——**樂高積木式的模組化，讓編譯器的邊際開發成本從 \(O(n)\) 降到 \(O(1)\) **。這正是 Lattner 推理的威力。

結案 -- 後果與影響#

• Apple 落地：2005 年 Apple 資助 LLVM，Clang（C/C++/Objective-C 前端）成為 Xcode 預設編譯器；Swift、Metal Shading Language 皆建在 LLVM 上。
• 成為世界基礎建設：Rust、Swift、Julia、Zig、Crystal 前端選擇 LLVM；AMD、NVIDIA 的 GPU 編譯器、TensorFlow/XLA 的後端也用它——LLVM 從學術專案變成全世界的編譯器作業系統。
• 工具革命：Clang 的庫化架構讓 clangd（語意補全）、clang-tidy（靜態檢查）、clang-format 成為可能——編譯器第一次能以「服務」而非「命令列工具」的姿態存在。
• 新語言的春天：因為後端現成，新語言的開發成本從「寫 \(n\) 套後端」降到「寫 1 個前端」——2010s 語言爆發（Rust 2010、Swift 2014、Julia 2012、Zig 2016）直接受益於此。
• 考古定位：Lattner 的論文被引用超過萬次；他本人後來又以 MLIR（2019，見 2017-WebAssembly與MLIR）再度翻案——單一 IR 不夠時，就做「IR 的 IR」。

關鍵人物與文獻#

• Chris Lattner（UIUC → Apple → Tesla → Google → SiFive → Modular）：LLVM、Clang、Swift、MLIR 之父。
• Vikram Adve（UIUC）：Lattner 的指導教授，論文共同作者。
• 文獻：
• C. Lattner, V. Adve, "LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation," CGO 2004.
• C. Lattner et al., "LLVM: A Scalable Compilation System," International Journal of Parallel Programming 32(3), 2004.
• C. Lattner et al., "MLIR: Scaling Compiler Infrastructure for Domain Specific Computation," CGO 2021.