[インデックス 18267] ファイルの概要
このコミットは、Goコンパイラのcmd/gcにおける、アドレスが取られているがヒープにエスケープしない変数（非エスケープアドレス取得変数）のライブネス解析を改善するものです。具体的には、これらの変数がスタックフレーム内に保持されるように、ビットマップの精度を向上させます。これにより、以前のライブネス解析が抱えていた「ずさんな（sloppy）」および「バグのある（buggy）」挙動を修正し、ガベージコレクションの正確性を高めるための基盤を築きます。
コミット
- コミットハッシュ:
ca9975a45e3597fc81418c85d95175249500cd7b - Author: Russ Cox rsc@golang.org
- Date: Thu Jan 16 10:32:30 2014 -0500
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/ca9975a45e3597fc81418c85d95175249500cd7b
元コミット内容
cmd/gc: handle non-escaping address-taken variables better
This CL makes the bitmaps a little more precise about variables
that have their address taken but for which the address does not
escape to the heap, so that the variables are kept in the stack frame
rather than allocated on the heap.
The code before this CL handled these variables by treating every
return statement as using every such variable and depending on
liveness analysis to essentially treat the variable as live during the
entire function. That approach has false positives and (worse) false
negatives. That is, it's both sloppy and buggy:
func f(b1, b2 bool) { // x live here! (sloppy)
if b2 {
print(0) // x live here! (sloppy)
return
}
var z **int
x := new(int)
*x = 42
z = &x
print(**z) // x live here (conservative)
if b2 {
print(1) // x live here (conservative)
return
}
for {
print(**z) // x not live here (buggy)
}
}
The first two liveness annotations (marked sloppy) are clearly
wrong: x cannot be live if it has not yet been declared.
The last liveness annotation (marked buggy) is also wrong:
x is live here as *z, but because there is no return statement
reachable from this point in the code, the analysis treats x as dead.
This CL changes the liveness calculation to mark such variables
live exactly at points in the code reachable from the variable
declaration. This keeps the conservative decisions but fixes
the sloppy and buggy ones.
The CL also detects ambiguously live variables, those that are
being marked live but may not actually have been initialized,
such as in this example:
func f(b1 bool) {
var z **int
if b1 {
x := new(int)
*x = 42
z = &x
} else {
y := new(int)
*y = 54
z = &y
}
print(**z) // x, y live here (conservative)
}
Since the print statement is reachable from the declaration of x,
x must conservatively be marked live. The same goes for y.
Although both x and y are marked live at the print statement,
clearly only one of them has been initialized. They are both
"ambiguously live".
These ambiguously live variables cause problems for garbage
collection: the collector cannot ignore them but also cannot
depend on them to be initialized to valid pointer values.
Ambiguously live variables do not come up too often in real code,
but recent changes to the way map and interface runtime functions
are invoked has created a large number of ambiguously live
compiler-generated temporary variables. The next CL will adjust
the analysis to understand these temporaries better, to make
ambiguously live variables fairly rare.
Once ambiguously live variables are rare enough, another CL will
introduce code at the beginning of a function to zero those
slots on the stack. At that point the garbage collector and the
stack copying routines will be able to depend on the guarantee that
if a slot is marked as live in a liveness bitmap, it is initialized.
R=khr
CC=golang-codereviews, iant
https://golang.org/cl/51810043
変更の背景
このコミットの主な背景は、Goコンパイラのライブネス解析における既存の不正確さと、それがガベージコレクション（GC）に与える悪影響を解決することにあります。
以前のGoコンパイラでは、アドレスが取られているがヒープにエスケープしない変数（例えば、&xのようにアドレスが参照されるが、そのアドレス自体が関数スコープ外に渡されないローカル変数）のライブネス解析が不正確でした。具体的には、以下の問題がありました。
-
過剰なライブネスの検出（Sloppy）:
- コミットメッセージの例にあるように、変数がまだ宣言されていないコードパスでも「ライブ」と誤って判断されることがありました。これは、すべての
return文がそのような変数を「使用している」と見なし、ライブネス解析が関数全体で変数をライブとして扱うことに依存していたためです。 - これにより、実際には不要な期間も変数がライブであるとマークされ、スタックフレームのサイズが不必要に大きくなったり、GCが不要な領域をスキャンしたりする可能性がありました。
- コミットメッセージの例にあるように、変数がまだ宣言されていないコードパスでも「ライブ」と誤って判断されることがありました。これは、すべての
-
ライブネスの検出漏れ（Buggy）:
- 無限ループ内の変数など、
return文から到達できないコードパスでは、実際にはライブであるにもかかわらず、変数が「デッド」と誤って判断されることがありました。これは、GCが解放してはならないメモリを誤って解放してしまう、あるいはポインタが指すデータが破壊されるといった深刻なバグにつながる可能性があります。
- 無限ループ内の変数など、
-
曖昧なライブ変数（Ambiguously Live Variables）の発生:
- 条件分岐（
if/else）などで、複数の異なる変数が同じポインタ変数に代入される場合、そのポインタ変数が参照する元の変数のうち、実際に初期化されているのは一つだけであるにもかかわらず、両方の変数が「ライブ」とマークされる状況が発生しました。 - これらの「曖昧なライブ変数」は、GCにとって大きな問題となります。GCはライブとマークされた変数を無視できませんが、それらが有効なポインタ値に初期化されているかどうかに依存することもできません。これは、GCが不正なメモリをスキャンしたり、クラッシュを引き起こしたりするリスクを伴います。
- 条件分岐（
特に、最近のmapやインターフェースのランタイム関数の呼び出し方法の変更により、コンパイラが生成する一時変数で曖昧なライブ変数が大量に発生するようになっていました。この問題は、GCの正確性と効率性を確保するために、早急な解決が必要とされていました。
このコミットは、これらの問題を解決し、より正確なライブネス解析を実現するための第一歩となります。最終的な目標は、ライブネスビットマップにライブとマークされたスロットが常に初期化されているという保証をGCに提供することです。
前提知識の解説
このコミットを理解するためには、以下のGoコンパイラとランタイムに関する基本的な概念を理解しておく必要があります。
1. ライブネス解析 (Liveness Analysis)
ライブネス解析は、コンパイラのデータフロー解析の一種で、プログラムの特定のポイントにおいて、ある変数が「ライブ（live）」であるか「デッド（dead）」であるかを決定します。
- ライブ変数: その変数の値が将来的にプログラムによって使用される可能性がある場合、その変数はライブであると見なされます。
- デッド変数: その変数の値が将来的に使用されることがない場合、その変数はデッドであると見なされます。デッド変数が占めるメモリは、再利用または解放することができます。
ライブネス解析は、レジスタ割り当て、デッドコード削除、そして特にガベージコレクションにおいて非常に重要です。GCは、ライブなオブジェクトのみを保持し、デッドなオブジェクトが占めるメモリを回収します。
2. ガベージコレクション (Garbage Collection, GC)
ガベージコレクションは、プログラムが動的に割り当てたメモリのうち、もはや使用されていない（到達不能な）領域を自動的に解放するプロセスです。Go言語はトレース型GCを採用しており、ライブネス解析の結果を利用して、どのオブジェクトがライブであるかを判断します。
- ポインタ: Goでは、変数が他のメモリ位置を指す場合、それはポインタです。GCはポインタをたどって、到達可能なオブジェクトをライブとマークします。
- スタックとヒープ:
- スタック: 関数呼び出しやローカル変数が一時的に格納されるメモリ領域です。通常、LIFO（後入れ先出し）方式で管理され、高速です。変数がスタックに割り当てられるかヒープに割り当てられるかは、エスケープ解析によって決定されます。
- ヒープ: プログラムが実行時に動的にメモリを割り当てる領域です。スタックよりも管理が複雑で、GCの対象となります。
3. エスケープ解析 (Escape Analysis)
Goコンパイラは、変数がスタックに割り当てられるべきか、それともヒープに割り当てられるべきかを決定するためにエスケープ解析を実行します。
- スタック割り当て: 変数が関数のスコープ外に「エスケープ」しない場合、その変数はスタックに割り当てられます。スタックに割り当てられた変数は、関数が終了すると自動的に解放されるため、GCの負担を軽減できます。
- ヒープ割り当て: 変数が関数のスコープ外にエスケープする場合（例えば、グローバル変数に代入されたり、他の関数にポインタとして渡されたりする場合）、その変数はヒープに割り当てられます。ヒープに割り当てられた変数は、GCによって管理されます。
このコミットで言及されている「アドレスが取られているがヒープにエスケープしない変数」とは、&xのようにアドレスが参照されるものの、そのアドレスが関数の外に渡されないローカル変数を指します。これらの変数はスタックに割り当てられるべきですが、そのライブネス解析が複雑になります。
4. ビットマップ (Bitmap)
ビットマップは、メモリ上の特定の領域（例えば、スタックフレームやヒープ上のオブジェクト）にポインタが含まれているかどうかを示すために使用されるデータ構造です。各ビットが特定のメモリワードに対応し、そのワードがポインタであるか（GCがスキャンする必要があるか）どうかを示します。GCはこれらのビットマップを使用して、ライブなポインタを効率的に識別し、追跡します。
5. 制御フローグラフ (Control Flow Graph, CFG) と基本ブロック (Basic Block)
- 基本ブロック: プログラムの実行において、入り口が一つで出口が一つであるような、連続した命令のシーケンスです。基本ブロック内では、常に最初の命令から最後の命令まで実行されます。
- 制御フローグラフ (CFG): プログラムのすべての基本ブロックをノードとし、ブロック間の可能な実行パスをエッジとするグラフです。コンパイラはCFGを使用して、データフロー解析（ライブネス解析など）を実行します。
6. データフロー解析 (Dataflow Analysis)
データフロー解析は、プログラムの実行中に変数の値がどのように伝播するかを分析するコンパイラ技術です。ライブネス解析はデータフロー解析の一種であり、CFG上を情報を伝播させることで、変数のライブネスを決定します。
- 順方向解析 (Forward Analysis): プログラムの開始から終了に向かって情報を伝播させます。
- 逆方向解析 (Backward Analysis): プログラムの終了から開始に向かって情報を伝播させます。ライブネス解析は通常、逆方向解析で行われます。
技術的詳細
このコミットは、Goコンパイラのライブネス解析、特にアドレスが取られているがヒープにエスケープしない変数（以下、「アドレス取得変数」）の扱いを大幅に改善します。
1. ライブネス計算の変更点
以前のライブネス解析は、アドレス取得変数について、すべてのreturn文がその変数を使用していると見なし、結果として関数全体でライブであると保守的に判断していました。これは、変数が宣言される前や、到達不能なコードパスでもライブとマークされる「ずさんな」または「バグのある」挙動を引き起こしていました。
このコミットでは、ライブネス計算を以下のように変更します。
- 変数の宣言から到達可能なコードポイントでのみライブとマーク: アドレス取得変数は、その変数が宣言された場所から到達可能なコードポイントでのみライブとマークされるようになります。これにより、変数が宣言される前のコードパスでライブと誤って判断される問題が解消されます。
avarinitビットベクトルの導入:Liveness構造体にavarinit、avarinitany、avarinitallという新しいビットベクトルが追加されました。avarinit: 個々の命令がアドレス取得変数を初期化または参照したことを示すビットベクトルです。avarinitany: ある基本ブロックの出口で、アドレス取得変数が「いずれかのパスで」初期化されている可能性があることを示すビットベクトルです。avarinitall: ある基本ブロックの出口で、アドレス取得変数が「すべてのパスで」確実に初期化されていることを示すビットベクトルです。
2. データフロー解析の改善
livenesssolve関数において、avarinitanyとavarinitallの順方向データフロー解析が追加されました。
avarinitanyの計算: 各基本ブロックのavarinitanyは、そのブロックの先行ブロックのavarinitanyの論理和（OR）と、そのブロック内で初期化されたアドレス取得変数（avarinit）の論理和によって計算されます。これは、変数が「いずれかのパスで」初期化されたかどうかを追跡します。avarinitallの計算: 各基本ブロックのavarinitallは、そのブロックの先行ブロックのavarinitallの論理積（AND）と、そのブロック内で初期化されたアドレス取得変数（avarinit）の論理和によって計算されます。これは、変数が「すべてのパスで」初期化されたかどうかを追跡します。
これらのビットベクトルは、変数の初期化状態に関するより正確な情報を提供し、特に「曖昧なライブ変数」の検出と対処に役立ちます。
3. 曖昧なライブ変数の検出と対処
コミットメッセージの例にあるように、条件分岐によって異なる変数が同じポインタ変数に代入される場合、両方の変数がライブとマークされる「曖昧なライブ変数」が発生していました。
- 検出ロジック:
livenessepilogue関数内で、any &^ all（anyに含まれるがallには含まれないビット）を計算することで、曖昧なライブ変数を検出します。これは、変数が「いずれかのパスで」初期化されたが、「すべてのパスで」初期化されたわけではないことを意味します。 - 警告の出力:
debuglive >= 3の場合、曖昧なライブ変数が検出されると警告が出力されます。これにより、コンパイラ開発者はこれらの問題のあるケースを特定できます。 - 将来の計画: コミットメッセージでは、曖昧なライブ変数が稀になるように、次のコミットで一時変数の解析を調整する計画が述べられています。さらに、曖昧なライブ変数が十分に稀になった後、関数の開始時にスタック上のこれらのスロットをゼロ初期化するコードを導入する計画も示されています。これにより、GCとスタックコピールーチンは、ライブネスビットマップでライブとマークされたスロットが常に初期化されているという保証に依存できるようになります。
4. デバッグ出力の改善
-liveフラグのレベルが拡張され、より詳細なデバッグ情報が出力されるようになりました。-live=1: セーフポイントでのライブネスリストをコード警告として出力。-live=2: ライブネスアノテーション付きのアセンブリリストを出力。-live=3: 各計算フェーズ中の詳細な情報を出力。
livenessprintdebug関数が追加され、複数のパスで利用される情報を統合して表示できるようになりました。
これらの変更により、Goコンパイラのライブネス解析はより正確になり、ガベージコレクションの信頼性と効率性が向上するための重要な基盤が築かれました。
コアとなるコードの変更箇所
このコミットでは、主に以下のファイルが変更されています。
src/cmd/gc/bv.c:- ビットベクトル操作のための新しい関数
bvand（論理積）が追加されました。これは、avarinitallの計算などで使用されます。
- ビットベクトル操作のための新しい関数
src/cmd/gc/go.h:bvand関数のプロトタイプが追加されました。Liveness構造体にavarinit、avarinitany、avarinitallという新しいビットベクトルポインタが追加されました。
src/cmd/gc/pgen.c:cmpstackvar関数で、スタック変数の比較ロジックが変更され、名前による比較が追加されました。これは直接的なライブネス解析の変更ではありませんが、関連するコンパイラの内部処理の調整です。
src/cmd/gc/plive.c:- ライブネス解析の主要なロジックが含まれるファイルで、最も大きな変更が行われました。
Liveness構造体の定義が更新され、新しいavarinit関連のビットベクトルが追加されました。progeffects関数が変更され、avarinitビットベクトルを引数として受け取るようになりました。この関数は、個々の命令がアドレス取得変数を初期化または参照したことを記録します。newliveness関数で、新しいビットベクトルの割り当てが行われます。freeliveness関数で、新しいビットベクトルの解放が行われます。livenessprologue関数で、avarinitビットベクトルの計算が組み込まれました。livenesssolve関数で、avarinitanyとavarinitallの順方向データフロー解析が追加されました。livenessepilogue関数で、曖昧なライブ変数の検出ロジックと、デバッグ出力の調整が行われました。また、twobitlivepointermapの呼び出しロジックも変更されました。- 新しいデバッグ出力関数
livenessprintdebugが追加されました。 liveness関数のデバッグ出力制御が改善されました。
- ライブネス解析の主要なロジックが含まれるファイルで、最も大きな変更が行われました。
test/live.go:- 新しいテストファイルが追加され、このコミットで修正されたライブネス解析の挙動（特に「ずさんな」と「バグのある」ケース、および曖昧なライブ変数）が正しく処理されることを検証します。
コアとなるコードの解説
このコミットの核心は、src/cmd/gc/plive.cにおけるライブネス解析のロジックの変更にあります。
Liveness構造体の拡張
struct Liveness {
// ... 既存のフィールド ...
Bvec **avarinit; // addrtaken variables set or used (proof of initialization)
Bvec **avarinitany; // addrtaken variables possibly initialized at block exit
Bvec **avarinitall; // addrtaken variables certainly initialized at block exit
// ... 既存のフィールド ...
};
avarinitは、特定の基本ブロック内でアドレス取得変数が初期化または使用されたことを示すビットベクトルです。avarinitanyとavarinitallは、それぞれ「いずれかのパスで初期化された可能性」と「すべてのパスで確実に初期化された」ことを追跡するためのビットベクトルで、データフロー解析によって計算されます。
progeffects関数の変更
static void
progeffects(Prog *prog, Array *vars, Bvec *uevar, Bvec *varkill, Bvec *avarinit)
{
// ...
// from->node->addrtaken または to->node->addrtaken の場合、avarinit にセット
if(from->node->addrtaken)
bvset(avarinit, pos);
// ...
if(to->node->addrtaken)
bvset(avarinit, pos);
// ...
}
この関数は、個々の命令（Prog）が変数に与える影響を計算します。変更点として、アドレスが取られている変数（node->addrtakenが真）が命令によって読み書きされる場合、新しく追加されたavarinitビットベクトルにその変数のビットをセットするようになりました。これにより、変数の初期化または使用の証拠が記録されます。
livenesssolve関数における順方向データフロー解析
static void
livenesssolve(Liveness *lv)
{
// ...
// Push avarinitall, avarinitany forward.
// avarinitall says the addressed var is initialized along all paths reaching the block exit.
// avarinitany says the addressed var is initialized along some path reaching the block exit.
for(i = 0; i < arraylength(lv->cfg); i++) {
bb = *(BasicBlock**)arrayget(lv->cfg, i);
rpo = bb->rpo;
if(i == 0)
bvcopy(lv->avarinitall[rpo], lv->avarinit[rpo]);
else {
bvresetall(lv->avarinitall[rpo]);
bvnot(lv->avarinitall[rpo]); // 全ビットをセット (初期値として)
}
bvcopy(lv->avarinitany[rpo], lv->avarinit[rpo]);
}
change = 1;
while(change != 0) {
change = 0;
for(i = 0; i < arraylength(lv->cfg); i++) {
bb = *(BasicBlock**)arrayget(lv->cfg, i);
rpo = bb->rpo;
bvresetall(any);
bvresetall(all);
for(j = 0; j < arraylength(bb->pred); j++) { // 各先行ブロックを処理
pred = *(BasicBlock**)arrayget(bb->pred, j);
if(j == 0) {
bvcopy(any, lv->avarinitany[pred->rpo]);
bvcopy(all, lv->avarinitall[pred->rpo]);
} else {
bvor(any, any, lv->avarinitany[pred->rpo]); // any は OR
bvand(all, all, lv->avarinitall[pred->rpo]); // all は AND
}
}
bvor(any, any, lv->avarinit[rpo]); // 現在のブロックの avarinit を OR
bvor(all, all, lv->avarinit[rpo]); // 現在のブロックの avarinit を OR
// 変更があれば change = 1
if(bvcmp(any, lv->avarinitany[rpo])) {
change = 1;
bvcopy(lv->avarinitany[rpo], any);
}
if(bvcmp(all, lv->avarinitall[rpo])) {
change = 1;
bvcopy(lv->avarinitall[rpo], all);
}
}
}
// ... 既存のライブネス解析 (逆方向) ...
}
livenesssolve関数は、ライブネス解析のデータフロー方程式を解く部分です。このコミットでは、従来の逆方向ライブネス解析（livein/liveoutの計算）に加えて、avarinitanyとavarinitallの順方向データフロー解析が追加されました。
avarinitanyは、先行ブロックのavarinitanyの論理和（OR）と現在のブロックのavarinitの論理和を取ることで、いずれかのパスで初期化された可能性を伝播させます。avarinitallは、先行ブロックのavarinitallの論理積（AND）と現在のブロックのavarinitの論理和を取ることで、すべてのパスで初期化された確実性を伝播させます。
この順方向解析は、曖昧なライブ変数を正確に特定するための重要なステップです。
livenessepilogue関数における曖昧なライブ変数の検出
static void
livenessepilogue(Liveness *lv)
{
// ...
for(i = 0; i < arraylength(lv->cfg); i++) {
bb = *(BasicBlock**)arrayget(lv->cfg, i);
// ... avarinitany と avarinitall の計算 (livenesssolve と同様のロジック) ...
for(p = bb->first;; p = p->link) {
progeffects(p, lv->vars, uevar, varkill, avarinit);
bvor(any, any, avarinit);
bvor(all, all, avarinit);
if(issafepoint(p)) {
if(debuglive >= 3) {
// Diagnose ambiguously live variables (any &^ all).
bvresetall(livein); // livein は一時変数として使用
bvandnot(liveout, any, all); // liveout = any AND NOT all
if(bvcmp(livein, liveout) != 0) { // liveout が空でなければ
for(pos = 0; pos < liveout->n; pos++) {
if(bvget(liveout, pos)) {
n = *(Node**)arrayget(lv->vars, pos);
if(!n->diag && strncmp(n->sym->name, "autotmp_", 8) != 0) {
n->diag = 1;
warnl(p->lineno, "%N: %lN is ambiguously live", curfn->nname, n);
}
}
}
bvset(all, pos); // silence future warnings in this block
}
}
// ... ライブポインタビットマップの記録 ...
}
// ...
}
// ...
}
// ...
}
livenessepilogue関数は、ライブネス解析の最終処理を行います。ここで、各セーフポイント（GCがスタックをスキャンできるポイント）において、anyとallビットベクトルを使用して曖昧なライブ変数を検出します。
bvandnot(liveout, any, all)は、anyに含まれるがallには含まれないビットをliveoutにセットします。これは、変数が「いずれかのパスで初期化されたが、すべてのパスで初期化されたわけではない」状態、すなわち「曖昧にライブ」な状態を示します。このような変数が検出された場合、デバッグレベルに応じて警告が出力されます。
また、この関数内でtwobitlivepointermapが呼び出される前に、avarinitロジックによって追加されたビットが考慮されるようになりました。これにより、アドレス取得変数のライブネス情報が正確にGCビットマップに反映されます。
これらの変更は、Goコンパイラがスタック上のポインタをより正確に追跡し、ガベージコレクタがより効率的かつ安全に動作するための基盤を強化します。
関連リンク
参考にした情報源リンク
- Go言語のGCについて - Qiita (一般的なGo GCの概念理解のため)
- Goのコンパイラ最適化 - エスケープ解析 - Qiita (エスケープ解析の概念理解のため)
- Liveness Analysis - Wikipedia (ライブネス解析の一般的な概念理解のため)
- Control-flow graph - Wikipedia (制御フローグラフの一般的な概念理解のため)
- Data-flow analysis - Wikipedia (データフロー解析の一般的な概念理解のため)
- Go compiler source code (cmd/gc/plive.c) (コミット内容の理解のため)
- Go compiler source code (cmd/gc/bv.c) (ビットベクトル操作の理解のため)
- Go compiler source code (cmd/gc/go.h) (構造体定義の理解のため)
- Go compiler source code (cmd/gc/pgen.c) (関連ファイルの理解のため)
- Go compiler source code (test/live.go) (テストケースの理解のため)