Goプログラムがビルドされるまで （コンパイラーの仕組みを探る）

Goを使っているプログラマの中でコンパイラについて聞いたことある人もいるかも知れませんが、実際に何をしているか分からないかもしれません。
心配はGo無用。この記事で解説いたします。

# コンパイルとは

ただGoプログラムを書くだけでは実行はできません。
実行可能にするまでに手を加える必要があります。コンパイラがソースコードをコンピューターが理解できる形式に変換します。

コンパイルをするプログラムの名前が**コンパイラ**です。

GCCやLLVMとか聞いたことありますか？これらもコンパイラです。
これらのコンパイラは長期に渡って、たくさんの貢献者によって開発されて来ました。

`> go build main.go`

もちろん、Goでもコンパイルします。
このコマンドのように、Goプログラムをビルドするたびにコンパイルしているんです。

### Goコンパイラについて
- Goは独自のコンパイラを開発しています。 (GCCやLLVMを使っていません。)
- Goプロジェクトはオープンソースなので、公式サイトでソースコードを読むことができます。
- ソースコードには標準ライブラリなどGoに欠かせない多くの機能が含まれています。コンパイラ関連のコードが格納されているディレクトリは`src/cmd/compile`です。

# プログラミング言語実行モデル

Goに深入りする前に、プログラミング言語全体の実行モデルについて話します。

![Screenshot 2023-12-05 at 15.04.25.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/5308/45dacd22-ae42-e2cf-149d-bbe229323998.png)

プログラミング言語には主に2種類の実行モデルがあります。

**コンパイル型**はCPU命令を生成し、それをバイナリに格納します。そしてコードを実行する時にそのCPU命令を読み込んで実行します。

**インタプリタ型**は「コードを実行するよ」というタイミングで仮想マシンなどによってCPU命令に変換されて実行します。

コンパイル型とインタプリタ型のプログラミング言語の例です。

| コンパイル型 | インタプリタ型 |
|:-:|:-:|
|  **Go** <br />C, C++<br />Rust<br />Swift| Javascript<br />Python<br />Ruby  |

コンパイル型は、最初の1行目を実施する前からビルドに時間をかけることで有名ですね。

その一方で、インタプリタ型の言語はサクッと実行できることで知られていますが、重い計算に不向きだという評判がありますね。

これらのプログラミング言語はケースバイケースで使い分けます。
コンパイル型とインタプリタ型のメリット・デメリットを見てみましょう。

|  | コンパイル型 | インタプリタ型 |
|:-:|:-:|:-:|
| メリット  | ・実行が早い  |  ・各プラットフォームのコンパイルが不要(“Write Once, Run Everywhere”) |
| デメリット  |  ・コンパイルに時間がかかる<br />・各プラットフォームにコンパイルする必要あり |  ・実行速度が遅め<br />・仮想マシンがCPU/メモリへの負担となる |

# CとGoのバイナリを比較

CとGoのバイナリを比較してみましょう。どちらもコンパイル型言語ですから、そんなに違うはずはないですよね？
実は結構違います。

### バイナリサイズ

```lang:c
#include <stdio.h>

int main(){
  printf("Hello, World!\n");
  return 0;
}
```

```lang:go
package main
import "fmt"

func main() {
    fmt.Println("Hello, World!")
}
```

| C | Go |
|:-:|:-:|
|  33KB | 2MB  |

まずはバイナリサイズを見てみましょう。ここではどちらの言語の"Hello World"プログラムを用意しています。
Cではバイナリのサイズが <ins>33KB</ins> です。
一方で、Goのバイナリはよっぽど大きい <ins>2MB</ins> です。たかが"Hello world”なのに。

こんな単純な内容なのに、どうしてこんなに容量を取るんでしょうか？

### アセンブリ

