Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

[インデックス 18523] ファイルの概要

このコミットは、Goコンパイラ（cmd/gc）におけるライブネス解析の誤りを修正するものです。特に、runtimeパッケージ内の特定の非復帰関数（throwreturn, selectgo, block）が、実際には呼び出し元に戻らないにもかかわらず、ライブネス解析が誤った制御フローエッジを推論し、その結果として変数が不必要に「ライブ」であると判断される問題に対処しています。この問題は、特に未初期化の変数が誤ってライブであると判断された場合に、予期せぬ動作やバグを引き起こす可能性がありました。

コミット

commit af545660d59edeffb52b8b72bec08f8c7b33cf23
Author: Russ Cox <rsc@golang.org>
Date:   Fri Feb 14 00:38:24 2014 -0500

    cmd/gc: correct liveness for various non-returning functions
    
    When the liveness code doesn't know a function doesn't return
    (but the generated code understands that), the liveness analysis
    invents a control flow edge that is not really there, which can cause
    variables to seem spuriously live. This is particularly bad when the
    variables are uninitialized.
    
    TBR=iant
    CC=golang-codereviews
    https://golang.org/cl/63720043

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/af545660d59edeffb52b8b72bec08f8c7b33cf23

元コミット内容

Goコンパイラ（cmd/gc）において、様々な非復帰関数に対するライブネス解析を修正します。

ライブネス解析のコードが、ある関数が実際には戻らないことを認識していない場合（しかし、生成されるコードはそのことを理解している場合）、ライブネス解析は実際には存在しない制御フローエッジを誤って生成してしまいます。これにより、変数が不必要にライブであると見なされる可能性があり、特に変数が未初期化である場合には深刻な問題を引き起こす可能性があります。

変更の背景

Go言語のコンパイラは、プログラムの効率的な実行のために様々な最適化を行います。その一つが「ライブネス解析（Liveness Analysis）」です。ライブネス解析は、あるプログラムポイントにおいて変数が将来使用される可能性があるかどうか（すなわち「ライブ」であるか「デッド」であるか）を判断するために行われます。この情報は、主にガベージコレクション（GC）において、どのメモリ領域がまだ参照されているかを特定するために不可欠です。また、レジスタ割り当てやデッドコード削除などの他の最適化にも利用されます。

このコミット以前は、Goコンパイラのライブネス解析が、runtimeパッケージ内の特定の関数（例: selectgo, throwreturn, block）の挙動を正確にモデル化できていませんでした。これらの関数は、呼び出されると決して呼び出し元に戻らない（非復帰関数）という特性を持っています。しかし、ライブネス解析はこれらの関数が通常の関数呼び出しのように呼び出し元に戻る可能性があると誤解し、存在しない制御フローエッジを推論していました。

この誤った推論の結果、実際にはデッドであるはずの変数が「ライブ」であると誤って判断されることがありました。特に問題となるのは、未初期化の変数が誤ってライブであると判断された場合です。このような変数がGCによって参照されていると見なされると、ガベージコレクタが誤ったメモリ領域をスキャンしたり、解放すべきメモリを保持し続けたりする可能性があり、メモリリークやクラッシュ、あるいは予測不能な動作につながる恐れがありました。

このコミットは、このような誤ったライブネス情報の伝播を防ぎ、コンパイラが非復帰関数の特性を正しく理解するようにすることで、より正確なライブネス解析と、それに続くガベージコレクションおよび最適化の精度を向上させることを目的としています。

前提知識の解説

ライブネス解析 (Liveness Analysis)

ライブネス解析は、データフロー解析の一種で、プログラムの特定のポイントにおいて、ある変数の値が将来の計算で利用される可能性があるかどうか（「ライブ」であるか）を決定します。もし変数の値が将来使われることがない場合、その変数は「デッド」であると判断されます。

  • 目的:
    • ガベージコレクション: ライブなオブジェクトのみがGCの対象となり、デッドなオブジェクトは解放されます。正確なライブネス情報は、GCの効率と正確性に直結します。
    • レジスタ割り当て: ライブな変数はレジスタに割り当てられ、デッドな変数はレジスタを解放できます。
    • デッドコード削除: デッドな変数を計算するコードは削除できます。
  • 動作原理: 通常、プログラムの制御フローグラフ（CFG）を逆方向に辿りながら、各プログラムポイントでの変数のライブネスを計算します。ある変数がライブであると判断されるのは、その変数が定義された後、その値が使用されるパスが存在する場合です。

