Jserv's blog

打造 Brainfuck 的 JIT compiler

Brainfuck 是種極為精簡的程式語言，由 Urban Müller 在 1993 年發展。Urban Müller 當初的目標為提出一種簡單的、可用最小的編譯器來實現、符合 Turing complete 的程式。最早在 Amiga 機器上撰寫的編譯器只有 240 bytes 的大小，而 Brian Raiter 在 1999 年甚至於 i386/Linux 機器上做出僅需 166 bytes 的 Brainfuck 編譯器，詳情可見 [bf.asm]。

既然 Brainfuck 是符合 Turing complete 的程式語言，理論上可進行任何運算動作，可查看 Wikipedia 的 [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) {
]	}

也就是說，下方的 Brainfuck 程式碼：

+++++[-]

對應為 C 語言程式碼為：

     *p=+5;
     while(*p != 0){
          *p--;
     }

體解「知易行難」的 Brainfuck，最好還是多練習，可搭配 [Brainfuck JS (interpreter & debugger)] 這強大的互動環境。

撰寫 Branfuck 編譯器是相當容易的，比方說，如果我們將 C 語言當作是 Brainfuck 的組合語言碼輸出 (事實上 LLVM 也有 C backend)，那麼這動作就如上述的對應表一般，可一對一轉換，只要用 sed 一類的工具即可達到，以下是一個簡單的實做： [bf2c.sed]

