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

このコミットは、Goコンパイラのcmd/6g（x86-64アーキテクチャ向け）およびcmd/8g（x86アーキテクチャ向け）におけるピーフホール最適化の改善と追加に関するものです。具体的には、定数によるシフト/ローテート命令がサブプロパゲーションを妨げないようにする修正、冗長なMOVLQZX命令の削除、そしてロード命令の早期発行の試みという3つの主要な変更が含まれています。

コミット

commit 3d3b4906f94a40b7dd2e66ad3ad48e86b5ce6f89
Author: Russ Cox <rsc@golang.org>
Date:   Thu May 24 12:11:32 2012 -0400

    cmd/6g: peephole fixes/additions
    
    * Shift/rotate by constant doesn't have to stop subprop. (also in 8g)
    * Remove redundant MOVLQZX instructions.
    * An attempt at issuing loads early.
      Good for 0.5% on a good day, might not be worth keeping.
      Need to understand more about whether the x86
      looks ahead to what loads might be coming up.
    
    R=ken2, ken
    CC=golang-dev
    https://golang.org/cl/6203091

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

https://github.com/golang/go/commit/3d3b4906f94a40b7dd2e66ad3ad48e86b5ce6f89

元コミット内容

このコミットは、Goコンパイラのバックエンドにおけるピーフホール最適化器の機能強化を目的としています。主な変更点は以下の通りです。

1. 定数によるシフト/ローテート命令のサブプロパゲーションへの影響緩和: 定数によるシフトまたはローテート命令が、レジスタのサブプロパゲーション（部分的な値の伝播）を不必要に停止させないように修正されました。これはcmd/6gとcmd/8gの両方に適用されています。
2. 冗長なMOVLQZX命令の削除: 不要なMOVLQZX命令（32ビット値を64ビットレジスタにゼロ拡張する命令）を特定し、削除するロジックが追加されました。これは、先行する命令によって上位ビットが既にクリアされている場合に適用されます。
3. ロード命令の早期発行の試み: メモリからのロード命令を可能な限り早期に発行することで、パイプラインの効率を向上させる試みが行われました。ただし、この最適化による性能向上は限定的（最大0.5%）であり、x86プロセッサの先行ロード（look-ahead load）の挙動に関するさらなる理解が必要であるとコメントされています。

変更の背景

コンパイラの最適化は、生成される機械語コードの性能を向上させるために不可欠です。ピーフホール最適化は、コンパイラのバックエンドで行われる最適化の一種で、生成された命令列の中から特定の短いパターン（「ピーフホール」）を見つけ出し、より効率的な命令列に置き換えることでコードを改善します。

このコミットの背景には、Goコンパイラが生成するコードの効率をさらに高めるという目標があります。特に、以下の点が課題として認識されていました。

• 不必要な最適化の停止: 特定の命令（定数シフト/ローテートなど）が、実際には影響しないにもかかわらず、より広範な最適化（サブプロパゲーション）の適用を妨げていた可能性があります。これを修正することで、より多くの最適化機会を解放できます。
• 冗長な命令の存在: MOVLQZXのような命令は、特定の状況下では冗長になることがあります。これは、前の命令によってレジスタの上位ビットが既にゼロに設定されている場合などです。このような冗長な命令を削除することで、コードサイズを削減し、実行効率を向上させることができます。
• メモリレイテンシの隠蔽: メモリからのデータロードは、CPUの実行速度に比べて時間がかかる操作です。ロード命令をできるだけ早く発行し、データが実際に必要になる前にキャッシュにロードされるようにすることで、CPUがデータを待つ時間を減らし、パイプラインのストールを回避できる可能性があります。これは「ロードパイプライニング」または「ロードの早期発行」と呼ばれ、性能向上に寄与します。

これらの課題に対処することで、Goプログラムの実行速度を微細ながらも向上させることが、このコミットの動機となっています。

前提知識の解説

このコミットを理解するためには、以下の概念についての知識が必要です。

