Blog Dice

Mugo, a toy compiler for a subset of Go that can compile itself

Ben Hoyt

Mugo：一個能編譯自身的 Go 子集玩具編譯器

原文由 Ben Hoyt 于 發布，訂閱此部落格

摘要：本文介紹 Mugo，一個針對 Go 程式語言極小子集的單遍編譯器。它會產生（非常陽春的）x86-64 組合語言，且支援的語言功能剛好足夠用來實作 Mugo 編譯器本身：int 與 string 型別、切片、函式、區域變數、全域變數，以及基本的運算式與陳述式。

自從開始寫程式以來，我就一直對編譯器深深著迷。我的第一批程式專案之一是「Third」，一個跑在 8086 DOS 上的自舉 Forth 編譯器。Forth 極其容易編譯：它沒有運算式或陳述式，每個用空白分隔的語彙都會直接被編譯成一個呼叫指令——通常是透過像是direct threading這類技巧。

像 C 和 Go 這類典型的語言，語法更為複雜，包含運算式與陳述式，因此需要真正的語法分析器與程式碼產生器。這些語言的編譯器通常既複雜又強大，但如我們接下來會看到的，如果只堅持使用基本型別並產生未經最佳化的輸出，仍然可以寫出一個簡單的編譯器。

Mugo 有點承襲了 Fabrice Bellard 的Obfuscated Tiny C Compiler 的精神，不過我的當然平淡無奇得多，短期內也沒機會贏得 IOCCC。Bellard 的編譯器只實作了剛好足夠把自身編譯成原生 i386 Linux 執行檔的 C 語言子集。

我想用 Go 做點類似的事，只是去掉混淆的部分。這個點子一開始只是洗澡時的靈光一現：「到底 Go 最小的哪個子集就能編譯它自己呢？」Fabrice 的 C 編譯器是用 2048 位元組經過混淆的 C 寫成的，而我的則是 1600 行經過排版的 Go。

雖然這是在一個長週末完成的趣味習作，但它徹頭徹尾就是個玩具——它捨棄了 Go 所有優秀的特性：使用者自訂型別、介面、goroutine、channel、map、垃圾回收，甚至連邊界檢查都沒有！我做 Mugo 的目標是教育性的：對我自己是如此，希望對你也是。做這類練習有助於揭開我們工具運作原理的神祕面紗。

要用哪個 Go 子集？

Mugo 是 Go 的一個子集，所以原始碼既可以用 Go 編譯，也可以用 Mugo 自己來編譯。在我看來，這讓它有趣得多。這也讓測試變得更容易：當 Go 編譯出來的版本所產生的組合語言輸出，與 Mugo 編譯出來的版本完全相同時，我就知道它成功了——當 diff mugo2.asm mugo3.asm 沒有任何輸出時，那真是美妙的一刻！

在動手之前，我反覆思索該納入哪些功能子集。我知道我會需要某種容器型別來儲存編譯器狀態：例如變數的名稱與型別，以及函式的簽章與回傳型別。但要用哪種容器呢？

Go 有指標，而且比 C 的指標安全，但也遠沒有那麼強大，因為你不能做指標運算。Bellard 的編譯器大量運用 C 指標，但在 Go 裡這招行不通。

那 struct 或 map 呢？嗯，那些實作起來會更複雜，而且也無法真正解決最常見的儲存清單需求。所以我決定這些都可以不要，只要有切片就夠了。

