Blog Dice

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

Ben Hoyt

Mugo、自分自身をコンパイルできるGoサブセット向けトイコンパイラ

原文は Ben Hoyt により に公開されました。 このブログを購読する

概要：本記事では、Goプログラミング言語のごく小さなサブセットを対象としたシングルパスコンパイラ「Mugo」を紹介します。出力するのは（きわめて素朴な）x86-64アセンブリで、Mugoコンパイラ自体を実装するのに必要なだけの言語機能をサポートしています。int型やstring型、スライス、関数、ローカル変数・グローバル変数、そして基本的な式や文です。

私はコーディングを始めた頃からコンパイラに魅了されてきました。初期のプロジェクトのひとつが、8086版DOS向けの自己ホスト型Forthコンパイラ“Third”でした。Forthはコンパイルが驚くほど簡単です。式や文が存在せず、空白で区切られた各トークンが直接call命令にコンパイルされ、多くの場合直接スレッディング（direct threading）のような手法が使われるからです。

CやGoのような一般的な言語は、式や文を含むより複雑な構文を持つため、本格的なパーサーやコード生成器が必要です。これらの言語向けコンパイラは通常複雑で高機能ですが、後述するように、基本的な型だけに絞り、最適化しない出力を許容すれば、シンプルなコンパイラでも十分作ることができます。

Mugoは、Fabrice Bellard氏によるObfuscated Tiny C Compilerの精神を少し受け継いでいます。もちろん私のものははるかに地味で、IOCCCで優勝するようなことは当分なさそうですが。Bellard氏のコンパイラは、C言語のうち自分自身をネイティブなi386 Linux実行ファイルとしてコンパイルできるだけの機能を実装しています。

Goでも難読化を抜きにして、似たようなことをやってみたいと思いました。きっかけはシャワーを浴びているときの思いつきでした。「Goのどのくらい小さなサブセットがあれば、自分自身をコンパイルできるのだろう？」と。Fabrice氏のCコンパイラは難読化されたCで2048バイトで実装されていますが、私のものは整形されたGoで1600行です。

これは長い週末を使った楽しい実験でしたが、あくまでトイ（おもちゃ）です。Goの素晴らしい機能はすべて省かれています。ユーザー定義型、インターフェース、ゴルーチン、チャネル、マップ、ガベージコレクション、境界チェックすらありません！Mugoの目的は教育的でした。私自身のために、そしてできれば読者の皆さんのためにも。こうした演習は、私たちの使っているツールがどう動いているかを解き明かしてくれます。

Goのどのサブセットか？

MugoはGoのサブセットなので、ソースコードはGoでもMugoでもコンパイルできます。個人的には、これがより面白くしていると思っています。テストも楽になりました。Goでビルドしたバージョンのアセンブリ出力と、Mugoでビルドしたバージョンの出力が同一であれば、正しく動いていると分かるのです。diff mugo2.asm mugo3.asmが何も出力しなかったときは、本当に感動的でした！

始める前に、どの機能をサブセットに含めるかじっくり考えました。コンパイラの状態を保持するには、何らかのコンテナ型が必要になることは分かっていました。たとえば変数の名前や型、関数のシグネチャや戻り値の型などです。しかし、どのコンテナを使うべきでしょうか？

Goにはポインタがありますが、Cのポインタほど強力ではありません。ポインタ演算ができない分、より安全ではありますが。Bellard氏のコンパイラはCのポインタを多用していますが、Goではそれは使えませんでした。

では構造体やマップはどうでしょうか？それらを実装するのはより複雑になるうえ、何かをリストとして保持するという最も一般的な問題を解決してくれるわけでもありません。そこで、それらはすべて不要だと判断し、スライスだけで十分だと決めました。

Mugoがサポートしている機能は次のとおりです。

  • int型、10進数の整数リテラル、文字定数、そしてintを扱うほぼすべての式：+、-、*、/、%、==、!=、<、<=、>、>=。演算子の優先順位はGoに準じて処理されます。コンパイラはboolという型名も認識しますが、intとまったく同じものとして扱います（&&、||、!はこの疑似的なboolに対して動作します）。
  • string型。文字列定数（\によるエスケープを含む）、==や!=による文字列の等価判定、+による文字列結合、len()を含みます。
  • スライス。ただし[]intと[]stringのみです。スライスリテラルやmake()はサポートされていないため、スライスを作るには空のスライスを作成してappendで追加する必要があります。スライス要素の取得や代入、slice[:n]形式の式、len()はサポートされています。
  • 型チェックは存在しますが、不完全です。意味があると感じた箇所やデバッグに役立つ箇所ではチェックしていますが、決して網羅的ではありません。
  • 文：ifとelse、for condition { ... }、return、そしてGoの:=による短縮変数宣言です。
  • 変数と定数。ただしvarとconstはトップレベルでのみサポートされ、ローカル変数では:=を使う必要があります（Goではそもそもこちらの方が一般的です）。サポートされるのは型付きの整数定数のみです。
  • トップレベルの関数（再帰を含む）。ただし関数値や無名関数はサポートされません。関数は単一の戻り値のみ持つことができ、可変長引数関数は含まれません。
  • 入出力。あらかじめ定義された3つの関数を使います。getcは標準入力から1文字読み込み、printとlogはそれぞれ標準出力と標準エラー出力に文字列を書き出します。
  • Goの文法。ただしここで必要なものだけに絞り込んでいます。多くの構文はサポートされていません。たとえば++や--、for rangeループなどです。//による単一行コメントはサポートされています。

