2016q3 Homework5 (jit-compiler)

contributed by <judy66jo>, <JonSyuGithub>

作業目標

• 改善內建 benchmark suite 效能的機制，並且要能夠充分解釋行為，需要一併透過 gnuplot 自動產生效能分析圖表
• 對 Brainfuck 程式語言進行擴充，使其能夠支援 concurrency / parallelism

Brainfuck

只有八個運算字元，可做數學運算、迴圈，以下為分別對應的 C code

• > |++ptr
• < |--ptr
• + |++*ptr
• - |--*ptr
• . |putchar(*ptr)
• , |*ptr = getchar()
• [ |while(*ptr) {
• ] |}

DynASM

A Dynamic Assembler for code generation engines.

Interpreter、Compiler、JIT比較

• Interpreter

  • 直接執行.b程式
  • 速度最慢，因為要不停地來回
  • 時間複雜度O(n)

• Compiler

  • 將高階語言編譯成 assembly code
  • 執行時間最快，但因比 JIT 多出 I/O 時間，故編譯時間較慢， Compiler 把編譯好的檔案先存起來，再執行
  • 有錯誤無法馬上修改
  • 時間複雜度O(1)

• JIT

  • 利用 DynASM 動態產生 machine code
  • 把透過 Compiler 生成的機器碼直接放到某塊 JIT 執行時期的記憶體 mmap 直接執行
  • 不會把編譯好的檔案存起來，每次均需重新編譯，若執行許多次也是一種負擔
  • 有錯誤可以馬上修改
  • 時間複雜度O(1)

JIT 的整體流程

• 進入 main function，逐行讀入 input file 並將對應的 machine code 塞入 dasm_State 中
• 呼叫 jitcode，透過dasm_link 與 dasm_encode 將 dasm_State 轉換成可執行的機器碼 block，並回傳
• 呼叫從 jitcode 回傳的函式指標，也就是前面讀入的 brainf*ck 程式(已經轉為當前架構的機器碼)

Optimization

記錄未優化前時間

$ make bench-jit-x86

Executing Brainf*ck benchmark suite. Be patient.

progs/awib.b            GOOD	98.3ms
progs/mandelbrot.b      GOOD	2948.4ms
progs/hanoi.b           GOOD	6291.6ms

$ make bench-jit-x64

Executing Brainf*ck benchmark suite. Be patient.

progs/awib.b            GOOD	64.8ms
progs/mandelbrot.b      GOOD	2969.5ms
progs/hanoi.b           GOOD	6236.9ms

改寫jit-x64

• Contraction
  將連續的 inc(+ , >) 或 dec(- , <) 合併成 add 或 sub

  ​progs/awib.b            GOOD	46.7ms
  ​progs/mandelbrot.b      GOOD	1032.8ms
  ​progs/hanoi.b           GOOD	3387.9ms
  

• Clear loops & Copy loops & Multiplication loops

• Scan loops

References

A09: jit-compiler
https://hackpad.com/2015q3-Homework-4B-5I46HyqOCGJ#:h=Jit-construct
https://embedded2015.hackpad.com/-Homework4-B-h5FfVE6RTeu
https://mimihalo.hackpad.com/HW4–2r8xNuU8gdf

tags: sysprog21 Team23