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

このコミットは、Goコンパイラのバックエンドであるcmd/5g (ARM), cmd/6g (x86-64), cmd/8g (x86) における最適化フェーズの一つである「コピー伝播 (copy propagation)」処理のパフォーマンス改善を目的としています。具体的には、コピー伝播のループ内で発生していたO(n)の「active」フラグのリセット処理を削除し、より効率的なメカニズムに置き換えることで、コンパイル時間の短縮を図っています。

コミット

commit 6d47de2f408811304f2cc06d3debd2404b360f84
Author: Russ Cox <rsc@golang.org>
Date:   Wed Sep 11 15:22:11 2013 -0400

    cmd/5g, cmd/6g, cmd/8g: remove O(n) reset loop in copyprop
    
    Simpler version of CL 13084043.
    
    R=ken2
    CC=golang-dev
    https://golang.org/cl/13602045

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

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

元コミット内容

cmd/5g, cmd/6g, cmd/8g: remove O(n) reset loop in copyprop

このコミットは、Goコンパイラの各アーキテクチャ（ARM, x86-64, x86）向けのバックエンドにおいて、コピー伝播最適化処理内のO(n)の（線形時間計算量を持つ）リセットループを削除するものです。これは、以前の変更（CL 13084043）をよりシンプルにしたバージョンであると説明されています。

変更の背景

Goコンパイラは、ソースコードを機械語に変換する過程で様々な最適化を行います。コピー伝播（copy propagation）はその一つで、ある変数の値が別の変数にコピーされた後、元の変数が使われている箇所をコピー先の変数に置き換えることで、冗長なデータ移動をなくし、コードの効率を高めます。

この最適化処理は、プログラムの制御フローグラフ（Control Flow Graph, CFG）上を探索しながら行われます。探索中に同じノード（プログラムの基本ブロックや命令）を複数回処理することを避けるため、通常は各ノードに「訪問済み」や「アクティブ」といったフラグを設定します。処理が完了した後、次のコピー伝播の実行に備えてこれらのフラグをリセットする必要があります。

従来のGoコンパイラのコピー伝播の実装では、この「active」フラグのリセットに、制御フローグラフの全ノードを線形に走査するO(n)のループが使われていました。プログラムの規模が大きくなり、制御フローグラフのノード数が増えるにつれて、このリセット処理がコンパイル時間のボトルネックとなる可能性がありました。特に、コピー伝播が複数回実行されるようなケースでは、このオーバーヘッドが累積的に影響します。

このコミットは、この非効率なリセットループを排除し、より高速なメカニズムに置き換えることで、コンパイルパフォーマンスの向上を目指しています。

前提知識の解説

コンパイラの最適化

コンパイラの最適化とは、コンパイラが生成する機械語コードの性能（実行速度、メモリ使用量など）を向上させるための様々な変換処理のことです。コピー伝播、デッドコード削除、定数伝播、ループ最適化など、多岐にわたる手法があります。

コピー伝播 (Copy Propagation)

コピー伝播は、コンパイラの最適化手法の一つです。例えば、x = y という代入があった場合、その後のコードで x が使われている箇所を y に置き換えることで、冗長な代入やメモリ参照を減らします。

例:

a := b
c := a + 1

コピー伝播後:

a := b
c := b + 1 // 'a' の代わりに 'b' を使用

制御フローグラフ (Control Flow Graph, CFG)

制御フローグラフは、プログラムの実行可能なパスを抽象的に表現したグラフ構造です。ノードは基本ブロック（連続した命令のシーケンスで、途中に分岐やジャンプがないもの）を表し、エッジは基本ブロック間の制御の移転（ジャンプ、条件分岐など）を表します。コンパイラの最適化の多くは、このCFG上を探索することで行われます。

グラフ探索における「訪問済み」フラグ

グラフ探索アルゴリズム（深さ優先探索や幅優先探索など）では、無限ループを防ぎ、同じノードを複数回処理する無駄を省くために、各ノードに「訪問済み」や「アクティブ」といった状態を示すフラグを持たせることが一般的です。一度訪問したノードにはフラグを立て、再訪問時にはそのフラグをチェックして処理をスキップします。

計算量 (Time Complexity)

アルゴリズムの効率性を示す指標で、入力サイズ（n）に対する実行時間の増加率を表します。

• O(1) (定数時間): 入力サイズに関わらず、実行時間が一定。
• O(n) (線形時間): 入力サイズに比例して実行時間が増加。
• O(n^2) (二次時間): 入力サイズの二乗に比例して実行時間が増加。

このコミットでは、O(n)のリセットループがボトルネックとなっていたため、これを改善することが目的です。

技術的詳細

このコミットの核心は、コピー伝播アルゴリズムにおけるグラフノードの「active」状態管理の変更にあります。

従来のcopyprop関数では、copy1関数（実際の伝播処理を行う再帰関数）を呼び出す前に、制御フローグラフの全てのFlowノード（各命令に対応するフロー情報）のactiveフラグを0にリセットしていました。これは以下のループで行われていました。

