跳轉到

5.3 目標碼產生與 LLVM/GCC 生態系#

目標碼產生的三大任務#

從最佳化後的 IR 到可執行碼，後端要做三件事：

  1. 指令選擇（instruction selection）：把 IR 指令映射為機器指令，儘量選到複合指令（如 x86 的 lea rax, [rdi+rsi*4] 同時完成加法與比例乘法）。
  2. 暫存器配置（register allocation）：見 5.2。
  3. 指令排程（instruction scheduling）：重排指令以隱藏延遲（load 延遲、分支、管線氣泡），RISC 機器尤其重要。

之後還有目標碼輸出：組合語言或直接產生目的碼（object file, ELF/Mach-O/COFF），連結器把多個目的檔與函式庫合成執行檔。

指令選擇的方法#

  • 樹覆蓋（tree covering）：把 IR 樹以「指令樣式樹」覆蓋，動態規劃求最小成本——Fraser、Hanson、Proebsting 的 burg（1992）為代表。
  • 模式匹配表：GCC 的 .md 機器描述、LLVM 的 TableGen InstrInfo.td，由 DSL 產生選擇器。
  • 貪心/貪婪合併：先逐條映射，再將常見組合（cmp+branch、mul+add）合併為單指令。
  • 延遲指令選擇（lazy code motion on DAG）：LLVM 的 SelectionDAG 把基本塊轉為 DAG，再做合法化、最佳化、選擇三階段；新一代 GlobalISel（2016 起）以通用 IR 三階段（legalize → combine → select）取代之，適合 JIT 與快速後端。

GCC：1987 至今的巨獸#

1985 年 Richard Stallman 開始撰寫 GCC，1987 年發布 1.0，是 GNU 計畫的第一個大型程式，也是自由軟體運動的旗艦。技術演進：

  • RTL（Register Transfer Language）作為中間碼，語義低階、貼近機器。
  • 2000 年代引入 GIMPLE/Tree SSA（Diego Novillo 等人主導，GCC 4.0, 2005）——把 SSA 引入中端，最佳化能力大躍進。
  • 支援 60+ 前端語言、30+ 目標架構，是 Linux 發行版與嵌入式世界的基石。
  • 授權 GPLv3；開發流程以年度發行、郵件列表審查聞名。

LLVM：模組化與新世代#

Chris Lattner 於 2000 年在伊利諾大學香檳分校（與 Vikram Adve）提出 LLVM（Low Level Virtual Machine），2003 年首屆論文，2005 年 Apple 聘請 Lattner 將 LLVM 用於 Objective-C 與後來的 Swift、Metal。設計哲學：

  • 三段式：前端（Clang、Rustc、Swift）→ LLVM IR → 各架構後端。中端最佳化（opt）與後端（llc）可獨立重用。
  • IR 即 SSA：型別化、人類可讀的 .ll 語法，llvm-as/llvm-dis 可往返。
  • 庫而非工具：以 C++ 函式庫提供一切，JIT（MCJIT、ORC）可內嵌，成為語言實作的主流地基。
; add(a, b) -> a + b
define i32 @add(i32 %a, i32 %b) {
entry:
  %sum = add i32 %a, %b
  ret i32 %sum
}

生態延伸：

  • Clang（2007 起）：C/C++/Objective-C 前端，錯誤訊息品質與編譯速度大幅超越當年 GCC，並提供 libclang 驅動 IDE（clangd）。
  • MLIR（Lattner 等, 2019）：多層次 IR 基礎設施，支援 Tensor/算子層（機器學習編譯器如 IREE、XLA 的橋樑）。
  • Rust（rustc）、Swift、Zig、Julia、Crystal 等新語言皆以 LLVM 為後端。

連結、載入與 LTO#

  • 連結器：GNU ld、gold、lld（LLVM, 2017 達到生產品質，速度比 ld 快數倍）。
  • LTO（Link-Time Optimization）：把 IR 保留在目的檔中，連結時跨模組最佳化（內聯跨檔案、死碼刪除整庫）；GCC 與 LLVM 皆支援，ThinLTO 以平行方式規模化。
  • PIE/ASLR、重定位（relocation）、符號解析（symbol resolution）屬於系統程式範疇。

現代編譯器架構觀察#

  • 分層 IR：MLIR 提議「多層、可插拔的 IR 家族」對應高階（張量）、中階（SSA）、低階（機器）各種抽象。
  • 增量編譯：Rust 的 incremental compilation、Swift 的模組化前端，支援 IDE 即時回饋。
  • JIT/AOT 融合：GraalVM（Oracle, 2019）以 Java 實作多語言執行期；V8 的 Turbofan/Sparkplug 分層編譯。
  • AI 時代的編譯器：XLA、TVM（Tianqi Chen, 2018）、MLIR 把「算子排程」變成新的後端問題，理論基礎（多面體模型 polyhedral model）重新熱門。

小結#

  • 指令選擇、暫存器配置、指令排程是後端三支柱，機器描述（GCC .md、LLVM TableGen）驅動自動化。
  • GCC（1987, Stallman）與 LLVM（2000, Lattner/Adve）代表兩種工程哲學：整合巨型 vs. 模組化庫。
  • 連結器、LTO、MLIR 構成現代編譯基礎設施，AI 時代使編譯器理論再度成為顯學。