2017q3 Homework3 (simulator)

tags: sysprogram

contributed by <st9007a>

Github

開發環境

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 來得知

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 的部分不一樣)

在給定的指令集中，規範了 heap 嗎？

jserv

其他：

• impl：instruction 的 opcode 對應的實作 ( handler )，在啟動虛擬機時，handler 會 hook 到對應的 opcode

應該一併提及如何從 opcode.def 產生對應 opcode.h 的過程，以及搭配 computed goto 實作更高效的 opcode dispatch。
參見: Computed goto for efficient dispatch tables

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 就完成了

TODO: 釐清以下議題:

1. instruction encoding 的長度，如 Stored Program and Instruction Representation 的分析;
2. 作為一個 register-based virtual machine (而非 stack-based, 如 Java VM)，能否進一步縮減編碼的空間開銷，進而提升 code density 呢？

jserv

vm 運作

vm 的運作有使用到大量的 macro

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

這段程式碼使用到 threaded code 的技巧，請以對應的 direct threading 解釋其效益，並對照單純的 switch-case，在效能上的落差

jserv

補充 - opcode dispatch

vm 的運作會將要執行的檔案處理成 bytecode 存放在 vm_env 這個結構中，執行時每次根據 pc 指向的位置去取得 bytecode 形式的 instruction 然後跳到對應的程式碼來執行該指令 ( 具體運作程式碼在上一小節 )

從 vm 的運作方式可以知道，如何根據目前的 opcode 跳到對應的程式碼的實作會影響 vm 的效能，根據 Computed goto for efficient dispatch tables 這篇提到了兩種實作方式，switch - case 以及 computed goto

switch - case 透過一個無窮迴圈內含一個 switch 來判斷目前的 bytecode 應該執行什麼程式，類似的實作還有 這篇，程式碼大致如下：

while (1) {   
    switch (instr[pc++]) {
        
        case OP_1:
            OP_1();
            break;
        case OP_2:
            OP_2();
            break;
        
        ...
    }
}

computed goto 是 C 語言的 feature GCC extension，參照 gcc - labels as values，可以將 label 的 address 存入 void * 型態的 pointer 中，用法如下：

void *ptr = &&label;
...
goto *ptr;

也能一次跟陣列搭配使用，先前提到的 opcode.h 中就有使用到

static void *array[] = { &&foo, &&bar, &&hack };
...
goto *array[0];

而使用 computed goto 來進行 opcode dispatch 的話，程式碼大致如下：

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 是比較有效率的實作方式

TODO: 研讀 Stack caching for interpreters 論文，思考進一步透過 caching top-of-stack 來提升效能的機制。

jserv

接受輸入參數

作業要求讓 vm 可以接受輸入參數，所以決定將輸入參數存入 vm 中的 #0 位置，在 vm.h 及 vm.c 加入一個可以設定 temps 的值的函式

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 的判斷

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

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)

參照 simple.vm 引入 fuzz testing

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，初始設定 #1 = f(0) = a, #2 = f(1) = b, #0 = n，然後每次遞迴會執行：

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);
}

計算和比較 tail recursion 運用後，實際 cycle count 的落差

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語言：遞迴呼叫篇 中的程式碼，將其轉換成組合語言版本

Profiler

為了能計算總共使用的 instructions 數量，寫一個 profiler.c：

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() 加入程式碼：

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 後，參考裡面的一些設計，如：使用 : 當作 label 的 prefix

接著 label 的實作策略用 two-pass assembler 的運作原理：掃程式碼一遍，把所有 label 跟對應的位置放在 symbol table，再掃程式碼一遍，把 call 跟 j type 指令跳的 label 根據 symbol table 轉成對應的位置

對應的程式碼寫在 as.c 中：

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

最後測試一下：

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)：

可以看到 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 的指令數量：

可以看到在大部分的情況下，fast doubling 的指令數量小於 iterative 的指令數量，尤其是輸入數值越接近

$2^n$，差異越大

參照之前學生的報告 Fibonacci fast doubling: ARM assembly 實作，引入 clz 一類的指令，可再提升 fast doubling 的效能

jserv

Fast Doubling with CLZ

參考 Fibonacci fast doubling: ARM assembly 實作，引入 clz 指令，在 opcode.def 加入 clz 指令：

clz,       23,       1,       1,          0

接著在 opcode.c 實作，這裡使用 built in function 來實作：

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 比較

由於原本的 else condition 所做的運算開銷非常大，引入 clz 重新實作後，指令數量大幅的減少

參考資料

stackoverflow - Are the shift operators (<<, >>) arithmetic or logical in C?
Linux 的目的檔
stackexchange - What exactly is virtual machine bytecode ?
Simple Virtual Machine
gcc - labels as values
stackoverflow - What is tail recursion ?
Tail recursion for fabonacci
Stack based vs Register based Virtual Machine Architecture, and the Dalvik VM
Fibonacci fast doubling: ARM assembly 實作