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

## はじめに

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

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

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

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

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

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

- [発表スライド](https://www.rileythomp.com/assets/GopherCon%202024%20-%20Exploring%20the%20Go%20Compiler_%20Adding%20a%20%E2%80%9Cfour%E2%80%9D%20loop.pdf)
- [デモ用PR](https://github.com/rileythomp/go/pull/2)
- [発表者のWriteup](https://www.rileythomp.com/write-ups/four-loop-go)

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

[^1]: for statementと"four" statementをかけていますね、はい。

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

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

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

// Output: 1 is odd number.
```

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

```go
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](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/238364/17427cdf-5ffe-9ba7-023b-dd3000b3bf1a.png)

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

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

[^2]: [Wikipedia](https://ja.wikipedia.org/wiki/%E3%82%B3%E3%83%B3%E3%83%91%E3%82%A4%E3%83%A9#:~:text=%E3%80%8C%E3%83%9F%E3%83%89%E3%83%AB%E3%82%A8%E3%83%B3%E3%83%89%E3%80%8D%EF%BC%88%E4%BB%8A%E6%97%A5%E3%81%A7%E3%81%AF%E6%BB%85%E5%A4%9A%E3%81%AB%E4%BD%BF%E3%82%8F%E3%82%8C%E3%81%AA%E3%81%84%EF%BC%89)によると、ミドルエンドという表現は最近使われないらしい。

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

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

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

[Dockerfile](
https://github.com/task4233/go/blob/f16300955f0b3cd40460844f65b057cf0478c963/Dockerfile)は次のとおりです。

```docker
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](https://github.com/task4233/go/blob/f16300955f0b3cd40460844f65b057cf0478c963/Makefile)は次のとおりです。

```docker
build:
	docker build -t go-workspace .

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

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

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

```bash
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コンテナ内部で実行するコマンドは次のとおりです。

```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`コマンドを毎回呼び出すのは面倒なので、[このように](https://github.com/task4233/go/blob/f16300955f0b3cd40460844f65b057cf0478c963/src/cmd/compile/internal/syntax/tokens.go#L11) `go:generate`ディレクティブが書かれています。

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

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

```bash
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 
```

ここまでの変更は、[こちらのコミット](https://github.com/task4233/go/commit/22882944daac84d5470593a3a9410fd7c407e1ad)にまとめてあります。

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

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

```bash
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](https://github.com/task4233/go/blob/6ac91e460c294bda5a50e628b7556bf20525fa44/src/cmd/compile/internal/syntax/scanner.go#L419))を持っており、 `four` と `unless` を追加した結果、想定されたサイズを超過してしまったために起きたエラーです。

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

```bash
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` は

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

のような形なので、 `four` は

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

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

同様にして、 `if` は

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

という形なので、 `unless` は

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

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

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

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

```bash
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
```

ここまでの変更は、[こちらのコミット](https://github.com/task4233/go/commit/185d413d33767c9be2e52ab5e15eabcde4bd44d0)にまとめてあります。

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

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

これが終わった状態で、 `recompile` して実行してみると、次のエラーが表示されます。変更は、[こちらのコミット](https://github.com/task4233/go/commit/852b68bd6a8f59cafc0c22d38b28688f5f924926)にまとめてあります。

```bash
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生成処理を行うことができます。変更は、[こちらのコミット](https://github.com/task4233/go/commit/55472e5e40efc69ad100cc737c6fb772625864ad)にまとめました。

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

```bash
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 
```

その後、さらに必要なファイルを変更していきます。変更は、[こちらのコミット](https://github.com/task4233/go/commit/a3606d4c071e1dc44c52b7a7977daaed18ac4a01)にまとめてあります。

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

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

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

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

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

### ミドルエンド

この章では、

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

を行います。

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

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

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

```bash
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へ変換して、一時変数を導入して、評価の順序に気を遣うステップのことです。変更は、[こちらのコミット](https://github.com/task4233/go/commit/68024e5bb94bd9aaf77d5967f4857906b432c0a6)にまとめてあります。

#### Desugarステップの追加

Desugarステップとは、ハイレベルな構文をよりプリミティブな構文へ変換するステップです。今回であれば、unless statementを否定されたif文というプリミティブな構文へ変換できるので、こちらの変更を適用します。変更は、[こちらのコミット](https://github.com/task4233/go/commit/9ccbc12ca59abc53ce4e506ef20a54f1cd7f95b9)にまとめてあります。

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

```bash
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` のみを含むファイルは実行できます。

```go
package main

import (
	"fmt"
)

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

```

```bash
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つの終了点のみが存在する形になります。変更は、[こちらのコミット](https://github.com/task4233/go/commit/f16300955f0b3cd40460844f65b057cf0478c963)にまとめてあります。

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

```bash
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](https://github.com/task4233/go/compare/go1.23.0...task4233:go:tmp/go-workspace?expand=1)

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