2016q3 Homework5 (jit-compiler)

contributed by <HuangWenChen> , <aweimeow>

預期目標

• 學習設計 JIT 編譯器
• 運用計算機組織的背景知識，進行深入效能評估和提出改善方案
• 延展程式語言，提供 concurrency 能力

環境設置

Fork jit-construct
閱讀 README.md 依序安裝操作

sudo apt-get update
sudo apt-get install build-essential
sudo apt-get install gcc-5-multilib
sudo apt-get install lua5.2 lua-bitop
sudo apt-get install gcc-arm-linux-gnueabihf
sudo apt-get install qemu-user

背景知識

JIT (Just-In-Time) compiler

• 參考資料 JIT compiler overview

The Just-In-Time (JIT) compiler is a component of the Java™ Runtime Environment that improves the performance of Java applications by compiling bytecodes into native machine code at run time.

Just-In-Time (JIT) compiler 是 Java™ Runtime Environment 的一部分，在執行時可以藉由編譯位元組碼成原生本機機器碼改善 Java 應用程式的效能。

Just-in-time compilation

• 參考資料 Just-in-time compilation wiki

Just-in-time (JIT) compilation, also known as dynamic translation, is compilation done during execution of a program – at run time – rather than prior to execution. Most often this consists of translation to machine code, which is then executed directly, but can also refer to translation to another format.

just-in-time (JIT) compilation 也被稱為動態編譯 (dynamic translation)，是在程序執行期間 - 在運行時完成編譯 - 而不是執行之前。因為通常大部分都是由編譯可直接執行的機械碼組成，但是也可以參考編譯成另一種格式。

JIT compilation is a combination of the two traditional approaches to translation to machine code – ahead-of-time compilation (AOT), and interpretation.

JIT compilation 是一個結合兩種傳統方法去編譯成機械碼，一種是 ahead-of-time compilation (AOT)，另一種是 interpretation

ahead-of-time compilation (AOT)

• 參考資料 Ahead-of-time compilation

Ahead-of-time (AOT) compilation is the act of compiling a high-level programming language such as C or C++, or an intermediate language such as Java bytecode or .NET Common Intermediate Language (CIL) code, into a native (system-dependent) machine code with the intention of executing the resulting binary file natively.

Ahead-of-time (AOT) compilation 是一個編譯高階程式語言 (C 或 C++) 或是中階語言(Java bytecode 或 .NET Common Intermediate Language (CIL) code) 成本機機械碼的行為，並產生本機可執行二進制文件檔案。

AOT produces machine optimized code, just like a "standard" native compiler. The difference is that AOT transforms the bytecode of an existing VM into machine code.

AOT 產生機械優化代碼就像是一個"標準"本機編譯器。而與本機編譯器不同的地方是 AOT 會轉換一個已存在虛擬機的位元組碼成機械碼。

Interpreter

• 參考資料 Interpreter (computing)

An interpreter is a computer program that directly executes, i.e. performs, instructions written in a programming or scripting language, without previously compiling them into a machine language program.

interpreter 是一個電腦語言，不用先前編譯程式語言成機械語言程式就能直接執行。

An interpreter generally uses one of the following strategies for program execution:

1. parse the source code and perform its behavior directly.
2. translate source code into some efficient intermediate representation and immediately execute this.
3. explicitly execute stored precompiled code[1] made by a compiler which is part of the interpreter system.

interpreter 使用下列其中一個策略讓程式執行：

1. 解析原始碼並直接執行動作。
2. 轉換原始碼成一些有效的中間語言並立刻執行。
3. 以直譯器包含的編譯器對高階語言編譯，並指示處理器執行編譯後的程式

Brainfuck

• 參考資料
  • Brainfuck wiki
  • A09: jit-compiler

Brainfuck，是一種極小化、符合圖靈完全思想的程式語言，是由只有八個簡單的指令與一個指令指標所組成的。

• 圖靈完備(turing complete) 如果它可以被用來模擬任何單磁帶圖靈機，一個數據操作規則（像是一組電腦的指令集，程式語言，或是細胞自動機）的系統被稱為圖靈完備（turing complete）

Brainfuck	C	描述
>	++p	增加資料指標指向下一個 cell
<	–p	減少資料指標指向上一個 cell
+	++*p	資料指標指向的位元組值加一
-	–*p	資料指標指向的位元組值減一
.	putchar(*p)	輸出資料指標指向的位元組值
,	*p=getchar()	輸入一個位元組值並存到資料指標
[	while(*p){	如果資料指標指向的位元組值為零，向後跳轉到對應的]指令的次一指令處
]	}	如果資料指標指向的位元組值不為零，向前跳轉到對應的[指令的次一指令處

Optimization

• A09: jit-compiler

在 brainfuck optimization strategies提到以下最佳化策略:

• Contraction
• Clear loops
• Copy loops
• Multiplication loops
• Operation offsets
• Scan loops

未最佳化之數據

Executing Brainf*ck benchmark suite. Be patient.

progs/awib.b            GOOD    168.5ms
progs/mandelbrot.b      GOOD    5342.1ms
progs/hanoi.b           GOOD    17117.2ms

Contraction

此方法是將多餘運算整併，例如 +++++ ，其實就是+=5，實作方法可在遇到+ - > < 時檢查是否為連續出現。而在此我們保留 inc 在只有出現一次的時候，可使效能最佳化。

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

Executing Brainf*ck benchmark suite. Be patient.

progs/awib.b            GOOD    100.6ms
progs/mandelbrot.b      GOOD    2381.6ms
progs/hanoi.b           GOOD    9478.1ms