November 04, 2009

打造 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
迴響

文中提到的 bf2c.awk 語法 sed 吧. 不是 awk
( http://en.wikipedia.org/wiki/AWK )

whoami 發表於 November 4, 2009 04:48 PM

@whoami

已修正,謝謝。AWK 的版本是後續文章要探討的 :)

jserv 發表於 November 4, 2009 07:08 PM

這個語言真有趣@_@

MGdesigner 發表於 November 4, 2009 07:51 PM

有意思的語言, 不過這語言真是如其名啊 看到令人頭昏

cphacker 發表於 November 4, 2009 11:15 PM
發表迴響









記住我的資訊?