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

このコミットは、Goコンパイラ（cmd/6gおよびcmd/8g）における境界チェック（bounds check）のコード生成方法を最適化し、panicindex関数の呼び出しをインラインからアウトオブラインに移動させる変更です。これにより、CPUのキャッシュ効率が向上し、特にタイトなループにおけるパフォーマンスが改善されます。

コミット

commit fefae6eed1df88397b4a53ed932e3cf3b32345ad
Author: Russ Cox <rsc@golang.org>
Date:   Tue May 29 12:09:27 2012 -0400

    cmd/6g, cmd/8g: move panicindex calls out of line
    
    The old code generated for a bounds check was
                    CMP
                    JLT ok
                    CALL panicindex
            ok:
                    ...
    
    The new code is (once the linker finishes with it):
                    CMP
                    JGE panic
                    ...
            panic:
                    CALL panicindex
    
    which moves the calls out of line, putting more useful
    code in each cache line.  This matters especially in tight
    loops, such as in Fannkuch.  The benefit is more modest
    elsewhere, but real.
    
    From test/bench/go1, amd64:
    
    benchmark                old ns/op    new ns/op    delta
    BenchmarkBinaryTree17   6096092000   6088808000   -0.12%
    BenchmarkFannkuch11     6151404000   4020463000  -34.64%
    BenchmarkGobDecode        28990050     28894630   -0.33%
    BenchmarkGobEncode        12406310     12136730   -2.17%
    BenchmarkGzip               179923       179903   -0.01%
    BenchmarkGunzip              11219        11130   -0.79%
    BenchmarkJSONEncode       86429350     86515900   +0.10%
    BenchmarkJSONDecode      334593800    315728400   -5.64%
    BenchmarkRevcomp25M     1219763000   1180767000   -3.20%
    BenchmarkTemplate        492947600    483646800   -1.89%
    
    And 386:
    
    benchmark                old ns/op    new ns/op    delta
    BenchmarkBinaryTree17   6354902000   6243000000   -1.76%
    BenchmarkFannkuch11     8043769000   7326965000   -8.91%
    BenchmarkGobDecode        19010800     18941230   -0.37%
    BenchmarkGobEncode        14077500     13792460   -2.02%
    BenchmarkGzip               194087       193619   -0.24%
    BenchmarkGunzip              12495        12457   -0.30%
    BenchmarkJSONEncode      125636400    125451400   -0.15%
    BenchmarkJSONDecode      696648600    685032800   -1.67%
    BenchmarkRevcomp25M     2058088000   2052545000   -0.27%
    BenchmarkTemplate        602140000    589876800   -2.04%
    
    To implement this, two new instruction forms:
    
            JLT target      // same as always
            JLT $0, target  // branch expected not taken
            JLT $1, target  // branch expected taken
    
    The linker could also emit the prediction prefixes, but it
    does not: expected taken branches are reversed so that the
    expected case is not taken (as in example above), and
    the default expectaton for such a jump is not taken
    already.
    
    R=golang-dev, gri, r, dave
    CC=golang-dev
    https://golang.org/cl/6248049

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

https://github.com/golang/go/commit/fefae6eed1df88397b4a53ed932e3cf3b32345ad

元コミット内容

Go言語のコンパイラ（cmd/6gはamd64用、cmd/8gは386用）において、配列の境界チェック（bounds check）時に発生するpanicindex関数の呼び出しに関するコード生成ロジックが変更されました。

以前のコード生成では、境界チェックは以下のようなアセンブリコードを生成していました。

CMP         ; 比較命令
JLT ok      ; 境界内であればokラベルにジャンプ
CALL panicindex ; 境界外であればpanicindexを呼び出し
ok:         ; 境界内の場合の処理
    ...

この方式では、panicindexの呼び出しが境界チェックの直後にインラインで配置されていました。

変更の背景

この変更の主な背景は、CPUのキャッシュ効率と分岐予測の最適化によるパフォーマンス向上です。

1. キャッシュ効率の改善:

   • CPUは、メモリからデータを読み込む際に「キャッシュライン」という単位でデータを取得します。キャッシュラインは通常64バイトなど、ある程度のまとまったサイズです。
   • 以前のコード生成では、panicindexへのCALL命令が境界チェックの直後に配置されていました。panicindexはエラー発生時にのみ実行される、めったに呼び出されないコードパスです。
   • この「めったに実行されないコード」が、頻繁に実行される「正常なコードパス」と同じキャッシュラインに存在すると、キャッシュラインが無駄に占有され、より頻繁に必要とされる「有用なコード」がキャッシュから追い出される可能性がありました。
   • 特にFannkuchのようなタイトなループでは、境界チェックが頻繁に行われるため、このキャッシュの無駄が顕著なパフォーマンス低下を引き起こしていました。