```lang:c

main:	file format mach-o arm64

Disassembly of section __TEXT,__text:

0000000100003f68 <_main>:
100003f68: ff 83 00 d1 	sub	sp, sp, #32
100003f6c: fd 7b 01 a9 	stp	x29, x30, [sp, #16]
100003f70: fd 43 00 91 	add	x29, sp, #16
100003f74: 08 00 80 52 	mov	w8, #0
100003f78: e8 0b 00 b9 	str	w8, [sp, #8]
100003f7c: bf c3 1f b8 	stur	wzr, [x29, #-4]
100003f80: 00 00 00 90 	adrp	x0, 0x100003000 <_main+0x18>
100003f84: 00 a0 3e 91 	add	x0, x0, #4008
100003f88: 05 00 00 94 	bl	0x100003f9c <_printf+0x100003f9c>
100003f8c: e0 0b 40 b9 	ldr	w0, [sp, #8]
100003f90: fd 7b 41 a9 	ldp	x29, x30, [sp, #16]
100003f94: ff 83 00 91 	add	sp, sp, #32
100003f98: c0 03 5f d6 	ret

Disassembly of section __TEXT,__stubs:

0000000100003f9c <__stubs>:
100003f9c: 10 00 00 b0 	adrp	x16, 0x100004000 <__stubs+0x4>
100003fa0: 10 02 40 f9 	ldr	x16, [x16]
100003fa4: 00 02 1f d6 	br	x16
```

```lang:go

hellogo:	file format mach-o arm64

Disassembly of section __TEXT,__text:

0000000100001000 <_runtime.text>:
100001000: ff 20 47 6f 	umlal2.4s	v31, v7, v7[0]
100001004: 20 62 75 69 	ldpsw	x0, x24, [x17, #-88]
100001008: 6c 64 20 49 	<unknown>
10000100c: 44 3a 20 22 	<unknown>
100001010: 56 58 48 70 	adr	x22, #592651
100001014: 77 41 4f 79 	ldrh	w23, [x11, #1952]
100001018: 66 4b 47 74 	<unknown>
10000101c: 5a 6d 48 74 	<unknown>
100001020: 56 42 4e 5f 	<unknown>
100001024: 2f 70 63 45 	<unknown>
100001028: 47 74 6b 54 	b.vc	0x1000d7eb0 <_runtime.pclntab+0x10d90>
10000102c: 42 38 75 67 	<unknown>
100001030: 6e 6f 36 76 	<unknown>
100001034: 34 36 34 34 	cbz	w20, 0x1000696f8 <_unicode.init+0x31b8>
100001038: 48 2f 7a 7a 	<unknown>
10000103c: 73 35 5f 39 	ldrb	w19, [x11, #1997]
100001040: 7a 66 49 58 	ldr	x26, 0x100093d0c <_go:func.*+0x2d94>
100001044: 49 47 65 6d 	ldp	d9, d17, [x26, #-432]
100001048: 6a 34 4e 5f 	srsra	d10, d3, #50
10000104c: 35 69 2f 41 	<unknown>
100001050: 74 47 49 54 	<unknown>
100001054: 42 51 46 4d 	<unknown>
100001058: 55 38 4d 2d 	ldp	s21, s14, [x2, #104]
10000105c: 52 4c 5a 33 	<unknown>
100001060: 4a 77 35 22 	<unknown>
100001064: 0a 20 ff 00 	<unknown>
		...

0000000100001070 <_internal/cpu.Initialize>:
100001070: 90 0b 40 f9 	ldr	x16, [x28, #16]
100001074: ff 63 30 eb 	cmp	sp, x16
100001078: a9 01 00 54 	b.ls	0x1000010ac <_internal/cpu.Initialize+0x3c>
10000107c: fe 0f 1e f8 	str	x30, [sp, #-32]!
100001080: fd 83 1f f8 	stur	x29, [sp, #-8]
...
...
... 
...
...
```

| C | Go |
|:-:|:-:|
|  22 行 | 14万 行  |

アセンブリを見てみましょう。`objdump`のコマンドで抽出しました。
これで、どうしてCのバイナリがGoのバイナリより軽量なのが分かって来ますね。

Cではアセンブリがたった <ins>22行</ins> です。
その一方で、Goでは <ins>14万行</ins> のアセンブリがあります。ただの"Hello world”ですよ。

### システムコール