非復帰関数 (Non-returning Functions)

非復帰関数とは、呼び出された後、決して呼び出し元に制御を戻さない関数のことです。典型的な例としては、以下のような関数があります。

  • panic: Goランタイムパニックを引き起こし、プログラムを異常終了させるか、recoverによって捕捉されない限りスタックをアンワインドします。
  • log.Fatal / os.Exit: プログラムを終了させます。
  • 無限ループを含む関数（ただし、コンパイラがそれを常に認識できるとは限りません）。
  • runtime.throw: Goランタイム内部で致命的なエラーが発生した場合に呼び出され、プログラムを終了させます。

コンパイラが非復帰関数を正しく認識することは重要です。なぜなら、非復帰関数の呼び出しの後には、通常の制御フローは存在しないため、その後のコードは到達不能（unreachable）であり、その時点での変数のライブネスも異なる扱いになるからです。

Goのselectステートメントとruntime.selectgo

Goのselectステートメントは、複数のチャネル操作を待機し、準備ができた最初の操作を実行するために使用されます。selectステートメントは、その内部でGoランタイムの低レベル関数を呼び出します。特に、複数のcaseを持つselectは、通常runtime.selectgoという関数を呼び出します。

runtime.selectgoは、チャネル操作の準備が整うまでゴルーチンをブロックしたり、ランタイムスケジューラと連携して動作したりする複雑なロジックを含んでいます。重要なのは、runtime.selectgoが呼び出し元に「戻る」のではなく、選択されたチャネル操作に対応するコードパスに直接「ジャンプ」するか、あるいはゴルーチンをブロックしてスケジューラに制御を渡すという点です。つまり、runtime.selectgoもまた、実質的に非復帰関数として振る舞うことがあります。

cmd/gcとpopt.c

  • cmd/gc: Go言語の公式コンパイラです。Goのソースコードを機械語に変換する主要なツールチェーンの一部です。
  • popt.c: cmd/gcのソースコードの一部で、主にプログラムの最適化（poptは"post-optimization"や"peephole optimization"の略である可能性があります）に関連する処理を扱います。このファイルには、コンパイラが特定の関数が非復帰であることを認識するためのロジックが含まれていることが多いです。noreturn関数は、コンパイラが非復帰関数を識別するために使用する内部ヘルパー関数であると推測されます。

技術的詳細

このコミットの核心は、Goコンパイラのライブネス解析が、特定のruntime関数（throwreturn, selectgo, block）の非復帰特性を正しく認識していなかった点にあります。

Goコンパイラは、コードを解析して制御フローグラフを構築し、その上でライブネス解析を実行します。ライブネス解析は、ある命令の後にどの変数がまだ使用される可能性があるかを判断するために、制御フローエッジを辿ります。

問題は、throwreturn、selectgo、blockといった関数が、通常の関数呼び出しのように呼び出し元に制御を戻すのではなく、プログラムの実行フローを別の場所に転送するか、あるいはプログラムを終了させるという特殊な挙動をすることにありました。

  • runtime.throwreturn: これは、Goの関数がreturnステートメントなしで終了しようとしたが、実際には戻り値を期待している場合など、ランタイムが致命的なエラーを検出したときに呼び出される内部関数です。この関数は決して呼び出し元に戻りません。
  • runtime.selectgo: 前述の通り、selectステートメントの内部で呼び出され、選択されたチャネル操作のコードパスに直接ジャンプするか、ゴルーチンをブロックします。呼び出し元に戻ることはありません。
  • runtime.block: ゴルーチンを無期限にブロックするランタイム関数です。これも呼び出し元に戻りません。

