Try   HackMD

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

$(OUT)/$(STAGE0): $(OUT)/libc.inc $(OBJS)
	$(VECHO) "  LD\t$@\n"
	$(Q)$(CC) $(OBJS) -o $@

用 gcc 編譯 src 底下的檔案，產生執行檔 shecc

Stage 1

$(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

$(OUT)/$(STAGE2): $(OUT)/$(STAGE1)
	$(VECHO) "  SHECC\t$@\n"
	$(Q)$(ARM_EXEC) $(OUT)/$(STAGE1) -o $@ $(SRCDIR)/main.c

QEMU 可模擬在 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 一個專案從 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)。文末提供簡單的範例展示如何 mapping。

最後則是輸出 ELF 的檔案 (執行檔，based on ARM)，本步驟即 elf_generate，在 wiki 中有對 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，在 build 專案時會在 stage 1 就 crash，透過 gdb 找出在 allocate code block　(shecc 紀錄資料的結構) 時會 segmentation fault。在 8G 的記憶體下無法分配這麼多記憶體，解法就是減小分配的記憶體。(當然，隨著 shecc 的長大，終究還是要增加在 defs.h 中定義的 limitation)

Support divide operation

這是我發的第二個 PR，基本上新增 operator 流程都一樣:

  1. 添加 Token
  2. 新增 parsing 時判斷為該 Token 的流程
  3. 添加 operator 的 priority
  4. 添加該 operator 該如何 encoding 成 binary (必須查 spec)

Support global variable initialization

這是我發的第三個 PR，這個 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:

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。

PS. This patch haven't add .bss section for un-initialized data.

Rework malloc and free function

這是我發的第五個 PR，原本 shecc 並沒有提供 free。為了添增功能，這次需要改動的地方在內建函式庫 lib/c.c

參考文章對 malloc & free 的實作來完成功能，簡單來說需要維護一條 list，每個節點都代表分配的記憶體(包含 free 後，亦在 list 上)。malloc 時會先找 list 上看是否有被釋放的記憶體，如果要求的大小小於該節點，則直接使用該記憶體。反之，如果整條 list 都找不到恰當的節點，那就需要透過系統呼叫 brk。而 free 記憶體只需要將該節點的 is_free 標籤更改狀態即可。

Consolidate break for general loop

這是我發的第六個 PR，目前的 shecc 不支援在 while 中使用 break，此外，do_while 和 for 亦不支援 break。

原先遇到 break 就會跳到"應該跳的地方":

if (lex_accept(T_break)) {
        ii = add_instr(OP_jump);
        ii->int_param1 = break_exit_ir_index[break_level - 1];
    }

為了達成功能，我們需要重新設計 loop 附近的 label:

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，原本的 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，原先的 shecc 無法讓 ++ 出現在等號的左邊，如:for(;;++i)。因為在 for 和一般 statement 處理 prefix expression 是分開的，所以需要到兩個地方補齊 prefix operation，第一個是一般的 statement，在 identifier (l-value) 前必須先看看有沒有 prefix:

/* 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:

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，原本 shecc 中的 logical not (!) 只能用於 0 或 1，但真實的 C 語言除了 0 以外都是 true，所以本 patch 就是試圖想讓 logical not 變成後者。需要改動的地方是 code generation 的部分:

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，原本 shecc 中的 main function 的回傳值不會被保留，所以可以在 tests/driver.sh 中看到大量的 exit 而非 return，原因同前面所述。所以本 patch 預期修改此問題，並更換 driver.sh 中所有的 exit 成 return。

原先沒有變數來記住 main 的 return 值，以下宣告 exit_ii 來記錄:

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:

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，原本的 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:

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


















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。





} 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

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。

以下舉例如何查表，在 codegen 中







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)

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，即 1101b。(opcode << 1) + (io << 5) 會變成 111010b，接著 shift 20，剛好就是指令的 25~20 bits。

ELF format

依據 Wikipedia，如果 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

grep --include=\*.{c,h} -rnw -e "..."
Last changed by 
 
sysprog
System Software Programming
3
1329
Published on HackMD