```lang:c
execve("./main", ["./main"], 0xffffcd34e2c0 /* 4 vars */) = 0
set_tid_address(0xffff9cc74230)         = 8
brk(NULL)                               = 0xaaaad0305000
brk(0xaaaad0307000)                     = 0xaaaad0307000
mmap(0xaaaad0305000, 4096, PROT_NONE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0xaaaad0305000
mprotect(0xaaaac4cff000, 4096, PROT_READ) = 0
ioctl(1, TIOCGWINSZ, 0xfffff28fad48)    = -1 ENOTTY (Not a tty)
writev(1, [{iov_base="Hello, World!", iov_len=13}, {iov_base="\n", iov_len=1}], 2) = 14
exit_group(0)                           = ?
+++ exited with 0 +++
```

```lang:go
execve("./main", ["./main"], 0xffffcd5741c0 /* 8 vars */) = 0
sched_getaffinity(0, 8192, [0, 1])      = 8
openat(AT_FDCWD, "/sys/kernel/mm/transparent_hugepage/hpage_pmd_size", O_RDONLY) = 3
read(3, "2097152\n", 20)                = 8
close(3)                                = 0
mmap(NULL, 262144, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0xffff953ed000
mmap(NULL, 131072, PROT_NONE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0xffff953cd000
mmap(NULL, 1048576, PROT_NONE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0xffff952cd000
mmap(NULL, 8388608, PROT_NONE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0xffff94acd000
mmap(NULL, 67108864, PROT_NONE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0xffff90acd000
mmap(NULL, 536870912, PROT_NONE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0xffff70acd000
mmap(NULL, 8388608, PROT_NONE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0xffff702cd000
mmap(0x4000000000, 67108864, PROT_NONE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x4000000000
mmap(NULL, 33554432, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0xffff6e2cd000
mmap(NULL, 1133584, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0xffff6e1b8000
mmap(0x4000000000, 4194304, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x4000000000
mmap(0xffff953cd000, 131072, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0xffff953cd000
mmap(0xffff952cd000, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0xffff952cd000
mmap(0xffff94acf000, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0xffff94acf000
mmap(0xffff90add000, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0xffff90add000
mmap(0xffff70b4d000, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0xffff70b4d000
mmap(0xffff702cd000, 12288, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0xffff702cd000
mmap(NULL, 1048576, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0xffff6e0b8000
mmap(NULL, 65536, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0xffff6e0a8000
mmap(NULL, 65536, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0xffff6e098000
rt_sigprocmask(SIG_SETMASK, NULL, [], 8) = 0
sigaltstack(NULL, {ss_sp=NULL, ss_flags=SS_DISABLE, ss_size=0}) = 0
sigaltstack({ss_sp=0x4000004000, ss_flags=0, ss_size=32768}, NULL) = 0
rt_sigprocmask(SIG_SETMASK, [], NULL, 8) = 0
gettid()                                = 453
rt_sigaction(SIGHUP, NULL, {sa_handler=SIG_DFL, sa_mask=[], sa_flags=0}, 8) = 0
rt_sigaction(SIGHUP, {sa_handler=0x6c5f0, sa_mask=~[], sa_flags=SA_ONSTACK|SA_RESTART|SA_SIGINFO}, NULL, 8) = 0
rt_sigaction(SIGINT, NULL, {sa_handler=SIG_DFL, sa_mask=[], sa_flags=0}, 8) = 0
rt_sigaction(SIGINT, {sa_handler=0x6c5f0, sa_mask=~[], sa_flags=SA_ONSTACK|SA_RESTART|SA_SIGINFO}, NULL, 8) = 0
rt_sigaction(SIGQUIT, NULL, {sa_handler=SIG_DFL, sa_mask=[], sa_flags=0}, 8) = 0
...
...
...
```

| C | Go |
|:-:|:-:|
|  9 回 | 209 回  |

これらのアセンブリにはOSに対するシステムコールも含まれています。
Cだとシステムコールが <ins>9回</ins> しかありません。
でもGoだと <ins>209回</ins> もあって、大違いです。

### Goでシステムコールが多い理由

Goでシステムコールが多い理由としては、Goのランタイムの存在が挙げられます。
ランタイムによって、多くの利便性が実現されています。例えば：
- ガベージコレクション
- Goroutine スケジューラ
- チャネル関連の操作

これらのランタイムの機能を実現するために、よほど大きくて複雑なバイナリが必要なんですね。

# Go コンパイラ(たち)

そもそもGoとは何でしょうか？実は２つのモノを指します。

