# Linux 核心專題: shecc
> 執行人: nosba0957, vacantron
[解說錄影](https://youtu.be/h96ShOAHkc0)
## 可自我編譯的最佳化編譯器
[shecc](https://github.com/sysprog21/shecc) 最初是為了教學需要而開發的精簡 C 編譯器，可編譯自身 (self-hosting)，直接輸出機械碼，不依賴其他開發工具，支援 32 位元的 Arm 和 RISC-V 處理器架構。近期實作 register allocation (RA) 和 static single assignment form (SSA) 為基礎的最佳化機制，用來產生更好的機械碼。
## TODO: 研讀專題報告，並依據 shecc 近期發展進行更新
> 紀錄閱讀過程中遇到的問題
> 更新的內容可置於本筆記頁面
闡述 bootstraping 流程，應涵蓋語法解析、產生 IR、建立 SSA 表示法、施行最佳化。
> 參見 [可自我編譯的 C 編譯器](https://hackmd.io/@sysprog/HkqE5DKqP)
### bootstrapping
shecc bootstrapping 流程分成三個階段
+ `stage0`: 用 `gcc` 編譯 `src` 目錄底下的檔案，產生第一個可執行檔 `out/shecc`，此執行檔支援的處理器架構是使用者的硬體所支援的架構，以我的為例是 X86。
+ `stage1`: 用 `stage0` 產生的 `out/shecc` 編譯 `src` 下的檔案，產生的可執行檔 `out/shecc-stage1.elf` 是 ARMV7 的指令集或是 RISC-V 的指令集，依照 makefile 的 config 設定產生。此執行檔需要透過 qemu 來執行。
+ `stage2`: 用 `stage1` 產生的 `out/shecc-stage1.elf` 編譯自己，產生 `out/shecc-stage2.elf`。
+ `bootstrap`: 比較 `out/shecc-stage1.elf` 和 `out/shecc-stage2.elf` 是否相同，判斷 bootstrap 是否成功。
### 語法解析
`parse` 函式內的第一個呼叫的函式是 `load_source_file`，用來載入檔案，並且把該檔案要透過 `#include ""` 引進的檔案也一併讀入。
接下來透過 `read_preproc_directive` 函式讀取在全域範圍的 preprocessor directives，例如 `define, ifdef ...`。如果不是 preprocessor directives，則是執行 `read_global_statement`，這個函式透過 `if` 敘述可以分成三個部分，第一個是執行全域的 `struct` 定義解析，接下來是 `typedef`，最後其他的變數和函式的解析會透過 `read_global_decl` 解析。
`read_global_decl` 解析了全域變數和函式宣告。
+ 函式宣告的解析中，會看到兩個函式，`add_func` 和 `add_fn`。`add_func` 是將函式的名稱加入到 `FUNC_TRIES` 結構中，加入的方式是透過 `insert_trie` 插入。`insert_trie` 會逐個檢查函式名稱的字串，如果是第一次紀錄的字元，則會將結構中的 `index, next[]` 初始化為 `0`。如果檢查到 `\0`，字串結尾，就會透過 `index` 是否為 `0` 判斷是不是新增的函式，再回傳 `index`。而在 `add_func` 中也會透過比對 `insert_trie` 回傳的數值和最初傳入的 `funcs_idx` 比對，如果不同表示是先前已經加入，就會透過 `insert_trie` 回傳的索引取得之前的結構，回傳 `FUNCS[index]`。而 `add_fn` 會配置一個新的 `fn_t` 結構並且加入到 `FUNC_LIST` 串列中。接下來在 `read_func_body` 函式內讀取該函式的參數。一開始透過 `add_symbol` 將每個參數的 `var_t` 的結構加入到當前的 `basic_block_t` 的 `symbol_list`。接下來 `var_add_killed_bb` 函式會記錄使用到這個變數的基本區塊，用 `var_t` 內的 `ref_block_list` 紀錄。接下來會透過呼叫 `read_body_statement` 處理函式內的程式碼。
+ 全域變數的解析是透過 `read_global_assign`。分成一個值，兩個值和兩個值以上的情況。如果只有一個值，也就是透過 `get_operator` 得到的回傳值是 `OP_generic`，就會直接新增 phase 1 IR。如果全域變數的初始化有兩個值以上，就會先透過 `eval_expression_imm` 將最後的數值計算出來，才新增 IR。最後如果是多餘兩個數值的情況，因為兩個數值以上的計算會需要考慮每個運算子的優先順序，透過 `get_operator_prio` 可以取得運算子的優先程度。如果下一個運算的優先度大於目前堆疊頂部運算子的優先度，則會將下一個運算儲存到堆疊中。例如 `1 + 2 * 3`，初始情況 `op_stack` 內會有 `+`，`val_stack` 內會有 `1, 2`。接下來會取得下一個運算子也就是 `*`，從 `get_operator_prio` 可以知道乘法優先度高於加法，所以就會將 `3` 存到 `val_stack`，`*` 存到 `op_stack`。
### 建立 SSA
建立 SSA 的流程在 [ssa_build](https://github.com/sysprog21/shecc/blob/1b3491968d058647722abe0ac64ec8b29b740c24/src/ssa.c#L1005) 函式內。首先是 `build_rpo`。 RPO 是 reverse postorder traversal，用來計算支配節點集合。`bb_forward_traversal` 提供逐一走訪每個節點的函式，透過指派不同函式的函式指標到 `bb_traversal_args_t` 的 `preorder_cb` 或 `postorder_cb`，就可以選擇走訪的方式。`bb_index_rpo` 會先透過一般的 postorder 走訪方式幫每個基本區塊指派最初的編號，並順便計算該函式的基本區塊數量。接下來透過 `bb_reverse_index` 得到 RPO 真正的值。接下來透過 `bb_build_rpo` 建立基本區塊間的 `rpo_next` 連結，也是透過後序走訪方式建立。
下圖的編號是 RPO 的 index。
後序走訪的第一個處理的節點是 5 號節點，所以函式引數 `bb` 是 5 號節點。第一次執行 `bb_build_rpo` 由於 `curr` 為 `NULL`，所以只會執行 `prev->rpo_next = bb`，也就是將 1 號節點的 `rpo_next` 連結到 5 號節點。接下來 `bb` 為 4 號節點，`prev` 為 1 號節點，`curr` 為 5 號節點，接下來會將 4 號節點的 `rpo_next` 連接到 5 號節點，再將 `prev->rpo_next`(也就是 1 號節點的 `rpo_next`) 連結到 4 號節點。以此類推。
```c
void bb_build_rpo(fn_t *fn, basic_block_t *bb)
{
if (fn->bbs == bb)
return;
basic_block_t *prev = fn->bbs;
basic_block_t *curr = prev->rpo_next;
for (; curr; curr = curr->rpo_next) {
if (curr->rpo < bb->rpo) {
prev = curr;
continue;
}
bb->rpo_next = curr;
prev->rpo_next = bb;
prev = curr;
return;
}
prev->rpo_next = bb;
}
```
接下來是 `build_idom`，找出每個基本區塊的 immediate dominator(IDOM)。透過剛才 `build_rpo` 建立的 RPO 的順序可以用更快速的方式找到 IDOM，因為依照 RPO 的順序處理某個節點時，已經先存取過該節點的所有前任節點。下圖舉例，圖上編號為 RPO 的號碼，假設我們要找 `5` 這個基本區塊的 IDOM，方法是先從 `5` 的前任節點中找兩個前任節點出來，所以是 `4` 和 `3`，再透過 `intersect` 函式找到 `4` 和 `3` 最近而且共同的 DOM，就是綠色的 `2` 號節點。接下來依序將節點 `5` 的每個前任節點(剩下 `1`)和 `2` 輸入到 `intersect`，會回傳節點 `0`。所以最後就得到節點 `5` 的 IDOM 為節點 `0`。
接下來是 `build_dom` 函式，就是透過 `build_idom` 所建立的 IDOM 連結建立 dominator tree。使用 preorder 走訪方式執行 `bb_build_dom`。經由 `dom_connect(curr->idom, curr)` 來連結 `curr` 和其 IDOM 節點。
`build_df` 函式建立支配邊界 DF(dominance frontier)。$p$ 為 $q$ 的支配邊界表示為 $p \in DF(q)$。要尋找 $q$ 的支配邊界有兩個條件
1. $p$ 有 1 個前任節點被 $q$ 支配。
2. $p$ 不被 $q$ 支配。
在 `bb_build_df` 內，先確認該基本區塊(假設為 `bb`)有一個以上的前任節點。再從 `bb` 的前任節點開始(設為 `curr`)。如果 `curr` 和 `bb->idom` 不同，表示 `bb` 並沒有被 `curr` 支配，而該節點支配自己，所以符合兩條件，將 `bb` 加入 `curr` 的 `DF` 集合內。接下來再確認 `curr->idom` 和 `bb` 的關係，以此類推判斷 `DF`。
`solve_globals` 透過 [`bb_solve_globals`](https://github.com/sysprog21/shecc/blob/1b3491968d058647722abe0ac64ec8b29b740c24/src/ssa.c#L337) 分析每個 `insn` 所使用的變數。`live_kill[]` 對應到〈Engneering a compiler 3rd〉中提到的 $VARKILL(m)$，$VARKILL(m)$ 集合含有所有定義在 $m$ 這個基本區塊的變數。所以 `bb_solve_globals` 一開始先檢查 `insn->rs1` 和 `insn->rs2` 是否是在此基本區塊定義的，如果不是則紀錄到此基本區塊所屬的 `fn` 內 `global_sym_list`。最後如果有被指定的變數，`insn->rd`，會透過 `bb_add_killed_var` 加入到 `live_kill[]` 再透過 `var_add_killed_bb` 在變數的結構內紀錄在哪個基本區塊內被指定過(紀錄在 `var_t` 內的 `ref_block_list`)。
插入 phi 函式是透過 `solve_phi_insertion` 函式進行。某變數需要插入 phi 函式的話，這個變數需要活躍 (live) 多個基本區塊內。這個條件在上一個 `bb_solve_global` 函式中的 `fn_add_global` 就會將此類型的變數記錄到 `fn->global_sym_list` 內。接下來將該變數結構內的 `ref_block_list` 所有基本區塊加入到 `work_list`。接下來依序處理 `work_list` 中的基本區塊。從 `work_list` 中取出一個基本區塊 `x`，接下來就會將 phi 函式插入在 `x` 的支配邊界上。
`solve_phi_params` 以版本號碼重新命名變數。首先分析 `var_t` 結構。`struct var *base` 記錄重新命名前的變數的資料。`int subscript` 紀錄目前的版本號碼。`struct var *subscripts` 紀錄其他版本號碼的 `var_t` 結構的位址。每一個變數的 `base->rename.stack` 用來模擬變數活躍的時間，堆疊頂部是目前最新衍生 (derived) 變數，會透過 `pop_name` 從堆疊移除表示該衍生變數已經無法使用。
整個 `bb_solve_phi_params` 是透過前序走訪支配樹的節點。首先分析整個基本區塊的所有指令 (`insn`)，如果是 phi 函式的變數和 `insn->rd`，就會透過 `new_name` 函式指派新的衍生變數，如果是 `insn->rn`, `insn->rm`，則透過 `rename_var` 得到目前最新版本的衍生變數。接下來處理這個節點的每個子代節點的 phi 函式的參數，透過 `append_phi_operand` 將 phi 函數的 operand 用 `phi_operand_t` 的鏈結串列連結，並且記錄 phi 函數的 operand 從哪些基本區塊來的。
最後是 `unwind_phi`，解開 phi 函數。執行的順序是依序從 `FUNC_LIST.head` 存取每個 `fn_t` 結構，在 `fn_t` 結構內透過前序走訪每個基本區塊。主要執行方式是 `bb_unwind_phi` 會在此基本區塊內，尋找 `insn->opcode == OP_phi`。接下來藉由先前處理過的 `phi_operand_t` 結構內的資料，輸入到 `append_unwound_phi_insn` 函式，就會新增 `OP_unwound_phi` 的 `insn` 並且加入到該 operand 所屬的基本區塊內。最後 `bb_unwind_phi` 處理完所有 phi 函數，會將該基本區塊所有 phi 函數移除。
### 施行最佳化
shecc 實作了兩個指令層級的最佳化，第一個是 CSE(common subexpression elimination)，第二個是 constant folding。
CSE 可以消除不必要的記憶體讀取指令，若有使用到相同定義的變數，可以用暫存器複製的指令取代記憶體讀取。首先確認我們找到記憶體讀取的指令，以及前一個指令是用 `add` 計算變數儲存在 `sp` 中的位移，這樣是一組記憶體讀取的指令。接下來往此基本區塊的 `IDOM` 尋找，一樣是要在指令的串列中找到一樣一組記憶體讀取指令。並且確認 `base` 和 `idx` 是相同的。這樣就可以確定找到相同定義的變數，然後改為使用暫存器複製的指令。
constant folding 會在編譯時期去找到常數的計算，並且在編譯時期就先將數值計算完，將計算結果改為數值指派的指令，減少中間的計算。首先 `mark_const` 函式，我們先找到 `OP_load_constant` 的指令，將該指令的 `rd` 標示為儲存常數(`is_const`)。如果是 `OP_assign` 的指令，則是判斷該指令的 `rs1` 是否被標註為常數，如果是，則將此指令直接改為儲存 `rs1` 內的常數，opcode 就會由 `OP_assign` 變成 `OP_load_constant`。另一個函式是 `eval_const_arithmetic`，處理常數的數學運算的指令。首先確認指令的兩個變數 `rs1`, `rs2` 是否儲存的是常數，再依 opcode 進行對應的計算，最後將指令改為讀取運算的結果。
## TODO: 消除 [Issue #120](https://github.com/sysprog21/shecc/issues/120)
> 該問題在 3 月下旬才出現，應對照相關修改，以釐清根本原因
> 此問題在 `d9a989d` 提交後首次出現
目前檢查到，在 [build_rpo](https://github.com/sysprog21/shecc/blob/1b3491968d058647722abe0ac64ec8b29b740c24/src/ssa.c#L108) 執行完 `bb_index_rpo` 時，會順便計算函式中基本區塊的數量 `fn->bb_cnt`，所以在這邊印出基本區塊的數量，發現由 `stage 0` 編譯器印出的數量和 `stage 1` 編譯器印出的數量不同。
後來發現在 [`read_body_statement`](https://github.com/sysprog21/shecc/blob/1b3491968d058647722abe0ac64ec8b29b740c24/src/parser.c#L2222) 中處理 `T_switch` 的這段程式碼。
```c=2222
if (control && true_body_) {
/* Create a new body block for next case, and connect the last
* body block which lacks 'break' to it to make that one ignore
* the upcoming cases.
*/
basic_block_t *n = bb_create(parent);
bb_connect(true_body_, n, NEXT);
true_body_ = n;
}
```
發現由 gcc 編譯出來的 `out/shecc` 編譯 `src/main.c` 是可以正常執行並進入這段 `if` 敘述，但產生出來的執行檔 `out/shecc-stage1.elf` 再編譯 `src/main.c` 就不會執行這段程式碼。所以後來又透過小程式測試。
```c
#include <stdlib.h>
#include <stdio.h>
int main(){
int a = 0, *b = NULL;
b = malloc(sizeof(int));
a = 1;
if (a && b)
printf("correct\n");
else
printf("wrong\n");
return 0;
}
```
如果是這段程式直接使用 gcc 編譯的結果會印出 `correct`，但使用 `out/shecc` 會產生 `wrong`。所以目前找到的錯誤和 `d9a989d` 提交的 `for` 迴圈相關修改似乎沒有關聯。
再進一步發現是和 [logical AND](https://github.com/sysprog21/shecc/blob/1b3491968d058647722abe0ac64ec8b29b740c24/src/arm-codegen.c#L445) 的定義有關。現在的實作是 bitwise AND，所以會有錯誤。
後來將 `OP_log_and` 的實作改為以下，並且要記得修改 `update_elf_offset` 中 `OP_log_and` 的位移。
```c
case OP_log_and:
emit(__teq(rm));
emit(__mov_r(__NE, rd, rn));
emit(__mov_i(__EQ, rd, 0));
return;
```
後來發現這個實作是不符合 C99 的。在 C99 6.5.13 中描述 logical-and 的部分。發現 logical-and 的結果只能是 `0` 或 `1`。
> The && operator shall yield 1 if both of its operands compare unequal to 0; otherwise, it yields 0. The result has type int.
所以後面實作改為先檢查第一個暫存器的值，如果是 `0` 就直接將目標暫存器 `rd` 改為 `0`。
```c
case OP_log_and:
/* TODO: Short-circuit evaluation */
emit(__teq(rn));
emit(__b(__EQ, 20));
emit(__teq(rm));
emit(__b(__EQ, 12));
emit(__mov_i(__AL, rd, 1));
emit(__b(__AL, 8));
emit(__mov_i(__AL, rd, 0));
return;
```
另外，在 C99 中也有提到 logical-and 操作具有 left-to-right evaluation 的特性。
> Unlike the bitwise binary & operator, the && operator guarantees left-to-right evaluation; there is a sequence point after the evaluation of the first operand. If the first operand compares equal to 0, the second operand is not evaluated.
在實作時我以為我這樣跳過第二個暫存器讀取就算是符合 left-to-right evaluation，但經過其他貢獻者(`@DrXiao`)提供的測試資料發現，如果測試資料為以下
```c
#include <stdio.h>
int func(int x)
{
if (x >= 0)
printf("x >= 0\n");
return x;
}
int main()
{
int ret = 0;
ret = 1 && func(5);
if (ret)
printf("%d\n", ret);
printf("============\n");
ret = 0 && func(5);
if (ret)
printf("%d\n", ret);
return 0;
}
```
shecc 處理 logical-and 時會先計算左右兩個 operand 的值，也就是如果 operand 是函式呼叫，就會進入函式並且得到回傳值，最後才進行 logical-and 操作。所以如果要達成 left-to-right evaluation，需要從比較前面的步驟開始修改。目前無法達到。
目前為了達成 left-to-right evaluation，要從 parser 開始修改。原本的程式無法達到 left-to-right evaluation 是因為我們在 `read_expr` 函式內的實作是先用 `read_expr_operand` 讀取 operator 之間的 operand。例如 `a && b` 會先產生讀取 `a` 和 `b` 所需的指令，隨後才產生 `&&` 的指令。但是這樣不符合 left-to-right evaluation 的概念。
所以目前實作的方式是在 `read_expr` 中，如果讀取到 `&&`，就先為 logical-and 新增所需的基本區塊以及 branch 指令。實作方式如下圖，logical-and 的所有 operand 的 false 情況都會前進到同一個基本區塊，在最後的基本區塊透過 phi 函式來取得最終 logical-and 的結果。
遇到的問題是 `stage 0` 的 shecc 要編譯出 `stage 1` 的 `shecc-stage1.elf` 時，會遇到 `free(): invalid pointer` 的錯誤訊息。後來檢查發現是 `ph2_ir_idx` 已經超過我們在 `src/defs.h` 中定義的 `MAX_IR_INSTR` 的數量，所以導致記憶體使用的錯誤。目前先將 `MAX_IR_INSTR` 設為 `40000`。
由於修改了解析 logical-and 的行為，也造成 `read_expr` 執行結果會有變化。所以要對會使用到 logical-and 的狀況修正。首先是 `for` 迴圈的條件敘述。因為解析 logical-and 會創建新的基本區塊，所以原本讀取使用 `read_expr(blk, &cond_)`，第二個參數 `&cond_` 在執行 `read_expr` 前後會是不同的基本區塊。所以原本的實作中在還沒解析條件敘述就先將基本區塊連接好，會造成錯誤。
### 在 do-while 遇到的問題
考慮以下程式
```c
int main()
{
int a = 1, b = 5;
do {
a++;
} while(a < 10 && b == 5);
return a;
}
```
當修改完 logical-and 後，這段程式碼無法正常運行。從下圖可以看到，這段程式碼主要有兩個 phi 函式。第一個是 `a2 = PHI(a1, a3)`，第二個是 `.t9(1) = PHI(.t9(0), .t9(2))`。這裡遇到的問題是，當 shecc 執行 [`insert_phi_insn`](https://github.com/sysprog21/shecc/blob/6cdd7e2d5d303a1467a6cd3758d9bb431a2b893d/src/ssa.c#L411) 插入 phi 函式時，shecc 並不會將原本在 `head` 的 `insn` 的 `prev` 指標連接到新插入的 phi 函式的結構。這個問題會導致後續 [`append_unwound_phi_insn`](https://github.com/sysprog21/shecc/blob/6cdd7e2d5d303a1467a6cd3758d9bb431a2b893d/src/ssa.c#L635) 函式執行時，解開 phi 函式時如果遇到 `branch` 要將 `unwind_phi` 的指令插入到 `branch` 指令前，但是實作時我們會用 `tail->prev` 來檢查 `branch` 前還有沒有指令，沒有的話就直接將 `unwind_phi` 的指令插入到 `insn_list.head` 並且連接 `branch`。
所以這裡就會發生問題，當 `branch` 前的指令是 phi 函式，我們插入 phi 函式時並沒有將 `branch` 指令的 `prev` 指標連接到 phi 函式，所以就會判斷錯誤。下圖是 `do-while` 範例程式的 CFG，注意 `append_unwound_phi_insn` 是前序走訪。第一個遇到的 phi 函式是 `a2 = PHI(a1, a3)`，首先就會將 `unwind_phi` 指令插入到 `a1` 的所在基本區塊的最後一道指令，也就是地址結尾是 `b6eb0` 的基本區塊，接下來就是將 `unwind_phi` 指令插入到 `a3` 所在的基本區塊，也就是地址結尾是 `f9fd0` 的基本區塊。而問題發生在插入 `unwind_phi a3`，因為 `branch` 沒有連接前面的 phi 函式，導致插入時會直接用 `unwind_phi a3` 放在 `insn_list.head`，也就是直接取代原本的 `.t9(1) = PHI(.t9(0), .t9(2))`。所以如果繼續運行，前序走訪到這個基本區塊，根本不會分析到 `.t9(1) = PHI(.t9(0), .t9(2))` 這個指令，導致錯誤。
如果直接修改 phi 節點的連接，[ssa.c](https://github.com/sysprog21/shecc/blob/6cdd7e2d5d303a1467a6cd3758d9bb431a2b893d/src/ssa.c#L411)
```diff
} else {
n->next = head;
+ head->prev = n;
bb->insn_list.head = n;
}
```
會產生非預期的結果
```
LD out/shecc
SHECC out/shecc-stage1.elf
SHECC out/shecc-stage2.elf
qemu: uncaught target signal 11 (Segmentation fault) - core dumped
make: *** [Makefile:85: out/shecc-stage2.elf] Segmentation fault (core dumped)
```
後來在 [`append_unwound_phi_insn`](https://github.com/sysprog21/shecc/blob/6cdd7e2d5d303a1467a6cd3758d9bb431a2b893d/src/ssa.c#L634) 修改，就可以正常執行。
```diff
if (tail->opcode == OP_branch) {
- if (tail->prev) {
+ if (head->opcode == OP_phi) {
+ while (head->next->opcode != OP_branch)
+ head = head->next;
+ head->next = n;
+ } else if (tail->prev) {
tail->prev->next = n;
```
## TODO: 消除 [Issue #46](https://github.com/sysprog21/shecc/issues/46)
> 目前程式碼支援不依賴除法指令的 Arm32 輸出，待支援 RV32I (不依賴 RV32M) 的指令輸出
* [Implement multiplication for RV32I](https://github.com/sysprog21/shecc/pull/133)
* [Implement division and modulo for RV32I](https://github.com/sysprog21/shecc/pull/134)
## TODO: 更新 [Issue #88](https://github.com/sysprog21/shecc/issues/88)
實作 copy propagation 或 dead code elimination
### Dead code elimination (DCE)
死碼消除，顧名思義消除程式碼中多餘的指令，這些多餘的指令可能是 parser 轉換後產生，消除後不會影響程式執行的結果，能減少執行檔大小，也能增加程式執行速度。
在〈Engneering a compiler 3rd〉將 DCE 分成兩個部分，第一部分是 eliminating useless code，也就是消除多餘無用的指令。第二部分是 eliminating useless control flow，消除多餘無用的基本區塊。
#### eliminating useless code
在〈Engneering a compiler 3rd〉中，消去多餘指令的實作方式是相似於 mark-sweep garbage collectors (可參見書中 6.6.2)。mark-sweep 分成兩個部分，第一個部分是 mark，會將關鍵性(critical)的操作標示為 "useful"。分析完所有指令後就是執行 sweep 的任務，sweep 就是將沒有標示為 "useful" 的指令進行處理，處理的方式有直接刪去或是轉換指令。
消除多餘指令分成兩種類型，非分支跳躍指令和分支跳躍指令。
##### 非分支跳躍指令類型
非分支跳躍指令的處理比較單純，首先在 mark 階段標記哪些為 "useful" 指令。在 sweep 階段移除沒有被標記為 "useful" 的指令。
##### 分支跳躍指令類型
分支跳躍指令有兩種，jump 和 branch。在 mark 階段，所有 jump 指令皆被標示為 "useful"。而 branch 指令需要分析分支後的基本區塊內是否有 "useful" 的操作，才會將 branch 標示為 "useful"。上述的方法要透過分析 control dependence 來協助達成。分析 control dependence 的時候需要引入 postdominance 的觀念。在 CFG 中，如果節點 $i$ 到 CFG 終點的節點(exit node)的路徑上必定經過節點 $j$，則稱為 node $j$ postdominates node $i$。
在 CFG 中，如果某節點 $j$ is control-dependent on node $i$，需要符合兩條件：
1. 節點 $j$ postdominates 從節點 $i$ 到節點 $j$ 路徑上的節點(不包含節點 $i$)。
2. 節點 $i$ 沒有被節點 $j$ strictly postdominate。也就是節點 $i$ 有其他路徑可以不經過節點 $j$ 且到達 CFG 的 exit node。
control dependence 的概念可以透過反向支配邊界 RDF(reverse dominance frontier)來實現。反向支配邊界是使用反向 CFG(reverse CFG) 來計算支配邊界。所以當 mark 階段標記了某個操作為 "useful"，則會存取此基本區塊的 RDF 集合內的基本區塊，將這些基本區塊最後的 branch 指令標示為 "useful"。
sweep 階段會將沒有被標記的 branch 指令轉換成 jump 指令。jump 目標的基本區塊會選擇最近並且含有 "useful" 操作的 postdominator。
##### 分析 pseudo code
書中 p.523 有提供 pseudo code。要將 pseudo code 實作前有幾個問題需要整理。
在 `Mark` 函式
1. 何謂 critical 的指令？書中提到
> An operation is *critical* if it sets a return value for the procedure, it is an input/output statement, or it affects the value in a storage location that may be accessible from outside the current procedure. Example of critical operations include a procedure's prolog and epilog code and the precall and postreturn sequences at calls.
是否還有其他指令也會被歸為 critical？在 shecc 內對應是哪些指令？
2. 分析 critical 指令 $x \leftarrow y\ op\ z$ 時，會判斷 $def(y)$ 和 $def(z)$ 是否已經被 mark。$def()$ 回傳的應是指派 $y$ 和 $z$ 數值的指令。$def()$ 要如何實作？
目前在 `var_t` 內有實作 def-use chain，`ref_block_list`，但是是紀錄基本區塊，若要搜尋對應指令，可能需要存取該基本區塊的所有指令。
4. RDF 如何實作？書中提到透過 reverse CFG 計算支配邊界，reverse CFG 該如何計算？
目前因 `liveness_analysis` 函式會計算 reverse rpo，所以可以用來計算 RDF。計算 RDF 的過程和計算 DF 過程一樣，只是使用 `rpo_r_next`，並要另外儲存 RDF。雖然過程一樣，但使用不同變數可能要重新撰寫對應函式。
在 `Sweep` 函式
1. branch 指令且沒有被 mark 時，要更換成 jump 指令且跳躍到最近的 marked postdominator。要如何尋找 marked postdominator？更換指令要如何達成？
2. 非分支跳躍指令且沒有被 mark 時，刪除該指令要如何實作？
---
## 問題
- [ ] [read_global_statement](https://github.com/sysprog21/shecc/blob/1b3491968d058647722abe0ac64ec8b29b740c24/src/parser.c#L2755) 中在解析 `struct` 時會檢查是否有 forward declaration，但是從 `read_global_statement` 內解析 `struct` 的程式碼中沒有允許 forward decalration。因為是使用 `lex_expect(T_open_curly)`，所以表示一定是要使用完整宣告的 `struct`。
```c
/* has forward declaration? */
type_t *type = find_type(token, 2);
if (!type)
type = add_type();
```
但我在此處加入 `else` 去印出結果時又會印出有 forward decalration 的情況。
$\to$ 此處的 forward declaration 指的是由 `typedef` 陳述式所預先宣告的別名 (alias)，如[此處](https://github.com/sysprog21/shecc/blob/1b3491968d058647722abe0ac64ec8b29b740c24/src/defs.h#L194)的 `fn_t`
```c
typedef struct fn fn_t;
```
- [ ] 為何解析函式時會建立兩個 `block_t`？
一開始會在 [read_function_body](https://github.com/sysprog21/shecc/blob/1b3491968d058647722abe0ac64ec8b29b740c24/src/parser.c#L2674) 內建立一個，接下來在 [read_code_block](https://github.com/sysprog21/shecc/blob/1b3491968d058647722abe0ac64ec8b29b740c24/src/parser.c#L2650) 中又建立一個。
$\to$ 為了簡化後續建立 SSA (static single assignment) 形式時為函式引數 (argument) 加上版號 (subscript) 的步驟，在此處額外加上一個程式碼區塊來區別函式引數與函式主體內的陳述式所定義的變數
- [ ] `block_t` 的意義是和 c99, 6.8 statements and blocks 中第 3 點的 block 定義一樣嗎？
> A block allows a set of declarations and statements to be grouped into one syntactic unit.
$\to$ 基本上雷同，用以記錄不同作用域所定義的變數
- [ ] [`var_add_killed_bb`](https://github.com/sysprog21/shecc/blob/1b3491968d058647722abe0ac64ec8b29b740c24/src/ssa.c#L288) 中，會紀錄該變數被哪些基本區塊 "reference"。我不知道 "reference" 的定義是什麼。
$\to$ 在計算變數的活躍區間時，我們將被指定新值的變數加入至基本區塊的 `live_kill` 列表中，同時記錄在變數中記錄這個基本區塊。我們可以由前者計算出哪些變數的活躍區間跨越了不同的基本區塊，而在後續插入 phi 節點時則需要後者所建立的 def->use 關係，用來快速的查找此變數內的數值曾被哪些基本區塊修改過。而此處的 reference 指的就是「變數中儲存的數值被修改」這個行為，我們在 shecc 的 IR 中將此類變數置於 `rd` 中
- [ ] CSE 最佳化時為何遇到讀取全域變數就不實行？[src/ssa.c](https://github.com/sysprog21/shecc/blob/6cdd7e2d5d303a1467a6cd3758d9bb431a2b893d/src/ssa.c#L1045)
$\to$ 這是實作造成的限制，由於目前的全域變數採取「內容被更改即立刻儲存回堆疊中」的策略簡化全域變數的活躍區間分析 (全域變數可能被某函式更動，而呼叫函式者卻無從得知)，在[建立 SSA、插入 phi 節點時](https://github.com/sysprog21/shecc/blob/6cdd7e2d5d303a1467a6cd3758d9bb431a2b893d/src/ssa.c#L452) 跳過全域變數並在 [暫存器配置階段](https://github.com/sysprog21/shecc/blob/6cdd7e2d5d303a1467a6cd3758d9bb431a2b893d/src/reg-alloc.c#L438) 將被更動的全域變數儲存回堆疊中
Sign in with Wallet
Connect another wallet