以下是 Mugo 支援的功能：

  • int 型別、十進位整數常值、字元常數，以及大多數作用於 int 的運算式：+、-、*、/、%、==、!=、<、<=、> 和 >=，運算子優先順序比照 Go 辦理。編譯器能辨識型別名稱 bool，但將其視為與 int 完全相同（&&、|| 與 ! 作用於這些擬布林值上）。
  • string 型別，包含支援 \ 跳脫的字串常數、使用 == 或 != 的字串相等性測試、使用 + 的字串串接，以及 len()。
  • 切片，但僅限 []int 與 []string。不支援切片字面量與 make()，所以要建立切片，必須先建立一個空切片再用 append 附加。支援讀取與指派切片元素，也支援 slice[:n] 運算式與 len()。
  • 有做型別檢查，但並不完整。我只在覺得合理或有助於除錯的地方檢查型別，但絕非面面俱到。
  • 陳述式：if 與 else、for condition { ... }、return，以及 Go 的 := 短變數宣告。
  • 變數與常數。不過，var 與 const 僅在頂層支援；區域變數必須使用 :=（反正在 Go 中這本來就比較常見）。僅支援具型別的整數常數。
  • 頂層函式，包含遞迴。不過，不支援函式值與匿名函式。函式只能有單一回傳值，也不包含可變參數函式。
  • I/O，使用三個預先定義的函式：getc 從 stdin 讀取單一字元，print 與 log 分別將字串寫至 stdout 與 stderr。
  • Go 語法，但精簡到僅保留此處所需的部份。許多結構都不支援，例如 ++ 與 --、for range 迴圈等等。支援以 // 開頭的單行註解。

大概就是這樣了！如果上面清單沒提到，那大概就是沒支援。就像我說的，是個很小的子集。

在打造它的過程中，我多次參考了精簡扼要的Go 語言規格，雖然我幾乎肯定有些地方還是弄錯了。不過，已實作的部分運作起來確實像 Go，這點從我的「diff 測試」就能看出來。

程式碼產生

Mugo 是一個單遍編譯器，在語法分析的過程中就直接輸出 x86-64 組合語言。（它是為 Linux 撰寫的，但在 macOS 或 Windows 上讓它跑起來應該也不難。）它沒有在記憶體中建立抽象語法樹——反正只靠切片要建立那種結構本來就很棘手。

它也非常陽春。完全沒有最佳化——我基本上是把強大的暫存器架構 CPU 當成笨拙的堆疊機器來用，把中間值 push、pop 到堆疊上。真正的編譯器大概有一半的複雜度在程式碼產生上——另一半則在型別檢查——而這兩者在 Mugo 中都被極度簡化了。

我必須耍的一個小技巧是處理區域變數宣告（使用 Go 的 := 語法）。因為只有一遍，你要到解析完整個函式後，才會知道會有多少區域變數以及它們的型別。所以我的函式前置程式碼（prologue），除了常見的 rbp 框架指標操作外，還會從堆疊指標減去 64 位元組，為最多 8 個區域變數的儲存格（cell）預留空間（Mugo 中用得最多的函式用了 7 個儲存格）。

更新：Hacker News 上的「a1369209993」指出，我其實可以參照一個在函式結尾、已知大小後才定義的組譯器常數。我在 if 與 else 的向前跳躍中已經是讓組譯器這樣處理了。感謝指正！

以下是整數 add 函式的完整輸出：

; func add(x int, y int) int {
;     return x + y
; }

; function prologue
add:
push rbp             ; rbp is the frame pointer
mov rbp, rsp
sub rsp, 64          ; make space for any more locals
                     ; (not used by this function)

; fetch and push local variable x, then y
push qword [rbp+24]
push qword [rbp+16]

; the + operation
pop rbx
pop rax
add rax, rbx
push rax

; pop result back into rax for "return"
pop rax

; function epilogue (restore stack and frame pointer)
mov rsp, rbp
pop rbp
ret 16              ; return, and free space due to
                    ; caller pushing x and y

跟 gcc 的未最佳化輸出相比，我們的表現還不算太差：

push    rbp
mov     rbp, rsp
mov     qword [rbp-8], rdi
mov     qword [rbp-16], rsi
mov     rdx, qword [rbp-8]
mov     rax, qword [rbp-16]
add     rax, rdx
pop     rbp
ret

不過，gcc 的最佳化後輸出只產生了一條基於暫存器的指令：

lea     rax, [rdi+rsi]
ret

在呼叫端，為了產生對 add 的呼叫，Mugo 會產生以下程式碼：

; add(1, 2)

