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

このコミットは、Goコンパイラ（cmd/6g および cmd/8g）における2つの特定のケースで発生していた「固定レジスタの枯渇 (out of fixed registers)」バグを修正するものです。これらのバグは、レジスタが早すぎる段階で割り当てられることによって、特にネストされた操作中に利用可能なレジスタが枯渇してしまうことが原因でした。具体的には、メソッド呼び出しと8ビット乗算の処理におけるレジスタ割り当てのロジックが改善されています。

コミット

commit 6feb61325a501b3e122c081624c837eeae5bd0a9
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Wed Sep 26 21:17:11 2012 +0200

    cmd/6g, cmd/8g: fix two "out of fixed registers" cases.
    
    In two cases, registers were allocated too early resulting
    in exhausting of available registers when nesting these
    operations.
    
    The case of method calls was due to missing cases in igen,
    which only makes calls but doesn't allocate a register for
    the result.
    
    The case of 8-bit multiplication was due to a wrong order
    in register allocation when Ullman numbers were bigger on the
    RHS.
    
    Fixes #3907.
    Fixes #4156.
    
    R=rsc
    CC=golang-dev, remy
    https://golang.org/cl/6560054

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

https://github.com/golang/go/commit/6feb61325a501b3e122c081624c837eeae5bd0a9

元コミット内容

cmd/6g, cmd/8g: fix two "out of fixed registers" cases.

In two cases, registers were allocated too early resulting
in exhausting of available registers when nesting these
operations.

The case of method calls was due to missing cases in igen,
which only makes calls but doesn't allocate a register for
the result.

The case of 8-bit multiplication was due to a wrong order
in register allocation when Ullman numbers were bigger on the
RHS.

Fixes #3907.
Fixes #4156.

R=rsc
CC=golang-dev, remy
https://golang.org/cl/6560054

変更の背景

このコミットは、Goコンパイラ（6gはAMD64アーキテクチャ用、8gは386/ARMアーキテクチャ用）が特定のコードパターンをコンパイルする際に発生していた「固定レジスタの枯渇」というバグを解決するために導入されました。この問題は、コンパイラがレジスタを必要以上に早く割り当ててしまうことで、後続の処理で利用可能なレジスタが不足し、結果としてコンパイルエラーや非効率なコード生成を引き起こす可能性がありました。

具体的には、以下の2つのシナリオで問題が顕在化していました。

1. メソッド呼び出し: コンパイラの命令生成部分（igen関数）が、通常の関数呼び出しは処理するものの、メソッド呼び出しやインターフェース呼び出しの戻り値を格納するためのレジスタを適切に割り当てていなかったため、これらの呼び出しがネストされるとレジスタが枯渇していました。
2. 8ビット乗算: 8ビットの乗算処理において、レジスタ割り当ての順序が不適切でした。特に、右辺（RHS）のオペランドのUllman数が大きい場合に、レジスタの割り当て順序が最適でなかったため、レジスタの枯渇が発生していました。

これらの問題は、コンパイラの安定性と生成されるコードの効率性に直接影響するため、修正が急務でした。

前提知識の解説

コンパイラのレジスタ割り当て

コンパイラは、プログラムの実行速度を最大化するために、CPUのレジスタを効率的に使用しようとします。レジスタ割り当てとは、プログラムの変数や中間結果を、メモリではなく高速なCPUレジスタにどのようにマッピングするかを決定するプロセスです。レジスタの数は限られているため、どの値をいつレジスタにロードし、いつメモリに退避させるか（スピルアウト）は、コンパイラの重要な最適化課題です。

「固定レジスタの枯渇 (out of fixed registers)」とは、コンパイラが特定の操作のために予約されたレジスタ（固定レジスタ）を使い果たしてしまい、それ以上レジスタを割り当てられなくなる状態を指します。これは通常、コンパイラのレジスタ割り当てアルゴリズムに問題がある場合に発生します。

Ullman数 (Ullman Number)