だいたい以上です！上記リストにないものは、おそらく含まれていないと思ってください。繰り返しますが、本当に小さなサブセットです。

作成中は、簡潔でよくまとまったGo言語仕様を何度も参照しましたが、間違っている部分もほぼ確実にあるでしょう。ただ、実装した範囲では「diffテスト」が示すように、Goと同じように動作しているようです。

コード生成

Mugoは、解析しながらその場でx86-64アセンブリを出力するシングルパスコンパイラです（Linux向けに書かれていますが、macOSやWindowsで動くようにするのも難しくはありません）。メモリ上に抽象構文木（AST）は持ちません。いずれにせよスライスだけでそれを構築するのは難しいでしょうから。

そして非常に素朴です。最適化は一切ありません。基本的に高性能なレジスタベースのCPUを愚直なスタックマシンに変えてしまい、中間値をpushやpopでスタックに積み下ろししています。本物のコンパイラの複雑さの半分はコード生成に、もう半分は型チェックにあると言えますが、Mugoではその両方が極端に単純化されています。

工夫が必要だったトリックのひとつが、ローカル変数宣言（Goの:=構文）です。シングルパスなので、関数の解析が終わるまでローカル変数がいくつあるのか、その型は何かが分かりません。そこで関数のプロローグでは、おなじみのrbpによるフレームポインタの処理に加え、スタックポインタから64バイト分を引いて、最大8セル分のローカル変数領域を確保しています（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の最適化ありの出力は、レジスタを使ったたった1命令になります。

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では、最初の6セル（64ビット値）はレジスタに置かれます。

シンプルにするため、MugoのABIでは引数をスタックにpushします。順番にpushされるため、メモリ上では逆順に並ぶことになります。一方、戻り値はレジスタを使います。rax、さらにセルが増える場合はrbxやrcxです。Goと同様に、intは1セル、stringは2セル（アドレスと長さ）、スライスは3セル（アドレス、長さ、容量）です。

文字列結合やスライスへの追加のためのメモリ確保には、Mugoはごく単純な「バンプアロケータ」を使っています。つまり、固定された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から、コンパイラの3つのバージョンをビルドする例を次に示します。

# 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では字句解析器（レキサ）で1文字の先読みを使い、典型的な再帰下降パーサーを採用しています。

字句解析器は基本的に次の文字に対する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仕様の文法にある生成規則の名前をなるべくそのまま使おうとしました。たとえば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()
    }
}

上に示した「単純な文（simple statement）」は少しややこしい部分です。構文木を生成するパーサーであれば、おそらく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()
}

再帰下降パーサーには2つの前方参照の再帰があります。Expression（式解析内のさまざまな関数がExpressionを呼び出す必要があります）とBlock（ブロック内の要素が最終的にBlockへ再帰します）です。Goでは前方参照は不要ですし許可もされていないため、Mugoでは起動時にこの2つの関数を正しいシグネチャで事前定義しています。

コンパイラは変数名や型情報を、グローバルなスライスの集合で管理しています。

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
)

最初の4つはほぼ自明ですが、funcSigsスライスは少し、いやかなりトリッキーです。実はこれは構造体のスライスなのです。本物のGoコードであれば、おそらくfuncSig構造体を定義して、これら3つの“func”系スライスを関数名から構造体へのマップにまとめるでしょう。

var funcSigs map[string]funcSig

type funcSig struct {
    retType  int
    argTypes []int
}

しかしMugoは構造体もマップもサポートしていないため、これらのフィールドをintのフラットなスライスに詰め込む必要がありました。funcSigIndexes[i]が、インデックスiの関数に対応する擬似構造体のfuncSigsスライス内での開始位置を指しています。

パフォーマンス

最適化を一切していないため、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、約29分の1のサイズです！これはまったく公平な比較ではありません。Mugoにはゴルーチンスケジューラもガベージコレクタも、ランタイム型情報も含まれていないのですから（こちらのGo FAQの質問を参照）。ただ、これは興味深い疑問を投げかけます。Goで書かれたシンプルなCLIツールであれば、ごく単純なスケジューラとGCでバイナリサイズを削減できるのではないでしょうか？

関連プロジェクト

冒頭でも触れたように、私は長年インタプリタやコンパイラに興味を持ってきました。この記事を楽しんでいただけたなら、関連する私のプロジェクトもいくつか紹介します。

  • Third：何年も前に私が書いた8086 DOS向けForthコンパイラです。Forthコンパイラの作り方のチュートリアルとしては、Richard Jones氏のjonesforth.Sも参照してください。
  • pyast64：astモジュールを使ってPythonの構文をx86-64アセンブリに変換するツールです。
  • LoxLox：Crafting InterpretersのLoxプログラミング言語のインタプリタを、Lox自体で書いたものです（何かパターンにお気づきでしょうか？）。
  • GoAWK：Goで書かれたPOSIX互換のAWKインタプリタです。
  • ZZT in Go：Adrian Siekierka氏のReconstruction of ZZTをGoに移植する際に最初に作成した、PascalからGoへのコンバータについて書いています。

この記事を楽しんでいただけたなら幸いです。私はMugoを作る過程を存分に楽しみました。ご感想をお待ちしています！Hacker Newsでのディスカッションもぜひご覧ください。

この記事は「muse-spark-1.2-contributor」を使用して翻訳されました。

コメント