push qword 1  ; push first arg
push qword 2  ; push second arg
call add      ; call the function
push rax      ; push return value back to stack

如你所見，Mugo 使用了自己那套非常沒有效率的ABI，與x86-64 ABI 完全不同——標準的 ABI 會把前六個「儲存格」（64 位元值）放在暫存器中。

為了簡單起見，Mugo 的 ABI 把參數推到堆疊上。它們是依序推入的，所以在記憶體中最終會以相反的順序出現在堆疊上。不過，Mugo 在回傳值上倒是會使用暫存器：rax，若有更多儲存格則依序使用 rbx 與 rcx。就跟 Go 一樣，int 佔一個儲存格，string 佔兩個（位址與長度），而切片則佔三個（位址、長度與容量）。

對於字串串接與切片附加所需的記憶體配置，Mugo 使用了一個極簡的「bump allocator」。換句話說，它只是在一塊固定 1MB 的記憶體區塊中不斷推進指標，若用完就顯示記憶體不足的訊息並結束。它從不釋放記憶體，也沒有垃圾回收。非常適合短時間執行的程式！

為了產生組合語言，Mugo 只是呼叫 print 將內容寫到標準輸出：

func genFuncStart(name string) {
    print("\n")
    print(name + ":\n")
    print("push rbp\n")
    print("mov rbp, rsp\n")
    print("sub rsp, " + itoa(localSpace) + "\n") // space for locals
}

Mugo 執行完畢後，我使用NASM 來組譯輸出，再用ld 連結器來建置執行檔。以下是Makefile 中的一個範例，展示我如何建置編譯器的三個版本：

# Build the compiler with Go
mugo:
    go build -o build/mugo

# Build the compiler with the Go-built Mugo
mugo2:
    build/mugo <mugo.go >build/mugo2.asm
    nasm -felf64 -o build/mugo2.o build/mugo2.asm
    ld -o build/mugo2 build/mugo2.o

# Build the compiler with the Mugo-built Mugo
mugo3:
    build/mugo2 <mugo.go >build/mugo3.asm
    nasm -felf64 -o build/mugo3.o build/mugo3.asm
    ld -o build/mugo3 build/mugo3.o
    diff build/mugo2.asm build/mugo3.asm  # ensure output matches!

還有一個 make 目標，會透過一個讓編譯器編譯自身的簡單測試來產生涵蓋率報告。這個測試只是呼叫 Mugo 的 main()，所以我們在開啟涵蓋率分析的情況下執行測試執行檔，並將 mugo.go 送進該行程的標準輸入。這個「測試」就是編譯編譯器本身的完整原始碼，並記錄我們得到的涵蓋率：

coverage:
    go test -c -o build/mugo_test -cover
    build/mugo_test -test.coverprofile build/coverage.out \
        <mugo.go >/dev/null
    go tool cover -html build/coverage.out -o build/coverage.html

一開始我加入了幾個編譯器本身沒用到的功能，所以它們沒有被測試到，在涵蓋率報告中顯示為紅色。除了像 ! not 運算子與字串切片指派這類基於一致性而保留的少數功能外，我把未使用的功能都移除了。現在除了錯誤處理之外，所有功能都有完整的涵蓋率。

有一兩次我得搬出 gdb 來除錯。我的 x86 組合語言技巧確實已經生疏，而且我從未寫過像樣的 64 位元組合語言。我確定即使在單遍的限制下，輸出仍有許多可以改進的地方——不過那些改進就留給讀者當作練習吧。:-)

詞法分析器與語法分析器

Go 擁有簡潔優美的語法，很容易做語彙分割與語法分析。Mugo 的詞法分析器只使用單一字元的前瞻（lookahead），並搭配典型的遞迴下降語法分析器。

詞法分析器基本上就是一大串針對下一個字元的 if 判斷，該字元儲存在全域整數 c 中。以下是它的片段外觀：

