# Homework5 (jit-compiler)

## 沈思上一個作業有什麼沒做好

> 1. 目標設立太大，不應該直接挑戰太難的目標，應該要 divide and conquer[name=Yen-Kuan Wu]
> 2. 閱讀不夠，應該要大略掃過閱讀資料，雖然不是每個都一定用得到，但腦海中還是會有點記憶，看不懂的就先記下來就好，然後互相幫助 :) [name=Yen-Kuan Wu]
> 3. 應該要多多參考別人的筆記跟問問題，不是說一個人做不到，而是參考後自己在實作上會有比較觸類旁通，而且這是個注重開發時間的年代，但切記看完別人的筆記後要確認自己有沒有懂![name=Yen-Kuan Wu]
> 4. 每個人應該要給自己一個充裕的時間表，預估時間的為自己認為的兩倍，盡量能 keep 一個進度[name=Yen-Kuan Wu][color=#fcb888]
> 我自己的時間分配是思考/閱讀跟coding,每個作業的順序也是如此,先思考作業的目標(最對的事情),然後拆分工作(WBS/把事情做對),接著是閱讀相關文件,參考資料跟原始碼,最後再動手coding,雖然不見能夠完成作業XD,但在時間分配上就會比較有規律,心情也不會那麼焦慮了,提供給你參考~ [name=kobe yu]

## 作業要求
* 作在 github 上 fork [jit-construct](https://github.com/sysprog21/jit-construct)，注意不要跟 2015 年的作業搞錯了
* 依據上方提示，提出改善內建 benchmark suite 效能的機制，並且要能夠充分解釋行為，需要一併透過 gnuplot 自動產生效能分析圖表
* 參考以下實做，對 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/)

## 參考資料
* [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)
* [作業共筆彙整](https://embedded2015.hackpad.com/2015q3-Homework-4-8AvSmXDYC38)

* [A Compiler, Assembler, Linker & Loader](http://www.tenouk.com/Bufferoverflowc/Bufferoverflow1c.html)
* [ ELF binaries](https://lwn.net/Articles/631631/)

* [ Linkers & Loaders ](http://www.becbapatla.ac.in/cse/naveenv/docs/LL1.pdf)
---

# 進度表

## 黃呂源

* [ ] 資料閱讀
* [ ] 參考資料的部分方法修改code
* [ ] 釐清三種compiler流程

## 吳彥寬
* code 觀察 + DynASM + 參考資料 (10/24 中午完成)
> 還有好多事要做R，搞不好會 delay，沒想到 DynASM 有點難R(汗[name=Yen-Kuan Wu][color=#fcb888]

# Interpreter vs Compiler vs JIT

這次`brainfuck`實作有包含這兩種，首先我們先略窺這兩種的差異

>節錄 [<張家榮共筆>](https://embedded2015.hackpad.com/HW4B-oKTqwC9newO)
>[color=#fcb888]
>[name=Yen-Kuan]
>協助補充compiler/JIT在產生組合語言後最後執行的方式差異.[name=kobe yu]
>>看了部份文件大部分都是提到說JIT是一個等到run time的時候才作compliation 的compiler
>>目前有幾個問題
>>1. interpreter 是否是執行interpreter 然後在程式中再去作code to machine code的部分? loading time有點疑惑?
>>2. Jit 應該是再執行時期再去做compliation的動作?
>>>> i. 是否是先在interpreter下，去做一個jit的動作?
>>>> ii. profiler 不知道是什麼
>>>> iii. jit的code scope範圍以及deadline?

## Interpreter

其實就是寫一個程式將 brainf*ck 轉換成 C 語言，之後再用 C 對應的 assembly code 來執行

    case '-':
        --(*ptr);
        break;
    case '.':
        putchar(*ptr);
        break;

### Compiler

相較之上，是編譯成 assembly code

## JIT

聽到很久了，但從來沒看過，就我所知他即是將 `brainf*ck` 轉換成 <s>assembly code</s> machine code，所以他比上面 interpreter 少了一步
> 這邊解釋我認為可以看，張家榮同學的共筆，他寫的詳細且簡潔。[name=Yen-Kuan Wu][color=#fcb888]
>>有看到廖健富共筆中有寫尚未實作profiler 所以JIT 無法邊編譯邊執行

---

# Code 觀察

# 實驗

:::info
Original
:::

progs/awib.b             GOOD	150.1ms
progs/mandelbrot.b       GOOD	3511.0ms
progs/hanoi.b            GOOD	8808.4ms

$ make bench-jit-x64 

Executing Brainf*ck benchmark suite. Be patient.

progs/awib.b             GOOD	99.7ms
progs/mandelbrot.b       GOOD	4227.8ms
progs/hanoi.b            GOOD	10583.1ms

>[name=HahaSula]
:::info
Contraction
:::

$ make bench-jit-x64 

Executing Brainf*ck benchmark suite. Be patient.

progs/awib.b             GOOD	67.2ms
progs/mandelbrot.b       GOOD	1404.2ms
progs/hanoi.b            GOOD	5440.1ms

:::info
Contraction && clean loop
:::

$ make bench-jit-x64 

Executing Brainf*ck benchmark suite. Be patient.

progs/awib.b             GOOD	48.7ms
progs/mandelbrot.b       GOOD	1354.6ms
progs/hanoi.b            GOOD	163.3ms

# 資料閱讀

## [Virtual Machine Constructions for Dummies](http://www.slideshare.net/jserv/vm-construct)
* Turing complete?
> 還記得在看 `模仿遊戲` 才第一次得知這咚咚，最簡易版本就是可跑在 turing machine 上，更進階一點的意思是，只要符合，就可以在上面跑任何演算法。[name=Yen-Kuan Wu]

* - [ ] While 迴圈的 interpreter
* - [ ] if-else-elseif

## [張家榮共筆](https://embedded2015.hackpad.com/HW4B-oKTqwC9newO)
>家榮大用了很精簡的方式來描述三者差別。
>* Interpreter
>直接執行
>疑問??user執行的視compiler還是code?[name=HahaSula]
>* Compiler
>將高階語言轉為組合語言
>* JIT
>將生成的機器碼(透過compiler)直接放到某塊JIT執行時期的記憶體(mmap)，直接執行
>>- [ ]可能要到程式碼看一下怎麼用到 mmap 的[name=Yen-Kuan Wu][color=#fcb888]
>## 三者速度比：
>* Interpreter
>最慢，因為要不停的來回，時間複雜度為O(n)，其他兩者為O(1)
>* Compiler
>如果只算執行時間，是最快的，但若考慮編譯時間，比JIT慢，因為多出I/O時間，把編好的檔案存起來再執行，而JIT把編好的內容，直接放入memory內，比JIT多一步，所以差異就出來了
>* JIT
>速度第二，但每次執行均須重編，若執行很多次也是不小的負擔。
其實JIT在於常常修改code的話，是十分方便的（前提是如果code本身不大）。
>> Compiler: I/O 應該指的是寫成 elf 檔的時間。
>> - [ ] JIT: 無法理解每次重編的意思，也就是不熟 JIT QQ[name=Yen-Kuan Wu][color=#fcb888]
>> - [ ] Interpreter 不產生Object檔案??那執行的mem在哪?link?a line is a excutefile?[name=HahaSula]
>> - [ ] Interpreter和jit compiler 跟 bf的source code 之間的關係?[name=HahaSula]

## compiler Opmization

SSA (靜態compiler 使用)
將L-value做版本編號，將程式流程作區塊的分類和簡化，以此消除掉一些參數(轉化為常數)，最後推導一些flow變數，進行判斷
[How A Compiler Works](http://www.slideshare.net/jserv/how-a-compiler-works-gnu-toolchain)的return 0的例子

Contraction

對於連加或是連減進行一個整合，原本一個+指令對應到一個asm的inc指令轉換成多個+指令對應的一個asm add指令
Ex:+++
add #3 , &ptr
>下列的DynASM 已經有飯粒了

copy loop

將一些Brainf*ck迴圈或是固定流程指令對應的指令減少
Ex:[>+<-] [->+<]
*(ptr+1) = *ptr;

* [ ]all clear loop (提出想法 不知道有否違背JIT)
>將 Clear Loops
想法:
將tape上的單位作區隔
分類一:
">"數量 = "<"數量 有固定的迴圈變數
頭尾視為終止條件和迴圈變數
">"數量 != "<"數量 變數在tape上變動
頭尾視為終止條件和tape變數 超過tape視為無線迴圈?
分類二:
以連續">","<"作為tape block version,將相同的block version 作結合。

## DynASM

DynASM is a preprocessor and tiny runtime library for creating assemblers and JIT compilers in C or C++.
> form [DynAsm](http://corsix.github.io/dynasm-doc/index.html)
* [ ] How it Dynamic?

---

##### tag <`Yen-Kuan Wu`> <`HahaSula`> <`jit-compiler`>