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

このコミットは、Goコンパイラ（特に5gと6g、それぞれARMとx86-64アーキテクチャ向けのコンパイラ）における、多重配列インデックスアクセス時のレジスタ枯渇問題を修正するものです。具体的には、s[s[s[...s[i]...]]]のような深くネストされた配列インデックス式をコンパイルする際に、コンパイラが利用可能なレジスタを使い果たしてしまう問題に対処しています。

コミット

commit 0b2353edcb7fc6ff100f42b1d9cc5613a6c57da1
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Fri Nov 2 07:50:59 2012 +0100

    cmd/5g, cmd/6g: fix out of registers with array indexing.
    
    Compiling expressions like:
        s[s[s[s[s[s[s[s[s[s[s[s[i]]]]]]]]]]]]
    make 5g and 6g run out of registers. Such expressions can arise
    if a slice is used to represent a permutation and the user wants
    to iterate it.
    
    This is due to the usual problem of allocating registers before
    going down the expression tree, instead of allocating them in a
    postfix way.
    
    The functions cgenr and agenr (that generate a value to a newly
    allocated register instead of an existing location), are either
    introduced or modified when they already existed to allocate
    the new register as late as possible, and sudoaddable is disabled
    for OINDEX nodes so that igen/agenr is used instead.
    
    Update #4207.
    
    R=dave, daniel.morsing, rsc
    CC=golang-dev
    https://golang.org/cl/6733055

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

https://github.com/golang/go/commit/0b2353edcb7fc6ff100f42b1d9cc5613a6c57da1

元コミット内容

cmd/5g, cmd/6g: fix out of registers with array indexing.

深くネストされた配列インデックス式、例えば s[s[s[s[s[s[s[s[s[s[s[s[i]]]]]]]]]]]] のようなものをコンパイルすると、5g および 6g コンパイラがレジスタを使い果たしてしまう問題が修正されました。このような式は、スライスが順列を表すために使用され、ユーザーがそれを反復処理したい場合に発生する可能性があります。

これは、式ツリーを下降する前にレジスタを割り当てるという一般的な問題に起因しており、ポストフィックス（後置）方式で割り当てるべきでした。

cgenr および agenr 関数（既存の場所ではなく新しく割り当てられたレジスタに値を生成する関数）は、新しいレジスタを可能な限り遅く割り当てるように導入または修正されました。また、OINDEX ノードに対して sudoaddable が無効にされ、代わりに igen/agenr が使用されるようになりました。

Issue #4207 を更新します。

変更の背景

Goコンパイラは、ソースコードを機械語に変換する際に、中間表現（IR）を生成し、そのIRを最適化し、最終的にターゲットアーキテクチャのレジスタに値を割り当てます。このレジスタ割り当てのプロセスは、コンパイラの性能と生成されるコードの効率に大きく影響します。

このコミットが修正しようとしている問題は、深くネストされた配列インデックス式、例えば arr[arr[arr[...]]] のような構造が、コンパイラのレジスタ割り当て戦略と衝突することでした。当時のGoコンパイラ（特に5gと6g）は、式ツリーを処理する際に、子ノードの評価に必要なレジスタを事前に確保しようとする傾向がありました。しかし、深くネストされた式では、各インデックス操作が一時的な値を生成し、それが次のインデックス操作の基底アドレスまたはインデックスとして使用されます。この連鎖的な依存関係により、コンパイラは多数の一時的なレジスタを同時に保持しようとし、結果として利用可能な物理レジスタを使い果たし、「out of registers」エラーを引き起こしていました。

この問題は、特にスライスが順列（permutation）を表すために使用され、その順列を反復処理するようなアルゴリズムで顕在化しました。このようなコードは、Goの言語仕様上は合法であり、コンパイラが正しく処理できるべきです。

前提知識の解説

このコミットを理解するためには、以下のコンパイラの概念とGoコンパイラの内部構造に関する知識が必要です。