1. コンパイラの最適化:

   • ピーフホール最適化 (Peephole Optimization): コンパイラのバックエンドで行われる最適化手法の一つ。生成されたアセンブリコードや中間表現の短いシーケンス（「ピーフホール」と呼ばれる数命令のウィンドウ）を検査し、より効率的な同等のシーケンスに置き換えます。例えば、MOV AX, AXのような冗長な命令の削除や、複数の命令をより強力な単一命令に置き換えるなどがあります。
   • サブプロパゲーション (Sub-propagation): レジスタ内の値の一部（例えば、32ビットレジスタの下位16ビット）が、そのレジスタ全体ではなく、特定の操作によってのみ影響を受ける場合に、その部分的な値の伝播を追跡する最適化手法。これにより、レジスタ全体が変更されたと見なす必要がなくなり、より多くの最適化が可能になります。
   • レジスタ割り当て (Register Allocation): プログラムの変数をCPUのレジスタに割り当てるプロセス。レジスタはメモリよりも高速なため、適切にレジスタを使用することで性能が向上します。

2. x86/x86-64アーキテクチャと命令:

   • cmd/6gとcmd/8g: Goコンパイラのバックエンドの一部で、それぞれx86-64（6g）およびx86（8g）アーキテクチャ向けのアセンブリコードを生成します。
   • MOVLQZX命令: x86-64アーキテクチャにおける命令で、「Move Long (32-bit) to Quadword (64-bit) with Zero-eXtension」を意味します。これは、32ビットのソースオペランドを読み込み、その値を64ビットのデスティネーションレジスタにコピーする際に、上位32ビットをゼロで埋める（ゼロ拡張する）命令です。例えば、MOVLQZX EAX, RAXは、EAXレジスタの32ビット値をRAXレジスタにコピーし、RAXの上位32ビットをゼロにします。
   • シフト/ローテート命令: SHL (Shift Left), SHR (Shift Right), ROL (Rotate Left), ROR (Rotate Right) など、レジスタやメモリの内容をビット単位でシフトまたはローテートする命令。
   • ロード命令: メモリからデータをレジスタに読み込む命令（例: MOV命令でメモリからレジスタへ）。

3. CPUパイプラインとメモリレイテンシ:

   • CPUパイプライン: CPUが命令を並行して処理するための仕組み。命令のフェッチ、デコード、実行、ライトバックなどのステージに分割し、異なる命令が同時に異なるステージで処理されます。
   • メモリレイテンシ: CPUがメモリからデータを読み込む際に発生する遅延時間。CPUの動作速度に比べてメモリは非常に遅いため、メモリからのロードはパイプラインのストール（停止）を引き起こす可能性があります。
   • ロードパイプライニング/早期発行: メモリロード命令を、そのデータが実際に必要になるよりも前に発行することで、メモリレイテンシを隠蔽し、パイプラインのストールを減らす技術。CPUは、必要になる前にデータをキャッシュにプリフェッチしようとします。

技術的詳細

このコミットは、Goコンパイラのピーフホール最適化器であるpeep.cファイル（src/cmd/6g/peep.cとsrc/cmd/8g/peep.c）に焦点を当てています。

1. 定数によるシフト/ローテート命令とサブプロパゲーション

subprop関数は、レジスタのサブプロパゲーション（部分的な値の伝播）を処理する役割を担っています。以前のバージョンでは、シフトやローテート命令（ARCLB, ARCLL, ARCLQなど）が、たとえシフト量が定数であっても、サブプロパゲーションを停止させていました。これは、これらの命令がレジスタの内容を複雑に変更し、部分的な値の追跡を困難にすると見なされていたためです。

しかし、シフト/ローテート命令が定数オペランドを持つ場合、その動作は予測可能であり、レジスタの特定のビット範囲にのみ影響を与える可能性があります。このコミットでは、subprop関数内のswitch文にif(p->from.type == D_CONST)という条件が追加されました。これにより、シフト/ローテート命令のソースオペランドが定数である場合、サブプロパゲーションが停止しないように変更されました。これは、コンパイラがより積極的にレジスタの部分的な値の伝播を追跡し、さらなる最適化を適用できる機会を増やすことを意味します。

