2016q3 Homework5 - JIT compiler

contributed by <oiz5201618>, <ierosodin>

tags: sysprog-hw JIT compiler

作業要求

• 作在 github 上 fork jit-construct，注意不要跟 2015 年的作業搞錯了
• 依據上方提示，提出改善內建 benchmark suite 效能的機制，並且要能夠充分解釋行為，需要一併透過 gnuplot 自動產生效能分析圖表
• 參考以下實做，對 Brainfuck 程式語言進行擴充，使其能夠支援 concurrency / parallelism。需要有程式語言的規格描述並且驗證。
  • Bukkake: A parallel brainfuck JIT in C
  • Brainfuck Process Extensions
  • Parallel Brainfuck
  • Concurrent Brainfuck

---

Brainfuck Instructions

Brainfuck 的基本模型是由一個連續的記憶體位置以及一個指向記憶體的指標所組成

這八種指令組成的 BF ，符合圖靈機的基本思想 Wikipedia ierosodin

八種 Brainfuck 的指令：

Compiler

一般編譯器的架構可以簡單拆成一個或數個 frontends ，以及一個或數個 backends ：

Frontend 先將原始碼轉換為一個或多個的 IR ，方便進行最佳化，再由 Backend 將 IR 轉換成執行程式。

• Intermediate Representation wikipedia

C語言作為許多作業系統的 System programming language ，很多其他的語言都使用它作為 IR ierosodin
中介碼（IR，intermediate representation）阿Hua

Objdump

陳鐘誠教授：Objdump 是 GNU 的主要目的檔觀察工具, 您可用 objdump 顯示目的檔的檔頭、區段、內容、符號表等資訊, 表格一顯示了其使用方法。

• objdump(1) - Linux man page

---

優化策略

• brainfuck optimization strategies
  • Contraction
  • Clear loops
  • Copy loops
  • Multiplication loops
  • Scan loops
  • Operation offsets

clear [-] 

Copy loops [->+>+<<] 

由於P[0]為判斷條件跟複製目標，其值將會遞減改變，因此將P[0]中的值複製到P[1]、P[2]之中，來達到複製的目的。
阿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 來使用
阿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 做出來的碎形

針對 jit-x64 進行效能優化

未優化版本

progs/awib.b            GOOD	89.4ms
progs/mandelbrot.b      GOOD	3486.2ms
progs/hanoi.b           GOOD	8919.4ms

Contraction

請在分組頁面中補上 github 連結
課程助教

OK 阿Hua & ierosodin

.

.

.

.

此方法是將多餘運算整併，例如 +++++ ，其實就是 += 5，此改善方法雖然直覺簡單，但實質效益也不差，而實作方法可在遇到+ - > < 時即檢查是否為連續出現。

int continuous_count(char *p)
{
    char *ptr = p;
    int count = 0;
    while (*ptr == *p) {
        count++;
        ptr++;
    }
    return count;
}

在 main 中修改成如下，包含 >、<、+、-

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

我們使用 if else 判斷，保留 inc 在只有出現一次的時候

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

• TODO：將圖表換成倍數 阿Hua

---

Clear loop

遇到 [ - ] 的情況直接將PTR給予的值給 0 ，然後跳過

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

---

Clear Loop & Multiple Loop & Copy Loop

因為這三者都和 while 迴圈有關，參考老師 的 check_loop() 進行修改，合併三個功能

因為是用 read_file(argv[1]) 讀取.b檔的字元，需要考慮到程式碼換行的問題( '\n' 也算一個字元) ierosodin

Multiple loop 的組語本身必須考慮到位元的配合，才不會因為搬動過多的記憶體，讓運算出錯

利用 global variable global_count 來計算 p 指標確切的位移量，避免遇到 '\n' 或空白所造成 offset 計算上的錯誤

Check loop 的修改

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 裡面組語的修改

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

因為每次遇到換行 '\n' 時， check loop 都會額外再調用 continuous_count 來檢查;而且當一連串的 ++++ 遇到換行時， 也會變成兩次運算，因此還有能夠優化的空間
阿Hua

從比較圖中可以發現，加入 check_loops 功能之後，碎形運算的效能反而降低了，還在思考 code 與優化方法之間的影響 ierosodin

---

將換行符號考慮進去後的效能表現， hanoi 再效能上有較穩定的變快，但其他兩者的數字很浮動，但整體的最快速度都是變快的

progs/awib.b            GOOD	32.3ms
progs/mandelbrot.b      GOOD	1329.1ms
progs/hanoi.b           GOOD	86.7ms

• [ ]TODO：必須加入數學統計模型阿Hua

---

參考資料

• 廖健富共筆
• 林郁寧共筆
• 作業共筆彙整
• brainfuck optimization strategies
• Lua 學習筆記 (一) : 基本語法
• The Unofficial DynASM Documentation
• 中英對照表
• x86 Assembly Guide
• dynasm
• mov in assembly
• PC Assembly Language 學習筆記(8) - Arrays
• Arrays in Assembly Language