[インデックス 14920] ファイルの概要
このコミットは、Goコンパイラのcmd/6c（x86-64アーキテクチャ向けのC言語バックエンド）およびcmd/6g（x86-64アーキテクチャ向けのGo言語バックエンド）における、シフトおよびローテート命令のピーホール最適化を改善するものです。具体的には、連続するシフト操作において、レジスタ間の不要なデータ移動を削減し、生成されるアセンブリコードの効率を向上させます。
コミット
commit 41ec481a53b2592111e1278670b3361ef98c352d
Author: Matthew Dempsky <mdempsky@google.com>
Date: Fri Jan 18 16:33:25 2013 -0500
cmd/6c: Improve peep hole optimization of rotate and shift instructions.
Update #4629.
$ cat shift2.c
unsigned int
shift(unsigned int x, unsigned int y)
{
x = (x << 3);
y = (y << 5);
x = (x << 7);
y = (y << 9);
return x ^ y;
}
## BEFORE
$ go tool 6c -S shift2.c
(shift2.c:2) TEXT shift+0(SB),$0-8
(shift2.c:4) MOVL x+0(FP),!!AX
(shift2.c:4) SALL $3,!!AX
(shift2.c:4) MOVL AX,!!DX
(shift2.c:5) MOVL y+4(FP),!!AX
(shift2.c:5) SALL $5,!!AX
(shift2.c:5) MOVL AX,!!CX
(shift2.c:6) MOVL DX,!!AX
(shift2.c:6) SALL $7,!!AX
(shift2.c:6) MOVL AX,!!DX
(shift2.c:7) MOVL CX,!!AX
(shift2.c:7) SALL $9,!!AX
(shift2.c:7) MOVL AX,!!CX
(shift2.c:8) MOVL DX,!!AX
(shift2.c:8) XORL CX,!!AX
(shift2.c:8) RET ,!!
(shift2.c:8) RET ,!!
(shift2.c:8) END ,!!
## AFTER
$ go tool 6c -S shift2.c
(shift2.c:2) TEXT shift+0(SB),$0-8
(shift2.c:4) MOVL x+0(FP),!!AX
(shift2.c:4) SALL $3,!!AX
(shift2.c:5) MOVL y+4(FP),!!CX
(shift2.c:5) SALL $5,!!CX
(shift2.c:6) SALL $7,!!AX
(shift2.c:7) SALL $9,!!CX
(shift2.c:8) XORL CX,!!AX
(shift2.c:8) RET ,!!
(shift2.c:8) RET ,!!
(shift2.c:8) END ,!!
R=rsc, minux.ma, dave, nigeltao
CC=golang-dev
https://golang.org/cl/7066055
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/41ec481a53b2592111e1278670b3361ef98c352d
元コミット内容
このコミットは、Goコンパイラのcmd/6cにおけるローテートおよびシフト命令のピーホール最適化を改善することを目的としています。具体的には、連続するシフト操作において、中間結果を一時的に別のレジスタに退避・復元するMOVL命令の冗長な使用を排除し、より効率的なアセンブリコードを生成するように変更されました。コミットメッセージには、shift2.cというC言語のサンプルコードと、そのコンパイル結果（アセンブリコード）が変更前後でどのように変化したかが示されており、最適化の効果が明確に示されています。
変更の背景
コンパイラが生成するアセンブリコードの効率は、プログラムの実行速度に直結します。特に、頻繁に実行されるビット演算（シフトやローテート）は、その最適化が重要です。Goコンパイラの既存のピーホール最適化では、連続するシフト操作において、レジスタの再利用が不十分な場合がありました。具体的には、ある変数のシフト操作を行った後、別の変数のシフト操作を行う際に、最初の変数の結果を一時的にメモリや別のレジスタに退避させ、再度使用する際にレジスタに戻すといった冗長なMOVL（Move Long）命令が挿入されることがありました。
この冗長なMOVL命令は、CPUサイクルを無駄にし、キャッシュの効率を低下させる可能性があります。コミットメッセージに記載されているshift2.cの例では、xとyという2つの変数がそれぞれ複数回シフトされるシナリオで、この非効率性が顕著に現れていました。この問題を解決し、よりコンパクトで高速なコードを生成するために、ピーホール最適化のロジックが見直されました。
前提知識の解説
ピーホール最適化 (Peephole Optimization)
ピーホール最適化は、コンパイラの最適化手法の一つで、生成されたアセンブリコード（または中間コード）の小さな連続した命令列（「ピーホール」と呼ばれる小さな窓）を検査し、より効率的な命令列に置き換える手法です。これは、局所的な最適化であり、通常はコンパイラのバックエンド（コード生成フェーズ）の最終段階で行われます。
ピーホール最適化の一般的な例としては、以下のようなものがあります。
- 冗長なロード/ストアの削除:
MOV A, R1の後にMOV R1, Aのような命令があれば、後者を削除する。 - 不要なジャンプの削除:
JMP L1の後にL1: JMP L2のような命令があれば、JMP L2に直接書き換える。 - 代数的な簡略化:
ADD R1, 0を削除する。 - 命令の置き換え:
MUL R1, 2をSHL R1, 1に置き換える（シフトの方が高速な場合）。 - レジスタの再利用: 今回のコミットで改善されたように、中間結果をレジスタに保持し続けることで、メモリへの退避・復元を避ける。
Goコンパイラ (cmd/6c, cmd/6g)
Go言語のコンパイラは、複数のアーキテクチャをサポートしており、それぞれのアーキテクチャに対応するバックエンドが存在します。
cmd/6c: x86-64アーキテクチャ向けのC言語バックエンド。Go 1.5以前のGoコンパイラは、GoコードをCコードに変換し、その後Cコンパイラ（6cなど）でアセンブリコードを生成していました。cmd/6g: x86-64アーキテクチャ向けのGo言語バックエンド。Go 1.5以降では、Goコンパイラ自体がGo言語で書かれ、直接アセンブリコードを生成するようになりました。このコミットが行われた2013年時点では、まだC言語バックエンドが主要な役割を担っていた時期ですが、6gにも同様の最適化が適用されていることから、両方のコンパイラで共通の最適化ロジックが使用されていることが示唆されます。
x86-64アセンブリ命令
コミットメッセージに登場する主なx86-64アセンブリ命令は以下の通りです。
MOVL: Move Long。32ビットの値を移動します。レジスタからレジスタ、メモリからレジスタ、レジスタからメモリなど、様々なオペランド間でデータをコピーするために使用されます。SALL: Shift Arithmetic Left Long。32ビットの値を算術左シフトします。指定されたビット数だけ左にシフトし、右から0を埋めます。これは、2のべき乗を掛ける操作に相当します。XORL: Exclusive OR Long。32ビットの値に対してビットごとの排他的論理和（XOR）演算を行います。TEXT: 関数の開始を宣言します。RET: 関数からのリターン。END: 関数の終了を宣言します。AX,CX,DX: x86-64アーキテクチャにおける汎用レジスタの一部です。AX(Accumulator Register): 算術演算の主要なレジスタとしてよく使われます。CX(Count Register): ループカウンタやシフト/ローテート命令のシフト量としてよく使われます。DX(Data Register): 算術演算の補助レジスタとして使われたり、AXと組み合わせて64ビット演算に使われたりします。
FP: Frame Pointer。スタックフレームのベースアドレスを指すレジスタです。x+0(FP)やy+4(FP)は、スタックフレーム上の引数xやyへのアクセスを示します。
技術的詳細
このコミットの技術的な核心は、Goコンパイラのピーホール最適化器（peep.cファイルに実装されている）が、連続するシフトおよびローテート命令を処理する方法の改善にあります。
変更前のアセンブリコードでは、x = (x << 3); の後に y = (y << 5); が続く場合、xの計算結果がAXレジスタに格納された後、MOVL AX,!!DXによってDXレジスタに退避され、その後yの計算のためにAXが再利用されていました。そして、xの次のシフト操作 (x = (x << 7);) の際には、MOVL DX,!!AXによってDXからAXに値が戻されていました。このようなレジスタ間の不要な移動は、パイプラインストールや余分な命令実行を引き起こし、パフォーマンスを低下させます。
変更後の最適化では、コンパイラはxとyの計算を異なるレジスタ（例: xはAX、yはCX）で並行して進めることができるようになります。これにより、中間結果を退避・復元するためのMOVL命令が不要となり、より少ない命令数で同じ処理を実現できます。
src/cmd/6c/peep.cおよびsrc/cmd/6g/peep.cの変更点を見ると、subprop関数内のswitch文で、AROLB（Rotate Left Byte）からASHRW（Shift Arithmetic Right Word）までのシフト/ローテート命令のケースに、以下の条件が追加されています。
if(p->from.type == D_CONST)
break;
goto giveup;
これは、シフト/ローテートの量が定数である場合（例: x << 3 の 3）、最適化を続行（break）し、そうでない場合（例: x << y の yが変数）、この特定のピーホール最適化を諦める（goto giveup）ことを意味します。定数シフトの場合にのみこの最適化を適用するのは、定数シフトはコンパイル時にシフト量が確定しているため、より単純なパターンマッチングとレジスタ割り当ての最適化が可能だからです。変数をシフト量とする場合は、実行時までシフト量が不明なため、より複雑なコード生成が必要となり、このピーホール最適化の範囲外となるか、別の最適化パスで処理されるべきと判断されたと考えられます。
また、ADIVB（Divide Byte）やAMULW（Multiply Word）などの除算・乗算命令のケースが、シフト/ローテート命令のケースの後に移動されています。これは、命令の処理順序や、giveupラベルへのジャンプのロジックを整理するためと考えられます。
コアとなるコードの変更箇所
変更は主にGoコンパイラのピーホール最適化を担当するファイルで行われています。
src/cmd/6c/peep.csrc/cmd/6g/peep.c
これらのファイル内のsubprop関数が変更されています。
src/cmd/6c/peep.c の変更点:
--- a/src/cmd/6c/peep.c
+++ b/src/cmd/6c/peep.c
@@ -330,20 +330,7 @@ subprop(Reg *r0)
case AIMULW:
if(p->to.type != D_NONE)
break;
-
- case ADIVB:
- case ADIVL:
- case ADIVQ:
- case ADIVW:
- case AIDIVB:
- case AIDIVL:
- case AIDIVQ:
- case AIDIVW:
- case AIMULB:
- case AMULB:
- case AMULL:
- case AMULQ:
- case AMULW:
+ goto giveup;
case AROLB:
case AROLL:
@@ -369,6 +356,23 @@ subprop(Reg *r0)
case ASHRL:
case ASHRQ:
case ASHRW:
+ if(p->from.type == D_CONST)
+ break;
+ goto giveup;
+
+ case ADIVB:
+ case ADIVL:
+ case ADIVQ:
+ case ADIVW:
+ case AIDIVB:
+ case AIDIVL:
+ case AIDIVQ:
+ case AIDIVW:
+ case AIMULB:
+ case AMULB:
+ case AMULL:
+ case AMULQ:
+ case AMULW:
case AREP:
case AREPN:
@@ -384,6 +388,7 @@ subprop(Reg *r0)
case AMOVSL:
case AMOVSQ:
case AMOVQL:
+ giveup:
return 0;
case AMOVL:
src/cmd/6g/peep.c の変更点:
--- a/src/cmd/6g/peep.c
+++ b/src/cmd/6g/peep.c
@@ -664,6 +664,7 @@ subprop(Reg *r0)
case AIMULW:
if(p->to.type != D_NONE)
break;
+ goto giveup;
case ARCLB:
case ARCLL:
@@ -699,6 +700,7 @@ subprop(Reg *r0)
case ASHRW:
if(p->from.type == D_CONST)
break;
+ goto giveup;
case ADIVB:
case ADIVL:
@@ -727,6 +729,7 @@ subprop(Reg *r0)
case AMOVSB:
case AMOVSL:
case AMOVSQ:
+ giveup:
if(debug['P'] && debug['v'])
print("\tfound %P; return 0\n", p);
return 0;
コアとなるコードの解説
peep.c内のsubprop関数は、ピーホール最適化の主要なロジックを含んでいます。この関数は、命令列を走査し、最適化の機会を探します。
変更の核心は、switch文内の命令タイプごとの処理ロジックにあります。
-
除算・乗算命令の移動:
src/cmd/6c/peep.cでは、以前はAIMULWの後にADIVBからAMULWまでの除算・乗算命令が連続して記述され、これらがgoto giveup;にフォールスルーしていました。- 今回の変更で、これらの除算・乗算命令のブロックが、シフト・ローテート命令のブロック（
AROLBからASHRW）の後に移動されました。これにより、コードの構造が整理され、特定の命令グループに対する最適化の適用範囲が明確になります。
-
シフト・ローテート命令の条件付き最適化:
AROLBからASHRWまでのシフト・ローテート命令のケースに、if(p->from.type == D_CONST) break;という条件が追加されました。pは現在の命令を表すポインタです。p->from.typeは命令のソースオペランドのタイプを示します。D_CONSTは、ソースオペランドが定数であることを意味します。
- この条件は、「もしシフトまたはローテートの量が定数であれば、この命令に対するピーホール最適化を続行する（
breakして次の最適化ルールを適用する可能性がある）」ことを意味します。 - もしシフト量が定数でなければ、
goto giveup;が実行されます。giveupラベルは、現在の命令に対するピーホール最適化を諦め、関数から0を返して、これ以上の最適化を行わないことを示します。これは、変数をシフト量とする動的なシフト操作は、このピーホール最適化の対象外であるか、より複雑な分析が必要なため、別の最適化パスに任せるという判断です。
この変更により、コンパイラは定数シフト操作において、より積極的にレジスタの再利用を試み、中間的なMOVL命令を削減できるようになりました。コミットメッセージの例で示されているように、xとyの連続するシフト操作が、それぞれ異なるレジスタ（AXとCX）で処理されるようになり、冗長なレジスタ間のデータ移動が排除されています。
関連リンク
- Go言語のIssueトラッカー: https://github.com/golang/go/issues/4629 (コミットメッセージで参照されているIssue)
- Go言語のコードレビューシステム (Gerrit): https://golang.org/cl/7066055 (このコミットの変更リスト)
参考にした情報源リンク
- Go言語のソースコード (特に
src/cmd/6c/peep.cとsrc/cmd/6g/peep.c): https://github.com/golang/go - ピーホール最適化に関する一般的な情報 (例: Wikipedia, コンパイラ設計の教科書)
- x86-64アセンブリ命令セットリファレンス
- Goコンパイラの歴史とアーキテクチャに関する情報 (Go 1.5以前と以降のコンパイラの変遷など)
- Go言語の公式ドキュメントやブログ記事 (コンパイラの内部動作に関するもの)
- Go言語のIssue #4629の議論内容 (もし公開されていれば、問題の背景をより深く理解できる)
- Go言語のGerrit変更リスト 7066055のコメントやレビュー内容 (変更の意図や議論の詳細を理解できる)