# 2016q3 Homework5 (jit-compiler)
contributed by `<jeff60907>`, `<chenan00>`

## 預期目標
[作業說明A09: jit-compiler](https://hackmd.io/s/SJ7AZJv1e)
* 學習設計 JIT 編譯器
* 運用計算機組織的背景知識，進行深入效能評估和提出改善方案
* 對 Brainfuck 程式語言進行擴充，使其能夠支援 concurrency / parallelism。需要有程式語言的規格描述並且驗證。
* [Bukkake](https://bitbucket.org/wjmelements/bukkake): A parallel brainfuck JIT in C
* [Brainfuck Process Extensions](http://www.kjkoster.org/BFPX/Brainfuck_Process_Extensions.html)
* [Parallel Brainfuck](https://github.com/cmdli/parallel-brainfuck)
* [Concurrent Brainfuck](http://www.schabi.de/cbf/)

### 了解Brainfuck 程式語言
Brainfuck 是符合 Turing complete 的程式語言，由8個運算子組成為 Amiga 機器編寫的編譯器
　`>`：`++ptr;` 指標加一
　`<`：`--ptr;` 指標減一
　`+`：`++*ptr;` 指標指向的位元組的值加一
　`-`：`--*ptr;` 指標指向的位元組的值減一
　`.`：`putchar(*ptr);` 輸出指標指向的單元內容（ASCII碼）
　`,`：`*ptr =getchar();` 輸入內容到指標指向的單元（ASCII碼）
　`[`：`while (*ptr) {` 如果指標指向的單元值為零，向後跳躍到對應的`]`指令的次一指令處
　`]`：`}` 如果指標指向的單元值不為零，向前跳躍到對應的`[`指令的次一指令處
>>「跳轉」為對岸用語，繁體中文翻譯是「跳躍」[color=red][name=課程助教]
>> 收到已更改[name=陳致佑]

* 投影片p.11， `case'[':` 那段不太了解，參考[ <`LanKuDot`>, <`ktvexe`>共筆](https://hackmd.io/AwDgrMBsKQxgtCA7LY8Asp2NkgRvAIYAmAzMHugGaGlJjpA=?view)
> 遇到迴圈起點時，先找尋對應的迴圈終點。可以偵測巢狀迴圈：
遇到`[` ，將 `b`初始化為 1，如果遇到`]`就減一，遇到`[`就加一。當`b`為 0 時，就代表找到最外層對應的括號，而且`==`的 優先權 比`+=`、`-=`高

* 投影片p.12， 當P>100 顯示 range error 是代表指標不能連續 +100 次以上嗎?是設計上規定指標有一定範圍內使用嗎?

* 投影片p.13，`if` 先把 t = x，在進入 `[ ]` 內，當 t != 0 把 x = t ，在進行 foobar，不太懂為什麼要先把 t = x 到後來又補回來?

* 投影片p.22，乘法6*7，透過連續加法，先 cell[0] 加到6，進入while cell[1]+7，cell[0]-1，直到 cell[0]=0，也做了6次 +7

* 投影片p.23，除法12/4，透過連續減法，最後輸出存商的資料

* 投影片p.26-31，bubble sort 作法看完同學的共筆還是有點困惑，再多想和討論看看
* 後面介紹優化的方式，有些重複的指令可以做更動不用一次一次執行

### 釐清基本知識 JIT VS AOT
* JIT (Just-In-Time) compilation [wiki參考](https://en.wikipedia.org/wiki/Just-in-time_compilation)
* 稱作即時編譯，在執行的同時也進行編譯，通常會轉換成機械碼或其他形式，JIT特別適合在動態編譯中使用
* jit 包含了傳統的兩種方法 AOT以及直譯，以及結合兩者的優劣
* AOT (Ahead-Of-Time) compilation [wiki參考](https://en.wikipedia.org/wiki/Ahead-of-time_compilation)
* 在執行程式前，將高階語言轉換成可執行的機械碼檔案，因為在執行程式前操作可做更多的最佳化
* 主要改進的是執行中間碼時，必須要先轉換成機械碼所造成的overhead

* andriod 過去有使用JIT後來改成AOT，最新版本7.0又加入了JIT技術，不知道過去跟現今差別在哪

### 閱讀推薦資料共筆
* [Virtual Machine Constructions for Dummies](http://www.slideshare.net/jserv/vm-construct)
* [How A Compiler Works](http://www.slideshare.net/jserv/how-a-compiler-works-gnu-toolchain)
* [廖健富共筆](https://hackpad.com/2015q3-Homework-4B-5I46HyqOCGJ#:h=Jit-construct)
* [林郁寧共筆](https://embedded2015.hackpad.com/-Homework4-B-h5FfVE6RTeu)

### 閱讀資料後 DynASM Interpreter、Compiler、JIT比較

-待整理

### 實作開發
Development packages for Ubuntu Linux Ubuntu 16.04 LTS:

sudo apt-get update
sudo apt-get install build-essential
sudo apt-get install gcc-5-multilib
sudo apt-get install lua5.2 lua-bitop
sudo apt-get install gcc-arm-linux-gnueabihf
sudo apt-get install qemu-user

修正前的測試`make bench-jit-x64 `

Executing Brainf*ck benchmark suite. Be patient.

progs/awib.b            GOOD	120.0ms
progs/mandelbrot.b      GOOD	2953.3ms
progs/hanoi.b           GOOD	7393.8ms


#### 在推薦資料有許多優化的方式，參考如何實作
* Contraction
重複的+ - < > ，計算完一次處理
* clear loop
遇到 [-] 直接設定為0
* copy loops
原本是要在回圈內執行，直接將當前指標加給要存放的指標
* multiplication loops
在迴圈內連續 + (乘法)，直接將當前指標乘完後加給要存放的指標
* operation offsets
多次< > 位移量的問題，可以計算好直接給一個offset
* scan loops
可使用 memchr() 進行最佳化

嘗試修改 `jit-x64.dasc` 檔 [參考team20](https://hackmd.io/s/HJnMwtdJx)

* **單獨 Contraction**
建立一個可以計算function + - < > 是否有連續出現，再修改case 進行動作
先測試 + - 可以改善多少

int continuous_count(char *p)
{
    char *ptr = p;
    int count = 0;
    while (*ptr == *p) {
        count++;
        ptr++;
    }
    return count;
}
case '+':
    count = continuous_count(p);
    p += count -1;
    |  add  byte [PTR], count
    break;
case '-':
    count = continuous_count(p);
    p += count -1;
    |  sub  byte [PTR], count
    break;

progs/awib.b            GOOD	56.9ms
progs/mandelbrot.b      GOOD	2933.2ms
progs/hanoi.b           GOOD	3629.1ms

> awib.b hanoi.b 內有大量的+ -，但是 mandelbrot.b內就很少連續+ -，所以效能就沒什麼提升

保留+ - 繼續修改case < > 測試效能

progs/awib.b            GOOD	76.7ms
progs/mandelbrot.b      GOOD	1128.3ms
progs/hanoi.b           GOOD	3689.3ms

> mandelbrot.b 大幅度改善效能，但是卻造成 awib.b 效能增加，很納悶的是 hanoi內也有很多< >，照理說也是應該改善很多，卻不是預期的效果

* **單獨clear loop**
在 `case '['` 先進行判別 是不是[-]，如果是就直接設定為0，本來是想說能不能指定完break，發現會造成錯誤...

case '[':
    if (top == limit) err("Nesting too deep.");
    if(*(p+1)== '-' && *(p+2) == ']') {
    |  mov   byte [PTR], 0
    //break;
    }

progs/awib.b            GOOD	112.7ms
progs/mandelbrot.b      GOOD	2933.7ms
progs/hanoi.b           GOOD	3023.9ms

>使用 clear loop方法 將[-]簡化成設定為0，不用等到while = 0，效能改善最多的是haoi.b，看了裡面的code，使用大量的[-]，所以改善效能才這麼高

* **Contraction + clear loop**
測試兩個優化結合再一起會不會效能提升

progs/awib.b            GOOD	62.7ms
progs/mandelbrot.b      GOOD	1097.1ms
progs/hanoi.b           GOOD	189.3ms

> 神奇的事情發生了！原本hanoi 優化各自獨立都是時間減少2倍，但是結合後卻減少了將近40倍！！
> 原先認為 優化Contraction < > 會改善很多卻沒有，但是結合了clear loop卻超乎想像

上課內容 stack(遞回) heap(malloc) brk "sbrk"

SLAB

linux SLUB

use after free bug

chunk

data in-place

linux kernel 跟 user memory共同空間

Thread Local Storage wiki 熟讀TLS

scalloc 論文 地表最強