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

このコミットは、Go言語の初期のコンパイラである6g（x86-64アーキテクチャ向け）に、最初の最適化パスを導入するものです。具体的には、レジスタ割り当て（Register Allocation）とピーフホール最適化（Peephole Optimization）のフレームワークが追加され、コンパイラが生成するアセンブリコードの効率を向上させることを目的としています。この変更は、Goコンパイラのコード生成パイプラインにおける重要な進化を示しています。

コミット

commit 2dd16a32083c716b80204c66d6bf1f2c8fadeccc
Author: Ken Thompson <ken@golang.org>
Date:   Tue Nov 18 19:24:37 2008 -0800

    first cut at optimizing
    
    R=r
    OCL=19564
    CL=19564

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

https://github.com/golang/go/commit/2dd16a32083c716b80204c66d6bf1f2c8fadeccc

元コミット内容

first cut at optimizing

この簡潔なコミットメッセージは、Goコンパイラにおける最適化機能の最初の実装であることを示しています。

変更の背景

Go言語の初期開発段階において、コンパイラはまず機能的なコードを生成することに重点を置いていました。しかし、生成されるコードのパフォーマンスは、言語の実用性にとって不可欠です。このコミットは、コンパイラが生成するアセンブリコードの品質を向上させ、実行速度を速めるための最初のステップとして、最適化パスを導入するものです。

特に、このコミットで追加されたコードの多くは、Inferno OSのutils/6c（x86-64向けのCコンパイラ）から派生していることが、各ファイルのヘッダーコメントから読み取れます。これは、GoコンパイラがPlan 9やInfernoのツールチェインの設計思想とコードベースを初期段階で活用していたことを示唆しています。既存の成熟したコンパイラ技術を再利用することで、Goコンパイラの開発を加速させたと考えられます。

前提知識の解説

コンパイラ最適化

コンパイラ最適化とは、コンパイラがソースコードを機械語に変換する際に、生成されるコードの実行速度、サイズ、消費電力などを改善するプロセスです。最適化は通常、コンパイラのバックエンドで行われ、中間表現やアセンブリコードに対して様々な変換を適用します。

レジスタ割り当て (Register Allocation)

レジスタ割り当ては、コンパイラ最適化の最も重要なフェーズの一つです。プログラムの実行中に頻繁にアクセスされる変数を、メモリではなくCPUの高速なレジスタに割り当てることで、メモリアクセスのオーバーヘッドを削減し、プログラムの実行速度を大幅に向上させます。レジスタの数は限られているため、どの変数をどのレジスタに割り当てるか、いつメモリに退避（spill）させるかなどを決定する複雑なアルゴリズムが用いられます。このコミットでは、データフロー解析（Dataflow Analysis）を用いて変数の生存期間（liveness）を分析し、レジスタ割り当ての決定に利用しています。

データフロー解析 (Dataflow Analysis)

データフロー解析は、プログラムの実行中に変数の値や状態がどのように変化するかを分析するコンパイラ技術です。レジスタ割り当てにおいては、変数がどのプログラムポイントで「生きている」（将来使用される可能性がある）かを判断するために使用されます。これにより、不要になった変数が占有していたレジスタを解放し、他の変数に再利用できるようになります。

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

ピーフホール最適化は、コンパイラ最適化の一種で、生成されたアセンブリコードの小さな「窓（peephole）」、つまり数命令のシーケンスを検査し、より効率的な同等のシーケンスに置き換える手法です。例えば、冗長なロード/ストア命令の削除、定数伝播、特定の命令のより効率的な代替命令への置換などが行われます。このコミットでは、MOV命令の冗長性除去や、ADD/SUB命令のINC/DECへの変換などが実装されています。

ビットセット (Bitset)

ビットセットは、ブール値の集合を効率的に表現するためのデータ構造です。各ブール値はビットに対応し、ビット演算（AND, OR, NOTなど）を用いて集合演算を高速に行うことができます。コンパイラのデータフロー解析では、変数の生存情報や到達定義（reaching definitions）などの集合を表現するために広く利用されます。このコミットでは、Bits構造体とそれに対するビット演算関数がbits.cで定義されており、データフロー解析の基盤となっています。

Inferno OS / Plan 9 コンパイラ (6c)

