# A09: jit-compiler

## 預期目標

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

由於我之前有做過這個作業的 pattern 優化了，所以這次重心放在 parallel 和 concurrency

>>中英文字間請以空白隔開
>>[color=red][name=課程助教]

## JIT
- Phase 1: create machine code at program run-time.
- Phase 2: execute that machine code, also at program run-time.

看了一點參考[1]和參考[2]，JIT 是先把目標程式碼(e.g. brainf*ck)編譯成 machine code 後，再放入程式記憶體執行，再這次的作業中，使用的是 JIT 是 Dynasm 。
這邊貼出參考[1]裡的部份程式碼

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>


// Allocates RWX memory of given size and returns a pointer to it. On failure,
// prints out the error and returns NULL.
void* alloc_executable_memory(size_t size) {
  void* ptr = mmap(0, size,
                   PROT_READ | PROT_WRITE | PROT_EXEC,
                   MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
  if (ptr == (void*)-1) {
    perror("mmap");
    return NULL;
  }
  return ptr;
}

void emit_code_into_memory(unsigned char* m) {
  unsigned char code[] = {
    0x48, 0x89, 0xf8,                   // mov %rdi, %rax
    0x48, 0x83, 0xc0, 0x04,             // add $4, %rax
    0xc3                                // ret
  };
  memcpy(m, code, sizeof(code));
}

const size_t SIZE = 1024;
typedef long (*JittedFunc)(long);

// Allocates RWX memory directly.
void run_from_rwx() {
  void* m = alloc_executable_memory(SIZE);
  emit_code_into_memory(m);

  JittedFunc func = m;
  int result = func(2);
  printf("result = %d\n", result);
}

在上面的程式碼當中，需要先產生可讀可寫可執行的記憶體(藉由mmap搭配一些指定的flag)，接下來將編譯好的機械碼(這邊省略編譯的步驟)複製到之前產生的記憶體空間裡，這樣一來，這裡的機械碼就可以被執行囉！

最後將指定 function 到記憶體的位址( function pointer 概念)，就可以被呼叫來執行。

## 編譯與測試

在 clone 下來之後嘗試 make，不過少了幾個套件，先安裝好再說

lua dynasm/dynasm.lua -o jit-x86.h jit-x86.dasc
make: lua: Command not found
make: *** [jit-x86.h] Error 127

需要先安裝lua

Package lua is a virtual package provided by:
  lua5.1:i386 5.1.5-5ubuntu0.1
  lua5.1 5.1.5-5ubuntu0.1
  lua5.2:i386 5.2.3-1
  lua50 5.0.3-7
  lua5.2 5.2.3-1
You should explicitly select one to install.

選擇安裝5.2

jit-x86.dasc:4: error: cannot load module:
dynasm/dasm_x86.lua:31: module 'bit' not found

安裝lua-bitop

/usr/include/features.h:374:25: fatal error: 
sys/cdefs.h: No such file or directory

安裝libc6-dev-i386

make: arm-linux-gnueabihf-gcc: Command not found

最後一個了，安裝gcc-arm-linux-gnueabihf
終於OK啦！

### 第一次測試
由於我的電腦是64bit的系統，那就跑 ==make bench-jit-x64== 吧

Executing Brainf*ck benchmark suite. Be patient.

progs/awib.b            GOOD	73.1ms
progs/mandelbrot.b      GOOD	3025.4ms
progs/hanoi.b           GOOD	7669.4ms

## 特定pattern 優化
## Concurrency
因為interpreter支援brainfuck平行化是最好寫的，所以打算先從interpreter開始著手
### interpreter的concurrency
目前想讓inerpreter版本支援concurrency，這樣我們就必須先定義一些符號來產生thread,中止thread以及同步

==*== : 創造一個 thread ，採用類似 clone 的方式，會複製 main thread 的 tape，並開始執行後面的運算直到碰到 ==&==
==&== ： 取諧音 end，用來表示 thread 結束位置
==|== : 等待 thread 執行完畢，用來同步

紀錄一下，在 coding 過程中，其中有個部份如下面的寫法一樣

case '*':       // create a thread
    pthread_t threadid;

在編譯的時候遇到下列 error

a label can only be part of a statement and a declaration is not a statement

在C語言裡，接在 label 後面的第一行程式碼必須是statement ，而 declaration 不算是 statement，因此編譯器不給過，那我們可以加一個 empty statement 在 declaration 前面就可以了

case '*':       // create a thread
    {}
    pthread_t threadid;

> 不過後來我已經捨棄這種寫法[name=林哲亘]
### 範例

++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.*<<+++++++++++++++.>.+++.------.--------.>+.>.&|

以 helloworld 作為例子，在 main thread 執行完 ==Hello== 的輸出後，關鍵在於後面的*符號，我們的 C interprter 在直譯到這個地方時，會使用 pthread_create() 來產生新的執行緒，新的執行緒一樣會繼續直譯 brainf*ck 程式碼，而原本的執行緒會跳到&符號的位置，再繼續直譯。

回到剛剛 helloworld 的例子，產生的 thread 用來輸出後半段的 ==world！== ，這時候的原本的 thread 直譯到了|符號，這個用來等待產生出來的執行緒結束(利用pthread_join())，才會繼續，而 helloworld 的例子則是因為後面沒有其他的程式碼，因此直接結束。

特別一題的是我採用的是用 C clone 的概念去產生 thread，也就是說，會複製原本的 tape 讓新生的 thread 去使用，等同於共享到創造 thread 之前的變數( tape )，但是 thread 的 pc 則是一樣的，換句話說，thread 是從被創造的那一個指令接續之後的動作，不像 pthread 產生新的 thread 後，會跳到其他的 function 位置後才繼續執行。

目前不支援 thread 裡面又創造一個新的 thread，在直譯的時候會跳出 error message

## Reference
1. http://eli.thegreenplace.net/2013/11/05/how-to-jit-an-introduction
2. http://blog.reverberate.org/2012/12/hello-jit-world-joy-of-simple-jits.html