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

コミット

commit a7b83f2287bc650e8479445bbe5008e9ccec12ba
Author: Russ Cox <rsc@golang.org>
Date:   Sat Feb 11 00:04:37 2012 -0500

    5g: fix out of registers bug
    
    Same fix as 6g, tripped by the 6g test case.
    
    R=ken2
    CC=golang-dev
    https://golang.org/cl/5651074

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

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

元コミット内容

5g: fix out of registers bug

Same fix as 6g, tripped by the 6g test case.

変更の背景

このコミットは、Go言語のコンパイラである5g（ARMアーキテクチャ向け）における「レジスタ不足（out of registers）」バグを修正するものです。コミットメッセージによると、このバグは6g（AMD64アーキテクチャ向け）コンパイラで既に修正されたものと同じ種類であり、6gのテストケースによって5gでも同様のバグが露呈したことが示唆されています。

コンパイラにおけるレジスタ不足のバグは、コンパイラが利用可能なCPUレジスタを効率的に管理できない場合に発生します。これにより、生成されるアセンブリコードが不正になったり、実行時エラーを引き起こしたりする可能性があります。特に、複雑な式や多くの変数を扱う際に、レジスタ割り当てのロジックに不備があると、このような問題が発生しやすくなります。

この修正は、Goコンパイラの安定性と正確性を向上させるための重要なバグ修正であり、異なるアーキテクチャ向けのコンパイラ間で共通のロジックが使用されていること、および一方のコンパイラのテストケースがもう一方のコンパイラのバグを発見するのに役立ったことを示しています。

前提知識の解説

Goコンパイラ (5g, 6g)

Go言語の初期のコンパイラは、Plan 9オペレーティングシステムのツールチェインに由来しており、ターゲットアーキテクチャごとに異なる名前が付けられていました。

5g: ARMアーキテクチャ（32ビット）向けのGoコンパイラを指します。
6g: AMD64（x86-64）アーキテクチャ向けのGoコンパイラを指します。
8g: 386（x86-32）アーキテクチャ向けのGoコンパイラを指します。

これらのコンパイラは、Go言語のソースコードを各アーキテクチャの機械語に変換する役割を担っていました。現代のGoコンパイラは、Go言語自体で書き直され、gc（Go compiler）として統一されており、go tool compileコマンドを通じて利用されます。しかし、このコミットが作成された2012年時点では、これらの特定のコンパイラ名が使われていました。

レジスタ割り当て (Register Allocation)

レジスタ割り当ては、コンパイラの最適化フェーズにおける最も重要なタスクの一つです。CPUのレジスタは非常に高速なメモリであり、プログラムの実行速度に直接影響します。レジスタ割り当ての目的は、プログラムの変数や中間結果を、メモリではなく可能な限りCPUのレジスタに割り当てることです。

コンパイラは、プログラムの制御フローグラフやデータフロー解析に基づいて、どの変数がどの時点で「生存」しているか（つまり、将来使用される可能性があるか）を判断し、利用可能なレジスタに効率的に割り当てます。

レジスタ割り当てのバグは、以下のような問題を引き起こす可能性があります。

レジスタ不足 (Out of Registers): コンパイラが、必要な数のレジスタを割り当てられないと判断した場合に発生します。これは、利用可能なレジスタが本当に不足している場合もありますが、割り当てアルゴリズムの不備によって、実際には利用可能なレジスタがあるにもかかわらず、不足していると誤って判断される場合もあります。この場合、コンパイラは変数をメモリにスピル（退避）させる必要があり、パフォーマンスが低下します。
不正なレジスタ使用: 誤ったレジスタに値が割り当てられたり、生存期間が異なる変数が同じレジスタに割り当てられたりすると、プログラムの動作が不正になります。これは、計算結果が間違ったり、クラッシュしたりする原因となります。

非対称二項演算 (Asymmetric Binary Operations)

「非対称二項演算コンパイラ」という用語は、コンパイラ設計の分野で一般的に使われる標準的な用語ではありません。しかし、このコミットの文脈（cgen.c内のabopラベル）から推測すると、これは二項演算（例: a = b + c）において、オペランド（bとc）が非対称に扱われる状況を指していると考えられます。

具体的には、多くのCPUアーキテクチャでは、二項演算の結果が一方のオペランドのレジスタに書き込まれることがあります（例: ADD R1, R2 は R1 = R1 + R2 を意味する）。この場合、R1はソースオペランドであると同時にデスティネーションオペランドでもあり、R2は純粋なソースオペランドです。このような状況では、オペランドの役割が異なるため、レジスタ割り当ての戦略も非対称になる必要があります。

