# 從零開始建構 C 語言最佳化編譯器
> 陳孟鴻, jserv

{%hackmd @coscup/BkyL5IdFA %}

:information_source: **[簡報檔案](https://docs.google.com/presentation/d/1RoSFZQdy4dqEYR9LRI5ShIFA_LMMlCmJImKIN3V_ry0/edit?usp=sharing)**

## 簡介
儘管許多大學開設編譯器課程，其中若干的資訊系仍將其列為必修，但隨著異質多核在內運算模型的變遷，編譯器技術隨之已有相當不同的面貌。但絕大多數的大學課程僅能勉強涵蓋到語法解析與產生指令，遑論要探討各式最佳化議題。

本議程將介紹一項從無到有開發 C 語言編譯器的嘗試：首先實作 C 語言的解析器與支援 Arm 和 RISC-V 處理器架構的編譯器後端，使其能不依賴任何組譯器或連結器達成自我編譯 ([self-hosting](https://en.wikipedia.org/wiki/Self-hosting_(compilers)))，隨後引入 SSA (static single assignment form) 及一系列的最佳化策略，以大約七千行 C 程式碼建構小而精巧的最佳化編譯器: [shecc](https://github.com/sysprog21/shecc)。
> shecc 是以女子天團命名的開放原始碼編譯器專案，讀法: s-h-e-c-c，如同 S.H.E.，亦可讀成 [ʃek]

請善用 [2024 年系統軟體系列課程討論區](https://www.facebook.com/groups/system.software2024)


## 經典的編譯流程
取自《Compilers: Principles, Techniques, and Tools (2/e)》編譯器無所不在，是資訊科技的基石。
涵蓋分詞(tokenizer)、語法/語意分析、中間程式碼產生、中間表示式(IR)、與硬體無關的最佳化、針對標的架構的程式碼產生器，和一系列最佳化。

## shecc 的 bootstrapping
從無到有建構 C 語言編譯器的前端和後端，顧及最佳化需求，引入額外的中端（middle-end）來銜接前後及後端。
1. stage0: 用 gcc/clang/MSVC 編譯，產生可執行檔 `out/shecc`，針對原生的處理器架構。本身是 cross compiler (交叉編譯器)
2. stage1: 用 stage0 產生的程式編譯 shecc 原始程式碼，產生的執行檔 `out/shecc-stage1.elf` 使用 ArmV7 或 RISC-V 指令集
3. stage2: 用 stage1 產生的 `out/shecc-stage1.elf` 編譯自己

檢驗 bootstrapping 的方式：`out/shecc-stage1.elf` 和 `out/shecc-stage2.elf` 二者內容應該完全相同

## 控制流圖 (control-flow graph, CFG) 分析
為了確保最佳化後的程式碼能維持正確的執行順序，許多現代最佳化編譯器都用控制流圖來記錄各個基本區塊 (basic block，程式碼單一入口，單一出口的區域，簡稱 BB) 間的關係，並且可藉由 分析 CFG 來取得程式的可達性 (reachability) 與支配性 (domination)。

基本區塊為組成 CFG 的基本單元，為一系列不具分支的指令序列，執行時會由第一條指令開始依序執行。CFG 由許多基本區塊節點所組成，節點與節點 間的有向邊 (directed edge) 則代表基本區塊間的執行順序，箭頭所指向的基本區 塊為發出箭頭的基本區塊的後繼 (successor) 節點，反之稱為前任 (predecessor) 節點。程式執行時會由起始節點依序走訪其後繼節點直到抵達終點。

而基本區塊間的有向邊可為條件分支或是無條件跳躍指令。

透過分析 CFG，我們可以歸納出以下兩項常用於建構最佳化編譯器的性質:

- [ ] 可達性 (reachability)

除了起始節點外，若一個基本區塊在最佳化中沒有前任節點連接，則此基本區塊被稱為不可到達 (unreachable)，我們可安全的移除該基本區塊來簡化 CFG，如 C 語言關鍵字 break, continue, return 後的程式碼及 if, for, while 中條 件恆為 0 的情況。

- [ ] 支配性 (domination)

若從起始點到節點 n 都必經節點 d，則稱節點 d 為節點 n 的支配節點 (dominator)，記作 d dom n;而其中最接近節點 n 的支配節點 m 又稱為直接支配 節點 (immediate dominator)，記作 m idom n。將 m 作為親代節點、n 作為子節點，我們可建立另外一種樹狀結構 ── 支配樹 (dominator tree)，記錄從起始點到某個基本區塊節點中必經的路徑。

結合可達性分析，若節點 n 不可到達，則其在支配樹中的所有子節點將同樣不可到達，這時我們可快速且安全地從 CFG 中移除這些基本區塊節點。

## 靜態單賦值 (static single assignment, SSA) 形式
考慮以下程式，我們可以看出第一個賦值是不必要的：

但是當程式碼規模擴大，要判斷賦值是否不必要就必須不斷地往下尋找變數是否被使用或是被重新賦值，此過程會加重編譯器最佳化時的成本，因此在 1980 年代中 SSA 的相關概念開始相繼被提出。由於 SSA 大幅地簡化變數定義的追蹤，讓分支控制流中的變數的相依性分析更加明確，因此 SSA 也成為現代最佳化編譯器最常使用的架構。

在靜態單賦值形式中，我們給予每個被賦值的變數一個唯一的版本 (version) 並重新命名，讓所有變數都僅被賦值一次以便追溯其定義。

但在條件分支的匯聚點會出現來自不同執行路徑的版本號碼衝突，這時需要在執行基本區塊的指令前插入 $\phi$ (phi) 函數，並為該基本區塊建立一個新的版本碼。


$\phi$ 函數會標記一個記憶體地址作為不同版本的暫存位置，新版本藉由讀取該地 址就能取得目前程式的執行路徑所使用的版本號碼。因為 $\phi$ 函數涉及記憶體寫入及讀取，如何精準的插入 $\phi$ 函數將左右輸出的執行檔的執行效率。

## 支配邊界 (dominance frontier)
支配邊界為一個變數的定義恰好不能到達的節點的集合。若節點 n 的前任節點被節點 m 支配，但節點 m 並不支配節點 n 時 (即有其他路徑可略過節點 m 抵達節點 n)，節點 n 即為節點 m 的支配邊界之一。


一個基本區塊中變數的定義可遍及其支配邊界以內的所有基本區塊，因此我們
可省略這些基本區塊中的 $\phi$ 函數，只需要在支配邊界上插入必要的 $\phi$ 函數。

## 常見編譯器最佳化策略

- [ ] 常數傳遞 (constant propagation)
利用 SSA 向前化簡指令中的運算元變數，若我們確認數學運算中的兩個運算元都為常數，則在編譯期就可先計算其結果，並將結果傳遞至所有使用其變數的指令中。

- [ ] 死碼消除、共同子表式消除
若一個變數被定義但從未被使用，我們可以將其視為死碼 (dead code)，與不可達程式碼一樣，可在最佳化中被移除；若兩個變數擁有相同的定義，我們則可省略其中一個變數的定義，以消除冗餘的計算。

- [ ] 暫存器配置
在 SSA 中，我們將資料分別儲存在無限多個虛擬暫存器中，但在現實世界
中的實體暫存器數量是有限的，我們需要配置及維護暫存器中的內容，讓指令在執行時能存取到正確的運算元。常見的資源配置演算法有圖著色演算法 (graph coloring) 及線性掃描 (linear scanning) 演算法。

- [ ] 指令融合、窺孔優化 (Peephole Optimization)
暫存器配置時產生某些指令序列，如暫存器間移動與寫入後讀取等，則可
以藉由窺孔優化來消除或化簡。

## 中間表示式 (intermediate representation)
中間表示式 (IR) 是個臨時的結構體，儲存來自編譯器不同階段中的資訊。其優點是可以分離編譯器前、後端，並讓最佳化中端獨立於程式語言與硬體架構之上。換言之，只要有完善的中間表示法即可支援不同的程式語言及目標機器。

shecc 引入二階段的中間表示式作為建立最佳化編譯器的基礎。
* 第一階段 IR 為高階 IR，使用不限數量的虛擬暫存器 (virtual register) 記錄由編譯器前端所解析的變數、運算子與程式控制流，並以這 些資訊建立 SSA 形式及進行後續與 SSA 相關的最佳化。
* 第二階段 IR 為低階 IR，用於記錄由暫存器配置後所對應到的實體 暫存器；由於 shecc 不依賴現有組譯器、直接產生機械碼，我們需要在產生指令的階段計算好分支與跳躍指令的偏移量。而與硬體架構相關的最佳化也將以第二階段 IR 為基礎。

## shecc

- 七千行程式碼，買越多省越多！
- 曾在 GitHub 上有看到一萬多行的最佳化編譯器實作 (但過去沒有見到三萬行程式碼以內可 self-hosting 的專案)，希望能做更小
- 如今精簡的東西相當難得
- 快來跟我們一起開發！

## 開發最佳化編譯器的背景知識

* 開始讀大學就可以了
* 好好讀難懂的語言規格書
* 程式碼解析器：計算理論、離散數學
* 計算機結構
* 離散數學、圖論（前面講的著色問題)、資料結構、演算法
* 作業系統、計算機結構、資訊安全

## Q & A

* Q: 目前使用 Cortex M55/N55，會不會未來在 NPU 上面有著墨？
* 現在 microcontroller (MCU) 已經能做非常多事情，如[上一場議程](https://hackmd.io/f3cs2UxpRKaIsY2ey3itYw) ([Mado 視窗管理系統](https://github.com/sysprog21/mado)) 可在 MCU 等級的硬體順暢執行
* 光有硬體是不夠的，還需要編譯器
* ONNC/ONNX 有不同 layer，目前沒有特別好的方案
* 通用 CPU (RISC-V) 有機會透過小的編譯器做 JIT / Profilling (PGO, Profile-Guided Optimization), Meta BOLT
* Q: parser 策略 (LR/LALR?)
* 暫時還沒花太多力氣做 parser，歡迎投入
* 也是有遇到很多問題。
* C preprocessor 的還有各種處裡，這邊大就花了 1000 行。
* shecc看起來很完善，有甚麼可以貢獻的東西
* https://github.com/sysprog21/shecc/issues
* 有好多 issue 可以解啊。
* c-preprocess 和 frontend 可以一起做R。
* bug 還是很多，也可以去找 bug 提出來。
* 產生的程式碼需要做 bootstrapping，目前只能跑在 QEMU，希望找些其他系統模擬的方法支援非 Linux OS
* 目前只支援 ARM／RISC-V，看看有沒有人可以貢獻 x86(-64) 之類的處理器後端。

## 小結論
* 現在這個時代很多東西都很複雜，反而這種簡單的東西去實作的東西，反而很難找到。

## 延伸閱讀
* [你所不知道的 C 語言：編譯器和最佳化原理篇](https://hackmd.io/@sysprog/c-compiler-optimization)
* [你所不知道的 C 語言：編譯器原理和案例分析](https://hackmd.io/@sysprog/c-compiler-construction)
* [可自我編譯的 C 編譯器](https://hackmd.io/@sysprog/HkqE5DKqP)
* [可自我編譯的最佳化編譯器](https://hackmd.io/@sysprog/H11Da3FQA)