同様に、ADIVBなどの除算・乗算命令も、以前はサブプロパゲーションを停止させていましたが、このコミットでswitch文の該当箇所から削除され、サブプロパゲーションを妨げないようになりました。

2. 冗長なMOVLQZX命令の削除

MOVLQZX命令は、32ビット値を64ビットレジスタにゼロ拡張するために使用されます。しかし、もしその32ビット値が既に先行する命令（例: ADDL, MOVLなど）によって32ビット演算の結果として生成されており、かつそのレジスタの上位32ビットが既にゼロにクリアされていることが保証されている場合、MOVLQZX命令は冗長になります。

このコミットでは、peep関数内に新しいループが追加され、冗長なMOVLQZX命令を特定し削除するロジックが実装されました。

• 新しいヘルパー関数prevl(Reg *r0, int reg)が導入されました。この関数は、指定されたレジスタregが、現在の命令r0の前に、32ビット演算（AADDL, AMOVLなど）によってターゲットとして使用され、その結果として上位ビットがゼロにクリアされていることが保証されるかどうかをチェックします。
• peep関数内で、AMOVLQZX命令が見つかった場合、そのソースレジスタに対してprevl関数が呼び出されます。もしprevlが真を返した場合（つまり、先行する32ビット演算によって上位ビットが既にクリアされている場合）、そのMOVLQZX命令はexcise(r)によって削除されます。

これにより、不要な命令が削減され、生成されるコードの効率が向上します。

3. ロード命令の早期発行の試み

メモリからのロード命令は、CPUのパイプラインにおいてレイテンシの原因となることがあります。ロード命令をできるだけ早く発行することで、データが実際に必要になる前にキャッシュにロードされ、パイプラインのストールを減らすことができます。

このコミットでは、peep関数内に「ロードパイプライニング」のための新しいロジックが追加されました。

• 新しいヘルパー関数pushback(Reg *r0)が導入されました。この関数は、与えられたロード命令r0を、データ依存性や副作用（例: CALL命令）を考慮しつつ、可能な限り命令ストリームの早期に移動させようとします。
• peep関数内で、AMOVB, AMOVW, AMOVL, AMOVQ, AMOVLQZXなどのロード命令（ソースがメモリで、デスティネーションがレジスタの場合）が見つかった場合、pushback関数が呼び出されます。
• pushback関数は、r0から逆方向に命令を辿り、r0を移動させても問題ない（データ依存性がない、副作用がない）最初の安全な位置を見つけます。そして、その位置にr0を移動させ、その間の命令を一つずつ後方にシフトさせます。

コミットメッセージにもあるように、この最適化は最大0.5%の性能向上に留まる可能性があり、x86プロセッサの「look-ahead load」（先行ロード）の挙動に関するさらなる理解が必要であるとされています。これは、現代のCPUが既に高度な投機的実行やプリフェッチ機構を持っているため、コンパイラによる単純な命令の並べ替えが大きな効果をもたらさない場合があることを示唆しています。

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

このコミットの主要な変更は、src/cmd/6g/peep.cとsrc/cmd/8g/peep.cの2つのファイルに集中しています。

src/cmd/6g/peep.c

• 新しい関数定義の追加:
  • static int prevl(Reg *r, int reg);
  • static void pushback(Reg *r);
  • static int regconsttyp(Adr*);
• peep関数内の変更:
  • MOVLQZX命令の冗長性除去ロジックの追加。
  • ロードパイプライニング（pushback関数呼び出し）ロジックの追加。
• 新しいヘルパー関数の実装:
  • regconsttyp(Adr *a): アドレスが定数型であるかを判定する。
  • prevl(Reg *r0, int reg): 指定されたレジスタが先行する32ビット演算によって上位ビットがクリアされているかをチェックする。
  • pushback(Reg *r0): ロード命令を早期に移動させるロジック。