Inferno OSとPlan 9は、ベル研究所で開発されたオペレーティングシステムです。これらのシステムには、独自のツールチェインとコンパイラ（例えば、x86-64向けの6c）が含まれていました。Go言語の初期開発は、これらのシステムの影響を強く受けており、コンパイラのコードベースにもその痕跡が見られます。このコミットは、6cコンパイラの最適化ロジックをGoの6gコンパイラに移植したものであることが、ソースコードの著作権表示から明らかです。

技術的詳細

このコミットは、Goコンパイラ6gにレジスタ割り当てとピーフホール最適化の機能を追加するために、以下の主要なコンポーネントを導入しています。

1. opt.h: 最適化パスで使用される主要なデータ構造とマクロを定義するヘッダーファイルです。

   • Bits構造体: ビットセットを表現し、データフロー解析における変数の集合を管理します。
   • Reg構造体: プログラムの各命令（Prog）に対応するレジスタ割り当て情報を保持します。これには、命令によって設定（set）される変数、使用（use1, use2）される変数、データフロー解析の結果（refbehind, refahead, calbehind, calahead, regdiff, act）、ループ情報（loop）、逆ポストオーダー（rpo）などが含まれます。
   • Var構造体: 最適化対象となる変数のオフセット、シンボル、名前、型を保持します。
   • Rgn構造体: レジスタ割り当ての「領域（region）」を定義し、レジスタ割り当てのコストや割り当てられたレジスタ番号を管理します。
   • データフロー解析に関連するマクロ（BLOAD, BSTORE, LOAD, STORE）や定数（BITS, NVAR, CLOAD, CREF, CINF, LOOP）も定義されています。

2. bits.c: Bits構造体に対する基本的なビット演算関数を提供します。

   • bor, band: ビットセットのOR、AND演算。
   • bany: ビットセットに1つでもセットされたビットがあるか。
   • beq: 2つのビットセットが等しいか。
   • bnum: ビットセットで最も小さいセットされたビットのインデックスを返す。
   • blsh: 指定されたインデックスのビットのみがセットされたビットセットを生成。
   • bset: 指定されたインデックスのビットがセットされているか。
   • bitno: 整数値で最も小さいセットされたビットのインデックスを返す。
   • Qconv: デバッグ出力用にBits構造体を文字列に変換する関数。

3. reg.c: レジスタ割り当ての主要なロジックを実装しています。

   • regopt関数: レジスタ割り当てのメインエントリポイントです。
     • パス1: プログラムの各命令（Prog）に対応するReg構造体を作成し、命令のfromとtoオペランドから変数の使用（use1, use2）と設定（set）情報を収集します。
     • パス2: 分岐命令のターゲットをReg構造体へのポインタに変換し、逆方向のリンク（p2link, p2）を構築します。
     • パス2.5: ループ構造を特定します。
     • パス3: データフロー解析（後方伝播）を実行し、変数の生存情報（refahead, calahead）を計算します。これは、prop関数によって再帰的に行われます。
     • パス4: レジスタと変数の同期（前方伝播）を行います。これはsynch関数によって行われます。
     • パス5: レジスタ割り当ての「領域」を特定し、各領域のコストを計算します（paint1関数）。コストは、その領域でレジスタを割り当てることの利益を示します。
     • パス6: 実際にレジスタを割り当て、コードを書き換えます（paint2, paint3関数）。allreg関数は、利用可能なレジスタの中から最適なものを選択します。
   • mkvar関数: Addr構造体からBits構造体を生成し、変数を識別します。
   • prop関数: データフロー解析の後方伝播ロジックを実装します。
   • synch関数: データフロー解析の前方伝播ロジックを実装します。

4. peep.c: ピーフホール最適化のロジックを実装しています。

   • peep関数: ピーフホール最適化のメインエントリポイントです。
     • Reg構造体のリンクを完成させ、命令間の関係を正確に表現します。
     • ループ内で、copypropとsubpropを繰り返し適用し、最適化を行います。
   • excise関数: 最適化によって不要になった命令をANOP（No Operation）命令に置き換えます。
   • uniqp, uniqs: 命令のユニークな先行命令（predecessor）または後続命令（successor）を検索します。
   • regtyp: Addrがレジスタ型であるかを判定します。
   • subprop関数: レジスタの置換（substitution propagation）を行います。例えば、MOV A, R0の後にMOV R0, R1がある場合、MOV A, R1に変換し、MOV R0, R1を削除できるようにします。
   • copyprop関数: コピー伝播（copy propagation）を行います。MOV V1, V2という命令がある場合、その後のV2の使用をV1に置き換えることで、MOV命令を削除できるようにします。
   • copy1, copyu, copyas, copyau, copysub: copypropとsubpropをサポートするヘルパー関数で、アドレスの比較、置換、使用/設定の判定を行います。

