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

このコミットは、Goコンパイラのcmd/5g (ARM), cmd/6g (x86-64), cmd/8g (x86) のpeep.cファイルにおける変更を元に戻すものです。具体的には、以前のコミット (CL 13084043 / ef4ee02a5853) で導入された、コンパイル速度向上のための最適化手法を元に戻しています。この最適化は、リンクリストの走査をmemsetによるメモリ初期化に置き換えることで、go install -a stdのCPU時間を約10%削減することを目的としていました。しかし、このコミットでは「よりクリーンでシンプルな方法がある」という理由で、その変更が取り消されています。

コミット

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

    undo CL 13084043 / ef4ee02a5853
    
    There is a cleaner, simpler way.
    
    ««« original CL description
    cmd/5g, cmd/6g, cmd/8g: faster compilation
    Replace linked list walk with memset.
    This reduces CPU time taken by 'go install -a std' by ~10%.
    Before:
    real            user            sys
    0m23.561s       0m16.625s       0m5.848s
    0m23.766s       0m16.624s       0m5.846s
    0m23.742s       0m16.621s       0m5.868s
    after:
    0m22.714s       0m14.858s       0m6.138s
    0m22.644s       0m14.875s       0m6.120s
    0m22.604s       0m14.854s       0m6.081s
    
    R=golang-dev, r
    CC=golang-dev
    https://golang.org/cl/13084043
    »»»
    
    TBR=dvyukov
    CC=golang-dev
    https://golang.org/cl/13352049

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

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

元コミット内容

このコミットは、以下の内容を持つ以前のコミット (CL 13084043 / ef4ee02a5853) を元に戻すものです。

コミットメッセージ（元コミット）:

cmd/5g, cmd/6g, cmd/8g: faster compilation
Replace linked list walk with memset.
This reduces CPU time taken by 'go install -a std' by ~10%.
Before:
real            user            sys
0m23.561s       0m16.625s       0m5.848s
0m23.766s       0m16.624s       0m5.846s
0m23.742s       0m16.621s       0m5.868s
after:
0m22.714s       0m14.858s       0m6.138s
0m22.644s       0m14.875s       0m6.120s
0m22.604s       0m14.854s       0m6.081s

この元コミットは、Goコンパイラのバックエンドである5g、6g、8gにおいて、コンパイル速度を向上させることを目的としていました。具体的には、リンクリストを走査してactiveフラグを設定する処理を、memset関数を用いたメモリの一括初期化に置き換えることで、パフォーマンスの改善を図りました。これにより、go install -a stdコマンドの実行時間が約10%短縮されたと報告されています。

変更の背景

このコミットの背景には、Goコンパイラのパフォーマンス最適化への継続的な取り組みがあります。元々、CL 13084043では、コンパイラのピーフール最適化（peephole optimization）の一部であるコピー伝播（copy propagation）処理において、Flow構造体のactiveフィールドを管理する方法を変更することで、コンパイル時間の短縮を目指しました。

以前の実装では、Flow構造体のリンクリストを順にたどり、各要素のactiveフィールドにインデックスを割り当てていました。これは、既に処理された要素を追跡するためのものでした。しかし、このリンクリストの走査は、特に大規模なプログラムのコンパイル時にオーバーヘッドとなる可能性がありました。

そこで、元コミットでは、activeフィールドの管理にmemsetを使用するアプローチが採用されました。これは、activeフラグを保持するための配列を動的に確保し、memsetを使って一括でゼロクリアすることで、リンクリストの走査と個別の代入処理を置き換えようとしたものです。これにより、ベンチマークでは顕著な速度向上が見られました。

しかし、この現在のコミットでは、その変更が「よりクリーンでシンプルな方法がある」という理由で元に戻されています。これは、memsetによるアプローチが、コードの可読性、保守性、あるいは将来的な拡張性において、何らかのトレードオフを伴っていた可能性を示唆しています。あるいは、memsetを使用するよりも、より効率的で、かつコードの複雑さを増さない代替手段が発見されたと考えられます。コンパイラのコードベースは非常に複雑であり、パフォーマンスとコードの品質（シンプルさ、保守性）のバランスは常に重要な考慮事項です。