for(r=g->start; r!=nil; r=r->link)
	r->active = 0;

このループは、グラフのノード数nに比例する時間（O(n)）を要します。copypropが複数回呼び出される場合、このO(n)のリセット処理が毎回実行され、コンパイル時間のオーバーヘッドとなっていました。

新しいアプローチでは、グローバル変数gactive（uint32型）を導入します。

1. peep関数の初期化時にgactiveを0に設定します。
2. copyprop関数が呼び出されるたびに、gactiveの値をインクリメントします。
3. copy1関数内でノードのactiveフラグをチェックする際、単にr->activeが1であるかどうかを見るのではなく、r->active == gactiveであるかどうかをチェックします。
4. ノードを「アクティブ」にする際には、r->active = 1とする代わりに、r->active = gactiveと設定します。

この変更により、各copypropの実行サイクルは、それぞれ異なるgactive値を持つことになります。ノードのactiveフラグが現在のgactive値と一致する場合のみ、そのノードが現在のサイクルで「アクティブ」であると判断されます。これにより、明示的に全てのノードのactiveフラグを0にリセットするO(n)ループが不要になります。

この手法は、グラフ探索アルゴリズムでよく用いられる「世代カウンタ (generation counter)」または「タイムスタンプ (timestamp)」と呼ばれる最適化パターンです。各探索フェーズにユニークなID（この場合はgactiveの値）を割り当て、ノードの訪問状態をそのIDと比較することで、全体のリセット処理をスキップします。これにより、リセット処理の計算量がO(n)からO(1)（定数時間）に削減されます。

この最適化は、特に大規模なプログラムや、コンパイラが多くの最適化パスを繰り返し実行するような場合に、コンパイル時間の顕著な改善をもたらす可能性があります。

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

変更はsrc/cmd/5g/peep.c, src/cmd/6g/peep.c, src/cmd/8g/peep.cの3つのファイルにわたっています。これらはそれぞれARM、x86-64、x86アーキテクチャ向けのGoコンパイラのバックエンド（コード生成と最適化）を担当する部分です。

各ファイルで共通して以下の変更が行われています。

1. gactive変数の追加:

   +static uint32	gactive;
   

   peep.cファイルの先頭付近に、静的グローバル変数gactiveが追加されています。これは、各コピー伝播の実行サイクルを識別するためのカウンタとして機能します。

2. peep関数でのgactive初期化:

   @@ -63,6 +65,7 @@ peep(Prog *firstp)
    	g = flowstart(firstp, sizeof(Flow));
    	if(g == nil)
    		return;
   +	gactive = 0; // 初期化
    
    loop1:
    	if(debug['P'] && debug['v'])
   

   peep関数の開始時にgactiveが0に初期化されます。これは、コンパイラの最適化パスが開始される際に、gactiveが既知の状態から始まることを保証します。

3. copyprop関数でのリセットループの削除とgactiveのインクリメント:

   @@ -360,15 +363,14 @@ copyprop(Graph *g, Flow *r0)
    {
    	Prog *p;
    	Adr *v1, *v2;
   -	Flow *r; // 削除
    
   +	USED(g); // 追加
    	p = r0->prog;
    	v1 = &p->from;
    	v2 = &p->to;
    	if(copyas(v1, v2))
    		return 1;
   -	for(r=g->start; r!=nil; r=r->link) // 削除
   -		r->active = 0; // 削除
   +	gactive++; // 追加: 世代カウンタをインクリメント
    	return copy1(v1, v2, r0->s1, 0);
    }
   

   • 従来のO(n)のリセットループ（for(r=g->start; r!=nil; r=r->link) r->active = 0;）が削除されています。
   • 代わりにgactive++;が追加され、copypropが呼び出されるたびにgactiveの値がインクリメントされます。これにより、各コピー伝播の実行が新しい「世代」として扱われます。
   • Flow *r;の宣言も不要になったため削除されています。
   • USED(g);が追加されていますが、これはコンパイラの警告を抑制するためのマクロで、g変数がデバッグビルドなどで使用されない場合に警告が出ないようにするためのものです。本質的なロジック変更ではありません。

