# 2016q3 Homework5 (jit-compiler)
contributed by <`LanKuDot`>, <`ktvexe`>

## 組員
- [ ] 李昆憶
- [ ] 劉亮谷

## 作業要求
[A09: jit-compiler](https://hackmd.io/s/SJ7AZJv1e)

* 學習設計 JIT 編譯器
* 運用計算機組織的背景知識，進行深入效能評估和提出改善方案
* 延展程式語言，提供 concurrency 能力

## 基礎知識
### AOT (Ahead-Of-Time) compilation
* 在執行程式之前，執行一連串的指令將 High-level programming language 轉換成可以在該機器上執行的機械碼，並產生可執行檔。
* 而執行檔可以不用重新編譯就在同一個機器上重複執行
* 相比 JIT compiler 可以對程式碼作諸多優化。

### JIT (Just-In-Time) compilation
* 與執行前編譯好執行檔不一樣，JIT 是~~一邊執行程式一邊編譯~~**在真正執行特定功能之際，才編譯程式碼**。可以直接將程式碼轉成機械碼或是其他形式執行。常常使用在 dynamic programming language。
* 只有在執行程式時，才會編譯。每一次執行，就需要重新編譯。

> 這邊我不是很懂，需要再閱讀些資料，研究其實作方式與相關應用[name=劉亮谷][color=blue]
> [我參考這個](http://scholarexchange.furman.edu/cgi/viewcontent.cgi?article=1879&context=furmanengaged)[name=LanKuDot]
>> "in time" 的意義要先搞懂，引述 dictionary.com 的解說:
>>> Before a time limit expires, early enough, as in His speech begins at eight, so we've arrived in time. It is often put as in time for, as in Please come in time for dinner.
>> 所以 just-in-time compiler 的意思是，在真正執行特定功能之際或期限超過前，才去編譯程式碼 [name=jserv]

### [BrainF\*ck](http://www.slideshare.net/jserv/vm-construct)
* 圖靈實現語言(Turing complete)：可以用來模擬單磁帶圖靈機的程式語言，而且只要懂一種圖靈實驗語言，就可以理解其他同一類型的語言。「磁帶」的每一個符號都有對應的動作，透過有限的 table 查表運作。而 brainf*ck 只有八個指令：
`>`：移動 data pointer 到下一個 cell
`<`：移動 data pointer 到上一個 cell
`+`：加一 data pointer 指向的 byte
`-`：減一 data pointer 指向的 byte
`.`：輸出 data pointer 所指向的 byte
`,`：輸入 1 byte 的資料到 data pointer 所指向的 cell
`[`：如果 data pointer 所指向的資料為 0，就跳到 `]`之後繼續執行，否則往下執行
`]`：跳回對應的`[`繼續執行
>上課中問到BrainF*ck可否實現if-else，不知道如果回答Turing machine的定義有沒有切重要害[name=劉亮谷][color=blue]

* 需要一個磁帶的空間，另一個是存資料的空間 (cell)，例如給變數的空間。
>instruction pointer and data pointer[name=李昆憶][color=red]

* [P11]：遇到迴圈起點時，先找尋對應的迴圈終點。可以偵測巢狀迴圈：
* 因為是先遇到`[` ，所以將 `b`初始化為 1，如果遇到 `]`就減一，遇到`[`就加一。當`b`為 0 時，就代表找到成對的中括號。
* 找到之後，先將對應的`]`，改成`0`，為了就是讓 data pointer 偵測迴圈終點。recursive call，進入迴圈執行。等迴圈結束後，再將`0`改回`]`。

    case '[': // 每次進到 switch 是 *c++ 所以此時 c 是指向 [ 的下一個
        for (b = 1, d = c; b && *c; c++)    // d 紀錄迴圈起點
            b += *c == '[';
            b -= *c == ']';
        if (!b) {
            c[-1] = 0;    // ] became \0
            while (a[p]) interpert(d);
            c[-1] = ']';    // Resume ]
            break;
        }

>`==`的 precedence 比`+=`、`-=`高。[name=李昆憶][color=red]

* [P16]：**copy**：`x=y`，`$y[-$x+$y]`。假設 x 存在 cell 0，y 存在 cell 1，data pointer 目前指向 x：那就會是 `>[-<+>]`：
* 將 y 減 1，再將 x 加 1，直到 y 為 0。
* `$y[-$t+$y]$t[-$x+$y+$t]`，另一個方法是將 y 的值存到 t 中，然後減掉 t，同時將 x y 加回來。假設 t 在 cell 2，data pointer 目前指向 x：`>[->+<]>[-<<+>+>]`
* **需要注意迴圈結束時，data pointer 指向哪個 cell**

* [P17]：**if**：`if (x) { <foobar> };`

Move x to t;
if ( t != 0 ) recharge x; foobar;

* [P18]：**clean**，`[-]`。用一個 while loop 把那個 cell 減到 0。
* [P19]：**cat**，`+[,.]`。先將目前的 cell 加一，確保他非 0，然後用一個 while loop，一直讀輸入，再輸出，直到遇到`\0`。
* [P20]：**if-endif**

$f +          // 確保可以作一次跳出迴圈
$A [          // if ($A) 這裡有可能就是移到要判定的 data cell
    <foo bar>
    $f [-]    // Clear $f -> end if
]

* [P21]：**if-else-endif**

$f +            // 確保可以作一次跳出迴圈
$A [            // if ($A)
    <foo bar>
    $f [-]      // clear $f
] $f [          // else，如果 if 成立 $f 會被清空，避免下個迴圈被執行
    <foo2 bar2>
    $f [-]
]

* [P22]：**Multiply**，就是連續加法，用一個 cell 存要加幾次，在重複加另一個 cell
* [P23]：**Divide**，連續減法，用一個 cell 存被除數，一個 cell 存商，每次 loop 減被除數除數

// a / b = c;
cell 0 store the value of a.
while ( a > 0 ) {
    ++c;
    a -= b;
}

* [P26]：bubble sort

>>>>>,.[>>>,.]        // 從第六個 cell 開始，讀取輸入，每隔兩個存一個值
<<<                   // 當輸入結束 （讀到0時），移回最後一個資料
[<<<                  // 迴圈A：移到上一個資料
[>>>                  // 迴圈B：移到下一個資料
    [-<<<-<+>[>]>>]   // 迴圈C1：每次將這個資料與上一個資料減一，每減一次就在上個資料的前一個 cell 加一，然後移回上一個資料。如果上一個資料還沒歸零的話，就會重複移回這個資料，持續上述動作。所以說，較小的值會被存到上一個資料的前面的 cell。如果上一個比這個大，data pointer 最終會指向這個資料（此時這個為0）。否則，會指向這個資料的前面一個 cell（此時上一個為0）
    <<<[<]>>          // 找到上一個資料的位置
    [>>>+<<<-]<       // 迴圈C2：如果上一個值比較大，就會先把剩下的值搬到"這個"去，然後指回暫時存起來的最小值
    [>+>>>+<<<<-]     // 迴圈C3：然後把暫存的最小值都搬到兩個資料中。搬移完成後，data pointer 會在這個暫存 cell 中。這樣比較大的值，就會跑到後面去了。
<<]                   // 迴圈B：往上一個值移動，這樣比較小的值就會一直往前，直到遇到0
>>>[.[-]]             // 往後移動到最近的資料，印出這個值後，把他 clear 掉（所以最小值會先被印出來）
>>>[>>>]<<<]          // 迴圈A：往下一個資料移動，直到遇到0後，將指標轉回最後一個，直到所有資料都被印出來（all 0）

* 優化：對於重複執行的動作，可以進行優化
* 連續加法，或連續減法，連續移動：都可以被一條指令給取代，而非一個一個重複執行

## 作業

### 環境建置
原本想直接跑 `make bench-jit-x64` 但出現缺少檔案的訊息 (我環境是 64 bit OS)

$ make bench-jit-x64 
lua dynasm/dynasm.lua -o jit-x64.h jit-x64.dasc
make: lua: Command not found

* 安裝 `lua`：

$ sudo apt-get install lua<ver>` (我是用5.2版)

再跑 `make` 會出現 `bit` module not found 的訊息

* 安裝 lua development package：

$ sudo apt-get install liblua<ver>-dev`

* 到[官網](http://bitop.luajit.org/index.html)下載 `bitop` module 的 source code

* 解壓縮後執行 `make`，可能會出現 include 的 header file 不在的訊息。檢查它所需的 header file 是否在 `/usr/include/lua<ver>`，通常安裝 library 的 header file 會在 `/usr/include` 或 `/usr/local/include`。找到後，修改 Makefile 中的 include 路徑。編完會產生一個 .so 檔。

$ make
gcc -fPIC -O2 -fomit-frame-pointer -Wall  -I/usr/include  -c -o bit.o bit.c
bit.c:32:17: fatal error: lua.h: 沒有此一檔案或目錄

* 執行 `sudo make install`，可能會出現 `install: 無法建立普通檔案` 這樣的訊息，可以直接建立對應的資料夾解決。
* 也可以先確認 `lua` 的預設 module 路徑，然後修改 `make` 中對應的安裝路徑

        [luaPackagePath.lua]
        print(package.path)
        print(package.cpath)
    
        $ lua luaPackagePath.lua
        /usr/local/share/lua/5.2/?.lua;/usr/local/share/lua/5.2/?/init.lua;/usr/local/lib/lua/5.2/?.lua;/usr/local/lib/lua/5.2/?/init.lua;/usr/share/lua/5.2/?.lua;/usr/share/lua/5.2/?/init.lua;./?.lua
        /usr/local/lib/lua/5.2/?.so;/usr/lib/x86_64-linux-gnu/lua/5.2/?.so;/usr/lib/lua/5.2/?.so;/usr/local/lib/lua/5.2/loadall.so;./?.so

### jit-x64
* source code：`*.dasc`
* preprocessor：`dynasm.lua`，經過處理的 `*.dasc` 會輸出為 `*.h`
* 包裝：將輸出的 `*.h` 與 `dynasm-driver.c` 一起編譯成 `jit-x64`
`dynasm-driver.c` 包含 JIT 初始化，配置記憶體空間，及釋放記憶體空間

[Intel x86_64 instruction set ](https://msdn.microsoft.com/en-us/library/windows/hardware/ff553442%28v=vs.85%29.aspx)

### Benchmark-Baseline
專案中預設執行的 benchmark 有三：`awib.b`、`mandelbort.b`、`hanoi.b`，執行的 compiler 為 `jit-x64`

### Contraction
將連續的 pointer 移動事件及連續對同一個 byte 的計算，整理起來計算有多少次，直接使用`add`及`sub`。
> 之前修課有寫過這個作業，jserv 老師提過增加新功能要以模組化的方式設計，提高可攜性及修改彈性[name=LanKuDot][color=red]

int contraction(char **tape)
{
    unsigned int count = 0;
    char ref_ch = **tape;    // Use first char as the reference char
    
    do {
        ++count;    // 'count' will be at least 1.
    } while(*(++(*tape)) == ref_ch);
    
    --(*tape);
    return count;
}

### Clear, Multiply, Divide, Move, and Copy
因為這些都牽涉到迴圈的運作，所以可以一併分析。觀察 bf 的原始碼，歸類一些特性 (`$x` 為 move to cell `x`)：

#### Clear
* `[-]`：清空目前的 data cell
* `[-{move y cell}]`：包含目前的 cell，每隔 y cells 減 1，直到遇到值為 0 的 cell

#### Move or Copy
* `[- $1- $2]`：$1 = $1 - $2, than $2 = 0 (cell data 沒有負數，推測 $1 > $2)
* `[- $1+ $2]`：$1 = $1 + $2, than $2 = 0
* `[- $1- $2+ $victim]`：要注意 $1, $2, $victim 的移動量加總為 0
* $1 = $1 - $victim
* $2 = $2 + $victim
* than $victim = 0
* 最後一個一定是 victim，因為這樣回到迴圈起頭時才能跳出迴圈。

#### Multiply
* 可以將 Move 或 copy 視為 1 倍的 multiply
* 注意：裡面的移動量一樣總合要為 0
* `[- $1++++++ $2]`：$1 = $1 + 6 * $2, than $2 = 0
* `[- $1------ $2]`：$1 = $1 - 6 * $2, than $2 = 0
* `[- $1+++ $2---- $victim]`：
* $1 = $1 + 3 * $victim
* $2 = $2 - 4 * $victim
* than $victim = 0

### Detect single loop
為了實現上面 section 的想法，必須處理 single loop：

* 第一版

int isSingleLoop(char *tape)
{
    while (*++tape != ']') {    // Usually true
        if (*tape == '[')       // Usually false
            return 0;
    }
    return 1;
}

* 第二版：branch predictor friendly，並紀錄 loop end

int isSingleLoop(char *tape, char **loop_end)
{
    while (*++tape != ']' && *tape != '[')    // Usually true
        ;

    if (*tape == ']') {
        *loop_end = tape;
        return 1;
    } else {
        *loop_end = NULL;
        return 0;
    }
}

紀錄 `loop_end` 可以在做完 single loop 簡化操作後，直接讓 `p` 指向 `loop_end`。
### Handle clear, copy, move, and multiply
這些都有幾個共通點：

* `[(減)+ (移動 (加)+/(減)+)+ 移動]`：`()+` 為出現1個或多個的意思
* loop 內的總移動量為 0

設計一個 structure 將分析到的資訊包起來：

typedef struct __CELL_ACTIONS_ {                                       
    int valid_length;
    int victim_divisor;
    int cell_move[MAX_ACTION]; 
    int victim_multiplier[MAX_ACTION];
} Cell_Actions;

* `vaild_length`：紀錄 `cell_move` 與 `victim_multiplier` 的有效長度，或是其他類型的 single loop
* -1：不是可以簡化的 single loop
* 總移動量不為 0
* 裡面有 `.` `,`
* 0：Clear loop
* 正值：可簡化的 single loop
* `victim_divisor`：victim 的除數。因為可能會出現 `[---->+<]` 這種情況，如果 victim 原為 12，則每次減 4 的話，下一個 cell 只會被加 3 (=12/4) 次。
* `cell_move`：紀錄到下個 cell 的距離 (不是相對於 victim 的距離)
* `victim_multiplier`：針對這個 cell 的操作，victim 要乘上的值

呼叫 `handle_single_loop()` 會得到分析結果，接下來是使用流程：

1. 判定是可以簡化的 single loop
2. 將目前 cell (也就是 victim) 的值除以 `victim_divisor`
3. 移動到下個 cell
4. 對要操作的 cell 的值設為 `$cur_cell` + `victim_multiplier` * `$victim`
5. 回到 3.，直到所有有效 cell 都被操作過
6. 將目前 tape 的 pointer 指向 `loop_end`
7. data pointer 指向 victim

### 問題
- [ ] 我該怎麼修改 `jit-x64` 讓我可以得到 data cell 的值並存到變數中?
* 嘗試下列 code，但總是會 segmenation fault

    uint32_t cur_cell_value = 0;
    
    | push  r9
    | mov   r9, byte [PTR]
    | movzx [cur_cell_value], r9
    | pop   r9

### Multiply and Copy
* 將 copy 視為 multiply 1 的操作
* 預期格式為：開頭為 `-` → 連續移動到第一個位址 `<`或`>`→ `+` → 連續移動到第二個位址 `<`或`>` → `＋` → 移動回原本的位址。
* `dst_1`儲存第一個位址要被歸零的位址差距：`<`為 -1，`>`為 +1
* `dst_2`儲存第二個位址要被歸零的位址差距
* `mul_1`、`mul_2`：儲存第一二個乘數的值
* 最後將原本位址的值歸零

| push  r8
| push  r9

| movzx r8, byte [PTR]
| imul  r8, mul_1
| mov   r9, PTR
| add   r9, dst_1
| add   byte [r9], r8   // 出現 mixed operand size in `add xb,rq'
// byte [r9] 為 8 bits, 而 r8 為 64 bit，使用 r8b 解決問題
| movzx r8, byte [PTR]
| imul  r8, mul_2
| mov   r9, PTR
| add   r9, dst_2
| add   byte [r9], r8   // 這一行也是

| mov   byte [PTR], 0

| pop   r9
| pop   r8

### Parser

* 跟昆憶哥討論過後，他給我提示說，讀取 brainfunck 原始碼是在 `util.h` 的 `read_file`，不過他就是整坨讀近來，沒有處理換行或是非有效字元等等問題。

* 所以開始處理在讀檔時所遇到的非有效 brainfuck 程式碼，不過我思考許久，我想不到確定可以比 `jit-x64.dasc` 中的 switch case 效能還要快的 parser 方式，因為原先 `util.h` 中是使用 `fread` ，只進行一次讀取，不過如果要在讀檔階段做 parse 那就必須一個字元一個字元判斷，我認為這會比起原先的讀檔還費時，所以我最後的作法有點像是把`jit-x64.dasc` 中的 switch case 搬到讀檔時處理，感覺不是很好的方式，所以我預測這樣的改寫效能可能不會提升。

char *read_file(const char * const filename)
{

......

size_t i=0;
while(fread(code+i,1,1,fp)){
	switch(*(code+i)){
        case '>':
        case '<':
        case '+':
        case '-':
        case '.':
        case ',':
        case '[':
        case ']':
            i++;
            break;
    }
}   
char *code_dup = malloc(sizeof(char) * i); 
memcpy(code_dup,code,i);
free(code);

但是實驗結果非常奇怪，其實我認為這組實驗數據應該是有問題的。
* 首先是我一開始做完parse後並未回傳正確大小之空間，這會造成的結果不只是在進行 JIT compilation 時，原先較大的空間中的 garbage value 會造成錯誤(雖然這是範例剛好沒有遇到)，而且還會變成沒有替 compilation 省下處理的時間(不過 prediction 有可能會比較順利，因為多出來的空間中大部份可能是 garbage value )。
* 再者，實驗結果中 `awib.b` 的效能提升相當有限，這也是蠻奇怪的，如果說事前的 parser 真的能夠對效能提升有所幫助，那其提升的比例應該會與其 code size 的改變有關，見下表比較 code size 的改變再對照效能分析，發現 code size 減少最多的 `awib.b` 效能提升的比例卻不如 `hanoi.b` 。

| |Origin Size|Parsed Size|
|-------------|-----------|-----------|
|awib.b |44463 |31514 |
|mandelbrot.b |11669 |11451 |
|hanoi.b |54593 |53884 |

* 最後我認為上面那段 `read_file` 程式的 parse 應該與 `jit-x64.dasc` 中的 switch case 合併，這樣效能會比現在這個方式還要更佳。

> 但因為我處理優化都是透過 function call，所以一開始就傳入處理好的字串會比較簡單。讓優化函式可以專注在目標 pattern 的判斷，而不用再處理非有效字元。[name=LanKuDot][color=red]

`jit-x64.dasc`：

 tape_head = read_file(argv[1]);
    for (char *p = tape_head; *p; p++) {
        switch (*p) {
        case '>':
            repeat = contraction(&p);
            |  add  PTR, repeat
            break;
        case '<':
            repeat = contraction(&p);
            |  sub  PTR, repeat
            break;
        case '+':
            repeat = contraction(&p);
            |  add  byte [PTR], repeat
            break;
        case '-':
            repeat = contraction(&p);
            |  sub  byte [PTR], repeat
            break;
        case '.':
            |  movzx edi, byte [PTR]
            |  callp putchar
            break;
        case ',':
            |  callp getchar
            |  mov   byte [PTR], al
.......

## 效能
### Baseline

progs/awib.b             GOOD	177.3ms
progs/mandelbrot.b       GOOD	5342.7ms
progs/hanoi.b            GOOD	14622.7ms

### Contraction

progs/awib.b             GOOD	75.9ms
progs/mandelbrot.b       GOOD	1960.0ms
progs/hanoi.b            GOOD	8193.4ms

### Clear loop
可以發現 `hanoi.b` 有很多 clear loop

progs/awib.b             GOOD	78.8ms
progs/mandelbrot.b       GOOD	1881.9ms
progs/hanoi.b            GOOD	207.6ms

### Parser withoout clear loop
> 注意這邊的測試是使用不同的電腦

Only Contraction：

Executing Brainf*ck benchmark suite. Be patient.

progs/awib.b             GOOD	62.0ms
progs/mandelbrot.b       GOOD	1390.6ms
progs/hanoi.b            GOOD	5036.3ms

Parse but don't duplicate memory：

Executing Brainf*ck benchmark suite. Be patient.

progs/awib.b             GOOD	65.8ms
progs/mandelbrot.b       GOOD	1439.4ms
progs/hanoi.b            GOOD	4614.0ms

Duplicate correct memory：

Executing Brainf*ck benchmark suite. Be patient.

progs/awib.b             GOOD	58.3ms
progs/mandelbrot.b       GOOD	1453.8ms
progs/hanoi.b            GOOD	4683.7ms

## 其他資料
* 輸出 execution map：gprof
* [優化 BF Compiler](http://www.wilfred.me.uk/blog/2015/08/29/an-optimising-bf-compiler/)

## Reference
* [What does a just-in-time (JIT) compiler do?](http://stackoverflow.com/questions/95635/what-does-a-just-in-time-jit-compiler-do)
* [Just-in-time compilation](https://en.wikipedia.org/wiki/Just-in-time_compilation)

###### tags: `sysprog21` `sysprog2016`