2017q3 Homework3 (simulator)

contributed by <Lihikoka>
GitHub

Reviewed by `st9007a`

computed goto 除了可以讓程式碼更簡潔，還有其他作用，應一併解釋，可以的話附上與 switch 的效能比較分析
Fibonacci 的實作缺乏效能比較
尚有三種 Fibonacci 實現方式沒有實作 (tail recursion, q-matrix, fast doubling)
有發現到數值表達的上限
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
發現到數值的上限後，應提出後續處理方案
有將 Fibonacci 加入測試流程
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →

開發環境

Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                8
On-line CPU(s) list:   0-7
Thread(s) per core:    2
Core(s) per socket:    4
Socket(s):             1
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 58
Model name:            Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz
Stepping:              9
CPU MHz:               3899.291
CPU max MHz:           3900.0000
CPU min MHz:           1600.0000
BogoMIPS:              6784.16
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              8192K
NUMA node0 CPU(s):     0-7

Operating Sysetm:      Linux Mint 18.2 Cinnamon 64-bit
Cinnamon Version       3.4.6
Linux Kernel           4.8.0-53-generic

程式碼分析

資料結構：

整個虛擬機的精髓 virtual machine environment 如下

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

insts: 按照執行的順序儲存在連續記憶體裡的指令
cpool: constants
temps: stack ，是一個 array，從高記憶體位址 temps[TEMPS_MAX_SIZE - 1] 開始存取
opcode_impl: 指令集的實作






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;

pc: program counter ，目前程式執行到的指令位址，與 vm_env.insts 搭配使用
sp: stack pointer

程式流程

主程式為 driver.c ，先從沒有給參數的 case 開始看





vm_env *env = vm_new();
assemble_from_fd(env, in_fd);
hook_opcodes(env);
vm_run(env);
vm_free(env);

可以得知流程為：

先創造一個指向初始化後的 vm_env 的指標 env
接著 assemble_from_fd 會從 .s 檔讀入每一行指令並放進 env
hook_opcodes 會將每個指令的名稱與實作「 hook 」在一起
然後由 vm_run 來執行所有 env->insts 裡的指令
最後 vm_free 將記憶體釋放。

Computed goto 技巧

opcode.h:






#define OP_LABELS &&OP_HALT, &&OP_ADD, &&OP_SUB, &&OP_PRINT, &&OP_JLT, \
    &&OP_JLE, &&OP_JZ, &&OP_JGE, &&OP_JGT, \
    &&OP_JNZ, &&OP_JMP, &&OP_MUL, &&OP_DIV, \
    &&OP_MOD, &&OP_CALL, &&OP_RET, &&OP_AND, \
    &&OP_OR, &&OP_NOT, &&OP_XOR, &&OP_LSL, \
    &&OP_LSR, &&OP_ASR,

vm.c:





















































#define OPCODE env->insts[env->r.pc]

#define BEGIN_OPCODES                          \
    const static void *labels[] = {OP_LABELS}; \
    goto *labels[OPCODE.opcode]

#define DISPATCH                     \
    do {                             \
        ++env->r.pc;                 \
        goto *labels[OPCODE.opcode]; \
    } while (0)

#define GOTO(n)                      \
    do {                             \
        env->r.from = env->r.pc;     \
        env->r.to = n;               \
        env->r.pc = n;               \
        goto *labels[OPCODE.opcode]; \
    } while (0)
    
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;
}

因為都是在 run 函式內，所以如上方程式碼這樣定義 label 並 goto 這些 label 並執行對應的程式碼，雖然用 switch 也可以達到相同的功能，但是 computed goto 技巧可以讓程式碼看起來比較簡潔。

修改程式碼接受輸入參數

首先在 vm.c 中加入設定 temp 的值的函式，注意到因為要在外部呼叫，因此不加上 static qualifier






inline void vm_set_temp_value(vm_env *env, int pos, int n)
{
    vm_value v = {.type = INT};
    v.value.vint = n;
    env->temps[pos] = v;
}

在 drive.c 判斷輸入的 else if (argv[i][0] == '-') 之前加入接受輸入參數的 case





else if (!strcmp(argv[i], "--input")) {
    if (!argv[i + 1])
    FATAL(-1, "Missing an argument after --input\n");
    input_value = atoi(argv[++i]);
}

在 drive.c 的每個 vm_env *env = vm_new(); 的下一行設定輸入參數，儲存參數的位置都是在 temp[0]


vm_set_temp_value(env, 0, input_value);

在 Makefile 中加入 fib 選項與相關操作：

TEMP ?= 20
FILE_FIB_ITER ?= ./tests/fib-iterative.s
FILE_FIB_RECU ?= ./tests/fib-recursive.s

fib: $(EXEC)
	@./$(EXEC) --input $(TEMP) $(FILE_FIB_ITER)
	@./$(EXEC) --input $(TEMP) $(FILE_FIB_RECU)