1. コンパイラのレジスタ割り当て (Register Allocation):

   • コンパイラの重要なフェーズの一つで、プログラムの変数や中間計算結果をCPUの高速なレジスタに割り当てるプロセスです。レジスタは数が限られているため、効率的な割り当て戦略が求められます。
   • レジスタ枯渇 (Register Exhaustion): 利用可能なレジスタが不足し、一時的な値をメモリにスピル（退避）せざるを得なくなる状況。スピルは性能低下を招きます。最悪の場合、コンパイルエラーとなることもあります。
   • グラフ彩色 (Graph Coloring): レジスタ割り当ての一般的なアルゴリズムの一つで、変数の生存期間をグラフで表現し、レジスタを色として割り当てることで、競合する変数に異なるレジスタを割り当てます。
   • 事前割り当て vs. 遅延割り当て:
     • 事前割り当て (Eager Allocation): 式ツリーを下降する前に、必要なレジスタを先に確保しようとする戦略。単純な式には有効ですが、複雑な式や深いネストではレジスタの無駄遣いや枯渇を招きやすいです。
     • 遅延割り当て (Lazy/Postfix Allocation): 値が必要になる直前、または式ツリーの評価が完了した後にレジスタを割り当てる戦略。レジスタの生存期間を短く保ち、より効率的な利用が可能です。このコミットが目指す方向性です。

2. Goコンパイラのバックエンド (5g, 6g, gc):

   • Goコンパイラは、歴史的に複数のアーキテクチャ固有のバックエンドを持っていました。5gはARMアーキテクチャ向け、6gはx86-64アーキテクチャ向けのコンパイラです。gcは共通のフロントエンド部分を指します。
   • これらのコンパイラは、C言語で書かれており、独自のAST（抽象構文木）と中間表現を使用しています。

3. Goコンパイラのコード生成関数:

   • Goコンパイラのバックエンドには、ASTノードを機械語命令に変換するための様々な関数が存在します。
   • agen(Node *n, Node *res): ノード n のアドレスを計算し、その結果を res に格納します。res は通常、レジスタまたはメモリ位置を表します。
   • cgen(Node *n, Node *res): ノード n の値を計算し、その結果を res に格納します。
   • igen(Node *n, Node *a, Node *res): ノード n の間接参照（ポインタのデリファレンス）を行い、その結果を a に格納します。a は通常、レジスタまたはメモリ位置を表します。
   • agenr(Node *n, Node *a, Node *res): agen と似ていますが、結果を新しく割り当てられたレジスタ a に格納します。r は "register" を意味します。
   • cgenr(Node *n, Node *a, Node *res): cgen と似ていますが、結果を新しく割り当てられたレジスタ a に格納します。
   • Node 構造体: コンパイラ内部でASTノードや中間表現の要素を表す構造体。op フィールドはノードの種類（演算子など）を示します。
   • OINDEX: 配列インデックス操作を表すASTノードのオペレーションコード。
   • addable: Node 構造体のフラグで、そのノードが直接アドレス指定可能（メモリ上の固定位置にあるなど）であるかを示します。addable なノードは、レジスタにロードせずに直接アクセスできるため、コード生成が単純化されます。
   • sudoaddable: gsubr.c にある関数で、あるノードが「擬似的にアドレス指定可能」であるかどうかを判断します。これは、コンパイラが特定の最適化を行うために、一時的にノードをアドレス指定可能として扱うことができるかどうかを決定します。

技術的詳細

このコミットの核心は、Goコンパイラのレジスタ割り当て戦略を、深くネストされた配列インデックス式に対してより効率的にすることです。具体的には、以下の2つの主要な変更が行われました。

1. cgenr および agenr 関数の導入/修正と遅延レジスタ割り当て:

   • 従来の agen や cgen 関数は、結果を格納するレジスタを比較的早期に割り当てていました。これが、深い式ツリーでレジスタ枯渇を引き起こす原因でした。
   • cgenr と agenr は、"generate a value to a newly allocated register" (新しく割り当てられたレジスタに値を生成する) という目的を持っています。このコミットでは、これらの関数が、新しいレジスタを可能な限り遅く割り当てるように修正または導入されました。
   • これにより、一時的な値がレジスタに保持される期間が短縮され、レジスタの再利用が促進されます。特に、ネストされたインデックス式では、内側のインデックスの結果がすぐに外側のインデックスの計算に使用されるため、その結果を保持するレジスタはすぐに解放されるべきです。

