2016q3 Team20_HＷ5 (jit-compiler)

# 2016q3 Team20_HＷ5 (jit-compiler) contributed by <`eeuserp`>, <`SaragCheng`> ## 組員 - [ ] 簡伯丞 - [ ] 程鈺涵 - [ ] 施雨妏# ## 作業要求 [A09: jit-compiler](https://hackmd.io/s/SJ7AZJv1e) * 在 github 上 fork [jit-construct](https://github.com/sysprog21/jit-construct) * 學習設計 JIT 編譯器 * 運用計算機組織的背景知識，進行深入效能評估和提出改善方案 * 提出改善內建 benchmark suite 效能的機制，並且要能夠充分解釋行為，需要一併透過 gnuplot 自動產生效能分析圖表 * 延展程式語言，提供 concurrency 能力 * 對 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/) ## 基礎知識 ### JIT (Just In Time) compilation 與執行前編譯好執行檔不一樣，JIT 是一邊執行程式一邊編譯，可以直接將程式碼轉成機械碼或是其他形式執行。常常使用在 dynamic programming language。 ### Interpreter ### Compiler 將 brainfuck 編譯成組語 * [複習組語](http://www.cs.cmu.edu/afs/cs/academic/class/15213-f05/lectures/class05.txt) * `cmpb $0, (%r12)` takes a byte that r12 point to and compare with 0 * if (b < 0) a++; 可更換為沒有分支的版本: a -= b >> 31; ### Brainfuck * Rules:( char *p 指向記憶體區塊) ![](https://i.imgur.com/zV3bos5.png) ### [compiling brainfuck to java in brainfuck](http://calmerthanyouare.org/2014/09/30/brainfuck-java.html) * Awib is a brainfuck compiler written in brainfuck * 前端(frontends) : 接受 source code 作為 input，產生 IR(intermediate representation) 作為 output * 後端(backends) : 接受 IR 作為 input ，產生可執行檔作為 putput * IR(intermediate representation) : 是一種資料結構，可將輸入的資料建構為一個電腦程式，也可以將一部份或是所有輸出的程式反推回輸入資料。這意味著 IR 將會保留一些輸入資料的資訊，同時擁有更進一步註釋或是快速查詢的功能。 * Awib compiler 的 frontends 和 backends 之間會有一些 Optimizer ![](https://i.imgur.com/JQ7Nv3R.png) * Representing large integers * 一個 cell 只有 8 bit ，這樣一來 loop 最多不就只能執行敘述 255 次 !? 那使用兩個 cell 一共 16 bit 好了，這樣充其量也只能執行65535 次啊。 * 解決辦法 : 一樣使用兩個 cell，但用法不同。以遞增為例，當 least significant cell 為 255 又要再加上去時， most significant cell ++ ， least significant cell 設為 0。 ``` function increment(hi, lo): if lo < 255: return (hi, lo + 1) return (hi + 1, 0) ``` * Storing the stack * **no random memory access in brainfuck** * 不需要 stack top variable * 必須自己設計 stack segment of the memory area * 必須確保 stack 能夠提供多層巢狀迴圈做計算 * 在記憶體中存放 stack 的一段連續記憶體位址稱為 stack segment ，存放 IR 的一段連續記憶體位址稱為 IR segment。在這兩個 segment 旁邊的位址寫入0 以防迴圈動到這兩個區塊，如下圖。 ![](https://i.imgur.com/7E9N4mf.png) ### [brainfuck optimization strategies](http://calmerthanyouare.org/2015/01/07/optimizing-brainfuck.html) 最佳化策略: * Contraction * Clear loops * Copy loops * Multiplication loops * Operation offsets * Scan loops ## 未優化版本輸入`make bench-jit-x64` 測試結果： ```shell Executing Brainf*ck benchmark suite. Be patient. progs/awib.b GOOD 116.0ms progs/mandelbrot.b GOOD 4213.6ms progs/hanoi.b GOOD 10782.6ms ``` ## 優化版本 ### Clear Loop * 修改 jit-x64.dasc 檔 ```clike= if(*(p+1) == '-'&&*(p+2) == ']'){ | mov byte [PTR], 0 } ``` * 執行結果 ```shell Executing Brainf*ck benchmark suite. Be patient. progs/awib.b GOOD 91.5ms progs/mandelbrot.b GOOD 4149.0ms progs/hanoi.b GOOD 4204.0ms ``` * 觀察執行結果可以發現跟為優化版本相比只有 hanoi.b 大幅降低執行時間（執行速度提升約 2.56 倍），由此可見 hanoi.b 程式碼裡有大量(44%)的`[-]`敘述，而 awib.b 只有極少量(14%)的`[-]`敘述 ### Contraction * 依照作業提示修改 jit-x64.dasc 檔，如下： ```clike= int continuous_count(char *p) { char *ptr = p; int count = 0; while (*ptr == *p) { count++; ptr++; } return count; } ``` 利用`add` `sub` 指令修改 for loop 中 `>` `<` `+` `-` 4 個 case ，指令用法如下 ```shell add <reg>,<con> add <mem>,<con> ``` example: ``` add BYTE PTR [var], 10 // add 10 to the single byte stored at memory address var add eax, 10 // EAX ← EAX + 10 ``` * 執行結果： ```shell Executing Brainf*ck benchmark suite. Be patient. progs/awib.b GOOD 56.4ms progs/mandelbrot.b GOOD 1551.1ms progs/hanoi.b GOOD 5372.3ms ``` * 觀察執行結果可以發現跟未優化版本相比 3 個程式的執行時間接大幅降低許多， awib.b 執行速度提升約 1.6 倍， mandelbrot.b 執行速度提升約 2.71 倍， hanoi.b 執行速度提升約 2.00 倍。 > `if(count == 1)`這個分支可以拿掉嗎？應該會更快？[name=SarahCheng] ### Clear loops & Copy loops & Multiplication loops * 依照作業提示修改 jit-x64.dasc 檔，如下： ```clike= int check_loops(char *p,int *index,int *mult) { int res,offset = 0,_index = 0; if (*(p+1) != '-') return -1; //不合這三種 loop p += 2; while (*p != ']') { //not end of loop if (*p == '[' || *p == '-' || *p == '.' || *p == ',') return -1;  //不合這三種 loop res = continuous_count(p); if (*p == '>') offset += res; else if (*p == '<') offset -= res; else if (*p == '+') { index[_index] = offset; mult[_index] = res; _index++; } p += res; } if (offset != 0) return -1;//不合法的loop，沒有回到第一個p return _index; //_index==0:clear; else:copy,multi; } ``` 以上這段程式碼將 copy 視為 Multiplication 中 * 1的狀況 `index[ ]` 儲存的是目的位址相較現在位址的位移量 `mult[ ]` 儲存的是要乘多少( `+` 的個數) 這個程式碼的精妙之處在於可以隨意以任何位址作目的位址，而且不局限於參考資料中的兩次 * 修改 for loop 中 `[` case : * 注意register的使用[(ref)](http://wanker742126.myweb.hinet.net/) * ![](https://i.imgur.com/JJNsCzW.png) * x64 架構的 CPU 是屬於 64 位元，包含了 16 個 64 位元的通用暫存器 ( general-purpose registers )，後面的 R8~R15，是新增的；而前面的八個暫存器，RAX、RBX、RCX、RDX、RBP、RSP、RSI、RDI，是把原有的 32 位元加以擴充而成。 * 雖然是在 64 位元系統中，但是還是可以使用 32、16、8 位元的暫存器。如上圖所示，EAX、EBX、ECX、EDX、ESI、EDI、EBP、ESP 等 32 位元的暫存器仍然可以使用；而新增加的 32 位元暫存器名為 R8D~R15D，暫存器名結尾的『D』是指雙字組 ( DWORD )。16 位元的暫存器也有十六個，分別是舊的 AX、BX、CX、DX、DI、SI、BP、SP 與新增的 R8W~R15W，這裏的『W』，顯然就是字組 ( WORD ) 之意。可用的 8 位元暫存器也有十六個，分別是舊有的 AL、BL、CL、DL 與新增的 SIL、DIL、BPL、SPL、R8BR15B，這裏的『B』是位元組 ( BYTE ) 的意思，而『L』是指低位元組之意 ``` _index=check_loops(p,idx,mult); length = sizeof(index)/sizeof(int); if(_index==0){ | mov byte [PTR], 0 } else{ while(i<length){ | push r8 | push r9 | movzx r8, byte [PTR] | imul r8, mult[i] | mov r9, PTR | add r9,idx[i] | add byte [r9],r8b | | pop r9 | pop r8 i++; } } ``` 註 : 不知道為什麼加上`clike=`整個程式碼區塊就會走鐘 * 執行結果: ``` Executing Brainf*ck benchmark suite. Be patient. progs/awib.b GOOD 47.4ms progs/mandelbrot.b GOOD 1516.5ms progs/hanoi.b GOOD 178.5ms ``` * 相較於位優化版本 awib.b 的執行速度提升了約2.45倍， mandelbrot.b的執行速度提升了約2.78倍， hanoi.b 的執行速度提升了約60.40倍。觀察可以得知 Clear loops & Copy loops & Multiplication loops 的處理對 hanoi.b 有非常巨大的幫助，因為光是clear loops 和 copy loops就佔了整個程式碼的80%。對mandelbrot.b沒什麼影響。 * length_idx: 128 length_index: 0, so it can work because it didn't run the loop >Q1.does our ptr move forward by 'count'? >Q2.take away the code `mov byte [PTR],0` , the error still exist >WHAT'S THE PROBLEM ABOUT WHILE LOOP? [name=SarahCheng] >try this: ``` while(x==1){ //Do something } ``` The same loop in assembler: ``` jmp loop1 ; Jump to condition first cloop1 nop ; Execute the content of the loop loop1 cmp ax,1 ; Check the condition je cloop1 ; Jump to content of the loop if met ``` deal with the variable 'length', not sure does it work or not ``` register int *length asm ("r10"); ``` [variable to reg ](https://gcc.gnu.org/onlinedocs/gcc-4.0.0/gcc/Local-Reg-Vars.html) 那這樣還要push r10嗎? * 一行一行測試結果： * failed output after add this: ` | add byte [PTR],r8b` output: ``` progs/awib.b bad output: expected 3b4f9a78ec3ee32e05969e108916a4affa0c2bba got 93898477b77b662771e12579cd4d1b7ad1771d1d �� progs/mandelbrot.b bad output: expected b77a017f811831f0b74e0d69c08b78e620dbda2b got da39a3ee5e6b4b0d3255bfef95601890afd80709 ``` * 可以參考 [Team6](https://hackmd.io/IwZgZgxgJgDAhhAtDARgFgJyM3AHIlAJnAIjimElwFNcQB2IA===?both#) / [github](https://github.com/janetwei/jit-construct/tree/aaeee1accefa5da6eac702d43da304eb0486f61a) ## 問題 * 對專案 make 產生以下錯誤訊息 ```shell /usr/lib/gcc-cross/arm-linux-gnueabihf/5/../../../../arm-linux-gnueabihf/bin/ld: cannot find crt1.o: No such file or directory /usr/lib/gcc-cross/arm-linux-gnueabihf/5/../../../../arm-linux-gnueabihf/bin/ld: cannot find crti.o: No such file or directory collect2: error: ld returned 1 exit status Makefile:64: recipe for target 'jit-arm' failed make: *** [jit-arm] Error 1 ``` > 有照著github上的指示安裝套件了 [name=eeuserp] >> 試著用 `sudo apt-get install gcc-multilib` 來安裝必要的套件 [name=jserv] >> 可以參考 https://hackmd.io/s/ryDY1CPyl >> [name=施雨妏] ##### 組語不夠熟，debug: * ` error: bad operand size in "imul rb,i?":| imul ah, mult[i]` > maybe: ah x86的 8 bits register，但是乘法必須是32 bits的register [name=SarahCheng] * `error: mixed operand size in "mov rq,xb":| mov rax, byte [PTR]` [name=SarahCheng] >> >> #include <windows.h> >> there is a func: ARRAYSIZE() >> [name=SarahCheng] >> [ref](https://youtu.be/IgPGwI1f29Q) * `error: array size missing in ‘index’int index[];` * ` missing terminating ' character [-Werror] case '.:` * `printf("PTR:%s, index[0]:%d",p,index[0]);`不知道為什麼是這結果 ![](https://i.imgur.com/dJzKjwT.png) ## 參考資料 * [廖健富共筆](https://hackpad.com/2015q3-Homework-4B-5I46HyqOCGJ#:h=Jit-construct) * [林郁寧共筆](https://embedded2015.hackpad.com/-Homework4-B-h5FfVE6RTeu) * [作業共筆彙整](https://emb不夠edded2015.hackpad.com/2015q3-Homework-4-8AvSmXDYC38) * [Intermediate representation - Wikipedia](https://en.wikipedia.org/wiki/Intermediate_representation) * [x86 Assembly Guide](http://www.cs.virginia.edu/~evans/cs216/guides/x86.html) >好用!![name=eeuserp] * [Introduction to x64 Assembly](https://software.intel.com/en-us/articles/introduction-to-x64-assembly) * [x64 Architecture](https://msdn.microsoft.com/en-us/library/windows/hardware/ff561499(v=vs.85).aspx) * [x64 CPU 暫存器](http://wanker742126.myweb.hinet.net/) * [Team5(LanKuDot, ktvexe)共筆](https://hackmd.io/AwDgrMBsKQxgtCA7LY8Asp2NkgRvAIYAmAzMHugGaGlJjpA=)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.