LoginSignup
3
2
@task4233

GopherCon 2024 Recap: Exploring the Go Compiler: Adding a "four" loop

Last updated at Posted at 2024-09-02

はじめに

本記事は GopherCon 2024 の発表である Exploring the Go Compiler: Adding a “four” loop の Recap のためのエントリです。こちらの内容は、元々 Go 1.23 リリースパーティ & GopherCon 2024 報告会で発表する予定でしたが、発表時間が15分しかなく具体的な実装を追う時間がなさそうなので、こちらの記事で具体的な変更差分をシェアすることとしました。

本記事で触れることと触れないこと

  • 触れること
    • 当該発表の概要
    • コンパイラの処理の概要
    • 構文追加における具体的な変更差分
  • 触れないこと
    • Goにおける用語の詳細な説明
      • Statement、arrayなど
      • よく知らない場合はGoのSpecificationを参照してください
    • コンパイラにおける用語の詳細な説明
      • AST(抽象構文木)やIR(中間表現)など
      • これらもググれば分かることですし、発表自体とは強く関連しないので省きます

では、発表概要から触れていきます。

Recap: Exploring the Go Compiler: Adding a “four” loop

こちらの発表は、2つの構文追加の実例に沿ってGoコンパイラの処理を紹介した発表でした。一次情報は次の通りです。

そして、追加された2つの構文は次の“four” statement1とunless statementでした。

four i := 0; i < 16; i++ {
	fmt.Printf("%d,", i)
}

// Output:
// 0,4,8,12,

const i = 1
unless i%2==0 {
  fmt.Printf("%d is odd number.", i)
}

// Output: 1 is odd number.

これらの構文は現在のGoには存在しません。そのため、発表では上記2つの構文を含む次のコードを実行できるようにすることがゴールでした。

package main

import (
	"fmt"
)

func main() {
	four i := 8; i <= 20; i++ {
		unless i%8 == 0 {
			fmt.Println(i, "is not divisible by 8")
			continue
		}
		fmt.Println(i, "is divisible by 8")
	}
}

とはいえ、コンパイラに構文を追加する上でコンパイラの処理を知っておく必要があります。

コンパイラ処理の概要

コンパイラ処理はざっくり言えば次のようなフローをたどります。具体的な処理はコンパイラによって異なるものの、フロントエンド、ミドルエンド、バックエンドの3ステージに大別することができます。

Screenshot 2024-09-02 at 22.41.41.png

それぞれの目的は次のとおりです。

ステージ 目的
フロントエンド ソースコードを解析して中間表現(IR)を構築すること
ミドルエンド2 IRを最適化すること
バックエンド 最適化されたIRを機械語へ変換すること

それぞれのステージを順番に実装追加していくことで構文追加が完了します。では、実際に構文追加のステップを見ていきましょう。

構文追加における具体的な変更差分

環境構築

環境差異を避けるため、説明ではDockerのDev Containerを利用します。これは、作業中に環境が壊れたりGoコンパイラが壊れたりすることがあるためです。その場合はコンテナを一度落としてから再実行してください。ボリュームはDockerコンテナ内にマウントされてホストOSにも共有されているので、コンテナを落としても問題ありません。

Dockerfileは次のとおりです。

FROM ubuntu:24.04

RUN apt-get update && \
    apt-get install -y wget git vim tmux

# Install Go for ARM64
RUN wget https://go.dev/dl/go1.23.0.linux-arm64.tar.gz && \
    rm -rf /usr/local/go && \
    tar -C /usr/local -xzf go1.23.0.linux-arm64.tar.gz

WORKDIR /app

ENV PATH=$PATH:/usr/local/go/bin
ENV GOBIN=/usr/local/go/bin
RUN echo "alias recompile='time ( cd src/; ../bin/go install cmd/compile; cd ..; go clean -cache; )'" >> ~/.bashrc

COPY . /app

CMD ["bash"]

Makefileは次のとおりです。

build:
	docker build -t go-workspace .

run:
	docker run --rm -v ./:/app/ -it go-workspace /bin/bash

そして、次のコマンドを実行し、Goのリポジトリをローカルへクローンしてビルドが出来れば問題ありません。

ホストOSで実行するコマンドは次のとおりです。

git clone https://github.com/golang/go
cd go
git checkout go1.23.0
git switch -c tmp/go-workspace
vim Dockerfile
vim Makefile
make build
make run

Dockerコンテナ内部で実行するコマンドは次のとおりです。

root@fa67117cd9a0:/root# cd /app/src
root@fa67117cd9a0:/app/src# ./make.bash
root@fa67117cd9a0:/app/src# ../bin/go version
go version go1.23.0 linux/arm64

