# C07: simulator
###### tags: `sysprog2017`
:::info
主講人: [jserv](http://wiki.csie.ncku.edu.tw/User/jserv) / 課程討論區: [2017 年系統軟體課程](https://www.facebook.com/groups/system.software2017/)
:mega: 返回「[進階電腦系統理論與實作](http://wiki.csie.ncku.edu.tw/sysprog/schedule)」課程進度表
:::

## 預期目標
* 搭配 [現代處理器設計](http://hackfoldr.org/cpu)，實際練習系統軟體開發
* 思考函式呼叫和掌握遞迴程式開發技巧
* 擴充給定的指令集 (ISA) 模擬器

## [full-stack-hello](https://github.com/sysprog21/full-stack-hello)
* [full-stack-hello](https://github.com/sysprog21/full-stack-hello) 是成功大學發展的小型指令集模擬器，附帶組譯器和編譯器等系統工具
* 編譯和測試

$ git clone https://github.com/sysprog21/full-stack-hello.git
$ cd full-stack-hello
$ make
$ make check

預期得到以下輸出:

42
tests/halt.s pass

Hello World
tests/hello.s pass

42
50
150
tests/test.s pass

$ make test
python tests/run_tests.py
..
---------------------------------------------------------
Ran 4 tests in 0.002s

OK

* 組譯器使用

$ ./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

* 用給定的 `tests/hello.s` 檔案做示範
1. 組譯和執行

    $ ./as_exec tests/hello.s

2. 組譯並輸出 ELF 格式目的檔 `tests/hello.o`

    $ ./as_exec -w tests/hello.s

3. 組譯並輸出 ELF 到給定的路徑

    $ ./as_exec -o tests/temp.o -w tests/hello.s

4. 載入之前組譯得到的 ELF 檔案並執行

    $ ./as_exec -x tests/hello.o

* 輸出的 ELF 檔案可用 [objdump](https://sourceware.org/binutils/docs/binutils/objdump.html) 工具分析和觀察:

$ objdump -x tests/hello.o

* 注意 `vm.c` 用到 GCC [computed goto](https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html) 的機制

#define OP(name) OP_##name

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

#define END_OPCODES

## [clang-format](https://clang.llvm.org/docs/ClangFormat.html)
* LLVM 專案旗下的 [clang-format](https://clang.llvm.org/docs/ClangFormat.html)
* 安裝方式:

$ sudo apt-get install clang-format

* 延伸閱讀: [使用Clang-format來幫助你美化你的程式碼](https://forum.angular.tw/t/topic/235)

## 作業要求
* 閱讀 [現代處理器設計](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(46) 之後的數值會超過 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)」

## 截止日期
* Nov 9, 2017 (含) 之前
* 越早在 GitHub 上有動態、越早接受 code review，評分越高