738 views
# 2017q3 Homework3 (simulator) contributed by <`st9007a`> ## [Github](https://github.com/st9007a/full-stack-hello) ## 開發環境 ``` Linux 4.4.0-92-generic Ubuntu 16.04.1 LTS CPU family: 6 CPU model: 94 CPU model name: Intel(R) Core(TM) i5-6500 CPU @ 3.20GHz L1d cache: 32K L1i cache: 32K L2 cache: 256K L3 cache: 6144K ``` ## 解析原始碼 在 `full-stack-hello` 這個 repo 中,主要以 `driver.c` 這支程式為操作的主體,其他程式提供相關的函式: - `vm`:虛擬機器,內涵虛擬機器的架構, 運作 - `opcode`:自訂指令集,以及相關實作,實作主要用於虛擬機器 - `as`:組譯器,用於組譯自訂指令集,產生對應的 object file - `elf`:提供產生 object file 相關的函式 ### vm 架構 vm 架構可以從 `vm_env` 以及 `vm_regs` 來得知 ```clike typedef struct { size_t pc; // program counter. size_t sp; // stack runs from the end of 'temps' region. size_t from; // the immediate PC before last branch/return. size_t to; // the immediate PC after last branch/return. } vm_regs; struct __vm_env { vm_inst insts[INSTS_MAX_SIZE]; /* Program instructions */ vm_value cpool[CPOOL_MAX_SIZE]; /* Constant pool */ vm_value temps[TEMPS_MAX_SIZE]; /* Temporary storage */ vm_opcode_impl impl[OPCODE_IMPL_MAX_SIZE]; /* OPCODE impl */ vm_regs r; int insts_count; int cpool_count; int temps_count; } ``` register: - pc:program counter,指向目前執行的指令的位置 - sp:stack pointer,指向目前 stack 最後的位置 - from:指向最後一個 branch/return 之前的 pc 所指向的位置 - to:指向最後一個 branch/return 之後的 pc 所指向的位置 storage: - insts:紀錄 program 中每個 instruction - cpool:儲存 program 中使用的常數 - temps:從 0 開始記錄暫存的變數,從尾端開始則是 stack,用於處理 call 跟 ret 指令 (類似 heap 與 stack 的關係,但是 heap 的部分不一樣) :::danger 在給定的指令集中,規範了 heap 嗎? :notes: jserv ::: 其他: - impl:instruction 的 opcode 對應的實作 ( handler ),在啟動虛擬機時,handler 會 hook 到對應的 opcode :::danger 應該一併提及如何從 `opcode.def` 產生對應 `opcode.h` 的過程,以及搭配 computed goto 實作更高效的 opcode dispatch。 參見: [Computed goto for efficient dispatch tables](https://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables) :notes: jserv ::: ### 補充 - 自訂指令集 在 vm 中所使用的指令集被定義於 `opcode.def` 這份檔案中,內容如下: ``` name, opcode, has_op1, has_op2, has_result halt, 0, 0, 0, 0 add, 1, 1, 1, 1 sub, 2, 1, 1, 1 mul, 11, 1, 1, 1 div, 12, 1, 1, 1 mod, 13, 1, 1, 1 and, 16, 1, 1, 1 or, 17, 1, 1, 1 not, 18, 1, 1, 0 xor, 19, 1, 1, 1 lsl, 20, 1, 1, 1 lsr, 21, 1, 1, 1 asr, 22, 1, 1, 1 print, 3, 1, 0, 0 jlt, 4, 1, 1, 0 jle, 5, 1, 1, 0 jz, 6, 1, 1, 0 jge, 7, 1, 1, 0 jgt, 8, 1, 1, 0 jnz, 9, 1, 1, 0 jmp, 10, 1, 0, 0 call, 14, 1, 0, 0 ret, 15, 0, 0, 0 ``` 從欄位可以很容易得知,裡面分別定義該指令的名字, opcode, 以及 oprand,接著 `opcode.h` 這支檔案可以透過 `opcode.def` 以及 `scripts/gen_opcode.py` 來自動產生,簡單列一下 `gen_code.py` 的架構如下: ``` OPCODE : class -__gt__ : function -__init__ : function -__repr__ : function -__str__ : function +main : function +write_opcode : function ``` `OPCODE` 這個 class 存著 instruction 的設定,透過 `main()` 將 `opcode.def` 的設定放進 `OPCODE` 中,接著 `write_opcode()` 利用所有 `OPCODE` 來產生出 `opcode.h` 這樣的作法讓指令集的擴增修改變的很靈活,只需在 `opcode.def` 中加入新的指令設定,然後在 `opcode.c` 中實作該指令的行為,最後在 `hook_opcodes()` 中把實作 hook 到對應的 opcode 就完成了 :::danger TODO: 釐清以下議題: 1. instruction encoding 的長度,如 [Stored Program and Instruction Representation](http://www.eecg.toronto.edu/~moshovos/ECE243-2008/l19-instruction-representation-stored-program.html) 的分析; 2. 作為一個 register-based virtual machine (而非 stack-based, 如 Java VM),能否進一步縮減編碼的空間開銷,進而提升 code density 呢? :notes: jserv ::: ### vm 運作 vm 的運作有使用到大量的 macro ```clike void vm_run(vm_env *env) { BEGIN_OPCODES; OP(ADD) : VM_CALL_HANDLER(); OP(SUB) : VM_CALL_HANDLER(); OP(MUL) : VM_CALL_HANDLER(); OP(DIV) : VM_CALL_HANDLER(); OP(MOD) : VM_CALL_HANDLER(); OP(AND) : VM_CALL_HANDLER(); OP(OR) : VM_CALL_HANDLER(); OP(NOT) : VM_CALL_HANDLER(); OP(XOR) : VM_CALL_HANDLER(); OP(LSL) : VM_CALL_HANDLER(); OP(LSR) : VM_CALL_HANDLER(); OP(ASR) : VM_CALL_HANDLER(); OP(PRINT) : VM_CALL_HANDLER(); OP(JLT) : VM_JLT(); OP(JLE) : VM_JLE(); OP(JZ) : VM_JZ(); OP(JGE) : VM_JGE(); OP(JGT) : VM_JGT(); OP(JNZ) : VM_JNZ(); OP(JMP) : GOTO(OPCODE.op1.value.id); OP(CALL) : VM_CALL(OPCODE.op1.value.id); OP(RET) : VM_RET(); OP(HALT) : goto terminate; END_OPCODES; terminate: return; } ``` - BEGIN_OPCODES:產生 op label set,並且跳到第一個 instruction 對應的 op label - OP:產生對應的 label - VM_CALL_HANDLER, VM_CALL, VM_RET, VM_J\*:根據 instruction 執行不同 handler - OPCODE:取得目前 pc 指向的位置的 instruction - OPCODE_IMPL:取得對應的 handler - DISPATCH:將 pc 指向下一個 instruction,並且跳到對應的 label 執行 - GOTO:將 pc 指向特定位置,並將 pc 轉跳前後所指的位置存入暫存器 from, to :::danger 這段程式碼使用到 [threaded code](https://en.wikipedia.org/wiki/Threaded_code) 的技巧,請以對應的 direct threading 解釋其效益,並對照單純的 switch-case,在效能上的落差 :notes: jserv ::: ### 補充 - opcode dispatch vm 的運作會將要執行的檔案處理成 bytecode 存放在 `vm_env` 這個結構中,執行時每次根據 pc 指向的位置去取得 bytecode 形式的 instruction 然後跳到對應的程式碼來執行該指令 ( 具體運作程式碼在上一小節 ) 從 vm 的運作方式可以知道,如何根據目前的 opcode 跳到對應的程式碼的實作會影響 vm 的效能,根據 [Computed goto for efficient dispatch tables](https://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables) 這篇提到了兩種實作方式,switch - case 以及 computed goto switch - case 透過一個無窮迴圈內含一個 switch 來判斷目前的 bytecode 應該執行什麼程式,類似的實作還有 [這篇](http://bartoszsypytkowski.com/simple-virtual-machine/),程式碼大致如下: ```clike while (1) { switch (instr[pc++]) { case OP_1: OP_1(); break; case OP_2: OP_2(); break; ... } } ``` computed goto 是 <s>C 語言的 feature</s> GCC extension,參照 [gcc - labels as values](https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html),可以將 label 的 address 存入 `void *` 型態的 pointer 中,用法如下: ```clike void *ptr = &&label; ... goto *ptr; ``` 也能一次跟陣列搭配使用,先前提到的 `opcode.h` 中就有使用到 ```clike static void *array[] = { &&foo, &&bar, &&hack }; ... goto *array[0]; ``` 而使用 computed goto 來進行 opcode dispatch 的話,程式碼大致如下: ```clike static void *op_labels = { &&OP_1, &&OP_2, .... }; #define DISPATCH() goto *op_labels[instr[pc++]] ... OP_1: OP_1(); DISPATCH(); OP_2: OP_2(); DISPATCH(); ... ``` 這兩種的效能比較可以從兩個地方來看: - bounds checking - branch prediction bounds checking 是在 switch 中執行的一個環節,每次迴圈中檢查是否有 default case 的狀況,在參考資料中提到,即使程式中的 switch 沒有用到 default case,compiler 在編譯時還是會產生強制檢查的程式,所以 switch 會較 computed goto 多花一個 bounds checking 的步驟 branch prediction 的部分,switch 需要預測接下來跳到哪個分支 case,而 computed goto 則是在每個 instruction 預測下一個 instruction,這之中比較直覺的想法是 computed goto 的可以根據上個指令來預測,但是 switch 的每次預測沒辦法根據上個指令,因此在 branch prediction accuracy 上 computed goto 會比較高 根據上述兩點來看,computed goto 是比較有效率的實作方式 :::danger TODO: 研讀 [Stack caching for interpreters](https://dl.acm.org/citation.cfm?id=207165) 論文,思考進一步透過 caching top-of-stack 來提升效能的機制。 :notes: jserv ::: ## 接受輸入參數 作業要求讓 vm 可以接受輸入參數,所以決定將輸入參數存入 vm 中的 `#0` 位置,在 `vm.h` 及 `vm.c` 加入一個可以設定 `temps` 的值的函式 ```clike inline void vm_set_temp_value(vm_env *env, int pos, int val) { vm_value v = {.type = INT}; v.value.vint = val; env->temps[pos] = v; } ``` 然後在 `driver.c` 中解析 `argv` 的部份加入 `--input` 的判斷 ```clike int vm_init_val = 0; ... else if (!strcmp(argv[i], "--input")) { if (!argv[i + 1]) FATAL(-1, "--input need a integer as argument, see -h\n"); vm_init_val = atoi(argv[++i]); } ... ``` 接著在 `driver.c` 中初始化 vm 的下一行都強制設定 `#0` ```clike vm_env *env = vm_new(); vm_set_temp_value(env, 0, vm_init_val); ``` 最後在 `Makefile` 中加入 Fibonacci 數列的相關操作 ``` TEMP0 ?= 1 IN_FILE ?= ./tests/fib-iterative.s fib: $(EXEC) @./$(EXEC) --input $(TEMP0) $(IN_FILE) ``` :::danger 參照 [simple.vm](https://github.com/skx/simple.vm) 引入 fuzz testing :notes: jserv ::: ## Fibonacci 數列 ### Iterative ``` ; if #0 = 0, just print 0 xor #0 $0 #1 jz #1 #13 sub #0 $1 #0 ; f0 = 0, f1 = 1 or $0 $0 #1 or $1 $0 #2 ; iteration add #1 #2 #3 or $0 #2 #1 or $0 #3 #2 sub #0 $1 #0 jz #0 #11 jgt #0 #5 ; print result print #3 halt ; print result if input = 0 print $0 halt ``` 這是一個簡易版本的 iterative 實作,輸入參數存放在 `#0`,輸出結果存放在 `#3`,`#1` 跟 `#2` 一開始分別存放 $f(0)$ 跟 $f(1)$ 的答案,其中 xor 跟 or 指令分別是拿來替代 x86 instruction set 中的 cmp 以及 mov ### Recursive ``` ; init result at #3 or $0 $0 #3 ; f0 = 0, f1 = 1 or $0 $0 #1 or $1 $0 #2 call #6 ; print result print #3 halt ; recursion xor #0 #2 #5 jz #5 #9 jnz #5 #11 add #3 #2 #3 ret xor #0 #1 #5 jz #5 #14 jnz #5 #15 ret sub #0 $1 #0 call #6 sub #0 $1 #0 call #6 add #0 $2 #0 ret ``` 接著是簡易版本的 recursive 實作,輸入參數存放在 `#0`,輸出存放在 `#3`,recursive 的部分可以看成一個 function,這個 function 的 input 也是 `#0`,每次都會比較 input 是否為 0 或 1,是的話就將$f(0)$ 或 $f(1)$ 加進去 `#3`,不是的話就呼叫 f( `#0` - 1 ) 跟 f( `#0` - 2 ),由於在呼叫的過程中 `#0` 的值會不斷減少,所以最後要加回來 ### Tail Recursion ``` ; init or $0 $0 #1 or $0 $1 #2 or $0 $0 #3 ; call func call #6 print #3 halt ; tail recursion xor #0 $0 #4 jz #4 #9 jnz #4 #11 or #1 $0 #3 ret xor #0 $1 #4 jz #4 #14 jnz #4 #16 or #2 $0 #3 ret ; #1 = #2, #2 = #1 + #2 or #1 $0 #5 or #2 $0 #1 add #2 #5 #2 sub #0 $1 #0 call #6 ret ``` tail recursion 跟一般遞迴的差在於它會把目前為止累積的答案傳給下一個遞迴的 function call,這樣的作法可以減少遞迴的重複運算,這裡的實作參考了 [Tail recursion for fabonacci](http://www.geeksforgeeks.org/tail-recursion-fibonacci/),初始設定 `#1 = f(0) = a, #2 = f(1) = b, #0 = n`,然後每次遞迴會執行: ```clike int fib(int n, int a = 0, int b = 1) { if (n == 0) return a; if (n == 1) return b; return fib(n - 1, b, a + b); } ``` :::danger 計算和比較 tail recursion 運用後,實際 cycle count 的落差 :notes: jserv ::: ### Fast doubling ``` xor #0 $0 #1 jz #1 #32 ; init variable or $1 $0 #1 ; t0 = 1 or $1 $0 #2 ; t1 = 1 or $1 $0 #3 ; t3 = 1 or $0 $0 #4 or $1 $0 #5 ; i = 1 ; while (i < n) or #0 $0 #6 ; copy input to #6 sub #6 #5 #6 jlt #6 #30 jz #6 #30 ; if ((i << 1) <= n) or #0 $0 #6 lsl #5 $1 #7 sub #7 #6 #7 jgt #7 #25 mul #2 #2 #4 ; t4 = t1 * t1 mul #1 #1 #7 ; tmp = t0 * t0 add #4 #7 #4 ; t4 += tmp mul $2 #2 #3 ; t3 = t1 * 2 sub #3 #1 #3 ; t3 -= t0 mul #1 #3 #3 ; t3 *= t0 or $0 #3 #1 ; t0 = t3 or $0 #4 #2 ; t1 = t4 lsl #5 $1 #5 ; i <<= 1 jmp #7 ; else or $0 #3 #1 ; t0 = t3 or $0 #4 #3 ; t3 = t4 add #4 #1 #4 ; t4 += t0 add #5 $1 #5 ; i += 1 jmp #7 print #3 halt print $0 halt ``` fast doubling 是基於 Fabonacci Q-Matrix 推導出來的,主要有兩個公式: $F(2k) = F(k) \times (2F(k + 1) - F(k))$ $F(2k + 1) = F(k + 1)^2 + F(k)^2$ 然後參考 [你所不知道的C語言:遞迴呼叫篇](https://hackmd.io/s/rJ8BOjGGl#fibonacci-sequence) 中的程式碼,將其轉換成組合語言版本 ## Profiler 為了能計算總共使用的 instructions 數量,寫一個 `profiler.c`: ```clike static uint32_t exec_instr_cnt = 0; inline void profiling() { #if defined(profile) exec_instr_cnt++; #endif } void show_profiling_info() { printf("Instructions: %u\n", exec_instr_cnt); } ``` 然後在每個 handler 相關的 macro 都加入 `profiling();`,最後在 `vm_run()` 加入程式碼: ```clike void vm_run(vm_env *env) { ... END_OPCODES; terminate: #if defined(profile) show_profiling_info(); #endif return; } ``` 如此就能透過 `Makefile` 來決定是否開啟 profiler 以下簡單顯示結果: ``` $ ./as_exec --input 20 tests/fib-iterative.s 6765 Instructions: 120 $ ./as_exec --input 20 tests/fib-recursive.s 6765 Instructions: 183492 $ ./as_exec --input 20 tests/fib-tailrecursion.s 6765 Instructions: 241 $ ./as_exec --input 20 tests/fib-fastdoubling.s 6765 Instructions: 208 ``` ## Add Label Support 由於在測試組合語言過程中頻繁修改程式碼,每次改完都要注意 call 跟 j type 指令有沒有跳錯位置,工作效率不佳,因此決定先把 label 功能加上去,看了 [Add label support](https://github.com/jserv/full-stack-hello/pull/30) 後,參考裡面的一些設計,如:使用 `:` 當作 label 的 prefix 接著 label 的實作策略用 two-pass assembler 的運作原理:掃程式碼一遍,把所有 label 跟對應的位置放在 symbol table,再掃程式碼一遍,把 call 跟 j type 指令跳的 label 根據 symbol table 轉成對應的位置 對應的程式碼寫在 `as.c` 中: ```clike struct __symbol_table { char *labels[SYMBOL_TABLE_SIZE]; int address[SYMBOL_TABLE_SIZE]; int count; }; static symbol_table symtab = {.count = 0}; static void insert_to_symtab(char *label, int address) { assert(symtab.count < SYMBOL_TABLE_SIZE); for (int i = 0; i < symtab.count; i++) { assert(strcmp(label, symtab.labels[i]) != 0); } symtab.labels[symtab.count] = strdup(label); symtab.address[symtab.count] = address; symtab.count++; } static int search_symtab(char *label) { for (int i = 0; i < symtab.count; i++) { if (strcmp(symtab.labels[i], label) == 0) return symtab.address[i]; } return -1; } static void lookup_address(vm_env *env) { vm_inst *inst = NULL; for (int i = 0; (inst = get_vm_inst(env, i)) != NULL; i++) { if (inst->op1.type == LABEL) { int new_addr = search_symtab(inst->op1.value.label); assert(new_addr != -1); inst->op1.value.id = new_addr; } if (inst->op2.type == LABEL) { int new_addr = search_symtab(inst->op2.value.label); assert(new_addr != -1); inst->op2.value.id = new_addr; } } } ``` 主要是新增了 symbol table 的結構,以及對 symbol table 的操作,`lookup_address()` 是上面提到的掃第二次程式碼時對其做 label 替換的函式,細節程式碼可以參照 [github](https://github.com/st9007a/full-stack-hello/commit/150ec6d4bf4bf9e64349d49de1d5a0e30b8a901d) 最後測試一下: ``` call :testcall print "fail" halt testcall print "call success" jmp :testjmp print "fail" halt testjmp print "jmp success" or $0 $0 #0 jz #0 :testjz print "fail" halt testjz print "jz success" add $1 #0 #0 jnz #0 :testjnz print "fail" halt testjnz print "jnz success" jge #0 :testjge1 print "fail" halt testjge1 print "jge success" sub #0 $1 #0 jge #0 :testjge2 print "fail" halt testjge2 print "jge success" jle #0 :testjle1 print "fail" testjle1 print "jle success" sub #0 $1 #0 jle #0 :testjle2 print "fail" halt testjle2 print "jle success" jlt #0 :testjlt print "fail" halt testjlt print "jlt success" add #0 $2 #0 jgt #0 :testjgt print "fail" halt testjgt print "jgt success" halt ``` 執行結果: ``` $ ./as_exec tests/label.s call success jmp success jz success jnz success jge success jge success jle success jle success jlt success jgt success ``` ## 效能比較 首先先比較有效範圍內(0 ~ 46)四種演算法所花費的指令數量,這裡只顯示(0 ~ 40): ![](https://i.imgur.com/SU9DayC.png) 可以看到 recursive 的指令數量是指數成長,這也符合 recursive 的時間複雜度為 $O(2^n)$,而 iterative 跟 tail recursion 的時間複雜度為 $O(n)$,所以是線性成長,但是由於 tail recursion 每次 iteration 做的指令比較多,所以斜率比較大 接著 fast doubling 在迴圈中的行為是先用每次迴圈乘 2 跳到最接近輸入的值之後再做改成每次迴圈加 1,所以會出現驟降的現象,驟降會發生在輸入值剛好是 2 的指數的時候 為了更仔細比較 iterative 跟 fast doubling 的差異,在不考慮 integer overflow 的狀況下,比較輸入數值 0 ~ 20000 的指令數量: ![](https://i.imgur.com/kyJyZ26.png) 可以看到在大部分的情況下,fast doubling 的指令數量小於 iterative 的指令數量,尤其是輸入數值越接近 $2^n$,差異越大 :::danger 參照之前學生的報告 [Fibonacci fast doubling: ARM assembly 實作](https://www.slideshare.net/erickitten/fibonacci-fast-doubling),引入 clz 一類的指令,可再提升 fast doubling 的效能 :notes: jserv ::: ## Fast Doubling with CLZ 參考 [Fibonacci fast doubling: ARM assembly 實作](https://www.slideshare.net/erickitten/fibonacci-fast-doubling),引入 clz 指令,在 opcode.def 加入 clz 指令: ``` clz, 23, 1, 1, 0 ``` 接著在 `opcode.c` 實作,這裡使用 built in function 來實作: ```clike static void clz_impl(VM_HANDLER_ARGS) { if (VM_T(op1) == INT && VM_T(op2) == INT) { VM_INT(op2) = __builtin_clz(VM_INT(op1)); } else { UNIMPL; } } ``` 有了 clz 指令後,寫一個 fast doubling with clz 的版本: ``` xor $0 #0 #1 jz #1 :output clz #0 #1 sub $30 #1 #1 or $1 $0 #2 or $1 $0 #3 xor $1 #0 #4 jz #4 :exit fib lsl #3 $1 #4 sub #4 #2 #4 mul #4 #2 #4 mul #2 #2 #6 mul #3 #3 #5 add #5 #6 #5 or #5 $0 #3 or #4 $0 #2 lsr #0 #1 #5 and #5 $1 #5 jz #5 :no_adv add #2 #3 #4 or #3 $0 #2 or #4 $0 #3 no_adv jz #1 :exit sub #1 $1 #1 jmp :fib exit or #2 $0 #0 output print #0 halt ``` 它的原理是利用 clz 算出最高有效位右邊的 bit 數,接著利用 bit-shift 從最高有效位開始一個一個往右檢查,每檢查一個 bit 就做 1 次 fast doubling 運算,如果檢查到的 bit 為 1,就做一次 $f(n) = f(n-1) + f(n-2)$ 的計算 這樣的作法大幅減少了原本版本 fast doubling 的 else condition 的計算,下圖為輸入數值 0 ~ 1000 原本的 fast doubling 跟 clz 版的 fast doubling 比較 ![](https://i.imgur.com/00Cxaqj.png) 由於原本的 else condition 所做的運算開銷非常大,引入 clz 重新實作後,指令數量大幅的減少 ## 參考資料 [stackoverflow - Are the shift operators (<<, >>) arithmetic or logical in C?](https://stackoverflow.com/questions/7622/are-the-shift-operators-arithmetic-or-logical-in-c) [Linux 的目的檔](http://ccckmit.wikidot.com/lk:objfile) [stackexchange - What exactly is virtual machine bytecode ?](https://softwareengineering.stackexchange.com/questions/231054/what-exactly-is-virtual-machine-bytecode) [Simple Virtual Machine](http://bartoszsypytkowski.com/simple-virtual-machine/) [gcc - labels as values](https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html) [stackoverflow - What is tail recursion ?](https://stackoverflow.com/questions/33923/what-is-tail-recursion) [Tail recursion for fabonacci](http://www.geeksforgeeks.org/tail-recursion-fibonacci/) [Stack based vs Register based Virtual Machine Architecture, and the Dalvik VM](https://markfaction.wordpress.com/2012/07/15/stack-based-vs-register-based-virtual-machine-architecture-and-the-dalvik-vm/) [Fibonacci fast doubling: ARM assembly 實作](https://www.slideshare.net/erickitten/fibonacci-fast-doubling)