2. 分岐予測の最適化:

   • 現代のCPUは、パイプライン処理を効率化するために「分岐予測」を行います。これは、条件分岐（JLTやJGEなど）がどちらのパスに進むかを事前に予測し、その予測に基づいて次の命令を先読みして実行する技術です。
   • 境界チェックは通常、ほとんどの場合で「境界内」であり、panicindexが呼び出されることは稀です。つまり、「境界外」への分岐は「予測が外れる」ケースとなります。
   • 予測が外れると、CPUはパイプラインをフラッシュし、正しいパスの命令を最初から読み込み直す必要があり、これが大きなペナルティ（ストール）となります。
   • 新しいコード生成では、JGE panicのように、panicラベルへのジャンプが「予測されない（not taken）」ことを期待する形にすることで、CPUの分岐予測器がより正確に動作し、パイプラインのストールを減らすことを目指しています。

この最適化により、特にBenchmarkFannkuch11において、amd64で-34.64%、386で-8.91%という大幅なパフォーマンス改善が見られました。これは、Fannkuchベンチマークが配列アクセスを多用し、タイトなループ内で頻繁な境界チェックが行われるため、この最適化の恩恵を最大限に受けたことを示しています。他のベンチマークでも、より控えめながらも改善が見られます。

前提知識の解説

1. Goコンパイラとリンカのアーキテクチャ

• cmd/6gとcmd/8g: これらはGo言語の初期のコンパイラで、それぞれamd64（64ビットIntel/AMDアーキテクチャ）と386（32ビットIntelアーキテクチャ）をターゲットとしていました。Goのツールチェインは、各アーキテクチャに対応するコンパイラ（gc、6g、8gなど）とリンカ（6l、8lなど）で構成されています。これらのコンパイラはGoのソースコードをアセンブリコードに変換し、リンカがそれを実行可能なバイナリに結合します。
• a.yとy.tab.c: a.yはYacc（またはBison）の文法定義ファイルで、アセンブラの構文解析ルールを記述しています。y.tab.cはa.yから生成されるC言語のソースファイルで、実際のパーサーの実装を含みます。このコミットでは、新しいアセンブリ命令形式をサポートするためにこれらのファイルが変更されています。
• cgen.c, ggen.c, gsubr.c: これらはGoコンパイラのコード生成（code generation）部分を担うC言語のソースファイルです。GoのAST（抽象構文木）からターゲットアーキテクチャのアセンブリ命令を生成するロジックが含まれています。
• optab.cとpass.c: これらはGoリンカのC言語のソースファイルです。optab.cは命令のオペコードテーブルを定義し、pass.cはリンカの主要な処理パス（命令の最適化、アドレス解決、スタックフレームの調整など）を実装しています。

2. 境界チェック (Bounds Checking)

Go言語は、メモリ安全性を保証するために、配列やスライスへのアクセス時に自動的に境界チェックを行います。例えば、a[i]というアクセスがあった場合、コンパイラはiが0以上かつlen(a)未満であることを実行時に確認するコードを挿入します。もしiが範囲外であれば、ランタイムパニック（panic: runtime error: index out of range）が発生します。

3. panicindex関数

panicindexはGoランタイムの一部であり、配列の境界チェックが失敗した際に呼び出される内部関数です。この関数が呼び出されると、プログラムの実行は停止し、スタックトレースを含むパニックメッセージが出力されます。

4. CPUキャッシュとキャッシュライン

• CPUキャッシュ: CPUはメインメモリよりも高速なSRAMベースのキャッシュメモリ（L1, L2, L3など）を持っています。CPUがデータや命令を必要とする際、まずキャッシュを検索し、見つかれば高速にアクセスできます（キャッシュヒット）。見つからなければメインメモリから読み込みます（キャッシュミス）。
• キャッシュライン: キャッシュは「キャッシュライン」という固定サイズのブロック単位でデータを扱います。例えば、64バイトのキャッシュラインの場合、CPUが1バイトのデータを要求しても、そのデータを含む64バイト全体がメモリからキャッシュに読み込まれます。
• 空間的局所性: プログラムが連続したメモリ領域にアクセスする傾向がある場合（空間的局所性）、一度キャッシュラインを読み込めば、その後のアクセスがキャッシュヒットしやすくなり、パフォーマンスが向上します。