統合と変更点

• src/cmd/6g/Makefile: 新しく追加されたbits.c, opt.h, peep.c, reg.cがビルドプロセスに組み込まれるように変更されています。
• src/cmd/6g/gen.c: regopt(ptxt)の呼び出しがコメントアウトから有効化され、コード生成の最後にレジスタ割り当てと最適化が実行されるようになりました。
• src/cmd/6g/gg.h: Prog構造体にvoid* reg;フィールドが追加され、各命令が対応するReg構造体へのポインタを持つことができるようになりました。これにより、命令とレジスタ割り当て情報の間の関連付けが容易になります。また、ushort txt[NTYPE*NTYPE];が削除されており、これはgsubr.cのbuildtxt関数の削除と関連しています。
• src/cmd/6g/gsubr.c: buildtxt関数が削除されました。この関数は、型間の移動命令（AMOVL, AMOVQなど）を決定するためのテーブルを構築していましたが、新しいレジスタ割り当てと最適化のフレームワークによってその役割が置き換えられたと考えられます。
• src/cmd/6g/obj.c: プログラムカウンタ（pcloc）の計算ロジックが追加され、分岐命令のターゲットアドレスが正しく解決されるようになりました。これは、最適化パスが命令の順序を変更したり、新しい命令を挿入したりする際に重要です。

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

このコミットは、主に以下の新しいファイルと既存ファイルの変更によって構成されています。

新規ファイル:

• src/cmd/6g/bits.c: ビットセット操作のためのユーティリティ関数群。
• src/cmd/6g/opt.h: 最適化パスで使用されるデータ構造とマクロの定義。
• src/cmd/6g/peep.c: ピーフホール最適化のロジック。
• src/cmd/6g/reg.c: レジスタ割り当てとデータフロー解析の主要ロジック。

変更された既存ファイル:

• src/cmd/6g/Makefile: 新規ファイルの追加とビルド設定の更新。
• src/cmd/6g/gen.c: regopt関数の呼び出しを有効化。
• src/cmd/6g/gg.h: Prog構造体へのregフィールド追加、txt配列の削除。
• src/cmd/6g/gsubr.c: buildtxt関数の削除。
• src/cmd/6g/obj.c: プログラムカウンタの計算と分岐ターゲットの解決ロジックの追加。

コアとなるコードの解説

opt.h の Reg 構造体

struct	Reg
{
	Bits	set;        // この命令で設定される変数（ビットセット）
	Bits	use1;       // この命令の第一オペランドで使用される変数（ビットセット）
	Bits	use2;       // この命令の第二オペランドで使用される変数（ビットセット）

	Bits	refbehind;  // 後方から参照される変数（データフロー解析結果）
	Bits	refahead;   // 前方へ参照される変数（データフロー解析結果）
	Bits	calbehind;  // 後方から呼び出しによって変更される変数（データフロー解析結果）
	Bits	calahead;   // 前方へ呼び出しによって変更される変数（データフロー解析結果）
	Bits	regdiff;    // レジスタ割り当ての差分
	Bits	act;        // アクティブな変数

	int32	regu;       // レジスタ使用情報
	int32	loop;       // ループ情報
	int32	rpo;        // 逆ポストオーダー番号
	int32	active;     // アクティブフラグ

	Reg*	p1;         // 第一先行命令のReg構造体へのポインタ
	Reg*	p2;         // 第二先行命令のReg構造体へのポインタ
	Reg*	p2link;     // p2リストのリンク
	Reg*	s1;         // 第一後続命令のReg構造体へのポインタ
	Reg*	s2;         // 第二後続命令のReg構造体へのポインタ
	Reg*	link;       // Reg構造体のリストリンク
	Prog*	prog;       // 対応するProg命令へのポインタ
};

このReg構造体は、各アセンブリ命令（Prog）に対応するメタデータを保持し、データフロー解析とレジスタ割り当ての基盤となります。Bits型のフィールドは、変数の集合を効率的に表現するために使用されます。

reg.c の regopt 関数

regopt関数は、レジスタ割り当てと最適化のオーケストレーターです。複数のパスに分かれて処理を行います。