**プログラミング言語の仕様**と**Goプログラムの実行環境**です。

![Screenshot 2023-12-05 at 15.30.31.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/5308/189e1ebe-d5fc-9ac7-9822-375ab05ce206.png)

プログラマの関心は、正しい文法でプログラムを作成し、規定のキーワードを使ってプログラムの挙動を表すことです。

一方で、Goの関心は、プログラマの書いたプログラムを理解し、コンピュータで実行することです。

そして、実はGoの仕様はネット上で誰にでも見れるように公開されています。

https://go.dev/ref/spec

仕様にはGoのルールが記載されています。どういう見た目であるべきなのか？どういう挙動をするべきなのか？

ルールとしてあるのは：
- 表記
- ソースコード表現
- 定数
- 変数
- 型と値のプロパティ
- ブロック
- 宣言と範囲
- 式
- ステートメント
- 内蔵関数
- パッケージ
- プログラムの初期化と実行
- エラー
- 実行時のパニック
- システムに関する考慮事項
- 型の統一

...などです。

:::note warn
どうしてGoは仕様を厳密に定義しているのでしょうか？

Goの開発者は、実装が仕様として扱われないように配慮しています。
他の分野で例えると、まるでウェブブラウザの実装が仕様にならないように、HTMLが標準化されているような感じです。
:::

これを踏まえると...
仕様に従えば、コンパイラの自作だって可能なんです！

### 様々なGoコンパイラ

![Screenshot 2023-12-05 at 15.36.19.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/5308/99bb1f5b-a282-e661-e45e-ce000b853758.png)

いろいろありますね！どれを使えばいいのでしょうか？

| コンパイラ | 特徴 |
|:-:|:-:|
|  **gc** |  公式実装のコンパイラで、最新バージョンが使えます。 |
|  **gccgo** |  `ver1.18`までにしか対応しておらず、ジェネリックスには未対応です。 |
|  **llgo** |  なんと2020年に開発中止されております。<br> あくまでメンテナンスの難しさを例示するために挙げています。<br> 本番環境には使わないほうがいいと思います。 |

![Screenshot 2023-12-05 at 15.39.33.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/5308/2f5723e6-a3f1-41f2-a441-ea3008e7a29d.png)

先ほど例示した有名なコンパイラですが、コンパイルできるのはCだけではありません。Goだってコンパイルできるんです。

Goプログラムをその他のコンパイラが理解できる中間言語に変換するフロントエンドプロジェクトが存在します。
Gccgoやllgoなどのフロントエンドが変換してくれます。
中間言語に変換されたら、あとはコンパイラに任せるだけです。
フロントエンドのおかげで、人気のコンパイラインフラを活用することだってできるんです。

### 他のコンパイラバックエンドを使う理由

公式実装があるのに、わざわざ他のコンパイラを使う理由はいくつかあります：

- `gc` (標準実装)にない最適化を使用するため
- `gc`が未対応のプラットフォームへコンパイルするため
- ライブラリをダイナミックリンクするため（公式は静的リンク）
- 政治的な理由で、実装が仕様になるのを防ぐため

# Goがコンパイルされるまで

さて、Goがいかにコンパイルされるか説明します。この記事の本題です。
この記事では公式コンパイラ（`gc`）を取り上げます。

![Screenshot 2023-12-05 at 15.42.10.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/5308/d710d10d-54fe-7f65-3471-f319792a0948.png)

これらがGoのソースコードからバイナリまでのコンパイルの過程です。

コンパイルの過程を **フロントエンド** と **バックエンド**に二分します。

フロントエンドはソースコードを中間言語へ変換する部分です。GoをASTという中間言語に変換するまでには、字句解析、パース、そしてASTの生成があります。

ASTが手に入れば、バックエンド部分が始まります。バックエンドにはミドルエンド最適化、ウォーク、英語のSingle Static Assignmentの頭文字を取ったSSA、そして機械言語の生成があります。

## トークン化 (字句解析)

:::note warn
実装箇所
`src/cmd/compile/internal/syntax/tokens.go` (トークン一覧) 
`src/cmd/compile/internal/syntax/tokenizer.go` (文字列をトークン化)
:::