つまり、abopは、結果を格納するレジスタと、純粋なソースレジスタの扱いが異なる二項演算を処理するコードパスを示している可能性が高いです。レジスタ割り当てのバグは、このような非対称なレジスタの役割を正しく処理できない場合に発生しやすいです。

技術的詳細

このコミットは、Goコンパイラのバックエンドの一部であるsrc/cmd/5g/cgen.cファイル内のレジスタ割り当てロジックを修正しています。cgen.cは、Goの抽象構文木（AST）をターゲットアーキテクチャ（この場合はARM）の機械語に近い中間表現に変換するコード生成（Code Generation）を担当するファイルです。

問題の箇所は、abop（asymmetric binary operations）というラベルが付いたセクション内にあります。このセクションは、二項演算のコード生成、特にオペランドの扱いが非対称な場合に特化した処理を行っていると考えられます。

コンパイラがコードを生成する際、regalloc関数は、特定のノード（変数や式の結果）に対してレジスタを割り当てる役割を担います。regallocの引数は通常、以下のようになります。

regalloc(Node *n, Type *t, Node *res)

n: レジスタを割り当てる対象のノード。
t: ノードの型。
res: 結果を格納するための推奨レジスタ、または特定のレジスタを割り当てないことを示す特別な値（例: N）。

元のコードでは、非対称二項演算の処理において、オペランドnr（おそらく右オペランド）とnl（おそらく左オペランド）に対するregallocの呼び出しで、推奨レジスタの指定が誤っていました。

具体的には、元のコードではnrに対してN（特定のレジスタを割り当てない）を指定し、nlに対してres（結果レジスタ）を指定していました。しかし、非対称演算の性質上、通常は一方のオペランドが結果を保持するレジスタとして使われるため、この指定が逆になっていたことがバグの原因と考えられます。これにより、コンパイラがレジスタを効率的に割り当てられず、「レジスタ不足」の状態に陥っていたと推測されます。

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

--- a/src/cmd/5g/cgen.c
+++ b/src/cmd/5g/cgen.c
@@ -402,9 +402,9 @@ abop:	// asymmetric binary
 		regalloc(&n2, nr->type, N);
 		cgen(nr, &n2);
 	} else {
-\t\tregalloc(&n2, nr->type, N);
+\t\tregalloc(&n2, nr->type, res);
 \t\tcgen(nr, &n2);
-\t\tregalloc(&n1, nl->type, res);
+\t\tregalloc(&n1, nl->type, N);
 	}
 \tgins(a, &n2, &n1);

コアとなるコードの解説

変更はsrc/cmd/5g/cgen.cファイルのabopセクション、具体的にはelseブロック内で行われています。このelseブロックは、非対称二項演算の特定のケースを処理していると考えられます。

元のコード:

		regalloc(&n2, nr->type, N);
		cgen(nr, &n2);
	} else {
		regalloc(&n2, nr->type, N); // ここが変更前
		cgen(nr, &n2);
		regalloc(&n1, nl->type, res); // ここが変更前
	}

修正後のコード:

		regalloc(&n2, nr->type, N);
		cgen(nr, &n2);
	} else {
		regalloc(&n2, nr->type, res); // ここが変更後
		cgen(nr, &n2);
		regalloc(&n1, nl->type, N); // ここが変更後
	}

この変更は、regalloc関数の第3引数（推奨レジスタ）の指定をn1とn2の間で入れ替えています。

regalloc(&n2, nr->type, N); から regalloc(&n2, nr->type, res); へ:
- n2は、おそらく右オペランドnrに対応するノードです。
- 変更前は、nrに対して特定のレジスタの推奨がないことを示すNが渡されていました。
- 変更後は、res（結果を格納するレジスタ）が推奨レジスタとして渡されています。これは、右オペランドnrが演算結果を保持するレジスタとして使われるべきであることを示唆しています。
regalloc(&n1, nl->type, res); から regalloc(&n1, nl->type, N); へ:
- n1は、おそらく左オペランドnlに対応するノードです。
- 変更前は、nlに対してresが推奨レジスタとして渡されていました。
- 変更後は、Nが渡されています。これは、左オペランドnlに対して特定のレジスタの推奨がないことを示唆しています。

この修正により、コンパイラは非対称二項演算において、結果を格納するレジスタとソースオペランドのレジスタ割り当ての優先順位を正しく設定できるようになります。これにより、レジスタの競合が減少し、「レジスタ不足」のバグが解消されたと考えられます。

comemo