コンパイラのライブネス解析は、これらの関数が非復帰であることを認識していなかったため、これらの関数呼び出しの直後に、あたかも通常の関数呼び出しのように呼び出し元に戻る「架空の」制御フローエッジを生成していました。この架空のエッジが存在することで、実際にはデッドであるはずの変数が、そのエッジを介して「将来使用される可能性がある」と誤って判断され、「ライブ」であるとマークされてしまっていました。

特に、未初期化の変数が誤ってライブであると判断されると、ガベージコレクタがその変数が指すメモリ領域を有効なものとして扱い、スキャン対象に含めてしまう可能性があります。これにより、GCの効率が低下したり、最悪の場合、未初期化のポインタを辿って不正なメモリにアクセスし、クラッシュを引き起こす可能性がありました。

このコミットでは、src/cmd/gc/popt.c内のnoreturn関数に、これらのruntime関数を追加することで、コンパイラがこれらの関数を非復帰関数として明示的に認識するように変更しています。noreturn関数は、コンパイラが制御フロー解析を行う際に、これらの関数が呼び出し元に戻らないことを考慮に入れるように指示します。これにより、架空の制御フローエッジが生成されなくなり、ライブネス解析がより正確に行われるようになります。

test/live.goに追加されたテストケースは、この問題がどのように現れていたか、そして修正によってどのように解決されたかを示しています。特にf11a, f11b, f12のコメントは、selectgoやselect{}が非復帰であるにもかかわらず、以前はライブネス解析が誤った変数をライブと判断していたことを明確に示しています。

コアとなるコードの変更箇所

src/cmd/gc/popt.c

--- a/src/cmd/gc/popt.c
+++ b/src/cmd/gc/popt.c
@@ -51,6 +51,9 @@ noreturn(Prog *p)
 		symlist[2] = pkglookup("throwinit", runtimepkg);
 		symlist[3] = pkglookup("panic", runtimepkg);
 		symlist[4] = pkglookup("panicwrap", runtimepkg);
+		symlist[5] = pkglookup("throwreturn", runtimepkg);
+		symlist[6] = pkglookup("selectgo", runtimepkg);
+		symlist[7] = pkglookup("block", runtimepkg);
 	}
 
 	if(p->to.node == nil)

test/live.go

--- a/test/live.go
+++ b/test/live.go
@@ -121,3 +121,64 @@ func f10() string {
 	panic(1)
 }
 
+// liveness formerly confused by select, thinking runtime.selectgo
+// can return to next instruction; it always jumps elsewhere.
+// note that you have to use at least two cases in the select
+// to get a true select; smaller selects compile to optimized helper functions.
+
+var c chan *int
+var b bool
+
+// this used to have a spurious "live at entry to f11a: ~r0"
+func f11a() *int {
+	select { // ERROR "live at call to selectgo: autotmp"
+	case <-c: // ERROR "live at call to selectrecv: autotmp"
+		return nil
+	case <-c: // ERROR "live at call to selectrecv: autotmp"
+		return nil
+	}
+}
+
+func f11b() *int {
+	p := new(int)
+	if b {
+		// At this point p is dead: the code here cannot
+		// get to the bottom of the function.
+		// This used to have a spurious "live at call to printint: p".
+		print(1) // nothing live here!
+		select { // ERROR "live at call to selectgo: autotmp"
+		case <-c: // ERROR "live at call to selectrecv: autotmp"
+			return nil
+		case <-c: // ERROR "live at call to selectrecv: autotmp"
+			return nil
+		}
+	}
+	println(*p)
+	return nil
+}
+
+func f11c() *int {
+	p := new(int)
+	if b {
+		// Unlike previous, the cases in this select fall through,
+		// so we can get to the println, so p is not dead.
+		print(1) // ERROR "live at call to printint: p"
+		select { // ERROR "live at call to newselect: p" "live at call to selectgo: autotmp.* p"
+		case <-c: // ERROR "live at call to selectrecv: autotmp.* p"
+		case <-c: // ERROR "live at call to selectrecv: autotmp.* p"
+		}
+	}
+	println(*p)
+	return nil
+}
+
+// similarly, select{} does not fall through.
+// this used to have a spurious "live at entry to f12: ~r0".
+
+func f12() *int {
+	if b {
+		select{}
+	} else {
+		return nil
+	}
+}

