2017q3 Homework3 (simulator)
===
contributed by <`Lihikoka`>
[GitHub](https://github.com/Lihikoka/full-stack-hello)
---
### Reviewed by `st9007a`
- computed goto 除了可以讓程式碼更簡潔，還有其他作用，應一併解釋，可以的話附上與 switch 的效能比較分析
- Fibonacci 的實作缺乏效能比較
- 尚有三種 Fibonacci 實現方式沒有實作 (tail recursion, q-matrix, fast doubling)
- 有發現到數值表達的上限 :+1:
- 發現到數值的上限後，應提出後續處理方案
- 有將 Fibonacci 加入測試流程 :+1:
---
# 開發環境
```
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 如下
```clike
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: 指令集的實作
```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;
```
* pc: program counter ，目前程式執行到的指令位址，與 `vm_env.insts` 搭配使用
* sp: stack pointer
## 程式流程
主程式為 `driver.c` ，先從沒有給參數的 case 開始看
```clike=
vm_env *env = vm_new();
assemble_from_fd(env, in_fd);
hook_opcodes(env);
vm_run(env);
vm_free(env);
```
可以得知流程為：
1. 先創造一個指向初始化後的 `vm_env` 的指標 `env`
2. 接著 `assemble_from_fd` 會從 `.s` 檔讀入每一行指令並放進 `env`
3. `hook_opcodes` 會將每個指令的名稱與實作「 hook 」在一起
4. 然後由 `vm_run` 來執行所有 `env->insts` 裡的指令
5. 最後 `vm_free` 將記憶體釋放。
### Computed goto 技巧
opcode.h:
```clike=
#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:
```clike=
#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
```clike=
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
```clike=
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]`
```clike=
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 同學共筆](https://hackmd.io/s/Hkf6pkPAb#fibonacci-數列)
# Fabonacci 數列
## iterative version
### C 語言程式碼
```clike=
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 語言程式碼
```clike=
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 修改成：
```python=
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` 指令的實作：
```clike=
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
```
Sign in with Wallet
Connect another wallet