[インデックス 13941] ファイルの概要
このコミットは、Goコンパイラのコード生成フェーズにおける最適化に関するものです。具体的には、cmd/6g (32-bit x86アーキテクチャ向けコンパイラ) と cmd/8g (64-bit x86アーキテクチャ向けコンパイラ) において、中間表現 (IR) のノードタイプである OINDREG、ODOT、ODOTPTR のハンドリングを igen 関数に追加することで、生成されるアセンブリコードの効率を向上させています。これにより、特に LEAL (Load Effective Address) / LEAQ 命令の削減と、8g コンパイラにおけるレジスタ割り当ての改善が図られています。
コミット
commit f4e76d5e0222c40e9b98ba19e6628e49f14ecc12
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date: Mon Sep 24 23:07:44 2012 +0200
cmd/6g, cmd/8g: add OINDREG, ODOT, ODOTPTR cases to igen.
Apart from reducing the number of LEAL/LEAQ instructions by about
30%, it gives 8g easier registerization in several cases,
for example in strconv. Performance with 6g is not affected.
Before (386):
src/pkg/strconv/decimal.go:22 TEXT (*decimal).String+0(SB),$240-12
src/pkg/strconv/extfloat.go:540 TEXT (*extFloat).ShortestDecimal+0(SB),$584-20
After (386):
src/pkg/strconv/decimal.go:22 TEXT (*decimal).String+0(SB),$196-12
src/pkg/strconv/extfloat.go:540 TEXT (*extFloat).ShortestDecimal+0(SB),$420-20
Benchmarks with GOARCH=386 (on a Core 2).
benchmark old ns/op new ns/op delta
BenchmarkBinaryTree17 7110191000 7079644000 -0.43%
BenchmarkFannkuch11 7769274000 7766514000 -0.04%
BenchmarkGobDecode 33454820 34755400 +3.89%
BenchmarkGobEncode 11675710 11007050 -5.73%
BenchmarkGzip 2013519000 1593855000 -20.84%
BenchmarkGunzip 253368200 242667600 -4.22%
BenchmarkJSONEncode 152443900 120763400 -20.78%
BenchmarkJSONDecode 304112800 247461800 -18.63%
BenchmarkMandelbrot200 29245520 29240490 -0.02%
BenchmarkParse 8484105 8088660 -4.66%
BenchmarkRevcomp 2695688000 2841263000 +5.40%
BenchmarkTemplate 363759800 277271200 -23.78%
benchmark old ns/op new ns/op delta
BenchmarkAtof64Decimal 127 129 +1.57%
BenchmarkAtof64Float 166 164 -1.20%
BenchmarkAtof64FloatExp 308 300 -2.60%
BenchmarkAtof64Big 584 571 -2.23%
BenchmarkAppendFloatDecimal 440 430 -2.27%
BenchmarkAppendFloat 995 776 -22.01%
BenchmarkAppendFloatExp 897 746 -16.83%
BenchmarkAppendFloatNegExp 900 752 -16.44%
BenchmarkAppendFloatBig 1528 1228 -19.63%
BenchmarkAppendFloat32Integer 443 453 +2.26%
BenchmarkAppendFloat32ExactFraction 812 661 -18.60%
BenchmarkAppendFloat32Point 1002 773 -22.85%
BenchmarkAppendFloat32Exp 858 725 -15.50%
BenchmarkAppendFloat32NegExp 848 728 -14.15%
BenchmarkAppendFloat64Fixed1 447 431 -3.58%
BenchmarkAppendFloat64Fixed2 480 462 -3.75%
BenchmarkAppendFloat64Fixed3 461 457 -0.87%
BenchmarkAppendFloat64Fixed4 509 484 -4.91%
Update #1914.
R=rsc, nigeltao
CC=golang-dev, remy
https://golang.org/cl/6494107
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/f4e76d5e0222c40e9b98ba19e6628e49f14ecc12
元コミット内容
cmd/6g, cmd/8g: add OINDREG, ODOT, ODOTPTR cases to igen.
このコミットは、Goコンパイラの 6g (32-bit x86) および 8g (64-bit x86) バックエンドにおいて、igen 関数に OINDREG、ODOT、ODOTPTR という中間表現ノードの処理ケースを追加するものです。これにより、LEAL/LEAQ 命令の生成を約30%削減し、特に 8g コンパイラでのレジスタ割り当て（registerization）を容易にすることを目的としています。strconv パッケージのベンチマークで顕著な改善が見られ、6g のパフォーマンスには影響がないとされています。
変更の背景
Goコンパイラは、ソースコードを中間表現 (IR) に変換し、その後、ターゲットアーキテクチャ向けのアセンブリコードを生成します。このプロセスにおいて、効率的なアセンブリコードを生成することは、プログラムの実行速度とバイナリサイズに直結します。
以前のGoコンパイラでは、構造体のフィールドアクセスやポインタのデリファレンスといった操作が、アセンブリコードレベルで最適に表現されていないケースがありました。特に、LEAL (Load Effective Address) や LEAQ (Load Effective Address Quadword) 命令は、メモリのアドレス計算を行う際に使用されますが、これが過剰に生成されると、コードの冗長性や実行効率の低下を招く可能性があります。
このコミットの背景には、Goコンパイラが生成するアセンブリコードの品質を向上させ、特に strconv のような数値変換処理において、より効率的なレジスタ利用と命令削減を実現したいという意図があります。これにより、Goプログラム全体のパフォーマンス向上とバイナリサイズの削減が期待されます。
前提知識の解説
このコミットを理解するためには、以下の概念についての知識が必要です。
- Goコンパイラ (gc): Go言語の公式コンパイラは、
gc(Go Compiler) と呼ばれるツールチェーンの一部です。歴史的に、各アーキテクチャ向けのコンパイラは6g(amd64),8g(386),5g(arm) のように命名されていました。このコミットが対象としているのは、6g(amd64) と8g(386) です。 - 中間表現 (IR): コンパイラがソースコードを解析した後、最終的な機械語に変換する前に内部的に使用する抽象的な表現です。Goコンパイラでは、AST (Abstract Syntax Tree) のような構造がIRとして利用されます。
igen関数: Goコンパイラのコード生成フェーズにおいて、中間表現のノードを処理し、アセンブリコードを生成するための重要な関数の一つです。igenは "generate immediate" の略で、ノードが表す値をレジスタまたはメモリに配置するための処理を行います。ONAME: 中間表現におけるノードタイプの一つで、変数や関数名などのシンボルを表します。OINDREG: 中間表現におけるノードタイプの一つで、レジスタを介した間接参照（例:*reg）を表します。ODOT: 中間表現におけるノードタイプの一つで、構造体のフィールドアクセス（例:s.field）を表します。ODOTPTR: 中間表現におけるノードタイプの一つで、ポインタを介した構造体のフィールドアクセス（例:p->fieldまたは Go のp.field）を表します。LEAL(Load Effective Address) /LEAQ(Load Effective Address Quadword): x86/x64アーキテクチャのアセンブリ命令です。通常、メモリのアドレスを計算し、その結果をレジスタに格納するために使用されます。例えば、LEAL (%eax, %ebx, 4), %ecxは%ecx = %eax + %ebx * 4を計算します。この命令は、実際にはメモリにアクセスせず、アドレス計算のみを行うため、算術演算としても利用されることがあります。しかし、単純なレジスタ間接参照で済む場合にLEAL/LEAQが使われると、命令の冗長性やパイプラインの効率低下を招く可能性があります。- レジスタ割り当て (Registerization): コンパイラの最適化の一つで、頻繁にアクセスされる変数をメモリではなくCPUのレジスタに割り当てることで、データアクセスを高速化する技術です。レジスタはメモリよりもはるかに高速にアクセスできます。
strconvパッケージ: Go標準ライブラリの一つで、文字列と数値の相互変換（例:intからstring、floatからstring）を行う機能を提供します。数値変換は計算負荷が高く、コンパイラのコード生成効率がパフォーマンスに大きく影響します。regalloc/regfree: Goコンパイラのレジスタ割り当てに関連する関数で、レジスタの確保と解放を行います。gmove: Goコンパイラのコード生成関数の一つで、あるノードから別のノードへ値を移動させるアセンブリ命令を生成します。ATESTB: x86アセンブリのTEST命令に相当するGoコンパイラの内部命令で、バイト単位のビットテストを行います。ここでは、ポインタがnilでないことを確認するために使用されています。nodintconst: 整数定数ノードを作成するGoコンパイラの内部関数です。
技術的詳細
このコミットの核心は、Goコンパイラの igen 関数が、OINDREG、ODOT、ODOTPTR といった中間表現ノードをより直接的かつ効率的に処理するように拡張された点にあります。
igen 関数の役割
igen 関数は、与えられた中間表現ノード n が表す値を、ターゲットノード a に「即値」として（つまり、レジスタやメモリ参照として）設定することを試みます。これまでの実装では、これらのノードタイプが igen で直接処理されず、より汎用的なコード生成パスにフォールバックしていた可能性があります。その結果、例えば構造体フィールドへのアクセス (ODOT, ODOTPTR) が、まずアドレスを計算し、そのアドレスをレジスタにロードし、さらにそのレジスタをデリファレンスするといった、複数のアセンブリ命令を必要とする非効率なコードを生成していました。特に LEAL/LEAQ 命令が、本来不要なアドレス計算のために頻繁に生成される原因となっていました。
OINDREG の追加
OINDREG は、既にレジスタに格納されている値への間接参照を表します。igen にこのケースを追加することで、コンパイラは、レジスタに格納されたポインタをデリファレンスする際に、余分なアドレス計算命令を生成することなく、直接そのレジスタを間接参照として利用できるようになります。これにより、LEAL/LEAQ 命令の削減に貢献します。
コードでは、n->val.u.reg != D_SP の条件でレジスタの参照カウントをインクリメントしています。これは、igen の呼び出し元が regfree を呼び出してレジスタを解放する必要があることを示しています。D_SP (スタックポインタ) は特殊なレジスタであり、参照カウントの管理から除外されています。
ODOT の追加
ODOT は、構造体のフィールドアクセスを表します。例えば s.field のような場合です。igen に ODOT のケースを追加することで、コンパイラは、構造体 s のベースアドレスにフィールド field のオフセットを直接加算したアドレスを、効率的に表現できるようになります。これにより、LEAL/LEAQ を使わずに、より直接的なメモリアクセス命令を生成することが可能になります。
実装では、まず n->left (構造体 s を表すノード) を igen で処理し、その結果を a に格納します。次に、a->xoffset に n->xoffset (フィールドのオフセット) を加算し、a->type を n->type (フィールドの型) に設定します。これにより、a は構造体フィールドへの直接的な参照を表すようになります。
ODOTPTR の追加
ODOTPTR は、ポインタを介した構造体のフィールドアクセスを表します。例えば p.field (Goでは (*p).field と同じ) のような場合です。このケースは ODOT よりも複雑で、ポインタのデリファレンスとフィールドオフセットの加算の両方を考慮する必要があります。
igen に ODOTPTR のケースを追加することで、コンパイラは以下の最適化を行います。
regalloc(a, types[tptr], res): 結果を格納するためのレジスタaを確保し、ポインタ型 (tptr) を割り当てます。cgen(n->left, a): ポインタpを表すn->leftをcgenで処理し、その値をレジスタaに格納します。if(n->xoffset != 0): フィールドオフセットが0でない場合（つまり、構造体の先頭フィールドでない場合）に、追加のチェックを行います。if(n->left->type->type->width >= unmappedzero): ポインタが指す構造体のサイズがunmappedzero(通常はページサイズ) 以上の場合、ポインタがnilでないことを明示的にチェックします。これは、大きな構造体の場合に、nilポインタをデリファレンスしようとした際に、アクセス違反が発生する前に検出するための安全策です。ATESTB命令 (x86のTEST命令に相当) を使用して、ポインタが指すアドレスの0オフセットにあるバイトをテストします。a->op = OINDREG:aのオペレーションをOINDREGに設定します。これにより、aはレジスタに格納されたポインタの間接参照を表すようになります。a->xoffset += n->xoffset:aのオフセットにフィールドのオフセットを加算します。a->type = n->type:aの型をフィールドの型に設定します。
この一連の処理により、ODOTPTR も LEAL/LEAQ を介さずに、より直接的なレジスタ間接参照とオフセット加算の組み合わせで表現できるようになります。
src/cmd/8g/gsubr.c の変更
ginit、gclean、anyregalloc 関数におけるレジスタのループ範囲が D_AL から D_AX に変更されています。これは、レジスタの定義が変更されたか、またはレジスタ管理のロジックがより正確になったことを示唆しています。D_AL は AX レジスタの下位8ビットを表すため、D_AX に変更することで、より広範なレジスタを対象とするようになった可能性があります。
src/cmd/gc/go.h の変更
go.h はGoコンパイラの共通ヘッダファイルで、中間表現のノード構造体 Node や型構造体 Type の定義が含まれています。このコミットでは、Type 構造体のコメントが更新され、type フィールドと width フィールドの役割がより明確に記述されています。
type:TFIELDの場合は実際の型、TARRAY,TCHAN,TMAP,TPTRxxの場合は要素型。width:TFIELDの場合はオフセット、それ以外の場合は幅。down:TFIELDの場合は次の構造体フィールド、TMAPの場合はキー型。
これらのコメントの更新は、コードの可読性と保守性を向上させるためのものです。
パフォーマンスへの影響
コミットメッセージに記載されているベンチマーク結果は、この最適化が特に GOARCH=386 (32-bit x86) 環境で顕著な効果をもたらしたことを示しています。
LEAL/LEAQ命令の約30%削減: これは、コンパイラが生成するアセンブリコードの命令数を直接的に減らし、バイナリサイズの削減と実行効率の向上に寄与します。8g(amd64) のレジスタ割り当て改善:igenがこれらのノードを直接処理することで、コンパイラはより多くの値をレジスタに保持できるようになり、メモリへのアクセス回数を減らすことができます。これは特にstrconvのような数値演算が頻繁に行われるコードで効果的です。6g(386) のパフォーマンスは影響なし: これは、6gのコード生成パスがこれらのノードタイプを既に効率的に処理していたか、または386アーキテクチャの特性上、この種の最適化がパフォーマンスに与える影響が小さかったことを示唆しています。- ベンチマーク結果:
Gzip,JSONEncode,JSONDecode,Templateなど、I/Oやデータ処理に関連するベンチマークで20%以上の大幅な改善が見られます。これは、これらの処理が文字列操作や構造体アクセスを頻繁に行うため、今回の最適化の恩恵を大きく受けたことを示しています。strconv関連のベンチマーク (BenchmarkAppendFloatなど) でも、同様に20%前後の改善が見られます。これは、strconvが数値と文字列の変換において、構造体やポインタの操作を多用するため、レジスタ割り当ての改善が直接的に効いた結果と考えられます。- 一部のベンチマーク (
BenchmarkGobDecode,BenchmarkRevcomp,BenchmarkAtof64Decimal,BenchmarkAppendFloat32Integer) ではわずかな回帰が見られますが、全体としては大幅なパフォーマンス向上が達成されています。
コアとなるコードの変更箇所
このコミットにおける主要なコード変更は、以下のファイルに集中しています。
-
src/cmd/6g/cgen.c:igen関数にOINDREG,ODOT,ODOTPTRのswitchケースが追加されました。OINDREGでは、レジスタの参照カウントをインクリメントし、ノードをそのまま返します。ODOTでは、左の子ノードをigenで処理し、オフセットを加算します。ODOTPTRでは、レジスタを確保し、左の子ノードをcgenで処理した後、必要に応じてnilチェックを行い、オフセットを加算してOINDREGに変換します。
-
src/cmd/8g/cgen.c:src/cmd/6g/cgen.cと同様に、igen関数にOINDREG,ODOT,ODOTPTRのswitchケースが追加されました。実装は6gのものとほぼ同じです。cgen関数内のisslice(nl->type)ブロックで、n1.op = OINDREG;が削除され、n1.xoffset = Array_cap;がn1.xoffset += Array_cap;に変更されています。これは、スライス容量のアクセス方法がより効率的になったことを示唆しています。
-
src/cmd/8g/gsubr.c:ginit,gclean,anyregalloc関数内のレジスタループの開始インデックスがD_ALからD_AXに変更されました。
-
src/cmd/gc/go.h:Type構造体のtype,width,downフィールドに関するコメントが更新され、その役割がより詳細に記述されました。
コアとなるコードの解説
src/cmd/6g/cgen.c および src/cmd/8g/cgen.c の igen 関数
// 変更前 (例: 6g)
// switch(n->op) {
// case ONAME:
// // ...
// }
// 変更後 (例: 6g)
switch(n->op) {
case ONAME:
// ...
case OINDREG:
// Increase the refcount of the register so that igen's caller
// has to call regfree.
if(n->val.u.reg != D_SP)
reg[n->val.u.reg]++;
*a = *n;
return;
case ODOT:
igen(n->left, a, res);
a->xoffset += n->xoffset;
a->type = n->type;
return;
case ODOTPTR:
regalloc(a, types[tptr], res);
cgen(n->left, a);
if(n->xoffset != 0) {
// explicit check for nil if struct is large enough
// that we might derive too big a pointer.
if(n->left->type->type->width >= unmappedzero) {
n1 = *a;
n1.op = OINDREG;
n1.type = types[TUINT8];
n1.xoffset = 0;
gins(ATESTB, nodintconst(0), &n1);
}
}
a->op = OINDREG;
a->xoffset += n->xoffset;
a->type = n->type;
return;
// ...
}
このコードは、igen 関数が中間表現ノード n を受け取り、そのノードが表す値を a に設定するロジックを示しています。
-
OINDREGケース:n->val.u.reg != D_SPの条件は、スタックポインタ以外のレジスタの場合に、そのレジスタの参照カウントreg[n->val.u.reg]をインクリメントしています。これは、igenがこのレジスタを「使用中」としてマークし、呼び出し元が後でregfreeを呼び出して解放する必要があることをコンパイラに伝えます。*a = *n;は、入力ノードnの情報を出力ノードaにコピーします。これにより、aはnと同じレジスタ間接参照を表すようになります。
-
ODOTケース:igen(n->left, a, res);は、構造体自体を表す左の子ノード (n->left) を再帰的にigenで処理し、その結果をaに格納します。これにより、aは構造体のベースアドレスまたはその参照を表すようになります。a->xoffset += n->xoffset;は、aが表すアドレスに、フィールドのオフセットn->xoffsetを加算します。これにより、aは構造体フィールドの正確なアドレスを指すようになります。a->type = n->type;は、aの型をフィールドの型に設定します。
-
ODOTPTRケース:regalloc(a, types[tptr], res);は、ポインタを格納するためのレジスタaを確保します。cgen(n->left, a);は、ポインタ変数自体を表す左の子ノード (n->left) をcgenで処理し、そのポインタ値をaに格納します。if(n->xoffset != 0) { ... }ブロックは、フィールドオフセットが0でない場合に、ポインタがnilでないことを確認するための安全チェックを行います。if(n->left->type->type->width >= unmappedzero): ポインタが指す構造体のサイズがunmappedzero(通常はメモリページのサイズ、例えば4KB) 以上の場合にチェックを行います。これは、大きな構造体の場合に、nilポインタをデリファレンスしようとした際に、アクセス違反が発生する前に検出するためのものです。n1 = *a; n1.op = OINDREG; n1.type = types[TUINT8]; n1.xoffset = 0;は、aが指すアドレスの0オフセットにあるバイトをテストするためのテンポラリノードn1を作成します。gins(ATESTB, nodintconst(0), &n1);は、ATESTB(x86のTEST命令に相当) 命令を生成し、n1が指すメモリ位置のバイトを0と比較します。これにより、ポインタが有効なメモリを指しているか（nilでないか）を間接的に確認します。
a->op = OINDREG;は、aのオペレーションをOINDREGに設定し、aがレジスタに格納されたポインタの間接参照を表すことを示します。a->xoffset += n->xoffset;は、aが指すアドレスにフィールドのオフセットを加算します。a->type = n->type;は、aの型をフィールドの型に設定します。
これらの変更により、コンパイラは構造体フィールドへのアクセスやポインタのデリファレンスを、より少ない命令で、かつレジスタを効率的に利用してアセンブリコードに変換できるようになりました。
src/cmd/8g/gsubr.c のレジスタループ範囲変更
// 変更前
// for(i=D_AL; i<=D_DI; i++)
// 変更後
for(i=D_AX; i<=D_DI; i++)
D_AL は AX レジスタの下位8ビット (AL) を指し、D_AX は AX レジスタ全体を指します。この変更は、レジスタ管理のループが、より広範なレジスタ（例えば、AX レジスタ全体）を対象とするようになったことを示しています。これは、レジスタ割り当ての正確性を向上させるか、または特定のレジスタの利用方法が変更されたことによるものです。
関連リンク
- Go言語のコンパイラに関するドキュメントやソースコードは、Goの公式リポジトリで確認できます。
- GoのIssueトラッカー: https://github.com/golang/go/issues
- Goのコードレビューシステム (Gerrit): https://go-review.googlesource.com/
参考にした情報源リンク
- Goコンパイラのソースコード (特に
src/cmd/gc/,src/cmd/6g/,src/cmd/8g/ディレクトリ) - Go Issue #1914: https://github.com/golang/go/issues/1914 (コミットメッセージに記載されているIssue)
- Go CL 6494107: https://golang.org/cl/6494107 (コミットメッセージに記載されているコードレビューリンク)
- x86アセンブリ命令セットに関する資料 (LEAL/LEAQ 命令について)
- コンパイラ最適化に関する一般的な書籍やオンラインリソース (レジスタ割り当て、中間表現など)
- Go言語の
strconvパッケージのドキュメント - Go言語のベンチマークに関するドキュメント
- Goコンパイラの歴史とアーキテクチャに関する記事 (例: Russ Cox のブログ記事など)