2016q3 Homework jit-compiler
===
contributed by <`kaizsv`>

## 閱讀資料
[廖健富](https://hackpad.com/2015q3-Homework-4B-5I46HyqOCGJ#:h=DynASM)同學的筆記紀錄了 DynAsm 及 Compiler, Interpreter, JIT的差異。

詳細閱讀[第三方 DynAsm 教學](http://corsix.github.io/dynasm-doc/tutorial.html)及[所有 DynAsm 指令](http://corsix.github.io/dynasm-doc/instructions.html#instructions)，試著找出作業可能會用到的指令。

## jit-x64 優化
參考[我去年的筆記](https://embedded2015.hackpad.com/Homework-4-B-Jm6jxbaiz3z)，[去年的github](https://github.com/kaizsv/jit-construct)這次只做2種優化。原本的數據如下。
|prog|ms|
|-|-|
|awib.b|93.7|
|mandelbrot.b|4059.5|
|hanoi.b|10017.6|
### 縮減連續的 `< > - +`
|prog|ms|
|-|-|
|awib.b|52.0|
|mandelbrot.b|1324.2|
|hanoi.b|4946.2|

int contraction(char **p)
{
	char target = **p;
	int offset = 1;

	(*p)++;

	// ignore character that is not brainfuck operator
	while (**p == target || !strchr("<>,.+-[]", **p)) {
		offset = (**p == target) ? offset + 1 : offset;
		(*p)++;
	}

	(*p)--;

	return offset;
}

除了找連續的`< > - +`外，原始碼可能存在 brainfuck operator 之外的字元，例如空白鍵，因此這裡多了一個`strchr()`的判斷忽略 brainfuck 以外的 operator。跟原始版比起來大約提升了 1倍。

### clear loop pattern `[-]`
|prog|ms|
|-|-|
|awib.b|43.2|
|mandelbrot.b|1292.5|
|hanoi.b|139.5|

int clear_loop(char *p)
{
	return (*(p+1) == '-' && *(p+2) == ']');
}

尋找簡單的 clear loop pattern `[-]`， 直接把該位置設成 0，在`hanoi.b`優化的較明顯，大約提升了 70 倍。

去年還有做其它的 pattern 有進一步的效能提升，這次把重心放在 concurrency / parallelism。

## concurrency / parallelism
我寫不出來，紀錄下我看不懂的地方。
### bukkake - parallel brainfuck
先看[bukkake.c](https://bitbucket.org/wjmelements/bukkake/src/999bdd74c0eb700ce9abe22011d31d425eeb0651/bukkake.c?at=master&fileviewer=file-view-default)，它多加了三個運算子。

* `*`: 會呼叫`threadpool_spawn`在 thread pool 產生一個 thread
* `\n`: 會呼叫到`bu_close` `bu_exit`，但還看不懂實際的作用，官網的解釋為離開 thread
* `|`: barrier 帶有一個 mutex lock，可以 block 住目前的 thread 直到所有 thread 完成

for (pc = 0; pc < filestatus.st_size; pc++) {
    if (exec[pc] == '\n') {
        num_rows++;
        column = 0;
        continue;
    } else if (num_rows == 0 && exec[pc] == '*') {
        has_spawns = 1;
    }
    column += 1;
    if (column > longest_row) {
         longest_row = column;
    }
}

JIT 會先對檔案做前處理，先