# 2016q3 Homework5 (jit-compiler)
contributed by <`HuangWenChen`> , <`aweimeow`>

## 預期目標

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

## 環境設置
Fork [jit-construct](https://github.com/sysprog21/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](http://www.ibm.com/support/knowledgecenter/SSYKE2_7.0.0/com.ibm.java.lnx.70.doc/diag/understanding/jit_overview.html)

The Just-In-Time (JIT) compiler is a component of the Java™ Runtime Environment that improves the performance of Java applications by compiling [bytecodes](https://en.wikipedia.org/wiki/Bytecode) into native machine code at run time.
>Just-In-Time (JIT) compiler 是 Java™ Runtime Environment 的一部分，在執行時可以藉由編譯[位元組碼](https://zh.wikipedia.org/wiki/%E5%AD%97%E8%8A%82%E7%A0%81)成原生本機機器碼改善 Java 應用程式的效能。

### Just-in-time compilation
* 參考資料 [Just-in-time compilation wiki](https://en.wikipedia.org/wiki/Just-in-time_compilation)

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](https://en.wikipedia.org/wiki/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)](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Brainfuck)
* [A09: jit-compiler](https://hackmd.io/s/SJ7AZJv1e#brainfuck-程式語言)

Brainfuck，是一種極小化、符合圖靈完全思想的程式語言，是由只有八個簡單的指令與一個指令指標所組成的。
* [圖靈完備(turing complete)](https://en.wikipedia.org/wiki/Turing_completeness) 如果它可以被用來模擬任何單磁帶圖靈機，一個數據操作規則（像是一組電腦的指令集，程式語言，或是細胞自動機）的系統被稱為圖靈完備（turing complete）

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

## Optimization
* [A09: jit-compiler](https://hackmd.io/s/SJ7AZJv1e#brainfuck-程式語言)

在 [ brainfuck optimization strategies](http://calmerthanyouare.org/2015/01/07/optimizing-brainfuck.html)提到以下最佳化策略:

* 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