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

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

このコミットは、Goコンパイラのcmd/gcパッケージにおける、panicで終わる関数におけるライブネス解析の正確性を修正するものです。具体的には、到達不能なRET（return命令）がライブネス解析に誤った情報を提供し、レジスタ割り当てコードの要件と衝突する問題を解決します。

コミット

  • Author: Russ Cox rsc@golang.org
  • Date: Thu Feb 13 23:56:53 2014 -0500
  • Commit Hash: ab9e8d068aafce0df7edca629af0549b5f54d3c9

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

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

元コミット内容

cmd/gc: correct liveness for func ending in panic

The registerization code needs the function to end in a RET,
even if that RET is actually unreachable.

The liveness code needs to avoid such unreachable RETs.
It had a special case for final RET after JMP, but no case
for final RET after UNDEF. Instead of expanding the special
cases, let fixjmp - which already knows what is and is not
reachable definitively - mark the unreachable RET so that
the liveness code can identify it.

TBR=iant
CC=golang-codereviews
https://golang.org/cl/63680043

変更の背景

Goコンパイラには、コードの最適化と正しい実行を保証するために、複数のフェーズが存在します。このコミットが対処している問題は、主に以下の2つのコンパイラフェーズ間の不整合に起因します。

  1. レジスタ割り当て (Registerization) コードの要件: Goコンパイラのレジスタ割り当てフェーズは、関数の終端にRET（return）命令が存在することを前提としています。これは、たとえそのRET命令が論理的に到達不可能であっても、レジスタ割り当てのアルゴリズムが正しく機能するために必要です。例えば、関数がpanicで終了する場合、通常の意味でのRETには到達しませんが、コンパイラ内部では形式的にRET命令が生成されることがあります。

  2. ライブネス解析 (Liveness Analysis) コードの要件: ライブネス解析は、特定のプログラムポイントで変数が「生きている」（将来使用される可能性がある）かどうかを判断する静的解析の一種です。この情報は、ガベージコレクションやレジスタ割り当ての効率化に不可欠です。ライブネス解析は、到達不能なコードパス、特に到達不能なRET命令を無視する必要があります。なぜなら、到達不能なコードは実際のプログラムの動作には影響せず、その中の変数のライブネスを考慮すると誤った結果や非効率なコード生成につながる可能性があるからです。

問題点: 以前のコンパイラでは、JMP（無条件ジャンプ）命令の後に続く到達不能なRET命令に対しては特別な処理が施され、ライブネス解析がそれを無視するようになっていました。しかし、panicのような関数がUNDEF（未定義の動作、または到達不能なコードを示す内部表現）の後にRET命令を持つ場合、この特別な処理が適用されず、ライブネス解析が誤って到達不能なRETを考慮してしまい、結果として誤ったライブネス情報が生成される可能性がありました。これは、レジスタ割り当てコードがRETを必要とする一方で、ライブネス解析がそれを無視したいという矛盾を生み出していました。

このコミットは、この矛盾を解消し、panicで終わる関数におけるライブネス解析の正確性を保証することを目的としています。

前提知識の解説

このコミットを理解するためには、以下のGoコンパイラ内部の概念と一般的なコンパイラの最適化技術に関する知識が必要です。

  1. Goコンパイラ (cmd/gc): Go言語の公式コンパイラです。ソースコードを機械語に変換する過程で、様々な最適化や解析を行います。

  2. 中間表現 (IR): コンパイラがソースコードを直接機械語に変換するのではなく、まず抽象的な中間表現に変換します。この中間表現に対して様々な最適化や解析が行われます。Goコンパイラも独自のIRを使用しており、Prog構造体はそのIRにおける命令（オペレーション）を表します。

  3. 命令の種類 (asフィールド): Prog構造体にはasフィールドがあり、これは命令の種類（オペレーションコード）を示します。

    • ARET: Return命令。関数の終了を示します。
    • AJMP: Jump命令。無条件ジャンプを示します。
    • UNDEF: 未定義の動作、または到達不能なコードを示す内部的な命令。panicのような関数が正常にリターンしない場合に、その後のコードが到達不能であることを示すために使用されることがあります。

  4. ライブネス解析 (Liveness Analysis): データフロー解析の一種で、プログラムの各ポイントにおいて、どの変数が「ライブ」（その値が将来の計算で使用される可能性がある）であるかを決定します。ライブでない変数は、そのメモリ領域を再利用したり、レジスタから追い出したりすることができます。これは、レジスタ割り当てやガベージコレクションの効率化に不可欠です。

  5. レジスタ割り当て (Register Allocation): プログラムの実行速度を向上させるために、頻繁に使用される変数をCPUのレジスタに割り当てるプロセスです。レジスタはメモリよりもはるかに高速にアクセスできます。レジスタ割り当てはライブネス解析の結果に大きく依存します。

  6. 基本ブロック (Basic Block): 制御フローグラフ (CFG) の構成要素で、単一のエントリポイントと単一のエグジットポイントを持つ命令のシーケンスです。基本ブロック内の命令は、常に連続して実行されます。

  7. fixjmp関数: Goコンパイラのpopt.cファイルに存在する関数で、ジャンプ命令の最適化や到達不能なコードの削除（デッドコードエリミネーション）を担当します。この関数は、コードの到達可能性について正確な知識を持っています。

  8. p->mode = -1: Prog構造体のmodeフィールドは、命令の特定の属性や状態を示すために使用されます。このコミットでは、mode = -1を「到達不能なRET命令」を示すマーカーとして使用しています。

