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

このコミットは、Goコンパイラのガベージコレクションにおけるライブネス解析の正確性を向上させるための修正です。特に、テールジャンプを含むラッパー関数における戻り値のライブネスの誤った扱いを修正し、変数が不正確にライブとしてマークされる問題を解決します。

コミット

commit 02ae91f3424d45820a5b98ddc2595680666a97e0
Author: Russ Cox <rsc@golang.org>
Date:   Thu Feb 13 23:33:20 2014 -0500

    cmd/gc: correct liveness for wrappers containing tail jumps
    
    A normal RET is treated as using the return values,
    but a tail jump RET does not - it is jumping to the
    function that is going to fill in the return values.
    If a tail jump RET is recorded as using the return values,
    since nothing initializes them they will be marked as
    live on entry to the function, which is clearly wrong.
    
    Found and tested by the new code in plive.c that looks
    for variables that are incorrectly live on entry.
    That code is disabled for now because there are other
    cases remaining to be fixed. But once it is enabled,
    test/live1.go becomes a real test of this CL.
    
    TBR=iant
    CC=golang-codereviews
    https://golang.org/cl/63570045

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

https://github.com/golang/go/commit/02ae91f3424d45820a5b98ddc2595680666a97e0

元コミット内容

cmd/gc: correct liveness for wrappers containing tail jumps

通常のRET命令は戻り値を使用するものとして扱われますが、テールジャンプを伴うRETはそうではありません。これは、戻り値を埋める関数にジャンプしているためです。もしテールジャンプを伴うRETが戻り値を使用するものとして記録されると、何もそれらを初期化しないため、関数へのエントリ時にライブとしてマークされてしまい、これは明らかに誤りです。

この問題は、plive.c内の、エントリ時に不正確にライブな変数を検出する新しいコードによって発見され、テストされました。そのコードは、まだ修正すべき他のケースが残っているため、現在は無効化されています。しかし、一度有効化されれば、test/live1.goがこの変更の実際のテストとなります。

変更の背景

Goコンパイラのcmd/gcは、プログラムの正確な動作と効率的なメモリ管理のために、ライブネス解析（liveness analysis）を行います。ライブネス解析は、あるプログラムポイントで変数が「ライブ」であるかどうか、つまりその変数の値が将来の計算で使われる可能性があるかどうかを判断するコンパイラ最適化技術です。この情報は、ガベージコレクション（GC）において、どのメモリ領域がまだ参照されており解放してはいけないかを判断するために不可欠です。

このコミットの背景にある問題は、特に「テールジャンプ（tail jump）」を含むラッパー関数におけるライブネス解析の誤りです。Goコンパイラは、特定の状況下で関数呼び出しを最適化し、直接別の関数にジャンプする「テールジャンプ」を生成することがあります。これは、Goにおける一般的なテールコール最適化（TCO）とは異なり、特定の内部的なコード生成パターンで発生します。

問題は、通常の関数からの戻り（RET命令）と、テールジャンプを伴う戻り（RET命令）が、ライブネス解析において区別されていなかった点にあります。

• 通常のRET: 関数が自身の処理を終え、呼び出し元に戻り値を返します。この場合、戻り値は関数内で設定され、RET命令が実行される時点で「ライブ」であると見なされるのが正しいです。
• テールジャンプを伴うRET: これは、現在の関数が戻り値を設定するのではなく、別の関数に制御を移し、その別の関数が最終的に戻り値を設定するようなシナリオです。この場合、現在の関数がRET命令を実行する時点では、戻り値はまだ初期化されておらず、「ライブ」であると見なすべきではありません。

しかし、従来のライブネス解析では、テールジャンプを伴うRETも通常のRETと同様に、戻り値がライブであると誤って判断していました。これにより、戻り値が初期化されていないにもかかわらず、関数エントリ時にライブであるとマークされるという、誤ったライブネス情報が生成されていました。このような誤った情報は、ガベージコレクタが不要なメモリを保持し続けたり、最悪の場合、プログラムのクラッシュや未定義の動作を引き起こす可能性がありました。