2. OINDEX ノードに対する sudoaddable の無効化:

   • sudoaddable 関数は、特定のノードが「擬似的にアドレス指定可能」であると判断し、コンパイラがより直接的なコード生成パスを選択できるようにします。
   • しかし、OINDEX ノード（配列インデックス操作）の場合、sudoaddable が有効になっていると、コンパイラはインデックス操作の結果を直接アドレス指定可能なものとして扱い、agen のような関数を呼び出す傾向がありました。この agen の内部で、レジスタが早期に割り当てられてしまう問題がありました。
   • このコミットでは、src/cmd/5g/gsubr.c と src/cmd/6g/gsubr.c の sudoaddable 関数内で、OINDEX ノードに対して return 0; を追加し、sudoaddable を明示的に無効にしました。
   • これにより、OINDEX ノードは sudoaddable ではないと判断され、コンパイラは代わりに igen や agenr のような関数を使用するようになります。これらの関数は、レジスタをより遅延して割り当てる戦略を採用しているため、レジスタ枯渇問題が緩和されます。

これらの変更により、コンパイラは深くネストされた配列インデックス式を処理する際に、レジスタをより賢く、必要な時にだけ割り当てるようになり、レジスタ枯渇エラーを回避できるようになりました。

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

このコミットで変更された主要なファイルと関数は以下の通りです。

• src/cmd/5g/cgen.c:
  • agen 関数: OINDEX ケースのコードが大幅に簡素化され、agenr を呼び出すように変更されました。
  • cgenr 関数: 新しく導入されました。ノードの値を新しく割り当てられたレジスタに生成します。
  • agenr 関数: 新しく導入されました。ノードのアドレスを新しく割り当てられたレジスタに生成します。OINDEX の複雑なロジックがここに移動しました。
  • sgen 関数: agen の代わりに agenr を使用するように変更されました。
• src/cmd/5g/gsubr.c:
  • sudoaddable 関数: OINDEX ケースで return 0; が追加され、OINDEX ノードが sudoaddable ではないとマークされるようになりました。
• src/cmd/6g/cgen.c:
  • agen 関数: OINDEX ケースのコードが大幅に簡素化され、agenr を呼び出すように変更されました。また、agen 自体も agenr を呼び出すように変更されました。
  • cgenr 関数: 新しく導入されました。
  • agenr 関数: 新しく導入されました。OINDEX の複雑なロジックがここに移動しました。
• src/cmd/6g/gg.h:
  • agenr 関数のプロトタイプが追加されました。
• src/cmd/6g/gsubr.c:
  • sudoaddable 関数: OINDEX ケースで return 0; が追加され、OINDEX ノードが sudoaddable ではないとマークされるようになりました。
• src/cmd/gc/fmt.c:
  • nodedump 関数: OINDREG が OREGISTER と同じようにダンプされるように修正されました。これはデバッグ出力の改善です。
• test/torture.go:
  • 新しいテストケース IndexChain1, IndexChain2, IndexChain3 が追加されました。これらは深くネストされた配列インデックスアクセスをテストするためのものです。

コアとなるコードの解説

src/cmd/5g/cgen.c および src/cmd/6g/cgen.c の変更

最も重要な変更は、agen 関数から OINDEX の処理ロジックが削除され、新しく導入された agenr 関数に移動したことです。

変更前 (agen の OINDEX ケースの抜粋):

	case OINDEX:
		p2 = nil;  // to be patched to panicindex.
		w = n->type->width;
		if(nr->addable) {
			// ... 複雑なレジスタ割り当てとコード生成ロジック ...
		} else
		if(nl->addable) {
			// ... 複雑なレジスタ割り当てとコード生成ロジック ...
		} else {
			// ... 複雑なレジスタ割り当てとコード生成ロジック ...
		}
		// ... 境界チェックとアドレス計算 ...
		gmove(&n3, res); // 結果をresに移動
		regfree(&n2);
		regfree(&n3);
		break;

このコードでは、agen 関数内で OINDEX ノードの処理中に多くの regalloc (レジスタ割り当て) が行われていました。これがレジスタ枯渇の原因でした。

変更後 (agen の OINDEX ケースの抜粋):

	case OINDEX:
		agenr(n, &n1, res); // agenrを呼び出し、結果をn1に格納
		gmove(&n1, res);    // n1からresに移動
		regfree(&n1);
		break;

