---
tags: sysprog21-hw, 0140454, linachiu
---
# 2016q3 Homework5 (jit-compiler)
contributed by <`0140454`>, <`linachiu`>
GitHub: [jit-construct](https://github.com/0140454/jit-construct)
## 作業要求
[A09: jit-compiler](https://hackmd.io/s/SJ7AZJv1e#作業要求)
## Brainfuck 程式語言
### 打造 Brainfuck 的 JIT compiler
Brainfuck 是種極為精簡的程式語言，由 Urban Müller 在 1993 年發展。Urban Müller 當初的目標為提出一種簡單的、可用最小的編譯器來實現、符合 Turing complete 的程式。
最早在 Amiga 機器上撰寫的編譯器只有 240 bytes 的大小，而 Brian Raiter 在 1999 年甚至於 i386/Linux 機器上做出僅需 166 bytes 的 Brainfuck 編譯器。
Brainfuck 僅有八個指令，其中兩個是 I/O 動作。作為 Turing machine 的實踐，Brainfuck 對記憶體單元作直接的存取，對應到 C 語言的概念來說，如果 char *p 指向記憶體區塊的話，Brainfuck 語言的八個指令可對照為以下： (Brainfuck vs. C)
```
Brainfuck C
> ++p;
< --p;
+ ++*p;
- --*p;
. putchar(*p);
, *p = getchar();
[ while (*p) {
] }
```
```
> : 將資料指標往右移
< : 將資料指標往左移
+ : 將資料指標所在位置的資料加 1
- : 將資料指標所在位置的資料減 1
. : 輸出資料指標所在位置的資料
, : 讀入資料並存到指標所在位置
[ : 如果資料指標所在位置的資料為 0，則指令指標跳至往後對應的 `]` 後一條指令
] : 如果資料指標所在位置的資料不為 0，則指令跳至往前對應的 `[` 後一條指令
```
也就是說，下方的 Brainfuck 程式碼：
```
+++++[-]
```
對應為 C 語言程式碼為：
```
*p=+5;
while(*p != 0){
*p--;
}
```
接著我們就來探討要如何改善此Complier，在此語言上因為極其簡易，因此許多的運算是累贅的，例如乘法、初始值等，又或是迴圈的使用，因為 Brainfuck 的迴圈終止都是仰賴 Array[0] 來判斷，在 Index 的運算上其實會有很多的不必要。
在 [brainfuck optimization strategies](http://calmerthanyouare.org/2015/01/07/optimizing-brainfuck.html) 提到以下最佳化策略:
* Contraction
* Clear loops
* Copy loops
* Multiplication loops
* Operation offsets
* Scan loops
### DynASM
**簡介**
DynASM 原本是為了 LuaJIT 所開發的，但如果有開發其他語言的 JIT compiler 的需求，也是可以使用的。
它是一個 Dynamic Assembler，主要分為兩個部份，preprocessor 與 tiny runtime。概觀如下。
在 `.dasc` 中會夾雜著 C code 以及組合語言，preprocessor 會依據特定語法來處理這種類型的檔案，把其中的組合語言轉換成 DynASM 內建的 method 型式，如 `dasm_put()` 等。
經過 preprocessor 產生 `.h` 檔案與其他檔案 (含 tiny runtime) 一同編譯，便可以獲得自己的 JIT compiler。
接下來，我們會觀看作業中的檔案內容並嘗試了解 DynASM 的語法。
**jit-x64.dasc**
* `|` 開頭
表示這一行會被 preprocessor 做處理，後面可以接 DynASM directives 或者是組合語言。
* `|.arch x64`
指定所使用的架構。
* `|.actionlist action`
讓 preprocessor 產生類似下面的 C code。
這個 directive 在 `.dasc` 檔案中==只能出現一次==，裏面存放著是 DynADM 會使用到的 assembly。
```clike=
static const unsigned char ident[] = {
/* ... */
};
```
* `|.define PTR, rbx`
有點像 C 中的 `#define PTR rbx`。
* `|.macro ...`
讓我們定義一個巨集函數，原始的定義如下。
在這中間也可以放 C/C++ 的程式碼，但必須以 `||` 開頭。
```
| .macro name [, param1 [, param2 [, ...]]]
| /* ... */
| .endmacro
```
* `dasm_growpc()` 函數
在 DynASM 我們可能會需要用到 label 才能實現跳躍的操作，所以我們必須透過這個函數來設定可以使用的 label 數量。其 function prototype 如下。
```clike=
DASM_FDEF void dasm_growpc(Dst_DECL, unsigned int maxpc);
```
設定完成後我們可以利用 `=>pc` 來表示某個 label，可使用的範圍是 `=>0` 到 `=>(maxpc-1)`。
**編譯產生的 jit-x64.h**
* `dasm_put()` 函數
其 function protoyype 如下。
```clike=
DASM_FDEF void dasm_put(Dst_DECL, int start, ...);
```
代表從 action list 中 index 為 start 的地方開始讀取指令，直到 DASM_STOP (255) 為止。
## 效能分析
### 原始版本
```shell=
$ make bench-jit-x64
Executing Brainf*ck benchmark suite. Be patient.
progs/awib.b GOOD 78.7ms
progs/mandelbrot.b GOOD 3252.2ms
progs/hanoi.b GOOD 8158.6ms
```
### 優化版本
**Contraction**
統計 `+`、`-`、`<` 和 `>` 這類指令的連續個數，一次處理完，不像原本的版本是每遇到一個就輸出一次。
```shell=
$ make bench-jit-x64
Executing Brainf*ck benchmark suite. Be patient.
progs/awib.b GOOD 45.9ms
progs/mandelbrot.b GOOD 1071.1ms
progs/hanoi.b GOOD 4173.3ms
```
**Loop 相關**
Loop 的部份主要分為 clear loop、copy loop、multiplication loop 以及 scan loop。接下來將針對這些 loop 進行分析。
* Clear loop
在 Brainfuck 中如果要清除 ptr 中的值必須寫成 `[-]`，讓 ptr 每次減一直到變成零，但在實際執行的時候我們可以利用 `mov` 指令直接把他歸零就好。
Pattern: `[-]`
* Copy loop
將 ptr 的值加到其他的位置上面。例如 `[->+>+<<]` 就是把 ptr 的值加到它的下一個位置跟下下一個位置。
Pattern: `[(減法) ((位移)(加法 | 減法)) (位移)]`
* Multiplication loop
對其他位置加上 ptr 次的某個值。例如 `[->+++<]` 就是把下一個位置作 ptr 次的加三。
從觀察中可以發現，其實 copy loop 就是 multiplication loop 的一個集合而已，所以在優化時可以直接考慮 multiplication loop 就好。
Pattern: `[(減法) ((位移)(加法 | 減法)) (位移)]`
* Scan loop
主要的工作是移動 ptr 直到遇見 0 為止。
Pattern: `[(位移)]`
再來，我們先來優化前三個 loop 看看成效如何。
根據 pattern 來看，我們所要優化的目標在遇到 `[` 時，下一個一定是 `-` 才對。因此我們可以透過這個條件來確定我們是否要優化。
檢查 loop 的程式碼如下。
```clike=
typedef struct _LOOP_OPT_INFO {
int total_offset;
int count;
int offset[256];
int mul_value[256];
} loop_opt_info_t;
int check_loop(char *p, loop_opt_info_t *info)
{
int count = 0, offset = 0;
info->count = 0;
info->total_offset = 2;
if (*(p + 1) != '-') {
return 0;
}
p += 2;
while (*p != ']') {
if (*p != '+' && *p != '<' && *p != '>') {
return 0;
}
count = continuous_count(p);
if (*p == '+') {
info->offset[info->count] = offset;
info->mul_value[info->count++] = count;
} else if (*p == '<') {
offset -= count;
} else if (*p == '>') {
offset += count;
}
info->total_offset += count;
p += count;
}
++info->total_offset;
return (offset == 0);
}
```
接下來是改善後的效能。
```shell=
$ make bench-jit-x64
Executing Brainf*ck benchmark suite. Be patient.
progs/awib.b GOOD 30.1ms
progs/mandelbrot.b GOOD 1181.9ms
progs/hanoi.b GOOD 73.1ms
```
## 參考資料
* [廖健富學長 hackpad](https://hackpad.com/2015q3-Homework-4B-5I46HyqOCGJ#:h=Jit-construct)
* [The Unofficial DynASM Documentation](http://corsix.github.io/dynasm-doc/reference.html)
Sign in with Wallet
Connect another wallet