まずは字句解析に伴うトークン化があります。トークンのことを「意味の単位」だと考えてください。
コンピュータにとってGoのソースコードはただの文字列であり、特に意味が理解することができません。だからソースコードを意味の単位に分割する必要があります。

意味の単位としては、変数などユーザーが定義した名前もありますし、if文、switch文、case分岐などGoのキーワードもあります。

![Screenshot 2023-12-05 at 15.45.26.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/5308/3f6e7b07-9d31-9aa0-5963-6a2464e0f94d.png)

Goでは`scanner`というパッケージがあります。ご自身のソースコードをトークンの単位に分割することもできます。

例えばHello Worldのプログラムがあります。プログラマーにとって一目瞭然ですが、コンパイラにはこれを細かく分割する必要があります。関数宣言、変数名、カッコ、中カッコ、呼び出されているパッケージや関数、さらにEnd of Fileのマーカーまであります。

## パース (AST 生成)

:::note warn
実装箇所
`src/cmd/compile/internal/syntax/parser.go` (パース) 
`src/cmd/compile/internal/syntax/nodes.go` (Noder)
:::

トークンが手に入りましたが、次はトークン同士の関係を形成しなければなりません。これらのトークンはどのように接触し、どういう挙動を起こすのでしょうか？
パーサが **Abstract Syntax Tree**、頭文字を取ってASTというグラフを生成します。

ASTは何でしょうか？
ASTはソースコードをツリー構造のグラフにしたものです。
そしてノードは式、宣言、ステートメントに該当します。

```lang:go
x := 2 + 3 * 6
```

ASTについて説明するより、例を使って説明した方が分かりやすいかもしれません。
ここにあるのはたった１行のコードの小さな例ですが、最終的には大きく拡張します。
このコードをASTにするとどうなるのでしょうか？

![Screenshot 2023-12-05 at 15.47.53.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/5308/3c07c9b8-cc99-bb24-2af6-dcc8676518cf.png)

単純な代入式がASTへ拡張されました。
左には変数xがあります。右には計算項目があります。ASTは計算の順番を遵守するように並べてあります。
まずはASTの真下へ捜索し、3*6を計算します。そして、それに2を足します。その後に計算結果をxへ代入します。

![Screenshot 2023-12-05 at 15.48.20.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/5308/183b6a3d-a0f0-5d42-7dc5-e80be8502eff.png)

メモリの中ではASTがさっきのようなグラフのように格納されていません。GoはASTをネスティングされた文字として格納しています。
たかがHello Worldもかなり複雑になります。
人間にとって難しく見えますが、コンパイラにとってはソースコードのレイアウトが分かりやすくなり処理しやすくなります。

## ミドルエンド最適化

:::note warn
実装箇所
`src/cmd/compile/internal/deadcode` (デッドコード削除) 
`src/cmd/compile/internal/inline` (関数のインライン展開) 
`src/cmd/compile/internal/devirtualize` (インターフェースメソッド呼び出しを非仮想化) 
`src/cmd/compile/internal/escape` (エスケープ解析)
:::

ASTができたので、次はバックエンドに移りましょう。まずはミドルエンド最適化があります。それぞれの最適化の方法は「パス」と呼ばれています。
パスの中には、デッドコード削除、関数のインライン展開、インターフェースメソッド呼び出しの非仮想化、エスケープ解析などがあります。

ミドルエンドで行われる最適化をみてみましょう。
インライン展開とエスケープ解析を取り上げます。

### インライン展開

まずはインライン展開です。Goが新しい関数を呼び出すたびに、関連情報を読み込んでメモリに格納するという計算資源への負荷があります。
インライン展開すればこの負荷を軽減することができます。とある関数がAST上で80ノード以内の他の関数を呼び出したら、コンパイラがこの２つの関数を1つに組み合わせます。そうすることで実際に2つの関数を呼び出す時より計算資源を節約することができます。

### エスケープ解析

もう１つ取り上げる最適化の方法がエスケープ解析です。関数が存在する期間より変数が「長生き」する場合があります。変数はスタック領域に格納されますが、すでに存在しない関数スタックにある変数をアクセスすることはできません。なので変数をスタック領域からヒープ領域へ逃がしてやります。こうすることで関数がメモリ上から消えても、変数がまだアクセス可能になります。

## ウォーク

