2016q3 Homework5 (jit-compiler)

contributed by <0140454>, <linachiu>
GitHub: jit-construct

作業要求

A09: jit-compiler

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 提到以下最佳化策略:

• 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。
  ​​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 如下。
  ​​DASM_FDEF void dasm_growpc(Dst_DECL, unsigned int maxpc);
  

  設定完成後我們可以利用 =>pc 來表示某個 label，可使用的範圍是 =>0 到 =>(maxpc-1)。

編譯產生的 jit-x64.h

• dasm_put() 函數
  其 function protoyype 如下。
  ​​DASM_FDEF void dasm_put(Dst_DECL, int start, ...);
  

  代表從 action list 中 index 為 start 的地方開始讀取指令，直到 DASM_STOP (255) 為止。

效能分析

原始版本

$ 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

統計 +、-、< 和 > 這類指令的連續個數，一次處理完，不像原本的版本是每遇到一個就輸出一次。

$ 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 的程式碼如下。

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);
}

接下來是改善後的效能。

$ 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
• The Unofficial DynASM Documentation