• subprop関数内の変更:
  • シフト/ローテート命令（ARCLBなど）および除算/乗算命令（ADIVBなど）のswitch文の条件を修正し、定数オペランドの場合にサブプロパゲーションを停止させないように変更。具体的には、これらの命令がsubpropを停止させるリストから削除され、定数オペランドの場合にのみ停止しないように再追加されています。

src/cmd/8g/peep.c

• subprop関数内の変更:
  • src/cmd/6g/peep.cと同様に、シフト/ローテート命令および除算/乗算命令のswitch文の条件が修正されています。

コアとなるコードの解説

peep関数内のMOVLQZX削除ロジック

	// MOVLQZX removal.
	// The MOVLQZX exists to avoid being confused for a
	// MOVL that is just copying 32-bit data around during
	// copyprop.  Now that copyprop is done, remov MOVLQZX R1, R2
	// if it is dominated by an earlier ADDL/MOVL/etc into R1 that
	// will have already cleared the high bits.
	for(r=firstr; r!=R; r=r->link) {
		p = r->prog;
		if(p->as == AMOVLQZX)
		if(regtyp(&p->from)) // ソースがレジスタであるか
		if(p->from.type == p->to.type) // ソースとデスティネーションのレジスタタイプが同じか
		if(prevl(r, p->from.type)) // ソースレジスタが先行する32ビット演算でクリアされているか
			excise(r); // 命令を削除
	}

このコードは、プログラム内のすべての命令を走査し、AMOVLQZX命令を見つけます。もしその命令のソースオペランドがレジスタであり、かつそのレジスタが以前の32ビット演算によって上位ビットがゼロにクリアされていることがprevl関数によって確認された場合、そのAMOVLQZX命令は冗長であると判断され、excise関数によって命令リストから削除されます。

prevl関数

static int
prevl(Reg *r0, int reg)
{
	Prog *p;
	Reg *r;

	for(r=uniqp(r0); r!=R; r=uniqp(r)) { // r0から逆方向に命令を辿る
		p = r->prog;
		if(p->to.type == reg) { // 現在の命令のデスティネーションが対象レジスタである場合
			switch(p->as) { // その命令が32ビット演算であるかチェック
			case AADDL:
			case AANDL:
			// ... (他の32ビット演算命令) ...
			case AXORL:
				return 1; // 32ビット演算であれば真を返す
			}
			return 0; // 32ビット演算でなければ偽を返す
		}
	}
	return 0; // 対象レジスタをデスティネーションとする命令が見つからなかった場合
}

prevl関数は、与えられたレジスタregが、現在の命令r0の直前の命令シーケンスにおいて、32ビット演算（例: ADDL, MOVLなど）のデスティネーションとして使用され、その結果として上位ビットがゼロにクリアされていることが保証されるかどうかをチェックします。これにより、MOVLQZXが本当に冗長であるかを判断します。

peep関数内のロードパイプライニングロジック

	// load pipelining
	// push any load from memory as early as possible
	// to give it time to complete before use.
	for(r=firstr; r!=R; r=r->link) {
		p = r->prog;
		switch(p->as) {
		case AMOVB:
		case AMOVW:
		case AMOVL:
		case AMOVQ:
		case AMOVLQZX:
			if(regtyp(&p->to) && !regconsttyp(&p->from)) // デスティネーションがレジスタで、ソースが定数でない（メモリロード）場合
				pushback(r); // pushback関数を呼び出す
		}
	}

このコードは、メモリからレジスタへのロード命令（AMOVBなど）を特定し、pushback関数を呼び出してその命令を可能な限り早期に移動させようとします。regconsttyp(&p->from)は、ソースが定数でないことを確認し、メモリからのロードであることを示唆しています。

pushback関数