Ullman数（またはUllmanのアルゴリズム）は、コンパイラのコード生成において、式の評価順序を決定し、必要なレジスタの数を最小化するための概念です。これは、式をツリー構造で表現した際に、各ノード（演算子やオペランド）に割り当てられる数値で、そのサブツリーを評価するために必要なレジスタの最小数を示します。

• 葉ノード（オペランド）: Ullman数は1です（その値を保持するために1つのレジスタが必要）。
• 内部ノード（演算子）: 左右の子ノードのUllman数を比較し、大きい方に1を加えるか、両方が同じ場合は1を加える、といったルールで計算されます。

Ullman数に基づいて式の評価順序を決定することで、コンパイラはレジスタの使用を最適化し、レジスタスピル（レジスタの内容をメモリに退避させること）を減らすことができます。このコミットでは、「右辺のUllman数が大きい場合のレジスタ割り当て順序の誤り」が問題とされており、これはUllman数に基づく最適化が正しく機能していなかったことを示唆しています。

Goコンパイラの構造 (cmd/6g, cmd/8g)

Go言語のコンパイラは、ターゲットアーキテクチャごとに異なるバックエンドを持っています。

• cmd/6g: AMD64 (x86-64) アーキテクチャ用のコンパイラ。
• cmd/8g: 386 (x86) および ARM アーキテクチャ用のコンパイラ。

これらのコンパイラは、フロントエンドでGoのソースコードを中間表現に変換し、バックエンドでその中間表現をターゲットアーキテクチャの機械語に変換します。cgen.cやggen.cのようなファイルは、このバックエンドのコード生成フェーズに関連しています。

• cgen.c: C言語のコード生成に似た、一般的なコード生成ロジックを扱うファイル。式の評価やステートメントの変換などを行います。
• ggen.c: Go言語特有のコード生成、特にレジスタ割り当てや特定の命令の生成など、より低レベルな最適化やアセンブリコード生成に近い部分を扱うファイル。

技術的詳細

このコミットは、src/cmd/6g/cgen.c, src/cmd/6g/ggen.c, src/cmd/8g/cgen.c, src/cmd/8g/ggen.c の4つのファイルにわたる変更を含んでいます。主な修正点は以下の2つです。

1. igen関数におけるメソッド/インターフェース呼び出しのレジスタ割り当て修正:

   • 以前のigen関数は、OCALLFUNC（通常の関数呼び出し）のみを明示的に処理し、cgen_callを呼び出していました。しかし、OCALLMETH（メソッド呼び出し）やOCALLINTER（インターフェース呼び出し）の場合、適切なレジスタ割り当てが行われていませんでした。
   • 修正後、igen関数はOCALLFUNC、OCALLMETH、OCALLINTERの3つのケースをswitch文で明示的に区別し、それぞれに対応するcgen_call、cgen_callmeth、cgen_callinterを呼び出すようになりました。これにより、メソッドやインターフェース呼び出しの戻り値が正しくレジスタに割り当てられるようになり、レジスタ枯渇の問題が解消されました。

2. cgen_bmul関数における8ビット乗算のレジスタ割り当て順序修正:

   • cgen_bmul関数は、8ビットの乗算を処理します。CPUには直接8ビット乗算命令がないため、通常はより大きな幅（例: 16ビット、32ビット、64ビット）に拡張して乗算を行い、結果を切り詰めます。
   • 以前の実装では、nl->ullman >= nr->ullmanという条件でオペランドのUllman数を比較し、レジスタ割り当ての順序を決定していました。しかし、この順序が「右辺のUllman数が大きい場合」に不適切であり、レジスタの早期枯渇を引き起こしていました。
   • 修正後、cgen_bmul関数は、まずnl->ullman < nr->ullmanの場合にnlとnrをスワップし、常にUllman数が大きいオペランドがnlになるようにします。
   • 次に、nl（Ullman数が大きい方）のレジスタをres（結果を格納するレジスタ）をヒントとして先に割り当て（regalloc(&n1, t, res); cgen(nl, &n1);）、その後でnrのレジスタを割り当てます（regalloc(&n2, t, N); cgen(nr, &n2);）。
   • また、乗算の型を6gではTUINT64/TINT64（64ビット）、8gではTUINT32/TINT32（32ビット）に拡張して処理するように変更されました。これにより、中間レジスタの管理が簡素化され、より堅牢なレジスタ割り当てが可能になりました。
   • 不要な中間レジスタ（n1b, n2b, n1w, n2w）が削除され、直接フル幅のレジスタ（n1, n2）を使用するようになり、コードが簡潔になりました。

