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

このコミットは、Go言語のコンパイラであるcmd/6g（amd64アーキテクチャ向け）におけるレジスタ割り当ての問題を修正するものです。具体的には、整数除算が連鎖するような式において、コンパイラがレジスタを使い果たしてしまう（"out of registers"）問題を解決します。

変更が加えられたファイルは以下の通りです。

• src/cmd/6g/cgen.c: Goコンパイラのコード生成部分を担うC言語のソースファイルです。このファイルで、整数除算のコード生成ロジックが修正されました。
• test/torture.go: Go言語のテストファイルで、コンパイラの特定のコーナーケースや最適化の挙動を検証するための「拷問テスト」が含まれています。このコミットでは、連鎖する整数除算の新しいテストケースが追加されました。

コミット

このコミットは、Goコンパイラcmd/6gにおける、整数除算の連鎖時に発生するレジスタ不足の問題を修正します。具体的には、cgen.c内のコード生成ロジックを改善し、Ullman数に基づいてオペランドの評価順序を調整することで、レジスタの効率的な利用を促進します。これにより、複雑な除算式でもコンパイラが適切にコードを生成できるようになります。また、この修正を検証するために、test/torture.goに新しいテストケースが追加されました。

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

https://github.com/golang/go/commit/46fcfdaa7dc4c35cf593df2b883db28814e641fe

元コミット内容

commit 46fcfdaa7dc4c35cf593df2b883db28814e641fe
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Sun Oct 7 00:30:29 2012 +0200

    cmd/6g: fix out of registers when chaining integer divisions.
    
    Fixes #4201.
    
    R=golang-dev, rsc
    CC=golang-dev, remy
    https://golang.org/cl/6622055

変更の背景

この変更は、Goコンパイラcmd/6gが、複数の整数除算が連鎖するような複雑な式を処理する際に、利用可能なCPUレジスタを使い果たしてしまうという問題（"out of registers"）を解決するために行われました。

コンパイラは、プログラムのソースコードを機械語に変換する際に、CPUのレジスタを効率的に割り当てる必要があります。レジスタはCPU内部の高速な記憶領域であり、計算の中間結果などを一時的に保持するために使われます。レジスタが不足すると、コンパイラは中間結果をメモリに退避させる必要があり、これはパフォーマンスの低下につながります。最悪の場合、レジスタが完全に不足すると、コンパイルエラーや不正なコード生成を引き起こす可能性があります。

特に整数除算は、多くのCPUアーキテクチャにおいて、他の算術演算（加算、減算、乗算）と比較して特殊なレジスタ（例えばx86のEAX/EDXレジスタペア）を使用したり、より多くのサイクルを必要としたりすることがあります。複数の除算が連鎖する場合、それぞれの中間結果を保持するためにレジスタが必要となり、コンパイラのレジスタ割り当て戦略が不適切だと、すぐにレジスタが枯渇してしまう可能性がありました。

この問題は、GoのIssue #4201として報告されていました。このコミットは、その問題を修正することを目的としています。

前提知識の解説

Goコンパイラ (6g)

Go言語の初期のコンパイラは、ターゲットアーキテクチャごとに異なる名前を持っていました。6gは、AMD64（x86-64）アーキテクチャ向けのGoコンパイラを指します。Goのツールチェインは、ソースコードを解析し、中間表現を生成し、最終的にターゲットアーキテクチャの機械語に変換する役割を担っています。cgen.cのようなファイルは、このコード生成フェーズの一部を担当しています。

レジスタ割り当て

レジスタ割り当ては、コンパイラ最適化の重要なフェーズの一つです。コンパイラは、プログラムの変数や中間結果を、CPUの限られた数のレジスタにどのように割り当てるかを決定します。目標は、メモリへのアクセス（レジスタよりもはるかに遅い）を最小限に抑え、プログラムの実行速度を最大化することです。

レジスタ割り当ての戦略には様々なものがありますが、一般的には、変数の「ライブ範囲」（変数が使用される期間）を分析し、競合しない変数に同じレジスタを割り当てるなどの手法が用いられます。レジスタが不足した場合、コンパイラは「スピル」（spill）と呼ばれる操作を行い、レジスタの内容をメモリに退避させます。

Ullman Number (ウルマン数)

Ullman数（またはUllmanのアルゴリズム）は、コンパイラが式を評価する際のレジスタ使用量を最小化するためのヒューリスティックです。これは、式の構文木における各ノード（演算子やオペランド）に対して、そのサブツリーを評価するために必要な最小レジスタ数を割り当てるものです。

基本的な考え方は以下の通りです：

1. 葉ノード（定数や変数）には1を割り当てる（レジスタ1つで値を保持できるため）。
2. 内部ノード（演算子）の場合、その子ノードのUllman数を比較し、大きい方に1を加える。これは、大きい方のサブツリーを評価する際に、もう一方のサブツリーの結果を保持するために追加のレジスタが必要になる可能性があるためです。