5. 分岐予測 (Branch Prediction)

• パイプライン処理: 現代のCPUは、複数の命令を同時に処理する「パイプライン」構造を持っています。これにより、命令の実行効率が向上します。
• 分岐命令: if文やループなどの条件分岐命令は、次に実行される命令のアドレスが確定しないため、パイプライン処理のボトルネックとなる可能性があります。
• 分岐予測器: CPU内の「分岐予測器」は、過去の実行履歴に基づいて、条件分岐がどちらのパスに進むかを予測します。予測が当たればパイプラインはスムーズに流れ、外れればパイプラインをフラッシュして再構築する必要があり、大きな性能ペナルティが発生します。
• 予測ヒント: 一部のアーキテクチャでは、コンパイラが分岐命令に「予測ヒント」（例: この分岐はほとんど取られない、ほとんど取られる）を付加できる場合があります。これにより、分岐予測器の精度を高めることができます。

技術的詳細

このコミットの核心は、境界チェックのコード生成パターンを変更し、panicindexの呼び出しを「アウトオブライン」に移動させることです。

1. 境界チェックのコード生成変更

• 旧方式:

  CMP  ; 比較
  JLT ok ; 境界内ならジャンプ（予測されるパス）
  CALL panicindex ; 境界外なら呼び出し（予測されないパス）
  

ok: ... ; 正常な処理 ``` この方式では、CALL panicindex命令が正常なコードパスのすぐ隣に配置されます。CPUがJLT okを予測し、実際にokにジャンプした場合でも、CALL panicindex命令がキャッシュラインの大部分を占有している可能性があります。これは、めったに実行されないコードが頻繁にアクセスされるキャッシュラインを汚染し、キャッシュミスを誘発する原因となります。

• 新方式:

  CMP  ; 比較
  JGE panic ; 境界外ならpanicラベルにジャンプ（予測されないパス）
  ... ; 正常な処理（フォールスルー）
  

panic: CALL panicindex ; 境界外の場合の処理 ``` この変更により、panicindexの呼び出しは、正常なコードパスから離れたpanicラベルの先に配置されます。これにより、正常なコードパスがより密にキャッシュラインに収まるようになり、キャッシュ効率が向上します。CPUはJGE panicが「取られない（not taken）」ことを予測し、正常な処理をフォールスルーで実行します。これにより、分岐予測の精度も向上し、パイプラインのストールが減少します。

2. 新しい命令形式とリンカの挙動

コミットメッセージには、新しいJLT命令形式が導入されたと記載されています。

• JLT target // 通常のジャンプ
• JLT $0, target // 分岐が取られないことを期待（branch expected not taken）
• JLT $1, target // 分岐が取られることを期待（branch expected taken）

これは、コンパイラがアセンブリ命令に分岐予測のヒントを付加できるようにするためのものです。しかし、コミットメッセージの後半では、リンカがこれらの予測プレフィックスを直接出力するのではなく、**「期待される取られる分岐は逆転され、期待されるケースが取られないようにする」**と説明されています。

これは、Goのリンカが、特定の分岐命令（特に境界チェックのような、ほとんどの場合で正常パスに進む分岐）に対して、以下のような最適化を行うことを意味します。

1. コンパイラはexpecttaken(p1, 1)（分岐が取られることを期待）のようなヒントを生成します。
2. リンカは、このヒントを受け取ると、元の条件分岐命令を逆転させます（例: JLTをJGEに）。
3. これにより、**「正常なケース（境界内）がフォールスルーで実行され、異常なケース（境界外）がジャンプする」**というパターンになります。
4. CPUの分岐予測器は、通常、フォールスルーパスをデフォルトで「取られない（not taken）」と予測する傾向があるため、このリンカの変換によって、明示的な予測プレフィックスなしでも、境界チェックの分岐予測が最適化されます。

この戦略は、x86/x64アーキテクチャにおける一般的な分岐予測の挙動（フォールスルーを優先的に予測する）を利用した賢い最適化です。

3. 影響を受けるファイルと変更内容