func next() {
    // Skip whitespace and comments, and look for / operator
    for c == '/' || c == ' ' || c == '\t' || c == '\r' || c == '\n' {
        if c == '/' {
            nextChar()
            if c != '/' {
                token = tDivide
                return
            }
            nextChar()
            // Comment, skip till end of line
            for c >= 0 && c != '\n' {
                nextChar()
            }
        } else if c == '\n' {
            nextChar()
            // Semicolon insertion: golang.org/ref/spec#Semicolons
            if token == tIdent || token == tIntLit || token == tStrLit ||
                token == tReturn || token == tRParen ||
                token == tRBracket || token == tRBrace {
                token = tSemicolon
                return
            }
        } else {
            nextChar()
        }
    }
    if c < 0 {
        // End of file
        token = tEOF
        return
    }

    // Integer literal
    if isDigit(c) {
        tokenInt = c - '0'
        nextChar()
        for isDigit(c) {
            tokenInt = tokenInt*10 + c - '0'
            nextChar()
        }
        token = tIntLit
        return
    }

    // ... handle other tokens (snipped) ...
}

在語法分析器中，我盡量沿用 Go 規格中語法產生式（production）的名稱，例如 Expression、VarSpec 與 Operand。當然，由於我們處理的是語言子集，其中許多都比 Go 規格中的版本精簡許多。以下是幾個語法分析函式的範例——請留意其中穿插的程式碼產生函式呼叫：

func Literal() int {
    if token == tIntLit {
        genIntLit(tokenInt)
        next()
        return typeInt
    } else if token == tStrLit {
        genStrLit(tokenStr)
        next()
        return typeString
    } else {
        error("expected integer or string literal")
        return 0
    }
}

func SimpleStmt() {
    // Funky parsing here to handle assignments
    identName := tokenStr
    expect(tIdent, "assignment or call statement")
    if token == tAssign {
        next()
        lhsType := varType(identName)
        rhsType := Expression()
        if lhsType != rhsType {
            error("can't assign " + typeName(rhsType) + " to " +
                typeName(lhsType))
        }
        genAssign(identName)
    } else if token == tDeclAssign {
        next()
        typ := Expression()
        defineLocal(typ, identName)
        genAssign(identName)
    } else if token == tLParen {
        genIdentifier(identName)
        typ := Arguments()
        genDiscard(typ) // discard return value
    } else if token == tLBracket {
        next()
        indexExpr()
        expect(tRBracket, "]")
        expect(tAssign, "=")
        Expression()
        genSliceAssign(identName)
    } else {
        error("expected assignment or call not " + tokenName(token))
    }
}

func Statement() {
    if token == tIf {
        IfStmt()
    } else if token == tFor {
        ForStmt()
    } else if token == tReturn {
        ReturnStmt()
    } else {
        SimpleStmt()
    }
}

其中一個有點凌亂的地方是上面的「簡單陳述式」——如果是有產生語法樹的語法分析器，你大概會呼叫 Expression 來解析左側，然後看看是否有 = 或 := 來判斷是否為指派，再解析右側。但我們不能呼叫 Expression，否則它會編譯出讀取該運算式的程式碼，而不是對其指派。所以我們必須先解析一個識別字，再偵測接下來的是指派、函式呼叫還是切片運算式。我確定上面的程式碼並未正確處理所有邊界情況，但已經夠用了。

運算子優先順序是透過遞迴下降來處理的，例如下面中 && 與 || 運算子的處理（名稱 orExpr 與 andExpr 並未出現在 Go 規格中）：

func andExpr() int {
    typ := comparisonExpr()
    for token == tAnd {
        op := token
        next()
        typRight := comparisonExpr()
        typ = genBinary(op, typ, typRight)
    }
    return typ
}

func orExpr() int {
    typ := andExpr()
    for token == tOr {
        op := token
        next()
        typRight := andExpr()
        typ = genBinary(op, typ, typRight)
    }
    return typ
}

func Expression() int {
    return orExpr()
}

在這個遞迴下降語法分析器中有兩個遞迴的前向參照：Expression（解析運算式時的各種函式都必須呼叫 Expression）與 Block（區塊元素最終會巢狀進入 Block）。Go 不需要也不允許前向參照，所以 Mugo 在啟動時就預先定義了這兩個函式的正確簽章。