前提知識の解説

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

Go言語の初期のコンパイラは、ターゲットアーキテクチャごとに独立した実装を持っていました。

• cmd/5g: ARMアーキテクチャ向けのコンパイラバックエンド。
• cmd/6g: x86-64 (AMD64) アーキテクチャ向けのコンパイラバックエンド。
• cmd/8g: x86 (32-bit Intel) アーキテクチャ向けのコンパイラバックエンド。

これらのコンパイラは、Goのソースコードを中間表現に変換し、最終的に各アーキテクチャの機械語に変換する役割を担っていました。現在のGoコンパイラは、より統合されたツールチェーンに進化していますが、このコミットが作成された2013年当時は、これらの個別のバックエンドが使用されていました。

ピーフール最適化 (Peephole Optimization)

ピーフール最適化は、コンパイラ最適化の一種で、生成された機械語コードや中間コードの小さな「窓（peephole）」を覗き込み、より効率的な命令シーケンスに置き換える手法です。例えば、冗長な命令の削除、より高速な命令への置き換え、レジスタの効率的な利用などが含まれます。これは、コード生成の最終段階で行われることが多い、局所的な最適化です。

コピー伝播 (Copy Propagation)

コピー伝播は、コンパイラ最適化の一種で、ある変数の値が別の変数にコピーされた後、そのコピーされた変数が使用されている箇所を、元の変数の値で直接置き換えるものです。これにより、冗長なコピー操作を排除し、レジスタの使用効率を向上させたり、他の最適化の機会を創出したりすることができます。

例:

a = x
b = a + 1
c = a + 2

コピー伝播後:

a = x
b = x + 1
c = x + 2

この最適化は、変数の「アクティブ」な状態（つまり、その変数がまだ使用される可能性があるかどうか）を追跡する必要があります。

Flow構造体とProg構造体

Goコンパイラのバックエンドでは、プログラムの制御フローや命令を表すために様々なデータ構造が使用されます。

• Prog (Program Instruction): コンパイラの中間表現における個々の命令（アセンブリ命令に相当するもの）を表す構造体と考えられます。fromとtoフィールドは、命令のオペランド（ソースとデスティネーション）を表すAdr（アドレス）構造体へのポインタであると推測されます。
• Flow: 制御フローグラフ（Control Flow Graph, CFG）のノードやエッジ、あるいは最適化パスにおける特定の状態を追跡するための補助的なデータ構造であると推測されます。activeフィールドは、この最適化パスにおいて、特定のFlowノードが現在「アクティブ」であるか、つまり処理中であるか、あるいは既に処理済みであるかをマークするために使用されるフラグであると考えられます。s1フィールドは、リンクリストの次の要素へのポインタである可能性があります。

memsetとrealloc

• memset: C言語の標準ライブラリ関数で、指定されたメモリ領域を特定の値で埋めるために使用されます。高速に大きなメモリブロックを初期化するのに適しています。
• realloc: C言語の標準ライブラリ関数で、以前に割り当てられたメモリブロックのサイズを変更するために使用されます。必要に応じてメモリブロックを移動し、新しいサイズに調整します。

元コミットでは、activeフラグを管理するために、nactiveとactiveというグローバル変数（または静的変数）が導入され、reallocでメモリを動的に確保し、memsetで初期化していました。

技術的詳細

このコミットは、Goコンパイラのピーフール最適化におけるコピー伝播処理の内部実装に関するものです。コピー伝播では、プログラムの命令列を走査し、冗長なコピー操作を特定して削除します。この処理中に、既に訪問した命令や処理中の命令をマークするために「アクティブ」な状態を追跡する必要があります。

元コミットでは、この「アクティブ」状態の追跡に、Flow構造体のリンクリストを走査して各Flowノードのactiveフィールドにユニークなインデックスを割り当てる代わりに、uchar *activeという配列とmemsetを使用するアプローチが導入されました。