參考資料： st9007a 同學共筆

Fabonacci 數列

iterative version

C 語言程式碼



















int fib_iterative(int n) {
    if (n == 0)
        return n;
    if (n == 1)
        return n;

    int first = 0;
    int second = 1;
    int result = 0;

    int i = n - 1;
    while(i > 0) {
        i--;
        result = first + second;
        first = second;
        second = result;
    }
    return result;
}

對應的組合語言

fib-iterative.s





























; if (n == 0) return n
jz #0 #15

; if (n == 1) return n
sub #0 $1 #5
jz #5 #15

; #1: first = 0
; #2: second = 1
; #3: result = 0
; #4: i = n - 1
or $0 $0 #1
or $0 $1 #2
or $0 $0 #3
sub #0 $1 #4

; iteration
jz #4 #13
sub #4 $1 #4
add #1 #2 #3
or $0 #2 #1
or $0 #3 #2
call #7

print #3
halt

print #0
halt

recursive version

C 語言程式碼





int fib_recursive(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib_recursive(n - 1) + fib_recursive(n - 2);
}

對應的組合語言

fib-recursive.s





































; #0: n
; #1: result
; #2: temp

; initialize result to 0
or $0 $0 #1

; enter to recursion
call #4

; print result
print #1
halt

; recursion
; if #0 == 1 is true, #1 = #1 + 1, then return
xor $1 #0 #2
jz #2 #7
jnz #2 #9
add #1 $1 #1
ret

; if #0 == 0 is true, then return
xor $0 #0 #2
jz #2 #12
jnz #2 #13
ret

; fib(n-1)
sub #0 $1 #0
call #4
; fib(n-2)
sub #0 $1 #0
call #4
; compensate n the subtracted 2
add #0 $2 #0
ret

Overflow

$ ./as_exec tests/fib-iterative.s --input 46
1836311903
$ ./as_exec tests/fib-iterative.s --input 47
-1323752223

發現輸入值超過 46 後就會導致 integer overflow

修改自動測試程式

在 Makefile 中有提供 test 功能，是利用 runner.py 來抓每個 .s 檔來執行並和對應的預期執行結果 .expected 檔來作比較。

將 Makefile 中 fib: 選項的輸入參數設為 40 並將其答案 6765 寫入檔案 fib-iterative.expected 和 fib-recursive.expected。

runner.py 取得執行結果的 function 都是直接執行，沒有輸入參數，因應 fib-iterative.s 和 fib-recursive.s 需要接受輸入參數，將 function 修改成：





def get_exec_output(testfile):
    if testfile == 'tests/fib-iterative' or testfile == 'tests/fib-recursive':
        return subprocess.check_output(['./as_exec', '%s.s' % testfile, '--input', '20'])
    else:
        return subprocess.check_output(['./as_exec', '%s.s' % testfile])

研究了一下 subprocess 模組中 check_output ，用途是產生一個執行第一個參數所代表的指令的 child process，並檢查 return 值是否為 0 ，若不為 0 則發生 Error

執行 make test：

.FF....
======================================================================
FAIL: test_fib-iterative (__main__.TestRunner)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "tests/runner.py", line 41, in test
    self.assertEqual(got, expected)
AssertionError: '6765\n' != '6765'

======================================================================
FAIL: test_fib-recursive (__main__.TestRunner)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "tests/runner.py", line 41, in test
    self.assertEqual(got, expected)
AssertionError: '6765\n' != '6765'

----------------------------------------------------------------------
Ran 7 tests in 0.001s

FAILED (failures=2)
Makefile:49: recipe for target 'test' failed
make: *** [test] Error 1

發現結果說 6765\n != 6765 ，然後去 opcode.c 看 print 指令的實作：













static void print_impl(VM_HANDLER_ARGS)
{
    switch (VM_T(op1)) {
    case INT:
        printf("%d\n", op1->value.vint);
        break;
    case STR:
        printf("%s\n", op1->value.vstr);
        break;
    default:
        break;
    }
}

當中有換行符號「\n」，但是其他測試檔 (例如 mul.s) 中也有包含 print 指令，但是卻沒有出錯，於是發現 mul.expected 中最後一行有 blank line ，於是在 fib-iterative.expected 和 fib-recursive.expected 的最後面也加入 blank line，並執行 make test 得到結果：

.......
----------------------------------------------------------------------
Ran 7 tests in 0.001s

OK

2017q3 Homework3 (simulator)

Reviewed by st9007a

開發環境

程式碼分析

資料結構：

程式流程

Computed goto 技巧

修改程式碼接受輸入參數

Fabonacci 數列

iterative version

C 語言程式碼

對應的組合語言

recursive version

C 語言程式碼

對應的組合語言

Overflow

修改自動測試程式

Reviewed by `st9007a`