• src/cmd/6a/a.y, src/cmd/8a/a.y: アセンブラの文法定義ファイル。新しいimm ',' rel（即値と相対アドレス）形式の命令を解析できるように文法が追加されています。これは、分岐予測ヒントを表現するための新しいアセンブリ構文に関連している可能性があります。
• src/cmd/6a/y.tab.c, src/cmd/8a/y.tab.c: a.yから生成されるパーサーのCソースファイル。文法変更に伴い、自動生成されたコードが更新されています。
• src/cmd/6g/cgen.c, src/cmd/6g/ggen.c, src/cmd/6g/gsubr.c: Goコンパイラのコード生成部分。
  • cgen.cとggen.cでは、境界チェックや除算ゼロチェックなどの箇所でexpecttaken(p1, 1)が追加されています。これは、生成される分岐命令が「取られることを期待する」というヒントを付加するためのものです。
  • gsubr.cには、expecttaken関数が追加されています。この関数はProg（プログラム命令）構造体のfrom.typeとfrom.offsetフィールドを使って、分岐予測のヒント（D_CONSTタイプとtaken値）をマークします。
• src/cmd/6l/optab.c, src/cmd/6l/pass.c: Goリンカの部分。
  • optab.cでは、yjcond（条件ジャンプ命令のテーブル）にYi0とYi1という新しいエントリが追加されています。これらは、分岐予測ヒント（$0と$1）を持つ条件ジャンプ命令に対応するものと考えられます。
  • pass.cでは、リンカの最適化パス（loop関数内）で、p->from.type == D_CONSTかつp->from.offset == 1（つまり、コンパイラが「取られることを期待する」とマークした分岐）の場合に、p->as = relinv(a)によって命令を逆転させ、p->linkとp->pcondを入れ替えるロジックが追加されています。これにより、期待されるパスがフォールスルーになるように変換されます。

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

このコミットの核心的な変更は、以下のファイルとコードスニペットに集約されます。

1. src/cmd/6g/gsubr.cにおけるexpecttaken関数の追加:

   --- a/src/cmd/6g/gsubr.c
   +++ b/src/cmd/6g/gsubr.c
   @@ -117,6 +117,16 @@ gbranch(int as, Type *t)
    	return p;
    }
    
   +/*
   + * mark branch as expected taken or not.
   + */
   +void
   +expecttaken(Prog *p, int taken)
   +{
   +	p->from.type = D_CONST;
   +	p->from.offset = taken;
   +}
   +
    /*
     * patch previous branch to jump to to.
     */
   

   この関数は、生成されたアセンブリ命令（Prog構造体）に、その分岐が「取られることを期待するか（taken=1）」または「取られないことを期待するか（taken=0）」というメタデータを付加します。このメタデータは、リンカが分岐最適化を行う際に利用されます。

2. src/cmd/6g/cgen.cおよびsrc/cmd/6g/ggen.cにおけるexpecttakenの呼び出し追加: 境界チェックや除算ゼロチェックなど、パニックが発生する可能性のある分岐命令の直後にexpecttaken(p1, 1)が追加されています。p1はgbranchによって生成された分岐命令です。taken=1は、この分岐が「取られることを期待する」（つまり、正常なケースでジャンプ先へ進む）というヒントを与えます。 例: src/cmd/6g/cgen.c

   --- a/src/cmd/6g/cgen.c
   +++ b/src/cmd/6g/cgen.c
   @@ -575,6 +575,7 @@ agen(Node *n, Node *res)
    				tnodconst(&n2, types[TUINT32], v);\
    				tgins(optoas(OCMP, types[TUINT32]), &n1, &n2);\
    				tp1 = gbranch(optoas(OGT, types[TUINT32]), T);\
   +				texpecttaken(p1, 1);\
    				tginscall(panicindex, 0);\
    				tpatch(p1, pc);\
    			}
   