技術的詳細

このコミットの核心は、Goコンパイラの異なるフェーズ（レジスタ割り当てとライブネス解析）が、関数の終端にあるRET命令に対して異なる要件を持っているという問題の解決策にあります。

問題の再確認:

  • レジスタ割り当て: 関数がRETで終わることを期待する。これは、panicのように実際にはリターンしない関数でも同様。
  • ライブネス解析: 到達不能なRET命令を無視したい。到達不能なコードはライブネス情報に影響を与えないべき。

以前のバージョンでは、JMP命令の後に続く到達不能なRET命令に対しては、ライブネス解析がそれを無視するための特別なロジックがplive.cに存在しました。しかし、panicで終わる関数は、コンパイラ内部でUNDEF命令の後に到達不能なRET命令が続くようなコードパターンを生成することがありました。このUNDEFのケースは既存の特別なロジックではカバーされていませんでした。

解決策: このコミットは、特別なケースをplive.cにさらに追加するのではなく、fixjmp関数（popt.cに存在）の能力を活用するという、より汎用的なアプローチを採用しています。

  1. fixjmpによる到達不能なRETのマーキング: fixjmp関数は、デッドコードエリミネーションの一部として、到達不能なコードパスを特定する能力を持っています。このコミットでは、fixjmpが関数の最後に存在する到達不能なARET命令（特にpanicなどで到達不能になるもの）を検出した場合、そのARET命令のmodeフィールドを-1に設定するように変更されました。 このARET命令は、レジスタ割り当ての要件を満たすために削除されずに残されますが、mode = -1というマーカーが付与されます。

    コミットメッセージにあるように、このARETを残す理由は、レジスタアロケータが「すべてのライブコードは、すべてのRET命令から前方向のリンクをたどることで走査できる」という仮定に基づいているためです。もし関数の終端で無限ループが発生し、その後に続くRETが削除されてしまうと、この仮定が崩れてしまう可能性があります。そのため、RETは残しつつ、ライブネス解析からは無視されるようにマークされます。

  2. ライブネス解析 (plive.c) でのマーカーの利用: plive.cのnewcfg関数（制御フローグラフを構築する部分）は、基本ブロックを構築する際に、命令を走査します。この変更により、newcfgはp->link->as == ARET && p->link->mode == -1という条件をチェックするようになりました。 もしこの条件が真であれば、それはfixjmpによって到達不能とマークされたARET命令であることを意味します。この場合、ライブネス解析はそこで基本ブロックの構築を停止し、到達不能なRETを制御フローグラフに含めないようにします。これにより、ライブネス解析が誤った情報に基づいて動作するのを防ぎます。

このアプローチにより、fixjmpが到達可能性に関する唯一の真実の源となり、ライブネス解析は単にその情報に従うだけでよくなります。これにより、コンパイラの異なる部分間の整合性が向上し、将来的に同様の問題が発生するのを防ぐことができます。

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

このコミットでは、主に以下の3つのファイルが変更されています。

  1. src/cmd/gc/plive.c: ライブネス解析に関連するコード。

    • newcfg関数内で、到達不能なRET命令をスキップするための条件が変更されました。
    • 変更前: if (p->as == AJMP && p->link->as == ARET && p->link->opt == nil) (JMPの後のRETのみを考慮)
    • 変更後: if(p->link != nil && p->link->as == ARET && p->link->mode == -1) (modeが-1のRETを考慮)

  2. src/cmd/gc/popt.c: 最適化パス、特にfixjmp関数に関連するコード。

    • fixjmp関数内で、関数の最後の到達不能なARET命令にmode = -1を設定するロジックが追加されました。
    • if(p->link == P && p->as == ARET && last && last->as != ARET)という条件で、関数の最後のARETであり、かつそのARETがデッドコードである場合に、p->mode = -1が設定されます。

  3. test/live.go: ライブネス解析のテストケース。

    • f10()という新しいテスト関数が追加されました。この関数はpanic(1)で終了し、以前のコンパイラではライブネス解析が混乱する原因となっていました。このテストケースの追加により、修正が正しく機能することを確認できます。

コアとなるコードの解説

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