これらの変更により、コンパイラはより正確かつ効率的にレジスタを管理できるようになり、特定のネストされた操作や8ビット乗算におけるレジスタ枯渇の問題が解決されました。

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

src/cmd/6g/cgen.c および src/cmd/8g/cgen.c の igen 関数

--- a/src/cmd/6g/cgen.c
+++ b/src/cmd/6g/cgen.c
@@ -840,8 +841,20 @@ igen(Node *n, Node *a, Node *res)
 		return;
 
 	case OCALLFUNC:
+	case OCALLMETH:
+	case OCALLINTER:
+		switch(n->op) {
+		case OCALLFUNC:
+			cgen_call(n, 0);
+			break;
+		case OCALLMETH:
+			cgen_callmeth(n, 0);
+			break;
+		case OCALLINTER:
+			cgen_callinter(n, N, 0);
+			break;
+		}
 		fp = structfirst(&flist, getoutarg(n->left->type));
-		cgen_call(n, 0);
 		memset(a, 0, sizeof *a);
 		a->op = OINDREG;
 		a->val.u.reg = D_SP;

（src/cmd/8g/cgen.cも同様の変更）

src/cmd/6g/ggen.c および src/cmd/8g/ggen.c の cgen_bmul 関数

--- a/src/cmd/6g/ggen.c
+++ b/src/cmd/6g/ggen.c
@@ -978,48 +978,37 @@ ret:
 /*
  * generate byte multiply:
  *	res = nl * nr
- * no 2-operand byte multiply instruction so have to do
- * 16-bit multiply and take bottom half.
+ * there is no 2-operand byte multiply instruction so
+ * we do a full-width multiplication and truncate afterwards.
  */
 void
 cgen_bmul(int op, Node *nl, Node *nr, Node *res)
 {
-	Node n1b, n2b, n1w, n2w;
+	Node n1, n2, *tmp;
 	Type *t;
 	int a;
 
-	if(nl->ullman >= nr->ullman) {
-		regalloc(&n1b, nl->type, res);
-		cgen(nl, &n1b);
-		regalloc(&n2b, nr->type, N);
-		cgen(nr, &n2b);
-	} else {
-		regalloc(&n2b, nr->type, N);
-		cgen(nr, &n2b);
-		regalloc(&n1b, nl->type, res);
-		cgen(nl, &n1b);
-	}
-
-	// copy from byte to short registers
-	t = types[TUINT16];
+	// copy from byte to full registers
+	t = types[TUINT64]; // For 6g (AMD64)
 	if(issigned[nl->type->etype])
-		t = types[TINT16];
-
-	regalloc(&n2w, t, &n2b);
-	cgen(&n2b, &n2w);
-
-	regalloc(&n1w, t, &n1b);
-	cgen(&n1b, &n1w);
+		t = types[TINT64]; // For 6g (AMD64)
 
+	// largest ullman on left.
+	if(nl->ullman < nr->ullman) {
+		tmp = nl;
+		nl = nr;
+		nr = tmp;
+	}
+
+	regalloc(&n1, t, res);
+	cgen(nl, &n1);
+	regalloc(&n2, t, N);
+	cgen(nr, &n2);
 	a = optoas(op, t);
-	gins(a, &n2w, &n1w);
-	cgen(&n1w, &n1b);
-	cgen(&n1b, res);
-
-	regfree(&n1w);
-	regfree(&n2w);
-	regfree(&n1b);
-	regfree(&n2b);
+	gins(a, &n2, &n1);
+	regfree(&n2);
+	gmove(&n1, res);
+	regfree(&n1);
 }

（src/cmd/8g/ggen.cも同様の変更だが、tの型がTUINT32/TINT32となる）