コアとなるコードの解説

src/cmd/gc/popt.cの変更

src/cmd/gc/popt.cファイル内のnoreturn関数は、Goコンパイラが特定の関数が呼び出し元に戻らないことを認識するための内部メカニズムです。この関数は、runtimeパッケージ内の既知の非復帰関数（例: panic, throwinit, panicwrap）のシンボルリストを保持しています。

このコミットでは、以下の3つのruntime関数がこのリストに追加されました。

  1. pkglookup("throwreturn", runtimepkg): runtime.throwreturn関数を追加します。これは、ランタイムが致命的なエラーを検出した際に呼び出され、決して呼び出し元に戻らない関数です。
  2. pkglookup("selectgo", runtimepkg): runtime.selectgo関数を追加します。これは、selectステートメントの内部で呼び出され、選択されたチャネル操作のコードパスに直接ジャンプするか、ゴルーチンをブロックするため、呼び出し元に戻りません。
  3. pkglookup("block", runtimepkg): runtime.block関数を追加します。これはゴルーチンを無期限にブロックする関数であり、呼び出し元に戻りません。

これらの関数をnoreturnリストに追加することで、コンパイラのライブネス解析は、これらの関数が呼び出された後に通常の制御フローが続かないことを正しく理解するようになります。これにより、これらの関数呼び出しの後に、実際には存在しない制御フローエッジが誤って生成されることがなくなり、変数のライブネスがより正確に判断されるようになります。

test/live.goの変更

test/live.goファイルには、この修正が正しく機能することを確認するための新しいテストケースが追加されています。これらのテストケースは、以前のライブネス解析の誤りを具体的に示し、修正後の正しい挙動を検証します。

  • f11a(): selectステートメントを含む関数です。コメントには「liveness formerly confused by select, thinking runtime.selectgo can return to next instruction; it always jumps elsewhere.」とあり、runtime.selectgoが非復帰であるにもかかわらず、以前はライブネス解析が誤解していたことを示しています。ERRORコメントは、修正前には誤ったライブネスエラーが発生していたことを示唆しています。
  • f11b(): ifブロック内にselectステートメントを含む関数です。p := new(int)でポインタを初期化し、if bのブロック内でselectを呼び出しています。コメントには「At this point p is dead: the code here cannot get to the bottom of the function. This used to have a spurious "live at call to printint: p".」とあり、selectが非復帰であるため、ifブロック内のpはデッドであるべきなのに、以前は誤ってライブと判断されていたことを示しています。
  • f11c(): f11b()と似ていますが、selectのcaseがreturn nilを含んでいないため、selectの後に制御がフォールスルーする可能性があります。このため、pはデッドではなくライブであるべきです。このテストは、selectの挙動によってライブネスが正しく判断されることを確認しています。
  • f12(): 空のselect{}ステートメントを含む関数です。コメントには「similarly, select{} does not fall through. this used to have a spurious "live at entry to f12: ~r0".」とあり、select{}も非復帰であるにもかかわらず、以前は誤ったライブネスエラーが発生していたことを示しています。

これらのテストケースは、コンパイラがruntime.selectgoや空のselect{}ステートメントの非復帰特性を正しく認識し、それに応じて変数のライブネスを正確に判断できるようになったことを検証しています。

関連リンク

参考にした情報源リンク

  • Go言語のドキュメント (特にselectステートメント、panic、runtimeパッケージに関するもの)
  • コンパイラのライブネス解析に関する一般的な情報源 (例: Dragon Book)
  • Goのガベージコレクションに関する技術記事やドキュメント
  • Goのruntimeパッケージのソースコード (特にselect.goやエラーハンドリング関連のファイル)
  • Goのcmd/gcコンパイラのソースコード (特にpopt.cやライブネス解析関連のファイル)