ここまで実行して、go version go1.23.0 linux/arm64 と表示されれば成功です。

今後の説明でファイルを編集する場合、基本的に go/src/cmd/compile/internal 以下で行うものとします。また、コマンドは全てDockerコンテナ内で実行するものとします。Gitのコミットを積みたい場合は、ホストOS側で実施してください。

フロントエンド

本節では、

  • 構文解析のためのtokenの追加と関連する微修正
  • 字句解析のための処理の追加
  • 型チェックに必要な処理の追加
  • IR生成処理の追加

を行います。

構文解析のためのtokenの追加と関連する微修正

まずは four と unless というtokenを追加します。場所は syntax/tokens.go です。

Goでは stringer コマンドを利用することで、tokenの定義を生成してくれます。stringerコマンドを毎回呼び出すのは面倒なので、このように go:generateディレクティブが書かれています。

//go:generate stringer -type token -linecomment tokens.go

そのため、次のように stringer コマンドをインストールした上で、 $ go generate を実行してください。

root@fa67117cd9a0:/app/src# go install golang.org/x/tools/cmd/stringer@latest
root@fa67117cd9a0:/app/src# go generate ./cmd/compile/internal/syntax/tokens.go

ここまでの変更は、こちらのコミットにまとめてあります。

これにより、 syntax/token_string.go に新しく Four および Unless が追加されていることが分かります。

では、実際にビルドして demo.go を実行してみましょう。次のようなエラーが表示されるはずです。

root@fa67117cd9a0:/app/src# recompile
root@fa67117cd9a0:/app/src# ../bin/go run ../demo.go
panic: imperfect hash
goroutine 1 [running]:
cmd/compile/internal/syntax.init.0()
	/app/src/cmd/compile/internal/syntax/scanner.go:431 +0xa4
(snip)
go: error obtaining buildID for go tool compile: exit status 2

これは、scannerが定義されたtokenのためのarrayである keywordMap (ref)を持っており、 four と unless を追加した結果、想定されたサイズを超過してしまったために起きたエラーです。

そのため、 keyworkMap のサイズを増やしてあげれば問題ありません。その後、再ビルドするとpanicは消えるはずです。

root@fa67117cd9a0:/app/src# ./make.bash
root@fa67117cd9a0:/app/src# ../bin/go run ../demo.go 
# command-line-arguments
../demo.go:8:2: syntax error: unexpected four, expected }

これは字句解析時のエラーに見えるので、次のステップに進みましょう。

字句解析のための処理の追加

字句解析の前に、 four と unless の構造を考えましょう。 four なら for 、 unless なら if という似た構造の構文があるので、これらの構造を踏襲します。

例えば、 for は

for <init>; <cond>; <post> {
	<body>
}

のような形なので、 four は

four <init>; <cond>; <post> {
	<body>
}

という構造にすれば良さそうです。

同様にして、 if は

if <init>; <cond> {
	<then>
} <else>

という形なので、 unless は

unless <init>; <cond> {
	<then>
}

という構造にすれば良さそうです。

この前提のもと、実装を追加します。

ここで recompile して実行してみると、次のエラーが表示されます。

root@fa67117cd9a0:/app/src# recompile 
root@fa67117cd9a0:/app/src# ../bin/go run ../demo.go 
# command-line-arguments
../demo.go:4:2: "fmt" imported and not used
../demo.go:8:2: invalid syntax tree: invalid statement

ここまでの変更は、こちらのコミットにまとめてあります。

型チェックに必要な処理の追加

続いて、型チェックのために必要な実装を追加します。

これが終わった状態で、 recompile して実行してみると、次のエラーが表示されます。変更は、こちらのコミットにまとめてあります。

root@fa67117cd9a0:/app/src# recompile 
root@fa67117cd9a0:/app/src# ../bin/go run ../demo.go 
# command-line-arguments
../demo.go:8:2: internal compiler error: unexpected statement: &{0x4000444940 0x400044c0c0 0x4000444980 0x40004449c0 {{{0x4000103e90 8 2}}}} (*syntax.FourStmt)

Please file a bug report including a short program that triggers the error.
https://go.dev/issue/new

これは、構文ツリーは構成できているが、そこからのIR生成に失敗しているため起きているエラーです。そのため、IR生成処理と小さな修正を行います。これにより、型チェックされた構文木から抽象構文木へ変換するためのIR生成処理を行うことができます。変更は、こちらのコミットにまとめました。

ここで、nodeの生成を実施する必要があります。node生成のためのコマンドは用意されており、 次のコマンドで生成できます。