:::note warn
実装箇所
`cmd/compile/internal/walk`
:::

バックエンドの次のステップはウォークです。Goが簡単に書けるのは、ウォークが行う作業のおかげです。複雑な表現を分解したり、Goならではハイレベルな概念をDesugarしたりします。

例えば、こういうDesugarがあります：
- switch文をバイナリサーチやジャンプテーブルへ変換
- mapとチャネルをランタイムコールへ変換

## SSA変換

:::note warn
実装箇所
`src/cmd/compile/internal/ssagen` (中間言語をSSAへ変換)
`src/cmd/compile/internal/ssa` (SSAパスとルール) 
:::

今度はSSA変換です。ここでASTがさらに加工されます。
SSAは英語のSingle Static Assignmentの頭文字です。SSAを使うとコードをさらに最適化することができます。

SSAについて解説します。
SSAは低レベルな中間言語です。
ASTをSSA変換すると、ASTにあるすべての変数が唯一のものとなり、不可変となります。だから英語ではSingle Static Assignmentという名前を取っています。
SSAにした方が行いやすい最適化の方法があります。
GoではSSAがまずamd64に向けてバージョン1.7で導入され、バージョン1.8でその他のCPUアーキテクチャに対応しました。
GoはSSAを初めて採用したコンパイラではありません。GCCやLLVMでも採用されています。

![Screenshot 2023-12-05 at 15.53.08.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/5308/25945639-6313-ae2d-faaf-bde97f0fc0a6.png)

これも説明するより見せた方が分かりやすいでしょう。
SSA変換前と後のコードを見てみましょう。SSA変換前は同じ変数に何回でも値を代入することができます。
しかし、SSA変換後では変数名が唯一のものとなりました。なので他の値を特定の変数に代入したい場合、同じ変数を使うのではなく、新しい変数に代入することになります。だから、変数に値が代入されるのは1回だけです。

![Screenshot 2023-12-05 at 15.53.44.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/5308/f88a5763-14af-f8ef-ffa4-e60e5411a0fd.png)

SSAに変換すると、コンパイラがまた複数の最適化パスを実行します。
これらのパスはSSAを活用しています。

これらがSSAを活用したパスの例です：
```
PhiElim
CopyElim
ShortCircuit
Decompose
CSE
PhilOpt
NilCheckElim
Prove
BCE
Loop
Fuse
DSE
WriteBarrier
insertLoopReschedChecks
Critical
LikelyAdjust
Layout
FlagAlloc
RegAlloc
LoopRotate
```

その中でも「CSE・共通部分式除去」がSSAの利点を見せる良い例かもしれません。

### 共通部分式除去 

![Screenshot 2023-12-05 at 15.55.08.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/5308/e0f7b74e-8a68-fc6e-f2e2-579b8073c1f6.png)

共通部分式除去はコードの中で重複している式を省く方法です。
例えば、変数yと`z`に`x+2`の表現を代入します。`x+2`を一度だけ使って、次回はその値を持った変数を使えば効率的ですね。ただ、`x+2`の値が`y`と`z`の間で変わったか分かりません。SSAがなければ、`y`と`z`の間にある`x`の値を捜索する必要があります。
ではSSAを使ったコードを見てみましょう。`x`の値が変わらないことは把握できていますね。`y`の値も変わりません。なので`z = x + 2`を見かけたら、yもまだ`x+2`に等しいと分かりますし、`y`に`z`を代入するだけで済みます。

### GOSSAFUNC

自分のコードがどのようにSSA変換されてるか気になりますか？Goのツールチェーンにはコンパイル中のコードを確認する方法があります。

`GOSSAFUNC`はSSA変換をHTMLにて出力するビルドフラグです。コンパイルの各段階のコードを表示します。以下のように呼び出せます：

`> GOSSAFUNC=main go build main.go`

以下のようにHTMLへ出力されます：

![gofuncssa.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/5308/701b37d4-9361-eef9-aaec-7e06d264affa.png)

## 機械言語の生成

:::note warn
実装箇所
`src/cmd/compile/internal/ssa` (SSA lowering + arch毎のパス) 
`src/cmd/compile/internal/obj` (機械言語の生成)
:::

最後に機械言語の生成があります。これでSSAがCPU命令に変換されます。