Ullman数を用いることで、コンパイラはレジスタ使用量が少ない方のサブツリーを先に評価し、その結果をレジスタに保持したまま、レジスタ使用量が多い方のサブツリーを評価するという戦略を取ることができます。これにより、レジスタのスピルを減らし、コードの効率を向上させることができます。

整数除算の特性

多くのCPUアーキテクチャでは、整数除算は特殊な命令とレジスタの制約を持ちます。例えば、x86アーキテクチャでは、DIV命令は被除数をEAX（またはAX/DX:AX）レジスタに、除数をオペランドに取ります。結果として商はEAXに、剰余はEDXに格納されます。このため、除算を行う際には、これらの特定のレジスタが一時的に占有されることになります。連鎖する除算では、これらのレジスタの競合が頻繁に発生し、レジスタ割り当てを複雑にします。

技術的詳細

このコミットの技術的詳細は、src/cmd/6g/cgen.c内のcgen関数における整数除算（ODIV、OMODなど）の処理ロジックの変更にあります。以前のコードでは、除算のオペランド（左辺nlと右辺nr）を評価する際に、レジスタ割り当ての順序を十分に考慮していませんでした。これが、連鎖する除算でレジスタ不足を引き起こす原因となっていました。

修正後のコードでは、Ullman数（ullmanフィールド）を利用して、左辺と右辺のサブツリーを評価するのに必要なレジスタ数を比較します。

• if(nl->ullman >= nr->ullman): もし左辺のサブツリーを評価するのに必要なレジスタ数が右辺以上である場合、まず左辺を評価します。

  • regalloc(&n1, nl->type, res);: 左辺の結果を保持するための一時レジスタn1を割り当てます。
  • cgen(nl, &n1);: 左辺の式を評価し、結果をn1に格納します。
  • cgen_div(n->op, &n1, nr, res);: n1と右辺nrを使って除算を実行します。
  • regfree(&n1);: n1を解放します。 この順序は、左辺の評価がより多くのレジスタを必要とする場合に、そのレジスタを先に解放し、右辺の評価や最終的な除算のために利用できるようにするためです。

• else: もし右辺のサブツリーを評価するのに必要なレジスタ数が左辺より大きい場合、まず右辺を評価します。

  • if(!smallintconst(nr)): 右辺が小さな整数定数でない場合（つまり、レジスタを必要とする複雑な式の場合）。
    • regalloc(&n2, nr->type, res);: 右辺の結果を保持するための一時レジスタn2を割り当てます。
    • cgen(nr, &n2);: 右辺の式を評価し、結果をn2に格納します。
  • else: 右辺が小さな整数定数の場合、レジスタ割り当ては不要です。
    • n2 = *nr;: 右辺のノードを直接使用します。
  • cgen_div(n->op, nl, &n2, res);: 左辺nlとn2を使って除算を実行します。
  • if(n2.op != OLITERAL) regfree(&n2);: n2がリテラルでない場合（つまり、一時レジスタが割り当てられた場合）にn2を解放します。 この順序は、右辺の評価がより多くのレジスタを必要とする場合に、そのレジスタを先に解放し、左辺の評価や最終的な除算のために利用できるようにするためです。

このUllman数に基づいた評価順序の変更により、コンパイラはレジスタをより効率的に利用できるようになり、連鎖する整数除算においてもレジスタ不足に陥ることを防ぎます。

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

src/cmd/6g/cgen.cのcgen関数内のcase ODIV:（およびOMODなど、除算関連の演算子）ブロックが変更されました。

--- a/src/cmd/6g/cgen.c
+++ b/src/cmd/6g/cgen.c
@@ -402,7 +402,23 @@ cgen(Node *n, Node *res)
 		t = optoas(n->op, nl->type);
 		goto abop;
 	}
-	cgen_div(n->op, nl, nr, res);
+
+	if(nl->ullman >= nr->ullman) {
+		regalloc(&n1, nl->type, res);
+		cgen(nl, &n1);
+		cgen_div(n->op, &n1, nr, res);
+		regfree(&n1);
+	} else {
+		if(!smallintconst(nr)) {
+			regalloc(&n2, nr->type, res);
+			cgen(nr, &n2);
+		} else {
+			n2 = *nr;
+		}
+		cgen_div(n->op, nl, &n2, res);
+		if(n2.op != OLITERAL)
+			regfree(&n2);
+	}
 	break;
 
 	case OLSH:

また、この修正を検証するために、test/torture.goに以下のテストケースが追加されました。

--- a/test/torture.go
+++ b/test/torture.go
@@ -169,3 +169,25 @@ func ChainUNoAssert(u *U) *U {
 		Child(0).\
 		Child(0).(*U)
 }
