# 2017q3 Homework3 (simulator)
contributed by <`ZixinYang`>
## 研究 [full-stack-hello](https://github.com/sysprog21/full-stack-hello) 程式碼
### README
本作業目的: 用小型的指令集及組譯/編譯器實現 Hello World 程式
### Makefile
* `$make`: 編譯所有檔案
* `$make check`: 執行 tests 目錄下的所有 .s 檔
* `$make test`: 執行 tests/runner.py
### 組譯器使用
```
$ ./as_exec -h
Usage: as_exec [-w] [-x] [-o <out_file>] <in_file>
-w Assemble <in_file> and write to an ELF file, see -o below
-o if -w is specifed, <out_file> is used to store the object code
-x Load <in_file> and execute it
<in_file> the file name to be used by commands above
```
* 不加參數: 組譯和執行
* -w: 組譯並輸出 ELF 格式目的檔 `tests/hello.o`
* -o: 指定目的檔儲存的位置
* -x: 載入目的檔並執行
* 實行看看並用 objdump 顯示所有標頭檔資訊
```
$ ./as_exec -o tests/hello.o -w tests/hello.s
$ ./as_exec -x tests/hello.o
Hello World
$ objdump -x tests/hello.o
tests/hello.o: file format elf64-little
tests/hello.o
architecture: UNKNOWN!, flags 0x00000102:
EXEC_P, D_PAGED
start address 0x0000000000000000
Program Header:
0x464c457f off 0x0000000000000000 vaddr 0x0000000100000002 paddr 0x0000000000000000 align 2**54
filesz 0x0000000000000000 memsz 0x0000000000000000 flags -w- 10100
INTERP off 0x0000000000000001 vaddr 0x00000000000000e8 paddr 0x0000000000000000 align 2**5
filesz 0x0000000000000000 memsz 0x0000000000000018 flags ---
0x20 off 0x0000000000000001 vaddr 0x0000000000000100 paddr 0x0000000000000000 align 2**5
filesz 0x0000000000000000 memsz 0x000000000000001c flags ---
Sections:
Idx Name Size VMA LMA File off Algn
SYMBOL TABLE:
no symbols
```
|file|Implementation|
|:--------:|:-------:|
|driver.c|主程式，判斷 argv 呼叫對應的 function|
|as|組譯器， 呼叫 elf 裡函式, 將組語轉換成機器碼, 產生目的檔 (.o)|
|elf|內含組譯所需函式|
|opcode|指令集的實作|
|vm|虛擬機器實作|
### as
* functions:
```
ASSEMBLE_AND_EVAL // 組譯並執行
ASSEMBLE_AND_ELF // 組譯並輸出成 ELF 目的檔
LOAD_ELF_AND_EVAL // 載入之前輸出好的目的檔並執行
```
### opcode
* functions
```
driver.c 呼叫 hook_opcodes
hook_opcodes // 呼叫 vm_hook_opcode_handler, 傳入 opcode 及對應的函式
vm_hook_opcode_handler // 紀錄 opcode 及對應的函式
```
### vm
* variables
```
size_t pc; // 指向目前執行的指令的位置
size_t sp; // 指向目前 stack 最後的位置
size_t from; // 指向最後一個 branch/return 之前的位置
size_t to; // 指向最後一個 branch/return 之後的位置
vm_inst insts[INSTS_MAX_SIZE]; /* 紀錄 instruction*/
vm_value cpool[CPOOL_MAX_SIZE]; /* 儲存常數 */
vm_value temps[TEMPS_MAX_SIZE]; /* 暫存器 */
vm_opcode_impl impl[OPCODE_IMPL_MAX_SIZE]; /* 紀錄指令集 */
vm_regs r;
int insts_count;
int cpool_count;
int temps_count;
```
* functions
```
driver.c 呼叫 vm_run 開始進入虛擬機器的程式碼
VM_CALL_HANDLER // env 已 hook 的 opcode handler 在這裡實現
// 實現 compute goto, 將 pc 指向特定位置 (符合情況才跳)
VM_JLT, VM_JLE(), VM_JZ(), VM_JGE(), VM_JGT, VM_JNZ(), VM_CALL(), VM_RET()
```
### gen_opcode.py
讀取 `opcode.def`, 將各個 operation 的資訊存在 class `OPCODE` , 並輸出 `opcode.h`, 這樣的作法方便擴增及修改指令集, 只需要更改 `opcode.def`, 就可以再自動產生新的 `opcode.h`
## Fibonacci 數列
* 指令集功能
opcode: 指令編號 / has_op1: 第一個輸入 / has_op2: 第二個輸入 / has_result: 輸出
```
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 // 右移 (signed)
print, 3, 1, 0, 0
jlt, 4, 1, 1, 0 // if < jump
jle, 5, 1, 1, 0 // if <= jump
jz, 6, 1, 1, 0 // if ==0 jump
jge, 7, 1, 1, 0 // if >= jump
jgt, 8, 1, 1, 0 // if > jump
jnz, 9, 1, 1, 0 // if !=0 jump
jmp, 10, 1, 0, 0
call, 14, 1, 0, 0
ret, 15, 0, 0, 0
```
### Iterative
**c programming**
```clike=
int fib(int n)
{
if (n == 0) return 0;
int prevPrev = 0;
int prev = 1;
while (n > 0)
{
n--;
result = prev + prevPrev;
prevPrev = prev;
prev = result;
}
return result;
}
```
**full-stack-hello ISA**
```
; if input = 0, print 0
xor #0 $0 #1
jz #1 #13
sub #0 $1 #0
; initialization
or $0 $0 #1
or $0 $1 #2
; iteration
sub #0 $1 #0
add #1 #2 #3
or #2 $0 #1
or #3 $0 #2
jz #0 #11
jgt #0 #5
; print result
print #3
halt
; print 0
print $0
halt
```
`note:` j- 指令 op2 記錄的是指令在 instruction cache 上的第幾個位置, 進而 goto 正確的指令執行。
### Recursive
**c programming**
```clike=
int fib(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
return fib(n - 1) + fib(n - 2);
}
```
**full-stack-hello ISA**
## 作業要求
* 閱讀 [現代處理器設計](http://hackfoldr.org/cpu) 教材和觀看裡頭所有錄影，記錄你的心得和疑惑
* 研究給定的 [full-stack-hello](https://github.com/sysprog21/full-stack-hello)，學習其中 ISA 和模擬器實作，並在 GitHub 上 fork [full-stack-hello](https://github.com/sysprog21/full-stack-hello)
* 對照研讀 [你所不知道的 C 語言：編譯器和最佳化原理篇](https://hackmd.io/s/Hy72937Me) 教材和觀看直播錄影，以得知編譯器運作原理
* 閱讀 [你所不知道的C語言：遞迴呼叫篇](https://hackmd.io/s/rJ8BOjGGl) 和觀看對應講座錄影，用 [full-stack-hello](https://github.com/sysprog21/full-stack-hello) 的指令實作 Fibonacci 數列
* 需要包含 recursive 和 non-recursive 實作，分別置於檔案 `tests/fib-recursive.s` 和 `tests/fib-iterative.s`
* 修改 `vm.c` (和對應的原始程式碼)，允許執行時期由使用者 (和 `Makefile`) 帶入參數，如 `--input`，這數值應該透過暫存器作為上述 Fibonacci 數列程式的 `Fib(N)`
* 研究現有 [full-stack-hello](https://github.com/sysprog21/full-stack-hello) 的自動測試程式，整合上述兩種 Fibonacci 程式實作，並且比較效能 (需要包含 vm 內部的 cycle count)
* 除了 recursive 和 iterative 版本，應該一併考慮以下 Fibonacci 數列的實作方式，並善用 GNU plot 製圖和解讀
* Tail recursion
* Q-Matrix
* Fast doubling
* 過程中可修改 [full-stack-hello](https://github.com/sysprog21/full-stack-hello) 模擬器的程式碼，加入追蹤 / 除錯用途的指令 (instruction)，也應該探討模擬器的運作機制並說明自己修改的方式
* 注意 Fib(63) 之後的數值會超過 2^32^ 可表達的範圍，需要設計有效的數值表示機制來處理 (如用兩個 32-bit 暫存器保存 2^64^ 數值)
* 觀察 [Add label support](https://github.com/jserv/full-stack-hello/pull/30) 的實作方式，試著在[full-stack-hello](https://github.com/sysprog21/full-stack-hello) 給定的組譯器中新增 label 的支援
* 相關的背景知識錄影共有 ==18 小時== (當然不可能看了就懂，請預留思考和提問討論的時間)，務必及早開始
* 將你的觀察、上述要求的解說，以及各式效能改善過程，善用 gnuplot 製圖，紀錄於「[作業區](https://hackmd.io/s/BJR9BTlRW)」
## 參考資料
* [clang-format](https://clang.llvm.org/docs/ClangFormat.html)
Sign in with Wallet
Connect another wallet