#! /bin/sed -f
s/[^][+<>.,-]//g
s/\([-+]\)/\1\1*p;/g
s/</p--;/g
s/>/p++;/g
s/\./putchar(*p);/g
s/,/*p=getchar();/g
s/\[/while (*p) {/g
s/\]/}/g
1s/^/#include <stdio.h>\
int main(void){char *p=calloc(1,10000);/
$s/$/}/

Wikipedia 上那個經典的 Brainfuck 版本的 Hello World 程式 (需要留意的是，在 Brainfuck 中，寫一個 UNIX "cat" 工具程式，遠比寫 Hello World 簡單)：

++++++++++[>+++++++>++++++++++>+++>+<<<<-]
>++.>+.+++++++..+++.>++.<<+++++++++++++++.
>.+++.------.--------.>+.>.

就得到以下的「編譯」結果：

#include <stdio.h> int main(void){char *p=calloc(1,10000); ++*p;++*p;++*p;++*p;++*p;++*p;++*p;++*p;++*p;++*p; while (*p) {p++;++*p;++*p;++*p;++*p;++*p;++*p;++*p; p++;++*p;++*p;++*p;++*p;++*p;++*p;++*p;++*p;++*p;++*p; p++;++*p;++*p;++*p;p++;++*p;p--;p--;p--;p--;--*p;} p++;++*p;++*p;putchar(*p);p++;++*p;putchar(*p);++*p; ++*p;++*p;++*p;++*p;++*p;++*p;putchar(*p);putchar(*p); ++*p;++*p;++*p;putchar(*p);p++;++*p;++*p;putchar(*p); p--;p--;++*p;++*p;++*p;++*p;++*p;++*p;++*p;++*p;++*p; ++*p;++*p;++*p;++*p;++*p;++*p;putchar(*p);p++;putchar(*p); ++*p;++*p;++*p;putchar(*p); --*p;--*p;--*p;--*p;--*p;--*p;putchar(*p); --*p;--*p;--*p;--*p;--*p;--*p;--*p;--*p;putchar(*p); p++;++*p;putchar(*p);p++;putchar(*p);}

當然，編譯器不是查表對照而已，還得涉及到 relocation 與 optimization 的議題，這些稍候筆者再來討論。稍早筆者介紹過 [AsmJit : C++ 封裝的 Just-In-Time Assembler] 後，大鳥就做了一個 [JustFuck, A x86 Just-In-Time Compiler for Brainfuck]，透過執行時期的行為，一邊分析 Brainfuck 的八個指令，一邊動態產生對應的機械碼，這真是個很不錯的範例實做

除了 [AsmJit]，使用 [Xbyak] (New BSD License) 也是相當好的選擇，可快速以此 x86 / x86_64 JIT assembler 實現 Brainfuck 語言的 Just-in-Time compiler。以下是一個具體的 Brainfuck JIT 實做，適用的平台是 x86/Linux： (完整的套件在 [bfjit-x86.tar.bz2])

#include "xbyak/xbyak.h"
#include <stdio.h>

#include <stdlib.h>
#include <stdint.h>
#include <stack>
#include <fstream>

class Brainfuck : public Xbyak::CodeGenerator {
private:
    enum Direction { B, F };
    const char *toStr(int labelNo, Direction dir) {
        static char num[64];
        snprintf(num, sizeof(num), "%c%d", dir == B ? 'B' : 'F', labelNo);
        return num;
    }

public:
    int getContinuousChar(std::istream& is, char c) {
        int count = 1;
        char p;
        while (is >> p) {
            if (p != c) break;
            count++;
        }
        is.unget();
        return count;
    }
    Brainfuck(std::istream& is) : CodeGenerator(50000) {
        using namespace Xbyak;
        const Reg32& pPutchar(esi);
        const Reg32& pGetchar(edi);
        const Reg32& stack(ebp);
        const Address cur = dword [stack];
        push(ebp); // stack
        push(esi);
        push(edi);
        const int _P = 4 * 3;
        mov(pPutchar, ptr[esp + _P + 4]); // putchar
        mov(pGetchar, ptr[esp + _P + 8]); // getchar
        mov(stack, ptr[esp + _P + 12]); // stack
        int labelNo = 0;
        std::stack<int> keepLabelNo;
        char c;
        while (is >> c) {
            switch (c) {
            case '+':
            case '-':
                {
                    int count = getContinuousChar(is, c);
                    if (count == 1) {
                        c == '+' ? inc(cur) : dec(cur);
                    } else {
                        add(cur, (c == '+' ? count : -count));
                    }
                }
                break;
            case '>':
            case '<':
                {
                    int count = getContinuousChar(is, c);
                    add(stack, 4 * (c == '>' ? count : -count));
                }
                break;
            case '.':
                push(cur);
                call(pPutchar);
                pop(eax);
                break;
            case ',':
                call(pGetchar);
                mov(cur, eax);
                break;
            case '[':
                L(toStr(labelNo, B));
                mov(eax, cur);
                test(eax, eax);
                jz(toStr(labelNo, F), T_NEAR);
                keepLabelNo.push(labelNo++);
                break;
            case ']':
                {
                    int no = keepLabelNo.top(); keepLabelNo.pop();
                    jmp(toStr(no, B));
                    L(toStr(no, F));
                }
                break;
            default:
                break;
            }
        }
        pop(edi);
        pop(esi);
        pop(ebp);
        ret();
    }
};

int main(int argc, char *argv[])
{
    if (argc == 1) {
        fprintf(stderr, "bf filename.bf [0|1]\n");
        return 1;
    }
    std::ifstream ifs(argv[1]);
    Brainfuck bf(ifs);
    static int stack[32768];
    ((void (*)(void*, void*, int *)) bf.getCode())(
               (void *) putchar, (void *) getchar, stack
    );
    return 0;
}

額外打上以下的 patch，可得知 JIT compiler 輸出的 x86 機械碼：

--- bfjit.cpp	2009-11-04 07:44:18.000000000 +0800
+++ bfjit-dump.cpp	2009-11-04 07:50:07.000000000 +0800
@@ -94,6 +94,31 @@ public:
     }
 };

+void dump(const uint8_t *code, size_t size)
+{
+    puts("#include <stdio.h>\n"
+            "static int stack[32768];\n"
+            "static const unsigned char code[] = {");
+    for (size_t i = 0; i < size; i++) {
+        printf("0x%02x,", code[i]); if ((i % 16) == 15) putchar('\n');
+    }
+    puts("\n};");
+#ifdef __linux__
+    puts("#include <unistd.h>");
+    puts("#include <sys/mman.h>");
+#endif
+    puts("main()\n{");
+#ifdef __linux__
+    puts("\tlong pageSize = sysconf(_SC_PAGESIZE) - 1;");
+    puts("\tmprotect((void*)code, (sizeof(code) + pageSize) & ~pageSize, PROT_READ | PROT_EXEC);");
+#endif
+    puts(
+            "\t((void (*)(void*, void*, int *))code)("
+            "\t\t(void*)putchar, (void*)getchar, stack);\n"
+            "}"
+        );
+}
+
 int main(int argc, char *argv[])
 {
     if (argc == 1) {
@@ -101,10 +126,16 @@ int main(int argc, char *argv[])
         return 1;
     }
     std::ifstream ifs(argv[1]);
+    int mode = argc == 3 ? atoi(argv[2]) : 0;
     Brainfuck bf(ifs);
-    static int stack[32768];
-    ((void (*)(void*, void*, int *)) bf.getCode())(
-               (void *) putchar, (void *) getchar, stack
-    );
+    if (mode == 0) {
+        static int stack[32768];
+        ((void (*)(void*, void*, int *)) bf.getCode())(
+                   (void *) putchar, (void *) getchar, stack
+        );
+    } else {
+        dump(bf.getCode(), bf.getSize());
+    }
     return 0;
 }
+

其實，Brainfuck 與其說是程式語言，不如說是一種硬體架構的實現 (Turing machine)，知名的編譯器開發計畫 [LLVM] 也包含一個 Brainfuck 的範例，作為一個 front-end，掛入 LLVM IR (中間表示)，進而與 LLVM 豐富的編譯器元件作整合。
由 jserv 發表於 November 4, 2009 09:30 AM