2016q3 Homework5 - JIT compiler === contributed by <`oiz5201618`>, <`ierosodin`> ###### tags: `sysprog-hw` `JIT compiler` # 作業要求 * 作在 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/) --- # Brainfuck Instructions Brainfuck 的基本模型是由一個==連續的記憶體位置==以及一個==指向記憶體的指標==所組成 >這八種指令組成的 BF ，符合圖靈機的基本思想 [Wikipedia](https://en.wikipedia.org/wiki/Turing_machine) [name=ierosodin] ## 八種 Brainfuck 的指令： ![](https://i.imgur.com/P4jM0IJ.png) --- # Compiler 一般編譯器的架構可以簡單拆成一個或數個 frontends ，以及一個或數個 backends ： ```graphviz digraph finite_state_machine { rankdir=LR; size="8,5" node [shape = ellipse]; source_code, executable; node [ shape="box" ]; source_code -> Frontend [ label = "" ]; Frontend -> Optimizer [ label = "IR" ]; Optimizer -> Backend [ label = "IR" ]; Backend -> executable [ label = "" ]; } ``` Frontend 先將原始碼轉換為一個或多個的 IR ，方便進行最佳化，再由 Backend 將 IR 轉換成執行程式。 * [Intermediate Representation wikipedia](https://en.wikipedia.org/wiki/Intermediate_representation) > C語言作為許多作業系統的 System programming language ，很多其他的語言都使用它作為 IR [name=ierosodin] > 中介碼（IR，intermediate representation）[name=阿Hua] # Objdump [陳鐘誠教授](http://ccckmit.wikidot.com/gnu:objdump)：Objdump 是 GNU 的主要目的檔觀察工具, 您可用 objdump 顯示目的檔的檔頭、區段、內容、符號表等資訊, 表格一顯示了其使用方法。 ![](https://i.imgur.com/pNTG3Xx.png) * [objdump(1) - Linux man page](https://linux.die.net/man/1/objdump) --- # 優化策略 * [brainfuck optimization strategies](http://calmerthanyouare.org/2015/01/07/optimizing-brainfuck.html) * `Contraction` * `Clear loops` * `Copy loops` * `Multiplication loops` * `Scan loops` * `Operation offsets` ``` clear [-] ``` ``` Copy loops [->+>+<<] ``` > 由於P[0]為判斷條件跟複製目標，其值將會遞減改變，因此將P[0]中的值複製到P[1]、P[2]之中，來達到複製的目的。 > [name=阿Hua] ``` Multiplication loops [->+++<] or [->+++>+++++++<<] ``` > Mul的操作視需求可以資料數 > 如上`[->+++>+++++++<<]`效果等同於 > ``` > P[1] += P[0] * 3; > P[2] += P[0] * 7; > P[0] = 0; > ``` > `+=`原因是因為若`P[1]、P[2]`中有值，就會直接累加 > 想要清空`P[1]、P[2]`就可以搭配上面的 copy loop 來使用 > [name=阿Hua] # About DynASM * generating machine code at runtime * JIT 利用 DynASM 動態產生 machine code 並將它放入 `dasm_State` (at runtime) ，最後再轉換成可執行的機器碼 * `|` 有這個開頭的表示， DynASM 的 preprocessor 會先進行處理 * `|.arch ` 在每一個 DynASM source file 中，必須先指定產生哪種架構的 machine code ，例如 x86 或 x64 * `.define (for simple substitutions)` * `.macro (for more complex constructions)` * `dasm_State` 用來存 DynASM 的狀態 * `initjit()` 包含了 `dasm_init(state, 1)` 與 `dasm_setup(state, actionlist)`，前者為配置 DynASM state 的空間，後者則是完成 DynASM state 的初始化 透過 brainfuck 做出來的碎形 ![](https://i.imgur.com/K8OgSTp.png) --- # 針對 jit-x64 進行效能優化 ## 未優化版本 ``` progs/awib.b GOOD 89.4ms progs/mandelbrot.b GOOD 3486.2ms progs/hanoi.b GOOD 8919.4ms ``` ![](https://i.imgur.com/gJBn2gU.png) ## Contraction > 請在分組頁面中補上 github 連結 > [color=red][name=課程助教] > >OK [color=orange][name=阿Hua & ierosodin] > >>.[color=yellow] > >> >.[color=green] > >> > >.[color=blue] > >> > >>.[color=purple] 此方法是將多餘運算整併，例如 +++++ ，其實就是 += 5，此改善方法雖然直覺簡單，但實質效益也不差，而實作方法可在遇到+ - > < 時即檢查是否為連續出現。 ```clike= int continuous_count(char *p) { char *ptr = p; int count = 0; while (*ptr == *p) { count++; ptr++; } return count; } ``` 在 main 中修改成如下，包含 >、<、+、- ```clike= case '+': count = continuous_count(p); p += count - 1; | add byte [PTR], count break; ``` ``` progs/awib.b GOOD 51.0ms progs/mandelbrot.b GOOD 1276.1ms progs/hanoi.b GOOD 5175.9ms ``` ![](https://i.imgur.com/QDHPjZr.png) 我們使用 if else 判斷，保留 inc 在只有出現一次的時候 ```clike= case '+': count = continuous_count(p); if(count == 1){ | inc byte [PTR] }else{ p += count - 1; | add byte [PTR], count } break; ``` 效能如下，可以發現在 awib.b、mandelbrot.b 效能反而變差，而只有 hanoi.b 效能變佳 我們發現 hanoi.b 相較於其他兩者有更大量的 [ - ] 操作，所以 inc 對比於 add 指令操作的優化會凸顯出來，但使用到其他兩者則沒有反而因為條件判斷使得效能降低。 ``` progs/awib.b GOOD 59.0ms progs/mandelbrot.b GOOD 1295.9ms progs/hanoi.b GOOD 4529.9ms ``` ![](https://i.imgur.com/RAbRQuj.png) > - [ ] TODO：將圖表換成倍數 [color=blue][name=阿Hua] --- ## Clear loop 遇到 [ - ] 的情況直接將PTR給予的值給 0 ，然後跳過 ```clike= int clear_loop(char *p){ if (*(p+1) == '-' && *(p+2) == ']'){ return 1; }else{ return 0; } } case '[': if (top == limit) err("Nesting too deep."); if(clear_loop(p)){ p += 2; | mov byte [PTR], 0 break; }else{ maxpc += 2; *top++ = maxpc; dasm_growpc(&state, maxpc); | cmp byte [PTR], 0 | je =>(maxpc-2) |=>(maxpc-1): break; } ``` ``` progs/awib.b GOOD 41.1ms progs/mandelbrot.b GOOD 1237.5ms progs/hanoi.b GOOD 137.1ms ``` ![](https://i.imgur.com/8H7HFzS.png) --- # Clear Loop & Multiple Loop & Copy Loop 因為這三者都和 while 迴圈有關，[參考老師](https://hackmd.io/s/SJ7AZJv1e) 的 check_loop() 進行修改，合併三個功能 >因為是用 `read_file(argv[1])` 讀取.b檔的字元，需要考慮到程式碼換行的問題( `'\n'` 也算一個字元) [name=ierosodin] > Multiple loop 的組語本身必須考慮到位元的配合，才不會因為搬動過多的記憶體，讓運算出錯 >利用 global variable `global_count` 來計算 p 指標確切的位移量，避免遇到 '\n' 或空白所造成 offset 計算上的錯誤 Check loop 的修改 ```clike= int check_loops(char *p,int *index,int *mult) { int res,offset = 0,_index = 0; global_count = 0; if (*(p+1) != '-') return -1; p += 2; global_count += 2; while (*p != ']') { if (*p == '[' || *p == '-' || *p == '.' || *p == ',') return -1; res = continuous_count(p); if (*p == '>') offset += res; else if (*p == '<') offset -= res; else if (*p == '+') { index[_index] = offset; mult[_index] = res; _index++; } global_count += res; p += res; } if (offset != 0) return -1; return _index; } ``` main 裡面組語的修改 ```clike= case '[': if (top == limit) err("Nesting too deep."); count = check_loops(p, index, mult); if(count == 0){ p += global_count; | mov byte [PTR], 0 break; }else if(count > 0){ | mov cx, word [PTR] | mov r11, PTR | add PTR, index[0] | mov ax, word mult[0] | imul ax, cx | add byte [PTR], al for(int i = 1; i < count; i++){ | mov r9, index[i] | sub r9, index[i - 1] | add PTR, r9 | mov ax, mult[i] | imul ax, cx | add byte [PTR], al } | mov PTR, r11 | mov byte [PTR], 0 p += global_count; break; }else{ maxpc += 2; *top++ = maxpc; dasm_growpc(&state, maxpc); | cmp byte [PTR], 0 | je =>(maxpc-2) |=>(maxpc-1): break; } ``` ``` progs/awib.b GOOD 39.3ms progs/mandelbrot.b GOOD 1351.9ms progs/hanoi.b GOOD 97.8ms ``` ![](https://i.imgur.com/J9L3RJ5.png) > 因為每次遇到換行 '\n' 時， check loop 都會額外再調用 continuous_count 來檢查;而且當一連串的 ++++ 遇到換行時， 也會變成兩次運算，因此還有能夠優化的空間 > [name=阿Hua] > 從比較圖中可以發現，加入 check_loops 功能之後，碎形運算的效能反而降低了，還在思考 code 與優化方法之間的影響 [name=ierosodin] --- 將換行符號考慮進去後的效能表現， hanoi 再效能上有較穩定的變快，但其他兩者的數字很浮動，但整體的最快速度都是變快的 ``` progs/awib.b GOOD 32.3ms progs/mandelbrot.b GOOD 1329.1ms progs/hanoi.b GOOD 86.7ms ``` ![](https://i.imgur.com/x8EbPtz.png) > - [ ]TODO：必須加入數學統計模型[color=blue][name=阿Hua] --- # 參考資料 * [廖健富共筆](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) * [brainfuck optimization strategies](http://calmerthanyouare.org/2015/01/07/optimizing-brainfuck.html) * [Lua 學習筆記 (一) : 基本語法](http://yhhuang1966.blogspot.tw/2015/07/lua_14.html) * [The Unofficial DynASM Documentation](https://corsix.github.io/dynasm-doc/reference.html#dynasm_lua) * [中英對照表](http://jjhou.boolan.com/terms.htm) * [x86 Assembly Guide](http://www.cs.virginia.edu/~evans/cs216/guides/x86.html) * [dynasm](https://luapower.com/dynasm) * [mov in assembly](http://slvs.tc.edu.tw/~baochyi/teacher/assembly/c0402.htm) * [PC Assembly Language 學習筆記(8) - Arrays](http://godleon.blogspot.tw/2008/02/assembly-segment.html) * [Arrays in Assembly Language](http://www.cs.uwm.edu/classes/cs315/Bacon/Lecture/HTML/ch12s04.html)