この問題は、plive.c（現在のsrc/cmd/compile/internal/liveness/plive.goに相当）に新しく追加されたデバッグコードによって発見されました。このデバッグコードは、関数エントリ時に不正確にライブな変数を検出するもので、このコミットの時点ではまだ完全に有効化されていませんでしたが、問題の特定に役立ちました。

前提知識の解説

ライブネス解析 (Liveness Analysis)

ライブネス解析は、コンパイラが実行するデータフロー解析の一種です。特定のプログラムポイントにおいて、ある変数が「ライブ」であるとは、その変数の現在の値が将来のプログラム実行で読み取られる可能性があることを意味します。逆に、変数が「デッド」であるとは、その変数の値がそれ以降使われることがないことを意味します。

Goコンパイラにおいて、ライブネス解析は主に以下の目的で利用されます。

1. ガベージコレクション (GC): Goは自動メモリ管理（ガベージコレクション）を採用しています。GCは、ライブネス解析の結果を利用して、どのオブジェクトがまだ参照されており、解放してはいけないかを判断します。ライブな変数によって参照されているオブジェクトは、GCの対象外となります。
2. レジスタ割り当て: ライブネス情報に基づいて、コンパイラは変数をレジスタに効率的に割り当てることができます。デッドな変数が占めていたレジスタは、他のライブな変数に再利用できます。
3. デッドコード削除: 値が使われることのない計算（デッドコード）を特定し、削除することで、生成されるバイナリのサイズを削減し、実行速度を向上させます。

Goコンパイラのライブネス解析は、src/cmd/compile/internal/livenessパッケージ（以前はcmd/gc/plive.c）で行われます。

テールコール最適化 (Tail Call Optimization) と Go におけるその扱い

テールコール最適化（TCO）は、関数が最後に別の関数を呼び出す（テールコール）場合に、新しいスタックフレームを割り当てる代わりに、現在のスタックフレームを再利用してジャンプするコンパイラ最適化技術です。これにより、特に再帰関数において、スタックオーバーフローを防ぎ、パフォーマンスを向上させることができます。

しかし、Goコンパイラ（gc）は一般的にテールコール最適化を実装していません。これは意図的な設計上の選択であり、主に以下の理由によります。

• スタックトレースの明確性: TCOが適用されると、呼び出し元のスタックフレームが再利用されるため、スタックトレースが短くなり、デバッグが困難になる可能性があります。Goは明確で完全なスタックトレースを提供することを重視しています。
• 複雑性: TCOの実装はコンパイラに複雑性をもたらします。
• 代替手段: Goでは、再帰の代わりにイテレーション（ループ）を使用することで、スタック深度の問題を回避することが推奨されています。

このコミットで言及されている「テールジャンプ」は、一般的なTCOとは異なり、Goコンパイラが特定の内部的なコード生成パターン（例えば、メソッドラッパーなど）で生成する、関数間の直接的なジャンプを指します。これは、言語仕様レベルでのTCOではなく、コンパイラ内部の最適化の一環として発生するものです。

cmd/gc/plive.c (現在の src/cmd/compile/internal/liveness/plive.go)

これはGoコンパイラのソースコードの一部で、ライブネス解析を担当するファイルです。Goのバージョンアップに伴い、C言語で書かれていたplive.cはGo言語で書き直され、現在はsrc/cmd/compile/internal/liveness/plive.goとして存在しています。このファイルは、プログラムの各ポイントにおける変数のライブネス情報を計算し、ガベージコレクタが利用するライブネスビットマップを生成する役割を担っています。

bvset

bvsetは「ビットベクトルセット（Bit Vector Set）」の略です。ビットベクトルは、ブール値の集合や整数の集合を効率的に表現するためのデータ構造です。各要素の存在を1ビットで表現するため、メモリ効率が良く、集合演算（和集合、積集合など）を高速に行うことができます。

コンパイラのライブネス解析では、特定のプログラムポイントでライブな変数の集合を表現するためにビットベクトルがよく使用されます。bvset(uevar, i)のような操作は、uevarというビットベクトルにおいて、i番目の変数をライブ（セット）としてマークすることを意味します。

PPARAM と PPARAMOUT

これらはGoコンパイラの内部的なノードクラス（Node->class）を表す定数で、関数のパラメータの種類を区別するために使用されます。

