# 2020q3 專題: 可自我編譯的 C 編譯器
> In computer programming, self-hosting is the use of a program as part of the toolchain or operating system that produces new versions of that same program—for example, a compiler that can compile its own source code.
引述自 Wikipedia 對 self-hosting 的定義。沒錯，`shecc` 就是一個 self-hosting compiler，可先透過現有的編譯器(e.g. gcc)產生執行檔，再透過該執行檔編譯下一個版本，達到 self-host 的效果。
## 運作原理
### How to bootstrap?
#### Stage 0
```shell
$(OUT)/$(STAGE0): $(OUT)/libc.inc $(OBJS)
$(VECHO) " LD\t$@\n"
$(Q)$(CC) $(OBJS) -o $@
```
用 `gcc` 編譯 `src` 底下的檔案，產生執行檔 `shecc`
#### Stage 1
```shell
$(OUT)/$(STAGE1): $(OUT)/$(STAGE0)
$(VECHO) " SHECC\t$@\n"
$(Q)$(OUT)/$(STAGE0) --dump-ir -o $@ $(SRCDIR)/main.c > $(OUT)/shecc-stage1.log
$(Q)chmod a+x $@
```
用上一個步驟產生的執行檔 `shecc` 來 "編譯" 自己(src/main.c)，預期產生 ARMv7-A 的 machine code(linux ELF)，此執行檔必須在 ARM platform 上執行。
另外 IR 會存在 `shecc-stage1.log`
#### Stage 2
```shell
$(OUT)/$(STAGE2): $(OUT)/$(STAGE1)
$(VECHO) " SHECC\t$@\n"
$(Q)$(ARM_EXEC) $(OUT)/$(STAGE1) -o $@ $(SRCDIR)/main.c
```
[QEMU](https://www.qemu.org/) 可模擬在 ARM 平台執行程式，將 stage 1 產生的執行檔(arm based elf file)透過 QEMU 來執行。同樣編譯自己，將產生的執行檔命名為 `shecc-stage2.elf`
#### bootstrap
比較 stage 1 和 stage 2 產生的兩個執行檔是否相同(binary aspect)，如果相同代表 bootstrap 成功！
### shecc 運作原理
本段落只用 high level 的方式說明運作流程，詳細的 code tracing 放在[文末](#Trace-code-in-detail)。
萬事起頭難，trace 一個專案從 `main.c` 下手通常是一個不錯的選擇。從 `main` 中可以清楚看到 `shecc` 的運作流程：
1. global_init()
2. libc_generate()
3. parse(in)
4. code_generate()
5. elf_generate(out)
首先需要分配稍後編譯所需的資料結構 (e.g. `BLOCK`) 和填寫 elf 檔案的空間。 接著是 `parse`，在 `parse` 的前半部需要先載入程式碼，也包含 `include` 的檔案，通通存到 `SOURCE`。後半部則是開始 parsing (`parse_internal`)，在開始前需要加一些 initial instruction 到 `instr_t` 內，接著就是一直讀程式碼 (`read_global_statement`)，直到 EOF。(事實上 `read_global_statement` 不只是判斷語法的正確與否，他還負責產生正確的執行順序，如四則運算。簡單來說，`read_global_statement` 會產生最核心的部分: Intermediate representation，而 IR 會記錄在 `instr_t` 型態的資料結構)
下一個步驟是 code generation (`code_generate`)，將 parsing 所紀錄的 instruction 產生成 ARM 的指令，這部分的程式碼在 `codegen.c` 和 `arm.c` 中。此外，這部分的實作基本上就是 1 對 1 的 mapping，由已知道的 `instr_t` (rs, rt, imm 等等都記錄在這個資料結構中) 對應到 ARM instruction (binary)。[文末](#Example-for-mapping-from-IR-to-ARM-instruction)提供簡單的範例展示如何 mapping。
最後則是輸出 ELF 的檔案 (執行檔，based on ARM)，本步驟即 `elf_generate`，在 [wiki](https://en.wikipedia.org/wiki/Executable_and_Linkable_Format) 中有對 ELF 做很清楚的規範，(仔細 trace `elf_generate_header()` 可以發現的確是照著 wiki 規範的格式產生 ELF)。再來就是把上個步驟 (透過 `emit`) 存在 `elf_code` 中的 instruction 寫到輸出的執行檔(ELF)
以上所有步驟將產生能在 ARM 平台上執行的執行檔 (當然執行前記得 chmod)
## Known Issues & Pull Request
本段落說明提交的 PR 修改了哪些功能，主要都是根據尚未通過 test bench (`tests/driver.sh`) 的語法或功能來改善。
### Adjust maximum value in defs.h
這是我發的[第一個 PR](https://github.com/jserv/shecc/commit/ea3d5ac11c7c656cef6d759b971f34945420c2ce)，在 build 專案時會在 stage 1 就 crash，透過 [gdb](https://zh.wikipedia.org/wiki/GNU%E4%BE%A6%E9%94%99%E5%99%A8) 找出在 allocate code block (`shecc` 紀錄資料的結構) 時會 segmentation fault。在 8G 的記憶體下無法分配這麼多記憶體，解法就是減小分配的記憶體。(當然，隨著 `shecc` 的長大，終究還是要增加在 `defs.h` 中定義的 limitation)
### Support divide operation
這是我發的[第二個 PR](https://github.com/jserv/shecc/commit/cd72dd4e95b581ffd85a7c4d74123e3081633768)，基本上新增 operator 流程都一樣:
1. 添加 Token
2. 新增 parsing 時判斷為該 Token 的流程
3. 添加 operator 的 priority
4. 添加該 operator 該如何 encoding 成 binary (必須查 spec)
### Support global variable initialization
這是我發的[第三個 PR](https://github.com/jserv/shecc/commit/12a38bc844dd3963066a3d2bfd575e9811b840f5)，這個 PR 牽涉的問題就比較多了。原本的 `shecc` 並沒有 special section for ELF，其中又屬 `.data` 這個 special section 對 initialized data 來說特別重要。這個區段是在編譯後、執行前就確定了。
為了添加這個功能，我們需要:
1. Evaluate expression before execution time
2. Modify data structure of `var_t`
3. Mechanism for writing initial value into `.data` section
為了解決第一個問題，我們需要變更運算 expression 的策略，原本的方法是產生正確的 instruction order 並等到 running time 才開始算，現在我們需要在編譯時期就算出答案。因此新增 `read_global_assignment` 、 `eval_expression_imm` 和 `read_numeric_sconstant`。
第二個問題就比較好解了，只需要多加一個欄位 `int init_val;` 給 `var_t` 即可。
最後則是需要設計新的函數來寫初始值進 `.data ` section:
```c
void elf_write_data_int(int val)
{
elf_data[elf_data_idx++] = (val & 0x000000FF);
elf_data[elf_data_idx++] = (val & 0x0000FF00) >> 8;
elf_data[elf_data_idx++] = (val & 0x00FF0000) >> 16;
elf_data[elf_data_idx++] = (val & 0xFF000000) >> 24;
}
```
既然已經提供了 global initialization，那就可以簡化 `shecc` 中的部分程式碼，修改於下一個 PR: [Simplify some code with global initializations](https://github.com/jserv/shecc/commit/d01804a557eb9cf9297f6441071f55bd7849962d)。
PS. This patch haven't add `.bss` section for un-initialized data.
### Rework malloc and free function
這是我發的[第五個 PR](https://github.com/jserv/shecc/commit/09a69e8176085d050c7d66e33dc7d211285a2924)，原本 `shecc` 並沒有提供 `free`。為了添增功能，這次需要改動的地方在內建函式庫 `lib/c.c`
參考[文章](https://danluu.com/malloc-tutorial/)對 malloc & free 的實作來完成功能，簡單來說需要維護一條 list，每個節點都代表分配的記憶體(包含 free 後，亦在 list 上)。malloc 時會先找 list 上看是否有被釋放的記憶體，如果要求的大小小於該節點，則直接使用該記憶體。反之，如果整條 list 都找不到恰當的節點，那就需要透過系統呼叫 [`brk`](https://man7.org/linux/man-pages/man2/brk.2.html)。而 free 記憶體只需要將該節點的 `is_free` 標籤更改狀態即可。
### Consolidate break for general loop
這是我發的[第六個 PR](https://github.com/jserv/shecc/commit/d19f0dc1dbb490a7d0fc159d45b5099875d8b84d)，目前的 `shecc` 不支援在 `while` 中使用 `break`，此外，`do_while` 和 `for` 亦不支援 `break`。
原先遇到 `break` 就會跳到"應該跳的地方":
```c
if (lex_accept(T_break)) {
ii = add_instr(OP_jump);
ii->int_param1 = break_exit_ir_index[break_level - 1];
}
```
為了達成功能，我們需要重新設計 loop 附近的 label:
```c
ir_instr_t *start_jump =
add_instr(OP_jump); /* jump to while condition */
ir_instr_t *exit_label = add_instr(OP_label);
ir_instr_t *exit_jump = add_instr(OP_jump);
ir_instr_t *start_label = add_instr(OP_label); /* start to return to */
lex_expect(T_open_bracket);
...
false_jump = add_instr(OP_jz);
false_jump->param_no = 0;
start_jump->int_param1 = start_label->ir_index;
/* create exit jump for breaks */
break_exit_ir_index[break_level++] = exit_label->ir_index;
read_body_statement(parent);
break_level--;
/* unconditional jump back to expression */
...
/* exit label */
ii = add_instr(OP_label);
false_jump->int_param1 = ii->ir_index;
exit_jump->int_param1 = ii->ir_index;
```
### Support continue for general loop
這是我發的[第七個 PR](https://github.com/jserv/shecc/commit/13d327fcd0ccbcd639e257b94d498fa3e70a4077)，原本的 `shecc` 並未提供 `continue` 語法，有別於 `break` ，這次我們還需要而外添加 Token 和控制流程。除此之外，我們還需要 `*conti_jump_ir_index` 來記錄遇到 `continue` 後會跳到哪裡。在 `while` 中較幸運的是 `continue` 需要跳的位置和 unconditional jump back to expression 一樣，所以可以直接把 `start_label->ir_index` 作為 `continue` 後的位置。
### Consolidate prefix operation
這是我發的[第八個 PR](https://github.com/jserv/shecc/commit/d5bd5188b844b0116cb59de07ed8eb447d929e77)，原先的 `shecc` 無法讓 `++` 出現在等號的左邊，如:`for(;;++i)`。因為在 `for` 和一般 statement 處理 prefix expression 是分開的，所以需要到兩個地方補齊 prefix operation，第一個是一般的 statement，在 identifier (l-value) 前必須先看看有沒有 prefix:
```c
/* statement with prefix */
if (lex_accept(T_increment))
prefix_op = OP_add;
else if (lex_accept(T_decrement))
prefix_op = OP_sub;
/* must be an identifier */
if (!lex_peek(T_identifier, token))
error("Unexpected token");
```
第二個部分是在 `for` 中的 prefix operation:
```c
increment = add_instr(OP_label);
if (!lex_accept(T_close_bracket)) {
if (lex_accept(T_increment))
prefix_op = OP_add;
else if (lex_accept(T_decrement))
prefix_op = OP_sub;
lex_peek(T_identifier, token);
read_body_assignment(token, parent);
read_body_assignment(token, parent, prefix_op);
lex_expect(T_close_bracket);
}
```
### Support exclusive-or operator & Support modulo operator & Support bitwise not operator
接續的 3 個 PR 都是新增 operator，流程基本上都一樣:
1. 添加 Token
2. 新增 parsing 時判斷為該 Token 的流程
3. 添加 operator 的 priority
4. 補齊 evaluate immediate 的 operation (for global initialization)
5. 添加該 operator 該如何 encoding 成 binary (必須查 spec)
### Consolidate logical not operator
這是我發的[第 13 個 PR](https://github.com/jserv/shecc/commit/cb7935a197f6a2867766d9f30dc0b703e2d3a518)，原本 `shecc` 中的 logical not (`!`) 只能用於 0 或 1，但真實的 C 語言除了 0 以外都是 true，所以本 patch 就是試圖想讓 logical not 變成後者。需要改動的地方是 code generation 的部分:
```c
case OP_log_not:
emit(__teq(dest_reg));
emit(__mov_i(__NE, dest_reg, 0));
emit(__mov_i(__EQ, dest_reg, 1));
```
### Reserve return value from main function
這是我發的[第 14 個 PR](https://github.com/jserv/shecc/commit/a159d083508c33e48030d266029f3d7e7482a44f)，原本 `shecc` 中的 main function 的回傳值不會被保留，所以可以在 `tests/driver.sh` 中看到大量的 `exit` 而非 `return`，原因同前面所述。所以本 patch 預期修改此問題，並更換 `driver.sh` 中所有的 `exit` 成 `return`。
原先沒有變數來記住 main 的 `return` 值，以下宣告 `exit_ii` 來記錄:
```c
ir_instr_t *exit_ii; /* exit for program */
void read_func_call(func_t *fn, int param_no, block_t *parent)
{
...
if (!strcmp(ii->str_param1, "main"))
exit_ii->int_param1 = ii->param_no;
}
```
此外也需要在 codegen 的地方修改 `OP_exit`:
```c
case OP_exit:
/* syscall for 'exit' */
emit(__mov_r(__AL, __r0, OP_reg));
emit(__mov_i(__AL, __r7, 1));
emit(__svc());
```
### Support ternary operator
這是我發的[第 15 個 PR](https://github.com/jserv/shecc/commit/6ce22c9ae450166a67a2f5019eb16f7e01daa82f)，原本的 `shecc` 並沒有提供經典的三元運算子 `?:`，本 patch 修改了四個部分的前端，來達到支援 ternary operator:
1. global variable initialization
2. local variable initialization & assignment
3. expression of return
4. parameter list in function call
其實 ternary operator 就像 `if-else`，照著 `if-else` 的邏輯來完成。以下為在 block 內的 statement 使用 ternary operator:
```c
void read_ternary_operation(int dest, block_t *parent)
{
ir_instr_t *false_jump, *true_jump, *ii;
if (!lex_accept(T_question))
return;
/* ternary-operator */
false_jump = add_instr(OP_jz);
false_jump->param_no = dest;
/* true branch */
read_expr(dest, parent);
if (!lex_accept(T_colon))
return;
/* jump true branch to end of expression */
true_jump = add_instr(OP_jump);
ii = add_instr(OP_label);
false_jump->int_param1 = ii->ir_index;
/* false branch */
read_expr(dest, parent);
/* this is finish, link true jump */
ii = add_instr(OP_label);
true_jump->int_param1 = ii->ir_index;
}
```
## Trace code in detail
以下試圖仔細解釋每個函數的功能
### load_source_file
```cpp=
void load_source_file(char *file)
...
if ((strncmp(buffer, "#include ", 9) == 0) && (buffer[9] == '"')) {
char path[MAX_LINE_LEN];
int c = strlen(file) - 1;
while (c > 0 && file[c] != '/')
c--;
if (c) {
/* prepend directory name */
strncpy(path, file, c + 1);
c++;
}
path[c] = 0;
buffer[strlen(buffer) - 2] = 0;
strcpy(path + c, buffer + 10);
load_source_file(path);
}
```
第一次呼叫 `load_source_file` 參數為主程式的檔名，接著若該檔案裡面又有 `include` 的話就要再呼叫 `load_source_file`。假如主程式為 `aaa/main.c` 然後裡面 `include` 路徑 `../hi.h`，那 13 行的 `path` 就是 `aaa/` 而 `buffer` 就是 `../hi.h`，經過 15 行後 `path` 變成 `aaa/../hi.h`。
```cpp=
} else {
strcpy(SOURCE + source_idx, buffer);
source_idx += strlen(buffer);
}
```
如果該行不是 `include`，那就把 statement 存到 `SOURCE`（char pointer and access element through `source_idx`）
### read_global_statement
### read_global_decl
這個函數扮演了很重要的角色：解析 function 或全域變數的宣告！
`read_full_var_decl` 先把 type 存到 `vd->type_name`，接著 `read_inner_var_decl` 檢查：
(為了方便說明，假設該行為 `int* main(int arg){` )
* 是否為指標型態？`vd->is_ptr = 1`
* 將 variable name 存到 `vd`。範例為 `main`
* 檢查是否為陣列？範例為非，`vd->array_size = 0`
接著回到 1666 行，上面解析到 variable name，即 `main`，所以如果是 function 的話接著預期會有 '('。
1670 行呼叫 `add_func` 註冊新的函數，在 `add_func` 中會先看看，接著解析參數(1673)。再來就是 `read_body_statement` 解析 function 內的 statement。
可以透過 `readelf` 來觀察 elf 檔案內的格式
```
readelf -a fib
```
`token_str` 存的是 token 的字串，而非代稱。e.g. `T_break` 的 `token_str` 為 "break"
### lex_peek
純粹看看下一個 token 是否和參數傳入的 token 一樣，並回傳結果。不會 comsume 目前的 token。
### lex_accept
參數為欲檢查的 token，如果 token 的確是下一個 token 回傳 1，並讀入(`get_next_token`)下一個 token。
### lex_expect
激進版的 lex_accept，一定要出現預期的 token，否則報錯。
### lex_indent
會把目前的 token 寫到指定的字串供 caller 使用，並讀下一個 token。
### OP_address_of
```cpp
ii = add_instr(OP_address_of);
ii->param_no = param_no;
ii->str_param1 = var->var_name;
```
`param_no` 為 load 的 destination reg. `str_param1` 為要 load 的 variable name。稍後在 codegen 時透過 `str_param1` 找(var_t)。
## Example for mapping from IR to ARM instruction
對應 instrcution 的 encoding 規則可以參考 [ARM Architecture Reference Manual ARMv7-A and ARMv7-R edition](https://www.google.com/search?q=ARMv7-A+spec&oq=armv&aqs=chrome.0.69i59l3j69i57j0l2j69i61j69i60.3413j0j1&sourceid=chrome&ie=UTF-8)。
以下舉例如何查表，在 `codegen` 中
```cpp=208
case OP_load_constant:
/* load numeric constant */
val = ii->int_param1;
if (val >= 0 && val < 256) {
emit(__mov_i(__AL, dest_reg, val));
}
```
來看看 `mov_i` 是怎麼 encoding 的。
`mov_i` 呼叫 `__mov(cond, 1, arm_mov, 0, 0, rd, imm)`
```cpp
int arm_encode(arm_cond_t cond, int opcode, int rn, int rd, int op2)
{
return (cond << 28) + (opcode << 20) + (rn << 16) + (rd << 12) + op2;
}
int __mov(arm_cond_t cond, int io, int opcode, int s, int rn, int rd, int op2)
{
int shift = 0;
...
return arm_encode(cond, s + (opcode << 1) + (io << 5), rn, rd,
(shift << 8) + (op2 & 255));
}
```
對應 spec：
可以發現 `arm_mov` 是 13，即 $1101_b$。`(opcode << 1) + (io << 5)` 會變成 $111010_b$，接著 shift 20，剛好就是指令的 25~20 bits。
### ELF format
依據 [Wikipedia](https://en.wikipedia.org/wiki/Executable_and_Linkable_Format)，如果 size 是 4 就用 `elf_write_header_int`，如果是 2 就用兩次 `elf_write_header_byte`，注意順序，little endian。
來看看 section header 是怎麼寫的，在 `elf_generate_sections` 的 `.text` 部份，`elf_write_section_int(1)` 代表 `SHT_PROGBITS | Program data`。接著 flag 設 7 代表有三個 attribute is on。
#### Useful command for searching word
```shell
grep --include=\*.{c,h} -rnw -e "..."
```
Sign in with Wallet
Connect another wallet