[インデックス 1219] ファイルの概要
このコミットは、Goコンパイラ 6g のバックエンドにおけるレジスタ割り当て（reg）とピーフホール最適化（peep）に関連する広範な変更を含んでいます。具体的には、以下の8つのファイルが修正されています。
src/cmd/6g/cgen.c: コード生成に関する変更。src/cmd/6g/gen.c: コード生成の汎用部分に関する変更。src/cmd/6g/gsubr.c: コード生成のサブルーチンに関する変更。src/cmd/6g/opt.h: 最適化パスで使用されるデータ構造の定義に関する変更。src/cmd/6g/peep.c: ピーフホール最適化のロジックに関する変更。src/cmd/6g/reg.c: レジスタ割り当てのロジックに関する変更。src/cmd/gc/go.h: Go言語のASTノードやオペレーションの定義に関する変更。src/cmd/gc/walk.c: ASTのウォーク（走査）に関する変更。
これらの変更は、コンパイラのコード生成と最適化の効率を向上させることを目的としています。
コミット
commit e081f25c3e602804fc3bd0780e09bf35d2a098cb
Author: Ken Thompson <ken@golang.org>
Date: Sat Nov 22 17:58:53 2008 -0800
reg and peep
R=r
OCL=19871
CL=19871
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/e081f25c3e602804fc3bd0780e09bf35d2a098cb
元コミット内容
reg and peep
この簡潔なコミットメッセージは、レジスタ割り当て（reg）とピーフホール最適化（peep）に焦点を当てた変更であることを示唆しています。Goコンパイラ 6g は、初期のGo言語のコンパイラであり、Ken Thompson氏によって開発されました。
変更の背景
Go言語の初期のコンパイラである 6g は、コンパイル速度を重視して設計されていました。そのため、GCCやLLVMのような高度な最適化は行われていませんでしたが、基本的な最適化は組み込まれていました。このコミットは、その基本的な最適化、特にレジスタ割り当てとピーフホール最適化の改善を目的としています。
コンパイラにおけるレジスタ割り当ては、プログラムの実行速度に直結する重要な最適化です。頻繁に使用される値をCPUのレジスタに割り当てることで、メモリへのアクセスを最小限に抑え、パフォーマンスを向上させます。ピーフホール最適化は、生成された機械語コードの小さなウィンドウ（ピーフホール）を検査し、より効率的な命令シーケンスに置き換える局所的な最適化手法です。これには、冗長なロード/ストアの削除、複数の操作の結合、デッドコードの排除などが含まれます。
このコミットは、6g コンパイラがより効率的なコードを生成できるように、これらの最適化パスを洗練させるための取り組みの一環と考えられます。特に、インクリメント/デクリメント操作の最適化や、型変換における命令選択の改善などが含まれています。
前提知識の解説
Goコンパイラ 6g
6g は、Go言語の初期のコンパイラツールチェーン gc の一部であり、x86-64アーキテクチャ（AMD64）をターゲットとしていました。6g は、高速なコンパイルを優先する設計思想を持っており、現代の最適化コンパイラに比べると最適化の深度は限定的でした。しかし、それでも基本的なレジスタ割り当てやピーフホール最適化などの手法を取り入れていました。
レジスタ割り当て (Register Allocation)
レジスタ割り当ては、コンパイラの最適化フェーズの一つで、プログラムの変数や中間結果をCPUのレジスタに割り当てるプロセスです。レジスタはメモリよりもはるかに高速にアクセスできるため、適切にレジスタを割り当てることでプログラムの実行速度を大幅に向上させることができます。
6g のようなコンパイラでは、通常、線形スキャンアルゴリズムやグラフ彩色アルゴリズムなどの手法が用いられます。線形スキャンアルゴリズムは、変数の「生存期間」（定義されてから最後に使用されるまでの期間）を分析し、レジスタが利用可能な期間に変数を割り当てます。レジスタが不足した場合は、「スピル」（レジスタからメモリへの退避）が発生します。
ピーフホール最適化 (Peephole Optimization)
ピーフホール最適化は、コンパイラのバックエンドで行われる局所的な最適化手法です。生成されたアセンブリコードや中間表現の小さな連続した命令列（「ピーフホール」と呼ばれるウィンドウ）を検査し、より効率的な等価な命令列に置き換えます。
一般的なピーフホール最適化の例としては、以下のようなものがあります。
- 冗長なロード/ストアの削除: 同じ値をレジスタにロードし、すぐにストアするような冗長な操作を削除します。
- 強度の削減: 複雑な命令をより単純で高速な命令に置き換えます（例:
x * 2をx << 1に）。 - 定数伝播: 定数値を計算時に使用し、実行時の計算を減らします。
- デッドコードの削除: 決して実行されないコードや、その結果が使用されないコードを削除します。
- インクリメント/デクリメントの最適化:
ADD reg, 1をINC regに置き換えるなど。
6g は、コンパイル速度を重視していたため、ピーフホール最適化も限定的な範囲で行われていました。
技術的詳細
このコミットは、6g コンパイラのコード生成と最適化の複数の側面に影響を与えています。
src/cmd/6g/cgen.c の変更
cgen関数内で、OINDREGオペレーションの処理が変更されています。以前はgmove(&n1, res)で直接結果に移動していましたが、n2 = n1; n2.op = OINDREG; n2.type = types[TINT32]; gmove(&n2, &n1);という中間ステップが追加され、その後gmove(&n1, res);で最終的な結果に移動しています。これは、ポインタのデリファレンスと値の移動のセマンティクスをより正確に扱うための変更である可能性があります。
src/cmd/6g/gen.c の変更
if(!debug['N'] || debug['R'] || debug['P']) regopt(ptxt);の行が追加され、デバッグフラグN（最適化なし）が設定されていない場合、またはレジスタ割り当て (R) やピーフホール最適化 (P) のデバッグフラグが設定されている場合にregopt関数（レジスタ最適化）が呼び出されるようになりました。これにより、最適化の適用条件がより柔軟になりました。cgen_asop関数内で、OADD,OSUB,OXOR,OAND,OORなどの二項演算子とリテラル値1の組み合わせに対する特殊な最適化が追加されました。OADDとOSUBの場合、右オペランドがリテラル1であれば、それぞれOINC(インクリメント) およびODEC(デクリメント) 命令に変換されるようになりました。これは、より効率的な単一命令に置き換えるピーフホール最適化の一種です。OXOR,OAND,OORの場合も、右オペランドがリテラルであれば、直接対応する命令を生成するようになりました。
cgen_as関数にiszerフラグが追加され、右辺がゼロである場合の処理が改善されました。特に、nl->addableかつiszerの場合にANOP(No Operation) 命令を挿入することで、後続の最適化パスで利用される可能性のある「使用済み」マークを付ける意図があるようです。
src/cmd/6g/gsubr.c の変更
gmove関数内で、TPTR32からTPTR64への型変換において、AMOVLQZX命令が使用されるようになりました。これは、32ビットポインタを64ビットポインタにゼロ拡張して移動するための命令です。- コメントアウトされていた整数型間の変換に関する
CASE文が、コメントアウトされたままですが、フォーマットが変更されています。 TUINT64からTINT8,TINT16,TINT32への変換にAMOVLQSX(符号拡張移動) が追加されました。TUINT32からTINT64,TUINT64,TPTR64への変換、およびTPTR32からTINT64,TUINT64,TPTR64への変換にAMOVLQZX(ゼロ拡張移動) が追加されました。これにより、異なるサイズの整数型やポインタ型間の変換がより正確かつ効率的に行われるようになりました。optoas関数に、OINC(インクリメント) とODEC(デクリメント) オペレーションに対する新しい命令マッピングが追加されました。TINT8/TUINT8にはAINCB/ADECB(バイト単位)TINT16/TUINT16にはAINCW/ADECW(ワード単位)TINT32/TUINT32/TPTR32にはAINCL/ADECL(ロングワード単位)TINT64/TUINT64/TPTR64にはAINCQ/ADECQ(クワッドワード単位) これらの命令は、CPUが提供する単一のインクリメント/デクリメント命令を利用することで、ADD reg, 1やSUB reg, 1といった2命令を1命令に削減し、コードサイズと実行速度を改善します。
src/cmd/6g/opt.h の変更
Reg構造体からmagic,pc,log5フィールドが削除され、loopフィールドがint32からuint16に変更され、refsetフィールドがuchar型で追加されました。これは、レジスタ割り当ての内部データ構造の整理と効率化を示しています。EXTERN Bits ovar;が追加され、出力引数（戻り値）の変数を追跡するためのビットセットが導入されました。ostats構造体が追加され、コンパイラの最適化に関する統計情報（ncvtreg,nspill,nreload,ndelmov,nvar,naddr）を収集できるようになりました。これは、最適化の有効性を評価し、さらなる改善のためのデータを提供するために重要です。dumpitとnoreturn関数のプロトタイプが、staticから通常の関数に変更されました。
src/cmd/6g/peep.c の変更
peep関数内で、Prog構造体のregフィールドがr2->prog = p; p->reg = r2;のように設定されるようになりました。これにより、プログラム命令とレジスタ情報が相互に参照できるようになり、最適化パスでのデータアクセスが容易になります。- デバッグ出力
dumpit("loop1", firstr);が追加され、ピーフホール最適化のループ開始時の状態を可視化できるようになりました。 AADDQ,AADDL,ASUBQ,ASUBL命令に対するピーフホール最適化が改善されました。オフセットが-1または1の場合、それぞれADECQ/ADECL/AINCQ/AINCLなどの単一命令に変換されるロジックがより堅牢になりました。これは、gen.cでのOINC/ODECの生成と連携して、より効率的なコードを生成します。excise関数内で、削除される命令のデバッグ出力が追加され、ostats.ndelmov++で削除された移動命令の統計が記録されるようになりました。
src/cmd/6g/reg.c の変更
MAGICマクロが削除されました。setoutvar関数が追加されました。この関数は、関数の出力引数（戻り値）を走査し、それらの変数をovarビットセットに記録します。これは、レジスタ割り当てにおいて、戻り値がレジスタに割り当てられるべきか、あるいはメモリにスピルされるべきかを判断する際に重要な情報となります。regopt関数内で、ovarビットセットの初期化が追加されました。regoptのパス1において、AINCB,AINCL,AINCQ,AINCW,ADECB,ADECL,ADECQ,ADECWといったインクリメント/デクリメント命令が、レジスタの読み書き操作として適切に処理されるようになりました。regoptの各パス（パス1、パス2、パス2.5、パス3、パス4、パス6）の開始時に、デバッグフラグRとvが設定されている場合にdumpit関数が呼び出され、レジスタ割り当ての各段階での状態を詳細にトレースできるようになりました。- 「used and not set」および「set and not used」の警告ロジックが変更され、
r->refsetフラグが導入されました。これにより、警告が一度だけ表示されるようになり、冗長な出力が抑制されます。また、デバッグフラグwが追加され、警告の表示を制御できるようになりました。 nregionがNRGNを超えた場合のfatalエラーが、デバッグモードでは警告に変わるようになりました。peep()関数の呼び出し条件がif(!debug['R'] || debug['P'])に変更されました。これは、レジスタ割り当てのデバッグ (-R) が有効な場合はピーフホール最適化 (-P) をスキップしないことを意味します。- 最適化後の不要な
ANOP命令の削除ロジックが改善され、分岐命令のターゲットも適切に更新されるようになりました。 regopt関数の最後に、ostats構造体に記録された最適化統計情報が出力されるようになりました。これにより、レジスタ割り当てやピーフホール最適化の効果を数値的に評価できるようになります。addmove関数内で、AMOVSD(double-precision float move) がTFLOAT64型の移動に使用されるようになりました。また、ostats.nspill++でスピル操作の統計が記録されるようになりました。mkvar関数内で、レジスタ使用ビットマップr->reguの更新がr != Rの条件付きになりました。また、ostats.naddr++とostats.nvar++でアドレスと変数の統計が記録されるようになりました。prop関数内で、ARET(return) 命令の処理が変更され、cal.b[z]にovar.b[z](出力変数) が含まれるようになりました。これにより、戻り値がレジスタ割り当ての考慮対象となることが明確になります。paint1関数内で、デバッグ出力が削除され、より簡潔になりました。paint3関数内で、デバッグ出力がdebug['R'] && debug['v']の条件付きになり、より詳細なデバッグ情報が必要な場合にのみ表示されるようになりました。また、addreg関数呼び出し後にostats.ncvtreg++でレジスタ変換の統計が記録されるようになりました。BtoR関数で、ビットマスクが0xffffLから0x3fffLに変更されました。これは、レジスタのビット表現に関する変更であり、おそらく特定のレジスタ（R14, R15）を除外するためです。dumpitとnoreturn関数の定義がstaticから通常の関数に変更されました。
src/cmd/gc/go.h の変更
enumにOINCとODECという新しいオペレーションが追加されました。これらは、インクリメントとデクリメントを表すプレースホルダーであり、コンパイラのフロントエンドで認識され、バックエンドで対応する機械語命令に変換されます。
src/cmd/gc/walk.c の変更
nottopラベルの処理が変更され、yyerrorのメッセージがより詳細になりました。topの値に応じて、操作がステートメントコンテキスト、代入コンテキスト、または式コンテキストで許可されていないことを示すエラーメッセージが表示されるようになりました。これにより、コンパイラのエラー報告が改善されます。symlist[1] = pkglookup("panicl", "sys");が追加され、noreturn関数がpaniclも非リターン関数として認識するようになりました。
コアとなるコードの変更箇所
このコミットのコアとなる変更は、以下のファイルと機能に集約されます。
src/cmd/6g/gen.cおよびsrc/cmd/6g/gsubr.cにおけるOINC/ODECの導入と最適化:gen.cで、+1や-1のリテラルを含む加減算をOINC/ODECオペレーションに変換するロジックが追加されました。gsubr.cのoptoas関数で、これらのOINC/ODECオペレーションが、ターゲットアーキテクチャの効率的な単一命令（AINCB,AINCW,AINCL,AINCQ,ADECB,ADECW,ADECL,ADECQ）にマッピングされるようになりました。
src/cmd/6g/reg.cにおけるレジスタ割り当ての改善と統計情報の導入:setoutvar関数の追加により、関数の戻り値がレジスタ割り当ての考慮対象となるようになりました。ostats構造体の導入により、レジスタ割り当てや最適化の各段階での統計情報が収集されるようになり、コンパイラのパフォーマンス分析と改善に役立つようになりました。- レジスタ割り当ての各パスにおける詳細なデバッグ出力が追加され、トレースが容易になりました。
src/cmd/6g/peep.cにおけるピーフホール最適化の強化:AADDQ/AADDL/ASUBQ/ASUBL命令に対するINC/DEC命令への変換ロジックが改善され、より多くのケースで効率的な命令が生成されるようになりました。- 最適化によって削除された命令の統計が
ostats.ndelmovで追跡されるようになりました。
コアとなるコードの解説
インクリメント/デクリメントの最適化 (gen.c, gsubr.c)
Goコンパイラ 6g は、x = x + 1 や x = x - 1 のような一般的な操作を、より効率的なCPU命令に変換するようになりました。
src/cmd/6g/gen.c の cgen_asop 関数では、以下のようなロジックが追加されています。
if(nl->addable && nr->op == OLITERAL)
switch(n->etype) {
case OADD:
if(!isint[nl->type->etype])
goto com;
if(mpgetfix(nr->val.u.xval) != 1)
goto com;
gins(optoas(OINC, nl->type), N, nl); // OINC に変換
goto ret;
case OSUB:
if(!isint[nl->type->etype])
goto com;
if(mpgetfix(nr->val.u.xval) != 1)
goto com;
gins(optoas(ODEC, nl->type), N, nl); // ODEC に変換
goto ret;
// ...
}
このコードは、左辺がアドレス可能 (nl->addable) で、右辺がリテラル (nr->op == OLITERAL) の場合に、加算 (OADD) や減算 (OSUB) のオペレーションをチェックします。もし右辺のリテラル値が 1 であれば、それぞれ OINC または ODEC という新しい内部オペレーションに変換します。
次に、src/cmd/6g/gsubr.c の optoas 関数では、これらの OINC/ODEC オペレーションが実際の機械語命令にマッピングされます。
case CASE(OINC, TINT8):
case CASE(OINC, TUINT8):
a = AINCB; // バイト単位のインクリメント
break;
// ... 他の型に対する AINCW, AINCL, AINCQ
case CASE(ODEC, TINT8):
case CASE(ODEC, TUINT8):
a = ADECB; // バイト単位のデクリメント
break;
// ... 他の型に対する ADECW, ADECL, ADECQ
これにより、例えば x = x + 1 というGoのコードは、コンパイル後に INCQ x (64ビット整数) のような単一のCPU命令に変換される可能性が高まります。これは、ADDQ $1, x のような2命令よりも効率的です。
レジスタ割り当ての統計情報 (reg.c, opt.h)
src/cmd/6g/opt.h で定義された ostats 構造体は、コンパイラの最適化パスの効率を測定するための重要なツールです。
struct
{
int32 ncvtreg; // レジスタ変換の回数
int32 nspill; // レジスタスピルの回数
int32 nreload; // レジスタリロードの回数
int32 ndelmov; // 削除された移動命令の回数
int32 nvar; // 変数の処理回数
int32 naddr; // アドレスの処理回数
} ostats;
これらのカウンタは、src/cmd/6g/reg.c や src/cmd/6g/peep.c の様々な場所でインクリメントされます。例えば、addmove 関数（レジスタからメモリへのスピルを生成する可能性のある関数）では ostats.nspill++ が、excise 関数（不要な命令を削除する関数）では ostats.ndelmov++ が呼び出されます。
reg.c の regopt 関数の最後で、これらの統計情報がデバッグ出力として表示されます。
if(debug['R']) {
if(ostats.ncvtreg || ostats.nspill || ostats.nreload || ostats.ndelmov || ostats.nvar || ostats.naddr || 0)
print("\nstats\n");
// ... 各統計情報の出力
memset(&ostats, 0, sizeof(ostats));
}
この統計情報は、コンパイラの開発者がレジスタ割り当てやピーフホール最適化のボトルネックを特定し、さらなる改善のための指針を得るのに役立ちます。例えば、nspill の値が高い場合、レジスタが不足している可能性があり、より洗練されたレジスタ割り当てアルゴリズムが必要であることを示唆します。
戻り値のレジスタ割り当てへの考慮 (reg.c)
src/cmd/6g/reg.c に追加された setoutvar 関数と、prop 関数における ARET (return) 命令の処理の変更は、関数の戻り値がレジスタ割り当ての対象となることを保証します。
setoutvar 関数は、関数の出力引数（戻り値）を走査し、それらの変数をグローバルな ovar ビットセットに記録します。
void
setoutvar(void)
{
// ...
t = structfirst(&save, getoutarg(curfn->type));
while(t != T) {
// ...
for(z=0; z<BITS; z++)
ovar.b[z] |= bit.b[z]; // ovar に出力変数を追加
t = structnext(&save);
}
}
そして、prop 関数（レジスタ割り当てのデータフロー解析の一部）では、ARET 命令が処理される際に、cal (call-clobbered registers) ビットセットに ovar が含まれるようになりました。
case ARET:
for(z=0; z<BITS; z++) {
cal.b[z] = externs.b[z] | ovar.b[z]; // 戻り値も cal に含める
ref.b[z] = 0;
}
break;
これにより、レジスタ割り当てアルゴリズムは、関数の戻り値が呼び出し元に渡される際にレジスタに保持されるべきであることを認識し、不必要なメモリへのスピルを避けることができます。
関連リンク
- Go言語の公式ドキュメント: https://go.dev/
- Goコンパイラのソースコード: https://github.com/golang/go
参考にした情報源リンク
- GitHubコミットページ: https://github.com/golang/go/commit/e081f25c3e602804fc3bd0780e09bf35d2a098cb
- Web検索結果: "Go compiler 6g register allocation peephole optimization" (Google Search)
- redhat.com (https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQEtbzE9h94vXgRZlCJSWD9XNy11H_lqimXVhYgtN27TNzBgBYXHrcI2-zWFzQRCGwogdvxO486BM1Q8efAsziUvaUqeyQ506LGKthSRsZVpmRT-fo_xFYBGfLNwdFkt4iK4hKT5Lo7K7e5WFm-f55xEYlsJg8An0f4sb4Yty7fSYuP6NzeHMUD12wMD)
- github.com (https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQE0BEKtKUWKsI8Sug5kr1-eNeAjc2PrSf5T4euOqzmKlE49JQa_Es57_UrZS6x7po6gzAwmScLEMjBXVn_c8s8gwRYyNtTLYnNKERFfSdpPJCKi_kofXbgNFl2-6ZkEXneYHo1Ylqjdo9bBM8f3A26CaI8ohFwh0A==)
- wikipedia.org (https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQFtkK2KCP3B6eU_flYVh9W9O36GjH81YNiTyQRptLSM7GyFGcAho24NBGAVlTMtr4OWUYGh0p-_CSGjYH5wmtk7gOdiZfZVkmNb4wvZeW98Zsn1whG9A1DvBxTJo_wljKJdIUM3IpjOuTb0gwot)
- medium.com (https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQHEM2KZ_Z9YZlkTRQK4o6u5QEZxHdXnHX9_S-yk5isaMjcqfLJcud_CxdYOVMebZrweeF0Mnwg9Sj-45fdfFTpnwl1l3_JQ8ndiXc7B6Uukkmkwyzdx5E38TO4w1SmkVQr0a_KQowiwHxNK-Z22s0B5n29vCEyBOfBWnbLmISsDwbyaGr2kyLEujQjo)
- collegenote.net (https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQFIvjcnhtMTltr-sHaRQ-ovrDOlZP0ugFCimm93sCYqpE6t0ATQ2PJvFN1d_YKDtvR0SbKiCffKmHebCrjLb7KDJF7zZOjbr3u-ruvsAw9bFvFWhAa2a7jTl7FswSZvx27-SxMDL_T9yl-3fbRLA3Gw7k4JBTw28ZA-yOBcYViLmbuf9U3SeC48e-bcCX87)
- h-da.de (https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQEGiJjhtfhFp2RCahMSNTTkTIX6TkMZ6xVyfpw9CQxn2qaSKhngVHcWYBses3KaV4QY8sQ3xQ_RxvJdhpiPbfsHXA8xACcw_2C8q3FuXtuXV8svVOzuTdNxc4HQf6uCg_cVjSbsf8I2Vatf78ee09sgbzOdb4YDKvPQiIg0M3TqK9T8-kSy2dXQjy6iUkPoEGUsadUprGICaxpaIg==)
- ycombinator.com (https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQERlDlM2zVNxAuYIopLX12fSrldfCLysawKawG-oH95qUZqdwdFje9VZL5qotz7ENyJUtCDpc4scG0AbrqIQ6IKkus85Afx4DzCNa_0g3yXfYWmX18eTKiLvJEt1iQFgoIztS1RPElk)