root@fa67117cd9a0:/app/src# cd cmd/compile/internal/ir/
root@fa67117cd9a0:/app/src/cmd/compile/internal/ir# go generate node.go
root@fa67117cd9a0:/app/src/cmd/compile/internal/ir# go run mknode.go

その後、さらに必要なファイルを変更していきます。変更は、こちらのコミットにまとめてあります。

そして、またstringerによるgenerationが必要なので、実施しておきます。

root@fa67117cd9a0:/app/src# go generate ./internal/pkgbits/sync.go

ここで生じるエラーは、次の通りのはずです。

../demo.go:8:2: internal compiler error: unexpected stmt: four loop

こちらのエラーはescape解析関連のファイルで生じているようなので、そちらの変更を次は加えていきましょう。

ミドルエンド

この章では、

  • エスケープ解析のための処理追加
  • Orderステップのための処理追加
  • Desugerステップのための処理追加

を行います。

エスケープ解析のための処理追加

エスケープ解析とは、プログラム実行時にオブジェクトがどのスコープに退避するかを解析する手法のことです。この解析により、パフォーマンスの向上やメモリ管理の最適化が期待できます。エスケープ解析のためには、statementを追加すれば良いです。変更は、こちらのコミットにまとめてあります。

この変更を加えると、エラーが次のものに変わります。

root@b5a4aa7ad417:/app/src# recompile
root@b5a4aa7ad417:/app/src# ../bin/go run ../demo.go 
# command-line-arguments
../demo.go:8:2: internal compiler error: order.stmt four

Orderステップの追加

Orderステップとは、複雑なStatementを単純なStatementへ変換して、一時変数を導入して、評価の順序に気を遣うステップのことです。変更は、こちらのコミットにまとめてあります。

Desugarステップの追加

Desugarステップとは、ハイレベルな構文をよりプリミティブな構文へ変換するステップです。今回であれば、unless statementを否定されたif文というプリミティブな構文へ変換できるので、こちらの変更を適用します。変更は、こちらのコミットにまとめてあります。

ここでrecompile後に実行すると、次のエラーが表示されるはずです。

root@b5a4aa7ad417:/app/src# recompile 
root@b5a4aa7ad417:/app/src# ../bin/go run ../demo.go 
# command-line-arguments
../demo.go:8:2: internal compiler error: 'main': unhandled stmt four

Please file a bug report including a short program that triggers the error.
https://go.dev/issue/new

これは、unless文が既存のif文を利用しているため、バックエンドの変更を必要としていないためです。つまり、次のような unless のみを含むファイルは実行できます。

package main

import (
	"fmt"
)

func main() {
	const i = 1
	unless i%2 == 0 {
		fmt.Printf("%d is odd number\n", i)
	}
}


root@b5a4aa7ad417:/app/src# ../bin/go run ../demo2.go 
1 is odd number

ここからは、 four も利用できるようにバックエンドの変更を加えていきましょう。

バックエンド

この章では、

  • SSA形式の構成

を行います。

今回は不要でしたが、械語命令の生成部分も実装する場合があります。

さて、今回は追加された “four” について見ていきます。 これは、ASTをSSA(Static Single Assignment)形式のIRに変換するものです。SSAに関しては、internalのREADMEが参考になります。

簡潔に言えば、これによってプログラムは各変数が1度だけ代入されるように書き直されます。これにより、プログラムをブロックへ分割することができ、各ブロックには値や操作のセットが含まれて、ブロックの終わりには1つの終了点のみが存在する形になります。変更は、こちらのコミットにまとめてあります。

ここでrecompileして実行すると、demo.goが実行できるはずです！お疲れ様でした:tada:

root@b5a4aa7ad417:/app/src# recompile
root@b5a4aa7ad417:/app/src# ../bin/go run ../demo.go 
8 is divisible by 8
12 is not divisible by 8
16 is divisible by 8
20 is not divisible by 8

ここまでの説明で利用した全体のdiffはこちらの通りです。

https://github.com/task4233/go/compare/go1.23.0...task4233:go:tmp/go-workspace

おわりに

実際に手元で構文を拡張できると面白いですよね。こういうきっかけがないと実装を読むことも少ないと思うので、良い機会になったのであれば幸いです。それと、もし良ければ Go 1.23 リリースパーティ & GopherCon 2024 報告会 も見ていってください。他にも面白い発表がたくさんあると思うので。ではまた。

  1. for statementと"four" statementをかけていますね、はい。 ↩

  2. Wikipediaによると、ミドルエンドという表現は最近使われないらしい。 ↩

3
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
2