4. copy1関数でのactiveフラグのチェックと設定の変更:

   @@ -378,12 +380,12 @@ copy1(Adr *v1, Adr *v2, Flow *r, int f)
    	int t;
    	Prog *p;
    
   -	if(r->active) { // 従来のチェック
   +	if(r->active == gactive) { // 新しいチェック: 現在の世代と一致するか
    		if(debug['P'])
    			print("act set; return 1\\n");
    		return 1;
    	}
   -	r->active = 1; // 従来の設定
   +	r->active = gactive; // 新しい設定: 現在の世代の値を設定
    	if(debug['P'])
    		print("copy %D->%D f=%d\\n", v1, v2, f);
    	for(; r != nil; r = r->s1) {
   

   • if(r->active)という従来のチェックがif(r->active == gactive)に変更されています。これにより、ノードが現在のコピー伝播サイクルで既に訪問済みであるかを効率的に判断します。
   • r->active = 1という従来のフラグ設定がr->active = gactiveに変更されています。これにより、ノードが現在のgactiveの世代で訪問されたことを記録します。

これらの変更により、コピー伝播の各実行サイクルにおいて、ノードのactiveフラグを個別にリセットする必要がなくなり、gactiveのインクリメントと比較だけで済むため、全体的なパフォーマンスが向上します。

コアとなるコードの解説

このコミットの核心は、コンパイラの最適化パスにおける「訪問済み」フラグのリセット方法を根本的に変更した点にあります。

Goコンパイラのバックエンドでは、peep.cファイル群が命令レベルの最適化（peephole optimization）を担当しています。その中でcopyprop関数はコピー伝播最適化を実行し、copy1関数は実際のグラフ探索と伝播ロジックを再帰的に処理します。

変更前（非効率なリセット）

変更前は、copyprop関数が呼び出されるたびに、その内部で以下のようなループが実行されていました。

for(r=g->start; r!=nil; r=r->link)
	r->active = 0;

このループは、制御フローグラフ内の全てのFlowノード（r）を走査し、それぞれのactiveフラグを明示的に0にリセットしていました。Flowノードは、プログラムの各命令や基本ブロックに対応するデータ構造であり、activeフラグはcopy1関数が既にそのノードを訪問したかどうかを示すために使われます。

このリセット処理は、グラフのノード数Nに比例する時間計算量O(N)を持ちます。もしcopypropがコンパイル中に複数回実行される場合（例えば、異なる最適化パスの一部として、あるいは反復的な最適化アルゴリズムの中で）、このO(N)のリセット処理が毎回繰り返され、コンパイル時間のボトルネックとなる可能性がありました。

変更後（世代カウンタによる効率化）

このコミットでは、この非効率なリセットループを排除し、代わりに「世代カウンタ（generation counter）」または「タイムスタンプ」と呼ばれるテクニックを導入しています。

1. gactiveの導入: static uint32 gactive; というグローバル変数（実際にはファイルスコープの静的変数）が導入されました。これは、コピー伝播の各実行サイクル（世代）を一意に識別するためのカウンタとして機能します。

2. peepでの初期化: gactive = 0; peep関数（最適化パスの開始点）でgactiveが0に初期化されます。

3. copypropでの世代更新: gactive++; copyprop関数が呼び出されるたびに、gactiveの値がインクリメントされます。これにより、新しいコピー伝播の実行が開始されるたびに、gactiveはユニークな値を持つことになります。

4. copy1での「訪問済み」チェック: if(r->active == gactive) copy1関数内でノードrが既に訪問済みであるかをチェックする際、従来のif(r->active)（activeが非ゼロなら訪問済み）ではなく、r->activeが現在のgactiveの値と一致するかどうかをチェックします。

   • もしr->activeがgactiveと一致すれば、そのノードは現在のコピー伝播サイクルで既に訪問済みであると判断されます。
   • もしr->activeがgactiveと一致しなければ、そのノードは現在のサイクルではまだ訪問されていないと判断されます（あるいは、以前のサイクルで訪問されたが、現在のサイクルではまだ訪問されていない）。

5. copy1での「訪問済み」設定: r->active = gactive; ノードrを訪問済みとしてマークする際、従来のr->active = 1ではなく、現在のgactiveの値をr->activeに設定します。

このメカニズムにより、copypropが新しいサイクルを開始するたびにgactiveがインクリメントされるため、以前のサイクルで設定されたr->activeの値は、現在のgactiveの値とは異なるものになります。したがって、明示的に全てのactiveフラグを0にリセットするループは不要になります。リセット処理の計算量は、O(N)からO(1)（gactiveのインクリメントのみ）に削減されます。

この変更は、コンパイラの最適化パスにおける一般的なパフォーマンス改善手法であり、特にグラフ探索アルゴリズムにおいて、探索ごとにグラフ全体をリセットするコストを削減するのに非常に効果的です。

関連リンク

• Go言語のコンパイラに関するドキュメントやソースコード:
  • golang/go GitHubリポジトリ
  • Go Compiler Design (公式ドキュメント)
• コンパイラ最適化に関する一般的な情報:
  • Wikipedia: コンパイラ最適化
  • Wikipedia: コピー伝播
• 制御フローグラフに関する情報:
  • Wikipedia: 制御フローグラフ

参考にした情報源リンク

• golang/go GitHubリポジトリ (特にコミット履歴と関連ファイル)
• Go issue tracker (CL 13084043) (このコミットが参照している以前の変更)
• Go issue tracker (CL 13602045) (このコミットのコードレビューリンク)
• コンパイラ最適化、データフロー解析、グラフアルゴリズムに関する一般的な知識（書籍やオンラインリソース）
• C言語の構文とセマンティクスに関する知識
• Go言語のコンパイラアーキテクチャに関する知識