元コミットのアプローチ（取り消された変更）:

1. peep関数内で、Flowリンクリストを走査し、各r->activeにインデックスtを割り当てるループが削除されました。
2. copyprop関数内で、static uchar *active;とstatic int nactive;という変数が導入されました。
3. copyprop関数内で、g->num（おそらくFlowノードの総数）に基づいてactive配列のサイズをreallocで調整し、memset(active, 0, g->num);で配列全体をゼロクリアしていました。
4. copy1関数内で、if(active[r->active])というチェックとactive[r->active] = 1;という設定が行われていました。これは、r->activeがインデックスとして使用され、active配列が訪問済みフラグのビットマップのように機能していたことを示唆しています。

このコミットによる変更（元に戻された状態）: このコミットでは、上記の変更が元に戻され、元のリンクリストベースのアプローチに戻されています。

1. peep関数内のforループが復活し、r->active = t;によって各Flowノードにインデックスが割り当てられるようになりました。
2. static uchar *active;とstatic int nactive;の宣言が削除されました。
3. copyprop関数内で、memsetによる初期化が削除され、代わりにfor(r=g->start; r!=nil; r=r->link) r->active = 0;というリンクリストを走査してr->activeを個別にゼロクリアするループが復活しました。
4. copy1関数内で、if(active[r->active])がif(r->active)に、active[r->active] = 1;がr->active = 1;に戻されました。これは、r->activeフィールド自体がブール値（0または1）として使用され、訪問済みフラグとして機能することを示しています。

この変更は、memsetアプローチがもたらすパフォーマンス上の利点（約10%の速度向上）よりも、コードのシンプルさ、可読性、あるいは潜在的なバグのリスクを避けることの重要性が優先されたことを示唆しています。memsetと動的なメモリ割り当て（realloc）は、C言語では一般的な最適化手法ですが、コンパイラのような複雑なシステムでは、その導入が予期せぬ副作用やデバッグの困難さを引き起こす可能性があります。特に、r->activeがインデックスとして使われる場合、そのインデックスが常にactive配列の範囲内にあることを保証する必要があり、これはリンクリストの走査で直接フラグを立てるよりも複雑になる可能性があります。

「よりクリーンでシンプルな方法」とは、おそらくFlow構造体自身のactiveフィールドを直接フラグとして使用し、リンクリストを走査して個別に設定・クリアする、元の直感的なアプローチを指していると考えられます。これにより、余分な配列の管理やメモリ割り当てのオーバーヘッドがなくなります。

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

変更は、Goコンパイラのバックエンドであるsrc/cmd/5g/peep.c, src/cmd/6g/peep.c, src/cmd/8g/peep.cの3つのファイルにわたっています。これらのファイルは、それぞれ異なるアーキテクチャ向けのピーフール最適化を担当しています。変更内容はほぼ同一です。

src/cmd/5g/peep.c (例)

--- a/src/cmd/5g/peep.c
+++ b/src/cmd/5g/peep.c
@@ -63,8 +63,6 @@ peep(Prog *firstp)
  	g = flowstart(firstp, sizeof(Flow));
  	if(g == nil)
  		return;
- 	for(r=g->start, t=0; r!=nil; r=r->link, t++)
- 		r->active = t;
 
  loop1:
  	if(debug['P'] && debug['v'])
@@ -345,9 +343,6 @@ gotit:
  	return 1;
  }
  