agen は非常にシンプルになり、OINDEX の実際の処理は agenr に委譲されています。これにより、agen はレジスタ割り当てのタイミングを直接制御せず、agenr がより遅延した割り当てを行うようになります。

新しく導入された cgenr 関数 (例: src/cmd/5g/cgen.c):

void
cgenr(Node *n, Node *a, Node *res)
{
	Node n1;

	if(debug['g'])
		dump("cgenr-n", n);

	if(isfat(n->type))
		fatal("cgenr on fat node");

	if(n->addable) {
		regalloc(a, types[tptr], res);
		gmove(n, a);
		return;
	}

	switch(n->op) {
	case ONAME:
	case ODOT:
	case ODOTPTR:
	case OINDEX:
	case OCALLFUNC:
	case OCALLMETH:
	case OCALLINTER:
		igen(n, &n1, res); // まずigenで間接参照
		regalloc(a, types[tptr], &n1); // 新しいレジスタaを割り当て
		gmove(&n1, a); // n1からaに移動
		regfree(&n1);
		break;
	default:
		regalloc(a, n->type, res); // 新しいレジスタaを割り当て
		cgen(n, a); // cgenで値を計算しaに格納
		break;
	}
}

cgenr は、ノード n の値を計算し、その結果を新しく割り当てられたレジスタ a に格納します。addable なノードの場合は直接移動し、そうでない場合は igen や cgen を呼び出して計算結果を a に格納します。重要なのは、regalloc(a, ...) が cgenr の内部で、かつ n の値が計算される直前に行われる点です。

新しく導入された agenr 関数 (例: src/cmd/5g/cgen.c): agenr は agen の複雑な OINDEX 処理ロジックをそのまま引き継いでいます。しかし、agenr は結果を *a に格納し、agen のように gmove(&n3, res) で最終的な res に移動するのではなく、呼び出し元が *a を利用して gmove を行うことを期待しています。これにより、レジスタのライフタイムをより細かく制御できるようになります。

src/cmd/5g/gsubr.c および src/cmd/6g/gsubr.c の変更

sudoaddable 関数の OINDEX ケースに return 0; が追加されました。

変更前:

	case OINDEX:
		// ... 既存のロジック ...

変更後:

	case OINDEX:
		return 0; // OINDEXノードはsudoaddableではないと明示的に指定
		// disabled: OINDEX case is now covered by agenr
		// for a more suitable register allocation pattern.

この変更により、コンパイラは OINDEX ノードを sudoaddable ではないと判断し、agen の代わりに igen や agenr を使用するようになります。これは、agenr がレジスタをより遅延して割り当てる戦略を採用しているため、レジスタ枯渇問題の解決に寄与します。

test/torture.go の追加テストケース

新しいテストケースが追加され、この修正が正しく機能することを確認しています。

• IndexChain1: 定数インデックスによる深いネスト。
• IndexChain2: 非定数インデックスによる深いネスト。
• IndexChain3: s[s[s[...]]] のような、値がインデックスとして使用される深いネスト。

これらのテストケースは、修正が適用される前のコンパイラではレジスタ枯渇エラーを引き起こす可能性があった式を網羅しており、修正の有効性を検証します。

関連リンク

• GitHubコミットページ: https://github.com/golang/go/commit/0b2353edcb7fc6ff100f42b1d9cc5613a6c57da1
• Go CL (Change List): https://golang.org/cl/6733055
• 関連するIssue: コミットメッセージには Update #4207 と記載されていますが、現在の golang/go GitHubリポジトリでは直接対応するIssue 4207は見つかりませんでした。これは、古いIssueトラッカーの番号であるか、またはIssueが統合・クローズされた可能性があります。

参考にした情報源リンク

• コミットメッセージと変更されたコード (src/cmd/5g/cgen.c, src/cmd/5g/gsubr.c, src/cmd/6g/cgen.c, src/cmd/6g/gsubr.c, test/torture.go)
• Goコンパイラの内部構造に関する一般的な知識
• コンパイラのレジスタ割り当てに関する一般的な知識
• Go言語のSliceとArrayの基本的な動作