+
+// Chains of divisions. See issue 4201.
+
+func ChainDiv(a, b int) int {
+	return a / b / a / b / a / b / a / b /\
+		a / b / a / b / a / b / a / b /\
+		a / b / a / b / a / b / a / b
+}
+
+func ChainDivRight(a, b int) int {
+	return a / (b / (a / (b /\
+            (a / (b / (a / (b /\
+            (a / (b / (a / (b /\
+            (a / (b / (a / (b /\
+            (a / (b / (a / b))))))))))))))))))\
+}
+
+func ChainDivConst(a int) int {
+	return a / 17 / 17 / 17 /\
+		17 / 17 / 17 / 17 /\
+		17 / 17 / 17 / 17
+}

コアとなるコードの解説

変更されたsrc/cmd/6g/cgen.cのコードブロックを詳細に解説します。このブロックは、抽象構文木（AST）のノードnが除算演算子（ODIVなど）である場合に実行されます。

	if(nl->ullman >= nr->ullman) {
		// 左オペランドのUllman数が右オペランド以上の場合
		// これは、左オペランドの評価がより多くのレジスタを必要とするか、
		// 同程度のレジスタを必要とするが、先に評価することでレジスタを早く解放できる場合に選択されるパスです。
		regalloc(&n1, nl->type, res);
		// nl (左オペランド) の結果を格納するための一時的なレジスタノード n1 を割り当てます。
		// nl->type は nl の型、res は最終的な結果が格納される場所を示唆します。
		cgen(nl, &n1);
		// 左オペランド nl のコードを生成し、その結果を n1 に格納します。
		// cgen は再帰的に呼び出され、nl のサブツリーを評価します。
		cgen_div(n->op, &n1, nr, res);
		// n->op (除算の種類), n1 (左オペランドの結果), nr (右オペランド), res (最終結果) を使って
		// 実際の除算命令のコードを生成します。
		regfree(&n1);
		// n1 に割り当てられたレジスタを解放します。これにより、他の計算でこのレジスタを再利用できるようになります。
	} else {
		// 右オペランドのUllman数が左オペランドより大きい場合
		// これは、右オペランドの評価がより多くのレジスタを必要とする場合に選択されるパスです。
		// より複雑なサブツリーを先に評価し、そのレジスタを早く解放することで、
		// 全体的なレジスタ使用量を最適化します。
		if(!smallintconst(nr)) {
			// nr (右オペランド) が小さな整数定数でない場合。
			// つまり、nr が複雑な式であり、レジスタを必要とする可能性がある場合です。
			regalloc(&n2, nr->type, res);
			// nr の結果を格納するための一時的なレジスタノード n2 を割り当てます。
			cgen(nr, &n2);
			// 右オペランド nr のコードを生成し、その結果を n2 に格納します。
		} else {
			// nr が小さな整数定数である場合。
			// この場合、レジスタを割り当てる必要はなく、直接値を使用できます。
			n2 = *nr;
			// nr のノード自体を n2 として使用します。
		}
		cgen_div(n->op, nl, &n2, res);
		// n->op (除算の種類), nl (左オペランド), n2 (右オペランドの結果), res (最終結果) を使って
		// 実際の除算命令のコードを生成します。
		if(n2.op != OLITERAL)
			// n2 がリテラル（定数）でない場合、つまり regalloc でレジスタが割り当てられた場合のみ、
			// そのレジスタを解放します。
			regfree(&n2);
	}

この変更のポイントは、Ullman数に基づいてオペランドの評価順序を動的に決定している点です。これにより、レジスタをより効率的に使用し、特に連鎖する除算のようなレジスタを多く消費する可能性のある操作において、レジスタ不足を回避できるようになります。

test/torture.goに追加されたテストケースは、この修正が正しく機能することを確認するためのものです。

• ChainDiv: 複数の除算が左結合で連鎖するケース。
• ChainDivRight: 複数の除算が右結合（括弧で明示的にネスト）で連鎖するケース。
• ChainDivConst: 定数による除算が連鎖するケース。

これらのテストは、コンパイラがこれらの複雑な除算式を正しくコンパイルし、期待通りの結果を生成できることを保証します。

関連リンク

• Go言語の変更リスト (CL): https://golang.org/cl/6622055
• GitHubコミットページ: https://github.com/golang/go/commit/46fcfdaa7dc4c35cf593df2b883db28814e641fe

参考にした情報源リンク

• コンパイラの最適化に関する一般的な情報（レジスタ割り当て、Ullman数など）
  • https://en.wikipedia.org/wiki/Register_allocation
  • https://en.wikipedia.org/wiki/Ullman%27s_algorithm
• Goコンパイラの内部構造に関する情報（当時のGoコンパイラの設計思想やコードベースについて）
  • Goの公式ドキュメントやブログ記事、またはGoのソースコード自体が最も信頼できる情報源となります。