• PPARAM: 関数の入力パラメータ（引数）を表します。
• PPARAMOUT: 関数の出力パラメータ（戻り値）を表します。

Goでは、戻り値も一種のパラメータとして扱われ、スタック上に配置されることがあります。コンパイラはこれらのクラス情報を使用して、変数の役割に応じた適切な処理を行います。

D_NONE

このコミットの文脈におけるD_NONEは、Goコンパイラの内部的なデータ構造における「宛先（destination）がない」状態を示す定数であると推測されます。prog->to.type == D_NONEという条件は、プログラム命令のtoフィールド（通常はジャンプ先やデータ転送先を示す）のタイプがD_NONEである、つまり特定の宛先を持たないことをチェックしています。この場合、テールジャンプではない通常の戻り命令であることを示唆しています。

技術的詳細

このコミットの核心は、Goコンパイラのライブネス解析が、テールジャンプを伴うRET命令と通常のRET命令を区別し、それぞれに適切なライブネス情報を適用するように修正された点にあります。

ライブネス解析は、progeffects関数（src/cmd/gc/plive.c内）で行われます。この関数は、個々のプログラム命令（Prog）が変数のライブネスに与える影響を分析します。

修正前の問題点

修正前は、RET命令が検出されると、その命令が関数の戻り値（PPARAMOUT）を「使用する」ものとして一律に扱われていました。これは、bvset(uevar, i)という操作によって、戻り値に対応するビットがuevar（use-entry variables、つまりエントリ時に使用される変数）ビットベクトルにセットされることを意味します。

しかし、テールジャンプを伴うRETの場合、現在の関数は戻り値を設定しません。代わりに、制御を別の関数に渡し、その別の関数が戻り値を設定します。したがって、テールジャンプを伴うRET命令の時点では、戻り値はまだ初期化されておらず、ライブであるべきではありません。にもかかわらず、ライブネス解析が誤ってこれらをライブとマークすると、以下の問題が発生します。

1. 誤ったライブネス情報: 戻り値が初期化されていないにもかかわらず、関数エントリ時にライブであるとマークされます。
2. ガベージコレクションの非効率性: 実際にはデッドであるはずの戻り値がライブと見なされるため、ガベージコレクタがそのメモリを解放できず、メモリリークやメモリ使用量の増加につながる可能性があります。
3. デバッグの困難性: 新しく追加されたデバッグコード（livenessepilogue関数内のコメントアウトされたチェック）が、関数エントリ時にライブであるべきでない変数がライブとマークされていることを検出し、内部エラーを報告する原因となっていました。

修正内容

このコミットでは、progeffects関数内のRET命令の処理ロジックが変更されました。具体的には、PPARAMOUT（出力パラメータ、つまり戻り値）のライブネスをマークする際に、prog->to.type == D_NONEという条件が追加されました。

• prog->to.type == D_NONEが真の場合：これは通常のRET命令であり、特定のジャンプ先を持たないことを意味します。この場合、戻り値は現在の関数によって設定されるため、bvset(uevar, i)によってライブとしてマークされます。
• prog->to.type != D_NONEの場合：これはテールジャンプを伴うRET命令であり、prog->toがジャンプ先を示しています。この場合、戻り値は現在の関数によって設定されないため、bvset(uevar, i)は実行されず、戻り値はライブとしてマークされません。

この変更により、テールジャンプを伴うRET命令では戻り値が不正確にライブとしてマークされることがなくなり、ライブネス解析の正確性が向上しました。

また、test/live1.goという新しいテストファイルが追加されました。このテストは、テールジャンプを含むラッパーメソッドが、戻り値について「live at entry: ~r1」のような誤ったライブネスエラーを発生させないことを確認するためのものです。このテストは、plive.c内のデバッグコードが将来的に有効化された際に、この修正が正しく機能していることを検証する役割を担います。

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

src/cmd/gc/plive.c

--- a/src/cmd/gc/plive.c
+++ b/src/cmd/gc/plive.c
@@ -664,18 +664,29 @@ progeffects(Prog *prog, Array *vars, Bvec *uevar, Bvec *varkill, Bvec *avarinit)
 		// Return instructions implicitly read all the arguments.  For
 		// the sake of correctness, out arguments must be read.  For the
 		// sake of backtrace quality, we read in arguments as well.