コアとなるコードの解説

igen関数の変更

igen関数は、Goの抽象構文木（AST）ノードを、ターゲットアーキテクチャの命令に変換する役割を担っています。以前は、OCALLFUNC（通常の関数呼び出し）のみが明示的に処理され、cgen_callが呼び出されていました。しかし、Goにはメソッド呼び出し（OCALLMETH）やインターフェース呼び出し（OCALLINTER）といった、通常の関数呼び出しとは異なる呼び出しメカニズムが存在します。これらの呼び出しも結果を返す可能性があり、その結果を格納するためのレジスタが適切に割り当てられる必要がありました。

変更後、igen関数はOCALLFUNC、OCALLMETH、OCALLINTERの3つのケースをswitch文で分岐させ、それぞれに対応する専用のコード生成関数（cgen_call、cgen_callmeth、cgen_callinter）を呼び出すようになりました。これにより、各呼び出しタイプに応じた正確なレジスタ割り当てとコード生成が行われるようになり、特にネストされたメソッド呼び出しなどで発生していたレジスタ枯渇の問題が解消されました。

cgen_bmul関数の変更

cgen_bmul関数は、8ビット整数同士の乗算を処理します。多くのCPUアーキテクチャには直接8ビット乗算を行う命令がないため、コンパイラは通常、オペランドをより大きな整数型（例: 16ビット、32ビット、64ビット）に拡張してから乗算を行い、結果を8ビットに切り詰める必要があります。

この関数の変更は、主にレジスタ割り当ての順序と中間レジスタの管理を改善しています。

1. Ullman数に基づくオペランド順序の最適化:

   • 以前はnl->ullman >= nr->ullmanという条件でレジスタ割り当ての順序を決定していましたが、これが「右辺のUllman数が大きい場合」に問題を引き起こしていました。
   • 新しいコードでは、if(nl->ullman < nr->ullman)という条件でnlとnrをスワップし、常にUllman数が大きいオペランドがnlになるようにしています。これにより、Ullman数に基づくレジスタ割り当てのヒューリスティックが正しく機能し、レジスタの早期枯渇を防ぎます。Ullman数が大きいオペランドを先に処理することで、その評価に必要なレジスタを確保し、その後の処理でレジスタを再利用しやすくします。

2. フル幅乗算への変更と中間レジスタの削減:

   • 以前は8ビット値を16ビットに拡張して乗算を行っていましたが、新しいコードでは6g（AMD64）では64ビット、8g（386/ARM）では32ビットといった、よりアーキテクチャのネイティブなワードサイズに拡張して乗算を行うように変更されました。これにより、中間レジスタ（n1b, n2b, n1w, n2w）が不要になり、コードが簡潔になりました。
   • regalloc(&n1, t, res); cgen(nl, &n1); のように、結果を格納するレジスタresをヒントとしてn1を割り当てることで、レジスタの再利用を促進し、レジスタ圧力を軽減しています。
   • 乗算後、不要になったn2レジスタをすぐに解放し（regfree(&n2)）、結果をresに移動してからn1レジスタを解放しています。これにより、レジスタのライフタイムが適切に管理され、レジスタの枯渇が回避されます。

これらの変更により、8ビット乗算のコード生成がより効率的かつ堅牢になり、レジスタ割り当てのバグが修正されました。

関連リンク

• Go Issue #3907: https://github.com/golang/go/issues/3907
• Go Issue #4156: https://github.com/golang/go/issues/4156
• Gerrit Change-ID: https://golang.org/cl/6560054

参考にした情報源リンク

• Go言語のソースコード (特に src/cmd/6g/, src/cmd/8g/ ディレクトリ)
• コンパイラ最適化に関する一般的な資料 (レジスタ割り当て、Ullman数など)
• Go言語のIssue Tracker (上記Fixesで参照されているIssue)
• Go言語のGerrit Code Review (上記golang.org/clで参照されている変更セット)
• Ullman's algorithm - Wikipedia (Ullman数に関する一般的な情報)
• Register allocation - Wikipedia (レジスタ割り当てに関する一般的な情報)