編譯器透過一組全域切片來追蹤變數名稱與型別資訊：

var (
    globals        []string // global names and types
    globalTypes    []int
    locals         []string // local names and types
    localTypes     []int
    funcs          []string // function names
    funcSigIndexes []int    // indexes into funcSigs
    funcSigs       []int    // each func: retType N arg1Type ... argNType
)

前四個相當淺顯易懂，但 funcSigs 這個切片就有點，嗯，古怪了。它其實是一個結構切片。在真正的 Go 程式碼中，你大概會定義一個 funcSig 結構，並把那三個「func」切片整合成一個從函式名稱對應到結構的 map：

var funcSigs map[string]funcSig

type funcSig struct {
    retType  int
    argTypes []int
}

但 Mugo 不支援 struct 或 map，所以我只好把這些欄位塞進一個扁平的 int 切片中，其中 funcSigIndexes[i] 指向 funcSigs 切片中該虛擬結構的起始位置（對應索引為 i 的函式）。

效能

因為完全沒有做最佳化，Mugo 顯然會比 Go 慢上許多，所以我不打算做大量的效能測試。但為了好玩，我寫了一個小程式來測試一個包含一些整數運算的基本迴圈效能——它會把從 1 到 10 億的數字加總：

var (
    result int
)

func main() {
    sum := 0
    i := 1
    for i <= 1000000000 {
        sum = sum + i
        i = i + 1
    }
    result = sum // so Go doesn't optimize it out
}

在我的機器上，Go 版本執行這個程式需時 0.34 秒。Mugo 版本則需 5.7 秒——大約是 17 倍的時間。對於有史以來最糟的組合語言碼之一來說，我覺得還不算太差。作為參考，同樣迴圈的Python 版本需要 1 分 38 秒……動態型別的位元組碼直譯器顯然不是處理大量整數運算的好選擇。

有趣的是，如果我把 sum 本身改成全域變數而非區域變數，Mugo 版本的耗時不變，但 Go 版本卻從 0.34 秒變成 1.7 秒。我猜 Mugo 之所以慢很多，一大原因在於它所有操作都在堆疊上的記憶體中進行——即使堆疊位於 CPU 快取中，暫存器終究還是更快。

效能的另一個面向是程式碼大小：Mugo 建置出的執行檔比 Go 建置的小得多。用 Go 建置的 Mugo 執行檔是 1.6MB，用 Mugo 建置的 Mugo 卻只有 56KB——大約是 1/29 的大小！這當然不是一場公平的較量——Mugo 並未內建 goroutine 排程器、垃圾回收器或執行期型別資訊（可參考這篇Go FAQ）。不過，這確實引發了一個有趣的問題：對於用 Go 寫的簡單 CLI 工具，我們是否能透過極簡的排程器與 GC 來縮小執行檔大小呢？

相關專案

如我先前提過的，我對直譯器與編譯器已經感興趣很久了。如果你喜歡這篇文章，以下是我的一些相關專案：

  • Third：我多年前為 8086 DOS 撰寫的 Forth 編譯器。另可參考 Richard Jones 的 jonesforth.S，了解如何打造 Forth 編譯器的教學。
  • pyast64：使用ast 模組將 Python 語法轉為 x86-64 組合語言。
  • LoxLox：用 Lox 本身撰寫的Crafting Interpreters 的 Lox 程式語言直譯器（你是否開始注意到其中的模式了？）。
  • GoAWK：一個用 Go 撰寫、相容於 POSIX 的 AWK 直譯器。
  • ZZT in Go：描述我為了將 Adrian Siekierka 的《Reconstruction of ZZT》移植到 Go 而撰寫的 Pascal-to-Go 轉換器。

希望你喜歡這篇文章——我自己在打造 Mugo 的過程中確實樂在其中。歡迎隨時向我提供回饋！你也可以閱讀在Hacker News 上的討論。

本文章由 muse-spark-1.2-contributor 進行翻譯

留言