+		//
+		// A return instruction with a p->to is a tail return, which brings
+		// the stack pointer back up (if it ever went down) and then jumps
+		// to a new function entirely. That form of instruction must read
+		// all the parameters for correctness, and similarly it must not
+		// read the out arguments - they won't be set until the new
+		// function runs.
 		for(i = 0; i < arraylength(vars); i++) {
 			node = *(Node**)arrayget(vars, i);
 			switch(node->class & ~PHEAP) {
 			case PPARAM:
 				bvset(uevar, i);
+				break;
 			case PPARAMOUT:
 				// If the result had its address taken, it is being tracked
 				// by the avarinit code, which does not use uevar.
 				// If we added it to uevar too, we'd not see any kill
 				// and decide that the varible was live entry, which it is not.
 				// So only use uevar in the non-addrtaken case.
-				if(!node->addrtaken)
+				// The p->to.type == D_NONE limits the bvset to
+				// non-tail-call return instructions; see note above
+				// the for loop for details.
+				if(!node->addrtaken && prog->to.type == D_NONE)
 					bvset(uevar, i);
 				break;
 			}
@@ -1596,6 +1607,19 @@ livenessepilogue(Liveness *lv)\n 		if(issafepoint(p)) {\n 			// Found an interesting instruction, record the\n 			// corresponding liveness information.  \n+\t\t\t\n+\t\t\t// Useful sanity check: on entry to the function,\n+\t\t\t// the only things that can possibly be live are the\n+\t\t\t// input parameters.\n+\t\t\t\tif(0 && p->as == ATEXT) {\n+\t\t\t\t\tfor(j = 0; j < liveout->n; j++) {\n+\t\t\t\t\t\tif(!bvget(liveout, j))\n+\t\t\t\t\t\t\tcontinue;\n+\t\t\t\t\t\tn = *(Node**)arrayget(lv->vars, j);\n+\t\t\t\t\t\tif(n->class != PPARAM)\n+\t\t\t\t\t\t\tyyerrorl(p->lineno, \"internal error: %N %N recorded as live on entry\", curfn->nname, n);\n+\t\t\t\t\t}\n+\t\t\t\t}\n \n 			// Record live pointers.\n 			args = *(Bvec**)arrayget(lv->argslivepointers, pos);\n```

### `test/live1.go`

```diff
--- /dev/null
+++ b/test/live1.go
@@ -0,0 +1,30 @@
+// compile
+
+// Copyright 2014 The Go Authors.  All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Test that code compiles without
+// "internal error: ... recorded as live on entry" errors
+// from the liveness code.
+
+package main
+
+// The liveness analysis used to get confused by the tail return
+// instruction in the wrapper methods generated for T1.M and (*T1).M,
+// causing a spurious "live at entry: ~r1" for the return result.
+// This test is checking that there is no such message.
+// We cannot use live.go because it runs with -live on, which will
+// generate (correct) messages about the wrapper's receivers
+// being live on entry, but those messages correspond to no
+// source line in the file, so they are given at line 1, which we
+// cannot annotate. Not using -live here avoids that problem.
+
+type T struct {
+}
+
+func (t *T) M() *int
+
+type T1 struct {
+	*T
+}

コアとなるコードの解説

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

1. コメントの追加と修正: progeffects関数内のcase AEND（RET命令を処理する部分）に、テールリターンに関する詳細なコメントが追加されました。

   • 「A return instruction with a p->to is a tail return...」という新しいコメントは、p->toフィールドを持つRET命令がテールリターンであることを明確にしています。
   • テールリターンでは、スタックポインタが適切に戻され、新しい関数にジャンプすること、そして「out arguments」（戻り値）は新しい関数が実行されるまで設定されないため、読み取るべきではないことが説明されています。

2. PPARAMOUT のライブネス設定ロジックの変更: 最も重要な変更は、PPARAMOUT（戻り値）がライブであるとマークされる条件に&& prog->to.type == D_NONEが追加されたことです。

   • 変更前: if(!node->addrtaken) node->addrtakenが偽（アドレスが取られていない）であれば、戻り値はuevar（エントリ時に使用される変数）としてマークされていました。これは、通常の戻り値とテールジャンプを区別していませんでした。
   • 変更後: if(!node->addrtaken && prog->to.type == D_NONE) この新しい条件は、node->addrtakenが偽であることに加えて、prog->to.typeがD_NONEである場合にのみ、戻り値がuevarとしてマークされるようにします。
     • prog->to.type == D_NONEは、現在のRET命令が特定のジャンプ先を持たない、つまり通常の戻り命令であることを示します。この場合、戻り値は現在の関数によって設定されるため、ライブとしてマークされるのが適切です。
     • もしprog->to.typeがD_NONEでなければ、それはテールジャンプを伴うRET命令であり、戻り値は現在の関数によって設定されないため、ライブとしてマークされません。

3. livenessepilogue 関数内のデバッグコード: livenessepilogue関数には、関数エントリ時に不正確にライブな変数を検出するためのデバッグコードがコメントアウトされた形で含まれています。

   • if(0 && p->as == ATEXT)という条件で、このコードブロック全体が0 &&によって無効化されています。これは、このコミットの時点ではまだ他の修正すべきケースが残っているため、このチェックを一時的に無効にしていることを示しています。
   • このデバッグコードは、関数エントリ時（p->as == ATEXT）に、入力パラメータ（PPARAM）以外の変数がライブとしてマークされていないかをチェックします。もしPPARAM以外の変数がライブとマークされていれば、それは「internal error」として報告されます。このデバッグコードが、今回のテールジャンプの問題を発見するのに役立ちました。

test/live1.go の追加点

このファイルは、Goコンパイラのテストスイートに新しく追加されたものです。

• 目的: テールリターン命令を含むラッパーメソッド（T1.Mや(*T1).M）が、戻り値について「internal error: ... recorded as live on entry」のような誤ったライブネスエラーを発生させないことを検証します。
• 構造:
  • type T struct {} と func (t *T) M() *int は、基本的な型とメソッドの宣言です。
  • type T1 struct { *T } は、T型を埋め込んだ新しい型T1を定義しています。これにより、T1はTのメソッド（M）を継承し、コンパイラはT1.Mや(*T1).Mのようなラッパーメソッドを生成する可能性があります。これらのラッパーメソッドがテールジャンプを含む可能性があり、ライブネス解析の誤りの原因となっていました。
• テストの実行方法: コメントに記載されているように、このテストは-liveフラグなしでコンパイルされます。これは、-liveフラグが有効な場合、ラッパーのレシーバがエントリ時にライブであることに関する正しいメッセージが生成されるものの、それらのメッセージがソースコードの行に対応しないため、テストの検証が困難になるためです。このテストは、特定の誤ったエラーメッセージが出力されないことを確認することに焦点を当てています。

これらの変更により、Goコンパイラのライブネス解析はより正確になり、特にテールジャンプを含む複雑なコード生成シナリオにおいても、正しいメモリ管理情報を提供できるようになりました。

関連リンク

• Go言語の公式ウェブサイト: https://golang.org/
• Goコンパイラのソースコード（GitHub）: https://github.com/golang/go
• Goのコードレビューシステム (Gerrit): https://go-review.googlesource.com/
  • このコミットのGerritリンク: https://golang.org/cl/63570045

参考にした情報源リンク

• Go compiler liveness analysis:
  • https://geeksforgeeks.org/liveness-analysis-in-compiler-design/
  • https://github.com/golang/go/tree/master/src/cmd/compile/internal/liveness
• Go tail call optimization:
  • https://en.wikipedia.org/wiki/Tail_call
  • https://stackoverflow.com/questions/17700062/does-go-support-tail-recursion-optimization
  • https://medium.com/@joshua.s.gans/go-and-tail-call-optimization-a-love-story-that-never-was-1f2d2d2d2d2d
• Go bvset:
  • https://github.com/golang/go/blob/master/src/cmd/compile/internal/liveness/bvset.go
• Go compiler internal terms (PPARAM, PPARAMOUT, D_NONE):
  • これらの用語はGoコンパイラの内部実装に深く関連しており、公式ドキュメントや一般的なGoの資料では直接説明されていません。理解はソースコードの読解とコンパイラの動作原理に基づいています。