static void
pushback(Reg *r0)
{
	Reg *r, *b;
	Prog *p0, *p, t;
	
	b = R;
	p0 = r0->prog;
	for(r=uniqp(r0); r!=R && uniqs(r)!=R; r=uniqp(r)) { // r0から逆方向に命令を辿る
		p = r->prog;
		if(p->as != ANOP) {
			if(!regconsttyp(&p->from) || !regtyp(&p->to)) // ソースが定数でないか、デスティネーションがレジスタでない場合
				break; // 移動を停止
			if(copyu(p, &p0->to, A) || copyu(p0, &p->to, A)) // データ依存性がある場合
				break; // 移動を停止
		}
		if(p->as == ACALL) // CALL命令がある場合
			break; // 移動を停止
		b = r; // 安全な移動先候補を更新
	}
	
	if(b == R) { // 移動できる安全な場所が見つからなかった場合
		// デバッグ出力
		return;
	}

	// デバッグ出力

	t = *r0->prog; // r0の命令を一時保存
	for(r=uniqp(r0);; r=uniqp(r)) { // r0からbまで命令を一つずつ後方にシフト
		p0 = r->link->prog;
		p = r->prog;
		p0->as = p->as;
		p0->lineno = p->lineno;
		p0->from = p->from;
		p0->to = p->to;

		if(r == b)
			break;
	}
	p0 = r->prog; // bの位置にr0の命令を挿入
	p0->as = t.as;
	p0->lineno = t.lineno;
	p0->from = t.from;
	p0->to = t.to;

	// デバッグ出力
}

pushback関数は、与えられたロード命令r0を、その命令が依存するデータや、CALL命令のような副作用を持つ命令を考慮しながら、命令ストリームの可能な限り早期に移動させようとします。uniqp(r0)は、命令リストを逆方向に辿るためのヘルパー関数です。copyu関数は、命令間のデータ依存性をチェックするために使用されます。安全な移動先が見つかった場合、命令を物理的に移動させ、その間の命令を後方にシフトさせます。

subprop関数内の変更

		case ARCLB:
		case ARCLL:
		case ARCLQ:
		case ARCLW:
		case ARCRB:
		case ARCRL:
		case ARCRQ:
		case ARCRW:
		case AROLB:
		case AROLL:
		case AROLQ:
		case AROLW:
		case ARORB:
		case ARORL:
		case ARORQ:
		case ARORW:
		case ASALB:
		case ASALL:
		case ASALQ:
		case ASALW:
		case SARB:
		case SARL:
		case SARQ:
		case SARW:
		case ASHLB:
		case ASHLL:
		case ASHLQ:
		case ASHLW:
		case ASHRB:
		case ASHRL:
		case ASHRQ:
		case ASHRW:
			if(p->from.type == D_CONST) // ソースが定数である場合
				break; // サブプロパゲーションを停止させない

この変更により、シフト/ローテート命令のソースオペランドが定数である場合、subprop関数はレジスタのサブプロパゲーションを停止させなくなりました。これにより、コンパイラはより多くの最適化機会を得ることができます。同様のロジックが除算/乗算命令群にも適用されています。

関連リンク

• Go言語のコンパイラに関するドキュメントやソースコード:
  • golang/go GitHubリポジトリ
  • Go Compiler Internals (古い情報を含む可能性あり)
• x86/x86-64命令セットリファレンス:
  • Intel 64 and IA-32 Architectures Software Developer's Manuals (Intelのウェブサイトで入手可能)
• コンパイラ最適化に関する一般的な情報:
  • Wikipedia: Peephole optimization
  • Wikipedia: Compiler optimization

参考にした情報源リンク

• golang/go GitHubリポジトリ (コミット情報とソースコード)
• Go CL 6203091 (元のGo Code Reviewの変更リスト)
• Intel 64 and IA-32 Architectures Software Developer's Manuals (x86命令セットの詳細確認のため)
• Wikipedia (ピーフホール最適化、CPUパイプラインなどの一般的な概念の確認のため)