2016q3 Homework5 (jit-compiler)
===
contributed by <`judy66jo`>, <`JonSyuGithub`>

## 作業目標
* 改善內建 benchmark suite 效能的機制，並且要能夠充分解釋行為，需要一併透過 gnuplot 自動產生效能分析圖表
* 對 Brainfuck 程式語言進行擴充，使其能夠支援 concurrency / parallelism

## Brainfuck
只有八個運算字元，可做數學運算、迴圈，以下為分別對應的 C code

* \> |`++ptr`
* < |`--ptr`
* \+ |`++*ptr`
* \- |`--*ptr`
* . |`putchar(*ptr)`
* , |`*ptr = getchar()`
* [ |`while(*ptr) {`
* ] |`}`

## DynASM
A Dynamic Assembler for code generation engines.

## Interpreter、Compiler、JIT比較
* Interpreter
* 直接執行.b程式
* 速度最慢，因為要不停地來回
* 時間複雜度O(n)

* Compiler
* 將高階語言編譯成 assembly code
* 執行時間最快，但因比 JIT 多出 I/O 時間，故編譯時間較慢， Compiler 把編譯好的檔案先存起來，再執行
* 有錯誤無法馬上修改
* 時間複雜度O(1)

* JIT
* 利用 DynASM 動態產生 machine code
* 把透過 Compiler 生成的機器碼直接放到某塊 JIT 執行時期的記憶體 mmap 直接執行
* 不會把編譯好的檔案存起來，每次均需重新編譯，若執行許多次也是一種負擔
* 有錯誤可以馬上修改
* 時間複雜度O(1)

#### JIT 的整體流程
* 進入 main function，逐行讀入 input file 並將對應的 machine code 塞入 `dasm_State` 中
* 呼叫 `jitcode`，透過`dasm_link` 與 `dasm_encode` 將 `dasm_State` 轉換成可執行的機器碼 block，並回傳
* 呼叫從 `jitcode` 回傳的函式指標，也就是前面讀入的 brainf*ck 程式(已經轉為當前架構的機器碼)

## Optimization
記錄未優化前時間

$ make bench-jit-x86

Executing Brainf*ck benchmark suite. Be patient.

progs/awib.b            GOOD	98.3ms
progs/mandelbrot.b      GOOD	2948.4ms
progs/hanoi.b           GOOD	6291.6ms

$ make bench-jit-x64

Executing Brainf*ck benchmark suite. Be patient.

progs/awib.b            GOOD	64.8ms
progs/mandelbrot.b      GOOD	2969.5ms
progs/hanoi.b           GOOD	6236.9ms

### 改寫jit-x64
* Contraction
將連續的 inc(+ , >) 或 dec(- , <) 合併成 add 或 sub

	progs/awib.b            GOOD	46.7ms
	progs/mandelbrot.b      GOOD	1032.8ms
	progs/hanoi.b           GOOD	3387.9ms

* Clear loops & Copy loops & Multiplication loops
* Scan loops

## References
[A09: jit-compiler](https://hackmd.io/s/SJ7AZJv1e)
https://hackpad.com/2015q3-Homework-4B-5I46HyqOCGJ#:h=Jit-construct
https://embedded2015.hackpad.com/-Homework4-B-h5FfVE6RTeu
https://mimihalo.hackpad.com/HW4--2r8xNuU8gdf

###### tags: `sysprog21` `Team23`