3. src/cmd/6l/pass.cにおけるリンカの分岐最適化ロジックの変更: リンカのloop関数内で、コンパイラがexpecttakenでマークした分岐命令を検出した場合の処理が追加されています。

   --- a/src/cmd/6l/pass.c
   +++ b/src/cmd/6l/pass.c
   @@ -192,12 +192,25 @@ loop:
    		 * recurse to follow one path.
    		 * continue loop on the other.
    		 */
   -		q = brchain(p->link);
   -		if(q != P && q->mark)
   -		if(a != ALOOP) {
   -			p->as = relinv(a);
   -			p->link = p->pcond;
   -			p->pcond = q;
   +		if(p->from.type == D_CONST) {
   +			if(p->from.offset == 1) {
   +				/*
   +				 * expect conditional jump to be taken.
   +				 * rewrite so that's the fall-through case.
   +				 */
   +				p->as = relinv(a);
   +				q = p->link;
   +				p->link = p->pcond;
   +				p->pcond = q;
   +			}
   +		} else {			
   +			q = brchain(p->link);
   +			if(q != P && q->mark)
   +			if(a != ALOOP) {
   +				p->as = relinv(a);
   +				p->link = p->pcond;
   +				p->pcond = q;
   +			}
    		}
    		xfol(p->link, last);
    		q = brchain(p->pcond);
   

   このコードは、p->from.type == D_CONSTかつp->from.offset == 1（つまり、コンパイラが「取られることを期待する」とマークした分岐）である場合、条件分岐命令p->asをrelinv(a)（逆の条件）に変換し、ジャンプ先（p->link）とフォールスルー先（p->pcond）を入れ替えます。これにより、元の「取られることを期待する」分岐が、リンカによって「フォールスルーが期待される」形に変換され、CPUのデフォルトの分岐予測挙動に合致するようになります。

コアとなるコードの解説

expecttaken関数の役割

expecttaken関数は、コンパイラが生成するアセンブリ命令（Prog構造体）に、その命令が持つべき分岐予測の「意図」を埋め込むためのメカニズムです。Prog構造体のfromフィールドは通常、命令のソースオペランドを記述しますが、ここでは特殊な用途として、D_CONSTタイプとoffset値（0または1）を使って分岐予測ヒントを伝達します。

• p->from.type = D_CONST;：fromフィールドを定数タイプとしてマークします。
• p->from.offset = taken;：takenの値（0または1）をオフセットとして格納します。1は「この分岐は取られることを期待する」、0は「取られないことを期待する」を意味します。

このヒントは、コンパイラがアセンブリ命令を生成する段階で付加され、後続のリンカの最適化パスで利用されます。

リンカにおける分岐最適化ロジック

src/cmd/6l/pass.cの変更は、Goリンカがどのようにコンパイラからの分岐予測ヒントを解釈し、実際のコードレイアウトに反映させるかを示しています。

1. ヒントの検出: リンカは、命令リストを走査する際に、expecttakenによってD_CONSTタイプとoffset値が設定された分岐命令（Prog *p）を検出します。
2. 「取られることを期待する」分岐の変換:
   • if(p->from.offset == 1)の条件は、コンパイラが「この分岐は取られることを期待する」とマークしたケースを指します。
   • p->as = relinv(a);：relinv(a)関数は、条件分岐命令aの条件を反転させます。例えば、JLT（より小さいならジャンプ）はJGE（より大きいか等しいならジャンプ）に変換されます。
   • q = p->link; p->link = p->pcond; p->pcond = q;：これにより、命令のジャンプ先（p->link）とフォールスルー先（p->pcond）が入れ替わります。
   • 結果として、元の「取られることを期待する」分岐は、条件が反転され、かつジャンプ先とフォールスルー先が入れ替わることで、**「ほとんどの場合でフォールスルーする」**という形に変換されます。これは、CPUの分岐予測器がデフォルトでフォールスルーを予測する挙動に合致するため、予測ミスを減らす効果があります。
3. キャッシュ効率の向上: この変換により、panicindexのようなめったに実行されないコードは、正常な実行パスから物理的に離れたメモリ領域に配置されることになります。これにより、正常なコードパスがより密にキャッシュラインに収まり、キャッシュミスが減少します。

この一連の変更は、Goコンパイラとリンカが連携して、低レベルのCPUアーキテクチャ特性（キャッシュと分岐予測）を考慮した最適化を行う典型的な例です。特に、panicindexのようなエラーハンドリングパスは稀にしか実行されないため、そのコードを「コールドパス」（cold path）として分離し、メインの「ホットパス」（hot path）のキャッシュ効率を最大化する戦略が取られています。

関連リンク

• Go言語のコンパイラとツールチェインに関する公式ドキュメント: https://go.dev/doc/install/source
• Goのランタイムパニックに関する情報: https://go.dev/blog/defer-panic-and-recover
• CPUキャッシュと分岐予測に関する一般的な情報（コンピュータアーキテクチャの教科書やオンラインリソース）

参考にした情報源リンク

• Goのコミット履歴: https://github.com/golang/go/commits/master
• Goのコードレビューシステム (Gerrit): https://go-review.googlesource.com/ (コミットメッセージに記載されているCLリンク: https://golang.org/cl/6248049)
• Yacc/Bisonのドキュメント: https://www.gnu.org/software/bison/manual/
• CPUアーキテクチャに関する一般的な知識（キャッシュ、パイプライン、分岐予測など）