--- a/src/cmd/gc/plive.c
+++ b/src/cmd/gc/plive.c
@@ -519,12 +519,10 @@ newcfg(Prog *firstp)
 				break;
 			bb->last = p;
 
-			// Pattern match an unconditional branch followed by a
-			// dead return instruction.  This avoids a creating
+			// Stop before an unreachable RET, to avoid creating
 			// unreachable control flow nodes.
-			if(p->link != nil && p->link->link == nil)
-				if (p->as == AJMP && p->link->as == ARET && p->link->opt == nil)
-					break;
+			if(p->link != nil && p->link->as == ARET && p->link->mode == -1)
+				break;
 
 			// Collect basic blocks with selectgo calls.
 			if(isselectgocall(p))

この変更は、newcfg関数内で制御フローグラフを構築する際のロジックを修正しています。 以前は、AJMP（無条件ジャンプ）の後に続くデッドなARET命令を特別に処理していました。これは、JMPによってARETが到達不能になるケースをカバーしていました。 新しいコードでは、p->link->as == ARET && p->link->mode == -1という条件に変わっています。これは、fixjmpによってmodeが-1に設定されたARET命令（すなわち、到達不能とマークされたARET）を検出した場合に、そこで基本ブロックの構築を停止することを意味します。これにより、JMPだけでなく、UNDEFなど他の理由で到達不能になったARETも適切に無視されるようになります。

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

--- a/src/cmd/gc/popt.c
+++ b/src/cmd/gc/popt.c
@@ -146,7 +146,13 @@ fixjmp(Prog *firstp)
 		if(p->opt == dead) {
 			if(p->link == P && p->as == ARET && last && last->as != ARET) {
 				// This is the final ARET, and the code so far doesn't have one.
-				// Let it stay.
+				// Let it stay. The register allocator assumes that all live code in
+				// the function can be traversed by starting at all the RET instructions
+				// and following predecessor links. If we remove the final RET,
+				// this assumption will not hold in the case of an infinite loop
+				// at the end of a function.
+				// Keep the RET but mark it dead for the liveness analysis.
+				p->mode = -1;
 			} else {
 				if(debug['R'] && debug['v'])
 					print("del %P\n", p);

この変更は、fixjmp関数内でデッドコードエリミネーションを行う際のロジックを修正しています。 p->opt == deadは、現在の命令pが到達不能（デッドコード）であることを示します。 if(p->link == P && p->as == ARET && last && last->as != ARET)という条件は、以下の状況を特定します。

  • p->link == P: pが命令リストの最後である（次の命令がない）。
  • p->as == ARET: pがARET命令である。
  • last && last->as != ARET: 直前の命令がARETではない（つまり、このARETが関数の最後のARETである可能性が高い）。

この条件が満たされ、かつpがデッドコードである場合、このARETはレジスタ割り当ての要件のために削除されずに残されます。しかし、ライブネス解析がこれを無視できるように、p->mode = -1が設定されます。コメントにもあるように、これはレジスタアロケータの仮定（すべてのライブコードはRET命令からたどれる）を維持しつつ、ライブネス解析からはこのRETを「デッド」として扱うためのものです。

test/live.go の変更

--- a/test/live.go
+++ b/test/live.go
@@ -113,3 +113,11 @@ func f9() bool {
 	x := i9
 	return x != 99
 }
+
+// liveness formerly confused by UNDEF followed by RET,
+// leading to "live at entry to f10: ~r1" (unnamed result).
+
+func f10() string {
+	panic(1)
+}
+

このファイルには、f10()という新しいテスト関数が追加されています。 この関数はpanic(1)を呼び出して終了します。panicは通常の関数のリターンパスをたどらないため、コンパイラ内部ではその後に到達不能なRET命令が生成される可能性があります。 このテストケースは、以前のコンパイラがこのようなシナリオでライブネス解析を誤り、「live at entry to f10: ~r1」（f10の入り口で~r1がライブである）という誤った結果を出力していた問題を再現し、修正が正しく適用されたことを検証するために使用されます。~r1は、Goコンパイラが生成する内部的なレジスタ名または一時変数名であり、この場合は関数の戻り値に関連するものです。panicする関数では戻り値は存在しないため、これがライブであると報告されるのは誤りです。

関連リンク

参考にした情報源リンク

  • Go言語のコンパイラに関する一般的な情報 (Go compiler internals, liveness analysis, register allocation):
    • Goの公式ドキュメントやブログ記事
    • Goのソースコード（特にsrc/cmd/gcディレクトリ）
    • コンパイラ理論に関する一般的な教科書やオンラインリソース
  • このコミットの具体的な内容を理解するために、コミットメッセージとコードの差分を詳細に分析しました。
  • Goコンパイラの内部構造に関する情報は、Goのソースコード自体が最も信頼できる情報源です。