CPU命令に変換するためには、SSA状態のコードに"lowering"パスを使います。パスを通す前のコードはプラットフォームに依存しない抽象度の高いコードでした。が、Lowerすることで特定のプラットフォームに依存する抽象度へ下げます。
例えば、arm64にはメモリ操作が可能ですので、ロード・ストアオペレーションを使うことがあります。Lowerパスを使うことで、プラットフォーム独自の最適化を使うことができます。

最終コードパスの例を挙げます：

- デッドコード削除
- 値を使用箇所に近づける
- 未使用のローカル変数を削除
- レジスタ割り付け
- スタックフレームレイアウト: ローカル変数にスタックオフセットを代入
- ポインタ生存分析（ガベージコレクタのセーフポイントにおいて、スタック上のポインタが生存しているか分析）

最終パスを通せば、バイナリになるオブジェクトファイルを書き出します。
書き出す際に、SSAをobj.Prog命令に変換します。
オブジェクトファイルにはリフレクションデーター、エキスポートデータ、デバッグ情報が含まれます。

# さいごに

![Screenshot 2023-12-05 at 15.42.10.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/5308/d710d10d-54fe-7f65-3471-f319792a0948.png)

長い記事となりましたが、これでGoのソースコードからバイナリまでコンパイルされる過程が分かりましたね！

:::note warn

振り返ると...

- ソースコードからASTへ変換される前後に、**フロントエンド**と**バックエンド**がある
- フロントエンドでは、字句解析、パース、AST生成により、ソースコードの文字列から意味のある構造を抽出している
- バックエンドでは、ミドルエンドとSSAによる最適化が行われ、ウォークで「分かりやすい」Goの表現を機械向けに変換している

:::

# 参考

**コンパイラ内部**
Introduction to the Go compiler (https://go.dev/src/cmd/compile/README)
A Journey With GO (https://medium.com/a-journey-with-go)
Eli Bendersky (https://eli.thegreenplace.net/tag/go)
Hacking Go Compiler Internals (https://speakerdeck.com/moriyoshi/hacking-go-compiler-internals-2nd-season)

**SSA**
Introduction to the Go compiler’s SSA backend (https://go.dev/src/cmd/compile/internal/ssa/README)
Keith Randall - Generating Better Machine Code with SSA (https://youtu.be/uTMvKVma5ms)
Inlining optimisations in Go (https://dave.cheney.net/2020/04/25/inlining-optimisations-in-go)

**GCCGO**
Gccgo in GCC 4.7.1 (https://go.dev/blog/gccgo-in-gcc-471)

**コンパイラについての参考書籍**

![Screenshot 2023-12-05 at 16.00.03.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/5308/71aeb03e-f8f1-945b-8536-9607b6629ea9.png)

- Aho, A., Sethi, R. and Ullman, J. (2006).  Compilers: Principles, Techniques, and Tools
- Nystrom, R. (2021). Crafting interpreters

いわゆるドラゴンブックは専門家の間でも高く評価されていますが、かなり内容が高度でそれなりの難易度があります。
一方で、*Crafting Interpreters*はコンパイラを自作するチュートリアルの形式を取っていますので、コンパイラの機能を実装しながら少しずつ理解することができ、入門者にもおすすめです。

# 謝辞

「Advent Calendarに投稿してみたら」と提案された市川悠人さんにお礼を申し上げます。市川さんは企業ブログでもGoコンパイラにについて解説していますので、この記事で興味が湧いたら続けて読まれてみてはいかがでしょうか？

https://tech.techtouch.jp/entry/go-compiler-study-optimization-undefined-behaviour

https://tech.techtouch.jp/entry/go-compiler-study-inline-escape-analysis

https://tech.techtouch.jp/entry/go-compiler-study-array-object-operation

この記事は[Go Conference mini 2023 Winter IN KYOTO](https://kyotogo.connpass.com/event/285351/)での発表を記事化したものです。これについて発表させていただいたイベント運営者、およびご清聴いただいた参加者に感謝いたします。

https://kyotogo.connpass.com/event/285351/

今後もGoコンパイラをはじめとする技術的な発表をしたいので、機会があったらぜひご連絡くださいませ！

https://twitter.com/coolandsmartrr