-static uchar *active;
-static int nactive;
-
 /*
  * The idea is to remove redundant copies.
  *	v1->v2	F=0
@@ -365,17 +360,15 @@ copyprop(Graph *g, Flow *r0)
  	Prog *p;
  	Adr *v1, Adr *v2;
 +	Flow *r;
  
  	p = r0->prog;
  	v1 = &p->from;
  	v2 = &p->to;
  	if(copyas(v1, v2))
  		return 1;
--	if(nactive < g->num) {
--		nactive = g->num;
--		active = realloc(active, g->num);
--	}
-- 	memset(active, 0, g->num);
++	for(r=g->start; r!=nil; r=r->link)
++		r->active = 0;
  	return copy1(v1, v2, r0->s1, 0);
  }
  
@@ -385,12 +378,12 @@ copy1(Adr *v1, Adr *v2, Flow *r, int f)
  	int t;
  	Prog *p;
  
--	if(active[r->active]) {
-+	if(r->active) {
  		if(debug['P'])
  			print("act set; return 1\n");
  		return 1;
  	}
--	active[r->active] = 1;
-+	r->active = 1;
  	if(debug['P'])
  		print("copy %D->%D f=%d\n", v1, v2, f);
  	for(; r != nil; r = r->s1) {

コアとなるコードの解説

このコミットの主要な変更点は、Flow構造体のactiveフィールドの利用方法を元に戻したことです。

1. peep関数内の変更:

   • 削除された行: for(r=g->start, t=0; r!=nil; r=r->link, t++) r->active = t;
     • これは、元コミットで削除されたループで、Flowリンクリストを走査し、各Flowノードのactiveフィールドにユニークな整数インデックスを割り当てていました。このインデックスは、active配列のオフセットとして使用されることを意図していました。このコミットでは、このループが復活しています。

2. グローバル/静的変数の削除:

   • 削除された行: static uchar *active; と static int nactive;
     • これらは、元コミットでmemsetベースのアプローチのために導入された、activeフラグを保持する動的配列とそのサイズを管理するための変数でした。このコミットでは、これらの変数が不要になったため削除されています。

3. copyprop関数内の変更:

   • 削除された行:

     if(nactive < g->num) {
         nactive = g->num;
         active = realloc(active, g->num);
     }
     memset(active, 0, g->num);
     

     • これは、元コミットでactive配列を動的にリサイズし、memsetでゼロクリアしていた部分です。
   • 追加された行: for(r=g->start; r!=nil; r=r->link) r->active = 0;
     • このループは、Flowリンクリストを走査し、各Flowノードのactiveフィールドを個別に0に設定しています。これは、memsetによる一括初期化の代わりに、元のリンクリスト走査による初期化に戻したものです。r->activeが直接フラグとして機能するため、0は「未訪問」を意味します。

4. copy1関数内の変更:

   • 変更された行: if(active[r->active]) から if(r->active) へ
     • 元コミットでは、r->activeをインデックスとしてactive配列を参照していましたが、このコミットではr->active自体がブール値（0または1）として機能するため、直接その値をチェックするように変更されています。
   • 変更された行: active[r->active] = 1; から r->active = 1; へ
     • 同様に、active配列の特定のインデックスに1を設定する代わりに、r->activeフィールド自体に1を設定することで、「訪問済み」としてマークしています。

これらの変更により、activeフラグの管理は、動的な配列とmemsetを使用する複雑な方法から、Flow構造体自身のフィールドを直接利用し、リンクリストを走査して個別に設定する、よりシンプルで直接的な方法に戻されました。これにより、コードの可読性と保守性が向上し、潜在的なメモリ管理の複雑さが排除されたと考えられます。

関連リンク

• 元コミット (CL 13084043): https://golang.org/cl/13084043 (このコミットで取り消された変更の元となるChange List)
• このコミット (CL 13352049): https://golang.org/cl/13352049 (このコミット自体のChange List)

参考にした情報源リンク

• Go言語のコンパイラに関する一般的な情報:
  • Go Compiler Internals (古い情報ですが、当時のコンパイラの構造を理解するのに役立つ可能性があります): https://go.dev/doc/articles/go_compiler_internals.html
• ピーフール最適化に関する一般的な情報:
  • Wikipedia: Peephole optimization: https://en.wikipedia.org/wiki/Peephole_optimization
• コピー伝播に関する一般的な情報:
  • Wikipedia: Copy propagation: https://en.wikipedia.org/wiki/Copy_propagation
• C言語のmemset関数:
  • cppreference.com: memset: https://en.cppreference.com/w/c/string/byte/memset
• C言語のrealloc関数:
  • cppreference.com: realloc: https://en.cppreference.com/w/c/memory/realloc