• パス1: 命令を走査し、各命令のfromとtoオペランドから、その命令がどの変数を「使用」し、どの変数を「設定」するかをReg構造体のuse1, use2, setビットセットに記録します。
• パス3 (prop関数): 後方データフロー解析のコアです。プログラムの制御フローグラフを逆順にたどり、各命令のrefahead（その命令以降で参照される変数）とcalahead（その命令以降で呼び出しによって変更される変数）を計算します。これは、変数の生存期間分析に不可欠です。
• パス4 (synch関数): 前方データフロー解析のコアです。レジスタと変数の同期情報を前方へ伝播させます。
• パス5 (paint1関数): レジスタ割り当ての「領域」を特定し、各領域にレジスタを割り当てることの「コスト」を計算します。コストが高い領域ほど、レジスタ割り当ての恩恵が大きいと判断されます。
• パス6 (paint2, paint3関数): 実際にレジスタを割り当て、命令を書き換えます。paint2は割り当てるレジスタを決定し、paint3は決定されたレジスタを使って命令のオペランドを更新します。

peep.c の peep 関数

peep関数は、ピーフホール最適化のメインループです。

void
peep(void)
{
	Reg *r, *r1, *r2;
	Prog *p, *p1;
	int t;

	/*
	 * complete R structure
	 */
	// ... Reg構造体のリンクを構築 ...

loop1:
	t = 0;
	for(r=firstr; r!=R; r=r->link) {
		p = r->prog;
		switch(p->as) {
		case AMOVL:
		case AMOVQ:
		case AMOVSS:
		case AMOVSD:
			if(regtyp(&p->to))
			if(regtyp(&p->from)) {
				if(copyprop(r)) { // コピー伝播
					excise(r);
					t++;
				} else
				if(subprop(r) && copyprop(r)) { // レジスタ置換とコピー伝播
					excise(r);
					t++;
				}
			}
			break;
		// ... その他の最適化ルール ...
		}
	}
	if(t)
		goto loop1; // 変更があったら再度ループ
}

peep関数は、プログラムの命令リストを走査し、copyprop（コピー伝播）やsubprop（レジスタ置換）などの最適化ルールを適用します。これらの関数は、冗長なMOV命令を削除したり、より効率的な命令に置き換えたりします。変更が適用されるたびにtがインクリメントされ、tが0でなくなる限りloop1にジャンプして最適化を繰り返します。これは、最適化が他の最適化の機会を生み出す可能性があるためです。

peep.c の copyprop と subprop

• copyprop(Reg *r0): MOV V1, V2のようなコピー命令を対象に、その後のV2の使用をV1に置き換えることで、コピー命令自体を削除できるかどうかを試みます。
• subprop(Reg *r0): MOV A, R0の後にMOV R0, R1のようなレジスタ間のコピーがある場合、MOV A, R1に変換し、MOV R0, R1を削除できるようにします。これは、レジスタの再利用を促進します。

これらの関数は、copyu, copyas, copyau, copysubといったヘルパー関数を内部で呼び出し、命令のオペランドを分析・書き換えます。

関連リンク

• Go言語の初期のコンパイラに関する情報: https://go.dev/doc/go1.0
• Inferno OS: https://www.vitanuova.com/inferno/
• Plan 9 from Bell Labs: https://plan9.io/plan9/
• コンパイラ最適化の基本概念 (Wikipedia): https://ja.wikipedia.org/wiki/%E3%82%B3%E3%83%B3%E3%83%91%E3%82%A4%E3%83%A9%E6%9C%80%E9%81%A9%E5%8C%96
• レジスタ割り当て (Wikipedia): https://ja.wikipedia.org/wiki/%E3%83%AC%E3%82%B8%E3%82%B9%E3%82%BF%E5%89%B2%E3%82%8A%E5%BD%93%E3%81%A6
• ピーフホール最適化 (Wikipedia): https://ja.wikipedia.org/wiki/%E3%83%94%E3%83%BC%E3%83%97%E3%83%9B%E3%83%BC%E3%83%AB%E6%9C%80%E9%81%A9%E5%8C%96

参考にした情報源リンク

• Go言語のソースコード (GitHub): https://github.com/golang/go
• Inferno OSのソースコード (Google Code Archive - utils/ccディレクトリ): http://code.google.com/p/inferno-os/source/browse/utils/cc/ (現在はアーカイブされており、直接アクセスは難しい場合がありますが、当時のコードベースの参照元として重要です。)
• コンパイラ設計に関する一般的な書籍やオンラインリソース (例: Dragon Book - Compilers: Principles, Techniques, and Tools)